Optimized Certainty Equivalent Risk Minimization Using Samples: Algorithms, Convergence Rates, and Applications

Optimized Certainty Equivalent Risk Minimization Using Samples: Algorithms, Convergence Rates, and Applications Sumedh Gupte 1,2 , Prashanth L. A. 2 , Sanjay P. Bhat 1 1

2

TCS Research, IIIT-H Research Park, Hyderabad, 500032, India Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, 600036, India sumedh.gupte@tcs.com, prashla@cse.iitm.ac.in, sanjay.bhat@tcs.com

arXiv:2608.07113v1 [stat.ML] 7 Aug 2026

Abstract We consider the optimization of the Optimized Certainty Equivalent (OCE) risk, with applications including portfolio optimization in finance, and uncertainty quantification, classification, and regression in machine learning. Our contributions cover popular special cases of OCE, such as entropic risk, mean-variance risk, and smooth variants of Conditional Value-at-Risk. Our treatment sets out the conditions that facilitate the extension of OCE to unbounded r.v.s.. We provide a useful characterization of OCE that links OCE to utility-based shortfall risk (UBSR). Our characterization enables us to form an OCE estimator from the classic sample-average approximation (SAA) of UBSR. We derive mean-squared error (MSE) bounds for our proposed OCE estimator. For OCE optimization, we first derive an expression for the OCE gradient using the characterization linking OCE to UBSR. This expression serves as the basis for a gradient estimator for the OCE. We derive non-asymptotic bounds on the MSE for the proposed OCE gradient estimator. We incorporate the aforementioned gradient estimator into a stochastic gradient (SG) algorithm to optimize OCE and quantify its convergence rate using nonasymptotic bounds that we derive. Finally, we present three experiments that use our OCE optimization algorithm to solve portfolio optimization and uncertainty quantification problems.

Introduction Accurate risk quantification is of prime importance in applications where assessment and mitigation of risk are critical both from a business perspective as well as a regulatory perspective. Examples of such application areas include the finance, healthcare, and insurance industries. A risk measure provides a quantitative assessment of a risky financial position formulated as a random variable (r.v.). A financially relevant risk measure should align with human perception and intuitive understanding of risk. For instance, when a financial position is evaluated purely based on its expected value, it downplays the risk associated with extreme but rare events. While the Value at Risk (VaR) (Jorion 1997; Basak and Shapiro 2015) highlights the risk from tail events, it fails to be sub-additive (Artzner et al. 1999) and thus militates against the intuition that that diversification should reduce risk. These considerations motivated a formal look at the properties that a financial risk measure should possess (Acerbi and Tasche 2002) and led to the notion of a

convex risk measure (Föllmer and Schied 2004). A convex risk measure possesses the financially relevant properties of monotonicity (higher losses represent greater risks), cash equivariance (more cash in hand means less risk) and subadditivity (diversification cannot increase risk). Convex risk measures also share a deep connection with the framework of Distributionally Robust Optimization (DRO) (Kuhn, Shafiee, and Wiesemann 2025), which has received increased research attention in the operations research and the machine learning (ML) communities. In the context of ML, DRO provides a seemingly better alternative to the classical empirical risk minimization (ERM) framework. Since optimizing a convex risk measure is equivalent to solving a DRO problem (Rahimian and Mehrotra 2022), developing risk minimization algorithms is meaningful and warrants research attention. OCE is a class of convex risk measures that generalizes CVaR and includes several popular risk measures, such as entropic risk, monotone mean-variance, and quartic risk, as special cases. The introduction of OCE in literature (Ben-Tal and Teboulle 1986), however, predates the emergence of risk measures (Artzner et al. 1999) and associated properties like convexity or coherence. OCE is associated with the idea of a preference order (⪰) that is commonly used in the expected utility theory (von Neumann and Morgenstern 1944), where for a utility function u and any two r.v.s. X, Y , we have X ⪰ Y (X is preferred over Y ) if and only if E [u(X)] ≥ E [u(Y )]. In a financial application, X and Y could denote the random returns associated with two different investment strategies. A certainty equivalent, say C(X), for a decision maker is a sure amount that is equivalent to the uncertain quantity X, and imposes the following preference order: X ⪰ Y if and only if C(X) ≥ C(Y ). OCE risk measure (Ben-Tal and Teboulle 1986) is a type of certainty equivalent that is based on utility functions. OCE was later reintroduced as a convex risk measure by Ben-Tal and Teboulle (2007). OCE risk measures are also connected to the information-theoretic concept of ϕ-divergence, and the reader is referred to BenTal and Teboulle (2007) and Section 4.9 of Föllmer and Schied (2016) for a precise statement of the aforementioned connection. Our contributions. We consider OCE estimation and optimization under uncertainty, i.e., using samples from the un-

Table 1: Comparison of related works w.r.t. OCE estimation and optimization. Here MSE, MAE denote mean-squared and mean-absolute errors, and SC, C, NC denotes strongly-convex, convex and non-convex objectives, respectively. OCE estimation includes Lipschitz utility in CVaR (see example 5) as well as several non-Lipschitz utilites (see examples 1 to 4). OCE optimization covers the linear case in portfolio optimization (see example 8) as well as non-linear cases in examples 9 to 11. (a) Comparison of OCE risk estimation guarantees.

Reference L.A. et al. 2022 Ghosh et al. 2024 Hamm et al. 2013 Our work

Bound type MAE MSE Asymptotic MSE, MAE

Non-Lipschitz utility ✗ ✗ ✗ ✓

(b) Comparison of OCE risk optimization guarantees.

Reference Natarajan et al. 2010 Shapiro et al. 2021 Tamtalini et al. 2022 Our work

derlying model, which is not known. Our contributions cover popular special cases of OCE, such as entropic risk, meanvariance risk, and two smooth variants of Conditional Valueat-Risk that we propose. Table 1 provides a summary comparison of our contributions against closely related works. We first extend the OCE formalism to unbounded r.v.s. while imposing an integrability condition. For this class, we establish the convexity of OCE. Our main contribution is to solve the OCE optimization problem under a smooth parameterization of the underlying r.v. We adopt a gradient-based approach and derive an expression for the OCE gradient. Next, we form a gradient estimate using samples, and establish MSE and MAE bounds for this estimator. Finally, we propose a SG algorithm for OCE optimization and provide non-asymptotic bounds that quantify the convergence rate of this algorithm. We derive these bounds for three cases: when the underlying parameterization yields a strongly convex, a convex, or a non-convex OCE objective. As a secondary contribution, we study the problem of OCE estimation from independent and identically distributed (i.i.d.) samples using an SAA approach. In particular, we exploit the connection between OCE and UBSR to derive an estimator of OCE from UBSR. For this estimator, we derive bounds on the MSE and MAE under a moment assumption on the underlying r.v. These bounds for OCE estimation are of independent interest. Finally, we conduct simulation experiments on OCE minimization for the following settings: classification, portfolio optimization, and uncertainty quantification. Additional experiments on CVaR estimation and optimization, and entropic risk estimation and optimization are available in Section E of the supplementary material. Related work. The OCE measure was first introduced by Ben-Tal and Teboulle (1986) as a decision-making criterion. Ben-Tal and Teboulle (2007) reformulated the OCE criterion and presented it as a risk measure. In particular, they derived useful properties, such as convexity and coherence, under the assumption that the r.v.s. are bounded and the utility function is sublinear. Hamm, Salfeld, and Weber (2013) provided a stochastic approximation scheme for OCE estimation, with an asymptotic convergence guarantee. Tamtalini, Matoussi, and Kaakai (2022) analyzed a multivariate form of OCE and proposed a stochastic approximation scheme for OCE esti-

Risk measure OCE Convex risk OCE OCE

Guarantee type Empirical Asymptotic Asymptotic Non-asymptotic

Objective Linear C Linear SC/C/NC

mation, wherein they showed asymptotic convergence and asymptotic normality of their estimator. Prashanth and Bhat (2022); Ghosh, Prashanth, and Jagannathan (2024) studied an SAA scheme for OCE estimation; the former gave MAE bounds for a Lipschitz utility function, while the latter gave MSE bounds for a smooth and strongly-convex utility function. In comparison to these works, we would like to the note the following aspects: i) Unlike (Hamm, Salfeld, and Weber 2013), our results for OCE estimation/optimization apply to possibly unbounded r.v.s.; ii) Unlike Ben-Tal and Teboulle (2007), we neither assume that the utility function is sublinear, nor assume that u(0) = 0 holds; iii) Unlike Shapiro, Dentcheva, and Ruszczynski (2021); Tamtalini, Matoussi, and Kaakai (2022); Hamm, Salfeld, and Weber (2013), we provide non-asymptotic error bounds on the proposed SAA estimator; iv) Unlike Prashanth and Bhat (2022), we provide MSE bounds, and our bounds allow for utility functions that may not be Lipschitz; v) Unlike Ghosh, Prashanth, and Jagannathan (2024), our MSE bounds do not require a strongly-convex utility function. Previous works on OCE risk optimization focus specifically on portfolio optimization and are limited to a few specific utility functions. These works use convex optimization routines and are either empirical (Natarajan, Sim, and Uichanco 2010) or provide only asymptotic guarantees (Tamtalini, Matoussi, and Kaakai 2022; Shapiro, Dentcheva, and Ruszczynski 2021). To the best of our knowledge, nonasymptotic bounds for OCE optimization using a stochastic gradient scheme are not available in the literature. Preliminaries We use boldface (v), uppercase (X), and a combination of boldface and uppercase (Z) to denote vectors, random variables, and random vectors, respectively. We use ’Var’ as an abbreviation for variance. The terms x+ and x− indicate max {x, 0} and max {−x, 0}, respectively. For p ∈ [1, ∞), ∥v∥p denotes the vector p-norm. Let (Ω, F , P ) be a probability space, L0 denote the space of F-measurable, real r.v.s. on Ω, and E(·) denote
the expectation under P . For p ∈ [1, ∞), Lp , ∥·∥Lp denotes the normed vector space of r.v.s. with finite pth moment. Let Z be a random vector such that each Zi is F-measurable and has finite pth moment. Then the  h i p1 p Lp -norm of Z is defined by ∥Z∥Lp ≜ E ∥Z∥p .

Let µX and µY denote the marginal distributions of r.v.s. X and Y , respectively. Let H(µX , µY ) denote the set of all joint distributions having µX and µY as the marginals. Then, for every p ≥ 1, Wp (µX , µY ) ≜
1/p R p de∥x − y∥ η(dx, dy) : η ∈ H(µX , µY ) inf notes the pth Wasserstein distance (Panaretos and Zemel 2020). Given a real-valued function f : R → R, Xf ⊆ L0 denotes the space of r.v.s. X for which f (X −t) is integrable for every t ∈ R. The risk measures that we consider in this paper are well-defined when X ∈ Xf , i.e., when E [f (X − t)] is finite for all t ∈ R. When the random variable X is unbounded, the finiteness of the above expectation not only depends on X, but also on f . This dependency motivates the use of the Xf notation above. For the remainder of the paper, the r.v. X denotes losses; therefore, a lower value is more preferable.

risk measure for the above utility function satisfies several useful properties. See Hamm, Salfeld, and Weber (2013) for more details. Example 5 (CVaR). Let α ∈ (0, 1) and define the utility function as u(x) = α−1 x+ , ∀x ∈ R. Then, OCEu (X) coincides with CVaRα (X). The Conditional Value-at-Risk (CVaR) at level R α ∈ (0, 1) for a r.v. X is given by α CVaRα (X) ≜ α1 0 VaRγ (X)dγ.

OCE Risk for Unbounded Random Variables

Characterization of OCE risk. For the main result characterizing OCE, we make the following assumption, which is satisfied by all the utility functions in examples 1 to 7. Assumption 1. The convex and increasing utility function u is continuously differentiable a.e., such that the range of u′ contains 1 in its interior. We characterize the OCE risk of an r.v. X using shortfall risk, a popular risk measure in finance. The shortfall risk, also known as ‘utility-based shortfall risk’ (UBSR), is specified using a loss function l and a risk threshold λ. The UBSR is formally defined below. Definition 3. Let l : R → R be increasing and continuous a.e., and let λ be a scalar value chosen within the range of l. Then, the UBSR for an r.v. X is given as

In this section, we characterize the OCE risk measure using an expression that relates OCE risk to UBSR. In addition, our analysis covers a class of unbounded r.v.s and shows that properties such as convexity continue to hold. In the financial domain, if a risk measure is convex, then diversification cannot increase this risk. We define convex risk measures below. Definition 1. A risk measure ρ : X → R is convex, if X is convex and for every X1 , X2 ∈ X and α ∈ [0, 1], we have ρ(αX1 + (1 − α)X2 ) ≤ αρ(X1 ) + (1 − α)ρ(X2 ). OCE is a convex risk measure (Ben-Tal and Teboulle 2007), and is formally defined below. Definition 2. Let u : R → R be a convex and increasing function. Let the r.v. X ∈ Xu . Then the OCE risk of X under the utility function u is defined as follows: OCEu (X) ≜ inf {t + E [u(X − t)]}. t∈R

Popular OCE Examples Example 1 (Entropic risk). Let β >
0 and define the utility function as u(x) = β −1 eβx − 1 , ∀x ∈ R. Then, the OCE risk measure coincides with the entropic risk measure (Föllmer and Schied 2016, Example 4.13), i.e.,
1 OCEu (X) = log E[eβX ] . (1) β Example 2 (Mean variance risk). Let the utility function be given by u(x) = x + βx2 for all x ∈ R. Then, the OCE risk measure coincides with the mean variance risk measure, i.e., OCEu (X) = E[X] + βVar(X). Example 3 (Monotone mean variance). Let a ≥ 2 and define a the utility function as u(x) = a−1 ([x + 1]+ ) − a−1 for all x ∈ R. For the choice of a = 2, the OCE risk measure coincides with the monotone mean-variance risk measure, see (Tamtalini, Matoussi, and Kaakai 2022) and (Černý et al. 2012, eq 1.10). Example 4 (Quartic risk). Define the utility function as 4 u(x) = ([x + 1]+ ) − 1 for all x ∈ R. The resulting OCE

Example 6 (Leaky-CVaR (L-CVaR)). Let α ∈ (0, 1) and de-
fine the utility function as u(x) = α−1 x+ −arctan α−1 x− for all x ∈ R. Then, OCEu (X) is a variant of CVaR that is sensitive to tail losses. Example 7 (Smooth-CVaR (S-CVaR)). Let α ∈
(0, 1) and x define the utility function as u(x) = α ln 1 + e α , ∀x ∈ R. Then, OCEu (X) is a smooth variant of CVaR and is sensitive to tail losses.

SRl,λ (X) ≜ {inf |E [l(X − t)] ≤ λ }. t∈R

Consider the function GX (·) : R → R defined below. GX (t) ≜ t + E [u(X − t)] . The expectation above is finite if X ∈ Xu . If X ∈ Xu′ also holds, then it is easy to see that GX is convex and differentiable, and the derivative of GX is given by ′

GX (t) = 1 − E [u′ (X − t)] .

(2) ∗

Suppose GX (·) attains a minimum at some t ∈ R, then we have OCEu (X) = GX (t∗ ) = t∗ + E [u(X − t∗ )] .

(3)

