Timezone: »

 
Poster
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator
Cong Fang · Chris Junchi Li · Zhouchen Lin · Tong Zhang

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 210 #49
in Wed Poster Session B »
In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interests with significantly reduced computational cost. Combining SPIDER with the method of normalized gradient descent, we propose SPIDER-SFO that solve non-convex stochastic optimization problems using stochastic gradients only. We provide a few error-bound results on its convergence rates. Specially, we prove that the SPIDER-SFO algorithm achieves a gradient computation cost of $\mathcal{O}\left( \min( n^{1/2} \epsilon^{-2}, \epsilon^{-3} ) \right)$ to find an $\epsilon$-approximate first-order stationary point. In addition, we prove that SPIDER-SFO nearly matches the algorithmic lower bound for finding stationary point under the gradient Lipschitz assumption in the finite-sum setting. Our SPIDER technique can be further applied to find an $(\epsilon, \mathcal{O}(\ep^{0.5}))$-approximate second-order stationary point at a gradient computation cost of $\tilde{\mathcal{O}}\left( \min( n^{1/2} \epsilon^{-2}+\epsilon^{-2.5}, \epsilon^{-3} ) \right)$.
Keywords: Stochastic Methods · Non-Convex Optimization
[ Paper] 

Author Information

Cong Fang (Peking University)
Chris Junchi Li (Tencent AI Lab)
Zhouchen Lin (Peking University)
Tong Zhang (Tencent AI Lab)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors