Proof of Theorem 4.2, p.25 —
ProvedPLIAG.alpha0_boundbregman-distanceconvex-optimizationincremental-gradientp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the constants of B1, let every block be nonempty, , , and let be monotonically increasing with . Then the step-size bound of (4.5) satisfies
This is the first step of the proof of Theorem 4.2: it shows that every step meets the step-size condition of Proposition 3.1, so the PLIAG iterates are well defined.
Differences from the source:
- encoding: L := max_{k≥0} Σ_{j∈J_k} L_j → Lmax Lc J := ⨆ k, Σ_{j ∈ J k} Lc j (real supremum); reason: the family takes finitely many values, so the supremum is the maximum
- encoding: ℓ monotonically increasing with ℓ(1) = 1 (introduced by B4 when τ > 0; ℓ(τ+1) = ℓ(1) = 1 when τ = 0) → ℓ : ℕ → ℝ with Monotone ℓ and ℓ 1 = 1 always; reason: when τ = 0 only ℓ(1) = 1 enters; ℓ(0) is never read and a monotone ℓ on the positive integers extends by ℓ(0) := ℓ(1)
Preamble
import Mathlib import Definitions.Def_PLIAG_Lmax import Definitions.Def_PLIAG_alpha0
Formal statement
namespace PLIAG
/-- **Step-size bound in the proof of Theorem 4.2** (Zhang–Dai–Guo–Peng, arXiv:1711.01136v3,
proof of Theorem 4.2, p.25): by the definition of `L` and Bernoulli's inequality,
`α_0 ≤ 1/(ℓ(τ+1)·(τ+1)·L) ≤ 1/Σ_{j ∈ J_k} L_j` for all `k ≥ 0`.
**Formalization Note.** `L = Lmax Lc J`; the constants `L_j > 0` (B1), `J_k ≠ ∅` (step (ii)),
`μ > 0` (B3), `ℓ` monotone with `ℓ(1) = 1` (B4). Both inequalities are stated. -/
theorem alpha0_bound {N : ℕ} (Lc : Fin N → ℝ) (J : ℕ → Finset (Fin N)) (μ : ℝ) (ℓ : ℕ → ℝ)
(τ : ℕ) (hLc : ∀ n, 0 < Lc n) (hJ : ∀ k, (J k).Nonempty) (hμ : 0 < μ)
(hℓm : Monotone ℓ) (hℓ1 : ℓ 1 = 1) :
alpha0 μ (Lmax Lc J) ℓ τ ≤ 1 / (ℓ (τ + 1) * ((τ : ℝ) + 1) * Lmax Lc J) ∧
∀ k : ℕ, 1 / (ℓ (τ + 1) * ((τ : ℝ) + 1) * Lmax Lc J) ≤ 1 / ∑ j ∈ J k, Lc j := by sorry
end PLIAG
Source
Zhang, Dai, Guo, Peng, Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence under Bregman Distance Growth Conditions, arXiv:1711.01136v3, proof of Theorem 4.2, p.25
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.