  In this paper, we present several new results on minimizing a nonsmooth and
nonconvex function under a Lipschitz condition. Recent work shows that while
the classical notion of Clarke stationarity is computationally intractable up
to some sufficiently small constant tolerance, the randomized first-order
algorithms find a $(\delta, \epsilon)$-Goldstein stationary point with the
complexity bound of $\tilde{O}(\delta^{-1}\epsilon^{-3})$, which is independent
of dimension $d \geq 1$~\citep{Zhang-2020-Complexity, Davis-2022-Gradient,
Tian-2022-Finite}. However, the deterministic algorithms have not been fully
explored, leaving open several problems in nonsmooth nonconvex optimization.
Our first contribution is to demonstrate that the randomization is
\textit{necessary} to obtain a dimension-independent guarantee, by proving a
lower bound of $\Omega(d)$ for any deterministic algorithm that has access to
both $1^{st}$ and $0^{th}$ oracles. Furthermore, we show that the $0^{th}$
oracle is \textit{essential} to obtain a finite-time convergence guarantee, by
showing that any deterministic algorithm with only the $1^{st}$ oracle is not
able to find an approximate Goldstein stationary point within a finite number
of iterations up to sufficiently small constant parameter and tolerance.
Finally, we propose a deterministic smoothing approach under the
\textit{arithmetic circuit} model where the resulting smoothness parameter is
exponential in a certain parameter $M > 0$ (e.g., the number of nodes in the
representation of the function), and design a new deterministic first-order
algorithm that achieves a dimension-independent complexity bound of
$\tilde{O}(M\delta^{-1}\epsilon^{-3})$.
