The Limits of Post-Selection Generalization
While statistics and machine learning offers numerous methods for ensuring generalization, these methods often fail in the presence of post selection-the common practice in which the choice of analysis depends on previous interactions with the same dataset. A recent line of work has introduced powerful, general purpose algorithms that ensure a property called post hoc generalization (Cummings et al., COLT'16), which says that no person when given the output of the algorithm should be able to find any statistic for which the data differs significantly from the population it came from. In this work we show several limitations on the power of algorithms satisfying post hoc generalization. First, we show a tight lower bound on the error of any algorithm that satisfies post hoc generalization and answers adaptively chosen statistical queries, showing a strong barrier to progress in post selection data analysis. Second, we show that post hoc generalization is not closed under composition, despite many examples of such algorithms exhibiting strong composition properties.
This paper demonstrates some of the limits of mechanisms satisfying post hoc generalization, which guarantees accuracy in the adaptive data analysis setting.  They show both an information-theoretic and computational lower bounds for sample complexity, and then show that mechanisms satisfying post hoc generalization do not in the worst case compose non-trivially.  These results tie up some loose ends in adaptive data analysis, e.g. closing the previously-open gap in sample complexity for statistical queries, and gives a more complete picture of what is possible in this area.  On the other hand, I would not call this the most clearly written paper.  In particular, there is very little discussion or overview of the proofs.  I recognize how difficult this is to do given the page limit constraints, but since a fair amount of the proofs are put into the appendix anyway, I consider it very important to communicate the ideas contained within the proofs rather than highlighting the technical details, as is done here.  Nor does this paper highlight the difference between their strategy and what is contained in the previous literature.  The basic strategy, after all, remains the same as in the lower bounds established in previous literature:  Algorithm 2 attempts to uncover the sample given to M, then asks a query that M will overfit on, plus using fingerprinting, etc.  What exactly is the new idea here?  Also, to be blunt, why is the result that post hoc generalization does not compose interesting?  After all, we know that we can achieve O(\sqrt{k}/\epsilon^2) sample complexity using differential privacy, and to achieve a better sample complexity, this paper shows that we can't guarantee post hoc generalization at all.  It seems that when it comes to statistical queries, post hoc generalization is a bit besides the point, no?  A few very small things: - Would be helpful to be much more explicit about sample complexity for uniform convergence, that way the reader can compare this to your results. (line 48) - Algorithm 2:  A_1 should start empty: no one has been accused yet. - Algorithm 2:  \tilde{q}_i^j presumably needs to lose the tilde.  Edit (post author response):  On the new idea in your results:  I appreciate your attempt to stress the idea of an approximate attack rather than an exact attack.  This seems like you're pointing out that a (very similar) attack, even if it doesn't work as well, still works well enough, which may or may not be of sufficient interest/novelty for your readers. On the interesting-ness of composition:  AFAIK, there's no good way to directly show that an algorithm satisfies post hoc generalization without also satisfying DP, information bounds, or the like.  This means it seems rather unlikely that you would actually need composition without already having stronger assumptions on the algorithms that you would like to compose, even if that assumption isn't DP.  Which in turn means I don't know where this result would likely be relevant.