PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentiable Convex Optimization Layers

Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, Zico Kolter

arXiv:1910.12430v1cs.LGmath.OCstat.ML

TL;DR

Existing differentiable optimization layers are rigid because users must manually transform problems into canonical forms. This paper introduces DPP and ASA form to differentiate through disciplined convex programs, with applications in machine learning and stochastic control and runtime competitive with a specialized QP solver.

  • Problem

    Existing convex optimization layers require users to manually transform problems into rigid canonical forms, a tedious and error-prone process requiring convex-analysis familiarity.

  • Method

    The paper introduces DPP and ASA form, representing parametrized disciplined convex programs through affine parameter-to-data and solution-to-original-solution maps around a solver.

  • Results

    The layer supports sensitivity analysis for linear machine learning models and learning control-Lyapunov policies for stochastic control, while achieving runtime competitive with OptNet's specialized qpth solver for QPs.

  • Takeaways & Limitations

    DPP and ASA form enable differentiation through convex-optimization DSLs without explicitly backpropagating through canonicalization, supporting applications across control and machine learning.

  • Takeaways & Limitations

    At nondifferentiable solutions, the method computes a heuristic derivative using a least-squares solution when the derivative system is not invertible; the cone program is assumed to have a unique solution.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the rigidity of existing differentiable convex optimization layers by bringing DSL-style modeling to differentiable convex programs. It introduces DPP and ASA form, implements them in common machine-learning software, and demonstrates applications and competitive runtime.

  • Motivation: Existing convex optimization layers are difficult to use because users must manually transform problems into rigid canonical forms.The process is described as tedious, error-prone, time-consuming, and requiring familiarity with convex analysis.
  • Contributions: DPP is a grammar for parametrized convex programs that enables their reduction to ASA form.ASA form composes an affine map from parameters to problem data, a solver, and an affine map to recover the original solution.
  • Contributions: DPP and ASA form enable differentiation through convex-optimization DSLs without explicitly backpropagating through canonicalization operations.
  • Implementation: The authors implement DPP and ASA reduction in CVXPY 1.1, with differentiable layers for PyTorch and TensorFlow 2.0.They report that the software substantially lowers the barrier to using convex optimization layers in differentiable programs and neural networks.
  • Applications: The layer is applied to sensitivity analysis for linear machine-learning models and learning control-Lyapunov policies for stochastic control.
  • Evaluation: The layer’s runtime for quadratic programs is competitive with OptNet’s specialized solver qpth.

2 Related work

Prior work established differentiation through convex optimization and DSL-based modeling separately. This paper connects them through parametrized canonicalization and solution-map differentiation, while retaining compatibility with different cone solvers.

  • Convex optimization DSLs: Convex optimization DSLs use disciplined convex programming to express problems naturally and canonicalize them into cone programs.DCP guarantees convexity, while canonicalization expands nonlinear functions through graph implementations.
  • Convex optimization DSLs: DPP restricts parameter usage within DCP so parametrized programs can be reduced to ASA form.
  • Differentiable optimization: Convex programs can be differentiated by implicitly differentiating their optimality conditions when regularity conditions hold.
  • Differentiable optimization: Differentiating the cone-program solution map allows the method to pair with any convex cone-program solver.Methods that differentiate every optimization step must instead be customized for each algorithm and provide approximate derivatives.

3 Background

The paper treats parametrized convex programs as solution maps from parameters to optimization solutions and uses DCP/DPP-compatible canonicalization to connect them to cone solvers. The formulation assumes unique solutions in the relevant cone-program setting.

  • Convex optimization problems: A parametrized convex optimization problem minimizes a convex objective subject to convex inequalities and affine equalities.The optimization variable is x ∈ R^n and the parameter vector is θ ∈ R^p.
  • Convex optimization problems: When the solution map is single-valued, S maps parameters θ to an optimal solution x⋆.The paper differentiates S with respect to θ for DPP-compliant programs when the derivative exists.
  • Disciplined convex programming: DCP constructs convex optimization problems from atoms with known curvature and monotonicity using a composition rule.
  • Cone programs: A cone program uses problem data A, b, and c together with a nonempty, closed, convex cone K.The paper assumes the cone program has a unique solution.
  • Cone-program solvers: The differentiable-layer method calls a conic solver in the forward pass to map cone-program data (A, b, c) to a solution x⋆.
  • Cone-program solvers: DCP-based DSLs canonicalize disciplined convex programs into equivalent cone programs whose data depend on the parameters and canonicalization procedure.

4 Differentiating through disciplined convex programs

