# Learning Submodular Sequencing from Samples

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 9 Sep 2024.

## Builds on (most cited first, 9 of 9)

- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [Optimal Sampling Gaps for Adaptive Submodular Maximization](https://mlsanity.com/paper/2104.01750/) (2021)
- [Network Inference and Influence Maximization from Samples](https://mlsanity.com/paper/2106.03403/) (2021)
- [Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees](https://mlsanity.com/paper/1304.0730/) (2013)
- [Sequential Submodular Maximization and Applications to Ranking an Assortment of Products](https://mlsanity.com/paper/2002.09458/) (2020)
- [Optimization from Structured Samples for Coverage Functions](https://mlsanity.com/paper/2007.02738/) (2020)
- [Learning Coverage Functions and Private Release of Marginals](https://mlsanity.com/paper/1304.2079/) (2013)
- [Ranking with submodular functions on a budget](https://mlsanity.com/paper/2204.04168/) (2022)
- [Non-monotone Sequential Submodular Maximization](https://mlsanity.com/paper/2308.08641/) (2023)

## Abstract (arXiv)

This paper addresses the problem of sequential submodular maximization: selecting and ranking items in a sequence to optimize some composite submodular function. In contrast to most of the previous works, which assume access to the utility function, we assume that we are given only a set of samples. Each sample includes a random sequence of items and its associated utility. We present an algorithm that, given polynomially many samples drawn from a two-stage uniform distribution, achieves an approximation ratio dependent on the curvature of individual submodular functions. Our results apply in a wide variety of real-world scenarios, such as ranking products in online retail platforms, where complete knowledge of the utility function is often impossible to obtain. Our algorithm gives an empirically useful solution in such contexts, thus proving that limited data can be of great use in sequencing tasks. From a technical perspective, our results extend prior work on ``optimization from samples'' by generalizing from optimizing a set function to a sequence-dependent function.