Recent research on Doeblin coefficients has shed light on their usefulness as a multi-way generalization of the Dobrushin contraction coefficient for TV distance, in a separate vein from their classic role in the theory of Markov chain ergodicity. However, strong conditions, such as being bounded away from 0, are typically necessary for Doeblin coefficients to establish the existence of information contraction. Building on recently formulated concepts of nonlinear information contraction, we aim to propose a finer-grained Doeblin-based characterization of multi-way contraction behavior which yields non-vacuous contraction guarantees even for channels whose Doeblin coefficient is 0. To this end, we introduce the notion of aDoeblin curve—a nonlinear function which quantifies the contraction behavior of a Markov kernel on collections of input distributions at specific levels of divergence and power. Through the course of our analysis, we develop a new variational characterization of Doeblin coefficients, present several properties of Doeblin curves, define several versions of power-constrained Doeblin curves, and derive upper and lower bounds using our aforementioned variational characterization. We then utilize these results in diverse areas, including generalization bounds for noisy iterative optimization, error bounds for reliable computation with noisy circuits, and differential privacy guarantees for online iterative algorithms. In particular, we extend results in these areas to broader domains or group settings, leveraging Doeblin curves to reveal finer-grained contraction phenomena than Doeblin coefficients.

In this work, we develop a hypothesis testing framework to determine whether pairwise comparison data is generated by an underlying generalized Thurstone model $\mathcal{T}_F$ for a given choice function $F$. While prior work has predominantly focused on parameter estimation and uncertainty quantification for such models, we address the fundamental problem of minimax hypothesis testing for $\mathcal{T}_F$ models. We formulate this testing problem by introducing a notion of separation distance between general pairwise comparison models and the class of $\mathcal{T}_F$ models. We then derive upper and lower bounds on the critical threshold for testing that depend on the topology of the observation graph. For the special case of complete observation graphs, this threshold scales as $\Theta((nk)^{-1/2})$, where $n$ is the number of agents and $k$ is the number of comparisons per pair. Furthermore, we propose a hypothesis test based on our separation distance, construct confidence intervals, establish time-uniform bounds on the probabilities of type I and II errors using reverse martingale techniques, and derive minimax lower bounds using information-theoretic methods. Finally, we validate our results through experiments on synthetic and real-world datasets.

Antithetic variates constitute a well-known variance reduction technique for Monte Carlo sampling methods and related applications. However, many standard antithetic variance bounds do not provide quantitative estimates of the theoretical gains enjoyed by these methods. As a step towards remedying this, in this work, we derive stronger antithetic variance reduction inequalities under anti-Lipschitz and strongly isotonic (as opposed to merely monotonic) assumptions in the univariate and multivariate settings, respectively, which quantify the magnitude of variance reduction. Over the course of our analysis, we develop the concept of an antithetic index and illustrate some of its properties. Furthermore, we show how our stronger antithetic variance reduction inequalities can be used to provide better theoretical guarantees when using antithetic variates in various applications. These applications include approximating integrals, function approximation, concentration inequalities, as well as stochastic optimization. Our arguments utilize and develop ideas from correlation inequalities and first-order optimization theory among other tools.

Maximal leakage quantifies the leakage of information from data$X \in \mathcal{X}$due to an observation$Y$. While fundamental properties of maximal leakage, such as data processing, sub-additivity, and its connection to mutual information, are well-established, its behavior over Bayesian networks is not well-understood and existing bounds are primarily limited to binary$\mathcal{X}$. In this paper, we investigate the behavior of maximal leakage over Bayesian networks with finite alphabets. Our bounds on maximal leakage are established by utilizing coupling-based characterizations which exist for channels satisfying certain conditions. Furthermore, we provide more general conditions under which such coupling characterizations hold for$\vert \mathcal{X} \vert =4$. In the course of our analysis, we also present a new simultaneous coupling result on maximal leakage exponents. Finally, we illustrate the effectiveness of the proposed bounds with some examples.

