Result 4, p. 353 — the Gentle AdaBoost algorithm (population version) uses Newton steps for minimizing Ee^{−yF(x)}
ProvedAddLogReg.Gentle.result_4Let be a probability measure on , the joint law of , let be the current fit and fix . Write as a function of the real number , and let
Then
- is the derivative of at ;
- the derivative of at every is , and the derivative of this function at is ;
- , so the Newton step is defined;
- the population Gentle AdaBoost update (Algorithm 4: with ) is exactly the Newton step:
This is Result 4: Gentle AdaBoost replaces the exact minimization of Real AdaBoost by one Newton step on the exponential criterion at each iteration.
Formalization Note "Uses Newton steps" is pinned down as in the paper's Derivation: the update equals minus first derivative over second derivative of the conditional criterion. Derivatives are HasDerivAt statements; positivity of is proved, not assumed, so the division is never Lean's junk division by zero. The statement holds for every ; conditional expectations are integrals against ν.condKernel x.
import Mathlib import Definitions.Def_AddLogReg_Gentle_Setting open MeasureTheory ProbabilityTheory
namespace AddLogReg.Gentle
theorem result_4 {X : Type*} [MeasurableSpace X] (ν : Measure (X × Bool))
[IsProbabilityMeasure ν] (F : X → ℝ) (x : X) :
HasDerivAt (condCritAt ν F x)
(-∫ b, Real.exp (-(AddLogReg.ExpCrit.sgn b * F x)) * AddLogReg.ExpCrit.sgn b ∂(ν.condKernel x)) 0 ∧
(∀ t : ℝ, HasDerivAt (condCritAt ν F x)
(-∫ b, Real.exp (-(AddLogReg.ExpCrit.sgn b * (F x + t))) * AddLogReg.ExpCrit.sgn b ∂(ν.condKernel x)) t) ∧
HasDerivAt (fun t : ℝ => -∫ b, Real.exp (-(AddLogReg.ExpCrit.sgn b * (F x + t))) * AddLogReg.ExpCrit.sgn b ∂(ν.condKernel x))
(∫ b, Real.exp (-(AddLogReg.ExpCrit.sgn b * F x)) ∂(ν.condKernel x)) 0 ∧
0 < ∫ b, Real.exp (-(AddLogReg.ExpCrit.sgn b * F x)) ∂(ν.condKernel x) ∧
gentleStep ν F x =
F x - (-∫ b, Real.exp (-(AddLogReg.ExpCrit.sgn b * F x)) * AddLogReg.ExpCrit.sgn b ∂(ν.condKernel x)) /
(∫ b, Real.exp (-(AddLogReg.ExpCrit.sgn b * F x)) ∂(ν.condKernel x)) := by sorry
end AddLogReg.Gentle
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.