論文の概要: Identifiability of the minimum-trace directed acyclic graph and hill climbing algorithms without strict local optima under weakly increasing error variances

• arxiv url: http://arxiv.org/abs/2508.05706v1
• Date: Thu, 07 Aug 2025 04:01:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:05.94874
• Title: Identifiability of the minimum-trace directed acyclic graph and hill climbing algorithms without strict local optima under weakly increasing error variances
• Title（参考訳）: 誤差分散の弱増加下での厳密な局所最適化を伴わない最小トレース有向非巡回グラフとヒルクライミングアルゴリズムの同定可能性
• Authors: Hyunwoong Chang, Jaehoan Kim,
• Abstract要約: ガウス線型構造方程式モデルにおける真基底非巡回グラフ(DAG)が最小トレースDAGと同定可能であることを証明した。 計算面では、ランダム・ト・ランドム(R2R)近傍のヒルクライミングアルゴリズムが厳密な局所最適化を含まないことを証明している。
• 参考スコア（独自算出の注目度）: 1.1279808969568255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that the true underlying directed acyclic graph (DAG) in Gaussian linear structural equation models is identifiable as the minimum-trace DAG when the error variances are weakly increasing with respect to the true causal ordering. This result bridges two existing frameworks as it extends the identifiable cases within the minimum-trace DAG method and provides a principled interpretation of the algorithmic ordering search approach, revealing that its objective is actually to minimize the total residual sum of squares. On the computational side, we prove that the hill climbing algorithm with a random-to-random (R2R) neighborhood does not admit any strict local optima. Under standard settings, we confirm the result through extensive simulations, observing only a few weak local optima. Interestingly, algorithms using other neighborhoods of equal size exhibit suboptimal behavior, having strict local optima and a substantial number of weak local optima.
• Abstract（参考訳）: ガウス線形構造方程式モデルにおける真基底非巡回グラフ(DAG)は、真の因果順序に関して誤差分散が弱いときに最小トレースDAGと同定可能であることを証明した。 この結果は,最小トレースDAG法における識別可能なケースを拡張し,アルゴリズム順序付け探索手法の原理的解釈を提供し,その目的が正方形全体の残余和を最小化することにあることを明らかにした。 計算面では、ランダム・ト・ランドム(R2R)近傍のヒルクライミングアルゴリズムが厳密な局所最適化を含まないことを証明している。 標準条件下では, 局所最適化の弱い部分のみを観測し, 広範囲なシミュレーションにより結果を確認する。 興味深いことに、同じ大きさの他の地区を用いたアルゴリズムは、厳密な局所最適とかなりの数の弱い局所最適を持つ、最適以下の挙動を示す。

関連論文リスト

• Zeroth-Order Optimization Finds Flat Minima [51.41529512093436]
  標準二点推定器によるゼロ階最適化は、ヘッセンの小さなトレースを持つ解を好むことを示す。 さらに、凸関数と十分に滑らかな関数に対する近似平坦なミニマに対して、ゼロ階最適化の収束率を提供する。
  論文  参考訳（メタデータ） (2025-06-05T17:59:09Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate [14.191310794366075]
  本稿では,機械学習における多種多様な応用を見出した低ランク行列最適化について述べる。 雑音モデルが任意である一般目的関数に対するランダムな汚職に対処できるフレームワークを開発する。 RIP定数が1/3$以上である場合、地平線付近の局所領域における問題の急激な局所最小値の幾何学を特徴付ける。
  論文  参考訳（メタデータ） (2022-03-08T07:44:47Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• The Minimax Complexity of Distributed Optimization [0.0]
  分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。 私は「間欠的コミュニケーション設定」の具体例に焦点をあてる コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
  論文  参考訳（メタデータ） (2021-09-01T15:18:33Z)
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures [8.556763944288116]
  非平衡クラスタにおいても,ベイズ最適一般化誤差を実現する構成が存在することを示す。 また,平均二乗誤差損失の幅の広い平らな最小値を目標とするアルゴリズム的ケースについても検討した。
  論文  参考訳（メタデータ） (2020-10-27T01:32:03Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks [45.3591788771536]
  我々はベイズネットワーク学習のためのNOTEARSという連続最適化フレームワークを再検討する。 本論文では,NOTEARSに対するKarush-Kuhn-Tucker最適条件は,自明な場合を除いて満足できないことを示す。 ローカル検索の組み合わせは、元のNOTEARSよりも正確かつ効率的である。
  論文  参考訳（メタデータ） (2020-10-18T22:59:37Z)
• Entropic gradient descent algorithms and wide flat minima [6.485776570966397]
  広い平坦領域に属する最小値に対応するベイズ最適点推定器が存在することを解析的に示す。 解析を広範囲な数値検証により深層学習シナリオに拡張する。 計算が容易な平坦度測定は、テスト精度と明確な相関を示す。
  論文  参考訳（メタデータ） (2020-06-14T13:22:19Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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