Chapter 09 — Mirror Descent

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

Definition 9.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 9.1: the standing assumptions (A)-(D) for (P) := min {f(x) : x ∈ C} are the existing owner class IsConstrainedConvexProblem, which packages that f : E → (-∞, ∞] is proper, closed, and convex, that C is nonempty, closed, convex, and contained in interior (dom(f)), and that the optimal set X^* is nonempty with optimal value f_opt.

recall IsConstrainedConvexProblem

Text 9.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 9.1, specialized at a fixed pair (x, y): if ω is strictly convex on D and differentiable at y ∈ D, then the associated Bregman distance from x to y is nonnegative, and it vanishes exactly on the diagonal.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem bregmanDistance_nonneg_and_eq_zero_iff (ω : E → ℝ) (D : Set E) (hω : StrictConvexOn ℝ D ω) {x y : E} (hx : x ∈ D) (hy : y ∈ D) (hy_diff : DifferentiableAt ℝ ω y) : 0 ≤ B[ω] x y ∧ (B[ω] x y = 0 ↔ x = y)

Definition 9.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 9.2: a Bregman potential on C yields the constrained-potential strong-convexity statement for ω + δ_C on its effective domain, matching the textbook package of standing assumptions via the canonical constrained-potential view.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem IsBregmanPotentialOn.strongConvexOn_add_indicator {ω : E → EReal} {C : Set E} {σ : ℝ} (hω : IsBregmanPotentialOn ω C σ) : StrongConvexOn (effective_domain (ω + δ_ C)) σ (fun x ↦ ((ω + δ_ C) x).toReal)

Text 9.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 9.2: there exists a strictly convex function and two points for which the Bregman distance is asymmetric.

open scoped Gradient theorem exists_strictly_convex_bregman_asymmetric_pair : ∃ (ω : ℝ → ℝ) (x y : ℝ), StrictConvexOn ℝ Set.univ ω ∧ B[ω] x y ≠ B[ω] y x

Definition 9.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 9.3: sequences of iterates x, stepsizes t, and chosen Euclidean subgradients g follow the Mirror Descent Method for objective f, mirror map ω, and feasible set C when for every iteration k, the current iterate lies in C ∩ dom(∂ ω), the chosen vector g k belongs to ∂ f(x^k), the stepsize t k is positive, and the next iterate x^(k+1) minimizes the mirror-descent update objective y ↦ ⟪t_k g_k - ∇ ω(x^k), y⟫ + ω(y) over C.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def is_mirror_descent_trajectory (f ω : E → ℝ) (C : Set E) (x g : ℕ → E) (t : ℕ → ℝ) : Prop := ∀ k, x k ∈ C ∩ subdifferential_domain ω.toEReal ∧ g k ∈ euclideanSubdifferentialAt f (x k) ∧ 0 < t k ∧ IsMinOn (mirror_descent_update_objective ω (x k) (g k) (t k)) C (x (k + 1)) -- Proof sketch: specialize the defining universal clause in -- `is_mirror_descent_trajectory f ω C x g t` at the iteration index `k`.

Lemma 9.3

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

Source header · Attribution source

Lemma 9.3: if ω.toReal has gradients ωa at a and ωb at b, then the associated three-point identity for the Chapter 9 Bregman distance is ⟪ωb - ωa, c - a⟫ = B_ω(c, a) + B_ω(a, b) - B_ω(c, b).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {ω : E → EReal} {a b c : E} theorem bregman_three_point_identity {ωa ωb : E} (ha : HasGradientAt (fun x ↦ (ω x).toReal) ωa a) (hb : HasGradientAt (fun x ↦ (ω x).toReal) ωb b) : inner ℝ (ωb - ωa) (c - a) = B[ω] c a + B[ω] a b - B[ω] c b

Text 9.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 9.3: the Bregman distance need not satisfy the triangle inequality; a strictly convex generator on the positive reals already gives a counterexample.

open scoped Gradient theorem exists_strictly_convex_bregman_triangle_counterexample : ∃ ω : ℝ → ℝ, StrictConvexOn ℝ (Set.Ioi (0 : ℝ)) ω ∧ ∃ x y z : ℝ, 0 < x ∧ 0 < y ∧ 0 < z ∧ B[ω] x z > B[ω] x y + B[ω] y z

