  The vanishing ideal of a set of points $X\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 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.
