Sparse Accelerated Exponential Weights

[edit]

Pierre Gaillard, Olivier Wintenberger ;
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:75-82, 2017.

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.

Related Material