Lemma 2.1 — Gaussian disagreement of LTFs
ProvedQuantumLTF.Membership.lemma_2_1linear-threshold-functionsmembership-queriesp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-learning
Let and . Then
and, in the homogeneous case ,
The first bound turns parameter error into classification error. It is the last step of the learner's analysis.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_ltf import Definitions.Def_QuantumLTF_Membership_disagree
Formal statement
namespace QuantumLTF.Membership
/-- **Lemma 2.1 (Gaussian disagreement of LTFs).** Krivcenko, Nguyen, de Wolf, *Fast Quantum Algorithms for Learning Linear Threshold Functions*,
arXiv:2609.40331, Lemma 2.1, p. 17 (PDF p. 18), Eqs. (14), (15).
For unit `w₁, w₂` and `θ₁, θ₂`,
`Pr[f_{w₁,θ₁} ≠ f_{w₂,θ₂}] ≤ ‖w₁ − w₂‖ / 2 + |θ₁ − θ₂| / √(2π)`; and for `θ₁ = θ₂ = 0` the disagreement
equals `arccos(⟨w₁, w₂⟩) / π`.
**Formalization Note.** Both clauses are in one statement. The source puts no bound on `n`; the
sphere is empty at `n = 0`. -/
theorem lemma_2_1 {n : ℕ} (w₁ w₂ : EuclideanSpace ℝ (Fin n)) (h₁ : ‖w₁‖ = 1) (h₂ : ‖w₂‖ = 1)
(θ₁ θ₂ : ℝ) :
disagree (ltf w₁ θ₁) (ltf w₂ θ₂) ≤ ‖w₁ - w₂‖ / 2 + |θ₁ - θ₂| / Real.sqrt (2 * Real.pi) ∧
disagree (ltf w₁ 0) (ltf w₂ 0) = Real.arccos (inner ℝ w₁ w₂) / Real.pi := by sorry
end QuantumLTF.Membership
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Lemma 2.1, Eqs. (14), (15), p. 17 (PDF p. 18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.