Papers

Topics

• Fast Algorithms
• Fine-grained Complexity Theory
• Discrepancy Theory and Random Matrix Theory
• Machine Learning Applications and Experiments

Fast Algorithms

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality

with Jan van den Brand, Li Chen, Yang P. Liu, Maximilian Probst Gutenberg, and Sushant Sachdeva.

To appear in FOCS 2024.

Abstract

We give the first almost-linear total time algorithm for deciding if a flow of cost at most \(F\) still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, or cost increases. This implies almost-linear time algorithms for approximating the minimum-cost flow value and \(s\)-\(t\) distance on such decremental graphs. Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically. These algorithms also improve over the current best known runtimes for statically computing minimum-cost flow, in both the randomized and deterministic settings. We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms. More precisely, our algorithm computes the flow via a sequence of \(m^{1+o(1)}\) dynamic min-ratio cut problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized \(m^{o(1)}\) time by maintaining a tree-cut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [Goranci-Räcke-Saranurak-Tan, SODA 2021] that also works in capacitated graphs. All our algorithms are deterministc, though they can be sped up further using randomized techniques while still working against an adaptive adversary.

Optimal Electrical Oblivious Routing on Expanders

with Cella Florescu, Maximilian Probst Gutenberg, and Sushant Sachdeva.

In ICALP 2024.

Abstract

In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an \(m\)-edge graph \(G = (V, E)\) that is a \(\Phi\)-expander, i.e. where \(\lvert \partial S \rvert \geq \Phi \cdot \mathrm{vol}(S)\) for every \(S \subseteq V, \mathrm{vol}(S) \leq \mathrm{vol}(V)/2\). Beyond its simplicity and structural importance, this question is well-motivated by the current state-of-the-art of fast algorithms for \(\ell_{\infty}\) oblivious routings that reduce to the expander-case which is in turn solved by electrical flow routing.
Our main result proves that the electrical routing is an \(O(\Phi^{-1} \log m)\)-competitive oblivious routing in the \(\ell_1\)- and \(\ell_\infty\)-norms. We further observe that the oblivious routing is \(O(\log^2 m)\)-competitive in the \(\ell_2\)-norm and, in fact, \(O(\log m)\)-competitive if \(\ell_2\)-localization is \(O(\log m)\) which is widely believed.
Using these three upper bounds, we can smoothly interpolate to obtain upper bounds for every \(p \in [2, \infty]\) and \(q\) given by \(1/p + 1/q = 1\). Assuming \(\ell_2\)-localization in \(O(\log m)\), we obtain that in \(\ell_p\) and \(\ell_q\), the electrical oblivious routing is \(O(\Phi^{-(1-2/p)}\log m)\) competitive. Using the currently known result for \(\ell_2\)-localization, this ratio deteriorates by at most a sublogarithmic factor for every \(p, q \neq 2\).
We complement our upper bounds with lower bounds that show that the electrical routing for any such \(p\) and \(q\) is \(\Omega(\Phi^{-(1-2/p)}\log m)\)-competitive. This renders our results in \(\ell_1\) and \(\ell_{\infty}\) unconditionally tight up to constants, and the result in any \(\ell_p\)- and \(\ell_q\)-norm to be tight in case of \(\ell_2\)-localization in \(O(\log m)\).

Arxiv

A Framework for Parallelizing Approximate Gaussian Elimination

with Yves Baumann.

In SPAA 2024.

Abstract

In a breakthrough result, Spielman and Teng (2004) developed a nearly-linear time solver for Laplacian linear equations, i.e. equations where the coefficient matrix is symmetric with non-negative diagonals and zero row sums. Since the development of the Spielman-Teng solver, there has been substantial progress, simplifying and improving their result, but obtaining a fast practical, parallel Laplacian solver remains an open problem. We present a framework for obtaining extremely simple, parallel Laplacian linear equation solvers with nearly-linear work and sublinear depth. Our framework allows us to parallelize any Laplacian solver based on repeated single-vertex approximate Gaussian elimination. We demonstrate this by parallelizing both the algorithm of Kyng and Sachdeva (2016) and the practical variant by Gao, Kyng, and Spielman (2023). Our framework is work-efficient in the sense of matching the sequential work of these algorithms. Our parallelization framework is very simple: We sample a subset of the current low-degree vertices (sparse columns), and in parallel we eliminate all vertices that are isolated in the resulting induced subgraph. This approach can be combined with any parallelizable approximate single-vertex elimination subroutine with sparse output. Given the simplicity of the approach, we believe that using it to parallelize the solver of Gao, Kyng, and Spielman (2023) is the most promising direction for obtaining practical parallel Laplacian solvers. If we additionally use a parallel spectral sparsification routine, our approach can be modified to work in polylogarithmic depth and nearly-linear work.

Conference

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow

with Li Chen, Yang P. Liu, Simon Meierhans, and Maximilian Probst Gutenberg.

To appear in STOC 2024.

Simons Institute Newsletter by Nikhil Srivastava

Abstract

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, \(s\)-\(t\) shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a \(m^{o(1)}\)-approximate minimum-ratio cycle in fully dynamic graphs in amortized \(m^{o(1)}\) time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold \(F\). By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above. Our new data structure also leads to a modular and deterministic almost-linear time algorithm for minimum-cost flow by removing the need for complicated modeling of a restricted adversary, in contrast to recent randomized and deterministic algorithms for minimum-cost flow in Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) & Brand-Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva-Sidford (FOCS 2023). At a high level, our algorithm dynamizes the \(\ell_1\) oblivious routing of Rozho\v{n}-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to extract an approximate minimum ratio cycle from the structure of the oblivious routing. To maintain the oblivious routing, we use tools from concurrent work of Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for shortest paths, in order to maintain a sparse neighborhood cover in fully dynamic graphs. To find a cycle, we first show that an approximate minimum ratio cycle can be represented as a fundamental cycle on a small set of trees resulting from the oblivious routing. Then, we find a cycle whose quality is comparable to the best tree cycle. This final cycle query step involves vertex and edge sparsification procedures reminiscent of the techniques introduced in Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), but crucially requires a more powerful dynamic spanner, which can handle far more edge insertions than prior work. We build such a spanner via a construction that hearkens back to the classic greedy spanner algorithm of Althöfer-Das-Dobkin-Joseph-Soares (Discrete & Computational Geometry 1993).

