Chapter 13 — The Generalized Conditional Gradient Method

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

Algorithm 13.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 13.1 is the constrained specialization of the canonical Chapter 13 generalized trajectory owner, obtained by taking g = extendedIndicator C.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → EReal) (C : Set E) (x p : ℕ → E) (t : ℕ → Set.Icc (0 : ℝ) 1) #check is_generalized_conditional_gradient_trajectory (fun y ↦ (f y).toReal) (extendedIndicator C) x p t

Assumption 13.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 13.1: clauses (A) and (B) for the generalized conditional-gradient method mean that g : E → (-∞, ∞] is proper, closed, and convex with compact effective domain, while f : E → (-∞, ∞] never takes the value -∞, has open convex effective domain containing effective_domain g, and (fun x ↦ (f x).toReal) is L_f-smooth on effective_domain f with L_f > 0. Text 13.1 later derives the nonemptiness of the optimal set X^* from these primitive assumptions.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsGeneralizedConditionalGradientProblem (f g : E → EReal) (Lf : NNReal) : Prop extends IsProperExtendedRealFunction g where g_closed : LowerSemicontinuous g g_convex : is_convex_function g g_effective_domain_compact : IsCompact (effective_domain g) f_ne_bot : ∀ x, f x ≠ ⊥ f_effective_domain_open : IsOpen (effective_domain f) f_effective_domain_convex : Convex ℝ (effective_domain f) g_effective_domain_subset_f_effective_domain : effective_domain g ⊆ effective_domain f f_toReal_smooth_on_effective_domain : is_l_smooth_on (fun x ↦ (f x).toReal) (effective_domain f) Lf Lf_pos : 0 < (Lf : ℝ)

Definition 13.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 13.1: the conditional-gradient problem min {f x | x ∈ C} has a nonempty convex compact feasible set C in a normed real vector space E, an extended-real-valued convex objective f : E → (-∞, ∞], the feasibility condition C ⊆ dom f, an open effective domain dom f, and differentiability of f.toReal on dom f.

universe u variable {E : Type u} variable [NormedAddCommGroup E] [NormedSpace ℝ E] class IsConditionalGradientProblem (f : E → EReal) (C : Set E) : Prop where f_ne_bot (x : E) : f x ≠ ⊥ constraint_nonempty : C.Nonempty constraint_convex : Convex ℝ C constraint_compact : IsCompact C f_convex : is_convex_function f feasible_subset_effective_domain : C ⊆ effective_domain f f_effective_domain_open : IsOpen (effective_domain f) f_toReal_differentiableOn_effective_domain : DifferentiableOn ℝ (fun x ↦ (f x).toReal) (effective_domain f)

Text 13.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 13.1: under Assumption 13.1 (A) and (B), the optimal set X^* of the composite optimization problem min_x {F(x) ≡ f(x) + g(x)} is nonempty.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f g : E → EReal} {Lf : NNReal} theorem generalized_conditional_gradient_optimal_set_nonempty (h : IsGeneralizedConditionalGradientProblem f g Lf) : (unconstrained_problem_solutions (composite_model_objective f g)).Nonempty

Algorithm 13.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 13.2: a triple of sequences (xᵏ, pᵏ, tₖ) follows the generalized conditional gradient method for the composite objective f + g when x⁰ ∈ dom(g), each pᵏ ∈ argmin_p {⟪p, ∇ f(xᵏ)⟫ + g(p)}, each tₖ ∈ [0, 1], and xᵏ⁺¹ = xᵏ + tₖ (pᵏ - xᵏ). The primitive trajectory data are the initial-domain condition, the chosen argmin point at each step, and the affine update equality; the paired step statement is derived API.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] class is_generalized_conditional_gradient_trajectory (f : E → ℝ) (g : E → EReal) (x p : ℕ → E) (t : ℕ → Set.Icc (0 : ℝ) 1) : Prop where /-- The initial iterate lies in `dom(g)`. -/ zero_mem_effective_domain : x 0 ∈ effective_domain g /-- At each iteration, the chosen search point solves the canonical Chapter 13 linearized subproblem. -/ argmin_mem (k : ℕ) : p k ∈ generalized_conditional_gradient_argmin f g (x k) /-- At each iteration, the next iterate is obtained by the convex-combination update along the chosen search point. -/ step_eq (k : ℕ) : x (k + 1) = x k + (t k : ℝ) • (p k - x k) -- Proof sketch: extract the initialization clause from the first conjunct of -- `is_generalized_conditional_gradient_trajectory`.

Definition 13.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 13.2: the composite problem min {F(x) ≡ f(x) + g(x)} is the same pointwise-sum objective owner composite_model_objective introduced earlier.

recall composite_model_objective

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

Text 13.2: by Definition 13.4, the generalized conditional-gradient quantity S(x) can be written as the supremum of the values ⟪∇ f(x), x - p⟫ + g(x) - g(p) over all p ∈ E.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] notation "S[" f ", " g "](" x ")" => generalized_conditional_gradient_norm f g x -- Proof sketch: unfold `generalized_conditional_gradient_norm`; this is exactly the order-theoretic -- supremum form of the textbook maximization problem defining `S(x)`. theorem generalized_conditional_gradient_norm_eq_sSup_inner_sub_add_sub (f : E → ℝ) (g : E → EReal) (x : E) : S[f, g](x) = sSup (Set.range (fun p ↦ ((inner ℝ (∇ f x) (x - p) : ℝ) : EReal) + g x - g p))

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

Text 13.3: if A is the matrix whose columns are a₁, ..., a_l, then x ∈ convexHull ℝ (Set.range A.col) exactly when there exists a simplex point v : Δ_l = stdSimplex ℝ (Fin l) such that x = A *ᵥ v. Equivalently, the quadratic problem over the convex hull of the columns can be rewritten as the constrained problem with variables (x, v), constraint x = A v, and v ∈ Δ_l.

