Certified Robustness via Sparse Second-Order Cone Relaxations

arXiv:2610.16016 · cs.LG · Submitted 2026-10-12 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Certified Robustness via Sparse Second-Order Cone Relaxations".

Jane: The gist The introduction introduces a hierarchy of sparse second-order cone programming (SOCP) relaxations that provide stronger certificates than linear programming (LP) while avoiding the cost of global semidefinite constraints,…

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we’re looking at the paper "Certified Robustness via Sparse Second-Order Cone Relaxations." It really boils down to how they tackle the computational problem of getting exact robustness certificates for neural networks Jane They introduce a hierarchy of second-order cone programming, or SOCP, relaxations that give them stronger certificates than linear programming but avoid the heavy cost of global semidefinite constraints Lu The core idea is combining convex-hull relaxations of ReLU activations with selective McCormick lifting and those second-order cone constraints to build a monotone hierarchy Jane

Tom: So what does that mean for us in terms of verification? It means you get tighter bounds as you add more complexity to the constraints, but you have control over how much computation it takes to get that tightness Lu They are applying this framework to verify robustness against input perturbations, which they define by an infinity-ball centered on a correctly classified input x with radius epsilon Jane

Lalam: The main goal is to certify that the worst-case margin stays above a certain threshold Tom That worst-case margin is defined as the maximum difference between the logit score of any target class y and the true class, over all valid perturbations in that ball Jane

Tom: It’s about making sure that this worst-case margin stays above a certain threshold Lu The paper sets up this framework using variables like the hidden pre-activation s and activation z, where z is the ReLU of s Jane They show that for simple cases, they can use one hidden layer to present the framework, but it extends layer-wise to multilayer networks Tom

Lu: It’s about showing this works beyond just one layer Jane The paper is essentially providing a practical middle ground between scalable LP verifiers and computationally expensive SDP verifiers Tom They position selective second-order constraints as a way to get that middle ground, which they demonstrate by showing that the ratio of RASDP to RASOCP is greater than or equal to the ratio of RASOCP to RALP on the same set of evaluations Jane

Tom: This suggests SOCP offers a good balance between tightness and cost Lu So, it’s about finding a way to get certification without needing the heavy machinery usually associated with SDP Jane Now that we know what they're trying to do, where does this leave us in terms of how we actually use this?

Jane: Okay, so wrapping up the paper "Certified Robustness via Sparse Second-Order Cone Relaxations," it really boils down to this: they’ve developed a method that offers stronger certification than linear programming while avoiding the computational burden of global semidefinite constraints Tom They do this by creating a hierarchy of second-order cone programming relaxations using specific combinations of ReLU convex-hull relaxations, McCormick lifting, and those two times two principal minor constraints Lu

Tom: The implication for us is that we have a method to get certified robustness from neural networks without needing the massive computational resources that SDP often demands Jane It moves the goalposts by showing that SOCP provides a practical middle ground between scalable LP-based methods and tighter SDP-based certification Lu

Lalam: The authors also introduced CORE, which is this class-wise cascade that applies verifiers selectively to target classes based on what's already certified Jane So, if you're deploying an AI system in something safety-sensitive, this suggests a way to get a mathematical guarantee without the prohibitive cost of SDP Tom

Tom: It’s about getting certification that is strong enough for real deployment but computationally feasible Lu That’s what this paper achieves by showing how sparse second-order cone constraints can be used effectively in this context <ref:2610.16016#pg1>

Jane: The authors also introduced CORE, which is this class-wise cascade that applies verifiers selectively to target classes based on what's already certified Lalam So, if you're deploying an AI system in something safety-sensitive, this suggests a way to get a mathematical guarantee without the prohibitive cost of SDP Tom It’s about getting certification that is strong enough for real deployment but computationally feasible Lu That’s what this paper achieves by showing how sparse second-order cone constraints can be used effectively in this context <ref:2610.16016#pg1>

Conclusion: Tom: So, we're wrapping up our look at "Certified Robustness via Sparse Second-Order Cone Relaxations." Basically, this paper is showing us how to get robust guarantees for neural networks without needing the super heavy math of full semidefinite programming.

Jane: Exactly. The authors are building a system where they use second-order cone programming instead of those big semidefinite constraints that take forever to solve. They do this by mixing different relaxation techniques—like convex hulls for ReLU neurons and these specific second-order cone constraints from two times two matrices—to create a stepping stone for certification.

Tom: It’s a hierarchy, right? They have one starting from the exact quadratic program, and then they progressively add these sparse constraints to make the bounds tighter while keeping the computation manageable. That's where the trade-off happens.

Jane: Right. The implication here is that we can get certification that is much stronger than just linear programming provides, but it doesn't require solving a massive semidefinite problem every time you want to verify robustness against an input perturbation set defined by some infinity-ball.

Tom: It positions this SOCP approach as a practical middle ground. It’s not the absolute tightest thing you can get with SDP, but it’s way faster than the original SDP verifiers on things like fully connected networks on MNIST or CIFAR-ten. That speed difference is huge, orders of magnitude.

