Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks

By Amrit Singh Bedi, Alec Koppel, Ketan Rajawat. 2019

31 citations recorded by the source corpus.

We consider expected risk minimization in multi-agent systems comprised of distinct subsets of agents operating without a common time scale. Each individual in the network is charged with minimizing the global objective function, which is an average of sum of the statistical average loss function of each agent in the network. Since agents are not assumed to observe data from identical distributions, the hypothesis that all agents seek a common action is violated, and thus the hypothesis upon that consensus constraints are formulated is violated. Thus, we consider nonlinear network proximity constraints, which incentivize nearby nodes to make decisions that are close to one another but do not necessarily coincide. Moreover, agents are not assumed to receive their sequentially arriving observations on a common time index, and thus seek to learn in an asynchronous manner. An asynchronous stochastic variant of the Arrow–Hurwicz saddle point method is proposed to solve this problem that operates by alternating primal stochastic descent steps and Lagrange multiplier updates that penalize the discrepancies between agents. This tool leads to an implementation that allows for each agent to operate asynchronously with local information only and message passing with neighbors. Our main result establishes that the proposed method yields convergence in expectation both in terms of the primal sub-optimality and constraint violation to radii of sizes ${\mathcal O}(\sqrt{T})$ and ${\mathcal O}(T^{3/4})$, respectively. Empirical evaluation on an asynchronously operating wireless network that manages user channel interference through an adaptive communications pricing mechanism demonstrates that our theoretical results translates well to practice.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

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

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “…using the primal-dual based algorithms as in (Chang et al., 2014b; Touri and Nedic, 2009; Nedi´c and Ozdaglar, 2009), saddle point algorithms proposed in (Koppel et al., 2017; Bedi et al., 2019), and ADMM based techniques such as (Glowinski and Marroco, 1975; Boyd et al., 2011; Deng et al., 2017).”
The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “In a different line of research, constrained learning is also called stochastic optimization with expectation constraints (Yu et al., 2017; Bedi et al., 2019; Madavan & Bose, 2021; Akhtar et al., 2021).”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “In the distributed optimization literature, there are a variety of algorithms that are broadly categorized into primal meth-ods [27]–[30] and primal-dual methods [31]–[33].”
Conservative Stochastic Optimization With Expectation Constraints (2020, methodology): “Projection-based algorithms for solving (1) have been recently studied in [24]–[26], [28]–[31].”