2018/09/18 by Zaiyi Chen, Chen, Zaiyi, Yi Xu +5 · 1 citation
Business, Management and Accounting · Computer Science · Engineering · Mathematics · #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1809.06754
openalex publication_date 2018/09/18 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
In this paper, we propose a new SVRG-style acceleated stochastic algorithm\nfor solving a family of non-convex optimization problems whose objective\nconsists of a sum of n smooth functions and a non-smooth convex function. Our\nmajor goal is to improve the convergence of SVRG-style stochastic algorithms to\nstationary points under a setting with a large condition number c - the ratio\nbetween the smoothness constant and the negative curvature constant. The\nproposed algorithm achieves the best known gradient complexity when c\≥\n\Ω(n), which was achieved previously by a SAGA-style accelerated\nstochastic algorithm. Compared with the SAGA-style accelerated stochastic\nalgorithm, the proposed algorithm is more practical due to its low memory cost\nthat is inherited from previous SVRG-style algorithms. Compared with previous\nstudies on SVRG-style stochastic algorithms, our theory provides much stronger\nresults in terms of (i) reduced gradient complexity under a large condition\nnumber; and (ii) that the convergence is proved for a sampled stagewise\naveraged solution that is selected from all stagewise averaged solutions with\nincreasing sampling probabilities instead of for a uniformly sampled solutions\nacross all iterations.\n