BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees

Abstract

The rising volume of datasets has made training machine learning (ML) models a major computational cost in the enterprise. Given the iterative nature of model and parameter tuning, many analysts use a small sample of their entire data during their initial stage of analysis to make quick decisions (e.g., what features or hyperparameters to use) and use the entire dataset only in later stages (i.e., when they have converged to a specific model). This sampling, however, is performed in an ad-hoc fashion. Most practitioners cannot precisely capture the effect of sampling on the quality of their model, and eventually on their decision-making process during the tuning phase. Moreover, without systematic support for sampling operators, many optimizations and reuse opportunities are lost. In this paper, we introduce BlinkML, a system for fast, quality-guaranteed ML training. BlinkML allows users to make error-computation tradeoffs: instead of training a model on their full data (i.e., full model), BlinkML can quickly train an approximate model with quality guarantees using a sample. The quality guarantees ensure that, with high probability, the approximate model makes the same predictions as the full model. BlinkML currently supports any ML model that relies on maximum likelihood estimation (MLE), which includes Generalized Linear Models (e.g., linear regression, logistic regression, max entropy classifier, Poisson regression) as well as PPCA (Probabilistic Principal Component Analysis). Our experiments show that BlinkML can speed up the training of large-scale ML tasks by 6.26x-629x while guaranteeing the same predictions, with 95% probability, as the full model.

22 pages, SIGMOD 2019

References in corpus (17)

• Adam: A Method for Stochastic Optimization
• Scikit-learn: Machine Learning in Python
• ADADELTA: An Adaptive Learning Rate Method
• Searching for Exotic Particles in High-Energy Physics with Deep Learning
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Sketching as a Tool for Numerical Linear Algebra
• Gradient-based Hyperparameter Optimization through Reversible Learning
• Optimal Subsampling for Large Sample Logistic Regression
• Fast approximation of matrix coherence and statistical leverage
• Measuring the Effects of Data Parallelism on Neural Network Training
• VerdictDB: Universalizing Approximate Query Processing
• Clipper: A Low-Latency Online Prediction Serving System
• Revisiting the Nystrom Method for Improved Large-Scale Machine Learning
• Database Learning: Toward a Database that Becomes Smarter Every Time
• Omnivore: An Optimizer for Multi-device Deep Learning on CPUs and GPUs
• Hemingway: Modeling Distributed Optimization Algorithms
• Asynchronous Complex Analytics in a Distributed Dataflow Architecture

Cited by in corpus (5)

• Approximate Computing Survey, Part II: Application-Specific & Architectural Approximation Techniques and Applications
• Computationally efficient univariate filtering for massive data
• Machine Learning Systems for Intelligent Services in the IoT: A Survey
• The Relational Data Borg is Learning
• Machine Learning over Static and Dynamic Relational Data