論文の概要: Locally Private Histograms in All Privacy Regimes

• arxiv url: http://arxiv.org/abs/2408.04888v2
• Date: Wed, 4 Sep 2024 07:12:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-06 19:18:56.668545
• Title: Locally Private Histograms in All Privacy Regimes
• Title（参考訳）: 全プライバシーレジームにおける局所的プライベートヒストグラム
• Authors: Clément L. Canonne, Abigail Gentle,
• Abstract要約: 中～下級のプライバシ体制において,局所的な私的ヒストグラムと,それに関連する分布学習課題について検討する。 我々は,従来のアルゴリズムと精度を一致させるが,メッセージや通信の複雑さが著しく向上した,局所的な微分プライバシーモデルにおけるヒストグラムのプロトコルを得る。 局所的な私的ヒストグラム問題において, 基板間の境界を改良した新しい解析結果から, 理論的知見が得られた。
• 参考スコア（独自算出の注目度）: 14.453502159917525
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Frequency estimation, a.k.a. histograms, is a workhorse of data analysis, and as such has been thoroughly studied under differentially privacy. In particular, computing histograms in the \emph{local} model of privacy has been the focus of a fruitful recent line of work, and various algorithms have been proposed, achieving the order-optimal $\ell_\infty$ error in the high-privacy (small $\varepsilon$) regime while balancing other considerations such as time- and communication-efficiency. However, to the best of our knowledge, the picture is much less clear when it comes to the medium- or low-privacy regime (large $\varepsilon$), despite its increased relevance in practice. In this paper, we investigate locally private histograms, and the very related distribution learning task, in this medium-to-low privacy regime, and establish near-tight (and somewhat unexpected) bounds on the $\ell_\infty$ error achievable. As a direct corollary of our results, we obtain a protocol for histograms in the \emph{shuffle} model of differential privacy, with accuracy matching previous algorithms but significantly better message and communication complexity. Our theoretical findings emerge from a novel analysis, which appears to improve bounds across the board for the locally private histogram problem. We back our theoretical findings by an empirical comparison of existing algorithms in all privacy regimes, to assess their typical performance and behaviour beyond the worst-case setting.
• Abstract（参考訳）: 周波数推定、すなわちヒストグラムは、データ分析のワークホースであり、そのように差分プライバシーの下で徹底的に研究されている。 特に、プライバシのemph{local}モデルにおけるヒストグラムの計算は、実りある最近の作業の焦点であり、時間や通信効率といった他の考慮事項のバランスを保ちながら、高いプライバシ(小さな$\varepsilon$)体制でオーダー最適化の$\ell_\infty$エラーを達成する様々なアルゴリズムが提案されている。 しかし、私たちの知る限りでは、実際には関連性が高まっているにも関わらず、中小または低小の政権(最大$\varepsilon$)に関しては、この絵は明らかになっていない。 本稿では、この中～下層のプライバシー体制において、局所的な私的ヒストグラムと、それに関連する分布学習タスクを調査し、$\ell_\infty$エラーを達成可能なほぼ28(そして多少の予期せぬ)境界を確立する。 実験結果の直接的な要約として,従来のアルゴリズムと精度が一致するが,メッセージや通信の複雑さが著しく向上する,差分プライバシーの「emph{shuffle}」モデルにおけるヒストグラムのプロトコルを得る。 局所的な私的ヒストグラム問題において, 基板間の境界を改良した新しい解析結果から, 理論的知見が得られた。 我々は、すべてのプライバシー体制における既存のアルゴリズムを実証的に比較し、最悪の状況を超えてそれらの典型的なパフォーマンスと振る舞いを評価することによって、我々の理論的な知見を裏付ける。

関連論文リスト

• A Unifying Privacy Analysis Framework for Unknown Domain Algorithms in Differential Privacy [1.5773159234875098]
  我々は、未知のドメイン上でヒストグラムをリリースするための、既存の微分プライベートアルゴリズムのいくつかを再検討する。 未知の領域でヒストグラムをリリースする主な実用的利点は、アルゴリズムが欠落したラベルを埋める必要がないことである。 いくつかの既存アルゴリズムのプライバシー分析のための統一的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-17T05:47:33Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。 本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-07-13T17:09:25Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging [20.39986955578245]
  ローカルディファレンシャルプライバシ(LDP)の緩和であるペアワイズネットワークディファレンシャルプライバシを導入する。 我々は、局所勾配降下ステップとゴシップ平均化を交互に交互に行う、微分プライベートな分散最適化アルゴリズムを導出する。 我々のアルゴリズムは,グラフ内のノード間距離の関数として,プライバシー保証を増幅することを示す。
  論文  参考訳（メタデータ） (2022-06-10T13:32:35Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。 ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。 これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
  論文  参考訳（メタデータ） (2022-06-06T13:49:37Z)
• Differentially Private Learning Needs Hidden State (Or Much Faster Convergence) [9.429448411561541]
  差分的にプライベートな学習は、厳密な拘束力を持って、隠れた状態のプライバシ分析や、高速な収束を必要とすることを示す。 私たちの収束するプライバシー分析は、差異のあるプライベートな学習が、厳密な拘束力を持って、隠れた状態のプライバシ分析や、高速な収束を必要とすることを示している。
  論文  参考訳（メタデータ） (2022-03-10T13:31:08Z)
• 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)
• Breaking the Communication-Privacy-Accuracy Trilemma [19.399122892615573]
  分散学習における2つの大きな課題は、ローカルサンプルのプライバシを保持し、それらを中央サーバに効率的に伝達することである。 我々は、最適なプライバシーと通信効率を同時に達成する新しい符号化・復号機構を開発する。
  論文  参考訳（メタデータ） (2020-07-22T22:43:01Z)

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

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