A near linear query lower bound for submodular maximization

Thank the reviewer for the suggestion on the exposition on the writing. We include a technique overview section (Section 1.1) in the updated paper that discusses our technical contribution in detail.

The algorithm for the additive function, presented as one of the key results in the paper, is insufficiently explained. Additionally, the authors do not discuss any related work in this area, leaving questions about how their work compares with prior studies on similar problems. A comparison with relevant literature would strengthen the paper by situating this result within the broader context of related research.

We discuss the intuition of our algorithm in Section 1.1. We do not find literature that studies the same problem (i.e., query complexity for additive function).

Several theoretical contributions, including the final theorem, are not fully clarified. Without adequate explanations, readers may struggle to understand the implications and validity of these findings.

Can you point out to us which theorem is not adequately explained?

Although the authors present proofs for their main results, they do not discuss the technical innovations and challenges in sufficient depth. A clearer articulation of the novel aspects of their approach would help readers appreciate the paper's unique contributions.

See Section 1.1 in the updated paper.

It is claimed that this paper produces query-efficient algorithms for estimating the optimal value of the studied problem, but there is no experimental evidence to support the claim in the paper.

The paper in its current version is a theoretical study, which settles important problems in the literature. We leave empirical study for future study.

The paper introduces an algorithm that estimates the optimal value of the problem of additive function maximization under cardinality constraint. What is the related work of this algorithm and how does this compare to existing results?

We do not find literature that studies the same problem (i.e., query complexity for additive function).

What are the major technical difficulties the authors overcome in proving the lower bound of the query complexity for the submodular maximization problem?

See Section 1.1 in the updated paper, our technique is completely different from previous work.

Thank you for your response. I would like to provide further clarification on my review.

The contribution of the paper seems limited. The inapproximability result on query complexity provided in Theorem 3.7 is $\Omega(\alpha^5 n/\log^2(n))$, with $k\le O(\alpha n)$. However, [1] proves that an $(\beta+\epsilon)$-approximation algorithm obeying $k = \beta n$ must use $\Omega(n/\log n)$ value oracle queries, which is tighter than the one provided in Theorem 3.7.

Let me clarify my comment further. [1] provides two inapproximability results on query complexity: $\Omega(\alpha n/k)$ and $\Omega(n/\log n)$, where the first one holds for all $k$ values and the second one holds when $k = \beta n$ and $\beta+\epsilon$ is the approximation ratio. Upon careful consideration, I realized that the improvement in this paper lies in providing a tighter bound on the query complexity for cases where $k=\Omega(\log^2 n)$ and $k = o(n)$. However, this is not clearly stated in the paper. As I mentioned in the weakness, the paper's presentation is lacking in clarity.

When the oracle is discussed on Line 031, it is unclear what the oracle model is….

I do agree that the oracle returns the exact value of $f(S)$ is a standard setting in theoretical research. However, there are also other settings for the value oracle. The main point here is not about discussing different settings of value oracle. Instead, the paper should clearly specify what the value oracle refers to. Both the definition on Line 032 and the example on Line 033 are unclear and confusing.

Our algorithm can first be used to assess whether the dataset is sufficiently valuable—that is, whether it contains $k$ elements with large values.

This might be a good point for the motivation. However, it should be more specific if such applications exist. I agree with Reviewer GZiL's comment that the authors do not discuss any related work in this area. Based on your response, there appears to be no related work addressing this problem. In that case, the motivation needs to be detailed enough to help readers understand why this problem is worth studying. The lack of discussion on both related work and potential applications is insufficient.

$**Summary.**$ This paper provides an improved inapproximability result on query complexity with $k$ range from $\Omega(\log^2 n)$ and $o(n)$. However, this result should be highlighted in the paper rather than left for the reader to uncover. Also, the motivation for studying the approximation of the optimal value is insufficiently addressed. Overall, the paper’s writing lacks clarity and needs significant improvement.

We thank the reviewer for their feedback. In the rebuttal, we clarify why our lower bound is significantly stronger than previous work, both conceptually and technically.

The paper's presentation is lacking in clarity. Some definitions are not as precise and formal as in other works. For example, the definition of submodular on Line136 is wrong….

Thanks for the correction, we revise the definition according to your suggestion.

The contribution of the paper seems limited. The inapproximability result on query complexity provided in Theorem 3.7 is $\Omega(\alpha^5n/log^2(n))$, with $k\le O(\alpha n)$. However, [1] proves that an $(\beta+\epsilon)$-approximation algorithm obeying $k = \beta n$ must use $\Omega(\frac{n}{\log n})$ value oracle queries, which is tighter than the one provided in Theorem 3.7.

