Timezone: »
We analyze stochastic gradient algorithms for optimizing nonconvex, nonsmooth finite-sum problems. In particular, the objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a possibly non-differentiable but convex component. We propose a proximal stochastic gradient algorithm based on variance reduction, called ProxSVRG+. Our main contribution lies in the analysis of ProxSVRG+. It recovers several existing convergence results and improves/generalizes them (in terms of the number of stochastic gradient oracle calls and proximal oracle calls). In particular, ProxSVRG+ generalizes the best results given by the SCSG algorithm, recently proposed by [Lei et al., 2017] for the smooth nonconvex case. ProxSVRG+ is also more straightforward than SCSG and yields simpler analysis. Moreover, ProxSVRG+ outperforms the deterministic proximal gradient descent (ProxGD) for a wide range of minibatch sizes, which partially solves an open problem proposed in [Reddi et al., 2016]. Also, ProxSVRG+ uses much less proximal oracle calls than ProxSVRG [Reddi et al., 2016]. Moreover, for nonconvex functions satisfied Polyak-\L{}ojasiewicz condition, we prove that ProxSVRG+ achieves a global linear convergence rate without restart unlike ProxSVRG. Thus, it can \emph{automatically} switch to the faster linear convergence in some regions as long as the objective function satisfies the PL condition locally in these regions. Finally, we conduct several experiments and the experimental results are consistent with the theoretical results.
Author Information
Zhize Li (Tsinghua University)
Zhize Li is a PhD student at Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University (Advisor: Prof. Jian Li). His research interests lie in theoretical computer science and machine learning, in particular (non-)convex optimization algorithms, machine learning, algorithms and data structures.
Jian Li (Tsinghua University)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization »
Thu. Dec 6th through Fri the 7th Room Room 210 #5
More from the Same Authors
-
2020 Poster: Improved Algorithms for Convex-Concave Minimax Optimization »
Yuanhao Wang · Jian Li -
2015 Poster: On Top-k Selection in Multi-Armed Bandits and Hidden Bipartite Graphs »
Wei Cao · Jian Li · Yufei Tao · Zhize Li -
2015 Poster: Stochastic Online Greedy Learning with Semi-bandit Feedbacks »
Tian Lin · Jian Li · Wei Chen