A Unified Approach to Submodular Maximization Under Noise

Thank you for noting the issue with Lemma 3.3. As noted in the paper, one cannot use the usual Hoeffding inequality out of the box because the random variables are not independent. However, Hoeffding also proved a version for sampling without replacement (see Proposition 1.2 of [1] below or Section 6 of Hoeffding’s paper [2]). Basically, the result says that the same bound holds even when sampling without replacement. Using the notation in [1], we would just set $X_i = f(S \cup H_i)$, so $X_1, …, X_m$ are sampled from a finite population of $h$-choose-$t$ elements without replacement. We will add this reference to the proof of Lemma 3.3.

[1] Bardenet, Rémi, and Odalric-Ambrym Maillard. "Concentration inequalities for sampling without replacement." Bernoulli (2015): 1361-1385.

[2] Hoeffding, Wassily. "Probability inequalities for sums of bounded random variables." Journal of the American statistical association 58.301 (1963): 13-30.

Thanks for your review and positive assessment!

(Weakness 1) Randomized surrogate function seems to be not super unexpected.

We agree that the idea of using randomization is not super surprising in and of itself. However, we still find it interesting that a simple randomized framework is already sufficient to recover and improve existing results while also allowing us to easily prove new results. It also allows us to reduce the problem of designing and analyzing algorithms in the noisy setting to checking robustness of existing approximation algorithms. It was not clear from prior work that this decoupling was possible.

(Question 1) What is the intuition behind the sub-exponential noise? What are the limitations of the approach towards general noise?

We would need some assumption on the distribution in order to have some result. Without any assumptions, we could have very bad distributions. For example, consider a case where there are n items and we just want to pick one. One item is very valuable but extremely noisy and will return 1 most of the time. All other items have value 1. It would not be possible for any algorithm to distinguish between these items. In addition, we also note that our sub-exponential assumption is already more general than prior work such as [11, 14].

(Question 2) The robustness assumption in Definition 3.1. seems restrictive at first glance. Is this really the case (even though several approx. algorithms fulfill this definition)? Could this be extended to less restrictive definitions as well?

We suspect that the robustness definition is not an extremely strong assumption but we don’t yet have a formal argument for it. Intuitively, if you ran an approximation algorithm but the values were off by $\epsilon$ then, by virtue of it being an approximation algorithm, you would still expect a good approximation. It is an interesting question to see if one can formalize a connection between approximation algorithms and robustness.

(Question 3) Is your approach also usable for, say, knapsack constraints or similar?

Great question! This is a great open question for future work. The analysis of our meta algorithm does rely on the fact the constraint is a matroid constraint. Our analysis uses a basis-exchange property for matroids, which does not directly extend to more general constraints (e.g., knapsack constraint).

Thanks for reviewing the paper and spotting the typo! We will fix it.

Thanks for your review. We would like to address the weaknesses you pointed out.

(Weakness 1) As you mentioned, one of the core methods is based on the robustness analysis of existing algorithms. However, we think this is actually one of the main advantages of our work. Previous work [11, 14] defined surrogate functions and implicitly used robustness arguments. However, their analysis mixes these two components and is very specific to their setting. It is unclear whether or not these two components can be separated to obtain a more general reduction. In contrast, we construct a new surrogate function that enables these two parts to be analyzed separately, establishing a clean reduction from the noisy submodular maximization problem to the robustness analysis of existing algorithms. Such a new surrogate function requires randomization that is not present in previous work.

(Weakness 2) As with prior work on this topic (specifically [11, 14]), and many prior works on submodular optimization published in NeurIPS, our goal is to advance the theoretical understanding of submodular optimization with noise. With that said, we also agree with the reviewer that the empirical comparison with heuristic methods may be helpful to demonstrate the practical value of our algorithm. So, we have implemented our algorithm and compared it with heuristic methods; please see the end of our rebuttal for details.

(Weakness 3) Yes, the rank constraint is a current limitation of our work. When the rank $r$ is very small, it is unclear whether the surrogate function approach (using auxiliary subsets to denoise the function) still works. Nonetheless, we note that our work already improves upon the dependency of the rank in prior work such as [14]. In [14], they have two regimes. The regime which is the most comparable is when $n \geq 1/\epsilon^4$ (Theorem 5.2 of [14]). For reference, note that we require $n \geq 1/\epsilon$ so our requirement on $n$ is better (their other regime actually requires $n$ to be exponential in $poly(1/\epsilon)$). In this case, their Theorem 5.2 requires $r \geq n^{1/3} \geq 1 / \epsilon^{4/3}$. So our dependency on the rank $r$ is exponentially better than [14].

