Large Language Model (LLM) training is increasingly concentrated in homogeneous datacenters, while private data and underutilized GPUs across universities, laboratories, and edge sites remain difficult to use. This extended abstract presents preliminary results from a geo-distributed LLM training prototype that treats networking constraints as first-order design concerns. The prototype connects three heterogeneous GPU sites via cloud-hosted parameter servers, outbound-only gRPC streams, two-stage delta compression (INT8 quantization + Huffman coding, achieving up to 4× payload reduction), and fault-tolerant rejoin. In real deployments, GPT-2 Medium pretraining achieves stable loss reduction and reaches the target loss 15.2% faster in wall-clock time than the best tested baseline; Llama3-1B pretraining remains stable under larger communication pressure; and cross-site latency traces reveal site-dependent WAN spikes of up to 200s. These results motivate adaptive networking support for synchronization, compression, placement, telemetry, and recovery in geo-distributed LLM training.

Partially observable Markov decision processes (POMDPs) are a general framework for sequential decision-making under latent state uncertainty, yet learning in POMDPs is intractable in the worst case. Motivated by sensing and probing constraints in practice, we study how much online state information (OSI) is sufficient to enable efficient learning guarantees. We formalize a model in which the learner can query only partial OSI (POSI) during interaction. We first prove an information-theoretic hardness result showing that, for general POMDPs, achieving an ϵ-optimal policy can require sample complexity that is exponential unless full OSI is available. We then identify two structured subclasses that remain learnable under POSI and propose corresponding algorithms with provably efficient performance guarantees. In particular, we establish regret upper bounds with Õ (√K) dependence on the number of episodesK, together with complementary lower bounds, thereby delineating when POSI suffices for efficient reinforcement learning. Our results highlight a principled separation between intractable and tractable regimes under incomplete online state access and provide new tools for jointly optimizing POSI queries and learning control actions.

Continual learning (CL) has garnered significant attention because of its ability to adapt to new tasks that arrive over time. Catastrophic forgetting (of old tasks) has been identified as a major issue in CL, as the model adapts to new tasks. The Mixture-of-Experts (MoE) model has recently been shown to effectively mitigate catastrophic forgetting in CL, by employing a gating network to sparsify and distribute diverse tasks among multiple experts. However, there is a lack of theoretical analysis of MoE and its impact on the learning performance in CL. This paper provides the first theoretical results to characterize the impact of MoE in CL via the lens of overparameterized linear regression tasks. We establish the benefit of MoE over a single expert by proving that the MoE model can diversify its experts to specialize in different tasks, while its router learns to select the right expert for each task and balance the loads across all experts. Our study further suggests an intriguing fact that the MoE in CL needs to terminate the update of the gating network after sufficient training rounds to attain system convergence, which is not needed in the existing MoE studies that do not consider the continual task arrival. Furthermore, we provide explicit expressions for the expected forgetting and overall generalization error to characterize the benefit of MoE in the learning performance in CL. Interestingly, adding more experts requires additional rounds before convergence, which may not enhance the learning performance. Finally, we conduct experiments on both synthetic and real datasets to extend these insights from linear models to deep neural networks (DNNs), which also shed light on the practical algorithm design for MoE in CL.

Self-supervised learning has become a cornerstone in computer vision, primarily divided into reconstruction-based methods like masked autoencoders (MAE) and discriminative methods such as contrastive learning (CL). Recent empirical observations reveal that MAE and CL capture different types of representations: CL tends to focus on global patterns, while MAE adeptly captures **both global and subtle local** information simultaneously. Despite a flurry of recent empirical investigations to shed light on this difference, theoretical understanding remains limited, especially on the dominant architecture **vision transformers** (ViTs). In this paper, to provide rigorous insights, we model the visual data distribution by considering two types of spatial features: dominant global features and comparatively minuscule local features, and study the impact of imbalance among these features. We analyze the training dynamics of one-layer softmax-based ViTs on both MAE and CL objectives using gradient descent. Our analysis shows that as the degree of feature imbalance varies, ViTs trained with the MAE objective effectively learn both global and local features to achieve near-optimal reconstruction, while the CL-trained ViTs favor predominantly global features, even under mild imbalance. These results provide a theoretical explanation for distinct behaviors of MAE and CL observed in empirical studies.

Accelerated diffusion models hold the potential to significantly enhance the efficiency of standard diffusion processes. Theoretically, these models have been shown to achieve faster convergence rates than the standard $\mathcal O(1/\epsilon^2)$ rate of vanilla diffusion models, where $\epsilon$ denotes the target accuracy. However, current theoretical studies have established the acceleration advantage only for restrictive target distribution classes, such as those with smoothness conditions imposed along the entire sampling path or with bounded support. In this work, we significantly broaden the target distribution classes with a new accelerated stochastic DDPM sampler. In particular, we show that it achieves accelerated performance for three broad distribution classes not considered before. Our first class relies on the smoothness condition posed only to the target density $q_0$, which is far more relaxed than the existing smoothness conditions posed to all $q_t$ along the entire sampling path. Our second class requires only a finite second moment condition, allowing for a much wider class of target distributions than the existing finite-support condition. Our third class is Gaussian mixture, for which our result establishes the first acceleration guarantee. Moreover, among accelerated DDPM type samplers, our results specialized for bounded-support distributions show an improved dependency on the data dimension $d$. Our analysis introduces a novel technique for establishing performance guarantees via constructing a tilting factor representation of the convergence error and utilizing Tweedie's formula to handle Taylor expansion terms. This new analytical framework may be of independent interest.

The denoising diffusion model has recently emerged as a powerful generative technique, capable of transforming noise into meaningful data. While theoretical convergence guarantees for diffusion models are well established when the target distribution aligns with the training distribution, practical scenarios often present mismatches. One common case is in the zero-shot conditional diffusion sampling, where the target conditional distribution is different from the (unconditional) training distribution. These score-mismatched diffusion models remain largely unexplored from a theoretical perspective. In this paper, we present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers, focusing on target distributions with finite second moments. We show that score mismatches result in an asymptotic distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions. This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise. Interestingly, the derived convergence upper bound offers useful guidance for designing a novel bias-optimal zero-shot sampler in linear conditional models that minimizes the asymptotic bias. For such bias-optimal samplers, we further establish convergence guarantees with explicit dependencies on dimension and conditioning, applied to several interesting target distributions, including those with bounded support and Gaussian mixtures. Our findings are supported by numerical studies.

Decentralized bilevel optimization (DBO) provides a powerful framework for multi-agent systems to solve local bilevel tasks in a decentralized fashion without the need for a central server. However, most existing DBO methods rely on lower-level strong convexity (LLSC) to guarantee unique solutions and a well-defined hypergradient for stationarity measure, hindering their applicability in many practical scenarios not satisfying LLSC. To overcome this limitation, we introduce a new single-loop DBO algorithm called diminishing quadratically-regularized bilevel decentralized optimization (DUET), which eliminates the need for LLSC by introducing a diminishing quadratic regularization to the lower-level (LL) objective. We show that DUET achieves an iteration complexity of $O(1/T^{1-5p-\frac{11}{4}\tau})$ for approximate KKT-stationary point convergence under relaxed assumptions, where $p$ and $\tau $ are control parameters for LL learning rate and averaging, respectively. In addition, our DUET algorithm incorporates gradient tracking to address data heterogeneity, a key challenge in DBO settings. To the best of our knowledge, this is the first work to tackle DBO without LLSC under decentralized settings with data heterogeneity. Numerical experiments validate the theoretical findings and demonstrate the practical effectiveness of our proposed algorithms.

Pretraining large language models (LLMs) on vast and heterogeneous datasets is crucial for achieving state-of-the-art performance across diverse downstream tasks. However, current training paradigms treat all samples equally, overlooking the importance or relevance of individual samples throughout the training process. Existing reweighting strategies, which primarily focus on group-level data importance, fail to leverage fine-grained instance-level information and do not adapt dynamically to individual sample importance as training progresses. In this paper, we introduce novel algorithms for dynamic, instance-level data reweighting aimed at improving both the efficiency and effectiveness of LLM pretraining. Our methods adjust the weight of each training sample based on its loss value in an online fashion, allowing the model to dynamically focus on more informative or important samples at the current training stage. In particular, our framework allows us to systematically devise reweighting strategies deprioritizing redundant or uninformative data, which we find tend to work best. Furthermore, we develop a new theoretical framework for analyzing the impact of loss-based reweighting on the convergence of gradient-based optimization, providing the first formal characterization of how these strategies affect convergence bounds. We empirically validate our approach across a spectrum of tasks, from pretraining 7B and 1.4B parameter LLMs to smaller-scale language models and linear regression problems, demonstrating that our loss-based reweighting approach can lead to faster convergence and significantly improved performance.

Understanding how transformers learn and utilize hidden connections between tokens is crucial to understand the behavior of large language models. To understand this mechanism, we consider the task of two-mixture of linear classification which possesses a hidden correspondence structure among tokens, and study the training dynamics of a symmetric two-headed transformer with ReLU neurons. Motivated by the stage-wise learning phenomenon in our experiments, we design and theoretically analyze a three-stage training algorithm, which can effectively characterize the actual gradient descent dynamics when we simultaneously train the neuron weights and the softmax attention. The first stage is a neuron learning stage, where the neurons align with the underlying signals. The second stage is a attention feature learning stage, where we analyze the feature learning process of how the attention learns to utilize the relationship between the tokens to solve certain hard samples. In the meantime, the attention features evolve from a nearly non-separable state (at the initialization) to a well-separated state. The third stage is a convergence stage, where the population loss is driven towards zero. The key technique in our analysis of softmax attention is to identify a critical sub-system inside a large dynamical system and bound the growth of the non-linear sub-system by a linear system. Finally, we discuss the setting with more than two mixtures. We empirically show the difficulty of generalizing our analysis of the gradient flow dynamics to the case even when the number of mixtures equals three, although the transformer can still successfully learn such distribution. On the other hand, we show by construction that there exists a transformer that can solve mixture of linear classification given any arbitrary number of mixtures.

Rehearsal-based methods have shown superior performance in addressing catastrophic forgetting in continual learning (CL) by storing and training on a subset of past data alongside new data in current task. While such a concurrent rehearsal strategy is widely used, it remains unclear if this approach is always optimal. Inspired by human learning, where sequentially revisiting tasks helps mitigate forgetting, we explore whether sequential rehearsal can offer greater benefits for CL compared to standard concurrent rehearsal. To address this question, we conduct a theoretical analysis of rehearsal-based CL in overparameterized linear models, comparing two strategies: 1) Concurrent Rehearsal, where past and new data are trained together, and 2) Sequential Rehearsal, where new data is trained first, followed by revisiting past data sequentially. By explicitly characterizing forgetting and generalization error, we show that sequential rehearsal performs better when tasks are less similar. These insights further motivate a novel Hybrid Rehearsal method, which trains similar tasks concurrently and revisits dissimilar tasks sequentially. We characterize its forgetting and generalization performance, and our experiments with deep neural networks further confirm that the hybrid approach outperforms standard concurrent rehearsal. This work provides the first comprehensive theoretical analysis of rehearsal-based CL.

Language recognition tasks are fundamental in natural language processing (NLP) and have been widely used to benchmark the performance of large language models (LLMs). These tasks also play a crucial role in explaining the working mechanisms of transformers. In this work, we focus on two representative tasks in the category of regular language recognition, known as 'even pairs' and 'parity check', the aim of which is to determine whether the occurrences of certain subsequences in a given sequence are even. Our goal is to explore how a one-layer transformer, consisting of an attention layer followed by a linear layer, learns to solve these tasks by theoretically analyzing its training dynamics under gradient descent. While even pairs can be solved directly by a one-layer transformer, parity check need to be solved by integrating Chain-of-Thought (CoT), either into the inference stage of a transformer well-trained for the even pairs task, or into the training of a one-layer transformer. For both problems, our analysis shows that the joint training of attention and linear layers exhibits two distinct phases. In the first phase, the attention layer grows rapidly, mapping data sequences into separable vectors. In the second phase, the attention layer becomes stable, while the linear layer grows logarithmically and approaches in direction to a max-margin hyperplane that correctly separates the attention layer outputs into positive and negative samples, and the loss decreases at a rate of $O(1/t)$. Our experiments validate those theoretical results.

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.

Transformers have demonstrated remarkable capabilities in multi-step reasoning tasks. However, understandings of the underlying mechanisms by which they acquire these abilities through training remain limited, particularly from a theoretical standpoint. This work investigates how transformers learn to solve symbolic multi-step reasoning problems through chain-of-thought processes, focusing on path-finding in trees. We analyze two intertwined tasks: a backward reasoning task, where the model outputs a path from a goal node to the root, and a more complex forward reasoning task, where the model implements two-stage reasoning by first identifying the goal-to-root path and then reversing it to produce the root-to-goal path. Our theoretical analysis, grounded in the dynamics of gradient descent, shows that trained one-layer transformers can provably solve both tasks with generalization guarantees to unseen trees. In particular, our multi-phase training dynamics for forward reasoning elucidate how different attention heads learn to specialize and coordinate autonomously to solve the two subtasks in a single autoregressive path. These results provide a mechanistic explanation of how trained transformers can implement sequential algorithmic procedures. Moreover, they offer insights into the emergence of reasoning abilities, suggesting that when tasks are structured to take intermediate chain-of-thought steps, even shallow multi-head transformers can effectively solve problems that would otherwise require deeper architectures.

It has been observed that applying pruning-at-initialization methods and training the sparse networks can sometimes yield slightly better test performance than training the original dense network. Such experimental observations are yet to be understood theoretically. This work makes the first attempt to study this phenomenon. Specifically, we identify a theoretical minimal setting and study a classification task with a one-hidden-layer neural network, which is randomly pruned according to different rates at the initialization. We show that as long as the pruning rate is below a certain threshold, the network provably exhibits good generalization performance after training.More surprisingly, the generalization bound gets better as the pruning rate mildly gets larger. To complement this positive result, we also show a negative result: there exists a large pruning rate such that while gradient descent is still able to drive the training loss toward zero, the generalization performance is no better than random guessing. This further suggests that pruning can change the feature learning process, which leads to the performance drop of the pruned neural network. To our knowledge, this is the first theory work studying how different pruning rates affect neural networks' performance, suggesting that an appropriate pruning rate might improve the neural network's generalization.

Distributionally robust offline reinforcement learning (RL) aims to find a policy that performs the best under the worst environment within an uncertainty set using an offline dataset collected from a nominal model. While recent advances in robust RL focus on Markov decision processes (MDPs), robust non-Markovian RL is limited to planning problem where the transitions in the uncertainty set are known. In this paper, we study the learning problem of robust offline non-Markovian RL. Specifically, when the nominal model admits a low-rank structure, we propose a new algorithm, featuring a novel dataset distillation and a lower confidence bound (LCB) design for robust values under different types of the uncertainty set. We also derive new dual forms for these robust values in non-Markovian RL, making our algorithm more amenable to practical implementation. By further introducing a novel type-I concentrability coefficient tailored for offline low-rank non-Markovian decision processes, we prove that our algorithm can find an$\epsilon $-optimal robust policy using$O(1/\epsilon ^{2})$offline samples. Moreover, we extend our algorithm to the case when the nominal model does not have specific structure. With a new type-II concentrability coefficient, the extended algorithm also enjoys polynomial sample efficiency under all different types of the uncertainty set.

Contextual Markov decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. While CMDPs serve as an important framework to model many real-world applications with time-varying environments, they are largely unexplored from theoretical perspective. In this paper, we study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights. For both models, we propose novel model-based algorithms and show that they enjoy guaranteed $\epsilon$-suboptimality gap with desired polynomial sample complexity. In particular, instantiating our result for the first model to the tabular CMDP improves the existing result by removing the reachability assumption. Our result for the second model is the first-known result for such a type of function approximation models. Comparison between our results for the two models further indicates that having context-varying features leads to much better sample efficiency than having common representations for all contexts under linear CMDPs.

Online nonconvex optimization has been an active area of research recently. Previous studies either considered the global regret with full information about the objective functions, or studied the local regret with window-smoothed objective functions, which required access to unlimited number of gradient oracles per time step. In this paper, we focus on the more challenging and practical setting, where access to only a single oracle is allowed per time step, and take the local regret of the original (i.e., unsmoothed) objective functions as the performance metric. Specifically, for both settings respectively with a single exact and stochastic gradient oracle feedback, we derive lower bounds on the local regret and show that the classical online (stochastic) gradient descent algorithms are optimal. Moreover, for the more challenging setting with a single function value oracle feedback, we develop an online algorithm based on a one-point running difference gradient estimator, and show that such an algorithm achieves a local regret that a generic stochastic gradient oracle can best achieve.

