Chapter 14 — Alternating Minimization
Proofs omitted. Hover over highlighted terms to see their Lean types.
Algorithm 14.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 14.1: a sequence of block vectors x^k follows the alternating minimization method for F when x^0 ∈ dom(F) and, for every outer iteration k and every zero-based block i : Fin p corresponding to textbook block i + 1, the updated block x_i^(k+1) minimizes the mixed subproblem xi ↦ F(x_1^(k+1), ..., x_(i-1)^(k+1), xi, x_(i+1)^k, ..., x_p^k).
universe v
variable {p : ℕ} {Ei : Fin p → Type v}
class is_alternating_minimization_trajectory
(F : ((i : Fin p) → Ei i) → EReal) (x : ℕ → (i : Fin p) → Ei i) : Prop where
zero_mem_effective_domain : x 0 ∈ effective_domain F
step_isMinOn (k : ℕ) (i : Fin p) :
IsMinOn
(alternating_minimization_block_objective F (x k) (x (k + 1)) i)
Set.univ
(x (k + 1) i)Definition 14.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 14.1: for an outer iterate sequence x^k in the block product PiLp 2 E, the auxiliary state x^{k,i} uses the new iterate x^(k+1) in blocks with index < i and the old iterate x^k in the remaining blocks.
universe u
open scoped Gradient
variable {p : ℕ} {E : Fin p → Type u}
local notation "BlockSpace" => PiLp (2 : ENNReal) E
def alternating_minimization_auxiliary_iterate
(x : ℕ → BlockSpace) (k : ℕ) (i : Fin (p + 1)) : BlockSpace :=
WithLp.toLp 2 (fun j ↦ if j.castSucc < i then x (k + 1) j else x k j)Lemma 14.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 14.1 uses Chapter 2's compact minimization owner exists_isMinOn_on_compact on a bounded real sublevel set of the fixed-block objective.
universe v
variable {p : ℕ} {Ei : Fin p → Type v}
variable [∀ i, PseudoMetricSpace (Ei i)]
recall exists_isMinOn_on_compact
-- Proof sketch: the fixed-base slice `yi ↦ F (Function.update xBar i yi)` is the composition of
-- `F` with the continuous block-update section `yi ↦ Function.update xBar i yi`.Proposition 14.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 14.1 (2): every point (-4 * α, 3 * α) on the distinguished line is a coordinate-wise minimum of the counterexample objective in the Chapter 14 two-block owner sense.
local notation "F" => alternating_minimization_failure_ii_objective.toEReal
local notation "g₀" => (0 : ℝ → EReal)
local notation "F₂" =>
two_block_alternating_minimization_objective_blocks
F
g₀
g₀
theorem alternating_minimization_counterexample_is_coordinatewise_minimum
(α : ℝ) :
is_coordinatewise_minimum F₂ (two_block_alternating_minimization_state (-4 * α) (3 * α))Algorithm 14.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 14.2: sequences of outer iterates x^k and auxiliary states x^{k,i} follow the alternating minimization method in alternative form from initialization x⁰ = x0 when, for every outer iteration k, one has x^{k,0} = x^k, each inner successor state x^{k,i} is obtained from x^{k,i-1} by updating block i with a minimizer of y ↦ F(x^{k,i-1} + 𝒰[i] (y - x_i^k)), and the next outer iterate is the terminal inner state x^(k+1) = x^{k,p}.
universe v
open scoped Gradient
variable {p : ℕ} {Ei : Fin p → Type v}
variable [∀ i, NormedAddCommGroup (Ei i)]
local notation "BlockSpace" => PiLp (2 : ENNReal) Ei
class is_alternating_minimization_alternative_trajectory
(F : BlockSpace → EReal) (x0 : BlockSpace) (x : ℕ → BlockSpace)
(xAux : ℕ → Fin (p + 1) → BlockSpace) : Prop where
zero_eq : x 0 = x0
start_eq : ∀ k : ℕ, xAux k 0 = x k
block_mem : ∀ k : ℕ, ∀ i : Fin p,
xAux k i.succ ∈
alternating_minimization_block_step F (x k) (xAux k i.castSucc) i
terminal_eq : ∀ k : ℕ, x (k + 1) = xAux k (Fin.last p)Definition 14.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 14.2: a point xStar is a coordinate-wise minimum of F on the finite block product if xStar ∈ dom(F) and, for every block i, the current coordinate xStar i globally minimizes the fixed-base Chapter 14 one-block objective obtained by varying only block i. The additive perturbation formula xStar + 𝒰[i] d is the equivalent bridge view in PiLp 2 Ei.
universe v
open scoped Gradient
variable {p : ℕ} {Ei : Fin p → Type v}
@[mk_iff is_coordinatewise_minimum_iff]
class is_coordinatewise_minimum
(F : ((i : Fin p) → Ei i) → EReal) (xStar : (i : Fin p) → Ei i) : Prop where
/-- A coordinate-wise minimum lies in the effective domain of the objective. -/
mem_effective_domain : xStar ∈ effective_domain F
/-- At a coordinate-wise minimum, each coordinate globally minimizes the fixed-base one-block
slice. -/
isMinOn (i : Fin p) :
IsMinOn (alternating_minimization_block_objective F xStar xStar i) Set.univ (xStar i)Lemma 14.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 14.2: under the standing composite-model assumptions from Assumption 14.6, every coordinate-wise minimum of the composite objective F(x) = f(x) + ∑ i, g_i(x_i) is a stationary point of the composite problem (14.9). The coordinate-wise minimum hypothesis uses the source-facing owner predicate from Definition 14.2 directly on the block product, while the regularity assumptions are supplied canonically by IsAlternatingMinimizationCompositeModel f g. The proof route factors through the companion blockwise subdifferential theorem coordinatewise_negative_gradient_mem_euclideanSubdifferential_of_coordinatewise_minimum.
universe u v
open scoped BigOperators Gradient
variable {p : ℕ} {Ei : Fin p → Type v}
variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)]
variable [hrawTupleFiniteDimensional : FiniteDimensional ℝ ((i : Fin p) → Ei i)]
variable {f : ((i : Fin p) → Ei i) → EReal} {g : (i : Fin p) → Ei i → EReal}
local notation "F" => composite_model_objective f (separableSum g)
local notation "toPiLp" =>
ContinuousLinearEquiv.symm (PiLp.continuousLinearEquiv (2 : ENNReal) ℝ Ei)
theorem is_stationary_point_of_coordinatewise_minimum
(hmodel : IsAlternatingMinimizationCompositeModel f g)
{xStar : (i : Fin p) → Ei i}
(hcoord : is_coordinatewise_minimum F xStar) :
is_stationary_point f (separableSum g) xStarProposition 14.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 14.2: if the frozen inactive penalty sum is finite, then the full block subproblem and the displayed one-block objective have the same minimizers.
universe v
open scoped BigOperators
variable {p : ℕ} {Ei : Fin p → Type v}
variable (f : ((i : Fin p) → Ei i) → EReal)
variable (g : (i : Fin p) → Ei i → EReal)
variable (xk xNext : (i : Fin p) → Ei i) (i : Fin p)
theorem isMinOn_alternating_minimization_full_objective_iff_isMinOn_composite_block_objective
(hinactive :
(∑ j ∈ Finset.univ.erase i, g j (if j.1 < i.1 then xNext j else xk j)) =
(((∑ j ∈ Finset.univ.erase i, g j (if j.1 < i.1 then xNext j else xk j)).toReal : ℝ) :
EReal))
(xi : Ei i) :
IsMinOn
(alternating_minimization_block_objective
(composite_model_objective f (separableSum g))
xk
xNext
i)
Set.univ
xi ↔
IsMinOn
(alternating_minimization_composite_block_objective f g xk xNext i)
Set.univ
xiAlgorithm 14.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 14.3: under Assumption 14.6, one alternating-minimization step from xk to xNext for the composite model f + ∑ i, g_i means that, for each block i : Fin p corresponding to textbook block i + 1, the updated block xNext i globally minimizes xi ↦ f(x_1^{k+1}, ..., x_{i-1}^{k+1}, xi, x_{i+1}^k, ..., x_p^k) + g_i(xi).
universe u
open scoped BigOperators
variable {p : ℕ} {Ei : Fin p → Type u}
variable [∀ i, NormedAddCommGroup (Ei i)]
variable [∀ i, NormedSpace ℝ (Ei i)]
class IsAlternatingMinimizationCompositeStep
(f : ((i : Fin p) → Ei i) → EReal)
(g : (i : Fin p) → Ei i → EReal)
(xk xNext : (i : Fin p) → Ei i) : Prop
extends IsAlternatingMinimizationCompositeModel f g where
block_isMinOn (i : Fin p) :
IsMinOn
(alternating_minimization_composite_block_objective f g xk xNext i)
Set.univ
(xNext i)Definition 14.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 14.3: Powell's example objective for the failure of alternating minimization, defined by `φ(x, y, z) = -xy - yz - zx + [x - 1]_+^2 + [-x - 1]_+^2 + [y - 1]_+^2 + [-y - 1]_+^2 + [z - 1]_+^2 + [-z - 1]_+^2`.
def powell_example_objective (x y z : ℝ) : ℝ :=
-(x * y) - y * z - z * x +
(x - 1)⁺ ^ 2 + (-x - 1)⁺ ^ 2 +
(y - 1)⁺ ^ 2 + (-y - 1)⁺ ^ 2 +
(z - 1)⁺ ^ 2 + (-z - 1)⁺ ^ 2Lemma 14.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 14.3: under Assumption 14.12 in its canonical Chapter 11/14 owner form, each half-step of the two-block alternating minimization method satisfies the corresponding sufficient-decrease estimate for the active block.
universe v
open scoped Gradient
variable {Ei : Fin 2 → Type v}
variable {f : ((i : Fin 2) → Ei i) → EReal} {g : (i : Fin 2) → Ei i → EReal}
variable {block_gradient : (i : Fin 2) → ((j : Fin 2) → Ei j) → Ei i}
variable {XStar : Set ((i : Fin 2) → Ei i)} {FOpt : ℝ}
variable {Li : (i : Fin 2) → PosReal}
local notation "F" => composite_model_objective f (separableSum g)
variable {xk : effective_domain (separableSum g)} {xNext : (i : Fin 2) → Ei i}
local notation "xHalf" => alternating_minimization_partial_state xk xNext 0 (xNext 0)
variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)]
-- Proof sketch: since `xNext 0` is an exact minimizer of the first frozen-block subproblem,
-- `F xHalf` is at most the value at any competitor, in particular the first-block prox-gradient
-- candidate from Lemma 11.3. Applying
-- `block_partial_gradient_sufficient_decrease_of_block_lipschitz` to the current iterate `xk`
-- and block `0` then yields the displayed lower bound.
theorem alternating_minimization_two_block_sufficient_decrease
[ProperSpace (Ei 0)] [ProperSpace (Ei 1)]
(hstep : IsAlternatingMinimizationCompositeStep f g xk xNext)
(hcore : IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li) :
F xk - F xHalf ≥
((((1 : ℝ) / (2 * (Li 0 : ℝ))) *
‖G[Li 0; hcore] xk 0‖ ^ (2 : ℕ) : ℝ) : EReal) ∧
F xHalf - F xNext ≥
((((1 : ℝ) / (2 * (Li 1 : ℝ))) *
‖G[Li 1; hcore] xHalf 1‖ ^ (2 : ℕ) : ℝ) : EReal)Proposition 14.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 14.3: if each a k belongs to the subdifferential of a lower semicontinuous extended-real-valued function h at b k, and a k → aBar, b k → bBar, then aBar belongs to the subdifferential of h at bBar. The statement uses the strong-dual bridge notation ∂ₛ h(x), so the theorem surface stays source-readable without exposing the long raw bridge name strongDualSubdifferential. The textbook properness and convexity hypotheses are redundant for this closed-graph property, so lower semicontinuity is the only public assumption.
universe u
open Filter
open scoped Topology
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem mem_strongDualSubdifferential_of_tendsto_subgradient_sequences
(h : E → EReal) (hclosed : LowerSemicontinuous h) (a : ℕ → StrongDual ℝ E) (b : ℕ → E)
{aBar : StrongDual ℝ E} {bBar : E}
(hsub : ∀ k : ℕ, a k ∈ ∂ₛ h(b k))
(ha : Tendsto a atTop (𝓝 aBar))
(hb : Tendsto b atTop (𝓝 bBar)) :
aBar ∈ ∂ₛ h(bBar)Theorem 14.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 14.3 [Convergence of alternating minimization to coordinate-wise minima]: let F : E₁ × ... × E_p → (-∞, ∞] be closed and continuous on its effective domain, assume that each one-block subproblem has a unique minimizer and that every real sublevel set of F is bounded, and let x be an alternating-minimization trajectory for F. Then the trajectory is bounded, and every sequential limit point of x is a coordinate-wise minimum of F. The source's properness clause for F is redundant for this conclusion and is not part of the exported Lean API; the generalized Lean theorem still keeps the ambient ProperSpace ((i : Fin p) → Ei i) hypothesis explicit because the cluster-point argument uses compactness of closed bounded sublevels. On the Lean surface, hunique asks only for subsingleton block argmin sets, since the existing closedness and bounded-sublevel hypotheses already supply the needed nonemptiness. The explicit recovery hypothesis records the domain-stability step used by the canonical helper chain and prevents applying the result to extended-valued domains where strict block competitors cannot be approximated from nearby base points.
universe u
open Filter
open scoped Topology
variable {p : ℕ} {Ei : Fin p → Type u}
variable [∀ i, PseudoMetricSpace (Ei i)]
theorem alternating_minimization_convergence_to_coordinatewise_minima
[ProperSpace ((i : Fin p) → Ei i)]
(F : ((i : Fin p) → Ei i) → EReal)
(x : ℕ → (i : Fin p) → Ei i)
(hclosed : LowerSemicontinuous F)
(hcont : ContinuousOn F (effective_domain F))
(hunique :
∀ xBar ∈ effective_domain F, ∀ i : Fin p,
Set.Subsingleton (alternating_minimization_argmin F xBar i))
(hlevel : ∀ α : ℝ, Bornology.IsBounded {x | F x ≤ (α : EReal)})
(hrecover : AlternatingMinimizationStrictCompetitorRecovery F)
(htraj : is_alternating_minimization_trajectory F x) :
Bornology.IsBounded (Set.range x) ∧
∀ xBar : (i : Fin p) → Ei i, MapClusterPt xBar atTop x →
is_coordinatewise_minimum F xBarTheorem 14.3.Helpers
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
alternatingMinimizationRecoverLimitArgminAlongPrefixState: along a refined subsequence of stage-i prefix states converging to xBar, recover a limit block coordinate in alternating_minimization_argmin F xBar i that is also the limit of the actual next-iterate active coordinates, while the corresponding recovered updates remain in effective_domain F.
theorem alternatingMinimizationRecoverLimitArgminAlongPrefixState :
∀ {p : ℕ} {Ei : Fin p → Type u}
[(i : Fin p) → PseudoMetricSpace (Ei i)]
[ProperSpace ((i : Fin p) → Ei i)]
(F : ((i : Fin p) → Ei i) → EReal) (x : ℕ → (i : Fin p) → Ei i),
LowerSemicontinuous F →
ContinuousOn F (effective_domain F) →
(∀ (α : ℝ), Bornology.IsBounded {x | F x ≤ ↑α}) →
is_alternating_minimization_trajectory F x →
∀ {xBar : (j : Fin p) → Ei j} (i : Fin p) {ψ : ℕ → ℕ},
Filter.Tendsto
(fun m ↦ alternating_minimization_prefix_state x (ψ m) ↑i)
Filter.atTop
(nhds xBar) →
(∀ ⦃zi : Ei i⦄,
Function.update xBar i zi ∈ effective_domain F →
F (Function.update xBar i zi) < ↑(F (x 0)).toReal →
∀ s ∈ nhds zi,
{xBase |
∃ zi' ∈ s,
Function.update xBase i zi' ∈ effective_domain F ∧
F (Function.update xBase i zi') <
↑(F (x 0)).toReal} ∈
nhds xBar) →
∃ φ,
∃ (_ : StrictMono φ),
∃ ziLimit ∈ alternating_minimization_argmin F xBar i,
Filter.Tendsto (fun m ↦ x (ψ (φ m) + 1) i) Filter.atTop
(nhds ziLimit) ∧
∀ m : ℕ,
Function.update
(alternating_minimization_prefix_state x (ψ (φ m)) ↑i)
i
(x (ψ (φ m) + 1) i) ∈
effective_domain FDefinition 14.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 14.4: Example 14.5 (failure of alternating minimization II) defines the convex objective F : ℝ × ℝ → ℝ by F(x₁, x₂) = |3x₁ + 4x₂| + |x₁ - 2x₂|.
def alternating_minimization_failure_ii_objective : ℝ × ℝ → ℝ :=
fun (x₁, x₂) ↦ |3 * x₁ + 4 * x₂| + |x₁ - 2 * x₂|
-- Proof sketch: unfold `alternating_minimization_failure_ii_objective`; evaluating it on the pair
-- `(x₁, x₂)` gives exactly the displayed formula from the source.Lemma 14.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 14.4: for a two-block alternating-minimization trajectory, the half-step and next-step objective gaps are controlled by the corresponding block gradient mappings on the frozen slices y₁ ↦ f (y₁, x₂ᵏ) and y₂ ↦ f (x₁ᵏ⁺¹, y₂), provided f is jointly convex and the initial pair lies in effective_domain F.
universe u
open scoped Gradient
variable {E1 : Type u} {E2 : Type u}
variable [NormedAddCommGroup E1] [NormedAddCommGroup E2]
variable [InnerProductSpace ℝ E1] [ProperSpace E1]
variable [InnerProductSpace ℝ E2] [ProperSpace E2]
variable (f : E1 × E2 → ℝ) (g1 : E1 → EReal) (g2 : E2 → EReal)
variable (x1 : ℕ → E1) (x2 : ℕ → E2) (k : ℕ)
local notation "F" => two_block_alternating_minimization_objective f.toEReal g1 g2
local notation "xk" => (x1 k, x2 k)
local notation "xHalf" => two_block_alternating_minimization_half_step x1 x2 k
local notation "xNext" => (x1 (k + 1), x2 (k + 1))
local notation "f1" => fun y1 ↦ f (y1, x2 k)
local notation "f2" => fun y2 ↦ f (x1 (k + 1), y2)
theorem two_block_alternating_minimization_objective_gap_le_gradient_mapping
(L1 L2 : PosReal)
[IsProperExtendedRealFunction g1]
[Fact (LowerSemicontinuous g1)]
[Fact (is_convex_function g1)]
[IsProperExtendedRealFunction g2]
[Fact (LowerSemicontinuous g2)]
[Fact (is_convex_function g2)]
(htraj : is_two_block_alternating_minimization_trajectory f.toEReal g1 g2 x1 x2)
(hx0 : (x1 0, x2 0) ∈ effective_domain F)
(hf_convex : ConvexOn ℝ Set.univ f)
(hf_x1_smooth : is_l_smooth_on f1 Set.univ (PosReal.toNNReal L1))
(hf_x2_smooth : is_l_smooth_on f2 Set.univ (PosReal.toNNReal L2))
(xStar : E1 × E2)
(hxStar : IsMinOn F Set.univ xStar) :
F xHalf - F xStar ≤ (((‖G[L1; f1, g1] (x1 k)‖ * ‖xk - xStar‖ : ℝ) : EReal)) ∧
F xNext - F xStar ≤ (((‖G[L2; f2, g2] (x2 k)‖ * ‖xHalf - xStar‖ : ℝ) : EReal))Theorem 14.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 14.4 (2): under Assumption 14.6, if each one-block argmin set of the composite objective F(x) = f(x) + ∑ i, g_i(x_i) on dom(F) is subsingleton, every real level set of F is bounded, and x^k is generated by Algorithm 14.3, then every sequential limit point of x^k is a stationary point of the composite problem. As in Lemma_14_2, the Chapter 3 owner is_stationary_point is read using the canonical raw-tuple Euclidean geometry from Chapter 11, not an arbitrary ambient inner product on ((i : Fin p) → Ei i). The properness input required by Theorem 14.3 is derived here from finite dimensionality of that raw-tuple product space.
universe u
open Filter
open scoped Topology
variable {p : ℕ} {Ei : Fin p → Type u}
variable [∀ i, NormedAddCommGroup (Ei i)]
variable [∀ i, InnerProductSpace ℝ (Ei i)]
variable [hrawTupleFiniteDimensional : FiniteDimensional ℝ ((i : Fin p) → Ei i)]
variable (f : ((i : Fin p) → Ei i) → EReal)
variable (g : (i : Fin p) → Ei i → EReal)
variable (x : ℕ → (i : Fin p) → Ei i)
local notation "F" => composite_model_objective f (separableSum g)
-- Proof sketch: convert the Algorithm 14.3 step data to the canonical owner trajectory for `F`,
-- apply Theorem 14.3 (2) to get coordinate-wise minimality of any cluster point, and then use
-- Lemma 14.2 to translate that coordinate-wise minimality into the Chapter 3 stationarity
-- condition for `f + separableSum g`.
theorem alternating_minimization_composite_cluster_point_is_stationary
(hunique :
∀ xBar ∈ effective_domain F, ∀ i : Fin p,
Set.Subsingleton (alternating_minimization_argmin F xBar i))
(hlevel :
∀ α : ℝ, Bornology.IsBounded {y | F y ≤ (α : EReal)})
(hx0 : x 0 ∈ effective_domain F)
(hstep : ∀ k : ℕ, IsAlternatingMinimizationCompositeStep f g (x k) (x (k + 1)))
(xBar : (i : Fin p) → Ei i)
(hxBar : MapClusterPt xBar atTop x) :
is_stationary_point f (separableSum g) xBarDefinition 14.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 14.5: the Chapter 14 composite model is the canonical objective composite_model_objective f (separableSum g).
recall composite_model_objectiveTheorem 14.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 14.5 optimality half: under the Chapter 14.5 hypotheses, every sequential cluster point of the alternating-minimization trajectory globally minimizes the composite objective F.
universe u
open Filter
open scoped Topology Gradient
variable {p : ℕ} {Ei : Fin p → Type u}
variable [∀ i, NormedAddCommGroup (Ei i)]
variable [∀ i, InnerProductSpace ℝ (Ei i)]
variable [FiniteDimensional ℝ ((i : Fin p) → Ei i)]
variable (f : ((i : Fin p) → Ei i) → ℝ)
variable (g : (i : Fin p) → Ei i → EReal)
local notation "F" => composite_model_objective f.toEReal (separableSum g)
-- Semantic recall note: the Chapter 14.5 optimality bridge is routed through
-- `Chap14/Lemma_14_2.lean`, `Chap14/Theorem_14_4.lean`, and `Chap03/Theorem_3_35.lean`, so the
-- smoothness needed downstream is already supplied by `IsAlternatingMinimizationCompositeModel
-- f.toEReal g`; it should not survive as a second public `ContDiffOn` hypothesis here.
variable (x : ℕ → (i : Fin p) → Ei i)
theorem alternating_minimization_cluster_point_is_global_minimizer
(hmodel : IsAlternatingMinimizationCompositeModel f.toEReal g)
(hf_convex : ConvexOn ℝ Set.univ f)
(hlevels : ∀ α : ℝ, Bornology.IsBounded {y | F y ≤ (α : EReal)})
(htraj : is_alternating_minimization_trajectory F x)
{xBar : (i : Fin p) → Ei i} (hxBar : MapClusterPt xBar atTop x) :
IsMinOn F Set.univ xBarTheorem 14.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 14.6 (Assumption 14.10). For the general p-block alternating-minimization problem, (A) each block penalty g_i : E_i → (-∞, ∞] is proper, closed, and convex; (B) the smooth term f : E → ℝ is convex and globally L_f-smooth; (C) for every α > 0 there exists Rα > 0 such that every x with F x ≤ α and every optimal point xStar ∈ XStar = X^* satisfy ‖x - xStar‖ ≤ Rα, where F(x) = f(x) + ∑ i, g_i(x_i); and (D) XStar is the nonempty optimal set and FOpt = F_opt is the optimal value. The Chapter 10 composite smooth owners for f.toEReal are recovered canonically from the inherited Chapter 10 fast proximal-gradient owner rather than stored as duplicate primitive data.
universe u
variable {p : ℕ} {Ei : Fin p → Type u}
variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, NormedSpace ℝ (Ei i)]
class IsAlternatingMinimizationConvexRateProblem
(f : ((i : Fin p) → Ei i) → ℝ) (g : ∀ i : Fin p, Ei i → EReal)
(XStar : outParam (Set ((i : Fin p) → Ei i))) (FOpt : outParam ℝ)
(Lf : outParam NNReal) : Prop
extends IsFastProximalGradientProblem f (separableSum g) XStar FOpt Lf where
bounded_sublevel_distance_to_each_optimal_point (α : PosReal) :
∃ Rα : PosReal, ∀ {x xStar : (i : Fin p) → Ei i},
composite_model_objective f.toEReal (separableSum g) x ≤ ((α : ℝ) : EReal) →
xStar ∈ XStar →
‖x - xStar‖ ≤ (Rα : ℝ)Theorem 14.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 14.7: if Assumption 14.10 holds and x is generated by the alternating-minimization method for F(x) = f(x) + ∑ i, g_i(x_i), then there exists a radius R = R_{F(x^0)} controlling the initial sublevel set {y | F(y) ≤ F(x^0)} such that, for every k ≥ 2, the objective gap satisfies F(x^k) - F_opt ≤ max {((1 / 2)^((k - 1) / 2)) (F(x^0) - F_opt), 8 L_f p^2 R^2 / (k - 1)}.
universe u
variable {p : ℕ} {Ei : Fin p → Type u}
variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, NormedSpace ℝ (Ei i)]
variable {f : ((i : Fin p) → Ei i) → ℝ} {g : ∀ i : Fin p, Ei i → EReal}
variable {XStar : Set ((i : Fin p) → Ei i)} {FOpt : ℝ} {Lf : NNReal}
variable [IsAlternatingMinimizationConvexRateProblem f g XStar FOpt Lf]
local notation "F" => composite_model_objective f.toEReal (separableSum g)
-- Proof sketch: choose one positive level `α` above the initial value `F(x^0)`, extract the
-- corresponding radius witness from Assumption 14.10 once and for all, and then apply the
-- supplied explicit-radius certificate uniformly in `k`.
theorem alternating_minimization_objective_gap_le_max_geometric_or_sublinear
(x : ℕ → (i : Fin p) → Ei i) (htraj : is_alternating_minimization_trajectory F x)
(hExplicitRadiusRate :
∀ (R : PosReal),
(∀ ⦃y xStar : (i : Fin p) → Ei i⦄,
F y ≤ F (x 0) →
xStar ∈ XStar →
‖y - xStar‖ ≤ (R : ℝ)) →
∀ k : ℕ,
2 ≤ k →
(F (x k)).toReal - FOpt ≤
max
(((1 / 2 : ℝ) ^ (((k - 1 : ℕ) : ℝ) / 2)) *
((F (x 0)).toReal - FOpt))
((8 * (Lf : ℝ) * (p : ℝ) ^ (2 : ℕ) * (R : ℝ) ^ (2 : ℕ)) /
((k - 1 : ℕ) : ℝ))) :
∃ R : PosReal,
(∀ ⦃y xStar : (i : Fin p) → Ei i⦄,
F y ≤ F (x 0) →
xStar ∈ XStar →
‖y - xStar‖ ≤ (R : ℝ)) ∧
∀ k : ℕ,
2 ≤ k →
(F (x k)).toReal - FOpt ≤
max
(((1 / 2 : ℝ) ^ (((k - 1 : ℕ) : ℝ) / 2)) *
((F (x 0)).toReal - FOpt))
((8 * (Lf : ℝ) * (p : ℝ) ^ (2 : ℕ) * (R : ℝ) ^ (2 : ℕ)) /
((k - 1 : ℕ) : ℝ))Algorithm 14.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 14.8 in source-facing pair form: x₂⁰ minimizes the initial second-block slice, and for every iteration k the updates x₁^(k+1) and x₂^(k+1) minimize their respective frozen one-variable subproblems. Effective-domain membership of (x₁⁰, x₂⁰) is a separate bridge hypothesis when passing to the canonical Chapter 14 trajectory owner.
universe w
variable {E1 E2 : Type w}
-- `lean_leansearch` is unavailable in this agent environment; this repair follows the local
-- Chapter 14 API already present in the workspace.
@[mk_iff is_two_block_alternating_minimization_trajectory_iff]
class is_two_block_alternating_minimization_trajectory
(f : E1 × E2 → EReal) (g1 : E1 → EReal) (g2 : E2 → EReal)
(x1 : ℕ → E1) (x2 : ℕ → E2) : Prop where
initial :
IsMinOn
(two_block_alternating_minimization_x2_objective f g1 g2 (x1 0))
Set.univ
(x2 0)
step_x1 (k : ℕ) :
IsMinOn
(two_block_alternating_minimization_x1_objective f g1 g2 (x2 k))
Set.univ
(x1 (k + 1))
step_x2 (k : ℕ) :
IsMinOn
(two_block_alternating_minimization_x2_objective f g1 g2 (x1 (k + 1)))
Set.univ
(x2 (k + 1))Theorem 14.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 14.8: if Assumption 14.12 holds and (x₁^k, x₂^k) is generated by the exact two-block alternating-minimization method from Algorithm 14.8, then there exists a radius R = R_{F(x^0)} controlling the initial sublevel set {y | F y ≤ F x[0]} such that, for every k ≥ 2, provided the initial pair x^0 = (x₁^0, x₂^0) lies in dom(F), the objective gap is bounded by the maximum of the geometric term (1 / 2)^((k - 1) / 2) (F(x^0) - F_opt) and the sublinear term 8 min {L₁, L₂} R^2 / (k - 1).
universe u
open scoped Gradient Topology
variable {E1 : Type u} {E2 : Type u}
variable [NormedAddCommGroup E1] [NormedSpace ℝ E1]
variable [NormedAddCommGroup E2] [NormedSpace ℝ E2]
variable {f : E1 × E2 → ℝ} {g1 : E1 → EReal} {g2 : E2 → EReal}
variable {x1 : ℕ → E1} {x2 : ℕ → E2} {XStar : Set (E1 × E2)} {xStar : E1 × E2} {FOpt : ℝ}
variable {L1 L2 R : PosReal}
local notation "F" => two_block_alternating_minimization_objective f.toEReal g1 g2
local notation "x[" k "]" => (x1 k, x2 k)
local notation "φ₁" => twoBlockX1PartialInfimum f g1 g2
local notation "φ₂" => twoBlockX2PartialInfimum f g1 g2
local notation "η₁" => twoBlockX1InactiveMarginal f g2
local notation "η₂" => twoBlockX2InactiveMarginal f g1
theorem two_block_objective_gap_le_max_geometric_or_sublinear
[hproblem : IsTwoBlockAlternatingMinimizationConvexRateProblem f g1 g2 XStar FOpt L1 L2]
(htraj : is_two_block_alternating_minimization_trajectory f.toEReal g1 g2 x1 x2)
(hx0 : x[0] ∈ effective_domain F) :
∃ R : PosReal,
(∀ ⦃y xStar : E1 × E2⦄,
F y ≤ F x[0] →
xStar ∈ XStar →
‖y - xStar‖ ≤ (R : ℝ)) ∧
∀ k : ℕ,
2 ≤ k →
(F x[k]).toReal - FOpt ≤
max
(((1 / 2 : ℝ) ^ (((k - 1 : ℕ) : ℝ) / 2)) *
((F x[0]).toReal - FOpt))
((8 * min (L1 : ℝ) (L2 : ℝ) * ((R : ℝ) ^ (2 : ℕ))) /
((k - 1 : ℕ) : ℝ))Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Algorithm_14_8/PairBridge.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
AlternatingMinimizationCompositeModel.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
CompositeObjectiveDomain.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
Lemma_14_4/InactiveBlockSupport.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
Theorem_14_3_Helpers/PrefixState.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
Theorem_14_3_Helpers/Recovery.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.