Learning mixtures of product distributions over discrete domains

No abstract is available for this paper.

• Publication year

  2005

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2005-10-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/060670705
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption

  2006cited by this paper
• Learning nonsingular phylogenies and hidden Markov models

  2005cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Toward Privacy in Public Databases

  2005cited by this paper
• Learning a Function of r Relevant Variables

  2003cited by this paper
• Multilinear formulas and skepticism of quantum computing

  2003cited by this paper
• A spectral algorithm for learning mixtures of distributions

  2002cited by this paper
• Learning mixtures of arbitrary gaussians

  2001cited by this paper
• A Two-Round Variant of EM for Gaussian Mixtures

  2000cited by this paper
• Estimating a mixture of two product distributions

  1999influential reference
• Learning and approximation algorithms for problems motivated by evolutionary trees

  1999influential reference
• Learning mixtures of Gaussians

  1999cited by this paper
• Evolutionary trees can be learned in polynomial time in the two-state general Markov model

  1998cited by this paper
• Efficient noise-tolerant learning from statistical queries

  1998cited by this paper
• Mixture models: Theory, geometry and applications

  1997cited by this paper
• A Theory of Pseudoskeleton Approximations

  1997cited by this paper
• Mixture models : theory, geometry, and applications

  1995cited by this paper
• On the learnability of discrete distributions

  1994cited by this paper
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

  1994cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• Rank-r Decision Trees are a Subclass of r-Decision Lists

  1992cited by this paper
• Learning decision trees from random examples

  1988cited by this paper
• Statistical analysis of finite mixture distributions

  1986cited by this paper
• Mixture densities, maximum likelihood, and the EM algorithm

  1984cited by this paper

• Identifiability and Estimation in High-Dimensional Nonparametric Latent Structure Models

  2025cites this paper
• Multi-Agent Fact Checking

  2025cites this paper
• A Distributional-Lifting Theorem for PAC Learning

  2025cites this paper
• Distributed Fact Checking: Learning Unreliability

  2024cites this paper
• Learning with Hidden Factorial Structure

  2024cites this paper
• Multi-Agent Fact-Checker: Adaptive Estimators

  2024cites this paper
• Lifting Uniform Learners via Distributional Decomposition

  2023influential citation
• Learning Polynomial Transformations via Generalized Tensor Decompositions

  2023cites this paper
• Distributed Fact Checking

  2023cites this paper
• Reward-Mixing MDPs with Few Latent Contexts are Learnable

  2023cites this paper
• The Identification of Discrete Mixture Models

  2023influential citation
• Causal Discovery under Latent Class Confounding

  2023cites this paper
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity

  2023cites this paper
• Support Recovery in Mixture Models With Sparse Parameters

  2022cites this paper
• On Learning Mixture of Linear Regressions in the Non-Realizable Setting

  2022cites this paper
• Efficient Algorithms for Sparse Moment Problems without Separation

  2022cites this paper
• On Learning Mixture Models with Sparse Parameters

  2022cites this paper
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable

  2022cites this paper
• Hadamard Extensions and the Identification of Mixtures of Product Distributions

  2021cites this paper
• Reinforcement Learning in Reward-Mixing MDPs

  2021cites this paper
• Clustering mixtures with almost optimal separation in polynomial time

  2021cites this paper
• Identifying Mixtures of Bayesian Network Distributions

  2021cites this paper
• Causal Inference Despite Limited Global Confounding via Mixture Models

  2021cites this paper
• Hadamard Powers and the Identification of Mixtures of Products

  2021cites this paper
• Source Identification for Mixtures of Product Distributions

  2020influential citation
• The Sparse Hausdorff Moment Problem, with Application to Topic Models

  2020cites this paper
• Network Inference from a Mixture of Diffusion Models for Fake News Mitigation

  2020cites this paper
• Polynomial-time algorithms for Multimarginal Optimal Transport problems with decomposable structure.

  2020cites this paper
• Polynomial-time algorithms for multimarginal optimal transport problems with structure

  2020cites this paper
• Algebraic and Analytic Approaches for Parameter Learning in Mixture Models

  2020influential citation
• Private Hypothesis Selection

  2019cites this paper
• Differentially Private Algorithms for Learning Mixtures of Separated Gaussians

  2019cites this paper
• 68 : 2 Trace Reconstruction : Generalized and Parameterized 1 Introduction

  2019cites this paper
• Efficiently learning structured distributions from untrusted batches

  2019cites this paper
• Robust Estimators in High-Dimensions Without the Computational Intractability

  2019cites this paper
• Identification of the Structure of a Probabilistic Boolean Network From Samples Including Frequencies of Outcomes

  2019cites this paper
• L G ] 1 9 Fe b 20 19 Beyond the Low-Degree Algorithm : Mixtures of Subcubes and Their Applications

  2019cites this paper
