🔢 mathematics

A $\sqrt{2}$ -accelerated FISTA for composite strongly convex problems

本文介绍了一种针对复合强凸问题的新型 $\sqrt{2}$ 加速前向-后向分裂算法，该算法通过对连续时间信息论精确法（ITEM）进行离散化推导得出，在保持线性收敛速率的同时，将 FISTA 的前导常数提升了 $\sqrt{2}$ 倍。

原作者： Kansei Ushiyama

发布于 2026-08-07

📖 1 分钟阅读🧠 深度阅读

原作者： Kansei Ushiyama

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一个雾气缭绕的广阔山谷中寻找最低点。这不仅仅是一个普通的山谷；这是一个数学景观，其地面由两种不同的材料组成。一部分是平滑且湿滑的，就像抛光后的冰场；而另一部分则是粗糙、崎岖且布满突发悬崖的，就像一条岩石山路。在这个世界里，这个“山谷”代表着我们需要解决的一个复杂问题，例如训练一个能够识别面部的智能 AI，或者计算压缩一张巨大图像的最佳方式。平滑的部分通常代表我们拥有的数据，而粗糙的部分则代表我们必须遵守的规则，比如保持解的简单性或稀疏性。

为了找到这个山谷的底部，计算机使用一种叫做“梯度下降”的策略。把它想象成一名登山者，他沿着感觉最向下的方向迈出一步。如果地面平滑，登山者可以快速滑行。但如果地面崎岖不平，登山者就必须停下来，小心地探测周围环境，然后谨慎地迈出一步。几十年来，科学界已知的最佳“登山者”（算法）都能到达底部，但它们有时会花费很长时间，尤其是在地形复杂的山谷中。它们会走之字形路线、越过目标点，或者陷入小的凹陷中。研究人员一直以来的大问题是：“我们能否制造出一个不仅在颠簸处足够谨慎，而且在平滑部分极其快速，且不会迷路的登山者？”

这篇论文介绍了一个全新的、经过强化升级的登山者：SR2-FISTA。作者 Kansei Ushiyama 设计了一种方法，其在混合地形中的移动速度比以往任何已知技术都要快。他们并非仅仅靠直觉，而是通过将一种连续的、流动的运动（就像河流向下游奔流）转化为计算机可以执行的一系列离散步骤，构建了这位新的登山者。他们的主要发现是，当山谷具有特定的形状——即它是“强凸”（strongly convex）的（这意味着它向上弯曲得很陡峭，保证了只有一个清晰的底部）时，这个新算法到达底部的速度显著快于旧有的冠军算法。

论文通过数学证明，这种新方法通过一个涉及 $\sqrt{2}$ （约 1.41 倍）的因子在指数上提升了速度。简单来说，如果旧的最佳方法需要 100 步才能接近答案，那么这个新方法可能只需要更少的步数，或者在相同的时间内达到更精确的答案。作者还展示了即使当山谷的“粗糙”部分有些奇特或属于“弱凸”（weakly convex，这是一种技术说法，指它并非完全颠簸，而是具有一些平缓的曲线）时，该方法依然有效，而这在医疗成像或金融建模等现实世界问题中是很常见的场景。他们不仅在计算机上进行了模拟，还提供了严谨的数学证明，证明了这位登山者总能找到底部，甚至展示了如何处理计算机并不确切知道平滑部分有多“湿滑”的情况。

论文的故事

问题：混合地形的山谷
论文解决了一个经典的优化问题：寻找函数 $f(x)$ 的最小值，其中 $f(x)$ 是 $g(x)$ 和 $h(x)$ 两部分的和。

$g(x)$ 是“平滑”的部分。想象一座平滑、起伏的丘陵。它很容易滑下，但它可能非常宽阔。
$h(x)$ 是“粗糙”的部分。想象一片崎岖的岩石地或一堵墙。你不能平滑地滑下它；你必须跳跃或小心地踏步。
目标： 找到这两者交汇处的绝对最低点。

在现实世界中，这种情况经常发生。例如，在 LASSO（一种统计学方法）中， $g(x)$ 可能是预测值与实际数据之间的误差（平滑），而 $h(x)$ 是针对变量过多的惩罚（粗糙，像是一个尖锐的转角）。挑战在于，标准方法往往难以在平滑部分的移动速度与对粗糙部分的谨慎之间取得平衡。

旧有的冠军及其缺陷
多年来，“快速迭代收缩/阈值算法”（FISTA）一直是黄金标准。它就像一名利用惯性在平滑部分加速，但在遇到岩石时会停下来检查脚下是否稳固的登山者。它很快，但也有极限。
还有一个被称为 ADR（加速对偶正则化）的方法，声称比它更快。然而，论文指出，虽然 ADR 表现不错，但它并不是绝对最快的。作者指出，以往的方法都有一个由涉及平滑度与山谷曲率比例的特定公式所决定的“速度限制”。

新发现：SR2-FISTA
作者提出了一种新算法，称之为 SR2-FISTA（平方根 2 强凸 FISTA）。

