Merging Continuous and Discrete Algorithms via Graph Laplacians
Algorithmic analyses of large matrices and networks are increasingly reliant on high-level primitives such as eigensolvers and optimization packages. Over the past three decades, the study of efficient solvers for a class of structured matrices, graph Laplacians, led to progresses on fundamental problems in scientific computing, combinatorial optimization, and data structures. In this talk, I will discuss key ideas and structures in hybrid algorithms for graph Laplacians, as well as the increasing reliance on sparsification and preconditioning in more recent developments. I will then describe efforts in bringing these results closer to practice, as well as several new theoretical tools tailored towards hybrid algorithmic frameworks motivated by studying graph Laplacians.
- Facebook Research (Feb 2019, slides),
- Georgia Scientific Computing Symposium (Feb 2019),
- Georgia Tech Theory Club (Nov 2018),
- FOCS`18 Workshop (Oct 2018),
- Simons Workshop (Sep 2018, video),
- ITCS at SUFE, (June 2017),
- NSF Algorithms in the Field PI meeting (Mar 2017),
- CSE 2017 (Feb 2017).
A Numerical Analysis Approach to Convex Optimization
In current convex optimization literature, there are significant gaps between algorithms that produce high accuracy (1+1/poly(n))-approximate solutions vs. algorithms that produce O(1)-approximate solutions for symmetrized special cases. This gap is reflected in the differences between interior point methods vs. (accelerated) gradient descent for regression problems, and between exact vs. approximate undirected max-flow.
In this talk, I will discuss generalizations of a fundamental building block in numerical analysis, preconditioned iterative methods, to convex functions that include p-norms. This leads to algorithms that converge to high accuracy solutions by crudely solving a sequence of symmetric residual problems. I will then briefly describe several recent and ongoing projects, including p-norm regression using m1/3 linear system solves, p-norm flow in undirected unweighted graphs in almost-linear time, and further improvements to the dependence on p in the runtime.
- Georgia Tech ACO Seminar (Jan 2019, slides),
- CMU (Dec 2018).
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
We provide almost-linear time algorithms for computing various fundamental quantities associated with random walks on directed graphs, including the stationary distribution, personalized PageRank vectors, hitting times between vertices, and escape probabilities. Previous algorithms for these problems either invoke a general purpose linear system solver or depend polynomially on condition number related quantities such as mixing time or restart probabilities.
Our result is based up several tools that may provide useful for studies into directed spectral graph theory, including: (1) a reduction from solving linear systems in arbitrary strongly connected directed graphs to Eulerian graphs; (2) spectral approximations of directed Eulerian graphs and algorithms for producing such sparse approximations; (3) approximate squaring / Gaussian elimination on Laplacians of directed graphs.
- Cornell University Theory Seminar (Oct 2017, slides),
- Duke University Algorithms Seminar (Nov 2016),
- UT Austin CS Theory Seminar (Oct 2016).
Lp Row Sampling by Lewis Weights
We give a generalization of statistical leverage scores to non-linear settings: Lp-norm Lewis weights. When 0 < p < 2, sampling the rows of an n-by-d matrix A by these weights gives A' with about dlogd rescaled rows of A such that ||Ax||p is close to ||A'x||p for all vectors x.
These weights can be computed iteratively, leading to input-sparsity time algorithms. We also give an elementary proof for the convergence of sampling by L1 Lewis weights that's arguably simpler than proofs of L2 matrix concentration bounds.