# Risk-Aware Estimation From Compressed Data Beyond the Bayes Risk

Malcolm Egan

► To cite this version:

Malcolm Egan. Risk-Aware Estimation From Compressed Data Beyond the Bayes Risk. IEEE International Symposium on Information Theory - ISIT 2025, Jun 2025, Ann Arbor, United States. hal-05037552

HAL Id: hal-05037552

https://hal.science/hal-05037552v1

Submitted on 30 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Risk-Aware Estimation From Compressed Data
# Beyond the Bayes Risk (Extended Version)

Malcolm Egan

## Abstract

Inference often relies on compressed data due to communication, storage, or privacy constraints. In order to minimize degradation in the quality of inference, it is desirable to tailor compression schemes to the inference task. The compression scheme should therefore account for the statistic of the loss relevant for the task. While the expected loss is widely considered, in applications sensitive to large losses—such as in safe control and learning—alternative statistics are relevant. A key family of these alternative statistics are obtained via risk measures. In this paper, we characterize the increase in risk measure criteria for inference tasks as a function of the code size. Our characterization applies for general data statistics, loss functions, and number of samples. In the special case of i.i.d. data, we also establish asymptotics and a connection between our characterization for risk measure criteria and the rate-distortion function, which was previously only known for expected loss and excess distortion criteria.

## I. INTRODUCTION

A challenge in many inference tasks is the difficulty in accounting for all sources of uncertainty [1]. This difficulty may arise in modelling of the data, or the use of approximate estimators in the case of complex data distributions. Another source of uncertainty arises due to data processing, such as compression and communication, which may lead to corrupted or missing data.

One approach to mitigate the impact of uncertainty due to data processing is to tailor compression schemes to an inference task, often known as compress-and-estimate [2]. Compression of data can take several forms including dimension reduction [3], clustering, data and feature selection [4], and vector quantization [5], which often rely on an expected loss or distortion criterion for their design. End-to-end performance can be optimizing by adapting the loss function
to the inference task. This approach has been adopted in many domains, ranging from speech
compression [6] to dataset compression in learning [7].

While expected loss criteria are ubiquitous in many domains [7]–[9], compression that can
introduce arbitrarily large losses poses a critical problem for control and decision systems where
poor inference can lead to a catastrophe. Ideally in these applications, design of compression
schemes is based on the worst case loss. However, problems arise when the space of the data
is unbounded.

An alternative approach is to design compression schemes based on risk measures, which
capture the tail behavior of the loss distribution; e.g., the value-at-risk (VaR) [10] and conditional
value-at-risk (CVaR) [11], as well as weighted sums of the mean and variance [12]. Risk measure
objectives have been considered in decision, control, and optimization tasks in domains ranging
from safe control [13], safe learning [14], insurance [10], and reliability engineering [15].

On the other hand, the use of risk measures in upstream data processing tasks—including
compression—has seen limited attention. Excess distortion probability criteria, which are closely
related to the VaR, have been considered in lossy compression [16]. However, constraints on
more general families of risk measures such as the CVaR have not been investigated despite
their importance in end-to-end performance criteria in safe decision making.

In this paper, we address this gap by developing a general framework characterizing the
impact of data processing in safe or risk-aware inference tasks where risk measure criteria are
required. In particular, we consider inference tasks with end-to-end performance criteria based
on the general family of distortion risk measures [17]. We show that the contribution of data
processing on the end-to-end risk measure criterion can be bounded in terms of a distortion risk
measure which can be viewed as a generalization of the CVaR.

We then specialize our framework to estimation with data compressed by a fixed-length lossy
source code. In order to analyze the impact of compression on the end-to-end risk measure cri-
terion, we first formulate the problem of risk-constrained fixed-length lossy compression, which
generalizes the standard formulation based on the expected loss. We establish upper and lower
bounds on the risk measure constraint for a source code of a given size and finite dimensional
data. Our bounds highlight the impact of the choice of risk measure on the performance of the
compression scheme.

For the case of high dimensional data, we also study the tradeoff between the size of the source
code and the risk measure constraint. Analogously to the case of expected loss constraints [8],
[18], we show that this tradeoff is characterized by the information rate-distortion function—
independent of the choice of risk measure—under standard assumptions on the data distribution
and loss function.

A. Notation

Scalars are denoted lowercase letters, $x$, and vectors by the superscript $x^n$. The $i$-th elements of the vector $x^n$ is denoted by $x_i$. Random variables are denoted by capitals, $X$, and $n$-dimensional random vectors by $X^n$. We denote the distribution of the random vector $X^n$ by $P_{X^n}(\cdot)$, the associated probability measure by $\mathbb{P}_{X^n}(\cdot)$, and the expectation with respect to $P_{X^n}$ by $\mathbb{E}_{X^n}[\cdot]$. The mutual information between the random vectors $X^n$ on $\mathcal{X}^n$ and $Y^n$ on $\mathcal{Y}^n$ is given by

$$
I(X^n; Y^n) = \mathbb{E}_{X^n Y^n} [i(X^n; Y^n)], \quad (1)
$$

where

$$
i(x^n; y^n) = \log \frac{\mathrm{d}P_{Y^n|X^n}(Y^n|X^n)}{\mathrm{d}P_{Y^n}(Y^n)}, \quad x^n \in \mathcal{X}^n, y^n \in \mathcal{Y}^n \qquad (2)
$$

denotes the information density. The total variation distance between the distributions $P_{X^n}$ and $P_{Y^n}$ is denoted by $\|P_{X^n} - P_{Y^n}\|_{TV}$.

II. RISK-AVERSE INFERENCE

Consider an estimator $\psi_n : \mathcal{X}^n \to \Theta$ of a parameter $\theta^* \in \Theta$, where $\Theta \subseteq \mathbb{R}^d$. Suppose that data $X^n \in \mathcal{X}^n$ is drawn according to $P_{\hat{X}^n}$, where $\theta^*$ is unknown.

In applications, storage, privacy or communication constraints often mean that it is not possible
to directly access $X^n$ and instead only the processed data $\hat{X}^n$ is observed. In other words, $\hat{X}^n$
is obtained via a (possibly random) transformation $P_{\hat{X}^n|X^n} : \mathcal{X}^n \to \mathcal{X}^n$, $X^n \mapsto \hat{X}^n$. Given the
processed data $\hat{X}^n$, the resulting estimate of $\theta^*$ is then given by $\hat{\theta} = \psi_n(\hat{X}^n)$.

Let $\ell: \mathcal{X}^n \times \mathcal{X}^n \to \mathbb{R}_+$ be a measurable loss or error function. The quality of the estimator $\psi_n(\hat{X}^n)$ is given by a statistic of $\ell(\psi_n(\hat{X}^n), \theta^*)$. A common choice is the Bayes risk or expected loss:

$$
R_B = \mathbb{E}[\ell(\psi_n(\hat{X}^n), \theta^*)]. \tag{3}
$$

On the other hand, the mean is not the only statistic of practical relevance. In order to control
the probability of large errors, another choice of statistic is based on the excess loss probability,
given by

$$
P_e = \mathbb{P}(\ell(\psi_n(\hat{X}^n), \theta^*) > \delta), \quad (4)
$$
for a given $\delta > 0$.

In safe decision making, it is desirable to place stronger constraints on the tail of the loss probability distribution; namely, the probability distribution of $\ell(\psi_n(\hat{X}^n), \theta^*)$. A key example is the conditional value at risk (CVaR) [11]. In the case where the cumulative distribution function of $\ell(\psi_n(\hat{X}^n), \theta^*)$ is continuous, the CVaR at level $\alpha \in (0, 1)$ is given by

