pith. sign in

arxiv: 1907.05324 · v1 · pith:JD2X5RR3new · submitted 2019-07-11 · 💻 cs.IT · cs.GT· math.IT· math.OC

Minimax Theorems for Finite Blocklength Lossy Joint Source-Channel Coding over an AVC

Anuj S. Vora , Ankur A. Kulkarni This is my paper

Pith reviewed 2026-05-24 22:56 UTC · model grok-4.3

classification 💻 cs.IT cs.GTmath.ITmath.OC
keywords finite blocklengthjoint source-channel codingarbitrarily varying channelminimax theoremzero-sum gamelocal randomizationdispersion boundsadversarial communication
0
0 comments X

The pith

Approximate minimax theorems hold asymptotically for finite-blocklength lossy joint source-channel coding over an AVC posed as a zero-sum game.

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

The paper poses finite-blocklength lossy joint source-channel coding over an arbitrarily varying channel as a zero-sum game between an encoder-decoder team and a jammer, with both sides restricted to locally randomized strategies. This restriction makes the communicating team's optimization non-convex, so a classical minimax theorem need not apply. The authors derive finite-blocklength bounds showing that the minimax and maximin values of the game nevertheless converge to each other as blocklength grows. Below a critical rate threshold both values approach zero; above it both approach one. At the threshold under a specific rate scaling they approach the same constant value between zero and one. A reader would care because the result supplies asymptotic reliability guarantees against adversarial jamming at finite lengths, directly relevant to secure cyber-physical systems.

Core claim

We show that approximate minimax theorems hold in the sense that the minimax and maximin values of the game approach each other asymptotically. In particular, for rates strictly below a critical threshold, both the minimax and maximin values approach zero, and for rates strictly above it, they both approach unity. We then show a second order minimax theorem, i.e., for rates exactly approaching the threshold along a specific scaling, the minimax and maximin values approach the same constant value, that is neither zero nor one. Critical to these results is our derivation of finite blocklength bounds on the minimax and maximin values of the game and our derivation of second order dispersion -b

What carries the argument

The zero-sum game between the communicating team and the jammer under locally randomized strategies, whose minimax and maximin values are bounded via finite-blocklength and dispersion analysis to establish asymptotic convergence.

If this is right

  • Below the critical threshold the error probability can be driven to zero against any jammer strategy.
  • Above the threshold the jammer can force the error probability to one.
  • Exactly at the threshold with the indicated scaling the game value converges to a fixed constant strictly between zero and one.
  • The second-order dispersion terms give a precise characterization of how fast the values approach their limits.
  • The same convergence holds for both the lossy source-channel setting and the underlying channel coding game.

Where Pith is reading between the lines

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

  • The result implies that for sufficiently large but finite blocklength one can still obtain near-minimax performance by optimizing over the approximate game.
  • Similar approximate convergence may hold in other non-convex adversarial settings once finite-blocklength bounds are available.
  • The specific scaling at the threshold suggests a natural way to test the second-order constant via simulation on concrete AVCs.
  • The local-randomization restriction may be relaxed in future work while preserving the asymptotic statements.

Load-bearing premise

Both the communicating team and the jammer are restricted to locally randomized strategies, which renders the communicating team's problem non-convex.

What would settle it

For some fixed rate below the critical threshold and sequence of blocklengths going to infinity, if the minimax value stays bounded away from zero while the maximin value goes to zero, the claimed asymptotic convergence would be false.

Figures

Figures reproduced from arXiv: 1907.05324 by Ankur A. Kulkarni, Anuj S. Vora.

Figure 1
Figure 1. Figure 1: Source-Channel Coding Setup and A ⊂ X n × Yn is a typical set. Let (X, X, Y ¯ ) ∼ PX × PX × PY |X,Θ. Then, there exists a deterministic channel code (fc, ϕc), such that e¯(fc, ϕc) ≤ r 2 ln(3|T |n) M + min PX max θ∈T n  P((X, Y ) ∈ A| / θ) + 2 log 3|T |n max x¯∈X n P(Z(X, x, Y ¯ ) = 0,(X, Y ) ∈ A|θ) +2M log e P(Z(X, X, Y ¯ ) = 0,(X, Y ) ∈ A|θ)  . (22) We thus have a deterministic channel code that gives a… view at source ↗
read the original abstract

