Rate-reliability functions for deterministic identification

• URL: http://arxiv.org/abs/2502.02389v1
• Date: Tue, 04 Feb 2025 15:09:14 GMT
• Title: Rate-reliability functions for deterministic identification
• Authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter,
• Abstract summary: We find that for positive exponents linear scaling is restored, now with a rate that is a function of the reliability exponents. We extend our results to classical-quantum channels and quantum channels with product input restriction.
• Score: 49.126395046088014
• License:
• Abstract: We investigate deterministic identification over arbitrary memoryless channels under the constraint that the error probabilities of first and second kind are exponentially small in the block length $n$, controlled by reliability exponents $E_1,E_2 \geq 0$. In contrast to the regime of slowly vanishing errors, where the identifiable message length scales as $\Theta(n\log n)$, here we find that for positive exponents linear scaling is restored, now with a rate that is a function of the reliability exponents. We give upper and lower bounds on the ensuing rate-reliability function in terms of (the logarithm of) the packing and covering numbers of the channel output set, which for small error exponents $E_1,E_2>0$ can be expanded in leading order as the product of the Minkowski dimension of a certain parametrisation the channel output set and $\log\min\{E_1,E_2\}$. These allow us to recover the previously observed slightly superlinear identification rates, and offer a different perspective for understanding them in more traditional information theory terms. We further illustrate our results with a discussion of the case of dimension zero, and extend them to classical-quantum channels and quantum channels with tensor product input restriction.

Related papers

• Error exponent of activated non-signaling assisted classical-quantum channel coding [12.221087476416056]
  We find that the optimal exponent--also called reliability function--is equal to the well-known sphere packing bound. Remarkably, there is no critical rate and our characterization remains tight for arbitrarily low rates below the capacity.
  arXiv  Detail & Related papers  (2024-10-01T21:26:17Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [49.126395046088014]
  We consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Our main findings are that the maximum length of messages thus identifiable scales superlinearly as $R,nlog n$ with the block length $n$. We show that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code.
  arXiv  Detail & Related papers  (2024-02-14T11:59:30Z)
• Lower Bounds on Error Exponents via a New Quantum Decoder [14.304623719903972]
  We show new lower bounds on the error exponent on the classical-quantum and the entanglement-assisted channel coding problem. Our bounds are expressed in terms of measured (for the one-shot bounds) and sandwiched (for the bounds) channel R'enyi mutual information of order between 1/2 and 1.
  arXiv  Detail & Related papers  (2023-10-13T11:22:49Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• Exponentially Weighted l_2 Regularization Strategy in Constructing Reinforced Second-order Fuzzy Rule-based Model [72.57056258027336]
  In the conventional Takagi-Sugeno-Kang (TSK)-type fuzzy models, constant or linear functions are usually utilized as the consequent parts of the fuzzy rules. We introduce an exponential weight approach inspired by the weight function theory encountered in harmonic analysis.
  arXiv  Detail & Related papers  (2020-07-02T15:42:15Z)
• Geometric distinguishability measures limit quantum channel estimation and discrimination [6.345523830122166]
  We show that a chain-rule property holds for the right logarithmic derivative Fisher information and the geometric R'enyi relative entropy. In channel estimation, these results imply a condition for the unattainability of Heisenberg scaling. More generally, we introduce the amortized quantum Fisher information as a conceptual framework for analyzing general sequential protocols.
  arXiv  Detail & Related papers  (2020-04-22T17:11:34Z)
• From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography [0.0]
  We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings. We then establish a connection between covert communication and deniability to propose DC-QKE. We present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.
  arXiv  Detail & Related papers  (2020-03-25T22:20:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.