PaperlayerView exact revision on arXiv

Source-linked AI summary

OptNet: Differentiable Optimization as a Layer in Neural Networks

Brandon Amos, J. Zico Kolter

arXiv:1703.00443v5cs.LGcs.AImath.OCstat.ML

TL;DR

The paper asks how exact constrained optimization can function as a trainable deep-network layer while expressing dependencies conventional layers may miss. OptNet uses differentiable quadratic-program layers with a GPU batch solver, and experiments report improved denoising and data-driven Sudoku solving; the approach remains computationally and practically limited.

  • Problem

    Deep networks need layers that can express constraints and complex dependencies, but conventional layers provide relatively simple transformations for such inference tasks.

  • Method

    OptNet inserts quadratic programs as neural-network layers, differentiates their KKT conditions, and solves batched instances with a GPU primal-dual interior-point method.

  • Results

    OptNet improves test MSE over the total-variation solution by 12% and solves problems such as learning 4x4 Sudoku purely from data.

  • Takeaways & Limitations

    Optimization layers add a neural-network primitive for tasks involving hard constraints and relationships that existing networks may handle poorly.

  • Takeaways & Limitations

    Exact OptNet solves have cubic complexity, with fewer than 1000 hidden dimensions reported as practical and substantially fewer preferred for real-time results.

Abstract

from arXiv · show

This paper presents OptNet, a network architecture that integrates optimization problems (here, specifically in the form of quadratic programs) as individual layers in larger end-to-end trainable deep networks. These layers encode constraints and complex dependencies between the hidden states that traditional convolutional and fully-connected layers often cannot capture. We explore the foundations for such an architecture: we show how techniques from sensitivity analysis, bilevel optimization, and implicit differentiation can be used to exactly differentiate through these layers and with respect to layer parameters; we develop a highly efficient solver for these layers that exploits fast GPU-based batch solves within a primal-dual interior point method, and which provides backpropagation gradients with virtually no additional cost on top of the solve; and we highlight the application of these approaches in several problems. In one notable example, the method is learns to play mini-Sudoku (4x4) given just input and output games, with no a-priori information about the rules of the game; this highlights the ability of OptNet to learn hard constraints better than other neural architectures.

1. Introduction

OptNet treats exact constrained optimization as a trainable neural-network layer, using quadratic programs to express richer dependencies and inference procedures than conventional layers.

  • Architecture: OptNet makes the output of a layer the solution to a constrained optimization problem parameterized by previous-layer values.This framework can represent complex operations within individual layers and support end-to-end training.
  • Architecture: The paper specializes OptNet layers to small quadratic programs because they capture interesting behavior and can be solved efficiently on GPUs.
  • Differentiation: QP data parameters can depend differentiably on the previous layer and be optimized like ordinary neural-network weights.The authors derive gradients by differentiating the optimization problem’s KKT conditions at its solution.
  • Solver: A custom primal-dual interior-point solver simultaneously solves batches of small QPs using dense GPU operations.The solver is reported to solve QP batches over 100 times faster than highly tuned solvers such as Gurobi and CPLEX.
  • Applications: The architecture is presented as enabling richer end-to-end training for tasks requiring inference procedures inside a neural network.

2. Background and related work

The related-work discussion positions OptNet among optimization-based inference and differentiation methods, emphasizing its treatment of constrained problems and insertion at arbitrary network layers.

  • Optimization in learning: Optimization-based inference appears across classification, structured prediction, vision, control, statistics, and physical simulation applications.
  • Related architectures: Energy-based and structured-prediction methods shape energies around observed data, but some settings lack the observed data these approaches require.
  • Differentiation alternatives: Analytic-gradient approaches apply when an analytic argmin solution exists, whereas the constrained problems studied here have no known analytic solutions.
  • Differentiation alternatives: Unrolling is straightforward for many unconstrained optimization procedures but becomes difficult when constraints require projection operators.OptNet instead uses argmin differentiation rather than unrolling the optimization procedure.
  • Argmin differentiation: Compared with closely related argmin-differentiation work, OptNet differentiates inequality constraints and general linear equality constraints and permits optimization layers anywhere in the network.

