Claim 4.10 — uniform estimation of monotone functions from noisy queries
ProvedBilateralProfit.claim_4_10There is an absolute constant with the following property. Let be a finite totally ordered set and a finite family of functions, each defined on a subset , monotone (non-decreasing or non-increasing) on , with values in , and with total variations satisfying for a known constant . For each and , the -th query at reveals the -th variable of a sequence of mutually independent random variables with expectation and values in a common interval of length at most . Then for every there is a procedure, depending only on , the domains , , and , that makes at most
queries on every run and, with probability at least , outputs estimates with for every and .
In the proof of Lemma 4.8 this is applied to the monotone pieces of the telescoping decomposition (21).
Formalization Note is indexed by a finite type; the procedure is a deterministic adaptive routine that queries only pairs with . is the variation on . The common interval is .
Differences from the source:
- generalization: a set of functions → a finite family indexed by a type (repetitions allowed); reason: an injective indexing is the paper's set; a family with repetitions is estimated by treating each index separately
- reading: "there exists a procedure" using at most the stated number of queries; an absolute constant → a deterministic adaptive routine chosen from before the functions and the observation laws, querying only inside the domains, with the query bound on every run; chosen first; reason: the proof's procedure is deterministic, queries domain points only, and is forced to halt deterministically after the bound (80) (p.58)
- encoding: a known constant with → hypothesis ; reason: total variations are non-negative, so for the hypothesis has no instance; the Lean order states the query bound before the functions
- encoding: values in a common interval of length at most ; probability at least → laws carried by for one ; the routine's success probability; reason: same instances; probabilities in
import Mathlib import Definitions.Def_BilateralProfit_QueryRoutine
namespace BilateralProfit
open MeasureTheory
/-- **Claim 4.10**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256 e91e8127…), p.27
(PDF 29), proof in App. A.4, pp.57–58: uniform estimation of monotone functions.
Let `G` be a finite family of monotone functions `g`, each defined on a subset of a finite
ordered domain `Y` with values in `[−1, 1]`, with `Σ_{g ∈ G} TV(g) ≤ W` for a known constant `W`.
Each query at `g(y)` reveals the next unused variable of a sequence of mutually independent
random variables with expectation `g(y)` and values in a common interval of length at most `4`.
Then for `α, δ′ ∈ (0, 1)` there is a procedure that estimates every function uniformly to error
`α`, simultaneously with probability at least `1 − δ′`, using at most
`C log(2|G||Y|/δ′)/α² · (|G| + (W/α) log(2|Y|))` queries, `C` an absolute constant.
**Formalization Note.** `G` is indexed by a finite type `ι`; `dom i ⊆ Y` is the (known) domain of
the `i`-th function. The procedure is a routine `R` (`QTree`) chosen from `ι, Y, dom, W, α, δ′`
only; it queries pairs `(i, y)` with `y ∈ dom i`, at most `N` times on every run, and works for
every family `g` and every observation law with the stated properties. "Monotone" is
non-decreasing or non-increasing on the domain; `TV(g)` is `eVariationOn` on the domain. The
common interval is `[c, c + 4]` for some `c`. `0 ≤ W` (a bound on a sum of total variations). -/
theorem claim_4_10 :
∃ C : ℝ, ∀ (ι Y : Type) [Fintype ι] [DecidableEq ι] [Fintype Y] [LinearOrder Y]
(dom : ι → Finset Y) (W α δ : ℝ), 0 ≤ W → 0 < α → α < 1 → 0 < δ → δ < 1 →
∃ (R : QTree (ι × Y) (ι → Y → ℝ)) (N : ℕ),
(N : ℝ) ≤ C * Real.log (2 * Fintype.card ι * Fintype.card Y / δ) / α ^ 2 *
(Fintype.card ι + W / α * Real.log (2 * Fintype.card Y)) ∧
R.QueriesAtMost N ∧ R.AllQueries (fun q => q.2 ∈ dom q.1) ∧
∀ g : ι → Y → ℝ, (∀ i, ∀ y ∈ dom i, g i y ∈ Set.Icc (-1 : ℝ) 1) →
(∀ i, MonotoneOn (g i) ↑(dom i) ∨ AntitoneOn (g i) ↑(dom i)) →
∑ i, (eVariationOn (g i) ↑(dom i)).toReal ≤ W →
∀ (c : ℝ) (obs : ι × Y → ℕ → Measure ℝ),
(∀ i, ∀ y ∈ dom i, ∀ n, IsProbabilityMeasure (obs (i, y) n)) →
(∀ i, ∀ y ∈ dom i, ∀ n, obs (i, y) n (Set.Icc c (c + 4))ᶜ = 0) →
(∀ i, ∀ y ∈ dom i, ∀ n, ∫ r, r ∂(obs (i, y) n) = g i y) →
ENNReal.ofReal (1 - δ) ≤
R.prob obs (fun est => ∀ i, ∀ y ∈ dom i, |est i y - g i y| ≤ α) (fun _ => 0) := by sorry
end BilateralProfit
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.