Arxiv

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications

with Simon Meierhans and Maximilian Probst Gutenberg.

To appear in STOC 2024.

Abstract

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs.
In an \(m\)-edge graph undergoing edge insertions and deletions, our data structures give the first algorithms for maintaining (a) \(m^{o(1)}\)-approximate all-pairs shortest paths (APSP) with \emph{worst-case} update time \(m^{o(1)}\) and query time \(\tilde{O}(1)\), and (b) a tree \(T\) that has diameter no larger than a subpolynomial factor times the diameter of the underlying graph, where each update is handled in amortized subpolynomial time.
In graphs undergoing only edge deletions, we develop a simpler and more efficient data structure to maintain a \((1+\epsilon)\)-approximate single-source shortest paths (SSSP) tree \(T\) in a graph undergoing edge deletions in amortized time \(m^{o(1)}\) per update.
Our data structures are deterministic. The trees we can maintain are not subgraphs of \(G\), but embed with small edge congestion into \(G\). This is in stark contrast to previous approaches and is useful for algorithms that internally use trees to route flow.
To illustrate the power of our new toolbox, we show that our SSSP data structure gives simple deterministic implementations of flow-routing MWU methods in several contexts, where previously only randomized methods had been known.
To obtain our toolbox, we give the first algorithm that, given a graph \(G\) undergoing edge insertions and deletions and a dynamic terminal set \(A\), maintains a vertex sparsifier \(H\) that approximately preserves distances between terminals in \(A\), consists of at most \(|A|m^{o(1)}\) vertices and edges, and can be updated in worst-case time \(m^{o(1)}\).
Crucially, our vertex sparsifier construction allows us to maintain a low edge-congestion embedding of \(H\) into \(G\), which is needed for our applications.

Arxiv

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

with Jan van den Brand, Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford.

In SODA 2024.

Abstract

We provide an algorithm which, with high probability, maintains a \((1-\epsilon)\)-approximate maximum flow on an undirected graph undergoing \(m\)-edge additions in amortized \(m^{o(1)} \epsilon^{-3}\) time per update. To obtain this result, we provide a more general algorithm that solves what we call the incremental, thresholded \(p\)-norm flow problem that asks to determine the first edge-insertion in an undirected graph that causes the minimum \(\ell_p\)-norm flow to decrease below a given threshold in value. Since we solve this thresholded problem, our data structure succeeds against an adaptive adversary that can only see the data structure's output. Furthermore, since our algorithm holds for \(p = 2\), we obtain improved algorithms for dynamically maintaining the effective resistance between a pair of vertices in an undirected graph undergoing edge insertions. Our algorithm builds upon previous dynamic algorithms for approximately solving the minimum-ratio cycle problem that underlie previous advances on the maximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS '22] as well as recent dynamic maximum flow algorithms [v.d.Brand-Liu-Sidford, STOC '23]. Instead of using interior point methods, which were a key component of these recent advances, our algorithm uses an optimization method based on \(\ell_p\)-norm iterative refinement and the multiplicative weight update method. This ensures a monotonicity property in the minimum-ratio cycle subproblems that allows us to apply known data structures and bypass issues arising from adaptive queries.

Arxiv

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow

with Jan van den Brand, Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford.

In FOCS 2023.

Abstract

We give a deterministic algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with \(m\) edges and polynomially bounded integral demands, costs, and capacities in \(m^{1+o(1)}\) time. As a consequence, we obtain the first improvement in the running time of deterministic algorithms for computing maximum-flow in graphs with polynomial bounded capacities since the work of Goldberg-Rao [J.ACM '98]. Our algorithm is based on the flow framework of Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS '22] that computes the optimal flow through a sequence of \(m^{1+o(1)}\) approximate undirected minimum-ratio cycles. We obtain a deterministic dynamic graph data-structure to process such a sequence of minimum-ratio cycles in an amortized \(m^{o(1)}\) time. Our two key technical contributions are 1) a deterministic analog of the vertex sparsification component of the data-structure from Chen et al. that was based on sampling random low-stretch trees, and 2) a deterministic edge sparsification component based on a new construction of dynamic spanners with explicit embeddings. Our methods can also be applied to give a deterministic data structure that maintains a fully dynamic low-stretch spanning tree on graphs with polynomially large lengths, with subpolynomial average stretch and requiring only subpolynomial amortized update time.

Arxiv

Robust and Practical Solution of Laplacian Equations by Approximate Elimination

with Yuan Gao and Daniel A. Spielman.

Manuscript.

Abstract

We introduce a new algorithm and software for solving linear equations in symmetric diagonally dominant matrices with non-positive off-diagonal entries (SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate gradient (PCG) to solve the system of linear equations. Our preconditioner is a variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS 2016). Our factorization approach is simple: we eliminate matrix rows/columns one at a time and update the remaining matrix using sampling to approximate the outcome of complete Cholesky factorization. Unlike earlier approaches, our sampling always maintains a connectivity in the remaining non-zero structure. Our algorithm comes with a tuning parameter that upper bounds the number of samples made per original entry. We implement our algorithm in Julia, providing two versions, AC and AC2, that respectively use 1 and 2 samples per original entry. We compare their single-threaded performance to that of current state-of-the-art solvers Combinatorial Multigrid (CMG), BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic Multigrid (LAMG), and MATLAB’s PCG with Incomplete Cholesky Factorization (ICC). Our evaluation uses a broad class of problems, including all large SDDM matrices from the SuiteSparse collection and diverse programmatically generated instances. Our experiments suggest that our algorithm attains a level of robustness and reliability not seen before in SDDM solvers, while retaining good performance across all instances. Our code and data are public, and we provide a tutorial on how to replicate our tests. We hope that others will adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our solver code is available on the Laplacians.jl Github Repo. Our benchmarking data and tutorial are available in our SDDM2023 Benchmark.

Arxiv

Maintaining Expander Decompositions via Sparse Cuts

with Yiding Hua, Maximilian Probst Gutenberg, and Zihang Wu.

In SODA 2023.

Abstract

