Non-convergence to Global Minimizers for Adam and Stochastic Gradient Descent Optimization and Constructions of Local Minimizers in the Training of Artificial Neural Networks¶
作者: Arnulf Jentzen, Adrian Riekert
来源: SIAM/ASA Journal on Uncertainty Quantification
主题: 统计计算 / 算法
相关性: 3/10
机构绿灯: Chinese University of Hong Kong(US News 前 50,免分进入精读)
链接: https://doi.org/10.1137/24m1639464
一、领域脉络与小综述¶
这个方向是什么¶
本文所处的子方向是人工神经网络(ANN)训练的优化理论,其根本的统计/科学问题是:为什么随机梯度下降(SGD)类方法在训练神经网络时在实践中如此有效,尽管神经网络的损失景观(loss landscape)高度非凸、存在大量局部极小值?这个问题的核心张力在于:理论上无法排除 SGD 收敛到糟糕的局部极小值,但实践中 SGD 总能找到风险值接近全局最优的解。本文试图从严格数学证明的角度,正面回答"SGD 是否以高概率收敛到全局极小值"这一长期开放问题。
这个方向的成熟度:理论结果严重滞后于实践。尽管 SGD/Adam 是深度学习的事实标准优化器,但对其收敛行为的严格理论刻画在大多数实际相关场景下仍是空白。本文属于该方向中"构造性反例"这一支——通过精心构造数据分布和网络结构,证明 SGD 类方法不会收敛到全局极小值。
发展脉络(history)¶
从 introduction 和参考文献看,这条线的发展大致如下:
-
奠基工作:神经网络优化的理论分析始于对损失景观几何的刻画。早期工作(如 Choromanska et al., 2015,引用自 intro 中关于 loss landscape 的讨论)通过随机矩阵理论(spin glass 模型)猜想:ANN 损失景观中局部极小值的风险值大致分布在某个区间内,且高质量局部极小值占主导。这一猜想为"SGD 能找到好解"提供了直觉支撑,但缺乏严格证明。留下的口子:这只是启发式论证,不涉及具体优化器的轨迹行为。
-
主要进展(优化器收敛性分析):另一条线是分析 SGD 及其变体(momentum、AdaGrad、RMSprop、Adam)在非凸优化中的收敛性。经典结果(如 Ghadimi & Lan, 2013,引用自 intro 关于 SGD 收敛性的讨论)证明 SGD 在非凸光滑目标上以 \(O(1/\sqrt{T})\) 的速率收敛到驻点(stationary point),而非全局极小值。留下的口子:这些结果只保证收敛到梯度为零的点,无法区分"好的"与"坏的"驻点,更无法回答"是否收敛到全局极小值"。
-
当前 frontier(构造性反例):近年来,若干工作开始构造具体例子证明 SGD 会错过全局极小值。例如,Jentzen 等人的系列工作(本文作者自己的前期研究,如 Jentzen & Riekert 的前序论文)在浅层 ReLU 网络的简化设定下,构造了 SGD 以正概率收敛到非全局极小值的例子。本文的位置:将这一结果大幅推广——不仅覆盖 vanilla SGD,还覆盖 momentum SGD、AdaGrad、RMSprop 和 Adam;不仅证明"可能错过",还证明"以高概率错过";同时揭示局部极小值的层级结构(不同风险值的局部极小值并存)。
子线索聚类¶
被引文献大致落在三条子线索上:
-
损失景观的几何刻画(loss landscape geometry):研究 ANN 损失函数中局部极小值的分布、风险值范围、以及它们与全局极小值的关系。代表工作:Choromanska et al. (2015) 的 spin glass 模型、以及后续关于"局部极小值风险值集中"的若干工作。这一簇在回答:坏局部极小值是否存在、有多坏。
-
优化器的收敛性保证(optimizer convergence guarantees):分析 SGD 及其变体在非凸优化中的收敛速率和收敛目标。代表工作:Ghadimi & Lan (2013) 的 \(O(1/\sqrt{T})\) 驻点收敛、Reddi et al. (2018) 关于 Adam 收敛性的修正。这一簇在回答:优化器到底收敛到什么。
-
构造性反例与不可能性结果(constructive counterexamples):通过具体构造证明优化器会错过全局极小值。代表工作:本文作者的前序工作、以及 Livni et al. (2014) 关于"存在 SGD 无法高效优化的网络"的结果。这一簇在回答:SGD 在什么情况下必然失败。
这个方向在追问的核心问题¶
- SGD 类方法是否以高概率收敛到全局极小值? —— 本文给出否定回答(在构造的设定下)。
- 如果 SGD 不收敛到全局极小值,那它收敛到的局部极小值的风险值有多接近全局最优? —— 本文揭示层级结构:存在风险值任意接近全局最优的局部极小值。
- 这些结论在多大程度上依赖网络结构、激活函数、数据分布的具体选择? —— 本文的构造依赖浅层网络 + ReLU 激活 + 特定数据分布,推广到深层网络和一般数据分布仍是开放问题。
⚠️ 作者的 framing(必须明确标注成"这是作者的说法")¶
这是作者的说法:作者将缺口 frame 成"SGD 类方法在 ANN 训练中是否以高概率收敛到全局极小值"这一具体问题,并声称本文首次在浅层 ReLU 网络 + MSE 损失的设定下给出严格否定回答。作者淡化的竞争路线包括:(i) 不关心全局极小值、只关心"足够好的局部极小值"的泛化误差分析(如 neural tangent kernel 框架);(ii) 从平均场/分布动力学角度分析 SGD 的全局收敛性(如 Mei et al., 2018)。什么明显该被引 / 该存在、却没出现在 intro 里:作者没有引用关于 loss landscape 中鞍点(saddle points)主导的严格结果(如 Dauphin et al., 2014),也没有引用 diffusion models / score matching 中关于非凸优化景观的近期严格分析——这些工作可能提供不同的视角。值得研究者去查的问题:作者对"高概率"的定义是否与实践中 SGD 的随机初始化分布匹配?构造的数据分布是否具有实际意义,还是纯粹的病态反例?
张力¶
未见明显对立引用。但存在一个微妙的张力:Choromanska et al. (2015) 的 spin glass 猜想暗示"局部极小值的风险值集中在某个区间",而本文构造的层级结构表明"局部极小值的风险值可以任意接近全局最优"——两者并不矛盾(前者是统计物理的启发式,后者是严格构造),但读者需要注意:本文的构造可能恰好落在 spin glass 猜想不适用的极端区域。
二、最核心、最简单的例子 / 数学问题¶
第一步:把符号、模型、可观测数据交代清楚¶
符号(逐个点名):
- \(d\):输入维度(input dimension),即每个数据点的特征数。
- \(N\):训练样本量(number of training samples)。
- \(\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N\):训练数据集,其中 \(x_i \in \mathbb{R}^d\) 是输入,\(y_i \in \mathbb{R}\) 是输出(标量)。
- \(\mathcal{N}\):人工神经网络(ANN)的参数化函数类,即网络结构(层数、宽度、激活函数)固定后,由参数 \(\theta\) 决定的函数族 \(\{f_\theta : \mathbb{R}^d \to \mathbb{R} : \theta \in \Theta\}\)。
- \(\theta \in \Theta\):网络的参数向量(weights and biases),是优化变量。
- \(\mathcal{L}(\theta) = \frac{1}{N} \sum_{i=1}^N (f_\theta(x_i) - y_i)^2\):均方误差(MSE)损失函数,是我们要最小化的目标。
- \(\theta^* \in \arg\min_{\theta \in \Theta} \mathcal{L}(\theta)\):全局极小值(global minimizer),即损失函数的最小值点。
- \(\hat{\theta}_T\):优化器运行 \(T\) 步后输出的参数估计。
- \(\mathbb{P}(\cdot)\):概率,用于描述随机初始化 + 随机梯度噪声下的优化轨迹。
模型(数据生成机制):
- 本文不假设数据来自某个真实模型。相反,作者主动构造特定的数据分布 \(\mathcal{D}\)(即特定的 \((x_i, y_i)\) 取值),使得损失景观 \(\mathcal{L}(\theta)\) 具有特定的几何结构(如存在一个"陷阱"区域,SGD 以高概率落入其中)。
- 网络结构:浅层 ANN,具体为单隐层(one hidden layer)网络,激活函数为 ReLU(\(\sigma(z) = \max(0, z)\))或类似的分段线性函数。输出层为线性。
- 优化器:vanilla SGD、momentum SGD、AdaGrad、RMSprop、Adam——这些是算法,不是统计模型的一部分,但它们的更新规则决定了轨迹 \(\{\theta_t\}_{t=1}^T\)。
可观测数据:
- 研究者实际能观测到的是:训练数据集 \(\mathcal{D}\)(输入-输出对)、网络结构、优化器的超参数(学习率、动量系数等)、以及优化器运行过程中的参数轨迹 \(\{\theta_t\}\) 和损失值 \(\{\mathcal{L}(\theta_t)\}\)。
- 想要但观测不到的是:全局极小值 \(\theta^*\) 的具体位置(除非穷举搜索)、以及 SGD 轨迹是否最终落入 \(\theta^*\) 的邻域——这正是本文要证明"不会发生"的事情。
第二步:讲最小内核¶
最小内核:本文的核心命题可以剥离为以下最简形式——
最简设定:考虑一个单输入(\(d=1\))、单隐层、单个隐藏神经元的 ReLU 网络,即 \(f_\theta(x) = a \cdot \max(0, wx + b)\),其中 \(\theta = (a, w, b)\)。训练数据只有两个点:\((x_1, y_1) = (0, 0)\) 和 \((x_2, y_2) = (1, 1)\)。损失为 MSE。
在这个最简设定下,损失函数 \(\mathcal{L}(a, w, b) = \frac{1}{2}[(f_\theta(0) - 0)^2 + (f_\theta(1) - 1)^2]\)。由于 \(f_\theta(0) = a \cdot \max(0, b)\),\(f_\theta(1) = a \cdot \max(0, w + b)\),损失景观可以显式写出。
核心观察:当 \(b < 0\) 且 \(w + b < 0\) 时(即 ReLU 对两个输入都"关闭"),\(f_\theta(0) = f_\theta(1) = 0\),损失恒为 \(1/2\)。这是一个平坦区域(plateau),梯度为零。如果 SGD 的初始化和噪声将参数推入这个区域,它就会永远卡住,无法到达全局极小值(全局极小值在 \(a=1, w=1, b=0\) 处,损失为 0)。
为什么这是最小内核:这个例子展示了本文的全部核心机制——ReLU 的"死亡"区域(dead region) 导致损失景观中存在梯度为零的平坦区域,SGD 一旦进入就无法逃离。本文的一般性定理(覆盖 \(d\) 维输入、多个隐藏神经元、多种优化器)本质上只是这个机制的加壳:构造更复杂的数据分布和网络结构,使得"死亡区域"以高概率被 SGD 的轨迹命中,且命中后无法逃离。
要证的命题退化成:在这个最简设定下,命题退化为——"从某些初始化出发,vanilla SGD 以正概率收敛到损失为 \(1/2\) 的平坦区域,而非损失为 0 的全局极小值"。证明只需验证:存在一个初始化区域,SGD 的更新规则(\(b \leftarrow b - \eta \cdot \partial \mathcal{L}/\partial b\),其中梯度为零因为 ReLU 关闭)使得参数不动。
为什么成立:因为 ReLU 在负区域的梯度为零,MSE 损失对参数的偏导也为零,SGD 更新量为零,参数永远停留在原地。这就是"不收敛到全局极小值"的严格证明。
一般化:本文的一般性定理将上述机制推广到:(i) 更一般的激活函数(分段线性、有"死亡"区域);(ii) 多个隐藏神经元(构造部分神经元死亡、部分活跃的混合状态);(iii) 多种优化器(证明 AdaGrad/RMSprop/Adam 的更新规则在死亡区域同样无法逃离,因为梯度为零时所有自适应缩放都无效);(iv) 高概率(通过构造数据分布使得死亡区域在参数空间中占据足够大的测度,随机初始化以高概率落入其中)。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在浅层 ReLU(及类似)激活函数的 ANN 训练中,SGD 类方法(vanilla SGD、momentum SGD、AdaGrad、RMSprop、Adam)是否以高概率收敛到全局极小值?
- 核心工具 / 方法:构造性证明——通过精心设计数据分布和网络结构,显式构造损失景观中的"陷阱"区域(ReLU 死亡区域),并证明这些优化器以高概率落入且无法逃离。
- 主要结论:在构造的设定下,上述所有 SGD 类方法都以高概率不收敛到全局极小值;同时,损失景观中存在层级结构的局部极小值,其风险值可以任意接近全局最优。
关键设定与假设¶
在第二节最小记号的基础上,补全完整设定:
- 网络结构:浅层(单隐层)ANN,隐层有 \(H\) 个神经元,激活函数为 ReLU(\(\sigma(z) = \max(0, z)\))或更一般的分段线性、存在平坦区域的激活函数(如 leaky ReLU 的极限情形)。输出层为线性(无激活)。
- 数据分布:作者构造特定的输入-输出对。关键假设是数据点数量 \(N\) 有限且固定,输入 \(x_i\) 的取值使得网络输出对某些参数的偏导为零(即 ReLU 关闭)。
- 损失函数:标准 MSE 损失 \(\mathcal{L}(\theta) = \frac{1}{N} \sum_{i=1}^N (f_\theta(x_i) - y_i)^2\)。
- 优化器:vanilla SGD(固定学习率)、momentum SGD、AdaGrad、RMSprop、Adam。关键假设是学习率为常数(或衰减但不会在有限步内降到零),且梯度噪声来自小批量采样(mini-batch)。
- 初始化:随机初始化(如 Gaussian 或均匀分布),且初始化分布的支持集包含"死亡区域"。
相比已有文献的放宽/强化: - 放宽:不假设损失函数光滑(ReLU 不可微),不假设强凸或 Polyak-Łojasiewicz 条件。 - 强化:构造的数据分布是病态的(adversarial),而非自然数据分布。这意味着结论是"存在性"而非"普遍性"——不排除在自然数据分布下 SGD 能收敛到全局极小值。
主要结果¶
定理 1(vanilla SGD 不收敛到全局极小值):在构造的数据分布和网络结构下,存在一个参数区域 \(\mathcal{R}\)(ReLU 死亡区域),使得: - 若初始化 \(\theta_0 \in \mathcal{R}\),则 vanilla SGD 的轨迹 \(\{\theta_t\}\) 以概率 1 停留在 \(\mathcal{R}\) 内,即 \(\mathcal{L}(\theta_t) = \text{const} > \mathcal{L}(\theta^*)\) 对所有 \(t\) 成立。 - 若初始化 \(\theta_0\) 从某个分布中抽取,则 \(\mathbb{P}(\theta_0 \in \mathcal{R}) \geq c > 0\),其中 \(c\) 是正常数。
定理 2(扩展到自适应优化器):同样的结论对 momentum SGD、AdaGrad、RMSprop、Adam 成立。证明思路:在死亡区域内,梯度为零,因此所有优化器的更新量为零(AdaGrad/RMSprop/Adam 的缩放因子无论多大,乘以零梯度仍为零)。
定理 3(局部极小值的层级结构):损失景观中存在一族局部极小值 \(\{\theta^{(k)}\}_{k=1}^\infty\),其风险值 \(\mathcal{L}(\theta^{(k)})\) 单调递减且 \(\lim_{k \to \infty} \mathcal{L}(\theta^{(k)}) = \mathcal{L}(\theta^*)\)。即存在风险值任意接近全局最优的局部极小值,但 SGD 以高概率无法到达它们。
技术难点: - 难点 1:证明死亡区域在参数空间中具有正测度(positive measure),从而随机初始化以正概率落入。 - 难点 2:证明死亡区域是吸收态(absorbing set)——一旦进入,所有优化器的更新都为零。 - 难点 3:构造层级结构——需要显式构造一族局部极小值,并计算其风险值。
证明路线与技术技巧¶
整体路线(3-5 步逻辑主干):
- 构造数据分布:选择输入 \(x_i\) 使得网络输出 \(f_\theta(x_i)\) 对某些参数的偏导为零。具体地,令所有输入 \(x_i\) 落在某个半空间内,使得 ReLU 对所有 \(x_i\) 都关闭(即 \(w \cdot x_i + b < 0\) 对所有 \(i\))。
- 识别死亡区域:定义参数区域 \(\mathcal{R} = \{\theta : w \cdot x_i + b < 0, \forall i\}\)。在此区域内,\(f_\theta(x_i) = 0\) 对所有 \(i\),因此 \(\mathcal{L}(\theta) = \frac{1}{N} \sum_{i=1}^N y_i^2 = \text{const}\),且梯度 \(\nabla \mathcal{L}(\theta) = 0\)。
- 证明吸收性:对每种优化器,验证在梯度为零时更新量为零。对 vanilla SGD:\(\theta_{t+1} = \theta_t - \eta \cdot 0 = \theta_t\)。对 momentum:\(v_{t+1} = \beta v_t\),若 \(v_0 = 0\) 则 \(v_t = 0\) 对所有 \(t\)。对 AdaGrad/RMSprop/Adam:累积梯度平方为零,缩放因子无定义或为无穷,但梯度为零使得更新为零(需处理除零问题,作者通过连续性论证或定义约定解决)。
- 计算命中概率:假设初始化分布(如 Gaussian)在 \(\mathcal{R}\) 上的概率质量为正,则 SGD 以正概率落入 \(\mathcal{R}\) 并永远停留。
- 构造层级结构:对于 \(k = 1, 2, \ldots\),构造参数 \(\theta^{(k)}\) 使得部分 ReLU 神经元激活、部分关闭,且输出 \(f_{\theta^{(k)}}(x_i)\) 逼近 \(y_i\)。通过调节激活神经元的权重,使风险值 \(\mathcal{L}(\theta^{(k)}) \to 0\)。
关键技巧: - ReLU 的齐次性:ReLU 是分段线性的,其"死亡区域"(输入为负时输出恒为零)提供了天然的梯度为零区域。这是构造的核心工具。 - 概率不等式:用于估计随机初始化落入死亡区域的概率下界。作者使用 Gaussian 测度的浓度不等式(如 Borell-TIS 不等式)来证明正概率。 - 构造性论证:不依赖抽象的存在性定理,而是显式写出数据点、网络权重和参数区域,使证明完全可验证。
真实例子与应用¶
本文没有真实数据实验。它是纯理论论文,所有"例子"都是构造性的数学例子(如上述单输入、单神经元的最小例子)。作者在论文中可能包含数值模拟来验证理论预测(如随机初始化多次运行 SGD,统计落入死亡区域的频率),但这些模拟是验证性的,不是实际应用。
🔎 结论是否比证明窄¶
是。具体表现: - 定理的适用范围是"构造的数据分布和网络结构",但摘要和 intro 的措辞("disprove that SGD methods can find a global minimizer with high probability")可能被读者理解为更普遍的结论。作者在 intro 中应明确说明这是存在性结果(存在某些问题设定下 SGD 失败),而非普遍性结果(所有问题设定下 SGD 都失败)。 - 定理对浅层网络成立,但 intro 中讨论的实践场景多为深层网络。作者没有声称结论推广到深层网络,但读者容易产生这种误解。 - 定理假设固定学习率。实践中常用的学习率衰减(learning rate schedule)可能改变结论——如果学习率衰减到零,SGD 在死亡区域外可能更早收敛,但一旦进入死亡区域仍无法逃离。作者未讨论学习率衰减的影响。
四、开放问题¶
-
深层网络的推广:本文的构造依赖浅层网络的显式参数化。对深层网络(depth \(\geq 2\)),能否构造类似的反例?扎根点:intro 中作者仅声称"shallow ANNs"的结果,未提及深层。要确认是否真 gap:去读近 5 年关于 deep loss landscape 的构造性结果(如 Venturi et al., 2019; Safran & Shamir, 2018),看是否已有深层反例。
-
自然数据分布下的行为:本文构造的数据分布是病态的。在自然数据分布(如图像、文本)下,死亡区域是否仍以高概率被命中?扎根点:intro 中作者承认构造是"adversarial"的,但未讨论自然分布下的推广。要确认是否真 gap:去读关于 ReLU 死亡(dying ReLU)的实证文献,看实践中死亡神经元的发生频率。
-
学习率衰减的影响:本文假设固定学习率。若学习率按 \(O(1/t)\) 衰减,SGD 在死亡区域外的收敛行为改变,但进入死亡区域后仍无法逃离。是否存在学习率调度策略能避免落入死亡区域?扎根点:定理的证明依赖固定学习率,未讨论调度策略。要确认是否真 gap:去读关于 learning rate schedule 与 loss landscape 交互的理论工作(如 Li et al., 2019)。
-
层级结构的泛化误差:本文证明了存在风险值接近全局最优的局部极小值,但未分析这些极小值的泛化误差(test error)。是否存在风险值接近全局最优且泛化误差也小的局部极小值?扎根点:定理 3 只涉及训练损失(risk),未涉及泛化。要确认是否真 gap:去读关于"sharp vs flat minima"泛化差异的文献(如 Keskar et al., 2017; Dziugaite & Roy, 2017),看是否有理论衔接。
提醒:要确认上述某条是否真 gap,去读同子领域近期约 5 篇的 intro——都指向它 = 共识(真 gap),互相打架 = 机会。例如,关于深层反例,如果 2023-2025 年的多篇论文都在尝试构造深层反例但未成功,说明这是一个公认的开放问题;如果各论文对"深层是否更难构造反例"有不同看法,则说明存在分歧,可能有机会。
Maintained by 陈星宇 · Homepage · Source on GitHub