We consider the problem of offline reinforcement learning from human feedback (RLHF) with pairwise comparisons, where the implicit reward is a linear function of an unknown parameter. Given an offline dataset, our objective is to identify the optimal action for each state, with the ultimate goal of minimizing the simple regret. We propose an algorithm, Reinforcement Learning with Locally Optimal Weights (RL-LOW), which achieves an exponential rate of simple regret that decays exponentially with the ratio of the number of data samples to an instance-dependent hardness parameter. This hardness parameter depends explicitly on the suboptimality gap of each action. Furthermore, we derive the first instance-dependent lower bound for offline RLHF with pairwise comparisons. Interestingly, the lower and upper bounds on the simple regret match in an order-wise sense in the exponent, demonstrating the order-wise optimality of RL-LOW. Motivated by privacy considerations in practical applications, we further extend RL-LOW to the setting of differential privacy and show, somewhat surprisingly, that the hardness parameter remains unchanged in the asymptotic regime as the number of data samples tends to infinity. This result highlights the inherent efficiency of RL-LOW in preserving the privacy of the observed rewards. By establishing instance-dependent bounds with exponential convergence rates, our work fills an important gap in the existing literature, which has primarily focused on worst-case regret bounds with inverse polynomial convergence rates for offline RLHF with pairwise comparisons.

The Combinatorial Multi-Armed Bandit (CMAB) framework extends classical multi-armed bandit theory to complex decision-making settings where agents select super arms to maximize a collective reward. While Thompson Sampling (TS) is widely favored for its robust empirical performance in these settings, its theoretical guarantees have historically suffered from a significant bottleneck: standard Combinatorial Thompson Sampling (\texttt{CTS}) incurs a regret bound with an exponential dependence on the size $k^*$ of the optimal super-arm. This exponential term arises because standard independent posterior sampling fails to coordinate optimism across the base arms of the optimal super arm, causing the probability of exploration to vanish as $k^*$ increases. Although recent advances have achieved polynomial regret for \emph{linear} rewards, designing an efficient TS algorithm for general, non-linear CMABs remains an open challenge. In this paper, we resolve this open question by proposing \emph{Combinatorial Thompson Sampling with a Single Seed} (\texttt{CTS$^3$}). Unlike standard approaches that sample base arms independently, \texttt{CTS$^3$} employs a comonotonic coupling strategy: it generates parameters for all base arms using a single shared random seed via the inverse CDF transform. This mechanism synchronizes sampling fluctuations across arms, ensuring concerted optimism and preventing the exploration probability from decaying exponentially. We prove that \texttt{CTS$^3$} achieves a regret bound of ${O}\left( \frac{m kk^*B^2}{\Delta_{\min}}\poly(\log(T,m,\Delta_{\max}/\Delta_{\min}))\right)$ for general reward functions satisfying monotonicity and bounded smoothness, where $m$ is the number of total base arms, $k$ is the largest super arm size, and $k^*$ is size of the optimal arm. To the best of our knowledge, this is the first polynomial regret bound for Thompson Sampling in general CMAB settings. Empirical evaluations confirm that \texttt{CTS$^3$} significantly outperforms standard independent TS, particularly in regimes with large super arms.

We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses. At each time step, an agent is allowed to query pairs of items and observe bandit binary feedback. If the pair of items belongs to the same (resp.\ different) cluster, the observed feedback is $1$ with probability $p>1/2$ (resp.\ $q<1/2$). Leveraging the ubiquitous change-of-measure technique, we establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the clustering accuracy, formulated as a sup-inf optimization problem. Building on this theoretical foundation, we design an asymptotically optimal algorithm in which the stopping criterion involves an empirical version of the inner infimum -- the Generalized Likelihood Ratio (GLR) statistic -- being compared to a threshold. We develop a computationally feasible variant of the GLR statistic and show that its performance gap to the lower bound can be accurately empirically estimated and remains within a constant multiple of the lower bound.

Electromagnetic information theory (EIT) is an interdisciplinary subject that serves to integrate deterministic electromagnetic theory with stochastic Shannon's information theory. Existing EIT analysis operates in the continuous space domain, which is not aligned with the practical algorithms working in the discrete space domain. This mismatch leads to a significant difficulty in application of EIT methodologies to practical discrete space systems, which is called as thediscrete-continuous gapin this paper. To bridge this gap, we establish the discrete-continuous correspondence with a prolate spheroidal wave function (PSWF)-based ergodic capacity analysis framework. Specifically, we state and prove some discrete-continuous correspondence lemmas to establish a firm theoretical connection between discrete information-theoretic quantities to their continuous counterparts. With these lemmas, we apply the PSWF ergodic capacity bound to advanced MIMO architectures such as continuous-aperture MIMO (CAP-MIMO) and extremely large-scale MIMO (XL-MIMO). From this PSWF capacity bound, we discover the capacity saturation phenomenon both theoretically and empirically. Although the growth of MIMO performance is fundamentally limited in this EIT-based analysis framework, we reveal new opportunities in MIMO channel estimation by exploiting the EIT knowledge about the channel. Inspired by the PSWF capacity bound, we utilize continuous PSWFs to improve the pilot design of discrete MIMO channel estimators, which is called as the PSWF channel estimator (PSWF-CE). Simulation results demonstrate improved performance of the proposed PSWF-CE, compared to traditional minimum mean squared error (MMSE) and compressed sensing-based estimators.

In this work, we extend the concept of the p-mean welfare objective from social choice theory to study p-mean regret in stochastic multi-armed bandit problems. The p-mean regret, defined as the difference between the optimal mean among the arms and the p-mean of the expected rewards, offers a flexible framework for evaluating bandit algorithms, enabling algorithm designers to balance fairness and efficiency by adjusting the parameter p. Our framework encompasses both average cumulative regret and Nash regret as special cases. We introduce a simple, unified UCB-based algorithm (Explore-Then-UCB) that achieves novel p-mean regret bounds. Our algorithm consists of two phases: a carefully calibrated uniform exploration phase to initialize sample means, followed by the UCB1 algorithm of Auer et al. (2002). Under mild assumptions, we prove that our algorithm achieves a p-mean regret bound of Otilde( sqrt( k / T^{1/(2|p|)} ) ) for all p

We consider a multi-armed bandit setting with finitely many arms, in which each arm yields an $M$-dimensional vector reward upon selection. We assume that the reward of each dimension (a.k.a. {\em objective}) is generated independently of the others. The best arm of any given objective is the arm with the largest component of mean corresponding to the objective. The end goal is to identify the best arm of {\em every} objective in the shortest (expected) time subject to an upper bound on the probability of error (i.e., fixed-confidence regime). We establish a problem-dependent lower bound on the limiting growth rate of the expected stopping time, in the limit of vanishing error probabilities. This lower bound, we show, is characterised by a max-min optimisation problem that is computationally expensive to solve at each time step. We propose an algorithm that uses the novel idea of {\em surrogate proportions} to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step. We demonstrate theoretically that our algorithm is asymptotically optimal. In addition, we provide extensive empirical studies to substantiate the efficiency of our algorithm. While existing works on pure exploration with multi-objective multi-armed bandits predominantly focus on {\em Pareto front identification}, our work fills the gap in the literature by conducting a formal investigation of the multi-objective best arm identification problem.

Semi-supervised learning (SSL), exemplified by FixMatch (Sohn et al., 2020), has shown significant generalization advantages over supervised learning (SL), particularly in the context of deep neural networks (DNNs). However, it is still unclear, from a theoretical standpoint, why FixMatch-like SSL algorithms generalize better than SL on DNNs. In this work, we present the first theoretical justification for the enhanced test accuracy observed in FixMatch-like SSL applied to DNNs by taking convolutional neural networks (CNNs) on classification tasks as an example. Our theoretical analysis reveals that the semantic feature learning processes in FixMatch and SL are rather different. In particular, FixMatch learns all the discriminative features of each semantic class, while SL only randomly captures a subset of features due to the well-known lottery ticket hypothesis. Furthermore, we show that our analysis framework can be applied to other FixMatch-like SSL methods, e.g., FlexMatch, FreeMatch, Dash, and SoftMatch. Inspired by our theoretical analysis, we develop an improved variant of FixMatch, termed Semantic-Aware FixMatch (SA-FixMatch). Experimental results corroborate our theoretical findings and the enhanced generalization capability of SA-FixMatch.

Speculative decoding has emerged as a popular method to accelerate the inference of Large Language Models (LLMs) while retaining their superior text generation performance. Previous methods either adopt a fixed speculative decoding configuration regardless of the prefix tokens, or train draft models in an offline or online manner to align them with the context. This paper proposes a training-free online learning framework to adaptively choose the configuration of the hyperparameters for speculative decoding as text is being generated. We first formulate this hyperparameter selection problem as a Multi-Armed Bandit problem and provide a general speculative decoding framework BanditSpec. Furthermore, two bandit-based hyperparameter selection algorithms, UCBSpec and EXP3Spec, are designed and analyzed in terms of a novel quantity, the stopping time regret. We upper bound this regret under both stochastic and adversarial reward settings. By deriving an information-theoretic impossibility result, it is shown that the regret performance of UCBSpec is optimal up to universal constants. Finally, extensive empirical experiments with LLaMA3 and Qwen2 demonstrate that our algorithms are effective compared to existing methods, and the throughput is close to the oracle best hyperparameter in simulated real-life LLM serving scenarios with diverse input prompts.

Off-policy learning and evaluation leverage logged bandit feedback datasets, which contain context, action, propensity score, and feedback for each data point. These scenarios face significant challenges due to high variance and poor performance with low-quality propensity scores and heavy-tailed reward distributions. We address these issues by introducing a novel estimator based on the log-sum-exponential (LSE) operator, which outperforms traditional inverse propensity score estimators. Our LSE estimator demonstrates variance reduction and robustness under heavy-tailed conditions. For off-policy evaluation, we derive upper bounds on the estimator's bias and variance. In the off-policy learning scenario, we establish bounds on the regret—the performance gap between our LSE estimator and the optimal policy—assuming bounded $(1+\epsilon)$-th moment of weighted reward. Notably, we achieve a convergence rate of $O(n^{-\epsilon/(1+\epsilon)})$ for the regret bounds, where $\epsilon\in[0,1]$ and $n$ is the size of logged bandit feedback dataset. Theoretical analysis is complemented by comprehensive empirical evaluations in both off-policy learning and evaluation scenarios, confirming the practical advantages of our approach. The code for our estimator is available at the following link: https://github.com/armin-behnamnia/lse-offpolicy-learning .

Accuracy and speed are critical in image editing tasks. Pan et al. introduced a drag-based framework using Generative Adversarial Networks, and subsequent studies have leveraged large-scale diffusion models. However, these methods often require over a minute per edit and exhibit low success rates. We present LightningDrag, which achieves high-quality drag-based editing in about one second on general images. By redefining drag-based editing as a conditional generation task, we eliminate the need for time-consuming latent optimization or gradient-based guidance. Our model is trained on large-scale paired video frames, capturing diverse motion (object translations, pose shifts, zooming, etc.) to significantly improve accuracy and consistency. Despite being trained only on videos, our model generalizes to local deformations beyond the training data (e.g., lengthening hair, twisting rainbows). Extensive evaluations confirm the superiority of our approach, and we will release both code and model.

This paper considers guessing-based decoders with abandonment for discrete memoryless channels in which all codewords have the same composition. This class of decoders rank-orders all input sequences in the type class from “closest” to “farthest” from the channel output and then queries them sequentially in that order for codeword membership. Decoding stops when a codeword is encountered or when a predetermined number of guesses is reached and decoding is abandoned. Ensemble-tight first- and second-order asymptotics are derived for the code rate and abandonment rate. The optimal secondorder region is characterized in terms of the minimum of the second-order code and abandonment rates.

We develop the first parameter-free algorithms for the Stochastically Extended Adversarial (SEA) model, a framework that bridges adversarial and stochastic online convex optimization. Existing approaches for the SEA model require prior knowledge of problem-specific parameters, such as the diameter of the domain $D$ and the Lipschitz constant of the loss functions $G$, which limits their practical applicability. Addressing this, we develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters. We first establish a comparator-adaptive algorithm for the scenario with unknown domain diameter but known Lipschitz constant, achieving an expected regret bound of $\tilde{O}\big(\Vert u\Vert_2^2 + \Vert u\Vert_2(\sqrt{\sigma^2_{1:T}} + \sqrt{\Sigma^2_{1:T}})\big)$, where $u$ is the comparator vector and $\sigma^2_{1:T}$ and $\Sigma^2_{1:T}$ represent the cumulative stochastic variance and cumulative adversarial variation, respectively. We then extend this to the more general setting where both $D$ and $G$ are unknown, attaining the comparator- and Lipschitz-adaptive algorithm. Notably, the regret bound exhibits the same dependence on $\sigma^2_{1:T}$ and $\Sigma^2_{1:T}$, demonstrating the efficacy of our proposed methods even when both parameters are unknown in the SEA model.

The challenge of identifying the optimal feasible arm within a fixed budget has attracted considerable interest in recent years. However, a notable gap remains in the literature: the exact exponential rate at which the error probability approaches zero has yet to be established, even in the relatively simple setting of $K$-armed bandits with Gaussian noise. In this paper, we address this gap by examining the problem within the context of linear bandits. We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability. Remarkably, the decay rate-characterized by the exponent-matches the theoretical lower bound derived using information-theoretic principles. Our approach leverages a posterior sampling framework embedded within a game-based sampling rule involving a min-learner and a max-learner. This strategy shares its foundations with Thompson sampling, but is specifically tailored to optimize the identification process under fixed-budget constraints. Furthermore, we validate the effectiveness of our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity. The results corroborate our theoretical findings and demonstrate that our method outperforms several benchmark algorithms in terms of both accuracy and efficiency.

We study the best arm identification (BAI) problem with potentially biased offline data in the fixed confidence setting, which commonly arises in real-world scenarios such as clinical trials. We prove an impossibility result for adaptive algorithms without prior knowledge of the bias bound between online and offline distributions. To address this, we propose the LUCB-H algorithm, which introduces adaptive confidence bounds by incorporating an auxiliary bias correction to balance offline and online data within the LUCB framework. Theoretical analysis shows that LUCB-H matches the sample complexity of standard LUCB when offline data is misleading and significantly outperforms it when offline data is helpful. We also derive an instance-dependent lower bound that matches the upper bound of LUCB-H in certain scenarios. Numerical experiments further demonstrate the robustness and adaptability of LUCB-H in effectively incorporating offline data.