In multi-task reinforcement learning (RL) under Markov decision processes (MDPs), the presence of shared latent structures among multiple MDPs has been shown to yield significant benefits to the sample efficiency compared to single-task RL. In this paper, we investigate whether such a benefit can extend to more general sequential decision making problems such as predictive state representations (PSRs). The main challenge here is that the large and complex model space makes it hard to identify what types of common latent structure of multi-task PSRs can reduce the model complexity and improve sample efficiency. To this end, we posit a joint model class for tasks and use the notion of $\eta$-bracketing number to quantify its complexity; this number also serves as a general metric to capture the similarity of tasks and thus determines the benefit of multi-task over single-task RL. We first study upstream multi-task learning over PSRs, in which all tasks share the same observation and action spaces. We propose a provably efficient algorithm UMT-PSR for finding near-optimal policies for all PSRs, and demonstrate that the advantage of multi-task learning manifests if the joint model class of PSRs has a smaller $\eta$-bracketing number compared to that of individual single-task learning. We further investigate downstream learning, in which the agent needs to learn a new target task that shares some commonalities with the upstream tasks via a similarity constraint. By exploiting the learned PSRs from the upstream, we develop a sample-efficient algorithm that provably finds a near-optimal policy. Upon specialization to some examples with small $\eta$-bracketing numbers, our results further highlight the benefit compared to directly learning a single-task PSR.

The general sequential decision-making problem, which includes Markov decision processes (MDPs) and partially observable MDPs (POMDPs) as special cases, aims at maximizing a cumulative reward by making a sequence of decisions based on a history of observations and actions over time. Recent studies have shown that the sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs). Despite these advancements, existing approaches typically involve oracles or steps that are computationally intractable. On the other hand, the upper confidence bound (UCB) based approaches, which have served successfully as computationally efficient methods in bandits and MDPs, have not been investigated for more general PSRs, due to the difficulty of optimistic bonus design in these more challenging settings. This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. We further characterize the sample complexity bounds for our designed UCB-type algorithms for both online and offline PSRs. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.

Assigning importance weights to adversarial data has achieved great success in training adversarially robust networks under limited model capacity. However, existing instance-reweighted adversarial training (AT) methods heavily depend on heuristics and/or geometric interpretations to determine those importance weights, making these algorithms lack rigorous theoretical justification/guarantee. Moreover, recent research has shown that adversarial training suffers from a severe non-uniform robust performance across the training distribution, e.g., data points belonging to some classes can be much more vulnerable to adversarial attacks than others. To address both issues, in this paper, we propose a novel doubly-robust instance reweighted AT framework, which allows to obtain the importance weights via exploring distributionally robust optimization (DRO) techniques, and at the same time boosts the robustness on the most vulnerable examples. In particular, our importance weights are obtained by optimizing the KL-divergence regularized loss function, which allows us to devise new algorithms with a theoretical convergence guarantee. Experiments on standard classification datasets demonstrate that our proposed approach outperforms related state-of-the-art baseline methods in terms of average robust performance, and at the same time improves the robustness against attacks on the weakest data points. Codes can be found in the Supplement.

The problem of two-player zero-sum Markov games has recently attracted increasing interests in theoretical studies of multi-agent reinforcement learning (RL). In particular, for finite-horizon episodic Markov decision processes (MDPs), it has been shown that model-based algorithms can find an $\epsilon$-optimal Nash Equilibrium (NE) with the sample complexity of $O(H^3SAB/\epsilon^2)$, which is optimal in the dependence of the horizon $H$ and the number of states $S$ (where $A$ and $B$ denote the number of actions of the two players, respectively). However, none of the existing model-free algorithms can achieve such an optimality. In this work, we propose a model-free stage-based algorithm and show that it achieves the same sample complexity as the best model-based algorithm, and hence for the first time demonstrate that model-free algorithms can enjoy the same optimality in the $H$ dependence as model-based algorithms. The main improvement of the dependency on $H$ arises by leveraging the popular variance reduction technique based on the reference-advantage decomposition previously used only for single-agent RL. However, such a technique relies on a critical monotonicity property of the value function, which does not hold in Markov games due to the update of the policy via the coarse correlated equilibrium (CCE) oracle. Thus, to extend such a technique to Markov games, our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions whose value difference is the smallest in the history in order to achieve the desired improvement in the sample efficiency.

Transformers have recently revolutionized many domains in modern machine learning and one salient discovery is their remarkable in-context learning capability, where models can solve an unseen task by utilizing task-specific prompts without further parameters fine-tuning. This also inspired recent theoretical studies aiming to understand the in-context learning mechanism of transformers, which however focused only on *linear* transformers. In this work, we take the first step toward studying the learning dynamics of a one-layer transformer with *softmax* attention trained via gradient descent in order to in-context learn linear function classes. We consider a structured data model, where each token is randomly sampled from a set of feature vectors in either balanced or imbalanced fashion. For data with balanced features, we establish the finite-time convergence guarantee with near-zero prediction error by navigating our analysis over two phases of the training dynamics of the attention map. More notably, for data with imbalanced features, we show that the learning dynamics take a stage-wise convergence process, where the transformer first converges to a near-zero prediction error for the query tokens of dominant features, and then converges later to a near-zero error for query tokens of under-represented features, via one and four training phases. Our proof features new techniques for analyzing the competing strengths of two types of attention weights, the change of which determines different training phases.

Function approximation has experienced significant success in the field of reinforcement learning (RL). Despite a handful of progress on developing theory for Nonstationary RL with function approximation under structural assumptions, existing work for nonstationary RL with general function approximation is still limited. In this work, we propose a UCB-type of algorithm LSVI-Nonstationary following the popular least-square-value-iteration (LSVI) framework. LSVI-Nonstationary features the restart mechanism and a new design of bonus term to handle nonstationarity, and performs no worse than the existing confidence-set based algorithm SW-OPEA in [1], which has been shown to outperform the existing algorithms for nonstationary linear and tabular MDPs in the small variation budget setting.

Federated Learning (FL) has gained significant popularity due to its effectiveness in training machine learning models across diverse sites without requiring direct data sharing. While various algorithms along with their optimization analyses have shown that FL with local updates is a communication-efficient distributed learning framework, the generalization performance of FL with local updates has received comparatively less attention. This lack of investigation can be attributed to the complex interplay between data heterogeneity and infrequent communication due to the local updates within the FL framework. This motivates us to investigate a fundamental question in FL: Can we quantify the impact of data heterogeneity and local updates on the generalization performance for FL as the learning process evolves? To this end, we conduct a comprehensive theoretical study of FL's generalization performance using a linear model as the first step, where the data heterogeneity is considered for both the stationary and online/non-stationary cases. By providing closed-form expressions of the model error, we rigorously quantify the impact of the number of the local updates (denoted as K) under three settings (K = 1, K < ∞, and K = ∞) and show how the generalization performance evolves with the number of rounds t. Our investigation also provides a comprehensive understanding of how different configurations (including the number of model parameters p and the number of training samples n) contribute to the overall generalization performance, thus shedding new insights (such as benign overfitting) for implementing FL over networks.

Transformers have achieved extraordinary success in modern machine learning due to their excellent ability to handle sequential data, especially in next-token prediction (NTP) tasks. However, the theoretical understanding of their performance in NTP is limited, with existing studies focusing mainly on asymptotic performance. This paper provides a fine-grained non-asymptotic analysis of the training dynamics of a one-layer transformer consisting of a self-attention module followed by a feed-forward layer. We first characterize the essential structural properties of training datasets for NTP using a mathematical framework based on partial orders. Then, we design a two-stage training algorithm, where the pre-processing stage for training the feed-forward layer and the main stage for training the attention layer exhibit fast convergence performance. Specifically, both layers converge sub-linearly to the direction of their corresponding max-margin solutions. We also show that the cross-entropy loss enjoys a linear convergence rate. Furthermore, we show that the trained transformer presents non-trivial prediction ability with dataset shift, which sheds light on the remarkable generalization performance of transformers. Our analysis technique involves the development of novel properties on the attention gradient and further in-depth analysis of how these properties contribute to the convergence of the training process. Our experiments further validate our theoretical findings.

In-context learning (ICL) refers to a remarkable capability of pretrained large language models, which can learn a new task given a few examples during inference. However, theoretical understanding of ICL is largely under-explored, particularly whether transformers can be trained to generalize to unseen examples in a prompt, which will require the model to acquire contextual knowledge of the prompt for generalization. This paper investigates the training dynamics of transformers by gradient descent through the lens of non-linear regression tasks. The contextual generalization here can be attained via learning the template function for each task in-context, where all template functions lie in a linear space with $m$ basis functions. We analyze the training dynamics of one-layer multi-head transformers to {in-contextly} predict unlabeled inputs given partially labeled prompts, where the labels contain Gaussian noise and the number of examples in each prompt are not sufficient to determine the template. Under mild assumptions, we show that the training loss for a one-layer multi-head transformer converges linearly to a global minimum. Moreover, the transformer effectively learns to perform ridge regression over the basis functions. To our knowledge, this study is the first provable demonstration that transformers can learn contextual (i.e., template) information to generalize to both unseen examples and tasks when prompts contain only a small number of query-answer pairs.

Understanding the training dynamics of transformers is important to explain the impressive capabilities behind large language models. In this work, we study the dynamics of training a shallow transformer on a task of recognizing co-occurrence of two designated words. In the literature of studying training dynamics of transformers, several simplifications are commonly adopted such as weight reparameterization, attention linearization, special initialization, and lazy regime. In contrast, we analyze the gradient flow dynamics of simultaneously training three attention matrices and a linear MLP layer from random initialization, and provide a framework of analyzing such dynamics via a coupled dynamical system. We establish near minimum loss and characterize the attention model after training. We discover that gradient flow serves as an inherent mechanism that naturally divide the training process into two phases. In Phase 1, the linear MLP quickly aligns with the two target signals for correct classification, whereas the softmax attention remains almost unchanged. In Phase 2, the attention matrices and the MLP evolve jointly to enlarge the classification margin and reduce the loss to a near minimum value. Technically, we prove a novel property of the gradient flow, termed \textit{automatic balancing of gradients}, which enables the loss values of different samples to decrease almost at the same rate and further facilitates the proof of near minimum training loss. We also conduct experiments to verify our theoretical results.

We study training one-hidden-layer ReLU networks in the neural tangent kernel (NTK) regime, where the networks' biases are initialized to some constant rather than zero. We prove that under such initialization, the neural network will have sparse activation throughout the entire training process, which enables fast training procedures via some sophisticated computational methods. With such initialization, we show that the neural networks possess a different limiting kernel which we call bias-generalized NTK, and we study various properties of the neural networks with this new kernel. We first characterize the gradient descent dynamics. In particular, we show that the network in this case can achieve as fast convergence as the dense network, as opposed to the previous work suggesting that the sparse networks converge slower. In addition, our result improves the previous required width to ensure convergence. Secondly, we study the networks' generalization: we show a width-sparsity dependence, which yields a sparsity-dependent Rademacher complexity and generalization bound. To our knowledge, this is the first sparsity-dependent generalization result via Rademacher complexity. Lastly, we study the smallest eigenvalue of this new kernel. We identify a data-dependent region where we can derive a much sharper lower bound on the NTK's smallest eigenvalue than the worst-case bound previously known. This can lead to improvement in the generalization bound.

The remarkable success of reinforcement learning (RL) heavily relies on observing the reward of every visited state-action pair. In many real world applications, however, an agent can observe only a score that represents the quality of the whole trajectory, which is referred to as the trajectory-wise reward. In such a situation, it is difficult for standard RL methods to well utilize trajectory-wise reward, and large bias and variance errors can be incurred in policy evaluation. In this work, we propose a novel offline RL algorithm, called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED), which decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value iteration based on the learned proxy reward. To ensure the value functions constructed by PARTED are always pessimistic with respect to the optimal ones, we design a new penalty term to offset the uncertainty of the proxy reward. We first show that our PARTED achieves an$\tilde {\mathcal {O}}(dH^{3}/\sqrt {N})$suboptimality for linear MDPs, where d is the dimension of the feature, H is the episode length, and N is the size of the offline dataset. We further extend our algorithm and results to general large-scale episodic MDPs with neural network function approximation. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.

The actor-critic (AC) reinforcement learning algorithms have been the powerhouse behind many challenging applications. Nevertheless, its convergence is fragile in general. To study its instability, existing works mostly consider the uncommon double-loop variant or basic models with finite state and action space. We investigate the more practical single-sample two-timescale AC for solving the canonical linear quadratic regulator (LQR) problem, where the actor and the critic update only once with a single sample in each iteration on an unbounded continuous state and action space. Existing analysis cannot conclude the convergence for such a challenging case. We develop a new analysis framework that allows establishing the global convergence to an epsilon-optimal solution with at most an order of epsilon to -2.5 sample complexity. To our knowledge, this is the first finite-time convergence analysis for the single sample two-timescale AC for solving LQR with global optimality. The sample complexity improves those of other variants by orders, which sheds light on the practical wisdom of single sample algorithms. We also further validate our theoretical findings via comprehensive simulation comparisons.

Learning to optimize (L2O) has gained increasing popularity, which automates the design of optimizers by data-driven approaches. However, current L2O methods often suffer from poor generalization performance in at least two folds: (i) applying the L2O-learned optimizer to unseen optimizees, in terms of lowering their loss function values (optimizer generalization, or “generalizable learning of optimizers”); and (ii) the test performance of an optimizee (itself as a machine learning model), trained by the optimizer, in terms of the accuracy over unseen data (optimizee generalization, or “learning to generalize”). While the optimizer generalization has been recently studied, the optimizee generalization (or learning to generalize) has not been rigorously studied in the L2O context, which is the aim of this paper. We first theoretically establish an implicit connection between the local entropy and the Hessian, and hence unify their roles in the handcrafted design of generalizable optimizers as equivalent metrics of the landscape flatness of loss functions. We then propose to incorporate these two metrics as flatness-aware regularizers into the L2O framework in order to meta-train optimizers to learn to generalize, and theoretically show that such generalization ability can be learned during the L2O meta-training process and then transformed to the optimizee loss function. Extensive experiments consistently validate the effectiveness of our proposals with substantially improved generalization on multiple sophisticated L2O models and diverse optimizees.

We investigate online nonconvex optimization from a local regret minimization perspective. Previous studies along this line implicitly required the access to sufficient gradient oracles at each time instance in order to design double-loop algorithms. In this work, we focus on more challenging but practical settings where only limited number of oracles are available in online nonconvex optimization, including window-smoothed single gradient oracle (Window-SGO), single function value oracle (Window-SVO) and multiple function value oracles (Window-MVO). Specifically, in the Window-SGO setting which allows only single-loop algorithm design, we derive a local regret lower bound, which indicates that single-loop algorithms are provably worse than double-loop algorithms. Further, the simple classical OGD algorithm achieves the window-unconditioned lower bound. Moreover, in the Window-SVO setting, we propose a novel single-loop online algorithm named SkipOGD, and show that it achieves a near-optimal local regret that matches the Window-SGO regret lower bound up to a factor of the dimension $d$ due to the function value feedback. Lastly, in the Window-MVO setting, we propose a new double-loop online algorithm named LoopOGD and show that it achieves a smooth trade-off between regret minimization and sample complexity over the number of oracle calls $K$ per time instance. In particular, with $K=1$ and $wd$, LoopOGD respectively achieves our regret lower bound with Window-SGO (up to the factor $d$ due to function value feedback) and the existing regret lower bound with multiple gradient oracle feedback.

Various optimal gradient-based algorithms have been developed for smooth nonconvex optimization. However, many nonconvex machine learning problems do not belong to the class of smooth functions and therefore the existing algorithms are sub-optimal. Instead, these problems have been shown to satisfy certain generalized-smooth conditions, which have not been well understood in the existing literature. In this paper, we propose a notion of $\alpha$-symmetric generalized-smoothness that substantially extends the existing notions and covers many important functions such as high-order polynomials and exponential functions. We study the fundamental properties and establish descent lemmas for the functions in this class. Then, to solve such a large class of nonconvex problems, we design a special deterministic normalized gradient descent algorithm that achieves the optimal iteration complexity $\mathcal{O}(\epsilon^{-2})$, and also prove that the popular SPIDER variance reduction algorithm achieves the optimal sample complexity $\mathcal{O}(\epsilon^{-3})$. Our results show that solving generalized-smooth nonconvex problems is as efficient as solving smooth nonconvex problems.