$$ \begin{aligned} & \mathrm{CVaR}_{\alpha}(\ell(\psi_n(\hat{X}^n), \theta^*)) \\ & = \mathbb{E}[\ell(\psi_n(\hat{X}^n), \theta^*) | \ell(\psi_n(\hat{X}^n), \theta^*) > l_{\alpha}], \end{aligned} \quad (5) $$

where $l_{\alpha} = \inf\{l : \mathbb{P}(\ell(\psi_n(\hat{X}^n), \theta^*) \le l) > \alpha\}$.

The Bayes risk, CVaR, and the value at risk (VaR) (closely related to the excess loss probability) are examples of a distortion risk measure [17]. As illustrated in Fig. 1, these quantities characterize different aspects of the behavior of the loss probability distribution tail.

**Definition 1.** Let $h: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function satisfying $h(0) = 0$ and $h(1) = 1$. The distortion risk measure parameterized by $h$ is defined as

$$ \rho_h(\ell(\psi_n(\hat{X}^n), \theta^*)) = \int_0^\infty h\left(\mathbb{P}(\ell(\psi_n(\hat{X}^n), \theta^*) > u)\right) du. \quad (6) $$

In particular, if $h(w) = w$, then

$$ \rho_h(\ell(\psi_n(\hat{X}^n), \theta^*)) = \mathbb{E}[\ell(\psi_n(\hat{X}^n), \theta^*)]. \quad (7) $$

On the other hand, if

$$ h(w) = \begin{cases} \frac{w}{1-\alpha}, & w < 1-\alpha \\ 1, & 1-\alpha \le w, \end{cases} \quad (8) $$

then

$$ \mathrm{CVaR}_{\alpha}(\ell(\psi_n(\hat{X}^n), \theta^*)) = \rho_h(\ell(\psi_n(\hat{X}^n), \theta^*)). \quad (9) $$

We are interested in controlling the risk measure

$$ \begin{aligned} & \rho_h(\ell(\psi_n(\hat{X}^n), \theta^*)) \\ & = \int_0^\infty h\left(\mathbb{P}\left(\ell(\psi_n(\hat{X}^n), \theta^*) > u\right)\right) du, \end{aligned} \quad (10) $$
where $h: \mathbb{R} \to \mathbb{R}$ is non-decreasing and satisfies $h(0) = 0$ and $h(1) = 1$. In the special case where $h(w) = w$, then we recover the expected loss

$$ \rho_h(\ell(\psi_n(\hat{X}^n), \theta^*)) = \mathbb{E}[\ell(\psi_n(\hat{X}^n), \theta^*)]. \quad (11) $$

<figure><img src="image_2.png" /><figcaption>Fig. 1: Illustration of different risk measures for a loss or distortion $D(X, \hat{X})$.</figcaption></figure>

### III. IMPACT OF DATA PROCESSING

Upstream data processing is often a key aspect of inference. In the context of risk-averse inference, data processing should not lead to a significant increase in the end-to-end performance measured in terms of the distortion risk measure $\rho_h(\ell(\psi_n(\hat{X}^n), \theta^*))$. We therefore seek to isolate the contribution of data processing. We first impose the following assumption on the loss function.

**Assumption 1.** The loss function $\ell: \Theta \times \Theta \to \mathbb{R}_+$, $(u, v) \mapsto \ell(u, v)$ is uniformly Lipschitz in $u$. That is, there exists $L < \infty$ such that for all $u_1, u_2 \in \Theta$,

$$ |\ell(u_1, v) - \ell(u_2, v)| \le L \|u_1 - u_2\|, \quad \forall v \in \Theta. \quad (12) $$

Observe that this assumption holds for $\ell(u, v) = \|u - v\|^2$ when $\Theta$ is bounded. A more general family of examples of loss functions satisfying Assumption 1 are provided by the following lemma.

**Lemma 1.** Suppose that $\ell(u, v)$ has bounded partial derivatives in $u$ for $u, v \in \Theta$. Then, Assumption 1 holds.
As $P_{X^n}$ is not known, the design of data processing is often based on an approximate probability distribution $P_{\tilde{X}^n}$. For example, it may be known that $P_{X^n} \in \{P \in \mathcal{P}(\mathcal{X}^n) : \|P_{X^n} - P_{\tilde{X}^n}\|_{\text{TV}} \le \kappa\}$ for a given $\kappa > 0$, where $\mathcal{P}(\mathcal{X}^n)$ is the set of probability distributions on the measurable space $(\mathcal{X}^n, \mathcal{B}(\mathcal{X}^n))$ with $\mathcal{B}(\mathcal{X}^n)$ the Borel $\sigma$-algebra for $\mathcal{X}^n$. We then have the following characterization of the end-to-end risk, which plays a similar role to the triangle inequality in the analysis of the expected loss.

**Theorem 1.** Let $\tilde{X}^n \sim P_{\tilde{X}^n}$ and $\ell_{\max} = \sup\{\ell(u, v) : u, v \in \Theta\}$. Suppose that Assumption 1 holds. Then,

$$ \rho_h(\ell(\psi_n(\hat{X}^n), \theta^*)) \\ \le 2\rho_{\tilde{h}}(L\|\psi_n(\hat{X}^n) - \psi_n(\tilde{X}^n)\|) + 2\rho_{\hat{h}}(\ell(\psi_n(X^n), \theta^*)) \\ + \int_0^{l_{\max}} \hat{h}(4\|P_{X^n} - P_{\tilde{X}^n}\|_{\text{TV}})du, \quad (13) $$

where $\hat{h}(w) = \min\{1, h(2w)\}$ and $\tilde{h}(w) = \min\{1, h(4w)\}$. Moreover, if $h$ is concave non-decreasing, then $\tilde{h}$ and $\hat{h}$ are also concave non-decreasing.

*Proof.* See Appendix A. □

**Remark 1.** Note that if $\mathbb{P}_{\tilde{X}^n}(A) \ne \mathbb{P}_{X^n}(A)$ on a set $A$ with non-zero measure, then we require that the loss function $\ell$ is bounded to ensure

$$ \int_0^{l_{\max}} \tilde{h}(4\|P_{X^n} - P_{\tilde{X}^n}\|_{\text{TV}})du < \infty. \quad (14) $$

In the case $\mathbb{P}_{X^n} = \mathbb{P}_{\tilde{X}^n}$, a.e., $\ell$ may be unbounded.

Theorem 1 provides a means of controlling the impact of data processing on the end-to-end risk. Indeed, the contribution of data processing is given by the term $\rho_{\hat{h}}(L\|\psi_n(\hat{X}^n) - \psi_n(\tilde{X}^n)\|)$. By controlling this term, the contribution of data processing can be constrained.

## IV. RISK-CONSTRAINED FIXED-LENGTH LOSSY COMPRESSION

A ubiquitous form of data processing is fixed-length lossy compression, where $\hat{X}^n$ is a quantized version of $X^n$. Ideally, the design of the compression scheme is based on the true data distribution $P_{X^n}$. However, in our setting $P_{X^n}$ is not perfectly known; indeed, the inference task aims to characterize $P_{X^n}$. Instead, we assume that a distribution $P_{\tilde{X}^n}$ is known such that $\|P_{\tilde{X}^n} - P_{X^n}\|_{\text{TV}} \le \kappa$. The design of the compression scheme is then based on $P_{\tilde{X}^n}$.
We focus on compression based on a fixed-length lossy source code of size $M \in \mathbb{N}$, which consists of:

(i) an encoder $P_{Z|\tilde{X}^n} : \mathcal{X}^n \to \{1, \dots, M\}$;

