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 A1, A2,. .., En av U sådan att c (S) = u på A i 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 [BH12]. Vår algoritm bygger på att först lösa ett enklare problem att lära täckning funktioner med låg l1-terror. Våra algoritmer är baserade på flera nya strukturella egenskaper hos täckningsfunktioner och, i synnerhet, vi bevisar att alla täckningsfunktioner kan vara ungefärliga i l1 av en täckningsfunktion som endast beror på O(1/ och 2 ) variabler. Detta är tätt upp till en konstant faktor. Däremot visar vi att utan antaganden om fördelningen, lärande täckning funktioner är minst lika svårt som lärande polynomialsize disjoint DNF formler, en klass av funktioner för vilka den mest kända algoritmen körs i tid 2 Õ Som en tillämpning av vårt resultat, ger vi en enkel polynomial-tid differentially private algoritm för att släppa monoton disjunction räkna frågor med lågt genomsnitt fel över den enhetliga fördelningen på disjunctions.
I ett parallellt arbete överväger REF att lära sig täckningsfunktioner.
Learning Coverage Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}