0 Paper
Rakhlin A, Shamir O, Sridharan K. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv:1109.5647. 2011 Sep 26.
1 Key contribution
The paper proved the followings regarding the convergence rate of stochastic gradient descent (SGD)
- For smooth & strongly convex problems, SGD attains
convergence rate
- For strongly convex problems, SGD with averaging has a lower bound
- For non-smooth & strongly convex problems, SGD with
-suffix averaging can recover the
2 Preliminary knowledge
Problem statement
Given some convex domainand an unknown convex function
, using SGD to update
so as to find the optimal solution
, and then the goal is to provide bounds on
either in expectation or in high probability.
if for all
and any subgradient
of
,
SGD
At each step, SGD producessuch that
is a subgradient of
. Then, update
where,is the projection on
is the learning rate.
3 Main analysis
1) Smooth functions
suppose
is
and
w.r.t.
over a convex set
, and
. Then if let
for some constant
, it holds for any
that
suppose
is
and
w.r.t.
over a convex set
, and
. Then if let
for some constant
, it holds for any
that
suppose
is
and
w.r.t.
over a convex set
,
is the average of
, and
. Then if let
for some constant
, it holds for any
that
2) Non-smooth functions
shows that when the global optimum lies at the corner of
, leading SGD to approaches the optimal from one direction, the convergence rate of SGD with averaging is
.
shows that even when the global optimum lies in the interior of
, as long as SGD approaches the optimum only from one direction, the convergence rate of SGD with averaging is still
.
3) SGD with -suffix averaging
Consider SGD with
-suffix averaging, and with step size
where
is a constant. Suppose
is
and that
for all t. Then for any
, it holds that
where
4) High probability bounds
Let
and
. Suppose
is
over a convex set
, and that
with probalility 1. Then if we pick
for some constant
, such that
is a whole number, it holds with probability at least
that for any
that
3 Some thoughts about innovation and writing
1) Innovation:
- Extend something already known to some unknown areas
- Talk about some special but important cases
- Establish theoretical analysis for some phenomenon
- Apply theoretical results to real applications
2) Writing:
- The title should be better if it is less than 10 words. Make it more concise and interesting!
- In the introduction, start with a general topic and narrow it down to the key topic of the paper step by step. Transitions could be made by saying, e.g., ”An important special case…”, “One of the … is that ”. Remember, tell a good story!
- Regarding literature review, include only the latest papers may be enough. Clarify the difference of your paper and other related works.
- Claim and list the specific contributions of the paper. Even though you may say something about what are your innovations, list them in details any way so that readers are able to know your exact contributions.
