通过msign来计算奇异值裁剪mclip(下)
By 苏剑林 | 2025-06-23 | 6944位读者 | 引用前面我们在《通过msign来计算奇异值裁剪mclip(上)》讨论了奇异值裁剪$\newcommand{mclip}{\mathop{\text{mclip}}}\mclip$的数值计算,核心思路来自 @leloykun 的文章《Numerically Stable Spectral Clipping Via Newton-Schulz Iteration》(现已重新修订和改名),通过寻找基于$\newcommand{msign}{\mathop{\text{msign}}}\msign$的表达式来避免另外寻找Newton-Schulz迭代,在文章中笔者提出了一个计算量更低的嵌套$\msign$方案。
不过前两天,@leloykun 在推特上指出笔者的方案实际计算中存在误差偏大的问题。本文来具体分析一下这个问题,并给出一个更高效、误差更低的新方案。
通过msign来计算奇异值裁剪mclip(上)
By 苏剑林 | 2025-06-07 | 10927位读者 | 引用前面我们用了两篇文章《msign算子的Newton-Schulz迭代(上)》和《msign算子的Newton-Schulz迭代(下)》讨论了矩阵的$\newcommand{msign}{\mathop{\text{msign}}}\newcommand{sign}{\mathop{\text{sign}}}\newcommand{clip}{\mathop{\text{clip}}}\newcommand{mclip}{\mathop{\text{mclip}}}\msign$算子的数值计算,这篇文章我们来关注“奇异值裁剪(Singular Value Clipping)”运算,它最近在 @_arohan_ 的推特上引起了热议,我们此前在《高阶muP:更简明但更高明的谱条件缩放》也提到过,接下来我们简称为$\mclip$。
基本概念
对于标量$x$,$\clip$运算定义为
\begin{equation}\clip(x) = \max(\min(x, 1), -1) = \left\{\begin{aligned}1, &\quad x\geq 1 \\
x, &\quad x\in(-1, 1)\\
-1, &\quad x\leq -1
\end{aligned}\right.\end{equation}
msign算子的Newton-Schulz迭代(下)
By 苏剑林 | 2025-06-05 | 13278位读者 | 引用在上文《msign算子的Newton-Schulz迭代(上)》中,我们试图为$\mathop{\text{msign}}$算子寻找更好的Newton-Schulz迭代,以期在有限迭代步数内能达到尽可能高的近似程度,这一过程又可以转化为标量函数$\mathop{\text{sign}}(x)$寻找同样形式的多项式迭代。当时,我们的求解思路是用Adam优化器端到端地求一个局部最优解,虽然有效但稍显粗暴。
而在几天前,arXiv新出了一篇论文《The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm》,作者运用了一系列精妙的数学结论,以优雅且硬核的方式给出了更漂亮的答案。本文让我们一起欣赏和学习一番这篇精彩的论文。
问题描述
相关背景和转化过程我们就不再重复了,直接给出我们要求解的问题是
\begin{equation}\mathop{\text{argmin}}_f d(f(x),1)\end{equation}
等值振荡定理:最优多项式逼近的充要条件
By 苏剑林 | 2025-06-02 | 11623位读者 | 引用最近在阅读时,遇到了一个关于最优多项式逼近的“等值振荡定理(Equioscillation Theorem)”,证明过程还涉及到无穷范数求导,感觉结论和证明都颇为新奇,特来记录一番。
参考资料:《Notes on how to prove Chebyshev’s equioscillation theorem》和《Approximation Theory – Lecture 5》。
等值振荡
我们先展示一下结论:
等值振荡定理 设$f(x)$是不超过$n$阶的多项式,$g(x)$是区间$[a,b]$上的连续函数,那么
\begin{equation}f^* = \mathop{\text{argmin}}_f \max_{x\in[a,b]} |f(x) - g(x)|\end{equation}
的充要条件是存在$a\leq x_0 < x_1 < \cdots < x_{n+1} \leq b$以及$\sigma\in\{0,1\}$,使得
\begin{equation}f^*(x_k) - g(x_k) = (-1)^{k+\sigma} \max_{x\in[a,b]} |f^*(x) - g(x)|\end{equation}
msign算子的Newton-Schulz迭代(上)
By 苏剑林 | 2025-05-11 | 19507位读者 | 引用在之前的《Muon优化器赏析:从向量到矩阵的本质跨越》、《Muon续集:为什么我们选择尝试Muon?》等文章中,我们介绍了一个极具潜力、有望替代Adam的新兴优化器——“Muon”。随着相关研究的不断深入,Muon优化器受到的关注度也在日益增加。
了解过Muon的读者都知道,Muon的核心运算是$\newcommand{msign}{\mathop{\text{msign}}}\msign$算子,为其寻找更高效的计算方法是学术社区的一个持续目标。本文将总结一下它的最新进展。
写在前面
$\msign$的定义跟SVD密切相关。假设矩阵$\boldsymbol{M}\in\mathbb{R}^{n\times m}$,那么
\begin{equation}\boldsymbol{U},\boldsymbol{\Sigma},\boldsymbol{V}^{\top} = \text{SVD}(\boldsymbol{M}) \quad\Rightarrow\quad \msign(\boldsymbol{M}) = \boldsymbol{U}_{[:,:r]}\boldsymbol{V}_{[:,:r]}^{\top}\end{equation}
其中$\boldsymbol{U}\in\mathbb{R}^{n\times n},\boldsymbol{\Sigma}\in\mathbb{R}^{n\times m},\boldsymbol{V}\in\mathbb{R}^{m\times m}$,$r$是$\boldsymbol{M}$的秩。简单来说,$\msign$就是把矩阵的所有非零奇异值都变成1后所得的新矩阵。
低秩近似之路(五):CUR
By 苏剑林 | 2025-01-12 | 21827位读者 | 引用再次回到低秩近似之路上。在《低秩近似之路(四):ID》中,我们介绍了“插值分解(Interpolative Decomposition,ID)”,这是为矩阵$\boldsymbol{M}\in\mathbb{R}^{n\times m}$寻找$\boldsymbol{C}\boldsymbol{Z}$形式的近似的过程,其中$\boldsymbol{C}\in\mathbb{R}^{n\times r}$是矩阵$\boldsymbol{M}$的若干列,而$\boldsymbol{Z}\in\mathbb{R}^{r\times m}$是任意矩阵。
这篇文章我们将介绍CUR分解,它跟插值分解的思想一脉相承,都是以原始矩阵的行、列为“骨架”来构建原始矩阵的近似,跟ID只用行或列之一不同,CUR分解同时用到了行和列。
基本定义
其实这不是本站第一次出现CUR分解了。早在《Nyströmformer:基于矩阵分解的线性化Attention方案》我们就介绍过矩阵的Nyström近似,它实际上就是CUR分解,后来在《利用CUR分解加速交互式相似度模型的检索》还介绍了CUR分解在降低交互式相似度模型的检索复杂度的应用。
低秩近似之路(四):ID
By 苏剑林 | 2024-10-30 | 27320位读者 | 引用这篇文章的主角是ID(Interpolative Decomposition),中文可以称之为“插值分解”,它同样可以理解为是一种具有特定结构的低秩分解,其中的一侧是该矩阵的若干列(当然如果你偏好于行,那么选择行也没什么问题),换句话说,ID试图从一个矩阵中找出若干关键列作为“骨架”(通常也称作“草图”)来逼近原始矩阵。
可能很多读者都未曾听说过ID,即便维基百科也只有几句语焉不详的介绍(链接),但事实上,ID跟SVD一样早已内置在SciPy之中(参考scipy.linalg.interpolative),这侧面印证了ID的实用价值。
基本定义
前三篇文章我们分别介绍了伪逆、SVD、CR近似,它们都可以视为寻找特定结构的低秩近似:
\begin{equation}\mathop{\text{argmin}}_{\text{rank}(\tilde{\boldsymbol{M}})\leq r}\Vert \tilde{\boldsymbol{M}} - \boldsymbol{M}\Vert_F^2\end{equation}
低秩近似之路(三):CR
By 苏剑林 | 2024-10-11 | 28998位读者 | 引用在《低秩近似之路(二):SVD》中,我们证明了SVD可以给出任意矩阵的最优低秩近似。那里的最优近似是无约束的,也就是说SVD给出的结果只管误差上的最小,不在乎矩阵的具体结构,而在很多应用场景中,出于可解释性或者非线性处理等需求,我们往往希望得到具有某些特殊结构的近似分解。
因此,从这篇文章开始,我们将探究一些具有特定结构的低秩近似,而本文将聚焦于其中的CR近似(Column-Row Approximation),它提供了加速矩阵乘法运算的一种简单方案。
问题背景
矩阵的最优$r$秩近似的一般提法是
\begin{equation}\mathop{\text{argmin}}_{\text{rank}(\tilde{\boldsymbol{M}})\leq r}\Vert \tilde{\boldsymbol{M}} - \boldsymbol{M}\Vert_F^2\label{eq:loss-m2}\end{equation}
最近评论