Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem

• URL: http://arxiv.org/abs/2304.08712v1
• Date: Tue, 18 Apr 2023 03:23:39 GMT
• Title: Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem
• Authors: Tosca Lechner, Shai-Ben-David
• Abstract summary: We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. In particular, we show that there is no notion of characterizing dimension (or characterization of learnability) for any of the tasks.
• Score: 11.39656079889941
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer - no such parameter exists. Our techniques allow us to show similar results for several general notions of characterizing learnability and for several learning tasks. We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. We then consider the weaker requirement of only characterizing learnability (rather than the quantitative sample complexity function). We propose some natural requirements for such a characterization and go on to show that there exists no characterization of learnability that satisfies these requirements for classes of distributions. Furthermore, we show that our results hold for various other learning problems. In particular, we show that there is no notion of dimension characterizing (or characterization of learnability) for any of the tasks: classification learning for distribution classes, learning of binary classifications w.r.t. a restricted set of marginal distributions, and learnability of classes of real-valued functions with continuous losses.

Related papers

• Distribution Learnability and Robustness [13.45619583182489]
  We show that realizable learnability of a class of probability distributions does not imply its learnability. We go on to examine what type of data corruption can disrupt the learnability of a distribution class.
  arXiv  Detail & Related papers  (2024-06-25T05:09:54Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• Neural Collapse Terminus: A Unified Solution for Class Incremental Learning and Its Variants [166.916517335816]
  In this paper, we offer a unified solution to the misalignment dilemma in the three tasks. We propose neural collapse terminus that is a fixed structure with the maximal equiangular inter-class separation for the whole label space. Our method holds the neural collapse optimality in an incremental fashion regardless of data imbalance or data scarcity.
  arXiv  Detail & Related papers  (2023-08-03T13:09:59Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  We study two basic statistical tasks in non-interactive local differential privacy (LDP): learning and refutation. Our main result is a complete characterization of the sample complexity of PAC learning for non-interactive LDP protocols.
  arXiv  Detail & Related papers  (2022-10-26T03:19:24Z)
• Agree to Disagree: Diversity through Disagreement for Better Transferability [54.308327969778155]
  We propose D-BAT (Diversity-By-disAgreement Training), which enforces agreement among the models on the training data. We show how D-BAT naturally emerges from the notion of generalized discrepancy.
  arXiv  Detail & Related papers  (2022-02-09T12:03:02Z)
• Realizable Learning is All You Need [21.34668631009594]
  equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. We give the first model-independent framework explaining the equivalence of realizable and agnostic learnability.
  arXiv  Detail & Related papers  (2021-11-08T19:00:00Z)
• Learning Debiased and Disentangled Representations for Semantic Segmentation [52.35766945827972]
  We propose a model-agnostic and training scheme for semantic segmentation. By randomly eliminating certain class information in each training iteration, we effectively reduce feature dependencies among classes. Models trained with our approach demonstrate strong results on multiple semantic segmentation benchmarks.
  arXiv  Detail & Related papers  (2021-10-31T16:15:09Z)
• Attentional meta-learners are polythetic classifiers [5.543867614999908]
  We show that threshold meta-learners require an embedding dimension that is exponential in the number of features to emulate these functions. We propose a self-attention feature-selection mechanism that adaptively dilutes non-discriminative features.
  arXiv  Detail & Related papers  (2021-06-09T18:11:54Z)
• From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability [0.0]
  We show that there is no general-purpose procedure for rigorously evaluating whether newly proposed models indeed successfully learn from data. For PAC binary classification, uniform and universal online learning, and exact learning through teacher-learner interactions, learnability is in general undecidable. There is no one-size-fits-all algorithm for deciding whether a machine learning model can be successful.
  arXiv  Detail & Related papers  (2021-06-02T18:00:04Z)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  We provide the first modernally precise analysis of linear multiclass classification. Our analysis reveals that the classification accuracy is highly distribution-dependent. The insights gained may pave the way for a precise understanding of other classification algorithms.
  arXiv  Detail & Related papers  (2020-11-16T05:17:29Z)

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.