  


SPIDER: NearOptimal NonConvex Optimization via Stochastic Path Integrated Differential Estimator
Cong Fang (fangcongpku.edu.cn) Abstract: In this paper, we propose a new technique named \textit{Stochastic PathIntegrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic firstorder and zerothorder methods. For stochastic firstorder method, combining SPIDER with normalized gradient descent, we propose two new algorithms, namely SPIDERSFO and SPIDERSFO\textsuperscript{+}, that solve nonconvex stochastic optimization problems using stochastic gradients only. We provide sharp errorbound results on their convergence rates. In special, we prove that the SPIDERSFO and SPIDERSFO\textsuperscript{+} algorithms achieve a recordbreaking gradient computation cost of $\mathcal{O}\left( \min( n^{1/2} \epsilon^{2}, \epsilon^{3} ) \right)$ for finding an $\epsilon$approximate firstorder and $\tilde{\mathcal{O}}\left( \min( n^{1/2} \epsilon^{2}+\epsilon^{2.5}, \epsilon^{3} ) \right)$ for finding an $(\epsilon, \mathcal{O}(\epsilon^{0.5}))$approximate secondorder stationary point, respectively. In addition, we prove that SPIDERSFO nearly matches the algorithmic lower bound for finding approximate firstorder stationary points under the gradient Lipschitz assumption in the finitesum setting. For stochastic zerothorder method, we prove a cost of $\mathcal{O}( d \min( n^{1/2} \epsilon^{2}, \epsilon^{3}) )$ which outperforms all existing results. Keywords: nonconvex optimization, firstorder stationary point, secondorder stationary point, gradient descent, zerothorder optimization, variance reduction Category 1: Stochastic Programming Category 2: Nonlinear Optimization Citation: Download: [PDF] Entry Submitted: 07/04/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  