Efficient Learning and Symmetry Discovery under Exact Invariances
Abstractの概要
本論文は、厳密な群不変性の下での教師あり回帰を研究し、対称性群が有限、無限、または未知である場合に不変推定量が効率的に計算可能かどうかを扱っています。スペクトル平均化フレームワークをランダム化部分集合選択手順によって拡張することで、著者らは群の濃度に依存しない実行時間で厳密な不変性を課す多項式時間アルゴリズムを確立しています。その理論的保証は、不変性制約が線形表現を介して定式化される有限次元特徴空間および多様体上のソボレフ回帰の両方をカバーしています。さらに著者らは対称性の発見についても検討し、既知の有限参照群から未知の有界指数部分群をデータから特定し、厳密に不変な推定量を学習する効率的な手法を提案しています。
新規性
本論文は、ランダム化部分集合選択を通じて群サイズへの実行時間の依存性を排除し、有限群と無限群に一様に適用可能な、厳密な群不変性を伴う学習のための初の多項式時間アルゴリズムを提供します。さらに、データから未知の有界指数部分群を復元するための、ランダムケイリーグラフの拡大とホールドアウト検証に基づく証明可能な対称性発見アルゴリズムを導入しています。
成果
既知の群に対して、提案手法は多項式時間で厳密に不変な推定量を計算し、ソボレフ空間においてO(n^{-s/(s+d/2)})の過剰リスク、有限次元特徴空間においてO(dim(H^G)/n)のミニマックス最適リスクを達成します。有限参照群における未知の有界指数部分群に対しては、サイズO(log|H|)の生成集合を発見し、poly(n, d, 1/kappa, log|G|, log(1/delta))時間で厳密に不変な推定量を返すことで、有限次元の既知の対称性におけるサンプル複雑性と一致します。
論文の注目点
- ランダム化部分集合選択により、線形制約が不変部分空間を完全に捉える少数の群要素を適応的に特定し、群の濃度への依存を回避する。
- 学習フレームワークはスペクトル係数推定と制約付き二次計画法を統合し、有限次元およびソボレフ回帰の両領域で厳密な不変性を保証する。
- 有限群内の未知の対称性に対して、ランダムな群サンプリングとホールドアウトデータ上での経験リスク比較を組み合わせることで、有界指数部分群の生成集合を確実に復元する。