7 papers · 1 filter
On the Limits of Biased Derivative Information for Nonconvex Stochastic Optimization
Anant Shyam, Brian Bullins
We consider the problem of finding -stationary points for , i.e., such that , for smooth, non-convex objectives, where the d…
Mirror-Free Proximal Methods
Abhijeet Vyas, Brian Bullins
We present a \emph{mirror-free} mirror prox (MFMP) algorithm, which extends the classic approach of Nemirovski (2004) to allow for proximal-like updates without the explicit need f…
Beyond First-Order Methods for -Structured Non-Monotone Variational Inequalities
Abhijeet Vyas, Brian Bullins
We propose novel high-order algorithms for a class of -structured non-monotone variational inequalities. In particular, work by Diakonikolas et al. (2021), which introduced…
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…
Faster Acceleration for Steepest Descent
Cedar Site Bai, Brian Bullins
Recent advances (Sherman, 2017; Sidford and Tian, 2018; Cohen et al., 2021) have overcome the fundamental barrier of dimension dependence in the iteration complexity of solving $\e…