Simple Person's Applied Math Seminar

Thursday, October 27, 2022 at 6:00pm to 6:45pm

Building 2, 2-132
182 MEMORIAL DR, Cambridge, MA 02139

Featured Speaker :  Lichen Zhang (MIT Mathematics)

Title :  Sketching as a tool for fast optimization

Abstract :  Sketching is a powerful tool with many applications including regression, low-rank approximation, and preconditioning. Given an n-by-d matrix A with n much larger than d, sketching describes a distribution on random matrices such that an element S of this distribution is an s-by-n matrix such that for any d-dimensional $ vector x, || SAx ||_2^2 <= (1+eps) || Ax ||_2^2$ , and $ s = poly(d, 1/eps, 1/delta) $ is independent of n.


\noindent In this talk, I survey another direction that uses sketching to speed up optimization algorithms. I’ll show how to design a good distribution of sketching matrices so that they can be used for \\
1). Compressed gradient descent, 
2). Linear programming and empirical risk minimization. \\


\noindent We will see how sketching enables us to develop novel data structures for numerical linear algebra problems, which are the backbones of recent breakthroughs in fast optimization algorithms. If time permits, I’ll also touch on using differential privacy (in a very surprising way) to improve the performance of the sketching data structure. \\

Event Type


Events By Interest


Events By Audience

MIT Community

Events By School

School of Science


aldixon, Applied Mathematics Seminar


Department of Mathematics


Contact Email

Add to my calendar

Recent Activity