Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization
This addresses the lack of efficient methods with convergence guarantees for nonsmooth nonconvex optimization, which is a bottleneck in machine learning and decision-making applications.
The paper tackles nonsmooth nonconvex optimization problems, common in machine learning and business, by proposing gradient-free methods (GFM and SGFM) that guarantee finite-time convergence to Goldstein stationary points, achieving an expected convergence rate of O(d^{3/2}δ^{-1}ε^{-4}) for Lipschitz functions.
Nonsmooth nonconvex optimization problems broadly emerge in machine learning and business decision making, whereas two core challenges impede the development of efficient solution methods with finite-time convergence guarantee: the lack of computationally tractable optimality criterion and the lack of computationally powerful oracles. The contributions of this paper are two-fold. First, we establish the relationship between the celebrated Goldstein subdifferential~\citep{Goldstein-1977-Optimization} and uniform smoothing, thereby providing the basis and intuition for the design of gradient-free methods that guarantee the finite-time convergence to a set of Goldstein stationary points. Second, we propose the gradient-free method (GFM) and stochastic GFM for solving a class of nonsmooth nonconvex optimization problems and prove that both of them can return a $(δ,ε)$-Goldstein stationary point of a Lipschitz function $f$ at an expected convergence rate at $O(d^{3/2}δ^{-1}ε^{-4})$ where $d$ is the problem dimension. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results. Finally, we demonstrate the effectiveness of 2-SGFM on training ReLU neural networks with the \textsc{Minst} dataset.