論文の概要: Efficient Online Learning of Optimal Rankings: Dimensionality Reduction
via Gradient Descent
- arxiv url: http://arxiv.org/abs/2011.02817v1
- Date: Thu, 5 Nov 2020 13:52:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-29 12:24:23.765515
- Title: Efficient Online Learning of Optimal Rankings: Dimensionality Reduction
via Gradient Descent
- Title（参考訳）: 最適ランキングの効率的なオンライン学習:勾配降下による次元性低減
- Authors: Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, Stratis
Skoulakis
- Abstract要約: 一般化されたMin-Sum-Set-Cover問題は上記の設定の形式モデルとして機能する。
GMSSCインタイムでの後悔度を低くする方法を示す。
- 参考スコア（独自算出の注目度）: 47.66497212729108
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a natural model of online preference aggregation, where sets of
preferred items $R_1, R_2, \ldots, R_t$ along with a demand for $k_t$ items in
each $R_t$, appear online. Without prior knowledge of $(R_t, k_t)$, the learner
maintains a ranking $\pi_t$ aiming that at least $k_t$ items from $R_t$ appear
high in $\pi_t$. This is a fundamental problem in preference aggregation with
applications to, e.g., ordering product or news items in web pages based on
user scrolling and click patterns. The widely studied Generalized
Min-Sum-Set-Cover (GMSSC) problem serves as a formal model for the setting
above. GMSSC is NP-hard and the standard application of no-regret online
learning algorithms is computationally inefficient, because they operate in the
space of rankings. In this work, we show how to achieve low regret for GMSSC in
polynomial-time. We employ dimensionality reduction from rankings to the space
of doubly stochastic matrices, where we apply Online Gradient Descent. A key
step is to show how subgradients can be computed efficiently, by solving the
dual of a configuration LP. Using oblivious deterministic and randomized
rounding schemes, we map doubly stochastic matrices back to rankings with a
small loss in the GMSSC objective.
- Abstract（参考訳）: R_1, R_2, \ldots, R_t$の各項目に$k_t$の要求を伴って, 優先項目のセットがオンラインに表示される, オンライン嗜好集約の自然なモデルを考える。
R_t, k_t)$の事前の知識がなければ、学習者は、$R_t$から少なくとも$k_t$のアイテムが$\pi_t$の上位に現れることを目標に、$\pi_t$のランクを維持する。
これは、例えば、ユーザのスクロールやクリックパターンに基づいて、Webページで製品やニュースアイテムを注文するアプリケーションに対する優先集約における根本的な問題である。
広く研究されている一般化Min-Sum-Set-Cover (GMSSC) 問題は、上記の設定の形式モデルとして機能する。
GMSSCはNPハードであり、非Regretオンライン学習アルゴリズムの標準的な応用は計算的に非効率である。
本研究では,GMSSCを多項式時間で低後悔にする方法を示す。
階数から2重確率行列空間への次元的還元を採用し、オンライングラディエントDescentを適用した。
鍵となるステップは、構成LPの双対を解くことで、過度を効率的に計算する方法を示すことである。
自明な決定論的、ランダムな丸めスキームを用いて、二重確率行列をgmsscの目的の損失が少なくランキングに戻す。
関連論文リスト
- Adaptively Learning to Select-Rank in Online Platforms [34.258659206323664]
本研究は、異種ユーザの候補プールからアイテムを適応的にランク付けすることの課題に対処する。
本研究では,多様なユーザの好みや項目位置の影響を考慮に入れたユーザ応答モデルを構築した。
シミュレーションと実世界の両方のデータセットで実施された実験は、アルゴリズムがベースラインを上回っていることを示している。
論文 参考訳（メタデータ） (2024-06-07T15:33:48Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Sketchy: Memory-efficient Adaptive Regularization with Frequent
Directions [22.09320263962004]
ディープラーニング(DL)学習タスクにおけるKronecker-factored gradient covariance matrixのスペクトルは、小さなリード固有空間に集中している。
本稿では,行列プレコンディショナを維持するためのメモリと計算要求を低減させる汎用的手法について述べる。
ShampooやAdamと競合する手法で、第2の瞬間を追跡するにはサブ線形メモリしか必要ありません。
論文 参考訳（メタデータ） (2023-02-07T21:50:06Z) - Large Scale Private Learning via Low-rank Reparametrization [77.38947817228656]
本稿では、大規模ニューラルネットワークに微分プライベートSGDを適用する際の課題を解決するために、再パラメータ化方式を提案する。
BERTモデルにディファレンシャルプライバシを適用し、4つの下流タスクで平均精度が8,3.9%に達するのはこれが初めてである。
論文 参考訳（メタデータ） (2021-06-17T10:14:43Z) - Episodic Linear Quadratic Regulators with Low-rank Transitions [31.8243883890202]
本稿では,本システムの低ランク構造を効率よく学習するアルゴリズムを提案する。
我々のアルゴリズムは$K$-episode regret bound of order $widetildeO(m3/2 K1/2)$を達成する。
論文 参考訳（メタデータ） (2020-11-03T08:48:31Z) - Learning to Rank under Multinomial Logit Choice [6.929312022493406]
コンテンツの最適順序付けを学ぶことは、ウェブサイト設計において重要な課題である。
本稿では,この問題に対する$Omega(sqrtJT)$lowbound,$tildeO(sqrtJT)$ upperbound on the regret of the UCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-07T16:15:12Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z) - Rank $2r$ iterative least squares: efficient recovery of ill-conditioned
low rank matrices from few entries [4.230158563771147]
低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。
我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
論文 参考訳（メタデータ） (2020-02-05T16:20:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。