1.9k citations · 6.5k across the 132 of their papers we have counts for
10 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…
A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
Greg Ongie, Rebecca Willett, Daniel Soudry +1
A key element of understanding the efficacy of overparameterized neural networks is characterizing how they represent functions as the number of weights in the network approaches i…
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…
Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
Mor Shpigel Nacson, Suriya Gunasekar, Jason D. Lee +2
With an eye toward understanding complexity control in deep learning, we study how infinitesimal regularization or gradient descent optimization lead to margin maximizing solutions…