acceptodds
Under review as a conference paper at ICLR 2027

Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation

Abstract

Heavy-tailed stochastic gradients can destabilize bilevel optimization by prop- agating lower-level errors into upper-level updates. We propose RQ-TTSA, a quantile-guided clipping framework for two-timescale stochastic approximation. The method uses a rolling buffer of gradient norms to adapt its clipping threshold, controlling the magnitudes of lower-level stochastic gradients while preserving their directions through radial rescaling. We further specify a predictable threshold variant that combines historical quantile estimates with bounded scale factors and an explicit polynomial growth schedule. This construction establishes pathwise threshold bounds and separates empirical scale adaptation from the growth con- ditions needed for convergence analysis. Experiments with the rolling-quantile implementation cover synthetic problems, vision benchmarks, stochastic games, and offline actor–critic learning. The reported results show lower mean final losses on the vision benchmarks and reduced actor-loss fluctuations in the offline re- inforcement learning experiment, while stability gains vary across tasks. These findings suggest that recent gradient statistics can provide useful scale information for robust bilevel updates.

Primary area:
optimization
Keywords:
Bilevel Optimization, Stochastic Optimization, Robust Optimization, Heavy-tailed Noise, Stochastic Approximation, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_pvxZOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes clipping the lower-level stochastic gradient in two-timescale bilevel optimization under heavy-tailed noise. The clipping threshold is set from a rolling quantile of recent gradient norms. The analysis studies a variant with a deterministic, polynomially growing threshold under noise with bounded pp-th moment, p∈(1,2]p \in (1,2]. Experiments cover synthetic problems, two vision tasks, a stochastic zero-sum game, and offline actor-critic.

Critical strengths
  1. The paper addresses a relevant problem. Large gradient outliers can make bilevel optimization unstable, and using recent gradient information to adjust clipping is a reasonable idea.
  2. The experiments cover several settings and include a fixed-threshold variant. This helps assess whether adapting the threshold matters in practice.
Critical weaknesses
  1. Assumption 4.2 bounds the noise around the true gradient. However, Theorem 4.4 uses this noise bound to control the expected squared norm of the clipped gradient itself. These are different quantities. For example, take a deterministic gradient equal to 2, with p=2p=2 and σ=1\sigma=1. The noise assumption is satisfied because there is no noise. If the clipping threshold is sufficiently large, the gradient remains unchanged, so its squared norm is 4. The theorem nevertheless bounds it by 1. The appendix introduces a term involving the true gradient but then drops it. This term needs to be handled explicitly, because the lower-level tracking proof relies on the resulting bound.

  2. The method requires the outer step αk\alpha_k to become smaller relative to the lower-level step βk\beta_k, so that the lower-level iterate can track the changing solution. However, the theorem chooses αk∝k−(1−ν),βk∝k−ν,ν>1/2.\alpha_k\propto k^{-(1-\nu)},\qquad \beta_k\propto k^{-\nu},\qquad \nu>1/2. This gives αk/βk∝k2ν−1\alpha_k/\beta_k\propto k^{2\nu-1}, which grows rather than tending to zero. With this schedule, the accumulated tracking-error contribution in the final bound also grows instead of vanishing. The proof therefore does not establish the claimed convergence rate. Please clarify the intended schedule and redo the rate calculation, since swapping the exponents also changes the balance of the other error terms.

Questions for authors
  1. Can you give a valid clipping bound that accounts for the true gradient and explain how it changes the analysis?

  2. Which step-size schedule is intended, and does the corrected analysis still give the claimed rate?

Reviewer_nan3OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper extends TTSA to the case where the LL problem is stochastic, and the noise is heavy-tailed. The proposed algorithm, RQ-TTSA, uses a quantile-guided clipping framework and a buffer of gradient norms to adapt its clipping threshold. Experiments are conducted on vision benchmarks to show the utility of the proposed approach.

Critical strengths

The paper considers a practical setting of heavy-tailed noise in the LL update and provides convergence guarantees for this setting. The presented experiments show strong performance of the proposed method.

Critical weaknesses

