Streaming Stochastic Submodular Maximization with On-Demand User Requests
Authors: Honglian Wang
Sijing Tu
Lutz Oettershagen
Aristides Gionis
Venue: NeurIPS 2025 poster ()
Keywords: Streaming
Submodular Maximization
Stochastic Algorithms
Coverage
User Request
Primary area: optimization
TL;DR: This paper proposes an approximation algorithm for streaming stochastic submodular maximization problem under a novel on-demand user requests senario

Abstract: We explore a novel problem in streaming submodular maximization, 
inspired by the dynamics of news-recommendation platforms.
We consider a setting where users can visit a news web\-site at any time, and upon each visit, 
the web\-site must display up to $k$ news items. 
User interactions are inherently stochastic: each news item presented to the user 
is consumed with a certain acceptance probability by the user, 
and each news item covers certain topics. 
Our goal is to design a streaming algorithm that maximizes the expected total topic coverage.
To address this problem, we establish a connection to submodular maximization subject to a matroid constraint.
We show that we can effectively adapt previous methods to address our problem when the number of user visits is known in advance 
or linear-size memory in the stream length is available.
However, in more realistic scenarios where only an upper bound on the visits and sublinear memory is available, the algorithms fail to guarantee any bounded performance.
To overcome these limitations, we introduce a new online streaming algorithm that 
achieves a competitive ratio of $1/8\delta$,  where $\delta$ controls the approximation quality. Moreover, it requires only a single pass over the stream, and uses memory independent of the stream length. 
Empirically, our algorithms consistently outperform the baselines.

Streaming Stochastic Submodular Maximization with On-Demand User Requests
Honglian Wang
Sijing Tu
KTH Royal Institute of Technology
KTH Royal Institute of Technology Digital Futures Stockholm, Sweden
Digital Futures Stockholm, Sweden
Lutz Oettershagen University of Liverpool Liverpool, UK
Aristides Gionis
KTH Royal Institute Technology
Digital Futures
Stockholm, Sweden
Abstract
We explore novel problem in streaming submodular maximization, inspired by the dynamics of news-recome www.srecommenittion platforms. We consider setting where users can visit a news website at any time, and upon each visit, the website must display up to k news items. User interactions are inherently stochastic: each news item presented the user is consumed with a certain acceptance probability by the user, and each news item covers certain topics. Our goal is to design streaming algorithm that maximizes the expected total topic coverage. To address this prob- lem, establish a connection to submodular maximization subject to matroid constraint. We show that we can effectively adapt previous methods to address our problem when the number of user visits is known in advance linear-size memory in the stream length available. However, in more realistic scenarios where only upper bound on the visits and sublinear memory is available, the algorithms fail to guarantee any bounded performance. To overcome these limitations, we introduce
online streaming algorithm that achieves competitive ratio of 1 1/(85), where 8 controls the approximation quality. Moreover, requires only a single pass over the stream, and uses memory independent of the stream length. Empirically, our algorithms consistently outperform the baselines.
Introduction
Streaming submodular maximization has been extensively studied under various feasibility con- straints, including matchoid [7, 8, 10], matroid [9], knapsack [21, 22] and k-ser [20] constraints. In the classical setting, the goal is to select a single subset items from data stream and output it when the stream ends. However, this classical framework falls short in many real-world scenarios, for exam- ple, when seeking to maximize content coverage in online news recommendation. In such a setting, users visit news website multiple times and expect receive relevant set of articles each visit. Meanwhile, new articles continuously arrive at the content- content-provider" s server in a stream fashion. The long-ten long-term objective to maximize the total content coverage across user visits. Existing streaming submodular maximization algorithms are ill-suited for this use case, as they are designed to produce single solution and do not support multiple or on-demand user interactions during the stream.
Motivated by this limitation, we introduce a novel problem called Streaming Stochastic Submodular Maximization with On-demand Requests (S3MOR). While the setting is broadly applicable to streaming submodular maximization tasks with multiple output requirements, we focus on the news
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Comparison of our algorithms. N N denotes the stream length, E N number of news
items to present per user access, T E N and T E N are the exact number and upper bound of user accesses, and 5 E N an approximation parameter.
Algorithm
Competitive ratio
Time
Space
Response time
LMGREEDY
1/2 1/1(T" -T+1)
(NNTE) ONTE O(NT
O( +T)
O(NK) O(T")
STORM
O(T)) O(T22k/8)
STORM+
1/188)
O(T))
recommendation task for illustration. Therefore, in S3MOR. the data stream consists of incoming news items that the system aggregates into a personalized news website. Each item V, covers a set of topics and is associated with probability pt. representing the probability that user will click the item when it is presented. A user may visit the system arbitrarily often and at any time during the stream. At each visit, the system must select and present subset of most is items from those that have arrived in the stream up to that point. If a user clicks on item V,, they are exposed to all topics associated with that item. The objective is maximize the expected total number of unique topics covered by all user clicks across all visits. This setting is challenging due to its online character:
On-demand: At any point, the system must be ready to output subset of news items.
Irrevoeability: Once a subset presented to the user, it cannot be modified.
To the best of our knowledge, no existing algorithm directly addresses the S3MOR problem.
We evaluate the performance of online streaming algorithms that make irrevocable decisions using the notion competitive ratio. An algorithm is called c-competitive if, for every input stream a, the value A(a) achieved by algorithm A satisfies OP 2 e, where (P) denotes the value of an optimal offline solution with full access to the input stream.
A(r))
To evaluate the performance of our algorithms, clarify the notions of response time complexity, time complexity, and space complexity.
Response-time complexity vs. time complexity. For the S3MOR problem, assume there exists an oracle that can evaluate the objective function fS)) for any feasible candidate set S. We define the response time complexity of an algorithm as the worst-case number of oracle calls needed to produce a recommendation result of size after the user submits a request. This metric captures the latency users experience. In contrast, time complexity is defined as the worst-case number of oracle calls required by the algorithm over the entire stream.
Space complexity. In practice, all users share common storage for original news items. We distinguish between two storage types: shared storuge containing original items accessible to all users (not counted toward space complexity), and per-user storage for additional memory each user needs to compute personalized recommendations, including document identifiers and user-item association probabilities. Throughout this paper, "space complexity" refers exclusively to per-user storage.
Our contributions. We reduce S3MOR to the problem of streaming submodular maximization under partition matroid constraint, which allows us to leverage existing online streaming algorithms. Based on this reduction, we propose three algorithms and evaluate them across multiple dimensions: competitive ratio, space complexity, time complexity, and response time complexity. We state our main results as follows:
We prove that provided sufficient memory store the whole stream, a greedy algorithm, LMGREEDY, can achieve the best possible 1/2 competitive ratio for the S3MÓR problem.
If the exact number 7 of user visits is known, the reduction preserves the competitive ratio of the underlying online streaming submodular algorithm.
However, in realistic scenarios, the number of user visits T' is unknown and we need to guess the number of visits as T" T. For this case, we introduce algorithm STORM, which has a competitive ratio of 1 -TT"-
To achieve a better competitive ratio, we propose a second algorithm STORM++ that makes multiple concurrent guesses of T, maintaining solution per guess. It then greedily

---

aggregates outcomes across guesses. This algorithm achieves competitive ratio of 1/(56), where is tunable parameter that balances efficiency and solution quality. The space and time complexity increase by factor of 8T" relative to the underlying streaming algorithm.
STORM and STORM++ achieve worse competitive ratios than LMGREEDY, but they utilize much smaller space and have significantly better response time.
We summarize the results for all algorithms mentioned above in Table 1. We validate our approach through empirical experiments on both large-scale and small-scale real-world datasets. Our re- sults show the effectiveness of our algorithms in terms of coverage quality and memory usage, in comparison relevant baselines.
Notation and background. We assume familiarity with constrained submodular maximization and competitive analysis. We provide formal definitions in Appendix A.
Related work
Submodular optimization plays a fundamental role machine learning, combinatorial optimization, and data analysis [13, 26, 29], capturing problems with diminishing returns, and finding applications in data summarization [34, 42], non-parametric learning [17, 45], recommendation systems [1. 33, 38, 44], influence maximization [24], and network monitoring [13]. The classical greedy algorithm achieves a (1 1/e) -pparopoxxiiaooon for monotone submodular maximization under cardinality constraints [39], and extends to matroid constraints [6, 12].
We study stochastic submodular coverage functions, where the objective depends on random re- alizations but selections must be made non-adaptively. This contrasts with adaptive submodular- ity [16, 18, 37, 41], which models sequential decision-making with feedback and supports strong guarantees for greedy strategies. Related work includes stochastic variants of set and submodular cover, where the objective itself random; notable examples analyze adaptivity gaps and approxima- tion bounds under oracle access [15, 19].
Classical greedy algorithms for (constrained) submodular optimization [27, 35, 39] assume random access to the full dataset, which is infeasible in large-scale or streaming settings. This challenge has motivated streaming algorithms that make irrevocable decisions under memory constraints [4, 5, 9, 22, 23, 36). Buchbinder et al. [5] apply the preemption paradigm, i.c., replacing elements with better ones, to achieve tight (1/2 - E) -appproximttoonn for monotone functions under cardinality constraints. Sieve++ [23] uses thresholding to achieve (1/2 e) -approximation under cardinality constraints using only (k) memory. Extensions to matroid and partition constraints include [ 8, 10]; for instance, Chekuri et al. [8] gives 1/4pccomptiiiive online streaming algorithm for monotone p-matchoids. These approaches, however, do not handle stochastic item utilities or repeated, unpredictable user access. We address this gap by studying stochastic submodular coverage under partition constraints in a streaming model with limited memory and unknown user access requests.
To extend submodularity to sequences, Alaei et al. [1] introduce grguence-submodullan gequecce-monotonicity showing that a greedy algorithm achieves a (1 1 (1/e))))apppeeee approximatio,,, with applications in online ad allocation. Similarly, Ohsaka and Yoshida [40] propose k-submodular functions to model optimization over k disjoint subsets, providing constant- monotone cases. In contrast to their settings, our problem involves making irrevocable decisions as an incoming stream of items progresses, requiring each of the i subsets be constructed incrementally rather than all at once after seeing the entire input.
and
approximations for
Finally, diversity-aware recommendation and coverage problems are closely related, many systems must recommend item sets rather than single items, motivating submodular approaches to maximize coverage and user satisfaction [2, 43]. Ashkan et al. [3] propose greedy offline method for maximizing utility under a submodular diversity constraint. Yue and Guestrin [44] use submodular bandits for diversified retrieval, learning user interaction probabilities adaptively rather than relying on known oracle, as in our setting.
2 Streaming submodular maximization with on-demand requests
Problem setting. V (V1, V2,..., ., VN} } be an ordered set of N news items appearing in the stream, where item Vi arrives at time step i. Each news item V2 E V covers subset of topics from
3

---

