cs.LGOct 12, 2026

Certified Robustness via Sparse Second-Order Cone Relaxations

Authors: Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma, Mahyar Fazlyab, Arman Adibi, Reza Samavi

Organizations: Toronto Metropolitan University · University of Minnesota Twin Cities · Johns Hopkins University · Augusta University · 

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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%.

Figures & tables

Figure 1: Overview of the proposed methods: (a) jointly selected cross-layer, current-layer, and previous-layer couplings at each hidden layer, with z(0)=xz^{(0)}=x , and (b) CORE’s class-wise cascade with early stopping.
Figure 2: Panels (a)–(c) illustrate sparse SOCP couplings by selecting cross-layer E(k)\mathcal{E}^{(k)} , current-layer S(k)\mathcal{S}^{(k)} , and previous-layer T(k)\mathcal{T}^{(k)} couplings and their SOC-representable 2×22\times 2 PSD constraints. Square lifts are shared across incident products, which also satisfy McCormick envelopes.
DatasetTraining Methodεtrain\varepsilon_{\mathrm{train}}εverify\varepsilon_{\mathrm{verify}}CleanSOCP-certα,β\alpha,\beta -CROWNPGD
MNISTIBP0.10.199.00%88.33%87.33%88.67%
CROWN-IBP0.10.197.67%94.33%93.67%94.67%
DeepPoly0.10.198.00%94.67%93.33%94.67%
Dual-WK0.10.182.00%69.67%70.00%72.33%
MNISTCROWN-IBP0.10.1597.67%8.00%N/A32.00%
DeepPoly0.10.1598.00%7.33%N/A34.33%
Table 1: Verification of CNNs Trained for Certified Robustness. Clean accuracy, certified robust accuracy (SOCP-cert and α,β\alpha,\beta -CROWN), and PGD upper bounds use matched test images (300 MNIST; 200 CIFAR-10). N/A indicates that α,β\alpha,\beta -CROWN ran out of memory (Appendix G ). Additional MNIST results at εverify=0.2\varepsilon_{\mathrm{verify}}=0.2 appear in Appendix A.3 .
VerifierRATime (min)Reduction
SDP-cert86.15%328.98–
SOCP-cert52.31%0.3199.90%
LP-cert12.31%––
CRV-FSR186.15%168.3348.83%
CRV-FSR286.15%91.8672.08%
CORE86.15%70.6178.54%
Table 2: Verification of Grad-NN on MNIST at ε=0.1\varepsilon=0.1 . RA is certified robust accuracy; PGD gives an empirical upper bound. Time is averaged per image; reduction is relative to SDP-cert.
Figure 3: Certified robust accuracy versus ℓ∞\ell_{\infty} perturbation radius on Grad-NN (one hidden layer). SOCP-cert retains certificates at radii where LP-cert certifies no inputs.
Figure 4: Certified robust accuracy versus ℓ∞\ell_{\infty} perturbation radius on Std-NN (two hidden layers). SOCP-cert improves on LP-cert across the evaluated radii.
Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

DatasetTraining methodεtrain\varepsilon_{\mathrm{train}}εverify\varepsilon_{\mathrm{verify}}CleanSOCP-certα,β\alpha,\beta -CROWNPGD
MNISTIBP0.30.299.0083.3381.6786.00
CROWN-IBP0.30.297.6788.3387.3390.00
DeepPoly0.30.298.0088.0086.6790.33
Dual-WK0.30.282.0061.6761.0062.67
Appendix
Table 3: Certified-trained MNIST models trained at εtrain=0.3\varepsilon_{\mathrm{train}}=0.3 and evaluated at εverify=0.2\varepsilon_{\mathrm{verify}}=0.2 , complementing Table 1 . Accuracy values are percentages on the same matched 300-image evaluation set.
More in this topic

Convex Relaxation

See all 12 papers

Explore similar work

CardsList
Aug 25, 2026

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

