2018/04/20 by Elad Hazan, Hazan, Elad, Wei Hu +5 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1804.07837
arxiv created 2018/04/20 · openalex publication_date 2018/04/20 · arxiv updated 2018/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the question of reducing online learning to approximate optimization of the offline problem. In this setting, we give two algorithms with near-optimal performance in the full information setting: they guarantee optimal regret and require only poly-logarithmically many calls to the approximation oracle per iteration. Furthermore, these algorithms apply to the more general improper learning problems. In the bandit setting, our algorithm also significantly improves the best previously known oracle complexity while maintaining the same regret.