Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 20 for Algorithm 1 with μ1=0\mu_1 = 0μ1​=0 — rates for the proximal ADMM iterates when C1=0C_1 = 0C1​=0

Open
BotNguyenADMM.Rates.theorem_20_prox_mu1_zero

by tianyipeng · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

admmconvergence-rateslojasiewicznonconvex-optimization

This is Theorem 20 of Boţ–Nguyen restricted to Algorithm 1 (the proximal ADMM) with metric bound μ1=0\mu_1 = 0μ1​=0, i.e. ∥M1k∥=0\|M_1^k\| = 0∥M1k​∥=0 for all kkk.

Suppose Assumption 2 holds for Algorithm 1 with μ1=0\mu_1 = 0μ1​=0, and let (xk,zk,yk)k≥0(x^k,z^k,y^k)_{k\ge0}(xk,zk,yk)k≥0​ be a bounded sequence generated by Algorithm 1 that converges to (x^,z^,y^)(\hat x,\hat z,\hat y)(x^,z^,y^​). Suppose that the Section 3 regularized augmented Lagrangian

Fr(x,z,y,x′,y′)=Lr(x,z,y)+2T1∥A∗(y−y′)∥2+C1∥x−x′∥2\mathcal F_r(x,z,y,x',y') = L_r(x,z,y) + 2T_1\|A^*(y-y')\|^2 + C_1\|x-x'\|^2Fr​(x,z,y,x′,y′)=Lr​(x,z,y)+2T1​∥A∗(y−y′)∥2+C1​∥x−x′∥2

satisfies the Łojasiewicz property (70) at (x^,z^,y^,x^,y^)(\hat x,\hat z,\hat y,\hat x,\hat y)(x^,z^,y^​,x^,y^​) with constant CL>0C_L>0CL​>0 and exponent θ∈[0,1)\theta\in[0,1)θ∈[0,1). Then:

  1. if θ=0\theta = 0θ=0, then (xk,zk,yk)=(x^,z^,y^)(x^k,z^k,y^k) = (\hat x,\hat z,\hat y)(xk,zk,yk)=(x^,z^,y^​) for all large kkk;
  2. if θ∈(0,12]\theta\in(0,\frac12]θ∈(0,21​], there are k0≥1k_0\ge1k0​≥1, C^0,1,C^0,2,C^0,3>0\hat C_{0,1},\hat C_{0,2},\hat C_{0,3}>0C^0,1​,C^0,2​,C^0,3​>0 and Q^∈[0,1)\hat Q\in[0,1)Q^​∈[0,1) such that for every k≥k0k\ge k_0k≥k0​
∥xk−x^∥≤C^0,1Q^k,∥yk−y^∥≤C^0,2Q^k,∥zk−z^∥≤C^0,3Q^k;\|x^k-\hat x\|\le\hat C_{0,1}\hat Q^k,\qquad \|y^k-\hat y\|\le\hat C_{0,2}\hat Q^k,\qquad \|z^k-\hat z\|\le\hat C_{0,3}\hat Q^k;∥xk−x^∥≤C^0,1​Q^​k,∥yk−y^​∥≤C^0,2​Q^​k,∥zk−z^∥≤C^0,3​Q^​k;
  1. if θ∈(12,1)\theta\in(\frac12,1)θ∈(21​,1), there are k0≥3k_0\ge3k0​≥3 and C^1,1,C^1,2,C^1,3>0\hat C_{1,1},\hat C_{1,2},\hat C_{1,3}>0C^1,1​,C^1,2​,C^1,3​>0 such that for every k≥k0k\ge k_0k≥k0​
∥xk−x^∥≤C^1,1(k−1)−1−θ2θ−1,∥yk−y^∥≤C^1,2(k−1)−1−θ2θ−1,∥zk−z^∥≤C^1,3(k−2)−1−θ2θ−1.\|x^k-\hat x\|\le\hat C_{1,1}(k-1)^{-\frac{1-\theta}{2\theta-1}},\quad \|y^k-\hat y\|\le\hat C_{1,2}(k-1)^{-\frac{1-\theta}{2\theta-1}},\quad \|z^k-\hat z\|\le\hat C_{1,3}(k-2)^{-\frac{1-\theta}{2\theta-1}}.∥xk−x^∥≤C^1,1​(k−1)−2θ−11−θ​,∥yk−y^​∥≤C^1,2​(k−1)−2θ−11−θ​,∥zk−z^∥≤C^1,3​(k−2)−2θ−11−θ​.

The paper's Assumption 1/2 allows μ1≥0\mu_1 \ge 0μ1​≥0, so this case is covered by the paper's Theorem 20. It is exactly the case in which C1=4T0μ12/rC_1 = 4T_0\mu_1^2/rC1​=4T0​μ12​/r vanishes: then Fr\mathcal F_rFr​ carries no ∥x−x′∥2\|x-x'\|^2∥x−x′∥2 term, and the constants C17=12min⁡{C1/4,1/(ρr)}C_{17} = \frac12\min\{C_1/4, 1/(\rho r)\}C17​=21​min{C1​/4,1/(ρr)}, C19C_{19}C19​ and C20=7/C17+1/C17C_{20} = 7/\sqrt{C_{17}} + 1/C_{17}C20​=7/C17​​+1/C17​ used in Lemmas 17 and 19 degenerate. For Algorithm 2, and for Algorithm 1 with μ1>0\mu_1 > 0μ1​>0, one has C1>0C_1 > 0C1​>0, and Theorem 20 follows from Theorem 18 and Lemma 19.

Formalization Note Same formal setting and conventions as BotNguyenADMM.Rates.theorem_20 (the limit and the Łojasiewicz property are packaged in LojAt; any valid bounds lam, μ₂ may be used), with the extra hypotheses v = prox and μ₁ = 0.

Preamble
import Mathlib
import Definitions.Def_BotNguyenADMM_Rates_Setting
import Definitions.Def_BotNguyenADMM_Rates_Lojasiewicz

open Filter Topology
open scoped InnerProductSpace RealInnerProductSpace
open NonconvexSplitting.Shared
Formal statement
namespace BotNguyenADMM.Rates

/-- **Theorem 20, case of Algorithm 1 with `μ₁ = 0`** (Boţ–Nguyen, arXiv:1801.01994v2, p. 28).
The statement of Theorem 20 for Algorithm 1 (`v = prox`) with the metric bound `μ₁ = 0`, i.e. the
case where the constant `C₁ = 4T₀μ₁²/r` vanishes and the constants `C₁₇`, `C₁₉`, `C₂₀` used in
the paper's proof (Lemmas 17 and 19) degenerate. -/
theorem theorem_20_prox_mu1_zero
    {n m : ℕ} (v : BotNguyenADMM.KL.Variant) (g : BotNguyenADMM.KL.E m → EReal) (h : BotNguyenADMM.KL.E n → ℝ) (A : BotNguyenADMM.KL.E n →L[ℝ] BotNguyenADMM.KL.E m)
    (L r ρ lam μ₁ μ₂ : ℝ) (M₁ : ℕ → BotNguyenADMM.KL.E n →L[ℝ] BotNguyenADMM.KL.E n) (M₂ : ℕ → BotNguyenADMM.KL.E m →L[ℝ] BotNguyenADMM.KL.E m)
    (hv : v = BotNguyenADMM.KL.Variant.prox) (hμ₁ : μ₁ = 0)
    (hA2 : Assumption2 v g h A L r ρ lam μ₁ μ₂ M₁ M₂)
    (x : ℕ → BotNguyenADMM.KL.E n) (z y : ℕ → BotNguyenADMM.KL.E m) (hrun : IsRun v g h A r ρ M₁ M₂ x z y)
    (hbx : Bornology.IsBounded (Set.range x)) (hbz : Bornology.IsBounded (Set.range z))
    (hby : Bornology.IsBounded (Set.range y))
    (xh : BotNguyenADMM.KL.E n) (zh yh : BotNguyenADMM.KL.E m) (CL θ : ℝ)
    (hloj : LojAt v g h A L r ρ lam μ₁ x z y xh zh yh CL θ) :
    (θ = 0 → ∃ K : ℕ, ∀ k ≥ K, x k = xh ∧ z k = zh ∧ y k = yh) ∧
    (0 < θ ∧ θ ≤ 1 / 2 → ∃ k₀ : ℕ, 1 ≤ k₀ ∧
      ∃ C01 C02 C03 Qhat : ℝ, 0 < C01 ∧ 0 < C02 ∧ 0 < C03 ∧ 0 ≤ Qhat ∧ Qhat < 1 ∧
      ∀ k ≥ k₀, ‖x k - xh‖ ≤ C01 * Qhat ^ k ∧ ‖y k - yh‖ ≤ C02 * Qhat ^ k ∧
        ‖z k - zh‖ ≤ C03 * Qhat ^ k) ∧
    (1 / 2 < θ ∧ θ < 1 → ∃ k₀ : ℕ, 3 ≤ k₀ ∧
      ∃ C11 C12 C13 : ℝ, 0 < C11 ∧ 0 < C12 ∧ 0 < C13 ∧
      ∀ k ≥ k₀, ‖x k - xh‖ ≤ C11 * ((k : ℝ) - 1) ^ (-((1 - θ) / (2 * θ - 1))) ∧
        ‖y k - yh‖ ≤ C12 * ((k : ℝ) - 1) ^ (-((1 - θ) / (2 * θ - 1))) ∧
        ‖z k - zh‖ ≤ C13 * ((k : ℝ) - 2) ^ (-((1 - θ) / (2 * θ - 1)))) := by sorry

end BotNguyenADMM.Rates
Source
Boţ and Nguyen, The proximal ADMM in the nonconvex setting, arXiv:1801.01994v2, p. 28, Theorem 20 (case Algorithm 1, μ₁ = 0; Assumption 1.4 on p. 8 allows μ₁ ≥ 0)

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