Online Two-Stage Submodular Maximization

Iasonas Nikolaou, Miltiadis Stouras, Stratis Ioannidis, Evimaria Terzi · 2025

Read Online Two-Stage Submodular Maximization by Iasonas Nikolaou, Miltiadis Stouras, Stratis Ioannidis, Evimaria Terzi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19480.txt.

Introduction

Iasonas Nikolaou, working with three co-authors, introduces an online version of two-stage submodular maximization, a selection problem used in tasks like influence maximization and data summarization. In the new version, the objective functions arrive one at a time rather than all at once. The goal stays the same: shrink the ground set so a randomly chosen objective still scores well on it.

The team designs an algorithm with sublinear regret guarantees under matroid constraints, covering both general matroids and uniform ones. The uniform-matroid result also improves the best known bound for the original offline problem. Experiments on real datasets confirm that the online method performs as the theory predicts.

Catalog record

CREATORIasonas Nikolaou, Miltiadis Stouras, Stratis Ioannidis, Evimaria Terzi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE134 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19480

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Online Two-Stage Submodular Maximization Iasonas Nikolaou, Miltiadis Stouras, Stratis Ioannidis, Evimaria Terzi Abstract 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 (1-1/e)^{2} -regret under general matroid constraints and ( 1 − 1 / e ) ​ ( 1 − e − k ​ k k / k ! ) (1-1/e)(1-e^{-k}k^{k}/k!) -regret in the case of uniform matroids of rank k 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. 1 Introduction Motivated by applications such as dictionary learning ( Maas et al. 2011 ) , data sumarization ( Lin and Bilmes 2012 ) , and recommender systems ( Yue and Guestrin 2011 ; El-Arini et al. 2009 ; Mirzasoleiman et al. 2016 ) , Balkanski et al. 2016 introduced the following Two-stage Submodular Maximization problem ( 2SSM ). Given a ground set V of n\in\mathbb{N} elements, in the first stage, an algorithm selects a set S\subseteq V of size |S|=\ell\in\mathbb{N} . In the second stage, a reward function f:2^{V}\to\mathbb{R}_{+} is sampled u.a.r. from a collection \mathcal{F} of monotone submodular functions; the function f is then optimized over subsets of S with size k<\ell . The goal of 2SSM is to select the restricted ground set S so that the expected second-stage reward is maximized; formally: Maximize: \displaystyle\quad F(S)\equiv\mathop{\mathbb{E}\/}\left[\max_{S^{\prime}\subseteq S:|S^{\prime}|\leq k}f(S)\right], (1a) subject to: \displaystyle\quad S\subseteq V,|S|\leq\ell, (1b) where the expectation is over the random function f\in\mathcal{F} . Balkanski et al. 2016 proposed an approximation algorithm for 2SSM . Subsequently, Stan et al. 2017 provided a generalization when the second stage optimization is over an arbitrary matroid (rather than a cardinality) constraint. The 2SSM problem is of significant interest when the second-stage optimization needs to happen in near real-time. For example, if the original ground set V is quite large, restricting the ground truth set prior to the revelation of the objective can yield significant computational dividends. Though applications are numerous (see Appendix A ), a canonical example is a recommender system ( Stan et al. 2017 ; Liu et al. 2022a ) . In this scenario, V is catalog of items to be recommended to a user cohort. Each user is described by a mononote submodular utility function f:2^{V}\to\mathbb{R}_{+} , sampled from a known distribution, that captures the value of a recommended set of items to the user. To speed-up recommendations and/or item delivery, the recommender a priori restricts recommendations to occur within a set S\subset V of size |S|=\ell items, where k<\ell<n . When users arrive, their utility is revealed, and the recommender suggests k items by solving the corresponding cardinality-constrained optimization problem. Restricting recommendations to S speeds up this computation; moreover, items in S can be, e.g., prefetched (non-realtime) to a cache, thereby also accelerating their delivery. This offline version of 2SSM , studied by Balkanski et al. 2016 and Stan et al. 2017 , assumes prior knowledge of the candidate objectives set \mathcal{F} (and the distribution over it). When set \mathcal{F} is unknown, it is natural to consider an online version, in which functions f\in\mathcal{F} are revealed sequentially, and the restricted ground set is adapted online. This Online Two-Stage Submodular Optimization ( O2SSM ) problem poses significant challenges: even though functions f\in\mathcal{F} are submodular, the first-stage objective F in ( 1a ) is not. Hence, O2SSM cannot be solved with existing online submodular maximization techniques ( Niazadeh et al. 2021 ; Matsuoka et al. 2021 ; Si Salem et al. 2024 ) . To make matters worse, even when the set \mathcal{F} is known, computing the objective F is itself NP-hard. As a result, any online algorithm solving O2SSM cannot even assume oracle access to the first-stage objective F(\cdot) , even after a sequence of second-stage objectives f has been revealed. Our main contribution is to overcome these challenges: we construct a no-regret online algorithm for O2SSM when objectives belong to a specific subclass of submodular functions, namely, Weighted Threshold Potential ( WTP ) functions ( Karimi et al. 2017 ; Stobbe and Krause 2010 ) . This subclass strictly generalizes weighted coverage functions and appears in applications such as recommender systems, team formation, and influence maximization. When \mathcal{F} is a subset of this class, we can construct a polynomial-time online algorithm that attains sublinear regret with respect to an offline approximation algorithm for 2SSM (with hindsight). We consider both general matroid and cardinality constraints for the second stage. In the latter case, our online algorithm yields also an improved approximation guarantee for the offline problem, when the objective is a WTP function (see Table 1 ). From a technical standpoint, we resolve the challenge of making online decisions without oracle access to the first-stage objective F(\cdot) . We do so by introducing a fractional relaxation of the objective and a corresponding rounding scheme. For Weighted Threshold Potential ( WTP ) objectives, we prove that this relaxation is concave and that its supergradients are efficiently computable. This enables us to use Online Convex Optimization ( OCO ) methods ( Hazan 2016 ) , such as Follow the Regularized Leader (FTRL) and Online Gradient Ascent (OGA), to compute fractional restricted ground sets with sublinear regret. We then seek a rounding scheme that converts fractional solutions to integral ones while preserving their expected reward up to a constant factor. We prove that Randomized Pipage Rounding ( Chekuri et al. 2009 ) has this property through a contention-resolution–based analysis that exploits submodular dominance, as exhibited the distribution induced by this rounding. 2 Related work Reference 2SSM O2SSM Setting Objective Function Constraints Offline Approx. Ratio Online \alpha -Regret Balkanski et al. 2016 1-\nicefrac{{1}}{{e}}-\nicefrac{{1}}{{k^{1/2-\epsilon}}}-e^{-\Omega(k^{2\epsilon})} – Offline Submodular Cardinality Balkanski et al. 2016 \nicefrac{{1}}{{2}}(1-\nicefrac{{1}}{{e}}) – Offline Coverage Cardinality Stan et al. 2017 \nicefrac{{1}}{{2}}(1-\nicefrac{{1}}{{e^{2}}}) – Offline Submodular Matroid Yang et al. 2021 \nicefrac{{1}}{{(p+1)}}(1-e^{-(p+1)}) – Offline Submodular p -Exchange System Mitrovic et al. 2018 \nicefrac{{1}}{{7}} – Streaming Submodular Matroid Mitrovic et al. 2018 \nicefrac{{1}}{{4}}(1-\nicefrac{{1}}{{e^{2}}}) – Distributed Submodular Matroid This paper (1-\nicefrac{{1}}{{e}})(1-e^{-k}\nicefrac{{k^{k}}}{{k!}}) \alpha=(1-\nicefrac{{1}}{{e}})(1-e^{-k}\nicefrac{{k^{k}}}{{k!}}) Online+Offline WTP Cardinality This paper (1-\nicefrac{{1}}{{e}})^{2} \alpha=(1-\nicefrac{{1}}{{e}})^{2} Online+Offline WTP Matroid Table 1 : Summary of known results for different settings of the Two-Stage Submodular Maximization ( 2SSM ) problem and its online version ( O2SSM ). Our work is the first to consider (and provide guarantees for) O2SSM . Our online algorithm can be converted to a new offline algorithm for 2SSM under WTP objectives (see Appendix J ). For cardinality constraints, the guarantees of both our (offline) algorithm and the one by Balkanski et al. 2016 converge to 1-1/e\approx 0.63 as k\to\infty ,

Read the complete text