- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper investigates the problem of online submodular minimization, considering the additional condition of 'switching cost', by directly injecting the additional switching cost in the regret notion. This work considers both full information and bandit feedback, and provides upper bound in expectation and with high probability, along with lower bound in expectation. This work highlights running SSD on Lovasz extension and use a single random threshold to round fractional iterates.
Critical strengths
- Interesting research question and a promising extension of online submodular minimization.
I find the inclusion of switching costs into online submodular minimization to be an interesting and worthwhile research direction. Explicitly incorporating switching costs into the regret measure provides a natural way to account for the cost of changing decisions in sequential optimization. I particularly appreciate that the authors investigate this setting under both full-information and bandit feedback. Although I am more familiar with continuous DR-submodular maximization, where switching costs are less commonly considered, I find this problem formulation promising and potentially useful.
- Strong theoretical contributions supported by upper and lower bounds.
The paper provides substantial mathematical results, including expected-regret and high-probability guarantees, together with lower bounds that establish optimality or near-optimality in the relevant regimes. I particularly appreciate the proposed cyclic-chain exploration technique for controlling switching costs under bandit feedback. Figure 1 is especially helpful in illustrating its advantage over independent exploration. The combination of algorithmic development and lower-bound analysis is a major strength of the paper and is the primary reason I lean toward acceptance.
Critical weaknesses
- The motivation and positioning of the contributions could be substantially strengthened.
While I find the research direction interesting, I do not think the Introduction sufficiently motivates why switching costs are an important consideration specifically for online submodular minimization. The opening paragraphs primarily focus on introducing the standard OSM setting, while the motivation for switching costs receives comparatively limited attention. The subsequent example based on Stone (1977) is also somewhat difficult to connect to the central research question without additional explanation.
I believe the motivation would be stronger if the authors could provide additional concrete applications in which both submodular losses and switching costs naturally arise, and explain why the proposed regret formulation is appropriate for these applications. The first three paragraphs could also benefit from some reorganization to establish a clearer progression from the classical problem to the new setting.
Similarly, I would appreciate a more explicit comparison of the theoretical guarantees with those of the closest prior works. I recognize that the introduction of switching costs changes the regret measure, so direct comparisons are not necessarily appropriate. Nevertheless, a compact table comparing the regret bounds, assumptions, and feedback settings of relevant prior work would help contextualize the contributions. In particular, it would be useful to understand the additional theoretical price of accounting for switching costs, and whether the proposed algorithms preserve the same dependence on the time horizon as their switching-free counterparts.
Although the current manuscript provides its own results summary in Table 1 and discusses previous bounds in Section 2, a more direct comparison would considerably improve the presentation of the theoretical contributions. Given that this is primarily a learning-theory paper, I consider such contextualization particularly valuable, in addition to the empirical validations.
- The presentation and organization of the mathematical results need improvement.
My other major concern is the readability of the theoretical development. Many results in the main text are presented rather abruptly, with limited introductory discussion, intuition, or proof sketches. This makes the paper difficult to follow without repeatedly consulting the appendices. The amount of explanation also feels inconsistent across results. For instance, Theorem 10 includes a relatively detailed proof sketch, while other important results receive much less discussion. It is unclear whether this difference reflects the relative technical importance of the results or simply an inconsistency in presentation.
Section 6 is a particularly noticeable example: it begins directly with a theorem statement, without an introductory paragraph explaining the purpose of the lower-bound analysis or how the results complement the preceding upper bounds. I would encourage the authors to provide more intuitive explanations of the main results and their underlying proof ideas, while retaining the complete technical proofs in the appendix.
I also find the organization of the appendix proofs somewhat fragmented. Several intermediate statements are isolated as standalone lemmas or propositions, even when they appear to be used only locally and do not represent independently highlighted technical contributions. In my view, auxiliary results that are not reused or explicitly referenced for their conceptual significance could sometimes be incorporated directly into the relevant proofs. This would make the logical dependencies easier to follow and reduce unnecessary navigation between statements.
These concerns are primarily about presentation rather than mathematical correctness, but they materially affect the accessibility of the contributions and the reader's ability to appreciate the technical novelty.
Overall, I find the research question interesting and worth investigating, and the theoretical results provide substantial support for acceptance. My concerns center primarily on the presentation: motivating the problem more convincingly, contextualizing the theoretical guarantees, and improving the organization and explanation of the mathematical arguments. I lean toward acceptance, but believe the manuscript would benefit considerably from revisions in these areas.
Questions for authors
- Clarification regarding the theoretical price of switching costs.
Could the authors clarify how the regret guarantees compare with the closest results for online submodular minimization without switching costs, particularly in terms of their dependence on (T), (n), and (\lambda)?
My understanding is that the proposed algorithms preserve the classical dependence on (T) in the corresponding feedback settings, while introducing additional dependence on the switching-cost weight. I would appreciate a more explicit discussion of this tradeoff and the extent to which the proposed techniques improve upon straightforward adaptations of existing algorithms. A side-by-side comparison table would be helpful.
- Clarification regarding the practical motivation and applicability of the model.
Could the authors elaborate on the motivating applications in which the switching cost is naturally proportional to the Hamming distance between consecutive subsets?
In particular, I would appreciate a clearer explanation of how the example based on Stone (1977) motivates the switching-cost formulation. Additional concrete examples would help establish the practical significance and generality of the proposed setting.