  We explore computational aspects of maximum likelihood estimation of the
mixture proportions of a nonparametric finite mixture model -- a convex
optimization problem with old roots in statistics and a key member of the
modern data analysis toolkit. Motivated by problems in shape constrained
inference, we consider structured variants of this problem with additional
convex polyhedral constraints. We propose a new cubic regularized Newton method
for this problem and present novel worst-case and local computational
guarantees for our algorithm. We extend earlier work by Nesterov and Polyak to
the case of a self-concordant objective with polyhedral constraints, such as
the ones considered herein. We propose a Frank-Wolfe method to solve the cubic
regularized Newton subproblem; and derive efficient solutions for the linear
optimization oracles that may be of independent interest. In the particular
case of Gaussian mixtures without shape constraints, we derive bounds on how
well the finite mixture problem approximates the infinite-dimensional
Kiefer-Wolfowitz maximum likelihood estimator. Experiments on synthetic and
real datasets suggest that our proposed algorithms exhibit improved runtimes
and scalability features over existing benchmarks.