Motivated by applications in the security of cyber-physical systems, we pose the finite blocklength communication problem in the presence of a jammer as a zero-sum game between the encoder-decoder team and the jammer, by allowing the communicating team as well as the jammer only locally randomized strategies. The communicating team's problem is non-convex under locally randomized codes, and hence, in general, a minimax theorem need not hold for this game. However, we show that approximate minimax theorems hold in the sense that the minimax and maximin values of the game approach each other asymptotically. In particular, for rates strictly below a critical threshold, both the minimax and maximin values approach zero, and for rates strictly above it, they both approach unity. We then show a second order minimax theorem, i.e., for rates exactly approaching the threshold with along a specific scaling, the minimax and maximin values approach the same constant value, that is neither zero nor one. Critical to these results is our derivation of finite blocklength bounds on the minimax and maximin values of the game and our derivation of second order dispersion-based bounds.

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

0 major / 2 minor

Summary. The paper models finite-blocklength lossy joint source-channel coding over an arbitrarily varying channel (AVC) as a zero-sum game in which both the communicating team and the jammer are restricted to locally randomized strategies. Despite the non-convexity this induces, the authors derive explicit finite-blocklength bounds on the minimax and maximin values and use them to prove approximate minimax theorems: the two values converge asymptotically (both to 0 below a critical rate threshold and both to 1 above it). A second-order result is also shown in which, along a specific scaling to the threshold, the minimax and maximin values converge to the same constant strictly between 0 and 1.

Significance. If the explicit bounds and dispersion analysis hold, the work supplies the first asymptotic and second-order minimax characterizations for a non-convex finite-blocklength game arising from local randomization. This is directly relevant to secure communication in cyber-physical systems. The provision of concrete finite-blocklength bounds (rather than only asymptotic statements) is a clear methodological strength.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'along a specific scaling' is used without indicating what the scaling is or pointing to the relevant theorem/equation; a one-sentence clarification would help readers.
  2. The notation for the critical threshold and the second-order constant should be introduced with an explicit equation reference the first time each appears.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were listed under the MAJOR COMMENTS section, so there are no individual points requiring point-by-point rebuttal or manuscript changes at this stage.

Circularity Check

0 steps flagged

No significant circularity detected in derivation

full rationale

The paper establishes approximate minimax theorems for the finite-blocklength game via explicit derivation of finite-blocklength bounds on minimax and maximin values, followed by second-order dispersion analysis. These steps are presented as direct analytic results rather than reductions to fitted parameters, self-definitions, or load-bearing self-citations. The abstract and description indicate the convergence claims (to 0 below threshold, 1 above, and a constant at second order) follow from the derived bounds without the central claims collapsing to inputs by construction. No quoted equations or steps exhibit self-definitional, fitted-input, or ansatz-smuggling patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no identifiable free parameters, axioms, or invented entities; the modeling choice of local randomization is stated but not expanded into explicit assumptions.

