Random Coordinate Descent for Resource Allocation in Open Multi-Agent Systems

We analyze the distributed random coordinate descent algorithm for solving separable resource allocation problems in the context of an open multi-agent system, where agents can be replaced during the process. First, we establish the linear convergence of the algorithm in closed systems, in terms of the estimate towards the minimizer, for general graphs and appropriate step-size. Next, we estimate the change of the optimal solution after a replacement to evaluate its effect on the distance between the estimate and the minimizer. From these two elements, we derive stability conditions in open systems and establish the linear convergence of the algorithm towards a steady state expected error. Our results allow characterizing the trade-off between speed of convergence and robustness to agent replacements, under the assumptions that local functions are smooth strongly convex and have their minimizers located in a given ball.