We propose ACProp (Asynchronous-centering-Prop), an adaptive optimizer which combines centering of second momentum and asynchronous update (e.g. for $t$-th update, denominator uses information up to step $t-1$, while numerator uses gradient at $t$-th step). ACProp has both strong theoretical properties and empirical performance. With the example by Reddi et al. (2018), we show that asynchronous optimizers (e.g. AdaShift, ACProp) have weaker convergence condition than synchronous optimizers (e.g. Adam, RMSProp, AdaBelief); within asynchronous optimizers, we show that centering of second momentum further weakens the convergence condition. We demonstrate that ACProp has a convergence rate of $O(\frac{1}{\sqrt{T}})$ for the stochastic non-convex case, which matches the oracle rate and outperforms the $O(\frac{logT}{\sqrt{T}})$ rate of RMSProp and Adam. We validate ACProp in extensive empirical studies: ACProp outperforms both SGD and other adaptive optimizers in image classification with CNN, and outperforms well-tuned adaptive optimizers in the training of various GAN models, reinforcement learning and transformers. To sum up, ACProp has good theoretical properties including weak convergence condition and optimal convergence rate, and strong empirical performance including good generalization like SGD and training stability like Adam. We provide the implementation at \url{ https://github.com/juntang-zhuang/ACProp-Optimizer}.

The empirical performance of neural ordinary differential equations (NODEs) is significantly inferior to discrete-layer models on benchmark tasks (e.g. image classification). We demonstrate an explanation is the inaccuracy of existing gradient estimation methods: the adjoint method has numerical errors in reverse-mode integration; the naive method suffers from a redundantly deep computation graph. We propose the Adaptive Checkpoint Adjoint (ACA) method: ACA applies a trajectory checkpoint strategy which records the forward- mode trajectory as the reverse-mode trajectory to guarantee accuracy; ACA deletes redundant components for shallow computation graphs; and ACA supports adaptive solvers. On image classification tasks, compared with the adjoint and naive method, ACA achieves half the error rate in half the training time; NODE trained with ACA outperforms ResNet in both accuracy and test-retest reliability. On time-series modeling, ACA outperforms competing methods. Furthermore, NODE with ACA can incorporate physical knowledge to achieve better accuracy.

Most popular optimizers for deep learning can be broadly categorized as adaptive methods (e.g.~Adam) and accelerated schemes (e.g.~stochastic gradient descent (SGD) with momentum). For many models such as convolutional neural networks (CNNs), adaptive methods typically converge faster but generalize worse compared to SGD; for complex settings such as generative adversarial networks (GANs), adaptive methods are typically the default because of their stability. We propose AdaBelief to simultaneously achieve three goals: fast convergence as in adaptive methods, good generalization as in SGD, and training stability. The intuition for AdaBelief is to adapt the stepsize according to the "belief" in the current gradient direction. Viewing the exponential moving average (EMA) of the noisy gradient as the prediction of the gradient at the next time step, if the observed gradient greatly deviates from the prediction, we distrust the current observation and take a small step; if the observed gradient is close to the prediction, we trust it and take a large step. We validate AdaBelief in extensive experiments, showing that it outperforms other methods with fast convergence and high accuracy on image classification and language modeling. Specifically, on ImageNet, AdaBelief achieves comparable accuracy to SGD. Furthermore, in the training of a GAN on Cifar10, AdaBelief demonstrates high stability and improves the quality of generated samples compared to a well-tuned Adam optimizer.

This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the minimization of quadratic functions and are fundamental primitives that arise in several domains. Algorithms that have been proposed are typically centralized and involve multiple graph-theoretic constructions or sampling mechanisms that make them difficult to implement and analyze. On the other hand, message passing routines are distributed, simple, and easy to implement. In this paper we establish a framework to analyze Min-Sum to solve voltage and flow problems. We characterize the error committed by the algorithm on general weighted graphs in terms of hitting times of random walks defined on the computation trees that support the operations of the algorithms with time. For $d$-regular graphs with equal weights, we show that the convergence of the algorithms is controlled by the total variation distance between the distributions of non-backtracking random walks defined on the original graph that start from neighboring nodes. The framework that we introduce extends the analysis of Min-Sum to settings where the contraction arguments previously considered in the literature (based on the assumption of walk summability or scaled diagonal dominance) can not be used, possibly in the presence of constraints.

The global Markov property for Gaussian graphical models ensures graph separation implies conditional independence. Specifically if a node set $S$ graph separates nodes $u$ and $v$ then $X_u$ is conditionally independent of $X_v$ given $X_S$. The opposite direction need not be true, that is, $X_u \perp X_v \mid X_S$ need not imply $S$ is a node separator of $u$ and $v$. When it does, the relation $X_u \perp X_v \mid X_S$ is called faithful. In this paper we provide a characterization of faithful relations and then provide an algorithm to test faithfulness based only on knowledge of other conditional relations of the form $X_i \perp X_j \mid X_S$. We study two classes of separable Gaussian graphical models, namely, weakly $K$-separable and strongly $K$-separable Gaussian graphical models. Using the above test for faithfulness, we introduce algorithms to learn the topologies of weakly $K$-separable and strongly $K$-separable Gaussian graphical models with $\Omega(K\log p)$ sample complexity. For strongly $K$-separable Gaussian graphical models, we additionally provide a method with error bounds for learning the off-diagonal precision matrix entries.

We apply the Min-Sum message-passing protocol to solve the consensus problem in distributed optimization. We show that while the ordinary Min-Sum algorithm does not converge, a modified version of it known as Splitting yields convergence to the problem solution. We prove that a proper choice of the tuning parameters allows Min-Sum Splitting to yield subdiffusive accelerated convergence rates, matching the rates obtained by shift-register methods. The acceleration scheme embodied by Min-Sum Splitting for the consensus problem bears similarities with lifted Markov chains techniques and with multi-step first order methods in convex optimization.

This paper studies the performance of sparse regression codes for lossy compression with the squared-error distortion criterion. In a sparse regression code, code words are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding, sparse regression codes achieve the Shannon rate-distortion function for i.i.d. Gaussian sources R*(D) as well as the optimal excess-distortion exponent. This completes a previous result which showed that R*(D) and the optimal exponent were achievable for distortions below a certain threshold. The proof of the rate-distortion result is based on the second moment method, a popular technique to show that a non-negative random variable X is strictly positive with high probability. In our context, X is the number of code words within target distortion D of the source sequence. We first identify the reason behind the failure of the standard second moment method for certain distortions, and illustrate the different failure modes via a stylized example. We then use a refinement of the second moment method to show that R*(D) is achievable for all distortion values. Finally, the refinement technique is applied to Suen's correlation inequality to prove the achievability of the optimal Gaussian excess-distortion exponent.

In this paper, we propose capacity-achieving communication schemes for Gaussian finite-state Markov channels subject to an average channel input power constraint, under the assumption that the transmitters can have access to delayed noiseless output feedback as well as instantaneous or delayed channel state information. We show that the proposed schemes reveals connections between feedback communication and feedback control.

We study the rate-distortion performance of Sparse Regression Codes where the codewords are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding and squared error distortion, these codes achieve R*(D), the Shannon rate-distortion function for an i.i.d. Gaussian source. This completes a previous result which showed that R*(D) was achievable for distortions below a certain threshold. The proof is based on the second moment method, a popular technique to show that a non-negative random variable X is strictly positive with high probability. We first identify the reason behind the failure of the vanilla second moment method for this problem, and then introduce a refinement to show that R*(D) is achievable for all distortions.

Many storage channels admit reading and rewriting of the content at a given cost. We consider rewritable channels with a hidden state which models the unknown characteristics of the memory cell. In addition to mitigating the effect of write noise, rewrites can help the write controller obtain a better estimate of the hidden state. The paper has two contributions. The first is a lower bound on the capacity of a general rewritable channel with hidden state. The lower bound is obtained using a coding scheme that combines Gelfand-Pinsker coding with superposition coding. The rewritable AWGN channel is discussed as an example. The second contribution is a simple coding scheme for a rewritable channel where the write noise and hidden state are both uniformly distributed. It is shown that this scheme is asymptotically optimal as the number of rewrites gets large.

We study a new class of codes for lossy compression with the squared-error distortion criterion, designed using the statistical framework of high-dimensional linear regression. Codewords are linear combinations of subsets of columns of a design matrix. Called a sparse superposition or sparse regression codebook, this structure is motivated by an analogous construction proposed recently by Barron and Joseph for communication over an Additive White Gaussian Noise channel. For independent identically distributed (i.i.d) Gaussian sources and minimum-distance encoding, we show that such a code can attain the Shannon rate-distortion function with the optimal error exponent, for all distortions below a specified value. It is also shown that sparse regression codes are robust in the following sense: a codebook designed to compress an i.i.d Gaussian source of variance σ2with (squared-error) distortion D can compress any ergodic source of variance less than σ2to within distortion D. Thus, the sparse regression ensemble retains many of the good covering properties of the i.i.d random Gaussian ensemble, while having a compact representation in terms of a matrix whose size is a low-order polynomial in the block-length.

We propose computationally efficient encoders and decoders for lossy compression using a sparse regression code. The codebook is defined by a design matrix and codewords are structured linear combinations of columns of this matrix. The proposed encoding algorithm sequentially chooses columns of the design matrix to successively approximate the source sequence. It is shown to achieve the optimal distortion-rate function for independent identically distributed (i.i.d) Gaussian sources under the squared-error distortion criterion. For a given rate, the parameters of the design matrix can be varied to tradeoff distortion performance with encoding complexity. An example of such a tradeoff as a function of the block length n is the following. With computational resource (space or time) per source sample of O((n/log n)2), for a fixed distortion-level above the Gaussian distortion-rate function, the probability of excess distortion decays exponentially in n. The sparse regression code is robust in the following sense: for any ergodic source, the proposed encoder achieves the optimal distortion-rate function of an i.i.d Gaussian source with the same variance. Simulations show that the encoder has good empirical performance, especially at low and moderate rates.

We propose computationally efficient encoders and decoders for lossy compression using a Sparse Regression Code. Codewords are structured linear combinations of columns of a design matrix. The proposed encoding algorithm sequentially chooses columns of the design matrix to successively approximate the source sequence. It is shown to achieve the optimal distortion-rate function for i.i.d Gaussian sources with squared-error distortion. For a given rate, the parameters of the design matrix can be varied to trade off distortion performance with encoding complexity. An example of such a trade-off is: computational resource (space or time) per source sample of O((n/ log n)2) and probability of excess distortion decaying exponentially in n/ log n, where n is the block length. The Sparse Regression Code is robust in the following sense: for any ergodic source, the proposed encoder achieves the optimal distortion-rate function of an i.i.d Gaussian source with the same variance. Simulations show that the encoder has very good empirical performance, especially at low and moderate rates.

Sparse Superposition or Sparse Regression codes were recently introduced by Barron and Joseph for communication over the AWGN channel. The code is defined in terms of a design matrix; codewords are linear combinations of subsets of columns of the matrix. These codes achieve the AWGN channel capacity with computationally feasible decoding. We have shown that they also achieve the optimal rate-distortion function for Gaussian sources. Further, the sparse regression codebook has a partitioned structure that facilitates random binning and superposition. In this paper, we review existing results concerning Sparse Regression codes and discuss directions for future research.

New lower bounds are obtained for the capacity of a binary channel with deletions and insertions. Each input bit to the channel is deleted with probability d, or an extra bit is inserted after it with probability i, or it is transmitted unmodified with probability 1-d-i. This paper builds on the idea introduced in [1] of using a sub-optimal decoder that decodes the positions of the deleted and inserted runs, in addition to the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its sub-optimality. The main contribution is an analytical lower bound for the rate loss term which leads to an improvement in the capacity lower bound of [1]. For the special case of the deletion channel, the new bound is larger than the previous best lower bound for deletion probabilities up to 0.3.

The max-product algorithm, a local message-passing scheme that attempts to compute the most probable assignment (MAP) of a given probability distribution, has been successfully employed as a method of approximate inference for applications arising in coding theory, computer vision, and machine learning. However, the max-product algorithm is not guaranteed to converge, and if it does, it is not guaranteed to recover the MAP assignment. Alternative convergent message-passing schemes have been proposed to overcome these difficulties. This paper provides a systematic study of such message-passing algorithms that extends the known results by exhibiting new sufficient conditions for convergence to local and/or global optima, providing a combinatorial characterization of these optima based on graph covers, and describing a new convergent and correct message-passing algorithm whose derivation unifies many of the known convergent message-passing algorithms. While convergent and correct message-passing algorithms represent a step forward in the analysis of max-product style message-passing algorithms, the conditions needed to guarantee convergence to a global optimum can be too restrictive in both theory and practice. This limitation of convergent and correct message-passing schemes is characterized by graph covers and illustrated by example.

This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit is added after it with probability i, or it is transmitted unmodified with probability 1-d-i. A computable lower bound on the capacity of this channel is derived. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer, some runs get deleted, and some new runs are added. It is difficult for the decoder to synchronize the channel output sequence to the transmitted codeword mainly due to deleted runs and new inserted runs. The main idea is a mutual information decomposition in terms of the rate achieved by a suboptimal decoder that determines the positions of the deleted and inserted runs in addition to decoding the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its suboptimality. Obtaining computable lower bounds on each of these quantities yields a lower bound on the capacity. The bounds proposed in this paper provide the first characterization of achievable rates for channels with general insertions, and for channels with both deletions and insertions. For the special case of the deletion channel, the proposed bound improves on the previous best lower bound for deletion probabilities up to 0.3.

We study a class of codes for compressing memoryless Gaussian sources, designed using the statistical framework of high-dimensional linear regression. Codewords are linear combinations of subsets of columns of a design matrix. With minimum-distance encoding we show that such a codebook can attain the rate-distortion function with the optimal error-exponent, for all distortions below a specified value. The structure of the codebook is motivated by an analogous construction proposed recently by Barron and Joseph for communication over an AWGN channel.

Many storage channels admit reading and rewriting of the content at a given cost. We consider rewritable channels with uniform write noise and a hidden state which models the unknown characteristics of the memory cell. In addition to mitigating the effect of the write noise, rewrites can help the write controller obtain a better estimate of the hidden state. We present two coding strategies, each of which yields a lower bound on the rewrite capacity. We show that the second strategy is asymptotically optimal as the number of rewrites gets large.

Variable length communication over a compound channel with feedback is considered. Traditionally, capacity of a compound channel without feedback is defined as the maximum rate that is determined before the start of communication such that communication is reliable. This traditional definition is pessimistic. In the presence of feedback, an opportunistic definition is given. Capacity is defined as the maximum rate that is determined at the end of communication such that communication is reliable. Thus, the transmission rate can adapt to the realized channel. Under this definition, feedback communication over a compound channel is conceptually similar to multiterminal communication. Transmission rate is a vector rather than a scalar; channel capacity is a region rather than a scalar; error exponent is a region rather than a scalar. In this paper, variable length communication over a compound channel with feedback is formulated, its opportunistic capacity region is characterized, and lower bounds for its error exponent region are provided.

Consider a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit added after it with probability i, or it is transmitted unmodified with probability 1 - d - i. We obtain a lower bound on the capacity of this channel. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer, some runs get deleted, and some new runs are added. The capacity is difficult to compute mainly due to the last two phenomena: deleted runs, and new inserted runs. We consider a decoder which first decodes the positions of the deleted and inserted runs, and then the transmitted codeword. Analyzing the performance of such a decoder leads to a computable lower bound on the capacity.

We examine the asymptotic behavior of optimal values and optimal configurations for the maximum weight partial coloring (MWPC) problem on sparse random graphs. The MWPC problem is a weighted version of the partial coloring problem, and it is a generalization of the maximum weight independent set (MWIS) problem. The MWPC problem is an illustrative example of how to employ the local weak convergence method on combinatorial optimization problems that are defined via a graphical model and have a nonbinary alphabet. Many of the results are inspired by Gamarnik, Nowicki, and Swirscsz [Random Structures Algorithms, 28 (2005), pp. 76–106]. They showed that if vertex weights were sampled independently from a nonatomic distribution and if a particular fixed point equation had a unique solution, then the scaled MWIS value on sparse Erdös–Rényi graphs converges in probability. Under the same conditions, Sanghavi and Shah [http://arxiv.org/pdf/cs/0508097v2 (12 April 2008)] showed how the max-product message passing algorithm can be used to produce [Formula: see text] approximations with probability [Formula: see text]. There are major difficulties in applying the above techniques to other natural combinatorial optimization problems. We show how to strengthen them so that they can be applied to a new range of problems which includes the MWPC problem. In the MWPC case, we show how our techniques can be used to get new convergence results on sparse Erdös–Rényi graphs—even in the case where the weights are sampled from a discrete distribution. This depends on new results on how certain long range independence properties occur almost surely for branching processes.

Network tomography studies the inference of network structure and dynamics based on indirect measurements when direct measurements are unavailable or difficult to collect. In this paper, we design and analyze routing tree topology and link performance inference algorithms for communication networks using tools from phylogenetic inference in evolutionary biology. We develop polynomial-time distance-based inference algorithms and derive sufficient conditions for the correctness of the algorithms. We show that the algorithms are consistent and robust. In particular, the algorithms achieve the optimall∞-radius 1/2 for binary trees and 1/4 for general trees when a threshold neighbor selection criterion is used.

Capacity of a compound channel without feedback is defined in a pessimistic manner as the maximum rate determined before the start of communication such that communication is reliable. In the presence of feedback, the transmission rate can adapt to the channel chosen by nature. Thus, capacity can be defined in an opportunistic manner as the maximum rate determined at the end of communication such that communication is reliable. Under this definition, transmission rate and error exponents are regions rather than scalars. In this paper, variable length communication over a compound channel with feedback is formulated, its opportunistic capacity region is characterized, and lower bounds for its error exponent region are provided.

We examine the clustering phenomena of solutions to inference problems defined on graphs and its effect on message-passing algorithms.

A graphical model for sequential teams is presented. This model is easy to understand, and at the same time, is general enough to model any finite horizon sequential team with finite valued system variables and unconstrained decision rules. The model can also be represented as a directed acyclic factor graph. This representation makes it easier to visualize and understand the functional dependencies between different system variables. It also helps in identifying data that is irrelevant for a decision maker to take an optimal decision. Such irrelevant data can be identified using algorithms from graphical models. Thus, the structural properties of optimal decision makers in this model for a sequential team can be identified in an automated manner using the directed acyclic factor graph representation of the sequential team.

The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashev's classic result is extended to finite-state ergodic Markov channels. For these channels, a single-letter characterization of the reliability function is presented, under the assumption of full causal output feedback, and full causal observation of the channel state both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference (ISI). Specifically, the convex-analytic approach to Markov decision processes is adopted in order to handle problems with stopping time horizons induced by variable-length coding schemes.

In this paper, we introduce a general framework for treating channels with memory and feedback. First, we prove a general feedback channel coding theorem based on Massey's concept of directed information. Second, we present coding results for Markov channels. This requires determining appropriate sufficient statistics at the encoder and decoder. We give a recursive characterization of these sufficient statistics. Third, a dynamic programming framework for computing the capacity of Markov channels is presented. Fourth, it is shown that the average cost optimality equation (ACOE) can be viewed as an implicit single-letter characterization of the capacity. Fifth, scenarios with simple sufficient statistics are described. Sixth, error exponents for channels with feedback are presented.

Inference of the routing topology and link performance from a node to a set of other nodes is an important component of network monitoring and application design. In this paper we propose a general framework for designing topology inference algorithms based on additive metrics. Our framework allows the integration of both end-to-end packet probing measurements and traceroute type measurements. Based on this framework we design several computationally efficient topology inference algorithms. In particular, we propose a novel sequential topology inference algorithm to address the probing scalability problem and handle dynamic node joining and leaving. We provide sufficient conditions for the correctness of our algorithms and derive lower bounds on the probability of correct topology inference. We conduct Internet experiments to evaluate and demonstrate the effectiveness of our algorithms.

We extend our previous work on channels with feedback to cases with partial feedback. Specifically [2], [3] treated the case of channels with memory and full output feedback. In this paper we treat the case of general channels with memory and partial deterministic feedback. One of the main difficulties in this problem has to do with the fact that the transmitter and the receiver may have different information about the state of the channel. We show how to choose appropriate sufficient statistics at both the transmitter and receiver. To this end we introduce the notion of joint sufficiency. These jointly sufficient statistics give insight into the structure of the channel encoder. We then formulate the capacity problem as an infinite horizon average cost stochastic control problem. The resulting Bellman equation leads to an implicit single-letter characterization of the capacity.

Understanding the role of communication in networked control systems is an important and challenging problem. In this paper we determine the communication rates required to achieve a variety of cooperative control objectives. Our results depend heavily on three information theoretic ideas: the directed data processing inequality, Slepian-Wolf coding, and source coding with side-information at the receiver.

Loss networks provide a powerful tool for the analysis and design of many communication and networking systems. It is well known that a large number of loss networks have product-form steady-state probabilities. However, for most networks of practical interest, evaluating the system performance is a difficult task due to the presence of a normalization constant. In this paper, we present a new framework based on probabilistic graphical models to tackle this task. Specifically, we propose to use factor graphs to model the stationary distribution of a network. Based on the factor graph model, we can easily derive recursive formulas for symmetric networks. Most importantly, for networks with arbitrary topology, we can apply efficient message-passing algorithms like the sum-product algorithm to compute the exact or approximate marginal distributions of all state variables and the related performance measures such as call blocking probabilities. Through extensive numerical experiments, we show that the sum-product algorithm returns very accurate blocking probabilities and greatly outperforms the reduced load approximation for both single-service and multiservice loss networks with a variety of topologies.

We consider the reliability function of Markov channels with feedback and variable length channel codes. We extend Burnashev's [M.V. Burnashev, 1976] classic result to this case and present a single letter characterization for the reliability function.

We study the capacity of Markov channels with causal deterministic partial (quantized) state feedback. We assume the feedback channel to be memoryless, the channel state process to be Markovian, belong to a finite set, and the state and observation transitions to satisfy some general mixing conditions. For such channels, we obtain a single-letter characterization for the capacity with feedback. We further show that for every e > 0, there exists a finite length memory (sliding) encoder structure that leads to an epsiv-optimal capacity; hence practically optimal performance can be achieved. We show that the non-linear filter generating the conditional state density provides the sufficient statistic for the optimal coding scheme.

A large number of stochastic networks including loss networks and certain queueing networks have product-form steady-state probabilities. However, for most practical networks, evaluating the system performance is a difficult task due to the presence of a normalization constant. We propose a new framework based on probabilistic graphical models to tackle this task. Specifically, we use factor graphs to model the stationary distribution of a network. For networks with arbitrary topology, we can apply efficient message-passing algorithms like the sum-product algorithm to compute the exact or approximate marginal distributions of all state variables and related performance measures such as blocking probabilities. Through extensive numerical experiments, we show that the sum-product algorithm returns very accurate blocking probabilities and greatly outperforms the reduced load approximation for loss networks with a variety of topologies. The factor graph model also provides a promising approach for analyzing product-form queueing networks.

Many communication and networking systems can be modeled as resource-sharing systems with multiple classes of calls. Call admission control (CAC) is an essential component of such systems. Markov decision process (MDP) tools can be applied to analyze and compute the optimal CAC policy that optimizes certain performance metrics of the system. But for most practical systems, it is prohibitively difficult to compute the optimal CAC policy using any MDP algorithm because of the "curse of dimensionality". We are, therefore, motivated to consider two families of structured CAC policies: reservation and threshold policies. These policies are easy to implement and have good performance in practice. However, since the number of structured policies grows exponentially with the number of call classes and the capacity of the system, finding the optimal structured policy is a complex unsolved problem. In this paper, we develop fast and efficient search algorithms to determine the parameters of the structured policies. We prove the convergence of the algorithms. Through extensive numerical experiments, we show that the search algorithms converge quickly and work for systems with large capacity and many call classes. In addition, the returned structured policies have optimal or near-optimal performance, and outperform those structured policies with parameters chosen based on simple heuristics

For a stationary additive Gaussian-noise channel with a rational noise power spectrum of a finite-order$L$, we derive two new results for the feedback capacity under an average channel input power constraint. First, we show that a very simple feedback-dependent Gauss–Markov source achieves the feedback capacity, and that Kalman–Bucy filtering is optimal for processing the feedback. Based on these results, we develop a new method for optimizing the channel inputs for achieving the Cover–Pombra block-length-$n$feedback capacity by using a dynamic programming approach that decomposes the computation into$n$sequentially identical optimization problems where each stage involves optimizing$O(L^{2})$variables. Second, we derive the explicit maximal information rate for stationary feedback-dependent sources. In general, evaluating the maximal information rate for stationary sources requires solving only a few equations by simple nonlinear programming. For first-order autoregressive and/or moving average (ARMA) noise channels, this optimization admits a closed-form maximal information rate formula. The maximal information rate for stationary sources is a lower bound on the feedback capacity, and it equals the feedback capacity if the long-standing conjecture, that stationary sources achieve the feedback capacity, holds.

As today's communication networks (e.g., the Internet) grow in size and diversity, accurate, large-scale, and distributed traffic matrix estimation techniques will become increasingly important for many network control and management tasks. In this paper, we study the gravity model with entropy penalization approach for estimating traffic matrices based on link traffic measurements, which is known to have remarkable accuracy for real networks [7], [12]. We propose a dual approach to convert the constrained primal optimization problem under the gravity model into an unconstrained dual optimization problem. For most practical networks in which the number of links is much smaller than the number of origin-destination pairs, the dual problem has a much smaller dimension and hence scales for large networks. In addition, the solution algorithm for the dual problem can be implemented in a distributed manner.

We consider discrete-time channels with finite-length intersymbol interference and additive Gaussian noise. The channel noise is considered to be a stationary ARMA (autoregressive and/or moving average) Gaussian process. We assume that the channel is used with feedback and compute the maximal feedback information rate achievable by stationary power-constrained sources. We show that feedback-dependent Gauss-Markov sources achieve the feedback capacity, and a Kalman-Bucy filter is optimal for processing the feedback. We then formulate the capacity computation into a system of equations whose solution gives the optimal signaling and the feedback capacity for stationary sources. In general, the equations are solved numerically, but for first-order channels, the problem admits a closed form solution.

In this paper, we provide a new unified approach to analyze and solve multicast-based network inference problems. We show that the outcome variables induced by the transmission of a multicast packet form a Markov random field on the multicast tree. We present an algorithm that recovers the multicast tree topology based on the values of an additive tree metric on pairs of the terminal nodes. We prove the correctness of the algorithm. We also give several examples of an additive tree metric for which the values on pairs of the terminal nodes can be estimated from traffic measurements taken at the receivers. In addition, we propose an algorithm to recover the link performance parameters from the joint distribution of the outcome variables at the terminal nodes

In this paper we study convergence of the max-product (MP) algorithm on general graphs with cycles. Our analysis follows analogously to that given for the convergence of the sum-product algorithm. We do not work with Gibbs measures but instead we introduce and work with local maxifiers. The contributions of this paper include: reformulation of the MP algorithm on cyclic graphs as max-marginalization on an associated computation tree; existence of local maxifiers and proof that uniqueness of the local maxifier is sufficient for convergence of MP; a Gibbsian theory of local maxifiers and interpretation as operators; an example of non-uniqueness which does not exhibit a phase transition like its Gibbs measure counterpart; and insights into the limitations of Dobrushin-type uniqueness conditions

Service differentiation is now becoming a more and more desirable feature in mobile cellular systems making the case for pricing differentiation among the users. One of the main objectives of a mobile service provider is to maximize its revenue. In general there are two approaches to optimize the revenue rate of a base station. One is through call admission control (CAC), the other is through pricing. For most real systems it is prohibitively difficult to compute the optimal CAC policy or pricing scheme because of the 'curse of dimensionality'. Therefore we focus on CAC policies that have simple structures and static pricing schemes in which the charging rates are independent of the system state. However, finding the optimal structured CAC policies or static pricing scheme is still combinatorial in nature. In this paper we show that our recently proposed iterative coordinate search algorithm provides an efficient and effective method to find the optimal or near-optimal structured CAC policies and static pricing schemes for mobile cellular systems.

Many communications and networking systems can be modelled as resource-sharing systems with multiple classes of calls. Call admission control (CAC) is an essential component of such systems. For most practical systems it is prohibitively difficult to compute the optimal CAC policy that optimizes certain performance metrics because of the 'curse of dimensionality'. In this paper we study two families of structured CAC policies: threshold and reservation policies. These policies are easy to implement and have good performance in practice. However, since the number of structured policies grows exponentially with the number of call classes and the capacity of the system, finding the optimal structured policies is a complex unsolved problem. In this paper efficient search algorithms are proposed to find the coordinate optimal structured policies among all structured policies. Through extensive numerical experiments we show that the search algorithms converge quickly and work for systems with large capacity and many call classes. In addition, the returned structured policies have optimal or near-optimal performance, and outperform those structured policies with parameters chosen based on simple heuristics.

Loss networks are a class of resource-sharing models which provide a powerful tool to the analysis and design of many communications and networking systems. For most loss networks of practical interest calculating the exact blocking probabilities is a difficult task. In this paper we present a new framework based on probabilistic graphical models to tackle this task. Specifically, we propose to use factor graphs to model the stationary distribution of product-form loss networks. We also propose to use the sum-product algorithm to compute the marginal distributions and the blocking probabilities of all call classes. Through extensive numerical experiments we show that the sum-product algorithm returns very accurate blocking probabilities and greatly outperforms the reduced load approximation for both single-service and multiservice loss networks with a variety of topologies. In addition, the sum-product algorithm converges very fast and can be implemented in a distributed way

We consider a finite-state machine channel with a finite memory length (e.g., finite length intersymbol interference channels with finite input alphabets-also known as partial response channels). For such a finite-state machine channel, we show that feedback-dependent Markov sources achieve the feedback capacity, and that the required memory length of the Markov process matches the memory length of the channel. Further, we show that the whole history of feedback is summarized by the causal posterior channel state distribution, which is computed by the sum-product forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) (Baum-Welch, discrete-time Wonham filtering) algorithm. These results drastically reduce the space over which the optimal feedback-dependent source distribution needs to be sought. Further, the feedback capacity computation may then be formulated as an average-reward-per-stage stochastic control problem, which is solved by dynamic programming. With the knowledge of the capacity-achieving source distribution, the value of the capacity is easily estimated using Markov chain Monte Carlo methods. When the feedback is delayed, we show that the feedback capacity can be computed by similar procedures. We also show that the delayed feedback capacity is a tight upper bound on the feedforward capacity by comparing it to tight existing lower bounds. We demonstrate the applicability of the method by computing the feedback capacity of partial response channels and the feedback capacity of run-length-limited (RLL) sequences over binary symmetric channels (BSCs).

This paper proposes a capacity-achieving feedback communication scheme for finite-state Markov channels (FSMC) with channel state information (CSI). This scheme considerably reduces coding complexity, shortens coding delay, and has a doubly exponential reliability function.

This paper introduces a particular network source coding problem for sensor networks. The problem consists of transmitting information between a set of source-destination pairs over a network where the nodes are correlated. When the underlying graph structure is a tree we give a complete characterization of the achievable rate region and discusses the role of graphical models and in particular the junction tree in determining routing paths for cases where the underlying graph structure has cycles. The communication complexity of learning the statistics of the source from observation data and computing the routing spanning tree in a distributed manner is determined.

For discrete-time power-constrained linear Gaussian channels with z-domain rational power spectral density functions: 1) Gauss-Markov sources achieve the feedback capacity; 2) a Kalman filter is optimal for processing the feedback information; 3) dynamic programming optimizes the Gauss-Markov source and computes the feedback capacity. Further, if the optimal Kalman filter reaches a steady state as the time k /spl rarr/ /spl infin/, then the asymptotic feedback capacity exists and its formula is given.

We address the question of convergence in the sum-product algorithm. Specifically, we relate convergence of the sum-product algorithm to the existence of a weak limit for a sequence of Gibbs measures defined on the associated computation tree. Using tools from the theory of Gibbs measures we develop easily testable sufficient conditions for convergence. The failure of convergence of the sum-product algorithm implies the existence of multiple phases for the associated Gibbs specification. These results give new insight into the mechanics of the algorithm.