Efficient online algorithms for fast-rate regret bounds under sparsity

Pierre Gaillard, Olivier Wintenberger

This paper tackles a fundamental challenge in Online Convex Optimization (OCO): achieving "fast" learning rates that depend on the sparsity of the solution rather than the total number of features, all while remaining computationally efficient.

The Challenge of High-Dimensional Online Learning

In online learning, a learner repeatedly chooses a parameter $\theta$ and suffers a loss. The primary goal is to minimize regret—the difference between the learner's total loss and the loss of the best fixed parameter chosen in hindsight.

Standard theoretical results often show that regret scales with $\sqrt{d/T}$, where $d$ is the dimension of the parameter space and $T$ is the number of time steps. However, in modern high-dimensional problems (like genomics or web-scale filtering), $d$ can be massive. Fortunately, the "true" optimal parameter is often sparse, meaning most of its entries are zero. Ideally, we want regret bounds that depend on the number of non-zero entries ($k$ or $d_0$) rather than the full dimension $d$.

While "slow-rate" sparse bounds (e.g., scaling with $k/\sqrt{T}$) exist, achieving "fast-rate" bounds (scaling with $k/T$) typically requires either unrealistically strong assumptions (like strict exp-concavity of the loss) or computationally intractable algorithms (like aggregating an exponential number of experts). This paper bridges that gap, introducing algorithms that are both computationally efficient and capable of achieving fast, sparse regret bounds.

Proposed Methods: BOA+ and SABOA

The authors build upon Bernstein Online Aggregation (BOA) and the Squint algorithm, innovating primarily in how they handle the discretization of the continuous parameter space (specifically, the unit $\ell_1$-ball).

  • BOA+ (Adversarial Setting): Designed for strongly convex losses where incoming data can be arbitrary or adversarial. It employs a "doubling trick" to divide time into sessions. In each session, it restarts a base algorithm using a small, carefully chosen grid of points. Crucially, this grid includes the "leader" (the empirical risk minimizer) from the previous session, truncated to maintain sparsity.
  • SABOA (i.i.d. Setting): Designed for the stochastic (i.i.d.) setting. It utilizes the Łojasiewicz assumption, a relaxation of strong convexity that allows for multiple optima or "flat" regions in the risk function. Like BOA+, it adaptively updates its discretization grid based on past performance.

To prove that their discrete grid approach generalizes well to the entire continuous $\ell_1$-ball, the authors introduce a new pseudo-metric, $D(\theta, \theta')$. This "averaging accelerability" metric measures how well a point $\theta$ can be approximated by a convex combination of a grid point and the origin.

Key Insights

  • Efficiency through Adaptation: Instead of discretizing the entire high-dimensional space upfront—which is computationally impossible—the algorithms start with a simple set of "corners" and adaptively add sparse, high-performing candidates to their "expert" pool over time.
  • Weak Exp-Concavity: The paper introduces a "weak" version of exp-concavity. This demonstrates that fast rates are possible even for loss functions that fail to meet strict classical definitions, such as absolute or quantile loss in regular regression settings.
  • The Łojasiewicz Advantage: By leveraging the Łojasiewicz assumption, the authors provide sparse bounds that remain robust even with "degenerate" data (e.g., highly correlated features), a frequent issue in high-dimensional statistics where the covariance matrix might lack full rank.
Comparison of procedures, rates, and assumptions in the stochastic setting.

Theoretical Results

As a purely theoretical paper, the contributions are mathematical proofs of algorithmic performance rather than empirical benchmarks.

  1. Quantile Bounds: The authors provide the first high-probability "quantile" bound for weak exp-concave losses, meaning the algorithm performs well against any "good" distribution of experts, not just the single best one.
  2. Adversarial Sparsity: BOA+ achieves a regret bound of approximately $\tilde{O}(\sqrt{k \cdot d / T})$ for strongly convex losses. While it doesn't quite reach the "ideal" $k/T$ rate, it represents a significant, efficiently computable improvement over non-sparse bounds.
  3. i.i.d. Sparsity: Under the Łojasiewicz assumption, SABOA achieves a rate of $\tilde{O}((k \ln d / T)^{1/(2-\beta)})$, where $\beta$ describes the "flatness" of the risk. For strongly convex risks ($\beta=1$), this perfectly recovers the optimal $k/T$ rate.
Comparison of regret bounds, efficiency (polynomial time), and sparsity settings for various procedures.

Limitations and Future Directions

  • The Adversarial Rate Gap: In the adversarial setting, the bound for BOA+ still contains a $\sqrt{d}$ term, albeit mitigated by the sparsity $k$. Achieving a pure $k/T$ rate with an efficient algorithm in the adversarial setting remains an open challenge.
  • Fixed Radius: The current analysis is restricted to the unit $\ell_1$-ball ($||\theta||_1 \leq 1$). Extending these proofs to balls of arbitrary radius $U$ is a target for future research.
  • Support Recovery: While the algorithms achieve excellent regret bounds, they do not necessarily "find" the exact support (the specific non-zero indices) of the optimal parameter without additional, more restrictive conditions.

Summary updated

Abstract

We consider the problem of online convex optimization in two different settings: arbitrary and i.i.d. sequence of convex loss functions. In both settings, we provide efficient algorithms whose cumulative excess risks are controlled with fast-rate sparse bounds. First, the excess risks bounds depend on the sparsity of the objective rather than on the dimension of the parameters space. Second, their rates are faster than the slow-rate $1/\sqrt{T}$ under additional convexity assumptions on the loss functions. In the adversarial setting, we develop an algorithm BOA+ whose cumulative excess risks is controlled by several bounds with different trade-offs between sparsity and rate for strongly convex loss functions. In the i.i.d. setting under the Łojasiewicz's assumption, we establish new risk bounds that are sparse with a rate adaptive to the convexity 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 under weak assumptions on the risk.
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