# A Memoization Framework for Scaling Submodular Optimization to Large Scale Problems

arXiv: https://arxiv.org/abs/1902.10176 · HTML: https://mlsanity.com/paper/1902.10176/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2019.

## Built on by (most cited first, 8 of 8)

- [SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios](https://mlsanity.com/paper/2107.00717/) (2021)
- [TALISMAN: Targeted Active Learning for Object Detection with Rare Classes and Slices using Submodular Mutual Information](https://mlsanity.com/paper/2112.00166/) (2021)
- [PLATINUM: Semi-Supervised Model Agnostic Meta-Learning using Submodular Mutual Information](https://mlsanity.com/paper/2201.12928/) (2022)
- [Theoretical Analysis of Submodular Information Measures for Targeted Data Subset Selection](https://mlsanity.com/paper/2402.13454/) (2024)
- [E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time](https://mlsanity.com/paper/2506.07747/) (2025)
- [STENCIL: Submodular Mutual Information Based Weak Supervision for Cold-Start Active Learning](https://mlsanity.com/paper/2402.13468/) (2024)
- [Multimodal Consistency-Guided Reference-Free Data Selection for ASR Accent Adaptation](https://mlsanity.com/paper/2602.13263/) (2026)
- [Complement Submodular Information Measures for Balanced and Robust Data Selection](https://mlsanity.com/paper/2605.24779/) (2026)

## Abstract (arXiv)

We are motivated by large scale submodular optimization problems, where standard algorithms that treat the submodular functions in the value oracle model do not scale. In this paper, we present a model called the precomputational 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, optimization with submodular constraints 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 precomputational 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.