PaperlayerView exact revision on arXiv

Source-linked AI summary

A Certified Robustness Framework for Backdoor Poisoning Attacks using $f$-Divergences

Evan Rose, Alina Oprea

arXiv:2610.34934v1cs.LGcs.CR

TL;DR

Existing randomized-smoothing defenses for poisoning attacks cover limited threat models and smoothing mechanisms. This paper develops a composable f-divergence framework for combining corruption constraints with subsampling and feature, label, and test-sample noise. It certifies general ℓ_p poisoning adversaries under bagging with Gaussian, Laplace, and Uniform noise.

  • Problem

    Certified randomized-smoothing defenses for poisoning attacks remain limited to particular threat models and smoothing mechanisms, despite adversaries corrupting training and test samples.

    Source: §1 · p. 1

  • Method

    The framework combines corruption constraints with subsampling and feature, label, and test-sample noise, then certifies the resulting mechanisms compositionally using f-divergence constraints.

    Source: §1 · pp. 1–2, §4.1 · p. 3

  • Results

    The framework certifies, for the first time, ℓ1, ℓ2, and ℓ∞ poisoning adversaries under bagging with Gaussian, Laplace, and Uniform noise.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The framework recovers several prior certification regimes as special cases and supports certification across combinations of threat models and smoothing strategies.

    Source: §1 · p. 2, §6 · p. 9

    The method trains thousands of base learners for sound prediction estimation and does not exploit dataset- or base-learner-specific properties.

    Source: §6 · p. 9

Abstract

from arXiv · show

Machine learning systems trained on untrusted data are vulnerable to data and backdoor poisoning attacks, in which an adversary corrupts training and test samples to manipulate predictions at inference time. Randomized smoothing yields provable defenses against such attacks, but existing applications to train-time robustness are limited to specific threat models and smoothing mechanisms. We propose a general framework that allows expressing complex adversary constraints on the number of corrupted training examples, feature and label perturbation magnitudes, and test-time corruptions. Our framework randomizes inputs by combining data subsampling with feature, label and test-sample noising. We develop a composable certification procedure based on $f$-divergences that handles arbitrary combinations of threat models and noising strategies, and recovers several prior certification regimes exactly as special cases. We demonstrate our framework experimentally by certifying, for the first time, robustness under general $\ell_p$-constrained poisoning adversaries under bagging with additive Laplace, Gaussian, and Uniform noises.

1 Introduction

Data and backdoor poisoning defenses based on randomized smoothing remain limited to simple strategies, despite the range of possible training- and inference-phase attacks. This work proposes a general framework that composes rich threat models and randomized smoothing mechanisms into sound certificates.

1 Introduction

  • Existing certified poisoning defenses remain limited to simple bagging or discrete label flipping, despite the availability of data subsampling, feature noising, and label flipping strategies.Analyzing guarantees becomes harder as noising procedures become more complex.Source: §1 · p. 1
  • Its certification perspective replaces admissible perturbations with a convex outer approximation defined by f-divergence constraints.The constraints depend on the smoothing mechanism and threat model and have composition properties.Source: §1 · p. 1
  • The framework represents complex feature, label, and test-instance corruptions and derives sound robustness certificates using f-divergences.It combines rich threat models, multi-step randomization, and convex relaxation.Source: §1 · pp. 1–2
  • The framework recovers tight certificates from several prior works as special cases and studies settings not considered in those works.Source: §1 · p. 2

2 Background and related work

Prior work on certifiable poisoning robustness includes randomized smoothing, learner-specific defenses, differential-privacy-based guarantees, and voting-based defenses. These lines of work use different learning assumptions and certification strategies.

Randomized smoothing

Learner-specific defenses

  • Learner-specific defenses derive certificates for particular models, including linear regression, decision trees, nearest neighbors, graph neural networks, SVMs, and gradient-based learners.The cited works include Rosenfeld et al. [2020], Drews et al. [2020], Jia et al. [2022], Sabanayagam et al. [2025], Gosch et al. [2026], and Sosnin et al. [2025].Source: §2 · p. 2

