Chapter 12 — Dual-Based Proximal Gradient Methods

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

Lemma 12.0.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 12.0.1: for every real x > 0, one has log (1 + x) < x.

theorem log_one_add_lt_self {x : ℝ} (hx : 0 < x) : Real.log (1 + x) < x

Proposition 12.0.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

Proposition 12.0.2 is a bridge/view item: the source-facing series starts at n = 1, while the core owner abstraction is the mathlib p-series theorem Real.summable_one_div_nat_pow, stated on n : ℕ starting at 0. The proposition is the canonical shift-by-one specialization of that owner.

recall summable_nat_add_iff

Theorem 12.0.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

Theorem 12.0.3 is a core/canonical recall in one-variable calculus. Domain sampling: - exists_hasDerivAt_eq_slope is the HasDerivAt owner form of Lagrange's theorem; - exists_deriv_eq_slope is the canonical deriv owner matching the textbook statement; - exists_deriv_eq_slope' is the same theorem in slope notation; - exists_deriv_eq_zero is the nearby Rolle specialization. The Chapter 12 item adds no new source-facing data or bridge construction, so the correct public surface is the direct recall of exists_deriv_eq_slope.

recall exists_deriv_eq_slope

Theorem 12.0.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

Theorem 12.0.4: the sequence s_m = ∑_{n=1}^m 1 / n^2 is bounded.

open scoped BigOperators open Bornology theorem one_div_nat_sq_partialSums_isBounded : IsBounded (Set.range (fun m : ℕ ↦ ∑ n ∈ Finset.range m, 1 / ((n + 1 : ℕ) : ℝ) ^ (2 : ℕ)))

Definition 12.0.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 12.0.6: the textbook notion of a smooth real-valued function on an open interval I is the canonical mathlib predicate ContDiffOn ℝ ∞ f I.

open scoped ContDiff variable (f : ℝ → ℝ) (I : Set ℝ) #check ContDiffOn ℝ ∞ f I

Algorithm 12.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 12.1: given an initial point y^0 = y0 and a constant admissible parameter L ≥ ‖A‖² / σ, a sequence y is a dual proximal-gradient trajectory for the dual representation for the dual objective F + G when it starts at y0 and follows the canonical proximal-gradient trajectory for F + G with the constant parameter L.

universe u v open scoped Gradient variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [NormedAddCommGroup V] [NormedSpace ℝ V] class is_dual_based_proximal_gradient_dual_trajectory (F G : V → EReal) [InnerProductSpace ℝ V] [CompleteSpace V] {A : E →L[ℝ] V} {σ : PosReal} (L : DualBasedProximalGradientDualStepsizeParameter A σ) (y : ℕ → V) (y0 : V) : Prop where zero_eq : y 0 = y0 trajectory : is_proximal_gradient_trajectory F G y (fun _ ↦ (L : PosReal)) -- Proof sketch: extract the initialization equation from the first conjunct of -- `is_dual_based_proximal_gradient_dual_trajectory`.

Definition 12.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 12.1: the primal objective for the dual-based proximal-gradient model is the Chapter 10 composite objective specialized to f and g ∘ A.

universe u v open Set variable {E : Type u} {Y : Type v} recall composite_model_objective

Proposition 12.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 12.1 is source-facing: it isolates the strong-duality equality from the stronger Chapter 12 owner theorem dual_based_proximal_gradient_strong_duality_with_dual_attainment. The equality companion itself is now owned by Theorem_12_2, so this file reuses that canonical chapter theorem directly rather than keeping a parallel local projection wrapper.

recall dual_based_proximal_gradient_problem_strong_duality

Definition 12.1.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 12.1.1: Assumption 12.1 means that f : E → (-∞, ∞] is proper, closed, and σ-strongly convex for a positive parameter σ : PosReal; g : V → (-∞, ∞] is proper, closed, and convex; A : E →ₗ[ℝ] V is linear; and the relative interiors of dom f and dom g satisfy the qualification ri (dom f) ∩ A⁻¹' (ri (dom g)) ≠ ∅, equivalently there exist x̂ ∈ ri(dom f) and ẑ ∈ ri(dom g) with A x̂ = ẑ.

universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [AddCommGroup V] [Module ℝ V] [TopologicalSpace V] class IsDualBasedProximalGradientProblem (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) (σ : PosReal) : Prop extends IsProperExtendedRealFunction f where f_closed : LowerSemicontinuous f f_strongly_convex : StrongConvexOn (effective_domain f) (σ : ℝ) (fun x ↦ (f x).toReal) g_proper : IsProperExtendedRealFunction g g_closed : LowerSemicontinuous g g_convex : is_convex_function g qualification : (intrinsicInterior ℝ (effective_domain f) ∩ A ⁻¹' intrinsicInterior ℝ (effective_domain g)).Nonempty

Algorithm 12.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 12.2: given an initialization y⁰ = y0 and an admissible constant stepsize parameter L, a pair of sequences (x^k, y^k) follows the dual proximal-gradient method in primal representation when every iterate satisfies step (a) x^k ∈ argmax_x {⟪x, Aᵀ y^k⟫ - f(x)} and step (b) y^(k+1) = y^k - (1 / L) A x^k + (1 / L) prox_{L g}(A x^k - L y^k), recorded here through the canonical set-valued owners for the argmax and proximal update.

universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] class is_dual_proximal_gradient_primal_trajectory (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) {σ : PosReal} (L : DualBasedProximalGradientDualStepsizeParameter A.toContinuousLinearMap σ) (y0 : V) (x : ℕ → E) (y : ℕ → V) : Prop where /-- The dual sequence starts from the prescribed initialization `y⁰ = y0`. -/ zero : y 0 = y0 /-- At each iteration `k`, the primal point lies in the argmax set. -/ primal_step (k : ℕ) : x k ∈ dual_proximal_gradient_primal_x_argmax f A (y k) /-- At each iteration `k`, the next dual point lies in the corresponding Chapter 12 proximal update set. -/ dual_step (k : ℕ) : y (k + 1) ∈ dual_proximal_gradient_primal_y_step g A (x k) (y k) L

Definition 12.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 12.2 is bridge/view: it rewrites the Chapter 12 primal objective into a split optimization problem on pairs (x, z) constrained by z = A x. Domain sampling identifies the owner abstractions already present upstream: - source-facing: the split reformulation of the primal infimum; - core/canonical: Chapter 10's composite_model_objective for pointwise sums, Chapter 12's dual_based_proximal_gradient_primal_optimal_value for the primal infimum, and mathlib's Set.graphOn for the graph constraint; - bridge/view: restricting the canonical product objective composite_model_objective (f ∘ Prod.fst) (g ∘ Prod.snd) to univ.graphOn A, which recovers the canonical primal objective composite_model_objective f (g ∘ A). Primitive data are only the summands f, g, and the map A; the product-space objective and feasible set should therefore be thin specializations of those owners rather than bespoke wrapper definitions.

universe u v open Set variable {E : Type u} {Y : Type v} recall composite_model_objective

Theorem 12.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 12.2 (1): under Assumption 12.1, the primal optimal value of min_x {f x + g (A x)} equals the optimal value of the Chapter 12 Lagrange dual problem max_y {-f*(Aᵀ y) - g*(-y)}.

universe u v open Set open InnerProductSpace (toDual toDualMap) variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] theorem dual_based_proximal_gradient_problem_strong_duality (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) (σ : PosReal) (h_problem : IsDualBasedProximalGradientProblem f g A σ) : dual_based_proximal_gradient_primal_optimal_value f g A = dual_based_proximal_gradient_lagrange_dual_problem_value f g A

Algorithm 12.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 12.3: the sequences (y^k, w^k, t_k) follow the fast dual proximal-gradient method in dual representation when L is an admissible constant stepsize parameter, the initial conditions are y⁰ = w⁰ = y0, each y^(k+1) lies in the Chapter 12 dual proximal step set based at w^k, the acceleration scalars are the canonical values t_k = fista_momentum_sequence k, and the textbook extrapolation step w^(k+1) = y^(k+1) + (((t_k - 1) / t_(k+1)) • (y^(k+1) - y^k)) is recorded directly by the momentum field.

universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [NormedAddCommGroup V] [NormedSpace ℝ V] structure IsFastDualProximalGradientDualTrajectory (A : E →L[ℝ] V) (σ : PosReal) (G : V → EReal) (gradF : V → V) (L : DualBasedProximalGradientDualStepsizeParameter A σ) (y0 : V) (y w : ℕ → V) : Prop where /-- The initial dual iterate is the prescribed point `y0`. -/ y_zero : y 0 = y0 /-- The extrapolated sequence starts from the same prescribed point `y0`. -/ w_zero : w 0 = y0 /-- At each step, the next dual iterate lies in the Chapter 12 dual proximal update set based at `w^k`. -/ dual_step (k : ℕ) : y (k + 1) ∈ dual_based_proximal_gradient_dual_step G gradF L (w k) /-- For every `k`, the extrapolated iterate satisfies the literal textbook momentum recursion. -/ momentum_step (k : ℕ) : w (k + 1) = y (k + 1) + ((fista_momentum_sequence k - 1) / fista_momentum_sequence (k + 1)) • (y (k + 1) - y k)

Definition 12.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 12.3: the Lagrangian for the split model min_{x,z} f x + g z with constraint A x - z = 0 and dual variable y ∈ Y* is L(x, z; y) = f x + g z - ⟪y, A x - z⟫, expressed using the canonical dual evaluation pairing.

universe u v variable {E : Type u} {Y : Type v} variable [AddCommMonoid E] [Module ℝ E] variable [AddCommGroup Y] [Module ℝ Y] def dual_based_proximal_gradient_lagrangian (f : E → EReal) (g : Y → EReal) (A : E →ₗ[ℝ] Y) (x : E) (z : Y) (y : Module.Dual ℝ Y) : EReal := composite_model_objective (f ∘ Prod.fst) (g ∘ Prod.snd) (x, z) - (y (A x - z) : EReal) -- Proof sketch: unfold `dual_based_proximal_gradient_lagrangian`; the displayed formula is exactly -- the defining split objective minus the equality-constraint pairing.

Lemma 12.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 12.3: if f is proper, closed, and σ-strongly convex, then its primal conjugate is globally smooth with constant 1 / σ. This is the identity-map core used to prove the Chapter 12 smoothness statement for F(y) = f*(Aᵀ y).

universe u v open InnerProductSpace (toDualMap) variable {E : Type u} {Y : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [FiniteDimensional ℝ Y] theorem conjugate_function_primal_is_l_smooth_on_of_proper_closed_strongConvexOn (σ : PosReal) (f : E → EReal) (hf_proper : IsProperExtendedRealFunction f) (hf_closed : LowerSemicontinuous f) (hf_strong : StrongConvexOn (effective_domain f) (σ : ℝ) (fun x ↦ (f x).toReal)) : is_l_smooth_on (fun x : E ↦ ((f∗) x).toReal) Set.univ (Real.toNNReal (1 / (σ : ℝ)))

Algorithm 12.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 12.4: a quadruple of sequences (u^k, y^k, w^k, t_k) follows the fast dual proximal-gradient method in primal representation when L is an admissible constant stepsize parameter, equivalently (L : ℝ) ≥ ‖A‖² / σ, the initial conditions are w^0 = y^0 = y0 and t_0 = 1, each u^k maximizes u ↦ ⟪u, Aᵀ w^k⟫ - f(u), each y^(k+1) is obtained from the primal proximal step at w^k, the scalar sequence satisfies t_(k+1) = (1 + sqrt (1 + 4 t_k^2)) / 2, and the momentum update is w^(k+1) = y^(k+1) + ((t_k - 1) / t_(k+1)) (y^(k+1) - y^k).

universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] class IsFastDualProximalGradientPrimalTrajectory (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) (σ : PosReal) (L : DualBasedProximalGradientDualStepsizeParameter A.toContinuousLinearMap σ) (y0 : V) (u : ℕ → E) (y w : ℕ → V) (t : ℕ → ℝ) : Prop where /-- The initial dual iterate is the prescribed point `y0`. -/ y_zero : y 0 = y0 /-- The extrapolated sequence starts from the same prescribed point `y0`. -/ w_zero : w 0 = y0 /-- The acceleration parameter is initialized by `t_0 = 1`. -/ t_zero : t 0 = 1 /-- At each step, `u^k` is a maximizer of `u ↦ ⟪u, Aᵀ w^k⟫ - f(u)`. -/ primal_step (k : ℕ) : u k ∈ dual_proximal_gradient_primal_x_argmax f A (w k) /-- At each step, `y^(k+1)` lies in the Chapter 12 primal proximal update set based at `w^k`. -/ dual_step (k : ℕ) : y (k + 1) ∈ dual_proximal_gradient_primal_y_step g A (u k) (w k) L /-- The acceleration scalars satisfy the Chapter 10 FISTA momentum recursion. -/ acceleration_step (k : ℕ) : t (k + 1) = fista_momentum_update (t k) /-- For every `k`, the extrapolated iterate satisfies the source momentum recursion. -/ momentum_step (k : ℕ) : w (k + 1) = y (k + 1) + ((t k - 1) / t (k + 1)) • (y (k + 1) - y k)

Definition 12.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 12.4: for proper extended-real-valued f and g, minimizing the Definition 12.3 Lagrangian over (x, z) yields the dual objective q(y). This is the Chapter 12 analogue of the Chapter 4 split Fenchel identity q(y) = inf_{x,z} L(x, z; y).

universe u v variable {E : Type u} {Y : Type v} variable [AddCommGroup E] [Module ℝ E] variable [AddCommGroup Y] [Module ℝ Y] theorem dual_based_proximal_gradient_lagrange_dual_objective_eq_sInf_lagrangian_formula (f : E → EReal) (g : Y → EReal) (A : E →ₗ[ℝ] Y) (y : Module.Dual ℝ Y) (hf_proper : IsProperExtendedRealFunction f) (hg_proper : IsProperExtendedRealFunction g) : dual_based_proximal_gradient_lagrange_dual_objective f g A y = sInf (Set.range fun xz : E × Y ↦ dual_based_proximal_gradient_lagrangian f g A xz.1 xz.2 y)

Proposition 12.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

Proposition 12.4 (1): evaluating the Chapter 12 denoising objective with the two-dimensional TV operator A[m, n] gives the main-model form x ↦ (1 / 2) ‖x - d‖_F^2 + λ g (A x). Choosing g to be the isotropic or anisotropic regularizer below gives the two textbook TV denoising models.

open scoped BigOperators Matrix Matrix.Norms.Frobenius open TwoDimensionalTV WithLp variable {m n : ℕ} notation:max "A[" m "," n "]" => (show MatrixSpace m n →ₗ[ℝ] DualSpace m n from two_dimensional_total_variation_difference) notation:max "Aᵀ[" m "," n "]" => (A[m, n]).adjoint theorem two_dimensional_total_variation_denoising_problem_objective_apply (g : DualSpace m n → ℝ) (d : MatrixSpace m n) (lam : ℝ) (x : MatrixSpace m n) : denoising_problem_objective d (fun z : DualSpace m n ↦ ↑(lam * g z)) A[m, n] x = ((‖x - d‖ ^ (2 : ℕ) / 2 : ℝ) : EReal) + ↑(lam * g (A[m, n] x))

Theorem 12.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

Theorem 12.4: if the Chapter 12 dual split terms satisfy the primitive proper/convex and strong-convexity hypotheses needed for the Chapter 10 convex proximal-gradient rate theorem, then every positive dual proximal-gradient iterate satisfies qOpt - q(y^k) ≤ L ‖y^0 - y^*‖^2 / (2 k) for any optimal dual solution y^*, where q(y) = -f*(Aᵀ y) - g*(-y).

open scoped Gradient open InnerProductSpace (toDualMap) universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] variable (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) -- Local declaration justification (source-local notation): the Chapter 12 split dual terms and -- objective appear in every theorem statement in this file, and the notation only abbreviates -- existing canonical owners instead of introducing a parallel public API. local notation "F" => fun z : V ↦ dual_based_proximal_gradient_dual_F_term f A (toDualMap ℝ V z) local notation "G" => fun z : V ↦ dual_based_proximal_gradient_dual_G_term g (toDualMap ℝ V z) local notation "q" => dual_based_proximal_gradient_lagrange_dual_objective_primal f g A local notation "qOpt" => dual_based_proximal_gradient_lagrange_dual_problem_value f g A theorem dual_based_proximal_gradient_dual_objective_gap_le (σ : PosReal) (hf_proper : IsProperExtendedRealFunction f) (hf_closed : LowerSemicontinuous f) (hf_strong : StrongConvexOn (effective_domain f) (σ : ℝ) (fun x ↦ (f x).toReal)) (hg_proper : IsProperExtendedRealFunction g) (hg_convex : is_convex_function g) (L : DualBasedProximalGradientDualStepsizeParameter A.toContinuousLinearMap σ) (y : ℕ → V) (y0 yStar : V) (htraj : is_dual_based_proximal_gradient_dual_trajectory F G L y y0) (hyStar : q yStar = qOpt) (k : ℕ) (hk : 1 ≤ k) : qOpt - q (y k) ≤ (((L : ℝ) * ‖y0 - yStar‖ ^ (2 : ℕ) / (2 * (k : ℝ)) : ℝ) : EReal)

