Nearly Optimal Sample Complexity for Learning with Label Proportions

• URL: http://arxiv.org/abs/2505.05355v2
• Date: Thu, 29 May 2025 20:12:53 GMT
• Title: Nearly Optimal Sample Complexity for Learning with Label Proportions
• Authors: Robert Busa-Fekete, Travis Dick, Claudio Gentile, Haim Kaplan, Tomer Koren, Uri Stemmer,
• Abstract summary: We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags.<n>Despite the partial observability, the goal is still to achieve small regret at the level of individual examples.<n>We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal.
• Score: 54.67830198790247
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each bag are available. Despite the partial observability, the goal is still to achieve small regret at the level of individual examples. We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal. From an algorithmic viewpoint, we rely on carefully designed variants of Empirical Risk Minimization, and Stochastic Gradient Descent algorithms, combined with ad hoc variance reduction techniques. On one hand, our theoretical results improve in important ways on the existing literature on LLP, specifically in the way the sample complexity depends on the bag size. On the other hand, we validate our algorithmic solutions on several datasets, demonstrating improved empirical performance (better accuracy for less samples) against recent baselines.

Related papers

• Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit [7.141484637056533]
  We propose a method for recovering projections containing either Imbalanced Clusters or a Bernoulli-Rademacher distribution.<n>We analyze our algorithm's sample complexity within a Planted Vector setting where we can observe that Imbalanced Clusters can be recovered more easily than balanced ones.<n>We experimentally evaluate our method's applicability to real-world data using FashionMNIST and the Human Activity Recognition dataset.
  arXiv  Detail & Related papers  (2025-02-04T19:18:17Z)
• Data Pruning via Moving-one-Sample-out [61.45441981346064]
  We propose a novel data-pruning approach called moving-one-sample-out (MoSo) MoSo aims to identify and remove the least informative samples from the training set. Experimental results demonstrate that MoSo effectively mitigates severe performance degradation at high pruning ratios.
  arXiv  Detail & Related papers  (2023-10-23T08:00:03Z)
• Easy Learning from Label Proportions [17.71834385754893]
  Easyllp is a flexible and simple-to-implement debiasing approach based on aggregate labels. Our technique allows us to accurately estimate the expected loss of an arbitrary model at an individual level.
  arXiv  Detail & Related papers  (2023-02-06T20:41:38Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model. We show that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model.
  arXiv  Detail & Related papers  (2022-02-11T03:01:45Z)
• Fast learning from label proportions with small bags [0.0]
  In learning from label proportions (LLP), the instances are grouped into bags, and the task is to learn an instance classifier given relative class proportions in training bags. In this work, we focus on the case of small bags, which allows designing more efficient algorithms by explicitly considering all consistent label combinations.
  arXiv  Detail & Related papers  (2021-10-07T13:11:18Z)
• Rethinking preventing class-collapsing in metric learning with margin-based losses [81.22825616879936]
  Metric learning seeks embeddings where visually similar instances are close and dissimilar instances are apart. margin-based losses tend to project all samples of a class onto a single point in the embedding space. We propose a simple modification to the embedding losses such that each sample selects its nearest same-class counterpart in a batch.
  arXiv  Detail & Related papers  (2020-06-09T09:59:25Z)
• Minority Class Oversampling for Tabular Data with Deep Generative Models [4.976007156860967]
  We study the ability of deep generative models to provide realistic samples that improve performance on imbalanced classification tasks via oversampling. Our experiments show that the way the method of sampling does not affect quality, but runtime varies widely. We also observe that the improvements in terms of performance metric, while shown to be significant, often are minor in absolute terms.
  arXiv  Detail & Related papers  (2020-05-07T21:35:57Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.