. ca), where denotes the total number of topics. Formally, V; S C' for each E [N]. Additionally, each news item V; is associated with a probability' p; [0, 1]. modeling the probability that user will click the item when presented to them. When user clicks news item, we say that the user exposed to topics the news item.
predefined set of topics C' = (c1. .......
Moreover, we assume that we observe a binary variable Tæ E {0, 1 indicating whether the user accesses the system at time step i. Specifically, T; denotes an access at time step i, and 7; otherwise. Whenever T = 1, the system should present at most k news items from the available news items {V ( ......... Vi). Now, suppose user visits the system times. The system outputs T sets S s'.... SS" where S represents the items presented to the user at their t-th visit, for E [7]. We allow the same item to be presented multiple visits; however, we treat each appearance as distinct copy. We make this choice as the user has multiple chances to click on an item if the item is presented multiple times. Therefore, for any I * 8, we have S n 0. We define the set of all items presented to the user over the entire sequence of visits as S U'=
Objective function. We define f(S) as the expected number of topics the user covers after T visits, where the expectation taken over click probabilities. Let E {00, 1} indicate whether topic cy is covered, i..., the user clicked at least one item that covers e from the shown sets S',... , The probability Pr(a,- = 0) that topic ej remains uncovered equals the probability the user clicks no items covering Cj-
Since the user clicks on item Vi with probability pt, the probability that they do not click on it is pi and, thus, Pr(o, 0) Hhr Ilvee (1 pz). leading to the expectation B|o,] = - He IIvees V,ae, (1 - p.). By linearity of expectation, the expected number of topics covered by user, which we denote by f(S), is given by
f(8) E
d
El, =
I- (E[T] MESS'
II
II
(L (L-
(I)
j=1
Lemma 2.1. f(8) is non-decreasing submodular set function.
Problem definition. We formally define our problem streaming stochastic submodular maxi- mization with on-demand requests (S3MOR) below.
Problem 2.2 (S3MOR). We define a news item stream S as a sequence of triples: S. TN)) (T)) where N is the (unknown) length of the stream. At each time step i, the system receives triple (Vs, Pt, TT). where V₁ E V, P; E 1), and T, E 10, Whenever news items from the set of items (Vi.... V.) received so far to denote the sets of news items presented to the user over T accesses. The objective is to maximize the expected number of distinct topics the user is exposed to by the end of the stream, measured by the function f(S).
((V1, PI. (1,T),,...... m),,... (VN. PN:
= the system selects up
present to the user. Let S = (S) (S!....,,S' S²
There are two key challenges in our streaming setting: (i) the system does not know in advance when how many times user will access it; and (ii) the system has to make decisions based on the information available so far, and these decisions are irrevocable. In the following, we show how the problem be reduced to submodular maximization problem subject to partition matroid constraint. We then leverage this connection to develop solutions under various memory constraints.
Reduction to submodular maximization under partition matroid constraint. We first reduce the S3MOR problem (Problem 2.2) to submodular maximization under a partition matroid constraint, which enables to apply efficient streaming algorithms with provable guarantees. Let r:: t H> ri map a user's s t-th access to its access time, and (rt)T= be the sequence of times at which the user accesses the system over an unknown time period. Whenever the user accesses the system, it presents up to i news items selected from all the news items available since the beginning of the stream, denoted by (V.)-
'These probabilities can be interpreted as measures of user-item preference or engagement, are typically estimated from historical click through data using machine learning models such as logistic regression, factor- ization machines, or neural networks trained on user behavior patterns and item features. We assume they are static and remain constant over time.

---

Let V be a copy of the item V; associated with the t-th visit. Let y" be a collection of these copies until the t-th visit, namely, V (VI = ........ .V......... Without loss of generality, we treat each copy as distinct item, i.e., V + V for all t + 8. Clearly, V n 1 = @ for +
Moreover, let S* _ V² be the set of news items that the system presents to the user at their t-th visit. Let S = U,= Sa be the union of all sets of presented items. Analogously to Equation (1), we adapt the function f: 2 V + R such that f(S) is the expected number of topics covered by the (copies) of news items that the user clicked on after S¹ ..... S have been presented to the user.
Observation 2.3. Let (U]= -U, F) be set system, where F is collection of subsets of [ V and F is constructed in the following way: for any set X C U V', | n V < k for any S 1 & T, then X E F. Observe that (u V F) is partition matroid. Problem 2.2 can be equivalently formulated as maxxeF f(X).
Based on Observation 2.3, we develop baseline algorithm for the Problem 2.2. Suppose that the system stores all the news items up to when the user accesses the system at the f-th time, and also has stored all the previous news item sets presented to the user, i.e., - S In this case, the stored news items up to time r2 constitute one partition of the matroid, i.e., V = {V Ji=1- We then apply the local greedy algorithm by Fisher et al. [12], i.e., the system greedily selects i news items from y that maximize the marginal gain of the objective function with respect to f ) This algorithm does not require any knowledge of T. and has competitive ratio of 1/2. Since all incoming news items need to be stored, the memory usage is SN(N + kT), and the running time is Σg= [()")))). The response time is (NNk) since it selects & items iteratively from O(N) items. We present the algorithm in Algorithm 3 (LMGREEDY) in Appendix B.
Theorem 2.4. Algorithm 3 for Problem 2.2 has competitive ratio of 1/2. space complexity O(N + KT), time complexity O (, and response time complexity (NN)). Moreover, the competitive ratio of 1/2 is tight, iee. for Problem 2.2, no streaming algorithm can achieve competitive ratio better than 1/2 without violating the irrevocability constrains.
The drawback of LMGREEDY that its memory usage depends linearly on the stream length, making it infeasible for large streams. Thus, we consider the setting where the system has limited memory and can store only user-specific subset of news items.
3 Algorithms with limited memory
We now consider more realistic setting where the system has limited memory. Our objective is to substantially reduce the memory usage and the response time complexity while achieving a bounded approximation ratio. We first establish that any algorithm achieving reasonably good performance must use at least (Tk) memory.
To illustrate this lower bound, consider the following example: Suppose that a user makes 7 requests; the input stream contains more than Tk items, each containing one distinet topic and associated with acceptance probability of 1. At the end of the stream, the user sequentially submits T requests. If an algorithm is allocated with only ((T'k) memory for some T" S T, it can store at most O(T*k) items, thus, at most O(T'k) k) distinct topics. However, optimally, the user may access ( distinct topics. We can conclude that for this example, the competitive ratio is at most ( /T), which is arbitrarily poor when T' T.
Since the exact number of requests T is typically unknown in advance, we assume the system has access to upper bound 7' > T and is allocated S(KT') memory. This allocation is sufficient to store all candidate items throughout the user's interaction period. In practice, T" can be estimated from historical interaction data, allowing the system to set T' close to 7 within reasonable accuracy, ensuring both efficient memory utilization and meaningful performance guarantees.
3.1 A first memory-efficient streaming algorithm
Our first memory-efficient algorithm processes the incoming stream S as follows. First, it initializes T' empty candidate sets A' for E (7'), all of which are initially active. Upon the arrival of news item from the stream S, for each active candidate set, the algorithm either adds the item to the set or
5

---

Newn items streamm
RD
Vjt1
Distriluue V
Present muns Hetin to tani.
Candldaate
G
Schematic view of our algorithm STORM. We first initialize T" empty active candidate sets. For each incoming news item in the stream S, decide whether it can be added to/swapped into each of the active candidate sets. When user submits request, i.e., Tj = 1, we select the best active candidate set, present it to the and deactivate it.
Figure 1:
Algorithm 1: STORM
Input: Estimated visits T N, budget & N. AA 0. f1,-.. Th 9o + 0
At.
for (V, p) ) the stream do
for j E T do
if 1 < k then
A + UU
clsc
V" arg migiiveed uff
if f(V UE A9) 2 2x(f ( 49, then
A A' (V"
10
ifr
j' arg arg JT f(AlUUi 9¹)
T T (5*}
b> Deactivate candidate set A
gi+1 At
output G gi+1 i - ++1
14
replaces an existing item if the set full. When user accesses the system, the algorithm selects one of the active candidate sets present to the user. The chosen candidate set is then marked as inactivate and will not be updated further. Figure shows an overview.
Based on our reduction to submodular maximization under partition matroid constraint, we can adapt any streaming algorithm designed for matroid constraints, provided it produces irrevocable outputs. Notable examples include the algorithms proposed by Chakrabarti and Kale [7], Chekuri al. [8], and Feldman et [10], of which achieve 1 /4 approximation ratio. In our work, we specifically adapt the algorithm introduced by Chekuri et al. [8].
Our algorithm, named STORM, is shown in Algorithm It keeps track of the number of visits using a counter i. Assume the user has visited times when news item V, arrives. This implies that, prior the arrival of V,. active sets from i partitions have already been presented the user, and thus, neither V, nor any subsequent item will be added to these partitions. The algorithm iterates over the remaining 7" active candidate sets, and determines whether V, should be added any of them, with replacement if necessary.
The decision replace existing item V with the current item Vj is based the comparison of their incremental value with respect to set U' Specificallyy, we adopt the notation v(f, A't from Chekuri et al. [8] and define
v(ʃ, Userr -u (V), with UsefrrjA (V' UsErTA'': V < <V}.

---

Algorithm 2: STORM+
Input: Estimated visits T N, budget & N, parameter ó N.
g 0, 8 - 0, 0, P + 6, 26, ..... | 16]
for T do Initialize STORM (T, k)
Maintain STORM for different T
for T.P) in the sfream do
for T do
g++1.(T) t STORM (T, k).step(V T,P)
Process (V, by executing lines 3-15 of Alg
if T then
T + arg e f(g
g <- gi+l.(0")
output B
10
i+i+l
Here, V < V indicates item V' is added to the set Uetraa before item V. For a specific set A", VJ replaces item in A if (e
minve "fS, A', V).
Upon the 1-th user visit, the system selects which active candidate set to output in greedy manner. To be specific, let G',... G denote the candidate sets that have already been presented to the and T represent the indices of the remaining active sets. The system selects the active set that offers the highest incremental gain with respect to the union of previously presented sets. Formally, let j" arg maxjeT f(Al U G*), and the system outputs G¹ = A'"
Theorem 3.1. Let T be the number of user accesses and I' given upper bound. Algorithm 1 has competitive ratio wT---+1 space complexity O(T))), time complexity O(N and response time complexity O (T').
If the exact number of visits is known, we can set the upper bound T = T and obtain a 1/4- competitive ratio using Algorithm However, the competitive ratio of Algorithm can be arbitrarily bad if 7" is significantly larger than T. Note that our analysis is tight. We can demonstrate that for any fixed T, there exists an example such that the competitive ratio of Algorithm 1 is most TV. TT-74I' which is only constant factor away from analysis. We provide the proof in Appendix C.
3.2 A memory-efficient streaming algorithm with bounded competitive ratio
As shown in the previous section, to achieve a large enough competitive ratio with STORM. the system must have a good enough estimate of the number user visits T. However, in practice, this information is typically unavailable in advance. To address this issue, discretize the range [T"] to generate multiple guesses for the value of T, and run separate instance of Algorithm for each visits the system, each copy of Algorithm outputs solution, and select
guess. When the best solution over all the outputs.
Specifically, Algorithm/ 2 (named STORM++) first initializes the set of guesses of T as P {8i i E [[T'/=]]}, where 8 E N is parameter controlling the trade-off between competitive ratio as well as the space and time complexity. In this construction, there always exists a guess 7 E P that is between and 5 5. Therefore, if we would run Algorithm with 7 as the input parameter, and present the re- sults to the user, we guaranteed to have a competitive ratio of at least 1/46 as shown in Theorem 3.1; however, do not know the value of 7 in advance. Thus, adopt greedy strategy aggregate the results from all the copies of Algorithm 1 to determine an output for each user visit. At the i-th user visit, we collect the i-th output from each running copy of STORM with a different guess T P and select the one that maximizes the incremental gain. This selection rule leads the following result.
Theorem 3.2. Algorithm 2 has competitive ratio of 1/(88), space complexity O time complexity ONNIT" (6), and response time complexity O(T)).
7

---

4 Empirical evaluation
We empirically evaluate the performance of our proposed algorithms STORM and STORM++. We denote ST) and ST"RM(T") as the STORM algorithm with the input parameter set to T (i.e., exact number of user accesses) and T (i.e., upper bound of user accesses), resp.
We design our experiments to answer the following research questions: (Q1) How effective are the solutions provided by STORM++ and STORM(T") compared to other baselines and to each other? (Q2) What is the impact of parameters 8 and k on the performance of STORM+ and STORM(T')) (Q3) How sensitive are STORM++ and STORM(T") to the upper bound T" and do our algorithms require highly-accurate estimation of I to perform well?
We use the following baselines:
LMGREEDY:
Our upper-bound baseline, which assumes linear memory size in the stream length, i.e. potentially unbounded memory (Algorithm 3).
SIEVE++: Based on Kazemi et al. [23], we implement a heuristic version of the SIEVE++ algorithm solve the S3MOR problem. The adaptation proceeds as follows: (1) Before the
first user visit, we run the exact SIEVE++ algorithm and obtain output set S (2) For each subsequent i-th output, we run SIEVE++ on the data stream between the (i ( 1)-th and i-th user visits, using the marginal gain function f(- Uf=1 St) as the objective.
PREEMPTION: We adapt the algorithm proposed by Buchbinder al. [5] for solving the S3MOR problem in the same way as described above for SIEVE++.
Datasets: We use six real-world datasets, including four rating datasets KuaiRec, Anime, Beer and Yahoo, and two multi-label dataset RCVI and Amazon. The number of items these dataset contains vary from thousands to one million, and the topic sets size vary from around 40 to around 4000, We provide the details in Appendix D.I.
To simulate the news item stream, we randomly shuffle the items to form a stream of length N. To simulate the user visit sequence, we start with an all-zeros sequence and then randomly select T indices, and set those positions to one. We establish an upper bound on the number of visits by setting 7" T + AT for some positive AT. We generate synthetic click probabilities, and provide the details in Appendix D.I.
Experimental setting:
In all experiments, we randomly selected 50 users and report the average expected coverage for the Yahoo, RCVI, and Amazon datasets. Standard deviations and expected coverage results for the other three datasets are provided in Appendix D. We also report runtime and memory usage on the largest dataset, Amazon.
All experiments ran on a MacBook Air (Model Mac15,12) equipped with an Apple M3 chip (8-core: 4 performance and 4 efficiency cores), 16 GB of memory, and solid-state drive (SSD). The source code and datasets are available.
Results and discussion
Impact of l and T on the expected coverage. As shown in Figure 2, LMGREEDY achieves the best performance across all datasets and values of k. Among our proposed methods, STORM(T) consistently performs the best, followed by STORM++, then STORM(T"). Compared to baselines SIEVE++ and PREEMPTION, our algorithms generally perform better across datasets and values of k. with exceptions on RCV1, where PREEMPTION performs comparably to STORM(T"). In Figure 3, we observe trend shift: STORM++ slightly outperforms STORM(T') and STORM(T) across datasets and T' values. ST"RM(1") and (TORM(T') perform comparably. This performance shift is due to smaller d and AT' in this experiment, which lead to improved competitive ratios for STORM(T") and STORM++ Although STORM(T) offers the strongest theoretical guarantee of the three algorithms, STORM(T') and STORM++ can empirically outperform it (we give an example of this effect in Appendix D.2).
Performance regarding parameters and AT. Figure 4a shows that STORM++'S 's expected coverage decreases as 8 increases, consistent with theory: as 8 grows from 3 to 30, the performance guarantee
artppo /ttp///tttb...///////////... wwt. Voa//ooggVVVn///// Strooming Subsodular maximization with user request
8

---

- Storm++ * StormIT) - Storm:) LMGreedy
Preemption + Sieve+++
480
Expected Coverage
32-
Expected Coveraug
Expported Coverage
4010
24-
750-
16-
240
500
160
200
9
12
18
21
21
27
30
20
60
100
140
200
20
60
100
140
200
(a) Yahoo
(b) RCVI
(c) Amazon
Figure 2: Empirical variation in expected coverage as function budget datasets. Parameter
25 and AT are fixed
Expected Coveragee
Expected Coverage
100
Expected Coverage
600
26-
450-
30
200
300
15-
150
10
20
30
50
80
70
80
90100
30
35
40
5
T
(a) Yahoo
(b) RCVI
(c) Amazon
Figure 3: Empirical variation in expected coverage as function of number of visits T all datascts. Parameter k: 10.4 and AT are fixed.
Storm++ - Stor((]
StormI)
-
LMGreedy
Preemption
- Sieve++
Expecled Coverage
21
Expected Coverage
24
Number oracle calls
x <10
8-8-6
Number of oracle calls
106
22
Beer
23
Beer
7.5
2.0
22.5
1.5
22.5
Amiie
Anime
5.0
1.0
20.0
20.0
20.0
2.5
0.5
18
17.5
KuaiRee
16
KuailRed
0.0
0.0
30
10
30
50
70
100
15
30
3
15
30
AT'
T
(a)
(b)
(d)
Figure 4: Left two: Impact of AT' and 8 on expected coverage. In (a) and (b), we fix &: = 5 and T = 10. When varying 8, we fix AT 60; when varying AT, we fix 5 10. Right two: Oracle call counts the Beer dataset. We fix 8 25 and AT 45. When varying k. fix T 5; when varying T, fix
Table 2: Runtime and mem. usage for the Amazon dataset. We set k, T' and to 10, = 20.
STORM++
STORM(T")
STORM(T)
LMGREEDY
SIEVE+
PREEMPTION
Runtime (s) Memory (MB)
7.94
88.13 28.99
307.43 0.91
136.04
2.00
1.28
0.72
0.03
drops by factor of 10. This reflected empirically with coverage declines across datasets, for example, from 130 to 120 on Amazon.
Figure 4b shows that STORM(T")ss performance declines with increasing AT, matching the theoreti- cal drop in competitive ratio (e.g., 10-fold decrease from AT = 10 to 100). contrast, STORM++ is theoretically unaffected.
Number oracle calls, runtime and memory. Figure 4c shows that the number of oracle calls increases rapidly and linearly with budget & for both STORM(T') and STORM++, while remaining

---

relatively stable for other algorithms. Similarly, Figure 4d indicates linear increase in oracle calls with user visits T for STORM(T"). (T)RM(T), and LMGREEDY, but a much slower growth for SIEVE++ and PREEMPTION. Notably, Figure 4d also reveals a non- non-monotonic trend: oracle calls first rise, then decline with increasing T. This increase is due to the guessing strategy for T under 5 = 25 and AT = 45, where the number of guesses T increases (T {25, 50) for T = 3 and T = {25, 50, 75} for T E [6, 30).. The decrease is due to STORM++'S irrevocability-ag more subsets are presented to the user, fewer items remain in S for potential swap, thereby reducing the number subsequent oracle calls.
Table 2 shows that our proposed algorithms require much less memory than LMGREEDY, and use comparable memory the other two baselines. STORM(T") and (T)RM(T) are also significantly faster than the remaining algorithms.
Conclusion
We investigate a novel online setting for streaming submodular maximization where users submit on-demand requests throughout the stream. In this context, we introduce the Streaming Stochastic Submodular Maximization with On-demand Requests (S3MOR) problem with the goal of maximizing the expected coverage of the selected items. We first propose a memory-efficient approximation algorithm that highlights the trade-off between memory usage and solution quality, but its competitive ratio can be poor. To solve this, propose parameter-deeendent memory cemmorr--fficien approximation algorithm to trade off between the competitive ratio and the memory and time usage. Our empirical evaluations show that proposed algorithms consistently outperform the baselines. We believe our approach will have a positive social impact. For instance, it can be applied to enhance the diversity of news content recommended to the users, thereby helping expose them multiple viewpoints and broaden their knowledge. While our approach optimizes topic coverage and can be used to promote content diversity, its misuse, such as deliberately optimizing a submodular utility function that favors polarized or biased content, could risk amplifying existing biases. However, such outcomes would require intentional manipulation of the objective function. When applied responsibly, our approach does not pose such risks.
Acknowledgments and Disclosure of Funding
This research is supported by the ERC Advanced Grant REBOUND (834862), the Swedish Research Council project EXCLUS (2024-05603), and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
References
[1] Saeed Alaei, Ali Makhdoumi, and Azarakhsh Malekian. 2021. Maximizing sequence- submodular functions and its application to online advertising. Management Science 67, 10 (2021), 6030-6054
[2] Bushra Alhijawi, Arafat Awajan, and Salam Fraihat. 2022. Survey on the objectives of recom- mender systems: Measures, solutions, evaluation methodology, and new perspectives. Comput. Surveys 55, 5 (2022), 1-38.
[3] Azin Ashkan, Branislav Kveton, Shlomo Berkovsky, and Zheng Wen. 2015. Optimal Greedy Diversity for Recommendation. In IJCAI, Vol. 15. 1742-1748.
[4] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. 2014. Streaming submodular maximization: Massive data summarization on the fly, In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 671 1-80.
[5] Niv Buchbinder, Moran Feldman, and Roy Schwartz. 2019. Online submodular maximization with preemption. ACM Transactions on Algorithms (TALG) 15, 3 (2019). 1-31.
[6] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. 2011. Maximizing a monotone submodular function subject to matroid constraint. SIAM J. Comput. 40, 6 (2011), 1740-1766.
10

---

[7] Amit Chakrabarti and Sagar Kale. 2015. Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming 154 (2015), 225-247.
[8] Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. 2015. Streaming algorithms for submod- ular function maximization. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6- 6-,0, 2015, Proceedings, Part 42. Springer, 318-330.
[9] Marwa EI Halabi, Federico Fusco, Ashkan Norouzi- Fardd Jakab Tardos, and Jakub Tamawski. 2023, Faimess in streaming submodular maximization over a matroid constraint. In International Conference on Machine Learning. PMLR, 9150-9171.
[10] Moran Feldman, Amin Karbasi, and Ehsan Kazemi. 2018. Do less, get more: Streaming submodular maximization with subsampling. Advances in Neural Information Processing Systems 31 (2018).
[11] Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. 2021. Streaming submodular maximization under matroid constraints. arXiv preprint arXiv:2107.07/88 183 (2021).
[12] Marshall I. Fisher, George I. Nemhauser, and Laurence A Wolsey. 1978. An analysis of approximations for maximizing submodular set functions-ll. Springer.
[13] Satoru Fujishige. 2005, Submodular functions and optimization. Vol. 58. Elsevier.
[14] Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. 2022. KuaiRec: A fbsly-observed dataset and insights for evaluating recommender systems. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 540-550.
[15] Michel Goemans and Jan Vondrák. 2006. Stochastic covering and adaptivity. In Latin American symposium on theoretical informatics. Springer, 532-543.
[16] Daniel Golovin and Andreas Krause. 2011. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42 (201 1), 427-486.
[17] Ryan Gomes and Andreas Krause. 2010. Budgeted Nonparametric Learning from Data Streams.. In ICML, Vol. Citeseer,
[18] Alkis Gotovos, Amin Karbasi, and Andreas Krause. 2015, Non-Monotone Adaptive Submodular Maximization. IJCAI. 1996-2003.
[19] Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh. 2008. Set covering with our eyes closed. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 347-356.
[20] Ran Haba, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. 2020. Streaming submodular maximization under a k-set system constraint. In International Conference on Machine Learning. PMLR, 3939-3949.
[21] Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. 2020. Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica 82, (2020), 1036-1032.
[22] Chien-Chung Huang, Theophile Thiery, and Justin Ward. 2021. Improved multi multi-pass pass stream- ing algorithms for submodular maximization with matroid constraints. arXiv preprint arXiv:2102.09679 (2021).
[23] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. 2019. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In International Conference on Machine Learning. PMLR, 3311-3320.
[24] David Kempe, Jon Kleinberg, and Evaa Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 137-146.
[25] Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 42, 8 (2009), 30-37.
[26] Andreas Krause and Daniel Golovin. 2014. Submodular function maximization. Tractability 71-104 (2014), 3.
11

---

[27] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 420-429.
[28] David D Lewis, Yiming Yang, Tony G Rose, and Fan Li. 2004. Rev1: A new benchmark collection for text categorization research. Journal of machine learning research 5, Apr (2004), 361-397.
[29] Yajing Liu, Edwin KP Chong, Ali Pezeshki, and Zhenliang Zhang. 2020. Submodular optimiza- tion problems and greedy strategies: A survey. Discrete Event Dynamic Systems 30, 3 (2020), 381-412.
[30] Julian McAuley and Jure Leskovee. 2013. Hidden factors and hidden topies: understanding rating dimensions with review text. In Proceedings of the 7th ACM conference on Recommender systems. 165-172.
[31] Julian McAuley, Jure Leskovee, and Dan Jurafsky. 2012. Learning attitudes and attributes from multi-aspect reviews. In 2012 IEEE 12th International Conference on Data Mining. IEEE, 1020-1025.
[32] Julian John McAuley and Jure Leskovec. 2013. From amateurs to connoisseurs: modeling the evolution of user expertise through online reviews. In Proceedings of the 22nd international conference on World Wide Web. 897-908.
[33] Anay Mehrotra and Nisheeth K Vishnoi. 2023. Maximizing submodular functions for rec- ommendation in the presence of biases. In Proceedings of the ACM Web Conference 2023. 3625-3636.
[34] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning. PMLR, 1358-1367.
[35] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. 2015. Lazier than lazy greedy. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 29.
[36] Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. 2018. Streaming non-monotone submodular maximization: Personalized video summarization the fly. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32.
[37] Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause, and Amin Karbasi. 2019. Adaptive sequence submodularity. Advances in Neural Information Processing Systems 32 (2019).
[38] Houssam Nassif. Kemal Oral Cansizlar, Mitchell Goodman, and SVN Vishwanathan. 2018. Diversifying music recommendations. arXiv preprint arXiv:1810.0145. (2018).
[39] George L Nemhauser, Laurence A Wolsey, and Marshall L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions Mathematical programming 14 (1978), 265-294.
[40] Naoto Ohsaka and Yuichi Yoshida. 2015. Monotone k-submodular function maximization with size constraints. Advances in Neural Information Processing Systems 28 (2015).
[41] Shaojie Tang and Jing Yuan. 2020. Adaptive cascade submodular maximization. arXiv preprint arXiv:2007.0m 035592 (2020).
[42] Kai Wei, Rishabh Iyer, and Jeff Bilmes. 2015. Submodularity in data subset selection and active learning. In International conference on machine learning. PMLR, 1954-1963.
[43] Qiong Wu, Yong Liu, Chunyan Miao, Yin Zhao, Lu Guan, and Haihong Tang. 2019. Recent advances in diversified recommendation. arXiv preprint prxXiv1905.0000
(2019). [44] Yisong Yue and Carlos Guestrin. 2011. Linear submodular bandits and their application to diversified retrieval. Advances in Neural Information Processing Systems 24 (2011).
[45] Ghahramani Zoubin. 2013. Scaling the indian buffet process via submodular maximization. In International Conference on Machine Learning. PMLR, 1013-1021.
12

---

Appendix
A Preliminaries
We use [i]. with j E denote the set ground set and Z is family of subsets of UT Definition A.1 (Matroid). A set system (U,Z) is matroid if
A set system a pair (U,Z), where is
(i e I,
(ïi) for B E I and any A B we have A I, and
(iii) if A E I, B I and |A] < [B, then there exists E B \ A such that AU {e) EI.
Definition A.2 (Partition matroid). A matroid M = (U,T) is partition matroid if there exists partition {E of i.e. - E, and E, E, for all j. and non-negative integers ki,..., ky, such that I = ( U: In E.l s for all [r]}.
A non-negatinn negative set function f: 2 - R> is called submodular if for all sets A S B CUU U and all elements
B, it is [ (et) J(A) 2 (e)) The function I monotone if for all A C B is S(A) < (BB). Let U be a finite ground set, and let f: 2 - Rz0 be monotone submodular set function. The constrained submodular maximization problem is to find maxser (SS), where I _ 2 represents the feasibility constraints.
For ease of notation, for any for A U B, A + e for A U (e}. A - B for A \ B, and A -- e for A {e). We write f(A B) and f(e B) for the incremental gain respectively defined as (AUBB) f(B) and f(A U (e]) f(A).
sets A U and S U, and any item U. we write + B
B Omitted proofs of Section 2
Lemma 2.1. f(S) is a non-decreasing submodular set function.
Proof. For any set S, we can rewrite Equation (1). Denote S = Uf and we allow multiple copies of Vi to appear S (the copies come from each St). Note that S is multi-set, and
S(S)
Σ j=1
II
II
(1 (1-pi) pi)
=
Σ
1
II
(1 (1-p)) pc)
[E[T] V
f=1
VESSVae,
Let (S) 1- 11 Ivve,, (1 p.). Then f(S) = ΣØ (S) To prove the lemma, it suffices to show that gj is non-decreasing and submodular for all j [d]
Non-decreasing property: For any X' y and for all [d]. it
g,(D)) - -)(()= (1- 1-
II
(1 Pi)
II
(1 - pi) 2 0.
V.XXVV
Submodularity: Let X C V. and let Z E y be an element not in y. Then, for all j E [d]. the following holds:
gj ( (2)) 9;(O)) 115(X (2)) (x(x
1-
II
(1 LL-pil pi)
II (1-p.)
-(1-
II (1-P:) V.((Z).eee)
II (1-p:)
ViEV.V:
ViEx.V
II
(1 (1-pi)
II
(1 (i-
II
(1 (1) S..
V,e(Z),V;3g
V.E.VV
13

---

Algorithm 3: LMGREEDY
Input: Budget K E E.
go, ,..... g 5 G. + 0. V2 t- 0,
for (V, T, p) in the stream do
V - Ve UU(
ifr . +- Ve
then
for j = to do
V +- arg vaX u
G* + G" U
N + No \V
10
output g
11
g g-gug y++1 + Vi t+t+l
12
13
Theorem 2.4. Algorithm for Problem 2.2 has competitive ratio of 1/2 space complexity O(N kT), time complexity (NNTk), and response time complexity O(Nk). Moreover, the competitive ratio of 1/2 is light, i.e., fee. for Problem 2.2, no streaming algorithm can achieve a competitive ratio better than 1/2 without violating the irrevocubility construint.
Proof. We first prove that Algorithm is 1/2 competitive for Problem 2.2.
Let O². ...... .." be the optimal output sets, and let ,-....... G be the output sets obtained by Algorithm 3. Since we treat each copy of the same item as a distinct item, it follows that for any i * j. O O and g n = @. We let G U g' and O U 0'. O³.
We prove that the following holds:
(a) f(0) & f(g) +
Σ f(V
()) ( f()) + Σ Σ l(
T
(2)
VEO
x=1 VEOii
2 (()) + Σ SV 9) < (G) + ΣΣ
T
(4)
J(V S(VI g')
Im VEO
Aml VEOL
j=1
Inequalities (a) and (d) holds by submodularity, (c) holds by monotonicity, and equality (b) holds because {0), O²'} form partition of O.
Next, we bound the final term of Equation (2). We denote O² (O). Ojj, and g (Gi, ..)) with Gj representing the j-th item that is added g' during the greedy selection steps. Note that, can assume 9 10| = k, because is monotone. The following holds
(a) flo
Σ f(V 1 VeOL
Σ flot U
Σ
U j=1
+
UG!
(3)
f=1
1=1
f(G U
U
U
f
U
j=1
where inequality (a) holds by submodularity, and inequality (b) holds by design of the greedy algorithm (Line 7 of Algorithm 3).
Combining Equation (2) and Equation (3) finishes the proof:
i-1
f(0) S f(9) + E - S (
(4)
j=1
#=1
14

---

Furthermore, we prove that the competitive ratio of 1/2 is tight for Problem 2.2.
Consider simple adversarial example with budget & = 1 and stream given by S O, (V2, 1), (Va, 1,)
where V1 = [ct, c2 and V/2 = c1). For any algorithm, if it selects s = [V1] as the first set to present, the adversary sets V3- {c1, 02). Conversely, if the algorithm selects S {V2), then the
adversary sets V/3 = {ca, c1).
In either case, the algorithm only cover two topics, while the optimal solution covers all four. Thus, the competitive ratio is at most 2 = 2. which completes the proof.
C Omitted proofs of Section 3
Before presenting the omitted proofs in Section 3, we provide a detailed description the reductions used in our analysis.
We begin by formally defining the streaming submodular maximization problem subject a partition matroid constraint (S2MM). Our definition adapts the streaming submodular maximization framework under p-matchoid constraint, as introduced by Chekuri et [8], and is stated as follows:
Problem C.1 (S2MM). Let M (S,I) be partition matroid and f submodular function. The elements of S are presented in a stream, and we order by order of appearance. The goal of the S2MM problem is to select a subset of items E I that maximizes [(A).
We demonstrate two types of reductions from an instance of S3MOR depending on whether we know the exact value of T. Algorithm I, as presented the main content, based on the second reduction, where only know upper bound T" of T.
instance of S2MM,
C.1 The case when the exact number of visits T is known
First, we show that the exact number of user visits T' is known, the S3MOR problem reduces to S2MM problem. Specifically, any streaming algorithm for S2MM that satisfies the irrevocable output requirement can solve S3MOR while maintaining the same competitive ratio. The irrevocable outpur requirement requires that the output subset for any partition becomes fixed irrevocably once all its items have appeared in the stream.
The reduction. Given an instance of the S3MOR problem, where the stream is given by
S = p), (VN,PN,TN) Tx)),
with a budget k, and the function f as defined in Equation (1), we can construct a corresponding instance of the S2MM problem.
Recall that 7i denotes the time step at which the user submits the f-th visit (with ru = 0), and V denotes copy of item Vú with copy identifier t. We use [| to denote the concatenation of streams. An instance of the S2MM problem with input stream S can be constructed as follows:
1. Let S.
- VP) for all / [T]. be specific,
S, Vi i
V 1-1 1+1 14-142
Ve
V
im
2. Let S = - S, be the concatenation of sub-streams S,,... ,T. i.e., S -S,,....,
3. Let Va = [V/ = (VI.... V.J.
4. Construct I in the following way: for any set C U V., if X X 14 & for all 1 < T, then X I.
15

---

S
vi
V
V
S2
v²:
V?
V2
V2
V2
ST
VT:
VT
VT
r141
VT
rr-1+1 1+1
VT
Figure 5: Illustration of the reduction when the exact number of visits T is known. The original with user accesses occurring at time steps r1, r1...., The constructed stream for the S2MM problem is S = UT_, S,
item stream for the S3MOR problem is (Vi,.., Vrr),
5. Let p P; denote copy of P; with copy identifier & [T]. Define f 2U2 V Rgo- Specifically, for any A S U V let A' = An Vs. Then, defined as follows:
f(AA) = 2=1
IIIII LETT V/EA',,
(1 (-P1))
(5)
and the goal of S2MM is to find A E I that maximizes f(A).
We observe that M (S, I), as defined above, forms partition matroid on the constructed stream S, with 5 = U Ve and V Nays Vi = 0. By construction, for each visit t E [T]. the partition Y contains exactly the set of items that arrived in the system before the 1-th user visit in the
S3MOR problem. Since the S2MM problem and the S3MOR problem share equivalent objective functions and equivalent constraints, conclude the following: for any optimal solution O E I of the S2MM problem, the sequence of subsets
Önv .... Ön VT
yields optimal output for the S3MOR problem each corresponding f-th user visit.
We can further conclude that any streaming algorithm achieving an a-competitive solution for the S2MM problem also yields a-competitive solution for the S3MOR problem. For this equivalence to hold, the streaming algorithm for S2MM must satisfy the irrevocable outpul requirement: for each partition D the stream, once the final item from this partition has arrived, the solution that belongs to this partition, An V", can no longer be changed. This requirement excludes algorithms like that of Feldman al. [11], whose solution set only becomes available after the stream terminates. In contrast, the algorithms proposed by Chakrabarti and Kale [7], Chekuri et al. [8], and Feldman et al. [10] are suitable. These three algorithms all meet the requirement while providing /4-competitive solutions for the S2MM problem.
C.2
The case when only an upper bound T" of available
Consider the where only upper bound 7' of the true number of user visits T is known. We prove the following: (1) An instance of the S2MM problem can be constructed such that any feasible solution the S2MM problem contains valid solution for the S3MOR problem. (2) Any streaming algorithm that solves the S2MM problem and satisfies the irrevocable output requirement can be adapted to solve the S3MOR problem, albeit with reduced competitive ratio. Specifically, the competitive ratio decays by factor of 1/(T" -T
In contrast to the reduction present in Appendix C.I, the construction of the stream for the S2MM problem depends on both the original stream S, and the algorithmic procedure described in Algorithm 1. We will prove that:
1. Algorithm I generates corresponding stream S for the S2MM problem
16

---

81
$2
9 14
V
V22
S3
V?
V2
V2
V
1/2 r211
V
P3
D
VP
V
V/3
V
V/3
m+
r2+1
C
V1
V
VT
V/8
V/8
1/6
V
V
F2+1
Figure 6: An example illustrating reduction when only an upper bound T of the true number of visits T is available. In this example, T and T' 5. The original item stream for the S3MOR problem given by (V1, V2...., V, with user visits occurring at time steps T1, 72, and r3. The constructed stream for the S2MM problem is S = Li S,, where $ = L Lines (Vi"), $2 = -.'++ Ll (V,)), and S; = -f L (V?"). Algorithm maintains and updates A' E Ee for all t [5] upon the arrival of each item in S. the visit time steps T1, T2, and r3, it outputs G AA, G A and g _42 respectively. By the end of the stream, the union U A' constitutes 1/4-competitive solution for the S2MM problem input S. The combined solution Ui G 3+1) competitive solution for the original S3MOR problem.
2. The candidate sets (At,... AT') maintained by Algorithm 1 forms solution to the S2MM problem; the output . J" of Algorithm forms a solution to the S3MOR problem.
By Algorithm line 13, we can construct bijective mapping x between the index sets of .g....., , and {A AT" }. This mapping satisfies the equality:
g' (1(1), for all [T].
7e (1,2, T"} denote the initial index set of all active candidate sets. For each é 2 1, let T represent the index set of active candidate sets before the t-th visit and after the (t - 1)-th visit.
The active index sets evolve follows:
[T]: T T {T))), and (2) for all / E + (": TT
(1) For all
The reduction.
1. We construct the stream for S2MM as follows
UAET (V19), for E [T], U (V,), for E (T + ,,..,, T)).
S.
2. Let S L S be the concatnation of $ ST.
3. Let p(t) π -t),,, and
3 { (V. (VT)T Join [V..... V
for E
(Vi.... V V.
for t T (T)))
4. Construct I in the following way: for any set X C T vi X X Dr $ le for all
1st5 T", then X E
17

---

5. Let ps = P: denote a copy of with copy identifier E [T'). The goal is to select
A = = A' I that maximizes (AA). The submodular function is given as follows:
E1-1111
d
f(A) = Σ j=1
1
-
II
II
(1-p5) p2)
(6)
4E[2 V. ETA, VVitn
Given the above construction,
verify that M (S,
is instance of partition matroid
defined on the constructed stream Š, with S = - V and V Niæs Vi = 0. By construction, the partitions ()((t) of S satisfy: (1) for each t [T]. ()((t) contains exactly the set of items that arrived before the I-th user visit in the S3MOR problem (2) The remaining T T partitions each contain the same set of items that arrived before the final user visit. The design ensures that each output G
satisfies G (((()) and | < k. for all E [T]. Consequently, the sequence G "²,...,,** constitutes feasible output for the S3MOR problem.
Following Algorithm 1, we conclude that for all t E [T'. we have A' S Ve with |A4l Consequently, the union U A' forms feasible solution the S2MM problem.
S k.
Since Algorithm essentially applies the streaming algorithm of Chekuri al. [8] to the constructed stream S, the solution U A' achieves a 1/ 1/4-approximation guarantee for the S2MM problem.
C.3 Omitted proofs
Theorem 3.1. Let T be the number of user accesses and T' a given upper bound. Algorithm has competitive ratio -TT1- space complexity OTT)k), time complexity O(NTT'), and response time complexity O )I"
Proof. Following the notations and conclusions we have in Appendix C.2, we are ready to prove Theorem 3.1. Let O1, p....... OT be the optimal solution for the S3MOR problem, and let Ô U Ót where O' = n Vr, denotes the optimal solution for the S2MM. We have
T
T-1
T-1
T-1
U = SU
A
+
AT(T))
(()
U
AT + UU Arll)
(0)
T-1 U AT(()) + f( U Ar(())
T-1
Σ
f(A$
-T-
SET (x())
1=1
1=1
T-1 U
T-1
Σ
S(A
(T)))
-+1
+1
SET (=(1))
t=1
(6) T U
1
A4)
1 4(T T 09) 4(T' T 1) o
1
where inequality (a) holds because by line 11 of Algorithm 1, that (T)) is selected with the largest marginal gain in terms of f(U (T()). Inequality (6) holds by submodularity. Inequality (c) holds because, as concluded in Appendix C.2, U A' achieves a 1/4-approximation guarantee for the S2MM problem. Finally, inequality (d) holds by contradiction: if f(U? O*) > fU O³). then there exists feasible solution for the S2MM problem where for all t E [T]. A' O and
regardless of the choice of -4*+1 AA,,, it holds that f(U A²) 2 SU" O9) > SU O³), which contradicts that Ô is optimal solution.
Complexity analysis. The space complexity in ((**k) because STORM only needs to maintain T" candidate sets of size k. Upon the arrival of each item, STORM makes T'k k oracle calls, thus the
18

---

time complexity is in (N) When user submit visit request, STORM selects one partition out of at most T" partitions and output it, thus the response time complexity is O(T)).
Tightness of our results. Note that the analysis in Equation (7) is tight. In the following, we show that for any value of T, which is only constant factor away from our analysis in Theorem 3.1.
construct stream such that STORM cannot do better than 7--441
To see this, consider an instance of the S3MOR problem with budget 1, the user visits one time at the end of the stream, and we have an estimated number of user visits T > 1, the stream is constructed as below:
S (((1), (12), 1,0). ((T"), (EL, .T,.,,,))
The (T"RM(T") algorithm outputs one of the first T" items and achieves expected topic coverage of value 1, while the optimal solution is to select the last item and obtain an expected coverage of value T". The competitive ratio in this instance is fo. while Alg. has competitive ratio .çT-
Note that for all possible numbers of user visits T and T > T, STORM cannot do better than TV T4- For example, when T = 2, we can construct a sub-stream S₂ as follows
construct stream such that
S ((IT' + +,,7 + 2),1,0), .. ((2T' - 1, 1,)) ((T' + +1.....33" ,37' 1,
By concatenating S1 and S2, we obtain new stream where the user visits for 2 times. With budget k = 1, STORM(T") achieves an expected coverage 3, while the optimal expected coverage 3 - 1). leading to competitive ratio of -- with again 1/4 factor away from 4(T'-++1) --1 We can repeat this process such that for any T, we can construct a stream such that the competitive ratio is equal to T T+-
Lemma C.2. Let be the number of user accesses and T' be a given upper bound. Algorithm generates set of guesses T as P {ōi i [[T"//]]], Let T be the smallest integer in P that larger than or equal to T. Let G' g'.... , be the output of STORM(T") ). and let B .... BT be the oulput of Algorithm then it holds that
T
T g +
T-1 I[UBBI
L+1
fU Ba)
2
B' U
(8)
t=1
Proof. We prove Equation (8) via induction.
When T 1, according to line 7 of Algorithm 2 that B is chosen with the largest marginal gain, holds that f(B 2 )(
The base case for the induction starts from T 2. is
(a)
f(B B
B²) 2 f(g)) ) f(g |B²)
f(g' [ + f(g B\)
( 1B) -(B'' ( + f(g² B²)
- f(g)) ug² ((B)) f(BB (
f(B .''."""')))) f(B") g
-(g).g") S(B' g - gt)),
where inequality (a) holds because f(B)) 2 f(G') and f(B² B') f(g2 BB).
Inequality (b)
holds by submodularity.
We then prove the induction step. Assume for T j. it holds
- Σ 1
H+
(9)
-=1
=1
==1
s=1
19

---

We can use o to represent the second term in Equation (9), i.e., f(Ul=1 B*) 2 9') we can then show that for T + 1 holds
j+1 f(Bit) UB) + BUB)
f( B²)
-
f(g U B¹) +
t=1
U -(B) ~ 3
U
B U + right L +
=
t=1
t=1
t 1=1
jtl
xU
1 fU U
1=1
Σ
U f ( BD U
a=l -=1
s=1
s=1
Here, inequality (a) holds by the induction assumption, and (b) holds by submodularity. This completes the induction.
Lemma C.3. Let T be the number of user accesses and T' be given upper bound. Algorithm
generates a set of guesses Tf as P {ōi i [[T"/=]]] Let T be the smallest integer in P that larger than or equal T. Let G G be the output of STORM(T") ), and let B² B²...., 33" be
the oulput of Algorithm It holds that
イレ f 1=1
(10)
Proof. Lemma C.3 is a direct result of Lemma C.2, as we can show that
H+1 U - f(U Ba U 2 fUB)
T
Σ E B
By.
To prove that the above inequality holds, we proceed to show that
Σ
rÜB B²
U
B. + شÚ
اΦف s rÙ
==1
s=1
==1
20

---

Indeed, it is
H+1
Σ B
U
U
(II)
H+1
= Σ
T-2
H+
1+1
T-1
= f(BB ( +
8 f
U gr)
-
ff
B
وو
8=1
==1
1=1
8=1
==1
SB(B) +
8
U
8
( 9a)
8=1
H1
H+1
1-
f(B))
-
f ~)
B
= f(B)) + Σ
T-2 Σ
f(B+t
UB
+
Ug) f(B)) +
f(B
UB)
==1
==1
a=1
T-1 =
(12)
t=1
t=1
Combining Equation (12) with Equation (8), obtain Equation (10).
Theorem 3.2. Algorithm 2 has competitive ratio of 1/(56), space complexity O(T k/T k/8), time /0), and response time complexity O(T").
complexity 2
Proof. Let T be the smallest integer in p= {ōi E [T/}]] that larger than equal to T. Let g!.... G be the output of STORM(T")
Observe that T < T 8 - 1, otherwise we can set T as T 5 and it is still an upper bound of T.
By Theorem 3.1, it holds that
T s U 4(T - +1) =1
U 4 SUo) 1=1
(13)
1=1
Combining Equation (13) with Lemma C.3, conclude that
T f(
B fU t=1
(())) 85 S(J)
(14)
Since STORM++ maintains [T/ copies of STORM, each copy of STORM has time complexity in ONNTT" and space complexity (T*k)), the space complexity for the STORM++ is k/8)) and the time complexity is ((N /8). When a user submits a visit request, each copy of STORM
selects one partition out of most 7" partitions as candidate result set, then STORM+ selects the best set among T' /a candidates as output. Thus, the response time of STORM++ is O(T)).
O
D Additional content for Section
D.1 Dataset and experimental setting
We use the following six datasets:
21

---

KuaiRec [14]: Recommendation logs from a video-sharing mobile app, containing metadata such as each video's 's categories and watch ratio. We use the watch ratio, computed as the user's viewing time divided by the video's duration, as the user rating score. The dataset includes 043 videos across 100 categories.
Anime: A dataset of animation ratings in the range [1, 10). consisting of 7745 animation
items across 43 genres.
Beer:* This dataset contains BeerAdvocate reviews [32, 31], along with categorical attributes for each beer. After filtering out beers and reviewers with fewer than 10 reviews, the final dataset includes 9 000 beers across 70 categories.
Yahoo: A music rating dataset with ratings in the range [1, 5]. After filtering out users with fewer than 20 ratings, the dataset includes 136 736 songs across 58 genres.
RCV1 [28]: multi-label dataset, each item news story from Reuters, Ltd. for research use. We sample 462 225 stories across 476 unique labels.
Amazon [30]] A multi-label dataset consisting of 117 006 Amazon products over 3 750 unique labels. This dataset is subset of the publicly available dataset.
Experimental setting To obtain the click probabilities for each item, we generate them uniformly at random in the range [0, 0.2] for the RCVI and Amazon datasets. For the four item-rating datasets, we estimate click probabilities by computing a low-rank completion
the user-item rating matrix using matrix factorization [25]. This yields latent feature vectors wn, for each user u and em for each item m, where the inner product w,, Um approximates user u rating for item m. We then apply standard min-max normalization to the predicted ratings and linearly scale the results to the range [0, 0.5) to obtain click probabilities. We set the latent feature dimension to 15 for the KuaiRec dataset, and to 20 for the remaining three rating datasets. While click probability ranges vary in real-world scenarios, where larger ranges can lead to faster convergence toward the maximum expected coverage value, we intentionally set the probabilities to be small in our experiments. This allows us to observe performance changes over a wider range of parameter settings.
Implementation To enhance the computational efficiency of the LMGREEDY algorithm (described in Algorithm 3), we implement lines 6-9 using the STOCHASTIC-GREEDY approach introduced by Mirzasoleiman al. [35]. For the implementations of STORM and STORM++, incorporate the sampling technique from Feldman et al. [10]. Specifically, when adding each item (with potential replacement) each candidate set, ignore it with probability 2/3.
D.2 Omitted results
In this section, we present additional experimental results and analyses. Specifically, we show how the expected coverage changes as the budget &s varies in Figure 7, and as the number of user visits T varies in Figure 8. The standard deviation of the expected coverage, as & and T are varied, is reported in Figure 10 and Figure 11, respectively. Finally, we present the effect of varying and AT on the expected coverage in Figure 9.
Why STORM+ and STORM(T') outperform STORM(T)? We present simple ex- ample where STORM(T)) outperforms STORM(T). Consider the input stream S = 1,0), 112), 1), (13, 4) 0.9, 1), ((5, 6), 1, 1)) with budget A: = and actual number of visits = 2. The algorithm STORM(2) selects either {1} or (2) for the first visit, and {5, 6} for the second, achieving expected coverage of 3.
If we overestimate the visits and set 7" 3. STORM(3) instead selects {3, 4} first and (5, 6} second, yielding an expected coverage of 3.8, which is higher than when the number of visits is known exactly. Likewise, STORM++ with T' and 8 3 matches (3)RM(3), and achieves the same coverage of 3.8.
This example shows that while (TORM(T) has the strongest theoretical guarantee, STORM(T") and STORM++ can outperform it empirically, which explains the trends observed in our experiments.
'https://www. kaggle. watgglee.cm/daaaaaeee www//attasets//oooeeooooooooooe 'nttpa://cseveb ucsd, edu/ htt////mmnllyydaaaaeeeeaa html
wtw.///iiieeeeeooeaeaaiiiiiiioii database
'tttps://wescoop, sandbox, yahoo, cww/ catalog. pap"datatype-
22

---

S -e Storm(T) + StormIT)
UMGreedy
Preemption -E- S
Expeeted: Coverage
Expected Coverage
30
Exppertedd Coverage
24
45
30-
18-
15.
12-
12
18
21
24
27
30
9
12
18
21
24
27
30
6
12
15
18
21
24
27
30
(a) KuaiRec
(b) Anime
(c) Beer
Figure Empirical variation in expected coverage as function of budget on three smaller datasets. Parameter T = 5, 8 = 25 and AT = 45 are fixed
Expeted Coverage
Expected Coverage
40
Expected Coverage
100
80
32
40
24
25
20
30
90100
T
T
(a) KuaiRec
(b) Anime
(c)
Figure 8: Empirical variation in expected coverage as a function of number of visits T on three
smaller datasets. Parameter 10, 10 and AT 10 are fixed.
Starmi++ + Starm[T) + Storm/T)
LMGreedy
Preemption -
Sieve++
Expected Coverage
160
BCVI
Coverage
150
140
130
120
115
Expecter
110
7..5
16
Yahoo
Yahoo
15.0
15
30
10
30
50
70
100
5
AT
(a)
(b)
Figure 9: Impact of AT' and 8 on expected coverage on three larger datasets. In (a) and (b), we fix
k = 5 and T = 10. When varying 6, we fix AT 60; when varying AT, we fix 8 = 10.
23

---

Starm++ Storm(T)
Sterm(T)
LMGreedy
Preemption -B- Sieve+=
20
SD Coverage
SD Coverage
3.0
SD Coverrage
155
2.01
10-
5-
21
30
18
27
(a) KuaiRee
(b) Anime
Beer
7.5
32
Coverage
6.0
50 Coverage
SD CCooeragg
4.5
6.0
24
16
60
1.5
8-
100
140
k
(d) Yahoo
(c) RCV1
(f)
Amazon
Figure 10: Empirical variation in standard deviation for the expected coverage as function of budget l all datasets. Parameter T
25 and AT 45 fixed.
Stom++ Storm(T)
Storm(T)
LMGreedy
Preemption
Sieve+
4.0
SD of Coverage
SD Coverage
SD Coverage
20
2.1
2.4
155
1.6-
10-
6-
50 60 70
90100
40
50
60
90100
10
10
50
60
70 900
(a) KuaiRec
(b) Anime
Beer
10.5
6.0
Coverage
Coverege
6.0
SD Coverage
9.0
4.5
7.5
4.5
1.5
3.0
4.5
10
50
60
70
90100
15
25
30
35
40
15
20
(d) Yahoo
(c) RCVI
( Amazon
Figure 11: Empirical variation in standard deviation for the expected coverage as function of the number of user visits T on all datasets. Parameter i 10, 8 10 and AT 10 are fixed.
24

---

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:
We included the important assumptions and main contrubutions made in the
paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide (1) competitive upper bound for our problem in Theorem 2.4 (2) worst case competitive ratio upper bound for the proposed Algorithm paragraph of Section 3.1 (3) memory and time complexity of the proposed algorithms (4) justification of why we need to assume the visit estimate T" to be larger than the actual number of visit T in the beginning of Section 3 (5) parameter studies in the experimental section.
the large
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
25

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We put the proofs for most theoretical results in the appendix to be found in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
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 it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide clear experimental setting in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
26

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide a link to our code and data in Section (the last sentence).
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ Setiiiddee/ooeeSumiisssiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: (CodeSubmisssonnPP
/ /nips. wtnppsccpppuliiiieeeeeeaatpppppp http:pulllcggggcee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: 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 to understand the results?
Answer: [Yes]
Justification: The experimental setting explains how simulate the main setting of paper to the level of detail that necessary to undertand the results and make sense of them. Full details are provided in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
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: We provide the standard deviation on the expected coverage value and oracle calls across all users in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
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 reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report this in the last paragraph of Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: : hww.rpsu....//.. cats..cc/poo Dpppblic/Ethissuiieine
Answer: [Yes]
Justification:
All user information in the source data has been anonymized.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
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 discuss both potential positive societal impacts and negative societal impacts in Section 5,
Guidelines:
The answer NA means that there is no societal impact of the work performed.
28

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: All datasets use are publically available, and our proposed models do not pose high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
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:
We provide proper citations to all datasets and baselines we use.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
29

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We release the code for our proposed algorithms via an anonymized URL..
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
30

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is 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.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ /ttps/////eeu..eeeeeee ceturips..ccCoofeeeeneeeee cc//omfferences//225////. for what should or should be described.
31


Reviews:
[{"review_id": "6npQTdyQ8i", "reviewer": "Reviewer_9boZ", "summary": "This work introduces and studies a new problem in streaming submodular maximization, called Streaming Stochastic Submodular Maximization with On-demand Requests, or S3MOR in short. This problem is motivated by the setting of wanting to diversify the news feed of a user, where the news coverage goes up only if the user actually clicks on an item. Formally, there is a stream $\\mathcal{V} = \\{V_1,\\dots,\\}$ of news items, and each item $V_i$ covers a subset of topics from a given universe of topics $C = \\{c_1,\\dots,c_d\\}$. The problem solver is given each news item tagged with a value $p_i$ that is the probability that the item will be clicked on. Further, at every time step $i$, a binary variable $\\tau_i \\in \\{0,1\\}$ is observed indicating whether or not the user of interest is online or not; if $\\tau_i = 1$ then the solver must pick some at most $k$ items from $\\{V_1,\\dots,V_i\\}$ to maximize the topic coverage for the user. The quality of the solvers algorithm is measured as the expected number of topics covered over the course of the stream.\n\nAfter introducing this problem, the authors establish a baseline by showing that this can be reduced to submodular maximization under a partition matroid constraint, and so by storing the entire data stream and applying a batch algorithm, they achieve a $1/2$ approximation - they call this algorithm LMGreedy. It is known that it is not possible to achieve better than a $1/2$ approximation in the worst case setting for streaming submodular maximization, but the downside of LMGreedy is its high memory usage.\n\nSo as to address this issue, the authors construct memory efficient streaming algorithms. One technical issue they come across is that their first method (STORM) achieves a good approximation of $1/4$ only when the number of visits made by the user is known in advance, and degrades reciprocally with the gap between the known upper bound on the number of visits and the number of visits actually made. To address this, they adopt an adaptive approach where they initialize a sequence of guesses for the number of visits by the users and adapt to the sequence. This allows them to interpolate smoothly by achieving an approximation factor of $1/8\\delta$ for any fixed parameter $\\delta\\in\\mathbb{N}$, and achieve space complexity $O(T'^2k/\\delta)$ and time complexity $O(NkT'^2/\\delta)$, where $T'$ is the actual number of times the user visits.\n\nFinally, the authors conduct some experiments demonstrating that their methods do indeed allow one to trade off coverage and space/time complexity effectively.", "questions": "1. Could you please address what I've written in the Weaknesses section above?\n2. In your experiments, how did you generate your $p_i$ values to run your experiments?", "limitations": "I think I've address any issues I have with limitations above in the Weaknesses section.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and easy to understand.\n2. The treatment of the problem is comprehensive with reasonable theoretical results and experimental corroboration.\n\nWeaknesses:\n1. I think this work is reasonably interesting but maybe not very novel. Based on the problem description and the technical description, although S3MOR seems reasonably posed there are some aspects of the problem description which needs more elaboration. Why is it reasonable to assume we have a clean probability tag for each item, and how would this perform under misspecification? How does this compare to other algorithms in the streaming submodular maximization literature which maybe don't exactly match this problem description but can perhaps still be applied?", "was_revised": true, "final_justification": "I have kept my score as is (a 3, slightly below the acceptance threshold) - I think my biggest concern is the novelty and impact of this work. While this is a good work, I don't think it meets the bar for NeurIPS.", "rebuttal": "We are thankful to the reviewer for their feedback of our paper:\n\n### Q1. Why is it reasonable to assume we have a clean probability tag for each item, and how would this perform under misspecification?\n\nThank you for your question! Could you please clarify what you mean by a **\"clean probability tag\"?**\n\n1. **If you mean why we can assume these probabilities are provided:**\n\n   These probabilities can be interpreted as the user's preference for certain items. Many machine learning and deep learning models are capable of estimating such preferences. We can treat these models as black boxes to generate the probability $p_i$ required by our algorithm.\n\n   For instance, the Probabilistic Matrix Factorization (PMF [1]) model approximates the user-item preference matrix as the product of two low-rank matrices—one for users and one for items. Additionally, Wang et al. [2] proposed a supervised machine learning model that learns personalized, contextualized, and real-time probabilities representing the likelihood that a user $i$ has intent $v$ for an item on the current recommendation page.\n\n   It is worth noting that our algorithm incorporates the scenario where multiple copies of the same news item may appear at different positions in the news stream. \n   Each copy of the news item can be assigned a different probability. \n   This corresponds to the case where the user may be presented with the same news item multiple times, and the user accesses it each time with different probabilities. \n   \n  \n\n2. **If you mean why the probabilities for an item are static, but not, for instance, time-dependent:**\n\n   \n\n   STORM++ cannot handle dynamic probabilities—i.e., probabilities that change over time. \n   \n   Recall that STORM always prepares what to present to the users in advance in *partitions*, and decides on the fly whether to add the news item to each partition or not whenever the algorithm processes a new news item.\n   Whenever the user visits the system, the algorithm presents one partition to the user.\n\n   Hereby, as user visit times are uncertain, it is infeasible to predetermine probabilities for each partition when computing topic coverage. Furthermore, STORM selects the optimal partition at each request, making it even more challenging to preassign dynamic probabilities.\n   However, this is a very interesting future work direction, and we appreciate you for pointing it out.\n\n\n### Q2. How does this compare to other algorithms in the streaming submodular maximization literature that may not exactly match this problem but could potentially be applied?\n\n\n\nBelow, we list three different aspects that make our problem different. \nThe major differences between our problem and other streaming submodular maximization problems arise from the fact that we incorporate an online setting, which are detailed in (b) and (c), and we provide more explanations in the following paragraphs.  \n\n\n- **(a) Uncertainty of whether user accesses the recommended items:** Each copy of the news item is assigned a probability indicating the likelihood that the user will access it when presented to the user.  \n\n- **(b) Users' visit times are unknown:** Users may access the system at any time, and the system does not know in advance when or how many times each user will visit.\n\n- **(c) The system provides fast response:** At each user's request, the system returns a result set of size at most $k$, and the system's response should be fast.\n\nIn other words, the algorithm must always be prepared to produce results at any point during the processing of the stream. This requirement distinguishes our setting from traditional streaming submodular maximization problems (as in [3,4]), where the algorithm is only required to output a result at the end of the stream.\n\nIn certain special cases, specifically (i) when the algorithm has access to all items at all times (as discussed in Section 2), or (ii) when the exact number of user visits $T$ is known in advance (as described in Section 3.1), we can reduce our problem to submodular maximization under matroid constraints. However, we emphasize that these reductions are *non-trivial* and require the construction of *new streams* for analytical purposes, as demonstrated in Appendix C of the supplementary material.\n\nIn the general case, where only an upper bound on $T$ is known, such reductions no longer apply. In this setting, we must develop entirely new algorithmic strategies, as outlined in Section 3.2.\n\n\n\n### Q3. In your experiments, how did you generate your $p_i$ values?\n\nWe explain how we generate probabilities in Appendix D.1. For the four item-rating datasets, we estimate click probabilities $p_i$ by performing low-rank matrix factorization on the user-item rating matrix. This yields latent vectors $w_u$ (user) and $v_m$ (item), and their inner product $w_u^\\top v_m$ approximates user $u$’s rating of item $m$. We then apply min-max normalization to these predicted ratings to obtain click probabilities. For the RCV1 and Amazon datasets, we sample $p_i$ uniformly at random from the range $[0, 0.2]$.\n\nWe would like to mention that, in the literature, paper [5] employs a similar approach to generate probabilities.\n\n\n\n\n> [1] Mnih A, Salakhutdinov RR. Probabilistic matrix factorization. Advances in neural information processing systems. 2007;20.\n\n> [2] Wang Y, Banerjee C, Chucri S, Soldo F, Badam S, Chi EH, Chen M. Beyond item dissimilarities: Diversifying by intent in recommender systems. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1 2025 Jul 20 (pp. 2672-2681).\n\n>[3] Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A. Streaming submodular maximization: Massive data summarization on the fly. InProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining 2014 Aug 24 (pp. 671-680).\n\n>[4] Chekuri C, Gupta S, Quanrud K. Streaming algorithms for submodular function maximization. In International Colloquium on Automata, Languages, and Programming 2015 Jun 20 (pp. 318-330). Berlin, Heidelberg: Springer Berlin Heidelberg.\n\n> [5] Wang, H., Tu, S., & Gionis, A. (2025, March). Sequential Diversification with Provable Guarantees. Proceedings of the 18th ACM International Conference on Web Search and Data Mining, pp. 345–353."}, {"review_id": "cb8vyuZI76", "reviewer": "Reviewer_XZhc", "summary": "The paper introduces the steaming stochastic submodular maximization with on-demand requests (S3MOR) problem, motivated by online news recommendation systems. The goal is to select $T$ news sets (corresponding to $T$ user visits) that maximize the expected number of topics covered. This problme is further formalized as monotone submodular maximization problem under a matroid constraint.\n\nThe main contribution are three approximation algorithms:\n- Given sufficient memory, a 1/2-approximation algorithm is proposed with $\\Omega(N+kT)$ memory usage and  $O(NTk)$ running time.\n- To improve the memory usage, a $\\frac{1}{4(T'-T+1)}$-approxiamtion algorithm is proposed with $O(T'k)$ memory usage and  $O(NT'k)$ running time, where $T'$ is a given upper bound to the number of user accesses $T$.\n- To further achieve a constant approximation ratio, a $1/(8\\delta)$-approximation algorithm is proposed with $O(T'^2k/\\delta)$ memory usage and  $O(NT'^2k/delta)$ running time.\n\nThe empirical evaluation shows the proposed algorithms consistently outperform the baselines regarding function value, runtime and memory.", "questions": "- Line 16: The range of $\\delta$ should be provided. Otherwise, it could be misleading that the approximation ratio could be better than $1/8$. Also, add parenthesis as $1/(8\\delta)$\n- Table 1: On line 182, it is discussed that the memory usage of LMGreedy is $\\Omega(N+kT)$. However, it is listed as $O(N+kT)$ in the table.\n- Line 224: Does $f_{\\cup_{t\\in [T']} \\mathcal A^t}(V_j)$ represents the marginal gain?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper introduces an interesting online setting for streaming submodular maximization problems, capturing real-world challenges in online news recommendations. It models the goal of maximizing topic coverage while adapting to dynamic user visits, making it applicable to recommendation systems that aim to diversify content exposure. \n- The authors propose three progressively refined approximation algorithms with different trade-offs between accuracy and memory efficiency. \n- The paper includes extensive experiments on six real-world datasets, validating the effectiveness of the proposed methods. The results demonstrate that the algorithms outperform baselines in terms of objective value (topic coverage), runtime efficiency, and memory consumption.\n- The paper is well-structured and clearly written, making it accessible to readers.\nThe logical flow from problem formulation to theoretical analysis and empirical evaluation enhances readability.\n\nWeaknesses\n- The probability $p_i$ that the user clicks an item $i$ is not clearly explained before the formal problem definition (Problem 2.2). It remains unclear whether click probabilities remain static or evolve based on user behavior over time.\n- The paper does not discuss how to estimate the total number of user visits $T$. Under the streaming setting, the predefined $T'$ sets may become insufficient if users continue visiting beyond expectations. The experimental setup assumes prior knowledge of T, which may not be realistic. The author may need to either add a discussion on how to guess $T$ and implement it in the experiment or add an assumption to $T$.", "was_revised": true, "final_justification": "I have read the rebuttal and other reviews. I will keep my score.", "rebuttal": "We are thankful for the reviewer's valuable feedback.\n\n### Q1. It remains unclear whether click probabilities remain static or evolve based on user behavior over time.\n\nPlease refer to our response to Reviewer 9b0Z (Question 1) for how we set probabilities.\n\n### Q2. The paper does not discuss how to estimate the total number of user visits $T'$\n\nWe assume $T$ represents the number of times a user visits the system per day, which is typically small. We could estimate $T$ by either directly asking the user or analyzing their behavior. Once we have an estimate, we can set $T'$ close enough to $T$, for example, $T' \\approx 1.1T$.\n\nWe always assume $T' > T$. This is because we want to pre-allocate a memory space for each user, and the memory depends on $T$. If we assume the user will visit $T'$ times, we set the memory to be $T'k$. If $T' < T$, any algorithm cannot perform well, as we explained in lines 192-199.\n\n### Line 16\nThank you for pointing this out. In line 147, we mention $\\delta \\in \\mathbb{N}$. We will clarify in Theorem 3.2 that $\\delta$ is a positive integer.\n### Table 1\nThank you for catching the typo. It should be $\\Theta(N + kT)$ both in line 182 and in the table. We will revise it in the next version.\n### Line 224\nYes, this represents the marginal gain. We will clarify this in the next revision of the paper."}, {"review_id": "GGdpkd9ktT", "reviewer": "Reviewer_87n5", "summary": "This paper investigates a novel variant of the streaming submodular maximization problem. The authors consider a setting in which users may visit a news website at any time, and upon each visit, the website must display up to $k$ news items. Each news item covers a subset of topics and has a certain probability of being clicked by the user. The objective is to design a streaming algorithm that maximizes the expected total topic coverage. To address this, the authors draw a connection to submodular maximization under a matroid constraint.", "questions": "Please see weakness section for my concerns regarding both the problem setting and technical contribution.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper introduces a new variant of the streaming submodular maximization problem and proposes memory- and time-efficient algorithms to address it. However, I have several concerns about both the problem setting and the technical contributions:\n\n1. The paper uses news recommendation as a motivating example, focusing on the development of memory-efficient online algorithms that avoid storing all incoming news items. While this may be reasonable for serving a single user, real-world news platforms typically serve a large number of users. To provide near-optimal recommendations across all users, storing all news items may still be necessary. For instance, if the proposed algorithm is applied independently to each user, the union of the candidate sets across all users could approximate the full set of news items, especially given users' diverse preferences. This observation challenges the practicality of the memory savings claimed by the authors.\n\n2. It is unclear what concrete advantages the proposed algorithms offer over existing methods such as LMGreedy. In particular, the memory requirement of their algorithm depends on $T'$, an upper bound on $T$ (the number of visits). In the worst case, $T'$ could be as large as $N$, the total number of news items. In such scenarios, the proposed method may offer little to no improvement over baseline approaches—unless it is shown to be robust to inaccurate estimates of $T$, which is not thoroughly addressed in the paper.", "was_revised": true, "final_justification": "My concern regarding the necessity of storing all news items remains.", "rebuttal": "We are thankful to the reviewer for their insightful comments.\n\n### Q1 . The paper uses news recommendation as a motivating example, focusing on the development of memory efficient online algorithms that avoid storing all incoming news items. While this may be reasonable for serving a single user, real-world news platforms typically serve a large number of users. To provide near optimal recommendations across all users, storing all news items may still be necessary. For instance, if the proposed algorithm is applied independently to each user, the union of the candidate sets across all users could approximate the full set of news items, especially given users’ diverse preferences. This observation challenges the practicality of the memory savings claimed by the authors.\n\nThank you for your great question!\n\nIn the paper, we primarily consider memory usage for a single user and did not address the case of multiple users. It turns out that even with multiple users, **STORM** still uses less memory than **LMGreedy**.\n\nTo compare their memory usage, let's assume that for both STORM and LMGreedy, memory usage consists of two components:\n\n1. **Common storage**: Shared by all users, storing all incoming news documents from the stream.\n2. **Per-user storage**: Allocated individually for each user, storing document identifiers and user-item click probabilities.\n\nThe common storage is the same for both algorithms, so we only analyze the per-user storage.\nLet $N$ denote the length of the stream.\n\n### STORM\n\nFor each user, STORM requires memory $\\mathcal{O}(T'k)$, since we store:\n- $T'k$ document identifiers, and\n- $T'k$ associated probabilities.\n\n### LMGreedy\n\nFor each user, LMGreedy requires memory $\\mathcal{O}(N + Tk)$, because we store:\n- $Tk$ document identifiers, and\n- $N$ probabilities (one for each document in the stream).\n\nAssuming each document identifier and each probability takes one unit of memory, and given $m$ users, the total **per-user memory** usage is:\n\n- **STORM**: $\\mathcal{O}(mT'k)$  \n- **LMGreedy**: $\\mathcal{O}(m(N + Tk))$\n- **STORM++**: $\\mathcal{O}\\left(\\frac{m{T'}^2 k }{\\delta}\\right)$\n\nWhen $kT'<<N$, STORM becomes significantly more memory-efficient than LMGreedy. When \n$(k{T'}^2)/\\delta<<N$，STORM++ is more memory-efficient than LMGreedy. \nIn practice, $T$ (number of visits per day) is typically small, if we consider, e.g., the average number of user visits versus the number of new Reddit posts (or YouTube videos) each day. \n\n### Q2. It is unclear what concrete advantages the proposed algorithms offer over existing methods such as LMGreedy. In particular, the memory requirement of their algorithm depends on $T'$, an upper bound on $T$ (the number of visits). In the worst case, $T'$ could be as large as $N$, the total number of news items. In such scenarios, the proposed method may offer little to no improvement over baseline approaches—unless it is shown to be robust to inaccurate estimates of , which is not thoroughly addressed in the paper.\n\nThe key advantage of STORM++ over LMGreedy lies in its faster response time. STORM always maintains a set of $T'$ candidate solutions. Upon receiving a user request, STORM returns the best solution among these candidates. Building on this, STORM++ selects the best guess from $\\frac{T'}{\\delta}$ candidates and presents it to the user. This process incurs a maximum computational cost of $\\mathcal{O}(T'k)$.\n\nIn contrast, LMGreedy does not maintain intermediate results. Upon request, the algorithm iterates all existing items and greedily selects the top $k$ items. This procedure takes at least $\\Omega(Nk)$ time.\n\nWe assume that $T'$, an estimate of $T$, is reasonably accurate and $T'<<N$. \nIn practice, $T$ (number of visits per day) is typically small, and $T$ can be inferred by directly asking the user or by analyzing their daily interaction patterns."}, {"review_id": "TC2DFcCwAw", "reviewer": "Reviewer_whBa", "summary": "This paper aims at a  streaming submodular maximization.  The context is that a user can visit a site and the site needs to present k distinct items to the users. These items will be consumed with a fixed probability (per item) which each item represents some topics. The goal is to design a streaming algorithm that maximizes the expected total topic coverage. \n\nThe authors show that this problem can be formulated as a submodular maximization subject to a matroid constraint under an ideal case:   the number of user visits is known in advance or linear-size memory in the stream length is available.\n\nTo do away from these assumptions, the authors proposed another streaming algorithm that achieves a competitive ratio of 1/8\\delta, where \\delta controls the approximation quality.", "questions": "Overall, it is a piece of work that introduces a good approximation algorithm, and it has performance guarantees.\n\nI enjoy reading the paper.", "limitations": "N.A.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The strength of this paper is in discovering the \"connection\" with the submodular maximization.\n\nThe authors also provide a cute approximation algorithm which can achieve 1/8\\delta, competitive ratio.\n\nThe presentation, in particular, on Section 3, can be improved since there are a lot of claims that need formal proof but I guess it is due to the page limit that the authors didn't put the proof in the main text.\n\nOverall, I enjoy reading the paper.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! We will improve the presentation and clarity in the next version."}]

Author rebuttal:

Meta-review: This paper investigates a novel variant of the streaming submodular maximization problem. The authors consider a setting in which users may visit a news website at any time, and upon each visit, the website must display up to k  news items. Each news item covers a subset of topics and has a certain probability of being clicked by the user. The objective is to design a streaming algorithm that maximizes the expected total topic coverage. To address this, the authors draw a connection to submodular maximization under a matroid constraint.

All reviewers agree that the paper is well-written and the treatment of the problem is adequately deep. Still there are some minor issue that limit in some way the impact of the paper: (i) it is not clear how the probabilities are provided in a recommendation system; (ii) it is limiting to think about single-user recommendations.

Anyway, the work's merits outweigh these issues, and the paper can foster more research addressing them. For this reason, we suggest acceptance.
Decision: Accept (poster)