  We consider the setting of agents cooperatively minimizing the sum of local
objectives plus a regularizer on a graph. This paper proposes a primal-dual
method in consideration of three distinctive attributes of real-life
multi-agent systems, namely: (i)expensive communication, (ii)lack of
synchronization, and (iii)system heterogeneity. In specific, we propose a
distributed asynchronous algorithm with minimal communication cost, in which
users commit variable amounts of local work on their respective sub-problems.
We illustrate this both theoretically and experimentally in the machine
learning setting, where the agents hold private data and use a stochastic
Newton method as the local solver. Under standard assumptions on Lipschitz
continuous gradients and strong convexity, our analysis establishes linear
convergence in expectation and characterizes the dependency of the rate on the
number of local iterations. We proceed a step further to propose a simple means
for tuning agents' hyperparameters locally, so as to adjust to heterogeneity
and accelerate the overall convergence. Last, we validate our proposed method
on a benchmark machine learning dataset to illustrate the merits in terms of
computation, communication, and run-time saving as well as adaptability to
heterogeneity.
