論文の概要: On efficiently computable functions, deep networks and sparse compositionality
- arxiv url: http://arxiv.org/abs/2510.11942v1
- Date: Mon, 13 Oct 2025 21:05:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-15 21:19:14.962875
- Title: On efficiently computable functions, deep networks and sparse compositionality
- Title（参考訳）: 効率的な計算可能関数, ディープネットワーク, スパース構成性について
- Authors: Tomaso Poggio,
- Abstract要約: 固定された入出力精度のチューリング計算能力は,有界(有界bサイズ)DAG表現の存在を示唆することを示す。
- 参考スコア（独自算出の注目度）: 0.8412351591933386
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that \emph{efficient Turing computability} at any fixed input/output precision implies the existence of \emph{compositionally sparse} (bounded-fan-in, polynomial-size) DAG representations and of corresponding neural approximants achieving the target precision. Concretely: if $f:[0,1]^d\to\R^m$ is computable in time polynomial in the bit-depths, then for every pair of precisions $(n,m_{\mathrm{out}})$ there exists a bounded-fan-in Boolean circuit of size and depth $\poly(n+m_{\mathrm{out}})$ computing the discretized map; replacing each gate by a constant-size neural emulator yields a deep network of size/depth $\poly(n+m_{\mathrm{out}})$ that achieves accuracy $\varepsilon=2^{-m_{\mathrm{out}}}$. We also relate these constructions to compositional approximation rates \cite{MhaskarPoggio2016b,poggio_deep_shallow_2017,Poggio2017,Poggio2023HowDS} and to optimization viewed as hierarchical search over sparse structures.
- Abstract（参考訳）: 本研究では,任意の固定入力/出力精度における 'emph{comppositionally sparse} (bounded-fan-in, polynomial-size) DAG 表現の存在と,目的の精度を達成するための対応する神経近似剤の存在を示唆することを示す。
具体的には、$f:[0,1]^d\to\R^m$ がビットdepthsの時間多項式で計算可能であれば、すべての精度に対して$(n,m_{\mathrm{out}})$ サイズと深さの有界ファンインブール回路が存在して $\poly(n+m_{\mathrm{out}})$ 離散写像を演算し、各ゲートを定数サイズのニューラルエミュレータで置き換えると、精度が$\varepsilon=2^{-m_{\mathrm{out}}} が得られる。
また、これらの構造は、合成近似レート \cite{MhaskarPoggio2016b,poggio_deep_shallow_2017,Poggio2017,Poggio2023HowDS} と、スパース構造上の階層的探索と見なされる最適化にも関係している。
関連論文リスト
- Mathematical Models of Computation in Superposition [0.9374652839580183]
重ね合わせは、現在のAIシステムを機械的に解釈する上で深刻な課題となる。
重ね合わせにおけるエンフン計算の数学的モデルを提案し, 重ね合わせはタスクを効率的に遂行するのに有効である。
我々は、重ね合わせで計算を実装するニューラルネットワークを解釈する研究の潜在的な応用について、結論付けている。
論文 参考訳（メタデータ） (2024-08-10T06:11:48Z) - Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。
逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。
設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
論文 参考訳（メタデータ） (2024-06-10T17:44:11Z) - Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。
シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文 参考訳（メタデータ） (2023-05-25T22:27:42Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳（メタデータ） (2021-11-28T14:08:25Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Deep Network Approximation for Smooth Functions [9.305095040004156]
幅$mathcalO(Nln N)$と深さ$mathcalO(L L)$の深いReLUネットワークは、ほぼ最適近似誤差で$fin Cs([0,1]d)$を近似できることを示す。
我々の推定は、それぞれ$NinmathbbN+$と$LinmathbbN+$で指定された任意の幅と深さに対して有効であるという意味では漸近的ではない。
論文 参考訳（メタデータ） (2020-01-09T15:06:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。