We respectfully disagree with this assessment. Our lower bound is significantly stronger than the previous work [1]. The lower bound in [1] applies only to the case where $\beta = \Theta(1)$ (see Theorem 4.2 in their paper). This implies that their lower bound is restricted to the regime where the subset size is linear, $k = \Theta(n)$. As discussed in our paper, this is an uncommon setting. In most of the literature, it is implicitly assumed that $\Omega(\log n) \leq k \leq o(n)$ as values outside this range can lead to anomalous results (see the paragraph starting at Line 68 for more details).

From a technical standpoint, their lower bound is derived using a simple counting argument. Specifically, they argue that determining the $k$ most valuable elements (assuming a linear function where these elements have value 1, while others have value 0) requires $k$ bits of information. Since each query reveals only $\log⁡(n)$ bits of information, this results in a lower bound of $k/\log⁡(n)$ queries. However, this approach clearly cannot be generalized to establish a $\tilde{\Omega}(n)$ lower bound when $k=o(n)$.

In contrast, our approach employs entirely different and more sophisticated techniques. We rely on a reduction from query complexity to communication complexity, leveraging a communication lower bound based on advanced methods such as information complexity and the distributed data-processing inequality. Additionally, our construction of the hard instance involves a novel two-level truncation technique. For further details, please see Remark 1.1 in the updated version of our paper.

We would be happy to provide further clarification on this point and to elaborate on why our lower bound is both significantly stronger and derived using non-trivial techniques.

When the oracle is discussed on Line 031, it is unclear what the oracle model is….

We assume the oracle returns the exact value of f(S), which is the standard setting in theoretical research. We acknowledge that real-world applications may involve noise and may not strictly adhere to the submodularity or linearity assumptions. This is a challenge faced by all theoretical studies, and extending the work to account for noisy settings is an exciting direction for future research. (We also note that our algorithm can be generalized to tolerate small amounts of noise.)

Typically, approximation algorithms find a subset with a constant approximation ratio for the objective value. In this paper, the algorithm approximates the optimal value. Its potential applications are not discussed.

This has been a typical goal for sublinear algorithms now (e.g., see [1,2]). In terms of application, consider a scenario where one needs to select a subset from a large dataset under a budget constraint of $k$. Our algorithm can first be used to assess whether the dataset is sufficiently valuable—that is, whether it contains $k$ elements with large values. If the dataset meets this criterion, one can proceed with further analysis or selection; otherwise, unnecessary efforts can be avoided.

[1] Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, and David Wajc. SODA 2023

[2] New Streaming Algorithms for High Dimensional EMD and MST. Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten. STOC 2022

Thank you for your quick response. We have updated our paper to address your concerns regarding the writing. All changes in this round are highlighted in blue. Specifically:

1. We have added motivations for studying the approximation of the optimal value. Please refer to the paragraph at Line 92.

2. We now emphasize the improved lower bound for $k$ ranging from $\Omega(\log^2(n))$ to $o(n)$, see Line 57 and Line 71.

3. We highlight our focus on the exact value oracle model. See Line 210.

Please let us know if there are additional concerns regard paper writing, thanks!

We thank the reviewer for the insightful comments!

This is interesting because it shows that finding the approximate value where the objective is linear is not as hard as the general case. But the linear setting is very restricted, and so I'm not sure that there is much value for this algorithm in applications.

We agree that the linearity assumption might be too strong for certain practical applications. However, in many large-scale machine learning scenarios, the "linearity" assumption often holds approximately. For instance, in the data valuation task, [1,2] employ a linear function to measure the value of individual data points, demonstrating strong empirical performance.

[1] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Data-models: Predicting predictions from training data. ICML 2022.

[2] Understanding Black-box Predictions via Influence Functions. Pang Wei Koh, Percy Liang. ICML 2017

​​The paper is missing an important citation. Theorem 4 of Kuhnle [2021] (referenced below) actually gives the lower bound of before the work of Li et al..

Many thanks for pointing this out, we added the reference to our paper.

Could you provide intuition for why the more complicated reduction to distributed set detection gives these stronger bounds, compared to approaches more similar to Li et al.?

The distributed set detection task has a linear $\tilde{\Omega}(n)$ communication lower bound regardless of the choice $k$ – this is the key reason that we can lift it to a linear query lower bound for submodular maximization. From a technical perspective, the communication lower bound for distributed set detection relies on advanced techniques such as information complexity and the distributed data processing inequality. This might explain why our approach results in a stronger lower bound.