TorchLean API

NN.MLTheory.CROWN.Proofs.GraphAlphaCrownTransferSoundness.Common

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.

theorem NN.MLTheory.CROWN.Graph.AlphaCrownTransferSoundness.FlatBox.ext' {α : Type} [TorchLean.Storage α] [Context α] {B1 B2 : FlatBox α} (hDim : B1.dim = B2.dim) (hLo : B1.lo B2.lo) (hHi : B1.hi B2.hi) :
B1 = B2

Extensionality for FlatBox: equal dimension and heterogeneously equal endpoints.

Helper assumptions #

The designated input entry in inputs matches the concrete point x (up to a castDimScalar).

Instances For

    Pointwise: whenever both arrays contain entries at id, the IBP box encloses the semantic value.

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

        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.

        theorem NN.MLTheory.CROWN.Graph.AlphaCrownTransferSoundness.enclosesAtInput_castOut (ctx : AffineCtx) (x : TorchLean.Tensor [ctx.inputDim]) (xin : FlatAffineBounds ) (vp : FlatTensor ) {outDim' : } (hout : xin.outDim = outDim') (hvout : vp.n = outDim') :
        CrownCertSoundness.EnclosesAtInput ctx x xin vpCrownCertSoundness.EnclosesAtInput ctx x { inDim := xin.inDim, outDim := outDim', loAff := castAffineOut hout xin.loAff, hiAff := castAffineOut hout xin.hiAff } { n := outDim', v := castDimScalar hvout vp.v }

        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.

        theorem NN.MLTheory.CROWN.Graph.AlphaCrownTransferSoundness.signSplit_term_upper (w l u x : ) (hlx : l x) (hxu : x u) :
        w * x (if 0 < w then w else 0) * u + (if 0 < w then 0 else w) * l

        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.

        theorem NN.MLTheory.CROWN.Graph.AlphaCrownTransferSoundness.signSplit_term_lower (w l u x : ) (hlx : l x) (hxu : x u) :
        (if 0 < w then w else 0) * l + (if 0 < w then 0 else w) * u w * x

        The lower-bound companion: w⁺ * l + w⁻ * u is at most w * x.

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

        theorem NN.MLTheory.CROWN.Graph.AlphaCrownTransferSoundness.List.all_eq_true_of_mem {α : Type} (p : αBool) (xs : List α) :
        xs.all p = truexxs, p x = true

        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 #

        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.

        theorem NN.MLTheory.CROWN.Graph.AlphaCrownTransferSoundness.boundsEvalAt_bounds_const {inDim outDim : } (lo hi : TorchLean.Tensor [outDim]) (x : TorchLean.Tensor [inDim]) :
        CrownCertSoundness.boundsEvalAt (Cert.boundsConst inDim outDim lo hi) x = { dim := outDim, lo := lo, hi := hi }

        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.

          Instances For