Skip to content

Median Estimation

Problem Formulation

Given a dataset of \(n\) scalar samples \(X \in \mathbb{R}^{n}\), estimate the median. The non-private estimator is the empirical median:

\[\hat{m} = \operatorname{median}(X_1, \dots, X_n)\]

Under differential privacy we want a release \(\tilde{m}\) that satisfies \(\varepsilon\)-DP or \((\varepsilon, \delta)\)-DP while staying close to \(\hat{m}\) or the true distributional median. The median is robust (its local sensitivity is small for well-spread data), which motivates smooth-sensitivity and exponential-mechanism approaches. Most algorithms require a public domain (lower/upper bound) on the data.

API Reference

Types, algorithms (with their privacy arguments + hyperparameter defaults), instance generators, and metrics are documented from the source docstrings on the Median Estimation API Reference page.

Inherited Algorithms

Median estimation is a child of the M-Estimation task, so all M-estimation algorithms (e.g. DPGradientDescent, EmpiricalRiskMinimization, GradientDescent, StochasticGradientDescent) are available via task inheritance — the absolute-loss M-estimation objective recovers the median. See the M-Estimation task page.

Usage Example

from dp_testing_platform import PureDPBudget
from dp_testing_platform.tasks.median_estimation import MedianEstimationTask
from dp_testing_platform.tasks.median_estimation.algorithms import (
    SampleMedian,
    ExponentialMechanismMedian,
)
import numpy as np

# Scalar data with known domain bounds
np.random.seed(0)
n = 1000
X = np.clip(np.random.randn(n), -5.0, 5.0)

metadata = MedianEstimationTask.Metadata(
    n_samples=n, domain_lower_bound=-5.0, domain_upper_bound=5.0
)
input_data = MedianEstimationTask.Input(X=X)

# Non-private baseline
budget = PureDPBudget(1.0)
base_out = SampleMedian().run(metadata, input_data, budget, seed=0)

# DP exponential mechanism (pure eps-DP)
dp_out = ExponentialMechanismMedian().run(metadata, input_data, budget, seed=0)

print(f"Baseline median: {base_out.median_est:.4f}")
print(f"DP median:       {dp_out.median_est:.4f}")