# Efficient Robust Proper Learning of Log-concave Distributions

arXiv: https://arxiv.org/abs/1606.03077 · HTML: https://mlsanity.com/paper/1606.03077/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2016.

## Built on by (most cited first, 3 of 3)

- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [An Efficient Minimax Optimal Estimator For Multivariate Convex Regression](https://mlsanity.com/paper/2205.03368/) (2022)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)

## Abstract (arXiv)

We study the em robust proper learning of univariate log-concave distributions (over continuous and discrete domains). Given a set of samples drawn from an unknown target distribution, we want to compute a log-concave hypothesis distribution that is as close as possible to the target, in total variation distance. In this work, we give the first computationally efficient algorithm for this learning problem. Our algorithm achieves the information-theoretically optimal sample size (up to a constant factor), runs in polynomial time, and is robust to model misspecification with nearly-optimal error guarantees. Specifically, we give an algorithm that, on input n=O(1/eps5/2) samples from an unknown distribution f, runs in time widetildeO(n8/5), and outputs a log-concave hypothesis h that (with high probability) satisfies dtv(h, f) = O(opt)+eps, where opt is the minimum total variation distance between f and the class of log-concave distributions. Our approach to the robust proper learning problem is quite flexible and may be applicable to many other univariate distribution families.