  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.
