无导数优化中梯度逼近的理论和实证比较
提出了一种创新算法,通过考虑目标函数的异质曲率,将球面平滑和高斯平滑方法扩展到噪声无导数优化中,动态调整平滑核的形状以逼近局部最优点周围的海森矩阵,从而通过采样大大减小了噪声评估中梯度估计的误差。通过对人工问题的数值实验展示了该方法的有效性,并展示了与现有的最先进启发式无导数和贝叶斯优化方法相比,在调整 NP - 难组合优化求解器时的改进性能。
May, 2024
该论文通过将离散数据应用于尺度空间理论,深入探讨了逼近高斯平滑和高斯导数计算的问题,研究了三种不同的离散化方法,并通过理论和实验分析了它们的性能特征,结果表明在非常精细的尺度下,离散模拟的高斯核和导数逼近比其他方法表现更好。
Nov, 2023
本文介绍了一种有限差分拟牛顿法,该方法利用 BFGS 更新的可伸缩性和能力,采用自适应程序选择基于 Hamming(2012)和 Moré 和 Wild(2011)的噪声估计技术的差分间隔 h。该算法包含恢复机制,以防止线性搜索过程无法产生可接受点的情况。通过数值实验将该方法与函数插值信任域方法进行了比较,同时还提出了一种考虑噪声线性搜索过程效应的新型收敛分析。
Mar, 2018
本文提供了关于利用无噪声函数评估进行 Derivative Free Optimization 的收敛速度下限,揭示了算法性能之间的根本和不可避免的差距。然而,在某些情况下 DFO 是不可避免的,对于这种情况,我们提出了一种新的 DFO 算法,被证明对于强凸目标函数类是近乎最优的。该算法的一个独特特点是仅使用布尔值函数比较,而不是函数评估。这使得该算法在更广泛的应用范围内有用,例如基于人工主体配对比较的优化。我们还展示了无论 DFO 是基于有噪音的函数评估还是布尔值函数比较,收敛率都是相同的。
Sep, 2012
本文探讨了一种基于函数评估的平滑函数全局最小化方法,通过使用无穷次平方平滑函数之和联合建模函数以逼近并寻找全局最小值,在时间多项式子采样的情况下,该方法的计算复杂性为 $O (n^{3.5})$,空间复杂性为 $O (n^2)$,并可以实现与全局最优解的收敛速度为 $O (n^{-m/d + 1/2 + 3/d})$,尤其适用于具有大量导数的函数,且在维数为 $m$ 的情况下,全局最优解的收敛速度不会受到 “维度诅咒” 的影响,而仅受到最坏情况下的特定常数影响。
Dec, 2020
通过分析,我们展示了对于凸问题,自适应的近端梯度方法不受传统的 Lipschitzian 假设的限制。我们的分析揭示了一类无需线搜索的方法仍然在纯粹的局部 Hölder 梯度连续性下收敛,特别是连续可微分的半代数函数。为了解决局部 Lipschitz 连续性的缺失,流行的方法围绕着 ε- 预测器和 / 或线搜索程序。相反,我们利用 Hölder 不等式,而不需要任何近似,同时保持自适应方案的无需线搜索的特性。此外,我们在先验地不了解局部 Hölder 常数和 Hölder 连续性的阶的情况下,证明了完全序列的收敛性。在数值实验中,我们将其与基准方法在涵盖局部和全局 Hölder 设置的各种机器学习任务中进行比较。
Feb, 2024
该研究提出了一种新型的鲁棒梯度下降算法,采用直接对观测值施加平滑的乘性噪声,构建软截断梯度坐标之和的方式,使其具有与传统方法相当的理论保证和更高的数据分布类别广泛性能。
Oct, 2018
我们开发了一种梯度下降法的新次优性边界,该边界依赖于优化路径中的目标条件,而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性,这是一种梯度变化的度量,我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束,我们展示了这些方程对于凸二次函数是容易解决的,并为两种传统步长提供了新的保证。对于一般函数,我们证明了 Polyak 步长和归一化梯度下降法尽管不使用方向平滑性的任何知识,但能够获得快速的路径相关性。逻辑回归上的实验证明,我们的收敛保证比基于 L 平滑性的传统理论更紧致。
Mar, 2024