Theorem 5.4 — for every some -dimensional geometric class forces expected queries
OpenSortingCounterexamples.Optimal.Supplement.theorem_5_4There is an absolute constant such that for all integers there are vectors and a finite class of rankings of the items, each induced by some direction , with the following property, where is chosen before and before the learner. For every and every randomized learner whose queries are linear orders (seed from an arbitrary probability space , each decision measurable in ; the learner may know and , and its queries need not lie in ) there are a target , fixed independently of the seed, and an oracle returning at most untruthful counterexamples for against every sequence of queries, such that
where is the number of queries until approval.
This is the lower half of Theorem 1.2: the dependence on of Theorem 5.1 is tight, and a factor remains open in the noiseless term.
Formalization Note The expectation is a lower Lebesgue integral in , so a learner that fails to terminate with positive probability has infinite cost; it is not excluded by an assumption.
Differences from the source:
- encoding: Ω(d log n + dk) worst-case expected query complexity → ∃ c > 0 before n, d, the class, k and the learner; ∃ σ ∈ H and an oracle with ofReal (c · (d log n + d k)) ≤ ∫⁻ Q dμ; reason: this is the meaning of an Ω bound on the worst case over targets in the class and oracles, uniform in all parameters; natural logarithm
- encoding: possibly randomized learner whose queries are linear orders → a family of deterministic learners indexed by a seed of a probability space (Ω : Type), decisions measurable in the seed; reason: drawing all private randomness at the start covers every randomized learner; measurability is needed for the expectation to exist
- encoding: in the presence of at most k untruthful counterexamples → a deterministic transcript-dependent oracle with at most k lies against every query sequence; reason: the source's hard oracles are of this kind; requiring validity against every query sequence only strengthens the existence claim
import Mathlib import Definitions.Def_SortingCounterexamples_Optimal_Protocol import Definitions.Def_SortingCounterexamples_Optimal_Supplement_Geometric open MeasureTheory open scoped ENNReal
namespace SortingCounterexamples.Optimal.Supplement
open SortingCounterexamples.Optimal
/-- Theorem 5.4: there is an absolute `c > 0` such that for every `2 ≤ d ≤ n` there is a
`d`-dimensional geometric class `H` of rankings of `n` items (with a representation `v`),
chosen before `k` and the learner, such that for every `k` and every randomized learner whose
queries are linear orders there are a fixed target `σ ∈ H` and an oracle with at most `k`
untruthful counterexamples against every query sequence forcing expected number of queries at
least `c (d log n + d k)`. -/
theorem theorem_5_4 :
∃ c : ℝ, 0 < c ∧ ∀ (n d : ℕ), 2 ≤ d → d ≤ n →
∃ (v : Fin n → Fin d → ℝ) (H : Finset (Ranking n)), IsGeometricClass v H ∧
∀ k : ℕ, ∀ (Ω : Type) [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(L : Ω → DetLearner n), IsRandomizedLearner L →
∃ σ ∈ H, ∃ O : Oracle n, Admissible O σ k ∧
ENNReal.ofReal (c * lowerRate n d k) ≤
∫⁻ ω, ((queries (L ω) O : ℕ∞) : ℝ≥0∞) ∂μ := by sorry
end SortingCounterexamples.Optimal.Supplement