Documentation

IntroductoryLecturesOnConvexOptimization_Nesterov_2004.Chap04.Lemma_4_2_3

theorem powerDistance_fderiv_pairing_eq_explicit_gradient_pairing {F : Type u} [NormedAddCommGroup F] [InnerProductSpace F] [CompleteSpace F] (p : ) (x0 x y : F) (hp : 2 p) :
((Module.dualPairing F) ((fderiv (powerDistance p x0) x) - (fderiv (powerDistance p x0) y))) (x - y) = inner (x - x0 ^ (p - 2) (x - x0) - y - x0 ^ (p - 2) (y - x0)) (x - y)

Helper for Lemma 4.2.3: on the canonical Hilbert-space owner powerDistance, the derivative pairing is exactly the inner product with the explicit power-gradient difference.

theorem powerDistance_fderiv_mono_ge_norm_rpow_of_explicit_gradient_mono {F : Type u} [NormedAddCommGroup F] [InnerProductSpace F] [CompleteSpace F] (p : ) (x0 x y : F) (hp : 2 p) (hmono : (1 / 2).rpow (p - 2) * x - y.rpow p inner (x - x0 ^ (p - 2) (x - x0) - y - x0 ^ (p - 2) (y - x0)) (x - y)) :
((Module.dualPairing F) ((fderiv (powerDistance p x0) x) - (fderiv (powerDistance p x0) y))) (x - y) (1 / 2).rpow (p - 2) * x - y.rpow p

Helper for Lemma 4.2.3: after rewriting the derivative pairing into the explicit gradient pairing on the owner powerDistance, the source monotonicity estimate is exactly (4.2.14).

theorem powerFunction_uniformConvexOn {E : Type u} [AddCommGroup E] [Module E] (B : LinearMap.BilinForm E) (hPos : (LinearMap.BilinMap.toQuadraticMap B).PosDef) (p : ) (x0 : B.PrimalSpace) (hp : 2 p) :
have x := hp; UniformConvexOn Set.univ (uniformConvexPowerModulus ((1 / 2).rpow (p - 2)) p) (powerFunction B p x0)

Lemma 4.2.3 in owner form: on the intrinsic B-weighted space, the degree-p power regularizer is uniformly convex with the textbook modulus (1 / p) * (1 / 2)^(p - 2) * r^p.

theorem powerFunction_fderiv_mono_ge_primalNorm_rpow {E : Type u} [AddCommGroup E] [Module E] (B : LinearMap.BilinForm E) (hPos : (LinearMap.BilinMap.toQuadraticMap B).PosDef) (p : ) (x0 x y : B.PrimalSpace) (hp : 2 p) :
have x_1 := hp; ((Module.dualPairing B.PrimalSpace) ((fderiv (powerFunction B p x0) x) - (fderiv (powerFunction B p x0) y))) (x - y) (1 / 2).rpow (p - 2) * x - y.rpow p

Lemma 4.2.3 (1): for a positive-definite self-adjoint form B, the Fréchet derivative of the degree-p power function d_p(x) = (1 / p) * ‖x - x₀‖[B]^p is strongly monotone with modulus (1 / 2)^(p - 2) when measured in the intrinsic norm on PrimalSpace B, i.e. in the B-induced norm.

theorem powerFunction_lower_tangent_ge_primalNorm_rpow {E : Type u} [AddCommGroup E] [Module E] (B : LinearMap.BilinForm E) (hPos : (LinearMap.BilinMap.toQuadraticMap B).PosDef) (p : ) (x0 x y : B.PrimalSpace) (hp : 2 p) :
have x_1 := hp; powerFunction B p x0 x powerFunction B p x0 y + ((Module.dualPairing B.PrimalSpace) (fderiv (powerFunction B p x0) y)) (x - y) + 1 / p * (1 / 2).rpow (p - 2) * x - y.rpow p

Lemma 4.2.3 (2): for a positive-definite self-adjoint form B, the degree-p power function lies above its tangent model at y by at least (1 / p) * (1 / 2)^(p - 2) * ‖x - y‖^p in the intrinsic norm on PrimalSpace B; equivalently, the Bregman gap at y has the same lower bound.