This paper explores Bayesian lower bounds on the minimum mean squared error (MMSE) that belong to the well-known Ziv-Zakai family. The Ziv-Zakai technique relies on connecting the bound to an$\mathsf M$-ary hypothesis testing problem. There are three versions of the Ziv-Zakai bound (ZZB): the first version relies on the so-calledvalley-filling function, the second one is a relaxation of the first bound which omits the valley-filling function, and the third one, namely the single-point ZZB (SZZB), replaces the integration present in the first two bounds with a single point maximization. The first part of this paper focuses on providing the most general version of the bounds. It is shown that these bounds hold without any assumption on the distribution of the estimand. This makes the bounds applicable to discrete and mixed distributions. Then, the SZZB is extended to an$\mathsf M$-ary setting and a version of it that holds for the multivariate setting is provided. In the second part, general properties of these bounds are provided. First, unlike the BayesianCramér-Rao bound, it is shown that all the versions of the ZZBtensorize. Second, a characterization of thehigh-noiseasymptotic is provided, which is used to argue about the tightness of the bounds. Third, a completelow-noiseasymptotic is provided under the assumptions of mixed-input distributions and Gaussian additive noise channels. In the low-noise, it is shown that the ZZB is generally tight, but there are examples for which the SZZB is not tight. In the third part, the tightness of the bounds is evaluated. First, it is shown that in the low-noise regime the ZZB without the valley-filling function, and, therefore, also the ZZB with the valley-filling function, are tight for mixed-input distributions and Gaussian additive noise channels. Second, for discrete inputs it is shown that the ZZB with the valley-filling function is always sub-optimal, and equal to zero without the valley-filling function. Third, unlike for the ZZB, an example is shown for which the SZZB is tight to the MMSE for discrete inputs. Fourth, sufficient and necessary conditions for the tightness of the bounds are provided. Finally, some examples are provided in which the bounds in the Ziv-Zakai family outperform other well-known Bayesian lower bounds, namely the Cramér-Rao bound and the maximum entropy bound.

Classification is a fundamental task in many applications on which data-driven methods have shown outstanding performances. However, it is challenging to determine whether such methods have achieved the optimal performance. This is mainly because the best achievable performance is typically unknown and hence, effectively estimating it is of prime importance. In this paper, we consider binary classification problems and we propose an estimator for the false positive rate (FPR) of the Bayes classifier, that is, the optimal classifier with respect to accuracy, from a given dataset. Our method utilizes soft labels, or real-valued labels, which are gaining significant traction thanks to their properties. We thoroughly examine various theoretical properties of our estimator, including its consistency, unbiasedness, rate of convergence, and variance. To enhance the versatility of our estimator beyond soft labels, we also consider noisy labels, which encompass binary labels. For noisy labels, we develop effective FPR estimators by leveraging a denoising technique and the Nadaraya-Watson estimator. Due to the symmetry of the problem, our results can be readily applied to estimate the false negative rate of the Bayes classifier.

We consider the problem of secure communication over a noiseless 1-2-1 network, an abstract model introduced to capture the directivity characteristic of mmWave communications. We focus on structured networks, which we refer to as 1-2-1 atomic networks. Broadly speaking, these are characterized by a source, a destination, and three layers of intermediate nodes with sparse connections. The goal is for the source to securely communicate to the destination in the presence of an eavesdropper with unbounded computation capabilities, but limited network presence. We derive novel upper and lower bounds on the secrecy capacity of 1-2-1 atomic networks. These bounds are shown to be tighter than existing bounds in some regimes. Moreover, in such regimes, the bounds match and hence, they characterize the secrecy capacity of 1-2-1 atomic networks.

This paper studies the problem of data permutation recovery, where the goal is to estimate the ordering of an$n$-dimensional data vector given a noisy observation of it. The focus is on scenarios where the noise is additive Gaussian with an arbitrary known covariance matrix. The goal is to characterize the probability of error and its behavior when a linear decoder (that is, a linear estimator followed by a sorting operation) is employed. First, a general expression is derived for the probability of error when a linear decoder is used. The derived expression holds for any continuous distribution of the input data vector, and when the noise has memory. Then, the rates of convergence of the probability of error in the low-noise and high-noise regimes are investigated when a simple linear decoder is used. It is shown that in the low-noise regime, the probability of error can quadratically increase with$n$, and in the high-noise regime it behaves as$1-1/n!$for several distributions of interest. Finally, upper and lower bounds on the probability of correctness with respect to$n$are derived for the case of an i.i.d. data distribution and show that the rate of convergence is at least exponential in$n$. The results showcase that the permutation recovery problem is noise dominated, which motivates the study of more relaxed versions of the permutation recovery problem that are also discussed.

This paper explores the Ziv-Zakai bound (ZZB), which is a well-known Bayesian lower bound on the Minimum Mean Squared Error (MMSE). First, it is shown that the ZZB holds without any assumption on the distribution of the estimand, that is, the estimand does not necessarily need to have a probability density function. The ZZB is then further analyzed in the high-noise and low-noise regimes and shown to always tensorize. Finally, the tightness of the ZZB is investigated under several aspects, such as the number of hypotheses and the usefulness of the valley-filling function. In particular, a sufficient and necessary condition for the tightness of the bound with continuous inputs is provided, and it is shown that the bound is never tight for discrete input distributions with a support set that does not have an accumulation point at zero.

