greatitself.
Continue
research28 min studyLesson 938 in Engineering

Certify only the classifier and noise law you proved

Connect Gaussian smoothing, conservative probability bounds, abstention, and finite-sample confidence to a scoped Euclidean certificate.

Before you begin
On this page

The question for today

What you’ll understand

  • Define the ideal Gaussian-smoothed classifier separately from its sampled implementation.
  • Compute a valid conservative radius from a one-sided probability lower bound.
  • State multiclass abstention, correctness, and simultaneous-confidence limitations.

Randomized smoothing offers a different kind of evidence from unsuccessful attacks. It defines a classifier by the most probable class under Gaussian input noise and proves stability inside a Euclidean ball when class probabilities are sufficiently separated. In practice those probabilities are estimated from finite samples, so the certificate also needs a valid confidence procedure. An observed vote fraction is not automatically a lower probability bound. Preserve the base model, preprocessing, noise coordinates, sampling protocol, and abstention rule so the implemented claim matches the theorem rather than a superficially similar noisy predictor.

Define the ideal smoothed decision

Take a fixed measurable base classifier defined on all real input vectors. Its fixed preprocessing, including any clipping, can be part of that base function. Add isotropic Gaussian noise in the stated coordinates before evaluating it. The ideal smoothed classifier returns the class with the greatest resulting probability, using a declared tie rule. It is a deterministic function of the input even though Monte Carlo sampling is used to approximate its decision in software.

Changing the noise law changes the theorem. Truncating or resampling the Gaussian before it reaches the base classifier is not the same as allowing a fixed clipping operation inside the base function after Gaussian addition. Likewise, isotropic noise after a nonuniform normalization corresponds to a different geometry in raw coordinates. Keep sigma’s units and injection location explicit. The standard certificate discussed here concerns the ideal smoothed classifier and an L2 perturbation in those same input coordinates.

g(x)=argmaxc∈YPr⁡{f(x+ξ)=c},ξ∼N(0,σ2Id)g(x)=\mathop{\rm argmax}_{c\in\mathcal Y}\Pr\{f(x+\xi)=c\},\qquad \xi\sim\mathcal N(0,\sigma^2I_d)
Y is a finite class set, f:R^d→Y is fixed and measurable, and σ>0 has input-coordinate units. Independent noise samples approximate probabilities; they do not redefine the ideal g as a single noisy base prediction.↔ Scroll wide equations horizontally.

Use valid probability bounds and abstain

A general Gaussian certificate uses a lower bound on the candidate class probability and an upper bound on the strongest competing class probability. A conservative multiclass construction bounds all competing mass by one minus the candidate’s lower bound. It yields a positive radius only when that lower bound exceeds one half. This sufficient condition may abstain even when a candidate is actually the unique most probable class with probability below one half; abstention is not evidence of nonrobustness.

Select the candidate class using one sample batch, then use a fresh independent batch to estimate its probability with a valid one-sided binomial lower confidence bound. This avoids treating an adaptively selected empirical winner as though it had been fixed before observing the estimation sample. With n successes in n estimation draws, the exact one-sided Clopper–Pearson lower endpoint is alpha raised to the power 1/n. Even unanimous votes therefore give a lower bound below one at any finite sample size.

R=σ2[Φ−1(p‾A)−Φ−1(p‾B)],p‾B=1−p‾A ⟹ R=σΦ−1(p‾A)R=\frac{\sigma}{2}\left[\Phi^{-1}(\underline p_A)-\Phi^{-1}(\overline p_B)\right],\qquad \overline p_B=1-\underline p_A\ \Longrightarrow\ R=\sigma\Phi^{-1}(\underline p_A)
Φ is the standard-normal CDF. The general expression requires valid bounds with pA lower bound greater than pB upper bound. The conservative specialization requires 1/2<pA lower bound<1 and certifies unchanged ideal g for every L2 displacement strictly smaller than R, on the event that the probability bound is valid.↔ Scroll wide equations horizontally.

Attach confidence and correctness to the certificate

The confidence parameter controls the probability that the sampling procedure issues an invalid probability bound for a fixed input and fixed model. It is not the probability that an adversary succeeds on an individual perturbation, nor a posterior probability that this particular computed radius is correct. For many inputs, a per-input confidence statement does not automatically provide the same simultaneous confidence for the whole release. Allocate failure probability or report the scope using an appropriate multiple-testing argument.

A stable wrong prediction is still wrong. Certified accuracy at a radius counts only examples whose certified class equals the true label and whose radius meets the chosen threshold, with abstentions treated consistently. The theorem does not certify the unsmoothed base classifier, arbitrary semantic transformations, or a finite-vote deployed decision that differs from ideal g. Report sampling error, runtime, and exact inference aggregation separately. Changing model weights, preprocessing, or sigma invalidates reuse of a certificate computed for the earlier classifier.