他们是如何构建它的： 他们没有仅仅微调旧的步骤，而是从物理学的视角审视了这个问题。他们从一个连续时间模型开始，这是一个描述粒子随时间运动的方程，称为 ITEM（信息论精确方法）。该模型描述了一个带有特定变化的摩擦力的粒子如何沿山坡下滑。
神奇的成分： 这个模型中的摩擦力并不是恒定的；它随时间变化的方式由一个双曲余切函数（一种高级数学曲线）来描述。通过仔细地将这种平滑、流动的运动“离散化”（分解为计算机可执行的步骤），他们创造了一种新的算法。
结果： 论文证明，该算法的收敛速度比 FISTA 和 ADR 更快。具体来说，速度公式中的“指数”通过 $\sqrt{2}$ 的因子得到了提升。
- 如果旧的方法像是时速 100 英里的汽车，那么这个新方法就像是一辆以一种随时间复合增长的方式加速的汽车，能显著提前到达目的地。
- 论文通过定理 6 提供了数学证明，显示误差（到底部的距离）每一步大约按 $(1 + \sqrt{2q})^{-k}$ 的比例缩小，其中 $q$ 是衡量山谷“强”程度的度量。这比之前已知的最佳速率 $(1 + \sqrt{2q} - 6q)^{-k}$ 更快。

处理“奇特”的岩石
这篇论文的一个独特之处在于，它处理了“粗糙”部分（ $h(x)$ ）并非完美凸函数的情况。在数学术语中， $h(x)$ 可以是“弱凸”的（它可能会稍微向错误的方向弯曲，但不足以破坏整个问题）。

许多旧方法要求用户在应用它们之前，必须重写问题使粗糙部分看起来“规整”（凸）。
作者的方法可以直接作用于原始问题。他们证明了即使粗糙部分有些“摇摆不定”，只要总和仍然是凸的（即山谷依然有一个底部），他们的算法就能奏效。这意义重大，因为这意味着你不需要做额外的数学作业来使用这个工具；你可以直接处理那些凌乱的现实世界问题。

证明与数据
作者对自己的结果非常有信心。他们不仅是运行了一个模拟并说“嘿，它看起来很快”，而是提供了一个严谨的数学证明（使用了一种称为 Lyapunov 函数的东西，这就像一个能量计，证明登山者始终在向底部靠近）。

他们证明了对于特定类型的问题（复合强凸问题），他们的方法在实现目标函数值（ $f(x_k) - f^*$ ）方面达到了已知的最快收敛率。
他们还在一个维度为 10,000（一个极高维度的山谷）的问题上进行了数值实验（第 6 节）。测试表明，他们的算法（SR2FISTA）确实比旧的 FISTA 和 ADR 方法更快，这在实践中证实了他们的理论。

他们并未声称的内容
需要注意的是，论文并没有说的事情：

他们并不声称找到了适用于所有场景的绝对最快方法。他们承认，虽然他们的方法在目标函数值（ $f(x_k) - f^*$ ）方面是已知最快的，但在某些语境下，另一种名为 Prox-ITEM 的方法在距离解的距离（ $\|x_k - x^*\|^2$ ）方面更快。然而，在本文讨论的“粗糙”（非光滑）设定下，你无法总是将距离速度转化为目标函数值的速度，因此他们的结果在目标值方面依然是最优的。
他们也没有声称该方法适用于“非凸”问题（即山谷可能有多个底部且没有清晰路径的情况）。他们严格要求总问题必须是凸的。

为什么这很重要
对于一个好奇的青少年或任何对计算机如何学习感兴趣的人来说，这篇论文就像是为赛车升级引擎。它将一个已经可以解决的问题变得更加高效、快速。在一个数据呈指数级增长的世界里，哪怕只是缩短一点点训练 AI 或解决复杂工程问题所需的时间，都能节省数百万美元和大量的计算时间。通过证明一种基于连续时间物理学的优雅数学方法可以导向一个更快的离散算法，作者为我们应对科学和技术中最困难的优化挑战提供了一个全新的、强大的工具。

技术摘要：针对复合强凸问题的 $\sqrt{2}$ 加速 FISTA

问题表述
本文研究如下形式的复合凸函数的极小化问题：
$\min_{x \in \mathbb{R}^d} f(x) := g(x) + h(x)$
其中 $g: \mathbb{R}^d \to \mathbb{R}$ 是可微的，具有 $L_g$ -Lipschitz 连续梯度且为 $\mu_g$ -凸； $h: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ 是适当的、下半连续的且为 $\mu_h$ -凸。作者定义的 $\mu$ -凸性是指：若 $\mu > 0$ 则为强凸，若 $\mu < 0$ 则为弱凸。整体目标函数 $f$ 被假定为凸函数（即 $\mu = \mu_g + \mu_h \geq 0$ ），尽管其单个组成部分可能是弱凸的。假设 $h$ 的近端算子（proximal operator）可以高效计算。

这种表述通过允许 $h$ 为弱凸（例如用于减少稀疏恢复中偏差的非凸正则项如 MCP 或 SCAD），泛化了标准的复合优化问题，而无需将整体目标函数重新表述为标准的强凸形式。

