Chapter 11 — The Block Proximal Gradient Method

Proofs omitted. Hover over highlighted terms to see their Lean types.

Algorithm 11.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Algorithm 11.1: the underlying pathwise stochastic projected-subgradient recursion is the existing Chapter 8 owner stochastic_projected_subgradient_method.

universe u v open Metric variable {E : Type u} {ι : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall stochastic_projected_subgradient_method

Definition 11.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.1 is a bridge/view recall of the Chapter 8 finite-sum model. Domain sampling: - finite_sum_objective is the upstream chapter owner for the aggregate objective x ↦ ∑ i, f i x; - finite_sum_objective_apply is its pointwise evaluation formula; - isMinOn_finite_sum_objective_iff is the canonical feasible-set bridge to the explicit sum. The primitive data here is only the finite family f : Fin m → E → α; the aggregate objective and the minimization reformulation are already owned upstream with the exact interface needed for Definition 11.1. This file therefore recalls those declarations directly instead of keeping a parallel Chapter 11 alias.

recall finite_sum_objective

Lemma 11.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lemma 11.1 (1): on the canonical PiLp 2 Ei aggregate owner, the full Chapter 10 prox-gradient update for PiLp.separableSum g is the PiLp block vector whose coordinates are the Chapter 11 one-block prox points T_L^i(x).

universe u v open scoped Gradient variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] variable [∀ i, InnerProductSpace ℝ (Ei i)] variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : ι) → PosReal} namespace BlockProximalGradientAssumptions variable [hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li] local notation "hcore" => hproblem.toIsBlockProximalGradientProblem local notation "toPiLp" => ContinuousLinearEquiv.symm (PiLp.continuousLinearEquiv (2 : ENNReal) ℝ Ei) theorem prox_grad_operator_eq_block_partial_prox_grad_point_tuple [∀ i, ProperSpace (Ei i)] [ProperSpace (PiLp 2 Ei)] (L : PosReal) (x : ((i : ι) → Ei i)) (hx : x ∈ interior (effective_domain f)) : hproblem.aggregate_prox_grad_operator L (WithLp.toLp 2 x) = WithLp.toLp 2 (fun i ↦ T[L; hcore] x i)

Proposition 11.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Proposition 11.1: under the standing assumptions of the block proximal-gradient method, the sufficient decrease inequality can be written in terms of the full one-block updated vector x⁺ = block_coordinate_update x i (T[Li i; hproblem] x i - x i), as F(x) - F(x⁺) ≥ (L_i / 2) ‖x - x⁺‖².

universe u v open scoped Gradient variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable {Lf : NNReal} {Li : (i : ι) → PosReal} variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} local notation "F" => composite_model_objective f (separableSum g) namespace BlockProximalGradientAssumptions -- Proof sketch: apply the owner theorem -- `BlockProximalGradientAssumptions.block_partial_gradient_sufficient_decrease` at the textbook -- stepsize `M = L_i`. Rewrite the residual through the canonical owner theorem -- `IsBlockProximalGradientProblem.gradient_mapping_def`, so the factor -- `(1 / (2 L_i)) ‖G^i_{L_i}(x)‖²` becomes `(L_i / 2) ‖x_i - T_{L_i}^i(x)‖²`. Then identify the -- full one-block update with `block_coordinate_update x i (T_{L_i}^i(x) - x_i)` and use -- `Pi.norm_single` to rewrite that block residual norm as the full-step norm `‖x - x⁺‖`. theorem block_partial_gradient_sufficient_decrease_step_norm (hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li) (i : ι) [ProperSpace (Ei i)] (x : effective_domain (separableSum g)) : let hcore : IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li := hproblem.toIsBlockProximalGradientProblem; let xPlus := block_coordinate_update x.1 i (T[Li i; hcore] x.1 i - x.1 i); F x.1 - F xPlus ≥ ((((Li i : ℝ) / 2) * ‖x.1 - xPlus‖ ^ (2 : ℕ) : ℝ) : EReal)

Theorem 11.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.1 (1): assuming the source hypotheses that each block penalty g_i is proper, closed, and convex, that f is proper and closed with convex effective domain, that effective_domain (separableSum g) lies in interior (effective_domain f), and that the chosen block map block_gradient i x is the gradient of the i-th block slice d ↦ f(x + 𝒰[i] d) on that interior, a point x is stationary for f + separableSum g if and only if every block satisfies the coordinatewise subdifferential condition `-(block_gradient i x) ∈ euclideanSubdifferential (g i) (x i)`.

