論文の概要: Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

• arxiv url: http://arxiv.org/abs/2610.18154v1
• Date: Tue, 13 Oct 2026 10:58:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-17 07:05:37.404912
• Title: Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
• Title（参考訳）: グループ要素の学習 : ガロア対応,最適ERM,ナタラジャン次元のためのアベル・ラフニ閾値
• Abstract要約: 有限軌道で作用する未知の要素を可算集合上で学習する。 可算体の有限ガロワ拡大に対して、ナタラジャン次元は群不変量に等しい。 グループ$A_5$と$S_5$は23ドルと$34$であり、$A_5$はギャップのある最小のグループである。
• 参考スコア（独自算出の注目度）: 5.232247961914376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study learning an unknown element $g$ of a group acting with finite orbits on a countable set, from examples $(x,gx)$. After a sample on $A$, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of $A$, and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the minimal base size. Among deterministic learners, symmetry makes empirical risk minimization optimal: on nondegenerate classes every consistent learner, whatever its tie-breaking, attains the optimal realizable sample complexity up to constant factors, and every consistent online learner the optimal mistake bound. Agnostically, every ERM's sample complexity exceeds the known lower bound by at most the DS-to-Natarajan ratio, up to constants. For finite Galois extensions of countable fields, the Natarajan dimension equals a group invariant, the coset-cube number, which is at least the number of complemented factors of any chief series of any subgroup. Hence the dimensions coincide for every solvable Galois group, while for the groups $A_5$ and $S_5$ of the quintic they are $2<3$ and $3<4$, and $A_5$ is the smallest group with a gap. For the Galois group $S_n$ of the general equation of degree $n$, they coincide exactly when $n\le 4$, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group $\mathrm{PSL}(2,8)$ has no gap. For linear, orthogonal and unitary maps of $\mathbb R^d$ or $\mathbb C^d$ both dimensions equal $d$, and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.
• Abstract（参考訳）: 可算集合上の有限軌道で作用する群の未知元$g$を、例えば$(x,gx)$から学習する。 A$のサンプルの後、一貫した仮説は、点方向の安定化器のコセットの制限であり、サンプルは、この安定化器が固定する点のラベルを正確に強制する。 この対応を通じて、多クラス次元は群不変となり、DSとグラフ次元は高さと等しく、リトルストーン次元は最長の既約列長、教育次元は最小基底サイズである。 決定論的学習者の中で、対称性は経験的リスク最小化を最適にする: 非退化クラスでは、すべての一貫した学習者は、その結びつきがどうであれ、最適に実現可能なサンプルの複雑さを一定要素まで達成し、全ての一貫したオンライン学習者は最適な誤りを負う。 不可知的に、全てのERMのサンプルの複雑さは、DS--ナタラジャン比の最大値から定数まで、既知の下界を超える。 可算体の有限ガロワ拡大に対しては、ナタラジャン次元は群不変量、少なくとも任意の部分群の主級数の補因子の数である余集合キューブ数と等しい。 したがって、次元はすべての可解ガロア群に一致するが、クインティック群の$A_5$と$S_5$は2<3$と$<4$であり、$A_5$はギャップを持つ最小の群である。 次数 $n$ の一般方程式のガロア群 $S_n$ に対して、それらはちょうど$n\le 4$, すなわち標数 0 において、方程式が根基によって解けるときにちょうど一致する。 線型、直交、ユニタリ写像において、$\mathbb R^d$ または $\mathbb C^d$ の両次元は$d$ であり、2-ファイバー擬キューブは、そのモノドロミー群がアーベル群であるときにちょうどナタラジャン立方体の非連結和である。

関連論文リスト

• Heuristic lower bounds on real Grothendieck constants of finite and infinite order [0.0]
  実グロタンディーク定数の候補下界は$K_mathrm G(d)$である。 我々は、このしきい値において半球戦略が地球規模で最適であると推測する。 大規模シーソー最適化は連続予測をサポートする。
  論文  参考訳（メタデータ） (2026-09-28T15:23:05Z)
• $\mathbb{SL}(n)$ Representation Learning: An Intrinsic Mixed-Curvature Space with Higher Curvature Capacities and Deeper Order-Aware Composition [47.80325814873361]
  混合曲率表現学習は、単一の曲率構造によって適切にモデル化できないリッチな幾何学的構造を捉えることを目指している。 例えば、$mathbbSL(n)$ space, a representation geometry defined by the simple $det(A)variant=1$ constraint and a left in Schatten-$p$ structure。 この最小構成にもかかわらず、$mathbbSL(n)$ は共通のフラグポールの周りに点方向の負、零、およびフラグ曲率を示す。
  論文  参考訳（メタデータ） (2026-09-14T05:52:14Z)
• The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups [0.0]
  いくつかの初期の量子アルゴリズムは有限アーベル群上の隠れ問題(HSP)の例である。 自由時間量子モジュラリティは、任意の非アーベル有限群上の HSP で知られている。 入力構造に対する軽度の仮定の下で、有限準ハミルトニアン群に対するニル時間量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2026-08-05T18:25:25Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• 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)
• Brauer's Group Equivariant Neural Networks [0.0]
  我々は、層が$mathbbRn$のテンソルパワーを持つような全ての可能な群同変ニューラルネットワークの完全な特徴付けを提供する。 そのようなテンソルパワー空間間の学習可能、線型、等変層関数に対する行列の分散集合を求める。
  論文  参考訳（メタデータ） (2022-12-16T18:08:51Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。