Theorem 1 — AG on smooth Ψ: min‖∇Ψ(x^md_k)‖² ≤ (Ψ(x_0) − Ψ*)/Σλ_kC_k; for convex Ψ, Ψ(x^ag_N) − Ψ(x*) ≤ Γ_N‖x_0 − x*‖²/(2λ_1)
ProvedNonconvexAG.Smooth.theorem_1Let be differentiable, bounded from below, with for all , where , and let . Let be computed by Algorithm 1 from with step sizes , (), , , and let be defined in (2.6). Fix .
- If for , where
then
- Suppose moreover that is convex and that is a minimizer of on . If for
then
Part 1 shows that the accelerated gradient method, with a suitable step-size policy, drives the gradient to zero on a nonconvex smooth problem at the rate of gradient descent; part 2 shows that the same method keeps the optimal rate of Nesterov's method when happens to be convex (for instance with , ).
Formalization Note The gradient is an explicit map g with IsBetaSmooth Ψ g LΨ (differentiability, gradient , and (1.2)). as in (1.2). "Bounded from below" is the standing assumption of §2.1 (BddBelow (Set.range Ψ)), and is the infimum ⨅ x, Ψ x. The minimum over is Finset.inf' over Finset.Icc 1 N. depends on . Conditions (2.7), (2.9) and (2.10) are imposed for only, the indices the proof uses. The two parts are the two conjuncts of the conclusion.
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Smooth_AGRun
namespace NonconvexAG.Smooth
/-- Theorem 1 (p. 5): a) and b). -/
theorem theorem_1 {n : ℕ} (Ψ : E n → ℝ) (g : E n → E n) (LΨ : ℝ)
(hΨ : ConvexOptAlg.SmoothGD.IsBetaSmooth Ψ g LΨ) (hL : 0 < LΨ)
(α β lam : ℕ → ℝ) (hstep : AGStepsizes α β lam) (x0 : E n)
(hbdd : BddBelow (Set.range Ψ)) (N : ℕ) (hN : 1 ≤ N) :
-- a) under (2.7) for `k = 1, …, N`: (2.8)
((∀ k ∈ Finset.Icc 1 N, 0 < C LΨ α β lam N k) →
(Finset.Icc 1 N).inf' (Finset.nonempty_Icc.mpr hN) (fun k => ‖g (xmdSeq g α β lam x0 k)‖ ^ 2) ≤
(Ψ x0 - ⨅ x, Ψ x) / ∑ k ∈ Finset.Icc 1 N, lam k * C LΨ α β lam N k) ∧
-- b) `Ψ` convex with a minimizer `x*`, under (2.9) and (2.10) for `k = 1, …, N`: (2.11), (2.12)
(∀ xstar : E n, ConvexOn ℝ Set.univ Ψ → (∀ x, Ψ xstar ≤ Ψ x) →
(∀ k ∈ Finset.Icc 1 N, α k * lam k ≤ β k ∧ β k < 1 / LΨ) →
(∀ k ∈ Finset.Icc 1 N, 2 ≤ k →
α k / (lam k * Gamma α k) ≤ α (k - 1) / (lam (k - 1) * Gamma α (k - 1))) →
(Finset.Icc 1 N).inf' (Finset.nonempty_Icc.mpr hN) (fun k => ‖g (xmdSeq g α β lam x0 k)‖ ^ 2) ≤
‖x0 - xstar‖ ^ 2 /
(lam 1 * ∑ k ∈ Finset.Icc 1 N, (Gamma α k)⁻¹ * β k * (1 - LΨ * β k)) ∧
Ψ (xagSeq g α β lam x0 N) - Ψ xstar ≤ Gamma α N * ‖x0 - xstar‖ ^ 2 / (2 * lam 1)) := by sorry
end NonconvexAG.Smooth
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.