Article Source

• Sketching and Projecting

Sketching and Projecting

• Deanna Needell (University of California, Los Angeles)
• https://simons.berkeley.edu/talks/mert-pilanci-stanford-university-2023-10-09
• Sketching and Algorithm Design

Abstract

We discuss recent work on sketching and projecting methods for linear systems as well as sketching in linear discriminant analysis. Both frameworks utilize stochastic gradient approaches, with the goal of obtaining solutions similar or exactly to the un-sketched problems, with significantly less computational burden. We present convergence guarantees for the sketched predictions on data within a fixed number of iterations. These guarantees account for both the modeling assumptions on the data and algorithmic randomness from the sketching procedure. We also include numerical results comparing the approaches.