open Matrix variable {n l : ℕ} theorem mem_convexHull_columns_iff_exists_stdSimplex {A : Matrix (Fin n) (Fin l) ℝ} {x : Fin n → ℝ} : x ∈ convexHull ℝ (Set.range A.col) ↔ ∃ v : stdSimplex ℝ (Fin l), x = A *ᵥ (v : Fin l → ℝ)

Definition 13.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 13.4: the chapter notation p(x) ∈ arg min_p {⟪p, ∇ f(x)⟫ + g(p)} is formalized as the Chapter 8 unconstrained solution set of the generalized conditional-gradient linearized subproblem at x, without choosing a canonical minimizer.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] abbrev generalized_conditional_gradient_argmin (f : E → ℝ) (g : E → EReal) (x : E) : Set E := unconstrained_problem_solutions (generalized_conditional_gradient_subproblem f g x) -- Proof sketch: Definition 13.4's argmin set is exactly the Chapter 8 unconstrained solution-set -- owner applied to the linearized subproblem.

Algorithm 13.5

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

Source header · Attribution source

Algorithm 13.5: the admissible next feasible iterates from xᵏ are obtained by choosing a vertex index i_k minimizing ⟪a_i, ∇ f_q(xᵏ)⟫, setting dᵏ = a_{i_k} - xᵏ, and then either stopping when ⟪dᵏ, ∇ f_q(xᵏ)⟫ ≥ 0, or updating by the exact-line-search step xᵏ⁺¹ = xᵏ + t_k dᵏ with t_k = min {λ_k, 1}.

open Matrix variable {n l : ℕ} local notation "E" => Fin n → ℝ inductive polytope_quadratic_conditional_gradient_one_step (Q : positiveDefiniteMatrices n) (b : E) (a : Fin l → E) (xk : polytope_quadratic_feasible_set a) : polytope_quadratic_feasible_set a → Prop where | stop (i : Fin l) (hi : i ∈ unconstrained_problem_solutions (polytope_quadratic_vertex_linear_objective Q b a xk)) (hderiv : 0 ≤ polytope_quadratic_conditional_gradient_directional_derivative Q b a xk i) : polytope_quadratic_conditional_gradient_one_step Q b a xk xk | update (i : Fin l) (hi : i ∈ unconstrained_problem_solutions (polytope_quadratic_vertex_linear_objective Q b a xk)) (hderiv : polytope_quadratic_conditional_gradient_directional_derivative Q b a xk i < 0) : polytope_quadratic_conditional_gradient_one_step Q b a xk (polytope_quadratic_conditional_gradient_next_iterate Q b a xk i hderiv) -- Proof sketch: pattern match on the two constructors of -- `polytope_quadratic_conditional_gradient_one_step`; the result is exactly the displayed -- stop-or-update alternative on feasible iterates.

Definition 13.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 13.5: the chapter conditional-gradient quantity S(x) is the existing canonical owner S[f, g](x), i.e. generalized_conditional_gradient_norm f g x. A chosen search-point map p(x) is handled below only as a bridge to that owner via pointwise argmin selection.

universe u recall generalized_conditional_gradient_norm

Lemma 13.5

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

Source header · Attribution source

Lemma 13.5: the generalized conditional-gradient norm rewrites as the affine term ⟪∇ f(x), x⟫ + g(x) plus the Fenchel conjugate value g∗(-∇ f(x)), where the gradient is taken for the real-valued map y ↦ (f y).toReal.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f g : E → EReal) local notation "f₀" => fun y ↦ EReal.toReal (f y) theorem generalized_conditional_gradient_norm_eq_inner_add_value_add_conjugate (x : E) : S[f₀, g](x) = ((inner ℝ (∇ f₀ x) x : ℝ) : EReal) + g x + (g∗) (-∇ f₀ x)

Algorithm 13.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 13.6: an initialization canonically yields Assumption 13.18 for the final output (x⁰, v⁰). This is the chapter-level bridge/view from the procedural initialization data to the source-facing strict-vertex-sublevel owner.

open scoped BigOperators variable {n l : ℕ} local notation "E" => Fin n → ℝ variable {f_q : E → ℝ} {a : Fin l → E} {p : Fin l} {xTilde0 x0 : E} variable {vTilde0 v0 : stdSimplex ℝ (Fin l)} variable {Q : positiveDefiniteMatrices n} {b : E} {a : Fin l → E} variable {p : Fin l} {xTilde0 x0 : E} {vTilde0 v0 : stdSimplex ℝ (Fin l)} namespace algorithm_13_6_initialization theorem toIsStrictVertexSublevelInitialPoint (h : algorithm_13_6_initialization Q b a p xTilde0 x0 vTilde0 v0) : IsStrictVertexSublevelInitialPoint (polytope_quadratic_objective Q b) a x0 v0

Definition 13.6

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

Source header · Attribution source

Definition 13.6 (1): the predefined diminishing stepsize strategy for the generalized conditional-gradient method uses the scalar t_k = 2 / (k + 2) at iteration k.

universe u def conditional_gradient_predefined_diminishing_stepsize (k : ℕ) : ℝ := 2 / (k + 2 : ℝ)

Theorem 13.6

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

Source header · Attribution source

Theorem 13.6 (1): the generalized conditional-gradient norm S(x) is nonnegative for every x, under the properness assumptions on g actually used by Fenchel's inequality.

universe u open InnerProductSpace (toDual) open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g : E → EReal} local notation "f₀" => fun y ↦ EReal.toReal (f y) theorem generalized_conditional_gradient_norm_nonneg (hg_proper : IsProperExtendedRealFunction g) (x : E) : 0 ≤ S[f₀, g](x)

Algorithm 13.7

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

Source header · Attribution source

Algorithm 13.7: for an initial point x⁰ ∈ dom(g), a realized sequence sampled_block k = i_k of sampled block indices, sampled-block minimizers `p^k ∈ argmin_v {⟪v, ∇_{i_k} f(x^k)⟫ + g_{i_k}(v)}, and stepsizes t_k ∈ [0, 1], the iterates x^k` follow the randomized generalized block conditional gradient method when x^{k+1} = x^k + 𝒰[i_k] (t_k • (p^k - x^k_{i_k})). As in Algorithm 13.2, the primitive trajectory data are exactly the initialization clause, the sampled-block argmin clause, and the one-block update equality; the accessor lemmas below are derived API.

