Sparse Sum-of-Squares Layers for Certified Learning

Ege Gursoy; Nicolas Mansard

cs.LGOct 25, 2026

Sparse Sum-of-Squares Layers for Certified Learning

Authors: Ege Gursoy, Nicolas Mansard

Organizations: LAAS-CNRS · ANITI

Abstract

A central limitation of modern machine learning systems is the lack of formal certificates guaranteeing their behavior beyond empirical, sample-based evaluation. Sum-of-squares (SOS) methods provide such guarantees by certifying polynomial inequalities over continuous domains via semidefinite programming (SDP). While prior work has introduced SDP layers as differentiable components in neural networks, repeated learning calls can lose the computational benefit of the forward program's sparse representation. We propose Sparse SOS Layers, differentiable value layers whose backward passes reuse the local coordinates of the forward solve. Under a fixed template and learned objective coefficients, each layer avoids building dense certificates and reuses its sparse structure across training steps. Compared with existing methods, our approach achieves up to 2.7 times speedup in total warm-call time, with nearly 100 times lower memory usage (1.7 vs. 160 GiB) for relatively large problem sizes for the tested dense parameterization. Experiments cover sparse polynomial certification, pendulum control, combinatorial relaxations, robotics projection, oscillator chains, and pose graph synchronization. A design study achieves zero certified violations across unseen problem instances and sizes, while requiring roughly 7 times fewer optimization solves than estimating gradients by perturbing the objective coefficients and re-solving the problem (finite differences). These results show that sparse certificate values can be effectively integrated into learning pipelines when the backward pass respects the verifier's structure.

Figures & tables

Comparison	Size	Reference	Sparse value route
Generic / value-specialized	$N=16$	28.851 [0.094]	17.839 [0.080]
Generic / value-specialized	$N=128$	520.488 [1.550]	196.259 [0.831]
Ambient / chordal	$N=16$	1.414 [0.003]	3.263 [0.006]
Rebuilt / cached	$N=16$	5.893 [0.056]	4.431 [0.048]
Rebuilt / cached	$N=256$	99.040 [5.165]	72.820 [0.754]

Table 1: Controlled total warm-call times, median [interquartile range] in milliseconds.

Implementation	Peak memory (GiB)	Forward (s)	Backward (s)
Dense parameterization	164.07	4161	203.6
Sparse SOS (Ours)	1.69	0.154	0.265

Table 2: Resource measurements at

N=384

$N$	Sparse SOS (Ours)	Dense CVXPY	Dense SDPR
96	$3.67\times 10^{-5}$	$2.00\times 10^{-2}$	$1.07\times 10^{-2}$
128	$1.88\times 10^{-4}$	$8.18\times 10^{-1}$	$5.19\times 10^{-1}$
192	$2.06\times 10^{-5}$	$2.46\times 10^{-1}$	$1.96\times 10^{-1}$
256	$3.20\times 10^{-5}$	$2.70\times 10^{-2}$	$4.06\times 10^{-1}$
384	$1.49\times 10^{-5}$	Not tested	Not tested
512	$1.26\times 10^{-5}$	Not tested	Not tested

Table 3: Minimum relative derivative error over three finite-difference step sizes at

\rho=0.45

. Qualification uses the complete record and the absolute-or-relative criterion. All reported primal statuses are optimal.

Family	Width $w$	Size $n$	Median ratio	[Q1, Q3]
Banded	4	96	1.068	[1.063, 1.070]
Random chordal	4	96	1.076	[1.038, 1.139]
Random chordal	6	160	1.057	[1.038, 1.070]
Random chordal	8	224	1.047	[0.999, 1.104]

Table 4: First tested size with median ambient/chordal time ratio above one.

Segments	Objective discrepancy	Gradient discrepancy
8	$6.80\times 10^{-4}$	$5.17\times 10^{-4}$
9	$2.93\times 10^{-3}$	$1.34\times 10^{-4}$
10	$1.50\times 10^{-4}$	$1.77\times 10^{-3}$
11	$1.68\times 10^{-3}$	$1.68\times 10^{-3}$

Table 5: Robot projection: relative discrepancies against SDPR on the matched Shor relaxation.

$N$	Certificate value		Gradient value
$N$	Sparse SOS (Ours)	CVXPY	Sparse SOS (Ours)	CVXPY
$4$	$0.072584$	$0.072584$	$-0.242536$	$-0.242536$
$6$	$0.108876$	$0.108876$	$-0.363803$	$-0.363803$
$8$	$0.145168$	$0.145168$	$-0.485071$	$-0.485071$

Table 6: Coupled oscillator certificate values and gradients for the same multiplier SOS program.

Poses	Forward time (s)			Backward time (s)
	Sparse SOS (Ours)	CVXPY	SDPR	Sparse SOS (Ours)	CVXPY	SDPR
$10$	$0.019$	$0.027$	$\mathbf{0.011}$	$\mathbf{4.72\!\cdot\!10^{-4}}$	$4.17\!\cdot\!10^{-3}$	$2.57\!\cdot\!10^{-3}$
$16$	$0.023$	$0.094$	$\mathbf{0.016}$	$\mathbf{1.12\!\cdot\!10^{-3}}$	$0.026$	$5.36\!\cdot\!10^{-3}$
$22$	$0.029$	$0.171$	$\mathbf{0.022}$	$\mathbf{2.66\!\cdot\!10^{-3}}$	$0.063$	$9.80\!\cdot\!10^{-3}$
$28$	$0.034$	$11.24$	$\mathbf{0.031}$	$\mathbf{3.41\!\cdot\!10^{-3}}$	$0.130$	$0.015$

Table 7: Pose graph synchronization: implementation-level times in seconds.

Pendulum	Method	Training signal	Cert. margin	Cert. rate
1	Sparse SOS (Ours)	certificate margin	$\mathbf{0.0274\pm 0.0014}$	1.000
1	Sampled surrogate	sampled grid loss	$0.0234\pm 0.0013$	1.000
1	Post hoc	no certificate during training	$-0.7957\pm 0.7453$	0.200
2	Sparse SOS (Ours)	certificate margin	$\mathbf{0.0036\pm 0.0002}$	1.000
2	Sampled surrogate	sampled grid loss	$0.0024\pm 0.0002$	1.000
2	Post hoc	no certificate during training	$0.0019\pm 0.0004$	1.000

Table 8: Pendulum control certificate outcomes.

Training signal	Train	Test	$n=96$	$n=160$	Solves
Sparse SOS (Ours)	0/80	0/30	0/20	0/30	480
Finite differences	4/80	0/30	4/20	6/30	3360
Sampled surrogate	9/80	4/30	5/20	12/30	0
Stop gradient	80/80	30/30	20/20	30/30	480
No layer	80/80	30/30	20/20	30/30	0

Table 9: Violations of the certified lower-bound requirement.

Layer choice	Final test loss	Forward total (s)	Backward total (s)	Time-to- $10^{-3}$ (s)
Sparse SOS (Ours)	$\mathbf{1.06\!\cdot\!10^{-7}}$	32.93	5.37	22.28
SDPR	$3.78\!\cdot\!10^{-5}$	20.67	268.33	71.94
CVXPY	$3.66\!\cdot\!10^{-5}$	2023.60	361.12	594.36

Table 10: Training loop case study at problem size

96

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

$N$	Objective value			Gradient value
$N$	Sparse SOS (Ours)	CVXPY	SDPR	Sparse SOS (Ours)	CVXPY	SDPR
$16$	$-15.213$	$-15.213$	$-15.213$	$-0.0131$	$-0.0131$	$-0.0131$
$32$	$-31.424$	$-31.424$	$-31.424$	$-0.0209$	$-0.0209$	$-0.0209$
$48$	$-47.367$	$-47.367$	$-47.367$	$-5.575\!\cdot\!10^{-3}$	$-5.596\!\cdot\!10^{-3}$	$-5.569\!\cdot\!10^{-3}$
$64$	$-63.118$	$-63.118$	$-63.118$	$0.0197$	$0.0198$	$0.0197$
$96$	$-95.154$	$-95.154$	$-95.154$	$0.0412$	$0.0422$	$0.0418$

