Research map / Bandits and online learning / Online convex optimization and games
Universal Online Convex Optimization with $1$ Projection per Round
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.
Proposes a universal OCO algorithm that uses only one projection onto the feasible domain per round, by combining black-box domain-converting surrogate losses with expert-based meta-learning and a new expert-loss for strongly convex functions.
Problem
Universal online convex optimization (simultaneously optimal regret for general convex, exp-concave, and strongly convex functions) typically requires O(log T) projections onto the feasible domain per round, which is costly for complicated domains.
Approach
Runs experts over a simple enclosing ball using a domain-converting surrogate loss, designs a new expert-loss for strongly convex functions using the actual decision x_t, and decomposes regret into meta-regret and expert-regret so the meta-regret's surrogate-induced negative term cancels; only the final aggregated decision is projected onto the true domain.
Key results
- Achieves O(sqrt(T)), O(d/alpha log T), and O(1/lambda log T) regret for general convex, alpha-exp-concave, and lambda-strongly convex functions with only 1 projection per round.
- Enhanced expert-loss yields small-loss regret O(sqrt(L_T)), O(d/alpha log L_T), O(1/lambda log L_T) for smooth non-negative functions, still with 1 projection per round.
- Theoretical analysis only; no empirical experiments reported.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce projections per round from O(\log T) to 1 | Universal OCO · General convex, exp-concave, and strongly convex functions | projections per round: O(\log T) -> 1 | Helped |
| Add an expert-loss for strongly convex functions using distance to the actual decision x_t | Proposed universal OCO · Strongly convex functions | regret: O(\frac{1}{\lambda}\log T) | Helped |
| Add the smoothness-enhanced expert-loss for strongly convex functions | Proposed small-loss universal OCO · Strongly convex smooth functions | regret: O(\frac{1}{\lambda}\log L_T) | Helped |
| Use the older domain-converting surrogate loss instead of the proposed surrogate loss | Universal OCO for strongly convex functions · Strongly convex functions | regret | Hurt |
Limitations
- Requires known domain diameter D and gradient bound G
- Strong convexity modulus assumed to lie in [1/T,1] via discretized expert grid
- No empirical evaluation
Experimental setup
Metrics: regret number of projections per round
Baselines: MetaGrad Maler AOGD projection-efficient MetaGrad (black-box reduction)
Builds on: MetaGrad Maler black-box reduction for projection-efficient MetaGrad Adapt-ML-Prod online gradient descent online newton step
Closest papers by meaning
- A Simple yet Universal Strategy for Online Convex Optimization (ICML 2022 · similarity 0.94)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.91)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.91)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.90)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 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.