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

arXiv: https://arxiv.org/abs/1905.12776 · HTML: https://mlsanity.com/paper/1905.12776/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

## Built on by (most cited first, 30 of 31)

- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Regret-optimal Estimation and Control](https://mlsanity.com/paper/2106.12097/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Competitive Control](https://mlsanity.com/paper/2107.13657/) (2021)
- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [Expert-Calibrated Learning for Online Optimization with Switching Costs](https://mlsanity.com/paper/2204.08572/) (2022)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [Best of Both Worlds in Online Control: Competitive Ratio and Policy Regret](https://mlsanity.com/paper/2211.11219/) (2022)
- [Online Optimization with Feedback Delay and Nonlinear Switching Cost](https://mlsanity.com/paper/2111.00095/) (2021)
- [Near-Optimal Adversarial Reinforcement Learning with Switching Costs](https://mlsanity.com/paper/2302.04374/) (2023)
- [Robustified Learning for Online Optimization with Memory Costs](https://mlsanity.com/paper/2305.00677/) (2023)
- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)
- [Online Convex Optimization with Switching Cost and Delayed Gradients](https://mlsanity.com/paper/2310.11880/) (2023)
- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization](https://mlsanity.com/paper/2311.00181/) (2023)
- [Partially Lazy Gradient Descent for Smoothed Online Learning](https://mlsanity.com/paper/2601.15984/) (2026)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Online Learning for Equilibrium Pricing in Markets under Incomplete Information](https://mlsanity.com/paper/2303.11522/) (2023)
- [Learning-Augmented Decentralized Online Convex Optimization in Networks](https://mlsanity.com/paper/2306.10158/) (2023)
- [Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation](https://mlsanity.com/paper/2507.04133/) (2025)
- [Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost](https://mlsanity.com/paper/2403.17480/) (2024)
- [Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2509.05930/) (2025)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)

## Abstract (arXiv)

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 ℓ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 ℓ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.