acceptodds
Under review as a conference paper at ICLR 2027

Mini-batch Submodular Maximization

Abstract

We present the first mini-batch algorithm for maximizing a non-negative monotone decomposable submodular function, , under a set of constraints. Our experiments demonstrate that a straightforward uniform mini-batch sampling approach significantly outperforms existing state-of-the-art sparsifier methods, requiring only a fraction of their running time. However, explaining this improvement via worst-case analysis is impossible. Under mild assumptions, we show that uniform sampling is superior to weighted sampling for both the mini-batch and sparsifier approaches. We further verify empirically that these assumptions hold across various datasets. Unlike weighted sampling, uniform sampling is simple to implement and several orders of magnitude faster, making it ideal for handling massive real-world datasets.

Primary area:
optimization
Keywords:
Submodular maximization, smoothed analysis, mini batch

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_fsDoOpenReview ↗
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 (F=∑I=1Nfi)(F=\sum_{I=1}^N f^i) are expensive to optimize, since using the naive greedy would result in paying for all the NN components. Each evaluation is counted as an oracle call, hence, the greedy algorithm requires O(Nnk)O(Nnk) 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 F^\hat{F} is ϵ\epsilon-sparsifier for FF if it satisfies w.h.p that ∀S⊆E,(1−ϵ)F(S)≤F^(S)≤(1+ϵ)F(S)\forall S\subseteq E, (1-\epsilon)F(S)\leq\hat{F}(S)\leq(1+\epsilon)F(S).

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 γ=2k\gamma=2k, which is indeed important to yield the approximation guarantees. Putting it into the batch size of Theorem 2.3 gives α=C⋅2k⋅log(n)ε2⋅ϕ\alpha = \frac{C\cdot 2k\cdot log(n)}{\varepsilon^2\cdot\phi}. I computed this batch size for various datasets, and in most cases the theoretical guarantees do not hold. For instance, let k=20k=20, ε=0.1\varepsilon = 0.1, 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
  1. 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?
  2. Can you further justify the reduced running time claim by adding wall-clock time comparison? Is the effect there significant?
7 comments

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.

Thank you for the response.

Thank for confirming the computation regarding the batch size. Indeed, the cost advantage is explained by avoiding the O(Nn)O(Nn) 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 Ω(N)\Omega(N) preprocessing is indeed a separation. But other than it, the paper compares k2n2/ε2k^2n^2/\varepsilon^2 with k2n/(ε2ϕ)k^2n/(\varepsilon^2\phi), both of them are upper bounds. The extra nn comes from the worst-case bound ∑ipi≤n\sum_i p_i \leq n (Lemma F.1), which is close to 11 when components are similar, and the uniform bound is worse when ϕ<1/n\phi < 1/n. 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 nn comes from the worst-case bound ∑ipi≤n\sum_i p_i\le n (Lemma F.1), which is close to 11 when components are similar, so the claim that uniform is theoretically better in general is weak.

You are right that the execution terms, k2n2/ε2k^2n^2/\varepsilon^2 for weighted and k2n/(ε2ϕ)k^2n/(\varepsilon^2\phi) for uniform, are both upper bounds and that nn is the worst case of ∑ipi\sum_i p_i. Neither dominates the other on every instance, and we will change the abstract sentence accordingly. The separation we claim is the Ω(N)\Omega(N) 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 ϕ\phi, which is far from its pathological value 1/N1/N 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 (N,n,ϕ)(N,n,\phi); 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 10610^6 to 10810^8 on their own MovieLens experiment, which runs only 2000 iterations. What the theory explains is the shape of the cost, no dependence on NN and a 1/ϕ1/\phi 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 10−4N10^{-4}N; we see this as a strength, not a gap. Second, ϕ\phi is a property of the data distribution, not of NN. For example, in the paper we measured ϕ=0.35\phi=0.35 on FashionMNIST (N=50,000N=50{,}000); for this rebuttal we further measured it on EMNIST (N=697,932N=697{,}932) and it is 0.320.32. We do not see this changing as NN grows, and are happy to verify it on larger datasets of your choice. Since our batch size does not depend on NN, it becomes a vanishing fraction of NN as datasets grow.

Edits we will make.

(1) Abstract: "uniform sampling is superior to weighted sampling" becomes "uniform sampling matches weighted sampling without its Ω(N)\Omega(N) 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 ε\varepsilon, and that the theory explains the dependence, not the constants.

(4) A related-work paragraph on stochastic submodular maximization.

Reviewer_FgZVOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the maximization of decomposable monotone submodular functions and proposes a mini-batch algorithm that draws a fresh uniform sample at each greedy iteration. It provides theoretical query complexity guarantees in terms of a singleton density parameter. The problem is practically relevant, and the proposed algorithm is simple and easy to implement.

Critical strengths

Simple and practical algorithmic design. Drawing a fresh uniform mini-batch at each greedy iteration avoids the costly preprocessing required by weighted sampling. Its simplicity makes the approach appealing for large decomposable objectives.

Broad empirical evaluation. The paper evaluates the method on five datasets spanning several applications and considers both cardinality and pp-system constraints. This breadth provides evidence that its practical benefits extend beyond a single task or constraint setting.

Critical weaknesses

The smoothing model does not sufficiently justify describing the assumptions as “mild”: it requires a common element e∗e^* whose expected contribution is bounded below for every component, together with a bounded-dependence condition across components. These requirements may be restrictive in applications with heterogeneous preferences or strongly correlated data.

The experimental implementation uses a lazy-greedy heuristic whose upper bounds are no longer valid when the mini-batch changes, leaving a gap between the theoretical guarantees and the reported results.

Questions for authors

Although Appendix G includes a comparison with stochastic-greedy from Lazier than Lazy Greedy [24], how much additional improvement does the proposed method offer over this baseline in terms of solution quality and computational efficiency?

Reviewer_JHmdOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper provides an algorithm for maximizing a non-negative monotone decomposable submodular function under some constraints. The proposed uniform mini-batch sampling algorithm is a simplified version of the state-of-the-art weighted sparsifier method. The proposed algorithm can achieve better utility scores while reducing the number of oracle class by avoiding a costful pre-processing steps of the sparsifier method. While the worst case anallysis is impossible, the proposed method can achieve better theoretical results under a realistic assumption.

Critical strengths

This paper provides a simple but strong method for an important subclass of submodular maximization problem. The paper provides an interesting finding that a simple uniform sampling-based method practically works better than a worst-case guaranteed baseline method.

Another strength of the paper is its presentation. Introduction provides a sufficient overview to understand the contributions of the paper. Although it contains complex math, I feel no difficulty for reading the paper.

Critical weaknesses

I can find no major weaknesses. Although the worst case performance of the proposed method is not guaranteed, this paper provides multiple experimental evidences showing the effectiveness of the proposed method.

Questions for authors

(Optional question) I'm interested in the cases of non-monotone submodular functions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.