论文标题
大致规模消失的理想计算
Approximate Vanishing Ideal Computations at Scale
论文作者
论文摘要
一组点$ x = \ {\ mathbf {x} _1，\ ldots，\ mathbf {x} _m \} \ subseteq \ mathbb {r}^n $的消失理想的消失。发电机的有限子集。实际上，为了适应数据中的噪声，对构建近似消失理想的发电机的算法进行了广泛的研究，但它们的计算复杂性仍然昂贵。在本文中，我们扩展了Oracle近似消失的理想算法（OAVI），这是唯一具有已知学习保证的发电机构造算法。我们证明，正如先前声称的那样，OAVI的计算复杂性不是超级线性，而是在样本数量$ M $中线性的。此外，我们提出了两种改进的修改，以加以OAVI的训练时间：我们的分析表明，取代了Oavi中使用的求解器之一的成对条件梯度算法，其混合成对条件梯度算法更快地导致了$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $。最后，使用新的逆Hessian增强方法，几乎可以立即解决中间凸优化问题，从而在各种数值实验中通过多个数量级来改善Oavi的训练时间。
The vanishing ideal of a set of points $X = \{\mathbf{x}_1, \ldots, \mathbf{x}_m\}\subseteq \mathbb{R}^n$ is the set of polynomials that evaluate to $0$ over all points $\mathbf{x} \in X$ and admits an efficient representation by a finite subset of generators. In practice, to accommodate noise in the data, algorithms that construct generators of the approximate vanishing ideal are widely studied but their computational complexities remain expensive. In this paper, we scale up the oracle approximate vanishing ideal algorithm (OAVI), the only generator-constructing algorithm with known learning guarantees. We prove that the computational complexity of OAVI is not superlinear, as previously claimed, but linear in the number of samples $m$. In addition, we propose two modifications that accelerate OAVI's training time: Our analysis reveals that replacing the pairwise conditional gradients algorithm, one of the solvers used in OAVI, with the faster blended pairwise conditional gradients algorithm leads to an exponential speed-up in the number of features $n$. Finally, using a new inverse Hessian boosting approach, intermediate convex optimization problems can be solved almost instantly, improving OAVI's training time by multiple orders of magnitude in a variety of numerical experiments.