open scoped Gradient Pointwise open InnerProductSpace (toDualMap) universe u v variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [hrawTupleFiniteDimensional : FiniteDimensional ℝ ((i : ι) → Ei i)] variable {f : ((i : ι) → Ei i) → EReal} variable {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} {Lf : NNReal} {Li : (i : ι) → PosReal} theorem is_stationary_point_iff_coordinatewise_negative_block_gradient_mem_euclideanSubdifferential (hf_proper : IsProperExtendedRealFunction f) (hg_proper : ∀ i, IsProperExtendedRealFunction (g i)) (hg_closed : ∀ i, LowerSemicontinuous (g i)) (hg_convex : ∀ i, is_convex_function (g i)) (hf_closed : LowerSemicontinuous f) (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain (separableSum g) ⊆ interior (effective_domain f)) (hf_toReal_differentiableOn_interior_effective_domain : DifferentiableOn ℝ (fun y ↦ (f y).toReal) (interior (effective_domain f))) (hblock_partial_gradient_spec : ∀ i {x : (j : ι) → Ei j}, x ∈ interior (effective_domain f) → HasFDerivAt (block_coordinate_slice f x i) (InnerProductSpace.toDualMap ℝ (Ei i) (block_gradient i x)) 0) (x : (i : ι) → Ei i) : @is_stationary_point ((i : ι) → Ei i) (rawTupleNormedAddCommGroup (ι := ι) (Ei := Ei)) (rawTupleInnerProductSpace (ι := ι) (Ei := Ei)) (rawTupleFiniteDimensionalMain (ι := ι) (Ei := Ei)) f (separableSum g) x ↔ ∀ i, -(block_gradient i x) ∈ euclideanSubdifferential (g i) (x i)

Algorithm 11.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Algorithm 11.2: the textbook proximal-gradient recursion with positive stepsizes is already the existing Chapter 10 owner is_proximal_gradient_trajectory_with_stepsizes.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall is_proximal_gradient_trajectory_with_stepsizes

Definition 11.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.2: the proximal gradient model min_{x ∈ E} f(x) + g(x) is the same composite objective owner composite_model_objective used earlier for the pointwise sum F(x) = f(x) + g(x).

recall composite_model_objective

Lemma 11.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lemma 11.2: under Definition 11.4, the textbook one-block update satisfies the quadratic upper model with the corresponding block Lipschitz constant L_i.

universe u v variable {ι : Type u} {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] namespace BlockProximalGradientAssumptions variable [Fintype ι] variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : ι) → PosReal} theorem block_coordinate_descent_lemma (hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li) (i : ι) [CompleteSpace (Ei i)] {x : (j : ι) → Ei j} {d : Ei i} (hx : x ∈ interior (effective_domain f)) (hxd : x + 𝒰[i] d ∈ interior (effective_domain f)) : (f (x + 𝒰[i] d)).toReal ≤ (f x).toReal + inner ℝ (block_gradient i x) d + ((Li i : ℝ) / 2) * ‖d‖ ^ (2 : ℕ)

Theorem 11.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.2 (1): for a fixed block index i, the norm of the partial gradient mapping G_L^i(x) is monotone nondecreasing in the positive parameter L. Thus if L₁ ≥ L₂ > 0, then ‖G^i_{L₂}(x)‖ ≤ ‖G^i_{L₁}(x)‖.

