Let$\boldsymbol{p}$denote a reference generative language model. Let$\boldsymbol{r}$denote a reward model that returns a scalar to capture the degree at which a draw from$\boldsymbol{p}$is preferred. The goal of language model alignment is to alter$\boldsymbol{p}$to a new distribution$\phi$that results in a higher expected reward while keeping$\phi$close to$\boldsymbol{p}$. A popular alignment method is the KL-constrained reinforcement learning$(\boldsymbol{RL})$, which chooses a distribution$\Phi_\Delta$that maximizes$E_{\phi_{\Delta}}\boldsymbol{r}(\boldsymbol{y})$subject to a relative entropy constraint$D_{\mathrm{K}\mathrm{L}}(\phi_{\Delta}\Vert \boldsymbol{p})\leq\Delta$. Another simple alignment method is best-of-N, where$N$samples are drawn from$\boldsymbol{p}$and one with highest reward is selected. In this paper, we offer a closed-form characterization of the optimal KL-constrained RL solution. We then demonstrate that any alignment method that achieves a comparable trade-off between KL divergence and expected reward must approximate the optimal KL-constrained RL solution in terms of relative entropy. To analyze the properties of alignment methods, we introduce two simplifying assumptions: we let the language model be memoryless, and the reward model be linear. Although these assumptions may not reflect complex real-world scenarios, they enable a precise characterization of the asymptotic (in the sequence length) behavior of the best-of-N and the KL-constrained RL methods, in terms of information-theoretic quantities.1

Correspondence analysis (CA) is a multivariate statistical tool used to visualize and interpret data dependencies by finding maximally correlated embeddings of pairs of random variables. CA has found applications in fields ranging from epidemiology to social sciences. However, current methods for CA do not scale to large, high-dimensional datasets. In this paper, we provide a novel interpretation of CA in terms of an information-theoretic quantity called the principal inertia components. We show that estimating the principal inertia components, which consists in solving a functional optimization problem over the space of finite variance functions of two random variable, is equivalent to performing CA. We then leverage this insight to design algorithms to perform CA at scale. Specifically, we demonstrate how the principal inertia components can be reliably approximated from data using deep neural networks. Finally, we show how the maximally correlated embeddings of pairs of random variables in CA further play a central role in several learning problems including multi-view and multi-modal learning methods and visualization of classification boundaries.

Analog signals processed in digital hardware are quantized into a discrete bit-constrained representation. Quantization is typically carried out using analog-to-digital converters (ADCs), operating in a serial scalar manner. In some applications, a set of analog signals are acquired individually and processed jointly. Such setups are referred to as distributed quantization. In this work we propose a distributed quantization scheme for representing a set of sparse time sequences acquired using conventional scalar ADCs. Our approach utilizes tools from secure group testing theory to exploit the sparse nature of the acquired analog signals, obtaining a compact and accurate representation while operating in a distributed fashion. We then show how our technique can be implemented when the quantized signals are transmitted over a multihop communication network providing a low-complexity network policy for routing and signal recovery. Our numerical evaluations demonstrate that the proposed scheme notably outperforms conventional methods based on the combination of quantization and compressed sensing tools.

In this paper we introduce Neural Network Coding (NNC), a data-driven approach to joint source and network coding. In NNC, the encoders at each source and intermediate node, as well as the decoder at each destination node, are neural networks which are all trained jointly for the task of communicating correlated sources through a network of noisy point-to-point links. The NNC scheme is application-specific and makes use of a training set of data, instead of making assumptions on the source statistics. In addition, it can adapt to any arbitrary network topology and power constraint. We show empirically that, for the task of transmitting MNIST images over a network, the NNC scheme shows improvement over baseline schemes, especially in the low-SNR regime.

We propose to exploit the structure of the correlation between two random variables X and Y via a relaxation on the Common Information problem of Gács and Körner (GK Common Information). Consider two correlated sources X and Y generated from a joint distribution PX,Y. We study embeddings of X into discrete random variables U, such that H(U|Y) ≤ δ, while maximizing I(X; U). When δ = 0, this reduces to the GK Common Information problem. However, unlike the GK Common Information, which is known to be zero for many pairs of random variables (X, Y), we show that this relaxation allows to capture the structure in the correlation between X and Y for a much broader range of joint distributions, and showcase applications for some problems in multi-terminal information theory.

