acceptodds
Under review as a conference paper at ICLR 2027

Pointwise Wasserstein verification of neural networks via closed-form bound concretization

Abstract

Affine-bound verifiers such as CROWN, DeepPoly, and DeepZ certify neural networks against perturbations by producing a valid affine bound A · x + b and minimizing it over the ball through the dual norm _. We show that this last step—the concretization—admits a closed form for Wasserstein balls: the worst case of any valid affine bound over a W1 ball is the budget ε times the maximal edge drop \| \|_, the W1-Lipschitz constant of the affine envelope, computed in O(|E|) = O(n) tensor operations on the pixel graph under the L1 ground metric, with no transport-side optimization. The form is exact on the relaxed (signed-measure) ball and is therefore a sound certificate on its own; an optional LP tier, gated by a zero-cost test that never changes a certification decision in our benchmarks, restores exactness on the probability-measure ball. Because the closed form depends only on the envelope, not on the domain it was computed on, every verifier is a ready-made envelope generator; and because the interface consumes validity rather than provenance, even learned envelopes are admitted by a check built from the same closed form, which certifies or abstains but never issues a false certificate. The method yields per-sample certified radii with an exact two-term gap decomposition that localizes all conservatism to the envelope, and the closed form matches explicit LPs to solver tolerance at roughly three orders of magnitude lower concretization cost.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Neural network verification, Bound propagation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_PzMEOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies neural network certification with affine relaxation and a W1 input set. It proposes a closed form solution for concretizing the bound given an affine inequality produced by existing affine relaxations to the W1 input set. It then did some evaluation for this method.

Critical strengths

The method is well-presented, the extension beyond Lp norm to translation etc is important, the closed form solution is sound, and the method is well-motivated.

Critical weaknesses

There is a deadly weakness: the main result has already been published as lemma 7 by Wegel et al. (https://arxiv.org/html/2110.06816v1#A1). I confirmed the equivalence between the results. In particular, although Wegel et al. studies a linear classifier, this work's result is also about concretizing a linear relaxation, so essentially equivalent. This equivalence is acknowledged by the authors in related work, while they argue their implementation is faster. I do not consider this as sufficient novelty, especially given the introduction clearly highlights that they contribute the closed-form solution without even mentioning the same result by Wegel et al.

The second main contribution mentioned in the introduction is also trivial. The bound from Wegel et al. can be trivially applied on any linear relaxation as well.

Further, the extension to geometric perturbations like translation is not new; see https://papers.nips.cc/paper_files/paper/2019/file/f7fa6aca028e7ff4ef62d75ed025fe76-Paper.pdf, but there is no demonstration about why the proposed W1 specification might be better for these perturbations which motivates the study (Line 45).

Questions for authors

See weakness. The authors should clearly highlight the difference between this work and the result of Wegel et al., and argue about its novelty.

Reviewer_YHP2OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes a closed form expression for certifying neural networks against Wasserstein perturbations. This leads to more efficient computations of the worst case envelope (computations scales as O(n)). The approach serves as a plug-and-play that can augment any other verifier that is based on affine-based overapproximations.

Critical strengths
  • The closed form expression is clean and sound
  • The reduction in the compute time is significant thanks to the linear scaling of the proposed algorithm.
Critical weaknesses
  • The proposed expression does not reduce the certification over-approximation compared to existing methods
  • The method was applied to small networks (MNIST and CIFAR)
Questions for authors

What specific architectural changes in the network do you believe are necessary to make the learned envelope approach scale beyond MNIST and can make CIFAR networks produce envelopes that are not vacuous?

Reviewer_gq39OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposed a closed-form Wasserstein distance concretization that is required in a bound propagation algorithm. In particular, let W(x0,x’)=W(x_0,x’)= denote the Wasserstein distance between x0x_0 and x’x’, the authors demonstrated that the Wasserstein ball centered at x0x_0 with radius ϵ\epsilon can be written as {x∣W(x0,x)≤ϵ}={x0+Bϕ∣∥ϕ∥1≤ϵ}\{x\mid W(x_0,x)\leq\epsilon\}=\{x_0+B\phi \mid \|\phi\|1\leq\epsilon\}. Given that the existing bound propagation framework such as CROWN can only handle ℓp\ell_p-norm input set, the reformulation allows the existing bound propagation to be extended for Wasserstein distance input set.

Critical strengths

None

Critical weaknesses

I found the novelty of this paper to be quite limiting. In particular, the reformulation of Wasserstein distance x∣W(x0,x)≤ϵ=x0+Bϕ∣∥ϕ∥1≤ϵ\\{x\mid W(x_0,x)\leq\epsilon\\}=\\{x_0+B\phi \mid \|\phi\|1\leq\epsilon\\} is known in the literature. In fact, I think it is also known in the verification community that existing bound propagation, such as CROWN, can easily handle Wasserstein distance by applying this reformulation and absorbing the B matrix into the weight matrix at the first layer.

Questions for authors

Is there any difference between A⋅xA\cdot x and ATxA^Tx?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.