  Empirical risk minimization is perhaps the most influential idea in
statistical learning, with applications to nearly all scientific and technical
domains in the form of regression and classification models. To analyze massive
streaming datasets in distributed computing environments, practitioners
increasingly prefer to deploy regression models on edge rather than in the
cloud. By keeping data on edge devices, we minimize the energy, communication,
and data security risk associated with the model. Although it is equally
advantageous to train models at the edge, a common assumption is that the model
was originally trained in the cloud, since training typically requires
substantial computation and memory. To this end, we propose STORM, an online
sketch for empirical risk minimization. STORM compresses a data stream into a
tiny array of integer counters. This sketch is sufficient to estimate a variety
of surrogate losses over the original dataset. We provide rigorous theoretical
analysis and show that STORM can estimate a carefully chosen surrogate loss for
the least-squares objective. In an exhaustive experimental comparison for
linear regression models on real-world datasets, we find that STORM allows
accurate regression models to be trained.
