5 citations · 20 across the 29 of their papers we have counts for
5 papers · 1 filter
Balancing Gradient and Hessian Queries in Non-Convex Optimization
Deeksha Adil, Brian Bullins, Aaron Sidford +1
We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function. We…
Isotropic Noise in Stochastic and Quantum Convex Optimization
Annie Marsden, Liam O'Carroll, Aaron Sidford +1
We consider the problem of minimizing a -dimensional Lipschitz convex function using a stochastic gradient oracle. We introduce and motivate a setting where the noise of the sto…
Reusing Samples in Variance Reduction
Yujia Jin, Ishani Karmarkar, Aaron Sidford +1
We provide a general framework to improve trade-offs between the number of full batch and sample queries used to solve structured optimization problems. Our results apply to a broa…
Solving Zero-Sum Games with Fewer Matrix-Vector Products
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
In this paper we consider the problem of computing an -approximate Nash Equilibrium of a zero-sum game in a payoff matrix with -bounded ent…
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
Michał Dereziński, Aaron Sidford
We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for large singular values. For solving su…