Online Convex Optimization Over Erdos-Renyi Random Networks

The work studies how node-to-node communications over an Erdős-Rényi random network influence distributed online convex optimization, which is vital in solving large-scale machine learning in antagonistic or changing environments. At per step, each node (computing unit) makes a local decision, experiences a loss evaluated with a convex function, and communicates the decision with other nodes over a network. The node-to-node communications are described by the Erdős-Rényi rule, where independently each link takes place with a probability p over a prescribed connected graph. The objective is to minimize the system-wide loss accumulated over a finite time horizon. We consider standard distributed gradient descents with full gradients, one-point bandits and two-points bandits for convex and strongly convex losses, respectively. We establish how the regret bounds scale with respect to time horizon T , network size N , decision dimension d, and an algebraic network connectivity. The regret bounds scaling with respect to T match those obtained by state-of-the-art algorithms and fundamental limits in the corresponding centralized online optimization problems, e.g., O( √ T ) and O(ln(T )) regrets are established for convex and strongly convex losses with full gradient feedback and two-points information, respectively. For classical Erdős-Rényi networks over all-to-all possible node communications, the regret scalings with respect to the probability p are analytically established, based on which the tradeoff between the communication overhead and computation accuracy is clearly demonstrated. Numerical studies have validated the theoretical findings.