TY - JOUR
T1 - The impact of stochastic noisy feedback on distributed network utility maximization
AU - Zhang, Junshan
AU - Zheng, Dong
AU - Chiang, Mung
N1 - Funding Information:
Manuscript received February 8, 2007; revised July 18, 2007. This research is supported in part by Office of Naval Research through the Grant N00014-05-1-0636 and National Science Foundation through the Grants ANI-0238550 and CNS-0721820. J. Zhang is with the Department of Electrical Engineering, Ira A. Fulton School of Engineering, Arizona State University, Tempe, AZ 85287 USA (e-mail: [email protected]). D. Zheng is with NextWave Broadband Inc., San Deigo, CA 92130 USA (e-mail: [email protected]). M. Chiang is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]). Communicated by E. Modiano, Associate Editor for Communication Networks. Color versions of Figures 2–11 in this paper are available at http:\\ieeexplore. ieee.org. Digital Object Identifier 10.1109/TIT.2007.913572
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2008/2
Y1 - 2008/2
N2 - The implementation of distributed network utility maximization (NUM) algorithms hinges heavily on information feedback through message passing among network elements. In practical systems the feedback is often obtained using error-prone measurement mechanisms and suffers from random errors. In this paper, we investigate the impact of noisy feedback on distributed NUM. We first study the distributed NUM algorithms based on the Lagrangian dual method, and focus on the primal-dual (P-D) algorithm, which is a single time-scale algorithm in the sense that the primal and dual parameters are updated simultaneously. Assuming strong duality, we study both cases when the stochastic gradients are unbiased or biased, and develop a general theory on the stochastic stability of the P-D algorithms in the presence of noisy feedback. When the gradient estimators are unbiased, we establish, via a combination of tools in Martingale theory and convex analysis, that the iterates generated by distributed P-D algorithms converge with probability one to the optimal point, under standard technical conditions. In contrast, when the gradient estimators are biased, we show that the iterates converge to a contraction region around the optimal point, provided that the biased terms are asymptotically bounded by a scaled version of the true gradients. We also investigate the rate of convergence for the unbiased case, and find that, in general, the limit process of the interpolated process corresponding to the normalized iterate sequence is a stationary reflected linear diffusion process, not necessarily a Gaussian diffusion process. We apply the above general theory to investigate stability of cross-layer rate control for joint congestion control and random access. Next, we study the impact of noisy feedback on distributed two time-scale NUM algorithms based on primal decomposition. We establish, via the mean ODE method, the convergence of the stochastic two time-scale algorithm under mild conditions, for the cases where the gradient estimators in both time scales are unbiased. Numerical examples are used to illustrate the finding that compared to the single time-scale counterpart, the two time-scale algorithm, although having lower complexity, is less robust to noisy feedback.
AB - The implementation of distributed network utility maximization (NUM) algorithms hinges heavily on information feedback through message passing among network elements. In practical systems the feedback is often obtained using error-prone measurement mechanisms and suffers from random errors. In this paper, we investigate the impact of noisy feedback on distributed NUM. We first study the distributed NUM algorithms based on the Lagrangian dual method, and focus on the primal-dual (P-D) algorithm, which is a single time-scale algorithm in the sense that the primal and dual parameters are updated simultaneously. Assuming strong duality, we study both cases when the stochastic gradients are unbiased or biased, and develop a general theory on the stochastic stability of the P-D algorithms in the presence of noisy feedback. When the gradient estimators are unbiased, we establish, via a combination of tools in Martingale theory and convex analysis, that the iterates generated by distributed P-D algorithms converge with probability one to the optimal point, under standard technical conditions. In contrast, when the gradient estimators are biased, we show that the iterates converge to a contraction region around the optimal point, provided that the biased terms are asymptotically bounded by a scaled version of the true gradients. We also investigate the rate of convergence for the unbiased case, and find that, in general, the limit process of the interpolated process corresponding to the normalized iterate sequence is a stationary reflected linear diffusion process, not necessarily a Gaussian diffusion process. We apply the above general theory to investigate stability of cross-layer rate control for joint congestion control and random access. Next, we study the impact of noisy feedback on distributed two time-scale NUM algorithms based on primal decomposition. We establish, via the mean ODE method, the convergence of the stochastic two time-scale algorithm under mild conditions, for the cases where the gradient estimators in both time scales are unbiased. Numerical examples are used to illustrate the finding that compared to the single time-scale counterpart, the two time-scale algorithm, although having lower complexity, is less robust to noisy feedback.
KW - Multihop wireless networks
KW - Network utility maximization
KW - Noisy feedback
KW - Primal-dual algorithm
KW - Stochastic approximation
KW - Stochastic networks
KW - Two time-scale algorithm
UR - http://www.scopus.com/inward/record.url?scp=39849102649&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=39849102649&partnerID=8YFLogxK
U2 - 10.1109/TIT.2007.913572
DO - 10.1109/TIT.2007.913572
M3 - Article
AN - SCOPUS:39849102649
SN - 0018-9448
VL - 54
SP - 645
EP - 665
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 2
ER -