💻 computer science

Riemannian Optimization for Hadamard Products of Low-Rank Matrices

本文提出了一种黎曼优化框架，该框架通过一种新颖的块对角度量和一个无需调参的高斯-牛顿算法，通过解决哈达玛积固有的缩放对称性，来高效地学习低秩矩阵。

原作者： Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

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

大局观：双人舞

想象一下，你正试图仅用两幅简单的、低分辨率的草图来重现一幅复杂的画作（一个大型数据矩阵）。

草图 A 捕捉了宏观的、整体的轮廓。
草图 B 捕捉了细腻的、细节的纹理。

论文指出，重现这幅画作的最佳方式不仅仅是将这些草图堆叠在一起，而是要将它们逐像素相乘（这被称为“Hadamard 积”）。这使得模型非常高效，使用的“笔触”（参数）比标准方法所需的方法更少。

然而，这里有一个陷阱。因为你在将两幅草图相乘，所以存在许多种调整草图 A 的亮度与草图 B 的对比度的方法，而这些方法最终都会得到完全相同的画作。这就像是在说：“我可以调亮灯光来让画作变得更亮，”或者“我可以调暗灯光来让画作变得更亮。”存在无数种这些调整的组合，最终都会导致相同的结果。

这为试图学习该模型的计算机创造了一个混乱的景观。标准的计算机方法会在这些“等效解的无限循环”中迷失方向，浪费时间和精力。

问题所在：迷失在迷雾中

作者指出，现有的方法（如交替梯度下降或块坐标下降）在处理这类特定问题时表现挣扎：

标准方法将问题视为在平坦、笔直的道路上行走。但实际的景观是弯曲且崎岖不平的。由于它们不理解地形的形状，它们的步伐要么太小，要么方向错误。
专门化方法如果目标仅仅是最小化简单的误差（如“平方误差”），效果非常好，但如果想要使用更复杂的目标（如预测用户评分或处理杂乱的数据），它们就会彻底失效。它们就像是一辆只能在赛车场上行驶、但在土路上会熄火的汽车。

解决方案：一张智能地图（黎曼优化）

作者提出了一种利用**黎曼优化（Riemannian Optimization）**来导航这一问题的新方法。

不要把问题空间看作一张平坦的纸，而要将其看作一个弯曲、折叠的表面（流形）。

“折叠”的本质： 由于前文提到的“无限循环”（对称性），许多不同的点实际上代表着同一幅画。
商流形（Quotient Manifold）： 作者创建了一个“商流形”。想象一下，将那个折叠的表面上所有代表同一幅画的点粘合在一起。现在，你拥有了一张干净、简化的地图，其中每个点都是唯一的。你不再会在“无限循环”中迷失，因为这些循环已经被缝合封闭了。

秘密武器：一个定制的指南针（度量）

为了在这样一个弯曲的表面上高效行走，你需要一个特殊的指南针。在数学中，这被称为黎曼度量（Riemannian Metric）。

作者发明了一个全新的、定制的指南针。

旧指南针： 标准方法使用通用的指南针，它假设地面是平坦的。它会被曲线所迷惑。
新指南针： 作者的指南针是“块对角（block-diagonal）”的。想象一个拥有为每一行和每一列草图设置的独立传感器的指南针。它准确地知道草图的一个部分的“纹理”如何影响另一个部分的“形状”。
神奇之处： 这个指南针具有尺度不变性（scale-invariant）。如果你决定将草图 A 的亮度增加两倍，同时将草图 B 的亮度减半，指南针并不会在意。它知道你并没有改变画作，因此不会感到困惑。它忽略了任意缩放带来的“噪声”，只专注于数据的实际形状。

算法：无需调优的徒步者

利用这张新地图和这个新指南针，作者构建了一个名为 RGD（黎曼梯度下降） 的徒步算法。

