Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Claim 4.10 — uniform estimation of monotone functions from noisy queries

Proved
BilateralProfit.claim_4_10

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

bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-bounds

There is an absolute constant CCC with the following property. Let YYY be a finite totally ordered set and GGG a finite family of functions, each g∈Gg\in Gg∈G defined on a subset Yg⊆YY_g\subseteq YYg​⊆Y, monotone (non-decreasing or non-increasing) on YgY_gYg​, with values in [−1,1][-1,1][−1,1], and with total variations satisfying ∑g∈GTV(g)≤W\sum_{g\in G}\mathrm{TV}(g)\le W∑g∈G​TV(g)≤W for a known constant WWW. For each ggg and y∈Ygy\in Y_gy∈Yg​, the nnn-th query at g(y)g(y)g(y) reveals the nnn-th variable Zg,y(n)Z^{(n)}_{g,y}Zg,y(n)​ of a sequence of mutually independent random variables with expectation g(y)g(y)g(y) and values in a common interval of length at most 444. Then for every α,δ′∈(0,1)\alpha,\delta'\in(0,1)α,δ′∈(0,1) there is a procedure, depending only on YYY, the domains YgY_gYg​, WWW, α\alphaα and δ′\delta'δ′, that makes at most

C log⁡(2∣G∣∣Y∣/δ′)α2(∣G∣+Wαlog⁡(2∣Y∣))C\,\frac{\log(2|G||Y|/\delta')}{\alpha^2}\Big(|G|+\frac W\alpha\log(2|Y|)\Big)Cα2log(2∣G∣∣Y∣/δ′)​(∣G∣+αW​log(2∣Y∣))

queries on every run and, with probability at least 1−δ′1-\delta'1−δ′, outputs estimates g^\hat gg^​ with ∣g^(y)−g(y)∣≤α|\hat g(y)-g(y)|\le\alpha∣g^​(y)−g(y)∣≤α for every g∈Gg\in Gg∈G and y∈Ygy\in Y_gy∈Yg​.

In the proof of Lemma 4.8 this is applied to the monotone pieces of the telescoping decomposition (21).

Formalization Note GGG is indexed by a finite type; the procedure is a deterministic adaptive routine that queries only pairs (g,y)(g,y)(g,y) with y∈Ygy\in Y_gy∈Yg​. TV\mathrm{TV}TV is the variation on YgY_gYg​. The common interval is [c,c+4][c,c+4][c,c+4].

Differences from the source:

  • generalization: a set GGG of functions → a finite family indexed by a type ι\iotaι (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; CCC an absolute constant → a deterministic adaptive routine chosen from (ι,Y,domains,W,α,δ′)(\iota,Y,\text{domains},W,\alpha,\delta')(ι,Y,domains,W,α,δ′) before the functions and the observation laws, querying only inside the domains, with the query bound on every run; CCC 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: WWW a known constant with ∑gTV(g)≤W\sum_g\mathrm{TV}(g)\le W∑g​TV(g)≤W → hypothesis 0≤W0\le W0≤W; reason: total variations are non-negative, so for W<0W<0W<0 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 444; probability at least 1−δ′1-\delta'1−δ′ → laws carried by [c,c+4][c,c+4][c,c+4] for one ccc; ofReal(1−δ′)≤\mathrm{ofReal}(1-\delta')\leofReal(1−δ′)≤ the routine's success probability; reason: same instances; probabilities in [0,∞][0,\infty][0,∞]
Preamble
import Mathlib
import Definitions.Def_BilateralProfit_QueryRoutine
Formal statement
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
Source
Brüstle, di Gregorio, Fusco, Leonardi, Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism (manuscript, STOC 2027 submission, sha256 e91e81279505b765c7c96c219d674c0fbbbd6ca47a00da8fe228d498ca25ac87), Claim 4.10, p.27 (PDF 29); proof in App. A.4, pp.57–58 (PDF 59–60)
Human review
  • Endorsed by Shuze Chen · Nov 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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