Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 15, p.46 — complete bounded-error adaptive curves for the normalized family

Open
DeepQOperator.Supplement.theorem_15

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

adaptivitybellman-operatorinformation-based-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity

For the normalized family (76)–(78), m≥2m\ge2m≥2, 0<γ<10<\gamma<10<γ<1, c=γ/mc=\gamma/mc=γ/m, and every known error level τ≥0\tau\ge0τ≥0: each queried raw site qqq returns q(θ)+eq(\theta)+eq(θ)+e with ∣e∣≤τ|e|\le\tau∣e∣≤τ. The error is chosen by a causal rule from the parameter, the current query and the public preceding transcript. Rule and parameter are fixed before the algorithm's private randomness. Then

BNdet⁡(τ)={c/2,N=0,1,cmin⁡{2τ,1/2},N≥2,BNran(τ)={c/4,N=0,1,cmin⁡{τ,1/4},N≥2.(82)\mathfrak B^{\det}_N(\tau)=\begin{cases}c/2,&N=0,1,\\c\min\{2\tau,1/2\},&N\ge2,\end{cases}\qquad \mathfrak B^{\mathrm{ran}}_N(\tau)=\begin{cases}c/4,&N=0,1,\\c\min\{\tau,1/4\},&N\ge2.\end{cases} \tag{82}BNdet​(τ)={c/2,cmin{2τ,1/2},​N=0,1,N≥2,​BNran​(τ)={c/4,cmin{τ,1/4},​N=0,1,N≥2.​(82)

The two-query upper bounds require no promise that the address or the contrast is separated from a boundary. The lower bounds for N≥2N\ge2N≥2 hold for every finite budget, even against randomized acquisition, using one fixed corrupted response for each raw site: there are two parameters in PmP_mPm​ and one reply per raw site, within τ\tauτ of both parameters' values, against which every algorithm with any budget has the stated worst loss.

The curves show that adaptive exactness degrades linearly in the observation error and that repetition cannot help.

Differences from the source:

  • encoding: worst-input expected regret sup⁡θEωℓ(A(θ;ω),θ)\sup_\theta E_\omega \ell(A(\theta;\omega),\theta)supθ​Eω​ℓ(A(θ;ω),θ) → an R≥0∪{∞}\mathbb{R}_{\ge0}\cup\{\infty\}R≥0​∪{∞}-valued supremum of lower Lebesgue integrals of the loss; reason: Lean convention; the loss is nonnegative and bounded, so the values agree
  • encoding: at most NNN queries (reply bits) on every input and random path → the algorithm is run with fuel NNN (protocols: hard budget HardBudgetOn and fuel BBB); reason: a run with fuel NNN asks at most NNN queries, and an algorithm with hard budget NNN behaves identically under fuel NNN
  • encoding: randomized algorithm with private seed; deterministic algorithm → seed space a standard Borel probability space (Ω,μ)(\Omega,\mu)(Ω,μ); deterministic = seed space Unit with the Dirac measure; reason: the standing randomization model (20), §5, p.8
  • encoding: the minimax value is at least xxx → every algorithm of the class (measurable, on every standard Borel probability seed space) has worst regret at least xxx; reason: an infimum is at least xxx exactly when every member is
  • reading: the minimax value is at most xxx (an upper bound on an infimum) → there is an algorithm of the class whose worst regret is at most xxx; reason: the source proves each upper bound by an explicit algorithm or design it describes
  • encoding: error rule chosen with the parameter before the seed, depending on the parameter, the current query and the public preceding transcript → a supremum over θ∈Pm\theta\in P_mθ∈Pm​ and over functions E(h,q)E(h,q)E(h,q) with ∣E∣≤τ|E|\le\tau∣E∣≤τ of (public transcript, current query); the seed is not an argument; reason: dependence on the parameter is the supremum over θ\thetaθ outside EEE
  • encoding: one fixed corrupted response for each raw site → ∃θ1,θ2∈Pm\exists\theta_1,\theta_2\in P_m∃θ1​,θ2​∈Pm​ and yyy on queries with ∣y(q)−q(θi)∣≤τ|y(q)-q(\theta_i)|\le\tau∣y(q)−q(θi​)∣≤τ on raw sites, such that every algorithm, for every budget, has worst (expected) loss over {θ1,θ2}\{\theta_1,\theta_2\}{θ1​,θ2​} at least the N≥2N\ge2N≥2 value when every query is answered by yyy; reason: the witness the sentence describes; it is stated for every budget NNN, as in 'every finite budget'
Preamble
import Mathlib
import Definitions.Def_DeepQOperator_Family
import Definitions.Def_DeepQOperator_Supplement_AdaptiveAlg
import Definitions.Def_DeepQOperator_Supplement_Normalized

open MeasureTheory
Formal statement
namespace DeepQOperator.Supplement

/-- **Theorem 15 (Complete bounded-error adaptive curves)** (Q. Qi, *Deep Q-Operator: Fixed-Accuracy
Adaptive Information and Shared Bellman Decisions*, STOC 2027 submission (manuscript sha256
9f8f3285…), Theorem 15, p.46, PDF p.49; model §L.3 p.45, proof Appendix Q pp.64–65).

For the raw normalized family (76)–(78), `m ≥ 2`, `0 < γ < 1`, `c = γ/m`, and every `τ ≥ 0`, when each
queried raw site `q` returns `q(θ) + e` with `|e| ≤ τ` and `e` chosen by a causal error rule:
`𝔅^det_N(τ) = c/2` for `N = 0, 1` and `c·min{2τ, 1/2}` for `N ≥ 2`, and `𝔅^ran_N(τ) = c/4` for
`N = 0, 1` and `c·min{τ, 1/4}` for `N ≥ 2` (82). The two-query upper bounds hold on all of `P_m`, with
no promise that the address or the contrast is separated from a boundary. The lower bounds for
`N ≥ 2` hold for every finite budget, even against randomized acquisition, using one fixed corrupted
response for each raw site.

**Formalization Note.** Algorithms are `AdaptiveAlg (NCoord m) Ω` with exact observation maps
(`IsExact`: the algorithm sees the corrupted reply itself) and raw queries, run with fuel `N`.
`noisyRegret` takes the supremum over `θ ∈ P_m` and over error rules `E` with `|E| ≤ τ`; `E` sees the
public preceding transcript (queries and replies) and the current query, is chosen with `θ` before the
seed, and cannot see the seed; the final decision may use fresh coins from the seed. Deterministic
algorithms have seed `Unit` (Dirac measure) and carry no measurability condition; randomized ones are
measurable on a standard Borel probability space. Each value is stated as a lower bound for the class
and an algorithm attaining it. The last clause states the lower-bound witness: two parameters
`θ₁, θ₂ ∈ P_m` and one reply `y q` for each raw site `q`, within `τ` of both `q(θ₁)` and `q(θ₂)`, against
which every algorithm, for every budget `N`, has the stated worst loss over `{θ₁, θ₂}`. -/
theorem theorem_15 :
    ∀ m : ℕ, 2 ≤ m → ∀ γ : ℝ, 0 < γ → γ < 1 → ∀ τ : ℝ, 0 ≤ τ →
      -- deterministic curve
      (∀ N : ℕ, N ≤ 1 →
        (∀ A : AdaptiveAlg (NCoord m) Unit, A.IsExact → A.IsRaw (nDictionary m) →
          ENNReal.ofReal (γ / m / 2) ≤
            noisyRegret (nBox m) (nLoss m γ) (Measure.dirac ()) A N τ) ∧
        (∃ A : AdaptiveAlg (NCoord m) Unit, A.IsExact ∧ A.IsRaw (nDictionary m) ∧
          noisyRegret (nBox m) (nLoss m γ) (Measure.dirac ()) A N τ ≤
            ENNReal.ofReal (γ / m / 2))) ∧
      (∀ N : ℕ, 2 ≤ N →
        (∀ A : AdaptiveAlg (NCoord m) Unit, A.IsExact → A.IsRaw (nDictionary m) →
          ENNReal.ofReal (γ / m * min (2 * τ) (1 / 2)) ≤
            noisyRegret (nBox m) (nLoss m γ) (Measure.dirac ()) A N τ) ∧
        (∃ A : AdaptiveAlg (NCoord m) Unit, A.IsExact ∧ A.IsRaw (nDictionary m) ∧
          noisyRegret (nBox m) (nLoss m γ) (Measure.dirac ()) A N τ ≤
            ENNReal.ofReal (γ / m * min (2 * τ) (1 / 2)))) ∧
      -- randomized curve
      (∀ N : ℕ, N ≤ 1 →
        (∀ (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
            [IsProbabilityMeasure μ] (A : AdaptiveAlg (NCoord m) Ω),
          A.IsExact → A.IsRaw (nDictionary m) → A.IsMeasurable →
          ENNReal.ofReal (γ / m / 4) ≤ noisyRegret (nBox m) (nLoss m γ) μ A N τ) ∧
        (∃ (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
            (_ : IsProbabilityMeasure μ) (A : AdaptiveAlg (NCoord m) Ω),
          A.IsExact ∧ A.IsRaw (nDictionary m) ∧ A.IsMeasurable ∧
          noisyRegret (nBox m) (nLoss m γ) μ A N τ ≤ ENNReal.ofReal (γ / m / 4))) ∧
      (∀ N : ℕ, 2 ≤ N →
        (∀ (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
            [IsProbabilityMeasure μ] (A : AdaptiveAlg (NCoord m) Ω),
          A.IsExact → A.IsRaw (nDictionary m) → A.IsMeasurable →
          ENNReal.ofReal (γ / m * min τ (1 / 4)) ≤ noisyRegret (nBox m) (nLoss m γ) μ A N τ) ∧
        (∃ (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
            (_ : IsProbabilityMeasure μ) (A : AdaptiveAlg (NCoord m) Ω),
          A.IsExact ∧ A.IsRaw (nDictionary m) ∧ A.IsMeasurable ∧
          noisyRegret (nBox m) (nLoss m γ) μ A N τ ≤ ENNReal.ofReal (γ / m * min τ (1 / 4)))) ∧
      -- the lower bounds for `N ≥ 2` use one fixed corrupted response for each raw site
      (∃ θ₁ ∈ nBox m, ∃ θ₂ ∈ nBox m, ∃ y : AffQuery (NCoord m) → ℝ,
        (∀ q ∈ nDictionary m, |y q - affEval q θ₁| ≤ τ ∧ |y q - affEval q θ₂| ≤ τ) ∧
        (∀ (N : ℕ) (A : AdaptiveAlg (NCoord m) Unit), A.IsExact → A.IsRaw (nDictionary m) →
          γ / m * min (2 * τ) (1 / 2) ≤
            max (nLoss m γ (A.decisionWith (fun _ q => y q) N ()) θ₁)
              (nLoss m γ (A.decisionWith (fun _ q => y q) N ()) θ₂)) ∧
        (∀ (N : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
            [IsProbabilityMeasure μ] (A : AdaptiveAlg (NCoord m) Ω),
          A.IsExact → A.IsRaw (nDictionary m) → A.IsMeasurable →
          ENNReal.ofReal (γ / m * min τ (1 / 4)) ≤
            max (∫⁻ ω, ENNReal.ofReal (nLoss m γ (A.decisionWith (fun _ q => y q) N ω) θ₁) ∂μ)
              (∫⁻ ω, ENNReal.ofReal (nLoss m γ (A.decisionWith (fun _ q => y q) 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 15 and eq. (82), p.46 (PDF p.49); error model §L.3, p.45 (PDF p.48); proof in Appendix Q

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me