Conference abstracts

Session A7 - Stochastic Computation

July 12, 18:00 ~ 18:25 - Room B2

Stochastic Composite Least-Squares Regression with convergence rate $O(1/n)$

Francis Bach

INRIA - Ecole Normale SupĂ©rieure, France   -   francis.bach@inria.fr

We consider the minimization of composite objective functions composed of the expectation of quadratic functions and an arbitrary convex function. We study the stochastic dual averaging algorithm with a constant step-size, showing that it leads to a convergence rate of $O(1/n)$ without strong convexity assumptions. This thus extends earlier results on least-squares regression with the Euclidean geometry to (a) all convex regularizers and constraints, and (b) all geometries represented by a Bregman divergence. This is achieved by a new proof technique that relates stochastic and deterministic recursions.

Joint work with Nicolas Flammarion.

View abstract PDF



FoCM 2017, based on a nodethirtythree design.