证明了非光滑非凸优化中局部算法无法在多项式时间内保证找到局部极小值。
On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization
- 研究局部算法在非光滑函数上的收敛性极限
- 最坏情况下，子指数时间内无法获得有意义的函数值保证
- 结果无需依赖P≠NP等假设，适用于所有近似驻点即全局最小的情况
我们研究了非光滑非凸优化的预言机复杂度，假设算法仅能访问局部函数信息。Davis、Drusvyatskiy 和 Jiang（2023）已证明，对于满足特定正则性和严格性条件的非光滑Lipschitz函数，扰动梯度下降可渐近收敛到局部极小值。受此结果及其他近期关于Goldstein平稳性的算法进展启发，我们探讨该问题类能否实现非渐近收敛速率至局部极小值。本文给出否定回答：在最坏情况下，作用于正则Lipschitz函数的局部算法，即使所有近似驻点均为全局最小值，也无法在子指数时间内提供有意义的函数值局部保证。这一结果与光滑情形形成鲜明对比，后者标准梯度方法可在与维度无关的速率下实现此类保证。本结果不依赖于P≠NP或密码学假设等条件，补充了理论计算机科学中大量基于假设的难解性结论。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。