Private Quantiles

You work at a hospital and want to publish the median salary of your staff so researchers can compare pay across institutions. Publishing the raw list is off the table — that would expose individual employees. Publishing just the median sounds safe. It is not.

Suppose the true median is $72,000. Now one employee changes jobs and her salary of $71,500 is replaced by an outside hire at $200,000. The median jumps to $73,000. An attacker who sees both published numbers can deduce that someone earning between $71,500 and $73,000 left the dataset. A single record leaves a fingerprint.

Differential privacy (DP) fixes this. Instead of the exact median, you release a slightly noisy version. The noise is calibrated so that whether or not any one person is in the dataset, the output looks almost the same — making it mathematically impossible to detect individuals. The formal guarantee, introduced by Cynthia Dwork and colleagues in 2006, is:

$$\Pr[\mathcal{M}(D) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{M}(D') \in S]$$

for any two datasets $D$ and $D'$ that differ in exactly one record, and any measurable output set $S$. The parameter $\varepsilon$ ("epsilon") controls the privacy–accuracy tradeoff: smaller $\varepsilon$ means more privacy but a noisier answer.

The demo below shows a dataset of values in $[0, 100]$. The true median is shown in blue; the private median adds Laplace noise calibrated to $\varepsilon$ and the sensitivity of the median query.

<!-- {{c_html_intro}} -->
<div class="controls">
  <div class="control-row">
    <label for="eps-slider">{{lbl_epsilon}} <span id="eps-val" class="val-badge">1.0</span></label>
    <input id="eps-slider" type="range" min="0.1" max="5" step="0.1" value="1">
  </div>
  <div class="control-row">
    <label for="n-slider">{{lbl_n}} <span id="n-val" class="val-badge">30</span></label>
    <input id="n-slider" type="range" min="5" max="100" step="1" value="30">
  </div>
  <button id="resample-btn" type="button">{{btn_resample}}</button>
</div>
<div class="chart-wrap">
  <canvas id="chart" width="520" height="160"></canvas>
</div>
<div class="legend">
  <span class="dot true-dot"></span><span>{{lbl_true_median}}</span>
  <span class="dot priv-dot"></span><span>{{lbl_priv_median}}</span>
</div>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 8px; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; align-items: center; margin-bottom: .7rem; }
.control-row { display: flex; flex-direction: column; gap: 2px; min-width: 180px; }
label { font-size: .82rem; color: #444; font-weight: 600; display: flex; align-items: center; gap: .4rem; }
.val-badge { background: #1d3557; color: #fff; border-radius: 4px; padding: 1px 6px; font-size: .8rem; }
input[type=range] { width: 100%; accent-color: #1d3557; }
button { font: 600 13px system-ui; padding: .4rem .85rem; background: #1d3557; color: #fff;
         border: none; border-radius: 7px; cursor: pointer; }
button:hover { background: #274d7a; }
.chart-wrap { border: 1px solid #d0d7de; border-radius: 8px; overflow: hidden; background: #f8fafc; }
canvas { display: block; width: 100%; height: auto; }
.legend { display: flex; gap: .9rem; align-items: center; margin: .5rem 0 .3rem; font-size: .83rem; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; }
.true-dot { background: #2563eb; }
.priv-dot { background: #e63946; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.3em; color: #444; }

// Code not found

Notice that as you decrease $\varepsilon$ (stronger privacy) the private median drifts further from the true one. As you increase $\varepsilon$ (weaker privacy) it tracks the true median closely. Adding more data points shrinks the error at any fixed $\varepsilon$ — with enough data you can be private and accurate. That is the core promise of differential privacy.

Why can we add noise and call it private? The key concept is sensitivity: how much can one person's record change the output?

For the median of $n$ values in a bounded range $[0, B]$, removing or changing one record moves the median by at most $B/1$ in the worst case — so the global sensitivity is $\Delta = B$. The Laplace mechanism draws noise from $\text{Lap}(0,\, \Delta / \varepsilon)$ and adds it to the true median:

$$\tilde{m} = \text{median}(D) + \text{Lap}\!\left(\frac{\Delta}{\varepsilon}\right)$$

This satisfies $\varepsilon$-differential privacy exactly. The expected absolute error is $\Delta / \varepsilon$, so doubling the privacy budget (halving $\varepsilon$) doubles the error.

For arbitrary quantiles (not just the median), a cleaner approach is the exponential mechanism (McSherry and Talwar, 2007): assign each candidate value a score based on how many records fall on each side, then sample a value with probability proportional to $\exp(\varepsilon \cdot \text{score} / 2)$. This avoids the post-processing step of clipping the noisy answer back into $[0, B]$ and achieves near-optimal error. For $n$ records and quantile $q$, the expected rank error is $O(\log(1/\delta) / \varepsilon)$ for $(\varepsilon, \delta)$-DP.

Releasing multiple quantiles simultaneously requires care: naively applying the Laplace mechanism $k$ times would multiply the privacy cost by $k$ (basic composition). Better algorithms — like the one by Gillenwater et al. (2021) — release all quantiles jointly with a total cost of $O(\varepsilon)$ regardless of how many quantiles are requested, by exploiting the joint sensitivity of the vector.

Private quantiles are one of the most practical tools in the differential-privacy toolkit:

• Salary and compensation surveys: industry benchmarks publish median pay without letting employers back-calculate any individual's salary.
• Medical research: reporting the median or 95th percentile of a lab measurement across patients without revealing who is in the cohort.
• Federated analytics: Apple and Google use DP histograms and quantiles to collect usage statistics from millions of devices without any individual device's data being identifiable.
• Streaming and monitoring: infrastructure teams publish latency percentiles (p50, p95, p99) for services handling private user data; DP keeps individual requests hidden.
• Machine-learning training: gradient clipping thresholds are set using private quantiles of gradient norms, a technique used in differentially private stochastic gradient descent (DP-SGD).

The same math underlies every approach: calibrate noise to sensitivity, trade a controlled amount of accuracy for a formal privacy guarantee. Once you understand private quantiles, you are most of the way to understanding PAC learning under privacy constraints and the broader landscape of counting problems where exact answers are too revealing.

The median feels like an innocent summary — just the middle value, nothing personal. But as we saw, a single record change can shift it enough to reveal who left or joined a dataset. Differential privacy fixes this by treating noise as a feature rather than a flaw: a carefully sized random perturbation makes every individual's participation invisible to any observer.

The Laplace mechanism is elegant precisely because the tradeoff is explicit: you set $\varepsilon$, you know exactly how much error to expect, and you have a mathematical proof that no attacker can detect any individual. Larger datasets make the tradeoff more favorable, which is why DP has become the standard for large-scale analytics at tech companies.

Next time you read "median salary: $72,000" in a published report, it may well be a private median — a number that is simultaneously useful and provably safe, produced by the same idea behind PAC learning under privacy constraints.