Lemma 1, p. 12 — the expected dual increase of an SDCA step is at least times the duality gap minus
ProvedSDCA.Lipschitz.lemma_1Throughout, (), are convex, , is the primal objective (1), the dual objective (2), the convex conjugate and .
Let and assume every is -strongly convex (the p. 2 display; is allowed). Let be an SDCA step rule, let be a sub-gradient selection, for all , and let . Let be any dual-feasible state ( for all ), , , and let with uniform on . Then all the dual values involved are finite and
This is the key lemma of the paper: the expected dual increase of one SDCA iteration is controlled from below by the current duality gap, which gives a recursion for the dual sub-optimality.
Formalization Note The paper states the lemma with expectations over the whole history; this is the conditional (one-step) form for a fixed state , from which the printed form follows by averaging over the history. is the average . The paper allows ; divides by , so is assumed. The dual values are converted to reals only after their finiteness is asserted in the conclusion.
import Mathlib import Definitions.Def_SDCA_Lipschitz_Model
namespace SDCA.Lipschitz
/-- Lemma 1, p. 12, in conditional (one-step) form. Assume every `φᵢ*` is `γ`-strongly convex
(`γ ≥ 0`; `γ = 0` is allowed), let `0 < s ≤ 1`, let `u` be a sub-gradient selection
(`−u i a ∈ ∂φᵢ(a)`), and let `α = α⁽ᵗ⁻¹⁾` be any dual-feasible state. Averaging over the uniformly
picked coordinate `i` (so that `α⁽ᵗ⁾ = α + Δαᵢeᵢ`),
`E[D(α⁽ᵗ⁾)] − D(α) ≥ (s/n)(P(w(α)) − D(α)) − (s/n)² G/(2λ)`, with
`G = (1/n) ∑ᵢ (‖xᵢ‖² − γ(1−s)λn/s)(uᵢ − αᵢ)²` and `uᵢ = u i (xᵢᵀw(α))`.
All dual values involved are finite. -/
theorem lemma_1 {d n : ℕ} (φ : Fin n → ℝ → ℝ) (x : Fin n → EuclideanSpace ℝ (Fin d)) (lam : ℝ)
(hn : 0 < n) (hlam : 0 < lam) (hconv : ∀ i, ConvexOn ℝ Set.univ (φ i))
(Δ : (Fin n → ℝ) → Fin n → ℝ) (hΔ : IsSDCAStep φ x lam Δ)
(γ : ℝ) (hγ : 0 ≤ γ)
(hsc : ∀ (i : Fin n) (u v r : ℝ), 0 ≤ r → r ≤ 1 →
conj (φ i) (r * u + (1 - r) * v) ≤
((r : ℝ) : EReal) * conj (φ i) u + ((1 - r : ℝ) : EReal) * conj (φ i) v
- ((γ * r * (1 - r) / 2 * (u - v) ^ 2 : ℝ) : EReal))
(s : ℝ) (hs0 : 0 < s) (hs1 : s ≤ 1)
(u : Fin n → ℝ → ℝ) (hu : ∀ i a, -(u i a) ∈ subdiff (φ i) a)
(α : Fin n → ℝ) (hα : ∀ j, conj (φ j) (-α j) ≠ ⊤) :
dual φ x lam α ≠ ⊥ ∧ (∀ i, dual φ x lam (sdcaStep Δ α i) ≠ ⊥) ∧
(1 / (n : ℝ)) * ∑ i, (dual φ x lam (sdcaStep Δ α i)).toReal - (dual φ x lam α).toReal ≥
s / n * (primal φ x lam (wOf x lam α) - (dual φ x lam α).toReal)
- (s / n) ^ 2 *
((1 / (n : ℝ)) * ∑ i, (‖x i‖ ^ 2 - γ * (1 - s) * lam * n / s)
* (u i (inner ℝ (wOf x lam α) (x i)) - α i) ^ 2) / (2 * lam) := by sorry
end SDCA.Lipschitz
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.