acceptodds
Under review as a conference paper at ICLR 2027

Noise-free Provable Trustworthy Machine Learning via Distribution-Specific Indistinguishability

Abstract

Indistinguishability guarantees in trustworthy machine learning are usually obtained by injecting noise, most prominently through Differential Privacy (DP). We develop a noiseless alternative for data-influence problems such as poisoning, memorization, and copyright protection. Let be the part of the training data whose influence we want to control (poisoned samples, a sensitive record, or a protected artwork), and let be the rest. A model trained on alone never sees and is taken as a safe reference. Our goal is to make the model trained on statistically indistinguishable from this reference, so that the reference's trustworthiness carries over. Operationally, instead of injecting algorithmic randomness such as noise, we exploit input-wise randomness: the benign data is modeled as a random sample from an unknown distribution, while may be chosen adversarially after observing . We formalize this as Distribution-Specific Indistinguishability (DiSI): a DiSI algorithm then transfers the reference's high-probability trustworthiness to the model trained on . We instantiate DiSI through consistency-robust gradient operators that make the target and reference updates agree exactly, except on a failure event whose probability decays exponentially in the number of sources. Across image and text backdoor benchmarks, DiSI sharply reduces attack success while preserving far more utility than noise-based baselines; in generative-model fine-tuning, it also reduces outlier memorization, membership leakage, and resemblance to protected artworks.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Distribution-Specific Indistinguishability, noise-free trustworthiness, consensus robustness

Reviews

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

This paper proposes Distribution-Specific Indistinguishability (DiSI), a noise-free framework for reducing the influence of potentially malicious or sensitive training data. It uses randomness in benign dataset and quantizes per-source gradients, replacing coordinate-wise averaging with thresholded majority vote or maximal-gap operators that abstain when the votes are ambiguous. Under assumptions on benign source independence and population vote gaps, each coordinate update matches its clean counterpart except with probability exponentially small in the number of benign sources. A bound over coordinates and training steps then transfers high probability properties of a safe reference model to the model trained with the selected data. Experiments on image and text backdoors, outlier memorization, copyright image similarity, and membership inference report better performance.

Critical strengths
  1. Instead of injecting algorithmic noise like DP and DaSI, the authors exploit randomness in benign training data to obtain high agreement probability between training on the full dataset and on a reference dataset that excludes the malicious data. Because this agreement is not tied to a particular risk event, the same argument can transfer the reference’s guarantees across backdoors, outlier memorization, copyright image similarity, and membership inference.

  2. For both TMV and TMGC, the paper identifies when malicious votes can change a coordinate update and gives conditions that make such cases unlikely. It also explains the role of the threshold, extends the results to sources with different distributions and replaced votes, and shows how extra data can be used to check parameter choices.

  3. The evaluation covers backdoor and data poisoning defense in image and language models, memorization mitigation, copyright protection, and membership inference. Across these tasks, DiSI generally performs better than standard training on the reported risk measures. The image backdoor results are especially strong: DiSI keeps attack success low while retaining much higher clean accuracy than DP-SGD and DaSI.

Critical weaknesses
  1. There are several baselines that are worth considering. FLCert (Cao et al., IEEE TIFS 2022) follows a similar idea. It splits clients into groups and takes a majority vote over the models trained on them, which gives a provable guarantee against a bounded number of malicious clients. It should be compared on the classification experiments. RLR (Ozdayi et al., AAAI 2021) is a standard baseline for backdoor defense in federated learning, and it also aggregates the signs of client updates in each coordinate. SignSGD with majority vote (Bernstein et al., ICLR 2019) is the special case of TMV with two quantization levels and =0. The authors already cite it and analyze it in Appendix F, so it is a natural ablation.

  2. As the authors mentioned in Section 3.3, the certificate is not satisfied in real experiments, which results in the high inconsistency rates(1.69% for n=10n=10, η=0.1\eta=0.1 on ResNet-20). The evidence of robustness is therefore entirely empirical, yet all evaluated attacks are standard data poisoning attacks that do not target DiSI. An adversary aware of the operator could exploit exactly these disagreeing coordinates: under TMV it can choose which benign majority updates are applied, and under TMGC it can inject its own values in coordinates where the votes are spread out. The authors should evaluate at least one adaptive attack of this kind.

  3. Four entries of Table 1 are trained with the loss of ABL (Li et al., 2021a) instead of cross entropy. Neither DiSI without ABL nor ABL alone is reported. In particular, on CIFAR-100 both operators rely on ABL for the clean-label SIG attack, so the effectiveness of DiSI alone against SIG on CIFAR-100 is not established. The authors should report the results of DiSI without ABL and of ABL alone for these entries, and explain why ABL was needed.

