Research map / Bandits and online learning / Online convex optimization and games
Safe Online Convex Optimization with Heavy-Tailed Observation Noises
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends safe online convex optimization (SO-PGD) to heavy-tailed observation noises with finite (1+ε)-th moments, proposing median-of-means (SOMM) and truncated-mean (SOTM) variants that achieve O(T^{c_ε}) high-probability regret while satisfying unknown linear safety constraints.
Problem
Safe online convex optimization with unknown linear safety constraints where observation noise is heavy-tailed (only finite (1+ε)-th moments) rather than sub-Gaussian, which breaks prior high-probability guarantees.
Approach
Replace the sub-Gaussian least-squares confidence set in SO-PGD's exploration phase with a median-of-means estimator or a truncated least-squares estimator, giving confidence sets valid under heavy-tailed noise and yielding high-probability regret O(T^{(1+ε)/(1+2ε)}) with safety maintained.
Key results
- SOMM and SOTM achieve high-probability regret O(T^{c_ε}) with c_ε=(1+ε)/(1+2ε), improving the δ dependence of SO-PGD's O(δ^{-1/(1+ε)} T^{c_ε}) bound to polylogarithmic in 1/δ.
- Both algorithms guarantee constraint satisfaction for all rounds with probability at least 1-2δ under heavy-tailed noise with finite (1+ε)-th moments.
- SOTM needs only the moment bound q, whereas SOMM requires the constant c; the paper provides no empirical experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use median-of-means estimation in the exploration phase instead of a single least-squares estimate | SO-PGD · SOCO with heavy-tailed observation noise | regret bound: O(δ^{-1/(1+ϵ)} T^{(1+ϵ)/(1+2ϵ)}) -> O((log (1/δ))^{1/(1+ϵ)} T^{(1+ϵ)/(1+2ϵ)}) | Helped |
| Truncate extreme observations during the exploration phase | SO-PGD · SOCO with heavy-tailed observation noise | regret bound: O(δ^{-1/(1+ϵ)} T^{(1+ϵ)/(1+2ϵ)}) -> O((log (1/δ))^{1/(1+ϵ)} T^{(1+ϵ)/(1+2ϵ)}) | Helped |
| Use the original least-squares estimate with a heavy-tailed confidence radius | SO-PGD · SOCO with heavy-tailed observation noise | regret bound: O(δ^{-1/(1+ϵ)} T^{(1+ϵ)/(1+2ϵ)}) | Hurt |
Limitations
- Requires prior knowledge of heavy-tailed noise constants (q or c and ε).
- Results are purely theoretical with no empirical experiments.
- Regret bound depends on the exploration phase and T0 tuned to T^{c_ε}.
Experimental setup
Metrics: regret bound (theoretical) safety satisfaction probability
Baselines: SO-PGD
Builds on: SO-PGD Online gradient descent Median-of-means bandit (Shao et al. 2018) Heavy-tailed linear bandits (Xue et al. 2021)
Closest papers by meaning
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.90)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.89)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.88)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.88)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.