Fugu-MT 論文翻訳(概要): Online Matrix Completion: A Collaborative Approach with Hott Items

論文の概要: Online Matrix Completion: A Collaborative Approach with Hott Items

arxiv url: http://arxiv.org/abs/2408.05843v1
Date: Sun, 11 Aug 2024 18:49:52 GMT
ステータス: 処理完了
システム内更新日: 2024-08-13 15:15:52.361823
Title: Online Matrix Completion: A Collaborative Approach with Hott Items
Title（参考訳）: オンラインマトリックスコンプリート:ホットトアイテムとの協調的アプローチ
Authors: Dheeraj Baby, Soumyabrata Pal,
Abstract要約: M$ユーザ,$N$アイテム,$T$ラウンド,未知のランク-$r$報酬行列$Rin mathbbRMtimes N$のオンライン設定における下位行列補完問題について検討する。
参考スコア（独自算出の注目度）: 19.781869063637387
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We investigate the low rank matrix completion problem in an online setting with ${M}$ users, ${N}$ items, ${T}$ rounds, and an unknown rank-$r$ reward matrix ${R}\in \mathbb{R}^{{M}\times {N}}$. This problem has been well-studied in the literature and has several applications in practice. In each round, we recommend ${S}$ carefully chosen distinct items to every user and observe noisy rewards. In the regime where ${M},{N} >> {T}$, we propose two distinct computationally efficient algorithms for recommending items to users and analyze them under the benign \emph{hott items} assumption.1) First, for ${S}=1$, under additional incoherence/smoothness assumptions on ${R}$, we propose the phased algorithm \textsc{PhasedClusterElim}. Our algorithm obtains a near-optimal per-user regret of $\tilde{O}({N}{M}^{-1}(\Delta^{-1}+\Delta_{{hott}}^{-2}))$ where $\Delta_{{hott}},\Delta$ are problem-dependent gap parameters with $\Delta_{{hott}} >> \Delta$ almost always. 2) Second, we consider a simplified setting with ${S}=r$ where we make significantly milder assumptions on ${R}$. Here, we introduce another phased algorithm, \textsc{DeterminantElim}, to derive a regret guarantee of $\widetilde{O}({N}{M}^{-1/r}\Delta_{det}^{-1}))$ where $\Delta_{{det}}$ is another problem-dependent gap. Both algorithms crucially use collaboration among users to jointly eliminate sub-optimal items for groups of users successively in phases, but with distinctive and novel approaches.
Abstract（参考訳）: 我々は、${M}$ users, ${N}$ items, ${T}$ rounds, and a unknown rank-$r$ reward matrix ${R}\in \mathbb{R}^{{M}\times {N}}$というオンライン設定における低階行列完備問題について検討する。この問題は文献でよく研究されており、実際にいくつかの応用がある。各ラウンドで、各ユーザに慎重に選択された個別のアイテムを${S}$で推奨し、ノイズの多い報酬を観察します。 In the regime where ${M},{N} >> {T}$, we propose two different computationally efficient algorithm for recommending items to users and analyze them under the benign \emph{hott items} assumption. 1) for ${S}=1$, under additional incoherence/smoothness assumptions on ${R}$, we propose the phased algorithm \textsc{PhasedClusterElim}。我々のアルゴリズムは、$\tilde{O}({N}{M}^{-1}(\Delta^{-1}+\Delta{hott}}^{-2}))$に対して、$\Delta_{{hott}},\Delta$は問題依存のギャップパラメータであり、$\Delta_{{hott}} >> \Delta$はほとんど常に同じである。 2) 第二に、${S}=r$ で単純化された設定を考える。ここでは、別の位相付きアルゴリズムである \textsc{DeterminantElim} を導入し、$\widetilde{O}({N}{M}^{-1/r}\Delta_{det}^{-1})$ の後悔の保証を導出する。どちらのアルゴリズムも、ユーザー同士のコラボレーションを重要視し、段階的かつ斬新なアプローチで、ユーザーグループのサブ最適項目を共同で除去する。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Partially Unitary Learning [0.0]
ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
論文参考訳（メタデータ） (2024-05-16T17:13:55Z)
Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文参考訳（メタデータ） (2023-11-18T23:55:59Z)
Matrix Completion in Almost-Verification Time [37.61139884826181]
99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
論文参考訳（メタデータ） (2023-08-07T15:24:49Z)
Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文参考訳（メタデータ） (2023-01-08T21:46:27Z)
Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文参考訳（メタデータ） (2022-10-15T09:22:22Z)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
論文参考訳（メタデータ） (2021-01-15T18:52:02Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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