(C.15), p.26 — the rate at
ProvedPLIAG.eq_C_15bregman-distanceconvex-optimizationincremental-gradientp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , , , let be monotonically increasing with , let be given by (4.5), and write for the condition number. Then
- ;
- ;
- for every , ;
- for every , by Bernoulli's inequality,
Combined with (4.7), this gives the explicit rate (4.10) of Theorem 4.2 in terms of the condition number and the delay.
Differences from the source:
- generalization: L = max_{k≥0} Σ_{j∈J_k} L_j → any real L > 0; reason: the paper’s L is positive, so the statement specializes to it
- 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)
- encoding: condition number Q := L/μ → L / μ (the letter Q names the constraint set); reason: notation only
Preamble
import Mathlib import Definitions.Def_PLIAG_alpha0
Formal statement
namespace PLIAG
/-- **(C.15): the rate at `α = α_0`** (Zhang–Dai–Guo–Peng, arXiv:1711.01136v3, proof of
Theorem 4.2, p.26). With `κ := L/μ` (the paper's condition number `Q`):
1. `1/(1 + α_0 μ) = (1 + 1/(ℓ(τ+1)κ))^{−1/(τ+1)}`;
2. `(1 + 1/(ℓ(τ+1)κ))^{−1/(τ+1)} = (1 − 1/(1 + ℓ(1+τ)κ))^{1/(τ+1)}`;
3. `(1/(1 + α_0 μ))^k = (1 − 1/(1 + ℓ(τ+1)κ))^{k/(τ+1)}` for all `k`;
4. `(1/(1 + α_0 μ))^k ≤ (1 − 1/([1 + ℓ(τ+1)κ](τ+1)))^k` for all `k` (Bernoulli).
**Formalization Note.** `κ` is written `L / μ` (the letter `Q` names the constraint set
elsewhere); `L > 0` is any real (in the paper `L = max_k Σ_{j∈J_k} L_j`), `μ > 0`, `ℓ` monotone
with `ℓ(1) = 1`. Real powers are `Real.rpow`. -/
theorem eq_C_15 (μ L : ℝ) (ℓ : ℕ → ℝ) (τ : ℕ) (hμ : 0 < μ) (hL : 0 < L)
(hℓm : Monotone ℓ) (hℓ1 : ℓ 1 = 1) :
1 / (1 + alpha0 μ L ℓ τ * μ) =
(1 + 1 / (ℓ (τ + 1) * (L / μ))) ^ (-(1 : ℝ) / ((τ : ℝ) + 1)) ∧
(1 + 1 / (ℓ (τ + 1) * (L / μ))) ^ (-(1 : ℝ) / ((τ : ℝ) + 1)) =
(1 - 1 / (1 + ℓ (1 + τ) * (L / μ))) ^ ((1 : ℝ) / ((τ : ℝ) + 1)) ∧
(∀ k : ℕ, (1 / (1 + alpha0 μ L ℓ τ * μ)) ^ k =
(1 - 1 / (1 + ℓ (τ + 1) * (L / μ))) ^ ((k : ℝ) / ((τ : ℝ) + 1))) ∧
(∀ k : ℕ, (1 / (1 + alpha0 μ L ℓ τ * μ)) ^ k ≤
(1 - 1 / ((1 + ℓ (τ + 1) * (L / μ)) * ((τ : ℝ) + 1))) ^ k) := 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, (C.15), proof of Theorem 4.2, p.26
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.