# Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 6 Feb 2026.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Prediction with Expert Advice: a PDE Perspective](https://mlsanity.com/paper/1904.11401/) (2019)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [New Potential-Based Bounds for Prediction with Expert Advice](https://mlsanity.com/paper/1911.01641/) (2019)
- [Optimal anytime regret with two experts](https://mlsanity.com/paper/2002.08994/) (2020)
- [Online Learning: Sufficient Statistics and the Burkholder Method](https://mlsanity.com/paper/1803.07617/) (2018)
- [Finite-Time 4-Expert Prediction Problem](https://mlsanity.com/paper/1911.10936/) (2019)
- [Towards Optimal Algorithms for Prediction with Expert Advice](https://mlsanity.com/paper/1409.3040/) (2014)
- [Tight Lower Bounds for Multiplicative Weights Algorithmic Families](https://mlsanity.com/paper/1607.02834/) (2016)
- [Improving Adaptive Online Learning Using Refined Discretization](https://mlsanity.com/paper/2309.16044/) (2023)
- [Continuous Prediction with Experts' Advice](https://mlsanity.com/paper/2206.00236/) (2022)
- [Efficient and Optimal Fixed-Time Regret with Two Experts](https://mlsanity.com/paper/2203.07577/) (2022)
- [Eventually LIL Regret: Almost Sure lnln T Regret for a sub-Gaussian Mixture on Unbounded Data](https://mlsanity.com/paper/2512.12325/) (2025)

## Abstract (arXiv)

Adversarial online linear optimization (OLO) is essentially about making performance tradeoffs with respect to the unknown difficulty of the adversary. In the setting of one-dimensional fixed-time OLO on a bounded domain, it has been observed since Cover (1966) that achievable tradeoffs are governed by probabilistic inequalities, and these descriptive results can be converted into algorithms via dynamic programming, which, however, is not computationally efficient. We address this limitation by showing that Stein's method, a classical framework underlying the proofs of probabilistic limit theorems, can be operationalized as computationally efficient OLO algorithms. The associated regret and total loss upper bounds are "additively sharp", meaning that they surpass the conventional big-O optimality and match normal-approximation-based lower bounds by additive lower order terms. Our construction is inspired by the remarkably clean proof of a Wasserstein martingale central limit theorem (CLT) due to R"ollin (2018). Several concrete benefits can be obtained from this general technique. First, with the same computational complexity, the proposed algorithm improves upon the total loss upper bounds of online gradient descent (OGD) and multiplicative weight update (MWU). Second, our algorithm can realize a continuum of optimal two-point tradeoffs between the total loss and the maximum regret over comparators, improving upon prior works in parameter-free online learning. Third, by allowing the adversary to randomize on an unbounded support, we achieve sharp in-expectation performance guarantees for OLO with noisy feedback.