(ii) a decoder $P_{\tilde{X}^n|Z} : \{1, \dots, M\} \to \mathcal{X}^n$.

In general, the encoder and decoder may be probabilistic; i.e., $P_{Z|\tilde{X}^n}$ and $P_{\tilde{X}^n|Z}$ may be random transformations.

The performance of a fixed-length lossy source code is defined in terms of a distortion metric $D_{\psi_n} : \mathcal{X}^n \times \mathcal{X}^n \to \mathbb{R}_+$. Using Theorem 1, we choose

$$D_{\psi_n}(\tilde{X}^n, \hat{X}^n) = L \| \psi_n(\hat{X}^n) - \psi_n(\tilde{X}^n) \|. \quad (15)$$

Typically, the performance is given by the expected distortion [8] $\mathbb{E}[D_{\psi_n}(\tilde{X}^n, \hat{X}^n)]$ or, for a given $\delta > 0$, the excess distortion probability [16] $\mathbb{P}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > \delta)$. In order to control the impact of data processing in terms of the end-to-end risk measure, Theorem 1 suggests that the performance measure should be chosen as $\rho_{\tilde{h}}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n))$. This motivates the following definition.

**Definition 2.** Let $\tilde{h} : \mathbb{R} \to \mathbb{R}$ be a non-decreasing function satisfying $\tilde{h}(0) = 0$ and $\tilde{h}(1) = 1$. Given a source $P_{\tilde{X}^n}$ on $\mathcal{X}^n$, a $(M, \tilde{h}, D_{\psi_n}, \delta)$-code is the pair $(P_{Z|\tilde{X}^n}, P_{\tilde{X}^n|Z})$ such that

$$\rho_{\tilde{h}}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) \le \delta. \quad (16)$$

In the remainder of this section, we establish conditions for the existence of $(M, \tilde{h}, D_{\psi_n}, \delta)$-codes.

### A. Existence of $(M, \tilde{h}, D_{\psi_n}, \delta)$-Codes

Given $M, \tilde{h}$ and $D_{\psi_n}$ we establish upper (achievability) and lower (converse) bounds on achievable values of $\delta$ in Definition 2. These bounds hold for arbitrary distributions $P_{\tilde{X}^n}$ on $(\mathcal{X}^n, \mathcal{B}(\mathcal{X}^n))$. Note that classical rate-distortion theory [8], [18] establishes analogous bounds as $n \to \infty$ for $\tilde{h}(w) = w$ (i.e., Bayes risk constraints). In contrast, our bounds hold for finite $n$ and can be viewed as analogous to the bounds for the excess loss probability established in [16].
**Theorem 2 (Achievability).** Let $\tilde{h}: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function satisfying $\tilde{h}(0) = 0$ and $\tilde{h}(1) = 1$, and $P_{\tilde{X}^n}$ be a probability distribution on $\mathcal{X}$. Then, there exists a $(M, \tilde{h}, D_{\psi_n}, \delta)$-code such that

$$ \delta \le \inf_{P_{\tilde{Y}^n}} \int_0^\infty \tilde{h} \left( \mathbb{E}_{\tilde{X}^n} \left[ \left( \mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n) > u | \tilde{X}^n) \right)^M \right] \right) du, \quad (17) $$

where $Y^n$ is any random variable on $\mathcal{X}^n$, independent of $\tilde{X}^n$.

*Proof.* See Appendix B. □

**Theorem 3 (Converse).** Let $\tilde{h}: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function satisfying $\tilde{h}(0) = 0$ and $\tilde{h}(1) = 1$, $P_{\tilde{X}^n}$ be a probability distribution on $\mathcal{X}$, and $(P_{Z|\tilde{X}^n}, P_{\hat{X}^n|Z})$ be a $(M, \tilde{h}, D_{\psi_n}, \delta)$-code. Then,

$$ \delta \ge \sup_{u_{\max} \ge 0} \int_0^{u_{\max}} \tilde{h} \left( 1 - M \sup_{y^n \in \mathcal{X}^n} \mathbb{P}(D_{\psi_n}(\tilde{X}^n, y^n) \le u) \right) du. \quad (18) $$

*Proof.* See Appendix B. □

**Remark 2.** In the case $\tilde{h}(w) = w$, Theorems 2 and 3 provide upper and lower bounds on the Bayes risk $\mathbb{E}[D_{\psi_n}(\tilde{X}^n, \hat{X}^n)]$.

**Remark 3.** An alternative converse bound can also be obtained via the hypothesis testing method in [16]. Indeed, under the assumption that $\tilde{h}$ is concave, for $w > 0$,

$$ \begin{aligned} \rho_h(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) &\ge \mathbb{E}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) \\ &\ge w \mathbb{P}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > w). \end{aligned} \quad (19) $$

Hence, a $(M, \tilde{h}, D_{\psi}, \delta)$ code satisfies

$$ \mathbb{P}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > w) \le \frac{\delta}{w}. \quad (20) $$

Applying [16, Theorem 8], then yields (see Appendix B for additional details)

$$ M \ge \sup_{w \in \mathbb{R}_+} \sup_{Q_{\tilde{X}^n}} \inf_{y^n \in \mathcal{X}^n} \frac{\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n})}{\mathbb{Q}_{\tilde{X}^n}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) \le w)}, \quad (21) $$

where $Q_{\tilde{X}^n}$ is any probability distribution on $\mathcal{X}^n$ and $\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n})$ (defined precisely in Appendix B) is the minimum type-II error probability associated with a hypothesis test between $P_{\tilde{X}^n}$ and $Q_{\tilde{X}^n}$ subject to a type-I error constraint of $1 - \frac{\delta}{w}$. In Sec. V, we show that Theorem 3 can be tighter than (21). This is expected as the bound in (21) does not take into account the impact of $\tilde{h}$ in the risk measure constraint.
## B. Asymptotics

We now turn to constraints on the size of the fixed-length source code as $n \to \infty$. As is standard in the asymptotic analysis of compression schemes, we impose the following assumptions.

**Assumption 2.** The following hold:

(i) (i.i.d. Data) For all $n$, $P_{\tilde{X}^n}(x^n) = \prod_{i=1}^n P_{\tilde{X}}(x_i)$, $x^n \in \mathcal{X}^n$.

(ii) (Separable Distortion) There exists $d: \mathcal{X} \times \mathcal{X} \to \mathbb{R}_+$ such that

$$D_{\psi_n}(\tilde{x}^n, \hat{x}^n) = \frac{1}{n} \sum_{i=1}^{n} d(\tilde{x}_i, \hat{x}_i). \qquad (22)$$

We also impose the following technical condition on the parameter function $\tilde{h}$ of the risk measure $\rho_{\tilde{h}}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n))$.

**Assumption 3.** $\tilde{h}: \mathbb{R} \to \mathbb{R}$ satisfies $\tilde{h}(0) = 0$, $\tilde{h}(1) = 1$, and is non-decreasing and Lipschitz continuous.

As $n \to \infty$, the key quantity characterizing the performance of a compression scheme is the achievable rate subject to the risk constraints. In standard rate-distortion theory, the goal is to characterize the tradeoff between the rate and the expected loss, leading to the rate-distortion function. In the presence of risk constraints, we are lead to an analogous quantity, called the rate-risk function.

**Definition 3.** Fix $\delta$ and the data dimension $n$. We define

$$M^*(n, \tilde{h}, d, \delta) = \min\{M : \exists(n, M, \tilde{h}, d, \delta) \text{ code}\} \qquad (23)$$

and

$$R(n, \tilde{h}, d, \delta) = \frac{\log M^*(n, \tilde{h}, d, \delta)}{n}. \qquad (24)$$

The rate-risk function is defined as