Differential privacy for robustness

  • Differential-privacy-based defenses derive robustness guarantees from the stability of differentially private learners, including instance-wise poisoning analyses.The cited works include Ma et al. [2019], Xie et al. [2023], Liu et al. [2023], and Saxena et al. [2026].Source: §2 · p. 2

Voting-based poisoning defenses

  • Voting-based poisoning defenses use ensembles trained on data partitions or randomized training samples and certify robustness through majority votes.The cited works cover deterministic partitions and randomized smoothing ensembles.Source: §2 · p. 2

3 Problem statement and preliminaries

The paper models learning and test-time prediction as one joint input and defines robustness over a set of jointly corrupted inputs. Its threat model separates corruption budgets across four axes, while its certificates characterize the full region of robust threat parameters.

3.1 Learning setup

  • The base predictor maps a joint input consisting of a training set and test example to a label distribution, with a hard predictor selecting the highest-probability label.The learning algorithm may be randomized, in which case the predictor averages over its internal randomness.Source: §3.1 · pp. 2–3

3.2 Threat model

  • The adversary jointly replaces training and test inputs, may alter training features and labels, and cannot insert or delete training examples.Source: §3.2 · p. 3
  • Four threat parameters separately bound the number of corrupted training examples, training-feature magnitude, training-label magnitude, and test-sample magnitude.The constraints use feature- and label-space distance functions.Source: §3.2 · p. 3
  • The four-axis threat model recovers prior threat models as special cases and includes previously unconsidered cases such as finite corruption budgets with ℓ_p feature constraints.Source: §3.2 · p. 3

3.3 Certified robustness

  • A predictor is ρ-robust when its output is unchanged for every input in the perturbation set defined by ρ.Source: §3.3 · p. 3
  • The robustness region records all threat-parameter combinations under which the predictor remains robust, capturing how changing one parameter can affect robustness to others.Existing defenses typically report a scalar radius for a single threat axis.Source: §3.3 · p. 3

4 Methodology

The methodology smooths a joint training-and-test input with subsampling and noise, then certifies robustness through composable f-divergence constraints. It handles the resulting mixture structure by grouping component bounds and computing divergences for paired noisy inputs.

4.1 Robust learning procedure

  • The randomized smoothing mechanism subsamples training examples, noises retained features and labels, and noises the test sample before the base predictor is evaluated.The smoothed predictor averages the base predictor's output distribution over randomized inputs.Source: §4.1 · pp. 3–4
  • The mechanism forms a mixture over retained subsamples, with product-measure components; bagging with replacement can yield n^k components.Bagging and Poisson subsampling, Gaussian, Laplace, Uniform, and discrete feature noise, and flipping or Markovian label noise are among the supported instantiations.Source: §4.1 · p. 4

4.2 Certifying predictions: overview

  • Prior hypothesis-testing certification is difficult to extend because the mechanism's combinatorial mixture complicates its likelihood ratio and mechanism changes require new derivations.The f-divergence dual formulation instead constructs certification conditions from per-component information and composes them with computational rules.Source: §4.2 · p. 4

4.3 Certification via convex optimization

  • Certification reduces to a convex program over probability bounds subject to f-divergence constraints, with the certificate holding when the program's optimum is non-negative.The constraints bound divergence from the smoothed prediction probabilities.Source: §4.3 · pp. 4–5

4.4 Computing divergence bounds

  • For subsampling mixtures, shared component weights and grouping components by corruption count reduce divergence computation to a tractable sum.The approach uses joint convexity and does not depend on the specific feature- or label-noise geometry.Source: §4.4 · p. 5

