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

Response: Thank you for your review and suggestions. We would like to clarify that the runtime plots presented in both Figure 2 and Figure 3 already show wall-clock time measurements in seconds. Please refer to the left subplot in Figures 2 and 3, where we directly report time elapsed. Specifically,

• In Figure~2 (left panel), we present the actual wall-clock time of our ZO-SOGD method compared to the baseline methods in the online adversarial attack experiment. The recorded times range from approximately $0.5 \times 10^2$ to $2.0 \times 10^2$ seconds at $T = 200$ steps.

• In Figure 3 (left panel), we present wall-clock time comparisons for our SOGD method against OAGD and SOBOW in the parametric loss tuning task. The results show a clear efficiency gain, with SOGD completing under 25 seconds at T = 400, compared to SOBOW, which takes roughly 220 seconds due to its reliance on conjugate gradient (CG) iterations.

All wall-clock times were measured using the same hardware platform across all algorithms to ensure fair and consistent comparisons. These empirical results support the practical value of our proposed methods, aligning with our theoretical efficiency claims.

In the revised version, we will make this point more explicit by stating "wall-clock time" clearly in the figure captions and experimental section to avoid any ambiguity.

Please let us know if we misunderstood your question, and we will be happy to address your concern further.

Further Elaboration on Runtime and Accuracy Using CIFAR-10:

For further elaboration of runtime and how our methods can handle large scale datasets, we have conducted additional experiments on CIFAR10 to demonstrate the scalability and effectiveness of our approach beyond MNIST. For our CIFAR-10 experiments, we used a dataset with 10 classes, and further details on the parameters will be added to the appendix in the revised manuscript.

Below we present the performance comparison of our ZO-SOGD method against single-level ZO methods on CIFAR10:

Table 1: Runtime (seconds)

Table 2: Testing Accuracy (lower is better for attacks)

Table 3: Perturbation Magnitude $||y||_\infty$

The CIFAR-10 results demonstrate that our ZO-SOGD approach scales effectively to higher-dimensional problems with ZO-SOGD (ours, Adam) reducing model accuracy to ~37% at $t=400$ compared to 47-71% for single-level ZO methods, while requiring larger perturbation magnitudes of 8.00 compared to 4.72-5.88 for baseline methods. This represents a trade-off where our approach can achieve significantly higher attack success rates at the cost of somewhat larger perturbations, which remain visually acceptable despite the 12 $\times$ increase in dimensionality from MNIST to CIFAR-10.

Our ZO-SOGD (ours, Adam) achieves this superior performance with approx. 2.9-3.0 $\times$ computational overhead, representing an excellent trade-off when attack success is the primary objective, and the consistent improvement from $t=100$ to $t=400$ confirms that BO optimization yields further benefits in higher-dimensional spaces. The larger perturbation magnitudes are offset by the substantially improved attack success rates, making our approach particularly valuable in scenarios where robustness evaluation is critical. We will add more detailed analyses and hyper-parameter sensitivity studies in the appendix.

Response to W1: Thank you for the helpful comment. We chose to use a hyper-gradient-based approach due to its robustness and strong theoretical guarantees in the context of stochastic OBO problems. In contrast, alternative approaches such as value function methods [1] and asynchronous bilevel optimization methods [2] are primarily designed for deterministic settings. These methods rely on Lagrangian reformulations and typically converge to Lagrangian stationary points, rather than true bilevel solutions. They also require careful tuning of penalty parameters, which increases their complexity. We have clarified the motivation and key differences from the deterministic methods in [1,2] in the revision.

Response to W2: Thank you for the suggestion of arithmetic complexity analysis. We have added a detailed arithmetic complexity comparison in our response to Reviewer x9oa and do not repeat it here due to response length limits. Briefly, our SOGD method significantly reduces computational cost, while ZO-SOGD suffers from worse dimensional dependence due to its gradient-free nature.

Response to W3: Thank you for this important point. We provide a detailed response to Reviewer Xqeg on this issue. Our experiments include a non-convex imbalanced learning task with a deep neural network inner problem (Section 5), where our algorithms show stable convergence despite the lack of strong convexity.

While Refs [3] and [4] use more relaxed inner assumptions (convexity of inner), they focus on simple bilevel problems in the offline setting. Our OBO setting is more complex and requires stronger assumptions for convergence. Adapting relaxed conditions such as PL to stochastic OBO is a valuable direction for future work but needs careful investigation.

