8 papers · 1 filter
Fast, Parallel, Query-Efficient Binary Classification
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size with normalized -dimensional features. Letting $Φ\…
Solving Matrix Games with Near-Optimal Matvec Complexity
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
We study the problem of computing an -approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix , when the players…
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 en…
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…
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…