論文の概要: Online Low Rank Matrix Completion

• arxiv url: http://arxiv.org/abs/2209.03997v1
• Date: Thu, 8 Sep 2022 18:49:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-12 12:24:03.524838
• Title: Online Low Rank Matrix Completion
• Title（参考訳）: オンライン低ランク行列補完
• Authors: Prateek Jain and Soumyabrata Pal
• Abstract要約: 我々は,textitonline Low-rank matrix completion with $mathsfM$ users, $mathsfN$ items and $mathsfT roundsについて検討した。 それぞれ、低線形ユーザ-イテム報酬行列からサンプリングされた(自明な)報酬を得る。 提案アルゴリズムは,ユーザをクラスタリングし,アイテムを協調的かつ反復的に除去する新しい手法を用いて,$mathsfT$で最小値に近い最適なレートを得ることができる。
• 参考スコア（独自算出の注目度）: 28.316718791239303
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of \textit{online} low-rank matrix completion with $\mathsf{M}$ users, $\mathsf{N}$ items and $\mathsf{T}$ rounds. In each round, we recommend one item per user. For each recommendation, we obtain a (noisy) reward sampled from a low-rank user-item reward matrix. The goal is to design an online method with sub-linear regret (in $\mathsf{T}$). While the problem can be mapped to the standard multi-armed bandit problem where each item is an \textit{independent} arm, it leads to poor regret as the correlation between arms and users is not exploited. In contrast, exploiting the low-rank structure of reward matrix is challenging due to non-convexity of low-rank manifold. We overcome this challenge using an explore-then-commit (ETC) approach that ensures a regret of $O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{2/3})$. That is, roughly only $\mathsf{polylog} (\mathsf{M}+\mathsf{N})$ item recommendations are required per user to get non-trivial solution. We further improve our result for the rank-$1$ setting. Here, we propose a novel algorithm OCTAL (Online Collaborative filTering using iterAtive user cLustering) that ensures nearly optimal regret bound of $O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{1/2})$. Our algorithm uses a novel technique of clustering users and eliminating items jointly and iteratively, which allows us to obtain nearly minimax optimal rate in $\mathsf{T}$.
• Abstract（参考訳）: 我々は,$\mathsf{m}$ ユーザ,$\mathsf{n}$ アイテム,$\mathsf{t}$ ラウンドを用いて,_textit{online} の低ランク行列完全性の問題を研究する。 各ラウンドでは、ユーザ毎に1つのアイテムを推奨します。 各レコメンデーションに対して、低ランクのユーザテーマ報酬マトリックスからサンプリングされた(迷惑な)報酬を得る。 目標は、($\mathsf{T}$で)サブ線形後悔を伴うオンラインメソッドを設計することである。 問題は、各アイテムが \textit{independent} armである標準的なマルチアームのバンディット問題にマッピングできるが、腕とユーザーの相関が悪用されないため、残念なことになってしまう。 対照的に、報酬行列の低階構造を利用するのは、低階多様体の非凸性のため困難である。 我々は、この挑戦を、$O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{2/3})$を後悔することを保証する探索-then-commit (ETC) アプローチで克服する。 つまり、おおよそ$\mathsf{polylog} (\mathsf{m}+\mathsf{n})$ itemレコメンデーションは、非自明なソリューションを得るためにユーザーごとに必要である。 私たちはさらに1ドルのランク設定で結果を改善します。 ここでは、O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{1/2})$をほぼ最適に再現できる新しいアルゴリズムOCTAL (Online Collaborative filTering using iterAtive user cLustering)を提案する。 提案アルゴリズムは,ユーザをクラスタリングし,アイテムを協調的かつ反復的に除去する新しい手法を用いて,$\mathsf{T}$で最小に近い最適なレートを得ることができる。

関連論文リスト

• Online Matrix Completion: A Collaborative Approach with Hott Items [19.781869063637387]
  M$ユーザ,$N$アイテム,$T$ラウンド,未知のランク-$r$報酬行列$Rin mathbbRMtimes N$のオンライン設定における下位行列補完問題について検討する。
  論文  参考訳（メタデータ） (2024-08-11T18:49:52Z)
• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。 我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-05-21T17:31:10Z)
• Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints [46.65419724935037]
  本稿では,複数のユーザを抱えるエンブロック型協調バンドイットの問題点について考察する。 私たちのゴールは、時間とともにすべてのユーザーが獲得した累積報酬を最大化するアルゴリズムを設計することです。 textttB-LATTICEは、予算制約の下で、ユーザ毎に$widetildeO(sqrtmathsfT(sqrtmathsfM-1)$を後悔する。
  論文  参考訳（メタデータ） (2023-10-31T11:04:21Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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