Theorem 26, p.71 — signed shared-design benchmark for independent Lipschitz rows
OpenDeepQOperator.Supplement.theorem_26adaptivitybellman-operatorinformation-based-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Let rows carry nonempty compact metric domains , bounds and Lipschitz constants . Inputs are tuples of independent -Lipschitz functions , . A known , and a signed fix the target . With as in (118), the deterministic adaptive minimax -norm recovery error from at most exact scalar queries is
Fixed near-optimal covers with midpoint estimates attain the infimum in the limiting sense: for every there are an allocation with and fixed sites whose midpoint estimate has worst error at most . The equality includes zero-query rows, constant rows () and unattained optimal covers.
The benchmark shows that, for independent rows, adaptive acquisition gives no advantage over a fixed allocation.
Differences from the source:
- encoding: the minimax error → an infimum over deterministic adaptive algorithms (run with fuel ) of the supremum over the input class of the sup-norm error, in ; reason: Lean convention; neither needs to be attained
- encoding: infimal fill distance of sites → infimum over maps from indices to (repetition allowed); reason: a set of at most distinct sites; the infimum is the same
- reading: attain the infimum in the limiting sense → for every , an allocation and fixed sites whose midpoint estimate has worst error at most ; reason: the limiting sense of App. W.2
Preamble
import Mathlib import Definitions.Def_DeepQOperator_Supplement_LipschitzRows open Finset
Formal statement
namespace DeepQOperator.Supplement
/-- **Theorem 26 (Signed shared-design benchmark)** (Q. Qi, *Deep Q-Operator: Fixed-Accuracy Adaptive
Information and Shared Bellman Decisions*, STOC 2027 submission (manuscript sha256 9f8f3285…),
Theorem 26, p.71, PDF p.74; setting (118) p.71; proof Appendix W, pp.73–74).
Let rows `i = 1, …, m` carry nonempty compact metric domains `𝒜_i`, bounds `B_i ≥ 0` and Lipschitz
constants `L_i ≥ 0`, and let the inputs `(f_i)` range independently over `L_i`-Lipschitz functions
`f_i : 𝒜_i → [-B_i, B_i]`, with `M_i = max f_i`. For known `b ∈ ℝ^K`, `0 < γ < 1` and signed
`A ∈ ℝ^{K×m}`, the deterministic adaptive minimax infinity-norm recovery error of `b + γAM` from at most
`N` exact scalar queries is
`ℜ_N(A) = (γ/2) min_{n ∈ ℕ₀^m, Σ_i n_i ≤ N} max_{k ≤ K} Σ_i |A_ki| D_i(n_i)` (119),
with `D_i` from (118). Fixed near-optimal covers and midpoint estimates attain the infimum in the
limiting sense. The equality includes zero-query rows, constant rows (`L_i = 0`), and unattained optimal
covers.
**Formalization Note.** `minimaxError` is the infimum over deterministic adaptive algorithms
(`LipAlg`, run with fuel `N`) of the supremum over the product input class of the sup-norm error, in
`ℝ≥0∞`. `allocationValue` is the minimum over the finite set of allocations with `Σ n_i ≤ N`. The
limiting-attainment clause: for every `η > 0` there are an allocation with `Σ n_i ≤ N` and fixed sites
`x_i : Fin n_i → 𝒜_i` whose midpoint estimate (Appendix W.2) has worst error at most `ℜ_N(A) + η` over
the input class. The midpoint estimate reads `f` only at the chosen sites. -/
theorem theorem_26 :
∀ (m K : ℕ) (𝒜 : Fin m → Type) [∀ i, MetricSpace (𝒜 i)] [∀ i, CompactSpace (𝒜 i)]
[∀ i, Nonempty (𝒜 i)] (Bd : Fin m → ℝ) (L : Fin m → NNReal) (b : Fin K → ℝ) (γ : ℝ)
(Amat : Matrix (Fin K) (Fin m) ℝ) (N : ℕ),
(∀ i, 0 ≤ Bd i) → 0 < γ → γ < 1 →
minimaxError 𝒜 Bd L b γ Amat N = ENNReal.ofReal (γ / 2 * allocationValue 𝒜 Bd L Amat N) ∧
∀ η : ℝ, 0 < η →
∃ (n : Fin m → ℕ) (_ : ∑ i, n i ≤ N) (x : ∀ i, Fin (n i) → 𝒜 i),
(⨆ (f : ∀ i, 𝒜 i → ℝ) (_ : InLipClass Bd L f),
ENNReal.ofReal ‖midpointEstimate Bd L b γ Amat n x f - recTarget b γ Amat f‖) ≤
ENNReal.ofReal (γ / 2 * allocationValue 𝒜 Bd L Amat N + η) := by sorry
end DeepQOperator.Supplement
Source
Qi, Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman Decisions, STOC 2027 submission (manuscript sha256 9f8f3285…), Theorem 26 and eqs. (118)–(119), p.71 (PDF p.74); proof in Appendix W, pp.73–74 (PDF pp.76–77)