universe u v open scoped Gradient variable {ι : Type u} {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable {f : ((j : ι) → Ei j) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable (hg_proper : ∀ i, IsProperExtendedRealFunction (g i)) (hg_closed : ∀ i, LowerSemicontinuous (g i)) (hg_convex : ∀ i, is_convex_function (g i)) local notation "BlockSpace" => (j : ι) → Ei j variable (i : ι) [ProperSpace (Ei i)] theorem block_partial_gradient_mapping_norm_monotone (L₁ L₂ : PosReal) (hL : L₂ ≤ L₁) (x : BlockSpace) (hblock : HasGradientAt (block_coordinate_slice f x i) (block_gradient i x) 0) : ‖G[L₂; g, block_gradient, hg_proper, hg_closed, hg_convex] x i‖ ≤ ‖G[L₁; g, block_gradient, hg_proper, hg_closed, hg_convex] x i‖

Algorithm 11.3

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Algorithm 11.3's textbook one-block proximal-gradient step is exactly the canonical Chapter 11 one-block update with displacement T_i(x) - x_i.

universe u v variable {ι : Type u} {Ei : ι → Type v} variable [∀ i, AddCommGroup (Ei i)] theorem block_proximal_gradient_update_eq_add_block_embedding (T : (i : ι) → ((j : ι) → Ei j) → Ei i) (x : (j : ι) → Ei j) (i : ι) : block_coordinate_update x i (T i x - x i) = x + 𝒰[i] (T i x - x i)

Definition 11.3

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.3: on the block product PiLp (2 : ENNReal) E, the objective F(x) = f(x) + ∑ i, g_i(x_i) is the canonical composite objective composite_model_objective f (PiLp.separableSum g), the block insertion map 𝒰ᵢ is the canonical singleton insertion PiLp.single 2 i, the block partial gradient ∇ᵢ f(x) is the i-th coordinate of ∇ f(x), and the block norm formula is PiLp.norm_eq_of_L2.

open scoped BigOperators Gradient universe u v recall PiLp.separableSum

Lemma 11.3

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lemma 11.3: if the i-th block partial gradient is M-Lipschitz along block updates and the block-separable effective domain lies in interior (effective_domain f), then replacing the i-th block by its one-block proximal-gradient update decreases the composite objective by at least (1 / (2 M)) ‖G_M^i(x)‖^2.

universe u v open scoped BigOperators Gradient variable {ι : Type u} {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [Fintype ι] -- Proof sketch: let `x⁺ = x + 𝒰_i(T_M^i(x) - x_i)`. The block descent lemma gives the quadratic -- upper bound on `f x⁺` because `x ∈ effective_domain (separableSum g)` implies -- `x ∈ interior (effective_domain f)`, and the updated point stays in the effective domain of the -- block-separable regularizer, hence also in `interior (effective_domain f)`. The second prox -- theorem controls the linear term together with the change in `g i`, while the remaining block -- penalties are unchanged. Finally rewrite the residual `M • (x_i - T_M^i(x))` as `G_M^i(x)`. namespace IsBlockProximalGradientProblem variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} variable {Li : (i : ι) → PosReal} local notation "F" => composite_model_objective f (separableSum g) theorem block_partial_gradient_sufficient_decrease_of_block_lipschitz (hproblem : IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li) (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (i : ι) [ProperSpace (Ei i)] (M : PosReal) (h_block_gradient_lipschitz : ∀ (x : (i : ι) → Ei i) (d : Ei i) (_ : x ∈ interior (effective_domain f)) (_ : block_coordinate_update x i d ∈ interior (effective_domain f)), ‖block_gradient i x - block_gradient i (block_coordinate_update x i d)‖ ≤ (M : ℝ) * ‖d‖) (x : effective_domain (separableSum g)) : let x' : (j : ι) → Ei j := x let xPlus := block_coordinate_update x' i (T[M; hproblem] x' i - x' i) F x' - F xPlus ≥ ((((1 : ℝ) / (2 * (M : ℝ))) * ‖G[M; hproblem] x' i‖ ^ (2 : ℕ) : ℝ) : EReal)

Algorithm 11.4

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Algorithm 11.4: for an initial point x^0 ∈ int(dom f), the cyclic block proximal gradient method generates outer iterates x^k by setting x^{k,0} = x^k, then cycling through the block updates x^{k,i} = x^{k,i-1} + U_i(T_{L_i}(x^{k,i-1}) - x_i^{k,i-1}), and finally defining x^{k+1} = x^{k,p}.

universe v open scoped Gradient variable {p : ℕ} {Ei : Fin p → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {f : ((i : Fin p) → Ei i) → EReal} {g : (i : Fin p) → Ei i → EReal} variable {block_gradient : (i : Fin p) → ((j : Fin p) → Ei j) → Ei i} variable {XStar : Set ((i : Fin p) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : Fin p) → PosReal} def cyclic_block_proximal_gradient_method (hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li) (x0 : interior (effective_domain f)) : ℕ → ((i : Fin p) → Ei i)

Definition 11.4

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.4: assumptions (A)-(E) for the block proximal-gradient method mean that each block penalty g_i : E_i → (-∞, ∞] is proper, closed, and convex; the smooth term f : (Π i, E_i) → (-∞, ∞] never takes the value -∞, is closed with convex effective domain, the effective domain of x ↦ ∑ i, g_i(x_i) lies in the interior of the effective domain of f, and x ↦ (f x).toReal is differentiable and L_f-smooth on that interior, so these clauses imply that f is proper; for each block index i, the chosen block gradient map block_gradient i x = ∇_i f(x) is the gradient of the one-block slice d ↦ f(x + 𝒰[i] d) at d = 0 and is L_i-Lipschitz along the i-th block direction; and XStar = X^* is the nonempty optimal set of the composite objective with optimal value FOpt = F_opt.

universe u v open scoped BigOperators Gradient variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] class BlockProximalGradientAssumptions (f : ((i : ι) → Ei i) → EReal) (g : (i : ι) → Ei i → EReal) (block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i) (XStar : Set ((i : ι) → Ei i)) (FOpt : ℝ) (Lf : NNReal) (Li : (i : ι) → PosReal) : Prop extends IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li where f_effective_domain_convex : Convex ℝ (effective_domain f) f_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun x ↦ (f x).toReal) (interior (effective_domain f)) Lf

Lemma 11.4

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lemma 11.4 (1): for part (a), the objective decrease across one cyclic block update satisfies equation (11.9), F(x^{k,j}) - F(x^{k,j+1}) ≥ (1 / (2 L_j)) ‖G_{L_j}^j(x^{k,j})‖^2.