General function approximation is a powerful tool to handle large state and action spaces in a broad range of reinforcement learning (RL) scenarios. However, theoretical understanding of non-stationary MDPs with general function approximation is still limited. In this paper, we make the first such an attempt. We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs, which subsumes majority of existing tractable RL problems in static MDPs as well as non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA, which features a sliding window mechanism and a new confidence set design for non-stationary MDPs. We then establish an upper bound on the dynamic regret for the proposed algorithm, and show that SW-OPEA is provably efficient as long as the variation budget is not significantly large. We further demonstrate via examples of non-stationary linear and tabular MDPs that our algorithm performs better in small variation budget scenario than the existing UCB-type algorithms. To the best of our knowledge, this is the first dynamic regret analysis in non-stationary MDPs with general function approximation.

Continual learning (CL), which aims to learn a sequence of tasks, has attracted significant recent attention. However, most work has focused on the experimental performance of CL, and theoretical studies of CL are still limited. In particular, there is a lack of understanding on what factors are important and how they affect "catastrophic forgetting" and generalization performance. To fill this gap, our theoretical analysis, under overparameterized linear models, provides the first-known explicit form of the expected forgetting and generalization error for a general CL setup with an arbitrary number of tasks. Further analysis of such a key result yields a number of theoretical explanations about how overparameterization, task similarity, and task ordering affect both forgetting and generalization error of CL. More interestingly, by conducting experiments on real datasets using deep neural networks (DNNs), we show that some of these insights even go beyond the linear models and can be carried over to practical setups. In particular, we use concrete examples to show that our results not only explain some interesting empirical observations in recent studies, but also motivate better practical algorithm designs of CL.

In many applications of Reinforcement Learning (RL), it is critically important that the algorithm performs safely, such that instantaneous hard constraints are satisfied at each step, and unsafe states and actions are avoided. However, existing algorithms for ``safe'' RL are often designed under constraints that either require expected cumulative costs to be bounded or assume all states are safe. Thus, such algorithms could violate instantaneous hard constraints and traverse unsafe states (and actions) in practice. Hence, in this paper, we develop the first near-optimal safe RL algorithm for episodic Markov Decision Processes with unsafe states and actions under instantaneous hard constraints and the linear mixture model. It achieves a regret $\tilde{O}(\frac{d H^3 \sqrt{d K}}{\Delta_c})$ that nearly matches the state-of-the-art regret in the setting with only unsafe actions and that in the unconstrained setting, and is safe at each step, where $d$ is the feature-mapping dimension, $K$ is the number of episodes, $H$ is the episode length, and $\Delta_c$ is a safety-related parameter. We also provide a lower bound $\tilde{\Omega}(\max\{d H \sqrt{K}, \frac{H}{\Delta_c^2}\})$, which indicates that the dependency on $\Delta_c$ is necessary. Further, both our algorithm design and regret analysis involve several novel ideas, which may be of independent interest.

Reinforcement learning (RL) under changing environment models many real-world applications via nonstationary Markov Decision Processes (MDPs), and hence gains considerable interest. However, theoretical studies on nonstationary MDPs in the literature have mainly focused on tabular and linear (mixture) MDPs, which do not capture the nature of unknown representation in deep RL. In this paper, we make the first effort to investigate nonstationary RL under episodic low-rank MDPs, where both transition kernels and rewards may vary over time, and the low-rank model contains unknown representation in addition to the linear state embedding function. We first propose a parameter-dependent policy optimization algorithm called PORTAL, and further improve PORTAL to its parameter-free version of Ada-PORTAL, which is able to tune its hyper-parameters adaptively without any prior knowledge of nonstationarity. For both algorithms, we provide upper bounds on the average dynamic suboptimality gap, which show that as long as the nonstationarity is not significantly large, PORTAL and Ada-PORTAL are sample-efficient and can achieve arbitrarily small average dynamic suboptimality gap with polynomial sample complexity.

Bilevel optimization has become a powerful tool in a wide variety of machine learning problems. However, the current nonconvex bilevel optimization considers an offline dataset and static functions, which may not work well in emerging online applications with streaming data and time-varying functions. In this work, we study online bilevel optimization (OBO) where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. To deal with the function variations and the unavailability of the true hypergradients in OBO, we propose a single-loop online bilevel optimizer with window averaging (SOBOW), which updates the outer-level decision based on a window average of the most recent hypergradient estimations stored in the memory. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. To handle the unique technical difficulties rooted in single-loop update and function variations for OBO, we develop a novel analytical technique that disentangles the complex couplings between decision variables, and carefully controls the hypergradient estimation error. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions. Extensive experiments across multiple domains corroborate the effectiveness of SOBOW.

Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. Although recent studies have characterized the convergence rate for several such popular algorithms, it is still unclear how much further these convergence rates can be improved. In this paper, we address this fundamental question from two perspectives. First, we provide the first-known lower complexity bounds of $\widetilde \Omega\bigg(\sqrt{\frac{L_y\widetilde L_{xy}^2}{\mu_x\mu_y^2}}\bigg)$ and $\widetilde \Omega\big(\frac{1}{\sqrt{\epsilon}}\min\{\kappa_y,\frac{1}{\sqrt{\epsilon^{3}}}\}\big)$ respectively for strongly-convex-strongly-convex and convex-strongly-convex bilevel optimizations. Second, we propose an accelerated bilevel optimizer named AccBiO, for which we provide the first-known complexity bounds without the gradient boundedness assumption (which was made in existing analyses) under the two aforementioned geometries. We also provide significantly tighter upper bounds than the existing complexity when the bounded gradient assumption does hold. We show that AccBiO achieves the optimal results (i.e., the upper and lower bounds match up to logarithmic factors) when the inner-level problem takes a quadratic form with a constant-level condition number. Interestingly, our lower bounds under both geometries are larger than the corresponding optimal complexities of minimax optimization, establishing that bilevel optimization is provably more challenging than minimax optimization. Our theoretical results are validated by numerical experiments.

As representation learning becomes a powerful technique to reduce sample complexity in reinforcement learning (RL) in practice, theoretical understanding of its advantage is still limited. In this paper, we theoretically characterize the benefit of representation learning under the low-rank Markov decision process (MDP) model. We first study multitask low-rank RL (as upstream training), where all tasks share a common representation, and propose a new multitask reward-free algorithm called REFUEL. REFUEL learns both the transition kernel and the near-optimal policy for each task, and outputs a well-learned representation for downstream tasks. Our result demonstrates that multitask representation learning is provably more sample-efficient than learning each task individually, as long as the total number of tasks is above a certain threshold. We then study the downstream RL in both online and offline settings, where the agent is assigned with a new task sharing the same representation as the upstream tasks. For both online and offline settings, we develop a sample-efficient algorithm, and show that it finds a near-optimal policy with the suboptimality gap bounded by the sum of the estimation error of the learned representation in upstream and a vanishing term as the number of downstream samples becomes large. Our downstream results of online and offline RL further capture the benefit of employing the learned representation from upstream as opposed to learning the representation of the low-rank model directly. To the best of our knowledge, this is the first theoretical study that characterizes the benefit of representation learning in exploration-based reward-free multitask RL for both upstream and downstream tasks.

Despite the empirical success of deep meta-learning, theoretical understanding of overparameterized meta-learning is still limited. This paper studies the generalization of a widely used meta-learning approach, Model-Agnostic Meta-Learning (MAML), which aims to find a good initialization for fast adaptation to new tasks. Under a mixed linear regression model, we analyze the generalization properties of MAML trained with SGD in the overparameterized regime. We provide both upper and lower bounds for the excess risk of MAML, which captures how SGD dynamics affect these generalization bounds. With such sharp characterizations, we further explore how various learning parameters impact the generalization capability of overparameterized MAML, including explicitly identifying typical data and task distributions that can achieve diminishing generalization error with overparameterization, and characterizing the impact of adaptation learning rate on both excess risk and the early stopping time. Our theoretical findings are further validated by experiments.

Bilevel optimization has arisen as a powerful tool for solving a variety of machine learning problems. Two current popular bilevel optimizers AID-BiO and ITD-BiO naturally involve solving one or two sub-problems, and consequently, whether we solve these problems with loops (that take many iterations) or without loops (that take only a few iterations) can significantly affect the overall computational efficiency. Existing studies in the literature cover only some of those implementation choices, and the complexity bounds available are not refined enough to enable rigorous comparison among different implementations. In this paper, we first establish unified convergence analysis for both AID-BiO and ITD-BiO that are applicable to all implementation choices of loops. We then specialize our results to characterize the computational complexity for all implementations, which enable an explicit comparison among them. Our result indicates that for AID-BiO, the loop for estimating the optimal point of the inner function is beneficial for overall efficiency, although it causes higher complexity for each update step, and the loop for approximating the outer-level Hessian-inverse-vector product reduces the gradient complexity. For ITD-BiO, the two loops always coexist, and our convergence upper and lower bounds show that such loops are necessary to guarantee a vanishing convergence error, whereas the no-loop scheme suffers from an unavoidable non-vanishing convergence error. Our numerical experiments further corroborate our theoretical results.

Bilevel optimization has arisen as a powerful tool in modern machine learning. However, due to the nested structure of bilevel optimization, even gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations, which can be costly and unscalable in practice. Recently, Hessian-free bilevel schemes have been proposed to resolve this issue, where the general idea is to use zeroth- or first-order methods to approximate the full hypergradient of the bilevel problem. However, we empirically observe that such approximation can lead to large variance and unstable training, but estimating only the response Jacobian matrix as a partial component of the hypergradient turns out to be extremely effective. To this end, we propose a new Hessian-free method, which adopts the zeroth-order-like method to approximate the response Jacobian matrix via taking difference between two optimization paths. Theoretically, we provide the convergence rate analysis for the proposed algorithms, where our key challenge is to characterize the approximation and smoothness properties of the trajectory-dependent estimator, which can be of independent interest. This is the first known convergence rate result for this type of Hessian-free bilevel algorithms. Experimentally, we demonstrate that the proposed algorithms outperform baseline bilevel optimizers on various bilevel problems. Particularly, in our experiment on few-shot meta-learning with ResNet-12 network over the miniImageNet dataset, we show that our algorithm outperforms baseline meta-learning algorithms, while other baseline bilevel optimizers do not solve such meta-learning problems within a comparable time frame.

General Value Function (GVF) is a powerful tool to represent both the {\em predictive} and {\em retrospective} knowledge in reinforcement learning (RL). In practice, often multiple interrelated GVFs need to be evaluated jointly with pre-collected off-policy samples. In the literature, the gradient temporal difference (GTD) learning method has been adopted to evaluate GVFs in the off-policy setting, but such an approach may suffer from a large estimation error even if the function approximation class is sufficiently expressive. Moreover, none of the previous work have formally established the convergence guarantee to the ground truth GVFs under the function approximation settings. In this paper, we address both issues through the lens of a class of GVFs with causal filtering, which cover a wide range of RL applications such as reward variance, value gradient, cost in anomaly detection, stationary distribution gradient, etc. We propose a new algorithm called GenTD for off-policy GVFs evaluation and show that GenTD learns multiple interrelated multi-dimensional GVFs as efficiently as a single canonical scalar value function. We further show that unlike GTD, the learned GVFs by GenTD are guaranteed to converge to the ground truth GVFs as long as the function approximation power is sufficiently large. To our best knowledge, GenTD is the first off-policy GVF evaluation algorithm that has global optimality guarantee.

Conventional machine learning applications typically assume that data samples are independently and identically distributed (i.i.d.). However, practical scenarios often involve a data-generating process that produces highly dependent data samples, which are known to heavily bias the stochastic optimization process and slow down the convergence of learning. In this paper, we conduct a fundamental study on how different stochastic data sampling schemes affect the sample complexity of online stochastic gradient descent (SGD) over highly dependent data. Specifically, with a $\phi$-mixing process of data, we show that online SGD with proper periodic data-subsampling achieves an improved sample complexity over the standard online SGD in the full spectrum of the data dependence level. Interestingly, even subsampling a subset of data samples can accelerate the convergence of online SGD over highly dependent data. Moreover, we show that online SGD with mini-batch sampling can further substantially improve the sample complexity over online SGD with periodic data-subsampling over highly dependent data. Numerical experiments validate our theoretical results.

The deterministic policy gradient (DPG) method proposed in Silver et al. [2014] has been demonstrated to exhibit superior performance particularly for applications with multi-dimensional and continuous action spaces. However, it remains unclear whether DPG converges, and if so, how fast it converges and whether it converges as efficiently as other PG methods. In this paper, we provide a theoretical analysis of DPG to answer those questions. We study the single timescale DPG (often the case in practice) in both on-policy and off-policy settings, and show that both algorithms attain an $\epsilon$-accurate stationary policy with a sample complexity of $\mathcal{O}(\epsilon^{-2})$. Moreover, we establish the convergence rate for DPG under Gaussian noise exploration, which is widely adopted in practice to improve the performance of DPG. To our best knowledge, this is the first non-asymptotic convergence characterization for DPG methods.

As a popular meta-learning approach, the model-agnostic meta-learning (MAML) algorithm has been widely used due to its simplicity and effectiveness. However, the convergence of the general multi-step MAML still remains unexplored. In this paper, we develop a new theoretical framework to provide such convergence guarantee for two types of objective functions that are of interest in practice: (a) resampling case (e.g., reinforcement learning), where loss functions take the form in expectation and new data are sampled as the algorithm runs; and (b) finite-sum case (e.g., supervised learning), where loss functions take the finite-sum form with given samples. For both cases, we characterize the convergence rate and the computational complexity to attain an $\epsilon$-accurate solution for multi-step MAML in the general nonconvex setting. In particular, our results suggest that an inner-stage stepsize needs to be chosen inversely proportional to the number $N$ of inner-stage steps in order for $N$-step MAML to have guaranteed convergence. From the technical perspective, we develop novel techniques to deal with the nested structure of the meta gradient for multi-step MAML, which can be of independent interest.

It has been shown that the SK scheme, which was proposed by Schalkwijk and Kailath, is a self-secure capacity-achieving (SSCA) feedback scheme for the Gaussian wiretap channel, i.e., the SK scheme not only achieves the feedback capacity of the Gaussian channel, but also is secure by itself and achieves the feedback secrecy capacity of the Gaussian wiretap channel. For the multi-user wiretap channels, very recently, it has been shown that Ozarow’s capacity-achieving feedback scheme for the two-user Gaussian multiple-access channel (GMAC) is the SSCA feedback scheme for the two-user Gaussian multiple-access wiretap channel (GMAC-WT). In this paper, first, we propose a SSCA feedback scheme for the two-user GMAC-WT with degraded message sets (GMAC-WT-DMS). Next, we extend the above scheme to the two-user GMAC-WT-DMS with noncausal channel state information at the transmitters (NCSIT), and show that the extended scheme is also a SSCA feedback scheme. Finally, we derive outer bounds on the secrecy capacity regions of the two-user GMAC-WT-DMS with or without NCSIT, and numerical results show the rate gains by the feedback.

Despite the wide applications of Adam in reinforcement learning (RL), the theoretical convergence of Adam-type RL algorithms has not been established. This paper provides the first such convergence analysis for two fundamental RL algorithms of policy gradient (PG) and temporal difference (TD) learning that incorporate AMSGrad updates (a standard alternative of Adam in theoretical analysis), referred to as PG-AMSGrad and TD-AMSGrad, respectively. Moreover, our analysis focuses on Markovian sampling for both algorithms. We show that under general nonlinear function approximation, PG-AMSGrad with a constant stepsize converges to a neighborhood of a stationary point at the rate of O(1/T) (where T denotes the number of iterations), and with a diminishing stepsize converges exactly to a stationary point at the rate of O(log^2 T/√T). Furthermore, under linear function approximation, TD-AMSGrad with a constant stepsize converges to a neighborhood of the global optimum at the rate of O(1/T), and with a diminishing stepsize converges exactly to the global optimum at the rate of O(log T/√T). Our study develops new techniques for analyzing the Adam-type RL algorithms under Markovian sampling.

Generative adversarial imitation learning (GAIL) is a popular inverse reinforcement learning approach for jointly optimizing policy and reward from expert trajectories. A primary question about GAIL is whether applying a certain policy gradient algorithm to GAIL attains a global minimizer (i.e., yields the expert policy), for which existing understanding is very limited. Such global convergence has been shown only for the linear (or linear-type) MDP and linear (or linearizable) reward. In this paper, we study GAIL under general MDP and for nonlinear reward function classes (as long as the objective function is strongly concave with respect to the reward parameter). We characterize the global convergence with a sublinear rate for a broad range of commonly used policy gradient algorithms, all of which are implemented in an alternating manner with stochastic gradient ascent for reward update, including projected policy gradient (PPG)-GAIL, Frank-Wolfe policy gradient (FWPG)-GAIL, trust region policy optimization (TRPO)-GAIL and natural policy gradient (NPG)-GAIL. This is the first systematic theoretical study of GAIL for global convergence.

