We explore the capability of transformers to address endogeneity in in-context linear regression. Our main finding is that transformers inherently possess a mechanism to handle endogeneity effectively using instrumental variables (IV). First, we demonstrate that the transformer architecture can emulate a gradient-based bi-level optimization procedure that converges to the widely used two-stage least squares (2SLS) solution at an exponential rate. Next, we propose an in-context pretraining scheme and provide theoretical guarantees showing that the global minimizer of the pre-training loss achieves a small excess loss. Our extensive experiments validate these theoretical findings, showing that the trained transformer provides more robust and reliable in-context predictions and coefficient estimates than the 2SLS method, in the presence of endogeneity.

Discrete state space diffusion models have shown significant advantages in applications involving discrete data, such as text and image generation. It has also been observed that their performance is highly sensitive to the choice of rate matrices, particularly between uniform and absorbing rate matrices. While empirical results suggest that absorbing rate matrices often yield better generation quality compared to uniform rate matrices, existing theoretical works have largely focused on the uniform rate matrices case. Notably, convergence guarantees and error analyses for absorbing diffusion models are still missing. In this work, we provide the first finite-time error bounds and convergence rate analysis for discrete diffusion models using absorbing rate matrices. We begin by deriving an upper bound on the KL divergence of the forward process, introducing a surrogate initialization distribution to address the challenge posed by the absorbing stationary distribution, which is a singleton and causes the KL divergence to be ill-defined. We then establish the first convergence guarantees for both the $\tau$-leaping and uniformization samplers under absorbing rate matrices, demonstrating improved rates over their counterparts using uniform rate matrices. Furthermore, under suitable assumptions, we provide convergence guarantees without early stopping. Our analysis introduces several new technical tools to address challenges unique to absorbing rate matrices. These include a Jensen-type argument for bounding forward process convergence, novel techniques for bounding absorbing score functions, and a non-divergent upper bound on the score near initialization that removes the need of early-stopping.

Discrete diffusion models have recently gained significant prominence in applications involving natural language and graph data. A key factor influencing their effectiveness is the efficiency of discretized samplers. Among these, $\tau$-leaping samplers have become particularly popular due to their theoretical and empirical success. However, existing theoretical analyses of $\tau$-leaping often rely on somewhat restrictive and difficult-to-verify regularity assumptions, and their convergence bounds contain quadratic dependence on the vocabulary size. In this work, we introduce a new analytical approach for discrete diffusion models that removes the need for such assumptions. For the standard $\tau$-leaping method, we establish convergence guarantees in KL divergence that scale linearly with vocabulary size, improving upon prior results with quadratic dependence. Our approach is also more broadly applicable: it provides the first convergence guarantees for other widely used samplers, including the Euler method and Tweedie $\tau$-leaping. Central to our approach is a novel technique based on differential inequalities, offering a more flexible alternative to the traditional Girsanov change-of-measure methods. This technique may also be of independent interest for the analysis of other stochastic processes.

In this paper, we investigate the beamforming and power control issue in cellular-connected unmanned aerial vehicle (UAV) communications under full-duplex (FD). To mitigate the self-interference (SI), we adopt a decoupled uplink (UL)-downlink (DL) association for UAVs to spatially separate the transmit and receive beams. Then, we formulate a joint beamforming and power control problem to maximize the system’s spectral efficiency (SE) while ensuring each UAV meets its UL transmission rate and DL latency requirements. To solve this problem, we design a novel distributed heterogeneous graph neural network (HGNN) architecture for beamforming and power control with a low signaling overhead. Simulation results demonstrate that our proposed scheme outperforms the existing schemes in terms of the total SE, UL transmission rate and DL latency.

Cellular-connected unmanned aerial vehicle (UAV) communications provides UAVs with ubiquitous connectivity via cellular networks. Introducing full-duplex (FD) technology into cellular-connected UAV communications to enable real-time bidirectional traffic applications, such as emergency rescue. However, severe self-interference (SI) under FD can lead to performance degradation, particularly with a coupled uplink-downlink (UL-DL) association. To address this issue, we adopt a decoupled UL-DL association (DUDA), which achieves spatial separation of transmit and receive beams to reduce SI. However, existing DUDA policies, which rely on minimum path loss (PL), are not optimal under FD. Therefore, we propose an adaptive multi-criteria decoupling scheme based on fuzzy logic (FL) to further reduce SI. In particular, we first consider the PL, the base station (BS)-UAV-BS angle, and the BS loads as the multiple criteria. We then use FL to integrate these criteria and generate scores for each BS. Finally, we can adaptively decouple the UL-DL association based on these calculated scores. Simulation results demonstrate that the proposed decoupling scheme can significantly mitigate SI and improve the average transmission rate in DL and UL.

Beam tracking is a promising technology in mmWave-enabled cellular-connected unmanned aerial vehicle (UAV) communications. However, conventional beam tracking schemes always incur a large training overhead, and it is difficult to determine the time duration of a training cycle due to the high mobility of UAVs, which is essential for improving the effective achievable rate (EAR). To address this issue, we first adopt angular velocity estimation to obtain the beam coherence time, which serves as the time duration of the training cycles. To further reduce the training overhead in each training cycle, we then design an adaptive beam tracking algorithm based on bandit learning, where the actions are taken based on the accuracy of the angular velocity estimation. If the estimation is not accurate, more beams will be swept in the next cycle. In this way, the beam misalignment incurred by estimation inaccuracy will largely alleviate. Thus, the EAR can be effectively improved with smaller training overhead. The simulation results demonstrate the superior performance of the proposed algorithm in terms of the training overhead and the EAR.

Bilevel optimization is one of the fundamental problems in machine learning and optimization. Recent theoretical developments in bilevel optimization focus on finding the first-order stationary points for nonconvex-strongly-convex cases. In this paper, we analyze algorithms that can escape saddle points in nonconvex-strongly-convex bilevel optimization. Specifically, we show that the perturbed approximate implicit differentiation (AID) with a warm start strategy finds an $\epsilon$-approximate local minimum of bilevel optimization in $\tilde{O}(\epsilon^{-2})$ iterations with high probability. Moreover, we propose an inexact NEgative-curvature-Originated-from-Noise Algorithm (iNEON), an algorithm that can escape saddle point and find local minimum of stochastic bilevel optimization. As a by-product, we provide the first nonasymptotic analysis of perturbed multi-step gradient descent ascent (GDmax) algorithm that converges to local minimax point for minimax problems.

Standard reinforcement learning (RL) algorithms primarily focus on minimizing the expected sum of costs, which can be insufficient in contexts where risk sensitivity is crucial. This paper explores the application of a class of coherent risk measures, termed ϕ-Divergence-Risk (PhiD-R) in risk-sensitive RL. This class of risk measures not only includes established measures such as Conditional Value-at-Risk (CVaR) as special cases but also broadens the horizon for exploring new risk measures. We propose a trajectory-based policy gradient method specifically tailored for PhiD-R, applicable across all forms of risk measures formed by different ϕ-divergence. We prove the asymptotic convergence of our algorithm towards locally optimal policies using multi-time stochastic approximation techniques. Extensive simulation experiments validate the effectiveness and practicality of our approach.

Markov decision process (MDP) is an important model of sequential decision making problems. Existing theoretical analysis focus primarily on finite state spaces. For continuous state spaces, a recent interesting work (Shah and Xie, 2018) proposes a nearest neighbor Q learning approach. Under the streaming setting, in shich samples are received in a sequential manner, the sample complexity of this method is$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+3}(1-\gamma)^{d+7}}}}\right)$for$\epsilon $-accurate Q function estimation of infinite horizon discounted MDP with discount factor$\gamma $, in which$|\mathcal {A}|$is the size of the action space. However, the sample complexity is not optimal, and the method is suitable only for bounded state spaces. In this paper, we propose two new nearest neighbor Q learning methods, one for the offline setting and the other for the streaming setting. We show that the sample complexities of these two methods are$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+2}(1-\gamma)^{d+2}}}}\right)$and$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+2}(1-\gamma)^{d+3}}}}\right)$for offline and streaming settings respectively, which significantly improve over existing results and have minimax optimal dependence over$\epsilon $. We achieve such improvement by utilizing samples more efficiently. In particular, the method by Shah and Xie, 2018, clears up all samples after each iteration, thus these samples are somewhat wasted. On the other hand, our offline method does not remove any samples, and our streaming method only removes samples with time earlier than$\beta t$at time t, thus our methods significantly reduce the loss of information. Apart from the sample complexity, our methods also have additional advantages of better computational complexity, as well as suitability to unbounded state spaces. Finally, we extend our work to the case where both state and action spaces are continuous.

This paper delves into the subject of designing a tree network, enabling the application of Distributed Dual Coordinate Ascent on a general tree network (DDCA-Tree) introduced in [1] – [3] for distributed Machine Learning (ML) process. We assume that a network is characterized by communication delays proportional to the distance between any two nodes. To efficiently managing distributed data across the network, we propose the Minimum Worst-Distance Tree (MWDT) algorithm for designing a tree network with a specified target depth yielding a network structure where the communication delay in worst path between a leaf node and its parent node is minimized, consequently enhancing the convergence speed of DDCA-Tree. In numerical experiments, to validate the effectiveness of our approach, we compared the communication delay in worst path on a tree network generated by our algorithm against a minimum spanning tree which provides minimum weight (i.e., distance) sum, and showed our network design has reduced distance in worst path.

Exploration is a crucial phase in reinforcement learning (RL). The reward-free RL paradigm, as explored by (Jin et al., 2020), offers an efficient method to design exploration algorithms for risk-neutral RL across various reward functions with a single exploration phase. However, as RL applications in safety critical settings grow, there’s an increasing need for risk-sensitive RL, which considers potential risks in decision-making. Yet, efficient exploration strategies for risk-sensitive RL remain underdeveloped. This study presents a novel risk-sensitive reward-free framework based on Conditional Value-at-Risk (CVaR), designed to effectively address CVaR RL for any given reward function through a single exploration phase. We introduce the CVaR-RF-UCRL algorithm, which is shown to be $(\epsilon,p)$-PAC, with a sample complexity upper bounded by $\tilde{\mathcal{O}}\left(\frac{S^2AH^4}{\epsilon^2\tau^2}\right)$ with $\tau$ being the risk tolerance parameter. We also prove a $\Omega\left(\frac{S^2AH^2}{\epsilon^2\tau}\right)$ lower bound for any CVaR-RF exploration algorithm, demonstrating the near-optimality of our algorithm. Additionally, we propose the planning algorithms: CVaR-VI and its more practical variant, CVaR-VI-DISC. The effectiveness and practicality of our CVaR reward-free approach are further validated through numerical experiments.

The multi-agent reinforcement learning systems (MARL) based on the Markov decision process (MDP) have emerged in many critical applications. To improve the robust-ness/defense of MARL systems against adversarial attacks, the study of various adversarial attacks on reinforcement learning systems is very important. Previous works on adversarial attacks considered some possible features to attack in MDP, such as the action poisoning attacks, the reward poisoning attacks, and the state perception attacks. In this paper, we propose a brand-new form of attack called the camouflage attack in the MARL systems. In the camouflage attack, the attackers change the appearances of some objects without changing the actual objects themselves; and the camouflaged appearances may look the same to all the targeted recipient (victim) agents. The camouflaged appearances can mislead the recipient agents to misguided actions. We design algorithms that give the optimal camouflage attacks minimizing the rewards of recipient agents. Our numerical and theoretical results show that camouflage attacks can rival the more con-ventional, but likely more difficult state perception attacks. We also investigate cost-constrained camouflage attacks and showed numerically how cost budgets affect the attack performance.

Robust Markov Decision Processes (RMDPs) have received significant research interest, offering an alternative to standard Markov Decision Processes (MDPs) that often assume fixed transition probabilities. RMDPs address this by optimizing for the worst-case scenarios within ambiguity sets. While earlier studies on RMDPs have largely centered on risk-neutral rein-forcement learning (RL), with the goal of minimizing expected total discounted costs, in this paper, we analyze the robustness of CVaR-based risk-sensitive RL under RMDP. Firstly, we consider predetermined ambiguity sets. Based on the coherency of CVaR, we establish a connection between robustness and risk sensitivity, thus, techniques in risk-sensitive RL can be adopted to solve the proposed problem. Furthermore, motivated by the existence of decision-dependent uncertainty in real-world problems, we study problems with state-action-dependent ambiguity sets. To solve this, we define a new risk measure named NCVaR and build the equivalence of NCVaR optimization and robust CVaR optimization. We further propose value iteration algorithms and validate our approach in simulation experiments.

