Communication Efficient Coresets for Empirical Loss Minimization

Sashank Jakkam Reddi Carnegie Mellon University, Barnabas Poczos Alex Smola
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:437-446, 2015.

Abstract

In this paper, we study the problem of empirical loss minimization with l2-regularization in distributed settings with significant communication cost. Stochastic gradient descent (SGD) and its variants are popular techniques for solving these problems in large-scale applications. However, the communication cost of these techniques is usually high, thus leading to considerable performance degradation. We introduce a novel approach to reduce the communication cost while retaining good convergence properties. The key to our approach is the construction of a small summary of the data, called coreset, at each iteration and solve an easy optimization problem based on the coreset. We present a general framework for analyzing coreset-based optimization and provide interesting insights into existing algorithms from this perspective. We then propose a new coreset construction and provide its convergence analysis for a wide class of problems that include logistic regression and support vector machines. We demonstrate the performance of our algorithm on real-world datasets and compare it against state-of-the-art algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-university15h, title = {Communication Efficient Coresets for Empirical Loss Minimization}, author = {University, Sashank Jakkam Reddi Carnegie Mellon and Smola, Barnabas Poczos Alex}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {437--446}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/university15h/university15h.pdf}, url = {https://proceedings.mlr.press/r13/university15h.html}, abstract = {In this paper, we study the problem of empirical loss minimization with l2-regularization in distributed settings with significant communication cost. Stochastic gradient descent (SGD) and its variants are popular techniques for solving these problems in large-scale applications. However, the communication cost of these techniques is usually high, thus leading to considerable performance degradation. We introduce a novel approach to reduce the communication cost while retaining good convergence properties. The key to our approach is the construction of a small summary of the data, called coreset, at each iteration and solve an easy optimization problem based on the coreset. We present a general framework for analyzing coreset-based optimization and provide interesting insights into existing algorithms from this perspective. We then propose a new coreset construction and provide its convergence analysis for a wide class of problems that include logistic regression and support vector machines. We demonstrate the performance of our algorithm on real-world datasets and compare it against state-of-the-art algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Communication Efficient Coresets for Empirical Loss Minimization %A Sashank Jakkam Reddi Carnegie Mellon University %A Barnabas Poczos Alex Smola %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-university15h %I PMLR %P 437--446 %U https://proceedings.mlr.press/r13/university15h.html %V R13 %X In this paper, we study the problem of empirical loss minimization with l2-regularization in distributed settings with significant communication cost. Stochastic gradient descent (SGD) and its variants are popular techniques for solving these problems in large-scale applications. However, the communication cost of these techniques is usually high, thus leading to considerable performance degradation. We introduce a novel approach to reduce the communication cost while retaining good convergence properties. The key to our approach is the construction of a small summary of the data, called coreset, at each iteration and solve an easy optimization problem based on the coreset. We present a general framework for analyzing coreset-based optimization and provide interesting insights into existing algorithms from this perspective. We then propose a new coreset construction and provide its convergence analysis for a wide class of problems that include logistic regression and support vector machines. We demonstrate the performance of our algorithm on real-world datasets and compare it against state-of-the-art algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
University, S.J.R.C.M. & Smola, B.P.A.. (2015). Communication Efficient Coresets for Empirical Loss Minimization. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:437-446 Available from https://proceedings.mlr.press/r13/university15h.html. Reissued by PMLR on 04 October 2026.

Related Material