Fast Regression Algorithms Using Spectral Graph Theory

Speaker  Richard (Yang) Peng

Affiliation  CMU

Host  Yuval Peres

Duration  00:51:15

Date recorded  23 January 2013

Convex optimization is a key tool in computer science, with applications ranging from machine learning to operational research. Due to the fast growth of data sizes, the development of faster optimization algorithms is becoming a more pressing question.

This talk will present a highly efficient solver for SDD linear systems, which is part of a new paradigm of designing algorithms for graph related optimization problems. This solver represents two decades of progress that exhibited a close connection between graph theory and numerical analysis. Surprisingly, this connection is two way: graph theoretic tools are needed to speed up linear algebraic routines, and the resulting routines are used to give the state of the art algorithms for many combinatorial problems.

A variety of tools such as graph sparsifiers and tree embeddings are used in the solver, and many of them may be of independent interest.

©2013 Microsoft Corporation. All rights reserved.
> Fast Regression Algorithms Using Spectral Graph Theory