现在位置:首页 > 学术报告
 

 

Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:

Dr. Junchi Li, Princeton University

Inviter: 刘歆
Title:
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
Time & Venue:
2018.8.26 11:00-12:00 Z311
Abstract:
In this paper, we propose a new technique named Stochastic Path-Integrated Di?erential EstimatoR (SPIDER), which can be used to track many deterministic quantities of interest with signi?cantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic ?rst-order and zeroth-order methods. For stochastic ?rst-order method, combining SPIDER with normalized gradient descent, we propose two new algorithms, namely SPIDER-SFO and SPIDER-SFO+, that solve non-convex stochastic optimization problems using stochastic gradients only. We provide sharp error-bound results on their convergence rates. In special, we prove that the SPIDER-SFO and SPIDER-SFO+ algorithms achieve a gradient computation cost of $O(\min(n^{1/2} \epsilon^{-2}, \epsilon^{-3} )$ for ?nding an $\epsilon$-approximate ?rst-order and $(\epsilon, O(\epsilon^{0.5}))$-approximate second-order stationary point, respectively. In addition, by modifying the recent lower result of Carmon, Duchi, Hinder and Sidford (2017+) we prove that SPIDER-SFO nearly matches the algorithmic lower bound for ?nding approximate ?rst-order stationary points under the gradient Lipschitz assumption in the ?nite-sum setting. For stochastic zeroth-order method, our proposed SPIDER-SZO algorithm has a gradient cost of $O(d \epsilon^{-3})$ which outperforms all existing results.
 

 

附件下载:
 
 
【打印本页】【关闭本页】
电子政务平台   |   科技网邮箱   |   ARP系统   |   会议服务平台   |   联系我们   |   友情链接