Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints

Thank you for your time and your encouraging review. We address your concerns in the following:

Weaknesses

The paper lacks empirical evaluation, which would be valuable in highlighting a use case and demonstrating the effectiveness of your proposed approach.

We agree with you that empirical evaluation can be valuable to demonstrate the effectiveness of proposed approaches in real-world applications. However, we highlight a few points:

1. Our paper primarily emphasizes the theoretical contribution of our approach.

2. Our Algorithm 1 is the first algorithm for online stochastic DR-submodular optimization with long-term constraints under semi-bandit feedback. There would not be any baselines to compare it to. All of the algorithms from previous works listed in Table 1 are for simpler settings (full information feedback, $0 \in \mathcal{K}$, some requiring exact gradients). We could potentially empirically evaluate Algorithm 1 against those in simpler settings (full information feedback, $0 \in \mathcal{K}$, exact gradients) but we do not think it would be fair to do so.

3. Similarly, our Algorithm 2 is the first algorithm for online stochastic DR-submodular optimization with long-term constraints with full-information feedback (when $0 \in \mathcal{K}$ is queryable). There would not be any baselines to compare to (aside from our Algorithm 1 designed for a harder setting of semi-bandit feedback). We could potentially apply Algorithm 2 in a simpler setting ($0 \in \mathcal{K}$, exact gradients) to evaluate against other algorithms listed in Table 1, though we think it would not be entirely fair to do so.

4. Existing methods for DR-submodular maximization with long-term constraints typically exhibit high query complexity, often exhibiting $\sqrt{T}$ per round for query complexity. In contrast, our method achieves a query complexity of just 1 per round.

The theoretical results, while commendable, are not particularly groundbreaking.

We highlight some aspects we believe are significant in Q1 of the general response above.

Questions

I have no questions

Thank you very much for your careful reading and helpful suggestions. Next, we will address some of your concerns in "Weakness" and "Questions".

Weaknesses

1. The main weakness is the technical contribution. The method used in this paper is a simple combination between non-oblivious PGA and regularized Lagrangian function techniques. I do not find the new analysis or algorithmic challenge.

We address technical contributions in Q1 of the general response above.

2. The author's references to previous works do not seem to be appropriate $\dots$

Thank you for your detailed suggestions. We agree with you and will cite [37] for Lemmas 2 and 7 to clarify [Zhang et al.]'s contributions.

3. The 1/2 approximation ratio is not satisfactory, even in the semi-bandit setting. It's known that the 1-1/e approximation ratio can be achieved in the full-bandit setting, which is a harder setting than the semi-bandit setting. As the authors say, these bandit algorithms with 1-1/e approximation ratio require the assumption that $0\in \mathcal{K}$. But I don't think it is necessary to remove this assumption.

First, in the final version of the paper we will include application examples that showcase the importance of general convex regions $\mathcal{K}$ for which the origin is not feasible. Please refer to Q2 in the general response above for examples.

Second, we note that when $0\in \mathcal{K}$, there is no clear path to get $O(\sqrt{T})$ $(1-1/e)$-regret with semi-bandit feedback even without considering long-term constraints. When the origin is included, the best known $(1-1/e)$-regret bound for semi-bandit feedback without long-term constraint is $O(T^{3/4})$ in Pedramfar et al., 2023 [24]. As indicated by the non-oblivious function in Lemma 2, the $1-1/e$ approximation needs information at two locations (e.g. a function value at $x$ and a gradient value at $z*x$). One possibility is that when $0\in \mathcal{K}$ and we have semi-bandit feedback, we believe we could utilize an explore-then-commit approach to bound $(1-1/e)$-regret, but the horizon $T$ dependence would be worse than $O(\sqrt{T})$. For reference, Table 1 in [Pedramfar et al., 2024] is good summary of regret bounds for online DR-submodular optimization under different types of feedback (semi and full bandit), objective functions, and feasible regions.

Questions

1. There is a new paper extending the non-oblivious PGA technique to non-monotone function setting: https://arxiv.org/abs/2401.08330. Can we use this result to generalize your results to non-monotone setting?

That is a great question. We think it might be possible but were not able to carefully verify this in the short rebuttal time. We will leave it as a future direction.

2. Why do the authors assume that the utility functions are sampled i.i.d. from a distribution? We know the online gradient ascent works for adversarial environment. Can we still derive the current results if the utility functions are adversarially selected? This question also applies on the constraint, what if the constraint is adversarially selected?

First, we note that the analysis we perform does not extend to adversarial objectives. Specifically, the operations in equation (38), which uses tower rule of expectations to establish upper bound on the difference of Lagrangian functions, rely on the stochastic nature of the objective. On the other hand, in adversarial objective scenarios, we anticipate that the methodologies applied in Lemma 7.5 from [Hassani et al., 2017] could be used to go through those steps, but we will leave it as future work.

