Abstract for the talk on 11.10.2022 (15:00 h)

Seminar on Nonlinear Algebra

Elias Wirth (TU Berlin)
Learning Guarantees for Approximate Vanishing Ideal Computations
11.10.2022, 15:00 h, MPI für Mathematik in den Naturwissenschaften Leipzig, 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.

 

20.09.2022, 12:01