Theorem 4 — Assumption 2(a) holds if X̄ ≠ ∅ and C1, C2 or C3 holds, or if f is strongly convex with Lipschitz gradient (C4)
ProvedTsengCGD.ErrorBound.theorem4Assume the standing assumptions of problem (1): , proper, convex and lower semicontinuous, continuously differentiable on an open set containing , and . Let be the set of stationary points of and the residual (13).
Suppose that either
- and one of the conditions C1, C2, C3 of Lemma 7 holds ( polyhedral, and quadratic, or , or with strongly convex with Lipschitz gradient and polyhedral); or
- C4: is strongly convex and satisfies (22), on , for some .
Then Assumption 2(a) holds: and for every there are and such that
This is the main result of §6 of the paper: it identifies problem classes for which the linear convergence theorem of the coordinate gradient descent method applies, among them -regularized least squares and other problems with polyhedral and quadratic or composite .
Formalization Note Under C4 the conclusion includes , which is not assumed (the paper's proof notes that is then a singleton). In C4 strong convexity and (22) are required on only, which is weaker than the paper's "strongly convex" on , so the statement is at least as strong as printed. Assumption 2(a) quantifies over every real ; the paper's "" agrees with this since the condition is vacuous below . is Metric.infDist.
import Mathlib import Definitions.Def_TsengCGD_Linear_Basic import Definitions.Def_TsengCGD_ErrorBound_Conditions
namespace TsengCGD.ErrorBound
theorem theorem4 {n : ℕ} (f : TsengCGD.Global.Vec n → ℝ) (D : Set (TsengCGD.Global.Vec n)) (P : TsengCGD.Global.Vec n → ℝ) (c : ℝ)
(hs : TsengCGD.Global.Standing f D P c)
(hC : ((TsengCGD.Linear.statSet f D P c).Nonempty ∧ (C1 f D P ∨ C2 f D P ∨ C3 f D P)) ∨ C4 f D) :
TsengCGD.Linear.Assumption2a f D P c := by sorry
end TsengCGD.ErrorBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.