Fast Regression Algorithms Using Spectral Graph Theory

Опубликовано 8 августа 2016, 17:50

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.