A Near Linear Query Lower Bound for Submodular Maximization

Yes

I have not checked in detail but overall the claims and sketches make sense

N/A

The paper is of interest to the submodular community.

None that I know of

Fine.

The high-level ideas seem fine and sound.

This theoretical paper focuses on impossibility results, rendering experiments inapplicable.

.

.

N/A

I only checked the proofs in the main part of the paper and not the appendix.

N/A

Previously, this problem had a general $\Omega(n/k)$ lower bound and also a $\Omega(n)$ lower bound when $k=\theta(n)$ but they could show that this lower bound holds for any $k$.

No

yes

I checked all proofs except those of Lemmas 3.5, 4.3, 4.5, 4.6 and Theorems 4.1 and 4.7.

The proofs I checked are correct, but have some typos and steps which are not well explained. In general, more details and intuitive explanations should be provided in the proofs.

• In the proof of Lemma 3.6, $Pr[i_1 \in \mathcal{I}]$ should be $Pr[i_1 \in \hat{\mathcal{I}} \mid V = 1]$ on line 648-649 and $Pr[i_1 \in \hat{\mathcal{I}} \mid V = 0]$ on line 652-653. I think the latter should be equal to $|\mathcal{I} \cap \hat{\mathcal{I}}| / (n- k + 1)$ instead of $|\mathcal{I}| / (n- k + 1)$ (the lemma is still correct though as this is a valid upper bound). Also, more explanation should be given for why the equalities on both these lines hold.

• In the proof of Theorem 3.2, it's not clear why the first inequality on TV holds.

• In the proof of Lemma 3.10, the second inequality bounds the probability that $\sum_t X_{t, i}$ deviates from its mean by more than $\epsilon m/2$, while the Lemma requires bounding the probability of $\sum_t X_{t, i}$ not being in $(\epsilon m/2, 2 \epsilon m)$, so the bound given doesn't actually match that. The lemma is still correct, but the proof needs to corrected.

• In the proof of Lemma 4.4, give more details for why the first two inequalities hold (1st one can be proved by induction, for 2nd one remind the reader of how all these quantities are related..). Moreover why is Azuma-Hoeffding bound needed, this bound holds by Hoeffding inequality.

No experiments included.

Obtaining constant factor approximation algorithms for monotone submodular maximization with low query complexity is important for applications where function evaluations are costly, such as neural networks training and influence maximization. Estimating the optimal value is also valuable in some cases, for example to assess dataset quality before proceeding with further analysis or selection, or as a subroutine in some submodular optimization algorithms.

Existing query bounds for constant factor approximation in monotone submodular maximization are $\Omega(n / k)$ for any $k$ and $\Omega(n / \log n)$ for $k = \Theta(n)$. These bounds rule out sublinear query complexity algorithms for $k = \Theta(1)$ and $k = \Theta(n)$. This work strengthen these impossibility results, showing that sublinear query complexity is also not possible for any $k \ll n$. This is particularly relevant as many applications involve $k$ that is not constant but still much smaller than $n$.

The lower bound $\tilde{\Omega}(n)$ provided here holds for the special case of modular functions too. This is also the case for the existing $\Omega(n / \log n)$ bound (see Theorem 4.2 in (Li et al., 2022)) but not for the $\Omega(n / k)$ bound. The provided lower bound holds also for estimating the optimal value of a monotone submodular function. I am not aware of other existing lower bounds for this.

Existing algorithms for submodular maximization achieve a $(1 - 1/e - \epsilon)$-approximation, using $O(n \log(1 /\epsilon))$ queries with a randomized algorithm, and $O(n/\epsilon)$ queries with a deterministic algorithm. So the $\tilde{\Omega}(n)$ query lower bound in this paper is tight up to log factors.

From a technical perspective, prior lower bounds are based on counting arguments. This paper uses novel techniques. Namely the lower bound for finding an approximate solution is derived via a reduction from the query complexity of submodular maximization to the communication complexity of a problem called distributed set detection. The lower bound for estimating the optimal value of a monotone submodular function is obtained by constructing a challenging submodular instance.

The proposed algorithm for estimating the optimal value of a monotone modular function uses two intuitive subroutines. I am not aware of existing algorithms for this problem that use sublinear queries, so this might be the first.

The lower bound $\Omega(n / \log n)$ for $k = \Theta(n)$ provided in (Li et al., 2022) holds for the special case of monotone modular function too (see Theorem 4.2 therein). This should be mentioned.