The log-concave maximum likelihood estimator (MLE) problem answers: for a set of points @math , which log-concave density maximizes their likelihood? We present a characterization of the log-concave MLE that leads to an algorithm with runtime @math to compute a log-concave distribution whose log-likelihood is at most @math less than that of the MLE, and @math is parameter of the problem that is bounded by the @math norm of the vector of log-likelihoods the MLE evaluated at @math .
Later work characterized the finite sample complexity of log-concave density estimation. First showed that no method can get closer than squared Hellinger distance @math (and indirectly, total variation distance) with @math samples, where @math hides logarithmic factors in @math @cite_5 . Later work demonstrated methods for learning log-concave distributions in total variation and squared Hellinger distances with bounded sample complexity. First showed a method that obtains sample complexity @math with respect to total variation distance @cite_4 . This work did use the log-concave MLE. later showed that the log-concave MLE is also effective for learning in squared Hellinger distance @cite_0 . The log-concave MLE was shown to converge to square Hellinger distance @math with @math with high probability, showing the log-concave MLE is nearly optimal in said metric. Both of these works are non constructive and do not provide efficient algorithms.
@cite_0 @cite_5 @cite_4
2788831527 2419492953 2762725970 2397544591
We study the problem of learning multivariate log-concave densities with respect to a global loss function. We obtain the first upper bound on the sample complexity of the maximum likelihood estimator (MLE) for a log-concave density on @math , for all @math . Prior to this work, no finite sample upper bound was known for this estimator in more than @math dimensions. In more detail, we prove that for any @math and @math , given @math samples drawn from an unknown log-concave density @math on @math , the MLE outputs a hypothesis @math that with high probability is @math -close to @math , in squared Hellinger loss. A sample complexity lower bound of @math was previously known for any learning algorithm that achieves this guarantee. We thus establish that the sample complexity of the log-concave MLE is near-optimal, up to an @math factor. We study the 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 @math samples from an unknown distribution @math , runs in time @math , and outputs a log-concave hypothesis @math that (with high probability) satisfies @math , where @math is the minimum total variation distance between @math 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. In this paper, we study the problem of sampling from a given probability density function that is known to be smooth and strongly log-concave. We analyze several methods of approximate sampling based on discretizations of the (highly overdamped) Langevin diffusion and establish guarantees on its error measured in the Wasserstein-2 distance. Our guarantees improve or extend the state-of-the-art results in three directions. First, we provide an upper bound on the error of the first-order Langevin Monte Carlo (LMC) algorithm with optimized varying step-size. This result has the advantage of being horizon free (we do not need to know in advance the target precision) and to improve by a logarithmic factor the corresponding result for the constant step-size. Second, we study the case where accurate evaluations of the gradient of the log-density are unavailable, but one can have access to approximations of the aforementioned gradient. In such a situation, we consider both deterministic and stochastic approximations of the gradient and provide an upper bound on the sampling error of the first-order LMC that quantifies the impact of the gradient evaluation inaccuracies. Third, we establish upper bounds for two versions of the second-order LMC, which leverage the Hessian of the log-density. We nonasymptotic guarantees on the sampling error of these second-order LMCs. These guarantees reveal that the second-order LMC algorithms improve on the first-order LMC in ill-conditioned settings. We study the problem of estimating multivariate log-concave probability density functions. We prove the first sample complexity upper bound for learning log-concave densities on @math , for all @math . Prior to our work, no upper bound on the sample complexity of this learning problem was known for the case of @math . In more detail, we give an estimator that, for any @math and @math , draws @math samples from an unknown target log-concave density on @math , and outputs a hypothesis that (with high probability) is @math -close to the target, in total variation distance. Our upper bound on the sample complexity comes close to the known lower bound of @math for this problem.