Computational complexity of learning algebraic varieties
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Algebra Unveils Deep Learning -- An Invitation to Neuroalgebraic Geometry
In this position paper, we promote the study of function spaces parameterized by machine learning models through the lens of algebraic geometry. To this end, we focus on algebraic models, such as neural networks with pol…
Deep LearningPositionCovering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications
Covering numbers are a powerful tool used in the development of approximation algorithms, randomized dimension reduction methods, smoothed complexity analysis, and others. In this paper we prove upper bounds on the cover…
Dimensionality ReductionTesting the variety hypothesis
Given a probability measure on the unit disk, we study the problem of deciding whether, for some threshold probability, this measure is supported near a real algebraic variety of given dimension and bounded degree. We ca…
Algebraic Systems Biology: A Case Study for the Wnt Pathway
Steady state analysis of dynamical systems for biological networks give rise to algebraic varieties in high-dimensional spaces whose study is of interest in their own right. We demonstrate this for the shuttle model of t…
Computing algebraic degrees of phylogenetic varieties
A phylogenetic variety is an algebraic variety parameterized by a statistical model of the evolution of biological sequences along a tree. Understanding this variety is an important problem in the area of algebraic stati…