acceptodds
Under review as a conference paper at ICLR 2027

Online Submodular Minimization with Switching Costs

Abstract

We consider online submodular minimization with switching costs against an oblivious adversary under full-information and bandit feedback. Our algorithms use shared-threshold rounding to control movement. For a ground set of size , horizon , losses in , and switching-cost weight , the minimax expected regret under full information is . Under bandit feedback, a chain-traversal exploration scheme achieves , matching our lower bound up to logarithmic factors when . To obtain high-probability guarantees, we establish a pathwise upper bound on the realized regret that isolates a cumulative movement the learner can monitor. Using this quantity to trigger a switching-budget restarting wrapper yields high-probability bounds under both feedback models with only logarithmic overhead.

Primary area:
learning theory
Keywords:
online learning, switching costs, submodular optimization, bandit feedback, high-probability regret

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_yETQOpenReview ↗
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
  1. 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.

  1. 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
  1. 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.

  1. 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
  1. 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.

  1. 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.

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

This paper studies online submodular minimization with Hamming switching costs under full-information and bandit feedback. The adversary is oblivious, and regret is measured against the best fixed subset. For losses in [−M,M][-M,M], the authors establish the full-information minimax expected-regret rate Θ(Mmin⁡{T,(1+λ/M)nT}).\Theta\left(M\min\{T,\sqrt{(1+\lambda/M)nT}\}\right). Under bandit feedback, they obtain O(Mmin⁡{T,n(1+λ/M)1/3T2/3}),O\left(M\min\{T,n(1+\lambda/M)^{1/3}T^{2/3}\}\right), with a lower bound that matches up to logarithmic factors when λ≥M\lambda\ge M. They also prove high-probability guarantees with logarithmic overhead. The algorithms optimize the Lovasz extension and use a shared random threshold to round fractional decisions while controlling movement. For bandit feedback, exploration follows a randomly shifted cyclic traversal of a chain. The high-probability analysis relates realized regret to movement and then applies an existing restarting framework based on switching budgets. The results are primarily theoretical, with additional synthetic experiments.

Critical strengths
  1. The paper gives a clear characterization of how regret depends on dimension, horizon, loss scale, and switching weight. The full-information bounds match, and the bandit bounds nearly match when switching costs dominate. Together, these results substantially improve our understanding of the problem.
  2. The design of bandit exploration is a useful contribution. Randomly shifting the cyclic traversal gives uniform marginals at each position while keeping movement to O(n)O(n) over an n+1n+1-round block. The structure of the estimator also controls its second moment. In the high-probability analysis, monitoring the movement of the virtual exploitation sequence allows exploration costs to be accounted for separately. These choices are important for obtaining the stated dependence on the problem parameters.
Critical weaknesses

My main reservation is that the bandit results leave the small-switching-cost regime unresolved. At λ=0\lambda=0, the main upper bound is O(MnT2/3)O(MnT^{2/3}), whereas existing algorithms achieve O~(Mn5/2T)\widetilde O(Mn^{5/2}\sqrt T). The latter has worse dimension dependence, so neither bound uniformly dominates the other. As the authors acknowledge, selecting between the existing algorithm and the proposed method recovers the known guarantee at zero switching cost, but does not provide a tight characterization of the transition as λ\lambda increases. Thus, the bandit contribution is less complete than the full-information result. This limits the strength of my recommendation, although it does not undermine the matching bounds established for λ≥M\lambda\ge M.

Questions for authors

None that would materially affect my recommendation. Closing the gap for small λ\lambda would be interesting future work.

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

The paper studies online submodular minimization when changing subsets incurs a cost λ\lambda per added or removed element. It combines Lovász-extension subgradient descent with a shared-randomness rounding to limit switching.

Under full information, it establishes minimax-optimal expected regret. Under bandit feedback, cyclic exploration reduces movement and achieves regret matching a lower bound up to logarithmic factors when λ≥M\lambda\ge M, where MM is the loss magnitude bound. Movement-triggered restarts yield high-probability guarantees. They also perform numerical tests to illustrate reduced switching cost.

Critical strengths

The reviewer understands the paper as extending online submodular minimization to Hamming switching costs. Shared-threshold rounding gives an optimal coupling under Hamming distance. The method builds on Lovasz-extension subgradient descent and Altschuler-Talwar's restart framework. Its main strengths lie in cyclic-chain exploration, the matching or near-matching regret bounds, and the specific pathwise analysis needed for high-probability guarantees.

Critical weaknesses
  • The full-information expected bound follows relatively directly from existing subgradient and coupling arguments, while the high-probability analysis adapts Altschuler-Talwar’s restart framework. The stronger contributions therefore lie in cyclic exploration and the bandit lower bound.

  • The paper considers only unconstrained subset selection. Many motivating applications impose cardinality, budget, capacity, or matroid constraints. This limits applicability since cyclic exploration traverses a full chain of subsets that such constraints may turn infeasible.

  • The bandit minimax characterization remains incomplete in the small-switching-cost regime. Experiments use only synthetic graph cut losses. Cyclic bandit SSD underperforms both fixed policies at every main tested horizon.

  • A dynamic comparator paying switching costs would also better capture the motivating adaptation-movement trade-off instead of the static comparator in this work.

Questions for authors
  • Can cyclic exploration accommodate cardinality, budget, or matroid constraints while preserving feasibility and movement guarantees?

  • Can the bandit minimax gap be closed for 0≤λ<M0\le\lambda<M?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.