PaperlayerView exact revision on arXiv

Source-linked AI summary

Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems

Tommaso Giovannelli, Griffin Dean Kent, Luis Nunes Vicente

arXiv:2110.00604v3math.OCcs.LGstat.ML

TL;DR

Bilevel stochastic optimization is used in machine-learning settings, but practical methods face challenges with high-dimensional variables and lower-level constraints. This paper develops a framework and convergence theory for constrained and unconstrained problems with inexact calculations, alongside practical implementations; on continual-learning instances, BSG-N-FD has iteration performance similar to BSG-1 and StocBiO but is slightly slower.

  • Problem

    Existing constrained bilevel approaches are limited to linear lower-level constraints or constraints depending only on y, despite machine-learning applications with lower-level constraints.

    Source: §1.2 · p. 4, §1.3 · p. 5

  • Method

    The paper develops a BSG framework and convergence theory for constrained and unconstrained lower-level problems, covering inexact adjoint calculations and noisy estimates.

    Source: §1.3 · p. 5, §2.3 · p. 8, §2.4 · p. 9

  • Results

    On continual-learning instances, BSG-N-FD has similar iteration performance to BSG-1 and StocBiO but is slightly outperformed in time.

    Source: §6 · p. 37

  • Takeaways & Limitations

    The paper provides low-rank practical BSG implementations for large-scale bilevel problems, and reports that BSG-N-FD, BSG-1, and StocBiO perform well on continual-learning instances in iterations and computational time.

    Source: §6 · p. 37

    Large datasets may prevent using all training and validation data from previous continual-learning tasks, making subsets necessary.

    Source: §5.4 · p. 32

Abstract

from arXiv · show

Two-level stochastic optimization formulations have become instrumental in a number of machine learning contexts such as continual learning, neural architecture search, adversarial learning, and hyperparameter tuning. Practical stochastic bilevel optimization problems become challenging in optimization or learning scenarios where the number of variables is high or there are constraints. In this paper, we introduce a bilevel stochastic gradient method for bilevel problems with nonlinear and possibly nonconvex lower-level constraints. We also present a comprehensive convergence theory that addresses both the lower-level unconstrained and constrained cases and covers all inexact calculations of the adjoint gradient (also called hypergradient), such as the inexact solution of the lower-level problem, inexact computation of the adjoint formula (due to the inexact solution of the adjoint equation or use of a truncated Neumann series), and noisy estimates of the gradients, Hessians, and Jacobians involved. To promote the use of bilevel optimization in large-scale learning, we have developed new low-rank practical bilevel stochastic gradient methods (BSG-N-FD and~BSG-1) that do not require second-order derivatives and, in the lower-level unconstrained case, dismiss any matrix-vector products.

1 Introduction

The introduction frames bilevel optimization as a nested upper- and lower-level problem and motivates stochastic methods for machine-learning applications. It presents a framework spanning constrained and unconstrained lower-level problems, a convergence theory for inexact calculations, and practical implementations for large-scale problems.

1.1 Bilevel machine learning

  • Continual learning, neural architecture search, adversarial training, and hyperparameter tuning are presented as machine-learning applications of bilevel optimization.In continual learning, each task uses an upper-level validation objective and a lower-level training objective; the sequence of tasks motivates concern about catastrophic forgetting.Source: §1.1 · p. 3

1.2 Bilevel stochastic descent

  • Bilevel stochastic gradients sample gradients and Hessians at an approximate lower-level solution, so the direction can be inexact even with full-batch calculations.The introduction describes the upper-level update as stochastic-gradient descent and notes that related DARTS calculations can approximate matrix-vector products with finite differences.Source: §1.2 · p. 4
  • Existing BSG methods mainly address unconstrained lower-level problems, while cited constrained approaches are limited to linear constraints or constraints depending only on y.The paper focuses on implicit differentiation; prior approaches also include iterative differentiation, and truncated Neumann approximations can require a strong norm condition or a typically unknown bound.Source: §1.2 · p. 4

