← All setups

Scent Compositional Entropic Risk — Compositional Entropic Risk Minimization

Descriptions may be stale. Consult the linked Lean sources.

Compositional Entropic Risk Minimization · Lean proof

Compositional Entropic Risk Minimization

We minimize F(x)=n−1∑i=1nlog⁡Eξ∼νi[esi(x,ξ)] over a nonempty closed convex set C in a separable real Hilbert space E, where n≥1, νi are probability laws, and si are bounded convex sample scores. Measurable score subgradients satisfy second-moment and exponentially weighted moment bounds, and a given starting point lies near a minimizer x⋆∈C. The oracle returns two independent score–subgradient pairs for one uniformly sampled component, or an exact projection onto C. For ε>0, the goal is a measurable, everywhere feasible output x¯ with integrable gap and E[F(x¯)−F(x⋆)]≤ε, averaging over independent algorithm and oracle randomness.

Let Ξ be a measurable sample space, and write si:E×Ξ→R,gi:E×Ξ→E,Zi(x)=Eξ∼νi[esi(x,ξ)],F(x)=1n∑i=1nlog⁡Zi(x). The optimization problem is minx∈CF(x). The norm is induced by the inner product on E. The parameters satisfy n,B∈N,n≥1,B≥1,c0,c1∈R,c0≤c1,G>0,κ≥1,σ≥0,R≥0,ε>0. The algorithm receives E, Ξ, n, B, c0, c1, G, κ, σ, R, ε, and the starting point x0; the scores, subgradients, laws, and feasible set are accessed through the oracle.

Our assumptions:

Assumption 1 (Feasible set and initial distance). The set C⊆E is closed and convex, and x0∈C. There exists x⋆∈C such that F(x⋆)≤F(x)for every x∈C,∥x0−x⋆∥≤R.

Assumption 2 (Bounded scores and subgradients). For each i∈{1,…,n}, the maps si and gi are jointly measurable. For every ξ∈Ξ and x,y∈C, si(x,ξ)+⟨gi(x,ξ),y−x⟩≤si(y,ξ),c0≤si(x,ξ)≤c1. Thus gi(x,ξ) is a subgradient of the sample score on C.

Assumption 3 (Moment bounds). For each i∈{1,…,n} and x∈C, the function ξ↦∥gi(x,ξ)∥2 is integrable under νi, and Eξ∼νi[∥gi(x,ξ)∥2]≤G2,Eξ∼νi[e2si(x,ξ)]≤κZi(x)2,Eξ∼νi[e2si(x,ξ)∥gi(x,ξ)∥2]≤σ2Zi(x)2.

Queries may be made at any point of E. At a sampling query x, a component I is drawn uniformly from {1,…,n}. Conditional on I=i, two samples ξ and ξ′ are drawn independently from νi. The reply is (I, (sI(x,ξ),gI(x,ξ)), (sI(x,ξ′),gI(x,ξ′))). Each score and its subgradient use the same sample, and the two pairs share the component index. The draws used at successive calls are independent and identically distributed, and independent of the algorithm’s randomness.

At a projection query x, the oracle returns ΠC(x). The map ΠC:E→E is measurable and satisfies ΠC(x)∈Cfor every x∈E,⟨x−ΠC(x),u−ΠC(x)⟩≤0for every x∈E, u∈C. Sampling and projection queries share one total call budget; a sampling call returns both pairs above.

After the allotted calls, the output x¯ must be measurable and belong to C for every realization. Its objective gap must be integrable and satisfy EP[F(x¯)−F(x⋆)]≤ε, where P is the joint law of the independent algorithm and oracle randomness, and x⋆ is a fixed minimizer on C.

Proved result

(B+1)⋅⌈64⋅κ⋅G2⋅R2⋅(1+exp⁡(c1−c0)⋅ε)+32⋅min{2⋅exp⁡(c1−c0)⋅σ2,exp⁡(2⋅(c1−c0))⋅G2}⋅R2⋅(1+ε)B+8⋅n⋅exp⁡(c1−c0)⋅(1+64⋅(1+(c1−c0))⋅(κ−1))⋅(1+ε)Bε2⌉+

OracleTemplate.Convergence LongTails.Setups.CompositionalEntropicRisk.spec
  OracleTemplate.Scent.ScentCompositionalEntropicRisk.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.