universe u v open scoped BigOperators Gradient variable {p : ℕ} {Ei : Fin p → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {f : ((i : Fin p) → Ei i) → EReal} {g : (i : Fin p) → Ei i → EReal} variable {block_gradient : (i : Fin p) → ((j : Fin p) → Ei j) → Ei i} variable {XStar : Set ((i : Fin p) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : Fin p) → PosReal} variable (hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li) variable (x0 : effective_domain (separableSum g)) local notation "F" => composite_model_objective f (separableSum g) local notation "Lmin" => cbpg_min_block_stepsize Li local notation "toPiLp" => ContinuousLinearEquiv.symm (PiLp.continuousLinearEquiv (2 : ENNReal) ℝ Ei) local notation "x0'" => hproblem.interior_effective_domain_point x0 local notation "x[" k "]" => cyclic_block_proximal_gradient_method hproblem x0' k local notation "x[" k "," i "]" => cyclic_block_proximal_gradient_inner_iterate hproblem x[k] i theorem cbpg_auxiliary_sufficient_decrease_gradient_mapping (k : ℕ) (j : Fin p) : F x[k, j.1] - F x[k, j.1 + 1] ≥ ((((1 : ℝ) / (2 * (Li j : ℝ))) * ‖G[Li j; (hproblem.toIsBlockProximalGradientProblem)] x[k, j.1] j‖ ^ (2 : ℕ) : ℝ) : EReal)

Algorithm 11.5

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Algorithm 11.5, as a pathwise recursion: from an initial point x0 and a realized sequence sampled_block k = i_k of block indices, the randomized block proximal-gradient iterates satisfy x^0 = x0 and x^{k+1} = block_coordinate_update x^k i_k (T_{L_{i_k}}^{i_k}(x^k) - x^k_{i_k}). Later Chapter 11 results apply this owner to initial data known to lie in int(dom f), but that admissibility is not primitive data of the recursion itself.

universe u v open scoped Gradient variable {ι : Type u} {Ei : ι → Type v} variable [Fintype ι] variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {Li : (i : ι) → PosReal} variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} def randomized_block_proximal_gradient_method (hproblem : IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li) (x0 : (i : ι) → Ei i) (sampled_block : ℕ → ι) : ℕ → ((i : ι) → Ei i)

Definition 11.5

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.5: the Chapter 11 gradient mapping is the previously defined Chapter 10 proximal-gradient mapping prox_gradient_mapping, whose core owner is gradient_mapping with residual formula G_L^{f,g}(x) = L • (x - T_L^{f,g}(x)). The auxiliary update T_L^{f,g} is already owned upstream by prox_grad_operator.

recall gradient_mapping

Lemma 11.5

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lemma 11.5: under Assumption 11.1, if x^k is generated by the cyclic block proximal gradient method, then for every k ≥ 0 the sufficient-decrease estimate F(x^k) - F(x^(k+1)) ≥ (C / p) * ‖G_{L_min}(x^k)‖^2 holds in the canonical block L² norm, where C = L_min / (2 (L_f + 2 L_max + sqrt (L_min L_max))^2).

universe v open scoped BigOperators Gradient variable {p : ℕ} {Ei : Fin p → Type v} variable [Nonempty (Fin p)] variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {f : ((i : Fin p) → Ei i) → EReal} {g : (i : Fin p) → Ei i → EReal} variable {block_gradient : (i : Fin p) → ((j : Fin p) → Ei j) → Ei i} variable {XStar : Set ((i : Fin p) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : Fin p) → PosReal} variable (hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li) variable (x0 : effective_domain (separableSum g)) local notation "hcore" => hproblem.toIsBlockProximalGradientProblem local notation "x0I" => hproblem.interior_effective_domain_point x0 local notation "x[" k "]" => cyclic_block_proximal_gradient_method hproblem x0I k local notation "x[" k "," m "]" => cyclic_block_proximal_gradient_inner_iterate hproblem x[k] m local notation "F" => composite_model_objective f (separableSum g) local notation "Lmin" => cbpg_min_block_stepsize Li local notation "Lmax" => cbpg_max_block_stepsize Li local notation "Gcbpg[" k "]" => fun i ↦ G[Lmin; hcore] x[k] i local notation "toPiLp" => ContinuousLinearEquiv.symm (PiLp.continuousLinearEquiv (2 : ENNReal) ℝ Ei) theorem cbpg_sufficient_decrease_gradient_mapping (k : ℕ) : F x[k] - F x[k + 1] ≥ (((cbpg_sufficient_decrease_constant Lf Li / (p : ℝ)) * ‖toPiLp Gcbpg[k]‖ ^ (2 : ℕ) : ℝ) : EReal)

Theorem 11.5

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.5: the outer-step sufficient-decrease estimate from Lemma 11.4 implies that each CBPG outer step weakly decreases the composite objective value F(x^k).