Privacy protection of users' entire contribution of samples is important in distributed systems. The most effective approach is the two-stage scheme, which finds a small interval first and then gets a refined estimate by clipping samples into the interval. However, the clipping operation induces bias, which is serious if the sample distribution is heavy-tailed. Besides, users with large local sample sizes can make the sensitivity much larger, thus the method is not suitable for imbalanced users. Motivated by these challenges, we propose a Huber loss minimization approach to mean estimation under user-level differential privacy. The connecting points of Huber loss can be adaptively adjusted to deal with imbalanced users. Moreover, it avoids the clipping operation, thus significantly reducing the bias compared with the two-stage approach. We provide a theoretical analysis of our approach, which gives the noise strength needed for privacy protection, as well as the bound of mean squared error. The result shows that the new method is much less sensitive to the imbalance of user-wise sample sizes and the tail of sample distributions. Finally, we perform numerical experiments to validate our theoretical analysis.

This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, (Scetbon et al., 2021) suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating maximization algorithm (PAM) to solve the dual of the entropy regularized EOT. In this paper, we provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that can numerically improve the performance of PAM. Results in this paper may shed lights on block coordinate (gradient) descent methods for general optimization problems.

Fairness and robustness are critical elements of trustworthy machine learning systems that need to be addressed. Using a minimax framework, in this paper, we aim to design an adversarially robust fair regression model that achieves optimal performance in the presence of an attacker who is able to perform a rank-one attack on the dataset. By solving the proposed nonsmooth nonconvex-nonconcave minimax problem, the optimal adversary as well as the robust fairness-aware regression model are obtained. Based on two real-world datasets, numerical results illustrate that the proposed adversarially robust fair model has better performance on the poisoned dataset than other fair machine learning models in both prediction accuracy and group-based fairness measure.

Entropy rate estimation has a broad range of applications such as bioinformatics, feature clustering etc. Although there are many existing work on the estimation of entropy rate for Markov chains with discrete distributions, the understanding for the entropy rate estimation of Markov chains with continuous distributions is limited. In this paper, efficient methods for estimating the entropy rate for Markov chains with continuous distributions are proposed. Moreover, we derive bounds on the convergence rate of the proposed entropy rate estimators.

Due to the broad range of applications of multi-agent reinforcement learning (MARL), understanding the effects of adversarial attacks against MARL model is essential for the safe applications of this model. Motivated by this, we investigate the impact of adversarial attacks on MARL. In the considered setup, there is an exogenous attacker who is able to modify the rewards before the agents receive them or manipulate the actions before the environment receives them. The attacker aims to guide each agent into a target policy or maximize the cumulative rewards under some specific reward function chosen by the attacker, while minimizing the amount of the manipulation on feedback and action. We first show the limitations of the action poisoning only attacks and the reward poisoning only attacks. We then introduce a mixed attack strategy with both the action poisoning and reward poisoning. We show that the mixed attack strategy can efficiently attack MARL agents even if the attacker has no prior information about the underlying environment and the agents’ algorithms.

In this paper, we formulate and solve a two-stage Bayesian sequential change diagnosis (SCD) problem in a multi-sensor setting. In the considered problem, a change first occurs at a sensor and then propagates across the sensor array gradually. After a change is detected, we are allowed to continue observing more samples so that we can identify the distribution after the change more accurately. Our goal is to minimize the total cost including delay, false alarm, and misdiagnosis probabilities. We first characterize the optimal SCD rule. Moreover, to address the high computational complexity issue of the optimal SCD rule, we propose a low-complexity threshold SCD rule. We further analyze the asymptotic optimality of the threshold SCD rule. In addition, we investigate how increasing the number of sensors can improve the performance of the proposed threshold SCD rule. Our analysis holds for different sensor array structures, including linear sensor arrays and 2D lattice sensor arrays.

In this paper, we develop a framework to achieve a desirable trade-off between fairness, inference accuracy and privacy protection in the inference as service scenario. Instead of sending raw data to the cloud, we conduct a random mapping of the data, which will increase privacy protection and mitigate bias but reduce inference accuracy. To properly address the trade-off, we formulate an optimization problem to find the optimal transformation map. As the problem is non-convex in general, we develop an iterative algorithm to find the desired map. Numerical examples show that the proposed method has better performance than gradient ascent in the convergence speed, solution quality and algorithm stability.

In this paper, we consider the dynamic content caching issue in the cache-enabled Internet of Things (IoT) systems. For real-time applications in cache-enabled IoT systems, it is imperative to design dynamic content caching schemes to reduce the energy consumption of sensors and improve the freshness of information at users. We first design a dynamic content caching procedure for a cache-enabled IoT system with limited cache capacity and express the evolution of the Age of Information (AoI) at both the edge caching node and each user. Then, we formulate the dynamic content caching problem as a Markov Decision Process to minimize the expectation of a long-term accumulative cost, which jointly considers the average AoI of users and the energy consumption of sensors. To solve this problem, we propose an actor-critic based caching algorithm without prior knowledge of users’ content demands. The numerical results show that the proposed algorithm can achieve lower average AoI and energy consumption than other baselines.

We analyze the convergence rates of$k$nearest neighbor density estimation method, under$\ell _{\alpha} $norm with$\alpha \in [1,\infty]$. Our analysis includes two different cases depending on whether the support set is bounded or not. In the first case, the probability density function has a bounded support. We show that if the support set is known, then the kNN density estimator is minimax optimal under$\ell _{\alpha} $with both$\alpha \in \big[1,\infty\big)$and$\alpha =\infty $. If the support is unknown, the kNN density estimator is still minimax optimal under$\ell _{1}$, but is suboptimal under$\ell _{\alpha} $for$\alpha >1$, and not consistent under$\ell _\infty $. In the second case, the support is unbounded and the probability density function is smooth everywhere. Moreover, the Hessian is assumed to decay with the density values. For this case, our result shows that the$\ell _\infty $error of kNN density estimation is nearly minimax optimal. The$\ell _{\alpha} $error for the original kNN density estimator is not consistent. To address this issue, we design a new adaptive kNN estimator, which can select different$k$for different samples. Using this adaptive estimator, the$\ell _{\alpha} $bound is minimax optimal. For comparison, we show that the popular kernel density estimator is not minimax optimal for this case.

In this paper, we propose an adaptive kNN method for classification, in which different k are selected for different test samples. Our selection rule is easy to implement since it is completely adaptive and does not require any knowledge of the underlying distribution. The convergence rate of the risk of this classifier to the Bayes risk is shown to be minimax optimal for various settings. Moreover, under some special assumptions, the convergence rate is especially fast and does not decay with the increase of dimensionality.

In this paper, we propose a general framework to provide a desirable trade-off between inference accuracy and privacy protection in the inference as service scenario. Instead of sending data directly to the server, the user will preprocess the data through a privacy-preserving mapping, which will increase privacy protection but reduce inference accuracy. To properly address the trade-off between privacy protection and inference accuracy, we formulate an optimization problem to find the optimal privacy-preserving mapping. Even though the problem is non-convex in general, we characterize nice structures of the problem and develop an iterative algorithm to find the desired privacy-preserving mapping.

In this paper, we investigate the adversarial robustness of principal component analysis (PCA) algorithms. In the considered setup, there is a powerful adversary who can add a carefully designed data point to the original data matrix. The goal of the adversary is to maximize the distance between the subspace learned from the original data and the subspace obtained from the modified data. Different from most of the existing research using Asimov distance to measure such a distance, we leverage a more precise and sophisticated measurement, Chordal distance, which can be used to analyze the influence of an outlier on PCA more comprehensively. Our analysis shows that the first principal angle can be completely changed by an outlier and the second principal angle changes very little. We also demonstrate the performance of our strategy with experimental results on synthetic data and real data.

The Wasserstein distance has become increasingly important in machine learning and deep learning. Despite its popularity, the Wasserstein distance is hard to approximate because of the curse of dimensionality. A recently proposed approach to alleviate the curse of dimensionality is to project the sampled data from the high dimensional probability distribution onto a lower-dimensional subspace, and then compute the Wasserstein distance between the projected data. However, this approach requires to solve a max-min problem over the Stiefel manifold, which is very challenging in practice. In this paper, we propose a Riemannian block coordinate descent (RBCD) method to solve this problem, which is based on a novel reformulation of the regularized max-min problem over the Stiefel manifold. We show that the complexity of arithmetic operations for RBCD to obtain an $\epsilon$-stationary point is $O(\epsilon^{-3})$, which is significantly better than the complexity of existing methods. Numerical results on both synthetic and real datasets demonstrate that our method is more efficient than existing methods, especially when the number of sampled data is very large.

Collecting and aggregating information from several probability measures or histograms is a fundamental task in machine learning. One of the popular solution methods for this task is to compute the barycenter of the probability measures under the Wasserstein metric. However, approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper proposes the projection robust Wasserstein barycenter (PRWB) that has the potential to mitigate the curse of dimensionality, and a relaxed PRWB (RPRWB) model that is computationally more tractable. By combining the iterative Bregman projection algorithm and Riemannian optimization, we propose two algorithms for computing the RPRWB, which is a max-min problem over the Stiefel manifold. The complexity of arithmetic operations of the proposed algorithms for obtaining an $\epsilon$-stationary solution is analyzed. We incorporate the RPRWB into a discrete distribution clustering algorithm, and the numerical results on real text datasets confirm that our RPRWB model helps improve the clustering performance significantly.

We analyze the$\ell_{1}$and$\ell_{\infty}$convergence rates of$k$nearest neighbor density estimation method. Our analysis includes two different cases depending on whether the support set is bounded or not. In the first case, the probability density function has a bounded support and is bounded away from zero. We show that kNN density estimation is minimax optimal under both$\ell_{1}$and$\ell_{\infty}$criteria, if the support set is known. If the support set is unknown, then the convergence rate of$\ell_{1}$error is not affected, while$\ell_{\infty}$error does not converge. In the second case, the probability density function can approach zero and is smooth everywhere. Moreover, the Hessian is assumed to decay with the density values. For this case, our result shows that the$\ell_{\infty}$error of kNN density estimation is nearly minimax optimal.

Due to the broad range of applications of reinforcement learning (RL), understanding the effects of adversarial attacks against RL model is essential for the safe applications of this model. Prior theoretical works on adversarial attacks against RL mainly focus on either reward poisoning attacks or environment poisoning attacks. In this paper, we introduce a new class of attacks named action poisoning attacks, where an adversary can change the action signal selected by the agent. Compared with existing attack models, the attacker’s ability in the proposed action poisoning attack model is more restricted, which brings some design challenges. We study the action poisoning attack in both white-box and black-box settings. We introduce an adaptive attack scheme called LCB-H, which works for most RL agents in the black-box setting. We prove that LCB-H attack can force any efficient RL agent, whose dynamic regret scales sublinearly with the total number of steps taken, to choose actions according to a policy selected by the attacker very frequently, with only sublinear cost. In addition, we apply LCB-H attack against a very popular model-free RL algorithm: UCB-H. We show that, even in black-box setting, by spending only logarithm cost, the proposed LCB-H attack scheme can force the UCB-H agent to choose actions according to the policy selected by the attacker very frequently.

Due to the big size of data and limited data storage volume of a single computer or a single server, data are often stored in a distributed manner. Thus, performing large-scale machine learning operations with the distributed datasets through communication networks is often required. In this paper, we study the convergence rate of the distributed dual coordinate ascent for distributed machine learning problems in a general tree-structured network. Since a tree network model can be understood as the generalization of a star network, our algorithm can be thought of as the generalization of the distributed dual coordinate ascent in a star network. We provide the convergence rate of the distributed dual coordinate ascent over a general tree network in a recursive manner and analyze the network effect on the convergence rate. Secondly, by considering network communication delays, we optimize the distributed dual coordinate ascent algorithm to maximize its convergence speed. From our analytical result, we can choose the optimal number of local iterations depending on the communication delay severity to achieve the fastest convergence speed. In numerical experiments, we consider machine learning scenarios over communication networks, where local workers cannot directly reach to a central node due to constraints in communication, and demonstrate that the usability of our distributed dual coordinate ascent algorithm in tree networks.

k Nearest Neighbor (kNN) method is a simple and popular statistical method for classification and regression. For both classification and regression problems, existing works have shown that, if the distribution of the feature vector has bounded support and the probability density function is bounded away from zero in its support, the convergence rate of the standard kNN method, in which k is the same for all test samples, is minimax optimal. On the contrary, if the distribution has unbounded support, we show that there is a gap between the convergence rate achieved by the standard kNN method and the minimax bound. To close this gap, we propose an adaptive kNN method, in which different k is selected for different samples. Our selection rule does not require precise knowledge of the underlying distribution of features. The proposed adaptive method significantly outperforms the standard one. We characterize the convergence rate of the proposed adaptive method, and show that it matches the minimax lower bound.

