Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
This work addresses practical challenges in large-scale machine learning by enabling distributed optimization without dual formulations and mitigating slowdowns from slow machines, though it is incremental as it builds on existing stochastic dual coordinate ascent methods.
The paper tackles the issues of dual formulation unavailability and straggler problems in distributed optimization by proposing a distributed asynchronous dual-free stochastic dual coordinate ascent algorithm, achieving linear convergence rates even for non-convex functions and validating results with experiments on convex and non-convex losses.
The primal-dual distributed optimization methods have broad large-scale machine learning applications. Previous primal-dual distributed methods are not applicable when the dual formulation is not available, e.g. the sum-of-non-convex objectives. Moreover, these algorithms and theoretical analysis are based on the fundamental assumption that the computing speeds of multiple machines in a cluster are similar. However, the straggler problem is an unavoidable practical issue in the distributed system because of the existence of slow machines. Therefore, the total computational time of the distributed optimization methods is highly dependent on the slowest machine. In this paper, we address these two issues by proposing distributed asynchronous dual free stochastic dual coordinate ascent algorithm for distributed optimization. Our method does not need the dual formulation of the target problem in the optimization. We tackle the straggler problem through asynchronous communication and the negative effect of slow machines is significantly alleviated. We also analyze the convergence rate of our method and prove the linear convergence rate even if the individual functions in objective are non-convex. Experiments on both convex and non-convex loss functions are used to validate our statements.