論文の概要: A Structural Complexity Analysis of Synchronous Dynamical Systems

• arxiv url: http://arxiv.org/abs/2312.08385v1
• Date: Tue, 12 Dec 2023 10:49:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-12-16 03:07:57.617587
• Title: A Structural Complexity Analysis of Synchronous Dynamical Systems
• Title（参考訳）: 同期力学系の構造複雑性解析
• Authors: Eduard Eiben, Robert Ganian, Thekla Hamm, Viktoriia Korchemna
• Abstract要約: 同期力学系における3つの問題について検討する。 これら3つの問題は、古典的な意味では難解であることが知られている。 定常木幅の例においても, いずれも難解であることを示す。
• 参考スコア（独自算出の注目度）: 33.788917274180484
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamic systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth - as the most prominent and ubiquitous structural parameter - and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree.
• Abstract（参考訳）: 同期力学系は、意見の拡散、病気の拡散、製品の採用など、ネットワークにおける様々な現象を捉えるためによく確立されたモデルである。 我々は、同期動的システムにおける3つの注目すべき問題について検討する: システムが開始設定から目標設定に移行するかどうか、システムが開始設定から収束するかどうか、およびシステムがすべての開始設定から収束する保証があるかどうか。 これら3つの問題はいずれも古典的な意味では難解であることが知られているが、より詳細なパラメータ化複雑性パラダイムを用いて、ネットワークの構造的パラメータの観点から、トラクタビリティの正確な境界の研究を開始する。 最初の結果として、木幅を最も顕著でユビキタスな構造パラメータとみなし、定常木幅の例においても3つの問題が難解であることを示す。 我々は、木幅の制約であるtreedepthによってパラメータ化された2つの問題に対して、固定パラメータアルゴリズムを用いてこの負の探索を補完する。 木深度と最大赤道度でパラメータ化した場合、この最終問題に対する固定パラメータアルゴリズムを用いて、木深度下での収束保証の類似アルゴリズムを除外することができる。

関連論文リスト

• On the Generalization Behavior of Deep Residual Networks From a Dynamical System Perspective [1.0388986221727612]
  ディープニューラルネットワーク(DNN)は非常に高度な機械学習を持ち、モデル深度は彼らの成功に中心的な役割を果たす。 本研究では,Rademacher複雑性,動的システムのフローマップ,ResNetsの深層限界における収束挙動を組み合わせることで,離散的および連続的残差ネットワーク(ResNets)の一般化誤差境界を確立する。 Findingsは、離散時間と連続時間の両方のResNet間の一般化の統一的な理解を提供し、サンプルの複雑さの順序と離散時間と連続時間設定の間の仮定のギャップを埋めるのに役立ちます。
  論文  参考訳（メタデータ） (2026-02-24T13:59:06Z)
• Twinning Complex Networked Systems: Data-Driven Calibration of the mABCD Synthetic Graph Generator [2.6776012440607784]
  本稿では、マッチング構成を推定し、関連するエラーを定量化する手法を提案する。 構成パラメータ間の強い相互依存が独立推定を弱め、代わりに共同予測アプローチを好んでいることから,本課題は非自明であることを示す。
  論文  参考訳（メタデータ） (2026-02-02T12:40:19Z)
• Multi-Scale Negative Coupled Information Systems (MNCIS): A Unified Spectral Topology Framework for Stability in Turbulence, AI, and Biology [1.4213973379473657]
  本研究は,MNCIS(Multi-Scale Negative Coupled Information System)フレームワークを一般化する。 グローバルな安定性には、状態依存のハイパスフィルタとして機能するアクティブなトポロジカル演算子 -- アダプティブスペクトル負結合(ASNC)が必要です。 ASNCはSGS(Global-enstrophy Adaptive Sub-Grid Scale)モデルとして機能し、不可視の限界を安定化し、人工超視力なしでコルモゴロフの5/3$慣性範囲を保存する。 以上の結果から, MNCISフレームワークは, 熱平衡に崩壊する複雑系と熱平衡を区別するために, 基底非依存の位相条件を提供する可能性が示唆された。
  論文  参考訳（メタデータ） (2026-01-06T21:11:33Z)
• Learning stochasticity: a nonparametric framework for intrinsic noise estimation [0.0]
  時系列データから状態依存の固有ノイズを推定するカーネルベースのフレームワークであるTrineを紹介する。 我々はTrineを生物学的および生態学的システムで検証し、隠れた力学を明らかにする能力を示した。
  論文  参考訳（メタデータ） (2025-11-17T18:52:05Z)
• Learning Discrete Bayesian Networks with Hierarchical Dirichlet Shrinkage [52.914168158222765]
  我々はDBNを学習するための包括的なベイズ的フレームワークについて詳述する。 我々は、並列ランゲヴィン提案を用いてマルコフ連鎖モンテカルロ(MCMC)アルゴリズムを新たに提案し、正確な後続サンプルを生成する。 原発性乳癌検体から予後ネットワーク構造を明らかにするために本手法を適用した。
  論文  参考訳（メタデータ） (2025-09-16T17:24:35Z)
