Learning Regularization-Aware Sum-of-Squares Certificates

Certifying polynomial nonnegativity is a fundamental computational problem arising in nonconvex optimization, control, robotics, and polynomial systems. A widely used sufficient certificate is the sum-of-squares (SOS) property, which can be verified through semidefinite programming (SDP). In practice, however, SOS verification remains expensive: the dimension of the associated Gram matrix grows rapidly with the number of monomials retained in the certificate, making the choice of SOS representation a central computational bottleneck. Recent theory has shown that regularization can fundamentally alter the algebraic structure of polynomial optimization problems. In particular, sufficiently strong Euclidean regularization can induce exact SOS certificates even for nonconvex regularized polynomial models \citep{cartis2026sufficiently}. Building on this observation, we introduce a regularization-aware learning-augmented framework for SOS certification. Rather than treating the input polynomial as an unstructured collection of monomials, we exploit the provenance of its terms---the radial regularizer, Taylor tensors, curvature, and support structure---and learn the smallest theoretically admissible reduced SOS cone likely to certify each instance. Our methodology has three components. First, we generate and solve structured regularized polynomial instances across dimensions, degrees, regularization strengths, Hessian spectra, and sparse-to-dense tensor-support patterns. Second, we derive a theory-guided hierarchy of reduced SOS cones and train a lightweight two-stage learner using structural features motivated directly by this hierarchy. Because the theoretical construction reduces the prediction problem from combinatorial monomial search to a small number of structured cone and routing decisions, our preliminary models are trained on only approximately (1.8)k solved instances. Third, we embed the learned prediction in a propose--verify--fallback procedure: every proposed cone is verified by an SDP, and failed proposals are deterministically expanded through the theoretically justified hierarchy until a certificate is found or the full SOS problem is reached. Learning therefore affects computational efficiency, but not correctness. Preliminary experiments show substantial reductions over generic SOS sparsity methods. In sparse high-order models, the Gram-size advantage over TSSOS grows with the regularization degree, reaching approximately (10.7\times) at (d=5,n=10). On AR(3) subproblems, preliminary solve-time tests show speedups of up to (43\times) in dense instances, while real optimization tests achieve up to (3\times) lower per-subproblem cost at identical outer convergence. The learned selector achieves (0.84) five-fold cross-validated accuracy against a (0.43) majority baseline, and feature analysis identifies the regularization-dominance ratio [ Rj=\frac{\sigma}{2d|Tj|} ] as the strongest predictor of the smallest tight cone. Beyond computational acceleration, this provides a data-driven structural insight: SOS certifiability is governed not by sparsity alone, but by the interaction between regularization strength, curvature, and tensor structure. Our results suggest a broader direction for theory-guided, learning-augmented SOS programming, in which algebraic theory defines a safe family of certificates and machine learning identifies the smallest certificate appropriate for each instance.