Online Two-Stage Submodular Maximization

We thank the reviewer for their feedback.

“Could the authors clarify the main technical contributions and specify the key challenges they had to overcome in establishing the primary results?"

First of all, we would like to thank the reviewer for the opportunity to re-iterate the main technical contributions of our work. These are split into two “categories”, those regarding the function F(x) and those regarding the two-stage rounding.

a) On $F(x)$:

Recall that the way that prior work measures the quality of a restricted groundset $x$ is by associating it to the maximal value a function $f$ can attain when optimized over it. This is captured by $F(x) = \max_{\substack{y \leq x, \\ ||y||_1 \leq k}} f(y)$. This is non-concave and, as we discuss in the paper, is NP-hard to compute. Thus, contrary to other online settings (like OCO and OSM), we cannot assume oracle access to the reward function when designing an online algorithm.

Instead, we work with the fractional relaxation $\widetilde{F}$ of F, which simply relaxes y to be fractional and replaces $f$ with its fractional relaxation.

An immediate challenge is that the behavior of $\widetilde{F}(x)$ is far from obvious; its input dictates the feasible region of the inner optimization problem and the relation between $x$ and $\widetilde{F}(x)$ is highly non-trivial. Surprisingly, we show that $\widetilde{F}$ is concave over the domain of $x$ and, even more importantly, that its super-gradients can be computed efficiently. To do the latter, we write $\widetilde{F}$ as a linear program and show that the dual variables corresponding to the constraints $y_i \leq x_i$ are actually a super-gradient of $\widetilde{F}$.

Both of the above structural insights are non-trivial and essential in order to leverage existing tools from the OCO literature.

b) On the two-stage rounding:

Designing a two-stage rounding procedure that handles matroid constraints is particularly challenging. Notably, no prior continuous optimization approach for the offline two-stage submodular maximization problem has succeeded in handling matroid constraints (the work of Balkanski et al. ICML 2016 only had a very simple rounding that works for a single cardinality constraint in the second stage).

The difficulty stems from the fact that the primary tool for rounding under matroid constraints, i.e. contention resolution schemes (CRSs), requires that coordinates are rounded independently at random. This is inherently incompatible with the two-stage setting: in our case, each coordinate $y_i$ in the second-stage solution must satisfy $y_i \leq x_i$​, where $x$ is the rounded first-stage solution. Consequently, the distribution over $y$ is inherently dependent on $x$, and since the first-stage solution $x$ must satisfy a global cardinality or matroid constraint, its coordinates are also correlated. This breaks the independence assumption required by standard CRSs and rules out their direct application.

To overcome this, we leverage a recent characterization theorem by Dughmi (ITCS’20). We notice that Dughmi’s result implies that it is sufficient for the rounding distribution to satisfy a structural property known as submodular dominance (Definition B3) in order for a CRS to exist for this sampling distribution. This implication is hinted at in Dughmi’s work, but we formally state and prove it as Lemma B.7. We believe that this connection could find applications beyond our setting.

Equipped with this insight, we show that, if we apply Randomized Pipage Rounding to the fractional first-stage solution and then sample an "intermediate" second-stage solution conditioned on the first stage (as detailed in Appendix C), the resulting distribution satisfies submodular dominance (Lemma C.4). This crucial property allows us to apply a CRS in the second stage and obtain a feasible solution with provable approximation guarantees.

For a higher-level discussion of the two-stage rounding, we refer you to our response to Reviewer SbnU and Appendix C.

We have discussed such issues in Section 5 (lines 239-244) and Appendix C (lines 727-732). We will revise the paper to make sure these technical contributions are more evident.

“The main weakness of the paper lies in the practicality of the proposed approach. While the two-stage setting is designed to address scenarios where the ground set is large and optimizing over a smaller subset is computationally efficient, the method introduced in this work is itself computationally intensive. … Given the computational overhead […] by the first stage, could the authors elaborate on why the two-stage online submodular maximization framework is more efficient and advantageous compared to traditional online submodular maximization methods?”

We appreciate the opportunity to discuss this. As the reviewer is asking us to compare two-stage submodular optimization to standard submodular optimization (online or otherwise), this is a question pertaining to the motivation of the two-stage submodular maximization setting in general (online and offline).

It would be good to clarify that a multi-stage approach is indeed often used for computational advantages. For example, many of today’s recommender systems involve multiple stages, progressively reducing the set of items to be recommended. Efficient early-stage recommender algorithms are run initially, and subsequently, more computationally expensive late-stage recommenders are applied at later stages (see, e.g., Liu et al., 2022a; Hron et al., 2021; Zheng et al., 2024; Covington et al., 2016).

