acceptodds
Under review as a conference paper at ICLR 2027

Why Forget-Only Unlearning Needs Memorization

Abstract

Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearning, where the deletion algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. We ask whether forget-only unlearning is always possible. We first show that this depends on the learning method: different datasets can produce the same trained model but require very different outputs after the same examples are removed. Using this observation, we derive lower bounds on how accurately unlearning can match retraining and instantiate it for several standard learning algorithms. We then ask what must be true when forget-only unlearning succeeds. To this end, we derive lower bounds on what an algorithm must memorize about the training data to handle arbitrary deletion requests. For simple threshold learners, the required information can be as large as the entire dataset, even though ordinary training keeps only one boundary point. Overall, our results show that information discarded during ordinary learning may be needed later for deletion, so models designed for forget-only unlearning may need to retain more information than standard training does.

Primary area:
learning theory
Keywords:
machine unlearning, memorization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_fX22OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper demonstrates from an information-theoretic perspective that "forget-only" forgetting is, in principle, sometimes impossible to achieve, and explains the reason (information loss). However, it does not prove that practical "forget-only" methods fail for this specific reason.

Critical strengths
  1. The motivation is clear.
  2. This paper demonstrates from an information-theoretic perspective that "forget-only" forgetting is impossible to achieve
  3. The permutation/chain-rule accounting is a simple and reusable way to avoid double-counting information shared between requests.
Critical weaknesses
  1. the same algorithm A produces both the pretrained model M = A(S) and the retraining target W = A(S∖U). The memorization results (Props. 4.4–4.7) are stated as “any forget-only unlearner satisfying the assumptions must obey I(M; S) ≥ …”. Yet for the bare learner, I(M; S) is log q or 0, which is far below the bound. The propositions therefore say that no such unlearner exists for this A. That makes them a second impossibility result, not a memorization requirement. But,the authors further interpret them as “a successful implementation would have to store additional state.” But if A is augmented to A'(S) = (h_S, state_S), then the retraining target A'(S∖U) also changes.
  2. It mentions the “constructions extend to larger N” but gives no details.
  3. The paper is purely theoretical, with only toy examples. A small experiment showing a common forget-only method failing as predicted would make the results more convincing.
  4. The connection to empirical forget-only methods (gradient ascent, NPO, etc.) remains informal.
Questions for authors
  1. Do the authors think the failure of forget-only methods is closely related to knowledge entanglement? How does the “information loss” explanation relate to the commonly discussed “knowledge entanglement” explanation for the failure of forget-only methods?
  2. The examples in the paper are simple learners such as thresholds and the median. Could you give a more realistic case, for example a neural network or a language model, where this information loss happens and causes forget-only unlearning to fail?
5 comments

We thank the reviewer for their insightful feedback.

W1. Yes, Propositions 4.4–4.7 establish impossibility for the bare learners considered. However, they are also instances of memorization requirements: Theorem 4.3 establishes a learner-dependent necessary information condition for successful forget-only unlearning, and the propositions show that the fixed learners fail to meet it, implying impossibility. Our goal with saying "a successful implementation would have to store additional state." is to highlight that if a forget only learner were to exist, it would need to store more information than the fixed learner. We agree that it would change both the unlearning and retraining target as a result and the memorisation lower bound would need to be satisfies with those changed targets.

W2. We agree that the extension to larger NN was only implicit, as we used N=2N=2 for illustration. We did primarily for simplicity to avoid having to write down cumbersome examples. Below, we provide an explicit construction for the threshold example with N>2N>2. Similar extensions are possible for the other examples and we will include them in the revised version.

The N=2N=2 threshold construction achieves the maximal separation Δ=c−12\Delta=c-\frac12. For a given 2<N≤2c2<N\leq2c, we extend it by choosing NN approximately equally spaced retraining targets within the same interval, while keeping the common deletion request U=⋃j=1m{(−c+1,+1)}U=\bigcup_{j=1}^m\{(-c+1,+1)\}. Define Si=U∪{(−c,−1),(−c+ki,+1)}∪⋃j=1n−m−2{(−c,−1)}S_i=U\cup\{(-c,-1),(-c+k_i,+1)\}\cup\bigcup_{j=1}^{n-m-2}\{(-c,-1)\}, where ki=1+(i−1)⌊(2c−1)/(N−1)⌋k_i=1+(i-1)\lfloor(2c-1)/(N-1)\rfloor for i∈[N]i\in[N]. Then all pretrained models coincide at A(Si)=−c+12A(S_i)=-c+\frac12, while the retraining targets satisfy A(Si∖U)=−c+ki2A(S_i\setminus U)=-c+\frac{k_i}{2}. Hence, their minimum pairwise separation is Δ=12⌊(2c−1)/(N−1)⌋>0\Delta=\frac12\lfloor(2c-1)/(N-1)\rfloor>0, recovering the original construction when N=2N=2.

