The single structural fact that makes the algebraic family tractable: the residual is linear in the parameter.
Sources: original to this vault (design and analysis); code:
lib/AlgebraicFactors.jl/src/veronese.jl,polynomial.jl,polyfit.jl,lib/AlgebraicFactors.jl/test/polynomial.jl.Theory (CT-ML wiki): Reverse Derivative Category
Setup
Collect all channels of a factor into one vector , . Let be the Veronese embedding of degree — the vector of all monomials of degree :
A vector of polynomials of degree is then exactly a matrix , and the residual of the implicit learner is
with the relation .
Why this is the right coordinatisation
The model factors as a fixed nonlinear embedding followed by a linear map.
Implemented in veronese and polynomial: graded degree, descending lexicographic
indices, affine or degree-exact tables, monomial or tensor-product Chebyshev
values and exact polynomial Jacobians. Chebyshev expects caller-scaled data in
[-1,1] without enforcing the domain. basis_change gives the exact affine-table
conversion; degree-exact Chebyshev products need not be homogeneous, so a square
conversion to homogeneous monomials generally does not exist.
Implemented in veronese and polynomial: graded degree, descending lexicographic
indices, affine or degree-exact tables, monomial or tensor-product Chebyshev
values and exact polynomial Jacobians. Chebyshev expects caller-scaled data in
[-1,1] without enforcing the domain. basis_change gives the exact affine-table
conversion; degree-exact Chebyshev products need not be homogeneous, so a square
conversion to homogeneous monomials generally does not exist.
Everything learnable is in the linear part. Consequences, each derived in its own note:
| consequence | note |
|---|---|
| complete-data algebraic-distance fitting has a global SVD optimum; Sampson fitting is non-convex | Fitting is a Nullspace Problem |
| the parameter cotangent is rank one per data point | Backpropagation by the Implicit Function Theorem |
| is identified only up to , so | The Parameter is a Grassmannian |
| all Jacobians are — no autodiff needed | below |
This is a genuinely unusual profile. A neural network is nonconvex in its parameters and trivial in its inputs. An algebraic factor is linear in its parameters and hard in its inputs. The difficulty has been moved from learning to inference.
Jacobians, exactly
has entries — a sparse matrix of monomials, computable exactly in integer arithmetic on the exponents. So
and, splitting by a polarity,
The implementation needs no automatic differentiation: first derivatives are polynomial expressions obtained by exponent arithmetic or Chebyshev recurrences. Rational inputs can be evaluated exactly; floating-point evaluation still rounds. Higher derivatives are not implemented, and no measured claim about their cost is made.
The number that kills it
| 10 | 3 | 286 |
| 20 | 3 | 1 771 |
| 20 | 4 | 10 626 |
| 100 | 3 | 176 851 |
| 100 | 4 | 4 598 126 |
| 784 (MNIST) | 2 | 308 505 |
| 784 | 3 | 8.09 × 10⁷ |
is simultaneously:
- the parameter count (times );
- the sample complexity — with data points the matrix of Fitting is a Nullspace Problem has a nontrivial null space for purely dimensional reasons, so you can fit a variety through the data while learning nothing. You need ;
- the size of the eigenproblem, dense (or iteratively);
- the number of columns Gröbner/border-basis algorithms manipulate.
One combinatorial count, four costs. This is why the family is filed under “low dimensions” and why no amount of implementation cleverness rescues it — see Open Problems in Algebraic Implicit Learning §2 for the escape routes that have been tried (sparse/structured supports, kernelisation, random projection) and why none of them fully works.
Choosing is not free either
Increasing does not merely add capacity; it also adds redundant vanishing polynomials. If vanishes on the data and , then also vanishes and lies in degree . These products lie in the degree- null space, but can be linearly dependent; there is no general N-fold dimension formula.
To identify new ideal generators rather than a fixed-degree vanishing space, a
procedure can work degree by degree, quotienting out the ideal generated by
what was already found. fit_nullspace returns the fixed-degree space; it does
not implement that quotient. That is exactly what approximate-vanishing-ideal and
border-basis algorithms do; see Fitting is a Nullspace Problem §“Doing it properly”.
Related: Fitting is a Nullspace Problem, The Parameter is a Grassmannian, Backpropagation by the Implicit Function Theorem