The Bradley-Terry-Luce (BTL) model is one of the most widely used models for ranking a collection of items or agents based on pairwise comparisons among them. Specifically, givennagents, the BTL model endows each agentiwith a latent skill score αi> 0 and posits that the probability that agentiis preferred over agentjin a comparison is αi/(αi+ αj). In this work, our objective is to formulate a hypothesis test that determines whether a given pairwise comparison dataset, withkcomparisons per pair of agents, originates from an underlying BTL model. We formalize this testing problem in the minimax sense and define the critical threshold of the problem. We then establish upper bounds on the critical threshold for general observation graphs and highlight their dependence on two fundamental structural properties: principal ratio and edge expansion. Additionally, we derive lower bounds on the critical threshold for the special case of complete induced graphs, thereby demonstrating that the critical threshold scales as Θ((nk)−1/2) in a minimax sense in this case. In particular, our test statistic for the upper bounds is based on a new approximation we derive for the separation distance between general pairwise comparison models and the class of BTL models. To further assess the performance of our statistical test, we prove upper bounds on conditional probabilities of error. Additionally, we derive several other auxiliary results over the course of our analysis, such as bounds on principal ratios of graphs, ℓ2-bounds on BTL parameter estimation under model mismatch, stability of rankings under the BTL model with small model mismatch, etc. Finally, we conduct several experiments on synthetic and real-world datasets to validate some of our theoretical results. Moreover, we also propose an approach based on permutation testing to determine the threshold of our test in a data-driven manner in these experiments.

Permutation networks and multiple-access channels (MACs) are objects of interest in modern information theory which find application in modeling biological storage mechanisms and wireless communication systems. In this paper, we present two variations of the recently introduced permutation adder multiple-access channel (PAMAC), and characterize their respective permutation capacity regions as an initial step towards establishing such results for general MACs. Firstly, we define the left-permutation adder MAC by interchanging the order of the adder and random permutation blocks in the original PAMAC, causing each sender's codeword to be shuffled by a different random permutation. We show that multiset coding with Bernoulli samples is a viable achievability scheme under this structural modification by extending a root stability argument from the binary PAMAC literature to general p-ary alphabets. Separately from the above, we define the permutation group-adder MAC by replacing the integer addition block in the original PAMAC with a modular addition block over$\mathbb{Z}_{p}$. Our achievability proof in this setting crucially demonstrates that time sharing strategies based on mixed-radix coding naturally generalize to an array of permutation network models beyond the original PAMAC. Lastly, using Fano's inequality and manipulations of directed graphical models, we obtain converse bounds matching our achievability results, ultimately illustrating that subtle modifications to a permutation network model may bring about significant qualitative changes in its capacity region.

Doeblin coefficients are fundamental tools in the analysis of Markov chains for establishing ergodicity and exponential convergence rates. However, strong conditions, such as Doeblin coefficients being bounded away from 0, are typically required to yield useful convergence or information contraction guarantees. Our work aims to illuminate the contraction behavior of Markov kernels under more relaxed conditions, such as the case where Doeblin coefficients are 0. To do this, we introduce the notion of a Doeblin curve—a nonlinear function that quantifies the contraction behavior of a Markov kernel on a collection of input distributions. We develop new variational characterizations of Doeblin coefficients and use them to derive useful bounds on the Doeblin curve. In the course of this analysis, we present several properties of Doeblin curves and define power-constrained Doeblin curves. Furthermore, our analysis motivates a generalized definition of differential privacy in the group setting. We discuss this motivation and several properties of this definition to lay the groundwork for its application in future.

