I am doing some work in the area of Property Testing, as in Goldreich, Goldwasser, and Ron (2008) or the textbook Introduction to Property Testing (Goldreich). In this framework, I run a test to see whether a function either a) has a property, or b) is $\epsilon$-far from having the property. The tester is guaranteed to always accept as long as the function has the property (the completeness requirement), while it rejects with probability $>1-\delta$ if the property is $\epsilon$-far from having the property.
Now, suppose I run several tests at several values of $\epsilon,\delta$ … say $\epsilon,\delta \in \{.01,.1,.5\}$. The idea of such a procedure would be to see roughly at what values of $\epsilon,\delta$ the test is likely to pass, and perhaps get some kind of "greatest lower bound" on the distance of our function to the property. The reason this seems necessary is that in practice with property testing (something that isn't discussed much in the literature), the number of trials I need to run before hitting a failure varies widely. This could mean that from a single test, the lower bound on the distance will vary widely from test to test.
This naturally motivates us to use multiple tests. But what is the best way to do this? One approach would be to sweep over multiple values of $\epsilon, \delta$. But if we do this without considering the context of all of the tests, our results looks noisy: it is entirely possible that a given test at $(\delta,\epsilon)=(.01,.01)$ accepts, while a test at a lower significance level and greater proximity like $(.1,.1)$ rejects.
One simple way we could get rid of any noise in a multiple-test scenario (or side-step it), would be to just have all of our tests for different values of $\epsilon,\delta$ be from a shared rolling test. In other words, if the query complexity of a test with $(\delta, \epsilon)=(.5,.5)$ is 50, we run the test up to 50 times, and if we want to test at $(.1,.1)$ which has say 500 q.c., we just keep the test going. i.e. run up to 450 new tests. I guess this change is a simple fix that will make the tables look more "stable" and easier to interpret.
But it still doesn't really solve an underlying issue, which is that the results of property testing seem to be fairly noisy. We are running a bunch of trials up to some query complexity $m$ and then making a pass/fail judgement for each $\epsilon,\delta$ based on that — but one would think we could do better, and actually combine these trials somehow. For example, maybe we could think of the test as a Poisson process and try to estimate the $\lambda$, and then we have a distribution for survival times that would imply a certain probability of success for any given "$\epsilon, \delta$" (which just maps 1-to-1 with a certain test length). Is there some way we could use that to "smooth out" the results? Or maybe we could use it to select some "greatest lower bound" on the distance, i.e. some lower bound on the distance that is as high as possible and the lower bound still holds with high probability?
Or am I thinking about this the wrong way?
If anyone has any insights on to how to stabilize property tests to make them useful, it would be greatly appreciated!