However, in many circumstances, the 2-stage approach is inevitable for reasons that do not have to do with computational considerations. One example is caching/pre-fetching (see also Appendix A.2 in the paper): a system may need to pre-fetch content (e.g., a movie, a large file) to a CDN server close to the user, in advance of the arrival of the user and the expression of their demand. Beyond the computational issue of computing user preferences over a large content catalog when the user arrives (and expresses their demand), the server is restricted to delivering (quickly) only items they have prefetched, and this pre-fetching (that takes time) has to happen before demand manifests.

Appendix A.2 gives several more examples, where decision making (ground set restriction) needs to happen in advance of the manifestation of the demand (the revelation of the objective function). Another simple and intuitive example is putting together a team roster: the players in a team, programmers in a software company, etc., need to be hired before tasks to be performed (playing games or coding a feature requested by clients) are revealed, manifesting any skills required.

Finally, going back to the computational motivation for having multiple stages, the computational burden/overhead of the first stage is not as large as alluded to by the reviewer. In fact, approaching the problem as an online submodular maximization problem, as suggested by the reviewer, will not yield computational dividends as OSM algorithms have similar computational complexity (e.g. Si Salem et al. AAAI 2024).

We have made an effort to highlight the scalability/computational complexity of our algorithm in Section 6 and the necessity of the multi-stage approach beyond computational reasons in Appendix A. We will revise these points to make these issues more prominent.

Dear Reviewer SdED,

Would you please check if the authors address your major concerns, and if you have further comments?

Regards,

AC

We thank the reviewer for their feedback.

“Explain how to comprehend the size of $(1-1/e)(1-e^{-k}k^k/k!)$ compared to $(1-1/e)^2$”

Please refer to Figure 4 in Appendix J. In this figure, we plot the aforementioned quantities as well as the approximation ratios of the prior work in the offline problem. We observe that $(1-1/e)(1-e^{-k}k^k/k!)$ is larger than $(1-1/e)^2$ for all $k \geq 1$. Also, compared with $1-1/e-1/\sqrt{k}$, which is the previous state-of-the-art approximation ratio for a cardinality constraint in the second stage, our guarantee is better for all $k\geq 1$.

“The authors state that "we design a two-stage randomized rounding procedure, used only in our analysis, that is coupled with the rounding performed by RAOCO." I am not sure if I understand this correctly. If the advanced rounding technique is used virtually, then what rounding is actually used in the algorithm? Does the given algorithm still achieve the claimed regret bound?”

We thank the reviewer for the opportunity to clarify this point regarding the algorithm’s rounding procedure. The point raised by the reviewer is important and is also related to the technical novelty of our contribution.

There are indeed two rounding procedures used in our analysis:

1) Rounding used by Alg. 1 (Pipage Rounding) Recall that Algorithm 1 must output a subset of size $\ell$ (the “restricted groundset”). To do so, it runs an Online Convex Optimization (OCO) policy (e.g., FTRL or OGA) to obtain fractional values for the elements (a “fractional restricted groundset”) and then applies Randomized Pipage Rounding to produce the final integral restricted groundset (see Appendix I). This is, in fact, the only rounding procedure used by the algorithm. The rounding is very simple, efficient, and easily implementable. No other rounding needs to be implemented to execute the algorithm; the regret bound stated in the paper (Theorem 5.1) is correct, and is indeed achieved using exactly this procedure.

2) A second rounding, introduced only in the regret analysis We stress that this second rounding is not used by the algorithm, and is only used in the analysis as a tool to prove a lower bound. We describe this in lines 246-250 & 717-721, but we will attempt to clarify this further here.

Observe that, by Lemma 5.2, the fractional restricted groundset that the OCO policy returns is “good enough” : if the algorithm could output that, it would have no regret.

However, as discussed above, the algorithm needs to round this restricted groundset, say $\widetilde{x}$, to an integral groundset $x$. It does so by running Randomized Pipage Rounding. In order to prove that the algorithm’s output has sublinear $\alpha$-Regret, we need to prove that the “value” of the rounded groundset is at least an $\alpha$ factor of the “value” of the original fractional groundset $\widetilde{x}$.

The “value” of a restricted groundset is measured by the maximal value a function $f$ can attain when optimized over the restricted groundset, i.e. $F(x) = \max_{\substack{y \leq x, \\ ||y||_1 \leq k}} f(y)$.

As $\widetilde{x}$ is rounded to $x$, it is highly nontrivial to track what is the relation between $F(\widetilde{x})$ and $F(x)$, as the input of $F$ changes the feasible region of the inner maximization problem.

