論文の概要: Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent

• arxiv url: http://arxiv.org/abs/2605.28612v1
• Date: Wed, 27 May 2026 15:26:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-28 17:38:56.170088
• Title: Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent
• Title（参考訳）: グラディエントDescentを用いた製品ネットワークを用いた高次元パリティ関数の学習
• Authors: Guillaume Larue, Louis-Adrien Dufrène, Quentin Lampin, Hadi Ghauch, Ghaya Rekaya,
• Abstract要約: 高次元パリティ関数は、機械学習、暗号、エラー訂正に不可欠である。 標準的なニューラルネットワークアーキテクチャは、通常指数的なサンプル複雑性を必要とする。 コンパクトな製品ベースのニューラルアーキテクチャとデータスパシティを組み合わせることで、効率の良いパリティ学習が可能になることを示す。 この研究は、自動プロトコル発見に適用されるニューラル演算、構造化推論、バイナリニューラルネットワーク、マシンラーニングの新たな可能性を開く。
• 参考スコア（独自算出の注目度）: 1.6802038598427533
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Parity functions are fundamental Boolean operations with critical applications across machine learning, cryptography, and error correction. Yet, learning high-dimensional parity functions poses significant challenges: in a general setting, standard neural network architectures typically require exponential sample complexity, making gradient-based optimization intractable for large number of inputs $N$. We demonstrate that compact product-based neural architectures combined with stochastic data sparsity (Bernoulli inputs with $p_e \leq 1/N$) and appropriate hyperparameter choice enable efficient parity learning, with theoretical guarantees of convergence. Experiments validate our theory across dimensions up to $N = 100{,}000$, with empirical evidence showing optimal hyperparameter choices for $p_e$ and learning rate $α$, as well as polynomial complexity scaling laws. This work establishes fundamental connections between architectural inductive bias and data sparsity, opening new possibilities for neural arithmetic, structured reasoning, binary neural networks, and machine learning applied to automated protocol discovery.
• Abstract（参考訳）: パーティ関数は、機械学習、暗号、エラー訂正といった重要なアプリケーションを含む基本的なブール演算である。 しかし、高次元パリティ関数の学習には大きな課題が伴う。一般的な設定では、標準ニューラルネットワークアーキテクチャは通常、指数的なサンプルの複雑さを必要とし、多くの入力に対して勾配に基づく最適化を惹きつけることができる。 我々は,コンパクトな製品ベースニューラルアーキテクチャと確率的データ空間(ベルヌーリ入力と$p_e \leq 1/N$)を組み合わせることで,効率の良いパリティ学習と理論的収束の保証を実現することを実証した。 実験では、N = 100{,}000$までの次元で理論を検証し、p_e$と学習率$α$の最適ハイパーパラメータ選択と多項式複雑性スケーリング法則を実証的に示す。 この研究は、アーキテクチャ上の帰納バイアスとデータの疎結合を確立し、ニューラルネットワーク、構造化推論、バイナリニューラルネットワーク、そして自動プロトコル発見に適用される機械学習の新しい可能性を開く。

関連論文リスト

• Neural Approximation and Its Applications [73.11802084858294]
  トレーニングされていないニューラルネットワークをベース関数として活用することにより、ニューラルネットワークの基盤関数を導入する。 多変量関数近似のための神経近似(NeuApprox)パラダイムを提案する。 多様な多次元画像、光フィールドデータ、ビデオ、トラフィックデータ、ポイントクラウドデータの実験は、NeuApproxの有望な性能を示している。
  論文  参考訳（メタデータ） (2026-03-04T06:05:43Z)
• Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $μ$P Parametrization [66.03821840425539]
  本稿では, テンソル勾配プログラム(SGD)フレームワークを用いた$L$層ニューラルネットワークのトレーニング力学について検討する。 SGDにより、これらのネットワークが初期値から大きく逸脱する線形独立な特徴を学習できることを示す。 このリッチな特徴空間は、関連するデータ情報をキャプチャし、トレーニングプロセスの収束点が世界最小であることを保証する。
  論文  参考訳（メタデータ） (2025-03-12T17:33:13Z)
• Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function [24.457000214575245]
  固定問題インスタンス上での実用関数の不連続性と発振を特徴付ける新しい手法を提案する。 これは、実用関数の族における学習理論の複雑さが有界であることを示すのに使うことができる。
  論文  参考訳（メタデータ） (2025-01-23T15:10:51Z)
• Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputs [35.212818841550835]
  一層ニューラルネットワークと一層トランスフォーマーの研究を行った。 1つの隠れた層ニューラルネットワークは、データセット上で最大$L_2,k+1$-marginに達する。 同様の計算機構を1層変換器に注意して観察する。
  論文  参考訳（メタデータ） (2024-02-12T05:52:06Z)
• Optimal Approximation with Sparse Neural Networks and Applications [0.0]
  深い疎結合ニューラルネットワークを用いて、関数クラスの複雑性を$L(mathbb Rd)$で測定する。 また、ニューラルネットワークを誘導する関数の可算コレクションである表現システムについても紹介する。 次に、レート歪曲理論とウェッジレット構成を用いて、$beta$マンガ的関数と呼ばれるクラスの複雑性を分析する。
  論文  参考訳（メタデータ） (2021-08-14T05:14:13Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。 我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。 回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
  論文  参考訳（メタデータ） (2021-03-23T17:03:10Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)

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

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