Research map / Bandits and online learning / Online convex optimization and games
On Adaptivity in Information-Constrained Online Learning
Siddharth Mitra, Aditya Gopalan
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 optimistic OMD with a hybrid regularizer and second-order corrections | Label efficient prediction · Label efficient prediction | expected regret: \order{\left(\sqrt{\frac{Q^*T\log K}{n}}\right)} | Improved |
| Replace the hybrid regularizer and second-order corrections with negative entropy and no corrections (ablation) | Adaptive Label Efficient Prediction · Label efficient prediction | expected regret: \order{\left( \sqrt{\nicefrac{QT\log K}{n}}\right)} | Mixed |
| Use epoch-based adaptive η rather than tuning η from prior knowledge of Q | Label efficient prediction · Label efficient prediction | expected regret: \order{\left( \sqrt{\nicefrac{QT\log K}{n}}+ \sqrt{\log K} \right)} | Improved |
| Use label-efficient bandit feedback with log-barrier regularization and second-order corrections | Adaptive Label Efficient Bandits · Label efficient bandits | expected regret: \mathbb{E} \left[ R_T \right] \leq \frac{K\log T}{\epsilon\eta} + 18 \eta Q^* + K(\log T)^2 | Improved |
| Reduce revealing-action games to label efficient prediction | Adaptive Revealing Action Strategy · Revealing action partial monitoring | expected regret: \order{\left(\left(Q^*T \log K \right)^{\nicefrac{1}{3}}\right)} | Improved |
| Use optimistic OMD with forced exploration and loss estimates based on L = WH | Hard partial monitoring strategy · Hard partial monitoring | expected regret: \order{(\left(QT K \right)^{\nicefrac{1}{3}})} | Improved |
Closest papers by meaning
- Online Learning with Sublinear Best-Action Queries (NeurIPS 2024 · similarity 0.89)
- A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.88)
- Label Shift Meets Online Learning: Ensuring Consistent Adaptation with Universal Dynamic Regret (CVPR 2025 · similarity 0.87)
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.87)
- Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.87)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · 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.
