Gradient-based Stochastic Optimization of Utility-based Shortfall Risk

Technical Summary: Gradient-based Stochastic Optimization of Utility-based Shortfall Risk

Problem Statement
This paper addresses the estimation and optimization of the Utility-based Shortfall Risk (UBSR) measure. UBSR is a convex, law-invariant risk measure that generalizes several prominent risk metrics, including Entropic Risk, Expectile Risk, Value-at-Risk (VaR), and Quadratic Risk. While UBSR offers advantages over standard measures like VaR and Conditional Value-at-Risk (CVaR)—specifically regarding invariance under randomization and sensitivity to heavy-tailed losses—existing literature largely restricts analysis to bounded random variables. Furthermore, prior works often rely on asymptotic guarantees or focus on scalar decision parameters.

The primary challenges addressed in this work are:

1. Extending the theoretical framework of UBSR to cover unbounded random variables satisfying specific integrability conditions.
2. Deriving non-asymptotic error bounds for UBSR estimation using Sample Average Approximation (SAA).
3. Formulating a gradient expression for UBSR under a smooth parameterization (vector parameters) and developing a corresponding gradient estimator.
4. Designing and analyzing a Stochastic Gradient (SG) algorithm for UBSR optimization with non-asymptotic convergence rates in strongly convex, convex, and non-convex regimes.

Methodology

• Theoretical Extension to Unbounded Variables:
  The authors define UBSR as $SR_{l,\lambda}(X) \triangleq \inf\{ t \in \mathbb{R} \mid \mathbb{E}[l(-X - t)] \leq \lambda \}$, where $l$ is a loss function and $\lambda$ is a risk threshold. They rigorously establish that for unbounded random variables, the UBSR remains a monetary and convex risk measure under weaker assumptions on $l$ and the distribution of $X$ than previously required. They prove that $SR_{l,\lambda}(X)$ corresponds to the unique root of a decreasing function $g_X(t) = \mathbb{E}[l(-X-t)] - \lambda$.

• Estimation via Sample Average Approximation (SAA):
  The paper proposes estimating UBSR by solving an optimization problem where the expectation is replaced by an empirical average over $m$ i.i.d. samples.

  • Algorithm: A "Search and Bisect" (UBSR-SB) algorithm is introduced to find the root of the empirical function without prior knowledge of the search interval bounds.
  • Error Bounds: Under a variance assumption on the loss function, the authors derive non-asymptotic bounds for the Mean Absolute Error (MAE) and Mean Squared Error (MSE) of the estimator, showing rates of $O(1/\sqrt{m})$ and $O(1/m)$, respectively.

• Gradient Derivation and Estimation:
  For a parameterized objective $F(\theta, \xi)$, the paper derives the gradient of the UBSR objective $SR(\theta)$ using the Implicit Function Theorem. The gradient is expressed as a ratio of expectations:
  $$\nabla SR(\theta) = \frac{-\mathbb{E}[l'(-F(\theta, \xi) - SR(\theta)) \nabla F(\theta, \xi)]}{\mathbb{E}[l'(-F(\theta, \xi) - SR(\theta))]}$$
  To estimate this, the authors propose a double-sampling scheme using two independent batches of samples: one to estimate the UBSR value ($SR(\theta)$) and another to estimate the numerator and denominator expectations. This yields a biased gradient estimator.

  • Error Bounds: The paper establishes non-asymptotic MAE and MSE bounds for this gradient estimator, scaling with the sample sizes $m_1$ and $m_2$.

• Stochastic Optimization Algorithm:
  The proposed gradient estimator is integrated into a Stochastic Gradient (SG) algorithm (Algorithm 2). The algorithm employs increasing batch sizes ($m_k \propto k$) and diminishing step sizes.

  • Convergence Analysis: The authors derive non-asymptotic convergence rates for the last iterate (or averaged iterate) under three scenarios:
    1. Strongly Convex: Convergence rate of $O(1/n)$ for parameter error.
    2. Convex: Convergence rate of $O(1/\sqrt{n})$ for objective value error.
    3. Non-Convex: Convergence rate of $O(1/\sqrt{n})$ for the expected squared norm of the gradient.
       The analysis accounts for the bias and variance of the gradient estimator and holds for both online settings (where samples are queried dynamically) and offline settings (fixed datasets).

Key Contributions

1. Extension to Unbounded Variables: The paper provides a rigorous theoretical extension of UBSR to unbounded random variables, a gap identified in previous literature which often assumed bounded support or treated the extension as trivial.
2. Non-Asymptotic Estimation Bounds: Novel proofs are provided for the MAE and MSE bounds of the SAA estimator for unbounded variables, establishing $O(1/\sqrt{m})$ and $O(1/m)$ rates without requiring Lipschitz continuity or convexity of the loss function in all cases.
3. Multivariate Gradient Estimator: Unlike prior works restricted to scalar parameters, this paper derives a general expression for the gradient of UBSR with respect to a vector parameter $\theta$ and proposes a corresponding estimator with proven non-asymptotic error bounds.
4. SG Algorithm with Finite-Sample Guarantees: The authors propose a stochastic gradient algorithm for UBSR optimization and derive finite-sample convergence rates for strongly convex, convex, and non-convex objectives, addressing the challenge of optimizing with biased gradient information.
5. Empirical Validation: The algorithms are tested on financial applications, including VaR estimation, entropic risk minimization, and portfolio optimization using real-world datasets (S&P 500, FTSE 100, Nasdaq).

Results

• Estimation: Simulations demonstrate that the UBSR-SB algorithm converges rapidly, with estimation errors (MAE and MSE) decreasing as $O(1/\sqrt{m})$ and $O(1/m)$ respectively, consistent with theoretical bounds.
• Optimization: In portfolio optimization experiments, the UBSR-SG algorithm (and its offline variant) produced portfolios that were comparable to or outperformed standard benchmarks like the Equal-Weighted portfolio and the Minimum CVaR portfolio across multiple market indices.
• Convergence: Theoretical analysis confirms that the proposed SG algorithm achieves the derived convergence rates, validating the utility of the increasing batch size strategy in handling the bias-variance trade-off of the gradient estimator.

Significance and Claims

The paper claims to lay the foundations for UBSR estimation and optimization in a broader setting than previously possible (unbounded variables) with stronger computational guarantees (non-asymptotic bounds). The authors emphasize that their work addresses the computational aspects of UBSR, moving beyond theoretical properties to provide practical algorithms with provable performance guarantees.

The significance is highlighted in the context of financial applications (portfolio optimization) and risk-sensitive online learning (multi-armed bandits, federated learning), where the ability to optimize risk measures with unbounded losses and vector parameters is crucial. The authors note that their approach is more general than existing robust optimization frameworks that often require discrete distributions, bounded support, or offline datasets. The work positions UBSR as a superior alternative to CVaR and VaR for both estimation and optimization tasks due to its desirable properties (elicibility, randomization invariance).

The paper concludes by suggesting future work in developing Newton-based methods for UBSR optimization, leveraging the derived gradient expression.