Adaptive Threshold Sampling for Fast Noisy Submodular Maximization

Authors: Wenjing Chen, Shuo Xing, Victoria G. Crawford
Primary area: optimization
Keywords: submodular, multi-armed bandit, bandit feedback, best-arm identification, combinatorial optimization

Abstract:
We address the problem of submodular maximization where objective function $f:2^U\to\mathbb{R}_{\geq 0}$ can only be accessed through i.i.d noisy queries. This problem arises in many applications including influence maximization, diverse recommendation systems, and large-scale facility location optimization. We propose an efficient adaptive sampling strategy, called Confident Sample (CS), that is inspired by algorithms for best-arm-identification in multi-armed bandit, which significantly improves sample efficiency. We integrate CS into existing approximation algorithms for submodular maximization, resulting in algorithms with approximation guarantees arbitrarily close to the standard value oracle setting that are highly sample-efficient. We propose and analyze sample-efficient algorithms for monotone submodular maximization with cardinality and matroid constraints, as well as unconstrained non-monotone submodular maximization. Our theoretical analysis is complemented by empirical evaluation on real instances, demonstrating the superior sample efficiency of our proposed algorithm relative to alternative approaches.

Decision: reject
Reviewer scores: 6, 5, 5, 6

Reviews and discussion:
<thread>
creation date:
1729398063131

thread_type:
official_review

<thread_object>
creator: reviewer_xgdq

<content>
summary:
The paper introduces the Confident Sample (CS) algorithm to maximize submodular functions under noisy conditions efficiently. By leveraging insights from multi-armed bandit algorithms, CS reduces the number of noisy queries required to approximate submodular functions, making it applicable to diverse optimization tasks such as influence maximization and recommendation systems. Theoretical analysis and empirical results demonstrate the effectiveness of CS in achieving competitive approximation guarantees with significantly improved sample efficiency compared to traditional methods.

strengths:
The paper proposes the Confident Sample (CS) algorithm, which effectively reduces the number of noisy queries by dynamically adjusting the sample size according to the level of uncertainty. This adaptive approach contrasts with traditional fixed-precision methods, offering substantial improvements in sample efficiency. The work's theoretical contributions are robust, providing guarantees on both approximation quality and sample complexity, making it a competitive alternative to existing methods like ExpGreedy. These theoretical insights are further supported by empirical evaluations on real-world datasets, where the proposed algorithms demonstrate superior sample efficiency, highlighting the practical relevance of the approach.

weaknesses:
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?

questions:
Please refer to weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730216357413

thread_type:
official_review

<thread_object>
creator: reviewer_kuee

<content>
summary:
This paper studies submodular maximization in a noisy model. Formally, the goal is the same as in the standard monotone submodular maximization with cardinality or matroid constraints, but the algorithm has access to the function via a noisy oracle. In particular, given a set $S$ and element $x$, the algorithm can query $(S,x)$ to the oracle and receives a random (unbiased) estimator of the marginal value of $x$ with respect to $S$. The authors assume that such estimator is subgaussian (of parameter $R$ that is known).

The paper's contribution is to provide tight approximation results for cardinality and matroid constraints by adapting known techniques with a sample efficient estimation procedure called Confident Sample (CS).

strengths:
Submolar maximization is a relevant topic for the NeurIPS/ICML/ICLR audience, given its vast applicability in ML. The model of noisy queries is natural and well-motivated. The sample complexity bounds are not trivial (as the authors explain, using Hoeffding would already yield some results).

weaknesses:
- 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. 
- The sample complexity bounds are pretty involved. Many parameters are entailed, and a clear picture is difficult to get.

questions:
Do you have any tightness results on the sample complexity?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730964653057

thread_type:
official_review

<thread_object>
creator: reviewer_jmtb

<content>
summary:
The paper studies the constrained submodular maximization under noise problem that arises in many applications in AI and ML Communities. The key algorithm of this work is Confident Sample (CS), which is inspired by algorithms for best-arm-identification in multi-armed bandit. The CS algorithm can then be integrated into many existing approximation algorithms for submodular maximization under constraints. The authors show that the integrated algorithms take fewer samples on both theoretical and practical sides.

strengths:
- This work studies an interesting and meaningful research problem in the AI ​​and ML community. The paper is well-written and structured. 
- The core algorithm, Confident Sample (CS), has been shown to be effective in estimating the expectation of the objective submodular function in Gause distributions. The theoretical analysis is natural and reliable. However, the techniques for proving them are pretty elementary.

weaknesses:
- 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.
- The idea of the CS algorithm is not new. It existed in previous algorithms (For example, in Alg 2 in [Mat]). 
- It is natural to apply CS algorithms to existing algorithms, but it is not difficult to derive theoretical bounds.

======================

Ref. 

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

