論文の概要: A Unified Characterization of Private Learnability via Graph Theory
- arxiv url: http://arxiv.org/abs/2304.03996v3
- Date: Wed, 24 May 2023 19:42:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 20:26:47.382492
- Title: A Unified Characterization of Private Learnability via Graph Theory
- Title(参考訳): グラフ理論による個人学習可能性の統一的特徴付け
- Authors: Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff
- Abstract要約: 純粋かつ近似微分プライベート(DP)学習を特徴付ける統一的なフレームワークを提供する。
DP学習性の特徴を特徴づけるグラフ理論次元を同定する。
- 参考スコア(独自算出の注目度): 19.287925620134324
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We provide a unified framework for characterizing pure and approximate
differentially private (DP) learnabiliity. The framework uses the language of
graph theory: for a concept class $\mathcal{H}$, we define the contradiction
graph $G$ of $\mathcal{H}$. It vertices are realizable datasets, and two
datasets $S,S'$ are connected by an edge if they contradict each other (i.e.,
there is a point $x$ that is labeled differently in $S$ and $S'$). Our main
finding is that the combinatorial structure of $G$ is deeply related to
learning $\mathcal{H}$ under DP. Learning $\mathcal{H}$ under pure DP is
captured by the fractional clique number of $G$. Learning $\mathcal{H}$ under
approximate DP is captured by the clique number of $G$. Consequently, we
identify graph-theoretic dimensions that characterize DP learnability: the
clique dimension and fractional clique dimension. Along the way, we reveal
properties of the contradiction graph which may be of independent interest. We
also suggest several open questions and directions for future research.
- Abstract(参考訳): 純粋かつ近似微分プライベート(DP)学習を特徴付ける統一的なフレームワークを提供する。
このフレームワークはグラフ理論の言語を使用する: 概念クラス $\mathcal{H}$ に対して、矛盾グラフ $G$ of $\mathcal{H}$ を定義する。
it頂点は実現可能なデータセットであり、2つのデータセット$s,s'$は、互いに矛盾した場合、エッジによって接続される(すなわち、$s$と$s'$で異なるラベルが付けられたポイント$x$がある)。
主な発見は、$g$ の組合せ構造は dp の下で $\mathcal{h}$ の学習と深く関係していることである。
純粋な DP の下で $\mathcal{H}$ を学ぶことは、分数clique の$G$ で表される。
DP で $\mathcal{H}$ を学ぶことは、clique number of $G$ で表される。
その結果,dp学習性を特徴づけるグラフ理論的次元,すなわち,クランク次元と分数的クランク次元を同定した。
その過程で、独立興味を持つかもしれない矛盾グラフの特性を明らかにする。
今後の研究にはいくつかのオープンな質問や方向性も提案する。
関連論文リスト
- Non-Clashing Teaching Maps for Balls in Graphs [0.058520770038704165]
教示写像は、概念のペアがそれらの教示集合の和集合と一致しない場合、非クラッシングである。
関連する決定問題 sc B-NCTD$+$ for NCTD$+$ is NP-complete in split, co-bipartite and bipartite graphs。
論文 参考訳(メタデータ) (2023-09-06T10:02:58Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳(メタデータ) (2023-04-17T10:38:08Z) - Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
有向フィードバックグラフが帯域幅を持つ拡張について検討する。
グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。
我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2022-10-09T11:21:08Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳(メタデータ) (2022-10-06T06:49:48Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳(メタデータ) (2022-08-18T09:19:01Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳(メタデータ) (2022-02-22T04:14:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳(メタデータ) (2021-10-11T05:07:50Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳(メタデータ) (2021-06-03T07:22:48Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-10-25T18:12:50Z) - Block Model Guided Unsupervised Feature Selection [32.21728295212875]
リンクデータに対するグラフ駆動型教師なし特徴選択のための新しい手法を提案する。
まず、グラフ上にブロックモデルを構築し、次に特徴選択にブロックモデルを使用するという、新しいアプローチを取ります。
実験結果から,本手法は実世界の複数の公開データセット上での最先端の手法であることがわかった。
論文 参考訳(メタデータ) (2020-07-05T16:19:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。