Response to W4: We thank the reviewer for the insightful feedback. We have revised the experimental section to provide a clearer analysis of why our proposed methods outperform the baselines and to highlight the components responsible for these improvements. Specifically:

• In Sec 5.1, ZO-SOGD demonstrates stronger attack performance compared to single-level baselines such as ZO-O-Adam. These gains stem from our proposed OBO framework, which allows for continuous optimization of hyper-parameters, in contrast to baselines like ZO-O-Adam that tune such parameters in a discrete and manually selected search space. Additionally, the new search direction defined in Eq. (6), combined with variance control in the finite-difference estimators (Eq. 21) and the projected update on $v_t$ defined in Eq. (8), contributes to more effective ZO-SOGD over time.

• In Sec 5.2, our SOGD method achieves the lowest runtime (left panel) while maintaining high accuracy across varying degrees of class imbalance (middle and right panels). Although other OBO-based algorithms can also perform continuous hyper-parameter search, our superior efficiency result from the single-loop simultaneous update scheme (Alg 1). This avoids the high computational cost of multi-loop strategies, such as SOBOW, which rely on window-smoothing and conjugate gradient solvers.

We have explicitly clarified these points in Sections 5.1 and 5.2 of the revised manuscript.

Response to W5: We appreciate the suggestion to compare with ZO nested methods. To our knowledge, there are no practical zeroth-order nested methods without access to a gradient oracle (including those with variance reduction) available in the literature. We include a comparison (following the setup in Sec.~5) with our offline variant (ZO-S$^2$GD), which highlights a tradeoff: while it achieves stronger attack performance (test accuracy drops to 0.09 at $T=200$), it requires significantly more computation (40$\times$ runtime) and generates highly visible perturbations ($||y|_\infty$ quickly reaches 5.0).

Our online method (ZO-SOGD) maintains an effective balance between computational efficiency, attack performance (testing accuracy 0.56 at $T=200$), and imperceptibility ($||y||_\infty$ 2.7 at $T=200$).

Runtime (seconds)

Testing Accuracy (lower is better for attacks)

Perturbation Magnitude $||y||_\infty$

We also note that, as illustrated in Figure 2 of our paper, ZO-SOGD (ours, Adam) achieves an adversarial testing accuracy of ~0.24 with similar runtime. This highlights the significant computational improvement offered by our online method over offline approaches.

W1: While the experimental evaluations support the claims ... generalizability of the proposed algorithms. A suggestion to explore the sensitivity of … $\rho$ and ablation studies on the momentum components ... .

Response: We appreciate the reviewer’s feedback. To address the generalizability of our algorithms, we conducted additional adversarial attack experiments on CIFAR10, beyond MNIST, and demonstrated the effectiveness of our approach on this larger-scale dataset. Due to space constraints, details and discussion are provided in our response to Reviewer C8i4.

For the smoothing parameter $\rho$, inner/outer stepsizes, and momentum components, we include a hyperparameter sensitivity analysis in our response to Reviewer x9oa, also due to space limitations. Our analysis shows that while ZO-SOGD is sensitive to hyperparameter choices, it remains robust within reasonable ranges. Following your suggestion, we have included extensive tuning results under adversarial attacks in the appendix.

W2: The theoretical assumptions, particularly strong convexity …?

Response: We greatly appreciate this thoughtful comment.

Our current theoretical guarantees rely on Assumption 3.2, which requires strong convexity of the inner objective $g_t(x, \cdot)$. This assumption enables the application of the implicit function theorem and stability of the inner solution mapping $y^*_t(x)$. While this assumption is common in bilevel optimization (e.g., Ghadimi and Wang, 2018; Ji et al., 2021) and is used in almost all previous OBO literature (as cited in Table 1), we acknowledge that it may not always hold in real-world applications.

To demonstrate practical robustness, we have included a highly non-convex imbalanced learning task in our experiments where the inner problem involves training a deep neural network (Section 5). Despite the lack of strong convexity, our algorithms perform effectively, showing stable convergence and improved balanced accuracy.

We also highlight that our online bilevel setup is more complex than standard bilevel settings, as both the inner and outer objectives change over time, making analysis under nonconvex or relaxed conditions significantly more challenging.

