Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD
This work addresses the optimization of SGD convergence rates for convex functions, which is incremental as it builds on existing theory to provide new characterizations and solutions.
The paper tackles the problem of characterizing convex objective functions and deriving optimal expected convergence rates for Stochastic Gradient Descent (SGD) with diminishing step sizes, resulting in a new inequality and exact solutions that confirm known results and characterize a new regularizer.
We study Stochastic Gradient Descent (SGD) with diminishing step sizes for convex objective functions. We introduce a definitional framework and theory that defines and characterizes a core property, called curvature, of convex objective functions. In terms of curvature we can derive a new inequality that can be used to compute an optimal sequence of diminishing step sizes by solving a differential equation. Our exact solutions confirm known results in literature and allows us to fully characterize a new regularizer with its corresponding expected convergence rates.