Decentralized optimization with non-identical sampling in presence of stragglers
This work addresses optimization challenges in distributed systems with heterogeneous data and slow nodes, but it is incremental as it combines previously studied problems without introducing a new optimal method.
The paper tackles decentralized consensus optimization with non-identical data distributions and stragglers, proving convergence for two heuristic weighting methods under perfect consensus and showing that weighting by work completed outperforms equal weighting in numerical experiments for convex and non-convex functions.
We consider decentralized consensus optimization when workers sample data from non-identical distributions and perform variable amounts of work due to slow nodes known as stragglers. The problem of non-identical distributions and the problem of variable amount of work have been previously studied separately. In our work we analyze them together under a unified system model. We study the convergence of the optimization algorithm when combining worker outputs under two heuristic methods: (1) weighting equally, and (2) weighting by the amount of work completed by each. We prove convergence of the two methods under perfect consensus, assuming straggler statistics are independent and identical across all workers for all iterations. Our numerical results show that under approximate consensus the second method outperforms the first method for both convex and non-convex objective functions. We make use of the theory on minimum variance unbiased estimator (MVUE) to evaluate the existence of an optimal method for combining worker outputs. While we conclude that neither of the two heuristic methods are optimal, we also show that an optimal method does not exist.