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

• URL: http://arxiv.org/abs/2606.22436v1
• Date: Sun, 21 Jun 2026 10:57:37 GMT
• Title: Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation
• Abstract summary: Bilevel optimization (BLO) is fundamental to hierarchical decision-making but suffers from critical instability under heavy-tailed noise.<n>Existing techniques typically rely on magnitude checks, which fail to distinguish informative geometric signals from outliers.
• Score: 16.106678611834102
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization (BLO) is fundamental to hierarchical decision-making but suffers from critical instability under heavy-tailed stochastic noise. Existing variance-reduction techniques typically rely on myopic magnitude checks, which fail to distinguish informative geometric signals from impulsive outliers. To resolve this, we propose \textbf{RQ-TTSA} (Robust Quantile-guided TTSA), a distribution-aware framework that leverages historical gradient buffers to estimate rolling quantiles for adaptive Huber-style clipping, effectively preserving local optimization geometry while strictly bounding effective variance. Theoretically, we provide a convergence analysis for quantile-guided TTSA under nonconvex-strongly convex assumptions with infinite-variance noise ($p \in (1,2]$), deriving a rate of $\mathcal{O}(T^{-\frac{p-1}{3p-2}})$ that recovers optimal dependence on the heavy-tailed parameter. Empirically, across six diverse tasks, spanning heterogeneous vision benchmarks, dynamic games under momentum poisoning, and offline reinforcement learning, RQ-TTSA consistently outperforms state-of-the-art baselines by eliminating divergence spikes and ensuring stable convergence. Our method demonstrates significant robustness to hyperparameter variations and incurs negligible computational overhead ($\approx 2.7\%$ increase), validating distribution-aware gradient control as a practical and necessary component for reliable bilevel learning.

Related papers

• Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization [16.106678611834102]
  Many central machine learning tasks are fundamentally root-finding problems rather than minimization loss.<n> squared residuals introduce a critical flaw we identify as the Variance Trap.<n>Standard bilevel minimization algorithms require estimating hypergradients involving implicit Jacobians.<n>We propose a Jacobian-free solution using Two-TimeScale Approximation (TTSA) that updates directly along the root error.
  arXiv  Detail & Related papers  (2026-06-21T10:53:32Z)
• Clipping Bottleneck: Stabilizing RLVR via Stochastic Recovery of Near-Boundary Signals [83.0127582612634]
  Near-boundary Rescue (NSR) is a minimal, plug-and-play modification that retains out-of-bound tokens to recover lost signals.<n>NSR substantially improves training stability and delivers consistent gains over strong baselines such as DAPO and GSPO.
  arXiv  Detail & Related papers  (2026-05-21T16:45:31Z)
• Holder Policy Optimisation [26.521180498291717]
  textbfHlderPO is a generalised policy optimisation framework.<n>It unifies token-level probability aggregation via the Hlder mean.<n>It achieves a state-of-the-art average accuracy of $54.9%$ across multiple mathematical benchmarks.
  arXiv  Detail & Related papers  (2026-05-12T12:45:03Z)
• Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL [8.809468023364703]
  Design of robust reinforcement learning algorithms poses fundamental challenges.<n>We propose an approximate DRRL framework based on a first-order expansion of the relevant robust functional.<n>To learn the fixed point of this approximate equation, we propose Mean-Variance Approximation (MVSA)
  arXiv  Detail & Related papers  (2026-05-08T19:24:28Z)
• From $\oldsymbol{\logπ}$ to $\oldsymbolπ$: Taming Divergence in Soft Clipping via Bilateral Decoupled Decay of Probability Gradient Weight [6.07556923512707]
  Reinforcement Learning with Verifiable Rewards (RLVR) has catalyzed a leap in Large Language Model (LLM) reasoning, yet its optimization dynamics remain fragile.<n>Standard algorithms like GRPO enforce stability via hard clipping'', which inadvertently stifles exploration by discarding gradients of tokens outside the trust region.<n>We propose Decoupled Gradient Policy Optimization (DGPO), which employs a decoupled decay mechanism based on importance sampling ratios.
  arXiv  Detail & Related papers  (2026-03-15T14:00:48Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Improved High-probability Convergence Guarantees of Decentralized SGD [74.39742894097348]
  We show that $mathttDSGD$ converges in HP under the same conditions on the cost as in the mean-squared error (MSE) sense.<n>Our improved analysis yields linear-up in the number of users, demonstrating that $mathttDSGD$ maintains performance in the HP sense.
  arXiv  Detail & Related papers  (2025-10-07T17:15:08Z)
• On the Power of Perturbation under Sampling in Solving Extensive-Form Games [56.013335390600524]
  We investigate how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in solving extensive-form games under sampling.<n>We present a unified framework for textitPerturbed FTRL algorithms and study two variants: PFTRL-KL and PFTRL-RKL.
  arXiv  Detail & Related papers  (2025-01-28T00:29:38Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  We show that Prospect, a gradient-based algorithm, enjoys linear convergence for smooth regularized losses. We also show that Prospect can converge 2-3$times$ faster than baselines such as gradient-based methods.
  arXiv  Detail & Related papers  (2023-10-21T00:03:54Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.