Classical results in sketching for dimensionality reduction in machine learning assert that, provided the sketch size is sufficiently large, the original unsketched solution is recovered at a fraction of the cost. However, in many practical settings, the sketch size may be smaller than needed for these guarantees. We provide a more general asymptotic result for sketched matrix inversion that holds for any sketch size and reveal that sketching is equivalent to adding ridge regularization. We prove our results for a broad class of asymptotically free sketches encompassing the spectral profiles of most sketches used in practice. We then determine the precise effect of sketching on the generalization error of ridge regression and show that the generalized cross-validation risk estimator is consistent for sketched ensembles, enabling the efficient evaluation of unsketched ridge regression risk using only sketched data.
https://umd.zoom.us/j/97962008923
Daniel LeJeune is a postdoctoral scholar in the Department of Statistics at Stanford University. He completed his B.S. in Engineering at McNeese State University, M.S. in Electrical and Computer Engineering at University of Michigan, and Ph.D. in Electrical and Computer Engineering at Rice University, and also served as Associate Staff at MIT Lincoln Laboratory working on applications of machine learning to cybersecurity. He is a recipient of the Rising Stars Award from the 2024 Conference on Parsimony and Learning and is interested in the theoretical analysis of heuristics applied in machine learning.