- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates stronger notions of regret for online submodular maximization. The authors introduce affine and quadratic transformation classes and develop polynomial-time algorithms by combining online gradient ascent, approximate fixed-point computation, and contention resolution schemes. The proposed algorithms achieve sublinear approximate -regret under the stated assumptions.
Critical strengths
-
The problem formulation is meaningful and theoretically interesting.
-
The paper provides detailed theoretical analysis.
Critical weaknesses
-
Insufficient experimental evaluation. The main focus of this paper is online submodular maximization. However, the objective functions used in the experiments are modular. Although modular functions are a special case of submodular functions, they do not capture the nontrivial diminishing-returns structure of general submodular objectives. Moreover, the experiments evaluate ordinary regret with , whereas the theoretical guarantees are established for a smaller approximation factor. Achieving sublinear regret with is generally computationally intractable for submodular maximization under standard complexity assumptions. Therefore, the current experiments do not adequately validate the main theoretical guarantees.
-
Unclear relationship between the approximation factor, transformation classes, and regret guarantees. The theoretical guarantees in Theorem 6.3 involve several parameters, making the concrete regret bounds and their dependence on problem characteristics insufficiently clear. More importantly, the improvement over existing regret guarantees is not well established. For example, when , the approximation factor is strictly smaller than the classical factor. Although the proposed framework considers stronger transformation-based regret notions, this comes with a weaker approximation factor, making direct comparisons with existing static-regret guarantees difficult. More fundamentally, the relationship between the achievable approximation factor , the expressiveness of the transformation class , and the resulting regret bounds remains unclear. It is also unclear under what conditions different -regret guarantees are achievable and whether the approximation losses are inherent or arise from the particular algorithmic framework.
Questions for authors
-
Please include experiments on genuinely submodular functions to better validate the theoretical guarantees, particularly the approximate -regret bounds.
-
Please clarify the parameter dependence in Theorem 6.3 and discuss whether the approximation factor can match the classical offline approximation guarantee of , and under what additional conditions this might be possible.
-
Please explicitly characterize the relationship and trade-offs among the approximation factor , the transformation class , and the achievable regret bounds. In particular, which conditions are sufficient or necessary for obtaining sublinear -regret?
4 comments
With the discussion period ending soon, we would appreciate your thoughts on whether our response and revisions address your main concerns. Please let us know if any points need further clarification.
Thank you for the detailed response. I acknowledge the authors' efforts. These revisions have addressed some of my previous concerns. However, the practical advantages and theoretical trade-offs of the proposed quadratic mappings are not yet fully established.
Overall, I appreciate the additional theoretical and experimental efforts. I want to say is that these contributions are not a difficult task for current AI tools. Therefore, I prefer to maintain my original score. If the author can fully explain the practical advantages, perhaps I will improve my score
We would appreciate clarification of which practical advantage or theoretical trade-off remains unresolved. Our response explains the additional expressive power of quadratic mappings and their approximation cost, while Section 6.3 and Theorem 6.4 quantify the computational and regret bounds. Appendix F.3 shows the added benefit of quadratic mappings. Experimentally, Appendix H.3 reports 4.6–8.9% higher mean rewards for Quadratic OGA than Affine OGA on the tested coverage instances.
In a nutshell, standard static regret formalizes one notion of rationality:
- Static: Compete with replacing all selected sets with a single fixed feasible set . Our framework asks for additional forms of rationality:
- Affine: Also compete with consistently swapping items: e.g., exchanging and in every selected set.
- Quadratic: Additionally compete with conditional replacements: e.g., replacing with whenever is selected and is absent.
Our contribution is primarily theoretical: to our knowledge, no prior work provides polynomial-time sublinear approximate -regret guarantees for permutations and conditional trades in OSM. We identify these natural learning requirements and establish that they can be achieved efficiently.
We respectfully ask you to reconsider the statement about AI. We would welcome a concrete assessment of the novelty and significance of the guarantees established here.
We thank the reviewer for their careful reading and constructive feedback. We address the concerns below.
Approximation factor (W2, Q2).
Affine mappings. We have improved Theorem 6.3's affine factor to 1−1/e using randomized pipage rounding (Calinescu et al., 2011). For Xt rounded from yt, EXt=yt implies E[ϕ(Xt)]=ϕ(yt) for affine ϕ. Moreover,
\qquad \mathbb E f_t(X_t^{\rm CRS})\ge\beta F_t(y_t).$$ Applying Appendix C.2's inequality to $\phi(X_t)$ and taking expectations gives the regret bound for constants and permutations.Quadratic mappings. We retain Theorem 6.3's CRS factor β(1−1/e), where β=1−e−kkk/k!. Pipage need not preserve E[ϕ(Xt)]=ϕ(yt) for quadratic ϕ, since this expectation depends on the probabilities of selecting pairs together. Whether the additional β loss is necessary remains open.
Submodular experiments and reward gains (W1, Q1). We extended the experiments in Section 7 and Appendix H.3 to nonmodular weighted coverage with overlapping features (T=500, three instance seeds per size). All learners use the CRS rounding, repeated 64 times on each fractional decision sequence. Mean rewards per round are:
We have added the protocol and results to the revision.
Approximate-regret results (W1, Q1). On additional nonmodular coverage instances designed to separate static and affine regret, we used the same protocol with CRS and a fixed subset of affine maps shared by all learners. At (n,k)=(128,21):
At (128,21), Static OGA has negative (1−1/e)-static regret, yet a fixed permutation of its selected items earns more reward even after scaling by β(1−1/e). Across all nine instances, mean regret over the evaluated affine maps is positive for Static OGA and negative for Affine and Quadratic OGA.
Concrete guarantees and tradeoffs (W2, Q2). We have added an explicit regret theorem for Algorithm 2 (Theorem 6.4). Under the paper's assumptions (0≤ft(S)≤M for every S), using pipage rounding for affine mappings and CRS for quadratic mappings gives, with probability at least 1−δ:
\qquad R_{\beta(1-1/e)}^{\Phi_2}(T)\le\widetilde O(Mnk\sqrt T).$$ Here $\widetilde O$ hides logarithms in $n,1/\delta$. These bounds use Algorithm 2's $\ell_1$ fixed-point tolerance $\epsilon=T^{-1/2}$, one unbiased gradient sample per coordinate per round ($2nT$ value-oracle calls), and feasible projections within $O(D/T)$ of the exact projection in Frobenius norm, where $D$ is the coefficient set's diameter. We have added the proof and error analysis to Appendix D.5. **What quadratic regret adds (W2, Q3).** We extend the separation in Appendix F.2 with a coverage example in Appendix F.3 ($n=12,k=3$) where the same decisions can have negative $(1-1/e)$-affine regret while $\beta(1-1/e)$-quadratic regret grows linearly with $T$. Thus the affine guarantee does not imply the quadratic guarantee. We have added the proof to the appendix. **Expressiveness and tractability (W2, Q3).** Sections 5–6 and Appendix D.3 give sufficient conditions: polynomial-size convex programs, efficient approximate fixed points, and rounding that converts fractional surrogate regret into integral $\alpha$-regret. Necessity of these structural conditions remains open. Because our classes contain every constant map, $1-1/e$ is the worst-case limit for polynomial-query algorithms (Calinescu et al., 2011); the revised affine guarantee attains it.