Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — adaptive restart lengths and linear convergence

Proved
RestartPD.Adaptive.theorem_2

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

adaptive-restartslinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dualsharpness

Let LLL define a differentiable convex–concave primal–dual problem on closed convex X×YX\times YX×Y with a nonempty saddle set Z⋆Z^\starZ⋆, and use a seminorm ∥⋅∥p\|\cdot\|_p∥⋅∥p​. Suppose the base algorithm satisfies Property 3 with constants q,C>0q,C>0q,C>0. Starting from a feasible z0,0z^{0,0}z0,0, run Algorithm 1 with the adaptive condition (30), a user-chosen positive first interval τ0\tau^0τ0, and β∈(0,1)\beta\in(0,1)β∈(0,1). Suppose α>0\alpha>0α>0 and there is a set S⊆X×YS\subseteq X\times YS⊆X×Y containing every outer start zk,0z^{k,0}zk,0 on which the problem is α\alphaα-sharp. Put

t⋆=⌈2C(q+2)αβ⌉.t^\star=\left\lceil\frac{2C(q+2)}{\alpha\beta}\right\rceil.t⋆=⌈αβ2C(q+2)​⌉.

Then, for every outer index k≥1k\ge1k≥1, both conclusions hold:

τk≤t⋆,dist⁡p(zk,0,Z⋆)≤βkt⋆τ0dist⁡p(z0,0,Z⋆).\tau^k\le t^\star,\qquad \operatorname{dist}_p(z^{k,0},Z^\star) \le \beta^k\frac{t^\star}{\tau^0} \operatorname{dist}_p(z^{0,0},Z^\star).τk≤t⋆,distp​(zk,0,Z⋆)≤βkτ0t⋆​distp​(z0,0,Z⋆).

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 k≥1k\ge1k≥1. The bound excludes k=0k=0k=0, since τ0\tau^0τ0 is freely selected. The paper's feasible-region and finite-value assumptions are represented by the stronger explicit condition Z⋆≠∅Z^\star\ne\varnothingZ⋆=∅, ensuring distance is well defined as a real infimum. The normalized gap and diameter are extended-real valued, retaining unbounded cases. The τ0\tau^0τ0 quotient is a real quotient.

Preamble
import Mathlib
import Definitions.Def_RestartPD_Adaptive_Restarts
Formal statement
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
Source
Applegate, Hinder, Lu & Lubin, Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness, arXiv:2105.12715v4, p. 18, Theorem 2(i)–(ii), (33)
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me