Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization

We propose a new randomized algorithm for solving L2-regularized\nleast-squares problems based on sketching. We consider two of the most popular\nrandom embeddings, namely, Gaussian embeddings and the Subsampled Randomized\nHadamard Transform (SRHT). While current randomized solvers for least-squares\noptimization prescribe an embedding dimension at least greater than the data\ndimension, we show that the embedding dimension can be reduced to the effective\ndimension of the optimization problem, and still preserve high-probability\nconvergence guarantees. In this regard, we derive sharp matrix deviation\ninequalities over ellipsoids for both Gaussian and SRHT embeddings.\nSpecifically, we improve on the constant of a classical Gaussian concentration\nbound whereas, for SRHT embeddings, our deviation inequality involves a novel\ntechnical approach. Leveraging these bounds, we are able to design a practical\nand adaptive algorithm which does not require to know the effective dimension\nbeforehand. Our method starts with an initial embedding dimension equal to 1\nand, over iterations, increases the embedding dimension up to the effective one\nat most. Hence, our algorithm improves the state-of-the-art computational\ncomplexity for solving regularized least-squares problems. Further, we show\nnumerically that it outperforms standard iterative solvers such as the\nconjugate gradient method and its pre-conditioned version on several standard\nmachine learning datasets.\n