Chapter 10 — The Proximal Gradient Method

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

Algorithm 10.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 10.1: a sequence x^k follows the proximal gradient method for the composite objective f + g with positive parameters L_k when, at every iteration k, the current iterate lies in int(dom(f)) and the next iterate satisfies x^(k+1) ∈ prox_{(1 / L_k) g}(x^k - (1 / L_k) ∇ f(x^k)).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def is_proximal_gradient_trajectory (f g : E → EReal) (x : ℕ → E) (L : ℕ → PosReal) : Prop := ∀ k : ℕ, x k ∈ interior (effective_domain f) ∧ x (k + 1) ∈ proximal_gradient_step f g (x k) (L k) -- Proof sketch: specialize the defining universal clause in -- `is_proximal_gradient_trajectory f g x L` at the iteration index `k`.

Assumption 10.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

Assumption 10.1: the standing hypotheses (A)-(C) for the composite model min_x {F(x) = f(x) + g(x)} are the existing owner class IsCompositeSmoothMinimizationProblem, which packages that g : E → (-∞, ∞] is proper, closed, and convex; that f : E → (-∞, ∞] never takes the value -∞, is closed, has convex effective domain, satisfies effective_domain g ⊆ interior (effective_domain f), and has (fun x ↦ (f x).toReal) L_f-smooth on interior (effective_domain f); consequently f is proper; and that the optimal set X^* is nonempty with optimal value F_opt.

recall IsCompositeSmoothMinimizationProblem

Definition 10.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 10.1: a Euclidean space carries the canonical real inner product structure InnerProductSpace ℝ E.

universe u variable (E : Type u) [NormedAddCommGroup E] [InnerProductSpace ℝ E] #check InnerProductSpace ℝ E

Algorithm 10.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 10.2: given parameters s > 0, γ ∈ (0,1), and η > 1, an index i_k is a valid output of backtracking procedure B1 at the current iterate x^k when the trial curvature s η^{i_k} is the first geometric trial satisfying F(x^k) - F(T_{s η^{i_k}}(x^k)) ≥ (γ / (s η^{i_k})) ‖G_{s η^{i_k}}(x^k)‖².

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] class is_backtracking_procedure_B1_index (f g : E → EReal) [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (s : PosReal) (γ : ProximalGradientBacktrackingDecreaseFraction) (η : ProximalGradientBacktrackingGrowthFactor) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) (x : effective_domain g) (i : ℕ) : Prop where accepts : proximal_gradient_backtracking_accepts f g γ (proximal_gradient_backtracking_trial_stepsize s η i) hg_effective_domain_subset_interior_f_effective_domain x minimal (j : ℕ) (hj : j < i) : ¬ proximal_gradient_backtracking_accepts f g γ (proximal_gradient_backtracking_trial_stepsize s η j) hg_effective_domain_subset_interior_f_effective_domain x

Definition 10.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 10.2: the composite model objective is the pointwise sum F(x) = f(x) + g(x) whose minimization over E is the composite optimization problem.

universe u v variable {E : Type u} {α : Type v} [Add α] abbrev composite_model_objective (f g : E → α) : E → α := f + g -- Proof sketch: `composite_model_objective` is definitionally the canonical pointwise sum `f + g`.

Algorithm 10.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 10.3: given a previous curvature estimate LPrev > 0 and a growth factor η > 1, an index i is a valid B2 backtracking output at the current iterate x when the trial curvature LPrev η^i is the first geometric trial satisfying the quadratic upper-model acceptance test. At iteration k, this applies with LPrev = L_(k-1), and at the initial step with LPrev = s = L_(-1).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] class is_backtracking_procedure_B2_index (f g : E → EReal) [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (LPrev : PosReal) (η : ProximalGradientBacktrackingGrowthFactor) (x : interior (effective_domain f)) (i : ℕ) : Prop where accepts : proximal_gradient_backtracking_B2_accepts f g (proximal_gradient_backtracking_trial_stepsize LPrev η i) x minimal (j : ℕ) (hj : j < i) : ¬ proximal_gradient_backtracking_B2_accepts f g (proximal_gradient_backtracking_trial_stepsize LPrev η j) x

Definition 10.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 10.3: clauses (A)-(C) for the composite model min_x {F(x) = f(x) + g(x)} mean that g is proper, closed, and convex; f never takes the value -∞, is closed, effective_domain f is convex, `effective_domain g ⊆ interior (effective_domain f), and (fun x ↦ (f x).toReal)isL_f`-smooth on interior (effective_domain f); these clauses therefore imply that f is proper; and XStar = X^* is the nonempty optimal set with optimal value FOpt = F_opt.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsCompositeSmoothMinimizationProblem (f g : E → EReal) (XStar : outParam (Set E)) (FOpt : outParam ℝ) (Lf : NNReal) : Prop where f_ne_bot : ∀ x, f x ≠ ⊥ g_proper : IsProperExtendedRealFunction g f_closed : LowerSemicontinuous f g_closed : LowerSemicontinuous g g_convex : is_convex_function g f_effective_domain_convex : Convex ℝ (effective_domain f) g_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f) f_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun x ↦ (f x).toReal) (interior (effective_domain f)) Lf optimal_set_eq : XStar = unconstrained_problem_solutions (composite_model_objective f g) optimal_set_nonempty : XStar.Nonempty optimal_value_isGLB : IsGLB (Set.range (composite_model_objective f g)) (FOpt : EReal)

Lemma 10.4

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

Source header · Attribution source

Lemma 10.4: if g is proper, closed, and convex; effective_domain f is convex; effective_domain g ⊆ interior (effective_domain f); and (fun y ↦ (f y).toReal) is L_f-smooth on interior (effective_domain f), then for every positive stepsize L the composite objective F = f + g decreases along one prox-grad step by at least ((L - L_f / 2) / L^2) ‖G_L^{f,g}(x)‖².

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (f g : E → EReal) (Lf : NNReal) variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] variable [Fact (is_convex_function g)] (hf_ne_bot : ∀ y, f y ≠ ⊥) variable (hf_effective_domain_convex : Convex ℝ (effective_domain f)) variable (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) variable (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) local notation "F" => composite_model_objective f g include hf_ne_bot hf_effective_domain_convex hg_effective_domain_subset_interior_f_effective_domain hf_toReal_smooth_on_interior_effective_domain theorem prox_grad_sufficient_decrease (L : PosReal) (x : interior (effective_domain f)) : F (x : E) - F (T[L, f, g] x) ≥ ((((L : ℝ) - (Lf : ℝ) / 2) / (L : ℝ) ^ (2 : ℕ) * ‖G[L, f, g] x‖ ^ (2 : ℕ) : ℝ) : EReal)

Definition 10.4.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 10.4.1: the unconstrained minimization problem min {f(x) | x ∈ E} is the Chapter 8 owner specialized to f.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (f : E → ℝ) (Lf : NNReal) #check unconstrained_problem_solutions f

Definition 10.4.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 10.4.2: the constrained problem itself is the Chapter 8 owner IsConstrainedConvexProblem f C XStar fOpt.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable (f : E → EReal) (C XStar : Set E) (fOpt : ℝ) (Lf : NNReal) #check IsConstrainedConvexProblem f C XStar fOpt

Definition 10.4.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 10.4.3: the Euclidean ℓ¹-regularized problem is the unconstrained minimization problem for the Chapter 10 composite objective x ↦ f x + λ ‖x‖₁.

universe u variable {ι : Type u} [Fintype ι] local notation "E" => EuclideanSpace ℝ ι variable (f : E → ℝ) (lam : ℝ) (Lf : NNReal) #check (unconstrained_problem_solutions (composite_model_objective f (fun x : E ↦ lam * EuclideanSpace.l1Norm x)) : Set E)

Definition 10.4.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 10.4.4 is a bridge/view specialization in the constrained first-order-method domain. The recursive owner already exists upstream as Algorithm 8.3's projected_subgradient_method, and the textbook projected-gradient iteration is exactly that owner specialized to the selected direction gₖ(x) = ∇ f(x). The positive stepsizes remain primitive data through PosReal, while the constrained quadratic minimization clause is derived from Text 9.11's canonical indicator/quadratic projection bridge. Domain sampling: - projected_subgradient_method and projected_subgradient_method_succ from Algorithm 8.3; - PosReal from Definition 6.7; - isMinOn_mirror_c_half_squared_norm_indicator_update_iff_eq_projection from Text 9.11; - projectionPoint from Proposition 3.12 for the ambient-space projection formula. Accordingly, this file deletes the duplicate local owner and states Definition 10.4.4 directly as the gradient specialization of the existing Chapter 8 owner.

universe u open InnerProductSpace (toDualMap) open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall projected_subgradient_method

Definition 10.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 10.5 is source-facing: the textbook introduces the gradient mapping G_L^{f,g}(x) = L (x - T_L^{f,g}(x)) using the prox-grad operator from the preceding definition. The canonical owner in this chapter is therefore a direct definition on interior (effective_domain f), reusing prox_grad_operator rather than repackaging the same operator through a new problem structure.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] instance instLowerSemicontinuousOfFact (g : E → EReal) [Fact (LowerSemicontinuous g)] : LowerSemicontinuous g

Algorithm 10.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 10.6: under Assumption 10.31, the owner-level fast stepsize bridge supplies the FISTA upper-model inequality (10.39) at every point y^k.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f : E → ℝ} {g : E → EReal} variable {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} namespace IsFastProximalGradientProblem variable [hproblem : IsFastProximalGradientProblem f g XStar FOpt Lf] theorem sublinearRateStepsizeRule_accepts {α : ℝ} {y : ℕ → E} {L : ℕ → PosReal} (hrule : hproblem.SublinearRateStepsizeRule y L α) (k : ℕ) : let xNext := hproblem.proxPoint (L k) (y k) f xNext ≤ f (y k) + inner ℝ (∇ f (y k)) (xNext - y k) + ((L k : ℝ) / 2) * ‖xNext - y k‖ ^ (2 : ℕ)

Corollary 10.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

Corollary 10.6: under the assumptions of Lemma 10.4, specializing the prox-gradient descent estimate to the stepsize L_f gives F(x) - F(T[L_f, f, g] x) ≥ (1 / (2 L_f)) ‖G[L_f, f, g] x‖^2 for every x ∈ interior (effective_domain f).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (f g : E → EReal) variable (Lf : PosReal) variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] local notation "F" => composite_model_objective f g -- Proof sketch: specialize `prox_grad_sufficient_decrease` to the stepsize `L = Lf`. The -- coefficient `((L_f - L_f / 2) / L_f^2)` then simplifies to `1 / (2 L_f)`, and the residual -- term is already expressed through the Chapter 10 owners `T[Lf, f, g]` and `G[Lf, f, g]` from -- `Lemma_10_4`. theorem prox_grad_sufficient_decrease_at_smoothness_constant (hf_ne_bot : ∀ y, f y ≠ ⊥) (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) (PosReal.toNNReal Lf)) (x : interior (effective_domain f)) : F (x : E) - F (T[Lf, f, g] x) ≥ (((1 / (2 * (Lf : ℝ)) * ‖G[Lf, f, g] x‖ ^ (2 : ℕ) : ℝ) : EReal))

Theorem 10.7

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

Source header · Attribution source

Theorem 10.7 (1): specializing the Chapter 10 gradient mapping to the zero penalty g₀ = 0 recovers the ambient gradient of f.toReal on interior (effective_domain f).

universe u open InnerProductSpace (toDual toDualMap) open scoped Gradient Pointwise variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] -- Proof sketch: the constant zero function never takes the value `⊥`, every point lies in its -- effective domain, it is continuous as an `EReal`-valued constant function, and its real-valued -- restriction is convex on `Set.univ`. theorem gradient_mapping_zero_penalty_eq_gradient (f : E → EReal) (L : PosReal) (x : interior (effective_domain f)) : G[L, f, 0] x = ∇ (fun y ↦ (f y).toReal) (x : E)

Text 10.7.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

Text 10.7.1 (1): the weighted Q-norm and weighted gradient on ℝ^n are read through the existing Chapter 1 and Chapter 3 bridge APIs.

#check Matrix.qNorm

Corollary 10.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