Codes in the Damerau-Levenshtein metric have received some attention by the research community recently owing to their applications in DNA-based data storage. In particular, Gabrys, Yaakobi, and Milenkovic designed a length-n code correcting a single deletion and s adjacent transpositions with at most$(1+2s)\log n$bits of redundancy. In this work, we consider a new setting where both deletions and asymmetric adjacent transpositions may occur. For asymmetric transpositions, at most$s^{+}0$-right shifts (i.e.,$01 \rightarrow 10$) and at most$s^ - 0$-left shifts (i.e.,$10 \rightarrow 01$) may occur. We present several constructions of the binary codes correcting these errors in various cases. In particular, we design a code correcting a single deletion,$s^{+}$right-shift, and$s^ - $left-shift errors with at most$(1+s)\log (n+s+1)+1$bits of redundancy where$s=s^{+}+s^ - $. In addition, we investigate uniquely-decodable codes correcting$t~0$-deletions and s adjacent transpositions with at most$(t+2s)\log n+o(\log n)$bits of redundancy. Then, we study the code for correcting$t~0$-deletions,$s^{+}$right-shift, and$s^ - $left-shift errors with list-decoding algorithms. Our main contribution here is the construction of a list-decodable code with list size$O(n^{s})$and with at most$(\max \{t,s+1\}) \log n+O(1)$bits of redundancy, where$s=s^{+}+s^ - $. We construct non-systematic codes for correcting$t_{\mathrm {b}}$blocks of 0-deletions with$\ell $-limited magnitude and s adjacent transpositions with redundancy at most$(2(t_{\mathrm {b}}+2s)+1)\log (n+1)+O(1)$bits and systematic codes with at most$((2(t_{\mathrm {b}}+2s)+1)(1+1/(\log (t_{\mathrm {b}}\ell +4)))\log (N+1)+O(\log \log N)$redundant bits in an N-length codeword.

Kolmogorov–Arnold Networks (KANs), a recently proposed neural network architecture, have gained significant attention in the deep learning community, due to their potential as a viable alternative to multi-layer perceptrons (MLPs) and their broad applicability to various scientific tasks. Empirical investigations demonstrate that KANs optimized via stochastic gradient descent (SGD) are capable of achieving near-zero training loss in various machine learning (e.g., regression, classification, and time series forecasting, etc.) and scientific tasks (e.g., solving partial differential equations). In this paper, we provide a theoretical explanation for the empirical success by conducting a rigorous convergence analysis of gradient descent (GD) and SGD for two-layer KANs in solving both regression and physics-informed tasks. For regression problems, we establish using the neural tangent kernel perspective that GD achieves global linear convergence of the objective function when the hidden dimension of KANs is sufficiently large. We further extend these results to SGD, demonstrating a similar global convergence in expectation. Additionally, we analyze the global convergence of GD and SGD for physics-informed KANs, which unveils additional challenges due to the more complex loss structure. This is the first work establishing the global convergence guarantees for GD and SGD applied to optimize KANs and physics-informed KANs.

This paper considers guessing-based decoders with abandonment for discrete memoryless channels in which all codewords have the same composition. This class of decoders rank-orders all input sequences in the codebook’s composition class from “closest” to “farthest” from the channel output and then queries them sequentially in that order for codebook membership. Decoding terminates when a codeword is encountered or when a predetermined number of guesses is reached, and decoding is abandoned. We derive ensemble-tight first-order asymptotics for the code rate and abandonment rate, which shows that guessing-based decoding is more efficient than conventional testing-based decoding whenever the capacity of the channel exceeds half the entropy of the capacity-achieving input distribution. The main focus of this paper is on refined asymptotics, specifically, second-order asymptotics, error exponents, and strong converse exponents. The optimal second-order region is characterized in terms of the minimum of the second-order code and abandonment rates. The error (resp. strong converse) exponent is characterized in terms of the minimum (resp. maximum) of the usual channel coding exponent and an abandonment exponent, which turns out to be a special case of the exponent of conditional almost-lossless source coding.

We develop a general framework for clustering and distribution matching problems with bandit feedback. We consider a K-armed bandit model where some subset of K arms is partitioned into M groups. Within each group, the random variable associated to each arm follows the same distribution on a finite alphabet. At each time step, the decision maker pulls an arm and observes its outcome from the random variable associated to that arm. Subsequent arm pulls depend on the history of arm pulls and their outcomes. The decision maker has no knowledge of the distributions of the arms or the underlying partitions. The task is to devise an online algorithm to learn the underlying partition of arms with the least number of arm pulls on average and with an error probability not exceeding a pre-determined value$\delta $. Several existing problems fall under our general framework, including finding M pairs of arms, odd arm identification, and N-ary clustering of K arms belong to our general framework. We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding$\delta $. Furthermore, we develop a computationally-efficient online algorithm based on the Track-and-Stop method and Frank-Wolfe algorithm, and show that the average number of arm pulls of our algorithm asymptotically matches that of the lower bound. Our refined analysis also uncovers a novel bound on the speed at which the average number of arm pulls of our algorithm converges to the fundamental limit as$\delta $vanishes.

We study variable-length feedback (VLF) codes with noiseless feedback for discrete memoryless channels. We present a novel non-asymptotic bound, which analyzes the average error probability and average decoding time of our modified Yamamoto-Itoh scheme. We then optimize the parameters of our code in the asymptotic regime where the average error probability$\epsilon $remains a constant as the average decoding timeNapproaches infinity. Our second-order achievability bound is an improvement of Polyanskiy et al.’s (2011) achievability bound. We also develop a universal VLF code that does not rely on the knowledge of the underlying channel parameters. Our universal VLF code employs the empirical mutual information as its decoding metric and universalizes the code by Polyanskiy et al. (2011). We derive a second-order achievability bound for universal VLF codes. Our results for both VLF and universal VLF codes are extended to the additive white Gaussian noise channel with an average power constraint. The former yields an improvement over Truong and Tan’s (2017) achievability bound. The proof of our results for universal VLF codes uses a refined version of the method of types and an asymptotic expansion from the nonlinear renewal theory literature.

Accurate and controllable image editing is a challenging task that has attracted significant attention recently. Notably, DRAGGAN developed by Pan et al. (2023) [33] is an interactive point-based image editing framework that achieves impressive editing results with pixel-level precision. However, due to its reliance on generative adversarial networks (GANs), its generality is limited by the capacity of pretrained GAN models. In this work, we extend this editing framework to diffusion models and propose a novel approach Dragdiffusion. By harnessing large-scale pretrained diffusion models, we greatly enhance the applicability of interactive point-based editing on both real and diffusion-generated images. Unlike other diffusion-based editing methods that provide guidance on diffusion latents of multiple time steps, our approach achieves efficient yet accurate spatial control by optimizing the latent of only one time step. This novel design is motivated by our observations that UNet features at a specific time step provides sufficient semantic and geometric information to support the drag-based editing. Moreover, we introduce two additional techniques, namely identity-preserving fine-tuning and reference-latent-control, to further preserve the identity of the original image. Lastly, we present a challenging benchmark dataset called DRAGBENCH─ the first benchmark to evaluate the performance of interactive point-based image editing methods. Experiments across a wide range of challenging cases (e.g., images with multiple objects, diverse object categories, various styles, etc.) demonstrate the versatility and generality of Dragdiffusion. Code and the Dragbench dataset: https://github.com/Yujun-Shi/DragDiffusion.

We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints, when the arm rewards are supported on the unit interval. Given a finite budget $T$ and a privacy parameter $\varepsilon>0$, the goal is to minimise the error probability in finding the arm with the largest mean after $T$ sampling rounds, subject to the constraint that the policy of the decision maker satisfies a certain {\em $\varepsilon$-differential privacy} ($\varepsilon$-DP) constraint. We construct a policy satisfying the $\varepsilon$-DP constraint (called {\sc DP-BAI}), based on the principle of {\em maximum absolute determinants}, and derive an upper bound on its error probability. Furthermore, we derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$, with exponents in the two bounds matching order-wise in (a) the sub-optimality gaps of the arms, (b) $\varepsilon$, and (c) the problem complexity that is expressible as the sum of two terms, one characterising the complexity of standard fixed-budget BAI (without privacy constraints), and the other accounting for the $\varepsilon$-DP constraint. Additionally, we present some auxiliary results that contribute to the derivation of the lower bound on the error probability. These results, we posit, may be of independent interest and could prove instrumental in proving lower bounds on error probabilities in several other bandit problems. Whereas prior works provide results for BAI in the fixed-budget regime without privacy constraints or in the fixed-confidence regime with privacy constraints, our work fills the gap in the literature by providing the results for BAI in the fixed-budget regime under the $\varepsilon$-DP constraint.

This paper considers a ubiquitous problem underlying several applications of DPMs, i.e., optimizing the parameters of DPMs when the objective is a differentiable metric defined on the generated contents. Since the sampling procedure of DPMs involves recursive calls to the denoising UNet, naive gradient backpropagation requires storing the intermediate states of all iterations, resulting in extremely high memory consumption. To overcome this issue, we propose a novel method AdjointDPM, which first generates new samples from diffusion models by solving the corresponding probability-flow ODEs. It then uses the adjoint sensitivity method to backpropagate the gradients of the loss to the models' parameters (including conditioning signals, network weights, and initial noises) by solving another augmented ODE. To reduce numerical errors in both the forward generation and gradient backpropagation processes, we further reparameterize the probability-flow ODE and augmented ODE as simple non-stiff ODEs using exponential integration. AdjointDPM can effectively compute the gradients of all types of parameters in DPMs, including the network weights, conditioning text prompts, and noisy states. Finally, we demonstrate the effectiveness of AdjointDPM on several interesting tasks: guided generation via modifying sampling trajectories, finetuning DPM weights for stylization, and converting visual effects into text embeddings.

We consider a private discrete distribution estimation problem with one-bit communication constraint. The privacy constraints are imposed with respect to the local differential privacy. The estimation error is quantified by the worst-case mean squared error. We completely characterize the first-order asymptotics of this privacy-utility trade-off under the one-bit communication constraint by using ideas from local asymptotic normality and the resolution of a block design mechanism. This results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint in terms of the privacy constraint and the size of the alphabet of the discrete distribution.

In this paper, we address the problem of best arm identification (BAI) with arm erasures in a multi-armed bandit setting with finitely many arms. A learner who seeks to identify the best arm-the arm with the largest mean reward-samples arms sequentially, one at each time instant, and communicates the sampled arm to an agent through an erasure channel with a known erasure probability$\epsilon\in(0,1)$• The learner does not receive any erasure feedback, and hence does not know whether the transmitted arm was erased by the channel. In instances where erasure does not occur, and the transmitted arm is successfully received by the agent, the agent promptly pulls the received arm. On the contrary, when erasure occurs, we analyse the following two distinct scenarios: (a) the agent randomly selects an arm, and (b) the agent selects the most recent successfully received arm. We assume that the instantaneous reward from the pulled arm is available to the learner, whose objective is to find the best arm as quickly as possible, subject to an upper bound on the error probability. Given$\delta\in(0,1)$, we derive a problem-dependent lower bound on the expected stopping time of any algorithm whose error probability is within$\delta$. We also propose two successive elimination algorithms for each of the aforementioned scenarios (a), (b), and provide upper bounds on their stopping times that hold with probability$1-\delta$• To our best knowledge, this is the first work on BAI with arm erasures.

Distributed gradient descent has attracted attention in modern machine learning, especially for handling large datasets. Less focus has been given to the distributed gradient descent where the partial gradient in each worker is subject to adversarial corruption instead of random noise. In this paper, we explore the challenges of this adversarial setting and propose a distributed gradient descent algorithm, focusing on the robustness against adversarial corruption and noises during model transmission. Furthermore, we derive bounds on the error rates for both non-strongly convex and strongly convex loss functions.

We study variable-length feedback (VLF) codes with noiseless feedback for discrete memoryless channels. We present a novel non-asymptotic bound, which analyzes the average error probability and average decoding time of our modified Yamamoto-Itoh scheme. We then optimize the parameters of our code in the asymptotic regime where the average error probability$\epsilon$remains a constant as the average decoding time$N$approaches infinity. Our second-order achievability bound refines Polyanskiy et al.'s (2011) achievability bound. We also universal-ize our code by employing the empirical mutual information in our decoding metric and derive a second-order achievability bound for universal VLF codes. The proof of our result for universal VLF codes uses a refined version of the method of types and an asymptotic expansion from the nonlinear renewal theory literature.

We consider a ubiquitous scenario in the study of Influence Maximization (IM), in which there is limited knowledge about the topology of the diffusion network. We set the IM problem in a multi-round diffusion campaign, aiming to maximize the number of distinct users that are influenced. Leveraging the capability of bandit algorithms to effectively balance the objectives of exploration and exploitation, as well as the expressivity of neural networks, our study explores the application of neural bandit algorithms to the IM problem. We propose the framework IM-GNB (Influence Maximization with Graph Neural Bandits), where we provide an estimate of the users' probabilities of being influenced by influencers (also known as diffusion seeds). This initial estimate forms the basis for constructing both an exploitation graph and an exploration one. Subsequently, IM-GNB handles the exploration-exploitation tradeoff, by selecting seed nodes in real-time using Graph Convolutional Networks (GCN), in which the pre-estimated graphs are employed to refine the influencers' estimated rewards in each contextual setting. Through extensive experiments on two large real-world datasets, we demonstrate the effectiveness of IM-GNB compared with other baseline methods, significantly improving the spread outcome of such diffusion campaigns, when the underlying network is unknown.

We propose a novel piecewise stationary linear bandit (PSLB) model, where the environment randomly samples a context from an unknown probability distribution at each changepoint, and the quality of an arm is measured by its return averaged over all contexts. The contexts and their distribution, as well as the changepoints are unknown to the agent. We design Piecewise-Stationary $\varepsilon$-Best Arm Identification$^+$ (PS$\varepsilon$BAI$^+$), an algorithm that is guaranteed to identify an $\varepsilon$-optimal arm with probability $\ge 1-\delta$ and with a minimal number of samples. PS$\varepsilon$BAI$^+$ consists of two subroutines, PS$\varepsilon$BAI and Naïve $\varepsilon$-BAI (N$\varepsilon$BAI), which are executed in parallel. PS$\varepsilon$BAI actively detects changepoints and aligns contexts to facilitate the arm identification process. When PS$\varepsilon$BAI and N$\varepsilon$BAI are utilized judiciously in parallel, PS$\varepsilon$BAI$^+$ is shown to have a finite expected sample complexity. By proving a lower bound, we show the expected sample complexity of PS$\varepsilon$BAI$^+$ is optimal up to a logarithmic factor. We compare PS$\varepsilon$BAI$^+$ to baseline algorithms using numerical experiments which demonstrate its efficiency. Both our analytical and numerical results corroborate that the efficacy of PS$\varepsilon$BAI$^+$ is due to the delicate change detection and context alignment procedures embedded in PS$\varepsilon$BAI.

This paper considers the problem of online clustering with bandit feedback. A set of arms (or items) can be partitioned into various groups that are unknown. Within each group, the observations associated to each of the arms follow the same distribution with the same mean vector. At each time step, the agent queries or pulls an arm and obtains an independent observation from the distribution it is associated to. Subsequent pulls depend on previous ones as well as the previously obtained samples. The agent's task is to uncover the underlying partition of the arms with the least number of arm pulls and with a probability of error not exceeding a prescribed constant $\delta$. The problem proposed finds numerous applications from clustering of variants of viruses to online market segmentation. We present an instance-dependent information-theoretic lower bound on the expected sample complexity for this task, and design a computationally efficient and asymptotically optimal algorithm, namely Bandit Online Clustering (BOC). The algorithm includes a novel stopping rule for adaptive sequential testing that circumvents the need to exactly solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower bound asymptotically, and significantly outperforms a non-adaptive baseline algorithm.

We design and analyze reinforcement learning algorithms for Graphon Mean-Field Games (GMFGs). In contrast to previous works that require the precise values of the graphons, we aim to learn the Nash Equilibrium (NE) of the regularized GMFGs when the graphons are unknown. Our contributions are threefold. First, we propose the Proximal Policy Optimization for GMFG (GMFG-PPO) algorithm and show that it converges at a rate of $\tilde{O}(T^{-1/3})$ after $T$ iterations with an estimation oracle, improving on a previous work by Xie et al. (ICML, 2021). Second, using kernel embedding of distributions, we design efficient algorithms to estimate the transition kernels, reward functions, and graphons from sampled agents. Convergence rates are then derived when the positions of the agents are either known or unknown. Results for the combination of the optimization algorithm GMFG-PPO and the estimation algorithm are then provided. These algorithms are the first specifically designed for learning graphons from sampled agents. Finally, the efficacy of the proposed algorithms are corroborated through simulations. These simulations demonstrate that learning the unknown graphons reduces the exploitability effectively.

Federated learning aims to train models collaboratively across different clients without sharing data for privacy considerations. However, one major challenge for this learning paradigm is thedata heterogeneityproblem, which refers to the discrepancies between the local data distributions among various clients. To tackle this problem, we first study how data heterogeneity affects the representations of the globally aggregated models. Interestingly, we find that heterogeneous data results in the global model suffering from severedimensional collapse, in which representations tend to reside in a lower-dimensional space instead of the ambient space. This dimensional collapse phenomenon severely curtails the expressive power of models, leading to significant degradation in the performance. Next, via experiments, we make more observations and posit two reasons that result in this phenomenon: 1) dimensional collapse on local models; 2) the operation of global averaging on local model parameters. In addition, we theoretically analyze the gradient flow dynamics to shed light on how data heterogeneity result in dimensional collapse. To remedy this problem caused by the data heterogeneity, we proposeFedDecorr, a novel method that can effectively mitigate dimensional collapse in federated learning. Specifically,FedDecorrapplies a regularization term during local training that encourages different dimensions of representations to be uncorrelated.FedDecorr, which is implementation-friendly and computationally-efficient, yields consistent improvements over various baselines on five standard benchmark datasets including CIFAR10, CIFAR100, TinyImageNet, Office-Caltech10, and DomainNet.

We consider a private discrete distribution estimation problem with one-bit communication constraint. The privacy constraints are imposed with respect to the local differential privacy and the maximal leakage. The estimation error is quantified by the worst-case mean squared error. We completely characterize the first-order asymptotics of this privacy-utility trade-off under the one-bit communication constraint for both types of privacy constraints by using ideas from local asymptotic normality and the resolution of a block design mechanism. These results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint in terms of the parameters of the privacy constraint and the size of the alphabet of the discrete distribution.

We study best arm identification in a federated multi-armed bandit setting with a central server and multiple clients, when each client has access to asubsetof arms and each arm yields independent Gaussian observations. The goal is to identify the best arm of each client subject to an upper bound on the error probability; here, the best arm is one that has the largestaveragevalue of the means averaged across all clients having access to the arm. Our interest is in the asymptotics as the error probability vanishes. We provide an asymptotic lower bound on the growth rate of the expected stopping time of any algorithm. Furthermore, we show that for any algorithm whose upper bound on the expected stopping time matches with the lower bound up to a multiplicative constant (almost-optimalalgorithm), the ratio of any two consecutive communication time instants must beboundeda result that is of independent interest. We thereby infer that an algorithm can communicate no more sparsely than at exponential time instants in order to be almost-optimal. For the class of almost-optimal algorithms, we present the first-of-its-kind asymptotic lower bound on the expected number ofcommunication roundsuntil stoppage. We propose a novel algorithm that communicates at exponential time instants, and demonstrate that it is asymptotically almost-optimal.

