多指标模型下经验风险最小化中的副本对称破缺与算法阈值

# 多指标模型下经验风险最小化中的副本对称性破缺与算法阈值  
来源：https://arxiv.org/html/2606.28573  
Andrea Montanari and Kangjie Zhou  
斯坦福大学数学系与统计系，哥伦比亚大学统计系  

###### 摘要  

现代机器学习模型通过优化高维非凸经验风险函数进行训练。这类代价函数可能包含大量局部最优点，然而基于梯度的优化似乎仍能收敛到接近全局最优。在简单的监督学习框架下，我们精确描绘了经验风险景观中哪些部分对于多项式时间算法是可达的。给定独立同分布的数据对 \(\{(\mathbf{x}_i, y_i): 1 \leq i \leq n\}\)，其中 \(\mathbf{x}_i \in \mathbb{R}^d\) 为标准高斯特征向量，\(y_i \in \mathbb{R}\) 为响应变量，其依赖关系取决于 \(\mathbf{x}_i\) 在未知的 \(k\) 维子空间上的投影。我们采用经验风险最小化来学习一个依赖于数据 \(m\) 维投影的模型（例如，一个具有 \(m\) 个神经元的神经网络）。我们提出一种增量近似消息传递（IAMP）算法，并精确刻画其在渐近状态 \(n, d \to \infty\)，\(n/d \to \alpha \in (0, +\infty)\) 下的训练误差，以及测试误差与训练误差之间的关系。基于相关模型的早期工作，我们预期该算法所达到的性能在多项式时间算法中是最优的。

###### 目录  