universe v open scoped Gradient variable {ι : Type v} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] variable [∀ i, InnerProductSpace ℝ (Ei i)] local notation "X" => PiLp 2 Ei class is_randomized_generalized_block_conditional_gradient_trajectory (g : (i : ι) → Ei i → EReal) (block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i) (x : ℕ → X) (sampled_block : ℕ → ι) (point : (k : ℕ) → Ei (sampled_block k)) (t : ℕ → Set.Icc (0 : ℝ) 1) : Prop where /-- The initial iterate lies in `dom(g)`. -/ zero_mem_effective_domain : x 0 ∈ effective_domain (PiLp.separableSum g) /-- At each iteration, the sampled-block point solves the sampled linearized subproblem. -/ argmin_mem (k : ℕ) : point k ∈ partial_conditional_gradient_argmin g block_gradient (x k) (sampled_block k) /-- At each iteration, the update changes only the realized sampled block. -/ step_eq (k : ℕ) : x (k + 1) = x k + 𝒰[sampled_block k] ((t k : ℝ) • (point k - x k (sampled_block k))) -- Proof sketch: extract the initialization clause from the first conjunct of -- `is_randomized_generalized_block_conditional_gradient_trajectory`.

Lemma 13.7

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

Source header · Attribution source

Lemma 13.7: if f is L_f-smooth on dom(g), g is convex, x ∈ dom(g), p minimizes the linearized subproblem at x, and t ∈ [0, 1], then the composite objective satisfies F(x + t (p - x)) ≤ F(x) - t S(x) + (t^2 L_f / 2) ‖p - x‖^2. Here F = composite_model_objective f.toEReal g and S(x) = S[f, g](x). The chosen-point formula S[f, g](x) = generalized_conditional_gradient_gap_objective f g x p follows from hp by Text 13.2. The textbook assumption g : E → (-∞, ∞] is represented by hg_ne_bot : ∀ y, g y ≠ ⊥.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {g : E → EReal} {Lf : NNReal} local notation "F" => composite_model_objective f.toEReal g theorem generalized_conditional_gradient_fundamental_inequality (hg_ne_bot : ∀ y, g y ≠ ⊥) (hg_convex : is_convex_function g) (hf_smooth : is_l_smooth_on f (effective_domain g) Lf) {x p : E} (hx : x ∈ effective_domain g) (hp : p ∈ generalized_conditional_gradient_argmin f g x) {t : ℝ} (ht : t ∈ Set.Icc (0 : ℝ) 1) : F (x + t • (p - x)) ≤ F x - (t : EReal) * S[f, g](x) + (((t ^ 2 * (Lf : ℝ) / 2) * ‖p - x‖ ^ 2 : ℝ) : EReal)

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

Lemma 13.8: if g : E → (-∞, ∞] is convex, f is L_f-smooth on dom(g), x⁰ ∈ dom(g), each pᵏ ∈ arg min_p {⟪p, ∇ f(xᵏ)⟫ + g(p)}, and xᵏ⁺¹ = xᵏ + tₖ (pᵏ - xᵏ) with stepsizes chosen either by the adaptive rule or by exact line search, then every one-step objective decrease is at least (1 / 2) * min {S(xᵏ), S(xᵏ)^2 / (L_f Ω^2)}, where S(xᵏ) = (S[f, g](x k)).toReal and Ω bounds the diameter of dom(g). Here F = composite_model_objective f.toEReal g. The textbook codomain restriction is represented explicitly by hg_ne_bot : ∀ y, g y ≠ ⊥.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {g : E → EReal} local notation "F" => composite_model_objective f.toEReal g theorem generalized_conditional_gradient_sufficient_decrease_of_adaptive_or_exact_line_search {Lf : NNReal} (hg_ne_bot : ∀ y, g y ≠ ⊥) (hg_convex : is_convex_function g) (hf_smooth_on_effective_domain_g : is_l_smooth_on f (effective_domain g) Lf) {x p : ℕ → E} {t : ℕ → Set.Icc (0 : ℝ) 1} (htraj : is_generalized_conditional_gradient_trajectory f g x p t) (hrule : uses_generalized_conditional_gradient_adaptive_or_exact_stepsize_rule f g Lf x p t) {Ω : ℝ} (hΩ : ∀ u ∈ effective_domain g, ∀ v ∈ effective_domain g, ‖u - v‖ ≤ Ω) (k : ℕ) : F (x k) - F (x (k + 1)) ≥ ((1 / 2 : ℝ) * min ((S[f, g](x k)).toReal) ((S[f, g](x k)).toReal ^ (2 : ℕ) / ((Lf : ℝ) * Ω ^ (2 : ℕ))) : EReal)

Definition 13.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 13.9: the constrained objective already has the canonical owner-level solution-set bridge in Chapter 10.

universe u variable {E : Type u} recall unconstrained_problem_solutions_constrained_problem_objective_eq

Theorem 13.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 13.9 (1): clause (a). Under Assumption 13.1, every step of the generalized conditional-gradient method with adaptive stepsize or exact line search is objective nonincreasing: F(x^(k+1)) ≤ F(x^k) for all k ≥ 0.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [CompleteSpace E] variable {f : E → ℝ} {g : E → EReal} {Lf : NNReal} variable [hproblem : IsGeneralizedConditionalGradientProblem f.toEReal g Lf] variable {x p : ℕ → E} {t : ℕ → Set.Icc (0 : ℝ) 1} variable (htraj : is_generalized_conditional_gradient_trajectory f g x p t) variable (hrule : uses_generalized_conditional_gradient_adaptive_or_exact_stepsize_rule f g Lf x p t) local notation "F" => composite_model_objective f.toEReal g local notation "F_opt" => generalized_conditional_gradient_optimal_value f.toEReal g theorem generalized_conditional_gradient_objective_step_nonincreasing [hproblem : IsGeneralizedConditionalGradientProblem f.toEReal g Lf] (htraj : is_generalized_conditional_gradient_trajectory f g x p t) (hrule : uses_generalized_conditional_gradient_adaptive_or_exact_stepsize_rule f g Lf x p t) (k : ℕ) : F (x (k + 1)) ≤ F (x k)

