論文の概要: Optimal structure learning and conditional independence testing

• arxiv url: http://arxiv.org/abs/2507.05689v1
• Date: Tue, 08 Jul 2025 05:39:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-09 16:34:37.6359
• Title: Optimal structure learning and conditional independence testing
• Title（参考訳）: 最適構造学習と条件付き独立テスト
• Authors: Ming Gao, Yuhao Wang, Bryon Aragam,
• Abstract要約: 構造学習問題に対する最小値の最適値は条件付き独立試験における最小値の最大値によって決定されることを示す。 これらの設定における最適アルゴリズムは、PCアルゴリズムの適切な修正であることを示す。
• 参考スコア（独自算出の注目度）: 17.35311408855062
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish a fundamental connection between optimal structure learning and optimal conditional independence testing by showing that the minimax optimal rate for structure learning problems is determined by the minimax rate for conditional independence testing in these problems. This is accomplished by establishing a general reduction between these two problems in the case of poly-forests, and demonstrated by deriving optimal rates for several examples, including Bernoulli, Gaussian and nonparametric models. Furthermore, we show that the optimal algorithm in these settings is a suitable modification of the PC algorithm. This theoretical finding provides a unified framework for analyzing the statistical complexity of structure learning through the lens of minimax testing.
• Abstract（参考訳）: 本研究では,最適構造学習と最適条件独立性テストの基本的な関連性を確立し,これらの問題における条件独立性テストの最小値率によって,構造学習問題の最小値が決定されることを示す。 これは、ポリフォレストの場合のこれらの2つの問題間の一般還元を確立し、ベルヌーイ、ガウスおよび非パラメトリックモデルを含むいくつかの例に対して最適な速度を導出することで証明される。 さらに、これらの設定における最適アルゴリズムは、PCアルゴリズムの適切な修正であることを示す。 この理論的発見は、ミニマックステストのレンズを通して構造学習の統計的複雑さを分析する統一的なフレームワークを提供する。

関連論文リスト

• A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization [4.703514158152835]
  Bilevelは最近、幅広いアプリケーションと高度な階層最適化機能のために、機械学習に大きな注目を集めている。 本稿では,双方向最適化手法の開発と解析を行うためのBOというプラグイン・アンド・プレイフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-05-02T13:26:43Z)
• Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation [4.239829789304117]
  最適学習の設定にはPAC-ベイズ理論を用いる。 証明可能な一般化保証付き最適化アルゴリズムを学習する最初のフレームワークを提示する。 学習アルゴリズムは、(決定論的)最悪のケース分析から得られた関連アルゴリズムを確実に上回ります。
  論文  参考訳（メタデータ） (2024-04-04T08:24:57Z)
• Optimal estimation of Gaussian (poly)trees [25.02920605955238]
  分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。 最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。 第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
  論文  参考訳（メタデータ） (2024-02-09T12:58:36Z)
• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。 構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。 本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-18T14:57:21Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)

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

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