Input Information and the Learning Boundary

Learning can fail because the input is insufficient, even when representation, optimization, and computation pose no obstacle. We study the corresponding information-theoretic learning boundary, which is the threshold at which the observations themselves become sufficient. Exact recovery makes this boundary observable by requiring an optimal learner to identify a finite structured target exactly. We show that exact recovery depends on two distinct properties of the input. The observations must distinguish the candidate set in total, and decisive evidence must reach every hidden coordinate. In forced-satisfiable planted $k$-SAT, we characterize this boundary at window precision. At $m=\frac{n(2^k-1)}{k}(\ln n+x+o(1))$ clauses, the complete version space is with high probability a random subcube, and its number of unresolved coordinates converges to a Poisson random variable with mean $e^{-x}$. This geometry separates two notions that are often conflated in learning. The data may permit an optimal learner to recover the planted target before they determine it uniquely. The limiting uniqueness probability is $\exp (-e^{-x})$, whereas Bayes-optimal and minimax exact recovery converge to $\exp (-e^{-x}/2)$. At every fixed success level, uniqueness therefore requires asymptotically $\ln 2(2^k-1)n/k$ more clauses. The same window law persists under bounded non-uniform coordinate coverage. Equal marginal coverage minimizes the occupancy clock exactly at every finite sample size, and uniform weights attain it within the conditional product family. Calibrations across five further learning families and finite-size experiments show when total information predicts the boundary and when coordinate coverage becomes decisive. Together, the theory and experiments show that the learning boundary for exact recovery depends on both the amount of input information and its allocation across hidden coordinates.