We study the problem of adversarial combinatorial bandit with a switching cost λ for a switch of each selected arm in each round, considering both the bandit feedback and semi-bandit feedback settings. In the oblivious adversarial case withKbase arms and time horizonT, we derive lower bounds for the minimax regret and design algorithms to approach them. To prove these lower bounds, we design stochastic loss sequences for both feedback settings, building on an idea from previous work in Dekel et al. (2014). The lower bound for bandit feedback is Ω((λK)1/3(TI)2/3) while that for semi-bandit feedback is Ω ( (λKI)1/3T2/3whereIis the number of base arms in the combinatorial arm played in each round. To approach these lower bounds, we design algorithms that operate in batches by dividing the time horizon into batches to restrict the number of switches between actions. For the bandit feedback setting, where only the total loss of the combinatorial arm is observed, we introduce the BATCHED-EXP2 algorithm which achieves a regret upper bound of Õ ( (λK)1/3T2/3I4/3asTtends to infinity. In the semi-bandit feedback setting, where all losses for the combinatorial arm are observed, we propose the BATCHED-BROAD algorithm which achieves a regret upper bound of Õ ( (λK)1/3(TI)2/3).

There exists a gap for the proofs of the converse parts of (49) and (50) inTheorem 1and (74) ofTheorem 3. These converse parts use Lemma 4, whose proofs contain a gap. We fix these errors when the rate is larger than the critical rate. A special case of (50) does not coincide the recent result (Li and Yao, 2022, arXiv:2209.00554v1) when the rate is smaller than the critical rate.

We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite-state space. The state transitions in each arm are captured by an ergodic transition probability matrix (TPM) that is a member of a single-parameter exponential family of TPMs. The real-valued parameters of the arm TPMs are unknown and belong to a given space. Given a function f defined on the common state space of the arms, the goal is to identify the best arm—the arm with the largest average value of f evaluated under the arm’s stationary distribution—with the fewest number of samples, subject to an upper bound on the decision’s error probability (i.e., the fixed-confidence regime). A lower bound on the growth rate of the expected stopping time is established in the asymptote of a vanishing error probability. Furthermore, a policy for best arm identification is proposed, and its expected stopping time is proved to have an asymptotic growth rate that matches the lower bound. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds. It is shown that under every policy, the state-action visitation proportions satisfy a specific approximate flow conservation constraint and that these proportions match the optimal proportions dictated by the lower bound under any asymptotically optimal policy. The prior studies on best arm identification in restless bandits focus on independent observations from the arms, rested Markov arms, and restless Markov arms with known arm TPMs. In contrast, this work is the first to study best arm identification in restless bandits with unknown arm TPMs.

We study the problem of best arm identification in a federated learning multi-armed bandit setup with a central server and multiple clients. Each client is associated with a multi-armed bandit in which each arm yields i.i.d. rewards following a Gaussian distribution with an unknown mean and known variance. The set of arms is assumed to be the same at all the clients. We define two notions of best arm local and global. The local best arm at a client is the arm with the largest mean among the arms local to the client, whereas the global best arm is the arm with the largest average mean across all the clients. We assume that each client can only observe the rewards from its local arms and thereby estimate its local best arm. The clients communicate with a central server on uplinks that entail a cost of C>=0 units per usage per uplink. The global best arm is estimated at the server. The goal is to identify the local best arms and the global best arm with minimal total cost, defined as the sum of the total number of arm selections at all the clients and the total communication cost, subject to an upper bound on the error probability. We propose a novel algorithm FedElim that is based on successive elimination and communicates only in exponential time steps and obtain a high probability instance-dependent upper bound on its total cost. The key takeaway from our paper is that for any C>=0 and error probabilities sufficiently small, the total number of arm selections (resp. the total cost) under FedElim is at most 2 (resp. 3) times the maximum total number of arm selections under its variant that communicates in every time step. Additionally, we show that the latter is optimal in expectation up to a constant factor, thereby demonstrating that communication is almost cost-free in FedElim. We numerically validate the efficacy of FedElim on two synthetic datasets and the MovieLens dataset.

We provide an exact characterization of the expected generalization error (gen-error) for semi-supervised learning (SSL) with pseudo-labeling via the Gibbs algorithm. The gen-error is expressed in terms of the symmetrized KL information between the output hypothesis, the pseudo-labeled dataset, and the labeled dataset. Distribution-free upper and lower bounds on the gen-error can also be obtained. Our findings offer new insights that the generalization performance of SSL with pseudo-labeling is affected not only by the information between the output hypothesis and input training data but also by the information shared between the labeled and pseudo-labeled data samples. This serves as a guideline to choose an appropriate pseudo-labeling method from a given family of methods. To deepen our understanding, we further explore two examples—mean estimation and logistic regression. In particular, we analyze how the ratio of the number of unlabeled to labeled data $\lambda$ affects the gen-error under both scenarios. As $\lambda$ increases, the gen-error for mean estimation decreases and then saturates at a value larger than when all the samples are labeled, and the gap can be quantified exactly with our analysis, and is dependent on the cross-covariance between the labeled and pseudo-labeled data samples. For logistic regression, the gen-error and the variance component of the excess risk also decrease as $\lambda$ increases.

Graph neural networks (GNNs) have gained an increasing amount of popularity due to their superior capability in learning node embeddings for various graph inference tasks, but training them can raise privacy concerns. To address this, we propose using link local differential privacy over decentralized nodes, enabling collaboration with an untrusted server to train GNNs without revealing the existence of any link. Our approach spends the privacy budget separately on links and degrees of the graph for the server to better denoise the graph topology using Bayesian estimation, alleviating the negative impact of LDP on the accuracy of the trained GNNs. We bound the mean absolute error of the inferred link probabilities against the ground truth graph topology. We then propose two variants of our LDP mechanism complementing each other in different privacy settings, one of which estimates fewer links under lower privacy budgets to avoid false positive link estimates when the uncertainty is high, while the other utilizes more information and performs better given relatively higher privacy budgets. Furthermore, we propose a hybrid variant that combines both strategies and is able to perform better across different privacy budgets. Extensive experiments show that our approach outperforms existing methods in terms of accuracy under varying privacy budgets.

Model-based deep learning has achieved astounding successes due in part to the availability of large-scale real-world data. However, processing such massive amounts of data comes at a considerable cost in terms of computations, storage, training and the search for good neural architectures. Dataset distillation has thus recently come to the fore. This paradigm involves distilling information from large real-world datasets into tiny and compact synthetic datasets such that processing the latter ideally yields similar performances as the former. State-of-the-art methods primarily rely on learning the synthetic dataset by matching the gradients obtained during training between the real and synthetic data. However, these gradient-matching methods suffer from the so-called accumulated trajectory error caused by the discrepancy between the distillation and subsequent evaluation. To mitigate the adverse impact of this accumulated trajectory error, we propose a novel approach that encourages the optimization algorithm to seek a flat trajectory. We show that the weights trained on synthetic data are robust against the accumulated errors perturbations with the regularization towards the flat trajectory. Our method, called Flat Trajectory Distillation (FTD), is shown to boost the performance of gradient-matching methods by up to 4.7% on a subset of images of the ImageNet dataset with higher resolution images. We also validate the effectiveness and generalizability of our method with datasets of different resolutions and demonstrate its applicability to neural architecture search. Code is available at. https://github.com/AngusDujw/FTD-distillation.

Motivated by concerns about making online decisions that incur undue amount of risk at each time step, in this paper, we formulate the probably anytime-safe stochastic combinatorial semi-bandits problem. In this problem, the agent is given the option to select a subset of size at most $K$ from a set of $L$ ground items. Each item is associated to a certain mean reward as well as a variance that represents its risk. To mitigate the risk that the agent incurs, we require that with probability at least $1-\delta$, over the entire horizon of time $T$, each of the choices that the agent makes should contain items whose sum of variances does not exceed a certain variance budget. We call this probably anytime-safe constraint. Under this constraint, we design and analyze an algorithm PASCombUCB that minimizes the regret over the horizon of time $T$. By developing accompanying information-theoretic lower bounds, we show that under both the problem-dependent and problem-independent paradigms, PASCombUCB is almost asymptotically optimal. Experiments are conducted to corroborate our theoretical findings. Our problem setup, the proposed PASCombUCB algorithm, and novel analyses are applicable to domains such as recommendation systems and transportation in which an agent is allowed to choose multiple items at a single time step and wishes to control the risk over the whole time horizon.

We study a distributed stochastic multi-armed bandit where a client supplies the learner with communication-constrained feedback based on the rewards for the corresponding arm pulls. In our setup, the client must encode the rewards such that the second moment of the encoded rewards is no more than $P$, and this encoded reward is further corrupted by additive Gaussian noise of variance $\sigma^2$; the learner only has access to this corrupted reward. For this setting, we derive an information-theoretic lower bound of $\Omega\left(\sqrt{\frac{KT}{\mathtt{SNR} \wedge1}} \right)$ on the minimax regret of any scheme, where $\mathtt{SNR}\coloneqq \frac{P}{\sigma^2}$, and $K$ and $T$ are the number of arms and time horizon, respectively. Furthermore, we propose a multi-phase bandit algorithm, $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$, which matches this lower bound to a minor additive factor. $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ performs uniform exploration in its initial phases and then utilizes the *upper confidence bound *(UCB) bandit algorithm in its final phase. An interesting feature of $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ is that the coarser estimates of the mean rewards formed during a uniform exploration phase help to refine the encoding protocol in the next phase, leading to more accurate mean estimates of the rewards in the subsequent phase. This positive reinforcement cycle is critical to reducing the number of uniform exploration rounds and closely matching our lower bound.

Codes for correcting sticky insertions/deletions and limited-magnitude errors have attracted significant attention due to their applications of flash memories, racetrack memories, and DNA data storage systems. In this paper, we first consider the error type of t sticky deletions with ℓ-limited-magnitude and propose a non-systematic code for correcting this type of error with redundancy 2t(1 − 1/p) • log(n + 1) + O(1), where p is the smallest prime larger than ℓ + 1. Next, we present a systematic code construction with an efficient encoding and decoding algorithm with redundancy $\frac{{\left\lceil {2t(1 - 1/p)} \right\rceil \cdot \left\lceil {\log p} \right\rceil }}{{\log p}}\log (n + 1) + O(\log \log n)$, where p is the smallest prime larger than ℓ + 1.

This paper studies two fundamental problems in regularized Graphon Mean-Field Games (GMFGs). First, we establish the existence of a Nash Equilibrium (NE) of any $\lambda$-regularized GMFG (for $\lambda\geq 0$). This result relies on weaker conditions than previous works analyzing both unregularized GMFGs ($\lambda=0$) and $\lambda$-regularized MFGs, which are special cases of GMFGs. Second, we propose provably efficient algorithms to learn the NE in weakly monotone GMFGs, motivated by Lasry and Lions (2007). Previous literature either only analyzed continuous-time algorithms or required extra conditions to analyze discrete-time algorithms. In contrast, we design a discrete-time algorithm and derive its convergence rate solely under weakly monotone conditions. Furthermore, we develop and analyze the action-value function estimation procedure during the online learning process, which is absent from algorithms for monotone GMFGs. This serves as a sub-module in our optimization algorithm. The efficiency of the designed algorithm is corroborated by empirical evaluations.

Abstract. We provide finite sample guarantees for the classical Chow–Liu algorithm [Chow and Liu, IEEE Trans. Inform. Theory, 14 (1968), pp. 462–467] to learn a tree-structured graphical model of a distribution. For a distribution [Formula: see text] on [Formula: see text] and a tree [Formula: see text] on [Formula: see text] nodes, we say [Formula: see text] is an [Formula: see text]-approximate tree for [Formula: see text] if there is a [Formula: see text]-structured distribution [Formula: see text] such that [Formula: see text] is at most [Formula: see text] more than the best possible tree-structured distribution for [Formula: see text]. We show that if [Formula: see text] itself is tree-structured, then the Chow–Liu algorithm with the plug-in estimator for mutual information with [Formula: see text] independent and identically distributed samples outputs an [Formula: see text]-approximate tree for [Formula: see text] with constant probability. In contrast, for a general [Formula: see text] (which may not be tree-structured), [Formula: see text] samples are necessary to find an [Formula: see text]-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne et al. [ Proceedings of the 50 th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 735–748]: we prove that for three random variables [Formula: see text] each over [Formula: see text], testing if [Formula: see text] is 0 or [Formula: see text] is possible with [Formula: see text] samples. Finally, we show that for a specific tree [Formula: see text], with [Formula: see text] samples from a distribution [Formula: see text] over [Formula: see text], one can efficiently learn the closest [Formula: see text]-structured distribution in KL divergence by applying the add-1 estimator at each node.

In this paper, we consider a novel$M$-ary sequential hypothesis testing problem in which an adversary is present and perturbs the distributions of the samples before the decision maker observes them. This problem is formulated as a sequential adversarial hypothesis testing game played between the decision maker and the adversary. This game is a zero-sum and strategic one. We assume the adversary is active under all hypotheses and knows the underlying distribution of observed samples. We adopt this framework as it is the worst-case scenario from the perspective of the decision maker. The goal of the decision maker is to minimize the expectation of the stopping time to ensure that the test is as efficient as possible; the adversary’s goal is, instead, to maximize the stopping time. We derive a pair of strategies under which the asymptotic Nash equilibrium of the game is attained. We also consider the case in which the adversary is not aware of the underlying hypothesis and hence is constrained to apply the same strategy regardless of which hypothesis is in effect. Numerical results corroborate our theoretical findings.

We design and analyze Variance-Aware-Lower and Upper Confidence Bound (VA-LUCB), a parameter-free algorithm, for identifying the best arm under the fixed-confidence setup and under a stringent constraint that the variance of the chosen arm is strictly smaller than a given threshold. An upper bound on VA-LUCB’s sample complexity is shown to be characterized by a fundamental variance-aware hardness quantity$H_{\mathrm {VA}}$. By proving an information-theoretic lower bound, we show that sample complexity of VA-LUCB is optimal up to a factor logarithmic in$H_{\mathrm {VA}}$. Extensive experiments corroborate the dependence of the sample complexity on the various terms in$H_{\mathrm {VA}}$. By comparing VA-LUCB’s empirical performance to a close competitor RiskAverse-UCB-BAI by David et al. (2018) our experiments suggest that VA-LUCB has the lowest sample complexity for this class of risk-constrained best arm identification problems, especially for the riskiest instances.

We study the problem of identifying the best arm in a multi-armed bandit environment when each arm is a time-homogeneous and ergodic discrete-time Markov process on a common, finite state space. The state evolution on each arm is governed by the arm’s transition probability matrix (TPM). A decision entity that knows the set of arm TPMs but not the exact mapping of the TPMs to the arms, wishes to find the index of the best arm as quickly as possible, subject to an upper bound on the error probability. The decision entity selects one arm at a time sequentially, and all the unselected arms continue to undergo state evolution (restless arms). For this problem, we derive the first-known problem instance-dependent asymptotic lower bound on the growth rate of the expected time required to find the index of the best arm, where the asymptotics is as the error probability vanishes. Further, we propose a sequential policy that, for an input parameter$R$, forcibly selects an arm that has not been selected for$R$consecutive time instants. We show that this policy achieves an upper bound that depends on$R$and is monotonically non-increasing as$R\to \infty $. The question of whether, in general, the limiting value of the upper bound as$R\to \infty $matches with the lower bound, remains open. We identify a special case in which the upper and the lower bounds match. Prior works on best arm identification have dealt with (a) independent and identically distributed observations from the arms, and (b) rested Markov arms, whereas our work deals with the more difficult setting of restless Markov arms.

This paper investigates fundamental limits of exact recovery in the general$d$-uniform hypergraph stochastic block model ($d$-HSBM), wherein$n$nodes are partitioned into$k$disjoint communities with relative sizes$(p_{1},\ldots , p_{k})$. Each subset of nodes with cardinality$d$is generated independently as an order-$d$hyperedge with a certain probability that depends on the ground-truth communities that the$d$nodes belong to. The goal is to exactly recover the$k$hidden communities based on the observed hypergraph. We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below the threshold (apart from a small regime of parameters that will be specified precisely). This threshold is represented in terms of a quantity which we term as the generalized Chernoff-Hellinger divergence between communities. Our result for this general model recovers prior results for the standard SBM and$d$-HSBM with two symmetric communities as special cases. En route to proving our achievability results, we develop a polynomial-time two-stage algorithm that meets the threshold. The first stage adopts a certain hypergraph spectral clustering method to obtain a coarse estimate of communities, and the second stage refines each node individually via local refinement steps to ensure exact recovery.

This paper considers the problem of covert communication over binary-input discrete memoryless channels with mismatched decoding, in which a sender wishes to reliably communicate with a receiver whose decoder is fixed and possibly sub-optimal, and simultaneously to ensure that the communication is covert with respect to a warden. We present a single-letter lower bound and two single-letter upper bounds on the information-theoretically optimal throughput as a function of the given decoding metric, channel laws, and the desired level of covertness. These bounds match for a variety of scenarios of interest, such as (i) when the channel between the sender and receiver is a binary-input binary-output channel, and (ii) when the decoding metric is particularized to the so-called erasures-only metric. The lower bound is obtained based on a modified random coding union bound with pulse position modulation (PPM) codebooks, coupled with a non-standard expurgation argument. The upper bounds are based on the idea of translating the mismatched-decoding error of the original channel to the decoding error of an auxiliary channel.

The Chow–Liu algorithm (IEEE Trans. Inform. Theory, 1968) has been a mainstay for the learning of tree-structured graphical models from i.i.d. sampled data vectors. Its theoretical properties have been well-studied and are well-understood. In this paper, we focus on the class of trees that are arguably even more fundamental, namelyhomogeneoustrees in which each pair of nodes that forms an edge has the same correlation$\rho $. We ask whether we are able to further reduce the error probability of learning the structure of the homogeneous tree model whenactive learningis allowed. Our figure of merit is theerror exponent, which quantifies the exponential rate of decay of the error probability with an increasing number of data samples. We design and analyze an algorithmActiveLearningAlgorithm forTrees withHomogeneousEdges (ACTIVE-LATHE), which surprisingly boosts the error exponent by at least 40% when$\rho $is at least 0.8. For all other values of$\rho $, we also observe commensurate, but more modest, improvements in the error exponent. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph in which we are less confident of being correct.

The beam alignment (BA) problem consists in accurately aligning the transmitter and receiver beams to establish a reliable communication link in wireless communication systems. Existing BA methods search the entire beam space to identify the optimal transmit-receive beam pair. This incurs a significant latency when the number of antennas is large. In this work, we develop a bandit-based fast BA algorithm to reduce BA latency for millimeter-wave (mmWave) communications. Our algorithm is named Two-Phase Heteroscedastic Track-and-Stop (2PHT&S). We first formulate the BA problem as a pure exploration problem in multi-armed bandits in which the objective is to minimize the required number of time steps given a certain fixed confidence level. By taking advantage of the correlation structure among beams that the information from nearby beams is similar and the heteroscedastic property that the variance of the reward of an arm (beam) is related to its mean, the proposed algorithm groups all beams into several beam sets such that the optimal beam set is first selected and the optimal beam is identified in this set after that. Theoretical analysis and simulation results on synthetic and semi-practical channel data demonstrate the clear superiority of the proposed algorithm vis-à-vis other baseline competitors.

This paper unifies the design and the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem for a class of risk functionals ρ that are continuous and dominant. We prove generalised concentration bounds for these continuous and dominant risk functionals and show that a wide class of popular risk functionals belong to this class. Using our newly developed analytical toolkits, we analyse the algorithm ρ-MTS (for multinomial distributions) and prove that they admit asymptotically optimal regret bounds of risk-averse algorithms under the CVaR, proportional hazard, and other ubiquitous risk measures. More generally, we prove the asymptotic optimality of ρ-MTS for Bernoulli distributions for a class of risk measures known as empirical distribution performance measures (EDPMs); this includes the well-known mean-variance. Numerical simulations show that the regret bounds incurred by our algorithms are reasonably tight vis-à-vis algorithm-independent lower bounds.

Class Incremental Learning (CIL) aims at learning a classifier in a phase-by-phase manner, in which only data of a subset of the classes are provided at each phase. Previous works mainly focus on mitigating forgetting in phases after the initial one. However, we find that improving CIL at its initial phase is also a promising direction. Specifically, we experimentally show that directly encouraging CIL Learner at the initial phase to output similar representations as the model jointly trained on all classes can greatly boost the CIL performance. Motivated by this, we study the differ-ence between a naively-trained initial-phase model and the oracle model. Specifically, since one major difference be-tween these two models is the number of training classes, we investigate how such difference affects the model rep-resentations. We find that, with fewer training classes, the data representations of each class lie in a long and narrow region; with more training classes, the representations of each class scatter more uniformly. Inspired by this obser-vation, we propose Class-wise Decorrelation (CwD) that ef-fectively regularizes representations of each class to scatter more uniformly, thus mimicking the model jointly trained with all classes (i.e., the oracle model). Our CwD is simple to implement and easy to plug into existing methods. Ex-tensive experiments on various benchmark datasets show that CwD consistently and significantly improves the per-formance of existing state-of-the-art methods by around 1% to 3%. Code: https://github.com/Yujun-Shi/CwD.

In several applications such as clinical trials and financial portfolio optimization, the expected value (or the average reward) does not satisfactorily capture the merits of a drug or a portfolio. In such applications, risk plays a crucial role, and a risk-aware performance measure is preferable, so as to capture losses in the case of adverse events. This survey aims to consolidate and summarise the existing research on risk measures, specifically in the context of multi-armed bandits. We review various risk measures of interest, and comment on their properties. Next, we review existing concentration inequalities for various risk measures. Then, we proceed to defining risk-aware bandit problems, We consider algorithms for the regret minimization setting, where the exploration-exploitation tradeoff manifests, as well as the best arm identification setting, which is a pure exploration problem—both in the context of risk-sensitive measures. We conclude by commenting on persisting challenges and fertile areas for future research.

This work systematically investigates the adversarial robustness of deep image denoisers (DIDs), i.e, how well DIDs can recover the ground truth from noisy observations degraded by adversarial perturbations. Firstly, to evaluate DIDs’ robustness, we propose a novel adversarial attack, namely Observation-based Zero-mean Attack (OBSATK), to craft adversarial zero-mean perturbations on given noisy images. We find that existing DIDs are vulnerable to the adversarial noise generated by OBSATK. Secondly, to robustify DIDs, we pro- pose an adversarial training strategy, hybrid adversarial training (HAT), that jointly trains DIDs with adversarial and non-adversarial noisy data to ensure that the reconstruction quality is high and the denoisers around non-adversarial data are locally smooth. The resultant DIDs can effectively remove various types of synthetic and adversarial noise. We also uncover that the robustness of DIDs benefits their generalization capability on unseen real-world noise. Indeed, HAT-trained DIDs can recover high-quality clean images from real-world noise even without training on real noisy data. Extensive experiments on benchmark datasets, including Set68, PolyU, and SIDD, corroborate the effectiveness of OBSATK and HAT.

In this paper, we formulate the sequential binary hypothesis testing problem in which an adversary is active under both hypotheses. This problem is formulated as a sequential adversarial hypothesis testing game played between the decision maker and the adversary and it is a zero-sum and strategic one. The goal of the decision maker is to minimize the expectation of stopping time to make the test more efficient, while the adversary’s goal is to maximize it. We obtain the pair of strategies under which the asymptotic Nash equilibrium of the game is attained.

The beam alignment (BA) problem consists in accurately aligning the transmitter and receiver beams to establish a reliable communication link in wireless communication systems. Existing BA methods search the entire beam space to identify the optimal transmit-receive beam pair. This incurs a significant latency when the number of antennas is large. In this work, we develop a bandit-based fast BA algorithm to reduce BA latency for millimeter-wave (mmWave) communications. Our algorithm is named Two Phase Heteroscedastic Track-and-Stop (2PHT&S). We first formulate the BA problem as a pure exploration problem in multi-armed bandits in which the objective is to minimize the required number of time steps given a certain fixed confidence setting. By taking advantage of the correlation structure among beams that the information from nearby beams are similar and the heteroscedastic property that the variance of the reward of an arm (beam) is linearly related to its mean, the proposed algorithm groups all beams into several sets of beams such that the optimal beam set is first selected, and the optimal beam is identified from this set after that. Theoretical analysis and simulation results demonstrate the superiority of the proposed algorithm vis-à-vis other baseline competitors.

This paper considers the problem of covert communication over binary-input discrete memoryless channels with mismatched decoding, in which a sender wishes to reliably communicate with a receiver whose decoder is fixed and possibly suboptimal, and simultaneously to ensure that the communication is covert with respect to a warden. We present single-letter lower and upper bounds on the information-theoretically optimal throughput as a function of the given decoding metric, channel laws, and the desired level of covertness. These bounds match when the decoding metric is particularized to the erasures-only metric, yielding an exact single-letter expression for the so-called covert erasures-only capacity. The lower bound is obtained based on a modified random coding union bound with pulse position modulation (PPM) codebooks, coupled with a nonstandard expurgation argument. The proof of the upper bound relies on a non-trivial combination of analytical techniques for the problems of covert communication and mismatched decoding.

We study the problem of best arm identification in multi-armed bandits when each arm is an ergodic Markov process that evolves whether or not the arm is selected (restless arms). The evolution of each arm’s Markov process is governed by its transition probability matrix (TPM). A decision entity that knows the set of arm TPMs but not the exact mapping of the TPMs to the arms, wishes to find the index of the best arm as quickly as possible, subject to an upper bound on the error probability. We derive an asymptotic lower bound on the expected time required to find the best arm, where the asymptotics is as the error probability vanishes. Also, we design a policy that, for an input parameter R, forcibly selects an arm that has not been selected for R consecutive time instants, and achieves an upper bound that is monotonically non-increasing in R. Showing that, in general, the lower bound and the limiting value of the upper bounds as R→∞ match, appears to be difficult and remains open. These bounds are, however, shown to match in the special case when the TPM of each arm has identical rows, i.e., the arms yield independent and identically distributed observations.

Codes in the Damerau–Levenshtein metric have been studied recently owing to their applications in DNA-based data storage. In previous work, codes for correcting a single deletion and multiple adjacent transpositions were presented. In this work, we consider a new setting with the asymmetric Damerau–Levenshtein distance where both 0-deletions and adjacent transpositions occur. We first study uniquely-decodable codes and present an optimal code (in the sense that its redundancy is optimal up to a constant additive term) correcting a single 0-deletion or a single adjacent transposition with redundancy log n + 2 bits. Then, we present a construction of codes correcting t 0-deletions and s adjacent transpositions with at most (t + 2s) log n bits of redundancy. Next, we focus on list-decodable codes and construct a list-decodable code with list-size O(nmin{s+1,t}) and has at most (max{t, s + 1}) log n bits of redundancy.

The Chow-Liu algorithm has been a mainstay for the learning of tree-structured graphical models from i.i.d. sampled data vectors. Its theoretical properties have been well-studied and are well-understood. In this paper, we focus on the class of trees that are arguably even more fundamental, namely homogeneous trees in which each pair of nodes that forms an edge has the same correlation ρ. We ask whether we are able to further reduce the error probability of learning the structure of the homogeneous tree model when active learning is allowed. Our figure of merit is the error exponent, which quantifies the exponential rate of decay of the error probability with an increasing number of data samples. We design and analyze an algorithm Active Learning Algorithm for Trees with Homogeneous Edges (ACTIVE-LATHE), which surprisingly boosts (increases) the error exponent. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph in which we are less confident of being correct.

Modern deep neural networks (DNNs) have achieved state-of-the-art performances but are typically over-parameterized. The over-parameterization may result in undesirably large generalization error in the absence of other customized training strategies. Recently, a line of research under the name of Sharpness-Aware Minimization (SAM) has shown that minimizing a sharpness measure, which reflects the geometry of the loss landscape, can significantly reduce the generalization error. However, SAM-like methods incur a two-fold computational overhead of the given base optimizer (e.g. SGD) for approximating the sharpness measure. In this paper, we propose Sharpness-Aware Training for Free, or SAF, which mitigates the sharp landscape at almost zero additional computational cost over the base optimizer. Intuitively, SAF achieves this by avoiding sudden drops in the loss in the sharp local minima throughout the trajectory of the updates of the weights. Specifically, we suggest a novel trajectory loss, based on the KL-divergence between the outputs of DNNs with the current weights and past weights, as a replacement of the SAM's sharpness measure. This loss captures the rate of change of the training loss along the model's update trajectory. By minimizing it, SAF ensures the convergence to a flat minimum with improved generalization capabilities. Extensive empirical results show that SAF minimizes the sharpness in the same way that SAM does, yielding better results on the ImageNet dataset with essentially the same computational cost as the base optimizer.

We study the problem of best arm identification in linear bandits in the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-free algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We provide a theoretical analysis of the failure probability of OD-LinBAI. Instead of all the optimality gaps, the performance of OD-LinBAI depends only on the gaps of the top $d$ arms, where $d$ is the effective dimension of the linear bandit instance. Complementarily, we present a minimax lower bound for this problem. The upper and lower bounds show that OD-LinBAI is minimax optimal up to constant multiplicative factors in the exponent, which is a significant theoretical improvement over existing methods (e.g., BayesGap, Peace, LinearExploration and GSE), and settles the question of ascertaining the difficulty of learning the best arm in the fixed-budget setting. Finally, numerical experiments demonstrate considerable empirical improvements over existing algorithms on a variety of real and synthetic datasets.

The cooperative Multi-Agent Reinforcement Learning (MARL) with permutation invariant agents framework has achieved tremendous empirical successes in real-world applications. Unfortunately, the theoretical understanding of this MARL problem is lacking due to the curse of many agents and the limited exploration of the relational reasoning in existing works. In this paper, we verify that the transformer implements complex relational reasoning, and we propose and analyze model-free and model-based offline MARL algorithms with the transformer approximators. We prove that the suboptimality gaps of the model-free and model-based algorithms are independent of and logarithmic in the number of agents respectively, which mitigates the curse of many agents. These results are consequences of a novel generalization error bound of the transformer and a novel analysis of the Maximum Likelihood Estimate (MLE) of the system dynamics with the transformer. Our model-based algorithm is the first provably efficient MARL algorithm that explicitly exploits the permutation invariance of the agents. Our improved generalization bound may be of independent interest and is applicable to other regression problems related to the transformer beyond MARL.

Using information-theoretic principles, we consider the generalization error (gen-error) of iterative semi-supervised learning (SSL) algorithms that iteratively generate pseudo-labels for a large amount of unlabelled data to progressively refine the model parameters. In contrast to most previous works that bound the gen-error, we provide an exact expression for the gen-error and particularize it to the binary Gaussian mixture model. Our theoretical results suggest that when the class conditional variances are not too large, the gen-error decreases with the number of iterations, but quickly saturates. On the flip side, if the class conditional variances (and so amount of overlap between the classes) are large, the gen-error increases with the number of iterations. To mitigate this undesirable effect, we show that regularization can reduce the gen-error. The theoretical results are corroborated by extensive experiments on the MNIST and CIFAR datasets in which we notice that for easy-to-distinguish classes, the gen-error improves after several pseudo-labelling iterations, but saturates afterwards, and for more difficult-to-distinguish classes, regularization improves the generalization performance.

Nonnegative matrix factorization (NMF) is a linear dimensionality reduction technique for analyzing nonnegative data. A key aspect of NMF is the choice of the objective function that depends on the noise model (or statistics of the noise) assumed on the data. In many applications, the noise model is unknown and difficult to estimate. In this paper, we define a multi-objective NMF (MO-NMF) problem, where several objectives are combined within the same NMF model. We propose to use Lagrange duality to judiciously optimize for a set of weights to be used within the framework of the weighted-sum approach, that is, we minimize a single objective function which is a weighted sum of the all objective functions. We design a simple algorithm based on multiplicative updates to minimize this weighted sum. We show how this can be used to find distributionally robust NMF (DR-NMF) solutions, that is, solutions that minimize the largest error among all objectives, using a dual approach solved via a heuristic inspired from the Frank-Wolfe algorithm. We illustrate the effectiveness of this approach on synthetic, document and audio data sets. The results show that DR-NMF is robust to our incognizance of the noise model of the NMF problem.

We consider the sequential composite binary hypothesis testing problem in which one of the hypotheses is governed by a single distribution while the other is governed by a family of distributions whose parameters belong to a known set$\Gamma $. We would like to design a test to decide which hypothesis is in effect. Under the constraints that the probabilities that the length of the test, a stopping time, exceeds$n$are bounded by a certain threshold$\epsilon $, we obtain certain fundamental limits on the asymptotic behavior of the sequential test as$n$tends to infinity. Assuming that$\Gamma $is a convex and compact set, we obtain the set of all first-order error exponents for the problem. We also prove a strong converse. Additionally, we obtain the set of second-order error exponents under the assumption that the alphabet of the observations$\mathcal {X}$is finite. In the proof of second-order asymptotics, a main technical contribution is the derivation of a central limit-type result for a maximum of an uncountable set of log-likelihood ratios under suitable conditions. This result may be of independent interest. We also show that some important statistical models satisfy the conditions.

This study considers the unconditional smooth Rényi entropy proposed by Renner and Wolf [ASIACRYPT, 2005], the smooth conditional Rényi entropy proposed by Kuzuoka [IEEE Trans. Inf. Th., 66(3), 1674–1690, 2020], and a novel quantity which we term theconditional smooth-⋆entropy.The latter two quantities can be specialized to the first in the absence of side-information. We explore the operational roles of these smooth Rényi entropies by establishing one-shot coding theorems for several information-theoretic problems, including Campbell’s source coding problem, the Arıkan–Massey guessing problem, and the Bunte–Lapidoth task encoding problem. We consider these problems in cases where the errors are non-vanishing and for each problem, we consider two error formalisms: the average and maximum error criteria, where the averaging and maximization are taken with respect to the side-information. Using the one-shot coding theorems, we conclude that Kuzuoka’s smooth conditional Rényi entropy and the conditional smooth-⋆ entropy are the solutions to the problems involving the average and maximum error criteria, respectively. Furthermore, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Applying our asymptotic expansions to the one-shot coding theorems, we derive various fundamental limits for these problems. We show that, under non-degenerate settings, the first-order fundamental limits differ under the average and maximum error criteria. This is in contrast to a different but related setting considered by the present authors [IEEE Trans. Inf. Th., 66(12), 7565–7587, 2020], for variable-length conditional source coding allowing errors, in which the first-order terms are identical but the second-order terms are different under these error criteria.

We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise with unknown statistics. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure; that is, a structure belonging to the equivalence class containing the true tree. This paper presents a systematic improvement of Katiyar et al. (2020). First, we present a novel impossibility result by deriving a bound on the necessary number of samples for partial recovery. Second, we derive a significantly improved sample complexity result in which the dependence on the minimum correlation $\rho_{\min}$ is $\rho_{\min}^{-8}$ instead of $\rho_{\min}^{-24}$. Finally, we propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery. We provide error exponent analyses and extensive numerical results on a variety of trees to show that the sample complexity of SGA is significantly better than the algorithm of Katiyar et al. (2020). SGA can be readily extended to Gaussian models and is shown via numerical experiments to be similarly superior.

We investigate the adversarial robustness of CNNs from the perspective of channel-wise activations. By comparing normally trained and adversarially trained models, we observe that adversarial training (AT) robustifies CNNs by aligning the channel-wise activations of adversarial data with those of their natural counterparts. However, the channels that are \textit{negatively-relevant} (NR) to predictions are still over-activated when processing adversarial data. Besides, we also observe that AT does not result in similar robustness for all classes. For the robust classes, channels with larger activation magnitudes are usually more \textit{positively-relevant} (PR) to predictions, but this alignment does not hold for the non-robust classes. Given these observations, we hypothesize that suppressing NR channels and aligning PR ones with their relevances further enhances the robustness of CNNs under AT. To examine this hypothesis, we introduce a novel mechanism, \textit{i.e.}, \underline{C}hannel-wise \underline{I}mportance-based \underline{F}eature \underline{S}election (CIFS). The CIFS manipulates channels’ activations of certain layers by generating non-negative multipliers to these channels based on their relevances to predictions. Extensive experiments on benchmark datasets including CIFAR10 and SVHN clearly verify the hypothesis and CIFS’s effectiveness of robustifying CNNs.

We consider a best arm identification (BAI) problem for stochastic bandits with adversarial corruptions in the fixed-budget setting of T steps. We design a novel randomized algorithm, Probabilistic Sequential Shrinking(u) (PSS(u)), which is agnostic to the amount of corruptions. When the amount of corruptions per step (CPS) is below a threshold, PSS(u) identifies the best arm or item with probability tending to 1 as T{\rightarrow}$\infty$. Otherwise, the optimality gap of the identified item degrades gracefully with the CPS.We argue that such a bifurcation is necessary. In PSS(u), the parameter u serves to balance between the optimality gap and success probability. The injection of randomization is shown to be essential to mitigate the impact of corruptions. To demonstrate this, we design two attack strategies that are applicable to any algorithm. We apply one of them to a deterministic analogue of PSS(u) known as Successive Halving (SH) by Karnin et al. (2013). The attack strategy results in a high failure probability for SH, but PSS(u) remains robust. In the absence of corruptions, PSS(2)’s performance guarantee matches SH’s. We show that when the CPS is sufficiently large, no algorithm can achieve a BAI probability tending to 1 as T{\rightarrow}$\infty$. Numerical experiments corroborate our theoretical findings.

In this work we show that for a stationary and ergodic source$X$, stationary and ergodic test channels achieve the rate-distortion function for the lossy source coding problem with feed-forward. As a by-product, we prove that the upper bound for the feed-forward rate-distortion function derived by Venkataramanan and Pradhan (2007) is tight. In addition, we derive an upper bound on the rate-distortion function by proving a Shannon-McMillan-Breiman theorem for the causally conditional entropy rate for the class of asymptotic mean stationary and ergodic processes.

We consider the sequential composite binary hypothesis testing problem in which one of the hypotheses is governed by a single distribution while the other is governed by a family of distributions whose parameters belong to a known set$\Gamma$. We would like to design a test to decide which hypothesis is in effect. Under the constraints that the probabilities that the length of the test, a stopping time, exceeds$n$are bounded by a certain threshold$\epsilon$, we obtain certain fundamental limits on the asymptotic behavior of the sequential test as$n$tends to infinity. Assuming that$\Gamma$is a convex and compact set, we obtain the set of all first-order error exponents for the problem. We also prove a strong converse. Additionally, under the assumption that$\Gamma$is a finite set, we obtain the set of second-order error exponents.

We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. In this setting, samples of an unknown state are requested sequentially and a decision to either continue or to accept one of the two hypotheses is made after each test. Under the constraint that the number of samples is bounded, either in expectation or with high probability, we exhibit adaptive strategies that minimize both types of misidentification errors. Namely, we show that these errors decrease exponentially (in the stopping time) with decay rates given by the measured relative entropies between the two states. Moreover, if we allow joint measurements on multiple samples, the rates are increased to the respective quantum relative entropies. We also fully characterize the achievable error exponents for non-adaptive strategies and provide numerical evidence showing that adaptive measurements are necessary to achieve our bounds.

In this paper, we consider sequential testing over a single-sensor, a single-decision center setup. At each time, instant t, the sensor gets k samples $(k \gt 0)$ and describes the observed sequence until time t to the decision center over a zero-rate noiseless link. The decision center sends a single bit of feedback to the sensor to request for more samples for compression/testing or to stop the transmission. We have characterized the optimal exponent of type-II error probability under the constraint that type-I error probability does not exceed a given threshold $\varepsilon \in(0,1)$ and also when the expectation of the number of requests from decision center is smaller than n which tends to infinity. Interestingly, the optimal exponent coincides with that for fixed-length hypothesis testing with zero-rate communication constraints.

We consider learning the structures of Gaussian latent tree models with vector observations when a subset of them are arbitrarily corrupted. First, we present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) without the assumption that the effective depth is bounded in the number of observed nodes, significantly generalizing the results in Choi et al. (2011). We show that Chow-Liu initialization in CLRG greatly reduces the sample complexity of RG from being exponential in the diameter of the tree to only logarithmic in the diameter for the hidden Markov model (HMM). Second, we robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. These robustified algorithms can tolerate a number of corruptions up to the square root of the number of clean samples. Finally, we derive the first known instance-dependent impossibility result for structure learning of latent trees. The optimalities of the robust version of CLRG and NJ are verified by comparing their sample complexities and the impossibility result.

Motivated by the important and urgent need for efficient optimization in online recommender systems, we revisit the cascading bandit model proposed by Kveton et al. (2015a). While Thompson sampling (TS) algorithms have been shown to be empirically superior to Upper Confidence Bound (UCB) algorithms for cascading bandits, theoretical guarantees are only known for the latter. In this paper, we first provide a problem-dependent upper bound on the regret of a TS algorithm with Beta-Bernoulli updates; this upper bound is tighter than a recent derivation under a more general setting by Huyuk and Tekin (2019). Next, we design and analyze another TS algorithm with Gaussian updates, TS-Cascade. TS-Cascade achieves the state-of-the-art problem-independent regret bound for cascading bandits. Complementarily, we consider a linear generalization of the cascading bandit model, which allows efficient learning in large-scale cascading bandit problem instances. We introduce and analyze a TS algorithm, which enjoys a regret bound that depends on the dimension of the linear model but not the number of items. Finally, by using information-theoretic techniques and a judicious construction of cascading bandit instances, we derive a nearly-matching lower bound on the expected regret for the standard model. Our paper establishes the first theoretical guarantees on TS algorithms for a stochastic combinatorial bandit problem model with partial feedback. Numerical experiments demonstrate the superiority of the proposed TS algorithms compared to existing UCB-based ones.

We consider an adversarially-trained version of the nonnegative matrix factorization, a popular latent dimensionality reduction technique. In our formulation, an attacker adds an arbitrary matrix of bounded norm to the given data matrix. We design efficient algorithms inspired by adversarial training to optimize for dictionary and coefficient matrices with enhanced generalization abilities. Extensive simulations on synthetic and benchmark datasets demonstrate the superior predictive performance on matrix completion tasks of our proposed method compared to state-of-the-art competitors, including other variants of adversarial nonnegative matrix factorization.

This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. In contrast to most related works, we assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available. We further require the probability of the estimation error to decay either exponentially or sub-exponentially fast (corresponding respectively to the large and moderate deviations regimes in information theory parlance). Based on the training sequences as well as the test sequence consisting of a single change-point, we design a change-point estimator and further show that this estimator is optimal by establishing matching (strong) converses. This leads to a full characterization of the optimal confidence width (i.e., half the width of the confidence interval within which the true change-point is located at with high probability) as a function of the undetected error, under both the large and moderate deviations regimes.

We consider the class of channels formed from the concatenation of a deletion channel and a finite-state channel. For this class of channels, we show that the operationally-defined capacity is equal to the stationary capacity. We also show that the stationary capacity can be approached by a sequence of Markov processes with increasing Markovian orders. As a by-product, we show that the polar coding scheme proposed by Tal, Pfister, Fazeli, and Vardy [arxiv: 1904.13385 (2019)] achieves the capacity of the binary deletion channel.

This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability.

We consider the fundamental limits of reliable communication over a two-state compound channel when the state of the channel needs to be masked. Our model is closely related to an area of study known as covert communication, a setting in which the transmitter wishes to communicate to legitimate receiver(s) while ensuring that the communication is not detected by an adversary. Our main contribution is the establishment of upper and lower bounds on the throughput-key length region when the constraint that quantifies how much the states are masked is defined to be the total variation distance between the channel output distributions of the two states. When length of the key is sufficiently large, we provide sufficient conditions for the bounds to coincide. Our results follow the so-called square-root law and hence are reminiscent of results in covert communications. Numerical examples, including that of a Gaussian channel, are provided to illustrate our results.

We leverage proof techniques from discrete Fourier analysis and an existing result in coding theory to derive new bounds for the problem of non-interactive simulation of binary random variables. Previous bounds in the literature were derived by applying data processing inequalities concerning maximal correlation or hypercontractivity. We show that our bounds are sharp in some regimes. Indeed, for a specific instance of the problem parameters, our main result resolves an open problem posed by E. Mossel in 2017. As by-products of our analyses, various new properties of the average distance and distance enumerator of binary block codes are established.

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size exp(exp(Θ(√{ n})) can be transmitted over n channel uses. We then characterize the exact pre-constant in the Θ(·) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.

We design and analyze CascadeBAI, an algorithm for finding the best set of K items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of available feedback at each step. To do so, we define a new class of random variables (r.v.’s) which we term as left-sided sub-Gaussian r.v.’s; this class is a relaxed version of the sub-Gaussian r.v.’s. This enables the application of a sufficiently tight Bernstein-type concentration inequality. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes. Finally, extensive numerical simulations corroborate the efficacy of CascadeBAI as well as the tightness of our upper bound on its time complexity.

The multi-armed bandit (MAB) problem is a classical learning task that exemplifies the exploration-exploitation tradeoff. However, standard formulations do not take into account risk. In online decision making systems, risk is a primary concern. In this regard, the mean-variance risk measure is one of the most common objective functions. Existing algorithms for mean-variance optimization in the context of MAB problems have unrealistic assumptions on the reward distributions. We develop Thompson Sampling-style algorithms for mean-variance MAB and provide comprehensive regret analyses for Gaussian and Bernoulli bandits with fewer assumptions. Our algorithms achieve the best known regret bounds for mean-variance MABs and also attain the information-theoretic bounds in some parameter regimes. Empirical simulations show that our algorithms significantly outperform existing LCB-based algorithms for all risk tolerances.

We consider the classical sequential binary hypothesis testing problem in which there are two hypotheses governed respectively by distributions P0and P1and we would like to decide which hypothesis is true using a sequential test. It is known from the work of Wald and Wolfowitz that as the expectation of the length of the test grows, the optimal typeI and type-II error exponents approach the relative entropies D(P1||P0) and D(P0||P1). We refine this result by considering the optimal backoff from the corner point of the achievable exponent region (D(P1||P0),D(P0||P1)) under the expectation constraint on the length of the test (or the sample size). We consider the expectation constraint in which the expectation of the sample size is bounded by n, and under mild conditions, characterize the backoff, also coined second-order asymptotics, precisely. Examples are provided to illustrate our results.

We consider the class of channels formed from the concatenation of a deletion channel and a finite-state channel. For this class of channels, we show that the operationally-defined capacity is equal to the stationary capacity. We also show that the stationary capacity can be approached by a sequence of Markov processes with increasing Markovian orders. As a byproduct, we show that the polar coding scheme constructed by Tal, Pfister, Fazeli, and Vardy [arxiv: 1904.13385 (2019)] achieves the capacity of the binary deletion channel.

We consider the problem of detecting one of M signals corrupted with white Gaussian noise. Conventionally, to minimize the probability of error, one uses matched filters to obtain a set of M sufficient statistics. In practice, M may be prohibitively large; this motivates the design and analysis of a reduced set of statistics which we term approximate sufficient statistics. By considering a sequence of sensing matrices that possesses suitable coherence and orthogonality properties, we bound the error exponent of the approximate sufficient statistics and compare it to that of the sufficient statistics. Additionally, we show that lower bound on the error exponent increases linearly for small compression rates.

Variable-length compression without prefix-free constraints and with side-information available at both encoder and decoder is considered. Instead of requiring the code to be error-free, we allow for it to have a non-vanishing error probability. We derive one-shot bounds on the optimal average codeword length by proposing two new information quantities; namely, the conditional and unconditional ε-cutoff entropies. Using these one-shot bounds, we obtain the second-order asymptotics of the problem under two different formalisms-the average and maximum probabilities of error with respect to the side-information. While the first-order terms in the asymptotic expansions for both formalisms are identical, we find that the source dispersion under the average error formalism is, in most cases, strictly smaller than its maximum counterpart. Applications to a certain class of guessing problems, previously studied by Kuzuoka [IEEE Trans. Inf. Theory, vol. 66, no. 3, pp. 1674-1690, 2020], are also discussed.

This study examines asymptotic expansions of the unconditional and conditional smooth Rényi entropies for a memoryless source. Using these smooth Rényi entropies, we establish one-shot coding theorems of several information-theoretic problems: Campbell's source coding, guessing, and task encoding problems, all allowing errors. Applying our asymptotic expansions to the derived one-shot coding theorems, we provide various asymptotic fundamental limits of these problems in the regime of non-vanishing error probabilities.

The "bee-identification problem" was formally defined by Tandon, Tan and Varshney [IEEE Trans. Commun., vol. 67, 2019], and the error exponent was studied. This work extends the results for the "absentee bees" scenario, where a small fraction of the bees are absent in the beehive image used for identification. For this setting, we present an exact characterization of the bee-identification error exponent, and show that independent barcode decoding is optimal, i.e., joint decoding of the bee barcodes does not result in a better error exponent relative to independent decoding of each noisy barcode. This is in contrast to the result without absentee bees, where joint barcode decoding results in a significantly higher error exponent than independent barcode decoding. We also define and characterize the `capacity' for the bee-identification problem with absentee bees, and prove the strong converse for the same.

We consider the problem of recovering communities of users and communities of items (such as movies) based on a partially observed rating matrix as well as side-information in the form of similarity graphs of the users and items. The user-to-user and item-to-item similarity graphs are generated according to the celebrated stochastic block model (SBM). We develop a lower bound on the minimum expected number of observed ratings (also known as the sample complexity) needed for this recovery task, which is a function of various parameters including the quality of the graph side-information manifested in the intra-and inter-cluster probabilities of the SBMs. Our information-theoretic results quantify the benefits of the two-sided graph side-information for recovery, and further analysis reveals that the two pieces of graph side-information produce an interesting synergistic effect under certain scenarios. This means that if one observes only one of the two graphs, then the required sample complexity worsens to the case in which none of the graphs is observed. Thus both graphs are strictly needed to reduce the sample complexity.

Consider the asymmetric broadcast channel with a random superposition codebook, which may be comprised of constant composition or i.i.d. codewords. By applying Forney's optimal decoder for individual messages and the message pair for the receiver that decodes both messages, exact (ensemble-tight) error and erasure exponents are derived. It is shown that the optimal decoder designed to decode the pair of messages achieves the optimal trade-off between the total and undetected exponents associated with the optimal decoder for the private message. Convex optimization-based procedures to evaluate the exponents efficiently are proposed. Finally, numerical examples are presented to illustrate the results.

We consider the problem of covert communication over wireless adhoc networks in which (roughly) n legitimate nodes (LNs) and nκfor κ > 0 non-communicating warden nodes (WNs) are randomly distributed in a square of unit area. Each legitimate source wants to communicate with its intended destination node while ensuring that every WN is unable to detect the presence of the communication. In this scenario, we study the throughput scaling law. Due to the covert communication constraint, the transmit powers are necessarily limited. Under this condition, we introduce a preservation region around each WN. This regionsuitably modified by taking a detour around each preservation region. To avoid the concentration of detours resulting extra relaying burdens, we distribute the detours evenly over a wide region. In the proposed HC scheme, we control the symbol power and the scheduling of distributed multiple-input multiple-output transmission. We also present upper bounds on the throughput scaling under the assumption that every active LN consumes the same average transmit power over the time period in which the WNs observe the channel outputs. For 0 <; κ <; 1, these upper bounds match with the achievable throughput scalings.

Consider a distributed detection problem in which the underlying distributions of the observations are unknown; instead of these distributions, noisy versions of empirically observed statistics are available to the fusion center. These empirically observed statistics, together with source (test) sequences, are transmitted through different channels to the fusion center. The fusion center decides which distribution the source sequence is sampled from based on these data. For the binary case, we derive the optimal type-II error exponent given that the type-I error decays exponentially fast. The type-II error exponent is maximized over the proportions of channels for both source and training sequences. We conclude that as the ratio of the lengths of training to test sequences α tends to infinity, using only one channel is optimal. By calculating the derived exponents numerically, we conjecture that the same is true when α is finite under certain conditions. We relate our results to the classical distributed detection problem studied by Tsitsiklis, in which the underlying distributions are known. Finally, our results are extended to the case of m-ary distributed detection with a rejection option.

We consider the classical sequential binary hypothesis testing problem in which there are two hypotheses governed respectively by distributions P0and P1and we would like to decide which hypothesis is true using a sequential test. It is known from the work of Wald and Wolfowitz that as the expectation of the length of the test grows, the optimal type-I and type-II error exponents approach the relative entropies D(P1∥P0) and D(P0∥P1). We refine this result by considering the optimal backoff-or second-order asymptotics-from the corner point of the achievable exponent region (D(P1∥P0), D(P0∥P1)) under two different constraints on the length of the test (or the sample size). First, we consider a probabilistic constraint in which the probability that the length of test exceeds a prescribed integer n is less than a certain threshold 0 <; ε <; 1. Second, the expectation of the sample size is bounded by n. In both cases, and under mild conditions, the second-order asymptotics is characterized exactly. Numerical examples are provided to illustrate our results.

The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. We also obtain bounds on the third-order coding rate. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate ϵ-net of the input probability simplex. While the achievability proof follows the general program to prove the third-order term for non-singular discrete memoryless channels put forth by Polyanskiy, several non-standard techniques-such as new definitions and bounds on the probabilities of typical sets using logarithmic Sobolev inequalities-are employed to handle the continuous nature of the channel.

Variable-length compression without prefix-free constraints and with side-information available at both encoder and decoder is considered. Instead of requiring the code to be error-free, we allow for it to have a non-vanishing error probability. We derive one-shot bounds on the optimal average codeword length by proposing two new information quantities; namely, the conditional and unconditional ε-cutoff entropies. Using these one-shot bounds, we obtain the second-order asymptotics of the problem under two different formalisms-the average and maximum probabilities of error over the realization of the side-information. While the first-order terms in the asymptotic expansions for both formalisms are identical, we find that the source dispersion under the average error formalism is, in most cases, strictly smaller than its maximum error counterpart. Applications to a certain class of guessing problems, previously studied by Kuzuoka (2020), are also discussed.

In this correspondence, we correct an erroneous result on the achievability part of the Rényi common information with order 1 + s E (1, 2] in (L. Yu and V. Y. F. Tan, “Wyner's common information under Rényi divergence measures,” IEEE Trans. Inf. Theory, vol. 64, no. 5, pp. 3616-3632, May 2018). The new achievability result (upper bound) of the Rényi common information no longer coincides with Wyner's common information. We also provide a new converse result (lower bound) in this correspondence for the Rényi common information with order 1 + s ϵ (1, ∞]. Numerical results show that for doubly symmetric binary sources, the new upper and lower bounds coincide for the order 1 + s ϵ (1, 2] and they are both strictly larger than Wyner's common information for this case.

We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.

Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, ∞-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.

We design and analyze TS-Cascade, a Thompson sampling algorithm for the cascading bandit problem. In TS-Cascade, Bayesian estimates of the click probability are constructed using a univariate Gaussian; this leads to a more efficient exploration procedure vis-ã-vis existing UCB-based approaches. We also incorporate the empirical variance of each item’s click probability into the Bayesian updates. These two novel features allow us to prove an expected regret bound of the form $\tilde{O}(\sqrt{KLT})$ where $L$ and $K$ are the number of ground items and the number of items in the chosen list respectively and $T\ge L$ is the number of Thompson sampling update steps. This matches the state-of-the-art regret bounds for UCB-based algorithms. More importantly, it is the first theoretical guarantee on a Thompson sampling algorithm for any stochastic combinatorial bandit problem model with partial feedback. Empirical experiments demonstrate superiority of TS-Cascade compared to existing UCB-based procedures in terms of the expected cumulative regret and the time complexity.

We develop an optimal primal-dual first-order algorithm for a class of stochastic three-composite convex minimization problems. The convergence rate of our method not only improves upon the existing methods, but also matches a lower bound derived for all first-order methods that solve this problem. We extend our proposed algorithm to solve a composite stochastic program with any finite number of nonsmooth functions. In addition, we generalize an optimal stochastic alternating direction method of multipliers (SADMM) algorithm proposed for the two-composite case to solve this problem, and establish its connection to our optimal primal-dual algorithm. We perform extensive numerical experiments on a variety of machine learning applications to demonstrate the superiority of our method via-a-vis the state-of-the-art.

Motivated by real-world machine learning applications, we analyze approximations to the non-asymptotic fundamental limits of statistical classification. In the binary version of this problem, given two training sequences generated according to two unknown distributions P1and P2, one is tasked to classify a test sequence which is known to be generated according to either P1or P2. This problem can be thought of as an analogue of the binary hypothesis testing problem but in the present setting, the generating distributions are unknown. Due to finite sample considerations, we consider the second-order asymptotics (or dispersion-type) tradeoff between type-I and type-II error probabilities for tests which ensure that (i) the type-I error probability for all pairs of distributions decays exponentially fast and (ii) the type-II error probability for a particular pair of distributions is non-vanishing. We generalize our results to classification of multiple hypotheses with the rejection option.

Recently, two extensions of Wyner's common information-exact and Rényi common informations-were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems refers to determining the minimum rate of the common input to two independent processors needed to generate an exact or approximate joint distribution. For the exact common information problem, an exact generation of the target distribution is required, while for Wyner's and α-Rényi common informations, the relative entropy and Rényi divergence with order α were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter. In this paper, we first establish the equivalence between the exact and ∞-Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and ∞-Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE.

We consider the exact channel synthesis problem. This problem concerns the determination of the amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is restricted to be close to a target distribution under the total variation (TV) distance measure, instead being exactly equal to the target distribution. We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources, which implies that for such sources, the admissible rate region is completely characterized. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for TV-approximate version.

In this paper, we study covert communication over a compound discrete memoryless channel (DMC). There are two channel states in which one of them is arbitrarily chosen and remains fixed during the transmission. The objective is to reliably send a message from the transmitter to the receiver. An adversary who is observing the channel output should not be able to infer the channel state. Two covertness metrics are considered. In the first metric, covertness is measured using the KL-divergence of the channel output marginal of each state with a fixed distribution. Different cases where such a distribution can be specified, are studied. The optimal transmission rate of each case is established. In the second metric, the covertness is measured by using the total variation distance of the channel output marginals of the two states. Upper and lower bounds on the optimal transmission covert rate are derived. The bounds match for a special case and characterize the optimal throughput.

By proving a strong converse, we strengthen the weak converse result by Salehkalaibar, Wigger and Wang (2017) concerning hypothesis testing against independence over a two-hop network with communication constraints. Our proof follows by judiciously combining two recently proposed techniques for proving strong converse theorems, namely the strong converse technique via reverse hypercontractivity by Liu, van Handel, and Verdú (2017) and the strong converse technique by Tyagi and Watanabe (2018), in which the authors used a change-of-measure technique and replaced hard Markov constraints with soft information costs. The techniques used in our paper can also be applied to prove strong converse theorems for other multiterminal hypothesis testing against independence problems.

We study the throughput scaling law of covert communication over wireless adhoc networks where (roughly) n legitimate nodes (LNs) and nκfor 0 <; κ <; 1 warden nodes (WNs) are randomly distributed in a unit area. Each legitimate source wants to communicate with its destination while ensuring that each WN is unable to detect the presence of communication. A preservation region, where the transmission of the LNs is not permitted, is introduced around each WN to increase the transmit power of the LNs outside the preservation regions. For achievability, multi-hop (MH), hierarchical cooperation (HC), and hybrid HC-MH schemes in the literature are utilized with some modifications. In the MH and the hybrid schemes, because the preservation regions may block the direct data paths, a detouring method that distributes the detours evenly over a wide region is proposed to avoid the concentration of relaying burdens. In the HC scheme, we properly control the symbol power and the MIMO transmission scheduling. We also present matching upper bounds on the throughput scaling under an assumption that every active LN consumes a same average transmit power over the time period that the WNs observe.

Motivated by real-world machine learning applications, we consider a statistical classification task in a sequential setting where test samples arrive sequentially. In addition, the generating distributions are unknown and only a set of empirically sampled sequences are available to a decision maker. The decision maker is tasked to classify a test sequence which is known to be generated according to either one of the distributions. In particular, for the binary case, the decision maker wishes to perform the classification task with minimum number of the test samples, so, at each step, she declares that either hypothesis 1 is true, hypothesis 2 is true, or she requests for an additional test sample. We propose a classifier and analyze the type-I and type-II error probabilities. We demonstrate the significant advantage of our sequential scheme compared to an existing non-sequential classifier proposed by Gutman. Finally, we extend our setup and results to the multi-class classification scenario and again demonstrate that the variable-length nature of the problem affords significant advantages as one can achieve the same set of exponents as Gutman's fixed-length setting but without having the rejection option.

We consider a binary distributed detection problem in which the distributions of the sensor observations are unknown and only empirically observed statistics are available to the fusion center. The source (test) sequences are transmitted through different channels to the fusion center, which also observes noisy versions of labelled training sequences generated independently from the two underlying distributions. The fusion center decides which distribution the source sequence is sampled from based on the observed statistics, i.e., the noisy training data. We derive the optimal type-II error exponent given that the type-I error decays exponentially fast. We further maximize the type-II error exponent over the proportions of channels for both source and training sequences and conclude that as the ratio of the lengths of training to test sequences tends to infinity, using only one channel is optimal. Finally, we relate our results to the distributed detection problem studied by Tsitsiklis.

The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate ε-net of the input probability simplex. An extended version of this paper is accessible at [1].

Consider the problem of identifying a massive number of bees, uniquely labeled with barcodes, using noisy measurements. We introduce this “bee-identification problem characterize the random coding exponent, and derive efficiently computable bounds for this exponent. We demonstrate that joint decoding of barcodes has much better exponent than separate decoding followed by permutation inference.

The fundamental limits of communication over state-dependent discrete memoryless channels with noiseless feedback are studied, under the assumption that the communicating parties are allowed to use variable-length coding schemes. Various cases are analyzed, with the employed coding schemes having either bounded or unbounded codeword lengths, and with state information revealed to the encoder and/or decoder in a strictly causal, causal, or non-causal manner. In each of these settings, necessary and sufficient conditions for positivity of the zero-error capacity are obtained and it is shown that, whenever the zero-error capacity is positive, it equals the conventional vanishing-error capacity. Moreover, it is shown that the vanishing-error capacity of state-dependent channels is not increased by the use of feedback and variable-length coding. Both these kinds of capacities of state-dependent channels with feedback are thus fully characterized.

Consider the problem of identifying a massive number of bees, uniquely labeled with barcodes, using noisy measurements. We formally introduce this “bee-identification problem”, define its error exponent, and derive efficiently computable upper and lower bounds for this exponent. We show that joint decoding of barcodes provides a significantly better exponent compared to separate decoding followed by permutation inference. For low rates, we prove that the lower bound on the bee-identification exponent obtained using typical random codes (TRC) is strictly better than the corresponding bound obtained using a random code ensemble (RCE). Further, as the rate approaches zero, we prove that the upper bound on the bee-identification exponent meets the lower bound obtained using TRC with joint barcode decoding.

This paper investigates the fundamental limits of communication over a noisy discrete memoryless channel that wears out, in the sense of signal-dependent catastrophic failure. In particular, we consider a channel that starts as a memoryless binary-input channel and when the number of transmitted ones causes a sufficient amount of damage, the channel ceases to convey signals. Constant composition codes are adopted to obtain an achievability bound, and the left-concave right-convex inequality is then refined to obtain a converse bound on the log-volume throughput for channels that wear out. Since infinite blocklength codes will always wear out the channel for any finite threshold of failure, and therefore cannot convey information at positive rates, we analyze the performance of finite blocklength codes to determine the maximum expected transmission volume at a given level of average error probability. We show that this maximization problem has a recursive form and can be solved by dynamic programming. Numerical results demonstrate that a sequence of block codes is preferred to a single block code for streaming sources.

We consider a covert communication scenario where a transmitter wishes to communicate simultaneously to two legitimate receivers while ensuring that the communication is not detected by an adversary, the warden. The legitimate receivers and the adversary observe the transmission from the transmitter via a three-user discrete or Gaussian memoryless broadcast channel. We focus on the case where the “no-input” symbol is not redundant, i.e., the output distribution at the warden induced by the no-input symbol is not a mixture of the output distributions induced by other input symbols, so that the covert communication is governed by the square root law, i.e., at most Θ(√n) bits can be transmitted over n channel uses. We show that for such a setting, a simple time-division strategy achieves the optimal throughputs for a non-trivial class of broadcast channels; this is not true for communicating over broadcast channels without the covert communication constraint. Our result implies that a code that uses two separate optimal point-to-point codes each designed for the constituent channels and each used for a fraction of the time is optimal in the sense that it achieves the best constants of the √n-scaling for the throughputs. Our proof strategy combines several elements in the network information theory literature, including concave envelope representations of the capacity regions of broadcast channels and El Gamal's outer bound for more capable broadcast channels.

We establish a general formula for the maximum size of finite length block codes with minimum pairwise distance no less than d. The achievability argument involves an iterative construction of a set of radius-d balls, each centered at a codeword. We demonstrate that the number of such balls that cover the entire code space cannot exceed this maximum size. Our approach can be applied to codes i) with elements over arbitrary code alphabets, and ii) under a broad class of distance measures. Our formula indicates that the maximum code size can be fully characterized by the cumulative distribution function of the distance measure evaluated at two independent and identically distributed random codewords. When the two random codewords assume a uniform distribution over the entire code alphabet, our formula recovers and thus naturally generalizes the Gilbert-Varshamov (GV) lower bound. Finally, we extend our study to the asymptotic setting.

The learning of mixture models can be viewed as a clustering problem. Indeed, given data samples independently generated from a mixture of distributions, we often would like to find the correct target clustering of the samples according to which component distribution they were generated from. For a clustering problem, practitioners often choose to use the simple k-means algorithm. k-means attempts to find an optimal clustering which minimizes the sum-of-squares distance between each point and its cluster center. In this paper, we consider fundamental (i.e., information-theoretic) limits of the solutions (clusterings) obtained by optimizing the sum-of-squares distance. In particular, we provide sufficient conditions for the closeness of any optimal clustering and the correct target clustering assuming that the data samples are generated from a mixture of spherical Gaussian distributions. We also generalize our results to log-concave distributions. Moreover, we show that under similar or even weaker conditions on the mixture model, any optimal clustering for the samples with reduced dimensionality is also close to the correct target clustering. These results provide intuition for the informativeness of k-means (with and without dimensionality reduction) as an algorithm for learning mixture models.

We consider data transmission across discrete memoryless channels (DMCs) using variable-length codes with feedback. We consider the family of such codes whose rates are ρN below the channel capacity C, where ρN is a positive sequence that tends to zero slower than the reciprocal of the square root of the expectation of the (random) blocklength N. This is known as the moderate deviations regime, and we establish the optimal moderate deviations constant. We show that in this scenario, the error probability decays sub-exponentially with speed exp(-(B/C)NρN), where B is the maximum relative entropy between output distributions of the DMC.

We consider transmission of discrete memoryless sources (DMSes) across discrete memoryless channels (DMCs) using variable-length lossy source-channel codes with feedback. The reliability function (optimum error exponent) is shown to be equal to max{0, B(1 - R(D)/C)},, where R(D) is the ratedistortion function of the source, B is the maximum relative entropy between output distributions of the DMC, and C is the Shannon capacity of the channel. We show that in this asymptotic regime, separate source-channel coding is, in fact, optimal.

A coupling of two distributions PXand PYis a joint distribution PXYwith marginal distributions equal to PXand PY. Given marginals PXand PYand a real-valued function f of the joint distribution PXY, what is its minimum over all couplings PXYof PXand PY? We study the asymptotics of such coupling problems with different f's and with X and Y replaced by Xn= (X1, . . . , Xn) and Yn= (Y1, . . . , Yn) where Xiand Yiare i.i.d. copies of random variables X and Y with distributions PXand PY, respectively. These include the maximal coupling, minimum distance coupling, maximal guessing coupling, and minimum entropy coupling problems. We characterize the limiting values of these coupling problems as n tends to infinity. We show that they typically converge at least exponentially fast to their limits. Moreover, for the problems of maximal coupling and minimum excess-distance probability coupling, we also characterize (or bound) the optimal convergence rates (exponents). Furthermore, for the maximal guessing coupling problem, we show that it is equivalent to the distribution approximation problem. Therefore, some existing results for the latter problem can be used to derive the asymptotics of the maximal guessing coupling problem. We also study the asymptotics of the maximal guessing coupling problem for two general sources and a generalization of this problem, named the maximal guessing coupling through a channel problem. We apply the preceding results to several new information-theoretic problems, including exact intrinsic randomness, exact resolvability, channel capacity with input distribution constraint, and perfect stealth and secrecy communication.

The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.

The random variable simulation problem consists in using a k-dimensional i.i.d. random vector Xkwith distribution PXkto simulate an n-dimensional i.i.d. random vector Ynso that its distribution is approximately QYn. In contrast to previous works, in this paper, we consider the standard Rényi divergence and two variants of all orders to measure the level of approximation. These two variants are the max-Rényi divergence Dαmax(P, Q) and the sum-Rényi divergence Du (P, Q). When α = ∞, these two measures are strong because for any ϵ ≥ 0, D∞max(P, Q) ≤ ϵ or D∞+(P, Q) ≤ ϵ implies e-ϵ≤ (P(x)/Q(x))ϵfor all x. Under these Rényi divergence measures, we characterize the asymptotics of normalized divergences as well as the Rényi conversion rates. The latter is defined as the supremum of n/k such that the Rényi divergences vanish asymptotically. Our results show that, when the Rényi parameter is in the interval (0, 1), the Rényi conversion rates equal the ratio of the Shannon entropies H (PX)/H (QY), which is consistent with traditional results in which the total variation measure was adopted. When the Rényi parameter is in the interval (1, ∞), the Rényi conversion rates are, in general, smaller than H (PX)/H (QY). When specialized to the case in which either PXor QYis uniform, the simulation problem reduces to the source resolvability and intrinsic randomness problems. The preceding results are used to characterize the asymptotics of Rényi divergences and the Rényi conversion rates for these two cases.

We consider a joint source channel coding (JSCC) problem in which we desire to transmit an arbitrary memoryless source over an arbitrary additive channel. We propose a mismatched coding architecture that consists of Gaussian codebooks for both the source reproduction sequences and channel codewords. The natural nearest neighbor encoder and decoder, however, need to be judiciously modified to obtain the highest communication rates at finite blocklength. In particular, we consider an unequal error protection scheme in which all sources are partitioned into disjoint power-type classes. We also regularize the nearest neighbor decoder so that an appropriate measure of the size of each power type class is taken into account in the decoding strategy. For such an architecture, we derive ensemble-tight second-order and moderate deviations results. Our first-order (optimal bandwidth expansion ratio) result generalizes the seminal results by Lapidoth (1996 and 1997). The dispersion of our JSCC scheme is a linear combination of the mismatched dispersions for the channel coding saddle-point problem by Scarlett, Tan, and Durisi (2017) and the rate-distortion saddle-point problem by the present authors, thus also generalizing these results.

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth's analysis in several directions in this paper. First, we consider refined asymptotics. In particular, when the source is stationary and memoryless, we establish the second-order, moderate, and large deviation asymptotics of the problem. Second, by random Gaussian codebook, Lapidoth referred to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an n -dimensional sphere. To be more precise, we term this as a spherical codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We derive the second-order, moderate, and large deviation asymptotics when i.i.d. Gaussian codebooks are employed. In contrast to the recent work on the channel coding counterpart by Scarlett, Tan, and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian codebooks are identical. The ensemble excess-distortion exponents for both spherical and i.i.d. Gaussian codebooks are established for all rates. Furthermore, we show that the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than its spherical counterpart for any rate greater than the ensemble rate-distortion function derived by Lapidoth.

In this paper, we demonstrate a new IMU-based wearable system (dubbed MANA or Mobility ANAlytics) for measuring gait in a clinical setting. The design process and choices that were made to ensure that the technology was invisible and accessible are described. We collect a rich and diverse dataset of walking data from sixty participants, including forty people with Parkinson's Disease (PD). The system is then validated in a clinical setting with this dataset. We present novel and innovative algorithms to measure common gait parameters. The system is able to estimate these gait parameters with high accuracy, with a mean absolute error of 4.0 cm for stride length and 2.6 cm for step length, outperforming all state-of-the-art methods that included data from people with PD.

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth's analysis in several directions in this paper. Firstly, we consider second-order asymptotics. In particular, when the source is stationary and memoryless, we establish ensemble tight second-order coding rate for the problem. Secondly, by “random Gaussian codebook”, Lapidoth refers to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an n-dimensional sphere. To be more precise, we term this as a spherical Gaussian codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We also derive the second-order asymptotics when i.i.d. Gaussian codebooks are employed. Interestingly, in contrast to the recent work on the channel coding counterpart by Scarlett, Tan and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian code books are identical for the rate-distortion saddle-point problem.

We consider a universal joint source channel coding (JSCC) scheme to transmit an arbitrary memoryless source over an arbitrary additive channel. We adopt an architecture that consists of Gaussian codebooks for both the source reproduction sequences and channel codewords. The natural minimum Euclidean distance encoder and decoder, however, need to be judiciously modified to ensure universality as well as to obtain the best (highest) possible communication rates. In particular, we consider the analogue of an unequal error (or message) protection scheme in which all sources are partitioned into disjoint power type classes. We also regularize the nearest neighbor decoder so an appropriate measure of the size of each power type class is taken into account in the decoding strategy. For such an architecture, we derive ensemble tight second-order asymptotics.

We study a generalized version of Wyner's common information problem (also coined the distributed sources simulation problem). The original common information problem is to characterize the minimum rate of the common input to independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves changing the distance measure to the unnormalized and normalized Renyi divergences of order α = 1+s ∈ [0,2]. We show that the minimum rate needed to ensure the Renyi divergences between the distribution induced by a code and the target distribution vanishes remains the same as the one in Wyner's setting, except when the order α = 1+s=0. This implies that Wyner's common information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to establish the above results, the exponentially strong converse for the common information problem under the total variation distance measure is established.

We derive exact (ensemble-tight) error and erasure exponents for the asymmetric broadcast channel given a random superposition codebook. We consider Forney's optimal decoder for both messages and the message pair for the receiver that decodes both messages. We prove that the optimal decoder designed to decode the pair of messages achieves the optimal tradeoff between the total and undetected exponents associated with the optimal decoder for the private message. We propose convex optimization procedures to evaluate the exponents. Numerical examples are presented to illustrate the results.

ELIGIBLE FOR THE STUDENT PAPER AWARD. The learning of mixture models can be viewed as a clustering problem. Indeed, given data samples independently generated from a mixture of distributions, we often would like to find the correct target clustering of the samples according to which component distribution they were generated from. For a clustering problem, practitioners often choose to use the simple k-means algorithm. k-means attempts to find an optimal clustering which minimizes the sum-of-squares distance between each point and its cluster center. We consider fundamental (i.e., information-theoretic) limits of the solutions (clusterings) obtained by optimizing the sum-of-squares distance. In particular, we provide sufficient conditions for the closeness of any optimal clustering and the correct target clustering assuming that the data samples are generated from a mixture of spherical Gaussian distributions. We also generalize our results to log-concave distributions. Moreover, we show that under similar or even weaker conditions on the mixture model, any optimal clustering for the samples with reduced dimensionality is also close to the correct target clustering. These results provide intuition for the informativeness of k-means (with and without dimensionality reduction) as an algorithm for learning mixture models.

We consider transmission of discrete memoryless sources (DMSes) across discrete memoryless channels (DMCs) using variable-length lossy source-channel codes with feedback. The reliability function (optimum error exponent) is shown to be equal to max{0, B(1-R(D)/C)}, where R(D) is the ratedistortion function of the source, B is the maximum relative entropy between output distributions of the DMC, and C is the Shannon capacity of the channel. We show that, in this setting and in this asymptotic regime, separate source-channel coding is, in fact, optimal.

The zero-error capacity of state-dependent channels with noiseless feedback is determined, under the assumption that the transmitter and the receiver are allowed to use variable-length coding schemes. Various cases are analyzed, with the employed coding schemes having either bounded or unbounded codeword lengths and with state information revealed to the encoder and/or decoder in a strictly causal, causal, or noncausal manner. In each of these settings, necessary and sufficient conditions for positivity of the zero-error capacity are obtained and it is shown that, whenever the zero-error capacity is positive, it equals the conventional vanishing-error capacity. A comparison of the results with the recently solved fixed-length case is given.

We revisit the hypothesis testing with communication constraints problem, also called distributed hypothesis testing, from the viewpoint of privacy. Instead of observing the raw data directly, the transmitter observes a sanitized or randomized version of it. We impose an upper bound on the mutual information between the raw and randomized data. Under this scenario, the decoder, which is also provided with side information, is required to make a decision on whether the null or alternative hypothesis is in effect. First, we provide a general lower bound on the type-II exponent for arbitrary hypotheses, privacy mechanism, rates, and leakage parameters. Second, we consider the testing against independence scenario in which the distribution under the alternative hypothesis is the product of the marginals of the distribution under the null hypothesis. In this setup, we show that the exponent is known exactly and the strong converse property holds. Finally, the trade-offs between the exponent, compression rate, and leakage parameter are illustrated through a binary example.

We consider a covert communication scenario where a transmitter wishes to communicate simultaneously to two legitimate receivers while ensuring that the communication is not detected by an adversary, the warden. The legitimate receivers and the adversary observe the transmission from the transmitter via a three-user discrete or Gaussian memoryless broadcast channel. We focus on the case where the “no-input” symbol is not redundant, i.e., the output distribution at the warden induced by the no-input symbol is not a mixture of the output distributions induced by other input symbols, so that the covert communication is governed by the square root law, i.e., at most Θ(√n) bits can be transmitted over n channel uses. We show that for such a setting, a simple time-division strategy achieves the optimal throughputs for a class of broadcast channels. Our result implies that a code that uses two separate optimal point-to-point codes each designed for the constituent channels and each used for a fraction of the time is optimal in the sense that it achieves the best constants of the √n-scaling for the throughputs. Our proof strategy combines several elements in the network information theory literature, including concave envelope representations of the capacity regions of broadcast channels and El Gamal's outer bound for more capable broadcast channels.

Hypothesis testing is a statistical inference framework for determining the true distribution among a set of possible distributions for a given data set. Privacy restrictions may require the curator of the data or the respondents themselves to share data with the test only after applying a randomizing privacy mechanism. This work considers mutual information (MI) as the privacy metric for measuring leakage. In addition, motivated by the Chernoff-Stein lemma, the relative entropy between pairs of distributions of the output (generated by the privacy mechanism) is chosen as the utility metric. For these metrics, the goal is to find the optimal privacy-utility tradeoff (PUT) and the corresponding optimal privacy mechanism for both binary and m-ary hypothesis testing. Focusing on the high privacy regime, Euclidean information-theoretic approximations of the binary and m-ary PUT problems are developed. The solutions for the approximation problems clarify that an MI-based privacy metric preserves the privacy of the source symbols in inverse proportion to their likelihoods.

This paper investigates the achievable rates of an additive white Gaussian noise energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed random variables. The blocks have length L , which can be interpreted as the coherence time of the energy-arrival process. If L is a constant or grows sublinearly in the blocklength n , we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability ε. The first-order term is known as the ε-capacity. In addition, we obtain lower and upper bounds on the second-order term in the asymptotic expansion, which reveal that the second order term is proportional to -(L/n)1/2for any ε less than 1/2. The lower bound is obtained through analyzing the save-and-transmit strategy. If L grows linearly in n, we obtain lower and upper bounds on the ε-capacity, which coincide whenever the cumulative distribution function of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks.

Given a sufficient statistic for a parametric family of distributions, one can estimate the parameter without access to the data. However, the memory or code size for storing the sufficient statistic may nonetheless still be prohibitive. Indeed, for n independent samples drawn from a k-nomial distribution with d = k - 1 degrees of freedom, the length of the code scales as d log n + O(1). In many applications, we may not have a useful notion of sufficient statistics (e.g., when the parametric family is not an exponential family), and we may also not need to reconstruct the generating distribution exactly. By adopting a Shannon-theoretic approach in which we allow a small error in estimating the generating distribution, we construct various approximate sufficient statistics and show that the code length can be reduced to (d/2) log n + O(1). We consider errors measured according to the relative entropy and variational distance criteria. For the code constructions, we leverage Rissanen's minimum description length principle, which yields a non-vanishing error measured according to the relative entropy. For the converse parts, we use Clarke and Barron's formula for the relative entropy of a parameterized distribution and the corresponding mixture distribution. However, this method only yields a weak converse for the variational distance. We develop new techniques to achieve vanishing errors, and we also prove strong converses. The latter means that even if the code is allowed to have a nonvanishing error, its length must still be at least (d/2) log n.

Motivated by communication channels in which the transmitted sequences are subjected to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors are derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any error radius and alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases.

We analyze the asymptotics of the normalized remaining uncertainty of a source when a compressed or hashed version of it and correlated side information is observed. For this system, commonly known as Slepian-Wolf source coding, we establish the optimal (minimum) rate of compression of the source to ensure that the remaining uncertainties vanish. We also study the exponential rate of decay of the remaining uncertainty to zero when the rate is above the optimal rate of compression. In this paper, we consider various classes of random universal hash functions. Instead of measuring remaining uncertainties using traditional Shannon information measures, we do so using two forms of the conditional Rényi entropy. Among other techniques, we employ new one-shot bounds and the moments of type class enumerator method (see Merhav) for these evaluations. We show that these asymptotic results are generalizations of the strong converse exponent and the error exponent of the Slepian-Wolf problem under maximum a posteriori decoding.

We characterize the fundamental limits of transmission of information over a Gaussian multiple access channel (MAC) with the use of variable-length feedback codes and under a non-vanishing error probability formalism. We develop new achievability and converse techniques to handle the continuous nature of the channel and the presence of expected power constraints. We establish the ε-capacity regions and bounds on the second-order asymptotics of the Gaussian MAC with variable-length feedback with termination codes and stopfeedback codes. We show that the former outperforms the latter significantly. Due to the multi-terminal nature of the channel model, we leverage tools from renewal theory developed by Lai and Siegmund to bound the asymptotic behavior of the maximum of a finite number of stopping times.

We study a generalized version of Wyner's common information problem (also coined the distributed source simulation problem). The original common information problem consists in understanding the minimum rate of the common input to independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves changing the distance measure to the unnormalized and normalized Rényi divergences of order α = 1 + s ∈ [0, 2]. We show that the minimum rate needed to ensure the Rényi divergences between the distribution induced by a code and the target distribution vanishes remains the same as the one in Wyner's setting, except when the order α = 1+s = 0. This implies that Wyner's common information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to the establish the above results, the exponential strong converse for the common information problem under the total variation distance measure is established.

Motivated by streaming multi-view video coding and wireless sensor networks, we consider the problem of blockwise streaming compression of a pair of correlated sources, which we term streaming Slepian-Wolf coding. We study the moderate deviations regime in which the rate pairs of a sequence of codes converge, along a straight line, to various points on the boundary of the Slepian-Wolf region at a speed slower than the inverse square root of the blocklength n, while the error probability decays subexponentially fast in n. Our main result focuses on the directions of approaches to corner points of the Slepian-Wolf region. It states that for each correlated source and all corner points, there exists a non-empty subset of directions of approaches, such that the moderate deviations constant (the constant of proportionality for the subexponential decay of the error probability) is enhanced (over the non-streaming case) by at least a factor of T, the block delay of decoding source block pairs. We specialize our main result to the setting of streaming lossless source coding and generalize this result to the setting, where we have different delay requirements for each of the two source blocks. The proof of our main result involves the use of various analytical tools and amalgamates several ideas from the recent information-theoretic streaming literature. We adapt the so-called truncated memory encoding idea from Draper and Khisti (2011) and Lee, Tan, and Khisti (2016) to ensure that the effect of error accumulation is nullified in the limit of large block lengths. We also adapt the use of the so-called minimum weighted empirical suffix entropy decoder, which was used by Draper, Chang, and Sahai (2014) to derive achievable error exponents for symbolwise streaming Slepian-Wolf coding.

We revisit the high-dimensional content identification with lossy recovery problem (Tuncel and Gündüz, 2014) and establish an exponential strong converse theorem. As a corollary of the exponential strong converse theorem, we derive an upper bound on the joint identification-error and excess-distortion exponent for the problem. Our main results can be specialized to the biometrical identification problem (Willems, 2003) and the content identification problem (Tuncel, 2009) since these two problems are both special cases of the content identification with lossy recovery problem. We leverage the information spectrum method introduced by Oohama and adapt the strong converse techniques therein to be applicable to the problem at hand.

We develop a unified and systematic framework for performing online nonnegative matrix factorization under a wide variety of important divergences. The online nature of our algorithms makes them particularly amenable to large-scale data. We prove that the sequence of learned dictionaries converges almost surely to the set of critical points of the expected loss function. Experimental results demonstrate the computational efficiency and outstanding performances of our algorithms on several real-life applications, including topic modeling, document clustering and foreground-background separation.

We propose a geometric assumption on nonnegative data matrices such that under this assumption, we are able to provide upper bounds (both deterministic and probabilistic) on the relative error of nonnegative matrix factorization (NMF). The algorithm we propose first uses the geometric assumption to obtain an exact clustering of the columns of the data matrix; subsequently, it employs several rank-one NMFs to obtain the final decomposition. Furthermore, when combined with the classical alternating nonnegative least-squares algorithm, we show on synthetic examples that our proposed algorithm outperforms the standard algorithm based on multiplicative updates.

The multiplicative update (MU) algorithm has been used extensively to estimate the basis and coefficient matrices in nonnegative matrix factorization (NMF) problems under a wide range of divergences and regularizations. However, theoretical convergence guarantees have only been derived for a few special divergences. In this work, we provide a conceptually simple, self-contained, and unified proof for the convergence of the MU algorithm applied on NMF with a wide range of divergences and regularizations. Our result shows the sequence of iterates (i.e., pairs of basis and coefficient matrices) produced by the MU algorithm converges to the set of stationary points of the NMF (optimization) problem. Our proof strategy has the potential to open up new avenues for analyzing similar problems.

This paper is motivated by the error-control problem in communication channels in which the transmitted sequences are subjected to random permutations, in addition to being impaired with insertions, deletions, substitutions, and erasures of symbols. Bounds on the size of optimal codes in this setting are derived, and their asymptotic behavior examined in the fixed-minimum-distance regime. A family of codes correcting these types of errors is described and is shown to be asymptotically optimal for some sets of parameters. The corresponding error-detection problem is also analyzed.

We analyse families of codes for classical data transmission over quantum channels that have both a vanishing probability of error and a code rate approaching capacity as the code length increases. To characterise the fundamental tradeoff between decoding error, code rate and code length for such codes we introduce a quantum generalisation of the moderate deviation analysis proposed by Altŭg and Wagner as well as Polyanskiy and Verdú. We derive such a tradeoff for classical-quantum (as well as image-additive) channels in terms of the channel capacity and the channel dispersion, giving further evidence that the latter quantity characterises the necessary backoff from capacity when transmitting finite blocks of classical data. To derive these results we also study asymmetric binary quantum hypothesis testing in the moderate deviations regime. Due to the central importance of the latter task, we expect that our techniques will find further applications in the analysis of other quantum information processing tasks.

This paper considers a multimessage network where each node may send a message to any other node in the network. Under the discrete memoryless model, we prove the strong converse theorem for any network with tight cut-set bound, i.e., whose cut-set bound is achievable. Our result implies that for any network with tight cut-set bound and any fixed rate vector that resides outside the capacity region, the average error probabilities of any sequence of length-n codes operated at the rate vector must tend to 1 as n grows. The proof is based on the method of types. The proof techniques are inspired by the work of Csiszar and Korner in 1982 which fully characterized the reliability function of any discrete memoryless channel (DMC) with feedback for rates above capacity.

This paper investigates the achievable rates of an additive white Gaussian noise (AWGN) energy-harvesting (EH) channel with an infinite battery under the assumption that the error probabilities do not vanish as the blocklength increases. The EH process is characterized by a sequence of blocks of harvested energy. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed (i.i.d.) random variables. The blocks have length L, which can be interpreted as the coherence time of the energy arrival process. If L is a constant or grows sublinearly in the blocklength n, we fully characterize the first-order coding rate. In addition, we obtain lower and upper bounds on the second-order coding rate, which are proportional to −√L/n for any fixed error probability < 1 /2. If L grows linearly in n, we obtain lower and upper bounds on the first-order coding rate, which coincide whenever the EH random variable is continuous. Our results suggest that correlation in the energy-arrival process decreases the effective blocklength by a factor of L.

Given a sufficient statistic for a parametric family of distributions, one can estimate the parameter without access to the data itself. However, the memory or code size for storing the sufficient statistic may nonetheless still be prohibitive. Indeed, for n independent data samples drawn from a k-nomial distribution with d = k − 1 degrees of freedom, the length of the code scales as d log n + O(1). In many applications though, we may not have a useful notion of sufficient statistics and also may not need to reconstruct the generating distribution exactly. By adopting a Shannon-theoretic approach in which we consider allow a small error in estimating the generating distribution, we construct various notions of approximate sufficient statistics and show that the code length can be reduced to d/2 logn + O(1). We consider errors measured according to the relative entropy and variational distance criteria. For the code construction parts, we leverage Rissanen's minimum description length (MDL) principle, which yields a non-vanishing error measured using the relative entropy. For the converse parts, we use Clarke and Barron's asymptotic expansion for the relative entropy of a parametrized distribution and the corresponding mixture distribution. The limitation of this method is that only a weak converse for the variational distance can be shown. We develop new techniques to achieve vanishing errors and we also prove strong converses for all our statements. The latter means that even if the code is allowed to have a non-vanishing error, its length must still be at least d/2 log n.

In this paper, a streaming transmission setup is considered, where an encoder observes a new message in the beginning of each block and a decoder sequentially decodes each message after a delay of T blocks. In this streaming setup, the fundamental interplay between the coding rate, the error probability, and the blocklength in the moderate deviations regime is studied. For output symmetric channels, the moderate deviations constant is shown to improve over the block coding or non-streaming setup by exactly a factor of T for a certain range of moderate deviations scalings. For the converse proof, a more powerful decoder, to which some extra information is fedforward is assumed. The error probability is bounded first for an auxiliary channel and this result is translated back to the original channel by using a newly developed change-of-measure lemma, where the speed of decay of the remainder term in the exponent is carefully characterized. For the achievability proof, a known coding technique that involves a joint encoding and decoding of fresh and past messages is applied with some manipulations in the error analysis.

The problem of publishing privacy-guaranteed data for hypothesis testing is studied using the maximal leakage (ML) as a metric for privacy and the type-II error exponent as the utility metric. The optimal mechanism (random mapping) that maximizes utility for a bounded leakage guarantee is determined for the entire leakage range for binary datasets. For non-binary datasets, approximations in the high privacy and high utility regimes are developed. The results show that, for any desired leakage level, maximizing utility forces the ML privacy mechanism to reveal partial to complete knowledge about a subset of the source alphabet. The results developed on maximizing a convex function over a polytope may also of an independent interest.

We derive upper and lower bounds on the reliability function for the discrete memoryless broadcast channel with common message and variable-length feedback. We show that the bounds are tight when the broadcast channel is stochastically degraded. We adapt and supplement new ideas to Yamamoto and Itoh's two-phase coding scheme for the direct part and Burnashev's proof technique for the converse part.

We characterize the information-theoretic limits of the Gaussian multiple access channel (MAC) when variable-length stop-feedback is available at the encoder and a non-vanishing error probability is permitted. Due to the continuous nature of the channel and the presence of expected power constraints, we need to develop new achievability and converse techniques. Due to the multi-terminal nature of the channel model, we are faced with the need to bound the asymptotic behavior of the expected value of the maximum of several stopping times. We do so by leveraging tools from renewal theory developed by Gut (1974) and Lai and Siegmund (1979).

This work investigates the limits of communication over a noisy channel that wears out, in the sense of signal-dependent catastrophic failure. In particular, we consider a channel that starts as a memoryless binary-input channel and when the number of transmitted ones causes a sufficient amount of damage, the channel ceases to convey signals. We restrict attention to constant composition codes. Since infinite blocklength codes will always wear out the channel for any finite threshold of failure and therefore convey no information, we analyze the performance of finite blocklength codes to determine the maximum expected transmission volume at a given level of average error probability. We show that this maximization problem has a recursive form and can be solved by dynamic programming. A discussion of damage state feedback in channels that wear out is also provided. Numerical results show that a sequence of block codes is preferred to a single block code for streaming sources.

In this paper, we revisit the content identification problem with lossy recovery (Tuncel and Gündüz, 2014) and establish the exponential strong converse theorem for the problem. Further, we derive an upper bound on the joint excess-distortion and error exponent for the problem.

Motivated by streaming multi-view video coding, we consider the problem of blockwise streaming compression of a pair of correlated sources, which we term streaming Slepian-Wolf coding. We study the moderate deviations regime in which the rate pairs of a sequence of codes converges, along a straight line, to various points on the boundary of the Slepian-Wolf region at a speed slower than the inverse square root of the blocklength n, while the error probability decays subexponentially fast in n. Our main result focuses on directions of approaches to corner points of the Slepian-Wolf region. It states that for each correlated source and all corner points, there exists a non-empty subset of directions of approaches such that the moderate deviations constant (the constant of proportionality for the subexponential decay of the error probability) is enhanced (over the non-streaming case) by at least a factor of T, the block delay of decoding symbol pairs. Further, we specialize our main result to the setting of lossless streaming source coding.

We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.

In this paper, asymptotic expansions for the two-user Gaussian multiple access channel with degraded message sets under long-term power constraints and non-vanishing error probabilities ε ∊ [0,1) are studied. The ε-capacity region is established and bounds on the second-order terms are derived.

In this paper, an exact distance spectrum formula for the largest minimum Hamming distance of finite-length binary block codes is presented. The exact formula indicates that the largest minimum distance of finite-length block codes can be fully characterized by the information spectrum of the Hamming distance between two independent and identically distributed (i.i.d.) random codewords. The distance property of finite-length block codes is then connected to the distance spectrum. A side result of this work is a new lower bound to the largest minimum distance of finite-length block codes. Numerical examinations show that the new lower bound improves the finite-length Gilbert-Varshamov lower bound and can reach the minimum distance of existing finite-length block codes.

This paper investigates the asymptotic expansion of the maximum coding rate of a parallel Gaussian channel with feedback under the following setting: A peak power constraint is imposed on every transmitted codeword, and the average error probabilities of decoding the transmitted message are non-vanishing as the blocklength increases. This paper proves an upper bound on the first-and second-order asymptotics. Combined with existing achievability results, our result implies that the presence of feedback does not improve the first-and second-order asymptotics.

We define and study the error exponent of covert communications over binary-input Discrete Memoryless Channels (DMCs). Our main result consists of upper and lower bounds for the exponent, which match in a regime that we explicitly characterize. While our proofs follow standard techniques, the vanishing rate regime inherent to covert communications and the low-weight of codewords introduces specific technical challenges. In particular, the lower bound of the error exponent follows from a non-standard constant-composition ensemble instead of an independent and identically distributed (i.i.d.) ensemble, and the upper bound requires a careful treatment that does not appear in the traditional analysis of error exponent.

We investigate the end-to-end delay of multiple-unicast wireless networks. In contrast to previous works where the end-to-end delay is measured by the queuing delay, in this work we measure the delay by the total blocklength of the communication scheme. As the capacity characterization of multiple-unicast networks is open, we consider random wireless networks (the Gupta-Kumar model) and investigate the end-to-end delay scaling law with respect to the number of nodes. The end-to-end delay of delivering a file depends on the file size as well as the throughput. Our main contribution is the characterization of the end-to-end delay scaling law of the multihopping scheme, which depends on the file size. Our main finding is that if the file size is sufficiently large, the end-to-end delay scaling law is proportional to it. While this is expected, if the file size is not large enough, the end-to-end delay scaling law becomes independent of it. In particular, in a network with 2 k randomly one-to-one paired users and area k and a source with F (k) bits to send, we show that the delay is ω (√kF (k)) if F (k) = Ω(√klog k), while it is ω(k log k) if F (k) = o(√klog k). Our result is derived by studying the multihopping scheme for large random wireless networks. Using ideas from moderate deviations theory and finite length bounds in the literature, we derive a lower bound on the required blocklength for the network.

A $ B_h $ set (or Sidon set of order $ h $) in an Abelian group $ G $ is any subset $ \{b_0, b_1, \ldots,b_{n}\} $ of $ G $ with the property that all the sums $ b_{i_1} + \cdots + b_{i_h} $ are different up to the order of the summands. Let $ \phi(h,n) $ denote the order of the smallest Abelian group containing a $ B_h $ set of cardinality $ n + 1 $. It is shown that ${\scriptstyle\lim_{h \to \infty} \frac{ \phi(h,n) }{ h^n } = \frac{1}{n! \ \delta_{\sc l}(\triangle^n)}},$ where $ \delta_{\sc l}(\triangle^n) $ is the lattice packing density of an $ n $-simplex in Euclidean space. This determines the asymptotics exactly in cases where this density is known ($ n \leq 3 $) and gives improved bounds on $ \phi(h,n) $ in the remaining cases. The corresponding geometric characterization of bases of order $ h $ in finite Abelian groups in terms of lattice coverings by simplices is also given.

This paper revisits the Gaussian degraded relay channel, where the link that carries information from the source to the destination is a physically degraded version of the link that carries information from the source to the relay. The source and the relay are subject to expected power constraints. The ε-capacity of the channel is characterized and it is strictly larger than the capacity for any ε > 0, which implies that the channel does not possess the strong converse property. The proof of the achievability part is based on several key ideas: block Markov coding, which is used in the classical decode-forward strategy, power control for Gaussian channels under expected power constraints, and a careful scaling between the block size and the total number of block uses. The converse part is proved by first establishing two non-asymptotic lower bounds on the error probability, which are derived from the type-II errors of some binary hypothesis tests. Subsequently, each lower bound is simplified by conditioning on an event related to the power of some linear combination of the codewords transmitted by the source and the relay. Lower and upper bounds on the second-order term of the optimal coding rate are also obtained.

This paper investigates the asymptotic expansion for the maximum rate of fixed-length codes over a parallel Gaussian channel with feedback under the following setting: a peak power constraint is imposed on every transmitted codeword, and the average error probabilities of decoding the transmitted message are non-vanishing as the blocklength increases. The main contribution of this paper is a self-contained proof of an upper bound on the first- and second-order asymptotics of the parallel Gaussian channel with feedback. The proof techniques involve developing an information spectrum bound followed by using Curtiss' theorem to show that a sum of dependent random variables associated with the information spectrum bound converges in distribution to a sum of independent random variables, thus facilitating the use of the usual central limit theorem. Combined with existing achievability results, our result implies that the presence of feedback does not improve the first- and second-order asymptotics.

We evaluate the asymptotics of equivocations, their exponents as well as their second-order coding rates under various Rényi information measures. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source when the number of copies of the sources is large. Unlike previous works that use Shannon information measures to quantify randomness, information, or uniformity, we define our security measures in terms of a more general class of information measures-the Rényi information measures and their Gallager-type counterparts. A special case of these Rényi information measure is the class of Shannon information measures. We prove tight asymptotic results for the security measures and their exponential rates of decay. We also prove bounds on the second-order asymptotics and show that these bounds match when the magnitudes of the second-order coding rates are large. We do so by establishing new classes non-asymptotic bounds on the equivocation and evaluating these bounds using various probabilistic limit theorems asymptotically.

The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zeroerror capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an n-cell register, where each cell is either empty or contains a particle of one of P possible types and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a P-ary alphabet through a queuing system with an infinite buffer and a first-in-first-out service procedure and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems.

We study the top-K ranking problem where the goal is to recover the set of top-K ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populations follow the standard Bradley-Terry-Luce model (i.e., the chance of item i beating item j is proportional to the relative score of item i to item j), while in the other population, the corresponding chance is inversely proportional to the relative score. When the relative size of the two populations is known, we characterize the minimax limit on the sample size required (up to a constant) for reliably identifying the top-K items, and demonstrate how it scales with the relative size. Moreover, by leveraging a tensor decomposition method for disambiguating mixture distributions, we extend our result to the more realistic scenario, in which the relative population size is unknown, thus establishing an upper bound on the fundamental limit of the sample size for recovering the top-K set.

In this paper, we consider single-and multi-user Gaussian channels with feedback under expected power constraints and with non-vanishing error probabilities. In the first of two contributions, we study asymptotic expansions for the additive white Gaussian noise (AWGN) channel with feedback under the average error probability formalism. By drawing ideas from Gallager and Nakiboǧlu's work for the direct part and the meta-converse for the converse part, we establish the e-capacity and show that it depends on e in general and so the strong converse fails to hold. Furthermore, we provide bounds on the second-order term in the asymptotic expansion. We show that for any positive integer L, the second-order term is bounded between a term proportional to - ln(L) n (where ln(L)(·) is the L-fold nested logarithm function) and a term proportional to +(n ln n)1/2, where n is the blocklength. The lower bound on the second-order term shows that feedback does provide an improvement in the maximal achievable rate over the case where no feedback is available. In our second contribution, we establish the e-capacity region for the AWGN multiple access channel with feedback under the expected power constraint by combining ideas from hypothesis testing, information spectrum analysis, Ozarow's coding scheme, and power control.

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function), and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe's work. In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú. The converse part uses a perturbation argument by Gu and Effros in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses two novel elements: 1) a generalization of various type covering lemmas and 2) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma, and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviations theorem to probabilities defined in terms of information spectrum quantities.

We derive the optimal second-order coding region and moderate deviations constant for successive refinement source coding with a joint excess-distortion probability constraint. We consider two scenarios: 1) a discrete memoryless source (DMS) and arbitrary distortion measures at the decoders and 2) a Gaussian memoryless source (GMS) and quadratic distortion measures at the decoders. For a DMS with arbitrary distortion measures, we prove an achievable second-order coding region, using type covering lemmas by Kanlis and Narayan and by No, Ingber, and Weissman. We prove the converse using the perturbation approach by Gu and Effros. When the DMS is successively refinable, the expressions for the second-order coding region and the moderate deviations constant are simplified and easily computable. For this case, we also obtain new insights on the second-order behavior compared with the scenario where separate excess-distortion proabilities are considered. For example, we describe a DMS, for which the optimal second-order region transitions from being characterizable by a bivariate Gaussian to a univariate Gaussian, as the distortion levels are varied. We then consider a GMS with quadratic distortion measures. To prove the direct part, we make use of the sphere covering theorem by Verger-Gaugry, together with appropriately-defined Gaussian type classes. To prove the converse, we generalize Kostina and Verdú's one-shot converse bound for point-to-point lossy source coding. We remark that this proof is applicable to general successively refinable sources. In the proofs of the moderate deviations results for both scenarios, we follow a strategy similar to that for the second-order asymptotics and use the moderate deviations principle.

We propose an optimization framework for performing online Non-negative Matrix Factorization (NMF) in the presence of outliers, based on l\ regularization and stochastic approximation. Due to the online nature of the algorithm, the proposed method has extremely low computational and storage complexity and is thus particularly applicable in this age of BigData. Furthermore, our algorithm shows promising performance in dealing with outliers, which previous online NMF algorithms fail to cope with. Convergence analysis shows the dictionary learned by our algorithm converges to that learned by its batch counterpart almost surely, as data size tends to infinity. We show numerically on a range of face datasets that our algorithm is superior to the state-of-the-art NMF algorithms in terms of running time, basis representations and reconstruction of original images. We also observe that our algorithm performs well even when the density of outliers reaches 40%. We provide explanations behind this seemingly surprising result.

We prove that 2-user Gaussian broadcast channels admit the strong converse. This implies that for every sequence of block codes with an asymptotic maximal error probability smaller than one, the limit points of the corresponding sequence of rate pairs must lie within the capacity region derived by Cover and Bergmans. The main mathematical tool required for our analysis is a logarithmic Sobolev inequality known as the Gaussian Poincaré inequality.

This paper investigates the information-theoretic limits of the additive white Gaussian noise (AWGN) energy-harvesting (EH) channel in the finite blocklength regime. The EH process is characterized by a sequence of i.i.d. random variables with finite variances. We use the save-and-transmit strategy proposed by Ozel and Ulukus (2012) together with Shannon's non-asymptotic achievability bound to obtain a lower bound on the achievable rate for the AWGN EH channel. The first-order term of the lower bound on the achievable rate is equal to C and the second-order (backoff from capacity) term is proportional to equation, where n denotes the blocklength and C denotes the capacity of the EH channel, which is the same as the capacity without the EH constraints. The constant of proportionality of the backoff term is found and qualitative interpretations are provided.

We study the asymptotics of the remaining uncertainty of a source when a compressed version of it and correlated side-information is observed. Instead of measuring the remaining uncertainty using Shannon measures, we do so using two forms of the conditional Rényi entropy. We show that these asymptotic results are generalizations of the strong converse exponent and the error exponent of Slepian-Wolf source coding.

We consider streaming data transmission over a discrete memoryless channel. A new message is given to the encoder at the beginning of each block and the decoder decodes each message sequentially, after a delay of T blocks. In this streaming setup, we study the fundamental interplay between the rate and error probability in the central limit and moderate deviations regimes and show that: 1) in the moderate deviations regime, the moderate deviations constant improves over the block coding or non-streaming setup by a factor of T and 2) in the central limit regime, the second-order coding rate improves by a factor of approximately √T for a wide range of channel parameters. For both the regimes, we propose coding techniques that incorporate a joint encoding of fresh and previous messages. In particular, for the central limit regime, we propose a coding technique with truncated memory to ensure that a summation of constants, which arises as a result of applications of the central limit theorem, does not diverge in the error analysis. Furthermore, we explore interesting variants of the basic streaming setup in the moderate deviations regime. We first consider a scenario with an erasure option at the decoder, i.e., the decoder can output an erasure symbol instead of a message estimate, and show that both the exponents of the total error and the undetected error probabilities improve by factors of T. Next, by utilizing the erasure option, we show that the exponent of the total error probability can be improved to that of the undetected error probability (in the order sense) at the expense of a variable decoding delay.

We study the second-order asymptotics of information transmission using random Gaussian codebooks and nearest neighbor decoding over a power-limited stationary memoryless additive non-Gaussian noise channel. We show that the dispersion term depends on the non-Gaussian noise only through its second and fourth moments, thus complementing the capacity result (Lapidoth, 1996), which depends only on the second moment. Furthermore, we characterize the second-order asymptotics of point-to-point codes over K-sender interference networks with non-Gaussian additive noise. Specifically, we assume that each user's codebook is Gaussian and that NN decoding is employed, i.e., that interference from the K -1 unintended users (Gaussian interfering signals) is treated as noise at each decoder. We show that while the first-order term in the asymptotic expansion of the maximum number of messages depends on the power of the interfering codewords only through their sum, this does not hold for the second-order term.

In this paper, we analyze the asymptotic expansion for additive white Gaussian noise (AWGN) channels with feedback under an expected power constraint and the average error probability formalism. We show that the ε-capacity depends on ε in general and so the strong converse fails to hold. Furthermore, we provide bounds on the second-order term in the asymptotic expansion. We show that the second-order term is bounded between −ln ln n and a term that is proportional to +√n ln n. The lower bound on the second-order term shows that feedback does provide an improvement in the maximal achievable rate over the case where no feedback is available.

We derive the optimal second-order coding region for the lossy Gray-Wyner source coding problem for discrete memoryless sources under mild conditions. To do so, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú (2012). The converse part uses the perturbation argument by Gu and Effros (2009) in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses a generalization of type covering lemmas and the uniform continuity of the conditional rate-distortion function in both the source joint distribution and the distortion level.

We derive the optimal second-order coding region for the discrete successive refinement source coding problem under the joint excess-distortion event. To do so, we define a generalization of the tilted information density and leverage its properties. In the achievability part, we make use of type covering lemmas by Kanlis and Narayan (1996) and by No, Ingber and Weissman (2015). In the converse proof, we make use of the perturbation approach by Gu and Effros (2009). We also specialize our results to successively refinable sources and provide an alternative converse proof for such sources by generalizing Kostina and Verdú's (2012) one-shot converse bound for point-to-point lossy source coding.

This paper investigates the scaling exponent of polar codes for binary-input energy-harvesting (EH) channels with infinite-capacity batteries. The EH process is characterized by a sequence of independent and identically distributed random variables with finite variances. The scaling exponent μ of polar codes for a binary-input memoryless channel (BMC) qY|X with capacity C(qY|X) characterizes the closest gap between the capacity and the non-asymptotic achievable rates in the following way. For a fixed average error probability e ∈ (0, 1), the closest gap between the capacity C(qY|X) and a non-asymptotic achievable rate Rn for a length-n polar code scales as n-1/μ, i.e., min{|C(qY|X) - Rn|} = O(n-1/μ). It has been shown that the scaling exponent μ for any binary-input memoryless symmetric channel with C(qY|X) ∈ (0, 1) lies between 3.579 and 4.714, where the upper bound 4.714 was shown by an explicit construction of polar codes. Our main result shows that 4.714 remains to be a valid upper bound on the scaling exponent for any binary-input EH channel, i.e., a BMC subject to additional EH constraints. Our result thus implies that the EH constraints do not worsen the rate of convergence to capacity if polar codes are employed. An auxiliary contribution of this paper is that the upper bound on μ holds for binary-input memoryless asymmetric channels.

This paper investigates the information-theoretic limits of energy-harvesting (EH) channels in the finite blocklength regime. The EH process is characterized by a sequence of i.i.d. random variables with finite variances. We use the save-andtransmit strategy proposed by Ozel and Ulukus (2012) together with Shannon's non-asymptotic achievability bound to obtain lower bounds on the achievable rates for both additive white Gaussian noise channels and discrete memoryless channels under EH constraints. The first-order terms of the lower bounds of the achievable rates are equal to C and the second-order (backoff from capacity) terms are proportional to -√log n/n, where n denotes the blocklength and C denotes the capacity of the EH channel, which is the same as the capacity without the EH constraints. The constant of proportionality of the backoff term is found and qualitative interpretations are provided.

In this paper, we study a security problem on a simple wiretap network, consisting of a source node S, a destination node D, and an intermediate node R. The intermediate node connects the source and the destination nodes via a set of noiseless parallel channels, with sizes n1and n2, respectively. A message M is to be sent from S to D. The information in the network may be eavesdropped by a set of wiretappers. The wiretappers cannot communicate with one another. Each wiretapper can access a subset of channels, called a wiretap set. All the chosen wiretap sets form a wiretap pattern. A random key K is generated at S, and a coding scheme on (M, K) is employed to protect M. We define two decoding classes at D. In Class-I, only M is required to be recovered, and in Class-II, both M and K are required to be recovered. The objective is to minimize H(K)/H(M) for a given wiretap pattern under the perfect secrecy constraint. The first question we address is whether routing is optimal on this simple network. By enumerating all the wiretap patterns on the Class-I/II (3,3) networks and harnessing the power of Shannon-type inequalities, we find that gaps exist between the bounds implied by routing and the bounds implied by Shannon-type inequalities for a small fraction (c2%) of all the wiretap patterns. The second question we investigate is the following: What is min H(K)/H(M) for the remaining wiretap patterns where gaps exist? We study some simple wiretap patterns and find that their Shannon bounds (i.e., the lower bound induced by Shannon-type inequalities) can be achieved by linear codes, which means routing is not sufficient even for the (3, 3) network. For some complicated wiretap patterns, we study the structures of linear coding schemes under the assumption that they can achieve the corresponding Shannon bounds. This paper indicates that the determination of the entropic region of six linear vector spaces cannot be sidestepped. Some subtle issues on the network models are discussed, and interesting observations are stated.

We prove the strong converse for the N -source Gaussian multiple access channel. In particular, we show that any rate tuple that can be supported by a sequence of codes with asymptotic average error probability <;1 must lie in the Cover-Wyner capacity region. Our proof consists of the following. First, we perform an expurgation step to convert any given sequence of codes with asymptotic average error probability <;1 to codes with asymptotic maximal error probability <;1. Second, we quantize the input alphabets with an appropriately chosen resolution. Upon quantization, we apply the wringing technique (by Ahlswede) on the quantized inputs to obtain further subcodes from the subcodes obtained in the expurgation step, so that the resultant correlations among the symbols transmitted by the different sources vanish as the blocklength grows. Finally, we derive upper bounds on achievable sum-rates of the subcodes in terms of the type-II error of a binary hypothesis test. These upper bounds are then simplified through judicious choices of auxiliary output distributions. Our strong converse result carries over to the Gaussian interference channel under strong interference as long as the sum of the two asymptotic average error probabilities <;1.

This paper establishes that the strong converse holds for some classes of discrete memoryless multimessage multicast networks (DM-MMNs) whose corresponding cut-set bounds are tight, i.e., coincide with the corresponding sets of achievable rate tuples. Our strong converse result implies that for any DM-MMN of these classes, the average error probabilities of any sequence of codes operated at a rate tuple belonging to the exterior of the cut-set bound must tend to one (and are not simply bounded away from zero) as the block length grows. Examples in the classes of DM-MMNs include wireless erasure networks, DM-MMNs consisting of independent discrete memoryless channels (DMCs) as well as single-destination DM-MMNs consisting of independent DMCs with destination feedback. Our elementary proof technique leverages properties of the Rényi divergence.

This paper investigates the asymptotic expansion for the size of block codes defined for the additive white Gaussian noise (AWGN) channel with feedback under the following setting: A peak power constraint is imposed on every transmitted codeword (i.e., maximum per-codeword power constraint), and the average error probability of decoding the transmitted message is non-vanishing as the blocklength increases. It is well-known that the presence of feedback does not increase the first-order asymptotics (i.e., capacity) in the asymptotic expansion for the AWGN channel. The main contribution of this paper is proving an upper bound on the asymptotic expansion for the AWGN channel with feedback. Combined with existing achievability results for the AWGN channel, our result implies that the presence of feedback does not improve the second- and third-order asymptotics.

This paper establishes that the strong converse holds for some classes of discrete memoryless multimessage multicast networks (DM-MMNs) whose corresponding cut-set bounds are tight, i.e., coincide with the set of achievable rate tuples. The strong converse for these classes of DM-MMNs implies that all sequences of codes with rate tuples belonging to the exterior of the cut-set bound have average error probabilities that tend to one. Examples in the classes of DM-MMNs include wireless erasure networks, DM-MMNs consisting of independent discrete memoryless channels (DMCs), and single-destination DM-MMNs consisting of independent DMCs with destination feedback. Our proof technique leverages the properties of the Rényi divergence.

In this paper, we evaluate the asymptotics of equivocations and their exponents. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source. Unlike previous works that use the Shannon information measures to quantify randomness or information, in this paper, we consider a more general class of information measures, i.e., the Rényi information measures and their Gallager forms. We prove tight asymptotic results for the equivocation and its exponential decay rates by establishing new non-asymptotic bounds on the equivocation and evaluating these bounds asymptotically.

The problem of channel coding with the erasure option is revisited for discrete memoryless channels. The interplay between the code rate, the undetected and total error probabilities is characterized. Using the information spectrum method, a sequence of codes of increasing blocklengths n is designed to illustrate this tradeoff. Furthermore, for additive discrete memoryless channels, the ensemble performance of a sequence of random codes is also analyzed to demonstrate the optimality of the above-mentioned codes. The tradeoff between the code rate, undetected and total errors as well as the threshold in a generalized likelihood ratio test is characterized asymptotically. In particular, the code rate tends to the capacity of the channel at a rate slower than n−1/2corresponding to the moderate deviations regime. In this case, both error probabilities decay subexponentially and asymmetrically. The precise decay rates are characterized. The proof techniques involve applications of a modified (or “shifted”) version of the Gärtner-Ellis theorem and the type class enumerator method to characterize the asymptotic behavior of a sequence of cumulant generating functions.

This paper studies the second-order asymptotics of the discrete memoryless multiple-access channel with degraded message sets. For a fixed average error probability ε ∈ (0, 1) and an arbitrary point on the boundary of the capacity region, we characterize the speed of convergence of rate pairs that converge to that point for codes that have asymptotic error probability no larger than ε, thus complementing an analogous result given previously for the Gaussian setting.

We consider the secret key generation problem when sources are randomly excited by the sender and there is a noiseless public discussion channel. Our setting is thus similar to recent works on channels with action-dependent states, where the channel state may be influenced by some of the parties involved. We derive single-letter expressions for the secret key capacity through a type of source emulation analysis. We also derive lower bounds on the achievable reliability and secrecy exponents, i.e., the exponential rates of decay of the probability of decoding error and of the information leakage. These exponents allow us to determine a set of strongly achievable secret key rates. For degraded eavesdroppers, the maximum strongly achievable rate equals the secret key capacity; our exponents can also be specialized to previously known results. In deriving our strong achievability results, we introduce a coding scheme that combines wiretap coding (to excite the channel) and key extraction (to distill keys from residual randomness). The secret key capacity is naturally seen to be a combination of both source- and channel-type randomness. Through examples, we illustrate a fundamental interplay between the portion of the secret key rate due to each type of randomness. We also illustrate inherent tradeoffs between the achievable reliability and secrecy exponents. Our new scheme also naturally accommodates rate limits on the public discussion. We show that under rate constraints, we are able to achieve larger rates than those that can be attained through a pure source emulation strategy.

The problem of channel coding with the erasure option is revisited for discrete memoryless channels. The interplay between the code rate, the undetected and total error probabilities is characterized. Using the information spectrum method, a sequence of codes of increasing blocklengths n is designed to illustrate this tradeoff. Furthermore, for additive discrete memoryless channels with uniform input distribution, we establish that our analysis is tight with respect to the ensemble average. This is done by analyzing the ensemble performance in terms of a tradeoff between the code rate, the undetected and total errors. This tradeoff is parameterized by the threshold in a generalized likelihood ratio test. Two asymptotic regimes are studied. First, the code rate tends to the capacity of the channel at a rate slower than n-1/2corresponding to the moderate deviations regime. In this case, both error probabilities decay subexponentially and asymmetrically. The precise decay rates are characterized. Second, the code rate tends to capacity at a rate of n-1/2. In this case, the total error probability is asymptotically a positive constant, while the undetected error probability decays as exp (-bn1/2) for some b > 0. The proof techniques involve the applications of a modified (or shifted) version of the Gärtner-Ellis theorem and the type class enumerator method to characterize the asymptotic behavior of a sequence of cumulant generating functions.

In 1975, Carleial presented a special case of an interference channel, called the very strong interference regime, in which the interference does not reduce the capacity of the constituent point-to-point Gaussian channels. In this paper, we show that in the strictly very strong interference regime, the dispersions are similarly unaffected. More precisely, in this paper, we characterize the second-order coding rates of the Gaussian interference channel in the strictly very strong interference regime. In other words, we characterize the speed of convergence of rates of optimal block codes toward a boundary point of the (rectangular) capacity region. These second-order coding rates are expressed in terms of the average probability of error and variances of appropriately defined information densities which coincide with the dispersion of the (single-user) Gaussian channel. This allows us to conclude that the dispersions are unaffected by interference in this channel model.

This paper studies the second-order asymptotics of the Gaussian multiple-access channel with degraded message sets. For a fixed average error probability ε ϵ (0,1) and an arbitrary point on the boundary of the capacity region, we characterize the speed of convergence of rate pairs that converge to that boundary point for codes that have asymptotic error probability no larger than ε. As a stepping stone to this local notion of the second-order asymptotics, we study a global notion, and establish relationships between the two. We provide a numerical example to illustrate how the angle of approach to a boundary point affects the second-order coding rate. This is the first conclusive characterization of the second-order asymptotics of a network information theory problem in which the capacity region is not a polygon.

We study a form of unequal error protection that we term unequal message protection (UMP). The message set of a UMP code is a union of m disjoint message classes. Each class has its own error protection requirement, with some classes needing better error protection than others. We analyze the tradeoff between rates of message classes and the levels of error protection; our analysis reveals new tradeoffs, which were not captured by prior works on UMP codes. To obtain our results, we generalize finite block length achievability and converse bounds due to Polyanskiy-Poor-Verdú. We evaluate our bounds for the binary symmetric and binary erasure channels, and analyze the asymptotic characteristic of the bounds in the fixed error and moderate deviations regimes. In addition, we consider two questions related to the practical construction of UMP codes. First, we study a header construction that prefixes the message class into a header followed by data protection using a standard homogeneous (classical) code. We show that, in general, this construction is not optimal at finite block lengths. We further demonstrate that our main UMP achievability bound can be obtained using coset codes, which suggests a path to implementation of tractable UMP codes.

Bounds on the reliability function for the discrete memoryless relay channel are derived using the method of types. Two achievable error exponents are derived based on partial decode-forward and compress-forward, which are well-known superposition block-Markov coding schemes. The derivations require combinations of the techniques involved in the proofs of Csiszár-Körner-Marton's packing lemma for the error exponent of channel coding and Marton's type covering lemma for the error exponent of source coding with a fidelity criterion. The decode-forward error exponent is evaluated on Sato's relay channel. From this example, it is noted that to obtain the fastest possible decay in the error probability for a fixed effective coding rate, one ought to optimize the number of blocks in the block-Markov coding scheme assuming the blocklength within each block is large. An upper bound on the reliability function is also derived using ideas from Haroutunian's lower bound on the error probability for point-to-point channel coding with feedback.

This paper shows that, under the average error probability formalism, the third-order term in the normal approximation for the additive white Gaussian noise channel with a maximal or equal power constraint is at least (1/2) log n + O(1). This improves on the lower bound by Polyanskiy-Poor-Verdú (2010) and matches the upper bound proved by the same authors.

We present a novel nonasymptotic or finite blocklength achievability bounds for three side-information problems in network information theory. These include: 1) the Wyner-Ahlswede-Körner (WAK) problem of almost-lossless source coding with rate-limited side-information; 2) the Wyner-Ziv (WZ) problem of lossy source coding with side-information at the decoder; and 3) the Gel'fand-Pinsker (GP) problem of channel coding with noncausal state information available at the encoder. The bounds are proved using ideas from channel simulation and channel resolvability. Our bounds for all three problems improve on all previous nonasymptotic bounds on the error probability of the WAK, WZ, and GP problems-in particular those derived by Verdú. Using our novel nonasymptotic bounds, we recover the general formulas for the optimal rates of these side-information problems. Finally, we also present achievable second-order coding rates by applying the multidimensional Berry-Esséen theorem to our new nonasymptotic bounds. Numerical results show that the second-order coding rates obtained using our nonasymptotic achievability bounds are superior to those obtained using existing finite blocklength bounds.

Strong impossibility results for noisy group testing are derived. It is shown that regardless of the allowed error probability in identifying the defective set, the required of number of measurements is almost the same as that required for the error probability to be arbitrarily small. Our proof technique involves the use of the blowing-up lemma.

The second-order asymptotics of the Gaussian interference channel in the strictly very strong interference regime are considered. The rates of convergence to a given point on the boundary of the (first-order) capacity region are determined. These rates are expressed in terms of the average probability of error and variances of selected modified information densities which coincide with the dispersion of the (single-user) Gaussian channel. Interestingly, under the strictly very strong interference assumption, the intuition that receivers can decode messages from non-intended transmitters carries over to the second-order analysis.

This paper studies the second-order asymptotics of the Gaussian multiple-access channel with degraded message sets. For a fixed average error probability ε ∈ (0,1) and an arbitrary point on the boundary of the capacity region, we characterize the speed of convergence of rate pairs that converge to that point for codes that have asymptotic error probability no larger than ε. We do so by elucidating the relationship between global and local notions of second-order asymptotics.

We study the problem of lossless joint source-channel coding (JSCC) in the finite block length regime from an unequal message protection (UMP) perspective. We demonstrate that the problem of lossless JSCC can be cast in terms of UMP codes previously studied. We show that an optimal JSCC can be constructed from a matched UMP code. We further derive a finite block length bound that characterizes the performance of a JSCC constructed from a UMP code not perfectly matched to the source. This bound is evaluated for a binary memoryless source transmitted over a binary symmetric channel. Two-class schemes previously studied in literature are compared with the proposed scheme. Empirically the JSCCs based on UMP codes approach the performance of the optimal matched code quite fast in number of classes used.

We study achievability bounds for a class of unequal error protection codebooks with m > 1 different classes of codewords called unequal message protection (UMP) codes. We extend the dependence testing bound due to Polyanskiy-Poor-Verdú to be applicable to UMP codes and use this extension to obtain refined asymptotic expansions for the performance of such codes over discrete memoryless channels. In addition, we consider two questions related to the practical construction of UMP codes. First, we study a “header” construction that prefixes the message class into a header followed by data protection using a standard homogeneous (classical) code. We show that, in general, this construction is not optimal at finite block lengths. We further demonstrate that our main UMP achievability bound can be obtained using coset codes, which suggests a path to tractable implementation of UMP codes.

We derive the second-order capacities (supremum of second-order coding rates) for erasure and list decoding. Fpor erasure decoding, we show that second-order capacity is √VΦ-1(εt) where V is the channel dispersion and (εtis the total error probability, i.e. the sum of the erasure and undetected errors. We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate. For list decoding, we consider list codes of deterministic size 2√nland show that the second-order capacity is l+ √VΦ-1(ε) where ε is the permissible error probability. Both coding schemes use the threshold decoder and converses are proved using variants of the meta-converse.

This paper shows that, under the average error probability formalism, the third-order term in the normal approximation for the additive white Gaussian noise channel with a maximal or equal power constraint is at least 1 over 2 log n+O(1). This improves on the lower bound by Polyanskiy-Poor-Verdú (2010) and matches the upper bound proved by the same authors.

We study the (almost lossless) joint source-channel coding problem from the moderate deviations perspective where the bandwidth expansion ratio tends towards the ratio of the channel capacity and source entropy at a rate larger than n−1/2(n being the channel blocklength) and the error probability decays subexponentially. We consider the stationary ergodic Markov (SEM) source as well as discrete memoryless and additive SEM channels. We also discuss the loss due to separation in the moderate deviations setting.

We study the non-asymptotic fundamental limits for transmitting classical information over memoryless quantum channels, i.e. we investigate the amount of information that can be transmitted when the channel is used a finite number of times and a finite average decoding error is permissible. We show that, if we restrict the encoder to use ensembles of separable states, the non-asymptotic fundamental limit admits a Gaussian approximation that illustrates the speed at which the rate of optimal codes converges to the Holevo capacity as the number of channel uses tends to infinity. To do so, several important properties of quantum information quantities, such as the capacity-achieving output state, the divergence radius, and the channel dispersion, are generalized from their classical counterparts. Further, we exploit a close relation between classical-quantum channel coding and quantum binary hypothesis testing and rely on recent progress in the non-asymptotic characterization of quantum hypothesis testing and its Gaussian approximation.

This letter derives strong impossibility results for several sparse signal processing problems. It is shown that regardless of the allowed error probability in identifying the salient support set (as long as this probability is below one), the required number of measurements is almost the same as that required for the error probability to be arbitrarily small. Our proof technique involves the use of the blowing-up lemma and can be applied to diverse problems from noisy group testing to graphical model selection as long as the observations are discrete.

We consider the Gel'fand-Pinsker problem in which the channel and state are general, i.e., possibly non-stationary, non-memoryless and non-ergodic. Using the information spectrum method and a non-trivial modification of the piggyback coding lemma by Wyner, we prove that the capacity can be expressed as an optimization over the difference of a spectral inf- and a spectral sup-mutual information rate. We consider various specializations, including the case where the channel and the state are memoryless but not necessarily stationary.

We analyze the dispersions of distributed lossless source coding (the Slepian-Wolf problem), the multiple-access channel, and the asymmetric broadcast channel. For the two-encoder Slepian-Wolf problem, we introduce a quantity known as the entropy dispersion matrix, which is analogous to the scalar dispersions that have gained interest recently. We prove a global dispersion result that can be expressed in terms of this entropy dispersion matrix and provides intuition on the approximate rate losses at a given blocklength and error probability. To gain better intuition about the rate at which the nonasymptotic rate region converges to the Slepian-Wolf boundary, we define and characterize two operational dispersions: 1) the local dispersion and 2) the weighted sum-rate dispersion. The former represents the rate of convergence to a point on the Slepian-Wolf boundary, whereas the latter represents the fastest rate for which a weighted sum of the two rates converges to its asymptotic fundamental limit. Interestingly, when we approach either of the two corner points, the local dispersion is characterized not by a univariate Gaussian, but a bivariate one as well as a subset of off-diagonal elements of the aforementioned entropy dispersion matrix. Finally, we demonstrate the versatility of our achievability proof technique by providing inner bounds for the multiple-access channel and the asymmetric broadcast channel in terms of dispersion matrices. All our proofs are unified by a so-called vector rate redundancy theorem, which is proved using the multidimensional Berry-Esséen theorem.

We study the performance limits of state-dependent discrete memoryless channels with a discrete state available at both the encoder and the decoder. We establish the ε-capacity as well as necessary and sufficient conditions for the strong converse property for such channels when the sequence of channel states is not necessarily stationary, memoryless, or ergodic. We then seek a finer characterization of these capacities in terms of second-order coding rates. The general results are supplemented by several examples including independent identically distributed and Markov states and mixed channels.

We propose a novel framework of using a parsimonious statistical model, known as mixture of Gaussian trees, for modeling the possibly multimodal minority class to solve the problem of imbalanced time-series classification. By exploiting the fact that close-by time points are highly correlated due to smoothness of the time-series, our model significantly reduces the number of covariance parameters to be estimated from O(d(2)) to O(Ld), where L is the number of mixture components and d is the dimensionality. Thus, our model is particularly effective for modeling high-dimensional time-series with limited number of instances in the minority positive class. In addition, the computational complexity for learning the model is only of the order O(Ln+d(2)) where n+ is the number of positively labeled samples. We conduct extensive classification experiments based on several well-known time-series data sets (both single- and multimodal) by first randomly generating synthetic instances from our learned mixture model to correct the imbalance. We then compare our results with several state-of-the-art oversampling techniques and the results demonstrate that when our proposed model is used in oversampling, the same support vector machines classifier achieves much better classification accuracy across the range of data sets. In fact, the proposed method achieves the best average performance 30 times out of 36 multimodal data sets according to the F-value metric. Our results are also highly competitive compared with nonoversampling-based classifiers for dealing with imbalanced time-series data sets.

We consider the scenario in which multiple sensors send spatially correlated data to the fusion center (FC) via independent Rayleigh-fading channels with additive noise. Assuming that the sensor data is sparse in some basis, we show that the recovery of the signal can be formulated as a compressive sensing (CS) problem. To model the scenario where sensors operate with intermittently available energy that is harvested from the environment, we propose that each sensor transmits independently with some probability, and adapts the transmit power to its harvested energy. Due to the probabilistic transmissions, the elements of the equivalent sensing matrix are not Gaussian. Besides, since the sensors have different energy harvesting rates and different sensor-to-FC distances, the FC has different receive signal-to-noise ratios (SNRs) for each sensor, referred to as the inhomogeneity of SNRs. Thus, the elements of the sensing matrix are also not identically distributed. We provide theoretical guarantees on the number of measurements for reliable reconstruction, by showing that the sensing matrix satisfies the restricted isometry property (RIP), under some mild conditions. We then compute an achievable system delay under an allowable mean-squared-error (MSE). Furthermore, using techniques from large deviations theory, we analyze the impact of inhomogeneity of the SNRs on the so-called k-restricted eigenvalues, which governs the number of measurements required for the RIP to hold. Our analysis is corroborated by numerical results.

In this work, achievable dispersions for the discrete memoryless interference channel (DM-IC) are derived. In other words, we characterize the backoff from the Han-Kobayashi (HK) achievable region, the largest inner bound known to date for the DM-IC. In addition, we also characterize the backoff from Sato's region in the strictly very strong interference regime, and the backoff from Costa and El Gamal's region in the strong interference regime. To do so, Feinstein's lemma is first generalized to be applicable to the interference channel. Making use of the generalized Feinstein's lemma, it is found that the dispersions for the DM-IC can be represented by the information variances of eight information densities when HK message splitting is involved, and of six information densities for another encoding strategy. We also derive an outer bound that leverages on a known dispersion result for channels with random state by Ingber-Feder. It is shown that for the strictly very strong interference regime, the inner and outer bound have similar algebraic forms.

We study converse bounds for unequal error protection codebooks with k > 1 different classes of codewords. We dub these unequal error protection codes “assorted codes”. We extend a finite blocklength converse bound due to Polyanskiy-Poor-Verdú to apply to assorted codes and use this extension to obtain a refined asymptotic expansion for the performance of assorted codes over a discrete memoryless channel. Our main contribution is to demonstrate that there is indeed a loss in the rates of an assorted code compared to equivalent homogeneous (classical) codes. Notably, when the number of codeword classes is polynomial in blocklength n the loss is apparent in the third order O(log n) term of the asymptotic expansion of the logarithm of the maximum number of codewords. This is in sharp contrast to the previous literature which only considers this problem within regimes where no such loss could be observed.

We consider the Gel'fand-Pinsker problem in which the channel and state are general, i.e., possibly non-stationary, non-memoryless and non-ergodic. Using Verdú-Han's information spectrum method and a non-trivial modification of Wyner's piggyback coding lemma, we prove that the capacity can be expressed as an optimization over the difference of a spectral infand a spectral sup-mutual information rate. We consider various specializations including the case where the channel and state are memoryless but non-stationary. We then extend our result to obtain the capacity region of the general Gel'fand-Pinsker problem with rate-limited state information at the decoder.

Achievable error exponents for the relay channel are derived using the method of types. In particular, two block-Markov coding schemes are analyzed: partial decode-forward and compress-forward. The derivations require combinations of the techniques in the proofs of the packing lemma for the error exponent of channel coding and the covering lemma for the error exponent of source coding with a fidelity criterion.

This paper shows that the logarithm of the ε-error capacity (average error probability) for n uses of a discrete memoryless channel with positive conditional information variance at every capacity-achieving input distribution is upper bounded by the normal approximation plus a term that does not exceed 1/2 log n + O(1).

We present a novel achievability bound for the Wyner-Ahlswede-Körner (WAK) problem of lossless source coding with rate-limited side-information. This bound is proved using ideas from channel simulation and channel resolvability. The bound improves on all previous non-asymptotic bounds on the error probability of the WAK problem. We also present achievable second-order coding rates by applying the multidimensional Berry-Essèen theorem to our new non-asymptotic bound.

We consider state-dependent memoryless channels with general state available at both encoder and decoder. We establish the ε-capacity and the optimistic ε-capacity. This allows us to prove a necessary and sufficient condition for the strong converse to hold. We also provide a simpler sufficient condition on the first- and second-order statistics of the state process that ensures that the strong converse holds.

This paper addresses the estimation of the latent dimensionality in nonnegative matrix factorization (NMF) with the β-divergence. The β-divergence is a family of cost functions that includes the squared euclidean distance, Kullback-Leibler (KL) and Itakura-Saito (IS) divergences as special cases. Learning the model order is important as it is necessary to strike the right balance between data fidelity and overfitting. We propose a Bayesian model based on automatic relevance determination (ARD) in which the columns of the dictionary matrix and the rows of the activation matrix are tied together through a common scale parameter in their prior. A family of majorization-minimization (MM) algorithms is proposed for maximum a posteriori (MAP) estimation. A subset of scale parameters is driven to a small lower bound in the course of inference, with the effect of pruning the corresponding spurious components. We demonstrate the efficacy and robustness of our algorithms by performing extensive experiments on synthetic data, the swimmer dataset, a music decomposition example, and a stock price prediction task.

This paper shows that the logarithm of the ε-error capacity (average error probability) for n uses of a discrete memoryless channel (DMC) is upper bounded by the normal approximation plus a third-order term that does not exceed [ 1/ 2] logn +O(1) if the ε-dispersion of the channel is positive. This matches a lower bound by Y. Polyanskiy (2010) for DMCs with positive reverse dispersion. If the ε-dispersion vanishes, the logarithm of the ε-error capacity is upper bounded by n times the capacity plus a constant term except for a small class of DMCs and ε ≥ [ 1/ 2].

We study the moderate-deviations (MD) setting for lossy source coding of stationary memoryless sources. More specifically, we derive fundamental compression limits of source codes whose rates are R(D) ± εn, where R(D) is the rate-distortion function and εnis a sequence that dominates √1/n. This MD setting is complementary to the large-deviations and central limit settings and was studied by Altug and Wagner for the channel coding setting. We show, for finite alphabet and Gaussian sources, that as in the central limit-type results, the so-called dispersion for lossy source coding plays a fundamental role in the MD setting for the lossy source coding problem.

We characterize second-order coding rates (or dispersions) for distributed lossless source coding (the Slepian-Wolf problem). We introduce a fundamental quantity known as the entropy dispersion matrix, which is analogous to scalar dispersion quantities. We show that if this matrix is positive-definite, the optimal rate region under the constraint of a fixed blocklength and non-zero error probability has a curved boundary compared to being polyhedral for the Slepian-Wolf case. In addition, the entropy dispersion matrix governs the rate of convergence of the non-asymptotic region to the asymptotic one. As a by-product of our analyses, we develop a general universal achievability procedure for dispersion analysis of some other network information theory problems such as the multiple-access channel. Numerical examples show how the region given by Gaussian approximations compares to the Slepian-Wolf region.

This paper establishes information-theoretic limits for estimating a finite-field low-rank matrix given random linear measurements of it. These linear measurements are obtained by taking inner products of the low-rank matrix with random sensing matrices. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp and the minimum-rank decoder is asymptotically optimal. The reliability function of this decoder is also derived by appealing to de Caen's lower bound on the probability of a union. The sufficient condition also holds when the sensing matrices are sparse—a scenario that may be amenable to efficient decoding. More precisely, it is shown that if the$n\times n$-sensing matrices contain, on average,$\Omega ({n}{\log n})$entries, the number of measurements required is the same as that when the sensing matrices are dense and contain entries drawn uniformly at random from the field. Analogies are drawn between the aforementioned results and rank-metric codes in the coding theory literature. In fact, we are also strongly motivated by understanding when minimum rank distance decoding of random rank-metric codes succeeds. To this end, we derive minimum distance properties of equiprobable and sparse rank-metric codes. These distance properties provide a precise geometric interpretation of the fact that the sparse ensemble requires as few measurements as the dense one.

This paper establishes information-theoretic limits in estimating a finite field low-rank matrix given random linear measurements of it. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp. The reliability function associated to the minimum-rank decoder is also derived. Our bounds hold even in the case where the sensing matrices are sparse. Connections to rank-metric codes are discussed.

We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm for structure estimation based known as conditional mutual information test. This simple local algorithm requires only low-order statistics of the data and decides whether two nodes are neighbors in the unknown graph. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent) when the number of samples scales as n= Omega(J_{min}^{-4} log p), where p is the number of nodes and J_{min} is the minimum edge potential. We also prove novel non-asymptotic necessary conditions for graphical model selection.

The problem of maximum-likelihood (ML) estimation of discrete tree-structured distributions is considered. Chow and Liu established that ML-estimation reduces to the construction of a maximum-weight spanning tree using the empirical mutual information quantities as the edge weights. Using the theory of large-deviations, we analyze the exponent associated with the error probability of the event that the ML-estimate of the Markov tree structure differs from the true tree structure, given a set of independently drawn samples. By exploiting the fact that the output of ML-estimation is a tree, we establish that the error exponent is equal to the exponential rate of decay of a single dominant crossover event. We prove that in this dominant crossover event, a non-neighbor node pair replaces a true edge of the distribution that is along the path of edges in the true tree graph connecting the nodes in the non-neighbor pair. Using ideas from Euclidean information theory, we then analyze the scenario of ML-estimation in the very noisy learning regime and show that the error exponent can be approximated as a ratio, which is interpreted as the signal-to-noise ratio (SNR) for learning tree distributions. We show via numerical experiments that in this regime, our SNR approximation is accurate.

The problem of composite binary hypothesis testing of Markov forest (or tree) distributions is considered. The worst-case type-II error exponent is derived under the Neyman-Pearson formulation. Under simple null hypothesis, the error exponent is derived in closed-form and is characterized in terms of the so-called bottleneck edge of the forest distribution. The least favorable distribution for detection is shown to be Markov on the second-best max-weight spanning tree with mutual information edge weights. A necessary and sufficient condition to have positive error exponent is derived.

We consider recovering the salient feature subset for distinguishing between two probability models from i.i.d. samples. Identifying the salient set improves discrimination performance and reduces complexity. The focus in this work is on the high-dimensional regime where the number of variables d, the number of salient variables k and the number of samples n all grow. The definition of saliency is motivated by error exponents in a binary hypothesis test and is stated in terms of relative entropies. It is shown that if n grows faster than max{ck log((d-k)/k), exp(c'k)} for constants c, c', then the error probability in selecting the salient set can be made arbitrarily small. Thus, n can be much smaller than d. The exponential rate of decay and converse theorems are also provided. An efficient and consistent algorithm is proposed when the distributions are graphical models which are Markov on trees.

The problem of maximum-likelihood learning of the structure of an unknown discrete distribution from samples is considered when the distribution is Markov on a tree. Large-deviation analysis of the error in estimation of the set of edges of the tree is performed. Necessary and sufficient conditions are provided to ensure that this error probability decays exponentially. These conditions are based on the mutual information between each pair of variables being distinct from that of other pairs. The rate of error decay, or error exponent, is derived using the large-deviation principle. The error exponent is approximated using Euclidean information theory and is given by a ratio, to be interpreted as the signal-to-noise ratio (SNR) for learning. Numerical experiments show the SNR approximation is accurate.

Graphical models allow scientific prior knowledge to be incorporated into the statistical analysis of data, whilst also providing a vivid way to represent and communicate this knowledge. In this paper we develop a graphical model of the immune system as a means of analyzing immunological data from the Manchester asthma and allergy study (MAAS). The analysis is achieved using the Infer.NET tool which allows Bayesian inference to be applied automatically to a specified graphical model.Our immune system model consists firstly of a hidden Markov model representing how allergen-specific skin prick tests (SPTs) and serum-specific IgE tests (SITs) change over time. By introducing a latent multinomial variable, we also cluster the children in an unsupervised manner into different sensitization classes. For 2 sensitization classes, the children who are vulnerable to allergies and have a high probability of having asthma (22%) are identified. For 5 sensitization classes, children in the first cluster, those who are vulnerable to allergies, have an even higher probability of having asthma (42%). The second part of the model involves using the inferred sensitization class as a label and 8 exposure variables in a Bayes point machine. Using multiple permutation tests, we conclude that the level of endotoxins and gender have a significant effect on a child's vulnerability to allergies.

We present a method for sequential learning of increasingly complex graphical models for discriminating between two hypotheses. We generate forests for each hypothesis, each with no more edges than a spanning tree, which optimize an information-theoretic criteria. The method relies on a straightforward extension of the efficient max-weight spanning tree (MWST) algorithm by incorporating multivalued edge-weights. Each iteration produces nested forests with increasing number of edges; each provably optimal as compared to alternative forests. Empirical results demonstrate superior probability of error as compared to generative approaches.