Lemma 13 — the matrix square root is operator monotone
ProvedAdaGrad.Full.lemma_13matrix-analysisoperator-monotonep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be real symmetric matrices with (Loewner order: and positive semidefinite). Then their positive semidefinite square roots satisfy
The paper uses it to see that is non-decreasing in (so the proximal functions of Figure 2 grow) and inside the proofs of Lemmas 8 and 9.
Formalization Note is Mathlib's CFC.sqrt. Mathlib proves this monotonicity (CFC.sqrt_le_sqrt) only in C*-algebras, which covers complex matrices but not real ones, so the real case is posed here.
Preamble
import Mathlib import Definitions.Def_AdaGrad_Full_Algorithm2 open scoped MatrixOrder InnerProductSpace
Formal statement
namespace AdaGrad.Full
/-- Lemma 13 (p. 2148): the matrix square root is monotone for the Loewner order on real symmetric
positive semidefinite matrices: `A ⪰ B ⪰ 0` implies `A^{1/2} ⪰ B^{1/2}`. -/
theorem lemma_13 {d : ℕ} (A B : Matrix (Fin d) (Fin d) ℝ) (hB : B.PosSemidef)
(hAB : (A - B).PosSemidef) : (CFC.sqrt A - CFC.sqrt B).PosSemidef := by sorry
end AdaGrad.Full
Source
Duchi, Hazan, Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 12 (2011), p. 2148, Lemma 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.