Definition 13.10

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

Source header · Attribution source

Definition 13.10: the quadratic program (13.32) on ℝ^n, with matrix Q, linear term b, and feasible set Ω = conv{a₁, a₂, …, a_l}, is the constrained objective obtained by restricting x ↦ (1 / 2) xᵀ Q x + bᵀ x to Ω. In the textbook setting, later results further assume Q ∈ 𝕊_{++}^n.

open Matrix variable {n l : ℕ} local notation "E" => Fin n → ℝ abbrev polytope_quadratic_problem (Q : Matrix (Fin n) (Fin n) ℝ) (b : E) (a : Fin l → E) : E → EReal := constrained_problem_objective (polytope_quadratic_objective Q b).toEReal (polytope_quadratic_feasible_set a) -- Proof sketch: rewrite `polytope_quadratic_problem` as `constrained_problem_objective` on the -- feasible set `polytope_quadratic_feasible_set a`, then apply -- `constrained_problem_objective_of_mem`.

Example 13.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

Example 13.10 (1): for the unit-ball constrained problem, the canonical conditional-gradient gap S[f, δ_B](x) is ⟪∇ f(x), x⟫ + ‖∇ f(x)‖. Equivalently, the normalized negative gradient is the corresponding oracle choice realizing this gap.

universe u open InnerProductSpace (toDualMap) open Metric open scoped Gradient -- Chapter 7 owns the global `Λ[...]` parser. Use the Chapter 10 meaning only in this file. local notation "Λ[" a "]" => primalCounterparts a variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] local notation "B" => closedBall (0 : E) 1 theorem unit_ball_generalized_conditional_gradient_norm_eq_inner_gradient_add_norm (f : E → ℝ) {x : E} (hx : x ∈ B) : S[f, extendedIndicator B](x) = ((inner ℝ (∇ f x) x + ‖∇ f x‖ : ℝ) : EReal)

Example 13.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

Example 13.11: for the quadratic maximization problem on the Euclidean unit ball with A ∈ 𝕊_+^n, if (xᵏ, pᵏ, tₖ) is a generalized conditional-gradient trajectory for the quadratic term x ↦ -(1 / 2) ⟪x, A x⟫ and the closed-ball indicator, if each tₖ is chosen by exact line search, and if xᵏ is not a constrained stationary point on the unit ball, then the next iterate is exactly the normalized matrix image xᵏ⁺¹ = (1 / ‖A xᵏ‖) • A xᵏ, i.e. the standard power-method update.

open InnerProductSpace (toDualMap) open Matrix open Metric open scoped Gradient RealInnerProductSpace -- Chapter 7 owns the global `Λ[...]` parser. Use the Chapter 10 meaning only in this file. local notation "Λ[" a "]" => primalCounterparts a variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "B" => closedBall (0 : E) 1 variable (A : Matrix (Fin n) (Fin n) ℝ) local notation "qA" => quadratic_affine_function_on_lp (2 : ENNReal) (-A) 0 0 theorem generalized_conditional_gradient_step_eq_power_method_of_not_stationary (hA : A.PosSemidef) {x p : ℕ → E} {t : ℕ → Set.Icc (0 : ℝ) 1} (htraj : is_generalized_conditional_gradient_trajectory qA (extendedIndicator B) x p t) (hline : uses_generalized_conditional_gradient_exact_line_search_rule qA (extendedIndicator B) x p t) (k : ℕ) (hk : ¬ is_stationary_point_on qA B (x k)) : x (k + 1) = ‖A.toEuclideanLin (x k)‖⁻¹ • A.toEuclideanLin (x k)

Lemma 13.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 13.12: if f is convex, never takes the value ⊥, and f₀ is differentiable at the base point x ∈ dom(f) ∩ dom(g), then the canonical generalized conditional-gradient norm dominates the objective gap F x - F_opt. Under Assumption 13.1, the differentiability hypothesis is supplied at every feasible point by Theorem 13.6.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g : E → EReal} open scoped Gradient local notation "f₀" => fun y ↦ EReal.toReal (f y) local notation "F" => composite_model_objective f g local notation "F_opt" => generalized_conditional_gradient_optimal_value f g theorem generalized_conditional_gradient_gap_ge_objective_gap {x : E} (hf_ne_bot : ∀ y, f y ≠ ⊥) (hf_convex : is_convex_function f) (hx_f : x ∈ effective_domain f) (hx_diff : DifferentiableAt ℝ f₀ x) (hx : x ∈ effective_domain g) : S[f₀, g](x) ≥ F x - F_opt

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

Lemma 13.13 (1): if nonnegative sequences a_k and b_k satisfy a_{k+1} ≤ a_k - γ_k b_k + (A / 2) γ_k^2 with γ_k = 2 / (k + 2p) and a_k ≤ b_k, then for every k ≥ 1 one has a_k ≤ 2 * max {A, (p - 1) a_0} / (k + 2p - 2).

open scoped BigOperators variable (a b : ℕ → ℝ) (A : ℝ) (p : ℕ) variable (hp : 1 ≤ p) variable (ha_nonneg : ∀ k : ℕ, 0 ≤ a k) variable (hstep : ∀ k : ℕ, a (k + 1) ≤ a k - conditional_gradient_predefined_diminishing_stepsize (k + 2 * (p - 1)) * b k + (A / 2) * (conditional_gradient_predefined_diminishing_stepsize (k + 2 * (p - 1))) ^ (2 : ℕ)) variable (ha_le_b : ∀ k : ℕ, a k ≤ b k) include hp ha_nonneg hstep ha_le_b -- Proof sketch: use `a k ≤ b k` to rewrite the recurrence as -- `a (k + 1) ≤ (1 - γₖ) * a k + (A / 2) * γₖ²` with -- `γₖ = conditional_gradient_predefined_diminishing_stepsize (k + 2 * (p - 1)) = 2 / (k + 2p)`, -- then unroll the -- recursion and estimate the resulting product and sum exactly as in the textbook. theorem scalar_recurrence_le_sublinear_bound_of_conditional_gradient_stepsize {k : ℕ} (hk : 1 ≤ k) : a k ≤ (2 * max A ((((p - 1 : ℕ) : ℝ) * a 0))) / (((k + 2 * p - 2 : ℕ) : ℝ))

