pith. sign in

arxiv: 2501.13582 · v3 · submitted 2025-01-23 · 💻 cs.IT · math.IT

Nonasymptotic Oblivious Relaying and Variable-Length Noisy Lossy Source Coding

Yanxiao Liu , Sepehr Heidari Advary , Cheuk Ting Li This is my paper

Pith reviewed 2026-05-23 05:35 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords oblivious relay channelinformation bottleneckfinite blocklengthvariable-length codingnoisy lossy source codingsecond-order asymptotics
0
0 comments X

The pith

Finite-blocklength achievability for the oblivious relay channel produces two distinct second-order versions of the information bottleneck, one for fixed-length relay codes and one for variable-length codes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes finite-blocklength achievability bounds for the oblivious relay channel, a setting where a relay compresses and forwards channel outputs to a decoder without knowledge of the codebook. Fixed-length coding at the relay yields one second-order characterization of the information bottleneck while variable-length coding yields another. The proofs combine existing nonasymptotic noisy lossy source coding results with the strong functional representation lemma and the Poisson matching lemma. A new nonasymptotic bound for variable-length noisy lossy source coding is derived along the way. These results matter for obtaining precise performance limits in short-packet relay communication.

Core claim

Finite-blocklength achievability results for the oblivious relay channel with fixed-length and variable-length codes at the relay produce two different second-order versions of the information bottleneck. The bounds are obtained by combining the nonasymptotic noisy lossy source coding results of Kostina and Verdú with the strong functional representation lemma and the Poisson matching lemma, together with a novel nonasymptotic variable-length noisy lossy source coding result.

What carries the argument

The information bottleneck function applied to nonasymptotic settings, with the fixed-length versus variable-length distinction at the relay producing the split in second-order terms.

If this is right

  • Short-blocklength rates for oblivious relaying can be bounded separately according to whether the relay employs fixed-length or variable-length codes.
  • The novel variable-length noisy lossy source coding result supplies tighter finite-blocklength guarantees for related compression tasks.
  • The two different second-order characterizations allow comparison of error-probability decay between the two coding styles at the relay.
  • The approach extends the information-bottleneck capacity result to precise nonasymptotic performance limits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • In short-packet wireless systems the choice between fixed and variable relay coding may produce measurably different reliability at the same average rate.
  • The split in second-order behavior could appear in other rate-limited forwarding problems such as multi-hop networks or distributed compression.
  • The variable-length source coding bound may improve finite-blocklength analysis for lossy compression under average-length constraints.

Load-bearing premise

Nonasymptotic noisy lossy source coding bounds can be combined with the strong functional representation lemma and the Poisson matching lemma to derive the stated achievability results for both fixed-length and variable-length relaying.

What would settle it

A direct calculation or simulation for a specific channel showing identical second-order terms for fixed-length and variable-length relay coding would contradict the claimed distinction between the two versions.

Figures

Figures reproduced from arXiv: 2501.13582 by Cheuk Ting Li, Sepehr Heidari Advary, Yanxiao Liu.

