9 papers
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…
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…
Differentially Private Bilevel Optimization
Guy Kornowski
We present differentially private (DP) algorithms for bilevel optimization, a problem class that received significant attention lately in various machine learning applications. The…
Trade-offs in Data Memorization via Strong Data Processing Inequalities
Vitaly Feldman, Guy Kornowski, Xin Lyu
Recent research demonstrated that training large language models involves memorization of a significant fraction of training data. Such memorization can lead to privacy violations…
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…
Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
Guy Kornowski, Daogao Liu, Kunal Talwar
We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstei…