5 citations · 18 across the 18 of their papers we have counts for
10 papers · 1 filter
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…
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…
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…
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…
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…