Efficient Robust Proper Learning of Log-concave Distributions

By Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. 2016

30 citations recorded by the source corpus.

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/\eps^{5/2})$ samples from an unknown distribution $f$, runs in time $\widetilde{O}(n^{8/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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Communication-Efficient Distributed Learning of Discrete Probability Distributions (2017, methodology): “Specifically, by using the structural approximation results of [6, 7, 20], we obtain sample-optimal distributed estimators for various well-studied classes of structured densities including monotone, unimodal, log-concave, monotone hazard rate (MHR) distributions, and others.”
Computationally Efficient Robust Sparse Estimation in High Dimensions (2017, methodology): “By Theorem 4.15 of (Diakonikolas et al., 2016a) we have the following formula for the cov (Ω)”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “Various different models have been introduced, see Charikar, Steinhardt, and Valiant [17], Diakonikolas, Kamath, Kane, Li, Moitra, and Stewart [23, 24, 25], Diakonikolas, Kane, and Stewart [26], Diakonikolas, Kong, and Stewart [27], Hopkins and Li [34], Klivans, Kothari, and Meka [42], Kothari, Stei”