As stochastic multi-armed bandit model has many important applications, understanding the impact of adversarial attacks on this model is essential for the safe applications of this model. In this paper, we propose a new class of attack named action-manipulation attack, where an adversary can change the action signal selected by the user. We investigate the attack against a very popular and widely used bandit algorithm: Upper Confidence Bound (UCB) algorithm. Without knowledge of mean rewards of arms, our proposed attack scheme can force the user to pull a target arm very frequently by spending only logarithm cost.

In this paper, we formulate and solve a two-stage Bayesian sequential change diagnosis problem. Different from the one-stage sequential change diagnosis problem considered in the existing work, after a change has been detected, we can continue to collect samples so that we can identify the distribution after change more accurately. The goal is to minimize the total cost including delay, false alarm and mis-diagnosis probabilities. We first convert the two-stage sequential change diagnosis problem into a two-ordered optimal stopping time problem. Using tools from multiple optimal stopping time problems, we obtain the optimal change detection and distribution identification rules.

Estimating Kullback-Leibler divergence from identically and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the k nearest neighbor distances between these samples. In this paper, we analyze the convergence rates of the bias and variance of this estimator.

In this paper, we consider the interference detection and resource allocation issue in Long-Term Evolution Unlicensed (LTE-U) system with carrier aggregation (CA). First, to avoid the co-channel interference between the WiFi and LTE-U users, we adopt the logistic regression method to train a classifier model for the base stations (BSs) to find the users that are susceptible to the interference from the WiFi. Then, we formulate the optimization problem with the goal to maximize the downlink (DL) throughput while guaranteeing the quality-of-service (QoS) for each user. To make the original problem more tractable, we first split it into two sequential subproblems and then propose a dual decomposition method to solve them efficiently. The numerical results show that the proposed schemes can significantly improve the overall throughput and outperform the existing schemes.

Motivated by recent data analytics applications, we study the adversarial robustness of robust estimators. Instead of assuming that only a fraction of the data points are outliers as considered in the classic robust estimation setup, in this paper, we consider an adversarial setup in which an attacker can observe the whole dataset and can modify all data samples in an adversarial manner so as to maximize the estimation error caused by his attack. We characterize the attacker's optimal attack strategy, and further introduce adversarial influence function (AIF) to quantify an estimator's sensitivity to such adversarial attacks. We provide an approach to characterize AIF for any given robust estimator, and then design optimal estimator that minimizes AIF, which implies it is least sensitive to adversarial attacks and hence is most robust against adversarial attacks. From this characterization, we identify a tradeoff between AIF (i.e., robustness against adversarial attack) and influence function, a quantity used in classic robust estimators to measure robustness against outliers, and design estimators that strike a desirable tradeoff between these two quantities.

KSG mutual information estimator, which is based on the distances of each sample to its k-th nearest neighbor, is widely used to estimate mutual information between two continuous random variables. Existing work has analyzed the convergence rate of this estimator for random variables whose densities are bounded away from zero in its support. In practice, however, KSG estimator also performs well for a much broader class of distributions, including not only those with bounded support and densities bounded away from zero, but also those with bounded support but densities approaching zero, and those with unbounded support. In this paper, we analyze the convergence rate of the error of KSG estimator for smooth distributions, whose support of density can be both bounded and unbounded. As KSG mutual information estimator can be viewed as an adaptive recombination of KL entropy estimators, in our analysis, we also provide convergence analysis of KL entropy estimator for a broad class of distributions.

Estimating Kullback-Leibler divergence from identical and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the k nearest neighbor distances between these samples. In this paper, we analyze the convergence rates of the bias and variance of this estimator. Furthermore, we derive a lower bound of the minimax mean square error and show that kNN method is asymptotically rate optimal.

With explosion of data size and limited storage space at a single location, data are often distributed at different locations. We thus face the challenge of performing large-scale machine learning from these distributed data through communication networks. In this paper, we generalize the distributed dual coordinate ascent in a star network to a general tree structured network, and provide the convergence rate analysis of the general distributed dual coordinate ascent. In numerical experiments, we demonstrate that the performance of the distributed dual coordinate ascent in a tree network can outperform that of the distributed dual coordinate ascent in a star network when a network has a lot of communication delays between the center node and its direct child nodes.

In this paper, we investigate the adversarial robustness of subspace learning problems. Different from the scenario addressed by classic robust algorithms that assume fractions of data are corrupted, we consider a more powerful adversary who can observe the whole data and modify all of them. The goal of the adversary is to maximize the distance between the subspace learned from the original data set and that learned from the modified data. We characterize the optimal rank-one attack strategy and show that the optimal strategy depends on the smallest singular value of the original data matrix and the adversary's energy budget.

In this paper, we investigate the convergence rate of k Nearest Neighbor (kNN) regression methods. We first derive the minimax bound for nonparametric regression under some general tail and smoothness assumptions. This bound shows that, when the distribution of features has heavy tails, there is a gap between this minimax bound and that can be achieved by the standard kNN methods where the same k is used for all query points. To close this gap, we propose an adaptive kNN method that selects smaller k when the query sample falls in the region with lower density, and vice versa. As the density function is unknown, we design a simple method to determine the value of k from training samples. Using this selection rule, we obtain a desirable tradeoff between bias and variance. Furthermore, we show that the convergence rate of our new regression method attains the minimax lower bound and hence is rate optimal when the underlying regression function is bounded. We further extend the analysis to the case with unbounded underlying regression functions and show that the proposed method significantly outperforms the standard kNN regression method in this case as well.

In this paper, the problem of function computation with privacy and secrecy constraints is considered. The considered model consists of three legitimate nodes (i.e., two transmitters, Alice and Bob, and a fusion center that acts as the receiver) that observe correlated sources and are connected by noiseless public channels, and an eavesdropper Eve who has full access to the public channels and also has its own source observations. The fusion center would like to compute a function of the distributed sources within a prefixed distortion level under a certain distortion metric. To facilitate the function computation, Alice and Bob will send messages to the fusion center. Different from the existing setups in function computation, we assume that there is a privacy constraint on the sources at Alice and Bob. In particular, Alice and Bob would like to enable the fusion center to compute the function, but at same time, they do not want the fusion center to learn too much information about the source observations. We introduce a quantity to precisely measure the privacy leakage to the fusion center. In addition to this privacy constraint, we also have a secrecy constraint to Eve and use equivocation of sources to measure this quantity. Under this model, we study the tradeoffs among message rates, private information leakage, equivocation, and distortion. We first consider a scenario that has only one transmitter, i.e., the source at Bob is empty, and fully single-letter characterize the corresponding regions. Then, we consider the more general case and provide both outer and inner bounds on the corresponding regions.

Due to the grow of modern dataset size and the desire to harness computing power of multiple machines, there is a recent surge of interest in the design of distributed machine learning algorithms. However, distributed algorithms are sensitive to Byzantine attackers who can send falsified data to prevent the convergence of algorithms or lead the algorithms to converge to value of the attackers' choice. Some recent work proposed interesting algorithms that can deal with the scenario when up to half of the workers are compromised. In this paper, we propose a novel algorithm that can deal with an arbitrary number of Byzantine attackers.

The problem of quickly detecting the occurrence of an unusual event that happens on one of multiple independent data streams is considered. In the considered problem, all data streams at the initial are under normal state and are generated by probability distribution P0. At some unknown time, an unusual event happens and the distribution of one data stream is modified to P1while the distributions of the rest remain unchange. The observer can only observe one data stream at one time. With his sequential observations, the observer wants to design an online stopping rule and a data stream switching rule to minimize the detection delay, namely the time difference between the occurrence of the unusual event and the time of raising an alarm, while keeping the false alarm rate under control. We model the problem under non-Bayesian quickest detection framework, and propose a detection procedure based on the CUSUM statistic. We show that this proposed detection procedure is asymptotically optimal.

In visible light communications (VLC) and visible light positioning (VLP), channel gains between receiver and light sources are required to be estimated. Although Time Division Multiple Access (TDMA) is typically used in the channel estimation phase of radio frequency systems, it may not be applicable for VLC and VLP systems due to the maximum power constraint and desired average power constraint that are unique to visible light systems. Recently, combinational code has been proposed as a coding scheme for channel estimation in VLC and VLP. Combinational code can work under the maximum and average power constraints, and it minimises the total and maximum noise variances experienced by the receiver. This paper reports some experimental results to compare combinational code and two schemes based on TDMA. Experimental results show that in terms of noise variance experienced by a receiver, combinational code significantly outperforms other schemes based on TDMA under the same power constraints. Challenges encountered in experiments for channel estimation are discussed and solutions are suggested to overcome these challenges.

We propose a nonparametric method to directly estimate the difference of Shannon entropy between two continuous random variables using finite number of samples. This method is based on a k-nearest-neighbor approach. We provide a finite sample analysis of the bias and variance of our proposed estimator. Numerical experiments show that our method performs better than estimating the entropy of two random variables separately. As an application of our estimator, we show that it can be used to significantly improve the performance of mutual information estimation using k-nearest-neighbor method for strongly dependent variables.

In visible light communications (VLC) and visible light positioning (VLP), it is essential to obtain accurate estimates of the channel gains between receiver and multiple light sources. When there are multiple transmitters, time-division multiple access (TDMA) is typically used in the channel estimation phase of radio frequency systems. However, the estimation performance of TDMA-based schemes in VLC and VLP systems is substantially impacted by the maximum power constraint and desired average power constraint that are unique to visible light systems. Under these constraints, this paper explores coding schemes for the simultaneous channel gain estimations of multiple light sources such that the total and maximum noise variances of the channel estimates by the receiver are minimized. Although the minimization problem is non-convex, criteria for optimal codes are found by using majorization theory. Coding scheme satisfying these criteria is proposed that helps to characterize the fundamental tradeoff between noise variance and codeword length.

In this paper, the problem of sub-channel selection for carrier aggregation (CA) systems is examined. CA enables the achievement of high data rate links via simultaneous transmissions over multiple component carriers. A CA system usually occupies only a limited number of sub-channels M of these components due to limitations on the maximum permitted number of sub-channels per system. From an information theoretic point of view, a CA system should detect and employ the M-best sub-channels out of the N available ones. To that end, such a system probes a subset of sub-channels during each coherence time via pilot transmission. Then, for the best M sub-channels, one-bit feedback information is transmitted in order to prohibit the transmission through sub-channels with gain below a threshold. The aim is to derive tractable forms via employing the extreme value theory for the sum rate (lower bound on ergodic capacity) achieved by the system under Rayleigh fading and then, to optimize jointly the training length and power, the number of the probed sub-channels (probing bandwidth size) and the feedback threshold such that the sum rate is maximized by considering the sub-channel estimation error. The accuracy of the theoretical analysis is verified by numerical results.

In the multisensor sequential change detection problem, a disruption occurs in an environment monitored by multiple sensors. This disruption induces a change in the observations of an unknown subset of sensors. In the Byzantine version of this problem, which is the focus of this work, it is further assumed that the postulated change-point model may be misspecified for an unknown subset of sensors. The problem then is to detect the change quickly and reliably, for any possible subset of affected sensors, even if the misspecified sensors are controlled by an adversary. Given a user-specified upper bound on the number of compromised sensors, we propose and study three families of sequential change-detection rules for this problem. These are designed and evaluated under a generalization of Lorden's criterion, where conditional expected detection delay and expected time to false alarm are both computed in the worst-case scenario for the compromised sensors. The first-order asymptotic performance of these procedures is characterized as the worst-case false alarm rate goes to 0. The insights from these theoretical results are corroborated by a simulation study.

We consider the problem of keyless message authentication over noisy channels in the presence of an active adversary. Different from the existing models, in our model, the legitimate users do not have any pre-shared key for authentication. Instead, we use the noisy channel connecting the legitimate users for authentication. The main idea is to utilize the noisy channel connecting the legitimate users to distinguish a legitimate message from a fake message, by generating an output at the receiver that is difficult for the adversary to replicate through its noisy channel. By interpreting the message authentication as a hypothesis testing problem, we investigate the authentication exponent and the authenticated channel capacity of the noisy channel. In the authentication exponent problem, for a given message rate, we investigate the speed at which the optimal successful attack probability can be driven to zero. We fully characterize the authentication exponent for the zero-rate message case and provide both an upper bound and a lower bound on the exponent for the non-zero message rate case. In the authenticated capacity problem, we study the largest data transmission rate under which the attacker's optimal successful attack probability can still be made arbitrarily small. We establish an all or nothing result. In particular, we show that the authenticated channel capacity is the same as the classic channel capacity if a simulatability condition is not satisfied, while the authenticated capacity will be zero if this condition is satisfied. We also provide efficient algorithms to check this condition. We further show that our results are robust to modeling uncertainties about the eavesdropper's channels.

