◇ OpenCyber Academy
Doctoral research · Chapter 4 · English

Chapter 4 — Baseline replication and pilot

Open, free learning for anyone who wants to protect people and technology. No account is required to read this text or its worked answers.

Chapter 4 — Baseline replication and pilot

Lesson map

Lesson 04 published. Map, example, EX021.

flowchart TD
  N0["Learning outcomes"]
  N1["4.1 Replicating first"]
  N2["4.2 The pilot release"]
  N3["4.3 Small cells"]
  N4["4.4 Budget accounting"]
  N5["Lab — Laplace noise on origin-destination counts"]
  N6["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6
  N6 --> EX["Worked example"]
  EX --> Q["Exercise EX021"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["4.1 Replicating first"]
  N2["4.2 The pilot release"]
  N3["4.3 Small cells"]
  N4["4.4 Budget accounting"]
  N5["Lab — Laplace noise on origin-destination counts"]
  N6["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> Q["EX021"]

[Learning outcomes]
    |
    v
[4.1 Replicating first]
    |
    v
[4.2 The pilot release]
    |
    v
[4.3 Small cells]
    |
    v
[4.4 Budget accounting]
    |
    v
[Lab — Laplace noise on origin-destination counts]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX021]

Learning outcomes

You will (1) replicate a known result before extending it; (2) implement the Laplace mechanism on counts; (3) read the accuracy cost of epsilon on small cells.

4.1 Replicating first

Before trusting her own code, Ines replicates a textbook property described by Dwork and Roth (2014): for Laplace noise with scale one over epsilon, the expected absolute error equals one over epsilon. If her implementation produced a different average, every later result would be suspect. She draws many noise samples for each epsilon and checks the mean absolute error against the theory. The replication is a small step, but Prof. Aaltonen insists that it appears in the thesis, because examiners need evidence that the instrument works before they consider what it measures in the transit setting.

4.2 The pilot release

The pilot uses 100 synthetic origin-destination counts between zero and 400 journeys a day. For each epsilon in the grid 0.1, 0.5, 1.0 and 2.0, the lab adds Laplace noise twenty times to every count. The mean absolute error is 9.91 at epsilon 0.1, 1.98 at 0.5, 0.98 at 1.0 and 0.51 at 2.0, matching one over epsilon closely. The replication passes. Ines notes that these absolute errors look tiny next to counts of several hundred journeys, which is exactly why the next step examines small cells separately rather than trusting an average. Small cells get separate checks.

4.3 Small cells

Planners care most about quiet routes, where a few journeys decide whether a bus continues to run. The pilot contains five cells with fewer than twenty journeys a day. On those cells the mean relative error is 94.1% at epsilon 0.1, 22.0% at 0.5, 9.3% at 1.0 and 5.0% at 2.0. At epsilon 0.1 the published number is almost noise. Ines therefore expects planners to reject low epsilon values for small routes, and she adds a pre-registered secondary analysis that reports errors separately for small and large cells, so that an average cannot hide the problem.

4.4 Budget accounting

Each published table spends part of a privacy budget, because answering several queries about the same riders adds up. Dwork and Roth describe how epsilon values combine under composition. Valemont wants daily tables for a year, so Ines must decide whether epsilon one is per table, per day or per year. She writes this decision into the protocol as an explicit question for the authority's data protection officer, because it changes the strength of the guarantee by orders of magnitude, and she warns that a per-table epsilon repeated daily cannot be described honestly as a strong annual protection.

Lab — Laplace noise on origin-destination counts

# Laplace mechanism on 100 synthetic origin-destination counts (sensitivity 1); error by epsilon.
import random, math
r = random.Random(3)
true = [r.randint(0, 400) for _ in range(100)]
def lap(b):
    u = r.random() - 0.5
    return -b * math.copysign(1, u) * math.log(1 - 2 * abs(u))
for eps in [0.1, 0.5, 1.0, 2.0]:
    errs = [abs(lap(1 / eps)) for _ in true for _ in range(20)]
    small = [t for t in true if t < 20]
    rel = sum(abs(lap(1 / eps)) / max(t, 1) for t in small for _ in range(20)) / (20 * len(small))
    print(f"epsilon {eps:3.1f}  mean abs error {sum(errs)/len(errs):5.2f}  mean relative error on {len(small)} small cells {rel:6.1%}")

Run with python3 lab_laplace.py. Verified output:

epsilon 0.1  mean abs error  9.91  mean relative error on 5 small cells  94.1%
epsilon 0.5  mean abs error  1.98  mean relative error on 5 small cells  22.0%
epsilon 1.0  mean abs error  0.98  mean relative error on 5 small cells   9.3%
epsilon 2.0  mean abs error  0.51  mean relative error on 5 small cells   5.0%

Worked example

Ines replicates the one-over-epsilon error of the Laplace mechanism (0.98 at epsilon 1.0), then finds a 94.1% relative error on small cells at epsilon 0.1, and raises budget accounting as a protocol decision.

Synthetic case. Counts are synthetic and seeded; Dwork, McSherry, Nissim and Smith (2006) and Dwork and Roth (2014) are real.

Errors and limits

Five small cells are too few for precise estimates. Real releases also need post-processing, such as rounding negative counts, which the pilot omits.

Exercises

Synthesis

Chapter 4 replicates the mechanism and exposes small-cell error and budget accounting. Chapter 5 runs the main study with an independent attack.

Continue studying — chapter 04 of 08

← Chapter 03 (draft) · Course chapter index · Chapter 05 (draft) →