論文の概要: Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries

• arxiv url: http://arxiv.org/abs/2403.00028v2
• Date: Wed, 17 Apr 2024 23:59:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-19 14:09:37.681670
• Title: Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
• Title（参考訳）: 連続観察およびオンライン閾値クエリにおける差分プライバシーのための下位境界
• Authors: Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer,
• Abstract要約: 我々は、$Omegaleft(minn,log Tright)$の新しい下限を示す。 また、我々の低い境界は"オンラインしきい値問題"にまで拡張され、そこでは、多くの"量子クエリ"をプライベートに答えることが目標であることも示しています。
• 参考スコア（独自算出の注目度）: 31.339322747660635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the most basic problems for studying the "price of privacy over time" is the so called private counter problem, introduced by Dwork et al. (2010) and Chan et al. (2010). In this problem, we aim to track the number of events that occur over time, while hiding the existence of every single event. More specifically, in every time step $t\in[T]$ we learn (in an online fashion) that $\Delta_t\geq 0$ new events have occurred, and must respond with an estimate $n_t\approx\sum_{j=1}^t \Delta_j$. The privacy requirement is that all of the outputs together, across all time steps, satisfy event level differential privacy. The main question here is how our error needs to depend on the total number of time steps $T$ and the total number of events $n$. Dwork et al. (2015) showed an upper bound of $O\left(\log(T)+\log^2(n)\right)$, and Henzinger et al. (2023) showed a lower bound of $\Omega\left(\min\{\log n, \log T\}\right)$. We show a new lower bound of $\Omega\left(\min\{n,\log T\}\right)$, which is tight w.r.t. the dependence on $T$, and is tight in the sparse case where $\log^2 n=O(\log T)$. Our lower bound has the following implications: $\bullet$ We show that our lower bound extends to the "online thresholds problem", where the goal is to privately answer many "quantile queries" when these queries are presented one-by-one. This resolves an open question of Bun et al. (2017). $\bullet$ Our lower bound implies, for the first time, a separation between the number of mistakes obtainable by a private online learner and a non-private online learner. This partially resolves a COLT'22 open question published by Sanyal and Ramponi. $\bullet$ Our lower bound also yields the first separation between the standard model of private online learning and a recently proposed relaxed variant of it, called private online prediction.
• Abstract（参考訳）: 時とともにプライバシーの価格」を研究するための最も基本的な問題の1つは、Dwork et al (2010) と Chan et al (2010) によって導入されたいわゆるプライベートカウンター問題である。 この問題では,各イベントの存在を隠蔽しながら,時間とともに発生するイベントの数を追跡することを目的としている。 より具体的に言えば、ステップ $t\in[T]$ では、(オンラインの方法で) $\Delta_t\geq 0$ 新たなイベントが発生し、見積もり $n_t\approx\sum_{j=1}^t \Delta_j$ で応答しなければなりません。 プライバシ要件は、すべてのアウトプットが、すべての時間ステップにわたって、イベントレベルの差分プライバシを満たすことです。 ここでの最大の疑問は、エラーが時間ステップの総数$T$とイベントの総数$n$に依存する必要があるかということです。 Dwork et al (2015) は$O\left(\log(T)+\log^2(n)\right)$ の上限を示し、Hnzinger et al (2023) は$Omega\left(\min\{\log n, \log T\right)$ の上限を示した。 我々は、$\Omega\left(\min\{n,\log T\right)$という新しい下界を示し、これは$T$への依存が強く、$\log^2 n=O(\log T)$のスパースケースでは厳密である。 $\bullet$ 私たちは、下位境界が"オンラインしきい値問題"にまで拡張していることを示します。 これは Bun et al (2017) の公開問題を解決する。 $\bullet$ 我々の下限は、初めて、プライベートオンライン学習者と非プライベートオンライン学習者によって得られる誤りの数とを分離することを意味します。 これは、Sanyal と Ramponi が公表した COLT'22 のオープンな質問を部分的に解決する。 $\bullet$ 我々の下限は、プライベートオンライン学習の標準モデルと、最近提案された「プライベートオンライン予測」と呼ばれる緩和版との、最初の分離をもたらす。

関連論文リスト

• Continual Counting with Gradual Privacy Expiration [15.87191465142231]
  提案アルゴリズムは,大規模なプライバシー有効期限関数に対して,O(log(T)/epsilon)$の加算誤差を実現する。 我々の経験的評価は、自然ベースラインアルゴリズムよりも大きな値の$d$に対する経験的プライバシ損失が著しく小さく、徐々に増加するプライバシー損失を達成していることを示している。
  論文  参考訳（メタデータ） (2024-06-06T07:20:16Z)
• On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective [8.104151304193216]
  我々は、差分的プライベート(DP)オンライン学習アルゴリズムに対して、より低いバウンダリを提供する。 我々の研究は、DP-オンライン学習の下位境界の設定に向けた最初の成果である。
  論文  参考訳（メタデータ） (2024-02-26T17:49:37Z)
• The Sample Complexity of Online Contract Design [120.9833763323407]
  オンライン環境での隠れアクションの主エージェント問題について検討する。 各ラウンドにおいて、主席は、各結果に基づいてエージェントへの支払いを指定する契約を投稿する。 エージェントは、自身のユーティリティを最大化する戦略的な行動選択を行うが、プリンシパルによって直接観察できない。
  論文  参考訳（メタデータ） (2022-11-10T17:59:42Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  プライバシー制約下でのオンライン分類の問題点を考察する。 この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。 学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
  論文  参考訳（メタデータ） (2021-06-25T09:08:33Z)
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
  本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。 差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。 同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
  論文  参考訳（メタデータ） (2021-02-16T02:48:16Z)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。 一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
  論文  参考訳（メタデータ） (2020-12-16T17:58:45Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• Private Query Release Assisted by Public Data [96.6174729958211]
  本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
  論文  参考訳（メタデータ） (2020-04-23T02:46:37Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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