Corollary 10.8: if g is proper, closed, and convex, `effective_domain g ⊆ interior (effective_domain f), fnever takes the value-∞, fisL_f`-smooth on interior (effective_domain f), and f is convex, then for xStar ∈ effective_domain g, the gradient mapping vanishes at xStar if and only if xStar is a global minimizer of the composite objective F(x) = f(x) + g(x).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] -- Proof sketch: send `xStar ∈ effective_domain g` into `interior (effective_domain f)` using the -- domain-inclusion hypothesis, use smoothness plus the no-`⊥` hypothesis to obtain -- `is_differentiable_at f xStar`, apply Theorem 10.7 to rewrite vanishing of the gradient -- mapping as stationarity, then -- apply Theorem 3.35 and the domain-restriction lemma above to identify stationarity with global -- optimality of the composite objective. theorem gradient_mapping_eq_zero_iff_optimal_composite_model_objective (f g : E → EReal) (hf_ne_bot : ∀ y, f y ≠ ⊥) [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (Lf : NNReal) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) (hf_convex : is_convex_function f) (L : PosReal) {xStar : E} (hxStar : xStar ∈ effective_domain g) : G[L, f, g] ⟨xStar, hg_effective_domain_subset_interior_f_effective_domain hxStar⟩ = 0 ↔ IsMinOn (composite_model_objective f g) Set.univ xStar

Definition 10.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 10.8 (1): sequences of iterates x and positive stepsizes t follow the proximal-gradient method for f + g when f is differentiable at every iterate x^k and the iterates satisfy the textbook stepsize update x^(k+1) ∈ prox[t_k g](x^k - t_k ∇ f(x^k)).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] class is_proximal_gradient_trajectory_with_stepsizes (f : E → ℝ) (g : E → EReal) (x : ℕ → E) (t : ℕ → PosReal) : Prop where /-- The primitive per-iteration data of a Definition 10.8 stepsize trajectory. -/ step : ∀ k : ℕ, DifferentiableAt ℝ f (x k) ∧ x (k + 1) ∈ prox[(((t k : ℝ) : EReal) • g)] (x k - (t k : ℝ) • ∇ f (x k))

Definition 10.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 10.9: for a proper closed convex function g and a positive parameter L, the prox-grad operator sends x ∈ interior (dom f) to the unique point of the Chapter 10 owner proximal_gradient_step f g x L.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] def prox_grad_operator (f g : E → EReal) [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (L : PosReal) : interior (effective_domain f) → E := fun x ↦ Classical.choose <| proximal_gradient_step_eq_singleton f g L (x : E)

Theorem 10.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 10.9 (1): for a proper closed convex g, the norm of the gradient mapping G_L^{f,g}(x) is monotone nondecreasing in the positive parameter L. In particular, if L₁ ≥ L₂ > 0, then ‖G_{L₂}(x)‖ ≤ ‖G_{L₁}(x)‖.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] theorem gradient_mapping_norm_monotone (f g : E → EReal) [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (x : interior (effective_domain f)) : Monotone (fun L : PosReal ↦ ‖G[L, f, g] x‖)

Lemma 10.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

Lemma 10.10 (1): for a proper closed convex g and an L_f-smooth extended-real-valued function f on interior (effective_domain f), the gradient mapping G_L is (2L + L_f)-Lipschitz on interior (effective_domain f).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {Lf : NNReal} variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] theorem gradient_mapping_lipschitz (hf_smooth : is_l_smooth_on (fun x ↦ (f x).toReal) (interior (effective_domain f)) Lf) (L : PosReal) : LipschitzWith (2 * PosReal.toNNReal L + Lf) (G[L, f, g])

Algorithm 10.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 10.11: sequences (x^k, y^k, z^k, L_k) form an MFISTA trajectory for f and g when y 0 = x 0, each z k is the prox-gradient point T[L k; f, g] (y k), the monotonicity clause is stated exactly by the displayed inequality `composite_model_objective f.toEReal g (x (k + 1)) ≤ min (composite_model_objective f.toEReal g (z k)) (composite_model_objective f.toEReal g (x k))`, and y (k + 1) is given by the MFISTA extrapolation formula using the canonical Chapter 10 momentum sequence fista_momentum_sequence. Under Assumption 10.31, the bridge IsFastProximalGradientProblem.IsMfistaTrajectory recovers the standing regularity assumptions on f and g.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] class is_mfista_trajectory (f : E → ℝ) (g : E → EReal) [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (x y z : ℕ → E) (L : ℕ → PosReal) : Prop where /-- The MFISTA initialization clause is `y 0 = x 0`. -/ init : y 0 = x 0 /-- At each iteration `k`, MFISTA records the prox-gradient point, the source monotonicity inequality, and the extrapolated next search point. -/ step : ∀ k : ℕ, z k = T[L k; f, g] (y k) ∧ composite_model_objective f.toEReal g (x (k + 1)) ≤ min (composite_model_objective f.toEReal g (z k)) (composite_model_objective f.toEReal g (x k)) ∧ y (k + 1) = x (k + 1) + (fista_momentum_sequence k / fista_momentum_sequence (k + 1)) • (z k - x (k + 1)) + ((fista_momentum_sequence k - 1) / fista_momentum_sequence (k + 1)) • (x (k + 1) - x k)

Definition 10.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 10.11: for an admissible parameter barL ∈ (L_f / 2, ∞), the constant stepsize strategy is the canonical constant map on ℕ with value barL.

variable {Lf : NNReal} #check (Function.const ℕ : PosReal → ℕ → PosReal)

Lemma 10.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

Lemma 10.11 (1): if f is convex and globally L-smooth and g is proper closed convex, then the specialized Chapter 10 gradient mapping satisfies `⟪G[L; f, g] x - G[L; f, g] y, x - y⟫ ≥ (3 / (4L)) ‖G[L; f, g] x - G[L; f, g] y‖²`.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (f : E → ℝ) (g : E → EReal) (L : PosReal) variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] theorem prox_gradient_mapping_cocoercive (hf_convex : ConvexOn ℝ Set.univ f) (hf_smooth : is_l_smooth_on f Set.univ (PosReal.toNNReal L)) (x y : E) : inner ℝ (G[L; f, g] x - G[L; f, g] y) (x - y) ≥ (3 / (4 * (L : ℝ))) * ‖G[L; f, g] x - G[L; f, g] y‖ ^ (2 : ℕ)

Definition 10.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 10.12: a sequence x^k follows the proximal-point method for g with parameter c > 0 and initial point x^0 = x0 when it starts at x0 and each successor iterate belongs to the scaled proximal set prox[((c : EReal) • g)] (x^k).

universe u variable {E : Type u} [NormedAddCommGroup E] def is_proximal_point_trajectory (g : E → EReal) (x0 : E) (c : PosReal) (x : ℕ → E) : Prop := x 0 = x0 ∧ ∀ k : ℕ, x (k + 1) ∈ prox[((c : EReal) • g)] (x k)

Lemma 10.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

Lemma 10.12: if f is convex and globally L-smooth for a positive stepsize L, and g is proper closed convex, then one prox-gradient step does not increase the norm of the gradient mapping: ‖G_L(T_L(x))‖ ≤ ‖G_L(x)‖.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] theorem prox_grad_step_gradient_mapping_norm_monotone (f : E → ℝ) (g : E → EReal) (L : PosReal) (hf_convex : ConvexOn ℝ Set.univ f) (hf_smooth : is_l_smooth_on f Set.univ (PosReal.toNNReal L)) [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (x : E) : ‖G[L; f, g] (T[L; f, g] x)‖ ≤ ‖G[L; f, g] x‖

Algorithm 10.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 10.13: given an input point z^{-1} and a positive integer restart length N, the restarted FISTA sequence is defined by z^0 = T_(L_f)(z^{-1}) and z^(k+1) = x^N, where x^N is the Nth constant-stepsize FISTA iterate started from z^k.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (f : E → ℝ) (g : E → EReal) variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] def restarted_fista (Lf : PosReal) (zMinusOne : E) (N : ℕ+) : ℕ → E

Remark 10.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

Remark 10.13 (1): for a proper closed convex g and a smooth term f that never takes the value -∞, whose domain contains effective_domain g in its interior, backtracking procedure B1 terminates at every point x^k ∈ dom(g). Equivalently, there exists a valid backtracking index whose accepted trial curvature satisfies the sufficient-decrease inequality.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (f g : E → EReal) (Lf : NNReal) variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] variable [Fact (is_convex_function g)] variable (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) variable (s : PosReal) (γ : ProximalGradientBacktrackingDecreaseFraction) variable (η : ProximalGradientBacktrackingGrowthFactor) (x : effective_domain g) theorem exists_backtracking_procedure_B1_index (hf_ne_bot : ∀ y, f y ≠ ⊥) (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) : ∃ i : ℕ, is_backtracking_procedure_B1_index f g s γ η hg_effective_domain_subset_interior_f_effective_domain x i

Algorithm 10.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 10.14: the primal V-FISTA iterate family x^k, with x^0 = y^0 = x0, x^(k+1) = prox_(1 / L_f g) (y^k - (1 / L_f) ∇ f(y^k)), and the companion extrapolated sequence y^k defined by the fixed momentum coefficient ((√(L_f / σ) - 1) / (√(L_f / σ) + 1)).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (f : E → ℝ) (g : E → EReal) variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] def vfista_x (x0 : E) (Lf σ : PosReal) (k : ℕ) : E := (vfista_state f g x0 Lf σ k).1

Lemma 10.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

Lemma 10.14 (1): under the one-step descent hypotheses of Lemma 10.4, if the iterates x^k are generated by the proximal gradient method with the constant stepsize barL ∈ (L_f / 2, ∞), then F(x^k) - F(x^(k+1)) ≥ M ‖G_barL(x^k)‖^2 with M = ((barL : ℝ) - L_f / 2) / barL^2.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {Lf : NNReal} variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] variable [Fact (is_convex_function g)] variable (hf_ne_bot : ∀ y, f y ≠ ⊥) (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) local notation "F" => composite_model_objective f g local notation:max "G[" L "]" => G[L, f, g] -- Proof sketch: rewrite the set-valued trajectory update at step `k` using the singleton -- description of the prox-gradient operator, so the realized successor `x^(k+1)` becomes the -- point-valued operator `T[L_k]` applied to the current iterate. include hf_ne_bot hf_effective_domain_convex hg_effective_domain_subset_interior_f_effective_domain hf_toReal_smooth_on_interior_effective_domain -- Proof sketch: specialize Lemma 10.4 at the canonical iterate `x^k` of the trajectory. This -- packages the primitive Assumption 10.1 hypotheses into a theorem-local API that the two source -- facing sufficient-decrease statements can reuse directly. theorem proximal_gradient_constant_stepsize_sufficient_decrease (barL : ProximalGradientConstantStepsizeParameter Lf) (x : ℕ → E) (htraj : is_proximal_gradient_trajectory f g x (Function.const ℕ barL)) (k : ℕ) : F (x k) - F (x (k + 1)) ≥ (((((barL : ℝ) - (Lf : ℝ) / 2) / ((barL : ℝ) ^ (2 : ℕ))) * ‖G[barL] (proximal_gradient_trajectory_iterate htraj k)‖ ^ (2 : ℕ) : ℝ) : EReal)

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

Theorem 10.15 (1): clause (a). Under the primitive regularity hypotheses isolated in Lemma 10.14, if the proximal-gradient trajectory uses either a constant stepsize barL ∈ (L_f / 2, ∞) or backtracking procedure B1, then the objective sequence F(x^k) is nonincreasing.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {Lf : NNReal} variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] variable [Fact (is_convex_function g)] variable (hf_ne_bot : ∀ y, f y ≠ ⊥) (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) local notation "F" => composite_model_objective f g local notation:max "G[" L "]" => G[L, f, g] variable {x : ℕ → E} {L : ℕ → PosReal} variable (htraj : is_proximal_gradient_trajectory f g x L) variable (hrule : (∃ barL : ProximalGradientConstantStepsizeParameter Lf, L = Function.const ℕ (barL : PosReal)) ∨ ∃ s : PosReal, ∃ γ : ProximalGradientBacktrackingDecreaseFraction, ∃ η : ProximalGradientBacktrackingGrowthFactor, uses_proximal_gradient_backtracking_B1_rule f g hg_effective_domain_subset_interior_f_effective_domain x L htraj s γ η) include hf_ne_bot hf_effective_domain_convex hg_effective_domain_subset_interior_f_effective_domain hf_toReal_smooth_on_interior_effective_domain htraj hrule theorem proximal_gradient_objective_values_antitone : Antitone (fun k ↦ F (x k))

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

