Polynomial methods in statistical inference: theory and practice

Abstract

This survey provides an exposition of a suite of techniques based on the theory of polynomials, collectively referred to as polynomial methods, which have recently been applied to address several challenging problems in statistical inference successfully. Topics including polynomial approximation, polynomial interpolation and majorization, moment space and positive polynomials, orthogonal polynomials and Gaussian quadrature are discussed, with their major probabilistic and statistical applications in property estimation on large domains and learning mixture models. These techniques provide useful tools not only for the design of highly practical algorithms with provable optimality, but also for establishing the fundamental limits of the inference problems through the method of moment matching. The effectiveness of the polynomial method is demonstrated in concrete problems such as entropy and support size estimation, distinct elements problem, and learning Gaussian mixture models.

Foundations and Trends in Communications and Information Theory: Vol. 17: No. 4, pp 402-586, 2020. ISBN to printed book: 978-1-68083-730-8. arXiv admin note: text overlap with arXiv:1807.07237

References in corpus (16)

• Scikit-learn: Machine Learning in Python
• TensorFlow: A system for large-scale machine learning
• MLlib: Machine Learning in Apache Spark
• Entropy and information in neural spike trains: Progress on the sampling problem
• Universal Estimation of Directed Information
• Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• Divided Differences
• Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• Nonquadratic estimators of a quadratic functional
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• Ten Steps of EM Suffice for Mixtures of Two Gaussians
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions
• Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
• Sample complexity of population recovery

Cited by in corpus (1)

• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution