  This paper develops a scalable new algorithm, called NysADMM, to minimize a
smooth convex loss function with a convex regularizer. NysADMM accelerates the
inexact Alternating Direction Method of Multipliers (ADMM) by constructing a
preconditioner for the ADMM subproblem from a randomized low-rank Nystr\"om
approximation. NysADMM comes with strong theoretical guarantees: it solves the
ADMM subproblem in a constant number of iterations when the rank of the
Nystr\"om approximation is the effective dimension of the subproblem
regularized Gram matrix. In practice, ranks much smaller than the effective
dimension can succeed, so NysADMM uses an adaptive strategy to choose the rank
that enjoys analogous guarantees. Numerical experiments on real-world datasets
demonstrate that NysADMM can solve important applications, such as the lasso,
logistic regression, and support vector machines, in half the time (or less)
required by standard solvers. The breadth of problems on which NysADMM beats
standard solvers is a surprise: it suggests that ADMM is a dominant paradigm
for numerical optimization across a wide range of statistical learning problems
that are usually solved with bespoke methods.
