Existing approaches to federated learning suffer from a communication bottleneck as well as
convergence issues due to sparse client participation. In this paper we introduce a novel …

A coreset for a set of points is a small subset of weighted points that approximately
preserves important properties of the original set. Specifically, if $ P $ is a set of points, $ Q …

In large scale machine learning, random sampling is a popular way to approximate datasets
by a small representative subset of examples. In particular, sensitivity sampling is an …

In the adversarially robust streaming model, a stream of elements is presented to an
algorithm and is allowed to depend on the output of the algorithm at earlier times during the …

Robustness against adversarial attacks has recently been at the forefront of algorithmic
design for machine learning tasks. In the adversarial streaming model, an adversary gives …

The seminal work of Cohen and Peng [CP15](STOC 2015) introduced Lewis weight
sampling to the theoretical computer science community, which yields fast row sampling …

Subset selection for the rank k approximation of an n× d matrix A offers improvements in the
interpretability of matrices, as well as a variety of computational savings. This problem is well …

We consider the classic Euclidean k-median and k-means objective on data streams, where
the goal is to provide a (1+ε)-approximation to the optimal k-median or k-means solution …

We give relative error coresets for training linear classifiers with a broad class of loss
functions, including the logistic loss and hinge loss. Our construction achieves …

Clustering is an important technique for identifying structural information in large-scale data
analysis, where the underlying dataset may be too large to store. In many applications …