Definition 9.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 9.4: clauses (A)-(D) for the composite mirror-descent problem min_x {F(x) = f(x) + g(x)} mean the core composite-convex assumptions together with the bounded-subgradient clause that every continuous-dual subgradient of f at every point of dom(g) has norm at most L_f > 0.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class IsCompositeMirrorDescentProblem (f g : E → EReal) (XStar : Set E) (FOpt Lf : ℝ) : Prop extends IsCompositeConvexMinimizationProblem f g XStar FOpt where Lf_pos : 0 < Lf subgradient_norm_le {x : E} {s : StrongDual ℝ E} (hx : x ∈ effective_domain g) (hs : s ∈ strongDualSubdifferential f x) : ‖s‖ ≤ Lf

Lemma 9.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 9.4 (1): if ω is a Bregman potential on C, then for every x ∈ C and every y ∈ C ∩ dom(∂ ω) where x ↦ (ω x).toReal is ambiently differentiable at y, the associated Bregman distance dominates the quadratic term (σ / 2) ‖x - y‖².

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {C : Set E} {ω : E → EReal} {σ : ℝ} theorem bregmanDistance_lower_quadratic_bound (hω : IsBregmanPotentialOn ω C σ) (x y : E) (hx : x ∈ C) (hyC : y ∈ C) (hy_subgrad : y ∈ subdifferential_domain ω) (hy_diff : DifferentiableAt ℝ (fun z ↦ (ω z).toReal) y) : B[ω] x y ≥ (σ / 2) * ‖x - y‖ ^ (2 : ℕ)

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

Text 9.4: letting ω̃ = ω + δ_C, if C is closed, hω : IsBregmanPotentialOn ω C σ, and x^k ∈ C ∩ dom(∂ ω), then the mirror-descent update step, encoded in Lean as x⁺ ∈ C ∧ IsMinOn (mirror_descent_update_objective ((fun y ↦ (ω y).toReal)) x^k g_f t) C x⁺, is equivalent to the source-facing conjugate formula x⁺ = ∇ ω̃∗(∇ω(x^k) - t g_f), expressed in Lean via the real-valued restriction of ω̃∗.

open InnerProductSpace (toDualMap) open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {ω : E → EReal} {C : Set E} {σ : ℝ} {xk xNext gradf : E} {t : ℝ} theorem mirror_descent_step_isMinOn_iff_eq_gradient_conjugate_add_indicator (hC_closed : IsClosed C) (hω : IsBregmanPotentialOn ω C σ) (hxk : xk ∈ C ∩ subdifferential_domain ω) : (xNext ∈ C ∧ IsMinOn (mirror_descent_update_objective (fun y ↦ (ω y).toReal) xk gradf t) C xNext) ↔ xNext = ∇ (fun y ↦ ((((ω + δ_ C)∗) y).toReal)) (∇ (fun y ↦ (ω y).toReal) xk - t • gradf)

Definition 9.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 9.5: in the composite model, the standing assumptions on the mirror map ω are exactly that ω is a Bregman potential on dom(g) = effective_domain g with modulus σ.

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

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

Text 9.5: in a real inner-product space, hence in particular in Euclidean space, choosing the mirror map ω(x) = ‖x‖² / 2, for which ∇ω(x) = x, turns the mirror-descent one-step minimization into the projected subgradient one-step minimization of the half squared distance to x - t • g. Equivalently, the two objectives have the same minimizers on the feasible set C.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] local notation "ω₂" => (fun z : E ↦ ‖z‖ ^ (2 : ℕ) / 2) theorem mirror_descent_half_squared_norm_step_iff_projected_subgradient_step (C : Set E) (x g xNext : E) (t : ℝ) : IsMinOn (mirror_descent_update_objective ω₂ x g t) C xNext ↔ IsMinOn (fun y : E ↦ ‖y - (x - t • g)‖ ^ (2 : ℕ) / 2) C xNext

Definition 9.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 9.6: sequences of iterates x, chosen subgradients s, and stepsizes t follow the Mirror-C Method for the composite objective f + g with mirror map ω when at every iteration k the current iterate lies in dom(g) ∩ dom(∂ ω), the chosen functional s k belongs to ∂ₛ f(x^k), the stepsize t k is positive, and the next iterate x^(k+1) minimizes the explicit Mirror-C objective from equation (9.32) over all x.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] def is_mirror_c_trajectory (f g ω : E → EReal) (x : ℕ → E) (s : ℕ → StrongDual ℝ E) (t : ℕ → ℝ) : Prop := ∀ k, x k ∈ effective_domain g ∩ subdifferential_domain ω ∧ s k ∈ ∂ₛ f(x k) ∧ 0 < t k ∧ IsMinOn (mirror_c_update_objective g ω (x k) (s k) (t k)) Set.univ (x (k + 1)) -- Proof sketch: specialize the defining universal clause in -- `is_mirror_c_trajectory f g ω x s t` at the iteration index `k`.

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