To prove the desired relation, we do the following: Fix $\widetilde{x}$, the algorithm’s output $x$, and a function $f$.

Let $y^{\*}$ be the maximal solution of $f$ on the restricted groundset, i.e. $F(\widetilde{x}) = f(y^{\*})$.

We construct a new solution $y’$ that lies in the rounded restricted groundset $x$, for which it holds that $f(y’) \geq \alpha \cdot f(y^*) = \alpha \cdot F(\widetilde{x})$.

Note that the maximal value of $f$ in the groundset $x$, namely $F(x)$ (!), is going to be at least $f(y’)$, because $y’$ is just one feasible selection.

Therefore this concludes our proof that: $F(x) \geq f(y’) \geq \alpha \cdot f(y^*) \geq \alpha F(\widetilde{x})$.

This is our proof of Lemma 5.3 on a high level. In order to make this proof possible, we need to come up with a way to construct $y’$ given $\widetilde{x}, x$ and $y^*$. This is exactly what the second ”virtual” rounding does.

This rounding first constructs an intermediate (possibly infeasible) integral solution $\hat{y}$​ and then applies a contention resolution scheme (CRS) to obtain a feasible solution $y’$. We describe this procedure in detail in Appendix C. Lemmas C.1 through C.5 build up to the guarantee that $f(y’) \geq \alpha f(y^*)$ as we described above.

This argument is central to proving Lemma 5.4 and, ultimately, our regret bounds.

To summarize, the second rounding, as technical as it may be, is not used by the algorithm and is only used in the analysis as a tool to prove a lower bound.

We hope that this clarifies the role and purpose of the two-stage rounding in our analysis.

“Given the heavy theoretical machinery, the algorithm is not scalable (up to thousands of elements).”

All components of our algorithm to scale to larger datasets. The online optimization routines (FTRL, Gradient Ascent) compute gradients efficiently in polynomial time via linear programming, and the rounding step (pipage rounding) runs in $O(n)$ time for cardinality constraints. As analyzed in detail in Section 5 (“Computational Complexity”), these components do not pose practical bottlenecks.

To further strengthen the paper, we will include a large-scale experiment in the final version. In this experiment, based on the HotpotQA dataset with a ground set of $10^5$ articles, our algorithm selects, at each iteration, a set of articles intended to “cover” an unknown topic revealed only after the selection. Despite the large ground set and the online nature of the task, each iteration, i.e., solving a convex program over the dataset and rounding the result via Randomized Pipage Rounding, completes in under 30 seconds, demonstrating the practical scalability of our approach. Notably, the algorithm of Stan et al. needs more than 15 minutes to find a restricted groundset in the above dataset, even for a small number of second-stage functions (e.g. less than 10)!

We include a table below showing the cumulative reward of our algorithm, the fractional optimal set in hindsight, and Random (i.e., selecting the restricted groundset randomly).

Table: Cumulative reward of different algorithms over HotpotQA dataset, as a function of online steps

Typos:

Thank you for spotting the typo in line 59. We will fix this and will correct all other typos pointed out by reviewers.

We thank the reviewer for their feedback. However, we believe that there is a fundamental misunderstanding regarding the main contributions and focus of our work.

“This paper focuses on the two stage submodular maximization problem [...] The first result of this paper [...] in the offline setting. [...] The authors ALSO consider the online setting.”

The paper’s primary focus is the online two-stage submodular maximization (O2SSM) problem, where the second-stage functions are revealed sequentially. Our main contribution is the first algorithm with sublinear $\alpha$-regret guarantees for this setting. The offline results (including the improved approximation for small $k$) are a (fortunate) by-product of our online framework, but not the central contribution. The online version of this problem was explicitly left as an open question by Stan et al. (ICML 2017), making our result the first to close this gap.

“The online setting considered in this work is not that interesting and the motivations provided for it are not strong enough”

The online setting we study is more natural and realistic than the offline two-stage submodular maximization problem in nearly all applications considered in prior work.

Consider the recommender system case, for instance, in which a platform must proactively maintain and update a restricted catalog $S$ (of size $\ell$) before user requests materialize. As a result, as new users, preferences, and content (movies, videos, or music) arrive continuously, user utility functions are not known ahead of time, and decisions on how to maintain this restricted catalog need to be made in advance.

Note that this setting, and the pertinent challenge, describe the (offline) 2SSM problem, as studied by Stan et al. (ICML 2017) and Balkanski et al. (ICML 2016). How is the challenge handled in the offline setting? Stan et al. and Balkanski et al. assume that a distribution over user utilities is known. In the online setting, we remove this assumption: we do not assume that utilities come from a known distribution. Instead, utilities are picked in an arbitrary (potentially adversarial) fashion. Clearly, making fewer assumptions than the offline setting makes the online setting more practical and better motivated, not less.

