- 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"?
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) 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), we have logr=Θ(n), so an additional logr factor can prevent a nearly linear bound in n. Our construction replaces several sources of numerical-rank dependence by dependence on the accuracy and on loglogr. Removing these rank factors is essential to our nearly linear analysis, but this tradeoff need not improve runtime when logr is modest: an additional factor polynomial in 1/ε can cost more than the rank dependence it removes. On the same instance, a different subroutine that removes an extra factor in n 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 S, so that it continues to contain S. The algorithm neither computes this base nor requires access to the optimum. The inequality in the theorem shows that the value gained by S compensates, in expectation, for the value lost by this evolving comparison base. We will define it explicitly before the theorem.