A randomized primal distributed algorithm for partitioned and big-data non-convex optimization
It addresses distributed optimization in network settings where each node handles a small portion of a large variable, but the contribution is incremental as it adapts existing coordinate descent methods to asynchronous gossip communication.
The paper develops a randomized primal distributed algorithm for partitioned, big-data non-convex optimization, proving convergence to a stationary point and confirming effectiveness via simulations on a non-convex quadratic program.
In this paper we consider a distributed optimization scenario in which the aggregate objective function to minimize is partitioned, big-data and possibly non-convex. Specifically, we focus on a set-up in which the dimension of the decision variable depends on the network size as well as the number of local functions, but each local function handled by a node depends only on a (small) portion of the entire optimization variable. This problem set-up has been shown to appear in many interesting network application scenarios. As main paper contribution, we develop a simple, primal distributed algorithm to solve the optimization problem, based on a randomized descent approach, which works under asynchronous gossip communication. We prove that the proposed asynchronous algorithm is a proper, ad-hoc version of a coordinate descent method and thus converges to a stationary point. To show the effectiveness of the proposed algorithm, we also present numerical simulations on a non-convex quadratic program, which confirm the theoretical results.