Sparse Accelerated Exponential Weights

Pierre Gaillard, Olivier WintenbergerAISTATS 2017 · OpenReview

Abstract

We consider the stochastic optimization problem where a convex function is minimized observing recursively the gradients. We introduce SAEW, a new procedure that accelerates exponential weights procedures with the slow rate $1/\sqrt{T}$ to procedures achieving the fast rate $1/T$. Under the strong convexity of the risk, we achieve the optimal rate of convergence for approximating sparse parameters in $\mathbb{R}^d$. The acceleration is achieved by using successive averaging steps in an online fashion. The procedure also produces sparse estimators thanks to additional hard threshold steps.

Introduction

In stochastic optimization, the goal is to find a parameter $\theta^*$ that minimizes a risk function based on noisy gradient observations over time. Two primary challenges persist in high-dimensional settings: the "speed gap" and the "sparsity challenge." Standard robust methods like Stochastic Gradient Descent (SGD) or Exponential Weights (EW) typically converge at a "slow" rate of $1/\sqrt{T}$. While "fast" $1/T$ rates are theoretically possible under strong convexity, achieving them with high probability in an online, high-dimensional setting is difficult. Furthermore, in applications like genomics, the true parameter $\theta^*$ is often sparse ($d_0 \ll d$). We seek an algorithm whose error depends on $d_0$ rather than $d$. SAEW bridges this gap by providing a fast, sparse-aware, and computationally efficient online procedure.

Methods: Localization and Restarting

The core innovation of SAEW is a recursive localization and restarting strategy. Instead of a single continuous run, the algorithm operates in sessions of adaptive length. Each session employs a standard online learning subroutine, such as the Bernoulli Online Aggregation (BOA).

Geometric illustration of the localization and restarting strategy in SAEW.

At the conclusion of each session, SAEW calculates an average estimator and initiates a new session centered at this average, restricted to a progressively smaller $\ell_1$-ball. As illustrated in Figure 1, this "zooming in" mechanism, combined with a hard-truncation step to enforce sparsity, allows the algorithm to focus on the optimal parameter region. The total computational complexity remains $O(dT)$, making it practical for large-scale problems.

Empirical Evaluation and Results

The performance of SAEW was evaluated using simulated datasets, including high-dimensional square linear regression ($d=500, d_0=5$) and linear quantile regression. The latter tests robustness to non-smooth losses where only the expected risk is strongly convex.

Convergence rates of SAEW compared to RDA and BOA, showing the acceleration effect.

The theoretical analysis proves that SAEW achieves an instantaneous risk rate of $O(\frac{d_0 \log d}{\alpha T})$, matching the minimax optimal rate for batch procedures like the Lasso. Empirically, as shown in Figure 6, SAEW initially follows the baseline (BOA) but eventually "accelerates" (around $\log t \approx 6.2$), with its error dropping significantly faster than non-accelerated methods like Regularized Dual Averaging (RDA). Additionally, SAEW achieves a cumulative risk of $O(\log T)$, the gold standard for fast online learning.

Discussion

SAEW is the first polynomial-time online procedure to recover minimax rates for sparse strongly convex settings with high probability. While the algorithm demonstrates superior performance, it does exhibit sensitivity to hyperparameters such as $d_0$ and the strong convexity parameter $\alpha$. Future work may involve refining the "restart" phase to minimize transient performance dips and exploring more specialized sparse online sub-procedures to further enhance performance in extremely high-dimensional regimes.

Summary updated

Abstract

We consider the stochastic optimization problem where a convex function is minimized observing recursively the gradients. We introduce SAEW, a new procedure that accelerates exponential weights procedures with the slow rate $1/\sqrtT$ to procedures achieving the fast rate $1/T$. Under the strong convexity of the risk, we achieve the optimal rate of convergence for approximating sparse parameters in $R^d$. The acceleration is achieved by using successive averaging steps in an online fashion. The procedure also produces sparse estimators thanks to additional hard threshold steps.
BibTeX
@inproceedings{gaillard2017sparse,
  author = {Pierre Gaillard and Olivier Wintenberger},
  title = {{Sparse Accelerated Exponential Weights}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=zXERme9tvU},
}

Loading related content...

Figure