Adaptive Threshold Sampling for Fast Noisy Submodular Maximization

I do not have significant negative comments regarding the contributions of this paper. My only concern is whether the topic aligns well with ICLR's scope, as I have not come across purely theoretical work on submodular maximization algorithms published at ICLR before. While submodular maximization is indeed a crucial problem in machine learning, ICLR, to my knowledge, tends to focus more on areas related to deep learning and neural networks. Therefore, would it be more appropriate to consider submitting this paper to venues like NeurIPS or ICML, which might better align with its focus?

Submodular optimization problems are important for many applications in machine learning, such as exemplar-based clustering, influence maximization, and reinforcement learning. While it is the case that more papers on the topic of submodularity appear at NeurIPS and ICML, this topic has recently been of interest at ICLR. In particular, there are a total of 7 submissions to ICLR 2025 that are on submodular optimization (many of which are mainly focused on algorithms), and 3 papers appeared at ICLR 2024 on the topic. As one example, the paper [1] is no less theoretical than our own work. Besides, another topic related to our paper is the multi-armed bandit problem under a pure-exploration setting. There are also many papers on this topic that have been published in ICLR. For example, [2] and [3] are published in ICLR 2024 and the main focus of the mentioned papers is theoretical.

[1] Pedramfar, Mohammad, et al. "Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization." ICLR, 2024. [2] Zixin Zhong, Wang Chi Cheung, Vincent Y. F. Tan. "Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits", ICLR, 2024. [3] Zhirui Chen, P. N. Karthik, Yeow Meng Chee, and Vincent Y. F. Tan. "Fixed-Budget Differentially Private Best Arm Identification", ICLR, 2024.

The technical contribution is moderate. In the end, the paper's contribution lies in rewriting concentration bounds, parameterized by a notion of gap. Threshold-based algorithms are well-known in the submodular literature.

We do not simply rewrite concentration bounds parameterized by a notion of gap. Our sampling strategy is fundamentally different from applying a concentration bound to a single batch of i.i.d. samples and is significantly more sample-efficient. In standard applications of concentration inequalities such as Hoeffding's inequality in submodular optimization, a fixed batch of samples is used. It isn't possible to sample until we've reached the gap because there is only a single batch of samples and we don't have any clue what $\phi$ would be before we take them. $\phi$ arises in the adaptive sampling context, where samples are taken one-by-one. This may seem similar to the former approach, but there are significant technical challenges that arise as a result. We describe this more thoroughly in the response to all reviewers, and we have included this discussion in the updated version of our paper highlighted in blue in the appendix.

The sample complexity bounds are pretty involved. Many parameters are entailed, and a clear picture is difficult to get.

Let us first examine the sample complexity for a specific instance of CS. In Theorem 1, the term on the left-hand side, $\frac{2R^2}{\epsilon^2}\log \left(\frac{4}{\delta}\right)$, represents the number of samples required to approximate $X$ within $\epsilon$-distance with probability, i.e., $|X-\mathbb{E}X|\leq\epsilon$. This corresponds to case (d) in Figure 1, and is the number of samples that the fixed $\epsilon$-approximation would take. Such a large number of samples is only necessary when $\mathbb{E} X$ is close to the threshold, and therefore many samples are needed to see if it is above or below the threshold. Importantly, this value can be obtained without adaptive sampling.

The value on the right-hand side of the sample compleixty result in Theorem 1 comes from the adaptive sampling, and it is the number of samples required to shrink the confidence interval just enough so that we can conclude whether $\mathbb{E}X$ is approximately above or below the threshold, and it depends on how far $\mathbb{E}X$ is from the threshold, i.e. the value of $\phi$ (since a larger gap allows for a wider confidence interval upon stopping and thus fewer samples. ). This latter value cannot be computed before we start sampling, and is a result of the adaptive sampling where we do not know how many samples we will take initially. This corresponds to cases (a) and (b) in Figure 1.