$$\bar{R}(\tilde{h}, d, \delta) = \limsup_{n \to \infty} R(n, \tilde{h}, d, \delta). \qquad (25)$$

In the following theorem, we characterize the rate-risk function.

**Theorem 4.** Suppose there exists $B < \infty$ such that $D_{\psi}(x, y) \le B$, $\forall x, y \in \mathcal{X}$. Let

$$\phi(\delta) = \inf_{\substack{P_{Y|X}: \\ \mathbb{E}[d(X,Y)] \le \delta}} I(X; Y), \qquad (26)$$
and $\delta_0 = \inf\{\delta : \phi(\delta) < \infty\}$. If Assumption 3 holds and $\delta > \delta_0$, then

$$ \bar{R}(\tilde{h}, d, \delta) = \phi(\delta). \qquad (27) $$

*Proof.* See Appendix B. □

An inspection of Theorem 4 shows that the $\bar{R}(\tilde{h}, d, \delta)$ does not depend on $\tilde{h}$. A rough intuition for this observation is that distortion risk measures can be thought of as distorted expectations, and hence we can apply a similar argument as in the expected distortion case. However, regularity of the function $\tilde{h}$ is also required for this to be made rigorous, as can be seen in the proof in Appendix B.

## V. NUMERICAL EXAMPLE

In this section, we present a numerical example to illustrate the bounds in the previous sections. Consider the scenario with binary data, where $\mathcal{X}^n = \{0, 1\}^n$ and $\mathbb{P}(\tilde{X}^n = x^n) = 2^{-n}$. Note that $P_{\tilde{X}^n}$ is not the true data distribution, and is only the distribution utilized to construct the fixed-length source code. We assume that the true data distribution $P_{X^n}$ satisfies

$$ \|P_{\tilde{X}^n} - P_{X^n}\|_{\text{TV}} \le \kappa, \qquad (28) $$

for some $\kappa > 0$. Moreover, we assume that

$$ \psi_n(x^n) = \frac{1}{n} \sum_{i=1}^{n} x_i, \quad x^n \in \{0, 1\}^n. \qquad (29) $$

Hence,

$$ \begin{aligned} |\psi_n(\hat{X}^n) - \psi_n(\tilde{X}^n)| &\le \frac{1}{n} \sum_{i=1}^{n} |\hat{X}_i - \tilde{X}_i| \\ &= \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{\hat{X}_i \ne \tilde{X}_i\}. \end{aligned} \qquad (30) $$

We then write

$$ D_{\psi_n}(x^n, y^n) = \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{x_i \ne y_i\}, \quad x^n, y^n \in \{0, 1\}^n, \qquad (31) $$

with $d(x_i, y_i) = \mathbf{1}\{x_i \ne y_i\}$, $x_i, y_i \in \{0, 1\}$.
Let $\ell: [0, 1] \times [0, 1] \to \mathbb{R}_+$ be a loss function with Lipschitz constant $L = 1$, and $h: \mathbb{R} \to \mathbb{R}$ satisfy the conditions in Definition 1 and Theorem 1. Setting $L = 1$ and using (28) in Theorem 1, we then have

$$ \begin{aligned} & \rho_h(\ell(\psi_n(\hat{X}^n), \theta^*)) \\ & \le 2\rho_{\tilde{h}}(D_{\psi_n}(\hat{X}^n, \tilde{X}^n)) + 2\rho_{\tilde{h}}(\ell(\psi_n(X^n), \theta^*)) \\ & \quad + l_{\max}\tilde{h}(4\kappa). \end{aligned} \quad (32) $$

Let

$$ \begin{pmatrix} n \\ k \end{pmatrix} = \sum_{j=0}^{k} \begin{pmatrix} n \\ j \end{pmatrix} \quad (33) $$

where $\begin{pmatrix} n \\ k \end{pmatrix} = 0$ if $k < 0$ and $\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n \\ n \end{pmatrix}$ if $k > n$. We now specialize the bounds in Theorems 2,3, and 4. Proofs of the following propositions are provided in the Appendix.

**Proposition 1 (Achievability).** Let $h: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function with $h(0) = 0$ and $h(1) = 1$. Then, there exists a $(M, h, D_{\psi_n}, \delta)$ code such that

$$ \delta \le \int_{0}^{\infty} h \left( \left( 1 - 2^{-n} \begin{pmatrix} n \\ \lfloor nu \rfloor \end{pmatrix} \right)^{M} \right) du. \quad (34) $$

**Proposition 2 (Converse).** Let $h: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function with $h(0) = 0$ and $h(1) = 1$, and $(P_{Z|\tilde{X}^n}, P_{\tilde{X}^n|Z})$ be a $(M, h, D_{\psi_n}, \delta)$-code. Then,

$$ \delta \ge \sup_{u_{\max} \ge 0} \int_{0}^{u_{\max}} h \left( 1 - 2^{-n} M \begin{pmatrix} n \\ \lfloor nu \rfloor \end{pmatrix} \right) du. \quad (35) $$

The following converse follows immediately from [16] and Remark 3.

**Proposition 3.** Let $P_{\tilde{X}^n}$ be the stationary equiprobable binary source, $\tilde{h}: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function with $\tilde{h}(0) = 0$ and $\tilde{h}(1) = 1$, $(P_{Z|\tilde{X}^n}, P_{\tilde{X}^n|Z})$ be a $(M, \tilde{h}, D_{\psi_n}, \delta)$ code and $w \in \mathbb{R}_+$. Then,

$$ \delta \ge w \left( 1 - 2^{-n} M \begin{pmatrix} n \\ \lfloor nw \rfloor \end{pmatrix} \right). \quad (36) $$

Fig 2 and Fig. 3 plot the bounds for the CVaR risk measure with $\alpha = 0.1$ and $M = 1000$. Observe that our converse in Proposition 2 is tighter than the converse using the hypothesis testing method in Proposition 3. We also observe that the impact of utilizing the modified risk measure $\tilde{h}$ is an increase in $\delta$. This is expected as $\tilde{h}$ places a higher weight on $\mathbb{P}(D_{\psi}(\tilde{X}^n, \hat{X}^n) > u)$ for all values of $u$.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Plot of bounds with $M = 1000$ and CVaR risk distortion function $h$ with $\alpha = 0.1$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3: Plot of bounds with $M = 1000$ and modified CVaR risk distortion function $\tilde{h}$ with $\alpha = 0.1$.</figcaption></figure>

# VI. CONCLUSIONS

Large errors in data processing, such as compression, upstream from an inference task can be catastrophic in applications involving safe control and learning. In these applications, it is desirable to introduce risk measure constraints on the loss distribution. To this end, we introduced a general framework to characterize the impact of data processing on end-to-end risk measure criteria for inference tasks. We established new bounds on achievable risk measure constraints
in fixed-length lossy compression for a general family of risk measures and finite dimensional data.

ACKNOWLEDGMENTS

This work was partially supported by the French National Agency for Research (ANR) via the project ANR-22-PEFT-0010 of the France 2030 program PEPR réseaux du Futur, and the project ANR-24-CE25-2256 TCDTP.

APPENDIX A

PROOFS FOR SEC. III

A. Proof of Theorem 1

We now prove Theorem 4. Recall Assumption 1.

**Assumption 4.** The loss function $\ell: \Theta \times \Theta \to \mathbb{R}_+$, $(u, v) \mapsto \ell(u, v)$ is uniformly Lipschitz in $u$. That is, there exists $L < \infty$ such that for all $u_1, u_2 \in \Theta$,

$$|\ell(u_1, v) - \ell(u_2, v)| \le L \|u_1 - u_2\|, \quad \forall v \in \Theta. \qquad (37)$$

