ترجمه فارسی مقاله تکمیل ماتریس آنلاین: رویکردی مشارکتی با Hott Items

چکیده

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}(Δ^{-1}+Δ_{hott}^{-2}))$ where $Δ_{hott},Δ$ are problem-dependent gap parameters with $Δ_{hott} >> Δ$ 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}Δ_{det}^{-1}))$ where $Δ_{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.

چکیده به فارسی (ترجمه ماشینی)

ما مشکل تکمیل ماتریس با درجه پایین را در یک تنظیم آنلاین با کاربران $ {m} $ ، موارد $ n} $ ، $ {t} $ $ و یک رتبه ناشناخته-$ r $ ماتریس $ {r} in بررسی می کنیم. Mathbb {r}^{{m} times {n}} $.این مشکل در ادبیات به خوبی مورد مطالعه قرار گرفته است و در عمل چندین کاربرد دارد.در هر دور ، ما $ {S} $ را با دقت انتخاب شده برای هر کاربر توصیه می کنیم و پاداش های پر سر و صدا را مشاهده می کنید.در رژیم که $ {m} ، {n} >> {t} $ ، ما دو الگوریتم محاسباتی کارآمد را برای توصیه موارد به کاربران پیشنهاد می کنیم و آنها را تحت عنوان های خوش خیم emp {hott} فرض می کنیم.$ {s} = 1 $ ، تحت فرضیات اضافی/صافی اضافی در $ {r} $ ، ما الگوریتم مرحله ای textsc {phasedclustereLim را پیشنهاد می کنیم.الگوریتم ما یک پشیمانی تقریباً بهینه از هر کاربر از $ tilde {o} ({n} {m}^{-1} (δ^{-1}+δ_ {hott}^{-2})) $ بدست می آورد.جایی که $ Δ_ {{} ، δ $ پارامترهای وابسته به مشکل با $ Δ_ {{hott} >> δ $ تقریباً همیشه هستند.2) دوم ، ما یک تنظیم ساده را با $ {S} = r $ در نظر می گیریم که در آن فرضیات قابل توجهی خفیف تر در $ {r} $ انجام می دهیم.در اینجا ، ما یک الگوریتم فاز دیگر ، textsc {deterantelim} را معرفی می کنیم تا ضمانت پشیمانی $ wideTilde {o} ({n} {m}^{-1/r}} Δ_ {det}^{-1}) را بدست آوریم)) $ که در آن $ Δ_ {det} $ یکی دیگر از شکاف های وابسته به مشکل است.هر دو الگوریتم به طور مهم از همکاری بین کاربران استفاده می کنند تا به طور مشترک موارد زیر بهینه را برای گروه های کاربران به طور پی در پی در مراحل از بین ببرند ، اما با رویکردهای متمایز و جدید.