Theorem 2 — adaptive restart lengths and linear convergence
ProvedRestartPD.Adaptive.theorem_2Let define a differentiable convex–concave primal–dual problem on closed convex with a nonempty saddle set , and use a seminorm . Suppose the base algorithm satisfies Property 3 with constants . Starting from a feasible , run Algorithm 1 with the adaptive condition (30), a user-chosen positive first interval , and . Suppose and there is a set containing every outer start on which the problem is -sharp. Put
Then, for every outer index , both conclusions hold:
The first bound limits the work in every adaptive interval after the first, and the second gives geometric decay of the distance to saddle points.
Formalization Note The run records the first positive trigger of (30) at each . The bound excludes , since is freely selected. The paper's feasible-region and finite-value assumptions are represented by the stronger explicit condition , ensuring distance is well defined as a real infimum. The normalized gap and diameter are extended-real valued, retaining unbounded cases. The quotient is a real quotient.
import Mathlib import Definitions.Def_RestartPD_Adaptive_Restarts
namespace RestartPD.Adaptive
/-- Theorem 2, p. 18: adaptive restart lengths and distance decay. -/
theorem theorem_2 {n m : ℕ}
(L : RestartPD.Fixed.Primal n → RestartPD.Fixed.Dual m → ℝ) (X : Set (RestartPD.Fixed.Primal n))
(Y : Set (RestartPD.Fixed.Dual m)) (hP : RestartPD.Fixed.IsPDProblem L X Y)
(p : Seminorm ℝ (RestartPD.Fixed.E n m)) (Runs : RestartPD.Fixed.E n m → Set (ℕ → RestartPD.Fixed.E n m))
(q C : ℝ) (h3 : RestartPD.Fixed.Property3 L X Y p Runs q C)
(α β : ℝ) (hα : 0 < α) (hβ : β ∈ Set.Ioo (0 : ℝ) 1)
(τ : ℕ → ℕ) (z : ℕ → RestartPD.Fixed.E n m) (zb : ℕ → ℕ → RestartPD.Fixed.E n m)
(hz0 : z 0 ∈ X ×ˢ Y)
(hrun : IsAdaptiveRestartRun L X Y p Runs β τ z zb)
(S : Set (RestartPD.Fixed.E n m)) (hzS : ∀ k, z k ∈ S)
(hsharp : RestartPD.Fixed.IsSharpOn L X Y p α S) :
let tstar := Nat.ceil (2 * C * (q + 2) / (α * β))
∀ k : ℕ, 1 ≤ k →
τ k ≤ tstar ∧
RestartPD.Fixed.distZ L X Y p (z k) ≤
β ^ k * ((tstar : ℝ) / (τ 0 : ℝ)) * RestartPD.Fixed.distZ L X Y p (z 0) := by sorry
end RestartPD.Adaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.