7 papers
Limitations of SGD for Multi-Index Models Beyond Statistical Queries
Daniel Barzilai, Ohad Shamir
Understanding the limitations of gradient methods, and stochastic gradient descent (SGD) in particular, is a central challenge in learning theory. To that end, a commonly used tool…
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
Guy Kornowski, Ohad Shamir
We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate conv…
When Models Don't Collapse: On the Consistency of Iterative MLE
Daniel Barzilai, Ohad Shamir
The widespread use of generative models has created a feedback loop, in which each generation of models is trained on data partially produced by its predecessors. This process has…
The Oracle Complexity of Simplex-based Matrix Games
Guy Kornowski, Ohad Shamir
We study the problem of solving matrix games of the form , where is a matrix and is the…
Beyond Benign Overfitting in Nadaraya-Watson Interpolators
Daniel Barzilai, Guy Kornowski, Ohad Shamir
In recent years, there has been much interest in understanding the generalization behavior of interpolating predictors, which overfit on noisy training data. Whereas standard analy…
Are Convex Optimization Curves Convex?
Guy Barzilai, Ohad Shamir, Moslem Zamani
In this paper, we study when we might expect the optimization curve induced by gradient descent to be \emph{convex} -- precluding, for example, an initial plateau followed by a sha…