Computational complexity of learning algebraic varieties
This work addresses a theoretical problem in computational algebraic geometry, with potential applications in machine learning for understanding the complexity of fitting models to data, but it appears incremental as it builds on existing concepts like Euclidean Distance Degree.
The paper tackles the problem of analyzing the computational complexity of learning algebraic varieties, specifically by deriving a closed formula for the algebraic complexity of fitting an (n-1)-sphere to m points in C^n for n=1 and conjecturing a generalization for n>1 based on numerical experiments.
We analyze the complexity of fitting a variety, coming from a class of varieties, to a configuration of points in $\Bbb C^n$. The complexity measure, called the algebraic complexity, computes the Euclidean Distance Degree (EDdegree) of a certain variety called the hypothesis variety as the number of points in the configuration increases. For the problem of fitting an $(n-1)$-sphere to a configuration of $m$ points in $\Bbb C^n$, we give a closed formula of the algebraic complexity of the hypothesis variety as $m$ grows for the case of $n=1$. For the case $n>1$ we conjecture a generalization of this formula supported by numerical experiments.