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

オープン
  • 何か問題がありますか？
#290 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
48/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
活発
技術スタック
numpy, python
領域
backend, databases, security

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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
主要言語
Python
スター
32
フォーク
13
30日以内にマージされた PR はありません

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

google/dpsynth のほかの issue

google/dpsynth の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。