← All setups

Compositional Entropic Risk Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Minimize F(w)=n−1∑i=1nlog⁡mi(w) over a nonempty closed convex set W in a separable real Hilbert space, where mi(w)=∫esi(w;ξ)dpi(ξ). Jointly measurable scores and subgradients satisfy si(w;ξ)∈[c0,c1], si(y;ξ)≥si(w;ξ)+⟨gi(w;ξ),y−w⟩, and, uniformly on W, ∫∥gi∥2dpi≤G2, ∫e2sidpi≤κmi2, ∫e2si∥gi∥2dpi≤σ2mi2. Here n,B≥1, G>0, κ≥1, σ,R≥0, ε>0, and w0,w⋆∈W, with w⋆ minimizing F and ∥w0−w⋆∥≤R. The oracle provides exact projection and IID uniform-anchor draws, each with two conditionally independent score–subgradient samples from pi. Target: ∫[F(w¯(ω))−F(w⋆)]dP(ω)≤ε under the IID execution law P; (1) constructs the SCENT average.

Compositional entropic risk under the CompositionalEntropicRisk setup.
Result Oracle complexity Novelty Limitations
(1) ScentCompositionalEntropicRisk (Ours) (⋆⋆⋆) (review) O(B+(B+1)κG2R2(1+eΔε)ε2+1+εε2(eΔmin{σ2,eΔG2}R2+neΔ[1+(1+Δ)(κ−1)])). Sequential sampling with replacement; total calls minimized at B=1.
(2) SCENT (Wei et al. 2026), Thm. 3.6 and Assumption 4.1. Derived bound, B=1; finite-dimensional, differentiable-score specialization. O(1+e2Δmin{σ2,G2}R2ε2+n(1+Δ)e2Δmin{κ−1,1}ε2+neΔε).

(1): Method-specific rate gain for joint optimization, including n≥2. For B=1, ε≤e−Δ, primal savings up to eΔ when κG2≲eΔσ2≤e2ΔG2; anchor savings factor eΔ(1+Δ)min{κ−1,1}1+(1+Δ)(κ−1) when >1.

Rademacher linear-score example: Δ=4r≥1, κ=G2=2, σ2=4, ε≤e−Δ: O(eΔ[R2+n(1+Δ)]/ε2) instead of O(e2Δ[R2+n(1+Δ)]/ε2).

(1): At κ=1, anchor cost neΔ/ε2 instead of neΔ/ε; worse when n≫eΔG2R2. Extra primal term eΔκG2R2/ε.
(3) Joint projected SGD (Nemirovski et al. 2009), §2.2, (2.15). Derived bound on W×[c0,c1]n; finite-dimensional specialization. O(1+e2Δ(GR+nΔ)2ε2). (1): In the Rademacher regime stated for (2), total cost O(eΔ[R2+n(1+Δ)]/ε2) instead of O(e2Δ[R+nΔ]2/ε2).

Abbr: Δ=c1−c0; n is the number of anchors; B is the number of sample calls per SCENT iteration. Costs count all sample and projection calls: an iteration in (1) uses B paired-sample calls and one projection, equivalently 2B primitive score–subgradient evaluations and one projection up to universal factors. P is the probability law of the execution, and w¯ its averaged output. In the example, si(w;ξ)=⟨ai,w⟩+u(ξ)⟨bi,w⟩, u=±1 equiprobably, ∥ai∥,∥bi∥≤1, and W is a radius-r ball; the displayed moment constants are valid upper bounds.

Nemirovski, Arkadi, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. 2009. “Robust Stochastic Approximation Approach to Stochastic Programming.” SIAM Journal on Optimization 19 (4): 1574–609. https://doi.org/10.1137/070704277.
Wei, Xiyuan, Linli Zhou, Bokun Wang, Chih-Jen Lin, and Tianbao Yang. 2026. A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization. https://doi.org/10.48550/arXiv.2602.02877.

Lean setup