Equation (2.28) — selected-gradient deterministic inequality
ProvedGhadimiLan.TwoPhase.eq_2_28inequalitiesnonconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the true gradients at candidates, and their estimated gradients. Choose any minimizing . Then
This deterministic relation connects the selected candidate to the best true gradient and to estimation errors.
Formalization Note The finite minimum and maximum are taken over the nonempty candidate set Fin S; the vectors abstract the paper's and .
Preamble
import Mathlib import Definitions.Def_GhadimiLan_TwoPhase_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace GhadimiLan.TwoPhase
/-- Equation (2.28), p. 12, abstracted from candidate gradients and estimates. -/
theorem eq_2_28 {n S : ℕ} (hS : 0 < S)
(a b : Fin S → GhadimiLan.RSG.E n) (sStar : Fin S)
(hmin : ∀ s, ‖b sStar‖ ≤ ‖b s‖) :
‖a sStar‖ ^ 2 ≤
4 * (Finset.univ : Finset (Fin S)).inf'
(by exact ⟨⟨0, hS⟩, Finset.mem_univ _⟩) (fun s => ‖a s‖ ^ 2) +
4 * (Finset.univ : Finset (Fin S)).sup'
(by exact ⟨⟨0, hS⟩, Finset.mem_univ _⟩) (fun s => ‖b s - a s‖ ^ 2) +
2 * ‖a sStar - b sStar‖ ^ 2 := by sorry
end GhadimiLan.TwoPhase
Source
Ghadimi & Lan, arXiv:1309.5549v1, Eq. (2.28), proof of Theorem 2.4(a), p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.