(4.4) —
ProvedNesterovRCD.Constrained.eq_4_4In the setting of §4 — with each nonempty, closed and convex, Euclidean block norms (3.4), and convex with coordinate-wise Lipschitz gradient (2.2), constants — let and be the constrained coordinate update (4.2). Then for every feasible point and every block ,
Each step of the constrained method therefore does not increase the objective, and decreases it in proportion to the squared length of the step. It makes the expected values of UCDM nonincreasing.
Formalization Note The paper writes for in the derivation (a typo). The hypothesis is implicit in the paper, whose derivation substitutes into (4.3), which requires ; it is stated. The standing assumptions of §4 are stated as for (4.3), together with and . Indices are Fin n, 0-based.
import Mathlib import Definitions.Def_NesterovRCD_HighProb_Basic import Definitions.Def_NesterovRCD_Constrained_UCDM
namespace NesterovRCD.Constrained
variable {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)] [∀ i, InnerProductSpace ℝ (E i)]
[∀ i, FiniteDimensional ℝ (E i)]
theorem eq_4_4 (hn : 0 < n) (f : NesterovRCD.Sublinear.Blocks E → ℝ) (L : Fin n → ℝ)
(hf : ConvexOn ℝ Set.univ f) (hL : NesterovRCD.Sublinear.CoordLipschitz f L)
(Q : ∀ i, Set (E i)) (hQc : ∀ i, IsClosed (Q i)) (hQv : ∀ i, Convex ℝ (Q i))
(hQne : ∀ i, (Q i).Nonempty) (x : NesterovRCD.Sublinear.Blocks E) (hx : x ∈ Qset Q) (i : Fin n) :
L i / 2 * ‖blockUpdate f L Q x i - x i‖ ^ 2 ≤ f x - f (constrStep f L Q i x) := by sorry
end NesterovRCD.Constrained
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.