Theorem 10.16: if the local B2 upper-model inequality holds at y, equivalently f(T_L(y)) ≤ f(y) + ⟪∇ f(y), T_L(y) - y⟫ + (L / 2) ‖T_L(y) - y‖², then the composite objective satisfies the fundamental prox-grad inequality F(x) - F(xPlus) ≥ (L / 2) ‖x - xPlus‖² - (L / 2) ‖x - y‖² + ℓ_f(x, y).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] local notation "F" => composite_model_objective f g theorem fundamental_prox_grad_inequality (x : E) (y : interior (effective_domain f)) (L : PosReal) (hmodel : proximal_gradient_backtracking_B2_accepts f g L y) : let xPlus := T[L, f, g] y F x - F xPlus ≥ ((((L : ℝ) / 2) * ‖x - xPlus‖ ^ (2 : ℕ) - ((L : ℝ) / 2) * ‖x - (y : E)‖ ^ (2 : ℕ) : ℝ) : EReal) + ℓ[f, x, y]

Remark 10.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

Remark 10.17: the first-order residual ℓ_f(x, y) = f(x) - f(y) - ⟪∇ f(y), x - y⟫ is the Chapter 10 owner prox_gradient_linearization_defect, with notation ℓ[f, x, y].

universe u open scoped Gradient recall prox_gradient_linearization_defect

Corollary 10.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

Corollary 10.18: if the local quadratic upper model of f at the prox-grad step T_L(x) holds, then the composite objective decreases by at least (1 / (2L)) ‖G_L(x)‖². The standing composite-model hypothesis f y ≠ ⊥ for all y is kept explicit here because it is part of the chapter setup used to interpret the displayed extended-real subtraction.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] local notation "F" => composite_model_objective f g theorem prox_grad_sufficient_decrease_of_upper_model (hf_ne_bot : ∀ y, f y ≠ ⊥) (L : PosReal) (x : interior (effective_domain f)) (hupper : proximal_gradient_backtracking_B2_accepts f g L x) : F x - F (T[L, f, g] x) ≥ (((1 : ℝ) / (2 * (L : ℝ)) * ‖G[L, f, g] x‖ ^ (2 : ℕ) : ℝ) : EReal)

Remark 10.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

Remark 10.19 (1): under the same hypotheses, the accepted stepsize inequality can be written in the displayed source-facing form f(x^(k+1)) ≤ f(x^k) + ⟪∇ f(x^k), x^(k+1) - x^k⟫ + (L_k / 2) ‖x^(k+1) - x^k‖².

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g : E → EReal} {Lf : NNReal} variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] variable (hf_effective_domain_convex : Convex ℝ (effective_domain f)) variable (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) variable (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) theorem proximal_gradient_upper_model_of_constant_or_backtracking_B2_rule (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) {x : ℕ → E} {L : ℕ → PosReal} (htraj : is_proximal_gradient_trajectory f g x L) (hrule : proximal_gradient_constant_or_backtracking_B2_stepsize_rule f g Lf x L htraj) (k : ℕ) : f (x (k + 1)) ≤ (((f (x k)).toReal + inner ℝ (∇ (fun y ↦ (f y).toReal) (x k)) (x (k + 1) - x k) + ((L k : ℝ) / 2) * ‖x (k + 1) - x k‖ ^ (2 : ℕ) : ℝ) : EReal)

Remark 10.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

Remark 10.20: if x is a proximal-gradient trajectory for f + g, f is differentiable at x^k in the Chapter 3 sense, and the local quadratic upper model of f holds at the realized successor iterate x^(k+1), then the composite objective is monotone at that step: F(x^(k+1)) ≤ F(x^k), where F = f + g.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g : E → EReal} {x : ℕ → E} {L : ℕ → PosReal} local notation "F" => composite_model_objective f g -- Proof sketch: use `is_proximal_gradient_trajectory_step` together with the canonical -- curvature-model bridge from Algorithm 10.66 to view `x (k + 1)` as a minimizer of the one-step -- quadratic model at `x k`. Testing that minimizing property against `x k` bounds the curvature -- model at `x (k + 1)` by `F (x k)`. theorem composite_model_objective_monotone_of_upper_model (htraj : is_proximal_gradient_trajectory f g x L) (k : ℕ) (hfxk : is_differentiable_at f (x k)) (hmodel : f (x (k + 1)) ≤ (((f (x k)).toReal + inner ℝ (∇ (fun y ↦ (f y).toReal) (x k)) (x (k + 1) - x k) + ((L k : ℝ) / 2) * ‖x (k + 1) - x k‖ ^ (2 : ℕ) : ℝ) : EReal)) : F (x (k + 1)) ≤ F (x k)

Definition 10.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 10.21: the condition number attached to the smoothness constant L_f and the positive strong-convexity modulus σ is the ratio L_f / σ.

def condition_number (Lf : NNReal) (σ : PosReal) : ℝ := (Lf : ℝ) / (σ : ℝ)

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

Theorem 10.21: under Assumption 10.1, if f is convex and x^k is generated by the proximal gradient method with either the constant stepsize rule L_k = L_f or backtracking procedure B2, then every positive iterate satisfies the sublinear objective-gap estimate F(x^k) - F_opt ≤ α L_f ‖x^0 - x*‖² / (2 k).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsConvexCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {α : ℝ} {x : ℕ → E} {L : ℕ → PosReal} {xStar : E} local notation "F" => composite_model_objective f g include hproblem theorem proximal_gradient_convex_objective_gap_le (htraj : is_proximal_gradient_trajectory f g x L) (hrule : hproblem.SourceSublinearRateStepsizeRule x L htraj α) (hxStar : xStar ∈ XStar) (k : ℕ) (hk : 1 ≤ k) : F (x k) - (FOpt : EReal) ≤ ((α * (Lf : ℝ) * ‖x 0 - xStar‖ ^ (2 : ℕ) / (2 * (k : ℝ)) : ℝ) : EReal)

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

Theorem 10.23: under Assumption 10.1, if f is convex and x^k is generated by the proximal gradient method with either the exact L_f rule or backtracking procedure B2, then the trajectory is Fejér monotone with respect to the optimal set XStar = X^*.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsConvexCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {x : ℕ → E} {L : ℕ → PosReal} local notation "F" => composite_model_objective f g theorem proximal_gradient_fejer_monotonicity (htraj : is_proximal_gradient_trajectory f g x L) (hrule : hproblem.ConstantOrBacktrackingB2StepsizeRule x L htraj) : IsFejerMonotoneWithRespectTo x XStar

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

Theorem 10.24: under Assumption 10.1, if f is convex and x^k is generated by the proximal gradient method with either the exact L_f rule or backtracking procedure B2, then the sequence converges to an optimal solution xStar ∈ XStar = X^*.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsConvexCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {x : ℕ → E} {L : ℕ → PosReal} namespace IsConvexCompositeSmoothMinimizationProblem theorem proximal_gradient_tendsto_optimal_point (htraj : is_proximal_gradient_trajectory f g x L) (hrule : hproblem.SourceConvergenceStepsizeRule x L htraj) : ∃ xStar ∈ XStar, Filter.Tendsto x Filter.atTop (nhds xStar)

Theorem 10.25

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 10.25: under Assumption 10.1, if f is convex and the proximal-gradient iterates use either the constant rule L_k = L_f or backtracking procedure B2, then any iterate index k ≥ ⌈α L_f R^2 / (2 ε)⌉ satisfies F(x^k) - F_opt ≤ ε, where R bounds the distance from the initial point x^0 to some optimizer xStar ∈ X^*.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsConvexCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {α : ℝ} {x : ℕ → E} {L : ℕ → PosReal} {xStar : E} local notation "F" => composite_model_objective f g theorem proximal_gradient_convex_objective_gap_le_of_ceiling_iteration_bound (htraj : is_proximal_gradient_trajectory f g x L) (hrule : hproblem.SourceSublinearRateStepsizeRule x L htraj α) (hxStar : xStar ∈ XStar) (ε : PosReal) (R : ℝ) (hR : ‖x 0 - xStar‖ ≤ R) (k : ℕ) (hiter : Nat.ceil (α * (Lf : ℝ) * R ^ (2 : ℕ) / (2 * (ε : ℝ))) ≤ k) : F (x k) - (FOpt : EReal) ≤ ((ε : ℝ) : EReal)

Theorem 10.26

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 10.26: under Assumption 10.1, if f is convex and x^k is generated by the proximal gradient method with the source-faithful constant/B2 stepsize regime from Theorem 10.21 with upper-rate factor α, and if the theorem-specific lower factor β satisfies β L_f ≤ L_n on the prefix 0 ≤ n ≤ k, then for every minimizer xStar ∈ X^* the best gradient-mapping norm up to iteration k at the canonical parameter α L_f satisfies the displayed source bound `min_{0 ≤ n ≤ k} ‖G_(α L_f)(x^n)‖ ≤ sqrt (α^3 L_f^2 ‖x^0 - xStar‖^2 / (β k))`, equivalently an O(1 / sqrt k) rate, for k ≥ 1.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsConvexCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {x : ℕ → E} {L : ℕ → PosReal} {xStar : E} {α : ℝ} {β : PosReal} local notation "R[" htraj "; " d ", " k "]" => letI : IsProperExtendedRealFunction g := hproblem.g_proper letI : Fact (LowerSemicontinuous g) := ⟨hproblem.g_closed⟩ letI : Fact (is_convex_function g) := ⟨hproblem.g_convex⟩ best_achieved_function_value (fun y ↦ ‖G[d, f, g] y‖) (proximal_gradient_trajectory_iterate htraj) k local notation "F" => composite_model_objective f g theorem proximal_gradient_best_gradient_mapping_norm_le_sublinear_rate (htraj : is_proximal_gradient_trajectory f g x L) (hrule : hproblem.SourceSublinearRateStepsizeRule x L htraj α) (hxStar : xStar ∈ XStar) (k : ℕ) (hk : 1 ≤ k) (hLlower : ∀ ⦃n : ℕ⦄, n ≤ k → (β : ℝ) * (Lf : ℝ) ≤ (L n : ℝ)) : R[htraj; hproblem.sublinearRateResidualStepsize htraj α (sourceSublinearRateRule_sublinearRateStepsizeRule htraj hrule), k] ≤ Real.sqrt (α ^ (3 : ℕ) * (Lf : ℝ) ^ (2 : ℕ) * ‖x 0 - xStar‖ ^ (2 : ℕ) / ((β : ℝ) * (k : ℝ)))

Theorem 10.27

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 10.27 (1): clause (a). If g is proper, closed, and convex, f is convex and globally L_f-smooth, and the proximal-gradient trajectory uses the constant stepsize rule L_k = L_f, then the gradient-mapping norms are nonincreasing: ‖G_(L_f)(x^(k+1))‖ ≤ ‖G_(L_f)(x^k)‖.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f : E → ℝ} {g : E → EReal} {Lf : NNReal} variable {x : ℕ → E} {L : ℕ → PosReal} theorem proximal_gradient_mapping_norm_nonincreasing_of_constant_stepsize [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] (hf_convex : ConvexOn ℝ Set.univ f) (hf_smooth : is_l_smooth_on f Set.univ Lf) (htraj : is_proximal_gradient_trajectory f.toEReal g x L) (hLconst : uses_proximal_gradient_Lf_stepsize_rule Lf L) (k : ℕ) : ‖G[hLconst.stepsize; f, g] (x (k + 1))‖ ≤ ‖G[hLconst.stepsize; f, g] (x k)‖

Theorem 10.28

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 10.28 (1): along any proximal-point trajectory starting from x^0 = x0, for any optimal point xStar ∈ X^* and any index k ≥ 1, the k-th iterate satisfies the O(1 / k) objective-gap estimate relative to the canonical optimal value g xStar.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable (g : E → EReal) [IsProperExtendedRealFunction g] variable [Fact (is_convex_function g)] variable (x0 : E) (c : PosReal) variable {x : ℕ → E} local notation "XStar" => unconstrained_problem_solutions g open scoped ProximalPoint theorem proximal_point_method_objective_gap_le (htraj : is_proximal_point_trajectory g x0 c x) (xStar : E) (hxStar : xStar ∈ XStar) (k : ℕ) (hk : 1 ≤ k) : g (x k) - g xStar ≤ ((((‖x0 - xStar‖ ^ (2 : ℕ)) / (2 * (c : ℝ) * (k : ℝ))) : ℝ) : EReal)

Definition 10.29

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 10.29: for a real-valued function h, the Chapter 10 Moreau smoothing is exactly the specialized Chapter 6 owner M[μ, h.toEReal].