Theorem 13.14

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

Source header · Attribution source

Theorem 13.14 (1): under Assumption 13.1, if f is convex and (xᵏ, pᵏ, tₖ) is a generalized conditional-gradient trajectory using either the predefined stepsize tₖ = 2 / (k + 2), the adaptive stepsize, or exact line search, and if Ω bounds the diameter of dom(g), then the objective gap satisfies F(xᵏ) - F_opt ≤ 2 L_f Ω^2 / k for every k ≥ 1.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {g : E → EReal} {Lf : NNReal} (hproblem : IsGeneralizedConditionalGradientProblem f.toEReal g Lf) (hf_convex : ConvexOn ℝ Set.univ f) {x p : ℕ → E} {t : ℕ → Set.Icc (0 : ℝ) 1} (htraj : is_generalized_conditional_gradient_trajectory f g x p t) (hsteps : uses_generalized_conditional_gradient_standard_stepsize_rule f g Lf x p t) {Ω : ℝ} (hΩ : ∀ u ∈ effective_domain g, ∀ v ∈ effective_domain g, ‖u - v‖ ≤ Ω) local notation "F" => composite_model_objective f.toEReal g local notation "F_opt" => generalized_conditional_gradient_optimal_value f.toEReal g include hproblem htraj hsteps hΩ omit hproblem htraj hsteps hΩ include hproblem htraj hsteps hΩ omit hproblem htraj hsteps hΩ include hproblem htraj hsteps hΩ omit hproblem htraj hsteps hΩ include hproblem hf_convex htraj hsteps hΩ theorem generalized_conditional_gradient_objective_gap_le_sublinear_rate {k : ℕ} (hk : 1 ≤ k) : F (x k) - F_opt ≤ (((2 : ℝ) * (Lf : ℝ) * Ω ^ (2 : ℕ) / (k : ℝ) : ℝ) : EReal)

Definition 13.15

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

Source header · Attribution source

Definition 13.15: the constrained problem min_{x ∈ C} f(x) is represented by the Chapter 3 owner constrained_problem_objective, specialized to the given objective f and feasible set C.

recall constrained_problem_objective

Lemma 13.15

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

Source header · Attribution source

Lemma 13.15: if the series of absolute values ∑ |a n| diverges, then for every ε > 0 there are infinitely many positive indices k whose square tail is at least k ^ (-(1 + ε)). The tail of squares is expressed via the canonical nonnegative ENNReal series.

