Optimistic Rates for Learning from Label Proportions

• URL: http://arxiv.org/abs/2406.00487v1
• Date: Sat, 1 Jun 2024 16:36:40 GMT
• Title: Optimistic Rates for Learning from Label Proportions
• Authors: Gene Li, Lin Chen, Adel Javanmard, Vahab Mirrokni,
• Abstract summary: We consider a weakly supervised learning problem called Learning from Label Proportions (LLP), where examples are grouped into bags'' We study various learning rules for LLP that achieve PAC learning guarantees for classification loss.
• Score: 19.980594971351014
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a weakly supervised learning problem called Learning from Label Proportions (LLP), where examples are grouped into ``bags'' and only the average label within each bag is revealed to the learner. We study various learning rules for LLP that achieve PAC learning guarantees for classification loss. We establish that the classical Empirical Proportional Risk Minimization (EPRM) learning rule (Yu et al., 2014) achieves fast rates under realizability, but EPRM and similar proportion matching learning rules can fail in the agnostic setting. We also show that (1) a debiased proportional square loss, as well as (2) a recently proposed EasyLLP learning rule (Busa-Fekete et al., 2023) both achieve ``optimistic rates'' (Panchenko, 2002); in both the realizable and agnostic settings, their sample complexity is optimal (up to log factors) in terms of $\epsilon, \delta$, and VC dimension.

Related papers

• Learning Conditional Averages [52.361762722359366]
  We introduce the problem of learning conditional averages in the PAC framework.<n>Instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood.<n>More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains.
  arXiv  Detail & Related papers  (2026-02-12T13:20:29Z)
• Nearly Optimal Sample Complexity for Learning with Label Proportions [54.67830198790247]
  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.
  arXiv  Detail & Related papers  (2025-05-08T15:45:23Z)
• Probably Approximately Precision and Recall Learning [62.912015491907994]
  Precision and Recall are foundational metrics in machine learning. One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems. We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• An Unbiased Risk Estimator for Partial Label Learning with Augmented Classes [46.663081214928226]
  We propose an unbiased risk estimator with theoretical guarantees for PLLAC. We provide a theoretical analysis of the estimation error bound of PLLAC. Experiments on benchmark, UCI and real-world datasets demonstrate the effectiveness of the proposed approach.
  arXiv  Detail & Related papers  (2024-09-29T07:36:16Z)
• Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical [66.57396042747706]
  Complementary-label learning is a weakly supervised learning problem. We propose a consistent approach that does not rely on the uniform distribution assumption. We find that complementary-label learning can be expressed as a set of negative-unlabeled binary classification problems.
  arXiv  Detail & Related papers  (2023-11-27T02:59:17Z)
• Robust Representation Learning for Unreliable Partial Label Learning [86.909511808373]
  Partial Label Learning (PLL) is a type of weakly supervised learning where each training instance is assigned a set of candidate labels, but only one label is the ground-truth. This is known as Unreliable Partial Label Learning (UPLL) that introduces an additional complexity due to the inherent unreliability and ambiguity of partial labels. We propose the Unreliability-Robust Representation Learning framework (URRL) that leverages unreliability-robust contrastive learning to help the model fortify against unreliable partial labels effectively.
  arXiv  Detail & Related papers  (2023-08-31T13:37:28Z)
• A Universal Unbiased Method for Classification from Aggregate Observations [115.20235020903992]
  This paper presents a novel universal method of CFAO, which holds an unbiased estimator of the classification risk for arbitrary losses. Our proposed method not only guarantees the risk consistency due to the unbiased risk estimator but also can be compatible with arbitrary losses.
  arXiv  Detail & Related papers  (2023-06-20T07:22:01Z)
• 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)
• Learning from Label Proportions by Learning with Label Noise [30.7933303912474]
  Learning from label proportions (LLP) is a weakly supervised classification problem where data points are grouped into bags. We provide a theoretically grounded approach to LLP based on a reduction to learning with label noise. Our approach demonstrates improved empirical performance in deep learning scenarios across multiple datasets and architectures.
  arXiv  Detail & Related papers  (2022-03-04T18:52:21Z)
• Leveraged Weighted Loss for Partial Label Learning [64.85763991485652]
  Partial label learning deals with data where each instance is assigned with a set of candidate labels, whereas only one of them is true. Despite many methodology studies on learning from partial labels, there still lacks theoretical understandings of their risk consistent properties. We propose a family of loss functions named textitd weighted (LW) loss, which for the first time introduces the leverage parameter $beta$ to consider the trade-off between losses on partial labels and non-partial ones.
  arXiv  Detail & Related papers  (2021-06-10T13:25:13Z)
• On the Complexity of Learning from Label Proportions [4.111899441919163]
  We study the problem of learning with label proportions with unlabeled training data. This model of learning is applicable to a wide variety of settings, including predicting the number of votes for candidates in political elections from polls. We show, perhaps surprisingly, that for finite VC classes what can be efficiently LLP learned is a strict subset of what can be leaned efficiently in PAC.
  arXiv  Detail & Related papers  (2020-04-07T16:15:22Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)

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.