Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization

AI summary

Overview

• Research area: Online bilevel optimization (OBO), a branch of machine learning optimization theory that studies nested (leader/follower) problems whose objectives change over time.
• Technical level: Advanced. The paper is theoretical, built on implicit function theorem derivations, projection-based local regret, path-length/regularity measures, and convergence proofs; it also includes a zeroth-order (gradient-free) extension.
• Scope in one sentence: The paper introduces a new search direction plus first-order and zeroth-order stochastic OBO algorithms that achieve sublinear stochastic bilevel regret without window smoothing, using only one inner-subproblem solver iteration per round and, in the zeroth-order case, only function-value feedback.

Note: the supplied paper content is truncated in the middle of Section 3, so the exact zeroth-order estimator construction and the full experimental section are not available in the text provided here; where results are not reported in the available content, this summary says so.

What This Paper Is About

Online bilevel optimization asks an algorithm to repeatedly pick a leader decision (such as hyperparameters) while an inner "follower" problem is solved anew each round, and the underlying objectives can shift over time. Prior OBO methods measure performance using window-smoothed regret, which averages recent objectives over a window of size w, and they need w = o(T) for sublinear regret—an assumption that misrepresents behavior when objectives change rapidly. This paper instead defines a projection-based local regret with no smoothing (w = 1) and proves that both first-order and zeroth-order stochastic methods attain sublinear regret under this harder, unsmoothed measure.

Key Contributions

1. Stochastic regret minimization without window smoothing. The authors introduce a novel search direction (Section 2) and prove that both first-order and zeroth-order methods achieve sublinear stochastic bilevel regret with no window smoothing (w = 1), established in Theorems 2.6 and 3.2 and summarized in Table 1. A key element is Lemma 2.1, which shows that for a particular choice of w = t, W = 1/η and ν = 1−η, the window-smoothed gradient reduces to a recursive momentum-type direction.
2. OBO with function-value oracle feedback. Algorithm 2 estimates Hessians, Jacobians, and gradients using only function value oracles, achieving sublinear local regret (Theorem 3.2). This targets large-scale and black-box settings where first- and second-order information is unavailable or costly, in contrast to existing methods that assume gradient, Hessian and Jacobian oracles.
3. OBO with a single subproblem solver iteration. Where SOBOW uses a conjugate gradient algorithm with an increasing number of iterations, Algorithms 1 and 2 require only a single subproblem solver iteration, updating the inner and outer variables together with the linear-system solution.
4. Oracle reduction and joint updating. The framework reduces oracle dependence in hypergradient estimation and updates inner variables, outer variables, and the linear system solution simultaneously, and it can estimate Hessians, Jacobians and gradients via zeroth-order information.

Main Findings

• Uns smoothed regret bound (first-order, SOGD): Theorem 2.6 states that Algorithm 1, with stepsizes α_t = 1/(c+t)^{1/3}, β_t = c_β α_t, δ_t = c_δ α_t, batch sizes b = b̄ = 1, and momentum parameters γ_{t+1} = c_γ α_t², η_{t+1} = c_η α_t², λ_{t+1} = c_λ α_t², guarantees BL-Reg_T ≤ O(T^{1/3}(σ² + Δ_T) + T^{2/3} Ψ_T).
• Sublinearity conditions: Remark 2.7 shows the average dynamic regret satisfies BL-Reg_T/T ≤ O(T^{−2/3}(σ² + Δ_T) + T^{−1/3} Ψ_T), which is sublinear when Δ_T = o(T^{2/3}), Ψ_T = o(T^{1/3}), and σ = o(T^{1/3}), giving BL-Reg_T = o(T).
• Improved stochastic rate: The T^{−2/3}σ² regret improves over the T^{−1/2}σ² bound reported for stochastic OBO by Bohne et al. (2024), and for online single-level optimization (OSO) it surpasses the T^{−1/2}σ² rate in Hallak et al. (2021).
• Zeroth-order bound (ZO-SOGD): Table 1 lists the ZO-SOGD regret as (d1 + d2)^{3/4} T^{1/3}(σ̂² + Δ̂_T) + (d1 + d2)^{3/2} T^{2/3} Ψ̂_T, with sublinear local regret established in Theorem 3.2.
• Comparison to prior OBO methods: Table 1 contrasts the new methods with OAGD (Tarzanagh et al., 2024), SOBOW (Lin et al., 2024), and SOBBO (Bohne et al., 2024). OAGD is listed as using an exact solver (N.A.) with no stochastic regret and no constrained regret; SOBOW uses O(κ_g log κ_g) solver iterations; SOBBO supports stochastic and constrained regret. All three rely on window size w = o(T), whereas SOGD and ZO-SOGD use w = 1, and ZO-SOGD is the only listed method marked as using only function feedback.
• New regret notion: The paper defines bilevel local regret (BL-Reg_T) as the sum over rounds of the squared norm of a projection-based gradient mapping P_{X,α_t}(x_t; ∇f_t(x_t, y*_t(x_t))), comparing the leader decision to stationary points of the leader's objective rather than to a smoothed objective sequence.
• Regularity measures: Because sublinear dynamic regret is generally infeasible under arbitrary time variation, the analysis controls regret via follower path length H_{p,T}, leader function variation V_T, sequential gradient differences D_{x,T} and D_{y,T} of the outer objective, and inner gradient/Hessian/Jacobian deviations G_{y,T}, G_{yy,T}, G_{xy,T}, combined into Δ_T = E_1 + V_T and Ψ_T = H_{2,T} + G_T + D_T.
• Validation tasks: The abstract states the approach is validated on online parametric loss tuning and black-box adversarial attacks. Specific datasets, benchmark numbers, or empirical tables are not reported in the available content.
• Motivating observation: Figure 1 illustrates smoothly versus rapidly changing f_t in OBO, using g_t(x_t, y_t) = (y_t − cos(x_t))², with a_t = 1 + 0.5 sin(t), b_t = 1 + sin(0.5t), and c_t = 10 b_t, to argue that smoothing can misrepresent regret behavior.
• Theoretical assumptions: The analysis assumes g_t is twice continuously differentiable and μ_g-strongly convex in y; smoothness of f_t and g_t up to second order (constants ℓ_{f,0}, ℓ_{f,1}, ℓ_{g,1}, ℓ_{g,2}); bounded outer objective |f_t| ≤ M; and unbiased stochastic gradient/Hessian/Jacobian estimators with bounded variances combined into σ² = σ²_{gy} + σ²_{gyy} + σ²_{fy} + σ²_{gxy} + σ²_{fx}.