Backdoor attacks embed an attacker-chosen pattern into inputs to cause model misclassification. This security threat to machine learning has been a long concern. There are a number of defense techniques proposed by the community. Do they work for a large spectrum of attacks?As we argue that they are significant and prevalent in contemporary research, and we conduct a systematic study on 14 attacks and 12 defenses. Our empirical results show that existing defenses often fail on certain attacks. To understand the reason, we study the characteristics of backdoor attacks through theoretical analysis. Particularly, we formulate backdoor poisoning as a continual learning task, and introduce two key properties: orthogonality and linearity. These two characteristics in-depth explain how backdoors are learned by models from a theoretical perspective. This helps to understand the reason behind the failure of various defense techniques. Through our study, we highlight open challenges in defending against backdoor attacks and provide future directions.

In this paper, we study the problem of learning the skill distribution of a population of agents from observations of pairwise games in a tournament. These games are played amongnrandomly drawn agents from the population. The agents in our model can be individuals, sports teams, or even Wall Street fund managers. Formally, we postulate that the likelihoods of outcomes of games are governed by the parametric Bradley-Terry-Luce (or multinomial logit) model, where the probability of an agent beating another is the ratio between its skill level and the pairwise sum of skill levels, and the skill parameters are drawn from an unknown, non-parametric skill density of interest. The above problem is, in essence, to learn a distribution from noisy and quantized observations. We propose a surprisingly simple and tractable algorithm that learns the skill density with near-optimal minimax mean squared error scaling as$n^{-1+\varepsilon }$, for any$\varepsilon \gt 0$, so long as the density is smooth. Our approach brings together prior work on learning skill parameters from pairwise comparisons with kernel density estimation from non-parametric statistics. We then prove information theoretic lower bounds which establish minimax near-optimality of the skill parameter estimation technique used in our algorithm. These bounds utilize a continuum version of Fano’s method along with a careful covering argument. Furthermore, we show that estimation error bounds for the skill density translate to theoretical guarantees on estimating the differential entropy and other bounded statistics of the skill density. Finally, we apply our algorithm to data from soccer world cups and leagues, cricket world cups, and even mutual funds. We find that the differential entropy of a learnt distribution provides a quantitative measure of overall skill in a tournament, which in turn can provide explanations for popular beliefs about perceived qualities of sporting and other tournaments.

Point-to-point permutation channels are useful models of communication networks and biological storage mechanisms and have received theoretical attention in recent years. Propelled by relevant advances in this area, we analyze thepermutation adder multiple-access channel(PAMAC) in this work. In the PAMAC network model,dsenders communicate with a single receiver by transmittingp-ary codewords through an adder multiple-access channel whose output is subsequently shuffled by a random permutation block. We define a suitable notion ofpermutation capacity regionCpermfor this model, and establish thatCpermis the simplex consisting of all rated-tuples that sum tod(p- 1)/2 or less. We achieve this sum-rate by encoding messages as i.i.d. samples from categorical distributions with carefully chosen parameters, and we derive an inner bound onCpermby extending the concept of time sharing to the permutation channel setting. Our proof notably illuminates various connections between mixed-radix numerical systems and coding schemes for multiple-access channels. Furthermore, we derive an alternative inner bound onCpermfor the binary PAMAC by analyzing the root stability of the probability generating function of the adder’s output distribution. Using eigenvalue perturbation results, we obtain error bounds on the spectrum of the probability generating function’s companion matrix, providing quantitative estimates of decoding performance. Finally, we obtain a converse bound onCpermmatching our achievability result.

