acceptodds
Under review as a conference paper at ICLR 2027

Nearly Linear Oracle Algorithms for Submodular Maximization under Matroid and Polymatroid Constraints

Abstract

We give nearly linear oracle algorithms for monotone submodular maximization under general matroid constraints and monotone DR-submodular maximization over integral polymatroids, with expected approximation and polynomial accuracy dependence. Short exchange walks and controlled endpoint bias make rounding inexpensive. For independence-oracle fractional optimization, private filtering progress and a smaller contraction minor support multilevel preprocessing. For polymatroids, we obtain nearly linear query complexity even at exponentially large numerical rank. Random gaps between capacity scales permit a nearly feasible product relaxation, while an integer baseline removes absolute capacity size from marginal threshold ranges. Poisson smoothing and colors allow large count increments; geometric searches with analytical shadow counts and aggregate latent-error concentration keep tests and samples inexpensive. A final shrink and approximate local covering complete the construction. The polymatroid algorithm uses value queries and expected integer-feasibility queries, where . An feasibility lower bound holds at rank exactly . All outputs are feasible on every run; the bounds count ordinary oracle calls rather than bit complexity.

Primary area:
optimization
Keywords:
Submodular Optimization, Approximation Algorithm, Matroid

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_EXriOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the question of optimizing a monotone submodular function subject to a matroid constraint (and, more generally, optimizing DR-submodular maximization over integral polymatroids).

It has been known for quite some time that we can obtain a (1-1/e)-approximation algorithm for this question using e.g. continuous greedy algorithm or non-oblivious local search. This guarantee is tight.

The focus of the submitted work is to obtain faster algorithms to achieve this optimal guarantee. In particular, the focus is on decreasing the number of oracle queries (valuation queries to the submodular function and independence queries to the matroid). The paper is the first one to achieve near linear running time and queries. The prior best was O(n + r^{3/2}) where r is the rank of the matroid. So this gives a significant improvement for matroids with large (close to linear rank) and the improvement is even more significant for polymatroids where we don't have r<=n.