Methodology in Plain English

The paper starts from the standard way of writing the gradient of the outer ("leader") objective using the implicit function theorem: it requires solving a linear system involving the inner Hessian, and it introduces an auxiliary variable v that decouples the nested structure. Instead of solving that linear system accurately with many solver iterations, the authors fold it into a single update loop, so the inner variable, the auxiliary variable, and the outer variable all move at once—an approach they call Simultaneous Online Gradient Descent (SOGD). The heart of the method is a new search direction that combines the current noisy gradient, a momentum term from the previous step, and a correction that compares the current gradient estimate at the current and previous iterates; this mimics a time-smoothed gradient but, by the authors' Lemma 2.1, admits a recursive form that avoids an explicit large window. The authors give the algorithm a projection step for the auxiliary variable onto a ball of radius p, then prove a regret bound under smoothness, strong convexity, and bounded-variance assumptions. For the black-box case they replace true gradients with zeroth-order estimates built from randomly sampled directions on unit balls and Gaussian smoothing of the objectives, and then analyze the same style of algorithm under the smoothed objectives. The theoretical validation comes from comparing the derived regret expressions against those of OAGD, SOBOW, and SOBBO.

Why This Matters

• Research impact: The work removes window smoothing from stochastic OBO regret analysis, sharpening the stochastic term from T^{−1/2}σ² to T^{−2/3}σ², tightening the analysis relative to prior stochastic OBO and OSO bounds, and reducing the number of inner solver iterations to one. It also extends OBO guarantees to settings where only function values are observable.
• Real-world applications:
  • Hyperparameter optimization where the best hyperparameters drift over time (online hyperparameter optimization).
  • Online meta-learning, where tasks arrive sequentially and the meta-model must adapt without knowing future tasks.
  • Online actor-critic reinforcement learning, framed as a leader/follower dynamic between policy and value updates.
  • Black-box adversarial attacks, where gradient information about the target model is unavailable.
  • Neural architecture search, where the architecture search problem is naturally bilevel.
• Industry relevance: Reducing reliance on gradient, Hessian, and Jacobian oracles matters for large-scale and proprietary systems where only queries to a function (such as a deployed model's loss) are permitted. Using a single subproblem solver iteration per round lowers per-step computation, which is attractive for streaming or nonstationary production pipelines.

Future Directions

• Empirical scope: The available content mentions experiments only on online parametric loss tuning and black-box adversarial attacks; broader benchmarking against the OAGD, SOBOW, and SOBBO baselines on standard machine learning tasks is a natural extension.
• Relaxing the assumptions: The regret bounds rely on μ_g-strong convexity of the inner objective and smoothness up to second order, so extending the guarantees to non-strongly-convex or nonsmooth inner problems remains open.
• Tuning and adaptivity: The bound depends on the constants c, c_β, c_δ, c_γ, c_η, c_λ specified in equation (107), and on choosing stepsizes from knowledge of the time horizon T; parameter-free or adaptive variants would be a useful next step.
• Zeroth-order efficiency: The ZO-SOGD bound carries dimension factors (d1 + d2)^{3/4} and (d1 + d2)^{3/2}, so reducing the dimension dependence of zeroth-order OBO is an open question. Details of the ZO gradient estimator construction (following Shamir, 2017) are cut off in the available content.

Target Audience

This paper is best suited for optimization and machine learning theory researchers working on bilevel optimization, online learning, and nonconvex stochastic optimization, as well as graduate students comfortable with the implicit function theorem, local dynamic regret, and convergence-rate proofs. Practitioners in hyperparameter optimization, meta-learning, reinforcement learning, and black-box/adversarial settings may benefit from the algorithmic ideas (single-loop updates, one solver iteration, function-value-only oracles), but will need supplementary empirical detail, since concrete experimental numbers are not present in the available content.

Authors’ abstract

Online bilevel optimization (OBO) is a powerful framework for machine learning problems where both outer and inner objectives evolve over time, requiring dynamic updates. Current OBO approaches rely on deterministic \textit{window-smoothed} regret minimization, which may not accurately reflect system performance when functions change rapidly. In this work, we introduce a novel search direction and show that both first- and zeroth-order (ZO) stochastic OBO algorithms leveraging this direction achieve sublinear {stochastic bilevel regret without window smoothing}. Beyond these guarantees, our framework enhances efficiency by: (i) reducing oracle dependence in hypergradient estimation, (ii) updating inner and outer variables alongside the linear system solution, and (iii) employing ZO-based estimation of Hessians, Jacobians, and gradients. Experiments on online parametric loss tuning and black-box adversarial attacks validate our approach.