Fugu-MT 論文翻訳(概要): Higher-arity PAC learning, VC dimension and packing lemma

論文の概要: Higher-arity PAC learning, VC dimension and packing lemma

arxiv url: http://arxiv.org/abs/2510.02420v1
Date: Thu, 02 Oct 2025 15:54:50 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-06 16:35:52.101647
Title: Higher-arity PAC learning, VC dimension and packing lemma
Title（参考訳）: 高純度PAC学習、VC次元およびパッキング補題
Authors: Artem Chernikov, Henry Towsner,
Abstract要約: 以下は、Towsner'20(arXiv:2010.00726)のチェルニコフにおける研究の概観である。また、arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404の最近の結果のいくつかは、arXiv:2010.00726における我々の研究から得られたものである。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The aim of this note is to overview some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise) hypergraph regularity lemma; and to demonstrate that it characterizes higher arity PAC learning (PAC$_n$ learning) in $n$-fold product spaces with respect to product measures introduced by Kobayashi, Kuriyama and Takeuchi'15. We also point out how some of the recent results in arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404 follow from our work in arXiv:2010.00726.
Abstract（参考訳）: 本研究の目的は,Hussler packing lemma の一般化や関連する Tame (slice-wise) hypergraph regularity lemma などの高次アリティ VC 理論(VC$_n$ dimension) の展開と,高次アリティ PAC 学習 (PAC$_n$ learning) を,小林,栗山,竹内'15 が導入した製品測度に関して$n$fold の製品空間において特徴付けることにある。また、arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404の最近の結果のいくつかは、arXiv:2010.00726における我々の研究から得られたものである。

関連論文リスト

A packing lemma for VCN${}_k$-dimension and learning high-dimensional data [1.6114012813668932]
本研究では,非認識型高アリティPAC学習性は,Husslerパッケージ特性の高アリティバージョンを意味することを示す。これは古典的なPAC学習性は古典的なハウスラーパッキング特性を意味するという直接的な証明を得ることによってなされる。
論文参考訳（メタデータ） (2025-05-21T16:03:12Z)
Sparsity dependence of Krylov state complexity in the SYK model [0.0]
我々は,Sachdev-Ye-Kitaevモデル(SYK)のKrylov状態の複雑さを$N le 28$ Majorana fermions with $q$-body fermion interactionに対して検討した。大きな温度では、k$を超えると、複雑さのピーク値は変化しない。
論文参考訳（メタデータ） (2024-07-30T05:57:14Z)
Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文参考訳（メタデータ） (2024-06-18T08:54:04Z)
Dimension-free discretizations of the uniform norm by small product sets [45.85600902330814]
ベルンシュタインの古典的不等式は、単位円上の最高ノルムの$f$と、その最高ノルムの$K$-階根のサンプリング集合上の最高ノルムと比較する。次元自由離散化は、濃度が$deg(f)$とは独立なサンプリング集合で可能であり、代わりに$f$の最大個人次数によって支配されることを示す。
論文参考訳（メタデータ） (2023-10-11T22:46:09Z)
Provable Advantage in Quantum PAC Learning [3.291862617649511]
PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
論文参考訳（メタデータ） (2023-09-19T19:26:20Z)
Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
論文参考訳（メタデータ） (2023-02-06T02:52:36Z)
Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文参考訳（メタデータ） (2023-01-04T04:15:40Z)
A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks [99.46182575751271]
グラフニューラルネットワーク(GNN)の2つの一次クラスに対する一般化境界を導出する。その結果,重みの最大ノード次数とスペクトルノルムが両モデルの一般化境界を規定することが明らかとなった。
論文参考訳（メタデータ） (2020-12-14T16:41:23Z)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文参考訳（メタデータ） (2020-06-22T17:53:54Z)
The VC-Dimension of Axis-Parallel Boxes on the Torus [0.0]
我々は、$d$次元軸、箱および立方体のファミリーのVC次元がともに$d log_2(d)$であることを示す。 VC次元は通常、同様の設定で$d$で線形に成長するので、これは特に驚きだ。
論文参考訳（メタデータ） (2020-04-28T21:41:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。