Research map / Bandits and online learning / Online convex optimization and games
Unconstrained Robust Online Convex Optimization
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.
Studies unconstrained online convex optimization when gradient feedback is adversarially corrupted, proposing algorithms with regret ||u||G(sqrt(T)+k) (G known) and an extra (||u||^2+G^2)k penalty (G unknown).
Problem
Online convex optimization over unconstrained domains R^d where the learner receives corrupted gradients; existing unconstrained algorithms incur very high regret even under tiny corruption.
Approach
Clip corrupted gradients, add a Huber-type composite regularizer plus sparsely applied quadratic regularizers to cancel corruption error, use an epigraph-based centered mirror descent learner for composite losses, and an adaptive threshold filter to estimate unknown G.
Key results
- With known G, regret is O~(||u||G(sqrt(T)+k)), matched by a lower bound Omega(||u||(sqrt(T)+k)).
- With unknown G, an extra additive penalty of (||u||^2+G^2)k is incurred, giving O~(||u||G(sqrt(T)+k) + (k+1)(||u||^2+G^2)) in a corollary.
- Simulation with KT-bettor on |w-1| shows exponential blow-up of regret under k=20 corrupted rounds, motivating the method.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the known-G algorithm without prior knowledge of G, with adaptive thresholding and regularization | Robust Online Learning · Unconstrained OCO | regret: unknown G adds (k+1) \left( \|u\|^2 + [G]_{\tau_G}^2 \right) | Hurt |
| Increase quadratic regularization to obtain constant regret at the origin (ablation) | Robust Online Learning (unknown G) · Unconstrained OCO | regret: \|u\|^2 (k+1)^2; constant regret at the origin no matter what k is | Mixed |
| Set γ_β = k², γ_α = k+1, c = τ_G, and τ_D = 1 instead of the alternative unknown-G parameter configuration (ablation) | Robust Online Learning (unknown G) · Unconstrained OCO | regret: \|u\|^2 (k+1)^2 rather than a penalty scaling with k | Mixed |
Surprising findings
- Standard unconstrained algorithms like KT-bettor suffer extremely high regret even under very small corruption, unlike the bounded-domain case.
Limitations
- Dependence on k for unknown G is multiplicative in the (||u||^2+G^2)k term and its optimality is unclear.
- Requires a corruption budget k to be supplied to the algorithm.
- Algorithm requires bisection to solve for iterates and tuning of several regularization parameters.
Experimental setup
Metrics: regret
Baselines: KT-bettor
Builds on: KT-bettor centered mirror descent epigraph-based regularization Huber regularization for unconstrained OCO
Closest papers by meaning
- Efficient online algorithms for fast-rate regret bounds under sparsity (NeurIPS 2018 · similarity 0.91)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.88)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.88)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.87)
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.