Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation

By Amrit Singh Bedi, Ketan Rajawat. 2017

32 citations recorded by the source corpus.

Stochastic network optimization problems entail finding resource allocation policies that are optimum on an average but must be designed in an online fashion. Such problems are ubiquitous in communication networks, where resources such as energy and bandwidth are divided among nodes to satisfy certain long-term objectives. This paper proposes an asynchronous incremental dual decent resource allocation algorithm that utilizes delayed stochastic gradients for carrying out its updates. The proposed algorithm is well-suited to heterogeneous networks as it allows the computationally-challenged or energy-starved nodes to, at times, postpone the updates. The asymptotic analysis of the proposed algorithm is carried out, establishing dual convergence under both, constant and diminishing step sizes. It is also shown that with constant step size, the proposed resource allocation policy is asymptotically near-optimal. An application involving multicell coordinated beamforming is detailed, demonstrating the usefulness of the proposed algorithm.

Subfields: Computational Mechanics, 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 Computational Mechanics

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): “A primal-dual decomposition method can solve this problem in a decentralized way (Bedi and Rajawat, 2018; Chang et al., 2014b; Jaggi et al., 2014), yet is not scalable since the constraint entails exponentially increasing communication rounds with N .”
Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks (2019, background): “On the other hand, the dual methods proposed in [21], [40]–[42] require a nonlinear minimization computation at each algorithm iteration, and thus is impractically costly.”