W3. Our contribution is indeed theoretical, with the goal of characterizing the intrinsic difficulty of the problem rather than providing an algorithm for unlearning or experimentally evaluating unlearning. As such, our examples quantify the information necessary for any algorithm to satisfy the unlearning guarantee. However, we agree that an empirical demonstration would strengthen the results. Our preliminary decision-tree experiments support the bound: the bare learner lacks sufficient memorization, and even the optimal forget-only method fails. If the reviewer finds this useful, we will include these results in the revision.

W4. Our result provides a lower bound on the amount of information a learner needs to retain to satisfy a formal unlearning guarantee. Neither gradient ascent nor NPO provides such a guarantee in their standard formulations. Even if they did, the success of these methods would depend on whether the learner itself retained the required information and whether the unlearner could access it. As discussed, there are good reasons to explore whether the information memorized by overparameterized networks could indeed be efficiently accessed.

Q1. We thank the reviewer for the interesting question. We think knowledge entanglement and information loss in forget-only unlearning are related but distinct explanations for unlearning failures. Knowledge entanglement concerns the overlap of representations associated with different pieces of knowledge, including knowledge derived from forget and retain data, making them difficult to separate. In contrast, our information-loss explanation concerns the inability to identify the correct retraining target from the information available to the unlearner. We agree with the reviewer that if the representations were overlapping then it does make the problem of identifying the correct retraining target difficult. However, even if an algorithm could perfectly separate different pieces of knowledge, a forget-only unlearner would still need sufficient information to identify the correct retraining target; otherwise, it would face the same impossibility result. Conversely, having sufficient information to distinguish between retraining targets does not imply that an algorithm can successfully separate forget and retain knowledge. Thus, while both explanations concern the difficulty of removing forget-data influence while preserving retained knowledge, they address two distinct challenges: selective modification and identifiability, respectively.

Q2. We kindly refer the reviewer to our answer to Q1 of Reviewer CXWo. The purpose of using thresholds and medians as examples was to simply illustrate the applicability of our framework to fundamental learning problems, as commonly seen in learning theory and differential privacy literature.

AuthorsOpenReview ↗

Gentle Reminder

We would like to gently remind the reviewer that the discussion phase is approaching its conclusion. If there are any outstanding concerns, we would be happy to address them. Otherwise, we kindly request that the reviewer consider our rebuttal when reassessing their score.

Additionally, we would like to draw the reviewer’s attention to our general comment addressed to all reviewers, titled “Clarification on the Theoretical Nature of Our Contribution,” which aims to address the shared concern regarding the absence of experiments in our work.

AuthorsOpenReview ↗

Final Reminder Before the Discussion Deadline

With less than 24 hours remaining before the discussion phase concludes, we would kindly ask the reviewer to consider our responses and let us know if any concerns remain unaddressed. If the reviewer finds our clarifications satisfactory, we would appreciate their consideration when reassessing the initial score. We would also like to draw attention once more to our general comment, “Clarification on the Theoretical Nature of Our Contribution.”

Thank you again for your time and feedback.

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

The paper studies strict forget-only unlearning, where the deletion algorithm receives only the trained model (M) and forget set (U). It constructs shared-deletion examples in which different training sets produce the same or similar pretrained model, but deleting the same (U) leads to separated retraining targets. It then derives Rényi-unlearning lower bounds and mutual-information lower bounds on how much information about the training set must be retained to support arbitrary future deletions.

Critical strengths
  1. The paper identifies a worth-thinking information-theoretic obstruction: if (M,U) cannot distinguish between different retraining targets, no forget-only post-processing method can recover the correct one.
  2. The impossibility and memorization results form a coherent theoretical line and cover exact and approximate collisions, randomized learners, and several classical learning problems.
