Efficient Computation of Nonparametric Survival Functions Via a Hierarchical Mixture Formulation

Abstract

We propose a new algorithm for computingthe maximum likelihood estimate of a nonparametric survivalfunction for interval-censored data, by extending therecently-proposed constrained Newton method in a hierarchicalfashion. The new algorithm makes use of the fact thata mixture distribution can be recursively written as a mixtureof mixtures, and takes a divide-and-conquer approach tobreak down a large-scale constrained optimization probleminto many small-scale ones, which can be solved rapidly.During the course of optimization, the new algorithm, whichwe call the hierarchical constrained Newton method, can efficientlyreallocate the probability mass, both locally andglobally, among potential support intervals. Its convergenceis theoretically established based on an equilibrium analysis.Numerical study results suggest that the new algorithmis the best choice for data sets of any size and for solutionswith any number of support intervals.