Figure 1
Figure 1. Figure 1: Information bottleneck channel (or oblivious relaying). [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
read the original abstract

The information bottleneck channel (or the oblivious relay channel) concerns a channel coding setting where the decoder does not directly observe the channel output. Rather, the channel output is relayed to the decoder by an oblivious relay (which does not know the codebook) via a rate-limited link. The capacity is known to be given by the information bottleneck. We study finite-blocklength achievability results of the channel, where the relay communicates to the decoder via fixed-length or variable-length codes. These two cases give rise to two different second-order versions of the information bottleneck. Our proofs utilize the nonasymptotic noisy lossy source coding results by Kostina and Verd\'{u}, the strong functional representation lemma, and the Poisson matching lemma. Moreover, we also give a novel nonasymptotic variable-length noisy lossy source coding result.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript derives finite-blocklength achievability bounds for the oblivious relay (information bottleneck) channel under both fixed-length and variable-length coding at the relay. These produce two distinct second-order characterizations of the information bottleneck. The proofs combine the Kostina-Verdú nonasymptotic noisy lossy source coding bounds, the strong functional representation lemma, and the Poisson matching lemma, while also introducing a new nonasymptotic variable-length noisy lossy source coding result.

Significance. If the derivations hold without extraneous dispersion or remainder terms in the new variable-length bound, the work supplies the first explicit distinction between fixed-length and variable-length regimes at the second-order level for this channel model. It extends nonasymptotic tools to a relay setting and supplies a new source-coding lemma whose utility may extend beyond the present application.

major comments (2)
  1. [abstract and proofs of the variable-length case] The central claim of two distinct second-order expressions rests on the new variable-length noisy lossy source coding bound not introducing additional o(1/sqrt(n)) terms or implicit fixed-length approximations when the block length is randomized. The abstract states that the proofs utilize this new result together with Kostina-Verdú bounds, but the composition must be checked to ensure the claimed distinction survives.
  2. [main achievability theorems] The achievability bounds for the relay channel are obtained by invoking the strong functional representation lemma and Poisson matching lemma on top of the source-coding results. Any mismatch in the second-order remainders between the fixed-length and variable-length source-coding statements would collapse the two information-bottleneck characterizations; explicit tracking of all o(1/sqrt(n)) terms through this composition is required.
minor comments (2)
  1. [preliminaries] Notation for the variable-length code should be introduced with an explicit definition of the random length random variable and its relation to the fixed-length case.
  2. [introduction] The abstract mentions 'two different second-order versions'; the introduction or theorem statements should state the precise dispersion coefficients for each regime side-by-side for immediate comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the insightful comments regarding the second-order characterizations. Below we respond point by point to the major comments, clarifying the term tracking in our proofs while agreeing to strengthen the presentation where helpful.

read point-by-point responses

  1. Referee: [abstract and proofs of the variable-length case] The central claim of two distinct second-order expressions rests on the new variable-length noisy lossy source coding bound not introducing additional o(1/sqrt(n)) terms or implicit fixed-length approximations when the block length is randomized. The abstract states that the proofs utilize this new result together with Kostina-Verdú bounds, but the composition must be checked to ensure the claimed distinction survives.

    Authors: The variable-length noisy lossy source coding bound is stated and proved directly for randomized block lengths, with all remainder terms controlled at o(1/sqrt(n)) without any fixed-length approximation or additional dispersion contribution. The subsequent composition with the strong functional representation lemma and Poisson matching lemma is performed by first applying the representation to obtain a conditional distribution, then invoking the variable-length source-coding result on the resulting empirical distribution; the second-order term therefore inherits the distinct dispersion coefficient that arises from the variable-length nature. We have verified this composition yields the claimed separation and will add an explicit appendix tabulating every o(1/sqrt(n)) remainder through the entire chain. revision: partial

  2. Referee: [main achievability theorems] The achievability bounds for the relay channel are obtained by invoking the strong functional representation lemma and Poisson matching lemma on top of the source-coding results. Any mismatch in the second-order remainders between the fixed-length and variable-length source-coding statements would collapse the two information-bottleneck characterizations; explicit tracking of all o(1/sqrt(n)) terms through this composition is required.

    Authors: The proofs apply the strong functional representation lemma to produce a representation of the relay output whose conditional distribution is then fed to the appropriate (fixed- or variable-length) source-coding bound; the Poisson matching lemma is used only for the final channel-coding step and contributes the same o(1/sqrt(n)) remainder in both cases. Because the source-coding statements already carry distinct dispersion coefficients, the overall second-order terms remain separated. We acknowledge that the current write-up leaves some of these remainder calculations implicit and will expand the proof sketches in the revised version to display the full term-by-term accounting. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations rest on external lemmas

full rationale

The paper derives finite-blocklength achievability for oblivious relaying by combining the nonasymptotic noisy lossy source coding bounds of Kostina-Verdú, the strong functional representation lemma, and the Poisson matching lemma, plus one novel variable-length source coding result. No load-bearing step is shown to reduce by the paper's own equations to a fitted parameter, self-defined quantity, or self-citation chain. The two distinct second-order information-bottleneck expressions arise from the fixed-length versus variable-length relay regimes; the abstract and structure give no indication that either collapses to the other by construction. This is the normal case of a self-contained derivation against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claims rest on three external lemmas whose validity is taken as given; no free parameters or new postulated entities are introduced in the abstract.

axioms (3)
  • domain assumption Nonasymptotic noisy lossy source coding results by Kostina and Verdú
    Invoked to obtain the finite-blocklength bounds for both relaying regimes.
  • standard math Strong functional representation lemma
    Used in the proof strategy for the relay channel.
  • standard math Poisson matching lemma
    Used in the proof strategy for the relay channel.

pith-pipeline@v0.9.0 · 5678 in / 1441 out tokens · 50743 ms · 2026-05-23T05:35:12.026338+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages · 1 internal anchor

  1. [1]

    Communication via decentralized processing,

    A. Sanderovich, S. Shamai, Y . Steinberg, and G. Kramer, “Communication via decentralized processing,” IEEE Transactions on Information Theory , vol. 54, no. 7, pp. 3008–3023, 2008

    work page 2008

  2. [2]

    On codebook information for interference relay channels with out-of-band relaying,

    O. Simeone, E. Erkip, and S. Shamai, “On codebook information for interference relay channels with out-of-band relaying,” IEEE transactions on information theory , vol. 57, no. 5, pp. 2880–2888, 2011

    work page 2011

  3. [3]

    On the capacity of cloud radio access networks with oblivious relaying,

    I. E. Aguerri, A. Zaidi, G. Caire, and S. Shamai, “On the capacity of cloud radio access networks with oblivious relaying,” IEEE Transactions on Information Theory , vol. 65, no. 7, pp. 4575–4596, 2019

    work page 2019

  4. [4]

    On mismatched oblivious relaying,

    M. Dikshtein, N. Weinberger, and S. Shamai, “On mismatched oblivious relaying,” in 2023 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2023, pp. 1687–1692

    work page 2023

  5. [5]

    An achievable error exponent for the information bottleneck channel,

    H. Wu and H. Joudeh, “An achievable error exponent for the information bottleneck channel,” in 2024 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2024, pp. 1297–1302

    work page 2024

  6. [6]

    The information bottleneck method,

    N. Tishby, F. Pereira, and W. Bialek, “The information bottleneck method,” in Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing . IEEE, 1999, pp. 368–377

    work page 1999

  7. [7]

    The information bottleneck: Theory and applications,

    N. Slonim, “The information bottleneck: Theory and applications,” Ph.D. dissertation, Hebrew University, 2002

    work page 2002

  8. [8]

    A unified framework for one-shot achievability via the Poisson matching lemma,

    C. T. Li and V . Anantharam, “A unified framework for one-shot achievability via the Poisson matching lemma,” IEEE Transactions on Information Theory, vol. 67, no. 5, pp. 2624–2651, 2021

    work page 2021

  9. [9]

    Nonasymptotic noisy lossy source coding,

    V . Kostina and S. Verdú, “Nonasymptotic noisy lossy source coding,” IEEE Transactions on Information Theory , vol. 62, no. 11, pp. 6111–6123, 2016

    work page 2016

  10. [10]

    Information transmission with additional noise,

    R. Dobrushin and B. Tsybakov, “Information transmission with additional noise,” IRE Transactions on Information Theory , vol. 8, no. 5, pp. 293–304, 1962

    work page 1962

  11. [11]

    Strong functional representation lemma and applications to coding theorems,

    C. T. Li and A. El Gamal, “Strong functional representation lemma and applications to coding theorems,” IEEE Transactions on Information Theory , vol. 64, no. 11, pp. 6967–6978, Nov 2018

    work page 2018

  12. [12]

    Fronthaul-constrained cloud radio access networks: Insights and challenges,

    M. Peng, C. Wang, V . Lau, and H. V . Poor, “Fronthaul-constrained cloud radio access networks: Insights and challenges,”IEEE Wireless Communications, vol. 22, no. 2, pp. 152–160, 2015

    work page 2015

  13. [13]

    On cloud radio access networks with cascade oblivious relaying,

    M. Ensan, H. Joudeh, A. Alvarado, U. Gustavsson, and F. M. Willems, “On cloud radio access networks with cascade oblivious relaying,” in 2021 IEEE Information Theory Workshop (ITW) . IEEE, 2021, pp. 1–6

    work page 2021

  14. [14]

    The information bottleneck method

    N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” arXiv preprint physics/0004057 , 2000

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  15. [15]

    On the information bottleneck problems: Models, connections, applications and information theoretic views,

    A. Zaidi, I. Estella-Aguerri, and S. Shamai, “On the information bottleneck problems: Models, connections, applications and information theoretic views,” Entropy, vol. 22, no. 2, p. 151, 2020

    work page 2020

  16. [16]

    The information bottleneck problem and its applications in machine learning,

    Z. Goldfeld and Y . Polyanskiy, “The information bottleneck problem and its applications in machine learning,” IEEE Journal on Selected Areas in Information Theory , vol. 1, no. 1, pp. 19–38, 2020

    work page 2020

  17. [17]

    Distributed variational representation learning,

    I. E. Aguerri and A. Zaidi, “Distributed variational representation learning,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 43, no. 1, pp. 120–138, 2019

    work page 2019

  18. [18]

    Indirect rate distortion problems,

    H. Witsenhausen, “Indirect rate distortion problems,” IEEE Transactions on Information Theory , vol. 26, no. 5, pp. 518–521, 1980

    work page 1980

  19. [19]

    Multiterminal source coding under logarithmic loss,

    T. A. Courtade and T. Weissman, “Multiterminal source coding under logarithmic loss,” IEEE Transactions on Information Theory , vol. 60, no. 1, pp. 740–761, 2013

    work page 2013

  20. [20]

    The dispersion of lossy source coding,

    A. Ingber and Y . Kochman, “The dispersion of lossy source coding,” in 2011 Data Compression Conference , March 2011, pp. 53–62

    work page 2011

  21. [21]

    Fixed-length lossy compression in the finite blocklength regime,

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

    work page 2012

  22. [22]

    Pointwise redundancy in lossy data compression and universal lossy data compression,

    I. Kontoyiannis, “Pointwise redundancy in lossy data compression and universal lossy data compression,” IEEE Transactions on Information Theory , vol. 46, no. 1, pp. 136–152, 2000

    work page 2000

  23. [23]

    Universal almost sure data compression,

    D. S. Ornstein and P. C. Shields, “Universal almost sure data compression,” The Annals of Probability , pp. 441–452, 1990

    work page 1990

  24. [24]

    A rate of convergence result for a universal d-semifaithful code,

    B. Yu and T. P. Speed, “A rate of convergence result for a universal d-semifaithful code,” IEEE Transactions on Information Theory , vol. 39, no. 3, pp. 813–820, 1993

    work page 1993

  25. [25]

    The redundancy of source coding with a fidelity criterion. 1. known statistics,

    Z. Zhang, E.-H. Yang, and V . K. Wei, “The redundancy of source coding with a fidelity criterion. 1. known statistics,” IEEE Transactions on Information Theory, vol. 43, no. 1, pp. 71–91, 1997

    work page 1997

  26. [26]

    Arbitrary source models and bayesian codebooks in rate-distortion theory,

    I. Kontoyiannis and J. Zhang, “Arbitrary source models and bayesian codebooks in rate-distortion theory,” IEEE Transactions on information theory , vol. 48, no. 8, pp. 2276–2290, 2002

    work page 2002

  27. [27]

    Asymptotic properties on codeword lengths of an optimal FV code for general sources,

    H. Koga and H. Yamamoto, “Asymptotic properties on codeword lengths of an optimal FV code for general sources,” IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1546–1555, 2005

    work page 2005

  28. [28]

    Variable-length compression allowing errors,

    V . Kostina, Y . Polyanskiy, and S. Verdú, “Variable-length compression allowing errors,” IEEE Transactions on Information Theory , vol. 61, no. 8, pp. 4316–4330, 2015

    work page 2015

  29. [29]

    Indirect rate distortion functions with f-separable distortion criterion,

    P. A. Stavrou, Y . Shkel, and M. Kountouris, “Indirect rate distortion functions with f-separable distortion criterion,” in2023 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2023, pp. 1050–1055

    work page 2023

  30. [30]

    Privacy-constrained remote source coding,

    K. Kittichokechai and G. Caire, “Privacy-constrained remote source coding,” in 2016 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2016, pp. 1078–1082

    work page 2016

  31. [31]

    Fixed-length lossy compression in the finite blocklength regime,

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

    work page 2012

  32. [32]

    New results on variable-length lossy compression allowing positive overflow and excess distortion probabilities,

    S. Saito, H. Yagi, and T. Matsushima, “New results on variable-length lossy compression allowing positive overflow and excess distortion probabilities,” in 2018 International Symposium on Information Theory and Its Applications (ISITA) . IEEE, 2018, pp. 359–363

    work page 2018

  33. [33]

    Indirect lossy source coding with observed source reconstruction: Nonasymptotic bounds and second-order asymptotics,

    H. Yang, Y . Shi, S. Shao, and X. Yuan, “Indirect lossy source coding with observed source reconstruction: Nonasymptotic bounds and second-order asymptotics,” IEEE Transactions on Communications , pp. 1–1, 2024

    work page 2024

  34. [34]

    Finite blocklength lossy source coding for discrete memoryless sources,

    L. Zhou, M. Motani et al., “Finite blocklength lossy source coding for discrete memoryless sources,” F oundations and Trends® in Communications and Information Theory , vol. 20, no. 3, pp. 157–389, 2023

    work page 2023

  35. [35]

    Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem,

    C. H. Bennett, P. W. Shor, J. Smolin, and A. V . Thapliyal, “Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem,” IEEE Transactions on Information Theory , vol. 48, no. 10, pp. 2637–2655, 2002

    work page 2002

  36. [36]

    The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels,

    C. H. Bennett, I. Devetak, A. W. Harrow, P. W. Shor, and A. Winter, “The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels,” IEEE Transactions on Information Theory , vol. 60, no. 5, pp. 2926–2959, May 2014

    work page 2014

  37. [37]

    Distributed channel synthesis,

    P. Cuff, “Distributed channel synthesis,” IEEE Transactions on Information Theory , vol. 59, no. 11, pp. 7071–7096, Nov 2013

    work page 2013

  38. [38]

    The communication complexity of correlation,

    P. Harsha, R. Jain, D. McAllester, and J. Radhakrishnan, “The communication complexity of correlation,” IEEE Transactions on Information Theory , vol. 56, no. 1, pp. 438–449, Jan 2010

    work page 2010

  39. [39]

    Greedy Poisson rejection sampling,

    G. Flamich, “Greedy Poisson rejection sampling,” Advances in Neural Information Processing Systems , vol. 36, 2023

    work page 2023

  40. [40]

    Algorithms for the communication of samples,

    L. Theis and N. Yosri, “Algorithms for the communication of samples,” in International Conference on Machine Learning . PMLR, 2022, pp. 21 308– 21 328

    work page 2022

  41. [41]

    One-shot coding over general noisy networks,

    Y . Liu and C. T. Li, “One-shot coding over general noisy networks,” in 2024 IEEE International Symposium on Information Theory (ISIT) , 2024, pp. 3124–3129. 9

    work page 2024

  42. [42]

    Universal exact compression of differentially private mechanisms,

    Y . Liu, W.-N. Chen, A. Özgür, and C. T. Li, “Universal exact compression of differentially private mechanisms,” Advances in Neural Information Processing Systems, 2024

    work page 2024

  43. [43]

    Minimax learning for distributed inference,

    C. T. Li, X. Wu, A. Özgür, and A. El Gamal, “Minimax learning for distributed inference,” IEEE Transactions on Information Theory , vol. 66, no. 12, pp. 7929–7938, 2020

    work page 2020

  44. [44]

    Neural estimation of the rate-distortion function with applications to operational source coding,

    E. Lei, H. Hassani, and S. S. Bidokhti, “Neural estimation of the rate-distortion function with applications to operational source coding,” IEEE Journal on Selected Areas in Information Theory , vol. 3, no. 4, pp. 674–686, 2022

    work page 2022

  45. [45]

    Channel simulation: Theory and applications to lossy compression and differential privacy,

    C. T. Li, “Channel simulation: Theory and applications to lossy compression and differential privacy,” F oundations and Trends® in Communications and Information Theory , vol. 21, no. 6, pp. 847–1106, 2024. [Online]. Available: http://dx.doi.org/10.1561/0100000141

    work page doi:10.1561/0100000141 2024

  46. [46]

    Pointwise redundancy in one-shot lossy compression via Poisson functional representation,

    ——, “Pointwise redundancy in one-shot lossy compression via Poisson functional representation,” in arXiv preprint; short version presented at 2024 International Zurich Seminar on Information and Communication , 2024, pp. 28–29. [Online]. Available: https://arxiv.org/pdf/2401.14805.pdf

    work page arXiv 2024

  47. [47]

    A method for the construction of minimum-redundancy codes,

    D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the IRE , vol. 40, no. 9, pp. 1098–1101, 1952

    work page 1952

  48. [48]

    Channel coding rate in the finite blocklength regime,

    Y . Polyanskiy, H. V . Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Transactions on Information Theory , vol. 56, no. 5, pp. 2307–2359, 2010. APPENDIX A. Remainder of the Proof of Theorem 2 We use the strategy in [11, Theorem 2] to remove the common randomness G := ( ¯Zi, Ti)i. Consider two values g0, g1 of the common r...

    work page 2010