PaperlayerView exact revision on arXiv

Source-linked AI summary

When Can One Obtain Certificates of Optimality Using Positivstellensaetze?

Nayoon Kim, Allen Gehret, Shenyuan Ma, Jakub Marecek

arXiv:2609.08736v1cs.AI

TL;DR

The paper addresses how to obtain explicit positivity and optimality certificates when learning objectives and constraints are not necessarily polynomial. It axiomatizes Fischer’s constructive strict and weak Positivstellensätze for abstract function algebras over ordered fields, separating broad objective and constraint functions from certificate-building primitives. The resulting framework covers continuous and definable examples, ordered fields without square roots, neural-network optimality certificates, and distinct expanded-term and shared-graph complexity bounds.

  • Problem

    Existing optimality certificates often depend on smoothness, semialgebraicity, or real-closed scalar fields, limiting explicit certification across learning problems and ordered fields.

  • Method

    The paper extracts Fischer’s constructive strict and weak Positivstellensätze into scalar and function-algebra axioms, then verifies the axioms in continuous, definable, and non-real-closed examples.

  • Results

    The framework yields lower-bound and global-optimality certificates for neural-network objectives and constraints, with shared certificate graphs of size O(k) and depth O(log(k + 1)) for k constraints.

  • Takeaways & Limitations

    Certificate construction can be reused across suitable function algebras and ordered fields by verifying explicit axioms, while separating certificate primitives from the network’s activation functions.

  • Takeaways & Limitations

    The complexity bounds concern explicit certificate construction and do not establish efficient certificate discovery or polynomial-time solutions to the associated optimization problems.

Abstract

from arXiv · show

We study certificates of positivity and optimality for learning problems whose objectives and constraints need not be polynomial. We isolate an axiomatic core of Fischer's constructive strict and weak Positivstellensätze and prove the resulting theorems for abstract function algebras over ordered fields. The framework separates two roles that can otherwise be conflated: objective and constraint functions may be built from broad classes of continuous or definable operations, while the auxiliary primitives used to construct a certificate satisfy explicit scalar and closure axioms. We give instances over continuous and definable function algebras, including ordered fields not closed under square roots, derive lower-bound and global-optimality certificates, and analyze both expanded term length and shared computation-graph complexity.

1. Introduction

The paper asks how to construct explicit optimality certificates for learning problems beyond standard smooth or semialgebraic settings. It extracts Fischer’s construction into an axiomatic framework covering broader function algebras, ordered fields, and neural-network applications.

  • Motivation: Neural-network activations expose a gap between smooth non-semialgebraic functions such as sigmoid and semialgebraic nonsmooth functions such as ReLU.Many existing certificates rely on either semialgebraicity or smoothness.
  • Research question: The paper focuses on explicit algebraic certificates for deep-learning problems and on how to construct them effectively.Classical Positivstellensätze often contain nonconstructive steps, whereas Fischer’s differentiable-function result provides an explicit structure for axiomatization.
  • Limitations addressed: The framework addresses two limitations of Fischer’s formulation: its presentation is tied to definable C^r-functions, and its construction relies heavily on real-closed scalar fields.The second limitation arises because the auxiliary functions are defined using square roots, which arbitrary ordered fields may not support.
  • Contributions: The paper states strict and weak Positivstellensätze, verifies examples over fields without square roots, and applies the results to neural-network optimality certificates.The examples include Q-valued continuous functions and variants of common activation functions.
  • Organization: The appendices provide universal terms, proof architectures, function-algebra verification, and exact term-length and shared-graph complexity analyses.These materials organize the construction and its complexity bounds by mathematical role.

2. Background

The background develops positivity certificates from polynomial preorderings and places the paper’s approach within extensions to continuous and definable function algebras. The paper formulates Fischer’s explicit construction through scalar and function-algebra axioms whose resulting terms are instance-independent.

  • Polynomial origins: Sums of squares motivate positivity certificates, but nonnegative polynomials need not themselves be sums of squares; rational-function representations resolve Hilbert’s seventeenth problem.This establishes the broader role of algebraic witnesses for nonnegativity.
  • Polynomial certificates: A preordering generated by constraint polynomials contains squares and constraints and is closed under addition and multiplication, so its elements witness nonnegativity on the feasible set.Classical Positivstellensätze produce such witnesses or related certificates.
  • Classical Positivstellensätze: Krivine–Stengle, Schmüdgen, and Putinar provide increasingly structured polynomial positivity certificates under differing assumptions such as compactness and Archimedeanity.Krivine–Stengle uses a preordering multiplier, while Schmüdgen removes the multiplier under compactness and Putinar uses an Archimedean quadratic module.
  • Nonpolynomial settings: Beyond polynomial rings, prior work established Positivstellensätze for continuous functions and definable C^r-functions, while Fischer supplied an explicit finite construction with uniform definability and variants.The present paper builds on this constructive line while changing the formal setting.
  • Axiomatic framework: The paper recasts Fischer’s construction using scalar and function-algebra axioms, making the resulting terms independent of the particular function algebra and scalar field.Only verification of the axioms depends on the chosen instance.