For completeness, we will note that in [14], if they assume $n$ is exponential in $poly(1/\epsilon)$ (although it is unclear what the degree of the polynomial is), then $r \geq 1/\epsilon$ is sufficient. In this regime, their dependency on the rank is better but we reiterate that this requires that $n$ is very large.

(Weakness 4) As discussed earlier, our main focus is on a better theoretical understanding of submodular optimization with noise. To complement the theoretical perspective, we provide experiments to demonstrate the “practical applicability” of our algorithms. Please see the details below.

Added experiments: To address Reviewer WQvx’s concerns in Weaknesses 2 and 4, we provide some experimental results. We focus on the simple yet underexplored case of unconstrained non-monotone submodular maximization. We consider an example where the submodular function has additive weights and quadratic cost in size: $f(S) = \sum_{i\in S} w_i - c |S|^2$, with $w_i \sim \mathrm{Uniform}[0, 20]$ and $c = 0.1$, with groundset size $n=100$. To match the setting in our paper, we ensured $w_i$ were chosen so that $f$ was non-negative (although this does not impact the results). The noisy value is $\tilde f(S) = \xi_S f(S)$ where $\xi_S \sim \mathrm{Normal}(\mu=1, \sigma^2=0.1)$. We compare four algorithms against the optimal value benchmark:

(1) Double greedy (DG) algorithm with exact value oracle (Buchbinder et al, 2015). This is a worst-case optimal polynomial-time algorithm in the noiseless setting.

(2) Random subset: pick a random subset of size $n/2$. This trivial algorithm is only for reference.

(3) Double greedy (DG) algorithm that uses the noisy value oracle directly. This is a natural heuristic algorithm. Reviewer WQvx suggested we compare against heuristic algorithms.

(4) Our algorithm in Theorem 4.5, which is the surrogate-function-based meta-algorithm instantiated with double greedy. After simple tuning, we set the parameters to h = 20, t = 4, and vary m.

Results are shown in the following table. We fix a function $f$, run the randomized algorithms for 100 simulations, and show the mean values (E[ALG] / OPT) and standard deviations.

We see that the heuristic algorithm (DG with noisy oracle) does not perform well in this example; its performance is similar to a random subset. Our algorithm significantly outperforms the heuristic algorithm, with 18% improvement with m = 50 and 33% with m = 200.

Thank you for the question.

To reiterate, we view the main contribution and novelty of our work as providing a reduction from the noisy setting to the non-noisy setting. This reduction allows us to reuse existing algorithms completely out of the box. We are not just “extending the existing continuous greedy and double greedy algorithms to our problems” – any existing algorithm that is robust in the non-noisy setting can be plugged into our framework. For example, for the matroid-constrained monotone case, one can also use the local search algorithm (instead of continuous greedy) in our meta-algorithm. The known (1-1/e) approximation guarantee of local search in the non-noisy setting directly extends to the noisy setting. In contrast, the algorithms and analyses in [11][14] are specific to their settings: for example, [14] uses the local search algorithm with some special deterministic surrogate function and derives a sub-optimal (1-1/e)/2 approximation ratio for the matroid-constrained monotone case via specific analysis. Our work directly improves upon [14], as well as deriving new results, via a unified analysis.

Making this reduction work is non-trivial (otherwise, [11, 14] would be trivial). As we mentioned in our initial response, we needed a new surrogate function to overcome the limitations of [11, 14]. It turns out that the idea is simple: use a random surrogate function. While this is simple, it was not considered in prior work and turns out to be extremely useful.

In addition, how to define the random surrogate function requires some care. The most naive way to do this would be to sample a small (but large enough) set $H$ and then obtain a surrogate function by considering $E[f(S \cup H’)]$ where $H’$ is a uniformly random subset of $H$. We do not know if this works or not as our proof would not work; this breaks when trying to handle the matroid constraints. The crucial idea here is to use fixed-size subsets of $H$ and combine this with a generalized version of the basis exchange property ([5] in our paper). The connection to [5] may also be of interest as we are not aware of any works in submodular optimization that make use of this version of the basis exchange property.

Thanks for the response. I now have a clearer understanding of the paper’s contribution. I will adjust the score accordingly.