论文标题
使用低维和适应性数据结构加速富兰克沃尔夫算法
Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures
论文作者
论文摘要
在本文中，我们研究了加速一种称为条件梯度方法的称为Frank-Wolfe的优化算法的问题。我们开发并采用了两种新型的内部产品搜索数据结构，改善了[Shrivastava，Song and Xu，Neurips 2021]中的先前最快的算法。 *第一个数据结构使用低维的随机投影将问题降低到较低的维度，然后使用有效的内部产品数据结构。它具有预处理时间$ \ tilde o（nd^{ω-1}+dn^{1+o（1）}）$，并且对小常数$ρ$的迭代成本$ \ tilde o（d+n^ρ）$。 *第二个数据结构利用自适应内部产品搜索数据结构的最新发展，该结构可以输出所有内部产品。它具有预处理时间$ \ tilde o（nd）$，并且按迭代成本$ \ tilde o（d+n）$。 第一种算法改善了最先进的算法（随着预处理时间$ \ tilde o（d^2n^{1+o（1）}）$，在所有情况下，迭代的成本$ \ tilde o（dn^ρ）$）在所有情况下，而第二个则提供了更快的预处理时间和更快的时间，并且是适用于小数的数字。
In this paper, we study the problem of speeding up a type of optimization algorithms called Frank-Wolfe, a conditional gradient method. We develop and employ two novel inner product search data structures, improving the prior fastest algorithm in [Shrivastava, Song and Xu, NeurIPS 2021]. * The first data structure uses low-dimensional random projection to reduce the problem to a lower dimension, then uses efficient inner product data structure. It has preprocessing time $\tilde O(nd^{ω-1}+dn^{1+o(1)})$ and per iteration cost $\tilde O(d+n^ρ)$ for small constant $ρ$. * The second data structure leverages the recent development in adaptive inner product search data structure that can output estimations to all inner products. It has preprocessing time $\tilde O(nd)$ and per iteration cost $\tilde O(d+n)$. The first algorithm improves the state-of-the-art (with preprocessing time $\tilde O(d^2n^{1+o(1)})$ and per iteration cost $\tilde O(dn^ρ)$) in all cases, while the second one provides an even faster preprocessing time and is suitable when the number of iterations is small.