Questions for authors
  1. In the combined experiments, adding DiSI to an existing defense sometimes yields a higher ASR than DiSI alone (e.g., on CIFAR-10 BadNets, 58.94% for CLP+TMV in Table 7 vs. 1.79% for TMV in Table 1; on the refusal task, 55.7–59.2% for CROW+DiSI in Table 6 vs. 20.3–30.4% for DiSI in Table 2). How were the combined runs set up, for example, the order in which the two defenses are applied and whether the DiSI configuration matches the main experiments, and what causes this difference?

  2. On the refusal task in Table 2, the original model has a refusal rate of 0.00 without the trigger (Table 6) but 100.00 under BadNets, 0.00 under Sleeper, and exactly 50.00 under the other three attacks with the trigger. What does the “Original” row refer to, and how is ASR computed?

7 comments
AuthorsOpenReview ↗

Acknowledgments and W1

We sincerely thank Reviewer PD3h for the constructive suggestions and for catching the error in Table 2. We ran the requested baselines, an adaptive attack, and the ABL ablation; results are below and in the revised PDF.

4.1 W1: FLCert, RLR, and Majority-Vote SignSGD

We evaluated all three on CIFAR-10 under BadNets, Blended, and label flipping (LF) in the setting of Table 1 (ten sources, one malicious, 300 epochs). For FLCert, we used the disjoint-group variant (FLCert-D), partitioning the ten sources into N=5N=5 disjoint groups of two sources each and certifying against one malicious client.

Table 1: Clean accuracy (Acc.) and attack success rate (ASR) on CIFAR-10, in percent. Bold marks the best result in each column.

DefenseBadNets Acc. ↑BadNets ASR ↓Blended Acc. ↑Blended ASR ↓LF Acc. ↑LF ASR ↓
FLCert81.965.3382.178.8081.946.01
RLR80.9595.4182.1299.9681.5166.13
SignSGD (majority vote)80.0694.7082.4999.9875.4611.09
ΦTMV\Phi_{\mathrm{TMV}}82.341.7982.272.1282.395.10
ΦTMGC\Phi_{\mathrm{TMGC}}84.641.9883.931.7883.264.88

Why SignSGD and RLR fail empirically. SignSGD and RLR both fail on the two trigger-based attacks (ASR above 94%). SignSGD is, as the reviewer notes, TMV with two levels and τ = 0, so this row is the ablation of the threshold: without it, the vulnerable band is the set of near-ties [0, c], which is where weak-signal coordinates concentrate, and one malicious vote decides them. RLR does threshold sign agreement, but on coordinates that pass it applies the average update, so the malicious source still contributes its magnitude there. TMV and TMGC output a value determined by the bin counts alone and abstain otherwise. The same pattern holds for coordinate-wise median and trimmed mean, which leave ASR above 99% in this setting (Table 8): estimation-robust aggregators do not remove the backdoor.

FLCert’s guarantee and ours are different statements. The reviewer notes that FLCert follows a similar idea and comes with a guarantee. Both methods vote, but what is proved differs on three points, and this difference is the core of our contribution.

(1) What the probability is over. FLCert takes the clients and their data as fixed. For a test input, its “label probability” is the fraction of client groups whose model predicts a given label. In FLCert-P the only randomness is the server’s own random sampling of groups, and the probabilistic statement is that the Monte Carlo estimate of the certified level is wrong with small probability; FLCert-D is deterministic. Neither is a statement over a data distribution: nothing is said about how often the vote gap is large for the data or inputs one will encounter. DiSI’s probability is over the benign data, for an unknown D. Theorems 3.2 and 3.3 bound, before training, the probability that an adversary can change the outcome.

(2) A certificate for the favorable case versus consistent behavior in every case. FLCert proves: if the gap between the largest and second-largest label counts for a test input is large enough, a bounded number of malicious clients cannot change the majority label. It certifies the inputs for which majority vote happens to be safe. When the gap is small the certified level is zero, the ensemble still outputs the majority label, and that label is unprotected. DiSI’s operator has two outputs, the majority value or ⊥, and the guarantee is that the choice between them and the value returned are the same with and without the adversarial sources, except with probability ∆. The uncertain case is handled by the mechanism, by abstaining, instead of being left outside the guarantee.

