Ridge Regression with Frequent Directions: Statistical and Optimization Perspectives
This work addresses the need for more efficient and accurate methods in large-scale regression tasks for machine learning practitioners, though it is incremental as it builds on existing FD techniques.
The paper tackled the problem of improving large-scale ridge regression by using Frequent Directions (FD) instead of randomized sketches, achieving the first constant factor relative error bounds on bias and variance for sketched ridge regression with FD, and showing that FD can be used in optimization with an iterative scheme for high-accuracy solutions.
Despite its impressive theory \& practical performance, Frequent Directions (\acrshort{fd}) has not been widely adopted for large-scale regression tasks. Prior work has shown randomized sketches (i) perform worse in estimating the covariance matrix of the data than \acrshort{fd}; (ii) incur high error when estimating the bias and/or variance on sketched ridge regression. We give the first constant factor relative error bounds on the bias \& variance for sketched ridge regression using \acrshort{fd}. We complement these statistical results by showing that \acrshort{fd} can be used in the optimization setting through an iterative scheme which yields high-accuracy solutions. This improves on randomized approaches which need to compromise the need for a new sketch every iteration with speed of convergence. In both settings, we also show using \emph{Robust Frequent Directions} further enhances performance.