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).
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.
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