5 citations · 18 across the 18 of their papers we have counts for
19 papers
The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
Guy Kornowski
We study the complexity of finding -Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can so…
The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
Guy Kornowski
We prove that first-order algorithms require gradient queries (in the worst case) to find a -Goldstein stationary point of a Lipschitz function, at which t…
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…
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…
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 pr…
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…
On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization
Guy Kornowski, Swati Padmanabhan, Ohad Shamir
We study the oracle complexity of nonsmooth nonconvex optimization, with the algorithm assumed to have access only to local function information. It has been shown by Davis, Drusvy…
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…
Open Problem: Anytime Convergence Rate of Gradient Descent
Guy Kornowski, Ohad Shamir
Recent results show that vanilla gradient descent can be accelerated for smooth convex objectives, merely by changing the stepsize sequence. We show that this can lead to surprisin…
First-Order Methods for Linearly Constrained Bilevel Optimization
Guy Kornowski, Swati Padmanabhan, Kai Wang +2
Algorithms for bilevel optimization often encounter Hessian computations, which are prohibitive in high dimensions. While recent works offer first-order methods for unconstrained b…
Efficient Agnostic Learning with Average Smoothness
Steve Hanneke, Aryeh Kontorovich, Guy Kornowski
We study distribution-free nonparametric regression following a notion of average smoothness initiated by Ashlagi et al. (2021), which measures the "effective" smoothness of a func…
An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization
Guy Kornowski, Ohad Shamir
We study the complexity of producing -stationary points of Lipschitz objectives which are possibly neither smooth nor convex, using only noisy function evaluations. Recent w…
From Tempered to Benign Overfitting in ReLU Neural Networks
Guy Kornowski, Gilad Yehudai, Ohad Shamir
Overparameterized neural networks (NNs) are observed to generalize well even when trained to perfectly fit noisy data. This phenomenon motivated a large body of work on "benign ove…
Deterministic Nonsmooth Nonconvex Optimization
Michael I. Jordan, Guy Kornowski, Tianyi Lin +2
We study the complexity of optimizing nonsmooth nonconvex Lipschitz functions by producing -stationary points. Several recent works have presented randomized algorithms that…
Near-optimal learning with average Hölder smoothness
Steve Hanneke, Aryeh Kontorovich, Guy Kornowski
We generalize the notion of average Lipschitz smoothness proposed by Ashlagi et al. (COLT 2021) by extending it to Hölder smoothness. This measure of the "effective smoothness" of…
On the Complexity of Finding Small Subgradients in Nonsmooth Optimization
Guy Kornowski, Ohad Shamir
We study the oracle complexity of producing -stationary points of Lipschitz functions, in the sense proposed by Zhang et al. [2020]. While there exist dimension-free randomi…
Oracle Complexity in Nonsmooth Nonconvex Optimization
Guy Kornowski, Ohad Shamir
It is well-known that given a smooth, bounded-from-below, and possibly nonconvex function, standard gradient-based methods can find -stationary points (with gradient norm less t…
High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
Guy Kornowski, Ohad Shamir
In this note, we consider the complexity of optimizing a highly smooth (Lipschitz -th order derivative) and strongly convex function, via calls to a -th order oracle which re…