Differentiable Convex Optimization Layers

By Akshay Agrawal, Brandon Amos, Shane T. Barratt, Stephen P. Boyd, Steven Diamond, J. Kolter. 2019

894 citations recorded by the source corpus.

Recent work has shown how to embed differentiable optimization problems (that is, problems whose solutions can be backpropagated through) as layers within deep learning architectures. This method provides a useful inductive bias for certain problems, but existing software for differentiable optimization layers is rigid and difficult to apply to new settings. In this paper, we propose an approach to differentiating through disciplined convex programs, a subclass of convex optimization problems used by domain-specific languages (DSLs) for convex optimization. We introduce disciplined parametrized programming, a subset of disciplined convex programming, and we show that every disciplined parametrized program can be represented as the composition of an affine map from parameters to problem data, a solver, and an affine map from the solver’s solution to a solution of the original problem (a new form we refer to as affine-solver-affine form). We then demonstrate how to efficiently differentiate through each of these components, allowing for end-to-end analytical differentiation through the entire convex program. We implement our methodology in version 1.1 of CVXPY, a popular Python-embedded DSL for convex optimization, and additionally implement differentiable layers for disciplined convex programs in PyTorch and TensorFlow 2.0. Our implementation significantly lowers the barrier to using convex optimization problems in differentiable programs. We present applications in linear machine learning models and in stochastic control, and we show that our layer is competitive (in execution time) compared to specialized differentiable solvers from past work.

Subfields: Artificial Intelligence, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation (2021, background): “Recent works in deep learning have successfully applied implicit differentiation to large-scale language modelling (Bai et al., 2019), semantic segmentation (Bai et al., 2020), meta-learning (Rajeswaran et al., 2019), neural architecture search (Zhang et al., 2021b), and more (Agrawal et al., 2019).”
Meta-Learning with Less Forgetting on Large-Scale Non-Stationary Task Distributions (2022, positive): “Therefore, for simplicity, we use CVXPY [1] for efficient approximation.”
Learning Binary Trees via Sparse Relaxation (2020, neutral): “General algorithms for quadratic Amos & Kolter (2017) and disciplined convex programming (Section 7, Amos, 2019; Agrawal et al., 2019a,b) have been given, as well as expressions for more speciﬁc cases like isotonic regression (Djolonga & Krause, 2017).”
Adversarial Robustness with Semi-Infinite Constrained Learning (2021, background): “While several heuristic algorithms exist for this setting, many focus on restricted classes of constraints [116–120] and those that can handle more general constraints come at the cost of added computation complexity [121, 122].”
Deep Declarative Networks (2019, background): “Indeed differentiation can be automated for convex programs by extending disciplined convex programming frameworks [1].”
Gradient Estimation with Stochastic Softmax Tricks (2020, methodology): “This idea is not ours and is enjoying renewed interest in [3, 4, 5].”
Efficient and Modular Implicit Differentiation (2021, background): “One example of such pre-processing is to convert the parameters to be differentiated from one form to another canonical form, such as a quadratic program [6] or a conic program [2].”
Safe Control With Learned Certificates: A Survey of Neural Lyapunov, Barrier, and Contraction Methods for Robotics and Control (2022, background): “Examples that learn CLF or CBF certificates that imply controllers include [10], [12], [21], [55], [56], [57], [58], [59], and [60].”
RAFT: Recurrent All-Pairs Field Transforms for Optical Flow (2020, background): “This has motivated several works to embed optimization problems into network architectures [4,3,43,32,44].”
Super-efficiency of automatic differentiation for functions defined as a minimum (2020, background): “It is also the cornerstone of the use of convex optimization as layers in neural networks (Agrawal et al., 2019).”
DeepEMD: Differentiable Earth Mover's Distance for Few-Shot Learning (2020, methodology): “to the problem parameters. With the same theory, Amos and Kolter [76] design a batched Quadratic Programming solver as a layer that can be integrated into a neural network for end-to-end training. In [77], Agrawal et al. propose a differentiable convex optimization layer which can differentiate thro”