Online Two-Stage Submodular Maximization
Authors: Iasonas Nikolaou
Miltiadis Stouras
Stratis Ioannidis
Evimaria Terzi
Venue: NeurIPS 2025 poster ()
Keywords: online
two-stage
submodular maximization
recommender systems
data summarization
Primary area: optimization

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$-regret under general matroid constraints and $(1 - 1/e)(1-e^{-k}k^k/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.

Online Two-Stage Submodular Maximization
Iasonas Nikolaou'
Miltiadis Stouras EPFL
Stratis Ioannidis Northeastern University
Evimaria Terzi Boston University
Boston University
Abstract
Given collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) [Balkanski et al., 2016] is to restrict the ground set 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 (02SSM) problem, in which the submodular objectives are revealed in an online fashion. We study this problem for weighted threshold potential functions, 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 under general matroid constraints and (1 1/e) e e-* /k:)- regret the case of uniform matroids of rank k; the latter also yields state-of-the. art bound for the (offline) 2SSM problem. We empirically validate the performance 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 al., 2016], Balkanski et al. [2016] introduced the following Two-stage Submodular Maximization problem (2SSM). Given ground set V of algorithm selects a set S S V of size |S| = E N. the second stage, a reward function f: 2 R, is sampled u.a.r. from collection F of monotone submodular functions; the function is then optimized over subsets of with size i < The goal of 2SSM to select the restricted ground set S so that the expected second-stage reward is maximized; formally:
N elements, in the first stage, an
Maximize: F(S) = E
max SCSIS
S(S)
(la)
subject to:
$ S
(1b)
where the expectation is the random function f E F. Balkanski et al. [2016] proposed an approximation algorithm for 2SSM Subsequently, Stan et al. [2017] provided a generalization when the second stage optimization over arbitrary matroid (rather than cardinality) constraint.
The 2SSM problem of significant interest when the second-stage optimization needs 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 recommender system [Stan al., 2017, Liu et al., 2022a]. In this scenario, V is catalog of items to be recommended user cohort. Each user is described by mononote submodular utility function f 2" - R,, sampled
"qqual Contribution, nikolaou@bu. edu 1 Equal Contribution, miltiadis. wal.iadissstourasdeee..... stouras@epfl.cc ch teeniidissoottestteeeee edu evimaria@bu.com edu
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Reference
0255N Online o-Regret
Setting
Objective Function
Coustruints
Offline Appeos, Ratio
Bolkanski [2016]
5/4 1pprre 1007
Offine
Suhmodular
Cardinality
Balkanski al. [2016]
1/(11 166
Ofllnne
Coverage
Cardinality
Ston et al. [2017]
1/(1 - 1/-)
Offine
Submocuular
Matroid
Yang al. [2021]
H/ n(1 16
Offine
Suhmodular
y- p-Exchanpe System
Mitrovic et al. 12018)
37
Streaming
Suhmodular
Matroid
Mitrovic et al. [2018]
1/[1 - 1/4)
Distributed
Submocular
Matroid
This paper
Online+Olliine
Cardinality
This paper
(1 1/19
(1 1/)
Online+OElliee
WIP
Matroid
Table I: Summary of known results for different settings of the Two-Stage Submodular Maximization (2SSM) problem and its online version (02SSM). Our work is the first to consider (and provide guarantees for) 02SSM. Our online algorithm can be converted 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/e s 0.63 as A - oo, but our algorithm has a strictly better guarantee for finite k E N. For general matroids, our guarantee for 2SSM ((1 - 1/e)² R 0.40) slightly worse than the one by Stan et al. [2017] (1/2(1 - 1/ 1/e²) R 0.43).
new offline algorithm for 2SSM
from 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 C V of size [S] = É items, where & < f < n. When users arrive, their utility is revealed, and the recommender suggests & items by solving the corresponding cardinality-constraiiee optimization problem. Restricting recommendations to S speeds up this computation; moreover, items in S can be, e.g., prefetched (non-realtime)
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 J (and the distribution over it). When set F is unknown, is natural to consider an online version, in which functions f E F are revealed sequentially, and the restricted ground set is adapted online. This Online Two-Stage Submodular Optimization (02SSM) problem poses sigmificant challenges: even though functions f E F are submodular, the first-stage objective F' in (Ia) is not. Hence, 02SSM 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 F is known, computing the objective F is itself NP-hard. As result, any online algorithm solving 02SSM cannot even assume oracle access to the first-stage objective F(.), even after sequence of second stage objectives has been revealed.
Our main contribution is to overcome these challenges: we construct a no-regret online algorithm for 02SSM 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 F is a subset of this class, we can construct polynomial-time online algorithm that attains sublinear regret with respect to 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 improved approximation guarantee for the offline problem, when the objective is a WTP function (see Table I).
From technical standpoint, we resolve the challenge of making online decisions without oracle access to the first-stage objective F(.) We do so by introducing a fractional relaxation the objective and 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 (DCO) 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 contention- contention-resolltionn baasedd analysis that exploits submodular dominance, as exhibited the distribution induced by this rounding.
2 Related work
Two-stage Submodular Maximization. Balkanski et al. [2016] introduced the Two-stage Submodu-
lar Maximization problem (2SSM) under cardinality constraints and proposed an - (1-1/e-((L/V/)

---

approximation algorithm. Their algorithm also optimizes a continuous relaxation and applies basic randomized rounding scheme twice: first, select the restricted ground set, and then to generate second-stage solutions. Our work departs from [Balkanski et al., 2016] in three ways: (a) we introduce the online variant of the problem, where the objectives arrive sequantially, (b) we generalize the second stage to general matroids and (c) improve both rounding stages: we use randomized pipage rounding [Chekuri et al., 2009] in the first stage (which incurs no loss) and state-of-the-art con- tention resolution schemes in the second stage [Dughmi, 2020]; this yields improved approximation guarantees when applied to the offline setting (see Table and Appendix J).
Balkanski et al. [2016] also propose local search algorithm for coverage functions under cardinality constraints that achieves an (1/2(1 - 1/c)) approximation. Building on this, Stan et al. [2017] design an (1/2(1 - 1/22)) [ap"))aapproximmation algorithm that works for arbitrary monotone submodular functions under general matroid constraints. The latter is the state of the art in the offline setting, though a gap persists between its guarantee and the hardness threshold of (1 1/6). Several works have since extended this algorithm to settings with weakly submodular functions [Chang et al., 2023], bounded curvature submodular functions [Li et al., 2023], or knapsack constraints in the first stage [Liu et al., 2022b]. Stan et al. [2017] leave the online version of the problem, which we address in this paper, as open question. Our algorithm achieves (1 1/2)² 0.40 approximation under general matroid constraints and WTP functions, which is close to the state-of-the-ar (1/2(1 - 1/22) z 0.43 approximation for the offline problem. Notably, our online algorithm is competitive with the best- known approximation algorithm in hindsight, without accessing the objective sequence in advance.
Streaming Two-Stage Submodular Maximization. Mitrovic et al. [2018] study the two-stage submodular maximization problem in the streaming setting, where the algorithm makes a single sequential pass over the ground set and must irrevocably decide whether to include or discard each element, while using limited memory. They design algorithms that achieve constant-factor approximations under matroid constraints. In contrast, we consider an online setting in which the objective functions, not the elements, are revealed sequentially. Note that, in the streaming setting, the al algorithm has access to all functions while making its decisions, while the online setting requires making decisions without knowledge of the objectives.
(One-stage) Online Submodular Maximization. Several online algorithms have been proposed for maximizing submodular functions under various matroid constraints [Streeter et al., 2009, Harvey et al., 2020, Niazadeh et al., 2021, Matsuoka et al., 2021, Si Salem et al., 2024]. There has also been recent work on the online maximization of continuous DR- DRssubmodular functions [Chen et al., 2018 Zhang et al., 2019, 2022]. Our work builds on the recent results of Si Salem et al. [2024], who reduce Online Submodular Maximization (OSM) to Online Convex Optimization (OCO) for the class of WTP functions. WTP functions, introduced by Stobbe and Krause [2010], form a broad and important sub- class of monotone submodular functions, with applications including influence maximization [Kempe et al., 2003], facility location [Krause and Golovin, 2014], caching networks [loannidis and Yeh, 2016, Li al., 2021]. similarity caching [Si Salem al., 2022], recommender systems [Krause and Golovin, 2014], and weighted coverage functions [Karimi et al., 2017]; we review some of these in Appendix A. Our main point of departure from Si Salem et al. [2024] and, more broadly, OSM, is that the objective in 02SSM is not submodular; in fact, we cannot even assume that we have polytime oracle access to it. Overcoming this obstacle is one of our main contributions.
3 Technical Preliminary
Submodular Functions and Matroids. Given a ground set V [n] [n]= (I..... n). a set function
f: 2n + R4 is submodular if f(Au (o}) f(A) > f(B U (w)) (BB) for all A C B C V and
v E VV \ B, and monotone if f(A) S f(B) for all A C C 2". A matroid is a pair M = (V,I). where I C 2", for which the following holds: (f) B E I and A C B, then A I. (ii) if A, B e and |A| < [B], then there exists a v E B \ A s.t. AU {u) E I. The elements of are called independent sets. The cardinality of the largest independent set is called the rank of the matroid M.
The characteristic vector & E (0. 13" of a set S C [n] the vector whose i-th coordinate x; is 1 if and only if E S. The matroid polytope P(M) is the convex hull of the characteristic vectors of M's independent sets. For the remainder of the paper, we will identify sets C V = [n] with their characteristic vectors x E 10.1)% Hence, we treat matroids M subsets of {0, 1)", while
3

---

P(M) S [0, 1]". Similarly, with slight abuse of notation, we refer to functions f: + RR via their equivalent representations as functions of binary vectors f: {0, + R,.
Two-Stage Submodular Maximization. In the two-stage submodular maximization setting of Balka- nski et al. [2016], functions over the ground set = [nx]. The goal is to select a smaller ground ser that yields a high objective value in expectation, when the function be maximized is selected u.a.r. from F.
given a collection F {fr)/=1 of monotone and submodular objective
Formally, let X2 S {0. 1) be the uniform matroid of rank over the ground set [n]. i.e.
X - (æ E {0,1)" Ei
For a E Xg and matroid M, let (2) S {0, 1 be all independent sets in M that are subsets of 2, i.e.:
J'M(2) ty E 10, y E M, y x}
Given fe E F, we define:
F((x)=
max fe(y), for Xt, MEYx(())
to be the objective attained by maximizing ft over the restriction of M to subsets of æ. Then, the Two-Stage Submodular Maximization (2SSM) problem can be stated as:
Maximize : F(x) =(=)=E=n Fe(x))
(3a)
subj. to: x Xt.
(3b)
In the recommender system example from the introduction, .M = Rr. i.e., the uniform matroid of rank S and J is a of user utility functions ft, capturing the value of recommended set to user t. Notice that 2SSM generalizes (one-stage) submodular maximization subject to a cardinality constraint, we set L k. and is therefore NP-hard to approximate within a factor better than 1/c [Feige, 1998]. Moreover, even computing (x))) for given is NP-hard, so polynomial -tim algorithm for 2SSM cannot assume oracle access F(.). Finally, the function F(-) not submodular [Balkanski et al., 6016], and approximation algorithms cannot readily rely on this property. Nevertheless, as discussed in Sec. 2, there exist polytime approximation algorithms for 2SSM
Online Convex Optimization (OCO). Online Convex Optimization (OCO), an algorithm makes sequential decisions in order to maximize concave reward functions that are revealed in online fashion. Formally, at each time step / = 1,..., T, a decision maker selects an æ; from a compact and convex set K., and then observes concave reward function d: : K. R. Decision æ; is made via a (possibly randomized) online algorithm (x) which takes as input the history of reward functions and decisions before time t; that is,
æ; = Px (1gr, (g),,,)))++ +-)
The goal of the decision maker is to minimize the regret, defined as:
T
Rr = max
Σ (x) (x) Σ (xx))
ZEK
[=1
Intuitively, sublinear regret (a.k.a. no-regret) implies that the cummulative reward of the online algorithm is comparable to the one attained by the optimal algorithm in hindsight. Standard algorithms, such Follow-the-Regude Regularized-Lendeee (OGA) [Zinkevich, 2003] achieve sublinear regret under mild assumptions:
(FTRL) Shwwar-S 2012] and Online Gradient Ascent
Theorem 3.1. [Hazan, 2016] Let {g be sequence of concave functions, each L-Lipschitz (with respect to the & norm) over convex and compact domain K. with Ey-diameter D. Then, FTRL and OGA achieve a regret bound of O (DINT).
We provide detailed description of FTRL and OGA in Appendix H.
It is worth noting that 2SSM remains Na-hard even if one has oracle access to F()).

---

Q- Regret. In many online combinatorial optimization problems (e.g., [Streeter et al., 2009, Harvey al., 2020, Gergatsouli and Tzamos, 2022, Christou et al.. 2023]), especially those whose offline counterparts are NP-hard, the performance of an online algorithm Px, (-) is evaluated relative to the best a-approximate solution in hindsight. This measured through a-Regret [Kakade et al., 2007]:
T E((t.))
RA. max E F((x) TEAt
The goal is then to design online algorithms that attain sublinear (e.g.. ((vT)) expected a-Regret, having thus a cumulative reward competitive with that of a-approximate offline algorithm. This relaxation is necessary in our setting (D2SSM), as achieving sublinear regret for a would imply a polynomial- solution to the (NP-hard) offline problem.
Weighted Threshold Potentials. Weighted Threshold Potential ( (WTP) function [Stobbe and Krause, 2010, Si Salem et al., 2024] is a submodular function of the form:
f(v)
Σ Cy min (bg. y w,}, for (0.1)", JEC
where C is an arbitrary index set, CJ > 0. b, Rz0 U {oo} and w, Rzo. For an extensive review of WTPs, we refer to Appendix B of Si Salem et al. [2024]. Given a WTP function f. its concave relaxation f is the concave function obtain by relaxing the domain of f to be [0, 1J" i.e.
F(y) = Σ cj min (by, y wy}, for y E [0,1]".
(6)
jEC
We will use Fa.M to denote the class of WTP functions as defined in Eq. (5), that have at most terms
(IC) < G) and whose parameters are upper bounded by M (eg S M, M, ||||| lo S M, Vj E C).
4 Online Two-stage Submodular Maximization (02SSM)
In this section, we define the Online Two-stage Submodular Maximization (02SSM) problem. Using our rumning example of a recommender system, we assume that the set F is not known a priori, and the user utilities are revealed sequentially. In turn, the recommender system maintains and adapts its cache of & E N items as utilities are revealed, via an online algorithm that has access only to the history of utilities and caching decisions.
The 02SSM Problem. Formally, at each time step 1 N, a decision maker selects a o, X of size at most & E N to serve as a (restricted) ground set. After committing to æt, monotone submodular function fe : {0, 1]" R4 is revealed, and the decision maker accrues reward:
F((x)) = max fe())),
where M is matroid (e.g., . = X₁, for K t).
The set x, Px, x+) is selected without knowledge of the function fc. by online algorithm that has only access to past history.
02SSM poses two significant challenges: first, the reward functions Fe(.) are not submodular, and the problem does not reduce to standard Online Submodular Maximization. Second, to make matters worse, evaluating functions F.(.) for a given is NP-hard. As a result, the online algorithm Px, (-) cannot assume oracle access to reward function F., even after ft has been revealed. Nevertheless, functions fo belong to the WTP class, we can indeed construct polynomial time online algorithm that attains sublinear a-regret, as we show in the next section.
5 Our Algorithm
In this section, we present RAOCO (Algorithm 1), an algorithm that achieves sublinear (1 - 1/ Regret for WTP functions under arbitrary matroid constraints on the second stage. When the second- stage matroid is a uniform matroid of rank & (i.e., cardinality constraints), RAOCO achieves an improved guarantee namely sublinear (1 1/e)(1 e k Regret.
Wheee the expectation is w.r.t. any random choices of the online algorithm Px,-
5

---

Algorithm I Rounding-Auggmented OCO (RAOCO)
1: Uses:
2: (I) FTRL OGA OCD policy Px; (see Appendix H)
3: (2) Randomized Pipage Rounding E Xt Xg (see Appendix I)
4: for t= to T do
5:
Tt - Px. X
F Fi-1)
Compute fractional solution
6:
I; f (
Round to obtain the integral solution
7: Play action
Accrue reward Fi (xxy (implicitly)
8: Construct relaxation Ft from ft
Function fi has been revealed
9: end for
5.1 Description of the Algorithm
At high level, RAOCO uses an OCO policy (such as FTRL or OGA), which outputs a fractional restricted ground set ã. Xr. It then rounds the fractional ground set ãe to integral ground set 24 E Xe using Randomized Pipage Rounding [Chekuri et al., 2009]. Importantly, we prove that the rounding procedure preserves, in expectation, the quality of the fractional solution produced by the 0C0 policy. We now describe each step of the algorithm in more detail.
Fractional Relaxation. We begin by introducing fractional relaxation of the reward function. Let
X E []. E 5
denote the convex hull of the feasible restricted ground sets X₁. Given ã X, and a matroid M, we also define the corresponding relaxed set of second-stage feasible solutions as
(T) = Iū [0, P(M), 5 x)
where P(M) denotes the matroid polytope associated with M..
Let f WTP function, as defined in Eq. (5), and f' be concave relaxation, as defined Eq. (6). then define the concave relaxation of the reward function/first-stage objective as
F
f(y). for ã E &t. (E)
max
(8)
As discussed below, we prove that F' is indeed concave and Lipschitz over Xe, and that both F and its supergradients can be computed in polynomial time. These properties are in stark contrast to the original reward function maXye)(()) fz)) whose evaluation is NP-hard.
Algorithm. Our algorithm, RAOCO, is summarized in Algorithm 1. operates using two main subroutines: (a) an OCO policy Pxx that maintains fractional restricted ground sets over X₁, and (b)
rounding scheme X4 + X' that maps fractional solutions to integral ones.
At each time step t > 1. the algorithm computes fractional solution ã using the OCO policy, based on the history of concave relaxations of reward functions revealed so far; then, it rounds the fractional solution to an integral ground set via the randomized rounding scheme. Formally,
PPe (I(Tr,
and 2r E(x.),
where Px, is instantiated either FTRL OGA (see Appendix H), and that the rounding scheme E: Xe X₁ is Randomized Pipage Rounding [Chekuri et al., 2009] (see Appendix I).
Note that, after selecting the restricted ground set æt, the algorithm observes the WTP function fr and constructs the fractional relaxation F, of its corresponding reward function F;; the history these (concave) functions is then passed to DCO policy Px, to produce Æz-1- Moreover, E is randomized, so is RAOCO; characterization of the expected regret will be w.r.t. this randomness.

---

5.2 Main Result
Our main contribution is the following theoretical guarantee of RAOCO:
Theorem 5.1. Fix matroid M S [n] and f, k N. For any sequence of WTP functions {f-) C
FG.M, Algorithm runs in polynomial time in n, G and log M and exhibits sublinear C.M 1//e- Regret, ie..
E|R E - (IGM.VTT)
where CM = e1-e-kph /k!) if M is uniform matroid of rank k and cM (1 - 1/c) otherwise.
The proof of Theorem 5.1 relies on two key ingredients: First, we show that the sequence of fractional restricted ground sets computed by the OCO policy has sublinear regret in the fractional relaxation of the problem (Lemma 5.2). Second, we show that applying Randomized Pipage Rounding to a fractional restricted ground set yields an integral ground set that, expectation, admits second- stage solutions with approximately the same value as those in the original fractional ground set. Consequently, the reward obtained from the rounded ground set approximately the same as that of the original fractional ground set (Lemma 5.4).
We now describe each of these components in more detail and use them in order prove Theorem 5.1.
Regret of the fractional DCO policy. Recall that the concave relaxation F. defined in Eq. (8), a function that maps fractional ground sets to the solution of an optimization problem, whose constraints dictated by the given fractional ground set. Despite the intricate relation between fractional ground set and its reward, we prove in Appendix D that F is concave and Lipschitz over X when the second-stage setnnd objective f is WTP function with bounded coefficients. These two key properties allow us to employ the standard regret analysis of OCO policies (Theorem 3.1) to show that the sequence of fractional ground sets that the algorithm computes will have no-regret. We state this formally in Lemma 5.2, whose proof is in Appendix D:
Lemma 5.2. Let (fet=1 C FG,M be sequence of WTP functions, let {FoJi=z be the corresponding reward functions as defined in Eq. (7) and ( (F:)T= be the corresponding concave relaxations the reward functions as defined in Eq. (8). Suppose that {ār}?== is the sequence of fractional restricted ground sets computed by the OCO policy of Algorithm 1. Then,
1T
T
T
max R
Σ
Fr(x))
Σ -
- (IGMN-VvTT))
Furthermore, we show that the supergradients of the fractional reward function can be computed in polynomial time by solving a linear program. This implies that standard OCO policies like FTRL or OGA, which use the supergradient of the reward function to calculate the next response, have polynomial time implementations. In particular, the following lemma holds:
Lemma 5.3. Let f E FG.M A be a WTP function and let be the corresponding fractional reward function, defined in Eq. (8). For any fractional restricted ground set 0 E Xr, both the time to compute F and the time compute a supergradient of F at ã polynomial in n. G and log M.
The proof of Lemma 5.3 is in Appendix E.
Randomized Rounding Bound. Our next goal is to show that the value of the reward function is preserved, in expectation, when passing from a fractional ground set to an integral one via Randomized Pipage Rounding. Specifically, we aim to prove that optimizing over the rounded ground set yields second-stage solutions whose value closely approximates those obtainable in the fractional domain.
To this end, we design a two-stage randomized rounding procedure, used only in our analysis, that coupled with the rounding performed by RAOCO. Given any fractional second-stage solution, this procedure first produces an intermediate integral solution within the rounded ground set, which potentially violates the matroid constraints, and then applies a contention resolution scheme (CRS) to obtain a feasible solution (for more details CRSs, see Appendix B). A key technical challenge is that standard CRS guarantees typically rely on the input vector being sampled independently across coordinates, an assumption that does not hold in our setting. However, when the ground set is obtained
7

---

via Randomized Pipage Rounding, we prove that the resulting distribution exhibits submodular dominance property that allows us to apply CRS with provable approximation guarantees. In particular, the CRS ensures that, in expectation, the quality of the resulting feasible solution remains close to that of the original fractional solution.
We stress that we use this CRS construction purely to characterize the performance of the (first-stage) randomized rounding, and not the online algorithm itselff the only rounding procedure in RAOCO is Randomized Pipage Rounding (see Algorithm 1), We leverage the CRS construction to show that the expected reward from the rounded ground set is within a constant factor of the reward from the fractional solution. This is formalized in Lemma 5.4 and proved in Appendix C.
Lemma 5.4. Let I Xe be fractional ground and { be integral ground set obtained by rounding using Randomized Pipage Rounding. Let also f be any WTP function, and F, F be the associated reward function and its concave relaxation (Eq. (7) and (8) respectively. Then,
E (F(E(T)) 2 CM (1--)) FF())
where CM 1 c- kk* /kl if the matroid M of the second stage is uniform with rank k. and CM = (1 - 1/c) otherwise.
Finally, using Lemmas 5.2, 5.3 and 5.4, our main theorem, Theorem 5.1, can be proved as follows.
Proof of Theorem 5.1. Regret Guarantee. Let {Fa)T= be a sequence of reward functions and Fi...., Fr be their concave relaxations (see Eq. (7) and (8) respectively). The expected regret of the Algorithm is
([ c 1/e)
max x
F((x)
E EE (F.(((()))
T
T Σ (()))) 1=1
Lem, 5.4
S
CM(1 1/e)
max mEX
F((x)
Lom, 5.2 O(LGM2
Computational Complexity. Each round of RAOCO consists of two steps: (1) computing a fractional solution through an OCO policy (either FTRL or OGA, see Appendix H for details), and (2) rounding this solution to an integral ground set. In order to run the OCO policy, RAOCO first computes a super- gradient of the concave relaxation function F at the previous solution Tt-1- This supergradient can be computed in polynomial time in n, and log M (Lemma 5.3) by solving linear program (see Appendix E). Next, depending on the instantiated OCO policy, the algorithm either performs projection onto X₁ (for OGA) which can be done in (n log n) time [Duchi et al., 2008], solves strongly convex optimization problem (for FTRL), which can be done in polynomial time in n and log M using standard first-order or interior point methods [Bubeck, 2015]. Finally, the fractional point obtained from the OCO policy is rounded via Randomized Pipage Rounding [Chekuri et al., 2009]. The rounding iteratively selects two fractional coordinates and redistributes their combined mass in a randomized way (for more details see Appendix 1). Each such iteration runs in time (()) and the algorithm will perform most ((n) iterations until all coordinates are integral. Overall, the per-round complexity of RADCO is polynomial in n. G and log M.
6 Experiments
In this section, we evaluate the performance of our algorithm on both real and synthetic datasets. Additional details on each dataset, how it maps to instances of 02SSM, our choices of k, f, and T, as well as detailed descriptions of competitor algorithms, can be found in Appendix F.?
Datasets and Problem Instances. We conduct experiments on seven datasets; five real: Wikipedia, Images, MovieRec, Influence and HotpotQA, and two synthetic: TeamFormation
Our code is available online at https: //github//tt com/ wtwp://assomiikkooooooooooalaaaa taro--tttte-----e

---

Dataset
e.
k
m
[C]
Description
Wikipedia
407
20
5
88
22
27.2
Wikipedia articles representatives
Images
150
20
40
10
20.9
Image collection summarization
MovieRec
1000
10
4
400
100
2.5
Movie recommendations
TeamFormation
100
10
4
50
50
1.0
Roster selection
Influence
34
8
3
100
100
34.0
Influence maximization
Coverage
100
20
500
20
1.95
Weighted Coverage
HotpotQA
111,140
150
4
500
97,852
1
QA Corpus summarization
Table Dataset summary: the number of elements; is the restricted ground set size; k the second-stage cardinality; 7 is the number of time steps; m is the number of objective functions; [C the average number of Threshold Potentials per function.
and Coverage. The Wikipedia, Images, and MovieRec datasets are drawn from prior work [Balka- nski et al., 2016, Stan et al., 2017]. The Coverage dataset is constructed adversarially to highlight the differences between one-stage and two-stage submodular optimization (see Appendix F).
Table 2 summarizes the key properties of each dataset.
Algorithms. We experiment with different variants of RAOCO (Algorithm 1). The variants dif- fer the OCO policy used in the fractional domain; thus, we have RAOCD-OGA, RAOCO-FTRL-L2, RAOCO-FTRL-EI where use Online Gradient Ascent (OGA), Follow the Regularized Leader (FTRL) with Le regularization and entropy regularization respectively.
Competitor Algorithms. We compare our method with the following online competitors: (1) Random, which selects of & elements uniformly at random each timestep. (2) One -tagee-GAA LSSOGA), which runs 140C0-OGA as if the second stage cardinality constraint was k = L, i.e., (one-stage) online WTP maximization. We also provide benchmarks the offline algorithms proposed by prior work, i.e. -wwosmopttitiizeeeeeeeee-e (OFLN-RGR) [Stan et al., 2017]. Finally, we report the value of the optimal (integral) solution in hindsight (OPT).
(OFLN-CO) [Balkanski et al., 2016] and pepllacemen-rreeee
Metries. For the online algorithms, we measure the cumulative average reward C; = Σt= F((w)). For each dataset, we report the average C, and its standard deviation over five
Results. Figure shows the average Ct over time t, for each algorithm and each dataset except HotpotQA; the latter, along with additional results with varying and f, can be found in Appendix G. In all cases, two-stage variants RADCO (RAOCO-OGA. form match the one-stage baseline (1S-OGA). The performance gap is particularly pronounced on the Influence, Images, and Coverage datasets. In Coverage, our algorithms achieve almost dou- ble the average reward of 1S-0GA (see Appendix F). Note that OFLN-CO does not apply to Coverage since it requires 1, while & = in that case.
FTRL-F,
outper-
7 Conclusion
We introduce the 02SSM problem and proposed RADCO, polynomial-time algorithm that achieves sublinear a-regret for WTP functions under general matroid constraints. Our method leverages online convex optimization over concave relaxation of the reward and combines it with randomized pipage rounding to obtain integral solutions with strong theoretical guarantees and practical performance.
Limitations and Future Directions. Our analysis is restricted to WTP objectives and assumes full- information feedback. Extending our framework general monotone submodular functions and parrial-revelationnannii feedback remains an interesting open direction.

---

RACCO-OGA
MACCO-TRIAA2
MOCOEETRIH
15036
OFNN-GO
OPEN
30
00.60
10
0.55
100
Steps
(a) Wikipedia
(h) Images
(c) TeamFormation
12.5
80-
1.000
5.0
20-
0.0
402
40
Time
Time
(d) MovieRec
(e) Infnuence
(1) Coverage
Figure I: Cumulative average reward C, of RAOCO variants and baselines for each dataset. We report the average value of C, over 5 runs. The shaded regions correspond to one standard deviation above and below the average. Note that OFLN-RGB coincides with OPT all datasets.
Acknowledgments and Disclosure of Funding
We gratefully acknowledge support Miltiadis Stouras by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00054, to Stratis loannidis by National Science Foundation grant 21 12471,, and partial support to lasonas Nikolaou and Evimaria Terzi through gifts from Microsoft and Google.
References
Rakesh Agrawal, Christos Faloutsos, and Arun Swami. Efficient similarity search in sequence databases. In Foundations of Data Organization and Algorithms: 4th International Conference, FODO'93 Chicago, Illinois, USA, October 13-15, 1993 Proceedings pages 69-84. Springer, 1993.
Eric Balkanski, Baharan Mirzasoleiman, Andreas Krause, and Yaron Singer. Learning sparse combinatorial representations via two-stage submodular maximization. In International Conference on Machine Learning, pages 2207-2216. PMLR, 2016.
Bart H Boon and Gerard Sierksma. Team formation: Matching quality supply and quality demand. EJOR, 2003.
Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. Proceedings of the twenty-fifth annual ACM-SIAM symposium Discrete algorithms, pages 946 957. SIAM, 2014.
Stephen Boyd. Convex optimization. Cambridge UP, 2004.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357 2015.
Hong Chang, Jing Jin, Zhicheng Liu, Ping Li, and Xiaoyan Zhang. Two-stage non-submodular maximization. Theoretical Computer Science, 968:114017, 2023. ISSN 0304-3975.
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding for matroid polytopes and applications. arXiv preprint arXiv:0909.42: 4348, 2009.
10

---

Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the forty-third anmual ACM symposium on Theory of computing, pages 783-792, 2011.
Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. In International Conference on Artificial Intelligence and Statistics, pages 1896-1905. PMLR, 2018.
Dimitrios Christou, Stratis Skoulakis, and Volkan Cevher. Efficient online clustering with moving costs. Advances in Neural Information Processing Systems, 36:25325-25533 25364, 2023.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM conference recommender systems, pages 191-198, 2016.
John Duchi, Shai Shalev- Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the l--ball for learning in high dimensions. In Proceedings of the 25th international conference Machine learning, pages 272-279, 2008.
Shaddin Dughmi. The outer limits of contention resolution on matroids and connections to the secretary problem. In 47th International Colloquium on Automata, Languages, and Programming Zentrum für Informatik, 2020.
(ICALP 2020). Schloss- Schlos--Dusstull-Lebbbe
Shaddin Dughmi. Matroid secretary is equivalent to contention resolution. Innovations in Theoretical Computer Science (ITCS), 2022.
Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimiza- tion-Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5-9, 2001 Revised Papers, pages 11-26. Springer, 2003.
Khalid El-Arini, Gaurav Veda, Dafna Shahaf, and Carlos Guestrin. Turning down the noise in the blogosphere. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 289 298, 2009.
Mark Everingham and John Winn. The pascal visual object classes challenge 2012 (voc2012) development kit. Pattern Analysis, Statistical Modelling and Computational Learning, Tech. Rep, 8(5):2-5, 2011.
Ariel Evnine, Stratis loannidis, Dimitris Kalimeris, Shankar Kalyanaraman, Weiwei Li, Israel Nir, Wei Sun, and Udi Weinsberg. Achieving a better tradeoff in multi-stage recommender systems through personalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4939-4950, 2024.
Uriel Feige. A threshold of In n for approximating set cover. Journal of the ACM (JACM), 45(4): 634 652, 1998.
Alan M Frieze. A cost function property for plant location problems. Mathematical Programming, 1974.
Evangelia Gergatsouli and Christos Tzamos. Online learning for min sum set cover and pandora's box. In International Conference on Machine Learning, pages 7382-7403. PMLR, 2022.
Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. Similarity search in high dimensions via hashing. In Vldb, volume 99, pages 518-529, 1999.
Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (täs), 5(4):1-19, 2015.
Nicholas Harvey, Christopher Liaw, and Tasuku Soma. Improved algorithms for online submodular maximization via first-order regret bounds. Advances Neural Information Processing Systems, 33:123-133. 2020.
11

---

Taher H Haveliwala, Aristides Gionis, Dan Klein, and Piotr Indyk. Evaluating strategies for similarity search on the web. In Proceedings of the 1 11th international conference on World Wide Web, pages 432-442, 2002.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-3255 2016.
Jiri Hron, Karl Krauth, Michael Jordan, and Niki Kilhertus. On component interactions in two-stage recommender systems. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 2744- 2757. Curran Associates, Inc., 2021.
Stratis loannidis and Edmund Yeh. Adaptive caching networks with optimality guarantees. ACM SIGMETRICS Performance Evaluation Review, 44(1):113-124 2016.
Shinji Ito and Ryohei Fujimaki. Large-scale price optimization via network flow. NeurlPS, 2016.
Sham M. Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, New York, NY, USA, 2007. Association for Computing Machinery.
Mohammad Karimi, Mario Lucic, Hamed Hassani, and Andreas Krause. Stochastic submodular maximization: The case of coverage functions. Advances Neural Information Processing Systems, 30, 2017.
Danish Kashaev and Richard Santiago. A simple optimal contention resolution scheme for uniform matroids. Theoretical Computer Science, 940:81-96, 2023.
David Kempe. Jon Kleinberg, and Êva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3(71-104):3, 2014.
Theodoros Lappas, Kun Liu, and Evimaria Terzi Finding team of experts in social networks. In KDD, 2009.
Yanzhi Li, Zhicheng Liu, Chuchu Xu, Ping Li, Xiaoyan Zhang, and Hong Chang. Two-stage submodular maximization under curvature. Journal of Combinatorial Optimization, 45(2):77, 2023.
Yao Li, Minhao Cheng, Kevin Fujii, Fushing Hsich, and Cho-Jui Hsich. Learning from group comparisons: exploiting higher order interactions. NewrIPS, 2018
Yuanyuan Li, Tareq Si Salem, Giovanni Neglia, and Stratis loannidis. Online caching networks with adversarial guarantees. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1-3), 2021.
Hui-Ching Lin and Jeff A. Bilmes. Learning mixtures of submodular shells with application to document summarization. In Conference on Uncertainty in Artificial Intelligence, 2012.
Weiwen Liu, Yunjia Xi, Jiarui Qin, Fei Sun, Bo Chen, Weinan Zhang, Rui Zhang, and Ruiming Tang. Neural re-ranking in multi-stage recommender systems: review. In Lud De Raedt, editor, Proceedings of the Thirty-Firss International Joint Conference on Artificial Intelligence, IJCAI-22, pages 15220520. International Joint Conferences on Artificial Intelligence Organization, 7 2022a. doi: 10.24963/ijcai.20222 2022//771 Survey Track.
Zhicheng Liu, Jing Jin, Donglei Du, and Xiaoyan Zhang. Two-stage submodular maximization under knapsack and matroid constraints. In International Conference on Theory and Applications of Models of Computation, pages 140-154. Springer, 2022b.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150, 2011.
12

---

Tatsuya Matsuoka, Shinji Ito, and Naoto Ohsaka. Tracking regret bounds for online submodular optimization. International Conference on Artificial Intelligence and Statistics, pages 3421-3429. PMLR, 2021.
Anay Mehrotra and Nisheeth K Vishnoi. Maximizing submodular functions for recommendation in the presence of biases. In Proceedings of the ACM Web Conference 2023, pages 3625-3636, 2023.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submod- ular maximization: Personalized data summarization. In International Conference on Machine Learning, pages 3558-367, PMLR, 2016.
Marko Mitrovic, Ehsan Kazemi, Morteza 7adimoghaddam, and Amin Karbasi. Data summarization at scale: A two-stage submodular approach. In International Conference on Machine Learning. pages 3596-3605. PMLR, 2018.
Houssam Nassif, Kemal Oral Cansizlar, Mitchell Goodman, and SVN Vishwanathan. Diversifying music recommendations. arXiv preprint
2018.
Yurii Nesterov and Arkadi Nemirovskii. Interior-point polynomial algorithums in convex program- ming. SIAM, 1994.
Rad Niazadeh, Negin Golrezaei, Joshua Wang, Fransisca Susan, and Ashwinkumar Badanidiyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 737-738, 2021.
Sofia Maria Nikolakaki, Alina Ene, and Evimaria Terzi. efficient framework for balancing submodularity and cost. In Feida Zhu, Beng Chin Ooi, and Chunyan Miao, editors, KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 1256-1266. ACM, 2021.
Frederick Qiu and Sahil Singla. Submodular dominance and applications. Appreximation, Random- ization, and Combinatorial Optimization. Algorithms and Techniques, 2022.
Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
Tareq Si Salem, Giovanni Neglia, and Damiano Carra. Ascent similarity eaching with approximate indexes. IEEE/ACM Transactions on Networking, 31(3):1173-1188) 2022.
Tareq Si Salem, Gözde Özean, lasonas Nikolaou, Evimaria Terzi, and Stratis Ioannidis. Online submodular maximization via online convex optimization, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15038-15044 2024.
Serban Stan, Morteza Zadimoghaddam, Andreas Krause, and Amin Karbasi. Probabilistic submodular maximization in sub-linear time. In International Conference on Machine Learning, pages 3241- 3250. PMLR, 2017.
Peter Stobbe and Andreas Krause. Efficient minimization of decomposable submodular functions. Advances in Neural Information Processing Systems, 23, 2010.
Matthew Streeter, Daniel Golovin, and Andreas Krause. Online learning of assignments. Advances in neural information processing systems, 22, 2009.
Youze Tang, Xiaokui Xiao, and Yanchen Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 75-86, 2014.
Sebastian Tschiatschek, Adish Singla, and Andreas Krause. Selecting sequences of items via submodular maximization. Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
13

---

Karan Vombatkere and Evimaria Terzi. Balancing task coverage and expert workload in team forma- tion. In Shashi Shekhar. Zhi-Hua Zhou, Yao-Y Yi Chiang. and Gregor Stiglic, editors, Proceedings of the 2023 SIAM International Conference Data Mining, SDM 2023, Minneapolis-SL. Paul Twin Cities, MN, USA, April 27-29, 2023, pages 640-648. SIAM, 2023.
Le Yan, Zhen Qin, Honglei Zhuang, Xuanhui Wang, Michael Bendersky. and Mare Najork. Revisiting two-tower models for unbiased learning to rank. In Proceedings of the 45th international ACM SIGIR conference on research and development in information retrieval, pages 2410-2414 2022.
Ji Yang, Xinyang Yi, Derek Zhiyuan Cheng, Lichan Hong, Yang Li, Simon Xiaoming Wang, Taibai Xu, and Ed H Chi. Mixed negative sampling for learning two-tower neural networks in recommendations. In Companion proceedings of the web conference 2020, pages 441-447, 2020.
Ruiqi Yang, Shuyang Gu, Chuangen Gao, Weili Wu, Hua Wang, and Dachuan Xu. A constrained two-stage submodular maximization, Theoretical Computer Science, 853:57-64, 2021.
Zhilin Yang, Peng Qi, Saizheng Zhang. Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answer- ing. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2369-2380, Brussels, Belgium, November 2018. Association for Computational Linguistics. doi: 10.18653/v1/DI8-11 1259.
Yisong Yue and Carlos Guestrin. Linear submodular bandits and their application diversified retrieval. Advances in Neural Information Processing Systems, 24, 2011. 1.
Wayne W Zachary. An information flow model for conflict and fission in small groups. Journal of anthropological research, 33(4):452-473 1977.
Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maxi- mization: From full-information to bandit feedback. Advances in Neural Information Processing Systems, 32, 2019.
Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodu- lar maximization: Boosting via non-oblivious function. In International Conference Machine Learning, pages 261 161114 PMLR, 2022.
Kai Zheng, Haijun Zhao, Rui Huang, Beichuan Zhang, Na Mou, Yanan Niu, Yang Song, Hongning Wang, and Kun Gai. Full stage learning rank: unified framework for multi-stage systems. In Proceedings of the ACM Web Conference 2024, pages
2024.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928 9366 2003.
14

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstract of our paper we claim that we develop an online algorithm for the 02SSM problem, with WTP second-stage objectives, that achieves sublinear (1 - 1/
regret under matroid constraints and (1 [1 - /k!))regret under cardinality constraints. This is exactly the main result of the paper that is stated in Theorem 5. We also state that this result implies an offline approximation algorithm that improves upon the state-of- state-of-the-ass art for the case of cardinality constraints. We give proof of this fact and analyze further in Appendix
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of our paper are discussed in a dedicated paragraph at the end of the main body (Section 7). Specifically, our algorithm is designed for Weighted Threshold Potential (WTP) functions, subclass of monotone submodular functions. This limitation is stated in the Abstract, Introduction, and Related Work, and is formalized in Theorem 5.1 and all of the relevant lemmas that build up to the main result.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results in the paper are formally stated with precise assumptions and rigorously proved. particular, Theorem 5.1 provides the main regret bound and is supported by complete and constructive proof (see Sections 5.2 and Appendices C, D,E). WTP function parameters and builds up through carefully stated lemmas (e.g.. Lemmas 5.2, 5.3, 5.4), each which includes detailed and correct proofs. Each formal lemma, theorem, etc. also starts with formal statement of its assumptions.
The analysis relies on well-defined assumptions such as boundedness
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We give detailed description of all datasets, construction of problem instances, algorithms and their implementations, hyperparameters, and metrics. See Experiments Section 6 and Appendix F. Also, code base is anonymized and available online (see answer to Q.5).
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide open access to our code in an anonymous repository The reposi- tory includes detailed README with setup instructions, descriptions of each component, and commands for reproducing all experiments and baselines reported in the paper. All datasets used are either publicly available produced by the given code.
6. Experimental setting/details
15

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
We provide comprehensive description of the experimental setup in Ap- pendix including dataset details, objective construction, and evaluation protocols. Table reports the learning rates selected for each algorithm/datase pair, and we explain the hyperparameter tuning process used choose them.
Justification:
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For the metric of interest C. (cumulative average reward), we report its average value over runs (sampled over input and pipage rounding randomness), along with the standard deviation (shown via the shaded area). See Figures 1, 2 and 3 and section "Metrics" in Appendix F.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We detail the computational setup in the "Setup" paragraph of Appendix F, including hardware specifications (Apple M2 CPU, 16GB RAM) and software environment. Each experiment runs efficiently a personal laptop: every problem instance could be computed until the time horizon T in less than one minute. No large-scale compute or specialized hardware required. Finally, please note that all our algorithms polynomial time; we report complexity guarantees in Section 5.2.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpps//nneurps:: cc/ppblicc/Ehhcccctteeeeee ines?
Answer: [Yes]
Justification: Our research does not involve human subjects, sensitive data, applications with foresceable negative societal or environmental impacts. We adhere to ethical research practices outlined in the NeurlPS Code of Ethics. All datasets used are publicly available. We have considered the broader impacts of our work and believe it aligns with the ethical standards expected by the NeurlPS community.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We briefly discuss the broader relevance our work in the context of recom- mender systems, influence maximization, and data summarization. highlighting potential benefits such as efficiency and scalability (see Appendix A). As our results are theoretical and algorithmic in nature and primarily applicable to submodular optimization problems, we do not foresee direct negative societal impacts. However, like any optimization tool, applications should be assessed case- case-by-cas byce-byycceeee to ensure ethical use.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
16

---

Justification: Our paper does not release any pretrained models, generative tools, or scraped datasets that pose risk of misuse. The work is theoretical and algorithmic in nature, focused optimization methods under well-defined mathematical assumptions.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets used in experiments (Wikipedia, Images, MovieRec, Influence, etc.) are drawn from prior published work or standard benchmarks (e.g., VOC2012, Movie- Lens, Zachary's Karate Club). We cite the original papers for each dataset in Section 6 and Appendix F. Where applicable, datasets were used in accordance with their stated licenses public terms of use. We do not use any proprictary, scraped, or restricted-access data.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce any datasets, models, other assets. All experiments are conducted using existing, publicly available datasets from prior work, which are cited accordingly. Our code is documented and documentation is included in README file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowdsourcing research with human subjects.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve any research with human subjects and therefore does not require IRB or equivalent ethical review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
Large language models (LLMs) were not used part of the core methodology, analysis, or results in this research. Any minor assistance from language models was limited editing formatting and did not affect the scientific content.
17

---

A Applications
In this section, we provide several applications of online two-stage submodular maximization (02SSM), focusing particularly on cases where the second-stage objectives can be modeled via weighted-thrreholld potential (WTP) functions. Before we present these applications, we first discuss a few abstract objectives that can be cast in WTP form. We then use these objectives to define specific 02SSM applications/instnees..
A.1 Examples of WTP functions
Si Salem et al. [2024] give several instances of submodular maximization whose objective can be expressed as WTP functions. These include influence maximization [Kempe et al., 2003]. facility location [Krause and Golovin, 2014, Frieze, 1974], cache networks [loannidis and Yeh, 2016, Li al., 2021], similarity caching [Si Salem al., 2022], demand forecasting [Ito and Fujimaki, 2016], and team formation [Li et al., 2018]. The objectives of most of these examples are fact specific cases of weighted coverage, facility location, or quadratic submodular functions. On account of this, we review these three types of objectives in this section, and show that they indeed belong to the WTP class. We refer the interested reader to Si Salem al. [2024], Karimi et al. [2017], and Stobbe and Krause [2010] for further discussion on WTP functions and applications.
In our description below, maintain our convention of describing set functions as functions of characteristic (i.e., binary) vectors, i.c., of the form f {0, 1)" - I2..
Weighted Coverage F Functions [Karimi et al., 2017]. For V = [n], let hrc be a collection of subsets of V, and or E lzzo be a weight associated to each subset Sy. A weighted set coverage function f : {0, 13 + R2 receives as input y E {0, 13" representing subset of V, and receives value ep if S₃ is "covered" by an element in y; formally,
f(v) = Σ ce min {1
Σ yh
Σ c mimin min {1, we), LEC
(10)
EEC
sES,
where We E {0, 1 is the characteristic vector of Sg. This is clearly a WTP function of the form (5).
Facility Location [Krause and Golovin, 2014, Frieze, 1974, Karimi et al., 2017]. In the classic
facility location problem, we are given a complete weighted bipartite graph G(V U UV', E), where V= [m]. E = V x V", with non-negative weights Wa.r 2 0, v E V.v E V". We are also given distibution (pw' wev', where par 2 0, for all r E V', and Evev Par = 1. The decision maker selects a subset C and each e' E V responds by selecting the Wepr The goal is to maximize the average weight of these selected edges, i.e. to maximize
with the highest weight
f(8')
Σ P max Wo,e" V'EV
(11)
WES
given some matroid constraints on S. Set V can be considered a set of facilities and V' set of customers or tasks to be served, while Wv,y' is the utility accrued if facility serves tasks v'. The goal is then to maximize the utility in expectation over a random task sampled from distribution E [0, 1] V')), assuming the task is mapped to the best facility in S. Karimi et al. [2017] show that this objective is weighted coverage function, of the form (10), because, for y E (0, 1) the characteristic vector of S, we have
Wo YES
(Wa,,e' W min {I.E Mhy } + Wxy min 1, Ei Ur,
(12)
where π. V + a permutation such that: Wx,, 2 Waype'' 2 2... ..... Wan. Hence, Eq. (11) can be written in WTP form in the same way as Eq. (10).
Quadratic Submodular Functions [Li et al., 2018, Ito and Fujimaki, 2016]. Consider quadratic monotone submodular functions f {0, 13" + R20 of the form
f(z) h + x H
(13)
2
18

---

where, w.l.ogg, H is symmetric and has zeros in the diagonal. Note that f is monotone and submodular if and only if: (a) H I O. and (b) h + H 2 0. for all the feasible domain. We can write the quadratic term as
n
n
x: H
Has
1=1 ==1
Σ
(1) + I3
minn1, + + Hij
j=l
n-1 n
2x H1 +2 Σ
Σ
(-Hr,) min 24 2z}.
j=i+1
where we used the equality - (1- - y) = x = minf1, wb Vz,y E 10,1}. Therefore, we can write f as
カ-1 n
f(x) min foc, (h+ H1) x) Σ
Σ
(-Hr,) 2zh.
j=i+1
which is a WTP function.
A.2 02SSH Instances and Applications.
Recommender Systems. The real-time delivery requirements of modern recommender systems necessitate that they operate in multiple stages [Liu et al., 2022a, Hron et al., 2021, Zheng et al., 2024, Covington et al., 2016]. In particular, upon a user request, a catalog of items to be recommended passes through multiple stages, each thinning the set of recommendation candidates passed on to the next stage. The catalog of items passed the very first stage is typically restricted heuristically, e.g., through item recency, relation to the recommendation surface, etc. It is exactly the catalog design that passes through the very first stage of the recommendation pipeline that Stan al. [2017] proposed to optimize via two-stage submodular maximization, presuming knowledge of the distribution of user preferences. As discussed in the introduction, the online version of the problem (D2SSM) enables the adaptation of the catalog in an online fashion, without the prior requirement of the distribution of user demand.
The motivation for considering submodular (i.c., diminishing-return. functions to model user preferences w.r.t. recommendations is natural, and several works model recommender system utilities via submodular functions [Tschiatschek et al., 2017, Nassif et al., 2018, El-Arini et al., 2009, Yue and Guestrin, 2011, 1, Mehrotra and Vishnoi, 2023, Evnine et al., 2024]. Several such models involve WTP functions. For example, El-Arim et al. [2009], Tschiatschek et al. [2017] and Yue and Guestrin [2011] model user utilities via weighted coverage functions of the form (10): items recommended "cover" topics or categories &. с C, and weights cg capture the a user to like that category. In similarity-basee recommendations [Haveliwala et al., 2002, Agrawal et al., 1993, Gionis et al., 1999), which often model early-stage rankers [Yan et al., 2022, Yang et al., 2020], queries and items are jointly embedded in the same latent space, and the reward of recommendated set is the similarity of nearest/most similar item to the user query. This can naturally be modeled via facility location objective (1 I), where o' correspond user/queries, wo is the similarity between their embeddings, and p', corresponds to distribution or weights over queries.
Team Formation. In high-reliability settings, such large-scale software companies or municipal emergency services, organizations must routinely form standby teams capable of reacting to unpre- dictable, high-stakes events. For instance, a software company may have thousands of engineers, and each day must select small subset of individuals to be "on-call" in case of operational incidents (e.g., outages, high-severity tickets, etc.). Similarly, emergency response agencies must designate a pool of responders (e.g., firefighters, paramedics, utility crews) to cover incoming incidents throughout the day. Each event or incident, when occurs, brings specific requirements: geographic proximity or timezone alignment, technical expertise, domain training, or familiarity with particular systems, neighborhoods, or equipment. both examples, the organization must commit in advance to restricted set of available personnel (i.c., roster) æ, Xe, from which second- stage selection is
19

---

made once an incident materializes, i... E (xz). Since the distribution over incident types is unknown and evolves over time, this naturally constitutes an instance of the 02SSM problem.
Team performance requirements are often modeled in the literature using a weighted coverage function [Nikolakaki et al., 2021, Vombatkere and Terzi, 2023] (see Eq. (10)). In these settings, the utility of a selected team is determined by how well it satisfies task-specific needs, captured by an appropriate bipartite graph. Several works [Lappas et al., 2009, Boon and Sierksma, 2003, Li et al., 2018] model pairwise synergies among team members via quadratic submodular functions (Eq. (13)), where the matrix H encodes compatibility or redundancy among team members. Both cases fall within the WTP class.
Influence Maximization. In social networks and marketing platforms, influence maximization aims to identify a small set of individuals whose activation leads to the largest spread of information, behaviors, or product adoption. A common strategy is to "seed" selected users, e.g. by offering free access, promotional incentives, or early content, so that influence propagates through their social ties. However, running influence maximization over large-scale network is often computationally prohibitive, particularly when campaigns or objectives evolve over time. A natural approach is to first select restricted set of influential or cooperative users and later select campaign-specie activate. Formally, this matches the 02SSM structure: at each round t, a platform selects a restricted candidate pool æt X2, from which seed set yı (x:( of k users is selected, after observing the influence objective ft (e.g., a new product or message). Since these objectives arrive sequentially and may reflect different target audiences goals, the platform must adaptively update I; based on the influence functions materialized in past rounds, in order to improve the quality of future seed selections.
subset to
Classical models of influence propagation, such as the Independent Cascade and Linear Threshold models [Kempe et al., 2003], yicld monotone submodular objectives that measure the expected number of activated nodes. In practice, many works study scalable approximations of these models using weighted coverage functions [Borgs al., 2014, Tang et al., 2014] (see Eq. (10)), where the coverage corresponds to reaching key individuals, groups, or communities within the network. These objectives fall within the WTP class.
B
Contention Resolution Schemes
B.1
Background
The framework of Contention Resolution Schemes was formalized by Chekuri al. [2011] 1] and has since found many applications. Given some feasibility constraints (usually matroid constraints) over some groundset V, a Contention Resolution Scheme (CRS) an algorithm that accepts a random set R C V, that is not necessarily feasible, and trims it down feasible set π (R) S R. The goal of this "rounding" " is to ensure that each element is kept with a high enough probability. Most prior work on CRSs has predominantly focused on product distributions, i.e. random sets R that include each element e E V, independently. with some probability Ze.
In our setting, we aim to use ORS-based roundings to round second-stage solutions (see Appendix C). However, the inclusion of an element in the random set R depends on whether it was included the rounded groundset by the randomized rounding applied to the first-stage. Since this rounding process (namely Randomized Pipage Rounding) introduces dependencies between elements, the inclusion of elements in R is no longer independent, and standard CRSs for product distributions cannot be directly applied.
Recently, Dughmi [2020, 2022] initiated the study of CRSs under non-product distributions. We build on this line of work and prove that the distribution over sets R induced by our two-stage rounding process satisfies property known as submodular dominance (Definition B.3), which enables the use of CRSs even in the absence of independence (Corollary B.8).
Notation. For the rest of the section, we fix V = [M] = (1, (1,.... n to be a ground set of n elements. Let M be matroid over V and w E Rn be a non-negative vector. We define the weighted rank function rank : {0, 1}" -> T. which maps every subset U C V to the weight of the maximum- weight independent set of M that is subset of U. Formally, under our notational convention equating
20

---

sets with their characteristic vectors, rank (x) (=== = max W y.
yEVM
When the matroid .M is clear from the context, we will omit it from the subscript and use the notation rank We use A ({0, 1)") to denote all possible probability distributions over {0, 1)". For any fractional vector E [0, 1 we define the distribution Ind(x) A (f0, 1)")) which produces a random set 2 ~ Ind(x) by including every E [n]. independently, with probability 2;. For distribution D E A (f0, })"
puD [0, 1]" denote it's expected value, i.e. jeD EE<D (a)]
We now give formal definition of Contention Resolution Scheme.
Definition B.1 (Contention Resolution Scheme (CRS)), Mt (V,I) be matroid over V. A contention resolution scheme (CRS) Φ is a randomized function from {0, 1 th to I, with the property that for all {0, 1)
<(x:) S and ((x=) I.
Of course, the above definition by itself trivially satisfied. For instance, one could define @ to always return the empty set, which is always feasible but clearly not useful. Intuitively, in CRS-based roundings, we want to retain each element the input set with sufficiently high probability. This intuition is captured by the notion of seleciability, which quantifies the minimum probability with which each element is preserved (conditioned on it being present in the input set).
Definition B.2 (7-selectable CRS). Let M ([n], I) be matroid over [n]] and D A (40, 1)m) be a distribution over subsets of [n]. A contention resolution scheme (CRS) ø is called 7-selectable for D, if for any D and every [n] it holds that Præ>D.oló(zr) 1|2; 1]
To extend the applicability of CRSs beyond product distributions, we need a structural property of distributions that enables approximation guarantees even in the presence of dependencies. One such property is submodular dominance [Dughmi, 2020, Qiu and Singla, 2022], which intuitively ensures that a distribution is "at least good" as its independent counterpart when evaluated against any submodular function. We give the formal definition below.
Definition B.3 (Submodular dominance). distribution D E (f0. 13m) has the property of submod- ular dominance if for every submodular function f it holds that [f > Eg-ind(e [=)).
We now proceed by stating the properties of some state-of-the- of-tte-art contention resolution schemes for product distributions, i.e. (n:) ) for some x E P(M).. We also state a necessary and sufficient condition for the existence of y-selectable CRS for distribution D.
Lemma B.4 (Chekuri et al. [2011]] I]). For any matroid M and any x E P(M), there exists contention resolution scheme o that (1 10--1/1 1/e)-selectable (1)//(/)--seletablll for the distribution Ind(x)).
The above result holds for any matroid and is known to be asymptotically optimal for general matroids under product distributions [Chekuri al., 2011]. For specific matroids, however, stronger guarantees are possible. In particular, the following lemma gives a tighter selectability bound for uniform matroids of rank k.
Lemma B.5 (Kashaev and Santiago [2023]), Let M' be the uniform matroid of rank k. There exists a contention resolution scheme o' that (1 k "//Kk)/-selecctbbl for the matroid M' and the distribution Ind( for any P(M').
Both the aforementioned results (Lemmas B.4 and B.5) admit constructive proofs, i.c. the respective contention resolution schemes are implementable in polynomial time and they are described in Chekuri al. [2011] and Dughmi [2020] respectively. However, our algorithm does not rely on these constructions, they are only needed in Appendix C for analysis purposes.
We now step away from product distributions and state a recent result of Dughmi [2020] that gives necessary and sufficient condition for the existence of a 7-selectable CRS for a distribution D.
Lemma B.6 (Dughmi [2020]). Let M matroid over [n] and D E ((0, 13") be a distribution over subsets of [n]. For any 7 [0, 1), the following are equivalent.
21

---

a) There exists contention resolution scheme 6 that is y-selectable for D.
b) For every weight vector w E IR4, it holds that
E w>D
[rank (x)) 2 7
E
(E(M)
Using the previous lemma, one can prove that the property of submodular dominance (Definition B.3) also sufficient for the existence of y-selectable CRS. The latter has been stated informally by Dughmi [2020]. We state it formally the next lemma and give a small proof for completeness.
Lemma B.7 (Dughmi [2020]). Let M be a matroid over [n] and D (2 be distribution over subsets of [n]. Suppose that DD has the property of submodular dominance (Def. (B.3)). Then, for any Y [0. 1], if there exists a --sselectable CRS for Ind(pr) then there also exists a "y-selcctbble CRS for D.
Proof of Lemma B.7. Fix any weight vector w RT. Notice that
E [
Σ Wilt
Σ Wi
[
Σ
E
Σ KE mz]
Wiiii
(nd
a~D
(E(m)
iE[n]
iE[n]
because Ex [xr]
End ( [a:]] = (ND)s. for all E [nx].
If the distribution Ind( has a y-selectable CRS, then by Lemma B.6(b), we get that
Trank (x)]
E
Σ Wa
E
x~D
Since the weighted rank function is submodular for any non non-negative vector w [Schrijver, 2003], we can use the submodular dominance property of 'D to get
E
frank (x)) 2 E
frank (x)]
2 e~D
Combining the latter incqualities gives that
E
Taank (x)) 2 7
IE
Σ W:T;
iE(n]
which by Lemma B.6 implies that there exists a -eeeectable CRS for D.
Finally, by combining Lemmas B.7, B.4 and B.5 get the following corollary, which will use in our analysis (Appendix C).
Corollary B.8. Let M ([n), I) be a matroid and D E A(2(ml) be a distribution over subsets of [n]] for which the following hold: (1) μD E P(M), for every submodular function EE (f(x) >
End(ind( (f (==). Then, there exists e---electabll CRS for D, where CM = e / if M is uniform matroid of rank ts and CM = -1 1/e otherwise.
B.2 CRS-Based Roundings of WTP Functions
We state useful lemmas for CRS- rounding processes that used convert fractional solutions into integral ones; we use this to provide a bound on the expectation of a WTP function w.r.t. its concave relaxation.
First, we state a lemma by Chekuri et al. [2011], which proves that applying a 7-selectable CRS to random set æ D produces a feasible solution whose expected value, under any monotone submodular function f. is at least a y fraction of the value ff under the independent distribution with the same marginals as D.
22

---

Lemma B.9 (Chekuri et al. [2011]). Let f be a monotone and non-negative submodular function over 2(m) and @ be y-seecttbble CRS for distribution D. Then,
E ar
[f(()))) 27
E sewInd(pp)
[(()]]
The following result, due to Si Salem et al. [2024], shows that under mild negative correlation condition, the expected value of WTP function under a distribution is well-approximated by its concave relaxation (as defined in Eq. (6)), evaluated at its expected vector pp-
Lemma B.10 (Si Salem et al. [2024]). Let f be WTP function and f be concave relaxation as ) defined in Eq. (6). Let also D E (2(11) be distribution over subsets of [rl], such that for any subset S S [n]. EEWD Ies T. < Ilies ExnD(E Then,
E [ 2 (1 (1-2) F(wD).
anD a
Finally, we combine Lemma B.9 and Lemma B.10 to derive the following approximation guarantee for the expected value of a WTP function after applying --selcctable CRS.
Lemma B.11. Let f be a WTP function and f be its concave relaxation as defined in Eq. (6). Let also be a r-selectable CRS for a distribution E A22 Then,
[[((())) 27 7 (1 (1-2) F(UD). æ~Di
E
Proof of Lemma B.11. Notice that the distribution Ind(pt) satisfies the properties of Lemma B.10, since for every subset 5 [n] we have that (gdInd(e)))) [[lies 2i =Iles End [2:]. There- fore, from Lemma B.10 we get
[f(x)] 2 (1- F(HD).
Ind(pp)
The proof is completed by combining the latter inequality with Lemma B.9:
[(xx)] .. (1-!) (uD)
E wnDD
[[((())))
27
E Ind(n(
C Proof of Lemma 5.4
In this section, we prove Lemma 5.4, which shows that the expected reward of the rounded ground set, obtained by applying Randomized Pipage Rounding fractional ground set, approximately preserves the value of the initial fractional ground set. Specifically, we aim to show that for any WTP function f and any fractional ground set ã E Xe, the expected reward of the rounded ground set =(ā) satisfies
Ee(F(E(F))) 2 cM - 1/e) F(().
where F(x) maxxge)'m()) f(y) is the reward of the rounded ground set (Eq. (7)) and F(Ø) (a f()) is the concave relaxation of the reward function (Eq. (8)). The constant CM depends on the structure of the second-star sttge matroid.
As reminder, for ground set Xr, the set of feasible second stage solutions, is the restriction of the matroid M to the set æ, i.e. VM = {y E (0, 13" y E M, y S æ:). In the same manner, for fractional ground set ~ه E Xr, the corresponding fractional relaxation of the second-stage feasible solutions is VM ( (ū [o. 1]" P(M), .)
High-level description. On high-level, we need show that the value attained by maximizing a WTP function over the fractional ground set remains approximately the same when we transition to the rounded ground set. To establish this, we design two-stage randomized rounding procedure, used purely for analysis, which transforms any fractional second-stage solution into feasible integral
23

---

one that has, in expectation, approximately the same value. This construction is coupled with the Randomized Pipage Rounding used by RAOCO to select the integral ground set. The rounding is performed in two steps: First, fractional second-stage solution is mapped to an intermediate integral vector that lies within the selected ground set but may violate the matroid constraints. Then, we apply contention resolution scheme (CRS) to trim the intermediate vector to a feasible solution (for more details on CRSs see Appendix B). A key challenge is that standard CRSs typically need each element of the input vector to have been included in it independently of other elements. This assumption does not hold in our case since the intermediate vector depends on the outcome of the Randomized Pipage Rounding which introduces dependencies across elements. However, we show that the intermediate vector exhibits the property of submodular dominance (Def. (B.3)) which allows us to use state-of- of the art CRS guarantees (Corollary B.8). We now formalize this construction and use to prove Lemma 5.4.
Rounding Description. Fix any E Xe and E Xg. Let also ý E (T) be a second stage solution that is consistent with w. To map ý E (²))) to a solution E (2)) we first round ý to an intermediate solution y. through randomized rounding Q. The intermediate solution ý is always feasible for the new groundset æ, i.e. ÿ S æ, but it might violate the matroid constraints. For this reason, we pass it through contention resolution scheme @ to trim it down to solution (()) < ÿ < that also respects the matroid constraints. On high level, the rounding procedure we described can seen in the following diagram.
(m)
y VEM()
uses
Formally, the rounding Q accepts x. x and ÿ E (x) and produces 9 = @, For i [m]. let ag be
0:
R 0,
otherwise.
The rounding Q is defined follows: first, it samples independent Bernoulli random variables, Ci...., Cns with c ~ Ber(a,). Then, sets the i-th coordinate of the resulting vector ý to be
{o: ú. 10. 0
if a. = and 6; = 1,
otherwise.
In other words, 9 x A By construction, ý only uses elements that are in the groundset i.e. 2 S. æ. However, does not necessarily satisfy the matroid constraints. For this reason, we pass through contention resolution scheme ó for the matroid M,, obtain y o(ÿ). We do not instantiate the scheme ò yet, but we remark that using any contention resolution scheme for the matroid M, will result in set y that is feasible second-stage solution for the rounded ground set, ie. E (mr).. We state this formally in the following lemma.
Lemma C.1. Fix any E E &r. any x E Xe and any ÿ E (T). Let = Q ā. x) and y = o()). where é is contention resolution scheme for the matroid M. Then, y (m))).
Proof of Lemma C.I. Recall that (x) contains all the independent sets of M that are also subsets of æ. By definition of the rounding Q. if æ; = 0 for some coordinate i E [n], then ÿ; 0. This means that ý is subset of æ:, i.e. ý S æ. By the definition of contention resolution schemes (Def. B. we know that y Φ()) < ÿ < and y Φ()) I. where I is the family of independent sets of the matroid M. Therefore, y E (2)(
Knowing that the resulting vector is always feasible allows us to link the expected value of the transformed solution with the reward of the rounded groundset a.
24

---

Lemma C.2. Fix any WTP function f and its correspoding reward function F, as defined in Eq. (7).
Then, for any it E Xe and any y (M) holds that
[(()) -
E
[f(x)]
(~))
x~ (Q(..)))
Proof. Fix a vector æo E X3 and let أ - Q ã. vo) and y - (()). The expected value of produced vector, y. is
E [f(y)]-
By Lemma C.I know that (m))) This means that there must exist y' E (3n( whose value is at least the expected value of the produced vector, i.e.
f(y')
[f(y]]
By the definition of the reward function F (Eq. (7)), have that
F(xo) 2 f(y') 2 ((Q [f()]]-
Notice that the above inequality holds for any 2n E Xr. We multiply this inequality by the probability that 2y is the result of Randomized Pipage Rounding on E and then sum up the corresponding inequalities for all xp E Ne:
Σ F(xu) Pr (x= zu) T
E w- -- DoE
Σ
[f(v)]
Pr -~5(())
[x:
xu)
w>))(a))
[(()] 2~
[f(y)]
Having the above lemma, will now turn focus analyzing the expected value of f(y) when a has been produced by Randomized Pipage Rounding. We start by proving some properties for y and then "instantiate" the contention resolution scheme 6
In order to make the notation simpler, we will use Q क, E(ã)) to denote the distribution Q ã. x) where x ( We begin by showing that the expected value of ý is the initial fractional solution y.
Lemma C.3. For any x E Xe and any ÿ E (m((T) it holds that
E i --QTEE
[ ÿ.
Proof of Lemma C.3, Fix an index E [n]. ã; = then y: = O. This because ÿ E (m) which
implies that ÿ C. In this case, we have that y: 0 y: In the case where क; z 0, the following true
Prim 1] Pr
Pr(c: 1] Pr(æ, 1]
Lem. 1.1 V
yi:
2;
where in the second to last inequality we used Lemma for the marginals of the Randomized Pipage rounding.
In all cases have that Ez,Q [0.) Pr à 1] Dc which concludes the proof.
Li
We continue by showing that the distribution @ 26, E i exhibits the propery of submodular dominance (Def. (B.3)).
Lemma C.4. For any ă E Xe and any ÿ (²) the distribution Q 2, E(x)) has the property of submodular dominance (Def. B.3), i.e. for every submodular function f it holds that
[f())] 2 (ndInd [f(]]-
25

---

Proof of Lemma C.4. Let p E [0, 1 be vector whose i-th coordinate is defined as
V +
P
0,
otherwise
Fix any submodular function f. We define the function g 2(x) + IR as
g 22
E Z~And(p)
[f( z)]
Intuitively, 9 maps every set z to its expected value after removing each one of its elements indepen- dently with probability p:. Notice that this is exactly what the rounding Q does to every rounded ground set æ. In other words, ÿ is simply the result setting the i-th coordinate of to zero, independently, with probability pt. From this observation we get that
E [(()]]
E
E Indin(pp)
[ 2)]
E m~
[g(x)]]
2~)(
In similar manner, we have that
[f(D]]
E Ind
E Ind(p)
[f A 2)1
E Ind
[g(x)]]
T IrwInd
We conclude the proof by showing that the function g is submodular and then applying the submodular dominance property the Randomized Pipage Rounding (Lemma 1.2).
To prove the submodularity of fix subset E {0. 1)" and two other subsets x, 10. By the submodularity property of f applied to the sets (x z) and (y 2), we have that
f(x ^ 2) + f(y A 2) 2 f(( A x) A (y A 2)) f(( A 2) V (g
=[(( A 4) A 2) f((x v y) A 2).
We write the above inequality for any 2g {0, 13" and multiply both sides with Prz=ndlpp)? zo]. By summing up all the aforementioned inequalities we get
Σ
Pr [z = 20] z~Ind(p)
=0E10,1)
Σ (f(())g) A 2) f((xV 3) 2))
Pr 1 zol z>Ind(p)
101/0,11
E (nd())
[s A)]
+ E
[f A z)]
I>Ind(p)
E
[f Ag) A 2)]+
E z~Ind(p)
[(x A x)1
Ipd(p)
(()) , 2 y( ^ v) + g(x Vg)
which proves that y is submodular.
We conclude the proof by applying Lemma 1.2 g.
Lem 122
E
[f())
[g(z)]
E Ind
[g(x)]
E Ind
[f(t)
Using the above properties for ÿ. we will now show that there exists an "appropriate" CRS ø. which will use to finally prove Lemma 5.4.
Lemma C.5. For any I E Xe and any y E {M(T), there exists a cyy-selectable CRS for the distribution Q क. E()) and the matroid M, where em - - /k! if M is a uniform matroid with rank k and CM 1 1/e otherwise.
26

---

Proof of Lemma C.5. Let CM be the constant mentioned in the statement of the lemma. From Corollary B.8, we know that in order for a distribution have a -elecctbe CRS, suffices that it's expectation is in the matroid polytope and that is has the property of submodular dominance. Fix any pair of σ X₃ and (z) For each such pair, Q क, (()) defines distribution subsets of [n]] that depends on the randomness of Q and E. From Lemma C.3 we have that
= y E P(M).
Y~ (
which is in the matroid polytope since ÿ E Y (z). Furthermore, from Lemma C.4, we know that the distribution (ÿ, x) has the property of submodular dominance. As result, using Corollary B.8, we get that there exists a ---selectbble CRS for the distribution Q Φ, [())).
We are now ready prove Lemma 5.4.
Proof of Lemma 5.4. For any solution ÿ E (T) and any contention resolution scheme Φ, from Lemma C.2 know that
E F(()) (-
E
[(()]]]
[f((()))
-~
By selecting ø to be the se--eclctable contention resolution scheme guaranteed by Lemma C.5 and applying Lemma B.11, get the following
Lem, B.11
CM (1- f(Ø)
(~Q(y,, [f(o()))
E
where f is the concave relaxation of the WTP function f. as defined in Eq. (6).
Let y² E Segmaxyeemml f(y). By selecting ÿ y² in the above inequality get
CM (1- fly") cm -om (1-2)-E(3) F()).
E x~
[(())
where in the last equality we used that F())= f(y)" by the definition of the fractional reward function (Eq. (8)).
D Regret of OCO Policies in Fractional O2SSM
In this section, we prove Lemma 5.2 which states that any standard OCO policy (e.g., FTRL or OGA, see Appendix H for more details) has no-regret in the fractional relaxation of 02SSM.
Notation. We introduce some extra notation regarding matroids that we will use in our proofs in this section. For matroid M (V. I), the rank function of M, rank 2 + N, maps each set U C [n] to the size of the largest independent set contained in U. Also, the matroid polytope ((M) can equivalently be written as: P(M) { [0, 1]" Eies 3 rank(S), VS V).
First, we will show that the fractional reward function T' associated with a WTP function is concave and Lipschitz. These two properties are proven in the next two lemmas (Lemmas D.I and D.2).
Lemma D.1. Let f be any WTP function, f be its concave relaxation as defined in Eg. (6) and F be the concave relaxation of the reward function associated with f, defined in Eq. (8). Then, F is concave over the domain Xt.
Proof of Theorem D.I. Recall that F is defined Eq. (8) as
F())
max J(Ø), Vo E XT ())m(
27

---

Let T1. E &e be any two fractional restricted ground sets. We will show that for any À E [0, the following holds
F((A \)āa) 2 XP (T) + (m2)
We define the vectors ý E VM (11) and y/2 E VM (ج²) follows
y1 argmax fr(
and
y/2 argmax fz) (
(())
It holds that
xF +1- 1) Xf(mn) + (1- ()f((2))
S f(xūn + +11
( f(0)
F(Aā= (1 \)522)
where first inequality true by the concavity of f and get the second inequality we used the fact that Aÿ + (1 - A)ă2 E {Mm(Am + (1 - A)ā2), which we prove below.
The memberships ÿ1 (ā.) and Y E (x2) imply the following inequalities:
A S Am1,
(1 A) 2 S A)
Vi. rank V and
(1 (1- 12.1 S (1 A)rank(S), VS C V.
IES
iES
Adding up the above inequalities gives us that Aÿ + (1 A) E 5M + (1- -)))2), which concludes the proof.
O
Note that the proof of Lemma D.I does not actually require that f is WTP function; the lemma follows for any / that admits concave relaxation s.
The following lemma establishes the Lipschitz property of F:
Lemma D.2. Let f E FG,M be a WTP function, as defined in Eq. (5). Let also be its concave relaxation, as defined in Eq. (6) and be the corresponding first-stage relaxation associated with f. as defined in Eq. (8). Then, is GM2 -i-iscchitz.
Proof of Lemma D.2. Recall the definitions of f (Eq. (6)) and F (Eq. (8)):
f(0)
- JEC
c min (b,, ÿ wyh. E 10. and F()) max f(0) ã Xz. TE)(#)
Recall that the family FG.M consists of the WTP functions whose index set C has size at most G and whose parameters ej, by, Wiy are upper bounded by M.
Fix an क E X2 and let y E argmna arginax (Z) f(z). As we show in Appendix E, computing the reward F(x) can be cast into a linear program. We focus on a dimension i E [n] and employ sensitivity analysis to upper bound how much the objective value of this linear program can increase when we increase the i-th coordinate of E/r by e, i.e. E' I e Notice that ã; appears only as the right-ham hand side in the constraint y; S H.. Therefore, by increasing T; a Z; + e, the objective function can increase by at most:
Elcsllooa s eGM2
jEC
28

---

Furthermore, by decreasing a coordinate of ã, the objective value can only stay the same or decrease. Therefore, for two points 31, 32 E X with ( 1 we get that
F( - [ = F(ã2) F(21)
GM2
Σ
(a22 21i
iE|n]
GM2 Σ
Z1d
iE|n]
GM²
|
21 11
S GM2 Vn 1
20 2/
Lemma D.3. The diameter of the convex set Xe is at most 28.
Proof. For the diameter D of the set X₂ holds that
D max
|| T1l12
3 E
max
|| T1ll1
E
max
||ح2||| + | lla
# T
< 26,
where for the last inequality we used that || S e, Va E &c.
We are now ready prove Lemma 5.2, which we restate below for convenience.
Lemma 5.2. Let (ft)== S FG.M be sequence of WTP functions, let {Fi)T= be the corresponding reward functions as defined in Eq. (7) and {F:)īm1 be the corresponding concave relaxations of the reward functions as defined in Eq. (8). Suppose that { J1=1 the sequence of fractional restricted ground sets computed by the 0CO policy of Algorithm 1. Then,
T
T
max DE
F((x))
= I=1
= (IEMPVVVVT
Proof of Lemma 5.2. The fractional reward functions are concave (Lemma D.I) and Lipschitz (Lemma D.2) and the set of actions, X₂ has diameter at most 28 (Lemma D.3). Therefore, by the standard regret analysis (Theorem 3.1) we get that
(T)
Σ F(T.) = O ((VT).
max #EX:
The proof of the lemma is completed by noticing that
T
T
max
F(
max TEX
F((Z)
< max
f()3),
TE
ZEX
because F(ã)
(T),, Vž
E Xe and X Lz
E Supergradient Computation
In this section, we show how to efficiently compute the supergradient of F(Φ) for any क. See Algorithm for the pseudocode. In particular, we are going to prove Lemma 5.3, which we restate below for convenience.
29

---

Lemma 5.3. Let f E FG.M be WTP function and let F be the corresponding fractional reward function, defined Eq. (8), For any fractional restricted ground set E Xg, both the time to compute F and the time compute a supergradient of F E are polynomial in n, G and log M.
Proof of Lemma 5.3. Consider the concave program:
F
Σ JEC
Cj min {bz, ÿ w))
JCVM
where the feasible region is given by {M( tv E [0. y P(M). TS.). Let y be an optimal solution this program. We will show that the dual variables (A),..., An) associated with the constraints Vi S T3 are valid supergradient of F at æ:.
First, we linearize the concave objective. For each j C, we introduce auxiliary variable 2j and enforce 2j S by and 2 S y wj. This yields the equivalent linear program:
Σ cjjj
max V.
JEC
2j S bj,
Vj EC,
S ÿ wi
Vj EC
y E 5 a
Next, we show how to solve the above linear program using the ellipsoid method. The main requirement is to construct separation oracle for the feasible Crucially, for any ÿ E [0, 1]". we can check membership in P(M) (ύ [0, Eies S rank(S), AS C V} by solving the submodular maximization problem
Σ J.. r(S)
max 8CIm
YES
where r(-) is the matroid rank function. This can be done efficiently via the greedy algorithm [Ed- monds, 2003, Schrijver, 2003]. If ÿ & P(M). we return the most violated constraint. The rest the constraints 2j S bj. 2j w. < I can be explicitly checked in polynomial time.
We solve the linearized primal LP using the ellipsoid method. During the process, the ellipsoid method generates only a polynomial number of constraints from the exponential family that are necessary define the optimal face of the feasible region. We then reconstruct reduced LP consisting of
these constraints along with the explicit ones (i.e., 2j < bj. 2j S y wi, and ÿ S 2). This approach follows standard technique for solving LPs with exponentially many constraints via the ellipsoid
method and extracting reduced LP from the active constraints [Grötschel et al., 2012, Schrijver, 1998].
This reduced LP has polynomial size and can be solved in polynomial time using an interior interior-point method [Nesterov and Nemirovskii, 1994, Boyd, 2004), efficiently in practice using the simplex method. Both types of solvers return the primal and dual optimal solutions. In particular, we obtain the vector of dual variables À (AI...., ) corresponding the constraints y; F;-
These dual variables constitute valid supergradient of F at क [Boyd, 2004]. That is, for any ø' E R".
F( < F()) ( E' -))
give the pseudocode of the above procedure Algorithm
For completeness, we show that the vector of dual variables À is a valid supergradient. This result is proven in Chapter 5.6 Boyd [2004], which establishes the correspondence between dual variables and subgradients in parametric convex optimization. Consider the following optimization problem:
max 7
f(z
s.t.
E P(M)
ÿ < x
0 S T 1
30

---

Algorithm 2 Compute Supergradient of F(T)
Require: Point ă E [0, matroid M 1: Define the LP:
Σgz
max D,
jEC
s.t. S bj,
2j v VjEC,
y E P(M), セ x
2:
if P(M) has polynomially many constraints then
3:
Solve the LP using solver that returns both primal and dual solutions (e.g., interior-point)
4:
else
5:
Solve the LP using the ellipsoid method with a separation oracle for P(M) Record the violated constraints identified by the oracle during optimization Construct a reduced LP with:
6:
7:
the recorded matroid constraints,
w,, the explicit constraints: 2 by. 2j S w. and ~
8: Solve the reduced LP using solver that provides access the dual variables
9:
end if
return dual variables (AI...., ,n) corresponding constraints T S x
The Lagrangian is:
(() + En(a= 11) + Σ (1(1 - us) +
M(a;;
Σ SC(0)
us ss)),
where (V) is an indicator function that is if ÿ E S and 0 otherwise. The dual function is:
9(A, v. 11) = min L(ū p.
The optimal value of the primal problem is:
F(
max 20
g gA,, 12).
Now, suppose that we perturb T to ,'
T + u. The perturbed optimization problem becomes:
max
f(0)
s.t.
DE P(M) ÿ 5 7/
5 +
0 05ğ51.
The Lagrangian for the perturbed problem is:
fū + Σ A ((z; + u:) - yi) + Σ 11(1 -1) + Σ
psls(y),
Se(n]
which simplifies to:
C( Σxe,. Nuu.
Minimizing over ÿ. the perturbed dual function is:
g' (A, U. p1) = g(A. p1) + Σ Asui.
31

---

The optimal value of the perturbed problem is:
g(). Σ X0es
F(T')=
max
9' d(A,
max 220,2201220
2
Thus, get the inequality:
F(0') S F()) + Σ Acus.
The dual variables À = (A1, A2,... ....., An) are supergradients of the function F(Ø) since they satisfy the following inequality for any æ and T::
F( F + 8)
where we substituted
-
F Experiments
F.1
Datasets and Problem Instances
We run experiments on six datasets: datasets Wikipedia, Images, and MovieRec were taken from the experimental setups of Balkanski al. [2016], Stan al. [2017]; an influence maximization dataset based on the Zachary's 's Karate Club graph Zachary [1977], Influence; and two synthetic datasets: a team formation dataset, TeamFormation and weighted coverage dataset, Coverage.
As in 02SSM, the objective is to select, in an online fashion, a set of items corresponding to articles, images, movies, nodes, experts, sets and receive reward equal that of the best among them. For Wikipedia, Images, and MovieRec, l and k were selected based on the experiments of prior work [Balkanski al., 2016, Stan al., 2017]. For Influence and TeamFormata was arbitrary, while for the Coverage dataset the choice was adversarial to the One- sta-etag-- algorithm.
the choice
In all cases, we use n to denote the dimension of the decision space, m the number of distinct objective functions, and T the time horizon. For Wikipedia, Images, and MovieRec, we construct a sequence of T objective functions by sampling T = 4 m functions uniformly at random from the m available functions. For the remaining datasets (Infl TeamFormation, and Coverage) we set T = m and use each of the m functions exactly once, in sequence.
We summarize the basic information for each dataset in Table 2.
Wikipedia. In the Wikipedia dataset, the goal is maintain of articles for Machine Learning that are highly relevant for a diverse set of subtopics (e.g., Markov Models, Neural Networks). The function f((S) measures how relevant the set of articles S is to the subtopic In total, we have 407 articles and m = 22 subtopics. We define f.() as the number of Wikipedia pages in the subtopic i that have a link to at least one article in S. Note that fa is a coverage function. We set fe fi by sampling subtopic i uniformly at random. We consider total of T = 4. m 88 time steps.
Images. In the Images dataset, the goal is to maintain a set of images that contain diverse set of visual elements. We used the VOC2012 dataset Everingham and Winn [2011] where each image contains a set of categories (e.g., chair, car, bird, etc.). For each image i we define fi(S) as the maximum similarity (minimum & distance) between the image and image in S. This objective is named Clustered Facility Location in Balkanski et al. [2016] and Exemplar-Basee Based Clustering in Stan al. [2017]. We have total of 10 different functions fi. We set = by sampling image i E [r)] uniformly at random. We consider a total of T = 4 m = 40 time steps.
MovieRec. In the MovieRec dataset Harper and Konstan [2015]. we consider a movie recommender system. We use the MovieLenss dataset that contains movies from different genres and user ratings. The goal is to maintain small set of movies so that every user can find enjoyable movies in this set. For each user i, we define the function fa(S)) as follows. Let ruk the rating given by user to movic k. Let R.y(S) {maxtes Tis k in genre j} be the highest rating that user i has given to
32

---

movie in genre j that belongs in S. Let way be the percent of movies in genre that user has rated out of all their rated movies. Then,
fi(S)
Σ (iyRiy(S).
JeGenees
Note that f; is a facility location function [Si Salem et al., 2024, Karimi et al., 2017]. We have total of m 100 different functions f:. We set f. fo by sampling a user i [n]] uniformly at random. We consider total of T = 4 m 400 time steps.
Team Formation. In the TeamForman FramFormation dataset, we consider a roster selection problem. The goal is to maintain a set of l individuals (i.e., a roster), so that when a new task ft arrives, there exists a subset of & individuals within the roster that can handle the task. order to model the performance of team when faced with a task ft, we use quadratic function of the form
fe(y) = h + T H.y-
The linear/modular part of the function captures the strength of each team member, and the quadratic part captures the complementarty/overlass
between their skills. Note that fa is monotone and submodular, iff H S 0 and h + Hy O, for all y E (2( We generate h, by sampling each coordinate from a Gaussian distribution with mean μ 30 and standard deviation a 20. Then, we generate H, by sampling each entry from Gaussian distribution with mean μ 20 and standard deviation o = 10, while ensuring the all entries are non-pot con-posiieve. If the constraint h, + H,y 0, Vy ((r) is violated, shrink the entries of Hr until is satisfied. We construct a total of m = 50 functions and consider a total of T = m = 50 time steps.
Influence. In the Influence dataset, we address two-stage influence maximization problem using Zachary's 's Karate Club as the underlying graph. The dataset assumes the presence of 5 distinct topics sports, politics, etc.), with each node in the graph being assigned subset of these topies. The objective is to maintain a set of nodes such that, at any time step f, it is possible to select a subset of k nodes from this set maximize the influence random cascades by sampling each edge of the graph with probability i [5] is selected uniformly random. A node can influence other nodes only within its connected component in the sampled graph, provided that it has been assigned the selected topic. Note that the influence function is weighted coverage function, since every node covers all the nodes in its connected component [Kempe et al., 2003].
specific topic. We generate total of T 100 0.25. In addition, topic
HotpotQA. The HotpotQA" " [Yang et al., 2018] dataset consists of approximately 97K questions along with ground -ouund-truthaan answers and Wikipedia articles that support the ground-truth answer. We create an 02SSM instance with the goal of maintaining a small collection of Wikipedia articles that can be used to answer questions from the HotpotQA dataset. The universe of elements is chosen to be the union of all Wikipedia articles that are supporting any question and its size approximately n 111K articles. For every question in the HotpotQA dataset, let S(4) S [n]] be the set of its supporting articles and es(g) E (0, 1)m be its characteristic vector. We associate q with a coverage-like WTP function fg defined as:
(xr) = min(11 x:)
For our experiment, create an arbitrary ordering of the above WTP functions and sample T 500 functions in the following way: with probability 0.5 we pick a uniformly random function (with replacement) from the first 30 functions of the order, otherwise we pick uniformly random function (with replacement) from the rest.
Coverage. In the Coverage dataset, we consider weighted coverage problem with 100 sets St...., Sn. We set é = 10 and k = 1. Consider the sets Si,,,.... ..,...,,,, S5 defined as follows. The first set covers the first é elements of the ground set and receives reward M for every covered element:
fz
M mimi(,, x),
33

---

where M = 100 is the value of covering an element of the groundset and is an indicator vector with coordinate and 0 everywhere else.
The rest of the sets i = .....; ,.,,, l, cover one, different, element each:
f2(²)) = M min(1, et41 x))
fe( M min(1, E2e x))
The online sequence of functions follows the pattern f1. f2.... fo and then cycles back to f1. We consider total of 50 eycles, which results in T f 50 = 500 iterations.
This dataset constructed in such a way so that Saee-stae--Oee algorithm performs poorly. Specif- ically, when One- tane-stag--one -OGA receives fi it aggressively updates all coordinates .1..... without taking into account that only one element can eventually be used for f1 due to the second-stage cardinality constraint of k 1. Eventually, weight on the first 28 coordinates and all other coordinates equal to 0, i.c.,
Aneesstae--OG converges to vector having equal
TT (1/2, 1/,,,.................. 1/2, .,....)).
After rounding the above vector with Randomized Pipage Rounding we get restricted dataset that has an expected reward of M/2 for the functions ,2,...,J and approximately M for fi-
The optimal solution in hindsight, however, only puts weight È coordinates, using exactly element for each second-stage objective, due to the inner constraint 1. That is, the optimal solution in hindsight is
T (0 0......I,...... 1.0...,00
and achieves value MM for every function.
On the other hand, RAOCO eventually converges vector that has a uniform of element spread across the elements of function Si and also takes more element for every other function f Se:
Øt R
8'
Rounding the above vector with Randomized Pipage Rounding yields restricted ground set that has expected value M for every function.
The above also explain the result observe in the Coverage experiment in Figure 1. As the time evolves, RAOCO improves and converges to the offline optimum in hindsight achieving cumulative average reward approximately M 100, while the cumulative average mne-stage-OGa remains constant at approximately M /2 50.
F.2
Algorithms
Online Algorithms. We provide several implementations the RAOCO algorithm (Algorithm 1). Implementations differ only in the OCO policy used the fractional domain. In partieular, have implemented RAOCO-OGA, RAOCO-FTRL-L2, RAOCO-FTRL-BB where we use Online Gradient Ascent (OGA), Follow the Regularized Leader (FTRL) with L2 regularization and entropy regularization, respectively. For each algorithm and dataset, we tested different values for the learning rate 1) E (0.0001, 0.001, 0.01, 0.1, 1, 10} and reported the best results. In Table 3, we report the 7 we used for each algorithm and dataset.
Online Competitors. We implement the following online competitors: Random selects a set of l elements uniformly random at each timestep; One-stage-OGA (1S-OGA) runs RAOCO-OGA as if the second stage cardinality constraint was k = E, i.e., (single stage) online submodular maximization. This the algorithm presented by Si Salem et al. [2024] for (one-stage) online submodular maximization.
34

---

Dataset
RAOCD-OGA
RAOCO-FTRL--ES
RADCO-FTRL-H
1S-0GA
Wikipedia
0.1
0.1
1
Images
10
10
10
0.1
MovieRec
0.001
0.001
0.01
1
TeamFormation
0.01
1
1
0.1
Influence
0.01
0.01
0.01
0.01
Coverage
0.01
0.001
0.01
0.1
Table 3: Optimal learning rates for each combination of dataset and algorithm.
Offline Benchmarks. As offline benchmarks, we implemented the
(OFLN-CO) algorithm proposed by Balkanski et al. [2016], and the Replacement -reedy (OFLN-RGH) algorithm proposed by Stan et al. [2017]. For completeness, we present the algorithms here.
Pantinoous-Optimizael [Balkanski et al., 2016] follows the relax-then-round paradigm. First, they solve the following program:
Σ (ii)
max f wh....... Dr
s.t.
yt E P(M), vt e [T]
Úr 5 ã
0 y: 1, Vt [2].
Let (#**, 7 ....... V7.) be the solution of the program. Then, they reduce Æ² by a factor (1 - c²), where = 1/k2/2-e, for < 1/2. We set independently to get an integral solution
1/4. Next, they round each coordinate of (1 6 e')@"
1, w.p. 81
Vi e [n].
x2
0. otherwise
If Φ satisfies the cardinality constraint, we return æ. Otherwise, if x violates the cardinality constraint (E 24 I f), we return uniformly random solution.
Replacement- Greedy [Stan et al., 2017] is based on a local search approach. First, we start with a series of useful definitions. Let (e, A) = (AU {e}) fa(A) denote the marginal gain of adding e to the set A if we consider the function ft- Let T(e, A) = {e' E A Ae(e) \ {e') E I) be the set of all elements in A that be replaced by without violating the matroid constraint. Let
A A), V. A)
(e) E
max (0, maxee((e.A) S( (e))) ((4)),
otherwise
be the gain of either inserting into A or replacing e with one element of A while keeping A an independent set. Let
AU EI
EI
Rep, (e, A)
arg (ax,") f((A((e) \ (e'))
( - f((A) otherwise
be the element that should be replaced by maximize the gain and stay independent. Using the above definitions, we give the pseudocode of Repl acement-Greedy
Algorithm 3.
Metrics. For the online algorithms we measure the cumulative average reward.
C,
F.(2.).
In order to calculate (xx Gurobi's integer linear program solver. We also compute the optimal (integral) solution in hindsight (OPT):
1
F
max
F((x).
T
ZEX.
35

---

Algorithm 3 Replacceent-Greedy
1: S 0
2: B, < for all SIST
3: for to do
4:
e" argmax,ev E B.),,
5:
S + SU({"}
6:
for 1
7:
if Vfle", B₂) > 0 then
8:
B. B, U {6*} Rep,(e", Bi)
9: end
end for 11: end for
return S
We repeat each experiment 5 times and report the average C. along with one standard deviation above and below the average depicted via the shaded regions. The sources of randomness are: (i) Randomized Pipage rounding, and (ii) sampling of the objective functions fe for datasets Wikipedia, Images, and MovieRec.
Setup. All the experiments
Apple M2 Macbook with 16GB RAM. The code is written in Python 3. 1.2. We make the code and data used for the experiments publicly available on GitHub. Each experiment runs efficiently personal laptop: every problem instance could be computed until the time horizon T less than one minute.
G Additional Experimental Results
G.1 Exploring the k CT tradeoff
In this section, we explore the tradeoff between & and CT, where I' is defined for each dataset at Table Recall that when k. the problem becomes equivalent one-stage online submodular maximization. We focus on the following algorithms: RAOCO-OGA, One-stage-OGa We also report the value of the optimal (integral) solution hindsight OPT. Figure 2, for each dataset, we show the cumulative average reward C₁ + (x,,) of each algorithm for each value of k. For each dataset and each k we each experiment 5 times and report the average Or as well as the standard deviation. For each dataset, we fix l' to the value reported in Table 2.
We observe that for most datasets, varying & does not significantly affect the performance gap between the two algorithms. many cases, the two algorithms perform similarly, with the MovieRec dataset being notable exception: RAOCO consistently outperforms One-stage-OGe and its performance remains close to that of the optimal solution in hindsight.
However, in the Coverage dataset, we observe that as l: increases, the gap between the two algorithms narrows. This is expected due the dataset's construction: One-stage-OGa tends to greedily select multiple elements for the first coverage function f1, whereas RAOCO learns to pick one element per function. Consequently, for small values of k. many of the elements selected by One-st cee-sttge--00 OGA cannot be used in the second stage for fi. As k grows, these elements become usable, and the performance of One ime-stage-OGG begins to recover.
G.2 Exploring the & vs Cr tradeoff
In this section, we explore the tradeoff between l and Cr, where is defined for each dataset at Table 2. We focus the following algorithms: RAOCD-OGA, One-stage-OGA We also report the value of the optimal (integral) solution hindsight OPT. In Figure 3, for each dataset, we show the cumulative average reward Cr ΣT F(( of each algorithm for each value of E. For each dataset and each E, we run each experiment 5 times and report the average Cr as well as standard deviation. For each dataset, we fix & to the value reported in Table 2 and we vary & as multiple of k that is kt 2h: 5k. We observe that varying & while keeping the second-stage cardinality constraint l fixed does not significantly affect the performance gap between the two online
36

---

040
130
520
16.
642
642
3502
230
OFT
22
225
350
25
175
(a) Wikipedia
(h) Images
(c) TeamFormate
330
PACO-OGA
40-
OFF
(d) MovieRec
(e) Inf luence
(l) Coverage
Figure 2: & vs Or tradeoff for RAOCD-OGA and Ane-stage-OGa where 7 is defined for each dataset Table 2. We report the average value of Cr over 5 runs. The shaded regions correspond one standard deviation above and below the average.
22.3
15.000
390
25.
662
300
7.5
030
(a) Wikipedia
(b) Images
(c) TeamF TeamFormat ormaaormat 1
MAD00-054
153
DF1
12.5
3004
MCCO-O6A
(d) MovieRec
(e) Inf luence
(l) Coverage
Figure 3: f vs OT tradcoff for RAOCO-O0C and One- One-stage-One DGA, where I' is defined for each dataset Table 2. We report the average value of CT over 5 runs. The shaded regions correspond one standard deviation above and below the average.
algorithms in most datasets. Across these settings, both algorithms exhibit nearly overlapping curves, indicating similar behavior. A notable exception is the MovieRec dataset, where RAOCO consistently outperforms One- Ane-stage-OGa DGA and approaches the performance the optimal fixed restricted ground set in hindsight.
In contrast, the Coverage dataset highlights a clear divergence: for small values of f, the two algorithms perform similarly, but as l increases, the performance of One-stage while that of RADCO improves. This behavior is expected given the construction of the dataset; tne-stage- tends to allocate more mass to elements that benefit the first coverage function fi- despite the second-stage constraint allowing only one element be used. contrast, RAOCO learns to include elements that are useful for different functions, resulting in higher cumulative reward.
deteriorates
G.3 Scalability of RADCO
To further assess the scalability of our approach, we experiment on a substantially larger dataset, namely HotpotQA [Yang et al., 2018], which consists of 97 85, questions with ground-truth
37

---

1.0
0.6
0.4
RADCO-DCS
Random
OFLN
100
200
300
400 500
Time Steps
Figure Cummulative reward of RAOCO- OGA, Random and OPT on HotpotQA
answers and supporting Wikipedia articles. We construct an 02SSM instance by associating each question with coverage-like function described in Appendix F.1. The union of all supporting articles forms ground set of 111,140 articles. Our goal to identify a restricted ground set of size L 150, from which k 4 articles are selected in the second stage for each question.
We generate T 500 objectives f,....,ff fr using the following sampling scheme: with probability 0.5 we select random question from fixed pool of 30 questions, and with probability 0.5 select one uniformly at random from the remaining questions. In Figure 4 we compare the cumulative reward of RAOCO-OGA against the fractional offline optimum (OPT) and Random.
Each iteration RAOCO-OGA requires solving one linear program, which we do Gurobi (using free academic license), followed by randomized pipage rounding of the fractional solution. On an Apple MI MacBook (16GB RAM), each step completes approximately 30 seconds on average.
H Online Convex Optimization (OCO)
In this section, we describe the the OCO policies Py used by our algorithm, i.e., Online Gradient Ascent (OGA) and Follow the Regularized Leader (FTRL). Both algorithms enjoy sublinear regret guarantees (O (T)).)). We refer the interested reader to Hazan [2016] for a more detailed treatment.
H.1 Online projected (super-) Ascent (OGA)
Online projected (super-)Gradices Ascent (OGA) [Hazan, 2016] comprises the following update rule:
Tt-1 11 (æ. + 79::),
where y is the learning rate, 9t is a supergradient Fe at Te, and 11 (.) the orthogonal projection on the set Xz.
H.2 Follow the Regularized Leader (FTRL)
Follow-the wew.hh----gglliee-eeeeeee Leader (FTRL) [Hazan, 2016] comprises the following update rule:
E = argmax
gr. .) R(x))
where is the learning rate, gi is supergradient of Fr ã.. and R is a strongly convex regularizer.
38

---

I Randomized Pipage Rounding
In this section, describe the Randomized Pipage Rounding algorithm for the case of cardinality constraints. The algorithm proceeds by iteratively rounding the fractional entries of ă until all components either 0 or 1. Let M₂
32 1] be the set of fractional components. At [3:
each iteration, two cases are considered:
If only one element in 전 is fractional (i.e., [Ha 1), we simply round this element to 1. This operation guaranteed to be feasible.
If multiple fractional elements remain (i.e. [Ha] 1), two components 24 and žy are arbitrarily selected from H.g. For these selected indices, define two quantities e1 and e2 follows:
min(1 H,, Zy), E2 min( ..)
These quantities represent the maximum possible adjustment to V, and žy while ensuring that the values remain within the range [0, 1]. Then random decision is made based on the ratio of e2/(er + 22). Specifically, the following actions are performed:
With probability fr we increase T by é1 and decrease T by EL.
With the complementary probability, we decrease T; by and increase ž, by
For more detailed analysis, defer the interested reader to Chekuri et al. [2009]. We state two lemmas that we use during our analysis in Appendix C.
Lemma I.1. [Chekuri et al., 2009] Let ă E X be a fractional vector and a = E(t) be resulting vector after running Randomized Pipage Rounding æ. Then, the following is true
Ez(z] =
Lemma 1.2. [Chekuri al., 2009] Let γ vector after running Randomized Pipage Rounding on Then, for any submdular function f. the following holds
X be a fractional vector and = =(x) be resulting
E [f(x))
Eg an
RAOCO in the offline 2SSM problem
For the sake of completeness, we give small proof that the ingredients of RAOCO can be used to
obtain c. 1/e) approxiaaton for the offline 2SSM problem when the input functions are WTP, where CM (1 * /k!) if M is uniform matroid of rank i and сы (1 1/e) otherwise.
The aforementioned guarantee improves upon the state-of-the-arr for the case cadinality constraints and WTP functions. Specifically, while Balkanski et al. [2016] achieve approximation guarantee of 1 1/c- 2(1/vk), our bound converges to the optimal value of 1 1/e more sharply as k increases, and yields strictly better guarantees for small values of We illustrate this comparison in Figure 5.
We now prove our offline guarantee formally in the following lemma.
Lemma J.1. Let [ni] be a universe of elements and M be a matroid over [n]. Let also E, k E and fi...., f. Fa.M be the input of the offline 2SSM problem. There exists randomized algorithm that runs in polynomial time in m, G and log M and outputs a ground set x E Xr for which
m
m
I
F(())
2 2c((1 11e)
Max 2E
EF(())
where the expectation is taken over the randomness of the algorithm and CM = (1-tttt) if M is uniform matroid of rank k and cM 1/e) otherwise.
Proof of Lemma J.I. Description of the algorithm. The offline algorithm is the following: first, construct the fractional reward functions Fi...., F as defined in Eq. (8), of the given WTP functions. Then, solve the following concave program
max R
39

---

Comparison of Approximation Guarantees
0.6
Aporoximeton Reão
Hardness: 1- 1/e
(Cardinality) RAOCO (this paperl: (1 1/el(1 - kk(kk)
(Cardinality) Balkanski
1/ee- 1/k
(Matroids) RADCO (this papert: 1/0)²
(Matrolds) Stan 2017: (1 1/e*)/
0.0
20 40
60
100
Figure 5: Comparison of approximation guarantees as function of & for the (offline) 2SSM. The guarantee of both our algorithm and the one by Balkanski et al. [2016] converge to the optimal value 1/e as + co, but our algorithm achieves strietly better guarantees even for finite k E N. Notably, our guarantee for cardinality constraints also outperforms the ttae-off-theaae bound for matroid constraints from Stan et [2017] for all 2. For general matroids, our guarantee for 2SSM ((1 1/e)² se 0.40) is slightly worse than the one by Stan et al. [2017] (1/2(1-11)) 1/e²) 0.43).
Finally, round the solution of the above program using Randomized Pipage Rounding (see Ap- pendix I).
Analysis. We know that each fractional reward function F, is concave over X (Lemma D.I) and their supergradient, any point in Xx, be computed in polynomial time in n, G and log M (Lemma 5.3).
Therefore, the above concave program can be solved in polynomial time in m, G and log M using standard first-order or interior point methods [Bubeck. 2015]. Let ø be a maximizer of the above program. In the last step, the algorithm rounds "" using Randomized Pipage Rounding. Let x = = ) ) be the resulting integral vector.
The analysis is concluded as follows:
F((
Σ 1=1
Es (F(((()))
Lom. 5.4
m
2 eM(1 1/e)
F((T"))
t=1
=c1(1 1/cc) max
F((
t=1
XiCR 2
CM(1 - (1/e)
max
F((x))
ZEN.
[=1
=(())=F((()) VrENi
cM(1 (1/e))))) &E
max
Ft(
[=1
40


Reviews:
[{"review_id": "pR3V58qlsK", "reviewer": "Reviewer_2YLy", "summary": "The (stochastic) submodular maximization problem aims to maximize an objective subject to some constraint defined over a ground set, where the objective is picked u.a.r. from a collection of monotone submodular functions. The two-stage submodular maximization problem (2SSM) aims to find a subset of size at most $\\ell$ from the ground set such that when restricted to this subset, the previous submodular maximization problem attains a high maximal value in expectation. This paper studies the online version of 2SSM. For weighted threshold potential functions, an important subclass of monotone submodular functions, it provides an online algorithm that achieves an $O(\\sqrt{T})$ $(1-1/e)^2$-regret under a matroid constraint and the ratio is slightly improved for uniform matroid.", "questions": "The (offline) 2SSM admits a better approximation ratio for coverage functions, a subclass of weighted threshold potential functions. Can one obtain the same ratio for online 2SSM by applying the approach of the paper?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Quality. The paper is technically sound. The main result is supported by theoretical analysis. Besides, the performance of the proposed algorithm is validated by experiments on both real and synthetic datasets.\n\nClarity. The paper is organized well. The algorithm involves several components. The paper thoroughly explains each of them and lists the corresponding lemmas used to prove the final theorem.\n\nSignificance. The paper is the first to consider the online version of the well-studied 2SSM problem and attains sublinear regret for the problem. Though built on submodular maximization, the problem is not a standard online submodular maximization (OIM) problem. Therefore, the result extends previous results on OIM to a non-submodular setting. This could be of interest to researchers. On the other hand, the approach is somewhat limited since it works only for a subclass of submodular functions. Besides, it looks difficult to extend the algorithm to general submodular functions since they do not admit computable concave extensions.\n\nOriginality. The paper exploits an algorithmic framework developed for online submodular maximization in a non-standard submodular maximization problem. Although the overall algorithmic framework derives from prior work, this paper contains sufficient technical contributions, as the successful application of the framework requires key insights and technical lemmas.", "was_revised": true, "final_justification": "Thanks for the authors' reply. My concerns have been addressed. I will retain my score.", "rebuttal": "We kindly thank the reviewer for their detailed feedback. We appreciate their positive view of the paper’s contributions.\n\n__“The (offline) 2SSM admits a better approximation ratio for coverage functions, a subclass of weighted threshold potential functions. Can one obtain the same ratio for online 2SSM by applying the approach of the paper?”__\n\nThank you for bringing up this point. This requires a somewhat subtle comparison to prior work, that we clarify below, and can add to the paper as needed.\n\nTo the best of our knowledge, the only results that pertain to coverage functions in the context of two-stage submodular optimization appear in Balkanski et al. (ICML 2016). There are two guarantees provided by Ballkanski et al. in the context of coverage functions.\n\n- First, along with their algorithm for general submodular functions, they propose a local search method that offers a $1/2 (1− 1/e) \\approx 0.31$-approximation for the special case of coverage functions, under cardinality constraints.  \nFor large $k$, this guarantee is worse than the  $1-1/e-1/\\sqrt{k}$ guarantee of the continuous optimization algorithm also proposed by Balkanski et al. The latter algorithm also works for general submodular functions. The $ \\approx 0.31$ guarantee is also worse than the  $(1-1/e^2)/2 \\approx 0.43$ guarantee provided by Stan et al. (ICML 2017), which also works for arbitrary submodular functions over general matroid constraints.  This is why we did not include the local search algorithm of Balkanski et al. in our literature review. \n\nOur framework already achieves the state-of-the-art approximation ratio ($(1-1/e)(1-e^{-k}k^k/k!)$)  both in the offline and online settings, for WTP functions and thus also for coverage functions, in the case of cardinality constraints. For more details, we refer the reviewer to Appendix J and Fig. 4. In particular, our guarantee is better than the guarantee by Stan et al. (ICML 2017) for $k \\geq 2$. It is also better than the\n$1-1/e-1/\\sqrt{k}$ guarantee of Balkanski et al. for all $k \\geq 1$.\n\n- Second, Balkanski et al. also point out that, for constant $k$ , a variant of their local search algorithm yields an improved $0.5$ approximation, still for coverage functions. This algorithm has a running time that is exponential in $k$. Note that our guarantee is better than $0.5$ for all $k > 3$, and does not require that $k$ is a constant. In fact, our algorithm’s running time is independent of $k$.\n\nIn summary, the guarantees for coverage in the offline case, under cardinality constraints, are not better than the ones we obtain here (either online or offline).\n\nIn the case of general matroid constraints, there are no special guarantees for coverage functions. The state-of-the-art approximation ratio in the offline problem is by Stan et al. (ICML 2017), who achieve a $(1-1/e^2)/2 \\approx 0.43$ approximation, for general submodular functions. In the case of general matroid constraints, the offline version of our algorithm yields a $(1-1/e)^2$ guarantee.  We discuss how our (offline) guarantee relates to prior work over matroid constraints in Table 1 and Appendix J. Note that the local search algorithm of Stan et al. heavily relies on the knowledge of all second-stage functions for its decisions, while our algorithm works in the online setting and operates without prior knowledge of second-stage functions."}, {"review_id": "wUA9WBer7u", "reviewer": "Reviewer_ToR4", "summary": "This paper focuses on the two stage submodular maximization problem in different settings and subject to cardinality and matroid constraint.\n\nThe first result in this paper follows the general steps of Balkanski et. al.   and slightly improves the approximation ratio in the offline setting. The improvement is mainly for small values of k.\n\nThe authors also consider the online setting and provide a 0.4 approximate algorithm for the general matroid constraint setting but only for a specific class of functions (WTP). In this online setting the functions are revealed in an online fashion and not the elements.", "questions": "1- Can the proposed algorithms be applied on much larger datasets?\n2- The motivation behind the online setting is not strong in my opinion, can you elaborate on its importance and applicability?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The main strength of the paper is overcoming the challenge of computing the function F. This function is not submodular and also it cannot be computed in polytime. The techniques used here are interesting but seem to be limited to this specific problem. \n\nThe online setting considered in this work is not that interesting and the motivations provided for it are not strong enough. This combined with the marginal improvements in the offline setting raises concern about the importance and strength of this paper. This is also not for general submodular functions and only for WTP. Most of the previous works cited in this paper (see Table 1) are for general submodular function and in more practical settings.\n\nThe experimental section requires significant changes. Currently it is not possible to conclude that the proposed algorithms can be used in practice. The main reason is that the datasets considered are tiny.", "was_revised": true, "final_justification": "I missed the point about the assumptions on the submodular functions. I also appreciate the more details on experiments and applications. The datasets considered here are still quite small compared to the large ones experimented on in submodular maximization literature (by an order of magnitude or so). I still have some concerns regarding the setting and techniques.", "rebuttal": "We thank the reviewer for their feedback. However, we believe that there is a fundamental misunderstanding regarding the main contributions and focus of our work.\n\n__“This paper focuses on the two stage submodular maximization problem [...] The first result of this paper [...] in the offline setting. [...] The authors ALSO consider the online setting.”__\n\nThe paper’s primary focus is the __online__ two-stage submodular maximization (O2SSM) problem, where the second-stage functions are revealed sequentially. Our main contribution is the first algorithm with sublinear $\\alpha$-regret guarantees for this setting. The offline results (including the improved approximation for small $k$) are a (fortunate) by-product of our online framework, but not the central contribution. The online version of this problem was explicitly left as an open question by Stan et al. (ICML 2017), making our result the first to close this gap.\n\n__“The online setting considered in this work is not that interesting and the motivations provided for it are not strong enough”__\n\nThe online setting we study is __more natural and realistic than the offline two-stage submodular maximization problem in nearly all applications considered in prior work.__\n\nConsider the recommender system case, for instance, in which a platform must proactively maintain and update a restricted catalog $S$ (of size $\\ell$) __before user requests materialize__. As a result, as new users, preferences, and content (movies, videos, or music) arrive continuously, __user utility functions are not known ahead of time__, and decisions on how to maintain this restricted catalog need to be made in advance.\n\nNote that this setting, and the pertinent challenge, describe the (offline) 2SSM problem, as studied by Stan et al. (ICML 2017) and Balkanski et al. (ICML 2016). How is the challenge handled in the offline setting? Stan et al. and Balkanski et al. __assume that a distribution over user utilities is known__. In the online setting, __we remove this assumption: we do not assume that utilities come from a known distribution__. Instead, utilities are picked in an arbitrary (potentially adversarial) fashion. Clearly, __making fewer assumptions than the offline setting makes the online setting more practical and better motivated, not less.__\n\nProviding guarantees in the online setting, and thereby lifting distributional assumptions, is a common theme in online algorithms; it is in fact the main reason they are studied, and of great interest to the machine learning community. Papers on online convex optimization and online submodular maximization have appeared in NeurIPS (Zhang et al. 2019; Harvey et al. 2020; Zhao et al. 2020; Ghai et al. 2022; Nie et al. 2024; Xu et al. 2024), ICML (Fotakis et al. 2021; Gergatsouli et al. 2022; Wan et al. 2023;), and COLT (Ito et al. 2024; Kozachinskiy et al. 2024; Appel et al. 2025; Mhammedi 2025), to name a few. The online setting is thus both of interest to the community as well as the original authors of (offline) 2SSM.\n\nNote that, precisely because they make no distributional assumptions, online problems are more technically challenging than their offline counterparts. This is another reason why online submodular maximization and online convex optimization are active areas of research, and why Stan et al. themselves pose online 2SSM as an open problem.\n\nIn conclusion, while the offline two-stage framework has been justified in prior work, our online framework strictly generalizes it, __removing the strong assumption that a distribution over objectives is known in advance__. The extension to the online setting was also highlighted as an open problem by Stan et al. __Finally, all other reviewers recognized the problem’s significance and strong motivation.__\n\n__“This is also not for general submodular functions and only for WTP. Most of the previous works cited in this paper (see Table 1) are for general submodular function and in more practical settings.”__\n\nWe stress that previous works in Table 1 are for the __offline__ 2SSM problem, __not__ the online O2SSM problem. __Our work is the first to provide any guarantees in the online setting for any submodular functions (WTP or otherwise)__. We also stress that our online setting is a more challenging and realistic setting than the offline setting: the offline setting requires distributional assumptions; the online setting does not. Hence, we do not agree that the offline setting is more practical.\n\nFinally, Weighted Threshold Potentials (WTPs) form a broad subclass of monotone submodular functions that subsumes all applications studied in prior two-stage maximization work, including Weighted Coverage, Influence Maximization, Facility Location, and Team Formation. __Our results directly apply to all applications presented as a motivation by Balkanski et al. (ICML 2016) and Stan et al. (ICML 2017), despite focusing on WTPs.__ Note that several works on submodular maximization focus on restricted classes of functions, both in the offline and online setting (Karimi et al. NeurIPS’17, Bai et al. NeurIPS’18, Bian et al. ICML’17, Hassani et al. NeurIPS’17, etc.)\n\n__\"“The techniques used here are interesting but seem to be limited to this specific problem.”__\n\nWe stress that we solve O2SSM for arbitrary WTP functions and general matroid constraints in the second stage, both of which include many important instances, as listed in Appendix A.2. \n\nOur techniques follow the general template of solving a continuous problem first, and then identifying an appropriate rounding. We design a novel scheme for 2-stage Submodular Maximization, when the feasible set of the second-stage maximization is restricted by a matroid constraint and depends on a first-stage decision. Such techniques are of broader interest and often find applications in different problems. As we also point out in the response to Reviewer SdED, the challenge we face lies in the incompatibility between standard contention resolution schemes (CRSs), which are essential for rounding continuous relaxations under matroid constraints, and the two-stage nature of the problem. Specifically, traditional CRSs require independent rounding, which is impossible when rounding across nested feasible sets (i.e., subsets selected in the first stage and constrained in the second).\n\nTo address this, we develop a two-stage rounding scheme based on a recent characterization theorem by Dughmi (ITCS 2020) concerning non-product CRSs. To our knowledge, this is the first time such a tool has been applied in a multi-stage stochastic setting. We believe this connection opens up new directions for multi-stage optimization under matroid and combinatorial constraints. Moreover, the rounding framework we introduce is not just an ad hoc fix: it may lead to closing the current approximation gap in offline 2SSM. Thus, we view this contribution as advancing rounding for structured, non-product settings, with potential applicability beyond 2SSM.\n\n__“The experimental section requires significant changes. [...] the datasets considered are tiny.”__\n\nWe recognize that our main contribution is theoretical, providing the first formal sublinear $alpha$-regret guarantee for O2SSM. Our experimental evaluation is intended to validate our algorithm’s behavior and to compare it directly with prior work, rather than to establish scalability. To ensure a fair comparison, __we follow the experimental setup of prior work__ [Balkanski et al., ICML’16; Stan et al., ICML’17], __using the same datasets__ (Wikipedia, Images, and MovieRec), to directly benchmark against established baselines. To highlight the broad applicability of our framework, we also include the Influence and TeamFormation datasets, while the Coverage dataset is designed to illustrate the benefits of two-stage optimization over one-stage formulations.\n\nNevertheless, to address the reviewer’s concerns, we have conducted a new experiment on a dataset whose groundset is two orders of magnitude bigger than the ones tested by our paper and prior work. We discuss this in the next paragraph.\n\n__“Can the proposed algorithms be applied on much larger datasets?”__\n\nAll components of our algorithm scale to larger datasets. The online optimization routines (FTRL, Gradient Ascent) compute gradients efficiently in polynomial time via linear programming, and the rounding step (pipage rounding) runs in $O(n)$ time for cardinality constraints. As discussed in Section 5 (“Computational Complexity”), these components do not cause bottlenecks. To strengthen the paper, we include a large-scale experiment based on the HotpotQA dataset with __a ground set of $10^5$ articles__. Our algorithm selects, at each iteration, a set of articles that “cover” an unknown topic revealed after the selection. Despite the large ground set, __each iteration solving a convex program over the dataset and rounding the result via Randomized Pipage Rounding, completes in under 30 seconds__, demonstrating the practical scalability of our approach. Notably, __the algorithm of Stan et al. needs more than 15 minutes to find a restricted groundset in the above dataset, even for a small number of second-stage functions (e.g. less than 10)!__\n\nWe include a table below showing the fractional optimal set in hindsight, the cumulative reward of our algorithm, and Random.\n\n| Alg.   | t = 0 | t = 20 | t = 40 | t = 60 | t = 80 | t = 100 | t = 120 | t = 140 | t = 160 | t = 180 | t = 200 |\n|---|----|----|----|----|----|---|---|----|----|---|---|\n| Fractional Offline Optimal | 1.0 | 1.0  | 1.0  | 1.0  | 1.0   | 1.0    | 1.0   | 1.0  | 1.0  | 1.0   | 1.0  |\n| RAOCO OGA | 0.0   | 0.571  | 0.659  | 0.590  | 0.593  | 0.594   | 0.612   | 0.596   | 0.578   | 0.564   | 0.560   |\n| Random   | 0.0   | 0.0    | 0.0    | 0.0    | 0.0    | 0.0     | 0.0     | 0.007   | 0.006   | 0.006   | 0.005   |\n\nTable: Cumulative reward vs. time over HotpotQA dataset."}, {"review_id": "B3tlO1H8qG", "reviewer": "Reviewer_SbnU", "summary": "This paper studies the online version of the Two-Stage Submodular Maximization (2SSM) problem, introduced by Balkanski et al. [2016].\n2SSM is an interesting problem that aims to select a subset $S$ of core elements from a ground set $V$ (1st stage), such that the expected utility over a collection of submodular functions $\\mathcal{F}$ on the selected subset $S$ is maximized (2nd stage).\nIt can be seen as a special kind of coreset problems.\n\nThe main challenge is the objective function:\n\n$$\\max_S E_{f \\sim \\mathcal{F}} [\\max_{S' \\subseteq S} f(S)],$$\n\nwhere the maximization over $S'$ is taken *inside* the expectation.\nThat means each submodular function $f$ is allowed to take on a different subset $S'$ of $S$.\nThis renders the expectation non-submodular, and difficult to handle.\n\nBalkanski et al. [2016] proposed to optimize a continuous relaxation and do randomized rounding to get a coreset $S$.\nThis paper follows the same idea but adapts it to the online setting.\nBesides, the authors leverage standard algorithms for online convex optimization and more powerful existing rounding techniques to achieve a sublinear regret bound for a specific class of submodular functions.\n\nI think this is a nice paper by combining the ideas of previous works on 2SSM and online convex optimization.\nBut relying heavily on existing components does reduce the novelty of the paper a bit.\nIn my opinion, the main discovery is the theoretical properties of the weighted threshold class of submodular functions that enable the analysis.\nMoreover, I have a question about the rounding technique (see below).\n\nRepresentation issues:\n- Typo: line 59 \"'\"\n- It would be great if the authors could briefly explain how to comprehend the size of $(1-1/e) (1-e^{-k}k^k/k!)$ compared to $(1-1/e)^2$.", "questions": "The authors state that \"we design a two-stage randomized rounding procedure, used only in our analysis, that is coupled with the rounding performed by RAOCO.\"\nI am not sure if I understand this correctly.\nIf the advanced rounding technique is used virtually, then what rounding is actually used in the algorithm?\nDoes the given algorithm still achieve the claimed regret bound?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The authors study an interesting problem, that is relevant to multiple applications such as recommenders.\n2. The authors are the first to study the online version of 2SSM.\n3. The authors leverage existing tools to achieve a sublinear regret bound for a specific class of submodular functions.\n\nWeaknesses:\n1. Concerns about the rounding techniques and the claimed bounds.\n2. Given the heavy theoretical machinery, the algorithm is not scalable (up to thousands of elements).", "was_revised": true, "final_justification": "I thank the authors for the rebuttal and clarification.\nMy concerns have been addressed.\nI improved my score.", "rebuttal": "We thank the reviewer for their feedback.\n\n__“Explain how to comprehend the size of $(1-1/e)(1-e^{-k}k^k/k!)$ compared to $(1-1/e)^2$”__\n\nPlease refer to Figure 4 in Appendix J. In this figure, we plot the aforementioned quantities as well as the approximation ratios of the prior work in the offline problem. We observe that $(1-1/e)(1-e^{-k}k^k/k!)$ is larger than $(1-1/e)^2$ for all $k \\geq 1$.  Also, compared with $1-1/e-1/\\sqrt{k}$, which is the previous state-of-the-art approximation ratio for a cardinality constraint in the second stage, our guarantee is better for all $k\\geq 1$.\n\n__“The authors state that \"we design a two-stage randomized rounding procedure, used only in our analysis, that is coupled with the rounding performed by RAOCO.\" I am not sure if I understand this correctly. If the advanced rounding technique is used virtually, then what rounding is actually used in the algorithm? Does the given algorithm still achieve the claimed regret bound?”__\n\nWe thank the reviewer for the opportunity to clarify this point regarding the algorithm’s rounding procedure. The point raised by the reviewer is important and is also related to the technical novelty of our contribution.\n\nThere are indeed two rounding procedures used in our analysis:\n\n__1) Rounding used by Alg. 1 (Pipage Rounding)__\nRecall that Algorithm 1 must output a subset of size $\\ell$ (the “restricted groundset”). To do so, it runs an Online Convex Optimization (OCO) policy (e.g., FTRL or OGA) to obtain fractional values for the elements (a “fractional restricted groundset”) and then applies Randomized Pipage Rounding to produce the final integral restricted groundset (see Appendix I). This is, in fact, the only rounding procedure used by the algorithm. The rounding is very simple, efficient, and easily implementable. No other rounding needs to be implemented to execute the algorithm; __the regret bound stated in the paper (Theorem 5.1) is correct, and is indeed achieved using exactly this procedure.__\n\n__2) A second rounding, introduced only in the regret analysis__\nWe stress that this second rounding __is not used by the algorithm, and is only used in the analysis as a tool to prove a lower bound__. We describe this in lines 246-250 & 717-721, but we will attempt to clarify this further here.\n\nObserve that, by Lemma 5.2, the fractional restricted groundset that the OCO policy returns is “good enough” : if the algorithm could output that, it would have no regret.\n\nHowever, as discussed above, the algorithm needs to round this restricted groundset, say $\\widetilde{x}$, to an integral groundset $x$. It does so by running Randomized Pipage Rounding. In order to prove that the algorithm’s output has sublinear $\\alpha$-Regret, we need to prove that the “value” of the rounded groundset is at least an $\\alpha$ factor of the “value” of the original fractional groundset $\\widetilde{x}$.\n\nThe “value” of a restricted groundset is measured by the maximal value a function $f$ can attain when optimized over the restricted groundset, i.e. $F(x) = \\max_{\\substack{y \\leq x, \\\\ ||y||_1 \\leq k}} f(y)$.\n\nAs $\\widetilde{x}$ is rounded to $x$, it is highly nontrivial to track what is the relation between $F(\\widetilde{x})$ and $F(x)$, as the input of $F$ changes the feasible region of the inner maximization problem.\n\nTo prove the desired relation, we do the following: Fix $\\widetilde{x}$, the algorithm’s output $x$, and a function $f$.\n\nLet $y^{\\*}$ be the maximal solution of $f$ on the restricted groundset, i.e. $F(\\widetilde{x}) = f(y^{\\*})$.\n\nWe construct a new solution $y’$ that lies in the rounded restricted groundset $x$, for which it holds that $f(y’) \\geq \\alpha \\cdot f(y^*) = \\alpha \\cdot F(\\widetilde{x})$.\n\nNote that the maximal value of $f$ in the groundset $x$, namely $F(x)$ (!),  is going to be at least $f(y’)$, because $y’$ is just one feasible selection.\n\nTherefore this concludes our proof that: $F(x) \\geq f(y’) \\geq \\alpha \\cdot f(y^*) \\geq \\alpha F(\\widetilde{x})$.\n\n\nThis is our proof of Lemma 5.3 on a high level. In order to make this proof possible, we need to come up with a way to construct $y’$ given $\\widetilde{x}, x$ and $y^*$. This is exactly what the second ”virtual” rounding does.\n\n\n\nThis rounding first constructs an intermediate (possibly infeasible) integral solution $\\hat{y}$​ and then applies a contention resolution scheme (CRS) to obtain a feasible solution $y’$. We describe this procedure in detail in Appendix C. Lemmas C.1 through C.5 build up to the guarantee that $f(y’) \\geq \\alpha f(y^*)$ as we described above. \n\n\nThis argument is central to proving Lemma 5.4 and, ultimately, our regret bounds. \n\nTo summarize, __the second rounding, as technical as it may be, is not used by the algorithm and is only used in the analysis as a tool to prove a lower bound.__\n\nWe hope that this clarifies the role and purpose of the two-stage rounding in our analysis.\n\n__“Given the heavy theoretical machinery, the algorithm is not scalable (up to thousands of elements).”__\n\nAll components of our algorithm to scale to larger datasets. The online optimization routines (FTRL, Gradient Ascent) compute gradients efficiently in polynomial time via linear programming, and the rounding step (pipage rounding) runs in $O(n)$ time for cardinality constraints. As analyzed in detail in Section 5 (“Computational Complexity”), these components do not pose practical bottlenecks.\n\nTo further strengthen the paper, we will include a large-scale experiment in the final version. In this experiment, based on the HotpotQA dataset __with a ground set of $10^5$ articles__, our algorithm selects, at each iteration, a set of articles intended to “cover” an unknown topic revealed only after the selection. Despite the large ground set and the online nature of the task, __each iteration, i.e., solving a convex program over the dataset and rounding the result via Randomized Pipage Rounding, completes in under 30 seconds__, demonstrating the practical scalability of our approach.\nNotably, the algorithm of Stan et al. needs more than 15 minutes to find a restricted groundset in the above dataset, even for a small number of second-stage functions (e.g. less than 10)!\n\n\nWe include a table below showing the cumulative reward of our algorithm, the fractional optimal set in hindsight, and Random (i.e., selecting the restricted groundset randomly).\n\n\n| Algorithm                   | t = 0 | t = 20 | t = 40 | t = 60 | t = 80 | t = 100 | t = 120 | t = 140 | t = 160 | t = 180 | t = 200 |\n|-----------------------------|-------|--------|--------|--------|--------|---------|---------|---------|---------|---------|---------|\n| Fractional Offline Optimal  | 1.0   | 1.0    | 1.0    | 1.0    | 1.0    | 1.0     | 1.0     | 1.0     | 1.0     | 1.0     | 1.0     |\n| RAOCO OGA                   | 0.0   | 0.571  | 0.659  | 0.590  | 0.593  | 0.594   | 0.612   | 0.596   | 0.578   | 0.564   | 0.560   |\n| Random                      | 0.0   | 0.0    | 0.0    | 0.0    | 0.0    | 0.0     | 0.0     | 0.007   | 0.006   | 0.006   | 0.005   \n\n\nTable: Cumulative reward of different algorithms over HotpotQA dataset, as a function of online steps\n\n\n\n__Typos:__\n\nThank you for spotting the typo in line 59.  We will fix this and will correct all other typos pointed out by reviewers."}, {"review_id": "bfJlFG2aGt", "reviewer": "Reviewer_SdED", "summary": "This paper addresses the problem of two-stage submodular maximization in an online setting. At each round $t$, the algorithm selects a subset $x_t$ of size $\\ell$ in the first stage, after which the submodular objective function $f_t$ is revealed. In the second stage, the algorithm performs submodular maximization over the selected subset. The authors propose an algorithm that leverages techniques from online convex optimization and rounding methods, and demonstrate that it achieves sublinear regret when the objective functions $f_t$ belong to the class of Weighted Threshold Potentials (WTP).", "questions": "1. The proofs in the paper appear to rely heavily on techniques from prior work. Could the authors clarify the main technical contributions and specify the key challenges they had to overcome in establishing the primary results?\n2. Given the computational overhead introduced by the first stage, could the authors elaborate on why the two-stage online submodular maximization framework is more efficient and advantageous compared to traditional online submodular maximization methods?", "limitations": "yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The studied problem is well-motivated and significant. In many online scenarios, the large size of the ground set can pose computational challenges for the submodular optimization algorithms. In this sense, the idea of optimization in two-stages, which means first choose a subset and then perform submodular optimization on the restricted set, offers a practical and compelling solution to this issue.\n2. The paper is well-written and easy to follow. \n3. The result that $\\tilde{F}$ is also concave and Lipschitz, and thus the OCO policies can be applied is also interesting.\n\nWeakness:\n1. The main weakness of the paper lies in the practicality of the proposed approach. While the two-stage setting is designed to address scenarios where the ground set is large and optimizing over a smaller subset is computationally efficient, the method introduced in this work is itself computationally intensive. Although the authors show that the algorithm runs in polynomial time, the overall computational overhead may limit its applicability in real-world online settings. As such, the practicality of the proposed method for large-scale problems remains questionable.", "was_revised": true, "final_justification": "I would like to thank the authors for the response. Most of my concerns are addressed, while the practical applicability of the proposed approach still remains unclear to me. Therefore, I maintain my current evaluation.", "rebuttal": "We thank the reviewer for their feedback.\n\n__“Could the authors clarify the main technical contributions and specify the key challenges they had to overcome in establishing the primary results?\"__\n\nFirst of all, we would like to thank the reviewer for the opportunity to re-iterate the main technical contributions of our work. These are split into two “categories”, those regarding the function F(x) and those regarding the two-stage rounding.\n\n__a) On $F(x)$:__\n\nRecall that the way that prior work measures the quality of a restricted groundset $x$ is by associating it to the maximal value a function $f$ can attain when optimized over it.\nThis is captured by $F(x) = \\max_{\\substack{y \\leq x, \\\\ ||y||_1 \\leq k}} f(y)$.\nThis is non-concave and, as we discuss in the paper, is NP-hard to compute. Thus, contrary to other online settings (like OCO and OSM), we cannot assume oracle access to the reward function when designing an online algorithm.\n\nInstead, we work with the fractional relaxation $\\widetilde{F}$ of F, which simply relaxes y to be fractional and replaces $f$ with its fractional relaxation.\n\nAn immediate challenge is that the behavior of $\\widetilde{F}(x)$ is far from obvious; its input dictates the feasible region of the inner optimization problem and the relation between $x$ and $\\widetilde{F}(x)$ is highly non-trivial. \nSurprisingly, we show that $\\widetilde{F}$ is concave over the domain of $x$ and, even more importantly, that its super-gradients can be computed efficiently. To do the latter, we write $\\widetilde{F}$ as a linear program and show that the dual variables corresponding to the constraints $y_i \\leq x_i$ are actually a super-gradient of $\\widetilde{F}$.\n\nBoth of the above structural insights are non-trivial and essential in order to leverage existing tools from the OCO literature.\n\n__b) On the two-stage rounding:__\n\nDesigning a two-stage rounding procedure that handles matroid constraints is particularly challenging. Notably, no prior continuous optimization approach for the offline two-stage submodular maximization problem has succeeded in handling matroid constraints (the work of Balkanski et al. ICML 2016 only had a very simple rounding that works for a single cardinality constraint in the second stage). \n\nThe difficulty stems from the fact that the primary tool for rounding under matroid constraints, i.e. contention resolution schemes (CRSs), requires that coordinates are rounded independently at random. This is inherently incompatible with the two-stage setting: in our case, each coordinate $y_i$ in the second-stage solution must satisfy $y_i \\leq x_i$​, where $x$ is the rounded first-stage solution. Consequently, the distribution over $y$ is inherently dependent on $x$, and since the first-stage solution $x$ must satisfy a global cardinality or matroid constraint, its coordinates are also correlated. This breaks the independence assumption required by standard CRSs and rules out their direct application. \n\nTo overcome this, we leverage a recent characterization theorem by Dughmi (ITCS’20). We notice that Dughmi’s result implies that it is sufficient for the rounding distribution to satisfy a structural property known as submodular dominance (Definition B3) in order for a CRS to exist for this sampling distribution. This implication is hinted at in Dughmi’s work, but we formally state and prove it as Lemma B.7. We believe that this connection could find applications beyond our setting. \n\nEquipped with this insight, we show that, if we apply Randomized Pipage Rounding to the fractional first-stage solution and then sample an \"intermediate\" second-stage solution conditioned on the first stage (as detailed in Appendix C), the resulting distribution satisfies submodular dominance (Lemma C.4). This crucial property allows us to apply a CRS in the second stage and obtain a feasible solution with provable approximation guarantees.\n\n\nFor a higher-level discussion of the two-stage rounding, we refer you to our response to Reviewer SbnU and Appendix C.\n\nWe have discussed such issues in Section 5 (lines 239-244) and Appendix C (lines 727-732). We will revise the paper to make sure these technical contributions are more evident.\n\n__“The main weakness of the paper lies in the practicality of the proposed approach. While the two-stage setting is designed to address scenarios where the ground set is large and optimizing over a smaller subset is computationally efficient, the method introduced in this work is itself computationally intensive. … Given the computational overhead […] by the first stage, could the authors elaborate on why the two-stage online submodular maximization framework is more efficient and advantageous compared to traditional online submodular maximization methods?”__\n\nWe appreciate the opportunity to discuss this. As the reviewer is asking us to compare two-stage submodular optimization to standard submodular optimization (online or otherwise), this is a question pertaining to the motivation of the two-stage submodular maximization setting in general (online and offline).\n\nIt would be good to clarify that a multi-stage approach is indeed often used for computational advantages. For example, many of today’s recommender systems involve multiple stages, progressively reducing the set of items to be recommended. Efficient early-stage recommender algorithms are run initially, and subsequently, more computationally expensive late-stage recommenders are applied at later stages (see, e.g., Liu et al., 2022a; Hron et al., 2021; Zheng et al., 2024; Covington et al., 2016).\n\nHowever, in many circumstances, the 2-stage approach is inevitable for reasons that do not have to do with computational considerations. One example is caching/pre-fetching (see also Appendix A.2 in the paper):  a system may need to pre-fetch content (e.g., a movie, a large file) to a CDN server close to the user, in advance of the arrival of the user and the expression of their demand. Beyond the computational issue of computing user preferences over a large content catalog when the user arrives (and expresses their demand), the server is restricted to delivering (quickly) only items they have prefetched, and this pre-fetching (that takes time) has to happen before demand manifests. \n\nAppendix A.2 gives several more examples, where decision making (ground set restriction) needs to happen in advance of the manifestation of the demand (the revelation of the objective function). Another simple and intuitive example is putting together a team roster: the players in a team, programmers in a software company, etc., need to be hired before tasks to be performed (playing games or coding a feature requested by clients) are revealed, manifesting any skills required.\n\nFinally, going back to the computational motivation for having multiple stages,  the computational burden/overhead of the first stage is not as large as alluded to by the reviewer.\nIn fact, approaching the problem as an online submodular maximization problem, as suggested by the reviewer, will not yield computational dividends as OSM algorithms have similar computational complexity (e.g. Si Salem et al. AAAI 2024).\n\n\nWe have made an effort to highlight the scalability/computational complexity of our algorithm in Section 6 and the necessity of the multi-stage approach beyond computational reasons in Appendix A. We will revise these points to make these issues more prominent."}]

Author rebuttal:

Meta-review: This paper initiates the study of online version of two-stage submodular maximization, and gives regret results for WTP functions. The result is competitive, and the techniques are solid. The main weakness seems to be the experiments, and the formulation of the problem may also be argued. As raised by some reviewers, a potential flaw is the scalability of the algorithm, but this seems clarified/resolved during the rebuttal. The review is overall positive, and I recommend to accept the paper.
Decision: Accept (poster)