AuthorsOpenReview ↗

W1: FLCert, RLR, and Majority-Vote SignSGD (continued)

(3) What is protected. FLCert protects the predicted class label of one test input at a time, using an ensemble of separately trained models. DiSI protects the output law of a single trained model, hence any event of it (Lemma 2.3), which is what allows it to address generative fine-tuning, memorization, and membership inference, where there is no label to vote on.

The setting is correspondingly more demanding. FLCert needs one label to be stable, after training, when the realized gap permits. DiSI needs every coordinate of every update of one training run to agree with the reference run, for an unknown distribution, an adversary who chooses its data after seeing the benign data, and a trust event that is a black box. The two reported quantities are therefore not comparable: FLCert’s certified accuracy at ten clients (65.77%, 67.55%, 65.93% for BadNets, Blended, LF) is the fraction of test inputs whose realized gap happens to suffice, whereas ∆ bounds the change in probability of any event of the model and, as Section 3.3 states, needs more sources to be small.

SignSGD and RLR. Majority-vote signSGD proves a convergence rate under unimodal symmetric gradient noise against blind adversaries; it makes no claim about the adversary’s influence on the trained model. RLR is an empirical defense supported by a conjecture about how backdoors are implanted and by a convergence analysis; it gives no guarantee on the backdoor. Neither abstains: both always apply an update.

Empirically, both DiSI operators have lower ASR and higher clean accuracy than all three baselines on all three attacks, with a single model. FLCert, RLR, and SignSGD are now discussed in the related work, and the new rows are added to Table 8.

AuthorsOpenReview ↗

W2: Adaptive Attacks

We agree that the attacks in Table 1 do not target DiSI, and we now evaluate one that does. We first state what the theory covers and then describe the attack.

What the theory covers. The analysis is stated against the strongest adversary. In Section 3 the cc adversarial votes are arbitrary functions of the benign votes, and the local inconsistency rate of Section 3.2 is

Δ(D)=Pr⁡[∃A, ∣A∣≤c:Φ(R∪A)≠Φ(R)],\Delta(D) = \Pr \left[\exists A,\ |A| \le c : \Phi(R \cup A) \neq \Phi(R)\right],

the probability that the benign θR\theta_R histogram can be changed by some placement of the adversarial votes. The guarantee therefore holds against an adversary who sees the benign data and then submits any gradient it likes, which is more than any data-poisoning attack can do. The guarantee is quantitative in the number of sources: it is informative with a few hundred (Section 3.3) and vacuous with ten, where, as the reviewer observes, the evidence is empirical.

The adaptive attack. We keep the threat model of Section 4 and of every attack in Table 1, data poisoning: the adversary controls the data of its source, and its vote is the gradient of that data. Within this model we give the adversary everything else. It knows the operator and (q,τ)(q, \tau), it sees the model at every step, and it sees the benign samples of the current step before choosing its own, so it re-crafts its data at every step (which is stronger than the fixed set A of Definition 2.1).

At each step the adversary computes the benign votes, finds the coordinates on which a single vote can change the operator’s output (the “disagreeing coordinates” the reviewer refers to), and determines for each the vote that moves the output toward the backdoor: it reinforces the leading bin when that bin helps the backdoor, and votes for the runner-up to force an abstention or a flip when it does not; under TMGC it votes into or next to the leading cluster in the same way. It then optimizes ℓ∞\ell_\infty-bounded perturbations of its poisoned minibatch by gradient matching (Geiping et al., 2021; Souri et al., 2022) so that the minibatch gradient lands in those bins on the vulnerable coordinates and stays aligned with the backdoor gradient elsewhere, and submits the gradient of the crafted images.

Table 2. BadNets on CIFAR-10 with one malicious source

Standard poisoning versus the operator-aware adaptive attack (clean accuracy / ASR, %).

OperatorAttackn=10n=10
TMVStandard81.24 / 96.15
TMVAdaptive, ϵ=8/255\epsilon=8/25577.44 / 4.36
TMGCStandard81.57 / 96.83
TMGCAdaptive, ϵ=8/255\epsilon=8/25579.58 / 2.06