universe u variable {E : Type u} [NormedAddCommGroup E] variable (μ : PosReal) (h : E → ℝ) #check M[μ, h.toEReal]

Theorem 10.29

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 10.29 (1): clause (a). Under Assumption 10.1, if f is σ-strongly convex and the proximal-gradient trajectory uses either the constant rule L_k = L_f or backtracking procedure B2 with the corresponding value of α, then with κ = L_f / σ, ‖x^(k+1) - x*‖² ≤ (1 - 1 / (α κ)) ‖x^k - x*‖².

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {σ : PosReal} {α : ℝ} {x : ℕ → E} {L : ℕ → PosReal} {xStar : E} local notation "F" => composite_model_objective f g local notation "κ" => κ(Lf, σ) theorem proximal_gradient_strongly_convex_step_distance_sq_le (hstrong : StrongConvexOn (effective_domain f) (σ : ℝ) (fun y ↦ (f y).toReal)) (htraj : is_proximal_gradient_trajectory f g x L) (hrule : hproblem.SublinearRateStepsizeRule x L htraj α) (hL_bound : ∀ k, (L k : ℝ) ≤ α * (Lf : ℝ)) (hxStar : xStar ∈ XStar) (k : ℕ) : ‖x (k + 1) - xStar‖ ^ (2 : ℕ) ≤ (1 - 1 / (α * κ)) * ‖x k - xStar‖ ^ (2 : ℕ)

Theorem 10.30

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 10.30: in the strongly convex proximal-gradient setting of Theorem 10.29, if the positive iteration index k satisfies the logarithmic iteration bound α κ log (1 / ε) + α κ log (α L_f R^2 / 2) ≤ k, where κ = L_f / σ and R bounds ‖x^0 - x*‖, then the k-th iterate satisfies F(x^k) - F_opt ≤ ε.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {σ : PosReal} {α : ℝ} {x : ℕ → E} {L : ℕ → PosReal} {xStar : E} local notation "F" => composite_model_objective f g local notation "κ" => κ(Lf, σ) theorem proximal_gradient_strongly_convex_objective_gap_le_of_log_iteration_bound (hstrong : StrongConvexOn (effective_domain f) (σ : ℝ) (fun y ↦ (f y).toReal)) (htraj : is_proximal_gradient_trajectory f g x L) (hrule : hproblem.SublinearRateStepsizeRule x L htraj α) (hL_bound : ∀ n, (L n : ℝ) ≤ α * (Lf : ℝ)) (hxStar : xStar ∈ XStar) (ε : PosReal) (R : ℝ) (hR : ‖x 0 - xStar‖ ≤ R) (k : ℕ+) (hiter : α * κ * Real.log (1 / (ε : ℝ)) + α * κ * Real.log (α * (Lf : ℝ) * R ^ (2 : ℕ) / 2) ≤ (k : ℝ)) : F (x k) - (FOpt : EReal) ≤ ((ε : ℝ) : EReal)

Assumption 10.31

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

Assumption 10.31: clauses (A)-(C) for the fast proximal-gradient method mean that g : E → (-∞, ∞] is proper, closed, and convex, f : E → ℝ is convex and globally L_f-smooth, and XStar = X^* is the nonempty optimal set of the composite problem min_x ((f x : EReal) + g x) with optimal value FOpt = F_opt.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsFastProximalGradientProblem (f : E → ℝ) (g : E → EReal) (XStar : outParam (Set E)) (FOpt : outParam ℝ) (Lf : outParam NNReal) : Prop where g_proper : IsProperExtendedRealFunction g g_closed : LowerSemicontinuous g g_convex : is_convex_function g f_convex : ConvexOn ℝ Set.univ f f_smooth : is_l_smooth_on f Set.univ Lf optimal_set_eq : XStar = unconstrained_problem_solutions (composite_model_objective f.toEReal g) optimal_set_nonempty : XStar.Nonempty optimal_value_isGLB : IsGLB (Set.range (composite_model_objective f.toEReal g)) (FOpt : EReal) -- Proof sketch for the bridge theorem below: a real-valued `L_f`-smooth convex function is -- continuous, hence lower -- semicontinuous, and its `EReal` coercion never takes the value `-∞` and has full effective -- domain `Set.univ`. Combine these derived facts with the source-facing fields of -- `IsFastProximalGradientProblem` and the convexity bridge `Function.toEReal_isConvexFunction`.

Remark 10.32

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

Remark 10.32: if the curvature estimates are generated by backtracking procedure B3 with initial value L_(-1) = s, multiplier η > 1, and a globally L_f-smooth convex term f, then for every iteration k the accepted stepsize satisfies s ≤ L_k ≤ max {η L_f, s}. Equivalently, when L_f > 0, this is the textbook bound β L_f ≤ L_k ≤ α L_f with α = max {η, s / L_f} and β = s / L_f.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f : E → ℝ} {g : E → EReal} {Lf : NNReal} variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] theorem uses_backtracking_procedure_B3_rule_stepsize_bounds (hf_smooth : is_l_smooth_on f Set.univ Lf) (hf_convex : ConvexOn ℝ Set.univ f) {y : ℕ → E} {L : ℕ → PosReal} (s : PosReal) (η : ProximalGradientBacktrackingGrowthFactor) (hrule : uses_backtracking_procedure_B3_rule f g y L s η) (k : ℕ) : (s : ℝ) ≤ (L k : ℝ) ∧ (L k : ℝ) ≤ max ((η : ℝ) * (Lf : ℝ)) (s : ℝ)

Lemma 10.33

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 10.33: if a real sequence starts at t_0 = 1 and satisfies the FISTA momentum recursion t_(k+1) = (1 + √(1 + 4 t_k^2)) / 2, then t_k ≥ (k + 2) / 2 for every k ≥ 0.

theorem fista_momentum_sequence_lower_bound {t : ℕ → ℝ} (h0 : t 0 = 1) (hsucc : ∀ k : ℕ, t (k + 1) = fista_momentum_update (t k)) (k : ℕ) : ((k : ℝ) + 2) / 2 ≤ t k

Theorem 10.34

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 10.34 is source-facing: the completed Chapter 10 owner theorem already lives in Theorem_10_34_pass2_complete, so this entry file restores the canonical chapter import surface by re-exposing that theorem directly and keeping no local migration or proof infrastructure.

recall fista_objective_gap_le_two_alpha_Lf_dist_sq_div_sq

Theorem 10.34.pass2.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

Theorem 10.34: under Assumption 10.31, FISTA satisfies the textbook O(1 / k^2) objective-gap bound.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f : E → ℝ} {g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsFastProximalGradientProblem f g XStar FOpt Lf] variable (x0 : E) (L : ℕ → PosReal) {α : ℝ} {xStar : E} theorem fista_objective_gap_le_two_alpha_Lf_dist_sq_div_sq (hrule : hproblem.SublinearRateStepsizeRule (fistaY hproblem x0 L) L α) (hxStar : xStar ∈ XStar) (k : ℕ) (hk : 1 ≤ k) : composite_model_objective f.toEReal g (fistaX hproblem x0 L k) - (FOpt : EReal) ≤ (((2 * α * (Lf : ℝ) * ‖x0 - xStar‖ ^ (2 : ℕ)) / (k + 1 : ℝ) ^ (2 : ℕ) : ℝ) : EReal)

Remark 10.35

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

Remark 10.35 (2): the explicit affine comparison sequence satisfies the quadratic recursion inequality used in the FISTA O(1 / k^2) estimate.

theorem fista_affine_comparison_quadratic_recursion_bound (k : ℕ) : fista_affine_comparison (k + 1) ^ (2 : ℕ) - fista_affine_comparison (k + 1) ≤ fista_affine_comparison k ^ (2 : ℕ)

Theorem 10.40

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 10.40: under Assumption 10.31, any MFISTA trajectory whose curvature estimates are chosen either by the constant rule L_k = L_f with α = 1 or by backtracking procedure B3 with α = max {η, s / L_f} satisfies the accelerated objective-gap bound F(x^k) - F_opt ≤ 2 α L_f ‖x^0 - x*‖^2 / (k + 1)^2 for every optimizer x* ∈ X^* and every k ≥ 1.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f : E → ℝ} {g : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsFastProximalGradientProblem f g XStar FOpt Lf] variable {x y z : ℕ → E} {L : ℕ → PosReal} {α : ℝ} {xStar : E} theorem mfista_objective_gap_le_two_alpha_Lf_dist_sq_div_sq (htraj : hproblem.IsMfistaTrajectory x y z L) (hrule : hproblem.SublinearRateStepsizeRule y L α) (hxStar : xStar ∈ XStar) (k : ℕ) (hk : 1 ≤ k) : composite_model_objective f.toEReal g (x k) - (FOpt : EReal) ≤ (((2 * α * (Lf : ℝ) * ‖x 0 - xStar‖ ^ (2 : ℕ)) / (k + 1 : ℝ) ^ (2 : ℕ) : ℝ) : EReal)

Theorem 10.41

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 10.41 (2): if the same restart length N = ⌈√(8 κ(PosReal.toNNReal Lf, σ) - 1)⌉ is used and the total iteration count k satisfies the displayed logarithmic lower bound, then the restart point at the last completed cycle is ε-optimal. In Lean, the textbook index ⌊k / N⌋ is written k / (N : ℕ).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f : E → ℝ} {g : E → EReal} {XStar : Set E} {FOpt : ℝ} variable {Lf σ : PosReal} variable {xStar zMinusOne : E} {N : ℕ+} {R : ℝ} variable [hproblem : IsFastProximalGradientProblem f g XStar FOpt (PosReal.toNNReal Lf)] theorem restarted_fista_objective_gap_le_epsilon_of_iteration_bound (hstrong : StrongConvexOn Set.univ (σ : ℝ) f) (hxStar : xStar ∈ XStar) (hR : ‖zMinusOne - xStar‖ ≤ R) (hN : (N : ℕ) = Nat.ceil (Real.sqrt (8 * κ(PosReal.toNNReal Lf, σ) - 1))) (ε : PosReal) (k : ℕ) (hiter : Real.sqrt (8 * κ(PosReal.toNNReal Lf, σ)) * (Real.log (1 / (ε : ℝ)) / Real.log 2 + Real.log ((Lf : ℝ) * R ^ (2 : ℕ)) / Real.log 2) ≤ (k : ℝ)) : composite_model_objective f.toEReal g (restartedZ (f := f) (g := g) (Lf := Lf) (XStar := XStar) (FOpt := FOpt) (zMinusOne := zMinusOne) (N := N) (k / (N : ℕ))) - (FOpt : EReal) ≤ ((ε : ℝ) : EReal)

Theorem 10.42

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 10.42: under Assumption 10.31, if the smooth term f is σ-strongly convex, then the V-FISTA iterates satisfy the geometric objective-gap bound F(x^k) - F_opt ≤ (1 - 1 / √κ)^k (F(x^0) - F_opt + (σ / 2) ‖x^0 - x*‖²), where κ = L_f / σ.

universe u open PosReal open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f : E → ℝ} {g : E → EReal} {XStar : Set E} {FOpt : ℝ} variable {Lf σ : PosReal} variable {x0 xStar : E} local notation "F" => composite_model_objective f.toEReal g local notation "κ" => κ(toNNReal Lf, σ) local notation "t" => Real.sqrt κ variable (hproblem : IsFastProximalGradientProblem f g XStar FOpt (toNNReal Lf)) local notation "xv" => letI : IsProperExtendedRealFunction g := hproblem.g_proper letI : Fact (LowerSemicontinuous g) := ⟨hproblem.g_closed⟩ letI : Fact (is_convex_function g) := ⟨hproblem.g_convex⟩ vfista_x f g x0 Lf σ local notation "yv" => letI : IsProperExtendedRealFunction g := hproblem.g_proper letI : Fact (LowerSemicontinuous g) := ⟨hproblem.g_closed⟩ letI : Fact (is_convex_function g) := ⟨hproblem.g_convex⟩ vfista_y f g x0 Lf σ theorem vfista_objective_gap_le_geometric (hstrong : StrongConvexOn Set.univ (σ : ℝ) f) (hxStar : xStar ∈ XStar) (k : ℕ) : F (xv k) - (FOpt : EReal) ≤ (((1 - 1 / Real.sqrt κ) ^ k : ℝ) : EReal) * ((F x0 - (FOpt : EReal)) + ((((σ : ℝ) / 2) * ‖x0 - xStar‖ ^ (2 : ℕ) : ℝ) : EReal))