In this paper, we consider distributed testing problems with cascaded encoders, which allow cascaded communications among encoders so that each encoder can utilize messages from other encoders for encoding. We first focus on a special case of testing against independence and design a scheme that enables each encoder to take advantage of extra information from other encoders. We also derive a matching upper bound and prove that the designed scheme is optimal. We then investigate the case with general hypotheses and obtain a lower bound on the type 2 error exponent. We further compare the performances that can be achieved by schemes with and without cascaded communications. We show that cascaded communication improves the performance in terms of the type 2 error exponent under positive rate communication constraints. On the other hand, we prove that cascaded communication does not provide performance gain under zero-rate communication constraints.

The K-receiver degraded broadcast channel with secrecy outside a bounded range is studied, in which a transmitter sends K messages to K receivers, and the channel quality gradually degrades from receiver K to receiver 1. Each receiver k is required to decode message W1, ..., Wk, for 1 ≤ k ≤ K, and to be kept ignorant of Wk+2, .. ., WK, fork = 1, ..., K -2. Thus, each message Wkis kept secure from receivers with at least two-level worse channel quality, i.e., receivers 1, ..., k-2. The secrecy capacity region is fully characterized. The achievable scheme designates one superposition layer to each message with binning employed for each layer. Joint embedded coding and binning are employed to protect all upper-layer messages from lower-layer receivers. Furthermore, the scheme allows adjacent layers to share rates so that part of the rate of each message can be shared with its immediate upper-layer message to enlarge the rate region. More importantly, an induction approach is developed to perform Fourier-Motzkin elimination of 2Kvariables from the order of K2bounds to obtain a close-form achievable rate region. An outer bound is developed that matches the achievable rate region, whose proof involves recursive construction of the rate bounds and exploits the intuition gained from the achievable scheme.

In this paper, the problem of identifying correlated components in a high-dimensional Gaussian vector is considered. In the setup considered, instead of having to take a full-vector observation at each time index, the observer is allowed to observe any subset or full set of components in the vector, and he has the freedom to design his sampling strategies over time. The observer aims to find an optimal sampling strategy and a decision rule to maximize the error exponent (per sample). We focus on sequential strategies, in which the sampling actions depend on the observations taken so far. We first derive performance bounds of any sequential sampling strategy. We then design a low complexity procedure called sequential diagonal procedure. We show that this low complexity sequential procedure substantially outperforms the optimal non-adaptive strategy when the strength of the signal is strong.

We consider problems where one wishes to represent a parameter associated with a signal source - subject to a certain rate and distortion - based on the observation of a number of realizations of the source signal. By reducing these indirect vector quantization problems to a standard vector quantization one, we provide a bound to the fundamental interplay between the rate and distortion in the large-rate setting. We specialize this characterization to two particular quantization scenarios: i) the representation of the mean of a multivariate Gaussian source; and ii) the representation of the eigen-spectrum of a multivariate Gaussian source. Numerical results compare our quantization approach to an approach where one recovers the parameters from the representation of the source signals itself: in addition to revealing that the characterization is sharp in the large-rate setting, the results also show that our approach offers considerable gains.

In this paper, we consider the identity testing problems in the distributed setting, in which each terminal has data only relates to one random variable. Each terminal sends zero-rate message to the decision maker, and the decision maker decides the distribution of (Xn, Yn), which is indirectly revealed from the encoded messages, is the same as or λ-far from a given distribution. Interpreting this as a distributed composite hypothesis testing problem, we characterize the best error exponent of the type 2 error probability using a universal coding scheme under the exponential-type constraint on the type 1 error probability.

In this paper, we analyze the sum-rate capacity of two-user Poisson multiple input multiple output multiple-access channels (MACs), when both the transmitters and the receiver are equipped with multiple antennas. Although the sum-rate capacity of Poisson MISO MAC when the receiver is equipped with a single antenna has been characterized by us, the inclusion of multiple antennas at the receiver makes the problem more challenging and requires the development of new analytical tools. We first characterize the sum-rate capacity of the Poisson MAC when each transmitter has a single antenna and the receiver has multiple antennas. We obtain the optimal input that achieves the sum-rate capacity by solving a non-convex optimization problem. We show that, for certain channel parameters, it is optimal for a single user to transmit to achieve the sum-rate capacity, and for certain channel parameters, it is optimal for both users to transmit. We then characterize the sum-rate capacity of the channel where both the transmitters and the receiver are equipped with multiple antennas. We show that the sum-rate capacity of the Poisson MAC with multiple transmit antennas is equivalent to a properly constructed Poisson MAC with a single antenna at each transmitter, and has thus been characterized by the former case. We show this by developing a novel channel transformation argument.

In this paper, the problem of simultaneously generating multiple keys over a cascade of a noiseless channel and a wiretap channel is considered. The problem consists of three legitimate parties (i.e., Alice, Bob, and Carol) and an eavesdropper (Eve), where Alice and Bob wish to agree with Carol on independent secret keys, both of which should be kept secret from Eve. Alice and Bob are connected via a noiseless channel, and Bob is connected with Carol via a wiretap channel, while there is no direct connection between Alice and Carol. To Alice and Carol, Bob acts as a relay. Under this model, a full characterization of the secret-key capacity region is provided for the case in which Eve has no side information. This result shows that there exists a tradeoff between the individual secret-key rates. Then, this result is generalized to the case in which Eve has side information, and the corresponding secret-key capacity region is fully characterized.

In this paper, we analyze the sum-rate capacity of two-user Poisson multiple access channels (MAC), when the receiver is equipped with single antenna. We first characterize the sum-rate capacity of the non-symmetric Poisson MAC when each transmitter has a single antenna. While the sum-rate capacity of the symmetric Poisson MAC with single antenna at each transmitter has been characterized in the literature, the special property exploited in the existing method for the symmetric case does not hold for the non-symmetric channel anymore. We obtain the optimal input that achieves the sum-rate capacity by solving a non-convex optimization problem. We show that, for certain channel parameters, it is optimal for a single user to transmit to achieve the sum-rate capacity. This is in sharp contrast to the Gaussian MAC, in which both users must transmit, either simultaneously or at different times, in order to achieve the sum-rate capacity. We then characterize the sum-rate capacity of the Poisson multiple-input single-output (MISO) MAC with multiple antennas at each transmitter and single antenna at the receiver. By converting a non-convex optimization problem with a large number of variables into a non-convex optimization problem with two variables, we show that the sum-rate capacity of the Poisson MISO MAC with multiple transmit antennas is equivalent to a properly constructed Poisson MAC with a single antenna at each transmitter.

The problem of simultaneously generating multiple keys for a cellular source model with a helper is investigated. In the model considered, there are four terminals, X0, X1, X2, and X3, each of which observes one component of a vector source. Terminal X0wishes to generate two secret keys K1and K2, respectively, with terminals X1and X2under the help of terminal X3. All terminals are allowed to communicate over a public channel. An eavesdropper is assumed to have access to the public discussion. Both symmetric and asymmetric key generations are considered. In symmetric key generation models, model 1a (with a trusted helper) requires that the two keys are concealed from the eavesdropper, and model 1b (with an untrusted helper) further requires that the two keys are concealed from the helper in addition to the eavesdropper. The asymmetric key generation models 2a and 2b are the same as symmetric key generation models 1a and 1b, respectively, except that the key K2is further required to be concealed from terminal X1. For all models studied, the key capacity region is established by designing a unified achievable strategy to achieve the cut-set outer bounds. We also study the problem of generating more than two keys and characterize its key capacity region when all the cellular terminals are required to generate independent keys with the base station.

In this paper, Bayesian quickest change-point detection problem with incomplete post-change information is considered. In particular, the observer knows that the post-change distribution belongs to a parametric distribution family, but he does not know the true value of the post-change parameter. Two problem formulations are considered in this paper. In the first formulation, we assume no additional prior information about the post-change parameter. In this case, the observer aims to design a detection algorithm to minimize the average (over the change-point) detection delay for all possible post-change parameters simultaneously subject to a worst case false alarm constraint. In the second formulation, we assume that there is a prior distribution on the possible value of the unknown parameter. For this case, we propose another formulation that minimizes the average (over both the change-point and the post-change parameter) detection delay subject to an average false alarm constraint. We propose a noval algorithm, which is termed as M-Shiryaev procedure, and show that the proposed algorithm is first order asymptotically optimal for both formulations considered in this paper.

In this paper, we consider the problem of quickly detecting an abrupt change of linear coefficients in linear regression models. In particular, the observer sequentially observes a sequence of observations {(xn, yn)}∞n=1, which is assumed to obey a linear regression model at each time slot n. Some of the coefficients in the linear model change at a fixed but unknown time t. The post-change linear coefficients are unknown to the observer. The observer aims to design an online algorithm to detect the model change based on his sequential observations. Two performance metrics, namely the worst case detection delay (WADD) and the average run length to false alarm (ARL2FA), are adopted to evaluate the performance of detection algorithms. We design a low complexity algorithm, termed as parallel sum algorithm, for the detection purpose. An asymptotic upper bound on WADD is provided under any given ARL2FA constraint.

Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as ℓ1minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error (MSE) of a denoising problem and the high-dimensional convex geometry for TV minimization.

In this paper, we characterize the sum-rate capacity of the non-symmetric Poisson multiple access channel (MAC). While the sum-rate capacity of the symmetric Poisson MAC has been characterized in the literature, the special property exploited in the existing method for the symmetric case does not hold for the non-symmetric channel anymore. We obtain the optimal input that achieves the sum-rate capacity by solving a non-convex optimization problem. We show that, for certain channel parameters, it is optimal for a single user to transmit to achieve the sum-rate capacity. This is in sharp contrast to the Gaussian MAC, in which all users must transmit, either simultaneously or at different times, in order to achieve the sum-rate capacity.

In this paper, the problem of simultaneously generating multiple keys over a cascade of a noiseless channel and a wiretap channel is considered. The problem consists of three legitimate parties, i.e., Alice, Bob and Carol, where Alice and Bob wish to agree with Carol on independent secret keys. Alice and Bob are connected via a noiseless channel, and Bob is connected with Carol via a wiretap channel, while there is no direct connection between Alice and Carol. To Alice and Carol, Bob acts as a relay. Under this model, a single-letter characterization of the secret-key capacity region is provided. The result shows that there exists a trade-off between the individual secret-key rates.

A K-receiver degraded broadcast channel with secrecy outside a bounded range is studied, in which a transmitter sends K messages respectively to K receivers, and the channel quality gradually degrades from receiver K to receiver 1. Each receiver k is required to decode messages W1, …, Wk, for 1 ≤ k ≤ K. Furthermore, each message Wkshould be kept secure from receivers with two-level worse channel quality, i.e., receivers 1, …, k − 2. The secrecy capacity region is fully characterized. The achievable scheme designates one superposition layer to each message with random binning employed for each layer for protecting all upper-layer messages from lower-layer receivers. Furthermore, the scheme allows adjacent layers to share rates so that part of the rate of each message can potentially be shared with its immediate upper-layer message to enlarge the rate region. More importantly, an induction approach is developed to perform Fourier-Motzkin elimination over 2K variables among Θ(K2) bounds to obtain a close-form achievable rate region. A converse proof is developed that matches the achievable rate region, which involves recursive construction of the rate bounds.

Preestablished secret keys are often used to encrypt and decrypt data in communication systems, which are not secure once the keys are compromised. One desirable method is to generate secret keys dynamically using correlated channel measurements. We explore this concept in underwater acoustic (UWA) channels, and present a protocol that can generate secret keys dynamically based on the channel frequency response (CFR) in orthogonal frequency-division multiplexing systems. The multi-bit quantization is carried out on the amplitude of each tone, and the Bose-Chaudhuri-Hocquenghem codes are used for information reconciliation. Part of the protocol was implemented in lake tests, and multiple data sets were collected. The lake test results verify that the amplitude of CFR can be used as a randomness source for key generation in UWA channels, and we also find the low correlation between the mutual channels of the legitimate users. Based on the lake test results, we incorporate two modules into the protocol for performance improvement. The first module employs the adaptively weighted probing signaling to increase the channel correlation, and the second module of block-sliced key verification is used to deal with channel dynamics and increase the key agreement probability. The simulation results demonstrate the improved performance of the enhanced protocol.

