Mathematical Background

This section provides the formal mathematical details underlying the Fair-Seldonian framework. The core algorithm follows the Quasi-Seldonian approach introduced in [Thomas2019].

Notation

Symbol	Definition
$\mathcal{D}$	Training dataset of $n$ i.i.d. samples $\{(x_i, y_i, t_i)\}_{i=1}^n$
$\mathcal{D}_c, \mathcal{D}_s$	Candidate and safety data splits
$\theta$	Model parameters
$f(\theta)$	Primary objective function (to maximize)
$g(\theta)$	Behavioral constraint function ($g(\theta) \leq 0$ required)
$\delta$	Significance level; constraint holds with probability $\geq 1 - \delta$
$\hat{g}(\theta)$	Upper confidence bound on $g(\theta)$
$T$	Sensitive attribute (group membership)

Quasi-Seldonian Algorithm

The Quasi-Seldonian Algorithm (QSA) consists of two computational phases after data splitting.

Candidate selection. Find $\theta^*$ by solving:

$$\theta^* = \arg\max_\theta \; f(\theta) \quad \text{s.t.} \quad \hat{g}_c(\theta, \mathcal{D}_c) \leq 0$$

where $\hat{g}_c$ is the predicted upper bound — an estimate of what the safety test bound will be, computed using the candidate data.

The constraint is not imposed as a hard barrier. What is actually minimised is the log loss plus an exact penalty on the violation:

$$\tilde{f}(\theta) = \underbrace{-f(\theta)}_{\text{log loss}} \; + \; \lambda \cdot \max\bigl(0,\; \hat{g}_c(\theta)\bigr)$$

with $\lambda$ set by penalty. This is continuous everywhere, order 1, and equal to the log loss on the feasible side.

Important

The tempting alternative — return a large constant plus $\hat{g}_c$ when infeasible, and the loss when feasible — does not work here, and the reason is worth knowing because the failure is silent.

SciPy’s Powell convergence test is relative. With an objective of order $10^4$ and the default ftol of $10^{-4}$, the stopping threshold works out near $1.0$, while $\hat{g}_c$ varies by only about $10^{-2}$ across the whole parameter space. Powell then reports success after a single iteration while still infeasible, and max_iter never binds. Every run returns No Solution Found, and nothing about it looks like a bug.

Keeping the objective order 1 is what gives the optimizer usable signal on the infeasible side.

Safety test. Given $\theta^*$, compute the upper confidence bound on $g(\theta^*)$ using the safety data:

$$\hat{g}_s(\theta^*, \mathcal{D}_s) \leq 0 \implies \text{accept } \theta^*$$

$$\hat{g}_s(\theta^*, \mathcal{D}_s) > 0 \implies \text{No Solution Found}$$

Delta Splitting

When the constraint expression tree has binary operators, the confidence level $\delta$ must be split between the left and right subtrees. By Boole’s inequality (the union bound) [Bonferroni1936], if each subtree’s bound holds with probability $1 - \delta_i$, the combined bound holds with probability $1 - \sum_i \delta_i$.

Uniform splitting (base mode) assigns $\delta/2$ to each child of every binary operator:

$$\delta_{\text{left}} = \delta_{\text{right}} = \frac{\delta}{2}$$

This is conservative: it does not account for constant nodes or repeated variables. The Algorithm Variants section describes three optimizations that address those, and a fourth, Affine-Form Compilation (affine), that sidesteps the per-leaf split altogether for constraints inside its fragment.

Interval Arithmetic

Confidence intervals are propagated through the expression tree using standard interval arithmetic rules [Moore1966]. For intervals $[l_x, u_x]$ and $[l_y, u_y]$:

Addition:

$$[l_x, u_x] + [l_y, u_y] = [l_x + l_y, \; u_x + u_y]$$

Subtraction:

$$[l_x, u_x] - [l_y, u_y] = [l_x - u_y, \; u_x - l_y]$$

Multiplication:

$$[l_x, u_x] \times [l_y, u_y] = \left[\min(S), \; \max(S)\right]$$

where $S = \{l_x l_y, \; l_x u_y, \; u_x l_y, \; u_x u_y\}$. The implementation handles all sign combinations (both positive, both negative, mixed signs) as special cases for efficiency.

Division:

$$[l_x, u_x] \,/\, [l_y, u_y] = [l_x, u_x] \times [1/u_y, \; 1/l_y] \quad \text{if } 0 \notin [l_y, u_y]$$

If $0 \in [l_y, u_y]$, the result is $(-\infty, +\infty)$.

Absolute value:

$$|[l_x, u_x]| = \begin{cases} [l_x, u_x] & \text{if } l_x \geq 0 \\ [-u_x, -l_x] & \text{if } u_x \leq 0 \\ [0, \max(-l_x, u_x)] & \text{if } l_x < 0 < u_x \end{cases}$$

See fair_seldonian.constraints.bounds for the full implementation.

Predicted Bounds

During candidate selection, the algorithm does not have access to the safety data. Instead, it predicts what the safety test bound will be by accounting for the statistical uncertainty from both data splits.

Standard prediction (base mode) uses a doubled Hoeffding term [Hoeffding1963]:

$$\hat{p} \pm 2\sqrt{\frac{\ln(c/\delta)}{2 \, |\mathcal{D}_s|}}$$

Decomposed prediction (mod mode) separates candidate and safety estimation error:

$$\hat{p} \pm \sqrt{\frac{\ln(c/\delta)}{2 \, |\mathcal{D}_c|}} + \sqrt{\frac{\ln(c/\delta)}{2 \, |\mathcal{D}_s|}}$$

Here $c = 2$ for a two-sided interval and $c = 1$ for a one-sided one; the root of a constraint tree needs only its upper endpoint, so leaves that inherit that one-sidedness pay the smaller term. See Concentration Inequalities.

The decomposed form yields tighter bounds when $|\mathcal{D}_c|$ and $|\mathcal{D}_s|$ differ substantially. See Algorithm Variants for the full set of optimizations.