論文の概要: CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

• arxiv url: http://arxiv.org/abs/2609.09255v1
• Date: Tue, 08 Sep 2026 15:12:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.747178
• Title: CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs
• Title（参考訳）: CAST: グラフ上の近似Coleskyのための正準近似Schur木
• Authors: Meher Chaitanya, Cameron Musco, Aristides Gionis,
• Abstract要約: CAST(Canonical Approximate Schur Tree)を導入する。 すべての実現は接続され、正確にd-1エッジを含むが、選択された各エッジを木非包含確率の逆数で重み付けすることで更新は不偏となる。 結果として得られた更新は未バイアスで接続され、正確に$O(d)$時間にサンプリングでき、正規化されたローカルSchurエラーの第2モーメントに1/$のバインドを満足する。
• 参考スコア（独自算出の注目度）: 28.99342075394145
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time and store the resulting sparse approximate factorization, the \emph{factor}, whose construction cost is amortized across these solves. But eliminating a vertex, the \emph{pivot}, creates a dense Schur-complement clique among its $d$ active neighbors. We introduce CAST (Canonical Approximate Schur Tree), which replaces this clique with a weighted random spanning tree sampled directly from it. Every realization is connected and contains exactly d-1 edges, while reweighting each selected edge by the reciprocal of its tree-inclusion probability makes the update unbiased. The distribution is independent of the ordering of the pivot neighbors, and we prove that its leverage-score marginals minimize the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators. We also introduce CAST-$ρ$, which replaces each pivot neighbor with $ρ$ copies, each carrying a $1/ρ$ share of that neighbor's incident weight, samples a weighted random spanning tree on the expanded clique, and contracts the copies back to the original neighborhood. The resulting update remains unbiased and connected, can be sampled exactly in $O(ρd)$ time, and satisfies a $1/ρ$ bound on the second moment of the normalized local Schur error. Increasing $ρ$ therefore reduces certified local sampling variability, but may increase construction cost and downstream fill. Empirically, we observe that CAST-1 is the faster default, whereas CAST-2 is preferable when its additional edge contributions remain inexpensive.
• Abstract（参考訳）: 拡散推定、ランク付け、半教師付き学習、ネットワーク最適化などのグラフデータワークロードは、同じ係数行列を持つ多くのラプラシアンもしくは対称に支配的なM-行列(SDDM)システムを解くことが多い。 近似チョレスキー条件付きプレコンディショナーは、頂点を一度に排除し、結果として生じるスパース近似因数分解である「emph{factor}」を記憶する。 しかし、頂点を除去する「emph{pivot}」は、その$d$アクティブな隣人の間でシュル補集合の高密度な傾きを生み出す。 我々はCAST(Canonical Approximate Schur Tree)を導入し、この斜めをそこから直接サンプリングしたランダムスパンニングツリーに置き換える。 すべての実現は接続され、正確にd-1エッジを含むが、選択された各エッジを木非包含確率の逆数で重み付けすることで更新は不偏となる。 この分布はピボット近傍の順序とは無関係であり、そのレバレッジスコア限界は、非偏りの逆辺の1木推定器における最大の正規化再重み付きエッジ寄与を最小化することを証明している。 また、CAST-$ρ$を導入し、それぞれのピボット隣人を$ρ$コピーに置き換え、それぞれが隣人のインシデント重量の1/ρ$のシェアを持ち、拡張された斜め上に散らばったランダムな木をサンプリングし、元の近所にコピーを契約する。 結果として得られた更新は、未バイアスで接続され、正確に$O(ρd)$時間にサンプリングでき、正規化されたローカルなSchurエラーの第2モーメントに1/ρ$バウンドを満足する。 したがって、$ρ$の増加は、認証されたローカルサンプリングのばらつきを減らすが、建設コストと下流の埋め合わせを増加させる可能性がある。 実証的には、CAST-1がより高速なデフォルトであるのに対し、CAST-2は、追加のエッジコントリビューションが安価である場合に好適である。

関連論文リスト

• Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
  重畳の非線形観測回数が限られていることから, スパースベクトルの回復を考察する。 本稿では, 一般化畳み込みペナルティとハマー化データ忠実度を組み合わせた正規化に基づくフレームワークを提案する。 仮に局所的な定常点を保った位数$sqrtslog(n)/m$の誤差境界を導出する。
  論文  参考訳（メタデータ） (2026-07-12T07:29:39Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。 本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。 実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
  論文  参考訳（メタデータ） (2026-06-04T16:04:31Z)
• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  永続性に基づく位相最適化は、点クラウド $X の部分集合 mathbbRd$ を $L(X) = ell(mathrmDgm(X))$ という形の目的を最小化することによって変形する。 実際、最適化は2つの結合した問題によって制限される: 永続ホモロジーは典型的にはサブサンプル上で計算され、結果として生じる位相勾配は非常にスパースであり、非ゼロ更新を受けるアンカーポイントはわずかである。
  論文  参考訳（メタデータ） (2026-05-09T15:47:20Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Empirical complexity of comparator-based nearest neighbor descent [0.0]
  K$-nearest 隣り合うアルゴリズムの Java 並列ストリームの実装を示す。 Kullback-Leiblerの発散比較器による実験は、$K$-nearest近くの更新ラウンドの数が直径の2倍を超えないという予測を支持している。
  論文  参考訳（メタデータ） (2022-01-30T21:37:53Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。 特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
  論文  参考訳（メタデータ） (2020-07-22T18:18:28Z)
• 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)

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

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