3. Setup

The setup abstracts function-algebra constructions over ordered-field scalars, combining closure axioms with auxiliary primitives that support the later Positivstellensätze. It includes continuous-function examples, polynomial non-examples, and scalar theories encoding positivity, partial inversion, activation, domination, and max-like behavior.

  • Abstract setting: The framework treats X as an arbitrary set, ordered-field structure R as scalars, and A as a collection of R-valued functions with specified closure properties.The language formulation makes the later theorems independent of any particular function algebra.
  • Abstract setting: Term interpretations act pointwise: an L-term t applied to functions f1,...,fn produces the function x ↦ t^R(f1(x),...,fn(x)).This provides a uniform way to construct functions from scalar-language operations.
  • Function-algebra axioms: The baseline algebra axioms require constants 0 and 1, additive inverses, addition, multiplication, and, for strict results, inverses of everywhere-positive functions.The main continuous-function example C0(U,R) satisfies these axioms, whereas polynomial rings satisfy the ring axioms but generally fail inverse closure.
  • Function-algebra axioms: Polynomial rings fail the inverse-closure axiom because 1 + X1^2 + ··· + Xn^2 is everywhere positive but its reciprocal is not polynomial, so the strict theorem does not apply.The weak theorem also fails for this choice of algebra, as established later in the cited setup discussion.
  • Scalar theories: The scalar languages add σ for nonnegative outputs, ρ as a partial inverse of σ, ξ as a positive-part or activation function, δ as a positive dominating function, and ν as a max-like proxy.Examples include squares, square roots, ReLU, exponential activation, and max-like formulas.
  • Scalar theories: The weak scalar theory constrains ξ, σ, and ρ, while the stronger theory additionally requires ν to be positive when either input is positive and bounded by its second input in the specified mixed-sign case.The concrete real structure from Main Example 3.5 satisfies both scalar theories.

4. Main results

The paper proves strict and weak Positivstellensätze for abstract function algebras under explicit ordered-field and closure axioms, with terms uniform across algebras and scalar fields. The results yield strictly positive or nonnegative certificate functions, while examples show both applicability to continuous-function algebras and limitations for polynomial algebras.

  • Strict Positivstellensatz: The Strict Positivstellensatz supplies universal terms whose evaluations are strictly positive and produce certificates whenever the strict axioms hold.The terms are independent of the particular ordered field, function algebra, and input functions; only axiom verification depends on the instance.
  • Proof strategy: The strict proof compresses all constraints into one function, then uses sign-case analysis in the objective and compressed constraint to construct the certificate.The ξ-terms distinguish sign cases, and the resulting functions are combined with the representation of the compressed constraint.
  • Examples: The continuous-function algebra C0(U, R) satisfies both the strict and weak axiom systems, providing a principal nonpolynomial instance of the theorems.The framework also gives a non-Archimedean weak example that does not satisfy inverse closure (A1).
  • Weak Positivstellensatz: The Weak Positivstellensatz provides universal terms under weaker closure axioms, producing nonnegative certificate functions and an additional nonnegative function satisfying the weak certificate relation.Unlike the strict axioms, the weak axioms do not require closure under inverses of all everywhere-positive functions.
  • Limitations: The polynomial algebra R[X1, ..., Xn] cannot satisfy the required activation-closure axiom, so neither the weak theorem nor its certificate construction applies there.Applying closure to X1 would force the activation function to agree everywhere with a polynomial, contradicting the activation axioms.

5. Examples

