論文の概要: Non-Clashing Teaching Maps for Balls in Graphs
- arxiv url: http://arxiv.org/abs/2309.02876v1
- Date: Wed, 6 Sep 2023 10:02:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-07 15:56:29.715883
- Title: Non-Clashing Teaching Maps for Balls in Graphs
- Title（参考訳）: グラフにおけるボールの非切断指導マップ
- Authors: J\'er\'emie Chalopin, Victor Chepoi, Fionn Mc Inerney, S\'ebastien
Ratel
- Abstract要約: 教示写像は、概念のペアがそれらの教示集合の和集合と一致しない場合、非クラッシングである。
関連する決定問題 sc B-NCTD$+$ for NCTD$+$ is NP-complete in split, co-bipartite and bipartite graphs。
- 参考スコア（独自算出の注目度）: 0.058520770038704165
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023]
introduced non-clashing teaching and showed it to be the most efficient machine
teaching model satisfying the benchmark for collusion-avoidance set by Goldman
and Mathias. A teaching map $T$ for a concept class $\cal{C}$ assigns a
(teaching) set $T(C)$ of examples to each concept $C \in \cal{C}$. A teaching
map is non-clashing if no pair of concepts are consistent with the union of
their teaching sets. The size of a non-clashing teaching map (NCTM) $T$ is the
maximum size of a $T(C)$, $C \in \cal{C}$. The non-clashing teaching dimension
NCTD$(\cal{C})$ of $\cal{C}$ is the minimum size of an NCTM for $\cal{C}$.
NCTM$^+$ and NCTD$^+(\cal{C})$ are defined analogously, except the teacher may
only use positive examples.
We study NCTMs and NCTM$^+$s for the concept class $\mathcal{B}(G)$
consisting of all balls of a graph $G$. We show that the associated decision
problem {\sc B-NCTD$^+$} for NCTD$^+$ is NP-complete in split, co-bipartite,
and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails,
{\sc B-NCTD$^+$} does not admit an algorithm running in time
$2^{2^{o(vc)}}\cdot n^{O(1)}$, nor a kernelization algorithm outputting a
kernel with $2^{o(vc)}$ vertices, where vc is the vertex cover number of $G$.
These are extremely rare results: it is only the second (fourth, resp.) problem
in NP to admit a double-exponential lower bound parameterized by vc (treewidth,
resp.), and only one of very few problems to admit an ETH-based conditional
lower bound on the number of vertices in a kernel. We complement these lower
bounds with matching upper bounds. For trees, interval graphs, cycles, and
trees of cycles, we derive NCTM$^+$s or NCTMs for $\mathcal{B}(G)$ of size
proportional to its VC-dimension. For Gromov-hyperbolic graphs, we design an
approximate NCTM$^+$ for $\mathcal{B}(G)$ of size 2.
- Abstract（参考訳）: 最近、カークパトリックら。
[ALT 2019]とFallatら。
[JMLR 2023]は非クラッシング教育を導入し,ゴールドマンとマティアスの共謀回避ベンチマークを満たす最も効率的な機械教育モデルであることを示した。
概念クラス $\cal{C}$ に対する教示写像 $T$ は、各概念 $C \in \cal{C}$ に対して (teaching) set $T(C)$ の例を割り当てる。
教示写像は、一対の概念が教示集合の結合と一致しない場合、非閉である。
non-clashing teaching map (nctm) $t$ のサイズは、$t(c)$, $c \in \cal{c}$ の最大サイズである。
非クラッシング教育次元 NCTD$(\cal{C})$ of $\cal{C}$ は、NCTMの$\cal{C}$ の最小サイズである。
NCTM$^+$ と NCTD$^+(\cal{C})$ は類似して定義されるが、教師は正の例のみを使用することができる。
グラフのすべての球からなる概念クラス $\mathcal{B}(G)$ に対して NCTM と NCTM$^+$s を研究する。
NCTD$^+$ に対する関連する決定問題 {\sc B-NCTD$^+$} は、分割、共分割、二分グラフにおいてNP完全であることを示す。
驚いたことに、ETHが失敗しない限り、 {\displaystyle {\sc B-NCTD$^+$} は、時間で走るアルゴリズムが $2^{2^{o(vc)}}\cdot n^{O(1)}$、カーネルに $2^{o(vc)}$ vertices を出力するカーネル化アルゴリズムも認めない。
これらは非常に稀な結果である: NP において vc (treewidth, resp.) によってパラメータ化される二重指数下界を許容するのは第2(第4、第4、第4)の問題であり、カーネル内の頂点数に ETH ベースの条件付き下界を許容する問題のうちの1つに過ぎない。
これらの下界と一致する上界を補完する。
木、インターバルグラフ、サイクルおよびサイクルのツリーに対して、VC次元に比例する大きさの$\mathcal{B}(G)$に対して NCTM$^+$s または NCTMs を導出する。
グロモフ-双曲グラフに対しては、近似NCTM$^+$ for $\mathcal{B}(G)$ of size 2 を設計する。
関連論文リスト
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - On character table of Clifford groups [0.0]
クリフォード群 $mathcalC_n$ for $n=1,2,3$ の文字表を構築する。
応用として、行列表現のテンソル積を効率的に分解することができる。
副生成物として、有限シンプレクティック群 $Sp(2n,2)$ を生成元と関係性の観点から提示する。
論文 参考訳（メタデータ） (2023-09-26T11:29:35Z) - A Unified Characterization of Private Learnability via Graph Theory [18.364498500697596]
純粋かつ近似微分プライベート(DP)学習性を特徴付ける統一的なフレームワークを提供する。
DP学習性の特徴を特徴づけるグラフ理論次元を同定する。
また、独立な興味を持つかもしれない矛盾グラフの性質も明らかにする。
論文 参考訳（メタデータ） (2023-04-08T12:25:08Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - 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) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。
これは高速多重極法について証明された最初の公式な制限である。
論文 参考訳（メタデータ） (2020-11-04T18:35:02Z) - Phase Transitions in Rate Distortion Theory and Deep Learning [5.145741425164946]
もし$mathcalS$をエンコードするために$mathcalO(R-s)$のエラーを達成できれば、$mathcalS$は$s$で圧縮できると言う。
ある"ニッチ"信号クラスに対して、$mathcalS$が相転移を起こすことを示す。
論文 参考訳（メタデータ） (2020-08-03T16:48:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。