At n=10n=10, the operator-aware adaptive attack (ϵ=8/255\epsilon=8/255) reduced ASR relative to standard poisoning from 96.15% to 4.36% under TMV and from 96.83% to 2.06% under TMGC. Clean accuracy decreased from 81.24% to 77.44% under TMV and from 81.57% to 79.58% under TMGC.

Scope. An adversary that is not bound to data and submits an arbitrary vector after seeing the benign votes (model poisoning) is the adversary of the theory. Against it the protection is the bound itself, which requires the source counts of Section 3.3; with ten to fifty sources we make no empirical claim of robustness against such an adversary, and Section 5 now says so.

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

This paper proposes Distribution-Specific Indistinguishability (DiSI), a noise-free framework for controlling data influence in trustworthy machine learning. As the conventional indistinguishability guarantees, in particular differential privacy, typically rely on algorithmic noise, DiSI instead proposes to exploit randomness in the input data under a specified contamination model. The central idea is to transfer trustworthiness properties from a safe reference model trained on benign data to a model trained on potentially contaminated data. To make this guarantee operational, the authors introduce consistency-robust gradient operators based on quantization, histogram statistics, and thresholding, with theoretical bounds on their inconsistency probabilities. The framework is evaluated on extensive empirical settings across backdoor defense, memorization mitigation, membership inference, and copyright protection.

Critical strengths
  1. The paper presents a clear and conceptually interesting approach to trustworthy machine learning by considering noise-free indistinguishability from safe reference models. The distinction between input-wise randomness and algorithmic randomness provides a useful perspective on controlling data influence.

  2. The paper provides a coherent progression from the contamination model and consistency guarantees to concrete gradient operators and their theoretical analysis. The proposed threshold majority vote and maximal-gap cut operators are clearly defined, and the analysis includes inconsistency bounds, trajectory composition, and parameter certification.

  3. The paper is generally well organized, and the motivation, theoretical framework, and proposed algorithms are presented clearly. The experiments cover several relevant applications, including image and text backdoor defense, memorization, membership inference, and copyright protection. These results provide evidence of the practical usefulness of the proposed approach.

Critical weaknesses
  1. The framework transfers trustworthiness properties from a reference model, instead of establishing these properties independently. Its guarantees therefore depend on whether the reference model is actually trustworthy for the property of interest. Although the paper discusses imperfect references, it remains unclear how this assumption can be verified or justified in practical applications. This may limit the interpretation of the resulting guarantees.

  2. The analysis relies on assumptions about benign data sources and their gradient distributions, including independence and suitable histogram gap conditions. While the paper provides extensions to independent heterogeneous sources, the applicability of these conditions to more general training settings remains unclear. In particular, it is not evident how often the required conditions hold throughout training or how they can be reliably verified in practice.

  3. The theoretical analysis establishes local consistency bounds for gradient operators and extends them to the training trajectory through conditional consistency assumptions and a union bound. However, gradient distributions depend on the evolving model parameters and may change throughout training. It remains unclear under what conditions in practical settings the local guarantees can be maintained along the entire trajectory.

Questions for authors
  1. Safe-reference validity.

Lemma 2.3 transfers the reference's trustworthiness guarantee to the contaminated model:

\geq \Pr(\operatorname{Alg}(R)\in\mathcal{T})-\Delta.$$ However, the usefulness of this guarantee depends on the baseline trustworthiness of $\operatorname{Alg}(R)$. How can this property be established or assessed in practical applications? In particular, when the reference model is imperfect, how should the resulting guarantee be interpreted? 2. **Distributional assumptions and adaptive training.** Theorems 3.2 and 3.3 establish local consistency guarantees under assumptions on the benign gradient distributions and their histogram gap structures. However, these distributions may depend on the evolving model parameters w(t). What conditions ensure that the local consistency guarantee $$\Pr\bigl(\Phi(R)=\Phi(R\cup A)\bigr)\geq 1-\Delta$$ continues to hold along the training trajectory? In particular, how sensitive are the guarantees to changes in the gradient distributions across iterations or to dependence between benign sources? 3. **Local-to-global guarantees.** Proposition 3.4 establishes the trajectory-level bound $$\Pr\bigl(w_X^{(T)}\neq w_R^{(T)}\bigr) \leq \sum_{t=1}^{T}\sum_{j=1}^{d}\Delta_{t,j} \leq dT\Delta,$$ under conditional consistency assumptions. Is it possible to obtain a more informative global guarantee without requiring exact agreement at every coordinate j and iteration t?
6 comments
AuthorsOpenReview ↗

