論文の概要: Constant matters: Fine-grained Complexity of Differentially Private
Continual Observation Using Completely Bounded Norms
- arxiv url: http://arxiv.org/abs/2202.11205v1
- Date: Wed, 23 Feb 2022 11:50:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-24 16:31:57.904831
- Title: Constant matters: Fine-grained Complexity of Differentially Private
Continual Observation Using Completely Bounded Norms
- Title（参考訳）: 定数問題:完全有界ノルムを用いた微分プライベート連続観測のきめ細かい複雑さ
- Authors: Monika Henzinger and Jalaj Upadhyay
- Abstract要約: 連続観測モデルにおける平均化とカウントのための差分プライベートアルゴリズムに対するきめ細かい誤差境界について検討する。
行列 $W$ に対して、cb ノルムは [ |W|_mathsfcb = max_Q left frac|Q bullet W||Q| right, ] と定義される。
- 参考スコア（独自算出の注目度）: 19.56959549209676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study fine-grained error bounds for differentially private algorithms for
averaging and counting in the continual observation model. For this, we use the
completely bounded spectral norm (cb norm) from operator algebra. For a matrix
$W$, its cb norm is defined as
\[
\|{W}\|_{\mathsf{cb}} = \max_{Q} \left\{ \frac{\|{Q \bullet W}\|}{\|{Q}\|}
\right\},
\]
where $Q \bullet W$ denotes the Schur product and $\|{\cdot}\|$ denotes the
spectral norm. We bound the cb norm of two fundamental matrices studied in
differential privacy under the continual observation model: the counting matrix
$M_{\mathsf{counting}}$ and the averaging matrix $M_{\mathsf{average}}$. For
$M_{\mathsf{counting}}$, we give lower and upper bound whose additive gap is $1
+ \frac{1}{\pi}$. Our factorization also has two desirable properties
sufficient for streaming setting: the factorization contains of
lower-triangular matrices and the number of distinct entries in the
factorization is exactly $T$. This allows us to compute the factorization on
the fly while requiring the curator to store a $T$-dimensional vector. For
$M_{\mathsf{average}}$, we show an additive gap between the lower and upper
bound of $\approx 0.64$.
- Abstract（参考訳）: 連続観測モデルにおける平均化とカウントのための差分プライベートアルゴリズムに対するきめ細かい誤差境界について検討する。
これに対し、作用素代数から完全に有界なスペクトルノルム(cbノルム)を用いる。
行列 $W$ に対して、その cb ノルムは \[ \|{W}\|_{\mathsf{cb}} = \max_{Q} \left\{ \frac{\|{Q \bullet W}\||{Q}\|} \right\}, \] と定義される。
我々は、連続観察モデルの下で微分プライバシーで研究された2つの基本行列の cb ノルムを定めている: カウント行列 $M_{\mathsf{counting}}$ と平均行列 $M_{\mathsf{average}}$ である。
M_{\mathsf{counting}}$に対して、加法ギャップが 1 + \frac{1}{\pi}$ である下限と上限を与える。
我々の因子化はストリーミング設定に十分な2つの望ましい性質を持つ: 因子化は低三角形行列を含み、因子化の異なる成分の数は正確に$T$である。
これにより、キュレーターに$t$次元のベクトルを保存させながら、フライで因子化を計算することができます。
M_{\mathsf{average}}$ の場合、$\approx 0.64$ の下限と上限の間の付加的なギャップを示す。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - A Unifying Framework for Differentially Private Sums under Continual
Observation [20.432568247732206]
本研究では,連続観測下での差分プライベート崩壊和の維持問題について検討する。
十分に滑らかな角関数に対して,この問題に対する統一的枠組みと効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-18T05:04:11Z) - Differential Privacy for Clustering Under Continual Observation [5.220940151628734]
我々は、点の挿入と削除の両方を行う$mathbbRd$のデータセットをプライベートにクラスタリングする問題を考える。
連続観測において、$k$-meansの目的に対して、$varepsilon$-differentially private clustering 機構を提供する。
論文 参考訳（メタデータ） (2023-07-07T07:23:56Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Almost Tight Error Bounds on Differentially Private Continual Counting [11.549143183739577]
プライベートフェデレーション学習の最初の大規模展開は、継続リリースモデルにおける差分プライベートカウントをサブルーチンとして利用する。
連続カウントの標準的なメカニズムはバイナリメカニズムである。
そこで本研究では,その平均二乗誤差が両立最適であり,二乗メカニズムの誤差よりも小さい因子が10であることを示す。
論文 参考訳（メタデータ） (2022-11-09T16:35:42Z) - Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation [22.51165277694864]
本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。
LSAは$d$次元線形系の近似解を計算するために用いられる。
論文 参考訳（メタデータ） (2022-07-10T14:36:04Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Tight High Probability Bounds for Linear Stochastic Approximation with
Fixed Stepsize [41.38162218102825]
本稿では,線形近似 (LSA) アルゴリズムの漸近的解析を行う。
我々は、より弱い条件下での LSA の性能に高い確率境界を導出する:$(bf A_n, bf b_n): n in mathbbN*$。
bf A_n: n in mathbbN*$ {\displaystyle \mathbbN*=} の列について追加の仮定なしでは、我々の結論は改善できないことを示す。
論文 参考訳（メタデータ） (2021-06-02T16:10:37Z) - High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。
最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
論文 参考訳（メタデータ） (2021-02-15T13:24:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。