Relatively Smart: A New Approach for Instance-Optimal Learning

• URL: http://arxiv.org/abs/2603.01346v1
• Date: Mon, 02 Mar 2026 00:59:10 GMT
• Title: Relatively Smart: A New Approach for Instance-Optimal Learning
• Authors: Shaddin Dughmi, Alireza F. Pour,
• Abstract summary: We revisit the framework of Smart PAC learning, which seeks supervised learners which compete with semi-supervised learners.<n>We show that relatively smart learning can be impossible or can require idiosyncratic learning approaches.
• Score: 3.545082819007165
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the framework of Smart PAC learning, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the marginal distribution on unlabeled data. Prior work has shown that such marginal-by-marginal guarantees are possible for "most" marginals, with respect to an arbitrary fixed and known measure, but not more generally. We discover that this failure can be attributed to an "indistinguishability" phenomenon: There are marginals which cannot be statistically distinguished from other marginals that require different learning approaches. In such settings, semi-supervised learning cannot certify its guarantees from unlabeled data, rendering them arguably non-actionable. We propose relatively smart learning, a new framework which demands that a supervised learner compete only with the best "certifiable" semi-supervised guarantee. We show that such modest relaxation suffices to bypass the impossibility results from prior work. In the distribution-free setting, we show that the OIG learner is relatively smart up to squaring the sample complexity, and show that no supervised learning algorithm can do better. For distribution-family settings, we show that relatively smart learning can be impossible or can require idiosyncratic learning approaches, and its difficulty can be non-monotone in the inclusion order on distribution families.

Related papers

• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Generalization Bounds and Stopping Rules for Learning with Self-Selected Data [0.0]
  We prove universal generalization bounds for reciprocal learning using covering numbers and Wasserstein ambiguity sets.<n>We illustrate our bounds and stopping rules for reciprocal learning's special case of semi-supervised learning.
  arXiv  Detail & Related papers  (2025-05-12T09:06:39Z)
• Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
  We show that there are problems whose proper learnability is logically undecidable, i.e., independent of the ZFC axioms.<n>We then show all impossibility results which obstruct any characterization of proper learnability in the realizable PAC model.
  arXiv  Detail & Related papers  (2025-02-14T18:41:53Z)
• 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)
• 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)
• Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization [39.51923275855131]
  We present a minimax optimal learner for the problem of learning predictors robust to adversarial examples at test-time. In particular, we show, in a strong negative sense, the suboptimality of the robust learner proposed by Montasser, Hanneke, and Srebro.
  arXiv  Detail & Related papers  (2022-09-15T15:32:42Z)
• Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap [64.60460828425502]
  We propose a new guarantee on the downstream performance of contrastive learning. Our new theory hinges on the insight that the support of different intra-class samples will become more overlapped under aggressive data augmentations. We propose an unsupervised model selection metric ARC that aligns well with downstream accuracy.
  arXiv  Detail & Related papers  (2022-03-25T05:36:26Z)
• Improving Self-supervised Learning with Automated Unsupervised Outlier Arbitration [83.29856873525674]
  We introduce a lightweight latent variable model UOTA, targeting the view sampling issue for self-supervised learning. Our method directly generalizes to many mainstream self-supervised learning approaches.
  arXiv  Detail & Related papers  (2021-12-15T14:05:23Z)
• MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning [65.52675802289775]
  We show that an uncertainty aware classifier can solve challenging reinforcement learning problems. We propose a novel method for computing the normalized maximum likelihood (NML) distribution. We show that the resulting algorithm has a number of intriguing connections to both count-based exploration methods and prior algorithms for learning reward functions.
  arXiv  Detail & Related papers  (2021-07-15T08:19:57Z)
• Credal Self-Supervised Learning [0.0]
  We show how to let the learner generate "pseudo-supervision" for unlabeled instances. In combination with consistency regularization, pseudo-labeling has shown promising performance in various domains. We compare our methodology to state-of-the-art self-supervision approaches.
  arXiv  Detail & Related papers  (2021-06-22T15:19:04Z)
• Semi-verified PAC Learning from the Crowd [7.594050968868919]
  We study the problem of crowdsourced PAC learning of threshold functions. We show that under the semi-verified model of Charikar et al., it is possible to PAC learn the underlying hypothesis class with a manageable amount of label queries.
  arXiv  Detail & Related papers  (2021-06-13T20:05:16Z)
• Fairness Constraints in Semi-supervised Learning [56.48626493765908]
  We develop a framework for fair semi-supervised learning, which is formulated as an optimization problem. We theoretically analyze the source of discrimination in semi-supervised learning via bias, variance and noise decomposition. Our method is able to achieve fair semi-supervised learning, and reach a better trade-off between accuracy and fairness than fair supervised learning.
  arXiv  Detail & Related papers  (2020-09-14T04:25:59Z)
• Unsupervisedly Learned Representations: Should the Quest be Over? [0.0]
  We demonstrate that Reinforcement Learning can learn representations which achieve the same accuracy as that of animals.<n>The corollary of these observations is that further search for Unsupervised Learning competitive paradigms which may be trained in simulated environments may be futile.
  arXiv  Detail & Related papers  (2020-01-21T13:05:31Z)

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.