Research map / Bandits and online learning / Online convex optimization and games
Efficient Online Linear Optimization with Approximation Algorithms
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 the new infeasible-projection algorithm instead of the KKL approach | Full-information online linear optimization with an approximation oracle · Full information | approximation-oracle calls per iteration: T -> \log(T) | Helped |
| Use the new infeasible-projection algorithm instead of the KKL approach | Bandit online linear optimization with a barycentric spanner · Bandit information | expected approximation-oracle calls per iteration: T^{2/3} -> \log(T) | Helped |
| Use the new full-information algorithm with low-oracle-complexity parameter settings | Full-information online linear optimization with an approximation oracle · Full information | expected α-regret: T^{-1/2} -> O(T^{-1/3}) | Mixed |
| Use the new bandit algorithm with a barycentric spanner | Bandit online linear optimization with an approximation oracle · Bandit information | expected α-regret: T^{-1/3} -> T^{-1/3} | No clear effect |
| Choose the alternative learning rate and projection error for the optimal-regret guarantee | Full-information algorithm · Full information | expected α-regret: O(αRFT^{-1/3}) -> O(αRFT^{-1/2}) | Helped |
| Choose the alternative learning rate and projection error for the optimal-regret guarantee | Full-information algorithm · Full information | approximation-oracle calls per iteration: O(d^2\ln\left({\frac{\alpha+1}{\alpha}T}\right)) -> O(\sqrt{T}d^2\ln\left({\frac{\alpha+1}{\alpha}T}\right)) | Hurt |
| Use a barycentric-spanner-based exploration reduction to estimate loss vectors | Bandit algorithm · Bandit information | expected α-regret: O((αβdCR+αRF+C)T^{-1/3}) | Helped |
Closest papers by meaning
- Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback (NeurIPS 2019 · similarity 0.93)
- Online Linear Optimization with Many Hints (NeurIPS 2020 · similarity 0.92)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.91)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.89)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.89)
- Online Submodular Maximization via Online Convex Optimization (AAAI 2024 · similarity 0.88)
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.