Critical weaknesses
  1. Limited empirical and practical implications. The paper does not provide any empirical results to validate its analyzed theoretical conditions. And although DNN is hard to analyze, I think the authors might provide or demonstrate some relevance to modern neural networks so that the theoretical analysis in this paper could provide some guidance of designing practical machine unlearning methods in this case. For example, it would strengthen the paper to summarize a principle that what sufficient statistics should be stored, how they can be accessed efficiently, or how to train a deletion-friendly representation.

  2. I appreciate the anlysis under Renyi unlearning, and I am also concerned with the other motivation of unlearning, privacy leakage. The retraining equivalence does matter but it does not characterize privacy leakage of forget data. I noticed that the conclusion of this paper that retaining more information may enable future forget-only deletion, but I am worrying whether this could lead to more severe privacy leakage of the forget data? Overall, I think the problem discussed and investigated in this paper is interesting, but its existing version might seem to be less insightful. It might be substantially strengthened by analyzing this privacy–memory–deletion trade-off.

Questions for authors
  1. Could the authors find or provide example where two functionally similar pre-trained models become substantially separated after deleting the same set? And if so, I am just curious whether this could be related to the failure of forget-only methods?
3 comments

We thank the reviewer for their useful feedback.

W1. As a lower-bound paper, our work shows a hardness result, rather than proposing a specific algorithm. However, for certain successful forget-only methods we tested, our preliminary experiments with decision trees show that they do obey the bound of Theorem 4.3. However, the reason it is generally difficult to experimentally verify mutual information lower bounds is that for high dimensional random variables, computing entropy can be difficult. Even for modest-depth trees, the entropy term of the bound becomes increasingly infeasible to compute, let alone an NN. Despite this, our result gives a general guiding principle: a successful unlearning method must either retain additional deletion-relevant state, or relax the unlearning guarantee. As we discussed, the form and accessibility of such state remains an open question, whose resolution would be a major breakthrough beyond this paper’s scope. However, some of the successful methods simply include the full retain set (Sekhari et al, 2021) second-order retain information (Neel et al., 2021) and historical parameter updates (Graves et al., 2021) as their state.

W2. Yes, the reviewer is right. Memorizing information about the dataset increases the privacy leakage. We can observe this from combining the known upper bound for an ε\varepsilon-differentially-private (DP) algorithm AA : I(A(S);S)<nεI(A(S); S) < n \varepsilon (Cuff & Yu, 2016); with Theorem 4.3 of our paper. This implies that ε\varepsilon must be larger than 1/n⋅RHS1/n \cdot RHS of our theorem, i.e., privacy cannot be too strict if we want to do forget-only unlearning. Note that this holds not just for the forget set, but also the retain set. We will include this paragraph in the updated draft.

Q1. We refer the reviewer to the Examples of Section 3 and the Proposition C.2, which guarantees the existence of such a pair of datasets for any zero-one loss ERM and any hypothesis class with a finite teaching dimension. The remainder of Section 3 is focused on precisely relating such examples to the impossibility of forget-only unlearning.

As an intuitive example, shared corrupted data (e.g., shortcut features, mislabeling, or poisoning) could mask differences in the "clean" retained data, yielding indistinguishable pretrained models but different retraining targets after deletion. Prior work shows that NNs can preferentially learn such patterns (Li et al., 2021), while unlearning methods can struggle to remove their effects (Pawelczyk et al., 2025; Kwon et al., 2026). Since a forget-only unlearner receives identical inputs in both cases, it cannot distinguish the datasets or closely match both retraining targets.

References.

  • Cuff, Paul, and Lanqing Yu. "Differential privacy as a mutual information constraint." Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016.
  • Li, Y., Lyu, X., Koren, N., Lyu, L., Li, B., & Ma, X. (2021). Anti-Backdoor Learning: Training Clean Models on Poisoned Data. Advances in Neural Information Processing Systems, 34.
  • Pawelczyk, M., Di, J. Z., Lu, Y., Kamath, G., Sekhari, A., & Neel, S. (2025). Machine Unlearning Fails to Remove Data Poisoning Attacks. International Conference on Learning Representations (ICLR).
  • Kwon, J., Kim, M., Lee, E., Lee, Y., Lee, S., & Kim, Y. (2026). Easy to Learn, Yet Hard to Forget: Towards Robust Unlearning Under Bias. Proceedings of the AAAI Conference on Artificial Intelligence, 40(7), 5782–5790.
