Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

Abstract: We consider optimizing a function smooth convex function

f

that is the average of a set of differentiable functions

f_{i}

, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient

{f_{i}}^{'}

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.

This page was built for publication: Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition