A Memoization Framework for Scaling Submodular Optimization to Large Scale Problems


Rishabh Iyer, Jeffrey Bilmes ;
Proceedings of Machine Learning Research, PMLR 89:2340-2349, 2019.


We are motivated by large scale submodular optimization problems, where standard algorithms, which treat the submodular functions in the value oracle model, do not scale. In this paper, we present a new model called the pre-computational complexity model, along with a unifying memoization based framework, which looks at the specific form of the given submodular function. A key ingredient in this framework, is the notion of a precomputed statistic, which is maintained in the course of the algorithms. We show that we can easily integrate this idea into a large class of submodular optimization problems including constrained and unconstrained submodular maximization, minimization, difference of submodular optimization, ratio of submodular optimization and several other related optimization problems. Moreover, memoization can be integrated in both discrete and continuous relaxation flavors of algorithms for these problems. We demonstrate this idea for several commonly occurring submodular functions, and show how the pre-computational model provides significant speedups compared to the value oracle model. Finally, we empirically demonstrate this for large scale machine learning problems of data subset selection and summarization.

Related Material