§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}
ProvedBoydADMM.ModelFit.feature_split_duals_agreeConsider the model-fitting problem split across features: the feature matrix is partitioned by columns as with , , the loss is convex, and . Fix the new local variables and the scaled duals , and write
The -update of the scaled ADMM minimizes over
For any , with average :
- minimizes if and only if minimizes
and, for every , ; 2. if minimizes , then the dual updates all coincide:
This is the reduction that turns the -block -update into a single problem in 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 (" is a convex loss function"). The book introduces as a minimizer and then defines from it; the statement formalizes this as the equivalence in item 1, with the average of the , 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, ; 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 .
import Mathlib import Definitions.Def_BoydADMM_ModelFit_Basic open Matrix
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.