Sammansättning är en av de viktigaste egenskaperna hos differential integritet (DP), eftersom det gör det möjligt för algoritm designers att bygga komplexa privata algoritmer från DP primitiver. Vi överväger exakta sammansättningsgränser för den totala integritetsförlusten för exponentiella mekanismer, en av de grundläggande kategorierna av mekanismer i DP. Vi ger tydliga formuleringar av den optimala integritetsförlusten för både adaptiva och icke-adaptiva inställningar. För den icke-adaptiva inställning där varje mekanism har samma integritetsparameter, ger vi en effektivt beräkningsbar formulering av den optimala integritetsförlusten. Dessutom visar vi att det finns en skillnad i integritetsförlusten när den exponentiella mekanismen väljs adaptivt jämfört med icke-adaptivt. Enligt vår kunskap var det tidigare okänt om det fanns en sådan lucka för alla DP-mekanismer med fasta integritetsparametrar, och vi demonstrerar gapet för en allmänt använd klass av mekanism i en naturlig miljö. Vi förbättrar sedan på de mest kända övre gränserna för adaptiv sammansättning av exponentiella mekanismer med effektivt beräknande formuleringar och visa förbättringen.
På senare tid har REF härlett skarpa sammansättningsgränser för den totala integritetsförlusten för exponentiella mekanismer.
Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}