mlsanityData to 7 Oct 2026

Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond

arXiv 2201.08905 ↗First posted 21 Jan 2022cs.LG math.OC stat.MLcited by 27

Not on the map. Why?

Abstract (arXiv)

We study the framework of universal dynamic regret minimization with strongly convex losses. We answer an open problem in Baby and Wang 2021 by showing that in a proper learning setup, Strongly Adaptive algorithms can achieve the near optimal dynamic regret of tilde O(d1/3 n1/3TV[u1:n]2/3 vee d) against any comparator sequence u1,ldots,un simultaneously, where n is the time horizon and TV[u1:n] is the Total Variation of comparator. These results are facilitated by exploiting a number of new structures imposed by the KKT conditions that were not considered in Baby and Wang 2021 which also lead to other improvements over their results such as: (a) handling non-smooth losses and (b) improving the dimension dependence on regret. Further, we also derive near optimal dynamic regret rates for the special case of proper online learning with exp-concave losses and an L_∞ constrained decision set.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 26 of its 42 references that are in the map. First posted on arXiv 21 Jan 2022.

Builds on

26 of 42 references.

References · 26

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2013Non-stationary Stochastic Optimizationcited by 173
  3. 2018Adaptive Online Learning in Dynamic Environmentscited by 130
  4. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  5. 2015Strongly Adaptive Online Learningcited by 102
  6. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  7. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  8. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 65
  9. 2016Improved Strongly Adaptive Online Learning using Coin Bettingcited by 48
  10. 2013Adaptive piecewise polynomial estimation via trend filteringcited by 47
  11. 2014Trend Filtering on Graphscited by 45
  12. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
14 more
  1. 2020Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functionscited by 33
  2. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  3. 2019Online Forecasting of Total-Variation-bounded Sequencescited by 30
  4. 2018Smoothed Online Optimization for Regression and Controlcited by 26
  5. 2015A Chaining Algorithm for Online Nonparametric Regressioncited by 16
  6. 2019Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functionscited by 15
  7. 2019Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyondcited by 12
  8. 2020Adaptive Online Estimation of Piecewise Polynomial Trendscited by 11
  9. 2016Online Isotonic Regressioncited by 9
  10. 2021An Optimal Reduction of TV-Denoising to Adaptive Online Learningcited by 9
  11. 2014The Falling Factorial Basis and Its Statistical Applicationscited by 8
  12. 2019Prediction bounds for higher order total variation regularized least squarescited by 7
  13. 2017Non-stationary Stochastic Optimization under Lp,q-Variation Measurescited by 5
  14. 2021Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRRcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 8; 2024: 6; 2025: 4; 2026: 4.

27 papers.

Sort:

  1. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  2. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  3. 2023Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guaranteescited by 13
  4. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  5. 2022On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedbackcited by 11
  6. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  7. 2023Online Label Shift: Optimal Dynamic Regret meets Practical Algorithmscited by 11
  8. 2024Online Linear Regression in Dynamic Environments via Discountingcited by 10
  9. 2023A Stability Principle for Learning under Non-Stationaritycited by 9
  10. 2022Second Order Path Variationals in Non-Stationary Online Learningcited by 7
  11. 2022Optimal Dynamic Regret in LQR Controlcited by 6
  12. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
15 more
  1. 2025Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixabilitycited by 6
  2. 2026Self-Evolving Agents with Anytime-Valid Certificatescited by 6
  3. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  4. 2025Learning to Bid in Non-Stationary Repeated First-Price Auctionscited by 5
  5. 2023Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problemscited by 4
  6. 2023Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Settingcited by 3
  7. 2022On the Computational Efficiency of Adaptive and Dynamic Regret Minimizationcited by 2
  8. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 2
  9. 2024Adaptive Regret for Bandits Made Possible: Two Queries Sufficecited by 1
  10. 2024Online Feature Updates Improve Online (Generalized) Label Shift Adaptationcited by 1
  11. 2024Tracking solutions of time-varying variational inequalitiescited by 1
  12. 2025Adaptive Estimation and Learning under Temporal Distribution Shiftcited by 1
  13. 2025Non-stationary Bandit Convex Optimization: A Comprehensive Studycited by 1
  14. 2026From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequencescited by 0
  15. 2026On the Relation Between Interval Regret and Dynamic Regretcited by 0