For some pathological cases, GX (·) may not attain a minil mum in R. To avoid such  lcases,  we assume existence of tX u ∗ u and tX such that t ∈ tX , tX . Furthermore, GX is convex, and therefore, finding t∗ , the minimizer of GX (·), is equivalent to finding the root of (2), and this problem can be solved by associating it with the UBSR, under suitable assumptions on X and u. Precisely, we equate u′ and 1 with l and λ respectively, and hence, u being convex and continuously differentiable a.e. is analogous to l being increasing and continuous a.e., respectively, which conforms to Definition 3. We denote X̄u ≜ Xu ∩ Xu′ , and present the following proposition, which associates the OCE risk with the UBSR.

Proposition 1. Suppose the utility function satisfies Assumption 1 and let X ∈ X̄u . Suppose there exist tuX , tlX ∈ R such ′ ′ that GX (tuX ) ≤ 0 < GX (tlX ). Then, SRu′ ,1 (X) is a root ′ of GX (·) as well as a minimizer of GX (·). Furthermore, the OCE of X is given as OCEu (X) = SRu′ ,1 (X) + E [u(X − SRu′ ,1 (X)] , and OCEu (·) is a convex risk measure. Remark 1. We provide a Wasserstein-distance bound on the difference in OCE between two distributions, in the spirit of (Prashanth and Bhat 2022), albeit for the non-Lipschitz utility case. In particular, we obtain p |OCEu (X) − OCEu (Y )| ≤ W2 (µX , µY ) σ12 + 1, where we assume Var (u′ (X − SRu′ ,1 (X))) ≤ σ12 . In Lemma 12 of Prashanth and Bhat (2022), the authors obtained a bound on |OCEu (X) − OCEu (Y )| in terms of the 1-Wasserstein distance (between marginals µX and µY ) under the assumption that the utility function is Lipschitz. Our extension covers examples 1 to 4, which includes popular OCE instances with non-Lipschitz utility functions. See Section A.2 for more details.

OCE Risk Estimation In this section, we consider the problem of estimating the OCE risk of a r.v. X ∈ X̄u using samples from the distribution of X. For m ∈ N , we obtain i.i.d samples {Zi }m i=1 (also indicated as a random vector Z) and use them construct SRm (Z), an estimator of SRu′ ,1 (X). We use the same samples to construct OCEm (Z), the estimator of OCEu (X). The estimators SRm : Rm → R and OCEm : Rm → R are defined as   m   1 X ′ SRm (z) ≜ min t ∈ R u (zj − t) ≤ 1 , (4)   m j=1

m

OCEm (z) ≜ SRm (z) +

1 X [u(zj − SRm (z))] . m j=1

(5)

In the following lemma, we bound the OCE estimation error in the case where the utility function is Lipschitz. Lemma 1. Suppose Assumption 1 and the assumptions of Proposition 1 are satisfied, and the utility function u is KLipschitz. If there exists q > 2 and T > 0 such that ∥X∥Lq ≤ T , then 39KT E [|OCEm (Z) − OCEu (X)|] ≤ √ . m If there exists q > 4 and T > 0 such that ∥X∥Lq ≤ T , then h i 108K 2 T 2 2 √ E |OCEm (Z) − OCEu (X)| ≤ . m In Corollary 20 of Prashanth and Bhat (2022), √ the authors derived an MAE bound of the order O (1/ m) for OCE estimation under the assumption that the utility function is Lipschitz. Their result does not include MSE bounds, which will be useful for deriving convergence rates of our OCE optimization algorithm. Furthermore, several popular instances of OCE risk are not Lipschitz, e.g., see examples 1 to 4. We fill these gaps under the following additional assumption.

Assumption 2. There exists σ1 > 0 such that the utility function satisfies Var (u′ (X − SRu′ ,1 (X))) ≤ σ12 . This assumption is satisfied for examples 2 to 7 when the underlying distribution has bounded higher moments, and for Example 1, when X is sub-Gaussian. Lemma 2. Suppose assumptions 1 and 2, and the assumptions of Proposition 1 are satisfied. Let there exist q > 4 and T > 0 such that ∥X∥Lq ≤ T . Then, we have h i 108(σ 2 + 1)T 2 2 1 √ E |OCEm (Z) − OCEu (X)| ≤ , m where σ1 is as given in assumption 2 respectively. Efficient procedure for OCE Estimation. We note that the UBSR estimation problem in eq. (4) is a root-finding problem Pm of′ a deterministic and monotone function gz (t) = 1 j=1 u (−zj − t) − 1, and can be solved efficiently using m bisection search. We now provide a simple procedure for estimating the quantity in eq. (4) using samples z. 1. Find the interval [low,high] such that gz (high) ≤ 0 ≤ gz (low). 2. Choose ϵ, δ > 0 and use bisection on this interval to find a solution that satisfies the following: t̂m − SRm (z) ≤ δ, and gz (t̂m ) ≤ ϵ,

(6)

For the sake of completeness, we include Algorithm 1 in the supplementary, whose output satisfies eq. (6). Next, we present the following scheme to approximate OCEm (z) using the samples z and the UBSR estimate t̂m : m 1 X ŝm ← t̂m + u(Zi − t̂m ) (7) m i=1 Choosing smaller values for δ and ϵ ensures that the output ŝm lies closer to OCEm (Z). Estimation bounds on ŝm can be established in a manner similar to those available in lemmas 1 and 2, and a detailed exposition is provided in Section B.3 in the supplementary.

OCE Risk Optimization We consider the following problem: Find θ∗ ∈ arg min OCEu (F (θ, ξ)).

(8)

θ∈Θ

In the above, given any θ ∈ Θ, F (θ, ξ) is the r.v. associated with the parameter θ and ξ denotes the noise factor, independent of θ. The decision set Θ is a subset of T ⊆ Rd , where T is an open and convex set. The OCE risk and its properties are well-defined for any element in T , whereas Θ is a possibly constrained and problem-dependent construct. For instance, in a portfolio optimization problem, Θ is a ddimensional simplex denoting portfolio weights. We present several choices of F that yield well-known problem instances in machine learning and finance. Example 8 (Portfolio Optimization). Consider a financial market with d assets, and let the random vector ξ ∈ Rd denote asset-wise market returns. Let θ ∈ Θ denote an asset allocation or portfolio weight, then the r.v. F (θ, ξ) ≜ −ξ T θ denotes portfolio losses associated with θ.

Example 9 (Classification). Consider a classification problem with K classes, where ξ denotes the random vector corresponding to the inputs and targets. Every data point z ≜ ⟨x, y⟩ is thus sampled from the distribution of ξ, where y is a K-dimensional one-hot encoded vector. Each parameter vector θ in the decision set Θ corresponds to a model fˆ(x; θ) that outputs the raw logits for a given input x. The categorical cross-entropy loss F (θ, z)
is then defined as: ˆ F (θ, z) = −⟨y, log softmax f (x; θ) ⟩. Example 10 (Regression). Consider a regression problem where ξ denotes the random vector corresponding to the inputs and continuous targets. Every data point z ≜ ⟨x, y⟩ is thus sampled from this distribution of ξ, where y ∈ R is a scalar target value. Each parameter vector θ in the decision set Θ corresponds to a model fˆ(x; θ) that outputs a scalar prediction for a given input x. The squared residual F (θ, z)  2 is then defined as:F (θ, z) = fˆ(x; θ) − y . Example 11 (Uncertainty Quantification). We consider the Mean Variance Estimation (MVE) framework for uncertainty quantification, where every data point z ≜ ⟨x, y⟩ is drawn from a random vector
ξ, that has the joint distribution y | x ∼ N µ(x), σ 2 (x) . The model parameters θ are learned by minimizing F (θ, z), the negative log-likelihood (NLL) of a Gaussian distribution (omitting constant terms) given by: 2

F (θ, z) =

1 (y − µθ (x)) 1 log σθ2 (x) + . 2 2 σθ2 (x)

(9)

OCE Gradient and properties. We use the association between the OCE and the UBSR given by Proposition 1 to derive the expression for the gradient of OCE. For notational convenience, let OCE(θ) ≜ OCEu (F (θ, ξ)), and SR(θ) ≜ SRu′ ,1 (F (θ, ξ)). We first state an assumption made in Proposition 1 using notation that involves θ and F . Assumption 3. For every θ ∈ T , F (θ, ξ) ∈ X̄u and there exist tu (θ), tl (θ) ∈ R such that G′F (θ,ξ) (tu (θ), θ) ≤ 0 and G′F (θ,ξ) (tl (θ), θ) > 0. A similar assumption has been made in Hu and Zhang (2018); Hegde et al. (2024). Under assumptions 1 and 3, Proposition 1 implies that ∀θ ∈ T , OCE(θ) is expressed as OCE(θ) = SR(θ) + E [u (F (θ, ξ) − SR(θ))] .

(10)

In the following result, we derive the expression for the gradient of OCE using the expression in eq. (10). Theorem 3 (Gradient of OCE). Suppose the utility function u is twice differentiable, F (·, ξ) is continuously differentiable a.s., and assumptions 1 and 3 hold. Then OCE(·) is continuously differentiable and, for every θ ∈ T , the gradient of OCE is given by ′

∇ OCE(θ) = E [u (F (θ, ξ) − SR(θ)) ∇F (θ, ξ)] . The result above applies to examples 1 to 4, 6 and 7. Using the above gradient expression, we shall establish the smoothness of OCE(θ), and in that spirit, we make the following assumptions.

Assumption 4. There exists M > 0 such that for every θ ∈ T , ∥∇F (θ, ξ)∥2 ≤ M a.s. Assumption 5. There exists L > 0 such that, ∀θ1 , θ2 ∈ T , ∥∇F (θ1 , ξ) − ∇F (θ2 , ξ)∥2 ≤ L ∥θ1 − θ2 ∥2 a.s.. For classification and regression applications (see examples 9 and 10) as well as the uncertainty quantification application in Example 11, assumption 4 is satisfied with a bounded input space (∥x∥ ≤ M1 , ∀x ∈ X) and bounded parameter space (∥θ∥ ≤ M2 , ∀θ ∈ Θ). Further, assumption 5 is satisfied in classification/regression examples under an affine parameterization, and a neural network parameterization with smooth activation functions. Finally, for Example 11, we note that in addition to the boundedness assumptions of input space and parameter space, a lower bound on 2 the variance, i.e., σθ2 ≥ σmin > 0, ∀θ ∈ Θ, ensures Assumption 5 is satisfied. The following result establishes smoothness of OCE(·). Lemma 4. Suppose Assumption 5 and the assumptions of Theorem 3 are satisfied. Then OCE(·) is L-smooth. The following result shows that OCE is strongly convex. Lemma 5. Suppose F (·, ξ) is µ-strongly convex w.p. 1, and the assumptions of Theorem 3 are satisfied. Then OCE(·) is µ-strongly convex. OCE Gradient estimator. From the gradient expression in Theorem 3, it is evident that to estimate the gradient of OCE, we also need to estimate SR(θ). We define the functions m d SRθm : Rm → R and Qm θ : R → R for a given θ ∈ T , as follows: For any z ∈ Rm ,   m   X 1 SRθm (z) ≜ min t ∈ R u′ (F (θ, zj ) − t) ≤ 1 ,   m j=1

(11) Qm θ (z) ≜

m X

1 u′ (F (θ, zj ) − SRθm (z)) ∇F (θ, zj ). m j=1 (12)

Let Z be an m-dimensional vector such that each Zj is an i.i.d. copy of ξ. Then, SRθm (Z) and Qm θ (Z) are our proposed estimators of SR(θ) and ∇ OCE(θ) respectively. Next, we restate Assumption 2 using F and θ. Assumption 6. There exists σ1 > 0 such that Var (u′ (F (θ, ξ) − SR(θ))) ≤ σ12 , for every θ ∈ T . The following assumption is made to bound the variance of the gradient, and it is common to the non-asymptotic analysis of stochastic gradient algorithms, cf. (Nemirovski et al. 2009; Ghadimi and Lan 2012). Assumption 7. There exists T > 0 such that ∥Yθ − E [Yθ ]∥L2 ≤ T, for every θ ∈ T , where Yθ ≜ u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ), ∀θ ∈ Θ. The result below provides bounds on the MSE and MAE of the OCE gradient estimator defined by (12).

Lemma 6. Suppose the assumptions of Theorem 3 and assumptions 4, 6 and 7 are satisfied. Then for every m ∈ N and θ ∈ T ⊆ Rd , we have M σ1 + T √ , m h i 2(M σ 2 + T 2 ) 2 1 , E ∥Qm θ (Z) − ∇ OCE(θ)∥2 ≤ m where M, T and σ1 are given in assumptions 4, 6 and 7. E [∥Qm θ (Z) − ∇ OCE(θ)∥2 ] ≤

SG Algorithm for OCE optimization. We now describe our proposed OCE-SG algorithm for solving eq. (8). The pseudocode of this algorithm is provided in Section D of the supplementary material. In each iteration k of our algorithm, we obtain mk samples from ξ to form Zk and perform the following update:   k k θk = ΠΘ θk−1 − αk Qm (13) θk−1 (Z ) , k ≥ 1, where ΠΘ : Rd → Θ is a non-expansive projection operator, k Qm θk−1 is as defined in eq. (12) and αk is the step size at iteration k. The following result establishes a non-asymptotic bound on the OCE-SG iterates across three regimes: strongly convex, convex, and non-convex. Theorem 7. Suppose the assumptions of Theorem 3 and assumptions 4 to 7 are satisfied. Suppose the minimizer θ∗ defined in eq. (8) satisfies ∇ OCE(θ∗ ) = 0. Strongly-convex case: Suppose the OCE objective OCE(·) is µ-strongly convex on Θ for some µ > 0. Set αk = kc , mk = k, ∀k, where c > µ1 . Then, θn , governed by eq. (13), satisfies i h C1 2 E ∥θn − θ∗ ∥2 ≤ . n+1 Convex case: Suppose OCE(·) is convex on Θ. Suppose iterates (θ1 , . . . , θn ) are governed Pn by eq. (13) with αk = 1 √ , mk = k, ∀k. Let θ n = 1 k=1 θk . Then, n K k   C2 E OCE(θn ) − OCE(θ∗ ) ≤ √ . n Non-convex case: Suppose the iterates (θ1 , . . . , θn ) are gov1 erned by eq. (13) with αk = L√ , mk = k, ∀k, then k   C3 2 E min ∥∇ OCE(θk−1 )∥2 ≤ √ . n k∈[1,n] Here, K is as defined in Lemma 4, and the constants C1 , C2 and C3 are given in Section D of the supplementary material. Recall that the OCE gradient is biased, and this bias is controlled using the batch sizes mk . To produce an any-time algorithm using eq. (13), we need an increasing batch size which diminishes this bias and leads to convergence rates that decrease with each iteration k. If the horizon N is known, then a fixed batch size of mk = N suffices. When working with a fixed dataset of size M , a fixed batch size of mk = m leads to convergence rates of O (1/m), which follow using arguments that are identical to those made in the proof of Theorem 7, and we avoid stating a separate result.

Remark 2. Portfolio optimization in example 8 does not satisfy Assumption 5 and Assumption 4. However, results similar to Lemmas 4 and 6 can be obtained using the linearity of F and a sub-Gaussianity assump2 tion for h∥∇F (θ, ξ)∥2 to infer a bound of the following i √ 2 m form: E ∥Qθ (Z) − ∇ OCE(θ)∥2 ≤ O (1/ m). Thus, the bounds in Theorem 7 apply to Example 8, see Appendix C.5 for the details.

Simulation Experiments We conduct several experiments to test the performance of the OCE estimation and optimization algorithms proposed in this work. Due to space limitations, the detailed experimental setup and additional results are provided in Section E of the supplementary material. Table 2: Performance of NN models minimized on three OCE optimization criteria: entropic risk, CVaR, and Monotone Mean Variance (MMV), against benchmark algorithms on a classification task with the UCI Heart Disease Dataset. Model

