PAC Learnability in the Presence of Performativity

• URL: http://arxiv.org/abs/2510.08335v1
• Date: Thu, 09 Oct 2025 15:22:52 GMT
• Title: PAC Learnability in the Presence of Performativity
• Authors: Ivan Kirev, Lyuben Baltadzhiev, Nikola Konstantinov,
• Abstract summary: We study whether and when performative binary classification problems are learnable, via the lens of the classic PAC (Probably Approximately Correct) learning framework.<n>We construct a performative empirical risk function, which depends on data from the original distribution and on the type performative effect.<n>Minimizing this notion of performative risk allows us to show that any PAC-learnable hypothesis space in the standard binary classification setting remains PAC-learnable.
• Score: 5.996298190476913
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Following the wide-spread adoption of machine learning models in real-world applications, the phenomenon of performativity, i.e. model-dependent shifts in the test distribution, becomes increasingly prevalent. Unfortunately, since models are usually trained solely based on samples from the original (unshifted) distribution, this performative shift may lead to decreased test-time performance. In this paper, we study the question of whether and when performative binary classification problems are learnable, via the lens of the classic PAC (Probably Approximately Correct) learning framework. We motivate several performative scenarios, accounting in particular for linear shifts in the label distribution, as well as for more general changes in both the labels and the features. We construct a performative empirical risk function, which depends only on data from the original distribution and on the type performative effect, and is yet an unbiased estimate of the true risk of a classifier on the shifted distribution. Minimizing this notion of performative risk allows us to show that any PAC-learnable hypothesis space in the standard binary classification setting remains PAC-learnable for the considered performative scenarios. We also conduct an extensive experimental evaluation of our performative risk minimization method and showcase benefits on synthetic and real data.

Related papers

• Mind the Gap: Bridging Prior Shift in Realistic Few-Shot Crop-Type Classification [0.3823356975862005]
  Real-world agricultural distributions often suffer from severe class imbalance, typically following a long-tailed distribution.<n>We propose Dirichlet Prior Augmentation (DirPA), a novel method that simulates an unknown label distribution skew of the target domain proactively during model training.<n>Our experiments show that DirPA successfully shifts the decision boundary and stabilizes the training process by acting as a dynamic feature regularizer.
  arXiv  Detail & Related papers  (2025-11-20T10:39:25Z)
• 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)
• Optimal Classification under Performative Distribution Shift [13.508249764979075]
  We propose a novel view in which performative effects are modelled as push-forward measures. We prove the convexity of the performative risk under a new set of assumptions. We also establish a connection with adversarially robust classification by reformulating the minimization of the performative risk as a min-max variational problem.
  arXiv  Detail & Related papers  (2024-11-04T12:20:13Z)
• SimPro: A Simple Probabilistic Framework Towards Realistic Long-Tailed Semi-Supervised Learning [49.94607673097326]
  We propose a highly adaptable framework, designated as SimPro, which does not rely on any predefined assumptions about the distribution of unlabeled data. Our framework, grounded in a probabilistic model, innovatively refines the expectation-maximization algorithm. Our method showcases consistent state-of-the-art performance across diverse benchmarks and data distribution scenarios.
  arXiv  Detail & Related papers  (2024-02-21T03:39:04Z)
• Class Distribution Shifts in Zero-Shot Learning: Learning Robust Representations [3.8980564330208662]
  We propose and analyze a model that assumes that the attribute responsible for the shift is unknown in advance.<n>We show that our algorithm improves generalization to diverse class distributions in both simulations and experiments on real-world datasets.
  arXiv  Detail & Related papers  (2023-11-30T14:14:31Z)
• Effect-Invariant Mechanisms for Policy Generalization [3.701112941066256]
  It has been suggested to exploit invariant conditional distributions to learn models that generalize better to unseen environments. We introduce a relaxation of full invariance called effect-invariance and prove that it is sufficient, under suitable assumptions, for zero-shot policy generalization. We present empirical results using simulated data and a mobile health intervention dataset to demonstrate the effectiveness of our approach.
  arXiv  Detail & Related papers  (2023-06-19T14:50:24Z)
• Variational Classification [51.2541371924591]
  We derive a variational objective to train the model, analogous to the evidence lower bound (ELBO) used to train variational auto-encoders. Treating inputs to the softmax layer as samples of a latent variable, our abstracted perspective reveals a potential inconsistency. We induce a chosen latent distribution, instead of the implicit assumption found in a standard softmax layer.
  arXiv  Detail & Related papers  (2023-05-17T17:47:19Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
  We propose a novel class of deep predictors for classifying metric data on graphs within PAC-Bayes risk certification paradigm. Building on the recent PAC-Bayes literature and data-dependent priors, this approach enables learning posterior distributions on the hypothesis space.
  arXiv  Detail & Related papers  (2022-01-26T19:59:14Z)
• Learning Invariant Representations and Risks for Semi-supervised Domain Adaptation [109.73983088432364]
  We propose the first method that aims to simultaneously learn invariant representations and risks under the setting of semi-supervised domain adaptation (Semi-DA) We introduce the LIRR algorithm for jointly textbfLearning textbfInvariant textbfRepresentations and textbfRisks.
  arXiv  Detail & Related papers  (2020-10-09T15:42:35Z)

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.