論文の概要: Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD

• arxiv url: http://arxiv.org/abs/2505.12128v1
• Date: Sat, 17 May 2025 19:41:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:11.052952
• Title: Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD
• Title（参考訳）: 正方形根への回帰:マルチエポック差分SGDにおける行列分解誤差の最適境界
• Authors: Nikita P. Kalinin, Ryan McKenna, Jalaj Upadhyay, Christoph H. Lampert,
• Abstract要約: 逆相関行列上にバンド構造を付加した新しい明示的因数分解法,Banded Inverse Square Root (BISR) を導入する。 BISRは、上界と下界をマッチングすることで、アナル最適誤差を達成する。
• 参考スコア（独自算出の注目度）: 21.92418810749819
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Matrix factorization mechanisms for differentially private training have emerged as a promising approach to improve model utility under privacy constraints. In practical settings, models are typically trained over multiple epochs, requiring matrix factorizations that account for repeated participation. Existing theoretical upper and lower bounds on multi-epoch factorization error leave a significant gap. In this work, we introduce a new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix. This factorization enables us to derive an explicit and tight characterization of the multi-epoch error. We further prove that BISR achieves asymptotically optimal error by matching the upper and lower bounds. Empirically, BISR performs on par with state-of-the-art factorization methods, while being simpler to implement, computationally efficient, and easier to analyze.
• Abstract（参考訳）: 差分的プライベートトレーニングのための行列分解機構は、プライバシー制約下でモデルユーティリティを改善するための有望なアプローチとして現れている。 現実的な設定では、モデルは典型的には複数のエポック上で訓練され、繰り返しの参加を考慮に入れた行列因数分解を必要とする。 既存の理論上界と下界の多重位相分解誤差は、大きなギャップを残している。 本研究では,逆相関行列上にバンド構造を課す,新しい明示的因数分解手法であるBanded Inverse Square Root (BISR)を導入する。 この因子化により、マルチエポック誤差の明示的かつ厳密な特徴を導出できる。 さらに,上境界と下限を一致させることで,漸近的最適誤差が得られることを証明した。 実証的には、BISRは最先端の分解法と同等に動作し、実装が簡単で、計算効率が良く、分析も容易である。

関連論文リスト

• Induced Covariance for Causal Discovery in Linear Sparse Structures [55.2480439325792]
  因果モデルでは、観測データから変数間の因果関係を解き明かそうとしている。 本稿では,変数が線形に疎結合な関係を示す設定のための新しい因果探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-02T04:01:38Z)
• Fitting Multilevel Factor Models [41.38783926370621]
  我々は,多段階因子モデルに適した期待最大化アルゴリズムの,新しい高速実装を開発する。 可逆PSD MLR行列の逆もまた、因子の間隔が同じMLR行列であることを示す。 線形時間と空間複素量を持つ拡張行列のコレスキー分解を計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-18T15:39:12Z)
• Banded Square Root Matrix Factorization for Differentially Private Model Training [3.6371628922281305]
  本稿では,この計算ボトルネックを克服する新しい行列分解手法であるBSRを提案する。 標準行列平方根の特性を利用することにより、BSRは大規模問題も効率的に扱うことができる。 我々の数値実験により、BSRを用いて訓練されたモデルは、その計算オーバーヘッドを完全に回避しつつ、最良の既存手法と同等に機能することを示した。
  論文  参考訳（メタデータ） (2024-05-22T15:47:35Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
  本稿では,複合最適化問題のクラスについて述べる。 合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
  論文  参考訳（メタデータ） (2023-03-29T16:15:34Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  閉形式解によって最適化できる新しいサロゲートを開発する。 そこで我々は, 上向きの相関関係を利用して, 適応的相関学習モデルを構築した。
  論文  参考訳（メタデータ） (2022-03-04T08:50:50Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  ROC曲線 (AUC) の下の領域は、不均衡学習やレコメンダシステムといった問題に対するよく知られたランキング基準である。 本稿では,マルチクラスAUCメトリクスを最適化することで,多クラススコアリング関数を学習する問題について検討する。
  論文  参考訳（メタデータ） (2021-07-28T05:18:10Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)

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

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