Incremental Stochastic Subgradient Algorithms for Convex Optimization

By Sundhar Srinivasan Ram, Angelia Nedić, Venugopal V. Veeravalli. 2008

279 citations recorded by the source corpus.

This paper studies the effect of stochastic errors on two constrained incremental subgradient algorithms. The incremental subgradient algorithms are viewed 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. First, the standard cyclic incremental subgradient algorithm is studied. In this, the agents form a ring structure and pass the iterate in a cycle. When there are stochastic errors in the subgradient evaluations, sufficient conditions on the moments of the stochastic errors are obtained that guarantee almost sure convergence when a diminishing step-size is used. In addition, almost sure bounds on the algorithm's performance with a constant step-size are also obtained. Next, the Markov randomized incremental subgradient method is studied. This is a noncyclic version of the incremental algorithm where the sequence of computing agents is modeled as a time nonhomogeneous Markov chain. Such a model is appropriate for mobile networks, as the network topology changes across time in these networks. Convergence results and error bounds for the Markov randomized method in the presence of stochastic errors for diminishing and constant step-sizes are obtained.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Privacy Amplification by Decentralization (2020, methodology): “…walk that is suitably ergodic), this model of computation allows to optimize sums of local cost functions using (stochastic) gradient descent (Ram et al., 2009; Jo-hansson et al., 2009; Mao et al., 2020; Ayache and Rouayheb, 2020) (sometimes referred to as incremental gradient methods) and…”
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization (2008, methodology): “The effects of stochastic errors on these algorithms have been investigated in [3,9,14,17,23,24,27].”
Distributed Alternating Direction Method of Multipliers (2012, methodology): “1 In this sense, our proposed method is closely related to incremental distributed algorithms studied in the literature [2], [15], where each agent takes turn to update the system wide decision variable and passes the updated variable to the network.”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “Some earlier methods include distributed incremental (sub)gradient methods [37–39, 54 ] and incremental incremental proximal methods [ 3 , 68] , while a more recent Some distributed methods exist that do not (explicitly) use dual variables but can still converge to an exact consensual solution…”
Constrained Consensus and Optimization in Multi-Agent Networks (2008, background): “Most closely related to our work are the recent papers [12], [13], which proposed distributed subgradient methods for solving unconstrained multi-agent optimization problems.”
Asynchronous Broadcast-Based Convex Optimization Over a Network (2011, methodology): “However, wireless media is inherently broadcast and establishing bidirectional communications creates a bottleneck.”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, background): “The incremental algorithms [3,17–19,31,42] can solve (1) without the need of a “master” agent but requires that the network contains a ring structure.”
Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation (2017, methodology): “A stochastic incremental algorithm for solving (15) was first proposed in [13].”
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, methodology): “Randomized incremental subgradient methods with Markov jumps have also been developed for solving (40) with Ψ(w) = 0 (Johansson et al., 2009; Ram et al., 2009).”
A gossip algorithm for convex consensus optimization over networks (2010, background): “Furthermore, the algorithms mostly assume delay- and error-free communications with no quantization over directed graphs, although there are a few exceptions: [18] allowed the presence of bounded time delays, [28] considered random additive errors in subgradient evaluations, [20], [26] studied the e”
QD-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations (2012, background): “The existing literature on distributed optimization (see, for example, [36], [37], [38], [39], [40]) mostly consider static scenarios, in which, broadly the network goal is to minimize the sum (or average) of static (deterministic) local objectives, with each agent only aware of its local objective”
Asynchronous gossip algorithms for stochastic optimization (2009, methodology): “Each agent has a local clock that ticks at a Poisson rate4 of 1.”
Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions (2015, methodology): “The incremental subgradient algorithm is introduced as one of the earlier approaches addressing this problem [1], [2].”
Distributed subgradient projection algorithm for convex optimization (2009, methodology): “Then 1) limk→∞Φ(k, s) = 1m ee T for all s. 2) Further, the convergence is geometric and the rate of convergence is given by∣∣∣∣[Φ(k, s)]i,j − 1m ∣∣∣∣ ≤ θβk−s, where θ = ( 1− η4m2 )−2 and β = ( 1− η4m2 ) 1 Q .”
Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization (2011, unknown): “The so-called incremental approach is used by [18], [24], [27], [28], [31]: a message containing an estimate of the desired minimizer iteratively travels all over the network.”
Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds (2016, methodology): “, applications such as network optimization [21] or network control [16].”