Tradeoffs for Space, Time, Data and Risk in Unsupervised Learning

2016/05/02 by Mario Lučić, Lucic, Mario, Mesrob I. Ohannessian +5
Computer Science · #Machine Learning and Algorithms #Bayesian Methods and Mixture Models #Gaussian Processes and Bayesian Inference

paper · pdf · doi:10.48550/arxiv.1605.00529

Abstract

Faced with massive data, is it possible to trade off (statistical) risk, and (computational) space and time? This challenge lies at the heart of large-scale machine learning. Using k-means clustering as a prototypical unsupervised learning problem, we show how we can strategically summarize the data (control space) in order to trade off risk and time when data is generated by a probabilistic model. Our summarization is based on coreset constructions from computational geometry. We also develop an algorithm, TRAM, to navigate the space/time/data/risk tradeoff in practice. In particular, we show that for a fixed risk (or data size), as the data size increases (resp. risk increases) the running time of TRAM decreases. Our extensive experiments on real data sets demonstrate the existence and practical utility of such tradeoffs, not only for k-means but also for Gaussian Mixture Models.

Citations

• Least squares quantization in PCM
• Moment-based Uniform Deviation Bounds for k-means and Friends
• An efficient k-means clustering algorithm: analysis and implementation

Cited by

• Strong Coresets for Hard and Soft Bregman Clustering with Applications\n to Exponential Family Mixtures
• Starting Small -- Learning with Adaptive Sample Sizes
• Coresets for Kinematic Data: From Theorems to Real-Time Systems

Related

• Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters
• Supervising Unsupervised Learning
• Big-Data Clustering: K-Means or K-Indicators?
• Robust Unsupervised Learning via L-Statistic Minimization
• Efficient Methods for Unsupervised Learning of Probabilistic Models