- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies submodular maximization when selecting a set changes the distribution under which its utility is evaluated:
\qquad F(S)=\mathbb E_{\xi\sim D(S)}[f(S,\xi)].$$ Although $f(\cdot,\xi)$ is monotone and submodular for every realization, the performative objective need not retain these properties. The authors recover submodularity by freezing the deployment distribution, relate approximate performative stability to global performance under sensitivity assumptions, and propose a finite-sample acceptance rule that certifies improvements after redeployment. Experiments use a synthetic decision-dependent weighted-coverage model.Critical strengths
-
The studied problem is relevant and well motivated. Distribution-changing subset selection provides a useful connection between combinatorial optimization and performative decision making.
-
The paper carefully separates improvement under a frozen distribution from improvement after deployment, and terminal stability from safety along the deployment trajectory.
-
The main arguments appear reasonable. The independent certification batch and probability control across adaptive iterations are handled explicitly.
Critical weaknesses
-
The main safety experiment uses parameters that make every nontrivial update impossible. In particular, Appendix E.2.
-
The technical novelty of the guarantees need better justification. The main bounds primarily combine sensitivity inequalities, greedy approximation, and concentration. Performative stability and its relationship to predictive performance were already central to the original framework. The paper should identify more precisely which new difficulties arise from submodular decisions and which technical results resolve them.
Questions for authors
-
Can the method demonstrate multiple accepted redeployments and a meaningful improvement over static greedy under identical initialization and sampling budgets?
-
On small instances, how do the actual approximation ratios compare with the theoretical feedback-dependent error terms?
-
When the distribution map is unknown and only sampling access is available, how can valid and sufficiently tight deployment certificates be obtained?
4 comments
Experimental Validation and Theoretical Contributions under Decision-Dependent Feedback
Q1: Can the method demonstrate multiple accepted redeployments and a meaningful improvement over static greedy under identical initialization and sampling budgets?
Response: We conducted additional experiments using identical initializations and matched function-evaluation budgets. Although the local certificate enabled safe redeployments, we did not consistently observe multiple accepted updates or establish a statistically significant improvement in terminal performance over static greedy.
These findings highlight a limitation of the current method: the theoretical guarantee ensures improvement for accepted redeployments, but does not guarantee repeated adaptation or superiority over static greedy. The additional certificate diagnostics also show that conservativeness can prevent beneficial updates.
Changes: We have expanded Section 7.2 and Appendix E.4.4 to clarify the distinction between deployment reliability and terminal performance, and to quantify certificate conservativeness.
Q2: On small instances, how do the actual approximation ratios compare with the theoretical feedback-dependent error terms?
Response: We conducted additional small-instance experiments to compare the empirical approximation ratios with the feedback-dependent terminal guarantee in Theorem 6.2.
Across 80 experimental settings, the median empirical approximation ratio is 0.9908, with a median conservative lower bound of 0.9747 based on simultaneous confidence intervals. In contrast, the theoretical lower bound remains positive for but becomes non-informative for the tested , primarily due to the feedback-dependent penalty. These results indicate that the theoretical guarantee can be substantially conservative, particularly under stronger feedback, even when the empirical approximation performance remains high.
Changes: We have added this comparison to Appendix E.4.4 (highlighted in purple).
Q3: When the distribution map is unknown and only sampling access is available, how can valid and sufficiently tight deployment certificates be obtained?
Response: Our current certificates require structural information in addition to sampling access. The global certificate uses a known upper bound on distributional sensitivity, while the model-specific local certificate exploits the parameters of the weighted-coverage softmax model. Samples from the current deployment are used to estimate frozen improvements, without requiring samples from candidate-induced distributions.
When the distribution map and its sensitivity bounds are unknown, constructing valid and sufficiently tight certificates from samples alone requires additional assumptions. This setting is beyond the scope of our current analysis, and developing data-driven deployment certificates remains an important direction for future work.
Changes: We have clarified the structural information required for the global and model-specific certificates in Section 6.2 (highlighted in blue) and discussed the limitations of certificate construction under unknown distribution maps in the Conclusion (highlighted in purple).
Thank you again for your valuable comments. We hope these revisions address your concerns and would appreciate further suggestions to improve our manuscript.
Thank you for the detailed reply. I have read thru your response and the changes in the revised manuscript. Most of my concerns have been addressed, and I will therefore raise my score.
Thank you very much for taking the time to review our responses and revised manuscript. We sincerely appreciate your thoughtful feedback and reconsideration of our work.
Experimental Validation and Theoretical Contributions under Decision-Dependent Feedback
Overall Response: We sincerely thank the reviewer for the constructive and insightful comments, which have been particularly valuable in helping us identify the limitations of our experimental evaluation and clarify our theoretical contributions. In response, we have made two main revisions:
Experimental validation: Expanded the evaluation of the model-specific local certificate to demonstrate nontrivial safe redeployments, assess terminal performance, and quantify certificate conservativeness.
Theoretical contributions and limitations: Clarified the challenges and guarantees in Theorems 5.1, 6.1, and 6.2, evaluated the informativeness of the theoretical approximation bounds, and specified the structural information required for deployment certification.
These revisions have helped us more precisely distinguish what our framework guarantees from its current practical limitations. We address the reviewer's concerns in detail below. The revisions addressing this review are mainly highlighted in purple in the revised manuscript.
Weakness1: The main safety experiment uses parameters that make every nontrivial update impossible. In particular, Appendix E.2.
Response: We agree that the global certificate used in the original experiment is overly conservative and prevents all nontrivial updates. However, this reflects the limitations of the general certificate rather than an inherent inability of the feedback-safe retraining framework to accept updates.
To demonstrate this distinction, we additionally evaluate the model-specific local certificate under cold-start initialization. The method accepts at least one certified redeployment in all runs for γ≤1 and in 96%–100% of runs for γ=2, with no observed safety violations. These results demonstrate that nontrivial safe redeployments are achievable with a tighter certificate, although certification remains conservative in some settings.
Changes: We have updated Section 7.2 and expanded the certificate diagnostics in Appendix E.4.4 (highlighted in purple).
Weakness2: The technical novelty of the guarantees need better justification. The main bounds primarily combine sensitivity inequalities, greedy approximation, and concentration. Performative stability and its relationship to predictive performance were already central to the original framework. The paper should identify more precisely which new difficulties arise from submodular decisions and which technical results resolve them.
Response: We appreciate this observation. We acknowledge that our proofs build on established sensitivity inequalities, greedy approximation, and concentration techniques. We have revised the manuscript to clarify the two difficulties introduced by decision-dependent feedback and the corresponding theoretical guarantees.
Our contribution is therefore not a new greedy algorithm or concentration inequality, but the connection between approximate stability, global decision quality, and certified deployment safety for decision-dependent set optimization.
Changes: We have clarified the theoretical motivation and corresponding guarantees in the Introduction, reorganized Section 4, and refined the presentation of Theorems 5.1, 6.1, and 6.2 (highlighted in teal, blue and purple).