questions:
1. What are the differences (ideas, theoretical analysis) between CS and Alg 2 in [Mat]?
2. What are the challenges in getting better theoretical bounds when applying CS algorithms to existing algorithms?
3. Does the CS algorithm work well with other distributions?
4. 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731136069543

thread_type:
official_review

<thread_object>
creator: reviewer_nxxo

<content>
summary:
The topic of this paper is the problem of submodular maximization:
given a ground set $U$ and a an oracle access to a
submodular objective function $f: U \to \mathbb{R}$,
our task is to find $S\subseteq U$ with the highest value of $f(S)$.     
They study also the classical constrained versions where
we maximize $f(S)$ subject to cardinality and matroid constraints.

The authors study submodular maximization in the setting,
where
exact evaluation of $f(S)$ is not possible 
and one can obtain only noisy estimate. In particular, they assume
the oracle returns a noisy estimate which is unbiased and 
is $R$-subgaussian. 
This setting was already studied before, e.g. by Singla et al. '15, who
achieved almost the same approximation guarantees as in the classical
non-noisy setting and provided bounds on the number of the performed
noisy queries.      
Authors provide theoretical bounds which they compare to previous
works and they also present an empirical comparison.

The main difference between their work and Singla et al. '15
is that their algorithm is based on a faster implementation
of the classical greedy algorithm by Badanidiyuru and Vondrak which, instead
of comparing the marginal gain of the elements to each other, it compares
their marginal gain to a threshold chosen during algorithm's runtime.
Therefore, instead of a quadratic dependence on the gap $\Delta_{max}$
between the two top marginal gains, they have a quadratic dependence on the
gap from the threshold (their parameter $\phi$).

strengths:
The problem is important and their setting seems relevant and well motivated.
They achieve improvements in sample complexity over previous works at least in
some settings. They have a better running time as well.

weaknesses:
The results are somewhat difficult to appreciate for me,
despite that they provide more than a page long comparison with the
previous works in Appendix discussing the differences in the long formulas.
For example, it is not clear to me why is it better to have dependence
on $\phi$ instead of $\Delta_{max}$.
Is $\phi$ always smaller than $\Delta_{max}$?

I am not an expert in the field. While I see that the authors do achieve
an improvement over the previous works, I do not see its significance.
Therefore my rating.

questions:
* Can you comment on the weakness above?

* Can you say that your algorithm has a better sample complexity
than the previous works always?

* 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732322852075

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Additional response to all reviewers

comment:
Here we address comments made by several reviewers questioning how novel the subroutine Confident Sample (CS) is within submodular optimization (Reviewers jMtB and KUeE). To the best of our knowledge, an adaptive sampling procedure similar to CS has not previously been proposed. What is commonly used in submodular optimization algorithms is what we call a "fixed $\epsilon$-approximation" in the paper (see Section 2). A fixed $\epsilon$-approximation is essentially when one applies a concentration inequality such as Hoeffding's for a fixed number of noisy samples such that the empirical mean of the evaluated random variable $X$ satisfies that $|\hat{X}-\mathbb{E}[X]|\leq\epsilon$.

The fundamental reason this approach is less efficient compared to CS is that we are only interested in determining whether $f(X)$ is approximately above a threshold or not, not in obtaining a precise approximation. In other words, we don't need the guarantee that the $|\hat{X}-\mathbb{E}[X]|\leq\epsilon$ in Hoeffding's inequality; instead, we care about whether $\mathbb{E}[X]\geq w$. Ideally, we would approximate $f(X)$ just finely enough to determine if it's above the threshold. However, this isn't feasible with the fixed $\epsilon$-approximation, because we don't have any prior knowledge of how far $f(X)$ is from the threshold. Thus, we can't determine the required number of samples, and the fixed $\epsilon$-approximation approach requires a single batch of i.i.d. samples.

In contrast, CS uses an adaptive sampling approach where samples are iteratively taken one-by-one until an evolving confidence interval crosses a threshold. The goal is to use fewer samples compared to a fixed $\epsilon$-approximation. While CS might initially seem similar to fixed $\epsilon$-approximation, there are several critical differences that introduce unique technical challenges:

- Fixed $\epsilon$-approximation approach has a batch of samples in which a single application of a concentration inequality is applied in order to approximate $\mathbb{E}[X]$. In contrast, in CS, we apply a concentration inequality after every single sample, and then take a union bound over all the applications. However, this is challenging because we don't know how many samples we will end up taking to approximate the mean value sufficiently well since that depends on the result of the sampling. So we have to carefully design our confidence intervals.
- Fixed $\epsilon$-approximation approach takes a predetermined number of samples, independent of the sampling results. In contrast, the CS algorithm dynamically determines the number of samples based on the outcomes of previous samples. Additionally, CS reuses samples across multiple applications of concentration bounds, enhancing its efficiency.
- In CS, the size of the confidence interval evolves with each additional sample, shrinking as the number of samples increases (see Theorem 1). Additionally, when applying concentration inequalities, the failure probability is adjusted dynamically based on how many samples we've taken so far (Lemma 6). The benefit of the varying failure probability is that the obtained sample complexity $\frac{8R^2}{\phi_X^2}\log\left(\frac{16R^2}{\phi_X^2}\sqrt{\frac{2}{\delta}}\right)$ won't suffer from small values of $\epsilon$.
- In Theorem 2 and 4, we use a combination of Hoeffding and Chernoff that is well-suited to the threshold algorithms, rather than using one or the other. This approach improves the sample complexity from $O(R^2)$ in Theorem 1 to $O(R)$ when $R$ is large.

