We study finite-state finite-action Bayesian statistical decision problems. While exact error-exponent characterizations are known for several special cases, including hypothesis testing and hypothesis exclusion, the asymptotic behavior of the optimal Bayes regret is largely unknown for general decision problems. In this paper, we show that the optimal regret always decays exponentially fast and characterize its exact exponent for arbitrary loss functions. The exponent is given by the minimum multivariate Chernoff information over the minimal incompatible subsets of states, where an incompatible subset is a collection of states for which no single action is optimal for all states in the subset. Our result recovers the classical pairwise-minimum Chernoff exponent for symmetric multiple hypothesis testing and the multivariate Chernoff exponent for hypothesis exclusion, while also yielding, to the best of our knowledge, the first exact exponent characterization for list hypothesis testing.

We study the problem of discrete distribution estimation under utility-optimized local differential privacy (ULDP), which enforces local differential privacy (LDP) on sensitive data while allowing more accurate inference on non-sensitive data. In this setting, we completely characterize the fundamental privacy–utility trade-off. The converse proof builds on several key ideas, including a generalized uniform asymptotic Cramér–Rao lower bound, a reduction showing that it suffices to consider a newly defined class of extremal ULDP mechanisms, and a novel distribution decomposition technique tailored to ULDP constraints. For the achievability, we propose a class of utility-optimized block design (uBD) schemes, obtained as nontrivial modifications of the block design mechanism known to be optimal under standard LDP constraints, while incorporating the distribution decomposition idea used in the converse proof and a score-based linear estimator. These results provide a tight characterization of the estimation accuracy achievable under ULDP and reveal new insights into the structure of optimal mechanisms for privacy-preserving statistical inference.

For multiple hypothesis testing based on classical data samples, we demonstrate a quantum advantage in the optimal privacy-utility trade-off (PUT), where the privacy and utility measures are set to (quantum) local differential privacy and the pairwise-minimum Chernoff information, respectively. To show the quantum advantage, we consider some class of hypotheses that we coin smoothed point masses. For such hypotheses, we derive an upper bound of the optimal PUT achieved by classical mechanisms, which is tight for some cases, and propose a certain quantum mechanism which achieves a better PUT than the upper bound. The proposed quantum mechanism consists of a classical-quantum channel whose outputs are pure states corresponding to a symmetric informationally complete positive operator-valued measure (SIC-POVM), and a depolarizing channel.

We consider a discrete distribution estimation problem under a local differential privacy (LDP) constraint in the presence of shared randomness. For this problem, we propose a new class of LDP schemes achieving the exactly optimal privacy-utility trade-off (PUT), with the communication cost less than or equal to the size of the input data. Moreover, it is shown as a simple corollary that one-bit communication is sufficient for achieving the exactly optimal PUT for a high privacy regime if the size of the input data is an even number. The main idea is to decompose a block design scheme proposed by Park et al. (2023), based on the combinatorial concept called resolution. We call the resultant decomposed LDP scheme with shared randomness as a resolution of the original block design scheme. A resolution of a block design scheme has a communication cost less than or equal to that of the original block design scheme. Also, the resolution of a block design scheme is exactly optimal whenever the original block design scheme is exactly optimal. Accordingly, we provide a resolution of the exactly optimal subset selection scheme proposed by Ye and Barg (2018), called the Baranyai's resolution. The Baranyai's resolution is not only exactly optimal, but also it achieves the minimum communication cost among all exactly optimal resolutions of block design schemes.

In this paper, we show that there is no advantage of using non-local cooperation between source encoders in improving the optimal compression rate (or rate region) for some canonical distributed compression tasks. The tasks are the lossless distributed compression, the lossless compression with a helper, and some special cases of the lossy distributed compression for 2-component discrete memoryless sources. These negative results for distributed source coding contrast with those for multi-user channel coding: quantum or general no-signaling cooperation between channel encoders improves the capacity region for some multiple access and interference channels.

The sampling problem under local differential privacy has recently been studied with potential applications to generative models, but a fundamental analysis of its privacy-utility trade-off (PUT) remains incomplete. In this work, we define the fundamental PUT of private sampling in the minimax sense, using the $f$-divergence between original and sampling distributions as the utility measure. We characterize the exact PUT for both finite and continuous data spaces under some mild conditions on the data distributions, and propose sampling mechanisms that are universally optimal for all $f$-divergences. Our numerical experiments demonstrate the superiority of our mechanisms over baselines, in terms of theoretical utilities for finite data space and of empirical utilities for continuous data space.

We consider a discrete distribution estimation problem under a local differential privacy (LDP) constraint in the presence of shared randomness. For this problem, we propose a new class of LDP schemes achieving the exactly optimal privacy-utility trade-off (PUT), with the communication cost less than or equal to the size of the input data. Moreover, it is shown as a simple corollary that one-bit communication is sufficient for achieving the exactly optimal PUT for a high privacy regime if the input data size is an even number. The main idea is to decompose a block design scheme proposed by Park et al. (2023), based on the combinatorial concept called resolution. We call the resultant decomposed LDP scheme with shared randomness as a resolution of the original block design scheme. A resolution of a block design scheme has a communication cost less than or equal to that of the original block design scheme. Also, the resolution of a block design scheme is exactly optimal whenever the original block design scheme is exactly optimal. Accordingly, we provide two resolutions of the exactly optimal subset selection scheme proposed by Ye and Barg (2018), called the Baranyai’s resolution and the cyclic shift resolution. We show that the Baranyai’s resolution achieves the minimum communication cost among all exactly optimal resolutions of block design schemes. One drawback of the Baranyai’s resolution is that its explicit structure is unknown in general. In contrast, the cyclic shift resolution has an explicit structure, but its communication cost can be larger than that of the Baranyai’s resolution. To complement this, we also suggest resolutions of other block design schemes achieving the exactly optimal PUT for some input data size and privacy budget. Those require the minimum communication cost as the Baranyai’s resolution and have explicit structures as the cyclic shift resolution.

In this paper, we propose a new class of local differential privacy (LDP) schemes based on combinatorial block designs for a discrete distribution estimation. This class not only recovers many known LDP schemes in a unified framework of combinatorial block design, but also suggests a novel way of finding new schemes achieving the optimal (or near-optimal) privacy-utility trade-off with lower communication costs. Indeed, we find many new LDP schemes that achieve both the optimal privacy-utility trade-off and the minimum communication cost among all the unbiased schemes for a certain set of input data size and LDP constraint. Furthermore, to partially solve the sparse existence issue of block design schemes, we consider a broader class of LDP schemes based on regular and pairwise-balanced designs, called RPBD schemes, which relax one of the symmetry requirements on block designs. By considering this broader class of RPBD schemes, we can find LDP schemes achieving near-optimal privacy-utility trade-off with reasonably low communication costs for a much larger set of input data size and LDP constraint.