536 citations · 4.4k across the 97 of their papers we have counts for
6 papers · 1 filter
The Complexity of Finding Stationary Points with Stochastic Gradient Descent
Yoel Drori, Ohad Shamir
We study the iteration complexity of stochastic gradient descent (SGD) for minimizing the gradient norm of smooth, possibly nonconvex functions. We provide several results, implyin…
How Good is SGD with Random Shuffling?
Itay Safran, Ohad Shamir
We study the performance of stochastic gradient descent (SGD) on smooth and strongly-convex finite-sum optimization problems. In contrast to the majority of existing theoretical wo…
Depth Separations in Neural Networks: What is Actually Being Separated?
Itay Safran, Ronen Eldan, Ohad Shamir
Existing depth separation results for constant-depth networks essentially show that certain radial functions in , which can be easily approximated with depth netw…
On the Power and Limitations of Random Features for Understanding Neural Networks
Gilad Yehudai, Ohad Shamir
Recently, a spate of papers have provided positive theoretical results for training over-parameterized neural networks (where the network size is larger than what is needed to achi…
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…
Space lower bounds for linear prediction in the streaming model
Yuval Dagan, Gil Kur, Ohad Shamir
We show that fundamental learning tasks, such as finding an approximate linear separator or linear regression, require memory at least \emph{quadratic} in the dimension, in a natur…