Definition 10.43

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 10.43: a function h : E → ℝ is (α, β)-smoothable if for every μ > 0 there exists a 1 / μ-smooth approximation of h with parameters (α, β). This is the textbook positive-parameter view of is_smoothable_nonneg.

universe u open PosReal variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] abbrev is_smoothable (h : E → ℝ) (α β : PosReal) : Prop := is_smoothable_nonneg h (toNNReal α) (toNNReal β) -- Proof sketch: for each `ε > 0`, choose the smoothing parameter `μ = ε / (β + 1)`. The -- approximation inequalities and convexity of `hμ` yield the Jensen inequality for `h` up to the -- additive error `β μ < ε`; then remove `ε` via `le_of_forall_pos_le_add`.

Example 10.44

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

Example 10.44: on any proper real inner-product space, hence in particular on every finite-dimensional Euclidean space ℝ^n, the norm is (1, 1)-smoothable, and for each μ > 0 the function x ↦ √(‖x‖² + μ²) - μ gives a 1 / μ-smooth approximation.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] open scoped BigOperators open WithLp theorem norm_is_one_one_smoothable : is_smoothable (fun x : E ↦ ‖x‖) 1 1

Example 10.45

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

Example 10.45: for n > 0, the shifted log-sum-exp function gives a 1 / μ-smooth approximation of the coordinatewise maximum on ℝ^n with nonnegative error parameter log n.

open scoped BigOperators variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem coordinatewise_max_shifted_log_sum_exp_is_smooth_approximation_nonneg (hn : 0 < n) (μ : PosReal) : IsSmoothApproximationNonneg (fun x : E ↦ coordinatewiseMax x) (shifted_log_sum_exp_smoothing μ : E → ℝ) 1 (log_cardinality_nonneg hn) μ

Theorem 10.46

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 10.46 (1): a nonnegative linear combination of two 1 / μ-smooth approximations is a 1 / μ-smooth approximation of the corresponding nonnegative linear combination, with parameters obtained by the same linear combination.

universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [NormedAddCommGroup V] [NormedSpace ℝ V] namespace IsSmoothApproximationNonneg theorem nonneg_weighted_sum {h1 h1μ h2 h2μ : E → ℝ} {α1 β1 α2 β2 : NNReal} {μ : PosReal} (hh1 : IsSmoothApproximationNonneg h1 h1μ α1 β1 μ) (hh2 : IsSmoothApproximationNonneg h2 h2μ α2 β2 μ) (gamma1 gamma2 : NNReal) : IsSmoothApproximationNonneg (fun x ↦ (gamma1 : ℝ) * h1 x + (gamma2 : ℝ) * h2 x) (fun x ↦ (gamma1 : ℝ) * h1μ x + (gamma2 : ℝ) * h2μ x) (gamma1 * α1 + gamma2 * α2) (gamma1 * β1 + gamma2 * β2) μ

Corollary 10.47

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

Corollary 10.47 (1): part (a). A nonnegative linear combination of two smoothable convex functions is nonnegatively smoothable, with parameters obtained by the same linear combination.

universe u v variable {E : Type u} {V : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [NormedAddCommGroup V] [NormedSpace ℝ V] theorem weighted_sum_is_smoothable_nonneg {h1 h2 : E → ℝ} {alpha1 beta1 alpha2 beta2 : PosReal} (gamma1 gamma2 : NNReal) (hh1 : is_smoothable h1 alpha1 beta1) (hh2 : is_smoothable h2 alpha2 beta2) : is_smoothable_nonneg (fun x ↦ (gamma1 : ℝ) * h1 x + (gamma2 : ℝ) * h2 x) (gamma1 * PosReal.toNNReal alpha1 + gamma2 * PosReal.toNNReal alpha2) (gamma1 * PosReal.toNNReal beta1 + gamma2 * PosReal.toNNReal beta2)

Example 10.48

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

Example 10.48: for a continuous linear map into a proper real inner-product space, hence in particular for matrices between finite-dimensional Euclidean spaces, the function x ↦ √(‖A x + b‖² + μ²) - μ is a 1 / μ-smooth approximation of x ↦ ‖A x + b‖ with parameters (‖A‖², 1).

universe u v variable {E : Type u} {F : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [NormedAddCommGroup F] [InnerProductSpace ℝ F] [ProperSpace F] -- Proof sketch: convert the canonical norm smoothing witness from Example 10.44 to the -- nonnegative-parameter owner and then apply the source-facing affine-precomposition bridge -- `IsSmoothApproximationNonneg.precompose_linearMap_add` from Theorem 10.46. theorem affine_norm_smooth_approximation_is_smooth_approximation (A : E →L[ℝ] F) (b : F) (μ : PosReal) : IsSmoothApproximationNonneg (affine_norm A b) (affine_norm_smooth_approximation A b μ) (‖A‖₊ ^ (2 : ℕ)) 1 μ

Example 10.49

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

Example 10.49: for a piecewise affine maximum q(x) = max_i ((A x)_i + b_i), the log-sum-exp function q_μ is a 1 / μ-smooth approximation with parameters (‖A‖₂,₂², log m).

open scoped BigOperators open WithLp (ofLp) variable {m n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "F" => EuclideanSpace ℝ (Fin m) theorem piecewise_affine_max_smoothing_is_smooth_approximation (hm : 0 < m) (A : Matrix (Fin m) (Fin n) ℝ) (b : F) (μ : PosReal) : IsSmoothApproximationNonneg (piecewise_affine_max A b) (piecewise_affine_max_smoothing A b μ) (‖(Matrix.toEuclideanLin A).toContinuousLinearMap‖₊ ^ (2 : ℕ)) (log_cardinality_nonneg hm) μ

Example 10.50

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

Example 10.50 (1): the shifted two-term log-sum-exp smoothing of |x| is a 1 / μ-smooth approximation with parameters (1, log 2), encoded by the canonical chapter owner log_cardinality_posreal at n = 2.

open WithLp (toLp) local notation "E₂" => EuclideanSpace ℝ (Fin 2) theorem absolute_value_log_sum_exp_smoothing_is_smooth_approximation (μ : PosReal) : IsSmoothApproximation (abs : ℝ → ℝ) (absolute_value_log_sum_exp_smoothing μ) 1 (log_cardinality_posreal (show 1 < 2 by decide)) μ

Theorem 10.51

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 10.51: if a real-valued convex function h is globally ℓ_h-Lipschitz, then for every μ > 0 its real-valued Moreau envelope is a 1 / μ-smooth approximation of h with nonnegative parameters (1, ℓ_h^2 / 2).

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] recall moreau_envelope_real_is_smooth_approximation

Theorem 10.51.1

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

Source header · Attribution source

Theorem 10.51: if a real-valued convex function h is globally ℓ_h-Lipschitz, then for every μ > 0 its real-valued Moreau envelope is a 1 / μ-smooth approximation of h with nonnegative parameters (1, ℓ_h^2 / 2).

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] -- Proof sketch: lift `h` canonically to `f := h.toEReal`. Chapter 6 already provides convexity -- and `(1 / μ)`-smoothness of `x ↦ (M[μ, f] x).toReal`. The lower bound comes from evaluating the -- Moreau infimum at `u = x`. For the upper bound, choose the canonical proximal point `u` of the -- scaled lift `μ f` at `x`; the Moreau value then equals `h u + ‖x - u‖² / (2 μ)`, and the -- global Lipschitz bound gives `h x ≤ h u + ℓ_h ‖x - u‖`. Optimizing the scalar quadratic -- `-t² / (2 μ) + ℓ_h t` yields the error term `(ℓ_h² / 2) μ`. theorem moreau_envelope_real_is_smooth_approximation (h : E → ℝ) (hconv : ConvexOn ℝ Set.univ h) (ℓh : NNReal) (hlip : LipschitzWith ℓh h) (μ : PosReal) : IsSmoothApproximationNonneg h (fun x ↦ (M[μ, h.toEReal] x).toReal) 1 (ℓh ^ 2 / 2) μ

Corollary 10.52

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

Corollary 10.52: if h : ℝ → ℝ is convex and globally ℓ_h-Lipschitz, then h is nonnegatively (1, ℓ_h^2 / 2)-smoothable. The nonnegative owner matches the textbook parameter ℓ_h^2 / 2, which need not be strictly positive.

theorem real_convex_lipschitz_is_one_lipschitz_sq_div_two_smoothable_nonneg (h : ℝ → ℝ) (hconv : ConvexOn ℝ Set.univ h) (ℓh : NNReal) (hlip : LipschitzWith ℓh h) : is_smoothable_nonneg h 1 (ℓh ^ (2 : ℕ) / 2)

Corollary 10.52.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

Corollary 10.52: on a real inner-product proper space, a convex real-valued function with global Lipschitz constant ℓ_h is nonnegatively (1, ℓ_h^2 / 2)-smoothable.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] theorem convex_lipschitz_is_one_lipschitz_sq_div_two_smoothable_nonneg (h : E → ℝ) (hconv : ConvexOn ℝ Set.univ h) (ℓh : NNReal) (hlip : LipschitzWith ℓh h) : is_smoothable_nonneg h 1 (ℓh ^ (2 : ℕ) / 2)

Definition 10.53

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 10.53 is bridge/view. Domain sampling in the local smoothing API gives: - H[μ] from Definition 6.8 as the source-facing owner for the Huber smoothing; - M[μ, f] from Definition 6.7 as the canonical Moreau-envelope owner; - moreau_envelope_norm_penalty_toReal_eq_huber_function from Example 6.54 as the existing bridge from the norm envelope to the Huber owner. The primitive data already live upstream. The only local content is the Euclidean specialization to EuclideanSpace ℝ (Fin n) together with the textbook reading of x ↦ ‖x‖ as norm_penalty 1. The explicit piecewise formula is therefore derived API via huber_function_apply, and the Chapter 10 item itself is only the Euclidean specialization of the existing Chapter 6 bridge, so the main entry here should be direct reuse of that theorem rather than a parallel local alias.

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) recall huber_function

Example 10.53

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

Example 10.53 is source-facing in the Chapter 10 smoothing API. Domain sampling identifies: - H[μ] from Definition 6.8 as the source-facing Huber owner; - moreau_envelope_real_is_smooth_approximation from Theorem 10.51 as the core/canonical Moreau-envelope smoothing theorem for convex Lipschitz functions; - moreau_envelope_norm_penalty_toReal_eq_huber_function from Example 6.54 as the bridge/view identifying the norm envelope with the Huber owner. The primitive data are only the ambient norm and the existing Huber owner. The Euclidean ℝ^n reading is a specialization of this intrinsic real inner-product-space statement, so the main public theorem is stated at that owner level rather than through a separate Euclidean bridge.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] recall huber_function -- Proof sketch: apply the general Moreau-envelope smooth-approximation theorem to `x ↦ ‖x‖`, -- using `convexOn_univ_norm` and `lipschitzWith_one_norm`, then rewrite the resulting Moreau -- envelope by the canonical Huber bridge `moreau_envelope_norm_penalty_toReal_eq_huber_function`.

Definition 10.54

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 10.54: for h(x) = ‖x‖₁ on ℝ^n and any μ > 0, the real-valued Moreau envelope of h is the sum of the scalar Huber values on the coordinates: M_h^μ(x) = ∑ i, H_μ(x_i).

open scoped BigOperators variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) #check (moreau_envelope_l1_sum_toReal_eq_sum_huber : ∀ μ : PosReal, ∀ x : E, (M[μ, fun y : E ↦ (‖y‖₁ : EReal)] x).toReal = ∑ i, H[μ] (x i))

Example 10.54

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

Example 10.54 is bridge/view in the Chapter 10 smoothing API. Domain sampling in this owner family identifies - M[μ, f] as the core Moreau-envelope owner; - ‖·‖₁ as the source-facing Euclidean ℓ¹ penalty owner; - H[μ] as the source-facing scalar Huber owner; and - moreau_envelope_l1_sum_toReal_eq_sum_huber from Example 6.59 as the owner-level bridge from the real-valued ℓ¹ envelope to the coordinatewise Huber sum. The primitive data already live upstream, and the displayed sum formula is derived API from that bridge. This file therefore reuses that canonical owner-level bridge directly instead of introducing a parallel Chapter 10 theorem with the same interface.

recall moreau_envelope_l1_sum_toReal_eq_sum_huber

Definition 10.55

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 10.55: the S-FISTA optimization model with objective H(x) = f(x) + h(x) + g(x) is the Chapter 10 composite-model owner used twice, written on the source-facing theorem surface as H[f, h, g].

