Theorem 2 — SDCA with -smooth losses reaches expected duality gap after iterations
ProvedSDCA.Smooth.theorem_2Let with , let and , and let be convex and -smooth (differentiable with -Lipschitz derivative). Assume the standing assumptions
- for all ,
- for all and ,
- for all .
Run Procedure SDCA from : at each iteration a coordinate is drawn uniformly at random, independently of the past, and is changed by an increment maximizing the coordinate dual objective; . Let . Then all dual values along the run and at the averaged output are finite, and:
- (Last iterate.) If
then . 2. (Averaging option.) If and
then the output , , satisfies . 3. (Random option.) Under the same condition, if for drawn uniformly from independently of the run, then .
This is the paper's main result: for smooth losses SDCA converges linearly in the duality gap, with iterations, and the duality gap certifies primal sub-optimality.
Formalization Note Expectations are uniform averages over the coordinate sequences (SAGA.Convex.expectIdx). The step is any map satisfying the argmax predicate IsSDCAStep. is EReal-valued; its values are converted to reals only under the first conjunct, which asserts their finiteness. The Random option is stated over the iterates , which is what the proof bounds (the procedure's line " for random " is off by one against it). is the natural logarithm; no sign condition on it is assumed. No dual optimum is assumed.
import Mathlib import Definitions.Def_SDCA_Smooth_Model
namespace SDCA.Smooth
/-- Theorem 2, p. 6 (Shalev-Shwartz–Zhang, arXiv:1209.1873v2). Run Procedure SDCA from `α⁽⁰⁾ = 0`
with convex `(1/γ)`-smooth losses `φᵢ` and the standing assumptions `‖xᵢ‖ ≤ 1`, `φᵢ ≥ 0`,
`φᵢ(0) ≤ 1` (p. 5), coordinates drawn i.i.d. uniformly. Let `εP > 0`. Then every dual value along
the run and at the outputs is finite, and:
1. if `T ≥ (n + 1/(λγ)) log((n + 1/(λγ)) · 1/εP)`, then `E[P(w⁽ᵀ⁾) − D(α⁽ᵀ⁾)] ≤ εP`;
2. if `T > T₀` and `T₀ ≥ (n + 1/(λγ)) log((n + 1/(λγ)) · 1/((T − T₀) εP))`, then the Averaging
option output `ᾱ = (1/(T − T₀)) ∑_{t=T₀+1}^{T} α⁽ᵗ⁻¹⁾`, `w̄ = w(ᾱ)`, has `E[P(w̄) − D(ᾱ)] ≤ εP`;
3. under the same condition, the Random option output (the iterate `α⁽ᵗ⁻¹⁾` for `t` uniform on
`{T₀+1, …, T}`, independent of the run) has `E[P(w̄) − D(ᾱ)] ≤ εP`. -/
theorem theorem_2 {d n : ℕ} (hn : 0 < n) (x : Fin n → EuclideanSpace ℝ (Fin d))
(φ φ' : Fin n → ℝ → ℝ) (hconv : ∀ i, ConvexOn ℝ Set.univ (φ i))
(lam γ : ℝ) (hlam : 0 < lam) (hγ : 0 < γ)
(hderiv : ∀ i a, HasDerivAt (φ i) (φ' i a) a)
(hsmooth : ∀ i a b, |φ' i a - φ' i b| ≤ (1 / γ) * |a - b|)
(hx : ∀ i, ‖x i‖ ≤ 1) (hφnn : ∀ i a, 0 ≤ φ i a) (hφ0 : ∀ i, φ i 0 ≤ 1)
(Δ : (Fin n → ℝ) → Fin n → ℝ) (hΔ : IsSDCAStep lam x φ Δ)
(εP : ℝ) (hεP : 0 < εP) :
((∀ (T : ℕ) (js : Fin T → Fin n) (t : ℕ), dual lam x φ (alphaIter Δ js t) ≠ ⊥) ∧
∀ (T : ℕ) (js : Fin T → Fin n) (T₀ : ℕ), T₀ < T → dual lam x φ (alphaAvg Δ js T₀) ≠ ⊥) ∧
(∀ T : ℕ,
(n + 1 / (lam * γ)) * Real.log ((n + 1 / (lam * γ)) * (1 / εP)) ≤ T →
SAGA.Convex.expectIdx n T (fun js =>
primal lam x φ (wOf lam x (alphaIter Δ js T)) -
(dual lam x φ (alphaIter Δ js T)).toReal) ≤ εP) ∧
(∀ T₀ T : ℕ, T₀ < T →
(n + 1 / (lam * γ)) * Real.log ((n + 1 / (lam * γ)) * (1 / (((T : ℝ) - T₀) * εP))) ≤ T₀ →
SAGA.Convex.expectIdx n T (fun js =>
primal lam x φ (wOf lam x (alphaAvg Δ js T₀)) -
(dual lam x φ (alphaAvg Δ js T₀)).toReal) ≤ εP) ∧
(∀ T₀ T : ℕ, T₀ < T →
(n + 1 / (lam * γ)) * Real.log ((n + 1 / (lam * γ)) * (1 / (((T : ℝ) - T₀) * εP))) ≤ T₀ →
(1 / ((T : ℝ) - T₀)) * ∑ t ∈ Finset.Ico T₀ T,
SAGA.Convex.expectIdx n T (fun js =>
primal lam x φ (wOf lam x (alphaIter Δ js t)) -
(dual lam x φ (alphaIter Δ js t)).toReal) ≤ εP) := by sorry
end SDCA.Smooth
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.