Text 9.6: on the unit simplex, a feasible minimizer of the Chapter 9 mirror-descent subproblem for the negative-entropy mirror map is the canonical softmax point of the shifted log-weights i ↦ log (x_i) - t g_i, hence coordinatewise the exponentiated-gradient formula x_i^+ = x_i * exp (-t g_i) / ∑_j x_j * exp (-t g_j).

open scoped BigOperators Gradient variable {n : ℕ} local notation "Δ" => stdSimplex ℝ (Fin n) local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Δ₂" => (Set.preimage (WithLp.ofLp : E → Fin n → ℝ) Δ : Set E) theorem mirror_descent_step_eq_exponentiated_gradient (x g xNext : E) (t : ℝ) (hx : x ∈ Δ₂) (hx_pos : ∀ i, 0 < x i) : xNext ∈ Δ₂ ∧ IsMinOn (mirror_descent_update_objective (fun z : E ↦ (negative_entropy_function n z).toReal) x g t) Δ₂ xNext ↔ xNext.ofLp = softmax_point (fun i ↦ Real.log (x i) - t * g i)

Lemma 9.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 9.7: if ω is a Bregman potential on dom(ψ) and ψ is proper, closed, and convex, and the intrinsic interiors of dom(ψ) and dom(ω) intersect, then the composite problem min_x {ψ(x) + ω(x)} has a unique minimizer, and that minimizer lies in dom(ψ) ∩ dom(∂ ω).

universe u open scoped Pointwise variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] variable {ψ ω : E → EReal} {σ : ℝ} theorem existsUnique_composite_minimizer_mem_domains (hω : IsBregmanPotentialOn ω (effective_domain ψ) σ) (hψ_proper : IsProperExtendedRealFunction ψ) (hψ_closed : LowerSemicontinuous ψ) (hψ_convex : is_convex_function ψ) (hqual : (intrinsicInterior ℝ (effective_domain ψ) ∩ intrinsicInterior ℝ (effective_domain ω)).Nonempty) : ∃! xStar : E, IsMinOn (fun x ↦ ψ x + ω x) Set.univ xStar ∧ xStar ∈ effective_domain ψ ∩ subdifferential_domain ω

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

Text 9.7: with α = Theta0, β = Lf ^ 2 / (2 * σ), and m = N + 1, the mirror-descent fixed-iteration bound is minimized by the constant stepsize √(2 * Theta0 * σ) / (Lf * √(N + 1)), and the attained value is Lf * √(2 * Theta0) / √(σ * (N + 1)), which is the explicit O(1 / √N) bound.

theorem mirror_descent_optimal_constant_stepsize_minimizes_fixed_iteration_bound (Theta0 Lf σ : ℝ) (N : ℕ) (hTheta0 : 0 < Theta0) (hLf : 0 < Lf) (hσ : 0 < σ) : IsMinOn (fixed_iteration_objective Theta0 (Lf ^ 2 / (2 * σ))) {t : Fin (N + 1) → ℝ | ∀ i, 0 < t i} (mirror_descent_textbook_stepsize Theta0 Lf σ N) ∧ fixed_iteration_objective Theta0 (Lf ^ 2 / (2 * σ)) (mirror_descent_textbook_stepsize Theta0 Lf σ N) = Lf * Real.sqrt (2 * Theta0) / Real.sqrt (σ * (N + 1 : ℝ))

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

Text 9.8: for mirror descent on the Euclidean simplex with mirror map ω(x) = ‖x‖₂² / 2, uniform initialization x⁰ = (1 / n)e, and constant stepsizes t_k = √2 / (L_{f,2} √(N + 1)) on the first N + 1 iterations, the running-best objective gap is bounded by √2 L_{f,2} / √(N + 1), with L_{f,2} represented here by h_bound.L_f.