AuthorsOpenReview ↗

Gentle Reminder

We would like to gently remind the reviewer that the discussion phase is approaching its conclusion. If there are any outstanding concerns, we would be happy to address them. Otherwise, we kindly request that the reviewer consider our rebuttal when reassessing their score.

Additionally, we would like to draw the reviewer’s attention to our general comment addressed to all reviewers, titled “Clarification on the Theoretical Nature of Our Contribution,” which aims to address the shared concern regarding the absence of experiments in our work.

AuthorsOpenReview ↗

Final Reminder Before the Discussion Deadline

With less than 24 hours remaining before the discussion phase concludes, we would kindly ask the reviewer to consider our responses and let us know if any concerns remain unaddressed. If the reviewer finds our clarifications satisfactory, we would appreciate their consideration when reassessing the initial score. We would also like to draw attention once more to our general comment, “Clarification on the Theoretical Nature of Our Contribution.”

Thank you again for your time and feedback.

Reviewer_T5GYOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies certified forget-only machine unlearning, where the unlearning algorithm Aˉ(M,U)\bar{\mathcal{A}}(M, U) only has access to the trained model M=A(S)M = \mathcal{A}(S) and the forget set UU, without the retained dataset S∖US \setminus U. Unlearning is defined through pointwise symmetric α\alpha-Rényi divergence between Aˉ(A(S),U)\bar{\mathcal{A}}(\mathcal{A}(S), U) and an empty-request reference Aˉ(A(S∖U),∅)\bar{\mathcal{A}}(\mathcal{A}(S \setminus U), \emptyset), together with a utility condition requiring Aˉ(w,∅)\bar{\mathcal{A}}(w, \emptyset) to stay close to ww. Section 3 derives a lower bound on ε\varepsilon (Theorem 3.1) when different datasets yield similar models before deletion but well-separated retrained models after deleting UU, with examples on 1D thresholds, empirical median, and hard-margin SVM. Section 4 lower-bounds the mutual information I(M;S)I(M; S) that a model must retain about its training set to support multiple deletion requests (Theorems 4.3 and E.2), applied to threshold ERM, coordinate PCA, block-sparse least squares, and matrix completion.

Critical strengths

None

