AI Paper Atlas

Research map / Architectures and efficiency / RNNs and normalization

Sparse Sum-of-Squares Layers for Certified Learning

Ege Gursoy, Nicolas Mansard

NeurIPS 2026 · Architectures and efficiency › RNNs and normalization · approach: Differentiable optimization layers · 0 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes sparse sum-of-squares (SOS) layers that embed certified polynomial-inequality reasoning via SDP as differentiable components in neural networks, aiming to improve scalability over prior SDP layers.

Problem

Modern ML systems lack formal certificates guaranteeing behavior beyond sample-based evaluation; existing SDP layers for certifying polynomial inequalities via sum-of-squares do not scale well.

Approach

Uses sparsity in sum-of-squares certificates so that SOS constraints become tractable as differentiable layers inside neural networks, extending prior dense SDP layers.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
specialize derivative to the scalar value instead of generic solution-map differentiation (ablation)Sparse SOS layer on chordal banded model · Banded binary optimization, N=16 to 128total warm-call time: 1.62x, 1.95x, 2.21x, 2.65x at N=16,32,96,128Improved
use chordal (sparse) formulation instead of ambient dense formulation (ablation)Sparse SOS layer · Banded binary optimizationtotal warm-call time: ambient faster through N=64, crossover at N=96, chordal 4.38x faster at N=256Mixed
cache the sparse template across calls instead of rebuilding (ablation)Sparse SOS layer · Banded binary optimization, N=256total warm-call time: 99.040 -> 72.820 ms (1.36x)Improved
use larger clique width (ablation)chordal vs ambient crossover · Banded and random chordal instancescrossover size: n_cross approx 32(w-1)Hurt
train through Sparse SOS certificate gradient instead of stop gradient (ablation)single pendulum controller · Single pendulumcertified margin: -0.323 -> 0.028Improved
train with certificate margin gradient instead of sampled grid surrogatependulum controller · Single pendulumcertified margin: 0.0234 -> 0.0274Improved
train with Sparse SOS gradient instead of finite differencescertified design MLP · Certified design task, train/test sizestraining optimization solves: 3360 -> 480 solves; violations 4/80 -> 0/80 on trainImproved
train with Sparse SOS gradient instead of sampled surrogatecertified design MLP · Certified design task, n=160violations: 12/30 -> 0/30Improved
block certificate gradient (stop gradient) while keeping the forward solve (ablation)certified design MLP · Certified design taskviolations: 0/80 -> 80/80 on trainHurt
evaluate exact certificate every 5 or 10 steps instead of every step (ablation)single pendulum training · Single pendulumtrain time and margin: train time 44.942 -> 18.804 s; margin 0.028 -> 0.023Mixed
use the Sparse SOS layer instead of SDPR or CVXPY in a training loopvalue-learning on banded N=96 · Banded binary N=96 training looptime to loss 1e-3: 71.94 -> 22.28 s vs SDPRImproved
use Sparse SOS layer for forward pass on pose graphspose graph synchronization · Pose graph synchronizationforward time: 0.034 vs 0.031 s (SDPR) at 28 posesHurt

Experimental setup

Builds on: SDP layers

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy