Jaminan Wasserstein Berdimensi Intrinsik untuk Ukuran Sintetis Privat

Ukuran sintetis privat diferensial ε berbasis PrivTree mencapai galat 1-Wasserstein optimal minimax pada dimensi ambien, dengan laju yang membaik yang dikendalikan oleh dimensi intrinsik berskala hingga.

Yiyun He· 2026· DOI 10.48550/arXiv.2609.17624

Masalah inti

Makalah ini mempelajari masalah merilis ukuran sintetis yang mengaproksimasi dataset arbitrer berisi n titik di kubus satuan [0, 1]^{d} sekaligus memenuhi privasi diferensial ε . Objek utamanya adalah ukuran sintetis \overset{μ}{^} yang jarak 1-Wasserstein-nya terhadap ukuran empiris μ_{n} = \frac{1}{n} i = 1 \sum n δ_{x_{i}} kecil secara ekspektasi. Penulis mengadopsi model data kasus terburuk: tidak ada asumsi pengambilan sampel, tidak ada distribusi populasi, dan tidak ada struktur manifold berdimensi rendah yang dipraanggapkan. Ini menyimpang dari sebagian besar literatur data sintetis privat, yang sering mengasumsikan pengambilan sampel i.i.d. dari suatu distribusi atau struktur berdimensi rendah yang harus dipulihkan. Pertanyaan utamanya adalah apakah seseorang dapat memperoleh laju Wasserstein optimal minimax dalam konteks yang sepenuhnya adversaria ini, dan apakah dimensi ambien d dapat digantikan oleh dimensi intrinsik yang lebih kecil dan bergantung pada data. Makalah ini menjawab kedua pertanyaan tersebut secara afirmatif. Konstruksinya sederhana: terapkan algoritma PrivTree yang sudah ada untuk membentuk partisi biner adaptif pada kubus, lalu rilis massa

Inovasi

Makalah ini menetapkan tiga hasil utama. Pertama, untuk setiap d \geq 2 dan setiap dataset berisi n titik di [0, 1]^{d}, galat 1-Wasserstein yang diharapkan dari ukuran sintetis memenuhi E [W_{1} (\overset{μ}{^}, μ_{n})] = O_{d} ((ε n)^{- 1/ d}), di mana notasi O_{d} menyembunyikan faktor polilogaritmik dalam n dan ε serta konstanta yang bergantung pada d . Ini cocok dengan batas bawah minimax yang diketahui Ω ((ε n)^{- 1/ d}) hingga faktor logaritmik, menunjukkan bahwa konstruksinya optimal dalam model data kasus terburuk. Kedua, untuk d \geq 3 dan 2 < s \leq d, jika dataset memiliki covering number paling banyak A r^{- s} pada rentang skala hingga yang relevan r, maka galat yang diharapkan membaik menjadi E [W_{1} (\overset{μ}{^}, μ_{n})] = O_{d, s} ((ε n)^{- 1/ s}) . Dengan demikian lajunya bergantung pada dimensi intrinsik berskala hingga s alih-alih dimensi ambien d, tanpa memerlukan pemulihan manifold berdimensi rendah. Kondisi covering number adalah asumsi ringan yang bergantung pada data yang dapat berlaku bahkan untuk him

Makalah ini mempelajari masalah merilis ukuran sintetis yang mengaproksimasi dataset arbitrer berisi n titik di kubus satuan [0, 1]^{d} sekaligus memenuhi privasi diferensial ε . Objek utamanya adalah ukuran sintetis \overset{μ}{^} yang jarak 1-Wasserstein-nya terhadap ukuran empiris μ_{n} = \frac{1}{n} i = 1 \sum n δ_{x_{i}} kecil secara ekspektasi. Penulis mengadopsi model data kasus terburuk: tidak ada asumsi pengambilan sampel, tidak ada distribusi populasi, dan tidak ada struktur manifold berdimensi rendah yang dipraanggapkan. Ini menyimpang dari sebagian besar literatur data sintetis privat, yang sering mengasumsikan pengambilan sampel i.i.d. dari suatu distribusi atau struktur berdimensi rendah yang harus dipulihkan. Pertanyaan utamanya adalah apakah seseorang dapat memperoleh laju Wasserstein optimal minimax dalam konteks yang sepenuhnya adversaria ini, dan apakah dimensi ambien d dapat digantikan oleh dimensi intrinsik yang lebih kecil dan bergantung pada data. Makalah ini menjawab kedua pertanyaan tersebut secara afirmatif. Konstruksinya sederhana: terapkan algoritma PrivTree yang sudah ada untuk membentuk partisi biner adaptif pada kubus, lalu rilis massa setiap daun secara privat. Analisisnya merupakan kontribusi utama, menetapkan batas atas yang cocok dengan batas bawah yang diketahui hingga faktor logaritmik dan memperluasnya ke rezim dimensi intrinsik berskala hingga.

Mekanismenya adalah prosedur dua tahap. Pertama, PrivTree (algoritma partisi hierarkis privat diferensial) dijalankan pada dataset untuk menghasilkan partisi biner adaptif P dari [0, 1]^{d} . PrivTree secara rekursif membelah sel ketika jumlah titik dalam suatu sel melebihi ambang yang bergantung pada parameter privasi ε dan kedalaman, sehingga memusatkan resolusi di tempat data padat. Kedua, massa daun dirilis secara privat. Untuk setiap daun L \in P, hitungan n_{L} = i = 1 \sum n 1 {x_{i} \in L} dihitung dan diganggu dengan derau Laplace untuk memperoleh \tilde{n}_{L}, dan ukuran sintetis didefinisikan sebagai

Mengapa penting

Hasil-hasil ini menempatkan mekanisme yang diusulkan di garis depan pembangkitan data sintetis privat. Laju optimal minimax (ε n)^{- 1/ d} untuk d \geq 2 adalah jaminan yang kuat dalam model kasus terburuk, dan peningkatan menjadi (ε n)^{- 1/ s} di bawah kondisi dimensi intrinsik berskala hingga sangat menarik karena tidak memerlukan estimasi atau pemulihan manifold. Kondisi covering number lebih lemah daripada mengasumsikan manifold: ia hanya mensyaratkan bahwa data dapat ditutupi oleh sejumlah bola tertentu pada setiap skala, yang merupakan gagasan umum dalam geometri metrik dan dapat diverifikasi secara empiris. Teknik penggeseran adalah kontribusi teknis yang mungkin menarik secara independen untuk algoritma privat berbasis partisi lainnya. Salah satu batasannya adalah hasil-hasilnya dinyatakan untuk jarak 1-Wasserstein; perluasan ke jarak p -Wasserstein untuk p > 1 tidak dibahas. Batasan lainnya adalah konstanta dalam notasi O mungkin bergantung pada d dan s dengan cara yang tidak sepenuhnya eksplisit, meskipun teknik penggeseran meredam ketergantungan eksponensial pada d . Makalah ini tidak menyediakan evaluasi empiris, sehingga kinerja praktis mekanisme pada dataset nyata masih perlu diteliti. Meskipun demikian, jaminan teoretisnya merupakan langkah signifikan menuju pemahaman batas fundamental data sintetis privat di dimensi tinggi, dan hal ini menunjukkan bahwa dimensi intrinsik dapat dimanfaatkan tanpa pemulihan manifold yang eksplisit. Karya ini juga terhubung dengan literatur yang lebih luas tentang ukuran privat dan transportasi optimal, dan dapat menginspirasi penelitian lebih lanjut tentang skema partisi adaptif yang secara otomatis menyesuaikan diri dengan dimensi intrinsik data.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…