論文の概要: Generalization Bounds for Semi-supervised Matrix Completion with Distributional Side Information
- arxiv url: http://arxiv.org/abs/2511.13049v2
- Date: Fri, 21 Nov 2025 12:07:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-24 14:08:26.077061
- Title: Generalization Bounds for Semi-supervised Matrix Completion with Distributional Side Information
- Title（参考訳）: 分布側情報を用いた半教師付き行列補完の一般化境界
- Authors: Antoine Ledent, Mun Chong Soo, Nong Minh Hieu,
- Abstract要約: 本稿では, 基底真理$R$行列と未知のサンプリング分布$P$が低ランク行列である行列完備化問題について検討する。
真の一般化誤差は、それぞれ$P$と基底真理行列$ground$の見積もりに対応する独立した誤差項に分解されることを示す。
- 参考スコア（独自算出の注目度）: 14.149880038429485
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a matrix completion problem where both the ground truth $R$ matrix and the unknown sampling distribution $P$ over observed entries are low-rank matrices, and \textit{share a common subspace}. We assume that a large amount $M$ of \textit{unlabeled} data drawn from the sampling distribution $P$ is available, together with a small amount $N$ of labeled data drawn from the same distribution and noisy estimates of the corresponding ground truth entries. This setting is inspired by recommender systems scenarios where the unlabeled data corresponds to `implicit feedback' (consisting in interactions such as purchase, click, etc. ) and the labeled data corresponds to the `explicit feedback', consisting of interactions where the user has given an explicit rating to the item. Leveraging powerful results from the theory of low-rank subspace recovery, together with classic generalization bounds for matrix completion models, we show error bounds consisting of a sum of two error terms scaling as $\widetilde{O}\left(\sqrt{\frac{nd}{M}}\right)$ and $\widetilde{O}\left(\sqrt{\frac{dr}{N}}\right)$ respectively, where $d$ is the rank of $P$ and $r$ is the rank of $M$. In synthetic experiments, we confirm that the true generalization error naturally splits into independent error terms corresponding to the estimations of $P$ and and the ground truth matrix $\ground$ respectively. In real-life experiments on Douban and MovieLens with most explicit ratings removed, we demonstrate that the method can outperform baselines relying only on the explicit ratings, demonstrating that our assumptions provide a valid toy theoretical setting to study the interaction between explicit and implicit feedbacks in recommender systems.
- Abstract（参考訳）: 我々は、基底真理$R$行列と未知のサンプリング分布$P$が低ランク行列である行列完備化問題と、共有部分空間であるtextit{share a common subspace} について検討する。
サンプリング分布$P$から引き出された大量の$M$と、同じ分布から引き出されたラベル付きデータの少量の$N$と、対応する基底真理エントリのノイズ推定が可能であると仮定する。
この設定は、ラベル付けされていないデータが'implicit feedback'(購入、クリックなどのインタラクションを構成する)に対応し、ラベル付けされたデータが'explicit feedback'に対応し、ユーザがアイテムに明示的な評価を与えているインタラクションからなるリコメンデーションシステムシナリオにインスパイアされている。
低ランク部分空間回復の理論による強力な結果を活用すると、行列完備化モデルの古典的な一般化境界とともに、$\widetilde{O}\left(\sqrt {\frac{nd}{M}}\right)$と$\widetilde{O}\left(\sqrt {\frac{dr}{N}}\right)$の2つの誤差項の合計からなる誤差境界が示され、$d$は$P$のランク、$r$は$M$のランクである。
合成実験において、真の一般化誤差は自然に$P$と基底真理行列$\ground$の見積もりに対応する独立した誤差項に分裂することを確認した。
実生活におけるDoubanとMovieLensの明確な評価を除いた実験では,提案手法は明示的な評価のみに頼ってベースラインを上回り,我々の仮定が推薦システムにおける明示的なフィードバックと暗黙的なフィードバックの相互作用を研究する上で有効なおもちゃの理論的設定を提供することを示した。
関連論文リスト
- Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Harmful Overfitting in Sobolev Spaces [49.47221415754556]
ソボレフ空間$Wk, p(mathbbRd)$における関数の一般化挙動を、ノイズの多いトレーニングデータセットに完全に適合するものとして研究する。
約ノルム最小化補間器は、滑らかさバイアスによって選択される正準解であり、有害なオーバーフィッティングを示す。
我々の証明では,ソボレフの不等式を用いたトレーニングデータの有害な近傍を同定する幾何学的議論を用いている。
論文 参考訳（メタデータ） (2026-01-31T17:40:56Z) - One-Sided Matrix Completion from Ultra-Sparse Samples [18.28432289831719]
観測周波数で第2モーメントの各非ゼロエントリを正規化する非バイアス推定器を提案する。
推定器は任意の$p$に対して偏りがなく、分散が低いことを示す。
合成データと実世界のデータの両方の実験は、我々のアプローチを検証する。
論文 参考訳（メタデータ） (2026-01-18T01:33:48Z) - Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [72.69498649272347]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しいパラダイムを提案する。
提案手法は任意の誤差で理論上真の条件分布を復元可能であることを示す。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。
グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
論文 参考訳（メタデータ） (2024-01-16T03:14:24Z) - Out-Of-Domain Unlabeled Data Improves Generalization [0.7589678255312519]
本稿では,ラベルなしデータを半教師付き分類問題に組み込む新しい枠組みを提案する。
ラベルのないサンプルは一般化ギャップを狭めるために利用できることを示す。
我々は、さまざまな合成および実世界のデータセットで実施された実験を通じて、我々の主張を検証する。
論文 参考訳（メタデータ） (2023-09-29T02:00:03Z) - Kernel-Based Tests for Likelihood-Free Hypothesis Testing [21.143798051525646]
2つのバランスの取れたクラスから$n$の観測が与えられたとき、追加の$m$入力をラベル付けするタスクを考える。
この問題の特別なケースはよく知られており、$m=1$はバイナリ分類に対応し、$mapprox n$は2サンプルテストに相当する。
最近の研究で、$m$と$n$の間に根本的なトレードオフがあることが判明した。
論文 参考訳（メタデータ） (2023-08-17T15:24:03Z) - Tackling Combinatorial Distribution Shift: A Matrix Completion
Perspective [42.85196869759168]
a) テストランダムデータおよびトレーニングランダムデータの下で、ラベル$z$は、(x,y)$, (b) トレーニングディストリビューションは、別々に$x$と$y$の限界分布をカバーしているが、(c) テストディストリビューションは、トレーニングディストリビューションがカバーしていない製品ディストリビューションの例を含む。
論文 参考訳（メタデータ） (2023-07-12T21:17:47Z) - How Does Pseudo-Labeling Affect the Generalization Error of the
Semi-Supervised Gibbs Algorithm? [73.80001705134147]
擬似ラベル付き半教師付き学習(SSL)におけるGibsアルゴリズムによる予測一般化誤差(ゲンエラー)を正確に評価する。
ゲンエラーは、出力仮説、擬ラベルデータセット、ラベル付きデータセットの間の対称性付きKL情報によって表現される。
論文 参考訳（メタデータ） (2022-10-15T04:11:56Z) - Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。
シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
論文 参考訳（メタデータ） (2021-10-15T09:27:50Z) - Leveraged Matrix Completion with Noise [84.20092979053119]
未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry.
我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
論文 参考訳（メタデータ） (2020-11-11T16:25:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。