Convergence of stochastic gradient method
Shuvomoy Das Gupta
December 27, 2022
In this blog, we study convergence of stochastic gradient method.
Problem setup
We are interested in solving the problemNotation
| ( |
where we have the following assumptions regarding the nature of the problem.
Assumption 1
We assume:
is a closed, proper, and convex function, is a nonempty, closed, convex set, with , and .
Stochastic gradient descent
The stochastic gradient descent (SGD) algorithm to solve (
Assumption 2
We assume that given an iterate
- (unbiased)
, and - (bounded variance)
___________________________________________________________
input:
___________________________________________________________
algorithm:
1. initialization:
pick
2. main iteration:
for
end for
3. return
___________________________________________________________
Convergence analysis
First, note that, for all
So, we have proved
|
so taking expectation with respect to
so
|
Now, let us do a telescoping sum:
and adding the equations above, we get:
In the last inequality,
|
so if we have
|
A pdf of the blog is available here.