CaltechAUTHORS (California Institute of Technology) · 2019 · 47 citations · 16 references
Open access
ComputingComputer ScienceAlgorithmsMachine LearningOptimizationConvex OptimizationOnline AlgorithmsOptimal ControlOptimization For Machine LearningReinforcement LearningStochastic ControlCompetitive RatioLogistic RegressionOnline Convex OptimizationOnline Machine LearningOnline OptimizationOnline Stochastic OptimizationRidge Regression
We consider Online Convex Optimization (OCO) in the setting where the costs are mm-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.
16
Dynamic right-sizing for power-proportional data centers
Minghong Lin, Adam Wierman, Lachlan L. H. Andrew et al. · 2011 · 445 citations
Competitive algorithms for server problems
Mark S. Manasse, Lyle A. McGeoch, Daniel D. Sleator · Journal of Algorithms · 1990 · 431 citations
An optimal on-line algorithm for metrical task system
Allan Borodin, Nathan Linial, Michael Saks · Journal of the ACM · 1992 · 333 citations · Full text
Online algorithms for geographical load balancing
Minghong Lin, Zhenhua Liu, Adam Wierman et al. · 2012 · 300 citations · Full text
A polylog(<i>n</i>)-competitive algorithm for metrical task systems
Yair Bartal, Avrim Blum, Carl Burch et al. · 1997 · 89 citations · Full text