Zusammenfassung für den Vortrag am 11.10.2022 (15:00 Uhr)
Seminar on Nonlinear AlgebraElias Wirth (TU Berlin)
Learning Guarantees for Approximate Vanishing Ideal Computations
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.