Before revision:  This improves over a prior algorithm of Kolmogorov (2018 ) which computes the single point estimate Z(\beta _{\max) using } O( \frac{q{\varepsilon^2}}  ) samples.
After revision:  This improves over a prior algorithm of Huber (2015 ) which computes the single point estimate Z(\beta _{\max) using } O( \frac{q{\varepsilon^2}} ) samples.