• Subfunction Structure Matters: A New Perspective on Local Optima Networks [0.0]
  ローカルオプティマネットワーク(LON)は、フィットネス情報ランドスケープをキャプチャする。 サブファンクションに基づく情報を組み込むことで、LON分析をどのように改善できるかを検討する。
  論文  参考訳（メタデータ） (2025-04-17T07:31:11Z)
• Sequencing the Neurome: Towards Scalable Exact Parameter Reconstruction of Black-Box Neural Networks [7.0710630443004705]
  クエリアクセスのみでニューラルネットワークの正確なパラメータを推測することはNP-Hardの問題である。 本稿では,最大情報化サンプルを生成し,非線形関係を効率的に解き放つ新しいクエリ生成アルゴリズムを提案する。 本稿では,150万以上のパラメータを含む隠れネットワークを再構築し,最大パラメータ差が0.0001未満の7層のうち,最大かつ最も深い再構成を行った。
  論文  参考訳（メタデータ） (2024-09-27T21:02:04Z)
• Triadic-OCD: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence [2.1348070823841363]
  本稿では,証明可能な堅牢性,証明可能な最適性,保証された収束性を備えた3進OCDフレームワークを開発する。 提案アルゴリズムは、完全に非同期な分散方式で実現でき、単一のサーバにデータを送信する必要がなくなる。 Triadic-OCDの非漸近収束特性は理論的に解析され、$epsilon$-Optimal点を達成するための複雑さが導出される。
  論文  参考訳（メタデータ） (2024-05-03T10:10:11Z)
• The Boundaries of Tractability in Hierarchical Task Network Planning [15.926731632774768]
  階層型タスクネットワーク計画における3つの古典的問題に対するトラクタビリティの複雑性理論的境界について検討する。 これら3つの問題はすべて、一定部分順序幅の原始的タスクネットワークにおいて、時間内に解くことができることを示す。
  論文  参考訳（メタデータ） (2024-01-25T13:34:33Z)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
  論文  参考訳（メタデータ） (2023-12-15T21:31:30Z)
• HKNAS: Classification of Hyperspectral Imagery Based on Hyper Kernel Neural Architecture Search [104.45426861115972]
  設計したハイパーカーネルを利用して,構造パラメータを直接生成することを提案する。 我々は1次元または3次元の畳み込みを伴う画素レベルの分類と画像レベルの分類を別々に行う3種類のネットワークを得る。 6つの公開データセットに関する一連の実験は、提案手法が最先端の結果を得ることを示した。
  論文  参考訳（メタデータ） (2023-04-23T17:27:40Z)
• DepGraph: Towards Any Structural Pruning [68.40343338847664]
  我々は、CNN、RNN、GNN、Transformersのような任意のアーキテクチャの一般的な構造解析について研究する。 本稿では,階層間の依存関係を明示的にモデル化し,包括的にグループ化してプルーニングを行う汎用かつ完全自動な手法であるemphDependency Graph(DepGraph)を提案する。 本研究では,画像用ResNe(X)t,DenseNet,MobileNet,Vision Transformer,グラフ用GAT,3Dポイントクラウド用DGCNN,言語用LSTMなど,さまざまなアーキテクチャやタスクに関する手法を広範囲に評価し,言語用LSTMと並行して示す。
  論文  参考訳（メタデータ） (2023-01-30T14:02:33Z)
• NeuralSI: Structural Parameter Identification in Nonlinear Dynamical Systems [9.77270939559057]
  本稿では,構造同定のための新しいフレームワークであるNeuralSIについて検討する。 提案手法は, 制御方程式から非線形パラメータを推定することを目的とする。 トレーニングされたモデルは、標準条件と極端な条件の両方で外挿することもできる。
  論文  参考訳（メタデータ） (2022-08-26T16:32:51Z)
• Hyperparameter Tuning in Echo State Networks [0.0]
  Echo State Networksは、リカレントニューラルネットワークの一種で、大きなランダムに生成された貯水池と、線形回帰によってトレーニングされた少数のリードアウト接続を備えている。 共分散行列適応進化戦略(CMA-ES)に基づくハイパーパラメータチューニングの代替手法を提案する。
  論文  参考訳（メタデータ） (2022-07-16T16:20:01Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  本研究では,スカラー値を持つ一層ネットワークのクラスとユークリッドノルムで有界な入力について検討する。 隠蔽層重み行列のスペクトルノルムの制御は、一様収束を保証するには不十分であることを示す。 スペクトルノルム制御が十分であることを示す2つの重要な設定を解析する。
  論文  参考訳（メタデータ） (2022-02-13T07:12:02Z)
• Unified Field Theory for Deep and Recurrent Neural Networks [56.735884560668985]
  本稿では,再帰的ネットワークと深層ネットワークの両方に対する平均場理論の統一的,体系的な導出について述べる。 平均場理論への収束は、ディープネットワークよりもリカレントネットワークの方が典型的に遅い。 提案手法はガウス過程が1/n$の体系的展開の最下位次数であることを示す。
  論文  参考訳（メタデータ） (2021-12-10T15:06:11Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)

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

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