Efficient density estimation via piecewise polynomial approximation

DOI10.1145/2591796.2591848zbMATH Open1315.68163arXiv1305.3207OpenAlexW2143122862MaRDI QIDQ5259596FDOQ5259596

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)

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.

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

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

zbMATH Keywords

unsupervised learningcomputational learning theorylearning distributions

Mathematics Subject Classification ID

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

Cites Work

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

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
• Density estimation for shift-invariant multidimensional distributions
• Reliable clustering of Bernoulli mixture models
• Monte Carlo Gradient in Optimization Constrained by Radiative Transport Equation
• Approximating \(L_1\)-distances between mixture distributions using random projections
• A least squares-type density estimator using a polynomial function
• Testing shape restrictions of discrete distributions
• Sample-optimal density estimation in nearly-linear time

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)