Alternating Differentiation for Optimization Layers

arXiv2210.01802MaRDI QIDQ6412907FDOQ6412907

Haixiang Sun, Jingya Wang, Ye Shi, H. Vincent Poor, Dacheng Tao, Hoang Duong Tuan

Publication date: 3 October 2022

Abstract: The idea of embedding optimization problems into deep neural networks as optimization layers to encode constraints and inductive priors has taken hold in recent years. Most existing methods focus on implicitly differentiating Karush-Kuhn-Tucker (KKT) conditions in a way that requires expensive computations on the Jacobian matrix, which can be slow and memory-intensive. In this paper, we developed a new framework, named Alternating Differentiation (Alt-Diff), that differentiates optimization problems (here, specifically in the form of convex optimization problems with polyhedral constraints) in a fast and recursive way. Alt-Diff decouples the differentiation procedure into a primal update and a dual update in an alternating way. Accordingly, Alt-Diff substantially decreases the dimensions of the Jacobian matrix especially for optimization with large-scale constraints and thus increases the computational speed of implicit differentiation. We show that the gradients obtained by Alt-Diff are consistent with those obtained by differentiating KKT conditions. In addition, we propose to truncate Alt-Diff to further accelerate the computational speed. Under some standard assumptions, we show that the truncation error of gradients is upper bounded by the same order of variables' estimation error. Therefore, Alt-Diff can be truncated to further increase computational speed without sacrificing much accuracy. A series of comprehensive experiments validate the superiority of Alt-Diff.

Has companion code repository: https://github.com/hxsun08/alt-diff

This page was built for publication: Alternating Differentiation for Optimization Layers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6412907)