Theorem 5.1 — every -dimensional geometric class is learnable with queries by a deterministic learner that does not know
OpenSortingCounterexamples.Optimal.Supplement.theorem_5_1There is an absolute constant with the following property. Let and , let , and let be a finite class of rankings of the items such that every is induced by some direction (that is, ). Then there is a deterministic learner , which may depend on , , and but not on , whose queries are arbitrary linear orders of the items (not necessarily in ), such that for every , every target and every adaptive oracle whose counterexamples to include at most untruthful ones for , obtains approval after
queries, the approved query included.
This is the upper half of Theorem 1.2: in a low-dimensional geometric class the number of queries depends on the dimension and only logarithmically on .
Formalization Note The query count lives in , with when the oracle never approves, so the bound also asserts termination. For and no strict ranking is induced and the statement is vacuous, as in the source.
Differences from the source:
- reading: O(d² log n + dk) for n items, no explicit domain → n ≥ 2, every d and every k ≥ 0; reason: at n = 1 the rate d² log 1 + dk vanishes for k = 0 while one query is always made; the base goal uses the same domain
- encoding: can be learned using O(d² log n + dk) queries → ∃ C > 0 before n, d, v, H; a learner chosen after H and v and before k, σ and the oracle with Q ≤ ofReal (C · (d² log n + d k)); reason: this is the meaning of an O bound uniform in all parameters for a learner that does not know k; natural logarithm
- encoding: at most k untruthful counterexamples → every transcript of the run of A against the oracle has at most k lies for σ; reason: this is exactly every adaptive response path with at most k lies against the deterministic learner
import Mathlib import Definitions.Def_SortingCounterexamples_Optimal_Protocol import Definitions.Def_SortingCounterexamples_Optimal_Supplement_Geometric open scoped ENNReal
namespace SortingCounterexamples.Optimal.Supplement
open SortingCounterexamples.Optimal
/-- Theorem 5.1: there is an absolute `C > 0` such that for every `n ≥ 2`, every `d`, every
`d`-dimensional geometric class `H` of rankings of `n` items with representation `v`, there is
one deterministic learner (its queries are arbitrary linear orders, not necessarily in `H`),
chosen before and independently of `k`, which for every `k`, every target `σ ∈ H` and every
oracle returning at most `k` untruthful counterexamples along the run obtains approval within
`C (d² log n + d k)` queries. -/
theorem theorem_5_1 :
∃ C : ℝ, 0 < C ∧ ∀ (n d : ℕ), 2 ≤ n → ∀ (v : Fin n → Fin d → ℝ) (H : Finset (Ranking n)),
IsGeometricClass v H → ∃ A : DetLearner n, ∀ k : ℕ, ∀ σ ∈ H, ∀ O : Oracle n,
RunAdmissible A O σ k →
((queries A O : ℕ∞) : ℝ≥0∞) ≤ ENNReal.ofReal (C * upperRate n d k) := by sorry
end SortingCounterexamples.Optimal.Supplement