Acknowledgments and W1/Q1

We sincerely thank Reviewer 8gzJ for the positive assessment and for three precise questions about the scope of the guarantees.

W1/Q1: Reference Validity and Imperfect References

DiSI separates two risks, and it controls only one of them. Let δR\delta_R be the probability that training on the reference R fails the trust requirement T . If the contaminated and reference runs agree with probability at least 1 − ∆, Lemma 2.3 gives

Pr⁡(Alg⁡(R∪A)∉T)≤δR+Δ.\Pr(\operatorname{Alg}(R\cup A)\notin\mathcal T)\le\delta_R+\Delta.

The reference determines δR\delta_R; DiSI controls ∆, the additional risk from including A. This requirement is shared by every indistinguishability-based argument, including differential privacy and DaSI: closeness to a reference is only as valuable as the reference.

How the reference is constructed (Appendix G). In the settings we study, the reference is defined by exclusion and needs to be safe only for the specific event of interest:

  • Sample-specific memorization and membership inference: for a target x, R = X \ {x}. A model trained without x cannot memorize it beyond what the population reveals.

  • Copyright: for a protected collection A, R = X \ A, the no-access reference.

  • Poisoning: if an unknown source i⋆ is malicious, R = X \ X_{i*} . The learner does not need to identify i⋆, because the bound is uniform over the identity and content of the malicious source.

When the reference is imperfect. The bound degrades transparently in two ways. If a further fraction ρ of the nominally benign sources may be contaminated, they can be treated as adversarial: the analysis is rerun with ηeff=η+(1−η)ρ\eta_{\mathrm{eff}}=\eta+(1-\eta)\rho, provided ηeff<1/2\eta_{\mathrm{eff}}<1/2. Otherwise, pre-existing failures of the reference enter through δR\delta_R, and the guarantee becomes a relative one: including A raises the failure probability by at most ∆. Our text-backdoor experiment illustrates the relative reading. The original model already has 42.62% Jailbreaking ASR with triggers (Table 2); unprotected fine-tuning on poisoned data raises it to 79.68%, while TMV and TMGC hold it at 44.76% and 49.29%. DiSI prevents the contaminated subset from materially worsening the baseline; it does not repair an unsafe baseline.

How δR\delta_R is assessed in practice. By running the same audit on the reference as on the protected model: ASR on held-out triggered inputs for a model trained on the clean sources alone; triggered and trigger-free behavior of the base model before fine-tuning; resemblance metrics for a diffusion model fine-tuned without the protected collection. Such an audit estimates δR\delta_R for the evaluation protocol at hand; it is evidence, not a proof. Appendix G already covered reference construction and imperfect references; we have added this audit protocol to it and state in Section 2.2 that DiSI certifies relative non-influence, not absolute safety.

AuthorsOpenReview ↗

W2/Q2: Distributional Assumptions Along the Trajectory

What the theory needs. The benign gradient distributions may change arbitrarily as the model evolves, and they need not be known. Theorems 3.2 and 3.3 are applied conditionally: at each step, given a history shared by the two runs, the next benign votes must be independent across sources, and their (state-dependent) bin probabilities determine a local bound ∆ that may differ across steps t and t,j coordinates j. Proposition 3.4 sums these. No stationarity is assumed, and the heterogeneous-source extension allows different sources to have different vote distributions.

Sensitivity. What matters is where the benign vote gap sits relative to the vulnerable band [τ − c, τ + c]. A drift that moves typical gaps toward the band raises ∆ even if the same (q, τ ) was t,j safe earlier. Dependence between benign sources is a real limitation: a shared fluctuation moves many votes together and weakens concentration, and our bounds do not cover it. Theorem 3.5 partly addresses both issues, since it certifies local risk from fresh histograms at the current model state without knowledge of the distribution, and can be re-run as the state changes. How often the conditions hold in practice. We measured this directly. Per-coordinate agreement between the contaminated and reference runs, averaged over training, is 98.3% at n = 10 and 99.99998% at n = 100 (Appendix J.1.3). Across q ∈ {0.001, 0.002, 0.005}, agreement stays above 98.29%, with clean accuracy 75.43–81.69% and ASR 4.43–5.73% on LF. The top-two gap quantiles are stable across all 21 parameter layers of ResNet-20 at fixed q and shift smoothly with q, so the gap structure is not a property of a few selected coordinates (Tables 10 and 11, Appendix J.1.4). These are measurements on the evaluated runs, not a proof that the conditional bounds hold along every trajectory; the reported experiments use fixed (q, τ ) rather than per-step calibration, as Section 3.4 and Appendix I state.

