Show simple item record

dc.contributor.authorNissim, Kobbien_US
dc.contributor.authorSmith, Adamen_US
dc.contributor.authorSteinke, Thomasen_US
dc.contributor.authorStemmer, Urien_US
dc.contributor.authorUllman, Jonathanen_US
dc.date2018-09-01
dc.date.accessioned2019-09-18T13:27:43Z
dc.date.available2019-09-18T13:27:43Z
dc.date.issued2018-12-01
dc.identifier.citationKobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman. 2018. "The Limits of Post-Selection Generalization." Advances in Neural Information Processing Systems 31 (NIPS 2018)
dc.identifier.urihttps://hdl.handle.net/2144/37836
dc.description.abstractWhile 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.en_US
dc.subjectData structures and algorithmsen_US
dc.subjectStatisticsen_US
dc.subjectComputer scienceen_US
dc.titleThe limits of post-selection generalizationen_US
dc.typeConference materialsen_US
dc.description.versionPublished versionen_US
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: No embargoen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US
dc.identifier.mycv467001


This item appears in the following Collection(s)

Show simple item record