Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions

W e develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (app roximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding a O (d/T) convergence rate for strongly convex objectives in d dimensions and O (null s (log d)/T) convergence rate when the optimum is s -sparse.