Source-linked AI summary
Testing Algebraic Complete Intersections
Alessandro Tamai
TL;DR
The paper asks whether sampled data concentrate near a real algebraic complete intersection in a prescribed, controlled-complexity class. It develops geometric estimates and a data-driven optimization procedure for testing that question. The resulting test distinguishes the stated alternatives, with sample complexity at most O(n^(d+1)) when the intrinsic parameters are fixed.
Problem
Directly optimizing geometric distance to candidate zero sets is computationally difficult because evaluating that distance requires global optimization.
Source: §1.2 · p. 5Method
The paper uses quantitative geometric estimates to replace geometric risk with an auxiliary polynomial-system optimization, then solves it with a data-driven algorithm.
Source: §1.2 · p. 5, §1.3 · p. 6, §4.1 · p. 13Results
For fixed l, d, k, ε, and α, the testing sample complexity grows at most as O(n^(d+1) as ambient dimension n increases.
Source: §1.1 · p. 4Takeaways & Limitations
The procedure tests concentration near complete intersections of prescribed dimension, bounded degree, and bounded condition number, returning a candidate regression manifold or identifying the no-manifold alternative up to controlled relaxation.
Source: §1 · p. 3, §1.1 · p. 4The modeled measures have compact support quantitatively separated from the domain boundary, and the tested manifolds are restricted to the prescribed dimension, degree, and condition-number bounds.
Source: §3 · p. 9, §3.1 · p. 10
Abstract
from arXiv · showhide
Given independent and identically distributed samples samples from a probability distribution in a potentially high-dimensional real space, we study the problem of testing whether the distribution is concentrated near a real algebraic complete intersection of prescribed dimension, bounded degree, and bounded condition number. We design an explicit and effective learning procedure which either certifies the nonexistence of such a manifold, up to a controlled relaxation of the approximation threshold, or returns a candidate regression manifold with controlled geometric complexity. Equivalently, the procedure tests the manifold hypothesis within this hypothesis class. The proposed procedure relies on quantitative geometric estimates for regular polynomial systems, which lead to a tractable auxiliary optimization problem. We then develop a data-driven algorithm to solve this auxiliary optimization problem, establishing explicit bounds on its sample and arithmetic complexity.
1. Introduction and Motivation
The paper develops a test for whether data concentrate near real algebraic complete intersections with prescribed dimension, degree, and condition number. It combines geometric estimates and statistical testing with a data-driven algorithm for the resulting optimization problem.
1. Introduction and Motivation
- The testing framework addresses whether a distribution is concentrated near a controlled-geometry manifold, extending the algebraic setting beyond the smooth-manifold class studied in.The algebraic variety setting of [LRHST25] allows singularities, whereas this paper focuses on complete intersections that are manifolds.Source: §1 · pp. 2–3
- The hypothesis class consists of real algebraic complete intersections with prescribed dimension, degree at most d, and condition number at most k.The defining polynomial system imposes global algebraic constraints, which cannot generally be enforced through independent local parametrizations alone.Source: §1 · p. 3
1.1. The Main Result: Testing Algebraic Complete Intersections.
- With at least m(n, l, d, k, ε, α) samples, the algorithm distinguishes the stated alternatives with probability at least 1−α and can return a candidate manifold within controlled relaxed parameters.For fixed l, d, k, ε, and α, the sample complexity grows at most as O(n^(d+1)) as ambient dimension n increases.Source: §1.1 · p. 4
1.2. Part I: Geometric Problem and Statistical Bounds.
- The auxiliary optimization avoids the intractable task of evaluating distance to implicitly described zero sets and supports a decision procedure for the original geometric test.The auxiliary risk can be evaluated from the observed data and defining polynomial system; its empirical optimization is treated in Part II.Source: §1.2 · pp. 5–6
- A quantitative Newton criterion detects a nearby zero when a regular polynomial system has sufficiently small value at an interior point.The result provides a finite-net route to detecting zeros, and hence a membership criterion for systems defining the hypothesis class.Source: §1.2 · p. 5
- A uniform Łojasiewicz-type inequality compares polynomial-system values with distance to the zero set, with its constant depending only on the prescribed condition-number bound k.This comparison motivates replacing geometric distance risk with the auxiliary risk based on the expected squared polynomial-system norm.Source: §1.2 · p. 5
1.3. Part II: Algorithmic Problem and Computational Complexity Bounds.
- Part II localizes the search near low-cost sublevel sets using the empirical cost matrix’s low spectral subspace and explicit covering-number bounds.The selected spectral index depends on the data; localization may reduce search complexity, but no reduction is guaranteed uniformly across datasets for a fixed threshold.Source: §1.3 · pp. 6–7
- The algorithm constructs a relaxed-admissible finite grid over the localized region, evaluates empirical cost there, and selects a candidate minimizer.The paper establishes convergence and arithmetic-complexity bounds for this procedure.Source: §1.3 · p. 7
2. Preliminaries
The preliminaries connect algebraic representations and regularity bounds to geometric control, then frame learning as minimizing risk from finite samples. The paper uses empirical risk minimization to approximate a best-fitting hypothesis.
2.1. The Bounded Geometry of Regression Manifolds.
- Complete intersections use the minimal number of defining equations, c = n − l, with the defining system having full rank along its zero set.A general algebraic manifold may require more equations than its codimension.Source: §2.1 · p. 7
- Degree bounds control algebraic complexity and geometry; Thom–Milnor’s bound gives O(d^n) connected components.The passage identifies degree as a complexity parameter for both the defining system and its manifold.Source: §2.1 · p. 7
- A bounded condition number controls manifold geometry, implies a positive lower bound on reach, and prevents overfitting in regression solutions.These are stated consequences of bounding the condition number of the defining equations.Source: §2.1 · pp. 7–8
2.2. The Geometric Hypothesis in Statistical Learning.
- Learning minimizes expected loss from i.i.d. samples, while empirical risk minimization replaces unknown risk with sample-based risk to approximate a true-risk minimizer.With suitable assumptions and enough samples, empirical-risk minimizers approximate minimizers of true risk.Source: §2.2 · p. 8
3. Hypothesis Class and Testing Problem
The paper defines a class of real algebraic complete intersections through dimension, degree, and condition-number bounds. Testing whether a measure satisfies the geometric hypothesis for this class reduces to evaluating a risk quantity and comparing it with the threshold.
3. Hypothesis Class and Testing Problem
- The model considers compactly supported Borel probability measures whose supports are quantitatively separated from the domain boundary.The radius R may be taken arbitrarily large, so the support condition imposes no genuine restriction on generality.Source: §3 · p. 9
3.1. Algebraic Complete Intersections and Condition Number.
- H_n(l, d, k) comprises real algebraic complete intersections of dimension l, degree at most d, and condition number at most k.The defining systems have a quantitative regularity condition encoded by the condition-number bound.Source: §3.1 · p. 10
- Testing the geometric hypothesis for H_n(l, d, k) amounts to evaluating the associated quantity and comparing it with threshold ε.The risk functional measures the fit of a candidate geometry to the data-generating measure.Source: §3.1 · p. 10
- Although admissible polynomial systems can be described by coefficient constraints, the corresponding polynomial zero sets lack an equally explicit description.The stated goal of Section 4 is to study these systems’ geometric properties to bridge that gap.Source: §3.1 · pp. 10–11
4. Geometric Properties of Complete Intersections
This section establishes geometric properties of regular systems, including criteria for nearby zeros and uniform Newton-flow and Łojasiewicz-type inequalities. It also specializes these bounds to polynomial systems, with constants depending only on the stated geometric parameters and, in the polynomial case, on τ and k.
4.1. A Zero Criterion for Regular Maps.
- The discriminant distance is characterized by C1 data, and a positive discriminant lower bound with sufficiently small residual guarantees a nearby zero via localized Newton iteration.The zero criterion uses a quantitative convergence radius determined by the condition number and non-degeneracy bound.Source: §4.1 · pp. 11, 13, 14, 15
4.2. A Uniform Lojasiewicz-Type Inequality.
- Under uniform non-degeneracy, a normalized Newton flow reaches Z(F) in time T = ||F(x)|| while remaining in the domain and a controlled neighborhood.Along the flow, ||F|| decreases at unit speed.Source: §4.2 · pp. 15–16
- For C2 systems satisfying the stated hypotheses, the theorem provides an admissible radius r(τ, k) and a positive inequality constant C(δ, τ, r, k).The fixed geometric parameter R is absorbed into the constant.Source: §4.2 · p. 18
- For systems in P* with condition number at most k, the corollary gives a Lojasiewicz-type inequality with a positive constant C(τ, k).In this polynomial class, the C2 norm is normalized to one and the discriminant functional is bounded below by k^-1.Source: §4.2 · pp. 19–20
5. Auxiliary Optimization Problem and Discretization
The section combines geometric results into a testing procedure, then develops auxiliary and discretized optimization problems for making that procedure tractable.
5.1. Auxiliary Optimization Problem.
- The auxiliary functional and its empirical counterpart are defined on the parametrized polynomial class using the data distribution and an i.i.d. sample.The sample consists of points drawn from the distribution under test.Source: §5.1 · p. 20
- Theorem 5.1.1 bounds the original optimization problem, provided the auxiliary problem can be solved.The procedure therefore reduces the testing task to bounding the auxiliary optimization problem.Source: §5.1 · p. 21
- Theorem 4.1.1 supplies sufficient conditions for a parametrized polynomial system to belong to the zero-set class, and those conditions can be checked on a finite discretization.The zero functional is introduced for an r-net to support this finite check.Source: §5.1 · p. 21
5.2. Discretized Optimization Problem.
- The discretized constraints test both the C2 norm and the discriminant functional on a finite net; polynomial Markov-type inequalities avoid requiring C3 data.The net radius in Proposition 5.2.1 can be chosen independently of ambient dimensions n and c.Source: §5.2 · pp. 22–23
- For a sufficiently fine net, the discretized feasible set lies between the original polynomial class and a relaxed version of it.The stated inclusions compare J_N(c,d,k) with P_n(c,d,k) and a relaxed class.Source: §5.2 · p. 24
- The discretized feasible sets are compact, and homogeneity yields comparisons between the optimal values over the two discretized sets.The compactness result ensures minimizers exist for the corresponding optimization problems.Source: §5.2 · pp. 24–25
6. Decision Procedure and Sample Complexity
Section 6 presents an effective procedure for testing whether a distribution is concentrated near a manifold in the prescribed class, and derives sample-complexity bounds for its empirical risk minimization component. Using a uniform deviation bound over the feasible set, it shows that for fixed geometric and accuracy parameters, the sample complexity grows at most polynomially with ambient dimension.
6.1. Algorithmic Decision Procedure.
- With at least m(n, l, d, k, ε, α) samples, the effective algorithm distinguishes among alternatives (A), (B), and “(A) and (B)” with probability at least 1 − α.In one case it returns a candidate with risk at most ε; in another it certifies nonexistence, and some cases yield both conclusions.Source: §6.1 · pp. 26, 31
- The testing algorithm’s sample complexity depends on k, although the statistical sample-complexity estimate for its ERM component is independent of k.The ERM accuracy must be selected using the geometric tolerance and condition-number-dependent risk comparisons.Source: §6.1 · p. 31, §6.2 · p. 32
6.2. Sample Complexity and Statistical Consistency.
- Hoeffding’s inequality and a covering argument yield the ERM sample-complexity bound through uniform deviation estimates over bounded-degree polynomial systems.The covering number is controlled by Lemma 6.2.1.Source: §6.2 · p. 32
6.2. Sample Complexity and Statistical Consistency
- A uniform deviation bound over the entire feasible set follows by combining a covering estimate with a deviation bound for the covered candidates.The result applies to sufficiently fine r-nets, with r ≤ r0(d, R), and gives probability at least 1 − α.Source: §6.2 · pp. 34–35
- Theorem 6.2.1 gives an upper bound on the sample complexity of ERM over the discretized feasible set.The bound applies when the discretization is an r-net with r ≤ r0(d, R).Source: §6.2 · p. 35
- For fixed l, d, k, ε, and α, the sample complexity grows at most polynomially in ambient dimension n.This conclusion follows by substituting the coefficient-space dimension growth for fixed degree into the sample-complexity bound.Source: §6.2 · pp. 36–37
7. Algorithmic Optimization Framework
Part II develops an algorithm for the constrained empirical-risk optimization that the testing problem reduces to. It represents polynomial systems and the optimization functionals in finite-dimensional matrix form.
Part II
- Part II supplies the algorithmic solution to the constrained empirical-risk optimization problem produced by the testing reduction.The observed sample is fixed in this part, and the empirical auxiliary cost is denoted E.Source: §7 · p. 38
7. Algorithmic Optimization Framework
- The algorithm is analyzed in an extended Blum–Shub–Smale model with exact spectral decomposition and tensor spectral-norm evaluation.The tensor evaluation cost is left abstract, and arithmetic complexity counts operations and comparisons.Source: §7 · p. 38
7.1. Matrix Representation of Polynomial Systems.
- A polynomial system is encoded by its coefficient matrix in a fixed basis, yielding finite-dimensional matrix representations of the empirical cost, discretized norm, and discriminant.The basis dimension is the dimension of the degree-at-most-d polynomial space.Source: §7 · p. 38, §7.1 · p. 39
- For degree d ≥ 1, the basis-gradient matrix has rank n everywhere, and every polynomial-system Jacobian in the basis can be represented as a coefficient matrix times that gradient matrix.The empirical cost and discriminant also admit positive-semidefinite Gram-matrix representations; the discretized norm includes second-order contributions.Source: §7.1 · pp. 38–40
8. Localized Net of Polynomial Systems
The section localizes low-cost polynomial systems near low spectral subspaces of a sample-dependent matrix, then covers these regions with nets. It extends the covering to systems satisfying relaxed admissibility constraints.
8.1. Unconstrained Optimization Problem.
- Low-cost systems lie in a tube around the subspace spanned by eigenvectors associated with the r smallest eigenvalues of the empirical matrix.The tube radius depends on the target cost and the next eigenvalue, when that eigenvalue is positive.Source: §8.1 · pp. 41–42, §8 · p. 41
- Choosing r trades the dimension of the covered subspace against the transverse radius, with stronger reduction when few eigenvalues are low and the gap above them is larger.The choice is data-dependent because the radius depends on the empirical spectrum.Source: §8.1 · p. 43
8.2. Localized Net and Theoretical Covering Reduction.
- An h-net for the localized tube has a covering bound whose metric-entropy reduction increases with both N − r and 1/ρ.The construction separates covering the low spectral component from covering the transverse quotient space.Source: §8.2 · pp. 44, 46
8.3. Constrained Optimization Problem and Admissible Localized Net.
- The covering is extended to discretely admissible systems by relaxing the condition-number constraint, with the relaxation factor tending to 1 as h tends to 0.The stability estimate requires h < 1/(2k^2).Source: §8.3 · pp. 46–47
9. Algorithm Definition and Error Control
The section defines a finite relaxed-admissible grid search over a spectrally localized region and establishes approximation, admissibility, and complexity guarantees, including detection of a nonempty low-cost feasible set by a buffered-cost grid. It also gives an asymptotic complexity bound and a constructive covering-bound case, noting that when ρ*≥1 the localized tube is the full normalized sphere.
9.1. Optimization Algorithm and Convergence.
- The algorithm selects a spectral index by minimizing a covering function, builds a relaxed-admissible grid at resolution h, and returns its minimum-empirical-cost candidate.The grid is constructed from an h-net of the localized region and filters candidates by a relaxed condition-number bound.Source: §9.1 · p. 48
- E(Uhat_h) ≤ inf_U∈I_N(c,d,k) E(U) + LEh, while K_N(Uhat_h) ≤ kΛ(h); the approximation error vanishes and the admissibility relaxation tends to 1 as h → 0.The number of evaluated candidates is bounded by φ(r*, h, ρ*).Source: §9.1 · p. 49
- A finite relaxed-admissible grid at the buffered cost level εbar + LEh detects nonemptiness of the feasible set below εbar.The lemma states the converse as well: if no grid point meets the enlarged cost level, the feasible set has no point at the original target cost.Source: §9.1 · pp. 49–50
- With the localized grid built at εbar + LEh, the theorem’s algorithm either returns EMPTY or outputs a matrix in I_N(c,d,Λ0k), and gives an arithmetic-complexity bound under its stated sample-size and parameter conditions.The bound accounts for candidate evaluation costs, including the spectral-norm computation Ttensor(n,c).Source: §9.1 · pp. 50–51
9.1. Optimization Algorithm and Convergence
- For fixed k, ε, ε̄, d≥1, and ℓ, the algorithm’s bound is stated as n→∞ and includes terms (Cd^4k)^n, n^(d+3), n^(2d+1), and T_tensor(n,c).The supplied passage gives only fragments of the displayed bound, so its full combination of terms is not recoverable here.Source: §9.1 · p. 54
- When ρ*≥1, the localized tube equals the full normalized sphere, and the text states a constructive covering bound for this case.The displayed covering-bound expression is fragmentary in the supplied passages.Source: §9.1 · p. 54
10. Arithmetic Complexity Bounds and Net Construction
The section bounds the arithmetic cost of evaluating relaxed admissibility and constructs an explicit net for the localized tube. The net matches the intrinsic dimensional exponents, with distortion controlled by norm-equivalence constants.
10.1. Auxiliary Arithmetic Complexity Bounds.
- Preprocessing the discretization matrices costs O(|N|N^2) arithmetic operations.The matrices are constructed independently for every discretization point.Source: §10.1 · p. 55
- After preprocessing, evaluating the discretized norm costs cNn^2 + c^2n + c^3 + Ttensor(n, c), where Ttensor is the tensor spectral-norm cost.The Hessian contribution requires evaluating a partially symmetric tensor spectral norm; the procedure's cost remains abstract.Source: §10.1 · p. 56
- The relaxed-admissibility test has complexity Tadm = Tnorm + Tdiscr + O(1), and combining the estimates bounds it by cNn^2 + c^2n + c^3 + Ttensor(n, c), with cNn^2 dominating cNn.Source: §10.1 · p. 57
- The tensor spectral-norm cost is left abstract: certified net discretization is possible, while iterative tensor power-type methods are typically faster but do not generally certify global optimality.Each of Nit iterations costs O(cn^2) arithmetic operations; Nit depends on accuracy and initialization.Source: §10.1 · p. 57
10.2. Explicit Net Construction.
- The constructive net separately covers longitudinal and transverse components, then radially normalizes centers to the unit sphere of the discretized norm.The norm-equivalence constants control the required Frobenius-net resolution.Source: §10.2 · pp. 57–58
- The explicit covering has the same dimensional exponents cr and c(N − r) as the intrinsic bound, with additional dependence on MN/mN.The ratio MN/mN controls the loss in the explicit net construction.Source: §10.2 · p. 57
Appendix A. Discretization of Polynomial Norms
The appendices establish dimension-independent discretization controls for polynomial norms and specify how Bernstein-basis constants affect the explicit covering construction. Markov-type derivative bounds and Chebyshev growth estimates connect net values to behavior over the full domain.
Appendix A. Discretization of Polynomial Norms
- For operator-based norms, the required discretization density depends only on degree d, not ambient dimension, and the net size grows approximately as O(dn).The argument applies a one-dimensional Markov inequality to first and second derivatives.Source: Appendix A · p. 59
- Local derivative control bounds higher derivatives using lower-order derivatives over a surrounding ball, with dependence only on degree d and radius τ.The bound is in operator norm and independent of ambient dimensions n and c.Source: Appendix A · p. 59
- A sufficiently fine r-net provides a reliable proxy for the continuous polynomial norm, with admissible radius independent of ambient dimensions n and c.The stated radius depends on η, d, l, and τ.Source: Appendix A · pp. 62–63
- Choosing the local-ball radius τ = R/d^2 yields an admissible net radius that depends polynomially on degree d and is independent of ambient dimensions.The result follows by optimizing the local radius in the discretization bound.Source: Appendix A · pp. 63–64
Appendix B. Bernstein Polynomials and Constant Bounds
- The Bernstein-basis constants affect localization and covering differently: MN controls tube radius, while MN/mN determines the explicit net's distortion loss.Both constants depend on the polynomial basis used to identify the polynomial coefficient space.Source: Appendix B · p. 64
B.1. Total-degree Bernstein polynomial basis.
This section defines the total-degree Bernstein basis on a regular simplex and estimates how its coefficient norm compares with polynomial-system norms. With the simplex chosen to contain the target ball, the coefficient-to-C2 comparison approaches one as the ambient dimension grows, for fixed degree and radius.
B.1. Total-degree Bernstein polynomial basis.
- The total-degree Bernstein polynomials form a basis for polynomials of degree at most d, defined using barycentric coordinates on a regular simplex.The simplex is chosen large enough to contain D_R; the stated sufficient condition is L ≥ nR.Source: §B.1 · pp. 64–65
- The section establishes an upper comparison between the polynomial system's C2 norm and its Bernstein coefficient Frobenius norm.The estimate is made for a simplex containing D_R, with the simplex size constrained by L ≥ nR.Source: §B.1 · pp. 65, 67
- For fixed d and R, the Bernstein coefficient-to-C2 comparison tends to 1 as n grows.The section states that this comparison becomes arbitrarily close to the constant one asymptotically in ambient dimension.Source: §B.1 · p. 67
B.2. Inverse Bernstein Norm Estimate.
The inverse estimate uses the fact that each Bernstein coefficient is determined on a face of dimension at most d − 1. This yields a finite coefficient-to-supremum comparison independent of ambient and target dimensions, while the section also establishes limits on dimension-independent lower bounds.
B.2. Inverse Bernstein Norm Estimate.
- Each degree-d Bernstein coefficient can be recovered from the polynomial's restriction to a face of dimension at most d − 1.The argument uses that a coefficient's multi-index has support of size at most d.Source: §B.2 · p. 68
- The inverse Bernstein comparison constant κ_d is finite and independent of ambient dimension n and target dimension c.It is obtained by taking the maximum of the finite-dimensional constants for faces of dimension at most d − 1.Source: §B.2 · p. 69
- For fixed degree, the inverse norm-comparison constant has at most polynomial deterioration with ambient dimension, but no dimension-independent positive lower bound holds in general.The impossibility already occurs for degree one.Source: §B.2 · p. 71
- The degree-one obstruction is exhibited by systems with coefficient Frobenius norm 1 and the minimal simplex size L = nR.The passage states that this sequence rules out a dimension-independent positive lower bound for m_N.Source: §B.2 · p. 71
Appendix C. Lipschitz Stability Estimates
This appendix establishes stability estimates for quantities used in the data-driven procedure. In particular, it gives Lipschitz control of the empirical cost on a net and of the discretized discriminant under perturbations.
Appendix C. Lipschitz Stability Estimates
- On the normalized coefficient sphere, the empirical cost is Lipschitz in the discretized norm, with constant 2 for its squared values.The estimate is stated when N is an r-net of the target ball.Source: Appendix C · pp. 72–73
- The empirical-cost estimate applies to observed data points by assigning each point a nearby net point and using the mean value estimate.The setup assumes N is an r-net of the target ball.Source: Appendix C · p. 73
- The discretized discriminant has controlled variation under perturbations measured in the discretized norm.The appendix records this stability on the normalized sphere.Source: Appendix C · p. 73