AJArun Jambulapati

Arun Jambulapati

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Arun Jambulapati has a total of 12 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

    by Arun Jambulapati, Aaron Sidford

    In this paper we provide an $O(m (\log \log n)^{O(1)} \log(1/\epsilon))$-expected time algorithm for solving Laplacian systems on $n$-node $m$-edge graphs, improving improving upon the previous best expected runtime of $O(m \sqrt{\log n} (\log \log n)^{O(1)} \log(1/\epsilon))$ achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of $\ell_p$-stretch graph approximations with improved stretch and sparsity bounds. Additionally, as motivation for this work, we show that for every set of vectors in $\mathbb{R}^d$ (not just those induced by graphs) and all $k > 1$ there exist ultrasparsifiers with $d-1 + O(d/\sqrt{k})$ re-weighted vectors of relative condition number at most $k$. For small $k$, this improves upon the previous best known relative condition number of $\tilde{O}(\sqrt{k \log d})$, which is only known for the graph case.

  • Open Access

    Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

    by Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian

    Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [She17], optimal transport [JST19], and bipartite matching [AJJ+22]. We develop efficient near-linear time, high-accuracy solvers for regularized variants of these games. Beyond the immediate applications of such solvers for computing Sinkhorn distances, a prominent tool in machine learning, we show that these solvers can be used to obtain improved running times for maintaining a (fractional) $\epsilon$-approximate maximum matching in a dynamic decremental bipartite graph against an adaptive adversary. We give a generic framework which reduces this dynamic matching problem to solving regularized graph-structured optimization problems to high accuracy. Through our reduction framework, our regularized box-simplex game solver implies a new algorithm for dynamic decremental bipartite matching in total time $\tilde{O}(m \cdot \epsilon^{-3})$, from an initial graph with $m$ edges and $n$ nodes. We further show how to use recent advances in flow optimization [CKL+22] to improve our runtime to $m^{1 + o(1)} \cdot \epsilon^{-2}$, thereby demonstrating the versatility of our reduction-based approach. These results improve upon the previous best runtime of $\tilde{O}(m \cdot \epsilon^{-4})$ [BGS20] and illustrate the utility of using regularized optimization problem solvers for designing dynamic algorithms.

  • Open Access

    Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

    by Deeksha Adil, Brian Bullins, Arun Jambulapati, Sushant Sachdeva

    In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for $p^{th}$-order smooth, monotone operators -- a problem that generalizes convex optimization and saddle-point problems. Recent works (Bullins and Lai (2020), Lin and Jordan (2021), Jiang and Mokhtari (2022)) present methods that achieve a rate of $\tilde{O}(\epsilon^{-2/(p+1)})$ for $p\geq 1$, extending results by (Nemirovski (2004)) and (Monteiro and Svaiter (2012)) for $p=1,2$. A drawback to these approaches, however, is their reliance on a line search scheme. We provide the first $p^{\textrm{th}}$-order method that achieves a rate of $O(\epsilon^{-2/(p+1)}).$ Our method does not rely on a line search routine, thereby improving upon previous rates by a logarithmic factor. Building on the Mirror Prox method of Nemirovski (2004), our algorithm works even in the constrained, non-Euclidean setting. Furthermore, we prove the optimality of our algorithm by constructing matching lower bounds. These are the first lower bounds for smooth MVIs beyond convex optimization for $p > 1$. This establishes a separation between solving smooth MVIs and smooth convex optimization, and settles the oracle complexity of solving $p^{\textrm{th}}$-order smooth MVIs.

  • Open Access

    Improved Iteration Complexities for Overconstrained $p$-Norm Regression

    by Arun Jambulapati, Yang P. Liu, Aaron Sidford

    In this paper we obtain improved iteration complexities for solving $\ell_p$ regression. We provide methods which given any full-rank $\mathbf{A} \in \mathbb{R}^{n \times d}$ with $n \geq d$, $b \in \mathbb{R}^n$, and $p \geq 2$ solve $\min_{x \in \mathbb{R}^d} \left\|\mathbf{A} x - b\right\|_p$ to high precision in time dominated by that of solving $\widetilde{O}_p(d^{\frac{p-2}{3p-2}})$ linear systems in $\mathbf{A}^\top \mathbf{D} \mathbf{A}$ for positive diagonal matrices $\mathbf{D}$. This improves upon the previous best iteration complexity of $\widetilde{O}_p(n^{\frac{p-2}{3p-2}})$ (Adil, Kyng, Peng, Sachdeva 2019). As a corollary, we obtain an $\widetilde{O}(d^{1/3}\epsilon^{-2/3})$ iteration complexity for approximate $\ell_\infty$ regression. Further, for $q \in (1, 2]$ and dual norm $q = p/(p-1)$ we provide an algorithm that solves $\ell_q$ regression in $\widetilde{O}(d^{\frac{p-2}{2p-2}})$ iterations. To obtain this result we analyze row reweightings (closely inspired by $\ell_p$-norm Lewis weights) which allow a closer connection between $\ell_2$ and $\ell_p$ regression. We provide adaptations of two different iterative optimization frameworks which leverage this connection and yield our results. The first framework is based on iterative refinement and multiplicative weights based width reduction and the second framework is based on highly smooth acceleration. Both approaches yield $\widetilde{O}_p(d^{\frac{p-2}{3p-2}})$ iteration methods but the second has a polynomial dependence on $p$ (as opposed to the exponential dependence of the first algorithm) and provides a new alternative to the previous state-of-the-art methods for $\ell_p$ regression for large $p$.

  • Open Access

    Fast and Near-Optimal Diagonal Preconditioning

    by Arun Jambulapati, Jerry Li, Christopher Musco, Aaron Sidford, Kevin Tian

    The convergence rates of iterative methods for solving a linear system $\mathbf{A} x = b$ typically depend on the condition number of the matrix $\mathbf{A}$. Preconditioning is a common way of speeding up these methods by reducing that condition number in a computationally inexpensive way. In this paper, we revisit the decades-old problem of how to best improve $\mathbf{A}$'s condition number by left or right diagonal rescaling. We make progress on this problem in several directions. First, we provide new bounds for the classic heuristic of scaling $\mathbf{A}$ by its diagonal values (a.k.a. Jacobi preconditioning). We prove that this approach reduces $\mathbf{A}$'s condition number to within a quadratic factor of the best possible scaling. Second, we give a solver for structured mixed packing and covering semidefinite programs (MPC SDPs) which computes a constant-factor optimal scaling for $\mathbf{A}$ in $\widetilde{O}(\text{nnz}(\mathbf{A}) \cdot \text{poly}(\kappa^\star))$ time; this matches the cost of solving the linear system after scaling up to a $\widetilde{O}(\text{poly}(\kappa^\star))$ factor. Third, we demonstrate that a sufficiently general width-independent MPC SDP solver would imply near-optimal runtimes for the scaling problems we consider, and natural variants concerned with measures of average conditioning. Finally, we highlight connections of our preconditioning techniques to semi-random noise models, as well as applications in reducing risk in several statistical regression models.

  • Open Access

    Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing

    by Arun Jambulapati, Jerry Li, Kevin Tian

    We develop two methods for the following fundamental statistical task: given an $\epsilon$-corrupted set of $n$ samples from a $d$-dimensional sub-Gaussian distribution, return an approximate top eigenvector of the covariance matrix. Our first robust PCA algorithm runs in polynomial time, returns a $1 - O(\epsilon\log\epsilon^{-1})$-approximate top eigenvector, and is based on a simple iterative filtering approach. Our second, which attains a slightly worse approximation factor, runs in nearly-linear time and sample complexity under a mild spectral gap assumption. These are the first polynomial-time algorithms yielding non-trivial information about the covariance of a corrupted sub-Gaussian distribution without requiring additional algebraic structure of moments. As a key technical tool, we develop the first width-independent solvers for Schatten-$p$ norm packing semidefinite programs, giving a $(1 + \epsilon)$-approximate solution in $O(p\log(\tfrac{nd}{\epsilon})\epsilon^{-1})$ input-sparsity time iterations (where $n$, $d$ are problem dimensions).

  • Open Access

    Towards Optimal Running Times for Optimal Transport

    by Jose Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford

    In this work, we provide faster algorithms for approximating the optimal transport distance, e.g. earth mover's distance, between two discrete probability distributions $\mu, \nu \in \Delta^n$. Given a cost function $C : [n] \times [n] \to \mathbb{R}_{\geq 0}$ where $C(i,j) \leq 1$ quantifies the penalty of transporting a unit of mass from $i$ to $j$, we show how to compute a coupling $X$ between $r$ and $c$ in time $\widetilde{O}\left(n^2 /\epsilon \right)$ whose expected transportation cost is within an additive $\epsilon$ of optimal. This improves upon the previously best known running time for this problem of $\widetilde{O}\left(\text{min}\left\{ n^{9/4}/\epsilon, n^2/\epsilon^2 \right\}\right)$. We achieve our results by providing reductions from optimal transport to canonical optimization problems for which recent algorithmic efforts have provided nearly-linear time algorithms. Leveraging nearly linear time algorithms for solving packing linear programs and for solving the matrix balancing problem, we obtain two separate proofs of our stated running time. Further, one of our algorithms is easily parallelized and can be implemented with depth $\widetilde{O}(1/\epsilon)$. Moreover, we show that further algorithmic improvements to our result would be surprising in the sense that any improvement would yield an $o(n^{2.5})$ algorithm for \textit{maximum cardinality bipartite matching}, for which currently the only known algorithms for achieving such a result are based on fast-matrix multiplication.

  • Open Access

    Parallel Reachability in Almost Linear Work and Square Root Depth

    by Arun Jambulapati, Yang P. Liu, Aaron Sidford

    In this paper we provide a parallel algorithm that given any $n$-node $m$-edge directed graph and source vertex $s$ computes all vertices reachable from $s$ with $\tilde{O}(m)$ work and $n^{1/2 + o(1)}$ depth with high probability in $n$ . This algorithm also computes a set of $\tilde{O}(n)$ edges which when added to the graph preserves reachability and ensures that the diameter of the resulting graph is at most $n^{1/2 + o(1)}$. Our result improves upon the previous best known almost linear work reachability algorithm due to Fineman which had depth $\tilde{O}(n^{2/3})$. Further, we show how to leverage this algorithm to achieve improved distributed algorithms for single source reachability in the CONGEST model. In particular, we provide a distributed algorithm that given a $n$-node digraph of undirected hop-diameter $D$ solves the single source reachability problem with $\tilde{O}(n^{1/2} + n^{1/3 + o(1)} D^{2/3})$ rounds of the communication in the CONGEST model with high probability in $n$. Our algorithm is nearly optimal whenever $D = O(n^{1/4 - \epsilon})$ for any constant $\epsilon > 0$ and is the first nearly optimal algorithm for general graphs whose diameter is $\Omega(n^\delta)$ for any constant $\delta$.

  • Open Access

    Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices

    by Arun Jambulapati, Kirankumar Shiragur, Aaron Sidford

    In this paper we show how to recover a spectral approximations to broad classes of structured matrices using only a polylogarithmic number of adaptive linear measurements to either the matrix or its inverse. Leveraging this result we obtain faster algorithms for variety of linear algebraic problems. Key results include: $\bullet$ A nearly linear time algorithm for solving the inverse of symmetric $M$-matrices, a strict superset of Laplacians and SDD matrices. $\bullet$ An $\tilde{O}(n^2)$ time algorithm for solving $n \times n$ linear systems that are constant spectral approximations of Laplacians or more generally, SDD matrices. $\bullet$ An $\tilde{O}(n^2)$ algorithm to recover a spectral approximation of a $n$-vertex graph using only $\tilde{O}(1)$ matrix-vector multiplies with its Laplacian matrix. The previous best results for each problem either used a trivial number of queries to exactly recover the matrix or a trivial $O(n^\omega)$ running time, where $\omega$ is the matrix multiplication constant. We achieve these results by generalizing recent semidefinite programming based linear sized sparsifier results of Lee and Sun (2017) and providing iterative methods inspired by the semistreaming sparsification results of Kapralov, Lee, Musco, Musco and Sidford (2014) and input sparsity time linear system solving results of Li, Miller, and Peng (2013). We hope that by initiating study of these natural problems, expanding the robustness and scope of recent nearly linear time linear system solving research, and providing general matrix recovery machinery this work may serve as a stepping stone for faster algorithms.

  • Open Access

    Efficient $\widetilde{O}(n/ε)$ Spectral Sketches for the Laplacian and its Pseudoinverse

    by Arun Jambulapati, Aaron Sidford

    In this paper we consider the problem of efficiently computing $\epsilon$-sketches for the Laplacian and its pseudoinverse. Given a Laplacian and an error tolerance $\epsilon$, we seek to construct a function $f$ such that for any vector $x$ (chosen obliviously from $f$), with high probability $(1-\epsilon) x^\top A x \leq f(x) \leq (1 + \epsilon) x^\top A x$ where $A$ is either the Laplacian or its pseudoinverse. Our goal is to construct such a sketch $f$ efficiently and to store it in the least space possible. We provide nearly-linear time algorithms that, when given a Laplacian matrix $\mathcal{L} \in \mathbb{R}^{n \times n}$ and an error tolerance $\epsilon$, produce $\tilde{O}(n/\epsilon)$-size sketches of both $\mathcal{L}$ and its pseudoinverse. Our algorithms improve upon the previous best sketch size of $\widetilde{O}(n / \epsilon^{1.6})$ for sketching the Laplacian form by Andoni et al (2015) and $O(n / \epsilon^2)$ for sketching the Laplacian pseudoinverse by Batson, Spielman, and Srivastava (2008). Furthermore we show how to compute all-pairs effective resistances from $\widetilde{O}(n/\epsilon)$ size sketch in $\widetilde{O}(n^2/\epsilon)$ time. This improves upon the previous best running time of $\widetilde{O}(n^2/\epsilon^2)$ by Spielman and Srivastava (2008).