技术摘要：全局 - 局部平滑性（Glocal Smoothness）

问题陈述

一阶优化算法（如梯度下降法 GD）的标准理论分析通常依赖于全局 $L$-平滑性（即全局 Lipschitz 连续梯度）的假设。在此假设下，迭代复杂度以全局 Lipschitz 常数 $L$ 表示，且通过使用固定步长（例如 $\eta_t = 1/L$）可实现近最优收敛速率。然而，实证观察往往与这些最坏情况界限相矛盾：

1. 线搜索与固定步长：尽管在全局平滑性假设下具有相同的最坏情况理论速率，但采用精确线搜索的梯度下降法（GD(LO)）在实际中通常比采用固定步长（$1/L$）的梯度下降法收敛快得多。
2. 线搜索与加速：在实际场景中，GD(LO) 经常优于采用固定步长（$1/L$）的 Nesterov 加速梯度法（NAG），尽管 NAG 在理论上提供了更优的最坏情况速率（$O(\sqrt{L/\mu})$ 对比 $O(L/\mu)$）。

现有文献试图利用局部平滑性假设来解释这些现象，其中 Lipschitz 常数取决于算法的迭代点（例如 $L(w_t)$）。虽然这些分析表明自适应方法可以利用局部平滑性，但它们存在一个关键局限：收敛速率取决于算法所采取的具体迭代序列。由于不同的算法（例如 GD 与 NAG）遵循不同的路径，它们的局部平滑性序列也不同，这使得在理论上直接比较它们的迭代复杂度变得困难。因此，目前缺乏严格的理论依据来解释为何 GD(LO) 在特定设置下可能优于 NAG(1/L)。

方法论

本文引入了一种新的平滑性刻画，称为**“全局 - 局部平滑性”（Glocal Smoothness）**。该框架在全局平滑性的基础上，增加了一个独立于算法具体轨迹、定义在解附近的局部平滑性度量。

定义：若函数 $f$ 满足以下条件，则称其为 $(L, L^*, \delta)$-全局 - 局部平滑：

1. 它是全局 $L$-平滑的（在全局范围内满足标准 Lipschitz 条件）。
2. 它在次水平集 $\{u \in \mathbb{R}^d \mid f(u) - f^* \leq \delta\}$ 上是局部 $L^*$-平滑的，其中 $f^*$ 是 $f$ 的下确界。

关键在于，$L^*$ 和 $\delta$ 是函数本身的属性，而非迭代点的属性。这使得推导出的迭代复杂度界限仅依赖于函数属性，从而能够直接比较不同算法。

作者采用两阶段分析策略：

1. 全局阶段：利用全局属性（$L$）界定到达局部区域（即次优性 $\leq \delta$）所需的迭代次数。
2. 局部阶段：利用局部属性（$L^*$）界定在局部区域内达到目标精度 $\epsilon$ 所需的迭代次数。

本文证明，在全局 - 局部平滑性下，利用线搜索或自适应步长的算法一旦进入次水平集，即可有效地“切换”到更快的局部速率（$L^*$），而无需预先知道 $L^*$ 或 $\delta$。

主要贡献与结果

1. 线搜索与加速的理论比较

本文确立了在全局 - 局部平滑性和强凸性条件下，采用线搜索的梯度下降法（GD(LO)）可以比采用固定步长的 NAG（NAG(1/L)）具有严格更优的迭代复杂度。

• 结果：GD(LO) 的迭代复杂度界限为 $O\left(\frac{L}{\mu} \log \frac{\Delta_0}{\delta} + \frac{L^*}{\mu} \log \frac{\delta}{\epsilon}\right)$。
• 比较：NAG(1/L) 的复杂度为 $O\left(\sqrt{\frac{L}{\mu}} \log \frac{\Delta_0}{\epsilon}\right)$。
• 条件：如果局部平滑性 $L^*$ 显著小于 $L$（具体而言，若 $L^*/L \ll (\sqrt{\kappa})^{-1} \dots$），且条件数 $\kappa = L/\mu$ 不过大，则 GD(LO) 优于 NAG(1/L)。这为“线搜索在特定机制下能击败加速方法”这一实证观察提供了首个理论依据。

2. 在特定算法中的应用

作者证明，全局 - 局部平滑性为广泛算法带来了改进的复杂度界限：

• 梯度下降法：精确线搜索以及实用变体（如带重置的 Armijo 回溯、前向回溯和 Polyak 步长）均实现了改进的速率。
• 自适应步长：AdGD（无需下降的自适应梯度下降）步长被证明能达到与 GD(LO) 相似的速率，且无需知道 $f^*$。
• 坐标下降法：随机和贪婪坐标下降法均受益于坐标方向上的全局 - 局部平滑性，其复杂度界限在局部阶段从 $dL/\mu$ 改进为 $dL^*/\mu$。
• 随机梯度下降法（SGD）：在插值假设下，采用随机线搜索的 SGD 实现了依赖于 $L^*$ 的改进速率。
• Nesterov 加速梯度法（NAG）：当结合 Armijo 线搜索时，NAG 也能受益于局部平滑性，尽管与标准 GD 相比，它需要稍长的“全局阶段”才能进入局部区域。
• 非线性共轭梯度法（NLCG）：本文表明，如果 Hessian 矩阵在局部区域内是常数（即局部二次），NLCG 可以实现依赖于 $L^*$ 的加速收敛速率。

3. 案例研究：逻辑回归

本文将该理论应用于二元逻辑回归。研究表明，虽然全局平滑性常数为 $L = \frac{1}{4}\|X\|^2$，但解附近的局部平滑性 $L^*$ 可以显著更小（例如，与损失值 $\ell^* + \delta$ 成正比）。

• 结果：对于逻辑回归，GD(LO) 可以执行比 $1/L$ 大 25 倍的步长，同时仍能降低目标函数值，从而通过最小化 $\delta$ 推导出更紧的迭代复杂度界限。

4. 松弛条件

该框架在多种松弛条件下被证明具有鲁棒性：

• 全局 - 局部强凸性：如果函数在局部是 $\mu^*$-强凸的（且 $\mu^* > \mu$），复杂度将进一步改善。
• Polyak-Łojasiewicz (PL) 条件：结果可推广至满足 PL 不等式的函数，即使没有全局强凸性。
• 全局凸性：对于全局凸但非强凸的函数，GD(LO) 在全局范围内实现次线性速率，在局部范围内实现线性速率。

意义与主张

本文主张，全局 - 局部平滑性提供了一个统一的理论框架，弥合了最坏情况分析与实际性能之间的差距。其主要意义在于：

1. 迭代独立性：与之前的局部平滑性假设不同，全局 - 局部平滑性仅依赖于函数的几何结构，而非算法的路径。这使得不同优化方法之间的迭代复杂度比较变得严格且公平（苹果对苹果）。
2. 为线搜索提供依据：它为简单的线搜索方法为何能在特定且现实的设置下（即局部平滑性远优于全局平滑性时）优于复杂的加速技术提供了理论基础。
3. 适应性：分析表明，算法无需显式知道 $L^*$ 或 $\delta$ 即可受益；线搜索或自适应步长的机制自然地利用了这些属性。

作者总结道，虽然全局平滑性假设是标准做法，但全局 - 局部平滑性更准确地反映了数值优化在实际中的表现，特别是对于逻辑回归和神经网络训练等问题，其解附近的局部几何结构往往比全局景观表现得更加良好。