The paper instantiates its axiomatic Positivstellensätze with continuous and definable function algebras, flexible primitive choices, activation-function variants, and an exact rational model over Q.

  • Axiomatic instances: Arbitrary scalar primitives satisfying TwP and TsP yield a definable-function algebra satisfying the strict and weak Positivstellensatz axioms.Closure under composition supplies the required algebra axioms.
  • Axiomatic instances: The framework permits discontinuous primitive choices, but this formal freedom requires working in the full definable-function algebra.The construction does not restrict primitives to continuous operations.
  • Activation variants: ReLU^α satisfies the strict conditions for every α > 0, while the weak condition additionally requires α > 1.For α ∈ (0, 1], the weak condition fails.
  • Activation variants: GELU, sigmoid, and softplus provide alternative choices of ξ within the activation-function examples.These choices are considered alongside power gates and a general construction from increasing functions.
  • Rational model: The construction extends to continuous functions over the ordered field Q, which is not real closed and lacks general square roots.The resulting model uses exact rational arithmetic rather than floating-point or fixed-point semantics.

6. Optimality certificates and an application to neural networks

The Positivstellensätze reformulate lower bounds and global optimality as algebraic certificates, including certificates for neural-network training and an exact rational example.

  • Certificate reformulation: Strict certificates are equivalent to a positive margin above a lower bound, while weak certificates are equivalent to nonnegativity over the feasible region.The strict construction uses strictly positive certificate functions; the weak construction uses nonnegative functions and a multiplier p.
  • Certificate reformulation: A feasible point is a global minimizer exactly when the weak certificate holds with L equal to its objective value.The certificate also identifies the zero set of the multiplier with the objective-level set.
  • Neural-network application: For continuous neural networks, the ambient algebra C0(R^n, R) supplies certificates for empirical risk minimization with pairwise output-consistency constraints.The auxiliary certificate primitives need not be the network’s activation functions.
  • Neural-network application: The universal certificate terms can be instantiated uniformly by substituting the objective gap and constraint functions into the Positivstellensatz terms.For strict lower bounds, the construction uses an η satisfying L + η < infθ∈F g(θ).
  • Rational example: Over Q, the weak construction certifies that x⋆ = 1 globally minimizes Q(x) subject to x − 1 ≥ 0.The certificate establishes Q(x) ≥ 1 on the feasible set, while x⋆ attains value 1.

7. Complexity analysis

The complexity analysis distinguishes expanded expression length from shared evaluation graphs: explicit terms can be polynomially large, while shared computation is linear-size and logarithmic-depth.

  • Shared computation graphs: Under shared straight-line evaluation, either universal certificate has graph size O(k) and depth O(log(k + 1)).Identical subexpressions are represented once, with fan-out free and scalar primitives assigned unit cost.
  • Shared computation graphs: When input functions have total graph size S and maximum depth D, composition yields size S + O(k) and depth D + O(log(k + 1)).The bound applies to the composed certificate graph.
  • Scope of complexity claims: The graph bounds concern evaluating fixed universal terms and do not provide smaller equivalent terms, equality decisions, or polynomial-time optimization algorithms.The associated optimization problems can remain NP-hard, including local-minimality questions for constrained indefinite quadratic programs.

8. Conclusions

The paper extracts Fischer’s construction into reusable scalar and function-algebra axioms, derives universal strict and weak certificates, and clarifies both their computational representation and unresolved scope.

  • Contributions: The extracted framework makes certificate terms independent of the particular function algebra and scalar field, while axiom verification remains instance-specific.The strict and weak constructions are universal once the required axioms hold.
  • Contributions: The constructions cover ordered fields that are not real closed, exact rational arithmetic, and variants of standard neural-network activation functions.These examples extend beyond Fischer’s real-closed-field setting.
  • Open questions and scope: The paper leaves open coverage of R[X], a separation question for weak axioms, and analogous constructions in the noncommutative setting.It also distinguishes explicit certificate evaluation from certificate discovery and optimization complexity.
  • Construction architecture: Both constructions first compress constraints into one auxiliary function and then use shared sign-gate stages to produce certificate terms.The strict and weak dependency pipelines differ after the common sign geometry stage.
  • Construction architecture: The closure axioms are used at specific construction stages, including violated-constraint detection, sign-region gluing, regularization, and Hilbert–17 factorizations.Other construction steps use only ring operations.

A.5. Scalar consequences and pathologies for σ and ρ.

