Convergence Analysis of SGD in Convex Optimization Problems
Abstract
As its name suggests, stochastic gradient descent (SGD) is a stochastic version of the gradient descent algorithm. Gradient descent is a greedy algorithm that locally decreases the value of the objective function by moving in the direction of its negative gradient, with the aim of eventually reaching a local or global minimum. In its stochastic version, the direction of movement is a random vector, which we expect its average to point in the direction of the negative gradient, or more generally, in the direction of the negative of a vector in the subdifferential of the function. Our goal is to provide a precise formulation of this general idea and to study the convergence of the algorithm for convex functions. We begin with Lipschitz convex objective functions and then extend the results to strongly convex functions. Finally, we consider an application of the method to regularized empirical risk minimization problems arising in machine learning.
Materials
Side Notes
In this final session, we introduce convex classes of learning problems and see how the convergence results for SGD developed earlier can be applied to such problems.