# Non-Stationary Online Structured Prediction with Surrogate Losses

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 44 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Builds on (most cited first, 26 of 26)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution](https://mlsanity.com/paper/2205.04583/) (2022)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Structured Prediction with Projection Oracles](https://mlsanity.com/paper/1910.11369/) (2019)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions](https://mlsanity.com/paper/1504.05002/) (2015)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [Exploiting the Surrogate Gap in Online Multiclass Classification](https://mlsanity.com/paper/2007.12618/) (2020)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control](https://mlsanity.com/paper/2407.11760/) (2024)
- [Structured Prediction in Online Learning](https://mlsanity.com/paper/2406.12366/) (2024)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Bandit and Delayed Feedback in Online Structured Prediction](https://mlsanity.com/paper/2502.18709/) (2025)

## Abstract (arXiv)

Online structured prediction, including online classification as a special case, is the task of sequentially predicting labels from input features. In this setting, the surrogate regret -- the cumulative excess of the actual target loss (e.g., the 0-1 loss) over the surrogate loss (e.g., the logistic loss) incurred by the best fixed estimator -- has gained attention because it admits a finite bound independent of the time horizon T. However, such guarantees break down in non-stationary environments, where every fixed estimator may incur surrogate loss that grows linearly with T. To address this limitation, we obtain an upper bound of FT + O(1 + PT) on the cumulative target loss, where FT is the cumulative surrogate loss of any comparator sequence and PT is its path length. This bound depends on T only through FT and PT, thus offering stronger guarantees under non-stationarity. Our core idea is to combine the dynamic regret analysis of online gradient descent (OGD) with the exploit-the-surrogate-gap technique. This viewpoint sheds light on the usefulness of a Polyak-style learning rate for OGD, which systematically yields target-loss bounds and performs well empirically. We then extend our approach to broader settings beyond prior work via the convolutional Fenchel--Young loss. Finally, a lower bound shows that the dependence on FT and PT is tight.