Documentation

Determinize.Proof.Symbolic.Soundness

Soundness of symbolic reduction #

The symbolic semantics preserves typing and operation-domain safety while replacing E samples by their means. Operational trace soundness builds on these invariants in CompactFiberSoundness.

theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.convex_integral_mem_real {α : Type u_1} [MeasurableSpace α] {μ : MeasureTheory.Measure α} [MeasureTheory.IsProbabilityMeasure μ] {set : Set ℝ} {value : α → ℝ} (hConvex : Convex ℝ set) (hMem : ∀ᵐ (x : α) ∂μ, value x ∈ set) (hIntegrable : MeasureTheory.Integrable value μ) :
∫ (x : α), value x ∂μ ∈ set
Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.Affine.eval_cons {n : ℕ} (expression : Symbolic.Affine (n + 1)) (value : ℝ) (environment : Env n) :
    expression.eval (Env.cons value environment) = expression.tail.eval environment + expression.2 0 * value
    theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.Affine.eval_cons_convexCombination {n : ℕ} (expression : Symbolic.Affine (n + 1)) (environment : Env n) (left right a b : ℝ) (hSum : a + b = 1) :
    expression.tail.eval environment + expression.2 0 * (a * left + b * right) = a * (expression.tail.eval environment + expression.2 0 * left) + b * (expression.tail.eval environment + expression.2 0 * right)
    theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.Affine.eval_substituteHeadMean {n : ℕ} (expression : Symbolic.Affine (n + 1)) (op : Spec.Paper.Op) (affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n) (generalArgs : Fin (Spec.Paper.generalArity op) → ℝ) (environment : Env n) :
    (substituteHeadMean expression op affineArgs generalArgs).eval environment = expression.tail.eval environment + expression.2 0 * Spec.Paper.meanValue op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs)
    theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.inDomain_valueSet_convex {n : ℕ} (queryOp : Spec.Paper.Op) (queryAffineArgs : Fin (Spec.Paper.affineArity queryOp) → Symbolic.Affine (n + 1)) (queryGeneralArgs : Fin (Spec.Paper.generalArity queryOp) → ℝ) (environment : Env n) :
    Convex ℝ {value : ℝ | Spec.Paper.InDomain queryOp (fun (i : Fin (Spec.Paper.affineArity queryOp)) => (queryAffineArgs i).eval (Env.cons value environment), queryGeneralArgs)}
    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.transitionPack_apply {n : ℕ} (laws : PrimitiveLaws) (op : Spec.Paper.Op) (affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n) (generalArgs : Fin (Spec.Paper.generalArity op) → ℝ) (environment : Env n) :
      (transitionPack laws op affineArgs generalArgs).kernel environment = MeasureTheory.Measure.map (fun (value : ℝ) => Env.cons value environment) ((laws.kernel op) (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs))
      theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.actualMeasure_snoc_eq_comp {n : ℕ} (laws : PrimitiveLaws) (history : Symbolic.SampleEnv laws n) (op : Spec.Paper.Op) (affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n) (generalArgs : Fin (Spec.Paper.generalArity op) → ℝ) :
      Symbolic.SampleEnv.actualMeasure laws (history.snoc op affineArgs generalArgs) = (Symbolic.SampleEnv.actualMeasure laws history).bind ⇑(transitionPack laws op affineArgs generalArgs).kernel
      theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.integrable_eval_transition {n : ℕ} (laws : PrimitiveLaws) (op : Spec.Paper.Op) (affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n) (generalArgs : Fin (Spec.Paper.generalArity op) → ℝ) (expression : Symbolic.Affine (n + 1)) (environment : Env n) (InDomain : Spec.Paper.InDomain op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs)) :
      MeasureTheory.Integrable (fun (nextEnvironment : Env (n + 1)) => expression.eval nextEnvironment) ((transitionPack laws op affineArgs generalArgs).kernel environment)
      theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.integral_eval_transition {n : ℕ} (laws : PrimitiveLaws) (op : Spec.Paper.Op) (affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n) (generalArgs : Fin (Spec.Paper.generalArity op) → ℝ) (expression : Symbolic.Affine (n + 1)) (environment : Env n) (InDomain : Spec.Paper.InDomain op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs)) :
      ∫ (nextEnvironment : Env (n + 1)), expression.eval nextEnvironment ∂(transitionPack laws op affineArgs generalArgs).kernel environment = (Affine.substituteHeadMean expression op affineArgs generalArgs).eval environment
      theorem Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.inDomain_meanEnvironment {n : ℕ} (laws : PrimitiveLaws) (history : Symbolic.SampleEnv laws n) (safe : Symbolic.SampleEnv.DomainSafe laws history) (op : Spec.Paper.Op) (affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n) (generalArgs : Fin (Spec.Paper.generalArity op) → ℝ) (domainAE : ∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.InDomain op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs)) :
      Spec.Paper.InDomain op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval (Symbolic.SampleEnv.meanEnvironment laws history), generalArgs)

      The source-side invariant used while replacing the recorded E draws by their sequential conditional means.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.ae_eq_one_of_lintegral_eq_one {α : Type u_1} [MeasurableSpace α] (μ : MeasureTheory.Measure α) (mass : μ Set.univ = 1) (f : α → ENNReal) (measurableF : Measurable f) (bounded : ∀ (x : α), f x ≤ 1) (integral : ∫⁻ (x : α), f x ∂μ = 1) :
        ∀ᵐ (x : α) ∂μ, f x = 1
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_univ_eq_one_of_value (stepKernel : StepKernel) (fuel : ℕ) (expression : Spec.Paper.Expr) (value : expression.isValue = true) :
        (nStepMeasure stepKernel fuel expression) Set.univ = 1
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_succ_eq_firstStep (stepKernel : StepKernel) (fuel : ℕ) (expression : Spec.Paper.Expr) :
        nStepMeasure stepKernel (fuel + 1) expression = (stepKernel.kernel expression).bind (nStepMeasure stepKernel fuel)
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_succ_sample_univ {site : Spec.Paper.DistributionAction × Spec.Paper.Op} (stepKernel : StepKernel) (fuel : ℕ) (expression : Spec.Paper.Expr) (fiber : MeasureTheory.Measure ℝ) (continuation : ℝ → Spec.Paper.Expr) (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.sample site fiber continuation) :
        (nStepMeasure stepKernel (fuel + 1) expression) Set.univ = ∫⁻ (value : ℝ), (nStepMeasure stepKernel fuel (continuation value)) Set.univ ∂fiber
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_succ_next_univ (stepKernel : StepKernel) (fuel : ℕ) (expression next : Spec.Paper.Expr) (reduction : Spec.Paper.reduce expression = Spec.Paper.Action.next next) :
        (nStepMeasure stepKernel (fuel + 1) expression) Set.univ = (nStepMeasure stepKernel fuel next) Set.univ
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.measurable_nStepMass_realize {n : ℕ} (stepKernel : StepKernel) (fuel : ℕ) (expression : Symbolic.AffineExpr n) :
        Measurable fun (environment : Env n) => (nStepMeasure stepKernel fuel (Symbolic.AffineExpr.realize environment expression)) Set.univ
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.exists_jointContinuation {site : Spec.Paper.DistributionAction × Spec.Paper.Op} {α : Type u_1} [MeasurableSpace α] {action : α → Spec.Paper.Action} (family : MeasurableActionFamily α action) :
        ∃ (joint : α × ℝ → Spec.Paper.Expr), Measurable joint ∧ ∀ (parameter : α) (fiber : MeasureTheory.Measure ℝ) (continuation : ℝ → Spec.Paper.Expr), action parameter = Spec.Paper.Action.sample site fiber continuation → ∀ (value : ℝ), joint (parameter, value) = continuation value
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.measurable_sampleG_joint_nStepMass {n : ℕ} {ty : Spec.Paper.Ty} {site : Spec.Paper.DistributionAction × Spec.Paper.Op} (laws : PrimitiveLaws) (stepKernel : StepKernel) (fuel : ℕ) (expression : Symbolic.AffineExpr n) (typed : Symbolic.AffineExpr.WellTyped [] expression ty) (fiber : MeasureTheory.Measure ℝ) (continuation : ℝ → Symbolic.AffineExpr n) (reduction : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.sampleG site fiber continuation) :
        Measurable fun (pair : Env n × ℝ) => (nStepMeasure stepKernel fuel (Symbolic.AffineExpr.realize pair.1 (continuation pair.2))) Set.univ
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.source_sampleG_safe_swap {laws : PrimitiveLaws} {n : ℕ} {ty : Spec.Paper.Ty} {site : Spec.Paper.DistributionAction × Spec.Paper.Op} (stepKernel : StepKernel) (fuel : ℕ) (history : Symbolic.SampleEnv laws n) (historySafe : Symbolic.SampleEnv.DomainSafe laws history) (expression : Symbolic.AffineExpr n) (typed : Symbolic.AffineExpr.WellTyped [] expression ty) (sourceSafe : ∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.DomainSafeAt (fuel + 1) (Symbolic.AffineExpr.realize environment expression)) (fiber : MeasureTheory.Measure ℝ) (continuation : ℝ → Symbolic.AffineExpr n) (reduction : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.sampleG site fiber continuation) :
        fiber Set.univ = 1 ∧ ∀ᵐ (value : ℝ) ∂fiber, ∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.DomainSafeAt fuel (Symbolic.AffineExpr.realize environment (continuation value))
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.source_sampleE_safe_extension {laws : PrimitiveLaws} {n : ℕ} {ty : Spec.Paper.Ty} (stepKernel : StepKernel) (fuel : ℕ) (history : Symbolic.SampleEnv laws n) (historySafe : Symbolic.SampleEnv.DomainSafe laws history) (expression : Symbolic.AffineExpr n) (typed : Symbolic.AffineExpr.WellTyped [] expression ty) (sourceSafe : ∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.DomainSafeAt (fuel + 1) (Symbolic.AffineExpr.realize environment expression)) (op : Spec.Paper.Op) (affine : List (Symbolic.Affine n)) (general : List ℝ) (continuation : Symbolic.AffineExpr (n + 1)) (reduction : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.sampleE op affine general continuation) :
        have affineArgs := fun (index : Fin (Spec.Paper.affineArity op)) => affine.getD ↑index (0, fun (x : Fin n) => 0); have generalArgs := fun (index : Fin (Spec.Paper.generalArity op)) => general.getD (↑index) 0; have extended := history.snoc op affineArgs generalArgs; Symbolic.SampleEnv.DomainSafe laws extended ∧ Symbolic.AffineExpr.WellTyped [] continuation ty ∧ ∀ᵐ (environment : Env (n + 1)) ∂Symbolic.SampleEnv.actualMeasure laws extended, Spec.Paper.DomainSafeAt fuel (Symbolic.AffineExpr.realize environment continuation)
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.targetRealize_wrap {n : ℕ} {ExprContext : Spec.Paper.Expr → Spec.Paper.Expr} (action : Symbolic.AffineExpr.SymbolicAction n) (environment : Env n) (context : Symbolic.AffineExpr n → Symbolic.AffineExpr n) (liftedContext : Symbolic.AffineExpr (n + 1) → Symbolic.AffineExpr (n + 1)) (context_realize : ∀ (expression : Symbolic.AffineExpr n), (Symbolic.AffineExpr.realize environment (context expression)).determinize = ExprContext (Symbolic.AffineExpr.realize environment expression).determinize) (lifted_realize : ∀ (expression : Symbolic.AffineExpr (n + 1)) (value : ℝ), (Symbolic.AffineExpr.realize (Env.cons value environment) (liftedContext expression)).determinize = ExprContext (Symbolic.AffineExpr.realize (Env.cons value environment) expression).determinize) :
        targetRealize environment (Symbolic.AffineExpr.SymbolicAction.wrap context liftedContext action) = Spec.Paper.Action.wrap ExprContext (targetRealize environment action)
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.safeConfigAt_not_stuck {laws : PrimitiveLaws} {fuel a✝ : ℕ} {history : Symbolic.SampleEnv laws a✝} {expression : Symbolic.AffineExpr a✝} (safe : SafeConfigAt laws (fuel + 1) history expression) (notValue : expression.isValue ≠ true) :

        A valid mean call takes one deterministic step, using no additional sample coordinate.

        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.source_mean_safe_step {n : ℕ} {ty : Spec.Paper.Ty} {op : Spec.Paper.Op} {affine : List (Symbolic.Affine n)} {general : List ℝ} {continuation : Symbolic.Affine n → Symbolic.AffineExpr n} {fuel : ℕ} (expression : Symbolic.AffineExpr n) (typed : Symbolic.AffineExpr.WellTyped [] expression ty) (actionEq : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.mean op affine general continuation) (environment : Env n) (safe : Spec.Paper.DomainSafeAt (fuel + 1) (Symbolic.AffineExpr.realize environment expression)) :
        Spec.Paper.InDomain op (Symbolic.AffineExpr.meanParams op affine general environment) ∧ Spec.Paper.DomainSafeAt fuel (Symbolic.AffineExpr.realize environment (continuation (Symbolic.AffineExpr.meanAffine op affine general)))
        theorem Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.bind_bind_const_swap {alpha : Type u_1} {beta : Type u_2} {gamma : Type u_3} [MeasurableSpace alpha] [MeasurableSpace beta] [MeasurableSpace gamma] (left : MeasureTheory.Measure alpha) (right : MeasureTheory.Measure beta) [MeasureTheory.SFinite left] [MeasureTheory.SFinite right] (kernel : ProbabilityTheory.Kernel (alpha × beta) gamma) :
        (left.bind fun (a : alpha) => right.bind fun (b : beta) => kernel (a, b)) = right.bind fun (b : beta) => left.bind fun (a : alpha) => kernel (a, b)