論文の概要: Private Continual Counting of Unbounded Streams

• arxiv url: http://arxiv.org/abs/2506.15018v1
• Date: Tue, 17 Jun 2025 23:09:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-19 19:35:51.503644
• Title: Private Continual Counting of Unbounded Streams
• Title（参考訳）: 非有界流のプライベート連続計数
• Authors: Ben Jacobsen, Kassem Fawaz,
• Abstract要約: 入力サイズ$n$が予め分かっていないような非有界な環境では、差分プライベートな連続数え上げの問題について検討する。 一般的な2倍のトリックを使用すると、$n$の知識は避けられるが、最適でないエラーと非滑らかなエラーにつながる。 先行研究で研究された関数 $frac1sqrt1-z$ の対数摂動に基づく新しい行列分解を導入する。
• 参考スコア（独自算出の注目度）: 11.941250828872189
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of differentially private continual counting in the unbounded setting where the input size $n$ is not known in advance. Current state-of-the-art algorithms based on optimal instantiations of the matrix mechanism cannot be directly applied here because their privacy guarantees only hold when key parameters are tuned to $n$. Using the common `doubling trick' avoids knowledge of $n$ but leads to suboptimal and non-smooth error. We solve this problem by introducing novel matrix factorizations based on logarithmic perturbations of the function $\frac{1}{\sqrt{1-z}}$ studied in prior works, which may be of independent interest. The resulting algorithm has smooth error, and for any $\alpha > 0$ and $t\leq n$ it is able to privately estimate the sum of the first $t$ data points with $O(\log^{2+2\alpha}(t))$ variance. It requires $O(t)$ space and amortized $O(\log t)$ time per round, compared to $O(\log(n)\log(t))$ variance, $O(n)$ space and $O(n \log n)$ pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. (SODA 2023). Empirically, we find that our algorithm's performance is also comparable to theirs in absolute terms: our variance is less than $1.5\times$ theirs for $t$ as large as $2^{24}$.
• Abstract（参考訳）: 入力サイズ$n$が予め分かっていないような非有界な環境では、差分プライベートな連続数え上げの問題について検討する。 行列機構の最適インスタンス化に基づく現在の最先端アルゴリズムは、鍵パラメータが$n$に調整された場合にのみ保持されるプライバシーを保証するため、ここで直接適用することはできない。 一般的な‘doubling trick’を使用すると$n$の知識は避けられるが、最適でないエラーと非滑らかなエラーにつながる。 この問題は、関数 $\frac{1}{\sqrt{1-z}}$ の対数摂動に基づく新しい行列分解を導入することで解決される。 結果のアルゴリズムはスムーズな誤差を持ち、任意の$\alpha > 0$と$t\leq n$に対して、$O(\log^{2+2\alpha}(t))$分散で最初の$t$のデータポイントの和をプライベートに見積もることができる。 ラウンドごとに$O(t)$空間と償却$O(\log t)$時間を必要とするが、$O(\log(n)\log(t))$ variance, $O(n)$ space and $O(n \log n)$ pre-processing time for the almost-optimal bounded-input algorithm of Henzinger et al (SODA 2023) である。 経験的に、我々のアルゴリズムの性能は絶対的な意味でも彼らのものと同等である:我々の分散は、$1.5\times$ theirs for $t$ as $2^{24}$である。

関連論文リスト

• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。 本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。 ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
  論文  参考訳（メタデータ） (2025-05-29T17:21:20Z)
• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  我々は、ErdHos-R'enyiランダムグラフのエッジ密度を強く推定する問題を、$G(n, dcirc/n)$で検討する。 我々のアルゴリズムは2乗の総和階層に基づいている。
  論文  参考訳（メタデータ） (2025-03-05T21:45:17Z)
• Differentially Private Clustering in Data Streams [65.78882209673885]
  オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。 我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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