論文の概要: Match Made with Matrix Completion: Efficient Learning under Matching Interference

• arxiv url: http://arxiv.org/abs/2601.06982v1
• Date: Sun, 11 Jan 2026 16:33:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:01.100321
• Title: Match Made with Matrix Completion: Efficient Learning under Matching Interference
• Title（参考訳）: 行列補完によるマッチング:マッチング干渉下での効率的な学習
• Authors: Zhiyuan Tang, Wanning Chen, Kan Xu,
• Abstract要約: 標準核ノルム正規化は、一致する干渉下で理論的に有効であることを示す。 我々は、核ノルム推定器をベースとした新しい二重エンハンスド推定器を開発し、ほぼ最適入力保証を行う。
• 参考スコア（独自算出の注目度）: 3.4439950003681417
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Matching markets face increasing needs to learn the matching qualities between demand and supply for effective design of matching policies. In practice, the matching rewards are high-dimensional due to the growing diversity of participants. We leverage a natural low-rank matrix structure of the matching rewards in these two-sided markets, and propose to utilize matrix completion to accelerate reward learning with limited offline data. A unique property for matrix completion in this setting is that the entries of the reward matrix are observed with matching interference -- i.e., the entries are not observed independently but dependently due to matching or budget constraints. Such matching dependence renders unique technical challenges, such as sub-optimality or inapplicability of the existing analytical tools in the matrix completion literature, since they typically rely on sample independence. In this paper, we first show that standard nuclear norm regularization remains theoretically effective under matching interference. We provide a near-optimal Frobenius norm guarantee in this setting, coupled with a new analytical technique. Next, to guide certain matching decisions, we develop a novel ``double-enhanced'' estimator, based off the nuclear norm estimator, with a near-optimal entry-wise guarantee. Our double-enhancement procedure can apply to broader sampling schemes even with dependence, which may be of independent interest. Additionally, we extend our approach to online learning settings with matching constraints such as optimal matching and stable matching, and present improved regret bounds in matrix dimensions. Finally, we demonstrate the practical value of our methods using both synthetic data and real data of labor markets.
• Abstract（参考訳）: 整合市場は、整合政策の効果的な設計のための需要と供給の整合性を学ぶ必要性が高まっている。 実際には、参加者の多様性が増すため、マッチング報酬は高次元である。 これら2つの市場におけるマッチング報酬の自然な低ランク行列構造を利用し、行列補完を利用して、限られたオフラインデータで報酬学習を促進することを提案する。 この設定における行列完備化のユニークな性質は、報酬行列の成分が一致した干渉で観測されることである。 このような一致依存は、通常、サンプル独立に依存するため、行列補完文学における既存の分析ツールの準最適性や適用不可能といった、ユニークな技術的課題を生じさせる。 本稿では, 標準核ノルム正規化は, 整合干渉下で理論的に有効であることを示す。 我々は、この設定における準最適フロベニウスノルムを保証するとともに、新しい解析手法を提案する。 次に,核ノルム推定器をベースとした新たな「二重エンハンスド」推定器を開発し,準最適進入保証を行う。 我々のダブルエンハンスメント手順は、独立した関心があるとしても、より広範なサンプリングスキームに適用できる。 さらに、最適マッチングや安定マッチングなどの制約を伴い、オンライン学習環境にアプローチを拡張し、行列次元における後悔境界を改善した。 最後に、労働市場の実データと合成データの両方を用いて、本手法の実用的価値を実証する。

関連論文リスト

• Statistical Inference for Matching Decisions via Matrix Completion under Dependent Missingness [6.28693385008859]
  本研究では,3つの正準機構,すなわち1対1,1対1のランダム到着と1対1のランダム到着,および2対2のランダム到着の非最適進入アルゴリズムを提案する。 実験により,提案手法は精度の高い信頼区間推定と効率的な評価を提供することを示した。
  論文  参考訳（メタデータ） (2025-10-30T13:31:32Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Understanding and Scaling Collaborative Filtering Optimization from the Perspective of Matrix Rank [39.857011461812014]
  協調フィルタリング(CF)手法は現実世界のレコメンデーションシステムを支配している。 本研究では,異なる学習戦略下での埋め込みテーブルの特性について検討する。 ユーザの安定なランクとアイテムの埋め込みを規則化する,効率的なウォームスタート戦略を提案する。
  論文  参考訳（メタデータ） (2024-10-15T21:54:13Z)
• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  本稿では, 学習モデルを用いて評価したヘッセン行列をトレーニングセットで評価した共分散行列の固有解析と, 深層学習モデルで評価したヘッセン行列を組み合わせた新しい手法を提案する。 本手法は複雑なパターンと関係を抽出し,分類性能を向上する。
  論文  参考訳（メタデータ） (2024-02-14T16:10:42Z)
• Adversarial Online Collaborative Filtering [20.931533714651376]
  非繰り返し制約下でのオンライン協調フィルタリングの問題点について検討する。 我々は,ユーザ・イテムの選好行列上の二クラスタリング仮定の下で機能するアルゴリズムを設計し,解析する。 このアルゴリズムは,完全適応性を維持しつつ,最適な後悔の保証を示すことを示す。
  論文  参考訳（メタデータ） (2023-02-11T19:30:55Z)
• Online Statistical Inference in Decision-Making with Matrix Context [5.2071564436846245]
  本稿では,適応的に収集したデータを用いて統計的推測を行うオンライン手法を提案する。 標準の低ランク推定器は偏りがあり、逐次的には得られない。 シーケンシャルな意思決定アルゴリズムにおける既存のアプローチは、低ランク性を考慮しておらず、バイアスもある。
  論文  参考訳（メタデータ） (2022-12-21T22:03:06Z)

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

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