Two timescale stochastic approximation (SA) has been widely used in value-based reinforcement learning algorithms. In the policy evaluation setting, it can model the linear and nonlinear temporal difference learning with gradient correction (TDC) algorithms as linear SA and nonlinear SA, respectively. In the policy optimization setting, two timescale nonlinear SA can also model the greedy gradient-Q (Greedy-GQ) algorithm. In previous studies, the non-asymptotic analysis of linear TDC and Greedy-GQ has been studied in the Markovian setting, with single-sample update at each iteration. For the nonlinear TDC algorithm, only the asymptotic convergence has been established. In this paper, we study the non-asymptotic convergence rate of two time-scale linear and nonlinear TDC and Greedy-GQ under Markovian sampling and with mini-batch data for each update. For linear TDC, we provide a novel non-asymptotic analysis and our sample complexity result achieves the complexity $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$. For nonlinear TDC and Greedy-GQ, we show that both algorithms attain $\epsilon$-accurate stationary solution with sample complexity $\mathcal{O}(\epsilon^{-2})$. It is the first time that non-asymptotic convergence result has been established for nonlinear TDC and our result for Greedy-GQ outperforms previous result orderwisely by a factor of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$.

Bilevel optimization has arisen as a powerful tool for many machine learning problems such as meta-learning, hyperparameter optimization, and reinforcement learning. In this paper, we investigate the nonconvex-strongly-convex bilevel optimization problem. For deterministic bilevel optimization, we provide a comprehensive convergence rate analysis for two popular algorithms respectively based on approximate implicit differentiation (AID) and iterative differentiation (ITD). For the AID-based method, we orderwisely improve the previous convergence rate analysis due to a more practical parameter selection as well as a warm start strategy, and for the ITD-based method we establish the first theoretical convergence rate. Our analysis also provides a quantitative comparison between ITD and AID based approaches. For stochastic bilevel optimization, we propose a novel algorithm named stocBiO, which features a sample-efficient hypergradient estimator using efficient Jacobian- and Hessian-vector product computations. We provide the convergence rate guarantee for stocBiO, and show that stocBiO outperforms the best known computational complexities orderwisely with respect to the condition number $\kappa$ and the target accuracy $\epsilon$. We further validate our theoretical results and demonstrate the efficiency of bilevel optimization algorithms by the experiments on meta-learning and hyperparameter optimization.

In safe reinforcement learning (SRL) problems, an agent explores the environment to maximize an expected total reward and meanwhile avoids violation of certain constraints on a number of expected total costs. In general, such SRL problems have nonconvex objective functions subject to multiple nonconvex constraints, and hence are very challenging to solve, particularly to provide a globally optimal policy. Many popular SRL algorithms adopt a primal-dual structure which utilizes the updating of dual variables for satisfying the constraints. In contrast, we propose a primal approach, called constraint-rectified policy optimization (CRPO), which updates the policy alternatingly between objective improvement and constraint satisfaction. CRPO provides a primal-type algorithmic framework to solve SRL problems, where each policy update can take any variant of policy optimization step. To demonstrate the theoretical performance of CRPO, we adopt natural policy gradient (NPG) for each policy update step and show that CRPO achieves an $\mathcal{O}(1/\sqrt{T})$ convergence rate to the global optimal policy in the constrained policy set and an $\mathcal{O}(1/\sqrt{T})$ error bound on constraint satisfaction. This is the first finite-time analysis of primal SRL algorithms with global optimality guarantee. Our empirical results demonstrate that CRPO can outperform the existing primal-dual baseline algorithms significantly.

Designing off-policy reinforcement learning algorithms is typically a very challenging task, because a desirable iteration update often involves an expectation over an on-policy distribution. Prior off-policy actor-critic (AC) algorithms have introduced a new critic that uses the density ratio for adjusting the distribution mismatch in order to stabilize the convergence, but at the cost of potentially introducing high biases due to the estimation errors of both the density ratio and value function. In this paper, we develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP, which can take advantage of learned nuisance functions to reduce estimation errors. Moreover, DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize, and is thus more sample efficient than prior algorithms that adopt either two timescale or nested-loop structure. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $\epsilon$-accurate optimal policy. We also show that the overall convergence of DR-Off-PAC is doubly robust to the approximation errors that depend only on the expressive power of approximation functions. To the best of our knowledge, our study establishes the first overall sample complexity analysis for single time-scale off-policy AC algorithm.

Bilevel optimization has been widely applied in many important machine learning applications such as hyperparameter optimization and meta-learning. Recently, several momentum-based algorithms have been proposed to solve bilevel optimization problems faster. However, those momentum-based algorithms do not achieve provably better computational complexity than $\mathcal{\widetilde O}(\epsilon^{-2})$ of the SGD-based algorithm. In this paper, we propose two new algorithms for bilevel optimization, where the first algorithm adopts momentum-based recursive iterations, and the second algorithm adopts recursive gradient estimations in nested loops to decrease the variance. We show that both algorithms achieve the complexity of $\mathcal{\widetilde O}(\epsilon^{-1.5})$, which outperforms all existing algorithms by the order of magnitude. Our experiments validate our theoretical results and demonstrate the superior empirical performance of our algorithms in hyperparameter applications.

Double Q-learning (Hasselt, 2010) has gained significant success in practice due to its effectiveness in overcoming the overestimation issue of Q-learning. However, the theoretical understanding of double Q-learning is rather limited. The only existing finite-time analysis was recently established in (Xiong et al. 2020), where the polynomial learning rate adopted in the analysis typically yields a slower convergence rate. This paper tackles the more challenging case of a constant learning rate, and develops new analytical tools that improve the existing convergence rate by orders of magnitude. Specifically, we show that synchronous double Q-learning attains an $\epsilon$-accurate global optimum with a time complexity of $\tilde{\Omega}\left(\frac{\ln D}{(1-\gamma)^7\epsilon^2} \right)$, and the asynchronous algorithm achieves a time complexity of $\tilde{\Omega}\left(\frac{L}{(1-\gamma)^7\epsilon^2} \right)$, where $D$ is the cardinality of the state-action space, $\gamma$ is the discount factor, and $L$ is a parameter related to the sampling strategy for asynchronous double Q-learning. These results improve the existing convergence rate by the order of magnitude in terms of its dependence on all major parameters $(\epsilon,1-\gamma, D, L)$. This paper presents a substantial step toward the full understanding of the fast convergence of double-Q learning.

Existing studies indicate that momentum ideas in conventional optimization can be used to improve the performance of Q-learning algorithms. However, the finite-time analysis for momentum-based Q-learning algorithms is only available for the tabular case without function approximation. This paper analyzes a class of momentum-based Q-learning algorithms with finite-time convergence guarantee. Specifically, we propose the MomentumQ algorithm, which integrates the Nesterov’s and Polyak’s momentum schemes, and generalizes the existing momentum-based Q-learning algorithms. For the infinite state-action space case, we establish the convergence guarantee for MomentumQ with linear function approximation under Markovian sampling. In particular, we characterize a finite-time convergence rate which is provably faster than the vanilla Q-learning. This is the first finite-time analysis for momentum-based Q-learning algorithms with function approximation. For the tabular case under synchronous sampling, we also obtain a finite-time convergence rate that is slightly better than the SpeedyQ (Azar et al., NIPS 2011). Finally, we demonstrate through various experiments that the proposed MomentumQ outperforms other momentum-based Q-learning algorithms.

This article investigates the estimation and generalization errors of the generative adversarial network (GAN) training. On the statistical side, we develop an upper bound as well as a minimax lower bound on the estimation error for training GANs. The upper bound incorporates the roles of both the discriminator and the generator of GANs, and matches the minimax lower bound in terms of the sample size and the norm of the parameter matrices of neural networks under ReLU activation. On the algorithmic side, we develop a generalization error bound for the stochastic gradient method (SGM) in training GANs. Such a bound justifies the generalization ability of the GAN training via SGM after multiple passes over the data and reflects the interplay between the discriminator and the generator. Our results imply that the training of the generator requires more samples than the training of the discriminator. This is consistent with the empirical observation that the training of the discriminator typically converges faster than that of the generator. The experiments validate our theoretical results.

The multi-armed bandit formalism has been extensively studied under various attack models, in which an adversary can modify the reward revealed to the player. Previous studies focused on scenarios where the attack value either is bounded at each round or has a vanishing probability of occurrence. These models do not capture powerful adversaries that can catastrophically perturb the revealed reward. This paper investigates the attack model where an adversary attacks with a certain probability at each round, and its attack value can be arbitrary and unbounded if it attacks. Furthermore, the attack value does not necessarily follow a statistical distribution. We propose a novel sample median-based and exploration-aided UCB algorithm (called med-E-UCB) and a median-based ϵ-greedy algorithm (called med-ϵ-greedy). Both of these algorithms are provably robust to the aforementioned attack model. More specifically we show that both algorithms achieve O(log T) pseudo-regret (i.e., the optimal regret without attacks). We also provide a high probability guarantee of O(log T) regret with respect to random rewards and random occurrence of attacks. These bounds are achieved under arbitrary and unbounded reward perturbation as long as the attack probability does not exceed a certain constant threshold. We provide multiple synthetic simulations of the proposed algorithms to verify these claims and showcase the inability of existing techniques to achieve sublinear regret. We also provide experimental results of the algorithm operating in a cognitive radio setting using multiple software-defined radios.

Rapid growth of radio traffic in the unlicensed spectrum has led to challenges in securing sufficient resources for reliable communications. This problem is compounded by the emergence of uncooperative and even adversarial users which can interfere with the network fidelity of existing secondary users. In this paper, we propose a DSA policy using a decentralized sample-median based exploration-aided UCB (DMA med-E-UCB) and a decentralized sample-median based epsilon greedy (DMA med-E-greedy). Both algorithms are applied in a distributed spectrum sharing cognitive radio network and able to defend against an adversarial attacker with arbitrarily large interference power. We model the proposed spectrum access problem as a multi-armed bandit and show that both algorithms are robust to adversarial attacks. Provided that the attack occurs infrequently, the regret achieved by both algorithms is O(logT) with high probability, where T is the number of sequential channel access attempts. We show that our algorithms outperform other standard distributed policies and verify our results using an over-the-air software-defined-radio testbed.

Variance-reduced algorithms, although achieve great theoretical performance, can run slowly in practice due to the periodic gradient estimation with a large batch of data. Batch-size adaptation thus arises as a promising approach to accelerate such algorithms. However, existing schemes either apply prescribed batch-size adaption rule or exploit the information along optimization path via additional backtracking and condition verification steps. In this paper, we propose a novel scheme, which eliminates backtracking line search but still exploits the information along optimization path by adapting the batch size via history stochastic gradients. We further theoretically show that such a scheme substantially reduces the overall complexity for popular variance-reduced algorithms SVRG and SARAH/SPIDER for both conventional nonconvex optimization and reinforcement learning problems. To this end, we develop a new convergence analysis framework to handle the dependence of the batch size on history stochastic gradients. Extensive experiments validate the effectiveness of the proposed batch-size adaptation scheme.

Existing convergence analyses of Q-learning mostly focus on the vanilla stochastic gradient descent (SGD) type of updates. Despite the Adaptive Moment Estimation (Adam) has been commonly used for practical Q-learning algorithms, there has not been any convergence guarantee provided for Q-learning with such type of updates. In this paper, we first characterize the convergence rate for Q-AMSGrad, which is the Q-learning algorithm with AMSGrad update (a commonly adopted alternative of Adam for theoretical analysis). To further improve the performance, we propose to incorporate the momentum restart scheme to Q-AMSGrad, resulting in the so-called Q-AMSGradR algorithm. The convergence rate of Q-AMSGradR is also established. Our experiments on a linear quadratic regulator problem demonstrate that the two proposed Q-learning algorithms outperform the vanilla Q-learning with SGD updates. The two algorithms also exhibit significantly better performance than the DQN learning method over a batch of Atari 2600 games.

Various types of parameter restart schemes have been proposed for proximal gradient algorithm with momentum to facilitate their convergence in convex optimization. However, under parameter restart, the convergence of proximal gradient algorithm with momentum remains obscure in nonconvex optimization. In this paper, we propose a novel proximal gradient algorithm with momentum and parameter restart for solving nonconvex and nonsmooth problems. Our algorithm is designed to 1) allow for adopting flexible parameter restart schemes that cover many existing ones; 2) have a global sub-linear convergence rate in nonconvex and nonsmooth optimization; and 3) have guaranteed convergence to a critical point and have various types of asymptotic convergence rates depending on the parameterization of local geometry in nonconvex and nonsmooth optimization. Numerical experiments demonstrate the convergence and effectiveness of our proposed algorithm.

The Schalkwijk-Kailath (SK) feedback scheme is a capacity-achieving coding scheme for the point-to-point white Gaussian channel with feedback. Recently, it has been shown that the SK scheme, which is not designed with consideration of secrecy, already achieves perfect weak secrecy by itself, i.e., the secrecy capacity of the Gaussian wiretap channel with feedback equals the capacity of the same model without secrecy constraint. In this paper, we propose a capacity-achieving SK type feedback scheme for the two-user Gaussian multiple-access channel with degraded message sets (GMAC-DMS). Similarly to the inherent secrecy nature of the classical SK scheme, we show that the proposed scheme is also secure by itself, which indicates that the feedback secrecy capacity of the two-user Gaussian multiple-access wiretap channel with degraded message sets (GMAC-WT-DMS) equals the capacity of the same model without secrecy constraint.

Although model-agnostic meta-learning (MAML) is a very successful algorithm in meta-learning practice, it can have high computational cost because it updates all model parameters over both the inner loop of task-specific adaptation and the outer-loop of meta initialization training. A more efficient algorithm ANIL (which refers to almost no inner loop) was proposed recently by Raghu et al. 2019, which adapts only a small subset of parameters in the inner loop and thus has substantially less computational cost than MAML as demonstrated by extensive experiments. However, the theoretical convergence of ANIL has not been studied yet. In this paper, we characterize the convergence rate and the computational complexity for ANIL under two representative inner-loop loss geometries, i.e., strongly-convexity and nonconvexity. Our results show that such a geometric property can significantly affect the overall convergence performance of ANIL. For example, ANIL achieves a faster convergence rate for a strongly-convex inner-loop loss as the number $N$ of inner-loop gradient descent steps increases, but a slower convergence rate for a nonconvex inner-loop loss as $N$ increases. Moreover, our complexity analysis provides a theoretical quantification on the improved efficiency of ANIL over MAML. The experiments on standard few-shot meta-learning benchmarks validate our theoretical findings.

Although Q-learning is one of the most successful algorithms for finding the best action-value function (and thus the optimal policy) in reinforcement learning, its implementation often suffers from large overestimation of Q-function values incurred by random sampling. The double Q-learning algorithm proposed in~\citet{hasselt2010double} overcomes such an overestimation issue by randomly switching the update between two Q-estimators, and has thus gained significant popularity in practice. However, the theoretical understanding of double Q-learning is rather limited. So far only the asymptotic convergence has been established, which does not characterize how fast the algorithm converges. In this paper, we provide the first non-asymptotic (i.e., finite-time) analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $\epsilon$-accurate neighborhood of the global optimum by taking $\tilde{\Omega}\left(\left( \frac{1}{(1-\gamma)^6\epsilon^2}\right)^{\frac{1}{\omega}} +\left(\frac{1}{1-\gamma}\right)^{\frac{1}{1-\omega}}\right)$ iterations, where $\omega\in(0,1)$ is the decay parameter of the learning rate, and $\gamma$ is the discount factor. Our analysis develops novel techniques to derive finite-time bounds on the difference between two inter-connected stochastic processes, which is new to the literature of stochastic approximation.

