Learning Guarantees for Approximate Vanishing Ideal Computations

  • Elias Wirth (TU Berlin)
E1 05 (Leibniz-Saal)


The approximate vanishing ideal of a set of points $X\subseteq \R^n$ is the set of polynomials that approximately evaluate to $0$ over all points $\textbf{x} \in X$ and admits an efficient representation by a finite set of polynomials called generators. 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. Generator-constructing algorithms are widely studied, but their computational complexities remain expensive and the methods lack learning guarantees. We introduce a generator-constructing algorithm that admits several learning guarantees and whose computational complexity is linear in the number of samples.

Mirke Olschewski

MPI for Mathematics in the Sciences Contact via Mail

Upcoming Events of this Seminar