方法论
所提出的算法被称为 SR2 强凸 FISTA，它是通过对信息论精确方法（ITEM）的连续时间常微分方程（ODE）模型进行离散化而得到的。

连续时间模型： 作者利用了 ITEM ODE：
$\ddot{x}(t) + 3\sqrt{\mu} \coth(\sqrt{\mu}t) \dot{x}(t) + 2\nabla f(x(t)) = 0$
该 ODE 此前已被证明是无约束光滑强凸极小化问题的最优连续时间模型。其阻尼系数 $3\sqrt{\mu} \coth(\sqrt{\mu}t)$ 在 $t \to \infty$ 时插值于三重动量法（TMM），并在 $\mu \to 0$ 时插值于优化梯度法（OGM）。
离散化策略： 为了将其扩展到复合（非光滑）设置，作者采用了弱离散梯度（wDG）。不同于依赖链式法则的标准离散化方法，wDG 提供了一个与非光滑函数 $\mu$ -凸性不等式相兼容的离散代理。具体而言，对于 $f = g + h$ ，离散梯度定义为 $\nabla f(y, z) = \nabla g(z) + \partial h(y)$ 。
算法构建： 通过使用 wDG 和由序列 $A_k$ 定义的特定步进方案对 ITEM ODE 进行离散化，作者推导出了一个显式迭代算法（算法 1）。步长和动量项通过求解一个确保离散李雅普诺夫函数（Lyapunov function）非增的递推关系来确定。该算法需要预先知道 $L_g, \mu_g$ 和 $\mu_h$ ，尽管作者指出 $L_g$ 可以通过回溯法（backtracking）进行自适应选择。

核心贡献

新颖算法： 本文引入了 SR2 FISTA，这是一种加速的前向-后向分裂法，可以直接处理弱凸正则项，而无需重新表述问题。
收敛速率提升： 对于复合强凸情况（ $\mu > 0$ ），所提方法在目标函数值 $f(x_k) - f^\star$ 上实现了线性收敛率，其几何因子为 $r^{-k}$ ，其中：
$r = 1 + q_2 + \frac{\sqrt{(q_1 + q_2)(2 - q_1 + q_2)}}{1 - q_1}$
这里 $q_1 = \mu_g/L_g$ 且 $q_2 = \mu_h/L_g$ 。在 $g$ 为强凸且 $h$ 为凸的具体情况下（ $\mu_g > 0, \mu_h = 0$ ），该因子在小条件数下比此前已知的最佳速率（由 ADR [16] 实现）在指数上提高了 $\sqrt{2}$ 倍。
统一分析： 收敛分析是与 ITEM ODE 的连续时间分析并行推导的，利用了一个镜像了连续能量函数的离散李雅普诺夫函数。这种方法提供了清晰的证明结构，并将其有效性扩展到了其中一个分量为弱凸的情况，只要总和保持为凸。
一般凸情况： 当 $\mu = 0$ 时，该方法恢复了标准 FISTA 的 $O(1/k^2)$ 收敛速率。

结果

理论界限： 本文确立了当 $\mu > 0$ 时，目标函数间隙满足：
$f(x_k) - f^\star \leq \min \left( \frac{L_g - \mu_g}{2} r^{-k+1}, \frac{6L_g}{k^2} \right) \|x_0 - x^\star\|^2$
该界限既提供了快速的非渐近次线性速率（适用于较小的 $k$ 或较小的 $\mu$ ），也提供了指数线性收敛速率。
数值实验： 作者在一个维度为 $d=10,000$ 的合成问题上测试了该算法，该问题涉及最小二乘损失（ $g$ ）和极小极大凹惩罚（MCP）正则项（ $h$ ），其中 $h$ 是弱凸的。结果表明，SR2 FISTA 的收敛速度略快于现有的加速方法（FISTA 和 ADR），且显著快于 ISTA。观察到的收敛情况与理论预测一致，在初始阶段优于参考速率 $O(e^{-\sqrt{2q}k})$ 。

意义与主张
作者声称，据其所知，SR2 FISTA 在目标函数值 $f(x_k) - f^\star$ 方面实现了已知最快的收敛速率，用于复合强凸极小化问题。

作者对于其速率的优越性表现得较为谦逊。他们承认，虽然 Prox-ITEM [25] 在复合强凸设置下的解距离（ $\|x_k - x^\star\|^2$ ）方面实现了最优速率，但目前尚不清楚这是否能转化为非光滑设置下目标函数值的最优速率。因此，作者并未声称其方法在绝对意义上是“最优”的，而是指出其相对于之前的最先进技术（ADR），在指数的领先常数上提高了 $\sqrt{2}$ 倍。

这项工作强调了利用 ODE 方法推导新算法的效用，并证明了 ITEM ODE 框架可以成功扩展到涉及弱凸正则项的复合问题，这一领域在稀疏恢复和成像中的偏差减少方面正日益受到重视。

论文的故事

类似论文