論文の概要: 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つの問題に対して、固定パラメータアルゴリズムを用いてこの負の探索を補完する。 木深度と最大赤道度でパラメータ化した場合、この最終問題に対する固定パラメータアルゴリズムを用いて、木深度下での収束保証の類似アルゴリズムを除外することができる。

関連論文リスト

• 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 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)

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

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