On the Complexity of Finding Small Subgradients in Nonsmooth Optimization
On the Complexity of Finding Small Subgradients in Nonsmooth Optimization
复制标题
关于非光滑优化中寻找小次梯度的复杂性
DOI：
10.48550/arxiv.2209.10346
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ohad Shamir
中科院分区：
文献类型：
--
作者：
Guy Kornowski;Ohad Shamir
我们研究了在Zhang et al. [2020]提出的意义下产生Lipschitz函数的$（\delta，\delta）$-平稳点的预言复杂性。虽然存在无量纲的随机算法，以产生这样的点内$\widetilde{O}（1/\delta\epsilon ^3）$一阶Oracle调用，我们表明，没有无量纲率可以实现的确定性算法。另一方面，我们指出，这一速率可以去随机化的光滑函数，仅仅是一个对数依赖的光滑参数。此外，我们建立了几个下界这个任务，适用于任何随机算法，有或没有凸性。最后，我们展示了如何找到$（\delta，\delta）$-固定点的收敛速度可以提高的情况下，该功能是凸的，一个设置，我们激励证明，在一般情况下，没有有限时间算法可以产生点，即使是凸函数的小次梯度。
We study the oracle complexity of producing $(\delta,\epsilon)$-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/\delta\epsilon^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 $(\delta,\epsilon)$-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.
DOI：
--
发表时间：
2021-12
期刊：
--
影响因子：
--
作者：
Damek Davis;D. Drusvyatskiy;Y. Lee;Swati Padmanabhan;Guanghao Ye
通讯作者：
Damek Davis;D. Drusvyatskiy;Y. Lee;Swati Padmanabhan;Guanghao Ye
DOI：
--
发表时间：
2020-03
期刊：
ArXiv
影响因子：
--
作者：
Y. Carmon;A. Jambulapati;Qijia Jiang;Yujia Jin;Y. Lee;Aaron Sidford;Kevin Tian
通讯作者：
Y. Carmon;A. Jambulapati;Qijia Jiang;Yujia Jin;Y. Lee;Aaron Sidford;Kevin Tian