Jane: And they even introduced this class-wise cascade called CORE. It means instead of checking every single target class at once, you only use the more expensive SOCP verifiers on the classes that haven't been certified yet by the cheaper ones.

Tom: So it’s about making verification effort selective. It’s about getting a mathematical guarantee without needing those massive computational resources that SDP often demands.

Jane: This moves us toward deploying AI in safety-sensitive areas because we have a method that balances accuracy and feasibility better than before. Now, if this works on these standard networks, what does it mean for verifying something like a complex generative model?

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

Toronto Metropolitan University · University of Minnesota Twin Cities · Johns Hopkins University Augusta University Toronto Metropolitan University, Vector Institute

cs.LG

Submitted: 2026-10-12

Updated: 2026-10-12

Code: https://github.com/SadigDaniel/SOCP-Verifier

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 89/100

The gist: The gist The introduction introduces a hierarchy of sparse second-order cone programming (SOCP) relaxations that provide stronger certificates than linear programming (LP) while avoiding the cost of

Key concepts

Sparse SOCP Hierarchy: This is a progressive set of mathematical relaxations that starts from an exact problem and adds constraints step-by-step. It uses ReLU activation convex hulls, McCormick envelopes for variable bounds, and 2x2 principal minor constraints to create a sequence of increasingly tight bounds while keeping the computation manageable.
McCormick Envelopes: These are mathematical tools used to approximate the product of two variables when only their individual upper and lower bounds are known. In this context, they are applied selectively over certified variable bounds to introduce quadratic terms into the relaxation in a way that is representable by SOCP.
Class-Optimized Robust Evaluation (CORE): CORE is a strategy that saves computation by only applying the most expensive verifiers to classes of inputs that haven't been certified yet. It cascades through different verification stages, moving to the next class only when the current one is successfully verified, significantly reducing overall verification time.
Second-Order Cone Constraints (SOCP): SOCP constraints are a specific type of convex optimization constraint that allows for the inclusion of quadratic relationships between variables. The paper uses SOC constraints derived from 2x2 principal minors to enforce second-order consistency among selected lifted variables, providing tighter bounds than linear programming.

Terminology

Robustness — 1× in this paper · explained in 5 episodes

Summary

The gist The introduction introduces a hierarchy of sparse second-order cone programming (SOCP) relaxations that provide stronger certificates than linear programming (LP) while avoiding the cost of global semidefinite constraints, positioning selective second-order constraints as a practical middle ground for certified robustness verification

How it works

The paper addresses the computational hardness of exact certification for neural networks by introducing a hierarchy of SOCP relaxations that offer a controllable trade-off between bound tightness and computational cost. This hierarchy combines convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2 × 2 principal minors. The construction progressively yields a monotone hierarchy of increasingly tight bounds with a controllable computationtightness trade-off.

The proposed methods include the Sparse SOCP hierarchy and Class-Optimized Robust Evaluation (CORE). The Sparse SOCP relaxation starts from the exact quadratically constrained quadratic program (QCQP) for ReLU-network verification and combines several components. Specifically, it involves convex-hull relaxations of ReLU activations (Wong and Kolter, 2018) with sparse lifting of selected cross-layer, current-layer, and previous-layer products at each hidden layer. These couplings are incorporated using McCormick envelopes over certified variable bounds (McCormick, 1976) and second-order cone (SOC) representations of 2 × 2 positive-semidefinite (PSD) constraints (Kim and Kojima, 2001).

Sparse SOCP Hierarchy Details

The base relaxation replaces the complementarity constraint with the convex-hull relaxation of each ReLU over bounded pre-activations. For unstable neurons, specific constraints are imposed to maintain equivalence to the original function, such as zj ≥ 0, zj ≥ sj, zj ≤ αj (sj − ls,j), αj = us,j / (us,j − ls,j). The paper introduces auxiliary diagonal moment variables to lift quadratic terms and enforces bounds on them. Cross-layer couplings are introduced using McCormick envelopes for selected products and local PSD constraints via 2 × 2 principal minors to enforce second-order consistency among selected lifted variables while remaining exactly SOCP-representable".

Class-Optimized Robust Evaluation (CORE)

CORE is a class-wise cascade designed to allocate verification effort selectively. It operates by applying verifiers in sequence, moving to the next class as soon as robustness against the current class is certified. The process follows Algorithm 1, where for each target class, it applies verifiers from cheap to expensive and escalates only when the current stage returns a non-negative upper bound for that class. CORE certifies an input as robust once every target class is certified, and if a class remains unresolved at the final stage, CORE stops and leaves the input uncertified.

Comparison with Other Methods

Experiments on MNIST and CIFAR-10 show that SOCP-based verification improves certified robust accuracy over the linear programming (LP) verifier. Specifically, on fully connected MNIST, SOCP verifier is orders of magnitude faster than the semidefinite programming (SDP) verifier. Furthermore, CORE variants match SDP-cert’s certified robust accuracy while reducing average verification time by up to 86.30%. The comparison shows that on Grad-NN at ε = 0.1, SOCP-cert certifies 52.31% of inputs compared to 12.31% for LP-cert and 86.15% for SDP-cert.

Computational Complexity