Algorithm 12.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 12.5: given A, b, d, an admissible constant parameter L ≥ ‖A‖₂,₂², and an initial dual point y⁰ = y0, the polyhedral projection DPG method generates the dual iterates y^k by recursively applying the shared primal-point and dual-update formulas.

open WithLp (toLp) variable {n p : ℕ} open EuclideanSpace (upperBoxClamp) def polyhedral_projection_dpg_dual_iterates (A : Matrix (Fin p) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin p)) (d : EuclideanSpace ℝ (Fin n)) (L : PolyhedralProjectionStepsizeParameter A) (y0 : EuclideanSpace ℝ (Fin p)) : ℕ → EuclideanSpace ℝ (Fin p)

Definition 12.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 12.5: the dual minimization objective in textbook split form is the Chapter 10 owner composite_model_objective applied to the Chapter 12 dual terms F and G.

universe u v variable {E : Type u} {Y : Type v} variable [AddCommGroup E] [Module ℝ E] variable [AddCommGroup Y] [Module ℝ Y] recall composite_model_objective

Lemma 12.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 12.5: the shifted dual proximal-gradient step for F(y) = f∗(A.adjoint y + b) and G(y) = g∗(-y) is equivalent to the primal-representation y-step at the canonical point xTilde = ∇ (fun x ↦ (((f∗) x).toReal)) (A.adjoint v + b), which is the source argmax point for x ↦ ⟪x, A.adjoint v + b⟫ - f x.

open scoped Gradient universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] theorem dual_based_proximal_gradient_dual_step_iff_mem_dual_proximal_gradient_primal_y_step (σ : PosReal) (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) (b : E) (hf_proper : IsProperExtendedRealFunction f) (hf_closed : LowerSemicontinuous f) (hf_strong : StrongConvexOn (effective_domain f) (σ : ℝ) (fun x ↦ (f x).toReal)) (hg_proper : IsProperExtendedRealFunction g) (hg_closed : LowerSemicontinuous g) (hg_convex : is_convex_function g) (y v : V) (L : PosReal) : y ∈ dual_based_proximal_gradient_dual_step (fun z : V ↦ (g∗) (-z)) (fun w ↦ ∇ (fun z : V ↦ (((f∗) (A.adjoint z + b)).toReal)) w) L v ↔ y ∈ dual_proximal_gradient_primal_y_step g A (∇ (fun x : E ↦ (((f∗) x).toReal)) (A.adjoint v + b)) v L

Proposition 12.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

Proposition 12.5: the Hilbert adjoint Aᵀ[m, n] of the two-dimensional TV operator A[m, n] has the divergence-style coordinate formula with zero-extended boundary terms.

open scoped BigOperators Matrix Matrix.Norms.Frobenius open Matrix TwoDimensionalTV WithLp variable (m n : ℕ) @[simp] theorem two_dimensional_total_variation_difference_adjoint_apply (z : DualSpace m n) (i : Fin m) (j : Fin n) : Aᵀ[m, n] z i j = (if h : j.1 < n - 1 then z.fst i ⟨j.1, h⟩ else 0) + (if h : i.1 < m - 1 then z.snd ⟨i.1, h⟩ j else 0) - (if h : 0 < j.1 then z.fst i ⟨j.1 - 1, by omega⟩ else 0) - (if h : 0 < i.1 then z.snd ⟨i.1 - 1, by omega⟩ j else 0)

Algorithm 12.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

Algorithm 12.6: for the projection problem min_x {(1 / 2) ‖x - d‖^2 : A x ≤ b}, given an admissible constant parameter L ≥ ‖A‖₂,₂² and an initial point y⁰ = w⁰ = y0, the recursive families below generate the FDPG iterates with step-(a) auxiliary point u^k = Aᵀ w^k + d, step-(b) update y^(k+1) = w^k - (1 / L) A u^k + (1 / L) min {A u^k - L w^k, b}, step-(c) momentum recursion t_(k+1) = (1 + √(1 + 4 t_k^2)) / 2, and step-(d) extrapolation w^(k+1) = y^(k+1) + ((t_k - 1) / t_(k+1)) (y^(k+1) - y^k). The public API keeps this direct source-facing recursion and also provides the convenient corollaries w¹ = y¹ and w^(k+2) = y^(k+2) + ((t_(k+1) - 1) / t_(k+2)) (y^(k+2) - y^(k+1)).

open Matrix variable {n p : ℕ} def polyhedral_projection_fdpg_y (A : Matrix (Fin p) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin p)) (d : EuclideanSpace ℝ (Fin n)) (L : PolyhedralProjectionStepsizeParameter A) (y0 : EuclideanSpace ℝ (Fin p)) : ℕ → EuclideanSpace ℝ (Fin p) := fun k ↦ (polyhedral_projection_fdpg_state A b d L y0 k).yCur

Proposition 12.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

Proposition 12.6: the discrete horizontal-vertical first-difference operator A on ℝ^(m × n) satisfies the operator-norm bound ‖A‖² ≤ 8.

open scoped BigOperators Matrix variable {m n : ℕ} local notation "Mmn" => Matrix (Fin m) (Fin n) ℝ local notation "Hmn" => Matrix (Fin m) (Fin (n - 1)) ℝ local notation "Vmn" => Matrix (Fin (m - 1)) (Fin n) ℝ local notation "TVSpace" => WithLp 2 (Hmn × Vmn) theorem two_dimensional_total_variation_difference_opNorm_sq_le_eight : ‖(A[m, n]).toContinuousLinearMap‖ ^ (2 : ℕ) ≤ 8

Algorithm 12.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

Algorithm 12.7: for a finite family of nonempty closed convex sets C₁, …, C_p, a point d, an admissible constant parameter L ≥ p, and an initialization y⁰ ∈ E^p, the dual projection-gradient method generates dual iterates by y_i^(k+1) = y_i^k - (1 / L) x^k + (1 / L) P_{C_i}(x^k - L y_i^k), where x^k = ∑ i, y_i^k + d.

open scoped BigOperators universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {p : ℕ} def finite_intersection_dual_projection_gradient_method (C : Fin p → Set E) (hC_nonempty : ∀ i, (C i).Nonempty) (hC_closed : ∀ i, IsClosed (C i)) (hC_convex : ∀ i, Convex ℝ (C i)) (L : DualBasedProximalGradientDualStepsizeParameter (dual_block_duplication E p) 1) (d : E) (y0 : Fin p → E) : ℕ → Fin p → E

Lemma 12.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 12.7: under Assumption 12.1, if xBar belongs to the primal argmax set argmax_x {⟪x, Aᵀ yBar⟫ - f x}, then for every primal optimizer xStar the canonical Chapter 12 dual gap at yBar dominates (σ / 2) ‖xBar - xStar‖². This is the owner-level form of the textbook inequality ‖xBar - xStar‖² ≤ (2 / σ) (q_opt - q(yBar)), stated directly with dual_based_proximal_gradient_lagrange_dual_objective_primal.

universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] variable (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) local notation "q" => dual_based_proximal_gradient_lagrange_dual_objective_primal f g A local notation "qOpt" => dual_based_proximal_gradient_lagrange_dual_problem_value f g A -- Proof sketch: apply the strong-convexity growth bound from Theorem 5.25 to the shifted function -- `x ↦ f x - ⟪x, Aᵀ yBar⟫`, whose minimizers are exactly the points in -- `dual_proximal_gradient_primal_x_argmax f A yBar`. Then compare the resulting Lagrangian value at -- `(xStar, A xStar)` with the canonical primal-space dual objective value at `yBar`, use strong -- duality from Theorem 12.2 to identify the primal optimum with the dual optimal value, and -- rearrange to the displayed dual-gap bound. theorem half_sigma_sqdist_le_dual_gap_of_primal_argmax (σ : PosReal) (h_problem : IsDualBasedProximalGradientProblem f g A σ) (yBar : V) (xBar xStar : E) (hxBar : xBar ∈ dual_proximal_gradient_primal_x_argmax f A yBar) (hxStar : IsMinOn (composite_model_objective f (g ∘ A)) Set.univ xStar) : ((((σ : ℝ) / 2) * ‖xBar - xStar‖ ^ (2 : ℕ) : ℝ) : EReal) ≤ qOpt - q yBar

