Chapter 06 — The Primal-Dual Model of an Objective Function
Proofs omitted. Hover over highlighted terms to see their Lean types.
Algorithm 6.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Algorithm 6.1: the method of similar triangles for minimizing f + Ψ over a closed convex set Q with a chosen L-Lipschitz gradient field and a differentiable 1-strongly convex prox-function is iterate data over the chapter's canonical CompositeLipschitzGradientModel. Its primitive data are the iterate sequence x_k, feasible minimizers v_k of the estimating functions φ_k, the initialization x₀ = v₀, φ₀(x) = L d(x), the estimating-function recursion at y_k = (k / (k + 2)) x_k + (2 / (k + 2)) v_k, and the update x_{k+1} = (k / (k + 2)) x_k + (2 / (k + 2)) v_{k+1}.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
structure SimilarTrianglesMethod
(model : CompositeLipschitzGradientModel E) (x0 : model.feasibleSet) where
/-- The iterate sequence `x₀, x₁, x₂, ...`. -/
x : ℕ → E
/-- The minimizers `v₀, v₁, v₂, ...` of the estimating functions. -/
v : ℕ → model.feasibleSet
/-- The estimating functions `φ₀, φ₁, φ₂, ...`. -/
φ : ℕ → E → WithTop ℝ
/-- The initial iterate is the prescribed point `x₀`. -/
x_zero : x 0 = x0
/-- The initial estimating-sequence minimizer is `v₀ = x₀`. -/
v_zero : v 0 = x0
/-- The initial estimating function is `φ₀(x) = L d(x)`. -/
phi_zero :
φ 0 = fun z ↦ (((model.L : ℝ) * model.proxFunction z : ℝ) : WithTop ℝ)
/-- Each `v_{k+1}` minimizes the updated estimating function `φ_{k+1}` on the feasible set. -/
v_succ_isMin (k : ℕ) : IsMinOn (φ (k + 1)) model.feasibleSet (v (k + 1))
/-- The estimating functions satisfy the recursive update from the method of similar
triangles. -/
phi_succ (k : ℕ) :
φ (k + 1) =
similarTrianglesEstimatingUpdate model (φ k) k
(similarTrianglesInterpolationPoint k (x k) (v k))
/-- The iterate update is
`x_{k+1} = (k / (k + 2)) x_k + (2 / (k + 2)) v_{k+1}`. -/
x_succ (k : ℕ) : x (k + 1) = similarTrianglesInterpolationPoint k (x k) (v (k + 1))Definition 6.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.1: the Fenchel conjugate of an extended-real function is the pointwise supremum of the affine functionals x ↦ ⟪s, x⟫ - f x; for a proper convex function, this is the textbook Fenchel conjugate.
open Module
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
def fenchelConjugate (f : E → EReal) : Dual ℝ E → EReal :=
fun s ↦ ⨆ x : E, (s x : EReal) - f xLemma 6.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6 1: on ℝⁿ, a proper closed convex function equals the supremum of the affine terms ⟪s, x⟫ - f_*(s) over dom f_* at every x, which is the canonical EReal surface of the textbook max formula.
open scoped ConvexAnalysis WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
namespace ClosedConvexFunction
theorem fenchelMoreau_eq_sSup_inner_sub_fenchelDual
{n : ℕ} {f : EuclideanSpace ℝ (Fin n) → WithTop ℝ} (hf : ClosedConvexFunction f)
(hdom : (dom f).Nonempty) (x : EuclideanSpace ℝ (Fin n)) :
withTopToEReal (f x) =
sSup ((fun s : EuclideanSpace ℝ (Fin n) ↦ (inner ℝ s x : EReal) - (f⋆) s) '' dom (f⋆))Proposition 6.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.1: if a real-valued function is bounded above by f 0 + L ‖x‖, then the finite-value domain of its Fenchel conjugate on the continuous dual is contained in the closed dual ball of radius L.
open Metric
open scoped ConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem dom_fenchelConjugate_subset_closedBall_of_upper_linear_growth
(f : E → ℝ) (L : NNReal) (hgrowth : ∀ x : E, f x ≤ f 0 + (L : ℝ) * ‖x‖) :
dom (strongFenchelConjugate f) ⊆ closedBall 0 LTheorem 6.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.1: let Q be a nonempty closed convex set, let phiHat be proper closed convex on Q, and let d2 be continuously differentiable and 1-strongly convex on Q. For μ > 0, if the penalized maximization problem defining smoothedPrimalObjective A Q 0 phiHat d2 μ x has a unique maximizer for every x and uMu selects that maximizer, then the smoothed objective is convex and continuously differentiable, its value at x is attained at uMu x, its derivative at x is A.flip (uMu x), and this derivative field is Lipschitz with constant (1 / μ) * ‖A‖^2.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
variable
(A : E₁ →L[ℝ] StrongDual ℝ E₂)
(Q : Set E₂) (phiHat d2 : E₂ → ℝ) {μ : ℝ}
(uMu : E₁ → E₂)
variable [FiniteDimensional ℝ E₁] [FiniteDimensional ℝ E₂]
theorem nesterovSmoothedObjective_properties
(hQ_nonempty : Q.Nonempty)
(hQ_closed : IsClosed Q)
(hQ_convex : Convex ℝ Q)
(hphi_closed : ClosedConvexOn Q (fun u ↦ (phiHat u : WithTop ℝ)))
(hd2_contDiff : ContDiffOn ℝ 1 d2 Q)
(hd2_strong : StrongConvexOn Q 1 d2)
(hμ : 0 < μ)
(hargmax_unique : ∀ x, ∃! u, u ∈ smoothedPrimalObjectiveArgmax A Q phiHat d2 μ x)
(huMu : ∀ x, uMu x ∈ smoothedPrimalObjectiveArgmax A Q phiHat d2 μ x) :
(∀ x,
smoothedPrimalObjective A Q 0 phiHat d2 μ x =
smoothedPrimalObjectiveMaximand A phiHat d2 μ x (uMu x)) ∧
ConvexOn ℝ Set.univ (smoothedPrimalObjective A Q 0 phiHat d2 μ) ∧
ContDiff ℝ 1 (smoothedPrimalObjective A Q 0 phiHat d2 μ) ∧
(∀ x, HasFDerivAt (smoothedPrimalObjective A Q 0 phiHat d2 μ) (A.flip (uMu x)) x) ∧
LipschitzWith (Real.toNNReal ((1 / μ) * ‖A‖ ^ (2 : ℕ))) (fun x ↦ A.flip (uMu x))Algorithm 6.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Algorithm 6.2: given a positive smoothing parameter μ and a score vector u ∈ ℝ^m, let \bar u = coordinateMaximum u and let centeredByCoordinateMaximum u be the vector obtained by subtracting \bar u from every coordinate of u. Then the log-sum-exp potential is recovered by the numerically stable shift formula η μ u = \bar u + η μ (centeredByCoordinateMaximum u).
open scoped BigOperators
variable {m : ℕ} [NeZero m]
recall eta_eq_coordinateMaximum_add_eta_centeredDefinition 6.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.2: the smooth approximation f_μ attached to f is the supremum over dom (fenchelConjugate f) of the affine functional s ↦ ⟪s, x⟫ - (fenchelConjugate f) s, regularized by (μ / 2) * ‖s‖[B,*]^2 for a nonnegative smoothing parameter μ. The owner lives in EReal, so empty or unbounded supremum sets retain their correct extended-real values; the companion theorem fenchelSmoothApproximation_toReal_eq_of_isMaxOn recovers the textbook real-valued maximum whenever the supremum is attained on dom (fenchelConjugate f).
open Module
open LinearMap (BilinForm)
open LinearMap.BilinForm
open scoped ConvexAnalysis BInducedNorm
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E] [FiniteDimensional ℝ E]
def fenchelSmoothApproximation
(B : BilinForm ℝ E) [Fact B.toQuadraticMap.PosDef]
(f : E → EReal) (μ : NNReal) : E → EReal :=
fun x ↦
sSup (fenchelSmoothApproximationMaximand B f μ x '' dom (fenchelConjugate f))
-- Proof sketch: unfold `fenchelSmoothApproximation`; the right-hand side is exactly the defining
-- supremum formula over `dom (fenchelConjugate f)`.Lemma 6.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2 lies in the chapter's prox-function smoothing / first-order smoothness domain. Sampled owner-style declarations: - smoothedPrimalObjective in Definition_6_30, the chapter's canonical regularized-max smoothing owner, specialized in Theorem_6_1 to zero smooth part; - ContinuousLinearMap.flip in Proposition_6_3, the chapter's canonical transpose owner for A : E₁ →L[ℝ] StrongDual ℝ E₂; - nesterovSmoothedObjective_hasFDerivAt in Theorem_6_1, the canonical derivative identification for the smoothed objective; - smoothedObjective_gradient_lipschitz in Theorem_6_1, the chapter's canonical Lipschitz smoothness theorem for the derivative selection. Best owner abstraction: - source-facing: the prox-smoothed objective f_μ defined by regularized maximization over the feasible dual set; - core/canonical: smoothedPrimalObjective A Q 0 phiHat d2 μ together with A.flip, nesterovSmoothedObjective_hasFDerivAt and smoothedObjective_gradient_lipschitz; - bridge/view: this numbered lemma file, which should only recall the upstream owner theorem pair instead of introducing a second smoothing construction. Primitive data: - the linear map A; - the feasible set Q, dual penalty phiHat, prox-function d2, and smoothing parameter μ; - the maximizer selection uMu; - the positivity, closed-convex, differentiability, and strong-convexity hypotheses already required by Theorem_6_1. Derived API: - the canonical transpose field x ↦ A.flip (uMu x); - the derivative identification nesterovSmoothedObjective_hasFDerivAt; - the Lipschitz smoothness theorem smoothedObjective_gradient_lipschitz. Source/core/bridge triage: - source-facing: Lemma 6.2's smoothness statement for the prox-smoothed objective; - core/canonical: A.flip, nesterovSmoothedObjective_hasFDerivAt, and smoothedObjective_gradient_lipschitz; - bridge/view: this recall-only numbered surface. The previous version introduced an averaging-based Euclidean-ball smoothing operator. That was a different construction from the chapter's structured prox-smoothing objective and duplicated the existing owner theorem. This file now reuses the chapter owner directly, recalling both the derivative identification for f_μ and the Lipschitz estimate for the canonical field x ↦ A.flip (uMu x).
recall nesterovSmoothedObjective_hasFDerivAtProposition 6.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.2: if g ∈ ∂ f(x), then f(x) + f*(g) = ⟪g, x⟫.
open scoped ConvexAnalysis WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem fenchelYoung_equality_of_mem_subdifferential
{f : E → WithTop ℝ} {x g : E} (hg : g ∈ ∂ f(x)) :
withTopToEReal (f x) + (f⋆) g = (inner ℝ g x : EReal)Theorem 6.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.2 [Chapter6_2.json:20]: equation (6.1.20) states that if x_k, y_k, and v_k are generated by method (6.1.19), then for every k ≥ 0 and every feasible point x ∈ Q, ((k (k + 1)) / 4) \tilde f(x_k) + (L / 2) ‖v_k - x‖² ≤ φ_k(x), where \tilde f(x_k) = f(x_k) + Ψ(x_k) is read through the canonical finite-real-part bridge on Q.
open scoped BigOperators
open scoped ConstrainedArgmin
open scoped WithTopConvexAnalysis
universe u
namespace SimilarTrianglesMethod
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {model : CompositeLipschitzGradientModel E} {x0 : model.feasibleSet}
theorem objective_le_estimatingFunction
(method : SimilarTrianglesMethod model x0)
(hx0 : NesterovIsProxCenter model.feasibleSet model.proxFunction (x0 : E))
(k : ℕ) (x : model.feasibleSet) :
(((k : ℝ) * (k + 1)) / 4) *
(model.smoothPart (method k) + withTopRealPart model.nonsmoothPart (method k)) +
((model.L : ℝ) / 2) * ‖(method.v k : E) - x‖ ^ (2 : ℕ) ≤
method.estimatingFunction k xAlgorithm 6.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Algorithm 6.3: given an initial pair ( \bar x₀, \bar u₀ ), initial smoothing parameters μ₁,0, μ₂,0, and the chapter's even and odd update owners, the alternating excessive-gap method is the recursive state sequence that uses the chapter step size τ_k = 2 / (k + 3) and applies the even branch at even indices and the odd branch at odd indices.
universe u v
open StronglyConvexDualUpdate
open scoped ConstrainedArgmin
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
variable {Q₁ : Set E₁} {Q₂ : Set E₂}
variable (hQ₁ : Convex ℝ Q₁) (hQ₂ : Convex ℝ Q₂)
variable {A : E₁ →L[ℝ] StrongDual ℝ E₂}
variable {hatf : E₁ → ℝ} {hatφ : E₂ → ℝ} {d₁ : E₁ → ℝ} {d₂ : E₂ → ℝ}
variable (xμ : ℝ → E₂ → E₁)
variable
(hxμ :
∀ μ : ℝ, ∀ u : E₂,
xμ μ u ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf d₁ μ u))
variable (uμ : ℝ → E₁ → E₂)
variable
(huμ :
∀ μ : ℝ, ∀ x : E₁, x ∈ Q₁ →
uμ μ x ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ x)
variable (x₀ : Q₂ → Q₁) (V : Q₂ → Q₂)
def alternatingExcessiveGapState
(hQ₁ : Convex ℝ Q₁) (hQ₂ : Convex ℝ Q₂)
(xμ : ℝ → E₂ → E₁)
(hxμ :
∀ μ : ℝ, ∀ u : E₂,
xμ μ u ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf d₁ μ u))
(uμ : ℝ → E₁ → E₂)
(huμ :
∀ μ : ℝ, ∀ x : E₁, x ∈ Q₁ →
uμ μ x ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ x)
(x₀ : Q₂ → Q₁) (V : Q₂ → Q₂)
(initialPrimalSmoothing initialDualSmoothing : ℝ)
(initialState : Q₁ × Q₂) : ℕ → Q₁ × Q₂
Definition 6.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.3: the textbook operator norm ‖A‖_{1,2} of a dual-valued map A : E₁ → E₂* is the canonical ambient norm on E₁ →L[ℝ] StrongDual ℝ E₂.
open Metric
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
#check (‖·‖ : (E₁ →L[ℝ] StrongDual ℝ E₂) → ℝ)Lemma 6.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.3 (1): on the simplex owner Δ_n, the ambient normalized entropy formula underlying normalizedEntropyProxFunction n is 1-strongly convex with respect to the canonical ℓ₁ seminorm.
open scoped BigOperators
open scoped StandardSimplex
theorem normalizedEntropyProxFunction_strongConvexOnWith_l1_stdSimplex (n : ℕ+) :
StrongConvexOnWith
(simplexL1Seminorm (n : ℕ)) 1
Δ[n]
(fun x ↦ Real.log (n : ℝ) + entropyFunction (n : ℕ) x)Proposition 6.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.3: the canonical transpose A.flip of a dual-valued continuous linear map has the same operator norm as A.
universe u v w
variable {𝕜 : Type u} [NontriviallyNormedField 𝕜]
variable {E₁ : Type v} {E₂ : Type w}
[NormedAddCommGroup E₁] [NormedSpace 𝕜 E₁]
[NormedAddCommGroup E₂] [NormedSpace 𝕜 E₂]
#check (ContinuousLinearMap.opNorm_flip :
∀ A : E₁ →L[𝕜] StrongDual 𝕜 E₂, ‖A.flip‖ = ‖A‖)Theorem 6.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.3: let μ(N) = 2 ‖A‖ / √(N (N + 1)) * √(D₁ / D₂) and \hat u_N = Finset.univ.centerMass (explicitModelDualAverageWeights N) u. If φ(\hat u_N) ≤ fμ x_N ≤ f x_N, if fμ is a lower smoothing of f with error at most μ(N) D₂ at x_N, and if the smoothed residual gap at (x_N, \hat u_N) is bounded by 4 ‖A‖² D₁ / (μ(N) N (N + 1)) + 4 M D₁ / (N (N + 1)), then 0 ≤ f(x_N) - φ(\hat u_N) ≤ 4 ‖A‖ √(D₁ D₂) / √(N (N + 1)) + 4 M D₁ / (N (N + 1)).
open scoped BigOperators
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
theorem optimized_primal_dual_gap_bound_for_explicit_model_smoothing
(A : E₁ →L[ℝ] StrongDual ℝ E₂) (f fμ : E₁ → ℝ) (φ : E₂ → ℝ)
(N : ℕ+) (xN : E₁) (u : Fin ((N : ℕ) + 1) → E₂)
(D₁ D₂ M : ℝ) (hD₁ : 0 ≤ D₁) (hD₂ : 0 < D₂)
(hxN_approx :
fμ xN ≥ f xN - explicitModelSmoothingParameter A D₁ D₂ N * D₂)
(hφ_le : φ (Finset.univ.centerMass (explicitModelDualAverageWeights N) u) ≤ fμ xN)
(hfμ_le : fμ xN ≤ f xN)
(hsmoothed_gap :
fμ xN - φ (Finset.univ.centerMass (explicitModelDualAverageWeights N) u) ≤
(4 * ‖A‖ ^ (2 : ℕ) * D₁) /
(explicitModelSmoothingParameter A D₁ D₂ N * ((N : ℝ) * ((N : ℝ) + 1))) +
(4 * M * D₁) / ((N : ℝ) * ((N : ℝ) + 1))) :
f xN - φ (Finset.univ.centerMass (explicitModelDualAverageWeights N) u) ∈ Set.Icc 0
((4 * ‖A‖ / Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))) * Real.sqrt (D₁ * D₂) +
(4 * M * D₁) / ((N : ℝ) * ((N : ℝ) + 1)))Algorithm 6.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Algorithm 6.4: a conditional-gradient method for the composite objective f + Ψ on a convex feasible set Q consists of a feasible starting point x₀, step sizes τ_t ∈ (0, 1], the Chapter 6 linear optimization oracle v_Ψ, and a continuous within-gradient field for f on Q. The iterates are then the recursively defined feasible points x_{t+1} = (1 - τ_t) x_t + τ_t v_Ψ(∇_Q f(x_t)), where v_Ψ(∇_Q f(x_t)) ∈ argmin_{x ∈ Q} {⟨∇_Q f(x_t), x⟩ + Ψ(x)}.
open scoped ConstrainedArgmin
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
structure LinearOracleCompositeMethod
(Q : Set E) (f : E → ℝ) (Ψ : Q → ℝ) where
/-- The feasible set `Q` is convex. -/
feasibleSet_convex : Convex ℝ Q
/-- The prescribed starting point `x₀`. -/
x0 : Q
/-- The step-size sequence `τ₀, τ₁, τ₂, ...`. -/
stepSize : ℕ → ℝ
/-- Each step size belongs to `(0, 1]`. -/
stepSize_mem_Ioc : ∀ t : ℕ, stepSize t ∈ Set.Ioc (0 : ℝ) 1
/-- The Chapter 6 linear optimization oracle `v_Ψ`. -/
oracle : StrongDual ℝ E → Q
/-- The oracle values lie in the canonical argmin sets of the linearized composite oracle
objective on `Q`. -/
oracle_spec : IsLinearOptimizationOracle Ψ oracle
/-- The smooth part has the canonical within-gradient at every feasible point. -/
hasGradientWithinAt :
∀ x : Q, HasGradientWithinAt f (gradientWithin f Q x) Q x
/-- The canonical within-gradient field is continuous on the feasible set. -/
gradientWithin_continuousOn : ContinuousOn (gradientWithin f Q) QDefinition 6.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.4: a primal convex minimization problem consists of a nonempty bounded closed convex feasible set Q₁ and a continuous convex objective function f : E → ℝ, considered on Q₁. The textbook item specializes this data to finite-dimensional real ambient spaces.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
structure PrimalConvexMinimizationProblem (E : Type u) [NormedAddCommGroup E]
[NormedSpace ℝ E] extends SetConstrainedMinimizationProblem E where
/-- The feasible set is nonempty, so the minimum-value notation is meaningful. -/
feasibleSet_nonempty : feasibleSet.Nonempty
/-- The feasible set is bounded. -/
feasibleSet_bounded : Bornology.IsBounded feasibleSet
/-- The feasible set is closed. -/
feasibleSet_closed : IsClosed feasibleSet
/-- The objective is continuous on the feasible set. -/
objective_continuous : ContinuousOn objective feasibleSet
/-- The objective is convex on the feasible set. -/
objective_convex : ConvexOn ℝ feasibleSet objectiveLemma 6.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.4: a simplex point maximizes the entropy-regularized linear functional exactly when it is the canonical softmax point u_μ(s).
open scoped BigOperators
open scoped StandardSimplex
variable (m : ℕ+)
local notation "E" => EuclideanSpace ℝ (Fin (m : ℕ))
lemma entropyRegularizedSimplexObjective_isMaxOn_iff
(μ : {μ : ℝ // 0 < μ}) (s : E) (u : Δ[m]) :
IsMaxOn (entropyRegularizedSimplexObjective m μ s) Set.univ u ↔
u = entropySimplexSoftmax m μ sProposition 6.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.4: every structured objective model satisfies the weak-duality inequality f_* ≤ f^*.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
namespace StructuredObjectiveModel
theorem weakDuality
(problem : StructuredObjectiveModel E₁ E₂) :
problem.adjointOptimalValue ≤ problem.primalOptimalValueTheorem 6.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
The chapter excessive-gap condition on a feasible pair (xBar, uBar) is the inequality f_{μ₂}(xBar) ≤ φ_{μ₁}(uBar).
open scoped ConstrainedArgmin Gradient
universe u v
abbrev satisfiesExcessiveGapCondition
{X : Type u} {U : Type v}
(Q₁ : Set X) (Q₂ : Set U)
(fμ₂ : X → ℝ) (φμ₁ : U → ℝ)
(xBar : Q₁) (uBar : Q₂) : Prop :=
fμ₂ xBar ≤ φμ₁ uBarAlgorithm 6.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Algorithm 6.5: for a composite convex minimization problem problem, a contracted-feasible- set trust-region scheme with linear model consists of the canonical within-derivative witness for the inherited smooth part on the feasible set, an initial feasible point x₀, a step-size sequence τ_t ∈ (0, 1], and a chosen one-step rule sending each feasible current iterate x_t to a successor x_{t+1} that minimizes the canonical affine-plus-regularizer model _root_.compositeObjective (fun y ↦ fderivWithin ℝ f Q x_t y) Ψ on the contracted feasible set {(1 - τ_t) x_t + τ_t x | x ∈ Q}.
open scoped ConstrainedArgmin
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
structure ContractedFeasibleSetTrustRegionScheme
(problem : CompositeConvexMinimizationProblem E) (x0 : problem.feasibleSet) where
/-- The inherited smooth part has the canonical within derivative at every feasible point. -/
smoothPart_hasFDerivWithinAt :
∀ x : problem.feasibleSet,
HasFDerivWithinAt problem.smoothPart
(fderivWithin ℝ problem.smoothPart problem.feasibleSet x)
problem.feasibleSet x
/-- The step-size sequence `τ₀, τ₁, τ₂, ...`. -/
stepSize : ℕ → ℝ
/-- Each step size belongs to `(0, 1]`. -/
stepSize_mem_Ioc : ∀ t : ℕ, stepSize t ∈ Set.Ioc (0 : ℝ) 1
/-- The chosen one-step contracted subproblem solver at time `t` and feasible current point
`x_t`. -/
nextIterate (t : ℕ) (x : problem.feasibleSet) : E
/-- The chosen one-step solver returns a minimizer of the contracted linearized composite model
centered at the current feasible point `x_t`. -/
nextIterate_mem_argmin (t : ℕ) (x : problem.feasibleSet) :
nextIterate t x ∈
argmin[contractedFeasibleSet problem.feasibleSet (x : E) (stepSize t)]
(_root_.compositeObjective
(fun y ↦ fderivWithin ℝ problem.smoothPart problem.feasibleSet x y)
problem.nonsmoothPart)Definition 6.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.5: a structured objective model consists of bounded closed convex sets Q₁ ⊆ E₁ and Q₂ ⊆ E₂, continuous convex functions \hat f and \hat φ, and a linear operator A : E₁ → E₂*; the associated primal objective is encoded by the recalled chapter owner and its derived objective API.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
recall StructuredObjectiveModel (E₁ : Type u) (E₂ : Type v)
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂] :
Type (max u v)Lemma 6.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.5: for a convex set Q ⊆ E and a monotone linear operator B : E →ₗ[ℝ] E, the explicit gap bridge ψ(w) = sup_{v ∈ Q} ⟪B(v), w - v⟫ is minimized exactly at the feasible solutions of the source variational inequality. The additional hypothesis hψmax records that this supremum is attained for each feasible w, so the sSup surface faithfully bridges the source max notation.
open Module LinearMap
open scoped BigOperators RealInnerProductSpace WithTopConvexAnalysis NormalCone
open scoped ConstrainedArgmin
universe u w
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem isSolution_iff_isMinOn_explicitGapFunction
[InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
(Q : Set E) (hQconv : Convex ℝ Q) (B : E →ₗ[ℝ] E)
(hBmono : ∀ h : E, 0 ≤ inner ℝ (B h) h)
(hψmax :
∀ w : Q, ∃ v : Q,
IsGreatest
(Set.range fun u : Q ↦ inner ℝ (B (u : E)) ((w : E) - (u : E)))
(inner ℝ (B (v : E)) ((w : E) - (v : E))))
(wStar : Q) :
(∀ v ∈ Q, 0 ≤ inner ℝ (B (wStar : E)) (v - (wStar : E))) ↔
IsMinOn
(fun w : Q ↦
sSup
(Set.range fun v : Q ↦
inner ℝ (B (v : E)) ((w : E) - (v : E))))
Set.univ
wStar
Proposition 6.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.5: a normalized prox-center of a prox-function on Q₂ gives the lower bound d₂ u ≥ (1 / 2) p(u - u₀)^2 at every feasible point u ∈ Q₂.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {p : Seminorm ℝ E} [Seminorm.IsNorm p]
variable {Q₂ : Set E} {d₂ : E → ℝ} {u₀ u : E}
theorem prox_center_quadratic_lower_bound
(hd₂ : NesterovIsProxFunction p Q₂ d₂)
(hu₀ : NesterovIsProxCenter Q₂ d₂ u₀)
(hu : u ∈ Q₂) :
d₂ u ≥ (1 / 2 : ℝ) * (p (u - u₀)) ^ (2 : ℕ)Theorem 6.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.5: for a fixed index k, if α_{k-1} ≠ 0, λ₁,k λ₂,k = α_k α_{k-1}, and τ_k = 1 - α_{k+1} / α_{k-1}, then the step-size inequality τ_k^2 ≤ (α_{k+1} / α_{k-1}) λ₁,k λ₂,k is equivalent to the three-term inequality (α_{k+1} - α_{k-1})^2 ≤ α_{k+1} α_k α_{k-1}^2.
variable {𝕜 : Type*} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜]
-- Proof sketch: rewrite `τ k` as
-- `(α (k - 1) - α (k + 1)) / α (k - 1)`, square to obtain the left-hand side as
-- `(α (k + 1) - α (k - 1)) ^ 2 / (α (k - 1)) ^ 2`, substitute
-- `λ₁ k * λ₂ k = α k * α (k - 1)`, and clear the positive denominator `(α (k - 1)) ^ 2`.
theorem tau_square_bound_iff_alpha_three_term_inequality
(α : Set.Ici (-1 : ℤ) → 𝕜) (lambda₁ lambda₂ τ : ℕ → 𝕜) (k : ℕ)
(hα_pred_ne : α (switching_parameters_pred_index k) ≠ 0)
(hprod : lambda₁ k * lambda₂ k =
α (switching_parameters_curr_index k) * α (switching_parameters_pred_index k))
(hτ : τ k = 1 - α (switching_parameters_succ_index k) / α (switching_parameters_pred_index k)) :
τ k ^ (2 : ℕ) ≤
(α (switching_parameters_succ_index k) / α (switching_parameters_pred_index k)) *
(lambda₁ k * lambda₂ k) ↔
(α (switching_parameters_succ_index k) - α (switching_parameters_pred_index k)) ^ (2 : ℕ) ≤
α (switching_parameters_succ_index k) * α (switching_parameters_curr_index k) *
(α (switching_parameters_pred_index k)) ^ (2 : ℕ)
Algorithm 6.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Algorithm 6.6: for a composite convex minimization problem problem, a composite trust- region method with contraction consists of a twice continuously differentiable inherited smooth part on the feasible set, an initial feasible point x₀, a contraction sequence τ_t ∈ (0, 1], and a chosen one-step solver sending each feasible current iterate x_t to a successor x_{t+1} that minimizes the contracted quadratic composite subproblem `arg min_{y = (1 - τ_t) x_t + τ_t x, x ∈ Q} ⟪∇ f(x_t), y - x_t⟫ + (1 / 2) ⟪∇² f(x_t) (y - x_t), y - x_t⟫ + Ψ(y)`.
open scoped ConstrainedArgmin Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
structure CompositeTrustRegionContractionMethod
(problem : CompositeConvexMinimizationProblem E) (x0 : problem.feasibleSet) where
/-- The inherited smooth part is twice continuously differentiable on the feasible set. -/
objective_contDiffOn : ContDiffOn ℝ 2 problem.smoothPart problem.feasibleSet
/-- The contraction sequence `τ₀, τ₁, τ₂, ...`. -/
stepSize : ℕ → ℝ
/-- Each contraction factor lies in `(0, 1]`. -/
stepSize_mem_Ioc : ∀ t : ℕ, stepSize t ∈ Set.Ioc (0 : ℝ) 1
/-- The chosen contracted quadratic subproblem solver at time `t` and feasible current point
`x_t`. -/
nextIterate (t : ℕ) (x : problem.feasibleSet) : E
/-- The one-step solver returns a minimizer of the contracted quadratic composite model centered
at the current feasible iterate. -/
nextIterate_mem_argmin (t : ℕ) (x : problem.feasibleSet) :
nextIterate t x ∈
argmin[contractedFeasibleSet problem.feasibleSet (x : E) (stepSize t)]
(contractedCompositeSecondOrderModel problem x)Definition 6.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.6 [Chapter6_1.json:11]: the primal optimal value is the infimum of the saddle-point maximization x ↦ sup_{u ∈ Q₂} Ψ(x, u). Under additional attainment or compactness hypotheses, this agrees with the textbook minimum formula.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
namespace StructuredObjectiveModel
theorem primalOptimalValue_eq_saddle_form (problem : StructuredObjectiveModel E₁ E₂) :
problem.primalOptimalValue =
sInf (Set.range fun x : problem.primalSet ↦
sSup (Set.range fun u : problem.dualSet ↦ (problem.saddleFunction x u : EReal)))Lemma 6.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.6: if the primal value fStar is the minimum of f on Q₁, the same value is the maximum of φ on Q₂, and the local smoothing bounds together with the excessive-gap certificate hold at xBar ∈ Q₁ and uBar ∈ Q₂, then the primal and dual errors are both controlled by the raw duality gap, which is at most μ₁ D₁ + μ₂ D₂.
universe u v
theorem excessive_gap_bounds_primal_dual_errors
{X : Type u} {U : Type v}
{Q₁ : Set X} {Q₂ : Set U}
{f fμ₂ : X → ℝ} {φ φμ₁ : U → ℝ}
{xBar : X} {uBar : U}
{fStar D₁ D₂ μ₁ μ₂ : ℝ}
(h_primal : IsLeast (f '' Q₁) fStar)
(h_dual : IsGreatest (φ '' Q₂) fStar)
(hfμ₂_lower : f xBar - μ₂ * D₂ ≤ fμ₂ xBar)
(hφμ₁_upper : φμ₁ uBar ≤ φ uBar + μ₁ * D₁)
(hxBar : xBar ∈ Q₁)
(huBar : uBar ∈ Q₂)
(hexcessive_gap :
satisfiesExcessiveGapCondition Q₁ Q₂ fμ₂ φμ₁ ⟨xBar, hxBar⟩ ⟨uBar, huBar⟩) :
max (f xBar - fStar) (fStar - φ uBar) ∈ Set.Icc 0 (f xBar - φ uBar) ∧
f xBar - φ uBar ≤ μ₁ * D₁ + μ₂ * D₂Proposition 6.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.6: if \hat φ is convex on Q₂, d₂ is 1-strongly convex on Q₂, and μ > 0, then the maximization problem max_{u ∈ Q₂} {ℓ(u) - \hat φ(u) - μ d₂(u)} has at most one feasible maximizer. In particular, whenever the smoothed maximizer exists, it is uniquely defined.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem smoothed_maximizer_unique
{Q₂ : Set E} (ℓ : E →L[ℝ] ℝ) {d₂ φ : E → ℝ}
(hφ : ConvexOn ℝ Q₂ φ) (hd₂ : StrongConvexOn Q₂ 1 d₂) {μ : ℝ} (hμ : 0 < μ)
{u v : E} (hu_mem : u ∈ Q₂) (hv_mem : v ∈ Q₂)
(hu : IsMaxOn (fun w ↦ ℓ w - φ w - μ * d₂ w) Q₂ u)
(hv : IsMaxOn (fun w ↦ ℓ w - φ w - μ * d₂ w) Q₂ v) :
u = vTheorem 6.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.6: if the initial Algorithm 6.3 iterate pair satisfies the Chapter 6 excessive-gap condition, if each even step preserves the general excessive-gap certificate, and if each odd step passes through the μ₁ = 0 excessive-gap certificate before returning to the general one, then every Algorithm 6.3 iterate pair satisfies the general excessive-gap condition.
open scoped ConstrainedArgmin
universe u v
variable {X : Type u} {U : Type v}
variable [NormedAddCommGroup X] [NormedSpace ℝ X]
variable [NormedAddCommGroup U] [InnerProductSpace ℝ U] [CompleteSpace U]
variable {Q₁ : Set X} {Q₂ : Set U}
variable (hQ₁ : Convex ℝ Q₁) (hQ₂ : Convex ℝ Q₂)
variable {A : X →L[ℝ] StrongDual ℝ U}
variable {hatf : X → ℝ} {hatφ : U → ℝ} {d₁ : X → ℝ} {d₂ : U → ℝ}
variable (xμ : ℝ → U → X)
variable
(hxμ :
∀ μ : ℝ, ∀ u : U,
xμ μ u ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf d₁ μ u))
variable (uμ : ℝ → X → U)
variable
(huμ :
∀ μ : ℝ, ∀ x : X, x ∈ Q₁ →
uμ μ x ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ x)
variable (x₀ : Q₂ → Q₁) (V : Q₂ → Q₂)
variable {fμ₂ : ℝ → X → ℝ} {φμ₁ : ℝ → U → ℝ}
variable {fμ₂_zero : ℝ → Q₁ → ℝ} {φ_zero : Q₂ → ℝ}
variable {initialPrimalSmoothing initialDualSmoothing : ℝ}
variable (initialState : Q₁ × Q₂)
local notation "μ₁" =>
algorithm_6_3_primal_smoothing initialPrimalSmoothing
local notation "μ₂" =>
algorithm_6_3_dual_smoothing initialDualSmoothing
local notation "x̄" =>
alternatingExcessiveGapPrimalIterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
x₀
V
initialPrimalSmoothing
initialDualSmoothing
initialState
local notation "ū" =>
alternatingExcessiveGapDualIterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
x₀
V
initialPrimalSmoothing
initialDualSmoothing
initialState
local notation "x̄ₑ" =>
fun k ↦
algorithm_6_3_even_primal_iterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
initialPrimalSmoothing
initialDualSmoothing
(x̄ k, ū k)
k
local notation "ūₑ" =>
fun k ↦
algorithm_6_3_even_dual_iterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
initialPrimalSmoothing
initialDualSmoothing
(x̄ k, ū k)
k
local notation "x̄ₒ" =>
fun k ↦
algorithm_6_3_odd_primal_iterate
hQ₁
hQ₂
uμ
huμ
x₀
initialDualSmoothing
(x̄ k, ū k)
k
local notation "ūₒ" =>
fun k ↦
algorithm_6_3_odd_dual_iterate
hQ₂
uμ
huμ
V
initialDualSmoothing
(x̄ k, ū k)
k
theorem algorithm_6_3_iterates_satisfy_excessive_gap_condition
(hzero :
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ 0))
(φμ₁ (μ₁ 0))
(x̄ 0)
(ū 0))
(heven_step :
∀ k : ℕ, Even k →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ k))
(φμ₁ (μ₁ k))
(x̄ k)
(ū k) →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ (k + 1)))
(φμ₁ (μ₁ (k + 1)))
(x̄ₑ k)
(ūₑ k))
(hodd_source :
∀ k : ℕ, Odd k →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ k))
(φμ₁ (μ₁ k))
(x̄ k)
(ū k) →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ k))
φ_zero
(x̄ k)
(ū k))
(hodd_step :
∀ k : ℕ, Odd k →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ k))
φ_zero
(x̄ k)
(ū k) →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ (k + 1)))
φ_zero
(x̄ₒ k)
(ūₒ k))
(hodd_target :
∀ k : ℕ, Odd k →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ (k + 1)))
φ_zero
(x̄ₒ k)
(ūₒ k) →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ (k + 1)))
(φμ₁ (μ₁ (k + 1)))
(x̄ₒ k)
(ūₒ k))
(k : ℕ) :
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ k))
(φμ₁ (μ₁ k))
(x̄ k)
(ū k)
Definition 6.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.7: Nesterov's prox-smoothed approximation f_μ is the chapter's canonical regularized-max owner smoothedPrimalObjective specialized to zero smooth part.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
variable (p : Seminorm ℝ E₂) [Seminorm.IsNorm p]
variable
(A : E₁ →L[ℝ] StrongDual ℝ E₂)
(Q₂ : Set E₂) (hatφ d₂ : E₂ → ℝ) (μ : ℝ) (u₀ : E₂) (x : E₁) (u : E₂)
recall smoothedPrimalObjectiveLemma 6.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.7: if u ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ₂ xhat, then the affine linearization of the smoothed primal objective at xhat ∈ Q₁, with the smooth contribution written as ∇ \hat f(xhat), is bounded above by \hat f(x) + ⟪A x, u⟫ - \hat φ(u) for every x ∈ Q₁.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
variable [CompleteSpace E₁]
theorem smoothedPrimalObjective_linearization_le_selected_dual_value
(A : E₁ →L[ℝ] StrongDual ℝ E₂)
{Q₁ : Set E₁} {Q₂ : Set E₂} {hatf : E₁ → ℝ} {hatφ d₂ : E₂ → ℝ} {μ₂ : ℝ}
(hhatf_conv : ConvexOn ℝ Q₁ hatf) (hμ₂ : 0 ≤ μ₂)
{x xhat : E₁} (hx : x ∈ Q₁) (hxhat : xhat ∈ Q₁) {u : E₂}
(hu : u ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ₂ xhat)
(hhatf_grad : HasGradientWithinAt hatf (gradientWithin hatf Q₁ xhat) Q₁ xhat)
(hd₂_nonneg : 0 ≤ d₂ u) :
smoothedPrimalObjective A Q₂ hatf hatφ d₂ μ₂ xhat +
inner ℝ (gradientWithin hatf Q₁ xhat) (x - xhat) +
A (x - xhat) u ≤
hatf x + A x u - hatφ uProposition 6.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.7: if μ ≥ 0, u₀ is a prox-center of d₂ on Q₂, and d₂(u) ≤ D₂ for every u ∈ Q₂, then the Chapter 6 zero-smoothed objective smoothedPrimalObjective A Q₂ 0 hatφ d₂ 0 and the prox-smoothed objective smoothedPrimalObjective A Q₂ 0 hatφ d₂ μ satisfy f₀(x) ≥ f_μ(x) ≥ f₀(x) - μ D₂ for every x.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
variable
{A : E₁ →L[ℝ] StrongDual ℝ E₂} {Q₂ : Set E₂} {hatφ d₂ : E₂ → ℝ}
{μ D₂ : ℝ} {u₀ : E₂}
-- Proof sketch: compare the zero-smoothed and `μ`-smoothed maximands pointwise on `Q₂`, then pass
-- to the corresponding suprema. The prox-center normalization supplies `0 ≤ μ D₂` in the
-- unbounded-above fallback branch of the real `sSup` API.
theorem smoothedPrimalObjective_error_bounds
(hμ : 0 ≤ μ) (hu₀ : NesterovIsProxCenter Q₂ d₂ u₀) (hD₂ : ∀ u ∈ Q₂, d₂ u ≤ D₂)
(x : E₁) :
smoothedPrimalObjective A Q₂ 0 hatφ d₂ 0 x ≥
smoothedPrimalObjective A Q₂ 0 hatφ d₂ μ x ∧
smoothedPrimalObjective A Q₂ 0 hatφ d₂ μ x ≥
smoothedPrimalObjective A Q₂ 0 hatφ d₂ 0 x - μ * D₂Theorem 6.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.7 recalls the chapter owner theorem for odd-step preservation of the μ₁ = 0 excessive-gap condition.
recall StronglyConvexDualUpdate.excessive_gap_condition_preserved
Definition 6.8
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
A Definition 6.8 model can be evaluated as the inherited Chapter 3 composite objective.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
namespace CompositeLipschitzGradientModel
instance : CoeFun (CompositeLipschitzGradientModel E) (fun _ ↦ E → WithTop ℝ)Lemma 6.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.8: let x₀ ∈ Q₁, let xBar ∈ Q₁ minimize the affine linearized prox model x ↦ ⟪∇ f_{μ₂}(x₀), x⟫ + L₁(f_{μ₂}) d₁(x), and let xμ₁uBar ∈ Q₁ be the selected primal prox point attached to uBar. If φ_{μ₁}(uBar) is given by the standard excessive-gap identity and μ₁ ≥ L₁(f_{μ₂}), then the smoothed excessive-gap inequality f_{μ₂}(xBar) ≤ φ_{μ₁}(uBar) holds.
open scoped Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [FiniteDimensional ℝ E₁]
theorem smoothed_pair_satisfies_excessive_gap_of_linearized_prox_minimizers
{Q₁ : Set E₁} {fμ₂ : E₁ → ℝ} {φμ₁ : E₂ → ℝ} {d₁ : E₁ → ℝ}
{x₀ xBar xμ₁uBar : Q₁} {uBar : E₂} {μ₁ Lfμ₂ : ℝ}
(hconv : ConvexOn ℝ Q₁ fμ₂)
(hfμ₂_grad :
HasGradientWithinAt fμ₂ (gradientWithin fμ₂ Q₁ x₀) Q₁ x₀)
(hbar_min :
IsMinOn
(fun x ↦ inner ℝ (gradientWithin fμ₂ Q₁ x₀) x + Lfμ₂ * d₁ x)
Q₁
xBar)
(hxμ₁_min :
IsMinOn
(fun x ↦ inner ℝ (gradientWithin fμ₂ Q₁ x₀) x + μ₁ * d₁ x)
Q₁
xμ₁uBar)
(hφμ₁ :
φμ₁ uBar =
fμ₂ x₀ + μ₁ * (d₁ x₀ - d₁ xμ₁uBar))
(hμ₁ : Lfμ₂ ≤ μ₁) :
fμ₂ xBar ≤ φμ₁ uBar
Proposition 6.8
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.8: if each x_k and y_k lies in the convex hull of the finite prefix v_0, ..., v_k and the points v_k satisfy ‖v_k - xStar‖² ≤ 2 D for all k ≥ 0, then the three sequences are bounded, equivalently the union of their ranges is bounded. Here D is the scalar value corresponding to the source quantity d(xStar).
universe u
variable {E : Type u} [SeminormedAddCommGroup E] [NormedSpace ℝ E]
-- Proof sketch: the estimate `‖v k - xStar‖² ≤ 2 * D` gives a uniform closed ball centered
-- at `xStar` containing every `v k`. Since each `x k` and `y k` lies in the convex hull of the
-- finite prefix `v 0, ..., v k`, convexity of that closed ball implies the same uniform bound for
-- `x k` and `y k`. Therefore the union of the three ranges is bounded.
theorem bounded_union_of_prefix_convex_hull_sequences
(xStar : E) (D : ℝ) (v x y : ℕ → E)
(hx : ∀ k, x k ∈ convexHull ℝ (Set.range (fun i : Fin (k + 1) ↦ v i)))
(hy : ∀ k, y k ∈ convexHull ℝ (Set.range (fun i : Fin (k + 1) ↦ v i)))
(hv : ∀ k, ‖v k - xStar‖ ^ 2 ≤ 2 * D) :
Bornology.IsBounded (Set.range v ∪ Set.range x ∪ Set.range y)Theorem 6.8
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.8: if scheme (6.2.37) yields f_{μ₂,k}(\bar x_k) ≤ φ(\bar u_k) with μ₂,k = 4 L₂(φ) / ((k + 1) (k + 2)), and if the smoothing family satisfies f(x) - μ₂ D₂ ≤ f_{μ₂}(x) for every μ₂ and x, then f(\bar x_k) - φ(\bar u_k) ≤ 4 L₂(φ) D₂ / ((k + 1) (k + 2)) for every integer k ≥ 0.
universe u v
variable {X : Type u} {U : Type v}
{f : X → ℝ} {φ : U → ℝ}
{fμ₂ : ℝ → X → ℝ}
{barx : ℕ → X} {baru : ℕ → U}
{L2phi D2 : ℝ}
theorem primal_dual_gap_le_scheme_6_2_37_rate
(happrox : ∀ μ₂ x, f x - μ₂ * D2 ≤ fμ₂ μ₂ x)
(hscheme :
∀ k : ℕ,
fμ₂ ((4 * L2phi) / (((k : ℝ) + 1) * ((k : ℝ) + 2))) (barx k) ≤ φ (baru k))
(k : ℕ) :
f (barx k) - φ (baru k) ≤
(4 * L2phi * D2) / (((k : ℝ) + 1) * ((k : ℝ) + 2))Definition 6.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.9: for a model objective \hat f and smoothing term f_μ, the explicit-model smoothed optimization problem on Q₁ minimizes the sum x ↦ \hat f(x) + f_μ(x) over Q₁.
universe u
variable {X : Type u}
def explicitModelSmoothedProblem (Q₁ : Set X) (hatf fμ : X → ℝ) :
SetConstrainedMinimizationProblem XLemma 6.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.9 is the same switching-parameter recurrence statement already canonicalized in Lemma_6_2_4. The owner theorem there now works directly with the pair-valued switching_parameters sequence, so this file keeps only the direct recall surface.
recall alpha_succ_eq_one_sub_tau_mul_pred_of_alternating_scalar_updatesProposition 6.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.9 is the earlier Euclidean prox radius theorem euclidean_prox_radius_bound.
recall euclidean_prox_radius_boundTheorem 6.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.9: for every natural number k, the Hessian quadratic form of the Chapter 6 trace-power owner π_k(X) = Trace (X^k) at a symmetric matrix X in the symmetric direction H is bounded above by k(k - 1) times the pairing of the eigenvalues of (CFC.abs X)^(k - 2) and the squared eigenvalues of CFC.abs H.
open RealSymmetricMatrixSpace
open PositiveSemidefiniteCone
open scoped BigOperators MatrixOrder NNReal RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem powerTrace_iteratedFDeriv_two_le_absEigenvaluePairing
(k : ℕ) (X H : SymmMat) :
iteratedFDeriv ℝ 2 (π[k] : SymmMat → ℝ) X ![H, H] ≤
(((k * (k - 1) : ℕ) : ℝ) *
∑ i : Fin n,
(((Matrix.nonneg_iff_posSemidef.mp
(CFC.abs_nonneg ((X : Matrix (Fin n) (Fin n) ℝ)))).isHermitian.eigenvalues i) ^
(k - 2)) *
(((Matrix.nonneg_iff_posSemidef.mp
(CFC.abs_nonneg ((H : Matrix (Fin n) (Fin n) ℝ)))).isHermitian.eigenvalues i) ^
(2 : ℕ)))
Definition 6.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.10: for a real normed space, a prox-function on Q₁ is exactly the unit-strongly convex owner StrongConvexOn Q₁ 1 d₁.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {Q₁ : Set E} {d₁ : E → ℝ}
#check (StrongConvexOn Q₁ 1 d₁ : Prop)Lemma 6.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.10: if 0 < σ and hatf is σ-strongly convex on Q₁, if x₀ u is a feasible minimizer of the zero-smoothing primal slice for every u, and if \hat φ is differentiable and convex, then the finite real part of the canonical zero-smoothing dual objective is concave and has gradient -\nabla \hat φ(u) + (InnerProductSpace.toDual ℝ E₂).symm (A (x₀ u)).
open scoped ConstrainedArgmin ConvexAnalysis Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂]
variable [CompleteSpace E₂]
-- Proof sketch: use the strong-convexity owner
-- `0 < σ ∧ StrongConvexOn Q₁ σ hatf` to obtain uniqueness of the
-- pointwise argmin in each zero-smoothing primal slice. Then apply the Chapter 6 Danskin-style
-- gradient statement for `smoothedDualObjective A Q₁ hatf hatφ 0 0` together with convexity of
-- `hatφ` to conclude concavity of the finite real part and the displayed gradient formula.
theorem dualObjective_concave_and_hasGradientAt
(A : E₁ →L[ℝ] StrongDual ℝ E₂) {Q₁ : Set E₁} {hatf : E₁ → ℝ} {hatφ : E₂ → ℝ}
{x₀ : E₂ → E₁} {σ : ℝ}
(hσ : 0 < σ)
(hhatf : StrongConvexOn Q₁ σ hatf)
(hhatφ_convex : ConvexOn ℝ Set.univ hatφ)
(hhatφ_diff : Differentiable ℝ hatφ)
(hx₀ : ∀ u : E₂, x₀ u ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf 0 0 u)) :
ConcaveOn ℝ Set.univ (extendedRealRealPart (smoothedDualObjective A Q₁ hatf hatφ 0 0)) ∧
∀ u : E₂,
HasGradientAt
(extendedRealRealPart (smoothedDualObjective A Q₁ hatf hatφ 0 0))
(-∇ hatφ u + (InnerProductSpace.toDual ℝ E₂).symm (A (x₀ u))) u
Proposition 6.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.10: if \hat f has M-Lipschitz gradient on Q₁ and f_μ has gradient Lipschitz constant Real.toNNReal ((1 / μ) * ‖A‖^2) on Q₁, then the objective of the explicit-model smoothed problem from Definition 6.9 has derivative selection gradHatF + gradFμ on Q₁, hence is differentiable there, and this derivative selection is Lipschitz on Q₁ with constant M + Real.toNNReal ((1 / μ) * ‖A‖^2).
universe u v
variable {E : Type u} {F : Type v}
[NormedAddCommGroup E] [NormedSpace ℝ E]
[NormedAddCommGroup F] [NormedSpace ℝ F]
theorem explicitModelSmoothedProblem_hasFDerivWithinAt_and_gradient_lipschitzOn
{Q₁ : Set E} {hatF fμ : E → ℝ} {gradHatF gradFμ : E → StrongDual ℝ E}
(A : E →L[ℝ] F) {μ : ℝ} {M : NNReal}
(hhatF : ∀ x ∈ Q₁, HasFDerivWithinAt hatF (gradHatF x) Q₁ x)
(hhatF_lipschitz : LipschitzOnWith M gradHatF Q₁)
(hfμ : ∀ x ∈ Q₁, HasFDerivWithinAt fμ (gradFμ x) Q₁ x)
(hfμ_lipschitz :
LipschitzOnWith (Real.toNNReal ((1 / μ) * ‖A‖ ^ (2 : ℕ))) gradFμ Q₁) :
(∀ x ∈ Q₁,
HasFDerivWithinAt
(explicitModelSmoothedProblem Q₁ hatF fμ)
(gradHatF x + gradFμ x) Q₁ x) ∧
LipschitzOnWith
(M + Real.toNNReal ((1 / μ) * ‖A‖ ^ (2 : ℕ)))
(fun x ↦ gradHatF x + gradFμ x) Q₁Theorem 6.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.10: if a defines a real power series with positive radius of convergence and nonnegative coefficients in every degree k ≥ 2, then every X in the induced spectral domain and every symmetric direction H satisfy the Hessian quadratic-form bound for the corresponding spectral sum.
open RealSymmetricMatrixSpace
open scoped BigOperators
open scoped Gradient
open scoped MatrixOrder
open scoped RealSymmetricMatrixSpace
universe u
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem hessianQuadraticForm_le_absEigenvalueSquareSum
(a : ℕ → ℝ)
(ha_radius : 0 < (FormalMultilinearSeries.ofScalars ℝ a).radius)
(ha_nonneg : ∀ k : ℕ, 2 ≤ k → 0 ≤ a k)
(X : SymmMat)
(hX : X ∈ theoremSixTenDom a)
(H : SymmMat) :
(iteratedFDeriv ℝ 2 (theoremSixTenMatrixFun a) X) ![H, H] ≤
∑ i : Fin n,
(iteratedDeriv 2 (theoremSixTenScalarFun a) (eigenvalues (|X| : SymmMat) i)) *
((eigenvalues (|H| : SymmMat) i) ^ (2 : ℕ))
Definition 6.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.11: the standard simplex Δ_n is the canonical mathlib set Δ[n] = stdSimplex ℝ (Fin n), and in general stdSimplex 𝕜 ι is the set of functions with nonnegative coordinates and total sum equal to 1.
universe u v
open scoped StandardSimplex
recall stdSimplex (𝕜 : Type v) (ι : Type u) [Semiring 𝕜] [PartialOrder 𝕜] [Fintype ι] : Set (ι → 𝕜)Lemma 6.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.11: for any u, \hat u ∈ Q₂, the difference u - \hat u also belongs to Q₂; this is exactly the canonical subtraction-closure theorem for a submodule.
universe u v
#check (Submodule.sub_mem : ∀ {R : Type u} {M : Type v}, [Ring R] → [AddCommGroup M] →
[Module R M] → (Q₂ : Submodule R M) → {u uHat : M} → u ∈ Q₂ → uHat ∈ Q₂ → u - uHat ∈ Q₂)Proposition 6.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.11: in the case M = 0, if the explicit-model smoothing hypotheses from Theorem 6.3 hold and √(N (N + 1)) ≥ 4 ‖A‖ √(D₁ D₂) / ε, then the primal-dual gap at (x_N, \hat u_N) is at most ε.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
theorem zero_model_smoothing_complexity_relation
(A : E₁ →L[ℝ] StrongDual ℝ E₂) (f fμ : E₁ → ℝ) (φ : E₂ → ℝ)
(N : ℕ+) (xN : E₁) (u : Fin ((N : ℕ) + 1) → E₂)
(D₁ D₂ ε : ℝ) (hε : 0 < ε) (hD₁ : 0 ≤ D₁) (hD₂ : 0 < D₂)
(hxN_approx :
fμ xN ≥ f xN - explicitModelSmoothingParameter A D₁ D₂ N * D₂)
(hφ_le : φ (Finset.univ.centerMass (explicitModelDualAverageWeights N) u) ≤ fμ xN)
(hfμ_le : fμ xN ≤ f xN)
(hsmoothed_gap :
fμ xN - φ (Finset.univ.centerMass (explicitModelDualAverageWeights N) u) ≤
(4 * ‖A‖ ^ (2 : ℕ) * D₁) /
(explicitModelSmoothingParameter A D₁ D₂ N * ((N : ℝ) * ((N : ℝ) + 1))))
(hiter :
(4 * ‖A‖ * Real.sqrt (D₁ * D₂)) / ε ≤
Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))) :
f xN - φ (Finset.univ.centerMass (explicitModelDualAverageWeights N) u) ≤ εTheorem 6.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.11: if the problem min_{x ∈ Q} {⟨s, x⟩ + Ψ(x)} admits an optimal solution, then there exists a feasible point v_Ψ(s) in the canonical minimizer set of linearOptimizationOracleObjective s Ψ on the feasible subtype Q.
open scoped ConstrainedArgmin
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {Q : Set E}
theorem exists_linear_optimization_oracle_point
(s : StrongDual ℝ E) (Ψ : Q → ℝ)
(hattains : ∃ x : Q, IsMinOn (linearOptimizationOracleObjective s Ψ) Set.univ x) :
∃ vPsi : Q,
vPsi ∈ argmin[Set.univ] (linearOptimizationOracleObjective s Ψ)Definition 6.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.12: [Simplex saddle-point problem and primal--dual nonsmooth forms] the simplex saddle-point problem determined by A, c, and b induces the corresponding Chapter 6 structured objective model on the Euclidean simplices Δ_n and Δ_m.
open scoped StandardSimplex
variable {n m : ℕ+}
namespace SimplexSaddlePointProblem
local notation "Eₙ" => EuclideanSpace ℝ (Fin (n : ℕ))
local notation "Eₘ" => EuclideanSpace ℝ (Fin (m : ℕ))
def toStructuredObjectiveModel (problem : SimplexSaddlePointProblem n m) :
StructuredObjectiveModel Eₙ EₘLemma 6.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.12: if fμ₂ satisfies the local lower smoothing bound f xBar - μ₂ D₂ ≤ fμ₂ xBar, if φ uBar ≤ fμ₂ xBar ≤ f xBar, and if the residual smoothed gap fμ₂ xBar - φ uBar is bounded above by r, then the raw primal-dual gap at (xBar, uBar) lies in the interval [0, μ₂ D₂ + r].
universe u v
-- Proof sketch: the inequalities `φ uBar ≤ fμ₂ xBar ≤ f xBar` give the lower bound
-- `0 ≤ f xBar - φ uBar`. The local estimate for `fμ₂` at `xBar` bounds the smoothing defect
-- `f xBar - fμ₂ xBar` by `μ₂ * D₂`; adding the assumed residual smoothed gap bound
-- `fμ₂ xBar - φ uBar ≤ r` gives the upper bound
-- `f xBar - φ uBar ≤ μ₂ * D₂ + r`.
theorem primal_dual_gap_bound_of_smoothed_lower_approximation
{Q₁ : Type u} {Q₂ : Type v}
{f fμ₂ : Q₁ → ℝ} {φ : Q₂ → ℝ} {μ₂ D₂ r : ℝ}
{xBar : Q₁} {uBar : Q₂}
(happrox : f xBar - μ₂ * D₂ ≤ fμ₂ xBar)
(hφ_le : φ uBar ≤ fμ₂ xBar) (hresidual : fμ₂ xBar - φ uBar ≤ r)
(hsmoothed_le : fμ₂ xBar ≤ f xBar) :
f xBar - φ uBar ∈ Set.Icc 0 (μ₂ * D₂ + r)Proposition 6.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.12: if the primal optimal value of a Lagrangian problem is bounded above by its dual optimal value, then there is no duality gap, so the primal and dual optimal values are equal.
universe u
namespace LagrangianProblem
theorem noDualityGap_of_primalOptimalValue_le_dualOptimalValue
{Q : Type u} {m : ℕ} (problem : LagrangianProblem Q m)
(h : problem.primalOptimalValue ≤ problem.dualOptimalValue) :
problem.primalOptimalValue = problem.dualOptimalValueTheorem 6.12
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.12: along method (6.4.12), if f is convex on Q, the canonical ambient extension of the regularizer Ψ is convex on Q, the coefficients satisfy A_t = ∑_{k=0}^t a_k and τ_t = a_{t+1} / A_{t+1}, and the (6.4.3) Hölder-gradient error term is bounded by G_ν D^(1 + ν), then for every iteration t and feasible point x the weighted composite objective at x_t is bounded by the sum of the affine linearizations at x plus the Chapter 6 error term linearOptimizationOracleErrorBound V₀ a G_ν D ν t, where V₀ = initialLinearizationGap Q f Ψ x₀ and x₀ = method.x0.
open scoped BigOperators WeightSequenceNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem weighted_objective_upper_bound_of_linear_oracle_composite_method
{Q : Set E} {f : E → ℝ} {Ψ : Q → ℝ}
(hf_convex : ConvexOn ℝ Q f)
(hΨ_convex : ConvexOn ℝ Q (Function.extend Subtype.val Ψ 0))
(method : LinearOracleCompositeMethod Q f Ψ)
(a : ℕ → ℝ) (ν Gν D : ℝ)
(ha_pos : ∀ t : ℕ, 0 < a t)
(h_step : ∀ t : ℕ, method.stepSize t = τ[a](t))
(h6043 :
∀ t : ℕ, ∀ x : Q,
inner ℝ
(gradientWithin f Q (method (t + 1)) - gradientWithin f Q (method t))
((x : E) - method.oraclePoint t) ≥
-((Real.rpow (method.stepSize t) ν) * Gν * Real.rpow D (1 + ν)))
(t : ℕ) (x : Q) :
A[a](t) * (f (method t) + Ψ (method t)) ≤
(Finset.sum (Finset.range (t + 1)) fun k ↦
a k *
(f (method k) +
inner ℝ (gradientWithin f Q (method k)) ((x : E) - method k) +
Ψ x)) +
linearOptimizationOracleErrorBound
(initialLinearizationGap Q f Ψ method.x0) a Gν D ν t
Definition 6.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.13: expanding simplexEuclideanProxFunction n gives the textbook formula (1 / 2) * Σ_i (x_i - 1 / n)^2.
open scoped BigOperators
open scoped StandardSimplex
theorem simplexEuclideanProxFunction_apply (n : ℕ+) (x : Δ[n]) :
simplexEuclideanProxFunction n x =
(1 / 2 : ℝ) * ∑ i : Fin n, (x i - (1 : ℝ) / n) ^ (2 : ℕ)Lemma 6.13
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.13 recalls the Chapter 6 owner theorem for the one-point excessive-gap inequality at barx = x₀(u₀) and baru = V(u₀).
open scoped Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
recall smoothed_primal_objective_at_x0_le_dual_value_at_V
(A : E₁ →L[ℝ] StrongDual ℝ E₂) {Q₂ : Set E₂}
{φ hatφ : E₂ → ℝ} {hatf : E₁ → ℝ} {d₂ : E₂ → ℝ}
{x₀ : E₂ → E₁} {V : E₂ → E₂} {u₀ : E₂} {μ₂ : NNReal}
(hQ₂_convex : Convex ℝ Q₂)
(hu₀ : u₀ ∈ Q₂)
(hφ_hasGradientWithinAt :
∀ ⦃u : E₂⦄, u ∈ Q₂ →
HasGradientWithinAt φ (gradientWithin φ Q₂ u) Q₂ u)
(hφ_gradient_lipschitz :
LipschitzOnWith μ₂ (fun u ↦ gradientWithin φ Q₂ u) Q₂)
(hV_max :
IsMaxOn
(fun u ↦
φ u₀ +
inner ℝ (gradientWithin φ Q₂ u₀) (u - u₀) -
((μ₂ : ℝ) / 2) * ‖u - u₀‖ ^ (2 : ℕ))
Q₂
(V u₀))
(hφ_eq :
φ u₀ = -hatφ u₀ + A (x₀ u₀) u₀ + hatf (x₀ u₀))
(hgradφ_eq :
gradientWithin φ Q₂ u₀ =
(InnerProductSpace.toDual ℝ E₂).symm (A (x₀ u₀)) - gradientWithin hatφ Q₂ u₀)
(hhatφ_model :
∀ ⦃u : E₂⦄, u ∈ Q₂ →
-hatφ u ≤
-hatφ u₀ - inner ℝ (gradientWithin hatφ Q₂ u₀) (u - u₀) +
(μ₂ : ℝ) * d₂ u -
((μ₂ : ℝ) / 2) * ‖u - u₀‖ ^ (2 : ℕ)) :
smoothedPrimalObjective A Q₂ hatf hatφ d₂ (μ₂ : ℝ) (x₀ u₀) ≤ φ (V u₀)
Proposition 6.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.13: for a real matrix A, the operator norm induced by the Euclidean norms on ℝ^n and ℝ^m is the square root of the largest eigenvalue of the Gram matrix Aᵀ * A.
open Matrix
open scoped Matrix.Norms.L2Operator MatrixOrder
theorem l2OperatorNorm_eq_sqrt_greatestEigenvalue_transpose_mul_self
{m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) :
‖A‖ = Real.sqrt (λ_max((Aᵀ * A : Matrix (Fin n) (Fin n) ℝ)))Theorem 6.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.13: if A_t > 0 and the weighted objective gap satisfies A_t (\bar f(x_t) - \bar f(x_s)) ≤ B_{ν,t} with B_{ν,t} = linearOptimizationOracleErrorBound V₀ a G_ν D ν t, then \bar f(x_t) - \bar f(x_s) ≤ B_{ν,t} / A_t. Here t : ℕ encodes the hypothesis t ≥ 0.
open scoped WeightSequenceNotation
universe u
variable {X : Type u}
theorem objective_gap_le_error_bound_div_accumulated_weight
(fbar : X → ℝ) (xt xs : X) (a : ℕ → ℝ) (V0 Gν D : ℝ)
{ν : ℝ} {t : ℕ}
(hAt : 0 < A[a](t))
(hweighted :
A[a](t) * (fbar xt - fbar xs) ≤
linearOptimizationOracleErrorBound V0 a Gν D ν t) :
fbar xt - fbar xs ≤
linearOptimizationOracleErrorBound V0 a Gν D ν t / A[a](t)Definition 6.14
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.14: evaluating normalizedEntropyProxFunction n gives the textbook formula log n + ∑ᵢ xᵢ log xᵢ on Δ_n.
open scoped BigOperators
open scoped StandardSimplex
theorem normalizedEntropyProxFunction_apply (n : ℕ+) (x : Δ[n]) :
normalizedEntropyProxFunction n x =
Real.log (n : ℝ) + ∑ i : Fin (n : ℕ), x i * Real.log (x i)Lemma 6.14
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.14: for nonnegative exponents, a positive-semidefinite symmetric matrix X, and a real symmetric matrix H, the single mixed trace term trace (((X^p H X^q)ᵀ) H) is bounded by the Frobenius pairing of X^(p+q) with H^2, and this is in turn bounded by the pairing of the eigenvalue vectors of X^(p+q) and H^2.
open Matrix
open RealSymmetricMatrixSpace
open PositiveSemidefiniteCone
open scoped BigOperators MatrixOrder NNReal RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
local notation "SymmMat" => 𝕊^n
theorem mixed_power_trace_le_power_pairing_of_pos
(p q : ℝ≥0) (X : 𝕊^n₊) (H : SymmMat) :
Matrix.trace
(((((X ^ p : 𝕊^n₊) : Mat) * (H : Mat) * ((X ^ q : 𝕊^n₊) : Mat))ᵀ) * (H : Mat))
≤ ⟪(X ^ (p + q) : 𝕊^n₊), H ^ (2 : ℕ)⟫_F ∧
⟪(X ^ (p + q) : 𝕊^n₊), H ^ (2 : ℕ)⟫_F
≤ ∑ i : Fin n, eigenvalues (X ^ (p + q) : 𝕊^n₊) i * eigenvalues (H ^ (2 : ℕ)) i
Proposition 6.14
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.14: for the entropy-smoothed simplex matrix game, if the smoothing budget is chosen so that μ₂ * sSup (Set.range (normalizedEntropyProxFunction m)) = 4 ‖A‖ / √(N (N + 1)), then the primal-dual gap at (xHat, uHat) lies in the interval whose upper endpoint is the spectral quantity 4 * sqrt (sSup (spectrum ℝ (Aᵀ * A))) / sqrt (N (N + 1)) + r, provided the residual smoothed gap fμ₂ xHat - φ uHat is bounded by r.
open Matrix
open scoped StandardSimplex
open scoped Matrix.Norms.L2Operator MatrixOrder
variable {m n : ℕ+} (A : Matrix (Fin (m : ℕ)) (Fin (n : ℕ)) ℝ)
variable (f fμ₂ : Δ[n] → ℝ) (φ : Δ[m] → ℝ)
variable (N : ℕ) (xHat : Δ[n]) (uHat : Δ[m]) {μ₂ r : ℝ}
theorem simplex_matrix_game_primalDualGap_mem_Icc_of_entropy_smoothing_spectral_bound
(happrox :
f xHat - μ₂ * sSup (Set.range (normalizedEntropyProxFunction m)) ≤ fμ₂ xHat)
(hφ_le : φ uHat ≤ fμ₂ xHat)
(hsmoothed_gap : fμ₂ xHat - φ uHat ≤ r)
(hfμ₂_le : fμ₂ xHat ≤ f xHat)
(hscale :
μ₂ * sSup (Set.range (normalizedEntropyProxFunction m)) =
(4 * ‖A‖) / Real.sqrt ((N : ℝ) * ((N : ℝ) + 1)))
:
f xHat - φ uHat ∈ Set.Icc 0
((4 * Real.sqrt (sSup (spectrum ℝ (Aᵀ * A)))) /
Real.sqrt ((N : ℝ) * ((N : ℝ) + 1)) + r)Theorem 6.14
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.14 (1): along Algorithm 6.5, if the initial model \tilde f underestimates the initial objective up to the scalar initial-gap term Δ(x₀) and the weights satisfy a_t > 0, then for every Hölder exponent parameter v : NNReal, every index t ≥ 0, and every comparison point x ∈ Q, one has A_t \bar f(x_t) ≤ φ_t(x) + C_{v,t}.
open scoped BigOperators Gradient TotalVariationNotation WeightSequenceNotation WithTopConvexAnalysis
universe u
namespace ConditionalGradientContraction
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
open ContractedFeasibleSetTrustRegionScheme
open scoped ContractionErrorNotation EstimatingFunctionNotation
theorem weighted_objective_le_estimatingFunction_add_contractionError
{problem : CompositeConvexMinimizationProblem E} {x0 : problem.feasibleSet}
(method : ContractedFeasibleSetTrustRegionScheme problem x0)
(a : ℕ → ℝ) (tildeF : E → ℝ) (Δ0 : ℝ) {v Gv : NNReal} {D : ℝ}
(hinitial :
∀ ⦃x : E⦄, x ∈ problem.feasibleSet →
problem.smoothPart x0 + withTopRealPart problem.nonsmoothPart x0 ≤ tildeF x + Δ0)
(hf_holder :
HolderGradientOn v Gv problem.feasibleSet problem.smoothPart method.gradient)
(ha_pos : ∀ t : ℕ, 0 < a t)
(h_step : ∀ t : ℕ, method.stepSize t = τ[a](t))
(hdiam :
∀ ⦃x y : E⦄, x ∈ problem.feasibleSet → y ∈ problem.feasibleSet → ‖x - y‖ ≤ D)
(t : ℕ) {x : E} (hx : x ∈ problem.feasibleSet) :
A[a](t) *
(problem.smoothPart (method t) +
withTopRealPart problem.nonsmoothPart (method t)) ≤
φ[method, a, tildeF](t, x) +
C[Δ0, a, (Gv : ℝ), D, (v : ℝ)](t)
Definition 6.15
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.15 [Chapter6_2.json:39]: the constrained location problem is the constrained minimization problem with objective f(x) = ∑_{j=1}^p m_j ‖x - c_j‖ over the Euclidean closed ball ‖x‖ ≤ r̄.
open scoped BigOperators
variable {p n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
def continuousLocationProblem
(weights : ContinuousLocationWeights (Fin p)) (centers : Fin p → E) (rBar : NNReal) :
SetConstrainedMinimizationProblem E :=
{ feasibleSet := Metric.closedBall (0 : E) (rBar : ℝ)
objective := continuousLocationObjective weights centers }Lemma 6.15
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.15: if a real function is decreasing on [a, b + 1] and convex on [a - 1 / 2, b + 1 / 2], then the sum of its integer samples from a to b lies between the integral over [a, b + 1] and the centered integral over [a - 1 / 2, b + 1 / 2].
open MeasureTheory
open scoped BigOperators
theorem sum_integer_samples_between_intervalIntegrals_of_antitoneOn_convexOn
(ξ : ℝ → ℝ) (a b : ℤ) (hab : a ≤ b)
(hantitone : AntitoneOn ξ (Set.Icc (a : ℝ) ((b : ℝ) + 1)))
(hconvex :
ConvexOn ℝ (Set.Icc ((a : ℝ) - (1 / 2 : ℝ)) ((b : ℝ) + (1 / 2 : ℝ))) ξ) :
(∑ k ∈ Finset.Icc a b, ξ (k : ℝ)) ∈
Set.Icc
(∫ x in (a : ℝ)..((b : ℝ) + 1), ξ x)
(∫ x in ((a : ℝ) - (1 / 2 : ℝ))..((b : ℝ) + (1 / 2 : ℝ)), ξ x)Proposition 6.15
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.15 [Chapter6_1.json:39]: if the entropy-distance matrix-game gap estimate is written with the canonical ℓ₁ → ℓ∞ operator norm of A, then the same estimate can be written with the largest absolute matrix entry max_{i,j} |A^{(i,j)}|.
open InnerProductSpace
open scoped BigOperators SeminormDualNorm SeminormOperatorNorm
universe u v
variable {m n : ℕ+}
local notation "EN" => EuclideanSpace ℝ (Fin (n : ℕ))
local notation "EM" => EuclideanSpace ℝ (Fin (m : ℕ))
theorem matrix_game_entropy_gap_mem_Icc_max_abs_entry_bound
{X : Type u} {U : Type v}
(A : Matrix (Fin (m : ℕ)) (Fin (n : ℕ)) ℝ)
(f : X → ℝ) (φ : U → ℝ) (xHat : X) (uHat : U) (N : ℕ+)
(hnonneg : 0 ≤ f xHat - φ uHat)
(hgap_le :
f xHat - φ uHat ≤
((4 * Real.sqrt (Real.log (n : ℝ) * Real.log (m : ℝ))) /
Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))) *
‖(toDual ℝ EM).toLinearMap.comp A.toEuclideanLin‖[EuclideanSpace.l1Seminorm (n : ℕ) ⇀
EuclideanSpace.l1Seminorm (m : ℕ),*]) :
f xHat - φ uHat ∈
Set.Icc 0
(((4 * Real.sqrt (Real.log (n : ℝ) * Real.log (m : ℝ))) /
Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))) *
↑((Finset.univ : Finset (Fin (m : ℕ))).sup fun j ↦
(Finset.univ : Finset (Fin (n : ℕ))).sup fun i ↦ Real.nnabs (A j i)))Theorem 6.15
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.15: if f is convex on Q, Ψ is σ_Ψ-strongly convex on the feasible set Q, method (6.4.12) is run with weights a_t normalized by a₀ = 0, coefficients τ_t = a_{t+1} / A_{t+1}, exponent v ∈ (0, 1], and the gradient differences satisfy the bound (6.4.3), then for every t ≥ 0 and every feasible comparison point x ∈ Q the weighted composite objective at x_t is bounded by the weighted affine linearizations at x plus the zero-initialized recursive error term \hat B_{v,t}.
open scoped BigOperators StrongConvex WeightSequenceNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem weighted_objective_upper_bound_of_strongly_convex_linear_oracle_composite_method
{Q : Set E} {f Ψ : E → ℝ} {σΨ : ℝ}
(hf_convex : ConvexOn ℝ Q f)
(hΨ : Ψ ∈ 𝒮^0_σΨ(Q))
(method : LinearOracleCompositeMethod Q f (fun x : Q ↦ Ψ x))
(a : ℕ → ℝ) (v Gv D : ℝ)
(hv : v ∈ Set.Ioc (0 : ℝ) 1)
(ha_zero : a 0 = 0)
(hD_nonneg : 0 ≤ D)
(ha_nonneg : ∀ t : ℕ, 0 ≤ a t)
(h_step : ∀ t : ℕ, method.stepSize t = τ[a](t))
(h6043 :
∀ t : ℕ,
‖gradientWithin f Q (method (t + 1)) - gradientWithin f Q (method t)‖ ≤
(Real.rpow (a (t + 1)) v /
Real.rpow (A[a](t.succ)) v) *
Gv * Real.rpow D v)
(t : ℕ) (x : Q) :
A[a](t) * (f (method t) + Ψ (method t)) ≤
(Finset.sum (Finset.range (t + 1)) fun k ↦
a k *
(f (method k) +
inner ℝ (gradientWithin f Q (method k)) ((x : E) - method k) +
Ψ x)) +
zeroInitStronglyConvexCompositeErrorBound a v Gv D σΨ tDefinition 6.16
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.16 [Chapter6_2.json:42]: the smooth approximation splits as the weighted sum of scalar Huber losses evaluated at the distances ‖x - c_j‖.
open scoped BigOperators
universe u v
variable {ι : Type u}
variable {E : Type v} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [Fintype ι]
theorem continuousLocationSmoothApproximation_eq_sum_huberLoss
(weights : ContinuousLocationWeights ι) (centers : ι → E)
(μ : {μ : ℝ // 0 < μ}) (x : E) :
continuousLocationSmoothApproximation weights centers μ x =
∑ j, (weights j : ℝ) * continuousLocationHuberLoss μ ‖x - centers j‖Lemma 6.16
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.16: for a concave real-valued function F on Q, the scaled restricted dual function of the canonical WithTop lift of F at (τ, xBar) lies between 0 and τ times the unscaled restricted dual function.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem scaledRestrictedDualFunction_mem_Icc_of_concaveOn
{Q : Set E} {F : E → ℝ} (hF : ConcaveOn ℝ Q F)
{xBar : E} (hxBar : xBar ∈ Q) {τ : ℝ} (hτ : τ ∈ Set.Icc (0 : ℝ) 1)
(s : StrongDual ℝ E) :
scaledRestrictedDualFunction Q (fun x ↦ (F x : WithTop ℝ))
⟨xBar, by simp [hxBar, withTopEffectiveDomain]⟩ τ s ∈
Set.Icc
(0 : WithTop ℝ)
(((τ : WithTop ℝ) *
restrictedDualFunction Q (fun x ↦ (F x : WithTop ℝ))
⟨xBar, by simp [hxBar, withTopEffectiveDomain]⟩ s))Proposition 6.16
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.16: the entropy-smoothed approximation of x ↦ ⟪c, x⟫ + max_j (⟪a_j, x⟫ + b_j) is obtained by replacing the entropy prox-function on Δ_m with its explicit formula log m + ∑_j u_j log u_j.
open scoped BigOperators
open scoped StandardSimplex
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
-- Proof sketch: compare the two `Set.range` supremum sets pointwise, then expand
-- `normalizedEntropyProxFunction m u = Real.log (m : ℝ) + ∑ j, u j * Real.log (u j)` inside the
-- supremum.
theorem entropySmoothedAffineSup_eq_entropyExpansion
(m : ℕ+) (c x : E) (a : Fin (m : ℕ) → E) (b : Fin (m : ℕ) → ℝ) (μ : ℝ) :
inner ℝ c x +
sSup
(Set.range fun u : Δ[m] ↦
(∑ j : Fin (m : ℕ), u j * (inner ℝ (a j) x + b j)) -
μ * normalizedEntropyProxFunction m u) =
inner ℝ c x +
sSup
(Set.range fun u : Δ[m] ↦
(∑ j : Fin (m : ℕ), u j * (inner ℝ (a j) x + b j)) -
μ * ∑ j : Fin (m : ℕ), u j * Real.log (u j) -
μ * Real.log (m : ℝ))Theorem 6.16
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.16: if {x_t} is generated by method (6.4.50), then for every ν ∈ [0, 1], every integer t ≥ 0, and every x ∈ Q, the estimating-sequence bound (6.4.55) holds; moreover, for every integer t ≥ 0, the objective-drop inequality (6.4.56) holds.
open scoped BigOperators ConstrainedArgmin Gradient WeightSequenceNotation WithTopConvexAnalysis
universe u
namespace SecondOrderLocalModel
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
open scoped SecondOrderOptimalityMeasureNotation
variable {problem : CompositeConvexMinimizationProblem E} {x0 : problem.feasibleSet}
theorem estimating_function_bound_and_objective_drop
(method : CompositeTrustRegionContractionMethod problem x0)
(a : ℕ → ℝ) {L D : ℝ} (Hν : NNReal) (xStar : E)
(ν : Set.Icc (0 : ℝ) 1)
(hxStar :
xStar ∈
argmin[problem.feasibleSet]
(fun x ↦ problem.smoothPart x + withTopRealPart problem.nonsmoothPart x))
(ha_pos : ∀ t : ℕ, 0 < a t)
(h_step : ∀ t : ℕ, method.stepSize t = τ[a](t))
(hdiam :
∀ ⦃x y : E⦄, x ∈ problem.feasibleSet → y ∈ problem.feasibleSet → ‖x - y‖ ≤ D)
(h_hessian_bound : ∀ t : ℕ, ‖hessian problem.smoothPart (method t)‖ ≤ L)
(h_upper_model :
∀ ⦃x y : E⦄, x ∈ problem.feasibleSet → y ∈ problem.feasibleSet →
problem.smoothPart y ≤
secondOrderTaylorModelAt problem.smoothPart x y +
(Hν : ℝ) * Real.rpow ‖y - x‖ (2 + (ν : ℝ)) / ((1 + (ν : ℝ)) * (2 + (ν : ℝ)))) :
(∀ t : ℕ, ∀ x : E, x ∈ problem.feasibleSet →
A[a](t) *
(problem.smoothPart (method t) + withTopRealPart problem.nonsmoothPart (method t)) ≤
estimatingFunction method a t x + errorTerm method a xStar L (Hν : ℝ) D ν t) ∧
(∀ t : ℕ,
(((problem.smoothPart (method t) + withTopRealPart problem.nonsmoothPart (method t)) -
(problem.smoothPart (method (t + 1)) +
withTopRealPart problem.nonsmoothPart (method (t + 1))) : ℝ) : EReal) ≥
(method.stepSize t : EReal) *
θ[problem.feasibleSet, problem.smoothPart, problem.nonsmoothPart](
⟨method t, iterate_mem_optimalityDomain method t⟩) -
((((Hν : ℝ) * Real.rpow D (2 + (ν : ℝ)) / ((1 + (ν : ℝ)) * (2 + (ν : ℝ)))) *
Real.rpow (method.stepSize t) (2 + (ν : ℝ)) : ℝ) : EReal))
Definition 6.17
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.17: an affine variational inequality problem consists of a bounded closed convex set Q ⊆ E and an affine operator B : E → E* whose linear part satisfies ⟪Bh, h⟫ ≥ 0 for every h ∈ E. The textbook item specializes this owner to finite-dimensional real normed spaces.
open Module LinearMap
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
structure AffineVariationalInequalityProblem (E : Type u) [NormedAddCommGroup E]
[NormedSpace ℝ E] where
/-- The feasible set `Q ⊆ E`. -/
feasibleSet : Set E
/-- The feasible set `Q` is bounded. -/
feasibleSet_bounded : Bornology.IsBounded feasibleSet
/-- The feasible set `Q` is closed. -/
feasibleSet_closed : IsClosed feasibleSet
/-- The feasible set `Q` is convex. -/
feasibleSet_convex : Convex ℝ feasibleSet
/-- The affine operator `B : E → E*`. -/
operator : E →ᵃ[ℝ] Dual ℝ E
/-- The bilinear form underlying the linear part of `B` is nonnegative. -/
operator_linear_isNonneg : BilinForm.IsNonneg operator.linearLemma 6.17
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.17 in the canonical Chapter 6 Hölder-gradient owner form: under the argmax-selection and dual uniform-convexity hypotheses, the chosen derivative field x ↦ A.flip (u x) defines ConditionalGradientContraction.HolderGradientOn on Set.univ with exponent v = 1 / (p - 1) and constant Gᵥ = (1 / σ_g)^v ‖A‖^(1 + v).
open ConditionalGradientContraction
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
theorem holderGradientOn_of_argmax_selection_of_uniformly_convex_derivative
{A : E₁ →L[ℝ] StrongDual ℝ E₂} {f : E₁ → ℝ} {g : E₂ → ℝ}
{u : E₁ → E₂} {gradg : E₂ → StrongDual ℝ E₂} {p σg : ℝ}
(hp : 2 ≤ p) (hσg : 0 < σg)
(hu : ∀ x : E₁, u x ∈ smoothedPrimalObjectiveArgmax A Set.univ g 0 0 x)
(hg : ∀ z : E₂, HasFDerivAt g (gradg z) z)
(huniform :
∀ u₁ u₂ : E₂,
σg * Real.rpow ‖u₁ - u₂‖ p ≤ (gradg u₁ - gradg u₂) (u₁ - u₂))
(hf : ∀ x : E₁, HasFDerivAt f (A.flip (u x)) x) :
HolderGradientOn
(Real.toNNReal (1 / (p - 1)))
(Real.toNNReal
(Real.rpow (1 / σg) (1 / (p - 1)) * Real.rpow ‖A‖ (1 + 1 / (p - 1))))
Set.univ f (fun x ↦ A.flip (u x))
Proposition 6.17
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.17: rewriting the canonical induced-norm statement through continuousLocationSmoothingMap_primalDualOperatorNorm_eq_sqrt_totalPopulation, Seminorm.primalDualOperatorNorm_eq_sSup_dualPairing, continuousLocationSmoothingMap_apply, and continuousLocationDualTupleSeminorm_apply, and then transporting back along PiLp.continuousLinearEquiv, gives the source-facing unit-sphere formula for the weighted pairing.
open Metric
open scoped BigOperators SeminormOperatorNorm
universe u v
variable {ι : Type v}
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [Fintype ι]
local notation "E₂" => PiLp 2 fun _ : ι ↦ E
theorem continuousLocation_sSup_pairing_unitSpheres_eq_sqrt_totalPopulation
[FiniteDimensional ℝ E] [Nontrivial E] (weights : ContinuousLocationWeights ι) :
sSup ((fun xu : E × (ι → E) ↦ ∑ j, (weights j : ℝ) * inner ℝ (xu.2 j) xu.1) ''
Set.prod (sphere (0 : E) 1) {u | continuousLocationDualTupleNorm E weights u = 1}) =
Real.sqrt (continuousLocationTotalPopulation weights)Definition 6.18
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.18: expanding the gap function at a feasible point recovers the defining supremum of affine residuals over all feasible comparison points.
open scoped ConstrainedArgmin
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
namespace AffineVariationalInequalityProblem
theorem gapFunction_def
(problem : AffineVariationalInequalityProblem E) (w : problem.feasibleSet) :
problem.gapFunction w =
sSup
(Set.range fun v : problem.feasibleSet ↦
problem (v : E) ((w : E) - (v : E)))Proposition 6.18
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.18: if P = \sum_j m_j is positive and an iterate xHat satisfies f(xHat) - f* ≤ 2 P \bar f / √(N (N + 1)), then the scaled objective \bar f(x) = f(x) / P satisfies \bar f(xHat) - \bar f* ≤ 2 \bar f / √(N (N + 1)), with both optimal values taken through the Chapter 1 whole-space owner in EReal.
universe u
open scoped BigOperators
variable {X : Type u} {ι : Type*} [Fintype ι]
theorem scaledObjective_convergence_rate_bound
(m : ι → ℕ) (f : X → ℝ) (xHat : X) {fBar : ℝ} {N : ℕ}
(hP : 0 < ∑ j, (m j : ℝ))
(hbound :
(f xHat : EReal) -
((.mk Set.univ f : SetConstrainedMinimizationProblem X).optimalValue) ≤
(2 * (∑ j, (m j : ℝ)) * fBar) /
Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))) :
(averageIndividualExpense (∑ j, (m j : ℝ)) f xHat : EReal) -
((.mk Set.univ (averageIndividualExpense (∑ j, (m j : ℝ)) f) :
SetConstrainedMinimizationProblem X).optimalValue) ≤
(2 * fBar) / Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))Definition 6.19
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.19: in the primal-form smoothing specialization with E₁ = E₂ = E, Q₁ = Q₂ = Q, d₁ = d₂ = d, and A = B, the smoothed subproblem f_μ is the Chapter 6 regularized-supremum owner specialized to the dual penalty \hat φ(u) = ⟪b, u⟫ + ⟪Bu, u⟫.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
abbrev primalFormSmoothedObjective
(B : E →L[ℝ] StrongDual ℝ E) (Q : Set E) (b : StrongDual ℝ E) (d : E → ℝ) (μ : ℝ) :
E → ℝ :=
smoothedPrimalObjective B Q 0 (fun u ↦ b u + B u u) d μProposition 6.19
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.19: if the extended-real minimax and maximin values of (w, v) ↦ ⟨B(v), w - v⟩ coincide, then that common value is also the negative of min_{v ∈ Q} max_{w ∈ Q} ⟨B(v), v - w⟩.
open Module
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
theorem dualFormSmoothingRepresentation
(Q : Set E) (B : E → Dual ℝ E)
(hminimax :
(⨅ w : Q, ⨆ v : Q, ((B v (w - v) : ℝ) : EReal)) =
(⨆ v : Q, ⨅ w : Q, ((B v (w - v) : ℝ) : EReal))) :
(⨅ w : Q, ⨆ v : Q, ((B v (w - v) : ℝ) : EReal)) =
-⨅ v : Q, ⨆ w : Q, ((B v (v - w) : ℝ) : EReal)Definition 6.20
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.20: for an affine variational inequality problem VI(Q, B), a prox-function d : Q → ℝ, and a smoothing weight μ, the smoothed gap function sends a feasible point w to max_{v ∈ Q} (\langle B(v), w - v \rangle - μ d(v)), encoded in Lean as a supremum over the feasible subtype.
open Module
open scoped Pointwise
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
namespace AffineVariationalInequalityProblem
abbrev smoothedGapFunction
(problem : AffineVariationalInequalityProblem E)
(proxFunction : problem.feasibleSet → ℝ) (μ : ℝ) :
problem.feasibleSet → ℝ :=
fun w ↦
sSup
(Set.range fun v : problem.feasibleSet ↦
problem v ((w : E) - v) - μ * proxFunction v)Proposition 6.20
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.20: stacking A and -A and duplicating b identifies max_j (|⟪a_j, x⟫| - b_j) with the supremum of the corresponding affine functional over the standard simplex on the signed row index set.
open scoped BigOperators
variable {m : ℕ+} {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "F" => EuclideanSpace ℝ (Fin (m : ℕ))
local notation "G" => Fin (m : ℕ) ⊕ Fin (m : ℕ)
theorem max_abs_row_pairing_sub_offset_eq_sSup_signed_simplex
(A : Matrix (Fin (m : ℕ)) (Fin n) ℝ) (b : F) (x : E) :
Finset.univ.sup' Finset.univ_nonempty
(fun j : Fin (m : ℕ) ↦ |dotProduct (A j) x| - b j) =
sSup (Set.range fun u : StdSimplex ℝ G ↦
dotProduct ((Matrix.fromRows A (-A)).mulVec x) u.weights -
dotProduct (Sum.elim b b) u.weights)Definition 6.21
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.21: the max-absolute-value objective is bounded by t at x exactly when every shifted absolute dual pairing |aᵢ(x)| - bᵢ is bounded by t.
open scoped ConstrainedArgmin
universe u
variable {ι : Type*} [Fintype ι] [Nonempty ι]
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
theorem maxAbsoluteValueOptimizationObjective_le_iff
(a : ι → Module.Dual ℝ E) (b : ι → ℝ) (x : E) (t : ℝ) :
maxAbsoluteValueOptimizationObjective a b x ≤ t ↔
∀ i : ι, |a i x| - b i ≤ tProposition 6.21
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.21: the operator norm of the canonical signed stack equals twice the supremum over the unit sphere of the sum of the absolute row evaluations.
open Metric
open scoped BigOperators Pointwise
universe u
variable {ι : Type*} [Fintype ι]
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
local notation "G" => ι ⊕ ι
local notation "E₂" => PiLp 1 (fun _ : G ↦ ℝ)
local notation "Â[" a "]" => signedRowStack a
-- Proof sketch: expand the `ℓ¹` norm in `PiLp 1`; the signed stack has coordinates
-- `a_i x` and `-a_i x` over `ι ⊕ ι`, so the absolute values add to
-- `2 * ∑ j, |a j x|`.
theorem signedRowStack_opNorm_eq_two_mul_sSup_abs_rowSum
(a : ι → StrongDual ℝ E) :
‖Â[a]‖ =
2 * sSup ((fun x : E ↦ ∑ j, |a j x|) '' sphere (0 : E) 1)Definition 6.22
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.22: for linear functionals a₁, …, aₘ ∈ E*, offsets b ∈ ℝᵐ, and smoothing parameter μ > 0, the log-sum-exp smoothing of the Chapter 6 objective x ↦ max_i (|a_i(x)| - bⁱ) from Definition 6.21 is the function x ↦ μ log (((card ι)⁻¹) ∑ᵢ exp ((|aᵢ(x)| - bᵢ) / μ)). The nonempty finite-family assumptions are part of the mathematics here because the normalization factor is the average over the index family.
open scoped BigOperators
universe u v
variable {ι : Type v} [Fintype ι]
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
def logSumExpAbsoluteValueSmoothing
[Nonempty ι] (a : ι → Module.Dual ℝ E) (b : ι → ℝ) (μ : {μ : ℝ // 0 < μ}) : E → ℝ :=
fun x ↦
μ.1 * Real.log (((Fintype.card ι : ℝ)⁻¹) *
∑ i : ι, Real.exp ((|a i x| - b i) / μ.1))
-- Proof sketch: unfold `logSumExpAbsoluteValueSmoothing`; the displayed formula is exactly the
-- normalized log-sum-exp smoothing of the same family `i ↦ |a i x| - b i` used in
-- `maxAbsoluteValueOptimizationObjective`.Proposition 6.22
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.22: for the row map with coordinates x ↦ a_j(x), the supremum of ∑ⱼ u_j a_j(x) over the ambient unit ball of E and the weighted unit ball of weightedRowEuclideanSeminorm a in EuclideanSpace ℝ ι is bounded above by (∑ⱼ ‖a_j‖)^(1/2).
open scoped BigOperators
universe u v
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {ι : Type v} [Fintype ι]
local notation "E₂" => EuclideanSpace ℝ ι
theorem weightedRowPairing_sSup_le_sqrt_sum_rowNorms
(a : ι → StrongDual ℝ E) :
sSup ((fun xu : E × E₂ ↦ ∑ j : ι, xu.2 j * a j xu.1) ''
Set.prod {x : E | ‖x‖ ≤ 1}
{u : E₂ | weightedRowEuclideanSeminorm a u ≤ 1}) ≤
Real.sqrt (∑ j : ι, ‖a j‖)Definition 6.23
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.23: the sum-of-absolute-values optimization problem on a feasible set Q₁ minimizes x ↦ ∑ⱼ |aⱼ x - b⁽ʲ⁾| over Q₁.
open scoped BigOperators
open scoped ConstrainedArgmin
universe u
variable {m : ℕ}
variable {E₁ : Type u} [AddCommGroup E₁] [Module ℝ E₁]
def sumAbsoluteValuesOptimizationProblem
(Q₁ : Set E₁) (a : Fin m → Module.Dual ℝ E₁) (b : Fin m → ℝ) :
SetConstrainedMinimizationProblem E₁Proposition 6.23
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.23 (1): if v is obtained from u by subtracting the maximal coordinate coordinateMaximum u from every component, then the log-sum-exp potential satisfies η(u) = coordinateMaximum u + η(v).
open scoped BigOperators
open scoped Gradient
universe v
variable {ι : Type v} [Fintype ι]
variable {m : ℕ} [NeZero m]
local notation "U" => EuclideanSpace ℝ (Fin m)
theorem eta_eq_coordinateMaximum_add_eta_centered
(μ : {μ : ℝ // 0 < μ}) (u : U) :
η μ u = coordinateMaximum u + η μ (centeredByCoordinateMaximum u)Definition 6.24
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.24: evaluating quadratic_box_smoothed_objective a b μ gives the textbook supremum of the penalized affine maximand over the dual box Q₂.
open scoped BigOperators
universe u v
variable {ι : Type v}
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
local notation "E₂" => EuclideanSpace ℝ ι
variable [Fintype ι]
theorem quadratic_box_smoothed_objective_spec
(a : ι → StrongDual ℝ E) (b : E₂) (μ : {μ : ℝ // 0 < μ}) (x : E) :
quadratic_box_smoothed_objective a b μ x =
sSup
((fun u : E₂ ↦
(∑ j : ι, (a j x - b j) * u j) - (μ : ℝ) * quadratic_box_prox_function a u) ''
quadratic_box_dual_set)Proposition 6.24
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.24 (1) [Chapter6_2.json:64]: if \hat f has within-gradient field gradHatf on Q₁, \hat φ is convex on Q₂, d₂ is 1-strongly convex on Q₂, and u_{μ₂} selects a feasible maximizer of the canonical Chapter 6 argmax owner, then that maximizer is unique for every x ∈ Q₁, and the smoothed primal objective has within-gradient gradHatf x + A^* u_{μ₂}(x) on Q₁.
open scoped Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
theorem smoothedPrimalObjective_argmax_unique_and_hasGradientWithinAt
(A : E₁ →L[ℝ] StrongDual ℝ E₂)
{Q₁ : Set E₁} {Q₂ : Set E₂}
{hatf : E₁ → ℝ} {gradHatf : E₁ → E₁} {hatφ d₂ : E₂ → ℝ} {μ₂ : ℝ}
(hμ₂ : 0 < μ₂)
(hhatφ : ConvexOn ℝ Q₂ hatφ)
(hd₂ : StrongConvexOn Q₂ 1 d₂)
(hhatf_grad : ∀ ⦃x : E₁⦄, x ∈ Q₁ →
HasGradientWithinAt hatf (gradHatf x) Q₁ x)
{uμ₂ : E₁ → E₂}
(huμ₂ : ∀ ⦃x : E₁⦄, x ∈ Q₁ →
uμ₂ x ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ₂ x) :
(∀ ⦃x : E₁⦄, x ∈ Q₁ → ∀ ⦃u : E₂⦄,
u ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ₂ x → u = uμ₂ x) ∧
(∀ ⦃x : E₁⦄, x ∈ Q₁ →
HasGradientWithinAt
(smoothedPrimalObjective A Q₂ hatf hatφ d₂ μ₂)
(gradHatf x +
(InnerProductSpace.toDual ℝ E₁).symm (A.flip (uμ₂ x)))
Q₁ x)Definition 6.25
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.25's oracle subproblem is the Chapter 6 regularized dual maximand at the fixed iterate y_k together with its canonical argmax owner on Q₂.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
variable
(A : E₁ →L[ℝ] StrongDual ℝ E₂)
(yk : E₁) (μ : NNReal) (Q₂ : Set E₂) (hatφ d₂ : E₂ → ℝ) (u : E₂)
recall smoothedPrimalObjectiveMaximandProposition 6.25
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.25 (1) [Chapter6_2.json:67]: if \hat φ is differentiable on Q₂, \hat f is convex on Q₁, d₁ is 1-strongly convex on Q₁, and x_{μ₁} selects a feasible minimizer of the canonical argmin owner for each u ∈ Q₂, then that minimizer is unique and the finite real part of φ_{μ₁} has within-set gradient -\nabla \hat φ(u) + A x_{μ₁}(u), encoded by the Riesz-vector form of A (xμ₁ u).
open scoped ConstrainedArgmin Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
theorem smoothedDualObjective_argmin_unique_and_hasGradientWithinAt
(A : E₁ →L[ℝ] StrongDual ℝ E₂)
{Q₁ : Set E₁} {Q₂ : Set E₂}
{hatf : E₁ → ℝ} {hatφ : E₂ → ℝ} {d₁ : E₁ → ℝ}
{μ₁ : ℝ} (hμ₁ : 0 < μ₁)
(hhatf : ConvexOn ℝ Q₁ hatf)
(hd₁ : StrongConvexOn Q₁ 1 d₁)
(hhatφ : DifferentiableOn ℝ hatφ Q₂)
{xμ₁ : E₂ → E₁}
(hxμ₁ : ∀ ⦃u : E₂⦄, u ∈ Q₂ →
xμ₁ u ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf d₁ μ₁ u)) :
(∀ ⦃u : E₂⦄, u ∈ Q₂ → ∀ ⦃x : E₁⦄,
x ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf d₁ μ₁ u) → x = xμ₁ u) ∧
∀ ⦃u : E₂⦄, u ∈ Q₂ →
HasGradientWithinAt
(extendedRealRealPart (smoothedDualObjective A Q₁ hatf hatφ d₁ μ₁))
(-gradientWithin hatφ Q₂ u + (InnerProductSpace.toDual ℝ E₂).symm (A (xμ₁ u)))
Q₂ uDefinition 6.26
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.26: the proximal minimization subproblem is the constrained problem on the feasible subtype Q₁ whose objective is the canonical affine-plus-regularizer owner linearOptimizationOracleObjective s d₁. Its minimizer set is the canonical Chapter 1 owner argmin[Set.univ] (proximalMinimizationProblem Q₁ d₁ s).
open scoped ConstrainedArgmin
universe u
variable {E₁ : Type u} [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
def proximalMinimizationProblem
(Q₁ : Set E₁) (d₁ : Q₁ → ℝ) (s : StrongDual ℝ E₁) :
SetConstrainedMinimizationProblem Q₁Proposition 6.26
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.26 [Chapter6_2.json:74]: if the raw duality gap is bounded by μ₁ D₁ + μ₂ D₂ and the smoothing parameters satisfy μ₁ = λ₁ ‖A‖_{1,2} √(D₂ / D₁) and μ₂ = λ₂ ‖A‖_{1,2} √(D₁ / D₂), then the gap is bounded by (λ₁ + λ₂) ‖A‖_{1,2} √(D₁ D₂).
universe u v
variable {X : Type u} {U : Type v}
theorem raw_duality_gap_le_symmetric_bound_of_parametrized_smoothing_parameters
{f : X → ℝ} {φ : U → ℝ} {xBar : X} {uBar : U}
{D₁ D₂ lambda₁ lambda₂ μ₁ μ₂ opNorm12 : ℝ}
(hD₁ : 0 < D₁) (hD₂ : 0 < D₂)
(hμ₁ : μ₁ = lambda₁ * opNorm12 * Real.sqrt (D₂ / D₁))
(hμ₂ : μ₂ = lambda₂ * opNorm12 * Real.sqrt (D₁ / D₂))
(hgap : f xBar - φ uBar ≤ μ₁ * D₁ + μ₂ * D₂) :
f xBar - φ uBar ≤ (lambda₁ + lambda₂) * opNorm12 * Real.sqrt (D₁ * D₂)Definition 6.27
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.27: the textbook finite-family log-sum-exp potential is the canonical Chapter 6 owner η for a positive smoothing parameter and a finite score family.
open scoped BigOperators
universe v
variable {ι : Type v} [Fintype ι]
recall ηProposition 6.27
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.27 [Chapter6_1.json:79]: if μ₁ = λ₁ ‖A‖_{1,2} √(D₂ / D₁) and μ₂ = λ₂ ‖A‖_{1,2} √(D₁ / D₂), then the assumed duality-gap bound f(x̄) - φ(ū) ≤ μ₁ D₁ + μ₂ D₂ implies the symmetric estimate f(x̄) - φ(ū) ≤ (λ₁ + λ₂) ‖A‖_{1,2} √(D₁ D₂). The positivity assumptions λ₁, λ₂ > 0 and μ₁, μ₂ > 0 from the source are omitted because they are redundant for the inequality statement itself.
universe u v
variable {X : Type u} {U : Type v}
-- Proof sketch: substitute the defining formulas for `μ₁` and `μ₂` into the assumed duality-gap
-- bound, use `D₁ > 0` and `D₂ > 0` to simplify
-- `Real.sqrt (D₂ / D₁) * D₁ = Real.sqrt (D₁ * D₂)` and
-- `Real.sqrt (D₁ / D₂) * D₂ = Real.sqrt (D₁ * D₂)`, and then factor the common term
-- `opNorm12 * Real.sqrt (D₁ * D₂)`.
theorem duality_gap_le_symmetric_bound_of_parametrized_smoothing_parameters
{f : X → ℝ} {φ : U → ℝ} {xBar : X} {uBar : U}
{D₁ D₂ lambda₁ lambda₂ μ₁ μ₂ opNorm12 : ℝ}
(hD₁ : 0 < D₁) (hD₂ : 0 < D₂)
(hμ₁ : μ₁ = lambda₁ * opNorm12 * Real.sqrt (D₂ / D₁))
(hμ₂ : μ₂ = lambda₂ * opNorm12 * Real.sqrt (D₁ / D₂))
(hgap : f xBar - φ uBar ≤ μ₁ * D₁ + μ₂ * D₂) :
f xBar - φ uBar ≤ (lambda₁ + lambda₂) * opNorm12 * Real.sqrt (D₁ * D₂)Definition 6.28
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.28 [Chapter6_1.json:65]: a primal-dual objective model consists of finite-dimensional real vector spaces E₁ and E₂, nonempty bounded closed convex sets Q₁ ⊆ E₁ and Q₂ ⊆ E₂, continuous convex functions \hat f on Q₁ and \hat φ on Q₂, and a linear map A : E₁ → E₂*. Its primal objective, adjoint objective, primal optimal value f^*, and adjoint optimal value f_* are the canonical Chapter 6 constructions attached to this structured data.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
structure PrimalDualObjectiveModel (E₁ : Type u) (E₂ : Type v)
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁] [FiniteDimensional ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂] [FiniteDimensional ℝ E₂]
extends StructuredObjectiveModel E₁ E₂ where
/-- The primal feasible set `Q₁` is nonempty. -/
primalSet_nonempty : primalSet.Nonempty
/-- The dual feasible set `Q₂` is nonempty. -/
dualSet_nonempty : dualSet.NonemptyProposition 6.28
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.28 [Chapter6_2.json:92]: for the objective x ↦ (1 / 2) ‖x‖^2 + max_j (f_j + ⟪g_j, x - x_j⟫) and the associated dual objective u ↦ -(1 / 2) ‖∑_j u_j g_j‖^2 - ∑_j u_j (⟪g_j, x_j⟫ - f_j), if the averaged iterates of scheme (6.2.37) satisfy the entropy-smoothed lower approximation with budget μ log m and the stagewise excessive-gap inequality at μ₂,k = 4 ‖A‖_{1,2}^2 / ((k + 1) (k + 2)), then f(x̄_k) - φ(ū_k) ≤ 4 log m · ‖A‖_{1,2}^2 / ((k + 1) (k + 2)).
open scoped BigOperators
open scoped StandardSimplex
variable (n : ℕ) (m : ℕ+)
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem strongly_convex_max_affine_primal_dual_gap_le_entropy_rate
(f : Fin (m : ℕ) → ℝ) (g points : Fin (m : ℕ) → E)
(fμ₂ : ℝ → E → ℝ) (barx : ℕ → E) (baru : ℕ → Δ[m])
(happrox :
∀ μ x,
strongly_convex_max_affine_objective n m f g points x - μ * Real.log (m : ℝ) ≤
fμ₂ μ x)
(hscheme :
∀ k : ℕ,
fμ₂
((4 * (strongly_convex_max_affine_operator_norm_12 n m g) ^ (2 : ℕ)) /
(((k : ℝ) + 1) * ((k : ℝ) + 2)))
(barx k) ≤
strongly_convex_max_affine_dual_objective n m f g points (baru k))
(k : ℕ) :
strongly_convex_max_affine_objective n m f g points (barx k) -
strongly_convex_max_affine_dual_objective n m f g points (baru k) ≤
(4 * Real.log (m : ℝ) * (strongly_convex_max_affine_operator_norm_12 n m g) ^ (2 : ℕ)) /
(((k : ℝ) + 1) * ((k : ℝ) + 2))Definition 6.29
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.29 uses the chapter's canonical prox-function owner and the canonical normalized prox-center owner.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable (p : Seminorm ℝ E) [Seminorm.IsNorm p]
variable (Q : Set E) (d : E → ℝ) (x₀ : E)
recall NesterovIsProxFunctionProposition 6.29
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.29: a simplex point maximizes the entropy-regularized affine objective exactly when it is the canonical softmax point with coordinates exp (s_j / μ₂) / \sum_l exp (s_l / μ₂), where s_j = f_j + ⟪g_j, xBar - x_j⟫.
open scoped BigOperators
open scoped StandardSimplex
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (m : ℕ+)
local notation "S" => EuclideanSpace ℝ (Fin (m : ℕ))
theorem entropyRegularizedAffineSimplexObjective_isMaxOn_iff
{μ₂ : ℝ} (hμ₂ : 0 < μ₂) (xBar : E) (f : Fin (m : ℕ) → ℝ)
(g points : Fin (m : ℕ) → E) (u : Δ[m]) :
IsMaxOn
(fun v : Δ[m] ↦
(∑ j : Fin (m : ℕ), v j * (f j + inner ℝ (g j) (xBar - points j))) -
μ₂ * (Real.log (m : ℝ) + ∑ j : Fin (m : ℕ), v j * Real.log (v j)))
Set.univ u ↔
u = entropySimplexSoftmax m ⟨μ₂, hμ₂⟩ (entropyRegularizedAffineScores m xBar f g points)
Definition 6.30
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.30: for a positive smoothing parameter μ₂ and a prox-function d₂ on Q₂, smoothedPrimalObjective A Q₂ hatf hatφ d₂ μ₂ x is the smoothed primal objective f_{μ₂}(x) = \hat f(x) + max_{u ∈ Q₂} {⟪A x, u⟫ - \hat φ(u) - μ₂ d₂(u)}, recorded in Lean as hatf x + sSup (...); this agrees with the displayed maximum whenever a maximizer exists.
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
def smoothedPrimalObjective
(A : E₁ →L[ℝ] StrongDual ℝ E₂) (Q₂ : Set E₂)
(hatf : E₁ → ℝ) (hatφ d₂ : E₂ → ℝ) (μ₂ : ℝ) : E₁ → ℝ :=
fun x ↦ hatf x + sSup (smoothedPrimalObjectiveMaximand A hatφ d₂ μ₂ x '' Q₂)
-- Proof sketch: unfold `smoothedPrimalObjective`; the right-hand side is exactly the defining
-- formula `\hat f(x) + sup_{u ∈ Q₂} (⟪A x, u⟫ - \hat φ(u) - μ₂ d₂(u))`.Proposition 6.30
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.30 [Chapter6_1.json:99]: for the affine scores s_j = f_j + ⟪g_j, xBar - x_j⟫ and every μ₂ > 0, the problem max_{u ∈ Δ_m} {∑_j u_j s_j - μ₂ (log m + ∑_j u_j log u_j)} is maximized by the canonical softmax point, and every simplex maximizer equals that point. In particular, the maximizer is unique and is given componentwise by the normalized exponential formula from entropySimplexSoftmax_apply.
open scoped BigOperators
open scoped StandardSimplex
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (m : ℕ+)
local notation "S" => EuclideanSpace ℝ (Fin (m : ℕ))
theorem entropyRegularizedAffineSimplexObjective_hasUniqueMaximizer
{μ₂ : ℝ} (hμ₂ : 0 < μ₂) (xBar : E) (f : Fin (m : ℕ) → ℝ)
(g points : Fin (m : ℕ) → E) :
IsMaxOn
(fun v : Δ[m] ↦
(∑ j : Fin (m : ℕ), v j * (f j + inner ℝ (g j) (xBar - points j))) -
μ₂ * (Real.log (m : ℝ) + ∑ j : Fin (m : ℕ), v j * Real.log (v j)))
Set.univ
(entropySimplexSoftmax m ⟨μ₂, hμ₂⟩
(entropyRegularizedAffineScores m xBar f g points)) ∧
∀ u : Δ[m],
IsMaxOn
(fun v : Δ[m] ↦
(∑ j : Fin (m : ℕ), v j * (f j + inner ℝ (g j) (xBar - points j))) -
μ₂ * (Real.log (m : ℝ) + ∑ j : Fin (m : ℕ), v j * Real.log (v j)))
Set.univ u →
u = entropySimplexSoftmax m ⟨μ₂, hμ₂⟩
(entropyRegularizedAffineScores m xBar f g points)Definition 6.31
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.31 [Chapter6_1.json:68]: a prox-center of d on Q is a feasible minimizer x₀, together with the standard normalization d x₀ = 0.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {p : Seminorm ℝ E} [Seminorm.IsNorm p]
variable {Q : Set E} {d : E → ℝ}
structure NesterovIsProxCenter (Q : Set E) (d : E → ℝ) (x₀ : E) : Prop where
/-- A prox-center belongs to the feasible set. -/
mem : x₀ ∈ Q
/-- A prox-center minimizes `d` on the feasible set. -/
isMinOn : IsMinOn d Q x₀
/-- The prox-function is normalized to vanish at the prox-center. -/
value_eq_zero : d x₀ = 0Proposition 6.31
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.31 [Chapter6_1.json:100]: if x0(uHat) is chosen in argmin_x {⟪A x, uHat⟫ + (1 / 2) ‖x‖²}, then x0(uHat) = -Aᵀ uHat.
open scoped ConstrainedArgmin
variable {m n : ℕ}
local notation "E₁" => EuclideanSpace ℝ (Fin n)
local notation "E₂" => EuclideanSpace ℝ (Fin m)
theorem euclideanLinearQuadraticMinimizer_eq_neg_transpose_apply
(A : Matrix (Fin m) (Fin n) ℝ) (uHat : E₂) {x0 : E₁}
(hx0 : x0 ∈ argmin[Set.univ] (euclideanLinearQuadraticMinimand A uHat)) :
x0 = -(A.transpose.toEuclideanLin uHat)Definition 6.32
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.32 [Chapter6_1.json:70]: a prox-function on Q₁ with respect to the norm p is the chapter's canonical owner NesterovIsProxFunction p Q₁ d₁; a prox-center is the canonical normalized minimizer owner NesterovIsProxCenter Q₁ d₁ x₀.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable (p : Seminorm ℝ E) [Seminorm.IsNorm p]
variable (Q₁ : Set E) (d₁ : E → ℝ) (x₀ : E)
recall NesterovIsProxFunctionProposition 6.32
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.32 [Chapter6_1.json:101] (2): the dual objective is differentiable on EuclideanSpace ℝ ι, and at every u its gradient is -b - A(Aᵀ u), encoded by the canonical pointwise owner HasGradientAt.
open scoped BigOperators InnerProduct
universe u v
variable {ι : Type v} [Fintype ι] [DecidableEq ι]
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
local notation "E₂" => EuclideanSpace ℝ ι
theorem affine_minorant_dualObjective_hasGradientAt
(g points : ι → E) (f : ι → ℝ) (u : E₂) :
HasGradientAt
(affine_minorant_dualObjective g points f)
(-affine_minorant_offset g points f -
affine_minorant_rowMap g (affine_minorant_adjointMap g u))
uDefinition 6.33
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.33 [Chapter6_1.json:71]: a feasible pair (xBar, uBar) ∈ Q₁ × Q₂ satisfies the excessive gap condition exactly when the smoothed primal value f_{μ₂}(xBar) is bounded above by the smoothed dual value φ_{μ₁}(uBar), namely the chapter owner satisfiesExcessiveGapCondition.
universe u v
variable {X : Type u} {U : Type v}
variable (Q₁ : Set X) (Q₂ : Set U)
variable (fμ₂ : X → ℝ) (φμ₁ : U → ℝ)
variable (xBar : Q₁) (uBar : Q₂)
recall satisfiesExcessiveGapConditionProposition 6.33
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.33: on 𝕊^n, the second directional derivative of X ↦ Trace (X^k) is the ambient trace/Frobenius sum k ∑_{p=0}^{k-2} trace ((X^p H X^(k-2-p))ᵀ H) for k ≥ 1.
open Matrix
open RealSymmetricMatrixSpace
open scoped RealSymmetricMatrixSpace
open scoped RightActions
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem powerTrace_iteratedFDeriv_two_eq_frobenius_sum
(k : ℕ) (hk : 1 ≤ k) (X H : SymmMat) :
iteratedFDeriv ℝ 2 (π[k] : SymmMat → ℝ) X ![H, H] =
(k : ℝ) *
(Finset.range (k - 1)).sum fun p ↦
Matrix.trace
(((((X ^ p : SymmMat) : Mat) * (H : Mat) *
((X ^ (k - 2 - p) : SymmMat) : Mat))ᵀ) * (H : Mat))
Definition 6.34
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.34 [Chapter6_2.json:73]: the smoothness parameters are the pair (μ₁, μ₂) defined by μ₁ = λ₁ ‖A‖_{1,2} √(D₂ / D₁) and μ₂ = λ₂ ‖A‖_{1,2} √(D₁ / D₂).
def smoothness_parameters
(D1 D2 opNorm12 lambda1 lambda2 : ℝ) : ℝ × ℝ :=
( lambda1 * opNorm12 * Real.sqrt (D2 / D1)
, lambda2 * opNorm12 * Real.sqrt (D1 / D2) )
-- Proof sketch: unfold `smoothness_parameters`; the first projection of the defining pair is
-- exactly the displayed formula for `μ₁`.Proposition 6.34
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.34 [Hessian bound for F_p]: for real symmetric matrices X and H, the Hessian quadratic form of the source smoothing functional F_p(X) = (1 / 2) * (π[2 * (p : ℕ)] X)^(1 / p) = (1 / 2) * ‖λ(X)‖_(2p)^2 is bounded above by (2p - 1) ‖λ(H)‖_(2p)^2, written here via the equivalent trace-power formula (2p - 1) * (π[2p] H)^(1 / p).
open RealSymmetricMatrixSpace
open scoped Gradient
open scoped MatrixOrder
open scoped RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem half_powerTrace_iteratedFDeriv_two_le
(p : ℕ+) (X H : SymmMat) :
iteratedFDeriv ℝ 2 (squaredLpMatrixNormSmoothing p) X ![H, H] ≤
(2 * (p : ℕ) - 1 : ℝ) * Real.rpow (π[2 * (p : ℕ)] H) (1 / (p : ℝ))
Definition 6.35
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.35 [Chapter6_1.json:78]: the smoothness parameters are the ordered pair (μ₁, μ₂) with μ₁ = λ₁ ‖A‖_{1,2} √(D₂ / D₁) and μ₂ = λ₂ ‖A‖_{1,2} √(D₁ / D₂).
recall smoothness_parametersProposition 6.35
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.35: the entropy-smoothing function E(X) = log (∑ᵢ exp (λᵢ(X))) on 𝕊^n is twice Fréchet differentiable, and its Hessian quadratic form in any symmetric direction H is bounded above by the square of the ambient matrix L² operator norm, i.e. by the square of the spectral norm of H.
open Matrix
open NormedSpace
open RealSymmetricMatrixSpace
open scoped BigOperators RealSymmetricMatrixSpace
open scoped RightActions
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
open scoped Matrix.Norms.L2Operator
theorem entropySmoothing_contDiff_and_hessianQuadraticForm_le (n : ℕ) :
ContDiff ℝ 2 (entropySmoothing : 𝕊^n → ℝ) ∧
∀ X H : 𝕊^n,
(iteratedFDeriv ℝ 2 (entropySmoothing : 𝕊^n → ℝ) X) ![H, H] ≤
(‖((H : Matrix (Fin n) (Fin n) ℝ))‖) ^ (2 : ℕ)
Definition 6.36
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.36 [Chapter6_2.json:79]: for a sequence α_k indexed by integers k ≥ -1, switching_parameters α k = (λ₁,k, λ₂,k), where for even k one has λ₁,k = α_{k-1} and λ₂,k = α_k, while for odd k one has λ₁,k = α_k and λ₂,k = α_{k-1}.
universe u
variable {M : Type u}
-- Proof sketch: the integer index `(k : ℤ)` is always at least `-1` because `k ≥ 0`.
def switching_parameters (α : Set.Ici (-1 : ℤ) → M) (k : ℕ) : M × M :=
if Even k then
(α (switching_parameters_pred_index k), α (switching_parameters_curr_index k))
else
(α (switching_parameters_curr_index k), α (switching_parameters_pred_index k))
-- Proof sketch: unfold `switching_parameters` and simplify the parity split using `hk`.Proposition 6.36
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.36 (2): for μ > 0, the smoothed maximal eigenvalue is differentiable on 𝕊^n, and its Fréchet derivative in direction H is the Frobenius pairing with the normalized matrix exponential.
open Matrix
open NormedSpace
open RealSymmetricMatrixSpace
open scoped BigOperators RealSymmetricMatrixSpace
open scoped RightActions
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
open RealSymmetricMatrixSpace
-- Proof sketch: rewrite `exp ((μ⁻¹) • X)` as the real continuous functional calculus of
-- `t ↦ exp (μ⁻¹ t)` applied to `X`, then evaluate that functional calculus by the Hermitian
-- spectral theorem and take the trace of the resulting diagonal form.
theorem differentiableAt_logSumExpMaxEigenvalueSmoothing_and_fderiv_eq_frobeniusInner
(μ : {μ : ℝ // 0 < μ}) (X : SymmMat) :
DifferentiableAt ℝ (logSumExpMaxEigenvalueSmoothing μ) X ∧
∀ H : SymmMat,
fderiv ℝ (logSumExpMaxEigenvalueSmoothing μ) X H =
⟪exponentialGradient μ X, H⟫_F
Definition 6.37
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.37, owner form: positive whole-space strong convexity.
open scoped Gradient StrongConvex WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (σ : ℝ) (f : E → ℝ)
#check (f ∈ 𝒮^0_σ(Set.univ))
Proposition 6.37
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.37: if φμ is a smoothing of φ on Q satisfying φμ(y) ≤ φ(y) for every feasible y and φ(yBar) ≤ φμ(yBar) + μ log n at the feasible point yBar, then any ε / 2-approximate minimizer of the smoothed problem is an ε-approximate minimizer of the original problem whenever μ log n ≤ ε / 2.
universe u
variable {X : Type u}
theorem isApproximateMinimizer_of_smoothedObjective_suboptimality
{Q : Set X} {φ φμ : X → ℝ} {n : ℕ} {μ ε : ℝ} {yBar : X}
(happrox_lower : ∀ y ∈ Q, φμ y ≤ φ y)
(happrox_upper : φ yBar ≤ φμ yBar + μ * Real.log (n : ℝ))
(hsmoothed :
(SetConstrainedMinimizationProblem.mk Q φμ).IsApproximateMinimizer (ε / 2) yBar)
(hμ_budget : μ * Real.log (n : ℝ) ≤ ε / 2) :
(SetConstrainedMinimizationProblem.mk Q φ).IsApproximateMinimizer ε yBarDefinition 6.38
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.38 [Chapter6_1.json:87]: a feasible pair (xBar, uBar) in Q1 x Q2 satisfies the excessive gap condition with mu1 = 0 exactly when f_{mu2}(xBar) <= phi(uBar), namely the chapter owner satisfiesExcessiveGapConditionWithMu1Zero.
universe u v
variable {X : Type u} {U : Type v}
variable (Q₁ : Set X) (Q₂ : Set U)
variable (fμ₂ : Q₁ → ℝ) (φ : Q₂ → ℝ)
variable (xBar : Q₁) (uBar : Q₂)
recall satisfiesExcessiveGapConditionWithMu1ZeroProposition 6.38
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.38 [Lipschitz constant for ∇φ_μ]: for the Chapter 6 smoothing pullback φ_μ(y) = f_μ (C + A y) = smoothedSemidefiniteObjective n μ C A y, the gradient is Lipschitz on Q with constant μ⁻¹ ‖A‖². The Hessian quadratic-form estimate is recorded in smoothedSemidefiniteObjective_hessianQuadraticForm_le_on, and the specialization μ = ε / (2 * log n) is recorded just below.
open Matrix
open RealSymmetricMatrixSpace
open scoped Gradient Matrix.Norms.L2Operator RealSymmetricMatrixSpace StandardSimplex
universe u
variable {E : Type u} [NormedAddCommGroup E]
variable {n : ℕ}
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem smoothedSemidefiniteObjective_gradient_lipschitzOn
[InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
(μ : {μ : ℝ // 0 < μ}) (Q : Set E)
(C : 𝕊^n) (A : E →L[ℝ] 𝕊^n) :
LipschitzOnWith
(Real.toNNReal ((1 / (μ : ℝ)) * ‖A‖ ^ (2 : ℕ)))
(fun y ↦ gradient (smoothedSemidefiniteObjective n μ C A) y) Q
Definition 6.39
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.39 [Chapter6_1.json:91]: a feasible pair (xBar, uBar) satisfies the excessive gap condition with μ₁ = 0 when the smoothed primal value f_{μ₂}(xBar) is bounded above by the dual value φ(uBar).
universe u v
variable {X : Type u} {U : Type v}
variable {Q₁ : Set X} {Q₂ : Set U}
abbrev satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂ : Q₁ → ℝ) (φ : Q₂ → ℝ) (xBar : Q₁) (uBar : Q₂) : Prop :=
fμ₂ xBar ≤ φ uBar
-- Proof sketch: unfold `satisfiesExcessiveGapConditionWithMu1Zero`.Proposition 6.39
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.39: if a chosen within-derivative field g for f on a convex feasible set Q is v-Hölder continuous with constant Gv for some 0 < v, then f satisfies the first-order upper model f y ≤ f x + g x (y - x) + (Gv / (1 + v)) * ‖y - x‖^(1 + v) on Q.
universe u
open ConditionalGradientContraction
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
namespace ConditionalGradientContraction.HolderGradientOn
theorem upper_model
{Q : Set E} {f : E → ℝ} {g : E → StrongDual ℝ E} {v Gv : NNReal}
(hf : HolderGradientOn v Gv Q f g) (hQ_convex : Convex ℝ Q) (hv : 0 < (v : ℝ))
{x y : E} (hx : x ∈ Q) (hy : y ∈ Q) :
f y ≤
f x + g x (y - x) +
((Gv : ℝ) / (1 + (v : ℝ))) * Real.rpow ‖y - x‖ (1 + (v : ℝ))
Definition 6.40
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.40 [Chapter6_1.json:93]: an adjoint gradient mapping on Q₂ is a feasible-set endomorphism V : Q₂ → Q₂ such that for every u ∈ Q₂, the point V(u) belongs to the feasible argmax set of v ↦ ⟪∇φ(u), v - u⟫ - (L₂(φ) / 2) ‖v - u‖² on Q₂.
universe u
variable {E₂ : Type u}
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
abbrev IsAdjointGradientMappingOn
(Q₂ : Set E₂) (φ : E₂ → ℝ) (Lphi : ℝ) (V : Q₂ → Q₂) : Prop :=
∀ u : Q₂, (V u : E₂) ∈ adjointGradientArgmax Q₂ φ Lphi (u : E₂)
-- Proof sketch: rewrite each pointwise argmax-membership condition with
-- `mem_adjointGradientArgmax_iff`; feasibility of `V u` is automatic from the codomain `Q₂`,
-- leaving exactly the `IsMaxOn` clause.Proposition 6.40
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.40: if the canonical iterated within second Fréchet derivative of f is v-Hölder on the convex set Q, then f admits the quadratic upper model with Hölder remainder H * ‖y - x‖^(2 + v) / ((1 + v) * (2 + v)).
universe u
open ConditionalGradientContraction
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem holder_hessian_upper_model
{E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
{Q : Set E} {f : E → ℝ} {v H : NNReal}
(hQ_unique : UniqueDiffOn ℝ Q)
(hf : DifferentiableOn ℝ f Q)
(hf' : DifferentiableOn ℝ (fderivWithin ℝ f Q) Q)
(hH : HolderOnWith H v (iteratedFDerivWithin ℝ 2 f Q) Q)
(hQ_convex : Convex ℝ Q)
{x y : E} (hx : x ∈ Q) (hy : y ∈ Q) :
f y ≤
f x + fderivWithin ℝ f Q x (y - x) +
(1 / 2 : ℝ) * iteratedFDerivWithin ℝ 2 f Q x ![y - x, y - x] +
(H : ℝ) * Real.rpow ‖y - x‖ (2 + (v : ℝ)) /
((1 + (v : ℝ)) * (2 + (v : ℝ)))
Definition 6.41
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.41: the spectral p-norm can equally be computed from the ordered eigenvalues of |X|.
open Matrix
open RealSymmetricMatrixSpace
open scoped MatrixOrder RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem symmetricMatrixSpectralPNorm_eq_abs_eigenvalueNorm
(p : Set.Ici (1 : ENNReal)) (X : SymmMat) :
symmetricMatrixSpectralPNorm p X =
‖WithLp.toLp (p : ENNReal) (eigenvalues (|X|))‖
Proposition 6.41
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.41: if a feasible point v ∈ Q satisfies the affine optimality inequality ⟪s, x - v⟫ + Ψ(x) ≥ Ψ(v) for every x ∈ Q, then -s belongs to the constrained subdifferential of Ψ at v relative to Q.
open scoped WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem neg_mem_constrainedSubdifferential_of_affine_optimality
{Q : Set E} {Ψ : E → WithTop ℝ} {s v : E}
(hvQ : v ∈ Q)
(hv_finite : Ψ v < ⊤)
(hoptimal :
∀ ⦃x : E⦄, x ∈ Q →
(((inner ℝ s (x - v) : ℝ) : WithTop ℝ) + Ψ x) ≥ Ψ v) :
-s ∈ ∂[Q] Ψ(v)Definition 6.42
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.42: on 𝕊^n, the textbook quantity π_k(X) is the ambient trace-power expression Trace (X^k).
open Matrix
open RealSymmetricMatrixSpace
open scoped RealSymmetricMatrixSpace
variable {n : ℕ}
namespace RealSymmetricMatrixSpace
abbrev powerTrace (k : ℕ) (X : 𝕊^n) : ℝ :=
Matrix.trace (((X ^ k : 𝕊^n) : Matrix (Fin n) (Fin n) ℝ))
Proposition 6.42
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.42, first clause: a Hölder affine lower model at x₀ bounds the linearized composite gap by the supremum of the corresponding Hölder upper-gap expression over S.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
open ConditionalGradientContraction
open scoped Gradient TotalVariationNotation
variable {S : Set E} {f Ψ : E → ℝ} {x0 : S} {g : StrongDual ℝ E} {Gv ν : ℝ}
theorem linearizedCompositeGap_le_holderUpperGapSup
(hmodel : HasHolderLowerModelOn S f x0 g Gv ν) :
linearizedCompositeGap S Ψ g x0 ≤
sSup
((fun x : E ↦
((f x0 - f x + Gv * Real.rpow ‖x - x0‖ (1 + ν) / (1 + ν) + Ψ x0 - Ψ x : ℝ) :
EReal)) '' S)Definition 6.43
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.43: the matrix spectral function of Φ is the Chapter 6 trace-power series attached to the owner π[k]. This is the thin bridge from the source-facing spectral sum to the existing trace-power owners.
open RealSymmetricMatrixSpace
open scoped BigOperators RealSymmetricMatrixSpace
namespace AnalyticSymmetricSpectralFunction
variable (Φ : AnalyticSymmetricSpectralFunction)
theorem matrixFun_hasSum_powerTrace {n : ℕ} {X : 𝕊^n} (hX : X ∈ Φ.dom) :
HasSum (fun k : ℕ ↦ Φ.coeff k * π[k] X) (Φ.matrixFun X)
Proposition 6.43
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.43: if xStar minimizes the composite objective \bar f = f + Ψ on Q and δ dominates the gap \bar f(x) - \bar f(xStar) for every x, then for each x the same gap is nonnegative and still bounded above by δ x.
universe u
variable {Q : Type u}
theorem delta_ge_compositeObjective_gap_and_nonneg
{f Ψ δ : Q → ℝ} {xStar x : Q}
(hxStar : IsMinOn (f + Ψ) Set.univ xStar)
(hdelta :
∀ y : Q, δ y ≥ (f y + Ψ y) - (f xStar + Ψ xStar)) :
δ x ≥ (f x + Ψ x) - (f xStar + Ψ xStar) ∧
0 ≤ (f x + Ψ x) - (f xStar + Ψ xStar)Definition 6.44
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.44: for a positive integer p, squaredLpMatrixNormSmoothing p X is the matrix smoothing functional F_p(X) = (1 / 2) ‖λ(X)‖_(2p)^2 = (1 / 2) (π_{2p}(X))^(1 / p) on the symmetric-matrix space 𝕊^n.
open RealSymmetricMatrixSpace
open scoped RealSymmetricMatrixSpace
variable {n : ℕ}
def squaredLpMatrixNormSmoothing (p : ℕ+) (X : 𝕊^n) : ℝ :=
(1 / 2 : ℝ) * Real.rpow (π[2 * (p : ℕ)] X) (1 / (p : ℝ))
-- Proof sketch: diagonalize the symmetric matrix `X`, rewrite the `ℓ_{2p}`-norm of `λ(X)` as the
-- `2p`-power sum of its eigenvalues, and identify that power sum with the trace formula
-- `π_{2p}(X) = Trace(X^(2p))`.
Proposition 6.44
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.44: let T ≥ 1 be odd. Along the Chapter 6 conditional-gradient scheme, if the step sizes are the standard coefficients τ_t = τ[standardWeight](t) = 2 / (t + 2), the smooth part has ν = 1 Hölder gradient on the feasible set with constant G₁, the feasible set has diameter bounded by D, the chosen dual field agrees with the ambient gradient along the first T + 1 iterates, and the total variations along the first T + 1 iterates are finite, then the sampled minimum total variation `δ_T^* = bestFunctionValueUpTo (fun t ↦ linearModelTotalVariationReal problem.feasibleSet problem.smoothPart (withTopRealPart problem.nonsmoothPart) ⟨method t, method.iterates_mem_feasibleSet t⟩) T` satisfies δ_T^* ≤ (34 / (11 log 2)) G₁ D^2 / (T + 1).
open scoped BigOperators WeightSequenceNotation TotalVariationNotation
universe u
namespace ConditionalGradientContraction
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem bestFunctionValueUpTo_totalVariationReal_le_standard_weight_rate_nu_one
{problem : CompositeConvexMinimizationProblem E} {x0 : problem.feasibleSet}
(method : ContractedFeasibleSetTrustRegionScheme problem x0) (G₁ : NNReal) (D : ℝ) {T : ℕ}
(hTpos : 1 ≤ T) (hTodd : Odd T)
(hstep : ∀ t : ℕ, method.stepSize t = τ[standardWeight](t))
(hholder :
HolderGradientOn 1 G₁ problem.feasibleSet problem.smoothPart method.gradient)
(hgradient :
∀ t : ℕ, t ≤ T →
method.gradient (method t) =
InnerProductSpace.toDualMap ℝ E (gradient problem.smoothPart (method.iterates t)))
(hdiam :
∀ ⦃x y : E⦄, x ∈ problem.feasibleSet → y ∈ problem.feasibleSet → ‖x - y‖ ≤ D)
(hfinite :
∀ t : ℕ, t ≤ T →
δ[problem.feasibleSet, problem.smoothPart, withTopRealPart problem.nonsmoothPart](⟨method t,
method.iterates_mem_feasibleSet t⟩) ≠ ⊤) :
bestFunctionValueUpTo
(fun t ↦
linearModelTotalVariationReal
problem.feasibleSet problem.smoothPart (withTopRealPart problem.nonsmoothPart)
⟨method t, method.iterates_mem_feasibleSet t⟩)
T ≤
(34 / (11 * Real.log 2)) * (G₁ : ℝ) * D ^ (2 : ℕ) / ((T + 1 : ℕ) : ℝ)
Definition 6.45
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.45 is recalled directly from the Chapter 6 owner entropySmoothing.
open Matrix
open RealSymmetricMatrixSpace
open scoped BigOperators RealSymmetricMatrixSpace
variable {n : ℕ}
#check (entropySmoothing : 𝕊^n → ℝ)
Proposition 6.45
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.45: if f̄(x) is the attained maximum of the fixed-x saddle slice u ↦ Ψ(x, u) on Q₂ and ḡ(u) is the attained minimum of the fixed-u saddle slice y ↦ Ψ(y, u) on Q₁, then the weak-duality gap f̄(x) - ḡ(u) is nonnegative.
universe u v
namespace StructuredObjectiveModel
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
theorem weakDualityGap_nonneg_of_attainedExtrema
{problem : StructuredObjectiveModel E₁ E₂}
(x : problem.primalSet) (u : problem.dualSet) {fBar gBar : ℝ}
(hprimal : IsGreatest (Set.range (problem.saddleFunction x)) fBar)
(hdual :
IsLeast
(Set.range fun y : problem.primalSet ↦ problem.saddleFunction y u)
gBar) :
0 ≤ fBar - gBarDefinition 6.46
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.46: the linear matrix operator A(y) = ∑ᵢ yᵢ Aᵢ attached to the coefficient matrices of the problem, landing directly in the symmetric-matrix owner 𝕊^n.
open Matrix
open scoped BigOperators RealSymmetricMatrixSpace
namespace NonsmoothEigenvalueMinimizationProblem
open RealSymmetricMatrixSpace
def linearOperator (problem : NonsmoothEigenvalueMinimizationProblem m n) :
EuclideanSpace ℝ (Fin m) →ₗ[ℝ] 𝕊^n
Proposition 6.46
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.46: if uBar attains the supremum defining the zero-smoothed Chapter 6 primal objective at xBar and the gradient at xBar is the vector representative of A^* uBar, then for every x the affine tangent identity f(xBar) + ⟪∇f(xBar), x - xBar⟫ = A x uBar - g uBar holds for f = smoothedPrimalObjective A Qd 0 g 0 0.
open scoped Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
theorem affine_minorant_identity
{A : E₁ →L[ℝ] StrongDual ℝ E₂} {Qd : Set E₂} {g : E₂ → ℝ}
{xBar x : E₁} {uBar : E₂}
(huBar : uBar ∈ smoothedPrimalObjectiveArgmax A Qd g 0 0 xBar)
(hgrad :
∇ (smoothedPrimalObjective A Qd 0 g 0 0) xBar =
(InnerProductSpace.toDual ℝ E₁).symm (A.flip uBar)) :
smoothedPrimalObjective A Qd 0 g 0 0 xBar +
inner ℝ (∇ (smoothedPrimalObjective A Qd 0 g 0 0) xBar) (x - xBar) =
A x uBar - g uBarDefinition 6.47
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.47: for a positive smoothing parameter μ and a real symmetric matrix X, the log-sum-exp smoothing of λ_max is f_μ(X) = μ log (∑ i, exp (λ_i(X) / μ)).
open RealSymmetricMatrixSpace
open scoped BigOperators RealSymmetricMatrixSpace
variable {n : ℕ}
def logSumExpMaxEigenvalueSmoothing
(μ : {μ : ℝ // 0 < μ}) (X : 𝕊^n) : ℝ :=
(μ : ℝ) * Real.log (∑ i : Fin n, Real.exp (eigenvalues X i / (μ : ℝ)))Proposition 6.47
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.47 [Duality-gap bound for averaged dual iterate (method 1)]. For the present finite-valued Chapter 6 surface, the book's minima are formalized by the real infima Φ(ν) = sInf (Set.range fun x : Q ↦ ψ x + A (x : E) ν). The bounded-below hypothesis on the dual slice at the averaged dual iterate ν_t is therefore kept explicit, and the companion theorems localModelAccuracyCertificate_gap_upper_bound_of_dual_average and localModelAccuracyCertificate_gap_bound_of_dual_average record the corresponding explicit sInf / zero-smoothing formulas. On this finite-valued surface the source's weak-duality comparison \bar g(ν_t) ≤ \bar f(x_t) is also kept explicit. Under that comparison and the certificate bound \bar f(x_t) - ℓ_t ≤ B_{v,t} / A_t, the averaged dual iterate ν_t satisfies 0 ≤ \bar f(x_t) - \bar g(ν_t) ≤ B_{v,t} / A_t.
open scoped BigOperators ConvexAnalysis Gradient WeightSequenceNotation
universe u v
variable {E : Type u} {F : Type v}
[NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
[NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F]
theorem proposition_6_47_dualityGapBoundForAveragedDualIterate
(Q : Set E) (ψ : Q → ℝ) (xSeq : ℕ → Q) (a : ℕ → ℝ)
(A : E →L[ℝ] StrongDual ℝ F) (g : F → ℝ) (u : E → F) (U : Set F) (t : ℕ)
(Bvt : ℝ)
(ha_nonneg : ∀ k ∈ Finset.range (t + 1), 0 ≤ a k)
(hAt : 0 < A[a](t))
(hdualSlice_bddBelow :
BddBelow
(Set.range fun x : Q ↦
ψ x + A (x : E) ((Finset.range (t + 1)).centerMass a (fun k ↦ u (xSeq k : E)))))
(hu_mapsTo : Set.MapsTo u Q U)
(hg_convex : ConvexOn ℝ U g)
(hcertificate :
let νt := (Finset.range (t + 1)).centerMass a (fun k ↦ u (xSeq k : E))
let Φ : F → ℝ :=
fun ν ↦
sInf (Set.range fun x : Q ↦ ψ x + A (x : E) ν)
let ellt : ℝ :=
Φ νt -
(Finset.range (t + 1)).centerMass a (fun k ↦ g (u (xSeq k : E)))
let barf : Q → ℝ := fun x ↦ ψ x + g (u x)
barf (xSeq t) - ellt ≤ Bvt / A[a](t))
(hweak :
let νt := (Finset.range (t + 1)).centerMass a (fun k ↦ u (xSeq k : E))
let Φ : F → ℝ :=
fun ν ↦
sInf (Set.range fun x : Q ↦ ψ x + A (x : E) ν)
let barG : F → ℝ := fun ν ↦ Φ ν - g ν
let barf : Q → ℝ := fun x ↦ ψ x + g (u x)
barG νt ≤ barf (xSeq t)) :
let νt := (Finset.range (t + 1)).centerMass a (fun k ↦ u (xSeq k : E))
let Φ : F → ℝ :=
fun ν ↦
sInf (Set.range fun x : Q ↦ ψ x + A (x : E) ν)
let barG : F → ℝ := fun ν ↦ Φ ν - g ν
let barf : Q → ℝ := fun x ↦ ψ x + g (u x)
barf (xSeq t) - barG νt ∈ Set.Icc 0 (Bvt / A[a](t))
Definition 6.48
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.48: for a symmetric matrix C ∈ 𝕊^n, a continuous linear map A : E →L[ℝ] 𝕊^n, and μ > 0, the smoothed semidefinite objective is the Definition 6.47 smoothing evaluated at C + A(y). The textbook case E = ℝ^m is the intended specialization.
open RealSymmetricMatrixSpace
open scoped BigOperators RealSymmetricMatrixSpace
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {n : ℕ}
abbrev smoothedSemidefiniteObjective
(n : ℕ) (μ : {μ : ℝ // 0 < μ}) (C : 𝕊^n) (A : E →L[ℝ] 𝕊^n) : E → ℝ :=
fun y ↦ logSumExpMaxEigenvalueSmoothing μ (C + A y)Proposition 6.48
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.48: let ν_t = (Finset.range t).centerMass (fun k ↦ a (k + 1)) (fun k ↦ u (x_k)). If the Chapter 6 certificate \hat ℓ_t = linearEstimatingAccuracyCertificate Q a f gradF ψ xSeq t is a lower bound for the dual value \bar g(ν_t) = inf_x (\bar f(x) + ⟪ν_t, u(x)⟫) - Φ*(ν_t) and if the primal objective satisfies \bar f(x_t) + Φ(u(x_t)) - \hat ℓ_t ≤ C_{v,t} / linearEstimatingWeightSum a t, then the primal-dual gap at this averaged dual iterate lies in the canonical interval [0, C_{v,t} / linearEstimatingWeightSum a t].
open scoped BigOperators
universe u v
variable {E : Type u} {F : Type v}
[NormedAddCommGroup E] [InnerProductSpace ℝ E]
[NormedAddCommGroup F] [InnerProductSpace ℝ F]
open LinearEstimatingCertificate
theorem averaged_duality_gap_bound_of_lower_certificate
(Q : Set E) (f : E → ℝ) (gradF : E → E) (ψ : Q → ℝ)
(barF : E → EReal) (phi : F → EReal) (u : E → F)
(xSeq : ℕ → Q) (a : ℕ → ℝ) (t : ℕ) (Cv_t : ℝ)
(hhatℓt :
let νt := (Finset.range t).centerMass (fun k ↦ a (k + 1)) (fun k ↦ u (xSeq k : E))
let dualObj : F → EReal := fun ν ↦
sInf (Set.range fun x : E ↦ barF x + ((inner ℝ ν (u x) : ℝ) : EReal)) -
fenchelConjugate phi (innerₗ F ν)
(linearEstimatingAccuracyCertificate Q a f gradF ψ xSeq t : EReal) ≤ dualObj νt)
(hcertificate :
barF (xSeq t : E) + phi (u (xSeq t : E)) -
(linearEstimatingAccuracyCertificate Q a f gradF ψ xSeq t : EReal) ≤
((Cv_t / linearEstimatingWeightSum a t : ℝ) : EReal)) :
let νt := (Finset.range t).centerMass (fun k ↦ a (k + 1)) (fun k ↦ u (xSeq k : E))
let dualObj : F → EReal := fun ν ↦
sInf (Set.range fun x : E ↦ barF x + ((inner ℝ ν (u x) : ℝ) : EReal)) -
fenchelConjugate phi (innerₗ F ν)
barF (xSeq t : E) + phi (u (xSeq t : E)) - dualObj νt ∈
Set.Icc 0 (((Cv_t / linearEstimatingWeightSum a t : ℝ) : EReal))Definition 6.49
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.49: in finite dimensions, the operator norm of A is attained at some unit vector of the source space. For the source-faithful maximum formulation, the source space must be nontrivial so that the unit sphere is nonempty. This recovers the textbook maximum formulation.
open Metric
open scoped Matrix.Norms.L2Operator RealSymmetricMatrixSpace
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {n : ℕ}
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem operatorNorm_exists_unitSphere_spectralNorm_maximizer
[FiniteDimensional ℝ E] [Nontrivial E] (A : E →L[ℝ] 𝕊^n) :
∃ h ∈ sphere (0 : E) 1, ‖A‖ = ‖((A h : 𝕊^n) : Mat)‖
Proposition 6.49
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.49: if Ψ is σΨ-strongly convex on the feasible set Q and the feasible point v_t ∈ Q minimizes the affine perturbation x ↦ Ψ x + ⟪g, x⟫ over Q, then every feasible point satisfies the strengthened variational inequality Ψ x + ⟪g, x - v_t⟫ ≥ Ψ v_t + (σΨ / 2) * ‖x - v_t‖².
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem strongConvexOn_variational_inequality_of_affine_isMinOn
{Q : Set E} {Ψ : E → ℝ} {σΨ : ℝ} {g v_t x : E}
(hΨ_strong : StrongConvexOn Q σΨ Ψ)
(hv_t_mem : v_t ∈ Q)
(hv_t : IsMinOn (fun y ↦ Ψ y + inner ℝ g y) Q v_t)
(hx : x ∈ Q) :
Ψ x + inner ℝ g (x - v_t) ≥
Ψ v_t + (σΨ / 2) * ‖x - v_t‖ ^ (2 : ℕ)Definition 6.50
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.50: a composite bounded convex minimization problem consists of a nonempty bounded closed convex feasible set Q, a convex differentiable smooth term f on Q, and a proper closed convex extended-valued term Ψ whose effective domain is contained in Q. The ambient smooth pair (Q, f) is owned canonically by SetConstrainedMinimizationProblem; the nonemptiness of Q is derived from properness of Ψ together with dom Ψ ⊆ Q, and the ambient Chapter 6 feasible-set owner is recovered by the bridge toPrimalConvexMinimizationProblem. The regularizer uses the Chapter 3 owner ClosedConvexFunction.
universe u
open scoped WithTopConvexAnalysis
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
structure CompositeBoundedConvexMinimizationProblem (E : Type u) [NormedAddCommGroup E]
[NormedSpace ℝ E] extends SetConstrainedMinimizationProblem E where
/-- The feasible set is bounded. -/
feasibleSet_bounded : Bornology.IsBounded feasibleSet
/-- The feasible set is closed. -/
feasibleSet_closed : IsClosed feasibleSet
/-- The inherited smooth term is convex on `Q`. -/
objective_convex : ConvexOn ℝ feasibleSet objective
/-- The inherited smooth term is differentiable on `Q`. -/
objective_differentiable : DifferentiableOn ℝ objective feasibleSet
/-- The extended-valued nonsmooth term `Ψ : E → ℝ ∪ {+∞}`. -/
nonsmoothPart : E → WithTop ℝ
/-- The effective domain of `Ψ` is nonempty. -/
nonsmoothPart_proper : (dom nonsmoothPart).Nonempty
/-- The nonsmooth term is a closed convex function in the Chapter 3 owner sense. -/
nonsmoothPart_closedConvex : ClosedConvexFunction nonsmoothPart
/-- The effective domain of `Ψ` is contained in the feasible set `Q`. -/
nonsmoothPart_domain_subset_feasibleSet : dom nonsmoothPart ⊆ feasibleSetProposition 6.50
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 6.50: under the assumptions of Definition 6.67, the second-order optimality measure θ(x) is nonnegative at every finite feasible point x ∈ Q ∩ dom Ψ.
open scoped SecondOrderLocalModel.SecondOrderOptimalityMeasureNotation WithTopConvexAnalysis
open SecondOrderLocalModel
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem secondOrderOptimalityMeasure_nonneg
(Q : Set E) (f : E → ℝ) (Ψ : E → WithTop ℝ) (x : ↥(Q ∩ dom Ψ)) :
0 ≤ θ[Q, f, Ψ](x)
Definition 6.51
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.51: the zero-function specialization of fenchelPrimalExtension is the textbook indicator function formula.
universe u
variable {E : Type u}
-- Proof sketch: unfold `fenchelPrimalExtension`; membership in `Q` is exactly the branch
-- condition, so the zero-function specialization yields the displayed `0`/`+∞` case split.
theorem fenchelPrimalExtension_zero_apply (Q : Set E) (x : E) :
fenchelPrimalExtension Q (fun _ : E ↦ (0 : ℝ)) x =
if x ∈ Q then (0 : WithTop ℝ) else ⊤Definition 6.52
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.52: a conditional-gradient linear optimization oracle for the regularizer Ψ assigns to each linear functional s a feasible point v_Ψ(s) belonging to the canonical argmin set of the Chapter 6 oracle objective x ↦ s x + Ψ x on the feasible subtype Q.
open scoped ConstrainedArgmin
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {Q : Set E}
def IsLinearOptimizationOracle
(Ψ : Q → ℝ) (vPsi : StrongDual ℝ E → Q) : Prop :=
∀ s : StrongDual ℝ E,
vPsi s ∈ argmin[Set.univ] (linearOptimizationOracleObjective s Ψ)Definition 6.53
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.53: the accumulated weights A_t = ∑_{k=0}^t a_k attached to the sequence a_t.
open scoped BigOperators
def accumulatedWeights (a : ℕ → ℝ) : ℕ → ℝ :=
fun t ↦ ∑ k ∈ Finset.range (t + 1), a kDefinition 6.54
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.54: when the maximizing data certify the textbook maximum and displayed gradient at x₀, coercing the scalar source quantity V₀ to EReal agrees with the ambient chosen-dual gap owner linearizedCompositeGap, specialized to Function.extend Subtype.val Ψ 0.
open scoped BigOperators Gradient WeightSequenceNotation
universe u
variable {E : Type u}
[NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {Q : Set E}
theorem initialLinearizationGap_eq_linearizedCompositeGap
(Q : Set E) (f : E → ℝ) (Ψ : Q → ℝ) (x0 : Q)
[hData : InitialLinearizationGapMaximizer Q f Ψ x0] :
(initialLinearizationGap Q f Ψ x0 : EReal) =
initialLinearizationGapEReal Q f Ψ x0Definition 6.55
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.55: the restricted dual function of an ℝ ∪ {+∞}-valued function F with respect to (xBar, Q) with xBar ∈ Q ∩ dom F is the supremum over the finite feasible points x ∈ Q ∩ dom F of the affine gap s (xBar - x) + F(xBar) - F(x). The feasible-base-point hypothesis keeps the index set nonempty, so this WithTop ℝ supremum is mathematically faithful. In the textbook setting where Q is bounded closed convex and the maximum is attained, this supremum is the displayed maximum.
open scoped WithTopConvexAnalysis
universe u
variable {E : Type u} [TopologicalSpace E] [AddCommGroup E] [Module ℝ E]
def restrictedDualFunction
(Q : Set E) (F : E → WithTop ℝ) (xBar : ↥(Q ∩ dom F)) : StrongDual ℝ E → WithTop ℝ :=
fun s ↦
sSup <| Set.range fun x : ↥(Q ∩ dom F) ↦
((restrictedDualMaximand F ⟨xBar, xBar.2.2⟩ s ⟨x, x.2.2⟩ : ℝ) : WithTop ℝ)Definition 6.56
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.56: the scaled restricted dual function of F with respect to (τ, xBar, Q) is the restricted dual function of F over the contracted feasible set {(1 - τ) • xBar + τ • x | x ∈ Q}, with the same feasible base point xBar ∈ Q ∩ dom F. Equivalently, it is the supremum over contracted feasible points y ∈ dom F of the affine gap s (xBar - y) + F(xBar) - F(y). In textbook settings with compactness or attainment hypotheses, this supremum is the displayed maximum.
open scoped WithTopConvexAnalysis
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
variable [TopologicalSpace E]
def scaledRestrictedDualFunction
(Q : Set E) (F : E → WithTop ℝ) (xBar : ↥(Q ∩ dom F)) (τ : ℝ) :
StrongDual ℝ E → WithTop ℝDefinition 6.57
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.57 [Estimating functional sequence]: the Chapter 6 estimating sequence φ_t is the recursively defined family with φ_0(x) = a_0 * \tilde f(x) and φ_{t+1}(x) = φ_t(x) + a_{t+1} * (f(x_t) + ∇f(x_t)(x - x_t) + Ψ(x)). This is exactly the chapter owner ConditionalGradientContraction.estimatingFunctionalSequence, so the item is formalized as a direct recall of that canonical recursive definition.
universe u
recall ConditionalGradientContraction.estimatingFunctionalSequence
{E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
(a : ℕ → ℝ) (tildeF f : E → ℝ) (gradF : E → StrongDual ℝ E) (Ψ : E → ℝ)
(xSeq : ℕ → E) :
ℕ → E → ℝ
Definition 6.58
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.58 [Constant C_{v,t}]: for t ≥ 0, the Chapter 6 constant C_{v,t} is a₀ Δ(x₀) + (1 / (1 + v)) * (∑ k = 1 to t, a_k^(1 + v) / A_k^v) * G_v * D^(1 + v), with A_k = A[a](k). In the chapter API this is exactly the owner ConditionalGradientContraction.contractionErrorTerm, so the item is formalized as a direct recall of that canonical definition.
recall ConditionalGradientContraction.contractionErrorTerm
(Δ0 : ℝ) (a : ℕ → ℝ) (Gv D v : ℝ) (t : ℕ) :
ℝ
Definition 6.59
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.59: the total variation δ(x) of the linear model at a feasible point x ∈ Q is the supremum over feasible points y ∈ Q of ⟪∇ f(x), x - y⟫ + Ψ(x) - Ψ(y), recorded in EReal so the owner remains faithful even when the supremum is not bounded above in ℝ. In the finite-dimensional setting where this supremum is finite and attained, this is the textbook maximum.
open scoped Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def linearModelTotalVariation (Q : Set E) (f Ψ : E → ℝ) : Q → EReal :=
fun x ↦
sSup
((fun y : E ↦
((inner ℝ (∇ f x) ((x : E) - y) + Ψ x - Ψ y : ℝ) : EReal)) '' Q)Definition 6.60
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.60: the contracted total variation δ_τ(x) of the linear model at a feasible point x ∈ Q is the total variation from Definition 6.59, specialized to the contracted feasible set centered at x. It is therefore EReal-valued, remaining faithful even when the contracted supremum is not bounded above in ℝ.
open scoped Gradient TotalVariationNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def contractedLinearModelTotalVariation
(Q : Set E) (f Ψ : E → ℝ) (τ : ℝ) : Q → ERealDefinition 6.61
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.61: the accuracy certificate ℓ_t is the accumulated-weight-normalized infimum of the weighted affine local model over the feasible set Q. When the infimum is attained, this recovers the textbook minimum in equation (6.u655).
open ConditionalGradientContraction
open scoped BigOperators Gradient WeightSequenceNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (Q : Set E) (f : E → ℝ) (ψ : Q → ℝ) (xSeq : ℕ → Q) (a : ℕ → ℝ)
def localModelAccuracyCertificate (t : ℕ) : ℝ :=
sInf (Set.range (accuracyCertificateLocalModel Q f ψ xSeq a t)) /
A[a](t)
-- Proof sketch: unfold `localModelAccuracyCertificate`.
Definition 6.62
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.62: the accuracy certificate \hat ℓ_t is the accumulated-weight-normalized infimum of the estimating function φ_t over Q, with source-facing denominator \sum_{k < t} a_{k+1} encoded by linearEstimatingWeightSum a t = A[linearEstimatingWeights a](t). When the infimum is attained, this recovers the textbook minimum formula \hat ℓ_t = (1 / A_t) \min_{x ∈ Q} φ_t(x).
open ConditionalGradientContraction
open scoped BigOperators WeightSequenceNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
namespace LinearEstimatingCertificate
variable (Q : Set E) (a : ℕ → ℝ) (f : E → ℝ) (gradF : E → E) (ψ : Q → ℝ) (xSeq : ℕ → Q)
def linearEstimatingAccuracyCertificate (t : ℕ) : ℝ :=
sInf (Set.range (linearEstimatingFunction Q a f gradF ψ xSeq t)) /
linearEstimatingWeightSum a t
-- Proof sketch: unfold `linearEstimatingAccuracyCertificate`.
Definition 6.63
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.63: f has a max-representation with p-uniformly convex dual term when there is a nonempty closed convex dual set Q_d, a differentiable dual term g, and a maximizer selection u(x) such that f x = max_{u ∈ Q_d} ((A x) u - g u), the maximizer is unique, and g is uniformly convex on Q_d with power modulus r ↦ (1 / p) * σ_g * r^p for some p ≥ 2 and σ_g > 0.
open scoped Gradient
universe u v
variable {E : Type u} {E₂ : Type v}
[NormedAddCommGroup E] [NormedSpace ℝ E]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
class IsMaxRepresentationWithUniformlyConvexDualTerm
(f : E → ℝ) (A : E →L[ℝ] StrongDual ℝ E₂) (Qd : Set E₂)
(g : E₂ → ℝ) (u : E → E₂) (p σg : ℝ) : Prop where
/-- The dual feasible set `Q_d` is nonempty. -/
dualSet_nonempty : Qd.Nonempty
/-- The dual feasible set `Q_d` is closed. -/
dualSet_closed : IsClosed Qd
/-- The dual term `g` is differentiable on `Q_d`. -/
dualTerm_differentiableOn : DifferentiableOn ℝ g Qd
/-- The exponent in the dual uniform-convexity inequality satisfies `p ≥ 2`. -/
two_le_degree : 2 ≤ p
/-- The dual uniform-convexity parameter is positive. -/
dualParameter_pos : 0 < σg
/-- The dual term is uniformly convex on `Q_d` with the Chapter 4 power modulus owner. -/
dualTerm_uniformConvexOn :
UniformConvexOn Qd (uniformConvexPowerModulus σg p) g
/-- The chosen maximizer belongs to the canonical Chapter 6 argmax owner for the zero-smoothed
maximand `v ↦ (A x) v - g v`. -/
argmax_mem (x : E) :
u x ∈ smoothedPrimalObjectiveArgmax A Qd g 0 0 x
/-- The represented objective agrees with the canonical Chapter 6 supremum owner for the same
zero-smoothed maximand. -/
objective_eq (x : E) :
f x = smoothedPrimalObjective A Qd 0 g 0 0 xDefinition 6.64
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.64 recalls the chapter owner for the adjoint problem.
open scoped ConvexAnalysis
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
namespace StructuredObjectiveModel
recall adjointObjective (problem : StructuredObjectiveModel E₁ E₂) : problem.dualSet → ERealDefinition 6.65
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.65, owner form: the chapter's positive fixed-parameter strong-convexity class on Q.
universe u
open scoped StrongConvex
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {Q : Set E} {σΨ : ℝ} {Ψ : E → ℝ}
#check (Ψ ∈ 𝒮^0_σΨ(Q))Definition 6.66
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.66: the quantity \hat{B}_{v,t} is the initial term a₀ V₀ plus the weighted strong-convexity contribution (∑_{k=1}^t a_k^(1 + 2 v) / A_k^(2 v)) G_v^2 D^(2 v) / (2 σ_Ψ).
open scoped BigOperators WeightSequenceNotation
def stronglyConvexCompositeErrorBound
(V0 : ℝ) (a : ℕ → ℝ) (v Gv D sigmaPsi : ℝ) (t : ℕ) : ℝ :=
a 0 * V0 +
Finset.sum (Finset.Icc 1 t)
(fun k ↦ Real.rpow (a k) (1 + 2 * v) / Real.rpow (A[a](k)) (2 * v)) *
(Gv ^ (2 : ℕ) * Real.rpow D (2 * v) / (2 * sigmaPsi))
-- Proof sketch: unfold `stronglyConvexCompositeErrorBound`.Definition 6.67
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Definition 6.67: the second-order optimality measure θ(x) is the Chapter 6 owner SecondOrderLocalModel.secondOrderOptimalityMeasure, defined on the finite feasible domain Q ∩ dom Ψ and valued in EReal.
open scoped WithTopConvexAnalysis
universe u
recall SecondOrderLocalModel.secondOrderOptimalityMeasure
{E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
(Q : Set E) (f : E → ℝ) (Ψ : E → WithTop ℝ) :
↥(Q ∩ dom Ψ) → EReal
6.1 — Smoothing for an Explicit Model of an Objective Function
Example 6.1.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Example 6.1.1 [Chapter6_1.json:13]: the max-absolute affine objective admits the signed-simplex representation f(x) = sup_{u ∈ Δ(ι ⊕ ι)} ∑_j (u(inl j) - u(inr j)) (⟪a_j, x⟫ - b_j).
open scoped BigOperators
universe u v
variable {ι : Type v} [Fintype ι] [Nonempty ι]
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem piecewiseLinearObjective_eq_simplexSup
(a : ι → E) (b : ι → ℝ) (x : E) :
piecewiseLinearObjective a b x =
sSup
(Set.range fun u : StdSimplex ℝ (ι ⊕ ι) ↦
∑ j, (u.weights (Sum.inl j) - u.weights (Sum.inr j)) *
(inner ℝ (a j) x - b j))Remark 6.1.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Remark 6.1.1: if method (6.1.19) starts from x₀ = v₀, then the update relations place x_k and y_k in the convex hull of v₀, ..., v_k; if moreover ‖v_k - x^*‖² ≤ 2 D for all k ≥ 0, where D is the source scalar d(x^*), then the iterates v_k, x_k, and y_k form a bounded family.
universe u
variable {E : Type u} [SeminormedAddCommGroup E] [NormedSpace ℝ E]
theorem bounded_iterates_of_sqDist_bound
(D : ℝ) (x y v : ℕ → E) (xStar : E) (hx0 : x 0 = v 0)
(hxsucc : ∀ k : ℕ,
x (k + 1) =
(1 - (2 / ((k : ℝ) + 2))) • x k + (2 / ((k : ℝ) + 2)) • v (k + 1))
(hy : ∀ k : ℕ,
y k = (1 - (2 / ((k : ℝ) + 2))) • x k + (2 / ((k : ℝ) + 2)) • v k)
(hv : ∀ k : ℕ, ‖v k - xStar‖ ^ (2 : ℕ) ≤ 2 * D) :
Bornology.IsBounded (Set.range v ∪ Set.range x ∪ Set.range y)Text 6.1.1.Black.Box.Complexity.Barrier
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.1.1-Black-Box Complexity Barrier: the Chapter 3 black-box lower-bound theorem gives the canonical O(1 / ε^2) oracle-complexity barrier for span-based nonsmooth convex minimization under the resisting-oracle prefix-support-growth hypothesis, and the Nemirovski hard family f_k explains this barrier constructively through explicit simple witness problems.
recall exists_problem_with_nonsmooth_firstOrder_lower_bound
Text 6.1.1.Complexity.Insight
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.1.1-Complexity Insight: if the smoothed surrogate has gradient Lipschitz constant L_μ with L_μ ≤ C_L / μ, the smoothing parameter is chosen on the scale μ ≳ ε, and a fast gradient method reaches an ε-approximation within C_F * √(L_μ / ε) oracle calls, then the number of oracle calls is bounded by a constant multiple of ε⁻¹.
theorem fastGradient_oracleComplexity_le_const_div_epsilon_of_smoothApproximation
{ε μ Lμ CL CF cμ : ℝ} (hε : 0 < ε) (hcμ : 0 < cμ) (hCF : 0 ≤ CF)
(hμ : cμ * ε ≤ μ) (hLμ : Lμ ≤ CL / μ) {N : ℕ}
(hN : (N : ℝ) ≤ CF * Real.sqrt (Lμ / ε)) :
(N : ℝ) ≤ (CF * Real.sqrt (CL / cμ)) / εText 6.1.1.Conjugate.Closedness.and.Domain.Nonemptiness
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6 1 1 Conjugate Closedness and Domain Nonemptiness: the Fenchel dual has a closed and convex effective epigraph. The domain nonemptiness consequence is recorded separately below.
open scoped ConvexAnalysis WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem fenchelDual_effectiveEpigraph_closed_convex
(f : E → WithTop ℝ) :
IsClosed (effectiveEpigraph (f⋆)) ∧
Convex ℝ (effectiveEpigraph (f⋆))Text 6.1.1.Smoothing.Approximation.Error
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Setting the smoothing parameter to 0 recovers the unsmoothed Fenchel supremum model.
open Module
open LinearMap (BilinForm)
open LinearMap.BilinForm
open scoped ConvexAnalysis BInducedNorm
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E] [FiniteDimensional ℝ E]
@[simp] theorem fenchelSmoothApproximation_zero_apply
(B : BilinForm ℝ E) [Fact B.toQuadraticMap.PosDef]
(f : E → EReal) (x : E) :
fenchelSmoothApproximation B f 0 x =
sSup ((fun s : Dual ℝ E ↦ (s x : EReal) - fenchelConjugate f s) ''
dom (fenchelConjugate f))Text 6.1.1.Structure.Helps.Beyond.Black.Box
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
If the smoothed surrogate approximates the original objective within ε / 2 from below and never exceeds it, then an ε / 2-accurate point for the surrogate relative to an exact smoothed minimizer has original objective value at most ε above any chosen comparison point xStar.
universe u
variable {E : Type u}
theorem sub_le_epsilon_of_smoothedObjective_suboptimality
{f fμ : E → ℝ} {x xStar xμStar : E} {ε : ℝ}
(hxμStar : IsMinOn fμ Set.univ xμStar)
(happrox_lower : ∀ z : E, f z ≤ fμ z + ε / 2)
(happrox_upper : ∀ z : E, fμ z ≤ f z)
(hstructured_step : fμ x ≤ fμ xμStar + ε / 2) :
f x - f xStar ≤ εExample 6.1.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Example 6.1.2: a normalized prox-center of a prox-function on Q gives the quadratic lower bound d u ≥ (1 / 2) p(u - x₀)^2 at every feasible point u ∈ Q.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {p : Seminorm ℝ E} [Seminorm.IsNorm p]
variable {Q : Set E} {d : E → ℝ} {x₀ u : E}
recall prox_center_quadratic_lower_bound
(hd : NesterovIsProxFunction p Q d)
(hx₀ : NesterovIsProxCenter Q d x₀)
(hu : u ∈ Q) :
d u ≥ (1 / 2 : ℝ) * (p (u - x₀)) ^ (2 : ℕ)Remark 6.1.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Remark 6.1.2 uses the canonical antisymmetry owner directly.
recall le_antisymm {α : Type*} [PartialOrder α] {a b : α} : a ≤ b → b ≤ a → a = bText 6.1.2.Adjoint.Problem.Tractability.Caveat
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.1.2-Adjoint Problem Tractability Caveat: for a fixed u ∈ Q₂, any point of the fixed-u saddle slice x ↦ Ψ(x, u) over Q₁ evaluates the adjoint objective φ(u) via the chapter's EReal owner.
universe u v
open scoped ConstrainedArgmin
namespace StructuredObjectiveModel
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
theorem adjointObjective_eq_saddleFunction_of_isMinOn
{problem : StructuredObjectiveModel E₁ E₂}
{u : problem.dualSet} {x : problem.primalSet}
(hx : IsMinOn
(fun y : E₁ ↦
(problem.smoothPart y + problem.linearMap y u - problem.dualPenalty u : EReal))
problem.primalSet x) :
problem.adjointObjective u = (problem.saddleFunction x u : EReal)Text 6.1.2.Nonunique.Structured.Representation
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
The canonical double-dual inclusion is the structured linear term used in the Fenchel representation.
open scoped ConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
recall NormedSpace.inclusionInDoubleDualExample 6.1.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Example 6.1.3 is the Euclidean specialization of the chapter owner theorem explicitModelSmoothedProblem_hasFDerivWithinAt_and_gradient_lipschitzOn.
recall explicitModelSmoothedProblem_hasFDerivWithinAt_and_gradient_lipschitzOnText 6.1.4.1.Oracle.Complexity.Preserved.Under.Entropic.Smoothing
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
A pointwise constant-factor bound on iteration work accumulates to the same constant-factor bound on total arithmetic work.
universe u v
variable {Query : Type u} {Answer : Type v}
namespace GeneralIterativeScheme
variable (scheme : GeneralIterativeScheme Query Answer)
variable (oracleWork originalOracleWork smoothedOracleWork : Query → Answer → ℕ)
variable (methodWork originalMethodWork smoothedMethodWork : Set (Query × Answer) → ℕ)
theorem totalArithmeticWork_le_mul_of_iterationArithmeticWork_le_mul
(C N : ℕ)
(hiter :
∀ k,
scheme.iterationArithmeticWork smoothedOracleWork smoothedMethodWork k ≤
C * scheme.iterationArithmeticWork originalOracleWork originalMethodWork k) :
scheme.totalArithmeticWork smoothedOracleWork smoothedMethodWork N ≤
C * scheme.totalArithmeticWork originalOracleWork originalMethodWork NText 6.1.4.2.Average.Individual.Expense.Bound
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
The average individual expense objective x ↦ f(x) / P obtained by dividing the total expense by the positive population factor P.
universe u
variable {X : Type u}
open scoped BigOperators
abbrev averageIndividualExpense (P : ℝ) (f : X → ℝ) : X → ℝ :=
P⁻¹ • fText 6.1.4.2.Population.Interpretation
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
The positive population weights m_j used in the continuous location model.
open scoped BigOperators
universe u v
variable {ι : Type u}
abbrev ContinuousLocationWeights (ι : Type u) :=
ι → {m : ℝ // 0 < m}Text 6.1.5.1.Per.Iteration.Complexity.Decomposition
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.1.5.1 uses the Chapter 6 dual-oracle argmax owner for Step (b) and the Chapter 6 proximal minimization problem together with the Chapter 1 argmin owner for Step (c).
open scoped ConstrainedArgmin
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
variable
{Q₁ : Set E₁} (Q₂ : Set E₂) (hatφ : E₂ → ℝ)
(A : E₁ →L[ℝ] StrongDual ℝ E₂) (d₂ : E₂ → ℝ) (μ : ℝ)
(d₁ : Q₁ → ℝ) (yk : Q₁) (s : StrongDual ℝ E₁)
recall smoothedPrimalObjectiveArgmaxText 6.1.5.2.Stable.Log.Sum.Exp.Shift.Trick
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.1.5.2-Stable Log-Sum-Exp Shift Trick: if v is obtained by subtracting the maximal coordinate coordinateMaximum u from every component of u, then the scaled log-sum-exp potential satisfies the stable identity η μ u = coordinateMaximum u + η μ (centeredByCoordinateMaximum u).
open scoped Gradient
variable {m : ℕ} [NeZero m]
local notation "U" => EuclideanSpace ℝ (Fin m)
recall eta_eq_coordinateMaximum_add_eta_centered
-- Proof sketch: this item's main statement is exactly the Chapter 6 owner theorem already
-- recalled above, so the proof is the recalled stable max-shift identity itself.6.2 — An Excessive Gap Technique for Non-smooth Convex Minimization
Assumption 6.2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Assumption 6.2.1 uses the chapter's source-facing fixed-parameter strong-convexity owner.
universe u
open scoped StrongConvex
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable (Q₁ : Set E) (hatf : E → ℝ) (hatσ : ℝ)
#check (hatf ∈ 𝒮^0_hatσ(Q₁))Corollary 6.2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Corollary 6.2.1: for a fixed index k, if λ₁,k λ₂,k = α_k α_{k-1} and τ_k = 1 - α_{k+1} / α_{k-1} with α_{k-1}, α_{k+1} > 0, then the step-size condition τ_k^2 / (1 - τ_k) ≤ λ_{1,k} λ_{2,k} is equivalent to (α_{k+1} - α_{k-1})^2 ≤ α_{k+1} α_k α_{k-1}^2.
universe u
variable {𝕜 : Type u} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜]
-- Proof sketch: rewrite `1 - τ k` as `α ((k : ℤ) + 1) / α ((k : ℤ) - 1)` and clear this
-- positive denominator to reduce to Theorem 6.5.
theorem step_size_condition_iff_alpha_three_term_inequality
(α : Set.Ici (-1 : ℤ) → 𝕜) (lambda₁ lambda₂ τ : ℕ → 𝕜) (k : ℕ)
(hα_pred_pos : 0 < α (switching_parameters_pred_index k))
(hα_succ_pos : 0 < α (switching_parameters_succ_index k))
(hprod : lambda₁ k * lambda₂ k =
α (switching_parameters_curr_index k) * α (switching_parameters_pred_index k))
(hτ : τ k = 1 - α (switching_parameters_succ_index k) / α (switching_parameters_pred_index k)) :
τ k ^ (2 : ℕ) / (1 - τ k) ≤ lambda₁ k * lambda₂ k ↔
(α (switching_parameters_succ_index k) - α (switching_parameters_pred_index k)) ^ (2 : ℕ) ≤
α (switching_parameters_succ_index k) * α (switching_parameters_curr_index k) *
(α (switching_parameters_pred_index k)) ^ (2 : ℕ)Lemma 6.2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.1 (1): the primal error at an excessive-gap pair is nonnegative.
universe u v
variable {X : Type u} {U : Type v}
theorem excessive_gap_condition_primal_error_nonneg {Q₁ : Set X} {f : X → ℝ} {xBar : X}
{fStar : ℝ} (h_primal : IsLeast (f '' Q₁) fStar) (hxBar : xBar ∈ Q₁) :
0 ≤ f xBar - fStarTheorem 6.2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.2.1 is exactly the Chapter 6 one-step excessive-gap preservation theorem already owned by satisfiesExcessiveGapCondition_preserved_under_update.
recall satisfiesExcessiveGapCondition_preserved_under_updateText 6.2.1.Fixed.Horizon.Drawback.and.Excessive.Gap.Motivation
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.2.1-Fixed-Horizon Drawback and Excessive-Gap Motivation: once a feasible pair (xBar, uBar) satisfies the chapter's excessive-gap certificate and the current smoothing budget obeys μ₁ D₁ + μ₂ D₂ ≤ ε, the raw duality gap is already ε-small. This source-facing stopping criterion uses only the two smoothing inequalities at the current pair (xBar, uBar), not global smoothing bounds on all of Q₁ and Q₂, so one can stop as soon as the current certificate budget falls below ε instead of fixing a horizon in advance.
universe u v
variable {X : Type u} {U : Type v}
-- Proof sketch: the excessive-gap certificate is exactly `fμ₂ xBar ≤ φμ₁ uBar`. Combine this
-- with the local smoothing bounds at `xBar` and `uBar` to obtain
-- `f xBar - φ uBar ≤ μ₁ D₁ + μ₂ D₂`, then use the stopping inequality
-- `μ₁ D₁ + μ₂ D₂ ≤ ε`.
theorem raw_duality_gap_le_epsilon_of_satisfiesExcessiveGapCondition
{Q₁ : Set X} {Q₂ : Set U}
{f fμ₂ : X → ℝ} {φ φμ₁ : U → ℝ}
{xBar : Q₁} {uBar : Q₂}
{D₁ D₂ μ₁ μ₂ ε : ℝ}
(hfμ₂_lower : f xBar - μ₂ * D₂ ≤ fμ₂ xBar)
(hφμ₁_upper : φμ₁ uBar ≤ φ uBar + μ₁ * D₁)
(hexcessive_gap : satisfiesExcessiveGapCondition Q₁ Q₂ fμ₂ φμ₁ xBar uBar)
(hbudget : μ₁ * D₁ + μ₂ * D₂ ≤ ε) :
f xBar - φ uBar ≤ εText 6.2.1.Implementability.Assumptions.for.Primal.Dual.Structure
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.2.1-Implementability Assumptions for Primal-Dual Structure: an implementable primal-dual representation provides closed-form solution operators for the primal proximal subproblem on Q₁ and, for each positive smoothing parameter μ > 0, the regularized dual oracle subproblem on Q₂, and the functions \hat f and \hat φ have gradients that are Lipschitz continuous on Q₁ and Q₂ with constants L₁(\hat f) and L₂(\hat φ).
open scoped ConstrainedArgmin Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
structure ImplementablePrimalDualStructure (E₁ : Type u) (E₂ : Type v)
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
extends StructuredObjectiveModel E₁ E₂ where
/-- The primal prox term `d₁`. -/
primalProxFunction : E₁ → ℝ
/-- The dual prox term `d₂`. -/
dualProxFunction : E₂ → ℝ
/-- The closed-form primal proximal solver `s ↦ x(s)`. -/
primalProxSolver : StrongDual ℝ E₁ → primalSet
/-- The primal proximal solver belongs to the canonical argmin set of the proximal subproblem
on the inherited primal set. -/
primalProxSolver_spec :
∀ s : StrongDual ℝ E₁,
primalProxSolver s ∈
argmin[Set.univ]
(proximalMinimizationProblem primalSet (fun x : primalSet ↦ primalProxFunction x) s)
/-- The closed-form dual oracle `u_μ(x)` returns a feasible maximizer of the regularized dual
subproblem on the inherited dual set for each positive smoothing parameter `μ`. -/
dualOracleSolver : primalSet → {μ : ℝ // 0 < μ} → dualSet
/-- The dual oracle belongs to the canonical argmax set of the regularized dual maximand on
the inherited dual set. -/
dualOracleSolver_spec :
∀ (x : primalSet) (μ : {μ : ℝ // 0 < μ}),
(dualOracleSolver x μ : E₂) ∈
smoothedPrimalObjectiveArgmax linearMap dualSet dualPenalty dualProxFunction μ x
/-- The Lipschitz constant `L₁(\hat f)` for the gradient of `\hat f` on `Q₁`. -/
smoothPartGradientLipschitzConstant : NNReal
/-- The gradient of `\hat f` exists on `Q₁` as the canonical within-gradient. -/
smoothPart_hasGradientWithinAt :
∀ ⦃x : E₁⦄, x ∈ primalSet →
HasGradientWithinAt smoothPart (gradientWithin smoothPart primalSet x) primalSet x
/-- The gradient of `\hat f` is Lipschitz on `Q₁` with constant `L₁(\hat f)`. -/
smoothPart_gradient_lipschitz :
LipschitzOnWith smoothPartGradientLipschitzConstant
(gradientWithin smoothPart primalSet) primalSet
/-- The Lipschitz constant `L₂(\hat φ)` for the gradient of `\hat φ` on `Q₂`. -/
dualPenaltyGradientLipschitzConstant : NNReal
/-- The gradient of `\hat φ` exists on `Q₂` as the canonical within-gradient. -/
dualPenalty_hasGradientWithinAt :
∀ ⦃u : E₂⦄, u ∈ dualSet →
HasGradientWithinAt dualPenalty (gradientWithin dualPenalty dualSet u) dualSet u
/-- The gradient of `\hat φ` is Lipschitz on `Q₂` with constant `L₂(\hat φ)`. -/
dualPenalty_gradient_lipschitz :
LipschitzOnWith dualPenaltyGradientLipschitzConstant
(gradientWithin dualPenalty dualSet) dualSetLemma 6.2.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.2: if u lies in the canonical argmax set of the regularized dual representation of the smoothed primal objective, then the affine linearization at xhat written with the explicit vector ∇ \hat f(xhat) + A^* u is bounded above by the selected dual value.
open scoped Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
-- Proof sketch: apply `smoothedPrimalObjective_linearization_le_selected_dual_value`
-- at the selected dual point `u` and rewrite the affine pairing term
-- using the transpose identity
-- `⟪(InnerProductSpace.toDual ℝ E₁).symm (A.flip u), v⟫ = A v u`.
theorem smoothedPrimalObjective_linearization_le_selected_dual_value_of_explicit_gradient
(A : E₁ →L[ℝ] StrongDual ℝ E₂) {Q₁ : Set E₁} {Q₂ : Set E₂}
{hatf : E₁ → ℝ} {hatφ d₂ : E₂ → ℝ} {μ₂ : ℝ} (hhatf_conv : ConvexOn ℝ Q₁ hatf)
(hμ₂ : 0 ≤ μ₂) {u : E₂} {x xhat : E₁} (hx : x ∈ Q₁) (hxhat : xhat ∈ Q₁)
(hu : u ∈ smoothedPrimalObjectiveArgmax A Q₂ hatφ d₂ μ₂ xhat)
(hhatf_grad :
HasGradientWithinAt hatf (gradientWithin hatf Q₁ xhat) Q₁ xhat)
(hd₂_nonneg : 0 ≤ d₂ u) :
smoothedPrimalObjective A Q₂ hatf hatφ d₂ μ₂ xhat +
inner ℝ
(gradientWithin hatf Q₁ xhat +
(InnerProductSpace.toDual ℝ E₁).symm (A.flip u))
(x - xhat) ≤
hatf x + A x u - hatφ uTheorem 6.2.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.2.2: if the Algorithm 6.3 iterates start from an excessive-gap pair and each even and odd update satisfy the canonical propagation hypotheses of Theorem_6_6, then every iterate pair (x̄_k, ū_k) of the feasible Algorithm 6.3 recursion satisfies the Chapter 6 excessive-gap certificate; if the smoothing budget also obeys the chapter rate estimate, then the raw duality gap satisfies the same rate bound.
open scoped ConstrainedArgmin
universe u v
variable
{X : Type u} {U : Type v}
[NormedAddCommGroup X] [NormedSpace ℝ X]
[NormedAddCommGroup U] [InnerProductSpace ℝ U] [CompleteSpace U]
{Q₁ : Set X} {Q₂ : Set U}
(hQ₁ : Convex ℝ Q₁) (hQ₂ : Convex ℝ Q₂)
{A₀ : X →L[ℝ] StrongDual ℝ U}
{hatf : X → ℝ} {hatφ : U → ℝ} {d₁ : X → ℝ} {d₂ : U → ℝ}
(xμ : ℝ → U → X)
(hxμ :
∀ μ : ℝ, ∀ u : U,
xμ μ u ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A₀ hatf d₁ μ u))
(uμ : ℝ → X → U)
(huμ :
∀ μ : ℝ, ∀ x : X, x ∈ Q₁ →
uμ μ x ∈ smoothedPrimalObjectiveArgmax A₀ Q₂ hatφ d₂ μ x)
(x₀ : Q₂ → Q₁) (V : Q₂ → Q₂)
{fμ₂ : ℝ → X → ℝ} {φμ₁ : ℝ → U → ℝ}
{fμ₂_zero : ℝ → Q₁ → ℝ} {φ_zero : Q₂ → ℝ}
{initialPrimalSmoothing initialDualSmoothing : ℝ}
(initialState : Q₁ × Q₂)
local notation "μ₁" =>
algorithm_6_3_primal_smoothing initialPrimalSmoothing
local notation "μ₂" =>
algorithm_6_3_dual_smoothing initialDualSmoothing
local notation "x̄" =>
alternatingExcessiveGapPrimalIterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
x₀
V
initialPrimalSmoothing
initialDualSmoothing
initialState
local notation "ū" =>
alternatingExcessiveGapDualIterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
x₀
V
initialPrimalSmoothing
initialDualSmoothing
initialState
local notation "x̄ₑ" =>
fun k ↦
algorithm_6_3_even_primal_iterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
initialPrimalSmoothing
initialDualSmoothing
(x̄ k, ū k)
k
local notation "ūₑ" =>
fun k ↦
algorithm_6_3_even_dual_iterate
hQ₁
hQ₂
xμ
hxμ
uμ
huμ
initialPrimalSmoothing
initialDualSmoothing
(x̄ k, ū k)
k
local notation "x̄ₒ" =>
fun k ↦
algorithm_6_3_odd_primal_iterate
hQ₁
hQ₂
uμ
huμ
x₀
initialDualSmoothing
(x̄ k, ū k)
k
local notation "ūₒ" =>
fun k ↦
algorithm_6_3_odd_dual_iterate
hQ₂
uμ
huμ
V
initialDualSmoothing
(x̄ k, ū k)
k
theorem algorithm_6_3_excessive_gap_and_duality_gap_rate
{A : X →L[ℝ] U}
{f : X → ℝ} {φ : U → ℝ} {D₁ D₂ : ℝ}
(hzero :
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ 0))
(φμ₁ (μ₁ 0))
(x̄ 0)
(ū 0))
(heven_step :
∀ k : ℕ, Even k →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ k))
(φμ₁ (μ₁ k))
(x̄ k)
(ū k) →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ (k + 1)))
(φμ₁ (μ₁ (k + 1)))
(x̄ₑ k)
(ūₑ k))
(hodd_source :
∀ k : ℕ, Odd k →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ k))
(φμ₁ (μ₁ k))
(x̄ k)
(ū k) →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ k))
φ_zero
(x̄ k)
(ū k))
(hodd_step :
∀ k : ℕ, Odd k →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ k))
φ_zero
(x̄ k)
(ū k) →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ (k + 1)))
φ_zero
(x̄ₒ k)
(ūₒ k))
(hodd_target :
∀ k : ℕ, Odd k →
satisfiesExcessiveGapConditionWithMu1Zero
(fμ₂_zero (μ₂ (k + 1)))
φ_zero
(x̄ₒ k)
(ūₒ k) →
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ (k + 1)))
(φμ₁ (μ₁ (k + 1)))
(x̄ₒ k)
(ūₒ k))
(hfμ₂_lower :
∀ k : ℕ,
f (x̄ k) - μ₂ k * D₂ ≤ fμ₂ (μ₂ k) (x̄ k))
(hφμ₁_upper :
∀ k : ℕ,
φμ₁ (μ₁ k) (ū k) ≤ φ (ū k) + μ₁ k * D₁)
(hbudget :
∀ k : ℕ,
μ₁ k * D₁ + μ₂ k * D₂ ≤
(4 * ‖A‖ * Real.sqrt (D₁ * D₂)) / ((k : ℝ) + 1)) :
∀ k : ℕ,
satisfiesExcessiveGapCondition
Q₁
Q₂
(fμ₂ (μ₂ k))
(φμ₁ (μ₁ k))
(x̄ k)
(ū k) ∧
f (x̄ k) - φ (ū k) ≤
(4 * ‖A‖ * Real.sqrt (D₁ * D₂)) / ((k : ℝ) + 1)
Lemma 6.2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.3: let x₀ ∈ Q₁, let \bar x minimize the linearized prox model x ↦ ⟪∇ f_{μ₂}(x₀), x - x₀⟫ + L₁(f_{μ₂}) d₁(x), and let \bar u := u_{μ₂}(x₀). This direct owner theorem records the hidden Chapter 6 ingredients explicitly: L₁(f_{μ₂}) is realized by the displayed prox upper model at x₀, d₁ is nonnegative on Q₁, and \bar u enters only through the bridge inequality coming from the selected μ₁-primal point. Under these source-faithful hypotheses, every μ₁ ≥ L₁(f_{μ₂}) yields the excessive-gap inequality f_{μ₂}(\bar x) ≤ φ_{μ₁}(\bar u).
open scoped ConstrainedArgmin Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
-- Semantic recall: `upper_model_of_hasGradientWithinAt_lipschitzOn` in `Theorem_6_4` is the
-- nearby Chapter 6 owner for the missing smoothness premise, while later Chapter 6 files consume
-- this item through a direct ambient excessive-gap theorem rather than through a bundled
-- `ImplementablePrimalDualStructure`.
theorem smoothed_pair_excessive_gap_of_linearized_prox_minimizers
{Q₁ : Set E₁} {fμ₂ : E₁ → ℝ} {φμ₁ : E₂ → ℝ} {d₁ : E₁ → ℝ}
{x₀ xBar xμ₁uBar : Q₁} {uBar : E₂} {μ₁ Lfμ₂ : ℝ}
(hconv : ConvexOn ℝ Q₁ fμ₂)
(hfμ₂_grad :
HasGradientWithinAt
fμ₂
(gradientWithin fμ₂ Q₁ x₀)
Q₁
x₀)
(hfμ₂_upper :
∀ ⦃x : E₁⦄, x ∈ Q₁ →
fμ₂ x ≤
fμ₂ x₀ +
inner ℝ (gradientWithin fμ₂ Q₁ x₀) (x - x₀) +
Lfμ₂ * d₁ x)
(hbar_min :
IsMinOn
(fun x ↦
inner ℝ (gradientWithin fμ₂ Q₁ x₀) (x - x₀) +
Lfμ₂ * d₁ x)
Q₁
xBar)
(hd₁_nonneg :
∀ ⦃x : E₁⦄, x ∈ Q₁ → 0 ≤ d₁ x)
(horacle_bridge :
fμ₂ x₀ +
inner ℝ (gradientWithin fμ₂ Q₁ x₀) ((xμ₁uBar : E₁) - x₀) +
μ₁ * d₁ xμ₁uBar ≤
φμ₁ uBar)
(hμ₁ : Lfμ₂ ≤ μ₁) :
fμ₂ xBar ≤ φμ₁ uBarTheorem 6.2.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.2.3: in the chapter's implementable primal-dual setting, let (\bar x, \bar u) satisfy the excessive-gap condition with μ₁ = 0, let x₀ select the zero-smoothing primal minimizer at every feasible dual point, and let V be the chapter adjoint-gradient update map for the actual zero-smoothed dual objective φ, whose gradient exists on the feasible dual set and is Lipschitz there with constant L₂(φ). Assume in addition that the chosen selector x₀ is the Chapter 6 zero-smoothed minimizer selection identified by the dual-gradient formula ∇φ(u) = A x₀(u) - ∇ \hat φ(u) on the feasible dual set, and that the chapter dual prox function is 1-strongly convex on the feasible dual set. Set \hat u = (1 - τ) \bar u + τ u_{μ₂}(\bar x), \bar x_+ = (1 - τ) \bar x + τ x₀(\hat u), and \bar u_+ = V(\hat u). If τ ∈ (0, 1) satisfies τ^2 / (1 - τ) ≤ μ₂ / L₂(φ), then the updated pair (\bar x_+, \bar u_+) again satisfies the excessive-gap condition with μ₁ = 0 and smoothing parameter μ₂⁺ = (1 - τ) μ₂.
open scoped ConstrainedArgmin
universe u v
namespace StronglyConvexDualUpdate
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
theorem excessive_gap_condition_preserved
(problem : ImplementablePrimalDualStructure E₁ E₂)
(hdualProx : StrongConvexOn problem.dualSet 1 problem.dualProxFunction)
(x₀ : problem.dualSet → problem.primalSet) (V : problem.dualSet → problem.dualSet)
(Lphi : NNReal)
{xBar : problem.primalSet} {uBar : problem.dualSet} {μ₂ : {μ : ℝ // 0 < μ}} {τ : ℝ}
(hgap :
satisfiesExcessiveGapConditionWithMu1Zero
(fun x : problem.primalSet ↦
smoothedPrimalObjective problem.linearMap problem.dualSet
problem.smoothPart problem.dualPenalty problem.dualProxFunction (μ₂ : ℝ) x)
(fun u : problem.dualSet ↦
extendedRealRealPart
(smoothedDualObjective problem.linearMap problem.primalSet
problem.smoothPart problem.dualPenalty (fun _ : E₁ ↦ 0) 0) u)
xBar
uBar)
(hx₀ :
∀ u : problem.dualSet,
(x₀ u : E₁) ∈
argmin[problem.primalSet]
(smoothedDualObjectiveMinimand problem.linearMap problem.smoothPart
(fun _ : E₁ ↦ 0) 0 u))
(hphi_hasGradientWithinAt :
∀ ⦃u : E₂⦄, u ∈ problem.dualSet →
HasGradientWithinAt
(fun u : E₂ ↦
extendedRealRealPart
(smoothedDualObjective problem.linearMap problem.primalSet
problem.smoothPart problem.dualPenalty (fun _ : E₁ ↦ 0) 0) u)
(gradient
(fun u : E₂ ↦
extendedRealRealPart
(smoothedDualObjective problem.linearMap problem.primalSet
problem.smoothPart problem.dualPenalty (fun _ : E₁ ↦ 0) 0) u)
u)
problem.dualSet
u)
(hphi_lipschitz :
LipschitzOnWith Lphi
(gradient
(fun u : E₂ ↦
extendedRealRealPart
(smoothedDualObjective problem.linearMap problem.primalSet
problem.smoothPart problem.dualPenalty (fun _ : E₁ ↦ 0) 0) u))
problem.dualSet)
(hgradient_eq_selectedSlope :
∀ u : problem.dualSet,
gradient
(fun u : E₂ ↦
extendedRealRealPart
(smoothedDualObjective problem.linearMap problem.primalSet
problem.smoothPart problem.dualPenalty (fun _ : E₁ ↦ 0) 0) u)
(u : E₂) =
(InnerProductSpace.toDual ℝ E₂).symm (problem.linearMap (x₀ u)) -
gradientWithin problem.dualPenalty problem.dualSet (u : E₂))
(hτ : 0 < τ) (hτ_lt : τ < 1)
(hstep :
τ ^ (2 : ℕ) / (1 - τ) ≤
(μ₂ : ℝ) / (Lphi : ℝ))
(hV :
IsAdjointGradientMappingOn
problem.dualSet
(fun u : E₂ ↦
extendedRealRealPart
(smoothedDualObjective problem.linearMap problem.primalSet
problem.smoothPart problem.dualPenalty (fun _ : E₁ ↦ 0) 0) u)
(Lphi : ℝ)
V) :
satisfiesExcessiveGapConditionWithMu1Zero
(fun x : problem.primalSet ↦
smoothedPrimalObjective problem.linearMap problem.dualSet
problem.smoothPart problem.dualPenalty problem.dualProxFunction
(reducedDualSmoothing μ₂ τ) x)
(fun u : problem.dualSet ↦
extendedRealRealPart
(smoothedDualObjective problem.linearMap problem.primalSet
problem.smoothPart problem.dualPenalty (fun _ : E₁ ↦ 0) 0) u)
(updatedPrimalPoint problem.primalSet_convex problem.dualSet_convex x₀
(fun x : problem.primalSet ↦ problem.dualOracleSolver x μ₂) xBar uBar τ
(tau_mem_Icc hτ hτ_lt))
(updatedDualPoint problem.dualSet_convex
(fun x : problem.primalSet ↦ problem.dualOracleSolver x μ₂) V xBar uBar τ
(tau_mem_Icc hτ hτ_lt))
Lemma 6.2.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.4: if the switching-parameter sequence attached to α_k satisfies the contraction rule parameters_{k+1} = (1 - τ_k) parameters_k, then for every k ≥ 0, α_{k+1} = (1 - τ_k) α_{k-1}.
theorem alpha_succ_eq_one_sub_tau_mul_pred_of_alternating_scalar_updates
(α : Set.Ici (-1 : ℤ) → ℝ) (τ : ℕ → ℝ)
(hparameters :
∀ k : ℕ, switching_parameters α (k + 1) = (1 - τ k) • switching_parameters α k)
(k : ℕ) :
α (switching_parameters_succ_index k) =
(1 - τ k) * α (switching_parameters_pred_index k)Theorem 6.2.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 6.2.4: assume that problem (6.2.1) satisfies Assumption 6.2.1, and let {(\bar x_k, \bar u_k)}_{k \ge 0} be the sequence generated by scheme (6.2.37). If at each stage k the scheme yields the smoothed inequality f_{μ₂,k}(\bar x_k) ≤ φ(\bar u_k) with μ₂,k = 4 L₂(φ) / ((k + 1) (k + 2)), and if the smoothing family satisfies f(x) - μ₂ D₂ ≤ f_{μ₂}(x) for every μ₂ and x, then f(\bar x_k) - φ(\bar u_k) ≤ 4 L₂(φ) D₂ / ((k + 1) (k + 2)) for every integer k ≥ 0.
universe u v
variable {X : Type u} {U : Type v}
{f : X → ℝ} {φ : U → ℝ}
{fμ₂ : ℝ → X → ℝ}
{barx : ℕ → X} {baru : ℕ → U}
{L2phi D2 : ℝ}
theorem scheme_6_2_37_primal_dual_gap_le_rate
(happrox : ∀ μ₂ x, f x - μ₂ * D2 ≤ fμ₂ μ₂ x)
(hscheme :
∀ k : ℕ,
fμ₂ ((4 * L2phi) / (((k : ℝ) + 1) * ((k : ℝ) + 2))) (barx k) ≤ φ (baru k))
(k : ℕ) :
f (barx k) - φ (baru k) ≤
(4 * L2phi * D2) / (((k : ℝ) + 1) * ((k : ℝ) + 2))Lemma 6.2.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.5 (1): if Q₁ is nonempty and closed, if \hat f ∈ 𝒮^0_σ(Q₁), if x₀ selects the pointwise zero-smoothing primal argmin, and if \hat φ is convex, differentiable, and has Lipschitz-continuous gradient, then the zero-smoothing dual objective is concave on E₂.
open scoped ConstrainedArgmin ConvexAnalysis Gradient StrongConvex
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
theorem dualObjective_zeroSmoothing_properties
(A : E₁ →L[ℝ] StrongDual ℝ E₂)
{Q₁ : Set E₁} {hatf : E₁ → ℝ} {hatφ : E₂ → ℝ}
{x₀ : E₂ → E₁} {σ : ℝ} {Lhatφ : NNReal}
(hQ₁_nonempty : Q₁.Nonempty)
(hQ₁_closed : IsClosed Q₁)
(hhatf : hatf ∈ 𝒮^0_σ(Q₁))
(hhatφ_convex : ConvexOn ℝ Set.univ hatφ)
(hhatφ_diff : Differentiable ℝ hatφ)
(hhatφ_lipschitz : LipschitzWith Lhatφ (∇ hatφ))
(hx₀ : ∀ u : E₂, x₀ u ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf 0 0 u)) :
ConcaveOn ℝ Set.univ
(extendedRealRealPart (smoothedDualObjective A Q₁ hatf hatφ 0 0))Lemma 6.2.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.6: for u, \hat u ∈ Q₂, if xHat solves the fixed-\hat u zero-smoothing primal slice, then the affine linearization of the dual objective at \hat u dominates -\hat φ(u) + A xHat u + \hat f(xHat).
open scoped ConstrainedArgmin Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
theorem dualObjective_linearization_lower_bound
(A : E₁ →L[ℝ] StrongDual ℝ E₂) {Q₁ : Set E₁} {Q₂ : Set E₂}
{hatf : E₁ → ℝ} {hatφ : E₂ → ℝ}
(hhatφ_convex : ConvexOn ℝ Q₂ hatφ)
{u uHat : E₂} {xHat : E₁}
(hxHat : xHat ∈ argmin[Q₁] (smoothedDualObjectiveMinimand A hatf 0 0 uHat))
(hu : u ∈ Q₂) (huHat : uHat ∈ Q₂)
(hhatφ_grad : HasGradientAt hatφ (∇ hatφ uHat) uHat)
(hdual_grad :
HasGradientAt
(extendedRealRealPart (smoothedDualObjective A Q₁ hatf hatφ 0 0))
(-∇ hatφ uHat + (InnerProductSpace.toDual ℝ E₂).symm (A xHat)) uHat) :
extendedRealRealPart (smoothedDualObjective A Q₁ hatf hatφ 0 0) uHat +
inner ℝ (∇ (extendedRealRealPart (smoothedDualObjective A Q₁ hatf hatφ 0 0)) uHat)
(u - uHat) ≥
-hatφ u + A xHat u + hatf xHatLemma 6.2.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.7: if fμ₂ satisfies the local lower estimate f xBar - μ₂ D₂ ≤ fμ₂ xBar, if (xBar, uBar) satisfies the Chapter 6 excessive-gap certificate fμ₂ xBar ≤ φ uBar, and if the raw weak-duality inequality φ uBar ≤ f xBar holds at the same pair, then the primal-dual gap at (xBar, uBar) lies in the interval [0, μ₂ D₂].
universe u v
variable {X : Type u} {U : Type v}
-- Proof sketch: the excessive-gap certificate is exactly `fμ₂ xBar ≤ φ uBar`, so
-- `raw_duality_gap_le_excessive_gap_budget` with `μ₁ = 0` yields the upper bound
-- `f xBar - φ uBar ≤ μ₂ * D₂`. The separate weak-duality hypothesis `φ uBar ≤ f xBar` gives the
-- lower bound `0 ≤ f xBar - φ uBar`.
theorem primal_dual_gap_bound_of_smoothed_lower_estimate
{Q₁ : Set X} {Q₂ : Set U}
{f fμ₂ : X → ℝ} {φ : U → ℝ}
{μ₂ D₂ : ℝ} {xBar : Q₁} {uBar : Q₂}
(hfμ₂_lower : f xBar - μ₂ * D₂ ≤ fμ₂ xBar)
(hexcessive_gap : satisfiesExcessiveGapCondition Q₁ Q₂ fμ₂ φ xBar uBar)
(hweak : φ uBar ≤ f xBar) :
f xBar - φ uBar ∈ Set.Icc 0 (μ₂ * D₂)Lemma 6.2.8
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Lemma 6.2.8: if ∇ φ is L₂(φ)-Lipschitz on the convex set Q₂, if V(u₀) maximizes the quadratic model of φ at u₀, and if the identities and penalty-corrected upper model from the preceding setup hold at u₀, then the excessive-gap inequality (6.2.31) is valid for μ₂ = L₂(φ), \bar x = x₀(u₀), and \bar u = V(u₀), namely f_{L₂(φ)}(x₀(u₀)) ≤ φ(V(u₀)).
open scoped Gradient
universe u v
variable {E₁ : Type u} {E₂ : Type v}
[NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
[NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
-- LeanSearch recall for the smooth lower-model step only surfaced the generic within-set
-- gradient API, so this item keeps the direct `HasGradientWithinAt` / `gradientWithin` route.
theorem smoothed_primal_objective_at_x0_le_dual_value_at_V
(A : E₁ →L[ℝ] StrongDual ℝ E₂) {Q₂ : Set E₂}
{φ hatφ : E₂ → ℝ} {hatf : E₁ → ℝ} {d₂ : E₂ → ℝ}
{x₀ : E₂ → E₁} {V : E₂ → E₂} {u₀ : E₂} {L₂φ : NNReal}
(hQ₂_convex : Convex ℝ Q₂)
(hu₀ : u₀ ∈ Q₂)
(hφ_hasGradientWithinAt :
∀ ⦃u : E₂⦄, u ∈ Q₂ →
HasGradientWithinAt φ (gradientWithin φ Q₂ u) Q₂ u)
(hφ_gradient_lipschitz :
LipschitzOnWith L₂φ (fun u ↦ gradientWithin φ Q₂ u) Q₂)
(hV_max :
IsMaxOn
(fun u ↦
φ u₀ +
inner ℝ (gradientWithin φ Q₂ u₀) (u - u₀) -
((L₂φ : ℝ) / 2) * ‖u - u₀‖ ^ (2 : ℕ))
Q₂
(V u₀))
(hVu₀ : V u₀ ∈ Q₂)
(hφ_eq :
φ u₀ = -hatφ u₀ + A (x₀ u₀) u₀ + hatf (x₀ u₀))
(hgradφ_eq :
gradientWithin φ Q₂ u₀ =
(InnerProductSpace.toDual ℝ E₂).symm (A (x₀ u₀)) - gradientWithin hatφ Q₂ u₀)
(hhatφ_model :
∀ ⦃u : E₂⦄, u ∈ Q₂ →
-hatφ u ≤
-hatφ u₀ - inner ℝ (gradientWithin hatφ Q₂ u₀) (u - u₀) +
(L₂φ : ℝ) * d₂ u -
((L₂φ : ℝ) / 2) * ‖u - u₀‖ ^ (2 : ℕ)) :
smoothedPrimalObjective A Q₂ hatf hatφ d₂ (L₂φ : ℝ) (x₀ u₀) ≤
φ (V u₀)6.3 — The Smoothing Technique in Semidefinite Optimization
Corollary 6.3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Corollary 6.3.1 is the canonical symmetric-matrix Hessian estimate from Theorem_6_9.
recall powerTrace_iteratedFDeriv_two_le_absEigenvaluePairing
6.4 — Minimizing the Local Model of an Objective Function
Corollary 6.4.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Corollary 6.4.1: for any iterate index t, if A_t > 0 and the weighted composite-objective gap at x_t relative to x_* is bounded by B_{ν,t}, then equation (6.4.17) holds: \bar f(x_t) - \bar f(x_*) ≤ B_{ν,t} / A_t, where B_{ν,t} = linearOptimizationOracleErrorBound V₀ a G_ν D ν t. The subsequent standard-weight rates (6.4.18)--(6.4.20) are referenced but not restated here.
open scoped WeightSequenceNotation
universe u
variable {E : Type u}
theorem composite_objective_gap_le_error_bound_div_accumulated_weight
(fbar : E → ℝ) (x : ℕ → E) (xStar : E) (a : ℕ → ℝ) (V0 Gν D : ℝ)
{ν : ℝ} {t : ℕ}
(hAt : 0 < A[a](t))
(hweighted :
A[a](t) * (fbar (x t) - fbar xStar) ≤
linearOptimizationOracleErrorBound V0 a Gν D ν t) :
fbar (x t) - fbar xStar ≤
linearOptimizationOracleErrorBound V0 a Gν D ν t / A[a](t)Example 6.4.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Example 6.4.1: for the unit disk Q and f(x) = max{x₁, x₂}, if a conditional-gradient trajectory starts from x₀, and the oracle selects one of the admissible extreme coordinate directions (1, 0) or (0, 1), then every iterate stays in conv{x₀, (-1, 0), (0, -1)}.
open scoped ConstrainedArgmin WithTopConvexAnalysis
namespace CoordinateMaxCounterexample
local notation "E" => EuclideanSpace ℝ (Fin 2)
theorem conditionalGradient_iterates_mem_oracleHull
{x0 : E}
{τ : ℕ → ℝ} (hτ : ∀ t : ℕ, τ t ∈ Set.Icc (0 : ℝ) 1)
{x : ℕ → E} (hx_zero : x 0 = x0)
{g : ℕ → E}
(hg :
∀ t : ℕ,
IsSubgradientAt (fun y ↦ (objective y : WithTop ℝ)) (x t) (g t) ∧
(g t = firstSubgradient ∨ g t = secondSubgradient))
{v : ℕ → E} (hv : ∀ t : ℕ, v t ∈ argmin[feasibleSet] (fun y : E ↦ inner ℝ (g t) y))
(hx_succ : ∀ t : ℕ, x (t + 1) = (1 - τ t) • x t + τ t • v t) :
∀ t : ℕ, x t ∈ oracleHull x0Text 6.4.1.Total.Variation.as.a.First.Order.Optimality.Measure
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6 4 1 Total Variation as a First Order Optimality Measure: the Chapter 6 total variation at a feasible point x bounds the composite-objective gap to any feasible minimizer xStar, and that gap is nonnegative.
open scoped Gradient TotalVariationNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {Q : Set E} {f Ψ : E → ℝ}
local notation:max "δ(" x:arg ")" => δ[Q, f, Ψ](x)
-- Proof sketch: evaluate the total-variation supremum at the feasible minimizer `xStar`. The
-- convex lower-tangent inequality at `x` gives
-- `(f x + Ψ x) - (f xStar + Ψ xStar) ≤ ⟪∇ f x, x - xStar⟫ + Ψ x - Ψ xStar`, and the explicit
-- feasible comparison point `xStar` gives a member of the defining supremum set, so the faithful
-- `EReal` owner allows a direct `le_sSup` step.
theorem totalVariation_ge_compositeObjective_gap_and_nonneg
(hf_conv : ConvexOn ℝ Q f) (x xStar : Q)
(hf_grad : HasGradientWithinAt f (∇ f x) Q x)
(hxMin : IsMinOn (fun y : Q ↦ f y + Ψ y) Set.univ xStar) :
δ(x) ≥ (f x + Ψ x) - (f xStar + Ψ xStar) ∧
0 ≤ (f x + Ψ x) - (f xStar + Ψ xStar)Text 6.4.2.Why.Smoothness.Is.Needed
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6 4 2 Why Smoothness Is Needed: in the nonsmooth counterexample of Example 6.4.1, if the conditional-gradient update is driven by admissible subgradient choices of x ↦ max{x₁, x₂}, then the full trajectory is trapped in the fixed set conv{x₀, (-1, 0), (0, -1)}.
open scoped ConstrainedArgmin
open CoordinateMaxCounterexample
local notation "E" => EuclideanSpace ℝ (Fin 2)
-- Proof sketch: this is the explicit trapping mechanism from Example 6.4.1. The admissible
-- subgradients are the two coordinate vectors `e₁` and `e₂`, so every linearized subproblem on
-- the unit disk selects one of the two oracle vertices. Induction on the update
-- `x_{t+1} = (1 - τ_t) x_t + τ_t v_t` keeps the whole trajectory in
-- `conv{x₀, y₁, y₂}`.
theorem coordinateMax_conditionalGradient_range_subset_oracleHull
{x0 : E}
{τ : ℕ → ℝ} (hτ : ∀ t : ℕ, τ t ∈ Set.Icc (0 : ℝ) 1)
{x : ℕ → E} (hx_zero : x 0 = x0)
{g : ℕ → E}
(hg :
∀ t : ℕ,
IsSubgradientAt (fun y ↦ (objective y : WithTop ℝ)) (x t) (g t) ∧
(g t = firstSubgradient ∨ g t = secondSubgradient))
{v : ℕ → E}
(hv : ∀ t : ℕ, v t ∈ argmin[feasibleSet] (fun y : E ↦ inner ℝ (g t) y))
(hx_succ : ∀ t : ℕ, x (t + 1) = (1 - τ t) • x t + τ t • v t) :
Set.range x ⊆ oracleHull x0Text 6.4.4.Accuracy.Certificates.Recover.Dual.Information
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
If f is presented through the Chapter 6 zero-smoothed max-representation owner and u x lies in the canonical argmax set, then u x realizes the selected dual value of f at x.
open LinearEstimatingCertificate
open scoped BigOperators Gradient WeightSequenceNotation
universe u v
variable {E : Type u} {E₂ : Type v}
[NormedAddCommGroup E] [InnerProductSpace ℝ E]
[NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
variable (f : E → ℝ) (A : E →L[ℝ] StrongDual ℝ E₂) (Qd : Set E₂)
(g : E₂ → ℝ) (u : E → E₂)
variable
(hobj : ∀ x : E, f x = smoothedPrimalObjective A Qd 0 g 0 0 x)
(hu : ∀ x : E, u x ∈ smoothedPrimalObjectiveArgmax A Qd g 0 0 x)
theorem objective_eq_selectedDualValue
(hobj : ∀ x : E, f x = smoothedPrimalObjective A Qd 0 g 0 0 x)
(hu : ∀ x : E, u x ∈ smoothedPrimalObjectiveArgmax A Qd g 0 0 x)
(x : E) :
f x = A x (u x) - g (u x)
Text 6.4.5.Strong.Convexity.Accelerates.Conditional.Gradients
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.4.5-Strong Convexity Accelerates Conditional Gradients: the standing assumption for the composite conditional-gradient regime is that Ψ is strongly convex on the feasible set Q, which means exactly that Q is convex and there exists a positive constant σΨ such that for all x, y ∈ Q and all τ ∈ [0,1], Ψ (τ • x + (1 - τ) • y) ≤ τ * Ψ x + (1 - τ) * Ψ y - (σΨ / 2) * τ * (1 - τ) * ‖x - y‖ ^ 2. This is the curvature assumption used later for the faster rate of method (6.4.12).
recall exists_pos_strongConvexOn_iff_forall_segment_upper_boundText 6.4.6.Second.Order.Model.Applicability
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Text 6.4.6-Second-Order Model Applicability: under the Hölder-continuous second-derivative assumption from (6.4.5), the second-order Taylor model satisfies the upper-model inequality with remainder H * ‖y - x‖^(2 + v) / ((1 + v) * (2 + v)). In the chapter API, this is exactly the canonical theorem holder_hessian_upper_model.
recall holder_hessian_upper_model
Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Proposition_6_38/Support.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.