We present a wideband time frequency coding scheme which combines the impulsive frequency shift keying scheme, shown to achieve the additive white Gaussian noise channel capacity in the wideband regime, with pulse position modulation. This coding scheme allows for information to be encoded in the position of the signal, which impulsive frequency shift keying does not take advantage of. We show that this scheme achieves rates which are comparable with the additive white Gaussian noise channel capacity upper bound, and performs well under a wide range of fading statistics and bandwidths. We show that our proposed scheme outperforms the impulsive frequency shift keying in lower bandwidths, even without optimization of the duty cycle. The scheme is also shown to perform similarly to impulsive frequency shift keying with smaller duty cycles in the wideband regime, indicating that continually decreasing duty cycles are not necessary to achieve rates on the order of additive white Gaussian noise channel capacity. We also discuss comparisons with other spread-spectrum signaling methods under noncoherent fading.

According to recent empirical studies, a majority of users have the same, or very similar, passwords across multiple password-secured online services. This practice can have disastrous consequences, as one password being compromised puts all the other accounts at much higher risk. Generally, an adversary may use any side-information he/she possesses about the user, be it demographic information, password reuse on a previously compromised account, or any other relevant information to devise a better brute-force strategy (so called targeted attack). In this work, we consider a distributed brute-force attack scenario in which m adversaries, each observing some side information, attempt breaching a password secured system. We compare two strategies: an uncoordinated attack in which the adversaries query the system based on their own side-information until they find the correct password, and a fully coordinated attack in which the adversaries pool their side-information and query the system together. For passwords X of length n, generated independently and identically from a distribution PX, we establish an asymptotic closed-form expression for the uncoordinated and coordinated strategies when the side-information Y(m) are generated independently from passing X through a memoryless channel PY|X, as the length of the password n goes to infinity. We illustrate our results for binary symmetric channels and binary erasure channels, two families of side-information channels which model password reuse. We demonstrate that two coordinated agents perform asymptotically better than any finite number of uncoordinated agents for these channels, meaning that sharing side-information is very valuable in distributed attacks.

Correspondence analysis (CA) is a multivariate statistical tool used to visualize and interpret data dependencies. CA has found applications in fields ranging from epidemiology to social sciences. However, current methods used to perform CA do not scale to large, high-dimensional datasets. By re-interpreting the objective in CA using an information-theoretic tool called the principal inertia components, we demonstrate that performing CA is equivalent to solving a functional optimization problem over the space of finite variance functions of two random variable. We show that this optimization problem, in turn, can be efficiently approximated by neural networks. The resulting formulation, called the correspondence analysis neural network (CA-NN), enables CA to be performed at an unprecedented scale. We validate the CA-NN on synthetic data, and demonstrate how it can be used to perform CA on a variety of datasets, including food recipes, wine compositions, and images. Our results outperform traditional methods used in CA, indicating that CA-NN can serve as a new, scalable tool for interpretability and visualization of complex dependencies between random variables.

Quantization allows physical signals to be processed using digital devices. Quantizers are commonly implemented using analog-to-digital converters (ADCs), which operate in a serial and scalar manner and are designed to yield an accurate digital representation of the observed signal. However, in many practical scenarios quantization is part of a system whose task is not to recover the observed signal, but some function of it. Recent works have shown that properly designed task-based quantizers, which include pre-quantization analog combining as well as digital processing, can achieve notable gains in recovering linear functions of the observations. In this work we focus on quantization for the task of recovering quadratic functions. Our analysis is based on principal inertia components (PICs), which form a basis for decomposing the statistical dependence between random quantities. Using PICs, we identify a practical structure of the pre-quantization mapping for recovering quadratic functions, which allows us to design a task-based quantization system capable of accurately estimating these functions. Our numerical study demonstrates that, when using scalar ADCs, notable performance gains that can be achieved using the proposed design over intuitive approaches such as quantizing the quadratic function directly as well as task-ignorant quantization.

