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

Bilevel optimization (BLO) is essential for hierarchical decision-making, such as meta-learning and hyperparameter optimization. However, standard solvers like Two-Timescale Stochastic Approximation (TTSA) are highly sensitive to heavy-tailed noise—common in reinforcement learning and heterogeneous data settings—which often leads to numerical instability and divergence. This paper asks: can we design a robust optimization framework that distinguishes between informative geometric signals and impulsive stochastic outliers without the over-damping associated with standard norm-based clipping?

The authors propose Robust Quantile-guided TTSA (RQ-TTSA). Instead of using fixed thresholds or global norm-based scaling, the algorithm maintains a sliding window of historical gradient norms. It calculates the empirical quantile of these norms to define an adaptive threshold for Huber-style clipping. This allows the optimizer to dynamically adjust its sensitivity to noise: it expands the threshold in steep regions to capture informative signals and contracts it in flat regions to suppress impulsive outliers. The authors provide a theoretical convergence analysis for this approach under nonconvex-strongly convex assumptions, even when the gradient noise has infinite variance.

RQ-TTSA demonstrates superior stability and convergence compared to state-of-the-art baselines across six diverse tasks, including synthetic bilevel problems, heterogeneous vision benchmarks, and offline reinforcement learning. Theoretically, the authors prove that RQ-TTSA achieves an optimal convergence rate of O(T^{-(p-1)/(3p-2)}) for heavy-tailed noise with a bounded p-th moment (p ∈ (1, 2]). Empirically, the method eliminates divergence spikes, reduces optimization variance by up to 50%, and improves robustness by 2–5x over existing methods. Notably, this performance gain comes with a negligible computational overhead of approximately 2.7%.