PaperlayerView exact revision on arXiv

Source-linked AI summary

SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization

Zhihao Gu, Qilong Wu, Junchi Yang

arXiv:2608.23211v1math.OCcs.LG

TL;DR

The paper asks whether fully first-order NC–SC bilevel optimization can achieve favorable ϵ-dependence without double-loop procedures. It introduces single-loop SGHA and Stoc-SGHA using a constrained, regularized Lagrangian and Smoothed GDA with finite-difference Hessian–vector approximations. The resulting methods achieve optimal deterministic ϵ-dependence and match the best-known stochastic ϵ-dependence, while condition-number dependence remains an open issue.

  • Problem

    Existing fully first-order methods with the best-known complexity guarantees typically rely on double-loop penalty procedures, motivating a single-loop alternative.

  • Method

    The paper reformulates lower-level stationarity as an equality constraint, builds a bounded-dual regularized Lagrangian, and applies Smoothed GDA with finite-difference Hessian–vector approximations.

  • Results

    SGHA achieves optimal ϵ-dependence in the deterministic setting, while Stoc-SGHA matches the best-known ϵ-dependence of existing nested-loop methods in the stochastic setting.

  • Takeaways & Limitations

    The approach establishes single-loop, fully first-order algorithms with favorable ϵ-dependence for deterministic and stochastic NC–SC bilevel optimization.

  • Takeaways & Limitations

    The dependence on κ_y and ¯κ_y remains worse than existing lower bounds and double-loop penalty methods, and optimal stochastic ϵ-dependence under the standard bounded-variance oracle remains unknown.

Abstract

from arXiv · show

In this work, we study the oracle complexity of finding an $ε$-stationary point for nonconvex-strongly-convex (NC-SC) bilevel optimization using only first-order oracles. Existing methods achieving the best-known complexity guarantees typically rely on double-loop, penalty-based procedures. We propose a novel single-loop algorithm based on a constrained reformulation in which lower-level stationarity is imposed as a constraint. Specifically, we construct a regularized Lagrangian by introducing a quadratic regularizer and restricting the dual variable to a bounded domain, and then apply Smoothed Gradient Descent Ascent [Zhang et al., 2020], with Hessian-vector products approximated via finite differences of gradients. We refer to the resulting deterministic and stochastic algorithms as SGHA and Stoc-SGHA, respectively. In the deterministic setting, SGHA achieves an oracle complexity of $O(\barκ_y^{5}ε^{-2})$, where $\barκ_y$ denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}ρ^{-3}\right)$ with probability at least $1-ρ$ for any $ρ\in(0,1)$, and an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}\right)$ in expectation under an additional bounded-iterate assumption. Moreover, under an additional stochastic smoothness assumption imposed only on the lower-level objective, the stochastic oracle complexity of Stoc-SGHA improves to $O\left(\barκ_y^{11}ε^{-4}ρ^{-2}\right)$ with high probability and $O\left(\barκ_y^{11}ε^{-4}\right)$ in expectation, matching the $ε$-dependence of the lower bounds.

1 Introduction

The paper targets fully first-order NC–SC bilevel optimization, where leading complexity guarantees typically depend on double-loop penalty procedures. It proposes single-loop SGHA and Stoc-SGHA through a regularized constrained Lagrangian reformulation and reports complexity guarantees for deterministic and stochastic settings.

  • Motivation: Bilevel optimization models hierarchical decision-making with nested upper- and lower-level problems.In the NC–SC setting, the lower-level objective is strongly convex in y, while the upper-level objective may be nonconvex; the lower-level solution is therefore unique.
  • Limitations of existing methods: Existing fully first-order approaches commonly use penalty formulations and double-loop procedures to approximate lower-level solutions and auxiliary subproblems.These procedures rely on inner iterates remaining close to exact minimizers, enabling favorable outer updates.
  • Limitations of existing methods: Directly removing inner loops worsens guarantees because tracking errors evolve with the upper-level variable and large penalty parameters deteriorate conditioning.The penalty-based value function can have smoothness independent of the penalty parameter, but single-loop methods that fail to exploit this property typically lose favorable dependence on ϵ.
  • Proposed approach: The paper proposes SGHA and Stoc-SGHA, single-loop algorithms based on Smoothed GDA, a regularized Lagrangian, and finite-difference approximations of Hessian–vector products.The constrained reformulation imposes lower-level stationarity; bounded dual variables and a concave quadratic regularizer make the minimax surrogate finite-valued, strongly concave in the multiplier, and better conditioned.
  • Results: SGHA and Stoc-SGHA provide deterministic and stochastic oracle-complexity guarantees for finding ϵ-stationary points in NC–SC bilevel optimization.The paper states that the stochastic bounds can match lower-bound dependence on ϵ under an additional stochastic smoothness condition on the lower-level objective, while expectation results require bounded iterates.

