Certified Fair Decisions from Smoothed Scores

Many high-stakes classifiers, such as those used for credit, bail, or admissions, are turned into decisions by a post-processing step. A score is mapped to an acceptance probability, and that mapping is tuned so that different demographic groups are selected at similar rates. This step can be solved exactly as a linear program (an optimization with a linear objective and linear constraints), because group selection rates are averages of acceptance probabilities. Its guarantee is fragile, though. If an adversary, a strategic applicant, or a small data corruption nudges each person's features slightly, the scores move, and the carefully balanced rates can break. Randomized smoothing addresses the opposite half of the problem. It averages a model's predictions over Gaussian-noised copies of the input, which provably limits how far the averaged score can move under a small change to the input. It says nothing about group fairness.

This note proposes joining the two through one observation. After smoothing, the worst an adversary can do to any individual is shift their score within a known, narrow window. The worst-case selection rate of a whole group is therefore a sum of per-person maxima or minima over that window, and this can be written with linear constraints. The result is a single small linear program that outputs a randomized decision rule on top of a smoothed model. Its demographic-parity or equal-opportunity gap is certified to stay below a chosen budget against every feature perturbation of size at most ε. It maximizes accuracy subject to that certificate, and it requires no retraining of the network.

Core Claim

Let $f$ be a binary base classifier and $p(x)=\mathbb{P}_{\delta\sim\mathcal{N}(0,\sigma^2 I)}(f(x+\delta)=1)$ its smoothed score. The Neyman-Pearson argument that yields the certified radius $R=\tfrac{\sigma}{2}(\Phi^{-1}(p_A)-\Phi^{-1}(p_B))$ in Certified Adversarial Robustness with Additive Noise and Certified Adversarial Robustness via Randomized Smoothing also gives a score-level statement:

