67 citations · 176 across the 22 of their papers we have counts for
6 papers · 1 filter
Leverage Score Sampling for Faster Accelerated Regression and ERM
Naman Agarwal, Sham Kakade, Rahul Kidambi +3
Given a matrix and a vector , we show how to compute an -approximate solution to the regression problem $ \min_{x\in\m…
Lower Bounds for Finding Stationary Points II: First-Order Methods
Yair Carmon, John C. Duchi, Oliver Hinder +1
We establish lower bounds on the complexity of finding -stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic…
Efficient Spectral Sketches for the Laplacian and its Pseudoinverse
Arun Jambulapati, Aaron Sidford
In this paper we consider the problem of efficiently computing -sketches for the Laplacian and its pseudoinverse. Given a Laplacian and an error tolerance , we seek to constr…
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Jack Murtagh, Omer Reingold, Aaron Sidford +1
We give a deterministic -space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating h…
Efficient Convex Optimization with Membership Oracles
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
We consider the problem of minimizing a convex function over a convex set given access only to an evaluation oracle for the function and a membership oracle for the set. We give a…
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
Yair Carmon, Oliver Hinder, John C. Duchi +1
We develop and analyze a variant of Nesterov's accelerated gradient descent (AGD) for minimization of smooth non-convex functions. We prove that one of two cases occurs: either our…