論文の概要: Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

• arxiv url: http://arxiv.org/abs/2606.29331v1
• Date: Sun, 28 Jun 2026 10:59:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-30 18:07:15.879617
• Title: Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees
• Title（参考訳）: 科学的発見のサンプル複雑さ:合成機能木のPAC学習性
• Authors: Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın,
• Abstract要約: 本稿では,PAC学習のレンズを通して統計的側面を再考する。 滑らかな作用素の有限語彙から構築された合成関数木に着目する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth. This paper revisits the statistical side through the lens of PAC learning, focusing on compositional function trees built from a finite vocabulary of smooth operators (e.g., $\{+,\times,\sin,\exp\}$ and affine maps). We prove that the relevant generalization quantity, Rademacher complexity, hence the excess risk, does not necessarily blow up exponentially with the number of distinct symbolic structures, but is controlled by (i) the depth $d$ and (ii) the Lipschitz constants of the base operators along the composed computation graph. Concretely, under mild Lipschitz conditions on operators and bounded affine leaves, a finite-union bound over a vocabulary of size $K=|\mathcal{H}_{\mathrm{base}}|$ together with Maurer-type vector contraction yields $\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})$ with arity bound $b$; corresponding high-probability risk bounds scale as $\mathcal{O}(L^{d}/\sqrt{n})$ when $K,b=O(1)$ and $\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})=O(n^{-1/2})$. We complement the theory with a modular codebase that trains differentiable operator trees (not MLPs) on synthetic "physics-like" targets of controlled depth and shows that the empirical generalization gap correlates positively with the predicted complexity term $(\widehat{L}^{d})/\sqrt{n}$.
• Abstract（参考訳）: 記号回帰による科学的発見は、表現の仮説空間が深さと組み合わせて成長するので、統計学的かつ計算的に難解であると見なされることが多い。 本稿では,滑らかな作用素の有限語彙(例えば,$\{+,\times,\sin,\exp\}$およびアフィン写像)から構築された合成関数木に着目し,PAC学習のレンズによる統計的側面を再検討する。 我々は、関連する一般化量、ラデマッハ複雑性、すなわち余剰リスクが、必ずしも異なる記号構造の数で指数関数的に爆発するわけではないことを証明している。 (i)d$とd$ (ii) 合成計算グラフに沿った基底作用素のリプシッツ定数。 具体的には、作用素と有界なアフィン葉上の穏やかなリプシッツ条件の下では、サイズ$K=|\mathcal{H}_{\mathrm{base}}|$とマウラー型ベクトル収縮(英語版)(Maurer-type vector contraction)$\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})$$ arity bound $b$; 対応する高確率なリスク境界スケールが $\mathcal{L}(d^{d}/\mathcal{n})$K=$O(\mathcal{H}_{\mathrm{comp}}^{1})$$$K である。 我々は、制御深さの合成的「物理的」なターゲット上で微分可能作用素木(MLPではない)を訓練するモジュラーコードベースで理論を補完し、経験的一般化ギャップが予測複雑性項 $(\widehat{L}^{d})/\sqrt{n}$ と正に相関していることを示す。

関連論文リスト

• Quantitative Sobolev Approximation Bounds for Neural Operators with Empirical Validation on Burgers Equation [0.0]
  本研究では,ソボレフ空間における演算子学習のための関数解析フレームワークを開発し,それをFNO(Fourier Neural Operators)の数値的挙動に接続する。 モデルサイズの全体にわたって、テスト$H1$-errorsを$mathcalO(10-7)$まで下げ、相対誤差を10～3$とし、解と空間微分を正確に一致させる。
  論文  参考訳（メタデータ） (2026-05-04T22:15:21Z)
• A Hierarchy of Entanglement Cones via Rank-Constrained $C^*$-Convex Hulls [0.0]
  本稿では、可分変換(mathscrPtrivial_+$)および可分変換(PPT)予想の幾何学について検討する。
  論文  参考訳（メタデータ） (2025-12-05T09:34:05Z)
• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound if $epsilon$ is constant。 また、$mu_mathbfy(mathbfX)$は計算が難しいという事前予想も否定する。
  論文  参考訳（メタデータ） (2024-12-03T18:11:37Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Randomised Composition and Small-Bias Minimax [0.9252523881586053]
  クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。 まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
  論文  参考訳（メタデータ） (2022-08-26T23:32:19Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)

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

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