PaperlayerView exact revision on arXiv

Source-linked AI summary

A Fully First-Order Method for Stochastic Bilevel Optimization

Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, Robert Nowak

arXiv:2301.10945v1math.OCcs.AIcs.LG

TL;DR

Computing a bilevel solution entails tracking the lower-level optimum, while existing methods may require derivatives beyond first order or lack finite-time guarantees. F2SA uses only first-order gradients and gradually increases a multiplier. It establishes explicit finite-time rates across stochastic regimes and can outperform second-order methods in MNIST data-hypercleaning experiments.

  • Problem

    Bilevel optimization requires tracking the lower-level optimum, and prior methods may require Jacobian or Hessian estimates or lack non-asymptotic guarantees.

    Source: §1 · p. 2

  • Method

    F2SA uses only first-order gradients and gradually increases a multiplier to obtain a consistent estimator with finite-time convergence guarantees.

    Source: §1 · p. 2, §1.1 · pp. 2–3

  • Results

    ~O(epsilon^-3.5), ~O(epsilon^-2.5), and ~O(epsilon^-1.5) iterations apply when both gradients, only the upper-level gradient, or neither is noisy; momentum improves the stochastic rates to ~O(epsilon^-2.5) and ~O(epsilon^-2), and F2SA can outperform second-order methods on MNIST data-hypercleaning.

    Source: §1.1 · p. 3, §4.4 · p. 12

  • Takeaways & Limitations

    A polynomial-rate increase of the multiplier is sufficient, and an adaptive choice is not needed for good practical performance.

    Source: §4.4 · p. 12

    Studying fully first-order methods beyond strongly-convex lower-level problems and with variable-dependent constraints remains future work.

    Source: §6 · p. 13

Abstract

from arXiv · show

We consider stochastic unconstrained bilevel optimization problems when only the first-order gradient oracles are available. While numerous optimization methods have been proposed for tackling bilevel problems, existing methods either tend to require possibly expensive calculations regarding Hessians of lower-level objectives, or lack rigorous finite-time performance guarantees. In this work, we propose a Fully First-order Stochastic Approximation (F2SA) method, and study its non-asymptotic convergence properties. Specifically, we show that F2SA converges to an $\epsilon$-stationary solution of the bilevel problem after $\epsilon^{-7/2}, \epsilon^{-5/2}$, and $\epsilon^{-3/2}$ iterations (each iteration using $O(1)$ samples) when stochastic noises are in both level objectives, only in the upper-level objective, and not present (deterministic settings), respectively. We further show that if we employ momentum-assisted gradient estimators, the iteration complexities can be improved to $\epsilon^{-5/2}, \epsilon^{-4/2}$, and $\epsilon^{-3/2}$, respectively. We demonstrate even superior practical performance of the proposed method over existing second-order based approaches on MNIST data-hypercleaning experiments.

1 Introduction

The paper targets stochastic bilevel optimization where hyper-gradient computation requires costly lower-level second-order information, while first-order alternatives lack complete finite-time guarantees. It introduces F2SA and analyzes its convergence across stochastic regimes, with an MNIST data-hypercleaning demonstration.

1 Introduction

  • The method avoids Jacobian and Hessian estimation, addressing a central obstacle in hyper-gradient computation where second-order operations can be costly or prohibitive.Earlier first-order approaches either lack complete finite-time analysis or apply only to deterministic functions.Source: §1 · p. 2

1.1 Overview of Main Results

  • F2SA converts the problem to a constrained single-level form and increases its multiplier λk = O(k^b), balancing bias removal against step-size decay from growing nonsmoothness.The technical contribution characterizes a growth rate that optimizes this trade-off and yields explicit non-asymptotic convergence rates.Source: §1.1 · pp. 2–3
  • F2SA is single-loop: each outer-variable update requires only a constant number of inner-variable updates.This addresses the need to track the lower-level solution without waiting for many inner iterations before updating the outer variable.Source: §1 · p. 2, §1.1 · p. 3
  • F2SA reaches an ϵ-stationary point in ˜O(ϵ^-3.5), ˜O(ϵ^-2.5), or ˜O(ϵ^-1.5) iterations across two-noisy, upper-level-only-noisy, or deterministic regimes, respectively.Momentum or variance reduction improves these to ˜O(ϵ^-2.5), ˜O(ϵ^-2), or ˜O(ϵ^-1.5), respectively.Source: §1.1 · p. 3
  • F2SA can outperform methods using second-order information in MNIST data hyper-cleaning experiments.The paper notes its theoretical guarantees are not better than those of existing second-order methods.Source: §1.1 · p. 3

