Distribution Learning with Valid Outputs Beyond the Worst-Case

• URL: http://arxiv.org/abs/2410.16253v1
• Date: Mon, 21 Oct 2024 17:56:09 GMT
• Title: Distribution Learning with Valid Outputs Beyond the Worst-Case
• Authors: Nick Rittler, Kamalika Chaudhuri,
• Abstract summary: Validity-constrained distribution learning attempts to address this problem by requiring that the learned distribution have a provably small fraction of its mass in invalid parts of space. We show that when the data distribution lies in the model class and the log-loss is minimized, the number of samples required to ensure validity has a weak dependence on the validity requirement.
• Score: 25.788559173418363
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Generative models at times produce "invalid" outputs, such as images with generation artifacts and unnatural sounds. Validity-constrained distribution learning attempts to address this problem by requiring that the learned distribution have a provably small fraction of its mass in invalid parts of space -- something which standard loss minimization does not always ensure. To this end, a learner in this model can guide the learning via "validity queries", which allow it to ascertain the validity of individual examples. Prior work on this problem takes a worst-case stance, showing that proper learning requires an exponential number of validity queries, and demonstrating an improper algorithm which -- while generating guarantees in a wide-range of settings -- makes an atypical polynomial number of validity queries. In this work, we take a first step towards characterizing regimes where guaranteeing validity is easier than in the worst-case. We show that when the data distribution lies in the model class and the log-loss is minimized, the number of samples required to ensure validity has a weak dependence on the validity requirement. Additionally, we show that when the validity region belongs to a VC-class, a limited number of validity queries are often sufficient.

Related papers

• On the Query Complexity of Verifier-Assisted Language Generation [35.43462431990329]
  We develop a framework for reasoning about constrained generation using a pre-trained language model generator oracle. Access to a verifier can render an intractable problem (information-theoretically or computationally) to a tractable one. We show even simple algorithms, like tokenwise rejection sampling, can enjoy significant benefits from access to a verifier.
  arXiv  Detail & Related papers  (2025-02-17T18:46:32Z)
• 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)
• Quantifying Local Model Validity using Active Learning [2.8078480738404]
  Real-world applications of machine learning models are often subject to legal or policy-based regulations. Some of these regulations require ensuring the validity of the model, i.e., the approximation error being smaller than a threshold. We propose learning the model error to acquire a local validity estimate while reducing the amount of required data through active learning.
  arXiv  Detail & Related papers  (2024-06-11T17:20:28Z)
• Understanding and Mitigating Classification Errors Through Interpretable Token Patterns [58.91023283103762]
  Characterizing errors in easily interpretable terms gives insight into whether a classifier is prone to making systematic errors. We propose to discover those patterns of tokens that distinguish correct and erroneous predictions. We show that our method, Premise, performs well in practice.
  arXiv  Detail & Related papers  (2023-11-18T00:24:26Z)
• Understanding prompt engineering may not require rethinking generalization [56.38207873589642]
  We show that the discrete nature of prompts, combined with a PAC-Bayes prior given by a language model, results in generalization bounds that are remarkably tight by the standards of the literature. This work provides a possible justification for the widespread practice of prompt engineering.
  arXiv  Detail & Related papers  (2023-10-06T00:52:48Z)
• MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
  We propose a worst-case consistency regularization technique for semi-supervised learning (SSL) We present a generalization bound for SSL consisting of the empirical loss terms observed on labeled and unlabeled training data separately. Motivated by this bound, we derive an SSL objective that minimizes the largest inconsistency between an original unlabeled sample and its multiple augmented variants.
  arXiv  Detail & Related papers  (2022-09-26T12:04:49Z)
• CAFA: Class-Aware Feature Alignment for Test-Time Adaptation [50.26963784271912]
  Test-time adaptation (TTA) aims to address this challenge by adapting a model to unlabeled data at test time. We propose a simple yet effective feature alignment loss, termed as Class-Aware Feature Alignment (CAFA), which simultaneously encourages a model to learn target representations in a class-discriminative manner.
  arXiv  Detail & Related papers  (2022-06-01T03:02:07Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
  arXiv  Detail & Related papers  (2021-10-27T08:00:53Z)
• Label-Descriptive Patterns and their Application to Characterizing Classification Errors [31.272875287136426]
  State-of-the-art deep learning methods achieve human-like performance on many tasks, but make errors nevertheless. Characterizing these errors in easily interpretable terms gives insight into whether a model is prone to making systematic errors, but also gives a way to act and improve the model. In this paper we propose a method that allows us to do so for arbitrary classifiers by mining a small set of patterns that together succinctly describe the input data that is partitioned according to correctness of prediction.
  arXiv  Detail & Related papers  (2021-10-18T19:42:21Z)
• Leave Zero Out: Towards a No-Cross-Validation Approach for Model Selection [21.06860861548758]
  Cross Validation (CV) is the main workhorse for model selection. CV suffers a conservatively biased estimation, since some part of the limited data has to hold out for validation. CV tends to be extremely cumbersome, e.g., intolerant time-consuming, due to the repeated training procedures.
  arXiv  Detail & Related papers  (2020-12-24T16:11:53Z)
• Identifying Wrongly Predicted Samples: A Method for Active Learning [6.976600214375139]
  We propose a simple sample selection criterion that moves beyond uncertainty. We show state-of-the-art results and better rates at identifying wrongly predicted samples.
  arXiv  Detail & Related papers  (2020-10-14T09:00:42Z)

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.