• Trace Reconstruction: Generalized and Parameterized

  2019cites this paper
• Doubly-Competitive Distribution Estimation

  2019cites this paper
• Efficiently Learning Mixtures of Mallows Models

  2018cites this paper
• Modern challenges in distribution testing

  2018cites this paper
• Beyond the low-degree algorithm: mixtures of subcubes and their applications

  2018influential citation
• TWO PROBLEMS IN NOISE TOLERANT COMPUTING

  2018cites this paper
• Noisy Population Recovery from Unknown Noise

  2017influential citation
• Robust and Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities

  2017cites this paper
• Testing properties of Ising models

  2017cites this paper
• Sample complexity of population recovery

  2017cites this paper
• Feature Selection Facilitates Learning Mixtures of Discrete Product Distributions

  2017cites this paper
• Learning Structured Distributions

  2016cites this paper
• Robust Estimators in High Dimensions without the Computational Intractability

  2016cites this paper
• Testing Ising Models

  2016cites this paper
• Know Your Customer: Multi-armed Bandits with Capacity Constraints

  2016cites this paper
• Predicting with Distributions

  2016cites this paper
• Theoretical Analysis of the k-Means Algorithm - A Survey

  2016cites this paper
• Adversarial Top- $K$ Ranking

  2016cites this paper
• Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures

  2016cites this paper
• Composition of Learning Models: Predicting with Distributions

  2016cites this paper
• Efficient Robust Proper Learning of Log-concave Distributions

  2016cites this paper
• Algorithms and lower bounds for testing properties of structured distributions

  2016cites this paper
• Learning Parametric-Output HMMs with Two Aliased States

  2015cites this paper
• Differentially Private Learning of Structured Discrete Distributions

  2015cites this paper
• Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

  2015cites this paper
• Sample-Optimal Density Estimation in Nearly-Linear Time

  2015cites this paper
• On Learning Mixture Models for Permutations

  2015cites this paper
• Low-Rank Matrix Completion with Adversarial Missing Entries

  2015influential citation
• Active Sets Improves Learning for Mixture Models

  2015cites this paper
• Stagewise Learning for Sparse Clustering of Discretely-Valued Data

  2015cites this paper
• Symmetric Tensor Completion from Multilinear Entries and Learning Product Mixtures over the Hypercube

  2015cites this paper
• Learning Arbitrary Statistical Mixtures of Discrete Distributions

  2015cites this paper
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables

  2015cites this paper
• Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables

  2015cites this paper
• Near-Optimal-Sample Estimators for Spherical Gaussian Mixtures

  2014cites this paper
• Estimating the accuracies of multiple classifiers without labeled data

  2014cites this paper
• On Learning and Covering Structured Distributions

  2014cites this paper
• Testing Identity of Structured Distributions

  2014cites this paper
• Testing Poisson Binomial Distributions

  2014cites this paper
• A Polynomial Time Algorithm for Lossy Population Recovery

  2013cites this paper
• Explorer Efficient Density Estimation via Piecewise Polynomial Approximation

  2013cites this paper
• Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

  2013cites this paper
• Learning Sums of Independent Integer Random Variables

  2013cites this paper
• Learning Mixtures of Discrete Product Distributions using Spectral Decompositions

  2013cites this paper
• Efficient Learning Algorithms with Limited Information.

  2013cites this paper
• Efficient density estimation via piecewise polynomial approximation

  2013cites this paper
• Robust hierarchical clustering

  2013cites this paper
• Population recovery and partial identification

  2012cites this paper
• Learning mixtures of structured distributions over discrete domains

  2012cites this paper
• A Method of Moments for Mixture Models and Hidden Markov Models

  2012cites this paper
• Learning mixtures of arbitrary distributions over large discrete domains

  2012cites this paper
• Inverse Problems in Approximate Uniform Generation

  2012cites this paper
• Learning Mixtures of Distributions over Large Discrete Domains

  2012cites this paper
• A randomized framework for discovery of heterogeneous mixtures

  2011cites this paper
• Learning transformed product distributions

  2011influential citation
• New directions in gaussian mixture learning and semi-supervised learning

  2010cites this paper
• CS369N: Beyond Worst-Case Analysis Lecture #4: Probabilistic and Semirandom Models for Clustering and Graph Partitioning ∗

  2010cites this paper
• Toward Learning Gaussian Mixtures with Arbitrary Separation.

  2010cites this paper
• Provably Learning Mixtures of Gaussians and More

  2010cites this paper
• Polynomial Learning of Distribution Families

  2010cites this paper
• Polynomial regression under arbitrary product distributions

  2010cites this paper
• Learning Gaussian Mixtures with Arbitrary Separation

  2009cites this paper
• Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles

  2009cites this paper