# Approximate Vanishing Ideal Computations at Scale

arXiv: https://arxiv.org/abs/2207.01236 · HTML: https://mlsanity.com/paper/2207.01236/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 53 references that are in the map.
- First posted on arXiv 4 Jul 2022.

## Builds on (most cited first, 9 of 9)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Deep Neural Network Training with Frank-Wolfe](https://mlsanity.com/paper/2010.07243/) (2020)
- [Polytope conditioning and linear convergence of the Frank-Wolfe algorithm](https://mlsanity.com/paper/1512.06142/) (2015)
- [Gradient Boosts the Approximate Vanishing Ideal](https://mlsanity.com/paper/1911.04174/) (2019)
- [Spurious Vanishing Problem in Approximate Vanishing Ideal](https://mlsanity.com/paper/1901.08798/) (2019)
- [Dual-to-kernel learning with ideals](https://mlsanity.com/paper/1402.0099/) (2014)
- [Border basis computation with gradient-weighted normalization](https://mlsanity.com/paper/2101.00401/) (2021)
- [Sparser Kernel Herding with Pairwise Conditional Gradients without Swap Steps](https://mlsanity.com/paper/2110.12650/) (2021)
- [Conditional Gradients for the Approximate Vanishing Ideal](https://mlsanity.com/paper/2202.03349/) (2022)

## Built on by (most cited first, 6 of 6)

- [Learning to Compute Gr"obner Bases](https://mlsanity.com/paper/2311.12904/) (2023)
- [Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms](https://mlsanity.com/paper/2505.23696/) (2025)
- [Approximating Latent Manifolds in Neural Networks via Vanishing Ideals](https://mlsanity.com/paper/2502.15051/) (2025)
- [Vanishing Component Analysis with Contrastive Normalization](https://mlsanity.com/paper/2210.16171/) (2022)
- [Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes](https://mlsanity.com/paper/2505.11259/) (2025)
- [Diagnosing Faults in Reinforcement Learning Simulators and World Models with Canonical Polynomial Invariants](https://mlsanity.com/paper/2609.13194/) (2026)

## Abstract (arXiv)

The vanishing ideal of a set of points X = x1, ldots, xmsubseteq ℝn is the set of polynomials that evaluate to 0 over all points x ∈ 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.