No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians

• 成果类型: Article
• 署名作者: Tian, Lai; So, Anthony Man-Cho
• 署名单位: Chinese University of Hong Kong
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02031-6
• 发表日期: 2024
• 页码: 51-74
• 关键词: gradient sampling algorithm; Lower bounds; nonsmooth; optimization; complexity

摘要

We consider the oracle complexity of computing an approximate stationary point of a Lipschitz function. When the function is smooth, it is well known that the simple deterministic gradient method has finite dimension-free oracle complexity. However, when the function can be nonsmooth, it is only recently that a randomized algorithm with finite dimension-free oracle complexity has been developed. In this paper, we show that no deterministic algorithm can do the same. Moreover, even without the dimension-free requirement, we show that any finite-time deterministic method cannot be general zero-respecting. In particular, this implies that a natural derandomization of the aforementioned randomized algorithm cannot have finite-time complexity. Our results reveal a fundamental hurdle in modern large-scale nonconvex nonsmooth optimization.