Providing guarantees in the online setting, and thereby lifting distributional assumptions, is a common theme in online algorithms; it is in fact the main reason they are studied, and of great interest to the machine learning community. Papers on online convex optimization and online submodular maximization have appeared in NeurIPS (Zhang et al. 2019; Harvey et al. 2020; Zhao et al. 2020; Ghai et al. 2022; Nie et al. 2024; Xu et al. 2024), ICML (Fotakis et al. 2021; Gergatsouli et al. 2022; Wan et al. 2023;), and COLT (Ito et al. 2024; Kozachinskiy et al. 2024; Appel et al. 2025; Mhammedi 2025), to name a few. The online setting is thus both of interest to the community as well as the original authors of (offline) 2SSM.

Note that, precisely because they make no distributional assumptions, online problems are more technically challenging than their offline counterparts. This is another reason why online submodular maximization and online convex optimization are active areas of research, and why Stan et al. themselves pose online 2SSM as an open problem.

In conclusion, while the offline two-stage framework has been justified in prior work, our online framework strictly generalizes it, removing the strong assumption that a distribution over objectives is known in advance. The extension to the online setting was also highlighted as an open problem by Stan et al. Finally, all other reviewers recognized the problem’s significance and strong motivation.

“This is also not for general submodular functions and only for WTP. Most of the previous works cited in this paper (see Table 1) are for general submodular function and in more practical settings.”

We stress that previous works in Table 1 are for the offline 2SSM problem, not the online O2SSM problem. Our work is the first to provide any guarantees in the online setting for any submodular functions (WTP or otherwise). We also stress that our online setting is a more challenging and realistic setting than the offline setting: the offline setting requires distributional assumptions; the online setting does not. Hence, we do not agree that the offline setting is more practical.

Finally, Weighted Threshold Potentials (WTPs) form a broad subclass of monotone submodular functions that subsumes all applications studied in prior two-stage maximization work, including Weighted Coverage, Influence Maximization, Facility Location, and Team Formation. Our results directly apply to all applications presented as a motivation by Balkanski et al. (ICML 2016) and Stan et al. (ICML 2017), despite focusing on WTPs. Note that several works on submodular maximization focus on restricted classes of functions, both in the offline and online setting (Karimi et al. NeurIPS’17, Bai et al. NeurIPS’18, Bian et al. ICML’17, Hassani et al. NeurIPS’17, etc.)

"“The techniques used here are interesting but seem to be limited to this specific problem.”

We stress that we solve O2SSM for arbitrary WTP functions and general matroid constraints in the second stage, both of which include many important instances, as listed in Appendix A.2.

Our techniques follow the general template of solving a continuous problem first, and then identifying an appropriate rounding. We design a novel scheme for 2-stage Submodular Maximization, when the feasible set of the second-stage maximization is restricted by a matroid constraint and depends on a first-stage decision. Such techniques are of broader interest and often find applications in different problems. As we also point out in the response to Reviewer SdED, the challenge we face lies in the incompatibility between standard contention resolution schemes (CRSs), which are essential for rounding continuous relaxations under matroid constraints, and the two-stage nature of the problem. Specifically, traditional CRSs require independent rounding, which is impossible when rounding across nested feasible sets (i.e., subsets selected in the first stage and constrained in the second).

To address this, we develop a two-stage rounding scheme based on a recent characterization theorem by Dughmi (ITCS 2020) concerning non-product CRSs. To our knowledge, this is the first time such a tool has been applied in a multi-stage stochastic setting. We believe this connection opens up new directions for multi-stage optimization under matroid and combinatorial constraints. Moreover, the rounding framework we introduce is not just an ad hoc fix: it may lead to closing the current approximation gap in offline 2SSM. Thus, we view this contribution as advancing rounding for structured, non-product settings, with potential applicability beyond 2SSM.

“The experimental section requires significant changes. [...] the datasets considered are tiny.”

We recognize that our main contribution is theoretical, providing the first formal sublinear $alpha$-regret guarantee for O2SSM. Our experimental evaluation is intended to validate our algorithm’s behavior and to compare it directly with prior work, rather than to establish scalability. To ensure a fair comparison, we follow the experimental setup of prior work [Balkanski et al., ICML’16; Stan et al., ICML’17], using the same datasets (Wikipedia, Images, and MovieRec), to directly benchmark against established baselines. To highlight the broad applicability of our framework, we also include the Influence and TeamFormation datasets, while the Coverage dataset is designed to illustrate the benefits of two-stage optimization over one-stage formulations.

