Title: Time Complexity Analysis of a Distributed Stochastic Optimization in a Non-Stationary Environment,
Abstract: In this paper, we consider a distributed stochastic optimization problem
where the goal is to minimize the time average of a cost function subject to a
set of constraints on the time averages of related stochastic processes called
penalties. We assume that the state of the system is evolving in an independent
and non-stationary fashion and the "common information" available at each node
is distributed and delayed. Such stochastic optimization is an integral part of
many important problems in wireless networks such as scheduling, routing,
resource allocation and crowd sensing. We propose an approximate distributed
Drift- Plus-Penalty (DPP) algorithm, and show that it achieves a time average
cost (and penalties) that is within epsilon > 0 of the optimal cost (and
constraints) with high probability. Also, we provide a condition on the
convergence time t for this result to hold. In particular, for any delay D >= 0
in the common information, we use a coupling argument to prove that the
proposed algorithm converges almost surely to the optimal solution. We use an
application from wireless sensor network to corroborate our theoretical
findings through simulation results.