Shared α-CROWN Transfer Lemmas #
Common definitions and local proof lemmas for the graph-dialect α-CROWN and α/β-CROWN transfer
rules over ℝ. These facts connect affine bounds, IBP boxes, ReLU relaxations, dimension casts,
and pointwise graph semantics.
Helper assumptions #
The designated input entry in inputs matches the concrete point x (up to a castDimScalar).
Instances For
Well-formedness condition for α vectors: each component lies in [0,1].
Instances For
Theorems.Semantics.encloses ↔ componentwise inequalities (via getScalar) #
Small tensor algebra helpers #
A linear layer with zero bias is a plain matrix-vector product.
The certificate builders emit zero biases for the layers that have none, so without this the
transfer proofs would carry a + 0 through every step.
Small cast lemmas (avoid cases on equalities mentioning record fields) #
castDimScalar_trans comes from CertSoundness (opened above) and castDimScalar_self from the
engine module where the cast is defined; this file already depends on both for the rest of the
interval lemmas. Each of them was stated a second time here, word for word, before this note
replaced them.
castDimScalar is proof-irrelevant in its equality argument.
getScalar commutes with castDimScalar (up to Fin.cast).
Activation.reluSpec commutes with castDimScalar.
A small matVecMulSpec cast lemma used for single-row “sum” encodings.
affineEvalAt commutes with casting the output dimension of an affine form.
boundsEvalAt commutes with casting the output dimension of affine bounds.
Semantics.encloses is preserved under casting a box and point to an equal dimension.
Semantics.encloses respects definitional equality of boxes.
Semantics.encloses respects definitional equality of values.
EnclosesAtInput is preserved under casting the output dimension of bounds and value payloads.
Matrix sign-splitting bound (pointwise, over ℝ) #
Entries of the negative part of a matrix: the entry where it is not positive, else zero.
One term of the interval upper bound: w * x is at most w⁺ * u + w⁻ * l.
This is the whole idea of sign splitting. A positive weight is maximized at the upper endpoint and a negative one at the lower endpoint, so pairing each sign with the right endpoint is what makes the matrix version below a coordinatewise consequence.
Interval bound propagation through an affine layer is sound.
The positive and negative parts of W are applied to opposite endpoints, so the resulting box
encloses W x + b for every x in the input box. This is plain IBP; α-CROWN uses it for the
intermediate boxes that its ReLU relaxations are built from.
ReLU relaxations used by α-CROWN #
The upper ReLU relaxation has nonnegative slope, in all three phase branches.
Monotonicity of the relaxation is what lets the transfer proofs multiply an inequality by the slope without flipping it, so this small fact is used pervasively downstream.
The α-parameterized lower relaxation also has nonnegative slope, for any α ≥ 0.
ReLU relaxations used by α/β-CROWN (β phase constraints) #
Accepting an active phase constraint forces 0 ≤ l, so the neuron really is unambiguously on.
This is how the β-CROWN branch decisions are validated: the checker refuses a phase assignment that the interval bounds do not already support, rather than trusting the search that proposed it.
Nonnegative slope for the upper relaxation under any phase constraint.
Nonnegative slope for the lower relaxation under any phase constraint and α ≥ 0.
ReLU transfer helpers (getScalar-level) #
The vector ReLU is the scalar ReLU coordinatewise.
The vector relaxation is the scalar relaxation coordinatewise, which is what turns the scalar soundness lemmas above into statements about whole layers.
Same coordinatewise reading for the α-parameterized lower relaxation.
Propagating an affine form through a ReLU relaxation acts coordinatewise as slope * value + bias.
The implementation scales the whole matrix and shifts the whole constant, so this lemma is the bridge from that global operation to the per-neuron reasoning the soundness proof needs.
β phase vectors (AlphaBetaCROWN.phaseRelaxVec?) are executable, so to reason about them we
extract their per-index consequences from the fact they returned some ....
Unpack a successful phaseRelaxVec?: the phase array has the right length, and every coordinate
carries a phase that is consistent with its interval and whose two relaxations are the scalar ones.
The checker returns only the relaxations, so this is the lemma that recovers the phase witnesses the soundness argument has to case on.
Evaluating linearBoundsFromAffine at a point #
Matrix-vector multiplication is additive in the matrix.
The zero matrix sends every vector to zero, which is what makes constant bounds constant.
The identity affine certificate acts as the identity on inputs.
The identity bounds certificate evaluates to the degenerate box [x, x].
This is the base case of every certificate chain: the input is bounded by itself exactly.
A constant bounds certificate evaluates to its own endpoints, ignoring the input.
Left commutativity of tensor addition, derived from associativity and commutativity.
Regroup (a + b) + (c + d) as (a + c) + (b + d).
Certificate composition produces sums in the order the layers were visited, while the goal groups them by which affine form they came from; this is the reassociation that reconciles the two.
Evaluating the composition of a linear layer with two incoming affine forms distributes over the pair: matrices compose, constants are pushed through, and the bias is added once at the end.
Evaluating the bounds certificate that a linear layer builds from an incoming affine bound gives exactly the sign-split box of the evaluated endpoints.
This is the lemma that connects the certificate the checker writes down to the interval arithmetic
that encloses_linear_signSplit proves sound, and it carries the output-dimension cast that the
graph dialect needs because layer widths are only equal up to a proof.
Step wrapper #
Wrapper around alphaCrownStepNode? in the CrownTransferSound “step function” shape.
Instances For
Wrapper around alphaBetaCrownStepNode? in the CrownTransferSound “step function” shape.