← 研踪 PaperTrailarXiv:2512.00791 · v3
Limitations of Using Identical Distributions for Training and Testing When Learning Boolean Functions
首次提交 2025-11-30 17:06
版本更新 2026-11-06 17:31
雷达观测 2026-11-09 11:19
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-06 17:31 · 最新观测版本
Limitations of Using Identical Distributions for Training and Testing When Learning Boolean Functions
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.
查看此版本解读 →查看此版本原文 ↗