3. OptNet: solving optimization within a neural network

OptNet layers solve quadratic programs and differentiate their solutions through KKT conditions, combining broad representational power with efficient GPU batching but substantial computational and tuning costs.

  • QP layer: An OptNet forward pass sets up a quadratic program and returns its optimal solution as the layer output.The QP uses a positive-semidefinite quadratic term, linear term, equality constraints, and inequality constraints.
  • Differentiation: The backward pass differentiates the QP’s KKT conditions to obtain derivatives of the solution with respect to its input parameters.This uses matrix differential calculus and can extend to more general convex optimization problems.
  • Differentiation: Backpropagation avoids explicitly forming Jacobians and computes parameter gradients through matrix-vector products and the factored KKT system.
  • Solver: The GPU primal-dual interior-point method solves QP batches and reuses its LU factorization, making additional backward-pass computation virtually nonexistent relative to solving.The approach addresses the lack of GPU-parallel batch capability in standard solvers such as Gurobi and CPLEX.
  • Properties: Under Q ≻ 0 and full-row-rank equality constraints, OptNet outputs are subdifferentiable everywhere and differentiable except on a measure-zero set.
  • Representational power: OptNet can represent elementwise piecewise-linear functions with O(nk) parameters and ReLU layers with O(mn) parameters.
  • Representational power: Some functions representable by OptNet cannot be represented exactly by two-layer ReLU networks and require exponentially many units to approximate.
  • Limitations: Exact OptNet solves have cubic complexity in variables or constraints, limiting practical layers to fewer than 1000 hidden dimensions and substantially fewer for real-time use.

4. Experimental results

The experiments evaluate OptNet's computational efficiency and its ability to improve or learn denoising procedures from data. The results show faster batched QP solving and improved denoising when the optimization layer is fine-tuned to the task.

  • 4.1. Batch QP solver performance: OptNet layers are substantially more computationally expensive than linear layers, but remain tractable in practical contexts.The comparison uses minibatches of 128 and input dimensions of 10, 50, 100, and 500.
  • 4.2.1. BASELINE: TOTAL VARIATION DENOISING: Total variation denoising achieves a minimum test MSE of about 16.5 at λ ≈13.The baseline varies λ from 0 to 100; only relative algorithm performance is considered meaningful for the reported error units.
  • 4.2.2. LEARNING TO DENOISE: A fully connected neural network performs substantially worse than the convex optimization baseline on the denoising task.The task uses piecewise constant signals corrupted with independent Gaussian noise.
  • 4.2.3. LEARNING THE DIFFERENCING OPERATOR: The learned differencing matrix is mainly sparse with neighboring entries of alternating sign, matching the intuition behind total variation denoising.This structure suggests total variation is appropriate for the generated dataset, while other noise processes could lead to a different learned operator.
  • 4.2.4. FINE-TUNING AND IMPROVING THE TOTAL VARIATION SOLUTION: Fine-tuning an OptNet layer initialized with the total variation differencing matrix improves test MSE by 12% over the total variation solution.The procedure improves both training and testing MSE.

4.3. MNIST

The mini-Sudoku experiment tests whether OptNet can learn strict puzzle constraints from unsolved and solved examples. OptNet generalizes better to unseen puzzles than the convolutional baseline, which overfits.

  • Task setup: Mini-Sudoku provides input-output examples without revealing the rules, making it a benchmark for learning strict relationships among variables.The input is a one-hot 4x4x4 tensor with unknown entries zeroed, and the output is the one-hot encoded solution.
  • Model: The OptNet layer uses a generic standard-form QP with positivity constraints, arbitrary Ax = b constraints, Q = 0.1I, and the input encoding as q.The model receives no explicit Sudoku rules.

5. Conclusion

