Research map / Bandits and online learning / Online convex optimization and games
Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets
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.
Shows that adaptive-to-curvature online algorithms can exploit the local curvature of feasible sets via a new "sphere-enclosed" condition, giving O(ρ ln T) regret in stochastic OCO and matching bounds for uniformly convex sets.
Problem
Achieving logarithmic (fast) regret in online convex optimization by exploiting the curvature of the feasible set, which prior work only handled for linear losses under global curvature or growth-type assumptions on loss vectors.
Approach
Introduces the (ρ, x⋆, f°)-sphere-enclosed condition, a local property at the optimum requiring the feasible set to lie in a sphere tangent at x⋆ aligned with the expected gradient; combined with universal online learning bounds (MetaGrad/Maler-type), this yields O(ρ ln T) regret directly for convex losses, plus a matching bound for q-uniformly convex sets.
Key results
- Achieves O(ρ ln T) regret in stochastic environments when K is sphere-enclosed at x⋆ and ∇f°(x⋆)≠0.
- Achieves O(√T) adversarially and O(ρ ln T + √(Cρ ln T)) under corruption level C.
- For q-uniformly convex sets, regret O(T^{(q-2)/(2(q-1))} (ln T)^{q/(2(q-1))}), matching a stochastic lower bound for d=2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Exploit local sphere-enclosed curvature of the feasible set | Curvature-adaptive algorithm · Stochastic OCO with convex losses and nonzero optimal gradient | regret: O(\rho \ln T) | Helped |
| Use a curvature-adaptive algorithm instead of FTL | Online optimization under adversarial losses · Adversarial OCO | regret: O(\sqrt{T}) vs. \Omega(T) | Helped |
| Exploit uniform convexity of the feasible set | Curvature-adaptive algorithm · Stochastic OCO with q-uniformly convex feasible sets | regret: O\prn*{T^{\frac{q-2}{2(q-1)}} \prn*{\ln T}^{\frac{q}{2(q-1)}}} vs. O\prn*{T^{\frac{q-2}{q-1}}} | Helped |
| Combine feasible-set curvature with strong convexity of the losses | Curvature-adaptive algorithm · Stochastic OCO with strongly convex losses | regret: O \prn*{ \frac{\Csc^2}{\gamma_\star + \alpha / \xi} \ln T + \Csc' \ln T} | Helped |
| Apply the sphere-enclosed curvature guarantee in a corrupted stochastic environment | Curvature-adaptive algorithm · Corrupted stochastic OCO | regret: O(\rho \ln T + \sqrt{C \rho \ln T}) | Helped |
Surprising findings
- FTL can suffer Ω(T) regret in adversarial environments where the growth condition fails, whereas the proposed approach retains O(√T).
Limitations
- Analysis assumes stochastic environments for the main logarithmic bound; sphere-enclosed condition is not extended to arbitrary norms.
- Lower bounds only proven for specific ellipsoid/linear constructions, not for general sphere-enclosed sets.
- Corrupted-stochastic bound is only nearly matching (up to logarithmic factors).
Experimental setup
Metrics: regret upper bound regret lower bound
Baselines: follow-the-leader MetaGrad online gradient descent Bernstein condition analysis
Builds on: MetaGrad Maler follow-the-leader Bernstein condition
Closest papers by meaning
- From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · similarity 0.94)
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback (ICML 2025 · similarity 0.93)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.91)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.91)
- Universal Online Convex Optimization with $1$ Projection per Round (NeurIPS 2024 · similarity 0.90)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.89)
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.