The result is obtained by first devising a faster algorithm for computing a fractional solution (which could have been replaced by prior work if we don't worry about the polynomial dependency on the error parameter) and then a faster rounding algorithm.

Critical strengths
  • This is a central problem in discrete optimization and getting close to tight oracle enumerations is an interesting result.

  • The paper is overall well written and puts the result in the right context.

Critical weaknesses
  • It is unclear whether the paper is best seen as a machine learning paper or a more theoretical algorithms contribution. It seems as a more fitting venue may have been SODA. There are no experiments and there are no indications that the algorithms are easy to implement and would actually be faster than prior algorithms (when taking into account complexity and hidden constants etc.)
Questions for authors

Please explain why this is not only of theoretical interest and why you didn't implement and run some experiments to show that this may have more applied value (as raised in the weaknesses section).

Minor comments on exposition:

  • When you enumerate your results, it is a confusing 4 bullet list where 2 of the bullets is more the technical result of getting the main result, i.e., computing the fractional solution and rounding it. That is more of Technical statements (that can be interesting in themselves) but they are helping you to prove the main results.

  • In the statement of Theorem 3.1: what do you mean by "analytical comparison base"?

1 comment

Thank you for recognizing the significance of the oracle-complexity improvement and for the helpful suggestions on exposition.

Relevance to machine learning and practical performance. The original submission focused on theoretical oracle-complexity guarantees. We agree that experiments can help clarify the practical value and limitations of these results, and we have added component-level experiments in Appendix J.

A theoretical O~(n)\widetilde{O}(n) bound requires every stage of the algorithm to satisfy that bound in the worst case. A practical implementation faces a different question: which stage is expensive on the instance at hand? Applying every device needed by the worst-case analysis can introduce overhead at stages that a conventional implementation already handles efficiently. A useful implementation may therefore combine selected subroutines from this work with simpler methods elsewhere.

The polymatroid algorithm illustrates this distinction. In the exponential-rank regime r=2Θ(n)r = 2^{\Theta(n)}, we have log⁡r=Θ(n)\log r = \Theta(n), so an additional log⁡r\log r factor can prevent a nearly linear bound in nn. Our construction replaces several sources of numerical-rank dependence by dependence on the accuracy and on log⁡log⁡r\log \log r. Removing these rank factors is essential to our nearly linear analysis, but this tradeoff need not improve runtime when log⁡r\log r is modest: an additional factor polynomial in 1/ε1/\varepsilon can cost more than the rank dependence it removes. On the same instance, a different subroutine that removes an extra factor in nn at an accuracy cost may still be worthwhile. The practical value of each component should therefore be assessed separately.

Conventional greedy, search, and exchange methods can perform well in common regimes, and our control experiments include many cases where they are preferable. Their favorable behavior does not exclude specific instances with long exchange searches, many blocked candidates, repeated rebuilding, or costly count searches. We construct instances exposing these mechanisms and ask whether the corresponding subroutine helps. Different components are tested on different instances; we do not require all bottlenecks to occur simultaneously. This explains both the focus on components rather than the complete maximization pipeline and the use of uncommon, sometimes deliberately artificial, scenarios. The results identify regimes in which particular components help and the tradeoffs they entail. They do not establish uniform superiority or the prevalence of these regimes in applications.

Organization of the contributions. We agree that the current list mixes end-to-end results with their ingredients. We will separate the two main optimization guarantees—matroids and integral polymatroids—from the rounding and preprocessing tools that establish them.

“Analytical comparison base” in Theorem 3.1. This is a base used only in the proof. It starts as an optimal base and is updated through feasible exchanges as the algorithm selects the prefix SS, so that it continues to contain SS. The algorithm neither computes this base nor requires access to the optimum. The inequality in the theorem shows that the value gained by SS compensates, in expectation, for the value lost by this evolving comparison base. We will define it explicitly before the theorem.

Reviewer_og5oOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper makes a significant theoretical contribution to submodular optimization by reducing oracle complexity to nearly linear while preserving a near-optimal approximation guarantee. A key innovation is the use of short open exchange sequences, which avoid the cost of finding complete exchange cycles while incurring only a small, controlled loss in objective value. The paper also introduces a preprocessing procedure that reduces the sampling cost of fractional optimization. For integral polymatroids, it combines capacity-scale separation, integer baselines, batched count updates, and Poisson smoothing with geometric count searches and aggregate sampling-error analysis, thereby avoiding unit-by-unit processing. Together, these techniques constitute a substantial advance in the theory of submodular optimization.

Critical strengths

The paper reduces the oracle complexity of submodular maximization to nearly linear while preserving a near-optimal approximation guarantee. It addresses both fractional optimization and rounding for general matroids using ordinary independence queries. The rounding procedure uses open exchange sequences to control the loss in objective value without additional value queries, while the preprocessing reduces the sampling cost of fractional optimization. For integral polymatroids, the dependence on the numerical rank is only doubly logarithmic, so the algorithm can handle exponentially large capacities. These results contribute to the theory of submodular optimization.

Critical weaknesses

The comparison with prior work should clarify which limitations are overcome and which proof ideas lead to the improved bounds.

The paper would benefit from distilling its technical tools into standalone results and discussing whether they extend beyond the problems considered here.

The authors explicitly acknowledge using AI to generate some proofs, raising concerns about whether those arguments have been thoroughly checked. Given the manuscript’s length of approximately 80 pages, verifying these proofs places a substantial burden on reviewers.

Questions for authors
  1. Have any of the proofs been formally verified using a proof assistant? If not, have the authors independently checked all proofs, including those generated with AI assistance?

  2. Can the authors identify mathematical techniques or tools developed in this work that may apply more broadly?

  3. Could the authors clarify how AI contributed to developing the main ideas, constructing proofs, and checking correctness? For the tasks explored in this work, where was AI most useful, and where did it require substantial human guidance or correction? Concrete examples would be helpful.

2 comments

Thank you for recognizing the theoretical contribution and for emphasizing the need to make both the technical novelty and the verification process easier to assess.

What changes relative to prior work. We will sharpen the comparison around the bottleneck removed by each ingredient. Kobayashi–Terao accelerate rounding using exchange cycles; we use open exchange walks and bound their endpoint bias. For independence access, geometric stopping connects the unfavorable endpoint to an actual removal, allowing all removal losses within a merge to be charged to a single value budget. This avoids paying a separate worst-case loss at every update.

For fractional optimization, earlier preprocessing balances its own cost against later sampling cost. Our private-subset-or-small-minor alternative ensures that repeated scans yield distinct progress, and recursion improves the cost to nearly linear. For polymatroids, batching counts alone does not remove the dependence on large numerical rank. Capacity-scale separation and an integer baseline, combined with geometric count search and aggregate sampling-error control, reduce the rank dependence to doubly logarithmic.

Reusable tools. We see three particularly useful standalone ingredients: (i) geometric walk rounding with a global removal budget, which applies to any supplied short convex combination of matroid bases; (ii) the private-subset-or-small-minor guarantee, derived from the published packing framework, which supports efficient rank-reduction tasks; and (iii) sampling-error budgets controlled over an entire feasible direction, which avoid demanding unnecessarily strong accuracy for every individual estimate. The first already has a direct use beyond our fractional algorithm. The latter two suggest broader applications, although we do not claim extensions beyond the settings proved here. We will distinguish these standalone guarantees from their use in the final optimization theorem.

Proof verification. We have reviewed all proofs through both human review and AI-assisted checks and have not identified any errors. These checks support our review process but do not replace the mathematical arguments in the paper. See below for further details about how AI assisted in the development of these proofs.

AI assistance. We used ChatGPT and Codex throughout the research process. To make this collaboration concrete, we describe how our use of Quanrud's result evolved. We organized the research as a Codex project, which helped us retain intermediate results, revisit earlier ideas, and build on prior progress.

Our initial focus was submodular maximization under polymatroid constraints. The O~(n8)\widetilde{O}(n^8) oracle complexity of the Soma–Yoshida algorithm motivated us to seek a substantially faster algorithm, ideally matching the O~(nn)\widetilde{O}(n\sqrt{n}) bound then available for matroids. This required improvements to both fractional optimization and rounding, with rounding accounting for the high O~(n8)\widetilde{O}(n^8) dependence. We first obtained a O~(n2)\widetilde{O}(n^2) rounding bound using a decomposition theorem of Edmonds. Further exploration led us to Quanrud's 2024 paper, whose result enabled a O~(nn)\widetilde{O}(n\sqrt{n}) bound.

After obtaining a O~(nn)\widetilde{O}(n\sqrt{n}) bound for the full polymatroid algorithm, we asked whether we could achieve nearly linear complexity for both matroids and polymatroids, approaching the known lower bounds in their dependence on nn. This became the second phase of the project and led to the submitted results. At this scale, exact decomposition of the polymatroid fractional point was too costly for our target bound. We instead developed an approximate decomposition, which underlies the rounding algorithm in the paper. Meanwhile, Quanrud's lemma, which we had initially used to accelerate rounding, proved useful for fractional optimization and became a core ingredient of that algorithm.

This progression illustrates how AI assistance supported our research: maintaining a record of intermediate ideas helped us revisit a structural result and transfer its use from rounding to fractional optimization. The final paper presents the resulting algorithms and their mathematical justifications.

Thank you for the clear response. The comparison with prior work and the explanation of which techniques can be used independently addressed my questions about the paper’s technical contribution. I’m raising my rating to 4.

Reviewer_US3kOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, they study the problem of monotone submodular maximization under matroid constraints and monotone DR-submodular maximization under integral polymatroid constraints. The goal is to find a (1−1/e−ϵ)(1-1/e-\epsilon)-approximate solution in expectation. Complexity is measured based on oracle calls (value and rank/independence). They provide nearly linear oracle complexity algorithms for both settings. The proposed approach comprises two main ingredients: i) an extension of swap rounding (Kobayashi–Terao’s technique) that works in nearly linear oracle complexity, ii) fractional algorithms based on preprocessing and continuous-greedy style optimization.

