Sample-optimal density estimation in nearly-linear time

DOI10.1137/1.9781611974782.83MaRDI QIDQ4575826zbMATH OpenOpenAlexFDO

Authors Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.00671

Mathematics Subject Classification ID

Density estimation (62G07) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We design a new, fast algorithm for agnostically learning univariate probability distributions whose densities are well approximated by piecewise polynomial functions. Let $f$ be the density function of an arbitrary univariate distribution, and suppose that $f$ is $mathrmOPT$-close in $L_1$-distance to an unknown piecewise polynomial function with $t$ interval pieces and degree $d$. Our algorithm draws $n=O(t(d+1)/epsilo{n}^2)$ samples from $f$, runs in time $ildeO(ncdotmathrmpoly(d))$, and with probability at least $9/10$ outputs an $O(t)$-piecewise degree-$d$ hypothesis $h$ that is $4cdotmathrmOPT+epsilon$ close to $f$. Our general algorithm yields (nearly) sample-optimal and nearly-linear time estimators for a wide range of structured distribution families over both continuous and discrete domains in a unified way. For most of our applications, these are the first sample-optimal and nearly-linear time estimators in the literature. As a consequence, our work resolves the sample and computational complexities of a broad class of inference tasks via a single "meta-algorithm". Moreover, we experimentally demonstrate that our algorithm performs very well in practice. Our algorithm consists of three "levels": (i) At the top level, we employ an iterative greedy algorithm for finding a good partition of the real line into the pieces of a piecewise polynomial. (ii) For each piece, we show that the sub-problem of finding a good polynomial fit on the current interval can be solved efficiently with a separation oracle method. (iii) We reduce the task of finding a separating hyperplane to a combinatorial problem and give an efficient algorithm for this problem. Combining these three procedures gives a density estimation algorithm with the claimed guarantees.

Recommendations

• Efficient density estimation via piecewise polynomial approximation
• Instance optimal learning of discrete distributions
• Learning \(k\)-modal distributions via testing
• Efficient profile maximum likelihood for universal symmetric property estimation

Cited in

(17)

• Optimal linear granulometric estimation for random sets
• Testing shape restrictions of discrete distributions
• A recursive procedure for density estimation on the binary hypercube
• On the nonparametric maximum likelihood estimator for Gaussian location mixture densities with application to Gaussian denoising
• Fast multivariate log-concave density estimation
• Sampling correctors
• Efficient Multidimensional Diracs Estimation With Linear Sample Complexity
• Robust estimators in high-dimensions without the computational intractability
• Density estimation for shift-invariant multidimensional distributions
• Density estimation \textit {via} optimal segmentation
• Efficient profile maximum likelihood for universal symmetric property estimation
• Efficient density estimation via piecewise polynomial approximation
• Instance optimal learning of discrete distributions
• Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
• Mixtures of Gaussians are privately learnable with a polynomial number of samples
• Algebraic and analytic approaches for parameter learning in mixture models
• Sample efficient identity testing and independence testing of quantum states

This page was built for publication: Sample-optimal density estimation in nearly-linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575826)