Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
This addresses computational challenges in empirical risk minimization for machine learning practitioners, though it appears to be an incremental improvement over existing nonsmooth optimization methods.
The paper tackles large-scale nonsmooth convex optimization problems common in machine learning by developing a new algorithm that achieves robust linear convergence with superior time and gradient complexity compared to state-of-the-art methods, while eliminating the need for extra error bound conditions or strong convexity assumptions. Experimental results demonstrate strong performance on a large-scale ranking problem.
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.