In this article, we show that the algorithm of maintaining expander decompositions in graphs undergoing edge deletions directly by removing sparse cuts repeatedly can be made efficient. Formally, for an \(m\)-edge undirected graph \(G\), we say a cut \((S, \bar{S})\) is \(\phi\)-sparse if \(|E_G(S, \bar{S})| < \phi \cdot \min\{vol_G(S), vol_G(\bar{S})\}\). A \(\phi\)-expander decomposition of \(G\) is a partition of \(V\) into sets \(X_1, X_2, \ldots, X_k\) such that each cluster \(G[X_i]\) contains no \(\phi\)-sparse cut (meaning it is a \(\phi\)-expander) with \(\tilde{O}(\phi m)\) edges crossing between clusters. A natural way to compute a \(\phi\)-expander decomposition is to decompose clusters by \(\phi\)-sparse cuts until no such cut is contained in any cluster. We show that even in graphs undergoing edge deletions, a slight relaxation of this meta-algorithm can be implemented efficiently with amortized update time \(m^{o(1)}/\phi^2\). Our approach naturally extends to maintaining directed \(\phi\)-expander decompositions and \(\phi\)-expander hierarchies and thus gives a unifying framework while having simpler proofs than previous state-of-the-art work. In all settings, our algorithm matches the run-times of previous algorithms up to subpolynomial factors. Moreover, our algorithm provides stronger guarantees for \(\phi\)-expander decompositions, for example, for graphs undergoing edge deletions, our approach achieves the first sublinear \(\phi m^{o(1)}\) recourse bounds on the number of edges to become crossing between clusters. Our techniques also give by far the simplest, deterministic algorithms for maintaining Strongly-Connected Components (SCCs) in directed graphs undergoing edge deletions, and for maintaining connectivity in undirected fully-dynamic graphs, both matching the current state-of-the-art run-times up to subpolynomial factors.

Arxiv

A Simple Framework for Finding Balanced Sparse Cuts via APSP

with Li Chen, Maximilian Probst Gutenberg, and Sushant Sachdeva.

In SOSA 2023.

Abstract

We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solving unit-weight multi-commodity flows with standard ball growing arguments. Using Dijkstra's algorithm for computing the shortest paths afresh every time gives a very simple algorithm that runs in time \(\widetilde{O}(m^2/\phi)\) and finds an \(\widetilde{O}(\phi)\)-sparse balanced cut, when the given graph has a \(\phi\)-sparse balanced cut. Combining our algorithm with known deterministic data-structures for answering approximate All Pairs Shortest Paths (APSP) queries under increasing edge weights (decremental setting), we obtain a simple deterministic algorithm that finds \(m^{o(1)}\phi\)-sparse balanced cuts in \(m^{1+o(1)}/\phi\) time. Our deterministic almost-linear time algorithm matches the state-of-the-art in randomized and deterministic settings up to subpolynomial factors, while being significantly simpler to understand and analyze, especially compared to the only almost-linear time deterministic algorithm, a recent breakthrough by Chuzhoy-Gao-Li-Nanongkai-Peng-Saranurak (FOCS 2020).

Arxiv

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

with Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.

In FOCS 2022. Won the FOCS Best Paper Award.

Abstract

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with \(m\) edges and polynomially bounded integral demands, costs, and capacities in \(m^{1+o(1)}\) time. Our algorithm builds the flow through a sequence of \(m^{1+o(1)}\) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized \(m^{o(1)}\) time using a dynamic data structure.
Our framework extends to an algorithm running in \(m^{1+o(1)}\) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives an almost-linear time algorithm for several problems including entropy-regularized optimal transport, matrix scaling, \(p\)-norm flows, and isotonic regression.

Arxiv

Quanta coverage

Derandomizing Random Walks in Almost-Linear Time

with Simon Meierhans and Maximilian Probst Gutenberg.

In FOCS 2022.

Abstract

In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions imply the first deterministic almost-linear time algorithms for computing various fundamental quantities on directed graphs including stationary distributions, personalized PageRank, hitting times and escape probabilities. We obtain these results by introducing partial symmetrization, a new technique that makes the Laplacian of an Eulerian directed graph ``less directed'' in a useful sense, which may be of independent interest. The usefulness of this technique comes from two key observations: Firstly, the partially symmetrized Laplacian preconditions the original Eulerian Laplacian well in Richardson iteration, enabling us to construct a solver for the original matrix from a solver for the partially symmetrized one. Secondly, the undirected structure in the partially symmetrized Laplacian makes it possible to sparsify the matrix very crudely, i.e. with large spectral error, and still show that Richardson iterations convergence when using the sparsified matrix as a preconditioner. This allows us to develop deterministic sparsification tools for the partially symmetrized Laplacian. Together with previous reductions from directed Laplacians to Eulerian Laplacians, our technique results in the first deterministic almost-linear time algorithm for solving linear equations in directed Laplacians. To emphasize the generality of our new technique, we show that two prominent existing (randomized) frameworks for solving linear equations in Eulerian Laplacians can be derandomized in this way: the squaring-based framework of Cohen, Kelner, Peebles, Peng, Rao, Sidford and Vladu (STOC 2017) and the sparsified Cholesky-based framework of Peng and Song (STOC 2022).

Arxiv

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

with Simon Meierhans and Maximilian Probst Gutenberg.

In SODA 2022.

Abstract

