论文标题
用于有限和凸功能的加速DFO算法
An Accelerated DFO Algorithm for Finite-sum Convex Functions
论文作者
论文摘要
无衍生化的优化（DFO）最近在机器学习方面获得了很多动力，激发了人们对社区的兴趣，以设计无法访问梯度的问题的更快方法。尽管在DFO文献中对加速度的概念给予了一些关注，但在理论上尚未显示具有有限和团结的目标函数的现有随机算法以达到加速收敛速率。在这种设置中使用加速度的算法很容易稳定，因此很难达到融合。在这项工作中，我们利用目标的有限和结构，以设计降低方差的DFO算法，该算法可实现加速。我们证明了平滑凸和强有限的有限和目标函数的收敛速率。最后，我们在几个任务和数据集上从经验上验证我们的理论结果。
Derivative-free optimization (DFO) has recently gained a lot of momentum in machine learning, spawning interest in the community to design faster methods for problems where gradients are not accessible. While some attention has been given to the concept of acceleration in the DFO literature, existing stochastic algorithms for objective functions with a finite-sum structure have not been shown theoretically to achieve an accelerated rate of convergence. Algorithms that use acceleration in such a setting are prone to instabilities, making it difficult to reach convergence. In this work, we exploit the finite-sum structure of the objective in order to design a variance-reduced DFO algorithm that provably yields acceleration. We prove rates of convergence for both smooth convex and strongly-convex finite-sum objective functions. Finally, we validate our theoretical results empirically on several tasks and datasets.