Existing linear program (LP) and semidefinite program (SDP) relaxations for rectified linear unit (ReLU) neural network (NN) verification yield overly-conservative safety guarantees due to significant relaxation gaps. While the completely positive program (CPP) formulation closes this gap, it is NP-hard to solve. Its cheapest tractable relaxation, the doubly non-negative program (DNN), retains critical constraints as an SDP, but one whose size exceeds the reach of interior-point methods at practical scale. While Burer-Monteiro (BM) factorization has been applied to make SDP-based verification scalable, no such result exists for the strictly tighter DNN formulation. A key obstacle is that additional non-negativity constraints in the DNN cause dual multipliers for optimality certification to be non-unique, making standard certification methods inapplicable. We propose a novel eigenvalue maximization procedure that searches the non-unique multiplier space for a valid certificate, i.e. a global optimality guarantee. Experiments demonstrate that our approach (DNN)2(\text{DNN})^2 produces bounds consistently tighter than the standard SDP method, often matching the exact solution, and that our certification procedure confirms global optimality when a valid certificate exists. These results are a key step toward providing tight, certifiable, and computationally scalable verification guarantees needed to deploy neural network controllers and perception modules in safety-critical autonomous systems.

Hanna Jiamei Zhang, Alan Papalia, Michael Everett +1

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.

Neural Network VerificationReLU Neural NetworksSemidefinite ProgrammingNonconvex Optimization
AskPDF
Jun 17, 2023

Understanding Certified Training with Interval Bound Propagation

As robustness verification methods are becoming more precise, training certifiably robust neural networks is becoming ever more relevant. To this end, certified training methods compute and then optimize an upper bound on the worst-case loss over a robustness specification. Curiously, training methods based on the imprecise interval bound propagation (IBP) consistently outperform those leveraging more precise bounding methods. Still, we lack an understanding of the mechanisms making IBP so successful. In this work, we thoroughly investigate these mechanisms by leveraging a novel metric measuring the tightness of IBP bounds. We first show theoretically that, for deep linear models, tightness decreases with width and depth at initialization, but improves with IBP training, given sufficient network width. We, then, derive sufficient and necessary conditions on weight matrices for IBP bounds to become exact and demonstrate that these impose strong regularization, explaining the empirically observed trade-off between robustness and accuracy in certified training. Our extensive experimental evaluation validates our theoretical predictions for ReLU networks, including that wider networks improve performance, yielding state-of-the-art results. Interestingly, we observe that while all IBP-based training methods lead to high tightness, this is neither sufficient nor necessary to achieve high certifiable robustness. This hints at the existence of new training methods that do not induce the strong regularization required for tight IBP bounds, leading to improved robustness and standard accuracy.

Yuhao Mao, Mark Niklas Müller, Marc Fischer +1

Department of Computer Science, ETH Zürich, Swizterland

Neural Network VerificationNeural Network RobustnessCertified Robustness
AskPDF
Jun 22, 2026

Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications

A primary challenge in AI safety is the existence of adversarial examples -- slightly distorted inputs that cause a neural network (NN) to misclassify. To mitigate this problem, recent research focuses on the computation of robustness certifications, which, for a given input, determine the largest distortion the input may receive without breaking the network's prediction. Robustness certifications can be interpreted as an axis-aligned hyper-rectangle (multi-dimensional intervals). Most existing approaches focus on maximizing the certification's volume, but recent intractability results prohibit the computation of volume-optimal certifications in reasonable time. We introduce the apothem measure and show how to compute apothem-optimal certifications in a linear number of calls to a NN verifier (oracle) w.r.t. the input domain's diameter. Moreover, we prove that we cannot have a volume-optimal, oracle-based algorithm, even if we discard the oracle costs. Also, we introduce dual certifications -- an interval including all instances of a class -- thus providing apothem-minimum upper bounds to a robustness certification. Further, we present the ParallelepipedoNN system, which we evaluate on the standard MNIST and Fashion MNIST benchmarks. A preliminary comparison with existing work on the same datasets reveals at least two-fold improvement w.r.t. the minimum edge length.

Merkouris Papamichail, Konstantinos Varsos, Giorgos Flouris +1

Foundation for Reasearch and Technology - Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1

Neural Network VerificationNeural Network RobustnessCertified Robustness
AskPDF