# Dynamical Models and Tracking Regret in Online Convex Programming

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jan 2013.

## Built on by (most cited first, 30 of 43)

- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Non-Stationary Learning of Neural Networks with Automatic Soft Parameter Reset](https://mlsanity.com/paper/2411.04034/) (2024)
- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [Efficient Methods for Non-stationary Online Learning](https://mlsanity.com/paper/2309.08911/) (2023)
- [A closer look at temporal variability in dynamic online learning](https://mlsanity.com/paper/2102.07666/) (2021)
- [Adaptive Online Learning of Quantum States](https://mlsanity.com/paper/2206.00220/) (2022)
- [Learning to Optimize in Model Predictive Control](https://mlsanity.com/paper/2212.02603/) (2022)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [Learning Sampling Distributions for Model Predictive Control](https://mlsanity.com/paper/2212.02587/) (2022)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022)
- [Online Continual Adaptation with Active Self-Training](https://mlsanity.com/paper/2106.06526/) (2021)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [Regret Analysis of Learning-Based MPC with Partially-Unknown Cost Function](https://mlsanity.com/paper/2108.02307/) (2021)
- [Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems](https://mlsanity.com/paper/2209.01608/) (2022)
- [On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization](https://mlsanity.com/paper/2301.09808/) (2023)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [Online Convex Optimization with Switching Cost and Delayed Gradients](https://mlsanity.com/paper/2310.11880/) (2023)
- [Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions](https://mlsanity.com/paper/2202.12843/) (2022)
- [Online Nonconvex Bilevel Optimization with Bregman Divergences](https://mlsanity.com/paper/2409.10470/) (2024)
- [A Unified Analysis Method for Online Optimization in Normed Vector Space](https://mlsanity.com/paper/2112.12134/) (2021)
- [Regret Analysis of Online Gradient Descent-based Iterative Learning Control with Model Mismatch](https://mlsanity.com/paper/2204.04722/) (2022)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)
- [Prediction techniques for dynamic imaging with online primal-dual methods](https://mlsanity.com/paper/2405.02497/) (2024)
- [Preparing for Black Swans: The Antifragility Imperative for Machine Learning](https://mlsanity.com/paper/2405.11397/) (2024)

## Abstract (arXiv)

This paper describes a new online convex optimization method which incorporates a family of candidate dynamical models and establishes novel tracking regret bounds that scale with the comparator's deviation from the best dynamical model in this family. Previous online optimization methods are designed to have a total accumulated loss comparable to that of the best comparator sequence, and existing tracking or shifting regret bounds scale with the overall variation of the comparator sequence. In many practical scenarios, however, the environment is nonstationary and comparator sequences with small variation are quite weak, resulting in large losses. The proposed Dynamic Mirror Descent method, in contrast, can yield low regret relative to highly variable comparator sequences by both tracking the best dynamical model and forming predictions based on that model. This concept is demonstrated empirically in the context of sequential compressive observations of a dynamic scene and tracking a dynamic social network.