論文の概要: Neural Weight Norm = Kolmogorov Complexity

• arxiv url: http://arxiv.org/abs/2605.10878v1
• Date: Mon, 11 May 2026 17:27:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:51.03217
• Title: Neural Weight Norm = Kolmogorov Complexity
• Title（参考訳）: Neural Weight Norm = Kolmogorov Complexity
• Authors: Tiberiu Musat,
• Abstract要約: 任意の固定精度状態において、二進弦を出力するループニューラルネットワークの最小の重みノルムは、対数係数まで、その弦のコルモゴロフ複雑性と等しい。 このことは、ウェイト崩壊が以前のソロモノフの普遍的事前、計算可能上の最適事前関数をマッチング係数まで誘導することを意味する。
• 参考スコア（独自算出の注目度）: 5.076419064097734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Why does weight decay work? We prove that, in any fixed-precision regime, the smallest weight norm of a looped neural network outputting a binary string equals the Kolmogorov complexity of that string, up to a logarithmic factor. This implies that weight decay induces a prior matching Solomonoff's universal prior, the optimal prior over computable functions, up to a polynomial factor. The result is norm-agnostic: in fixed precision, every weight norm collapses to the non-zero parameter count up to constants, so the same sandwich bound holds for any norm used as a regulariser. The proof has two short reductions: any program for a universal Turing machine can be encoded into neural weights at unit cost per program bit, and any fixed-precision network can be described by enumerating its non-zero parameters with logarithmic addressing overhead. Both bounds are tight up to constants, with the logarithmic factor realised by permutation encodings: a network whose parameters encode a permutation produces a string whose Kolmogorov complexity is the non-zero parameter count times its logarithm. The fixed-precision assumption is essential: with infinite precision, neural networks can encode non-computable functions and the weight norm loses its relevance.
• Abstract（参考訳）: なぜ体重減少はうまくいくのか? 固定精度では、二進弦を出力するループニューラルネットワークの最小の重みノルムが、対数係数までその弦のコルモゴロフ複雑性に等しいことを証明している。 このことは、ウェイト崩壊が、ソロモノフの普遍的事前、計算可能関数の最適事前を多項式係数まで導き出すことを意味する。 固定精度では、すべての重みノルムは定数までゼロでないパラメータに崩壊するので、同じサンドイッチ境界は正規化として使われるノルムに対して成り立つ。 普遍チューリングマシンのプログラムは、プログラムビット当たりの単位コストでニューラルウェイトにエンコードすることができ、固定精度ネットワークは、その非ゼロパラメータを対数アドレスのオーバーヘッドで列挙することで記述することができる。 置換を符号化するネットワークは、コルモゴロフ複雑性が非ゼロパラメータの対数倍である文字列を生成する。 無限の精度で、ニューラルネットワークは計算不能な関数を符号化することができ、ウェイトノルムはその関連性を失う。

関連論文リスト

• Binary Tree Block Encoding of Classical Matrix [6.334095794072344]
  ブロックエンコーディングは量子コンピューティングにおいて重要な計算である。 私たちのプロトコルはBinary Tree Block-encoding (textttBITBLE)と名付けられています。
  論文  参考訳（メタデータ） (2025-04-08T02:53:43Z)
• SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantization [5.982922468400901]
  ニューラルネットワークの重みの順に得られる誤差境界を達成可能であることを示す。 我々は、無限アルファベットと入力データに対する最小の仮定の下で、完全なネットワーク境界を達成できることを証明した。
  論文  参考訳（メタデータ） (2023-09-20T00:35:16Z)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  グラフクエリはグラフニューラルネットワーク(GNN)の有界サイズファミリによって計算可能であることを示す。 GNNは、カウントとビルトインの関係を持つ一階述語論理のガードされた断片で定義できる。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:32:59Z)
• Koopman-based generalization bound: New aspect for full-rank weights [45.64416573341108]
  クープマン演算子を用いたニューラルネットワークの一般化のための新しいバウンダリを提案する。 我々の結果は、フルランクの重み行列を持つニューラルネットワークの一般化の理解に新たな光を当てている。
  論文  参考訳（メタデータ） (2023-02-12T00:39:25Z)
• On Algebraic Constructions of Neural Networks with Small Weights [21.915057426589748]
  神経ゲートの重みサイズ,回路サイズ,深さのトレードオフについて検討した。 具体的には、任意の係数を持つ1つの線型方程式が与えられたとき、より小さい(一定の)係数を持つ線形方程式系を用いてそれを表現したい。 EQUALITY関数を計算するために,定数重み付き最適サイズ行列を明示的に構築する。 我々はComparISON関数を計算するために最もよく知られたウェイトサイズ(線形)行列の存在を証明した。
  論文  参考訳（メタデータ） (2022-05-17T00:09:23Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  暗黙のニューラルネットワークは、精度の向上とメモリ消費の大幅な削減を示す。 彼らは不利な姿勢と収束の不安定さに悩まされる。 本論文は,ニューラルネットワークを高機能かつ頑健に設計するための新しい枠組みを提供する。
  論文  参考訳（メタデータ） (2021-06-06T18:05:02Z)
• SiMaN: Sign-to-Magnitude Network Binarization [165.5630656849309]
  重みバイナライゼーションは、高倍率重みを+1s、0sに符号化することで分析ソリューションを提供する。 二元化ネットワークの学習重みは、エントロピーを許さないラプラシアン分布に概ね従うことが証明される。 CIFAR-10 と ImageNet を用いて,シマナライゼーション (SiMaN) と呼ばれる手法の評価を行った。
  論文  参考訳（メタデータ） (2021-02-16T07:03:51Z)

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

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