大步长梯度下降在逻辑回归上收敛多快？

论文界定的是不稳定阶段而非全程

问题在于：当步长被刻意取得很大时，需要多少步梯度下降才能把逻辑损失压到目标 ε 以下。论文针对线性可分数据上的二分类逻辑回归给出答案，从初始化 w₀ = 0 出发，使用常数步长 η。

关键对象是相变时间 τ，定义为首次出现 L(w_t) ≤ 1/η 的步 t。在 τ 之前损失可能振荡而非单调下降；从 τ 起它单调下降。因此总步数被拆成这段不稳定阶段的长度加上随后的稳定阶段。论文的主要定理界定 τ，并复述了此前的结果：从第 τ 步起损失单调下降。

这一区分很重要，因为两个阶段由不同的量支配。稳定阶段的速率继承自此前工作；新的贡献是对振荡阶段能持续多久给出了紧得多的界。

大步长为何使下降引理失效

经典收敛保证依赖下降引理：若损失是 β-光滑的且步长小于 2/β，则每一步都使损失下降，速率可由逐步下降量求和得到。对该逻辑损失 β = 1/4，因此步长小于 8 即可保证单调下降。

论文研究的步长远高于该阈值，此时损失不必单调下降。这正是实践者所称的稳定性边缘：锐度上升到约 2/η，训练恰好发生在下降引理不再适用的地方。论文的框架是：这里的加速来自梯度下降自身的动力学，而非设计好的步长调度。

由于单调下降的论证不再可用，证明不能简单地对每步进展求和，而必须直接控制振荡阶段，这正是新的计数论证所做的事。

从 η 的线性界到多对数界

在步长 η = 1/ε 下，论文证明能在 O(ln^p(1/ε)) 步内达到损失 ε，其中 p 只取决于数据的间隔 γ 和秩 r。对于固定的问题相关参数，这把任意维度下此前的 O(1/√ε) 步复杂度改进为 1/ε 的多对数级。

改进落在相变时间的界上。此前的分析把不稳定阶段界定为步长的线性函数，这限制了在固定步数预算下可用的步长上限，并被猜测可以改进。本文表明，只要步长超过阈值 η₀，不稳定阶段就在 O((ln η)^p) 步内结束。

大间隔情形另有一个初等的结论：当 γ ≥ 1/√2 且 η ≥ 64n² 时，一步即可，因此 τ ≤ 1。多对数界适用于 0 < γ < 1/√2 的情形。

嵌套区间把振荡变成计数问题

证明既不对轨迹上的势函数取平均，也不追踪迭代点沿最大间隔方向的振荡——那种运动只在平面内才是一维的。它转而数步数。

某些带符号间隔为负的步被证明数量很少。其余步被组织成递归嵌套的区间，每个区间携带若干参考方向，约束区间内的每次更新。携带 j 个参考方向的区间分裂为一段短前缀和至多 R 个子区间，其中 R = 1 + ⌈4Λ/θ⌉、Λ = ln η；每个子区间继承这 j 个方向并新增一个。

随后有两个量控制结构。一个几何容量引理表明，带符号样本凸包中至多有 ν + 2 个向量两两内积不超过 θ，从而用间隔和秩界定嵌套深度。一个计数论证界定每一深度上有多少区间：由于兄弟区间的起始系数取对数后相隔超过 θ/4，联合计数可带来阶乘级的节省，得到 D_j(I) ≤ 2(6Λ/θ)^j / j!。

指数 p 从何而来

深度 ν 定义为 max{0, min{r, ⌊γ⁻² + (γ⁻² − 1)/(h − 1)⌋ − 2}}，其中 h = ⌈ln(16γ⁻²)⌉，r 是数据的秩。当 ν ≥ 1 时，指数 p 等于 ν 加上修正项 ν ln(18hγ⁻²/ν) / ln(max{2, ν})；当 ν = 0 时 p 等于 0。

论文明确解释了这一取舍。原始界 τ ≤ C(6hγ⁻² ln η)^ν / ν! 的阶数 ν 更小，但其系数在 1/γ 上可能是超多项式的。指数 p 吸收该系数，使前因子 C 保持为 n 和 1/γ 的多项式。用渐近记号表示，C = O(γ⁻⁴ ln(γ⁻²)[n + ln²(γ⁻²)])，阈值 η₀ 为 Õ(γ⁻² + ln n)，p = O(min{r, γ⁻²} ln(γ⁻²))。

阈值 η₀ 的选取使 η ≥ 4、Λ > 10、4Λ ≤ ηθ，且 CΛ^p 低于证明中使用的有限时域。值得注意的是，论证从不要求 Λ ≥ ν，否则将意味着步长需要指数级大。

该结果覆盖与不覆盖的范围

该保证在有界且可分的数据下成立：每个 ‖x_i‖ ≤ 1，标签 y_i ∈ {±1}，且存在单位向量 w* 使所有 i 满足 ⟨y_i x_i, w*⟩ ≥ γ。秩 r 是带符号样本张成空间的维数，至多为 min{n, d}。

该结果是对相变时间的上界，而非下界。作者表示，收紧其界中的常数并建立新的下界留待未来工作。该界还只涉及常数步长、逻辑回归和线性可分数据这一特定设定；论文将其与为极小值可达的光滑凸目标设计的步长调度作了对比。

另一点范围说明是，分析假设步长至少为 η₀，而该阈值随 1/γ 和 ln n 增大。多对数相变是关于该情形的陈述，而非关于任意步长。

真正重要的比较是与线性界之比

本文中与决策相关的比较，是同一个量——相变时间 τ——的两个界之间的比较。此前的分析把它界定为步长的线性函数，这正是固定步数预算下可用步长受限的原因。本文把它界定为 C(ln η)^p，因此不稳定阶段只随 η 多对数增长。

正是这一变化使激进选择 η = 1/ε 与 1/ε 的多对数步复杂度相容。实际解读是有条件的：当间隔 γ 和秩 r 使 p 保持较小时改进最大，因为 p = O(min{r, γ⁻²} ln(γ⁻²))，而前因子 C 的量级为 γ⁻⁴ ln(γ⁻²) 乘以 n 再加上对数项。当间隔大到 γ ≥ 1/√2 且 η ≥ 64n² 时，不稳定阶段坍缩为至多一步。

论文还把自身与二维结果作了对照：后者证明不稳定阶段在独立于 η 的步数内结束，但依赖只在平面内才可用的一维运动追踪。本文的贡献是通过区间层级和基于间隔与秩的深度界，把类似的控制推广到任意维度。

本文引用的文献