Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption

1 Introduction

• In the simple formulation, the upper-level objective f is independent of the lower-level variable y, while g is independent of the upper-level variable x.The lower-level function g is a primary requirement, and f selects among lower-level solutions.Source: §1 · p. 1
• The lower-level solution set may be nonconvex or disconnected, so classical convex bilevel techniques do not directly transfer.The lower-level constraint is global, even in the deterministic setting.Source: §1 · p. 1
• Stochastic gradient substitution can make DBGD's adaptive multiplier singular when the lower-level gradient estimator vanishes away from stationary points.DBGD combines upper- and lower-level descent through an adaptive dual multiplier.Source: §1 · p. 1
• Denominator-only perturbation yields faster convergence under standard, verifiable assumptions than approaches that require rare visits or use penalty regularization.The cited comparison is summarized in Table 1 by iteration count, upper- and lower-level oracle calls, and required assumptions.Source: §1 · p. 2, Table 1 · p. 2
• O(ε^-2) iterations, O(ε^-4) upper-level oracle calls, and O(ε^-7) lower-level oracle calls suffice for (ε, ε)-stationarity without a rare-visit assumption.The method also provides anytime convergence rates that do not require knowing the final horizon.Source: §1 · p. 2

2 Problem Setup and Stationarity

• The objectives f and g are expectations of stochastic realizations defined over a real Hilbert space.The setup assumes the expectations are well-defined and differentiable, with gradients equal to the corresponding expected stochastic gradients.Source: §2 · p. 2
• The assumptions include smooth objectives, a uniformly bounded upper-level gradient, and uniformly bounded variance of stochastic gradients.The authors retain bounded variance to simplify results and isolate difficulties arising from stochasticity.Source: §2 · p. 2
• The assumptions do not require a uniformly bounded lower-level gradient or smooth individual stochastic realizations.This differs from the cited work [1], which requires bounded ∇g and uses realization smoothness for its variance-reduced variant.Source: §2 · p. 3
• Stationarity is measured using squared gradient norms, and an (εf, εg)-stationary point requires both lower-level near-stationarity and upper/lower-level first-order compatibility.The compatibility condition rules out a first-order direction that substantially decreases f without increasing g.Source: §2 · p. 3
• Because g may be nonconvex, lower-level stationarity does not generally imply proximity to argmin g.The definition is a first-order approximation for solving the bilevel problem, not a guarantee of lower-level global optimality.Source: §2 · p. 3

3 Stochastic Dynamic Barrier Gradient Descent

• Adding ρ_k to the stochastic multiplier’s denominator prevents singularities when the estimated lower-level gradient is small or zero.As ρ_k → 0, the definition recovers the deterministic multiplier.Source: §3 · p. 3
• Unlike the multiplier in [1], SDBGD regularizes the denominator without adding a corresponding ρ_kβ_k term to the numerator.The authors state that the similar-looking definitions lead to different convergence properties and require distinct arguments.Source: §3 · p. 3
• The reported iterate x_NK is sampled with probability proportional to η_kβ_k, and the analysis provides horizon-dependent and anytime rates.The rates’ proportionality constants are independent of K or k.Source: §3 · p. 4
• For horizon K ≥ 1, choose a ∈ (0, 1/3), with η ∝ K⁻ᵃ ∈ (0, (2Lf + 4Lg)⁻¹), β ∝ η⁻³K⁻¹ ∈ (0, 1), ρ ∝ η⁻²K⁻², Bf ∝ η⁴K², and Bg ∝ η⁶K⁴.Source: §3 · p. 4
• The balanced choice a = 1/4 gives O(K^-1/2) or ˜O(K^-1/2) rates for both stationary residuals.The parameter a ∈ (0, 1/3) controls the tradeoff between the residuals.Source: §3 · p. 4
• O(ε^-2) iterations reach (ε, ε)-stationarity, using O(ε^-4) upper-level and O(ε^-7) lower-level stochastic oracle calls.These complexities use the balanced choice a = 1/4.Source: §3 · pp. 4–5

4 Numerical Illustration

• The experiment compares SDBGD with SDBPG, PR-SDBPG, and VR-PR-SDBPG [1] under a shared oracle budget B = 108.All methods use anytime schedules and stochastic gradients with Gaussian noise.Source: §4 · p. 5
• SDBGD does not empirically improve on the previously proposed methods, despite stronger theoretical guarantees that require no unverifiable assumption.Figure 1 compares upper- and lower-level stationarity measures in terms of stochastic oracle calls.Source: §4 · p. 5, Figure 1 · p. 5
• Figure 1 plots upper- and lower-level stationarity measures against stochastic oracle calls for all four methods.Source: §4 · p. 5, Figure 1 · p. 5

