5 citations · 20 across the 29 of their papers we have counts for
10 papers · 1 filter
Dynamic Maxflow via Dynamic Interior Point Methods
Jan van den Brand, Yang P. Liu, Aaron Sidford
In this paper we provide an algorithm for maintaining a -approximate maximum flow in a dynamic, capacitated graph undergoing edge additions. Over a sequence of -additions…
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur +1
We provide an efficient unified plug-in approach for estimating symmetric properties of distributions given independent samples. Our estimator is based on profile-maximum-likel…
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati, Yang P. Liu, Aaron Sidford
We present an algorithm that given any -vertex, -edge, rank hypergraph constructs a spectral sparsifier with hyperedges in nearly-li…
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.,…
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\…
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…
The Complexity of Infinite-Horizon General-Sum Stochastic Games
Yujia Jin, Vidya Muthukumar, Aaron Sidford
We study the complexity of computing stationary Nash equilibrium (NE) in n-player infinite-horizon general-sum stochastic games. We focus on the problem of computing NE in such sto…
Semi-Random Sparse Recovery in Nearly-Linear Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
Sparse recovery is one of the most fundamental and well-studied inverse problems. Standard statistical formulations of the problem are provably solved by general convex programming…
Efficient Convex Optimization Requires Superlinear Memory
Annie Marsden, Vatsal Sharan, Aaron Sidford +1
We show that any memory-constrained, first-order algorithm which minimizes -dimensional, -Lipschitz convex functions over the unit ball to accuracy using…
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
Yujia Jin, Aaron Sidford, Kevin Tian
We design accelerated algorithms with improved rates for several fundamental classes of optimization problems. Our algorithms all build upon techniques related to the analysis of p…