論文の概要: Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks

• arxiv url: http://arxiv.org/abs/2611.07973v1
• Date: Thu, 05 Nov 2026 13:05:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 21:50:50.693945
• Title: Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks
• Title（参考訳）: Pecewise-Linear Kolmogorov-Arnold ネットワークの線形領域の最大数に関する高次漸近境界
• Abstract要約: Schoots et al.citepschoots2025relating (AIST 2025) CPWL (Continuous piecewise-linear) Kolmogorov-Arnold Network (KANs) の線形領域数に概してゆるい上界を定めている citepschoots2025 citepschoots2025 related is $ksum_ell=1Tn_ell-1n_ell。
• 参考スコア（独自算出の注目度）: 11.888882732753922
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Schoots et al.~\citep{schoots2025relating} (AISTATS 2025) established a generally loose upper bound on the number of linear regions of continuous piecewise-linear (CPWL) Kolmogorov--Arnold networks (KANs), without providing a lower bound. We consider a $T$-layer network with width vector $\mathbf n=(n_0,\ldots,n_T)$, input dimension $n_0=d$, output width $n_T=1$, and at most $k\geq2$ affine segments per edge. Our matching upper and lower bounds determine the tight growth order $Θ_{\mathbf n}(k^{\sum_{\ell=1}^{T}ρ_{\ell-1}})$ in $k$, where $ρ_{\ell-1}:=\min_{0\leq s\leq\ell-1}n_s$. When every hidden width is at least $d$, the tight order simplifies to $Θ_{\mathbf n}(k^{dT})$. The upper bound of \citep{schoots2025relating} is $k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell}$. Our upper bound improves it by a factor of $Θ_{\mathbf n}\!\left(k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell-\sum_{\ell=1}^{T}ρ_{\ell-1}} \right)$, with strict asymptotic improvement whenever a hidden layer has width greater than one. We further compare CPWL KANs with rectified linear unit (ReLU) networks using dense parameterizations with at most $Λ$ parameters per model and the same fixed nonlinear depth $T$. Counting trainable knot locations and optimizing the widths and $k$, we prove that the maximum region count of CPWL KANs divided by that of ReLU networks is $Θ_{d,T}(Λ^{d\lfloor T/2\rfloor})$ as $Λ\to\infty$, yielding a polynomial advantage for KANs when $T\geq2$. These tight bounds characterize the attainable geometric complexity of CPWL KANs, providing a foundation for understanding their expressive power and guiding architectural design.
• Abstract（参考訳）: Schoots et al ~\citep{schoots2025relating} (AISTATS 2025) は、連続片方向線形(CPWL)コルモゴロフ-アルノルドネットワーク(KAN)の線型領域の個数に対して、一般にゆるやかな上限を確立した。 我々は,幅ベクトル$\mathbf n=(n_0,\ldots,n_T)$,入力次元$n_0=d$,出力幅$n_T=1$,最大で$k\geq2$アフィンセグメントを持つ$T$層ネットワークを考える。 一致する上界と下界は、厳密な成長次数 $ _{\mathbf n}(k^{\sum_{\ell=1}^{T}ρ_{\ell-1}})$ in $k$, where $ρ_{\ell-1}:=\min_{0\leq s\leq\ell-1}n_s$ を決定する。 すべての隠れた幅が少なくとも$d$であるとき、厳密な順序は $ _{\mathbf n}(k^{dT})$ に単純化される。 citep{schoots2025relating} の上界は $k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell}$ である。 上界は$ _{\mathbf n}\! k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell-\sum_{\ell=1}^{T}ρ_{\ell-1}} \right)$。 さらに、CPWL Kans と正則線形単位(ReLU)ネットワークを、モデル毎のパラメータが最大$=$$、同じ固定非線形深さ$T$で、高密度パラメータ化(英語版)を用いて比較する。 トレーニング可能な結び目の位置を計算し、幅と$k$を最適化すると、ReLU ネットワークで分割された CPWL Kans の最大領域数は、$T\geq2$ のときに Kans の多項式上の優位性を与える$ を$ y_{d,T}(a^{d\lfloor T/2\rfloor})$ とする。 これらの厳密な境界は、CPWL Kansの達成可能な幾何学的複雑さを特徴付け、表現力を理解し、アーキテクチャ設計を導く基盤を提供する。

関連論文リスト

• Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization [1.6921396880325779]
  インクリメンタルな1次アルゴリズムをゼロ参照する場合、複雑性は$tildeO(n+sqrtn,Lvarepsilon-2)$で、クエリ予算は固定される。
  論文  参考訳（メタデータ） (2026-10-04T04:38:36Z)
• Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness [8.428362872515416]
  我々は、各$_maxgeq 3$に対して、個々の滑らかさの下で下界に一致することを証明した。 また、各$_maxgeq 3$に対して、個々の滑らかさの下で下界が一致することを証明する。
  論文  参考訳（メタデータ） (2026-08-30T02:47:24Z)
• Shallower ReLU Network Representations via Exact Linear Algebra [6.437241429006478]
  実数$n$の最大値は、$nle 10$ごとに2つの隠された層を持つReLUネットワークによって正確に表現可能であることを証明している。 特に$mathbbRd$ for $dle 9$ 上のすべての連続ピースワイズ線型関数は、2層ReLU表現を許容する。
  論文  参考訳（メタデータ） (2026-07-22T16:58:02Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。 我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
  論文  参考訳（メタデータ） (2026-05-22T12:22:20Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Optimal Approximation Rate of ReLU Networks in terms of Width and Depth [5.37133760455631]
  本稿では,深部フィードフォワードニューラルネットワークの幅と深さの近似力に着目した。 幅$mathcalObig(maxdlfloor N1/drfloor,, N+2big)$と深さ$mathcalO(L)$のReLUネットワークは、近似レート$mathcalObig(lambdasqrtd (N2L2ln)で$[0,1]d$のH"古い連続関数を近似できる。
  論文  参考訳（メタデータ） (2021-02-28T13:15:55Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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