通过 SGD 优化的两层神经网络可学习任意多项式链接函数的单指数目标函数，并具有与信息理论界限相匹配的样本和运行时间复杂度。

Jun, 2024

我们介绍了学习错误（LWE）问题的连续模拟，命名为 CLWE，我们从最坏情况拉特斯问题到 CLWE 给出了多项式时间量子约简，表明 CLWE 具有与 LWE 相似的硬度保证。

May, 2020

该论文研究了近期对未知量子电路的可学习性，证明了用于学习量子过程的量子统计查询的自然鲁棒性，并提供了一种有效的方式来评估各种统计噪声，为开发噪声容忍算法提供了强大的框架。我们对具有小的查询复杂度额外开销的常深度量子电路的学习算法进行了适应，并证明了通过统计查询在钻石距离内学习对数和更高深度的随机量子电路的平均情况下的下界。此外，我们展示了从量子统计查询中量子阈值搜索问题的困难性，并讨论了其对浅层量子电路可学习性的影响。最后，我们通过构造一个高效的区分器并证明量子无免费午餐定理的一个新变种，证明了伪随机幺正（PRU）不能使用常深度电路构造。

May, 2024

通过梯度下降，我们研究了学习等变神经网络的问题。尽管已知的问题对称（“等变性”）被纳入神经网络中，经验上改善了从生物学到计算机视觉等领域的学习流程的性能，但是一项有关学习理论的研究表明，在相关统计查询模型（CSQ）中，实际学习浅层全连接（即非对称）网络的复杂度呈指数级增长。在这项工作中，我们提出了一个问题：已知的问题对称是否足以减轻通过梯度下降学习等变神经网络的基本困难？我们的答案是否定的。特别地，我们给出了浅层图神经网络、卷积网络、不变多项式和排列子群的框架平均网络的下界，这些下界在相关输入维度中都以超多项式或指数级增长。因此，尽管通过对称性注入了显著的归纳偏差，但通过梯度下降实际学习等变神经网络所代表的完整函数类仍然是困难的。

Jan, 2024

利用梯度下降证明了学习单层神经网络的第一个超多项式下限，它包括使用小批量的梯度下降，需要锐利的激活函数和适用于特定查询的以前结果。与以前的结果不同，我们的结果适用于包括 ReLU 和 sigmoid 在内的广泛激活类别，并且围绕一种新型神经网络的结构构建。

Jun, 2020

通过梯度优化算法训练高频周期函数或模运算存在限制和挑战，即使频率或质数基数 - p 很大时梯度的方差也非常小，从而阻止该学习算法的成功。

Oct, 2023

探讨对输入分布和目标函数的特定假设是否足以保证使用基于梯度的方法进行学习，在此基础上提供了一些工具来证明不同类别的目标函数的难以学习性和困难输入分布。

Sep, 2016

本文研究神经网络的理论解释，针对单个隐藏层、平滑激活函数和良好输入分布条件下生成的数据可否进行有效学习，证明了对于广泛的激活函数和任何对数凹分布的输入，存在一类单隐藏层函数，其输出为和门，难以以任何精度有效地学习，这一下界对权重的微小扰动具有鲁棒性，且通过实验验证了训练误差的相变现象。

Jul, 2017

我们研究了使用参数化单量子比特门和固定双量子比特门构建的量子神经网络，研究表明在无限宽度限制下，随机初始化参数的未训练网络生成的函数的概率分布收敛于高斯过程。通过梯度下降法对网络进行训练时，网络可以完美拟合训练集，并且训练后生成的函数概率分布仍然收敛于高斯过程。测量结果的统计噪声对网络的影响在多项式数量的测量下是可忽略的，而且网络的训练时间也是多项式级别的。

Feb, 2024

研究单个神经元面对对抗标签噪声情况下的 $L_2^2$ 损失学习问题。提出了一种高效算法，适用于广泛的激活函数族，包括 ReLU，并在远比之前工作更微弱的分布假设下近似最优 $L_2^2$ 误差，关键在于优化理论中局部误差界的一种新颖联系。

Jun, 2023