Critical weaknesses
  1. Sloppy mathematical presentation, imprecise definitions, and flawed theorem statements. The paper has recurring issues in how its core objects and results are defined:

    • Sections 1 (line 041) and 2 (line 126) write Aˉ(M,U)\bar{\mathcal{A}}(M, U) as the definition of general unlearning before introducing the forget-only setting, even though most existing unlearning algorithms also use the retain set S∖US \setminus U.
    • Corollary 1.1 is presented as the very first result of the paper, before any theorem or formal definition, and omits the utility condition (without which a constant map trivially achieves ε=0\varepsilon = 0 on all datasets). Theorem 1.2 is also stated formally before definitions, treats SS as fixed (which gives I(M;S)=0I(M; S) = 0), uses undefined notation (MM for random SS, Wπ(<i)W _ {\pi(\lt i)}, Uπ(≤i)U _ {\pi(\le i)}), and writes the slack term as err(α,ε)\mathrm{err}(\alpha, \varepsilon) although in Theorem 4.3 it also depends on ∣W∣|\mathcal{W}|, η\eta, and learner randomness.
    • Section 2 defines A\mathcal{A} and Aˉ\bar{\mathcal{A}} with output space W\mathcal{W} (vectors) rather than distributions over W\mathcal{W}, mixing up deterministic vectors, random variables, and distributions in Definition 1 and Example 1. Since α\alpha-Rényi divergence is infinite when supports differ, Definition 1 gives ε=∞\varepsilon = \infty for any deterministic approximate unlearner and forces weight noise even on empty requests, which is never properly discussed.
    • Datasets are defined as ordered tuples S∈XnS \in \mathcal{X}^n (line 118), followed immediately by set operations (U⊆SU \subseteq S, S∖US \setminus U) that are undefined on tuples, while the proofs switch without explanation to multisets (Appendix C) and indexed copies (Appendix D.2). Similarly, "canonical threshold learner" means the leftmost positive point in Section 1 and Proposition 4.4, but the midpoint in Example 2.
    • Several formal statements break on valid inputs or edge cases: Definition 1 quantifies over all S∈XnS \in \mathcal{X}^n and ∣U∣≤m|U| \le m, yet Examples 2 and 4 are undefined when SS is non-separable or when deleting UU removes an entire class from S∖US \setminus U; Theorem 3.1 restricts rr to 0<u(r)<10 \lt u(r) \lt 1, leaving R=∅R = \emptyset in the noiseless case u(r)=0u(r) = 0; and Propositions 4.4 to 4.7 fix M=A(S)M = \mathcal{A}(S) to the standard learner (where I(M;S)=0I(M; S) = 0 in Propositions 4.6 and 4.7), making the bounds vacuously true because a learner with extra memory state is never formalized.
  2. Toy constructions far from practical unlearning and multiple unedited errors in the proofs. The concrete examples rely on contrived properties that do not reflect standard machine learning models. Section 1 motivates exact collisions A(S1)=A(S2)\mathcal{A}(S _ 1) = \mathcal{A}(S _ 2) with 1D thresholds, whereas in gradient-trained models two distinct datasets rarely produce the exact same weight vector even if their outputs coincide. In Example 4 (and Corollary 1.1), the ε→∞\varepsilon \to \infty lower bound for hard-margin SVM comes entirely from shrinking the data norm ∥x∥2=ρ→0\|x\| _ 2 = \rho \to 0 so that the unnormalized weight vector blows up (∥w∥2=1/ρ→∞\|w\| _ 2 = 1/\rho \to \infty) relative to fixed-variance Gaussian noise; normalizing the weights to w/∥w∥2w / \|w\| _ 2 bounds Δ=2\Delta = \sqrt{2} and removes the blow-up. No results are given for regularized smooth losses or neural networks. Finally, both Section 4 and the Appendices contain unedited proof errors: an undefined variable YY in the main text (lines 329 to 330, instead of W∅W^\emptyset), an unused function F(q)F(q) (line 372), Definition 5 passing the retrained model WW into the unlearner (Aˉ(W,U)\bar{\mathcal{A}}(W, U) instead of Aˉ(M,U)\bar{\mathcal{A}}(M, U), line 1248), an undefined ρs\rho _ s at the end of the proof of Proposition 4.7 (line 1228), and an undefined TT alongside a discrete sum ∑s∈S\sum _ {s \in \mathcal{S}} inside the proof of continuous Theorem E.2 (lines 1388 and 1425).

Questions for authors

Clarifications:

  1. Definition 1 requires (α,ε)(\alpha, \varepsilon)-Rényi unlearning for every S∈XnS \in \mathcal{X}^n and ∣U∣≤m|U| \le m. How are the learners in Examples 2 and 4 defined when SS is not separable, or when deleting UU removes all points of one class from S∖US \setminus U?
  2. In Propositions 4.4 to 4.7, if the learner is modified to store extra state M~=(Abare(S),Z(S))\tilde{M} = (\mathcal{A} _ {\mathrm{bare}}(S), Z(S)), does Definition 1 apply to the full state M~\tilde{M} or only to Abare\mathcal{A} _ {\mathrm{bare}}? If it applies to M~\tilde{M}, why doesn't the larger state space increase the Fano penalty term?
  3. Can ε→∞\varepsilon \to \infty occur for normalized hard-margin SVM (w/∥w∥2w / \|w\| _ 2) in fixed dimension dd, or for ℓ2\ell _ 2-regularized convex learners on bounded data?

Suggestions:

  • State the results in Section 1 informally instead of using premature Corollary and Theorem environments before the definitions, clarify upfront that Aˉ(M,U)\bar{\mathcal{A}}(M, U) applies only to forget-only unlearning, use a single consistent dataset representation (e.g., multisets) and distinguish vectors from distributions, fix the u(r)=0u(r) = 0 case in Theorem 3.1, and clean up the undefined variables (YY, TT, ρs\rho _ s) and the Aˉ(W,U)\bar{\mathcal{A}}(W, U) typo in Section 4 and the Appendices.