AuthorsOpenReview ↗

W3/Q3: Beyond Exact Agreement at Every Coordinate and Step

Trust transfer needs only a bound on the total variation between the final output laws; exact agreement at every (t, j) is one sufficient route to it, and a conservative one. Two remarks.

First, the union bound is less costly than dT ∆ suggests. Because the local rate decays exponentially in the number of benign votes n0n_0, a global failure probability ρ\rho needs n0≳1Ilog⁡dTρn_0\gtrsim\frac{1}{I}\log\frac{dT}{\rho} (Section 3.3): logarithmic in model size and training length. The bound is loose at small n, not in its scaling.

Second, there are two concrete ways to tighten it, outlined in Section 5 and Appendix H. (i) Whole-update events. The same malicious sources act on all coordinates of a step. Bounding the event that one admissible set of malicious rows changes any coordinate of the source-gradient matrix would avoid paying the factor d separately. (ii) Last-iterate coupling. A mismatch may be small, transient, or later cancelled; an analysis that lets trajectories diverge and coalesce would bound final-output disagreement directly rather than the probability of any intermediate mismatch.

One caveat explains why we do not simply relax exact agreement to closeness in parameter space. A bound on ∣∣wX−wR∣∣||w_X-w_R|| does not transfer an arbitrary trust event, because the event may have no margin: a backdoor can be encoded by a small, structured parameter change. For a specific event with a known margin, a distance bound would suffice, but that gives up the black-box property that lets one argument cover all four applications.

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

The paper's setting is the following: X is a dataset partitioned into subsets R and A where we want a model trained on X to be as if it was trained on R (up to some slack). The order of quantifiers seems to be a universal quantifier over all measurable A and measure observables on the output model subject to what is effectively a limit on the size of A.

A gradient-based technique that achieves this is a modification of SGD so that we quantize/round the gradients to a discrete space, and then effectively pick a popular rounded gradient, say one that has significantly more votes than the next most popular rounded gradient value. This is intuitively more robust to a small number of adversarial examples.

Critical strengths
  • I think the threshold maximal-gap cut is an interesting proposal but I'm failing to see intuitively why this algorithm is more useful than just threshold majority vote.
Critical weaknesses
  • I find that the writing quality is low. -- "Consistency-robust gradient operators" in the abstract means nothing to most readers. -- You should specify the what "attack success means". Everything in the abstract is rather vague. -- Clopper-Pearson is introduced in Theorem 3.5 with no preliminary discussion nor motivation. -- The statement of Theorem 3.5 should be heavily edited, it's currently full of terminology, e.g. calibration draw, calibration votes, local inconsistency rate. -- If A can arbitrarily choosen the remaining samples, why isn't the ability to craft a contamination specification of T_i vacuously true? -- Definition 2.2 is not well written, i.e. "suppose that for each requirement Ti\mathcal{T}_i we can specify a (ηi,Di)(\eta_i, \mathcal{D}_i)-Contamination Model..."

  • The name distribution-specific indistinguishability is not good because indistinguishability in the history of computer science of course refers to two distributions. I recommend a name that has something to do with the contamination model.

  • Lemma 2.3 is completely trivial. Please state it as a preliminary or as a known fact about TV distance. The interesting observation is that about the robust histogram feature and quantization.

  • The variant on the SGD seems to be inspired by or related in part to that in https://arxiv.org/pdf/1810.05291. Can you better motivate the need for the threshold gap?

  • Why did you not empirically test a non-vacuous (i.e. RHS is not \geq 1) setting of Proposition 3.4?

Questions for authors

See weaknesses.

7 comments
AuthorsOpenReview ↗

Summary of Revisions