Appendix

Table 11: Banded binary optimization quality check.

Segments	Objective value			Gradient value
Segments	Sparse SOS (Ours)	CVXPY	SDPR	Sparse SOS (Ours)	CVXPY	SDPR
$8$	$1.322\!\cdot\!10^{-3}$	$1.367\!\cdot\!10^{-3}$	$1.299\!\cdot\!10^{-3}$	$3.235\!\cdot\!10^{-3}$	$3.498\!\cdot\!10^{-3}$	$3.206\!\cdot\!10^{-3}$
$9$	$7.619\!\cdot\!10^{-4}$	$7.649\!\cdot\!10^{-4}$	$7.451\!\cdot\!10^{-4}$	$2.931\!\cdot\!10^{-3}$	$3.002\!\cdot\!10^{-3}$	$2.882\!\cdot\!10^{-3}$
$10$	$7.818\!\cdot\!10^{-4}$	$7.897\!\cdot\!10^{-4}$	$7.592\!\cdot\!10^{-4}$	$3.074\!\cdot\!10^{-3}$	$3.245\!\cdot\!10^{-3}$	$2.990\!\cdot\!10^{-3}$
$11$	$7.959\!\cdot\!10^{-4}$	$8.026\!\cdot\!10^{-4}$	$7.702\!\cdot\!10^{-4}$	$3.085\!\cdot\!10^{-3}$	$3.217\!\cdot\!10^{-3}$	$2.976\!\cdot\!10^{-3}$

Appendix

Table 12: Continuum robot shape projection quality check for the generic sparse SOS implementation.

Poses	Objective value			Gradient value
Poses	Sparse SOS (Ours)	CVXPY	SDPR	Sparse SOS (Ours)	CVXPY	SDPR
$10$	$-0.253278$	$-0.253278$	$-0.253278$	$-5.197106$	$-5.197109$	$-5.197106$
$16$	$-0.401243$	$-0.401243$	$-0.401243$	$-8.269580$	$-8.269584$	$-8.269580$
$22$	$-0.543913$	$-0.543927$	$-0.543914$	$-11.201$	$-11.201$	$-11.201$
$28$	$-0.694724$	$-0.694726$	$-0.694726$	$-14.299$	$-14.299$	$-14.299$

Appendix

Table 13: Pose graph synchronization quality check.

Seg.	Status rate		Agreement vs. SDPR		Time (s)		Chordal structure
Seg.	Usable	Strict	Obj. rel.	Grad. rel.	Forward	Backward	Cliques	Max clique
$8$	$1.0$	$1.0$	$6.80\!\cdot\!10^{-4}$	$5.17\!\cdot\!10^{-4}$	$2.99\!\cdot\!10^{-2}$	$6.67\!\cdot\!10^{-3}$	$34$	$6$
$9$	$1.0$	$1.0$	$2.93\!\cdot\!10^{-3}$	$1.34\!\cdot\!10^{-4}$	$3.20\!\cdot\!10^{-2}$	$7.58\!\cdot\!10^{-3}$	$38$	$6$
$10$	$1.0$	$0.8$	$1.50\!\cdot\!10^{-4}$	$1.77\!\cdot\!10^{-3}$	$3.57\!\cdot\!10^{-2}$	$8.94\!\cdot\!10^{-3}$	$42$	$6$
$11$	$1.0$	$0.8$	$1.68\!\cdot\!10^{-3}$	$1.68\!\cdot\!10^{-3}$	$4.20\!\cdot\!10^{-2}$	$1.02\!\cdot\!10^{-2}$	$46$	$6$

Appendix

Table 14: Exact chordal Shor diagnostic for continuum robot projection.

Method	Training signal	Cert. margin	Cert. rate	Train time (s)	Train speedup vs layer
Sparse SOS (Ours)	certificate margin	$0.0274\pm 0.0014$	1.000	52.86	$1.0\times$
Sampled surrogate	sampled grid loss	$0.0234\pm 0.0013$	1.000	27.97	$1.9\times$
Post hoc	-	$-0.7957\pm 0.7453$	0.200	11.38	$4.6\times$

