Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§8.3, p. 68 — feature splitting: the z-update reduces to the z̄-update and all duals equal Ax̄^{k+1} + ū^k − z̄^{k+1}

Proved
BoydADMM.ModelFit.feature_split_duals_agree

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

admmfeature-splittingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1sharing

Consider the model-fitting problem split across features: the feature matrix is partitioned by columns as A=[A1⋯AN]A=[A_1\cdots A_N]A=[A1​⋯AN​] with Ai∈Rm×niA_i\in\mathbb R^{m\times n_i}Ai​∈Rm×ni​, N≥1N\ge1N≥1, the loss l:Rm→Rl:\mathbb R^m\to\mathbb Rl:Rm→R is convex, b∈Rmb\in\mathbb R^mb∈Rm and ρ>0\rho>0ρ>0. Fix the new local variables xi=xik+1∈Rnix_i=x_i^{k+1}\in\mathbb R^{n_i}xi​=xik+1​∈Rni​ and the scaled duals ui=uik∈Rmu_i=u_i^k\in\mathbb R^mui​=uik​∈Rm, and write

Ax‾=1N∑i=1NAixi,uˉ=1N∑i=1Nui.\overline{Ax}=\frac1N\sum_{i=1}^N A_ix_i,\qquad \bar u=\frac1N\sum_{i=1}^N u_i .Ax=N1​i=1∑N​Ai​xi​,uˉ=N1​i=1∑N​ui​.

The zzz-update of the scaled ADMM minimizes over (z1,…,zN)∈(Rm)N(z_1,\dots,z_N)\in(\mathbb R^m)^N(z1​,…,zN​)∈(Rm)N

Φ(z1,…,zN)=l(∑i=1Nzi−b)+∑i=1Nρ2∥Aixi−zi+ui∥22.\Phi(z_1,\dots,z_N)=l\Bigl(\sum_{i=1}^N z_i-b\Bigr)+\sum_{i=1}^N\frac{\rho}{2}\|A_ix_i-z_i+u_i\|_2^2 .Φ(z1​,…,zN​)=l(i=1∑N​zi​−b)+i=1∑N​2ρ​∥Ai​xi​−zi​+ui​∥22​.

For any (z1,…,zN)(z_1,\dots,z_N)(z1​,…,zN​), with average zˉ=1N∑izi\bar z=\frac1N\sum_i z_izˉ=N1​∑i​zi​:

  1. (z1,…,zN)(z_1,\dots,z_N)(z1​,…,zN​) minimizes Φ\PhiΦ if and only if zˉ\bar zzˉ minimizes
zˉ↦l(Nzˉ−b)+Nρ2∥zˉ−Ax‾−uˉ∥22\bar z\mapsto l(N\bar z-b)+\frac{N\rho}{2}\|\bar z-\overline{Ax}-\bar u\|_2^2zˉ↦l(Nzˉ−b)+2Nρ​∥zˉ−Ax−uˉ∥22​

and, for every iii, zi=zˉ+Aixi+ui−Ax‾−uˉz_i=\bar z+A_ix_i+u_i-\overline{Ax}-\bar uzi​=zˉ+Ai​xi​+ui​−Ax−uˉ; 2. if (z1,…,zN)(z_1,\dots,z_N)(z1​,…,zN​) minimizes Φ\PhiΦ, then the dual updates ui+=ui+Aixi−ziu_i^{+}=u_i+A_ix_i-z_iui+​=ui​+Ai​xi​−zi​ all coincide:

ui+=Ax‾+uˉ−zˉfor every i.u_i^{+}=\overline{Ax}+\bar u-\bar z\qquad\text{for every } i .ui+​=Ax+uˉ−zˉfor every i.

This is the reduction that turns the NNN-block zzz-update into a single problem in mmm variables and lets the algorithm keep a single dual variable, as in the sharing problem.

