We propose a novel Stochastic Frank-Wolfe (a.k.a. conditional gradient) algorithm for constrained smooth finite-sum minimization with a generalized linear prediction/structure. This class of problems includes empirical risk minimization with sparse, low-rank, or other structured constraints. The proposed method is simple to implement, does not require step-size tuning, and has a constant per-iteration cost that is independent of the dataset size. Furthermore, as a byproduct of the method we obtain a stochastic estimator of the Frank-Wolfe gap that can be used as a stopping criterion. Depending on the setting, the proposed method matches or improves on the best computational guarantees for Stochastic Frank-Wolfe algorithms. Benchmarks on several datasets highlight different regimes in which the proposed method exhibits a faster empirical convergence than related methods. Finally, we provide an implementation of all considered methods in an open-source package.
翻译:我们建议采用新的Stochastic Frank-Wolfe(a.k.a. 有条件梯度)算法,以采用一般线性预测/结构,限制平稳的有限和最小化,这一类问题包括:以稀少、低级别或其他结构性限制,尽量减少经验风险;拟议方法简单易行,不需要步进式调整,并且具有与数据集大小无关的固定的逐项计算成本;此外,作为我们获得一个可以用作停止标准的弗兰克-沃夫差距随机估计器的方法的副产品,我们提出的方法匹配或改进了斯托切斯-弗兰克-沃夫算法的最佳计算保证;关于若干数据集的基准突出不同的制度,其中拟议的方法比相关方法更能显示经验趋同。最后,我们提出了在开放源软件包中采用所有考虑过的方法。