In order to prove Theorem 1, we first establish the following lemmas.

**Lemma 2.** Suppose that Assumption 4 holds. Then,

$$\ell(\psi_n(\hat{X}^n), \theta^*) \le L \|\psi_n(\hat{X}^n) - \psi_n(X^n)\| + \ell(\psi_n(X^n), \theta^*). \qquad (38)$$

Proof.

$$\begin{align*}
\ell(\psi_n(\hat{X}^n), \theta^*) &\le |\ell(\psi_n(\hat{X}^n), \theta^*) - \ell(\psi_n(X^n), \theta^*)| \\
&\quad + \ell(\psi_n(X^n), \theta^*) \\
&\le L \|\psi_n(\hat{X}^n) - \psi_n(X^n)\| + \ell(\psi_n(X^n), \theta^*). \tag{39}
\end{align*}$$

□

**Lemma 3.** Let A, B be two positive real-valued random variables and $h: \mathbb{R} \to \mathbb{R}$ be a non-decreasing function. Then,

$$\rho_h(A + B) \le 2\rho_{\hat{h}}(A) + 2\rho_{\hat{h}}(B), \qquad (40)$$

where $\hat{h}(w) = \min\{1, h(2w)\}$.
Proof.

$$
\begin{align*}
\rho_h(A + B) \\
&= \int_0^\infty h(\mathbb{P}(A + B > u))du \\
&\le \int_0^\infty h(\mathbb{P}(\max\{A, B\} > u/2))du \\
&= \int_0^\infty h(\mathbb{P}(\{A > u/2\} \cup \{B > u/2\}))du \\
&\le \int_0^\infty \min\{1, h(\mathbb{P}(A > u/2) + \mathbb{P}(B > u/2))\}du \\
&\le \int_0^\infty \min\{1, h(\max\{2\mathbb{P}(A > u/2), 2\mathbb{P}(B > u/2)\})\}du \\
&\le \int_0^\infty \min\{1, h(2\mathbb{P}(A > u/2))\}du \\
&\quad + \int_0^\infty \min\{1, h(2\mathbb{P}(B > u/2))\}du. \tag{41}
\end{align*}
$$

Letting $\hat{h}(w) = \min\{1, h(2w)\}$ and applying the change of variables $u \mapsto u/2$ yields the desired result. $\square$

**Lemma 4.** Suppose the assumptions in Theorem 1 hold. Then,

$$
\begin{align}
\rho_{\tilde{h}}(D_{\psi_n}(X^n, \hat{X}^n)) &\le \rho_{\tilde{h}}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) \nonumber \\
&\quad + \int_0^\infty \tilde{h}(4\|P_X - P_{\tilde{X}}\|_{\text{TV}})du, \tag{42}
\end{align}
$$

where $\tilde{h}(w) = \min\{1, h(4w)\}$.

Proof.

$$
\begin{align*}
\rho_{\tilde{h}}(D_{\psi_n}(X^n, \hat{X}^n)) \\
&= \int_0^\infty \tilde{h} \left( \mathbb{E}_{X^n} \left[ \mathbb{P}(D_{\psi_n}(X^n, \hat{X}^n) > u | X^n) \right] \right) du \\
&\le \int_0^\infty \tilde{h} \left( \mathbb{E}_{\tilde{X}^n} \left[ \mathbb{P}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > u | \tilde{X}^n) \right] \right. \\
&\qquad \left. + 2 \| P_{X^n} - P_{\tilde{X}^n} \|_{\text{TV}} \right) du \\
&\le \int_0^\infty \tilde{h} \left( \max \left\{ 2 \mathbb{E}_{\tilde{X}^n} \left[ \mathbb{P}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > u | \tilde{X}^n) \right], \right. \right. \\
&\qquad \left. 4 \| P_{X^n} - P_{\tilde{X}^n} \|_{\text{TV}} \right) du
\end{align*}
$$
$$ \leq \int_{0}^{\infty} \tilde{h} \left( 2 \mathbb{E}_{\tilde{X}^n} \left[ \mathbb{P} \left( D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > u | \tilde{X}^n \right) \right] \right) du \\ + \int_{0}^{\infty} \tilde{h} (4 \| P_{X^n} - P_{\tilde{X}^n} \|_{\text{TV}}) du. \qquad (43) $$

□

Combining the previous lemmas yields the bound Theorem 1. Concavity of $\tilde{h}$ is due to the observation that if $h(w)$ is concave non-decreasing, then $h(4w)$ is also concave non-decreasing:

$$ \begin{aligned} & h(4(\lambda w_1 + (1 - \lambda)w_2)) \\ & = h(\lambda 4w_1 + (1 - \lambda)4w) \geq \lambda h(4w_1) + (1 - \lambda)h(4w_2), \end{aligned} \qquad (44) $$

by concavity of $h$.

# APPENDIX B

## PROOFS FOR SEC. IV

### A. Proof of Theorem 2

Consider the codewords $\{Y_1, \dots, Y_M\}$ drawn i.i.d. from $P_Y$, and the encoding rule

$$ j^* \in \arg \min_{j=1,\dots,M} D_{\psi_n}(X, Y_j), \qquad (45) $$

where ties are broken arbitrarily. Then,

$$ \begin{aligned} & \mathbb{E}_{Y_1, \dots, Y_M} \left[ \int_0^\infty \tilde{h} \left( \mathbb{P} \left( D(X, \hat{X}) > u \right) \right) du \right] \\ & \stackrel{(a)}{\leq} \int_0^\infty \tilde{h} \left( \mathbb{E}_X \left[ \mathbb{E} \left[ \prod_{j=1}^M 1\{D(X, Y_j) > u\} \mid X \right] \right] \right) du \\ & \stackrel{(b)}{=} \int_0^\infty \tilde{h} \left( \mathbb{E}_X \left[ \left( \mathbb{P}(D_{\psi_n}(X, Y) > u | X) \right)^M \right] \right) du, \end{aligned} \qquad (46) $$

where (a) follows from the concavity of $\tilde{h}$ and Jensen's inequality, and (b) follows from the fact that $Y_1, \dots, Y_M$ are i.i.d. and independent of $X$.

It then follows that there exists a $(M, \tilde{h}, D_{\psi_n}, \delta)$-code<fnref n="1" /> satisfying

$$ \delta \leq \inf_{P_Y} \int_0^\infty \tilde{h} \left( \mathbb{E}_X \left[ \left( \mathbb{P}(D_{\psi_n}(X, Y) > u | X) \right)^M \right] \right) du, \qquad (47) $$

as required.

<footnote n="1">¹Often known as Shannon's random coding argument; see, e.g., [16].</footnote>
## B. Proof of Theorem 3

By assumption,

$$ \delta \geq \int_{0}^{\infty} \tilde{h} \left( \mathbb{P}(D_{\psi_n}(X, \hat{X}) > u) \right) du. \quad (48) $$

Let $u_{\max} \geq 0$. Then,

