Comparison map for lower-linearizability ((40)–(41))
DefinitionTiltedCvx_Supplement_IsComparisonMapconvex-analysisgeneralized-convexitynonsmooth-analysisoptimizationp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , and a class of functions on . The class is lower-linearizable with coefficient if there are maps , and with (40). The paper uses the case , :
Here is the upper tilt of §3 (the published TiltedCvx.psiBar), so for . A map satisfying (41) is called here a comparison map for ; it reduces online optimization over to online linear optimization with –regret.
Formalization Note Functions on are real functions on read on ; is read only at , . A comparison map witnesses (40) with , .
Definition code
import Mathlib
import Definitions.Def_TiltedCvx_psiBar
open scoped InnerProductSpace
namespace TiltedCvx.Supplement
/-- **Comparison map for lower-linearizability with coefficient α ((40)–(41)).**
Pedramfar–Khanna–Quinn–Aggarwal, arXiv:2611.03472, §8.2, (40)–(41), p.41: a class `𝓒` of
functions on `K` is lower-linearizable with coefficient `α` if there are maps
`g : 𝓒 × K → ℝ^d`, `χ : K → K` and `β > 0` with `f(χ(x)) − ψ̄α(f(y)) ≤ β⟨g(f, x), x − y⟩` (40);
in the special case `χ = id`, `β = 1` used by the paper this reads
`f(x) − ψ̄α(f(y)) ≤ ⟨g(f, x), x − y⟩` for all `f ∈ 𝓒` and `x, y ∈ K` (41).
`IsComparisonMap α K 𝓒 g` says that `g` satisfies (41).
**Formalization Note** Functions on `K` are `E → ℝ` (only values on `K` enter); `g` is a map
`(E → ℝ) → E → E`, read only at `f ∈ 𝓒`, `x ∈ K`. A map satisfying (41) witnesses (40) with
`χ = id`, `β = 1`. The tilt is the upper tilt `ψ̄α(z) = max{αz, α⁻¹z}` (the published
`TiltedCvx.psiBar`; the rendered (40)–(41) have the bar, which the text layer drops), so that
`ψ̄α(z) = αz` for `z ≤ 0`, as the paper notes after (40). -/
def IsComparisonMap {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
(α : ℝ) (K : Set E) (C : Set (E → ℝ)) (g : (E → ℝ) → E → E) : Prop :=
∀ f ∈ C, ∀ x ∈ K, ∀ y ∈ K,
(f x : EReal) - TiltedCvx.psiBar α (f y : EReal) ≤ ((⟪g f x, x - y⟫_ℝ : ℝ) : EReal)
end TiltedCvx.Supplement
Source
Pedramfar–Khanna–Quinn–Aggarwal, Tilted Convexity and an Exact Offline–Online Separation, arXiv:2611.03472, §8.2, (40)–(41), p.41