Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective

本文探讨了在局部梯度变化有界的情况下的非光滑优化问题，该假设规定了在点周围的小局部区域内，（次）梯度之间的差异有界，可以是平均意义或最大意义。由此产生的目标函数类封装了传统优化中通常研究的目标函数类，这些函数是基于目标的Lipschitz连续性或其梯度的Holder/Lipschitz连续性定义的。此外，定义的类包含既不是Lipschitz连续的函数，也没有Holder连续梯度的函数。当限制在传统的优化问题类上时，定义这些类的参数会导致更精细的复杂度界限，恢复了最坏情况下的传统预言机复杂度界限，但通常会导致对于不是“最坏情况”的函数的更低的预言机复杂度。我们的结果中的一些亮点是：（i）可以通过局部梯度变化的常数替换（局部或全局）Lipschitz常数来获得凸和非凸问题的复杂度结果；（ii）次微分集围绕最优解的平均宽度在非光滑优化的复杂度中起着作用，特别是在并行设置中。由（ii）得出的一个结论是，对于任何误差参数$\epsilon>0$，当目标函数在输入大小的多项式片段中时，非光滑Lipschitz凸优化的并行预言机复杂度比其顺序预言机复杂度低一个因子$\tilde{\Omega}(\frac{1}{\epsilon})$。这尤其令人惊讶，因为现有的并行复杂度下界是基于这些函数类的。这种看似矛盾的情况是通过考虑算法被允许查询目标函数的区域来解决的。

研究非光滑优化问题在局部梯度变化受限的情况下的复杂度和性质，包括传统的Lipschitz连续性和H"{o}lder/Lipschitz连续性，以及不具备这些连续性的函数。

将局部梯度变化受限的常数代替Lipschitz常数来描述函数的光滑性，进而得到更细粒度的复杂度界，特别是在并行计算中。

可以得到凸和非凸问题的复杂度界，对于具有多项式分段的线性函数，本文提出的并行算法比现有的算法具有更低的oracle复杂度界。

最近的相关研究包括：《On the complexity of first-order and derivative-free algorithms for smooth nonconvex optimization》、《Stochastic gradient descent with sub-Gaussian sampling》等。