Theorem 2(a), corrected — for under the restricted Gauss–Seidel rule
ProvedTsengCGD.Linear.theorem2_aFix and constants , . There is a constant , depending only on , , , , with the following property. Consider any instance of problem (1) (with its standing assumptions) in which is -Lipschitz on (22), and any run of the CGD method with iterates in , satisfying Assumption 1 with , with chosen by the restricted Gauss–Seidel rule (12) along , and with block-separable with respect to every . If the stepsizes are bounded, for all , then for every
The paper states without the block-separability hypothesis; we state the corrected form above. As printed, the bound fails twice. (1) With , , , , and constant stepsizes , it reads , false for ; the paper's proof gives the factor . (2) With , , there, , , alternating blocks and , every coordinate step is blocked, so while ; the proof splits over the blocks, which needs block-separability, as Theorem 2(b) assumes. Where the theorem is used, in (b), and is block-separable, so (b) is unaffected.
The bound controls the optimality residual at the start of each Gauss–Seidel cycle by the length of the steps taken during the cycle; combined with the error bound (Assumption 2(a)) it drives the linear rate of Theorem 2(b).
Formalization Note The constant is quantified before the problem data, the run and , so it is uniform (it may depend on , which is fixed). is replaced by an explicit upper bound . The hypothesis for all is the domain of the method (the subproblem (6) is posed at , and the proof uses ); with it follows from convexity. is a strictly increasing map with , and . is the full direction (13) with .
import Mathlib import Definitions.Def_TsengCGD_Linear_Basic open Filter Topology Finset Matrix open scoped RealInnerProductSpace
namespace TsengCGD.Linear
theorem theorem2_a {n : ℕ} (L lam lamBar : ℝ) :
∃ C > 0, ∀ (f : TsengCGD.Global.Vec n → ℝ) (D : Set (TsengCGD.Global.Vec n)) (P : TsengCGD.Global.Vec n → ℝ) (c : ℝ)
(J : ℕ → Finset (Fin n)) (H : ℕ → Matrix (Fin n) (Fin n) ℝ)
(x d : ℕ → TsengCGD.Global.Vec n) (α : ℕ → ℝ) (t : ℕ → ℕ),
TsengCGD.Global.Standing f D P c → GradLipOn f D L → TsengCGD.Global.IsCGDRun f D P c J H x d α →
(∀ k, x k ∈ D) → TsengCGD.Global.Assumption1 H lam lamBar → RestrictedGaussSeidel J t →
(∀ k, TsengCGD.Global.BlockSeparable D P (J k)) →
∀ abar : ℝ, (∀ j, α j ≤ abar) →
∀ i, ‖TsengCGD.Global.dI f D P c (x (t i))‖ ≤ max 1 abar * C * r t d i := by sorry
end TsengCGD.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.