mlsanityData to 14 Oct 2026

Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor

arXiv 2205.00741 ↗First posted 2 May 2022cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

In this paper, we investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO), in which the learner needs to minimize not only the hitting cost but also the switching cost. In the setting of learning with expert advice, Daniely and Mansour (2019) demonstrate that Discounted-Normal-Predictor can be utilized to yield nearly optimal regret bounds over any interval, even in the presence of switching costs. Inspired by their results, we develop a simple algorithm for SOCO: Combining online gradient descent (OGD) with different step sizes sequentially by Discounted-Normal-Predictor. Despite its simplicity, we prove that it is able to minimize the adaptive regret with switching cost, i.e., attaining nearly optimal regret with switching cost on every interval. By exploiting the theoretical guarantee of OGD for dynamic regret, we further show that the proposed algorithm can minimize the dynamic regret with switching cost in every interval.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 35 of its 77 references that are in the map. First posted on arXiv 2 May 2022.

Builds on

35 of 77 references.

References · 35

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2013Non-stationary Stochastic Optimizationcited by 175
  3. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  4. 2018Adaptive Online Learning in Dynamic Environmentscited by 133
  5. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 125
  6. 2015Strongly Adaptive Online Learningcited by 107
  7. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  8. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  9. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 66
  10. 2017Thinking Fast and Slow: Optimization Decomposition Across Timescalescited by 60
  11. 2016Improved Strongly Adaptive Online Learning using Coin Bettingcited by 50
  12. 2016Improved Dynamic Regret for Non-degenerate Functionscited by 46
23 more
  1. 2013Dynamical Models and Tracking Regret in Online Convex Programmingcited by 43
  2. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 40
  3. 2020Adaptive Regret for Control of Time-Varying Dynamicscited by 38
  4. 2018Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descentcited by 33
  5. 2020Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functionscited by 33
  6. 2019Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimizationcited by 31
  7. 2020Minimizing Dynamic Regret and Adaptive Regret Simultaneouslycited by 31
  8. 2021Revisiting Smoothed Online Learningcited by 29
  9. 2018Smoothed Online Optimization for Regression and Controlcited by 26
  10. 2019Adaptive Regret of Convex and Smooth Functionscited by 24
  11. 2018Chasing Nested Convex Bodies Nearly Optimallycited by 21
  12. 2019Chasing Convex Bodies Optimallycited by 18
  13. 2019Chasing Convex Bodies with Linear Competitive Ratiocited by 15
  14. 2019Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functionscited by 15
  15. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
  16. 2017Online Learning for Changing Environments using Coin Bettingcited by 13
  17. 2019Online Optimization with Predictions and Non-convex Lossescited by 12
  18. 2020Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithmscited by 12
  19. 2018A Nearly-Linear Bound for Chasing Nested Convex Bodiescited by 9
  20. 2017Nested Convex Bodies are Chaseablecited by 8
  21. 2020Dimension-Free Bounds on Chasing Convex Functionscited by 8
  22. 2018Competitively Chasing Convex Bodiescited by 7
  23. 2019Understand Dynamic Regret with Switching Cost for Online Decision Makingcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 0; 2025: 2; 2026: 2.

6 papers.

  1. 2023Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guaranteescited by 13
  2. 2023Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimizationcited by 2
  3. 2025Discounted Online Convex Optimization: Uniform Regret Across a Continuous Intervalcited by 2
  4. 2026Partially Lazy Gradient Descent for Smoothed Online Learningcited by 2
  5. 2025Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithmscited by 0
  6. 2026Dynamic Regret in Online Convex Optimization with Indicator Switching Costscited by 0