NDLI: The Impact of Stochastic Noisy Feedback on Distributed Network Utility Maximization

Content Provider	IEEE Xplore Digital Library
Author	Junshan Zhang Dong Zheng Mung Chiang
Copyright Year	1963
Abstract	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.
Sponsorship	IEEE Information Theory Society
Starting Page	645
Ending Page	665
Page Count	21
File Size	1515958
File Format	PDF
ISSN	00189448
Volume Number	54
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-02-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Stochastic processes Feedback Utility programs Stability Convergence Diffusion processes Fasteners Message passing Lagrangian functions Algorithm design and analysis two time-scale algorithm Multihop wireless networks network utility maximization noisy feedback primal-dual algorithm stochastic approximation stochastic networks
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Impact of Stochastic Noisy Feedback on Distributed Network Utility Maximization

Impact of stochastic noisy feedback on distributed network utility maximization (2007)

Impact of stochastic noisy feedback on distributed network utility maximization (2007)

An event-triggered distributed primal-dual algorithm for Network Utility maximization

Distributed wireless network utility maximization

A Stochastic Primal-Dual Algorithm for Joint Flow Control and MAC Design in Multi-hop Wireless Networks

Distributed power control in wireless ad hoc networks using message passing: Throughput optimality and network utility maximization

Congestion & power control of wireless multihop networks over stochastic LTF channels

On-line gossip-based distributed expectation maximization algorithm

The Impact of Stochastic Noisy Feedback on Distributed Network Utility Maximization

Similar Documents

The Impact of Stochastic Noisy Feedback on Distributed Network Utility Maximization

Impact of stochastic noisy feedback on distributed network utility maximization (2007)

Impact of stochastic noisy feedback on distributed network utility maximization (2007)

An event-triggered distributed primal-dual algorithm for Network Utility maximization

Distributed wireless network utility maximization

A Stochastic Primal-Dual Algorithm for Joint Flow Control and MAC Design in Multi-hop Wireless Networks

Distributed power control in wireless ad hoc networks using message passing: Throughput optimality and network utility maximization

Congestion & power control of wireless multihop networks over stochastic LTF channels

On-line gossip-based distributed expectation maximization algorithm

The Impact of Stochastic Noisy Feedback on Distributed Network Utility Maximization