# Online Two-Stage Submodular Maximization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 74 references that are in the map.
- First posted on arXiv 22 Oct 2025.

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

- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency](https://mlsanity.com/paper/1404.0900/) (2014)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Neural Re-ranking in Multi-stage Recommender Systems: A Review](https://mlsanity.com/paper/2202.06602/) (2022)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [On component interactions in two-stage recommender systems](https://mlsanity.com/paper/2106.14979/) (2021)
- [Stochastic Submodular Maximization: The Case of Coverage Functions](https://mlsanity.com/paper/1711.01566/) (2017)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Adaptive Caching Networks with Optimality Guarantees](https://mlsanity.com/paper/1604.03175/) (2016)
- [An Efficient Framework for Balancing Submodularity and Cost](https://mlsanity.com/paper/2002.07782/) (2020)
- [Full Stage Learning to Rank: A Unified Framework for Multi-Stage Systems](https://mlsanity.com/paper/2405.04844/) (2024)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Maximizing Submodular Functions for Recommendation in the Presence of Biases](https://mlsanity.com/paper/2305.02806/) (2023)
- [Diversifying Music Recommendations](https://mlsanity.com/paper/1810.01482/) (2018)
- [Ascent Similarity Caching with Approximate Indexes](https://mlsanity.com/paper/2107.00957/) (2021)
- [The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem](https://mlsanity.com/paper/1909.04268/) (2019)
- [Matroid Secretary Is Equivalent to Contention Resolution](https://mlsanity.com/paper/2103.04205/) (2021)
- [A Simple Optimal Contention Resolution Scheme for Uniform Matroids](https://mlsanity.com/paper/2105.11992/) (2021)

## Abstract (arXiv)

Given a collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) [Balkanski et al., 2016] is to restrict the ground set so an objective selected u.a.r. from the collection attains a high maximal value, on average, when optimized over the restricted ground set. We introduce the Online Two-Stage Submodular Maximization (O2SSM) problem, in which the submodular objectives are revealed in an online fashion. We study this problem for weighted threshold potential functions, a large and important subclass of monotone submodular functions that includes influence maximization, data summarization, and facility location, to name a few. We design an algorithm that achieves sublinear (1 - 1/e)2-regret under general matroid constraints and (1 - 1/e)(1-e-kkk/k!)-regret in the case of uniform matroids of rank k; the latter also yields a state-of-the-art bound for the (offline) 2SSM problem. We empirically validate the performance of our online algorithm with experiments on real datasets.