Instance Based Approximations to Profile Maximum Likelihood

• URL: http://arxiv.org/abs/2011.02761v1
• Date: Thu, 5 Nov 2020 11:17:19 GMT
• Title: Instance Based Approximations to Profile Maximum Likelihood
• Authors: Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
• Abstract summary: 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.
• Score: 33.51964370430905
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution, a prominent quantity in symmetric property estimation. We provide an algorithm which matches the previous best known efficient algorithms for computing approximate PML distributions and improves when the number of distinct observed frequencies in the given instance is small. We achieve this result by exploiting new sparsity structure in approximate PML distributions and providing a new matrix rounding algorithm, of independent interest. Leveraging this result, we obtain the first provable computationally efficient implementation of PseudoPML, a general framework for estimating a broad class of symmetric properties. Additionally, we obtain efficient PML-based estimators for distributions with small profile entropy, a natural instance-based complexity measure. Further, we provide a simpler and more practical PseudoPML implementation that matches the best-known theoretical guarantees of such an estimator and evaluate this method empirically.

Related papers

• On Policy Evaluation Algorithms in Distributional Reinforcement Learning [0.0]
  We introduce a novel class of algorithms to efficiently approximate the unknown return distributions in policy evaluation problems from distributional reinforcement learning (DRL) For a plain instance of our proposed class of algorithms we prove error bounds, both within Wasserstein and Kolmogorov--Smirnov distances. For return distributions having probability density functions the algorithms yield approximations for these densities; error bounds are given within supremum norm.
  arXiv  Detail & Related papers  (2024-07-19T10:06:01Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Algorithme EM r\'egularis\'e [0.0]
  This paper presents a regularized version of the EM algorithm that efficiently uses prior knowledge to cope with a small sample size. Experiments on real data highlight the good performance of the proposed algorithm for clustering purposes.
  arXiv  Detail & Related papers  (2023-07-04T23:19:25Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• Orthogonal Polynomials Approximation Algorithm (OPAA):a functional analytic approach to estimating probability densities [0.0]
  We present the new Orthogonal Polynomials Approximation Algorithm (OPAA) OPAA estimates probability distributions using functional analytic approach. It can be applied to estimating the normalizing weight of the posterior.
  arXiv  Detail & Related papers  (2022-11-16T00:51:00Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Efficient Data-Dependent Learnability [8.766022970635898]
  The predictive normalized maximum likelihood (pNML) approach has recently been proposed as the min-max optimal solution to the batch learning problem. We show that when applied to neural networks, this approximation can detect out-of-distribution examples effectively.
  arXiv  Detail & Related papers  (2020-11-20T10:44:55Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• A General Framework for Symmetric Property Estimation [35.14819168275207]
  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.
  arXiv  Detail & Related papers  (2020-03-02T13:00: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.