Non-Stationary Online Structured Prediction with Surrogate Losses

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 $F_T+O(1+P_T)$ on the cumulative target loss, where $F_T$ is the cumulative surrogate loss of any comparator sequence and $P_T$ is its *path length*. This bound depends on $T$ only through $F_T$ and $P_T$, 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 $F_T$ and $P_T$ is tight.

Online structured prediction is a framework for repeatedly making predictions from input data. However, in non-stationary environments, where data trends change over time, existing theoretical guarantees based on a single fixed estimator can become uninformative. In this work, we show that the learner's cumulative target loss can be bounded by how well a changing sequence of estimators fits the data in terms of surrogate loss, together with how much that sequence changes over time. In particular, we prove that the cumulative target loss can remain small even in non-stationary environments when there exists a sequence of estimators with small surrogate loss and limited path length. We also propose a learning-rate schedule that improves learning efficiency and demonstrate through experiments that it works effectively in practice.