Proposition 12.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

Proposition 12.7 (1): the diagonal duplication operator 𝒜(z) = (z, …, z) satisfies ‖𝒜‖² = p.

open scoped BigOperators universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [Nontrivial E] recall dual_block_duplication_opNorm_sq

Algorithm 12.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

Algorithm 12.8: for nonempty closed convex sets C₁, …, C_p, an admissible constant parameter L ≥ p, a point d ∈ E, and an initialization w⁰ = y⁰ = y0 ∈ E^p, the iterate families below generate the finite-intersection FDPG recursion with u^k = ∑ᵢ wᵢ^k + d, yᵢ^(k+1) = wᵢ^k - (1 / L) u^k + (1 / L) P_{Cᵢ}(u^k - L wᵢ^k), t_(k+1) = (1 + √(1 + 4 t_k^2)) / 2, and the source momentum clause is exposed in the equivalent public form w¹ = y¹ and w^(k+2) = y^(k+2) + (((t_(k+1) - 1) / t_(k+2)) • (y^(k+2) - y^(k+1))).

universe u open scoped BigOperators variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {p : ℕ} variable (C : Fin p → Set E) (hC_nonempty : ∀ i, (C i).Nonempty) variable (hC_closed : ∀ i, IsClosed (C i)) (hC_convex : ∀ i, Convex ℝ (C i)) variable (L : DualBasedProximalGradientDualStepsizeParameter (dual_block_duplication E p) 1) variable (d : E) (y0 : Fin p → E) def finite_intersection_fdpg_y : ℕ → Fin p → E := fun k ↦ (finite_intersection_fdpg_state C hC_nonempty hC_closed hC_convex L d y0 k).yCur

Definition 12.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

Definition 12.8. The polyhedral feasible set S = {x ∈ ℝ^n | A x ≤ b} associated to the matrix inequality system A x ≤ b.

variable {n p : ℕ} def polyhedral_projection_feasible_set (A : Matrix (Fin p) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin p)) : Set (EuclideanSpace ℝ (Fin n)) := inequality_feasible_set (fun i x ↦ A.toEuclideanLin x i - b i)

Proposition 12.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

Proposition 12.8: for the diagonal duplication operator 𝒜(z) = (z, …, z), the FDPG parameter from Algorithm 12.1 satisfies L = ‖𝒜‖² / σ = p / σ.

#check dual_block_duplication_fdpg_lipschitz_constant_eq

Theorem 12.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 12.8: under Assumption 12.1, if (x^k, y^k) is generated by the dual proximal gradient method with an admissible constant parameter L, then for every primal optimal solution x*, every dual optimal solution y*, and every k ≥ 1, the primal iterate satisfies the sublinear estimate ‖x^k - x*‖² ≤ L ‖y^0 - y*‖² / (σ k).

universe u v open scoped Gradient open InnerProductSpace (toDualMap) variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] variable (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) local notation "F" => fun z : V ↦ dual_based_proximal_gradient_dual_F_term f A (toDualMap ℝ V z) local notation "G" => fun z : V ↦ dual_based_proximal_gradient_dual_G_term g (toDualMap ℝ V z) local notation "pOpt" => dual_based_proximal_gradient_primal_optimal_value f g A local notation "q" => dual_based_proximal_gradient_lagrange_dual_objective_primal f g A local notation "qOpt" => dual_based_proximal_gradient_lagrange_dual_problem_value f g A theorem dual_proximal_gradient_primal_sequence_sqdist_le (σ : PosReal) (L : DualBasedProximalGradientDualStepsizeParameter A.toContinuousLinearMap σ) (h_problem : IsDualBasedProximalGradientProblem f g A σ) (y0 : V) (x : ℕ → E) (y : ℕ → V) (htraj : is_dual_proximal_gradient_primal_trajectory f g A L y0 x y) (xStar : E) (hxStar : IsMinOn (composite_model_objective f (g ∘ A)) Set.univ xStar) (yStar : V) (hyStar : q yStar = qOpt) (k : ℕ) (hk : 1 ≤ k) : ‖x k - xStar‖ ^ (2 : ℕ) ≤ (L : ℝ) * ‖y0 - yStar‖ ^ (2 : ℕ) / ((σ : ℝ) * (k : ℝ))

Algorithm 12.9

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 12.9: the second-version FDPG dual sequence specialized to the row halfspaces C_i = {x | ⟪a_i, x⟫ ≤ b_i} of A x ≤ b, with explicit rowwise nonemptiness input, admissible constant parameter L ≥ p, and initialization w⁰ = y⁰ = y0 ∈ (ℝ^n)^p.

open scoped BigOperators open WithLp (toLp) variable {n p : ℕ} def polyhedral_projection_second_fdpg_y (A : Matrix (Fin p) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin p)) (hC_nonempty : ∀ i, (polyhedral_projection_halfspace A b i).Nonempty) (d : EuclideanSpace ℝ (Fin n)) (L : DualBasedProximalGradientDualStepsizeParameter (dual_block_duplication (EuclideanSpace ℝ (Fin n)) p) 1) (y0 : Fin p → EuclideanSpace ℝ (Fin n)) : ℕ → Fin p → EuclideanSpace ℝ (Fin n)

Definition 12.9

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 12.9: for S = ⋂ i, C i, once the total intersection is known to be nonempty, closed, and convex, its orthogonal projection is the canonical point projection projectionPoint onto S, equivalently the optimal solution of min_x {(1 / 2) ‖x - d‖^2 : x ∈ S}.

universe u variable {ι : Sort*} variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (C : ι → Set E) (hC_nonempty : (⋂ i, C i).Nonempty) variable (hC_closed : ∀ i, IsClosed (C i)) (hC_convex : ∀ i, Convex ℝ (C i)) local notation "S" => ⋂ i, C i local notation "hS_closed" => isClosed_iInter hC_closed local notation "hS_convex" => convex_iInter hC_convex local notation "P" => projectionPoint S hC_nonempty hS_closed hS_convex #check (P : E → E)

Proposition 12.9

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 12.9: for the Chapter 12 denoising objective with identity forward map, the step-(a) argmax set is exactly the proximal set prox[g1] (d + w).

universe u open scoped RealInnerProductSpace variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] theorem dual_proximal_gradient_primal_x_argmax_denoising_problem_objective_eq_prox (g1 : E → EReal) (d w : E) : dual_proximal_gradient_primal_x_argmax (denoising_problem_objective d g1 id) (LinearMap.id : E →ₗ[ℝ] E) w = prox[g1] (d + w)

Theorem 12.9

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 12.9: under Assumption 12.1, if (u k, y k, w k, t k) is generated by the fast dual proximal-gradient method with constant parameter L, then every iterate with 1 ≤ k satisfies qOpt - q (y k) ≤ 2 L ‖y0 - yStar‖^2 / (k + 1)^2 for every optimal dual point yStar.

universe u v open scoped Gradient open InnerProductSpace (toDualMap) variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] variable (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) -- Local declaration justification (source-local notation): the Chapter 12 split dual terms and -- dual objective appear verbatim in every public statement in this file, and keeping the notation -- file-local avoids introducing one-off public aliases for these already canonical owners. local notation "F" => fun z : V ↦ dual_based_proximal_gradient_dual_F_term f A (toDualMap ℝ V z) local notation "G" => fun z : V ↦ dual_based_proximal_gradient_dual_G_term g (toDualMap ℝ V z) local notation "gradF" => fun z : V ↦ ∇ (fun z' : V ↦ EReal.toReal (F z')) z local notation "q" => dual_based_proximal_gradient_lagrange_dual_objective_primal f g A local notation "qOpt" => dual_based_proximal_gradient_lagrange_dual_problem_value f g A theorem fast_dual_proximal_gradient_dual_objective_gap_le (σ : PosReal) (L : DualBasedProximalGradientDualStepsizeParameter A.toContinuousLinearMap σ) (h_problem : IsDualBasedProximalGradientProblem f g A σ) (y0 : V) (u : ℕ → E) (y w : ℕ → V) (t : ℕ → ℝ) (htraj : IsFastDualProximalGradientPrimalTrajectory f g A σ L y0 u y w t) (yStar : V) (hyStar : q yStar = qOpt) (k : ℕ) (hk : 1 ≤ k) : qOpt - q (y k) ≤ ((2 * (L : ℝ) * ‖y0 - yStar‖ ^ (2 : ℕ) / ((k + 1 : ℝ) ^ (2 : ℕ)) : ℝ) : EReal)

