Appendix H, p. 23 — (1/d) Σ_i min_t [t∇_i f(x) + (L/2)t² + g_i(x_i + t) − g_i(x_i)] = −(1/(2Ld)) D_g(x, L)
ProvedKarimiPL.ProxCD.expected_improvement_eqcoordinate-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradientseparable
Let , , , and let with each convex. Then for every ,
where .
The left side is the expected best one-coordinate improvement of the upper model when the coordinate is drawn uniformly. Separability of lets the sum of the coordinate minima be exchanged with the minimum over the full vector .
Formalization Note Minima are real infima; both are attained because the are convex and . The page writes for the dimension and for .
Preamble
import Mathlib import Definitions.Def_KarimiPL_ProxCD_Setting open InnerProductSpace
Formal statement
namespace KarimiPL.ProxCD
theorem expected_improvement_eq {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ) (L : ℝ) (hL : 0 < L)
(gs : Fin d → ℝ → ℝ) (hgs : ∀ i, ConvexOn ℝ Set.univ (gs i)) :
∀ x : KarimiPL.Rel.E d, (1 / (d : ℝ)) * ∑ i, (⨅ t : ℝ, coordModel f gs L x i t)
= -(1 / (2 * L * d)) * Dg f (sepSum gs) x L := by sorry
end KarimiPL.ProxCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Appendix H, display between (62) and (63), p. 23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.