論文の概要: Arithmetic Circuits and Neural Networks for Regular Matroids

• arxiv url: http://arxiv.org/abs/2511.02406v1
• Date: Tue, 04 Nov 2025 09:37:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 18:47:05.875983
• Title: Arithmetic Circuits and Neural Networks for Regular Matroids
• Title（参考訳）: 正規マトロイドの算術回路とニューラルネットワーク
• Authors: Christoph Hertrich, Stefan Kober, Georg Loho,
• Abstract要約: 我々は、$n$要素上の正規マトロイドを生成する基底を計算するために、サイズ$O(n3)$の均一な$(max,+,)$回路が存在することを証明した。 熱帯化により、通常のマトロイドの重み付けベースで同じ大きさの$(max,+,)$-circuitsとReLUニューラルネットワークが存在することが示唆される。
• 参考スコア（独自算出の注目度）: 8.026318680041738
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that there exist uniform $(+,\times,/)$-circuits of size $O(n^3)$ to compute the basis generating polynomial of regular matroids on $n$ elements. By tropicalization, this implies that there exist uniform $(\max,+,-)$-circuits and ReLU neural networks of the same size for weighted basis maximization of regular matroids. As a consequence in linear programming theory, we obtain a first example where taking the difference of two extended formulations can be more efficient than the best known individual extended formulation of size $O(n^6)$ by Aprile and Fiorini. Such differences have recently been introduced as virtual extended formulations. The proof of our main result relies on a fine-tuned version of Seymour's decomposition of regular matroids which allows us to identify and maintain graphic substructures to which we can apply a local version of the star-mesh transformation.
• Abstract（参考訳）: 我々は、$n$要素上の正規マトロイドの基底生成多項式を計算するために、サイズ$O(n^3)$の均一な$(+,\times,/)$-回路が存在することを証明した。 熱帯化により、通常のマトロイドの重み付け基底最大化のために同じ大きさの$(\max,+,-)$-circuitsとReLUニューラルネットワークが存在することが示唆される。 線形プログラミング理論の結果として、2つの拡張された定式化の差を取ることは、4月とフィオリーニによる最もよく知られた$O(n^6)$の個人拡張定式化よりも効率的にできるという最初の例を得る。 このような違いは、最近仮想拡張式として紹介されている。 主結果の証明は、シーモアの正規マトロイド分解の微調整版に依拠し、星メシュ変換の局所版を適用可能なグラフィック部分構造を特定し維持することができる。

関連論文リスト

• Geometry of fibers of the multiplication map of deep linear neural networks [0.0]
  固定行列に乗算する構成可能な行列のクイバーの集合の幾何学について検討する。 我々の解は、同変コホモロジーにおけるポアンカー級数、二次整数プログラム、明示的な公式の3つの形式で表される。
  論文  参考訳（メタデータ） (2024-11-29T18:36:03Z)
• Neural Networks and (Virtual) Extended Formulations [8.185918509343818]
  私たちは、$P$を最適化するニューラルネットワークのサイズに対して、より低い境界を証明します。 我々は、$mathrmxc(P)$が任意のモノトーンや入力ニューラルネットワークのサイズの低い境界であることを示し、$P$を超える線形最適化問題を解く。
  論文  参考訳（メタデータ） (2024-11-05T11:12:11Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Shallow neural network representation of polynomials [91.3755431537592]
  d+1+sum_r=2Rbinomr+d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1]
  論文  参考訳（メタデータ） (2022-08-17T08:14:52Z)
• De Rham compatible Deep Neural Network FEM [0.0]
  DNNでは通常のsimplicial partitions $mathcalT$ of $Omega$の制限は不要である。 我々は、高階互換空間や他の非互換な離散化のクラスへの構成の一般化を示す。
  論文  参考訳（メタデータ） (2022-01-14T11:22:13Z)
• Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks [0.0]
  最大固有値は、よく知られた線形確率行列のアンサンブルと同じ極限(確率)を持つことを示す。 これは機械学習の応用にとって大きな関心事かもしれない。
  論文  参考訳（メタデータ） (2022-01-13T00:48:20Z)
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks [70.15611146583068]
  我々は、線形整列ユニット(ReLU)を用いた2層ニューラルネットワークのトレーニングの正確な表現を開発する。 我々の理論は半無限双対性と最小ノルム正規化を利用する。
  論文  参考訳（メタデータ） (2020-02-24T21:32:41Z)

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

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