Algorithm 12.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

Algorithm 12.10: for the one-dimensional total variation denoising problem min_x {(1 / 2) ‖x - d‖₂² + λ ‖D x‖₁}, with signal length n, positive regularization parameter λ encoded by lam : PosReal, and an initial dual point y⁰ ∈ ℝ^(n-1), this recursive sequence generates the DPG dual iterates by x^k = Dᵀ y^k + d and y^(k+1) = y^k - (1 / 4) D x^k + (1 / 4) T_[4 λ](D x^k - 4 y^k).

open scoped SoftThreshold variable (n : ℕ) (d : EuclideanSpace ℝ (Fin n)) (lam : PosReal) variable (y0 : EuclideanSpace ℝ (Fin (n - 1))) def one_dimensional_total_variation_dpg : ℕ → EuclideanSpace ℝ (Fin (n - 1))

Definition 12.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

Definition 12.10: the denoising problem objective is x ↦ (1 / 2) ‖x - d‖^2 + R (A x), realized as the Chapter 10 composite objective with quadratic data-fidelity term and regularizer R composed with the map A.

universe u v variable {E : Type u} {Y : Type v} variable [NormedAddCommGroup E] recall composite_model_objective

Proposition 12.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

Proposition 12.10 (1) in the Chapter 6 soft-thresholding form: for λ > 0, the proximal mapping of (u, v) ↦ λ |u - v| at (y, z) is the singleton given by the rank-one soft-thresholding correction along (λ, -λ).

open WithLp (toLp) open scoped RealInnerProductSpace local notation "E2" => EuclideanSpace ℝ (Fin 2) theorem prox_pair_difference_penalty_eq_singleton_soft_thresholding (lam y z : ℝ) (hlam : 0 < lam) : prox[pair_difference_penalty lam] (toLp 2 ![y, z]) = {(toLp 2 ![y, z]) + (((𝒯[2 * lam ^ 2] (lam * y - lam * z) - (lam * y - lam * z)) / (2 * lam ^ 2)) • (toLp 2 ![lam, -lam]))}

Theorem 12.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 12.10: if y^k is generated by the fast dual proximal-gradient method with L ≥ ‖A‖^2 / σ, and x^k is chosen from argmax_x {⟪x, Aᵀ y^k⟫ - f(x)} for each k, then every positive iterate satisfies the primal estimate ‖x^k - x*‖^2 ≤ 4 L ‖y^0 - y*‖^2 / (σ (k + 1)^2) for any primal optimizer x* and any optimal dual solution y*.

universe u v open scoped Gradient open InnerProductSpace (toDualMap) variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup V] [InnerProductSpace ℝ V] [FiniteDimensional ℝ V] variable (f : E → EReal) (g : V → EReal) (A : E →ₗ[ℝ] V) local notation "F" => fun z : V ↦ dual_based_proximal_gradient_dual_F_term f A (toDualMap ℝ V z) local notation "G" => fun z : V ↦ dual_based_proximal_gradient_dual_G_term g (toDualMap ℝ V z) local notation "gradF" => fun z : V ↦ ∇ (fun z' : V ↦ EReal.toReal (F z')) z local notation "q" => dual_based_proximal_gradient_lagrange_dual_objective_primal f g A local notation "qOpt" => dual_based_proximal_gradient_lagrange_dual_problem_value f g A theorem fast_dual_proximal_gradient_primal_sqdist_le (σ : PosReal) (L : DualBasedProximalGradientDualStepsizeParameter A.toContinuousLinearMap σ) (h_problem : IsDualBasedProximalGradientProblem f g A σ) (y0 : V) (u x : ℕ → E) (y w : ℕ → V) (t : ℕ → ℝ) (htraj : IsFastDualProximalGradientPrimalTrajectory f g A σ L y0 u y w t) (hx : ∀ k : ℕ, x k ∈ dual_proximal_gradient_primal_x_argmax f A (y k)) (xStar : E) (hxStar : IsMinOn (composite_model_objective f (g ∘ A)) Set.univ xStar) (yStar : V) (hyStar : q yStar = qOpt) (k : ℕ) (hk : 1 ≤ k) : ‖x k - xStar‖ ^ (2 : ℕ) ≤ 4 * (L : ℝ) * ‖y0 - yStar‖ ^ (2 : ℕ) / ((σ : ℝ) * ((k + 1 : ℝ) ^ (2 : ℕ)))

Algorithm 12.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

Algorithm 12.11: for the one-dimensional total variation denoising problem min_x { (1 / 2) ‖x - d‖_2^2 + λ ‖D x‖_1 }, with signal length n, positive regularization parameter λ encoded by lam : PosReal, and initialization w⁰ = y⁰ = y0 ∈ ℝ^(n-1), the iterate families below generate the FDPG recursion with u^k = Dᵀ w^k + d, y^(k+1) = w^k - (1 / 4) D u^k + (1 / 4) T_[4 λ] (D u^k - 4 w^k), t_(k+1) = (1 + √(1 + 4 t_k^2)) / 2, and w^(k+1) = y^(k+1) + ((t_k - 1) / t_(k+1)) (y^(k+1) - y^k).

variable (n : ℕ) def one_dimensional_total_variation_fdpg_y (d : EuclideanSpace ℝ (Fin n)) (lam : PosReal) (y0 : EuclideanSpace ℝ (Fin (n - 1))) : ℕ → EuclideanSpace ℝ (Fin (n - 1)) := fun k ↦ (one_dimensional_total_variation_fdpg_state n d lam y0 k).yCur

Definition 12.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

Definition 12.11 is a bridge/view recall: it introduces no new owner beyond the chapter's source-facing one-dimensional total-variation denoising objective. Domain sampling against the nearby chapter/project owners gives the following split: - source-facing: one_dimensional_total_variation_denoising_objective, - core/canonical: denoising_problem_objective, - derived API: one_dimensional_total_variation_denoising_objective_apply. Primitive data are only the datum d, the canonical one-dimensional TV operator, and the positive regularization parameter λ : PosReal, all already packaged by the source-facing owner in Definition 12.19. This file should therefore recall that owner directly rather than rebuild a lower-level specialization with a widened bare-real parameter.

recall one_dimensional_total_variation_denoising_objective

Proposition 12.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

Proposition 12.11: for the first split total-variation block g₁(x) = λ ∑ |x_(2 i) - x_(2 i + 1)|, realized on Fin n as the even-start adjacent pairs (0,1), (2,3), ..., the proximal mapping is the singleton containing the point obtained by the explicit pairwise correction formula on each such pair, for the chapter's positive parameter lam : PosReal.

open scoped BigOperators open EuclideanSpace open WithLp (toLp ofLp) variable {n : ℕ} local notation "En" => EuclideanSpace ℝ (Fin n) theorem prox_one_dimensional_total_variation_even_edge_penalty_eq_singleton (lam : PosReal) (x : En) : prox[one_dimensional_total_variation_even_edge_penalty lam] x = {one_dimensional_total_variation_even_edge_prox_point lam x}

Algorithm 12.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

Algorithm 12.12: at every iteration k, the extrapolated successor satisfies the textbook step-(d) update with the canonical FISTA momentum sequence.

open TwoDimensionalTV WithLp variable {m n : ℕ} theorem two_dimensional_tv_l1_fdpg_zExtrap_succ (d : MatrixSpace m n) (lam : PosReal) (p0 : HorizontalSpace m n) (q0 : VerticalSpace m n) (k : ℕ) : two_dimensional_tv_l1_fdpg_zExtrap d lam p0 q0 (k + 1) = two_dimensional_tv_l1_fdpg_z d lam p0 q0 (k + 1) + ((fista_momentum_sequence k - 1) / fista_momentum_sequence (k + 1)) • (two_dimensional_tv_l1_fdpg_z d lam p0 q0 (k + 1) - two_dimensional_tv_l1_fdpg_z d lam p0 q0 k)

Definition 12.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