无需旋转旋钮： 大多数徒步算法都需要你手动调节一个“步长”旋钮（调优超参数）。如果你转得太多，会走过头；转得太少，则移动太慢。这个新算法使用一种“高斯-牛顿（Gauss-Newton）”技巧自动计算完美的步长。它就像一个能根据山坡坡度本能地知道每一步该走多远的徒步者，不需要任何人工调整。
速度： 它极其快速。它的扩展性与数据量呈线性关系，这意味着如果画作的大小增加一倍，绘制它也仅需两倍的时间，而不是四倍或十倍。

结果：赢得比赛

作者在真实世界的数据（如 MovieLens 的电影评分和网络图谱）上，将这位徒步者与旧方法进行了对比测试。

准确性： 在 MovieLens 数据集（预测电影评分）上，他们的方法在所有测试配置中都实现了最低的误差率（最佳准确度）。它找到了比那些仅限“赛车场”的专门化方法更好的解。
鲁棒性： 当他们人为地破坏初始条件（使一幅草图非常亮，另一幅非常暗）时，他们的方法忽略了这些混乱，并且每次都能找到正确答案。旧方法则会感到困惑并表现得更差。
通用性： 与那些仅适用于简单数学问题的专门化方法不同，这种新方法适用于任何光滑的目标，使其成为处理此类数据的通用工具。

总结

本文介绍了一种更聪明的方法，教计算机如何从具有“乘法”结构的数据中学习。通过意识到问题存在于一个弯曲、折叠的表面上，并构建了一个能够忽略无关缩放技巧的定制指南针，他们创建了一种比以往方法更快、更准确、且不需要更多人工调优的算法。这就像是从一个蒙着眼睛的步行者升级到了一个拥有完美、自动调节 GPS 的徒步者。

技术摘要：针对哈达玛积低秩矩阵的黎曼优化

问题定义
本文研究了利用两个低秩矩阵的逐元素（哈达玛）积来对具有乘性结构的数据进行建模的挑战。目标矩阵 $W \in \mathbb{R}^{m \times n}$ 被建模为：
$W = (GH^\top) \circ (UV^\top)$
其中 $G, U \in \mathbb{R}^{m \times r_1, r_2}$ 且 $H, V \in \mathbb{R}^{n \times r_1, r_2}$ 。虽然与标准的秩为 $r_1r_2$ 的分解相比，这种形式提供了更高的参数效率（需要 $(m+n)(r_1+r_2)$ 个参数，而非 $(m+n)r_1r_2$ 个），但它引入了复杂的优化景观。具体而言，该模型表现出了超越标准广义线性（GL）重参数化不变性的对称性。乘积 $W$ 在两个因子对 $(G, H)$ 和 $(U, V)$ 之间的耦合行与列缩放下保持不变。这些额外的自由度创造了一种具有挑战性的几何结构，使得标准的欧几里得梯度下降法难以高效地进行导航。

现有求解器面临局限性：交替梯度下降（AGD）忽略了特定的几何结构和缩放对称性；而块坐标下降（BCD）虽然在最小二乘损失函数上非常有效，但对于非二次损失（例如逻辑回归链路预测或交叉熵）缺乏闭式解，这限制了其在鲁棒统计学及其他领域的适用性。

方法论
作者提出将学习问题表述为在**黎曼商流形（Riemannian quotient manifold）**上的优化任务。这种方法显式地考虑了哈达玛积的自然不变性。

流形几何： 作者通过对全对称群 $\mathcal{G}$ 进行因子化，定义了商流形 $\mathcal{M}$ 。该群包括：
- 每个因子对的标准 GL 重参数化不变性。
- 新型的跨哈达玛缩放对称性（cross-Hadamard scaling symmetries），即可逆对角矩阵在两个因子对之间进行反向的行与列缩放。
  该流形是由全列秩矩阵对该群作用取模构成的空间。
