論文の概要: Streaming Private Continual Counting via Binning
- arxiv url: http://arxiv.org/abs/2412.07093v1
- Date: Tue, 10 Dec 2024 01:21:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-11 14:37:28.793672
- Title: Streaming Private Continual Counting via Binning
- Title(参考訳): バインディングによるプライベート連続カウントのストリーミング
- Authors: Joel Daniel Andersson, Rasmus Pagh,
- Abstract要約: 我々は、$textitbinning$を介して低空間における分解機構を近似する簡単な方法を提案する。
空間利用が極端に少ない場合でも、最適分解機構の性能は密に一致し、時には上回ることができることを実証的に示す。
- 参考スコア(独自算出の注目度): 11.72102598708538
- License:
- Abstract: In differential privacy, $\textit{continual observation}$ refers to problems in which we wish to continuously release a function of a dataset that is revealed one element at a time. The challenge is to maintain a good approximation while keeping the combined output over all time steps differentially private. In the special case of $\textit{continual counting}$ we seek to approximate a sum of binary input elements. This problem has received considerable attention lately, in part due to its relevance in implementations of differentially private stochastic gradient descent. $\textit{Factorization mechanisms}$ are the leading approach to continual counting, but the best such mechanisms do not work well in $\textit{streaming}$ settings since they require space proportional to the size of the input. In this paper, we present a simple approach to approximating factorization mechanisms in low space via $\textit{binning}$, where adjacent matrix entries with similar values are changed to be identical in such a way that a matrix-vector product can be maintained in sublinear space. Our approach has provable sublinear space guarantees for a class of lower triangular matrices whose entries are monotonically decreasing away from the diagonal. We show empirically that even with very low space usage we are able to closely match, and sometimes surpass, the performance of asymptotically optimal factorization mechanisms. Recently, and independently of our work, Dvijotham et al. have also suggested an approach to implementing factorization mechanisms in a streaming setting. Their work differs from ours in several respects: It only addresses factorization into $\textit{Toeplitz}$ matrices, only considers $\textit{maximum}$ error, and uses a different technique based on rational function approximation that seems less versatile than our binning approach.
- Abstract(参考訳): 差分プライバシーでは、$\textit{continual observed}$は、一度に1つの要素が明らかになったデータセットの機能を継続的にリリースしたいという問題を指す。
課題は、すべての時間ステップで組み合わせたアウトプットを個別に保ちながら、良好な近似を維持することです。
特別な場合、$\textit{continual counting}$ はバイナリ入力要素の和を近似しようとします。
この問題は近年、微分プライベートな確率勾配勾配の導出に関係していることから、かなりの注目を集めている。
$\textit{Factorization mechanism}$は連続カウントの主要なアプローチであるが、入力のサイズに比例した空間を必要とするため、$\textit{streaming}$設定ではうまく機能しない。
本稿では, 行列ベクトル積を線形空間で維持できるような方法で, 類似値を持つ隣接行列エントリを同一に変化させることにより, 低空間における分解機構を近似する簡単な手法を提案する。
提案手法は, 対角線から単調に成分が減少する下方三角形行列のクラスに対して, 証明可能な部分線型空間を保証する。
空間利用が極めて少ない場合でも、漸近的に最適な因子分解機構の性能は密に一致し、時には上回ることができることを実証的に示す。
近年,Dvijothamらは,ストリーミング環境における因子分解機構の実装へのアプローチを提案している。
因数分解を$\textit{Toeplitz}$行列にのみ対応し、$\textit{maximum}$エラーのみを考慮し、有理関数近似に基づく別の手法を用いており、これは我々の双対アプローチよりも多様ではない。
関連論文リスト
- Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity [3.9657575162895196]
曖昧な部分空間の埋め込みは、ランダムな$mtimes n$ matrix $Pi$で、その部分空間内のすべてのベクトルのノルムを1pmepsilon$ factorで保存する。
最適次元が $m=Theta(d/epsilon2)$ で、最適間隔が $tilde O (1/epsilon)$ のとき、非零エントリは $Pi$ である。
論文 参考訳(メタデータ) (2024-11-13T16:58:51Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳(メタデータ) (2024-06-07T12:07:16Z) - Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [16.046186753149]
最近のLarge Language Models(LLM)におけるトランスフォーマーの成功の鍵は自己認識メカニズムである
我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。
トランスフォーマーモデルにおけるアテンション計算を加速するための新しいパラダイムが、より長いコンテキストへのアプリケーションを支援することを願っています。
論文 参考訳(メタデータ) (2024-05-08T17:11:38Z) - A Novel and Optimal Spectral Method for Permutation Synchronization [8.517406772939292]
置換同期はコンピュータ科学において重要な問題であり、多くのコンピュータビジョンタスクの重要なステップを構成する。
本稿では,新しい,統計的に最適なスペクトルアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-21T17:43:26Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳(メタデータ) (2023-02-03T03:19:14Z) - Majorization-minimization for Sparse Nonnegative Matrix Factorization
with the $\beta$-divergence [2.3787352248749376]
他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。
標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。
我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
論文 参考訳(メタデータ) (2022-07-13T16:09:29Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳(メタデータ) (2022-06-17T09:24:41Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-30T19:17:35Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - On the Expressive Power of Self-Attention Matrices [41.72598286888797]
固定自己アテンションモジュールは入力に応じて任意のスパースパターンを近似することができることを示す。
行列を近似するために適応的な入力と固定された自己アテンションパラメータを求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-07T16:30:28Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-01-19T04:24:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。