論文の概要: Private Alternating Least Squares: Practical Private Matrix Completion
with Tighter Rates
- arxiv url: http://arxiv.org/abs/2107.09802v1
- Date: Tue, 20 Jul 2021 23:19:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-22 14:20:00.106046
- Title: Private Alternating Least Squares: Practical Private Matrix Completion
with Tighter Rates
- Title(参考訳): 自家用リアストスクエア:タイターレートによる実用的プライベートマトリックスコンパートメント
- Authors: Steve Chien, Prateek Jain, Walid Krichene, Steffen Rendle, Shuang
Song, Abhradeep Thakurta, Li Zhang
- Abstract要約: ユーザレベルのプライバシの下で、差分的プライベート(DP)行列補完の問題について検討する。
本稿では,Alternating-Least-Squares (ALS) 方式の差分型を設計する。
- 参考スコア(独自算出の注目度): 34.023599653814415
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of differentially private (DP) matrix completion under
user-level privacy. We design a joint differentially private variant of the
popular Alternating-Least-Squares (ALS) method that achieves: i) (nearly)
optimal sample complexity for matrix completion (in terms of number of items,
users), and ii) the best known privacy/utility trade-off both theoretically, as
well as on benchmark data sets. In particular, we provide the first global
convergence analysis of ALS with noise introduced to ensure DP, and show that,
in comparison to the best known alternative (the Private Frank-Wolfe algorithm
by Jain et al. (2018)), our error bounds scale significantly better with
respect to the number of items and users, which is critical in practical
problems. Extensive validation on standard benchmarks demonstrate that the
algorithm, in combination with carefully designed sampling procedures, is
significantly more accurate than existing techniques, thus promising to be the
first practical DP embedding model.
- Abstract(参考訳): ユーザレベルのプライバシー下での差分プライベート(DP)行列補完の問題について検討する。
i) 行列補完のための最適なサンプル複雑性(アイテム数、ユーザ数、およびii) 理論的には、最もよく知られているプライバシと有効性の両方のトレードオフ ベンチマークデータセット である。
特に, dp を保証するために導入された雑音をals に導入した最初の大域収束解析を行い, もっともよく知られた代替法 (jain らによる private frank-wolfe アルゴリズム) と比較した。
(2018)では,実際の問題において重要な項目数やユーザ数に対して,エラー境界のスケールが大幅に向上した。
標準ベンチマークの大規模な検証は、注意深く設計されたサンプリング手順と組み合わせて、アルゴリズムが既存の手法よりもはるかに正確であることを示し、最初の実用的なDP埋め込みモデルとなることを約束する。
関連論文リスト
- Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文 参考訳(メタデータ) (2024-05-28T19:02:30Z) - How Private are DP-SGD Implementations? [61.19794019914523]
2種類のバッチサンプリングを使用する場合、プライバシ分析の間に大きなギャップがあることが示される。
その結果,2種類のバッチサンプリングでは,プライバシ分析の間に大きなギャップがあることが判明した。
論文 参考訳(メタデータ) (2024-03-26T13:02:43Z) - Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
非プライベートなデータ依存前処理アルゴリズムによって生じる追加のプライバシーコストを評価するための一般的なフレームワークを提案する。
当社のフレームワークは,2つの新しい技術的概念を活用することにより,全体的なプライバシー保証の上限を確立する。
論文 参考訳(メタデータ) (2024-03-19T17:54:49Z) - Adaptive Differentially Quantized Subspace Perturbation (ADQSP): A Unified Framework for Privacy-Preserving Distributed Average Consensus [6.364764301218972]
本稿では適応微分量子化部分空間(ADQSP)という一般手法を提案する。
本研究では,単一の量子化パラメータを変化させることで,提案手法がSMPC型の性能とDP型性能に異なることを示す。
この結果から,従来の分散信号処理ツールを暗号保証に活用する可能性が示唆された。
論文 参考訳(メタデータ) (2023-12-13T07:52:16Z) - User-level Differentially Private Stochastic Convex Optimization:
Efficient Algorithms with Optimal Rates [16.958088684785668]
我々は,実行時において凸関数と強凸関数の両方に対して最適なレートを求める,ユーザレベルのDP-SCOの新しいアルゴリズムを開発した。
我々のアルゴリズムは、時間内に非滑らかな関数に対して最適な速度を得る最初の方法である。
論文 参考訳(メタデータ) (2023-11-07T08:26:51Z) - Practical Privacy-Preserving Gaussian Process Regression via Secret
Sharing [23.80837224347696]
本稿では秘密共有(SS)に基づくプライバシー保護型GPR手法を提案する。
コンフュージョン補正(confusion-correction)というアイデアを通じて,新たなSSベースの指数演算を導出し,Cholesky分解に基づくSSベースの行列逆変換アルゴリズムを構築する。
実験結果から,データプライバシ保護の前提として,提案手法が妥当な精度と効率を達成できることが示唆された。
論文 参考訳(メタデータ) (2023-06-26T08:17:51Z) - Robustness Implies Privacy in Statistical Estimation [16.061651295129302]
本研究では,高次元統計学における敵のプライバシーと差分プライバシーの関係について検討する。
プライバシーから堅牢性への最初のブラックボックスの削減は、最適なトレードオフを伴うプライベートな推定器を生み出すことができる。
また, アルゴリズムは, ほぼ最適に崩壊したサンプルに対して頑健である。
論文 参考訳(メタデータ) (2022-12-09T18:07:30Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳(メタデータ) (2022-05-05T06:43:46Z) - Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
本稿では,分散動的安全スクリーニング(DDSS)手法を提案し,共有メモリアーキテクチャと分散メモリアーキテクチャにそれぞれ適用する。
提案手法は, 線形収束率を低次複雑度で達成し, 有限個の繰り返しにおいてほとんどすべての不活性な特徴をほぼ確実に除去できることを示す。
論文 参考訳(メタデータ) (2022-04-23T02:45:55Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Private Stochastic Convex Optimization: Efficient Algorithms for
Non-smooth Objectives [28.99826590351627]
本稿では,プライバシパラメータがサンプル数に比例する場合に,一階降下を実現する雑音ミラーに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-22T03:03:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。