論文の概要: Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
- arxiv url: http://arxiv.org/abs/2106.04819v1
- Date: Wed, 9 Jun 2021 05:39:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-11 05:51:14.526452
- Title: Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
- Title（参考訳）: コンテキストレコメンデーションと低解像度カットプレーンアルゴリズム
- Authors: Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin
Manurangsi, Renato Paes Leme, Jon Schneider
- Abstract要約: 本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 49.91214213074933
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the following variant of contextual linear bandits motivated by
routing applications in navigational engines and recommendation systems. We
wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are
presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible
actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain
utility $\langle x_t, w^* \rangle$ but only learn the identity of the best
action $\arg\max_{x \in \mathcal{X}_t} \langle x, w^* \rangle$. We design
algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d
\log d))$. To accomplish this, we design novel cutting-plane algorithms with
low "regret" -- the total distance between the true point $w^*$ and the
hyperplanes the separation oracle returns. We also consider the variant where
we are allowed to provide a list of several recommendations. In this variant,
we give an algorithm with $O(d^2 \log d)$ regret and list size
$\mathrm{poly}(d)$. Finally, we construct nearly tight algorithms for a weaker
variant of this problem where the learner only learns the identity of an action
that is better than the recommendation. Our results rely on new algorithmic
techniques in convex geometry (including a variant of Steiner's formula for the
centroid of a convex set) which may be of independent interest.
- Abstract（参考訳）: ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられたコンテキスト線形バンディットの変種について考察する。
隠れた$d$次元の値$w^*$を学びたいと思っています。
ラウンドごとに、可能なアクションのサブセット $\mathcal{x}_t \subseteq \mathbb{r}^d$ が示されます。
選択すれば(つまり)
ユーザへの推奨) action $x_t$, we get utility $\langle x_t, w^* \rangle$, but only the identity of the best action $\arg\max_{x \in \mathcal{x}_t} \langle x, w^* \rangle$。
我々は、この問題のアルゴリズムを設計し、後悔する$O(d\log T)$と$\exp(O(d \log d))$を達成する。
これを達成するために、我々は、真点 $w^*$ と分離オラクルが返す超平面の合計距離である低い "regret" を持つ新しい切削平面アルゴリズムを設計した。
また、いくつかの推奨事項のリストを提供することができる変種についても検討しています。
この変種では、$O(d^2 \log d)$ regret と list size $\mathrm{poly}(d)$ のアルゴリズムを与える。
最後に,学習者が推薦よりも優れた行動の同一性のみを学習する,この問題の弱い変種に対して,ほぼ厳密なアルゴリズムを構築する。
この結果は凸幾何学における新しいアルゴリズム技術(凸集合の遠心に対するシュタイナーの公式の変種を含む)に依存している。
関連論文リスト
- A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳（メタデータ） (2023-06-16T17:00:51Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Optimal Contextual Pricing and Extensions [32.152826900874075]
このアルゴリズムは$Omega(d log T)$ lower bound up to the $d log d$ additive factor。
これらのアルゴリズムは、凸領域のスタイナー固有値を様々なスケールで有界化する新しい手法に基づいている。
論文 参考訳（メタデータ） (2020-03-03T18:46:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。