Streaming Stochastic Submodular Maximization with On-Demand User Requests

Thank you for your comments! We will improve the presentation and clarity in the next version.

I read the review and I am ok with it. I will keep my score.

We are thankful to the reviewer for their insightful comments.

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.

Thank you for your great question!

In 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.

To compare their memory usage, let's assume that for both STORM and LMGreedy, memory usage consists of two components:

1. Common storage: Shared by all users, storing all incoming news documents from the stream.
2. Per-user storage: Allocated individually for each user, storing document identifiers and user-item click probabilities.

The common storage is the same for both algorithms, so we only analyze the per-user storage. Let $N$ denote the length of the stream.

STORM

For each user, STORM requires memory $\mathcal{O}(T'k)$, since we store:

• $T'k$ document identifiers, and
• $T'k$ associated probabilities.

LMGreedy

For each user, LMGreedy requires memory $\mathcal{O}(N + Tk)$, because we store:

• $Tk$ document identifiers, and
• $N$ probabilities (one for each document in the stream).

Assuming each document identifier and each probability takes one unit of memory, and given $m$ users, the total per-user memory usage is:

• STORM: $\mathcal{O}(mT'k)$
• LMGreedy: $\mathcal{O}(m(N + Tk))$
• STORM++: $\mathcal{O}\left(\frac{m{T'}^2 k }{\delta}\right)$

When $kT'<<N$, STORM becomes significantly more memory-efficient than LMGreedy. When $(k{T'}^2)/\delta<<N$，STORM++ is more memory-efficient than LMGreedy. In 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.

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.

The 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)$.

In 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.

We assume that $T'$, an estimate of $T$, is reasonably accurate and $T'<<N$. In 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.

Thank you for your review. We’d appreciate it if you could share whether our response resolved your concerns, or if there’s anything else you'd like us to address. We’re happy to clarify further if needed.

We are thankful for the reviewer's valuable feedback.

Q1. It remains unclear whether click probabilities remain static or evolve based on user behavior over time.

Please refer to our response to Reviewer 9b0Z (Question 1) for how we set probabilities.

Q2. The paper does not discuss how to estimate the total number of user visits $T'$

We 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$.

We 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.

Line 16

Thank 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.

Table 1

Thank 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.

Line 224

Yes, this represents the marginal gain. We will clarify this in the next revision of the paper.

We are thankful to the reviewer for their feedback of our paper:

Q1. Why is it reasonable to assume we have a clean probability tag for each item, and how would this perform under misspecification?

Thank you for your question! Could you please clarify what you mean by a "clean probability tag"?

1. If you mean why we can assume these probabilities are provided:

   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.

   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.

   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. Each copy of the news item can be assigned a different probability. 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.

2. If you mean why the probabilities for an item are static, but not, for instance, time-dependent:

   STORM++ cannot handle dynamic probabilities—i.e., probabilities that change over time.

   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. Whenever the user visits the system, the algorithm presents one partition to the user.

   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. However, this is a very interesting future work direction, and we appreciate you for pointing it out.

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?

Below, we list three different aspects that make our problem different. The 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.

• (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.

• (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.

• (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.

In 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.

In 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.

In 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.

Q3. In your experiments, how did you generate your $p_i$ values?

We 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]$.

We would like to mention that, in the literature, paper [5] employs a similar approach to generate probabilities.

[1] Mnih A, Salakhutdinov RR. Probabilistic matrix factorization. Advances in neural information processing systems. 2007;20.

[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).

[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).

[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.

[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.

Thank you for your review. We’d appreciate it if you could share whether our response resolved your concerns, or if there’s anything else you'd like us to address. We’re happy to clarify further if needed.