論文の概要: Almost Tight Error Bounds on Differentially Private Continual Counting
- arxiv url: http://arxiv.org/abs/2211.05006v2
- Date: Mon, 5 Feb 2024 13:00:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 07:19:00.910192
- Title: Almost Tight Error Bounds on Differentially Private Continual Counting
- Title（参考訳）: 個人別連続数におけるほぼタイトな誤差境界
- Authors: Monika Henzinger and Jalaj Upadhyay and Sarvagya Upadhyay
- Abstract要約: プライベートフェデレーション学習の最初の大規模展開は、継続リリースモデルにおける差分プライベートカウントをサブルーチンとして利用する。
連続カウントの標準的なメカニズムはバイナリメカニズムである。
そこで本研究では,その平均二乗誤差が両立最適であり,二乗メカニズムの誤差よりも小さい因子が10であることを示す。
- 参考スコア（独自算出の注目度）: 11.549143183739577
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The first large-scale deployment of private federated learning uses
differentially private counting in the continual release model as a subroutine
(Google AI blog titled "Federated Learning with Formal Differential Privacy
Guarantees"). In this case, a concrete bound on the error is very relevant to
reduce the privacy parameter. The standard mechanism for continual counting is
the binary mechanism. We present a novel mechanism and show that its mean
squared error is both asymptotically optimal and a factor 10 smaller than the
error of the binary mechanism. We also show that the constants in our analysis
are almost tight by giving non-asymptotic lower and upper bounds that differ
only in the constants of lower-order terms. Our algorithm is a matrix mechanism
for the counting matrix and takes constant time per release. We also use our
explicit factorization of the counting matrix to give an upper bound on the
excess risk of the private learning algorithm of Denisov et al. (NeurIPS 2022).
Our lower bound for any continual counting mechanism is the first tight lower
bound on continual counting under approximate differential privacy. It is
achieved using a new lower bound on a certain factorization norm, denoted by
$\gamma_F(\cdot)$, in terms of the singular values of the matrix. In
particular, we show that for any complex matrix, $A \in \mathbb{C}^{m \times
n}$, \[ \gamma_F(A) \geq \frac{1}{\sqrt{m}}\|A\|_1, \] where $\|\cdot \|$
denotes the Schatten-1 norm.
We believe this technique will be useful in proving lower bounds for a larger
class of linear queries. To illustrate the power of this technique, we show the
first lower bound on the mean squared error for answering parity queries.
- Abstract（参考訳）: プライベートフェデレーション学習の最初の大規模展開では、継続リリースモデルにおける差分プライベートカウントをサブルーチンとして使用している(“Federated Learning with Formal Differential Privacy Guarantees”と題されたGoogle AIブログ)。
この場合、エラーの具体的なバウンドは、プライバシパラメータを減らすために非常に重要になります。
連続カウントの標準的なメカニズムはバイナリメカニズムである。
本稿では,その平均二乗誤差が漸近的に最適であり,二乗メカニズムの誤差よりも小さい因子10であることを示す。
また, 本解析の定数は, 下級項の定数でのみ異なる非漸近的下限と上限を与えることにより, ほぼタイトであることを示した。
本アルゴリズムは計数行列の行列機構であり,リリース毎に一定時間を要する。
また,デニソフらの私的学習アルゴリズム(NeurIPS 2022)の過剰なリスクに上限を与えるために,算数行列の明示的な因子化も行っている。
連続数え上げ機構に対する我々の下限は、近似微分プライバシーの下での連続数え上げに関する最初の厳密な下限である。
これは、行列の特異値の観点から、$\gamma_F(\cdot)$ で表されるある分解ノルム上の新しい下界を用いて達成される。
特に、任意の複素行列に対して、$A \in \mathbb{C}^{m \times n}$, \[ \gamma_F(A) \geq \frac{1}{\sqrt{m}}\|A\|_1, \] ここで、$\|\cdot \|$はシャッテン-1ノルムを表す。
このテクニックは、より大きな線形クエリのクラスに対する下限を証明するのに役立つと思います。
この手法のパワーを説明するために、パリティクエリに応答する平均二乗誤差の第1下位境界を示す。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。
本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
論文 参考訳（メタデータ） (2023-10-02T19:59:39Z) - A Unifying Framework for Differentially Private Sums under Continual
Observation [20.432568247732206]
本研究では,連続観測下での差分プライベート崩壊和の維持問題について検討する。
十分に滑らかな角関数に対して,この問題に対する統一的枠組みと効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-18T05:04:11Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Majorization-minimization for Sparse Nonnegative Matrix Factorization
with the $\beta$-divergence [2.3787352248749376]
他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。
標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。
我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
論文 参考訳（メタデータ） (2022-07-13T16:09:29Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - New Lower Bounds for Private Estimation and a Generalized Fingerprinting
Lemma [10.176795938619417]
統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。
フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
論文 参考訳（メタデータ） (2022-05-17T17:55:10Z) - Constant matters: Fine-grained Complexity of Differentially Private
Continual Observation [10.624505781812385]
連続的な観測をカウントするための差分プライベートアルゴリズムに対するきめ細かい誤差境界について検討する。
我々は連続観察下で様々な問題に対して具体的な誤差境界を初めて与えている。
論文 参考訳（メタデータ） (2022-02-23T11:50:20Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。