Second, we emphasize that in DR-submodular maximization, the stochastic and adversarial settings are distinctly separate scenarios, as we've detailed in lines 61-63 of the paper: "Note that this setting is still of interest because as opposed of assuming each arriving function $f_t$ being DR-submodular, we only assume the expectation of $f_t$ to possess DR-submodularity". Working with the stochastic objectives holds equal significance to the adversarial ones, given that many real-world applications are commonly framed within a stochastic framework, such as maximum coverage and budget allocation problems (described in general response), among others.

When the constraints are selected adversarially, for either stochastic or adversarial objectives, there is a known hardness result: [Mannor et al., 2009] provided a simple counterexample showing that achieving sub-linear regret against the best-fixed benchmark action in hindsight while maintaining sub-linear total constraint violation is not always possible. Subsequently, works addressing adversarial constraints alter the regret definition to consider only benchmark satisfying the constraint proportionally over some window of size $W\in [T]$, e.g., [Sadeghi et al., 2020]. We have included a discussion with this point in Appendix G. It is not clear if our results in this paper could be extended to that setting.

3. See weakness 1, what is the new challenge in your algorithm design and analysis?

We address technical contributions in Q1 of the general response above.

Thank you very much for your review. Here we address the questions in "Weakness" and "Questions" as follows.

Weaknesses

• The authors did not motivate the stochastic DR-submodular setting well. It is not explained why previous works used adversarial setting and what the motivation is for relaxing this scenario to stochastic setting.

First, for objectives, we emphasize that in DR-submodular maximization, the stochastic and adversarial settings are distinctly separate scenarios, as we've detailed in lines 61-63 of the paper: "Note that this setting is still of interest because as opposed of assuming each arriving function $f_t$ being DR-submodular, we only assume the expectation of $f_t$ to possess DR-submodularity". Working with the stochastic objectives holds equal significance to the adversarial ones, given that many real-world applications are commonly framed within a stochastic framework, such as influence maximization and facility location problems (described in general response), among others.

Second, when the constraints are selected adversarially, for either stochastic or adversarial objectives, there is a known hardness result: [Mannor et al., 2009] provided a simple counterexample showing that achieving sub-linear regret against the best-fixed benchmark action in hindsight while maintaining sub-linear total constraint violation is not always possible. Subsequently, works addressing adversarial constraints alter the regret definition to consider only benchmark satisfying the constraint proportionally over some window of size $W\in [T]$, e.g., [Sadeghi et al., 2020]. We have included a discussion with this point in Appendix G. It is not clear if our results in this paper could be extended to that setting.

• It isn't clear what the significance is of not requiring that 0 be in the constraint region.

See response to the first question below.

Questions

• What is the significance of handling search spaces that do not necessarily include 0 between your algorithm and other algorithms? Could you provide more details?

In offline DR-submodular maximization literature (without long-term constraints), there appears to be a significant hardness gap between $0\in \mathcal{K}$ and otherwise when only feasible points can be queried (e.g. with semi-bandit and bandit feedback). With $\mathcal{K}$ being a general convex set, the best-known approximation ratio is 1/2 [Hassani et al., 2017]. The tightness of the upper bound is not known, but is conjectured to be 1/2 [Pedramfar et al., 2023]. With the assumption $0\in \mathcal{K}$, the best-known result is $1-1/e$ [Mokhtari et al., 2020].

In online scenarios, we note that when $0\in \mathcal{K}$, there is no clear path to get $1-1/e$-regret in semi-bandit setting with only $\sqrt{T}$ regret even not considering long-term constraint. When the origin is included, the best known $1-1/e$-regret in semi-bandit setting without long-term constraint is $O(T^{3/4})$ in [Pedramfar et al., 2023]. As indicated by Lemma 2, the $1-1/e$ approximation needs additional information (to query function value at $z\*x$). One possibility is that when $0\in \mathcal{K}$, we could utilize an ETC style in the semi-bandit setting, where we alternately sample $z_t\*x_t$ (giving estimates for $\nabla F$), and $x_t$ (giving reward signal,) to achieve $1-1/e$ approximation ratio but a regret worse than $O(\sqrt{T})$. Table 1 in [Pedramfar et al., 2023] gives a great summary of regret results for online DR-submodular optimization.

In the final version of the paper, we will also include application examples that showcase the importance of general convex regions $\mathcal{K}$ for which the origin is not feasible. Please refer to Q2 in the general response above for those examples.

• Why do most prior works assume the adversarial choice of functions? Are there any example applications that would fall into the stochastic setting considered in this paper?

Please see response to the first Weakness above.