4.5 Bounding component divergences

  • Component divergence bounds reduce to optimizing over feasible noisy input pairs; symmetric noise can make each f-divergence depend only on a low-dimensional adjacency parameter.Gaussian noise depends on normalized ℓ2 separation; Rényi divergences tensorize, and Laplace hockey-stick profiles require numerical integration.Source: §4.5 · pp. 5–6
  • Worst-case pairs exist for Gaussian and Uniform noise under all ℓ_p norms and for Laplace noise under ℓ1 and ℓ∞, while Laplace under ℓ2 needs special treatment.For Uniform noise, optimizing the adjacency parameter uses a loose relaxation.Source: §4.5 · p. 6
  • The worked bagging example groups components by the number of corrupted retained samples, whose count follows a binomial distribution under the stated sampling setup.For ℓ2 Gaussian noise, the component adjacency is determined by the corrupted-sample count and maximal corruption magnitude.Source: §4.5 · p. 6

5 Evaluation

The evaluation covers MNIST, CIFAR10, and class-subsampled variants, testing ℓp feature attacks as well as joint feature-label and backdoor attacks. Results show tradeoffs across noise choices, poisoning budgets, and prior methods.

5.1 ℓp feature adversaries

  • Pure bagging has higher non-robust certified accuracy; Uniform noise is competitive for ℓ1 at moderate poisoning, while Laplace marginally beats Gaussian for ℓ1 when R ≥ 1.5%.For ℓ2 and ℓ∞, Gaussian noise yields the largest certified accuracies; Uniform is competitive for poisoning amounts below 1.2%.Source: §5.1 · p. 7, Figure 1 · p. 7
  • On MNIST, εf = 1 gives a substantially larger certified radius, but at εf = 2 the certificate nearly matches the εf = ∞ bagging certificate.The reported dependence covers MNIST, MNIST-17, CIFAR10, and CIFAR10-02 under Gaussian noise.Source: §5.1 · p. 7

5.2 Label flipping and backdoor adversaries

  • On MNIST-17, the method retains over 45% certified accuracy at R = 2%, while RAB reaches trivial accuracy at R = 0.5% under backdoor attacks.The authors attribute the advantage to bagging, which retains only O(k · mp/n) poisoned samples with high probability, unlike RAB, which retains all poisons.Source: Table 3 · p. 8, §5.2 · p. 8
  • As Gaussian noise must grow with εf, large budgets can make inputs unclassifiable and reduce base-learner accuracy, favoring pure bagging without feature noise.Aggressive noise can erase corruptions and increase certified radii, but it also lowers vote confidence by degrading the base learner.Source: §5.2 · pp. 8–9
  • Label-noising improvements over plain bagging occur only on the binary datasets MNIST-17 and CIFAR10-02; MNIST-17 reaches a certified radius of 3.5% of the training set.The authors note that label noise is especially destructive because labels provide the only supervision signal.Source: Table 2 · p. 8, §5.2 · p. 9

5.3 Comparison with prior works

  • The framework recovers Zhang et al.’s exact certificates under their considered threat models and smoothing strategies, and Jia et al.’s exact certificates for replacement adversaries.The evaluation also compares robustness tradeoffs for joint feature-label attacks and clean-label backdoor attacks across poisoned fractions.Source: §5.2 · p. 8, §5.3 · p. 9

6 Conclusion

The conclusion presents the composable $f$-divergence framework for certifying robustness to poisoning attacks, while identifying computational and modeling limitations and directions for stronger certificates. It also contrasts tight certificates based on ensemble vote-probability estimates with an efficient but loose closed form for linear-regression learners, which under its threat model reduces to a previously analyzed standard Gaussian certificate.

6 Conclusion

  • The framework decomposes poisoning constraints across corruption axes and uses composite noise and f-divergence convex programs to certify ℓ1, ℓ2, and ℓ∞ adversaries under several noise distributions.The authors report first-time certification for these adversaries with Gaussian, Laplace, Uniform, and discrete noise.Source: §6 · p. 9
  • The method trains thousands of base learners; future work could seek closed-form solutions, exploit dataset or learner properties, characterize optimal noising, or use data-smoothness for tighter certificates.The authors note that their parallelized implementation mitigates the training cost, and that the tradeoff between subsampling and data noising remains unclear.Source: §6 · p. 9