universe u open InnerProductSpace (toDualMap) open WithLp (toLp) variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Δ" => (toLp 2 '' (stdSimplex ℝ (Fin n) : Set (Fin n → ℝ)) : Set E) local notation "ω" => ((fun z : E ↦ ‖z‖ ^ (2 : ℕ) / 2) : E → ℝ) local notation "ωₑ" => Function.toEReal ω variable {f : EuclideanSpace ℝ (Fin n) → EReal} variable {XStar : Set (EuclideanSpace ℝ (Fin n))} {fOpt : ℝ} variable (h_problem : IsConstrainedConvexProblem f Δ XStar fOpt) variable (h_bound : SubgradientNormBoundOn f (toLp 2 '' (stdSimplex ℝ (Fin n) : Set (Fin n → ℝ)) : Set (EuclideanSpace ℝ (Fin n)))) -- Proof sketch: apply Theorem 9.16 to the Euclidean mirror map `ω(x) = ‖x‖² / 2` on the simplex -- `Δ`, use `half_squared_norm_isBregmanPotentialOn_simplex` for the Bregman-potential owner, and -- bound the initial Bregman term by `1` via -- `half_squared_norm_bregman_le_one_of_mem_simplex` at the optimal point `xStar ∈ XStar ⊆ Δ`. -- With `σ = 1`, `Θ₀ = 1`, and the constant stepsize -- `t_k = √2 / (L_{f,2} √(N + 1))`, Theorem 9.16 reduces exactly to the displayed estimate. theorem euclidean_simplex_mirror_descent_best_value_gap_le (hn : 0 < n) {x g : ℕ → EuclideanSpace ℝ (Fin n)} {t : ℕ → ℝ} (h_problem : IsConstrainedConvexProblem f Δ XStar fOpt) (h_traj : is_mirror_descent_trajectory (fun y ↦ (f y).toReal) ω Δ x g t) {xStar : EuclideanSpace ℝ (Fin n)} (hxStar : xStar ∈ XStar) (hx0 : x 0 = (uniform_simplex_point hn : EuclideanSpace ℝ (Fin n))) {N : ℕ} (h_stepsize : ∀ k : Fin (N + 1), t k = Real.sqrt 2 / (h_bound.L_f * Real.sqrt (N + 1 : ℝ))) : best_achieved_function_value (fun y ↦ (f y).toReal) x N - fOpt ≤ Real.sqrt 2 * h_bound.L_f / Real.sqrt (N + 1 : ℝ)

Theorem 9.8

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

Source header · Attribution source

Theorem 9.8: if C is nonempty, closed, and convex, ω is a Bregman potential on C, and intrinsicInterior ℝ C ∩ intrinsicInterior ℝ (effective_domain ω) is nonempty, then for every dual vector a, the constrained problem min_{x ∈ C} {⟨a, x⟩ + ω(x)} has a unique minimizer, and that minimizer lies in C ∩ dom(∂ ω).

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {C : Set E} {ω : E → EReal} {σ : ℝ} variable [FiniteDimensional ℝ E] theorem existsUnique_mirror_descent_problem_minimizer_mem_domains (a : StrongDual ℝ E) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (hω : IsBregmanPotentialOn ω C σ) (hqual : (intrinsicInterior ℝ C ∩ intrinsicInterior ℝ (effective_domain ω)).Nonempty) : ∃! xStar : E, IsMinOn (fun x ↦ ((a x : ℝ) : EReal) + ω x) C xStar ∧ xStar ∈ C ∩ subdifferential_domain ω

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

Text 9.9: the simplex negative-entropy mirror-descent estimate before optimizing the constant stepsize. If the chosen simplex mirror-descent trajectory starts at x⁰ = (1 / n)e and its selected subgradients satisfy ‖g_k‖_∞ ≤ L_{f,∞} on the first N + 1 iterations, then the running-best objective value gap is bounded by the fixed-iteration mirror-descent objective with Θ₀ = log n and σ = 1.

open WithLp (toLp) variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "E₁" => WithLp 1 (Fin n → ℝ) local notation "Δ" => (toLp 2 '' (stdSimplex ℝ (Fin n) : Set (Fin n → ℝ)) : Set E) local notation "Δ₁" => (Set.preimage (WithLp.ofLp : E₁ → Fin n → ℝ) (stdSimplex ℝ (Fin n)) : Set E₁) local notation "ωₑ" => negative_entropy_function n theorem simplex_negative_entropy_best_value_gap_le_fixed_iteration_objective (hn : 0 < n) {f : E → EReal} {XStar : Set E} {fOpt LfInf : ℝ} (h_problem : IsConstrainedConvexProblem f Δ XStar fOpt) {x g : ℕ → E} {t : ℕ → ℝ} (h_traj : is_mirror_descent_trajectory (fun y ↦ (f y).toReal) (fun y ↦ (negative_entropy_function n y).toReal) Δ x g t) (hx0 : x 0 = (uniform_simplex_point hn : E)) {N : ℕ} (h_subgrad_bound : ∀ k : Fin (N + 1), ‖toLp ⊤ (fun i ↦ g k i)‖ ≤ LfInf) : best_achieved_function_value (fun y ↦ (f y).toReal) x N - fOpt ≤ fixed_iteration_objective (Real.log (n : ℝ)) (LfInf ^ 2 / 2) (fun k : Fin (N + 1) ↦ t k)

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