Definition 12.12: the two-dimensional total variation denoising problem is the minimization of the Chapter 12 denoising objective specialized to the matrix space, the identity map, and a matrix-side regularizer.

open scoped Matrix Matrix.Norms.Frobenius variable {m n : ℕ} local notation "Mmn" => Matrix (Fin m) (Fin n) ℝ abbrev two_dimensional_total_variation_denoising_objective (TV : Mmn → ℝ) (d : Mmn) (lam : PosReal) : Mmn → EReal := denoising_problem_objective d (fun x ↦ ↑((lam : ℝ) * TV x)) id

Proposition 12.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

Proposition 12.12: for the split total-variation block g₂(x) = λ ∑ |x_(2 i + 1) - x_(2 i + 2)|, realized on Fin n as the odd-start adjacent pairs (1,2), (3,4), ..., the proximal mapping is the singleton containing the point obtained by the explicit pairwise shrinkage formula on each such pair, for the chapter's positive parameter lam : PosReal.

open scoped BigOperators variable {n : ℕ} local notation "En" => EuclideanSpace ℝ (Fin n) open EuclideanSpace open WithLp (toLp ofLp) theorem prox_one_dimensional_total_variation_odd_edge_penalty_eq_singleton (lam : PosReal) (x : En) : prox[one_dimensional_total_variation_odd_edge_penalty lam] x = {one_dimensional_total_variation_odd_edge_prox_point lam x}

Algorithm 12.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

Algorithm 12.13: any such trajectory canonically yields the Chapter 12.4 accelerated dual proximal-gradient primal trajectory for the finite-sum block Hilbert-product model, with nonsmooth term PiLp.separableSum g, duplication operator dual_block_duplication E p, and constant parameter p / σ.

universe u open scoped BigOperators variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {p : ℕ+} variable {f : E → EReal} {g : Fin p → E → EReal} {σ : PosReal} variable {y0 : Fin p → E} {u : ℕ → E} {y w : ℕ → Fin p → E} {t : ℕ → ℝ} theorem IsFastDualBlockProximalGradientPrimalTrajectory.toFastDualProximalGradientPrimalTrajectory (h : IsFastDualBlockProximalGradientPrimalTrajectory f g σ y0 u y w t) : IsFastDualProximalGradientPrimalTrajectory f (PiLp.separableSum g) (dual_block_duplication E p).toLinearMap σ (dual_block_proximal_gradient_stepsize_parameter E p σ) (WithLp.toLp 2 y0) u (fun k ↦ WithLp.toLp 2 (y k)) (fun k ↦ WithLp.toLp 2 (w k)) t

Definition 12.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 12.13 (1): the isotropic two-dimensional total variation of a real matrix is the finite sum of the isotropic site contributions over all pixels.

open scoped BigOperators open Matrix variable {rows cols : ℕ} local notation "Mmn" => Matrix (Fin rows) (Fin cols) ℝ local notation "PixelIndex" => Fin rows × Fin cols def isotropic_two_dimensional_total_variation (x : Mmn) : ℝ := ∑ ij : PixelIndex, isotropic_two_dimensional_total_variation_site_term x ij

Proposition 12.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

Proposition 12.13: for the fixed three-point-star matrix A, the proximal mapping of the scaled penalty λ h with h(z) = ‖A z‖₂ is the singleton {x - A† (A A†)⁻¹ A x} on the branch ‖(A A†)⁻¹ A x‖₂ ≤ λ. On the complementary branch λ < ‖(A A†)⁻¹ A x‖₂, the active-branch shift is the unique positive root α* of the decreasing scalar residual g(α) = ‖(A A† + α I)⁻¹ (A x)‖₂² - λ², and the proximal mapping is the singleton {x - A† (A A† + α* I)⁻¹ A x}. In this Euclidean model, A† is the transpose action Aᵀ.

open scoped InnerProduct local notation "E3" => EuclideanSpace ℝ (Fin 3) local notation "E2" => EuclideanSpace ℝ (Fin 2) local notation "A" => three_point_star_difference_operator local notation "AT" => LinearMap.toContinuousLinearMap (Matrix.toEuclideanLin three_point_star_difference_matrix.transpose) local notation "G" => three_point_star_difference_gram theorem prox_three_point_star_difference_penalty_eq_piecewise (x : E3) (lam : ℝ) (hlam : 0 < lam) : (‖(G).inverse (A x)‖ ≤ lam → prox[fun z : E3 ↦ ((lam : EReal) * three_point_star_difference_penalty z)] x = {x - (A†) ((G).inverse (A x))}) ∧ (∀ hlarge : lam < ‖(G).inverse (A x)‖, prox[fun z : E3 ↦ ((lam : EReal) * three_point_star_difference_penalty z)] x = {x - (A†) ((G + three_point_star_difference_active_shift x lam hlam hlarge • 1).inverse (A x))})

Algorithm 12.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

Algorithm 12.14: given an initialization y⁰ = y0 ∈ E^p, a positive parameter σ, and a block-choice sequence i_k ∈ {1, …, p}, a sequence y follows the dual block proximal-gradient method in dual representation when y 0 = y0 and every successor iterate updates only the chosen block i_k by a proximal step of σ G_(i_k) at y_(i_k)^k - σ ∇ f*(∑ j, y_j^k), with grad_f_conj representing ∇ f*.

universe u open scoped BigOperators variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class is_dual_block_proximal_gradient_dual_trajectory {p : ℕ} (G : Fin p → E → EReal) (grad_f_conj : E → E) (σ : PosReal) (block_choice : ℕ → Fin p) (y0 : Fin p → E) (y : ℕ → Fin p → E) : Prop where /-- The trajectory starts from the prescribed initialization `y⁰ = y0`. -/ zero : y 0 = y0 /-- At each iteration, the next block vector is obtained by the selected one-block dual proximal update. -/ step : ∀ k : ℕ, y (k + 1) ∈ dual_block_proximal_gradient_dual_step G grad_f_conj σ (block_choice k) (y k)

Definition 12.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 12.14: the dual block proximal-gradient primal objective is exactly the Chapter 10 composite objective specialized to the Chapter 8 finite-sum term.

universe u open scoped BigOperators variable {E : Type u} recall composite_model_objective

Theorem 12.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

Theorem 12.14 (1): for primal and dual sequences generated by the dual block proximal-gradient method with randomized uniformly sampled block order, if the sampled dual objective value is integrable and the relevant dual points lie in the finite domain of q, then the expected dual objective gap satisfies the sublinear estimate q_opt - E[q(y^{k+1})] ≤ (p / (p + k + 1)) ((1 / (2σ)) ‖y^0 - y*‖² + q_opt - q(y^0)).

