Temporal Variability in Implicit Online Learning

Nicolò Campolongo, Francesco Orabona

Introduction

In online learning, an agent makes a sequence of decisions ($x_t$), observes a loss function ($\ell_t$), and aims to minimize regret—the difference between their total loss and the loss of the best fixed decision in hindsight.

The standard approach, Online Mirror Descent (OMD), uses the gradient of the current loss to update the model. However, practitioners often prefer Implicit updates, which use the loss function directly to find a point that would have been good for the current round. While implicit methods often perform better in the real world, theoretical analyses have historically lumped them in with OMD, assigning them the same $O(\sqrt{T})$ regret bound.

This paper bridges the gap between the practical success of implicit online learning algorithms and their previously lackluster theoretical guarantees. The authors tackle a fundamental question: Why do implicit algorithms work so much better in practice than theory suggests? By introducing a metric called temporal variability, they prove that implicit algorithms can achieve constant regret in stable environments—a feat impossible for standard gradient-based methods. Furthermore, they provide a new adaptive algorithm, AdaImplicit, that automatically exploits "easy" data.

Methodology

The authors focus on Implicit Online Mirror Descent (IOMD). Unlike standard OMD, which linearizes the loss, IOMD solves a mini-optimization problem at each step:

$$x_{t+1} = \arg \min_{x \in V} B_\psi(x, x_t) + \eta_t \ell_t(x)$$

where $B_\psi$ is a distance measure (Bregman divergence) and $\eta_t$ is the learning rate.

To analyze this, the authors introduce two key methodological innovations:

  1. Temporal Variability ($V_T$): They define a metric that sums up the maximum possible change between consecutive loss functions. If the environment is static, $V_T$ is zero; if it changes slowly, $V_T$ is small.
  2. AdaImplicit Algorithm: They propose an adaptive version of IOMD. Instead of requiring the user to guess the "hardness" of the problem or the total variability $V_T$, AdaImplicit updates its learning rate on the fly based on the observed differences between the loss at the current point and the updated point.

The authors validated their theory using both synthetic 1D regression tasks (where the target follows a sine wave to create low but non-zero temporal variability) and real-world benchmarks from LIBSVM, including classification (covtype, cod-rna, phishing) and regression (abalone_scale, cpusmall_scale, cadata) datasets.

Key Insights & Results

The "Future" Gradient and Breaking the $O(\sqrt{T})$ Barrier

Implicit updates are essentially "proximal" updates. Mathematically, they are equivalent to taking a gradient step using the gradient at the new point ($x_{t+1}$) rather than the old one ($x_t$). This "future-looking" property makes the algorithm much more stable.

Standard gradient descent cannot achieve constant regret on non-smooth losses, even if the loss function never changes. This paper proves that IOMD can achieve constant regret if the temporal variability is constant. Specifically, the authors prove a regret bound of $O(V_T + 1)$ and provide a matching lower bound, proving that no deterministic algorithm can do better than $O(V_T)$.

Empirical Superiority in Slow-Varying Environments

In synthetic experiments designed to simulate slow-varying losses, AdaImplicit's cumulative loss grew significantly slower than standard Online Gradient Descent (OGD) and its adaptive counterpart (AdaOGD).

Cumulative loss over time for slow varying losses.

Hyperparameter Stability

A major practical insight from the empirical section is the robustness of implicit algorithms to hyperparameter choices. While many algorithms can reach the same minimum loss with perfect tuning, Implicit algorithms are far less sensitive to the choice of the learning rate parameter ($\beta$).

Average loss vs. learning rate parameter across multiple real-world datasets.

On real-world datasets, the "performance valleys" for AdaImplicit (plots of loss vs. learning rate) were much wider than for OGD. In a real-world streaming scenario where cross-validation to find the perfect learning rate is impossible, AdaImplicit's stability makes it a much safer and more reliable choice.

Limitations and Future Work

  • Computational Cost: Every step of an implicit algorithm requires solving an optimization problem. While closed-form solutions exist for common losses (like Hinge, Absolute, and Square loss), more complex loss functions might make IOMD computationally expensive compared to simple gradient steps.
  • Dynamic Competitors: This analysis focuses on static regret (comparing against the best single fixed decision). Extending this framework to dynamic regret (comparing against a sequence of varying decisions) is a natural next step.
  • Stochastic Settings: The paper primarily deals with adversarial settings. Exploring how temporal variability interacts with stochastic (noisy) data could yield further insights into the "easiness" of certain datasets and environments.

Summary updated

Abstract

In the setting of online learning, Implicit algorithms turn out to be highly successful from a practical standpoint. However, the tightest regret analyses only show marginal improvements over Online Mirror Descent. In this work, we shed light on this behavior carrying out a careful regret analysis. We prove a novel static regret bound that depends on the temporal variability of the sequence of loss functions, a quantity which is often encountered when considering dynamic competitors. We show, for example, that the regret can be constant if the temporal variability is constant and the learning rate is tuned appropriately, without the need of smooth losses. Moreover, we present an adaptive algorithm that achieves this regret bound without prior knowledge of the temporal variability and prove a matching lower bound. Finally, we validate our theoretical findings on classification and regression datasets.
BibTeX
@inproceedings{campolongo2020temporal,
  author = {Nicolò Campolongo and Francesco Orabona},
  title = {{Temporal Variability in Implicit Online Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=FO4KJfVtUgo},
}
Figure