# Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters

arXiv: https://arxiv.org/abs/1602.02151 · HTML: https://mlsanity.com/paper/1602.02151/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2016.

## Built on by (most cited first, 6 of 6)

- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Adaptive Second Order Coresets for Data-efficient Machine Learning](https://mlsanity.com/paper/2207.13887/) (2022)
- [Efficient Coreset Selection via K-Nearest Neighbor Graphs](https://mlsanity.com/paper/2608.16270/) (2026)
- [Approximate Inference via Clustering](https://mlsanity.com/paper/2111.14219/) (2021)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)

## Abstract (arXiv)

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 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. Our accelerated algorithm ClusterACDM is built on a novel Haar transformation applied to the dual space of the ERM problem, and our variance-reduction based algorithm ClusterSVRG introduces a new gradient estimator using clustering. Our algorithms outperform their classical counterparts ACDM and SVRG respectively.