theorem tail_sq_ge_rpow_neg_infinitely_often_of_not_summable_abs {a : ℕ → ℝ} (ha : ¬ Summable (fun n ↦ |a n|)) {ε : ℝ} (hε : 0 < ε) : Set.Infinite {k : ℕ | 0 < k ∧ ENNReal.ofReal ((k : ℝ) ^ (-(1 + ε))) ≤ ∑' n : ℕ, ENNReal.ofReal ((a (n + k)) ^ 2)}

Definition 13.16

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

Source header · Attribution source

Definition 13.16: on the canonical block product PiLp 2 E, the block composite objective is the Chapter 10 owner composite_model_objective f (PiLp.separableSum g), the insertion map 𝒰ᵢ is the Chapter 11 notation for PiLp.single 2 i, and the block partial gradient ∇ᵢ f is the Chapter 11 bridge to the ambient gradient.

open scoped Gradient recall PiLp.separableSum

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

Lemma 13.16: for a real sequence with 0 ≤ b n < 1 for every n, the textbook partial products ∏_{n=0}^m (1 - b n) tend to 0 exactly when the series ∑ b n diverges.

open Filter open scoped Topology theorem prod_one_sub_tendsto_zero_iff_not_summable {b : ℕ → ℝ} (hb_nonneg : ∀ n, 0 ≤ b n) (hb_lt_one : ∀ n, b n < 1) : Tendsto (fun m : ℕ ↦ ∏ n ∈ Finset.range (m + 1), (1 - b n)) atTop (𝓝 0) ↔ ¬ Summable b

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

Assumption 13.17: for the constrained problem from Definition 13.10, the feasible set Ω has nonempty interior, and the chosen optimal solution xStar = x* lies on the boundary of Ω but is not an extreme point of Ω.

universe u variable {E : Type u} {α : Type*} [Preorder α] variable [TopologicalSpace E] [AddCommMonoid E] [SMul ℝ E] class IsBoundaryNonExtremeOptimalSolution (F : E → α) (Ω : Set E) (xStar : E) : Prop where interior_nonempty : (interior Ω).Nonempty mem_constrained_problem_solutions : xStar ∈ constrained_problem_solutions F Ω mem_frontier : xStar ∈ frontier Ω not_mem_extremePoints : xStar ∉ Ω.extremePoints ℝ

Definition 13.17

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

Source header · Attribution source

Definition 13.17: the i-th partial conditional-gradient norm S_i(x) is the supremum of the block gap objective v ↦ ⟪∇_i f(x), x_i - v⟫ + g_i(x_i) - g_i(v) over the i-th block space.

universe u v open scoped BigOperators variable {ι : Type u} {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] [∀ i, InnerProductSpace ℝ (Ei i)] def partial_conditional_gradient_norm (g : (i : ι) → Ei i → EReal) (block_gradient : (i : ι) → ((j : ι) → Ei j) → Ei i) (x : (j : ι) → Ei j) (i : ι) : EReal := sSup (Set.range (partial_conditional_gradient_gap_objective g block_gradient x i))

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

Assumption 13.18: the starting point x0 = x⁰ has quadratic objective value strictly below every vertex value f_q(a_i), where Ω = conv{a₁, …, a_l}, and x0 is the barycentric combination of the vertices a_i with strictly positive simplex weights v0 = v⁰.

open scoped BigOperators universe u variable {E : Type u} [AddCommMonoid E] [Module ℝ E] variable {l : ℕ} class IsStrictVertexSublevelInitialPoint (f_q : E → ℝ) (a : Fin l → E) (x0 : E) (v0 : stdSimplex ℝ (Fin l)) : Prop where objective_lt_vertex (i : Fin l) : f_q x0 < f_q (a i) eq_weighted_sum : x0 = ∑ i, v0 i • a i weights_mem_positiveOrthant : (v0 : Fin l → ℝ) ∈ positiveOrthant l

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

Lemma 13.19 (1): every iterate of the exact-line-search polytope quadratic conditional-gradient trajectory lies in the interior of Ω = conv{a₁, …, a_l}.

open Matrix open scoped BigOperators variable {n l : ℕ} local notation "E" => Fin n → ℝ variable {Q : positiveDefiniteMatrices n} {b : Fin n → ℝ} {a : Fin l → Fin n → ℝ} variable {x : ℕ → polytope_quadratic_feasible_set a} {i : ℕ → Fin l} local notation "d[" k "]" => polytope_quadratic_conditional_gradient_direction a (x k) (i k) local notation "λ[" k "]" => polytope_quadratic_exact_line_search_ratios Q b a x i k local notation "κ[" k "]" => dotProduct (d[k]) (Q *ᵥ d[k]) -- The trajectory predicate itself is owned by the extracted theorem-local core helper module -- `Lemma_13_19.TrajectoryCore`, so the target file only keeps the source-facing results. -- Proof sketch: apply the canonical Algorithm 13.5 bridge from a negative directional derivative -- to exact line search on the segment from `xᵏ` to `a_{i_k}`. variable {v0 : stdSimplex ℝ (Fin l)} {xStar : Fin n → ℝ} local notation "Ω" => convexHull ℝ (Set.range a) local notation "f_q" => polytope_quadratic_objective Q b local notation "f_opt" => EReal.toReal (polytope_quadratic_optimal_value Q b a) local notation "gap[" k "]" => f_q (x k : E) - f_opt -- The public barycentric-weight owner is imported from `TrajectoryWeights`; keeping a second -- declaration here would duplicate the same recursive object and obscure its trajectory data. local notation "v[" k "]" => polytope_quadratic_exact_line_search_weights (Q := Q) (b := b) (a := a) (x := x) (i := i) (v0 : Fin l → ℝ) k theorem polytope_quadratic_exact_line_search_iterate_mem_interior (hΩ : (interior Ω).Nonempty) (hinit : IsStrictVertexSublevelInitialPoint (polytope_quadratic_objective Q b) a (x 0 : E) v0) (htraj : is_polytope_quadratic_conditional_gradient_exact_line_search_trajectory Q b a x i) (k : ℕ) : (x k : E) ∈ interior Ω

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

Theorem 13.20: under Assumptions 13.17 and 13.18, every sequence generated by Algorithm 13.5 for the quadratic problem (13.32) has the Canon-Cullum negative-rate property: for every ε > 0, the objective gap f_q(xᵏ) - f_opt is at least k ^ (-(1 + ε)) for infinitely many positive indices k.

open Matrix open scoped BigOperators variable {n l : ℕ} local notation "E" => Fin n → ℝ variable (Q : positiveDefiniteMatrices n) (b : E) (a : Fin l → E) variable (x : ℕ → polytope_quadratic_feasible_set a) local notation "Ω" => convexHull ℝ (Set.range a) local notation "f_q" => polytope_quadratic_objective Q b local notation "f_opt" => EReal.toReal (polytope_quadratic_optimal_value Q b a) local notation "gap[" k "]" => f_q (x k) - f_opt local notation "d[" i "," k "]" => polytope_quadratic_conditional_gradient_direction a (x k) (i k) local notation "κ[" i "," k "]" => dotProduct (d[i, k]) (Q *ᵥ d[i, k]) local notation "λ[" i "," k "]" => polytope_quadratic_exact_line_search_ratio Q b (x k) (d[i, k]) theorem polytope_quadratic_objective_gap_ge_rpow_neg_one_add_eps_infinitely_often {xStar : E} {v0 : stdSimplex ℝ (Fin l)} (hboundary : IsBoundaryNonExtremeOptimalSolution (polytope_quadratic_problem Q b a) Ω xStar) (hstart : IsStrictVertexSublevelInitialPoint f_q a (x 0) v0) (hstep : ∀ k : ℕ, polytope_quadratic_conditional_gradient_one_step Q b a (x k) (x (k + 1))) (ε : ℝ) (hε : 0 < ε) : Set.Infinite {k : ℕ | 0 < k ∧ ((k : ℝ) ^ (-(1 + ε))) ≤ gap[k]}

Definition 13.22

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

Source header · Attribution source

Definition 13.22 (1): a nonempty set C is σ-strongly convex when σ > 0; for every x, y ∈ C plus every t ∈ [0, 1], the closed ball centered at the convex combination t • x + (1 - t) • y, with radius (σ / 2) * t * (1 - t) * ‖x - y‖², is contained in C.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] namespace Set class StronglyConvexWith (C : Set E) (σ : ℝ) : Prop where sigma_pos : 0 < σ nonempty : C.Nonempty strongConvex : StrongConvex C σ

