4 papers
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
Michael Menart, Aleksandar Nikolov, Ohad Shamir
We prove two lower bounds for the first order oracle complexity of minimizing a -dimensional -Lipschitz convex function over the unit ball with bits of memory. We first s…
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 th…
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 rando…
Logarithmic Width Suffices for Robust Memorization
Amitsour Egosi, Gilad Yehudai, Ohad Shamir
The memorization capacity of neural networks with a given architecture has been thoroughly studied in many works. Specifically, it is well-known that memorizing samples can be…