cs.LGNov 30, 2025

Limitations of Using Identical Distributions for Training and Testing When Learning Boolean Functions

Authors: Jordi Pérez-Guijarro

Organizations: SPCOM Group, Universitat Politècnica de Catalunya, Barcelona, Spain

Abstract

When the distributions of the training and test data do not coincide, the problem of understanding generalization becomes considerably more complex, prompting a variety of questions. Prior work has shown that, for some fixed learning methods, there are scenarios where training on a distribution different from the test distribution improves generalization. However, these results do not account for the possibility of choosing, for each training distribution, the optimal learning algorithm, leaving open whether the observed benefits stem from the mismatch itself or from suboptimality of the learner. In this work, we address this question. That is, we study whether it is always optimal for the training distribution to be identical to the test distribution when the learner is allowed to be optimally adapted to the training distribution. Surprisingly, when we restrict our attention to efficient learners, i.e., those running in polynomial time, and assume the existence of one-way functions, the answer is negative. In other words, matching the training and test distributions is not always optimal.

Explore similar work

Jul 17, 2026

Testing Distributions Against Bounded Distinguishers

Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution PP over a very large domain to decide between two cases: P=PrefP = P_{\mathsf{ref}} for a fixed reference distribution PrefP_{\mathsf{ref}}, or there exists a distinguisher ff in a bounded class F\mathcal{F} which witnesses the separation ∣EP[f]−EPref[f]∣>ε|\mathbf{E}_P[f] - \mathbf{E}_{P_{\mathsf{ref}}}[f]| > ε. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.) We show that testing with respect to fooling distance is not only a natural computational problem that admits sample-efficient algorithms even in high-dimensional settings, but also one that reveals and underlies connections between three seemingly unrelated areas of study: testable learning, verification of learning algorithms, and testing of structured distributions (whose "Ak\mathcal{A}_k-testing" model our framework extends). These connections yield new results for all of these models, including: 1. Testable proper learners using membership queries for halfspaces and decision trees. 2. A lower bound for testable PAC verification in terms of Rademacher complexity, and a distribution-free verification protocol for disjoint unions of kk multidimensional rectangles. 3. Identity testers (with respect to total variation distance) for decision tree distributions and distributions with low-degree polynomial densities, over Boolean and continuous hypercube domains.
May 7, 2026

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift

Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al. (2024)). Algorithms for TDS learning are allowed to reject a test set entirely if distribution shift is detected. In contrast, PQ learners may only reject points that are deemed out-of-distribution on an individual basis. Our main result is a surprising equivalence between these two models in the distribution-free setting. In particular, we give an efficient black-box reduction from PQ learning to TDS learning for any Boolean concept class. This equivalence implies the first hardness results for distribution-free TDS learning of basic classes such as halfspaces. The main technical contribution underlying our equivalence is a method for boosting, via branching programs, the weak distinguishing power of TDS learners that have rejected the target domain. We also show that giving a learner access to membership queries sidesteps these hardness results and allows for efficient, distribution-free PQ learnability of halfspaces. Our algorithm iteratively recovers large-margin separators obtained by applying successive Forster transforms on the training data.
Jun 22, 2025

Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning

Robust distributed learning algorithms aim to maintain reliable performance despite the presence of misbehaving workers. Such misbehaviors are commonly modeled as Byzantine failures, allowing arbitrarily corrupted communication, or as data poisoning, a weaker form of corruption restricted to local training data. While prior work shows similar optimization guarantees for both models, an important question remains: How do these threat models impact generalization? We show, for the first time, a fundamental gap in generalization guarantees between the two threat models: Byzantine failures yield strictly worse rates than those achievable under data poisoning. Our findings are based upon a tight algorithmic stability analysis of robust distributed learning. Specifically, with ff out of nn workers misbehaving, we prove that: (i) under data poisoning, the uniform algorithmic stability of a robust distributed learning algorithm