1.3 Contributions of the paper

  • The paper proposes a BSG framework for both unconstrained and general nonlinear, possibly nonconvex, lower-level constraints, a case the authors say prior work had not covered algorithmically or theoretically.Its convergence theory covers inexact lower-level solutions, inexact adjoint calculations, and noisy gradient, Hessian, and Jacobian estimates.Source: §1.3 · p. 5
  • The practical BSG-N-FD and BSG-1 implementations target large-scale bilevel problems by avoiding Hessian-vector products and, for BSG-1, explicit adjoint-equation solves.BSG-N-FD uses an iterative adjoint solve with finite differences; BSG-1 uses rank-1 Hessian approximations.Source: §1.3 · p. 5

1.4 Organization of this paper

  • The paper proceeds from the method and its assumptions to convergence rates, numerical experiments, and concluding remarks.The experiments cover synthetic quadratic bilevel problems and continual-learning instances, with and without lower-level constraints.Source: §1.4 · pp. 5–6

2 The bilevel stochastic gradient method

The BSG method estimates an upper-level descent direction using stochastic gradients and an approximate lower-level solution, with separate adjoint formulas for unconstrained and constrained lower-level problems. It updates the upper-level variables and supports inexact adjoint calculations.

2.1 The unconstrained lower-level case

  • In the unconstrained lower-level case, BSG approximates the adjoint gradient using stochastic estimates of upper-level gradients and lower-level gradients and Hessians.BSG-N-FD uses iterative methods with finite differences; BSG-1 uses rank-one approximations and solves the resulting adjoint equation in the least-squares sense.Source: §2.1 · p. 6

2.2 The constrained lower-level case

  • For constrained lower-level problems, sensitivity of the KKT system yields an adjoint-gradient formula using gradients and Jacobians, with the negative adjoint gradient giving a descent direction.The lower-level constraints may include inequalities and equalities; the formulation uses their KKT conditions and associated multipliers.Source: §2.2 · pp. 7–8

2.3 A unified notation for LL unconstrained and constrained cases

  • A unified notation represents the lower-level variables as y when unconstrained and v when constrained, allowing one algorithm to cover both cases.The unified method goal and variable convention are stated across the two cases.Source: §2.3 · p. 8

2.4 The BSG method

  • BSG alternates an approximate lower-level solve, a stochastic descent-direction calculation, and an upper-level update, projecting onto X when it is closed and convex.The direction may use the unconstrained or constrained adjoint formula.Source: §2.4 · p. 9

2 The bilevel stochastic gradient method

  • Lower-level solutions, stochastic quantities, and adjoint-direction calculations are treated as approximate within the BSG framework.The method description permits any optimization method to approximately solve the lower-level problem before computing the direction.Source: §2.4 · p. 9, §2.5 · p. 9

2.5 Computing the BSG direction inexactly

  • Inexact adjoint directions can arise from either an inexact adjoint-equation solve or a truncated Neumann-series approximation, whose accuracy increases with the truncation parameter q.The Neumann-series approach is stated for q > 0 and ∥B∥ < 1.Source: §2.5 · p. 9

3 Assumptions, sensitivity, and smoothness

The convergence analysis covers unconstrained and constrained lower-level problems under smoothness, boundedness, and sensitivity assumptions. It establishes controls on approximate BSG directions and Lipschitz continuity of the true objective’s gradient.

3 Assumptions, sensitivity, and smoothness

  • The convergence framework covers both unconstrained and constrained lower-level problems, inexact lower-level solutions, and inexact adjoint-direction calculations.It extends stochastic-gradient convergence analysis to the bilevel setting with decaying step sizes.Source: §3 · p. 10

3.1.1 LL unconstrained case

  • For unconstrained lower-level problems, the assumptions require smooth bounded derivatives and a unique solution with a positive-definite lower-level Hessian and uniformly bounded inverse.The inverse-Hessian bound is described as equivalent to strong convexity in the lower-level variables.Source: §3.1.1 · p. 10

