mlsanityData to 14 Oct 2026

Online Optimization : Competing with Dynamic Comparators

arXiv 1501.06225 ↗First posted 26 Jan 2015cs.LG math.OC stat.MLcited by 99

Not on the map. Why?

Abstract (arXiv)

Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we address these two directions together. We present a fully adaptive method that competes with dynamic benchmarks in which regret guarantee scales with regularity of the sequence of cost functions and comparators. Notably, the regret bound adapts to the smaller complexity measure in the problem environment. Finally, we apply our results to drifting zero-sum, two-player games where both players achieve no regret guarantees against best sequences of actions in hindsight.

Key facts. Cited by 99 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 Jan 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 19; 2022: 20; 2023: 24; 2024: 9; 2025: 11; 2026: 15.

99 papers.

Sort:

By area:

  1. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  2. 2022Parameter-free Mirror Descentcited by 45
  3. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 40
  4. 2021Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraintscited by 39
  5. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  6. 2021Revisiting Smoothed Online Learningcited by 29
  7. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 28
  8. 2022Adapting to Online Label Shift with Provable Guaranteescited by 26
  9. 2022Learning Predictions for Algorithms with Predictionscited by 25
  10. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  11. 2023Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimizationcited by 22
  12. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
38 more
  1. 2025Lightweight Online Adaption for Time Series Foundation Model Forecastscited by 16
  2. 2021Stochastic Optimization under Distributional Driftcited by 15
  3. 2022Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methodscited by 15
  4. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  5. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
  6. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  7. 2021A closer look at temporal variability in dynamic online learningcited by 13
  8. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  9. 2023Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guaranteescited by 13
  10. 2024Model Assessment and Selection under Temporal Distribution Shiftcited by 12
  11. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  12. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  13. 2023Online Label Shift: Optimal Dynamic Regret meets Practical Algorithmscited by 11
  14. 2024An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraintscited by 11
  15. 2021Regret-optimal Estimation and Controlcited by 10
  16. 2022Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Driftcited by 10
  17. 2023A Stability Principle for Learning under Non-Stationaritycited by 10
  18. 2021An Optimal Reduction of TV-Denoising to Adaptive Online Learningcited by 9
  19. 2021Robust Bandit Learning with Imperfect Contextcited by 8
  20. 2021Online Continual Adaptation with Active Self-Trainingcited by 8
  21. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  22. 2022Second Order Path Variationals in Non-Stationary Online Learningcited by 7
  23. 2022Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum Statescited by 7
  24. 2023Learning Rate Schedules in the Presence of Distribution Shiftcited by 7
  25. 2021An Online Learning Approach to Optimizing Time-Varying Costs of AoIcited by 6
  26. 2022Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environmentscited by 6
  27. 2022Smoothed Online Convex Optimization Based on Discounted-Normal-Predictorcited by 6
  28. 2022Optimal Dynamic Regret in LQR Controlcited by 6
  29. 2023Minimizing Dynamic Regret on Geodesic Metric Spacescited by 6
  30. 2023Online Submodular Maximization via Online Convex Optimizationcited by 6
  31. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  32. 2024Multi-level Traffic-Responsive Tilt Camera Surveillance through Predictive Correlated Online Learningcited by 6
  33. 2022On Efficient Online Imitation Learning via Classificationcited by 5
  34. 2025Learning to Bid in Non-Stationary Repeated First-Price Auctionscited by 5
  35. 2025On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruningcited by 5
  36. 2025Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgerycited by 5
  37. 2021Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRRcited by 4
  38. 2023Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problemscited by 4

50 most cited of 99 All 99 (JSON)