(4.16) — one inexact step decreases by
ProvedDynSampleSize.Det.eq_4_16gradient-methodsinexact-gradientp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be twice continuously differentiable with Hessian bounds for all , where (assumption (4.2)). Let , let be arbitrary vectors of , and let be generated by the fixed-step iteration (4.1) with steplength (4.7),
If at iteration the approximate gradient satisfies (4.8), , then
This is the sufficient-decrease estimate that summarizes the chain (4.15). Combined with (4.5) it yields the contraction (4.9).
Formalization Note Only (4.8) at the single index is assumed. The iterates are any sequence satisfying the recursion for every ; is beta θ.
Preamble
import Mathlib import Definitions.Def_DynSampleSize_Det_Setting open Filter Topology
Formal statement
namespace DynSampleSize.Det
theorem eq_4_16 {m : ℕ} (J : EuclideanSpace ℝ (Fin m) → ℝ) (lam L : ℝ)
(hJ : HessianBounds J lam L) (θ : ℝ) (hθ0 : 0 < θ) (hθ1 : θ < 1)
(g w : ℕ → EuclideanSpace ℝ (Fin m))
(hw : ∀ k, w (k + 1) = w k - ((1 - θ) / L) • g k) (k : ℕ)
(h48 : ‖g k - gradient J (w k)‖ ≤ θ * ‖g k‖) :
J (w (k + 1)) ≤ J (w k) - beta θ / L * ‖gradient J (w k)‖ ^ 2 := by sorry
end DynSampleSize.Det
Source
Byrd, Chin, Nocedal, Wu, Sample size selection in optimization methods for machine learning, Math. Program. (2012), doi:10.1007/s10107-012-0572-5 — authors' version of 18 Oct 2011, p. 9, (4.15)–(4.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.