Theorem 13.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 13.23: if g is nonnegative, globally L_g-smooth, and globally σ_g-strongly convex, and if the α-sublevel set is nonempty, then C_α = g ⁻¹' Iic α is σ_g / sqrt(2 α L_g)-strongly convex in the Chapter 13 source-facing sense.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] open Set theorem sublevelSet_stronglyConvexWith_of_nonnegative_isLSmoothOn_of_strongConvexOn (g : E → ℝ) (α : ℝ) (Lg : NNReal) (σg : ℝ) (hα : 0 < α) (hLg : 0 < (Lg : ℝ)) (hσg : 0 < σg) (hsublevel_nonempty : (g ⁻¹' Iic α).Nonempty) (hg_nonneg : ∀ x, 0 ≤ g x) (hg_smooth : is_l_smooth_on g univ Lg) (hg_strong : StrongConvexOn univ σg g) : Set.StronglyConvexWith (g ⁻¹' Iic α) (σg / Real.sqrt (2 * α * (Lg : ℝ)))

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

Assumption 13.25 (1): clauses (A)-(D) for the strongly convex conditional-gradient setting mean that f never takes the value ⊥, the constrained feasible set C is nonempty and compact, f is convex with C ⊆ dom(f) and open effective domain, σ > 0, C is σ-strongly convex in the primitive sense Set.StrongConvex C σ, x ↦ (f x).toReal is L_f-smooth on dom(f) with L_f > 0, and the gradient norm on C is bounded below by δ > 0, for the constrained problem min {f x : x ∈ C}. The baseline owner IsConditionalGradientProblem f C is derived below as bridge API rather than inherited. The canonical optimizer set constrained_problem_solutions f C and optimal value generalized_conditional_gradient_optimal_value f (extendedIndicator C) are derived below rather than stored as primitive fields.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] class IsStronglyConvexConditionalGradientProblem (f : E → EReal) (C : Set E) (σ δ : ℝ) (Lf : NNReal) : Prop where f_ne_bot (x : E) : f x ≠ ⊥ constraint_nonempty : C.Nonempty constraint_compact : IsCompact C f_convex : is_convex_function f feasible_subset_effective_domain : C ⊆ effective_domain f f_effective_domain_open : IsOpen (effective_domain f) sigma_pos : 0 < σ strongConvex : Set.StrongConvex C σ f_toReal_smooth_on_effective_domain : is_l_smooth_on (fun x ↦ (f x).toReal) (effective_domain f) Lf Lf_pos : 0 < (Lf : ℝ) delta_pos : 0 < δ gradient_norm_lower_bound {x : E} (hx : x ∈ C) : δ ≤ ‖∇ (fun y ↦ (f y).toReal) x‖

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

Lemma 13.26: if C is σ-strongly convex in the primitive sense Set.StrongConvex C σ, σ > 0, fun y ↦ (f y).toReal is differentiable at the feasible point x ∈ C, δ ≤ ‖∇f(x)‖, and px is a feasible linear minimizer at x, then the canonical constrained Frank-Wolfe gap S(x) dominates (σ δ / 4) ‖x - px‖².

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → EReal} {C : Set E} {σ δ : ℝ} local notation "f₀" => fun y ↦ EReal.toReal (f y) theorem generalized_conditional_gradient_norm_ge_strong_convexity_quadratic_bound (hσ : 0 < σ) (hC : Set.StrongConvex C σ) (x : C) (hx_diff : DifferentiableAt ℝ f₀ x) (hδ : δ ≤ ‖∇ f₀ x‖) (px : E) (hp : px ∈ generalized_conditional_gradient_argmin f₀ (extendedIndicator C) x) : (S[f₀, extendedIndicator C](x)).toReal ≥ (σ * δ / 4) * ‖x - px‖ ^ (2 : ℕ)

Theorem 13.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 13.27 (1): under Assumption 13.25, every adaptive-step or exact-line-search conditional-gradient iteration contracts the constrained objective gap by the factor 1 - λ, where λ = min {σ δ / (8 L_f), 1 / 2}.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → EReal} {C : Set E} {σ δ : ℝ} {Lf : NNReal} local notation "f₀" => fun y ↦ EReal.toReal (f y) local notation "f_opt" => generalized_conditional_gradient_optimal_value f (extendedIndicator C) local notation "F" => composite_model_objective f (extendedIndicator C) variable [hproblem : IsStronglyConvexConditionalGradientProblem f C σ δ Lf] {x p : ℕ → E} {t : ℕ → Set.Icc (0 : ℝ) 1} (htraj : is_generalized_conditional_gradient_trajectory (fun y : E ↦ EReal.toReal (f y)) (extendedIndicator C) x p t) (hsteps : uses_generalized_conditional_gradient_adaptive_or_exact_stepsize_rule (fun y : E ↦ EReal.toReal (f y)) (extendedIndicator C) Lf x p t) local notation "λ" => min (σ * δ / (8 * (Lf : ℝ))) (1 / 2 : ℝ) include hproblem htraj hsteps -- Proof sketch: combine the sufficient-decrease estimate for adaptive stepsize / exact line -- search with the strong-convex-feasible-set gap lower bound from Lemma 13.26. The ratio -- estimate yields the contraction factor `1 - λ`, where -- `λ = min {σ δ / (8 L_f), 1 / 2}`. theorem conditional_gradient_objective_gap_step_le_linear_rate_factor (k : ℕ) : (f (x (k + 1)) - f_opt).toReal ≤ (1 - λ) * (f (x k) - f_opt).toReal

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

Assumption 13.28: clauses (A)-(D) for the randomized generalized block conditional-gradient method are expressed directly on the chapter objects f : X → EReal, the block penalties g_i, the canonical PiLp block gradient ∇[i] (fun z ↦ (f z).toReal). The public owner keeps only the primitive regularity, domain-compatibility, differentiability, and block-Lipschitz clauses on the PiLp model; the canonical optimizer set unconstrained_problem_solutions (composite_model_objective f (PiLp.separableSum g)) and optimal value generalized_conditional_gradient_optimal_value f (PiLp.separableSum g) are derived below rather than stored as wrapper parameters. The one-block update and slice are written in the canonical Chapter 11 textbook form x + 𝒰[i] d.

