  Zhang et al. introduced a novel modification of Goldstein's classical
subgradient method, with an efficiency guarantee of $O(\varepsilon^{-4})$ for
minimizing Lipschitz functions. Their work, however, makes use of a nonstandard
subgradient oracle model and requires the function to be directionally
differentiable. In this paper, we show that both of these assumptions can be
dropped by simply adding a small random perturbation in each step of their
algorithm. The resulting method works on any Lipschitz function whose value and
gradient can be evaluated at points of differentiability. We additionally
present a new cutting plane algorithm that achieves better efficiency in low
dimensions: $O(d\varepsilon^{-3})$ for Lipschitz functions and
$O(d\varepsilon^{-2})$ for those that are weakly convex.