新型黎曼度量： 一个关键贡献是推导出了一个由 Frobenius 内积的拉回（pullback）得到的分块对角黎曼度量（ $g_x$ ）。
- 完整的拉回度量会耦合所有四个因子块，导致计算昂贵的稠密线性系统。
- 所提议的度量仅保留拉回度的对角块，舍弃了交叉项。
- 该度量通过用于各因子行/列的权重矩阵（ $S$ -块）来定义。例如， $G$ 的第 $i$ 行的权重为 $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$ ，其中 $Y = UV^\top$ 。
- 不变性： 证明了该度量在 GL 重参数化和跨哈达玛缩放对称性下都是不变的。这确保了优化器对因子之间任意幅度的拆分是不敏感的。
- 与 BCD 的联系： 所提议度量中的权重矩阵与 BCD 更新中使用的正规方程矩阵完全对应。因此，黎曼梯度可以被解释为在所有行上同时对任意光滑损失函数执行“软” BCD 步骤。
优化算法 (RGD)： 作者开发了一种黎曼梯度下降（RGD）算法：
- 梯度计算： 通过使用 $S$ -块求解独立的 $r \times r$ 线性系统（每个行/列一个）来计算黎曼梯度。
- 步长： 推导出了一个无需调参的高斯-牛顿柯西步长（Gauss–Newton Cauchy step size）。该步长在对称群下是不变的，且不需要超参数调优。
- 收缩（Retraction）： 使用加法收缩将更新映射回流形。
- 复杂度： 每次迭代的成本随观测条目数 $N$ 线性缩放（$O(Nr) $），并随秩呈多项式缩放（$ O((m+n)r^4)$），使其在大规模数据集上保持高效。

核心贡献

几何特征化： 对哈达玛积的商流形结构进行了形式化描述，识别了 GL 和跨哈达达玛缩放对称性。
尺度不变度量： 提出了一个尊重完整对称群并能将优化解耦为独立行/列子问题的全新分块对角黎曼度量。
算法开发： 推导出了一个支持任何光滑损失函数的 RGD 算法，并配备了无需调参的高斯-牛顿步长，这与仅限于最小二乘法的 BCD 不同。
实验验证： 证明了该方法在最小二乘任务上能达到与 BCD 相当的性能，并在非二次目标函数上优于 BCD，且在特定的哈达玛秩配置下取得了更优结果。

实验结果
作者在合成和真实世界数据集上评估了 RGD：

合成压力测试： 在 $2,000 \times 1,000$ $2, 000 \times 1, 000$ 的合成目标矩阵上，RGD 展示了：
- 尺度不变性： 在不同对角尺度分离度（ $\kappa_{scale}$ ）下，恢复误差保持恒定，经验性地验证了度量的不变性属性。相比之下，AGD 对缩放表现出敏感性。
- 条件数： RGD 在不同因子条件数下的表现与 BCD 相当，显著优于 AGD。
- 噪声鲁棒性： RGD 以与 BCD 相同的速率收敛至噪声水平，而 AGD 则相对滞后。
真实世界数据集：
- 全矩阵逼近： 在 Camera、Football 和 Les Misérables 数据集上，RGD 在相对误差上紧随 BCD，证实了该度量在二次损失下提供了等效于 BCD 的预处理。
- MovieLens-1M： 在矩阵补全任务中（固定参数预算 $r_1+r_2=6$ ），RGD 在所有测试的哈达玛秩配置中实现了最低的留出集 RMSE。值得注意的是，平衡配置 $(3,3)$ 的表现优于近乎传统的 $(1,5)$ 配置，这表明哈达玛交互能力（ $r_1r_2$ ）有助于提升准确性。RGD 在真正的哈达玛配置下始终优于 AGD，并且比 BCD 实现了更低的 RMSE。

意义与主张
本文声称弥合了 BCD 在最小二乘问题上的高效性与基于梯度的方法在一般光滑损失函数上的灵活性之间的鸿沟。通过将问题提升到黎曼商流形上，作者提供了一个能够处理哈达玛积复杂对称性的原则性框架。所提议的 RGD 算法提供了一种无需调参、尺度不变且计算复杂度随数据规模线性增长的方法。作者断言，该框架可以自然地扩展到 $k$ 个低秩矩阵的乘积，并且与其他黎曼求解器（如共轭梯度法、置信区域法）兼容，为现有的乘性低秩建模求解器提供了一个强有力的替代方案。