2 Related Work

Related work develops Hessian-based and fully first-order approaches for NC–SC bilevel optimization, while the strongest fully first-order guarantees largely rely on double-loop penalty methods.

  • Bilevel Optimization with Hessian: Hypergradient methods estimate lower-level sensitivity, often through Hessian or inverse-Hessian computations.Iterative differentiation differentiates through finite lower-level trajectories, while approximate implicit differentiation solves an associated linear system.
  • Fully First-order Bilevel Optimization: Fully first-order methods avoid explicit Hessian information but have mostly used double-loop penalty formulations.These methods incorporate lower-level optimality into a penalized upper-level objective.
  • Minimax Optimization: Existing single-loop algorithms generally have worse complexity than the best-known double-loop rates.FdeHBO uses finite-difference Hessian–vector products but requires variance reduction and stronger assumptions.
  • Minimax Optimization: Generic NC–C minimax results do not directly apply to this setting, while the bilevel structure yields sharper complexity guarantees.Smoothed GDA has O(ϵ^-4) complexity for general NC–C problems and requires additional conditions for O(ϵ^-2).

3 Preliminaries and Technical Background

The paper formulates smooth NC–SC bilevel optimization through the lower-level optimality constraint, yielding an equivalent equality-constrained problem and a Lagrangian stationarity framework.

  • Assumptions and Notation: The NC–SC setting assumes a nonconvex upper-level objective and a lower-level objective strongly convex in y.Strong convexity makes y⋆(x) unique and the hyperobjective smooth.
  • Assumptions and Notation: The paper assumes smooth objectives, Lipschitz Hessians, and a finite lower bound on f.These assumptions define the smooth NC–SC problem class analyzed throughout.
  • Assumptions and Notation: The global condition number is defined as ¯κ_y := ¯L/µ_g, and ε-stationarity means ∥∇φ(x)∥≤ε.The condition-number notation and stationarity measure are used in the complexity results.
  • Equality-constrained Reformulation: The lower-level first-order condition ∇_y g(x,y⋆(x))=0 exactly characterizes the feasible graph of y⋆(x).The reformulation preserves the original objective values and minimizers.
  • Equality-constrained Reformulation: The equality-constrained problem uses L(x,y,λ) := f(x,y) + λ^T∇_y g(x,y).Lower-level strong convexity ensures LICQ and supports the associated stationarity system.
  • Equality-constrained Reformulation: Stationarity of the Lagrangian can be reduced to stationarity of the hyperobjective, while KKT multipliers are bounded by problem-dependent constants.This boundedness motivates the constrained Lagrangian approach rather than penalizing the lower-level value gap.

4 Deterministic NC–SC Bilevel Optimization

SGHA applies Smoothed GDA to a regularized, bounded-dual Lagrangian surrogate and replaces Hessian–vector products with finite differences, achieving a deterministic single-loop complexity guarantee.

  • Algorithm: SGHA is designed for deterministic NC–SC bilevel optimization using a single loop and fully first-order oracles.The algorithm uses common primal stepsizes, a separate dual stepsize, and averaged auxiliary primal variables.
  • Regularized Surrogate: The dual variable is restricted to a sufficiently large bounded domain because unconstrained multiplier maximization can be unbounded.The bounded domain contains all KKT multipliers and provides uniform smoothness control along the trajectory.
  • Regularized Surrogate: A quadratic dual regularizer and proximal primal terms make the surrogate strongly concave in λ and strongly convex in w=(x,y).These modifications produce a well-conditioned minimax problem for Smoothed GDA.
  • Hessian Approximation: Hessian–vector products involving ∇²_yyg(x,y)λ are approximated by central finite differences of first-order gradients.The finite-difference radius τ controls this approximation.
  • Analysis: The convergence analysis uses a lower-bounded Lyapunov function and a one-step descent inequality controlling stationarity and tracking residuals.Residual control is translated into Lagrangian stationarity and then hypergradient convergence.

5 Stochastic NC–SC Bilevel Optimization

