Lemma 4 — Hölder-type Lipschitz dependence of the coordinate subproblem's minimizer on the linear term
ProvedTsengCGD.Linear.lemma4Let and let be proper, convex and lower semicontinuous. Let be continuously differentiable and satisfy, for some and ,
and let be the conjugate exponent, . Fix , a nonempty index set , and two vectors . Let minimize and minimize , both over the vectors with for . Then
The lemma says that the coordinate subproblem's solution moves Hölder-continuously with its linear coefficients; with , , it is the 1-Lipschitz dependence of on that the proof of Theorem 2(a) uses.
Formalization Note is the pair with . A minimizer is a vector supported on with and objective value no larger than that of any other such vector (the others have value ); the bound is asserted for every pair of minimizers, which is the paper's statement since the minimizers are unique. Coordinates are 0-based (Fin n), and , are the explicit sums of rpows, of nonnegative bases.
import Mathlib import Definitions.Def_TsengCGD_Linear_Basic open Filter Topology Finset Matrix open scoped RealInnerProductSpace
namespace TsengCGD.Linear
theorem lemma4 {n : ℕ} (D : Set (TsengCGD.Global.Vec n)) (P : TsengCGD.Global.Vec n → ℝ) (c : ℝ)
(hP : ProxNewton.Inexact.IsProperClosedConvex D P) (hc : 0 < c)
(h : TsengCGD.Global.Vec n → ℝ) (hh : ContDiff ℝ 1 h) (ρ p q : ℝ) (hρ : 0 < ρ) (hp : 1 < p)
(hq : 1 / p + 1 / q = 1)
(hmono : ∀ u v : TsengCGD.Global.Vec n, ρ * pNorm p (u - v) ^ p ≤ ⟪gradient h u - gradient h v, u - v⟫)
(x : TsengCGD.Global.Vec n) (hx : x ∈ D) (J : Finset (Fin n)) (hJ : J.Nonempty) (gb gt db dt : TsengCGD.Global.Vec n)
(hdb : TsengCGD.Global.SupportedOn J db ∧ x + db ∈ D ∧ ∀ d', TsengCGD.Global.SupportedOn J d' → x + d' ∈ D →
⟪gb, db⟫ + h db + c * P (x + db) ≤ ⟪gb, d'⟫ + h d' + c * P (x + d'))
(hdt : TsengCGD.Global.SupportedOn J dt ∧ x + dt ∈ D ∧ ∀ d', TsengCGD.Global.SupportedOn J d' → x + d' ∈ D →
⟪gt, dt⟫ + h dt + c * P (x + dt) ≤ ⟪gt, d'⟫ + h d' + c * P (x + d')) :
pNorm p (db - dt) ≤ ρ ^ (-q / p) * pNormOn q J (gb - gt) ^ (q / p) := by sorry
end TsengCGD.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.