I detta papper ger vi effektiva algoritmer och lägre gränser för att lösa de tunga hitters problem samtidigt som differential integritet i den fullt distribuerade lokala modellen. I denna modell, det finns n partier, som var och en har ett enda element från ett universum av storlek N. De tunga hitters problem är att hitta identiteten hos de vanligaste elementet som delas mellan n partier. I den lokala modellen finns det ingen betrodd databasadministratör, och därför måste algoritmen interagera med var och en av n-parterna separat, med hjälp av ett differentialt privat protokoll. Vi ger snäva informationsteoretiska övre och nedre gränser för exaktheten som detta problem kan lösas med i den lokala modellen (som ger en separation mellan den lokala modellen och den mer gemensamma centraliserade modellen för integritet), samt beräkningseffektiva algoritmer även i fall där datauniversum N kan vara exponentiellt stort. Tänk på problemet med en webbplatsadministratör som vill veta vad hans vanligaste trafikkällor är. Var och en av n besökare anländer med en enda hänvisning webbplats: namnet på den senaste webbplats som hon besökte, som är hämtad från ett stort universum N av möjliga hänvisningsplatser (N här är uppsättningen av alla webbplatser på internet). Det finns värde i att identifiera den mest populära referenssidan (den tunga hitter ): webbplatsadministratören kan bättre skräddarsy innehållet på sin webbplats, eller bättre fokusera sina marknadsföringsresurser. Å andra sidan kan identiteten på varje individs referenssida vara pinsamt eller på annat sätt avslöjande, och är därför privat information. Vi kan därför föreställa oss en värld där denna information måste behandlas "privat". I denna situation kommunicerar besökarna dessutom direkt med servrarna på de webbplatser som de besöker: d.v.s. Det finns ingen tredje part som kan vara betrodd med att aggregera alla uppgifter på webbplatsen och tillhandahålla sekretessbevarande statistik till webbplatsens administratör. I denna inställning, hur väl kan webbplatsadministratören uppskatta den tunga hitter samtidigt kunna ge formella integritetsgarantier till sina besökare? Denna situation kan mer allmänt modelleras som de tunga hitters problem under begränsningen av differential integritet. Det finns n individer i... [n] som var och en är associerad med ett element v i... N av några stora datauniversum N. Den tunga hitter är den mest förekommande element x... N bland de som {v 1,. .., v n }, och vi skulle vilja kunna identifiera detta element, eller en som inträffar nästan lika ofta som den tunga hitter. Dessutom vill vi lösa detta problem 1 samtidigt som vi bevarar den differentierade integriteten i den helt fördelade (lokala) modellen. Vi definierar detta formellt i avsnitt 2, men grovt taget, en algoritm är differentialt privat om förändringar i data hos enskilda individer endast resulterar i små förändringar i utdatadistributionen av algoritmen. Dessutom, i den fullt fördelade inställningen, måste varje individ (som kan ses som en databas av storlek 1) interagera med algoritmen oberoende av alla andra individer, med hjälp av en differentialt privat algoritm. Detta är i motsats till den mer allmänt studerade centraliserade modellen, där en betrodd databasadministratör kan ha (exakt) tillgång till alla data, och samordna en privat beräkning. Vi studerar detta problem både ur informationsteoretisk synvinkel och ur synvinkeln effektiva algoritmer. Vi säger att en algoritm för de privata tunga hitters problem är effektiv om det körs i tid poly(n, log N ): d.v.s. polynom i databasstorleken, men endast polylogaritmisk i universumstorleken (dvs. i vad vi betraktar som det mest intressanta intervallet av parametrar, kan universum vara exponentiellt större än storleken på databasen). Vi ger tät information teoretiska övre och nedre gränser för exaktheten som den tunga hitter kan hittas i den privata distribuerade inställningen (skilja denna modell från den privata centraliserade inställningen), och ger flera effektiva algoritmer som uppnår bra, även om informations-teoretiskt suboptimal noggrannhet garanterar. Vi lämnar öppen frågan om effektiva algoritmer exakt kan matcha den information teoretiska gränser vi bevisar för de privata tunga hitters problem i den distribuerade inställningen. I detta avsnitt sammanfattar vi våra resultat. De gränser vi diskuterar här är informella och döljer många av de parametrar som vi ännu inte har definierat. De formella gränserna anges i papperets huvuddel. För det första tillhandahåller vi en teoretisk karakterisering av den noggrannhet till vilken någon algoritm (oberoende av beräkningsbegränsningar) kan lösa de tunga hitters problem i den privata distribuerade inställningen. Vi säger att en algoritm är α-korrekt om den returnerar ett universumelement som inträffar med frekvensen som mest en additiv α mindre än den verkliga tunga hittern. I den centraliserade inställningen, en enkel tillämpning av den exponentiella mekanismen [MT07] ger en α-korrekt mekanism för den tunga-hitters problem där α = O (log  på N), som i synnerhet, är oberoende av antalet individer n. Däremot visar vi att i den fullt distribuerade inställningen, ingen algoritm kan vara α-korrekt för α =  på n) även i det fall  på N = 2. Omvänt ger vi en nästan matchande övre gräns (och en algoritm med run-time linjär i N ) som är α-noggrannhet för α = O ( ε n log N ). Nästa, Vi anser effektiva algoritmer som körs i tiden endast polylogaritmiska i universumets storlek. Här, vi ger två algoritmer. En är en tillämpning av en komprimerad sensoralgoritm av Gilbert et al [GLPS10], som är α-korrekt för α = Õ(n 5/6 log N log N ). Sedan ger vi en algoritm baserad på grupptestning med hjälp av pairwise oberoende hash funktioner, som har en ojämförlig gräns. Ungefärligt, garanterar det att returnera exakt tung hitter (d.v.s. α = 0) när den tunga hitterns frekvens är större än l 2-normen för de återstående elementens frekvenser. Beroende på hur dessa frekvenser fördelas kan detta motsvara en gräns för α-noggrannhet för α som sträcker sig var som helst mellan den optimala α = O( ε n) till α = O(n). 2 Våra övre gränser, både informationsteoretiska, och de med effektiva algoritmer, är baserade på den allmänna tekniken för slumpmässig projektion och koncentration av mått. För att bevisa vår information teoretiska övre gräns, Vi observerar att för att hitta den tunga hitter, kan vi se den privata databasen som en histogram v i N dimensional utrymme. Sedan är det tillräckligt att hitta indexet i [N] av universum element som maximerar v, e i, där e i är i'th standard bas vektor. Både v och varje e i har liten l 1 -norm, och så var och en av dessa inre produkter kan ungefär bevaras genom att ta en slumpmässig projektion in i Õ(log N ) dimensionsutrymme. Dessutom kan vi projicera varje individs data in i detta utrymme oberoende i den fullt distribuerade inställningen, vilket medför en förlust av endast O ( ε n) i noggrannhet. Denna mekanism, dock, är inte effektiv, eftersom för att hitta den tunga hitter, måste vi räkna upp genom alla  på N grund vektorer e i för att hitta den som maximerar den inre produkten med den projicerade databasen. Liknande idéer leder till våra effektiva algoritmer, om än med sämre precisionsgarantier. Till exempel, i vår första algoritm, tillämpar vi tekniker från komprimerad avkänning till den projicerade databasen för att återställa (ungefär) den tunga hitter, snarare än att kontrollera bas vektorer direkt. I vår andra algoritm, tar vi en projektion med hjälp av en viss familj av parvis oberoende hash funktioner, som är linjära funktioner data universum element. På grund av denna linjäritet kan vi effektivt "invertera" projektionsmatrisen för att hitta den tunga hittern. Vår nedre gräns skiljer den distribuerade inställningen från den centraliserade inställningen genom att tillämpa ett antikoncentrationsargument. Ungefärligt sett observerar vi att i den helt distribuerade inställningen, om enskilda dataelement valdes enhetligt i.i.d. från datauniversumet N, sedan även efter konditionering på meddelanden som utbyts med någon differentialt privat algoritm, förblir de självständigt distribuerade, och ungefär enhetligt. Därför, av Berry-Esseen teorem, även efter någon algoritm beräknar sin uppskattning av den tunga hitter, är den verkliga fördelningen över räkna fortfarande ungefär normalt distribueras. Eftersom den Gaussiska distributionen uppvisar starka antikoncentrationsegenskaper, gör det möjligt för oss att villkorslöst ge en lägre gräns för vilken algoritm som helst i den fullt distribuerade inställningen. Differentiell integritet infördes i en sekvens av papper som kulminerar i [DMNS06], och har sedan dess blivit standard "lösningskoncept" för integritet i den teoretiska datavetenskap litteratur. Det finns vid det här laget en mycket stor litteratur om detta ämne, som är för stor för att sammanfattas här. Istället fokuserar vi bara på det mest närbesläktade arbetet, och hänvisar den nyfikna läsaren till en undersökning av Dwork [Dwo08]. Merparten av litteraturen om differential integritet fokuserar på den centraliserade modellen, där det finns en betrodd databasadministratör. I detta dokument fokuserar vi på den lokala eller helt distribuerade modellen, som infördes av [KLN + 08], där varje individ har sina egna data (dvs. Det finns n databaser, var och en av storlek 1), och algoritmen måste interagera med var och en på ett differentierat privat sätt. Det har varit lite arbete i denna mer restriktiva modell-problemen att lära [KLN + 08] och frågeutgåva [GHRU11] i den lokala modellen är väl förstådd 1, men endast upp till polynom faktorer 1 Grovt, den uppsättning begrepp som kan läras i den lokala modellen ges polynom prov komplexitet är lika med den uppsättning begrepp som kan läras i SQ-modellen med tanke på polynom frågekomplexitet [KLN + 08], och uppsättningen av frågor som kan släppas i den lokala modellen givet polynom prov komplexitet är lika med uppsättningen av begrepp som kan agnostiskt lärts i SQ-modellen givet polynomet frågekomplex [GHRU11], men polynomials
Slutligen bygger våra effektiva protokoll på idéer från den stora litteraturen om strömmande algoritmer och kompressiv avkänning (liksom de effektiva protokollen från Hsu et al. Om det inte finns några uppgifter som tyder på att det finns en risk för att det finns en risk för att det uppstår en allvarlig risk för en allvarlig störning, ska den behöriga myndigheten i den medlemsstat där den behöriga myndigheten har sitt säte underrätta den behöriga myndigheten i den medlemsstat där den behöriga myndigheten har sitt säte om detta.
Distributed Private Heavy Hitters
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}