universe u v open MeasureTheory ProbabilityTheory open scoped BigOperators ProbabilityTheory ENNReal Gradient variable {Ω : Type v} {E : Type u} {p : ℕ} variable [NeZero p] variable [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable (σ : PosReal) (f : E → EReal) (g : Fin p → E → EReal) variable (y0 : Fin p → E) variable (sampled_block : ℕ → Ω → Fin p) variable (x : ℕ → Ω → E) variable (y : ℕ → Ω → Fin p → E) local notation "F" => composite_model_objective f (finite_sum_objective g) variable (h_problem : IsDualBlockProximalGradientProblem f g σ) (h_traj : ∀ ω, is_dual_block_proximal_gradient_primal_trajectory f g σ (fun n ↦ sampled_block n ω) y0 (fun n ↦ x n ω) (fun n ↦ y n ω)) (h_sampled_block_meas : ∀ k, Measurable (sampled_block k)) (h_sampled_block_indep : iIndepFun sampled_block μ) (h_sampled_block_uniform : ∀ k (i : Fin p), μ ((sampled_block k) ⁻¹' {i}) = 1 / (p : ℝ≥0∞)) (yStar : Fin p → E) (hyStar : yStar ∈ Λ*(f, g)) (hy0_finite : y0 ∈ finite_domain (q(f, g))) (hyStar_finite : yStar ∈ finite_domain (q(f, g))) include sampled_block x h_problem h_traj h_sampled_block_meas h_sampled_block_indep h_sampled_block_uniform hyStar hy0_finite hyStar_finite theorem randomized_dual_block_proximal_gradient_expected_dual_gap_le (k : ℕ) (h_dual_value_finite : ∀ ω, y (k + 1) ω ∈ finite_domain (q(f, g))) (h_dual_value_integrable : Integrable (fun ω ↦ (q(f, g) (y (k + 1) ω)).toReal) μ) : EReal.toReal (q_opt(f, g)) - μ[fun ω ↦ (q(f, g) (y (k + 1) ω)).toReal] ≤ (p : ℝ) / (p + k + 1 : ℝ) * ((1 / (2 * (σ : ℝ))) * ‖y0 - yStar‖ ^ (2 : ℕ) + EReal.toReal (q_opt(f, g)) - (q(f, g) y0).toReal)

Algorithm 12.15

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 12.15: given an initialization y⁰ = y0 in the finite block family ι → E and a block-selection rule block : ℕ → ι, a pair of sequences (x^k, y^k) follows the dual block proximal-gradient method in primal representation when every iteration k satisfies x^k ∈ argmax_x {⟪x, ∑ j, y_j^k⟫ - f(x)} and the next block vector y^(k+1) is obtained by updating only the selected coordinate block k through the proximal rule y_i^k - σ x^k + σ prox_{g_i / σ}(x^k - y_i^k / σ).

open scoped BigOperators universe u variable {ι : Type*} [Fintype ι] variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] class is_dual_block_proximal_gradient_primal_trajectory (f : E → EReal) (g : ι → E → EReal) (σ : PosReal) (block : ℕ → ι) (y0 : ι → E) (x : ℕ → E) (y : ℕ → ι → E) : Prop where /-- The trajectory starts from the prescribed initialization `y⁰ = y0`. -/ zero : y 0 = y0 /-- At each iteration, the primal point lies in the aggregated argmax set and the next block vector is obtained by the selected one-block proximal update. -/ step : ∀ k : ℕ, x k ∈ dual_proximal_gradient_primal_x_argmax f LinearMap.id (∑ j, y k j) ∧ y (k + 1) ∈ dual_block_proximal_gradient_primal_y_step g σ (x k) (y k) (block k)

Definition 12.15

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 12.15: Assumption 12.14 for the dual block proximal-gradient model says that f : E → (-∞, ∞] is proper, closed, and σ-strongly convex for a positive parameter σ : PosReal; each gᵢ : E → (-∞, ∞] is proper, closed, and convex; and the qualification ri (dom f) ∩ ⋂ i, ri (dom gᵢ) ≠ ∅ holds.

universe u variable {E : Type u} variable [NormedAddCommGroup E] [NormedSpace ℝ E] class IsDualBlockProximalGradientProblem {p : ℕ} (f : E → EReal) (g : Fin p → E → EReal) (σ : PosReal) : Prop extends IsProperExtendedRealFunction f where f_closed : LowerSemicontinuous f f_strongly_convex : StrongConvexOn (effective_domain f) (σ : ℝ) (fun x ↦ (f x).toReal) g_proper (i : Fin p) : IsProperExtendedRealFunction (g i) g_closed (i : Fin p) : LowerSemicontinuous (g i) g_convex (i : Fin p) : is_convex_function (g i) qualification : (intrinsicInterior ℝ (effective_domain f) ∩ ⋂ i : Fin p, intrinsicInterior ℝ (effective_domain (g i))).Nonempty

Lemma 12.15

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 12.15: for the dual block proximal-gradient method, the Chapter 12 block dual update at block i is equivalent to the Chapter 12 block primal update at the canonical point xTilde = ∇ f^*(∑ j, v_j).

open scoped BigOperators Gradient universe u variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {p : ℕ} variable (f : E → EReal) (g : Fin p → E → EReal) (σ : PosReal) variable (hf_proper : IsProperExtendedRealFunction f) (hf_closed : LowerSemicontinuous f) variable (hf_strong : StrongConvexOn (effective_domain f) (σ : ℝ) (fun x ↦ (f x).toReal)) variable (hg_proper : ∀ j : Fin p, IsProperExtendedRealFunction (g j)) variable (hg_closed : ∀ j : Fin p, LowerSemicontinuous (g j)) variable (hg_convex : ∀ j : Fin p, is_convex_function (g j)) include hf_proper hf_closed hf_strong hg_proper hg_closed hg_convex theorem dual_block_proximal_gradient_dual_step_iff_mem_dual_block_proximal_gradient_primal_y_step (i : Fin p) (yNext v : Fin p → E) : yNext ∈ dual_block_proximal_gradient_dual_step (fun j z ↦ ((g j)∗) (-z)) (∇ fun z : E ↦ (((f∗) z).toReal)) σ i v ↔ yNext ∈ dual_block_proximal_gradient_primal_y_step g σ ((∇ fun z : E ↦ (((f∗) z).toReal)) (∑ j : Fin p, v j)) v i

Algorithm 12.16

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 12.16 is a bridge/view specialization rather than a new owner: the accelerated two-block method is exactly Algorithm 12.4 with A = id, primal term f + g₁, nonsmooth term g₂, and constant parameter σ⁻¹. Domain sampling against the surrounding chapter API identifies the canonical owners: - IsFastDualProximalGradientPrimalTrajectory from Algorithm 12.4 for the accelerated trajectory; - dual_proximal_gradient_primal_x_argmax and dual_proximal_gradient_primal_y_step from Algorithm 12.2 for the step-(a) and step-(b) set-valued updates; - fista_momentum_update from Algorithm 10.13 for the scalar recursion t_(k+1) = (1 + sqrt (1 + 4 t_k^2)) / 2; - dual_based_proximal_gradient_identity_stepsize_parameter from Algorithm 12.1 for the admissible identity-map stepsize. Primitive data are only the iterate families u, y, w, t together with the two-block split f, g₁, g₂. The step clauses and acceleration formulas are derived API from the Chapter 12.4 owner, so this file should reuse that owner directly instead of maintaining a parallel local trajectory class.

universe u variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall IsFastDualProximalGradientPrimalTrajectory

Definition 12.16

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 12.16: the finite-sum problem min_x {f x + ∑ i, g i x} fits the Chapter 12.1 composite model by taking V = E^p (implemented as Fin p → E), g(x₁, ..., x_p) = ∑ i, g i (x_i), and A z = (z, ..., z).

universe u open scoped BigOperators variable {E : Type u} recall composite_model_objective

Definition 12.17

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 12.17: the block dual objective q(y) = -f*(∑ i, y_i) - ∑ i, g_i*(-y_i) for the finite-sum dual block proximal-gradient model.

universe u open scoped BigOperators variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] def dual_block_proximal_gradient_dual_objective {p : ℕ} (f : E → EReal) (g : Fin p → E → EReal) : (Fin p → E) → EReal := fun y ↦ -((f∗) (∑ i : Fin p, y i)) - ∑ i : Fin p, ((g i)∗) (-y i)

Theorem 12.17

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 12.17 GPT-5.4 high proof-only provider diagnostic: for a cyclic DBPG trajectory and the Assumption 12.16 radius R = R(q(y⁰)), every sampled dual iterate y^(p k) with k ≥ 2 satisfies the textbook geometric-or-sublinear dual-gap bound DualBlockProximalGradient.cyclicGapBound.

universe u open DualBlockProximalGradient variable {E : Type u} {p : ℕ} variable [NeZero p] variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable (σ : PosReal) (f : E → EReal) (g : Fin p → E → EReal) variable [h_problem : IsDualBlockProximalGradientSuperlevelDistanceBoundedProblem f g σ] variable (y0 : PiLp 2 (fun _ : Fin p ↦ E)) (x : ℕ → E) variable (y : ℕ → PiLp 2 (fun _ : Fin p ↦ E)) variable (h_trajectory : is_dual_block_proximal_gradient_primal_trajectory f g σ (dual_block_proximal_gradient_cyclic_block_index p) y0.ofLp x (fun n ↦ (y n).ofLp)) variable (α0 : PosReal) (h_initial_level : q(f, g) y0.ofLp = (α0 : EReal)) variable (R : PosReal) (h_R : IsSuperlevelRadius f g α0 R) include h_problem h_trajectory h_initial_level h_R omit y0 x y h_problem h_trajectory α0 h_initial_level R h_R include y0 x y h_problem h_trajectory α0 h_initial_level R h_R theorem cyclic_dual_gap_le_max_geometric_or_sublinear (k : ℕ) (hk : 2 ≤ k) : (q_opt(f, g) - q(f, g) (y (p * k)).ofLp).toReal ≤ cyclicGapBound p σ R (q_opt(f, g) - q(f, g) y0.ofLp).toReal k

Definition 12.18

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 12.18 is source-facing: under Assumption 12.14, the block dual optimal set Λ* is nonempty and, for every α > 0, every dual point y with q(y) ≥ α lies within a uniformly bounded Euclidean product distance of every optimal dual solution y* ∈ Λ*, where q(y) = -f*(∑ i, y_i) - ∑ i, g_i*(-y_i). The stronger pairwise bound is primitive source data. The weaker canonical infDist y Λ* ≤ Rα reformulation is derived API below.

universe u open Metric open scoped BigOperators variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] class IsDualBlockProximalGradientSuperlevelDistanceBoundedProblem {p : ℕ} (f : E → EReal) (g : Fin p → E → EReal) (σ : PosReal) : Prop extends IsDualBlockProximalGradientProblem f g σ where dual_optimal_set_nonempty : (Λ*(f, g)).Nonempty bounded_dual_superlevel_distance_to_each_optimal_point (α : PosReal) : ∃ Rα : PosReal, DualBlockProximalGradient.IsSuperlevelRadius f g α Rα

