  We consider the computation of an approximately stationary point for a
Lipschitz and semialgebraic function $f$ with a local oracle. If $f$ is smooth,
simple deterministic methods have dimension-free finite oracle complexities.
For the general Lipschitz setting, only recently, Zhang et al. [47] introduced
a randomized algorithm that computes Goldstein's approximate stationarity [25]
to arbitrary precision with a dimension-free polynomial oracle complexity.
  In this paper, we show that no deterministic algorithm can do the same. Even
without the dimension-free requirement, we show that any finite time guaranteed
deterministic method cannot be general zero-respecting, which rules out most of
the oracle-based methods in smooth optimization and any trivial derandomization
of Zhang et al. [47]. Our results reveal a fundamental hurdle of nonconvex
nonsmooth problems in the modern large-scale setting and their
infinite-dimensional extension.