The section introduces DPP and ASA form to make parametrized disciplined convex programs differentiable without backpropagating through canonicalization. It then describes affine canonicalization, cone-solver differentiation, and solution retrieval.

  • ASA form: The solution map is decomposed as R ◦ s ◦ C, where C canonicalizes parameters, s solves the cone program, and R retrieves the original solution.ASA form requires C and R to be affine, enabling the chain rule for differentiation.
  • DPP: DPP is a grammar whose programs are convex and guaranteed to reduce to ASA form.Unlike DCP, DPP restricts parameter usage so canonicalization and retrieval are affine.
  • DPP: A disciplined parametrized program uses convex objectives, concave upper bounds, and affine equality expressions constructed under DPP.Parameters and variables are distinguished by whether expressions are parameter-affine or parameter-free.
  • DPP: DPP can rewrite noncompliant parameter expressions by introducing variables, constraints, or reparameterized inputs.Examples include replacing p1p2 with p1s subject to s = p2, and replacing e/p1 with ep2 where p2 represents 1/p1.
  • Canonicalization: Canonicalization represents problem data using sparse linear maps, so repeated parameter updates use sparse matrix multiplication rather than rerunning graph expansion.The adjoint canonicalization derivative is obtained by transposing the sparse representation.
  • Cone-solver differentiation: Cone-program derivatives are obtained by implicitly differentiating optimality conditions, while nondifferentiable solutions use a least-squares heuristic.The heuristic applies when the derivative system is not invertible.

5 Implementation

The implementation integrates DPP and ASA reduction into CVXPY 1.1 and provides differentiable layers for PyTorch and TensorFlow 2.0. Examples show layer construction, backpropagation, and applications to logistic sensitivity analysis and stochastic-control learning.

  • Software: CVXPY 1.1 implements DPP and ASA reduction, while PyTorch and TensorFlow 2.0 receive differentiable convex optimization layers.The layers implement the forward and backward maps and support batched inputs.
  • Software: The implementation modifies diffcp for performance by adding C++ components, dense direct solves, and parallelizable forward and backward passes.diffcp supplies derivatives of cone programs.
  • Software: The software is presented as the first DSL for differentiable convex optimization layers and is released as open-source.The implementation combines DPP and ASA form with PyTorch and TensorFlow layers.
  • Usage: A CVXPY example declares parameters, variables, an objective, and constraints, then verifies DPP compliance.The example uses a norm objective with a nonnegative regularization parameter.
  • Usage: Calling the PyTorch layer applies R ◦s ◦C and backpropagates the summed solution with respect to F_t, g_t, and lambd_t.Layer construction first canonicalizes the problem to extract C and R.
  • Applications: Figure 1 visualizes training-data gradients for a logistic model, showing directions that torque the learned hyperplane toward the test-loss-minimizing hyperplane.The gradients are black lines attached to the training points.

6 Examples

The paper demonstrates differentiable convex optimization in data poisoning and stochastic control, showing how gradients and optimization layers support these applications. In stochastic control, gradient descent reduced average cost by roughly 40%.

  • 6.1 Data poisoning attack: A data-poisoning adversary perturbs each training point by δ_i with ∥δ_i∥∞≤0.01 to increase test loss.The adversary uses gradients of test loss with respect to training data to choose perturbation directions.
  • 6.1 Data poisoning attack: The predicted test-loss increase from poisoning is (0.01) Σ_i=1^N ∥∇_x_iL_test(θ⋆)∥_1.This quantity is computed from gradients obtained through the fitted optimization problem.
  • 6.1 Data poisoning attack: The numerical poisoning example uses 30 training points and 30 test points in R^2 with logistic regression and elastic-net regularization.The training points are treated as DPP parameters, and the layer provides gradients of test loss with respect to them.
  • 6.2 Convex approximate dynamic programming: The stochastic-control problem has dynamics x_t+1 = A x_t + B φ(x_t) + ω_t, with controls constrained to a convex set U.When U is not affine, the problem is generally difficult to solve; the policy is the optimization variable.
  • 6.2 Convex approximate dynamic programming: Approximate dynamic programming parameterizes the policy, and stochastic gradient descent differentiates through the SOCP used to evaluate the policy.The example optimizes parameters P, Q, and q for a quadratic control-Lyapunov policy.
  • 6.2 Convex approximate dynamic programming: Roughly 40%: the numerical stochastic-control example decreased average cost by this amount over gradient-descent iterations.The experiment used x ∈ R^2, u ∈ R^3, a horizon of T = 25, and batch size 8, initialized from the unconstrained LQR solution.

7 Evaluation

The evaluation finds that the implementation reduces canonicalization time and performs competitively with qpth on dense QPs while being substantially faster on sparse QPs. The comparison separates canonicalization and solution-retrieval costs for cvxpylayers.

  • Canonicalization: An order-of-magnitude speed-up: the extension accelerates canonicalization on average by computing C through a sparse matrix multiply rather than the DSL.Table 1 compares CVXPY 1.0.23 and 1.1 across 10 runs on a single CPU core.
  • Comparison to specialized layers: Figure 3 compares PyTorch CvxpyLayer with qpth over 10 trials on dense and sparse QPs.For cvxpylayers, canonicalization and solution-retrieval times are reported separately for fair comparison.
  • Comparison to specialized layers: The dense QP has n = 128, m = 0, and p = 128, while the sparse QP has n = 1024, m = 1024, and p = 1024.In the sparse problem, Q, A, and G each have 1% nonzeros.
  • Comparison to specialized layers: Roughly 5 times faster: the implementation outperforms qpth on the sparse QP, while remaining competitive on the dense QP even on the GPU.The sparse advantage comes from sparse operations and LSQR, which qpth cannot exploit.

