On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization

By Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, Edison Guo. 2016

249 citations recorded by the source corpus.

Some recent works in machine learning and computer vision involve the solution of a bi-level optimization problem. Here the solution of a parameterized lower-level problem binds variables that appear in the objective of an upper-level problem. The lower-level problem typically appears as an argmin or argmax optimization problem. Many techniques have been proposed to solve bi-level optimization problems, including gradient descent, which is popular with current end-to-end learning approaches. In this technical report we collect some results on differentiating argmin and argmax optimization problems with and without constraints and provide some insightful motivating examples.

Subfields: Computational Mechanics, Computer Graphics and Computer-Aided Design, Numerical Analysis, Optimization & Training

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

In Computer Graphics and Computer-Aided Design

In Numerical Analysis

In Optimization & Training

Citations in the corpus

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, background): “We observe that two additional properties arising from the convex nature that allows efficient metalearning: implicit differentiation of the optimization [2, 11] and the low-rank nature of the classifier in the few-shot setting.”
OptNet: Differentiable Optimization as a Layer in Neural Networks (2017, background): “In the case of Gould et al. (2016), the authors describe general techniques for differentiation through optimization problems, but only describe the case of exact equality constraints rather than both equality and inequality constraints (in the case inequality constraints, they add these via a…”
Video Representation Learning Using Discriminative Pooling (2018, methodology): “By applying Lemma 3.3 of [17], this gradient of the argmin at an optimum SVMP solution w ∗ can be shown to be the following: where the ﬁrst term captures the inverse of the Hessian evaluated at w ∗ and the second term is the second-order derivative wrt z and w .”
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).”
Differentiating through the Fréchet Mean (2020, methodology): “Theoretical foundations of differentiating through the argmin operator have been provided in Gould et al. (2016).”
Truncated Back-propagation for Bilevel Optimization (2018, unknown): “[7] assume that ŵ⇤ S( ) = w ⇤ S and compute r ŵ⇤ S( ) by implicit di↵erentiation.”
Efficient and Modular Implicit Differentiation (2021, methodology): “We now show that the KKT conditions, manually differentiated in several works [19, 35, 6, 53, 52], fit our framework.”
Learning Binary Trees via Sparse Relaxation (2020, methodology): “Solving an optimization problem as a diﬀerentiable module within a parent problem tackled with gradient-based optimization methods is known as argmin diﬀerentiation, a particular instance of bi-level optimization (Gould et al., 2016).”
End-to-End Representation Learning for Correlation Filter Based Tracking (2017, background): “[11] have recently considered differentiating the solution to general argmin problems without restricting themselves to iterative procedures.”
Deep Declarative Networks (2019, background): “[31] addressed the question of computing gradients for these problems by GOULD ET AL.”
Task-based End-to-end Model Learning (2017, unknown): “Recent approaches have looked into similar argmin differentiations (Gould et al., 2016; Amos et al., 2016), though the methodology we present here is more general and handles the stochasticity of the objective.”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, methodology): “In recent years, gradient-based methods for problem (3) have become increasingly popular including implicit differentiation (Domke, 2012; Pedregosa, 2016; Gould et al., 2016; Ji et al., 2021) and iterative differentiation (Maclaurin et al.”
Bilevel Optimization: Convergence Analysis and Enhanced Design (2020, methodology): “, 2005; Moore, 2010) and gradientbased methods (Domke, 2012; Pedregosa, 2016; Gould et al., 2016; Maclaurin et al., 2015; Franceschi et al., 2018; Ghadimi & Wang, 2018; Liao et al., 2018; Shaban et al., 2019; Hong et al., 2020; Liu et al., 2020; Li et al., 2020; Grazzi et al., 2020; Lorraine et al.,”
Graph Contrastive Learning Automated (2021, methodology): “, 2019), or first-order techniques based on some inner-loop approximated solution (Maclaurin et al., 2015; Pedregosa, 2016; Gould et al., 2016).”