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

Abstract

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 \emph{Variance Reduction via Primal-Dual Accelerated Dual Averaging (\vrpda)}. In the nonsmooth and general convex setting, \vrpda~has the overall complexity $O(nd\log \min \{1/\epsilon ,n\}+d/\epsilon )$ in terms of the primal-dual gap, where $n$ denotes the number of samples, $d$ the dimension of the primal variables, and $\epsilon$ the desired accuracy. In the nonsmooth and strongly convex setting, the overall complexity of \vrpda~becomes $O(nd\log \min \{1/\epsilon ,n\}+d/\sqrt{\epsilon })$ 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(nd\log \min \{1/\epsilon ,n\}+\sqrt{n}d/\epsilon )$ for the nonsmooth and general convex setting and $O(nd\log \min \{1/\epsilon ,n\}+\sqrt{n}d/\sqrt{\epsilon })$ for the nonsmooth and strongly convex setting, in a much more simple and straightforward way. Moreover, both complexities are better than \emph{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.

arXiv comment33 pages, 18 figures

References in corpus (15)

• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Robust Wasserstein Profile Inference and Applications to Machine Learning
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• Optimal Black-Box Reductions Between Optimization Objectives
• Randomized First-Order Methods for Saddle Point Optimization
• Variance Reduction for Matrix Games
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
• Stochastic Variance Reduced Primal Dual Algorithms for Empirical Composition Optimization
• Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization
• Breaking the Span Assumption Yields Fast Finite-Sum Minimization
• Random extrapolation for primal-dual coordinate descent