論文の概要: On the Representational Geometry of Dynamic Programs

• arxiv url: http://arxiv.org/abs/2608.25034v1
• Date: Tue, 25 Aug 2026 18:23:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-27 14:15:15.409568
• Title: On the Representational Geometry of Dynamic Programs
• Title（参考訳）: 動的プログラムの表現幾何学について
• Abstract要約: 標準的なニューラルアーキテクチャは、しばしば動的プログラミング(DP)ターゲットのより長い入力に一般化できない。 我々はこの難易度を幾何学的に調査する。 直列および並列合成は、より小さなサブDAGから全てのDAGトポロジーを構築するのに失敗する。
• 参考スコア（独自算出の注目度）: 0.17188280334580197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels --- formal polynomials and their computed functions --- connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.
• Abstract（参考訳）: 標準的なニューラルアーキテクチャは、しばしば動的プログラミング(DP)ターゲットのより長い入力に一般化できない。 我々はこの難易度を幾何学的に調査する。 すべての有限 min-plus DP は DAG 上の最短経路であり、これは同等に、ニュートン多面体がどの経路が勝つかの決定境界を符号化する熱帯多項式である。 これらの3つの記述(グラフ、多項式、ポリヘドロン)は、すべての構造的冗長性を特徴づける演算によって連結される2つのレベル(形式多項式とその計算関数)で同型半環であることを示す。 決定境界は長さ$T$で、境界は$T+1$で決定されますか? 構造否定は2つある。 半環の次元を減少させる2つのネイティブな方法(各恒等式に変数をセットする)は、射影的でも、常にDP内で閉じていない。 直列および並列合成では、より小さなサブDAGから全てのDAGトポロジを構築することができず、終端のみの操作でも全てのDP合成をキャプチャできない。

関連論文リスト

• Restricted Dynamic Geometric Complexity: Path-Space Reduction and Möbius--Jacobi Response [0.0]
  経路空間値問題として制限された動的幾何学的複雑性について検討する。 主な応答結果は、アダマール状態空間におけるグローバルである。
  論文  参考訳（メタデータ） (2026-07-08T09:36:45Z)
• Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids [12.16068230936605]
  対角ユニタリ(Diagonal Unitary)は、量子演算のリソース集約型クラスである。 合成と編集を共同で行う。 GPFを2次元近傍グリッドにコンパイルすることは、この最適性を保っていることを示す。
  論文  参考訳（メタデータ） (2026-06-16T06:51:26Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs [0.0]
  実数値力学により進化した実数値状態について検討する。 これら3つの状態は、実数値力学によって進化した連続体-実数値状態に作用する。
  論文  参考訳（メタデータ） (2026-04-27T11:48:49Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Universal Hirschberg for Width Bounded Dynamic Programs [0.0]
  ヒルシュベルクのアルゴリズムは、格子動的プログラム(DP)上の中点二項による$O(N2)$から$O(N)$へ、最も長い共通部分列問題の空間複雑性を減少させる。 我々は、その基礎となるアイデアが、有向非巡回グラフ(DP DAG)に局所的依存を持つ広範な動的プログラムのクラスに一般化されることを示す。 前方シングルパスモデルでは$()$空間項は避けられないことを示し、ストリーミング設定における推測される$sqrtT$-type障壁について議論する。
  論文  参考訳（メタデータ） (2025-12-10T22:26:22Z)
• Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
  上界の先導手法である三点法は、大高精度半確定プログラム(SDP)の解法に問題を還元する。 我々は、SDP構成を、ポリシーが一連の許容成分からSDP定式化を組み立てる逐次決定過程、SDPゲームとして定式化する。 従来からある幾何学的問題において,モデルに基づく探索が計算の進歩を推し進めることができることを示す。
  論文  参考訳（メタデータ） (2025-12-04T14:11:52Z)
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks [0.0]
  正準多面体のすべての次元の領域と面を決定する。 この全標準構造を計算するアルゴリズムを提案する。 得られたアルゴリズムは、中間ニューロンの数に時間とともに数値的に安定し、すべての次元にわたって正確な情報を得る。
  論文  参考訳（メタデータ） (2022-07-15T18:36:12Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  本稿では,3次元形状間の幾何学的一貫したマッピング空間をグローバルに最適化するスケーラブルなアルゴリズムを提案する。 従来の解法よりも数桁高速なラグランジュ双対問題と結合した新しい原始問題を提案する。
  論文  参考訳（メタデータ） (2022-04-27T09:47:47Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。 例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
  論文  参考訳（メタデータ） (2020-08-06T09:50:29Z)

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

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