Fast Regression Algorithms Using Spectral Graph Theory

January 23, 2013
Richard (Yang) Peng | CMU

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.

Speaker Details

Richard Peng is a graduate student in computer science at Carnegie Mellon University, and a Microsoft Research PhD Fellow. His main interests are in efficient algorithms for a variety of applications. The avenues that he has tried to explore in these directions include graph theory, scientific computing, and parallel algorithms. On his spare time, Richard enjoys attending codeholic anonymous meetings, and attempting to play hockey.