Doeblin coefficients are a classical tool for analyzing the ergodicity and exponential convergence rates of Markov chains. Propelled by recent works on contraction coefficients of strong data processing inequalities, we investigate whether Doeblin coefficients also exhibit some of the notable properties of canonical contraction coefficients. In this paper, we present several new structural and geometric properties of Doeblin coefficients. Specifically, we show that Doeblin coefficients form a multi-way divergence, exhibit tensorization, and possess an extremal trace characterization. We then show that they also have extremal coupling and simultaneously maximal coupling characterizations. By leveraging these characterizations, we demonstrate that Doeblin coefficients act as a nice generalization of the well-known total variation (TV) distance to a multi-way divergence, enabling us to measure the “distance” between multiple distributions rather than just two. We then prove that Doeblin coefficients exhibit contraction properties over Bayesian networks similar to other canonical contraction coefficients. We additionally derive some other results and discuss an application of Doeblin coefficients to distribution fusion. Finally, in a complementary vein, we introduce and discuss three new quantities:max-Doeblin coefficient,max-DeGroot distance, andmin-DeGroot distance. The max-Doeblin coefficient shares a connection with the concept of maximal leakage in information security; we explore its properties and provide a coupling characterization. On the other hand, the max-DeGroot and min-DeGroot measures extend the concept of DeGroot distance to multiple distributions.

Propelled by recent advances in the study of point-to-point permutation channels, which stem from communication networks and biological communications applications, we analyze the permutation binary adder multiple-access channel (PAMAC) in this work. The PAMAC network model consists of d senders communicating with a single receiver through a standard binary adder multiple-access channel followed by a random permutation block that shuffles the output codeword of the multiple-access channel. We formally define an appropriate notion of permutation sum-capacity Cpsumfor this model, and then establish that ${{\text{C}}_{{\text{psum }}}} = \frac{d}{2}$. To derive an achievability bound we construct d randomized encoders where input codewords are i.i.d. samples from Bernoulli distributions with carefully chosen parameters. These parameters can be perceived as roots of the probability generating function of the distribution over the output alphabet after the PAMAC's addition operation. Our achievability proof crucially uses eigenvalue perturbation results to provide quantitative estimates on the stability of the roots, which allows us to analyze decoding performance. This argument also yields an inner bound on the permutation capacity region of the PAMAC model. Finally, we also obtain a converse bound on Cpsummatching our achievability result.

Doeblin coefficients are a classical tool to study the ergodicity of Markov chains. Propelled by recent works on contraction coefficients of strong data processing inequalities, we investigate whether Doeblin coefficients also exhibit some of the notable properties of canonical contraction coefficients. Specifically, we present various new structural and geometric properties of Doeblin coefficients. Then, by establishing an extremal coupling characterization, we show that Doeblin coefficients generalize the well-known total variation (TV) distance to a multi-way divergence, enabling us to measure the distance between multiple distributions rather than just two. We also demonstrate that Doeblin coefficients exhibit contraction properties over Bayesian networks similar to other canonical contraction coefficients. Finally, we discuss how Doeblin coefficients can be used to define a new rule for fusion of probability mass functions.

The Bradley-Terry-Luce (BTL) model is one of the most widely used models for ranking a set of items given data about pairwise comparisons among them. While several studies in the literature have attempted to empirically test how accurately a BTL model can model some given pairwise comparison data, this work aims to develop a formal, computationally efficient hypothesis test to determine whether the BTL model accurately represents the data. Specifically, we first propose such a formal hypothesis test, establish an upper bound on the critical radius of the proposed test, and then provide a complementary lower bound on the critical radius. Our bounds prove the minimax optimality of the scaling of the critical radius with respect to the number of items (up to constant factors). Finally, we also take the first step towards characterizing the stability of rankings under the BTL model when there is a small model mismatch.

