論文の概要: Solution Path of Time-varying Markov Random Fields with Discrete Regularization

• arxiv url: http://arxiv.org/abs/2307.13750v1
• Date: Tue, 25 Jul 2023 18:19:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-27 14:47:49.860049
• Title: Solution Path of Time-varying Markov Random Fields with Discrete Regularization
• Title（参考訳）: 離散正則化を伴う時変マルコフ確率場の解経路
• Authors: Salar Fattahi and Andres Gomez
• Abstract要約: 本研究では,時間変化確率場(MRF)をパラメータの離散的および時間的正規化で推定する問題について検討する。 すべての空間レベルの解は$mathcalO(Tp3)$で得られ、$T$は時間ステップの数、$p$は任意の時間における未知のパラメータの数である。
• 参考スコア（独自算出の注目度）: 7.79230326339002
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of inferring sparse time-varying Markov random fields (MRFs) with different discrete and temporal regularizations on the parameters. Due to the intractability of discrete regularization, most approaches for solving this problem rely on the so-called maximum-likelihood estimation (MLE) with relaxed regularization, which neither results in ideal statistical properties nor scale to the dimensions encountered in realistic settings. In this paper, we address these challenges by departing from the MLE paradigm and resorting to a new class of constrained optimization problems with exact, discrete regularization to promote sparsity in the estimated parameters. Despite the nonconvex and discrete nature of our formulation, we show that it can be solved efficiently and parametrically for all sparsity levels. More specifically, we show that the entire solution path of the time-varying MRF for all sparsity levels can be obtained in $\mathcal{O}(pT^3)$, where $T$ is the number of time steps and $p$ is the number of unknown parameters at any given time. The efficient and parametric characterization of the solution path renders our approach highly suitable for cross-validation, where parameter estimation is required for varying regularization values. Despite its simplicity and efficiency, we show that our proposed approach achieves provably small estimation error for different classes of time-varying MRFs, namely Gaussian and discrete MRFs, with as few as one sample per time. Utilizing our algorithm, we can recover the complete solution path for instances of time-varying MRFs featuring over 30 million variables in less than 12 minutes on a standard laptop computer. Our code is available at \url{https://sites.google.com/usc.edu/gomez/data}.
• Abstract（参考訳）: パラメータの離散的および時間的正則化が異なるsparse time-varying markov random fields (mrfs) を推定する問題について検討する。 離散正則化の難しさのため、この問題のほとんどのアプローチは、緩和された正則化を伴ういわゆる最大準正則推定(MLE)に依存しており、これは理想的な統計的性質や、現実的な環境で遭遇する次元へのスケールにはならない。 本稿では、MLEパラダイムから脱却し、推定パラメータの空間性を促進するために、厳密な離散正規化を伴う制約付き最適化問題に頼り、これらの課題に対処する。 我々の定式化の非凸性と離散性にもかかわらず、全ての空間レベルに対して効率的にパラメトリックに解けることを示す。 より具体的には、すべての空間レベルに対する時間変化MRFの解パス全体は、$\mathcal{O}(pT^3)$で得られ、$T$は時間ステップの数、$p$は任意の時間における未知のパラメータの数である。 解経路の効率的かつパラメトリックなキャラクタリゼーションは,正規化値の変動にパラメータ推定が必要となるクロスバリデーションに適した手法である。 その単純さと効率性にもかかわらず,提案手法は,ガウス型と離散型 MRF の異なるクラス,すなわちガウス型と離散型 MRF に対して,1時間に1つのサンプルで確実に小さな推定誤差を達成できることを示す。 このアルゴリズムを用いることで、標準のラップトップコンピュータで112分以内で3000万以上の変数を持つ時間変化型MRFの完全な解経路を復元できる。 私たちのコードは \url{https://sites.google.com/usc.edu/gomez/data} で利用可能です。

関連論文リスト

• Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation [0.135975510645475]
  本研究は, 安全スクリーニングのルールを導出し, インテリジェンスサンプルを廃棄する。 新しいテストは、特に高次元のパラメータ空間に関わる問題に対して、より高速に計算できる。 本稿では,ラッソ法の正規化経路を計算するホモトピーアルゴリズムを,正方形 $ell_$-penalty に対して再パラメータ化する方法を示す。
  論文  参考訳（メタデータ） (2023-10-13T08:10:46Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Robust Multi-view Registration of Point Sets with Laplacian Mixture Model [25.865100974015412]
  重み付きラプラシアン分布に基づいて複数の点集合を整列させる新しい確率的生成法を提案する。 本稿では,提案手法の利点を,ベンチマークの挑戦的データセットに対する最先端手法と比較することによって示す。
  論文  参考訳（メタデータ） (2021-10-26T14:49:09Z)
• Distributionally Robust Optimization with Markovian Data [8.126833795693699]
  本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。 本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
  論文  参考訳（メタデータ） (2021-06-12T10:59:02Z)
• Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees [10.127456032874978]
  スパース変換型MRFの推論に制約付き最適化問題を新たに導入する。 1時間未満で5億以上の変数を持つ疎交換グラフィカルモデルを正確に推定することができる。
  論文  参考訳（メタデータ） (2021-02-06T13:53:00Z)
• The Variational Method of Moments [65.91730154730905]
  条件モーメント問題は、観測可能量の観点から構造因果パラメータを記述するための強力な定式化である。 OWGMMの変動最小値再構成により、条件モーメント問題に対する非常に一般的な推定器のクラスを定義する。 同じ種類の変分変換に基づく統計的推測のためのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-12-17T07:21:06Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)

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

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