Work it through

Unanimous votes still have finite-sample uncertainty

A candidate class is selected using an independent preliminary sample. In a fresh estimation batch it receives all n=10 votes. Use one-sided failure probability alpha=0.05, sigma=0.5, and the conservative certificate. Compute the exact lower endpoint and radius; use Φ⁻¹(0.7411344491)≈0.646846797.

  1. For ten successes in ten independent Bernoulli trials, the one-sided exact lower endpoint is alpha^(1/n)=0.05^(1/10)≈0.7411344491. It is not the observed fraction 1.

  2. The lower endpoint exceeds 0.5, so the conservative multiclass procedure can return the selected class with a positive radius. Competing-class probability is at most 1−0.7411344491≈0.2588655509 on the valid-bound event.

  3. The radius is sigma×Φ⁻¹(lower)=0.5×0.646846797≈0.3234233985 input units. Stability is claimed for L2 perturbations strictly below that radius, with the stated per-input sampling confidence.

The result

Ten unanimous votes do not produce infinite confidence or an infinite radius. The theorem and confidence procedure certify the ideal smoothed decision under the specified Gaussian model, not every possible deployed randomized rule.

The living notebook

Explore the model

Interactive lab

Interactive lab · sampling

Separate an unknown vote probability from a sample fraction

Reset, set Success probability p to 0.75 and Independent samples n to 12. Predict sample-mean expectation 0.75 and variance 0.015625 before Step. Reset, explicitly set p=0.75 and n=48, then Step: predict variance 0.00390625. These are exact iid binomial masses; playback highlights outcomes rather than sampling. The lab does not compute Clopper–Pearson endpoints or smoothing radii. Its Berry–Esseen readout bounds standardized CDF error, not bars or certification failure.

Separate an unknown vote probability from a sample fractionExact binomial masses for the mean of n independent Bernoulli trials, compared with normal mass between adjacent half-count boundaries; normal tails outside the finite support remain outside the bars. Playback highlights outcomes, not random samples. The Berry–Esseen bound applies to standardized CDFs, not individual bars or continuity-corrected errors. At p = 0 or 1, normal comparison and that bound are disabled. Normal-CDF evaluation uses a numerical approximation with absolute error below 7.5×10⁻⁸ (at most 1.5×10⁻⁷ per interval, before rounding). Current readings: Mean sample proportion: 0.5; Sample-mean variance: 0.0125; Uniform CDF error bound: ≤ 0.1062. All parameters are adjustable with the labeled controls below.Exact distribution of the mean of 20 independent Bernoulli variables with success probability 0.5; playback highlights outcome 0.00.250.50.75100.0580.1150.1730.23Sample mean · k / nProbability massNormal bin masses are an approximationk = 0 · exact probability = 9.54e-7
Exact binomial massNormal interval massHighlighted outcome / mean
Mean sample proportion
0.5
Sample-mean variance
0.0125
Uniform CDF error bound
≤ 0.1062
t = 0 s

Exact binomial masses for the mean of n independent Bernoulli trials, compared with normal mass between adjacent half-count boundaries; normal tails outside the finite support remain outside the bars. Playback highlights outcomes, not random samples. The Berry–Esseen bound applies to standardized CDFs, not individual bars or continuity-corrected errors. At p = 0 or 1, normal comparison and that bound are disabled. Normal-CDF evaluation uses a numerical approximation with absolute error below 7.5×10⁻⁸ (at most 1.5×10⁻⁷ per interval, before rounding). Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forA sample fraction and a valid probability lower bound serve different purposes.

Pause & reason

Check your understanding

A candidate’s valid conservative probability lower bound is 0.47. What should the positive-radius procedure described here do?

Your turn

Try it yourself

With independent candidate selection, all n=4 estimation votes choose that candidate and alpha=0.05. The exact one-sided lower endpoint is 0.05^(1/4)≈0.4728708. Can the conservative procedure certify a positive radius? Separately, if a valid lower bound is 0.9 and sigma=0.25, use Φ⁻¹(0.9)≈1.2815516 to find the radius.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Apply the one-half threshold before computing a positive radius.

Compare with the solution

The four-vote lower endpoint is below 0.5, so this conservative procedure abstains from a positive-radius claim despite unanimous observed votes. With lower bound 0.9 and sigma 0.25, the radius is 0.25×1.2815516≈0.3203879 input units for the ideal smoothed classifier under the stated assumptions.

Keep the idea

Take it with you

  • Gaussian noise geometry and the complete base function define the certified object.
  • Use valid finite-sample bounds and preserve selection-estimation independence.
  • State abstention, clean correctness, and per-input confidence explicitly.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.