A.1 Tightness of Randomized Smoothing

  • Cohen et al. [2019] derived provably optimal certificates via hypothesis testing, while earlier differential-privacy and Rényi-based approaches yielded slack bounds; Salman et al. [2019] obtained the same tight certificate via Weierstrass transforms.Dvijotham et al. [2020] connect convex optimization with hockey-stick divergences to recover optimal certificates in the general case.Source: §A.1 · pp. 13–14

A.2 f-Divergences

  • Dvijotham et al. [2020] give convex-program characterizations for specification robustness and broader robustness settings, with hockey-stick divergences sufficient for tight certificates in the latter.These are the three results the paper identifies as important to its work.Source: §A.2 · p. 14

B Background on f-divergences

  • Hockey-stick divergences are preferred when available; otherwise, the appendix recommends computing Rényi divergences, whose tensorization and continuity properties aid computation.Several other divergences can be expressed through hockey-stick or Rényi divergences of suitable orders.Source: B Background on f-divergences · p. 16

B.1 Additional lemmata

  • When two measures share a common component, the total variation distance determines their entire hockey-stick envelope and, in this setting, any f-divergence.Consequently, the information-limited certificate depends only on the total variation distance.Source: §B.1 · p. 18

C.1 Threat model and mechanism comparison

  • The framework recovers BagFlip’s certificate under the described label-flipping setup and remains able to compute tight certificates when feature and label spaces or noises differ.The broader case is more general than Zhang et al. [2022].Source: §C.1 · p. 19
  • Rosenfeld et al. [2020] provide an efficient, loose closed form for linear-regression learners, while tight certificates require estimating vote probabilities with an ensemble.Source: §C.1 · p. 19
  • Under Rosenfeld et al. [2020]’s threat model, the certificate reduces to Cohen et al. [2019]’s standard Gaussian certificate, already understood by Dvijotham et al. [2020].Source: §C.1 · p. 19

C.2 Comparison with Saxena et al. [2026]

The comparison frames Saxena et al.’s randomized DPA as a special case of the paper’s data-noising analysis, while distinguishing their assumptions and threat-model scope. The framework’s analysis also supports reuse across certifications and bounds for add-or-remove training-sample adversaries.

C.2 Comparison with Saxena et al. [2026]

  • The framework places assumptions on and noises input data, handling subsampling, noise products, and individual noise factors; Saxena et al. analyze composition of DP mechanisms.Its per-example replacement budgets cover arbitrary ℓ_p constraints and label corruptions, whereas Saxena et al. focus primarily on symmetric set-distance adversaries, with a special case for ℓ_2 features and Gaussian noise.Source: §C.2 · pp. 19–20
  • Randomized DPA assigns records to N buckets, trains one model per bucket, then samples a bucket; in this formulation, noise is applied only to the test sample.The training buckets are uniform and pairwise disjoint, with no feature or label noise.Source: §C.2 · p. 20
  • The DPA bound is attained when exactly r buckets change, the test perturbation reaches its bound, and the corrupted sub-datasets are pairwise distinct.The proof combines uncorrupted-bucket divergence with the hockey-stick divergence min(1, β) for a corrupted bucket.Source: §C.2 · p. 20
  • Training can be reused across arbitrarily many certifications because N is small and training data receive no feature or label noise; inference on a sampled model is still required.With hash-based bucket assignment, the method also bounds symmetric set-difference adversaries that add or remove samples, with r ≤ min(2mp, N) for mp replaced training examples.Source: §C.2 · p. 20

D.1 Equivalence of robustness conditions

The appendix equates robustness of the smoothed classifier across a threat region with robust certification of its pairwise class-margin specifications. Strict certified margins additionally ensure a unique predicted class throughout that region.

