# Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jan 2015.

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

- [HealthBench: Evaluating Large Language Models Towards Improved Human Health](https://mlsanity.com/paper/2505.08775/) (2025)
- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (2021)
- [Kernel Stein Discrepancy Descent](https://mlsanity.com/paper/2105.09994/) (2021)
- [Rethinking Importance Weighting for Transfer Learning](https://mlsanity.com/paper/2112.10157/) (2021)
- [MedConsultBench: A Full-Cycle, Fine-Grained, Process-Aware Benchmark for Medical Consultation Agents](https://mlsanity.com/paper/2601.12661/) (2026)
- [On Medians of (Randomized) Pairwise Means](https://mlsanity.com/paper/2211.00603/) (2022)
- [Assessing Uncertainty in Similarity Scoring: Performance & Fairness in Face Recognition](https://mlsanity.com/paper/2211.07245/) (2022)
- [Beyond Basic A/B testing: Improving Statistical Efficiency for Business Growth](https://mlsanity.com/paper/2505.08128/) (2025)
- [Doing well with less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimization](https://mlsanity.com/paper/2606.02345/) (2026)
- [Scalable Personalised Item Ranking through Parametric Density Estimation](https://mlsanity.com/paper/2105.04769/) (2021)
- [Self-Supervised Pretraining of Graph Neural Network for the Retrieval of Related Mathematical Expressions in Scientific Articles](https://mlsanity.com/paper/2209.00446/) (2022)
- [Scaling Up ROC-Optimizing Support Vector Machines](https://mlsanity.com/paper/2511.04979/) (2025)
- [On Gossip Algorithms for Machine Learning with Pairwise Objectives](https://mlsanity.com/paper/2603.24128/) (2026)
- [Learning U-Statistics with Active Inference](https://mlsanity.com/paper/2605.11638/) (2026)
- [On Finite-sample Concentration of Median of Incomplete U-Statistics](https://mlsanity.com/paper/2606.00661/) (2026)
- [On Pairwise Quantile Regression - Statistical Guarantees and Applications](https://mlsanity.com/paper/2607.04431/) (2026)
- [Bayes-Optimal BER and AUC: Estimation and Evaluation of Estimators](https://mlsanity.com/paper/2609.02304/) (2026)

## Abstract (arXiv)

In a wide range of statistical learning problems such as ranking, clustering or metric learning among others, the risk is accurately estimated by U-statistics of degree d≥ 1, i.e. functionals of the training data with low variance that take the form of averages over k-tuples. From a computational perspective, the calculation of such statistics is highly expensive even for a moderate sample size n, as it requires averaging O(nd) terms. This makes learning procedures relying on the optimization of such data functionals hardly feasible in practice. It is the major goal of this paper to show that, strikingly, such empirical risks can be replaced by drastically computationally simpler Monte-Carlo estimates based on O(n) terms only, usually referred to as incomplete U-statistics, without damaging the O_mathbbP(1/√n) learning rate of Empirical Risk Minimization (ERM) procedures. For this purpose, we establish uniform deviation results describing the error made when approximating a U-process by its incomplete version under appropriate complexity assumptions. Extensions to model selection, fast rate situations and various sampling techniques are also considered, as well as an application to stochastic gradient descent for ERM. Finally, numerical examples are displayed in order to provide strong empirical evidence that the approach we promote largely surpasses more naive subsampling techniques.