model derivation

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:

consequencenote
complete-data algebraic-distance fitting has a global SVD optimum; Sampson fitting is non-convexFitting is a Nullspace Problem
the parameter cotangent is rank one per data pointBackpropagation by the Implicit Function Theorem
is identified only up to , so The Parameter is a Grassmannian
all Jacobians are — no autodiff neededbelow

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

103286
2031 771
20410 626
1003176 851
10044 598 126
784 (MNIST)2308 505
78438.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