本文提供了关于利用无噪声函数评估进行Derivative Free Optimization的收敛速度下限，揭示了算法性能之间的根本和不可避免的差距。然而，在某些情况下DFO是不可避免的，对于这种情况，我们提出了一种新的DFO算法，被证明对于强凸目标函数类是近乎最优的。该算法的一个独特特点是仅使用布尔值函数比较，而不是函数评估。这使得该算法在更广泛的应用范围内有用，例如基于人工主体配对比较的优化。我们还展示了无论DFO是基于有噪音的函数评估还是布尔值函数比较，收敛率都是相同的。

Sep, 2012

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

Jul, 2017

该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题，给出了统计查询下限。通过梯度提升过程对之前的低界进行放大，对具体问题ReLU回归（等同于伪装学习ReLU），我们证明任何统计查询算法都必须使用至少2^(n^c) ε个查询，从而阐述了与真实价值的学习问题不同的情况，我们的结果排除了一般（相对于关联）SQ学习算法，这在实值学习问题中是不寻常的。同时我们将两种常见的学习模型，即伪装学习和概率概念之间得到了最好的规约。

Jun, 2020

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

Oct, 2023

单指标模型是高维回归问题，根据未知的一维投影通过非线性、潜在非确定性的变换，标签与输入相关，涵盖了广泛的统计推断任务，提供了在高维领域研究统计和计算权衡的丰富模版。我们证明了在统计查询（SQ）和低次多项式（LDP）框架内计算高效算法所需的样本复杂度最低为Ω(d^k/2)，其中k是与模型关联的“生成”指数，我们明确定义了这个指数。此外，通过使用部分跟踪算法建立的匹配上界证明了这个样本复杂度也是充分的。因此，我们的结果表明，在SQ和LDP类中，只要k>2，计算与统计之间存在明显的差距。为了完成这个研究，我们提供了具有任意大生成指数k的平滑和Lipschitz确定的目标函数的示例。

Mar, 2024

从有限的点值样本学习多变量平滑目标函数的近似是科学计算和计算科学工程中的一个重要任务。本文调查了近年来在此方面取得的重大进展，描述了来自参数模型和计算不确定性量化的当代动机，无穷维巴拿赫空值全纯函数类，这些类的有限数据可学习性的基本限制，以及从有限数据高效学习此类函数的稀疏多项式和深度神经网络方法。针对深度学习的实际性能与深度神经网络的近似理论之间的差距，我们发展了实际存在理论的主题，宣称存在维度无关的 DNN 结构和训练策略，以证明在训练数据量方面具有可证明近似最优的泛化误差。

Apr, 2024

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

Apr, 2024

通过在高维度中训练剪枝神经网络并与梯度下降算法结合，我们研究了剪枝网络对广泛类统计模型学习的影响，发现剪枝神经网络在样本复杂度上相比未剪枝网络有提升，并引入了相关统计查询下界来支持这一观点。

Jun, 2024

研究具有加法结构的目标函数学习的计算和样本复杂性，证明了多项式target function可以通过梯度下降法训练两层神经网络高效地学习，同时建立了统计查询算法的边界。

Jun, 2024

本研究针对优化函数时投影随机一阶方法的表现限制进行了调查，特别在于$(\alpha,\tau,\mathcal{X})$-投影梯度主导特性下的子最优间隙。通过对非凸和凸函数的分析，提出了查询随机一阶预言者以达到全局最优点的复杂性界限，展示了投影方差减少算法在理论上的优越性与效率。

Aug, 2024