论文标题
较低的复杂性界限以最大程度地减少正则功能
Lower Complexity Bounds for Minimizing Regularized Functions
论文作者
论文摘要
在本文中，我们为一阶方法的甲骨复杂性建立了下限，最大程度地减少了正则化凸功能。我们考虑目标的综合表示。光滑的部分具有[0，1] $中的$ν\的hölder连续梯度，并且可以通过黑盒本地甲骨文来访问。复合部分是规范的力量。我们证明，欧几里得规范的大规模设置中一阶方法的最佳速率是$ o（k^{ - p（1 +3ν） /（2（p-1-ν） /（2（p-1-ν）}）$用于功能残留的$，其中$ k $ $ k $是itseration counter，$ p $是正规化的幂。我们的公式涵盖了几种情况，包括按一阶梯度方法计算立方正规化的牛顿步骤，在这种情况下，速率变为$ O（k^{ - 6}）$。可以通过快速梯度方法来实现。因此，我们的结果证明后一个速率是最佳的。我们还发现非欧盟规范的复杂性范围较低。
In this paper, we establish lower bounds for the oracle complexity of the first-order methods minimizing regularized convex functions. We consider the composite representation of the objective. The smooth part has Hölder continuous gradient of degree $ν\in [0, 1]$ and is accessible by a black-box local oracle. The composite part is a power of a norm. We prove that the best possible rate for the first-order methods in the large-scale setting for Euclidean norms is of the order $O(k^{- p(1 + 3ν) / (2(p - 1 - ν))})$ for the functional residual, where $k$ is the iteration counter and $p$ is the power of regularization. Our formulation covers several cases, including computation of the Cubically regularized Newton step by the first-order gradient methods, in which case the rate becomes $O(k^{-6})$. It can be achieved by the Fast Gradient Method. Thus, our result proves the latter rate to be optimal. We also discover lower complexity bounds for non-Euclidean norms.