Acc.

F1

ECE

AUROC

Logistic Reg. Random Forest NN BCE Loss

0.8444 0.8556 0.8556

0.8250 0.8395 0.8395

0.1050 0.1198 0.0980

0.9439 0.9293 0.9415

Entropic Risk CVaR MMV Risk

0.8556 0.8778 0.8667

0.8395 0.8736 0.8500

0.1089 0.3721 0.1192

0.9504 0.9444 0.9479

Table 3: Performance of NN models minimized on three OCE optimization criteria: entropic risk, SCVaR, and MMV risk, against benchmark algorithms on a classification task with the Breast Cancer Detection dataset. Model

Acc.

F1

ECE

AUROC

Logistic Reg. Random Forest NN BCE Loss

0.9883 0.9357 0.9532

0.9907 0.9488 0.9619

0.0324 0.0430 0.0437

0.9981 0.9913 0.9908

Entropic risk Smooth CVaR MMV Risk

0.9591 0.9883 0.9649

0.9668 0.9907 0.9717

0.0213 0.0239 0.0263

0.9950 0.9963 0.9956

Classification (Example 9) We consider a two-layer neural network (NN) parameterization for the UCI Heart Disease (UCI-HD) dataset (Janosi et al. 1989). We learn OCEoptimal NN parameters using the OCE-SG algorithm. We benchmark them against logistic regression, random forest, and an NN optimized for the binary cross-entropy (BCE) loss. Table 2 shows the performance of these algorithms, evaluated across four well-known classification metrics: accuracy, F1-score, ECE (Expected Calibration Error), and AUROC (Area Under the Receiver Operating Characteristic). From Table 2, we observe that the OCE models achieve higher

Table 4: Comparison of portfolios given by Algorithm 2 for CVaR variants in examples 5 to 7 against a CVaR solver of skfolio library.

200.00%

Portfolios Benchmark - HRP Benchmark - Equal Weights 150.00%

Benchmark - Sharpe

Cumulative returns

Entropic Risk

Portfolio

CVaR Risk Leaky CVaR Risk

CVaR

CDaR

Sharpe

0.1250 0.1261 0.1619 0.2135

0.0239 0.0239 0.0258 0.0348

0.1561 0.1544 0.1350 0.2681

0.7639 0.7713 0.9209 0.8466

CVaR (solver) CVaR (OCE) LCVaR (OCE) SCVaR (OCE)

Smooth CVaR Risk

100.00%

Ann. Ret.

MV Risk Mono-MV Risk Quartic Risk

50.00%

Table 5: Risk and Return Metrics

0.00%

2015

2016

2017

2018

2019

2020

2021

2022

Time

Figure 1: Performance of OCE-SG algorithm for a variety of OCE risk measures in a portfolio optimization application sourced from the S&P stock market data. accuracy, F1, and AUROC than the rest on UCI-HD dataset. We conduct a similar experiment on the Breast Cancer Detection (BCD) dataset (Wolberg et al. 1993). From Table 3, we observe that the OCE models achieve the lowest ECE, and show comparable performance on the remaining metrics. Portfolio optimization (Example 8). With OCE(θ) ≜ OCEu (F (θ, ξ)), we obtain OCE-optimal portfolio allocations under three choices of asset returns ξ, corresponding to the stock markets S&P, NASDAQ and the FTSE. Using data sourced from these stock markets, we obtain portfolio allocations for each OCE instance given in examples 1 to 7 and compare them against three classical benchmark portfolios: equal weighted, maximum Sharpe ratio, and Hierarchical Risk Parity (HRP). A comprehensive analysis is provided in Section E of the supplementary material. Figure 1 captures the performance on the S&P dataset and we observe that the OCE-optimal portfolios outperform the benchmarks, demonstrating that OCE is a viable optimization metric and that our gradient-based optimization scheme is a compelling candidate for optimizing OCE. CVaR Optimization. Borrowing the OCE-optimal portfolio allocations from the previous experiment, we focus on the three OCE variants related to the CVaR risk, i.e., examples 5 to 7. We compare their performance with a CVaRoptimal portfolio generated by a solver in the skfolio library. We evaluate the performance of these portfolios using four well-known risk metrics: annualized returns, CVaR, Conditional Drawdown-at-Risk (CDaR), and the Sharpe ratio. We observe from Table 4 that i) for the utility function in Example 5, the OCE-SG algorithm gives a portfolio that has identical score on the CVaR metric, but marginally better scores on all other metrics, in comparison to the CVaRoptimal portfolio given by the solver, and ii) our proposed CVaR variants serve as viable alternatives, taking into account all the performance metrics. Uncertainty quantification. Consider the objective F (θ, ξ) for the MVE framework given in Example 11. We

Table 6: Comparison of our MVE with OCE approach against vanilla MVE and deep ensembles across the metrics: Mean Absolute Calibration Error (MACE), Root Mean Squared Calibration Error (RMSCE), and Miscalibration Area (MA). Algorithm

MACE

RMSCE

MA

Deep Ensembles

0.0772

0.0883 3

0.0780

MVE

0.0718

0.0815

0.0724

MVE with OCE

0.0285

0.0367

0.0283

modify the MVE’s loss E [F (θ, ξ)] by replacing the expectation with the OCE risk criterion OCE(·), where u is the exponential utility function. Using a simple heterogeneous regression dataset, we compare the model obtained by minimizing the OCE against two benchmarks: the original MVE solution and the state-of-the-art Deep ensembles (Lakshminarayanan, Pritzel, and Blundell 2017). The results are presented in Table 6, and we observe that our approach significantly outperforms both the benchmarks and is a viable alternative for quantifying model uncertainty.

Conclusions We proposed estimators for OCE and its gradient and provided non-asymptotic bounds on the MAE and MSE of these estimators for both Lipschitz and non-Lipschitz utility functions. Our proposed OCE gradient estimator is based on the OCE gradient expression we derive. We used this estimator to devise an SG algorithm to optimize the OCE of a parametrized loss r.v. and to provide non-asymptotic convergence bounds. Finally, we presented simulation experiments to demonstrate the performance of our proposed algorithms.

References Acerbi, C.; and Tasche, D. 2002. On the coherence of expected shortfall. Journal of Banking & Finance, 26(7): 1487– 1503. Artzner, P.; Delbaen, F.; Eber, J.; and Heath, D. 1999. Coherent Measures of Risk. Mathematical Finance, 9(3): 203–228. Basak, S.; and Shapiro, A. 2015. Value-at-Risk-Based Risk Management: Optimal Policies and Asset Prices. The Review of Financial Studies, 14(2): 371–405. Ben-Tal, A.; and Teboulle, M. 1986. Expected Utility, Penalty Functions, and Duality in Stochastic Nonlinear Programming. Management Science, 32(11): 1445–1466. Ben-Tal, A.; and Teboulle, M. 2007. An Old-New Concept of Convex Risk Measures: The Optimized Certainty Equivalent. Mathematical Finance, 17(3): 449–476. Föllmer, H.; and Schied, A. 2016. Stochastic finance. de Gruyter. Föllmer, H.; and Schied, A. 2004. Stochastic Finance: An Introduction in Discrete Time. Berlin, Boston: De Gruyter. Ghadimi, S.; and Lan, G. 2012. Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework. SIAM Journal on Optimization, 22(4): 1469–1492. Ghosh, A.; Prashanth, L. A.; and Jagannathan, K. 2024. Concentration Bounds for Optimized Certainty Equivalent Risk Estimation. arXiv:2405.20933. Gupte, S.; Prashanth, L. A.; and Bhat, S. P. 2024. Optimization of Utility-based Shortfall Risk: A Non-asymptotic Viewpoint. In 2024 IEEE 63rd Conference on Decision and Control (CDC), 1075–1080. Hamm, A.-M.; Salfeld, T.; and Weber, S. 2013. Stochastic root finding for optimized certainty equivalents. In 2013 Winter Simulations Conference (WSC), 922–932. Hegde, V.; Menon, A. S.; Prashanth, L.; and Jagannathan, K. 2024. Online Estimation and Optimization of Utility-Based Shortfall Risk. Mathematics of Operations Research. Hu, Z.; and Zhang, D. 2018. Utility-based shortfall risk: Efficient computations via Monte Carlo. Naval Research Logistics (NRL), 65(5): 378–392. Hurwicz, L.; and Richter, M. K. 2003. Implicit functions and diffeomorphisms without C 1 . In Advances in Mathematical Economics, volume 5, 65–96. Tokyo: Springer. Janosi, A.; Steinbrunn, W.; Pfisterer, M.; and Detrano, R. 1989. Heart Disease. UCI Machine Learning Repository. Jorion, P. 1997. Value at Risk: The New Benchmark for Controlling Market Risk. McGraw-Hill. Kuhn, D.; Shafiee, S.; and Wiesemann, W. 2025. Distributionally robust optimization. Acta Numerica, 34: 579–804. Lakshminarayanan, B.; Pritzel, A.; and Blundell, C. 2017. Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc. N. Fournier. 2023. Convergence of the empirical measure in expected wasserstein distance: non-asymptotic explicit bounds in Rd. ESAIM: PS, 27: 749–775.

Natarajan, K.; Sim, M.; and Uichanco, J. 2010. Tractable robust expected utility and risk models for portfolio optimization. Mathematical Finance: An International Journal of Mathematics, Statistics and Financial Economics, 20(4): 695–731. Nemirovski, A.; Juditsky, A.; Lan, G.; and Shapiro, A. 2009. Robust Stochastic Approximation Approach to Stochastic Programming. SIAM Journal on Optimization, 19(4): 1574– 1609. Nesterov, Y. 2004. Introductory Lectures on Convex Optimization, volume 87 of Applied Optimization. Boston, MA: Springer US. Nix, D.; and Weigend, A. 1994. Estimating the mean and variance of the target probability distribution. In Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN’94), 55–60 vol.1. Orlando, FL, USA: IEEE. Panaretos, V. M.; and Zemel, Y. 2020. An invitation to statistics in Wasserstein space. SpringerBriefs in Probability and Mathematical Statistics. Cham: SpringerOpen. Prashanth, L.; and Bhat, S. P. 2022. A Wasserstein Distance Approach for Concentration of Empirical Risk Estimates. Journal of Machine Learning Research, 23(238): 1–61. Rahimian, H.; and Mehrotra, S. 2022. Frameworks and Results in Distributionally Robust Optimization. Open Journal of Mathematical Optimization, 3: 4. Shapiro, A.; Dentcheva, D.; and Ruszczynski, A. 2021. Lectures on Stochastic Programming: Modeling and Theory, Third Edition. Society for Industrial and Applied Mathematics. Shreve, S. 2004. Stochastic Calculus for Finance II: Continuous-Time Models. Number v. 11 in Springer Finance Textbooks. Springer. Sluijterman, L.; Cator, E.; and Heskes, T. 2024. Optimal training of Mean Variance Estimation neural networks. Neurocomputing, 597: 127929. Tamtalini, A.; Matoussi, A.; and Kaakai, S. 2022. Multivariate Optimized Certainty Equivalent Risk Measures and their Numerical Computation. Working paper or preprint. Vershynin, R. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 1 edition. von Neumann, J.; and Morgenstern, O. 1944. Theory of Games and Economic Behavior. princeton, first edition. Wainwright, M. J. 2019. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 1 edition. Wolberg, W.; Mangasarian, O.; Street, N.; and Street, W. 1993. Breast Cancer Wisconsin (Diagnostic). UCI Machine Learning Repository. Černý, A.; Maccheroni, F.; Marinacci, M.; and Rustichini, A. 2012. On the computation of optimal monotone mean–variance portfolios via truncated quadratic utility. Journal of Mathematical Economics, 48(6): 386–395.

Organization of the supplementary material In Section A, we provide proofs related to the results that characterize the OCE risk for unbounded r.v.s. In Section B, we provide proofs for results related to OCE estimation, while in Section C, we provide proofs for the results related to OCE optimization. In Section D, we provide the pseudocode for the OCE-SG Algorithm and subsequently provide complete proofs on the convergence guarantees of the algorithm in all three regimes, strongly-convex, convex, and non-convex. Finally, in Section E, we provide a comprehensive analysis details of the simulation experiments reported in the main paper, and also include more simulation experiments.

A A.1

Characterization of the OCE risk measure

Proof of Proposition 1

