論文の概要: Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics

• arxiv url: http://arxiv.org/abs/2607.18559v1
• Date: Mon, 20 Jul 2026 22:44:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-22 19:05:05.262109
• Title: Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics
• Title（参考訳）: グラウバーダイナミクスを用いたガウス図形モデルの混合・自由・信号最適学習
• Authors: Vignesh Tirukkonda, Gautam Dasarathy,
• Abstract要約: ランダム・スキャン・ガウス・グラウバー力学の1つの軌道からグラフの正確な復元について検討する。 混合のない2つのアルゴリズムを提案し、情報理論の下界の2$依存を実現する。
• 参考スコア（独自算出の注目度）: 5.844015313757267
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gaussian graphical model selection is usually studied under independent sampling, but in many applications the data arise as a single trajectory of a dependent stochastic process. We study exact recovery of the graph from one trajectory of random-scan Gaussian Glauber dynamics. Existing techniques for this problem either inherit the mixing time of the chain, which can be super-polynomial in the dimension $p$ without strong assumptions, or are suboptimal in the minimum normalized edge strength $κ$. We propose two algorithms that are mixing-free and attain the $κ^{-2}$ dependence of the information-theoretic lower bounds. Both instantiate a shared dueling-neighborhood search meta-algorithm with a local statistic built directly from the update sequence. The first fits a least-squares regression at the updates of each node and recovers the graph from $\widetilde O(pd^{2}/κ^{2})$ updates, where $d$ is the maximum degree. This algorithm's data requirement depends on a local conditioning quantity, but only logarithmically and is provably optimal even when the underlying chain mixes slowly. The second algorithm is based on counting occurences of a specific update pattern and requires $\widetilde O(pd^{4}/κ^{2})$ updates, with no dependence on any condition number. The central technical challenge is that both statistics are built from dependent, non-stationary observations. Our analysis tackles this by demonstrating how to extract fresh Gaussian innovations from the update sequence, which yields mixing-free control of appropriate quantities. Neither the algorithms nor their analyses invoke stationarity, a spectral gap, or mixing conditions, and all guarantees hold from an arbitrary initialization.
• Abstract（参考訳）: ガウス図形モデル選択は通常、独立したサンプリングの下で研究されるが、多くの応用において、データは依存確率過程の単一軌跡として生じる。 ランダム・スキャン・ガウス・グラウバー力学の1つの軌道からグラフの正確な復元について検討する。 この問題の既存のテクニックは、強い仮定なしで次元$p$で超ポリノミカルな鎖の混合時間を継承するか、最小正規化エッジ強度$κ$で最適である。 混合のない2つのアルゴリズムを提案し、情報理論の下界の$κ^{-2}$依存性を得る。 どちらも、更新シーケンスから直接構築されたローカル統計によって、共有デュエル近傍の検索メタアルゴリズムをインスタンス化する。 1つは各ノードの更新において最小二乗回帰に適合し、$\widetilde O(pd^{2}/κ^{2})$ updateからグラフを復元する。 このアルゴリズムのデータ要求は、局所的な条件付け量に依存するが、対数的にのみであり、基礎となる連鎖がゆっくりと混在しても証明可能な最適である。 第2のアルゴリズムは、特定の更新パターンの発生を数えることに基づいており、いかなる条件数にも依存せず、$\widetilde O(pd^{4}/κ^{2})$ updateを必要とする。 中心となる技術的課題は、両方の統計は依存的、非定常的な観測から成り立っていることである。 我々の分析は、適切な量の混合自由制御をもたらす更新シーケンスから新しいガウス的革新を抽出する方法を実証することによって、この問題に対処する。 アルゴリズムや解析は、定常性、スペクトルギャップ、混合条件を呼び起こさず、全ての保証は任意の初期化から成り立たない。

関連論文リスト

• Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing [13.453178572042125]
  グラウバー力学の単一軌道から$n$変数上の$d$スパースガウス図形モデルの構造を学習する作業について検討する。 このギャップによって部分的に動機づけられた条件付き時間アルゴリズムは、単一グラウバー軌道から軌道長保証を回復する。
  論文  参考訳（メタデータ） (2026-06-30T07:07:57Z)
• Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model [53.6316818897326]
  本稿では,2層ニューラルネットワークを時間内にトレーニングするための勾配に基づくアルゴリズムを提案する。 このアルゴリズムは未知の信号$star$と強く一致したスパース表現を学習することを示す。 私たちは、$star$が$k$-sparse for $k = o(sqrtd)$という設定にアプローチを拡張します。
  論文  参考訳（メタデータ） (2026-06-13T09:34:39Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。 適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-03-29T17:59:10Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。 エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。 ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
  論文  参考訳（メタデータ） (2022-02-08T12:58:14Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。 最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-30T10:42:48Z)

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

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