167 citations · 679 across the 25 of their papers we have counts for
6 papers · 1 filter
Lower Bounds for Non-Convex Stochastic Optimization
Yossi Arjevani, Yair Carmon, John C. Duchi +3
We lower bound the complexity of finding -stationary points (with gradient norm at most ) using stochastic first-order methods. In a well-studied model where algorithms acces…
The gradient complexity of linear regression
Mark Braverman, Elad Hazan, Max Simchowitz +1
We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model…
Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
Blake Woodworth, Nathan Srebro
We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly…
Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis
Ryan Rogers, Aaron Roth, Adam Smith +3
We design a general framework for answering adaptive statistical queries that focuses on providing explicit confidence intervals along with point estimates. Prior work in this area…
Kernel and Rich Regimes in Overparametrized Models
Blake Woodworth, Suriya Gunasekar, Pedro Savarese +5
A recent line of work studies overparametrized neural networks in the "kernel regime," i.e. when the network behaves during training as a kernelized linear predictor, and thus trai…
The Complexity of Making the Gradient Small in Stochastic Convex Optimization
Dylan J. Foster, Ayush Sekhari, Ohad Shamir +3
We give nearly matching upper and lower bounds on the oracle complexity of finding -stationary points () in stochastic convex optimization. We jointly a…