D.1 Equivalence of robustness conditions

  • Robustness throughout Bρ(w) is equivalent to robust certification of every pairwise specification ψc,c′ at M(w) over Dw,ρ.Each specification is the difference between the base learner’s scores for classes c and c′.Source: §D.1 · p. 20
  • The equivalence follows because each specification’s expectation under M(w′) equals the corresponding smoothed-score difference.A violating class margin makes that expectation negative, so the specification fails robust certification.Source: §D.1 · pp. 20–21
  • Strict certified margins make c the unique maximizer throughout the threat region, recovering ρ-robustness.The strict condition requires GM(w′)c > GM(w′)c′ for every competing class and every w′ in Bρ(w).Source: §D.1 · pp. 20–21

D.2 Proof of Theorem 4.1

Appendix D.2 proves the Rényi analogue of the mixture bound in Theorem 4.1 by treating orders below and above one separately. It derives the reorganized bound through the corresponding f-divergence representations.

D.2 Proof of Theorem 4.1

  • Theorem 4.1’s proof applies joint convexity of f-divergence and rearranges terms according to the partition.This is the stated proof step underlying the mixture bound.Source: §D.2 · p. 21
  • For all α in (0, 1) ∪ (1, ∞), Corollary D.1 gives a Rényi mixture bound and a reorganized bound under Theorem 4.1’s setting.The proof obtains the reorganized bound from the first using monotonicity of logarithm and exponential.Source: §D.2 · p. 21
  • For 0 < α < 1, the proof relates Rényi divergence to the f-divergence generated by f(u) = 1 − u^α, then applies joint convexity and monotonicity.It uses D_f(μ_i∥ν_i) = 1 − exp((α − 1)D_R,α(μ_i∥ν_i)) in the derivation.Source: §D.2 · p. 21
  • For α > 1, the proof uses the generator f(u) = u^α − 1 and applies joint convexity with the monotonicity of log(1 + ·).It uses D_f(μ_i∥ν_i) = exp((α − 1)D_R,α(μ_i∥ν_i)) − 1.Source: §D.2 · pp. 21–22

E Tightness of certificates

The section examines when the framework’s certificates are tight and identifies two sources of slack. Its joint-convexity slack is the divergence gap between labeled and unlabeled mixtures, which vanishes when the component label is recoverable from the observation.

E Tightness of certificates

  • The section defines tightness as the existence of a worst-case input and compatible base algorithm for every radius outside the certified region.In the information-limited setting, the base algorithm is constrained by the aggregated vote probabilities.Source: E Tightness of certificates · p. 22
  • The framework can introduce slack by replacing the induced constraint set with a convex outer approximation and replacing exact divergence bounds.A further potential source, reorganization in Theorem 4.1, is exact in the cases considered.Source: E Tightness of certificates · p. 22
  • If the exact Hockey-stick profile is available at all orders β ≥ 0, the resulting certificate is tight given only vote statistics θ_a and θ_b.Without further assumptions on the base learner, no procedure observing only those statistics can certify a larger region.Source: E Tightness of certificates · p. 22

E.1 Joint-convexity slack from label recovery

  • Jia et al. [2021] and Zhang et al. [2022] satisfy the label-recovery condition, so the framework recovers their certificates exactly.The appendix analyzes the slack from Theorem 4.1 to establish this exactness.Source: E Tightness of certificates · p. 22
  • The joint-convexity slack equals the f-divergence difference between labeled and unlabeled mixtures, and it vanishes when component supports are pairwise disjoint.Disjoint supports make the component label recoverable from the observation.Source: §E.1 · p. 23

E.2 Tightness of pure subsampling

For pure subsampling without noise, the mixture bound is exact under record-distinctness. The resulting certificate is governed by the probability that a subsample retains a corrupted record.

