# Learning from N-Tuple Data with M Positive Instances: Unbiased Risk Estimation and Theoretical Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 21 Oct 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Attention-based Deep Multiple Instance Learning](https://mlsanity.com/paper/1802.04712/) (2018)
- [The Future of Digital Health with Federated Learning](https://mlsanity.com/paper/2003.08119/) (2020)
- [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)
- [Multiple Instance Learning: A Survey of Problem Characteristics and Applications](https://mlsanity.com/paper/1612.03365/) (2016)
- [Progressive Identification of True Labels for Partial-Label Learning](https://mlsanity.com/paper/2002.08053/) (2020)
- [Learning with Biased Complementary Labels](https://mlsanity.com/paper/1711.09535/) (2017)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Complementary-Label Learning for Arbitrary Losses and Models](https://mlsanity.com/paper/1810.04327/) (2018)
- [Partial Label Learning with Self-Guided Retraining](https://mlsanity.com/paper/1902.03045/) (2019)
- [On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data](https://mlsanity.com/paper/1808.10585/) (2018)
- [Classification from Pairwise Similarity and Unlabeled Data](https://mlsanity.com/paper/1802.04381/) (2018)
- [Mitigating Overfitting in Supervised Classification from Two Unlabeled Datasets: A Consistent Risk Correction Approach](https://mlsanity.com/paper/1910.08974/) (2019)
- [Learning from Label Proportions with Generative Adversarial Networks](https://mlsanity.com/paper/1909.02180/) (2019)
- [Binary Classification from Positive-Confidence Data](https://mlsanity.com/paper/1710.07138/) (2017)
- [Binary Classification from Positive Data with Skewed Confidence](https://mlsanity.com/paper/2001.10642/) (2020)
- [Classification from Triplet Comparison Data](https://mlsanity.com/paper/1907.10225/) (2019)
- [Multi-Complementary and Unlabeled Learning for Arbitrary Losses and Models](https://mlsanity.com/paper/2001.04243/) (2020)

## Abstract (arXiv)

Weakly supervised learning often operates with coarse aggregate signals rather than instance labels. We study a setting where each training example is an n-tuple containing exactly m positives, while only the count m per tuple is observed. This NTMP (N-tuple with M positives) supervision arises in, e.g., image classification with region proposals and multi-instance measurements. We show that tuple counts admit a trainable unbiased risk estimator (URE) by linking the tuple-generation process to latent instance marginals. Starting from fixed (n,m), we derive a closed-form URE and extend it to variable tuple sizes, variable counts, and their combination. Identification holds whenever the effective mixing rate is separated from the class prior. We establish generalization bounds via Rademacher complexity and prove statistical consistency with standard rates under mild regularity assumptions. To improve finite-sample stability, we introduce simple ReLU corrections to the URE that preserve asymptotic correctness. Across benchmarks converted to NTMP tasks, the approach consistently outperforms representative weak-supervision baselines and yields favorable precision-recall and F1 trade-offs. It remains robust under class-prior imbalance and across diverse tuple configurations, demonstrating that count-only supervision can be exploited effectively through a theoretically grounded and practically stable objective.