論文の概要: Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization

• arxiv url: http://arxiv.org/abs/2601.02257v1
• Date: Mon, 05 Jan 2026 16:36:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:23.282288
• Title: Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization
• Title（参考訳）: マトリックスファクトリゼーションによる完全動的流路におけるプライベート連続心力推定の精度向上
• Authors: Joel Daniel Andersson, Palak Jain, Satchit Sivakumar,
• Abstract要約: 完全動的連続観測モデルにおける微分プライベート統計量について検討する。 筆者らのフレームワークは, 異なる要素をカウントし, 等級ヒストグラムを推定し, 三角形数を推定するためのバウンダリを改良したことを示す。
• 参考スコア（独自算出の注目度）: 6.895689879562656
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study differentially-private statistics in the fully dynamic continual observation model, where many updates can arrive at each time step and updates to a stream can involve both insertions and deletions of an item. Earlier work (e.g., Jain et al., NeurIPS 2023 for counting distinct elements; Raskhodnikova & Steiner, PODS 2025 for triangle counting with edge updates) reduced the respective cardinality estimation problem to continual counting on the difference stream associated with the true function values on the input stream. In such reductions, a change in the original stream can cause many changes in the difference stream, this poses a challenge for applying private continual counting algorithms to obtain optimal error bounds. We improve the accuracy of several such reductions by studying the associated $\ell_p$-sensitivity vectors of the resulting difference streams and isolating their properties. We demonstrate that our framework gives improved bounds for counting distinct elements, estimating degree histograms, and estimating triangle counts (under a slightly relaxed privacy model), thus offering a general approach to private continual cardinality estimation in streaming settings. Our improved accuracy stems from tight analysis of known factorization mechanisms for the counting matrix in this setting; the key technical challenge is arguing that one can use state-of-the-art factorizations for sensitivity vector sets with the properties we isolate. Empirically and analytically, we demonstrate that our improved error bounds offer a substantial improvement in accuracy for cardinality estimation problems over a large range of parameters.
• Abstract（参考訳）: 完全動的連続観測モデルでは,各時点に多くの更新が到着し,ストリームへの更新は項目の挿入と削除の両方を伴う可能性がある。 初期の研究(例: Jain et al , NeurIPS 2023, Raskhodnikova & Steiner, PODS 2025, エッジ更新を伴う三角形の計数)では、各濃度推定問題は入力ストリーム上の真の関数値に関連する差分ストリームの連続的な計数に還元された。 このような削減では、元のストリームの変更が差分ストリームに多くの変更をもたらす可能性があるため、プライベートな連続カウントアルゴリズムを適用して最適なエラー境界を得るという課題が生じる。 得られた差分ストリームの関連した$\ell_p$-sensitivityベクトルを解析し、それらの特性を分離することにより、そのような還元の精度を向上させる。 筆者らのフレームワークは、異なる要素をカウントし、等級ヒストグラムを推定し、三角形の数を推定する(やや緩和されたプライバシモデルの下で)ため、ストリーミング設定におけるプライベートな濃度推定に対する一般的なアプローチを提供する。 我々の改良された精度は、この設定における数え上げ行列の既知の因子化機構の厳密な解析に起因しており、重要な技術的課題は、我々が分離した性質を持つ感度ベクトル集合に対して、最先端の因子化を使うことができることである。 経験的かつ解析的に、改良された誤差境界が、幅広いパラメータに対する濃度推定問題の精度を大幅に向上することを示した。

関連論文リスト

• Revisiting Randomization in Greedy Model Search [16.15551706774035]
  特徴サブサンプリングによってランダム化される欲求前方選択推定器のアンサンブルを提案し,解析する。 計算効率を大幅に向上させる動的プログラミングに基づく新しい実装を設計する。 ランダム化アンサンブルが縮小と類似しているという一般的な信念とは対照的に、トレーニングエラーと自由度を同時に低減できることが示される。
  論文  参考訳（メタデータ） (2025-06-18T17:13:53Z)
• Semiparametric conformal prediction [79.6147286161434]
  ベクトル値の非整合性スコアの結合相関構造を考慮した共形予測セットを構築する。 スコアの累積分布関数(CDF)を柔軟に推定する。 提案手法は,現実の回帰問題に対して,所望のカバレッジと競争効率をもたらす。
  論文  参考訳（メタデータ） (2024-11-04T14:29:02Z)
• Enabling Uncertainty Estimation in Iterative Neural Networks [49.56171792062104]
  本研究では,アンサンブルのような手法よりもはるかに低い計算コストで最先端の見積もりを提供する不確実性推定手法を開発する。 航空画像における道路検出と2次元および3次元形状の空力特性の推定という2つの応用領域に組み込むことで,その実用的価値を実証する。
  論文  参考訳（メタデータ） (2024-03-25T13:06:31Z)
• Better Batch for Deep Probabilistic Time Series Forecasting [15.31488551912888]
  本稿では,確率的予測精度を高めるために,誤り自己相関を取り入れた新しいトレーニング手法を提案する。 本手法は,モデルトレーニングのためのD$連続時系列セグメントのコレクションとしてミニバッチを構築する。 各ミニバッチ上で時間変化の共分散行列を明示的に学習し、隣接する時間ステップ間の誤差相関を符号化する。
  論文  参考訳（メタデータ） (2023-05-26T15:36:59Z)
• Projective Integral Updates for High-Dimensional Variational Inference [0.0]
  変分推論は、完全な後部に立つパラメータの簡易分布を最適化することにより、予測の不確実性を改善することを目指している。 この研究は、任意の可能なログ密度を与えられた基底から関数の線形結合として表現できる場合に適用可能な変分推論のための固定点最適化を導入する。 QNVBのPyTorch実装は、競合する方法よりも訓練中のモデルの不確実性をよりよく制御できる。
  論文  参考訳（メタデータ） (2023-01-20T00:38:15Z)
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions [41.7567932118769]
  経験的リスク最小化アルゴリズムは、様々な推定や予測タスクで広く利用されている。 本稿では,コンベックスEMMの統計的精度に関する基礎的限界を推論のために初めて特徴づける。
  論文  参考訳（メタデータ） (2020-06-16T04:27:38Z)
• Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes [72.68201611113673]
  本稿では,情報理論の観点から,新しいオフライン変化点検出問題について検討する。 基礎となる事前および変更後分布の知識は分かっておらず、利用可能なトレーニングシーケンスからのみ学習できると仮定する。
  論文  参考訳（メタデータ） (2020-03-13T23:39:40Z)

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

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