Gradient Equilibrium in Online Learning: Theory and Applications

Anastasios N. Angelopoulos, Michael I. Jordan, Ryan J. TibshiraniarXiv 2025 · DOI · arXiv

Introduction

Traditional online learning frameworks primarily focus on minimizing regret—the difference between the cumulative loss of an algorithm and that of the best fixed model in hindsight. While theoretically robust, the no-regret paradigm often misaligns with practical statistical objectives like long-run unbiasedness or calibrated coverage. Furthermore, achieving no-regret typically necessitates decaying learning rates, which can hinder a model's responsiveness in non-stationary environments.

This paper introduces Gradient Equilibrium (GEQ), a novel perspective that shifts the focus from loss minimization to ensuring that the average gradient along a sequence of predictions converges to zero. GEQ serves as a sequential analog to classical first-order optimality conditions, offering a framework that is often achievable with simple constant step sizes and directly translates to meaningful statistical properties.

The Gradient Equilibrium Framework

A sequence of iterates satisfies Gradient Equilibrium if the average gradient vanishes over time: $$\frac{1}{T} \sum_{t=1}^T g_t(\theta_t) \to 0$$ A critical insight of this work is that GEQ is distinct from No-Regret. One can achieve sublinear regret without satisfying GEQ, and conversely, GEQ can be attained even when regret remains linear. This distinction is vital because GEQ specifically targets the average direction of updates, ensuring that the model is not systematically biased in its predictions. For instance, under squared loss, GEQ implies long-run unbiasedness, while under quantile loss, it ensures exact coverage.

GEQ vs. No-Regret: The norm of bias (GEQ) can converge to zero even when the average regret does not, highlighting the independence of these two properties.

Methods and Implementation

The authors demonstrate that GEQ can be achieved using Online Gradient Descent (OGD) with constant step sizes, provided the loss functions exhibit "restorative" properties.

  1. Restorative Losses: If a loss function's negative gradient generally points toward the origin when parameters are far away, OGD naturally stays bounded and achieves GEQ.
  2. Regularization: For losses that are not inherently restorative (e.g., logistic loss), adding $\ell_1$ (Lasso) or $\ell_2$ (Ridge) penalties can induce the necessary restorative field.
  3. Post-hoc Debiasing: A practical application involves adjusting "black-box" model predictions. By applying OGD updates to the residuals of a pre-trained model, one can guarantee that the adjusted predictions remain unbiased over time, even under distribution shifts.

Experimental Results

The GEQ framework was evaluated across several domains, including clinical data (MIMIC-III), recidivism risk (COMPAS), and LLM evaluation (Chatbot Arena).

Multigroup Debiasing and Fairness

In experiments using the COMPAS dataset, the authors applied GEQ to ensure fairness across overlapping demographic groups (e.g., race and marital status). By treating each group's bias as a separate gradient component, the algorithm successfully drove the "norm of bias" to zero for all groups simultaneously.

Multigroup debiasing on the COMPAS dataset. The norm of bias converges toward zero across various demographic categories as iterations increase.

LLM Calibration and Elo Scores

The study also reveals that the standard Elo rating system used in LLM leaderboards is essentially an OGD algorithm achieving GEQ. On the Chatbot Arena dataset, GEQ ensures that win-rate predictions for individual models remain unbiased in the long run.

Discussion and Future Work

GEQ offers a compelling alternative to regret-based online learning, particularly for applications requiring statistical calibration and responsiveness to non-stationarity. While constant step sizes are effective, future work may explore more sophisticated step-size selection or ensembling methods. Additionally, extending the GEQ framework to full probabilistic calibration and highly non-convex landscapes, such as deep reinforcement learning, remains a promising direction for research.

Summary updated

Abstract

We present a new perspective on online learning that we refer to as gradient equilibrium: a sequence of iterates achieves gradient equilibrium if the average of gradients of losses along the sequence converges to zero. In general, this condition is not implied by, nor implies, sublinear regret. It turns out that gradient equilibrium is achievable by standard online learning methods such as gradient descent and mirror descent with constant step sizes (rather than decaying step sizes, as is usually required for no regret). Further, as we show through examples, gradient equilibrium translates into an interpretable and meaningful property in online prediction problems spanning regression, classification, quantile estimation, and others. Notably, we show that the gradient equilibrium framework can be used to develop a debiasing scheme for black-box predictions under arbitrary distribution shift, based on simple post hoc online descent updates. We also show that post hoc gradient updates can be used to calibrate predicted quantiles under distribution shift, and that the framework leads to unbiased Elo scores for pairwise preference prediction.
BibTeX
@misc{angelopoulos2025gradient,
  author = {Anastasios N. Angelopoulos and Michael I. Jordan and Ryan J. Tibshirani},
  title = {{Gradient Equilibrium in Online Learning: Theory and Applications}},
  year = {2025},
  eprint = {2501.08330},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.08330},
}
Figure