Theorem A.1 — forward-only sketch baseline
OpenSketchAttr.LOO.Supplement.theorem_A_1One finite program and one universal constant work for every , every scalar arithmetic circuit real-valued on , every , and every stability profile with -stable and . With and the forward-only estimates defined above, the returned cells satisfy
with probability at least under the published independent complex Gaussian tape law. On every tape the program halts without fault, consumes exactly tape entries, and returns the specified full forward-only estimates. It makes no oracle calls.
The paper writes operations and auxiliary space; the forward-differentiation and trimmed-mean estimates on pp. 4–5, 12–13 yield the explicit forms
where , , , and . All coefficient arithmetic, powers, factorial scaling, selection and summation are charged using the published RAM instructions. The statement asserts these actual execution bounds rather than assuming a fast coefficient primitive.
This companion theorem supplies the forward-only comparison to the published goal's faster estimator.
Differences from the source:
- encoding: indices in [n] → indices in Fin n; reason: zero-based coordinate labels change no instance
- encoding: forward sketches with tilde O work and auxiliary-space bounds → N=ceil(log4(1/epsilon)), ell=log(16nN/delta), m=ceil(256ell/epsilon squared), k=floor(ell), and universal-C bounds C size m N log(N+1) and C(size N+nmN); reason: these are the full forward-only construction and constants from the source estimates; log(N+1) retains the published N=1 convention
- encoding: forward-sketch outputs with success probability at least 1-delta → a finite program returns the scalar full-sketch estimator on every tape and its simultaneous bad-event probability is at most delta; reason: the explicit execution and complementary event have the same accuracy and resource content
- encoding: independent complex Gaussian directions reused across coordinates and degrees → disjoint length-n blocks of the published complex Gaussian tape, exactly nm sampled entries, and no call instruction; reason: this supplies the same independent directions without backward-forward slices or exact high-variance corrections
import Mathlib import Definitions.Def_SketchAttr_LOO_Supplement_Forward open MeasureTheory open scoped ENNReal
namespace SketchAttr.LOO.Supplement
theorem theorem_A_1 :
∃ (M : Program) (C : ℝ), 0 < C ∧
(∀ j : ℕ, M[j]? ≠ some Instruction.call) ∧
∀ (n : ℕ), 1 ≤ n → ∀ (c : Circuit n 1) (ε δ : ℝ),
0 < ε → ε < 1 → 0 < δ → δ < 1 → c.RealOnCube →
∀ α : StabilityProfile, IsStable (circuitFunction c) α →
α ⟨4, by norm_num⟩ < ⊤ →
(∀ tape : ℕ → ℂ,
let fuel := forwardFuel C c ε δ
let result := forwardRun M c ε δ tape fuel
result.halted = true ∧ result.fault = false ∧
result.cursor = n * forwardSamples n ε δ ∧
(∀ i : Fin n, result.cm 0 i.val = forwardEstimate c ε δ tape i) ∧
(fuel : ℝ) ≤ C * forwardWorkScale c ε δ ∧
(∀ t : ℕ, t ≤ fuel →
((forwardRun M c ε δ tape t).space : ℝ) ≤ C * forwardSpaceScale c ε δ)) ∧
(gaussianTape (forwardFailure M C c ε δ α) ≤ ENNReal.ofReal δ) := by sorry
end SketchAttr.LOO.Supplement