Monotone probability distributions over the Boolean cube can be learned with sublinear samples

Abstract

A probability distribution over the Boolean cube is monotone if flipping the value of a coordinate from zero to one can only increase the probability of an element. Given samples of an unknown monotone distribution over the Boolean cube, we give (to our knowledge) the first algorithm that learns an approximation of the distribution in statistical distance using a number of samples that is sublinear in the domain. To do this, we develop a structural lemma describing monotone probability distributions. The structural lemma has further implications to the sample complexity of basic testing tasks for analyzing monotone probability distributions over the Boolean cube: We use it to give nontrivial upper bounds on the tasks of estimating the distance of a monotone distribution to uniform and of estimating the support size of a monotone distribution. In the setting of monotone probability distributions over the Boolean cube, our algorithms are the first to have sample complexity lower than known lower bounds for the same testing tasks on arbitrary (not necessarily monotone) probability distributions. One further consequence of our learning algorithm is an improved sample complexity for the task of testing whether a distribution on the Boolean cube is monotone.

References in corpus (11)

• Maximum likelihood estimation of a log-concave density and its distribution function: Basic properties and uniform consistency
• Polynomial Learning of Distribution Families
• Learning mixtures of structured distributions over discrete domains
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
• Asymptotics of the discrete log-concave maximum likelihood estimator and related applications
• A Size-Free CLT for Poisson Multinomials and its Applications
• Near-optimal-sample estimators for spherical Gaussian mixtures
• Learning Multivariate Log-concave Distributions
• Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
• A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables

Cited by in corpus (7)

• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Computationally Efficient Robust Estimation of Sparse Functionals
• Profile Entropy: A Fundamental Measure for the Learnability and Compressibility of Discrete Distributions
• A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
• An Investigation of Data Poisoning Defenses for Online Learning
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
• On the Sample Complexity of Learning Sum-Product Networks