Distributed Asynchronous Constrained Stochastic Optimization

被引:256
作者
Srivastava, Kunal [1 ]
Nedic, Angelia [1 ]
机构
[1] Univ Illinois, Ind & Enterprise Syst Engn ISE Dept, Urbana, IL 61801 USA
基金
美国国家科学基金会;
关键词
Asynchronous model; distributed optimization; multiagent system; noisy communications; stochastic optimization; CONSENSUS ALGORITHMS; NETWORKS;
D O I
10.1109/JSTSP.2011.2118740
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
In this paper, we study two problems which often occur in various applications arising in wireless sensor networks. These are the problem of reaching an agreement on the value of local variables in a network of computational agents and the problem of cooperative solution to a convex optimization problem, where the objective function is the aggregate sum of local convex objective functions. We incorporate the presence of a random communication graph between the agents in our model as a more realistic abstraction of the gossip and broadcast communication protocols of a wireless network. An added ingredient is the presence of local constraint sets to which the local variables of each agent is constrained. Our model allows for the objective functions to be nondifferentiable and accommodates the presence of noisy communication links and subgradient errors. For the consensus problem we provide a diminishing step size algorithm which guarantees asymptotic convergence. The distributed optimization algorithm uses two diminishing step size sequences to account for communication noise and subgradient errors. We establish conditions on these step sizes under which we can achieve the dual task of reaching consensus and convergence to the optimal set with probability one. In both cases we consider the constant step size behavior of the algorithm and establish asymptotic error bounds.
引用
收藏
页码:772 / 790
页数:19
相关论文
共 45 条
[1]   A Distributed Machine Learning Framework [J].
Alpcan, Tansu ;
Bauckhage, Christian .
PROCEEDINGS OF THE 48TH IEEE CONFERENCE ON DECISION AND CONTROL, 2009 HELD JOINTLY WITH THE 2009 28TH CHINESE CONTROL CONFERENCE (CDC/CCC 2009), 2009, :2546-2551
[2]  
[Anonymous], IEEE T AUTO IN PRESS
[3]  
[Anonymous], 2800 LIDS MIT
[4]  
[Anonymous], P INF THEOR APPL WOR
[5]  
[Anonymous], 1967, COMP MATH MATH PHYS+
[6]  
[Anonymous], ARXIV10051292V1MATHO
[7]  
[Anonymous], MSRTR201023
[8]  
[Anonymous], 2009, MARKOV CHAINS STOCHA
[9]  
[Anonymous], DISTRIBUTED PARAMETE
[10]  
[Anonymous], P 46 IEEE C DEC CONT