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

Problem Statement

The paper addresses Online Bilevel Optimization (OBO), a framework where both outer and inner objectives evolve over time, requiring dynamic updates to decision variables without prior knowledge of future outcomes. In the standard offline setting, bilevel optimization minimizes an outer objective $f(x, y^*(x))$ subject to $y^*(x)$ being the solution to an inner minimization problem $g(x, y)$. In the online setting, the functions $f_t$ and $g_t$ change at each round $t$, and the agent must select $x_t$ and $y_t$ sequentially.

A critical challenge in existing OBO literature is the reliance on deterministic window-smoothed regret minimization. Current methods (e.g., OAGD, SOBOW) average objectives over a window $w$ to achieve sublinear regret bounds. However, the authors argue that when functions change rapidly, window smoothing may misrepresent system performance and fail to capture the true regret behavior. Furthermore, existing approaches often require access to exact gradients, Hessians, and Jacobians, or rely on expensive iterative solvers (like Conjugate Gradient) to approximate the hypergradient, which limits scalability in large-scale or black-box settings.

The paper focuses on stochastic OBO, where only noisy evaluations of functions, gradients, and Hessians are available. The goal is to minimize stochastic bilevel regret without window smoothing and with limited oracle access (specifically, function value oracles in the zeroth-order setting).

Methodology

The authors propose a novel framework centered on a new search direction that enables sublinear regret without window smoothing. This framework is implemented through two primary algorithms:

1. Simultaneous Online Gradient Descent (SOGD)

For settings with access to first-order and inner second-order oracles, the paper introduces SOGD (Algorithm 1).

• Novel Search Direction: Unlike previous methods that use window-smoothed gradients or alternating loops, SOGD employs a recursive momentum-type search direction (Equation 7) that incorporates the difference between current and previous gradients. This direction is used for updating the follower variable $y$, the auxiliary variable $v$ (solving the linear system), and the leader variable $x$ simultaneously.
• Single-Loop Structure: The algorithm updates all variables ($x_t, y_t, v_t$) in a single loop per round, avoiding the computational overhead of multiple inner-loop iterations required by methods like SOBOW.
• Linear System Approximation: Instead of solving the linear system $\nabla^2_y g_t v + \nabla_y f_t = 0$ exactly, SOGD updates an auxiliary variable $v_t$ using a single gradient step, effectively decoupling the nonlinear structure of the hypergradient.

2. Zeroth-Order SOGD (ZO-SOGD)

For black-box settings where gradients are unavailable, the paper proposes ZO-SOGD (Algorithm 2).

• Function Value Oracles: This method relies solely on noisy function value evaluations. It constructs unbiased estimators for gradients, Hessians, and Jacobians using Gaussian smoothing and finite-difference approximations.
• Estimation Strategy:
  • Gradients are estimated using two-point function evaluations (Equations 24-25).
  • Hessian-vector and Jacobian-vector products are approximated via finite differences of the estimated gradients (Equation 26).
• Convergence Control: The algorithm employs a projection step on the auxiliary variable $v$ to bound its norm, controlling variance in the updates.

Key Contributions

1. Stochastic Regret Minimization without Window-Smoothing:
   The paper introduces a novel search direction and proves that both first-order (SOGD) and zeroth-order (ZO-SOGD) algorithms achieve sublinear stochastic bilevel regret with a window size of $w=1$. This removes the need for window smoothing, which is often restrictive in rapidly changing environments. The regret bounds depend on path-lengths and function variations of the underlying sequences.

2. Efficiency in Oracle Dependence:
   The framework significantly reduces oracle dependence.

   • First-Order: It avoids the need for exact solutions to the inner linear system, using a single-step update for the auxiliary variable.
   • Zeroth-Order: It is the first to provide regret guarantees for OBO using only function value oracles for both the leader and follower objectives. It successfully estimates Hessians, Jacobians, and gradients from function values, addressing the challenge of the nested structure in bilevel problems.

3. Single Subproblem Solver Iteration:
   The proposed algorithms require only one subproblem solver iteration per round. This contrasts with methods like SOBOW, which use Conjugate Gradient with increasing iterations, thereby improving computational efficiency and scalability.

Results and Regret Bounds

The paper establishes theoretical regret bounds for both algorithms under standard assumptions (strong convexity of the inner objective, smoothness, and bounded variance of stochastic estimators).

• SOGD (First-Order):
  Theorem 2.6 guarantees a bilevel local regret bound of:
  $$BL\text{-}Reg_T \le O\left( T^{1/3}(\sigma^2 + \Delta_T) + T^{2/3}\Psi_T \right)$$
  where $\sigma^2$ represents the variance of stochastic estimators, and $\Delta_T, \Psi_T$ capture the variations in the environment (function values, gradients, Hessians, and Jacobians). Under suitable conditions where these variations grow sublinearly, the average dynamic regret is sublinear ($o(T)$). Notably, this improves upon the $O(T^{-1/2}\sigma^2)$ rate of previous stochastic OBO methods.

• ZO-SOGD (Zeroth-Order):
  Theorem 3.2 provides the first regret guarantee for OBO with only noisy function evaluations. The bound is:
  $$BL\text{-}Reg_T \le O\left( (d_1 + d_2)^{3/4} T^{1/3}(\hat{\sigma}^2 + \hat{\Delta}_T) + (d_1 + d_2)^{3/2} T^{2/3}\hat{\Psi}_T \right)$$
  The dependence on dimension $(d_1 + d_2)$ aligns with optimal results for offline min-max problems. The bound also depends on batch sizes and smoothing parameters.

Experimental Validation

The authors validate their approach on two applications:

1. Online Black-Box Adversarial Attacks (BBAA): Using MNIST data, ZO-SOGD and ZO-SOGD (Adam) were compared against single-level zeroth-order baselines (ZO-O-GD, ZO-O-Adam, etc.). Results showed that ZO-SOGD achieved superior attack accuracy and maintained effective perturbations despite the added complexity of outer-level optimization.
2. Parametric Loss Tuning for Imbalanced Data: The algorithms were tested on tuning logit adjustments for imbalanced datasets. SOGD demonstrated faster runtime compared to SOBOW (due to the single-loop structure) and achieved competitive accuracy in balancing classes as the data distribution shifted.

Significance and Claims

The paper claims to overcome the limitations of existing OBO algorithms that depend on extensive oracle information and high computational costs. By introducing a novel search direction and utilizing limited feedback (including zeroth-order), the proposed methods achieve sublinear bilevel regret without window smoothing.

The authors position this work as a significant step toward efficient online bilevel optimization in dynamic, non-convex, and black-box settings. They explicitly note a limitation: the results focus on nonconvex regret bounds and do not extend guarantees to convex settings. The work is presented as a foundational framework for handling dynamic bilevel problems where traditional smoothing techniques fail to accurately reflect performance.