Strategic PAC Learnability via Geometric Definability

• URL: http://arxiv.org/abs/2605.13426v2
• Date: Thu, 14 May 2026 04:07:26 GMT
• Title: Strategic PAC Learnability via Geometric Definability
• Abstract summary: Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
• Score: 69.34283267701421
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension $1$ on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $\mathbb{R}_{\mathtt{exp}}$. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including $\ell_p$ distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.

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)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  Learning intersections of halfspaces is a central problem in Computational Learning Theory.<n>Even for just two halfspaces, it remains a major open question whether learning is possible in time.<n>We introduce a novel algorithm that provably circumvents the CSQ hardness barrier.
  arXiv  Detail & Related papers  (2025-11-13T00:28:24Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• Fundamental computational limits of weak learnability in high-dimensional multi-index models [30.501140910531017]
  This paper focuses on the minimum sample complexity required for weakly recovering their low-dimensional structure with first-order iterative algorithms.<n>Our findings unfold in three parts: (i) we identify under which conditions a trivial subspace can be learned with a single step of a first-order algorithm for any $alpha!>!0$; (ii) if the trivial subspace is empty, we provide necessary and sufficient conditions for the existence of an easy subspace.<n>In a limited but interesting set of really hard directions -- akin to the parity problem -- $alpha_c$ is found
  arXiv  Detail & Related papers  (2024-05-24T11:59:02Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  This work is inspired by the foundation of PAC and is motivated by the existing regression learning issues. The proposed approach, denoted by epsilon-Confidence Approximately Correct (epsilon CoAC), utilizes Kullback Leibler divergence (relative entropy) It enables the learner to compare hypothesis classes of different complexity orders and choose among them the optimum with the minimum epsilon.
  arXiv  Detail & Related papers  (2023-03-28T15:59:12Z)
• Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes [5.194264506657145]
  We introduce comparative learning as a combination of the realizable and agnostic settings in PAC learning. Even when both $S$ and $B$ have infinite VC dimensions, comparative learning can still have a small sample complexity. We show that the sample complexity of comparative learning is characterized by the mutual VC dimension $mathsfVC(S,B)$.
  arXiv  Detail & Related papers  (2022-11-16T18:38:24Z)
• Adversarially Robust PAC Learnability of Real-Valued Functions [19.54399554114989]
  We show that classes of fat-shattering dimension are $ell_p$ learnable in $ell_p$ perturbation setting. We introduce a novel agnostic agnostic sample scheme for real functions, which may be independent interest.
  arXiv  Detail & Related papers  (2022-06-26T21:27:23Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  We prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $tilde O(d6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2O(d)$ on the sample complexity.
  arXiv  Detail & Related papers  (2020-12-07T18:17:46Z)

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.