The complexity of the SOCP formulation is analyzed by defining variables based on the selected coupling sets E, S, and T. The resulting formulation has O(N + Q) variables, constraints, and cones compared to O(N2) entries in a dense SDP lift. The time complexity for target verification is bounded by Ttarget = O(Tform + ISOCPM3), where Tform is related to the construction costs. This suggests that sparse conic data require O(A + N + Q) storage.

Conclusion

SOCP retains the input bounds and ReLU hulls of the corresponding LP, hence its projection is contained in the LP feasible set. The paper concludes that SOCP offers an intermediate tightness-cost trade-off, as RASDP ≥ RASOCP ≥ RALP on the same evaluation set.

--- Page 1 ---

Certified Robustness via Sparse Second-Order Cone Relaxations Mohammadreza Maleki Daniel Sadig Rushendra Sidibomma Toronto Metropolitan University Toronto Metropolitan University University of Minnesota Twin Cities Mahyar Fazlyab Arman Adibi Reza Samavi Johns Hopkins University Augusta University Toronto Metropolitan University, Vector Institute 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 positivesemidefinite 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 × 2 principal minors. Adding these constraints progressively yield a monotone hierarchy of increasingly tight bounds with a controllable computationtightness trade-off. On fully connected and convolutional networks on MNIST and CIFAR10, SOCP-based verification improves certified robust accuracy over LP-based verification and is competitive with α, β-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. 1 INTRODUCTION Reliable deployment of neural networks in safetysensitive settings requires guarantees that extend beyond accuracy on unperturbed inputs. Small adversarial perturbations can change a classifier’s prediction while remaining visually imperceptible (Madry et al., 2018; Sadig et al., 2026). This vulnerability motivates certified robustness, which provides a mathematical guarantee that the classifier assigns the correct label to every input in a prescribed perturbation set (Wong and Kolter, 2018; Raghunathan et al., 2018). Exact certification can be formulated by maximizing each competing class’s logit margin relative to the true class over the allowed perturbations. Computing these worst-case margins generally requires solving nonconvex optimization problems, which can make verification computationally hard (Katz et al., 2017). For ReLU networks, complete verifiers, including satisfiability modulo theories (SMT) (Pulina and Tacchella, 2012), mixed-integer optimization (Tjeng et al., 2019), and branch-and-bound methods (Wang et al., 2021), can resolve a verification problem given sufficient computation, but their cost can be prohibitive. Incomplete verifiers instead bound these margins to certify that the prediction remains correct under every admissible perturbation. If these certification bounds cannot be established, the input remains uncertified. A robust input left uncertified represents a false negative in robustness certification. In this paper, we introduce a hierarchy of sparse secondorder cone programming (SOCP) relaxations with a controllable trade-off between bound tightness and computational cost, and a class-wise cascade to progressively allocate more expensive verifiers to unresolved margins. Sparse SOCP hierarchy (Fig. 1a) Starting from the exact quadratically constrained quadratic program (QCQP) for ReLU-network verification, we combine arXiv:2610.16016v1 [cs.LG] 12 Oct 2026.

--- Page 2 ---

Certified Robustness via Sparse SOCP Relaxations Certified Robustness via Sparse SOCP Relaxations (a) Sparse SOCP hierarchy (b) CORE: class-wise cascade LP outer relaxation Sparse lifting with McCormick envelopes and SOC-representable 2 × 2 PSD constraints Cross-layer E(k) couplings Current-layer S(k) couplings Previous-layer T(k) couplings Joint sparse SOCP relaxation Select target class y!= ybar start with the first verifier Current verifier V U <- V(x, ybar, y, epsilon bar) Class y certified Last verifier? Certified robust Uncertified U = 0 All target classes are certified Next target class if any Use next verifier no yes Figure 1: Overview of the proposed methods:

Improvements for AI systems

Robust verification of deep neural networks using Sparse Second-Order Cone Programming (SOCP) relaxations can be implemented to provide stronger certificates than LP while avoiding the cost of global positive semidefinite constraints. This allows for more accurate certification bounds in safety-sensitive settings compared to purely linear relaxations.
Deployment of a Class-Optimized Robust Evaluation (CORE) cascade can be integrated into the verification pipeline, which allocates verification effort to individual class-wise margin problems and escalates only when the current stage returns a non-negative upper bound for that class. This reduces average verification time by up to 86.30% while maintaining at least the certified robust accuracy of the final verifier in the cascade.
AI systems can utilize a hierarchy of SOCP relaxations, combining convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2 × 2 principal minors. This provides a monotone hierarchy of increasingly tight bounds with a controllable computation tightness trade-off, enabling practitioners to select the appropriate level of certification based on computational budget.
For networks requiring high confidence, the system can employ SOCP-cert verification, which improves on LP-cert across the evaluated radii and can certify robust accuracy where LP-cert vanish[es] beyond this point, effectively extending the certified robustness guarantee into regions unreachable by simpler methods.
The system can leverage the computational efficiency of SOCP over SDP by utilizing a formulation with O(N + Q) variables, constraints, and cones instead of O(N 2) entries in a dense SDP lift, allowing for faster verification times when memory-limited evaluations occur.

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