Dyadic parameter selection for boundary estimation
ProvedQuantumLTF.Membership.theorem_3_1_parameterslearning-theoryreal-analysis
There is an absolute positive constant such that, for every admissible accuracy pair ε and ζ, the dyadic scale L has an exponent m and one can choose a bisection count q for which both q+2 and m+q+2 are bounded by the logarithmic target, while the final midpoint error is at most ζ.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_Leps
Formal statement
theorem QuantumLTF.Membership.theorem_3_1_parameters :
∃ C : ℝ, 0 < C ∧ ∀ ε ζ : ℝ, 0 < ε → ε ≤ 1 / 2 → 0 < ζ → ζ < 1 →
∃ m q : ℕ,
Leps ε = (2 : ℝ) ^ m ∧
((q + 2 : ℕ) : ℝ) ≤ C * Real.log (Leps ε / ζ) ∧
((m + q + 2 : ℕ) : ℝ) ≤ C * Real.log (Leps ε / ζ) ∧
2 * Leps ε / (2 : ℝ) ^ (q + 1) ≤ ζ := by sorrySource
Quantitative parameter selection in Theorem 3.1 of Fast Quantum Algorithms for Learning Linear Threshold Functions