- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies approximate unlearning for offline stochastic multi-armed bandits, measuring utility by the expected simple regret of the final recommendation. Its output-level definition allows O(m) stored statistics and gives the reference execution retained-data statistics plus the deleted arms' identities and counts. The proposed method screens the affected arm, then switches between exact rollback and downward-shifted Gaussian perturbation using theoretical utility costs. The paper develops single-source bounds under fixed-count and behavior-policy models, a multi-source construction under the fixed-count model, and synthetic and Yelp-derived comparisons.
Critical strengths
- A meaningful statistical question and a useful adaptive construction. Although exact rollback is inexpensive, deletion reduces effective coverage and can harm the final recommendation. The retained-data screen aligns the actual and reference branches, while the downward shift controls promotion of a suboptimal deleted arm. This gives a concrete approach to trading approximate unlearning against statistical utility.
- A substantive multi-source extension. Common candidate refinement, private source selection, conditional Gaussian perturbation and an explicitly budgeted exceptional mixture provide a coherent way to perturb only one requested source. The appendix is detailed enough to inspect the argument, and the full 200-seed rerun reproduced the synthetic multi-source percentages in Appendix B.5.
Critical weaknesses
- The experiments do not validate the stated switching rule at consistently calibrated privacy budgets. Equation (2) corresponds to
BG < BR, butexperiment_suite.py:39–53,425applies undocumented multipliers 0.567, 0.614, 0.6215, 0.732 and 0.745 to BR. They change the chosen branch: at N=3000, k=80 and gamma=.02, the 200-seed rerun gives regret .004456 with the exact rule versus .003860 with the supplied implementation. Their selection procedure needs explanation. Single-source CSVs/CDR use the classical formulaepsilon=sqrt(2log(1.25/delta))/gamma; at delta=.1 and gamma=.02 it gives 112.38, whereas the manuscript's analytic calibration requires 1313.09. A separate valid two-arm example violates even the final-recommendation inequality at the reported 112.38, .1 budget, so this is more than failure of a sufficient Gaussian certificate. It does not refute the correctly calibrated manuscript theorem. Utility gains at informative privacy levels remain unestablished, and the official supplement lacks the Yelp features/preprocessing needed to reproduce the main real-data figure. - The optimality claims need narrower scope, and one lower-bound statement needs repair. For fixed
1<C*<2, both executions can reconstruct original counts usingN_D(a)=N_retained(a)+k_a. Preserving the original most-frequent-arm decision therefore gives exact(0,0)-BUL and exponentially decreasing expected regret in N, independent of deletion size, under the stated i.i.d. behavior model. Algorithm 6's deletion-dependent bound is unnecessarily weak in this regime. The other lower bounds do not establish tightness of the Gaussian-dominated privacy dependence. Separately, Theorem 6 omits a needed coverage condition: with counts (50,100), N*=100, a0=1 and k=20, coverage forces arm 2 to be optimal, so a constant arm-2 rule has zero regret, contradicting the positive lower bound. The two-point proof needs both candidate optimal arms to satisfy coverage. This is a repairable statement error rather than a failure of the central privacy argument.
Questions for authors
- How were the single-source switch multipliers chosen, and which rule generated the figures? Please provide comparisons using the exact Equation (2) rule and a fully specified source/deletion protocol.
- How much of the advantage remains when all methods use the same correctly calibrated
(epsilon, delta)values, including informative privacy levels? Can you provide the Yelp inputs or an executable raw-to-feature pipeline and the missing Table 2 configuration? - Can you repair Theorem 6's coverage assumptions and state precisely which regimes have matching bounds? Please address the descriptor-aware original-count rule for
1<C*<2. A shifted Laplace mechanism is also a useful comparator at the same epsilon; the existing Gaussian lower bounds do not establish its inferiority.
We thank you for your constructive and detailed feedback.
[Weakness 1 and Question 1] Validation of calibration. We thank the reviewer for pointing out the insufficient explanation of our calibration procedure. Our theoretical bounds characterize sub-optimality only up to constant factors, and the quantities compared in Eq. (2) are theoretical utility bounds rather than exact expected sub-optimalities. In the experiments, we introduce a conservative calibration factor c∈(0,1) on the rollback-side bound, so that the Gaussian mechanism is selected only when BG<cBR. This encourages an earlier switch to rollback. For a fixed, publicly specified c, the adjustment preserves the (ϵ,δ)-unlearning guarantee and the asymptotic utility bounds up to constant factors. The coefficients were chosen based on our prior exploratory experiments. We acknowledge that this calibration was not adequately documented and provide the details and comparisons in the last page of appendix in the revised version.
[Weakness 2 and Question 3] Technical Details.
Coverage condition in Theorem 6 and Regimes with matching bounds: Please see the response to Reviewer gHZ6 on [Weakness 2 and Question 2].
Descriptor-aware original-count rule for 1<C⋆<2: We thank the reviewer for this observation. We agree that, under our current Definition 1, the original arm counts can be reconstructed from the deletion descriptor. Our initial intention for 1<C⋆<2 was to impose a stronger privacy requirement: the reference execution cannot access the deletion descriptor. Since imitation learning already achieves exponentially small regret in this regime, allowing reconstruction of the original counts would trivialize the unlearning problem. Nevertheless, we have decided to retain the current privacy requirement and incorporate the reviewer's observation into Algorithm 6. Specifically, the revised algorithm uses the original arm counts in both the actual and reference executions, remains (0,0)-BUL, and achieves an improved regret bound of O(exp(−2Nln4(C⋆−1)(C⋆)2)), independent of the deletion size k. Please see our revised PDF.
Shifted Laplace comparison: We thank the reviewer for this suggestion. Gaussian perturbation is a natural starting point, following prior certified-unlearning frameworks for parameter-valued models. Our single-source mechanism perturbs only one LCB coordinate, therefore shifted Laplace offers a favorable alternative. By [1], Laplace noise with scale b=ϵΔf achieves pure ϵ,0-privacy for any ϵ>0. With an appropriate downward shift, the additional sub-optimality terms for Gaussian mechanisms is $O\left(\frac{k\gamma(\epsilon,\delta)}{N(a_0)} \left[1+\sqrt{\ln(1+N\gamma(\epsilon,\delta))}\right]\right)$, for Laplace mechanism is $O\left(\frac{k}{N(a_0)\epsilon} \left[1+\ln\left(1+\frac{Nk}{N(a_0)\epsilon}\right)\right]\right)$. For fixed δ>0, Gaussian can be preferable as ϵ→0, since γ(ϵ,δ) remains bounded, whereas Laplace noise scales as 1/ϵ. Conversely, as ϵ→∞, Laplace has a better noise-scale dependence, and may also be preferable for small δ. We will incorporate shifted Laplace as an additional base mechanism in the next version.
[Question 2] At this loose budget in the last page of revised version, although strict Eq. (2) has a narrower advantage than the tuned switch, it still achieves lower mean regret than rollback at 16/25 fixed-sample and 15/25 distributional deletion sizes in the Yelp hard case, with 14/25 pointwise paired 95% intervals wholly below zero in each model. This provides a tuning-free utility advantage in the stated regime. We include the complete Yelp dataset preprocessing and experimental reproduction protocol in the supplementary materials (YELP_PROTOCOL.md). Table 2 (pp.39-40 of the revised manuscript) reports results for Algorithms 2 and 6 (the previous version) using their untuned switching rules with codes in table2_cstar13_gamma05.py.
[1] Differential Privacy.