Conference proceeding
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
Advances in Neural Information Processing Systems, Vol.31
2018
Abstract
(This is a theory paper) In this paper, we consider first-order methods for solving stochastic non-convex optimization problems. The key building block of the proposed algorithms is first-order procedures to extract negative curvature from the Hessian matrix through a principled sequence starting from noise, which are referred to {\it NEgative-curvature-Originated-from-Noise or NEON} and are of independent interest. Based on this building block, we design purely first-order stochastic algorithms for escaping from non-degenerate saddle points with a much better time complexity (almost linear time in the problem's dimensionality). In particular, we develop a general framework of {\it first-order stochastic algorithms} with a second-order convergence guarantee based on our new technique and existing algorithms that may only converge to a first-order stationary point. For finding a nearly {\it second-order stationary point}
\x
such that
∥
∇
F
(
\x
)
∥
≤
ϵ
and
∇
2
F
(
\x
)
≥
−
√
ϵ
I
(in high probability), the best time complexity of the presented algorithms is
˜
O
(
d
/
ϵ
3.5
)
, where
F
(
⋅
)
denotes the objective function and
d
is the dimensionality of the problem. To the best of our knowledge, this is the first theoretical result of first-order stochastic algorithms with an almost linear time in terms of problem's dimensionality for finding second-order stationary points, which is even competitive with existing stochastic algorithms hinging on the second-order information.
Details
- Title: Subtitle
- First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
- Creators
- Yi XuRong JinTianbao Yang
- Resource Type
- Conference proceeding
- Publication Details
- Advances in Neural Information Processing Systems, Vol.31
- Language
- English
- Date published
- 2018
- Academic Unit
- Computer Science
- Record Identifier
- 9984259426202771
Metrics
12 Record Views