Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD


Marten Van Dijk, Lam Nguyen, Phuong Ha Nguyen, Dzung Phan ;
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6392-6400, 2019.


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.

Related Material