Corollary 1 — subgradient rate on weakly convex functions
ProvedBnBPEP.WeakCvx.corollary_1Let , , and let ( convex, all subgradients of norm at most ) have a global minimizer . Let and . Run the subgradient method
with arbitrary subgradients and the stepsize
and assume, as in the setup of Theorem 1, that . Let for and assume the initial condition . Then
where is the Moreau envelope of .
This is the explicit rate of the subgradient method on nonsmooth weakly convex functions obtained by Das Gupta, Van Parys and Ryu with the BnB-PEP methodology; it improves on the rate of Davis and Drusvyatskiy for all large enough . Since the minimum of the summands is at most their average, it also bounds .
Formalization Note "In the setup of Theorem 1" includes Theorem 1's requirement ; for this stepsize it reads and is stated as the explicit hypothesis (it fails, e.g., for ). is the paper's (normalized weak-convexity modulus ), and is written inline. The prox points are hypotheses IsProxPoint f (1/2) (x k) (y k), the subdifferential is the weak-convexity inequality with modulus , and is the gradient of the real-valued Moreau envelope moreauEnv 2 f.
import Mathlib import Definitions.Def_SAGA_Convex_IsProxPoint import Definitions.Def_BnBPEP_WeakCvx_IsWeakSubgrad import Definitions.Def_BnBPEP_WeakCvx_InWeakClass import Definitions.Def_BnBPEP_WeakCvx_moreauEnv
namespace BnBPEP.WeakCvx
/-- Corollary 1, p. 625: in the setup of Theorem 1 (which requires `h ∈ (0, 1/2]`), the stepsize
`h = √(4κ²(N+1) + 1) / (2(N+1))` with `κ = R/L` yields
`(1/(N+1)) Σ_{i=0}^N ‖∇f_{(1/2)}(x_i)‖² ≤ L² (2√(4κ²(N+1) + 1) - 1)/(N+1)`.
Here `L` is the paper's `L̃` (subgradient bound after normalizing `ρ = 1`). -/
theorem corollary_1 {d : ℕ} (f : EuclideanSpace ℝ (Fin d) → ℝ) (L : ℝ)
(hL : 0 < L) (hf : InWeakClass 1 L f)
(xstar : EuclideanSpace ℝ (Fin d)) (hxstar : ∀ z, f xstar ≤ f z)
(R : ℝ) (hR : 0 < R) (N : ℕ) (h : ℝ)
(hhdef : h = √(4 * (R / L) ^ 2 * ((N : ℝ) + 1) + 1) / (2 * ((N : ℝ) + 1)))
(hh : h ≤ 1 / 2)
(x g y : ℕ → EuclideanSpace ℝ (Fin d))
(hg : ∀ k ≤ N, IsWeakSubgrad 1 f (x k) (g k))
(hstep : ∀ k ≤ N, x (k + 1) = x k - h • g k)
(hy : ∀ k ≤ N + 1, SAGA.Convex.IsProxPoint f (1 / 2) (x k) (y k))
(hinit : f (y 0) - f xstar + ‖x 0 - y 0‖ ^ 2 ≤ R ^ 2) :
1 / ((N : ℝ) + 1) * ∑ i ∈ Finset.range (N + 1), ‖gradient (moreauEnv 2 f) (x i)‖ ^ 2
≤ L ^ 2 * (2 * √(4 * (R / L) ^ 2 * ((N : ℝ) + 1) + 1) - 1) / ((N : ℝ) + 1) := by sorry
end BnBPEP.WeakCvx
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.