本文由Sungyoon Kim和Mert Pilanci共同撰写，两位作者均来自斯坦福大学电气工程系。该研究发表于2024年的第41届国际机器学习会议（ICML），并收录于PMLR 235期刊中。本文主要探讨了两层ReLU神经网络在权重衰减正则化下的凸松弛问题，并证明了在随机训练数据下，原始问题与其凸松弛之间的相对最优性差距可以被一个对数因子所限制。此外，本文还提出了一种多项式时间算法，能够在对数因子内近似求解原始的非凸问题，并证明了在温和假设下，局部梯度方法能够以高概率收敛到具有低训练损失的解。
随着深度学习（Deep Learning）的巨大成功，数据驱动的方法在计算机科学的各个领域中占据了重要地位。然而，尽管深度学习模型具有高度非凸的优化景观（Non-convex Landscape），局部梯度方法（如随机梯度下降SGD和Adam）却能够很好地找到网络的近似全局最小值。这一现象引起了学习理论社区的广泛关注，许多研究者致力于在特定假设下（如无限宽度限制、过度参数化等）证明局部方法的收敛性。
然而，训练一个简单的两层ReLU神经网络已被证明是NP难问题。尽管增加网络的宽度（Width）看似使问题更加复杂，但实际上却使得问题更容易求解。因此，理解临界宽度（Critical Width）m*，即在m ≥ m*时保证多项式时间算法的存在性，成为了一个自然的研究兴趣。
本文的研究流程主要包括以下几个步骤：
问题定义与凸松弛：
本文首先定义了两层ReLU神经网络的训练问题，并提出了其凸松弛形式。具体来说，原始问题是一个非凸优化问题，而凸松弛问题通过线性化和适当的缩放，将非凸问题转化为凸问题。凸松弛问题的变量数量可能是指数级的，但在临界宽度m*下，当m ≥ m*时，存在一个多项式时间算法能够精确求解原始问题。
随机高斯松弛：
由于凸松弛问题的变量数量可能非常大，本文提出了一种随机高斯松弛方法，即通过随机采样高斯向量来生成超平面排列模式（Hyperplane Arrangement Patterns），从而减少问题的复杂性。本文证明了在这种随机松弛下，原始问题与凸松弛之间的相对最优性差距可以被一个对数因子所限制。
局部梯度方法的收敛性：
本文还证明了在温和假设下，局部梯度方法（如SGD和Adam）能够以高概率收敛到一个具有低训练损失的平稳点。这一结果表明，即使局部梯度方法收敛到平稳点，它们仍然能够近似全局最优解。
多项式时间算法：
基于上述结果，本文提出了一种多项式时间算法，能够在所有维度上以多项式复杂度近似求解原始问题，并保证其解在对数因子内接近全局最优解。
本文的主要结果可以总结为以下几点：
相对最优性差距的界限：
在随机训练数据的假设下，原始非凸问题与其随机凸松弛之间的相对最优性差距可以被一个对数因子所限制。具体来说，本文证明了当网络宽度m满足一定条件时，随机凸松弛的解与原始问题的解之间的差距为O(√log n)。
局部梯度方法的收敛性：
本文证明了在温和假设下，局部梯度方法能够以高概率收敛到一个具有O(√log n)相对训练误差的平稳点。这一结果表明，即使局部梯度方法收敛到平稳点，它们仍然能够近似全局最优解。
多项式时间算法：
本文提出了一种多项式时间算法，能够在所有维度上以多项式复杂度近似求解原始问题，并保证其解在对数因子内接近全局最优解。该算法的复杂度为O(d³m³)，其中d为数据维度，m为网络宽度。
本文的主要贡献在于提供了两层ReLU神经网络的凸松弛问题的近似保证，并证明了在随机训练数据下，随机凸松弛能够在多项式时间内近似求解原始问题。此外，本文还揭示了局部梯度方法在训练神经网络时的收敛性，表明即使这些方法收敛到平稳点，它们仍然能够近似全局最优解。
本文的研究具有重要的科学价值和应用价值。从科学角度来看，本文为理解神经网络的训练过程提供了新的理论工具，特别是在非凸优化和凸松弛之间的关系方面。从应用角度来看，本文提出的多项式时间算法为实际训练神经网络提供了理论保证，尤其是在大规模数据集上的应用。
本文的研究亮点包括：
新颖的凸松弛方法：
本文提出了一种随机高斯松弛方法，能够在多项式时间内近似求解原始的非凸问题，并提供了严格的理论保证。
局部梯度方法的收敛性分析：
本文首次在正则化ReLU网络下证明了局部梯度方法的收敛性，表明这些方法能够以高概率收敛到具有低训练损失的平稳点。
多项式时间算法：
本文提出的多项式时间算法为实际训练神经网络提供了理论支持，尤其是在大规模数据集上的应用。
本文作者指出，未来的研究方向包括：
去除对数因子：
进一步研究如何去除近似保证中的对数因子，以提高算法的精度。
扩展到其他网络架构：
将本文的结果扩展到其他神经网络架构，如卷积神经网络（CNN）、Transformer和多层网络等。
本文通过凸松弛方法为两层ReLU神经网络的训练问题提供了新的理论工具，并证明了在随机训练数据下，随机凸松弛能够在多项式时间内近似求解原始问题。此外，本文还揭示了局部梯度方法在训练神经网络时的收敛性，表明即使这些方法收敛到平稳点，它们仍然能够近似全局最优解。本文的研究为神经网络的训练过程提供了新的理论支持，并具有广泛的应用前景。