Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

Original · EN

We consider optimizing a function smooth convex function f that is the average of a set of differentiable functions fᵢ, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient fᵢ' is bounded by a linear function of the norm of the average gradient f'. We show that under these assumptions the basic stochastic gradient method with a sufficiently-small constant step-size has an O(1/k) convergence rate, and has a linear convergence rate if g is strongly-convex.