Nevertheless, to address the reviewer’s concerns, we have conducted a new experiment on a dataset whose groundset is two orders of magnitude bigger than the ones tested by our paper and prior work. We discuss this in the next paragraph.

“Can the proposed algorithms be applied on much larger datasets?”

All components of our algorithm scale to larger datasets. The online optimization routines (FTRL, Gradient Ascent) compute gradients efficiently in polynomial time via linear programming, and the rounding step (pipage rounding) runs in $O(n)$ time for cardinality constraints. As discussed in Section 5 (“Computational Complexity”), these components do not cause bottlenecks. To strengthen the paper, we include a large-scale experiment based on the HotpotQA dataset with a ground set of $10^5$ articles. Our algorithm selects, at each iteration, a set of articles that “cover” an unknown topic revealed after the selection. Despite the large ground set, each iteration solving a convex program over the dataset and rounding the result via Randomized Pipage Rounding, completes in under 30 seconds, demonstrating the practical scalability of our approach. Notably, the algorithm of Stan et al. needs more than 15 minutes to find a restricted groundset in the above dataset, even for a small number of second-stage functions (e.g. less than 10)!

We include a table below showing the fractional optimal set in hindsight, the cumulative reward of our algorithm, and Random.

Table: Cumulative reward vs. time over HotpotQA dataset.

Dear Reviewer ToR4,

Would you please check if the authors address your major concerns, and if you have further comments?

Regards,

AC

We kindly thank the reviewer for their detailed feedback. We appreciate their positive view of the paper’s contributions.

“The (offline) 2SSM admits a better approximation ratio for coverage functions, a subclass of weighted threshold potential functions. Can one obtain the same ratio for online 2SSM by applying the approach of the paper?”

Thank you for bringing up this point. This requires a somewhat subtle comparison to prior work, that we clarify below, and can add to the paper as needed.

To the best of our knowledge, the only results that pertain to coverage functions in the context of two-stage submodular optimization appear in Balkanski et al. (ICML 2016). There are two guarantees provided by Ballkanski et al. in the context of coverage functions.

• First, along with their algorithm for general submodular functions, they propose a local search method that offers a $1/2 (1− 1/e) \approx 0.31$-approximation for the special case of coverage functions, under cardinality constraints.
  For large $k$, this guarantee is worse than the $1-1/e-1/\sqrt{k}$ guarantee of the continuous optimization algorithm also proposed by Balkanski et al. The latter algorithm also works for general submodular functions. The $\approx 0.31$ guarantee is also worse than the $(1-1/e^2)/2 \approx 0.43$ guarantee provided by Stan et al. (ICML 2017), which also works for arbitrary submodular functions over general matroid constraints. This is why we did not include the local search algorithm of Balkanski et al. in our literature review.

Our framework already achieves the state-of-the-art approximation ratio ($(1-1/e)(1-e^{-k}k^k/k!)$) both in the offline and online settings, for WTP functions and thus also for coverage functions, in the case of cardinality constraints. For more details, we refer the reviewer to Appendix J and Fig. 4. In particular, our guarantee is better than the guarantee by Stan et al. (ICML 2017) for $k \geq 2$. It is also better than the $1-1/e-1/\sqrt{k}$ guarantee of Balkanski et al. for all $k \geq 1$.

• Second, Balkanski et al. also point out that, for constant $k$ , a variant of their local search algorithm yields an improved $0.5$ approximation, still for coverage functions. This algorithm has a running time that is exponential in $k$. Note that our guarantee is better than $0.5$ for all $k > 3$, and does not require that $k$ is a constant. In fact, our algorithm’s running time is independent of $k$.

In summary, the guarantees for coverage in the offline case, under cardinality constraints, are not better than the ones we obtain here (either online or offline).

In the case of general matroid constraints, there are no special guarantees for coverage functions. The state-of-the-art approximation ratio in the offline problem is by Stan et al. (ICML 2017), who achieve a $(1-1/e^2)/2 \approx 0.43$ approximation, for general submodular functions. In the case of general matroid constraints, the offline version of our algorithm yields a $(1-1/e)^2$ guarantee. We discuss how our (offline) guarantee relates to prior work over matroid constraints in Table 1 and Appendix J. Note that the local search algorithm of Stan et al. heavily relies on the knowledge of all second-stage functions for its decisions, while our algorithm works in the online setting and operates without prior knowledge of second-stage functions.

Dear Reviewer 2YLy,

Would you please check if the authors address your major concerns, and if you have further comments?

Regards,

AC