Sampling enables physical signals to be processed using digital hardware. When multiple signals are sampled, the spatial correlation between them may be utilized to reduce the overall reconstruction error. In this work we study joint sampling and reconstruction of multiple correlated stochastic sources, exploiting their correlation to improve recovery. We derive the achievable reconstruction error and the corresponding sampling system for arbitrary sampling rates and spectral structures. The proposed system minimizes the error when sampling below the Nyquist rate by preserving only the most dominant spatial eigenmodes aliased to each frequency. Using this characterization, we obtain sufficient conditions for error free recovery. We also discuss a distributed sampling setting, where each signal is acquired separately, while reconstruction is performed jointly. We characterize conditions under which distributed sampling performs as well as joint sampling. Our numerical results illustrate that joint sampling can achieve negligible reconstruction error using low sampling rates when the signals exhibit notable spatial correlation, and demonstrate that properly exploiting this correlation can dramatically improve reconstruction accuracy.

In this work we investigate the capacity of multilayer relaying networks operating over multipath fading channels under a non-coherent wideband regime and physically degraded broadcast stages. First, based on hyper-graph models and network equivalence techniques, we derive an upper bound on the network capacity. Then, by considering a peaky, frequency-shift keying signaling scheme, we establish a set of point-to-point achievable rates for each communication link in the network. Finally, by capitalizing on this set of rates we devise an achievable transmission scheme for the entire network via network coding. Remarkably, it turns out that this achievable rate for the network coincides with its upper bound capacity. In other words, these results give ultimately the capacity of the investigated network.

We study the problem of mismatched guesswork, where we evaluate the number of symbols y ∈ Y which have higher likelihood than X ~ μ according to a mismatched distribution μ. We discuss the role of the tilted/exponential families of the source distribution μ and of the mismatched distribution ν. We show that the value of guesswork can be characterized using the tilted family of the mismatched distribution v, while the probability of guessing is characterized by an exponential family which passes through μ. Using this characterization, we demonstrate that the mismatched guesswork follows a large deviation principle (LDP), where the rate function is described implicitly using information theoretic quantities. We apply these results to one-to-one source coding (without prefix free constraint) to obtain the cost of mismatch in terms of average codeword length. We show that the cost of mismatch in one-to-one codes is no larger than that of the prefix-free codes, i.e., D(μ||ν). Further, the cost of mismatch vanishes if and only if ν lies on the tilted family of the true distribution μ, which is in stark contrast to the prefix-free codes. These results imply that one-to-one codes are inherently more robust to mismatch.

In September 2017, McAffee Labs quarterly report estimated that brute force attacks represent 20\% of total network attacks, making them the most prevalent type of attack ex-aequo with browser based vulnerabilities. These attacks have sometimes catastrophic consequences, and understanding their fundamental limits may play an important role in the risk assessment of password-secured systems, and in the design of better security protocols. While some solutions exist to prevent online brute-force attacks that arise from one single IP address, attacks performed by botnets are more challenging. In this paper, we analyze these distributed attacks by using a simplified model. Our aim is to understand the impact of distribution and asynchronization on the overall computational effort necessary to breach a system. Our result is based on Guesswork, a measure of the number of queries (guesses) required of an adversary before a correct sequence, such as a password, is found in an optimal attack. Guesswork is a direct surrogate for time and computational effort of guessing a sequence from a set of sequences with associated likelihoods. We model the lack of synchronization by a worst-case optimization in which the queries made by multiple adversarial agents are received in the worst possible order for the adversary, resulting in a min-max formulation. We show that, even without synchronization, and for sequences of growing length, the asymptotic optimal performance is achievable by using randomized guesses drawn from an appropriate distribution. Therefore, randomization is key for distributed asynchronous attacks. In other words, asynchronous guessers can asymptotically perform brute-force attacks as efficiently as synchronized guessers.

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given decoding rule. Specifically, it is assumed that the mismatched decoder has an incorrect assumption on the channel impulse response. The mismatch capacity is the highest achievable rate for a given decoding rule. The existing achievable rates for channels and decoding metrics with memory (as in our model) are currently available only in the form of multi-letter expressions that cannot be calculated. Consequently, they provide little insight on the mismatch problem. In this paper, we derive the computable formulas of achievable rates and discuss some implications of our results. Our achievable rates are based on two ensembles: the ensemble of codewords generated by an autoregressive process and the ensemble of codewords drawn uniformly over a “type class” of real-valued sequences. We provide a few numerical results of our achievable rates, as functions of the mismatched ISI parameters. Finally, we compare our results with universal decoders which are designed outside the true class of channels that we consider in this paper.