$$
\begin{align*}
\delta &\geq \int_{0}^{u_{\max}} \tilde{h} \left( \sum_{z=1}^{M} \frac{1}{M} - \sum_{x} \sum_{z=1}^{M} \sum_{y} P_X(x) P_{Z|X}(z|x) P_{\hat{X}|Z}(y|z) \mathbf{1}\{D_{\psi_n}(x, y) \leq u\} \right) du \\
&\stackrel{(a)}{\geq} \frac{1}{M} \sum_{z=1}^{M} \int_{0}^{u_{\max}} \tilde{h} \left( 1 - M \sum_{x} \sum_{y} P_X(x) P_{Z|X}(z|x) P_{\hat{X}|Z}(y|z) \mathbf{1}\{D_{\psi_n}(x, y) \leq u\} \right) du \\
&\stackrel{(b)}{\geq} \frac{1}{M} \sum_{z=1}^{M} \int_{0}^{u_{\max}} \tilde{h} \left( 1 - M \sum_{y} P_{\hat{X}|Z}(y|z) \sum_{x} P_X(x) \mathbf{1}\{D_{\psi_n}(x, y) \leq u\} \right) du \\
&\geq \frac{1}{M} \sum_{z=1}^{M} \int_{0}^{u_{\max}} \tilde{h} \left( 1 - M \sup_{y} \mathbb{P}(D_{\psi_n}(X, y) \leq u) \right) du \\
&= \int_{0}^{u_{\max}} \tilde{h} \left( 1 - M \sup_{y} \mathbb{P}(D_{\psi_n}(X, y) \leq u) \right) du, \tag{49}
\end{align*}
$$

where (a) follows from the concavity of $\tilde{h}$ and Jensen's inequality, and (b) follows from the fact that $P_{Z|X}(z|x) \leq 1$.

As the choice of $u_{\max}$ is arbitrary, it follows that

$$ \delta \geq \sup_{u_{\max} \geq 0} \int_{0}^{u_{\max}} \tilde{h} \left( 1 - M \sup_{y} \mathbb{P}(D_{\psi_n}(X, y) \leq u) \right) du, \quad (50) $$

as required.

## C. Discussion of Remark 3

We now prove (21) in Remark 3, which provides another converse bound using the hypothesis testing method in [16].

**Theorem 5.** Let $\tilde{h}: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function with $\tilde{h}(0) = 0$ and $\tilde{h}(1) = 1$, $P_{\tilde{X}^n}$ be a source on $\mathcal{X}$, and $(P_{Z|\tilde{X}^n}, P_{\tilde{X}^n|Z})$ be a $(M, \tilde{h}, D_{\psi_n}, \delta)$ code. Then,

$$ M \geq \sup_{w \in \mathbb{R}_+} \sup_{Q_{\tilde{X}^n}} \inf_{y^n} \frac{\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n})}{Q_{\tilde{X}^n}(D_{\psi_n}(\tilde{X}^n, y^n) \leq w)}, \quad (51) $$

where $Q_{\tilde{X}^n}$ is any distribution on $\mathcal{X}$ and $\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n})$ is defined in (53).
Proof. Let $Q_{\tilde{X}^n}$ be a comparison distribution on $\mathcal{X}$ and $w \in \mathbb{R}_+$. Define the hypothesis test

$$ 
\begin{aligned}
\mathcal{H}_0: \tilde{X}^n &\sim Q_{\tilde{X}^n} \\
\mathcal{H}_1: \tilde{X}^n &\sim P_{\tilde{X}^n}.
\end{aligned} 
\qquad (52) 
$$

Let $W \in \{0, 1\}$ be the decision variable. By the Neyman-Pearson lemma, the minimum type-II error probability subject to a type-I error constraint is given by

$$ \beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n}) = \min_{\substack{P_{W|\tilde{X}^n}: \\ \mathbb{P}_{\tilde{X}^n}(W=1) \ge 1-\frac{\delta}{w}}} \mathbb{Q}_{\tilde{X}^n}(W=1). \qquad (53) $$

Consider the sub-optimal decision rule

$$ W = \mathbf{1} \left\{ \int_{0}^{\infty} \tilde{h} \left( \mathbf{1}\{D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > u\} \right) du \le w \right\}. \qquad (54) $$

Then,

$$ 
\begin{aligned}
\mathbb{P}_{\tilde{X}^n}(W=1) &= \mathbb{P}_{\tilde{X}^n} \left( \int_0^\infty \tilde{h} \left( \mathbf{1}\{D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > u\} \right) du \le w \right) \\
&\stackrel{(a)}{\ge} 1 - \frac{1}{w} \mathbb{E} \left[ \int_0^\infty \tilde{h} \left( \mathbf{1}\{D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > u\} \right) du \right] \\
&\stackrel{(b)}{\ge} 1 - \frac{1}{w} \int_0^\infty \tilde{h}(\mathbb{P}_{\tilde{X}^n}(D(\tilde{X}^n, \hat{X}^n) > u)) du \\
&\stackrel{(c)}{\ge} 1 - \frac{\delta}{w},
\end{aligned} 
\qquad (55) 
$$

where (a) follows from the Markov inequality, (b) exploits concavity of $h$, and (c) utilizes the assumption that $(P_{Z|\tilde{X}^n}, P_{\hat{X}^n|Z})$ is a $(M, \tilde{h}, D_{\psi_n}, \delta)$ code. As such, this decision rule satisfies the feasibility constraint.

We then have 2

$$ 
\begin{aligned}
\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n}) &\le \mathbb{Q}_{\tilde{X}^n}(W=1) \\
&= \sum_{x^n} \sum_{z=1}^{M} \sum_{y^n} Q_{\tilde{X}^n}(x^n) P_{Z|\tilde{X}^n}(z|x^n) P_{\hat{X}^n|Z}(y^n|z) \mathbf{1} \left\{ \int_0^\infty \tilde{h} \left( \mathbf{1}\{D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > u\} \right) du \le w \right\} \\
&\le M \sup_{y^n} \mathbb{Q}_{\tilde{X}^n} \left( \int_0^\infty \tilde{h} \left( \mathbf{1}\{D_{\psi_n}(\tilde{X}^n, y^n) > u\} \right) du \le w \right) \\
&= M \sup_{y^n} \mathbb{Q}_{\tilde{X}^n} \left( \int_0^\infty \mathbf{1}\{D_{\psi_n}(X^n, y) \le u\} du \le w \right) \\
&= M \sup_{y^n} \mathbb{Q}_{\tilde{X}^n} (D_{\psi_n}(\tilde{X}^n, y^n) \le w).
\end{aligned} 
\qquad (56) 
$$

<footnote n="2">²Note that the same analysis applies for continuous sources, where the sums are replaced by integrals and densities replace the probability mass functions.</footnote>
As the choices of $Q_{\tilde{X}^n}$ and $w$ are arbitrary, it follows that

$$ M \geq \sup_{w \in \mathbb{R}_+} \sup_{Q_{\tilde{X}^n}} \inf_{y^n} \frac{\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n})}{\mathbb{Q}_{\tilde{X}^n}(D_{\psi_n}(\tilde{X}^n, y^n) \leq w)}. \quad (57) $$

As mentioned in Remark 3, an alternative method to prove Theorem 5 is to directly utilize the converse bound in [16, Theorem 8] for the case of excess distortion probability constraints. Indeed, under the assumption that $\tilde{h}$ is concave, for $w > 0$,

$$ \begin{aligned} \rho_h(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) &\geq \mathbb{E}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) \\ &\geq w \mathbb{P}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > w). \end{aligned} \quad (58) $$

Hence, a $(M, \tilde{h}, D_\psi, \delta)$ code satisfies

$$ \mathbb{P}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n) > w) \leq \frac{\delta}{w}. \quad (59) $$

Applying [16, Theorem 8], then yields (57).

### D. Proof of Theorem 4

We recall the following assumption.

**Assumption 5.** $\tilde{h}: \mathbb{R} \to \mathbb{R}$ satisfies $\tilde{h}(0) = 0$, $\tilde{h}(1) = 1$, and is non-decreasing and Lipschitz continuous.

(Converse:) Let $(P_{Z|\tilde{X}^n}, P_{\tilde{X}^n|Z})$ be a $(n, M, \tilde{h}, d, \delta)$ code. Observe that $X^n \to Z \to \hat{X}^n$ forms a Markov chain. Following a standard argument (see, e.g., [8]), we have