pith-pipeline@v0.9.0 · 5745 in / 1193 out tokens · 31761 ms · 2026-05-24T22:56:34.832658+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Non-Probabilistic Game-Theoretic Information Theory Which Subsumes Probabilistic Channel Coding

    cs.IT 2026-04 unverdicted novelty 6.0

    A game-theoretic information theory with dynamic hedging and nonconvex downward-closed cones subsumes probabilistic channel coding theorems and adversarial settings.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    A minimax theorem for finite blocklength joint source-channel coding over an A VC,

    A. S. V ora and A. A. Kulkarni, “A minimax theorem for finite blocklength joint source-channel coding over an A VC,” in Twenty-fifth National Conference on Communications (NCC) . IEEE, 2019, pp. 1–6

    work page 2019

  2. [2]

    Cyber-physical sys tems securitya survey,

    A. Humayed, J. Lin, F. Li, and B. Luo, “Cyber-physical sys tems securitya survey,” IEEE Internet of Things Journal , vol. 4, no. 6, pp. 1802–1831, 2017

    work page 2017

  3. [3]

    Lessons learned from the maroochy water breach,

    J. Slay and M. Miller, “Lessons learned from the maroochy water breach,” in International Conference on Critical Infrastructure Protection. Springer, 2007, pp. 73–82

    work page 2007

  4. [4]

    Stuxnet: Dissecting a cyberwarfare weapon ,

    R. Langner, “Stuxnet: Dissecting a cyberwarfare weapon ,” IEEE Security & Privacy , vol. 9, no. 3, pp. 49–51, 2011

    work page 2011

  5. [5]

    Maschler, E

    M. Maschler, E. Solan, and S. Zamir, Game Theory . Cambridge University Press, 2013

    work page 2013

  6. [6]

    An optimizer’s approac h to stochastic control problems with nonclassical informa tion structures,

    A. A. Kulkarni and T. P . Coleman, “An optimizer’s approac h to stochastic control problems with nonclassical informa tion structures,” IEEE Transactions on Automatic Control , vol. 60, no. 4, pp. 937–949, 2015

    work page 2015

  7. [7]

    A note on the existence of the weak capacity for channels with arbitrarily varying channel probability functions and its relation to shannon’s zero error capacity,

    R. Ahlswede, “A note on the existence of the weak capacity for channels with arbitrarily varying channel probability functions and its relation to shannon’s zero error capacity,” The Annals of Mathematical Statistics , vol. 41, no. 3, pp. 1027–1033, 1970

    work page 1970

  8. [8]

    Channel coding rate in the finite blocklength regime,

    Y . Polyanskiy, H. V . Poor, and S. V erd´ u, “Channel coding rate in the finite blocklength regime,” Information Theory, IEEE Transactions on, vol. 56, no. 5, pp. 2307–2359, 2010

    work page 2010

  9. [9]

    Lossy joint source-channel co ding in the finite blocklength regime,

    V . Kostina and S. V erd´ u, “Lossy joint source-channel co ding in the finite blocklength regime,” Information Theory, IEEE Transactions on, vol. 59, no. 5, pp. 2545–2575, 2013

    work page 2013

  10. [10]

    Csiszar and J

    I. Csiszar and J. K¨ orner, Information theory: coding theorems for discrete memoryle ss systems . Cambridge University Press, 2011. 30

    work page 2011

  11. [11]

    Finite Blocklength and Dispersion Bounds for the Arbitrarily-Varying Channel

    O. Kosut and J. Kliewer, “Finite blocklength and disper sion bounds for the arbitrarily-varying channel,” arXiv preprint arXiv:1801.03594 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  12. [12]

    Linear programming-base d converses for finite blocklength lossy joint source-chann el coding,

    S. T. Jose and A. A. Kulkarni, “Linear programming-base d converses for finite blocklength lossy joint source-chann el coding,” IEEE Transactions on Information Theory , vol. 63, no. 11, pp. 7066–7094, 2017

    work page 2017

  13. [13]

    Linear programming based converses for finite-blo cklength joint-source channel coding,

    ——, “Linear programming based converses for finite-blo cklength joint-source channel coding,” IEEE Transactions on Information Theory, vol. 63, no. 11, pp. 7066–7094, 2017

    work page 2017

  14. [14]

    Improved finite blocklength converses for Slepian -Wolf coding via linear programming,

    ——, “Improved finite blocklength converses for Slepian -Wolf coding via linear programming,” accepted (currently in press), IEEE Transactions on Information Theory , 2018

    work page 2018

  15. [15]

    Some infor mation theoretic saddlepoints,

    J. M. Borden, D. M. Mason, and R. J. McEliece, “Some infor mation theoretic saddlepoints,” SIAM journal on control and optimization , vol. 23, no. 1, pp. 129–143, 1985

    work page 1985

  16. [16]

    On the capacity o f channels with unknown interference,

    M. Hegde, W. Stark, and D. Teneketzis, “On the capacity o f channels with unknown interference,” IEEE Transactions on Information Theory, vol. 35, no. 4, pp. 770–783, 1989

    work page 1989

  17. [17]

    A complete characterization of minimax and maximin encod er-decoder policies for communication channels with incomplete statistical description,

    T. Bas ¸ar et al. , “A complete characterization of minimax and maximin encod er-decoder policies for communication channels with incomplete statistical description,” IEEE Transactions on Information Theory , vol. 31, no. 4, pp. 482–489, 1985

    work page 1985

  18. [18]

    Gaussian arbitrarily varyin g channels,

    B. Hughes and P . Narayan, “Gaussian arbitrarily varyin g channels,” IEEE Transactions on Information Theory , vol. 33, no. 2, pp. 267–284, 1987

    work page 1987

  19. [19]

    On a game between a delay-c onstrained communication system and a finite state jammer,

    S. T. Jose and A. A. Kulkarni, “On a game between a delay-c onstrained communication system and a finite state jammer,” in Decision and Control (CDC), 2018 IEEE 57th Annual Conference , to appear

    work page 2018

  20. [20]

    Shannon meets von Neumann: A Minimax Theorem for Channel Coding in the Presence of a Jammer

    ——, “Shannon meets von neumann: A minimax theorem for ch annel coding in the presence of a jammer,” Under review with IEEE Transactions on Information Theory; arXiv: https://arxiv .org/abs/1811.07358, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  21. [21]

    The capaci ties of certain channel classes under random coding,

    D. Blackwell, L. Breiman, and A. Thomasian, “The capaci ties of certain channel classes under random coding,” The Annals of Mathematical Statistics, vol. 31, no. 3, pp. 558–567, 1960

    work page 1960

  22. [22]

    Elimination of correlation in random cod es for arbitrarily varying channels,

    R. Ahlswede, “Elimination of correlation in random cod es for arbitrarily varying channels,” Probability Theory and Related Fields , vol. 44, no. 2, pp. 159–175, 1978

    work page 1978

  23. [23]

    Reliable communication un der channel uncertainty,

    A. Lapidoth and P . Narayan, “Reliable communication un der channel uncertainty,” IEEE Transactions on Information Theory , vol. 44, no. 6, pp. 2148–2177, 1998

    work page 1998

  24. [24]

    T. M. Cover and J. A. Thomas, Elements of information theory . John Wiley & Sons, 2012

    work page 2012

  25. [25]

    Fixed-length lossy compress ion in the finite blocklength regime,

    V . Kostina and S. V erd´ u, “Fixed-length lossy compress ion in the finite blocklength regime,” Information Theory, IEEE Transactions on , vol. 58, no. 6, pp. 3309–3338, 2012

    work page 2012

  26. [26]

    Coding theorems for a discrete source wi th a fidelity criterion,

    C. E. Shannon, “Coding theorems for a discrete source wi th a fidelity criterion,” IRE Nat. Conv. Rec , vol. 4, no. 142-163, p. 1, 1959

    work page 1959

  27. [27]

    An optimizer’s approa ch to stochastic control problems with nonclassical inform ation structures,

    A. A. Kulkarni and T. P . Coleman, “An optimizer’s approa ch to stochastic control problems with nonclassical inform ation structures,” IEEE Transactions on Automatic Control , vol. 60, no. 4, pp. 937–949, 2015

    work page 2015

  28. [28]

    Conforti, G

    M. Conforti, G. Cornu´ ejols, and G. Zambelli, Integer programming. Springer, 2014, vol. 271

    work page 2014

  29. [29]

    Dispersion of the discrete arb itrarily-varying channel with limited shared randomness,

    O. Kosut and J. Kliewer, “Dispersion of the discrete arb itrarily-varying channel with limited shared randomness, ” in Information Theory (ISIT), 2017 IEEE International Symposium on . IEEE, 2017, pp. 1242–1246

    work page 2017