OptNet: Differentiable Optimization as a Layer in Neural Networks
By Brandon Amos, J. Kolter. 2017
1,283 citations recorded by the source corpus.
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. In this paper, 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, we show that the method is capable of learning 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 our architecture to learn hard constraints better than other neural architectures.
Subfields: Computational Mechanics, Numerical Analysis, Statistical and Nonlinear Physics, Model Architectures, 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 Computational Mechanics
- Fabian Pedregosa
- Chunhua Shen
- Guosheng Lin
- Valentina Zantedeschi
- Byron Boots
- Vlad Niculae
- Matt J. Kusner
- Subhransu Maji
In Numerical Analysis
- Shane T. Barratt
- Steven Diamond
- Chunhua Shen
- Guosheng Lin
- Chi Zhang
- Yujun Cai
- Vlad Niculae
- Matt J. Kusner
In Statistical and Nonlinear Physics
- Sergey Levine
- Nils Thürey
- Aravind Rajeswaran
- Vladlen Koltun
- Chelsea Finn
- Byron Boots
- Igor Mordatch
- Bistra N. Dilkina
In Model Architectures
In Optimization & Training
- Simon Lacoste-Julien
- Fabian Pedregosa
- Sergey Levine
- Sham M. Kakade
- Chelsea Finn
- Stefano Soatto
- Byron Boots
- Zeyuan Allen-Zhu
In Mathematical Optimization
- Chi Zhang
- Chunhua Shen
- Yujun Cai
- Guosheng Lin
- Byron Boots
- Simon Lacoste-Julien
- J. Kolter
- Andreas Krause
Citations in the corpus
- Neural Ordinary Differential Equations (2018, neutral): “If truly convergent dynamics are required, replacing the ODE solver with a differentiable black-box optimizer, as in OptNet (Amos and Kolter, 2017), would be more appropriate.”
- Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation (2021, background): “The implicit function theorem allows for seamless integration of optimization problems into larger end-to-end trainable neural networks (Gould et al., 2016; Amos & Kolter, 2017; Blondel et al., 2021; El Ghaoui et al., 2021).”
- Meta-Learning With Differentiable Convex Optimization (2019, methodology): “We solve the dual QP of Equation 10 using [1] which implements a differentiable GPU-based QP solver.”
- Deep Learning for Distributed Optimization: Applications to Wireless Resource Management (2019, background): “Since a convex projection can be realized with linear operations, the gradient of the activation in (10) that solves the convex projection problem is well-defined [31], and the backpropagation works well with this activation.”
- On the Differentiability of the Solution to Convex Optimization Problems (2018, background): “Thus, our results confirm the findings of Amos and Kolter, generalize them to the general convex optimization setting, and provide conditions under which the Jacobian is well-defined.”
- Implicit Behavioral Cloning (2021, background): “Many other works have investigated using the notion of implicit functions in 225 learning, including works that investigate implicit layers [39, 40, 41, 42].”
- Automatic differentiation in machine learning: a survey (2015, methodology): “cent interest is implicit and iterative AD techniques (Griewank and Walther, 2008), which has found use in work incorporating constrained optimization within deep learning (Amos and Kolter, 2017) and probabilistic graphical models and neural networks (Johnson et al.”
- Adaptively Sparse Transformers (2019, background): “Since entmax is defined through an optimization problem, this is non-trivial and cannot be simply handled through automatic differentiation; it falls within the domain of argmin differentiation, an active research topic in optimization (Gould et al., 2016; Amos and Kolter, 2017).”
- Deep Equilibrium Models (2019, background): “There has been a growing interest in implicit layers in recent years [37, 3, 37, 50], but the precise formulation of the DEQ is quite different, and our current models represent the largest-scale practical application of implicit layers in deep learning of which we are aware.”
- Recurrent Relational Networks (2017, methodology): “Amos and Kolter [2017] Introduces OptNet, a neural network layer that solve quadratic programs using an efficient differentiable solver. OptNet is trained to solve 4x4 Sudokus amongst other problems and beats the deep convolutional network baseline as described in Park [2016]. Unfortunately we canno”
- Deep Declarative Networks (2019, methodology): “Amos and Kolter [4] also show how to differentiate through an optimization problem, for the specific case of quadratic programs (QPs).”
- Lagrangian Duality for Constrained Deep Learning (2020, background): “e, but is receiving increasing attention, such as the efforts in jointly training prediction and optimization models [38, 25, 27] and incorporating optimization algorithms into differentiable systems [17, 4, 39]. This research originated in an attempt to apply deep learning to fundamentally differen”
- Efficient and Modular Implicit Differentiation (2021, methodology): “Another line of applications is “optimization as a layer” [42, 6, 51, 27, 36, 7], which usually includes regularization or constraints in the optimization problem in order to impose desirable structure on the layer output.”
- Transformers learn in-context by gradient descent (2022, background): “First, to exceed upon a single step of gradient descent in every self-attention layer it could be advantageous to incorporate so called declarative nodes (Amos & Kolter, 2017; Bai et al., 2019; Gould et al., 2021; Zucchet & Sacramento, 2022) into Transformer architectures.”
- Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization (2018, methodology): “Accordingly, it is easy to show that the RHS matrix is nonsingular by applying the same logic as (Amos and Kolter 2017) (Theorem 1).”
- Differentiable Top-k with Optimal Transport (2020, methodology): “Specifically, motivated by the implicit differentiation (Duchi et al., 2008; Griewank and Walther, 2008; Amos and Kolter, 2017; Luise et al., 2018) techniques, we first parameterize the top-k operation in terms of the optimal solution of an Optimal Transport (OT) problem.”
- Solver-in-the-Loop: Learning from Differentiable Physics to Interact with Iterative PDE-Solvers (2020, methodology): “Our work shares the motivation of previous work to use differentiable components at training time [1, 14, 58, 9] and frameworks for differentiable programming [50, 25, 26, 23].”
- Safe Exploration in Continuous Action Spaces (2018, methodology): “First, the solution there relied on an in-graph implementation of a full QP solver (Amos & Kolter, 2017), which runs an iterative interior-point algorithm with each forward propagation.”
- Under review as a conference paper at ICLR 2020 3 L INEAR INEQUALITY CONSTRAINTS FOR DEEP LEARNING MODELS We consider a generic L layer neural network (2019, methodology): “One might consider OptNet (Amos & Kolter, 2017) and an analogous version of the method introduced by Pathak et al. (2015) as baselines.”