論文の概要: A Unified Characterization of Private Learnability via Graph Theory
- arxiv url: http://arxiv.org/abs/2304.03996v2
- Date: Thu, 4 May 2023 12:12:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 18:41:21.157204
- 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学習性を特徴づけるグラフ理論的次元,すなわち,クランク次元と分数的クランク次元を同定した。
その過程で、独立興味を持つかもしれない矛盾グラフの特性を明らかにする。
今後の研究にはいくつかのオープンな質問や方向性も提案する。
関連論文リスト
- Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Non-Clashing Teaching Maps for Balls in Graphs [0.05356944479760104]
関連する決定問題 B-NCTD$+$ for NCTD$+$ is NP-complete in split, co-bipartite and bipartite graphs を示す。
また、ETHが失敗しない限り、B-NCTD$+$は、時間で22o(textvc)cdot nO(1)$、カーネルに2o(textvc)cdot nO(1)$を出力するカーネル化アルゴリズムを許可しない。
論文 参考訳（メタデータ） (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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。