Text 9.10: the Mirror-C update formula can be rewritten from the linearized objective in equation (9.32) to the Bregman-distance objective in equation (9.33) without changing the set of minimizers on the finite-valued domain of ω, provided the chosen minimizer itself lies in that domain.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem isMinOn_mirror_c_update_objective_iff_isMinOn_bregman_form (g ω : E → EReal) (xk xNext : E) (s : StrongDual ℝ E) (t : ℝ) (hxNext : xNext ∈ finite_domain ω) : IsMinOn (mirror_c_update_objective g ω xk s t) (finite_domain ω) xNext ↔ IsMinOn (fun x ↦ Real.toEReal (t * s x) + (t : EReal) * g x + Real.toEReal (B[ω] x xk)) (finite_domain ω) xNext

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

Text 9.11 (1): in a Euclidean space with distance-generating function ω(x) = ‖x‖² / 2, the one-step Mirror-C update is exactly the proximal subgradient update. Equivalently, the next iterate minimizes the Mirror-C objective if and only if it belongs to the proximal set of the scaled nonsmooth term (t : EReal) • g at the forward-subgradient point xk - t • f'(xk).

open InnerProductSpace (toDualMap) universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] local notation "ω₂" => (fun z : E ↦ (((‖z‖ ^ (2 : ℕ) / 2 : ℝ) : EReal))) theorem isMinOn_mirror_c_half_squared_norm_update_iff_mem_scaled_prox (g : E → EReal) (xk gradf xNext : E) (t : ℝ) : IsMinOn (mirror_c_update_objective g ω₂ xk (toDualMap ℝ E gradf) t) Set.univ xNext ↔ xNext ∈ prox[((t : EReal) • g)] (xk - t • gradf)

Theorem 9.12

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

Source header · Attribution source

Theorem 9.12: under the intrinsic-interior qualification, a minimizer of secondProxObjective ψ ω b lies in dom(∂ω) and satisfies the variational inequality (9.16) at every point of dom(ψ).

open Filter open InnerProductSpace (toDualMap) open scoped Pointwise Topology Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {ψ ω : E → EReal} {σ : ℝ} {a b : E} variable (hω : IsBregmanPotentialOn ω (effective_domain ψ) σ) variable (hω_diff : ∀ x ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun z ↦ (ω z).toReal) x) variable (hψ_proper : IsProperExtendedRealFunction ψ) (hψ_convex : is_convex_function ψ) variable (hb : b ∈ subdifferential_domain ω) variable (ha : IsMinOn (secondProxObjective ψ ω b) Set.univ a) include hω hω_diff hψ_proper hb ha include hψ_convex namespace SecondProxObjective theorem minimizer_spec (hqual : (intrinsicInterior ℝ (effective_domain ψ) ∩ intrinsicInterior ℝ (effective_domain ω)).Nonempty) : a ∈ subdifferential_domain ω ∧ ∀ u ∈ effective_domain ψ, inner ℝ (∇ (fun x ↦ (ω x).toReal) b - ∇ (fun x ↦ (ω x).toReal) a) (u - a) ≤ ψ u - ψ a

Lemma 9.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 9.13: under the standing constrained-problem assumptions of Definition 9.1 and the Bregman-potential assumptions of Definition 9.2, every step of a mirror-descent trajectory satisfies the fundamental inequality t_k (f(x^k).toReal - f_opt) ≤ B_ω(xStar, x^k) - B_ω(xStar, x^(k+1)) + t_k^2 ‖g_k‖^2 / (2σ) for each optimal point xStar ∈ XStar.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f ω : E → EReal} {C XStar : Set E} {fOpt σ : ℝ} variable {x g : ℕ → E} {t : ℕ → ℝ} theorem mirror_descent_fundamental_inequality (h_problem : IsConstrainedConvexProblem f C XStar fOpt) (hω : IsBregmanPotentialOn ω C σ) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (h_traj : is_mirror_descent_trajectory (fun y ↦ (f y).toReal) (fun y ↦ (ω y).toReal) C x g t) {xStar : E} (hxStar : xStar ∈ XStar) (k : ℕ) : t k * ((f (x k)).toReal - fOpt) ≤ B[ω] xStar (x k) - B[ω] xStar (x (k + 1)) + (t k) ^ (2 : ℕ) * ‖g k‖ ^ (2 : ℕ) / (2 * σ)

