p. 115: for A, B, Â, B̂ ∈ [0,1] with |A − Â|, |B − B̂| ≤ τ', AB − 2τ' ≤ ÂB̂ ≤ AB + 3τ'
ProvedComputationalLearning.product_estimate_errorerror-propagationestimation
p. 115. For any and that satisfy and for some , we have . Thus if we are using the product of the estimates and to estimate the product within additive error , then suffices.
Formally: the two inequalities, for reals with and .
Preamble
import Definitions.Def_ComputationalLearning_Noise open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning
/-- **Error propagation through a product** (§5.4.2, p. 115): for any `A, B ∈ [0, 1]` and
estimates `Â, B̂ ∈ [0, 1]` with `|A − Â| ≤ τ'` and `|B − B̂| ≤ τ'` for some `τ' ∈ [0, 1]`,
`AB − 2τ' ≤ ÂB̂ ≤ AB + 3τ'`; thus `τ' = τ/3` suffices to estimate a product within `τ`. -/
theorem product_estimate_error {A B Ah Bh τ' : ℝ} (hA : A ∈ Set.Icc (0 : ℝ) 1)
(hB : B ∈ Set.Icc (0 : ℝ) 1) (hAh : Ah ∈ Set.Icc (0 : ℝ) 1) (hBh : Bh ∈ Set.Icc (0 : ℝ) 1)
(hτ : τ' ∈ Set.Icc (0 : ℝ) 1) (h1 : |A - Ah| ≤ τ') (h2 : |B - Bh| ≤ τ') :
A * B - 2 * τ' ≤ Ah * Bh ∧ Ah * Bh ≤ A * B + 3 * τ' := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §5.4.2 p. 115, the error propagation through a product of estimates
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.