Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters

Understand

The amount of data available in the world is growing faster than our ability to deal with it.

• However, if we take advantage of the internal \emph{structure}, data may become much smaller for machine learning purposes.
• In this paper we focus on one of the fundamental machine learning tasks, empirical risk minimization (ERM), and provide faster algorithms with the help from the clustering structure of the data.
• We introduce a simple notion of raw clustering that can be efficiently computed from the data, and propose two algorithms based on clustering information.