Efficient density estimation via piecewise polynomial approximation

DOI10.1145/2591796.2591848MaRDI QIDQ5259596zbMATH OpenOpenAlexFDO

Authors Siu On Chan, Ilias Diakonikolas, Xiaorui Sun, Rocco A. Servedio

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

unsupervised learningcomputational learning theorylearning distributions

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32)

Abstract: We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let $p$ be an arbitrary distribution over an interval $I$ which is $au$-close (in total variation distance) to an unknown probability distribution $q$ that is defined by an unknown partition of $I$ into $t$ intervals and $t$ unknown degree-$d$ polynomials specifying $q$ over each of the intervals. We give an algorithm that draws $ildeO(tew(d+1)/ep{s}^2)$ samples from $p$, runs in time $poly(t,d,1/eps)$, and with high probability outputs a piecewise polynomial hypothesis distribution $h$ that is $(O(au)+eps)$-close (in total variation distance) to $p$. This sample complexity is essentially optimal; we show that even for $au=0$, any algorithm that learns an unknown $t$-piecewise degree-$d$ probability distribution over $I$ to accuracy $eps$ must use $Omega(fract(d+1)poly(1+log(d+1))cdotfrac1ep{s}^2)$ samples from the distribution, regardless of its running time. Our algorithm combines tools from approximation theory, uniform convergence, linear programming, and dynamic programming. We apply this general algorithm to obtain a wide range of results for many natural problems in density estimation over both continuous and discrete domains. These include state-of-the-art results for learning mixtures of log-concave distributions; mixtures of $t$-modal distributions; mixtures of Monotone Hazard Rate distributions; mixtures of Poisson Binomial Distributions; mixtures of Gaussians; and mixtures of $k$-monotone densities. Our general technique yields computationally efficient algorithms for all these problems, in many cases with provably optimal sample complexities (up to logarithmic factors) in all parameters.

Recommendations

• Sample-optimal density estimation in nearly-linear time
• Learning mixtures of structured distributions over discrete domains
• Learning \(k\)-modal distributions via testing
• Universal algorithms for learning theory. II: Piecewise polynomial functions
• Learning \(k\)-modal distributions via testing

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(16)

• Function approximation with polynomial membership functions and alternating cluster estimation
• Maximum a posteriori estimators as a limit of Bayes estimators
• Efficient and robust density estimation using Bernstein type polynomials
• Robust estimators in high-dimensions without the computational intractability
• On the nonparametric maximum likelihood estimator for Gaussian location mixture densities with application to Gaussian denoising
• Estimation of exponential-polynomial distribution by holonomic gradient descent
• Sampling correctors
• Piecewise linear approximation of empirical distributions under a Wasserstein distance constraint
• Learning mixtures of structured distributions over discrete domains
• Reliable clustering of Bernoulli mixture models
• Density estimation for shift-invariant multidimensional distributions
• A least squares-type density estimator using a polynomial function
• Monte Carlo Gradient in Optimization Constrained by Radiative Transport Equation
• Approximating \(L_1\)-distances between mixture distributions using random projections
• Testing shape restrictions of discrete distributions
• Sample-optimal density estimation in nearly-linear time

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Efficient density estimation via piecewise polynomial approximation

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