Abstract
In statistical learning theory, consistency typically refers to the convergence of error rates to zero as sample sizes increase. However, a more stringent and often more desirable requirement is "eventually almost surely" (e.a.s.) predictability: the guarantee that a learner will make only a finite number of errors over an infinite horizon. This paper characterizes the conditions under which e.a.s. predictability is possible in both supervised and unsupervised settings. We demonstrate that this property is intrinsically linked to structural regularization through nested model classes. Furthermore, we explore e.a.s. learnability—the ability to not only predict correctly but also to identify, via a stopping rule, when no further errors will occur. Our results provide a complete characterization for i.i.d. processes and offer novel applications in matrix inference.
Introduction
Most machine learning paradigms are concerned with minimizing loss or ensuring that the probability of error vanishes in the limit. While these are powerful guarantees, they do not preclude the possibility of a learner making infrequent mistakes indefinitely. In high-stakes environments—such as medical diagnostics or structural engineering—or in the pursuit of fundamental mathematical truths, we may require a stronger guarantee: that the learner will eventually stop making mistakes altogether.
This research, presented at AISTATS 2021, formalizes this requirement as "eventually almost surely" (e.a.s.) predictability. A model class is e.a.s. predictable if there exists an algorithm that, when presented with an infinite sequence of observations, incurs a total binary (0-1) loss that is finite with probability 1, regardless of which model within the class is generating the data.
The Framework of E.A.S. Predictability
The authors model the problem as an online game between "Nature" and a "Learner." Nature selects a probability model from a known class $\mathcal{P}$, and the Learner must predict properties of the model or future observations. After each prediction, the Learner receives feedback in the form of a binary loss. This work unifies and extends several historical threads of research, including Gold’s (1967) "language identification in the limit" and Cover’s (1973) work on predicting irrationality.
The Role of Structural Regularization
A central finding of the paper is that e.a.s. predictability is fundamentally tied to the structure of the model class. Specifically, a class is e.a.s. predictable if and only if it can be decomposed into a sequence of nested subclasses: $$P_1 \subset P_2 \subset P_3 \subset \dots$$ where each subclass $P_n$ is "uniformly predictable."
This decomposition mirrors the principle of Structural Risk Minimization (SRM). The Learner effectively navigates these layers, starting with the simplest hypothesis ($P_1$) and only moving to more complex models ($P_n$) as the accumulated data provides sufficient evidence. This provides a formal, theoretical justification for the necessity of regularization: to guarantee a finite number of errors, one must be able to stratify the problem by complexity.
From Predictability to Learnability
The paper distinguishes between merely making a finite number of errors and "knowing" when the errors have ceased. This leads to the definition of e.a.s. learnability. A class is e.a.s. learnable if, in addition to being predictable, there exists a universal "stopping rule"—a signal that identifies, to any given confidence level, that no more errors will be made.
For i.i.d. (independent and identically distributed) samples, the authors provide a complete characterization: e.a.s. learnability is possible if and only if the model class can be decomposed into identifiable and predictable components. This highlights a "stopping rule gap"—the requirement for identifiability adds a layer of difficulty beyond simple predictability. While the Learner might eventually stop making mistakes, they cannot always know for certain that they have reached that point without specific structural properties in the model class.
Applications: Matrix Inference and Topological Conditions
To demonstrate the utility of the framework, the authors apply it to the problem of inferring properties of an expected matrix $E[X]$ from binary samples $X_i$. They prove that several complex properties are e.a.s. predictable, including:
- Determining the rank of the expected matrix.
- Identifying if the matrix is singular.
- Determining if eigenvalues have a multiplicity greater than one.
This is particularly notable because the individual samples $X_i$ might always be full-rank, yet the algorithm can eventually determine the rank of the underlying mean with only finitely many errors. Furthermore, the paper provides a positive answer to a long-standing conjecture by Dembo and Peres (1994) regarding the topological conditions ($F_\sigma$-separability) required for hypothesis testing with finite errors.
Conclusion and Future Directions
This work provides a rigorous foundation for understanding the limits of learning with finite errors. By characterizing e.a.s. predictability and learnability, the authors bridge the gap between classical identification theory and modern statistical learning.
However, several avenues remain open. While the i.i.d. case is fully characterized, the conditions for e.a.s. learnability in non-i.i.d. processes (such as general Markov chains) are not yet fully understood. Additionally, the stopping rules derived are existence proofs; developing "fast" or optimal stopping rules for specific practical applications remains a challenge for future research. Finally, specific mathematical properties, such as whether matrix diagonalizability is e.a.s. predictable, remain unresolved.
Summary updated