# A Generalized Online Mirror Descent with Applications to Classification and Regression

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2013.

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

- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Learning Sparse Graphon Mean Field Games](https://mlsanity.com/paper/2209.03880/) (2022)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Delayed Bandits: When Do Intermediate Observations Help?](https://mlsanity.com/paper/2305.19036/) (2023)
- [Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad](https://mlsanity.com/paper/2403.02648/) (2024)
- [Cooperative Online Learning with Feedback Graphs](https://mlsanity.com/paper/2106.04982/) (2021)
- [Optimistic Optimisation of Composite Objective with Exponentiated Update](https://mlsanity.com/paper/2208.04065/) (2022)
- [Online Deep Learning from Doubly-Streaming Data](https://mlsanity.com/paper/2204.11793/) (2022)
- [Structured Directional Pruning via Perturbation Orthogonal Projection](https://mlsanity.com/paper/2107.05328/) (2021)
- [Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2208.04579/) (2022)
- [Adaptive Stochastic Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2211.11710/) (2022)
- [Online AUC Optimization Based on Second-order Surrogate Loss](https://mlsanity.com/paper/2510.21202/) (2025)
- [Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares](https://mlsanity.com/paper/2605.04364/) (2026)
- [Adam Converges in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2606.22326/) (2026)
- [A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning](https://mlsanity.com/paper/2610.14041/) (2026)

## Abstract (arXiv)

Online learning algorithms are fast, memory-efficient, easy to implement, and applicable to many prediction problems, including classification, regression, and ranking. Several online algorithms were proposed in the past few decades, some based on additive updates, like the Perceptron, and some on multiplicative updates, like Winnow. A unifying perspective on the design and the analysis of online algorithms is provided by online mirror descent, a general prediction strategy from which most first-order algorithms can be obtained as special cases. We generalize online mirror descent to time-varying regularizers with generic updates. Unlike standard mirror descent, our more general formulation also captures second order algorithms, algorithms for composite losses and algorithms for adaptive filtering. Moreover, we recover, and sometimes improve, known regret bounds as special cases of our analysis using specific regularizers. Finally, we show the power of our approach by deriving a new second order algorithm with a regret bound invariant with respect to arbitrary rescalings of individual features.