論文の概要: Facility Location Problem under Local Differential Privacy without Super-set Assumption

• arxiv url: http://arxiv.org/abs/2506.15224v1
• Date: Wed, 18 Jun 2025 08:08:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-19 19:35:51.582537
• Title: Facility Location Problem under Local Differential Privacy without Super-set Assumption
• Title（参考訳）: スーパーセットを含まない地域差分プライバシー下における施設配置問題
• Authors: Kevin Pfisterer, Quentin Hillebrand, Vorapong Suppakitpaisarn,
• Abstract要約: 施設配置問題への適応を導入し、局所差分プライバシー(LDP)の枠組みの中で分析する。 このモデルでは、特定の場所でクライアントの存在のプライバシを確保する。 提案アルゴリズムは, 合成されたデータセットと実世界のデータセットの両方において, 直接的なアプローチよりも優れていることを示す実験結果を提供する。
• 参考スコア（独自算出の注目度）: 1.9749268648715583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce an adaptation of the facility location problem and analyze it within the framework of local differential privacy (LDP). Under this model, we ensure the privacy of client presence at specific locations. When n is the number of points, Gupta et al. established a lower bound of $\Omega(\sqrt{n})$ on the approximation ratio for any differentially private algorithm applied to the original facility location problem. As a result, subsequent works have adopted the super-set assumption, which may, however, compromise user privacy. We show that this lower bound does not apply to our adaptation by presenting an LDP algorithm that achieves a constant approximation ratio with a relatively small additive factor. Additionally, we provide experimental results demonstrating that our algorithm outperforms the straightforward approach on both synthetically generated and real-world datasets.
• Abstract（参考訳）: 本稿では,施設配置問題への適応を導入し,地域差分プライバシー(LDP)の枠組みの中で解析する。 このモデルでは、特定の場所でクライアントの存在のプライバシを確保する。 n が点数であるとき、Gupta et al は元の施設位置問題に適用された任意の微分プライベートアルゴリズムの近似比に対して $\Omega(\sqrt{n})$ という下界を確立した。 その結果、その後の研究はスーパーセットの仮定を採用しており、ユーザーのプライバシーを侵害する可能性がある。 この下限は, 相対的に小さい加算係数の近似比を一定とする LDP アルゴリズムを提示することによって, 適応には適用できないことを示す。 さらに,本アルゴリズムは,合成されたデータセットと実世界のデータセットの両方において,直接的なアプローチよりも優れていることを示す実験結果を提供する。

関連論文リスト

• Instance-Optimality for Private KL Distribution Estimation [41.35506763248454]
  未知の離散分布 $p$ over $d$ symbols, given $n$ i.i.d. sample from the distribution。 本稿では,差分プライバシー制約を伴わずに,一定要素までのインスタンス最適化を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-29T16:27:57Z)
• Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization [30.45012237666837]
  M$クライアントの分散環境でのDP-SCO(差分プライベート凸最適化)の問題点を考察する。 目的は,100万ドル規模のクライアントを対象とした協調作業を用いて,凸人口減少を最小限に抑えるアルゴリズムを設計することである。 我々は,新しい下位境界と分散DP-SCOの新しいアルゴリズムを用いて,一致した逆と達成可能性を求める。
  論文  参考訳（メタデータ） (2025-01-06T18:57:05Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• Dynamic Privacy Allocation for Locally Differentially Private Federated Learning with Composite Objectives [10.528569272279999]
  本稿では,強い凸性を持つが非滑らかな問題に対する差分プライベートなフェデレーション学習アルゴリズムを提案する。 提案アルゴリズムは、共有情報に人工ノイズを加えてプライバシーを確保するとともに、時間変化のノイズ分散を動的に割り当て、最適化誤差の上限を最小化する。 解析結果から,提案手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-08-02T13:30:33Z)
• Instance-Optimal Differentially Private Estimation [2.320417845168326]
  我々は,$epsilon$-differential privacyの対象となる局所最小収束推定値について検討した。 そこで本研究では,Canonneらの最近の最適プライベートテスタによる簡易仮説テストのための最適アルゴリズムが,局所最小推定アルゴリズムの設計を直接的に通知することを示した。
  論文  参考訳（メタデータ） (2022-10-28T01:08:01Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Private Domain Adaptation from a Public Source [48.83724068578305]
  我々は、公開ラベル付きデータを持つソースドメインから、未ラベル付きプライベートデータを持つターゲットドメインへの適応のための差分プライベート離散性に基づくアルゴリズムを設計する。 我々の解は、Frank-WolfeとMirror-Descentアルゴリズムのプライベートな変種に基づいている。
  論文  参考訳（メタデータ） (2022-08-12T06:52:55Z)
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging [20.39986955578245]
  ローカルディファレンシャルプライバシ(LDP)の緩和であるペアワイズネットワークディファレンシャルプライバシを導入する。 我々は、局所勾配降下ステップとゴシップ平均化を交互に交互に行う、微分プライベートな分散最適化アルゴリズムを導出する。 我々のアルゴリズムは,グラフ内のノード間距離の関数として,プライバシー保証を増幅することを示す。
  論文  参考訳（メタデータ） (2022-06-10T13:32:35Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。