$$ \begin{aligned} \log M &\geq H(Z) \\ &\geq I(\tilde{X}^n; Z) \\ &\geq I(\tilde{X}^n; \hat{X}^n) \\ &= H(\tilde{X}^n) - H(\tilde{X}^n|\hat{X}^n) \\ &= \sum_{i=1}^{n} H(\tilde{X}_i) - \sum_{i=1}^{n} H(\tilde{X}_i|\hat{X}^n, \tilde{X}_{i-1}, \dots, \tilde{X}_1) \\ &\geq \sum_{i=1}^{n} H(\tilde{X}_i) - \sum_{i=1}^{n} H(\tilde{X}_i|\hat{X}_i) \end{aligned} $$
$$
\begin{align}
&= \sum_{i=1}^{n} I(\tilde{X}_i | \hat{X}_i) \nonumber \\
&\ge \sum_{i=1}^{n} \phi(\mathbb{E}[d(\tilde{X}_i, \hat{X}_i)]) \nonumber \\
&\ge n\phi(\delta). \tag{60}
\end{align}
$$

Hence,

$$
\frac{\log M}{n} \geq \phi(\delta). \tag{61}
$$

(Achievability:) Consider the codebook {$Y_1^n, \dots, Y_M^n$}, where $Y_{i,j} \sim P_Y$ are i.i.d. Define the
encoding rule

$$
i^* \in \arg \min_{i=1,\dots,M} D_{\psi_n}(\tilde{X}^n, Y_i^n), \quad (62)
$$

where ties are broken arbitrarily.

Let $\gamma > 0$, $\hat{X}^n = Y_{i^*}^n$ and set $Y^n \sim \prod P_Y$. We then have

$$
\begin{align}
& \rho_h(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) \notag \\
& \le \int_0^B \tilde{h} \left( \mathbb{E} \left[ \left( \mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n) > u | \tilde{X}^n) \right)^M \right] \right) du \notag \\
& \le \int_0^B \tilde{h} \left( \mathbb{E} \left[ e^{-M/\gamma} + \mathbb{P}(i(\tilde{X}^n; Y^n) > \log \gamma | \tilde{X}^n) \right. \right. \notag \\
& \phantom{\le \int_0^B \tilde{h} \left( \mathbb{E} \left[ \right.} \left. \left. + \mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n) > u | \tilde{X}^n) \right] \right) du, \tag{63}
\end{align}
$$

which follows from the proof of [19, Theorem 25.2].

Let $\epsilon > 0$ and set $\tilde{X} \sim P_{\tilde{X}}$, $Y \sim P_Y$,

$$
\begin{align}
\log M &= n(I(\tilde{X}; Y) + 2\epsilon) \notag \\
\log \gamma &= n(I(\tilde{X}; Y) + \epsilon). \tag{64}
\end{align}
$$
It then follows that

$$
\begin{align}
& \rho_{\tilde{h}}(D_{\psi_n}(\tilde{X}^n, \hat{X}^n)) \nonumber \\
& \le \int_0^B \tilde{h} (\exp(-\exp(n\epsilon)) \nonumber \\
& \qquad + \mathbb{P} \left( \frac{1}{n} \sum_{i=1}^n i(\tilde{X}_i; Y_i) > I(\tilde{X}; Y) + \epsilon \right) \nonumber \\
& \qquad + \mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n) > u) ) \, du \nonumber \\
& = \int_0^B \tilde{h} (D_{\psi_n}(\tilde{X}^n, Y^n) > u + t_n(u)) \, du, \tag{65}
\end{align}
$$

where $t_n(u) \to 0$ as $n \to \infty$ by the weak law of large numbers.

By Assumption 5,

$$
\begin{equation}
\begin{aligned}
& \left| h\left(\mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n)) + t_n(u)\right) - h\left(\mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n))\right) \right| \\
& \leq L t_n(u).
\end{aligned}
\tag{66}
\end{equation}
$$

Moreover, $t_n(u) \le T_n < \infty$ with $T_n \to 0$ for all $n$. Hence,

$$
\int_0^B Lt_n(u)du \le BLT_n \to 0. \quad (67)
$$

Fix $\epsilon > 0$. Take any $P_{Y|\tilde{X}}$ such that for $(\tilde{X}^n, Y^n) \sim \prod_{i=1}^n P_{Y|\tilde{X}} P_{\tilde{X}}$,

$$
\rho_{\tilde{h}}(D_{\psi_n}(\tilde{X}^n, Y^n)) \leq \delta - \epsilon. \quad (68)
$$

Such a $P_{Y|\tilde{X}}$ exists since $\delta > \delta_0$. As such, there exists a $(n, M, \tilde{h}, d, \delta)$ code satisfying

$$
\int_0^\infty h\left(\mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n) > u)\right) du \le \delta - \epsilon + o(1), \quad (69)
$$

and

$$
\log M = n(I(\tilde{X}; Y) + 2\epsilon). \tag{70}
$$

Letting $n \to \infty$, $\epsilon \to 0$, and using the continuity of $\phi(\delta)$ on $(\delta_0, \infty)$ [19, Theorem 24.4], we obtain the desired result.
# APPENDIX C

## PROOFS FOR SEC. V

Consider the stationary equiprobable binary source $P_{X^n}$ on $\{0, 1\}^n$ with $\mathbb{P}(X^n = x^n) = 2^{-n}$ and distortion metric

$$D(x^n, y^n) = \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\{x_i \neq y_i\}. \qquad (71)$$

Let

$$\begin{bmatrix} n \\ k \end{bmatrix} = \sum_{j=0}^{k} \begin{pmatrix} n \\ j \end{pmatrix} \qquad (72)$$

where $\begin{bmatrix} n \\ k \end{bmatrix} = 0$ if $k < 0$ and $\begin{bmatrix} n \\ k \end{bmatrix} = \begin{bmatrix} n \\ n \end{bmatrix}$ if $k > n$.

### A. Proof of Proposition 1

By concavity of $(1-x)^M$ for $x \in [0, 1]$, it follows that for any $P_{Y^n}$ on $\{0, 1\}^n$,

$$\begin{align}
& \int_0^\infty \tilde{h} \left( \mathbb{E}_{\tilde{X}^n} \left[ \left( 1 - \mathbb{P}(D_{\psi_n}(\tilde{X}^n, Y^n) \le u | \tilde{X}^n) \right)^M \right] \right) \mathrm{d}u \nonumber \\
& \ge \int_0^\infty \tilde{h} \left( \left( 1 - \mathbb{E}_{\tilde{X}^n} \left[ \mathbb{P} \left( D_{\psi_n}(\tilde{X}^n, Y^n) \le u | \tilde{X}^n \right) \right] \right)^M \right) \mathrm{d}u. \tag{73}
\end{align}$$

Observe that equality is achieved when $Y^n$ is equiprobable yields the desired result. The desired result follows immediately by combining this observation with Theorem 2.

### B. Proof of Proposition 2

Observe that

$$\sup_{y^n \in \{0,1\}^n} \mathbb{P}(D_{\psi_n}(\tilde{X}^n, y^n) \le u) = \mathbb{P}(D_{\psi_n}(\tilde{X}^n, 0) \le u) = 2^{-n} \begin{bmatrix} n \\ \lfloor nu \rfloor \end{bmatrix}. \qquad (74)$$

Applying Theorem 3 then yields the desired result.

We also establish the following proposition, which gives a converse bound based on (21) in Remark 3.

