Median Estimation — API Reference
Auto-generated from the source docstrings. For the problem formulation and a usage example, see the Median Estimation task page.
Types
dp_testing_platform.tasks.median_estimation.types
MedianEstimationMetadata
dataclass
Metadata for median estimation.
Attributes:
| Name | Type | Description |
|---|---|---|
n_samples |
int
|
Number of samples in the dataset. |
domain_lower_bound |
float | None
|
Lower bound of the data domain. Required by some algorithms. |
domain_upper_bound |
float | None
|
Upper bound of the data domain. Required by some algorithms. |
MedianEstimationInput
dataclass
Input for median estimation.
Attributes:
| Name | Type | Description |
|---|---|---|
X |
Array1D
|
Data vector, shape (n_samples,). |
MedianEstimationOutput
dataclass
Output for median estimation.
Attributes:
| Name | Type | Description |
|---|---|---|
median_est |
float
|
Estimated median (scalar). |
Algorithms
dp_testing_platform.tasks.median_estimation.algorithms.sample_median
SampleMedian
Bases: BaseAlgorithm
Non-private sample median (baseline).
Returns the middle value of sorted data. No privacy guarantees. Standard/textbook estimator; not a DP mechanism and has no single canonical paper.
Reference
Non-private baseline; no DP source paper.
dp_testing_platform.tasks.median_estimation.algorithms.ss_lln
SmoothSensitivityMechanismLLNMedian
Bases: BaseAlgorithm
Smooth sensitivity mechanism with Laplace log-normal noise.
Adds Laplace-log-normal noise scaled to the smooth sensitivity of the
median. The noise family provides 1/2eps_cdp^2-CDP; the offered budget is
spent as rho-zCDP and entered as eps_cdp = sqrt(2rho), then plugged into the dilation
eps_cdp = t/sigma + e^{3 sigma^2 / 2} s (t = beta).
Requires domain_lower_bound and domain_upper_bound in metadata.
The 1/2 scale is the add/remove-one local sensitivity of the midpoint
median convention.
Reference
Bun & Steinke, "Average-Case Averages: Private Algorithms for Smooth
Sensitivity and Mean Estimation", 2019 (arXiv:1906.02830). Laplace
-log-normal admissible noise: Theorem 18 (1/2*eps^2-CDP for
eps = t/sigma + e^{3 sigma^2 / 2} s).
https://arxiv.org/abs/1906.02830
Smooth-sensitivity median mechanism (the dplr family): Alabi,
McMillan, Sarathy, Smith & Vadhan, "Differentially Private Simple
Linear Regression", PoPETs 2022. https://arxiv.org/abs/2007.05157
Smooth-sensitivity framework: Nissim, Raskhodnikova & Smith, "Smooth
Sensitivity and Sampling in Private Data Analysis", STOC 2007.
https://doi.org/10.1145/1250790.1250803
Hyperparameters
beta: Smoothing parameter t of the smooth sensitivity. Default: 0.1.
dp_testing_platform.tasks.median_estimation.algorithms.ss_uln
SmoothSensitivityMechanismULNMedian
Bases: BaseAlgorithm
Smooth sensitivity mechanism with uniform log-normal noise.
Adds uniform-log-normal noise scaled to the smooth sensitivity of the
median. The noise family provides 1/2eps_cdp^2-CDP; the offered budget is
spent as rho-zCDP and entered as eps_cdp = sqrt(2rho), then plugged into the dilation
eps_cdp = t/sigma + e^{3 sigma^2 / 2} sqrt(2/(pi sigma^2)) s (t = beta).
The admissibility result holds only for sigma >= sqrt(2); the code uses
sigma = sqrt(2), sitting exactly on that boundary.
Requires domain_lower_bound and domain_upper_bound in metadata.
The 1/2 scale is the add/remove-one local sensitivity of the midpoint
median convention.
Reference
Bun & Steinke, "Average-Case Averages: Private Algorithms for Smooth
Sensitivity and Mean Estimation", 2019 (arXiv:1906.02830). Uniform
-log-normal admissible noise: Theorem 22 + Proposition 4 (1/2*eps^2-CDP
for eps = t/sigma + e^{3 sigma^2 / 2} sqrt(2/(pi sigma^2)) s,
sigma >= sqrt(2)). https://arxiv.org/abs/1906.02830
Smooth-sensitivity median mechanism (the dplr family): Alabi,
McMillan, Sarathy, Smith & Vadhan, "Differentially Private Simple
Linear Regression", PoPETs 2022. https://arxiv.org/abs/2007.05157
Smooth-sensitivity framework: Nissim, Raskhodnikova & Smith, "Smooth
Sensitivity and Sampling in Private Data Analysis", STOC 2007.
https://doi.org/10.1145/1250790.1250803
Hyperparameters
beta: Smoothing parameter t of the smooth sensitivity. Default: 0.1.
dp_testing_platform.tasks.median_estimation.algorithms.ss_students_t
SmoothSensitivityMechanismStudentsTMedian
Bases: BaseAlgorithm
Smooth sensitivity mechanism with Student's t noise.
Adds noise calibrated to the smooth sensitivity of the median. Satisfies pure epsilon-DP and therefore spends any offered budget through the pure-DP implication-lattice entry.
Requires domain_lower_bound and domain_upper_bound in metadata.
The 1/2 scale is the add/remove-one local sensitivity of the midpoint
median convention.
Reference
Alabi, McMillan, Sarathy, Smith & Vadhan, "Differentially Private
Simple Linear Regression", PoPETs 2022 (arXiv:2007.05157). DPSSTheilSen
median mechanism: Lemma 11 ((eps,0)-DP); Appendix E, Algorithm 5 +
Lemma 21 (Student's-t noise calibration t = beta,
s = 2*sqrt(d)*(eps - beta*(d+1))/(d+1)).
https://arxiv.org/abs/2007.05157
Smooth-sensitivity framework: Nissim, Raskhodnikova & Smith, "Smooth
Sensitivity and Sampling in Private Data Analysis", STOC 2007.
https://doi.org/10.1145/1250790.1250803
Hyperparameters
beta: Smoothing parameter t of the smooth sensitivity. Default: 0.1. d: Degrees of freedom for Student's t distribution. Default: 1.
dp_testing_platform.tasks.median_estimation.algorithms.ss_arsinh_normal
SmoothSensitivityMechanismArsinhNormalMedian
Bases: BaseAlgorithm
Smooth sensitivity mechanism with arsinh-normal noise.
Adds arsinh-normal noise scaled to the smooth sensitivity of the median.
The noise family provides 1/2eps_cdp^2-CDP; the offered budget is spent as
rho-zCDP and entered as eps_cdp = sqrt(2rho). The
dilation s = (6 sigma / (4 + 3 sigma^2)) (eps_cdp - sqrt(beta (beta/sigma^2
+ 1/sigma + 2))) is the algebraic inversion of the max-divergence bound
into the 1/2*eps^2-CDP form (t = beta). The code fixes sigma = 2/sqrt(3),
the paper's distinguished value at which the noise is calibrated.
Requires domain_lower_bound and domain_upper_bound in metadata.
The 1/2 scale is the add/remove-one local sensitivity of the midpoint
median convention.
Reference
Bun & Steinke, "Average-Case Averages: Private Algorithms for Smooth
Sensitivity and Mean Estimation", 2019 (arXiv:1906.02830). Arsinh
-normal admissible noise: Theorem 25 + Proposition 5 (1/2*eps^2-CDP;
sigma = 2/sqrt(3) is the paper's distinguished value).
https://arxiv.org/abs/1906.02830
Smooth-sensitivity median mechanism (the dplr family): Alabi,
McMillan, Sarathy, Smith & Vadhan, "Differentially Private Simple
Linear Regression", PoPETs 2022. https://arxiv.org/abs/2007.05157
Smooth-sensitivity framework: Nissim, Raskhodnikova & Smith, "Smooth
Sensitivity and Sampling in Private Data Analysis", STOC 2007.
https://doi.org/10.1145/1250790.1250803
Hyperparameters
beta: Smoothing parameter t of the smooth sensitivity. Default: 0.1.
dp_testing_platform.tasks.median_estimation.algorithms.exp_mech
ExponentialMechanismMedian
Bases: BaseAlgorithm
Exponential mechanism for median estimation.
Selects an interval based on distance from median rank. Satisfies eps-DP.
Requires domain_lower_bound and domain_upper_bound in metadata.
Reference
Alabi, McMillan, Sarathy, Smith & Vadhan, "Differentially Private
Simple Linear Regression", PoPETs 2022 (the dplr median family).
https://arxiv.org/abs/2007.05157
Exponential mechanism primitive: McSherry & Talwar, "Mechanism Design
via Differential Privacy", FOCS 2007.
https://doi.org/10.1109/FOCS.2007.66
dp_testing_platform.tasks.median_estimation.algorithms.exp_mech_wide
WideExponentialMechanismMedian
Bases: BaseAlgorithm
Wide exponential mechanism for median estimation.
Extends intervals around the median by a fixed width. Satisfies eps-DP.
Requires domain_lower_bound and domain_upper_bound in metadata.
Reference
Alabi, McMillan, Sarathy, Smith & Vadhan, "Differentially Private
Simple Linear Regression", PoPETs 2022 (the dplr median family).
https://arxiv.org/abs/2007.05157
Exponential mechanism primitive: McSherry & Talwar, "Mechanism Design
via Differential Privacy", FOCS 2007.
https://doi.org/10.1109/FOCS.2007.66
Hyperparameters
width: Interval extension around median. Default: 0.01.
dp_testing_platform.tasks.median_estimation.algorithms.unbounded_quantile
UnboundedQuantileMechanismMedian
Bases: BaseAlgorithm
Unbounded quantile mechanism for median estimation (AboveThreshold/SVT).
Implements the Unbounded Quantile Estimation mechanism of Durfee (2023), "Unbounded Differentially Private Quantile and Maximum Estimation" (arXiv:2305.01177), Algorithm 2: a noisy guess-and-check over a geometrically growing, data-independent candidate grid using a single invocation of AboveThreshold (the Sparse Vector Technique, Algorithm 1).
Mechanism. Candidate values estimate_k = lower + beta**k are tried for
k = 0, 1, 2, .... The per-candidate query is the count above the
candidate, f_k(X) = |{x : x > estimate_k}|, compared against the
threshold T = n/2 (the median). The count is monotonically decreasing
in k; AboveThreshold halts at the first k whose noisy count falls at
or below the noisy threshold, and the candidate estimate_k is released.
Privacy (pure eps-DP). This is exactly AboveThreshold on the negated count
query (Laplace noise is symmetric, so the "<=" stopping rule is AboveThreshold
on -f_k with threshold -T). Per Durfee (2023) Lemma 4.1 the count
queries are MONOTONIC with sensitivity Delta = 1, and per Lemma 3.1 (Lyu et
al. 2017) AboveThreshold with Laplace noise is (eps_1 + eps_2)-DP for
monotonic queries. We use the symmetric split eps_1 = eps_2 = eps/2, so
BOTH the (once-drawn) threshold noise and each per-query noise are
Lap(Delta / eps_i) = Lap(2/eps), giving eps-DP overall. This is the
paper's factor-2 improvement over the general-query split (which would use
Lap(2/eps) threshold / Lap(4/eps) query for (eps_1 + 2*eps_2)-DP).
Crucially the threshold noise is drawn ONCE before the loop (the property
that makes the privacy cost independent of the unbounded number of
candidates); only per-query noise is fresh each iteration. The released
candidate value is a deterministic post-processing of the halting index over
a DATA-INDEPENDENT grid (lower is public metadata, beta is a
hyperparameter), so releasing the value rather than the index leaks nothing
extra.
Requires domain_lower_bound in metadata (a public lower bound on the data domain; 0.0 for non-negative quantities such as squared errors).
Reference
Durfee, "Unbounded Differentially Private Quantile and Maximum Estimation", NeurIPS 2023 (Algorithm 2; AboveThreshold/SVT, Algorithm 1). https://arxiv.org/abs/2305.01177
Hyperparameters
beta: Multiplicative step size for the candidate grid. Default: 2.0.
dp_testing_platform.tasks.median_estimation.algorithms.truncated_exp_mech_bgsuz
TruncatedExponentialMechanismBGSUZ
Bases: BaseAlgorithm
Scalar truncated exponential mechanism for the median via Tukey depth + PTR.
Estimates the median by a Propose-Test-Release (PTR) check on Tukey-depth volumes followed by a truncated exponential mechanism over the surviving candidate interval; satisfies (eps, delta)-DP.
Reference
"BGSUZ" = Brown, Gaboardi, Smith, Ullman & Zakynthinou, "Covariance- Aware Private Mean Estimation Without Private Covariance Estimation", NeurIPS 2021 (the Tukey-depth PTR construction). https://arxiv.org/abs/2106.13329 "AJRV" = Amin, Joseph, Ribero & Vassilvitskii, "Easy Differentially Private Linear Regression", 2022 (the distance-lower-bound PTR variant implemented here for the Phase-1 volume test). https://arxiv.org/abs/2208.07353
Lifted algorithms
M-estimation algorithms presented as native median-estimation algorithms (the L1 loss whose minimizer is the sample median).
dp_testing_platform.tasks.median_estimation.algorithms.lifted
M-estimation algorithms lifted onto the median-estimation task.
Each class presents an m_estimation algorithm as a native
median_estimation algorithm. The child->parent map fixes the L1 loss whose
minimizer is the sample median: the scalar per-row data is reshaped to a single
feature column and the fitted M-estimation parameter is returned as the median
estimate. lift_input is per-row (row i maps to row i), so the inner
algorithm's (eps, delta)-DP guarantee transfers verbatim.
Instance generators
dp_testing_platform.tasks.median_estimation.instance_generators.simple_gaussian
SimpleGaussian
Bases: InstanceGenerator
Gaussian instance generator for median estimation.
Generates X ~ N(median, 1). The true domain is unbounded.
If known_domain is True, uses min(X) and max(X) as domain bounds. This violates privacy (data-dependent bounds) but is useful for testing algorithms that require domain bounds.
Metrics
dp_testing_platform.tasks.median_estimation.metrics
Metric registry for median_estimation task.
l1_error
L1 error between estimated median and reference.
empirical_quantile_error
Quantile error computed from the empirical distribution of the dataset.
Measures how far the estimate is from being a valid median of the data. For a true median x, we have P(Y < x) <= 0.5 and P(Y > x) <= 0.5.
The error is: max(P(Y < x) - 0.5, P(Y > x) - 0.5, 0)
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
output
|
MedianEstimationOutput
|
The algorithm output containing median_est. |
required |
data
|
Array1D
|
The dataset samples (1D array). |
required |
Returns:
| Type | Description |
|---|---|
float
|
The quantile error (0 if estimate is a valid median). |
distribution_quantile_error
Quantile error computed from the true CDF of the distribution.
Measures how far the estimate is from being a valid median of the distribution. For a true median x, we have CDF(x) >= 0.5 and 1 - CDF(x) >= 0.5.
The error is: max(CDF(x) - 0.5, (1 - CDF(x)) - 0.5, 0)
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
output
|
MedianEstimationOutput
|
The algorithm output containing median_est. |
required |
cdf
|
Callable[[float], float]
|
The cumulative distribution function of the true distribution. |
required |
Returns:
| Type | Description |
|---|---|
float
|
The quantile error (0 if estimate is a valid median). |