  We study the complexity of optimizing nonsmooth nonconvex Lipschitz functions
by producing $(\delta,\epsilon)$-stationary points. Several recent works have
presented randomized algorithms that produce such points using $\tilde
O(\delta^{-1}\epsilon^{-3})$ first-order oracle calls, independent of the
dimension $d$. It has been an open problem as to whether a similar result can
be obtained via a deterministic algorithm. We resolve this open problem,
showing that randomization is necessary to obtain a dimension-free rate. In
particular, we prove a lower bound of $\Omega(d)$ for any deterministic
algorithm. Moreover, we show that unlike smooth or convex optimization, access
to function values is required for any deterministic algorithm to halt within
any finite time.
  On the other hand, we prove that if the function is even slightly smooth,
then the dimension-free rate of $\tilde O(\delta^{-1}\epsilon^{-3})$ can be
obtained by a deterministic algorithm with merely a logarithmic dependence on
the smoothness parameter. Motivated by these findings, we turn to study the
complexity of deterministically smoothing Lipschitz functions. Though there are
efficient black-box randomized smoothings, we start by showing that no such
deterministic procedure can smooth functions in a meaningful manner, resolving
an open question. We then bypass this impossibility result for the structured
case of ReLU neural networks. To that end, in a practical white-box setting in
which the optimizer is granted access to the network's architecture, we propose
a simple, dimension-free, deterministic smoothing that provably preserves
$(\delta,\epsilon)$-stationary points. Our method applies to a variety of
architectures of arbitrary depth, including ResNets and ConvNets. Combined with
our algorithm, this yields the first deterministic dimension-free algorithm for
optimizing ReLU networks, circumventing our lower bound.