1.2 Related Work

  • Compared with the closest deterministic first-order work, the paper reports an improved ˜O(k^-2/3) rate versus O(k^-1/4), while targeting guarantees in the true objective F.The cited prior work considers deterministic oracles and does not provide convergence guarantees in terms of F.Source: §1.2 · p. 4

2 Preliminaries

The preliminaries specify a smooth, well-conditioned problem class with a strongly convex lower-level objective. They define the stochastic gradient-oracle assumptions and the paper’s ϵ-stationarity criterion.

Assumptions

  • The analysis assumes smooth objectives and bounded upper-level gradients, with a strongly convex lower-level objective yielding the well-conditioned setting of interest.In particular, g is µg-strongly convex in y.Source: §2 · p. 4
  • The stochastic setting accesses first-order information through unbiased gradient estimators with bounded variances.The paper assumes these conditions for gradients of f and g unless otherwise specified.Source: §2 · pp. 4–5

Optimality criterion

  • An ϵ-stationary point satisfies ∥∇F(x)∥2 ≤ ϵ, and an algorithm achieves one in K iterations when E[∥∇F(xK)∥2] ≤ ϵ.The expectation is over the algorithm’s stochasticity.Source: §2 · p. 5

3 Algorithm

F2SA seeks stationary points of the bilevel objective using only first-order gradients, with a proxy objective whose bias decreases as its multiplier grows. Its step-size design balances that bias against the inner iterates’ ability to track their moving targets, and momentum-assisted estimators provide an extension aimed at improving convergence rates.

3 Algorithm

  • F2SA uses only gradients of f and g to seek a stationary point of the bilevel objective, while keeping the number of inner updates per outer update constant.The method uses stochastic gradients that are independent unbiased estimators.Source: §3 · pp. 5–6

3.1 Step-Size Design Principle

  • The proxy objective’s gradient follows the exact bilevel gradient with bias O(1/λ), while increasing λ reduces bias but forces smaller step sizes.The design balances this bias against the need for y_k to track a moving target; T can be set to 1 with a sufficiently small ξ.Source: §3 · pp. 5–6, Figure 1 · p. 7, §3.1 · p. 8

3.2 Extension: Integrating Momentum

  • F3SA replaces the basic gradient estimators with momentum-assisted estimators to integrate variance reduction into the fully single-loop method.The extension adds momentum-weight parameters η_k.Source: §3.2 · p. 8

4 Main Results

The section establishes non-asymptotic convergence guarantees for two fully first-order algorithms, with rates depending on noise and momentum. It also discusses the trade-off against second-order methods and reports practical behavior.

4.2 Main Result for Algorithm 1

  • Algorithm 1's analysis tracks the error between y_k and y*(x_k), with its scaling by λ_k key to computing the true outer gradient using gradients alone.The analysis also tracks the decrease in the objective and the distance between z_k and y*(x_k).Source: §4.2 · p. 9
  • With stochastic noise only in the upper level rather than both levels, the rate improves from O(k^-2/7) to O(k^-2/5); with no noise, it is O(k^-2/3), versus O(k^-1) obtainable with second-order methods.Source: §4.2 · p. 10

4.3 Main Result for Algorithm 2

  • For Algorithm 2, the analysis requires neither the bounded-x-gradient assumption nor smoothness of the Hessian of f required in Algorithm 1's analysis.The section states that momentum-assisted convergence results hold under weaker assumptions.Source: §4 · p. 8, §4.3 · p. 10
  • With stochastic noise in both levels, momentum lowers sample complexity for achieving an ϵ-stationary point from ˜O_P(ϵ^-7/2) to ˜O_P(ϵ^-5/2); with noise only in the upper-level objective, it lowers it from ˜O_P(ϵ^-5/2) to ˜O_P(ϵ^-2).Source: §4.3 · p. 11

4.4 Discussion

  • Avoiding second derivatives of g comes with slower iteration rates: O(k^-2/7) without momentum and O(k^-2/5) with momentum, compared with cited second-order rates.The comparison rates cited are O(k^-1/2) without momentum and O(k^-2/3) with momentum.Source: §4.4 · p. 11
  • Experiments report no slowdown in convergence, and F2SA can outperform second-order methods; fixing λ trades this for faster convergence to a biased point.The fixed-λ strategy is suggested when an O(1/λ^2) solution bias is not critical to overall performance.Source: §4.4 · p. 12
  • For deterministic settings, polynomial-rate growth of λ_k is sufficient without an adaptive choice, and the reported rate is k^-2/3 versus k^-1/4 in [45].The contrasted dynamic-barrier method in [45] uses a quantity unavailable in stochastic settings.Source: §4.4 · p. 12