We sincerely thank Reviewer 8kRN for the careful reading and the candid feedback on presentation. We are glad that the reviewer has no concern about soundness; we agree that the exposition made a simple argument harder to follow than it should be. The revised PDF (changes highlighted) makes the following edits, each explained below:

  • The abstract describes the operators by what they do, and ASR is defined at first use;

  • Definition 2.2 is restated with the order of quantifiers explicit;

  • Lemma 2.3 is moved to the preliminaries as a known fact about total variation;

  • Theorem 3.5 is preceded by a motivation paragraph and a worked example, and its statement is shortened;

  • Section 3.1 names majority-vote signSGD as the τ = 0, two-level case of TMV and adds a worked example of when TMGC is preferable.

AuthorsOpenReview ↗

W1: Abstract, Definition 2.2, and Theorem 3.5

Abstract and metrics. The revised abstract replaces “consistency-robust gradient operators” with a description: DiSI rounds each source’s gradient to a grid and updates a coordinate only when the source votes identify a clear winner (or a clear leading group); adding contaminated sources then changes the update only with probability exponentially small in the number of sources. Attack success rate (ASR) is now defined where it first appears: for image backdoors, the fraction of triggered test inputs from non-target classes that are classified as the attacker’s target class; for text backdoors, the fraction of responses to triggered prompts that exhibit the attacker’s target behavior.

Definition 2.2: order of quantifiers, and why it is not vacuous. The order is: (1) the learner fixes the algorithm; (2) the reference sources RiR_i are drawn independently from DiD_i; (3) the adversary, after seeing RiR_i, chooses the contaminated sources AiA_i within the budget η<1/2\eta < 1/2; (4) the probability in the guarantee is over the draw of RiR_i only, and the bound must hold for every adversary strategy in step (3).

The reviewer is right that one can always write down a contamination model, precisely because A is unconstrained. Doing so is a hypothesis, not a conclusion, and it has content in two places. First, it asserts that the non-designated sources really are independent draws from DiD_i and form a strict majority; this is an assumption about the data that can fail. Second, the transferred guarantee is only useful if training on RiR_i alone satisfies TiT_i with high probability. If either fails, DiSI’s bound is either inapplicable or transfers nothing of value. We have rewritten Definition 2.2 so that it no longer reads as “we can specify a model” but states these two conditions directly.

Theorem 3.5 and Clopper–Pearson. Theorems 3.2 and 3.3 bound the probability that contami-nation changes an update, but the bounds depend on the benign bin probabilities, which are unknown in practice. Theorem 3.5 removes this dependence: it certifies a choice of quantization scale q and threshold τ from data alone.

The idea is a simple audit. Call a benign vote histogram vulnerable if adding at most c votes could change the operator’s output. For example, with c = 1 and τ = 2, a benign histogram whose top two bins have 5 and 3 votes is vulnerable: its gap of 2 lies in [τ − c, τ + c] = [1, 3], so one vote can move TMV between “update” and “abstain”. Using K fresh minibatches per source, disjoint from the update minibatch, we form K histograms and count how many are vulnerable. The calibration histograms may themselves contain up to c malicious votes, so we label them with the widened band [τ −2c, τ +2c]; this can only over-count, whatever the malicious votes are. Because a count of zero does not mean the true vulnerability probability is zero, we convert the count into a one-sided upper confidence bound; Clopper–Pearson is the standard exact bound for a binomial proportion. Applying it at level α/J makes the bounds hold simultaneously over all J candidate (q, τ ) pairs, so the choice may be made after looking at the data. Concretely, if no vulnerable histogram is observed, K ≥ log(α/J)/ log(1 − ρ) histograms certify local risk at most ρ; for α = 0.05, J = 12, ρ = 1% this is K = 546.

This paragraph now precedes Theorem 3.5, and the theorem statement uses only the terms defined in it. The guarantee is local to one model state and coordinate. Using it throughout training addi-tionally requires that the two coupled runs select the same parameters (Theorem I.1), and Appendix I is explicit that the resulting end-to-end certificate is too data-hungry to be practical; the reported experiments use parameters fixed in advance (see W5).

AuthorsOpenReview ↗

W2: The Name & W3: Lemma 2.3

W2: The Name

