Sketching as a tool for fast optimization

Abstract: \noindent 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. \\

Computer scienceMathematicsPhysics

Audience: researchers in the topic

MIT Simple Person's Applied Mathematics Seminar