5 Conclusion

• SDBGD achieves O(ε^-2) iterations with O(ε^-4) upper-level and O(ε^-7) lower-level stochastic oracle calls, without the rare-visit assumption, improving upon assumption-free guarantees in [1].The paper also provides an anytime parameter schedule that does not require knowledge of the final horizon.Source: §5 · p. 5
• The paper reports a simple numerical illustration alongside its theoretical results.Source: §5 · p. 5
• The appropriate stochastic analogue of deterministic multiplier-based bilevel methods remains an open question.The authors suggest considering a stochastic projected dynamical system to derive the stochastic multiplier.Source: §5 · p. 5

A Proofs

• The appendix takes the iterates generated by Algorithm 1 as its sequence and assumes Assumptions 2.1 and 2.2.Source: A Proofs · p. 7
• It defines F_k from the initial point and past oracle samples, making x_k measurable with respect to F_k.Source: A Proofs · p. 7
• The proof uses E_k for conditional expectation given F_k and E for total expectation.Source: A Proofs · p. 7

A.1 Preliminary Results

• The quadratic bound converts x ≤ C + D√x, for nonnegative x and D, into x ≤ 2C + D².Source: §A.1 · p. 7
• When β∥b∥² − ⟨a,b⟩ ≤ 0, the multiplier is zero and the resulting direction is d = a.Source: §A.1 · p. 7
• The preliminary stability result bounds changes in the multiplier map and relates the exact direction to the direction formed from stochastic gradient estimates.The proof applies the bounds to d_k and its stochastic counterpart.Source: §A.1 · pp. 8–9
• For fixed b, the map ϕ_b is the identity on the inactive half-space and has operator-norm derivative at most one in the stated regions.Source: §A.1 · p. 8

A.2 Descent Analysis and Energy Bound

• Combining the descent bounds yields a weighted stationarity bound, from which the convergence rates follow.The residual-bound theorem states conditions on the step sizes and barrier parameters and uses a randomly sampled iterate.Source: §A.2 · pp. 9–11
• The upper-level descent lemma is established using smoothness of f and a preceding bound.Source: §A.2 · pp. 9–10
• The lower-level descent lemma follows by smoothness of g, paralleling the upper-level argument.Source: §A.2 · p. 10

A.3.1 Horizon-Dependent Parameters

• For the horizon-dependent setting, τ ∝ βη, ρ ∝ β^2η^4, and β ∝ η^-3K^-1.The parameters are constant across iterations in this setting.Source: §A.3.1 · p. 12
• Choosing η ∝ K^-a for a ∈ (0, 1/3) yields the stated result.Under the chosen parameters, the remaining terms are O(η^2) or lower.Source: §A.3.1 · p. 13

A.3.2 Anytime Parameters

• The anytime parameter choice is derived from the finite-horizon parameter selection.The analysis expands the resulting terms into powers of k + 1.Source: §A.3.2 · p. 13
• In the anytime analysis, βk/ηk ∝ (k + 1)^(4a−1) is nonincreasing when a ≤ 1/4 and nondecreasing when a ≥ 1/4.These conditions identify the two cases used in applying Theorem A.7.Source: §A.3.2 · p. 13

• The toy problem is specified so that the solution to (P) is (2π, 0), with Lf = 1, Lg = 1, and Gf = 1.Source: B Experimental Setup · p. 14
• The stochastic gradients use Gaussian noise with σf = σg = 0.5, satisfying the uniformly bounded variance assumption.Source: B Experimental Setup · p. 14
• SDBGD, SDBPG, PR-SDBPG, and VR-PR-SDBPG start at x0 = (1.5, 1.5) with stochastic-oracle budget B = 108.SDBGD uses the anytime schedule with a = 1/4; the schedules for the methods in Ahmadi et al. [1] replace horizon K with k + 1.Source: B Experimental Setup · p. 14
• Table 2 gives the compared methods’ parameter choices; schedule powers follow theory, while proportionality constants are manually chosen and held fixed across runs.Source: Table 2 · p. 14, B Experimental Setup · p. 14
• SDBGD, SDBPG, and PR-SDBPG use Bf,k + Bg,k oracle calls per iteration, while VR-PR-SDBPG uses twice that amount.An iteration runs only when its full oracle cost fits the remaining budget.Source: B Experimental Setup · p. 14
• Across 10 independent runs, the experiment plots empirical means of the upper-level and lower-level stationarity measures; full gradients are used only for evaluation.The plotted measures are ∥dk∥2 and ∥∇g(xk)∥2.Source: B Experimental Setup · p. 14