Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses

Yihan Zhou, Victor S. Portella, Mark Schmidt, Nicholas J. A. Harvey

Introduction

In the realm of Online Convex Optimization (OCO), a player repeatedly selects points within a convex set while an adversary reveals a sequence of loss functions. The ultimate objective is to minimize regret—the difference between the player's accumulated loss and the loss they would have incurred by choosing the single best fixed point in hindsight.

Traditionally, proving that an algorithm achieves "sublinear" regret (which guarantees that the average regret approaches zero over time) relies heavily on the assumption that the loss functions are Lipschitz continuous. In simpler terms, the functions cannot be "too steep," meaning their gradients must be strictly bounded. However, this assumption breaks down in many practical scenarios where gradients can explode, such as in inverse Poisson problems or even simple quadratic functions ($x^2$) defined over an unbounded domain.

While researchers in offline convex optimization have recently circumvented this by developing "relative" notions of Lipschitzness and strong convexity—measuring steepness relative to a reference "mirror map" rather than a fixed norm—these concepts had not been fully translated to the online setting. This paper bridges that gap, proving that foundational OCO algorithms can achieve optimal regret bounds under these relaxed, relative assumptions.

The Relative Lipschitz Framework

To tackle functions with exploding gradients, the authors analyze two workhorse frameworks of online learning:

  1. Follow the Regularized Leader (FTRL): An algorithm that selects the point minimizing the sum of all past losses plus a regularizing stabilization term.
  2. Dual-Stabilized Online Mirror Descent (DS-OMD): A variant of standard mirror descent that incorporates an extra step in the "dual space" to prevent iterates from drifting too far when the problem's geometry is complex.

The core technical innovation of the paper is the application of the Relative Lipschitz condition to these online algorithms. Mathematically, a function is relative-Lipschitz if its gradient $g$ satisfies:

$$\langle g, x - y \rangle \leq L \sqrt{2D_R(y, x)}$$

where $D_R$ is a Bregman divergence (a generalized distance metric) associated with a reference function $R$. Instead of demanding that the gradient itself is small, this condition requires that the gradient is small relative to how much the reference function $R$ changes. By choosing a regularizer that matches the growth rate of the loss functions, algorithms can successfully optimize functions previously considered too unstable for standard OCO.

Key Theoretical Results

This purely theoretical work provides rigorous mathematical proofs that extend classical OCO performance to the relative setting. The key findings include:

  • Optimal Sublinear Regret: For relative-Lipschitz functions, both FTRL and DS-OMD achieve $O(\sqrt{T})$ regret. This perfectly matches the optimal rate historically reserved for classical Lipschitz functions.
  • First Logarithmic Regret in the Relative Setting: By utilizing Relative Strong Convexity (which replaces the standard squared-norm penalty with a Bregman divergence), the authors prove a regret bound of $O(\log T)$. This is a major milestone, as it represents the first time logarithmic regret—a marker of extremely efficient learning—has been demonstrated for relative-strongly convex functions in an online environment.
  • The Necessity of Dual Stabilization: The analysis reveals that for Online Mirror Descent, a "dual-stabilization" step is absolutely crucial. Without it, OMD can suffer linear regret (effectively failing to learn) if the learning rate is dynamic and the distance to the boundary of the feasible set is infinite.
  • Broad Generality: Because FTRL and OMD serve as "meta-algorithms," these bounds automatically apply to a vast family of specific algorithms, including Dual Averaging and AdaGrad-style methods, even when dealing with non-Lipschitz, composite losses (e.g., adversarial loss plus an $\ell_1$-norm penalty).

Limitations and Future Directions

While the paper significantly expands the boundaries of OCO, it notes a few inherent limitations. First, for a function to be simultaneously relative-Lipschitz and relative-strongly convex, the domain often requires boundedness constraints; if the Bregman divergence approaches infinity, these two properties can eventually contradict one another.

Furthermore, while the authors prove that these optimal bounds exist, they do not provide a universal recipe for selecting the perfect reference function ($R$) for a novel problem. Finding the optimal mirror map for specific classes of non-Lipschitz functions remains an open challenge for future research. Finally, the authors suggest that exploring the connections between this "relative" approach and other emerging geometric frameworks—such as Riemann-Lipschitz continuity—could yield even deeper insights into optimization over complex spaces.

Summary updated

Abstract

In online convex optimization (OCO), Lipschitz continuity of the functions is commonly assumed in order to obtain sublinear regret. Moreover, many algorithms have only logarithmic regret when these functions are also strongly convex. Recently, researchers from convex optimization proposed the notions of <code>relative Lipschitz continuity'' and</code>relative strong convexity''. Both of the notions are generalizations of their classical counterparts. It has been shown that subgradient methods in the relative setting have performance analogous to their performance in the classical setting. In this work, we consider OCO for relative Lipschitz and relative strongly convex functions. We extend the known regret bounds for classical OCO algorithms to the relative setting. Specifically, we show regret bounds for the follow the regularized leader algorithms and a variant of online mirror descent. Due to the generality of these methods, these results yield regret bounds for a wide variety of OCO algorithms. Furthermore, we further extend the results to algorithms with extra regularization such as regularized dual averaging.
BibTeX
@inproceedings{zhou2020regret,
  author = {Yihan Zhou and Victor S. Portella and Mark Schmidt and Nicholas J. A. Harvey},
  title = {{Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=OIXiRvZpBS},
}
Figure