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

• URL: http://arxiv.org/abs/2510.18406v2
• Date: Mon, 10 Nov 2025 07:41:24 GMT
• Title: Learning from N-Tuple Data with M Positive Instances: Unbiased Risk Estimation and Theoretical Guarantees
• Authors: Miao Zhang, Junpeng Li, ChangChun HUa, Yana Yang,
• Abstract summary: Weakly supervised learning often operates with coarse aggregate signals rather than labels.<n>We show that counts admit a trainable unbiased risk estimator (URE) by linking the instance-generation process to latent marginals.<n>We demonstrate that count-only supervision can be exploited effectively through a theoretically grounded and practically stable objective setting.
• Score: 33.15955234458642
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Computable Bernstein Certificates for Cross-Fitted Clipped Covariance Estimation [0.0]
  We propose a cross-fitted clipped covariance estimator equipped with emphfully computable Bernstein-type deviation certificates.<n>The resulting procedure adapts to intrinsic complexity measures such as effective rank under mild tail regularity.
  arXiv  Detail & Related papers  (2026-02-15T06:53:40Z)
• A Unified and Stable Risk Minimization Framework for Weakly Supervised Learning with Theoretical Guarantees [33.15955234458642]
  Weakly supervised learning has emerged as a practical alternative to fully supervised learning when complete and accurate labels are costly or infeasible to acquire.<n>We propose a principled, unified framework that bypasses such post-hoc adjustments by formulating a stable surrogate risk grounded in the structure of weakly supervised data.
  arXiv  Detail & Related papers  (2025-11-28T00:57:04Z)
• In-Context Learning Is Provably Bayesian Inference: A Generalization Theory for Meta-Learning [51.56484100374058]
  We introduce a principled risk decomposition that separates the total ICL risk into two components: Bayes Gap and Posterior Variance.<n>For a uniform-attention Transformer, we derive a non-asymptotic upper bound on this gap, which explicitly clarifies the dependence on the number of pretraining prompts.<n>The Posterior Variance is a model-independent risk representing the intrinsic task uncertainty.
  arXiv  Detail & Related papers  (2025-10-13T03:42:31Z)
• The Lie of the Average: How Class Incremental Learning Evaluation Deceives You? [48.83567710215299]
  Class Incremental Learning (CIL) requires models to continuously learn new classes without forgetting previously learned ones.<n>We argue that a robust CIL evaluation protocol should accurately characterize and estimate the entire performance distribution.<n>We propose EDGE, an evaluation protocol that adaptively identifies and samples extreme class sequences using inter-task similarity.
  arXiv  Detail & Related papers  (2025-09-26T17:00:15Z)
• Benign Overfitting in Out-of-Distribution Generalization of Linear Models [19.203753135860016]
  We take an initial step towards understanding benign overfitting in the Out-of-Distribution (OOD) regime.<n>We provide non-asymptotic guarantees proving that benign overfitting occurs in standard ridge regression.<n>We also present theoretical results for a more general family of target covariance matrix.
  arXiv  Detail & Related papers  (2024-12-19T02:47:39Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  A key challenge in machine learning is the prevalence of one-sided feedback.<n>We introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels.<n>We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• Task-oriented Embedding Counts: Heuristic Clustering-driven Feature Fine-tuning for Whole Slide Image Classification [1.292108130501585]
  We propose a clustering-driven feature fine-tuning method (HC-FT) to enhance the performance of multiple instance learning. The proposed method is evaluated on both CAMELYON16 and BRACS datasets, achieving an AUC of 97.13% and 85.85%, respectively.
  arXiv  Detail & Related papers  (2024-06-02T08:53:45Z)
• Rethinking Classifier Re-Training in Long-Tailed Recognition: A Simple Logits Retargeting Approach [102.0769560460338]
  We develop a simple logits approach (LORT) without the requirement of prior knowledge of the number of samples per class. Our method achieves state-of-the-art performance on various imbalanced datasets, including CIFAR100-LT, ImageNet-LT, and iNaturalist 2018.
  arXiv  Detail & Related papers  (2024-03-01T03:27:08Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Meta-Learned Confidence for Few-shot Learning [60.6086305523402]
  A popular transductive inference technique for few-shot metric-based approaches, is to update the prototype of each class with the mean of the most confident query examples. We propose to meta-learn the confidence for each query sample, to assign optimal weights to unlabeled queries. We validate our few-shot learning model with meta-learned confidence on four benchmark datasets.
  arXiv  Detail & Related papers  (2020-02-27T10:22:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.