Research map / Bandits and online learning / Online convex optimization and games
Adaptive Oracle-Efficient Online Learning
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 |
|---|---|---|---|
| Replace admissibility alone with an approximable PTM, Laplace perturbations, and a data-dependent step size | GFTPL · General online learning | regret bound: O(\frac{N}{\delta}\sqrt{T}) -> O(\max\{{\gamma},\ln K, \sqrt{N\ln K}\}\sqrt{L_T^*}) | Helped |
| Use an approximable, implementable PTM for online auctions with binary admissible PTMs | Proposed GFTPL · Online auctions with binary admissible PTM | regret bound: O(N\sqrt{T-L_T^*}) | Helped |
| Construct the PTM with a coordinate-wise threshold function and an augmented problem | Level auction · Level auction, single-item | regret bound: O(nm^2\sqrt{T}) -> O(nsm\sqrt{T-L_T^{*}}) | Helped |
| Use a 1-approximable, implementable PTM with d columns and complexity 1 | Proposed GFTPL · Online learning with finite adversary action space |Y|=d | regret bound: O(\sqrt{\max\{\ln K,\sqrt{d\ln K}}}\sqrt{L_T^*}) | Helped |
| Switch adaptively between FTL and proposed GFTPL using estimated regret | Oracle-efficient Flipflop (OFF) · General online learning, including IID data | regret bound: R_T^{\OFF}\leq \min\left\{3 U_T^{\FPL}+1, 3{U}_T^{\FTL}+\tau\right\} | Helped |
| Use an ell_p perturbation instead of Laplace perturbation for a binary PTM (ablation) | Proposed GFTPL · General online learning with binary PTM | regret bound: O(\max\{N,\ln K\}\sqrt{L_T^*}) -> O(\max\{N,\ln K,\sqrt{N\ln K}\}\sqrt{L_T^*}) | No clear effect |
| Use an admissible PTM without the approximability condition (ablation) | GFTPL · General online learning | stability ratio of consecutive action probabilities: infinity | Hurt |
Closest papers by meaning
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.91)
- Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning (NeurIPS 2025 · similarity 0.87)
- Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.86)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.86)
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.85)
- Online Estimation via Offline Estimation: An Information-Theoretic Framework (NeurIPS 2024 · 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.