# Conditional Gradients for the Approximate Vanishing Ideal

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 50 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Subspace Robust Wasserstein Distances](https://mlsanity.com/paper/1901.08949/) (2019)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Weakly-supervised learning of visual relations](https://mlsanity.com/paper/1707.09472/) (2017)
- [Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm](https://mlsanity.com/paper/1905.13194/) (2019)
- [Weakly-Supervised Alignment of Video With Text](https://mlsanity.com/paper/1505.06027/) (2015)
- [An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion](https://mlsanity.com/paper/1511.02204/) (2015)
- [Boosting Frank-Wolfe by Chasing Gradients](https://mlsanity.com/paper/2003.06369/) (2020)
- [Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes](https://mlsanity.com/paper/1605.06492/) (2016)
- [Lazifying Conditional Gradient Algorithms](https://mlsanity.com/paper/1610.05120/) (2016)
- [Multi-output Polynomial Networks and Factorization Machines](https://mlsanity.com/paper/1705.07603/) (2017)
- [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)
- [Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets](https://mlsanity.com/paper/2011.03351/) (2020)
- [An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms](https://mlsanity.com/paper/1312.7864/) (2013)
- [Learning Infinite RBMs with Frank-Wolfe](https://mlsanity.com/paper/1710.05270/) (2017)

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

- [Approximate Vanishing Ideal Computations at Scale](https://mlsanity.com/paper/2207.01236/) (2022)

## Abstract (arXiv)

The vanishing ideal of a set of points Xsubseteq ℝn is the set of polynomials that evaluate to 0 over all points x ∈ X and admits an efficient representation by a finite set of polynomials called generators. To accommodate the noise in the data set, we introduce the pairwise conditional gradients approximate vanishing ideal algorithm (PCGAVI) that constructs a set of generators of the approximate vanishing ideal. The constructed generators capture polynomial structures in data and give rise to a feature map that can, for example, be used in combination with a linear classifier for supervised learning. In PCGAVI, we construct the set of generators by solving constrained convex optimization problems with the pairwise conditional gradients algorithm. Thus, PCGAVI not only constructs few but also sparse generators, making the corresponding feature transformation robust and compact. Furthermore, we derive several learning guarantees for PCGAVI that make the algorithm theoretically better motivated than related generator-constructing methods.