Distributed optimization algorithms have been widely used in large scale machine learning problems [[1]}, [2]}, [3]}]. The benefit of distributed algorithms is two-folded. Firstly, by distributing the workload to local data centers, distributed optimization algorithms could potentially reduce the required computation time from parallel computing and processing. A salient feature of most machine learning problems is that the objectives are separable, and distributed optimization algorithms could exploit the benefit of having separable objectives. Secondly, distributed optimization algorithms are preferred when there are data security and privacy related concerns. However, in practice, distributed optimization algorithms often suffer from slow convergence to the target tolerance level when applied to large scale machine learning problems [[4]}, [5]}]. This work aims at providing a theoretical answer to the following questions: why distributed optimization algorithms can sometimes have unsatisfactory performance, and what kind of data distribution leads to such slow convergence. With theoretical guidance, this paper provides a meta data-sharing algorithm that only requires a small amount of pre-fixed sampled data to build a global data pool. And we show that only a small amount of data share is sufficient to improve the convergence speed for different distributed optimization algorithms. With tailored design on utilizing the shared data to different distributed algorithms, we are able to enjoy both the benefit from faster convergence from data sharing, and from parallel computing by keeping the main structure of the optimization algorithms closer to a distributed manner. In this paper, we mainly focus on multi-block distributed Alternating Direction Method of Multipliers (ADMM) and preconditioned conjugate gradient methods (PCG), which are both known for lying in between the first order gradient descent method and the second order newton methods. We also apply our algorithms to machine learning problems including least square and logistic regressions.