Given a pair of random variables (X, Y) ~ PXYand two convex functions f1and f2, we introduce two bottleneck functionals as the lower and upper boundaries of the two-dimensional convex set that consists of the pairs (If1(W;X), If2(W;Y)), where If denotes f-information and W varies over the set of all discrete random variables satisfying the Markov condition W → X → Y. Applying Witsenhausen and Wyner's approach, we provide an algorithm for computing boundaries of this set for f1, f2, and discrete PXY. In the binary symmetric case, we fully characterize the set when (i) f1(t)=f2(t)=tlogt, (ii) f1(t)=-f2(t)=t2- 1, and (iii) f1and f2are both lβnorm function for β ≥ 2. We then argue that upper and lower boundaries in (i) correspond to Mrs. Gerber's Lemma and its inverse (which we call Mr. Gerber's Lemma), in (ii) correspond to estimation-theoretic variants of Information Bottleneck and Privacy Funnel, and in (iii) correspond to Arimoto Information Bottleneck and Privacy Funnel.

Suppose that we wish to guess the realization x of a discrete random variable X taking values in a finite set, by asking sequential questions of the form “Is X is equal to x?” exhausting the elements of X until the answer is Yes. [1, 2]. If the distribution of X is known to the guesser, and the guesser has memory of his previous has memory of his previous queries then the best strategy is to guess in decreasing order of probabilities. In this paper, we consider the problem of a memoryless guesser, namely, each new guess is independent of the previous guesses. We consider also the scenario of a guesser with a bounded number of guesses. For both cases we derive the optimal guessing strategies, and show new connections to Rényi entropy.

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given (possibly suboptimal) metric decoding rule. Specifically, it is assumed that the mismatched decoder has incorrect knowledge of the ISI coefficients (or, the impulse response function). The mismatch capacity is the highest achievable rate for a given decoding rule. Unfortunately, existing lower bounds to the mismatch capacity for multi-letter channels and decoding metrics (or, channels and decoding metrics with memory), as in our model, are presented only in the form of multi-letter expressions, and thus cannot be calculated in practice. In this paper, we derive a computable single-letter lower bound to the mismatch capacity, and discuss some implications of our results.

We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork.

We introduce a property that we call Successive Description property for Slepian Wolf coding. We show that Monotone-Chain Polar Codes can be used to construct low-complexity codes that satisfy this property. We discuss applications of this property to network coding problems.

We focus on the privacy-utility trade-off encountered by users who wish to disclose some information to an analyst, that is correlated with their private data, in the hope of receiving some utility. We rely on a general privacy statistical inference framework, under which data is transformed before it is disclosed, according to a probabilistic privacy mapping. We show that when the log-loss is introduced in this framework in both the privacy metric and the distortion metric, the privacy leakage and the utility constraint can be reduced to the mutual information between private data and disclosed data, and between non-private data and disclosed data respectively. We justify the relevance and generality of the privacy metric under the log-loss by proving that the inference threat under any bounded cost function can be upperbounded by an explicit function of the mutual information between private data and disclosed data. We then show that the privacy-utility tradeoff under the log-loss can be cast as the non-convex Privacy Funnel optimization, and we leverage its connection to the Information Bottleneck, to provide a greedy algorithm that is locally optimal. We evaluate its performance on the US census dataset. Finally, we characterize the optimal privacy mapping for the Gaussian Privacy Funnel.