論文の概要: Non-Clashing Teaching Maps for Balls in Graphs
- arxiv url: http://arxiv.org/abs/2309.02876v2
- Date: Mon, 29 Jul 2024 14:10:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-31 00:46:55.671791
- Title: Non-Clashing Teaching Maps for Balls in Graphs
- Title（参考訳）: グラフ内の球に対する非切断型指導マップ
- Authors: Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel,
- Abstract要約: 関連する決定問題 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)$を出力するカーネル化アルゴリズムを許可しない。
- 参考スコア（独自算出の注目度）: 0.05356944479760104
- 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 is the most efficient machine teaching model satisfying the Goldman-Mathias collusion-avoidance criterion. A teaching map $T$ for a concept class $\mathcal{C}$ assigns a (teaching) set $T(C)$ of examples to each concept $C \in \mathcal{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 teaching set $T(C)$, $C \in \mathcal{C}$. The non-clashing teaching dimension NCTD$(\mathcal{C})$ of $\mathcal{C}$ is the minimum size of an NCTM for $\mathcal{C}$. NCTM$^+$ and NCTD$^+(\mathcal{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 B-NCTD$^+$ for NCTD$^+$ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, B-NCTD$^+$ does not admit an algorithm running in time $2^{2^{o(\text{vc})}}\cdot n^{O(1)}$, nor a kernelization algorithm outputting a kernel with $2^{o(\text{vc})}$ vertices, where vc is the vertex cover number of $G$. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by vc, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. 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, and for Gromov-hyperbolic graphs, we design an approximate NCTM$^+$ of size 2.
- Abstract（参考訳）: 最近、Kirkpatrick et al [ALT 2019] と Fallat et al [JMLR 2023] は非クラッシング教育を導入し、ゴールドマン・マティアスの共謀回避基準を満たす最も効率的な機械教育モデルであることを示した。
概念クラス $\mathcal{C}$ に対する教示写像 $T$ は、各概念 $C \in \mathcal{C}$ に対して (teaching) set $T(C)$ の例を割り当てる。
教示写像は、概念のペアがそれらの教示集合の和集合と一致しない場合、非クラッシングである。
非クラッシング教育写像 (NCTM) $T$ は、授業セット $T(C)$, $C \in \mathcal{C}$ の最大サイズである。
非クラッシング教育次元 NCTD$(\mathcal{C})$ of $\mathcal{C}$ は、NCTM の$\mathcal{C}$ の最小サイズである。
NCTM$^+$ と NCTD$^+(\mathcal{C})$ は類似して定義されるが、教師は正の例のみを使用することができる。
グラフのすべての球からなる概念クラス $\mathcal{B}(G)$ に対して NCTM と NCTM$^+$s を研究する。
関連する決定問題 B-NCTD$^+$ for NCTD$^+$ is NP-complete in split, co-bipartite and bipartite graphs。
驚いたことに、ETH が失敗しない限り、B-NCTD$^+$ は時間で走るアルゴリズム 2^{2^{o(\text{vc})}}\cdot n^{O(1)}$、カーネルに 2^{o(\text{vc})$ vertices を出力するカーネル化アルゴリズムも認めない。
これらの下界と一致する上界を補完する。
これらは非常に稀な結果である: NP において、vc によってパラメータ化されるような厳密な二重指数下界を許容することは唯一の問題であり、カーネル内の頂点数にそのような ETH ベースの条件付き下界を許容する問題の1つである。
木、インターバルグラフ、サイクルおよびサイクルのツリーに対して、VC次元に比例する大きさのNCTM$^+$sまたはNCTMを$\mathcal{B}(G)$とし、グロモフ・ハイエルボリックグラフに対して、近似NCTM$^+$s2を設計する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。