Research map / Bandits and online learning / Online convex optimization and games
An Ellipsoid Algorithm for Online Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an ellipsoid-based algorithm for online convex optimization that uses only a separation oracle, avoiding Euclidean projections onto the feasible set.
Problem
Online convex optimization over a convex set accessed via a separation oracle, where projection-based methods like projected OGD require costly Euclidean projections onto the feasible set whenever iterates leave it.
Approach
Replaces Euclidean projections with ellipsoid-method updates driven by separation oracle queries, so the iterates are maintained without projecting onto K, while keeping the optimal O(sqrt(T)) regret order (per the abstract's framing of OGD as the benchmark).
Key results
- The abstract states projected OGD achieves the optimal O(sqrt(T)) regret but requires Euclidean projections; the paper proposes an ellipsoid-based alternative (full results unavailable in the provided text).
Experimental setup
Metrics: regret
Baselines: projected online gradient descent
Builds on: online gradient descent ellipsoid method
Closest papers by meaning
- Projection-Free Online Convex Optimization via Efficient Newton Iterations (NeurIPS 2023 · similarity 0.91)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.89)
- Gradient-Variation Bound for Online Convex Optimization with Constraints (AAAI 2023 · similarity 0.89)
- Universal Online Convex Optimization with $1$ Projection per Round (NeurIPS 2024 · similarity 0.89)
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.89)
- From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · 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.