# Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor

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

## 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 (most cited first, 30 of 35)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Thinking Fast and Slow: Optimization Decomposition Across Timescales](https://mlsanity.com/paper/1704.07785/) (2017)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions](https://mlsanity.com/paper/1906.10851/) (2019)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Online Learning for Changing Environments using Coin Betting](https://mlsanity.com/paper/1711.02545/) (2017)
- [Online Optimization with Predictions and Non-convex Losses](https://mlsanity.com/paper/1911.03827/) (2019)
- [Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms](https://mlsanity.com/paper/2011.12539/) (2020)

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

- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization](https://mlsanity.com/paper/2311.00181/) (2023)
- [Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval](https://mlsanity.com/paper/2505.19491/) (2025)
- [Partially Lazy Gradient Descent for Smoothed Online Learning](https://mlsanity.com/paper/2601.15984/) (2026)
- [Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2509.05930/) (2025)
- [Dynamic Regret in Online Convex Optimization with Indicator Switching Costs](https://mlsanity.com/paper/2609.30556/) (2026)

## 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.