mlsanityData to 14 Oct 2026

PDE-Based Optimal Strategy for Unconstrained Online Learning

arXiv 2201.07877 ↗First posted 19 Jan 2022cs.LGcited by 27

Not on the map. Why?

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.

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

26 of 63 references.

References · 26

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  3. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  4. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 125
  5. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  6. 2014Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximationscited by 46
  7. 2017Online Learning Without Prior Informationcited by 36
  8. 2014Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learningcited by 27
  9. 2019Combining Online Learning Guaranteescited by 22
  10. 2020Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Bettingcited by 19
  11. 2019Prediction with Expert Advice: a PDE Perspectivecited by 17
  12. 2019New Potential-Based Bounds for Prediction with Expert Advicecited by 16
14 more
  1. 2020Optimal anytime regret with two expertscited by 16
  2. 2017Online Convex Optimization with Unconstrained Domains and Lossescited by 14
  3. 2018Online Learning: Sufficient Statistics and the Burkholder Methodcited by 14
  4. 2019Finite-Time 4-Expert Prediction Problemcited by 14
  5. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
  6. 2013Minimax Optimal Algorithms for Unconstrained Linear Optimizationcited by 12
  7. 2019On the asymptotic optimality of the comb strategy for prediction with expert advicecited by 10
  8. 2020A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Expertscited by 7
  9. 2019New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advicecited by 6
  10. 2020Malicious Experts versus the multiplicative weights algorithm in online predictioncited by 6
  11. 2020Online Prediction With History-Dependent Experts: The General Casecited by 6
  12. 2017PDE approach to the problem of online prediction with expert advice: a construction of potential-based strategiescited by 4
  13. 2013A Differential Equations Approach to Optimizing Regret Trade-offscited by 2
  14. 2019Parameter-Free Locally Differentially Private Stochastic Subgradient Descentcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 9; 2024: 6; 2025: 3; 2026: 3.

27 papers.

Sort:

By area:

  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 133
  2. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
  3. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  4. 2023Optimal Linear Decay Learning Rate Schedules and Further Refinementscited by 43
  5. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  6. 2023Normalized Gradients for Allcited by 20
  7. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 17
  8. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  9. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  10. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  11. 2024Fully Unconstrained Online Learningcited by 10
  12. 2022Optimal Comparator Adaptive Online Learning with Switching Costcited by 9
15 more
  1. 2023Improving Adaptive Online Learning Using Refined Discretizationcited by 8
  2. 2022Continuous Prediction with Experts' Advicecited by 7
  3. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
  4. 2022Efficient and Optimal Fixed-Time Regret with Two Expertscited by 5
  5. 2022A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Banditcited by 3
  6. 2025Sparsity-Based Interpolation of External, Internal and Swap Regretcited by 3
  7. 2022A New Approach to Drifting Games, Based on Asymptotically Optimal Potentialscited by 2
  8. 2023Parameter-free projected gradient descentcited by 2
  9. 2025Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applicationscited by 1
  10. 2022A PDE approach for regret bounds under partial monitoringcited by 0
  11. 2024State-free Reinforcement Learningcited by 0
  12. 2025Reasoning without Regretcited by 0
  13. 2026Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffscited by 0
  14. 2026A Perturbation Approach to Unconstrained Linear Banditscited by 0
  15. 2026Clipping the Price of Adaptivity at the Tailcited by 0