Appendix

Table 15: Single pendulum control full table.

Distribution shift	Layer margin	Layer success	$\Delta$ margin vs sampled	$\Delta$ margin vs stop-grad
in-distribution	0.028	1.000	0.004	0.351
high gravity	0.025	1.000	0.002	0.223
low damping	0.024	1.000	0.003	0.349
large region	0.054	0.970	0.008	0.836
combined hard	0.050	0.957	$5.387\!\cdot\!10^{-4}$	0.634

Appendix

Table 16: Pendulum generalization under distribution shift.

\Delta

is layer

-

baseline certified margin.

Schedule	Cert margin	Train time (s)	Train speedup vs every step	Cert time (s)	Exact step frac
every step	0.028	44.942	$1.0\times$	0.019	1.000
every 5	0.024	20.235	$2.2\times$	0.008	0.202
every 10	0.023	18.804	$2.4\times$	0.007	0.101
late-stage	0.025	21.495	$2.1\times$	0.007	0.183
curriculum	0.028	22.115	$2.0\times$	0.007	1.000

Appendix

Table 17: Pendulum schedule ablation.

Method	Training signal	Cert. margin	Cert. rate	Train time (s)	Train speedup vs layer
Sparse SOS (Ours)	certificate margin	$0.0036\pm 0.0002$	1.000	17.128	$1.0\times$
Stop gradient	blocked certificate gradient	$0.0019\pm 0.0004$	1.000	1.161	$14.8\times$
Sampled surrogate	sampled grid loss	$0.0024\pm 0.0002$	1.000	16.223	$1.1\times$
Post hoc	no certificate during training	$0.0019\pm 0.0004$	1.000	0.945	$18.1\times$
DSOS	inner linear certificate	0.002	1.000	96.710	$0.18\times$
SDSOS	inner second order certificate	0.002	1.000	114.952	$0.15\times$

Appendix

Table 18: Coupled two pendulum chain full diagnostic matrix.

Schedule	Cert. margin	Train time (s)	Train speedup vs every step	Exact step frac.
Every step	$0.0036\pm 0.0002$	17.128	$1.0\times$	1.000
Every 5	$0.0025\pm 0.0002$	1.490	$11.5\times$	0.200
Every 10	$0.0025\pm 0.0002$	1.361	$12.6\times$	0.113
Curriculum	$0.0036\pm 0.0002$	1.894	$9.0\times$	1.000

Appendix

Table 19: Coupled two pendulum chain schedule ablation.

Mode	Test cert. margin	Cert. rate	Exact step frac.	Train time (s)	Train speedup vs exact
Sparse SOS (Ours) every step	0.0021	1.000	1.0	98.7	$1.00\times$
Curriculum	0.0021	1.000	1.0	97.9	$1.01\times$
Sampled surrogate	0.0014	1.000	0.0	97.4	$1.01\times$
Post hoc	0.0014	1.000	0.0	98.3	$1.00\times$
Stop gradient	0.0014	1.000	1.0	94.6	$1.04\times$

Appendix

Table 20: Three pendulum short validation.

Method	Sparse cert. margin	Sparse cert. rate
Structured certificate (Ours)	0.5315	1.000
Post hoc repair	0.0373	0.705
Dense Cholesky	0.1674	0.905

Appendix

Table 21: Structured precision check outside polynomial SOS.

Method	Test NLL	Rel. matrix error	Sparse cert. margin	Sparse cert. rate
Structured certificate (Ours)	9.4311	0.3382	0.5315	1.000
Post hoc repair	9.3666	0.4860	0.0373	0.705
Dense Cholesky	9.4630	0.3893	0.1674	0.905

Appendix

Table 22: Structured precision learning outside polynomial SOS on five seeds.

Training signal	Certificate family	Order	Cert. margin	Cert. rate	Cert. time (s)	Cert. time rel. to sparse SOS
Certificate gradient	DSOS	2	0.044	1.000	0.010	$1.4\times$
Certificate gradient	DSOS	3	0.111	1.000	0.012	$1.7\times$
Certificate gradient	SDSOS	2	0.052	1.000	0.008	$1.1\times$
Certificate gradient	SDSOS	3	0.135	1.000	0.012	$1.7\times$
Certificate gradient	Sparse SOS	2	0.052	1.000	0.007	$1.0\times$
Certificate gradient	Sparse SOS	3	0.135	1.000	0.007	$1.0\times$

