Robust sketching for multiple square-root LASSO problems
This addresses computational bottlenecks in large-scale learning tasks like cross-validation for researchers and practitioners, though it is incremental as it builds on existing sketching methods.
The paper tackles the problem of solving multiple square-root LASSO problems efficiently by introducing a robust sketching framework using low-rank approximations, which reduces computational effort from m to k observations without sacrificing statistical performance, sometimes even improving it.
Many learning tasks, such as cross-validation, parameter search, or leave-one-out analysis, involve multiple instances of similar problems, each instance sharing a large part of learning data with the others. We introduce a robust framework for solving multiple square-root LASSO problems, based on a sketch of the learning data that uses low-rank approximations. Our approach allows a dramatic reduction in computational effort, in effect reducing the number of observations from $m$ (the number of observations to start with) to $k$ (the number of singular values retained in the low-rank model), while not sacrificing---sometimes even improving---the statistical performance. Theoretical analysis, as well as numerical experiments on both synthetic and real data, illustrate the efficiency of the method in large scale applications.