Critical strengths
  • They make significant progress for an important problem.
  • The rounding idea is a clever extension of the prior approach of Kobayashi–Terao’s rounding. It might also be reusable in other settings.
  • The high-level ideas are sound and interesting. They naturally build on prior work.
Critical weaknesses
  • Presentation could be improved. The main body hides too many details which are deferred to the appendix (including the main algorithms). Also, the appendix is difficult to check in detail due to its extensive length.
  • Not clear if the proposed algorithms are practical. The dependence on the accuracy ϵ\epsilon is poor (albeit polynomial on 1/ϵ1/\epsilon) particularly for polymatroids. Furthermore, no empirical evaluation is provided to validate the performance of the algorithms.
Questions for authors
  • Does the proposed rounding satisfy the usual guarantees of swap rounding? That is: marginal preservation and negative correlation? Although it might not exactly satisfy these properties, it may satisfy them with some slack or up to some multiplicative factor.

  • Do you have lower bounds for the factors you get from the rounding/fractional algorithms or do you think they can be improved?

  • Which components are the main obstacles for practical efficiency, and could they be simplified? A discussion of useful parameter regimes, ideally supported by experiments, would help assess the practical implications.

  • Suggestion: I think the presentation would be clearer if the main body is only for submodular maximization under matroid constraints and you surface more details from the appendix to the main body. The DR-submodular results can go to the appendix.

