論文の概要: Bayesian Inference of Random Dot Product Graphs via Conic Programming
- arxiv url: http://arxiv.org/abs/2101.02180v1
- Date: Wed, 6 Jan 2021 18:29:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-11 03:30:24.271147
- Title: Bayesian Inference of Random Dot Product Graphs via Conic Programming
- Title(参考訳): コーニックプログラミングによるランダムドット製品グラフのベイズ推定
- Authors: David Wu, David R. Palmer, Daryl R. Deford
- Abstract要約: 本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定する凸コーンプログラムを提案する。
また、この手法がケイトクラブグラフと米国上院の投票グラフの潜在構造を復元することを示した。
- 参考スコア(独自算出の注目度): 1.7188280334580195
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a convex cone program to infer the latent probability matrix of a
random dot product graph (RDPG). The optimization problem maximizes the
Bernoulli maximum likelihood function with an added nuclear norm regularization
term. The dual problem has a particularly nice form, related to the well-known
semidefinite program relaxation of the MaxCut problem. Using the primal-dual
optimality conditions, we bound the entries and rank of the primal and dual
solutions. Furthermore, we bound the optimal objective value and prove
asymptotic consistency of the probability estimates of a slightly modified
model under mild technical assumptions. Our experiments on synthetic RDPGs not
only recover natural clusters, but also reveal the underlying low-dimensional
geometry of the original data. We also demonstrate that the method recovers
latent structure in the Karate Club Graph and synthetic U.S. Senate vote graphs
and is scalable to graphs with up to a few hundred nodes.
- Abstract(参考訳): 本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定するための凸錐プログラムを提案する。
最適化問題は、追加の核ノルム正規化項でベルヌーイ最大度関数を最大化する。
双対問題は、MaxCut問題のよく知られた半定値プログラム緩和に関連して、特によい形式を持つ。
原始双対最適性条件を用いて、原始解と双対解のエントリとランクを制限した。
さらに, 最適目的値を限定し, 軽度な技術的仮定の下で, わずかに修正されたモデルの確率推定の漸近的一貫性を証明した。
RDPGの合成実験は、自然クラスターを復元するだけでなく、元のデータの低次元形状も明らかにする。
また,この手法は,空手クラブグラフとアメリカ合衆国上院世論投票グラフの潜在構造を復元し,数百ノードまでのグラフに拡張可能であることを実証した。
関連論文リスト
- Graph Matching via convex relaxation to the simplex [6.327393762036104]
本稿では,2つの入力グラフの最適アライメントを求めるグラフマッチング問題に対処する。
この問題に対処するための一般的なアプローチは、NP-hard emphQuadratic Assignment Problem (QAP) の凸緩和である。
単位単純度に新しい凸緩和を導入し、この問題を解決するための閉形式反復を用いた効率的なミラー降下スキームを開発する。
論文 参考訳(メタデータ) (2023-10-31T16:44:26Z) - Gradient-Based Spectral Embeddings of Random Dot Product Graphs [7.612218105739107]
本稿では,RDPG (Random Dot Product Graph) の組込み問題の解法について述べる。
そこで我々は, 結果の多様体に対して, 実現可能な新しい最適化手法を開発した。
当社のオープンソースアルゴリズムの実装はスケーラブルで、エッジデータに欠ける堅牢さと異なり、ストリーミンググラフからゆっくりと、潜伏した位置を追跡することができます。
論文 参考訳(メタデータ) (2023-07-25T21:09:55Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳(メタデータ) (2023-06-29T01:20:44Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳(メタデータ) (2023-02-08T08:17:43Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳(メタデータ) (2021-09-17T17:46:12Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained
Graphical Models? [13.572602792770288]
ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。
我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
論文 参考訳(メタデータ) (2020-06-26T12:06:10Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳(メタデータ) (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。