Research map / Architectures and efficiency / RNNs and normalization
Sparse Sum-of-Squares Layers for Certified Learning
Ege Gursoy, Nicolas Mansard
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 changed | Where | Measured | Effect |
|---|---|---|---|
| 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 128 | total warm-call time: 1.62x, 1.95x, 2.21x, 2.65x at N=16,32,96,128 | Improved |
| use chordal (sparse) formulation instead of ambient dense formulation (ablation) | Sparse SOS layer · Banded binary optimization | total warm-call time: ambient faster through N=64, crossover at N=96, chordal 4.38x faster at N=256 | Mixed |
| cache the sparse template across calls instead of rebuilding (ablation) | Sparse SOS layer · Banded binary optimization, N=256 | total warm-call time: 99.040 -> 72.820 ms (1.36x) | Improved |
| use larger clique width (ablation) | chordal vs ambient crossover · Banded and random chordal instances | crossover size: n_cross approx 32(w-1) | Hurt |
| train through Sparse SOS certificate gradient instead of stop gradient (ablation) | single pendulum controller · Single pendulum | certified margin: -0.323 -> 0.028 | Improved |
| train with certificate margin gradient instead of sampled grid surrogate | pendulum controller · Single pendulum | certified margin: 0.0234 -> 0.0274 | Improved |
| train with Sparse SOS gradient instead of finite differences | certified design MLP · Certified design task, train/test sizes | training optimization solves: 3360 -> 480 solves; violations 4/80 -> 0/80 on train | Improved |
| train with Sparse SOS gradient instead of sampled surrogate | certified design MLP · Certified design task, n=160 | violations: 12/30 -> 0/30 | Improved |
| block certificate gradient (stop gradient) while keeping the forward solve (ablation) | certified design MLP · Certified design task | violations: 0/80 -> 80/80 on train | Hurt |
| evaluate exact certificate every 5 or 10 steps instead of every step (ablation) | single pendulum training · Single pendulum | train time and margin: train time 44.942 -> 18.804 s; margin 0.028 -> 0.023 | Mixed |
| use the Sparse SOS layer instead of SDPR or CVXPY in a training loop | value-learning on banded N=96 · Banded binary N=96 training loop | time to loss 1e-3: 71.94 -> 22.28 s vs SDPR | Improved |
| use Sparse SOS layer for forward pass on pose graphs | pose graph synchronization · Pose graph synchronization | forward time: 0.034 vs 0.031 s (SDPR) at 28 poses | Hurt |
Experimental setup
Builds on: SDP layers
Closest papers by meaning
- Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization (ICLR 2025 · similarity 0.84)
- DeepBern-Nets: Taming the Complexity of Certifying Neural Networks Using Bernstein Polynomial Activations and Precise Bound Propagation (AAAI 2024 · similarity 0.84)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.83)
- Sparse Transfer Learning Accelerates and Enhances Certified Robustness: A Comprehensive Study (AAAI 2025 · similarity 0.83)
- Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing (NeurIPS 2024 · similarity 0.83)
- A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.83)
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.