The actor-critic (AC) algorithm is a popular method to find an optimal policy in reinforcement learning. In the infinite horizon scenario, the finite-sample convergence rate for the AC and natural actor-critic (NAC) algorithms has been established recently, but under independent and identically distributed (i.i.d.) sampling and single-sample update at each iteration. In contrast, this paper characterizes the convergence rate and sample complexity of AC and NAC under Markovian sampling, with mini-batch data for each iteration, and with actor having general policy class approximation. We show that the overall sample complexity for a mini-batch AC to attain an $\epsilon$-accurate stationary point improves the best known sample complexity of AC by an order of $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$, and the overall sample complexity for a mini-batch NAC to attain an $\epsilon$-accurate globally optimal point improves the existing sample complexity of NAC by an order of $\mathcal{O}(\epsilon^{-2}/\log(1/\epsilon))$. Moreover, the sample complexity of AC and NAC characterized in this work outperforms that of policy gradient (PG) and natural policy gradient (NPG) by a factor of $\mathcal{O}((1-\gamma)^{-3})$ and $\mathcal{O}((1-\gamma)^{-4}\epsilon^{-2}/\log(1/\epsilon))$, respectively. This is the first theoretical study establishing that AC and NAC attain orderwise performance improvement over PG and NPG under infinite horizon due to the incorporation of critic.

Community detection in large social networks is affected by degree heterogeneity of nodes. The D-SCORE algorithm for directed networks was introduced to reduce this effect by taking the element-wise ratios of the singular vectors of the adjacency matrix before clustering. Meaningful results were obtained for the statistician citation network, but rigorous analysis on its performance was missing. First, this paper establishes theoretical guarantee for this algorithm and its variants for the directed degree-corrected block model (Directed-DCBM). Second, this paper provides significant improvements for the original D-SCORE algorithms by attaching the nodes outside of the community cores using the information of the original network instead of the singular vectors.

We investigate the state-dependent Gaussian wiretap channel with noncausal channel state information at the transmitter (GWTC-N-CSIT), and explore whether three strategies (i.e., taking action on the state, legitimate receiver's channel output feedback, and combining the former two strategies together) help to enhance the secrecy capacity of the GWTC-N-CSIT. To be specific, we first determine the secrecy capacity of the GWTC-N-CSIT with noiseless feedback. Next, we derive lower and upper bounds on the secrecy capacity of the GWTC-N-CSIT with action-dependent state. Finally, we derive lower and upper bounds on the secrecy capacity of the GWTC-N-CSIT with both action-dependent state and noiseless feedback, and show that these bounds meet for a special case. Numerical results of this paper indicate that all three strategies enhance the secrecy capacity of the GWTC-N-CSIT. The study of this paper offers new options for enhancing the secrecy rates of the state-dependent wiretap channel models.

Cubic regularization (CR) is an optimization method with emerging popularity due to its capability to escape saddle points and converge to second-order stationary solutions for nonconvex optimization. However, CR encounters a high sample complexity issue for finite-sum problems with a large data size. Various inexact variants of CR have been proposed to improve the sample complexity. In this paper, we propose a stochastic variance-reduced cubic-regularization (SVRC) method under random sampling, and study its convergence guarantee as well as sample complexity. We show that the iteration complexity of SVRC for achieving a second-order stationary solution within $\epsilon$ accuracy is $O(\epsilon^{-3/2})$, which matches the state-of-art result on CR types methods. Moreover, our proposed variance reduction scheme significantly reduces the per-iteration sample complexity. The resulting total Hessian sample complexity of our SVRC is $O(N^{2/3} \epsilon^{-3/2})$, which outperforms the state-of-art result by a factor of $O(N^{2/15})$. We also study our SVRC under random sampling without replacement scheme, which yields a lower per-iteration sample complexity, and hence justifies its practical applicability.

Two types of zeroth-order stochastic algorithms have recently been designed for nonconvex optimization respectively based on the first-order techniques SVRG and SARAH/SPIDER. This paper addresses several important issues that are still open in these methods. First, all existing SVRG-type zeroth-order algorithms suffer from worse function query complexities than either zeroth-order gradient descent (ZO-GD) or stochastic gradient descent (ZO-SGD). In this paper, we propose a new algorithm ZO-SVRG-Coord-Rand and develop a new analysis for an existing ZO-SVRG-Coord algorithm proposed in Liu et al. 2018b, and show that both ZO-SVRG-Coord-Rand and ZO-SVRG-Coord (under our new analysis) outperform other exiting SVRG-type zeroth-order methods as well as ZO-GD and ZO-SGD. Second, the existing SPIDER-type algorithm SPIDER-SZO (Fang et al., 2018) has superior theoretical performance, but suffers from the generation of a large number of Gaussian random variables as well as a $\sqrt{\epsilon}$-level stepsize in practice. In this paper, we develop a new algorithm ZO-SPIDER-Coord, which is free from Gaussian variable generation and allows a large constant stepsize while maintaining the same convergence rate and query complexity, and we further show that ZO-SPIDER-Coord automatically achieves a linear convergence rate as the iterate enters into a local PL region without restart and algorithmic modification.

The dirty paper wiretap channel, also referred to as the Gaussian wiretap channel with noncausal state at the transmitter, is revisited. First, we determine the secrecy capacity of the dirty paper wiretap channel with noiseless feedback, where the feedback channel is from the legitimate receiver to the transmitter. Next, we obtain lower and upper bounds on the secrecy capacity of the action-dependent dirty paper wiretap channel with noiseless feedback, and show that these bounds meet for a special case. Unlike the fact that action on the state helps to enhance the capacity of the dirty paper channel with feedback, numerical results of this paper indicate that it may not help to enhance the secrecy capacity of the dirty paper wiretap channel with feedback.

We study model recovery for data classification, where the training labels are generated from a one-hidden-layer neural network with sigmoid activations, and the goal is to recover the weights of the neural network. We consider two network models, the fully-connected network (FCN) and the non-overlapping convolutional neural network (CNN). We prove that with Gaussian inputs, the empirical risk based on cross entropy exhibits strong convexity and smoothness uniformly in a local neighborhood of the ground truth, as soon as the sample complexity is sufficiently large. Hence, if initialized in this neighborhood, it establishes the local convergence guarantee for empirical risk minimization using cross entropy via gradient descent for learning one-hidden-layer neural networks, at the near-optimal sample and computational complexity with respect to the network input dimension without unrealistic assumptions such as requiring a fresh set of samples at each iteration.

SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objective functions that involve nonsmooth regularizers. In this paper, we propose SpiderBoost as an improved scheme, which allows to use a much larger constant-level stepsize while maintaining the same near-optimal oracle complexity, and can be extended with proximal mapping to handle composite optimization (which is nonsmooth and nonconvex) with provable convergence guarantee. In particular, we show that proximal SpiderBoost achieves an oracle complexity of O(min{n^{1/2}\epsilon^{-2},\epsilon^{-3}}) in composite nonconvex optimization, improving the state-of-the-art result by a factor of O(min{n^{1/6},\epsilon^{-1/3}}). We further develop a novel momentum scheme to accelerate SpiderBoost for composite optimization, which achieves the near-optimal oracle complexity in theory and substantial improvement in experiments.

Gradient-based temporal difference (GTD) algorithms are widely used in off-policy learning scenarios. Among them, the two time-scale TD with gradient correction (TDC) algorithm has been shown to have superior performance. In contrast to previous studies that characterized the non-asymptotic convergence rate of TDC only under identical and independently distributed (i.i.d.) data samples, we provide the first non-asymptotic convergence analysis for two time-scale TDC under a non-i.i.d.\ Markovian sample path and linear function approximation. We show that the two time-scale TDC can converge as fast as O(log t/t^(2/3)) under diminishing stepsize, and can converge exponentially fast under constant stepsize, but at the cost of a non-vanishing error. We further propose a TDC algorithm with blockwisely diminishing stepsize, and show that it asymptotically converges with an arbitrarily small error at a blockwisely linear convergence rate. Our experiments demonstrate that such an algorithm converges as fast as TDC under constant stepsize, and still enjoys comparable accuracy as TDC under diminishing stepsize.

SARSA is an on-policy algorithm to learn a Markov decision process policy in reinforcement learning. We investigate the SARSA algorithm with linear function approximation under the non-i.i.d.\ setting, where a single sample trajectory is available. With a Lipschitz continuous policy improvement operator that is smooth enough, SARSA has been shown to converge asymptotically. However, its non-asymptotic analysis is challenging and remains unsolved due to the non-i.i.d. samples, and the fact that the behavior policy changes dynamically with time. In this paper, we develop a novel technique to explicitly characterize the stochastic bias of a type of stochastic approximation procedures with time-varying Markov transition kernels. Our approach enables non-asymptotic convergence analyses of this type of stochastic approximation algorithms, which may be of independent interest. Using our bias characterization technique and a gradient descent type of analysis, we further provide the finite-sample analysis on the mean square error of the SARSA algorithm. In the end, we present a fitted SARSA algorithm, which includes the original SARSA algorithm and its variant as special cases. This fitted SARSA algorithm provides a framework for \textit{iterative} on-policy fitted policy iteration, which is more memory and computationally efficient. For this fitted SARSA algorithm, we also present its finite-sample analysis.

In this paper, the finite-order autoregressive moving average (ARMA) Gaussian wiretap channel with noiseless causal feedback is considered, in which an eavesdropper receives noisy observations of signals in both forward and feedback channels. It is shown that the generalized Schalkwijk-Kailath scheme, a capacity-achieving coding scheme for the Gaussian feedback channel, achieves the same maximum rate for the same channel even with the presence of an eavesdropper. Therefore, the secrecy capacity is equal to the feedback capacity without the presence of an eavesdropper for the Gaussian feedback channel. Furthermore, the results are extended to the additive white Gaussian noise (AWGN) channel with quantized feedback. It is shown that the proposed coding scheme achieves a positive secrecy rate. Our result implies that as the amplitude of the quantization noise decreases to zero, the secrecy rate converges to the capacity of the AWGN channel.

This paper investigates the Gaussian state-dependent interference channel (IC) and Z-IC, in which two receivers are corrupted respectively by two different but correlated states that are noncausally known to two transmitters but are unknown to the receivers. Three interference regimes are studied, and the capacity region boundary or the sum capacity boundary is characterized either fully or partially under various channel parameters. In particular, the impact of the correlation between states on cancellation of state and interference as well as achievability of capacity is explored with numerical illustrations. For the very strong interference regime, the capacity region is achieved by the scheme where the two transmitters implement a cooperative dirty paper coding. For the strong but not very strong interference regime, the sum-rate capacity is characterized by rate splitting, layered dirty paper coding, and successive cancellation. For the weak interference regime, the sum-rate capacity is achieved via dirty paper coding individually at two receivers as well as treating interference as noise. This paper also provides the achievable region for the state-dependent IC with each state known at its corresponding transmitter.

We investigate a nonparametric hypothesis testing problem, in which we assume a testing data stream is generated by one of a set of distributions (hypotheses), and the goal is to test which one of the multiple distributions generates the testing data stream, i.e., which hypothesis occurs. We assume that some distributions in the set are unknown with only training sequences generated by the corresponding distributions are given. We construct the generalized likelihood (GL) test, and characterize the error exponent of the maximum error probability. We show that the error exponent is captured by the Chernoff distance between each pair of distributions as well as the KL divergence between the approximated distributions (via training sequences) and the true distributions. We also show that the ratio between the lengths of training and testing sequences plays an important role in determining the error decay behavior.

This paper studies clustering using a Kolmogorov-Smirnov based K-means algorithm. All data sequences are assumed to be generated by unknown continuous distributions. The pairwise KS distances of the distributions are assumed to be lower bounded by a certain positive constant. The convergence analysis of the proposed algorithms and upper bounds on the error probability are provided for both known and unknown number of clusters. More importantly, it is shown that the probability of error decays exponentially as the sample size of each data sequence goes to infinity, and the error exponent is only a function of the pairwise KS distances of the distributions. the analysis is validated by simulation results.

In this paper, the finite-order autoregressive moving average (ARMA) Gaussian wiretap channel with noiseless causal feedback is considered, in which an eavesdropper receives noisy observations of the signals in both forward and feedback channels. It is shown that the generalized Schalkwijk-Kailath scheme, a capacity-achieving coding scheme for the feedback Gaussian channel, achieves the same maximum rate for the same channel with the presence of an eavesdropper. Therefore, the secrecy capacity is equal to the feedback capacity without the presence of an eavesdropper for the feedback channel. Furthermore, the results are extended to the additive white Gaussian noise (AWGN) channel with quantized feedback. It is shown that the proposed coding scheme achieves a positive secrecy rate. As the amplitude of the quantization noise decreases to zero, the secrecy rate converges to the capacity of the AWGN channel.

An important class of distance metrics proposed for training generative adversarial networks (GANs) is the integral probability metric (IPM), in which the neural net distance captures the practical GAN training via two neural networks. This paper investigates the minimax estimation problem of the neural net distance based on samples drawn from the distributions. We develop the first known minimax lower bound on the estimation error of the neural net distance, and an upper bound tighter than an existing bound on the estimator error for the empirical neural net distance. Our lower and upper bounds match not only in the order of the sample size but also in terms of the norm of the parameter matrices of neural networks, which justifies the empirical neural net distance as a good approximation of the true neural net distance for training GANs in practice.

Cubic-regularized Newton's method (CR) is a popular algorithm that guarantees to produce a second-order stationary solution for solving nonconvex optimization problems. However, existing understandings of convergence rate of CR are conditioned on special types of geometrical properties of the objective function. In this paper, we explore the asymptotic convergence rate of CR by exploiting the ubiquitous Kurdyka-Lojasiewicz (KL) property of the nonconvex objective functions. In specific, we characterize the asymptotic convergence rate of various types of optimality measures for CR including function value gap, variable distance gap, gradient norm and least eigenvalue of the Hessian matrix. Our results fully characterize the diverse convergence behaviors of these optimality measures in the full parameter regime of the KL property. Moreover, we show that the obtained asymptotic convergence rates of CR are order-wise faster than those of first-order gradient descent algorithms under the KL property.

With ever growing data volume and model size, an error-tolerant, communication efficient, yet versatile distributed algorithm has become vital for the success of many large-scale machine learning applications. In this work we propose m-PAPG, an implementation of the flexible proximal gradient algorithm in model parallel systems equipped with the partially asynchronous communication protocol. The worker machines communicate asynchronously with a controlled staleness bound $s$ and operate at different frequencies. We characterize various convergence properties of m-PAPG: 1) Under a general non-smooth and non-convex setting, we prove that every limit point of the sequence generated by m-PAPG is a critical point of the objective function; 2) Under an error bound condition of convex objective functions, we prove that the optimality gap decays linearly for every $s$ steps; 3) Under the Kurdyka-Łojasiewicz inequality and a sufficient decrease assumption, we prove that the sequences generated by m-PAPG converge to the same critical point, provided that a proximal Lipschitz condition is satisfied.

The problem of estimating the Kullback-Leibler divergence D(P∥Q) between two unknown distributions P and Q is studied, under the assumption that the alphabet size k of the distributions can scale to infinity. The estimation is based on m independent samples drawn from P and n independent samples drawn from Q. It is first shown that there does not exist any consistent estimator that guarantees asymptotically small worst case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions, with density ratio bounded by a function f (k) is further considered. An augmented plug-in estimator is proposed, and its worst case quadratic risk is shown to be within a constant factor of ((k/m) + (kf (k)/n))2+ (log2f (k)/m) + ( f (k)/n), if m and n exceed a constant factor of k and kf (k), respectively. Moreover, the minimax quadratic risk is characterized to be within a constant factor of ((k/(m log k)) + (kf (k)/(n log k)))2+ (log2f (k)/m) + ( f (k)/n), if m and n exceed a constant factor of k/ log(k) and kf (k)/ log k, respectively. The lower bound on the minimax quadratic risk is characterized by employing a generalized Le Cam's method. A minimax optimal estimator is then constructed by employing both the polynomial approximation and the plug-in approaches.

This paper studies a two-user state-dependent Gaussian multiple-access channel (MAC) with state noncausally known at one encoder. Two scenarios are considered: 1) each user wishes to communicate an independent message to the common receiver; and 2) the two encoders send a common message to the receiver and the non-cognitive encoder (i.e., the encoder that does not know the state) sends an independent individual message (this model is also known as the MAC with degraded message sets). For both scenarios, new outer bounds on the capacity region are derived, which improve uniformly over the best known outer bounds. In the first scenario, the two corner points of the capacity region as well as the sum rate capacity are established, and it is shown that a single-letter solution is adequate to achieve both the corner points and the sum rate capacity. Furthermore, the full capacity region is characterized in situations in which the sum rate capacity is equal to the capacity of the helper problem. The proof exploits the optimal-transportation idea of Polyanskiy and Wu (which was used previously to establish an outer bound on the capacity region of the interference channel) and the worst case Gaussian noise result for the case in which the input and the noise are dependent.

