On the Complexity of Finding Small Subgradients in Nonsmooth Optimization

Guy Kornowski, Ohad Shamir

We study the oracle complexity of producing $(\delta ,\epsilon )$-stationary points of Lipschitz functions, in the sense proposed by Zhang et al. [2020]. While there exist dimension-free randomi…