高维随机零阶优化
研究了基于Nesterov的对偶平均算法的随机优化算法,在预期损失是强凸的且最优解是(近似)稀疏的问题上进行优化,证明了在局部Lipschitz损失下,在T轮迭代后,我们的解决方案的误差最多为O((slogp)/T),并确立了我们的收敛率是最佳的,且在数值模拟中通过对最小二乘回归问题进行几个基准线的比较,证实了我们方法的有效性。
Jul, 2012
本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题,特别着重于高度平滑问题的凸优化问题,包括逻辑回归等。研究表明,相对于基于梯度的算法,高阶平滑性可用于改善估计速率,并精确地依赖于平滑度的程度,同时提出了此类算法可行性的上限。最后,作者还在在线优化设置中取得了类似的结果。
May, 2016
本文提出了针对非凸和凸优化的零阶随机逼近算法,并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点,并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法,并讨论了它们的收敛率。
Sep, 2018
本文提出了一种新的基于梯度的随机凸复合优化方法,将估计序列概念推广到随机优化算法中,以一种简单通用的方式证明了众多随机优化算法的收敛性,并提出几种可靠性策略。
Jan, 2019
本文介绍了两种零阶随机算法的优化和改进,其中一种通过新的ZO-SVRG-Coord-Rand算法和分析结果发现,比现有的同类算法以及ZO-GD和ZO-SGD更为优秀,另一种通过新的ZO-SPIDER-Coord算法有效降低了Gaussian随机变量的数量和步长的级别以实现相同的收敛速度和查询复杂度,并且自动实现了线性收敛率。
Oct, 2019
该论文提出了两种简单但强大的无梯度估计的梯度下降(GLD)算法,并从一种新的几何视角进行分析,展示了其具有收敛性的优势,并且能够在保证单调变换不变的情况下,利用低的潜在维数来实现优化,对BBOB和MuJoCo基准测试产生了良好的实证效果。
Nov, 2019
通过噪声、凸性和零阶优化等概念,研究在有界凸集合中的一类函数的优化问题,我们提出了一个基于质心方法的改进算法,证明其相对于最小值的差距的阶数小于d^2/√n,且比现有文献中已知的d^{2.5}/√n的速度更快,并且更简化。
Jun, 2024
非凸优化中采用维度无关的随机一阶方法(DISFOM)来解决样本复杂度问题,使用小批量估计梯度以达到ε-稳定点的样本复杂度为O((log d) / ε^4),进一步利用方差缩减可将该界限提高至O((log d)^(2/3) / ε^(10/3)),并提供了两种非平滑距离函数的选择,数值实验验证了所提框架的维度无关性。
Jun, 2024
在在线学习中,优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下,对二阶平滑和强凸函数进行优化的问题;通过提出匹配的上下界,第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法,结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画,从而使算法能够在偏差-方差权衡方面达到最优平衡,以及一种用于启动阶段的新的迭代方法,它能够保持无界Hessian的性能。
Jun, 2024