universe v variable {p : ℕ} {Ei : Fin p → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {f : ((i : Fin p) → Ei i) → EReal} {g : (i : Fin p) → Ei i → EReal} variable {block_gradient : (i : Fin p) → ((j : Fin p) → Ei j) → Ei i} variable {XStar : Set ((i : Fin p) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : Fin p) → PosReal} variable (hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li) variable (x0 : effective_domain (separableSum g)) local notation "x0I" => hproblem.interior_effective_domain_point x0 local notation "Lmin" => cbpg_min_block_stepsize Li local notation "toPiLp" => ContinuousLinearEquiv.symm (PiLp.continuousLinearEquiv (2 : ENNReal) ℝ Ei) local notation "x[" k "]" => cyclic_block_proximal_gradient_method hproblem x0I k local notation "F" => composite_model_objective f (separableSum g) local notation "Δ[" k "]" => ((((Lmin : ℝ) / 2) * ‖toPiLp x[k] - toPiLp x[k + 1]‖ ^ (2 : ℕ) : ℝ) : EReal) theorem cbpg_objective_step_monotone (k : ℕ) : F x[k + 1] ≤ F x[k]

Definition 11.6

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.6: the one-block proximal-gradient point is the existing Chapter 11 owner block_partial_prox_grad_point, written on the theorem surface as (T[M; g, block_gradient, hg_proper, hg_closed, hg_convex]) x i, the unique point of prox[((1 / M) • g_i)] (x_i - (1 / M) • block_gradient_i(x)).

recall block_partial_prox_grad_point

Lemma 11.6

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lemma 11.6: abstracting the convex-CBPG proof to its two source inequalities, the quadratic objective-gap control (11.18) together with the sufficient-decrease estimate (11.11) implies the one-step lower bound F(xᵏ) - F(xᵏ⁺¹) ≥ c * (F(xᵏ⁺¹) - F_opt)^2, where c = L_min / (2 p (L_f + L_max)^2 R_α^2).

universe u variable {p : ℕ} variable [Nonempty (Fin p)] variable {X : Type u} [NormedAddCommGroup X] variable {Lf : NNReal} {Li : Fin p → PosReal} variable {F : X → EReal} {x : ℕ → X} {FOpt : ℝ} theorem cbpg_step_decrease_ge_sq_objective_gap (Rα : PosReal) (k : ℕ) (hGapSq : cbpgObjectiveGapSqBound Lf Li Rα F x FOpt k) (hStep : cbpgStepDecreaseBound Li F x k) : F (x k) - F (x (k + 1)) ≥ ((cbpg_quadratic_gap_constant Lf Li Rα * (((F (x (k + 1))).toReal - FOpt) ^ (2 : ℕ)) : ℝ) : EReal)

Theorem 11.6

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.6: in the convex case of the cyclic block proximal gradient method, the standing Chapter 11 block proximal-gradient assumptions are supplemented by (A) convexity of the smooth term f and (B) the requirement that every positive sublevel set of the composite objective F(x) = f(x) + ∑ i, g_i(x_i) stays within a uniformly bounded distance of every optimal point x* ∈ X^*: for each α > 0 there is Rα > 0 such that F(x) ≤ α implies ‖x - x*‖ ≤ Rα for all x* ∈ X^*. The weaker infDist reformulation is derived below as a bridge theorem, but it is not the primitive source-facing field.

universe u v open Metric variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable {Lf : NNReal} {Li : (i : ι) → PosReal} class CyclicBlockProximalGradientConvexAssumptions (f : ((i : ι) → Ei i) → EReal) (g : (i : ι) → Ei i → EReal) (block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i) (XStar : Set ((i : ι) → Ei i)) (FOpt : ℝ) (Lf : NNReal) (Li : (i : ι) → PosReal) : Prop extends BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li where f_convex : is_convex_function f bounded_sublevel_distance_to_each_optimal_point (α : PosReal) : ∃ Rα : PosReal, SublevelDistanceToEachOptimalPointBound f g XStar α Rα

Definition 11.7

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.7: if the ith block penalty vanishes identically, then the ith partial gradient mapping namely x ↦ (G[L; g, block_gradient, hg_proper, hg_closed, hg_convex]) x i, coincides on interior (effective_domain f) with the map x ↦ block_gradient i x, which encodes x ↦ ∇_i f(x) in the standing block setup.

universe u v open scoped Gradient variable {ι : Type u} {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable (f : ((i : ι) → Ei i) → EReal) (g : (i : ι) → Ei i → EReal) variable (block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i) variable (hg_proper : ∀ i, IsProperExtendedRealFunction (g i)) variable (hg_closed : ∀ i, LowerSemicontinuous (g i)) variable (hg_convex : ∀ i, is_convex_function (g i)) local notation "BlockSpace" => ((j : ι) → Ei j) theorem partial_gradient_mapping_eq_block_gradient_of_block_penalty_eq_zero (L : PosReal) (i : ι) (hgi_zero : g i = 0) : (fun x : interior (effective_domain f) ↦ (G[L; g, block_gradient, hg_proper, hg_closed, hg_convex]) (x : BlockSpace) i) = fun x : interior (effective_domain f) ↦ block_gradient i (x : BlockSpace)

Lemma 11.7

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lemma 11.7 (1): if a nonnegative scalar sequence satisfies a k - a (k + 1) ≥ (1 / γ) * a (k + 1)^2 for every k and some positive γ, then for every n ≥ 2 one has a n ≤ max {((1 / 2)^((n - 1) / 2)) * a 0, 4γ / (n - 1)}.

variable {a : ℕ → ℝ} {γ : PosReal} variable (ha_nonneg : ∀ k : ℕ, 0 ≤ a k) variable (hstep : ∀ k : ℕ, a k - a (k + 1) ≥ (1 / (γ : ℝ)) * (a (k + 1)) ^ 2) include ha_nonneg hstep lemma nonnegative_sequence_le_max_geometric_or_sublinear_of_quadratic_step_recurrence {n : ℕ} (hn : 2 ≤ n) : a n ≤ max (((1 / 2 : ℝ) ^ (((n - 1 : ℕ) : ℝ) / 2)) * a 0) (4 * (γ : ℝ) / ((n - 1 : ℕ) : ℝ))

Theorem 11.7

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.7 (1): under Assumptions 11.1 and 11.15, there exists a radius R_α together with the corresponding initial-sublevel distance witness such that the CBPG objective gap at iteration k ≥ 2 is bounded by the maximum of the geometric and sublinear terms with that R_α.

universe v open Metric open scoped Gradient variable {p : ℕ} {Ei : Fin p → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, CompleteSpace (Ei i)] [∀ i, ProperSpace (Ei i)] variable [Nonempty (Fin p)] variable {f : ((i : Fin p) → Ei i) → EReal} {g : (i : Fin p) → Ei i → EReal} variable {block_gradient : (i : Fin p) → ((j : Fin p) → Ei j) → Ei i} variable {XStar : Set ((i : Fin p) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : Fin p) → PosReal} variable (hconvex : CyclicBlockProximalGradientConvexAssumptions f g block_gradient XStar FOpt Lf Li) variable (x0 : effective_domain (separableSum g)) local notation "hproblem" => hconvex.toBlockProximalGradientAssumptions local notation "x0I" => hconvex.interior_effective_domain_point x0 local notation "x[" k "]" => cyclic_block_proximal_gradient_method hproblem x0I k local notation "x[" k "," i "]" => cyclic_block_proximal_gradient_inner_iterate hproblem x[k] i local notation "F" => composite_model_objective f (separableSum g) local notation "toPiLp" => ContinuousLinearEquiv.symm (PiLp.continuousLinearEquiv (2 : ENNReal) ℝ Ei) local notation "x₂[" k "]" => toPiLp x[k] local notation "XStar₂" => toPiLp '' XStar local notation "Δ[" k "]" => (F x[k]).toReal - FOpt local notation "RadiusBound" => fun Rα : PosReal ↦ ∀ ⦃x⦄, F x ≤ F x[0] → infDist (toPiLp x) XStar₂ ≤ Rα local notation "GapBound[" Rα "," k "]" => max (((1 / 2 : ℝ) ^ (((k - 1 : ℕ) : ℝ) / 2)) * Δ[0]) (4 / (cbpg_quadratic_gap_constant Lf Li Rα * ((k - 1 : ℕ) : ℝ))) local notation "IterationThreshold[" Rα "," ε "]" => max ((2 / Real.log 2) * (Real.log (Δ[0]) + Real.log (1 / (ε : ℝ)))) (4 / (cbpg_quadratic_gap_constant Lf Li Rα * (ε : ℝ))) + 1 -- Match the singleton-coordinate owner in Lemma 11.5 definitionally. include hconvex x0 theorem cbpg_objective_gap_le_max_geometric_or_sublinear (k : ℕ) (hk : 2 ≤ k) : ∃ Rα : PosReal, RadiusBound Rα ∧ Δ[k] ≤ GapBound[Rα,k]

Theorem 11.8

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.8: if a convex differentiable function on a finite block product ∏ i, E_i has canonical block partial gradients ∇ᵢ φ that are L_i-Lipschitz along the i-th block direction 𝒰ᵢ(d), then φ is globally L-smooth with L = ∑ i, L_i.

universe u v open scoped BigOperators Gradient variable {ι : Type v} [Fintype ι] variable {E : ι → Type u} variable [∀ i, NormedAddCommGroup (E i)] [∀ i, InnerProductSpace ℝ (E i)] variable [∀ i, CompleteSpace (E i)] theorem convex_block_partial_gradients_lipschitz_is_l_smooth_on (φ : PiLp (2 : ENNReal) E → ℝ) (Li : ι → NNReal) (hφ_convex : ConvexOn ℝ Set.univ φ) (hφ_diff : Differentiable ℝ φ) (h_block_partial_gradient_lipschitz : ∀ (i : ι) (x : PiLp (2 : ENNReal) E) (d : E i), ‖(∇[i] φ) x - (∇[i] φ) (x + 𝒰[i] d)‖ ≤ (Li i : ℝ) * ‖d‖) : is_l_smooth_on φ Set.univ (∑ i, Li i)

Theorem 11.10

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.10: Remark 11.22 rewrites step (b) of the randomized block proximal gradient algorithm as x^{k+1} = x^k - (1 / L_{i_k}) 𝒰_{i_k}(G^{i_k}_{L_{i_k}}(x^k)).

universe u v open scoped Gradient variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {Li : (i : ι) → PosReal} variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} variable (hproblem : IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li) variable (x0 : interior (effective_domain f)) variable (sampled_block : ℕ → ι) local notation "x[" k "]" => randomized_block_proximal_gradient_method hproblem x0 sampled_block k -- Proof sketch: combine the recursive RBPG update -- `randomized_block_proximal_gradient_method_succ` with the one-step reformulation -- `block_coordinate_update_eq_sub_block_partial_gradient_mapping` at the -- realized sampled block `i_k = sampled_block k`. theorem randomized_block_proximal_gradient_method_succ_eq_sub_block_partial_gradient_mapping (k : ℕ) : x[k + 1] = x[k] - (1 / (Li (sampled_block k) : ℝ)) • 𝒰[sampled_block k] (G[Li (sampled_block k); hproblem] x[k] (sampled_block k))

Theorem 11.11

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.11: for RBPG iterates generated by i.i.d. uniformly sampled blocks, the expected objective gap satisfies the sublinear estimate E[F(x^(k + 1))] - F_opt ≤ (|ι| / (|ι| + k + 1)) rbpg_initial_lyapunov.

universe u v w open MeasureTheory ProbabilityTheory open scoped ProbabilityTheory RBPG BigOperators Gradient variable {Ω : Type w} [MeasurableSpace Ω] variable {ι : Type u} [Fintype ι] [MeasurableSpace ι] [DiscreteMeasurableSpace ι] variable {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {Li : ι → PosReal} variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} variable {Ω : Type w} [MeasurableSpace Ω] variable {ι : Type u} [Fintype ι] [MeasurableSpace ι] [DiscreteMeasurableSpace ι] variable {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {Li : ι → PosReal} variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} theorem randomized_block_proximal_gradient_expected_objective_gap_le_sublinear (hproblem : RandomizedBlockProximalGradientAssumptions f g block_gradient XStar FOpt Li) (x0 : effective_domain (separableSum g)) (sampled_block : ℕ → Ω → ι) (μ : Measure Ω) [IsProbabilityMeasure μ] (xStar : (i : ι) → Ei i) (hxStar : xStar ∈ XStar) (h_sampled_block_meas : ∀ k, Measurable (sampled_block k)) (h_sampled_block_indep : iIndepFun sampled_block μ) (h_sampled_block_uniform : ∀ k (i : ι), μ ((sampled_block k) ⁻¹' {i}) = 1 / (Fintype.card ι : ENNReal)) (k : ℕ) : rbpg_expected_objective_gap hproblem x0 sampled_block μ (k + 1) ≤ ((Fintype.card ι : ℝ) / (Fintype.card ι + k + 1 : ℝ)) * rbpg_initial_lyapunov Li FOpt (composite_model_objective f (separableSum g)) x0 xStar

Theorem 11.12

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.12 (1): clause (a). Under Assumption 11.1, the Chapter 11 residual tuple i ↦ G^i_{L_min}(x^k), viewed in the canonical block L² owner PiLp (2 : ENNReal) Ei, converges to 0 along the outer iterates.

universe v open scoped Gradient Pointwise BigOperators variable {p : ℕ} {Ei : Fin p → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {f : ((i : Fin p) → Ei i) → EReal} {g : (i : Fin p) → Ei i → EReal} variable {block_gradient : (i : Fin p) → ((j : Fin p) → Ei j) → Ei i} variable {XStar : Set ((i : Fin p) → Ei i)} {FOpt : ℝ} variable {Lf : NNReal} {Li : (i : Fin p) → PosReal} variable [Nonempty (Fin p)] variable (hproblem : BlockProximalGradientAssumptions f g block_gradient XStar FOpt Lf Li) variable (x0 : effective_domain (separableSum g)) local notation "x0I" => hproblem.interior_effective_domain_point x0 local notation "x[" k "]" => cyclic_block_proximal_gradient_method hproblem x0I k local notation "hcore" => hproblem.toIsBlockProximalGradientProblem local notation "Lmin" => cbpg_min_block_stepsize Li local notation "F" => composite_model_objective f (separableSum g) local notation "Ccbpg" => cbpg_sufficient_decrease_constant Lf Li local notation "toPiLp" => ContinuousLinearEquiv.symm (PiLp.continuousLinearEquiv (2 : ENNReal) ℝ Ei) local notation "Gcbpg" => fun k ↦ toPiLp (fun i ↦ G[Lmin; hcore] x[k] i) local notation "Rcbpg" => fun k ↦ best_achieved_function_value (fun y ↦ ‖y‖) Gcbpg k theorem cbpg_gradient_mapping_tendsto_zero : Filter.Tendsto Gcbpg Filter.atTop (nhds 0)

Definition 11.13

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.13: Assumption 11.21 for the randomized block proximal gradient method fixes block penalties g_i : E_i → (-∞, ∞], a smooth term f : (Π i, E_i) → (-∞, ∞], chosen block partial gradients block_gradient i x = ∇_i f(x), explicit positive block Lipschitz constants L_i, and optimality data XStar = X^*, FOpt = F_opt, such that (A) each g_i is proper, closed, and convex; (B) f is proper, closed, and convex, the effective domain of x ↦ ∑ i, g_i(x_i) is contained in interior (effective_domain f), and (fun x ↦ (f x).toReal) is differentiable on that interior; (C) each chosen block partial gradient is the gradient of the one-block slice d ↦ f(block_coordinate_update x i d) at d = 0 and is L_i-Lipschitz along the i-th block direction; and (D) XStar is the nonempty optimal set of the composite objective with optimal value FOpt.

universe u v variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable {Li : (i : ι) → PosReal} class RandomizedBlockProximalGradientAssumptions (f : ((i : ι) → Ei i) → EReal) (g : (i : ι) → Ei i → EReal) (block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i) (XStar : Set ((i : ι) → Ei i)) (FOpt : ℝ) (Li : (i : ι) → PosReal) : Prop extends IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li where f_convex : is_convex_function f f_toReal_differentiableOn_interior_effective_domain : DifferentiableOn ℝ (fun x ↦ (f x).toReal) (interior (effective_domain f))

Theorem 11.13

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Theorem 11.13: along any realized RBPG sample path, each step decreases the composite objective by at least (1 / (2 L_{i_k})) ‖G^{i_k}_{L_{i_k}}(x^k)‖^2.

universe u v open scoped BigOperators Gradient variable {ι : Type u} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {Li : (i : ι) → PosReal} variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} namespace RandomizedBlockProximalGradientAssumptions variable (hproblem : RandomizedBlockProximalGradientAssumptions f g block_gradient XStar FOpt Li) variable (x0 : effective_domain (separableSum g)) variable (sampled_block : ℕ → ι) -- Proof sketch: combine the iterate-domain theorem with the owner-level sufficient-decrease -- theorem -- `IsBlockProximalGradientProblem.block_partial_gradient_sufficient_decrease_of_block_lipschitz` -- from `Lemma_11_3`, specialized to the current iterate `x[k]` and the realized sampled block -- `i_k = sampled_block k`. The convexity input is supplied by -- `effective_domain_convex_of_is_convex_function hproblem.f_convex`, and the resulting one-step -- update agrees with `x[k + 1]` by `randomized_block_proximal_gradient_method_succ`. theorem randomized_block_proximal_gradient_sufficient_decrease (k : ℕ) : composite_model_objective f (separableSum g) (randomized_block_proximal_gradient_method hproblem.toIsBlockProximalGradientProblem (hproblem.interior_effective_domain_point x0) sampled_block k) - composite_model_objective f (separableSum g) (randomized_block_proximal_gradient_method hproblem.toIsBlockProximalGradientProblem (hproblem.interior_effective_domain_point x0) sampled_block (k + 1)) ≥ ((((1 : ℝ) / (2 * (Li (sampled_block k) : ℝ))) * ‖G[Li (sampled_block k); hproblem.toIsBlockProximalGradientProblem] (randomized_block_proximal_gradient_method hproblem.toIsBlockProximalGradientProblem (hproblem.interior_effective_domain_point x0) sampled_block k) (sampled_block k)‖ ^ (2 : ℕ) : ℝ) : EReal)

Definition 11.14

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Definition 11.14: the randomized block gradient mapping packages the block residuals G^i_{L_i}(x) into a single block vector.

universe u v open MeasureTheory ProbabilityTheory open scoped ProbabilityTheory ENNReal BigOperators Gradient variable {ι : Type u} {Ei : ι → Type v} variable [Fintype ι] variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, ProperSpace (Ei i)] variable {f : ((i : ι) → Ei i) → EReal} {g : (i : ι) → Ei i → EReal} variable {block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i} variable {XStar : Set ((i : ι) → Ei i)} {FOpt : ℝ} variable {Li : (i : ι) → PosReal} abbrev randomized_block_gradient_mapping (h : IsBlockProximalGradientProblem f g block_gradient XStar FOpt Li) (x : (i : ι) → Ei i) : (i : ι) → Ei i := fun i ↦ G[Li i; h] x i