Error bound for oriented bisection
ProvedQuantumLTF.Membership.orientedBisectValue_errorapproximationbinary-searchlearning-theory
Starting from an interval containing the threshold , after orientation-aware bisection updates the returned midpoint differs from by at most . The statement handles both positive and negative orientations.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_orientedBisectValue
Formal statement
namespace QuantumLTF.Membership
/-- After `q` oriented bisection updates, the returned midpoint has exponentially small error. -/
theorem orientedBisectValue_error (s : ℤ) (q : ℕ) (lo hi h : ℝ)
(hlo : lo ≤ h) (hhi : h ≤ hi) :
|orientedBisectValue s q lo hi h - h| ≤
(hi - lo) / (2 : ℝ) ^ (q + 1) := by sorry
end QuantumLTF.MembershipSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Theorem 3.1, pp. 21–22 (PDF pp. 22–23).