The paper presents OptNet as a neural architecture that embeds optimization problems as network layers and derives the machinery needed to train them end to end. It combines differentiable optimization with an efficient batch solver for practical use.

  • Conclusion: OptNet uses optimization problems as single network layers and derives algorithms for differentiating through them during end-to-end backpropagation.The architecture supports optimization layers within larger neural networks.
  • Conclusion: The paper develops an efficient batch solver based on a primal-dual interior point method and obtains the required gradient information with virtually no additional solve cost.

A. MNIST Experiment

The MNIST experiment compares a fully connected network with an OptNet layer inserted before the SoftMax output. Both networks perform similarly, with OptNet showing slightly lower error and variance.

  • A. MNIST Experiment: The experiment compares FC600-FC10-FC10-SoftMax with FC600-FC10-Optnet10-SoftMax.The OptNet layer uses inequality constraints and the previous layer only in the linear objective term.
  • A. MNIST Experiment: Figure 6 reports similar results for both networks, with slightly lower error and less variance when OptNet is the final layer.

B. Denoising Experiment Details

The denoising details compare a learned fully connected predictor with convex total-variation optimization and a generic learned OptNet denoising layer. The fully connected network performs substantially worse than the convex optimization baseline, while the generic OptNet variant is limited by over-regularization.

  • B. Denoising Experiment Details: Figure 7 shows fully connected-network denoising error, while Figure 8 shows error from fine-tuning the total-variation solution.

C. Representational power of the QP OptNet layer

The section defers proofs of the representational-power results to the appendix. It identifies those proofs as based on established properties.

  • The section contains proofs for results highlighted earlier in Section 3.2.
  • The included proofs are described as straightforward.
  • The proofs follow from well-known properties and are included for completeness.

C.1. Proof of Theorem 1

Theorem 1 establishes regularity of OptNet-layer solutions under strict convexity and a rank assumption, with differentiability failing only at degenerate points.

  • OptNet layers are subdifferentiable from strictly convex QPs because their solutions are continuous.The proof relies on Q ≻0 and the continuity of strictly convex QP solutions.
  • The Jacobian is unique except on a measure zero set, and the proof assumes A has full row rank.The full-row-rank assumption can be relaxed.
  • The KKT differential matrix is nonsingular when exactly one of each inequality's slack and dual variable is zero.The proof scales the second block by D(λ⋆)^−1 to obtain a standard nonsingular KKT system.
  • At degenerate solutions, the KKT matrix can be singular while the Jacobian equations still have solutions, which are not unique.Degeneracy occurs when an inequality is tight and its dual variable is zero.

C.2. Proof of Theorem 2

Theorem 2's proof represents piecewise-linear univariate functions through sums of shifted maxima and encodes them directly with an OptNet layer.

  • Any piecewise-linear univariate function can be written in sum-of-max form.The construction proceeds across breakpoints, adding scaled linear terms for successive pieces.
  • The OptNet layer encodes each shifted-max term through linear inequality constraints.The constraints are aix + bi ≤ ti for i = 1, . . . , k.
  • The objective selects the smallest feasible t values, yielding the desired maximum terms.Applying the construction coordinatewise gives a multivariate elementwise function.
  • A ReLU layer is represented as a corresponding OptNet problem with the constraint z ≥0.

C.3. Proof of Theorem 3

Theorem 3 contrasts the representational geometry of OptNet layers with two-layer ReLU networks. A three-term maximum can be represented compactly by OptNet but may require exponentially many ReLU units for close approximation.

  • A two-layer ReLU network can require exponentially more units than an OptNet layer to approximate some multivariate functions.The theorem considers a single-output ReLU network with a ReLU followed by a linear layer.
  • For a three-term pointwise maximum, OptNet and ReLU networks have different crease geometries.Figure 9 contrasts the creases of the three-term maximum with those of a ReLU network.
  • Approximating the three-term maximum arbitrarily closely with ReLUs can require an exponential-size covering of the input space.
  • The example is limited because the function can be exactly approximated using a Maxout network.The authors also note other functions for which they found no compact representation, including simplex projection.
Loading 1703.00443v5…