Simulatability condition is a fundamental concept in studying key generation over a non-authenticated public channel, in which Eve is active and can intercept, modify and falsify messages exchanged over the non-authenticated public channel. Using this condition, Maurer and Wolf showed a remarkable “all or nothing” result: if the simulatability condition does not hold, the key capacity over the non-authenticated public channel will be the same as that of the case with a passive Eve, while the key capacity over the non-authenticated channel will be zero if the simulatability condition holds. However, two questions remain open so far: 1) For a given joint probability mass function (PMF), are there efficient algorithms (polynomial complexity algorithms) for checking whether the simulatability condition holds or not?; and 2) If the simulatability condition holds, are there efficient algorithms for finding the corresponding attack strategy? In this paper, we answer these two open questions affirmatively. In particular, for a given joint PMF, we construct a linear programming (LP) problem and show that the simulatability condition holds if and only if the optimal value obtained from the constructed LP is zero. Furthermore, we construct another LP and show that the minimizer of the newly constructed LP is a valid attack strategy. Both LPs can be solved with a polynomial complexity.

The problem of when all terminals must talk to achieve the secrecy capacity in the multiterminal source model is investigated. Two conditions under which respectively a given terminal does not need to and must talk to achieve the secrecy capacity are characterized. The cases when all terminals must talk to achieve secrecy capacity are shown to be many more than those conjectured in [1] for systems with four or more terminals. There is a gap between the above two conditions, in which whether a given terminal need to talk is not clear. A conjecture is further made in order to narrow down the gap.

The problem of simultaneously generating two keys for a cellular model is investigated, in which each of four terminals, X0, X1, X2, and X3observes one component of correlated sources. The terminal X0 wishes to generate secret keys K1and K2respectively, with terminals X1and X2under the help of terminal X3. They are allowed to communicate over a public channel. Both K1and K2are required to be concealed from an eavesdropper that has access to the public discussion. The key capacity region is established by designing a unified achievable strategy to achieve the cut-set outer bounds, which greatly simplifies the proof.

Motivated by distributed inference over big datasets problems, we study multi-terminal distributed hypothesis testing problems in which each terminal has data related to only one random variable. We consider a case of practical interest in which each terminal is allowed to send zero-rate messages to a decision maker. Subject to a constraint that the error exponent of the type 1 error probability is larger than a certain level, we characterize the best error exponent of the type 2 error probability using basic properties of the r-divergent sequences.

A four-receiver degraded broadcast channel with secrecy outside a bounded range is studied, over which a transmitter sends four messages to four receivers. In the model considered, the channel quality gradually degrades from receiver 4 to receiver 1, and receiver k is required to decode the first k messages for k = 1, …, 4. Furthermore, message 3 is required to be secured from receiver 1, and message 4 is required to be secured from receivers 1 and 2. The secrecy capacity region is established. The achievable scheme includes not only superposition, binning and embedded coding used in previous studies, but also rate splitting and sharing particularly designed for this model, which is shown to be critical to further enlarge the achievable region and enable the development of the converse proof.

A three-receiver degraded broadcast channel with secrecy outside of a bounded range is studied, in which the channel quality gradually degrades from receiver 3 to receiver 1. The transmitter has three messages intended for the receivers with receiver 3 decoding all messages, receiver 2 decoding the first two messages, and receiver 1 decoding only the first message. Furthermore, the third message should be kept secure from receiver 1. The discrete memoryless channel is studied and the secrecy capacity region is characterized. The achievable scheme is based on superposition coding and random binning, in which one superposition layer and random binning together provide secrecy. The converse proof is derived based on the insight obtained from the achievable scheme so that manipulations of terms yield tight rate bounds.

Recent information-theoretic results on a class of broadcast channels with layered decoding and/or layered secrecy are reviewed. In this class of models, a transmitter sends multiple messages to a set of legitimate receivers in the presence of a set of eavesdroppers, whose channels can be ordered based on the quality of received signals. Receivers with better channel quality are required to decode more messages, and eavesdroppers with worse channel quality are required to be kept ignorant of more messages. The design of achievable schemes and the characterization of the corresponding secrecy capacity regions are presented. Comparison of the designs for different models is discussed. Applications of these information-theoretic models to the study of secure communication over fading wiretap channels and secret sharing are also presented to illustrate potential applications of these models.

In this paper, we study Poisson fading channels with time-varying background light. Different from most of the existing work on fading Poisson channel that focus on the case with time-varying channel gain, our model is motivated by indoor optical wireless communication systems, in which the noise level is affected by the strength of the background light. We study both the single-input single-output and the multiple-input and multiple-output channels. For each channel, we consider scenarios with and without delay constraints. For the case without a delay constraint, we characterize the optimal power allocation scheme that maximizes the ergodic capacity. For the case with a strict delay constraint, we characterize the optimal power allocation scheme that minimizes the outage probability. We also provide several numerical examples to demonstrate the analytic results.

We consider two secret key generation problems under a pairwise independent network model, and propose low complexity key generation schemes in a framework that connects our problems to network flow problems in graphs. Our schemes have two components: 1) local key generation and 2) global key propagation. In the local key generation, we use point-to-point source coding with side information to establish pairwise keys, from which we construct a graph with the capacity of each edge being the key rate of the corresponding point-to-point local key. In the global key propagation, depending on the particular problem, secret keys are delivered to users in the network using various network flow algorithms. In particular, in the first problem in which one is required to generate a group key for a group of users in the network, we propose a network coding-based global key propagation approach. This approach has a low complexity and has a better performance than the existing approach. In the second problem, in which one is required to generate multiple keys simultaneously for different pairs of users, we propose a multicommodity flow-based global key propagation approach. We show that the proposed approach is optimal for the case of generating two keys. For the general case of generating more than two keys, we show that the sum rate of the proposed scheme is larger than an upper bound characterized in this paper divided by a constant.

The Poisson interference channel, which models optical communication systems with multiple transceivers in the short-noise-limited regime, is investigated. Conditions for the strong interference regime are characterized and the corresponding capacity region is derived, which is the same as that of the compound Poisson multiple-access channel with each receiver decoding both messages. For the cases when the strong interference conditions are not satisfied, inner and outer bounds on the capacity region are derived. The inner bound is derived via approximating the Poisson interference channel by a binary interference channel and then evaluating the corresponding Han-Kobayashi region. The outer bounds are obtained via various techniques, including noise reduction, genie-aided scheme, and channel transformation. The Poisson Z-interference channel is then studied. The sum rate capacity is obtained when the cross link coefficient is either sufficiently small or sufficiently large.

A novel information theoretic approach is proposed to solve the secret sharing problem, in which a dealer distributes one or multiple secrets among a set of participants in such a manner that for each secret only qualified sets of users can recover this secret by pooling their shares together while nonqualified sets of users obtain no information about the secret even if they pool their shares together. While existing secret sharing systems (implicitly) assume that communications between the dealer and participants are noiseless, this paper takes a more practical assumption that the dealer delivers shares to the participants via a noisy broadcast channel. Thus, in contrast to the existing solutions that are mainly based on number theoretic tools, an information theoretic approach is proposed, which exploits the channel randomness during delivery of shares as additional resources to achieve secret sharing requirements. In this way, secret sharing problems can be reformulated as equivalent secure communication problems via wiretap channel models, and can hence be solved by employing the powerful information theoretic security techniques. This approach is first developed for the classic secret sharing problem, in which only one secret is to be shared. This classic problem is shown to be equivalent to a communication problem over a compound wiretap channel. Thus, the lower and upper bounds on the secrecy capacity of the compound channel provide the corresponding bounds on the secret sharing rate, and the secrecy scheme designed for the compound channel provides the secret sharing schemes. The power of the approach is further demonstrated by a more general layered multisecret sharing problem, which is shown to be equivalent to the degraded broadcast multiple-input multiple-output (MIMO) channel with layered decoding and secrecy constraints. The secrecy capacity region for the degraded MIMO broadcast channel is characterized, which provides the secret sharing capacity region. Furthermore, the secure encoding scheme that achieves the secrecy capacity region provides an information theoretic scheme for sharing the secrets.

In this paper, Bayesian quickest change-point detection problem with a stochastic energy constraint is considered. This work is motivated by applications of renewable energy powered wireless sensor networks. In particular, a renewable energy powered wireless sensor is deployed to detect the change in the probability distribution of the observation sequence. The energy in the sensor is consumed by taking observations and is replenished randomly. The sensor cannot store extra energy if its battery is full and cannot take observations if it has no energy left. Hence, the sensor needs to use its energy efficiently. Our goal is to design a power allocation scheme and a detection strategy to minimize the average detection delay while keeping a low false alarm probability. We show that this problem can be written into a set of iteratively defined functions and then solved by the tools from the optimal stopping theory. It turns out that the optimal solution has a very complex structure. For practical applications, we propose a low complexity algorithm, in which the sensor adopts a greedy power allocation scheme with a threshold detection rule. We show that this algorithm is first order asymptotically optimal as the false alarm probability goes to zero.

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated, in which each terminal observes a component of correlated sources. All three terminals are required to generate a common secret key concealed from an eavesdropper that has access to public discussion, while two designated terminals are required to generate an extra private key concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established in [1], and was shown to be achievable for one case. In this paper, achievable schemes are designed to achieve the outer bound for the remaining two cases, and hence the SK-PK capacity region is established in general. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound.

In this paper, the degraded Gaussian Multiple-Input-Multiple-Output (MIMO) broadcast channel with layered decoding and secrecy constraints is investigated. In this model, there are in total K messages and K receivers that are ordered by the channel quality. Each receiver is required to decode one more message than the receiver with one level worse channel quality. Furthermore, this message should be kept secure from the receivers with worse channel qualities. The secrecy capacity region for this model is fully characterized. The converse proof relies on a novel construction of a series of covariance matrices. An application of this model to the problem of sharing multiple secrets, which is difficult to solve using number theoretic tools, is investigated. The secret sharing capacity region is characterized by reformulating the secret sharing problem as the secure communication problem over the K-receiver degraded Gaussian MIMO broadcast channel.

A cellular source model for key generation is proposed and studied, in which a central terminal χ0wishes to generate K1with terminal χ1and K2with terminal χ2, respectively, via public discussion. Each terminal observes a component of a correlated source sequence. The K1is required to be concealed from an eavesdropper that has access to the public discussion, while the key K2needs to be concealed from both the eavesdropper and terminal χ1. The key capacity region is established by showing that the cut-set upper bound is achievable.

In this paper, we propose a sequential spectrum sensing algorithm for cognitive radio systems, which we term the sequential shifted chi-square test (SSCT). SSCT has the following attractive features for practical implementations. First, SSCT employs a simple test statistic and thus has a low implementation complexity. Secondly, SSCT is a sequential detection algorithm and is capable of achieving performance comparable to fixed sample size detection algorithms such as energy detection but with much reduced sensing time. Thirdly, SSCT is essentially a non-coherent detection algorithm in the sense that it does not require any deterministic knowledge of the primary signals. Lastly, SSCT is able to strike a desirable trade-off between sensing performance and sensing time particularly in the signal-to-noise ratio mismatched case. To evaluate sensing performance, we derive the exact false-alarm probability for SSCT, and develop numerical integration algorithms to compute misdetection probability and the average sample number. We further demonstrate the performance of SSCT with several numerical examples.

In this paper, we propose a novel sequential channel estimation approach for multiband cognitive radio (CR) systems. We introduce a general model and test two scenarios of practical interest. The two scenarios are as follows: 1) CR users optimally estimate all the available bands; and 2) CR users find one good channel with a large gain. In particular, we use a sequential search in which the CR users estimate the available channels one by one. During the search, the CR users determine whether to terminate the current channel estimation process and switch to the next channel based on the training symbols received so far. Our objective is to design a switch function, an estimator, and a stopping rule that minimize a combination of estimation time and error. For the multiband estimation scenario, we show that the optimal rule is to find the optimal number of symbols required for each channel in a joint optimization problem. For the good channel search problem, we show that the optimal decision rules that minimize a properly chosen cost function have a simple structure. In particular, both the termination and switching rules are threshold based. Numerical results are provided to illustrate the effectiveness of the proposed algorithms.

