Abstract

We present two new algorithms, A SYN CADA and H EDGE H OG, for asynchronous sparse online and stochastic optimization. A SYN CADA is, to our knowledge, the first asynchronous stochastic optimization algorithm with finite-time datadependent convergence guarantees for generic convex constraints. In addition, A SYN CADA: (a) allows for proximal (i.e., composite-objective) updates and adaptive step-sizes; (b) enjoys any-time convergence guarantees without requiring an exact global clock; and (c) when the data is sufficiently sparse, its convergence rate for (non-)smooth, (non-)strongly-convex, and even a limited class of nonconvex objectives matches the corresponding serial rate, implying a theoretical “linear speed-up”. The second algorithm, H EDGE H OG, is an asynchronous parallel version of the Exponentiated Gradient (EG) algorithm for optimization over the probability simplex (a.k.a. Hedge in online learning), and, to our knowledge, the first asynchronous algorithm enjoying linear speed-ups under sparsity with nonSGD-style updates. Unlike previous work, A SYN CADA and H EDGE H OG and their convergence and speed-up analyses are not limited to individual coordinatewise (i.e., “box-shaped”) constraints or smooth and strongly-convex objectives. Underlying both results is a generic analysis framework that is of independent interest, and further applicable to distributed and delayed feedback optimization.