Recently, Gutenberg, Williams and Wein [STOC'20] introduced a deterministic \(\tilde{O}(n^2)\) algorithm for this problem, achieving near linear time for very dense graphs. For sparse graphs, Chechik and Zhang [SODA'21] recently presented a deterministic \(\tilde{O}(m^{5/3})\) algorithm, and an adaptive randomized algorithm with run-time \(\tilde{O}(m\sqrt{n} + m^{7/5})\). This algorithm is remarkable for two reasons: 1) in very spare graphs it reaches the directed hopset barrier of \(\tilde{\Omega}(n^{3/2})\) that applied to all previous approaches for partially-dynamic SSSP [STOC'14, SODA'20, FOCS'20] \emph{and} 2) it does not resort to a directed hopset technique itself.
In this article we introduce \emph{propagation synchronization}, a new technique for controlling the error build-up on paths throughout batches of insertions. This leads us to a significant improvement of the approach in [SODA'21] yielding a \emph{deterministic} \(\tilde{O}(m^{3/2})\) algorithm for the problem. By a very careful combination of our new technique with the sampling approach from [SODA'21], we further obtain an adaptive randomized algorithm with total update time \(\tilde{O}(m^{4/3})\). This is the first partially-dynamic SSSP algorithm in sparse graphs to bypass the notorious directed hopset barrier which is often seen as the fundamental challenge towards achieving truly near-linear time algorithms.

Arxiv

Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

with Sílvia Casacuberta.

In ITCS 2022.

Abstract

We improve the current best running time value to invert sparse matrices over finite fields, lowering it to an expected \(O\big(n^{2.2131}\big)\) time for the current values of fast rectangular matrix multiplication. We achieve the same running time for the computation of the rank and nullspace of a sparse matrix over a finite field. This improvement relies on two key techniques. First, we adopt the decomposition of an arbitrary matrix into block Krylov and Hankel matrices from Eberly et al. (ISSAC 2007). Second, we show how to recover the explicit inverse of a block Hankel matrix using low displacement rank techniques for structured matrices and fast rectangular matrix multiplication algorithms. We generalize our inversion method to block structured matrices with other displacement operators and strengthen the best known upper bounds for explicit inversion of block Toeplitz-like and block Hankel-like matrices, as well as for explicit inversion of block Vandermonde-like matrices with structured blocks. As a further application, we improve the complexity of several algorithms in topological data analysis and in finite group theory.

Arxiv

Almost-linear-time Weighted \(\ell_p\)-norm Solvers in Slightly Dense Graphs via Sparsification

with Deeksha Adil, Brian Bullins, and Sushant Sachdeva

In ICALP 2021.

Abstract

We give almost-linear-time algorithms for constructing sparsifiers with \(n \text{poly}(\log n)\) edges that approximately preserve weighted \((\ell^{2}_2 + \ell^{p}_p)\) flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit \(\ell_p\) weights, and is based on expander decompositions. For voltage objectives, we give the first sparsifier construction for these objectives, which we build using graph spanners and leverage score sampling. Together with the iterative refinement framework of [Adil et al, SODA 2019], and a new multiplicative-weights based constant-approximation algorithm for mixed-objective flows or voltages, we show how to find \((1+2^{-\text{poly}(\log n)})\) approximations for weighted \(\ell_p\)-norm minimizing flows or voltages in \(p(m^{1+o(1)} + n^{4/3 + o(1)})\) time for \(p=\omega(1),\) which is almost-linear for graphs that are slightly dense (\(m \ge n^{4/3 + o(1)}\)).

Arxiv

Flows in Almost Linear Time via Adaptive Preconditioning

with Richard Peng, Sushant Sachdeva, and Di Wang.

In STOC 2019.

Abstract

We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to \((1 + 1 / poly(n))\) accuracy in almost-linear time. These problems include \(\ell_p\)-norm minimizing flow for \(p\) large (\(p \in [ω(1), o(\log^{2/3} n) ]\)), and their duals, \(\ell_p\)-norm semi-supervised learning for \(p\) close to \(1\). As \(p\) tends to infinity, \(\ell_p\)-norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives. This algorithm demonstrates that many tools previous viewed as limited to linear systems are in fact applicable to a much wider range of convex objectives. It is based on the the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC '04, SIMAX '14), but require several new tools: adaptive non-linear preconditioning, tree-routing based ultra-sparsification for mixed \(\ell_2\) and \(\ell_p\) norm objectives, and decomposing graphs into uniform expanders.

Arxiv

Conference

Iterative Refinement for \(\ell_p\)-norm Regression

with Deeksha Adil, Richard Peng, and Sushant Sachdeva.

In SODA 2019.

Abstract

We give improved algorithms for the \(\ell_{p}\)-regression problem, \(\min_{x} \|x\|_{p}\) such that \(A x=b,\) for all \(p \in (1,2) \cup (2,\infty).\) Our algorithms obtain a high accuracy solution in \(\tilde{O}_{p}(m^{\frac{|p-2|}{2p + |p-2|}}) \le \tilde{O}_{p}(m^{\frac{1}{3}})\) iterations, where each iteration requires solving an \(m \times m\) linear system, \(m\) being the dimension of the ambient space.

By maintaining an approximate inverse of the linear systems that we solve in each iteration, we give algorithms for solving \(\ell_{p}\)-regression to \(1 / \text{poly}(n)\) accuracy that run in time \(\tilde{O}_p(m^{\max\{ω, 7/3\}}),\) where \(ω\) is the matrix multiplication constant. For the current best value of \(ω> 2.37\), we can thus solve \(\ell_{p}\) regression as fast as \(\ell_{2}\) regression, for all constant \(p\) bounded away from \(1.\) Our algorithms can be combined with fast graph Laplacian linear equation solvers to give minimum \(\ell_{p}\)-norm flow / voltage solutions to \(1 / \text{poly}(n)\) accuracy on an undirected graph with \(m\) edges in \( \tilde{O}_{p}(m^{1 + \frac{|p-2|}{2p + |p-2|}}) \le \tilde{O}_{p}(m^{\frac{4}{3}}) \) time.