Most of the existing work on key generation from wireless fading channels requires a direct wireless link between legitimate users so that they can obtain correlated observations from the common wireless link. This paper studies the key generation problem in the two-way relay channel, in which there is no direct channel between the key generating terminals. We propose an effective key generation scheme that achieves a substantially larger key rate than that of a direct channel mimic approach. Unlike existing schemes, there is no need for the key generating terminals to obtain correlated observations in our scheme. We also investigate the effects of an active attacker on the proposed key generation protocol. We characterize the optimal attacker's strategy that minimizes the key rate of the proposed scheme. Furthermore, we establish the maximal attacker's power under which our scheme can still achieve a nonzero key rate.

In this paper, Bayesian quickest change detection problems with sampling right constraints are considered. In particular, there is a sequence of random variables whose probability density function will change at an unknown time. The goal is to detect this change in a way such that a linear combination of the average detection delay and the false alarm probability is minimized. Two types of sampling right constrains are discussed. The first one is a limited sampling right constraint, in which the observer can take at most N observations from this random sequence. Under this setup, we show that the cost function can be written as a set of iterative functions, which can be solved by Markov optimal stopping theory. The optimal stopping rule is shown to be a threshold rule. An asymptotic upper bound of the average detection delay is developed as the false alarm probability goes to zero. This upper bound indicates that the performance of the limited sampling right problem is close to that of the classic Bayesian quickest detection for several scenarios of practical interest. The second constraint discussed in this paper is a stochastic sampling right constraint, in which sampling rights are consumed by taking observations and are replenished randomly. The observer cannot take observations if there are no sampling rights left. We characterize the optimal solution, which has a very complex structure. For practical applications, we propose a low complexity algorithm, in which the sampling rule is to take observations as long as the observer has sampling rights left and the detection scheme is a threshold rule. We show that this low complexity scheme is first order asymptotically optimal as the false alarm probability goes to zero.

A (layered) broadcast approach is studied for the fading wiretap channel without the channel state information (CSI) at the transmitter. Two broadcast schemes, based on superposition coding and embedded coding, respectively, are developed to encode information into a number of layers and use stochastic encoding to keep the corresponding information secret from an eavesdropper. The layers that can be successfully and securely transmitted are determined by the channel states to the legitimate receiver and the eavesdropper. The advantage of these broadcast approaches is that the transmitter does not need to know the CSI to the legitimate receiver and the eavesdropper, but the scheme still adapts to the channel states of the legitimate receiver and the eavesdropper. Three scenarios of block fading wiretap channels with stringent delay constraints are studied, in which either the legitimate receiver's channel, the eavesdropper's channel, or both channels are fading. For each scenario, the secrecy rate that can be achieved via the broadcast approach developed in this paper is derived, and the optimal power allocation over the layers (or the conditions on the optimal power allocation) is also characterized. A notion of probabilistic secrecy, which characterizes the probability that a certain secrecy rate of decoded messages is achieved during one block, is also introduced and studied for scenarios when the eavesdropper's channel is fading. Numerical examples are provided to demonstrate the impact of the CSI at the transmitter and the channel fluctuations of the eavesdropper on the average secrecy rate. These examples also demonstrate the advantage of the proposed broadcast approach over the compound channel approach.

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated. In this problem, each terminal observes a component of correlated sources. All three terminals are required to generate the common SK to be concealed from an eavesdropper that has access to the public discussion, while two designated terminals are required to generate an extra PK to be concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established by Ye and Narayan, and was shown to be achievable for a special case. In this paper, the SK-PK capacity region is established in general by developing schemes to achieve the outer bound for the remaining two cases. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound.

A key feature of cognitive radio network is the intelligence of secondary users who can collaborate to improve the system performance. The collaboration in terms of channel recommendation is studied in this paper. The recommendation mechanism results in dynamics of the channel preferences of secondary users, thus causing a behavior propagation in a social network. For cognitive radio networks having a grid topology, the ergodicity of the dynamics is studied using the model of interacting particles in nonequilibrium statistical mechanics. For networks having a grid topology or being randomly deployed, mean field descriptions using ordinary differential equation are used to explicitly describe the dynamics of behavior propagation. The analytic results are demonstrated by numerical simulations.

Motivated by applications of wireless sensors powered by energy harvested from the environment, we study non-Bayesian quickest change detection problems with a stochastic energy constraint. In particular, a wireless sensor powered by renewable energy is deployed to detect the change of probability density function in a random sequence. The energy in the sensor is consumed by taking observation and is replenished randomly. The sensor cannot take observations if there is no energy left. Our goal is to design power allocation scheme and detection strategy to minimize the delay between the time the change occurs and an alarm is raised. Two types of average run length (ARL) constraint, namely an algorithm level ARL and a system level ARL, are considered. We show that a low complexity scheme, in which the sensor takes observations as long as the battery is not empty coupled with the Cumulative Sum (CUSUM) test for detection, is optimal for the setup with the algorithm level ARL constraint, and is asymptotically optimal for the setup with the system level ARL constraint.

The problem of sequentially finding an independent and identically distributed (i.i.d.) sequence that is drawn from a probability distribution F1by searching over multiple sequences, some of which are drawn from F1and the others of which are drawn from a different distribution F0, is considered. The sensor is allowed to take one observation at a time. It has been shown in a recent work that if each observation comes from one sequence, Cumulative Sum (CUSUM) test is optimal. In this paper, we propose a new approach in which each observation can be a linear combination of samples from multiple sequences. The test has two stages. In the first stage, namely scanning stage, one takes a linear combination of a pair of sequences with the hope of scanning through sequences that are unlikely to be generated from F1and quickly identifying a pair of sequences such that at least one of them is highly likely to be generated by F1. In the second stage, namely refinement stage, one examines the pair identified from the first stage more closely and picks one sequence to be the final sequence. The problem under this setup belongs to a class of multiple stopping time problems. In particular, it is an ordered two concatenated Markov stopping time problem. We obtain the optimal solution using the tools from the multiple stopping time theory. Numerical simulation results show that this search strategy can significantly reduce the searching time, especially when F1is rare.

This paper considers source coding problems with the requirements of perfect secrecy and zero error at receivers. In the problems considered in this paper, there is always one transmitter but there can be one or two receivers. Two different scenarios depending on whether the receivers' side information are present at the transmitter or not are considered. By deriving bounds on the probability masses of the cipher-text and the key, the minimum transmission rate and key rate are characterized. Although zero-error capacities are typically difficult to characterize, the perfect secrecy constraint turns out to be the key that simplifies the problems considered in this paper and makes them analytically tractable.

The problem of simultaneously establishing multiple keys, one for each user in a set of users, is considered with possible assist from a group of dedicated helpers. For the case in which all users are required to generate keys, we develop a scheme that is sum rate optimal. For the case with dedicated helpers, we develop an achievable scheme and derive an outer bound. We identify conditions under which the developed scheme achieves the full capacity region and conditions under which it is sum rate optimal. We then specialize the study to a pairwise independent network model, for which we convert the key generation problem to a single-source multi-commodity flow over a network problem. Coupling results from graph theory, we fully characterize the capacity region for the general case of generating multiple keys with multiple helpers under the PIN model.

The main goal of this special issue is to gather state-of-the art-contributions that address such challenges as they pertain to the design, analysis, and optimization of physical layer security in next-generation networks.

This paper considers the problem of how to quickly and accurately determine the availability of each spectrum band for a multi-band primary system using one or few sensors. Such problem is referred to as spectrum scanning. Two cases of practical interest are studied: 1) a single sensor case in which only one spectrum band is observed at one time; and 2) a multiple sensor case in which multiple spectrum bands are observed simultaneously. For each case, scenarios with and without a scanning delay constraint are investigated. Using mathematical tools from optimal stopping theory, optimal spectrum scanning algorithms are developed to minimize a cost function that strikes a desirable trade-off between detection performance and sensing delay. In the non delay-constrained case, it is shown that the optimal scanning algorithm is a concatenated sequential probability ratio test (C-SPRT). In the delay-constrained case, the optimal scanning algorithm has a high implementation complexity and truncation algorithms are developed as alternative low complexity options. Numerical examples are provided to illustrate the effectiveness of the proposed algorithms.

Broadcasting over the fading wiretap channel is investigated for the situation without the channel state information (CSI) at the transmitter and subject to a delay constraint. A new broadcast approach is developed, which integrates secure superposition coding studied in the authors' previous work and embedded coding in a hybrid fashion. This scheme outperforms the previous approaches for the cases when the eavesdropper's channel is fading. The secrecy rate achievable via the new broadcast approach is derived, and the structure of the optimal power allocation function across the secure coding layers is characterized via techniques for solving the problem of constrained calculus of variations. A notion of probabilistic secrecy is introduced and studied, which characterizes the probability that a certain secrecy rate is achieved for any given fading block. Numerical examples are provided to demonstrate the impact of CSI at the transmitter if not available and the channel fluctuation of the eavesdropper on the average secrecy rate.

The problem of simultaneously generating multiple independent keys for multiple pairs of users is considered. This problem is motivated by the fact that typically in wireless networks, multiple pairs of users need to establish secret keys for secure communications between these pairs. We propose a secure routing based key distribution approach to establish keys for the terminals. This approach connects the problem at the hand to that of multi-commodity flow problem studied in graph theory. Using the Max Bi-Flow Min Cut Theorem in the graph theory and developing a matching outer-bound, we show that the proposed approach achieves the key capacity region for the case of establishing two keys. For the general case of establishing more than two keys, an upper bound on the achievable sum rate is derived based on the concept of multicut and our proposed approach can achieve a sum rate equals to the upper bound divided by a constant factor.

The impact of relay nodes on the secret key generation via the physical layer resources is investigated. A novel relay-assisted strategy is proposed to improve the generated secret key rate. The main idea is to exploit the random channels associated with relay nodes in the network as additional random sources for the key generation. This approach is particularly useful when the channels between legitimate nodes change slowly. Four increasingly sophisticated yet more practical scenarios are studied, for which relay-assisted key generation protocols are proposed and are shown to be optimal or order-optimal in terms of the key rate. It is also shown that the multiplexing gain in the key rate scales linearly with the number of relays, which demonstrates that relay-assisted schemes substantially increase the key rate. This is in sharp contrast to scenarios with relays helping information transmission, in which the multiplexing gain does not scale with the number of relays. Furthermore, a cooperative scheme is also proposed in which relays help key generation but the generated keys are kept secure from these relays.

In cyber physical systems, communication is needed for conveying sensor observations to controllers; thus, the design of the communication sub-system is of key importance for the stabilization of system dynamics. In this paper, multicast routing is studied for networking of decentralized sensors and controllers. The challenges of uncertain destinations and multiple routing modes, which are significantly different from traditional data networks, are addressed by employing the theories of hybrid systems and linear matrix inequalities, thus forming a novel framework for studying the communication sub-system in cyber physical systems. Both cases of neglible delay and non-negligible delay are discussed. The proposed framework is then applied in the context of voltage control in smart grid. Numerical simulations using a 4-bus power grid model show that the proposed framework and algorithm can effectively stabilize cyber physical systems.

The problem of key generation over wireless fading channels is investigated. First, a joint source-channel approach that combines existing source and channel models for key agreement over wireless fading channels is developed. It is shown that, in general, to fully exploit the resources provided by time-varying channel gains, one needs to combine both the channel model, in which Alice sends a key to Bob over a wireless channel, and the source model, in which Alice and Bob generate a key by exploiting the correlated observations obtained from the wireless fading channel. Asymptotic analyses suggest that in the long coherence time regime, the channel model is asymptotically optimal. On the other hand, in the high power regime, the source model is asymptotically optimal. Second, the framework is extended to the scenario with an active attacker. Assuming that the goal of the attacker is to minimize the key rate that can be generated using the proposed protocol and the attacker will employ such an attack strategy, the attacker's optimal attack strategy is identified and the key rate under this attack model is characterized.

The communication for the control of distributed energy generation (DEG) in microgrid is discussed. Due to the requirement of realtime transmission, weak or no explicit channel coding is used for the message of system state. To protect the reliability of the uncoded or weakly encoded messages, the system dynamics are considered as a 'nature encoding' similar to convolution code, due to its redundancy in time. For systems with or without explicit channel coding, two decoding procedures based on Kalman filtering and Pearl's Belief Propagation, in a similar manner to Turbo processing in traditional data communication systems, are proposed. Numerical simulations have demonstrated the validity of the schemes, using a linear model of electric generator dynamic system.

The social behavior in cognitive radio networks is studied using analysis tools in social networks. A recommendation system is proposed for cognitive radio, thus incurring the channel preference propagation in the corresponding random geometric network. A mean field based ordinary differential equation is used to describe the dynamics of the channel preference propagation in cognitive radio networks. The conditional distribution of random geometric graph is studied. The convergence and the steady state of the mean field equation are discussed. Numerical simulations are used to demonstrate the properties uncovered by the analysis.

