Source-linked AI summary
Semidefinite relaxations for certifying robustness to adversarial examples
Aditi Raghunathan, Jacob Steinhardt, Percy Liang
TL;DR
Neural-network defenses are repeatedly defeated by adaptive attacks, motivating certificates over fixed attack models. The paper proposes a semidefinite relaxation for arbitrary ReLU networks and reports tighter certificates, including meaningful guarantees on foreign networks.
Problem
Existing defenses can be broken by adaptive attackers, while prior convex relaxations are loose on networks not trained against the respective relaxation.
Method
The paper develops a semidefinite relaxation that jointly reasons about intermediate activations and converts ReLU certification into a convex upper-bounding procedure.
Results
The SDP is tighter than previous relaxations and provides the first non-trivial certificate for a moderate-size adversarially trained MNIST model at ϵ=0.1.
Takeaways & Limitations
The relaxation produces meaningful robustness guarantees on foreign networks whose training objectives are agnostic to the proposed certification procedure.
Takeaways & Limitations
The experiments focus on fully connected feedforward networks, and current off-the-shelf solvers cannot naively handle the large SDPs produced by convolutional networks.
Abstract
from arXiv · showhide
Despite their impressive performance on diverse tasks, neural networks fail catastrophically in the presence of adversarial inputs---imperceptibly but adversarially perturbed versions of natural inputs. We have witnessed an arms race between defenders who attempt to train robust networks and attackers who try to construct adversarial examples. One promise of ending the arms race is developing certified defenses, ones which are provably robust against all attackers in some family. These certified defenses are based on convex relaxations which construct an upper bound on the worst case loss over all attackers in the family. Previous relaxations are loose on networks that are not trained against the respective relaxation. In this paper, we propose a new semidefinite relaxation for certifying robustness that applies to arbitrary ReLU networks. We show that our proposed relaxation is tighter than previous relaxations and produces meaningful robustness guarantees on three different "foreign networks" whose training objectives are agnostic to our proposed relaxation.
1 Introduction
Certified defenses replace the attacker–defender arms race with provable guarantees over fixed attack models. The proposed SDP relaxation handles arbitrary ReLU networks, is tighter than prior relaxations, and certifies robustness on networks not trained for it.
- Motivation: Adversarial examples expose state-of-the-art classifiers to catastrophic failures from small, imperceptible perturbations, sustaining an arms race between defenses and adaptive attackers.Several published defenses were subsequently broken, including seven ICLR 2018 defenses attacked by Athalye et al.
- Certified robustness: Certified defenses construct convex-relaxation upper bounds on worst-case loss for all attacks within a fixed attack model.The paper’s relaxation is based on semidefinite programming and handles arbitrary numbers of layers.
- New relaxation: The SDP jointly reasons about intermediate activations and theoretically exhibits a square root dimension gap over the LP relaxation for random-weight neural networks.This captures interactions that the LP relaxation cannot.
- Empirical results: The method provides the first non-trivial robustness certificate for a moderate-size adversarially trained MNIST model at ϵ=0.1.Earlier certification for comparable PGD-trained models reached only ϵ=0.05 in the ℓ∞-norm.
- Empirical results: On networks trained to optimize another relaxation, the proposed SDP still produces tighter certificates than the relaxation used during training.This demonstrates the method’s performance on foreign networks whose training objectives are not tailored to it.
2 Setup
The setup bounds a neural network’s worst-case classification margin under ℓ∞-bounded attacks. Because the resulting ReLU optimization is generally non-convex and computationally hard, the paper seeks convex upper bounds that certify robustness.
- Network model: The networks studied are multilayer feedforward ReLU models, with each activation formed by applying max(Wx,0) coordinatewise to the preceding layer.The class label is the output score with the highest value.
- Attack model: The attacker perturbs a clean input within an ℓ∞ ball of radius ϵ and succeeds if some incorrect class outranks the true label.The attacker is assumed to have full knowledge of the neural network.
- Worst-case objective: For each incorrect class, the objective is the worst-case margin between that class’s score and the true class’s score.The optimization jointly considers the input and all intermediate network activations.
- Computational challenge: Computing the worst-case margin is generally intractable because the network’s ReLU consistency constraints make the optimization non-convex.The paper therefore studies convex relaxations that produce an upper bound on the objective.
- Certificate: A negative upper bound on the worst-case incorrect-class margin certifies robustness for the input-label pair.The certificate follows because every admissible attack then leaves the true class ahead of that incorrect class.
3 Semidefinite relaxations
The paper converts ReLU and input constraints into a QCQP, then relaxes it into an SDP using a PSD matrix of linear and quadratic monomials. This construction provides robustness upper bounds and naturally extends beyond one hidden layer.
- The approach rewrites each ReLU constraint as one quadratic and two linear constraints, producing a QCQP that can be relaxed to an SDP.The quadratic constraint enforces z to equal either x or 0, while the linear constraints enforce z ≥ x and z ≥ 0.
- The one-hidden-layer model uses z = ReLU(Wx), bounded inputs, and a linear objective over hidden activations.The objective can represent a worst-case classification margin by choosing c as the difference between incorrect- and true-label weights.
- Input box constraints are expressed quadratically, enabling both input and ReLU constraints to be represented within the QCQP.For each coordinate, lj ≤ xj ≤ uj is equivalent to (xj−lj)(xj−uj)≤0.
- The SDP introduces variables for all linear and quadratic monomials in x and z, making the QCQP constraints linear in those variables.The matrix P collects these monomial variables and supports the semidefinite formulation.
- Replacing the nonconvex rank-one condition on P with P ⪰ 0 yields a convex relaxation whose optimum upper-bounds the original QCQP and robustness loss.Rank-one P exactly recovers the monomials; allowing full-rank factorizations enlarges the feasible set and gives fSDP ≥ fQCQP.
- Unlike the one-hidden-layer formulation in [23], this SDP construction naturally generalizes to multiple layers and often yields substantially tighter bounds.The paper positions this generality and tightness as differences from prior relaxations.
4 Analysis of the relaxation
The geometric interpretation explains how the SDP’s feasible vectors and PSD constraints determine relaxation tightness. Compared with LP, the SDP couples activations, yielding tighter objectives for multiple-unit networks and a dimension-dependent gap.
- 4.1 Geometric interpretation: The SDP represents matrix entries as dot products among vectors, with linear monomials as projections and quadratic monomials as norms or pairwise products.P[1]=1 makes the reference vector unit length, while P[x2] and P[z2] represent squared norms.
- 4.1 Geometric interpretation: Input constraints bound the norm of the vector representing x, while the ReLU quadratic constraint places z on a circle and linear constraints restrict it to a positive arc.The circle is centered at 1/2 x, and the arc has a larger projection on e than x.
- 4.1 Geometric interpretation: As the angle between x and e increases, the feasible z arc has a larger projection on e, making the relaxation looser.For fixed x·e, increasing the norm of x increases the angle; constraints keeping the norm close to x·e therefore tighten the relaxation.
- 4.2 Comparison with linear programming relaxation: The LP relaxes each ReLU independently, so its feasible set for multiple activations is the product of their individual feasible sets.Each unit’s convex envelope depends only on its input bounds and is independent of the other activations.
- 4.2 Comparison with linear programming relaxation: The LP is tighter for a single isolated ReLU, but the SDP becomes tighter than LP when multiple units interact.This contrast motivates the SDP’s joint reasoning over activations.
- 4.2 Comparison with linear programming relaxation: The SDP couples activations through joint constraints, making their feasible set a strict subset of the LP product set.Dependence among inputs such as x1+x2 and x1−x2 is reflected in the PSD matrix constraint, preventing independent variation.
- 4.2 Comparison with linear programming relaxation: fSDP < fLP when optimizing over all valid inputs in the two-ReLU example, demonstrating a tighter SDP objective than LP.The example maximizes z1+z2 for z1 = ReLU(x1+x2) and z2 = ReLU(x1−x2).
- 4.2 Comparison with linear programming relaxation: For random networks, the reported scaling is fLP = Θ(md) while fSDP = Θ(md + d√m), establishing a dimension-dependent gap.The proposition assumes independently sampled ±1 weights, all-ones output vector, clean input 0, and ϵ=1.
5 Multi-layer networks
The multi-layer SDP generalizes the one-hidden-layer relaxation by modeling ReLU interactions across layers and tightening bounds on intermediate activations. Simple interval bounds are sufficient for good certificates in the reported real-network experiments, though tighter bounds could improve them further.
- SDP formulation: The multi-layer SDP generalizes the one-hidden-layer relaxation by iteratively constraining interactions between consecutive ReLU layers.These interactions are represented through bounds on the inputs to each layer's ReLU units.
- SDP formulation: Restricting quadratic monomials of intermediate activations tightens the overall relaxation because each layer's activations feed the next layer.The SDP remains finite without these additional bounds, but tighter bounds on activation squares improve relaxation tightness.
- Intermediate activation bounds: Activation-square bounds can be tightened by relating them to linear activation terms using bounds on each hidden unit.One simple procedure obtains these activation bounds separately for each hidden unit with interval arithmetic.
- Intermediate activation bounds: Simple interval bounds were sufficient to obtain good certificates on real networks, while tighter bounds could potentially produce tighter certificates.This observation comes from the experiments described in Section 6.
6 Experiments
Experiments compare SDP-cert with LP-cert and Grad-cert on three MNIST networks trained by different robust procedures. SDP-cert consistently performs best, including on foreign networks, while PGD-margin analysis shows that many uncertified points are close to misclassification.
- Experimental setup: The evaluation compares three certification procedures on three MNIST networks trained using different robust training procedures.The networks include Grad-NN, LP-NN, and a four-layer PGD-trained network; all are foreign to the proposed SDP.
- Experimental setup: The comparison reports non-certified fractions over the same 1000 random test points and uses PGD attack error as a lower bound on adversarial error.Exact worst-case adversarial error is not computationally tractable in this evaluation.
- Certification results: 18% is the certified error upper bound for the four-layer PGD-NN at ϵ=0.1, versus a 9% lower bound from the PGD attack.For two-layer networks, SDP-cert improves Grad-NN's bound from 35% to 20% and LP-NN's from 22% to 20%.
- PGD-margin analysis: PGD margins average 1.2 for SDP-uncertified points and 4.5 for certified points.The smaller margins among uncertified points suggest that stronger attacks might misclassify many of them.
- Ablation: Removing intermediate-layer constraints relating linear and quadratic terms produces vacuous certificates exceeding 90% error.This ablation indicates that those intermediate-layer constraints materially contribute to empirical SDP performance.
- Certification results: SDP-cert consistently outperforms LP-cert and Grad-cert across all three networks.The table reports fractions of non-certified MNIST examples for ℓ∞ attacks at ϵ=0.1.
7 Discussion
The discussion identifies computational and threat-model boundaries for the proposed SDP. The experiments focus on fully connected networks and bounded ℓ∞ perturbations, while broader real-world perturbations remain outside current mathematical models.
- Computational scope: The study focuses on fully connected feedforward networks because current off-the-shelf solvers cannot naively handle the large SDPs produced by unrolled CNNs.The authors suggest exploiting CNN sparsity and structure, or using scalable SDP methods, to extend the approach.
- Threat-model scope: The framework is evaluated in the common ℓ∞ attack model, although different attack models can be accommodated when their input constraints are linear and quadratic.The unresolved difficulty is securing multi-layer ReLU networks even in this well-studied model.
- Threat-model scope: Bounded-norm guarantees are sufficient but not necessary for real-world robustness because some attacks use visible or semantics-preserving perturbations without well-defined mathematical models.The paper presents its bounded-norm ideas as potential building blocks rather than complete coverage of the broader adversarial setting.
- Reproducibility: All code, data, and experiments are available on the Codalab platform.The paper also acknowledges support and contributions from funding agencies, collaborators, and reviewers.
A Proof of Proposition 1
The proof lower-bounds the LP objective using a feasible solution and upper-bounds the SDP objective through a general lemma and random-matrix spectral-norm bounds. Together, these bounds establish the claimed separation between the relaxations.
- Proof strategy: The proof first lower-bounds fLP and then upper-bounds fSDP.This ordering supports a direct comparison between the two relaxation objectives.
- LP lower bound: A feasible LP solution at x=0 yields a lower bound based on the element-wise ℓ1-norm of the weight matrix.For a random sign matrix, every entry has absolute value 1, giving the stated norm-based bound.
- LP lower bound: The random-sign construction gives fLP ≥ 1/2 md with probability 1.The supplied proof passage states this probability-one lower bound for the LP objective.
- SDP upper bound: A general lemma upper-bounds fSDP in terms of the weight matrices and objective vector.Applying it uses ∥c∥2 = √m and a high-probability spectral-norm bound on W.
A.1 Proof of Lemma 1
The proof invokes the nuclear norm, Hölder’s inequality, and probability bounds implied by constraints on l and u to establish the stated result.
- The argument introduces the nuclear norm, defined as the sum of singular values.
- Hölder’s inequality is used as one step in the proof.
- Constraints imposed by l and u imply that P[x2_j] ≤ 1 for all j.
- The proof concludes with the stated result.