2019/10/08 by Dan Garber, Garber, Dan, Ben Kretzu +1 · 1 citation
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1910.03374
openalex publication_date 2019/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the challenge of designing online algorithms for the bandit convex optimization problem (BCO) which are also scalable to high dimensional problems. Hence, we consider algorithms that are projection-free, i.e., based on the conditional gradient method whose only access to the feasible decision set, is through a linear optimization oracle (as opposed to other methods which require potentially much more computationally-expensive subprocedures, such as computing Euclidean projections). We present the first such algorithm that attains O(T3/4) expected regret using only O(T) overall calls to the linear optimization oracle, in expectation, where T is the number of prediction rounds. This improves over the O(T4/5) expected regret bound recently obtained by \citeKarbasi19, and actually matches the current best regret bound for projection-free online learning in the full information setting.