A Frank-Wolfe Approach to Goldstein Stationarity

We investigate the problem of finding $(\delta, \varepsilon)$-stationary points (also called Goldstein stationary points) for nonsmooth nonconvex Lipschitz functions. This problem has recently garnered significant attention, with several non-asymptotic convergence guarantees. However, existing methods for such guarantees require prior knowledge of problem parameters and lack anytime convergence. Our work addresses these issues by providing an algorithm that satisfies two properties: Firstly, our algorithm is parameter-free; secondly, it generates a sequence of $(\varepsilon, \varepsilon)$-stationary points with monotonically decreasing $\varepsilon$. This algorithm achieves the (non-stochastic) state-of-the-art complexity for any $\varepsilon > 0$ and ensuring convergence to a Clarke stationary point in the limit. Central to our result is the insight that one can slightly modify prior algorithms for this problem and view them within the framework of the classic Frank-Wolfe algorithm.