Research map / Bandits and online learning / Online convex optimization and games
Online Improper Learning with an Approximation Oracle
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OMD with a strongly convex regularizer satisfying PNIP and a projection-and-decomposition oracle | Online improper linear optimization with full information · Full information online improper linear optimization | oracle calls per round: O(T) -> O(\log T ) | Helped |
| Use CMWU with refining domains and a separation-or-decomposition oracle | Online improper linear optimization with full information · Full information online improper linear optimization | oracle calls per round: O(T) -> O(\log T) | Helped |
| Use CMWU rather than the earlier non-negative-loss approach | Online improper linear optimization with full information · General loss vectors | supported loss-vector domain | Helped |
| Use OMD with the barycentric regularizer in the bandit setting | Bandit α-regret minimization · Bandit α-regret minimization | oracle calls over T rounds: \widetilde O(T) -> \widetilde O(T^{2/3}) | Helped |
| Use OMD with the barycentric regularizer | Bandit α-regret minimization · Bandit α-regret minimization | regret: O(T^{2/3}) | No clear effect |
| Use OMD instead of online gradient descent with Euclidean regularization | Online improper linear optimization · Full information online improper linear optimization | regret bound | Helped |
Closest papers by meaning
- Adaptive Oracle-Efficient Online Learning (NeurIPS 2022 · similarity 0.91)
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.89)
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.87)
- Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning (NeurIPS 2025 · similarity 0.86)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.86)
- Online Set Learning from Precision and Recall Feedback (NeurIPS 2026 · similarity 0.85)
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.