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.
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_methodDefinition 11.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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_objectiveLemma 11.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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.
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_stepsizesDefinition 11.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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_objectiveLemma 11.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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.
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.separableSumLemma 11.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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)) LfLemma 11.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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_mappingLemma 11.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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_pointLemma 11.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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.
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.
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.
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.
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.
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
xStarTheorem 11.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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.
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