Abstract-Vi utvecklar teori för att använda heuristik för att lösa beräknings svårt problem i differential integritet. Heuristiska metoder har haft enorm framgång i maskininlärning, där prestanda kan utvärderas empiriskt. Men integritetsgarantier kan inte bedömas empiriskt, och måste bevisas - utan att göra heuristiska antaganden. Vi visar att inlärningsproblem över breda grupper av funktioner - de som har polynomiskt stora universella identifieringsset - kan lösas privat och effektivt, förutsatt att det finns ett icke-privat orakel för att lösa samma problem. Vår första algoritm ger en integritetsgaranti som är beroende av oraklets korrekthet. Vi ger sedan en minskning som gäller för en klass av heuristik som vi kallar certifierbar, vilket gör att vi kan konvertera orakelberoende integritet garantier till värsta fall integritet garanti som håller även när heuristic står i för orakel kan misslyckas på kontradiktoriska sätt. Slutligen tänker vi på funktionsklasser för vilka både de och deras dubbla klasser har små universella identifieringsuppsättningar. Detta inkluderar de flesta klasser av enkla booleska funktioner som studeras i PAC inlärningslitteratur, inklusive associationer, disjunktioner, pariteter och diskreta halvrymder. Vi visar att det finns en effektiv algoritm för privat konstruktion av syntetiska data för alla sådana klasser, med tanke på ett icke-privat lärande orakel. Detta ger i synnerhet den första orakleeffektiva algoritmen för privatgenererande syntetiska data för beredskapsplaner. Den mest spännande frågan som lämnas öppen genom vårt arbete är om varje problem som kan lösas differentialt privat kan lösas privat med en orakeleffektiv algoritm. Även om vi inte löser detta, ger vi ett barriärresultat som tyder på att en allmän orakle-effektiv minskning måste falla utanför en naturlig klass av algoritmer (som inkluderar algoritmer som ges i detta dokument).
Det arbete som är närmast relaterat till vår första algoritm är REF, som också ger en liknande "orakeleffektiv" algoritm för icke-konvex differentialt privat optimering: d.v.s. minskningar från icke-privat optimering till privat optimering.
How to Use Heuristics for Differential Privacy
{'venue': '2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}