跳转至

Symmetric Rank-k Methods

作者: Chengchang Liu, Cheng chen, Luo Luo
来源: JMLR
主题: 统计计算 / 算法
相关性: 4/10
机构绿灯: Chinese University of Hong Kong(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文属于连续优化中的拟牛顿方法(Quasi-Newton Methods) 这一子方向。其根本的统计/科学问题是:在目标函数光滑且强凸的假设下,如何用一阶信息(梯度)构造对 Hessian 矩阵(或其逆)的近似,从而在迭代中同时获得接近牛顿法的快速收敛(超线性甚至二次)和远低于牛顿法的单步计算/存储成本。该方向自 1959 年 Davidon 提出变尺度法以来已高度成熟,经典方法(BFGS、DFP、SR1)的渐近超线性收敛性在 1970 年代已被证明(Powell, 1971; Dennis and Moré, 1974),但非渐近(有限步)显式收敛速率的刻画直到 2020 年代才由 Rodomanov 和 Nesterov 等人突破。本文的定位是在这一"显式速率"研究浪潮中,将单方向的拟牛顿更新推广到块(block)更新,并给出第一个显式的、随块大小 k 加速的超线性收敛率。

发展脉络(history)

奠基工作(1959–1970s):Davidon (1959) 提出变尺度法(variable metric method),首次引入用秩一或秩二修正迭代逼近 Hessian 逆的思想。Broyden (1967, 1970a,b) 和 Shanno (1970) 系统化地发展了 Broyden 族(含 BFGS、DFP、SR1),并建立了这些方法的局部超线性收敛性。这一时期的理论是渐近的——只保证收敛速率是超线性的,但不给出具体的有限步速率表达式。

主要进展(2020–2023):Rodomanov 和 Nesterov (2021a, 2022) 首次给出了经典 BFGS 和 SR1 方法的非渐近显式超线性收敛率,形如 O((dκ/t)^{t/2}) 和 O((1−1/d)^{t(t−1)/2})。Ye et al. (2023) 进一步改进了 SR1 的速率。Jin 和 Mokhtari (2023) 给出了经典 BFGS/DFP 在额外假设(初始 Hessian 估计足够接近真值)下的 O((1/t)^{t/2}) 速率。这些工作把拟牛顿方法的理论从"渐近定性"推进到"有限步定量",但都局限于单方向(秩一或秩二)更新。

当前 frontier(2023–2026):块拟牛顿方法(block quasi-Newton)在实证中表现出比单方向方法更快的收敛(Gao and Goldfarb, 2018; Kovalev et al., 2020),但其理论分析长期停留在渐近超线性或线性速率层面,缺乏显式的、与块大小 k 相关的超线性速率。Gower and Richtárik (2017) 从矩阵逼近的角度研究了随机化块更新的线性收敛性,但未给出优化问题上的超线性速率。本文填补的正是这一缺口:给出 SR-k 方法(以及改进的块 BFGS/DFP)的第一个显式超线性速率 O((1−k/d)^{t(t−1)/2}),并证明块大小 k 直接进入速率底数。

本文的位置:本文是块拟牛顿方法显式速率研究的"第一块基石"。它把 Rodomanov–Nesterov 的单方向分析框架推广到 k 方向,并揭示了块更新的本质优势——每轮用 k 个 Hessian-vector product 换取速率底数从 (1−1/d) 提升到 (1−k/d)。同时,本文也承认其分析局限于局部收敛(需要初始点足够接近最优解),全局收敛性仍是开放问题。

子线索聚类

被引文献大致落在三条子线索上:

  1. 经典拟牛顿方法的渐近理论(Davidon 1959; Broyden 1967, 1970a,b; Shanno 1970; Powell 1971; Dennis and Moré 1974; Dai 2002):建立 BFGS/DFP/SR1 的局部超线性收敛性,但无显式速率。这一簇是拟牛顿方法的理论基础,其核心工具是 Dennis–Moré 条件(衡量 Hessian 近似误差的收缩)。

  2. 非渐近显式速率分析(Rodomanov and Nesterov 2021a, 2021b, 2022; Ye et al. 2023; Jin and Mokhtari 2023; Jin et al. 2022):在强凸+光滑+强自和谐(strong self-concordance)假设下,给出单方向拟牛顿方法的有限步超线性速率。这一簇的关键技术是"势函数"(potential function)分析——构造一个同时控制 Hessian 近似误差和梯度范数的量,证明其每轮以 (1−1/d) 因子收缩。本文的 SR-k 分析直接继承了这一框架。

  3. 块拟牛顿方法的算法设计与渐近分析(Schnabel 1983; O'Leary and Yeremin 1994; Gao and Goldfarb 2018; Gower and Richtárik 2017; Kovalev et al. 2020; Lee and Sun 2024):设计多方向更新的拟牛顿方法,证明其渐近超线性收敛或线性收敛,但缺乏显式速率。这一簇的动机是:块更新每轮利用更多曲率信息,实证上比单方向方法更快,但理论上"快多少"一直不清楚。

这个方向在追问的核心问题

  1. 显式速率:拟牛顿方法的超线性收敛速率能否用问题维度 d、条件数 κ、迭代次数 t 显式表达?——Rodomanov–Nesterov 系列已解决单方向情形,本文将其推广到块情形。
  2. 块大小的作用:块大小 k 如何影响收敛速率?是否存在"每增加一个方向,速率底数提升 k/d"的精确刻画?——本文给出肯定回答(定理 4.3)。
  3. 计算-收敛权衡:块更新每轮需要 k 个 Hessian-vector product,其计算成本增加是否被更快的收敛速率所补偿?——本文的速率分析为这一权衡提供了理论依据,但未做完整的复杂度分析。
  4. 全局收敛性:现有显式速率都是局部的(需要初始点足够接近最优解),能否建立全局的显式超线性速率?——本文未解决,仅在结论中提及。

⚠️ 作者的 framing(这是作者的说法)

作者在引言中将缺口 frame 为:"块拟牛顿方法在实证中优于单方向方法,但其理论优势长期缺乏显式刻画;我们给出第一个显式的、随 k 加速的超线性收敛率,从而在理论上解释了块更新的优势。" 作者将本文定位为"显然的下一步"——因为 Rodomanov–Nesterov 已经建立了单方向的显式速率框架,而块更新是自然的推广方向。

被淡化或回避的竞争路线: - 随机化 vs 贪心策略:作者同时分析了随机化和贪心两种策略,但贪心策略需要计算矩阵的 top-k 对角元(计算成本 O(d²)),作者在实验部分承认贪心策略的计算开销可能抵消其收敛优势,但理论部分未做复杂度对比。 - 全局收敛性:作者回避了全局收敛性问题,仅给出局部结果。相比之下,Jin 和 Mokhtari (2023) 的全局分析(尽管需要额外假设)是更全面的框架。 - 非光滑或约束优化:本文仅处理无约束光滑强凸问题,未涉及投影拟牛顿或近端拟牛顿等扩展。

什么明显该被引 / 该存在、却没出现在 intro 里? - 随机拟牛顿方法的统计效率分析(如 SFO 复杂度):本文的速率分析是确定性的,未讨论随机梯度或随机 Hessian 近似的场景。考虑到作者之一(Luo Luo)此前有随机拟牛顿方法的工作,这一缺失值得注意。 - 拟牛顿方法与二阶优化在统计估计中的联系:本文未引用任何统计学文献(如 M-estimation 中的拟牛顿方法),尽管其收敛速率分析对统计计算有直接意义。 - 低阶多项式障碍(low-degree polynomial barrier):本文的贪心策略本质上是在做"稀疏"的 Hessian 近似,这与高维统计中的稀疏恢复问题有潜在联系,但作者未提及。

张力

未见明显对立引用。各被引工作之间在"显式速率"这一目标上是一致的,差异仅在于方法(单方向 vs 块)和假设(是否需要初始 Hessian 估计足够好)。一个值得注意的微妙点是:Rodomanov 和 Nesterov (2021a) 的贪心 SR1 速率是 O((1−1/d)^{t(t−1)/2}),而本文的 SR-k 在 k=1 时退化为同一速率,但本文的贪心策略(选 top-k 对角元)与 Rodomanov–Nesterov 的贪心策略(选最大对角元)在 k=1 时一致,在 k>1 时是自然推广——这暗示本文的分析框架是前者的严格推广,而非平行路线。


二、最核心、最简单的例子 / 数学问题

第一步:符号、模型、可观测数据

在展开技术细节之前,先把记号一次性立清楚。本文研究的是确定性无约束优化问题:

\[\min_{x \in \mathbb{R}^d} f(x)\]

其中 \(f: \mathbb{R}^d \to \mathbb{R}\) 是二次可微的。核心记号如下:

记号 含义 类型
\(x_t \in \mathbb{R}^d\) 第 \(t\) 轮迭代的估计值 随机变量(由算法产生)
\(\nabla f(x_t) \in \mathbb{R}^d\) 目标函数在 \(x_t\) 处的梯度 可观测(一阶 oracle)
\(\nabla^2 f(x_t) \in \mathbb{R}^{d \times d}\) 目标函数在 \(x_t\) 处的 Hessian 不可直接观测(需通过 Hessian-vector product 近似)
\(G_t \in \mathbb{R}^{d \times d}\) 第 \(t\) 轮对 Hessian 的估计 算法维护的状态
\(A \triangleq \nabla^2 f(x_*)\) 最优解处的 Hessian 目标矩阵(未知但固定)
\(U_t \in \mathbb{R}^{d \times k}\) 第 \(t\) 轮选取的 \(k\) 个方向 由贪心或随机策略生成
\(k\) 块大小(每轮使用的方向数) 算法超参数,\(1 \le k \le d\)
\(d\) 问题维度 已知
\(\mu, L\) 强凸参数和光滑参数(\(\mu I \preceq \nabla^2 f(x) \preceq L I\)) 已知上界
\(\kappa = L/\mu\) 条件数 派生量
\(M\) 强自和谐参数(Assumption 2.4) 已知
\(\lambda(x) \triangleq \sqrt{\nabla f(x)^\top (\nabla^2 f(x))^{-1} \nabla f(x)}\) 局部梯度范数(牛顿方向范数) 收敛性度量
\(\tau_A(G) \triangleq \operatorname{tr}(G - A)\) Hessian 估计误差的迹 矩阵逼近误差度量
\(\sigma_A(G) \triangleq \operatorname{tr}(A^{-1}(G - A))\) 加权 Hessian 估计误差 矩阵逼近误差度量(用于 BFGS/DFP)

模型:目标函数 \(f\) 满足: 1. \(\mu\)-强凸:\(f(y) \ge f(x) + \nabla f(x)^\top (y-x) + \frac{\mu}{2}\|y-x\|^2\) 2. \(L\)-光滑:\(\|\nabla f(x) - \nabla f(y)\| \le L\|x-y\|\) 3. \(M\)-强自和谐(Assumption 2.4):\(\nabla^2 f(y) - \nabla^2 f(x) \preceq M\|y-x\|_z \nabla^2 f(w)\) 对所有 \(x,y,z,w\) 成立

可观测数据:算法在每轮可以获取: - 梯度 \(\nabla f(x_t)\)(一阶 oracle) - \(k\) 个 Hessian-vector product \(\nabla^2 f(x_{t+1}) u_t^{(j)}\)(二阶 oracle,\(j=1,\dots,k\))

不可观测但需要估计的量:完整的 Hessian 矩阵 \(\nabla^2 f(x_t)\)。拟牛顿方法的核心就是用 \(k\) 个 Hessian-vector product 的信息来更新 \(G_t\),使其逼近 \(\nabla^2 f(x_t)\)。

关键区分:本文的"可观测"与因果推断中的可观测数据不同——这里没有样本数据,而是oracle 模型:算法可以查询梯度(一阶 oracle)和 Hessian-vector product(二阶 oracle),但查询有成本。收敛速率分析回答的是:给定 oracle 预算,算法能以多快的速度逼近最优解?

第二步:最小内核

把原文的所有技术假设剥掉,本文的核心数学问题可以归结为:

矩阵逼近问题:给定一个正定矩阵 \(A \in \mathbb{R}^{d \times d}\)(目标 Hessian)和一个正定矩阵 \(G \in \mathbb{R}^{d \times d}\)(当前估计),如何用 \(k\) 个方向 \(U \in \mathbb{R}^{d \times k}\) 的信息,构造一个新的估计 \(G_+\),使得 \(G_+\) 比 \(G\) 更接近 \(A\)?

本文给出的答案是 SR-k 更新(定义 3.1):

\[G_+ = G - (G - A)U \left(U^\top (G - A) U\right)^\dagger U^\top (G - A)\]

这个公式的直觉是:\(G - A\) 是当前估计的误差矩阵。SR-k 更新在 \(U\) 张成的 \(k\) 维子空间上"消除"误差——它把 \(G - A\) 投影到 \(U\) 的列空间上,然后从 \(G\) 中减去这个投影。如果 \(U\) 恰好包含了 \(G - A\) 的最大特征方向,那么一步就能大幅减少误差。

为什么这个更新有效? 关键在于两个引理:

  1. 引理 3.3:对于任意满秩 \(U\),SR-k 更新保证误差的迹不增加,且减少量至少为 \(\operatorname{tr}\left(U(U^\top U)^{-1}U^\top (G - A)\right)\)。这个下界是 \(G - A\) 在 \(U\) 列空间上的投影的迹。

  2. 引理 3.4:如果 \(U\) 是随机高斯矩阵(每个元素独立服从 \(N(0,1)\)),那么

    \[\mathbb{E}\left[\operatorname{tr}\left(U(U^\top U)^{-1}U^\top R\right)\right] = \frac{k}{d}\operatorname{tr}(R)\]
    即随机投影平均消除 \(k/d\) 比例的误差。如果 \(U\) 是贪心选择的(取 \(G - A\) 的 top-\(k\) 对角元对应的坐标向量),那么
    \[\operatorname{tr}\left(U(U^\top U)^{-1}U^\top R\right) \ge \frac{k}{d}\operatorname{tr}(R)\]
    即贪心选择至少消除 \(k/d\) 比例的误差。

最小内核的数学命题:

命题(SR-k 更新的收缩性质):设 \(A \preceq G \preceq \eta A\),\(U\) 由随机或贪心策略生成。则

\[\mathbb{E}[\tau_A(G_+)] \le \left(1 - \frac{k}{d}\right)\tau_A(G)\]
其中 \(\tau_A(G) = \operatorname{tr}(G - A)\)。

这个命题的证明只需要三步: 1. 用引理 3.3 把 \(\tau_A(G_+)\) 上界为 \(\tau_A(G) - \operatorname{tr}(U(U^\top U)^{-1}U^\top (G - A))\); 2. 用引理 3.4 把 \(\operatorname{tr}(U(U^\top U)^{-1}U^\top (G - A))\) 下界为 \(\frac{k}{d}\tau_A(G)\); 3. 合并得到 \(\mathbb{E}[\tau_A(G_+)] \le (1 - k/d)\tau_A(G)\)。

为什么这是"最小内核"? 因为整个论文的收敛性分析(定理 4.3)本质上就是把上述矩阵逼近命题嵌入到拟牛顿迭代的框架中:每轮迭代先做一次梯度下降(或牛顿步),然后用 SR-k 更新改进 Hessian 估计。矩阵逼近的收缩因子 \((1 - k/d)\) 直接决定了超线性收敛的速率底数。当 \(k=1\) 时,它退化为 Rodomanov–Nesterov 的 SR1 速率;当 \(k=d\) 时,收缩因子为 0,即一步就精确恢复 Hessian,对应牛顿法的二次收敛。

这个最小内核的难度在哪? 引理 3.3 的证明需要处理 Moore-Penrose 逆的代数恒等式,而引理 3.4(a) 的证明需要用到 Stiefel 流形上的均匀分布性质(或等价的 elementary 证明,见附录 A)。真正的技术难点在于将矩阵逼近的收缩性质与优化迭代的收敛性结合起来——这需要精心构造势函数,使得 Hessian 估计误差和梯度范数同时被控制。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:块拟牛顿方法(每轮用 \(k\) 个 Hessian-vector product 更新 Hessian 估计)能否获得显式的、优于单方向方法的超线性收敛速率?
  2. 核心工具/方法:提出了 SR-k 更新(对称秩-k 矩阵逼近),并基于强自和谐假设和势函数分析,证明了 SR-k 方法、随机块 BFGS 和随机块 DFP 方法的显式局部超线性收敛速率。
  3. 主要结论:SR-k 方法达到 O((1−k/d)^{t(t−1)/2}) 的局部超线性速率,随机块 BFGS/DFP 达到 O((1−k/(κd))^{t(t−1)/2}),首次从理论上解释了块更新相比单方向更新的加速效应。

关键设定与假设

在第二节最小记号的基础上,本文的完整设定如下:

目标函数(Assumptions 2.1, 2.2, 2.4): - \(f\) 是 \(L\)-光滑且 \(\mu\)-强凸的(保证存在唯一最优解 \(x_*\),且 Hessian 有界) - \(f\) 是 \(M\)-强自和谐的(控制 Hessian 的 Lipschitz 变化,这是拟牛顿方法局部分析的关键) - 初始点 \(x_0\) 满足 \(M\lambda(x_0) \le \ln(3/2)/(4\eta_0)\)(局部收敛条件,保证迭代不离开收敛域)

算法设定(Algorithm 1): - 每轮迭代:先计算梯度下降步 \(x_{t+1} = x_t - G_t^{-1}\nabla f(x_t)\) - 然后构造方向矩阵 \(U_t\): - 随机策略:\([U_t]_{ij} \overset{\text{i.i.d.}}{\sim} N(0,1)\) - 贪心策略:\(U_t = E_k(\tilde{G}_t - \nabla^2 f(x_{t+1}))\),即取误差矩阵的 top-\(k\) 对角元 - 最后用 SR-k 更新:\(G_{t+1} = \text{SR-k}(\tilde{G}_t, \nabla^2 f(x_{t+1}), U_t)\)

相比已有工作的关键差异: - 相比 Rodomanov–Nesterov 的单方向 SR1/BFGS:本文允许 \(k \ge 2\),且速率底数从 \((1-1/d)\) 提升到 \((1-k/d)\)。 - 相比 Gao–Goldfarb 和 Kovalev 等人的块 BFGS:本文给出了显式非渐近速率,而非仅渐近超线性。 - 相比 Gower–Richtárik 的随机块方法:本文同时覆盖了贪心和随机两种策略,且速率与 \(k\) 的关系更精确。

主要结果

定理 4.2(线性收敛):在定理 4.3 的假设下,SR-k 方法(Algorithm 1)满足

\[\lambda(x_t) \le \left(1 - \frac{1}{2\eta_0}\right)^t \lambda(x_0)\]
即先以线性速率收敛到一个局部邻域。

定理 4.3(超线性收敛):在更强的初始条件(19)下,SR-k 方法满足

\[\mathbb{E}\left[\frac{\lambda(x_{t+1})}{\lambda(x_t)}\right] \le 2d\kappa\eta_0\left(1 - \frac{k}{d}\right)^t\]
这意味着经过 \(t\) 轮迭代后,每步的收缩因子以 \((1-k/d)^t\) 的速度趋于 0,即超线性收敛。当 \(k=1\) 时,这退化为 Rodomanov–Nesterov 的 SR1 速率;当 \(k=d\) 时,收缩因子为 0,对应二次收敛。

定理 5.5(随机块 BFGS/DFP):随机块 BFGS/DFP 方法(Algorithm 2)满足

\[\mathbb{E}\left[\frac{\lambda(x_{t+1})}{\lambda(x_t)}\right] \le 2d\eta_0\left(1 - \frac{k}{d\kappa}\right)^t\]
速率底数为 \((1 - k/(d\kappa))\),比 SR-k 的 \((1-k/d)\) 慢一个 \(\kappa\) 因子,这与单方向情形中 BFGS 比 SR1 慢的观察一致。

定理 5.8(更快随机块 BFGS):通过引入缩放方向(Algorithm 3),随机块 BFGS 的速率提升到 \((1-k/d)\),与 SR-k 匹配。

技术难点与证明技巧:

  1. 势函数设计:证明的核心是构造一个势函数 \(\Phi_t = \lambda(x_t) + c \cdot \tau_{\nabla^2 f(x_t)}(G_t)\),同时控制梯度范数和 Hessian 估计误差。SR-k 更新的矩阵逼近性质(定理 3.6)保证了 \(\tau\) 的收缩,而梯度下降步保证了 \(\lambda\) 的收缩。

  2. 随机矩阵的期望计算:引理 3.4(a) 的关键是计算 \(\mathbb{E}[U(U^\top U)^{-1}U^\top]\)。作者使用了 Stiefel 流形上的均匀分布性质(或附录 A 的 elementary 证明),得到 \(\mathbb{E}[U(U^\top U)^{-1}U^\top] = \frac{k}{d}I_d\)。这个恒等式是随机策略分析的基石。

  3. 贪心策略的确定性分析:引理 3.4(b) 的证明不需要概率工具,而是直接利用 top-\(k\) 对角元的性质:\(\sum_{i=1}^k r_i \ge \frac{k}{d}\sum_{i=1}^d r_i\)(其中 \(r_i\) 是 \(R\) 的对角元)。这个不等式虽然简单,但抓住了贪心选择的本质。

  4. 缩放方向的技巧(Algorithm 3):为了消除条件数 \(\kappa\) 的影响,作者引入了缩放矩阵 \(L_t\)(满足 \(L_t^\top L_t = G_t^{-1}\)),将方向从 \(U_t\) 改为 \(L_t^\top U_t\)。这个技巧在 Gower–Richtárik 的工作中已有雏形,但本文将其与显式速率分析结合。

真实例子与应用

本文的实验部分(第 6 节)在三个数据集上测试了 SR-k 方法: - MNIST(\(d = 780\)):手写数字识别,逻辑回归模型 - sido0(\(d = 4{,}932\)):药物活性预测,逻辑回归模型 - gisette(\(d = 5{,}000\)):手写数字区分,逻辑回归模型

实验设置:正则化逻辑回归(公式 36),比较 R-SR-k、G-SR-k、RB-BFGSv2、RB-DFP、FRB-BFGS 与基线方法(R-SR1、G-SR1、RB-BFGSv1)。主要发现: 1. 迭代次数:R-SR-k 和 G-SR-k 在达到相同梯度范数阈值时所需的迭代次数显著少于 SR1 方法,且 \(k\) 越大,迭代次数越少。 2. 运行时间:虽然块更新每轮需要 \(k\) 个 Hessian-vector product,但由于迭代次数大幅减少,总运行时间仍然优于 SR1 方法(在 \(k\) 不超过 200 时)。 3. 贪心 vs 随机:G-SR-k 通常比 R-SR-k 少用迭代次数,但每轮需要额外计算 top-\(k\) 对角元,在 \(d\) 较大时可能更耗时。

这个实验设计想说明的是:块更新不仅理论上更快,实践上也确实更快——但"快"的体现是迭代次数而非单轮计算时间,且 \(k\) 的选择存在权衡(\(k\) 太大时单轮计算成本可能抵消收敛加速)。

🔎 结论是否比证明窄

是的,存在几处"证明窄于结论"的情况:

  1. 定理 4.3 的初始条件(19):要求 \(M\lambda(x_0) \le \frac{\ln 2}{2} \cdot \frac{d-k}{\eta_0 d^2 \kappa}\)。这个条件比定理 4.2 的条件(\(M\lambda(x_0) \le \ln(3/2)/(4\eta_0)\))严格得多,且依赖于 \(d\) 和 \(k\)。作者在 Remark 4.4 中承认,这个条件是为了保证分析中某些不等式成立,但实际算法可能在更宽松的条件下也收敛。结论的适用范围(局部收敛)比证明所要求的初始条件更广。

  2. 定理 5.5 的速率底数:作者声称随机块 BFGS/DFP 的速率是 O((1−k/(κd))^{t(t−1)/2}),但定理 5.3 的证明中使用了条件 \(\mu I \preceq A \preceq L I\) 来估计 \(\kappa\)。如果 Hessian 的条件数在迭代过程中变化(强自和谐只控制变化率,不控制范围),这个速率可能不成立。证明假设 Hessian 条件数在整个迭代过程中有界,但结论未明确说明这一假设。

  3. Corollary 4.6(\(k=d\) 时的二次收敛):证明依赖于 \(U_t \in \mathbb{R}^{d \times d}\) 非奇异(几乎必然成立),但实际计算中 \(k=d\) 意味着每轮需要 \(d\) 个 Hessian-vector product,计算成本与牛顿法相同。结论的"二次收敛"在计算上并不比牛顿法更优,但作者未在结论中说明这一计算代价。

  4. 实验部分的泛化性:实验仅在逻辑回归(强凸)上验证,未测试非强凸或非光滑问题。作者在结论中承认"扩展到非凸问题的分析是未来工作",但未提及实验的局限性。


四、开放问题

以下开放问题均扎根于本文的具体语句:

  1. 全局收敛性:本文的所有收敛速率都是局部的(需要初始点满足条件 19)。作者在结论部分(第 7 节)写道:"It would be interesting to investigate the global convergence of block quasi-Newton methods." 具体要证什么:能否在不需要初始点接近最优解的条件下,建立 SR-k 方法的全局超线性收敛速率?这与 Jin–Mokhtari (2023) 的全局分析框架(针对单方向 BFGS)有何异同?

  2. 有限内存变体:作者在结论中提及:"The limited memory versions of our methods are also worth exploring." 具体要算什么:当内存限制为 \(O(kd)\) 而非 \(O(d^2)\) 时,SR-k 更新的收敛速率如何退化?这需要重新设计更新公式(类似 L-BFGS 的两循环递归),并分析其对势函数收缩的影响。

  3. 随机块大小的自适应选择:本文的 \(k\) 是固定的超参数。作者在实验部分观察到"\(k\) 越大迭代越少但单轮成本越高",但未给出 \(k\) 的最优选择策略。具体要算什么:能否根据当前 Hessian 估计的误差谱自适应地选择 \(k\),使得总计算量最小化?这需要刻画 \(k\) 与单轮计算成本、收敛速率之间的精确权衡。

  4. 非欧几里得推广:本文的分析基于欧几里得范数。作者在 Assumption 2.4 中使用了强自和谐假设,但未讨论该假设在非欧几里得设置(如 Bregman 距离)下的推广。具体要算什么:在黎曼流形或 Bregman 距离下,SR-k 更新的收缩性质是否仍然成立?

  5. 与随机优化的结合:本文是确定性优化方法。作者在引言中提到了随机拟牛顿方法(如 Kovalev et al. 2020),但未将其与 SR-k 结合。具体要算什么:当梯度由随机 oracle 给出时(如随机梯度下降),SR-k 更新的收敛速率如何变化?这需要将本文的势函数分析与随机逼近理论结合。


关于"是否是真 gap"的提醒:要确认上述问题是否是真 gap,建议去读以下近期论文的引言部分(每篇约 5 篇): - Rodomanov 和 Nesterov (2021a, 2022) 的后续工作 - Jin 和 Mokhtari (2023, 2024) 的全局分析系列 - Kovalev et al. (2020) 的随机块 BFGS - Lee 和 Sun (2024) 的几乎多割线 BFGS

如果这些论文的引言都指向"块更新的显式速率"这一缺口,那么本文确实是该方向的奠基工作;如果它们已经解决了部分问题,那么本文的贡献需要重新定位。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论