Lärandeproblem utgör en viktig kategori av beräkningsuppgifter som generaliserar många av de beräkningar forskare tillämpar på stora verkliga datamängder. Vi frågar oss: vilka konceptklasser kan man lära sig privat, nämligen genom en algoritm vars utdata inte är alltför starkt beroende av någon input eller något specifikt utbildningsexempel? Mer exakt undersöker vi lärande algoritmer som tillgodoser differential integritet, ett begrepp som ger starka sekretessgarantier i sammanhang där aggregerad information släpps om en databas som innehåller känslig information om individer. Vårt mål är en bred förståelse av de resurser som krävs för privat lärande i form av prover, beräkningstid och interaktion. Vi visar att det är möjligt att privat agnostiskt lära sig vilken konceptklass som helst med hjälp av en provstorlek som är ungefär logaritmisk i begreppsklassens kardinalitet. Därför är nästan allt man kan lära sig privat: specifikt, om en konceptklass kan läras av en (icke-privat) algoritm med polynomisk prov komplexitet och produktionsstorlek, då kan det läras privat med hjälp av ett polynom antal prover. Vi presenterar också en beräkningseffektiv privat PAC-inlärare för klassen paritetsfunktioner. Detta resultat skingrar likheten mellan lärande med buller och privat lärande (båda måste vara robusta till små förändringar i input), eftersom paritet anses vara mycket svårt att lära med tanke på slumpmässig klassificering buller. Lokala (eller randomiserade svar) algoritmer är en praktisk klass av privata algoritmer som har fått omfattande utredning. Vi ger en exakt karakterisering av lokala privata inlärningsalgoritmer. Vi visar att en konceptklass kan läras av en lokal algoritm om och endast om den är inlärbar i den statistiska frågeställningen (SQ). Därför, för lokala privata lärande algoritmer, likheten med lärande med buller är starkare: lokalt lärande är likvärdigt med SQ lärande, och SQ algoritmer inkluderar mest kända bullertoleranta lärande algoritmer. Slutligen presenterar vi en åtskillnad mellan kraften i interaktiva och icke-interaktiva lokala inlärningsalgoritmer. På grund av likvärdigheten med SQ-inlärning separerar detta resultat också adaptivt och icke adaptivt SQ-inlärning.
Kasiviswanathan m.fl. Ref visade ett exempel på en konceptklass - klassen paritetsfunktioner - som inte går att lära sig i modellen för statistiska frågor men som kan läras privat och effektivt.
What Can We Learn Privately?
{'venue': 'SIAM Journal of Computing 40(3) (2011) 793-826', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}