Formalization Note The loss is real valued and convex, as in (8.1) on p. 61 ("l:Rm→Rl:\mathbf R^m\to\mathbf Rl:Rm→R is a convex loss function"). The book introduces zˉk+1\bar z^{k+1}zˉk+1 as a minimizer and then defines zik+1z_i^{k+1}zik+1​ from it; the statement formalizes this as the equivalence in item 1, with zˉ\bar zzˉ the average of the ziz_izi​, so it says both that the two-step recipe produces a minimizer and that every minimizer arises this way. The book overlines the whole product, Ax‾k+1\overline{Ax}^{k+1}Axk+1; it is a single vector, the average of the partial predictors. Iteration superscripts are dropped. The blocks are indexed by Fin N, i.e. from 000.

Preamble
import Mathlib
import Definitions.Def_BoydADMM_ModelFit_Basic

open Matrix
Formal statement
namespace BoydADMM.ModelFit

/-- §8.3, p. 68: in the feature-split ADMM, the `z`-update over `(z₁, …, z_N)` reduces to the
`z̄`-update for the average `z̄` plus the explicit formula for each `zᵢ`, and then all the scaled
dual variables `uᵢ^{k+1} = uᵢ^k + Aᵢxᵢ^{k+1} − zᵢ^{k+1}` equal `Ax̄^{k+1} + ū^k − z̄^{k+1}`. -/
theorem feature_split_duals_agree {N m : ℕ} {n : Fin N → ℕ} (hN : 0 < N)
    (A : ∀ i, Matrix (Fin m) (Fin (n i)) ℝ) (l : EuclideanSpace ℝ (Fin m) → ℝ)
    (hl : ConvexOn ℝ Set.univ l) (b : EuclideanSpace ℝ (Fin m)) (ρ : ℝ) (hρ : 0 < ρ)
    (x : ∀ i, EuclideanSpace ℝ (Fin (n i))) (u z u' : Fin N → EuclideanSpace ℝ (Fin m))
    (hu' : ∀ i, u' i = u i + Matrix.toEuclideanLin (A i) (x i) - z i) :
    (IsMinOn (fun z' : Fin N → EuclideanSpace ℝ (Fin m) =>
        l ((∑ i, z' i) - b) + ∑ i, ρ / 2 * ‖Matrix.toEuclideanLin (A i) (x i) - z' i + u i‖ ^ 2)
        Set.univ z ↔
      (IsMinOn (fun zb : EuclideanSpace ℝ (Fin m) =>
          l ((N : ℝ) • zb - b) + (N : ℝ) * ρ / 2 *
            ‖zb - (N : ℝ)⁻¹ • (∑ i, Matrix.toEuclideanLin (A i) (x i))
              - (N : ℝ)⁻¹ • (∑ i, u i)‖ ^ 2)
          Set.univ ((N : ℝ)⁻¹ • (∑ i, z i)) ∧
        ∀ i, z i = (N : ℝ)⁻¹ • (∑ j, z j) + Matrix.toEuclideanLin (A i) (x i) + u i
          - (N : ℝ)⁻¹ • (∑ j, Matrix.toEuclideanLin (A j) (x j))
          - (N : ℝ)⁻¹ • (∑ j, u j))) ∧
    (IsMinOn (fun z' : Fin N → EuclideanSpace ℝ (Fin m) =>
        l ((∑ i, z' i) - b) + ∑ i, ρ / 2 * ‖Matrix.toEuclideanLin (A i) (x i) - z' i + u i‖ ^ 2)
        Set.univ z →
      ∀ i, u' i = (N : ℝ)⁻¹ • (∑ j, Matrix.toEuclideanLin (A j) (x j))
        + (N : ℝ)⁻¹ • (∑ j, u j) - (N : ℝ)⁻¹ • (∑ j, z j)) := by sorry

end BoydADMM.ModelFit
Source
Boyd, Parikh, Chu, Peleato, Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Found. Trends Mach. Learn. 3(1) (2011), pp. 67–68, §8.3
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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