- Low Memory Realizability Testing Algorithms under the Streaming Model
- Project Year:
2025
- REU Student (s):
Lauren Knopp | University of Vermont VT
- Student 1 Institution:
University of Vermont
- Project Mentor:
Sumegha Garg
- Project Mentor Area:
Computer Science
- Project Abstract:
In learning theory, realizability is a property a distribution holds if there exists a hypothesis. We say that a distribution ( X x Y ) where X is a set of attribute vectors and Y ) is realizable if there exists a hypothesis within a class of hypotheses H such that the true error of the selected hypothesis is 0. When we aim to determine whether a specific distribution is realizable, using property testing can help us tolerantly test for realizability. In this paper, I introduce two different algorithms that explore efficient low-memory strategies in both the strict realizability testing case (aiming to accept only when true realizability is met) and the tolerant realizability testing case (accepting when hypothesis classes contain a hypothesis that is within ε from realizable, and rejecting all hypothesis classes that only contain hypotheses that are at least ε-far from realizable). I also provide additional future directions and conjectures about low memory realizability testing.