Appendix

Table 23: Coupled certification-native strength comparisons.

Schedule	Cert. rate	Cert. margin	Train time (s)	Train speedup vs every step	Cert. time (s)	Exact step frac.
every step	1.000	0.266	27.211	$1.0\times$	0.007	1.000
every 5	1.000	0.263	3.791	$7.2\times$	0.007	0.203
every 10	1.000	0.262	3.594	$7.6\times$	0.008	0.103
late-stage	1.000	0.262	4.079	$6.7\times$	0.008	$<0.001$
curriculum	1.000	0.266	14.094	$1.9\times$	0.007	1.000

Appendix

Table 24: Certification-native schedule ablation.

Study	Seeds	Modes	Runs	Total budget (s)	Mean run (s)
Coupled certification-native	3	4	12	66.598	5.550
Single pendulum control	5	3	15	461.084	30.739
Two pendulum control	5	6	30	1235.595	41.187
Three pendulum validation	1	5	5	486.900	97.380
Non-SOS chain precision	5	3	15	59.510	3.967

Appendix

Table 25: Compute budget summary.

$N$	Forward time (s)			Backward time (s)
	Sparse SOS (Ours)	CVXPY	SDPR	Sparse SOS (Ours)	CVXPY	SDPR
$16$	$0.018$	$\mathbf{0.011}$	$0.011$	$\mathbf{3.80\!\cdot\!10^{-4}}$	$5.24\!\cdot\!10^{-3}$	$4.44\!\cdot\!10^{-3}$
$32$	$0.027$	$0.071$	$\mathbf{0.021}$	$\mathbf{1.50\!\cdot\!10^{-3}}$	$0.050$	$0.022$
$48$	$0.037$	$0.226$	$\mathbf{0.036}$	$\mathbf{3.38\!\cdot\!10^{-3}}$	$0.188$	$0.120$
$64$	$\mathbf{0.048}$	$0.849$	$0.048$	$\mathbf{6.07\!\cdot\!10^{-3}}$	$0.638$	$0.434$
$96$	$\mathbf{0.072}$	$5.307$	$0.079$	$\mathbf{0.014}$	$3.583$	$2.700$

Appendix

Table 26: Banded binary optimization implementation times in seconds.

$N$	Forward time (s)		Backward time (s)
	Sparse SOS (Ours)	CVXPY	Sparse SOS (Ours)	CVXPY
$4$	$\mathbf{1.66\!\cdot\!10^{-2}}$	$9.38\!\cdot\!10^{-2}$	$\mathbf{4.37\!\cdot\!10^{-4}}$	$1.26\!\cdot\!10^{-1}$
$6$	$\mathbf{1.65\!\cdot\!10^{-2}}$	$4.52\!\cdot\!10^{-1}$	$\mathbf{9.10\!\cdot\!10^{-4}}$	$9.12\!\cdot\!10^{-1}$
$8$	$\mathbf{1.86\!\cdot\!10^{-2}}$	$1.87$	$\mathbf{1.58\!\cdot\!10^{-3}}$	$4.08$

Appendix

Table 27: Coupled oscillator Lyapunov certificates implementation times in seconds.

Family	$w$	$n$	Median	Q1	Q3	IQR
Banded	4	24	0.555	0.535	0.560	0.024
Banded	4	48	0.635	0.633	0.636	0.004
Banded	4	96	1.068	1.063	1.070	0.007
Banded	4	160	1.807	1.804	1.812	0.008
Banded	4	224	3.084	3.080	3.088	0.008
Random chordal	4	24	0.467	0.451	0.495	0.044

Appendix

Table 28: Full width-controlled results.

