Since, by definition,ˆr(x0,) is the radius of the smallest ball with1/2+ probability mass of f(x0 +P)overall possible centers inRk and ˆRisthe radius of the smallest such ball centered at ˆf(x),wemusthaveˆr(x0,) ˆR. Consider the smallest ballB(z0,ˆr(x, 1)) that encloses at least1/2 + 1 probability mass of f(x+P). We sample then points in batches and compute the distanced(ci,zj) for each pair of candidate centerci andpointzj inabatch. Also, with high probability, at least half of then samples will lie in this ball too. Ignoring the probability that none of then0 points lie inside the ball, we can derive the following versionoftheorem3: Theorem1.