Proof. Putting l = u′ and λ = 1 in Definition 3, we observe that SRu′ ,1 (X) is a solution to eq. (2), and therefore, SRu′ ,1 (X) is a root of G′X (·). This implies that SRl,λ (X) is also a minimizer of GX (·) and therefore, we substitute t∗ in eq. (3) with SRu′ ,1 (X), and we have OCEu (X) = SRu′ ,1 (X) + E [u(X − SRu′ ,1 (X)] . (14) Next, we show that OCEu (·) is a convex risk measure. Monotonicity. Let X1 , X2 ∈ X̄u such that X1 ≤ X2 a.s. From the claim in (14), SRu′ ,1 (X1 ) is a minimizer of GX1 (·), and therefore it follows that GX1 (SRu′ ,1 (X1 )) ≤ GX1 (t) , ∀t ∈ R. Then substituting t = SRu′ ,1 (X2 ), we have OCEu (X1 ) = GX1 (SRu′ ,1 (X1 )) ≤ GX1 (SRu′ ,1 (X2 )) = SRu′ ,1 (X2 ) + E [u(X1 − SRu′ ,1 (X2 ))] ≤ SRu′ ,1 (X2 ) + E [u(X2 − SRu′ ,1 (X2 ))] = OCEu (X2 ), where the final inequality follows because X1 ≤ X2 a.s. and u is increasing. This proves monotonicity of OCEu (·). Cash-invariance.

Let X ∈ X̄u and m ∈ R. Then, OCEu (X + m) = SRu′ ,1 (X + m) + E [u(X − m − SRu′ ,1 (X + m))] = SRu′ ,1 (X) + m + E [u(X − SRu′ ,1 (X))] = OCEu (X) + m,

where the second equality holds due to cash-invariance property of SRu′ ,1 (·), cf. (Gupte, Prashanth, and Bhat 2024, Proposition 2). This proves cash-invariance of the OCEu (·). Convexity. Let α ∈ [0, 1] and denote Xα ≜ αX1 + (1 − α)X2 . Then by Proposition 1, SRu′ ,1 (Xα ) is a minimizer of GXα (·), and hence GXα (SRu′ ,1 (Xα )) ≤ GXα (t), ∀t ∈ R. Then, with t = α SRu′ ,1 (X1 ) + (1 − α) SRu′ ,1 (X2 ), we have OCEu (Xα ) = GXα (SRu′ ,1 (Xα )) ≤ GXα (α SRu′ ,1 (X1 ) + (1 − α) SRu′ ,1 (X2 )) = α SRu′ ,1 (X1 ) + (1 − α) SRu′ ,1 (X2 ) + E [u(Xα − α SRu′ ,1 (X1 ) − (1 − α) SRu′ ,1 (X2 ))] ≤ α SRu′ ,1 (X1 ) + (1 − α) SRu′ ,1 (X2 ) + αE [u(X1 − SRu′ ,1 (X1 ))] + (1 − α)E [u(X2 − SRu′ ,1 (X2 ))] = α OCEu (X1 ) + (1 − α) OCEu (X2 ), where the first and second inequalities follow from the convexity of GXα and u, respectively. This proves the convexity of OCEu (·).

A.2

Wasserstein Distance Bound on OCE.

The following result provides a bound on the difference between the OCE risk value of two r.v.s. X and Y in terms of the 2-Wasserstein distance between the corresponding marginal distributions µX and µY . Lemma 8. Let X, Y ∈ X̄u ∩ L2 , and suppose that assumptions 1 and 2, and the assumptions of Proposition 1 are satisfied. Then, q |OCEu (X) − OCEu (Y )| ≤ W2 (µX , µY ) σ12 + 1. Proof. Recall that H(µX , µY ) denotes the set of all joint distributions whose marginals are µX and µY . Note from the assumptions of the lemma that the r.v.s. X, Y ∈ X̄u have finite 2nd moment. Then by definition of W2 as the infimum, it follows that for every ϵ > 0, there exists η ′ (ϵ) ∈ H(µX , µY ) such that following holds. h i 2 W22 (µX , µY ) > Eη′ (ϵ) |X − Y |2 − ϵ. (15)

Fix ϵ > 0. W.L.O.G., consider the case where OCEu (X) ≥ OCEu (Y ). Then, we have |OCEu (X) − OCEu (Y )| = SRu′ ,1 (X) − SRu′ ,1 (Y ) + E [u (X − SRu′ ,1 (X))] − E [u (Y − SRu′ ,1 (Y ))] = SRu′ ,1 (X) − SRu′ ,1 (Y ) + Eη′ (ϵ) [u (X − SRu′ ,1 (X)) − u (Y − SRu′ ,1 (Y ))] ≤ SRu′ ,1 (X) − SRu′ ,1 (Y ) + Eη′ (ϵ) [u′ (X − SRu′ ,1 (X)) (SRu′ ,1 (Y ) − SRu′ ,1 (X) + X − Y )] ≤ Eη′ (ϵ) [u′ (X − SRu′ ,1 (X)) (X − Y )] r q h i q 2 ≤ E [u′ (X − SRu′ ,1 (X))2 ] Eη′ (ϵ) |X − Y | < σ12 + 1 W22 (µX , µY ) + ϵ, where the first inequality is due to the convexity of u. The second inequality follows from the fact that E [u′ (X − SRu′ ,1 (X))] = 1 and the second inequality holds for any arbitrary choice of ϵ. The third inequality follows from the Cauchy-Schwartz inequality. The final inequality follows from the variance assumption of the lemma and eq. (15). Since ϵ was chosen to be arbitrary, the claim of the lemma follows. In Lemma 12 of Prashanth and Bhat (2022), the authors obtained a bound similar to Lemma 8 in terms of the 1-Wasserstein distance (between marginals µX and µY ) under the assumption that the utility function is Lipschitz. In Lemma 8, we extend the result to possibly non-Lipschitz utility functions by replacing the Lipschitz assumption with a variance assumption and provide a bound in terms of the 2-Wasserstein distance between the marginal distributions µX and µY . This extension covers examples 1 to 4, which includes popular OCE instances with non-Lipschitz utility functions.

B B.1

OCE estimation

Proof for Lemma 1

Proof. Let µ denote the distribution of X. Choose z ∈ Rm and let µm (z) denote the measure having a mass 1/m at each of the points z1 , z1 , . . . , zm . Further, let X̂m (z) denote the r.v. which takes values z1 , z1 , . . . , zm with probability 1/m each. Then it is clear that z is a collection of samples of X̂m (z) and µm (z) is the associated empirical measure. Recall SRm (z) defined in (4) and GX (t) ≜ t + E [u(X − t)]. Then by Proposition 1, SRu′ ,1 (X) is a minimizer of GX (·) and therefore, GX (SRu′ ,1 (X)) ≤ GX (SRm (z)), i.e., SRu′ ,1 (X) + E [u(X − SRu′ ,1 (X))] ≤ SRm (z) + E [u(X − SRm (z))] . (16) P m 1 Consider a convex function Ĝz (t) ≜ t + m j=1 u(zj − t). It is easy to see from (4) that SRm (z) is a minimizer of Ĝz (·), and we have m m 1 X 1 X SRm (z) + u(zj − SRm (z)) ≤ SRu′ ,1 (X) + u(zj − SRu′ ,1 (X)). (17) m j=1 m j=1 We now derive the error bounds. Recall the definition of OCEu (X) given by Proposition 1 and the definition of OCEm given in (5). Consider the case when OCEm (z) ≥ OCEu (X). Then, we have m

OCEm (z) − OCEu (X) = SRm (z) − SRu′ ,1 (X) +

1 X u (zj − SRm (z)) − E [u (X − SRu′ ,1 (X))] m j=1

m

1 X u(zj − SRu′ ,1 (X)) − E [u (X − SRu′ ,1 (X))] m j=1 h  i  h  i  = E u −X̂m (z) − SRu′ ,1 (X) − E [u (X − SRu′ ,1 (X))] = K E u1 X̂m (z) − E [u1 (X)] ,

≤

(18)

where u1 (t) ≜ K −1 u(−t − SRu′ ,1 (X)), ∀t ∈ R, and the first inequality above follows from (17). Since u1 is 1-Lipschitz, by Kantorovich–Rubinstein Theorem (cf. Section 1.8.2 of Panaretos and Zemel (2020)), OCEm (z) − OCEu (X) is bounded above by KW1 (µm (z), µ). For the other case: OCEm (z) < OCEu (X), we have m

OCEu (X) − OCEm (z) = SRu′ ,1 (X) − SRm (z) + E [u (X − SRu′ ,1 (X))] − m

1 X u (zj − SRm (z)) m j=1

1 X u (zj − SRm (z)) m j=1 h  i  h  i = E [u (X − SRm (z))] − E u −X̂m (z) − SRm (z) = K E [u2 (X)] − E u2 X̂m (z) , ≤ E [u (X − SRm (z))] −

where u2 (t) ≜ K −1 u(−t − SRm (z)), ∀t ∈ R, and the first inequality follows from (16). Since u2 is 1-Lipschitz, by Kantorovich–Rubinstein Theorem (cf. Section 1.8.2 of Panaretos and Zemel (2020)), OCEu (X) − OCEm (z) is bounded above by KW1 (µ, µm (z)). Combining the two cases, we have |OCEm (z) − OCEu (X)| ≤ KW1 (µm (z), µ). Since z was chosen to be arbitrary, it follows that the above holds w.p. 1 with z replaced by the random vector Z. Then, |OCEm (Z) − OCEu (X)| ≤ KW1 (µm (Z), µ).

(19)

Taking expectation on both sides of (19), we have 39KT E [|OCEm (Z) − OCEu (X)|] ≤ KE [W1 (µm (Z), µ)] ≤ √ . m where the last inequality follows by invoking the Theorem 2.1 of N. Fournier (2023). With p, d, m and q from the notation of the Theorem 2.1 in (N. Fournier 2023), we invoke the theorem with p = 1, d = 1, m = 1, q = 3 to get the following bound: √ . In a similar manner, first squaring both sides in (19) and then taking expectation E [W1 (µm (Z), µ)] = E [T1 (µm (Z), µ)] ≤ 39T m on both sides, we have h i     108K 2 T 2 2 √ E |OCEm (Z) − OCEu (X)| ] ≤ K 2 E W12 (µm (Z), µ) ≤ E W22 (µm (Z), µ) ≤ . m The second inequality above follows from the monotonicity of the Wasserstein distance (Panaretos and Zemel 2020, eq 2.1), while the last inequality follows by invoking the Theorem 2.1 of (N. Fournier 2023) with p = 2, d = 1, m = 1, q = 5 to   2 √ get E W22 (µm (Z), µ) = E [T2 (µm (Z), µ)] ≤ 108T . The bound on Tp applies if the higher-moment bound ∥X∥Lq ≤ T is m satisfied for some q > 2p. Therefore, for the MAE bound (p = 1), we assume that the higher-moment bound is satisfied for some q > 2, and for the MSE bound (p = 2), we assume that the higher-moment bound is satisfied for some q > 4. This concludes the proof of Theorem 1.

B.2

Proof for Lemma 2

Proof. Choose z ∈ Rm . Recall SRm (z) defined in (4). Recall the definitions X̂m (z) from the proof of Theorem 1 in Section B.1. Consider the case: OCEm (z) < OCEu (X), we have m

OCEu (X) − OCEm (z) = SRu′ ,1 (X) − SRm (z) + E [u (X − SRu′ ,1 (X))] −

1 X u (zj − SRm (z)) m j=1

Recall that µ denotes the distribution of X, and µm (z) is the empirical measure associated with r.v. X̂m (z). Suppose H(µm (z), µ) denotes the set of all joint distributions whose marginals are µm (z) and µ. Then for every η ∈ H(µm (z), µ), we have h  i OCEm (z) − OCEu (X) ≤ SRu′ ,1 (X) − SRm (z) + Eη u (X − SRu′ ,1 (X)) − u X̂m (z) − SRm (z) . From the higher moment assumption on X and the definition of X̂m (z), it is easy to see that the r.v.s. X, X̂m (z) ∈ X̄u and have finite 2nd moment. Then by definition of W2 as the infimum, it follows that for every ϵ > 0, there exists η(ϵ) ∈ H(µm (z), µ) such that following holds.   2 W22 (µm (z), µ) > Eη(ϵ) X − X̂m (z) − ϵ. (20) 2

Fix ϵ > 0. Then, from (20) we have h  i OCEu (X) − OCEm (z) = SRu′ ,1 (X) − SRm (z) + Eη(ϵ) u (X − SRu′ ,1 (X)) − u X̂m (z) − SRm (z) h  i ≤ SRu′ ,1 (X) − SRm (z) + Eη(ϵ) u′ (X − SRu′ ,1 (X)) X − SRu′ ,1 (X) − X̂m (z) + SRm (z) h  i = Eη(ϵ) u′ (X − SRu′ ,1 (X)) X̂m (z) − X s r h   q q i 2 2 Eη(ϵ) X − X̂m (z) < σ12 + 1 W22 (µm (z), µ) + ϵ. ≤ E u′ (X − SRu′ ,1 (X)) Since ϵ was chosen arbitrarily, we have OCEm (z) − OCEu (X) ≤

q

σ12 + 1

q W22 (µm (z), µ).

For the case: OCEm (z) ≥ OCEu (X), using parallel arguments to those above, we get the same bound as above. Combining the two cases, we have q q (21) |OCEm (z) − OCEu (X)| ≤ σ12 + 1 W22 (µm (z), µ) Since z was chosen to be arbitrary, it follows that the above holds w.p. 1 with z replaced by the random vector Z. Then, replacing z with Z and taking expectation on both sides, we have q  q  q q 2 2 E [|OCEm (Z) − OCEu (X)|] ≤ σ1 + 1 E W2 (µm (Z), µ) ≤ σ12 + 1 E [W22 (µm (Z), µ)].   √ The final inequality follows from the Cauchy-Schwarz inequality. Using E W22 (µm (Z), µ) ≤ 108T by the Theorem 2.1 of (N. m Fournier 2023) yields the first bound of the lemma. The second bound of the lemma follows by a similar argument, by first squaring on both sides of eq. (21) and then taking the expectation.

B.3

Algorithm for OCE estimation

Algorithm 1: OCE-SB (Search and Bisect) Input : thresholds δ, ϵ > 0, i.i.d. samples {Zi }m i=1 Pm ′ 1 Define : ĝ(t) ≜ m u (−Z − t) − 1 i i=1 if ĝ(0) > 0 then low, high ← −1, 0 else low, high ← 0, 1; while ĝ(high) > 0 do high ← 2 ∗ high; while ĝ(low) < 0 do low ← 2 ∗ low; T ← high - low, t̂m ← (low + high)/2; while T > 2δ or ĝ(t̂m ) > ϵ do if ĝ(t̂m ) > 0 then low ← t̂m else high ← t̂m ; T ← high - low, t̂m ← (low + high)/2; Output : t̂m Proposition 2. Suppose the utility function u is continuously differentiable and satisfies the assumptions of Proposition 1. Let ŝm be an approximate solution to eq. (4) given by eq. (7) with the inputs Z, δ > 0 and ϵ > 0. , we have E[|ŝm (Z) − OCEu (X)|] ≤ δϵ + E [|OCEm (Z) − OCEu (X)|] , and h i 2 2 E[(ŝm (Z) − OCEu (X)) ] ≤ 2δ 2 ϵ2 + 2E |OCEm (Z) − OCEu (X)| . Proof. Choose z ∈ Rm , let t̂m (z) denote the approximation of SRm (z) obtained by Algorithm 1 or any. Then the following holds. t̂m (z) − SRm (z) ≤ δ, and

m
1 X ′ u zj − t̂m (z) − 1 ≤ ϵ. m j=1

Using same z, eq. (7) returns ŝm (z) as an estimate for OCEu (X), where m
1 X ′ u zj − t̂m (z) . ŝm (z) ≜ t̂m (z) + m j=1 Suppose ŝm (z) ≥ OCEu (X). Then we have |ŝm (z) − OCEu (X)| = t̂m (z) − SRu′ ,1 (X) +

m  1 X u(zj − t̂m (z)) − E [u (X − SRu′ ,1 (X))] m j=1

= t̂m (z) − SRm (z) + SRm (z) − SRu′ ,1 (X) +

