# NURD: Negative-Unlabeled Learning for Online Datacenter Straggler Prediction

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 84 references that are in the map.
- First posted on arXiv 16 Mar 2022.

## Builds on (most cited first, 17 of 17)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [PyOD: A Python Toolbox for Scalable Outlier Detection](https://mlsanity.com/paper/1901.01588/) (2019)
- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [Learning from positive and unlabeled data: a survey](https://mlsanity.com/paper/1811.04820/) (2018)
- [XGBOD: Improving Supervised Outlier Detection with Unsupervised Representation Learning](https://mlsanity.com/paper/1912.00290/) (2019)
- [LSCP: Locally Selective Combination in Parallel Outlier Ensembles](https://mlsanity.com/paper/1812.01528/) (2018)
- [A polynomial-time algorithm for learning nonparametric causal graphs](https://mlsanity.com/paper/2006.11970/) (2020)
- [Interpretable, Multidimensional, Multimodal Anomaly Detection with Negative Sampling for Detection of Device Failure](https://mlsanity.com/paper/2007.10088/) (2020)
- [Multiresolution Kernel Approximation for Gaussian Process Regression](https://mlsanity.com/paper/1708.02183/) (2017)
- [Grabit: Gradient Tree-Boosted Tobit Models for Default Prediction](https://mlsanity.com/paper/1711.08695/) (2017)
- [A Survey of Machine Learning Applied to Computer Architecture Design](https://mlsanity.com/paper/1909.12373/) (2019)
- [CAFQA: A classical simulation bootstrap for variational quantum algorithms](https://mlsanity.com/paper/2202.12924/) (2022)
- [A Zero-Positive Learning Approach for Diagnosing Software Performance Regressions](https://mlsanity.com/paper/1709.07536/) (2017)
- [Dynamical systems theory for causal inference with application to synthetic control methods](https://mlsanity.com/paper/1808.08778/) (2018)
- [Programming with Neural Surrogates of Programs](https://mlsanity.com/paper/2112.06148/) (2021)
- [Straggler Mitigation at Scale](https://mlsanity.com/paper/1906.10664/) (2019)
- [Minimax designs for causal effects in temporal experiments with treatment habituation](https://mlsanity.com/paper/1908.03531/) (2019)

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

- [Cost-aware Duration Prediction for Software Upgrades in Datacenters](https://mlsanity.com/paper/2212.05155/) (2022)
- [Applications of Positive Unlabeled (PU) and Negative Unlabeled (NU) Learning in Cybersecurity](https://mlsanity.com/paper/2412.06203/) (2024)

## Abstract (arXiv)

Datacenters execute large computational jobs, which are composed of smaller tasks. A job completes when all its tasks finish, so stragglers -- rare, yet extremely slow tasks -- are a major impediment to datacenter performance. Accurately predicting stragglers would enable proactive intervention, allowing datacenter operators to mitigate stragglers before they delay a job. While much prior work applies machine learning to predict computer system performance, these approaches rely on complete labels -- i.e., sufficient examples of all possible behaviors, including straggling and non-straggling -- or strong assumptions about the underlying latency distributions -- e.g., whether Gaussian or not. Within a running job, however, none of this information is available until stragglers have revealed themselves when they have already delayed the job. To predict stragglers accurately and early without labeled positive examples or assumptions on latency distributions, this paper presents NURD, a novel Negative-Unlabeled learning approach with Reweighting and Distribution-compensation that only trains on negative and unlabeled streaming data. The key idea is to train a predictor using finished tasks of non-stragglers to predict latency for unlabeled running tasks, and then reweight each unlabeled task's prediction based on a weighting function of its feature space. We evaluate NURD on two production traces from Google and Alibaba, and find that compared to the best baseline approach, NURD produces 2--11 percentage point increases in the F1 score in terms of prediction accuracy, and 2.0--8.8 percentage point improvements in job completion time.