Computational complexity of learning algebraic varieties

DOI10.1016/J.AAM.2020.102100MaRDI QIDQ2221768zbMATH OpenOpenAlexFDO

Authors Oliver Gäfvert

Publication date 2 February 2021

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.03305

Mathematics Subject Classification ID

General nonlinear regression (62J02) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: 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.

Recommendations

• The complexity of exactly learning algebraic concepts
• On the Turing complexity of learning finite families of algebraic structures
• scientific article; zbMATH DE number 3936520
• scientific article; zbMATH DE number 3972183
• On Computational Complexity of Semilinear Varieties
• On the complexity of counting components of algebraic varieties
• scientific article; zbMATH DE number 48692
• ALGORITHMIC PROBLEMS IN VARIETIES
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Computational complexity in algebraic systems

Cites work

• Chern classes and characteristic cycles of determinantal varieties
• Critical points via monodromy and local methods
• Learning algebraic varieties from samples
• Nonlinear Dimensionality Reduction
• Numerically solving polynomial systems with Bertini
• Regeneration homotopies for solving systems of polynomials
• Software for numerical algebraic geometry: a paradigm and progress towards its implementation
• The Euclidean distance degree of an algebraic variety
• The Euclidean distance degree of smooth complex projective varieties
• The elements of statistical learning. Data mining, inference, and prediction
• Understanding machine learning. From theory to algorithms

Cited in

(2)

• Learning algebraic varieties from samples
• Algebraic machine learning with an application to chemistry

Describes a project that uses

Uses Software

• LearningAlgebraicVarieties
• Bertini
• Macaulay2

This page was built for publication: Computational complexity of learning algebraic varieties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2221768)