We study the oracle complexity of nonsmooth nonconvex optimization, with the algorithm assumed to have access only to local function information. It has been shown by Davis, Drusvyatskiy, and Jiang (2023) that for nonsmooth Lipschitz functions satisfying certain regularity and strictness conditions, perturbed gradient descent converges to local minimizers asymptotically. Motivated by this result and by other recent algorithmic advances in nonconvex nonsmooth optimization concerning Goldstein stationarity, we consider the question of obtaining a non-asymptotic rate of convergence to local minima for this problem class. We provide the following negative answer to this question: Local algorithms acting on regular Lipschitz functions cannot, in the worst case, provide meaningful local guarantees in terms of function value in sub-exponential time, even when all near-stationary points are global minima. This sharply contrasts with the smooth setting, for which it is well-known that standard gradient methods can do so in a dimension-independent rate. Our result complements the rich body of work in the theoretical computer science literature that provide hardness results conditional on conjectures such as $\mathsf{P}\neq\mathsf{NP}$ or cryptographic assumptions, in that ours holds unconditional of any such assumptions.

本研究探讨了非光滑非凸优化的oracle复杂性，针对局部算法在给定一定条件下无法在子指数时间内提供有意义的局部保证的问题。通过分析，我们发现即使所有近似驻点都是全局极小值，局部利普希茨函数的局部算法在最坏情况下依然不能提供有效的函数值保证，这与光滑情况下标准梯度方法的结果形成鲜明对比。此发现对理论计算机科学文献中的困难性研究提供了补充。 

非光滑非凸优化中有意义局部保证的困难性研究