Now consider Theorems 3, 4, and 5, which provide the sample complexity of CS within the algorithms. These results are derived by setting the failure probability $\delta$ in Theorems 1 or 2 to be the reciprocal of the total number of calls to CS, (i.e. the number of marginal gain queries) multiplied by $\delta'$. This adjustment ensures that, via a union bound, the overall algorithm succeeds with a probability of at least $1-\delta$. We have incorporated this discussion into the updated version of the paper, highlighted in blue.

Except for CS, the remaining algorithms are not new. The author's main contribution is how to apply CS algorithm to existing algorithms and the corresponding theoretical analysis ... What are the challenges in getting better theoretical bounds when applying CS algorithms to existing algorithms?"

The idea of the CS algorithm is not new. It existed in previous algorithms (For example, in Alg 2 in [Mat]) ... What are the differences (ideas, theoretical analysis) between CS and Alg 2 in [Mat]?

Algorithm 2 in [Mat] does not appear to be the same as the CS algorithm but is similar to what we call a fixed $\epsilon$-approximation in the paper (see Section 2 in our manuscript for a definition of this). In fact, the CS algorithm improves upon this approach.

In particular, in Algorithm 2 [Mat] takes a single batch of samples in order to approximate the mean of their distribution $\mathcal{D}_t$. In contrast, the key idea of CS is to sample one at a time and check the mean and confidence interval after every sample (i.e. sample "adaptively"), which introduces significant technical challenges in the development and analysis of CS. We give a more thorough description of why the analysis of our adaptive sampling approach is much different than algorithms such as that of [Mat] in the response to all reviewers. Here, we briefly summarize the key points. The technical challenges and differences include:

• The fixed-$\epsilon$ approximation only use the concentration inequality for a single time on a fixed number of samples while CS algorithm requires applying the concentration inequality for each sample.
• The fixed-$\epsilon$ approximation takes a predetermined number of samples while in the CS algorithm, the number of samples is a random variable dependent on the outcomes of previous samples. This caused difficulty in applying the concentration inequality.
• In CS, the confidence interval is designed to adapt with each new sample, gradually shrinking as the number of samples increases (see Theorem 1). In addition, the failure probability is adjusted dynamically based on how many samples we've taken so far (see proof of Lemma 6).
• In Theorem 2 and 4, we use a combination of Hoeffding and Chernoff that is well-suited to the threshold algorithms, which results in improved dependence on $R$ when $R$ is large .

It may in fact be possible that the algorithm of [Mat] could use something like CS as a subroutine, improving their sample complexity, which illustrates CS as a widely useful algorithm.

[Mat] Matthew Fahrbach, Vahab S. Mirrokni, Morteza Zadimoghaddam: Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity. SODA 2019: 255-273.

"Confident Sample (CS), has been shown to be effective in estimating the expectation of the objective submodular function in Gause distributions ... Does the CS algorithm work well with other distributions?"

The CS algorithm is for any random variable that is $R$-sub-Gaussian, which include bounded and Gaussian random variables.

"Can the CS algorithm be applied to the Minimum Cost Submodular Cover (MCSC) problem? The paper's contribution would be better if it is possible to apply CS to MCSC with better theoretical bounds."

The CS algorithm works for a wide range of submodular algorithms which has the thresholding step to check whether the marginal gain is above the threshold or not. Therefore, if we adopt an algorithm based on threshold greedy algorithm, it is also possible for our algorithm to work for MCSC algorithms. For example, we can use bicriteria algorithms developed in [1].

[1] Chen, Wenjing, and Victoria Crawford. "Bicriteria approximation algorithms for the submodular cover problem", NeurIPS, 2024.

Thanks for the feedback from the authors. I still think the paper is technically average. The CS algorithm is not really new, it borrows ideas from previous algorithms. Besides, I think that putting CS into existing algorithms without any improvements is not a significant contribution. In submodular function optimization, developing new techniques that improve theoretical bounds is more important. Therefore I keep my score of 5.

The results are somewhat difficult to appreciate for me, despite that they provide more than a page-long comparison with [Singla et al. (2016)] in Appendix discussing the differences in the long formulas ... While I see that the authors do achieve an improvement over the previous works, I do not see its significance.

