After reading the reviews and authors' responses, it seems the only main concern raised is the lack of experiments. My opinion is that while experiments would be nice to have, the lack of experiments is not a significant concern if the theoretical results are strong enough. In my own assessment of the paper, I find the theoretical results to be indeed quite a strong contribution to the field (they provide the first algorithm to match the PAC lower bound, for a problem which has quite a few previous works). The reviewers seem to agree with this point in their reviews. I, therefore, recommend that the paper be accepted.