m m  1 X 1 X u(zj − t̂m (z)) − [u(zj − SRm (z)] m j=1 m j=1

m

1 X + [u(zj − SRm (z)] − E [u (X − SRu′ ,1 (X))] m j=1   m   1 X
≤ SRm (z) − t̂m (z)  u′ zj − t̂m (z) − 1 + OCEm (z) − OCEu (X) ≤ δϵ + OCEm (z) − OCEu (X). m j=1

(22)

Here, the first inequality follows from the convexity of u, and the second inequality follows from eq. (22). For the other case: ŝm (z) < OCEu (X), we have m  1 X |ŝm (z) − OCEu (X)| = SRu′ ,1 (X) − t̂m (z) + E [u (X − SRu′ ,1 (X))] − u(zj − t̂m (z)) m j=1 = SRu′ ,1 (X) − SRm (z) + SRm (z) − t̂m (z) + E [u (X − SRu′ ,1 (X))] m m m  1 X 1 X 1 X − [u(zj − SRm (z)] + [u(zj − SRm (z)] − u(zj − t̂m (z)) m j=1 m j=1 m j=1 m

≤ OCEu (X) − OCEm (z) + SRm (z) − t̂m (z) +

 1 X ′ u (zj − SRm (z)) t̂m (z) − SRm (z) = OCEu (X) − OCEm (z), m j=1

where equality follows from the continuous differentiability of u. Indeed, if u′ is continuous, then eq. (4) implies that Pmthe last 1 ′ u (z j − SRm (z)) = 1. Combining the two cases, we have j=1 m |ŝm (z) − OCEu (X)| ≤ δϵ + |OCEu (z) − OCEu (X)| 2

2

|ŝm (z) − OCEu (X)| ≤ 2δ 2 ϵ2 + 2 |OCEu (z) − OCEu (X)| . Since z was chosen to be arbitrary, it follows that the above holds w.p. 1 with z replaced by the random vector Z. Then, taking the expectation on both sides, the proposition’s claims follow. Proposition 2 extends the bounds from theorems 1 and 2 to the solution given by eq. (7). Depending on the choice of the utility function u, Proposition 2 may be invoked in tandem with one of the lemmas from Theorems 1 and 2 and the values for δ and ϵ can be chosen to match the respective error rates of the lemma. For √ example, suppose the assumptions of Theorem 1 hold for some T > 0 and K > 0. Then invoking Proposition 2 with δ = 1/ m and ϵ = d2 would yield the following MAE and MSE bounds on the estimator ŝm given by eq. (7): h i 2d2 + 216K 2 T 2 d2 + 39KT 2 √ E [|ŝm (Z) − OCEu (X)|] ≤ , and E |ŝm (Z) − OCEu (X)| ≤ 2 √ . m m Remark 3. Proposition 2 employs the assumption that u is continuously differentiable, which is satisfied by all examples except CVaR in Example 5. Notice that the continuous differentiability of u is only employed in case 2, i.e., ŝm (z) < OCEu (X). In such cases, we can avoid relying on the aforementioned assumption by using an alternative proof technique. We partition case 2 further into three sub-cases: i) ŝm (z) < OCEu (X) ≤ SRm (z) ii) ŝm (z) < SRm (z) < OCEu (X), and iii) SRm (z) ≤ ŝm (z) < OCEu (X). It is easy to see that this leads to an upper bound of ϵ + |OCEu (z) − OCEu (X)| for case 2, and combined with case 1, gives the bound: (δ + 1)ϵ + |OCEu (z) − OCEu (X)|. Thus, even when u is not continuously differentiable, we obtain a bound similar to Proposition 2, with the exception that δ is replaced with δ + 1.

C C.1

OCE Optimization

Proof for Theorem 3

Proof. Recall that SR(θ) ≜ SRu′ ,1 (F (θ, ξ)). Define h : Θ × R → R as h(θ, t) = E [u′ (F (θ, ξ) − t)] − 1. Note that i) h(θ, SR(θ)) = E [u′ (F (θ, ξ) − SR(θ))] − 1 = 0 for every θ ∈ Θ. Since u is twice differentiable and F is continuously differentiable, it implies that ii) h is differentiable on Θ × R. Furthermore, by the theorem assumption of ∀θ ∈ Θ, P (u′′ (F (θ, ξ) − SR(θ)) > 0) > 0, we have E [u′′ (F (θ, ξ) − SR(θ))] for every θ ∈ Θ. This implies that iii) ∂h/∂t < 0 is satisfied at every (θ, SR(θ)). Then (i),(ii), and (iii) satisfy the conditions of Theorem 1 of (Hurwicz and Richter 2003) and therefore, SR(θ) is differentiable, and the partial derivatives are given by ∂h/∂θi ∂ SR(θ) = ∀i ∈ 1, . . . , d. ∂θi ∂h/∂t (θ,SR(θ)) We do not expand the r.h.s. of the above equation as the partial derivatives of SR(θ) get canceled in the following passage. Thus, we require only their existence. Recall the expression for OCE(θ) in eq. (10). Taking partial derivatives w.r.t. θi on both sides of eq. (10), we have    ∂ SR(θ) ∂F (θ, ξ) ∂ SR(θ) ∂ OCE(θ) ′ = − E u (F (θ, ξ) + SR(θ)) − ∂θi ∂θi ∂θi ∂θi   ∂ SR(θ) ∂F (θ, ξ) ′ ′ = [1 − E [u (F (θ, ξ) − SR(θ))]] + E u (F (θ, ξ) − SR(θ)) ∂θi ∂θi   ∂F (θ, ξ) = E u′ (F (θ, ξ) − SR(θ)) , ∂θi

where the final equality follows (i). Since u and F are continuously differentiable, the r.h.s. of the final equality is continuously differentiable, implying that the gradient of OCE(θ) exists and the claim of the theorem follows.

C.2

Proof of Lemma 4

Assumption 5 implies that F and therefore −F is L-smooth a.s. Then by the Theorem 2.1.5 of (Nesterov 2004), for every θ1 , θ2 ∈ Θ, we have T

(−F (θ2 , ξ)) − (−F (θ1 , ξ)) ≤ (−∇F (θ1 , ξ)) (θ2 − θ1 ) +

L 2 ∥θ1 − θ2 ∥ a.s. 2

(23)

Recall that OCE(θ) = SR(θ) + E [u (F (θ, ξ) − SR(θ))]. Then, for every θ1 , θ2 ∈ T , we have OCE(θ1 ) − OCE(θ2 ) = SR(θ1 ) − SR(θ2 ) + E [u (F (θ1 , ξ) − SR(θ1 ))] − E [u (F (θ2 , ξ) − SR(θ2 ))] ≤ SR(θ1 ) − SR(θ2 ) + E [u′ (F (θ1 , ξ) − SR(θ1 )) (SR(θ2 ) − SR(θ1 ) + F (θ1 , ξ) − F (θ2 , ξ))] = E [u′ (F (θ1 , ξ) − SR(θ1 )) (F (θ2 , ξ) − F (θ1 , ξ))]    L 2 ′ T ≤ E u (F (θ1 , ξ) − SR(θ1 )) ∇F (θ1 , ξ) (θ1 − θ2 ) + ∥θ1 − θ2 ∥ 2 L 2 = ∇ OCE(θ1 )T (θ1 − θ2 ) + ∥θ1 − θ2 ∥ . 2 Here, the first inequality follows from the convexity of u, while the second equality follows by definition of SR(θ1 ), which for a continuously differentiable u implies that E [u′ (F (θ1 , ξ) − SR(θ1 ))] = 1. The last inequality follows from eq. (23). Then by the Theorem 2.1.5 of (Nesterov 2004), OCE(·) is L-smooth.

C.3

Proof of Lemma 5

From the assumptions of the lemma, we note that F is continuously differentiable and µ-strongly convex w.p. 1. Then by (Nesterov 2004, Definition 2.1.2), and F is µ-strongly convex w.p. 1, i.e., for every θ1 , θ2 ∈ Θ, we have F (θ1 , ξ) ≥ F (θ2 , ξ) + ∇F (θ2 , ξ)T (θ1 − θ2 ) +

µ 2 ∥θ1 − θ2 ∥ , 2

w.p. 1.

(24)

Recall that OCE(θ) = SR(θ) + E [u (F (θ, ξ) − SR(θ))]. Then, for every θ1 , θ2 ∈ T , we have OCE(θ1 ) − OCE(θ2 ) = SR(θ1 ) − SR(θ2 ) + E [u (F (θ1 , ξ) − SR(θ1 ))] − E [u (F (θ2 , ξ) − SR(θ2 ))] ≥ SR(θ1 ) − SR(θ2 ) + E [u′ (F (θ2 , ξ) − SR(θ2 )) (SR(θ2 ) − SR(θ1 ) + F (θ1 , ξ) − F (θ2 , ξ))] = E [u′ (F (θ2 , ξ) − SR(θ2 )) (F (θ2 , ξ) − F (θ1 , ξ))] h  i µ 2 ≥ E u′ (F (θ2 , ξ) − SR(θ2 )) ∇F (θ2 , ξ)T (θ1 − θ2 ) + ∥θ1 − θ2 ∥ 2 µ 2 = ∇ OCE(θ2 )T (θ1 − θ2 ) + ∥θ1 − θ2 ∥ . 2 The first inequality follows from convexity of u, while the second equality follows because by the definition of SR(θ2 ) which implies that E [u′ (F (θ2 , ξ) − SR(θ2 ))] = 1 holds for a continuously differentiable utility function u. The second inequality follows from eq. (24) while the final equality follows from the gradient expression of OCE. Then by (Nesterov 2004, Definition 2.1.2), OCE is µ-strongly convex.

C.4

Proof for Lemma 6

Proof. Fix m ∈ N , z ∈ Rm and θ ∈ T . Recall that SRθm (z) and Qm θ (z) are estimators of SR(θ) and ∇ OCE(θ) respectively. Then, the following holds for q ∈ {1, 2}. q

m

q ∥Qm θ (z) − ∇ OCE(θ)∥2 =

≤q

1 X ′ u (F (θ, zj ) − SRθm (z)) ∇F (θ, zj ) − E [u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ)] m j=1

m X

1 1 u′ (F (θ, zj ) − SRθm (z)) ∇F (θ, zj ) − u′ (F (θ, zj ) − SR(θ)) ∇F (θ, zj ) m j=1 m j=1

2

q

m

+q

2

q

m X

1 X ′ u (F (θ, zj ) − SR(θ)) ∇F (θ, zj ) − E [u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ)] m j=1

2 q

m X

1 = qI1 + q u′ (F (θ, zj ) − SR(θ)) ∇F (θ, zj ) − E [u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ)] m j=1

.

(25)

2

For bounding I1 , we note the following. q

m

1 X ′ [u (F (θ, zj ) − SR(θ)) − u′ (F (θ, zj ) − SRθm (z))] ∇F (θ, zj ) I1 = m j=1 2  q m X 1 q ≤ max ∥∇F (θ, zj )∥2  |u′ (F (θ, zj ) − SR(θ)) − u′ (F (θ, zj ) − SRθm (z))| j m j=1 q

m

q = max ∥∇F (θ, zj )∥2 j

1 X ′ u (F (θ, zj ) − SR(θ)) − u′ (F (θ, zj ) − SRθm (z)) m j=1

q = max ∥∇F (θ, zj )∥2 j

1 X ′ u (F (θ, zj ) − SR(θ)) − 1 . m j=1

(26)

q

m

q

For obtaining the first inequality, we first apply the Cauchy Schwartz inequality, then replace ∥∇F (θ, zj )∥2 with its maximum over j and finally take the max term outside the summation. The last equality follows from eq. (11). The equality in eq. (26) is unusual, and we provide the following justification. Consider the case: SRθm (z) ≥ SR(θ). Then, m X

|u′ (F (θ, zj ) − SR(θ)) − u′ (F (θ, zj ) − SRθm (z))| =

j=1

m X

u′ (F (θ, zj ) − SR(θ)) − u′ (F (θ, zj ) − SRθm (z)) ,

j=1

where we use the fact that u′ is increasing, which follows from convexity of u. For the other case: SRθm (z) < SR(θ), we note that following holds. m X

|u′ (F (θ, zj ) − SR(θ)) − u′ (F (θ, zj ) − SRθm (z))| =

j=1

m X

u′ (F (θ, zj ) − SRθm (z) − u′ (F (θ, zj ) − SR(θ))) .

j=1

Combining the two cases conclude the proof of the equality in eq. (26). Substituting the bound on I1 back into eq. (25), we have m

q

X q q 1 ∥Qm u′ (F (θ, zj ) − SR(θ)) − 1 θ (z) − ∇ OCE(θ)∥2 ≤ q max ∥∇F (θ, zj )∥2 j m j=1 m

1 X ′ u (F (θ, zj ) − SR(θ)) ∇F (θ, zj ) − E [u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ)] +q m j=1

q

. 2

(27)

The above holds for all z ∈ Rm , and therefore it holds almost surely with z replaced with Z. Applying Assumption 4 and taking expectation on both sides, we have  q m X 1 q q  E [∥Qm u′ (F (θ, Zj ) − SR(θ)) − 1  θ (Z) − ∇ OCE(θ)∥2 ] ≤ qM2 E m j=1  q m X 1 + qE  u′ (F (θ, Zj ) − SR(θ)) ∇F (θ, Zj ) − E [u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ)]  . m j=1 2

Next, we substitute 1 in the above inequality with E

h

Pm 1 m

′ j=1 u (F (θ, Zj ) − SR(θ))

i

because Zj are i.i.d. and by definition

′

of SR(θ) = SRu′ ,1 (F (θ, ξ)), we have E [u (F (θ, ξ) − SR(θ))] = 1. Then, we have  q m X 1 q q  E [∥Qm u′ (F (θ, Zj ) − SR(θ)) − 1  θ (Z) − ∇ OCE(θ)∥2 ] ≤ qM2 E m j=1    q m m X X 1 1 + qE  u′ (F (θ, Zj ) − SR(θ)) ∇F (θ, Zj ) − E  u′ (F (θ, Zj ) − SR(θ)) ∇F (θ, Zj )  . m j=1 m j=1 2

We note that both the terms on the r.h.s. of the above inequality are variances of summations of m i.i.d. terms. Then, replacing variance of a sum with the sum of variances, we have q

E [∥Qm θ (Z) − ∇ OCE(θ)∥2 ] ≤

qM2q q q V ar (u′ (F (θ, ξ) − SR(θ))) + q/2 E [∥Yθ − E [Yθ ]∥2 ] , q/2 m m

where Yθ ≜ u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ). Applying assumptions 2 and 7, the claim of the lemma follows.

C.5

An alternative to Lemma 6

Some optimization objectives (see Example 8) do not satisfy Assumption 4. We derive similar rates as given in Lemma 6 using the following relaxed assumption. 2

Assumption 8. There exists S1 > 0, S2 > 0 such that for every θ ∈ Θ, ∥∇F (θ, ξ)∥2 is sub-Gaussian and satisfies the following for m i.i.d. copies {ξj }m j=1 of ξ:     p p 4 2 E max ∥∇F (θ, ξj )∥2 ≤ S1 log(m) and E max ∥∇F (θ, ξj )∥2 ≤ S2 log(m). j

j

2

4

The inequalities above follow from the sub-Gaussianity of ∥∇F (θ, ξ)∥2 , which also implies that ∥∇F (θ, ξ)∥2 is subexponential. For a precise value of the constants S1 , S2 , see (Wainwright 2019, Chapter 2) or (Vershynin 2018, Chapter 3). A variant of Lemma 6 with Assumption 8 is presented below. Lemma 9. Suppose the assumptions of Theorem 3 and assumptions 6 to 8 are satisfied. Then for every m ∈ N and θ ∈ T ⊆ Rd , we have p σ1 S1 log(m) + T m √ E [∥Qθ (Z) − ∇ OCE(θ)∥2 ] ≤ m h i 4 In addition, if there exists L1 , M1 > 0 such that u′ is L1 -Lipschitz and for every θ ∈ T , E |F (θ, ξ) − E [F (θ, ξ)]| ≤ M1 , then h i  √ 2 3 3  log(m) 2T 2 2 √ E ∥Qm (Z) − ∇ OCE(θ)∥ ≤ σ S + 2 2S2 L1 M1 + . 1 1 θ 2 m m m The above MAE and MSE bounds can be shown to hold when Qm θ (Z) is constructed by replacing SRθ (z) with an m approximation of SRθ (ẑ).

Proof. Fix m ∈ N , z ∈ Rm and θ ∈ T . The proof of this lemma is identical to the proof of Theorem 6 up to eq. (27). The treatment of the second term on the r.h.s. of eq. (27) is also identical, and we omit the details. We focus on bounding the first

q q 1 Pm ′ term on the r.h.s. of eq. (27), i.e. I1 ≜ q maxj ∥∇F (θ, zj )∥2 m j=1 u (F (θ, zj ) − SR(θ)) − 1 . Replacing z in I1 with Z, putting q = 1, and then taking expectation, we have,   m X 1 E max ∥∇F (θ, Zj )∥2 u′ (F (θ, Zj ) − SR(θ)) − 1  j m j=1 v   u s  2 u q p m u  1 X σ1 2 ′ (F (θ, Z ) − SR(θ)) − 1  ≤ ≤ E max ∥∇F (θ, Zj )∥2 u E S1 log(m) √ . u   j t j m j=1 m

For the second claim, we replace z in I1 with Z, put q = 2 and then take expectation to have   2 m X   2 1 E max ∥∇F (θ, Zj )∥2 u′ (F (θ, zj ) − SR(θ)) − 1  j m j=1   4   m X  1  4 ≤ E max ∥∇F (θ, Zj )∥2 E  u′ (F (θ, Zj ) − SR(θ)) − 1  j m j=1  ≤ S22

p

m X

3

m X



1  1  log(m)E  u′ (F (θ, Zj ) − SR(θ)) − 1 u′ (F (θ, Zj ) − SR(θ)) − 1  m j=1 m j=1

