When can optimality certificates be obtained for broad learning problems

When Can One Obtain Certificates of Optimality Using Positivstellensaetze?

Artificial Intelligence

Summary

Many learning tasks need ways to prove that a solution is truly the best, but these tasks often involve complicated functions not just simple polynomials. The authors study a general mathematical framework that isolates key properties needed to construct such proofs, called certificates of optimality, even when the functions are complex and the underlying number systems lack some usual operations. They show how these certificates can still be built under very general conditions and analyze what influences their complexity. This helps understand when and how guarantees about best solutions can be reliably generated beyond standard polynomial cases.

What this means in practice

  • For optimization software engineers: Develop optimization tools that generate proofs of solution optimality for complex objective and constraint functions beyond polynomials.
  • For control systems designers: Use generalized positivity certificates to verify global optimality conditions in systems with non-polynomial performance criteria.

A theory result. No direct application yet.

Authors

Nayoon Kim, Allen Gehret, Shenyuan Ma, Jakub Marecek

Abstract

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.
View PDFOpen arXiv