The scalar axioms force several basic identities and positivity properties, but they do not determine standard regularity or invertibility behavior. An explicit construction realizes extreme pathologies for σ and ρ on every positive interval.

  • Scalar consequences: The axioms imply σ(1)=1, ρ(0)=σ(0)=0, and positivity of σ(a) and ρ(a) for every a>0.They also imply injectivity of ρ on [0,+∞) and surjectivity of σ onto [0,+∞).
  • Scalar consequences: The axioms do not determine whether ρ is surjective, σ is injective, or either function is monotone on [0,+∞).These properties therefore require additional assumptions beyond TwP.
  • Pathological construction: Transferring L and M through logarithm and exponential yields σ and ρ satisfying the scalar axioms while exhibiting the stated pathologies.The construction uses the Axiom of Choice and preserves the required multiplicative and inverse relations.
  • Pathological construction: Using a Q-linear isomorphism, the construction produces additive maps L and M with L∘M=id_R, while L is surjective noninjective and M injective nonsurjective.Both maps are discontinuous and hence nonmonotone on every nonempty interval.
  • Pathological construction: On every interval (a,b)⊆[0,+∞), ρ is not surjective, σ is not injective, and neither σ nor ρ is monotone.Noninjectivity follows from a nonzero element of ker(L), while nonmonotonicity transfers from L and M.

Appendix B. Proof of the strict Positivstellensatz

The strict Positivstellensatz proof reconstructs Fischer’s construction within an axiomatic function algebra. It builds auxiliary functions whose sign properties culminate in a strictly positive certificate satisfying the required algebraic relations.

  • Construction strategy: The proof constructs a sequence of functions in the algebra while checking Fischer’s strict construction against the abstract scalar and closure axioms.The setup fixes a model, an algebra, and constraint functions satisfying the strict assumptions.
  • Constraint compression: The first construction forms ψ≤0 and positive ε_i, then defines positive s_i through ρ(ξ(−f_i)+ε_i).On {g≤0}, the ε_i satisfy ε_i f_i<−ψ/k, providing the key sign control.
  • Constraint compression: The function h belongs to the algebra and separates feasible and violating regions through {h≥0}⊆{g>0}.It is nonnegative on the constraint-feasible set and negative wherever g≤0.
  • Strict certificate: The construction defines φ from three ξ-transformed sign expressions and proves φ>0 everywhere, then defines ε=ν(g,φ)·(δ(f))−1.The resulting ε lies in the algebra, is strictly positive, and satisfies ε·f<φ on {g≤0}.
  • Strict certificate: The final auxiliary functions u and t_i remain in the algebra and are strictly positive, with σ(t_i)=wσ(s_i) for i≥1.These identities complete the algebraic certificate construction under the strict axioms.

Appendix C. Proof of the weak Positivstellensatz

The weak Positivstellensatz uses a parallel axiomatic construction without requiring reciprocal closure for every positive function. It builds nonnegative auxiliary functions whose zero sets encode the target sign conditions.

  • Construction strategy: The weak proof follows the strict construction’s pattern while checking each term in the weaker function-algebra axioms.The weak package omits closure under inverses of all everywhere-positive functions.
  • Constraint compression: The function h belongs to the algebra, satisfies h≤0, and has zero set F={h=0}⊆{g≥0}.Its zero set captures the region where every f_i is nonnegative.
  • Sign encoding: The functions φ_1, φ_2, φ_3 and φ are nonnegative, and {φ=0}={g=0}∩{h=0}.Their sign regions encode the relevant combinations of g and h.
  • Zero-set encoding: The function q is nonnegative and satisfies {q=0}={g=0}, providing a nonnegative algebra element whose zeros exactly track g’s zeros.Its construction multiplies φ, ξ(g^2), and additional nonnegative ξ-terms.
  • Weak certificate: The final function ω belongs to the algebra, is nonnegative, vanishes exactly where g vanishes, and satisfies an additional property away from {g=0}.The paper avoids directly defining an auxiliary w because that function is not guaranteed to belong to the algebra.
  • Axiom boundary: The weak axioms do not imply reciprocal closure: a model, domain, and function ring can satisfy (AwP) while failing (A1).A positive infinitesimal ε belongs to the ring while ε^−1 does not.

D.1. Arbitrary definable primitives.