universe u v variable {E : Type u} {α : Type v} [Add α] variable (f h g : E → α) @[inherit_doc composite_model_objective] notation "H[" f ", " h ", " g "]" => composite_model_objective (composite_model_objective f h) g #check H[f, h, g]

Example 10.55

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

Example 10.55: among the three constructed 1 / μ-smooth approximations of |x|, the Huber function has the smallest uniform approximation-error parameter.

theorem absolute_value_huber_smoothing_has_tightest_uniform_error_bound (μ : PosReal) : IsLeast {β : NNReal | IsSmoothApproximationNonneg (abs : ℝ → ℝ) (norm_smooth_approximation μ) 1 β μ ∨ IsSmoothApproximationNonneg (abs : ℝ → ℝ) (absolute_value_log_sum_exp_smoothing μ) 1 β μ ∨ IsSmoothApproximationNonneg (abs : ℝ → ℝ) (H[μ] : ℝ → ℝ) 1 β μ} ((1 : NNReal) / 2)

Proposition 10.56

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 10.56: the S-FISTA assumptions are organized into five atomic clauses. Clause (A): f is convex and globally L_f-smooth. Clause (B): h is (α, β)-smoothable. Clause (C): g : E → (-∞, ∞] is proper, closed, convex. Clause (D): each real sublevel set of H(x) = f(x) + h(x) + g(x) is bounded. Clause (E): XStar = X^* is the nonempty minimizer set of H, with optimal value HOpt = H_opt.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsSFISTAProblem (f h : E → ℝ) (g : E → EReal) (XStar : outParam (Set E)) (HOpt : outParam ℝ) (Lf : NNReal) (α β : PosReal) : Prop where f_convex : ConvexOn ℝ Set.univ f f_smooth : is_l_smooth_on f Set.univ Lf h_smoothable : is_smoothable h α β g_proper : IsProperExtendedRealFunction g g_closed : LowerSemicontinuous g g_convex : is_convex_function g bounded_real_sublevelSets (a : ℝ) : Bornology.IsBounded {x | H[f.toEReal, h.toEReal, g] x ≤ (a : EReal)} optimal_set_eq : XStar = unconstrained_problem_solutions H[f.toEReal, h.toEReal, g] optimal_set_nonempty : XStar.Nonempty optimal_value_isGLB : IsGLB (Set.range H[f.toEReal, h.toEReal, g]) (HOpt : EReal)

Definition 10.57

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 10.57 is a bridge/view item. For a chosen smoothing parameter μ > 0 and a chosen 1 / μ-smooth approximation h_μ of h with parameters (α, β), the smoothed problem (10.65) keeps the same Chapter 10 owner composite_model_objective, applied twice after coercing the real-valued smooth terms to EReal. Domain sampling identifies the owner abstraction and the primitive/derived split: - Function.toEReal from Chapter 9 is the canonical coercion from real-valued smooth terms to the extended-real codomain; - composite_model_objective from Definition 10.2 is the Chapter 10 owner for composite objectives; - the explicit three-term evaluation and minimization rewrites are definitional consequences of the nested Chapter 10 owner from Definition 10.55, so this file should not introduce a second named specialization. Primitive data here are only the three objective terms f, h_μ, and g; the source item adds no new owner-level construction beyond the existing composite objective.

universe u recall Function.toEReal

Theorem 10.57

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 10.57: assuming Proposition 10.56, if hμ is the smoothing used by S-FISTA with μ = (√(α / β) * ε) / (√(αβ) + √(αβ + L_f ε)) and if x⁰ ∈ dom(H), then there exists a radius R_{H(x⁰) + ε / 2} controlling the real sublevel set at level H(x⁰) + ε / 2, and for every iteration index k, if 2 √(2 α β Γ) / ε + √(2 L_f Γ) / √ε ≤ k with Γ = (R_{H(x⁰) + ε / 2} + ‖x⁰‖)^2, then the original objective gap at the kth S-FISTA iterate is at most ε.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable {f h hμ : E → ℝ} {g : E → EReal} {XStar : Set E} {HOpt : ℝ} variable {Lf : NNReal} {α β : PosReal} variable (ε : PosReal) (x0 : E) local notation "μ" => s_fista_complexity_smoothing_parameter ε α β Lf local notation "Hsf" => H[f.toEReal, h.toEReal, g] theorem s_fista_objective_gap_le_epsilon_of_iteration_bound [problem : IsSFISTAProblem f h g XStar HOpt Lf α β] (hhμ : IsSmoothApproximation h hμ α β μ) (hx0 : x0 ∈ effective_domain Hsf) : ∃ Rlevel : PosReal, (∀ ⦃x : E⦄, Hsf x ≤ Hsf x0 + (((ε : ℝ) / 2 : ℝ) : EReal) → ‖x‖ ≤ (Rlevel : ℝ)) ∧ ∀ k : ℕ, 2 * Real.sqrt (2 * (α : ℝ) * (β : ℝ) * s_fista_complexity_gamma Rlevel x0) / (ε : ℝ) + Real.sqrt (2 * (Lf : ℝ) * s_fista_complexity_gamma Rlevel x0) / Real.sqrt (ε : ℝ) ≤ (k : ℝ) → Hsf (problem.sFistaX hμ μ x0 k) - (HOpt : EReal) ≤ ((ε : ℝ) : EReal)

Proposition 10.58

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 10.58: at each iteration k, the S-FISTA extrapolated point satisfies the update y^(k+1) = x^(k+1) + ((t_k - 1) / t_(k+1)) (x^(k+1) - x^k).

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (f hμ : E → ℝ) (g : E → EReal) [IsProperExtendedRealFunction g] variable [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] variable (Lf : NNReal) (α μ : PosReal) (x0 : E) theorem s_fista_y_succ (k : ℕ) : s_fista_y f hμ g Lf α μ x0 (k + 1) = s_fista_x f hμ g Lf α μ x0 (k + 1) + ((s_fista_t f hμ g Lf α μ x0 k - 1) / s_fista_t f hμ g Lf α μ x0 (k + 1)) • (s_fista_x f hμ g Lf α μ x0 (k + 1) - s_fista_x f hμ g Lf α μ x0 k)

Algorithm 10.59

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 10.59: for a constrained convex Lipschitz problem min {h(x) | x ∈ C}, an accuracy parameter ε > 0, and an initial feasible point x^0 ∈ C, the constrained S-FISTA state sequence is expressed through the chapter's canonical FISTA owner FISTAState E, representing (x^(k-1), x^k, t_k). It starts from x^(-1) = x^0, t_0 = 1, uses the source parameters μ = ε / ℓ_h² and L̃ = ℓ_h² / ε, and recursively applies the projected-proximal update x^(k+1) = P_C (prox_(μ h) (y^k)), where y^k is the associated FISTA extrapolated point.

universe u open scoped ProximalPoint variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (h : E → ℝ) (C : Set E) (ℓh : PosReal) variable [problem : IsConvexLipschitzConstrainedMinimizationProblem h C (PosReal.toNNReal ℓh)] def constrained_s_fista (ε : PosReal) (x0 : C) : ℕ → FISTAState E

Definition 10.59

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 10.59: the constrained problem min {h(x) | x ∈ C} has a nonempty closed convex feasible set C, and its objective h : E → ℝ is globally convex and ℓ_h-Lipschitz.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsConvexLipschitzConstrainedMinimizationProblem (h : E → ℝ) (C : Set E) (ℓh : NNReal) : Prop where constraint_nonempty : C.Nonempty constraint_closed : IsClosed C constraint_convex : Convex ℝ C objective_convex : ConvexOn ℝ Set.univ h objective_lipschitz : LipschitzWith ℓh h

Proposition 10.59

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 10.59: for every nonzero vector a in a real inner-product space, the Chapter 10 norming-vector set Λ[toDualMap ℝ E a] is the singleton containing the normalized vector ‖a‖⁻¹ • a.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. universe u open InnerProductSpace (toDualMap) variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem primalCounterparts_toDualMap_eq_singleton_normalized {a : E} (ha : a ≠ 0) : Λ[toDualMap ℝ E a] = ({‖a‖⁻¹ • a} : Set E)

Algorithm 10.60

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 10.60. For a constrained convex Lipschitz problem min { h(x) | x ∈ C }, an accuracy parameter ε > 0, and an initial feasible point x^0 ∈ C, the source-facing projected S-FISTA recursion is the state sequence whose internal companion recursion stores both the state (x^(k-1), x^k, t_k) and the textbook extrapolated point y^k. It starts from y^0 = x^0, t_0 = 1, uses the source parameters μ = ε / ell_h^2 and L̃ = ell_h^2 / ε, and evolves by x^(k+1) = P_C (prox_(μ h) (y^k)), t_(k+1) = (1 + √(1 + 4 t_k^2)) / 2, and y^(k+1) = x^(k+1) + ((t_k - 1) / t_(k+1)) • (x^(k+1) - x^k).

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E] variable (h : E → ℝ) (C : Set E) (ell_h eps : PosReal) (x0 : C) (k : Nat) variable [IsConvexLipschitzConstrainedMinimizationProblem h C (PosReal.toNNReal ell_h)] def constrained_s_fista_textbook (eps : PosReal) (x0 : C) : ℕ → FISTAState E := fun k ↦ (constrainedSFistaTextbookStateAndY h C ell_h eps x0 k).1

Definition 10.60

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 10.60: the least-squares analysis-ℓ¹ objective is the specialized Chapter 10 three-term owner H[least_squares_loss A b, analysis_l1_penalty D, ambient_l1_regularizer n lam].

variable {m n p : ℕ} local notation "X" => EuclideanSpace ℝ (Fin n) variable (A : Matrix (Fin m) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin m)) (D : Matrix (Fin p) (Fin n) ℝ) (lam : ℝ) #check H[least_squares_loss A b, analysis_l1_penalty D, ambient_l1_regularizer n lam]

Proposition 10.60

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 10.60: for a nonzero ℓ∞ coefficient vector a, the norming-functional set Λ[LinearMap.toContinuousLinearMap (lpPairingDual 1 (ofLp a))] is exactly the set of signed active-coordinate convex combinations ∑_{i ∈ I(a)} λ_i sign(a_i) e_i, expressed here as the image of activeCoordinateFace (fun i ↦ |a i|).

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. open WithLp (toLp ofLp) open InnerProductSpace (toDualMap) variable {ι : Type*} [Fintype ι] local notation "E" => WithLp 1 (ι → ℝ) local notation "E₂" => EuclideanSpace ℝ ι local notation "E*" => WithLp (⊤ : ENNReal) (ι → ℝ) local notation "coordToL1" => (fun z : E₂ ↦ toLp (1 : ENNReal) (ofLp z)) theorem primalCounterparts_lpPairingDual_one_eq_signed_activeCoordinateFace (a : E*) (ha : a ≠ 0) : Λ[LinearMap.toContinuousLinearMap (lpPairingDual (1 : ENNReal) (ofLp a))] = (fun coeff : ι → ℝ ↦ toLp 1 (fun i ↦ coeff i * Real.sign (a i))) '' activeCoordinateFace (fun i ↦ |a i|)

Algorithm 10.61

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 10.61: given an initial point x^0 = x0, a positive curvature sequence L_k, and a rule counterpart selecting a primal counterpart of the current derivative, the non-Euclidean gradient method generates iterates by x^(k+1) = x^k - (‖f'(x^k)‖_* / L_k) f'(x^k)^†.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. universe u open scoped DualNorm variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] def non_euclidean_gradient_method (f : E → ℝ) (counterpart : ℕ → E → E) (L : ℕ → PosReal) (x0 : E) : ℕ → E

Definition 10.61

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 10.61: the unconstrained problem min {f(x) | x ∈ E} is the Chapter 8 owner unconstrained_problem_solutions f.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (f : E → ℝ) (Lf : NNReal) #check unconstrained_problem_solutions f

Lemma 10.61

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 10.61 (1): if a ≠ 0, every primal counterpart a† ∈ Λ_a has norm 1.

universe u open Metric local notation "Λ[" a "]" => primalCounterparts a variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem norm_eq_one_of_mem_primalCounterparts {a : E →L[ℝ] ℝ} (ha : a ≠ 0) {aDagger : E} (haDagger : aDagger ∈ Λ[a]) : ‖aDagger‖ = 1

Proposition 10.61

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 10.61: after unpacking the transported Chapter 3 owner euclideanSubdifferentialAt, the source set Λ_a is the coordinatewise sign cube {z : ℝ^n | z_i = sgn(a_i) on the nonzero coordinates of a, and |z_j| ≤ 1 on the zero coordinates}. In the textbook nonzero case, this is the usual description of ∂ h(a) for h(x) = ‖x‖₁.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. open WithLp (ofLp toLp) open scoped BigOperators variable {n : ℕ} local notation "E₂" => EuclideanSpace ℝ (Fin n) local notation "E" => WithLp (⊤ : ENNReal) (Fin n → ℝ) local notation "E*" => WithLp (1 : ENNReal) (Fin n → ℝ) local notation "coordToLinf" => (fun z : E₂ ↦ toLp (⊤ : ENNReal) (ofLp z)) theorem primalCounterparts_lpPairingDual_top_eq_coordinatewise_sign_cube (a : E*) : Λ[LinearMap.toContinuousLinearMap (lpPairingDual (⊤ : ENNReal) (ofLp a))] = { z : E | (∀ i, a i ≠ 0 → z i = Real.sign (a i)) ∧ ∀ i, a i = 0 → |z i| ≤ 1 }

Algorithm 10.62

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 10.62: given parameters s > 0, γ ∈ (0,1), and η > 1, an index i_k is a valid output of backtracking procedure B4 at a current iterate x^k with chosen primal counterpart xDagger = f'(x^k)^† when f is differentiable at x^k, the chosen direction belongs to Λ_{f'(x^k)}, the trial curvature s η^{i_k} satisfies f(x^k) - f(x^k - (‖f'(x^k)‖_* / (s η^{i_k})) • xDagger) ≥ (γ / (s η^{i_k})) ‖f'(x^k)‖_*², and every earlier geometric trial fails this inequality.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. universe u open scoped DualNorm variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class is_backtracking_procedure_B4_index (f : E → ℝ) (s : PosReal) (γ : ProximalGradientBacktrackingDecreaseFraction) (η : ProximalGradientBacktrackingGrowthFactor) (x xDagger : E) (i : ℕ) : Prop where differentiableAt : DifferentiableAt ℝ f x counterpart_mem : xDagger ∈ Λ[fderiv ℝ f x] accepts : non_euclidean_gradient_backtracking_B4_accepts f γ (proximal_gradient_backtracking_trial_stepsize s η i) x xDagger minimal (j : ℕ) (hj : j < i) : ¬ non_euclidean_gradient_backtracking_B4_accepts f γ (proximal_gradient_backtracking_trial_stepsize s η j) x xDagger

Definition 10.62

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 10.62: given an initial point x0 and stepsizes t_k, the gradient method for a differentiable objective f is the recursive sequence satisfying x^(k+1) = x^k - t_k • ∇ f(x^k).

recall gradient_method

Proposition 10.62

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 10.62: under the hypotheses of Theorem 10.71, if the stepsizes are chosen by exact line search and L_f > 0, then every positive iterate satisfies f(x^k) - f_opt ≤ 2 L_f R_f(x^0)^2 / k, where R_f(x^0) is represented here by the radius Rα for the initial sublevel set f(x) ≤ f(x^0).

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → ℝ} {XStar : Set E} {fOpt : ℝ} {Lf : NNReal} variable [hproblem : IsFastProximalGradientProblem f (0 : E → EReal) XStar fOpt Lf] variable {counterpart : ℕ → E → E} {L : ℕ → PosReal} {x0 : E} {Rα : PosReal} local notation "x" => non_euclidean_gradient_method f counterpart L x0 local notation "xDagger" => non_euclidean_gradient_method_counterpart_sequence f counterpart L x0 theorem non_euclidean_gradient_objective_gap_le_two_Lf_mul_sublevel_radius_sq_div_k (hRα : ∀ ⦃y : E⦄, f y ≤ f x0 → infDist y XStar ≤ Rα) (hadm : non_euclidean_gradient_method_is_admissible f counterpart L x0) (hLf : 0 < (Lf : ℝ)) (hsearch : uses_non_euclidean_exact_line_search_stepsize_rule f x L xDagger) (k : ℕ) (hk : 1 ≤ k) : f (x k) - fOpt ≤ 2 * (Lf : ℝ) * (Rα : ℝ) ^ 2 / (k : ℝ)

Algorithm 10.63

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 10.63: in Euclidean coordinates, the canonical owner trajectory satisfies the textbook update x^(k+1) = x^k - (‖∇ f(x^k)‖_∞ / L_k) sgn ((∇ f(x^k))_(i_k)) e_(i_k), transported back to the primal ℓ₁ model by coordToL1.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. open WithLp (ofLp toLp) open scoped Gradient variable {ι : Type*} [Fintype ι] local notation "E" => WithLp 1 (ι → ℝ) local notation "E₂" => EuclideanSpace ℝ ι local notation "coordToL1" => (fun z : E₂ ↦ toLp (1 : ENNReal) (ofLp z)) local notation "coordToL2" => (fun x : E ↦ toLp 2 (ofLp x)) local notation "e[" i "]" => (EuclideanSpace.basisFun ι ℝ i : E₂) variable (f : EuclideanSpace ℝ ι → ℝ) (iSel : ℕ → EuclideanSpace ℝ ι → ι) (L : ℕ → PosReal) (x0 : EuclideanSpace ℝ ι) local notation "f₁" => fun x : E ↦ f (coordToL2 x) local notation "counterpart" => l1_non_euclidean_gradient_counterpart_rule f iSel local notation "x[" k "]" => non_euclidean_gradient_method f₁ counterpart L (coordToL1 x0) k local notation "x₂[" k "]" => coordToL2 (x[k]) theorem non_euclidean_gradient_method_update_l1_counterpart_rule (k : ℕ) : x[k + 1] = coordToL1 (x₂[k] - (‖(∇ f x₂[k]).ofLp‖ / (L k : ℝ)) • (Real.sign ((∇ f x₂[k]) (iSel k x₂[k])) • e[iSel k x₂[k]]))

Definition 10.63

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 10.63 is recall-only: the source-faithful arg max characterization of the owner set Λ[a] already lives in the owner file Lemma_10_61 as mem_Λ_iff.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] -- Semantic search note: `lean_leansearch` was unavailable in this environment, so the owner/API -- choice was verified against `Lemma_10_61` and nearby Chapter 10 files. recall mem_Λ_iff

Algorithm 10.64

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 10.64: given an initialization x^0 = x0, a linear map A, an offset b, and a positive parameter L_f^{(2)}, Algorithm G2 generates iterates by the recursion x^(k+1) = x^k - (1 / L_f^{(2)}) (A x^k + b) in the ambient real module.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] def affine_gradient_method (A : E →ₗ[ℝ] E) (b : E) (Lf2 : PosReal) (x0 : E) : ℕ → E

Definition 10.64

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 10.64, pointwise bridge form: a primal vector x is a source counterpart x ∈ Λ[a] exactly when its canonical bidual image belongs to the norm subdifferential at a.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] @[simp] theorem mem_primalCounterparts_iff_mem_subdifferentialAt_norm (a : StrongDual ℝ E) {x : E} : x ∈ Λ[a] ↔ NormedSpace.inclusionInDoubleDual ℝ E x ∈ subdifferentialAt (fun b : StrongDual ℝ E ↦ ‖b‖) a

Algorithm 10.65

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 10.65: given row vectors A_i, affine offsets b_i, a positive parameter L_f^(1), an initial point x^0 = x0, and a rule selecting an index i_k, Algorithm G1 generates the iterate sequence by keeping all coordinates except the selected one fixed and updating x_(i_k)^(k+1) = x_(i_k)^k - (1 / L_f^(1)) (A_(i_k) x^k + b_(i_k)).

variable {n : ℕ} local notation "E" => Fin n → ℝ def max_row_residual_coordinate_method (A : Fin n → E) (b : Fin n → ℝ) (Lf1 : PosReal) (i : ℕ → E → Fin n) (x0 : E) : ℕ → E

Definition 10.65

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 10.65: clauses (A)-(C) mean that f : E → ℝ is convex and globally L_f-smooth, XStar = X^* is the nonempty optimal set of min_x f(x) with optimal value fOpt = f_opt, and for every α > 0 there is R_α > 0 such that every point x with f x ≤ α lies within distance at most R_α of the optimal set XStar. The convexity, smoothness, optimal-set, and optimal-value clauses are inherited from the canonical Chapter 10 owner IsFastProximalGradientProblem for the zero regularizer.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsSublevelDistanceBoundedSmoothConvexMinimizationProblem (f : E → ℝ) (XStar : outParam (Set E)) (fOpt : outParam ℝ) (Lf : outParam NNReal) : Prop extends IsFastProximalGradientProblem f (0 : E → EReal) XStar fOpt Lf where bounded_sublevel_distance_to_optimal_set (α : PosReal) : ∃ Rα : PosReal, ∀ ⦃x : E⦄, f x ≤ α → infDist x XStar ≤ Rα

Lemma 10.65

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 10.65: if f is globally L_f-smooth and xDagger ∈ Λ_{f'(x)}, then the non-Euclidean trial point x - (‖f'(x)‖_* / L) • xDagger satisfies the sufficient-decrease inequality f(x - (‖f'(x)‖_* / L) • xDagger) ≤ f(x) - ((L - L_f / 2) / L^2) ‖f'(x)‖_*^2.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. universe u open scoped DualNorm variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem non_euclidean_gradient_method_sufficient_decrease {f : E → ℝ} {Lf : NNReal} (hf : is_l_smooth_on f Set.univ Lf) (x : E) (L : PosReal) (xDagger : E) (hDagger : xDagger ∈ Λ[fderiv ℝ f x]) : f (x - (‖fderiv ℝ f x‖_* / (L : ℝ)) • xDagger) ≤ f x - (((L : ℝ) - (Lf : ℝ) / 2) / (L : ℝ) ^ 2) * ‖fderiv ℝ f x‖_* ^ 2

Algorithm 10.66

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 10.66: a point x^(k+1) is a valid proximal-gradient update from x^k with curvature parameter L_k exactly when it globally minimizes the linearized quadratic model x ↦ f(x^k) + ⟪∇ f(x^k), x - x^k⟫ + g(x) + (L_k / 2) ‖x - x^k‖² whenever f is differentiable at x^k in the Chapter 3 sense, so the displayed gradient is the genuine textbook gradient there.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem mem_proximal_gradient_step_iff_isMinOn_curvature_model {f g : E → EReal} {xk xNext : E} {Lk : PosReal} (hfxk : is_differentiable_at f xk) : xNext ∈ proximal_gradient_step f g xk Lk ↔ IsMinOn (proximal_gradient_curvature_model f g xk Lk) Set.univ xNext

Definition 10.66

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 10.66: the composite optimization model min_{x ∈ E} {F(x) ≡ f(x) + g(x)} in a normed space whose norm is not assumed Euclidean is the same Chapter 10 objective owner composite_model_objective.

recall composite_model_objective

Lemma 10.66

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 10.66 (1), constant-stepsize branch: if every L_k = barL for some barL ∈ (L_f / 2, ∞), then each non-Euclidean gradient step satisfies the sufficient-decrease estimate with coefficient ((barL : ℝ) - L_f / 2) / barL^2.

local notation "Λ[" a "]" => primalCounterparts a -- Declarations for this item will be appended below by the statement pipeline. universe u open scoped DualNorm variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → ℝ} {Lf : NNReal} variable (hf : is_l_smooth_on f Set.univ Lf) variable {x : ℕ → E} {L : ℕ → PosReal} {xDagger : ℕ → E} variable (hstep : ∀ k : ℕ, x (k + 1) = x k - (‖fderiv ℝ f (x k)‖_* / (L k : ℝ)) • xDagger k) variable (hDagger : ∀ k : ℕ, xDagger k ∈ Λ[fderiv ℝ f (x k)]) theorem non_euclidean_gradient_constant_stepsize_sufficient_decrease (hf : is_l_smooth_on f Set.univ Lf) (hstep : ∀ k : ℕ, x (k + 1) = x k - (‖fderiv ℝ f (x k)‖_* / (L k : ℝ)) • xDagger k) (hDagger : ∀ k : ℕ, xDagger k ∈ Λ[fderiv ℝ f (x k)]) (barL : ProximalGradientConstantStepsizeParameter Lf) (hL : L = Function.const ℕ (barL : PosReal)) (k : ℕ) : f (x k) - f (x (k + 1)) ≥ (((barL : ℝ) - (Lf : ℝ) / 2) / ((barL : ℝ) ^ (2 : ℕ))) * ‖fderiv ℝ f (x k)‖_* ^ (2 : ℕ)

Algorithm 10.67

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 10.67: a point x⁺ is an admissible next iterate of the non-Euclidean proximal-gradient method from x^k with curvature parameter L_k when f is differentiable at x^k in the Chapter 3 sense, x⁺ lies in the finite-valued domain of ω, and x⁺ minimizes the Chapter 9 Mirror-C update objective specialized to the functional f'(x^k) and reciprocal curvature (Lk : ℝ)⁻¹ over that finite-valued domain.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class non_euclidean_proximal_gradient_step (f g ω : E → EReal) (xk : E) (Lk : PosReal) (xNext : E) : Prop where differentiable : is_differentiable_at f xk mem_finite_domain : xNext ∈ finite_domain ω minimizer : IsMinOn (mirror_c_update_objective g ω xk (fderiv ℝ (fun y ↦ (f y).toReal) xk) ((Lk : ℝ)⁻¹)) (finite_domain ω) xNext

Definition 10.67

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 10.67: Assumption 10.77 for the non-Euclidean proximal gradient method means that g : E → (-∞, ∞] is proper, closed, and convex; f : E → (-∞, ∞] is proper, closed, and convex with effective_domain g ⊆ interior (effective_domain f) and (fun x ↦ (f x).toReal) L_f-smooth on interior (effective_domain f); and XStar = X^* is the nonempty optimal solution set of min_x (f x + g x) with optimal value FOpt = F_opt.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsConvexCompositeSmoothMinimizationProblem (f g : E → EReal) (XStar : outParam (Set E)) (FOpt : outParam ℝ) (Lf : NNReal) : Prop where f_ne_bot : ∀ x, f x ≠ ⊥ g_proper : IsProperExtendedRealFunction g f_closed : LowerSemicontinuous f g_closed : LowerSemicontinuous g f_convex : is_convex_function f g_convex : is_convex_function g g_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f) f_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun x ↦ (f x).toReal) (interior (effective_domain f)) Lf optimal_set_eq : XStar = unconstrained_problem_solutions (composite_model_objective f g) optimal_set_nonempty : XStar.Nonempty optimal_value_isGLB : IsGLB (Set.range (composite_model_objective f g)) (FOpt : EReal)

