Making Progress Based on False Discoveries. (arXiv:2204.08809v1 [cs.LG])

We consider the question of adaptive data analysis within the framework of
convex optimization. We ask how many samples are needed in order to compute
$\epsilon$-accurate estimates of $O(1/\epsilon^2)$ gradients queried by
gradient descent, and we provide two intermediate answers to this question.

First, we show that for a general analyst (not necessarily gradient descent)
$\Omega(1/\epsilon^3)$ samples are required. This rules out the possibility of
a foolproof mechanism. Our construction builds upon a new lower bound (that may
be of …

arxiv discoveries false making progress