# Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 31 Oct 2023.

## Builds on (most cited first, 18 of 18)

- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Thinking Fast and Slow: Optimization Decomposition Across Timescales](https://mlsanity.com/paper/1704.07785/) (2017)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Analysis of the Optimization Landscape of Linear Quadratic Gaussian (LQG) Control](https://mlsanity.com/paper/2102.04393/) (2021)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems](https://mlsanity.com/paper/2106.10497/) (2021)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Chasing Convex Bodies and Functions with Black-Box Advice](https://mlsanity.com/paper/2206.11780/) (2022)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [Robustness and Consistency in Linear Quadratic Control with Untrusted Predictions](https://mlsanity.com/paper/2106.09659/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)

## Built on by (most cited first, 2 of 2)

- [The SMART approach to instance-optimal online learning](https://mlsanity.com/paper/2402.17720/) (2024)
- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)

## Abstract (arXiv)

We study the smoothed online quadratic optimization (SOQO) problem where, at each round t, a player plays an action xt in response to a quadratic hitting cost and an additional squared ℓ2-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management, where switching-efficient algorithms are highly sought after. We study the SOQO problem in both adversarial and stochastic settings, and in this process, perform the first stochastic analysis of this class of problems. We provide the online optimal algorithm when the minimizers of the hitting cost function evolve as a general stochastic process, which, for the case of martingale process, takes the form of a distribution-agnostic dynamic interpolation algorithm (LAI). Next, we present the stochastic-adversarial trade-off by proving an Omega(T) expected regret for the adversarial optimal algorithm in the literature (ROBD) with respect to LAI and, a sub-optimal competitive ratio for LAI in the adversarial setting. Finally, we present a best-of-both-worlds algorithm that obtains a robust adversarial performance while simultaneously achieving a near-optimal stochastic performance.