論文の概要: Continual Counting with Gradual Privacy Expiration

• arxiv url: http://arxiv.org/abs/2406.03802v1
• Date: Thu, 6 Jun 2024 07:20:16 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 16:09:36.676812
• Title: Continual Counting with Gradual Privacy Expiration
• Title（参考訳）: Gradual Privacy Expiration による連続カウント
• Authors: Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, Jalaj Upadhyay,
• Abstract要約: 提案アルゴリズムは,大規模なプライバシー有効期限関数に対して,O(log(T)/epsilon)$の加算誤差を実現する。 我々の経験的評価は、自然ベースラインアルゴリズムよりも大きな値の$d$に対する経験的プライバシ損失が著しく小さく、徐々に増加するプライバシー損失を達成していることを示している。
• 参考スコア（独自算出の注目度）: 15.87191465142231
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time $t$ the privacy loss guaranteed for a data item seen at time $(t-d)$ is $\epsilon g(d)$, where $g$ is a monotonically non-decreasing function. We study the fundamental $\textit{continual (binary) counting}$ problem where each data item consists of a bit, and the algorithm needs to output at each time step the sum of all the bits streamed so far. For a stream of length $T$ and privacy $\textit{without}$ expiration continual counting is possible with maximum (over all time steps) additive error $O(\log^2(T)/\varepsilon)$ and the best known lower bound is $\Omega(\log(T)/\varepsilon)$; closing this gap is a challenging open problem. We show that the situation is very different for privacy with gradual expiration by giving upper and lower bounds for a large set of expiration functions $g$. Specifically, our algorithm achieves an additive error of $ O(\log(T)/\epsilon)$ for a large set of privacy expiration functions. We also give a lower bound that shows that if $C$ is the additive error of any $\epsilon$-DP algorithm for this problem, then the product of $C$ and the privacy expiration function after $2C$ steps must be $\Omega(\log(T)/\epsilon)$. Our algorithm matches this lower bound as its additive error is $O(\log(T)/\epsilon)$, even when $g(2C) = O(1)$. Our empirical evaluation shows that we achieve a slowly growing privacy loss with significantly smaller empirical privacy loss for large values of $d$ than a natural baseline algorithm.
• Abstract（参考訳）: 段階的有効期限付き差分プライバシーは、データアイテムがストリームに到着し、所定の時間に$t$が保証されるデータアイテムのプライバシー損失を$(t-d)$ is $\epsilon g(d)$でモデル化する。 基本$\textit{continual (binary) counting}$ problem where each data item are a bit, and the algorithm need to output each time step the sum of all bits streamed。 長さ$T$とプライバシー$\textit{without}$ expiration continual counting is possible with maximum (over all time steps) additive error $O(\log^2(T)/\varepsilon)$ and the most known lower bound is $\Omega(\log(T)/\varepsilon)$; このギャップを閉じることは難しいオープンな問題である。 大規模な有効期限関数セットの上下境界を$g$で付与することで、段階的有効期限付きプライバシでは状況が極めて異なることを示す。 具体的には、大規模なプライバシー有効期限関数に対して、O(\log(T)/\epsilon)$の加算誤差を達成する。 また、もし$C$がこの問題に対する$\epsilon$-DPアルゴリズムの加算誤差であるなら、$C$の製品と$C$の後のプライバシー有効期限関数は$\Omega(\log(T)/\epsilon$でなければならない。 我々のアルゴリズムはこの下限と一致し、加法誤差は$O(\log(T)/\epsilon)$であり、g(2C) = O(1)$である。 我々の経験的評価は、自然ベースラインアルゴリズムよりも大きな値の$d$に対する経験的プライバシ損失が著しく小さく、徐々に増加するプライバシー損失を達成していることを示している。

関連論文リスト

• Differentially Private Approximate Pattern Matching [0.0]
  我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。 目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。 1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
  論文  参考訳（メタデータ） (2023-11-13T15:53:45Z)
• Online Robust Mean Estimation [37.746091744197656]
  オンライン環境における高次元ロバスト平均推定問題について検討する。 このモデルでは、オンラインロバスト平均推定の主な2つの結果が証明されている。
  論文  参考訳（メタデータ） (2023-10-24T15:28:43Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)
• Differentially Private Online Submodular Maximization [16.422215672356167]
  差分プライバシフィード(DP)を用いた基準制約下でのオンラインサブモジュラー関数の問題点について考察する。 共通有限基底集合上の$T$サブモジュラー関数のストリームがオンラインに届き、各時点において、決定者は関数を観察する前に$U$のほとんどの$k$要素を選択する必要がある。 意思決定者は、選択された集合で評価された関数に等しい報酬を得るとともに、期待の低い後悔を実現する一連の集合を学習することを目的とする。
  論文  参考訳（メタデータ） (2020-10-24T07:23:30Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
  データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。 本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。 我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
  論文  参考訳（メタデータ） (2020-08-15T11:06:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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