Abstract. In this paper we study the effect of stochastic errors on two constrained incremental sub-gradient algorithms. We view the incremental sub-gradient algorithms as decentralized network optimization algorithms as applied to minimize a sum of functions, when each component function is known only to a particular agent of a distributed network. We first study the standard cyclic incremental sub-gradient algorithm in which the agents form a ring structure and pass the iterate in a cycle. We consider the method with stochastic errors in the sub-gradient evaluations and provide sufficient conditions on the moments of the stochastic errors that guarantee almost sure convergence when a diminishing step-size is used. We also obtain almost sure bounds on the algorithm's performance when a constant step-size is used. We then consider the Markov randomized incremental subgradient method, which is a non-cyclic version of the incremental algorithm where the sequence of computing agents is modeled as a time non-homogeneous Markov chain. Such a model is appropriate for mobile networks, as the network topology changes across time in these networks. We establish the convergence results and error bounds for the Markov randomized method in the presence of stochastic errors for diminishing and constant step-sizes, respectively. A problem of recent interest in distributed networks is the design of decentralized algorithms to minimize a sum of functions, when each component function is known only to a particular agent [4, 9, 20, 24, 29] . Such problems arise in many network applications, including in-network estimation, learning, signal processing and resource allocation [6, 16, [28] [29] [30] [31] . In these applications, there is no central coordinator that has access to all the information and, thus, decentralized algorithms are needed to solve the problems. In this paper, we consider decentralized subgradient methods for constrained minimization of a sum of convex functions, when each component function is only known partially (with stochastic errors) to a specific network agent. We study two incremental subgradient methods with stochastic errors: a cyclic and a (non-cyclic) Markov randomized incremental method. The cyclic incremental algorithm is a decentralized method in which the network agents form a ring and process the information cyclically. The incremental method was originally proposed by Kibardin [11] and has been extensively studied more recently in [4, 7, 17, 20, 33] . Incremental gradient algorithms were first used for optimizing the weights in neural network training [7, 17, 33] , and most of the associated literature deals with differentiable non-convex unconstrained optimization problems [3, 4, 7, 33, 34] . The incremental subgradient algorithm for non-differentiable constrained convex optimization has been investigated in [19,20] without errors, and in [13,21,29,34] where the effects of deterministic errors are considered. The algorithm that we consider in this paper is stochastic and as such differs from the existing literature. For this algorithm, we establish convergence for diminishing step-size and provide an error bound for constant step-size. The Markov randomized incremental algorithm is a decentralized method where the iterates are generated incrementally within the network by passing them from agent to agent. Unlike the cyclic incremental method, where the agent network has a ring structure and the information flow is along this ring (cycle), in the Markov
The asymptotic analysis of dual problem in the present work follows the same general outline as that of the cyclic incremental algorithm in REF , with additional modifications introduced to handle asynchrony.
Incremental Stochastic Subgradient Algorithms for Convex Optimization
arXiv: Optimization and Control
Computer Science Mathematics