论文标题
关于在非滑动优化中找到小亚级别的复杂性
On the Complexity of Finding Small Subgradients in Nonsmooth Optimization
论文作者
论文摘要
我们研究了Lipschitz函数的$（δ，ε）$固定点的甲骨文复杂性，从Zhang等人提出的意义上。 [2020]。尽管存在无维数算法，用于在$ \ widetilde {o}（1/δε^3）$一阶甲骨文调用中产生此类点，但我们表明，确定性算法无法实现无尺寸的速率。另一方面，我们指出，对于平滑函数，可以将此速率取代，而仅对对数依赖平滑度参数。此外，我们为此任务建立了几个下限，这些界限适用于任何随机算法，无论有或没有凸度。最后，我们展示了查找$（δ，ε）$ - 固定点的收敛速率，如果函数是凸的，我们是通过证明一般没有有限的时间算法可以激励的设置，即使没有有限的时间算法也可以产生较小的子级别的点。
We study the oracle complexity of producing $(δ,ε)$-stationary points of Lipschitz functions, in the sense proposed by Zhang et al. [2020]. While there exist dimension-free randomized algorithms for producing such points within $\widetilde{O}(1/δε^3)$ first-order oracle calls, we show that no dimension-free rate can be achieved by a deterministic algorithm. On the other hand, we point out that this rate can be derandomized for smooth functions with merely a logarithmic dependence on the smoothness parameter. Moreover, we establish several lower bounds for this task which hold for any randomized algorithm, with or without convexity. Finally, we show how the convergence rate of finding $(δ,ε)$-stationary points can be improved in case the function is convex, a setting which we motivate by proving that in general no finite time algorithm can produce points with small subgradients even for convex functions.