Split	Sparse SOS (Ours)	Finite differences	Sampled surrogate
Train	0, 0, 0, 0, 0	0, 0, 3, 0, 1	0, 0, 0, 0, 9
Test instances	0, 0, 0, 0, 0	0, 0, 0, 0, 0	0, 0, 0, 0, 4
$n=96$	0, 0, 0, 0, 0	0, 4, 0, 0, 0	0, 0, 1, 0, 4
$n=160$	0, 0, 0, 0, 0	0, 6, 0, 0, 0	0, 0, 6, 0, 6

Appendix

Table 29: Violation counts for all seeds.

Training signal	Mean of seed means	SD	Worst design
Sparse SOS (Ours)	0.0114	0.0051	0.0056
Finite differences	0.0113	0.0184	$-0.0146$
Sampled surrogate	0.0205	0.0333	$-0.0062$
Stop gradient or no layer	$-0.0059$	0.0018	$-0.0082$

Appendix

Table 30: Continuous certified relative margins at

n=160

Semidefinite Programming

Semidefinite programming optimizes linear objectives over positive semidefinite matrices to solve convex problems and build tractable relaxations and certificates.

See all 21 papers

Certified Robustness via Sparse Second-Order Cone Relaxations
Oct 12, 2026Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma +3Convex Relaxation Second-Order Cone Programming
Toronto Metropolitan University · University of Minnesota Twin Cities · Johns Hopkins University +2
$(\text{DNN})^2$ : Doubly Non-Negative Relaxations for Deep Neural Networks
Aug 25, 2026Hanna Jiamei Zhang, Alan Papalia, Michael Everett +1Neural Network Verification ReLU Neural Networks
Departments of Computer Science, Electrical and Computer Engineering, and Mathematics Northeastern University, Boston, MA. · Department of Naval Architecture and Marine Engineering, University of Michigan, Ann Arbor, MI.
Demystifying Lipschitz verification: positive matrices, negative results
Mar 30, 2026Simon Kuang, Yuezhu Xu, S. Sivaranjani +1Neural Network Verification Lipschitz Neural Networks
Department of Mechanical and Aerospace Engineering University of California, Davis · Edwardson School of Industrial Engineering Purdue University

Oct 12, 2026J/K move · Enter open · S save

Certified Robustness via Sparse Second-Order Cone Relaxations

Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma, Mahyar Fazlyab+2

Toronto Metropolitan University · University of Minnesota Twin Cities · Johns Hopkins University+2

Convex Relaxation Second-Order Cone Programming Neural Network Verification Certified Robustness Constrained Optimization

Open paper AskPDF arXiv

Certified robustness is critical for deploying neural networks in safety-sensitive settings, but computing exact certificates typically requires solving nonconvex optimization problems. Practical verifiers use convex relaxations: linear programming (LP) relaxations are scalable but often too conservative, whereas semidefinite programming (SDP) relaxations can be substantially tighter but are computationally expensive. We introduce a hierarchy of second-order cone programming (SOCP) relaxations that provide stronger certificates than LP while avoiding the cost of global positive-semidefinite constraints. Our construction combines convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2-by-2 principal minors. Adding these constraints progressively yields a monotone hierarchy of increasingly tight bounds with a controllable computation-tightness trade-off. On fully connected and convolutional networks on MNIST and CIFAR-10, SOCP-based verification improves certified robust accuracy over LP-based verification and is competitive with alpha,beta-CROWN, while remaining orders of magnitude faster than SDP-based verification. These results position selective second-order constraints as a practical middle ground between scalable LP-based and tight SDP-based certification. Finally, we introduce class-optimized robust evaluation (CORE), which applies tighter relaxations only to target classes not certified by cheaper ones. On the fully connected MNIST benchmark, CORE variants match SDP-cert's certified robust accuracy while reducing average verification time by up to 86.30%.

Abstract

Semidefinite Programming

Explore similar work

Certified Robustness via Sparse Second-Order Cone Relaxations

(DNN)2(\text{DNN})^2(DNN)2: Doubly Non-Negative Relaxations for Deep Neural Networks

Demystifying Lipschitz verification: positive matrices, negative results

$(\text{DNN})^2$ : Doubly Non-Negative Relaxations for Deep Neural Networks