Vi inför ett nytt generiskt ramverk för privat dataanalys. Målet med en privat dataanalys är att ge ut aggregerad information om en datauppsättning samtidigt som man skyddar integriteten för de individer vars information datamängden innehåller. Vårt ramverk tillåter en att släppa funktioner f av data med instans-baserade additiva buller. Det vill säga, bullernivån bestäms inte bara av den funktion vi vill släppa, utan också av själva databasen. En av utmaningarna är att se till att bullernivån inte läcker ut information om databasen. För att ta itu med detta kalibrerar vi brusstorleken till den smidiga känsligheten av f på databasen x - ett mått på variabiliteten av f i närheten av instansen x. Det nya ramverket utökar avsevärt tillämpligheten av utdata perturbation, en teknik för att skydda individers integritet genom att lägga till en liten mängd slumpmässigt buller till den publicerade statistiken. Såvitt vi vet är detta den första formella analysen av effekten av exempelbaserat buller i samband med datasekretess. Vårt ramverk väcker många intressanta algoritmiska frågor. Nämligen, för att tillämpa ramen måste man beräkna eller approximera den smidiga känsligheten hos f på x. Vi visar hur man gör detta effektivt för flera olika funktioner, inklusive medianen och kostnaden för minsta spanning träd. Vi ger också ett generiskt förfarande baserat på provtagning som tillåter en att släppa f (x) exakt på många databaser x. Detta förfarande är tillämpligt även när ingen effektiv algoritm för approximering av mjuk känslighet för f är känd eller när f ges som en svart låda. Vi illustrerar förfarandet genom att tillämpa det på k-SED (k-means) klusterbildning och lärande blandningar av Gaussians.
Privat lärande blandningar av Gaussians ansågs i REF.
Smooth sensitivity and sampling in private data analysis
{'venue': "STOC '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}