Classification is a fundamental task in science and engineering on which machine learning methods have shown outstanding performances. However, it is challenging to determine whether such methods have achieved the Bayes error rate, that is, the lowest error rate attained by any classifier. This is mainly due to the fact that the Bayes error rate is not known in general and hence, effectively estimating it is paramount. Inspired by the work by Ishida et al. (2023), we propose an estimator for the Bayes error rate of supervised multi-class classification problems. We analyze several theoretical aspects of such estimator, including its consistency, unbiasedness, convergence rate, variance, and robustness. We also propose a denoising method that reduces the noise that potentially corrupts the data labels, and we improve the robustness of the proposed estimator to outliers by incorporating the median-of-means estimator. Our analysis demonstrates the consistency, asymptotic unbiasedness, convergence rate, and robustness of the proposed estimators. Finally, we validate the effectiveness of our theoretical results via experiments both on synthetic data under various noise settings and on real data.

This paper considers the problem of recovering the ranking of a data vector from noisy observations, up to a distortion. Specifically, the noisy observations consist of the original data vector corrupted by isotropic additive Gaussian noise, and the distortion is measured in terms of a distance function between the estimated ranking and the true ranking of the original data vector. First, it is shown that an optimal (in terms of error probability) decision rule for the estimation task simply outputs the ranking of the noisy observation. Then, the error probability incurred by such a decision rule is characterized in the low-noise regime, and shown to grow sublinearly with the noise standard deviation. This result highlights that the proposed approximate version of the ranking recovery problem is significantly less noise-dominated than the exact recovery considered in [Jeong, ISIT 2021].

This paper considers the problem of recovering the permutation of an n-dimensional random vector X observed in Gaussian noise. First, a general expression for the probability of error is derived when a linear decoder (i.e., linear estimator followed by a sorting operation) is used. The derived expression holds with minimal assumptions on the distribution of X and when the noise has memory. Second, for the case of isotropic noise (i.e., noise with a diagonal scalar covariance matrix), the rates of convergence of the probability of error are characterized in the high and low noise regimes. In the low noise regime, for every dimension$n$, the probability of error is shown to behave proportionally to$\sigma$, where$\sigma$is the noise standard deviation. Moreover, the slope is computed exactly for several distributions and it is shown to behave quadratically in$n$. In the high noise regime, for every dimension$n$, the probability of correctness is shown to behave as$1/\sigma$, and the exact expression for the rate of convergence is also provided.

This paper considers a noisy data structure recovery problem. Specifically, the goal is to investigate the following question: Given a noisy observation of the data, according to which permutation was the original data sorted? The main focus is on scenarios where data is generated according to an isotropic Gaussian distribution, and the perturbation consists of adding Gaussian noise with diagonal scalar covariance matrix. This problem is posed within a hypothesis testing framework. First, the optimal decision criterion is characterized and shown to be identical to the hypothesis of the observation. Then, by leveraging the structure of the optimal decision criterion, the probability of error is characterized. Finally, the logarithmic behavior (i.e., the exponent) of the probability of error is derived in the regime where the dimension of the data goes to infinity.

This letter considers an M-ary hypothesis testing problem on an n-dimensional random vector perturbed by the addition of Gaussian noise. A novel expression for the gradient of the error probability, with respect to the covariance matrix of the noise, is derived and shown to be a function of the cross-covariance matrix between the noise matrix (i.e., the matrix obtained by multiplying the noise vector by its transpose) and Bernoulli random variables associated with the correctness event.

In this paper, we present an efficient method to construct a good rate-compatible punctured polar (RCPP) code for incremental redundancy hybrid automatic repeat request schemes. One of the major challenges on the construction of a RCPP code is to optimize a common information set which is good for all the (punctured) polar codes in the family. Unfortunately, there is no efficient way to solve the above problem. In the proposed construction, a common information set is simply optimized for the highest-rate code in the family and then it is updated to yield an effective information set for each other code, by keeping the condition that information bits are unchanged during retransmissions. This is enabled by presenting a novel hierarchical (or reciprocal) puncturing and information-copy technique. Specifically, some information bits are copied to frozen-bit channels whose locations are carefully determined according to rate-compatible puncturing patterns. This yields an information-dependent frozen vector in the encoding part. Also, in the decoding part, the effective information sets are obtained by properly combining the common information set and the information-dependent frozen vector. More importantly, the impact of unknown frozen bits are avoided due to the special structure of the proposed hierarchical (or reciprocal) puncturing. Simulation results verify that the proposed RCPP code can yield a significant performance gain (about 2 dB) over a benchmark RCPP code where both codes use the same rate-compatible puncturing patterns but the latter uses the conventional all-zero frozen vector. Therefore, the proposed method would be crucial to construct a good RCPP code efficiently.