本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题,特别着重于高度平滑问题的凸优化问题,包括逻辑回归等。研究表明,相对于基于梯度的算法,高阶平滑性可用于改善估计速率,并精确地依赖于平滑度的程度,同时提出了此类算法可行性的上限。最后,作者还在在线优化设置中取得了类似的结果。
May, 2016
在在线学习中,优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下,对二阶平滑和强凸函数进行优化的问题;通过提出匹配的上下界,第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法,结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画,从而使算法能够在偏差 - 方差权衡方面达到最优平衡,以及一种用于启动阶段的新的迭代方法,它能够保持无界 Hessian 的性能。
Jun, 2024
本文介绍了使用随机零阶查询优化高维凸函数的问题,提出了两种算法,并表明两种算法只依赖于问题的环境维度的对数收敛率。实证研究证明了理论发现,并表明我们设计的算法在高维场景中优于经典的零阶优化方法。
Oct, 2017
本文研究了非凸优化中的无导数算法,利用有限差分器进行梯度逼近,最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法,并在收敛速度上达到了与精确梯度接近的性能。
Oct, 2019
零阶强化学习的计算方法在对抗性和随机性设置中的性能界限及其与维度的关系
本文提出了一种基于随机赌博反馈模型的新型优化算法,采用椭球算法的泛化形式,对凸紧致集上的凸利普希茨(Lipschitz)函数最小化问题进行求解,证明其性能在满足一定条件下与时间步数 T 为 O(d^3/2)同阶,并获得了泛化性能的高阶乘性加速,表现出良好的应用前景和性能优势。
Jul, 2011
研究非光滑、非凸的 Lipschitz 目标函数在具有噪声函数评估的条件下生成 $(\delta,\epsilon)$- 稳定点的复杂性,提出的算法具有 $O (d\delta^{-1}\epsilon^{-3})$ 的复杂度和最优收敛速率。
Jul, 2023
我们介绍了一种新的零阶算法,用于非凸和非光滑目标的私有随机优化。给定一个大小为 M 的数据集,我们的算法确保(α,αρ²/2)-Rényi 差分隐私,并找到一个(δ,ε)- 稳定点,只要 M=Ω^(~)[(d/(δε³)) + (d^(3/2)/(ρδε²)) ]。这与其非私有的零阶模拟的最优复杂度相匹配。值得注意的是,尽管目标不是光滑的,只要 ρ ≥ √(d)ε,我们就有了 “免费” 的隐私。
本文研究了利用随机一阶预测器在凸集上最小化凸函数的问题,证明了函数在最小值点 $x_{f, S}^*$ 附近增长的速率是最优学习率的决定因素,并得到了关于学习率和复杂度的结论结果。
Jul, 2012
该研究探讨了使用函数值而不是梯度的无导数算法在随机和非随机凸优化问题中的应用,同时关注其收敛速率,经实验表明使用随机扰动的梯度估算方法具有比传统随机梯度方法更快的收敛速率,尤其在光滑和非光滑情况下,且可以扩展到多次评估的情况。
Dec, 2013