优化平滑函数所需的比较
该研究论文证明了在高维、潜在非凸函数上找到 ε- 稳态点的复杂性下界,并探讨了基于 Oracle 算法的复杂度测量方法,显示出梯度下降、三次正则化牛顿法和广义 p 次正则化在自然函数类中是最优的。
Oct, 2017
本文提出相对平滑性和相对强凸性的概念,并相应地将标准算法扩展到新的设置中,应用于发展新的一阶方法来解决 D - 优化设计问题并进行计算复杂度分析。
Oct, 2016
该研究探讨了使用函数值而不是梯度的无导数算法在随机和非随机凸优化问题中的应用,同时关注其收敛速率,经实验表明使用随机扰动的梯度估算方法具有比传统随机梯度方法更快的收敛速率,尤其在光滑和非光滑情况下,且可以扩展到多次评估的情况。
Dec, 2013
本文研究了非凸优化中的无导数算法,利用有限差分器进行梯度逼近,最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法,并在收敛速度上达到了与精确梯度接近的性能。
Oct, 2019
非凸优化中寻找近似驻点的计算和查询复杂性是本文的关键研究内容,其中包括在无约束域中寻找近似驻点的问题的 PLS 完备性、二维情况下的零阶算法以及近似驻点的查询复杂性的特征化,同时还研究了约束优化问题中寻找近似 KKT 点的查询复杂性,并指出约束优化中近似 KKT 点与无约束优化中近似驻点的对应关系。
Oct, 2023
该研究提出了一种在 oracle 模型下,用高斯凸优化问题的 $p$ 阶 Taylor 拓展在查询点处获得的方法,可以实现任意 $p$ 阶导数为 Lipschitz 的凸函数的收敛速率 $\tilde {O}(1/k^{(3p+1)/2})$。
Dec, 2018
本文探讨了一种基于函数评估的平滑函数全局最小化方法,通过使用无穷次平方平滑函数之和联合建模函数以逼近并寻找全局最小值,在时间多项式子采样的情况下,该方法的计算复杂性为 $O (n^{3.5})$,空间复杂性为 $O (n^2)$,并可以实现与全局最优解的收敛速度为 $O (n^{-m/d + 1/2 + 3/d})$,尤其适用于具有大量导数的函数,且在维数为 $m$ 的情况下,全局最优解的收敛速度不会受到 “维度诅咒” 的影响,而仅受到最坏情况下的特定常数影响。
Dec, 2020
本文提出了一种在线凸优化算法,该算法在非稳态环境中表现出优异的动态后悔表现,通过充分利用流畅性条件,能够在动态后悔中代替对 T 的依赖,而采用问题相关的数量:损失函数的梯度变化、比较序列的累积损失和前两个 term 的最小值,从而使问题的复杂度自适应问题的困难程度,即在简单问题上使界限更紧,同时保证了最坏情况下相同的界限。
Jul, 2020
本文提出了新的计算方法和相关计算保证,利用一阶方法来解决凸优化问题,并且引入了增长常数 G 用作计算复杂度分析。特别地,当函数 f (・) 为非光滑函数时,提供了 Subgradient Descent Method 和平滑方法的新的计算保证。当 f (・) 是光滑函数时,对重新启动加速梯度方法的方案进行了阐述。
Nov, 2015
本文分析了多个仅基于函数值的逼近噪声函数梯度的方法,包括有限差分、线性插值、高斯平滑和球面平滑等,并给出了收敛性保证和数值结果以及应用于无导数优化算法的表现。
May, 2019