25 citations · 98 across the 29 of their papers we have counts for
5 papers · 1 filter
Private Convex Optimization in General Norms
Sivakanth Gopi, Yin Tat Lee, Daogao Liu +2
We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm . Our algorithms are based on a regulariz…
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…
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…
Quadratic Speedups in Parallel Sampling from Determinantal Distributions
Nima Anari, Callum Burgess, Kevin Tian +1
We study the problem of parallelizing sampling from distributions related to determinants: symmetric, nonsymmetric, and partition-constrained determinantal point processes, as well…
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…