536 citations · 4.4k across the 97 of their papers we have counts for
13 papers · 1 filter
A Simple Complexity Lower Bound for Solving
Ohad Shamir
In this note, we provide a short and direct proof that approximately solving to relative error , where has condition number and unrestricted dimension,…
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…
A Stochastic Newton Algorithm for Distributed Convex Optimization
Brian Bullins, Kumar Kshitij Patel, Ohad Shamir +2
We propose and analyze a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization, where each machine can calculate stochastic gradients of the same p…
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…