1. [引言](#S1)  
   1.1 [技术设定：多指标模型与经验风险最小化](#S1.SS1)  
   1.2 [与投影追踪的联系](#S1.SS2)  
   1.3 [一般方法](#S1.SS3)  
   1.4 [主要结果总结及论文组织](#S1.SS4)  
   1.5 [定义与符号](#S1.SS5)  
2. [来自统计物理的猜想](#S2)  
3. [主要结果（I）：算法可达性](#S3)  
   3.1 [算法概述](#S3.SS1)  
   3.2 [AMP的可达性结果](#S3.SS2)  
   3.3 [对偶值 \(\mathcal{V}_{m,\alpha,\varphi}^{\mathrm{alg}}(h)\) 与随机最优控制](#S3.SS3)  
4. [\(m=k=1\) 时的副本对称情形](#S4)  
5. [插曲：大 \(n/d\) 与张量 PCA 等价性](#S5)  
   5.1 [单指标模型](#S5.SS1)  
   5.2 [全局最大值的副本预测](#S5.SS2)  
   5.3 [通过AMP的可达性](#S5.SS3)  
   5.4 [等价高斯模型](#S5.SS4)  
   5.5 [示例](#S5.SS5)  
6. [主要结果（II）：Parisi 变分原理](#S6)  
7. [两阶段AMP算法：定理3.1的证明](#S7)  
   7.1 [近似消息传递](#S7.SS1)  
   7.2 [第一阶段：不动点AMP](#S7.SS2)  
   7.3 [第二阶段：增量AMP](#S7.SS3)  
   7.4 [两阶段的结合](#S7.SS4)  
8. [对偶刻画与Parisi公式：定理6.1的证明](#S8)  
   8.1 [技术预备知识](#S8.SS1)  
   8.2 [6.1的证明](#S8.SS2)  
9. [参考文献](#bib)  
10. [附录A：副本计算](#A1)  
11. [附录B：第三节的附录](#A2)  
    B.1 [约化为随机信号](#A2.SS1)  
    B.2 [\(m=k=1\) 情形的AMP可达性结果](#A2.SS2)  
    B.3 [辅助引理](#A2.SS3)  
12. [附录C：第四节的附录](#A3)  
    C.1 [4.1和4.3的证明](#A3.SS1)  
    C.2 [经验风险最小化与贝叶斯AMP的估计误差](#A3.SS2)  
    C.3 [副本对称条件](#A3.SS3)  
13. [附录D：第五节的附录](#A4)  
    D.1 [5.1的推导](#A4.SS1)  
    D.2 [5.1、5.2和5.3的证明](#A4.SS2)  
    D.3 [5.4节的附录](#A4.SS3)  
        D.3.1 [Parisi公式](#A4.SS3.SSS1)  
        D.3.2 [两阶段算法达到的 \(\widehat{H}_d^g\) 值](#A4.SS3.SSS2)  
    D.4 [5.4、D.1和D.2的证明](#A4.SS4)  
    D.5 [D.3的证明](#A4.SS5)  
    D.6 [辅助引理](#A4.SS6)  
14. [附录E：第七节的附录](#A5)  
    E.1 [7.3和7.4的证明](#A5.SS1)  
    E.2 [命题7.5的证明](#A5.SS2)  
    E.3 [定理7.1的证明](#A5.SS3)  
    E.4 [辅助引理](#A5.SS4)  
15. [附录F：第八节的附录](#A6)  
    F.1 [8.3的证明](#A6.SS1)  
    F.2 [辅助引理](#A6.SS2)  

## 1 引言  

经验风险最小化（ERM）是设计学习算法的主要指导原则。然而，在模型复杂度111模型复杂度由参数数量或Rademacher复杂度[SSBD14](https://arxiv.org/html/2606.28573#bib.bibx37)刻画。与样本量成比例增长的情况下，其理论性质尚未得到充分理解，而这一尺度正是当前人工智能趋势[KMH+20](https://arxiv.org/html/2606.28573#bib.bibx25)，[HBM+22](https://arxiv.org/html/2606.28573#bib.bibx20)所青睐的。在凸经验风险函数（即具有凸损失的线性模型）情形下，丰富的理论使我们能够在简单数据分布下推导出精确的渐近结果[BM11b](https://arxiv.org/html/2606.28573#bib.bibx7)，[TOH15](https://arxiv.org/html/2606.28573#bib.bibx40)，[EK18](https://arxiv.org/html/2606.28573#bib.bibx15)，[DM16](https://arxiv.org/html/2606.28573#bib.bibx13)。近期工作发展了处理非凸性的方法，适用于经验风险在全局最小化邻域内局部凸，且仅有一个或少量接近全局最小值的情形[AMS26](https://arxiv.org/html/2606.28573#bib.bibx4)，[VDR+25](https://arxiv.org/html/2606.28573#bib.bibx41)，[MS26](https://arxiv.org/html/2606.28573#bib.bibx32)。然而，机器学习中感兴趣的经验风险景观通常在定性上有所不同，存在许多相互分离的局部最小值。这类问题的一个例子出现在张量 PCA 中，即试图从被高斯噪声破坏的观测中估计一个高维秩一张量[MR14](https://arxiv.org/html/2606.28573#bib.bibx30)。在这种情况下，负对数似然函数是以参数向量 \(\mathbf{w} \in \mathbb{S}^{d-1}\) 为索引的高斯过程 \(\widehat{L}_n(\mathbf{w})\)，且可能出现指数级数量的局部最小值[AMMN19](https://arxiv.org/html/2606.28573#bib.bibx2)。这种代价函数也是平均场自旋玻璃理论[AMS23](https://arxiv.org/html/2606.28573#bib.bibx3)的核心。

由于在最坏情况下，具有众多局部最小值的经验风险函数的全局优化对于多项式时间算法而言是不可行的，我们转而解决以下核心问题：

- **Q**：给定数据分布，对于多项式时间算法，哪些训练误差和测试误差值以高概率是可达的？

为具体起见，考虑一个简单设定，其中观测到的独立同分布数据 \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\) 遵循高斯单指标模型：

\[
y_i = \sqrt{\lambda}\,\varphi(\mathbf{w}_*^{\mathsf{T}}\mathbf{x}_i) + \varepsilon_i, \quad \mathbf{x}_i \sim \mathsf{N}(\mathbf{0},\boldsymbol{I}_d), \quad \varepsilon_i \sim \mathsf{N}(0,1),
\tag{1}
\]

其中 \(\varphi\) 是链接函数，\(\mathbf{w}_* \in \mathbb{S}^{d-1}\) 是真实信号，\(\lambda > 0\) 代表信噪比。我们关注比例缩放尺度，其中 \(n, d \to \infty\) 且 \(n/d \to \alpha \in (0, \infty)\)。虽然我们的主要结果考虑更一般的模型，但上述设定已足够说明关键点。

为了学习真实信号 \(\mathbf{w}_*\)，我们提出在单位球面 \(\mathbb{S}^{d-1}\) 上求解以下相关性最大化问题：

\[
\text{最大化} \quad \widehat{H}_n(\mathbf{w}) := \frac{1}{n\sqrt{\lambda}} \sum_{i=1}^n y_i \sigma(\mathbf{w}^{\mathsf{T}}\mathbf{x}_i), \quad \text{约束} \quad \mathbf{w} \in \mathbb{S}^{d-1},
\tag{2}
\]

其中 \(\sigma\) 是给定的激活函数。同样，我们的主要结果更为一般，此处仅以相关性损失为例进行说明。另一方面，我们不假设 \(\sigma = \varphi\)，因为一般而言数据生成过程是未知的。

我们特别感兴趣的是刻画高效迭代算法（如基于梯度的方法和近似消息传递（AMP））所能达到的训练误差和测试误差。

我们注意到，模型 (1) 的许多特例以及类似于 (2) 的经验风险最小化方法已在文献中得到广泛研究。例如，参见 [CC17](https://arxiv.org/html/2606.28573#bib.bibx8)，[MM18](https://arxiv.org/html/2606.28573#bib.bibx27)，[AMK+18](https://arxiv.org/html/2606.28573#bib.bibx1)，[BKM+19](https://arxiv.org/html/2606.28573#bib.bibx5)。

令 \(\alpha = \lim_{n,d\to\infty} n/d\) 为极限纵横比。现有文献 [VDR+25](https://arxiv.org/html/2606.28573#bib.bibx41)，[MS26](https://arxiv.org/html/2606.28573#bib.bibx32)，[MBB26](https://arxiv.org/html/2606.28573#bib.bibx26) 的结果表明 \(\widehat{H}_n(\mathbf{w})\) 的景观存在以下定性图像：

1. 对于 \(\alpha > \alpha_{\mathrm{tr}}(\lambda, \varphi, \sigma)\)，经验相关性 \(\widehat{H}_n(\mathbf{w})\) 存在唯一的全局最大化器 \(\widehat{\boldsymbol{w}} \in \mathbb{S}^{d-1}\)。此外，\(\widehat{\boldsymbol{w}}\) 与真实信号 \(\mathbf{w}_*\) 正相关，且 \(\widehat{H}_n(\mathbf{w})\) 在 \(\widehat{\boldsymbol{w}}\) 的邻域内是强凹的。该局部最大值可以通过合适的多项式时间算法（仅利用 \(\widehat{H}_n\) 的梯度或 Hessian 信息，如 AMP）达到。

2. 对于 \(\alpha < \alpha_{\mathrm{tr}}(\lambda, \varphi, \sigma)\)，要么所有接近全局最大化器几乎与 \(\mathbf{w}_*\) 正交，要么存在一个全局最大化器与 \(\mathbf{w}_*\) 正相关，但无法被多项式时间算法找到，或者其邻域不是强凹的。也可能出现 \(\alpha_{\mathrm{tr}} = 0\) 或 \(\alpha_{\mathrm{tr}} = \infty\) 的情况。

我们将 \(\alpha_{\mathrm{tr}}\) 处的相变称为“平凡化”相变。在统计物理术语中，当景观呈现多个分离的近似最优点，且其值大致独立随机（如 \(\alpha < \alpha_{\mathrm{tr}}\) 的情形）时，称为“副本对称性破缺”。现有结果成功地刻画了贝叶斯最优估计误差，或者分析了 \(\alpha > \overline{\alpha}_{\mathrm{tr}}\) 时的经验风险最小化（其中 \(\overline{\alpha}_{\mathrm{tr}}\) 是平凡化阈值 \(\alpha_{\mathrm{tr}}\) 的上界）[BKM+19](https://arxiv.org/html/2606.28573#bib.bibx5)，[VDR+25](https://arxiv.org/html/2606.28573#bib.bibx41)，[AMS26](https://arxiv.org/html/2606.28573#bib.bibx4)，[MS26](https://arxiv.org/html/2606.28573#bib.bibx32)。然而，这些工作在最具挑战性的 \(\alpha < \alpha_{\mathrm{tr}}\) 区间内未能完全回答问题Q。

参见图注

**图1：** 左图：贝叶斯AMP、经验风险最小化（我们的两阶段算法达到的值）和投影梯度下降（PGD）与 \(\mathbf{w}_*\) 的极限重叠。右图：这三种方法的极限训练误差（归一化经验相关性）和测试误差（归一化总体相关性）。这些值是在 \(\alpha \to \infty\) 且 \(\lambda \to 0\) 使得 \(\alpha\lambda \to \overline{\alpha}\) 的极限下计算的。请参阅第5节以了解实验设置和实现细节的全面描述。

为说明问题Q的内容，图1报告了数值模拟的结果。我们考虑经验风险最小化问题 (2)，数据使用 \(\varphi(x) = \operatorname{ReLU}(x) = \max(x, 0)\) 生成，并使用错误指定的激活函数 \(\sigma(x) = x + \sqrt{2}x^2\) 进行学习。我们评估了三种算法的性能：(i) 贝叶斯AMP；(ii) 通过我们的两阶段算法计算的经验风险最小化方法（我们预期其在多项式时间算法中是最优的，详见第3节）；(iii) 在单位球面上最小化 \(-\widehat{H}_n\)（即最大化 \(\widehat{H}_n\)）的投影梯度下降（PGD）。对于 (i)，我们使用来自 [BKM+19](https://arxiv.org/html/2606.28573#bib.bibx5) 的理论预测；对于 (ii)，我们绘制了本工作的预测结果。最后，对于 (iii)，我们绘制了数值实验的结果。我们绘制了适当归一化的训练误差和测试误差（详见第5.5节），以及三种方法达到的与真实信号 \(\mathbf{w}_*\) 的相关性。我们观察到，PGD 的数值模拟与最优两阶段算法的理论预测紧密匹配。换句话说，我们的理论似乎捕捉到了适当调参的梯度下降的行为。另一方面，基于经验风险最小化（无论是 PGD 还是我们的两阶段算法）的测试误差与贝叶斯最优 AMP 的测试误差之间存在显著差距。

### 1.1 技术设定：多指标模型与经验风险最小化  

在本文的其余部分，我们旨在通过描述一大类迭代算法在以下高斯多指标模型下的计算可行的训练误差和测试误差，来回答问题Q。