Vi studerar avvägningar mellan noggrannhet och integritet i samband med linjära frågor över histogram. Detta är en rik klass av frågor som inkluderar beredskapsplaner och intervall frågor och har varit i fokus för en lång rad arbete. För en given uppsättning d linjära frågor över en databas x  på R N, försöker vi hitta den differentialt privata mekanismen som har den minsta genomsnittliga kvadrat fel. För ren differential integritet, [5, 32] ger en O(log 2 d) approximation till den optimala mekanismen. Vårt första bidrag är att ge en effektiv O(log 2 d)-tillnärmningsgaranti för (ε, ε)-differentierad integritet. Vår mekanism lägger noga utvalda korrelerade Gaussian buller till svaren. Vi bevisar dess approximation garanti i förhållande till den ärftliga avvikelsen lägre gränsen av [44], med hjälp av verktyg från konvex geometri. Vi betraktar därefter det glesa fallet när antalet frågor överstiger antalet individer i databasen, dvs.. när d > n x 1. De lägre gränserna som används i den tidigare approximationsalgoritmen gäller inte längre - i själva verket är bättre mekanismer kända i denna inställning [7, 27, 28, 31, 49]. Vårt andra huvudsakliga bidrag är att ge en effektiv (ε, ε)-differentiellt privat mekanism som, för varje given fråga uppsättning A och en övre gräns n på x 1, har genomsnittliga kvadratfel inom polylog(d, N ) av den optimala för A och n. Denna approximation uppnås genom att koppla Gaussian buller addition strategi med linjär regression över 1 boll. Dessutom visar vi en liknande polylogaritmisk approximation garanti för den optimala ε-differentiellt privata mekanismen i denna glesa inställning. Vårt arbete visar också att för godtycklig räkning frågor, dvs... A med poster i {0, 1}, det finns en ε-differentiellt privat mekanism med förväntat fel Õ( ε n) per fråga, förbättra på Õ(n 2 3 ) bundet av [7] och matcha den lägre bundet underförstått [15] upp till logaritmiska faktorer. Sambandet mellan den ärftliga diskrepansen och integritetsmekanismen gör det möjligt för oss att härleda den första polylogaritmiska approximationen till den ärftliga diskrepansen hos en matris A.
Nikolov m.fl. REF utvidgar resultatet av [23] om att besvara linjära frågor över ett histogram till fallet med (, δ)-differentiell integritet.
The geometry of differential privacy: the sparse and approximate cases
{'venue': "STOC '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}