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.

\vspace{1ex}

\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. \\

\vspace{1ex}

\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

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

MIT Community

Events By School

School of Science

Tags

aldixon, Applied Mathematics Seminar

Website

https://math.mit.edu/seminars/spams/

Department
Department of Mathematics
Hashtag

#Mathematics

Contact Email

aldixon@mit.edu

Add to my calendar

Recent Activity