Vi studerar problemet med att approximera och lära täckningsfunktioner. En funktion c : 2 [n] → R + är en täckningsfunktion, om det finns ett universum U med icke-negativa vikter w(u) för varje u U och undergrupper A 1, A 2,. .., A n av U sådan att c(S) = u pås Ai w(u). Alternativt kan täckningsfunktioner beskrivas som icke-negativa linjära kombinationer av monotona avvikelser. De är en naturlig underklass av submodulära funktioner och uppstår i ett antal tillämpningar. Vi ger en algoritm som för alla γ, γ > 0, ges slumpmässiga och enhetliga exempel på en okänd täckning funktion c, finner en funktion h som approximerar c inom faktor 1 + γ på alla utom δ-fraktion av punkterna i tiden poly (n, 1/γ, 1/δ). Detta är den första helt polynomal algoritmen för att lära sig en intressant klass av funktioner i den krävande PMAC-modellen av Balcan och Harvey [2012]. Våra algoritmer bygger på flera nya strukturella egenskaper hos täckningsfunktioner. Med hjälp av resultaten i [Feldman och Kothari, 2014], Vi visar också att täckningsfunktioner är lärbara agnostiskt med överskott l 1 -terror  på alla produkter och symmetriska fördelningar i tid n log(1/ på). Däremot visar vi att utan antaganden om fördelningen, lärande täckning funktioner är minst lika svårt som att lära polynom storlek isär DNF formler, en klass av funktioner för vilka den mest kända algoritmen körs i tid 2Õ (n 1/3 ) [Klivans och Servedio, 2004]. Som en tillämpning av våra lärande resultat, ger vi enkla differential-private algoritmer för att släppa monotona counting frågor med lågt genomsnitt fel. I synnerhet, för alla k ≤ n, får vi privat release av k-way marginaler med genomsnittliga fel i tid n O(log(1/)).
Feldman och Kothari REF gav en helt polynom tid algoritm för att lära koncis täckning funktioner i PMAC-modellen om fördelningen är enhetlig.
Learning Coverage Functions and Private Release of Marginals
{'venue': 'COLT 2014', 'journal': 'arXiv: Learning', 'mag_field_of_study': ['Computer Science', 'Mathematics']}