A General Framework for Symmetric Property Estimation
- URL: http://arxiv.org/abs/2003.00844v1
- Date: Mon, 2 Mar 2020 13:00:04 GMT
- Title: A General Framework for Symmetric Property Estimation
- Authors: Moses Charikar, Kirankumar Shiragur, Aaron Sidford
- Abstract summary: We identify the easy region where empirical estimation works and the difficult region where more complex estimators are required.
We show that by approximately computing the profile maximum likelihood (PML) distribution citeADOS16 in this difficult region we obtain a symmetric property estimation framework that is sample complexity optimal for many properties.
- Score: 35.14819168275207
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we provide a general framework for estimating symmetric
properties of distributions from i.i.d. samples. For a broad class of symmetric
properties we identify the easy region where empirical estimation works and the
difficult region where more complex estimators are required. We show that by
approximately computing the profile maximum likelihood (PML) distribution
\cite{ADOS16} in this difficult region we obtain a symmetric property
estimation framework that is sample complexity optimal for many properties in a
broader parameter regime than previous universal estimation approaches based on
PML. The resulting algorithms based on these pseudo PML distributions are also
more practical.
Related papers
- Sample Complexity of the Sign-Perturbed Sums Identification Method:
Scalar Case [0.0]
Sign-Perturbed Sum (SPS) is a powerful finite-sample system identification algorithm.
This paper studies the behaviour of SPS confidence intervals.
arXiv Detail & Related papers (2024-01-28T22:44:41Z) - On the Consistency of Maximum Likelihood Estimation of Probabilistic
Principal Component Analysis [1.0528389538549636]
PPCA has a broad spectrum of applications ranging from science and engineering to quantitative finance.
Despite this wide applicability in various fields, hardly any theoretical guarantees exist to justify the soundness of the maximal likelihood (ML) solution for this model.
We propose a novel approach using quotient topological spaces and in particular, we show that the maximum likelihood solution is consistent in an appropriate quotient Euclidean space.
arXiv Detail & Related papers (2023-11-08T22:40:45Z) - On the Efficient Implementation of High Accuracy Optimality of Profile
Maximum Likelihood [33.051282474765955]
Our estimator is based on profile-maximum-likelihood (PML) and is sample optimal for estimating various symmetric properties.
This result improves upon the previous best accuracy threshold of $epsilon gg n-1/4$ by achievable time.
arXiv Detail & Related papers (2022-10-13T04:52:15Z) - Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models.
We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling.
We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
arXiv Detail & Related papers (2022-09-27T07:58:25Z) - Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
We show that efficiency of Metropolis-Hastings (M-H) algorithms in discrete spaces can be characterized by an acceptance rate that is independent of the target distribution.
Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces.
arXiv Detail & Related papers (2022-09-16T22:09:53Z) - Revisiting the Sample Complexity of Sparse Spectrum Approximation of
Gaussian Processes [60.479499225746295]
We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space.
Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
arXiv Detail & Related papers (2020-11-17T05:41:50Z) - Instance Based Approximations to Profile Maximum Likelihood [33.51964370430905]
We provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution.
We obtain the first provable computationally efficient implementation of PseudoPML, a framework for estimating a broad class of symmetric properties.
arXiv Detail & Related papers (2020-11-05T11:17:19Z) - Generalized Sliced Distances for Probability Distributions [47.543990188697734]
We introduce a broad family of probability metrics, coined as Generalized Sliced Probability Metrics (GSPMs)
GSPMs are rooted in the generalized Radon transform and come with a unique geometric interpretation.
We consider GSPM-based gradient flows for generative modeling applications and show that under mild assumptions, the gradient flow converges to the global optimum.
arXiv Detail & Related papers (2020-02-28T04:18:00Z) - Profile Entropy: A Fundamental Measure for the Learnability and
Compressibility of Discrete Distributions [63.60499266361255]
We show that for samples of discrete distributions, profile entropy is a fundamental measure unifying the concepts of estimation, inference, and compression.
Specifically, profile entropy a) determines the speed of estimating the distribution relative to the best natural estimator; b) characterizes the rate of inferring all symmetric properties compared with the best estimator over any label-invariant distribution collection; c) serves as the limit of profile compression.
arXiv Detail & Related papers (2020-02-26T17:49:04Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.