universe v open scoped Gradient variable {ι : Type v} [Fintype ι] {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] variable [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, CompleteSpace (Ei i)] local notation "X" => PiLp 2 Ei class IsGeneralizedBlockConditionalGradientProblem (f : X → EReal) (g : (i : ι) → Ei i → EReal) (Li : (i : ι) → PosReal) : Prop where block_g_proper (i : ι) : IsProperExtendedRealFunction (g i) block_g_closed (i : ι) : LowerSemicontinuous (g i) block_g_convex (i : ι) : is_convex_function (g i) g_effective_domain_compact (i : ι) : IsCompact (effective_domain (g i)) f_ne_bot (x : X) : f x ≠ ⊥ f_convex : is_convex_function f g_effective_domain_subset_f_effective_domain : effective_domain (PiLp.separableSum g) ⊆ effective_domain f f_effective_domain_open : IsOpen (effective_domain f) f_toReal_differentiableOn_effective_domain : DifferentiableOn ℝ (fun x ↦ (f x).toReal) (effective_domain f) block_partial_gradient_lipschitz (i : ι) {x : X} {d : Ei i} (hx : x ∈ effective_domain f) (hxd : x + (𝒰[i] d : X) ∈ effective_domain f) : ‖(∇[i] fun z : X ↦ (f z).toReal) x - (∇[i] fun z : X ↦ (f z).toReal) (x + (𝒰[i] d : X))‖ ≤ (Li i : ℝ) * ‖d‖

Theorem 13.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 13.29. Under Assumption 13.28, if x^k is the RGBCG iterate process with deterministic stepsizes t_k = 2 |ι| / (k + 2 |ι|) and Ω bounds the diameter of dom(g) in the weighted norm ‖·‖_L, then: (a) for every k ≥ 1, the expected objective gap satisfies E(F(x^k)) - F_opt ≤ 2 max{(|ι| - 1)(F(x^0) - F_opt), |ι| Ω^2} / (k + 2 |ι| - 2); (b) for every k ≥ 3, the minimum of E(S(x^n)) on the half-tail interval {⌊k / 2⌋ + 2, …, k} is bounded by 8 max{(|ι| - 1)(F(x^0) - F_opt), |ι| Ω^2} / (k - 2). In Lean clause (b) is represented by the infimum of the finite image over Set.Icc (k / 2 + 2) k, and the generated-by-method hypothesis is packaged by is_generated_by_randomized_generalized_block_conditional_gradient_method rather than exposed as a separate deterministic point-rule premise.

universe v w open MeasureTheory ProbabilityTheory open scoped ProbabilityTheory ENNReal Gradient open GeneralizedBlockConditionalGradient variable {Ξ : Type w} [MeasurableSpace Ξ] {μ : Measure Ξ} [IsProbabilityMeasure μ] variable {ι : Type v} [Fintype ι] [MeasurableSpace ι] [DiscreteMeasurableSpace ι] variable {Ei : ι → Type v} variable [∀ i, NormedAddCommGroup (Ei i)] variable [∀ i, InnerProductSpace ℝ (Ei i)] variable [∀ i, CompleteSpace (Ei i)] local notation "X" => PiLp 2 Ei open scoped RBPG variable {f : X → EReal} {g : (i : ι) → Ei i → EReal} variable {Li : (i : ι) → PosReal} variable {sampled_block : ℕ → Ξ → ι} {x : ℕ → Ξ → X} variable {point : (k : ℕ) → (ω : Ξ) → Ei (sampled_block k ω)} variable {t : ℕ → Set.Icc (0 : ℝ) 1} local notation "F" => composite_model_objective f (PiLp.separableSum g) local notation "domG" => effective_domain (PiLp.separableSum g) local notation "F_opt" => generalized_conditional_gradient_optimal_value f (PiLp.separableSum g) local notation "F_opt_real" => EReal.toReal F_opt local notation "N" => Fintype.card ι -- Proof sketch: after expressing the sampled-block observable through the current sampled block -- and the finite sampled-block history, specialize Chapter 11's -- `randomized_block_history_current_block_average` and rewrite the resulting block average with -- `block_conditional_gradient_norm_eq_sum`. variable (x0 : X) (Ω : ℝ) local notation "rateBound" => max ((((N - 1 : ℕ) : ℝ) * (EReal.toReal (F x0) - F_opt_real))) (((N : ℝ) * Ω ^ (2 : ℕ))) theorem randomized_generalized_block_conditional_gradient_expected_sublinear_rates (h_problem : IsGeneralizedBlockConditionalGradientProblem f g Li) (h_zero : x 0 = fun _ ↦ x0) (h_generated : is_generated_by_randomized_generalized_block_conditional_gradient_method g (blockGradient f) x sampled_block point t) (h_stepsize : ∀ n : ℕ, (t n : ℝ) = (2 * Fintype.card ι : ℝ) / (n + 2 * Fintype.card ι : ℕ)) (h_sampled_block_measurable : ∀ n, Measurable (sampled_block n)) (h_sampled_block_indep : iIndepFun sampled_block μ) (h_sampled_block_uniform : ∀ n (i : ι), μ ((sampled_block n) ⁻¹' {i}) = 1 / (N : ℝ≥0∞)) (h_diameter_bound : ∀ {u v : X}, u ∈ effective_domain (PiLp.separableSum g) → v ∈ effective_domain (PiLp.separableSum g) → ‖u - v‖_[Li] ≤ Ω) : (∀ k : ℕ, 1 ≤ k → μ[fun ω ↦ (F (x k ω)).toReal] - F_opt_real ≤ ((2 : ℝ) * rateBound) / ((k + 2 * N - 2 : ℕ) : ℝ)) ∧ ∀ k : ℕ, 3 ≤ k → sInf ((fun n ↦ μ[fun ω ↦ (Sᵇ[g, blockGradient f](x n ω)).toReal]) '' Set.Icc (k / 2 + 2) k) ≤ ((8 : ℝ) * rateBound) / ((k - 2 : ℕ) : ℝ)

Supporting modules

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

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

Source header · Attribution source

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

Source header · Attribution source

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

Source header · Attribution source

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

Source header · Attribution source

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

Source header · Attribution source

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

Source header · Attribution source

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