This paper investigates the phase retrieval problem, which aims to recover a signal from the magnitudes of its linear measurements. We develop statistically and computationally efficient algorithms for the situation when the measurements are corrupted by sparse outliers that can take arbitrary values. We propose a novel approach to robustify the gradient descent algorithm by using the sample median as a guide for pruning spurious samples in initialization and local search. Adopting a Poisson loss and a reshaped quadratic loss, respectively, we obtain two algorithms termedmedian-truncated Wirtinger flowandmedian-reshaped Wirtinger flow, both of which provably recover the signal from a near-optimal number of measurements when the measurement vectors are composed of independent and identically distributed Gaussian entries, up to a logarithmic factor, even when a constant fraction of the measurements is adversarially corrupted. We further show that both algorithms are stable in the presence of additional dense bounded noise. Our analysis is accomplished by developing non-trivial concentration results of median-related quantities, which may be of independent interest. We provide numerical experiments to demonstrate the effectiveness of our approach.

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.

We consider demixing a pair of sparse signals in orthonormal basis via convex optimization. Theoretically, we characterize the condition under which the solution of the convex optimization problem correctly demixes the true signal components. In specific, we introduce the local subspace coherence to characterize how a basis vector is coherent with a signal subspace, and show that the convex optimization approach succeeds if the subspaces of the true signal components avoid high local subspace coherence. Furthermore, we illustrate via examples that our condition for exact demixing is more fundamental than existing conditions. We then verify our theoretical finding through numerical experiments.

In this work, we investigate the accelerated proximal gradient method for nonconvex programming (APGnc). The method compares between a usual proximal gradient step and a linear extrapolation step, and accepts the one that has a lower function value to achieve a monotonic decrease. In specific, under a general nonsmooth and nonconvex setting, we provide a rigorous argument to show that the limit points of the sequence generated by APGnc are critical points of the objective function. Then, by exploiting the Kurdyka-Lojasiewicz (KL) property for a broad class of functions, we establish the linear and sub-linear convergence rates of the function value sequence generated by APGnc. We further propose a stochastic variance reduced APGnc (SVRG-APGnc), and establish its linear convergence under a special case of the KL property. We also extend the analysis to the inexact version of these methods and develop an adaptive momentum strategy that improves the numerical performance.

This paper studies a two-user state-dependent Gaussian multiple-access channel with state noncausally known at one encoder. Two new outer bounds on the capacity region are derived, which improve uniformly over the best known (genie-aided) outer bound. The two corner points of the capacity region as well as the sum rate capacity are established, and it is shown that a single-letter solution is adequate to achieve both the corner points and the sum rate capacity. Furthermore, the full capacity region is characterized in situations in which the sum rate capacity is equal to the capacity of the helper problem. The proof exploits the optimal-transportation idea of Polyanskiy and Wu (which was used previously to establish an outer bound on the capacity region of the interference channel) and the worst-case Gaussian noise result for the case in which the input and the noise are dependent.

In this paper, we consider the first-order autoregressive moving average Gaussian channel with perfect causal feedback where an eavesdropper receives noisy observations of the channel inputs and outputs. We show that the secrecy capacity is equal to the feedback capacity without the presence of eavesdropper. Furthermore, we explicitly construct the secrecy capacity-achieving feedback code, which is deterministic and simple to implement.

This paper investigates the Gaussian state-dependent Z-interference channel (Z-IC), in which two receivers are corrupted respectively by two correlated states that are noncausally known to transmitters and unknown to receivers. Three interference regimes are studied, and the capacity region or sum capacity boundary is characterized either fully or partially under various channel parameters. The impact of correlation between the states on state and interference cancellation as well as the achievability of the capacity is demonstrated via numerical analysis.

We study the problem of solving a quadratic system of equations, i.e., recovering a vector signal $\boldsymbol{x}\in \mathbb{R}^n$ from its magnitude measurements $y_i=|\langle \boldsymbol{a}_i, \boldsymbol{x}\rangle|, i=1,..., m$. We develop a gradient descent algorithm (referred to as RWF for reshaped Wirtinger flow) by minimizing the quadratic loss of the magnitude measurements. Comparing with Wirtinger flow (WF) (Candes et al., 2015), the loss function of RWF is nonconvex and nonsmooth, but better resembles the least-squares loss when the phase information is also available. We show that for random Gaussian measurements, RWF enjoys linear convergence to the true signal as long as the number of measurements is $\mathcal{O}(n)$. This improves the sample complexity of WF ($\mathcal{O}(n\log n)$), and achieves the same sample complexity as truncated Wirtinger flow (TWF) (Chen and Candes, 2015), but without any sophisticated truncation in the gradient loop. Furthermore, RWF costs less computationally than WF, and runs faster numerically than both WF and TWF. We further develop an incremental (stochastic) version of RWF (IRWF) and connect it with the randomized Kaczmarz method for phase retrieval. We demonstrate that IRWF outperforms existing incremental as well as batch algorithms with experiments.

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

With ever growing data volume and model size, an error-tolerant, communication efficient, yet versatile parallel algorithm has become a vital part for the success of many large-scale applications. In this work we propose mspg, an extension of the flexible proximal gradient algorithm to the model parallel and stale synchronous setting. The worker machines of mspg operate asynchronously as long as they are not too far apart, and they communicate efficiently through a dedicated parameter server. Theoretically, we provide a rigorous analysis of the various convergence properties of mspg, and a salient feature of our analysis is its seamless generality that allows both nonsmooth and nonconvex functions. Under mild conditions, we prove the whole iterate sequence of mspg converges to a critical point (which is optimal under convexity assumptions). We further provide an economical implementation of mspg, completely bypassing the need of keeping a local full model. We confirm our theoretical findings through numerical experiments.

The following detection problem is studied, in which there are M sequences of samples out of which one outlier sequence needs to be detected. Each typical sequence contains n independent and identically distributed (i.i.d.) continuous observations from a known distribution π, and the outlier sequence contains n i.i.d. observations from an outlier distribution μ, which is distinct from n, but otherwise unknown. A universal test based on Kullback-Leibler (KL) divergence is built to approximate the maximum likelihood test, with known π and unknown μ. A KL divergence estimator based on data-dependent partitions is employed, and is shown to converge to its true value exponentially fast when the density ratio satisfies 0 <; Kl ≤ dμ/dπ ≤ K2, where K1 and K2 are positive constants. The performance of such a KL divergence estimator further implies that the outlier detection test is exponentially consistent. The detection performance of the KL divergence based test is compared with that of a recently introduced test for this problem based on the machine learning approach of maximum mean discrepancy (MMD). Regimes in which the KL divergence based test is better than the MMD based test are identified.

Nonparametric detection of existence of an anomalous disk over a lattice network is investigated. If an anomalous disk exists, then all nodes belonging to the disk observe samples generated by a distribution q, whereas all other nodes observe samples generated by a distribution p that is distinct from q. If there does not exist an anomalous disk, then all nodes receive samples generated by p. The distributions p and q are arbitrary and unknown. The goal is to design statistically consistent test as the network size becomes asymptotically large. A kernel-based test is proposed based on maximum mean discrepancy (MMD) which measures the distance between mean embeddings of distributions into a reproducing kernel Hilbert space (RKHS). A sufficient condition on the minimum size of candidate anomalous disks is characterized in order to guarantee the consistency of the proposed test. A necessary condition that any universally consistent test must satisfy is further derived. Comparison of sufficient and necessary conditions yields that the proposed test is order-level optimal.

Solving systems of quadratic equations is a central problem in machine learning and signal processing. One important example is phase retrieval, which aims to recover a signal from only magnitudes of its linear measurements. This paper focuses on the situation when the measurements are corrupted by arbitrary outliers, for which the recently developed non-convex gradient descent Wirtinger flow (WF) and truncated Wirtinger flow (TWF) algorithms likely fail. We develop a novel median-TWF algorithm that exploits robustness of sample median to resist arbitrary outliers in the initialization and the gradient update in each iteration. We show that such a non-convex algorithm provably recovers the signal from a near-optimal number of measurements composed of i.i.d. Gaussian entries, up to a logarithmic factor, even when a constant portion of the measurements are corrupted by arbitrary outliers. We further show that median-TWF is also robust when measurements are corrupted by both arbitrary outliers and bounded noise. Our analysis of performance guarantee is accomplished by development of non-trivial concentration measures of median-related quantities, which may be of independent interest. We further provide numerical experiments to demonstrate the effectiveness of the approach.

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.

The problem of estimating the KL divergence between two unknown distributions is studied. The alphabet size k of the distributions can scale to infinity. The estimation is based on m and n independent samples respectively drawn from the two distributions. It is first shown that there does not exist any consistent estimator to guarantee asymptotic small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions with bounded ratio f(k) is further considered. An augmented plug-in estimator is proposed, and is shown to be consistent if and only if m = ω(k ⋁ log2(f(k)) and n = ω(k f(k)). Furthermore, if f(k) ≥ log2k and log2(f(k)) = o(k), it is shown that any consistent estimator must satisfy the necessary conditions: m = ω( k/log k ⋁ log2(f(k)) and n = ω( k f(k)/log k).

This paper investigates the two-user state-dependent Gaussian multiple access channel (MAC) with a helper. The channel is corrupted by an additive Gaussian state sequence known to neither the transmitters nor the receiver, but to a helper noncausally, which assists state cancellation at the receiver. Inner and outer bounds on the capacity region are first derived, which improve the previous bounds given by Duan et al. Further comparison of these bounds yields either segments on the capacity region boundary or the full capacity region by considering various cases of channel parameters.

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.

We study the problem of recovering a vector $\bx\in \bbR^n$ from its magnitude measurements $y_i=|\langle \ba_i, \bx\rangle|, i=1,..., m$. Our work is along the line of the Wirtinger flow (WF) approach \citet{candes2015phase}, which solves the problem by minimizing a nonconvex loss function via a gradient algorithm and can be shown to converge to a global optimal point under good initialization. In contrast to the smooth loss function used in WF, we adopt a nonsmooth but lower-order loss function, and design a gradient-like algorithm (referred to as reshaped-WF). We show that for random Gaussian measurements, reshaped-WF enjoys geometric convergence to a global optimal point as long as the number $m$ of measurements is at the order of $\cO(n)$, where $n$ is the dimension of the unknown $\bx$. This improves the sample complexity of WF, and achieves the same sample complexity as truncated-WF \citet{chen2015solving} but without truncation at gradient step. Furthermore, reshaped-WF costs less computationally than WF, and runs faster numerically than both WF and truncated-WF. Bypassing higher-order variables in the loss function and truncations in the gradient loop, analysis of reshaped-WF is simplified.

The state-dependent Gaussian interference channel (IC) and Z-IC are investigated, in which two receivers are corrupted by the same but differently scaled states. The state sequence is noncausally known at both transmitters, but not known at either receiver. Three interference regimes are studied, i.e., the very strong, strong, and weak regimes. In the very strong regime, the capacity region is characterized under certain channel parameters by designing a cooperative dirty paper coding between the two transmitters to fully cancel the state. In the strong regime, points on the capacity region boundary are characterized under certain channel parameters by designing an achievable scheme based on rate splitting, layered dirty paper coding, and successive state cancellation. In the weak regime, the sum capacity is obtained by independent dirty paper coding at two transmitters. For all the above regimes, the capacity achieves that of the IC/Z-IC without state. Comparison between the state-dependent regular IC and the Z-IC suggests that even with one interference-free link, the Z-IC does not necessarily perform better, because dirty paper coded interference in the regular IC facilitates to cancel the state through the cooperative dirty paper coding between the transmitters.

The state-dependent point-to-point Gaussian channel with a helper is first studied, in which a transmitter communicates with a receiver via a state-corrupted channel. The state is not known to the transmitter nor to the receiver, but known to a helper noncausally, which then wishes to assist the receiver to cancel the state. Differently from the previous work that characterized the capacity only in the infinite state power regime, this paper explores the general case with arbitrary state power. A lower bound on the capacity is derived based on an achievable scheme that integrates direct state subtraction and single-bin dirty paper coding. By analyzing this lower bound and further comparing it with the existing upper bounds, the capacity of the channel is characterized for a wide range of channel parameters. Such an idea of characterizing the capacity is further extended to study the two-user state-dependent multiple access channel with a helper. By comparing the derived inner and outer bounds, the channel parameters are partitioned into appropriate cases, and for each case, either segments on the capacity region boundary or the full capacity region are characterized.

A type of state-dependent Gaussian Z-interference channels is studied, in which transmitters 1 and 2 wish to send two messages to receivers 1 and 2, and only receiver 1 is interfered by transmitter 2's signal. Both receivers are corrupted by the same but differently scaled state sequence. The state information is assumed to be known noncausally at both transmitters. The channel is partitioned into very strong, strong, and weak interference regimes based on the strength of the interference. Respectively for the very strong and strong regimes, the capacity region and points on the capacity region boundary are characterized under certain channel parameters by designing joint dirty paper coding between two transmitters to cancel the state at both receivers. For the weak interference regime, the sum capacity is characterized by independent dirty paper coding at two transmitters. Comparison between the state-dependent regular and Z-interference channels indicates that although with one interference-free link, Z-interference channel does not necessarily perform better, because the dirty paper coded interference can be useful to help to fully cancel the state via joint dirty paper coding between the transmitters.

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.

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.

We investigate the robust PCA problem of decomposing an observed matrix into the sum of a low-rank and a sparse error matrices via convex programming Principal Component Pursuit (PCP). In contrast to previous studies that assume the support of the error matrix is generated by uniform Bernoulli sampling, we allow non-uniform sampling, i.e., entries of the low-rank matrix are corrupted by errors with unequal probabilities. We characterize conditions on error corruption of each individual entry based on the local incoherence of the low-rank matrix, under which correct matrix decomposition by PCP is guaranteed. Such a refined analysis of robust PCA captures how robust each entry of the low rank matrix combats error corruption. In order to deal with non-uniform error corruption, our technical proof introduces a new weighted norm and develops/exploits the concentration properties that such a norm satisfies.

The articles in this special issue highlight recent advances along with the remaining challenges in the field of physical-layer communications security.

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.

A class of cognitive interference channel with state is investigated, in which two transmitters (transmitters 1 and 2) communicate with two receivers (receivers 1 and 2) over an interference channel.The two transmitters jointly transmit a common message to the two receivers, and transmitter 2 also sends a separate message to receiver 2. The channel is corrupted by an independent and identically distributed (i.i.d.) state sequence.The scenario in which the state sequence is noncausally known only at transmitter 2 is first studied.For the discrete memoryless channel and its degraded version, inner and outer bounds on the capacity region are obtained.The capacity region is characterized for the degraded semideterministic channel and channels that satisfy a less noisy condition.The Gaussian channels are further studied, which are partitioned into two cases based on how the interference compares with the signal at receiver 1.For each case, inner and outer bounds on the capacity region are derived, and partial boundary of the capacity region is characterized.The full capacity region is characterized for channels that satisfy certain conditions.The second scenario in which the state sequence is noncausally known at both transmitter 2 and receiver 2 is further studied.The capacity region is obtained for both the discrete memoryless and Gaussian channels.It is also shown that this capacity is achieved by certain Gaussian channels with state noncausally known only at transmitter 2.

State-dependent parallel networks with a common state-cognitive helper is studied, in which K transmitters wish to send K messages to their corresponding receivers over K state-corrupted parallel channels, and a helper who knows the state information noncausally wishes to assist these receivers to cancel state interference. Furthermore, the helper also has its own message to be sent simultaneously to its corresponding receiver. Since the state information is known only to the helper, but not to other transmitters, transmitter-side state cognition and receiver-side state interference are mismatched. Our focus is on the high state power regime, i.e., the state power goes to infinity. Three (sub)models are studied. Model I serves as a basic model, which consists of only one transmitter-receiver (with state corruption) pair in addition to a helper that assists the receiver to cancel state in addition to transmitting its own message. Model II consists of two transmitter-receiver pairs in addition to a helper, and only one receiver is interfered by a state sequence. Model III generalizes model I to include multiple transmitter- receiver pairs with each receiver corrupted by independent state. For all models, the inner and outer bounds on the capacity region are derived, and comparison of the two bounds yields characterization of either full or partial boundary of the capacity region under various channel parameters.

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.

The multi-design multi-response linear regression problem is investigated, in which design matrices are Gaussian with covariance matrices Σ(1:K)= (Σ(1), ... , 1(K)) for K linear regression tasks. Design matrices across tasks are assumed to be independent. The support union of K p-dimensional regression vectors (collected as columns of matrix B*) is recovered using l1/l2-regularized lasso. Sufficient and necessary conditions on sample complexity are characterized as a sharp threshold to guarantee successful recovery of the support union. This model has been previously studied via l1/l∞-regularized lassoand via l1/l1+ l1/l∞-regularized lasso, in which sharp threshold on sample complexity is characterized only for K = 2 and under special conditions. In this paper, using l1/l2-regularized lasso, sharp threshold on sample complexity is characterized under standard regularization conditions. Namely, if n > cp1ψ(B*, Σ(1:K)) log(p - s) where cp1is a constant, and s is the size of the support set, then l1/l2-regularized lasso correctly recovers the support union; and if np2ψ(B*, Σ(1:K))log(p - s) where cp2is a constant, then l1/l2-regularized lasso fails to recover the support union. In particular, the function ψ(B*, Σ(1:K)) captures the impact of the sparsity of K regression vectors and the statistical properties of the design matrices on the threshold on sample complexity. Therefore, such threshold function also demonstrates the advantages of joint support union recovery using multitask lasso over individual support recovery using single-task lasso.

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.

The state-dependent parallel Gaussian channel with a common helper is investigated, in which transmitters 1 and 2 transmit two messages respectively to receivers 1 and 2 over the parallel channel. Furthermore, both parallel subchannels can be corrupted by independent state sequences, respectively, which are unknown to both transmitters and receivers. There is a common helper that knows the states noncausally and assists communication between transmitters and receivers. Our focus is on the high state power regime, i.e., the state power goes to infinity. Two Gaussian models are studied with model I having only receiver 1 interfered by the state and with model II having both receivers interfered by independent states. Each model has its unique challenge to address. For both models, inner and outer bounds on the capacity region are derived, and comparison of the two bounds leads to capacity results under certain channel parameters.

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.

The state-dependent broadcast channel with a helper is investigated, in which a transmitter wishes to send messages to two receivers via a broadcast channel. The channel is corrupted by an independent and identically distributed (i.i.d.) state sequence which is known to neither the transmitter nor the receivers. A helper that knows the state sequence noncausally assists the broadcast transmission to cancel state interference. Two scenarios are studied. In scenario 1, the transmitter sends one message to both receivers, and in scenario II, the transmitter sends two private messages respectively to two receivers. Our focus is on the Gaussian channel with additive state. Inner and outer bounds are derived for both scenarios. By comparing the inner and outer bounds, capacity/capacity region are characterized under various ranges of channel parameters. Practical impact of the model and results are discussed.

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.

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.

The multivariate multi-response (MVMR) linear regression problem is investigated, in which design matrices can be distributed differently across K linear regressions. The support union of K p-dimensional regression vectors are recovered via block regularized Lasso which uses the l_1/l_2 norm for regression vectors across K tasks. Sufficient and necessary conditions to guarantee successful recovery of the support union are characterized. More specifically, it is shown that under certain conditions on the distributions of design matrices, if n > c_p1 ψ(B^*,Σ^(1:K))\log(p-s) where c_p1 is a constant and s is the size of the support set, then the l_1/l_2 regularized Lasso correctly recovers the support union; and if n < c_p2 ψ(B^*,Σ^(1:K))\log(p-s) where c_p2 is a constant, then the l_1/l_2 regularized Lasso fails to recover the support union. In particular, ψ(B^*,Σ^(1:K)) captures the sparsity of K regression vectors and the statistical properties of the design matrices. Numerical results are provided to demonstrate the advantages of joint support union recovery using multi-task Lasso problem over studying each problem individually.

The Gaussian interference channel with additive state at two receivers is investigated, in which the state information is noncausally known at both transmitters but not known at either receiver. For the very strong Gaussian interference channel with state, the capacity region is obtained under certain conditions on channel parameters. For the strong (but not very strong) Gaussian interference channel with state, points on the boundary of the capacity region are characterized under corresponding conditions on channel parameters. Finally, for the weak Gaussian interference channel with state, the sum capacity is obtained for certain channel parameters. All the above capacity-achieving rate points achieve the capacity for the corresponding channel without state.

Two-user fading multiple access channel (MAC) is investigated, which is corrupted by random fading coefficients and additive Gaussian noise. It is assumed that the channel is block fading, and each transmitter knows only its own channel state to the receiver, but does not know the other transmitter's channel state. The receiver has full knowledge of channel state information (CSI). The performance measure, the expected capacity region over channel statistics, is studied for two scenarios. For the first scenario, in which user 1 has multiple states, and user 2 has one state, most part of the boundary of the expected capacity region is characterized. Interestingly, these rate points are also on the boundary of the capacity region (i.e., the best achievable rate pairs) when the CSI is fully known at both transmitters. Furthermore the expected capacity region is fully characterized for some asymptotic regimes. For the second scenario, in which both users 1 and 2 have two states, a number of achievable regions are studied, and are demonstrated to be close to an outer bound numerically.

A state-dependent Gaussian Z-interference channel model is investigated in the regime of high state power, in which transmitters 1 and 2 communicate with receivers 1 and 2, and only receiver 2 is interfered by transmitter 1's signal and a random state sequence. The state sequence is known noncausally only to transmitter 1, not to the corresponding transmitter 2. A layered coding scheme is designed for transmitter 1 to help interference cancelation at receiver 2 (using a cognitive dirty paper coding) and to transmit its own message to receiver 1. Inner and outer bounds are derived, and are further analyzed to characterize the boundary of the capacity region either fully or partially for all Gaussian channel parameters. Our results imply that the capacity region of such a channel with mismatched transmitter-side state cognition and receiver-side state interference is strictly less than that of the corresponding channel without state, which is in contrast to Costa type of dirty channels, for which dirty paper coding achieves the capacity of the corresponding channels without state.

A Gaussian cognitive interference channel model with state is investigated, in which transmitters 1 and 2 communicate with receivers 1 and 2 via an interference channel. The two transmitters jointly send one message to receivers 1 and 2, and transmitter 2 also sends a separate message to receiver 2. The channel outputs at the two receivers are corrupted by an independent and identically distributed (i.i.d.) Gaussian state sequences and Gaussian noise variables. The state sequence is noncausally known at transmitter 2 only. The Gaussian channels are partitioned into two classes based on channel parameters. For each class, inner and outer bounds on the capacity region are derived, and either the partial boundary of the capacity region or capacity region is characterized for all Gaussian channels. The cognitive interference channel with state known at both transmitter 2 and receiver 2 is further studied, and the capacity region is established for a class of such channels. It is also shown that this capacity can be achieved by certain Gaussian channels with state noncausally known only at transmitter 2.

The nonparametric decentralized detection problem is investigated, in which the joint distribution of the environmental event and the sensors' observations are not known and only a set of training samples are available. The system features rate constraints, i.e., integer bit constraints on sensors' transmissions, different qualities of observations, additional observations to the fusion center, and multi-level tree-structured network. Our study adopts the kernel-based nonparametric approach proposed by Nguyen, Wainwright, and Jordan with the following generalization. A weighted count kernel is introduced so that the corresponding reproducing kernel Hilbert space (RKHS) (over which the fusion center's decision rule is optimized) allows the fusion center's decision rule to count information from sensors and its own observations differently. In order to find the optimal decision rules, our optimization is solved by alternatively and recursively conducting three optimization steps: finding the optimal weight parameters in the weighted count kernel for selecting the best associated RKHS, finding the best optimal decision rule for the fusion center over the identified RKHS, and finding the local decision rules for sensors. Generalization to multilevel tree-structured networks is also discussed. Finally numerical results are provided to demonstrate the performance based on the proposed weighted count kernel.

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

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.

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.

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.

A wireless broadcast network model with secrecy constraints is investigated, in which a source node broadcastsKconfidential message flows toKuser nodes, with each message intended to be decoded accurately by one user and to be kept secret from all other users (who are thus considered to be eavesdroppers with regard to all other messages but their own). The source maintains a queue for each message flow if it is not served immediately. The channel from the source to theKusers is modeled as a fading broadcast channel, and the channel state information is assumed to be known to the source and the corresponding receivers. Two eavesdropping models are considered. For a collaborative eavesdropping model, in which the eavesdroppers exchange their outputs, the secrecy capacity region is obtained, within which each rate vector is achieved by using a time-division scheme and a source power control policy over channel states. A throughput optimal queue-length-based rate scheduling algorithm is further derived that stabilizes all arrival rate vectors contained in the secrecy capacity region. Moreover, the network utility function is maximized via joint design of rate control, rate scheduling, power control, and secure coding. More precisely, a source controls the message arrival rate according to its message queue, the rate scheduling selects a transmission rate based the queue length vector, and the rate vector is achieved by power control and secure coding. These components work jointly to solve the network utility maximization problem. For a noncollaborative eavesdropping model, in which eavesdroppers do not exchange their outputs, an achievable secrecy rate region is derived based on a time-division scheme, and the queue-length-based rate scheduling algorithm and the corresponding power control policy are obtained that stabilize all arrival rate vectors in this region. The network utility maximizing rate control vector is also obtained.

A recent inner bound on the capacity region of the two-receiver discrete memoryless broadcast channel is shown to be equivalent to the Marton-Gelfand-Pinsker region. The proof method is based on a result of Gelfand and Pinsker concerning channel input distributions.

The secrecy throughput of mobile ad hoc networks (MANETs) with malicious nodes is investigated. The MANET consists ofnlegitimate mobile nodes andmmalicious nodes. Transmissions between legitimate nodes are subject to a delay constraintD. A model under passive attack is first studied, in which the malicious nodes are assumed to be eavesdroppers that only listen to transmission without actively injecting signals. An information-theoretic approach for security is applied to achieve secure communication among legitimate nodes in MANETs with transmissions being kept perfectly secure from eavesdroppers. A critical threshold on the number of malicious nodes (m) is identified such that whenm=o(√{nD}), i.e., limn→∞m/√{nD} = 0, the optimal secrecy throughput equals that of MANETs without malicious nodes, i.e., the impact of the presence of malicious nodes on the network throughput is negligible; and whenm= Ω(√{nD}poly(n)), i.e., limn→∞m/(√{nD}poly(n)) ≥cfor a positive constant c, the optimal secrecy throughput is limited by the number of malicious nodes. A model under active attack is further studied, in which the malicious nodes actively attack the network by transmitting modified packets to the destination nodes. It is shown that to guarantee the same throughput as the model under passive attack, the model under active attack needs to satisfy more stringent condition on the number of malicious nodes.

The fading cognitive multiple-access channel with confidential messages (CMAC-CM) is investigated, in which two users (users 1 and 2) wish to transmit a common message to a destination and user 1 also has a confidential message intended for the destination. The two users transmit to the destination via a multiple access channel, and user 2 also receives noisy channel outputs. Such channel outputs potentially help user 2 to learn user 1's confidential information (although they are not exploited by user 2 for channel transmission). Hence, user 1 views user 2 as an eavesdropper and wishes to keep its confidential message as secret as possible from user 2. A parallel CMAC-CM with independent subchannels is first studied. The secrecy capacity region of the parallel CMAC-CM is established, which yields the secrecy capacity regions of the parallel CMAC-CM with degraded subchannels and the parallel Gaussian CMAC-CM. These results are then applied to study the fading CMAC-CM, in which both the user-to-user channel and the user-to-destination channel are corrupted by multiplicative fading gain coefficients in addition to additive white Gaussian noise. The channel state information (CSI) is assumed to be known at both the users and the destination. With the CSI, users can dynamically change their transmission powers with the channel realization to achieve the optimal performance. The closed-form power allocation function that achieves every boundary point of the secrecy capacity region is derived.

The problem of optimal resource allocation is studied for ergodic fading orthogonal multi-access relay channels (MARCs) in which the users (sources) communicate with a destination with the aid of a half-duplex relay that transmits and receives on orthogonal channels. Under the assumption that the instantaneous fading state information is available at all nodes, the maximum sum-rate and the optimal user and relay power allocations (policies) are developed for a decode-and-forward (DF) relay. A known lemma on the sum-rate of two intersecting polymatroids is used to determine the DF sum-rate and the optimal user and relay policies, and to classify fading MARCs into one of three types: (i) partially clustered MARCs in which a user is clustered either with the relay or with the destination, (ii) clustered MARCs in which all users are either proximal to the relay or to the destination, and (iii) arbitrarily clustered MARCs which are a combination of the first two types. Cutset outer bounds are used to show that DF achieves the capacity region for a sub-class of clustered orthogonal MARCs.

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.

This paper considers the problem of the multiple-input multiple-output (MIMO) Gaussian broadcast channel with two receivers (receivers 1 and 2) and two messages: a common message intended for both receivers and a confidential message intended only for receiver 1 but needing to be kept asymptotically perfectly secure from receiver 2. A matrix characterization of the secrecy capacity region is established via a channel enhancement argument. The enhanced channel is constructed by first splitting receiver 1 into two virtual receivers and then enhancing only the virtual receiver that decodes the confidential message. The secrecy capacity region of the enhanced channel is characterized using an extremal entropy inequality previously established for characterizing the capacity region of a degraded compound MIMO Gaussian broadcast channel.

We study the compound multi-input multi-output (MIMO) broadcast channel with confidential messages (BCC), where one transmitter sends a common message to two receivers and two confidential messages respectively to each receiver. The channel state may take one of a finite set of states, and the transmitter knows the state set but does not know the realization of the state. We study achievable rates with perfect secrecy in the high SNR regime by characterizing an achievable secrecy degree of freedom (s.d.o.f.) region for two models, the Gaussian MIMO-BCC and the ergodic fading multi-input single-output (MISO)-BCC without a common message. We show that by exploiting an additional temporal dimension due to state variation in the ergodic fading model, the achievable s.d.o.f. region can be significantly improved compared to the Gaussian model with a constant state, although at the price of a larger delay.

The secrecy throughput of mobile ad-hoc networks (MANETs) with malicious nodes is investigated. The MANET consists of n legitimate mobile nodes and m malicious nodes. Transmissions between legitimate nodes are subject to a delay constraint D. An information theoretic approach for security is applied to achieve secure communication among legitimate nodes in MANETs with transmissions being kept perfectly secure from malicious nodes. A critical threshold on the number of malicious nodes (m) is identified such that when m = o(radicnD), i.e., limnrarrinfinm/radicnD = 0, the secrecy throughput equals the throughput of MANETs without malicious nodes, i.e., the impact of the presence of malicious nodes on the network throughput is negligible; and when m = Omega (radicnDpoly(n)), i.e., limnrarrinfinm/(radicnDpoly(n)) ges c for a positive constant c, the secrecy throughput is limited by the number of malicious nodes.

Abstract This paper reviews the information theoretic characterization of security in broadcast channels, in which a transmitter has both public and confidential messages intended for multiple receivers. All messages must be successfully received by their intended receivers, and the confidential messages must be kept as secret as possible from non‐intended recipients. Various scenarios are considered in the context of two‐user broadcast channels, for which known results on the secrecy capacity region are reviewed and corresponding coding schemes for achieving rates in these regions are described. Copyright © 2009 John Wiley & Sons, Ltd.

Like the conventional two-user interference channel, the cognitive interference channel consists of two transmitters whose signals interfere at two receivers. It is assumed that there is a common message (message 1) known to both transmitters, and an additional independent message (message 2) known only to the cognitive transmitter (transmitter 2). The cognitive receiver (receiver 2) needs to decode messages 1 and 2, while the non cognitive receiver (receiver 1) should decode only message 1. Furthermore, message 2 is assumed to be a confidential message which needs to be kept as secret as possible from receiver 1, which is viewed as an eavesdropper with regard to message 2. The level of secrecy is measured by the equivocation rate. In this paper, a single-letter expression for the capacity-equivocation region of the discrete memoryless cognitive interference channel is obtained. The capacity-equivocation region for the Gaussian cognitive interference channel is also obtained explicitly. Moreover, particularizing the capacity-equivocation region to the case without a secrecy constraint, the capacity region for the two-user cognitive interference channel is obtained, by providing a converse theorem.

In this paper, we consider the optimality of the beamforming scheme for both the multiple-input multiple-output (MIMO) point-to-point channel and the MIMO multiple access channel (MAC), where all communication terminals are assumed to be equipped with multiple antennas. For both channels, the channel matrices have correlated elements and are modelled by virtual representation. For the point-to-point channel, i.e., the single user case, we show that the optimal beamforming angle is unique and is independent of the signal-to-noise ratio (SNR). We further show that there exists a certain SNR threshold below which beamforming is optimal and above which beamforming is strictly suboptimal. For the MIMO MAC, we show that to achieve sum capacity, the inputs from different users are independent and their covariance matrices are diagonal. We also derive a necessary and sufficient condition for the optimal input distribution to achieve the sum capacity. Based on these results, we investigate the conditions under which beamforming achieves the sum capacity. We show that the optimal beamforming angles are not unique, and are dependent on both the value of SNR and beamforming angles of other users. We further provide explicit conditions to determine the optimal beamforming angles for a special class of correlated MIMO MACs.

Outer bounds on the capacity region of broadcast channels are reviewed and a new outer bound is presented.

The compound wire-tap channel is studied, which is based on Wynerpsilas wire-tap model with both the channel from the source to the destination and the channel from the source to the wire-tapper taking a number of states. No matter which states occur for the two channels, the source wishes to guarantee that the destination decodes its message successfully and that the wire-tapper does not obtain the source message. The semideterministic compound wire-tap channel is first studied, in which the channel from the source to the destination is deterministic and has only one state. The secrecy capacity is obtained. An example parallel Gaussian compound wire-tap channel is then studied, in which both channels have two states. Three schemes are studied, and it is shown that introducing randomness either into the source message or into the encoder achieves the maximal secrecy degree of freedom. Both channels studied in this paper demonstrate that creating an auxiliary input, and hence adding a prefix channel from this auxiliary input to the actual channel input, improves the secrecy rate.

This paper investigates the problem of ensuring secure communication through error-correcting coding methods. A practical structured secure coding design is considered for a general wiretap channel, in which the main channel and the eavesdropper channel are binary-input symmetric-output memoryless (BISOM) channels. The proposed secure error-correcting code has a nested code structure. The nesting is based on cosets of a capacity-achieving sequence for binary erasure channels (BECs). The corresponding achievable secrecy rate is derived based on an erasure decomposition for the eavesdropper channel and an Bhattacharyya-equivalent channel construction for the main channel. Those two techniques allow a “degraded” erasure wiretap channel to be built and, hence, significantly simplify the practical coding design for secure transmission.

A discrete memoryless multiple-access channel (MAC) with confidential messages is studied, where two users attempt to transmit common information to a destination and each user also has private (confidential) information intended for the destination. This channel generalizes the classical MAC model in that each user also receives channel outputs, and hence may obtain the confidential information sent by the other user from the channel output it receives. However, each user views the other user as a wiretapper or eavesdropper, and wishes to keep its confidential information as secret as possible from the other user. The level of secrecy of the confidential information is measured by the equivocation rate, i.e., the entropy rate of the confidential information conditioned on channel outputs at the wiretapper (the other user). The performance measure is the rate-equivocation tuple that includes the common rate, two private rates, and two equivocation rates as components. The set that includes all achievable rate-equivocation tuples is referred to as the capacity-equivocation region. The case of perfect secrecy is particularly of interest, in which each user's confidential information is perfectly hidden from the other user. The set that includes all achievable rates with perfect secrecy is referred to as the secrecy capacity region. For the MAC with two confidential messages, in which both users have confidential messages for the destination, inner bounds on the capacity-equivocation region, and secrecy capacity region are obtained. It is demonstrated that there is a tradeoff between the two equivocation rates (secrecy levels) achieved for the two confidential messages. For the MAC with one confidential message, in which only one user (user 1) has private (confidential) information for the destination, inner and outer bounds on the capacity-equivocation region are derived. These bounds match partially, and hence the capacity-equivocation region is partially characterized. Furthermore, the outer bound provides a tight converse for the case of perfect secrecy, and hence establishes the secrecy capacity region. A class of degraded MACs with one confidential message is further studied, and the capacity-equivocation region and the secrecy capacity region are established. These results are further explored via two example channels: the binary and Gaussian MACs. For both channels, the capacity-equivocation regions and the secrecy capacity regions are obtained.

The fading broadcast channel with confidential messages (BCC) is investigated, where a source node has common information for two receivers (receivers 1 and 2), and has confidential information intended only for receiver 1. The confidential information needs to be kept as secret as possible from receiver 2. The broadcast channel from the source node to receivers 1 and 2 is corrupted by multiplicative fading gain coefficients in addition to additive Gaussian noise terms. The channel state information (CSI) is assumed to be known at both the transmitter and the receivers. The parallel BCC with independent subchannels is first studied, which serves as an information-theoretic model for the fading BCC. The secrecy capacity region of the parallel BCC is established, which gives the secrecy capacity region of the parallel BCC with degraded subchannels. The secrecy capacity region is then established for the parallel Gaussian BCC, and the optimal source power allocations that achieve the boundary of the secrecy capacity region are derived. In particular, the secrecy capacity region is established for the basic Gaussian BCC. The secrecy capacity results are then applied to study the fading BCC. The ergodic performance is first studied. The ergodic secrecy capacity region and the optimal power allocations that achieve the boundary of this region are derived. The outage performance is then studied, where a long-term power constraint is assumed. The power allocation is derived that minimizes the outage probability where either the target rate of the common message or the target rate of the confidential message is not achieved. The power allocation is also derived that minimizes the outage probability where the target rate of the confidential message is not achieved subject to the constraint that the target rate of the common message must be achieved for all channel states.

The fading broadcast channel with confidential messages (BCC) is investigated, where a source node has common information for two receivers (receivers 1 and 2), and has confidential information intended only for receiver 1. The confidential information needs to be kept as secret as possible from receiver 2. The broadcast channel from the source node to receivers 1 and 2 is corrupted by multiplicative fading gain coefficients in addition to additive Gaussian noise terms. The channel state information (CSI) is assumed to be known at both the transmitter and the receivers. The secrecy capacity region is first established for the parallel Gaussian BCC, and the optimal source power allocations that achieve the boundary of the secrecy capacity region are derived. In particular, the secrecy capacity region is established for the Gaussian case of the Csiszar-Korner BCC model. The secrecy capacity results are then applied to give the ergodic secrecy capacity region for the fading BCC.

The problem of resource allocation is studied for a two-user fading orthogonal multiaccess relay channel (MARC) where both users (sources) communicate with a destination in the presence of a relay. A half-duplex relay is considered that transmits on a channel orthogonal to that used by the sources. The instantaneous fading state between every transmit-receive pair in this network is assumed to be known at both the transmitter and receiver. Under an average power constraint at each source and the relay, the sum-rate for the achievable strategy of decode-and-forward (DF) is maximized over all power allocations (policies) at the sources and relay. It is shown that the sum-rate maximizing policy exploits the multiuser fading diversity to reveal the optimality of opportunistic channel use by each user. A geometric interpretation of the optimal power policy is also presented.

This paper studies secrecy capacity in a semi-deterministic setting, in which the channel between legitimate users (called Alice and Bob) is deterministic, while that between Alice and the eavesdropper (called Eve) is a discrete memoryless channel. Such a model is particularly relevant when a pre-existing error correcting code tailored to the legitimate channel is in use on top of which secret information is to be shared. First, a point-to-point setting is considered with a single wiretapper, a situation in which the secrecy capacity has an elegant characterization. Next, a generalized multiple access setting with confidential messages is considered in which each user wishes to communicate secret information to a common destination without the other determining its message. In this latter situation, outer bounds on the secrecy capacity are obtained.

A partially cooperative relay broadcast channel (RBC) is a three-node network with one source node and two destination nodes (destinations 1 and 2) where destination 1 can act as a relay to assist destination 2. Inner and outer bounds on the capacity region of the discrete memoryless partially cooperative RBC are obtained. When the relay function is disabled, the inner bound reduces to an inner bound on the capacity region of broadcast channels that includes an inner bound of Marton, and Gel'fand and Pinsker. The outer bound reduces to a new outer bound on the capacity region of broadcast channels that generalizes an outer bound of Marton to include a common message, and that generalizes an outer bound of Gel'fand and Pinsker to apply to general discrete memoryless broadcast channels. The proof for the outer bound simplifies the proof of Gel'fand and Pinsker that was based on a recursive approach. Four classes of RBCs are studied in detail. For the partially cooperative RBC with degraded message sets, inner and outer bounds are obtained. For the semideterministic partially cooperative RBC and the orthogonal partially cooperative RBC, the capacity regions are established. For the parallel partially cooperative RBC with unmatched degraded subchannels, the capacity region is established for the case of degraded message sets. The capacity is also established when the source node has only a private message for destination 2, i.e., the channel reduces to a parallel relay channel with unmatched degraded subchannels.

The capacity regions are investigated for two relay broadcast channels (RBCs), where relay links are incorporated into two-user broadcast channels to support user cooperation. In the first channel, the partially cooperative RBC, only one user in the system acts as a relay. An achievable rate region is derived based on the relay using the decode-and-forward scheme. An outer bound on the capacity region is derived and is shown to be tighter than the cut-set bound. For the special case where the partially cooperative RBC is degraded, the achievable rate region is shown to be the capacity region. Two Gaussian cases of the partially cooperative RBC are studied. For the system where the additive white Gaussian noise (AWGN) term at one receiver is a degraded version of the other, which we refer to as the D-AWGN partially cooperative RBC, the capacity region is established. For the system where the AWGN term at one receiver is independent of the other, which we refer to as the AWGN partially cooperative RBC, inner and outer bounds on the capacity region are derived and are shown to be close. Furthermore, it is shown that feedback does not increase the capacity region for the degraded partially cooperative RBC, but that it improves the capacity region for the nondegraded version. In particular, feedback improves the capacity region for the AWGN partially cooperative RBC. In the second channel model being studied in the paper, the fully cooperative RBC, both users can act as relay nodes. All the results for the partially cooperative RBC are correspondingly generalized to the fully cooperative RBC. In particular, capacity regions are established for the degraded and D-AWGN fully cooperative RBCs. The capacity region is also established for the fully cooperative RBC with feedback. It is further shown that the AWGN fully cooperative RBC has a larger achievable rate region than its partially cooperative counterpart. The results illustrate that relaying and user cooperation are powerful techniques for improving the capacity of broadcast channels

Resource allocation is investigated for fading relay channels under separate power constraints at the source and relay nodes. As a basic information-theoretic model for fading relay channels, the parallel relay channel is first studied, which consists of multiple independent three-terminal relay channels as subchannels. Lower and upper bounds on the capacity are derived, and are shown to match, and thus establish the capacity for the parallel relay channel with degraded subchannels. This capacity theorem is further demonstrated via the Gaussian parallel relay channel with degraded subchannels, for which the synchronized and asynchronized capacities are obtained. The capacity-achieving power allocation at the source and relay nodes among the subchannels is partially characterized for the synchronized case and fully characterized for the asynchronized case. The fading relay channel is then studied, which is based on the three-terminal relay channel with each communication link being corrupted by a multiplicative fading gain coefficient as well as an additive Gaussian noise term. For each link, the fading state information is assumed to be known at both the transmitter and the receiver. The source and relay nodes are allowed to allocate their power adaptively according to the instantaneous channel state information. The source and relay nodes are assumed to be subject to separate power constraints. For both the full-duplex and half-duplex cases, power allocations that maximize the achievable rates are obtained. In the half-duplex case, the power allocation needs to be jointly optimized with the channel resource (time and bandwidth) allocation between the two orthogonal channels over which the relay node transmits and receives. Capacities are established for fading relay channels that satisfy certain conditions.

A discrete memoryless generalized multiple access channel (GMAC) with confidential messages is studied, where two users attempt to transmit common information to a destination and each user also has private (confidential) information intended for the destination. This channel generalizes the multiple access channel (MAC) in that the two users also receive channel output. It is assumed that each user views the other user as a wiretapper, and wishes to keep its confidential information as secret as possible from the other user. The level of secrecy of the confidential information is measured by the equivocation rate. The performance measure of interest is the rate-equivocation tuple that includes the common rate, two private rates and two equivocation rates as components. The set that includes all achievable rate-equivocation tuples is referred to as the capacity-equivocation region. For the GMAC with one confidential message set, where only one user (user 1) has private (confidential) information for the destination, inner and outer bounds on the capacity-equivocation region are derived. The outer bound provides a tight converse to the secrecy capacity region, which is the set of all achievable rates with user 2 being perfectly ignorant of confidential messages of user 1, thus establishing the secrecy capacity region. Furthermore, the degraded GMAC with one confidential message set is further studied, and the capacity-equivocation region and the secrecy capacity region are established. For the GMAC with two confidential message sets, where both users have confidential messages for the destination, an inner bound on the capacity-equivocation region is obtained. The secrecy rate region is derived, where each user's confidential information is perfectly hidden from the other user

A Gaussian orthogonal relay model is investigated, where the source transmits to the relay and destination in channel 1, and the relay transmits to the destination in channel 2, with channels 1 and 2 being orthogonalized in the time-frequency plane in order to satisfy practical constraints. The total available channel resource (time and bandwidth) is split into the two orthogonal channels, and the resource allocation to the two channels is considered to be a design parameter that needs to be optimized. The main focus of the analysis is on the case where the source-to-relay link is better than the source-to-destination link, which is the usual scenario encountered in practice. A lower bound on the capacity (achievable rate) is derived, and optimized over the parameter /spl theta/, which represents the fraction of the resource assigned to channel 1. It is shown that the lower bound achieves the max-flow min-cut upper bound at the optimizing /spl theta/, the common value thus being the capacity of the channel at the optimizing /spl theta/. Furthermore, it is shown that when the relay-to-destination signal-to-noise ratio (SNR) is less than a certain threshold, the capacity at the optimizing /spl theta/ is also the maximum capacity of the channel over all possible resource allocation parameters /spl theta/. Finally, the achievable rates for optimal and equal resource allocations are compared, and it is shown that optimizing the resource allocation yields significant performance gains.

The capacity of the multiple-input multiple-output (MIMO) wireless channel with uniform linear arrays (ULAs) of antennas at the transmitter and receiver is investigated. It is assumed that the receiver knows the channel perfectly but that the transmitter knows only the channel statistics. The analysis is carried out using an equivalent virtual representation of the channel that is obtained via a spatial discrete Fourier transform. A key property of the virtual representation that is exploited is that the components of virtual channel matrix are approximately independent. With this approximation, the virtual representation allows for a general capacity analysis without the common simplifying assumptions of Gaussian statistics and product-form correlation (Kronecker model) for the channel matrix elements. A deterministic line-of-sight (LOS) component in the channel is also easily incorporated in much of the analysis. It is shown that in the virtual domain, the capacity-achieving input vector consists of independent zero-mean proper-complex Gaussian entries, whose variances can be computed numerically using standard convex programming algorithms based on the channel statistics. Furthermore, in the asymptotic regime of low signal-to-noise ratio (SNR), it is shown that beamforming along one virtual transmit angle is asymptotically optimal. Necessary and sufficient conditions for the optimality of beamforming, and the value of the corresponding optimal virtual angle, are also derived based on only the second moments of the virtual channel coefficients. Numerical results indicate that beamforming may be close to optimum even at moderate values of SNR for sparse scattering environments. Finally, the capacity is investigated in the asymptotic regime where the numbers of receive and transmit antennas go to infinity, with their ratio being kept constant. Using a result of Girko, an expression for the asymptotic capacity scaling with the number of antennas is obtained in terms

The capacity of two broadcast systems with relay links is studied in this paper. Both of these systems are extensions of two users degraded broadcast channels, which achieves a rate region of channels and includes the capacity region of original broadcast channel. We then consider another system, the dumb relay broadcast channel, where an additional relay node is introduced into the two users degraded broadcast channel that assists both user. This relay node does not have its own information from the source, and hence is referred to as dumb relay node. From the results an achievable rate region for this channel is derived and is shown to include that for the cooperative broadcast channel.

The capacity of noncoherent time-selective Rayleigh-fading channels is studied under various models for the variations in time. The study includes both single-input and single-output (SISO) and multiple-input and multiple-output (MIMO) systems. A block-fading model is first considered where the channel changes correlatively over each block period of length T, and independently across blocks. The predictability of the channel is characterized through the rank Q of the correlation matrix of the vector of channel gains in each block. This model includes, as special cases, the standard block-fading model where the channel remains constant over block periods (Q=1), and models where the fading process has finite differential entropy rate (Q=T). The capacity is initially studied for long block lengths and some straightforward but interesting asymptotes are established. For the case where Q is kept fixed as T/spl rarr//spl infin/, it is shown that the noncoherent capacity converges to the coherent capacity. For the case where both T,Q/spl rarr//spl infin/, with Q/T being held constant, a bound on the capacity loss due to channel unpredictability is established. The more interesting scenario of large signal-to-noise ratio (SNR) is then explored in detail. For SISO systems, useful upper and lower bounds on the large SNR asymptotic capacity are derived, and it is shown that the capacity grows logarithmically with SNR with a slope of T-Q/spl rarr/T, for Q