TY - GEN
T1 - Asynchronous Dual Free Stochastic Dual Coordinate Ascent for Distributed Data Mining
AU - Huo, Zhouyuan
AU - Jiang, Xue
AU - Huang, Heng
PY - 2018/11/17
Y1 - 2018/11/17
N2 - The primal-dual distributed computational methods have broad large-scale data mining 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 novel distributed asynchronous dual free stochastic dual coordinate ascent algorithm for distributed data mining. Our method does not need the dual formulation of the target problem in the computation. 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.
AB - The primal-dual distributed computational methods have broad large-scale data mining 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 novel distributed asynchronous dual free stochastic dual coordinate ascent algorithm for distributed data mining. Our method does not need the dual formulation of the target problem in the computation. 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.
UR - https://openir.whu.edu.cn/AchievementDetail/WOS_3bf9df89-06f5-4534-84ea-9334647f358a
U2 - 10.1109/icdm.2018.00032
DO - 10.1109/icdm.2018.00032
M3 - Conference contribution
SN - 0769517544
SN - 0769527019
SN - 0769530192
SN - 9780769527024
SN - 9780769530185
SN - 9780769530192
SN - 9780769542560
SN - 9781665423984
SN - 9781665450997
SN - 9781728183169
T3 - IEEE International Conference on Data Mining
SP - 167
EP - 176
BT - 2018 IEEE INTERNATIONAL CONFERENCE ON DATA MINING (ICDM)
PB - Institute of Electrical and Electronics Engineers Inc.
ER -