Smart grid, equipped with modern communication infrastructures, is subject to possible cyber attacks. Particularly, false report attacks which replace the sensor reports with fraud ones may cause the instability of the whole power grid or even result in a large area blackout. In this paper, a trustiness system is introduced to the controller, who computes the trustiness of different sensors by comparing its prediction, obtained from Kalman filtering, on the system state with the reports from sensor. The trustiness mechanism is discussed and analyzed for the Linear Quadratic Regulation (LQR) controller. Numerical simulations show that the trustiness system can effectively combat the cyber attacks to smart grid.

We consider the secret sharing problem, in which a dealer distributes a secret among a set of participants in such a manner that only qualified sets of users can recover the secret by pooling their shares together while non-qualified sets of users will obtain no information about the secret even if they pool their shares together. In contrast to the existing solutions that are mainly based on number theoretic tools, we propose a physical layer approach that exploits the presence of random noise inherent to wireless channels for secret sharing. Two different scenarios are considered. In the first scenario, the classic secret sharing problem with a single secret message is considered, in which qualified sets are specified by a general access structure. A secret sharing scheme is proposed by constructing a secure coding scheme for an equivalent compound wiretap channel. Based on this approach, both lower and upper bounds on the secret sharing capacity are obtained. For some special cases, the secret sharing capacity is fully characterized. In the second scenario, a generalization of the classic secret sharing problem is proposed, in which multiple secret messages are required to be recovered at different qualified sets. A secret sharing scheme is provided by constructing an equivalent broadcast channel with compound eavesdroppers and constructing a secure coding scheme for the equivalent channel.

We study a secure distributed source coding problem. Two terminals with correlated observations would like to send their observations securely to a receiver using minimal transmission rates and key rates. By providing a converse, we show the optimality of a natural structure, in which Slepian-Wolf distributed compression is followed by an application of a onetime pad for encryption. Hence, in contrast to many multiuser setting, the separation of compression and encryption is optimal for this particular case. The optimality of the separation can simplify practical algorithm design. In addition, we constructively demonstrate that switching the order of compression and encryption does not incur any performance loss. Finally, we show that if one requires perfect secrecy and zero error probability, the required rates increase significantly and data compression becomes unnecessary.

The sequential detection problem in wireless sensors powered by energy harvested from the enviroment is considered. Assuming that a unit of energy arrives with probability p at each time instant, two different problem setups, namely minimizing the weighted sum of detection delay and error probabilities and minimizing the average detection delay subject to error probabilities constraints, are studied. Optimal decision rules including energy allocation, stopping rule and terminal decision rules are derived for both setups. For both setups, we show that the sensor will take samples immediately after energy arrives. However, the numbers of samples that the sensor will take for these two setups behave differently as p changes. For the first setup, the number of samples increases as p increase. For the second setup, the number of samples the sensor will take is the same for different values of p.

In this paper, cognitive radio wireless networks are investigated, in which a number of primary users (PUs) transmit in orthogonal frequency bands, and a number of secondary users (SUs) monitor the transmission status of the PUs and search for transmission opportunities in these frequency bands by collaborative detection. A network management problem is formulated to find the configuration of SUs (assignment of SUs) to detect PUs so that the best overall network performance is achieved. Two performance metrics are considered, both of which characterize the probability of errors for detecting transmission status of all PUs. For both metrics, a graphical representation of the problem is provided, which facilitates to connect the problems under study to the sum-product inference problem studied in probabilistic graphical models. Based on the elimination algorithm that solves the sum-product problem, a message passing algorithm is proposed to solve the problem under study in a computationally efficient manner and in a distributed fashion. The complexity of the algorithm is shown to be significantly lower than that of the exhaustive search approach. Moreover, a clique-tree algorithm is applied to efficiently compute the impacts of each SU's choice on the overall system performance. Finally, simulation results are provided to demonstrate the considerable performance enhancement achieved by implementing an optimal assignment of SUs.

This is the first part of a two-part paper on the information theoretic study of biometric security systems. In this paper, the design of single-use biometric security systems is analyzed from an information theoretic perspective. A fundamental trade-off between privacy, measured by the normalized equivocation rate of the biometric measurements, and security, measured by the rate of the key generated from the biometric measurements, is identified. The privacy-security region, which characterizes the above-noted trade-off, is derived for this case. The scenario in which an attacker of the system has side information is then considered. Inner and outer bounds on the privacy-security region are derived in this case. Finally, biometric security systems with perfect privacy are studied, which is shown to be possible if and only if common randomness can be generated from two biometric measurements.

This is the second part of a two-part paper on the information theoretic study of biometric security systems. In this paper, the performance of reusable biometric security systems, in which the same biometric information is reused in multiple locations, is analyzed. The scenario in which the subsystems are jointly designed is first considered. An outer bound on the achievable trade-off between the privacy leakage of the biometric measurements and rates of keys generated at the subsystems is derived. A scheme that achieves the derived outer bound is then presented. Next, an incremental design approach is studied, in which the biometric measurements are reused while keeping the existing system intact. An achievable privacy-security trade-off region for this design approach is derived. It is shown that under certain conditions, the incremental design approach can achieve the performance of the joint design approach. Finally, examples are given to illustrate the results derived.

This paper studies the frequency/time selectiveK-user Gaussian interference channel with secrecy constraints. Two distinct models, namely the interference channel with confidential messages and the interference channel with an external eavesdropper, are analyzed. The key difference between the two models is the lack of channel state information (CSI) of the external eavesdropper. Using interference alignment along with secrecy precoding, it is shown that each user can achieve non-zero secure degrees of freedom (DoF) for both cases. More precisely, the proposed coding scheme achieves [(K-2)/(2K-2)] secure DoF with probability one per user in the confidential messages model. For the external eavesdropper scenario, on the other hand, it is shown that each user can achieve [(K-2)/(2K)] secure DoF in the ergodic setting. Remarkably, these results establish the positive impact of interference on the secrecy capacity region of wireless networks.

The problem of sequentially finding an independent and identically distributed sequence that is drawn from a probability distributionQ1by searching over multiple sequences, some of which are drawn fromQ1and the others of which are drawn from a different distributionQ0, is considered. In the problem considered, the number of sequences with distributionQ1is assumed to be a random variable whose value is unknown. Within a Bayesian formulation, a sequential decision rule is derived that optimizes a trade-off between the probability of false alarm and the number of samples needed for the decision. In the case in which one can observe one sequence at a time, it is shown that the cumulative sum (CUSUM) test, which is well-known to be optimal for a non-Bayesian statistical change-point detection formulation, is optimal for the problem under study. Specifically, the CUSUM test is run on the first sequence. If a reset event occurs in the CUSUM test, then the sequence under examination is abandoned and the rule switches to the next sequence. If the CUSUM test stops, then the rule declares that the sequence under examination when the test stops is generated byQ1. The result is derived by assuming that there are infinitely many sequences so that a sequence that has been examined once is not retested. If there are finitely many sequences, the result is also valid under a memorylessness condition. Expressions for the performance of the optimal sequential decision rule are also developed. The general case in which multiple sequences can be examined simultaneously is considered. The optimal solution for this general scenario is derived.

This paper considers the design of efficient strategies that allow cognitive users to choose frequency bands to sense and access among multiple bands with unknown parameters. First, the scenario in which a single cognitive user wishes to opportunistically exploit the availability of frequency bands is considered. By adopting tools from the classical bandit problem, optimal as well as low complexity asymptotically optimal solutions are developed. Next, the multiple cognitive user scenario is considered. The situation in which the availability probability of each channel is known is first considered. An optimal symmetric strategy that maximizes the total throughput of the cognitive users is developed. To avoid the possible selfish behavior of the cognitive users, a game-theoretic model is then developed. The performance of both models is characterized analytically. Then, the situation in which the availability probability of each channel is unknown a priori is considered. Low-complexity medium access protocols, which strike an optimal balance between exploration and exploitation in such competitive environments, are developed. The operating points of these low-complexity protocols are shown to converge to those of the scenario in which the availability probabilities are known. Finally, numerical results are provided to illustrate the impact of sensing errors and other practical considerations.

In a cognitive radio (CR) network, secondary users (SUs) are allowed to opportunistically access a licensed spectrum that is not currently being occupied by primary users. This paper is concerned with the problem of how to quickly and accurately locate an unoccupied channel or determine that there is no unoccupied channel, from multiple (yet finite) candidate channels for a SU with a single detector. To design channel search algorithms, we propose a design criterion that minimizes average searching time subject to constraints on the error probabilities for a multichannel system. Relying on the proposed design criterion, we develop two efficient channel search algorithms that are based on a sequential application of the sequential probability ratio test and energy detection to the candidate channels.

The performance of reusable biometric security systems in which the same biometric information is reused in several different locations is analyzed in this paper. The scenario in which the subsystems used at different locations are jointly designed is first considered. A fundamental limit of the privacy-security tradeoff is derived. Next, an incremental design approach is studied, in which the biometric measurements are reused while keeping the existing system intact. An achievable privacy-security tradeoff region for this design approach is derived. It is shown that under certain conditions, the incremental design approach can achieve the performance of the joint design approach. Finally, examples are given to illustrate the results.

The Poisson interference channel is studied, which models optical communication systems with multiple transceivers. Conditions for the strong interference is characterized and the corresponding capacity region is given, which is the same as that of the compound Poisson multiple access channel with each receiver decoding both messages. For the cases when the strong interference conditions are not satisfied, inner and outer bounds on the capacity region are derived. Finally, numerical results are provided to illustrate the derived regions.

In this letter the performance limits and design principles of rateless codes over fading channels are studied. The diversity-multiplexing tradeoff (DMT)is used to analyze the system performance for all possible transmission rates. It is revealed from the analysis that the design of such rateless codes follows the design principle of approximately universal codes for multiple-input multiple-output (MIMO) channels. It is also shown that for a single-input single-output (SISO) channel, simple permutation codes of unit length for parallel channels can be transformed directly into rateless codes that achieve the DMT performance limit of the channel.

The wiretap channel type II with an active eavesdropper is considered in this paper. Compared with the eavesdropper model considered in much of the literature, the eavesdropper considered here can not only overhear but also modify the signal transmitted over the channel. Two modification models are considered. In the first model, the eavesdropper erases the bits it observes. In the second model, the eavesdropper modifies the bits it observes. For this channel with memory (introduced by the activity of the eavesdropper), one should conduct the worst case scenario analysis. Novel concatenated coding schemes that provide perfect security for the communications are developed for both models to give bounds on the achievable secrecy rate. The technique to modify the inner code to maintain the secrecy properties of the outer code may be of independent interest.

An authentication counterpart of Wyner's study of the wiretap channel is developed in this work. More specifically, message authentication over noisy channels is studied while impersonation and substitution attacks are investigated for both single- and multiple-message scenarios. For each scenario, information-theoretic lower and upper bounds on the opponent's success, or cheating, probability are derived. Remarkably, in both scenarios, the lower and upper bounds are shown to match, and hence, the fundamental limits on message authentication over noisy channels are fully characterized. The opponent's success probability is further shown to be smaller than that derived in the classical noiseless channel model. These results rely on a novel authentication scheme in which shared key information is used to provide simultaneous protection against both types of attacks. Finally, message authentication for the case in which the source and receiver possess only correlated sequences is studied.

This paper investigates the optimal sensing order problem in multi-channel cognitive medium access control with opportunistic transmissions. The scenario in which the availability probability of each channel is known is considered first. In this case, when the potential channels are identical (except for the availability probabilities) and independent, it is shown that, although the intuitive sensing order (i.e., descending order of the channel availability probabilities) is optimal when adaptive modulation is not used, it does not lead to optimality in general with adaptive modulation. Thus, a dynamic programming approach to the search for an optimal sensing order with adaptive modulation is presented. For some special cases, it is proved that a simple optimal sensing order does exist. More complex scenarios are then considered, e.g., in which the availability probability of each channel is unknown. Optimal strategies are developed to address the challenges created by this additional uncertainty. Finally, a scheme is developed to address the issue of sensing errors.

This paper investigates the problem of maximally utilizing the spectrum opportunities in cognitive radio networks with multiple potential channels. In particular, the optimal sensing order problem in multi-channel cognitive medium access control with opportunistic transmissions is studied. It is first shown that, when the potential channels are identical (except for the availability probabilities) and independent, the intuitive sensing order (i.e., descending order of the channel availability probabilities) does not lead to optimality in general. A dynamic programming approach for the search of optimal sensing order is then presented. Finally, for some special cases, it is proved that a simple optimal sensing order does exist.