3 comments

We thank the reviewer for their constructive feedback.

Weakness 1

P3. We respectfully disagree. The outputs of AA and Aˉ\bar{A} are r.v.s with laws defined on W\mathcal W. As stated in Section 2, Aˉ\bar{A} is randomized, and both divergence terms in Definition 1 are outputs of Aˉ\bar{\mathcal{A}}, including the empty-request reference, even for deterministic AA. This standard formulation, first used by Sekhari et al. (2021), avoids infinite Rényi divergence from deterministic reference outputs. We explicitly defined dα(X,Y)d_\alpha(X,Y) as the divergence between the laws of r.v.s X,YX,Y, making Definition 1 and Example 1 well-defined.

P4. We will clarify that standard set notation and operations are interpreted in the multiset sense, resolving concerns about indexed copies, since only multiplicities matter. Furthermore, canonical threshold learner refers to a deterministic decision rule between the rightmost negative and leftmost positive. This is a convention; Example 2 could alternatively use the leftmost positive.

P5/Q1.

  • In the revision, we will restrict (∀S∈Xn)(\forall S \in \mathcal{X}^n) to admissible (∀S∈Sn)(\forall S \in \mathcal{S}_n), Sn⊆Xn\mathcal{S}_n\subseteq\mathcal{X}^n, fixing Examples 2 and 4. Without negatives, the threshold returns the leftmost domain point; without positives, just above the rightmost, with minor proof changes. For SVM, deleting a class preserves feasibility and the unique minimum-norm solution, requiring no modifications.
  • We will update Theorem 3.1 and its proof to include u(r)=0u(r)=0, redefining R={r∈(0,Δ/2):0≤u(r)<1}R=\{r\in(0,\Delta/2):0\leq u(r)<1\}, with −log⁡0=+∞-\log 0=+\infty and sup⁡∅=−∞\sup\emptyset=-\infty (vacuous bound if RR is empty). The proof requires a minimal change. For u(r)=0u(r)=0, Qi(Bi)=1Q_i(B_i)=1 for all ii, with pairwise disjoint BiB_i. If ε<∞\varepsilon<\infty, finite symmetric Rényi divergence between QiQ_i and TiT_i implies Ti(Bi)=1T_i(B_i)=1. Thus, for any i≠ji\neq j, Ti(Bi)=1T_i(B_i)=1 but Tj(Bi)=0T_j(B_i)=0, giving dα(Ti,Tj)=∞d_\alpha(T_i,T_j)=\infty. This contradicts data processing: dα(Ti,Tj)≤dα(Mi,Mj)≤δα<∞d_\alpha(T_i,T_j)\leq d_\alpha(M_i,M_j)\leq\delta_\alpha<\infty. Hence, no finite ε\varepsilon is possible.
  • Finally, Propositions 4.4–4.7 illustrate the impossibility of forget-only unlearning for standard learners through necessary memorization bounds. Overcoming this may require augmenting their output space (or model class) to retain deletion-relevant information. We agree that such augmentation requires reevaluating both memorization and the corresponding lower bounds. Nevertheless, our results remain important in identifying the need for such modifications to enable successful forget-only unlearning.

Weakness 2

  • The introduction merely illustrates shared deletion; Definition 3 formalizes this with distributional collisions, accommodating randomized learners such as SGD.
  • We agree normalization removes SVM blow-up, as noted around line 243, and can present it first instead. Note that the sensitivity is at least comparable to the classifier norm, so sensitivity-scaled noise can nevertheless destroy SVM utility.
  • We derive a ridge-regression bound with fixed λ>0\lambda>0 (smooth, strongly convex). Set d=2bd=2b, n=8bn=8b (b≥1b\geq1), with one-hot inputs, labels {−1,+1}\{-1,+1\}. Draw independent Cj∼Unif({1,2,3})C_j\sim\mathrm{Unif}(\{1,2,3\}). Put CjC_j of each label at 2j−12j-1, and 4−Cj4-C_j at 2j2j. The ridge output is zero: I(M;S)bare=0I(M;S)_{\mathrm{bare}}=0. Theorem 4.3 gives I(M;S)≥n8[log⁡3−h(β3)−β3log⁡2]I(M;S)\geq\frac{n}{8}[\log 3-h(\beta_3)-\beta_3\log 2], β3=min⁡{eγεηγ,2/3}\beta_3=\min\{e^{\gamma\varepsilon}\eta^\gamma,2/3\}. For β3<2/3\beta_3<2/3, this is positive despite zero bare memorization. We will include the full proof in the final version. For NNs, see our response to Reviewer CXWo, Q1.

