BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vincent Y. F. Tan

Vincent Y. F. Tan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITMachine Learningmath.STStatistics Theoryeess.SPCryptography and Securitymath.OCMethodologyComputer VisionDiscrete MathematicsApplicationseess.IVInformation Retrievalmath.COArtificial IntelligenceComputational Geometrymath-phmath.GRmath.MPmath.NTmath.PRNumerical Analysisquant-ph

Catalog footprint

What is connected

87works
24topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

87 published item(s)

preprint2022arXiv

A Survey of Risk-Aware Multi-Armed Bandits

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 trade-off 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits

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 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Asymptotic Nash Equilibrium for the $M$-ary Sequential Adversarial Hypothesis Testing Game

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 \emph{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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Asymptotics of Sequential Composite Hypothesis Testing under Probabilistic Constraints

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 $Γ$. 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 $ε$, we obtain certain fundamental limits on the asymptotic behavior of the sequential test as $n$ tends to infinity. Assuming that $Γ$ 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 $\mathcal{X}$ is a finite alphabet. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Best Arm Identification in Restless Markov Multi-Armed Bandits

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 ({\em 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Sharpness-aware Minimization for Improved Training of Neural Networks

Overparametrized Deep Neural Networks (DNNs) often achieve astounding performances, but may potentially result in severe generalization error. Recently, the relation between the sharpness of the loss landscape and the generalization error has been established by Foret et al. (2020), in which the Sharpness Aware Minimizer (SAM) was proposed to mitigate the degradation of the generalization. Unfortunately, SAM s computational cost is roughly double that of base optimizers, such as Stochastic Gradient Descent (SGD). This paper thus proposes Efficient Sharpness Aware Minimizer (ESAM), which boosts SAM s efficiency at no cost to its generalization performance. ESAM includes two novel and efficient training strategies-StochasticWeight Perturbation and Sharpness-Sensitive Data Selection. In the former, the sharpness measure is approximated by perturbing a stochastically chosen set of weights in each iteration; in the latter, the SAM loss is optimized using only a judiciously selected subset of data that is sensitive to the sharpness. We provide theoretical explanations as to why these strategies perform well. We also show, via extensive experiments on the CIFAR and ImageNet datasets, that ESAM enhances the efficiency over SAM from requiring 100% extra computations to 40% vis-a-vis base optimizers, while test accuracies are preserved or even improved.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Exact Recovery in the General Hypergraph Stochastic Block Model

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 (p1,..., pk). 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Robustness of Neural Ordinary Differential Equations

Neural ordinary differential equations (ODEs) have been attracting increasing attention in various research domains recently. There have been some works studying optimization issues and approximation capabilities of neural ODEs, but their robustness is still yet unclear. In this work, we fill this important gap by exploring robustness properties of neural ODEs both empirically and theoretically. We first present an empirical study on the robustness of the neural ODE-based networks (ODENets) by exposing them to inputs with various types of perturbations and subsequently investigating the changes of the corresponding outputs. In contrast to conventional convolutional neural networks (CNNs), we find that the ODENets are more robust against both random Gaussian perturbations and adversarial attack examples. We then provide an insightful understanding of this phenomenon by exploiting a certain desirable property of the flow of a continuous-time ODE, namely that integral curves are non-intersecting. Our work suggests that, due to their intrinsic robustness, it is promising to use neural ODEs as a basic block for building robust deep network models. To further enhance the robustness of vanilla neural ODEs, we propose the time-invariant steady neural ODE (TisODE), which regularizes the flow on perturbed data via the time-invariant property and the imposition of a steady-state constraint. We show that the TisODE method outperforms vanilla neural ODEs and also can work in conjunction with other state-of-the-art architectural methods to build more robust deep networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Informativeness of K -Means for Learning Mixture Models

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 {\it 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 {\it optimal clustering} that 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Tight Regret Bounds for Noisy Optimization of a Brownian Motion

We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the $T$ adaptively chosen observations are corrupted by Gaussian noise. We show that as the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $Ω(σ\sqrt{T / \log (T)}) \cap \mathcal{O}(σ\sqrt{T} \cdot \log T)$ and $Ω(σ/ \sqrt{T \log (T)}) \cap \mathcal{O}(σ\log T / \sqrt{T})$ respectively, where $σ^2$ is the noise variance. Thus, our upper and lower bounds are tight up to a factor of $\mathcal{O}( (\log T)^{1.5} )$. The upper bound uses an algorithm based on confidence bounds and the Markov property of Brownian motion (among other useful properties), and the lower bound is based on a reduction to binary hypothesis testing.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Towards Adversarially Robust Deep Image Denoising

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 ({\sc ObsAtk}), to craft adversarial zero-mean perturbations on given noisy images. We find that existing DIDs are vulnerable to the adversarial noise generated by {\sc ObsAtk}. Secondly, to robustify DIDs, we propose an adversarial training strategy, hybrid adversarial training ({\sc 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, {\sc 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 {\sc ObsAtk} and {\sc HAT}.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

An Interpretable Intensive Care Unit Mortality Risk Calculator

Mortality risk is a major concern to patients have just been discharged from the intensive care unit (ICU). Many studies have been directed to construct machine learning models to predict such risk. Although these models are highly accurate, they are less amenable to interpretation and clinicians are typically unable to gain further insights into the patients' health conditions and the underlying factors that influence their mortality risk. In this paper, we use patients' profiles extracted from the MIMIC-III clinical database to construct risk calculators based on different machine learning techniques such as logistic regression, decision trees, random forests and multilayer perceptrons. We perform an extensive benchmarking study that compares the most salient features as predicted by various methods. We observe a high degree of agreement across the considered machine learning methods; in particular, the cardiac surgery recovery unit, age, and blood urea nitrogen levels are commonly predicted to be the most salient features for determining patients' mortality risks. Our work has the potential for clinicians to interpret risk predictions.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Community Detection and Matrix Completion with Social and Item Similarity Graphs

We consider the problem of recovering a binary rating matrix as well as clusters of users and items based on a partially observed matrix together with side-information in the form of social and item similarity graphs. These two graphs are both generated according to the celebrated stochastic block model (SBM). We develop lower and upper bounds on sample complexity that match for various scenarios. Our information-theoretic results quantify the benefits of the availability of the social and item similarity graphs. Further analysis reveals that under certain scenarios, the social and item similarity graphs produce an interesting synergistic effect. This means that observing two graphs is strictly better than observing just one in terms of reducing the sample complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Distributionally Robust and Multi-Objective Nonnegative Matrix Factorization

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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On Non-Interactive Simulation of Binary Random Variables

We leverage proof techniques 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. For a specific instance of problem parameters, our main result answers 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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Risk-Constrained Thompson Sampling for CVaR Bandits

The multi-armed bandit (MAB) problem is a ubiquitous decision-making problem that exemplifies the exploration-exploitation tradeoff. Standard formulations exclude risk in decision making. Risk notably complicates the basic reward-maximising objective, in part because there is no universally agreed definition of it. In this paper, we consider a popular risk measure in quantitative finance known as the Conditional Value at Risk (CVaR). We explore the performance of a Thompson Sampling-based algorithm CVaR-TS under this risk measure. We provide comprehensive comparisons between our regret bounds with state-of-the-art L/UCB-based algorithms in comparable settings and demonstrate their clear improvement in performance. We also include numerical simulations to empirically verify that CVaR-TS outperforms other L/UCB-based algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Sequential Classification with Empirically Observed Statistics

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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples

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 $ρ_{\min}$ is $ρ_{\min}^{-8}$ instead of $ρ_{\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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Asymptotic Expansions of Smooth Rényi Entropies and Their Applications

This study considers the unconditional smooth Rényi entropy, the smooth conditional Rényi entropy proposed by Kuzuoka [\emph{IEEE Trans.\ Inf.\ Theory}, vol.~66, no.~3, pp.~1674--1690, 2020], and a new quantity which we term the conditional smooth Rényi entropy. In particular, we examine asymptotic expansions of these entropies when the underlying source with its side-information is stationary and memoryless. Using these smooth Rényi entropies, we establish one-shot coding theorems of several information-theoretic problems: Campbell's source coding, guessing problems, and task encoding problems, all allowing errors. In 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 of the source. Applying our asymptotic expansions to the derived one-shot coding theorems, we derive various asymptotic fundamental limits for these problems when their error probabilities are allowed to be non-vanishing. We show that, in 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 (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 criteria.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting

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; these are r.v.'s whose cumulant generating functions (CGFs) can be bounded by a quadratic only for non-positive arguments of the CGFs. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Corrections to "Wyner's Common Information under Rényi Divergence Measures"

In this correspondence, we correct an erroneous result on the achievability part of the Rényi common information with order $1+s\in(1,2]$ in [1]. 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\in(1,\infty]$. Numerical results show that for doubly symmetric binary sources, the new upper and lower bounds coincide for the order $1+s\in(1,2]$ and they are both strictly larger than Wyner's common information for this case.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Detection with Empirically Observed Statistics

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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Economy Statistical Recurrent Units For Inferring Nonlinear Granger Causality

Granger causality is a widely-used criterion for analyzing interactions in large-scale networks. As most physical interactions are inherently nonlinear, we consider the problem of inferring the existence of pairwise Granger causality between nonlinearly interacting stochastic processes from their time series measurements. Our proposed approach relies on modeling the embedded nonlinearities in the measurements using a component-wise time series prediction model based on Statistical Recurrent Units (SRUs). We make a case that the network topology of Granger causal relations is directly inferrable from a structured sparse estimate of the internal parameters of the SRU networks trained to predict the processes$'$ time series measurements. We propose a variant of SRU, called economy-SRU, which, by design has considerably fewer trainable parameters, and therefore less prone to overfitting. The economy-SRU computes a low-dimensional sketch of its high-dimensional hidden state in the form of random projections to generate the feedback for its recurrent processing. Additionally, the internal weight parameters of the economy-SRU are strategically regularized in a group-wise manner to facilitate the proposed network in extracting meaningful predictive features that are highly time-localized to mimic real-world causal events. Extensive experiments are carried out to demonstrate that the proposed economy-SRU based time series prediction model outperforms the MLP, LSTM and attention-gated CNN-based time series models considered previously for inferring Granger causality.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples

Given side information that an Ising tree-structured graphical model is homogeneous and has no external field, we derive the exact asymptotics of learning its structure from independently drawn samples. Our results, which leverage the use of probabilistic tools from the theory of strong large deviations, refine the large deviation (error exponents) results of Tan, Anandkumar, Tong, and Willsky [IEEE Trans. on Inform. Th., 57(3):1714--1735, 2011] and strictly improve those of Bresler and Karzand [Ann. Statist., 2020]. In addition, we extend our results to the scenario in which the samples are observed in random noise. In this case, we show that they strictly improve on the recent results of Nikolakakis, Kalogerias, and Sarwate [Proc. AISTATS, 1771--1782, 2019]. Our theoretical results demonstrate keen agreement with experimental results for sample sizes as small as that in the hundreds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Exact and $\infty$-Rényi Common Informations

Recently, two extensions of Wyner's common information\textemdash exact and Rényi common informations\textemdash 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 $\infty$-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 $\infty$-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, $\infty$-Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Error Exponent of Approximate Sufficient Statistics for M-ary Hypothesis Testing

Consider the problem of detecting one of M i.i.d. Gaussian signals corrupted in white Gaussian noise. Conventionally, matched filters are used for detection. We first show that the outputs of the matched filter form a set of asymptotically optimal sufficient statistics in the sense of maximizing the error exponent of detecting the true signal. In practice, however, M may be large which motivates the design and analysis of a reduced set of N statistics which we term approximate sufficient statistics. Our construction of these statistics is based on a small set of filters that project the outputs of the matched filters onto a lower-dimensional vector using a sensing matrix. We consider a sequence of sensing matrices that has the desiderata of row orthonormality and low coherence. We analyze the performance of the resulting maximum likelihood (ML) detector, which leads to an achievable bound on the error exponent based on the approximate sufficient statistics; this bound recovers the original error exponent when N = M. We compare this to a bound that we obtain by analyzing a modified form of the Reduced Dimensionality Detector (RDD) proposed by Xie, Eldar, and Goldsmith [IEEE Trans. on Inform. Th., 59(6):3858-3874, 2013]. We show that by setting the sensing matrices to be column-normalized group Hadamard matrices, the exponents derived are ensemble-tight, i.e., our analysis is tight on the exponential scale given the sensing matrices and the decoding rule. Finally, we derive some properties of the exponents, showing, in particular, that they increase linearly in the compression ratio N/M.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Second- and Third-Order Asymptotics of the Continuous-Time Poisson Channel

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Second-Order Asymptotics of Sequential Hypothesis Testing

We consider the classical sequential binary hypothesis testing problem in which there are two hypotheses governed respectively by distributions $P_0$ and $P_1$ and 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(P_1\|P_0)$ and $D(P_0\|P_1)$. We refine this result by considering the optimal backoff---or second-order asymptotics---from the corner point of the achievable exponent region $(D(P_1\|P_0),D(P_0\|P_1))$ 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<\varepsilon <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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Thompson Sampling Algorithms for Mean-Variance Bandits

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 {\em 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Unsupervised Image Noise Modeling with Self-Consistent GAN

Noise modeling lies in the heart of many image processing tasks. However, existing deep learning methods for noise modeling generally require clean and noisy image pairs for model training; these image pairs are difficult to obtain in many realistic scenarios. To ameliorate this problem, we propose a self-consistent GAN (SCGAN), that can directly extract noise maps from noisy images, thus enabling unsupervised noise modeling. In particular, the SCGAN introduces three novel self-consistent constraints that are complementary to one another, viz.: the noise model should produce a zero response over a clean input; the noise model should return the same output when fed with a specific pure noise input; and the noise model also should re-extract a pure noise map if the map is added to a clean image. These three constraints are simple yet effective. They jointly facilitate unsupervised learning of a noise model for various noise types. To demonstrate its wide applicability, we deploy the SCGAN on three image processing tasks including blind image denoising, rain streak removal, and noisy image super-resolution. The results demonstrate the effectiveness and superiority of our method over the state-of-the-art methods on a variety of benchmark datasets, even though the noise types vary significantly and paired clean images are not available.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Variable-Length Source Dispersions Differ under Maximum and Average Error Criteria

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 $\varepsilon$-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 [\emph{{IEEE} Trans.\ Inf.\ Theory}, vol.~66, no.~3, pp.~1674--1690, 2020], are also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Fundamental Limits of Communication Over State-Dependent Channels With Feedback

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.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems

A (tandem) duplication of length $ k $ is an insertion of an exact copy of a substring of length $ k $ next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein's construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length $ k $. Furthermore, we derive bounds on the cardinality of optimal $ q $-ary codes correcting up to $ t $ duplications of length $ k $, and establish the following corollaries in the asymptotic regime of growing block-length: 1.) the presented family of codes is optimal for every $ q, t, k $, in the sense of the asymptotic scaling of code redundancy; 2.) the upper bound, when specialized to $ q = 2 $, $ k = 1 $, improves upon Levenshtein's bound for every $ t \geq 3 $; 3.) the bounds coincide for $ t = 1 $, thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Codes in the Space of Multisets---Coding for Permutation Channels with Impairments

Motivated by communication channels in which the transmitted sequences are subject 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 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 any alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Strong Converse for Hypothesis Testing Against Independence over a Two-Hop Network

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.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Discrete Lossy Gray-Wyner Revisited: Second-Order Asymptotics, Large and Moderate Deviations

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 (2015). 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ú (2012). The converse part uses a perturbation argument by Gu and Effros (2009) in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses two novel elements: (i) a generalization of various type covering lemmas; and (ii) 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.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Improved Bounds on Sidon Sets via Lattice Packings of Simplices

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 $ ϕ(h,n) $ denote the order of the smallest Abelian group containing a $ B_h $ set of cardinality $ n + 1 $. It is shown that \[ \lim_{h \to \infty} \frac{ ϕ(h,n) }{ h^n } = \frac{1}{n! δ_L(\triangle^n)} , \] where $ δ_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 $ ϕ(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.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Zero-Error Capacity of $P$-ary Shift Channels and FIFO Queues

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 zero-error 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 (FIFO) 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Numerical Study on the Wiretap Network with a Simple Network Topology

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 $n_1$ and $n_2$, 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~($<2\%$) 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....

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Proof of the Strong Converse Theorem for Gaussian Multiple Access Channels

We prove the strong converse for the $N$-source Gaussian multiple access channel (MAC). In particular, we show that any rate tuple that can be supported by a sequence of codes with asymptotic average error probability less than one 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 less than one to codes with asymptotic maximal error probability less than one. 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 less than one.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Achievable Rates for Gaussian Degraded Relay Channels with Non-Vanishing Error Probabilities

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 $\varepsilon$-capacity of the channel is characterized and it is strictly larger than the capacity for $\varepsilon>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 in terms of blocklength and error probability are also obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Adversarial Top-$K$ Ranking

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Analysis of Remaining Uncertainties and Exponents under Various Conditional Rényi Entropies

In this paper, 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 our study, 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 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 \emph{a posteriori} (MAP) decoding.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Empirical Output Distribution of Good Delay-Limited Codes for Quasi-Static Fading Channels

This paper considers delay-limited communication over quasi-static fading channels under a long-term power constraint. A sequence of length-$n$ delay-limited codes for a quasi-static fading channel is said to be capacity-achieving if the codes achieve the delay-limited capacity, which is defined to be the maximum rate achievable by delay-limited codes. The delay-limited capacity is sometimes referred to as the zero-outage capacity in wireless communications. The delay-limited capacity is the appropriate choice of performance measure for delay-sensitive applications such as voice and video over fading channels. It is shown that for any sequence of capacity-achieving delay-limited codes with vanishing error probabilities, the normalized relative entropy between the output distribution induced by the length-$n$ code and the $n$-fold product of the capacity-achieving output distribution, denoted by $\frac{1}{n}D(p_{Y^n}\|p_{Y^n}^*)$, converges to zero. Additionally, we extend our convergence result to capacity-achieving delay-limited codes with non-vanishing error probabilities.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Equivocations, Exponents and Second-Order Coding Rates under Various Rényi Information Measures

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Exact Moderate Deviation Asymptotics in Streaming Data Transmission

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Hypothesis Testing in the High Privacy Limit

Binary hypothesis testing under the Neyman-Pearson formalism is a statistical inference framework for distinguishing data generated by two different source distributions. Privacy restrictions may require the curator of the data or the data respondents themselves to share data with the test only after applying a randomizing privacy mechanism. Using mutual information as the privacy metric and the relative entropy between the two distributions of the output (postrandomization) source classes as the utility metric (motivated by the Chernoff-Stein Lemma), this work focuses on finding an optimal mechanism that maximizes the chosen utility function while ensuring that the mutual information based leakage for both source distributions is bounded. Focusing on the high privacy regime, an Euclidean information-theoretic (E-IT) approximation to the tradeoff problem is presented. It is shown that the solution to the E-IT approximation is independent of the alphabet size and clarifies that a mutual information based privacy metric preserves the privacy of the source symbols in inverse proportion to their likelihood.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Non-Asymptotic Achievable Rates for Energy-Harvesting Channels using Save-and-Transmit

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-and-transmit 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 $-\sqrt{ \frac{\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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Gaussian Channels with Feedback under Expected Power Constraints and with Non-Vanishing Error Probabilities

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 $\varepsilon$-capacity and show that it depends on $\varepsilon$ 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)}(\cdot)$ is the $L$-fold nested logarithm function) and a term proportional to $+\sqrt{n\ln n}$ 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 $\varepsilon$-capacity region for the AWGN multiple access channel (MAC) with feedback under the expected power constraint by combining ideas from hypothesis testing, information spectrum analysis, Ozarow's coding scheme, and power control.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Scaling Exponent of Polar Codes for Binary-Input Energy-Harvesting Channels

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 i.i.d. random variables with finite variances. The scaling exponent $μ$ of polar codes for a binary-input memoryless channel (BMC) characterizes the closest gap between the capacity and non-asymptotic rates achieved by polar codes with error probabilities no larger than some non-vanishing $\varepsilon\in(0,1)$. It has been shown that for any $\varepsilon\in(0,1)$, the scaling exponent $μ$ for any binary-input memoryless symmetric channel (BMSC) with $I(q_{Y|X})\in(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. The main result is proved by leveraging the following three existing results: scaling exponent analyses for BMSCs, construction of polar codes designed for binary-input memoryless asymmetric channels, and the save-and-transmit strategy for EH channels.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Nonnegative Matrix Factorization with General Divergences

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 algorithm makes it 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. We do so by leveraging the theory of stochastic approximations and projected dynamical systems. This result substantially generalizes the previous results obtained only for the squared-$\ell_2$ loss. Moreover, the novel techniques involved in our analysis open new avenues for analyzing similar matrix factorization problems. The computational efficiency and the quality of the learned dictionary of our algorithm are verified empirically on both synthetic and real datasets. In particular, on the tasks of topic learning, shadow removal and image denoising, our algorithm achieves superior trade-offs between the quality of learned dictionary and running time over the batch and other online NMF algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Nonnegative Matrix Factorization with Outliers

We propose a unified and systematic framework for performing online nonnegative matrix factorization in the presence of outliers. Our framework is particularly suited to large-scale data. We propose two solvers based on projected gradient descent and the alternating direction method of multipliers. We prove that the sequence of objective values converges almost surely by appealing to the quasi-martingale convergence theorem. We also show the sequence of learned dictionaries converges to the set of stationary points of the expected loss function almost surely. In addition, we extend our basic problem formulation to various settings with different constraints and regularizers. We also adapt the solvers and analyses to each setting. We perform extensive experiments on both synthetic and real datasets. These experiments demonstrate the computational efficiency and efficacy of our algorithms on tasks such as (parts-based) basis learning, image denoising, shadow removal and foreground-background separation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Second-Order and Moderate Deviation Asymptotics for Successive Refinement

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: (i) a discrete memoryless source (DMS) and arbitrary distortion measures at the decoders and (ii) 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 to 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Dispersion of Nearest-Neighbor Decoding for Additive Non-Gaussian Channels

We study the second-order asymptotics of information transmission using random Gaussian codebooks and nearest neighbor (NN) 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 interferring codewords only through their sum, this does not hold for the second-order term.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymmetric Evaluations of Erasure and Undetected Error Probabilities

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 analysing the ensemble performance in terms of a tradeoff between the code rate, the undetected and the total errors. This tradeoff is parametrized 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/2}$ corresponding 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(- b n^{ 1/2})$ for some $b>0$. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities

This monograph presents a unified treatment of single- and multi-user problems in Shannon's information theory where we depart from the requirement that the error probability decays asymptotically in the blocklength. Instead, the error probabilities for various problems are bounded above by a non-vanishing constant and the spotlight is shone on achievable coding rates as functions of the growing blocklengths. This represents the study of asymptotic estimates with non-vanishing error probabilities. In Part I, after reviewing the fundamentals of information theory, we discuss Strassen's seminal result for binary hypothesis testing where the type-I error probability is non-vanishing and the rate of decay of the type-II error probability with growing number of independent observations is characterized. In Part II, we use this basic hypothesis testing result to develop second- and sometimes, even third-order asymptotic expansions for point-to-point communication. Finally in Part III, we consider network information theory problems for which the second-order asymptotics are known. These problems include some classes of channels with random state, the multiple-encoder distributed lossless source coding (Slepian-Wolf) problem and special cases of the Gaussian interference and multiple-access channels. Finally, we discuss avenues for further research.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Error and Erasure Exponents for the Broadcast Channel with Degraded Message Sets

Error and erasure exponents for the broadcast channel with degraded message sets are analyzed. The focus of our error probability analysis is on the main receiver where, nominally, both messages are to be decoded. A two-step decoding algorithm is proposed and analyzed. This receiver first attempts to decode both messages, failing which, it attempts to decode only the message representing the coarser information, i.e., the cloud center. This algorithm reflects the intuition that we should decode both messages only if we have confidence in the estimates; otherwise one should only decode the coarser information. The resulting error and erasure exponents, derived using the method of types, are expressed in terms of a penalized form of the modified random coding error exponent.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Second-Order Asymptotics for the Classical Capacity of Image-Additive Quantum Channels

We study non-asymptotic fundamental limits for transmitting classical information over memoryless quantum channels, i.e. we investigate the amount of classical information that can be transmitted when a quantum channel is used a finite number of times and a fixed, non-vanishing average error is permissible. We consider the classical capacity of quantum channels that are image-additive, including all classical to quantum channels, as well as the product state capacity of arbitrary quantum channels. In both cases we show that the non-asymptotic fundamental limit admits a second-order approximation that illustrates the speed at which the rate of optimal codes converges to the Holevo capacity as the blocklength tends to infinity. The behavior is governed by a new channel parameter, called channel dispersion, for which we provide a geometrical interpretation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Second-Order Asymptotics for the Discrete Memoryless MAC with Degraded Message Sets

This paper studies the second-order asymptotics of the discrete memoryless multiple-access channel with degraded message sets. For a fixed average error probability $ε\in(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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Second-Order Asymptotics for the Gaussian MAC with Degraded Message Sets

This paper studies the second-order asymptotics of the Gaussian multiple-access channel with degraded message sets. For a fixed average error probability $\varepsilon \in (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 $\varepsilon$. As a stepping stone to this local notion of 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Streaming Data Transmission in the Moderate Deviations and Central Limit Regimes

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 i) in the moderate deviations regime, the moderate deviations constant improves over the block coding or non-streaming setup by a factor of $T$ and ii) in the central limit regime, the second-order coding rate improves by a factor of approximately $\sqrt{T}$ for a wide range of channel parameters. For both 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 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. Finally, we also extend our results to the case where the message rate is not fixed but alternates between two values.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Strong Converse Theorems for Classes of Multimessage Multicast Networks: A Rényi Divergence Approach

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 necessarily tend to one (and are not simply bounded away from zero). 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Case Where Interference Does Not Affect The Channel Dispersion

In 1975, Carleial presented a special case of an interference channel in which the interference does not reduce the capacity of the constituent point-to-point Gaussian channels. In this work, we show that if the inequalities in the conditions that Carleial stated are strict, the dispersions are similarly unaffected. More precisely, in this work, 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 towards a boundary point of the (rectangular) capacity region. These second-order rates are expressed in terms of the average probability of error and variances of some modified information densities which coincide with the dispersion of the (single-user) Gaussian channel. We thus conclude that the dispersions are unaffected by interference in this channel model.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Formula for the Capacity of the General Gel'fand-Pinsker Channel

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 state are memoryless but not necessarily stationary.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Asymptotic Expansions for Gaussian Channels with Feedback under a Peak Power Constraint

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, 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 a self-contained proof of 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. An auxiliary contribution is a proof of the strong converse for the parallel Gaussian channels with feedback under a peak power constraint.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fixed Error Asymptotics For Erasure and List Decoding

We derive the optimum second-order coding rates, known as second-order capacities, for erasure and list decoding. For erasure decoding for discrete memoryless channels, we show that second-order capacity is $\sqrt{V}Φ^{-1}(ε_t)$ where $V$ is the channel dispersion and $ε_t$ is 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. We also show that the analogous result also holds for lossless source coding with decoder side information, i.e., Slepian-Wolf coding. For list decoding, we consider list codes of deterministic size that scales as $\exp(\sqrt{n}l)$ and show that the second-order capacity is $l+\sqrt{V}Φ^{-1}(ε)$ where $ε$ is the permissible error probability. We also consider lists of polynomial size $n^α$ and derive bounds on the third-order coding rate in terms of the order of the polynomial $α$. These bounds are tight for symmetric and singular channels. The direct parts of the coding theorems leverage on the simple threshold decoder and converses are proved using variants of the hypothesis testing converse.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Information Spectrum Approach to Strong Converse Theorems for Degraded Wiretap Channels

We consider block codes for degraded wiretap channels in which the legitimate receiver decodes the message with an asymptotic error probability no larger than $\varepsilon$ but the leakage to the eavesdropper vanishes. For discrete memoryless and Gaussian wiretap channels, we show that the maximum rate of transmission does not depend on $\varepsilon\in [0,1)$, i.e., such channels possess the partial strong converse property. Furthermore, we derive sufficient conditions for the partial strong converse property to hold for memoryless but non-stationary symmetric and degraded wiretap channels. Our proof techniques leverage the information spectrum method, which allows us to establish a necessary and sufficient condition for the partial strong converse to hold for general wiretap channels without any information stability assumptions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Non-Asymptotic and Second-Order Achievability Bounds for Coding With Side-Information

We present novel non-asymptotic or finite blocklength achievability bounds for three side-information problems in network information theory. These include (i) the Wyner-Ahlswede-Korner (WAK) problem of almost-lossless source coding with rate-limited side-information, (ii) the Wyner-Ziv (WZ) problem of lossy source coding with side-information at the decoder and (iii) 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 non-asymptotic bounds on the error probability of the WAK, WZ and GP problems--in particular those derived by Verdu. Using our novel non-asymptotic 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-Esseen theorem to our new non-asymptotic bounds. Numerical results show that the second-order coding rates obtained using our non-asymptotic achievability bounds are superior to those obtained using existing finite blocklength bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Reliability Function of the Discrete Memoryless Relay Channel

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Second-Order Coding Rates for Channels with State

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 epsilon-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 i.i.d. and Markov states and mixed channels.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Second-Order Coding Rates for Conditional Rate-Distortion

This paper characterizes the second-order coding rates for lossy source coding with side information available at both the encoder and the decoder. We first provide non-asymptotic bounds for this problem and then specialize the non-asymptotic bounds for three different scenarios: discrete memoryless sources, Gaussian sources, and Markov sources. We obtain the second-order coding rates for these settings. It is interesting to observe that the second-order coding rate for Gaussian source coding with Gaussian side information available at both the encoder and the decoder is the same as that for Gaussian source coding without side information. Furthermore, regardless of the variance of the side information, the dispersion is $1/2$ nats squared per source symbol.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Unequal Message Protection: Asymptotic and Non-Asymptotic Tradeoffs

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 of these codes. We demonstrate that there is a clear performance loss compared to homogeneous (classical) codes with equivalent parameters. This is in sharp contrast to previous literature that considers 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 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Tight Upper Bound for the Third-Order Asymptotics for Most Discrete Memoryless Channels

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

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Dispersions of Discrete Memoryless Channels with Noncausal State Information at the Encoder

In this paper, we study the finite blocklength limits of state-dependent discrete memoryless channels where the discrete memoryless state is known noncausally at the encoder. For the point-to-point case, this is known as the Gel'fand-Pinsker channel model. We define the (n,ε)-capacity of the Gel'fand-Pinsker channel as the maximal rate of transmission of a message subject to the condition that the length of the block-code is n and the average error probability is no larger than ε. This paper provides a lower bound for the (n,ε)-capacity of the Gel'fand-Pinsker channel model, and hence an upper bound on the dispersion, a fundamental second-order quantity in the study of the performance limits of discrete memoryless channels. In addition, we extend the work of Y. Steinberg (2005), in which the (degraded) broadcast channel extension of the Gel'fand-Pinsker model was studied. We provide and inner bound to the (n,ε)-capacity region for this broadcast channel model using a combination of ideas of Gel'fand-Pinsker coding, superposition coding and dispersion (finite blocklength) analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Dispersions of Three Network Information Theory Problems

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 non-asymptotic rate region converges to the Slepian-Wolf boundary, we define and characterize two operational dispersions: the local dispersion and the weighted sum-rate dispersion. The former represents the rate of convergence to a point on the Slepian-Wolf boundary while 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 a so-called vector rate redundancy theorem which is proved using the multidimensional Berry-Esseen theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Sender-Excited Secret Key Agreement Model: Capacity, Reliability and Secrecy Exponents

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Automatic Relevance Determination in Nonnegative Matrix Factorization with the β-Divergence

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 and Itakura-Saito 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 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 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion

We consider the problem of high-dimensional Gaussian graphical model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n=omega(J_{min}^{-2} log p), where p is the number of variables and J_{min} is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

High-dimensional structure estimation in Ising models: Local separation criterion

We consider the problem of high-dimensional Ising (graphical) model selection. We propose a simple algorithm for structure estimation based on the thresholding of the empirical conditional variation distances. We introduce a novel criterion for tractable graph families, where this method is efficient, based on the presence of sparse local separators between node pairs in the underlying graph. For such graphs, the proposed algorithm has a sample complexity of $n=Ω(J_{\min}^{-2}\log p)$, where $p$ is the number of variables, and $J_{\min}$ is the minimum (absolute) edge potential in the model. We also establish nonasymptotic necessary and sufficient conditions for structure estimation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Moderate-Deviations of Lossy Source Coding for Discrete and Gaussian Sources

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) \pm ε_n$, where $R(D)$ is the rate-distortion function and $ε_n$ is a sequence that dominates $\sqrt{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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Wireless Compressive Sensing for Energy Harvesting Sensor Nodes

We consider the scenario in which multiple sensors send spatially correlated data to a 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 this sparse signal can be formulated as a compressive sensing (CS) problem. To model the scenario in which the 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. This is referred to as the inhomogeneity of SNRs. Thus, the elements of the sensing matrix are also not identically distributed. For this unconventional setting, we provide theoretical guarantees on the number of measurements for reliable and computationally efficient recovery, by showing that the sensing matrix satisfies the restricted isometry property (RIP), under reasonable 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 SNRs on the so-called k-restricted eigenvalues, which governs the number of measurements required for the RIP to hold. We conclude that the number of measurements required for the RIP is not sensitive to the inhomogeneity of SNRs, when the number of sensors n is large and the sparsity of the sensor data (signal) k grows slower than the square root of n. Our analysis is corroborated by extensive numerical results.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Canonical Estimation in a Rare-Events Regime

We propose a general methodology for performing statistical inference within a `rare-events regime' that was recently suggested by Wagner, Viswanath and Kulkarni. Our approach allows one to easily establish consistent estimators for a very large class of canonical estimation problems, in a large alphabet setting. These include the problems studied in the original paper, such as entropy and probability estimation, in addition to many other interesting ones. We particularly illustrate this approach by consistently estimating the size of the alphabet and the range of the probabilities. We start by proposing an abstract methodology based on constructing a probability measure with the desired asymptotic properties. We then demonstrate two concrete constructions by casting the Good-Turing estimator as a pseudo-empirical measure, and by using the theory of mixture model estimation.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Rank Minimization over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations

This paper establishes information-theoretic limits in 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, Ω(nlog 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 above 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 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. Finally, we provide a non-exhaustive procedure to search for the unknown low-rank matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures

The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that the extremal tree structure that minimizes the error exponent is the star for any fixed set of correlation coefficients on the edges of the tree. If the magnitudes of all the correlation coefficients are less than 0.63, it is also shown that the tree structure that maximizes the error exponent is the Markov chain. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Learning Latent Tree Graphical Models

We study the problem of learning a latent tree graphical model where samples are available only from a subset of variables. We propose two consistent and computationally efficient algorithms for learning minimal latent trees, that is, trees without any redundant hidden nodes. Unlike many existing methods, the observed nodes (or variables) are not constrained to be leaf nodes. Our first algorithm, recursive grouping, builds the latent tree recursively by identifying sibling groups using so-called information distances. One of the main contributions of this work is our second algorithm, which we refer to as CLGrouping. CLGrouping starts with a pre-processing procedure in which a tree over the observed variables is constructed. This global step groups the observed nodes that are likely to be close to each other in the true latent tree, thereby guiding subsequent recursive grouping (or equivalent procedures) on much smaller subsets of variables. This results in more accurate and efficient learning of latent trees. We also present regularized versions of our algorithms that learn latent tree approximations of arbitrary distributions. We compare the proposed algorithms to other methods by performing extensive numerical experiments on various latent tree graphical models such as hidden Markov models and star graphs. In addition, we demonstrate the applicability of our methods on real-world datasets by modeling the dependency structure of monthly stock returns in the S&P index and of the words in the 20 newsgroups dataset.

0 citations0 reviewsNo code linkedOpen access