$$|\Phi^{-1}(p(x))-\Phi^{-1}(p(x'))|\le \|x-x'\|_2/\sigma,$$

where $\Phi^{-1}$ is the inverse standard normal CDF. Under an ℓ2 perturbation of size ε, each person's probit score $z=\Phi^{-1}(p(x))$ can move by at most $w=\varepsilon/\sigma$.

Partition $z$ into bins $k=1,\dots,K$. The decision rule is a table of acceptance probabilities $\pi_{a,k}\in[0,1]$ for group $a$ (sensitive attributes are assumed unperturbable) and bin $k$. Let $m_{a,k}$ be the empirical mass of group $a$ in bin $k$, and let $W(k)$ be the set of bins reachable within $w$. The attacked selection rate of group $a$ then lies in $[L_a,U_a]$:

$$U_a=\sum_k m_{a,k}\max_{j\in W(k)}\pi_{a,j},\qquad L_a=\sum_k m_{a,k}\min_{j\in W(k)}\pi_{a,j}.$$

The certified parity constraints are $U_0-L_1\le\tau$ and $U_1-L_0\le\tau$. These are convex in $\pi$ and become linear after introducing one epigraph variable per bin and group, $t_{a,k}\ge\pi_{a,j}$ and $s_{a,k}\le\pi_{a,j}$ for $j\in W(k)$. Equal opportunity uses the same construction restricted to positives. Worst-case accuracy follows the same pattern: positives contribute $s$ and negatives contribute $1-t$. Maximizing it, or nominal accuracy, subject to the certified constraints is therefore still a linear program with $O(K\cdot|W|)$ constraints.

Because the bound holds per individual, it holds for any joint attack on the population. That includes every covariate shift in which no person's features move by more than ε.

Two further linear constraints are optional. A slope bound $|\pi_{a,k+1}-\pi_{a,k}|\le \lambda\Delta$ yields a per-person certificate: the acceptance probability of any individual changes by at most $\lambda w$. This is the ℓ2-certified analogue of the bounded-density threshold in Individual Fairness In Strategic Classification. Second, finite Monte Carlo estimation of $p(x)$ is handled by widening $W(k)$ by the Clopper-Pearson interval of the probit estimate. This matters for cost. The decision only needs to locate a person's bin window, not tight bounds on the score, so a few hundred noise samples may suffice instead of the $10^5$ used in Individual Fairness Revisited. Whether this holds in practice is an empirical question the program tests.

Relation to Prior Work

The linear-programming side supplies the method. On the Power of Randomization in Fair Classification and Representation shows that optimal fair classifiers are randomized "mass-threshold" rules found by convex optimization. Happiness as a Measure of Fairness shows that such post-processing linear programs run in minutes without retraining. Individual Fairness In Strategic Classification discretizes a randomized threshold into $K$ bins with Lipschitz and group constraints. All three optimize over unperturbed scores and certify nothing about feature perturbations. We keep their binned structure but replace nominal rates with certified worst-case rates.

On the smoothing side, three papers constrain and motivate the design. Individual Fairness Revisited smooths a frozen network to certify individual Lipschitz fairness, but has no group constraints and no policy optimization. Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing certifies group fairness under demographic-partition shift, but does so by smoothing weights during expensive training and does not certify input ℓ2 balls. Certifying Confidence via Randomized Smoothing bounds score movement, which is the ingredient we reuse, but not in a decision program.

From Fragile to Certified: Wasserstein Audits is the closest in spirit: it upper-bounds group unfairness of a fixed classifier over a Wasserstein ball. It audits rather than optimizes, and it uses no smoothing. Our per-person ε-window corresponds to a Wasserstein-∞ ball, and we optimize the rule against it.

Research Program

The program has three parts. First, build the certified-fairness linear program for demographic parity and equal opportunity, with nominal-accuracy and worst-case-accuracy objectives. Add a finite-sample slack on bin masses so the certificate transfers from calibration data to the population. Second, analyze the price of certification. The robust program's feasible set shrinks as $w=\varepsilon/\sigma$ grows, which exposes a three-way trade-off among σ (clean accuracy, the usual "robustness tax"), ε (certified budget), and τ (fairness budget). We will prove that for $w\to 0$ the program recovers the nominal mass-threshold solution. We will also characterize when base-rate differences between groups make certified parity infeasible at a given ε. This is the Neyman-Pearson-versus-parity tension: groups whose mass sits near the decision region lose more certified rate. Third, study the test-time sampling budget. We measure how certified gap and accuracy degrade as Monte Carlo samples fall from $10^5$ to $10^2$, given that the window absorbs estimation error.

Baselines

The naive reference point is the unconstrained smoothed classifier: majority vote at $p=0.5$, trained with Gaussian noise augmentation. We report its nominal and certified parity gap to show how far from fair a certified-robust model is by default.

The strongest competitor on the question "do we need the robust constraints at all?" is the nominal fair linear program applied to the same smoothed scores. This is the method of On the Power of Randomization and Happiness as a Measure of Fairness, run on the same bins and with the same τ. It is also the key ablation, because it differs from our method only in replacing $U_a,L_a$ with nominal rates. Beating it means achieving a certified gap at or below τ where the nominal program's certified gap exceeds τ, while losing at most a few points of accuracy.

The strongest existing certified-group-fairness method is FAIRSMOOTH ( Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing). It reports, combined across Adult and COMPAS, an "18.7% boost in Accuracy" and a "48.2% reduction in Demographic Parity Disparity," both relative to its baselines. It reports no certified gap under input ℓ2 attack, so we will evaluate its trained models under our certificate and under PGD attacks. We will match its training compute against our noise-augmented training plus linear program.

For the strategic-classification comparison, we run the binned program of Individual Fairness In Strategic Classification on FICO. It reports an individual-fairness ratio dropping "from 4.421 … to as low as 0.100" with F1 "only dipped from 0.986 to 0.975." We match its bins and parity constraint and add only the certified window.

All methods share data splits, base architectures, and a fixed hyperparameter grid over σ, K, τ, and λ, with tuning on a validation split.

Why not just…?

Why not just certify each individual's label with the standard radius and count uncertified people as worst case? This does give a valid certified parity bound, and it is our "certify-then-count" baseline. It treats every uncertified person as fully flippable and every certified one as fixed. Our window bound is never looser, because a randomized rule with gradual acceptance changes loses only part of a person's probability. The count-based approach also cannot be optimized directly over thresholds. The experiments quantify the gap between the two bounds at matched accuracy. If the gap is negligible, the contribution reduces to the optimization, and we will say so.

Why not just sweep a deterministic threshold per group on the smoothed score? Deterministic rules are a special case of our feasible set, so they can only match or lose. They lose on accuracy under parity, as proven in On the Power of Randomization. They also lose on individual certificates, since a hard cutoff has unbounded slope and the per-person guarantee is vacuous at the boundary. The FICO numbers from Individual Fairness In Strategic Classification illustrate this in the unperturbed setting. We include the sweep, with its certified gap computed by our bound.

Why not just use adversarial training with a fairness penalty? It provides no certificate. The file documents that empirical defenses are broken by adaptive attacks (Certified Adversarial Robustness with Additive Noise) and that unsmoothed fair classifiers' metrics "oscillated wildly" across test partitions (FAIRSMOOTH). This alternative could still match us on empirical PGD-attacked parity. We report that number honestly, and we treat the certificate as the distinguishing deliverable, not the empirical gap.

Proposed Experiments

On the tabular benchmarks, we use Adult, COMPAS, FICO, Law School, HELOC, and ACS Income, with standardized features and ℓ2 ε on the standardized scale. On images, we use CelebA with a binary attribute target and a demographic sensitive attribute, where ℓ2 smoothing is most natural. Diffusion-denoised smoothing ((Certified!!) Adversarial Robustness for Free!) serves as a no-retraining base, and its reported "70.6% certified accuracy at ε = 0.25" on CIFAR-10 indicates the regime is viable. No reported result was found on Lacuna for certified demographic-parity gap under input ℓ2 perturbation on any of these datasets, so that metric is new.

We report five quantities: nominal accuracy, certified worst-case accuracy, nominal and certified DP and EO gaps across ε, the individual acceptance-change certificate $\lambda w$, and empirical gaps under group-targeted PGD attacks on the smoothed decision. The PGD results check that certificates are not merely loose.

The decisive check is the ablation against the nominal program on identical smoothed scores. If the nominal solution's certified gap is already below τ for realistic ε, smoothing alone provides robust fairness, and the method should be recast as a certification tool rather than a new decision rule. The second decisive check is the Monte Carlo curve. If certified gaps with $10^2$–$10^3$ samples stay within one point of those with $10^5$, the approach cuts test-time cost by orders of magnitude over Individual Fairness Revisited. The third is the infeasibility boundary: we predict it appears at smaller ε on datasets with larger base-rate gaps, such as COMPAS relative to Adult. This would confirm the analyzed tension between Neyman-Pearson worst cases and parity.