Stoc-SGHA extends SGHA to stochastic NC–SC bilevel optimization by replacing exact gradients with mini-batch estimators while retaining a single-loop structure. Its guarantees include high-probability and expectation complexity bounds, with remaining gaps in stochastic dependence and condition-number dependence.

  • Stoc-SGHA preserves SGHA’s single-loop structure while replacing exact gradients with mini-batch stochastic estimators.Gradients of f and finite-difference Hessian-vector products of g are estimated using mini-batches.
  • The stochastic finite-difference approximation uses coupled samples for both gradient evaluations in each central difference.This coupling is essential for the sharper variance bound under the additional stochastic smoothness assumption.
  • The resulting ε-dependence matches the best-known fully first-order stochastic upper bound while removing its logarithmic factor.The paper identifies this as the first single-loop fully first-order method to attain the same ε^-6 dependence.
  • An additional ε^-2 gap and a substantial condition-number gap remain relative to stochastic lower bounds.Closing the gap between the best-known upper and lower bounds remains open.

6 Improved Complexities with Lower-Level Stochastic Smoothness

Imposing stochastic smoothness only on the lower-level objective improves Stoc-SGHA’s stochastic complexity. The resulting ε^-4 dependence matches the lower-bound dependence, although the condition-number dependence remains suboptimal.

  • Lower-level stochastic smoothness controls mean-square variation of stochastic gradients across points and improves Stoc-SGHA’s stochastic complexity.The condition is stronger than the standard bounded-variance oracle model.
  • Using the same sample in each central difference yields sharper variance control for the stochastic Hessian-vector approximation.Under the bounded-variance model, the finite-difference error contains a variance term amplified by the finite-difference radius; coupled sampling removes that amplification.
  • The ε^-4 dependence matches the rate for smooth nonconvex single-level optimization and the lower-bound dependence under the stochastic smoothness assumption.The paper notes that this rate was previously achieved only when the lower-level gradient is noise-free.
  • The ¯κ_y-dependence remains worse than the lower bound, leaving a condition-number gap for single-loop fully first-order methods.Closing this gap remains an open problem.

7 Numerical Experiments

The experiments evaluate SGHA on learn-to-regularize logistic regression and data hyper-cleaning, using common tuning and comparison protocols. SGHA achieves the strongest reported performance in both tasks, including lower test loss, higher test accuracy, and smaller weights on corrupted examples.

  • Experimental setup: SGHA and competing methods are evaluated in learn-to-regularize logistic regression and data hyper-cleaning experiments under a common protocol.Method-specific stepsizes and parameters are tuned, and the best stable performance is reported.
  • Learn-to-Regularize Logistic Regression: The 20 Newsgroups experiment uses 20 classes, 101,631 TF-IDF features, and separate training, validation, and by-date test sets.The experiment compares SGHA with penalty-based and HVP-based bilevel methods.
  • Learn-to-Regularize Logistic Regression: SGHA consistently achieves the best test loss and test accuracy, while F2BSA is the strongest baseline.The comparison includes performance without hyperparameter tuning as a dashed reference.
  • Data Hyper-Cleaning on MNIST: The MNIST hyper-cleaning experiment uses corruption ratios p ∈ {0.5, 0.9, 0.99} and measures average weights assigned to corrupted training examples.Lower weights indicate better suppression of corrupted examples.
  • Data Hyper-Cleaning on MNIST: SGHA assigns substantially smaller weights to corrupted examples across all corruption ratios, with a larger advantage as corruption increases.F2BSA is the strongest baseline but assigns noticeably larger corrupted-example weights than SGHA.

8 Conclusions and Future Directions

The paper concludes that SGHA and Stoc-SGHA provide single-loop, fully first-order algorithms with strong ε-dependence guarantees for NC–SC bilevel optimization. Future work concerns condition-number dependence, stochastic lower bounds, and extension beyond strongly convex lower-level problems.

  • Conclusions: SGHA and Stoc-SGHA use a constrained lower-level stationarity reformulation, a regularized minimax surrogate, Smoothed GDA, and finite-difference gradient approximations.The analysis is tailored to this structure to obtain the stated complexity guarantees.
  • Future Directions: The dependence on κy and ¯κy remains worse than existing lower bounds and double-loop penalty methods.Improving condition-number dependence while retaining the single-loop, fully first-order structure is identified as an open direction.
  • Future Directions: The optimal stochastic ε-dependence under the standard bounded-variance oracle remains unknown because existing lower bounds use restricted problem structures.The paper conjectures a lower bound of Ω(poly(κy)ε^-6) without those special structures.
  • Future Directions: Extending the SGHA framework beyond strongly convex lower-level problems remains an open question.

B.5 Oracle Complexity under Deterministic Setting