Q2. Definition 1 applies to the augmented state Mˉ\bar{M}, requiring reevaluation of memorization and Theorem 4.3's bounds. The ∣W∣|\mathcal{W}| in Fano penalty is pessimistic, and we used it for ease of presentation. For request ii, let NiN_i bound the conditional support of Wπ(i)W_{\pi(i)} given prior targets and requests, and βi\beta_i its conditional recovery error. The penalty becomes h2(βi)+βilog⁡(Ni−1)h_2(\beta_i)+\beta_i\log(N_i-1) (h2h_2: binary entropy). Augmentation may increase this conditional support, but also decrease it as earlier augmented targets reveal more information.

Q3. For an s.d.e. (Δ>0\Delta>0), empty-request outputs supported within r<Δ/2r<\Delta/2 (Γ(r)=0\Gamma(r)=0) have disjoint reference supports, forcing ε=∞\varepsilon=\infty. We showed normalized SVMs have such an s.d.e. For ℓ2\ell_2-regularized convex learners, e.g., ridge regression admits exact collisions (shown above), but fixed-size regularized mean estimation does not. Thus, divergence follows from unbounded Δ\Delta under concentrated noise or bounded-support empty-request randomization with Δ>0\Delta>0.

We emphasize that most concerns are presentational and do not affect the soundness or substance of our results. We will correct notation and editing artifacts, and address the remaining reviewer's suggestions in the revision.

AuthorsOpenReview ↗

Gentle Reminder

We would like to gently remind the reviewer that the discussion phase is approaching its conclusion. If there are any outstanding concerns, we would be happy to address them. Otherwise, we kindly request that the reviewer consider our rebuttal when reassessing their score.

Additionally, we would like to draw the reviewer’s attention to our general comment addressed to all reviewers, titled “Clarification on the Theoretical Nature of Our Contribution,” which aims to address the shared concern regarding the absence of experiments in our work.

AuthorsOpenReview ↗

Final Reminder Before the Discussion Deadline

With less than 24 hours remaining before the discussion phase concludes, we would kindly ask the reviewer to consider our responses and let us know if any concerns remain unaddressed. If the reviewer finds our clarifications satisfactory, we would appreciate their consideration when reassessing the initial score. We would also like to draw attention once more to our general comment, “Clarification on the Theoretical Nature of Our Contribution.”

Thank you again for your time and feedback.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Clarification on the Theoretical Nature of Our Contribution

We thank the reviewers for their feedback! We address their individual concerns and questions via replies to their respective reviews below.

One common concern that we would like to address here is about the lack of empirical results in our work. The nature of our results is purely theoretical and therefore, we selected "learning theory" as the primary area for our submission, which according to ICLR guidelines relaxes requirement for experimental results and focuses the evaluation of the theoretical results. Furthermore, our work is about hardness results (i.e. lower bounds); as is natural and customary in CS/learning theory literature, we do not provide experimental results to evaluate this hardness. By the very nature of impossibility and hardness results, it is somewhat difficult to experimentally verify the non-existence of any algorithm that can achieve the said property; instead, we prove it mathematically. Instead, if our focus were on upper bounds (or algorithmic results), we would have been more than happy to provide experimental results.

We hope this clarification helps position and clarify the contribution of our work and therefore request the reviewers to judge the work in that light.

Dear Area Chair,

We have responded to the reviewers' questions and concerns in our rebuttal and we have not heard anything back. We have also posted a general comment highlighting that the main nature of our work is theoretical and explained why many of the reviewers' concerns are less applicable to a learning theory work like ours. We hoped that the comment would help clarify that.

But we haven't heard back anything throughout the whole period. With the discussion deadline approaching, could you please encourage them to review our responses and indicate whether their concerns remain?

If they are unable to respond in time, we would appreciate your consideration of the new results in your assessment of the paper. Thank you for your time and consideration.

Best Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.