E.2 Tightness of pure subsampling

  • Record-distinctness requires clean records, corrupted records, and records within each group to be distinct.The condition is used to make the component supports pairwise disjoint and establish exactness.Source: §E.2 · pp. 23–24
  • For record-distinct corruptions under pure subsampling, Theorem 4.1 is exact and yields the Hockey-stick profile based on the probability of retaining a corrupted record.The theorem defines m(w, w′) as that retention probability and takes its supremum over feasible corruptions.Source: §E.2 · pp. 23–24
  • The recovered certificate uses the worst-case corrupted-record retention probability to certify robustness for the subsampled model.The section identifies this result as recovery of the bagging certificate.Source: §E.2 · p. 24
  • Without record-distinctness, the proof cannot directly use Lemma B.7 to obtain the worst-case τ_β, although the resulting bound remains valid.The condition can fail through repeated records in the sample or inability to choose a suitable corruption.Source: §E.2 · p. 24

E.3 Recovering BagFlip’s certificate

The framework recovers BagFlip’s certificate exactly in the analytical sense because its analysis uses the label-released mixture. That exact match does not guarantee tightness for BagFlip learners that do not use the mixture-component label.

E.3 Recovering BagFlip’s certificate

  • With feature or label noise, mixture components are no longer identifiable, so the joint-convexity slack can be nonzero in principle.For the setting BagFlip actually analyzes, releasing the label makes the exactness condition applicable.Source: §E.3 · p. 24
  • The framework’s certificate matches Zhang et al. [2022] exactly for the label-released mixture analyzed by BagFlip.Theorem E.2 applies the mixture bound after partitioning by the number of retained corrupted examples.Source: §E.3 · p. 24
  • BagFlip’s certificate may not be tight for base learners that do not use the mixture-component label, even though the analytical certificates match.The passage identifies this as a possible gap between the certificate and the robustness of those learners.Source: §E.3 · p. 24

F.1 Training

This section describes the training and smoothing configurations, confidence-bound and certification procedures, and divergence tools used to analyze the framework. It derives bounds for adjacent flipping and Gaussian–flipping measures, characterizes worst-case Uniform-noise adjacency under ℓ_p constraints, and notes applications and a limitation of the analyzed methods.

F.1 Training

  • Experiments cover MNIST, CIFAR10, and derived MNIST-17/CIFAR10-02 binary tasks, using a two-convolution network on MNIST and group-normalized, weight-standardized ResNet-20 on CIFAR10.Training uses Adam with learning rate 10^-3 for 200 epochs and batch size 16, with weight decay 2·10^-3 on MNIST and 10^-4 on CIFAR10; full-training-set RAB models instead use 20 epochs and batch size 128 on MNIST and MNIST-17, or 10 epochs and batch size 64 on CIFAR10 and CIFAR10-02. Augmentation uses translations up to 2 pixels and 8×8 cutout on MNIST, and translations up to 4 pixels and horizontal flips on CIFAR10; Gaussian batch noise with standard deviation drawn uniformly from [0,1] is disabled for plain bagging on both CIFAR10 and CIFAR10-02.Source: §F.1 · p. 25

F.2 Mechanisms and configurations

  • The experiments use bagging with replacement, primarily Gaussian feature noise, and label flipping in joint feature-and-label trials; backdoor trials omit label noise.Ensembles contain 10,000 models on MNIST and MNIST-17 and 1,000 on CIFAR10 and CIFAR10-02; feature-noise scales and bag sizes vary by dataset and threat model.Source: §F.2 · p. 25

F.3 Confidence intervals

  • Certification estimates smoothed-classifier vote probabilities with Clopper–Pearson bounds and applies SimuEM with Bonferroni correction across classes and test points.Each bound has failure probability α/(eC), making the full test-set failure probability at most α by the union bound.Source: §F.3 · pp. 25–26

F.4 Algorithms

  • The certification algorithms follow prior procedures and use hockey-stick constraints of all orders.The cited algorithms build and certify ensembles, then output a predicted label and certified corruption count or abstain when none is certified.Source: §F.4 · p. 26, §F.3 · p. 26, G Bounding divergences · p. 27

G Bounding divergences

  • The divergence analysis reduces mixture bounds to worst-case adjacent perturbations and then computes the divergences for the resulting measure pairs.The same worst-case pair is desired across all f-divergences and should compose across the factors of the noising mechanism.Source: G Bounding divergences · pp. 26–27

