Vi studerar problemet med att lära sig multivariat log-concave densiteter med avseende på en global förlust funktion. Vi får den första övre gränsen på provet komplexitet av den maximala sannolikheten estimator (MLE) för en log-konkav densitet på R d, för alla d ≥ 4. Före detta arbete var ingen ändlig övre provbindning känd för denna estimator i mer än 3 dimensioner. I mer detalj, Vi bevisar att för alla d ≥ 4 och > 0, givet Õ d ((1/ ) (d+3)/2 ) prover som tagits från en okänd log-konkav densitet f 0 på R d, MLE utgångar en hypotes h att med hög sannolikhet är -nära f 0, i kvadrat Hellinger förlust. För varje d ≥ 2 var en prov komplexitet lägre gräns för d ((1/ ) (d+1)/2 ) tidigare känd för alla lärande algoritmer som uppnår denna garanti. Vi fastställer således att provets komplexitet i log-concave MLE är nära optimal för d ≥ 4, upp till en Õ(1/ ) faktor.
REF visade en prov komplexitet övre gräns för Õ d (1/ ) (d+3)/2 för multivariat log-concave MLE med avseende på kvadrat Hellinger förlust, vilket ger den första finita prov komplexitet övre gräns för denna uppskattning i dimension d ≥ 4.
Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
{'venue': 'COLT 2018 proceedings version', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}