Research map / Bandits and online learning / Online convex optimization and games
Best of Both Worlds Guarantees for Smoothed Online Quadratic 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.
x
Problem
x
Approach
x
Key results
- LAI online optimal with O(T) cost under martingale minimizers; static benchmark is Theta(T^2)
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LAI instead of ROBD | SOQO with martingale minimizers · Stochastic SOQO, martingale minimizers | regret vs. LAI: Ω(T) | Helped |
| Use LAI(γ) with γ=1 instead of the stochastic-optimal LAI | SOQO · Stochastic SOQO, martingale minimizers | regret vs. LAI: constant regret | No clear effect |
| Use LAI(γ) with γ=1 | SOQO · Adversarial SOQO, λ_max^A ≪ 1 | competitive ratio: ≤ 1 + √(κ(A)/λ_min^A) | Helped |
| Replace the dynamic LAI policy with a static action | SOQO · Stochastic SOQO | expected total cost: Θ(T²) | Hurt |
| Use fixed interpolation with C ≠ C_L instead of the adaptive LAI coefficient sequence (ablation) | SOQO with martingale minimizers · Stochastic SOQO, martingale minimizers | regret vs. LAI: Ω(T) | Hurt |
| Set γ=1 in LAI(γ), producing fixed interpolation with C=C_L (ablation) | LAI(γ) · Stochastic SOQO, martingale minimizers | regret vs. LAI: constant regret | Helped |
| Set γ=0 in LAI(γ), recovering LAI (ablation) | LAI(γ) · Stochastic SOQO, martingale minimizers | regret vs. LAI | Helped |
| Use ROBD instead of LAI(γ=1) | SOQO with martingale minimizers · Purely stochastic experiments, light- and heavy-tailed distributions | regret vs. LAI | Hurt |
| Use LAI(γ=1) instead of ROBD | SOQO with mixed stochastic and adversarial minimizers · Mixed environments, adversarial percentage up to approximately 20% | total cost relative to LAI: approximately around 20% | Helped |
| Increase adversarial percentage in the mixed minimizer sequence | LAI(γ=1) and ROBD · Mixed stochastic and adversarial environments | total cost relative to LAI | Mixed |
Limitations
- Assumes known A
- Adversarial guarantee for LAI(gamma) only in small-eigenvalue regime
Experimental setup
Metrics: regret competitive ratio
Baselines: ROBD
Builds on: ROBD
Closest papers by meaning
- Making Non-Stochastic Control (Almost) as Easy as Stochastic (NeurIPS 2020 · similarity 0.89)
- Online Optimization with Memory and Competitive Control (NeurIPS 2020 · similarity 0.88)
- Revisiting Smoothed Online Learning (NeurIPS 2021 · similarity 0.87)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
- Tight Rates for Bandit Control Beyond Quadratics (NeurIPS 2024 · similarity 0.86)
- Online Control with Adversarial Disturbance for Continuous-time Linear Systems (NeurIPS 2024 · similarity 0.86)
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.