The definable-function setting supports the abstract axioms whenever the scalar primitives are named and the algebra contains all definable functions. This permits broad, including discontinuous, primitive choices.

  • Definable algebras: For a nonempty definable set X, the collection of all definable functions X→R satisfies the strict and weak algebra axioms.Closure follows because required expressions remain definable under named scalar primitives and ordered-field operations.
  • Primitive choices: The framework permits any primitive choices satisfying the scalar theories, including discontinuous choices such as the binary step function for ξ.The algebra is the full definable-function algebra in the expanded structure.
  • Primitive choices: In o-minimal expansions, every definable function is piecewise C^r for each fixed r, while discontinuous definable primitives remain permitted.This combines piecewise regularity of definable functions with the allowed expanded scalar primitives.
  • Definable algebras: In the maximal expansion naming every subset of every finite Cartesian power of R, every function X→R is definable, so A=R^X.This gives the largest function-algebra instance described in the section.

D.2. Continuous-function algebras.

The continuous-function setting reduces algebra closure to continuity of scalar auxiliary primitives and composition. Under explicit continuity and asymptotic conditions, C0(X,R) satisfies the strict and weak Positivstellensatz axioms.

  • Continuous-function algebras: Corollaries D.6 and D.11 provide sufficient continuity conditions for the auxiliary primitives in C0(X,R).These conditions yield Proposition 5.2 when R=R and X is an open subset of R^n.
  • Continuous-function algebras: Composition with continuous scalar maps preserves C0(X,R), enabling closure under the algebra’s primitive operations.The closure verification applies continuity of arithmetic, inversion on nonzero values, and the designated auxiliary functions.
  • Boundary continuity: Continuity of Ψξ and Φξ at their singular boundary points is equivalent to ξ(t) ≺ t at 0+.Away from the relevant singular points, continuity follows from ordinary continuity and inversion.
  • Axiomatic consequences: The resulting continuous algebras satisfy both strict and weak axioms, including over the ordered field models R and Q.The stated corollaries cover C0(U,R), C0(X,R), and C0(X,Q), alongside corresponding scalar structures.

D.5. Fischer’s definable Cr setting.

The definable Cr setting instantiates the axiomatic framework over definably complete ordered fields, using auxiliary functions whose regularity supports algebra closure. It recovers Fischer’s strict and weak definable Positivstellensätze with fiberwise definable Cr certificates.

  • Setting: The construction works over a definably complete L-expansion of R, with a smooth exponential additionally required when r=∞.The function algebra consists of definable Cr functions on a definable Cr-manifold M.
  • Strict certificates: Fischer’s strict theorem yields strictly positive definable Cr certificate functions under gs > 0 on Fs.The certificates are constructed by substituting the universal axiomatic terms into gs and the constraint functions.
  • Weak certificates: The weak theorem similarly yields definable Cr certificate families and a function ps whose zero set is contained in the zero set of gs.The framework’s construction gives the stronger inclusion stated for every parameter s.
  • Auxiliary primitives: The selected auxiliary functions are definable and satisfy the scalar strict and weak Positivstellensatz axioms.Their regularity is established through finite-order or flatness estimates at zero sets.
  • Function-algebra closure: The algebra A of definable Cr functions satisfies both (AsP) and (AwP).Closure follows from standard calculus together with the regularity lemma for the auxiliary constructions.

E.1. Expanded term length.

Expanded certificate expressions are analyzed by recursive term-length rules, while shared computation graphs expose substantially smaller universal constructions. The graph model gives linear size and logarithmic depth in the number of constraints.

  • Expanded term length: Recursive unique-readability rules define expanded term length, with unary operations adding one node and binary operations combining argument lengths.These rules generate the intermediate strict and weak lengths reported in Tables 1 and 2.
  • Shared computation graphs: A shared straight-line computation graph represents identical subexpressions once and shares their outputs across all certificate computations.The cost model counts primitive applications as nodes and permits arbitrary reuse of node values.
  • Shared computation graphs: The strict and weak constructions both have graph size O(k) and depth O(log(k + 1)).With jointly represented inputs of size S and depth D, the totals become S + O(k) and D + O(log(k + 1)).
  • Expanded term length: For k = 1, the strict right-hand side has formal length 579, while the weak left- and right-hand sides have lengths 999 and 2726.These values describe the particular universal constructions and are not lower bounds for all certificates.
  • Expanded term length: For k = 2, the corresponding formal lengths are 2003 for the strict right-hand side and 1531 and 6217 for the weak sides.The reported values likewise concern the constructions analyzed in the paper.
Loading 2609.08736v1…