v  v   u 2 u 6 u u m m X u u  1 X p    1 u′ (F (θ, Zj ) − SR(θ)) − 1 u u′ (F (θ, Zj ) − SR(θ)) − 1  ≤ S22 log(m)u tE  m tE  m j=1

j=1

v   u 6 u m X u p σ1  1  ≤ S22 log(m) √ u E u′ (F (θ, Zj ) − SR(θ)) − E [u′ (F (θ, ξ) − SR(θ)) ∇F (θ, ξ)]  m j=1 mt ≤ S22

p

σ1 √ 3 log(m) √ 2L1 2M13 . m

D

Algorithm for OCE optimization and its convergence rates

Algorithm 2: OCE-SG Input : θ0 ∈ Θ, batch sizes {mk }k≥1 , step sizes {αk }k≥1 , and number of iterations n. for k = 1, 2, . . . , n do k sample Zk = [Z1k , Z2k , . . . , Zm ] from ξ; k mk k compute SRθ (Z ) using eq. (11); k k compute Qm θk−1 (Z ) using eq. (5);  k k update θk ← ΠΘ θk−1 − αk Qm θk−1 (Z ) ;

D.1

Strongly-convex case

The following result establishes a non-asymptotic bound on the last iterate of Algorithm 2. Theorem 10. Suppose the assumptions of Theorem 3 and assumptions 2, 4, 5 and 7 are satisfied. Suppose the OCE objective OCE(·) is µ-strongly convex on Θ for some µ > 0. Run Algorithm 2 with αk = kc , mk = k, ∀k, where c > µ1 . Then, h i h i E ∥θ0 − θ∗ ∥22 + K1 K2 E [∥θ0 − θ∗ ∥2 ] K3 2 E ∥θn − θ∗ ∥2 ≤ + , + (n + 1)2 n+1 (n + 1)3/2 where the constants K1 , K2 and K3 are independent of n. Proof. We split the proof into three parts. In Part I, we derive some intermediate results that are applied in the later parts of the proof. In part II, we derive an MAE bound on the last iterate of the SG algorithm, whereas in part III, we derive an MSE bound on the last iterate of the SG algorithm. Part I. Recall that the objective function OCE(·) is µ-strongly convex and L-smooth. θ0 is chosen arbitrarily and {θ1 , θ2 , . . . , θn } are the random iterates of the SG algorithm given in Algorithm 2. Using the shorthand notation zk ≜ θk − θ∗ , the following holds w.p. 1. 2

2

2

∥zn−1 − αn ∇ OCE(θn−1 )∥2 = ∥zn−1 ∥2 + αn2 ∥∇ OCE(θn−1 )∥2 − 2αn ⟨zn−1 , ∇ OCE(θn−1 )⟩ 2

≤ (1 + αn2 L2 ) ∥zn−1 ∥2 − 2αn ⟨zn−1 , ∇ OCE(θn−1 )⟩ .

(28)

The above inequality follows from the theorem condition: ∇ OCE(θ∗ ) = 0 and because OCEu (X)(·) is L-smooth, which implies that ∇ OCEu (X) is L-Lipschitz. Since OCE is continuously differentiable and µ-strongly convex function OCEu (X)(·), by Definition 2.1.2 of Nesterov (2004), we have OCE(θ1 ) ≥ OCE(θ2 ) + ⟨∇ OCE(θ2 ), θ2 − θ1 ⟩ + µ2 ∥θ1 − θ2 ∥2 , for every θ1 , θ2 ∈ Θ. Putting θ1 = θn−1 , θ2 = θ∗ in the identity and using the condition: ∇ OCE(θ∗ ) = 0, we have OCE(θ∗ ) − 2 OCE(θn−1 ) ≤ −µ 2 ∥zn−1 ∥2 . Furthermore, by putting θ1 = θ∗ and θ2 = θn−1 in the identity, we have µ 2 2 − ⟨zn−1 , ∇ OCE(θn−1 )⟩ ≤ OCE(θ∗ ) − OCE(θn−1 ) − ∥zn−1 ∥2 ≤ −µ ∥zn−1 ∥2 . 2 Substituting the above result back in (28), we have 2

2

∥zn−1 − αn ∇ OCE(θn−1 )∥2 ≤ (1 − 2αn µ + αn2 L2 ) ∥zn−1 ∥2 .

(29)

k k k Recall that Qm θk−1 (Z ) is the gradient estimator constructed at iteration k, using iterate θk−1 and samples Z of size mk . We k k use the following shorthand notation J k = Qm θk−1 (Z ). For the case when θ is fixed (deterministic) and m ∈ N , the gradient m estimator Qθ (·) satisfies estimation bounds given by

h i C C1 2 2 m E [∥Qm , θ (Z) − ∇ OCE(θ)∥2 ] ≤ √ , and E ∥Qθ (Z) − ∇ OCE(θ)∥2 ≤ m m where C1 and C2 can be determined from Lemma 6. For the case when inputs are stochastic, such as the random iterates {θk }k∈N , we now show that the above bounds can be extended to the gradient estimators {J k }k∈N that are constructed using the random iterates. Define
the following shorthand notation ζk ≜ J k − ∇ OCE(θk−1 ). Define filtration F0 = σ(θ0 ) and Fk = σ θ0 , Z1 , Z2 , . . . , Zk , ∀k ∈ N . From the procedure given in Algorithm 2, we deduce that θk−1 is Fk−1 measurable, and Zk ⊥ Fk−1 . Then by the Lemma 2.3.4 (Independence Lemma) of Shreve (2004), following holds for every k ∈ N: h i C1 C2 2 E [ ∥ζk ∥2 | Fk−1 ] ≤ √ , and E ∥ζk ∥2 Fk−1 ≤ . (30) mk mk

Part II. Next, we derive MAE bounds on the last iterate of the SG algorithm. For each iteration n ∈ N of the SG update, we have zn = Πθ (θn−1 − αn (∇ OCE(θn−1 ) + ζn )) − θ∗ . Note that θ∗ ∈ Θ holds, and therefore, θ∗ = ΠΘ (θ∗ ). Using this identity along with the non-expansive property of the projection operator, we have the following w.p. 1. ∥zn ∥2 ≤ ∥zn−1 − αn (∇ OCE(θn−1 ) + ζn )∥2 ≤ ∥zn−1 − αn ∇ OCE(θn−1 )∥2 + αn ∥ζn ∥2 ≤

p 1 − 2αn µ + αn2 L2 ∥zn−1 ∥2 + αn ∥ζn ∥2 ,

where the last inequality follows from eq. (29). Here, the square root is well-defined because 1 − 2αk µ + αk2 L2 is non-negative for every k. Indeed, (1 − 2αk µ + αk2 L2 ) ≥ (1 − 2αk µ + αk2 µ2 ) ≥ 0, where we used the fact that for a L-smooth and µ-strongly convex function, L ≥ µ holds. After unrolling the above inequality, the following holds w.p. 1:   ! n n q n q X Y Y 1 − 2αk µ + αk2 L2 + 1 − 2αj µ + αj2 L2  [(αk ∥ζk ∥2 )]  ∥zn ∥2 ≤ ∥z0 ∥2 k=1

k=1

j=k+1

v v u n u Y n X uY u n 2 2 t = ∥z0 ∥ (1 − 2αk µ + α L ) + [(αk ∥ζk ∥ )] t 2

2

k

k=1

1 − 2αj µ + αj2 L2 .

(31)

j=k+1

k=1

Note that if 0 ≤ aj ≤ bj , ∀j then Πj aj ≤ Πj bj . Let aj = (1 − 2αj µ + αj2 L2 ) and bj = exp 2αj µ + αj2 L2 . Then, we apply the identity: 1 + x ≤ ex , ∀x ∈ R to infer that aj ≤ bj , ∀j. Then, we have n Y

n X

1 − 2αj µ + αj2 L2 ≤ exp −2αj µ + αj2 L2 .

j=k+1

j=k+1

(32)

Substituting the above result in (31), we have  ! ! X n n X αj2 L2 αk2 L2 αk ∥ζk ∥ ∥zn ∥2 ≤ ∥z0 ∥2 exp −αk µ + + exp  −αj µ + 2 2 2 k=1 k=1 j=k+1      ! n n n n X X X X αj2 L2  ∥z0 ∥ exp ≤ exp  −αk µ + exp  −αj µαk ∥ζk ∥2  . 2 2 j=1 n  X

k=1

For the term: exp

P

2

αj L n j=1 2

2



k=1

j=k+1

, using αk = kc and applying simple calculus to have the following bound:

     2 2 2 n n 2 2 X X αj2 L2 c L π 1  = exp  c L ≤ exp exp  . 2 2 2 j 12 j=1 j=1 In a similar manner, for the other term: exp



n j=k+1 −αj µ

, we have

 n X −1  exp  −αj µ = exp µc j j=k+1 j=k+1  Z n+1   µc    k + 1 µc −1 k n+1 µc ≤ exp µc dj = exp µc [− log(x)]k+1 = ≤2 . n+1 n+1 j=k+1 j 

n X



P



Substituting the bounds for the above two terms back in (33), we have #  2 2 2" n ∥z0 ∥2 c L π 2µc c X µc−1 ∥zn ∥2 ≤ exp + k ∥ζk ∥2 . 12 (n + 1)µc (n + 1)µc k=1

Taking expectation on both sides, we have #  2 2 2" n E [∥z0 ∥2 ] 2µc cC1 X µc−1.5 c L π + k , E [∥zn ∥2 ] ≤ exp 12 (n + 1)µc (n + 1)µc k=1

(33)

where the above inequality follows from eq. (30) after applying the law of total expectation. The theorem assumption c > µ1 implies that the condition : µc − 1.5 > −1 is satisfied, and the summation above is bounded by a finite integral given below. Z n+1 n X (n + 1)1+µc−1.5 µc−1.5 ≤ 2(n + 1)µc−0.5 . k ≤ k µc−1.5 dk ≤ 1 + µc − 1.5 k=1 k=1

Then,

 2 2 2  E [∥z0 ∥2 ] 2µc+1 cC1 c L π . + √ 12 n+1 n+1 This concludes the MAE bound on the last iterate of SG algorithm. E [∥zn ∥2 ] ≤ exp

Part III.

(34)

We now derive the MSE error bound on the last iterate θn . With probability 1, we have 2

2

∥zn ∥2 ≤ ∥zn−1 − αn ∇ OCE(θn−1 ) − αn ζn ∥2 2

2

= ∥zn−1 − αn ∇ OCE(θn−1 )∥2 − 2αn ⟨zn−1 − αn ∇ OCE(θn−1 ), ζn ⟩ + αn2 ∥ζn ∥2 2

2

≤ (1 − 2αn µ + αn2 L2 ) ∥zn−1 ∥2 + 2αn ∥zn−1 − αn ∇ OCE(θn−1 )∥2 ∥ζn ∥2 + αn2 ∥ζn ∥2 p 2 2 ≤ (1 − 2αn µ + αn2 L2 ) ∥zn−1 ∥2 + 2αn 1 − 2αn µ + αn2 L2 ∥zn−1 ∥2 ∥ζn ∥2 + αn2 ∥ζn ∥2 2

2

≤ (1 − 2αn µ + αn2 L2 ) ∥zn−1 ∥2 + 2αn (1 + cL) ∥zn−1 ∥2 ∥ζn ∥2 + αn2 ∥ζn ∥2 , where the second and third inequalities follow from (29), while the last inequality follows from: 1 + αn L ≤ 1 + α1 L = 1 + cL. Unrolling the above equation, we have  n n n  Y  Y X
2 2  2 (1 + cL) αk ∥zk−1 ∥ ∥ζk ∥ + αk2 ∥ζk ∥2 1 − 2αk µ + αk2 L2 + ∥zn ∥2 ≤ ∥z0 ∥2 2 2 2 k=1 n 2 X ∥z0 ∥2 ≤ + (n + 1)2µc k=1




1 − 2αj µ + αj2 L2 

j=k+1

k=1

"

p 1 − 2αn µ + αn2 L2 <

2

2 (1 + cL) αk ∥zk−1 ∥2 ∥ζk ∥2 + αk2 ∥ζk ∥2



k+1 n+1

2µc # .

The last inequality follows from (32). Taking expectations on both sides, we have h i i h i h P h i E ∥z0 ∥22 + 22µc nk=1 2 (1 + cL) αk E [∥zk−1 ∥2 ∥ζk ∥2 ] + αk2 E ∥ζk ∥22 k 2µc 2 E ∥zn ∥2 ≤ 2µc (n + 1)

(35)

Next, we have for all k ∈ {1, 2, . . . , n}, C1 E [∥zk−1 ∥2 ∥ζk ∥2 ] = E [ E [∥zk−1 ∥2 ∥ζk ∥2 | Fk−1 ]] = E [∥zk−1 ∥2 E [∥ζk ∥2 | Fk−1 ]] ≤ √ E [∥zk−1 ∥2 ] . mk The first equality is the law of total expectation, while the second equality follows because θk−1 is Fk−1 -measurable. The last inequality follows from the first bound in eq. (30). Substituting this back into eq. (35) and applying the second bound from eq. (30), we have h i 2  n  h i E ∥z0 ∥2 X 22µc 2 (1 + cL) C1 2 2µc 2 C2 2µc + α k E [∥z ∥ ] + α k . E ∥zn ∥2 ≤ √ k k−1 2 k 2µc (n + 1)2µc mk mk (n + 1) k=1

Substituting mk = k and αk = c/k, we have h i 2 n n h i E ∥z0 ∥2 22µc c2 C2 X 2µc−3 22µc+1 (1 + cL) cC1 X 2µc−1.5 2 + k + k E [∥zk−1 ∥2 ] E ∥zn ∥2 ≤ 2µc 2µc (n + 1)2µc (n + 1) (n + 1) k=1 k=1 h i 2 n E ∥z0 ∥2 22µc+1 (1 + cL) cC1 X 2µc−1.5 22µc c2 C2 + k E [∥zk−1 ∥2 ] . ≤ + 2 2µc (n + 1)2 (2µc − 2) (n + 1) (n + 1)

(36)

k=1

The last inequality follows from the assumption c > µ1 and by replacing the first summation with an integral. For bounding the last summation in eq. (36), we make the following claim: for every k ≥ 1,  2 2 2  E [∥z0 ∥2 ] 2µc+1 cC1 c L π √ E [∥zk−1 ∥2 ] ≤ exp + . 12 k k

For k > 1, the claim follows from the MAE bound in eq. (34), while for the case k = 1 it holds trivially. Substituting the above inequality back in eq. (36), we have h i i E ∥z0 ∥22 h 22µc c2 C2 2 + E ∥zn ∥2 ≤ 2 (n + 1)2 (2µc − 2) (n + 1)   n
c2 L2 π 2 X 2µc−2.5 22µc+1 (1 + cL) cC1 exp + k E [∥z0 ∥2 ] + 2µc+1 cC1 k 2µc−2 2µc 12 (n + 1) k=1 h i 2  2 2 2  E ∥z0 ∥2 E [∥z0 ∥2 ] 22µc c2 C2 c L π 22µc+2 (1 + cL) cC1 µc √ + + exp + 2 cC ≤ 1 2 (n + 1)2 n+1 12 n+1 (2µc − 2) (n + 1) h i 2 E ∥z0 ∥2 + K1 K2 E [∥z0 ∥2 ] K3 + + , = (n + 1)2 n+1 (n + 1)3/2  2 2 2 2µc 2 c C2 where K1 = 2(2µc−2) , K2 = 22µc+2 (1 + cL) cC1 exp c L12π and K3 = 2µc cC1 K2 . The last inequality follows by bounding the summation with a finite integral. This completes the proof for the bound on convergence in parameter, i.e., θn → θ∗ for the strongly-convex case. For the bound on convergence in value (OCE(θn ) → OCE(θ∗ )), similar bounds may be obtained using the fact that OCE is L-smooth.

