Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums

We study structured nonsmooth convex finite-sum optimization that appears widely in machine learning applications, including support vector machines and least absolute deviation. For the primal-dual formulation of this problem, we propose a novel algorithm called Variance Reduction via Primal-Dual Accelerated Dual Averaging (vrpda). In the nonsmooth and general convex setting, vrpda~has the overall complexity O(ndlogmin 1/ε, n + d/ε ) in terms of the primal-dual gap, where n denotes the number of samples, d the dimension of the primal variables, and ε the desired accuracy. In the nonsmooth and strongly convex setting, the overall complexity of vrpda~becomes O(ndlogmin1/ε, n + d/√ε) in terms of both the primal-dual gap and the distance between iterate and optimal solution. Both these results for vrpda~improve significantly on state-of-the-art complexity estimates, which are O(ndlog min1/ε, n + √nd/ε) for the nonsmooth and general convex setting and O(ndlog min1/ε, n + √nd/√ε) for the nonsmooth and strongly convex setting, in a much more simple and straightforward way. Moreover, both complexities are better than lower bounds for general convex finite sums that lack the particular (common) structure that we consider. Our theoretical results are supported by numerical experiments, which confirm the competitive performance of vrpda~compared to state-of-the-art.