Lemma 9.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 9.14: under Definition 9.1 for the constrained problem min {f(x) : x ∈ C} and Definition 9.2 for the mirror potential ω, if every subgradient of f on C has norm at most L_f = h_bound.L_f, then for every optimal point xStar ∈ XStar, every mirror-descent trajectory x with positive stepsizes t, and every N, the running-best objective gap satisfies f_best^N - f_opt ≤ (B_ω(xStar, x⁰) + (h_bound.L_f^2 / (2σ)) * ∑_{k=0}^N t_k^2) / ∑_{k=0}^N t_k.

open scoped BigOperators open InnerProductSpace (toDualMap) universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f ω : E → EReal} {C XStar : Set E} {fOpt σ : ℝ} variable {x g : ℕ → E} {t : ℕ → ℝ} theorem mirror_descent_best_value_gap_le (h_problem : IsConstrainedConvexProblem f C XStar fOpt) (hω : IsBregmanPotentialOn ω C σ) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (h_bound : SubgradientNormBoundOn f C) (h_traj : is_mirror_descent_trajectory (fun y ↦ (f y).toReal) (fun y ↦ (ω y).toReal) C x g t) {xStar : E} (hxStar : xStar ∈ XStar) (N : ℕ) : best_achieved_function_value (fun y ↦ (f y).toReal) x N - fOpt ≤ (B[ω] xStar (x 0) + (h_bound.L_f ^ (2 : ℕ) / (2 * σ)) * Finset.sum (Finset.range (N + 1)) (fun k ↦ (t k) ^ (2 : ℕ))) / Finset.sum (Finset.range (N + 1)) (fun k ↦ t k)

Lemma 9.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 9.15: for positive α and β, the ratio (α + β * ∑ i, t i ^ 2) / (∑ i, t i) is minimized over positive step sizes by the constant choice t_i = √(α / (β |ι|)). Specializing to ι = Fin m recovers the textbook m-step statement.

open scoped BigOperators variable {ι : Type*} [Fintype ι] theorem fixed_iteration_objective_minimized_by_uniform_steps [Nonempty ι] {α β : ℝ} (hα : 0 < α) (hβ : 0 < β) : IsMinOn (fixed_iteration_objective α β) {t : ι → ℝ | ∀ i, 0 < t i} (fixed_iteration_uniform_steps ι α β)

Theorem 9.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 9.16: under the standing constrained-problem assumptions of Definition 9.1 and the Bregman-potential assumptions of Definition 9.2, if every subgradient of f on C has norm at most L_f = h_bound.L_f, if some optimizer xStar ∈ X^* satisfies B_ω(xStar, x⁰) ≤ Theta0, and if the mirror descent stepsizes are fixed to √(2 * Theta0 * σ) / (L_f * √(N + 1)) on the first N + 1 iterations, equivalently if the restricted prefix n ↦ t n on Fin (N + 1) agrees with mirror_descent_textbook_stepsize Theta0 h_bound.L_f σ N, then the running-best objective gap after N iterations is bounded by the standard O(1 / √N) estimate.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f ω : E → EReal} {C XStar : Set E} {fOpt σ : ℝ} variable {x g : ℕ → E} {t : ℕ → ℝ} theorem mirror_descent_best_value_gap_le_one_div_sqrt_of_constant_stepsizes (h_problem : IsConstrainedConvexProblem f C XStar fOpt) (hω : IsBregmanPotentialOn ω C σ) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (h_bound : SubgradientNormBoundOn f C) (h_traj : is_mirror_descent_trajectory (fun y ↦ (f y).toReal) (fun y ↦ (ω y).toReal) C x g t) (Theta0 : ℝ) {xStar : E} (hxStar : xStar ∈ XStar) {N : ℕ} (h_bregman_upper : B[ω] xStar (x 0) ≤ Theta0) (h_stepsize : (fun n : Fin (N + 1) ↦ t n) = mirror_descent_textbook_stepsize Theta0 h_bound.L_f σ N) : best_achieved_function_value (fun y ↦ (f y).toReal) x N - fOpt ≤ h_bound.L_f * Real.sqrt (2 * Theta0) / Real.sqrt (σ * (N + 1 : ℝ))

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