D.2

Convex case

  When OCE(·) is convex, we bound the difference in function value E OCE(θn ) − OCE(θ∗ ) for an average iterate given by Pn √ θn ≜ n1 k=1 θk−1 . This bound is Õ (1/ n) and is presented in the result below. Theorem 11. Suppose the assumptions of Theorem 3 and assumptions 2, 4, 5 and 7 are satisfied. Suppose OCE(·) is convex 1 on Θ. Run Algorithm 2 with αk = L√ , mk = k, ∀k, then we have k   K4 E OCE(θn ) − OCE(θ∗ ) ≤ √ , n h i 2 where the constant K4 depends on the initial errors E [∥θ0 − θ∗ ∥2 ] , E ∥θ0 − θ∗ ∥2 and contains the terms ln n and ln2 n. Proof. Note that OCE is convex and L-smooth, and Θ is convex. Then by Theorem 2.1.5 of (Nesterov 2004), for every θ2 , θ2 ∈ Θ, we have ⟨∇ OCE(θ2 ) − ∇ OCE(θ1 ), θ2 − θ1 ⟩ ≥

1 2 ∥∇ OCE(θ2 ) − ∇ OCE(θ1 )∥ . L

(37)

Since OCE(·) is continuously differentiable and convex, by Definition 2.1.2 of (Nesterov 2004), we have OCE(θ2 ) ≥ OCE(θ1 ) + ∇ OCE(θ1 )T (OCE(θ2 ) − OCE(θ1 )), ∀θ1 , θ2 ∈ T .

(38)

Let {zk }k≥0 and {ζk }k≥1 be as defined in the proof of Theorem 10. Then, we have the following w.p. 1. 2

2

2

∥zn−1 − αn ∇ OCE(θn−1 )∥2 = ∥zn−1 ∥2 + αn2 ∥∇ OCE(θn−1 )∥2 − 2αn ⟨zn−1 , ∇ OCE(θn−1 )⟩ 2αn 2 2 2 ≤ ∥zn−1 ∥2 + (αn2 − ) ∥∇ OCE(θn−1 )∥2 ≤ ∥zn−1 ∥2 L =⇒ ∥zn−1 − αn ∇ OCE(θn−1 )∥2 ≤ ∥zn−1 ∥2 . This implies that w.p. 1, the following holds. ∥zn ∥2 ≤ ∥zn−1 − αn (∇ OCE(θn−1 ) + ζn )∥2 ≤ ∥zn−1 − αn ∇ OCE(θn−1 )∥2 + αn ∥ζn ∥2 ≤ ∥zn−1 ∥2 + αn ∥ζn ∥2 n X =⇒ ∥zn ∥2 ≤ ∥z0 ∥2 + αk ∥ζk ∥2 , k=1

(39)

where the first inequality follows from eq. (37) and the second inequality follows from the step size assumption: αn ≤ 1/L. Next, we note that the following holds w.p. 1. 2

2

2

∥zn ∥2 ≤ ∥zn−1 − αn ∇ OCE(θn−1 )∥2 − 2αn ⟨zn−1 − αn ∇ OCE(θn−1 ), ζn ⟩ + αn2 ∥ζn ∥2  αn  2 2 2 ≤ ∥zn−1 ∥2 + αn2 − ∥∇ OCE(θn−1 )∥2 − αn (OCE(θn−1 ) − OCE(θ∗ )) + 2αn ∥zn−1 ∥2 ∥ζn ∥2 + αn2 ∥ζn ∥2 L ! n−1 X 2 2 ≤ ∥zn−1 ∥2 − αn (OCE(θn−1 ) − OCE(θ∗ )) + 2αn ∥z0 ∥2 + αk ∥ζk ∥2 ∥ζn ∥2 + αn2 ∥ζn ∥2 k=1 2 2 =⇒ αn (OCE(θn−1 ) − OCE(θ∗ )) ≤ ∥zn−1 ∥2 − ∥zn ∥2 + 2αn ∥ζn ∥2 ∥z0 ∥2 + 2αn ∥ζn ∥2

"n−1 X

# 2

αk ∥ζk ∥2 + αn2 ∥ζn ∥2 .

k=1

Taking the telescopic sum, we have the following w.p. 1. n X

2

αk (OCE(θk−1 ) − OCE(θ∗ )) ≤ ∥z0 ∥2 + 2 ∥z0 ∥2

k=1

n X

αk ∥ζk ∥2 + 2

k=1

n X

αk ∥ζk ∥2

k−1 X

αj ∥ζj ∥2 +

j=1

k=1

n X

2

αk2 ∥ζk ∥2 .

(40)

k=1

By monotonicity of αk , i.e., αn ≤ αk , ∀k ∈ 1. . . . , n, we have the following w.p. 1. n X

2

αn (OCE(θk−1 ) − OCE(θ∗ )) ≤ ∥z0 ∥2 + 2 ∥z0 ∥2

k=1

n X

αk ∥ζk ∥2 + 2

k=1

n X

αk ∥ζk ∥2

k=1

k−1 X

αj ∥ζj ∥2 +

j=1

n X

2

αk2 ∥ζk ∥2 .

k=1

By convexity of OCE(·), we have the following w.p. 1. √ n k−1 n n 2 X X
∥ζk ∥2 ∥ζk ∥2 X ∥ζj ∥2 X ∥ζk ∥2 n 2 √ + √ +2 √ OCE(θn ) − OCE(θ∗ ) ≤ ∥z0 ∥2 + 2 ∥z0 ∥2 . L L2 k L k L k j=1 L j k=1

k=1

k=1

Taking expectation on both sides, and with identical arguments as made in the proof in Theorem 10 (see eq. (30)), we have √ k−1 n n n h i 2C E [∥z ∥ ] X  n  1 C2 X 1 X 1 C X 1 1 0 2 2 √ √ + 22 E OCE(θn ) − OCE(θ∗ ) ≤ E ∥z0 ∥2 + + 2 12 . L L k L L k2 k j=1 j k=1 k=1 k=1 Pn Applying k=1 k1 ≤ 1 + ln n and rearranging, we have   h i   1 2C12 (1 + ln n)2 C2 π 2 2 √ E OCE(θn ) − OCE(θ∗ ) ≤ LE ∥z0 ∥2 + 2C1 E [∥z0 ∥2 ] (1 + ln n) + + . L 6L n

D.3

Non-convex case

The final result for OCE optimization does not require convexity, and as is standard in non-convex optimization literature, establishes a bound on the OCE gradient norm. Theorem 12. Suppose the assumptions of Theorem 3 and assumptions 2, 4, 5 and 7 are satisfied. Run Algorithm 2 with 1 αk = L√ , mk = k, ∀k, then we have k   K5 2 E min ∥∇ OCE(θk−1 )∥2 ≤ √ , n k∈[1,n] i h 2 where the constant K5 depends on the initial errors E [∥θ0 − θ∗ ∥2 ] , E ∥θ0 − θ∗ ∥2 and contains the terms ln n and ln2 n. Proof. Recall the terms {zk }k≥0 and {ζk }k≥1 given in Theorem 10. The following holds w.p. 1.   2αn 2 2 2 2 2 ∥zn ∥2 ≤ ∥zn−1 ∥2 + αn − ∥∇ OCE(θn−1 )∥2 + 2αn ∥zn−1 ∥2 ∥ζn ∥2 + αn2 ∥ζn ∥2 L   n−1 X α n 2 2 2 ≤ ∥zn−1 ∥2 − ∥∇ OCE(θn−1 )∥2 + 2αn ∥z0 ∥2 + αj ∥ζj ∥2  ∥ζn ∥2 + αn2 ∥ζn ∥2 L j=1   n−1   X αn 2 2 2 2 =⇒ ∥∇ OCE(θn−1 )∥2 ≤ ∥zn−1 ∥2 − ∥zn ∥2 + 2αn ∥z0 ∥2 + αj ∥ζj ∥2  ∥ζn ∥2 + αn2 ∥ζn ∥2 . L j=1

Pn 2 2 Taking summation from 1 to n, we have (i) L1 k=1 αk ∥∇ OCE(θk−1 )∥2 ≤ Y a.s., where Y = ∥z0 ∥2 + Pn Pn Pk−1 Pn 2 2 ∥z0 ∥2 k=1 αk ∥ζk ∥2 + 2 k=1 αk ∥ζk ∥2 j=1 αj ∥ζj ∥2 + k=1 αk2 ∥ζk ∥2 . From Theorem 11, we know that Y is the same term as that on the r.h.s. of eq. (40) and we know that (ii) E [Y ] ≤ KL4 . From the monotonicity of αk , we know that n X

2 αk ∥∇ OCE(θk−1 )∥2 ≥ αn

n X

2

2

∥∇ OCE(θk−1 )∥2 ≥ nαn min ∥∇ OCE(θk−1 )∥2 . k∈1,...,n

k=1

k=1 √ 2 Combining the above inequality with (i), we have Ln mink∈1,...,n ∥∇ OCE(θk−1 )∥2 ≤ Y a.s. Then, taking the expectation on

both sides and invoking (ii), we have

 E

min

k∈1...n

2 ∥∇ OCE(θk−1 )∥2



K4 ≤√ . n

The ln n terms in theorems 11 and 12 are unavoidable as Algorithm 2 is an any-time algorithm. If we modify the step sizes to αk = L√1 N or modify the batch sizes to mk = N , then the ln n terms are reduced to a constant.

E

Experiments

In this section, we provide a detailed description of our simulation experiments on OCE estimation and optimization. Our work is foundational, and we introduce a gradient-based approach to optimize the OCE criterion and provide convergence guarantees. The goal of the experiments is to compare the OCE-optimal decision models against well-known benchmarks, including the risk-neutral variant. The experiments report comparisons across different problem instances, different OCE instances, and a wide range of evaluation metrics. Therefore, a comprehensive hyperparameter analysis is out of scope for this work and could be an interesting research direction for future work. In a similar spirit, analysis of the hyperparameters that make up the utility functions is left to future work, as the choice of utility functions is subjective and depends on the decision-maker’s risk preferences. Thus, there are no ’optimal’ hyperparameters in the context of utility functions. Hardware: The experiments on uncertainty quantification and classification were run on Google Colab with ’Python 3 Google Compute Engine backend’ having 12.7 GB of RAM. The remaining experiments were run on a standard 16 GB laptop.

E.1

Portfolio Optimization

Setup. Our experiment setup is based on the skfolio Python library. We test the aforementioned algorithms on three different datasets: ’Standard and Poor’s 500 (S&P500)’, ’Financial Times Stock Exchange (FTSE100)’, and ’Nasdaq’. The ’S&P 500’ dataset is composed of the daily prices of 20 assets from the ’S&P 500’ composition starting from 1990-01-02 up to 2022-12-28. The ’FTSE100’ dataset contains daily prices for 64 assets in the ’FTSE100’ index, from 2000-01-04 to 2026-05-26. The ’Nasdaq’ dataset contains daily prices for 1455 assets in the ’Nasdaq’ index from 2018-01-02 to 2026-05-26. For each of the above datasets, we run the OCE-SG algorithms and evaluate several risk measures, including popular choices such as entropic, monotone mean-variance, and quartic risk. Implementation details. We denote the dataset size by M and the number of assets by d. Thus, values of (M, d) for ’S&P 500’, ’FTSE100’, and ’Nasdaq’ are (8312, 20), (5959, 64), and (1361, 1455), respectively. Thus, the OCE-SG algorithm finds a d-dimensional vector θ that corresponds to the portfolio weights, with OCE as the optimization criteria. We run the OCE-SG algorithm for different choices of utility functions, given in examples 1 to 7. For each dataset and each aforementioned example, we run the OCE-SG algorithm for N = 15000 iterations, where we use αk = √1M and mk = M for each iteration. We use the pyproximal Python library for the projection step in the gradient update step of the algorithm. Observations. From figures 2 to 4 and tables 7 to 9 we conclude that the portfolios given by the OCE-SG algorithm are either comparable to the benchmarks or outperform the benchmarks. Depending on market conditions and the decision-maker’s preferences, different OCE risk measures emerge as the preferred choices. The CVaR indeed outperforms when the stock market returns fall, indicating that it is a viable risk-averse choice. On the other hand, when the stock market returns are rising, then the OCE risks: entropic, mean-variance, monotone mean-variance, smooth-cvar, and quartic risks produce higher returns, with better Sharpe and Sortino ratios. In all three datasets, the portfolio performance on the CVaR metric shows that the OCE-SG algorithm for utility given in Example 5 indeed optimizes the CVaR criterion, and validates the convergence guarantees of the OCE-SG algorithm.

200.00%

Portfolios Benchmark - HRP Benchmark - Equal Weights 150.00%

Benchmark - Sharpe

Cumulative returns

Entropic Risk CVaR Risk Leaky CVaR Risk Smooth CVaR Risk

100.00%

MV Risk Mono-MV Risk Quartic Risk

50.00%

0.00%

2015

2016

2017

2018

2019

2020

2021

2022

Time

Figure 2: The performance of the OCE-SG algorithm for a variety of OCE risk measures in a portfolio optimization application sourced from the S&P stock market data. Table 7: The performance of the OCE-SG algorithm on the S&P stock market dataset, compared against three benchmark portfolios. The table reports the portfolio evaluations across a wide range of risk metrics. Portfolio

Annualized Returns

Gini MD

CVaR

EVaR

CDaR

Sharpe

Sortino

Benchmark - HRP Benchmark - Equal Weights Benchmark - Sharpe

0.1462 0.1717 0.1814

0.0102 0.0115 0.0115

0.0251 0.0274 0.0270

0.0541 0.0565 0.0542

0.1302 0.1448 0.1409

0.8663 0.9241 0.9685

1.1988 1.2885 1.3725

Entropic Risk CVaR Risk Leaky CVaR Risk Smooth CVaR Risk MV Risk Mono-MV Risk Quartic Risk

0.1924 0.1272 0.1603 0.1937 0.1921 0.1874 0.1683

0.0128 0.0099 0.0106 0.0134 0.0125 0.0125 0.0113

0.0297 0.0239 0.0254 0.0304 0.0294 0.0291 0.0267

0.0579 0.0487 0.0526 0.0563 0.0588 0.0570 0.0539

0.1697 0.1528 0.1315 0.1868 0.1644 0.1644 0.1432

0.9445 0.7792 0.9225 0.9150 0.9593 0.9403 0.9206

1.3308 1.0881 1.2924 1.2925 1.3451 1.3242 1.2954

100.00%

Portfolios Benchmark - HRP 80.00%

Benchmark - Equal Weights Benchmark - Sharpe

Cumulative returns

Entropic Risk 60.00%

CVaR Risk Leaky CVaR Risk Smooth CVaR Risk MV Risk

40.00%

Mono-MV Risk Quartic Risk

20.00%

0.00%

−20.00% 2018

2019

2020

2021

2022

2023

Time

Figure 3: The figure shows the performance of the OCE-SG algorithm for a variety of OCE risk measures in a portfolio optimization application sourced from the FTSE stock market data.

Table 8: The performance of the OCE-SG algorithm on the FTSE stock market dataset, compared against three benchmark portfolios. The table reports the portfolio evaluations across a wide range of risk metrics. Portfolio

