An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood

2018/11/08 by Brian Axelrod, Gregory Valiant, Axelrod, Brian +1
Computer Science · Engineering · #Algorithms and Data Compression #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Medical Image Segmentation Techniques #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1811.03204

openalex publication_date 2018/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The log-concave maximum likelihood estimator (MLE) problem answers: for a set of points X₁,...X_n ∈ \mathbb R^d, which log-concave density maximizes their likelihood? We present a characterization of the log-concave MLE that leads to an algorithm with runtime poly(n,d, \frac 1 ε,r) to compute a log-concave distribution whose log-likelihood is at most ε less than that of the MLE, and r is parameter of the problem that is bounded by the ℓ₂ norm of the vector of log-likelihoods the MLE evaluated at X₁,...,X_n.

Citations

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes

Related

• A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
• Maximum likelihood estimation of a multidimensional log-concave density
• Theoretical properties of the log-concave maximum likelihood estimator of a multidimensional density
• Recent progress in log-concave density estimation