Theorem 9.18 (1): under the standing constrained mirror-descent assumptions of Definitions 9.1 and 9.2, if every subgradient of f on C has norm at most L_f = h_bound.L_f and (∑_{n=0}^k t_n^2) / (∑_{n=0}^k t_n) → 0, then the running-best objective value attained by the mirror-descent iterates converges to the optimal value fOpt.

open scoped BigOperators open InnerProductSpace (toDualMap) universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f ω : E → EReal} {C XStar : Set E} {fOpt σ : ℝ} variable {x g : ℕ → E} {t : ℕ → ℝ} theorem mirror_descent_best_value_tendsto_of_stepsize_ratio (h_problem : IsConstrainedConvexProblem f C XStar fOpt) (hω : IsBregmanPotentialOn ω C σ) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (h_bound : SubgradientNormBoundOn f C) (h_traj : is_mirror_descent_trajectory (fun y ↦ (f y).toReal) (fun y ↦ (ω y).toReal) C x g t) (h_ratio : Filter.Tendsto (fun k ↦ (Finset.sum (Finset.range (k + 1)) fun n ↦ (t n) ^ (2 : ℕ)) / (Finset.sum (Finset.range (k + 1)) fun n ↦ t n)) Filter.atTop (nhds 0)) : Filter.Tendsto (fun k ↦ best_achieved_function_value (fun y ↦ (f y).toReal) x k) Filter.atTop (nhds fOpt)

Theorem 9.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 9.24: if g is proper, closed, and convex, and ω is a Bregman potential on dom(g), and intrinsicInterior ℝ (dom(g)) ∩ intrinsicInterior ℝ (dom(ω)) is nonempty, then the Mirror-C auxiliary problem min_x {⟨a, x⟩ + g(x) + ω(x)} has a unique minimizer in dom(g) ∩ dom(∂ ω).

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {g ω : E → EReal} {σ : ℝ} variable [FiniteDimensional ℝ E] -- Proof sketch: specialize the domain-membership companion from Lemma 9.7 to the perturbed -- objective `x ↦ ((a x : ℝ) : EReal) + g x`, using that a continuous linear functional is finite -- everywhere and preserves the effective domain and convexity hypotheses of `g`. theorem existsUnique_mirror_c_problem_minimizer_mem_domains (a : StrongDual ℝ E) (hω : IsBregmanPotentialOn ω (effective_domain g) σ) (hqual : (intrinsicInterior ℝ (effective_domain g) ∩ intrinsicInterior ℝ (effective_domain ω)).Nonempty) (hg_proper : IsProperExtendedRealFunction g) (hg_closed : LowerSemicontinuous g) (hg_convex : is_convex_function g) : ∃! xStar : E, IsMinOn (fun x ↦ ((a x : ℝ) : EReal) + g x + ω x) Set.univ xStar ∧ xStar ∈ effective_domain g ∩ subdifferential_domain ω

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

Lemma 9.25: under the composite convex minimization assumptions extracted from Definition 9.4, together with the mirror-map assumptions of Definition 9.5 and the Mirror-C trajectory data of Definition 9.6, if g is nonnegative on dom(g) and the Mirror-C stepsizes are nonincreasing, then for every optimal point xStar ∈ XStar = X^* and every iteration index k, the running-best composite objective gap up to time k is bounded by the weighted ratio (t₀ g(x⁰) + B_ω(xStar, x⁰) + (1 / (2σ)) * ∑_{n=0}^k t_n^2 ‖f'(x^n)‖^2) / ∑_{n=0}^k t_n.

universe u open Filter open scoped BigOperators Topology open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g ω : E → EReal} {XStar : Set E} {FOpt σ : ℝ} variable {x : ℕ → E} {s : ℕ → StrongDual ℝ E} {t : ℕ → ℝ} theorem mirror_c_best_value_gap_le (h_problem : IsCompositeConvexMinimizationProblem f g XStar FOpt) (hω : IsBregmanPotentialOn ω (effective_domain g) σ) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (h_nonneg : ∀ z ∈ effective_domain g, 0 ≤ g z) (h_traj : is_mirror_c_trajectory f g ω x s t) (h_stepsize_antitone : Antitone t) {xStar : E} (hxStar : xStar ∈ XStar) (k : ℕ) : best_achieved_function_value (fun y ↦ (f y + g y).toReal) x k - FOpt ≤ ((t 0) * (g (x 0)).toReal + B[ω] xStar (x 0) + (1 / (2 * σ)) * Finset.sum (Finset.range (k + 1)) (fun n ↦ (t n) ^ (2 : ℕ) * ‖s n‖ ^ (2 : ℕ))) / Finset.sum (Finset.range (k + 1)) (fun n ↦ t n)