Theorem 10.67

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 10.67 (1): clause (a). If f is globally L_f-smooth and the iterates are generated by the non-Euclidean gradient method with one of the three admissible stepsize rules from Lemma 10.66, then the objective sequence f(x^k) is nonincreasing.

universe u open scoped DualNorm variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → ℝ} {Lf : NNReal} variable {counterpart : ℕ → E → E} {L : ℕ → PosReal} {x0 : E} {M : ℝ} local notation "x" => non_euclidean_gradient_method f counterpart L x0 local notation "xDagger" => non_euclidean_gradient_method_counterpart_sequence f counterpart L x0 variable (hf : is_l_smooth_on f Set.univ Lf) variable (hadm : non_euclidean_gradient_method_is_admissible f counterpart L x0) variable (hstepsize : uses_non_euclidean_gradient_stepsize_rule f Lf x L xDagger M) theorem non_euclidean_gradient_objective_values_antitone (hf : is_l_smooth_on f Set.univ Lf) (hadm : non_euclidean_gradient_method_is_admissible f counterpart L x0) (hstepsize : uses_non_euclidean_gradient_stepsize_rule f Lf x L xDagger M) : Antitone (fun k ↦ f (x k))

Algorithm 10.68

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 10.68: a sequence x^k follows the non-Euclidean proximal-gradient method for the composite objective f + g with mirror map ω and positive curvature parameters L_k when, at every iteration k, the current iterate lies in dom(g) ∩ dom(∂ω) and the next iterate x^(k+1) satisfies the canonical Algorithm 10.67 one-step predicate.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] def is_non_euclidean_proximal_gradient_trajectory (f g ω : E → EReal) (x : ℕ → E) (L : ℕ → PosReal) : Prop := ∀ k : ℕ, x k ∈ effective_domain g ∩ subdifferential_domain ω ∧ non_euclidean_proximal_gradient_step f g ω (x k) (L k) (x (k + 1))

Definition 10.68

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 10.68: Assumption 10.78 for the proximal gradient method is exactly that ω is a Bregman potential on dom(g) = effective_domain g with strong-convexity modulus 1.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {g ω : E → EReal} #check (IsBregmanPotentialOn ω (effective_domain g) (1 : ℝ))

Algorithm 10.69

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 10.69: a non-Euclidean proximal-gradient run uses backtracking procedure B5 with parameters (s, η) when L_{-1} = s and, at every iteration k, the accepted curvature estimate L_k is the first geometric trial L_{k-1} η^{i_k} for which some admissible Algorithm 10.67 step x⁺ from x^k satisfies the quadratic upper-model inequality f(x⁺) ≤ f(x^k) + ⟪∇ f(x^k), x⁺ - x^k⟫ + (L / 2) ‖x⁺ - x^k‖².

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable (f g ω : E → EReal) variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] [IsBregmanPotentialOn ω (effective_domain g) (1 : ℝ)] class UsesNonEuclideanProximalGradientBacktrackingB5Rule (f g ω : E → EReal) (x : ℕ → E) (L : ℕ → PosReal) (s : PosReal) (η : ProximalGradientBacktrackingGrowthFactor) : Prop where existsIndex (k : ℕ) : ∃ i : ℕ, IsBacktrackingProcedureB5Index f g ω (proximal_gradient_backtracking_B2_previous_stepsize s L k) η (x k) i ∧ L k = proximal_gradient_backtracking_trial_stepsize (proximal_gradient_backtracking_B2_previous_stepsize s L k) η i

Definition 10.69

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 10.69: if effective_domain f is convex, effective_domain g ⊆ interior (effective_domain f), (fun y ↦ (f y).toReal) is L_f-smooth on interior (effective_domain f), and the non-Euclidean proximal-gradient trajectory satisfies the canonical constant-or-B5 stepsize owner, then at every iteration k the quadratic upper-model inequality f(x^(k+1)) ≤ f(x^k) + ⟪∇ f(x^k), x^(k+1) - x^k⟫ + (L_k / 2) ‖x^(k+1) - x^k‖² holds.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {f g ω : E → EReal} {Lf : NNReal} variable [IsProperExtendedRealFunction g] [Fact (LowerSemicontinuous g)] [Fact (is_convex_function g)] local notation "constantOrBacktrackingB5StepsizeRule[" hω "; " x "; " L "]" => non_euclidean_proximal_gradient_constant_or_backtracking_B5_stepsize_rule (f := f) (g := g) (ω := ω) (Lf := Lf) hω x L theorem non_euclidean_proximal_gradient_upper_model_of_constant_or_backtracking_B5_rule (hf_effective_domain_convex : Convex ℝ (effective_domain f)) (hg_effective_domain_subset_interior_f_effective_domain : effective_domain g ⊆ interior (effective_domain f)) (hf_toReal_smooth_on_interior_effective_domain : is_l_smooth_on (fun y ↦ (f y).toReal) (interior (effective_domain f)) Lf) (hω : IsBregmanPotentialOn ω (effective_domain g) (1 : ℝ)) {x : ℕ → E} {L : ℕ → PosReal} (htraj : is_non_euclidean_proximal_gradient_trajectory f g ω x L) (hrule : constantOrBacktrackingB5StepsizeRule[hω; x; L]) (k : ℕ) : f (x (k + 1)) ≤ f (x k) + ((inner ℝ (∇ (fun y ↦ (f y).toReal) (x k)) (x (k + 1) - x k) + ((L k : ℝ) / 2) * ‖x (k + 1) - x k‖ ^ (2 : ℕ) : ℝ) : EReal)

Lemma 10.69

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 10.69: if the non-Euclidean gradient iterates satisfy the sublevel-distance bound at level α = f(x^0), then every step obeys the quadratic decrease estimate f(x^k) - f(x^(k+1)) ≥ (M / R_α^2) (f(x^k) - f_opt)^2, where M is the sufficient-decrease constant supplied by the Chapter 10 owner uses_non_euclidean_gradient_stepsize_rule; equivalently, with C = R_α^2 / M, one has f(x^k) - f(x^(k+1)) ≥ (1 / C) (f(x^k) - f_opt)^2.

universe u open Metric open scoped DualNorm variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → ℝ} {XStar : Set E} {fOpt : ℝ} {Lf : NNReal} variable [hproblem : IsFastProximalGradientProblem f (0 : E → EReal) XStar fOpt Lf] variable {counterpart : ℕ → E → E} {L : ℕ → PosReal} {x0 : E} {M : ℝ} {Rα : PosReal} variable {α : ℝ} local notation "xSeq" => non_euclidean_gradient_method f counterpart L x0 local notation "xDaggerSeq" => non_euclidean_gradient_method_counterpart_sequence f counterpart L x0 theorem non_euclidean_gradient_step_decrease_ge_sq_objective_gap (hRα : ∀ ⦃y : E⦄, f y ≤ f x0 → infDist y XStar ≤ Rα) (hadm : non_euclidean_gradient_method_is_admissible f counterpart L x0) (hstepsize : uses_non_euclidean_gradient_stepsize_rule f Lf xSeq L xDaggerSeq M) (k : ℕ) : f (xSeq k) - f (xSeq (k + 1)) ≥ (M / ((Rα : ℝ) ^ (2 : ℕ))) * (f (xSeq k) - fOpt) ^ (2 : ℕ)

Lemma 10.70

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 10.70: a real sequence satisfying a k - a (k + 1) ≥ (1 / γ) * (a k)^2 for every k obeys the sublinear bound a k ≤ γ / k for every k ≥ 1.

lemma sequence_le_gamma_div_of_step_difference_ge_inv_mul_sq {a : ℕ → ℝ} {γ : PosReal} (hstep : ∀ k : ℕ, a k - a (k + 1) ≥ (1 / (γ : ℝ)) * (a k) ^ (2 : ℕ)) {k : ℕ} (hk : 1 ≤ k) : a k ≤ (γ : ℝ) / (k : ℝ)

Theorem 10.71

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 10.71: under the setting of Lemma 10.69, every positive iterate of the non-Euclidean gradient method satisfies the sublinear objective-gap estimate f(x^k) - f_opt ≤ C / k, where C = R_α^2 / M.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → ℝ} {XStar : Set E} {fOpt : ℝ} {Lf : NNReal} variable [hproblem : IsFastProximalGradientProblem f (0 : E → EReal) XStar fOpt Lf] variable {counterpart : ℕ → E → E} {L : ℕ → PosReal} {x0 : E} {M : ℝ} {Rα : PosReal} local notation "x" => non_euclidean_gradient_method f counterpart L x0 local notation "xDagger" => non_euclidean_gradient_method_counterpart_sequence f counterpart L x0 theorem non_euclidean_gradient_objective_gap_le_sublinear_rate (hRα : ∀ ⦃y : E⦄, f y ≤ f x0 → infDist y XStar ≤ Rα) (hadm : non_euclidean_gradient_method_is_admissible f counterpart L x0) (hstepsize : uses_non_euclidean_gradient_stepsize_rule f Lf x L xDagger M) (k : ℕ) (hk : 1 ≤ k) : f (x k) - fOpt ≤ (((Rα : ℝ) ^ (2 : ℕ)) / M) / (k : ℝ)

Theorem 10.72

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 10.72 (1): clause (a). Under the displayed g-regularity, smoothness, domain, and Bregman-potential hypotheses, if the non-Euclidean proximal-gradient trajectory uses either the constant stepsize rule L_k = L_f or backtracking procedure B5, then the objective sequence F(x^k) is nonincreasing.

universe u open Filter open scoped Topology Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {f g ω : E → EReal} {XStar : Set E} {FOpt : ℝ} {Lf : NNReal} variable [hproblem : IsConvexCompositeSmoothMinimizationProblem f g XStar FOpt Lf] variable {x : ℕ → E} {L : ℕ → PosReal} {α : ℝ} {xStar : E} local notation "F" => composite_model_objective f g theorem non_euclidean_proximal_gradient_objective_values_antitone (hω : IsBregmanPotentialOn ω (effective_domain g) (1 : ℝ)) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (htraj : is_non_euclidean_proximal_gradient_trajectory f g ω x L) (hrule : hproblem.ConstantOrBacktrackingB5StepsizeRule hω x L) : Antitone (fun k ↦ F (x k))

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