Robust Coreset Construction for Distributed Machine Learning

• Main Authors: Lu, Hanlin, Li, Ming-Ju, He, Ting, Wang, Shiqiang, Narayanan, Vijaykrishnan, Chan, Kevin S.
• Format: Conference Proceeding
• Language: English
• Subjects: Approximation algorithms; Computational modeling; Cost function; Distributed databases; Machine learning; Machine learning algorithms; Partitioning algorithms
• ISSN: 2576-6813
• DOI: 10.1109/GLOBECOM38437.2019.9013625

Motivated by the need of solving machine learning problems over distributed datasets, we explore the use of \emph{coreset} to reduce the communication overhead. Coreset is a summary of the original dataset in the form of a small weighted set in the same sample space. Compared to other data summaries, coreset has the advantage that it can be used as a proxy of the original dataset. However, existing coreset construction algorithms are each tailor-made for a specific machine learning problem. Thus, to solve different machine learning problems, one has to collect coresets of different types, defeating the purpose of saving communication overhead. We resolve this dilemma by developing robust coreset construction algorithms based on k-means/median clustering, that give a provably good approximation for a broad range of machine learning problems with sufficiently continuous cost functions. Through evaluations on diverse datasets and machine learning problems, we verify the robust performance of the proposed algorithms.