The deterministic analysis establishes that SGHA reaches an ε-stationary point through descent of a Lyapunov function and translation of primal–dual residuals to bilevel stationarity. The proof uses strong convexity, bounded dual variables, and explicit parameter choices.

  • Deterministic analysis: The regularized Lagrangian is strongly convex in the primal variable and strongly concave in the bounded dual variable under the stated parameter conditions.These properties support the descent and stability arguments.
  • Deterministic analysis: The Lyapunov function decreases by terms controlling primal and dual update residuals.The descent inequality is then summed over iterations to obtain an iterate with small residuals.
  • Deterministic analysis: The residual bounds are transferred to stationarity of the bilevel hyper-objective, yielding an ε-stationary point.The proof uses the relation between the regularized problem and the bilevel hyper-objective.
  • Stochastic extension: The stochastic analysis replaces deterministic finite differences and gradients with mini-batch estimators and controls their bias and variance.The stochastic oracle construction uses separate mini-batches for the upper- and lower-level quantities.

C.5 Oracle Complexity of Stoc-SGHA in High Probability

The high-probability analysis of Stoc-SGHA selects accuracy, smoothing, batch-size, and iteration parameters to control stochastic errors. It then converts residual bounds into an oracle-complexity guarantee with probability at least 1 − ρ.

  • Parameter selection: The high-probability proof sets εL proportional to ε√ρ and specifies the smoothing parameter τ using ¯κy and the smoothness bound.These choices enable the deterministic conditions to be applied pathwise.
  • High-probability guarantee: The selected iteration count and batch size yield a high-probability residual bound for a returned iterate.With probability at least 1 − ρ, the primal, dual, and tracking residuals are simultaneously controlled.
  • High-probability guarantee: The residual guarantee is converted through the stationarity relation into an ε-stationary point of the bilevel objective.
  • Complexity: The resulting total oracle complexity is the bound stated for Stoc-SGHA in the high-probability setting.The final complexity follows after substituting the selected parameters into the iteration and batch-size requirements.

C.6 Oracle Complexity of Stoc-SGHA in Expectation

The section establishes bounded-gradient properties for the regularized Lagrangian and develops finite-difference estimates used in the stochastic analysis. It then combines these estimates to obtain a finite stochastic first-order oracle complexity.

  • The constants Gf(Dw), Gg(Dw), and GJ(Dw) are finite because the relevant mappings are continuous on a compact set.
  • The bounded Lagrangian uses a dual domain Λ with radius Cλ exceeding lf,0/µg.
  • The primal and multiplier gradients are bounded by constants Gw and Gλ on bounded iterates.
  • The analysis combines primal and multiplier estimates to bound their contribution by 3Gwϵ2 and concludes with a finite total oracle complexity.
  • Central finite differences use the same sample at perturbed points, separating deterministic bias from centered sampling variance.

D.4 Oracle Complexity under Stochastic Setting with Stochastic Smoothness of g

Under stochastic smoothness assumptions, the analysis selects averaging, batch-size, and iteration parameters for Algorithm 2 and guarantees an iterate satisfying the stated stationarity conditions.

  • The proof derives the guarantee through Proposition 39 and combines its estimates with the chosen batch-size parameter.
  • The theorem specifies an averaging parameter, positive batch size, and iteration count for Algorithm 2.
  • The same conclusion holds when τ2 is no larger and B and K are no smaller than their displayed values.
  • There exists an index k in {0, . . . , K −1} satisfying the theorem’s stated stationarity guarantee.

D.5 Oracle Complexity of Stoc-SGHA in High Probability with Stochastic Smoothness of g

The high-probability analysis chooses accuracy, stepsize, averaging, batch-size, and iteration parameters for Stoc-SGHA under stochastic smoothness of g. It then establishes simultaneous iterate bounds on an event with probability at least 1 −ρ.

  • The accuracy parameter ϵL scales with ϵ√ρ, while L0 is set to 8¯L¯κy.
  • The parameter verification uses pw = 2L0, γ1 = 2, and γ2 ≤ 1/(8¯κy).
  • The batch size is required to satisfy B ≥ 226¯Mg¯L2ϵ−2.
  • There exists an index k⋆ in {0, . . . , K −1} satisfying the analyzed stationarity condition.
  • With probability at least 1 −ρ, three iterate-distance bounds hold simultaneously for wk⋆, λk⋆, and the auxiliary points.
  • The proof applies the deterministic bridge pathwise and then invokes the hypergradient conclusion to complete the high-probability guarantee.
Loading 2608.23211v1…