2019/02/20 by Yi Xu, Rong Jin, Xu, Yi +3 · 5 citations
Computer Science · Engineering · Mathematics · Medicine · #Applied mathematics #Computer science #Conic optimization #Convergence (economics) #Convex analysis #Convex combination #Convex function #Convex optimization #FOS: Mathematics #Mathematical analysis #Mathematical optimization #Mathematics #Optical Imaging and Spectroscopy Techniques #Optimization and Control (math.OC) #Proper convex function #Proximal Gradient Methods #Proximal gradient methods for learning #Regular polygon #Sparse and Compressive Sensing Techniques #Stationary point #Stochastic Gradient Optimization Techniques #Subderivative #math.OC
paper · pdf · doi:10.48550/arxiv.1902.07672
published in arXiv (Cornell University) 32, 2626-2636 (Cornell University) · Accepted to NeurIPS 2019
openalex publication_date 2019/02/20 · arxiv created 2019/11/18 · arxiv updated 2019/11/19 · openalex created_date 2020/01/30 · openalex updated_date 2026/07/28
Stochastic Proximal Gradient (SPG) methods have been widely used for solving\noptimization problems with a simple (possibly non-smooth) regularizer in\nmachine learning and statistics. However, to the best of our knowledge no\nnon-asymptotic convergence analysis of SPG exists for non-convex optimization\nwith a non-smooth and non-convex regularizer. All existing non-asymptotic\nanalysis of SPG for solving non-smooth non-convex problems require the\nnon-smooth regularizer to be a convex function, and hence are not applicable to\na non-smooth non-convex regularized problem. This work initiates the analysis\nto bridge this gap and opens the door to non-asymptotic convergence analysis of\nnon-smooth non-convex regularized problems. We analyze several variants of\nmini-batch SPG methods for minimizing a non-convex objective that consists of a\nsmooth non-convex loss and a non-smooth non-convex regularizer. Our\ncontributions are two-fold: (i) we show that they enjoy the same complexities\nas their counterparts for solving convex regularized non-convex problems in\nterms of finding an approximate stationary point; (ii) we develop more\npractical variants using dynamic mini-batch size instead of a fixed mini-batch\nsize without requiring the target accuracy level of solution. The significance\nof our results is that they improve upon the-state-of-art results for solving\nnon-smooth non-convex regularized problems. We also empirically demonstrate the\neffectiveness of the considered SPG methods in comparison with other peer\nstochastic methods.\n