2 comments

Thank you for the positive assessment of the rounding idea and for identifying where the presentation and guarantees need clarification.

Marginal preservation and negative correlation. Our rounder allows a controlled bias, so exact marginal preservation is not part of its guarantee. The proved guarantee is that, for a supplied convex combination xx of bases, the output base SS satisfies

E[f(S)]≥(1−η)F(x)\mathbb E[f(S)]\geq(1-\eta)F(x)

for every normalized monotone submodular objective, without making value queries. This does imply a useful approximate marginal guarantee: applying the theorem to the modular objective fe(A)=1{e∈A}f_e(A)=\mathbf 1\{e\in A\} gives

Pr⁡(e∈S)≥(1−η)xe.\Pr(e\in S)\geq(1-\eta)x_e.

This is a one-sided guarantee; we do not establish the usual negative-correlation properties of swap rounding, or an approximate version of those properties. The distinction is central to the speedup: opening an exchange cycle makes the update cheaper, while the endpoint analysis controls the resulting loss in expected objective value. We will state this distinction explicitly. Our analysis therefore targets approximate preservation of the expected objective value rather than exact preservation of every marginal. An approximate objective guarantee alone does not imply exact marginal preservation.

Lower bounds and room for improvement. The lower bounds concern the dependence on problem size. At fixed accuracy, the cited Ω(n/log⁡2n)\Omega(n/\log^2 n) value-query lower bound makes our matroid result optimal up to polylogarithmic factors in the worst case. For polymatroids, we give an Ω(n)\Omega(n) expected feasibility-query lower bound even at numerical rank 2n2^n. These do not show that our accuracy factors, logarithmic overheads, or individual rounding and fractional bounds are tight. We regard improving those factors as an important open direction, particularly the high powers of 1/ϵ1/\epsilon in the polymatroid algorithm.

Practical obstacles and possible simplifications. We have added experiments in Appendix J to examine the practical benefits and limitations of individual components.

A theoretical O~(n)\widetilde{O}(n) bound requires every stage of the algorithm to satisfy that bound in the worst case. A practical implementation faces a different question: which stage is expensive on the instance at hand? Applying every device needed by the worst-case analysis can introduce overhead at stages that a conventional implementation already handles efficiently. A useful implementation may therefore combine selected subroutines from this work with simpler methods elsewhere.

The polymatroid algorithm illustrates this distinction. In the exponential-rank regime r=2Θ(n)r = 2^{\Theta(n)}, we have log⁡r=Θ(n)\log r = \Theta(n), so an additional log⁡r\log r factor can prevent a nearly linear bound in nn. Our construction replaces several sources of numerical-rank dependence by dependence on the accuracy and on log⁡log⁡r\log \log r. Removing these rank factors is essential to our nearly linear analysis, but this tradeoff need not improve runtime when log⁡r\log r is modest: an additional factor polynomial in 1/ε1/\varepsilon can cost more than the rank dependence it removes. On the same instance, a different subroutine that removes an extra factor in nn at an accuracy cost may still be worthwhile. The practical value of each component should therefore be assessed separately.

Conventional greedy, search, and exchange methods can perform well in common regimes, and our control experiments include many cases where they are preferable. Their favorable behavior does not exclude specific instances with long exchange searches, many blocked candidates, repeated rebuilding, or costly count searches. We construct instances exposing these mechanisms and ask whether the corresponding subroutine helps. Different components are tested on different instances; we do not require all bottlenecks to occur simultaneously. This explains both the focus on components rather than the complete maximization pipeline and the use of uncommon, sometimes deliberately artificial, scenarios. The results identify regimes in which particular components help and the tradeoffs they entail. They do not establish uniform superiority or the prevalence of these regimes in applications.

Presentation. We agree that the exposition would benefit from reorganization and clearer explanations. We will expand the explanations of the matroid results and improve the organization to make the main ideas easier to follow.

I thank the authors for the clarifications. I will maintain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.