Limitations of Using Identical Distributions for Training and Testing When Learning Boolean Functions
This addresses a fundamental problem in machine learning theory for researchers, showing incremental insights into generalization under distribution shifts.
The paper investigates whether training and test distributions should always match for learning Boolean functions, finding that under the existence of one-way functions, matching is not always optimal, but standard conclusions hold with uniform distributions under certain regularities.
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. In this work, we focus on a fundamental one: Is it always optimal for the training distribution to be identical to the test distribution? Surprisingly, assuming the existence of one-way functions, we find that the answer is no. That is, matching distributions is not always the best scenario, which contrasts with the behavior of most learning methods. Nonetheless, we also show that when certain regularities are imposed on the target functions, the standard conclusion is recovered in the case of the uniform distribution.