År 2008, Kasiviswanathan el al al. definierat privat lärande som en kombination av PAC-inlärning och differentiell integritet [16]. Informellt, en privat inlärare tillämpas på en samling av märkta individuell information och outputs en hypotes samtidigt som integriteten för varje individ. Kasiviswanathan m.fl. gav en allmän konstruktion av privata elever för (finita) koncept klasser, med urval komplexitet logaritmisk i storleken på konceptklassen. Denna urval komplexitet är högre än vad som krävs för icke-privata inlärare, vilket lämnar öppen möjlighet att urvalet komplexitet privat lärande kan vara ibland betydligt högre än den icke-privata lärande. Vi ger en kombinatorisk karakterisering av provstorleken tillräcklig och nödvändig för att privat lära sig en klass av begrepp. Denna karakterisering är jämförbar med den välkända karakteriseringen av urvalskomplexiteten hos icke-privat lärande i termer av VC-dimensionen i konceptklassen. Vi introducerar begreppet probabilistisk representation av en konceptklass, och vår nya komplexitetsmått RepDim motsvarar storleken på den minsta probabilistiska representationen av konceptklassen. Vi visar att varje privat inlärningsalgoritm för en konceptklass C med prov komplexitet m innebär RepDim(C) = O(m), och att det finns en privat inlärningsalgoritm med prov komplexitet m = O(RepDim(C)). Vi visar vidare att en liknande karakterisering håller för den databasstorlek som behövs för privat databehandling en stor klass av optimeringsproblem och även för det väl studerade problemet med privat data release.
En karakterisering för urvalet komplexitet ren privata inlärare gavs i REF, i termer av en ny kombinatorisk åtgärd - representationsdimensionen, det vill säga, med tanke på en klass C, antalet prover som behövs och tillräcklig för privat lärande C är. (RepDim(C)).
Characterizing the sample complexity of private learners
{'venue': "ITCS '13", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}