論文の概要: A Unifying Framework for Differentially Private Sums under Continual Observation

• arxiv url: http://arxiv.org/abs/2307.08970v1
• Date: Tue, 18 Jul 2023 05:04:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-19 16:34:01.059292
• Title: A Unifying Framework for Differentially Private Sums under Continual Observation
• Title（参考訳）: 連続観測における個人差分和の統一化フレームワーク
• Authors: Monika Henzinger and Jalaj Upadhyay and Sarvagya Upadhyay
• Abstract要約: 本研究では,連続観測下での差分プライベート崩壊和の維持問題について検討する。 十分に滑らかな角関数に対して,この問題に対する統一的枠組みと効率的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 20.432568247732206
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for \emph{any sufficiently smooth} function. Our algorithm is the first differentially private algorithm that does not have a multiplicative error for polynomially-decaying weights. Our algorithm improves on all prior works on differentially private decaying sums under continual observation and recovers exactly the additive error for the special case of continual counting from Henzinger et al. (SODA 2023) as a corollary. Our algorithm is a variant of the factorization mechanism whose error depends on the $\gamma_2$ and $\gamma_F$ norm of the underlying matrix. We give a constructive proof for an almost exact upper bound on the $\gamma_2$ and $\gamma_F$ norm and an almost tight lower bound on the $\gamma_2$ norm for a large class of lower-triangular matrices. This is the first non-trivial lower bound for lower-triangular matrices whose non-zero entries are not all the same. It includes matrices for all continual decaying sums problems, resulting in an upper bound on the additive error of any differentially private decaying sums algorithm under continual observation. We also explore some implications of our result in discrepancy theory and operator algebra. Given the importance of the $\gamma_2$ norm in computer science and the extensive work in mathematics, we believe our result will have further applications.
• Abstract（参考訳）: 本研究では,連続観測下での差分プライベート崩壊和の維持問題について検討する。 この問題に対する統一フレームワークと効率的なアルゴリズムを 'emph{any enough smooth} 関数に対して与える。 我々のアルゴリズムは多項式分解重みに対する乗算誤差を持たない最初の微分プライベートアルゴリズムである。 本アルゴリズムは,連続観測下での微分プライベート減衰和に関するすべての先行研究を改善し,henzinger et al. (soda 2023) からの連続カウントの特別な場合の加法誤差を正確に回復する。 我々のアルゴリズムは、誤差が基底行列の$\gamma_2$と$\gamma_F$ノルムに依存する分解機構の変種である。 我々は、$\gamma_2$ および $\gamma_F$ ノルム上のほぼ正確な上界と、大域な三角形行列のクラスに対する $\gamma_2$ ノルム上のほぼ厳密な下界に対する構成的証明を与える。 これは、非零成分がすべて同じでない下三角行列に対する最初の非自明な下界である。 これはすべての連続的減衰和問題に対する行列を含み、連続的観測の下では任意の微分的減衰和アルゴリズムの加法誤差の上界となる。 我々はまた、不一致理論と作用素代数における結果のいくつかの意味についても検討する。 計算機科学における$\gamma_2$ノルムの重要性と数学における広範な研究を考えると、我々の結果はさらなる応用が期待できる。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond [8.604882842499212]
  任意の円錐多様体が与えられた線型部分空間と$mathbbFn$の交叉元を求める問題について検討する。 この問題は、多種多様な選択の下で、アルゴリズムの問題の豊富なファミリーを捉えている。 我々は,この問題を「典型的」部分空間に対して効率的に解くアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-12-07T18:45:33Z)
• Almost Tight Error Bounds on Differentially Private Continual Counting [11.549143183739577]
  プライベートフェデレーション学習の最初の大規模展開は、継続リリースモデルにおける差分プライベートカウントをサブルーチンとして利用する。 連続カウントの標準的なメカニズムはバイナリメカニズムである。 そこで本研究では,その平均二乗誤差が両立最適であり,二乗メカニズムの誤差よりも小さい因子が10であることを示す。
  論文  参考訳（メタデータ） (2022-11-09T16:35:42Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Majorization-minimization for Sparse Nonnegative Matrix Factorization with the $\beta$-divergence [2.3787352248749376]
  他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。 標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。 我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2022-07-13T16:09:29Z)
• Constant matters: Fine-grained Complexity of Differentially Private Continual Observation [10.624505781812385]
  連続的な観測をカウントするための差分プライベートアルゴリズムに対するきめ細かい誤差境界について検討する。 我々は連続観察下で様々な問題に対して具体的な誤差境界を初めて与えている。
  論文  参考訳（メタデータ） (2022-02-23T11:50:20Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)

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

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