Definition 12.19

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 12.19: for datum d ∈ ℝ^n and positive parameter λ, encoded by lam : PosReal, the one-dimensional total-variation denoising objective is F(x) = (1 / 2) ‖x - d‖_2^2 + λ * ∑_{i=1}^{n-1} |x_(i-1) - x_i|.

open scoped BigOperators variable {n : ℕ} local notation "En" => EuclideanSpace ℝ (Fin n) local notation "Em" => EuclideanSpace ℝ (Fin (n - 1)) notation:max "D[" n "]" => one_dimensional_total_variation_difference_operator n notation:max "Dᵀ[" n "]" => (show EuclideanSpace ℝ (Fin (n - 1)) →ₗ[ℝ] EuclideanSpace ℝ (Fin n) from (D[n]).adjoint) abbrev one_dimensional_total_variation_denoising_objective (d : En) (lam : PosReal) : En → EReal := denoising_problem_objective d (fun y : Em ↦ ↑((lam : ℝ) * ‖y‖₁)) D[n] -- Proof sketch: unfold -- `one_dimensional_total_variation_denoising_objective` through `denoising_problem_objective`, -- then expand the quadratic fidelity term from Definition 12.10.

Theorem 12.19

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 12.19: under Assumption 12.14 with two blocks, if the reduced accelerated dual-proximal-gradient trajectory represents the ADBPG iterates and x^k is chosen from argmax_x {⟪x, y^k⟫ - f(x) - g₁(x)} for each current dual iterate y^k, then for any optimal two-block dual solution y* = (y₁*, y₂*) ∈ Λ*(f, ![g₁, g₂]) and any associated reduced primal argmax point x* ∈ argmax_x {⟪x, y₂*⟫ - f(x) - g₁(x)}, every positive iterate satisfies ‖x^k - x*‖² ≤ 4 ‖y^0 - y₂*‖² / (σ² (k + 1)²).

universe u open scoped BigOperators open scoped Gradient variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable (σ : PosReal) (f g1 g2 : E → EReal) local notation "F" => composite_model_objective f g1 local notation "A" => (LinearMap.id : E →ₗ[ℝ] E) local notation "L" => (dual_based_proximal_gradient_identity_stepsize_parameter (E := E) σ : DualBasedProximalGradientDualStepsizeParameter (ContinuousLinearMap.id ℝ E) σ) local notation "pRed" => composite_model_objective F g2 local notation "qRed" => dual_based_proximal_gradient_lagrange_dual_objective_primal F g2 A local notation "qRedOpt" => dual_based_proximal_gradient_lagrange_dual_problem_value F g2 A local notation "FRedDual" => fun z : E ↦ dual_based_proximal_gradient_dual_F_term F A (InnerProductSpace.toDualMap ℝ E z) local notation "GRedDual" => fun z : E ↦ dual_based_proximal_gradient_dual_G_term g2 (InnerProductSpace.toDualMap ℝ E z) local notation "gradFRed" => fun z : E ↦ ∇ (fun z' : E ↦ EReal.toReal (FRedDual z')) z theorem accelerated_dual_block_proximal_gradient_primal_sqdist_le (h_problem : IsDualBlockProximalGradientProblem f ![g1, g2] σ) (y0 : E) (u x : ℕ → E) (y w : ℕ → E) (t : ℕ → ℝ) (htraj : IsFastDualProximalGradientPrimalTrajectory F g2 A σ L y0 u y w t) (hx : ∀ k : ℕ, x k ∈ dual_proximal_gradient_primal_x_argmax F A (y k)) (yStar : Fin 2 → E) (hyStar : yStar ∈ Λ*(f, ![g1, g2])) (xStar : E) (hxStar : xStar ∈ dual_proximal_gradient_primal_x_argmax F A (yStar 1)) (k : ℕ) (hk : 1 ≤ k) : ‖x k - xStar‖ ^ (2 : ℕ) ≤ 4 * ‖y0 - yStar 1‖ ^ (2 : ℕ) / (((σ : ℝ) ^ (2 : ℕ)) * ((k + 1 : ℝ) ^ (2 : ℕ)))

Definition 12.20

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 12.20 [Splitting of the one-dimensional total variation denoising objective]: the one-dimensional total-variation denoising objective is exactly the Chapter 12.14 two-block composite objective whose block family is given by the even-edge and odd-edge split penalties.

open scoped BigOperators variable {n : ℕ} local notation "En" => EuclideanSpace ℝ (Fin (n + 1)) local notation "G[" lam "]" => (![one_dimensional_total_variation_split_even_edge_penalty lam, one_dimensional_total_variation_split_odd_edge_penalty lam] : Fin 2 → En → EReal) theorem one_dimensional_total_variation_denoising_fits_dual_block_model (d : En) (lam : PosReal) : one_dimensional_total_variation_denoising_objective d lam = composite_model_objective (denoising_data_fidelity d) (finite_sum_objective G[lam])

Definition 12.21

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 12.21 is the direct specialization of the canonical Chapter 12.12 owner to the isotropic regularizer TV_I and the chapter's positive parameter type PosReal.

open scoped BigOperators Matrix.Norms.Frobenius variable {rows cols : ℕ} local notation "M" => Matrix (Fin rows) (Fin cols) ℝ recall two_dimensional_total_variation_denoising_objective

Definition 12.22

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 12.22: the diagonal component ψ_(i+1) of TV_I is the sum of the isotropic cell terms over all diagonals D_k whose offsets belong to the residue class K_(i+1).

open scoped BigOperators variable {m n : ℕ} local notation "PixelIndex" => Fin m × Fin n local notation "Mmn" => Matrix (Fin m) (Fin n) ℝ namespace IsotropicTwoDimensionalTotalVariation def isotropic_diagonal_component (m n : ℕ) (i : Fin 3) (x : Matrix (Fin m) (Fin n) ℝ) : ℝ := (K m n i).sum fun k ↦ (D m n k).sum fun ij ↦ isotropic_two_dimensional_total_variation_site_term x ij

Definition 12.23

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 12.23 is a bridge/view: Definition 12.21 already fixes the isotropic two-dimensional denoising objective, and Definition 12.22 already decomposes the isotropic regularizer TV_I into the three diagonal components ψ[i]. Domain sampling in the surrounding Chapter 12 API identifies: - core/canonical: two_dimensional_total_variation_denoising_objective from Definition 12.12; - source-facing: TV_I and the diagonal component family isotropic_diagonal_component; - core/canonical: denoising_data_fidelity, composite_model_objective, and finite_sum_objective; - bridge/view: the three-block family obtained by scaling the diagonal components by λ. Primitive data here are only the datum d, the positive parameter λ, and the diagonal component family from Definition 12.22. The public API should therefore be only the bridge from the existing isotropic denoising owner to the canonical Chapter 10/8 composite finite-sum owner layer, rather than a parallel local wrapper.

open scoped BigOperators Matrix.Norms.Frobenius variable {m n : ℕ} local notation "Mmn" => Matrix (Fin m) (Fin n) ℝ open IsotropicTwoDimensionalTotalVariation local instance instDefinition1223NormedAddCommGroupMatrix : NormedAddCommGroup Mmn

Definition 12.24

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 12.24: the three-variable penalty is the L² norm of the pair of differences from x to y and z.

open WithLp #check fun x y z : ℝ ↦ ‖toLp 2 (x - y, x - z)‖ -- Proof sketch: apply `WithLp.prod_norm_eq_of_L2` to the difference pair and simplify the real -- norms to absolute values, then square the absolutes back to plain squares.

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

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

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

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

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

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

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