5 citations · 20 across the 29 of their papers we have counts for
6 papers · 1 filter
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…
Convex optimization with -norm oracles
Deeksha Adil, Brian Bullins, Arun Jambulapati +1
In recent years, there have been significant advances in efficiently solving -regression using linear system solvers and -regression [Adil-Kyng-Peng-Sachdeva, J. AC…
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
Yujia Jin, Ishani Karmarkar, Christopher Musco +2
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an -node undirected graph. We provide a randomized algorithm that, with $O(nε^{-…
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…
Truncated Variance Reduced Value Iteration
Yujia Jin, Ishani Karmarkar, Aaron Sidford +1
We provide faster randomized algorithms for computing an -optimal policy in a discounted Markov decision process with -state-action pairs, bounded rewards, and d…
On computing approximate Lewis weights
Simon Apers, Sander Gribling, Aaron Sidford
In this note we provide and analyze a simple method that given an matrix, outputs approximate -Lewis weights, a natural measure of the importance of the rows w…