**Proposition 4.** Let $P_{\tilde{X}^n}$ be the stationary equiprobable binary source, $\tilde{h}: \mathbb{R} \to \mathbb{R}$ be a concave non-decreasing function with $\tilde{h}(0) = 0$ and $\tilde{h}(1) = 1$, $(P_{Z|\tilde{X}^n}, P_{\tilde{X}^n|Z})$ be a $(M, \tilde{h}, D_{\psi_n}, \delta)$ code and $w \in \mathbb{R}_+$. Then,

$$\delta \ge w \left( 1 - 2^{-n} M \begin{bmatrix} n \\ \lfloor nw \rfloor \end{bmatrix} \right). \qquad (75)$$
*Proof.* Applying Theorem 5, we have

$$
\begin{align*}
M &\ge \sup_{Q_{\tilde{X}^n}} \inf_{y^n \in \{0,1\}^n} \frac{\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, Q_{\tilde{X}^n})}{Q_{\tilde{X}^n}(D_{\psi_n}(\tilde{X}^n, y^n) \le w)} \\
&\ge \inf_{y^n \in \{0,1\}^n} \frac{\beta_{1-\frac{\delta}{w}}(P_{\tilde{X}^n}, P_{\tilde{X}^n})}{P_{\tilde{X}^n}(D_{\psi_n}(\tilde{X}^n, y^n) \le w)} \\
&= \frac{1-\frac{\delta}{w}}{P(D_{\psi_n}(\tilde{X}^n, 0) \le w)} \\
&= \frac{1-\frac{\delta}{w}}{2^{-n \langle \frac{n}{[nw]} \rangle}}. \tag{76}
\end{align*}
$$

Re-arranging this bound then yields the desired result.

<figure><img src="image_5.png" /></figure>

APPENDIX D

ADDITIONAL NUMERICAL RESULTS

In this section, we provide additional numerical results illustrating the propositions in the
previous section. We focus on the quadratic risk measure introduced in [17], which is defined
as follows.

**Definition 4 (Quadratic Risk Measure).** The quadratic risk measure is a distortion risk measure with

$$
h(w) = w + k(w - w^2), \quad k \in [0, 1]. \tag{77}
$$

Note that *h* in (77) is concave and differentiable.

We note that on $\mathbb{R}$, $h(w) = w + k(w - w^2)$ is not a non-decreasing function. Nevertheless, the function $g(w) = \min\{w, 1\} + k(\min\{w, 1\} - \min\{w, 1\}^2)$ satisfies $g(w) = h(w)$, $w \in [0, 1]$. The corresponding modified risk measure arising in Theorem 1 is given by

$$
\tilde{h}(w) = \min\{1, \min\{4w, 1\} + k(\min\{4w, 1\} - (\min\{4w, 1\})^2)\}. \quad (78)
$$

Fig 4 plots the bounds for the quadratic risk measure with $k = 0$ and $M = 1000$, corresponding
to an expectation constraint. Consistent with the CVaR example in Fig. 2, our converse in
Proposition 2 is tighter than the converse using the hypothesis testing method in Proposition 3.
Utilizing the modified risk measure $\tilde{h}$ also leads to an increase in $\delta$. This is expected as $\tilde{h}$ places
a higher weight on $\mathbb{P}(D_{\psi}(\tilde{X}^n, \hat{X}^n) > u)$ for all values of $u$.
<figure><img src="image_6.png" /><figcaption>(a) Plot of bounds with $M = 1000$ and quadratic risk distortion function $h$ in (77) with $k = 0$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Plot of bounds with $M = 1000$ and modified quadratic risk distortion function $\tilde{h}$ in (78) with $k = 0$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(a) Plot of bounds with $M = 1000$ and quadratic risk distortion function $h$ in (77) with $k = 1$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(b) Plot of bounds with $M = 1000$ and modified quadratic risk distortion function $\tilde{h}$ in (78) with $k = 1$.</figcaption></figure>

<caption>Fig. 5: Bounds for quadratic risk measures with $k = 1$.</caption>

Fig 5 plots the bounds for the quadratic risk measure with $k = 1$ and $M = 1000$, corresponding to an expectation constraint. Consistent with Fig. 2 and Fig. 4, our converse in Proposition 2 is tighter than the converse using the hypothesis testing method in Proposition 3. Comparing the Fig. 5 with Fig. 4 for $k = 0$, we observe an increase in $\delta$. Moreover, utilizing the modified risk
measure $\tilde{h}$ also leads to an increase in $\delta$. Both of these observations are expected as $\tilde{h}$ places a
higher weight on $\mathbb{P}(D_{\psi}(\tilde{X}^n, \hat{X}^n) > u)$ for all values of $u$.

REFERENCES

[1] R. Smith, *Uncertainty Quantification: Theory, Implementation, and Applications*. SIAM, 2014.

[2] A. Kipnis, S. Rini, and A. Goldsmith, “The rate-distortion risk in estimation from compressed data,” *IEEE Transactions on Information Theory*, vol. 67, no. 5, pp. 2910–2924, 2021.

[3] P. E. Van Der Maaten, L. and H. Jaap Van Den Herik, “Dimensionality reduction: a comparative review,” *Journal of Machine Learning Research*, vol. 10, no. 66-71, 2009.

[4] J. Li et al., “Feature selection: a data perspective,” *ACM Computing Surveys (CSUR)*, vol. 50, no. 6, pp. 1–45, 2017.

[5] A. Gersho and R. Gray, *Vector Quantization and Signal Compression*. Springer Science & Business Media, 2012.

[6] Y. Linde, A. Buzo, and R. Gray, “An algorithm for vector quantizer design,” *IEEE Transactions on Communications*, vol. 28, no. 1, pp. 84–95, 1980.

[7] D. Feldman, “Core-sets: updated survey,” *Sampling Techniques for Supervised or Unsupervised Tasks*, pp. 23–44, 2020.

[8] T. Cover and J. Thomas, *Elements of Information Theory*. Hoboken, NJ: John Wiley & Sons, 2006.

[9] I. Goodfellow, Y. Bengio, and A. Courville, “Deep learning,” 2016.

[10] P. Artzner et al., “Coherent measures of risk,” *Mathematical Finance*, vol. 9, no. 3, pp. 203–228, 1999.

[11] R. Rockafellar and S. Uryasev, “Optimization of conditional value-at-risk,” *Journal of Risk*, vol. 2, pp. 21–42, 2000.

[12] A. Shapiro, D. Dentcheva, and A. Ruszczynski, *Lectures on Stochastic Programming: Modeling and Theory*. SIAM, 2021.

[13] A. Singletary, M. Ahmadi, and A. Ames, “Safe control for nonlinear system with stochastic uncertainty via risk control barrier functions,” *IEEE Control Systems Letters*, vol. 7, pp. 349–254, 2022.

[14] O. Mihatsch and R. Neuneier, “Risk-sensitive reinforcement learning,” *Machine Learning*, vol. 49, pp. 267–290, 2002.

[15] R. Rockafellar and J. Royset, “Engineering decisions under risk averseness,” *ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering*, vol. 1, no. 2, 2015.

[16] V. Kostina and S. Verdú, “Fixed-length lossy compression in the finite blocklength regime,” *IEEE Transcations on Information Theory*, vol. 58, no. 6, pp. 3309–3338, 2012.

[17] E. Sereda et al., “Distortion risk measures in portfolio optimization,” *Handbook of Portfolio Construction*, pp. 649–673, 2010.

[18] T. Han, *Information-Spectrum Methods in Information Theory*. Berlin: Springer-Verlag, 2003.

[19] Y. Polyanskiy and Y. Wu, *Information Theory: From Coding to Learning*. Cambridge University Press, 2024.