Source-linked AI summary
On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, Edison Guo
TL;DR
Bi-level optimization couples an upper objective to a parameterized lower-level argmin or argmax, creating a need to differentiate the lower-level solution. The report collects exact differentiation results with and without constraints, illustrates them through gradient calculations and a softmax-classifier example, and discusses practical limitations for large-scale and non-smooth problems.
Problem
Bi-level learning requires gradients through parameterized lower-level argmin or argmax solutions, whose closed-form expressions are not always available.
Method
The report collects differentiation results for unconstrained and constrained parameterized argmin and argmax problems and develops motivating gradient-based examples.
Results
The report presents exact gradients for parameterized argmin and argmax problems, including equality- and inequality-constrained cases.
Takeaways & Limitations
The results support gradient-descent approaches for bi-level optimization and motivate expressive end-to-end models containing optimization sub-problems.
Takeaways & Limitations
The exact methods require smooth optimized functions and a Hessian inverse, while non-smooth large-scale bi-level problems remain an open direction involving unresolved computational questions.
Abstract
from arXiv · showhide
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.
1 Introduction
The report motivates bi-level optimization in machine learning and computer vision and aims to collect differentiation results for parameterized argmin and argmax problems, including constrained cases.
- 1 Introduction: Bi-level optimization defines an upper objective over x and y while a lower problem binds y as a function of x, typically through minimization.The upper-level variable is chosen knowing that the lower-level problem will follow optimally.
- 1 Introduction: Although bi-level optimization can be viewed as constrained optimization, its structure merits separate study when the lower-level argmin lacks a closed-form solution.The report therefore focuses on first-order gradient-based techniques, which are important in machine learning and computer vision.
- 1 Introduction: The report’s main aim is to collect results on differentiating parameterized argmin and argmax problems and revisit them for first-order procedures in bi-level optimization.Earlier work considered some unconstrained and equality-constrained argmin cases, while this report adds motivating examples in the deep-learning context.
- 1 Introduction: The report covers unconstrained argmin and argmax problems, then extends the results to equality and inequality constraints.It includes gradient calculations, discussion, a softmax-classifier bi-level example, and supplementary Python code.
2 Background
The background compares analytic, optimality-condition, and gradient-descent approaches to bi-level optimization, motivating direct differentiation of lower-level solutions for scalable learning.
- 2 Background: An analytic lower-level solution y⋆(x) reduces bi-level optimization to a single-level problem, but such a solution may be difficult to compute or may not exist.The lower-level problem must effectively be solved in closed form for this approach.
- 2 Background: Replacing the lower-level problem with sufficient optimality conditions, such as KKT conditions for convex problems, yields a constrained optimization problem.The conditions can be hard to express, and the resulting problem can remain difficult or become non-convex even when the lower-level problem is convex.
- 2 Background: Gradient descent instead differentiates the lower-level solution with respect to upper-level variables and updates the upper-level objective without explicitly finding y⋆(x).This requires efficiently solving the lower-level problem and finding the gradient at the current solution.
- 2 Background: This gradient-based approach is motivated by large-scale, end-to-end machine learning, where first-order and stochastic gradient methods are often preferred.The report studies gradients of parameterized argmin and argmax problems whose parameters are optimized through an external objective or learned parameterized function.
3 Unconstrained Optimization Problems
The section derives gradients for unconstrained parameterized argmin and argmax solutions, including vector-valued variables and non-unique stationary points. It applies these results to distance minimization, soft-max maximum likelihood, and monotonic transformations.
- Scalar and vector argmin: Under continuity and first- and second-derivative assumptions, the derivative of a scalar argmin solution follows by implicit differentiation without requiring a closed-form solution.The lower-level optimum may be non-unique, with any minimum point selected.
- Scalar and vector argmin: The vector-valued argmin result extends the scalar case by differentiating with respect to each parameter and using the Hessian and mixed derivatives.For multiple parameters, the inverse Hessian can be reused across derivative systems until x or g(x) changes.
- Argmax extension: The same stationary-point derivation applies to argmax problems, so the result does not depend on selecting a local minimum.The argmax lemma assumes continuity and first and second derivatives.
- Examples: The distance-minimization example compares the implicit gradient from Lemma 3.1 with the known analytic mean solution.The objective minimizes summed squared distances to parameterized points h_i(x).
- Examples: For functions with multiple stationary points, the derived gradient tracks each point locally, but iterative bi-level optimization must consistently select corresponding solutions across updates.The example includes three stationary points over the stated parameter ranges, including one solution independent of x.
- Invariance under monotonic transformations: Composing the objective with a smooth monotonic transformation preserves stationary points and the derivative of the argmin solution.The report illustrates this with exponentiation, for which the transformed and original solutions coincide.
4 Constrained Optimization Problems
The paper extends argmin and argmax differentiation to lower-level problems with linear equality and arbitrary inequality constraints. Equality constraints are handled through null-space or direct constrained formulations, while inequality constraints are approximated with log barriers.
- Scope: The constrained results extend argmin and argmax differentiation to problems with linear equality and arbitrary inequality constraints.These extensions are presented as the focus of the constrained-optimization section.
- Equality Constraints: For linear equalities Ay = b, the solution derivative can be obtained by parameterizing feasible points as y0 + Fz, where F spans the null-space of A.The reduced derivative uses the Hessian and mixed derivative projected into the null-space.
- Equality Constraints: The equality-constrained derivative remains feasible because g′(x) lies in the null-space of A.When A = 0 and b = 0, the expression reduces to the unconstrained vector argmin result.
- Inequality Constraints: For inequality constraints, a log-barrier converts the problem into an unconstrained approximation controlled by a scaling factor t.In convex problems, t also controls the approximation or duality gap.
- Inequality Constraints: The resulting inequality-constrained argmin gradient is approximated by applying the unconstrained differentiation result to the barrier problem.If constraint functions do not depend on x, the expression simplifies because φXY(x, y) is zero.
- Examples: In the positivity example, the barrier approximation converges to the true function and gradient as t approaches infinity.The example compares g(x) = argminy≥0 (x − y)^2 with barrier approximations gt(x).
5 Bi-level Optimization Example
The example applies constrained argmax differentiation to tune a three-class soft-max classifier so its maximum-likelihood feature vectors reach prescribed locations. Gradient descent positions the targets evenly around the unit circle and converges rapidly.
- The experiment optimizes classifier parameters so three constrained maximum-likelihood feature vectors reach given target locations.The feature vectors are constrained to the unit ball centered at the origin.
- The target locations are set evenly around the unit circle, and the final parameter settings achieve them.
- The objective decreases rapidly during the first 20 iterations and converges within 10^-9 of the optimum in under 100 iterations.
- The learning curve plots objective value against iteration number on a log-scale.Figure 6 also compares initial and final likelihood surfaces under the constraint ∥x∥2 ≤1.
6 Discussion
The report presents exact gradients for parameterized argmin and argmax problems to support gradient-based bi-level optimization. It notes smoothness and Hessian-inversion requirements while identifying large-scale, non-smooth settings as open challenges.
- The reported differentiation results provide exact gradients for parameterized argmin and argmax problems and support solving bi-level problems by gradient descent.
- The exact-gradient approach requires a smooth optimized function and computing a Hessian matrix inverse, which may be expensive at large scale.
- Non-smooth functions can be handled in practice by approximating the function or perturbing the current solution to a nearby differentiable point.
- For large-scale problems, a diagonal Hessian approximation can still provide a descent direction in CNN parameter learning for video recognition.
- Future work includes efficient gradients for non-smooth large-scale problems, warm starts, descent directions, and non-exact lower-level solutions.The report specifically identifies whether approximate lower-level solutions can still yield descent directions as an open question.
- The report aims to support expressive end-to-end models that include optimization sub-problems.