Marginal counts are rounded to float32 before noise, which increases sensitivity for large values

Abierto
  • ¿Algo no está bien?
#290 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
48/100
Tipo de issue
Error
Claridad
Bastante claro
Estado de actividad
Activo
Stack tecnológico
numpy, python
Área
backend, databases, security

Línea de trabajo

Start by tracing how discrete-mechanism marginals pass through data.project() into an mbi Factor, and where sensitivity is computed relative to noise. Reproduce the reported discrepancy with the weighted dataset in the issue, then identify a representation and sensitivity calculation that preserve the intended neighboring-dataset bound. Done means the released marginal satisfies the stated differential privacy guarantee for the large-count example.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

Every discrete-mechanism marginal goes through data.project(), which converts it to an mbi Factor, which is implicitly stored in float32 by default. For large numbers of records, the floating-point imprecision has an influence on the sensitivity: the ulp after 2²⁴ is 2, the ulp after 2²⁵ is 4, etc., so adding single element can lead to a larger-than-1 increase in the float32 representation.

To observe the issue, we don't need to build a massive dataset, we can just use the weights parameter in the input dataset to emulate what would happen if a specific value was present 2²⁶+4 or 2²⁶+5 times — values that will be rounded to 2²⁶ and 2²⁶+8, respectively. The sensitivity mismatch makes it easy to retrieve the original database.

import math
import mbi
import numpy as np
import dpsynth
from dpsynth.discrete_mechanisms import common

# one binary column: D has 2^26 + 4 records with value 0 and 1000 with value 1; D' has one more record with value 0
D = mbi.Dataset({"a": np.array([0, 1])}, mbi.Domain(["a"], [2]), weights=np.array([2**26 + 4.0, 1000.0]))
D2 = mbi.Dataset({"a": np.array([0, 1])}, mbi.Domain(["a"], [2]), weights=np.array([2**26 + 5.0, 1000.0]))
N, EPS, DELTA = 300, 1.0, 1e-5
_generate = common.generate_synthetic_data
common.generate_synthetic_data = lambda model, rng, **k: _generate(model, rng, **{**k, "rows": 1000})
mech = dpsynth.calibrate(dpsynth.discrete_mechanisms.DiscreteConfig(
    mechanism=dpsynth.discrete_mechanisms.IndependentConfig(pgm_iters=1), one_way_budget_fraction=1.0),
    None, epsilon=EPS, delta=DELTA)

rng = np.random.default_rng(0)
hits = {}
for name, data in (("D", D), ("D'", D2)):
  hits[name] = 0
  for _ in range(N):
    [m] = [m for m in mech(rng, data).measurements if m.clique == ("a",)]
    y = float(np.asarray(m.noisy_measurement)[0])
    hits[name] += y >= 2**26 + 4
  print(f"{name}: last released count {y:.1f}, stddev {float(m.stddev):.3f}")

p, p2 = hits["D"] / N, hits["D'"] / N
print(f"P_D[E] = {p:.3f}, P_D'[E] = {p2:.3f}; ({EPS}, {DELTA})-DP allows P_D'[E] <= e^eps * P_D[E] + delta = "
      f"{math.exp(EPS) * p + DELTA:.3f}")

This prints:

D: last released count 67108858.2, stddev 3.731
D': last released count 67108873.0, stddev 3.731
P_D[E] = 0.130, P_D'[E] = 0.863; (1.0, 1e-05)-DP allows P_D'[E] <= e^eps * P_D[E] + delta = 0.353
Lenguaje dominante
Python
Estrellas
32
Forks
13
Sin PR fusionados en 30 d

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de google/dpsynth

Todos los issues de google/dpsynth

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.