Theorem 9.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 9.26: under the standing composite mirror-descent assumptions of Definition 9.4 together with Definitions 9.5 and 9.6, if g is nonnegative on dom(g), if some optimizer xStar ∈ X^* satisfies B[ω](xStar, x⁰) ≤ Theta0, if g(x⁰) = 0, and if the first N Mirror-C stepsizes are given by the textbook constant value √(2 * Theta0 * σ) / (Lf * √N), equivalently by the canonical finite-horizon uniform family from Lemma 9.15, then after N iterations the best objective value attained among x⁰, …, x^(N-1) satisfies the fixed-horizon O(1 / √N) estimate.

universe u open scoped BigOperators variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g ω : E → EReal} {XStar : Set E} {FOpt Lf σ : ℝ} variable {x : ℕ → E} {s : ℕ → StrongDual ℝ E} {t : ℕ → ℝ} theorem mirror_c_best_value_gap_le_one_div_sqrt_of_constant_stepsizes (h_problem : IsCompositeMirrorDescentProblem f g XStar FOpt Lf) (hω : IsBregmanPotentialOn ω (effective_domain g) σ) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (h_nonneg : ∀ z ∈ effective_domain g, 0 ≤ g z) (h_g0 : g (x 0) = 0) (h_traj : is_mirror_c_trajectory f g ω x s t) (Theta0 : ℝ) {xStar : E} (hxStar : xStar ∈ XStar) {N : ℕ} (hN : 0 < N) (h_bregman_upper : B[ω] xStar (x 0) ≤ Theta0) (h_stepsize : ∀ n : Fin N, t n = Real.sqrt (2 * Theta0 * σ) / (Lf * Real.sqrt (N : ℝ))) : best_achieved_function_value (fun y : E ↦ (f y + g y).toReal) x (N - 1) - FOpt ≤ Lf * Real.sqrt (2 * Theta0) / (Real.sqrt σ * Real.sqrt (N : ℝ))

Theorem 9.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 9.27: under the composite mirror-descent assumptions of Definitions 9.4, 9.5, and 9.6, if g is nonnegative on dom(g) and the Mirror-C stepsizes are given by the canonical diminishing family mirror_descent_predefined_diminishing_stepsize Lf σ, equivalently by the textbook rule t_k = √(2 σ) / (L_f √(k + 1)), then for every k ≥ 1 the running-best composite objective gap is bounded by the O(log k / √k) estimate `(L_f / √(2 σ)) * (B[ω] xStar x⁰ + (√(2 σ) / L_f) g(x⁰) + 1 + log (k + 1)) / √(k + 1)`.

universe u open scoped BigOperators variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f g ω : E → EReal} {XStar : Set E} {FOpt Lf σ : ℝ} variable {x : ℕ → E} {s : ℕ → StrongDual ℝ E} {t : ℕ → ℝ} theorem mirror_c_best_value_gap_le_log_over_sqrt_of_predefined_diminishing_stepsizes (h_problem : IsCompositeMirrorDescentProblem f g XStar FOpt Lf) (hω : IsBregmanPotentialOn ω (effective_domain g) σ) (hω_diff : ∀ z ∈ subdifferential_domain ω, DifferentiableAt ℝ (fun w ↦ (ω w).toReal) z) (h_nonneg : ∀ z ∈ effective_domain g, 0 ≤ g z) (h_traj : is_mirror_c_trajectory f g ω x s t) {xStar : E} (hxStar : xStar ∈ XStar) {k : ℕ} (hk : 1 ≤ k) (h_stepsize : t = mirror_descent_predefined_diminishing_stepsize Lf σ) : best_achieved_function_value (fun y ↦ (f y + g y).toReal) x k - FOpt ≤ (Lf / Real.sqrt (2 * σ)) * (B[ω] xStar (x 0) + (Real.sqrt (2 * σ) / Lf) * (g (x 0)).toReal + 1 + Real.log ((k : ℝ) + 1)) / Real.sqrt ((k : ℝ) + 1)

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