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.
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 IsConstrainedConvexProblemText 9.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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 xDefinition 9.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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 bText 9.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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 zDefinition 9.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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‖ ≤ LfLemma 9.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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.
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 xNextDefinition 9.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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.
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.
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.
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.
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.
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 ω) xNextText 9.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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 - ψ aLemma 9.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
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.
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.
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.
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.
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.
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.
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.
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.
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.
-
MirrorDescentStepsize.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
Theorem_9_12/Linearized.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
Theorem_9_12/Objective.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.