That said, we are encouraged by recent progress in extending bilevel optimization to Polyak–Łojasiewicz (PL) conditions (e.g., Shen et al., 2023; arXiv:2302.05185). These works suggest that strong convexity may not be strictly necessary, and PL-like structures may suffice for convergence. We believe our theoretical framework can be extended to PL conditions, which represents an exciting direction for future work. However, given the complexity of our online and dynamic bilevel optimization setting, this extension requires careful investigation. In the final version of the paper, we will incorporate this discussion following the strong convexity assumption.

W3: The proofs are complex … would help readability.

Response: Thank you for the helpful suggestion. We have revised the theory section to include intuitive explanations for the path length and function variation metrics, clarifying how they capture nonstationarity in OBO problems. We have also provided an example in the appendix to illustrate these metrics.

We have also expanded Remarks 3.7, 4.3, and 4.4 to explain the intuition behind our main theorems---highlighting improvements in variance dependence, dimensional scaling, and regret under noisy feedback. Our initial submission included detailed proof roadmaps in Appendix C (lines 796–806) for first-order methods and Appendix D (lines 2185–2196) for zeroth-order methods.

In the final version, we plan to relocate these roadmaps and summaries to the main body, as we will have an additional page. We will also offer a more intuitive high-level roadmap outlining the overall proof strategy: we decompose regret into bias and approximation errors in gradient and projection steps, control these in a sequential manner through a number of lemmas, and assemble them into our final bounds. These changes, along with the existing comments and appendix, help make the theoretical results clearer and easier to understand.

W1:... experiments on larger datasets ... .

Response: We appreciate the reviewer’s feedback regarding evaluation on additional datasets. To address this, we conducted additional experiments on CIFAR10 to demonstrate the scalability of our approach beyond MNIST. Results are provided in our response to Reviewer C8i4 and omitted here due to space constraints.

Response to Question 1: We provide the total computational complexity of our methods and compare them with baselines. This comparison will be added to Table 1 in the final version. Our SOGD algorithm offer notable computational benefits.

As an example, for SOGD, the regret bound $\text{BL-Reg}_T \leq \mathcal{O}(T^{1/3}(\sigma^2 +\Delta_T) + T^{2/3} \Psi_T)$ implies that $T = \mathcal{O}(\varepsilon^{-3})$ suffices for average regret $\leq \varepsilon$, leading to total cost $\mathcal{O}((d_1 + d_2) \cdot \varepsilon^{-3})$. We note that the total cost for other baselines (SOBOW/SOBBO) is derived using their window size $w = o(T)$ and $\kappa_g \log(\kappa_g)$ for conjugate gradient (CG) steps. OAGD baseline incurs higher cost due to exact system solves at each iteration.

SOGD offers two key advantages: 1) it uses a single system solve per step, which is more efficient than full solves or CG steps required by some baselines; 2) it sets $w = 1$, avoiding costly average gradient computation, unlike window-based methods. ZO-SOGD has higher complexity but enables gradient-free optimization. Its higher dimensional dependence is consistent with the increased complexity in single-level ZO methods.

Response to Question 2: We appreciate the reviewer’s concern regarding the handling of non-convex inner problems. To demonstrate practical robustness, the inner problem in Section 5 is non-convex, and our experiments validate that the algorithm performs effectivel--showing stable convergence and improved balanced accuracy. This robustness stems from our novel search direction, which controls variance over time without requiring window smoothing. A detailed discussion is provided in our response to Reviewer Xqeg; due to space constraints, we omit it here.

Response to Question 3: Thank you for the insightful question. As detailed in Section 5 (Experimental Setup), we carefully tuned all hyperparameters to ensure stable and fair comparisons; the selected ranges are listed in Lines 405–420 (second column). Our analysis shows that while ZO-SOGD is sensitive to hyperparameter choices, it remains robust within reasonable ranges. Following your suggestion, we include extensive tuning results under adversarial attacks for ZO-SOGD (ours, Adam), summarized in the tables below.

For inner ($\beta$) and outer ($\alpha$) stepsizes:

For smoothing parameters:

For momentum parameters:

Lower test accuracy indicates better attack performance. The algorithm is robust across a broad range of hyperparameters. Optimal performance is achieved with inner stepsize $\beta = 0.1$, outer stepsize $\alpha = 0.001$, smoothing parameters $\rho_v = 0.01$, $\rho_r = \rho_s = 0.005$, and momentum parameters $\gamma_t = 0.99$, $\lambda_t = \eta_t = 0.99$.

In our revised version, we will include a detailed sensitivity analysis for SOGD (the first-order variant) in the parametric loss tuning application (Section 5.2) in the appendix.