I detta dokument initierar vi en principiell studie av hur generalisering egenskaper ungefärlig differential integritet kan användas för att utföra adaptiv hypotes testning, samtidigt som statistiskt giltiga p-värde korrigeringar. Vi gör detta genom att observera att garantierna för algoritmer med begränsad ungefärlig maxinformation är tillräckliga för att korrigera p-värdena för adaptivt valda hypoteser, och sedan genom att bevisa att algoritmer som uppfyller (, δ)-differential integritet har avgränsat ungefärlig max-information när deras ingångar hämtas från en produktdistribution. Detta utökar avsevärt den kända kopplingen mellan differentiell integritet och max-information, som tidigare bara var känd för att hålla för (ren) (, 0)-differentiell integritet. Det utökar också vår förståelse av maxinformation som ett delvis enande mått som styr generaliseringsegenskaperna hos adaptiva dataanalyser. Vi visar också en lägre gräns, som bevisar att (trots den starka sammansättningen egenskaper av max-information), när data hämtas från en produktdistribution, (, δ)differentiellt privata algoritmer kan komma först i en sammansättning med andra algoritmer som uppfyller max-information gränser, men inte nödvändigtvis sekund om sammansättningen krävs för att själv uppfylla en icke-trivial max-information bundna. Detta innebär särskilt att kopplingen mellan (, δ)-differentiell integritet och max-information endast innehåller indata från produktdistributioner, till skillnad från kopplingen mellan (, 0)-differentiell integritet och max-information.
Uppfattat. REF visade att ungefärliga differentialt privata algoritmer också har låg approximativ max-information, och att begreppet ungefärlig max-information fångar generalisering egenskaper (om än med något sämre parametrar) av differentially privata algoritmer (ren eller ungefärlig).
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing
{'venue': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}