8 Discussion

The discussion situates the method among specialized solvers, nonconvex differentiation methods, and the DPP/ASA reduction. It emphasizes solver flexibility and analytical differentiation while describing recursive affine-expression processing.

  • Other solvers: Specialized solvers can outperform general conic solvers, but CVXPY’s backend architecture allows DPP and ASA form to extend to other problem classes.The paper identifies OSQP, L-BFGS, and SAGA as examples of specialized alternatives and plans future QP-solver interfaces.
  • Nonconvex problems: Convex layers are preferred over nonconvex layers when possible because convex programs can typically be solved efficiently and accurately, especially for low-latency inference.The discussion contrasts analytical differentiation and SGD unrolling as approaches for nonconvex problems.
  • Canonicalization map: The canonicalization proof recursively represents affine-expression-tree operations using tensors associated with each subtree.DPP rules ensure that one tensor in each argument has nonzero entries only in the final parameter-related slice.
  • Canonicalization map: The recursion combines child tensors through ψ and sums the resulting terms to obtain the tensor at the parent node.Leaf cases separately encode variables, parameters, and constants.
  • Canonicalization map: Variable, parameter, and constant leaves produce tensors encoding variable mappings, parameter mappings, and constant values, respectively.These tensor constructions provide the base cases for the affine-expression-tree recursion.

B Derivative of a cone program

This section models a cone-program solver as a differentiable composition and derives its adjoint for backpropagation. It also describes an implicit-differentiation computation and a least-squares fallback when the relevant system is singular.

  • Primal-dual form of a cone program: A cone program has primal and dual optimization forms linked by feasibility, cone-membership, and complementarity conditions.The primal uses x and slack s, while the dual uses y and the dual cone K∗.
  • Primal-dual form of a cone program: Every convex optimization problem can be reformulated as a convex cone program.
  • Homogeneous self-dual embedding: The homogeneous self-dual embedding converts solving the cone program into finding a zero of a normalized residual map.The embedding partitions z into (u, v, w) and uses projection onto R^n × K∗ × R+.
  • Differentiation: The solver map ψ is decomposed as φ ◦ s ◦ Q: data become Q, s solves the embedding, and φ recovers the primal-dual solution.This decomposition enables differentiation through each component and supports adjoint computation for backpropagation.
  • Differentiation: Backpropagation applies the adjoint derivatives of φ, s, and Q in reverse order, with dy = ds = 0 when the layer outputs only x.The derivative of s is obtained by implicitly differentiating the normalized residual map.
  • Non-differentiability: When the system matrix M is not invertible, the method approximates the derivative using a least-squares solution.For large M, LSQR can avoid materializing and factorizing the matrix by requiring only multiplication by M and M^T.

C Examples

The examples show how CVXPY problems are wrapped as differentiable PyTorch layers for logistic regression and stochastic control. The layer specification exposes parameters as inputs and selected optimization variables as outputs.

  • The appendix includes code for the paper’s examples.
  • Logistic regression: The logistic-regression example maximizes regularized log likelihood and exposes X as a layer parameter while returning β and b.The objective includes ℓ1 and squared-ℓ2 regularization.
  • Stochastic control: The stochastic-control example minimizes a quadratic objective subject to a norm bound on u and the equality y = P_21u.

D TensorFlow layer

The TensorFlow 2.0 layer uses a CvxpyLayer inside GradientTape to return an optimization solution and gradients with respect to its parameters.

  • The TensorFlow example constructs CvxpyLayer with F, g, and λ as parameters and x as the optimization output.
  • GradientTape computes dF, dg, and dλ from the returned x_star.

E Additional examples

The additional examples implement common neural-network operations and constrained optimization layers through CVXPY. They include projections, entropy-based mappings, constrained variants, and a quadratic-program layer.

  • Projection layers: ReLU is interpreted as projecting x onto the non-negative orthant, and the corresponding layer minimizes ||x − y||² subject to y ≥ 0.
  • Entropy-based layers: The sigmoid or logistic function is interpreted as projection onto the interior of the unit hypercube using a binary-entropy objective.The implementation minimizes a linear term in x and binary entropy terms.
  • Simplex layers: The simplex mapping uses an entropy objective with 0 < y < 1 and 1^T y = 1, while sparsemax uses Euclidean projection onto the simplex.
  • Constrained layers: Constrained softmax adds an upper bound y ≤ u to the entropy-based simplex problem.
  • Constrained layers: Constrained sparsemax adds componentwise bounds 0 ≤ y ≤ u to the Euclidean simplex projection.
  • Constrained layers: The Limited Multi-Label layer uses a binary-entropy objective with 1^T y = k, and its CVXPY implementation exposes x as the parameter.
  • Quadratic-program layer: The OptNet layer is reimplemented as a convex quadratic program with equality and inequality constraints, using Q_sqrt, q, A, b, G, and h as parameters.The matrix square root of Q is taken outside the CVXPY layer because DPP does not allow the quadratic-form atom to be parametrized.
Loading 1910.12430v1…