論文の概要: Tighter Generalization Bounds for Iterative Differentially Private
Learning Algorithms
- arxiv url: http://arxiv.org/abs/2007.09371v2
- Date: Fri, 7 Aug 2020 04:41:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 05:24:18.326707
- Title: Tighter Generalization Bounds for Iterative Differentially Private
Learning Algorithms
- Title（参考訳）: 反復差分学習アルゴリズムの高次一般化境界
- Authors: Fengxiang He, Bohan Wang, Dacheng Tao
- Abstract要約: 本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。
我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。
次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
- 参考スコア（独自算出の注目度）: 95.73230376153872
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the relationship between generalization and privacy
preservation in iterative learning algorithms by two sequential steps. We first
establish an alignment between generalization and privacy preservation for any
learning algorithm. We prove that $(\varepsilon, \delta)$-differential privacy
implies an on-average generalization bound for multi-database learning
algorithms which further leads to a high-probability bound for any learning
algorithm. This high-probability bound also implies a PAC-learnable guarantee
for differentially private learning algorithms. We then investigate how the
iterative nature shared by most learning algorithms influence privacy
preservation and further generalization. Three composition theorems are
proposed to approximate the differential privacy of any iterative algorithm
through the differential privacy of its every iteration. By integrating the
above two steps, we eventually deliver generalization bounds for iterative
learning algorithms, which suggest one can simultaneously enhance privacy
preservation and generalization. Our results are strictly tighter than the
existing works. Particularly, our generalization bounds do not rely on the
model size which is prohibitively large in deep learning. This sheds light to
understanding the generalizability of deep learning. These results apply to a
wide spectrum of learning algorithms. In this paper, we apply them to
stochastic gradient Langevin dynamics and agnostic federated learning as
examples.
- Abstract（参考訳）: 本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。
まず,学習アルゴリズムの一般化とプライバシ保護の整合性を確立する。
我々は、$(\varepsilon, \delta)$-differential privacyは、任意の学習アルゴリズムに対して高い確率を持つマルチデータベース学習アルゴリズムに対して、平均的な一般化を意味することを証明している。
この高い確率境界はまた、微分プライベート学習アルゴリズムのPAC学習保証を意味する。
次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
3つの合成定理は、任意の反復アルゴリズムの微分プライバシーを各反復の微分プライバシーによって近似するために提案される。
上記の2つのステップを統合することで、最終的には反復学習アルゴリズムの一般化境界が提供され、プライバシの保存と一般化が同時に向上することを示唆します。
私たちの結果は既存の作品より厳格です。
特に、我々の一般化境界は、ディープラーニングにおいて禁止的に大きいモデルサイズに依存しない。
これは深層学習の一般化可能性を理解するための光である。
これらの結果は幅広い学習アルゴリズムに適用できる。
本稿では,確率勾配ランゲヴィン力学と非認識フェデレーション学習を例として応用する。
関連論文リスト
- 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) - PAC-Bayesian Learning of Optimization Algorithms [6.624726878647541]
PAC-Bayes理論を学習最適化の設定に適用する。
証明可能な一般化保証(PAC-bounds)と高収束確率と高収束速度との間の明示的なトレードオフを持つ最適化アルゴリズムを学習する。
この結果は指数族に基づく一般の非有界損失関数に対してPAC-Bayes境界に依存する。
論文 参考訳（メタデータ） (2022-10-20T09:16:36Z) - Stochastic Differentially Private and Fair Learning [7.971065005161566]
我々は、収束することが保証されるフェアラーニングのための最初の微分プライベートアルゴリズムを提供する。
われわれのフレームワークは、人口格差や均等化オッズなど、さまざまな公平さを許容できるほど柔軟である。
本アルゴリズムは,複数の(非バイナリ)機密属性を持つ非バイナリ分類タスクに適用可能である。
論文 参考訳（メタデータ） (2022-10-17T06:54:57Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Uniform-PAC Bounds for Reinforcement Learning with Linear Function
Approximation [92.3161051419884]
線形関数近似を用いた強化学習について検討する。
既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。
我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
論文 参考訳（メタデータ） (2021-06-22T08:48:56Z) - Of Moments and Matching: Trade-offs and Treatments in Imitation Learning [26.121994149869767]
我々は、モーメントマッチングのレンズを通して、過去の模倣学習アルゴリズムの大規模なファミリの統一ビューを提供する。
学習者と専門家の行動の相違を考慮することで、政策パフォーマンスの限界を導出することができる。
AdVILとAdRILという2つの新しいアルゴリズムテンプレートを、強力な保証、シンプルな実装、競争力のある実証的パフォーマンスで導出します。
論文 参考訳（メタデータ） (2021-03-04T18:57:11Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Privacy Analysis of Online Learning Algorithms via Contraction
Coefficients [5.333582981327498]
差分プライバシー保証は、$f$-divergencesの強いデータ処理の不等式から導かれる収縮係数の直接適用によって決定できることを示す。
また、このフレームワークは、トレーニングデータセットをワンパスで実装できるバッチ学習アルゴリズムに調整可能であることも示しています。
論文 参考訳（メタデータ） (2020-12-20T22:02:15Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Efficient, Noise-Tolerant, and Private Learning via Boosting [15.62988331732388]
本研究では,大規模ハーフスペースのための耐雑音性とプライベートなPAC学習者を構築する方法について述べる。
この最初の境界は、プライバシからPAC学習者を取得するための一般的な方法論を示している。
2つ目の境界は、大きな有理半空間の微分プライベート学習において最もよく知られたサンプルの複雑さに適合する標準手法を使用する。
論文 参考訳（メタデータ） (2020-02-04T03:16:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。