Conference proceeding
Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems
Advances in Neural Information Processing Systems, Vol.32, pp.2630-2640
02/20/2019
Abstract
Stochastic Proximal Gradient (SPG) methods have been widely used for solving optimization problems with a simple (possibly non-smooth) regularizer in machine learning and statistics. However, to the best of our knowledge no non-asymptotic convergence analysis of SPG exists for non-convex optimization with a non-smooth and non-convex regularizer. All existing non-asymptotic analysis of SPG for solving non-smooth non-convex problems require the non-smooth regularizer to be a convex function, and hence are not applicable to a non-smooth non-convex regularized problem. This work initiates the analysis to bridge this gap and opens the door to non-asymptotic convergence analysis of non-smooth non-convex regularized problems. We analyze several variants of mini-batch SPG methods for minimizing a non-convex objective that consists of a smooth non-convex loss and a non-smooth non-convex regularizer. Our contributions are two-fold: (i) we show that they enjoy the same complexities as their counterparts for solving convex regularized non-convex problems in terms of finding an approximate stationary point; (ii) we develop more practical variants using dynamic mini-batch size instead of a fixed mini-batch size without requiring the target accuracy level of solution. The significance of our results is that they improve upon the-state-of-art results for solving non-smooth non-convex regularized problems. We also empirically demonstrate the effectiveness of the considered SPG methods in comparison with other peer stochastic methods.
Details
- Title: Subtitle
- Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems
- Creators
- Yi XuRong JinTianbao Yang
- Resource Type
- Conference proceeding
- Publication Details
- Advances in Neural Information Processing Systems, Vol.32, pp.2630-2640
- Publisher
- Curran Associates, Inc.
- Language
- English
- Date published
- 02/20/2019
- Academic Unit
- Computer Science
- Record Identifier
- 9984259439602771
Metrics
14 Record Views