  Distributed optimization algorithms have been widely used in machine
learning. While those algorithms have the merits in parallel processing and
protecting data security, they often suffer from slow convergence. This paper
focuses on how a small amount of data sharing could benefit distributed
optimization and learning. Specifically, we examine higher-order optimization
algorithms including distributed multi-block alternating direction method of
multipliers (ADMM) and preconditioned conjugate gradient method (PCG). The
contribution of this paper is three-folded. First, in theory, we answer when
and why distributed optimization algorithms are slow by identifying the worst
data structure. Surprisingly, while PCG algorithm converges slowly under
heterogeneous data structure, for distributed ADMM, data homogeneity leads to
the worst performance. This result challenges the common belief that data
heterogeneity hurts convergence, highlighting the need for a universal approach
on altering data structure for different algorithms. Second, in practice, we
propose a meta-algorithm of data sharing, with its tailored applications in
multi-block ADMM and PCG methods. By only sharing a small amount of prefixed
data (e.g. 1%), our algorithms provide good quality estimators in different
machine learning tasks within much fewer iterations, while purely distributed
optimization algorithms may take hundreds more times of iterations to converge.
Finally, in philosophy, we argue that even minimal collaboration can have huge
synergy, which is a concept that extends beyond the realm of optimization
analysis. We hope that the discovery resulting from this paper would encourage
even a small amount of data sharing among different regions to combat difficult
global learning problems.
