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

Abstract

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.

References in corpus (7)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• SGD: General Analysis and Improved Rates
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• Accelerate Stochastic Subgradient Method by Leveraging Local Growth Condition

Cited by in corpus (1)

• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD