2018/10/23 by Gautam Goel, Adam Wierman, Goel, Gautam +1 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1810.10132
openalex publication_date 2018/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider Online Convex Optimization (OCO) in the setting where the costs are m-strongly convex and the online learner pays a switching cost for changing decisions between rounds. We show that the recently proposed Online Balanced Descent (OBD) algorithm is constant competitive in this setting, with competitive ratio 3 + O(1/m), irrespective of the ambient dimension. Additionally, we show that when the sequence of cost functions is ε-smooth, OBD has near-optimal dynamic regret and maintains strong per-round accuracy. We demonstrate the generality of our approach by showing that the OBD framework can be used to construct competitive algorithms for a variety of online problems across learning and control, including online variants of ridge regression, logistic regression, maximum likelihood estimation, and LQR control.