Arun Jambulapati

activity

20172025

most citedParallel Reachability in Almost Linear Work and Square Root Depth

11 citations · 58 across the 33 of their papers we have counts for

collaborators

36 papers

cs.DS2025

Radial Isotropic Position via an Implicit Newton's Method

Arun Jambulapati, Jonathan Li, Kevin Tian

Placing a dataset $A = {a_{i}}_{i \in [n]} \subset R^{d}$ in radial isotropic position, i.e., finding an invertible $R \in R^{d \times d}$ such th…

math.OC2024

Extracting Dual Solutions via Primal Optimizers

Yair Carmon, Arun Jambulapati, Liam O'Carroll +1

We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associa…

math.OC2024

Convex optimization with $p$ -norm oracles

Deeksha Adil, Brian Bullins, Arun Jambulapati +1

In recent years, there have been significant advances in efficiently solving $ℓ_{s}$ -regression using linear system solvers and $ℓ_{2}$ -regression [Adil-Kyng-Peng-Sachdeva, J. AC…

cs.DS2024

Eulerian Graph Sparsification by Effective Resistance Decomposition

Arun Jambulapati, Sushant Sachdeva, Aaron Sidford +2

We provide an algorithm that, given an $n$ -vertex $m$ -edge Eulerian graph with polynomially bounded weights, computes an $O ˘ (n lo g^{2} n \cdot ε^{- 2})$ -edge $\vare…

math.OC2024

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

Arun Jambulapati, Aaron Sidford, Kevin Tian

We develop a new parallel algorithm for minimizing Lipschitz, convex functions with a stochastic subgradient oracle. The total number of queries made and the query depth, i.e., the…

math.NA2024

Black-Box $k$ -to- $1$ -PCA Reductions: Theory and Applications

Arun Jambulapati, Syamantak Kumar, Jerry Li +3

The $k$ -principal component analysis ( $k$ -PCA) problem is a fundamental algorithmic primitive that is widely-used in data analysis and dimensionality reduction applications. In sta…

cs.LG2024

Testing Calibration in Nearly-Linear Time

Lunjia Hu, Arun Jambulapati, Kevin Tian +1

In the recent literature on machine learning and decision making, calibration has emerged as a desirable and widely-studied statistical property of the outputs of binary prediction…

cs.DS2023

Sparsifying generalized linear models

Arun Jambulapati, James R. Lee, Yang P. Liu +1

We consider the sparsification of sums $F : R^{n} \to R$ where $F (x) = f_{1} (⟨ a_{1}, x ⟩) + \dots + f_{m} (⟨ a_{m}, x ⟩)$ for vectors $a_1,\ldots,a_m \…

cs.DS2023

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

Yair Carmon, Arun Jambulapati, Yujia Jin +1

We design algorithms for minimizing $max_{i \in [n]} f_{i} (x)$ over a $d$ -dimensional Euclidean or simplex domain. When each $f_{i}$ is $1$ -Lipschitz and $1$ -smooth, our method computes…

cs.DS2023

Structured Semidefinite Programming for Recovering Structured Preconditioners

Arun Jambulapati, Jerry Li, Christopher Musco +3

We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental p…

cs.DS2023

Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory

Arun Jambulapati, Victor Reis, Kevin Tian

Discrepancy theory provides powerful tools for producing higher-quality objects which "beat the union bound" in fundamental settings throughout combinatorics and computer science.…

cs.DS2023★ 2 cited

Sparsifying sums of norms

Arun Jambulapati, James R. Lee, Yang P. Liu +1

For any norms $N_{1}, \dots, N_{m}$ on $R^{n}$ and $N (x) := N_{1} (x) + \dots + N_{m} (x)$ , we show there is a sparsified norm $N ~ (x) = w_{1} N_{1} (x) + \dots + w_{m} N_{m} (x)$ such that…

math.OC2023

Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations

Arun Jambulapati, Kevin Tian

We investigate different aspects of area convexity [Sherman '17], a mysterious tool introduced to tackle optimization problems under the challenging $ℓ_{\infty}$ geometry. We deve…

math.OC2023

ReSQueing Parallel and Private Stochastic Convex Optimization

Yair Carmon, Arun Jambulapati, Yujia Jin +4

We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probab…

cs.DS2022

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification

Arun Jambulapati, Yang P. Liu, Aaron Sidford

We present an algorithm that given any $n$ -vertex, $m$ -edge, rank $r$ hypergraph constructs a spectral sparsifier with $O (n ε^{- 2} lo g n lo g r)$ hyperedges in nearly-li…

math.OC2022★ 4 cited

RECAPP: Crafting a More Efficient Catalyst for Convex Optimization

Yair Carmon, Arun Jambulapati, Yujia Jin +1

The accelerated proximal point algorithm (APPA), also known as "Catalyst", is a well-established reduction from convex optimization to approximate proximal point computation (i.e.,…

math.OC2022★ 1 cited

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

Deeksha Adil, Brian Bullins, Arun Jambulapati +1

In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for $p^{t h}$ -order smooth, monotone operators -- a problem that gener…

math.OC2022★ 5 cited

Optimal and Adaptive Monteiro-Svaiter Acceleration

Yair Carmon, Danielle Hausler, Arun Jambulapati +2

We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Consequently, for any $p\…

cs.DS2022

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Arun Jambulapati, Yujia Jin, Aaron Sidford +1

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 mat…

math.AG2021

Weil-Poincaré series and topology of collections of valuations on rational double points

A. Campillo, F. Delgado, S. M. Gusein-Zade

Earlier it was described to which extent the Alexander polynomial in several variables of an algebraic link in the Poincaré sphere determines the topology of the link. It was shown…

cs.DS2021

Improved Iteration Complexities for Overconstrained $p$ -Norm Regression

Arun Jambulapati, Yang P. Liu, Aaron Sidford

In this paper we obtain improved iteration complexities for solving $ℓ_{p}$ regression. We provide methods which given any full-rank $A \in R^{n \times d}$ with…

cs.DS2021★ 7 cited

Robust Regression Revisited: Acceleration and Improved Estimation Rates

Arun Jambulapati, Jerry Li, Tselil Schramm +1

We study fast algorithms for statistical regression problems under the strong contamination model, where the goal is to approximately optimize a generalized linear model (GLM) give…

math.OC2021

Stochastic Bias-Reduced Gradient Methods

Hilal Asi, Yair Carmon, Arun Jambulapati +2

We develop a new primitive for stochastic optimization: a low-bias, low-cost estimator of the minimizer $x_{⋆}$ of any Lipschitz strongly-convex function. In particular, we use a…

math.OC2021★ 6 cited

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

Yair Carmon, Arun Jambulapati, Yujia Jin +1

We characterize the complexity of minimizing $max_{i \in [N]} f_{i} (x)$ for convex, Lipschitz functions $f_{1}, \dots, f_{N}$ . For non-smooth functions, existing methods require $O(Nε^{-2…

Radial Isotropic Position via an Implicit Newton's Method

Extracting Dual Solutions via Primal Optimizers

Convex optimization with p-norm oracles

Eulerian Graph Sparsification by Effective Resistance Decomposition

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

Black-Box k-to-1-PCA Reductions: Theory and Applications

Testing Calibration in Nearly-Linear Time

Sparsifying generalized linear models

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

Structured Semidefinite Programming for Recovering Structured Preconditioners

Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory

Sparsifying sums of norms

Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations

ReSQueing Parallel and Private Stochastic Convex Optimization

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification

RECAPP: Crafting a More Efficient Catalyst for Convex Optimization

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

Optimal and Adaptive Monteiro-Svaiter Acceleration

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Weil-Poincaré series and topology of collections of valuations on rational double points

Improved Iteration Complexities for Overconstrained p-Norm Regression

Robust Regression Revisited: Acceleration and Improved Estimation Rates

Stochastic Bias-Reduced Gradient Methods

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

Convex optimization with $p$ -norm oracles

Black-Box $k$ -to- $1$ -PCA Reductions: Theory and Applications

Improved Iteration Complexities for Overconstrained $p$ -Norm Regression