论文标题
无尺寸的确定性算法计算Lipschitzians的近似平稳性
No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzians
论文作者
论文摘要
我们考虑使用本地甲骨文的Lipschitz和Semialgebraic函数$ f $的大约固定点计算。如果$ f $平稳，则简单的确定性方法具有无尺寸有限的甲骨文复杂性。对于一般的Lipschitz设置，直到最近，Zhang等人。 [47]引入了一种随机算法，该算法将戈德斯坦的近似平稳性[25]计算为任意精度，没有无维度的多项式甲骨文复杂性。 在本文中，我们表明没有确定性算法可以做到这一点。即使没有无维度的要求，我们也表明，保证的任何有限的确定性方法都不能成为一般零渴望，它排除了基于甲骨文的大多数基于甲骨文的平滑优化和Zhang等人的任何微不足道的衍生化。 [47]。我们的结果揭示了现代大规模环境中非洞穴非平滑问题的基本障碍及其无限维度扩展。
We consider the computation of an approximately stationary point for a Lipschitz and semialgebraic function $f$ with a local oracle. If $f$ is smooth, simple deterministic methods have dimension-free finite oracle complexities. For the general Lipschitz setting, only recently, Zhang et al. [47] introduced a randomized algorithm that computes Goldstein's approximate stationarity [25] to arbitrary precision with a dimension-free polynomial oracle complexity. In this paper, we show that no deterministic algorithm can do the same. Even without the dimension-free requirement, we show that any finite time guaranteed deterministic method cannot be general zero-respecting, which rules out most of the oracle-based methods in smooth optimization and any trivial derandomization of Zhang et al. [47]. Our results reveal a fundamental hurdle of nonconvex nonsmooth problems in the modern large-scale setting and their infinite-dimensional extension.
