Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization

Abstract

We study online convex optimization in a setting where the learner seeks to minimize the sum of a per-round hitting cost and a movement cost which is incurred when changing decisions between rounds. We prove a new lower bound on the competitive ratio of any online algorithm in the setting where the costs are $m$-strongly convex and the movement costs are the squared ${\ell }_2$ norm. This lower bound shows that no algorithm can achieve a competitive ratio that is $o(m^{-1/2})$ as $m$ tends to zero. No existing algorithms have competitive ratios matching this bound, and we show that the state-of-the-art algorithm, Online Balanced Decent (OBD), has a competitive ratio that is $\Omega (m^{-2/3})$. We additionally propose two new algorithms, Greedy OBD (G-OBD) and Regularized OBD (R-OBD) and prove that both algorithms have an $O(m^{-1/2})$ competitive ratio. The result for G-OBD holds when the hitting costs are quasiconvex and the movement costs are the squared ${\ell }_2$ norm, while the result for R-OBD holds when the hitting costs are $m$-strongly convex and the movement costs are Bregman Divergences. Further, we show that R-OBD simultaneously achieves constant, dimension-free competitive ratio and sublinear regret when hitting costs are strongly convex.

References in corpus (2)

• Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization
• Potential-Function Proofs for First-Order Methods

Cited by in corpus (11)

• Online Optimization with Memory and Competitive Control
• Non-stationary Online Learning with Memory and Non-stochastic Control
• Regret-optimal control in dynamic environments
• Regret-optimal measurement-feedback control
• Revisiting Smoothed Online Learning
• Expert-Calibrated Learning for Online Optimization with Switching Costs
• Chasing Convex Bodies with Linear Competitive Ratio
• Lazy OCO: Online Convex Optimization on a Switching Budget
• Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory
• Proximal Algorithms for Smoothed Online Convex Optimization with Predictions