In this work, the agility of detection algorithms in cognitive radio is studied. A sequential change detection framework is developed to investigate the delay of detection algorithms. Three scenarios with different information about primary users' parameters available at cognitive users are considered. Optimal detection schemes that minimize the detection delay under certain false alarm constraints are developed. Minimal detection delay is characterized as a function of the false alarm probability and the Kullback-Leibler distance between signal plus noise and noise only models.

The design of medium access control protocols for a cognitive user wishing to opportunistically exploit frequency bands within parts of the radio spectrum having multiple bands is considered. In the scenario under consideration, the availability probability of each channel is unknown a priori to the cognitive user. Hence efficient medium access strategies must strike a balance between exploring the availability of channels and exploiting the opportunities identified thus far. Using a sequential design approach, an optimal medium access strategy is derived. To avoid the prohibitive computational complexity of this optimal strategy, a low complexity asymptotically optimal strategy is also developed. The proposed strategy does not require any prior statistical knowledge about the traffic pattern on the different channels.

In this paper the performance limits and design principles of rateless codes over fading channels are studied. The diversity-multiplexing tradeoff (DMT) is used to analyze the system performance for all possible transmission rates. It is revealed from the analysis that the design of such rateless codes follows the design principle of approximately universal codes for parallel multiple-input multiple-output (MIMO) channels, in which each sub-channel is a MIMO channel. More specifically, it is shown that for a single-input single-output (SISO) channel, the previously developed permutation codes of unit length for parallel channels having rate LR can be transformed directly into rateless codes of length L having multiple rate levels (R, 2R, …, LR), to achieve the DMT performance limit.

This paper studies the K-user Gaussian interference channel with secrecy constraints. Two distinct network models, namely the interference channel with confidential messages and the one with an external eavesdropper, are analyzed. Using interference alignment along with secrecy pre-coding at each transmitter, it is shown that each user in the network can achieve non-zero secure Degrees of Freedoms (DoFs) in both scenarios. In particular, the proposed coding scheme achieves K−2/2K−2 secure DoFs for each user in the interference channel with confidential messages model, and K−2/2K secure DoFs in the case of an external eavesdropper. The fundamental difference between the two scenarios stems from the lack of channel state information (CSI) about the external eavesdropper. Remarkably, the results establish the positive impact of interference on the secrecy capacity of wireless networks.

We consider the secure transmission of information over an ergodic fading channel in the presence of an eavesdropper. Our eavesdropper can be viewed as the wireless counterpart of Wyner's wiretapper. The secrecy capacity of such a system is characterized under the assumption of asymptotically long coherence intervals. We first consider the full channel state information (CSI) case, where the transmitter has access to the channel gains of the legitimate receiver and the eavesdropper. The secrecy capacity under this full CSI assumption serves as an upper bound for the secrecy capacity when only the CSI of the legitimate receiver is known at the transmitter, which is characterized next. In each scenario, the perfect secrecy capacity is obtained along with the optimal power and rate allocation strategies. We then propose a low-complexity on/off power allocation strategy that achieves near-optimal performance with only the main channel CSI. More specifically, this scheme is shown to be asymptotically optimal as the average signal-to-noise ratio (SNR) goes to infinity, and interestingly, is shown to attain the secrecy capacity under the full CSI assumption. Overall, channel fading has a positive impact on the secrecy capacity and rate adaptation, based on the main channel CSI, is critical in facilitating secure communications over slow fading channels.

A game-theoretic framework is developed to design and analyze the resource allocation algorithms in fading multiple-access channels (MACs), where the users are assumed to be selfish, rational, and limited by average power constraints. The maximum sum-rate point on the boundary of the MAC capacity region is shown to be the unique Nash equilibrium of the corresponding water-filling game. This result sheds a new light on the opportunistic communication principle. The base station is then introduced as a player interested in maximizing a weighted sum of the individual rates. A Stackelberg formulation is proposed in which the base station is the designated game leader. In this setup, the base station announces first its strategy defined as the decoding order of the different users, in the successive cancellation receiver, as a function of the channel state. In the second stage, the users compete conditioned on this particular decoding strategy. This formulation is shown to be able to achieve all the corner points of the capacity region, in addition to the maximum sum-rate point. On the negative side, it is shown that there does not exist a base station strategy in this formulation that achieves the rest of the boundary points. To overcome this limitation, a repeated game approach, which achieves the capacity region of the fading MAC, is presented. Finally, the study is extended to vector channels highlighting interesting differences between this scenario and the scalar channel case.

This paper establishes the utility of user cooperation in facilitating secure wireless communications. In particular, the four-terminal relay–eavesdropper channel is introduced and an outer-bound on the optimal rate-equivocation region is derived. Several cooperation strategies are then devised and the corresponding achievable rate-equivocation region are characterized. Of particular interest is the novel noise-forwarding (NF) strategy, where the relay node sends codewords independent of the source message to confuse the eavesdropper. This strategy is used to illustrate the deaf helper phenomenon, where the relay is able to facilitate secure communications while being totally ignorant of the transmitted messages. Furthermore, NF is shown to increase the secrecy capacity in the reversely degraded scenario, where the relay node fails to offer performance gains in the classical setting. The gain offered by the proposed cooperation strategies is then proved theoretically and validated numerically in the additive white Gaussian noise (AWGN) channel.

In this work, the critical role of noisy feedback in enhancing the secrecy capacity of the wiretap channel is established. Unlike previous works, where a noiseless public discussion channel is used for feedback, the feed-forward and feedback signals share the same noisy channel in the present model. Quite interestingly, this noisy feedback model is shown to be more advantageous in the current setting. More specifically, the discrete memoryless modulo-additive channel with a full-duplex destination node is considered first, and it is shown that the judicious use of feedback increases the secrecy capacity to the capacity of the source-destination channel in the absence of the wiretapper. In the achievability scheme, the feedback signal corresponds to a private key, known only to the destination. In the half-duplex scheme, a novel feedback technique that always achieves a positive perfect secrecy rate (even when the source-wiretapper channel is less noisy than the source-destination channel) is proposed. These results hinge on the modulo-additive property of the channel, which is exploited by the destination to perform encryption over the channel without revealing its key to the source. Finally, this scheme is extended to the continuous real valued modulo-Lambda channel where it is shown that the secrecy capacity with feedback is also equal to the capacity in the absence of the wiretapper.

In wireless networks with energy limited nodes, user cooperation is usually exploited to reduce the network energy consumption. In many practical scenarios, however, nodes' selfishness raises doubts on whether each node will be willing to spend its valuable energy in forwarding packets for other users. To analyze this problem, a non-cooperative game theoretic framework is adopted in our work. Using this framework, the critical role of altruistic nodes in encouraging cooperation is established, both for small and large scale networks. In a small network, where nodes utilize the Decode-Forward scheme to cooperate, we show that a relay node, with appropriate strategy and location, successfully turns the Nash Equilibrium from no- cooperation to full-cooperation. In the large scale network, we show that it is sufficient to have a vanishingly small fraction of the nodes to be altruistic, i.e., relay nodes, in order to ensure full cooperation from all the nodes in the network. This result hinges on using the appropriate forwarding policies by the altruistic nodes, as detailed in the sequel. Our work also establishes the sub-optimality of traditional relaying strategies, which ignore the game-theoretic aspect of the problem. An important aspect of our work is that only reward/punishment policies that can be realized on the physical layer are used, and hence, our results establish the achievability of full cooperation without requiring additional incentive mechanisms at the application layer.

It is well known that a non-zero secrecy capacity of the wiretap channel is only possible when the legitimate receiver is less noisy than the wiretapper. This work shows that user cooperation is an efficient solution to this limitation. In particular, the four-terminal wiretap relay channel is considered in our work where several cooperation strategies, that enable secure communication, are constructed and the corresponding rate-equivocation regions are characterized. Of particular interest is the novel noise forwarding strategy which establishes the deaf helper phenomenon. Here, the relay is able to facilitate secure communication over the main channel while being totally ignorant of the transmitted message. The gain offered by the proposed strategies is proved theoretically and validated numerically in the additive white Gaussian noise (AWGN) channel. Overall, our work establishes the utility of user cooperation in facilitating secure communication over wireless channels.

This paper considers wireless networks with energy limited nodes. In this scenario, multi-hop forwarding is needed to minimize the network energy consumption. In many practical scenarios, however, nodes' selfishness raises doubts on whether each node will be willing to forward packets in order to minimize the overall energy expenditure. To analyze this problem, a non-cooperative game theoretic approach is adopted in our work. Using this framework, the critical role of altruistic nodes in encouraging cooperation is established. More specifically, we show that it is sufficient to have a vanishingly small fraction of the nodes to be altruistic, i.e., relay nodes, in order to ensure full cooperation from all the nodes in the network. This result hinges on using the appropriate forwarding policies by the altruistic nodes, as detailed in the sequel. An important aspect of our work is that only reward/punishment policies that can be realized on the physical layer are used, and hence, our results establish the achievability of full cooperation without requiring additional incentive mechanisms at the higher layer.

We consider the secure transmission of information over an ergodic fading channel in the presence of an eavesdropper. Our eavesdropper can be viewed as the wireless counterpart of Wyner's wiretapper. The secrecy capacity of such a system is characterized under the assumption of asymptotically long coherence intervals. We analyze the full Channel State Information (CSI) case, where the transmitter has access to the channel gains of the legitimate receiver and eavesdropper, and the main channel CSI scenario, where only the legitimate receiver channel gain is known at the transmitter. In each scenario, the secrecy capacity is obtained along with the optimal power and rate allocation strategies. We then propose a low-complexity on/off power allocation strategy that achieves near-optimal performance with only the main channel CSI. More specifically, this scheme is shown to be asymptotically optimal as the average SNR goes to infinity, and interestingly, is shown to attain the secrecy capacity under the full CSI assumption. Remarkably, our results reveal the positive impact of fading on the secrecy capacity and establish the critical role of rate adaptation, based on the main channel CSI, in facilitating secure communications over slow fading channels.

This paper investigates the role of user cooperation in facilitating secure wireless communications. In particular, the four-terminal relay-eavesdropper channel is introduced and analyzed. Several cooperation strategies are devised and the corresponding achievable rate-equivocation region are characterized. Of particular interest is the novel Noise-Forwarding (NF) strategy, where the relay node sends codewords independent of the source message to confuse the eavesdropper. This strategy is used to illustrate the deaf helper phenomenon, where the relay is able to facilitate secure communications while being totally ignorant of the transmitted messages. Furthermore, NF is shown to increase the perfect secrecy rate in the reversely degraded scenario, where the relay node fails to offer performance gains in the classical setting. The gain offered by the proposed cooperation strategies is then proved theoretically and validated numerically in the additive white Gaussian noise (AWGN) channel.

We adopt a game theoretic approach for the design and analysis of distributed resource allocation algorithms in fading multiple access channels, where the users are assumed to be selfish, rational and limited by average power constraints. We show that the sum-rate optimal point on the boundary of the multiple access channel capacity region is the unique Nash equilibrium of the corresponding water-filling game. The base-station is then introduced as a player interested in maximizing a weighted sum of the individual rates. We propose a Stackelberg formulation in which the base-station is the designated game leader. We show that this formulation allows for achieving all the corner points of the capacity region, in addition to the sum-rate optimal point. On the negative side, we prove the non-existence of a base-station strategy in this formulation that achieves the rest of the boundary points. To overcome this limitation, we present a repeated game approach which achieves the capacity region of the fading multiple access channel. Finally, we extend our study to vector channels highlighting interesting differences between this scenario and the scalar channel case

We consider a wireless network composed of three nodes and limited by the half-duplex and total power constraints. This formulation encompasses many of the special cases studied in the literature and allows for capturing the common features shared by them. Here, we focus on three special cases, namely, 1) relay channel, 2) multicast channel, and 3) three-way channel. These special cases are judicially chosen to reflect varying degrees of complexity while highlighting the common ground shared by the different variants of the three-node wireless network. For the relay channel, we propose a new cooperation scheme that exploits the wireless feedback gain. This scheme combines the benefits of the decode-and-forward (DF) and compress-and-forward (CF) strategies and avoids the noiseless feedback assumption adopted in earlier works. Our analysis of the achievable rate of this scheme reveals the diminishing feedback gain in both the low and high signal-to-noise ratio (SNR) regimes. Inspired by the proposed feedback strategy, we identify a greedy cooperation framework applicable to both the multicast and three-way channels. Our performance analysis reveals the asymptotic optimality of the proposed greedy approach and the central role of list source-channel decoding in exploiting the receiver side information in the wireless network setting.