論文の概要: Network Learning with Semi-relaxed Gromov-Wasserstein

• arxiv url: http://arxiv.org/abs/2606.02223v1
• Date: Mon, 01 Jun 2026 13:21:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:32.098531
• Title: Network Learning with Semi-relaxed Gromov-Wasserstein
• Title（参考訳）: 半緩和Gromov-Wassersteinを用いたネットワーク学習
• Abstract要約: 大規模ネットワークの生成メカニズムを推定することは、機械学習における根本的な課題である。 確率的結合を許容し、代入問題を緩和することで、この問題に対処する。 我々のフレームワークは半相対的グロモフ=ワッサーシュタインの目的として定式化することができ、生成構造の低次元表現を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Estimating the generative mechanism of large-scale networks is a fundamental challenge in statistical machine learning. It requires the identification of the latent connectivity structure, which is in general an NP-hard combinatorial problem due to the absence of canonical node labels. We address this challenge by allowing for probabilistic couplings, thereby relaxing the assignment problem. Our estimation framework can be formulated as a semi-relaxed Gromov-Wasserstein objective and provides a low-dimensional representation of the generative structure. We solve this via a block-coordinate conditional gradient algorithm. Despite the relaxation, the resulting solution is typically deterministic: in fact, we show that the optimality gap between the relaxed solution and the deterministic assignment vanishes at rate $O(1/n)$, where $n$ is the number of nodes. This allows for tractable recovery of the underlying model and enables rigorous statistical analysis: we establish consistency and minimax-optimal convergence rates for both stochastic block models and Holder-smooth graphons. Our implementation scales efficiently with $n$, as demonstrated on both synthetic and real-world datasets.
• Abstract（参考訳）: 大規模ネットワークの生成メカニズムを推定することは、統計的機械学習の基本的な課題である。 一般に、標準ノードラベルの欠如によるNPハード組合せ問題である潜在接続構造を同定する必要がある。 確率的結合を許容し、代入問題を緩和することで、この問題に対処する。 我々の推定フレームワークは半相対的グロモフ=ワッサーシュタインの目的として定式化することができ、生成構造の低次元表現を提供する。 ブロック座標条件勾配アルゴリズムを用いてこの問題を解決する。 実際には、緩和された解と決定論的代入の間の最適性ギャップは、$O(1/n)$で消滅し、$n$はノードの数である。 確率ブロックモデルとホルダー・スムースグラフロンの整合性と最小最大収束率を確立する。 我々の実装は、合成データセットと実世界のデータセットの両方で示されるように、$n$で効率的にスケールする。

関連論文リスト

• 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)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Beyond Isotonization: Scalable Non-Crossing Quantile Estimation via Neural Networks for Student Growth Percentiles [0.0]
  学生成長パーセンタイル(SGP)は、アメリカ合衆国の国家評価システムで広く採用されており、独立した量子レグレッションとポストホック補正が採用されている。 我々は、このアプローチが基本的な方法論上の矛盾を含んでいることを実証する: 独立に見積もられた、潜在的に交差する量子化の間には、単調性が必要である。 ニューラルネットワークを用いたマルチクエンタイル回帰(NNQR)を実用的な代替手段として提案する。
  論文  参考訳（メタデータ） (2025-10-25T19:39:07Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound [11.086440815804226]
  Gromov-Wasserstein (GW) は、最適な輸送データセットに基づいて、構造化されたデータ間のノードグラフを定式化する。 本稿では,代入問題との関係から着想を得て,GWの代理としてGromov-Wasserstein離散性を提案する。
  論文  参考訳（メタデータ） (2022-05-12T02:10:56Z)
• Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees [23.256961881716595]
  エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。 分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
  論文  参考訳（メタデータ） (2022-01-21T01:26:08Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  連続観測データからBNのスパースDAG構造を学習する問題について検討する。 この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。 ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
  論文  参考訳（メタデータ） (2020-05-29T00:13:15Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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