Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
arXiv:1805.05189
Abstract
In this paper, we consider the problem of minimizing the average of a large number of nonsmooth and convex functions. Such problems often arise in typical machine learning problems as empirical risk minimization, but are computationally very challenging. We develop and analyze a new algorithm that achieves robust linear convergence rate, and both its time complexity and gradient complexity are superior than state-of-art nonsmooth algorithms and subgradient-based schemes. Besides, our algorithm works without any extra error bound conditions on the objective function as well as the common strongly-convex condition. We show that our algorithm has wide applications in optimization and machine learning problems, and demonstrate experimentally that it performs well on a large-scale ranking problem.
arXiv comment10 pages, 12 figures. arXiv admin note: text overlap with arXiv:1103.4296, arXiv:1403.4699 by other authors
References in corpus (8)
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Proximal Stochastic Dual Coordinate Ascent
- RSG: Beating Subgradient Method without Smoothness and Strong Convexity
- A Variance Reduced Stochastic Newton Method
- Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
- Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization