論文の概要: Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms

• arxiv url: http://arxiv.org/abs/2602.12209v1
• Date: Thu, 12 Feb 2026 17:49:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-13 21:07:25.965033
• Title: Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
• Title（参考訳）: 秘密を守るには良い記憶が必要だ:プライベートアルゴリズムのためのスペースローバウンド
• Authors: Alessandro Epasto, Xin Lyu, Pasin Manurangsi,
• Abstract要約: 本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。 本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。 このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
• 参考スコア（独自算出の注目度）: 67.94856074923571
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the computational cost of differential privacy in terms of memory efficiency. While the trade-off between accuracy and differential privacy is well-understood, the inherent cost of privacy regarding memory use remains largely unexplored. This paper establishes for the first time an unconditional space lower bound for user-level differential privacy by introducing a novel proof technique based on a multi-player communication game. Central to our approach, this game formally links the hardness of low-memory private algorithms to the necessity of ``contribution capping'' -- tracking and limiting the users who disproportionately impact the dataset. We demonstrate that winning this communication game requires transmitting information proportional to the number of over-active users, which translates directly to memory lower bounds. We apply this framework, as an example, to the fundamental problem of estimating the number of distinct elements in a stream and we prove that any private algorithm requires almost $\widetildeΩ(T^{1/3})$ space to achieve certain error rates in a promise variant of the problem. This resolves an open problem in the literature (by Jain et al. NeurIPS 2023 and Cummings et al. ICML 2025) and establishes the first exponential separation between the space complexity of private algorithms and their non-private $\widetilde{O}(1)$ counterparts for a natural statistical estimation task. Furthermore, we show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
• Abstract（参考訳）: メモリ効率の観点から差分プライバシーの計算コストについて検討する。 精度と差分プライバシーのトレードオフはよく理解されているが、メモリ使用に関するプライバシーの固有のコストは、まだ明らかにされていない。 本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を導入することにより,ユーザレベルの差分プライバシーに対する非条件空間の低いバウンダリを初めて確立する。 私たちのアプローチでは、このゲームは、低メモリのプライベートアルゴリズムの難しさと‘コントリビューションキャッピング’の必要性を公式に関連付けています。 我々は,このコミュニケーションゲームに勝つためには,メモリの低い領域に直接変換する過剰なユーザ数に比例した情報を送信する必要があることを実証する。 この枠組みを例として、ストリーム内の異なる要素の数を推定する根本的な問題に適用し、任意のプライベートアルゴリズムが問題の約束変種におけるある種のエラー率を達成するために、ほぼ$\widetildeΩ(T^{1/3})$空間を必要とすることを証明する。 このことは、(Jain et al NeurIPS 2023 と Cummings et al ICML 2025 による)文学におけるオープンな問題を解決し、自然統計推定タスクのために、プライベートアルゴリズムの空間複雑性とそれらの非プライベートな$\widetilde{O}(1)$との最初の指数的分離を確立する。 さらに、この通信理論手法は、プライベートな中央値、量子化値、最大選択値に対する下位境界を導出し、幅広い問題のクラスに一般化することを示す。

関連論文リスト

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• Optimal Private Discrete Distribution Estimation with One-bit Communication [63.413106413939836]
  1ビット通信制約を伴う個別分布推定問題を考える。 1ビット通信制約下での最悪のトレードオフの1次を特徴付ける。 これらの結果は,1ビット通信制約下でのプライバシユーティリティトレードオフの最適依存性を示す。
  論文  参考訳（メタデータ） (2023-10-17T05:21:19Z)
• Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise [7.110450972801578]
  プライベート分散マルチパーティ乗算の問題点を考察する。 Shamirの秘密共有コーディング戦略が、分散計算における完全な情報理論プライバシを実現することは、十分に確立されている。
  論文  参考訳（メタデータ） (2023-09-28T02:13:13Z)
• Privacy Amplification via Shuffling: Unified, Simplified, and Tightened [20.10078781197001]
  シングルメッセージとマルチメッセージのシャッフルプロトコルの両方において、プライバシーを増幅するための包括的なフレームワークを提案する。 我々の理論的な結果は、特に極端確率設計を持つ局所確率化器に対して、我々のフレームワークがより厳密な境界を提供することを示している。 私たちのバウンダリは、非常に効率的な$tildeO(n)$アルゴリズムで、$n=108$ユーザに対して10$秒未満で、数値的にプライバシを増幅します。
  論文  参考訳（メタデータ） (2023-04-11T06:27:25Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。 差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。 アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
  論文  参考訳（メタデータ） (2023-02-11T14:45:31Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。 本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-07-13T17:09:25Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Robust and Differentially Private Mean Estimation [40.323756738056616]
  異なるプライバシーは、米国国勢調査から商用デバイスで収集されたデータまで、さまざまなアプリケーションで標準要件として浮上しています。 このようなデータベースの数は、複数のソースからのデータからなり、それらすべてが信頼できるわけではない。 これにより、既存のプライベート分析は、腐敗したデータを注入する敵による攻撃に弱い。
  論文  参考訳（メタデータ） (2021-02-18T05:02:49Z)
• Breaking the Communication-Privacy-Accuracy Trilemma [19.399122892615573]
  分散学習における2つの大きな課題は、ローカルサンプルのプライバシを保持し、それらを中央サーバに効率的に伝達することである。 我々は、最適なプライバシーと通信効率を同時に達成する新しい符号化・復号機構を開発する。
  論文  参考訳（メタデータ） (2020-07-22T22:43:01Z)

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

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