License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.28
URN: urn:nbn:de:0030-drops-101214
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10121/
De, Anindya ;
Long, Philip M. ;
Servedio, Rocco A.
Density Estimation for Shift-Invariant Multidimensional Distributions
Abstract
We study density estimation for classes of shift-invariant distributions over R^d. A multidimensional distribution is "shift-invariant" if, roughly speaking, it is close in total variation distance to a small shift of it in any direction. Shift-invariance relaxes smoothness assumptions commonly used in non-parametric density estimation to allow jump discontinuities. The different classes of distributions that we consider correspond to different rates of tail decay.
For each such class we give an efficient algorithm that learns any distribution in the class from independent samples with respect to total variation distance. As a special case of our general result, we show that d-dimensional shift-invariant distributions which satisfy an exponential tail bound can be learned to total variation distance error epsilon using O~_d(1/ epsilon^{d+2}) examples and O~_d(1/ epsilon^{2d+2}) time. This implies that, for constant d, multivariate log-concave distributions can be learned in O~_d(1/epsilon^{2d+2}) time using O~_d(1/epsilon^{d+2}) samples, answering a question of [Diakonikolas et al., 2016]. All of our results extend to a model of noise-tolerant density estimation using Huber's contamination model, in which the target distribution to be learned is a (1-epsilon,epsilon) mixture of some unknown distribution in the class with some other arbitrary and unknown distribution, and the learning algorithm must output a hypothesis distribution with total variation distance error O(epsilon) from the target distribution. We show that our general results are close to best possible by proving a simple Omega (1/epsilon^d) information-theoretic lower bound on sample complexity even for learning bounded distributions that are shift-invariant.
BibTeX - Entry
@InProceedings{de_et_al:LIPIcs:2018:10121,
author = {Anindya De and Philip M. Long and Rocco A. Servedio},
title = {{Density Estimation for Shift-Invariant Multidimensional Distributions}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {28:1--28:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-095-8},
ISSN = {1868-8969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10121},
URN = {urn:nbn:de:0030-drops-101214},
doi = {10.4230/LIPIcs.ITCS.2019.28},
annote = {Keywords: Density estimation, unsupervised learning, log-concave distributions, non-parametrics}
}
|
Keywords: |
|
Density estimation, unsupervised learning, log-concave distributions, non-parametrics |
|
Collection: |
|
10th Innovations in Theoretical Computer Science Conference (ITCS 2019) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.01.2019 |
