Efficient online algorithms for fast-rate regret bounds under sparsity

Pierre Gaillard, Olivier Wintenberger

Abstract: We consider the online convex optimization problem. In the setting of arbitrary sequences and finite set of parameters, we establish a new fast-rate quantile regret bound. Then we investigate the optimization into the L1-ball by discretizing the parameter space. Our algorithm is projection free and we propose an efficient solution by restarting the algorithm on adaptive discretization grids. In the adversarial setting, we develop an algorithm that achieves several rates of convergence with different dependencies on the sparsity of the objective. In the i.i.d. setting, we establish new risk bounds that are adaptive to the sparsity of the problem and to the regularity of the risk (ranging from a rate $1/\sqrt{T}$ for general convex risk to $1/T$ for strongly convex risk). These results generalize previous works on sparse online learning. They are obtained under a weak assumption on the risk (Łojasiewicz's assumption) that allows multiple optima which is crucial when dealing with degenerate situations.

Introduction

In online convex optimization (OCO), the primary objective is to minimize "regret"—the cumulative difference between a learner's performance and that of the best fixed strategy in hindsight. While standard algorithms like Hedge or Exponentiated Gradient are robust, they typically converge at a rate of $O(1/\sqrt{T})$. In modern high-dimensional applications, this "slow" rate is often insufficient. Furthermore, many existing fast-rate algorithms require expensive projections onto the $\ell_1$-ball at every iteration, creating a computational bottleneck when the number of features $d$ is large.

In their research, Pierre Gaillard and Olivier Wintenberger introduce two novel algorithms, BOA+ and SABOA, designed to achieve "fast-rate" regret bounds (approaching $O(1/T)$) by exploiting the inherent sparsity of high-dimensional data. These algorithms are projection-free and utilize adaptive discretization to maintain efficiency in both adversarial and i.i.d. settings.

Adaptive Discretization and Projection-Free Efficiency

The core innovation of this work lies in the shift from continuous optimization to a grid-based approach. Instead of optimizing over a continuous parameter space, the authors utilize a dynamic grid of "experts." This approach bypasses the need for $O(d^2)$ or $O(d^3)$ projection steps required by traditional gradient-descent variants.

BOA+ (Adversarial Setting)

For data sequences that may be chosen by an adversary, the authors propose BOA+. This algorithm employs a "doubling trick," dividing time into discrete sessions. At the start of each session, the algorithm restarts and enriches its grid by adding sparse versions of the "leader" (the best-performing vector from the previous session). This allows the algorithm to adapt to the best sparse parameter without prior knowledge of the sparsity level.

SABOA (i.i.d. Setting)

In the more stable i.i.d. setting, the SABOA (Sparse Acceleration of BOA) algorithm is introduced. SABOA enriches its grid by averaging past estimates and applying truncation to maintain sparsity. This allows the algorithm to converge faster as it gathers more information about the underlying distribution of the data.

Handling Degeneracy: The Łojasiewicz Assumption

A significant challenge in high-dimensional learning is "degeneracy," where multiple combinations of features yield the same optimal result (e.g., collinearity). Most fast-rate algorithms rely on strong convexity, which fails in these scenarios. To address this, the authors utilize the Łojasiewicz assumption. This is a weaker, more realistic regularity condition that allows for multiple optima while still providing a framework for accelerated convergence. It ensures that the algorithms remain robust even when the objective function lacks a unique minimum.

Key Theoretical Results

The paper establishes several new benchmarks for sparse online learning:

  1. Quantile Regret Bounds: The authors provide the first high-probability quantile regret bound that achieves a fast rate. This ensures the algorithm performs well if any significant group of experts (rather than just a single best expert) performs well.
  2. Adversarial Performance: BOA+ achieves a regret bound of approximately $\tilde{O}(\sqrt{\|\theta\|_0 d / T})$. This bridges the gap between standard $1/\sqrt{T}$ rates and the ideal $1/T$ rate, specifically tuned for the number of active features $\|\theta\|_0$.
  3. i.i.d. Performance: In the i.i.d. setting, SABOA achieves a rate of $\tilde{O}((\|\theta\|_0 \ln d / T)^{1/(2-\beta)})$, where $\beta$ represents the regularity of the risk. For strongly convex risk ($\beta=1$), this reaches the optimal $O(1/T)$ rate.
  4. Full Adaptivity: Both algorithms are fully adaptive, meaning they do not require prior knowledge of the sparsity level or the specific regularity of the loss functions to achieve these accelerated rates.

Conclusion

By combining adaptive discretization with the Łojasiewicz assumption, Gaillard and Wintenberger provide a computationally efficient framework for sparse online learning. Their approach demonstrates that sparsity is not just a constraint to be managed, but a "speed booster" that can be leveraged to achieve fast-rate convergence without the overhead of complex projections. While challenges remain regarding sensitivity to the radius of the $\ell_1$-ball and optimizing computational constants, this work represents a significant step forward in making high-dimensional online optimization both faster and more robust.

Summary updated

Abstract

We consider the online convex optimization problem. In the setting of arbitrary sequences and finite set of parameters, we establish a new fast-rate quantile regret bound. Then we investigate the optimization into the L1-ball by discretizing the parameter space. Our algorithm is projection free and we propose an efficient solution by restarting the algorithm on adaptive discretization grids. In the adversarial setting, we develop an algorithm that achieves several rates of convergence with different dependencies on the sparsity of the objective. In the i.i.d. setting, we establish new risk bounds that are adaptive to the sparsity of the problem and to the regularity of the risk (ranging from a rate 1 / $\sqrt T$ for general convex risk to 1 /T for strongly convex risk). These results generalize previous works on sparse online learning. They are obtained under a weak assumption on the risk ({\L}ojasiewicz's assumption) that allows multiple optima which is crucial when dealing with degenerate situations.
BibTeX
@inproceedings{gaillard2018efficient,
  author = {Pierre Gaillard and Olivier Wintenberger},
  title = {{Efficient online algorithms for fast-rate regret bounds under sparsity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=rk4w0IbdbS},
}
Figure