For sparse graphs and for matrices with similar dimensions, our iteration counts and running times improve on the \(p\)-norm regression algorithm by [Bubeck-Cohen-Lee-Li STOC`18] and general-purpose convex optimization algorithms. At the core of our algorithms is an iterative refinement scheme for \(\ell_{p}\)-norms, using the smoothed \(\ell_{p}\)-norms introduced in the work of Bubeck et al. Given an initial solution, we construct a problem that seeks to minimize a quadratically-smoothed \(\ell_{p}\) norm over a subspace, such that a crude solution to this problem allows us to improve the initial solution by a constant factor, leading to algorithms with fast convergence.

Arxiv

Conference

Solving Directed Laplacians in Nearly Linear Time through Sparse LU Factorizations

with Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford.

In FOCS 2018.

Abstract

We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an \(n \times n\) Eulerian directed Laplacian with \(m\) nonzero entries, we show how to compute an \(ε\)-approximate solution in time \(O(m \log^{O(1)} (n) \log (1/ε))\). Through reductions from [Cohen et al. FOCS'16] , this gives the first nearly-linear time algorithms for computing \(ε\)-approximate solutions to row or column diagonally dominant linear systems (including arbitrary directed Laplacians) and computing \(ε\)-approximations to various properties of random walks on directed graphs, including stationary distributions, personalized PageRank vectors, hitting times, and escape probabilities. These bounds improve upon the recent almost-linear algorithms of [Cohen et al. STOC'17], which gave an algorithm to solve Eulerian Laplacian systems in time \(O((m+n2^{O(\sqrt{\log n \log \log n})})\log^{O(1)}(n ε^{-1}))\).

To achieve our results, we provide a structural result that we believe is of independent interest. We show that Laplacians of all strongly connected directed graphs have sparse approximate LU-factorizations. That is, for every such directed Laplacian \({\mathbf{L}}\), there is a lower triangular matrix \(\boldsymbol{\mathit{\mathfrak{L}}}\) and an upper triangular matrix \(\boldsymbol{\mathit{\mathfrak{U}}}\), each with at most \(\tilde{O}(n)\) nonzero entries, such that their product \(\boldsymbol{\mathit{\mathfrak{L}}} \boldsymbol{\mathit{\mathfrak{U}}}\) spectrally approximates \({\mathbf{L}}\) in an appropriate norm. This claim can be viewed as an analogue of recent work on sparse Cholesky factorizations of Laplacians of undirected graphs. We show how to construct such factorizations in nearly-linear time and prove that, once constructed, they yield nearly-linear time algorithms for solving directed Laplacian systems.

Arxiv

Conference

Incomplete Nested Dissection

with Richard Peng, Robert Schwieterman, and Peng Zhang.

In STOC 2018.

Abstract

We present an asymptotically faster algorithm for solving linear systems in well-structured 3-dimensional truss stiffness matrices. These linear systems arise from linear elasticity problems, and can be viewed as extensions of graph Laplacians into higher dimensions. Faster solvers for the 2-D variants of such systems have been studied using generalizations of tools for solving graph Laplacians [Daitch-Spielman CSC'07, Shklarski-Toledo SIMAX'08].

Given a 3-dimensional truss over \(n\) vertices which is formed from a union of \(k\) convex structures (tetrahedral meshes) with bounded aspect ratios, whose individual tetrahedrons are also in some sense well-conditioned, our algorithm solves a linear system in the associated stiffness matrix up to accuracy \(ε\) in time \(O(k^{1/3} n^{5/3} \log (1 / ε))\). This asymptotically improves the running time \(O(n^2)\) by Nested Dissection for all \(k \ll n\).

We also give a result that improves on Nested Dissection even when we allow any aspect ratio for each of the \(k\) convex structures (but we still require well-conditioned individual tetrahedrons). In this regime, we improve on Nested Dissection for \(k \ll n^{1/44}\).

The key idea of our algorithm is to combine nested dissection and support theory. Both of these techniques for solving linear systems are well studied, but usually separately. Our algorithm decomposes a 3-dimensional truss into separate and balanced regions with small boundaries. We then bound the spectrum of each such region separately, and utilize such bounds to obtain improved algorithms by preconditioning with partial states of separator-based Gaussian elimination.

Arxiv

Conference

Approximate Gaussian Elimination

Rasmus Kyng.

My PhD dissertation, 2017.

Thesis

Sampling Random Spanning Trees Faster than Matrix Multiplication

with David Durfee, John Peebles, Anup B. Rao, and Sushant Sachdeva.

In STOC 2017.

Abstract

We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in \(\tilde{O}(n^{4/3}m^{1/2}+n^{2})\) time (The \(\tilde{O}(\cdot)\) notation hides \(\operatorname{polylog}(n)\) factors). The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, \(O(n^ω)\). For the special case of unweighted graphs, this improves upon the best previously known running time of \(\tilde{O}(\min\{n^ω,m\sqrt{n},m^{4/3}\})\) for \(m \gg n^{5/3}\) (Colbourn et al. '96, Kelner-Madry '09, Madry et al. '15).

The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinant-based and random walk-based techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement). As part of our algorithm, we show how to compute \(ε\)-approximate effective resistances for a set \(S\) of vertex pairs via approximate Schur complements in \(\tilde{O}(m+(n + |S|)ε^{-2})\) time, without using the Johnson-Lindenstrauss lemma which requires \(\tilde{O}( \min\{(m + |S|)ε^{-2}, m+nε^{-4} +|S|ε^{-2}\})\) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn't sufficiently accurate.

Arxiv

Conference

A Framework for Analyzing Resparsification Algorithms

with Jakub Pachocki, Richard Peng, and Sushant Sachdeva.

In SODA 2017.

Abstract

A spectral sparsifier of a graph \(G\) is a sparser graph \(H\) that approximately preserves the quadratic form of \(G\), i.e. for all vectors \(x\), \(x^T L_G x \approx x^T L_H x\), where \(L_G\) and \(L_H\) denote the respective graph Laplacians. Spectral sparsifiers generalize cut sparsifiers, and have found many applications in designing graph algorithms. In recent years, there has been interest in computing spectral sparsifiers in semi-streaming and dynamic settings. Natural algorithms in these settings often involve repeated sparsification of a graph, and accumulation of errors across these steps. We present a framework for analyzing algorithms that perform repeated sparsifications that only incur error corresponding to a single sparsification step, leading to better results for many resparsification-based algorithms. As an application, we show how to maintain a spectral sparsifier in the semi-streaming setting: We present a simple algorithm that, for a graph \(G\) on \(n\) vertices and \(m\) edges, computes a spectral sparsifier of \(G\) with \(O(n \log n)\) edges in a single pass over \(G\), using only \(O(n \log n)\) space, and \(O(m \log^2 n)\) total time. This improves on previous best semi-streaming algorithms for both spectral and cut sparsifiers by a factor of \(\log{n}\) in both space and runtime. The algorithm extends to semi-streaming row sampling for general PSD matrices. We also use our framework to combine a spectral sparsification algorithm by Koutis with improved spanner constructions to give a parallel algorithm for constructing \(O(n\log^2{n}\log\log{n})\) sized spectral sparsifiers in \(O(m\log^2{n}\log\log{n})\) time. This is the best known combinatorial graph sparsification algorithm.The size of the sparsifiers is only a factor \(\log{n}\log\log{n}\) more than ones produced by numerical routines.

Arxiv

Conference

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

with Sushant Sachdeva.

In FOCS 2016.

Abstract

We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization, the version of Gaussian elimination for symmetric matrices. This is the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. The crux of our analysis is a novel concentration bound for matrix martingales where the differences are sums of conditionally independent variables.

Arxiv

Conference

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

with Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman.

In STOC 2016.

Abstract

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians, a generalization of Laplacian matrices that arise in many problems in image and signal processing. We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the original matrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians. independent variables.

Arxiv

Conference

Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)-norms

with Anup B. Rao and Sushant Sachdeva.

In NIPS 2015.

Abstract

Given a directed acyclic graph \(G,\) and a set of values \(y\) on the vertices, the Isotonic Regression of \(y\) is a vector \(x\) that respects the partial order described by \(G,\) and minimizes \(||x-y||,\) for a specified norm. This paper gives improved algorithms for computing the Isotonic Regression for all weighted \(\ell_{p}\)-norms with rigorous performance guarantees. Our algorithms are quite practical, and their variants can be implemented to run fast in practice.

Arxiv

Conference

Our implementation of the least-squares Isotonic regression algorithm is available on the Isotonic Github repository.

Algorithms for Lipschitz Learning on Graphs

with Anup B. Rao, Daniel A. Spielman, and Sushant Sachdeva.

In COLT 2015.

Abstract

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large \(p\) of \(p\)-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time \(\widetilde{O} (m n)\). The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform \(l_{0}\)-regularization on the given values in polynomial time and \(l_{1}\)-regularization on the initial function values and on graph edge weights in time \(\widetilde{O} (m^{3/2})\).

Arxiv

Conference

Our implementations of the lex-minimization algorithms are available on the YINSlex Github repository.

Solving SDD Linear Systems in Nearly \( m\log^{1/2}n \) Time

with Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao and Shen Chen Xu.

In STOC 2014.

Abstract

We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems with m non-zero entries to a relative error of ε in O(m log^1/2n log^cn log(1/ε)) time. Our approach follows the recursive preconditioning framework, which aims to reduce graphs to trees using iterative methods. We improve two key components of this framework: random sampling and tree embeddings. Both of these components are used in a variety of other algorithms, and our approach also extends to the dual problem of computing electrical flows.

We show that preconditioners constructed by random sampling can perform well without meeting the standard requirements of iterative methods. In the graph setting, this leads to ultra-sparsifiers that have optimal behavior in expectation.

The improved running time makes previous low stretch embedding algorithms the running time bottleneck in this framework. In our analysis, we relax the requirement of these embeddings to snowflake spaces. We then obtain a two-pass approach algorithm for constructing optimal embeddings in snowflake spaces that runs in O(m log log n) time. This algorithm is also readily parallelizable.

Conference

The paper Solving SDD Linear Systems in Nearly \( m\log^{1/2}n \) Time was a merged submission of the following two papers:

Preconditioning in Expectation

with Michael B. Cohen, Jakub W. Pachocki, Richard Peng, and Anup B. Rao.

Abstract

We show that preconditioners constructed by random sampling can perform well without meeting the standard requirements of iterative methods. When applied to graph Laplacians, this leads to ultra-sparsifiers that in expectation behave as the nearly-optimal ones given by [Kolla-Makarychev-Saberi-Teng STOC`10]. Combining this with the recursive preconditioning framework by [Spielman-Teng STOC`04] and improved embedding algorithms, this leads to algorithms that solve symmetric diagonally dominant linear systems and electrical flow problems in expected time close to \(m\log^{1/2}n\).

Arxiv

Conference

Stretching Stretch

Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, and Shen Chen Xu.

Abstract

We give a generalized definition of stretch that simplifies the efficient construction of low-stretch embeddings suitable for graph algorithms. The generalization, based on discounting highly stretched edges by taking their \(p\)-th power for some \(0 < p < 1\), is directly related to performances of existing algorithms. This discounting of high-stretch edges allows us to treat many classes of edges with coarser granularity. It leads to a two-pass approach that combines bottom-up clustering and top-down decompositions to construct these embeddings in \(\mathcal{O}(m\log\log{n})\) time. Our algorithm parallelizes readily and can also produce generalizations of low-stretch subgraphs.

Arxiv

Fine-grained Complexity Theory

Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets

with Ming Ding, Maximilian Probst Gutenberg, and Peng Zhang.

In ICALP 2022.

Abstract

We study linear equations in combinatorial Laplacians of k-dimensional simplicial complexes (k-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacians play a crucial role in homology and are a central tool in topology. Beyond this, they have various applications in data analysis and physical modeling problems. It is known that nearly-linear time solvers exist for graph Laplacians. However, nearly-linear time solvers for combinatorial Laplacians are only known for restricted classes of complexes. This paper shows that linear equations in combinatorial Laplacians of 2-complexes are as hard to solve as general linear equations. More precisely, for any constant c≥1, if we can solve linear equations in combinatorial Laplacians of 2-complexes to high accuracy in time \(\tilde{O}(\text{# of nonzero coefficients})^c\), then we can solve general linear equations with polynomially bounded integer coefficients and condition numbers to high accuracy in time \(\tilde{O}(\text{# of nonzero coefficients})^c\). We prove this by a nearly-linear time reduction from general linear equations to combinatorial Laplacians of 2-complexes. Our reduction preserves the sparsity of the problem instances up to poly-logarithmic factors.

Arxiv

Two-Commodity Flow is as Hard as Linear Programming

with Ming Ding and Peng Zhang.

In ICALP 2022.

Abstract

We give a nearly-linear time reduction that encodes any linear program as a 2-commodity flow problem with only a polylogarithmic blow-up in size. Our reduction applies to high-accuracy approximation algorithms and exact algorithms. Given an approximate solution to the 2-commodity flow problem, we can extract a solution to the linear program in linear time with only a polynomial factor increase in the error. This implies that any algorithm that solves the 2-commodity flow problem can solve linear programs in essentially the same time. Given a directed graph with edge capacities and two source-sink pairs, the goal of the 2-commodity flow problem is to maximize the sum of the flows routed between the two source-sink pairs subject to edge capacities and flow conservation. A 2-commodity flow problem can be formulated as a linear program, which can be solved to high accuracy in almost the current matrix multiplication time (Cohen-Lee-Song JACM'21). In this paper, we show that linear programs can be approximately solved, to high accuracy, using 2-commodity flow as well. As a corollary, if a 2-commodity flow problem can be approximately solved in time \(O(|E|^c \operatorname{polylog}(U|E|\epsilon^{-1}))\), where \(E\) is the graph edge set, \(U\) is the ratio of maximum to minimum edge capacity, \(\epsilon\) is the multiplicative error parameter, and \(c\) is a constant greater than or equal to 1, then a linear program with integer coefficients and feasible set radius \(r\) can be approximately solved in time \(O(N^c \operatorname{polylog}((r+1)X\epsilon^{-1}))\), where \(N\) is the number of nonzeros and \(X\) is the largest magnitude of the coefficients. Thus a solver for 2-commodity flow with running time exponent \(c < \omega\), where \(\omega < 2.37286\) is the matrix multiplication constant, would improve the running time for solving sparse linear programs. Our proof follows the outline of Itai’s polynomial-time reduction of a linear program to a 2-commodity flow problem (JACM’78). Itai's reduction shows that exactly solving 2-commodity flow and exactly solving linear programming are polynomial-time equivalent. We improve Itai’s reduction to preserve the sparsity of all the intermediate steps. In addition, we establish an error bound for approximately solving each intermediate problem in the reduction, and show that the accumulated error is polynomially bounded. We remark that our reduction does not run in strongly polynomial time and that it is open whether 2-commodity flow and linear programming are equivalent in strongly polynomial time.

Arxiv

On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization

with Nicolas Emmenegger and Ahad N. Zehmakan.

In AISTATS 2022 and in the ICML 2021 workshop 'Beyond first-order methods in ML systems'.

Abstract

We prove lower bounds for higher-order methods in smooth non-convex finite-sum optimization. Our contribution is threefold: We first show that a deterministic algorithm cannot profit from the finite-sum structure of the objective, and that simulating a pth-order regularized method on the whole function by constructing exact gradient information is optimal up to constant factors. We further show lower bounds for randomized algorithms and compare them with the best known upper bounds. To address some gaps between the bounds, we propose a new second-order smoothness assumption that can be seen as an analogue of the first-order mean-squared smoothness assumption. We prove that it is sufficient to ensure state-of-the-art convergence guarantees, while allowing for a sharper lower bound.

Arxiv

Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard

with Di Wang and Peng Zhang.

In SODA 2020.

Abstract

We study the complexity of approximately solving packing linear programs. In the Real RAM model, it is known how to solve packing LPs with N non-zeros in time Õ(N/ϵ). We investigate whether the ϵ dependence in the running time can be improved.

Our first main result relates the difficulty of this problem to hardness assumptions for solving dense linear equations. We show that, in the Real RAM model, unless linear equations in matrices n × n with condition number O(n¹⁰) can be solved to ϵ accuracy faster than Õ(n^2.01 log(1/ϵ)), no algorithm (1−ϵ)-approximately solves a O(n)×O(n) packing LPs (where N = O(n²)) in time Õ(n²ϵ^−0.0003). It would be surprising to solve linear equations in the Real RAM model this fast, as we currently cannot solve them faster than Õ(n^ω), where ω denotes the exponent in the running time for matrix multiplication in the Real RAM model (and equivalently matrix inversion). The current best bound on this exponent is roughly ω ≤ 2.372. Note, however, that a fast solver for linear equations does not directly imply faster matrix multiplication. But, our reduction shows that if fast and accurate packing LP solvers exist, then either linear equations can be solved much faster than matrix multiplication or the matrix multiplication constant is very close to 2.

Instantiating the same reduction with different parameters, we show that unless linear equations in matrices with condition number O(n^1.5) can be solved to ϵ accuracy faster than Õ(n^2.372 log(1/ϵ)), no algorithm (1 – ϵ)-approximately solves packing LPs in time Õ(n²ϵ^−0.067). Thus smaller improvements in the exponent for ϵ in the running time of Packing LP solvers also imply improvements in the current state-of-the-art for solving linear equations.

Our second main result relates the difficulty of approximately solving packing linear programs to hardness assumptions for solving sparse linear equations: In the Real RAM model, unless well-conditioned sparse systems of linear equations can be solved faster than Õ((no. non-zeros of matrix) ), no algorithm (1 – ϵ)-approximately solves packing LPs with N non-zeros in time Õ(Nϵ^−0.165). This running time of Õ((no. non-zeros of matrix) ) is obtained by the classical Conjugate Gradient algorithm by a standard analysis. Our reduction implies that if sufficiently good packing LP solvers exist, then this long-standing best-known bound on the running time for solving well-conditioned systems of linear equations is sub-optimal. While we prove results in the Real RAM model, our condition number assumptions ensure that our results can be translated to fixed point arithmetic with (log n)^O(1) bits per number.

Conference

Hardness Results for Structured Linear Systems

with Peng Zhang.

In FOCS 2017. Won the Machtey Award for Best Student Paper.

Abstract

We show that if the nearly-linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly larger families of linear systems, then they can be used to quickly solve all systems of linear equations over the reals. This result can be viewed either positively or negatively: either we will develop nearly-linear time algorithms for solving all systems of linear equations over the reals, or progress on the families we can solve in nearly-linear time will soon halt.

Arxiv

Conference

Discrepancy Theory and Random Matrix Theory

Scalar and Matrix Chernoff Bounds from \(\ell_{\infty}\)-Independence

with Tali Kaufman and Federico Solda.

In SODA 2022.

Abstract

We present new scalar and matrix Chernoff-style concentration bounds for a broad class of probability distributions over the binary hypercube \(\{0,1\}^n\). Motivated by recent tools developed for the study of mixing times of Markov chains on discrete distributions, we say that a distribution is \(\ell_\infty\)-independent when the infinity norm of its influence matrix \(\mathcal{I}\) is bounded by a constant. We show that any distribution which is \(\ell_\infty\)-infinity independent satisfies a matrix Chernoff bound that matches the matrix Chernoff bound for independent random variables due to Tropp. Our matrix Chernoff bound is a broad generalization and strengthening of the matrix Chernoff bound of Kyng and Song (FOCS'18). Using our bound, we can conclude as a corollary that a union of \(O(\log|V|)\) random spanning trees gives a spectral graph sparsifier of a graph with \(|V|\) vertices with high probability, matching results for independent edge sampling, and matching lower bounds from Kyng and Song.

Arxiv

Four Deviations Suffice for Rank 1 Matrices

with Kyle Luh and Zhao Song.

In Advances in Mathematics, Volume 375, 2 December 2020.

Abstract

We prove a matrix discrepancy bound that strengthens the famous Kadison-Singer result of Marcus, Spielman, and Srivastava. Consider any independent scalar random variables \(ξ_1, \ldots, ξ_n\) with finite support, e.g. \(\{ \pm 1 \}\) or \(\{ 0,1 \}\)-valued random variables, or some combination thereof. Let \(u_1, \dots, u_n \in \mathbb{C}^m\) and \( σ^2 = \left\| \sum_{i=1}^n \text{Var}[ ξ_i ] (u_i u_i^{*})^2 \right\|.\) Then there exists a choice of outcomes \(\varepsilon_1,\ldots,\varepsilon_n\) in the support of \(ξ_1, \ldots, ξ_n\) s.t. \( \left \|\sum_{i=1}^n \mathbb{E} [ ξ_i] u_i u_i^* - \sum_{i=1}^n \varepsilon_i u_i u_i^* \right \| \leq 4 σ.\) A simple consequence of our result is an improvement of a Lyapunov-type theorem of Akemann and Weaver.

Arxiv

Journal

A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees

with Zhao Song.

In FOCS 2018.

Abstract

Strongly Rayleigh distributions are a class of negatively dependent distributions of binary-valued random variables [Borcea, Branden, Liggett JAMS 09]. Recently, these distributions have played a crucial role in the analysis of algorithms for fundamental graph problems, e.g. Traveling Salesman Problem [Gharan, Saberi, Singh FOCS 11]. We prove a new matrix Chernoff bound for Strongly Rayleigh distributions.

As an immediate application, we show that adding together the Laplacians of \(ε^{-2} \log^2 n\) random spanning trees gives an \((1\pm ε)\) spectral sparsifiers of graph Laplacians with high probability. Thus, we positively answer an open question posed in [Baston, Spielman, Srivastava, Teng JACM 13]. Our number of spanning trees for spectral sparsifier matches the number of spanning trees required to obtain a cut sparsifier in [Fung, Hariharan, Harvey, Panigraphi STOC 11]. The previous best result was by naively applying a classical matrix Chernoff bound which requires \(ε^{-2} n \log n\) spanning trees. For the tree averaging procedure to agree with the original graph Laplacian in expectation, each edge of the tree should be reweighted by the inverse of the edge leverage score in the original graph. We also show that when using this reweighting of the edges, the Laplacian of single random tree is bounded above in the PSD order by the original graph Laplacian times a factor \(\log n\) with high probability, i.e. \(L_T \preceq O(\log n) L_G\).

We show a lower bound that almost matches our last result, namely that in some graphs, with high probability, the random spanning tree is \(\it{not}\) bounded above in the spectral order by \(\frac{\log n}{\log\log n}\) times the original graph Laplacian. We also show a lower bound that in \(ε^{-2} \log n\) spanning trees are necessary to get a \((1\pm ε)\) spectral sparsifier.

Arxiv

Conference

Machine Learning Applications and Experiments

Robust and Practical Solution of Laplacian Equations by Approximate Elimination

with Yuan Gao and Daniel A. Spielman.

Manuscript.

Abstract

We introduce a new algorithm and software for solving linear equations in symmetric diagonally dominant matrices with non-positive off-diagonal entries (SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate gradient (PCG) to solve the system of linear equations. Our preconditioner is a variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS 2016). Our factorization approach is simple: we eliminate matrix rows/columns one at a time and update the remaining matrix using sampling to approximate the outcome of complete Cholesky factorization. Unlike earlier approaches, our sampling always maintains a connectivity in the remaining non-zero structure. Our algorithm comes with a tuning parameter that upper bounds the number of samples made per original entry. We implement our algorithm in Julia, providing two versions, AC and AC2, that respectively use 1 and 2 samples per original entry. We compare their single-threaded performance to that of current state-of-the-art solvers Combinatorial Multigrid (CMG), BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic Multigrid (LAMG), and MATLAB’s PCG with Incomplete Cholesky Factorization (ICC). Our evaluation uses a broad class of problems, including all large SDDM matrices from the SuiteSparse collection and diverse programmatically generated instances. Our experiments suggest that our algorithm attains a level of robustness and reliability not seen before in SDDM solvers, while retaining good performance across all instances. Our code and data are public, and we provide a tutorial on how to replicate our tests. We hope that others will adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our solver code is available on the Laplacians.jl Github Repo. Our benchmarking data and tutorial are available in our SDDM2023 Benchmark.

Arxiv

This paper describes ApproxChol, the Laplacian solver in Laplacians.jl.

Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)-norms

with Anup B. Rao and Sushant Sachdeva.

In NIPS 2015.

Abstract

Given a directed acyclic graph \(G,\) and a set of values \(y\) on the vertices, the Isotonic Regression of \(y\) is a vector \(x\) that respects the partial order described by \(G,\) and minimizes \(||x-y||,\) for a specified norm. This paper gives improved algorithms for computing the Isotonic Regression for all weighted \(\ell_{p}\)-norms with rigorous performance guarantees. Our algorithms are quite practical, and their variants can be implemented to run fast in practice.

Arxiv

Conference

Our implementation of the least-squares Isotonic regression algorithm is available on the Isotonic Github repository.

Algorithms for Lipschitz Learning on Graphs

with Anup B. Rao, Daniel A. Spielman, and Sushant Sachdeva.

In COLT 2015.

Abstract

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large \(p\) of \(p\)-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time \(\widetilde{O} (m n)\). The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform \(l_{0}\)-regularization on the given values in polynomial time and \(l_{1}\)-regularization on the initial function values and on graph edge weights in time \(\widetilde{O} (m^{3/2})\).

Arxiv

Conference

Our implementations of the lex-minimization algorithms are available on the YINSlex Github repository.