5 Experiments

The experiments evaluate F2SA on MNIST data hyper-cleaning and compare it with a second-order method and training without bilevel optimization. F2SA is at least on par with SOBO and can outperform it at small batch sizes.

5 Experiments

  • The experiment uses 19,000 training samples, 1,000 clean validation samples, and regularization parameter c = 0.01.The task assigns training-example weights so a model trained on the weighted data performs well on the clean validation set.Source: §5 · p. 12
  • The comparison includes F2SA, SOBO at batch sizes 50 and 500, stocBiO as a representative second-order method, and training without bilevel optimization.The no-bilevel baseline trains on all samples despite label corruption.Source: §5 · pp. 12–13
  • F2SA is at least on par with SOBO and can outperform it with small batch sizes in the MNIST data hyper-cleaning experiment.The authors report that F2SA is less sensitive to small batch sizes and free of the bias they observed with Neumann approximation.Source: §5 · p. 13

6 Future work

The future-work discussion identifies open questions about first-order methods’ complexity gap and broader lower-level problems. Appendix A introduces notation and auxiliary lemmas used in the proofs.

6 Future work

  • The authors observe a gap between fully first-order methods and methods using second-order information, and conjecture that the gap may be fundamental.Investigating the fundamental limits of fully first-order methods is left as an open question.Source: §6 · p. 13
  • The authors identify non-strongly-convex or non-smooth lower-level problems and variable-dependent constraints as future extensions for fully first-order approaches.They note that formula (1) is available only for well-conditioned lower-level problems.Source: §6 · p. 13

A.1 Additional Notation

  • Appendix A.1 uses qx notation for variable movements and summarizes instance-specific constants and their meanings in Table 1.The movements are described as those expected if gradient oracles have no stochastic noise.Source: §A.1 · p. 17, Table 1 · p. 17

A.2 Auxiliary Lemmas

  • Appendix A introduces auxiliary lemmas for use in the main proofs.The supplied text names Lemmas A.2 through A.6 but does not state their results.Source: §A.2 · pp. 17–18

Appendix B Main Results for Algorithm 1

Appendix B sets up the proof of Theorem 4.1 by bounding changes in a potential function. Its first subsection estimates the change in the objective across an iteration.

Appendix B Main Results for Algorithm 1

  • The proof bounds the change in potential V_k across iterations in terms of I_k and J_k.The passage says the potential can be rewritten using the defined notation; it does not provide the resulting bound in readable form.Source: Appendix B · p. 18

B.1 Estimation of F(xk+1) −F(xk)

  • The B.1 estimate uses objective smoothness and bounds the discrepancy between the regularized gradient and ∇F(x_k) by Cλ/λ_k.The passage says this bound combines with regularity of f and g.Source: §B.1 · pp. 19–20
  • The B.1 derivation concludes using Cauchy–Schwarz and the stated step-size condition.The supplied passages do not state the resulting inequality’s values or full terms.Source: §B.1 · p. 20

B.2 Descent Lemma for yk towards y∗λ,k

Appendix B.2 and B.3 establish descent bounds for the inner variables toward their respective lower-level solutions under step-size conditions.

B.2 Descent Lemma for yk towards y∗λ,k

  • B.2 analyzes descent of y_k toward y*_{λ,k}, using step-size rules and bounds for the inner iterates.The supplied passages state that the inner update is repeated T times and that the relevant lower-level functions are strongly convex in y.Source: §B.2 · pp. 20–21
  • B.2 also bounds terms involving y*_{λ,k} and y*_k, including their relation to the smoothness of y*_λ.The passages identify these as components of the descent bound but do not expose its full expression.Source: §B.2 · pp. 20–21

B.3 Descent Lemma for zk towards y∗k

  • B.3 states bounds for J_k and the distance between z_{k+1} and y*_k, subject to its step-size rules.The supplied excerpts name Lemmas B.4 and B.5 but do not show their complete bounds.Source: §B.3 · p. 22
  • B.3 analyzes one inner-loop step for z_k toward y*_k and repeats the resulting relation T times under a step-size condition.The section states that strong convexity and smoothness of g_k are used in the argument.Source: §B.3 · pp. 22–23

B.4 Proof of Theorem 4.1