G.2 Bounds between adjacent smoothing measures

  • The appendix derives divergence bounds for Uniform, Gaussian, Laplace, and discrete flipping measures, and supports product combinations through computation of likelihood-ratio distributions.The general procedure covers Uniform, Gaussian, and Flipping measures and product combinations under ℓ_p and ℓ_0 feature-label constraints, but Laplace feature noise with general ℓ_p norms where p ≠ 1 requires separate treatment.Source: G Bounding divergences · p. 27, §G.2 · p. 28

G.1 Finding worst-case adjacent distributions

  • An adjacency parameter summarizes how divergences between noised inputs depend on their perturbation, while worst-case pairs are ordered by all-generator divergence and compose across product measures.For Gaussian measures, Euclidean distance is an adjacency parameter; hockey-stick divergences characterize the ordering of pairs.Source: §G.1 · pp. 27–28

G.2 Bounds between adjacent smoothing measures

  • The flipping-measure bounds exploit an O(s)-region likelihood-ratio partition to compute hockey-stick divergence, while Rényi and KL divergences tensorize across changed coordinates.The partition has one region for each possible signed distance d from −s to s.Source: §G.2 · pp. 31–33
  • Gaussian–flipping measures support joint feature–label smoothing for dirty-label poisoning and smoothing mixed continuous and discrete feature spaces.For adjacent measures, Rényi and KL divergences combine the Gaussian and flipping values by tensorization; the hockey-stick divergence uses the flipping likelihood-ratio distribution.Source: §G.2 · p. 35

G.3 Worst-case Uniform parameters

  • For Uniform noise, worst-case adjacency under an ℓ_p constraint reduces to maximizing the parameter θ; when η ≥ 1, the adversary can make the supports disjoint and θ = 1.Here η is the perturbation budget scaled by twice the Uniform radius.Source: §G.3 · p. 36
  • For Uniform-noise optimization, the ℓ_1 case concentrates the budget in one coordinate, the ℓ_∞ case maximizes each coordinate, and intermediate ℓ_p cases use dimension-dependent bounds.The intermediate-case bounds follow from Hölder’s inequality.Source: §G.3 · p. 36

G.4 Worst-case Laplace parameters

The section characterizes worst-case Laplace parameters under feature-norm constraints: ℓ1 and ℓ∞ cases are exact for all f-divergences, while intermediate ℓp cases use a dominating parameter. Its argument uses coordinate monotonicity and Schur convexity to compare divergence profiles.

G.4 Worst-case Laplace parameters

  • For ℓ1 and ℓ∞ constraints, worst-case Laplace divergences are exact for all f-divergences: perturbations concentrate in one coordinate for ℓ1 and reach η in every coordinate for ℓ∞.The maximizing parameters are ηe1 and η1, respectively.Source: §G.4 · pp. 36, 38
  • Coordinate-wise increases in the Laplace shift cannot decrease the divergence, providing the comparison used to bound admissible parameters.The monotonicity applies to each coordinate and every β > 0.Source: §G.4 · p. 37
  • Under an ℓ1 budget, splitting perturbation across two coordinates gives no larger Hockey-stick divergence than concentrating it in one coordinate; equality holds outside β ∈ (e^−η, e^η).The comparison is established across the four orderings of the two shifts and ℓ.Source: §G.4 · pp. 37–38
  • Schur convexity of the divergence in the Laplace parameter lets majorization order perturbation vectors and identify a dominating vector.If t ≺ t′, then (µt, ν) ≺ (µt′, ν).Source: §G.4 · p. 38
  • For 1 < p < ∞, no single parameter maximizes every Hockey-stick divergence; a dominating parameter uses K = ⌈m^(1−1/p)⌉ coordinates, each set to η.For p = 2, K = ⌈√m⌉.Source: §G.4 · p. 39

Related papers

Loading 2610.34934v1…