Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters
By Zeyuan Allen-Zhu, Yang Yuan, Karthik Sridharan. 2016
29 citations recorded by the source corpus.
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. 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.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Jakub Konecný
- Peter Richtárik
- H. Brendan McMahan
- Daniel Ramage
- Martin Jaggi
- Virginia Smith
- Nicolas Loizou
- Qiang Yang
Citations in the corpus
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “SVRG can be further accelerated via a raw clustering mechanism [4].”
- Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “SVRG can be further accelerated via a raw clustering mechanism [6].”
- Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “Very recently, (Hofmann et al., 2015; Allen-Zhu et al., 2016) exploited neighborhood structure to further reduce the variance of stochastic gradient descent and improve its running time.”