Linjär regression är en av de vanligaste teknikerna i dataanalys. Med tanke på en stor samling prover som består av funktioner x x x och en etikett y, används linjär regression för att hitta den bästa förutsägelsen av etiketten som en linjär kombination av funktionerna. Det är dock också vanligt att använda linjär regression för sin förklarande förmåga snarare än att märka förutsägelser. Vanliga minsta kvadrater (OLS) används ofta i statistik för att fastställa ett samband mellan ett attribut (t.ex. kön) och en etikett (t.ex. inkomst) i närvaro av andra (potentiellt korrelerade) egenskaper. OLS använder linjär regression för att uppskatta korrelationen mellan etiketten och en funktion x j på en given datauppsättning; och sedan, under antagandet av en viss slumpmässig generativ modell för data, OLS ger ett intervall på reals som sannolikt kommer att innehålla korrelationen mellan y och x j i den underliggande fördelningen (ett konfidensintervall ). När detta intervall inte skär ursprunget, kan vi förkasta nollhypotesen eftersom det är troligt att x j verkligen har en icke-noll korrelation med y. Vårt arbete syftar till att uppnå liknande garantier för data under differentiell integritet. Vi använder Gaussian Johnson-Lindenstrauss transform, som har visat sig tillfredsställa differential integritet om den givna data har stora singular värden [BBDS12]. Vi analyserar resultatet av att projicera data med hjälp av JL transform under OLS-modellen och visar hur man ungefärligt konfidensintervall med endast de projicerade data. Vi band också antalet prover som behövs för att förkasta nollhypotesen med differentiell integritet, när data dras i.i.d från en multivariat Gaussian. När inte alla enskilda värden av data är tillräckligt stora, ändrar vi inmatningen och ökar dess singular värden och sedan projicera den med hjälp av en JL-transform. Således våra projicerade data ger en approximation för Ridge Regression problem - en variant av linjär regression som använder en l 2 -regularisering term. Vi ger villkor under vilka det legaliserade problemet fortfarande är till hjälp vid upprättandet av samband. Sedan de första dagarna av differential integritet, var dess främsta mål att designa integritet bevara versioner av befintliga tekniker för dataanalys. Det är därför inte förvånande att flera av de första differentierade privata algoritmerna var maskininlärningsalgoritmer [BDMN05, KLN + 08] och bland dem privat linjär regression [CMS11, KST12, BST14]. När allt kommer omkring är linjär regression extremt vanligt i dataanalys. Det finns dock två nackdelar med den befintliga tekniken. Först (och kanske lättare att förklara), är att de ovan nämnda algoritmerna är utformade för ett enda linjärt regressionsproblem: varje provpunkt består av (x x x • y) där x x x betecknar problemets egenskaper och y betecknar etiketten. Ändå i en databas D där varje prov har d attribut, är vi fria att välja någon egenskap som etikett och någon delmängd av de återstående attributen som problemfunktioner. På så sätt kan D möjliggöra exp(d) olika linjära regressionsproblem. Naïvely kör ovan nämnda algoritmer exponentiellt många gånger körs in i det oundvikliga problemet med integritet-utility kompromiss: den extra buller är så stor att den utplånar någon nytta i svaret. 1 Den andra och den allvarligare nackdelen av det befintliga arbetet med differentialt privat linjär regression ligger i dess nytta analys. Nyttoanalysen i dessa verk begränsar det förväntade l 2-avståndet mellan de linjära koefficienter som finns i standardalgoritmen och de koefficienter som finns i den integritetsbevarande versionen. Detta är motiverat ur ett maskininlärningsperspektiv, eftersom gränserna för skillnaden i estimatorer översätter till felgränser vid förutsägelse (eller på förlustfunktionen). Men lika intressanta och (mycket) icke-triviala som de är, sådana gränser är av liten nytta i situationer där man använder linjär regression för att fastställa korrelationer snarare än att förutsäga etiketter. I statistiklitteraturen är linjär regression en teknik som används för att bestämma korrelationen mellan en variabel och ett utfall, särskilt i närvaro av andra faktorer, i modellen Ordinary Least Squares (OLS). 2 Samhällsvetenskapen har använt OLS i nästan ett århundrade, i verk som sträcker sig från att avgöra om katoliker tenderar att rösta på demokraterna i 1932 valet [GG35], till verk som kvantifierar effekten av utbildning på inkomst [Car99], till moderna verk som fastställer att Tweeting hjälper till att bli vald för ämbete [DMBR13]. Sådana arbeten syftar inte till att använda linjär regression för att förutsäga märkningen på ett nytt omärkt parti prover. Snarare syftar de till att fastställa förekomsten av ett starkt samband mellan etiketten och något inslag. Naturligtvis är det viktigt att i sådana verk skydda privatlivet för de individer som bidrog till uppgifterna. För att bestämma att en viss variabel x j är positivt (sp. negativt) korrelerat med ett utfall y, OLS antar en modell där resultatet y är en bullrig version av en linjär kartläggning av alla variabler: y = β β β · x x x + e (med e betecknande slumpmässiga Gaussian buller) för vissa förutbestämda och okända β β β β. Sedan, givet många prover (x x x i, y i ) OLS etablerar två saker: (i) när man monterar en linjär funktion för att bäst förutsäga y från x x x över provet (via computingβ β = i x x x x x T i −1 (i y i x x x i )) är koefficientenβ j positiv (sp. negativ), och ii) förtroendet för att ha β j inte långt från den sanna β j är högt. I själva verket, crux i OLS är att definiera den lämpliga konfidensintervall - intervallet 1 I själva verket, Ullman [Ull15] har utarbetat en lösning på detta problem baserat på Iterative-Database Construction av [GRU12], men denna lösning fungerar i den mer cumbersome online-modellen och kräver exponentiellt körtid för curator; medan vår teknik är beräkningsbart dragbar och fungerar i offline-modellen. 2 Och så, i detta papper, drar vi en skillnad mellan "linjär regression", genom vilken vi hänvisar till maskininlärning teknik för att hitta en specifik estimator för en specifik förlustfunktion; och "Ordinary Least Squares" modell, genom vilken vi hänvisar till en specifik generativ modell för data som löses med hjälp av linjär regressionsteknik. Algoritm 1: Utgående en privat Johnson-Lindenstrauss projektion av en matris. Inmatning: En matris A  till R n×d och en gräns B > 0 på l 2 -normen på varje rad i A. Integritetsparametrar:  till, δ > 0. Parameter r som anger antalet rader i den resulterande matrisen.
I samband med modellkoefficienter studerade Sheffet REF (, δ)-differentierat private Ordinary Least Squares Regression (OLS) och genererade konfidensintervall för parametrarna.
Differentially Private Ordinary Least Squares
{'venue': 'ICML 2017', 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}