The proof of Theorem 4.1 bounds the terms in the potential-function change, then sums those bounds over iterations to obtain the theorem.

B.4 Proof of Theorem 4.1

  • The change in F(xk) is bounded using Proposition B.1 before the terms are rearranged.Source: §B.4 · p. 23
  • The proof estimates terms (i) and (ii) using Lemma B.2 and Lemma B.4, respectively.The estimate for (i) uses λk+1 = λk + δk and the step-size rules.Source: §B.4 · pp. 23–24
  • Summing the per-iteration bounds from k = 0 to K −1 and retaining the dominating terms completes the proof of Theorem 4.1.The argument uses δk/λk = O(1/k) and λk = poly(k).Source: §B.4 · p. 25

B.5 Proof of Corollary 4.2

The proof selects step-size exponents for three stochasticity regimes and develops the momentum-assisted analysis through noise-variance and potential-function bounds.

B.5 Proof of Corollary 4.2

  • The proof treats three regimes: stochasticity in both objectives, stochasticity only in the upper-level objective, and no stochasticity.Source: §B.5 · p. 25
  • With stochasticity in both objectives, the Corollary 4.2 proof chooses a = 5/7, c = 4/7, giving λk = k^1/7.The passage identifies σ²_g · Σ as the dominating term.Source: §B.5 · p. 25

Appendix C Main Results for Algorithm 2

  • Algorithm 2 defines momentum-assisted moving directions for the inner and outer updates, together with stochastic error terms.The outer update uses a choice of ηk.Source: Appendix C · p. 26

C.2 Descent Lemma for Noise Variances

  • The Algorithm 2 analysis tracks decreases in stochastic error terms through dedicated noise-variance lemmas.Source: §C.2 · p. 27

C.6 Decrease in Potential Function

  • The step-size design makes the coefficient of all squared terms negative to suppress noise-variance terms.Source: §C.6 · p. 31
  • For Algorithm 2, summing the potential-function decrease over iterations yields Theorem 4.3.The argument uses δk/λk = O(1/k) and 1/λk, δk/γk = o(1).Source: §C.6 · p. 31

C.7 Proof of Corollary 4.4

The proof of Corollary 4.4 chooses step-size exponents for three stochasticity regimes; the accompanying lemmas bound strong convexity and relate regularized minimizers to the bilevel solution.

C.7 Proof of Corollary 4.4

  • Under stochasticity in both upper-level and lower-level objectives, for g > 0 the parameter choices a = 3/5 and c = 2/5 give λk ≍ k^1/5.Source: §C.7 · p. 32
  • For the regime with σ²_g = 0, the proof sets a = 2/4, c = 1/4, yielding λk ≍ k^1/4.Source: §C.7 · p. 32
  • With no stochasticity, the proof sets a = 1/3 and c = 0.Source: §C.7 · p. 32

D.1.2 Proof of Lemma 3.2

  • When λ > 2lf,1/µg, Lλ(x, ·) is at least λµg/2-strongly convex in y.Source: §D.1.2 · p. 32
  • The proof concludes that y∗(x) is the limit of the regularized minimizer y∗_λ(x) as λ tends to infinity.Source: §D.1.2 · p. 33

D.2.1 Proof of Lemma A.1

These appendix proofs establish regularity and error bounds used in the convergence analysis, including bounds involving the solution maps and stochastic gradient estimates.

D.2.1 Proof of Lemma A.1

  • The proof of Lemma A.1 uses function smoothness and Hessian continuity assumptions to obtain a bound for x1 and x2 in X.Source: §D.2.1 · p. 33

D.2.3 Proof of Lemma A.3

  • For λ > 2lf,1/µg, the matrix in the proof is positive definite with minimum eigenvalue greater than λµg/2.Source: §D.2.3 · p. 35

D.2.5 Proof of Lemma A.5

  • The proof notes that smoothness of y∗(x) is crucial for controlling noise variance induced by updating x.Source: §D.2.5 · p. 35
  • The proof obtains the desired Lemma A.5 result using Lipschitz continuity and smoothness of y∗(x).Source: §D.2.5 · p. 36

D.3.3 Proof of Lemma C.3

  • The proof defines qy_k(ζ, φ) as ∇yf(xk, yk; ζ) + λk∇yg(xk, yk; φ).Source: §D.3.3 · p. 38

D.3.4 Proof of Lemma C.4

  • The proof defines qx_k(ζ, φ) using gradients at yk+1 and zk+1, including their difference in ∇xg.Source: §D.3.4 · p. 38
Loading 2301.10945v1…