- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This work focuses on maximizing a decomposable sumbodular function under both cardinality and p-system constraints. Generally speaking, these type of functions are expensive to optimize, since using the naive greedy would result in paying for all the components. Each evaluation is counted as an oracle call, hence, the greedy algorithm requires oracle calls.
One option to avoid this, is to use a sparsifier-based approach, which evaluates a weighted subset of the components instead of all of the components. Theoretically speaking, a sparsifier is -sparsifier for if it satisfies w.h.p that .
However, choosing the weighted subset of these components (with their corresponding weights) is the main pre-processing bottleneck step in prior work. In this work, the authors study theoretically and empirically a uniform sampling (draw a new subset in every greedy round) to overcome this bottleneck.
The authors provide theoretical analysis and insights of the suggested approach (Algorithm 2), as well as empirical study on various datasets. Empirical evaluation shows that weighted sampling approaches is impractical due to its cost bottleneck, and the relative performance is comparable and sometimes even better than weighted sampling.
Critical strengths
The approach studied in this work is simple and has useful observation. Uniform subsampling is cheap, intuitive, and empirically strong. I have went through the theorems and proofs, and the proofs are correct and sound. The writing is very clear and easy to follow.
Critical weaknesses
Although I like the approach and the empirical evaluation is convincing, I have two major concerns:
Theoretical guarantees - do they cover the empirical evaluation?: I have tried to verify whether the guarantees hold also for empirical subset sizes (for example, k=5,10,20,...) as used in the empirical evaluation, and this is not clear or at least straightforward.
In the proof of Theorem 2.4 (specifically speaking, line 274), the authors set , which is indeed important to yield the approximation guarantees. Putting it into the batch size of Theorem 2.3 gives . I computed this batch size for various datasets, and in most cases the theoretical guarantees do not hold. For instance, let , , and the batch size required for FashionMNIST, CIFAR100, and Facebook is significantly larger than the number of components. I believe an additional paragraph explaining when the theoretical guarantees hold would significantly improve this work.
Novelty and related work: I believe there are some missing related work in this paper, mainly stochastic submodular maximization papers, such as:
- Mokhtari, Aryan, Hamed Hassani, and Amin Karbasi. "Conditional gradient method for stochastic submodular maximization: Closing the gap." International Conference on Artificial Intelligence and Statistics. PMLR, 2018.
- Hassani, Hamed, Mahdi Soltanolkotabi, and Amin Karbasi. "Gradient methods for submodular maximization." Advances in Neural Information Processing Systems 30 (2017).
I believe novelty is a bit overstated as well, but I do not flag this as a critical weakness, but as a minor one, since this paper theoretically and empirically studies an efficient and simple approach.
I am currently slightly leaning toward rejection, but I am looking forward to discuss these points with the authors in the rebuttal period.
Questions for authors
- This work states that uniform sampling is theoretically better than weighted one. However, we are comparing upper bounds. How confident are you that this gap is real, and not an effect cause by the analysis?
- Can you further justify the reduced running time claim by adding wall-clock time comparison? Is the effect there significant?
7 comments
Thank you for the response.
Thank for confirming the computation regarding the batch size. Indeed, the cost advantage is explained by avoiding the preprocessing, but the solution quality is not, since the guarantee does not cover the batch sizes used on most of the experiments. The claim in the introduction about why it outperforms weighted sampling in practice should be softened, and the paper should state when does the guarantee hold.
I agree that the preprocessing is indeed a separation. But other than it, the paper compares with , both of them are upper bounds. The extra comes from the worst-case bound (Lemma F.1), which is close to when components are similar, and the uniform bound is worse when . So the claim that uniform sampling is theoretically better in general is weak as I see it.
Regarding related work, stochastic submodular maximization already uses mini-batches, though in the continuous setting. "The first mini-batch algorithm" should be stated more carefully, with a short comparison to these works.
Overall, my main concern remains, the theory is presented as explaining the empirical results, but it does not cover the experimental settings. Since this affects how the main claims are framed, I keep my score.
Thank you for the clarification. It looks like we are mostly in agreement, and the remaining issues are ones of presentation. Please let us know if the explanations below and the suggested edits resolve your main concerns.
Stochastic submodular maximization already uses mini-batches, though in the continuous setting. "The first mini-batch algorithm" should be stated more carefully, with a short comparison to these works.
Agreed. Mokhtari et al. (2018) use greedy on a fresh sample of users at every step as an experimental baseline, and Hassani et al. (2017) use greedy on a fixed sample, in both cases without analysis. We will restate our contribution as the first analysis of the mini-batch greedy algorithm, add both works to the related work, and note that in the finite-sum case their unanalyzed baselines are our uniform mini-batch algorithm and uniform sparsifier, respectively.
The paper compares two upper bounds. The extra comes from the worst-case bound (Lemma F.1), which is close to when components are similar, so the claim that uniform is theoretically better in general is weak.
You are right that the execution terms, for weighted and for uniform, are both upper bounds and that is the worst case of . Neither dominates the other on every instance, and we will change the abstract sentence accordingly. The separation we claim is the preprocessing, which uniform sampling avoids and no weighted scheme can: its probabilities are computed from the component values, so every component is queried before the first greedy step. Removing this term, verifying experimentally that nothing is lost, and giving a theoretical account of why (the dependence on , which is far from its pathological value on every dataset we measured) is the contribution.
The solution quality is not covered, since the guarantee does not cover the batch sizes used in most experiments.
The guarantee is a worst-case bound over all instances with the given ; real data has structure the concentration bounds do not use, and the algorithm works far below the bound. This is the usual situation: in the two works above, the iteration bounds of Theorem 4.7 (Hassani et al.) and Corollary 6 (Mokhtari et al.) are of order to on their own MovieLens experiment, which runs only 2000 iterations. What the theory explains is the shape of the cost, no dependence on and a dependence, not the constants, and we will say so explicitly.
Two further points. First, the experiments show the algorithm is robust well below the bound, down to batches of ; we see this as a strength, not a gap. Second, is a property of the data distribution, not of . For example, in the paper we measured on FashionMNIST (); for this rebuttal we further measured it on EMNIST () and it is . We do not see this changing as grows, and are happy to verify it on larger datasets of your choice. Since our batch size does not depend on , it becomes a vanishing fraction of as datasets grow.
Edits we will make.
(1) Abstract: "uniform sampling is superior to weighted sampling" becomes "uniform sampling matches weighted sampling without its preprocessing"; "the first mini-batch algorithm" becomes "the first analysis of the mini-batch greedy algorithm".
(2) Section 1: drop "which explains why it outperforms weighted sampling in practice".
(3) After Theorem 2.4, a paragraph stating when the guarantee is non-vacuous and which of our datasets this covers at which , and that the theory explains the dependence, not the constants.
(4) A related-work paragraph on stochastic submodular maximization.
Dear Reviewer, the discussion period ends soon, and we wanted to check whether our response addressed your concerns. If anything is still open, we’d be glad to clarify.