Theorem 3.2, p. 12 — DRS objective rates
ProvedRelaxedPRS.DRSSmooth.theorem_3_2Let be proper, closed and convex, and let be convex and differentiable with -Lipschitz gradient, . Run DRS with stepsize , start , and fixed point ; write and . Let and be the positive roots of (so ) and (), respectively. Then
For every , the best-iterate error is . If , then every and .
This is the objective convergence rate for DRS with one smooth summand.
Formalization Note DRS uses relaxation (the section's standing Assumption 5). The minimum is a nonempty finite minimum, and is a genuine little-o limit. The threshold is corrected. The page defines as the positive root of . The proof's display (3.2) needs , which in reads , so the threshold is the positive root of . With the printed the first case is false: for , , , and , the error is twice the bound. The second case holds for every with the corrected .
import Mathlib import Definitions.Def_RelaxedPRS_DRSSmooth_Setting open InnerProductSpace Filter
namespace RelaxedPRS.DRSSmooth
variable {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
/-- Theorem 3.2, p. 12: best-iterate and nonergodic DRS objective rates.
Corrected threshold: the page defines ρ as the positive root of x³ − 2x² − 1 (ρ ≈ 2.2056), but the
proof (display (3.2)) needs γ³/β − 2γβ − β² ≤ 0, i.e. t³ − 2t − 1 ≤ 0 with t = γ/β, whose positive
root is the golden ratio (≈ 1.618). With the printed ρ the first case is false: f = 0,
g(x) = x²/(2β) on ℝ, γ = 2β, k = 0 gives an error twice the bound. Here ρ is the positive root of
x³ − 2x − 1. -/
theorem theorem_3_2 (f : H → EReal)
(hf : ThreeOpSplitting.ConvexRates.IsProperClosedConvex f)
(g : H → ℝ) (β : ℝ) (hβ : 0 < β)
(hg : ThreeOpSplitting.ConvexRates.IsSmoothConvex β g)
(γ : ℝ) (hγ : 0 < γ) (Pf Pg : H → H)
(hPf : ThreeOpSplitting.ConvexRates.IsProx γ f Pf)
(hPg : ThreeOpSplitting.ConvexRates.IsProx γ (gE g) Pg)
(z : ℕ → H) (hz : RelaxedPRS.StrongCvx.IsPRSRun Pf Pg (fun _ => 1 / 2) z)
(zs : H) (hzs : RelaxedPRS.StrongCvx.TPRS Pf Pg zs = zs)
(ρ : ℝ) (hρ : 0 < ρ ∧ ρ ^ 3 - 2 * ρ - 1 = 0)
(κ : ℝ) (hκ : 0 < κ ∧ κ ^ 3 + κ ^ 2 - 2 * κ - 1 = 0) :
(γ < ρ * β → ∀ k : ℕ,
(Finset.range (k + 1)).inf' (Finset.nonempty_range_add_one) (errF f g Pf Pg z zs) ≤
‖RelaxedPRS.StrongCvx.xg Pg (z 0) - RelaxedPRS.StrongCvx.xg Pg zs‖ ^ 2 / (2 * γ * ((k : ℝ) + 1))) ∧
(ρ * β ≤ γ → ∀ k : ℕ,
(Finset.range (k + 1)).inf' (Finset.nonempty_range_add_one) (errF f g Pf Pg z zs) ≤
(‖RelaxedPRS.StrongCvx.xg Pg (z 0) - RelaxedPRS.StrongCvx.xg Pg zs‖ ^ 2 +
1 / (β ^ 2 + γ ^ 2) *
(γ ^ 3 / β - 2 * γ * β - β ^ 2) * ‖z 0 - zs‖ ^ 2) /
(2 * γ * ((k : ℝ) + 1))) ∧
(fun k : ℕ => (Finset.range (k + 1)).inf' (Finset.nonempty_range_add_one)
(errF f g Pf Pg z zs)) =o[atTop] (fun k : ℕ => 1 / ((k : ℝ) + 1)) ∧
(γ < κ * β →
(∀ k : ℕ, errF f g Pf Pg z zs k ≤
‖RelaxedPRS.StrongCvx.xg Pg (z 0) - RelaxedPRS.StrongCvx.xg Pg zs‖ ^ 2 / (2 * γ * ((k : ℝ) + 1))) ∧
(errF f g Pf Pg z zs) =o[atTop]
(fun k : ℕ => 1 / ((k : ℝ) + 1))) := by sorry
end RelaxedPRS.DRSSmooth
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.