Annualized Returns

Gini MD

CVaR

EVaR

CDaR

Sharpe

Sortino

Benchmark - HRP Benchmark - Equal Weights Benchmark - Sharpe

0.0857 0.0879 0.1010

0.0103 0.0114 0.0120

0.0249 0.0276 0.0266

0.0516 0.0568 0.0450

0.1992 0.2367 0.2287

0.5311 0.4892 0.5579

0.7198 0.6673 0.7709

Entropic Risk CVaR Risk Leaky CVaR Risk Smooth CVaR Risk MV Risk Mono-MV Risk Quartic Risk

0.1252 0.0990 0.0979 0.1120 0.1229 0.1125 0.1119

0.0139 0.0102 0.0107 0.0132 0.0140 0.0132 0.0120

0.0310 0.0229 0.0244 0.0297 0.0311 0.0297 0.0272

0.0580 0.0406 0.0452 0.0550 0.0581 0.0551 0.0497

0.3026 0.1864 0.1934 0.2877 0.3065 0.2859 0.2435

0.5866 0.6401 0.5989 0.5554 0.5738 0.5563 0.6078

0.8071 0.8777 0.8174 0.7622 0.7895 0.7633 0.8365

20.00%

Cumulative returns

10.00%

0.00%

−10.00%

Portfolios −20.00%

Benchmark - HRP Benchmark - Equal Weights Benchmark - Sharpe

−30.00%

Entropic Risk CVaR Risk Leaky CVaR Risk

−40.00%

Smooth CVaR Risk MV Risk

−50.00%

Mono-MV Risk Quartic Risk Mar 2022

May 2022

Jul 2022

Sep 2022

Nov 2022

Jan 2023

Mar 2023

May 2023

Time

Figure 4: The figure shows the performance of the OCE-SG algorithm for a variety of OCE risk measures in a portfolio optimization application sourced from the NASDAQ stock market data.

Table 9: The performance of the OCE-SG algorithm on the NASDAQ stock market dataset, compared against three benchmark portfolios. The table reports the portfolio evaluations across a wide range of risk metrics. Portfolio

Annualized Returns

Gini MD

CVaR

EVaR

CDaR

Sharpe

Sortino

Benchmark - HRP Benchmark - Equal Weights Benchmark - Sharpe

-0.0747 -0.0949 -0.1711

0.0153 0.0181 0.0246

0.0279 0.0325 0.0465

0.0333 0.0379 0.0526

0.2121 0.2345 0.4183

-0.3471 -0.3739 -0.4930

-0.4924 -0.5308 -0.6945

Entropic Risk CVaR Risk Leaky CVaR Risk Smooth CVaR Risk MV Risk Mono-MV Risk Quartic Risk

-0.2722 -0.0315 -0.2171 -0.3620 -0.2727 -0.3483 -0.3150

0.0379 0.0099 0.0292 0.0371 0.0390 0.0371 0.0341

0.0695 0.0191 0.0553 0.0686 0.0706 0.0685 0.0633

0.0768 0.0270 0.0608 0.0753 0.0769 0.0753 0.0685

0.5772 0.2033 0.4735 0.6369 0.5866 0.6256 0.5525

-0.5064 -0.2220 -0.5270 -0.6872 -0.4945 -0.6616 -0.6520

-0.7333 -0.3103 -0.7469 -0.9975 -0.7172 -0.9606 -0.9399

E.2

Classification

Setup. We used the UCI Heart Disease dataset and Breast Cancer Detection dataset for the classification problem given in Example 9. In this experiment, we evaluate neural network (NN) models obtained by minimizing the OCE criterion using our OCE-SG algorithm. We use PyTorch to train these models and benchmark them against three standard classification algorithms: Logistic Regression, Support Vector Machines (SVM), and Random Forest, as well as a risk-neutral NN variant obtained by minimizing Binary Cross-Entropy (BCE) loss. These algorithms are the standard benchmarks on clinical classification tasks due to their generalization, interpretability, and performance across a wide range of metrics, going beyond ’Accuracy’. on the chosen datasets. We evaluate these models across four well-established metrics: Accuracy, F1-score, ECE (Expected Calibration Error), and AUROC (Area Under the Receiver Operating Characteristic). Implementation details. For simplicity, we choose 2 layer NN models with hidden sizes of 32 and 16 respectively, for all NN-based algorithms. The following procedure is identical for the OCE variants and the risk-neutral variant. We train each algorithm for 500 epochs, using the Adam optimizer with a learning rate of αk = 0.003. In each epoch, the entire dataset is iterated using a fixed batch size of mk = 64. The remaining algorithms are implemented using the scikit-learn library. Table 10: Model Performance Comparison (a) Performance comparison on the Breast Cancer Detection dataset

(b) Performance comparison on the UCI Heart Disease dataset

Model

Acc.

F1

ECE

AUROC

Model

Acc.

F1

ECE

AUROC

NN (OCE) Entropic NN (OCE) CVaR NN (OCE) LCVaR NN (OCE) SCVaR NN (OCE) Monotone MV NN (OCE) Quartic

0.9591 0.9766 0.9766 0.9883 0.9649 0.9708

0.9668 0.9813 0.9815 0.9907 0.9717 0.9767

0.0213 0.3358 0.0497 0.0239 0.0263 0.0279

0.9950 0.9974 0.9963 0.9963 0.9956 0.9966

NN (OCE) Entropic NN (OCE) CVaR NN (OCE) LCVaR NN (OCE) SCVaR NN (OCE) Monotone MV NN (OCE) Quartic

0.8556 0.8778 0.8333 0.8556 0.8667 0.8444

0.8395 0.8736 0.8193 0.8395 0.8500 0.8250

0.1089 0.3721 0.2873 0.1244 0.1192 0.2580

0.9504 0.9444 0.9464 0.9449 0.9479 0.9464

NN BCE Loss Logistic Regression SVC (Baseline) Random Forest

0.9532 0.9883 0.9766 0.9357

0.9619 0.9907 0.9813 0.9488

0.0437 0.0324 0.0412 0.0430

0.9908 0.9981 0.9978 0.9913

NN BCE Loss Logistic Regression SVC (Baseline) Random Forest

0.8556 0.8444 0.8333 0.8556

0.8395 0.8250 0.8052 0.8395

0.0980 0.1050 0.0989 0.1198

0.9415 0.9439 0.9340 0.9293

Conclusions. From Table 10b, we observe that the OCE models achieve higher accuracy, F1, and AUROC on the UCI Heart Disease dataset. From Table 10a, we observe that the OCE models achieve the lowest ECE on the Breast Cancer Detection dataset and exhibit comparable performance on the remaining metrics.

E.3

CVaR Optimization

We use the same setup as in the portfolio optimization experiment, including the implementation details. This experiment analyzes the OCE variants associated with CVaR and compares them against a benchmark CVaR solver from the skfolio library. Let the solver compute portfolio weights θcvs that minimize CVaR. In Figure 5, we observe that the OCE variant for CVaR not only converges in value to the solver variant (OCE(θk ) → OCE(θcvs )), but also in the portfolio composition (θk → θcvs ). This provides empirical evidence of the convergence guarantees established in the paper for the OCE-SG algorithm. From Table 11, we observe that the other variants, L-CVaR and S-CVaR, outperform the standard CVaR on some important metrics, indicating that these proposed variants could serve as viable alternatives to the standard CVaR. The tables 12 and 13 provides a similar performance comparison for the FTSE dataset and the Nasdaq dataset, respectively. Portfolio

An. Ret

CVaR

CDaR

Sharpe

Portfolio

An. Ret

CVaR

CDaR

Sharpe

Benchmark - CVaR CVaR Risk Leaky CVaR Risk Smooth CVaR Risk

0.0987 0.0991 0.0980 0.1284

0.0229 0.0229 0.0244 0.0305

0.1870 0.1858 0.1950 0.2938

0.6378 0.6407 0.5993 0.6101

Benchmark - CVaR CVaR Risk Leaky CVaR Risk Smooth CVaR Risk

-0.0283 -0.0281 -0.2168 -0.3619

0.0190 0.0190 0.0553 0.0686

0.2051 0.2016 0.4734 0.6368

-0.2000 -0.1988 -0.5263 -0.6869

Table 12: Comparison of CVaR variants against a benchmark solution on ’FTSE’ dataset, and evaluated on popular risk metrics

Table 13: Comparison of CVaR variants against a benchmark solution on ’NASDAQ’ dataset, and evaluated on popular risk metrics

Portfolios Composition

asset 100%

JNJ

PG

CVX

AAPL

LLY

PFE

MRK

PEP

BBY

RRC

XOM UNH

WMT MSFT

KO HD

Weight

80%

Portfolio

An. Ret

CVaR

CDaR

Sharpe

Benchmark - CVaR CVaR Risk Leaky CVaR Risk Smooth CVaR Risk

0.1250 0.1261 0.1619 0.2135

0.0239 0.0239 0.0258 0.0348

0.1561 0.1544 0.1350 0.2681

0.7639 0.7713 0.9209 0.8466

60%

40%

20%

0%

Benchmark - CVaR

CVaR Risk

Leaky CVaR Risk

Smooth CVaR Risk

Portfolios

Figure 5: Portfolio compositions of CVaR variants given by the OCE-SG algorithm, in comparison to the benchmark CVaR portfolio given by the skfolio library.

Table 11: Comparison of CVaR variants against a benchmark solution on ’S&P’ dataset, and evaluated on popular risk metrics

E.4

Uncertainty Quantification

Deep learning models have achieved superior performance on ML prediction problems, but they often fail to generalize well to out-of-distribution (OOD) data. A crucial aspect of any machine learning (ML) application is understanding what the model does not know. Uncertainty quantification tackles this problem by quantifying the model’s uncertainty. A popular method for capturing a model’s uncertainty is to use a mean-variance estimation (MVE) network (Nix and Weigend 1994; Sluijterman, Cator, and Heskes 2024), which serves as a building block for many uncertainty quantification algorithms in a supervised learning setting. Setup. The MVE framework assumes that every pair of input z = ⟨x, y⟩ comes from a Gaussian distribution: y ∼ N (µ(x), σ(x)), and the model learns to outputs mean and variance estimates for the given input, by minimizing the negative likelihood loss (NLL) of a Gaussian distribution. Precisely, it solves the problem : find θ∗ = arg minθ∈Θ E [F (θ, ξ)], where
1 (y − µθ (x))2 1 F (θ, z) = F (θ, ⟨x, y⟩) ≜ log σθ2 (x) + . 2 2 σθ2 (x) Implementation details. In this experiment, we use a simple heterogeneous regression dataset. We use two benchmarks: the original MVE solution and the state-of-the-art Deep ensemble solution. The implementations of both the benchmarks and the aforementioned dataset are available in the lightning-uq-box Python library. We modify the MVE’s loss by replacing the expectation with OCE risk criterion OCE(·), where u is the exponential utility given in Example 1. We run the OCE-SG for 1000 epochs with a batch size of 175 and a fixed learning rate of 0.03. From Figure 6, we observe that our approach significantly outperforms both benchmarks.

(a) Deep Ensembles

(b) Mean Variance Estimation

(c) Mean Variance Estimation with OCE risk

Figure 6: Performance of a Mean-Variance Estimation (MVE) model with OCE criterion against standard MVE and Deep Ensembles.

E.5

Entropic Risk - Estimation and Optimization

Entropic risk estimation. In this experiment, we assume X ∼ N (µ, σ 2 ) denotes losses, with mean µ = −1 and variance σ 2 = 4. Under this assumption, the value of the entropic risk measure ρe (X) for some β > 0, is given by:  
1 βσ 2 ρe (X) = log E eβX = µ + . (41) β 2

Mean Squared Error (MSE) MSE ±1 Std. Dev Mean Absolute Error (MAE) MAE ±1 Std. Dev

0.35

0.3

Errors

0.25

0.2

0.15

0.1

0.05

0 0

5

10

15

20

Iteration Complexity (√n)

(a) Estimation errors for sample-based estimation of entropic risk using OCE.

(b) Convergence of iterates of the OCE-SG algorithm for the entropic risk criterion.

We use eq. (1) with β = 0.5 in our experiment and employ eq. (7) to estimate OCEu (X) using m samples of X. The associated MAE and MSE bounds on the estimation error, for varying choices of sample size m are given in Figure 7a. For each choice of m, we repeat the simulation N = 1000 times and compute the error mean and its spread (standard error) by averaging across the N simulations. The figure shows that our proposed estimator converges rapidly1 . Entropic risk optimization. We consider a portfolio optimization application (Example 8) with entropic risk as the objective. In particular, we consider a d-dimensional random vector ξ denoting a random vector of asset-wise market returns, which follows a multivariate normal distribution with mean µ and covariance matrix Σ, where Σ is positive-definite. The decision space Θ is T an d-dimensional simplex. Given θ ∈ Θ, we are interested in the problem  T of optimizing the quantity θ ξ over Θ.T A risk-neutral criterion would be to consider the average returns, i.e., maximize E θ ξ over θ, or equivalently, minimize −θ ξ over θ. A popular risk-sensitive criterion is the mean-variance risk, defined as follows. Let β > 0, then the mean-variance optimization problem is posed as   β (42) find θ∗ ≜ arg min −θT µ + θT Σθ . 2 θ∈Θ For our experiments, we choose entropic risk as the optimization criterion and relate it to the mean-variance criterion. Consider the objective function defined as F (θ, ξ) ≜ −θT ξ. Since ξ ∼ N (µ, Σ), we have F (θ, ξ) ∼ N (−θT µ, θT Σµ), ∀θ ∈ Θ. Replacing X in (41) with F (θ, ξ), we redefine the entropic risk as the function of θ as follows. Define ρE : Θ → R, where ρE (θ) = ρe (F (θ, ξ)), ∀θ ∈ Θ, where ρe is defined in (41). Then, by (41), it follows that for every θ ∈ Θ, βθT Σθ . 2 Comparing, (42) and (43), it is easy to see that θ∗ is also the minimizer of ρE (·). ρE (θ) = −θT µ +

(43)

Experiment setup. In our setup, we set d = 5. Using an arbitrary vector µ ∈ Rd and arbitrary, positive-definite matrix Σ ∈ Rd × Rd , we define ξ ∼ N (µ, Σ). The choices for µ, Σ are governed by a distribution underlying the make_spd_matrix function of scikit-learn python package. To find θ∗ in (42), we employed the convex optimization solver in the pyportfolioopt Python package. We evaluate the performance of the OCE-SG algorithm by choosing the√utility function as per Example 1, due to which, OCEu (F (θ, ξ)) coincides with ρE (θ). We run Algorithm 2 with αk = 1/ k and mk = k for 500 iterations. We repeat this simulation 20 times and Figure 7b shows the MAE and MSE errors on the iterates produced by the algorithm, averaged across the 20 runs. From the figure, we observe that the iterates indeed converge to the optima, i.e., θk → θ∗ . 1

Owing to fast convergence, we choose to plot these errors versus

√ m instead of m, in order to make the error decrease discernible.

Related documents

• On theoretical guarantees and a blessing of dimensionality for nonconvex sampling#635556
• On theoretical guarantees and a blessing of dimensionality for nonconvex sampling#633207
• A Weighted Kolmogorov Metric under Sub-Cubic Moments: Admissible Parameters and an Obstruction#793546
• A Weighted Kolmogorov Metric under Sub-Cubic Moments: Admissible Parameters and an Obstruction#789542
• Tight Sample Bounds for Renyi and Min-Entropy Estimation#625535