Single-Letter Characterization of the Mismatched Distortion-Rate Function

Maël Le Treust, Tristan Tomala · 2025

Read Single-Letter Characterization of the Mismatched Distortion-Rate Function by Maël Le Treust, Tristan Tomala (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-14081.txt.

Introduction

Maël Le Treust and Tristan Tomala solve a long-open problem in this 2025 arXiv paper on data compression with a mismatch. The classic question asks the cheapest rate to describe a source within a set distortion. In the mismatched version, the decoder judges distortion by a different rule than the encoder expects, and the best rate had resisted proof since the problem was posed in the late nineteen-nineties.

The authors give a single-letter formula for that rate, naming the exact chance rules the encoder and decoder should use. Achieving it needs only two regimes, high rate and low rate, blended by time sharing. The hard part is the converse: showing no encoder can do better. Their trick builds a rival strategy with the same cost whenever the encoder strays from the stated rule. A counting bound from geometry caps the size of the auxiliary variables.

Catalog record

CREATORMaël Le Treust, Tristan Tomala
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-14081

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Single-Letter Characterization of the Mismatched Distortion-Rate Function Maël Le Treust, Tristan Tomala Abstract The mismatched distortion-rate problem has remained open since its formulation by Lapidoth in 1997. In this paper, we characterize the mismatched distortion-rate function. Our single-letter solution highlights the adequate conditional distributions for the encoder and the decoder. The achievability result relies on a time-sharing argument that allows to convexify the upper bound of Lapidoth. We show that it is sufficient to consider two regimes, one with a large rate and another one with a small rate. Our main contribution is the converse proof. Suppose that the encoder selects a single-letter conditional distribution distinct from the one in the solution, we construct an encoding strategy that leads to the same expected cost for both encoder and decoder. This ensures that the encoder cannot gain by changing the single-letter conditional distribution. This argument relies on a careful identification of the sequence of auxiliary random variables. By building on Caratheodory’s Theorem we show that the cardinality of the auxiliary random variables is equal to the one of the source alphabet plus three. † † The work of Maël Le Treust is supported in part by PEPR NF FOUNDS ANR-22-PEFT-0010. Tristan Tomala gratefully acknowledges the support of the HEC foundation and ANR/Investissements d’Avenir under grant ANR-11-IDEX-0003/Labex Ecodec/ANR-11-LABX-0047. I Introduction In the mismatched distortion-rate problem, the encoder optimizes a distortion function which differs from the one of the decoder. Formulated by Lapidoth in [ 1 ] , the main difficulty comes from the fact that the decisions are taken separately. This problem differs from Shannon’s distortion-rate problem [ 2 ] where the distortion function may have several components, and both encoding and decoding functions are selected jointly. Here, the encoder and the decoder decide in a decentralized manner which coding functions to implement, and they optimize distinct cost functions. The use of Game Theory is thus relevant. It gives us new insights to solve the mismatched distortion-rate problem. By selecting in advance the decoding function, the decoder determines the codebook. Indeed, the decoder can remove a codeword simply by producing the same decoder output as for another codeword. The encoder knows the decoding function before the transmission starts. Once it observes the source sequence, it selects the optimal codeword for its own cost function. This reaction is anticipated by the decoder when selecting the decoding function. This defines a Stackelberg game [ 3 ] in which the decoder is the leader that plays first, and the encoder is the follower that plays second [ 4 ] . When there is no communication constraint, this problem coincides with the mechanism design problem solved by Jackson and Sonnenschein in [ 5 ] . A large communication rate clearly benefits to the decoder. According to the revelation principle , see [ 6 , Chap. 7.2] , it is optimal that the decoding scheme incentivizes the encoder to communicate perfectly the source sequence to the decoder. However, with restrictions in the communication, the source cannot be perfectly transmitted to the decoder, and thus the revelation principle breaks down. \mathcal{P}_{U} \sigma \tau U^{n} M\in\{1,\ldots,2^{\lfloor\!n\mathsf{R}\!\rfloor}\} V^{n} c_{\mathsf{e}}(u,v) c_{\mathsf{d}}(u,v) Fig. 1: The mismatched distortion-rate problem. This problem is fundamental to understand situations in which the decoding rule is selected exogenously, for example in learning algorithms. Kanabar and Scarlett use superposition coding and expurgated parallel coding to derive new achievability bounds in [ 7 ] . The authors of [ 8 ] pointed out a list of open questions covering the mismatched distortion-rate problem and the mismatched channel coding problem, for which converse bounds are provided in [ 9 ] and [ 10 ] . In [ 11 ] , we provide a single-letter converse bound that matches Lapidoth’s achievability bound in several cases. In this paper, we characterize the single-letter mismatched distortion-rate function. The achievability proof relies on the time-sharing argument that convexifies the achievability bound of Lapidoth. We show that it is sufficient to consider two regimes, one with a large rate and another one with a small rate. The main novelty lies in the converse proof. For each component of the source and decoder output symbols (U_{t},V_{t}) with t\in\{1,\ldots,n\} , we identify the auxiliary random variable W_{t}=(M,U^{t-1}) . Suppose that the encoder selects a single-letter conditional distribution distinct from the one in the solution, we construct an encoding strategy that leads to the same expected cost for the encoder and decoder. Therefore, the encoder cannot gain by changing the single-letter conditional distribution. We build on Caratheodory’s Theorem to bound the cardinality of each of the auxiliary random variables (W_{t})_{t} by the cardinality of the source alphabet plus three. II System Model A memoryless source takes values in the finite set \mathcal{U} , according to the probability distribution \mathcal{P}_{U}\in\Delta(\mathcal{U}) . The notation \Delta(\cdot) stands for the set of probability distributions. The encoder and decoder optimize two distinct cost functions \displaystyle c_{\mathsf{e}}:\mathcal{U}\times\mathcal{V}\rightarrow\mathbb{R},\qquad c_{\mathsf{d}}:\mathcal{U}\times\mathcal{V}\rightarrow\mathbb{R}, (1) where \mathcal{V} denotes the finite set of decoder output symbols. Definition 1 Given \mathsf{R}\geq 0 and n\in\mathbb{N}^{\star} , the stochastic encoding and the decoding functions are defined by \displaystyle\sigma: \displaystyle\;\,\mathcal{U}^{n}\longrightarrow\Delta\big(\{1,\ldots,2^{\lfloor\!n\mathsf{R}\!\rfloor}\}\big), (2) \displaystyle\tau: \displaystyle\;\,\{1,\ldots,2^{\lfloor\!n\mathsf{R}\!\rfloor}\}\longrightarrow\Delta(\mathcal{V}^{n}). (3) The pair (\sigma,\tau) induces the probability distribution \mathcal{P}_{U^{n}MV^{n}}^{\sigma,\tau} . We denote the encoder long-run cost function by \displaystyle c^{n}_{\mathsf{e}}(\sigma,\tau)=\sum_{u^{n},v^{n}}\mathcal{P}_{U^{n}V^{n}}^{\sigma,\tau}\big(u^{n},v^{n}\big)\cdot\Bigg[\frac{1}{n}\sum_{t=1}^{n}c_{\mathsf{e}}(u_{t},v_{t})\Bigg]. (4) Similarly, the decoder long-run cost function writes c^{n}_{\mathsf{d}}(\sigma,\tau) . Definition 2 Given \mathsf{R}\geq 0 and n\in\mathbb{N}^{\star} , we define 1. the set of encoder best responses to the decoding \tau \displaystyle\textsf{BR}_{\mathsf{e}}(\tau)= \displaystyle\underset{\sigma}{\operatorname{argmin}}\;c_{\mathsf{e}}^{n}(\sigma,\tau), (5) 2. the n -optimal decoder cost with pessimistic tie-breaking rule \displaystyle C_{\mathsf{d}}^{n}(\mathsf{R})=\inf_{\tau}\max_{\sigma\in\textsf{BR}_{\mathsf{e}}(\tau)}c_{\mathsf{d}}^{n}(\sigma,\tau). (6) The mismatched distortion-rate function is defined by \displaystyle C_{\mathsf{d}}^{\star}(\mathsf{R})=\lim_{n\to+\infty}C_{\mathsf{d}}^{n}(\mathsf{R})=\inf_{n\in\mathbb{N}^{\star}}C_{\mathsf{d}}^{n}(\mathsf{R}). (7) The limit coincides with the infimum according to Fekete’s Lemma for the subadditive sequence (n\cdot C_{\mathsf{d}}^{n}(\mathsf{R}))_{n\in\mathbb{N}^{\star}} , see [ 11 , Lemma 4] . Theorem 1 The mismatched distortion-rate function writes \displaystyle C_{\mathsf{d}}^{\star}(\mathsf{R})=\min_{\alpha\in[0,1],\mathsf{R}_{1}\geq 0,\mathsf{R}_{2}\geq 0,\atop\alpha\mathsf{R}_{1}+(1-\alpha)\mathsf{R}_{2}\leq\mathsf{R}}\alpha C(\mathsf{R}_{1})+(1-\alpha)C(\mathsf{R}_{2}). (8) It is the convexification, i.e. the greatest convex minorant, of \displaystyle C(\mathsf{R})= \displaystyle\inf_{\mathcal{Q}_{WV}}\;\;\max_{\mathcal{Q}_{W|U}\in\mathbb{P}(\mathcal{Q}_{WV},\mathsf{R})}\;\mathbb{E}\Big[c_{\mathsf{d}}(U,V)\Big], (9) where W\in\mathcal{W} is an auxiliary random variable with |\mathcal{W}|=|\mathcal{U}|+3 . The set of compatible distributions \mathbb{P}(\mathcal{Q}_{WV},\mathsf{R}) , and the set of encoder’s deviations \mathbb{D}(\mathcal{Q}_{W},\mathsf{R}) are defined by \displaystyle\mathbb{P}(\mathcal{Q}_{WV},\mathsf{R})= \displaystyle\quad\underset{\mathcal{P}_{W|U}\in\mathbb{D}(\mathcal{Q}_{W},\mathsf{R})}{\operatorname{argmin}}\;\;\,\mathbb{E}_{\mathcal{Q}}[c_{\mathsf{e}}(U,V)], (10) \displaystyle\mathbb{D}(\mathcal{Q}_{W},\mathsf{R})= \displaystyle\;\;\Big\{\mathcal{P}_{W|U}\in\Delta(\mathcal{W})^{|\mathcal{U}|},\;\;I_{\mathcal{P}}(U;W)\leq\mathsf{R}, \displaystyle\quad\quad\;\;\sum_{u}\mathcal{P}_{U}(u)\mathcal{P}_{W|U}(\cdot|u)=\mathcal{Q}_{W}\Big\}. (11) The achievability proof is obtained by using a time-sharing argument for the coding scheme of [ 1 , Sec. II] , see also [ 8 , Sec. 4.5] and [ 11 , Sec. III] . We focus on the converse proof. III Converse Proof of Theorem 1 III-A Identification of the auxiliary random variables We fix n\in\mathbb{N}^{\star} , we consider a decoding function \tau and an encoding function \sigma\in\textsf{BR}_{\mathsf{e}}(\tau) that achieves the maximum in \displaystyle\max_{\sigma\in\textsf{BR}_{\mathsf{e}}(\tau)}c_{\mathsf{d}}^{n}(\sigma,\tau). (12) Let \mathcal{T}=\{1,\ldots,n\} , for all t\in\{1,\ldots,n\} we identify the coefficients \alpha_{t}=\frac{1}{n} , the auxiliary random variables, the rates \displaystyle W_{t}= \displaystyle\;(M,U^{t-1}), (13) \displaystyle\mathsf{R}_{t}= \displaystyle\;I(U_{t};W_{t})=I(U_{t};M,U^{t-1}). (14) We denote by \mathcal{Q}^{\sigma,\tau}_{U^{n}W^{n}V^{n}} the distribution of the sequences (U^{n},W^{n},V^{n}) induced by (\sigma,\tau) , and we denote by \mathcal{Q}^{\sigma,\tau}_{U_{t}W_{t}V_{t}} the marginal for all t . We define the average distribution by \displaystyle\mathcal{Q}^{\sigma,\tau}_{UWV}=\frac{1}{n}\sum_{t=1}^{n}\mathcal{Q}^{\sigma,\tau}_{U_{t}W_{t}V_{t}}. (15) In this proof, we consider the above \mathcal{T} , (\alpha_{t})_{t\in\mathcal{T}} , (\mathsf{R}_{t})_{t\in\mathcal{T}} , (U_{t},W_{t},V_{t})_{t\in\mathcal{T}} , and we show that \mathcal{Q}^{\sigma,\tau}_{UWV} belongs to the set \displaystyle\mathbb{Q}=\Bigg\{ \displaystyle\mathcal{P}_{U}\mathcal{Q}_{V|U},\;\exists\mathcal{T},\exists(\alpha_{t})_{t\in\mathcal{T}},\exists(\mathsf{R}_{t})_{t\in\mathcal{T}},\exists(U_{t},W_{t},V_{t})_{t\in\mathcal{T}}, \displaystyle\forall t\in\mathcal{T},\quad U_{t}-\!\!\!\!\minuso\!\!\!\!-W_{t}-\!\!\!\!\minuso\!\!\!\!-V_{t},\;\;\mathcal{Q}_{U_{t}}=\mathcal{P}_{U}, (16) \displaystyle\forall t\in\mathcal{T},\quad\mathcal{Q}_{W_{t}|U_{t}}\in\mathbb{P}(\mathcal{Q}_{W_{t}V_{t}},\mathsf{R}_{t}),\text{ and } \displaystyle\quad\mathbb{E}_{\mathcal{Q}}\Big[c_{\mathsf{d}}(U_{t},V_{t})\Big]=\!\!\!\max_{\mathcal{Q}_{W|U}\in\mathbb{P}(\mathcal{Q}_{W_{t}V_{t}},\mathsf{R}_{t})}\mathbb{E}\Big[c_{\mathsf{d}}(U_{t},V_{t})\Big], (17) \displaystyle\sum_{t\in\mathcal{T}}\alpha_{t}\mathsf{R}_{t}\leq\mathsf{R},\qquad\sum_{t\in\mathcal{T}}\alpha_{t}=1, (18) \displaystyle\mathcal{P}_{U}\mathcal{Q}_{V|U}=\sum_{t}\alpha_{t}\sum_{w_{t}}\mathcal{P}_{U_{t}}\mathcal{Q}_{W_{t}|U_{t}}(w_{t}|\cdot)\mathcal{Q}_{V_{t}|W_{t}}(\cdot|w_{t})\Bigg\}. Lemma 1 , Lemma 2 , Lemma 3 below, show that \mathcal{Q}^{\sigma,\tau}_{U_{t}W_{t}V_{t}} satisfies ( 16 ), (

Read the complete text