TY - JOUR
T1 - Communication-Efficient k-Means for Edge-Based Machine Learning
AU - Lu, Hanlin
AU - He, Ting
AU - Wang, Shiqiang
AU - Liu, Changchang
AU - Mahdavi, Mehrdad
AU - Narayanan, Vijaykrishnan
AU - Chan, Kevin S.
AU - Pasteris, Stephen
N1 - Publisher Copyright:
© 1990-2012 IEEE.
PY - 2022/10/1
Y1 - 2022/10/1
N2 - We consider the problem of computing the 'k'k-means centers for a large high-dimensional dataset in the context of edge-based machine learning, where data sources offload machine learning computation to nearby edge servers. 'k'k-Means computation is fundamental to many data analytics, and the capability of computing provably accurate 'k'k-means centers by leveraging the computation power of the edge servers, at a low communication and computation cost to the data sources, will greatly improve the performance of these analytics. We propose to let the data sources send small summaries, generated by joint dimensionality reduction (DR), cardinality reduction (CR), and quantization (QT), to support approximate 'k'k-means computation at reduced complexity and communication cost. By analyzing the complexity, the communication cost, and the approximation error of 'k'k-means algorithms based on carefully designed composition of DR/CR/QT methods, we show that: (i) it is possible to compute near-optimal 'k'k-means centers at a near-linear complexity and a constant or logarithmic communication cost, (ii) the order of applying DR and CR significantly affects the complexity and the communication cost, and (iii) combining DR/CR methods with a properly configured quantizer can further reduce the communication cost without compromising the other performance metrics. Our theoretical analysis has been validated through experiments based on real datasets.
AB - We consider the problem of computing the 'k'k-means centers for a large high-dimensional dataset in the context of edge-based machine learning, where data sources offload machine learning computation to nearby edge servers. 'k'k-Means computation is fundamental to many data analytics, and the capability of computing provably accurate 'k'k-means centers by leveraging the computation power of the edge servers, at a low communication and computation cost to the data sources, will greatly improve the performance of these analytics. We propose to let the data sources send small summaries, generated by joint dimensionality reduction (DR), cardinality reduction (CR), and quantization (QT), to support approximate 'k'k-means computation at reduced complexity and communication cost. By analyzing the complexity, the communication cost, and the approximation error of 'k'k-means algorithms based on carefully designed composition of DR/CR/QT methods, we show that: (i) it is possible to compute near-optimal 'k'k-means centers at a near-linear complexity and a constant or logarithmic communication cost, (ii) the order of applying DR and CR significantly affects the complexity and the communication cost, and (iii) combining DR/CR methods with a properly configured quantizer can further reduce the communication cost without compromising the other performance metrics. Our theoretical analysis has been validated through experiments based on real datasets.
UR - http://www.scopus.com/inward/record.url?scp=85123682068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85123682068&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2022.3144595
DO - 10.1109/TPDS.2022.3144595
M3 - Article
AN - SCOPUS:85123682068
SN - 1045-9219
VL - 33
SP - 2509
EP - 2523
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 10
ER -