論文の概要: Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach

• arxiv url: http://arxiv.org/abs/2502.08536v1
• Date: Wed, 12 Feb 2025 16:21:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-13 13:44:47.365718
• Title: Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach
• Title（参考訳）: グラフ情報を用いた行列補完:確率的非凸最適化手法
• Authors: Yao Wang, Yiyang Yang, Kaidong Wang, Shanxing Gao, Xiuwu Liao,
• Abstract要約: 本稿では,グラフを用いた行列補完の問題について,変数間の相互関係を表す側情報として考察する。 本稿では,事前条件付き投射降下法に基づくGSGDと呼ばれるグラフ正規化行列補完アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.235925587710112
• License:
• Abstract: We consider the problem of matrix completion with graphs as side information depicting the interrelations between variables. The key challenge lies in leveraging the similarity structure of the graph to enhance matrix recovery. Existing approaches, primarily based on graph Laplacian regularization, suffer from several limitations: (1) they focus only on the similarity between neighboring variables, while overlooking long-range correlations; (2) they are highly sensitive to false edges in the graphs and (3) they lack theoretical guarantees regarding statistical and computational complexities. To address these issues, we propose in this paper a novel graph regularized matrix completion algorithm called GSGD, based on preconditioned projected gradient descent approach. We demonstrate that GSGD effectively captures the higher-order correlation information behind the graphs, and achieves superior robustness and stability against the false edges. Theoretically, we prove that GSGD achieves linear convergence to the global optimum with near-optimal sample complexity, providing the first theoretical guarantees for both recovery accuracy and efficacy in the perspective of nonconvex optimization. Our numerical experiments on both synthetic and real-world data further validate that GSGD achieves superior recovery accuracy and scalability compared with several popular alternatives.
• Abstract（参考訳）: 本稿では,グラフを用いた行列補完の問題について,変数間の相互関係を表す側情報として考察する。 鍵となる課題は、グラフの類似性構造を活用して行列回復を強化することである。 既存のアプローチは主にグラフのラプラシア正規化に基づいており、(1) 近傍変数間の類似性のみに焦点をあてるが、長距離相関を見渡す、(2) グラフの偽エッジに非常に敏感である、(3) 統計的および計算的複雑さに関する理論的保証を欠いている、といういくつかの制限がある。 本稿では,事前条件付き勾配降下法に基づくGSGDと呼ばれる新しいグラフ正規化行列補完アルゴリズムを提案する。 GSGDはグラフの背後にある高次相関情報を効果的に取得し、偽エッジに対して優れた堅牢性と安定性を実現することを実証する。 理論的には、GSGD が大域的最適値への線形収束をほぼ最適サンプルの複雑さで達成し、非凸最適化の観点から、回復精度と有効性の両方に関する最初の理論的保証を提供する。 合成データと実世界のデータの両方に関する数値実験により、GSGDは、いくつかの一般的な代替品と比較して、回復精度とスケーラビリティに優れることを確認した。

関連論文リスト

• Consistency of augmentation graph and network approximability in contrastive learning [3.053989095162017]
  拡張グラフ Laplacian の点次およびスペクトルの整合性について解析する。 ラプラシアンは自然データ多様体上の重み付きラプラス・ベルトラミ作用素に収束することを示す。 これらの整合性は、グラフラプラシアスペクトルが多様体幾何学を効果的に捉えることを保証する。
  論文  参考訳（メタデータ） (2025-02-06T18:55:51Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization [0.626226809683956]
  グラデーションに基づくグラフ空間幅最適化法として,グラフRG-IHTとグラフSG-IHTの2つの手法を提案する。 我々は,手法が勾配に基づく枠組みを楽しむことを示す理論解析の一般性を示す。
  論文  参考訳（メタデータ） (2024-07-24T03:26:26Z)
• Gradient-Based Spectral Embeddings of Random Dot Product Graphs [7.612218105739107]
  本稿では,RDPG (Random Dot Product Graph) の組込み問題の解法について述べる。 そこで我々は, 結果の多様体に対して, 実現可能な新しい最適化手法を開発した。 当社のオープンソースアルゴリズムの実装はスケーラブルで、エッジデータに欠ける堅牢さと異なり、ストリーミンググラフからゆっくりと、潜伏した位置を追跡することができます。
  論文  参考訳（メタデータ） (2023-07-25T21:09:55Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  構造方程式モデル(SEM)は、有向非巡回グラフ(DAG)を介して表される因果関係を推論する効果的な枠組みである。 近年の進歩により、観測データからDAGの有効最大点推定が可能となった。 線形ガウス SEM を特徴付ける DAG 上の分布を推定するための変分フレームワークである BCD Nets を提案する。
  論文  参考訳（メタデータ） (2021-12-06T03:35:21Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  近年のDAG構造学習は連続的な非巡回性制約を伴う制約付き連続最適化問題として定式化されている。 本稿では,DAG空間の重み付き隣接行列を直接モデル化し,学習するための新しい学習フレームワークを提案する。 本手法は, 線形および一般化された構造方程式モデルにおいて, ベースラインDAG構造学習法よりも精度が高いが, 効率がよいことを示す。
  論文  参考訳（メタデータ） (2021-06-14T07:11:36Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。 従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
  論文  参考訳（メタデータ） (2021-05-12T06:47:34Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)

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

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