We agree that indistinguishability is a relation between two distributions, and DiSI is one: the two distributions are the output laws of the same algorithm on R and on R∪A, compared in total variation. The revised Section 2 states this in its first sentence. “Distribution-specific” qualifies the conditions under which that closeness holds, in the same sense as “distribution-specific” learning guarantees: unlike differential privacy, which holds for every input, the bound holds for benign data drawn from D. The name also parallels the prior noise-based Data-Specific Indistinguishability (DaSI), which DiSI replaces. We take the reviewer’s point that the name alone does not signal the contamination model, and the revised abstract and introduction now introduce DiSI as “indistinguishability under an (η, D)-contamination model” at first mention.

W3: Lemma 2.3

We agree that the inequality is the standard coupling bound for total variation, and the revised PDF states it as a known fact in the preliminaries, with attribution. We also agree on where the technical work lies: in the quantization and robust histogram operators of Section 3.

We would like to explain why we nevertheless place it at the center of the framework (General Response, point 1). The fact is elementary; the decision it encodes is not. Because the trust set is a black box, with no metric or margin, an approximate-robustness guarantee on the update does not imply anything about the trained model’s behavior, and Table 8 shows this is not a technicality. The coupling bound identifies the one requirement that does transfer every event: exact agreement with the reference run outside an event of small probability. Everything in Section 3 follows from taking that requirement literally. The operators are designed to be consistent between R and R ∪ A rather than accurate, they must be so for an unknown D and an adversary who chooses A after seeing R, and they may not use noise. We have rewritten the paragraph after the statement to say this directly, so that the lemma reads as the bridge to Section 3 and not as a result in its own right.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response (all reviewers)

We thank all reviewers. Two questions recur across the reviews: what is technically new relative to robust aggregation and certified defenses, and what exactly is guaranteed. We answer them once here and refer back.

1. The target is consistency, not estimation accuracy. The trust set T\mathcal{T} (“no backdoor”, “does not reproduce xx”, “does not infringe”) is a black box. We are given no metric, margin, or Lipschitz property that relates a model's parameters to membership in T\mathcal{T}, and the benign distribution D\mathcal{D} is unknown. Under these constraints a robust-estimation guarantee, ∥g^−gR∥≤ε\lVert\hat{g} - g_R\rVert \leq \varepsilon, transfers nothing: a backdoor can be encoded by a small update that sits inside the benign range, and coordinate-wise median and trimmed mean indeed leave ASR above 99% in our setting (Table 8). The one property that transfers every event is closeness of the output laws in total variation. Lemma 2.3 is the elementary reason: if the contaminated and reference runs return the same output except with probability Δ\Delta, the probability of any event moves by at most Δ\Delta. The inequality is standard, and we now present it as such. Its consequence for design is what we want to make clearer: the problem changes from “estimate the benign gradient accurately” to “return exactly what the benign data alone would have returned, with high probability, for an unknown D\mathcal{D}, a worst-case AA chosen after seeing RR, and no added noise”.

2. The threshold decides when a vote may be used at all. We do not use majority vote as an estimator and then ask when it is reliable. The requirement is that the operator behaves identically with and without the adversarial sources, and the threshold is how that is enforced: the majority value (or, for TMGC, the leading cluster) is returned only when the vote is decisive enough that cc additional votes cannot change it; otherwise the operator returns ⊥\bot and gives up the update. This reverses the logic of prior vote-based methods. They state a condition under which majority vote is safe, either assumed of the gradient distribution (majority-vote signSGD proves convergence under unimodal symmetric noise against blind adversaries) or checked after training, input by input (FLCert certifies a test label when the realized ensemble vote gap is large enough, and says nothing otherwise). We assume nothing about the distribution. There are two cases, “majority” and “⊥\bot”, and in both the behavior on RR and on R∪AR \cup A is the same; the threshold selects the case. The outputs can differ only when the benign gap falls in a band of width 2c2c around τ\tau (Eq. (3)), which is a deterministic statement that does not involve D\mathcal{D}. The distribution enters only through the probability of that band, which decays exponentially in the number of benign sources (Theorems 3.2 and 3.3) and can be upper-bounded from samples, so that τ\tau can be chosen from data without knowing D\mathcal{D} (Theorem 3.5).

3. What the experiments do and do not certify. The end-to-end bound (Proposition 3.4) needs a few hundred sources to be non-vacuous; the image experiments use ten, on purpose, to test the mechanism where voting is hardest. We therefore report formal bounds and empirical measurements separately throughout, including the measured agreement between contaminated and reference runs, which is the quantity the theory controls.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.