論文の概要: Efficient Learning and Symmetry Discovery under Exact Invariances

• arxiv url: http://arxiv.org/abs/2609.07031v1
• Date: Mon, 07 Sep 2026 04:35:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.361823
• Title: Efficient Learning and Symmetry Discovery under Exact Invariances
• Title（参考訳）: 厳密な不変条件下での効率的な学習と対称性の発見
• Abstract要約: 群不変性による学習は多くの科学的および幾何学的な学習問題の中心である。 与えられた群作用のちょうど部分群にある回帰関数を効率的に計算できるかどうかは不明である。 有限群と無限群に一様に適用する正確な群不変量を持つ学習アルゴリズムを初めて提案する。
• 参考スコア（独自算出の注目度）: 62.27019402162741
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning with group invariances is central to many scientific and geometric learning problems, yet its computational foundations remain poorly understood. Even for classical supervised regression settings, it has been unclear whether one can efficiently compute a regression function that is exactly invariant to a given group action. Recent work showed that exact invariance can be enforced in polynomial time when the underlying group is finite and known, but left open the cases of infinite groups and unknown symmetries. In this paper, we resolve both challenges. First, we present the first polynomial-time algorithm for learning with exact group invariances that applies uniformly to finite and infinite groups. The runtime is polynomial in the data dimension and sample size, and independent of the group, while achieving strong generalization guarantees. This provides a computational explanation for the empirical success of invariant and equivariant methods in geometric machine learning and partially answers a recent open question in the literature. Second, we study learning in the symmetry discovery setting, where the invariance group is unknown. Focusing on the subgroup lattice of a finite group, we show that exact symmetries can be identified from data and exploited for learning in polynomial time. For regression over finite-dimensional feature spaces, our algorithm provably recovers the underlying symmetry, matches the minimax-optimal sample complexity of the known-symmetry setting, and runs in time polynomial in the data dimension and sample size. Our analysis relies on tools from random Cayley graphs and expander theory, which may be of independent interest.
• Abstract（参考訳）: 群不変性による学習は多くの科学的および幾何学的な学習問題の中心であるが、その計算基盤は未だ理解されていない。 古典的教師付き回帰設定であっても、与えられた群作用に正確に不変な回帰関数を効率的に計算できるかどうかは不明である。 最近の研究は、基底群が有限で既知の多項式時間で正確な不変性を強制できることを示したが、無限群と未知の対称性のケースは開き放たれた。 本稿では,両課題の解決について述べる。 まず、有限群と無限群に一様に適用する正確な群不変性を持つ学習のための最初の多項式時間アルゴリズムを提案する。 ランタイムはデータ次元とサンプルサイズにおける多項式であり、グループとは独立であり、強力な一般化を保証する。 これは幾何学的機械学習における不変および同変手法の実証的成功の計算的説明を提供し、文献における最近のオープンな疑問に部分的に答える。 第2に、不変群が未知の対称性発見環境における学習について研究する。 有限群の部分群格子に着目して、データから正確な対称性を特定でき、多項式時間で学習するために利用されることを示す。 有限次元の特徴空間上の回帰について、本アルゴリズムは、基礎となる対称性を確実に回復し、既知の対称性設定の最小最適サンプル複雑性と一致し、データ次元とサンプルサイズにおいて時間多項式で実行される。 我々の分析は、無作為なケイリーグラフと拡張子理論のツールに依存しており、これは独立した興味を持つかもしれない。

関連論文リスト

• Data Augmentation: A Fourier Analysis Perspective [52.00584777952869]
  部分的なデータ拡張は、一般化やサンプルの複雑さの観点から、完全な拡張と同じ統計的利点が得られることを示す。 この結果から, 部分拡張が, ほぼ対称性を保っているにもかかわらず, 完全拡張の統計的利点を維持できる理由を理論的に説明できる。
  論文  参考訳（メタデータ） (2026-06-23T10:54:14Z)
• Learning with Exact Invariances in Polynomial Time [43.81087760363805]
  本稿では,カーネル回帰を用いて,正確な不変性(あるいは対称性)を学習するための統計的・計算的トレードオフについて検討する。 提案手法は,元のカーネル回帰問題と同じ過大な集団リスクを実現する。
  論文  参考訳（メタデータ） (2025-02-27T04:49:52Z)
• Invariant Kernels: Rank Stabilization and Generalization Across Dimensions [7.154556482351604]
  対称性がカーネル行列のランクに顕著な影響を与えることを示す。 具体的には、その2つの引数に対して独立に作用する様々な群の下で不変な固定次数の核のランクを計算する。 上記の3つの例を含む具体的状況において、対称性はデータ次元から独立させるランクを劇的に減少させる。
  論文  参考訳（メタデータ） (2025-02-03T23:37:43Z)
• Accelerated Discovery of Machine-Learned Symmetries: Deriving the Exceptional Lie Groups G2, F4 and E6 [55.41644538483948]
  このレターでは、対称性変換の発見を著しく高速化する2つの改良されたアルゴリズムを紹介している。 例外的リー群の複雑性を考えると,この機械学習手法は完全に汎用的であり,多種多様なラベル付きデータセットに適用可能であることを示す。
  論文  参考訳（メタデータ） (2023-07-10T20:25:44Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  ラベル付きデータセットに存在する連続した対称性群の検出と同定のためのディープラーニングアルゴリズムを設計する。 完全に接続されたニューラルネットワークを用いて、変換対称性と対応するジェネレータをモデル化する。 また,Lie群とその性質の数学的研究に機械学習アプローチを使うための扉を開く。
  論文  参考訳（メタデータ） (2023-01-13T16:25:25Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• On the Sample Complexity of Learning with Geometric Stability [42.813141600050166]
  対象関数がそのような不変性や安定性を示す学習問題のサンプル複雑性について検討する。 カーネル法における非パラメトリック収束率と,グループの大きさに等しい因子によるサンプル複雑性の改善について述べる。
  論文  参考訳（メタデータ） (2021-06-14T03:51:16Z)

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

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