One Sample Stochastic Frank-Wolfe
One Sample Stochastic Frank-Wolfe
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Mingrui Zhang;Zebang Shen;Aryan Mokhtari;Hamed Hassani;Amin Karbasi
中科院分区：
文献类型：
--
作者：
Mingrui Zhang;Zebang Shen;Aryan Mokhtari;Hamed Hassani;Amin Karbasi
投影梯度下降法的优点之一在于其相当简单的机制和稳定的行为以及不精确的随机梯度，这使得它在许多机器学习应用中得到广泛使用。然而，一旦我们用更简单的线性程序替换投影算子（如 Frank-Wolfe 方法中所做的那样），简单性和稳定性都会受到严重打击。本文的目的是在不牺牲效率的情况下将它们带回来。在本文中，我们提出了第一个单样本随机 Frank-Wolfe 算法，称为 1-SFW，它避免了仔细调整批量大小、步长、学习率和其他复杂超参数的需要。特别是，1-SFW 实现了 $\mathcal{O}(1/\epsilon^2)$ 的最优收敛速度，以在随机凸设置中达到 $\epsilon$-次优解，以及随机单调 DR-子模最大化问题的 $(1-1/e)-\epsilon$ 近似解。此外，在一般的非凸设置中，1-SFW 在最多 $\mathcal{O}(1/\epsilon^3)$ 迭代后找到 $\epsilon$ 一阶驻点，实现当前已知的最佳收敛速度。所有这一切都可以通过设计一种新颖的无偏动量估计器来实现，该估计器控制优化过程的稳定性，同时在每次迭代中使用单个样本。
One of the beauties of the projected gradient descent method lies in its rather simple mechanism and yet stable behavior with inexact, stochastic gradients, which has led to its wide-spread use in many machine learning applications. However, once we replace the projection operator with a simpler linear program, as is done in the Frank-Wolfe method, both simplicity and stability take a serious hit. The aim of this paper is to bring them back without sacrificing the efficiency. In this paper, we propose the first one-sample stochastic Frank-Wolfe algorithm, called 1-SFW, that avoids the need to carefully tune the batch size, step size, learning rate, and other complicated hyper parameters. In particular, 1-SFW achieves the optimal convergence rate of $\mathcal{O}(1/\epsilon^2)$ for reaching an $\epsilon$-suboptimal solution in the stochastic convex setting, and a $(1-1/e)-\epsilon$ approximate solution for a stochastic monotone DR-submodular maximization problem. Moreover, in a general non-convex setting, 1-SFW finds an $\epsilon$-first-order stationary point after at most $\mathcal{O}(1/\epsilon^3)$ iterations, achieving the current best known convergence rate. All of this is possible by designing a novel unbiased momentum estimator that governs the stability of the optimization process while using a single sample at each iteration.