acceptodds
Under review as a conference paper at ICLR 2027

Is Retraining Enough? Coordinated Local Editing for Certified Vertical Federated Unlearning

Abstract

Vertical federated unlearning (VFU) removes a departed party's feature block from a model jointly trained by institutions holding different features of one population. VFU faces a distinctive obstacle: feature blocks are correlated across institutions, so retraining leaves a predictable share of the departed signal in the retained encoders. Current methods edit inside the task objective and settle at the level retraining attains, and they certify model parameters rather than the embeddings, read-out and caches an auditor reads. To address these, we first establish a two-floor separation: the recoverable share splits into a task-required part and a free part whose removal locates an encoding-layer floor beneath the task-objective floor. We then design CLEAVE, a Coordinated Local Editing framework for Attested Vertical Erasure. Within this framework, Residual Splitting measures the joint residual from statistics the active party already holds and separates task-required from removable directions. Coordinated Local Editing then solves one block-diagonal edit that hands each retained party a local adapter, so no party combines features held by others. In addition, State Purge and Certification refits the read-out, purges the requested state and certifies leakage for a declared decoder class and audited interface. Across three datasets, four deletion granularities and thirteen published baselines, CLEAVE most consistently lowers the recovered share and the issued level while retaining utility close to retraining in one communication round. For example, on Letter under party unlearning, CLEAVE lowers the recovered share from 0.727 under retraining to 0.331 at higher utility.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
vertical federated learning, machine unlearning, certified unlearning, information leakage, feature reconstruction, data deletion, privacy

Reviews

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

The paper studies why information about a departed party can remain recoverable after retraining in vertical federated learning. The authors propose CLEAVE, which combines coordinated local edits with refitting of the prediction layer. It provides theoretical guarantees for a family of linear reconstruction models and evaluates how well the method reduces recoverable information while maintaining prediction accuracy.

Critical strengths
  1. The problem and method are well motivated. The paper distinguishes between removing a party's contribution to training and reducing the information that can be recovered from correlated data held by other parties. For linear reconstruction models, the analysis tries to separate information connected to the prediction task from additional information that can be recovered. It also studies the constraints introduced by requiring each party to edit only its own representation.

  2. The experiments cover three datasets and different types of deletion, and compare against retraining and existing unlearning methods.

Critical weaknesses
  1. The usefulness of the certificate in practice needs clearer evidence. The paper provides a theoretical guarantee; however, the confidence intervals used in the empirical audits rely on bootstrap resampling. There is no information about the numerical error terms needed to show that the theorem gives a useful bound for the main experiments.

  2. The comparison at similar prediction accuracy could be clearer. The paper also includes tests with more flexible reconstruction models. However, it does not compare CLEAVE with other federated unlearning methods under the same models. It would be good to see how CLEAVE performs there.

Questions for authors
  1. The certificate in practice: For one experiment, could the authors calculate the theoretical bound using the actual audit sample size and error terms? Does it give a useful upper limit on recoverable information, and which reported results are covered by that guarantee?

  2. Comparison with other methods: Could the authors extend the existing comparisons to evaluate CLEAVE, retraining, and representative federated unlearning methods using the same nonlinear reconstruction model and at similar prediction accuracy? How much of CLEAVE's reported advantage remains?

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

The paper studies whether retraining is sufficient for vertical federated unlearning when retained parties hold features correlated with those of a departing party. It distinguishes removing direct training dependence from reducing the information that remains reconstructible.

The proposed method, CLEAVE, separates task-required and removable information, jointly designs adapters that each retained party applies locally, and refits the read-out while purging obsolete state. The paper provides reconstruction floors under linear decoding, characterizes the cost of local deployment, and develops a certificate for a fixed decoder class and audited interface. Experiments cover three datasets, four deletion granularities, and thirteen published baselines.

Critical strengths
  • The distinction between retraining and reducing reconstructible information is useful. Correlated retained features can continue to reveal a departed party’s information after retraining. The two-floor analysis makes this issue precise in the linear setting and explains which information can be removed while preserving the defined task utility. Separating the cost of local deployment from the solver’s remaining error also makes the analysis more informative.

  • The method connects representation editing with the state actually left after deletion. Jointly designed local adapters, read-out refitting, and cache purging form a coherent protocol. The experiments provide encouraging evidence across several deletion settings. For example, on Letter party deletion, recovered share falls from 0.727 with retraining to 0.331 with CLEAVE, while accuracy changes from 0.747 to 0.739. This is a substantial reconstruction reduction for a relatively small accuracy cost.

Critical weaknesses

The reported certificates need a clearer connection to the theoretical guarantee. Theorem 5 requires analytic sampling and approximation slacks, whereas Section C.5 describes bootstrap intervals and explicitly distinguishes them from that guarantee. It remains unclear whether the reported ε^\hat{\varepsilon} values are theorem-backed bounds or empirical uncertainty estimates. Since certification is a central contribution, the paper should report the analytic bounds at the experimental audit sizes and specify the decoder radius used.

