Randomized smoothing is the standard way to make an image classifier provably robust. It adds random Gaussian noise to the input many times, takes a majority vote, and certifies that no perturbation smaller than some radius can change the answer. The cost is clean accuracy. More noise gives a bigger certificate but blurs away the features the classifier needs. Methods from differential privacy for structured data show a better way to place noise. These methods add noise to a frequency or wavelet transform of the data rather than to raw values, and they split the noise budget unevenly across frequency bands. For face recognition, histograms, and time series, this keeps useful structure that uniform noise destroys. The obvious transfer, "do randomized smoothing in the frequency domain," hides a catch. Gaussian noise with a different variance per band of an orthonormal transform is just a rotated, anisotropic Gaussian in pixel space. For the usual certificate, a round ball of radius $r$ in pixel space, the radius is set by the smallest band variance. Extra noise in other bands buys nothing on that metric.
This note takes the catch as its starting point. The frequency view earns its keep only when the certified set is stated as an ellipsoid shaped band by band and matched to the frequency profile of the perturbations a deployed model actually faces. Brightness and contrast shifts are almost pure DC (the zero-frequency, block-average component). Fog sits in low frequencies. Adversarial textures sit high. We propose a smoothing mechanism with per-band noise budgets, borrowed from frequency-domain differential privacy, that is tuned on training data and then frozen. We pair it with a spectral account of where clean accuracy and per-class accuracy go under smoothing. We test whether this mechanism covers real corruptions with a certificate at a lower clean-accuracy cost than isotropic smoothing, Fourier augmentation, input-dependent anisotropic smoothing, or projection onto a principal-component (PCA) subspace.
Core Claim
Let $U$ be the orthonormal 8×8 block discrete cosine transform (DCT), the transform used in JPEG. Let $\sigma_k$ be a noise scale for each of its 64 frequency bands, shared across blocks. Define the noise covariance $\Sigma = U^\top \mathrm{diag}(\sigma_k^2)\, U$. Applying Cohen-style certification after whitening gives a guarantee that the smoothed prediction is constant on the set
$$ \mathcal{C}(x) = \{\delta : \|\mathrm{diag}(1/\sigma_k)\, U\delta\|_2 \le R(x)\}, \quad R(x) = \tfrac{1}{2}\left(\Phi^{-1}(p_A) - \Phi^{-1}(p_B)\right), $$
Here $p_A$ and $p_B$ are lower and upper bounds on the top two class probabilities under noise, and $\Phi^{-1}$ is the inverse standard normal CDF. The ordinary round-ball radius is $R(x)\min_k \sigma_k$, which we will always report. The claim has three parts. First, clean accuracy is governed mainly by the noise on the bands that carry each class's discriminative energy. Second, the corruptions that break existing certificates mostly occupy different bands, chiefly DC and low AC. Third, a frozen, learned allocation can therefore certify a large fraction of real corrupted inputs at fixed round-ball radius, with a clean-accuracy cost close to isotropic smoothing at $\min_k \sigma_k$.
What is new here is not anisotropic smoothing itself. It is a data-independent spectral basis chosen so that both the certificate's shape and the accuracy cost can be read off per band. The allocation is set once per dataset, so certification needs no per-input Hessians or noise-generator networks.
Where This Sits
Two papers motivate the work by locating the trade-off in frequency. Hidden Cost of Randomized Smoothing shows that isotropic smoothing shrinks decision regions and collapses classes: on CIFAR-10 at σ=1.0, "ship" keeps 68% accuracy while "cat" falls to 22%, and on ImageNet at σ=0.5 more than 75% of classes reach zero accuracy. A Spectral View of Randomized Smoothing Under Common Corruptions shows the matching failure on the robustness side: smoothed models have certified radii that drop by as much as 74% under low-frequency corruptions on ImageNet-C. Its fix, Fourier-domain augmentation (FourierMix) with consistency regularization, changes training while leaving the noise isotropic. We change the noise distribution itself, and therefore the shape of the certificate.
A second group already escapes isotropic noise in pixel space. Anisotropic Randomized Smoothing learns pixel-wise means and variances with a small CNN and notes that the radius is bounded by the minimum variance, the same fact our reduction rests on. RANCER rotates smoothing ellipsoids using per-input loss Hessians and reaches 81% certified accuracy at ℓ2 radius 0.25 on CIFAR-10, against 56% for isotropic smoothing, at about 5× the cost. Projected Randomized Smoothing smooths in a PCA subspace, which yields hypercylinder certificates with a reported ~2% clean-accuracy drop. These papers constrain the design. Input-dependent covariances are expensive and raise soundness questions, and a learned linear subspace is a strong competitor. Our basis is fixed and our allocation is input-independent, which makes the certificate sound by construction.
The method itself comes from frequency-domain differential privacy. Differential Privacy via Wavelet Transforms shows that calibrating noise to transform coefficients, rather than raw values, cuts error by orders of magnitude on structured queries. Privacy-Preserving Face Recognition with Learnable Privacy Budgets in Frequency Domain learns a per-band noise budget in block-DCT space. It finds that the DC component holds over 91% of visual energy yet is not needed for recognition, and it reaches 99.48% on LFW at ε=0.5 against 99.60% non-private. We reuse its learnable per-band budget and its DC observation. PixelDP supplies the bridge: noise added to inputs under a sensitivity bound certifies robustness, at a cost it reports as clean ImageNet accuracy falling from 77.5% to 68.3%. PixelDP spends its noise uniformly over pixels. Separately, Evaluating Adversarial Robustness in the Spatial Frequency Domain finds that feeding block-DCT coefficients to CNNs improves empirical PGD accuracy on CIFAR-10 (58.4% against 19.6%) but provides no certificate. DP-CERT combines training-data privacy with smoothing, entirely in pixel space. We leave training-data privacy out of scope, so that a single question can be answered cleanly.
Research Program
The first component is a spectral diagnosis of clean-accuracy loss. For a base classifier trained under isotropic noise, we measure two quantities per class and per band. One is the class's discriminative energy in each band, estimated from input-gradient energy projected onto DCT bands. The other is the signal-to-noise ratio in each band at noise level σ. Natural images have power falling steeply with frequency, so isotropic noise drowns high bands first. The hypothesis is that per-class smoothed accuracy is predicted by the share of a class's discriminative energy in bands whose signal-to-noise ratio is below one. If that predictor does not explain the Mohapatra-style class collapse, the spectral story is wrong, and the rest of the program loses its rationale.
The second component is the mechanism. We parameterize the 64 band scales $\sigma_k$ in the manner of Ji et al. and train them jointly with the base classifier under noise. The objective is a clean-accuracy loss plus a penalty that requires the whitened norm of a target threat set to stay below a chosen certified level $R^\ast$. The target threat set is estimated from held-out corruption families (brightness, contrast, fog, frost, noise) and from PGD perturbations, all projected onto bands. A floor $\sigma_{\min}$ fixes the round-ball radius we commit to. After training, the allocation is frozen and certification proceeds exactly as in Cohen et al., with $10^5$ samples. Because $\Sigma$ does not depend on the test input, no soundness correction is needed. We also test a Haar wavelet variant. Its localized bases may handle spatially concentrated corruptions differently than block DCT does.
The third component is evaluation that matches how the certificate is used. We introduce certified corruption coverage. For each corrupted test image $x_c$ with clean source $x$, we compute $\delta = x_c - x$ and count the image as covered if the smoothed prediction at $x$ is correct and $\delta \in \mathcal{C}(x)$. This metric asks whether the certificate actually contains the perturbation that occurred. A large average radius on an irrelevant ball does not satisfy it.
Baselines
The naive reference is standard isotropic Gaussian smoothing from Certified Adversarial Robustness via Randomized Smoothing, run at σ equal to our floor $\sigma_{\min}$, with the same architecture, epochs, and sample counts. That paper reports 49% certified top-1 at ℓ2 radius 0.5 on ImageNet. Our method beats this baseline if it matches its round-ball certified accuracy within one point while substantially raising certified corruption coverage. If coverage does not rise, the spectral allocation buys nothing.
The strongest competitor for corruption certification is FourierMix with hierarchical consistency regularization from the Spectral View paper. It reports mean average certified radius gains of 26.7% on CIFAR-10-C and 55.9% on ImageNet-C over the Gaussian baseline. We retrain it with our architecture and an equal tuning budget, and we compare at matched clean accuracy. Beating it means higher coverage on the low-frequency corruption families at equal clean accuracy. We also test the combination: FourierMix training under our allocated noise. That combination may be the best system overall.
For round-ball certification, the strongest competitor is RANCER, with 81% certified accuracy at radius 0.25 and an average certified radius of 0.53 on CIFAR-10, alongside ANCER. We run both with the authors' optimization settings on our base models. We do not expect to beat RANCER on ball radius, and we will say so if we do not. The comparison that matters is coverage per unit of certification time, since RANCER is reported at about 5× isotropic cost.
Projected randomized smoothing with PCA is run with the same number of retained dimensions as our retained DCT bands. This comparison tests directly whether the fixed basis matters.
Two ablations isolate the key ingredient. In the first, we keep our learned per-band variances but apply them in a random orthonormal basis, which tests whether frequency structure matters or anisotropy alone does the work. In the second, we keep the DCT basis but use a uniform allocation with only DC noise inflated. This tests whether the learned budget adds anything beyond the single DC observation borrowed from Ji et al.
Why not just…?
Why not just use PCA projection, since it already gives a ~2% clean drop? This is the most serious threat. For roughly stationary natural images, principal components resemble Fourier modes, so a PCA subspace and a low-pass DCT subspace may behave almost identically. The matched-dimension comparison settles it. If PCA matches our coverage and clean accuracy on CIFAR-10 and SVHN, the defensible residual claims are cost and ImageNet scale. The PRS authors note that their volume bound needs an ℓ∞ regression, whereas block DCT needs no fitting. If PCA also wins at ImageNet scale, we will report that the frequency basis adds nothing.
Why not just JPEG-compress or low-pass the input and then smooth isotropically? Smoothing a deterministic preprocessor composed with a classifier yields a valid certificate. This baseline is therefore legitimate, and we include it. It discards high bands, but it still certifies a round ball, so brightness and fog shifts, which are large in ℓ2 norm, remain uncovered. The coverage metric on low-frequency corruptions should separate the two. If it does not, the allocation is unnecessary.
Why not just tune σ or add consistency regularization in pixel space? The Spectral View paper reports that regularized smoothers such as SmoothAdv and MACER still lose up to 74% of their certified radius under low-frequency shifts. The Hidden Cost paper reports that noise-augmented training does not prevent class collapse. Tuning a single σ moves a model along the same trade-off curve and cannot change the shape of the certificate. Our isotropic baselines at several σ values trace that curve explicitly.
Why not just use input-dependent anisotropic smoothing like ARS? It can fit each image better. It also adds a noise-generator network, it adds certification overhead (about 0.34 s per sample for ARS), and a covariance that depends on the input complicates soundness. If ARS dominates on coverage at equal cost, the fixed-basis argument fails. Our comparison reports both quantities.
Proposed Experiments
The datasets are CIFAR-10, CIFAR-10-C, and the 192-band Fourier corruption suite from the Spectral View paper; ImageNet and ImageNet-C; and SVHN for comparison with PRS. The metrics are clean accuracy, per-class accuracy and the fraction of collapsed classes, round-ball certified accuracy and average certified radius, certified corruption coverage for each corruption family, and certification time.
The first decisive check is the diagnosis. Per-class smoothed accuracy should correlate with the predicted share of discriminative energy in drowned bands, and the correlation should hold out of sample, across σ values and between CIFAR-10 and ImageNet. The second decisive check is matched-radius coverage. At fixed $\sigma_{\min}$, our allocation should keep clean accuracy within about one point of isotropic smoothing, while raising coverage on brightness, contrast, and fog well above both isotropic smoothing and FourierMix. The third decisive check is the pair of ablations. The random-basis version should lose most of the coverage gain, and the DC-only version should recover part but not all of it.
If the diagnosis fails, or if the random-basis ablation matches the DCT version, the frequency framing is unnecessary, and we will report the result as a negative one about transferring frequency-domain privacy noise to certified robustness.
References
- Hidden Cost of Randomized Smoothing
- A Spectral View of Randomized Smoothing Under Common Corruptions: Benchmarking and Improving Certified Robustness
- Certified Adversarial Robustness via Anisotropic Randomized Smoothing
- RANCER: Non-Axis Aligned Anisotropic Certification with Randomized Smoothing
- Projected Randomized Smoothing for Certified Adversarial Robustness
- Differential privacy via wavelet transforms
- Privacy-Preserving Face Recognition with Learnable Privacy Budgets in Frequency Domain
- Certified Robustness to Adversarial Examples with Differential Privacy
- Evaluating Adversarial Robustness in the Spatial Frequency Domain
- Augment then Smooth: Reconciling Differential Privacy with Certified Robustness
- Certified Adversarial Robustness via Randomized Smoothing