# PDE-Based Optimal Strategy for Unconstrained Online Learning

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 63 references that are in the map.
- First posted on arXiv 19 Jan 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [Combining Online Learning Guarantees](https://mlsanity.com/paper/1902.09003/) (2019)
- [Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting](https://mlsanity.com/paper/2006.07507/) (2020)
- [Prediction with Expert Advice: a PDE Perspective](https://mlsanity.com/paper/1904.11401/) (2019)
- [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 Convex Optimization with Unconstrained Domains and Losses](https://mlsanity.com/paper/1703.02622/) (2017)
- [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)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Minimax Optimal Algorithms for Unconstrained Linear Optimization](https://mlsanity.com/paper/1302.2176/) (2013)
- [On the asymptotic optimality of the comb strategy for prediction with expert advice](https://mlsanity.com/paper/1902.02368/) (2019)
- [A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts](https://mlsanity.com/paper/2007.12732/) (2020)
- [New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice](https://mlsanity.com/paper/1912.03132/) (2019)
- [Malicious Experts versus the multiplicative weights algorithm in online prediction](https://mlsanity.com/paper/2003.08457/) (2020)
- [Online Prediction With History-Dependent Experts: The General Case](https://mlsanity.com/paper/2008.00052/) (2020)
- [PDE approach to the problem of online prediction with expert advice: a construction of potential-based strategies](https://mlsanity.com/paper/1705.01091/) (2017)
- [A Differential Equations Approach to Optimizing Regret Trade-offs](https://mlsanity.com/paper/1305.1359/) (2013)
- [Parameter-Free Locally Differentially Private Stochastic Subgradient Descent](https://mlsanity.com/paper/1911.09564/) (2019)

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

- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Optimal Linear Decay Learning Rate Schedules and Further Refinements](https://mlsanity.com/paper/2310.07831/) (2023)
- [Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation](https://mlsanity.com/paper/2303.12277/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learning](https://mlsanity.com/paper/2405.16642/) (2024)
- [Discounted Adaptive Online Learning: Towards Better Regularization](https://mlsanity.com/paper/2402.02720/) (2024)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [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)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [Efficient and Optimal Fixed-Time Regret with Two Experts](https://mlsanity.com/paper/2203.07577/) (2022)
- [A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit](https://mlsanity.com/paper/2202.05767/) (2022)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [A New Approach to Drifting Games, Based on Asymptotically Optimal Potentials](https://mlsanity.com/paper/2207.11405/) (2022)
- [Parameter-free projected gradient descent](https://mlsanity.com/paper/2305.19605/) (2023)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [A PDE approach for regret bounds under partial monitoring](https://mlsanity.com/paper/2209.01256/) (2022)
- [State-free Reinforcement Learning](https://mlsanity.com/paper/2409.18439/) (2024)
- [Reasoning without Regret](https://mlsanity.com/paper/2504.09777/) (2025)
- [Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs](https://mlsanity.com/paper/2602.06545/) (2026)
- [A Perturbation Approach to Unconstrained Linear Bandits](https://mlsanity.com/paper/2603.28201/) (2026)
- [Clipping the Price of Adaptivity at the Tail](https://mlsanity.com/paper/2606.22669/) (2026)

## Abstract (arXiv)

Unconstrained Online Linear Optimization (OLO) is a practical problem setting to study the training of machine learning models. Existing works proposed a number of potential-based algorithms, but in general the design of these potential functions relies heavily on guessing. To streamline this workflow, we present a framework that generates new potential functions by solving a Partial Differential Equation (PDE). Specifically, when losses are 1-Lipschitz, our framework produces a novel algorithm with anytime regret bound C√T+||u||√2T[√log(1+||u||/C)+2], where C is a user-specified constant and u is any comparator unknown and unbounded a priori. Such a bound attains an optimal loss-regret trade-off without the impractical doubling trick. Moreover, a matching lower bound shows that the leading order term, including the constant multiplier √2, is tight. To our knowledge, the proposed algorithm is the first to achieve such optimalities.