There are many major issues with the paper. Here, I list the major weaknesses.

  • The underlying premise of the paper is wrong. The paper mentions and states that TTSA is the optimal algorithm for solving stochastic bilevel algorithms under strongly convex LL and bounded noise variance; this is not true. TTSA is not an optimal algorithm for stochastic bilevel algorithms; this can be seen from the fact that many algorithms under the same assumptions achieve faster convergence than TTSA; for example, check ALSET and StocBIO.

    More importantly, the majority of convergence rates stated in the paper for existing algorithms are wrong. TTSA does not achieve a rate of O(ϵ−3)O(\epsilon^{-3}); similarly, the rates stated for BiSLS and AccBO are wrong in the table and the discussion. Also, please note that the measure of performance in AccBO is not the squared norm of the gradient, as in other papers.

  • Another major issue is with the statements made about the papers and algorithms discussed in the literature review and in the introduction section. The statements made are simply not correct for the majority of works. For example, in the introduction for TTSA, the paper cites StocBiO. Then later, Khanduri et al. 2021 is a variance-reduced method, but the paper mentions that it is developed to mitigate sensitivity to hyperparameters. Similarly, I am not sure why Reddy et al. 2020, a single-level FL method, is randomly cited among other bilevel methods. The references cited and the discussion seem random, without following any scheme. Also, when the paper stated that "this assumption is routinely violated in regimes characterized by sparse rewards in RL Zhang et al. (2019); Gorbunov et al. (2020)", the cited papers are not RL papers. Similarly, it is not clear why heavy-tailed noise should exist at the lower level for FL problems.

  • The literature review is incomplete; it has left out some major works that have significantly improved on TTSA. One big example is ALSET that is actually close to an optimal algorithm than TTSA. Similarly, AMiGO, STOCBiO, and multiple single-level methods recently proposed for solving the problem are considered flagship methods in the bilevel literature. All of these methods are missing from the discussion.

  • The paper says that (1) is a stochastic problem, but as stated, it is a deterministic problem. Also, ξ\xi and ζ\zeta appear when the gradients are computed and are never defined in the paper.

  • Why is heavy-tailed noise only considered in the lower level? Why does it not affect the upper level?

  • Why are parts of the paper written in blue font?

  • Finally, I believe even if all the mistakes in the paper are ignored, the motivation and the contributions made in the paper may not be enough to warrant publication. Specifically, first, the paper claims that it recovers the optimal rate of TTSA, which is not correct. Secondly, adding heavy-tailed noise only in the LL without sufficient motivation is also a major drawback.

Questions for authors

The whole premise of the paper is wrong, and the guarantees presented for other algorithms and papers are wrong.

Reviewer_wD2FOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studied robust bilevel optimization with heavy tail noise and proposed RQ-TTSA using quantile-guided clipping framework to alleviate the issue of noises. Convergence results are established for RQ-TTSA, and the sample complexity of it is O(T−p−13p−2)\mathcal{O}\left(T^{-\frac{p-1}{3 p-2}}\right) with p∈(1,2]p\in (1,2]. Experiments validate the effectiveness of the proposed method.

Critical strengths

The heavy tail noise issues are important to bilevel optimization problem.

Critical weaknesses
  1. The key theorem in this paper seems to have some technical flaws. As shown in (31) in Appendix B.4.3, the last term includes the error term Czκ2αk2/βkC_z \kappa^2 \alpha_k^2 / \beta_k. Under the chosen stepsizes αk=k−(1−ν),βk=k−ν\alpha_k=k^{-(1-\nu)}, \beta_k=k^{-\nu}, its contribution after summing and normalizing is

\begin{align*} \frac{\sum_{k=1}^T \alpha_k^2 / \beta_k}{\sum_{k=1}^T \alpha_k}=\frac{\Theta\left(\sum_{k=1}^T k^{3 \nu-2}\right)}{\Theta\left(\sum_{k=1}^T k^{\nu-1}\right)}=\Theta\left(T^{2 \nu-1}\right) . \end{align*}

This grows for ν>1/2\nu>1 / 2 and cannot be omitted. In the paper, the authors choose ν=p3p−2\nu=\frac{p}{3 p-2} and set ν∈(0.5,1)\nu \in(0.5,1), so the error terms cannot be overlooked and the resulting bound seems to be problematic.

  1. Some relevant works are missing, making it hard to justify the contribution of this work. For example, the method proposed in [1] uses fully first order oracles and seems to have better complexity bound. [2] studied single-level optimization, but the gradient-norm quantile clipping with a rolling history buffer technique proposed in this method seems to be similar to their work, and the novelty of applying it into bilevel optimization is somewhat limited.

  2. In the toy example (11) with λ=10\lambda=10, solving the lower-level problem gives

\begin{align} \phi^{\star}(\theta)=\frac{3}{4} \theta, F(\theta, \phi^{\star}(\theta))=-\frac{5}{16} \theta^2 . \end{align}

Therefore, over θ∈[−1,1]\theta \in[-1,1], the minima should be (θ,ϕ)=(±1,±3/4)(\theta, \phi)=( \pm 1, \pm 3 / 4), with value -5/16. So the solution (0,0)(0,0) is not a minimizer of the reduced outer objective and the convergence toward zero does not show the minimization of the stated problem.

[1] Stochastic Bilevel Optimization with Heavy-Tailed Noise. Zhuanghua Liu, Luo Luo. https://arxiv.org/pdf/2509.14952

[2] Robust Stochastic Optimization via Gradient Quantile Clipping. Ibrahim Merad, Stéphane Gaïffas. https://arxiv.org/pdf/2309.17316v2

Questions for authors

Please see weakness.

Minor issues: the figure generation quality in this paper can be improved. For example, different lines in Figure 2 overlap with each other and it is hard to visualize the gains and distinguish different methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.