One important difference is that the work of Singla et al. only considers the problem of monotone submodular maximization with a cardinality constraint. In contrast, our proposed CS algorithms could serve as a general tool for a wide range of threshold-based submodular optimization algorithms where the sampling process is used to determine whether the expectation of the noisy marginal gain is above or below the threshold. Therefore part of our contribution is that we develop and analyze algorithms for different optimization settings of monotone submodular maximization with a matroid constraint (Algorithm 5), and unconstrained non-monotone submodular maximization (Algorithm 4). This former problem setting is especially important for the submodular optimization community because it displays how CS can be used to make the widely used multilinear extension algorithms more efficient.

We now discuss the improvements made by our algorithm CTG over the algorithm EXP-GREEDY of Singla et al. for cardinality constrained monotone submodular maximization.

• Query Complexity. There are two major aspects of the query compleixty of these algorithms: (i) How many times does a marginal gain of $f$ need to be computed over the duration of the algorithm, and (ii) how many samples do we need to take in order to approximate this marginal gain sufficiently well. For (i), our proposed algorithm CTG is proven to be superior to that of Singla et al. by a factor of $O(k)$. In many applications, the input budget $k$ is quite large (even on the order of $n$) and therefore this speedup can make a huge difference. On the other hand, when considering the number of noisy queries for each marginal gain, the proven bounds on the algorithm CTG and EXP-GREEDY are incomparable as they are using completely different noisy sampling strategies, and it would depend on the instance which is superior.

• Improved Robustness. In the EXP-Greedy algorithm, a small $\Delta_{max}$ could directly impact the sample complexity of an entire round of the standard greedy algorithm, where the marginal gains of adding all $n$ elements to the solution set are evaluated and are influenced. In contrast, our algorithm evaluates the marginal gains for different elements independently. As a result, a small value of $\phi$ for one marginal gain does not influence the evaluation of other marginal gains, enhancing robustness.

Knowing something about the properties of the input instance, how can you estimate the value of $\phi$ without running your algorithm? I am asking this to understand whether your bounds can be used to predict your algorithm's performance. Note that, for example, $\Delta_{max}$ can be estimated in advance based on the properties of the input instance.

CS effectively lower bounds $\phi$ by $\epsilon$, and therefore this gives us a worst case sample complexity not dependent on $\phi$. In particular, notice in CS we stop sampling once the confidence interval reaches $\epsilon$ (see Figure 1 for illustration), and in Theorems 1 and 2 the left side of the bounds on the number of samples is not dependent on $\phi$.

On the other hand, notice that $\Delta_{\max}=\min_{i\in[n],i\neq i^*}(\Delta f(S,i^*)-\Delta f(S,i))$ where $\Delta f(S,i^*)=\max_{i\in[n]} \Delta f(S,i)$ is the highest marginal gain. \Delta_{\max} measures the difference of the marginal gain between the element with the highest marginal gain and the element with the second highest marginal gain. The parameter $\phi$ in our algorithm is $\phi=\frac{|\Delta f(S,i)-w|+\epsilon}{2}$. Therefore, in the scenario where we can know something about the properties of the input instance to help estimate $\Delta_{max}$, we should be able to estimate the value of the marginal gain. Notice that the threshold $w$ and parameter $\epsilon$ are known before the algorithm, so we might also be able to estimate $\phi$ in advance.

I thank you for your explanation. It does address some of my comments. In particular, I did not manage to understand that your algorithm improves the bound on the total number queries by factor of $k$. Your theorems focus on per-iteration bounds which, as you say, are incomparable to Singla et al. I would suggest to point it out more clearly. Even now, I can only see in the appendix B that such an improvement is supposed to happen if $\Delta_{max} \leq O(\epsilon)$, not explaining what will happen if this is not the case. There is at least one other reviewer who had troubles to make sense of your results.

However, looking at the comments of the other reviewers, I have decided to keep my original rating.