A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems

TLDR

The algorithm is designed for distributed implementation, making it suitable for tasks such as parameter estimation in networks of tiny wireless sensors. The paper introduces a generalized randomized incremental subgradient method with fixed step size, extending the Nedić and Bertsekas framework. It employs a Markov‑chain–based stochastic component that can be constructed locally, and the authors analyze its convergence and compare it to existing deterministic and randomized incremental subgradient methods. Reference: Nedić and Bertsekas, SIAM J.

Abstract

We present an algorithm that generalizes the randomized incremental subgradient method with fixed stepsize due to Nedić and Bertsekas [SIAM J. Optim., 12 (2001), pp. 109–138]. Our novel algorithm is particularly suitable for distributed implementation and execution, and possible applications include distributed optimization, e.g., parameter estimation in networks of tiny wireless sensors. The stochastic component in the algorithm is described by a Markov chain, which can be constructed in a distributed fashion using only local information. We provide a detailed convergence analysis of the proposed algorithm and compare it with existing, both deterministic and randomized, incremental subgradient methods.