We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distribution $D$, and we are interested in designing a (truthful) mechanism that has good performance for all "true distributions" that are close to $D$ in Total Variation (TV) distance. We show that DSIC and BIC mechanisms in this setting are strongly robust with respect to TV distance, for any bounded objective function $\mathcal{O}$, extending a recent result of Brustle et al. ([BCD20], EC 2020). At the heart of our result is a fundamental duality property of total variation distance. As direct applications of our result, we (i) demonstrate how to find approximately revenue-optimal and approximately BIC mechanisms for weakly dependent prior distributions; (ii) show how to find correlation-robust mechanisms when only ``noisy'' versions of marginals are accessible, extending recent results of Bei et. al. ([BGLT19], SODA 2019); (iii) prove that prophet-inequality type guarantees are preserved for correlated priors, recovering a variant of a result of D{\"u}tting and Kesselheim ([DK19], EC 2019) as a special case; (iv) give a new necessary condition for a correlated distribution to witness an infinite separation in revenue between simple and optimal mechanisms, complementing recent results of Psomas et al. ([PSCW22], NeurIPS 2022); (v) give a new condition for simple mechanisms to approximate revenue-optimal mechanisms for the case of a single agent whose type is drawn from a correlated distribution that can be captured by a Markov Random Field, complementing recent results of Cai and Oikonomou ([CO21], EC 2021).

In this work, we study empirical risk minimization (ERM) within a federated learning framework, where a central server seeks to minimize an ERM objective function using$n$samples of training data that is stored across$m$clients and the server. The recent flurry of research in this area has identified the Federated Averaging ($\mathtt{FedAve} $) algorithm as the staple for determining$\epsilon $-approximate solutions to the ERM problem. Similar to standard optimization algorithms, e.g., stochastic gradient descent, the convergence analysis of$\mathtt{FedAve} $and its variants only relies on smoothness of the loss function in the optimization parameter. However, loss functions are often very smooth in the training data too. To exploit this additional smoothness in data in a federated learning context, we propose the Federated Low Rank Gradient Descent (FedLRGD) algorithm. Since smoothness in data induces an approximate low rank structure on the gradient of the loss function, our algorithm first performs a few rounds of communication between the server and clients to learn weights that the server can use to approximate clients’ gradients using its own gradients. Then, our algorithm solves the ERM problem at the server using an inexact gradient descent method. To theoretically demonstrate that FedLRGD can have superior performance to$\mathtt{FedAve} $, we present a notion of federated oracle complexity as a counterpart to canonical oracle complexity in the optimization literature. Under some assumptions on the loss function, e.g., strong convexity and smoothness in the parameter,$\eta $-Hölder class smoothness in the data, etc., we prove that the federated oracle complexity of$LRGD $scales like$\phi m (p/\epsilon)^{\Theta (d/\eta)}$and that of$\mathtt{FedAve} $scales like$\phi m (p / \epsilon)^{3/4}$(neglecting typically sub-dominant factors), where$\phi \gg 1$is the ratio of client-to-server communication time to gradient computation time,$p$is the parameter dimension, and$d$is the data dimension. Then, we show that when$d$is small compared to$n$and the loss function is sufficiently smooth in the data, i.e.,$\eta = \Theta (d)$, FedLRGD beats$\mathtt{FedAve} $in federated oracle complexity. Finally, in the course of analyzing FedLRGD, we also establish a general result on low rank approximation of smooth latent variable models.

We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex$X$at layer 0, and$k + 1$vertices at layer$k \geq 1$, which are at a distance of$k$from$X$. Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0,$X$is given a uniform random bit. At time$k \geq 1$, each vertex in layer$k$receives transmitted bits from its parents in layer$k-1$, where the bits pass through independent binary symmetric channels with common crossover probability$\delta \in \left({0,\frac {1}{2}}\right)$during the process of transmission. Then, each vertex at layer$k$with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover$X$with probability of error better than$\frac {1}{2}$from all vertices at layer$k$as$k \rightarrow \infty $. Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattices, with boundary conditions that limit the number of sites at each time$k$to$k+1$. Inspired by the literature surrounding the “positive rates conjecture” for 1D probabilistic cellular automata, we conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level$\delta $and the choice of common Boolean processing function. In this paper, we make considerable progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of$X$is impossible for any$\delta \in \left({0,\frac {1}{2}}\right)$provided that all vertices with indegree 2 use either AND or XOR for their processing functions. Furthermore, we propose a detailed and general martingale-based approach that establishes the impossibility of recovering$X$for any$\delta \in \left({0,\frac {1}{2}}\right)$when all NAND processing functions are used if certain structured supermartingales can be rigorously constructed. We also provide strong numerical evidence for the existence of these supermartingales by computing several explicit examples for different values of$\delta $via linear programming.

We investigate the problem of broadcasting a bit on a 2D regular grid. Consider a directed acyclic graph with the structure of a 2D regular grid, which has a single source vertex$X$at layer 0, and$k+1$vertices at distance of$k\geq 1$from$X$at layer$k$. Every vertex has outdegree 2, the boundary vertices have indegree 1, and the interior vertices have indegree 2. At time 0,$X$is given a uniform random bit. At time$k\geq 1$, each vertex in layer$k$receives bits from its parents in layer$k-1$, where the bits pass through binary symmetric channels with crossover probability$\delta\in\left(0,\frac{1}{2}\right)$. Each vertex with indegree 2 then combines its input bits with a common Boolean processing function to produce its output bit. The goal is to reconstruct$X$with probability of error less than$\frac{1}{2}$from all vertices at layer$k$as$k\rightarrow\infty$. Besides their natural interpretation in communication networks, such stochastic processes can be construed as 1D probabilistic cellular automata (PCA) with boundary conditions on the number of sites per layer. Inspired by the “positive rates conjecture” for 1D PCA, we establish that reconstruction of$X$is impossible for any$\delta$provided that either AND or XOR gates are employed as the common processing function. Furthermore, we show that if certain structured supermartingales exist, reconstruction is impossible for any$\delta$when a common NAND processing function is used. We also provide numerical evidence for the existence of these supermartingales using linear programming.

The "permutation channel" model is a convenient representation of certain communication networks, where packets are not indexed and delivered out-of-order, and closely resembles models of DNA based storage systems. It consists of a standard discrete memoryless channel (DMC) followed by an independent random permutation block that permutes the output codewords of the DMC. In this paper, we present some new general bounds on the so called permutation channel capacity of such channels. Specifically, on the achievability front, we derive a lower bound on the permutation channel capacity of any DMC in terms of the rank of the stochastic matrix of the DMC. On the converse front, we illustrate two complementary upper bounds on the permutation channel capacity of any DMC whose stochastic matrix is entry-wise strictly positive. Together, these bounds characterize the permutation channel capacities of entry-wise strictly positive and "full rank" DMCs. Finally, we also demonstrate two related results concerning the well-known degradation preorder. The first constructs a symmetric channel for any DMC such that the DMC is a degraded version of the symmetric channel, and the second demonstrates the monotonicity of permutation channel capacity.

A modal decomposition is a useful tool that deconstructs the statistical dependence between two random variables by decomposing their joint distribution into orthogonal modes. Historically, modal decompositions have played important roles in statistics and information theory, e.g., in the study of maximal correlation. They are defined using the singular value decompositions of divergence transition matrices (DTMs) and conditional expectation operators corresponding to joint distributions. In this paper, we first characterize the set of all DTMs, and illustrate how the associated conditional expectation operators are the only weak contractions among a class of natural candidates. While modal decompositions have several modern machine learning applications, such as feature extraction from categorical data, the sample complexity of estimating them in such scenarios has not been analyzed. Hence, we also establish some non-asymptotic sample complexity results for the problem of estimating dominant modes of an unknown joint distribution from training data.

In this paper, we study the problem of learning the skill distribution of a population of agents from observations of pairwise games in a tournament. These games are played among randomly drawn agents from the population. The agents in our model can be individuals, sports teams, or Wall Street fund managers. Formally, we postulate that the likelihoods of outcomes of games are governed by the parametric Bradley-Terry-Luce (or multinomial logit) model, where the probability of an agent beating another is the ratio between its skill level and the pairwise sum of skill levels, and the skill parameters are drawn from an unknown, non-parametric skill density of interest. The problem is, in essence, to learn a distribution from noisy, quantized observations. We propose a surprisingly simple and tractable algorithm that learns the skill density with near-optimal minimax mean squared error scaling as $n^{-1+\varepsilon}$, for any $\varepsilon>0$, so long as the density is smooth. Our approach brings together prior work on learning skill parameters from pairwise comparisons with kernel density estimation from non-parametric statistics. Furthermore, we prove information theoretic lower bounds which establish minimax optimality of the skill parameter estimation technique used in our algorithm. These bounds utilize a continuum version of Fano's method along with a careful covering argument. We apply our algorithm to various soccer leagues and world cups, cricket world cups, and mutual funds. We find that the entropy of a learnt distribution provides a quantitative measure of skill, which in turn provides rigorous explanations for popular beliefs about perceived qualities of sporting events, e.g., soccer league rankings. Finally, we apply our method to assess the skill distributions of mutual funds. Our results shed light on the abundance of low quality funds prior to the Great Recession of 2008, and the domination of the industry by more skilled funds after the financial crisis.

In this paper, we formally define and analyze the class of noisy permutation channels. The noisy permutation channel model constitutes a standard discrete memoryless channel (DMC) followed by an independent random permutation that reorders the output codeword of the DMC. While coding theoretic aspects of this model have been studied extensively, particularly in the context of reliable communication in network settings where packets undergo transpositions, and closely related models of DNA based storage systems have also been analyzed recently, we initiate an information theoretic study of this model by defining an appropriate notion of noisy permutation channel capacity. Specifically, on the achievability front, we prove a lower bound on the noisy permutation channel capacity of any DMC in terms of the rank of the stochastic matrix of the DMC. On the converse front, we establish two upper bounds on the noisy permutation channel capacity of any DMC whose stochastic matrix is strictly positive (entry-wise). Together, these bounds yield coding theorems that characterize the noisy permutation channel capacities of every strictly positive and “full rank” DMC, and our achievability proof yields a conceptually simple, computationally efficient, and capacity achieving coding scheme for such DMCs. Furthermore, we also demonstrate the relation between the well-known output degradation preorder over channels and noisy permutation channel capacity. In fact, the proof of one of our converse bounds exploits a degradation result that constructs a symmetric channel for any DMC such that the DMC is a degraded version of the symmetric channel. Finally, we illustrate some examples such as the special cases of binary symmetric channels and (general) erasure channels. Somewhat surprisingly, our results suggest that noisy permutation channel capacities are generally quite agnostic to the parameters that define the DMCs.

We study the following generalization of the wellknown model of broadcasting on trees. Consider an infinite directed acyclic graph (DAG) with a unique source vertex X. Let the collection of vertices at distance k from X be called the kth layer, and suppose every non-source vertex has indegree d ≥ 2. At layer 0, the source vertex is given a random bit. At layer k ≥ 1, each vertex receives d bits from its parents in the (k-1)th layer, which are transmitted along edges that are independent binary symmetric channels (BSCs) with crossover probability δ ∈ (0, 1/2). Each vertex combines its d noisy inputs using a 2 deterministic d-ary Boolean processing function that generates the value at the vertex. The goal is to be able to reconstruct the original bit X with probability of error bounded away from 1/2 using the values of all vertices at an arbitrarily deep layer k. This question is closely related to models of reliable computation and storage, and information flow in biological networks. In this paper, we treat the case of randomly constructed DAGs, for which we show that broadcasting is only possible if the BSC noise level δ is below a certain (degree and function dependent) critical threshold. For d ≥ 3, and random DAGs with layers of size Ω(log(k)) and majority processing functions, we identify the critical threshold. For d = 2, we establish a similar result for the NAND processing function. We also prove a partial converse result for odd d ≥ 3 illustrating that the identified thresholds are impossible to improve by selecting different processing functions if the decoder is restricted to using a single vertex's value. Finally, for any BSC noise level δ, we construct explicit DAGs (using regular bipartite lossless expander graphs) with bounded degree and layers of size Θ(log(k)) admitting reconstruction. In particular, we show that the first r layers of such DAGs can be generated in either deterministic quasipolynomial time or randomized polylogarithmic time in r. These results portray a doubly-exponential advantage for storing a bit in bounded degree DAGs compared to trees, where d = 1 but layer sizes need to grow exponentially with depth in order for broadcasting to be possible.

We study a generalization of the problem of broadcasting on trees to the setting of directed acyclic graphs (DAGs). At time 0, a source vertex X transmits a uniform bit along binary symmetric channels (BSCs) to a set of vertices called layer 1. Each vertex except X has indegree d. At time k ≥ 1, vertices at layer k apply d-input Boolean processing functions to their received bits and send out the results to vertices at layer k + 1. We say that broadcasting is possible if we can reconstruct X with probability of error bounded away from 1/2 using the values of all vertices at an arbitrarily deep layer k. This question is closely related to models of reliable computation and storage, probabilistic cellular automata, and information How in biological networks. In this work, we analyze randomly constructed DAGs and demonstrate that broadcasting is only possible if the BSC noise level is below a certain (degree and function dependent) critical threshold. Specifically, for every d ≥ 3, we identify the critical threshold for random DAGs with layers of size Ω(log(k)) and majority processing functions. For d = 2, we establish a similar result for the NAND processing function. Furthermore, for odd d ≥ 3, we prove that the identified thresholds cannot be improved by other processing functions if reconstruction is required from a single vertex. Finally, for any BSC noise level, in quasi-polynomial or randomized polylogarithmic time in the depth, we construct deterministic bounded degree DAGs with layers of size Θ(log(k)) that admit reconstruction using lossless expander graphs.

This paper studies the basic question of whether a given channel V can be dominated (in the precise sense of being more noisy) by a q-ary symmetric channel. The concept of less noisy relation between channels originated in network information theory (broadcast channels) and is defined in terms of mutual information or Kullback-Leibler divergence. We provide an equivalent characterization in terms of χ2-divergence. Furthermore, we develop a simple criterion for domination by a q-ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel V. The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev inequality for the original channel.

We develop an information theoretic framework for addressing feature selection in applications where the inference task is not specified in advance and the data is from a large alphabet. We introduce a natural notion of universality for such problems, and show that locally optimal solutions are straight forward to obtain, admit natural interpretations via information geometry, have computationally efficient implementations, and represent a practically useful learning methodology. Our development also reveals the key role of Hirschfeld-Gebelein-Renyi maximal correlation and the alternating conditional expectations (ACE) algorithm in such problems.

Consider the family of all q-ary symmetric channels (q-SCs) with capacities decreasing from log(q) to 0. This paper addresses the following question: what is the member of this family with the smallest capacity that dominates a given channel V in the “less noisy” preorder sense. When the q-SCs are replaced by q-ary erasure channels, this question is known as the “strong data processing inequality.” We provide several equivalent characterizations of the less noisy preorder in terms of x2-divergence, Lowner (PSD) partial order, and spectral radius. We then illustrate a simple criterion for domination by a q-SC based on degradation, and mention special improvements for the case where V is an additive noise channel over an Abelian group of order q. Finally, as an application, we discuss how logarithmic Sobolev inequalities for q-SCs, which are well-studied, can be transported to an arbitrary channel V.

In this paper, we show that the conditional expectation operators corresponding to a family of source-channel models, defined by natural exponential families with quadratic variance functions and their conjugate priors, have orthonormal polynomials as singular vectors. These models include the Gaussian channel with Gaussian source, the Poisson channel with gamma source, and the binomial channel with beta source. To derive the singular vectors of these models, we prove and employ the equivalent condition that their conditional moments are strictly degree preserving polynomials.