3.1.2 LL constrained case

  • For constrained lower-level problems, the assumptions include smooth bounded derivatives and multipliers, plus LICQ, strict complementarity, and second-order sufficiency at a KKT solution.These conditions ensure a strict local minimizer; further positive-semidefinite Lagrangian-Hessian conditions can ensure a unique global minimizer.Source: §3.1.2 · p. 11, Assumption 3.5 (Existence and… · p. 11

Assumption 3.5 (Existence and uniqueness of solution (LL constrained case))

  • In the constrained case, uniformly bounded inverses of the KKT matrices provide the counterpart to the unconstrained Hessian non-singularity bound.The paper identifies this condition as the constrained analogue of uniform convexity.Source: Assumption 3.5 (Existence and… · p. 11

3.2 Sensitivity of the approximate bilevel stochastic gradient direction

  • Sensitivity assumptions bound how the BSG direction changes with its input data, and Proposition 3.1 verifies these bounds for inexact adjoint solves or truncated Neumann series.For stochastic estimates, the stated result additionally assumes Lipschitz continuity in the lower-level variable.Source: §3.2 · pp. 12–13

3.3 Smoothness of the true objective function

  • Under the stated assumptions, the true objective has a Lipschitz-continuous gradient in x.The paper derives this smoothness from Lipschitz continuity of the lower-level solution mappings and involved derivatives, together with Hessian or KKT-matrix bounds away from singularity.Source: §3.3 · p. 16

4 Convergence rate of the BSG method

The section establishes convergence guarantees for BSG across nonconvex, strongly convex, and convex objectives, covering constrained and unconstrained lower-level problems and inexact BSG directions. It also gives conditions for controlling lower-level solution error and stochastic-estimation noise.

4 Convergence rate of the BSG method

  • The convergence analysis covers both lower-level constrained and unconstrained cases, including stochastic inexact lower-level solutions and inexact BSG directions.It applies regardless of the approach used to compute the inexact BSG direction.Source: §4 · p. 16

4.1 Rate in the nonconvex case

  • For nonconvex objectives, the analysis uses a decaying stepsize and assumes the objective values along the iterates are bounded below.The section presents a convergence theorem under these and the stated assumptions, but the supplied theorem passage does not expose its rate.Source: §4.1 · pp. 17–18

4.2 Rate in the strongly convex case

  • Strongly convex objectives yield a sublinear 1/k convergence rate under a decaying stepsize, but this setting requires strong practical restrictions.The paper notes that this case corresponds in practice to an affine y(x), restricting the lower-level problem to a QP.Source: §4.2 · p. 19

4.3 Rate in the convex case

  • For convex objectives that attain a minimizer, BSG has a sublinear convergence rate slower than the strongly convex case.The paper notes that the affine y(x) requirement considerably restricts the choice of lower-level problems.Source: §4.3 · p. 20

4.4 Imposing a bound on the distance from the LL optimal solution

  • In the unconstrained lower-level case, taking k^2 stochastic-gradient steps with stepsize β_i = γ/i can enforce a bound on the distance to the lower-level solution.This uses a strongly convex lower-level objective and the stated classical sampling assumptions.Source: §4.4 · p. 20

4.5 Imposing a bound on dynamic sampling

  • Dynamic sampling controls estimation noise by increasing mini-batch sizes as the upper-level stepsize decreases.The batch sizes are chosen so the estimation error bound is at most C_D α_k.Source: §4.5 · p. 21

5 Numerical experiments

The numerical experiments target the practical BSG-N-FD and BSG-1 implementations on synthetic quadratic bilevel problems and continual-learning problems. The supplied passages describe their mechanisms and experimental setup, but not comparative experimental outcomes.

5.1 Our practical BSG methods

  • The experiments test practical BSG implementations on synthetic quadratic bilevel problems and continual-learning problems, focusing on BSG-N-FD and BSG-1 rather than standard BSG.They also include BSG-H on synthetic problems for comparison; the test problems omit upper-level constraints.Source: §5.1 · p. 22

5.1.1 BSG-N-FD

  • BSG-N-FD solves the adjoint system iteratively while approximating each Hessian-vector product with finite differences.The unconstrained case uses linear CG; the constrained case uses GMRES.Source: §5.1.1 · p. 23

5.1.2 BSG-1

  • BSG-1 approximates second-order derivatives in the adjoint formulas with outer products of the corresponding gradients.The paper reports that these rank-one approximations perform well when the lower-level function has a Gauss-Newton structure, such as the binary cross-entropy loss used for continual learning.Source: §5.1.2 · p. 24

5.1 Our practical BSG methods

  • BSG-1 avoids computing Hessians and Hessian-vector products, while BSG-N-FD uses finite differences to avoid Hessian-vector products.These designs address the second-order derivative costs identified as a difficulty for large-scale machine-learning bilevel problems.Source: §5.1.1 · p. 23, §5.1.2 · p. 24

5.2 DARTS

DARTS is described for stochastic bilevel optimization in neural architecture search, with only the unconstrained lower-level case considered. It takes one stochastic-gradient step on the lower-level problem, then updates the upper-level variables using an approximated descent direction.

5.2 DARTS

  • DARTS addresses stochastic bilevel problems with an unconstrained lower level and approximates a second-order matrix-vector product using finite differences.Its finite-difference scaling is ε = 0.01/∥∇_y f_u(x_k, ỹ_k)∥.Source: §5.2 · p. 25
  • Each DARTS iteration takes one fixed-stepsize stochastic-gradient step on the lower-level problem, then updates the upper-level variables along an approximated descent direction.The upper-level update uses a stepsize α_k.Source: §5.2 · p. 25

5.3 Numerical results for synthetic quadratic bilevel problems

On synthetic quadratic bilevel problems, the BSG methods are compared across unconstrained, linear-constraint, and quadratic-constraint lower levels. BSG-N-FD is consistently strong under stochastic noise, while BSG-H’s performance can deteriorate when Hessian noise is high.

5.3 Numerical results for synthetic quadratic bilevel problems

  • The tests use synthetic problems with quadratic objectives and compare an unconstrained lower level with linear and quadratic lower-level constraints.The unconstrained case uses dimension 300 at both levels and adds Gaussian noise to gradient and Hessian estimates in its stochastic experiments.Source: §5.3 · p. 26, §5.3.1 · p. 26

5.3.1 Results for the LL unconstrained case

  • In deterministic unconstrained tests, BSG-N-FD and BSG-H outperform the other methods in iterations and time, and alone reach the true optimum within the limits.BSG-H takes more time than BSG-N-FD because computing Hessian matrices is costly.Source: §5.3.1 · pp. 27–28, Figure 1 · p. 27
  • With stochastic estimates, BSG-N-FD performs best in iterations and time, while BSG-1 and DARTS retain iteration performance similar to the deterministic case.BSG-H needs more iterations and time to attain a similar function value; its performance degrades substantially when Hessian noise exceeds the tested standard deviation of 0.05.Source: Figure 1 · p. 27, §5.3.1 · p. 28

5.3.2 Results for the LL linearly constrained case

  • For deterministic linear constraints, BSG-N-FD and BSG-H outperform SIGD in iterations and time, with identical iteration performance.The experiments use 300 variables at each level and 50 constraints; the stochastic settings vary Hessian-noise standard deviation.Source: §5.3.2 · pp. 28, 30, Figure 2 · p. 29
  • With low Hessian noise and linear constraints, BSG-H outperforms SIGD in iterations and time, while BSG-N-FD is more time-efficient in the long run.At high Hessian noise, BSG-N-FD is the superior method; SIGD cannot converge, and no convergent step sizes were found for BSG-H.Source: §5.3.2 · pp. 28, 30, Figure 2 · p. 29

5.3.3 Results for the LL quadratically constrained case

  • For deterministic quadratic constraints, BSG-N-FD and BSG-H have the same performance in iterations and time, although BSG-N-FD’s time-efficiency advantage becomes clearer over longer runs.The experiments use 300 variables at each level and five constraints.Source: §5.3.3 · p. 30, Figure 3 · p. 31
  • With low Hessian noise and quadratic constraints, BSG-H retains nearly its deterministic behavior while BSG-N-FD is affected by noise.At high Hessian noise, BSG-N-FD’s performance remains unchanged, whereas no step sizes were found that let BSG-H converge.Source: §5.3.3 · pp. 30, 32, Figure 3 · p. 31

5.4 Continual learning

The continual-learning formulation treats each arriving task as a bilevel problem, using validation error at the upper level and training error at the lower level. Lower-level inequality constraints are introduced to address deterioration in accuracy on earlier tasks, while dataset size may limit use of all past samples.

5.4 Continual learning

  • The model parameters are split into λ_t and δ_t to provide flexibility in minimizing training and validation classification error across the task sequence.For a neural network, the cited strategy assigns hidden-layer weights to λ_t and output-layer weights to δ_t [21].Source: §5.4 · p. 32
  • At each stage, the upper level minimizes validation error over the current and previous tasks, while the lower level minimizes training error over those tasks.The task-specific objectives change as new tasks are added.Source: §5.4 · p. 32
  • Large datasets may prevent using all past tasks’ training and validation samples; this paper does not use subsets because its focus is stochastic bilevel problems.Source: §5.4 · p. 32
  • Adding a new task can deteriorate accuracy on previous tasks, and lower-level inequality constraints are used to ensure the current model outperforms the old model on those tasks.The constraints may be nonconvex for neural networks; the paper’s theory covers nonconvex lower-level constraints when the lower-level SOSC holds.Source: §5.4 · pp. 32–33

5.5 Results for continual learning instances

The continual-learning experiments compare BSG-N-FD and BSG-1 with other methods on unconstrained lower-level problems, and compare the two BSG methods when lower-level constraints are added. The reported results distinguish iteration performance from elapsed time.

5.5 Results for continual learning instances

  • The experiments use CIFAR-10 with five sequential tasks, expanding from two classes in the first task to all ten in the fifth.The model has two convolutional layers, a max-pooling layer, and one fully connected layer; only the training and validation images are used.Source: §5.5 · p. 33
  • The comparisons track upper-level iterations and elapsed time, and plot an approximation of the true objective function.For the unconstrained comparison, the methods use selected step sizes from grid searches; most use an increasing-accuracy strategy for lower-level iterations.Source: §5.5 · pp. 33, 36
  • On unconstrained tasks, BSG-N-FD, BSG-1, and StocBiO perform similarly in iterations and lead on all but the first two tasks; DARTS leads on the first two.DARTS falls behind on the last two tasks, while the three other methods perform similarly on the last three.Source: Figure 4 · p. 34, §5.5 · p. 36
  • With lower-level constraints, BSG-N-FD leads in iterations except on the first task, where both methods perform similarly.In elapsed time, BSG-1 is slightly better except on the first task; both methods plateau after task two as iterations per task decrease substantially.Source: Figure 5 · p. 35, §5.5 · p. 36

6 Concluding remarks and future work

The conclusion presents a BSG framework for unconstrained and constrained lower-level problems, with convergence theory covering inexact adjoint-gradient calculations and lower-level solutions. Its practical methods perform similarly in iterations on continual-learning instances, while the authors identify possible applications and future work.

6 Concluding remarks and future work

  • The proposed convergence theory covers unconstrained and constrained lower-level problems, including inexact adjoint-gradient calculations and inexact lower-level solutions.The paper also introduces BSG-N-FD and BSG-1 as practical methods for large-scale bilevel optimization.Source: §6 · p. 36
  • On continual-learning instances, BSG-N-FD performs similarly to BSG-1 and StocBiO in iterations and is slightly outperformed in time.The conclusion also reports that BSG-N-FD performs well on the synthetic quadratic bilevel problem.Source: §6 · p. 37
  • The authors suggest the methods have potential for unconstrained neural architecture search and note that variance-reduction techniques remain future work.They point to low-rank Hessian approximations or finite differences as important for the extreme dimensions of resulting bilevel problems.Source: §6 · p. 37

A Proposition 3.1

The supplied proof passages treat errors in the adjoint calculation through residuals and use inverse-matrix perturbation bounds. They also invoke bounded constants and Lipschitz continuity to establish the stated estimates.

A Proposition 3.1

  • The proof bounds inverse differences using the product of the two inverse norms and the difference between the matrices.It then defines constants and uses equivalence of norms to complete the estimate.Source: A Proposition 3.1 · pp. 42–43
  • For an inexact adjoint system, the approximate direction includes a residual error in the adjoint-equation solution.The proof uses constants defined from problem bounds and residual norms to establish its estimate.Source: A Proposition 3.1 · p. 42
  • For a truncated Neumann series, the approximate direction uses an inverse approximation represented by a residual matrix.The proof reuses the reasoning for the inexact adjoint system.Source: A Proposition 3.1 · p. 42
  • The stochastic-data estimate follows from Lipschitz continuity of the stochastic gradients, Hessians, and Jacobians.The proof identifies a positive constant that bounds the estimate.Source: A Proposition 3.1 · p. 43

B Proposition 3.2

The proof uses bounds on the derivatives of the lower-level solution mappings to establish their Lipschitz continuity in the upper-level variable. It then applies Lipschitz bounds to gradient terms in the unconstrained case and follows similar steps for the constrained case.

B Proposition 3.2

  • In the unconstrained case, bounds on the derivatives of y(x) and w(x) imply that both mappings are Lipschitz continuous in x.The proof gives the common bound Lℓ for their Lipschitz constants.Source: B Proposition 3.2 · p. 43
  • The unconstrained proof uses Lipschitz continuity of the upper-level gradient and related terms to bound the gradient difference.It concludes with a bound involving L∇f and constants for the component terms.Source: B Proposition 3.2 · p. 43
  • For the constrained case, the proof follows similar steps but first establishes Lipschitz continuity for terms in the constrained adjoint gradient.The proof cites Lipschitz continuity of Hessian terms, Jacobians, multipliers, and boundedness of terms.Source: B Proposition 3.2 · pp. 43–44

C Theorem 4.4

The proof of Theorem 4.4 derives an optimality gap in function values and concludes the first result.

C Theorem 4.4

  • The argument applies Assumption 4.3 and inequalities (3.5), (3.9), and (4.7) in its derivation.Source: C Theorem 4.4 · p. 44
  • After taking total expectation, the proof denotes M = Gd + 2CdΘ and uses induction to establish the first result.The induction step cites [43, Eq. (2.9) and (2.10)].Source: C Theorem 4.4 · p. 44
  • The proof derives an optimality gap in function values by taking total expectation and using the optimality condition at x∗.It invokes (C.1), (C.2), and PX∇f(x∗) = 0.Source: C Theorem 4.4 · p. 45

D Theorem 4.5

The proof of Theorem 4.5 adapts the preceding theorem’s argument using Assumption 4.5 and (D.1), then sums the resulting inequalities.

D Theorem 4.5

  • The proof reuses the argument for Theorem 4.4, substituting (D.1) to obtain the corresponding inequality.Source: D Theorem 4.5 · p. 45
  • It rearranges the inequality, takes total expectation, and divides by αk before summing over s = 0, 1, . . . , k.Source: D Theorem 4.5 · p. 45
  • The desired result follows using Assumption 4.3 and the steps of [36, Theorem 5.3].Source: D Theorem 4.5 · p. 45

Related papers

Loading 2110.00604v3…