The comparisons do not fully isolate the benefit of coordination at comparable utility. Published baselines use their original operating points, while CLEAVE explicitly targets a leakage–utility constraint. The component ablation helps, but its variants also achieve different accuracies. Appendix D adds useful projection and adversarial controls, partly through the separate CLEAVE-RP variant. A comparison of the original CLEAVE against independent local editing at matched accuracy would make the coordination claim stronger. The abstract’s “higher utility” claim also needs correction: Table 1 reports 0.739 for CLEAVE versus 0.747 for retraining.

Questions for authors
  • Do the reported certificates use the analytic bound in Section 3.4, and how tight is it in practice?

  • Does coordination still improve reconstruction suppression over independent local editing at matched accuracy?

  • For the unmet targets in Figure 5(b), are the constraints inherently infeasible, or does the surrogate solver fail to find a feasible edit?

  • What are the ranks of the learned adapters, and do the reconstruction reductions persist when the decoder’s norm constraint is relaxed?

Reviewer_ZGTzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies vertical federated unlearning, where institutions that hold different features of the same people train one model, and later a party, a feature subset, a group of samples or a class must be removed. The starting point is that retraining on the remaining blocks removes direct use of the deleted block but not the part of its signal that correlated blocks can still predict. The authors measure this with a residual index, the share of the deleted footprint that a least squares decoder can recover from the retained embeddings. They split this index into a part the task needs and a free part outside the label predictive subspace, which a linear edit can remove without changing second-order utility.

Critical strengths
  1. The paper gives VFU a clear target and puts a price on locality. Prior VFU work treats retraining as the gold standard. Fig. 2a shows that on correlated vertical splits, retraining leaves a predictable share of the deleted block in the retained embeddings. Fig. 3a shows that on Adult VertiBench federations the free part is more than half of this residual for two-thirds of the departing parties. Splitting the residual into a task part and a free part turns the observation into a quantity that can be measured and reduced. Theorem 3 then prices the rule that each party may edit only its own block. The surcharge is zero when only one block can be edited, Eq. 27 gives the exact utility floor for correlated blocks in closed form, and Eq. 30 shows that for a scalar label the surcharge is a weighted variance across blocks. This locality analysis is the most original part of the paper, and later VFU work can reuse both the target and the cost split.

  2. The evaluation is broad and reports results that do not favor the method. It covers three datasets, four deletion units, thirteen baselines and five seeds, with a component ablation in Table 4. The authors also include stress tests that go against CLEAVE. In Table 6 a stronger decoder recovers more than the declared probe, and refitting a nonlinear head after the certificate is issued pushes the margin to minus 0.193 on Letter and minus 0.163 on Fashion-MNIST. Appendix B reports that 21.7% of 540 requests miss the utility target. The faulty release study in D.5 is useful. Checking the committed artifacts together with the statistical audit rejects every faulty release tested, while the statistical audit alone catches 6.5% of missing adapter releases and none of the stale head releases. The appendix is also direct about scope. It says that Theorem 2 does not describe encoders changed by retraining and that Theorem 5 does not apply when the analytic slack is replaced by a bootstrap quantile. This openness makes the reported numbers easier to trust.

Critical weaknesses
  1. The main tables measure the quantity CLEAVE optimizes, and evidence beyond it is thin. Recovered share is the leakage of the declared norm-bounded linear decoder, defined in C.4 and C.5, and CLEAVE constrains this same quantity with a target of half the residual left by the identity edit. The baselines run at the settings chosen in their own papers, as C.3 states, and they do not target this quantity. On CIFAR-100 sample deletion, their accuracy falls as low as 0.015 for Han et al. and 0.055 for SCRUB. Tables 1 to 3 have no comparison at matched utility and no concept erasure or projection baseline such as LEACE. As a result, they mostly show that limiting linear leakage lowers linear leakage.

  2. The term: certificate, in the theory is not the one computed in the experiments. Theorem 5 is a conditional finite sample bound, and its slack comes from a covering argument in Lemma 4. That slack grows with p times d_A, with the norm bounds B_Z and B_X, and with the decoder radius β. Section C.5 instead reports empirical intervals from 200 bootstrap resamples at δ = 0.05 and says that the guarantee of Theorem 5 needs the analytic slack. The paper never reports the value of that slack, so the experiments do not show that a certificate built from the theorem would be informative at the audit sizes used. Even with the bootstrap, some issued levels go above 1, for example 1.163, 1.352 and 1.104 in the Baseline row of Table 4 and several points in Fig. 5c, and Eq. 57 caps these at a bound that says nothing.

Questions for authors
  1. For Letter and Fashion-MNIST at least, could you plot recovered share against accuracy, or report one point at matched accuracy, over five seeds? Please include retraining, the strongest baselines, and retraining followed by a per block linear eraser such as LEACE or your independent local edit, and evaluate each with both the declared linear probe and the stronger decoder. A clear margin for CLEAVE under the stronger decoder would change my view of the first weakness.

  2. In the setting of Table 6, how much does the adaptive decoder with 1024 random features recover from the retrained federation? This number shows whether the gap between 0.727 and 0.331 on Letter holds outside the linear class.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.