From a high-level perspective, we want to point out that the sample complexity of submodular optimization problems with stochastic noise usually originated from two reasons: (1). The query complexity of submodular optimization algorithms for the exact oracle value setting (no noise); (2). The sample complexity of estimating the expectation of the submodular objectives. The sample complexity of (2) is usually overlooked and addressed in a simple way. We highlight that the second part, as mentioned by the reviewer JMtB, is usually achieved by only taking a fixed number of samples and is therefore not sample-efficient enough. We minimize the samples required in this process by adaptively deciding when to stop. The only work to the best of knowledge that also uses the adaptive sampling idea is [1] which incorporate the best-arm identification algorithm into the standard greedy approach. However, the algorithm is also not sample-efficient and runtime-efficient. Moreover, 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.

[1] Singla, Adish, Sebastian Tschiatschek, and Andreas Krause. "Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization."
</content>
</thread_object>

</thread>
<thread>
creation date:
1732325718890

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to all reviewers and ACs

comment:
We thank the reviewers for their thoughtful comments. We also appreciate the positive feedback received on the paper, including:
- The problem considered in the paper is interesting and meaningful in the AI and ML community (Reviewers jMtB and KUeE), and the setting is relevant and well-motivated (Reviewers NxXo and KUeE).
- The sample complexity bounds are not trivial (Reviewer KUeE), and the theoretical results of the paper are robust (Reviewer XgDq).
- The theoretical insights are supported by empirical evaluations on real-world datasets (Reviewer XgDq).
- The adaptive sampling in the paper is different from existing fixed-precision methods (see Section 2 for a definition of fixed $\epsilon$-approximation) (Reviewer XgDq).
- The algorithms are a competitive alternative to existing ones (Reviewer XgDq).
- The paper is well-written and structured (Reviewer jMtB).

Several reviewers made comments questioning how our sampling subroutine Confident Sample (CS) is different compared to sampling approaches existing in the submodular optimization literature (Reviewers jMtB and KUeE). We address these remarks in a separate comment at https://openreview.net/forum?id=vtCkb4KJxr&noteId=7unTbMJ62F.

We have uploaded a revised version of the manuscript, incorporating reviewer feedback with changes highlighted in blue. The updates include:
- A discussion of the technical challenges and a comparison with the fixed $\epsilon$-approximation approach (Appendix C.1).
- Detailed description and explanation of the results of sample complexity. (Sections 3 and 4).

We believe these revisions have improved the paper and welcome further feedback. Below are our detailed responses to individual reviewer comments.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies the problem of maximizing a submodular function in the setting where we only have access to noisy evaluations of the marginal gains. Specifically, the noisy evaluations are assumed to be iid samples from a sub-Gaussian distribution. This setting mirrors exactly that of a prior work (Singla et al., 2016), who studied the cardinality constrained problem and proposed an algorithm based on the standard Greedy algorithm. The current paper considers the cardinality constrained problem as well as a more general matroid constraint and unconstrained non-monotone maximization. The current work shows how to implement the well-known descending thresholds Greedy algorithm for submodular maximization using noisy evaluations, and achieve a smaller sample complexity, particularly in practice. The main contribution is a procedure called Confident Sample (CS) that implements the main step of the algorithm using noisy samples: given an element and a threshold, determine whether the marginal gain of the element on top of the current solution exceeds the threshold. Instead of taking a fixed number of samples in order to estimate the marginal gain sufficiently accurately, the CS algorithm only takes enough samples to determine whether the gain is above the threshold. This is beneficial in practice, since we only need to take the worst-case number of samples only when the marginal gain is very close to the threshold. The paper gives theoretical guarantees that quantify the improvement in the sample complexity parameterized by how far away the marginal gain is from the threshold, and it empirically evaluates the improvement on data summarization instances.

The problem studied is well motivated and relevant for machine learning applications. The proposed algorithm has the potential to reduce the number of samples taken in practice compared to other approaches based on worst-case concentration results, which give pessimistic bounds when the marginal gain is far from the threshold. A major weakness noted by the reviewers is that the overall contribution is modest. The main contribution is the application of the CS algorithm to the well-known descending thresholds algorithm. The CS algorithm itself is novel and the analysis poses some challenges but, as Reviewers JMtB and KUeE noted, the novelty in the algorithm design and the analysis is limited.