Sketching for Convex and Nonconvex Regularized Least Squares with Sharp
  Guarantees
Yingzhen Yang Ping Li
Randomized algorithms are important for solving large-scale optimization
problems. In this paper, we propose a fast sketching algorithm for least square
problems regularized by convex or nonconvex regularization functions, Sketching
for Regularized Optimization (SRO). Our SRO algorithm first generates a sketch
of the original data matrix, then solves the sketched problem. Different from
existing randomized algorithms, our algorithm handles general Frechet
subdifferentiable regularization functions in an unified framework. We present
general theoretical result for the approximation error between the optimization
results of the original problem and the sketched problem for regularized least
square problems which can be convex or nonconvex. For arbitrary convex
regularizer, relative-error bound is proved for the approximation error.
Importantly, minimax rates for sparse signal estimation by solving the sketched
sparse convex or nonconvex learning problems are also obtained using our
general theoretical result under mild conditions. To the best of our knowledge,
our results are among the first to demonstrate minimax rates for convex or
nonconvex sparse learning problem by sketching under a unified theoretical
framework. We further propose an iterative sketching algorithm which reduces
the approximation error exponentially by iteratively invoking the sketching
algorithm. Experimental results demonstrate the effectiveness of the proposed
SRO and Iterative SRO algorithms.