在本文中，我们使用随机梯度下降（SGD）在两层全连接神经网络上解决了 k - 奇偶问题。我们展示了 SGD 能够以样本复杂性 O (d^(k-1))，使用 2^(Θ(k)) 个神经元有效地解决 k - 稀疏奇偶问题，从而与统计查询（SQ）模型的已知 Ω(d^k) 下界相匹配。我们通过构建一个能够正确解决 k - 奇偶问题的良好神经网络开始我们的理论分析。然后，我们证明了 SGD 训练出的神经网络可以有效地逼近这个良好网络，以小的统计误差来解决 k - 奇偶问题。我们的理论结果和发现得到了经验证据的支持，展示了我们方法的效率和效力。

Apr, 2024

该研究调查了深度学习在计算统计差距存在的情况下的算法设计选择。通过考虑离线稀疏奇偶学习，一种多层感知器的梯度训练的统计查询下界，我们展示了稀疏初始化和增加网络宽度在样本效率方面的显著改进，以及合成稀疏奇偶任务对于需要轴对齐特征学习的真实问题的代理用途。

Sep, 2023

本文研究了梯度下降算法在光滑内核中的应用限制，提出了基于特征向量预处理的 EigenPro 迭代优化算法，通过注入小规模二阶信息以改善此限制，从而实现更好的收敛性能。

Mar, 2017

对于分布式算法，通过对随机梯度下降（SGD）的压缩（如 top-k 或 random-k）等技术进行分析，发现它在进行误差补偿的情况下，能够实现与传统 SGD 相同的收敛速度，降低数据通信量达到更好的分布式可扩展性。

Sep, 2018

这篇论文证明了深度学习在低交叉可预测性函数分布上的失败，提出了算法约束和跨预测性的概念，并利用信息度量来限制统计间距离，探讨了神经网络、优化误差和算法分析的相关问题。

Dec, 2018

该论文提出了一个可以研究 Stochastic Gradient Descent 在 overparametrized 模型中的隐式偏差的通用框架，该框架使用一个描述参数极限动态的随机微分方程，并考虑了任意噪声协方差，文中给出了一些新结果，同时可以在线性模型中进行应用。

Oct, 2021

采用课程学习策略和稀疏样本可改善神经网络学习效率，对于一个混合了稀疏和密集输入的数据分布，采用应用在稀疏样本中的 curriculum noisy-GD/SGB 算法训练的 2 层 ReLU 神经网络可在有限的步数内学习到足够大次数的奇偶类型问题，而对于任何通过 noisy-GD/SGB 算法训练的神经网络，无论宽度或深度的大小，都需要额外的步骤才能学习，这可以通过理论和实验得出的结论加以支持。

Jun, 2023

本文旨在正式解释当代机器学习中观察到的 SGD 快速收敛现象。我们重点观察现代学习架构是过参数化的，并且被训练用于通过将经验损失（分类和回归）驱动到接近零的插值数据。我们表明，这些插值方案允许 SGD 快速收敛，与全梯度下降迭代次数相当。对于凸损失函数，我们获得了与全梯度下降相似的 “迷你批次” SGD 的指数收敛界限。关键的迷你批次大小可以视为有效迷你批次并行化的限制，并且几乎独立于数据大小。

Dec, 2017

研究了梯度法在有限循环群中学习离散对数奇偶位的局限性，理论和经验证实发现梯度函数集中在一个固定点附近，不管所使用的对数的基。通过使用内积空间中的 Boas-Bellman 不等式以及建立离散对数奇偶位函数的近似正交性，对于基于梯度的学习的限制性能进行了证明。使用基于神经网络的方法的实证实验证明了梯度法学习的局限性，随着群的阶数的增加，在预测奇偶位上的成功率逐渐降低。

Oct, 2023

实验研究表明，Stochastic Gradient Descent 利用条件互信息学习了从线性分类器到逐渐复杂的函数的分类器，解释了超参数化区域中 SGD 学习的分类器为什么往往具有良好的泛化能力。

May, 2019