# (参考訳) コンテキストレコメンデーションと低解像度カットプレーンアルゴリズム [全文訳有]

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms ( http://arxiv.org/abs/2106.04819v1 )

ライセンス: CC BY 4.0
Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes Leme, Jon Schneider(参考訳) ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられたコンテキスト線形バンディットの変種について考察する。 隠れた$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)$ のアルゴリズムを与える。 最後に,学習者が推薦よりも優れた行動の同一性のみを学習する,この問題の弱い変種に対して,ほぼ厳密なアルゴリズムを構築する。 この結果は凸幾何学における新しいアルゴリズム技術(凸集合の遠心に対するシュタイナーの公式の変種を含む)に依存している。

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.
公開日: Wed, 9 Jun 2021 05:39:05 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。


    Page: /      
1 2 0 2 n u J 1 2 0 2 n u J 0.85
9 ] G L . 9 ] G L。 0.81
s c [ 1 v 9 1 8 4 0 sc [ 1 v 9 1 8 4 0 0.68
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Contextual Recommendations and Low-Regret Cutting-Plane コンテキストレコメンデーションと低反射切削平面 0.70
Algorithms Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes アルゴリズム Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes 0.78
Leme, and Jon Schneider レメとジョン・シュナイダーは 0.67
Google Research Google Research 0.85
June 10, 2021 2021年6月10日 0.71
Abstract We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. 概要 ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられたコンテキスト線形バンディットの変種について考察する。 0.51
We wish to learn a hidden d-dimensional value w∗. 隠れたd-次元値 w∗ を学びたい。 0.75
Every round, we are presented with a subset Xt ⊆ Rd of possible actions. 各ラウンドで、可能なアクションの集合 Xt > Rd が提示される。 0.56
If we choose (i.e. 選択すれば(つまり) 0.62
recommend to the user) action xt, we obtain utility hxt, w∗i but only learn the identity of the best action arg maxx∈Xt hx, w∗i. ユーザへの推奨) アクション xt は、ユーティリティ hxt, w∗i を得るが、最善のアクション arg maxxjavaxt hx, w∗i の同一性のみを学習する。 0.74
We design algorithms for this problem which achieve regret O(d log T ) and exp(O(d log d)). 我々は, 後悔のO(d log T ) と exp(O(d log d)) を実現するアルゴリズムを設計する。 0.80
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. これを達成するために、我々は、真の点 w∗ と分離オラクルが返す超平面との全体距離である低い "regret" を持つ新しい切削平面アルゴリズムを設計した。 0.62
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(d2 log d) regret and list size poly(d). この変種では、o(d2 log d) の後悔とリストサイズ poly(d) を持つアルゴリズムを与える。 0.73
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. 最後に,学習者が推薦よりも優れた行動の同一性のみを学習する,この問題の弱い変種に対して,ほぼ厳密なアルゴリズムを構築する。 0.78
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. 我々の結果は凸幾何学における新しいアルゴリズム技術(凸集合の遠心に対するシュタイナーの公式の変種を含む)に依存している。 0.65
1 Introduction Consider the following problem faced by a geographical query service (e g Google Maps). はじめに 地理的クエリサービス(例えばGoogle Maps)が直面している次の問題を考える。 0.65
When a user searches for a path between two endpoints, the service must return one route out of a set of possible routes. ユーザが2つのエンドポイント間のパスを検索する場合、サービスは可能なルートのセットから1つのルートを返す必要がある。 0.70
Each route has a multidimensional set of features associated with it, such as (i) travel time, (ii) amount of traffic, (iii) how many turns it has, (iv) total distance, etc. 各ルートは、(i)旅行時間、(ii)交通量、(iii)曲がり角の数、(iv)総距離など、それに関連する多次元的な特徴を持っている。
訳抜け防止モード: それぞれの経路は、それに関連付けられた多次元の特徴の集合を持つ。 例えば (i ) 旅行時間、 (ii ) トラフィックの量などです (iii)回転数、(iv)全距離、etc。
The service must recommend one route to the user, but doesn’t a priori know how the user values these features relative to one another. サービスはユーザーに1つのルートを推奨しなければならないが、ユーザーがこれらの機能を相互にどう評価するかを事前には知らない。 0.65
However, when the service recommends a route, the service can observe some feedback from the user: whether or not the user followed the recommended route (and if not, which route the user ended up taking). しかし、サービスがルートを推奨する場合には、ユーザが推奨するルートをフォローするかどうか(そうでなければ、どのルートを取ろうとしたのか)という、ユーザからのフィードバックを見ることができる。 0.68
How can the service use this feedback to learn the user’s preferences over time? このフィードバックを使って、時間の経過とともにユーザの好みを学習できるだろうか? 0.65
Similar problems are faced by recommendation systems in general, where every round a user arrives their current search query, recent activity, etc. 同様の問題は、ユーザーが現在の検索クエリや最近のアクティビティなどに到達するたびに発生するレコメンデーションシステム全般によって直面している。 0.68
), the accompanied by some contextual information (e g system makes a recommendation to the user, and the system can observe the eventual action (e g the purchase of a specific item) by the user. は、いくつかのコンテキスト情報(例えば、システムは、ユーザに推薦し、システムは、ユーザによる最終的なアクション(例えば、特定のアイテムの購入)を観察することができる。 0.71
These problems can be viewed as specific cases of a variant of linear contextual bandits that we term contextual recommendation. これらの問題は、コンテキストレコメンデーション(contextual recommendation)と呼ばれる線形文脈帯域の変動の特定のケースと見なすことができる。 0.61
In contextual recommendation, there is a hidden vector w∗ ∈ Rd (e g representing the values of the user for different features) that is unknown to the learner. 文脈的レコメンデーションでは、学習者にとって未知の隠れたベクトル w∗ ∈ rd(例えば、異なる特徴に対するユーザの値を表す)が存在する。 0.78
Every round t (for T rounds), the learner is presented with an adversarially chosen (and potentially very large) set of possible actions Xt. 各ラウンドt(Tラウンド)において、学習者は敵に選択された(そしておそらく非常に大きな)アクション Xt を提示する。 0.67
Each element xt of Xt is also an element of Rd (visible to the learner); playing action xt results in the learner receiving a reward xt の各要素 xt も rd (visible to the learner) の要素であり、アクション xt をプレイすると、学習者が報酬を受け取る。 0.78
1 1 0.85
of hxt, w∗i. hxt, w∗iです 0.86
The learner wishes to incur low regret compared to the best possible strategy in hindsight – i.e. 学習者は、後見の最良の戦略である——すなわち—に比べて、低い後悔を招きたい。 0.63
the learner wishes to minimize 学習者は最小化したい 0.69
T Reg = (hx∗ T 例 = (hx∗) 0.70
t , w∗i − hxt, w∗i) , t , w∗i − hxt, w∗i) , 0.84
(1) Xt=1 where x∗ In our geographical query example, this regret corresponds to the difference between the utility of a user that always blindly follows our recommendation and the utility of a user that always chooses the optimal route. (1) Xt=1 地理的クエリの例では、この後悔は、常に私たちの推奨に盲目的に従うユーザのユーティリティと、常に最適なルートを選択するユーザのユーティリティとの違いに対応しています。 0.74
t = arg maxx∈Xthx, w∗i is the best possible action at time t. t = arg maxx linkedinxthx, w∗i は時間 t における最善の作用である。 0.66
Thus far this agrees with the usual set-up for contextual linear bandits (see e g [8]). これまでのところ、これは文脈線形バンドイットの通常の設定と一致する(e g [8]参照)。 0.65
Where contextual recommendation differs from this is in the feedback available to the learner: whereas classically in contextual linear bandits the learner learns (a possibly noisy version of) the reward they receive each round, in contextual recommendation the learner instead learns the identity of the best arm x∗ t . 古典的には文脈的線形帯域幅において、学習者は各ラウンドの報酬(おそらくノイズの多いバージョンの)を学習するが、文脈的レコメンデーションでは、学習者は最高の腕 x∗ t の同一性を学ぶ。
訳抜け防止モード: 文脈的レコメンデーションがこれと違うのは、学習者が利用できるフィードバックにある。 文脈的線形バンディットでは 学習者は(おそらく騒がしいバージョンの)各ラウンドの報酬を学習する。 文脈的レコメンデーションでは、学習者は代わりに最良のarm x∗ t の同一性を学ぶ。
This altered feedback makes it difficult to apply existing algorithms for linear contextual bandits. この変更されたフィードバックにより、既存のアルゴリズムを線形文脈帯域に適用することは困難になる。 0.56
In particular, algorithms like LINUCB and LIN-Rel [2, 8] all require estimates of hxt, w∗i in order to learn w∗ over time, and our feedback prevents us from obtaining any such absolute estimates. 特に、LINUCB や LIN-Rel [2, 8] のようなアルゴリズムは、時間とともに w∗ を学ぶために、hxt, w∗i の見積もりを必要とする。 0.54
In this paper we design low-regret algorithms for this problem. 本稿では,この問題に対する低regretアルゴリズムを設計する。 0.76
We present two algorithms for this problem: one with regret O(d log T ) and one with regret exp(O(d log d)) (Theorems 4.2 and 4.4). この問題に対するアルゴリズムは, 後悔のO(d log T ) と後悔のexp(O(d log d)) の2つ(定理 4.2 と 4.4 )である。 0.79
Note that both regret guarantees are independent of the number of offered actions |Xt| (the latter even being independent of the time horizon T ). 両方の後悔保証は、提供されたアクション |xt| の数とは独立である(後者は時間軸 t とは独立である)。 0.65
Moreover both of these algorithms are efficiently implementable given an efficient procedure for optimizing a linear function over the sets Xt. さらに、これらのアルゴリズムは、集合 Xt 上の線型関数を最適化する効率的な手順により、効率的に実装できる。 0.75
This condition holds e g in the example of recommending shortest paths that we discussed earlier. この条件は、例えば、先に議論した最短経路を推奨する例である。 0.70
In addition to this, we consider two natural extensions of contextual recommendation where the learner is allowed to recommend a bounded subset of actions instead of just a single action (as is often the case in practice). これに加えて、学習者が単に1つのアクション(実際にはそうである)ではなく、境界付けられたアクションのサブセットを推薦することを許すような、コンテキストレコメンデーションの自然な2つの拡張について考察する。
訳抜け防止モード: これに加えて、学習者が1つのアクションではなく1つのアクションの束縛されたサブセットを推薦できる2つのコンテキストレコメンデーションの自然な拡張を考える。 (例によって)
In the first variant, which we call list contextual recommendation, each round the learner recommends a set of at most L (for some fixed L) actions to the learner. リストのコンテキストリコメンデーションと呼ばれる第1の変種では、学習者が学習者に対して、最大l(固定l)アクションのセットを推奨する。 0.61
The learner still observes the user’s best action each round, but the loss of the learner is now the difference between the utility of the best action for the user and the best action offered by the learner (capturing the difference in utility between a user playing an optimal action and a user that always chooses the best action the learner offers). 学習者は、各ラウンドごとのユーザのベストアクションを引き続き観察するが、学習者の喪失は、ユーザにとって最高のアクションの効用と学習者が提供するベストアクションの効用との違いである(最適なアクションを行うユーザと、学習者が常にベストアクションを選択するユーザとの実用性の違いをキャプチャする)。 0.84
In list contextual recommendation, the learner has the power to cover multiple different user preferences simultaneously (e g presenting the user with the best route for various different measures). リストのコンテキストレコメンデーションでは、学習者は複数の異なるユーザの好みを同時にカバーする能力を持つ(例えば、様々な対策に最適なルートをユーザに提示する)。 0.74
We show how to use this power to construct an algorithm for the learner which offers poly(d) actions each round and obtain a total regret of O(poly(d)). 本稿では、このパワーを用いて、各ラウンドにポリ(d)アクションを提供し、O(poly(d))を完全に後悔する学習者のためのアルゴリズムを構築する方法を示す。 0.74
In the second variant, we relax an assumption of both previous models: that the user will always choose their best possible action (and hence that we will observe their best possible action). 第2の変種では、私たちは両方の以前のモデルの仮定を緩和します。ユーザが常に可能な限りのアクションを選択します(従って、可能な限りのアクションを観察します)。
訳抜け防止モード: 第2の変種では、両モデルの仮定を緩和する:ユーザが常に最善のアクションを選択する()。 したがって、私たちは彼らの最善の行動を観察します。
To relax this assumption, we also consider the following weaker version of contextual recommendation we call local contextual recommendation. この仮定を緩和するために、ローカルコンテキストレコメンデーションと呼ぶコンテキストレコメンデーションのより弱いバージョンについても検討する。 0.48
In this problem, the learner again recommends a set of at most L actions to the learner (for some L > 1)1. この問題において、学習者は、学習者(L > 1)1に対して、最も多くの L アクションの集合を再び推奨する。 0.78
The user then chooses an action which is at least as good as the best action in our list, and we observe this action. ユーザが選択したアクションは、少なくとも私たちのリストのベストアクションに匹敵するもので、このアクションを観察します。 0.76
In other words, we assume the learner at least looks at all the options we offer, so if they choose an external option, it must be better than any offered option (but not necessarily the global optimum). 言い換えれば、学習者は少なくとも私たちの提供するすべてのオプションを見て、外部オプションを選択した場合には、どのオプションよりも優れている(必ずしもグローバルな最適化ではない)と仮定する。 0.85
Our regret in this case is the difference between the total utility of a learner that always follows the best recommendation in our list and the total utility of a learner that always plays their optimal action2. この場合の後悔は、リストの中で常に最良の推奨に従う学習者の全効用と、常に最適なアクション2を演じる学習者の全効用との違いです。 0.68
Let A = maxt |Xt| be a bound on the total number of actions offered in any round, and let γ = A/(L − 1). A = maxt |Xt| を任意のラウンドで提供される作用の総数上の有界とし、γ = A/(L − 1) とする。 0.82
Via a simple reduction to contextual recommendation, we construct algorithms for local contextual recommendation with regret O(γd log T ) and γ exp(O(d log d)). 文脈レコメンデーションの簡易化により,後悔o(γd log t)とγ exp(o(d log d))を用いた局所文脈レコメンデーションのためのアルゴリズムを構築する。 0.77
We further show that the first bound is さらに、最初の境界は、 0.44
1Unlike in the previous two variants, it is important in local contextual recommendation that L > 1; if L = 1 then the user 1 以前の2つの変種とは異なり、L > 1 の局所的な文脈的推奨において重要である。 0.63
can simply report the action the learner recommended and the learner receives no meaningful feedback. 単に学習者が推奨するアクションを報告し、学習者は有意義なフィードバックを受け取らない。
訳抜け防止モード: 単に学習者が推奨する行動を報告し 学習者は無意味なフィードバックを受け取ります
2In fact, our algorithms all work for a slightly stronger notion of regret, where the benchmark is the utility of a learner that always follows the first (i.e. 2事実、私たちのアルゴリズムは、ベンチマークが常に最初の(つまり)学習者の効用である、少し強い後悔の考えのために機能しています。 0.68
a specifically chosen) recommendation on our list. 特別に選ばれた) リストの推奨事項。 0.77
With this notion of regret, contextual recommendation reduces to local contextual recommendation with L = max |Xt|. この後悔の概念により、文脈レコメンデーションはL = max |Xt| で局所的な文脈レコメンデーションに還元される。 0.49
2 2 0.85
“nearly tight” (up to poly(d) factors) in some regimes; in particular, we demonstrate an instance where L = 2 and K = 2Ω(d) where any algorithm must incur regret at least min(2Ω(d), Ω(T )) (Theorem 6.4). 特に、L = 2 と K = 2Ω(d) の場合には、任意のアルゴリズムが少なくとも min(2Ω(d), Ω(T )) を後悔しなければならない(定理 6.4)。
訳抜け防止モード: ほとんどきつく」(ポリ(d) 因子まで)はいくつかのレジームにおいて、特に。 L = 2 で K = 2Ω(d ) のときの例を示す。 どんなアルゴリズムでも後悔を招き 少なくとも min(2Ω(d ), Ω(T ) ) ( Theorem 6.4 ) である。
1.1 Low-regret cutting plane methods and contextual search 1.1 低反射切削法と文脈探索 0.76
To design these low-regret algorithms, we reduce the problem of contextual recommendation to a geometric online learning problem (potentially of independent interest). これらの低精細なアルゴリズムを設計するために、幾何学的オンライン学習問題(潜在的に独立した関心)に対する文脈推薦の問題を軽減する。 0.60
We present two different (but equivalent) viewpoints on this problem: one motivated by designing separation-oracle-ba sed algorithms for convex optimization, and the other by contextual search. 我々は,この問題に対する2つの異なる(等価な)視点を提示する。一方は,凸最適化のための分離軌道に基づくアルゴリズムを設計し,もう一方は文脈探索によるものである。
訳抜け防止モード: この問題については二つの異なる(しかし等価な)視点を提示する。 分離をデザインする -oracle-based algorithms for convex optimization, and other by context search。
1.1.1 Separation oracles and cutting-plane methods 1.1.1 分離神託と切断面法 0.56
Separation oracle methods (or “cutting-plane methods”) are an incredibly well-studied class of algorithms for linear and convex optimization. 分離 oracle メソッド(あるいは "カットプレーンメソッド" )は、線形および凸最適化のための驚くほどよく研究されたアルゴリズムのクラスである。 0.72
For our purposes, it will be convenient to describe cutting-plane methods as follows. 我々の目的のためには、切削平面法を次のように記述することは便利である。 0.58
Let B = {w ∈ Rd | kwk ≤ 1} be the unit ball in Rd. B = {w ∈ Rd | kwk ≤ 1} を Rd の単位球とする。 0.76
We are searching for a hidden point w∗ ∈ B. 我々は隠れ点 w∗ ∈ b を探している。 0.82
Every round we can choose a point pt ∈ B and submit this point to a separation oracle. 各ラウンドで点 pt ∈ B を選択して、この点を分離オラクルに渡すことができる。 0.72
The separation oracle then returns a half-space separating pt from w∗; in particular, the oracle returns a direction vt such that hw∗, vti ≥ hpt, vti. 分離オラクルはその後、w∗ から pt を分離する半空間を返し、特に、オラクルは hw∗, vti ≥ hpt, vti のような方向 vt を返す。 0.73
Traditionally, cutting-plane algorithms have been developed to minimize the number of calls to the separation oracle until the oracle returns a hyperplane that passes within some distance δ of w∗. 伝統的に、切断平面アルゴリズムは分離オラクルへの呼び出し数を最小化するために開発され、オラクルはw∗ のある種の距離 δ 内を通過する超平面を返す。 0.66
For example, the ellipsoid method (which always queries the center of the currently-maintained ellipse) has the guarantee that it makes at most O(d2 log 1/δ) oracle queries before finding such a hyperplane. 例えば、楕円型メソッド(現在維持されている楕円の中心を常にクエリする)は、そのような超平面を見つける前に、o(d2 log 1/δ) oracleクエリを最大にする保証を持っている。 0.63
In our setting, instead of trying to minimize the number of separation oracle queries before finding a “close” hyperplane, we would like to minimize the total (over all T rounds) distance between the returned hyperplanes and the hidden point w∗. 我々の設定では、"クローズ"な超平面を見つける前に分離オラクルクエリの数を最小にするのではなく、返却された超平面と隠された点 w∗ の間の全(全 T ラウンド)距離を最小にしたい。 0.67
That is, we would like to minimize the expression つまり、表現を最小限にしたいのです。 0.73
T Reg′ = Xt=1 T reg'= Xt=1 0.68
(hw∗, vti − hpt, vti) . (hw∗, vti − hpt, vti)。 0.74
(2) Due to the similarity between (2) and (1), we call this quantity the regret of a cutting-plane algorithm. (2) (2) と (1) の類似性から、この量を切削平面アルゴリズムの後悔と呼ぶ。
訳抜け防止モード: (2) 2 ) と (1 ) の類似性のためである。 この量をカットプレーンアルゴリズムの後悔と呼ぶ。
We show that, given any low-regret cutting-plane algorithm, there exists a low-regret algorithm for contextual recommendation. 我々は,低レグレットなカットプレーンアルゴリズムを考慮すれば,文脈的推薦のための低レグレットアルゴリズムが存在することを示す。 0.60
Theorem 1.1 (Restatement of Theorem 3.1). Theorem 1.1 (Theorem 3.1の更新)。 0.70
Given a low-regret cutting-plane algorithm A with regret ρ, we can construct an O(ρ)-regret algorithm for contextual recommendation. 後悔 ρ を持つ低精細な切削平面アルゴリズム a が与えられると、文脈推薦のために o(ρ)-regret アルゴリズムを構築することができる。 0.71
This poses a natural question: what regret bounds are possible for cutting-plane methods? これは自然な疑問を呈する: 切断平面法に何の後悔の限界があるのか? 0.62
One might expect guarantees on existing cutting-plane algorithms to transfer over to regret bounds, but interestingly, this does not appear to be the case. 既存のカットプレーンアルゴリズムが後悔の限界に移行する保証は期待できるかもしれないが、興味深いことに、これはそうではないようだ。 0.61
In particular, most existing cutting-plane methods and analysis suffers from the following drawback: even if the method is likely to find a hyperplane within distance δ relatively quickly, there is no guarantee that subsequent calls to the oracle will return low-regret hyperplanes. 特に、既存のカットプレーン法や分析法は以下の欠点に悩まされている: 距離δ で比較的早く超平面を見つけるであろうとしても、その後のオラクルへの呼び出しが低反射超平面を返すという保証はない。 0.69
In this paper, we will show how to design low-regret cutting-plane methods. 本稿では,低抵抗切削平面法の設計方法について述べる。 0.79
Although our final algorithms some involve cutting through the will bear some resemblance to existing cutting-plane algorithms (e g center-of-gravity of some convex set), our analysis will instead build off more recent work on the problem of contextual search. 私たちの最終的なアルゴリズムは、既存の切削面のアルゴリズム(凸集合の重心など)に少し似ているが、その代わりに文脈探索の問題に関する最近の研究を積み上げることになるでしょう。 0.75
1.1.2 Contextual search 1.1.2 文脈探索 0.52
Contextual search is an online learning problem initially motivated by applications in pricing [16]. コンテキスト検索は、当初価格のアプリケーションによって動機付けられたオンライン学習問題です [16]。 0.68
The basic form of contextual search can be described as follows. 文脈探索の基本的な形式は次のように記述できる。 0.77
As with the previously mentioned problems, there is a hidden vector w∗ ∈ [0, 1]d that we wish to learn over time. 前述した問題と同様に、隠れたベクトル w∗ ∈ [0, 1]d が存在し、時間の経過とともに学習したいと考える。 0.69
Every round the adversary provides the learner with a vector vt (the “context”). 各ラウンドの敵は学習者にベクトルvt("context")を提供する。 0.60
In response, the learner must guess the value of hvt, w∗i, submitting a guess 応答として、学習者は hvt, w∗i の値を推測し、推測を提出しなければならない 0.60
3 3 0.85
yt. The learner then incurs a loss of |hvt, w∗i − yt| (the distance between their guess and the true value of the inner product), but only learns whether hvt, w∗i is larger or smaller than their guess. ytだ 学習者は |hvt, w∗i − yt| の損失(その推測と内積の真の値の間の距離)を負うが、hvt, w∗i が推測よりも大きいか小さいかだけを学習する。 0.74
The problem of designing low-regret cutting plane methods can be interpreted as a “context-free” variant of contextual search. 低解像度切削平面法を設計する問題は、文脈探索の「文脈自由な」変種と解釈できる。 0.70
In this variant, the learner is no longer provided the context vt at the beginning of each round, and instead of guessing the value of hvt, w∗i, they are told to directly submit a guess pt for the point w∗. この変種では、学習者は各ラウンドの開始時に文脈 vt が与えられなくなり、hvt, w∗i の値を推測する代わりに、点 w∗ に対して推測 pt を直接提出するように指示される。 0.77
The context vt is then revealed to them after they submit their guess, where they are then told whether hpt, w∗i is larger or smaller than hvt, w∗i and incur loss |hvt, w∗i − hpt, w∗i|. 文脈 vt は、それらの仮定を提出した後、それらに明らかにされ、hpt, w∗i が hvt, w∗i より大きいか小さいか、そして帰納損失 |hvt, w∗i − hpt, w∗i| より小さいかが分かる。 0.68
Note that this directly corresponds to querying a separation oracle with the point pt, and the separation oracle returning either the halfspace vt (in the case that hw∗, vti ≥ hw∗, pti) or the halfspace −vt (in the case that hw∗, vti ≤ hw∗, pti). これは、分離オラクルを点 pt で問うことと、分離オラクルが半空間 vt (hw∗, vti ≥ hw∗, pti) または半空間 −vt (hw∗, vti ≤ hw∗, pti) を返すことと直接一致する。
訳抜け防止モード: これは直接対応することに注意。 ポイントptで分離オラクルを問い合わせる そして、半空間 vt のどちらかを返す分離オラクル(hw∗, vti ≥ hw∗, pti の場合) あるいは、半空間 −vt (hw∗, vti ≤ hw∗, pti ) である。
One advantage of this formulation is that (unlike in standard analyses of cutting-plane methods) the total loss in contextual search directly matches the expression in (2) for the regret of a cutting-plane method. この定式化の利点の1つは、(切断平面法の標準的な解析とは異なり)文脈探索における総損失が、切断平面法を後悔する(2)式と直接一致することである。 0.72
In fact, were there to already exist an algorithm for contextual search which operated in the above manner – guessing hvt, w∗i by first approximating w∗ and then computing the inner product – we could just apply this algorithm verbatim and get a cutting-plane method with the same regret bound. 実際、既に上記の方法で操作された文脈探索のアルゴリズムが存在していた ― 最初はhvt, w∗i を近似して内部積を計算し、このアルゴリズムを冗長に適用して同じ後悔境界を持つ切断平面法を得ることができた。 0.86
Unfortunately, both the algorithms of [19] and [16] explicitly require knowledge of the direction vt. 残念ながら、[19] と [16] のアルゴリズムはどちらも、方向 vt の知識を明示的に要求する。 0.78
This formulation also raises an interesting subtlety in the power of the separation oracle: specifically, whether the direction vt is fixed (up to sign) ahead of time or is allowed to depend on the point p. Specifically, we consider two different classes of separation oracles. この定式化はまた、分離オラクルのパワーに興味深い微妙さを生じさせ、具体的には、方向 vt が時間前(符号まで)固定されているか、あるいは点 p に依存することが許されているかを考える。 0.58
For (strong) separation oracles, the direction vt is allowed to freely depend on the point pt (as long as it is indeed true that hw∗, vti ≥ hpt, vti). 強い)分離オラクルの場合、方向 vt は点 pt に自由に依存することが許される(実際には hw∗, vti ≥ hpt, vti が真である限り)。 0.63
For weak separation oracles, the adversary fixes a direction ut at the beginning of the round, and then returns either vt = ut or vt = −ut (depending on the sign of hw∗ − pt, uti). 弱い分離のオラクルに対して、敵はラウンドの開始時に方向 ut を固定し、次に vt = ut または vt = −ut を返す(hw∗ − pt, uti の符号に依存する)。 0.79
The strong variant is most natural when comparing to standard separation oracle guarantees (and is necessary for the reduction in Theorem 1.1), but for many standalone applications (especially those motivated by contextual search) the weak variant suffices. 強変種は、oracleの標準分離と比べれば最も自然であるが(定理1.1の削減には必要である)、多くのスタンドアロンアプリケーション(特に文脈探索によって動機付けられたもの)では弱い変種が十分である。 0.67
In addition, the same techniques we use to construct a cutting-plane algorithm for weak separation oracles will let us design low-regret algorithms for list contextual recommendation. さらに、弱分離オラクルのための切削平面アルゴリズムを構築するのと同じ手法で、リストのコンテキストレコメンデーションのための低回帰アルゴリズムを設計できる。 0.73
1.2 Our results and techniques We design the following low-regret cutting-plane algorithms: 1.2 結果と技術 以下の低解像度切削平面アルゴリズムを設計する。 0.75
1. An exp(O(d log d))-regret cutting-plane algorithm for strong separation oracles. 1. 強い分離オラクルのための exp(o(d log d))-regret cutting-plane アルゴリズム 0.77
2. An O(d log T )-regret cutting-plane algorithm for strong separation oracles. 2. O(d log T )-regret cut-plane algorithm for strong separation orakles。 0.82
3. An O(poly(d))-regret cutting-plane algorithm for weak separation oracles. 3. 弱分離神託に対するo(poly(d))-regret cutting-planeアルゴリズム 0.75
All three algorithms are efficiently implementable (in poly(d, T ) time). 3つのアルゴリズムはすべて効率よく実装できる(ポリ(d, T)時間)。 0.86
Through Theorem 1.1, points (1) and (2) immediately imply the algorithms with regret exp(O(d)) and O(d log T ) for contextual recommendation. Theorem 1.1 を通じて、(1) と (2) は直ちに、文脈的推奨のために exp(O(d)) と O(d log T ) のアルゴリズムを暗示する。 0.79
Although we do not have a blackbox reduction from weak separation oracles to algorithms for list contextual recommendation, we show how to apply the same ideas in the algorithm in point (3) to construct an O(d2 log d)-regret algorithm for list contextual recommendation with L = poly(d). 弱い分離オラクルからリストのコンテキストレコメンデーションのためのアルゴリズムへのブラックボックスの削減はないが、L = poly(d) を用いてリストのコンテキストレコメンデーションのための O(d2 log d)-regret アルゴリズムを構築するために、ポイント(3)でアルゴリズムに同じアイデアを適用する方法を示す。 0.82
To understand how these algorithms work, it is useful to have a high-level understanding of the algorithm of [19] for contextual search. これらのアルゴリズムがどのように機能するかを理解するためには,[19]のアルゴリズムを文脈探索に高レベルに理解することが有用である。
訳抜け防止モード: アルゴリズムの仕組みを理解するためです 文脈探索には[19]のアルゴリズムを高レベルに理解しておくことが有用である。
That algorithm relies on a multiscale potential function the authors call the Steiner potential. このアルゴリズムは、スタイナーポテンシャルと呼ばれるマルチスケールポテンシャル関数に依存する。 0.67
The Steiner potential at scale r is given by the expression Vol(Kt + rB), where Kt (the “knowledge set”) is the current set of possibilities for the hidden point w∗, B is the unit ball, and addition denotes Minkowsi sum; in other words, this is the volume of the set of points within distance r of Kt. スケール r におけるスタイナーポテンシャルは、Vol(Kt + rB) という式で与えられるが、ここで Kt (「知識集合」) は隠れた点 w∗, B が単位球であり、加法はミンコワシ和を表し、言い換えれば、これは Kt の距離 r 内の点の集合の体積である。
訳抜け防止モード: スケール r におけるスタイナーポテンシャルは、Vol(Kt + rB ) という式で与えられる。 ここで Kt (“知識集合 ” ) は隠された点 w∗ に対する現在の可能性の集合である。 B は単位球である。 追加はMinkowsi sumを表す 言い換えれば、これは Kt の距離 r 内の点の集合の体積である。
The authors show that by choosing their guess yt carefully, they can decrease the r-scale Steiner potential (for some r roughly proportional to the width of Kt in the current direction vt) by a constant factor. 著者らは、推測 yt を慎重に選択することで、r-スケールのスタイナーポテンシャル(現在の方向 vt の kt の幅にほぼ比例する r に対して)を定数因子で減少させることができることを示した。 0.75
In particular, they show that this is achieved by choosing yt so to divide the expanded set Kt + rB exactly in half by volume. 特に、拡張集合 Kt + rB を体積でちょうど半分に分割するために yt を選択することで達成されることを示す。 0.71
Since the Steiner potential at scale r is bounded below by Vol(rB), this allows the authors to bound the total number of mistakes at this scale. スケール r におけるスタイナーポテンシャルは、Vol(rB) によって下界されるので、著者はこのスケールでの誤りの総数に制限を与えることができる。 0.72
(A more detailed description of this algorithm is provided in Section 2.2). (このアルゴリズムの詳細は第2節2に記載されている。) 0.81
4 4 0.85
In the separation oracle setting, we do not know vt ahead of time, and thus cannot implement this algorithm as written. oracleの分離設定では、私たちは事前にvtを知らないので、このアルゴリズムを記述通りに実装できない。 0.69
For example, we cannot guarantee our hyperplane splits Kt + rB exactly in half. 例えば、超平面分割 Kt + rB を正確に半分にすることは保証できない。 0.73
We partially work around this by using (approximate variants of) Grunbaum’s theorem, which guarantees that any hyperplane through the center-of-gravity of a convex set splits that convex set into two pieces of roughly comparable volume. このことは、凸集合の中心の重力を通した超平面が、凸集合をほぼ同等の体積の2つの部分に分割することを保証している。
訳抜け防止モード: 我々は、Grunbaum の定理を ( の近似変種) を用いて部分的に取り巻く。 これは、凸集合の重力が、凸集合をほぼ同等の体積の2つの断片に分割することを保証する。
In other words, everywhere where the contextual search algorithm divides the volume of Kt + rB in half, Grunbaum’s theorem implies we obtain comparable results by choosing any hyperplane passing through the center-of-gravity of Kt + rB. 言い換えれば、文脈探索アルゴリズムが Kt + rB の体積を半分に分割する至るところで、グルンバウムの定理は、Kt + rB の中心を通り抜ける超平面を選択することで、同等の結果が得られることを示唆している。
訳抜け防止モード: 言い換えれば、どこにでも 文脈探索アルゴリズムは Kt + rB の体積を半分に分割する Grunbaum の定理は、同等の結果が得られることを示唆する Kt + rB の-重心を通る超平面を選ぶ。
Unfortunately, we still cannot quite implement this in the separation oracle setting, since the choice of r in the contextual search algorithm depends on the input vector vt. 残念ながら、文脈探索アルゴリズムにおける r の選択は入力ベクトル vt に依存するため、oracle の分離設定でこれを実装できない。 0.67
Nonetheless, by modifying the analysis of contextual search we can still get some guarantees via simple methods of this form. それでも、文脈探索の分析を変更することで、この形式の単純な方法によっていくつかの保証が得られる。 0.60
In particular we show that always querying the center-of-gravity of Kt (alternatively, the center of the John ellipsoid of Kt) results in an exp(O(d log d))-regret cutting-plane algorithm, and that always querying the center of gravity of Kt + 1 特に、Kt の中心を常に問う(逆に Kt の John ellipsoid の中心)と exp(O(d log d))-regret 切断平面アルゴリズム が成立し、Kt + 1 の重心を常に問うことが示される。
訳抜け防止モード: 特に、常に中心(つまりKt)の重力(重心)を問合せすることを示す。 Kt の John ellipsoid の中心は exp(O(d log d))-regret cut - plane algorithm をもたらす。 常に Kt + 1 の重心を問い合わせます
T B results in an O(d log T )-regret cutting-plane algorithm. t b は o(d log t )-regret cutting-plane アルゴリズムとなる。 0.77
Our cutting-plane algorithm for weak separation oracles requires a more nuanced understanding of the family of sets of the form Kt + rB. 弱分離オラクルに対する切断平面アルゴリズムは、Kt + rB という形の集合の族をより微妙に理解する必要がある。 0.60
This family of sets has a number of surprising algebraic properties. この集合の族は多くの驚くべき代数的性質を持つ。 0.73
One such property (famous in convex geometry and used extensively in earlier algorithms for contextual search) is Steiner’s formula, which states that for any convex K, Vol(K + rB) is actually a polynomial in r with nonnegative coefficients. そのような性質(凸幾何学で有名で、以前のアルゴリズムで文脈探索に広く使われている)の1つはシュタイナーの公式であり、任意の凸 K に対して、Vol(K + rB) は実際には非負係数を持つ r の多項式である。 0.71
These coefficients are called intrinsic volumes and capture various geometric measures of the set K (including the volume and surface area of K). これらの係数は内在体積と呼ばれ、集合 K の様々な幾何学的測度(K の体積と面積を含む)を捉える。 0.76
There exists a lesser-known analogue of Steiner’s formula for the center-of-gravity of K + rB, which states that each coordinate of cg(K + rB) is a rational function of degree at most d; in other words, the curve cg(K + rB) for r ∈ [0,∞) is a rational curve. k + rb の重心に関するシュタイナーの公式のあまり知られていない類似物が存在し、これは cg(k + rb) の各座標が最大 d の次数の有理関数であることを意味する; つまり、r ∈ [0,∞) の曲線 cg(k + rb) は有理曲線である。
訳抜け防止モード: K + rB の重力の中心に対するシュタイナーの公式の、より少ない-既知の類似体が存在する。 これは、cg(K + rB ) の各座標が高々 d の次数の有理関数であることを示す。 言い換えれば、r ∈ [ 0,∞ ) に対する曲線 cg(K + rB ) は有理曲線 である。
Moreover, this variant of Steiner’s formula states that each point cg(K + rB) can be written as a convex combination of d + 1 points contained within K known as the curvature centroids of K. Motivated by this, we call the curve ρK(r) = cg(K + rB) the curvature path of K. Since the curvature path ρK is both bounded in algebraic degree and bounded in space (having to lie within the convex hull of the curvature centers), we can bound the total length of the curvature path ρK by a polynomial in d (since it is bounded in degree, each component function of ρK can switch from increasing to decreasing a bounded number of times). Moreover, this variant of Steiner’s formula states that each point cg(K + rB) can be written as a convex combination of d + 1 points contained within K known as the curvature centroids of K. Motivated by this, we call the curve ρK(r) = cg(K + rB) the curvature path of K. Since the curvature path ρK is both bounded in algebraic degree and bounded in space (having to lie within the convex hull of the curvature centers), we can bound the total length of the curvature path ρK by a polynomial in d (since it is bounded in degree, each component function of ρK can switch from increasing to decreasing a bounded number of times). 0.88
This means that we can discretize the curvature path to within precision ε while only using poly(d)/ε points on the path. これは、経路上のポリ(d)/ε点のみを使用しながら、曲率パスを精度 ε 内で離散化することができることを意味する。 0.72
Our algorithms against weak separation oracles and for list contextual recommendation both make extensive use of such a discretization. 弱分離オラクルに対する我々のアルゴリズムとリストのコンテキストレコメンデーションは、どちらもそのような離散化を広く利用しています。 0.56
For example, we show that in order to construct a low-regret algorithm against a weak separation oracle, it suffices to discretize ρKt into O(d4) points and then query a random point; with probability at least O(d−4), we will closely enough approximate the point ρ(r) = cg(K + rB) that our above analogue of contextual search would have queried. 例えば、弱い分離神託に対して低精細なアルゴリズムを構築するには、ρkt を o(d4) 個の点に離散化し、それからランダムな点を問い合わせるだけで十分であることを示す; 少なくとも o(d−4) では、上記の文脈探索の類似性がクエリされるであろう ρ(r) = cg(k + rb) を十分近似する。 0.81
We show this results in poly(d) total regret3. この結果はpoly(d) total regret3で示される。 0.75
A similar strategy works for list contextual recommendation: there we discretize the curvature path for the knowledge set Kt into poly(d) candidate values for w∗, and then submit as our set of actions the best response for each of these candidates. ここでは、知識集合 Kt の曲率パスを w∗ のポリ(d) 候補値に分解し、その各候補に対して最良の応答を我々の行動集合として提出する。
訳抜け防止モード: 類似した戦略がリストコンテキストレコメンデーションに有効である ここで、知識集合 Kt の曲率経路を w∗ のポリ(d) 候補値に識別する。 そして それぞれの候補に対して 最善を尽くして 行動群として提出します。
1.3 Related work There is a very large body of work on recommender systems which employs a wide range of different techniques – for an overview, see the survey by Bobadilla et al [5]. 1.3関連作品 さまざまなテクニックが採用されているレコメンデータシステムには,非常に多くの作業があります – 概要については,Bobadilla氏らによる調査をご覧ください [5]。 0.71
Our formulation in this paper is closest to treatments of recommender systems which formulate the problem as an online learning problem and attack it with tools such as contextual bandits or reinforcement learning. 本論文の定式化は,オンライン学習問題として問題を定式化し,文脈バンディットや強化学習などのツールを用いて攻撃するレコメンダシステムの扱いに最も近い。 0.75
Some examples of such approaches can be seen in [17, 18, 23, 25, 26]. そのようなアプローチのいくつかの例は [17, 18, 23, 25 26] に見ることができる。 0.84
Similarly, there is a wide variety of work on online shortest path routing [3, 11, 12, 15, 24, 28] which also applies tools from online learning. 同様に、オンライン最短経路ルーティング(3、11、12、12、15、24、28)にもさまざまな取り組みがあり、オンライン学習のツールも適用しています。 0.77
One major difference between these works and the setting we study in our paper is that these settings often rely on some quantitative feedback regarding the quality of item recommended. これらの作業と本論文における設定の主な違いの1つは、推奨項目の品質に関する定量的フィードバックに依存することが多い点である。 0.83
In contrast, our paper only relies on qualitative feedback of the form “action x is the best action this round” or “action x is is at least as good as any action recommended”. 対照的に、我々の論文は「アクション x は、このラウンドで最も良いアクション」あるいは「アクション x は、推奨されるどんなアクションよりも少なくとも良い」という形式の質的なフィードバックにのみ依存する。 0.69
3The reason this type of algorithm does not work against strong separation oracles is that each point in this discretization 3 この種のアルゴリズムが強い分離神託に対して機能しない理由は、この離散化の各点が原因である。 0.67
could return a different direction vt, in turn corresponding to a different value of r 異なる方向 vt を返すことができ、r の異なる値に対応する。 0.77
5 5 0.85
One setting in the bandits literature that also possesses qualitative feedback is the setting of Duelling Bandits [27]. 質的なフィードバックも持っている盗賊文学の1つの設定は、デュエル・バンディットの設定である[27]。 0.58
In this model, the learner can submit a pair of actions and the feedback is a noisy bit signalling which action is better. このモデルでは、学習者は1対のアクションを送信でき、フィードバックはどのアクションが良いかを示すノイズのビット信号である。 0.64
However, their notion of regret (essentially, the probability the best arm would be preferred over the arms chosen by the learner) significantly differs from the notion of regret we measure in our setting (the loss to the user by following our recommendations instead of choosing the optimal actions). しかし,彼らの後悔の概念(学習者の選択した腕よりも最高の腕の方が好まれる可能性)は,我々の設定における後悔の概念とは大きく異なる(最適な行動を選択するのではなく,推奨に従うことでユーザを失う)。 0.83
Cutting-plane methods have a long and storied history in convex optimization. 切断面法は凸最適化の長い歴史を持つ。 0.66
The very first efficient algorithms for linear programming (based on the ellipsoid method [10, 14]). 線形計画のための非常に最初の効率的なアルゴリズム(楕円型 [10, 14] に基づく)。 0.84
Since then, there has been much progress in designing more efficient cutting-plane methods (e g [6]), but the focus remains on the number of calls to the separating oracle or the total running time of the algorithm. それ以来、より効率的な切削平面法(例えば [6])の設計には多くの進歩があったが、分離したオラクルへの呼び出し数やアルゴリズムの総実行時間に焦点が当てられている。 0.79
We are not aware of any work which studies cutting-plane methods under the notion of regret that we introduce in Section 1.1. 我々は,第1.1節で紹介した後悔という概念の下で,切削面法を研究するいかなる作業も意識していない。 0.60
Contextual search was first introduced in the form described in Section 2.2 in [16], where the authors gave the first time-horizon-indepen dent regret bound of O(poly(d)) for this problem (earlier work by [20] and [9] indirectly implied bounds of O(poly(d) log T ) for this problem). 文脈探索は [16] の節 2.2 で記述された形式で最初に導入され、著者らはこの問題に対して O(poly(d)) の時間-水平非依存的後悔境界を初めて与えた(この問題に対して [20] と [9] 間接的に O(poly(d) log T ) の値が与えられた)。 0.81
This was later improved by [19] to a near-optimal O(d log d) regret bound. これは後に[19]により、オプティマイズに近いo(d log d) に改善された。 0.73
The algorithms of both [16, 19] rely on techniques from integral geometry, and specifically on understanding the intrinsic volumes and Steiner polynomial of the set of possible values for w∗. 両方の [16, 19] のアルゴリズムは積分幾何学の技法、特に w∗ の可能な値の集合の内在体積とスタイナー多項式を理解することに依存する。 0.79
Some related geometric techniques have been used in recent work on the convex body chasing problem[1, 7, 22]. 近年, 凸体追尾問題[1, 7, 22]における幾何的手法が用いられている。 0.68
To our knowledge, our paper is the first paper to employ the fact that the curvature path cg(K + rB) is a bounded rational curve (and thus can be efficiently discretized) in the development of algorithms. 我々の知る限り、我々の論文はアルゴリズムの開発において曲率経路 cg(K + rB) が有界有理曲線(したがって効率的に離散化できる)であるという事実を利用する最初の論文である。 0.78
2 Model and preliminaries We begin by briefly reviewing the problems of contextual recommendation and designing low-regret cutting plane algorithms. 2モデルと予備 まず,コンテクストレコメンデーションの問題を簡単に検討し,低精細な切削平面アルゴリズムの設計から始める。 0.74
In all of the below problems, B = {w ∈ Rd | kwk2 ≤ 1} is the ball of radius 1 (and generally, all vectors we consider will be bounded to lie in this ball). 以下のすべての問題において、 B = {w ∈ Rd | kwk2 ≤ 1} は半径 1 の球である(そして一般に、我々が考えるすべてのベクトルはこの球の中に有界である)。 0.89
In contextual recommendation there is a hidden point w∗ ∈ B. 文脈的推奨では、隠れた点 w∗ ∈ B が存在する。 0.68
Each Contextual recommendation. それぞれのコンテキストレコメンデーション。 0.55
round t (for T rounds) we are given a set of possible actions Xt ⊆ B. 円 t (T ラウンド) には、可能な作用の集合 Xt = B が与えられる。 0.61
If we choose action xt ∈ Xt we obtain t = arg maxx∈Xthx, w∗i, the identity of the reward hxt, w∗i (but do not learn this value). 作用 xt ∈ Xt を選択すると t = arg maxx・Xthx, w∗i, 報酬 hxt, w∗i を得る(ただし、この値は学ばない)。 0.73
Our feedback is x∗ best action4. フィードバックはx∗ best action4です。 0.75
Our goal is to minimize the total expected regret E[Reg] = EhPT t − xt, w∗ii. 我々の目標は、予想される全後悔 E[Reg] = EhPT t − xt, w∗ii を最小化することである。 0.67
Note that since the feedback is deterministic, this expectation is only over the randomness of the learner’s algorithm. 注意 フィードバックは決定論的であるため、この期待は学習者のアルゴリズムのランダム性にのみ依存する。 0.60
It will be useful to establish some additional notation for discussing algorithms for contextual recommendation. コンテクストレコメンデーションのためのアルゴリズムを議論するための追加の表記法を確立するのに役立つだろう。 0.62
We define the knowledge set Kt to be the set of possible values for w∗ given the knowledge we have obtained by round t. Note that the knowledge set Kt is always convex, since the feedback we receive each round (that hx∗, w∗i ≥ hx, w∗i for all x ∈ Xt) can be written as an intersection of several halfspaces (and the initial knowledge set K1 = B is convex). 各ラウンド(すべての x ∈ xt に対して hx∗, w∗i ≥ hx, w∗i) を受け取るフィードバックは、いくつかの半空間の交叉として書ける(そして初期知識集合 k1 = b は凸である)ので、知識集合 kt は常に凸であることに注意せよ。
訳抜け防止モード: 我々は、知識集合 Kt をw∗ の可能な値の集合と定義し、この知識集合 Kt が常に凸であることに注意する。 各ラウンドのフィードバック(すべての x ∈ Xt に対して hx∗, w∗i ≥ hx, w∗i であること)から いくつかのハーフスペース(および)の交差点として書くことができる 初期知識集合 K1 = B は凸である。
In fact, we can say more. 実際、私たちはもっと言える。 0.69
Given a w ∈ Kt, let w ∈ Kt を与えられたら、 0.85
t=1hx∗ be the set of optimal actions in Xt if the hidden point was w. We can then partition Kt into several convex subregions based on the value of BRt(w); specifically, let t=1hx∗ 隠れ点が w であれば、xt の最適作用の集合である。次に、kt を brt(w) の値に基づいて複数の凸部分領域に分割することができる。 0.52
BRt(w) = arg max BRt(w) = arg max 0.85
x∈Xthx, wi xhtmlxthx, wi 0.63
be the region of Kt where x is the optimal action to play in response. は Kt の領域で、x は応答で再生する最適なアクションである。 0.73
Then: Rt(x) = {w ∈ Kt|x ∈ BRt(w)} すると Rt(x) = {w ∈ Kt|x ∈ BRt(w)} 0.74
1. Each Rt(x) is a convex subset of Kt. 1. 各 Rt(x) は Kt の凸部分集合である。 0.84
2. The regions Rt(x) have disjoint interiors and partition Kt. 2. 領域 Rt(x) は不連結な内部と分割 Kt を持つ。 0.81
3. Kt+1 will equal the region Rt(x∗) (where x∗ ∈ BRt(w∗) is the optimal action returned as feedback). 3. Kt+1 は領域 Rt(x∗) と等しい(ここで x∗ ∈ BRt(w∗) はフィードバックとして返される最適作用である)。 0.81
4If this argmax is multi-valued, the adversary may arbitrarily return any element of this argmax. 4 このargmaxが多重値であれば、敵はこのargmaxの任意の要素を任意に返すことができる。
訳抜け防止モード: 4 argmax が multi-valued であれば 敵は任意のargmax要素を返すことができる。
6 6 0.85
We also consider two other variants of contextual recommendation in this paper (list contextual recommendation and local contextual recommendation). 本論文では、コンテキストレコメンデーションの他の2つのバリエーション(リストコンテキストレコメンデーションとローカルコンテキストレコメンデーション)についても検討する。 0.54
We will formally define them as they arise (in Sections 5 and 6 respectively). それらが生じると正式に定義する(それぞれ第5節と第6節)。 0.69
Designing low-regret cutting-plane algorithms. 低反射切削平面アルゴリズムの設計 0.68
In a low-regret cutting-plane algorithm, we again have a hidden point w∗ ∈ B. 低回帰切断平面アルゴリズムでは、再び隠れた点 w∗ ∈ B を持つ。 0.77
Each round t (for T rounds) we can query a separation oracle with a point pt in B. 各ラウンド t (T ラウンド) は B に点 pt の分離オラクルを問うことができる。 0.63
The separation oracle then provides us with an adversarially chosen direction vt (with kvtk = 1) that satisfies hw∗, vti ≥ hpt, vti. 分離オラクルは、hw∗, vti ≥ hpt, vtiを満たす反対に選択された方向 vt (kvtk = 1) を提供する。 0.69
The regret in round t is equal to hw∗ − pt, vti, and our goal is to minimize t=1hw∗ − pt, vtii. ラウンド t の後悔は hw∗ − pt, vti に等しく、我々の目標は t=1hw∗ − pt, vtii を最小化することである。 0.77
Again, since the feedback is deterministic, the the total expected regret E[Reg] = EhPT 繰り返しますが、フィードバックは決定論的であるため、期待された総後悔E[Reg] = EhPT 0.71
expectation is only over the randomness of the learner’s algorithm. 予測は学習者のアルゴリズムのランダム性にのみ適用される。 0.78
As with contextual recommendation, it will be useful to consider the knowledge set Kt, consisting of possibilities for w∗ which are still feasible by the beginning of round t. Again as with contextual recommendation, Kt is always convex; here we intersect Kt with the halfspace provided by the separation oracle every round (i.e. 文脈的レコメンデーションと同様に、文脈的レコメンデーションと同様に、文脈的レコメンデーションと同様に、Ktは常に凸であり、ここでは Kt は各ラウンド(すなわち)ごとに分離オラクルによって提供されるハーフスペースと交差する。
訳抜け防止モード: 文脈的レコメンデーションと同様に、知識集合 kt を考えることは有用である。 w∗ の可能性から成るさま コンテクストレコメンデーションのように、第tラウンドの開始までにはまだ実現可能です。 ktは常に凸である ここで kt と分離オラクルが提供するハーフスペースを各ラウンド (つまり) 毎に交わします。
Kt+1 = Kt ∩ {hw − pt, vti ≥ 0}). Kt+1 = Kt > {hw − pt, vti ≥ 0})。 0.84
Unless otherwise specified, the separation oracle can arbitrarily choose vt as a function of the query point pt. それ以外の指定がなければ、分離オラクルは問合せポイントptの関数として vt を任意に選択できる。 0.73
For obtaining low-regret algorithms for list contextual recommendation, it will be useful to consider a variant of this problem where the separation oracle must commit to vt (up to sign) at the beginning of round t. Specifically, at the beginning of round t (before observing the query point pt), the oracle fixes a direction ut. リストコンテキストレコメンデーションのための低regretアルゴリズムを得るためには、分離オラクルがラウンドtの開始時にvt(符号まで)にコミットしなければならないこの問題の変種を考えるのが有用である。
訳抜け防止モード: リストコンテキストレコメンデーションのための低-後悔のアルゴリズムを得るために。 分離オラクルがラウンド t の開始時に vt にコミットしなければならないこの問題の変種を考えるのに役立つだろう。 ラウンドtの開始時に(クエリポイントptを観察する前に) オラクルは方向を直します
Then, on query pt, the separation oracle returns the direction vt = ut if hw − pt, uti ≥ 0, and the direction vt = −ut otherwise. そして、クエリ pt において、分離オラクルは hw − pt, uti ≥ 0 のとき方向 vt = ut を返し、そうでなければ方向 vt = −ut を返す。 0.81
We call such a separation oracle a weak separation oracle; an algorithm that only works against such separation oracles is a low-regret cutting-plane algorithm for weak separation oracles. このような分離オラクルを弱い分離オラクルと呼び、そのような分離オラクルに対してのみ作用するアルゴリズムは、弱い分離オラクルに対する低反射切削平面アルゴリズムである。 0.67
Note that this distinction only matters when the learner is using a randomized algorithm; if the learner is deterministic, the adversary can predict all the directions vt in advance. この区別は、学習者がランダムなアルゴリズムを使っている場合にのみ重要であり、学習者が決定論的であれば、敵は事前にすべての方向vtを予測できる。 0.69
2.1 Convex geometry preliminaries and notation We will denote by Convd the collection of all convex bodies in Rd. 2.1 convex geometry preliminaries and notation rd 内のすべての凸体の集合をconvdする。 0.67
Given a convex body K ∈ Convd, we will use Vol(K) = RK 1dx to denote its volume (the standard Lebesgue measure). 凸体 K ∈ Convd が与えられると、Vol(K) = RK 1dx を使って体積を表す(標準ルベーグ測度)。 0.69
Given two sets K and L in Rd, their Minkowski sum is given by K + L = {x + y; x ∈ K, y ∈ L}. Rd の二つの集合 K と L が与えられたとき、ミンコフスキーの和は K + L = {x + y; x ∈ K, y ∈ L} で与えられる。 0.84
Let Bd denote the unit ball in Rd, let Sd−1 = {x ∈ Rd;kxk2 = 1} denote the unit sphere in Rd and let κd = Vol(Bd) be the volume of the i-th dimensional unit ball. Bd は Rd の単位球を表し、Sd−1 = {x ∈ Rd;kxk2 = 1} は Rd の単位球面を表し、κd = Vol(Bd) を i-次元単位球の体積とする。 0.78
When clear from context, we will omit the superscripts on Bd and Sd−1. 文脈から明確にすると、Bd と Sd−1 上のスーパースクリプトを省略する。 0.60
We will write cg(K) = (RK xdx)/(RK 1dx) to denote the center of gravity (alternatively, centroid ) of K. cg(K) = (RK xdx)/(RK 1dx) と書くと、K の重心 (alternatively, centroid ) を表す。 0.70
Given a direction u ∈ Sd−1 and convex set K ∈ Convd we define the width of K in the direction u as: 向き u ∈ Sd−1 と凸集合 K ∈ Convd が与えられたとき、方向 u における K の幅を次のように定義する。 0.74
width(K; u) = max width(K; u) = max 0.85
x∈Khu, xi − min x ∈khu, xi −min 0.81
x∈Khu, xi xhtmlkhu, xi 0.58
Approximate Grunbaum and John’s Theorem Finally, we state two fundamental theorems in convex geometry. 近似 Grunbaum と John's Theorem 最後に、凸幾何学における2つの基本的な定理を述べる。 0.71
Grunbaum’s Theorem bounds the volume of the convex set in each side of a hyperplane passing through the centroid. grunbaumの定理は、中心面を通過する超平面の各辺に設定された凸の体積を制限している。 0.67
For our purposes it will be also important to bound a cut that passes near, but not exactly at the centroid. 私たちの目的のためには、遠心部ではなく、近くを通るカットをバインドすることも重要です。 0.72
The bound given in the following paragraph comes from a direct combination of Lemma B.4 and Lemma B.5 in Bubeck et al [7]. 次の段落で与えられる境界は、ブベック等におけるLemma B.4とLemma B.5の直接的な組み合わせに由来する。 0.58
We will use the notation Hu(p) = {x | hx, ui = hp, ui} to denote the halfspace passing through p with p を通る半空間を表すために、Hu(p) = {x | hx, ui = hp, ui} という表記を用いる。 0.74
normal vector u. 通常のベクトル u。 0.79
Similarly, we let H + Theorem 2.1 (Approximate Grunbaum [4, 7]). 同様に、H + Theorem 2.1 (Approximate Grunbaum [4, 7]) とする。 0.83
Let K ∈ Convd, c = cg(K) and u ∈ Sd−1. K ∈ Convd, c = cg(K) および u ∈ Sd−1 とする。 0.96
Then consider the semi-space H+ = {x ∈ Rd;hu, x − ci ≥ t} for some t ∈ R+. すると、ある t ∈ R+ に対して半空間 H+ = {x ∈ Rd;hu, x − ci ≥ t} を考える。 0.86
Then: 2t(d + 1) u (p) = {x | hx, ui ≥ hp, ui}. 2t(d + 1) u (p) = {x | hx, ui ≥ hp, ui} である。 0.75
width(K; u) width (複数形 widths) 0.70
Vol(K ∩ H+) Vol(K, H+) 0.84
Vol(K) 1 e − Vol(K) 1 e − 0.85
≥ John’s theorem shows that for any convex set K ∈ Convd, we can find an ellipsoid E contained in K such ≥ ジョンの定理は、任意の凸集合 K ∈ Convd に対して、K に含まれる楕円体 E を見つけることができることを示している。
訳抜け防止モード: ≥ ジョンの定理は 任意の凸集合 K ∈ Convd に対して、K に含まれる楕円体 E を見つけることができる。
that K is contained in (some translate of) a dilation of E by a factor of d. K が d の因子による E の拡大に含まれる(ある訳)。 0.61
7 7 0.85
Theorem 2.2 (John’s Theorem). Theorem 2.2 (John's Theorem)。 0.89
Given K ∈ Convd, there is a point q ∈ K and an invertible linear transformation A : Rd → Rd such that K ∈ Convd が与えられたとき、点 q ∈ K と可逆線型変換 A : Rd → Rd が存在する。 0.82
We call the ellipsoid E = A−1(q + B) in Theorem 2.2 the John ellipsoid of K. 我々は Theorem 2.2 の楕円体 E = A−1(q + B) を K のジョン楕円体と呼ぶ。 0.76
q + B ⊆ A(K) ⊆ q + dB. q + B > A(K) > q + dB である。 0.87
2.2 Contextual search 2.2 コンテキスト検索 0.74
In this section, we briefly sketch the algorithm and analysis of [19] for the standard contextual search problem. 本稿では,標準的な文脈探索問題に対する[19]のアルゴリズムと解析を簡潔に記述する。 0.86
We will never use this algorithm directly, but many pieces of the analysis will prove useful in our constructions of low-regret cutting-plane algorithms. このアルゴリズムを直接使用することはないが、解析の多くの部分が低精細な切削面アルゴリズムの構築に有用であることを証明している。 0.67
Recall that in contextual search, each round the learner is given a direction vt. コンテキスト検索では、各ラウンドの学習者には方向vtが与えられる。 0.63
The learner is trying to learn the location of a hidden point w∗, and at time t has narrowed down the possibilities of w∗ to a knowledge set Kt. 学習者は隠れ点 w∗ の位置を学習しようとしており、t は時折 w∗ の可能性を知識集合 kt に狭めている。
訳抜け防止モード: 学習者は試みています 隠れた点 w∗ の位置を知るために そして t は t の知識集合 Kt への w∗ の可能性を狭めた。
The algorithm of [19] runs the following steps: 19]のアルゴリズムは以下のステップを実行します。 0.86
1. Compute the width w = width(Kt; vt) of Kt in the direction vt. Let r = 2⌈lg(w/10d)⌉ (rounding w/10d 1. 方向 vt における kt の幅 w = width(kt; vt) を計算する。
訳抜け防止モード: 1. 方向 vt における Kt の幅 w = 幅 (Kt ; vt ) を計算する。 r = 2\lg(w/10d) を (丸い w/10d) とする。
to a nearby power of two). 近くの2つの力に)。 0.74
2. Consider the set ˜K = Kt + rB. 2. K = Kt + rB の集合を考える。 0.82
Choose yt so that the hyperplane H = {w | hvt, wi = yt} divides the 超平面 H = {w | hvt, wi = yt} が割り切れるように yt を選択する。 0.84
set ˜K into two pieces of equal volume. K を 2 つの等しい体積に設定する。 0.72
We can understand this algorithm as follows. このアルゴリズムは次のように理解できる。 0.77
Classic cutting-plane methods try to decrease Vol(Kt) by a constant factor every round (arguing that this decrease can only happen so often before one of our hyperplanes passes within some small distance to our feasible region). 古典的な切削平面法は、各ラウンドの定数係数でvol(kt)を減少させようとする(この減少は、我々の超平面の1つが我々の実現可能な領域まで少しの距離内を通過する前にしか起こり得ない)。 0.62
The above algorithm can be thought of as a multi-scale variant of this approach: they show that if we incur loss w ≈ dr in a round (since loss in a round is at most the width), the potential function Vol(Kt + rB) must decrease by a constant factor. 上記のアルゴリズムはこのアプローチのマルチスケールな変種と見なすことができる: ラウンドにおける損失 w > dr が(ラウンドにおける損失が少なくともその幅であるから)得られれば、ポテンシャル函数 Vol(Kt + rB) は定数因子によって減少しなければならない。 0.83
Since Vol(Kt + rB) ≥ Vol(rB) = rdκd, we can incur a loss of this size at most O(d log(2/r)) times. Vol(Kt + rB) ≥ Vol(rB) = rdκd なので、ほとんどの O(d log(2/r)) でこの大きさの損失が生じる。 0.80
Summing over all possible discretized values of r (i.e. r の任意の離散値(すなわち)を総和する 0.68
powers of 2 less than 1), we arrive at an O(d log d) regret bound. 1 より 2 未満のパワーでは、O(d log d) の後悔境界に達する。 0.59
There is one important subtlety in the above argument: if we let H + = {w | hvt, wi ≥ yt} be the halfspace defined by H, the two sets (Kt ∩ H +) + rB and (Kt + rB) ∩ H + are not equal. H + = {w | hvt, wi ≥ yt} を H によって定義されるハーフ空間とすると、2つの集合 (Kt, H +) + rB と (Kt + rB) > H + は等しくない。
訳抜け防止モード: 上記の議論には1つの重要な微妙な点がある: h + = { w | hvt, とする。 wi ≥ yt } は h によって定義される半空間であり、2つの集合 (kt ≥ h + ) + rb そして ( kt + rb ) , h + は等しくない。
The volume of the first set represents the new value of our potential (i.e. 最初の集合の体積は、我々のポテンシャル(すなわち)の新しい値を表す。 0.81
Vol(Kt+1 + rB)), but it is the second set that has volume equal to half our current potential (i.e. Vol(Kt+1 + rB)) しかし、これは現在のポテンシャルの半分に等しい体積を持つ2番目の集合である。 0.83
1 2 Vol(Kt + rB)). 1 2 Vol(Kt + rB)。 0.78
Luckily, our choice of r allows us to relate these two quantities in a way so that our original argument works. 幸いにも、r の選択は、元の議論がうまくいくように、これらの 2 つの量を関連付けることを可能にする。
訳抜け防止モード: 幸運にも r の選択は 私たちはこの2つの量を元の議論が機能するように関連付けるべきです。
Let H divide K into K + and K −. H を K+ と K− に分割する。 0.73
Note that Vol(K + + rB) + Vol(K − + rB) = Vol(K + rB) + Vol((K ∩ H) + rB) (in particular, K + rB and (K ∩ H) + rB are the union and intersection respectively of K + + rB and K − + rB). 注意すべき点は、Vol(K + + rB) + Vol(K − + rB) = Vol(K + rB) + Vol((K + rB) + rB) (特に、K + rB と (K + rB) + rB はそれぞれ K + + rB と K − + rB の和と交わりである。 0.84
Since Vol(K + + rB) = Vol(K − + rB), to bound Vol(K + + rB)/Vol(K + rB) it suffices to bound Vol((K ∩ H) + rB). Vol(K + + rB) = Vol(K − + rB) であるから、Vol(K + + rB)/Vol(K + rB) は、Vol((K ) H) + rB) となる。 0.78
We do so in the following lemma (which will also prove useful to us in later analysis). 私たちは次の補題でそうします(これは後での分析でも役に立ちます)。 0.76
Lemma 2.3. Given K ∈ Convd and u ∈ Sd−1, let H be a hyperplane of the form {w | hw, ui = b} (for some b ∈ R). 補題2.3。 K ∈ Convd と u ∈ Sd−1 が与えられたとき、H を {w | hw, ui = b} (ある b ∈ R に対して)という形の超平面とする。 0.64
Then: Vol((K ∩ H) + rB) ≤(cid:18) すると Vol((K, H) + rB)≤(cid:18) 0.66
2rd width(K; u)(cid:19) · Vol(K + rB) 第2回 幅(K; u)(cid:19)·Vol(K + rB) 0.64
Proof. Let V = Vold−1((K +rB)∩H) be the volume of the (d−1)-dimensional cross-section of K +rB carved out by H. Note first that we can write any point in (K∩H)+ rB in the form w + λu, where w ∈ (K + rB)∩H and λ ∈ [−r, r]. 証明。 まず、任意の点を w + λu の形に書けることに注意してください。 ここで w ∈ (k + rb)\h と λ ∈ [−r, r] である。
訳抜け防止モード: 証明。 V = Vold−1((K + rB) = H ) を(d−1)-次元断面の体積とし、K + rB を H で彫った部分とする。 ここで w ∈ ( K + rB) = H と λ ∈ [ −r, R]
It follows that (3) We will now bound V . その通りです (3) V に縛られる。 0.54
Let K = (K + rB)∩ H. Let p+ be the point in K + rB maximizing hu, pi, and let p− be the point in K + rB minimizing hu, pi (so p− and p+ certify the width). p+ を hu, pi を最大化する K + rB の点とし、p− を hu, pi を最小化する K + rB の点とする(したがって p− と p+ は幅を証明)。
訳抜け防止モード: K = ( K + rB) = H とする。 p+ を K + rB の極大化 hu の点とする。 pi, and let p− be the point in K + rB minimizing hu, pi (つまり p− と p+ は幅を認証する)。
Consider the cones C− and C+ formed by taking the convex hull Conv(p−, K) and Conv(p+, K) respectively. 凸殻 Conv(p−,K) と Conv(p+,K) をそれぞれ取ることにより形成される錐体 C− と C+ を考える。 0.83
C− and C+ are disjoint and contained within K + rB, so c− と c+ は結合せず、k + rb に含まれる。 0.69
Vol((K ∩ H) + rB) ≤ 2rV . Vol((K, H) + rB) ≤ 2rV である。 0.86
8 8 0.85
But now note that by the formula for the volume of a cone, ここでは、円錐の体積の式に注意してください。 0.37
Vol(C−) + Vol(C+) ≤ Vol(K + rB). Vol(C−) + Vol(C+) ≤ Vol(K + rB)。 0.92
Vol(C−) + Vol(C+) = Vol(C−) + Vol(C+) = 1.00
1 d · width(K + rB; u) · Vold−1(K) ≥ 1 d · width(K + rB; u) · Vold−1(K) ≥ 0.94
width(K; u) width (複数形 widths) 0.70
d · V . It follows that d ・V。 その通りです 0.69
V ≤ d width(K; u) V ≤ d width (複数形 widths) 0.80
Vol(K + rB). Vol(K + rB)。 0.80
(4) Substituting this into (3), we arrive at the theorem statement. (4) これを(3)に置き換えると、定理のステートメントに到達します。 0.78
This lemma allows us to conclude our analysis of the contextual search algorithm. この補題によって文脈探索アルゴリズムの分析を結論付けることができる。 0.78
In particular, since we have chosen r ≈ width(K, vt)/10d, by applying this lemma we can see that in our analysis of contextual search, Vol((K ∩ H) + rB) ≤ 0.2Vol(K + rB), from which it follows that Vol(K + + rB)/Vol(K + rB) ≤ 0.6. 特に、我々は、この補題を適用することで、Vol(K + + rB) ≤ 0.2Vol(K + rB) ≤ 0.6(Vol(K + + rB)/Vol(K + rB) ≤ 0.6(Vol(K + rB) ≤ 0.6) を選択することができる。
訳抜け防止モード: 特に、r > 幅 (K, vt)/10d を選んだからである。 この補題を適用することで 文脈探索の分析で Vol((K ) H ) + rB ) ≤ 0.2Vol(K + rB ) そこから、Vol(K + + rB)/Vol(K + rB ) ≤ 0.6 となる。
3 From Cutting-Plane Algorithms to Contextual Recommendation 3 カットプレーンアルゴリズムからコンテキストレコメンデーションへ 0.63
We begin by proving a reduction from designing low-regret cutting plane algorithms to contextual recommendation. まず、低解像度のカットプレーンアルゴリズムを設計することから、コンテキストレコメンデーションへ還元することから始める。 0.53
Specifically, we will show that given a regret ρ cutting-plane algorithm, we can use it to construct an O(ρ)-regret algorithm for contextual recommendation. 具体的には, 残念な ρ カットプレーンアルゴリズムを用いて, 文脈的推薦のための O(ρ)-regret アルゴリズムを構築することができることを示す。 0.81
Note that while these two problems are similar in many ways (e g この2つの問題は様々な点で似ているが(例えば) 0.81
they both involve searching for an unknown point w∗), they are not completely identical. どちらも未知の点 w* を探索するが、それらは全く同じではない。 0.72
Among other things, the formulation of regret although similar is qualitatively different between the two problems (i.e. 特に、後悔の定式化は2つの問題(すなわち、類似点)の間で定性的に異なる。 0.69
between expressions (1) and (2)). 式(1)と(2))の間。 0.56
In particular, in contextual recommendation, the regret each round is hx∗ t −xt, w∗i, whereas for cutting-plane algorithms, the regret is given by hw∗ − pt, vti. 特に文脈的推奨では、各ラウンドの後悔は hx∗ t −xt, w∗i であるのに対し、切断平面アルゴリズムでは、後悔は hw∗ − pt, vti によって与えられる。 0.67
Nonetheless, we will be able to relate these two notions of regret by considering a separation oracle that always returns a halfspace in the direction of x∗ t − xt. それでも、この2つの後悔の概念を、常に x∗ t − xt の方向に半空間を返す分離オラクルを考えることで、関連付けることができる。 0.67
We present this reduction below. この削減を以下に示す。 0.75
Theorem 3.1. Given a low-regret cutting-plane algorithm A with regret ρ, we can construct an O(ρ)-regret algorithm for contextual recommendation. 定理3.1。 後悔 ρ を持つ低精細な切削平面アルゴリズム a が与えられると、文脈推薦のために o(ρ)-regret アルゴリズムを構築することができる。 0.63
Proof. We will simultaneously run an instance of A with the same hidden vector w∗. 証明。 同じ隠れベクトル w∗ を持つ A のインスタンスを同時に実行する。 0.66
Each round we will ask A for its query pt to the separation oracle. それぞれのラウンドに対して,oracleの分離に対するクエリptを a に求めます。 0.64
We will then compute a xt ∈ BRt(pt) (recall that BRt(w) is the optimal action to play if w is the true hidden vector) and submit xt as our action for this round of contextual recommendation. 次に、xt ∈ brt(pt) を計算し(w が真の隠れベクトルであるなら、brt(w) がプレーする最適なアクションであると再呼び)、この一連の文脈勧告に対する我々のアクションとして xt を提出する。
訳抜け防止モード: すると xt ∈ BRt(pt ) を計算する(ただし BRt(w ) が w が真の隠れベクトルであるときの最適作用であることを思い出す)。 コンテキストレコメンデーションのラウンドの アクションとしてxtを提出します
We then receive feedback x∗ フィードバック x∗ を受け取ります 0.70
t ∈ BRt(w∗). t ∈ BRt(w∗)。 0.69
Consider the following two cases: 以下の2つの事例を考える。 0.66
If x∗ t = xt, then our contextual recommendation algorithm incurs zero regret since we successfully Case 1: chose the optimal point. x∗ ならば t = xt ならば、私たちのコンテキストレコメンデーションアルゴリズムは、ケース 1: 最適点を選択したので、ゼロ後悔を招きます。 0.70
In this case we ignore this round for A (i.e. この場合、このラウンドはA(すなわち)は無視する。 0.70
we reset its state to its state at the beginning of round t). ラウンドtの始めに状態をその状態にリセットします)。 0.55
Case 2: to query pt. ケース2:ptをクエリする。 0.77
Note that this is a valid answer, since これが妥当な答えであることに注意してください 0.67
t 6= xt, let vt = (x∗ t 6 = xt, vt = (x∗ 0.89
t − xt)/kx∗ t − xt)/kx∗ 0.88
If x∗ t − xtk. x∗ ならば t − xtk。 0.72
We will return vt to A as the separation oracle’s answer oracle の回答として vt を a に返します。 0.58
hw∗ − pt, vti = hw∗ − pt, vti = 0.97
1 t − xtk kx∗ 1 t − xtk kx∗ 0.82
(hw∗, x∗ t − xti + hpt, xt − x∗ (hw∗, x∗) t − xti + hpt, xt − x∗ 0.95
ti) ≥ Here the final inequality holds since (by the definition of BRt(pt)) hpt, xti ≥ hpt, xi for any x ∈ Xt. ti) ≥ ここでの最終不等式は((brt(pt)) hpt, xti ≥ hpt, xi の定義によって)任意の x ∈ xt に対して成り立つ。 0.78
The RHS of (5) is in turn larger than zero, since hw∗, x∗ ti ≥ hw∗, xi for any x ∈ Xt (and thus this is a valid answer to the separation oracle). (5) の RHS は、任意の x ∈ Xt に対して hw∗, x∗ ti ≥ hw∗, xi であるため、0 より大きい(したがって、これは分離オラクルに対する有効な解である)。 0.85
Moreover, note that the regret we incur under contextual recommendation is exactly hw∗, x∗ さらに、文脈的推奨の下での後悔は、ちょうど hw∗, x∗ である。 0.64
t − xti, so by rearranging equation (5), we have that: t − xti なので、方程式 (5) を並べ替えることで、 0.63
1 t − xtkhw∗, x∗ kx∗ 1 t − xtkhw∗, x∗ kx∗ 0.88
t − xti. (5) t − xti。 (5) 0.82
9 9 0.85
hw∗, x∗ t − xti ≤ kx∗ hw∗, x∗ t − xti ≤ kx∗ 0.97
t − xtkhw∗ − pt, vti ≤ 2hw∗ − pt, vti. t − xtkhw∗ − pt, vti ≤ 2hw∗ − pt, vti である。 0.86
It follows that the total regret of our algorithm for contextual recommendation is at most twice that of 文脈的推薦のためのアルゴリズムの完全な後悔は、少なくともその2倍である。 0.63
A. Our regret is thus bounded above by 2ρ, as desired. A。 したがって、我々の後悔は、望んだように2ρに制限される。 0.64
Note that the reduction in Theorem 3.1 is efficient as long as we have an efficient method for optimizing a linear function over Xt (i.e. Xt 上の線型関数を最適化する効率的な方法がある限り、定理 3.1 の減少は効率的である。 0.77
for computing BRt(w)). BRt(w) を計算します。 0.72
In particular, this means that this reduction can be practical even in settings where Xt may be combinatorially large (e g the set of s-t paths in some graph). 特にこれは、Xt が組合せ的に大きい(例えばグラフ内の s-t パスの集合)設定でも、この還元は実用的であることを意味する。 0.74
Note also that this reduction does not work if A is only low-regret against weak separation oracles. また、aが弱い分離オラクルに対してのみ低リグレットである場合、この削減は機能しない。 0.57
This is since the direction vt we choose does depend non-trivially on the point pt (in particular, we choose xt ∈ BRt(pt)). これは、私たちが選択した方向 vt が点 pt に非自明に依存するためである(特に xt ∈ BRt(pt))。 0.81
Later in Section 5.3, we will see how to use ideas from designing cutting-plane methods for weak separation oracles to construct low-regret algorithms for list contextual recommendation – however we do not have a black-box reduction in that case, and our construction will be more involved. 後で、セクション5.3で、弱い分離オラクルのためにカットプレーンメソッドの設計からアイデアを活用して、低精細なアルゴリズムを構築して、文脈の推奨をリスト化する方法について見ていく。 0.57
4 Designing Low-Regret Cutting-Plane Algorithms 4 ローレグレット切削面アルゴリズムの設計 0.69
In this section we will describe how to construct low-regret cutting-plane algorithms for strong separation oracles. この節では、強い分離オラクルのための低反射切削平面アルゴリズムの構築方法について述べる。 0.56
4.1 An exp(O(d log d))-regret cutting-plane algorithm 4.1 exp(o(d log d))-regret cutting-planeアルゴリズム 0.91
We begin with a quick proof that always querying the center of the John ellipsoid of Kt leads to a exp(O(d log d))-regret cutting-plane algorithm. 我々は、Kt の John 楕円体の中心を常にクエリする素早い証明から始め、exp(O(d log d))-regret cutting-planeアルゴリズムへと導かれる。 0.80
Interestingly, although this corresponds to the classical ellipsoid algorithm, our analysis will instead proceed along the lines of the analysis of the contextual search algorithm summarized in Section 2.2. 興味深いことに、これは古典的楕円体アルゴリズムに対応するが、我々の分析は2.2節で要約された文脈探索アルゴリズムの分析の行に沿って進む。 0.74
We will need the following lemma. 私たちは次の補題が必要です。 0.63
Lemma 4.1. Let K ∈ Convd be an arbitrary convex set and let r ≥ 0. 補題4.1。 K ∈ Convd を任意の凸集合とし、r ≥ 0 とする。 0.71
Let E be the John ellipsoid of K, and let H be a hyperplane that passes through the center of E, dividing K into two regions K + and K −. E を K のジョン楕円体とし、H を E の中心を通る超平面とし、K を 2 つの領域 K + K − に分割する。 0.78
Then Vol(K + + rB) ≤(cid:18)1 − そして Vol(K + + rB) ≤(cid:18)1 − 0.82
1 10dd(cid:19)(cid:0)V ol(K + + rB) + Vol(K − + rB)(cid:1) 1 10dd(cid:19)(cid:0)V ol(K + + rB) + Vol(K − + rB)(cid:1) 0.89
Proof. Let H divide E into the two regions E+ and E− analogously to how it divides K into K + and K −. 証明。 H を 2 つの領域 E+ と E− に分けると、K を K + と K − に分割する方法と類似する。 0.73
Note that since E ⊆ K ⊆ dE (translating K so that E is centered at the origin), we can write: 1 2dd . 注意すべき点は、E は K を原点中心に翻訳するので、1 2dd と書くことができることである。 0.63
0.5 · Vol(E + rB) Vol(dE + rB) ≥ 0.5 · Vol(E + rB) Vol(dE + rB) ≥ 0.96
Vol(K − + rB) Vol(K + rB) ≥ Vol(K − + rB) Vol(K + rB) ≥ 0.85
Vol(E− + rB) Vol(dE + rB) ≥ Vol(E− + rB) Vol(dE + rB) ≥ 0.91
1 2dd Vol(E + rB) 1 2dd Vol(E + rB) 0.87
Vol(E + (r/d)B) ≥ Vol(E + (r/d)B) ≥ 1.00
(6) On the other hand, by monotonicity we also have that (6) 一方、単調性によってもそうである。 0.69
It follows that The conclusion then follows since その通りです その後、結論は続く。 0.58
Vol(K + + rB)/Vol(K − + rB) ≤ 2dd. Vol(K + + rB)/Vol(K − + rB) ≤ 2dd。 0.92
Vol(K + + rB) Vol(K + rB) ≤ 1. Vol(K + + rB) Vol(K + rB) ≤ 1。 0.84
2dd ≤(cid:18)1 − 2dd ≤(cid:18)1 − 0.94
1 10dd(cid:19) (2dd + 1). 1 10dd (cid:19) (2dd + 1)。 0.84
10 10 0.85
We can now modify the analysis of contextual search to make use of Lemma 4.1. Lemma 4.1を使ってコンテキスト検索の分析を変更できるようになった。 0.79
In particular, we will show that for each round t, there’s some r (roughly proportional to the current width) where Vol(Kt + rB) decreases by a multiplicative factor of (1 − d−O(d)). 特に、各円 t に対して、Vol(Kt + rB) が (1 − d−O(d)) の乗法因子によって減少する r が存在することを示す。 0.54
Theorem 4.2. The cutting-plane algorithm which always queries the center of the John ellipsoid of Kt incurs exp(O(d log d)) regret. 理論4.2。 Kt の John ellipsoid の中心を常にクエリする切断平面アルゴリズムは exp(O(d log d)) を後悔させる。 0.68
Proof. Fix a round t, and let K = Kt be the knowledge set at time t. Let E be the John ellipsoid of K and let pt be the center of E. When we query the separation oracle with pt, we get a hyperplane H (defined by vt) that passes through pt and divides K into K + = Kt+1 and K − = K \ Kt+1. 証明。 E を K のジョン楕円体とし、pt を E の中心とする。分離オラクルを pt で問うと、 pt を通過して K を K + = Kt+1 と K − = K \ Kt+1 に分割する超平面 H (vt で定義される) が得られる。
訳抜け防止モード: 証明。 丸いtを固定し、離す K = Kt はタイムトの知識集合である。 をKのジョン楕円体とし、 pt (複数形 pts) 我々は超平面 H ( vt で定義される) を得る。 pt を通過して K を K + = Kt+1 と K − = K \ Kt+1 に分割する。
By Lemma 4.1, for any r ≥ 0, we have that Vol(K + + rB) ≤(cid:18)1 − Lemma 4.1 により、任意の r ≥ 0 に対して Vol(K + + rB) ≤(cid:18)1 − 0.87
1 10dd(cid:19)(cid:0)V ol(K + + rB) + Vol(K − + rB)(cid:1) 1 10dd(cid:19)(cid:0)V ol(K + + rB) + Vol(K − + rB)(cid:1) 0.89
Note that (as in Section 2.2), Vol(K + + rB) + Vol(K − + rB) = Vol(K + rB) + Vol((K ∩ H) + rB). 注意すべき点は、(セクション2で言うように) Vol(K + + rB) + Vol(K − + rB) = Vol(K + rB) + Vol((K + rB) + rB) である。 0.92
By Lemma 2.3, we have that ところで Lemma 2.3、それがあります。 0.61
and thus that Vol((K ∩ H) + rB) ≤ だからこそ Vol((K, H) + rB) ≤ 0.66
2rd width(K; vt) · Vol(K + rB), 第2回 幅(K; vt) · Vol(K + rB) 0.57
10dd(cid:19)(cid:18) 1 + In particular, if we choose r ≤ width(K; vt)/(100dd+1), then 1 10dd(cid:19)(cid:18) 1 + 特に r ≤ width(k; vt)/(100dd+1) を選ぶと 1 になる。 0.86
Vol(K + + rB) ≤(cid:18)1 − Vol(K + + rB) ≤(cid:18)1 − 0.91
1 2dr width(K; vt)(cid:19) Vol(K + rB) 1 2dr 幅(K; vt)(cid:19)Vol(K + rB) 0.84
Vol(K + + rB) ≤(cid:18)1 − Vol(K + + rB) ≤(cid:18)1 − 0.91
20dd(cid:19) Vol(K + rB). 20dd(cid:19) Vol(K + rB)。 0.89
The analysis now proceeds as follows. 分析は次のとおりである。 0.68
In each round, let r = 2⌊lg(width(K;vt)/100dd+1)⌋ be the largest power 各ラウンドにおいて、r = 2 lg(width(k;vt)/100dd+1) を最大のパワーとする 0.79
of 2 smaller than w/(100dd+1). w/(100dd+1)より小さい2。 0.77
Any specific r can occur in at most 任意の特定の r が存在しうる 0.69
log(Vol(K0 + rB)/Vol(KT + rB)) log(Vol(K0 + rB)/Vol(KT + rB)) 0.96
rounds. This in turn is at most ラウンドだ これはおまけに 0.42
log(cid:0)1 − 1 20dd(cid:1) ≤ 20dd+1 log(2/r) log(cid:0)1 − 1 20dd(cid:1) ≤ 20dd+1 log(2/r) 0.76
log(Vol(2B)/Vol(rB)) log(Vol(2B)/Vol(rB)) 0.99
1/(20dd) rounds, and in each such round the regret that round is at most width(K; vt) ≤ 200dd+1r. 1/(20dd) ラウンドは各ラウンドにおいて、ラウンドが最大幅 (K; vt) ≤ 200dd+1r であることを後悔する。 0.74
The total regret from such rounds is therefore at most それゆえ このラウンドの 総後悔は せいぜい 0.53
Now, by our discretization, r is a power of two less than 1. さて、この離散化により、r は 1 未満の 2 の力である。 0.71
Note that P∞ O(cid:0)P∞ i=0 2−ii(cid:1) = O(1). p∞ o(cid:0)p∞ i=0 2−ii(cid:1) = o(1) に注意。 0.73
It follows that the total regret over all rounds is at most O(d2(d+1)) = exp(O(d log d)), すべてのラウンドに対する後悔の総数は、o(d2(d+1)) = exp(o(d log d)) である。 0.78
i=0 2−i log(2/2−i) = i=02−i log(2/2−i) = 0.62
as desired. 20dd+1 log(2/r) · 200dd+1r = O(d2(d+1)r log(2/r)). 望み通りだ 20dd+1 log(2/r) · 200dd+1r = O(d2(d+1)r log(2/r))。 0.53
The remaining algorithms we study will generally query the center-of-gravity of some convex set, as opposed to the center of the John ellipsoid. 私たちが研究した残りのアルゴリズムは、ジョン・エリプソイドの中心とは対照的に、一般に凸集合の重心を照会します。 0.71
This leads to the following natural question: what is the regret of the cutting-plane algorithm which always queries the center-of-gravity of Kt? カットプレーンアルゴリズムが常にKtの中心を問うことを後悔しているのは何だろうか?
訳抜け防止モード: これは以下の自然問題に繋がる: 切断平面アルゴリズムの後悔とは何か? 常にKtの中心、つまり重力を問うのか?
Kannan, Lovasz, and Simonovits (Theorem 4.1 of [13]) show that it is possible to choose an ellipsoid E satisfying E ⊆ K ⊆ dE such that E is centered at cg(K), so our proof of Theorem 4.2 shows that this algorithm is also an exp(O(d log d)) algorithm. Kannan, Lovasz, Simonovits ([13] の Theorem 4.1) は、E が cg(K) 中心となるような楕円体 E を満足する楕円体 E を選択することが可能であることを示し、このアルゴリズムは exp(O(d log d)) アルゴリズムでもあることを示す。
訳抜け防止モード: Kannan, Lovasz, Simonovits ([13 ] の Theorem 4.1 ) は、それが可能であることを示す。 E を cg(K ) 中心とする E を満足する楕円体 E を選択する したがって、Theorem 4.2の証明は、このアルゴリズムがexp(O(d log d ) ) アルゴリズムでもあることを示している。
However, for both this algorithm and the ellipsoid algorithm しかし、このアルゴリズムと楕円体アルゴリズムの両方について 0.76
11 11 0.85
of Theorem 4.2, we have no non-trivial lower bound on the regret. Theorem 4.2 では、後悔に対する非自明な下限は存在しない。 0.70
It is an interesting open question to understand what regret these algorithms actually obtain (for example, do either of these algorithms achieve poly(d) regret? これらのアルゴリズムが実際に何を得るのかを理解するのは、興味深い質問である(例えば、どちらのアルゴリズムもpoly(d)を後悔しているか? 0.70
). 4.2 An O(d log T )-regret cutting-plane algorithm ). 4.2 O(d log T )-regretcut-planeアルゴリズム 0.89
We will now show how to obtain an O(d log T )-regret cutting plane algorithm. 本稿では,o(d log t )-regret cutting planeアルゴリズムの取得法を示す。 0.70
Our algorithm will simply query the center-of-gravity of Kt + 1 T B each round. 我々のアルゴリズムは、各ラウンド毎のKt + 1 T Bの重心を求める。 0.75
The advantage of doing this is that we will only need to examine one scale of the contextual search potential (namely the value of Vol(Kt + 1 T B)). これを行う利点は、文脈探索ポテンシャルの1つのスケール(すなわち Vol(Kt + 1 T B) の値)のみを調べることである。 0.63
The following geometric lemma shows that, as long as the width of the Kt is long enough, this potential decreases by a constant fraction each step. 以下の幾何学的補題は、Kt の幅が十分長い限り、このポテンシャルは各ステップごとに一定の割合で減少することを示している。 0.73
Lemma 4.3. Given K ∈ Convd, u ∈ Sd−1 and b, r ∈ R (with r ≥ 0), let: 補題は4.3。 K ∈ Convd が与えられたとき、u ∈ Sd−1 と b, r ∈ R (r ≥ 0) は、 0.68
• c = cg(K + rB) be the center-of-gravity of K + rB, • H +(b) = {hu, x − ci ≥ −b} be a half-space induced by a hyperplane in the direction u passing within • c = cg(k + rb) は k + rb の重心、• h +(b) = {hu, x − ci ≥ −b} は u の方向の超平面によって誘導される半空間である。
訳抜け防止モード: • c = cg(K + rB ) は K + rB の中心である。 • H + ( b ) = { hu, x − ci ≥ −b 半空間で、超平面によって誘導される方向 u の内側を通る方向
distance b of the point c, and • K + = K ∩ H +(b) be the intersection of K with this half-space. 点cの距離b,及び • K + = K , H +(b) はこの半空間との K の交叉である。 0.74
If r,|b| ≤ width(K, u)/(16ed) then r,|b| ≤ width(k, u)/(16ed) ならば 0.85
Vol(K + + rB) ≤ 0.9 · Vol(K + rB). Vol(K + + rB) ≤ 0.9 · Vol(K + rB)。 0.90
Proof. Observe that K ++rB ⊆ (K +rB)∩H +(b+r). 証明。 K ++rB は (K +rB) = H +(b+r) である。 0.62
If we define H −(b+r) = {x ∈ Rd;hu, x−ci ≤ −(b+r)} then: H −(b+r) = {x ∈ Rd;hu, x−ci ≤ −(b+r)} とすると、 0.89
By Theorem 2.1 (Approximate Grunbaum) we have: Theorem 2.1 (Approximate Grunbaum) 0.59
Vol(K + + rB) ≥ Vol(K + rB) − Vol((K + rB) ∩ H −(b + r)). Vol(K + + rB) ≥ Vol(K + rB) − Vol((K + rB) ) H −(b + r) である。 0.82
Vol((K + rB) ∩ H −(b + r)) vol((k + rb) ] h −(b + r))) である。 0.67
Vol(K + rB) Vol(K + rB) 0.85
1 e − 2(d + 1) width(K; u) · 1 e − 2(d + 1) 幅(K; u) · 0.83
≥ 2width(K, u) ≥ 2width (k, u) 0.90
16ed 1 2e ≥ 0.1 16 1 2e ≥ 0.1 0.74
≥ We can now prove that the above algorithm achieves O(d log T ) regret. ≥ 上記のアルゴリズムが O(d log T ) の後悔を達成することを証明できる。 0.80
Theorem 4.4. The cutting-plane algorithm which queries the point pt = cg(cid:0)Kt + 1 定理4.4。 点 pt = cg(cid:0)Kt + 1 を問う切削平面アルゴリズム 0.69
regret. T B(cid:1) incurs O(d log T ) 後悔してる T B(cid:1) は O(d log T ) 0.78
Proof. We will begin by showing that if we incur more than 50d/T regret in a given round, we reduce the value of Vol(Kt + 1 T B), this will allow us to bound the number of times we incur a large amount of regret. 証明。 私たちはまず、あるラウンドにおいて50d/t以上の後悔を負い、vol(kt + 1 t b)の値を減少させるならば、大量の後悔を負う回数を制限できることを示すことから始めます。 0.66
T B) by a constant factor. T) が一定値を示した。 0.64
Since Vol(Kt + 1 Vol(Kt + 1)から 0.84
T B) is bounded below by Vol( 1 T B) は Vol( 1) によって下界される 0.74
Consider a fixed round t of this algorithm. このアルゴリズムの固定円tを考える。 0.66
Let Kt be the knowledge set at time t. When we query the T B), we obtain a half-space H + = {w ∈ Rd;hw − p, vti ≥ 0} passing The regret in round t is bounded by width(Kt, vt). 時間 t において kt を知識集合とする: t b を問うとき、半空間 h + = {w ∈ rd;hw − p, vti ≥ 0} を得る。
訳抜け防止モード: kt を時間 t における知識集合とする。 半空間 h + = { w ∈ rd;hw − p を得る。 ラウンド t で後悔を渡す vti ≥ 0 } は、幅(kt, vt ) で区切られる。
If the width is at least 50d/T we can then apply 幅が少なくとも50d/Tであれば、適用できます 0.73
separation-oracle point pt = cg(K + 1 through pt which contains w∗. 分離-oracle point pt = cg(k + 1 から pt へ、w∗ を含む。 0.79
We update Kt+1 = Kt ∩ H + Lemma 4.3 with b = 0 and r = 1/T to conclude that: Kt+1 = Kt > H + Lemma 4.3 を b = 0 と r = 1/T で更新する。 0.88
Vol(cid:18)Kt+1 + B(cid:19) ≤(cid:18)1 − Vol(cid:18)Kt+1 + B(cid:19) ≤(cid:18)1 − 0.83
1 e 1 T B(cid:19) ≤ 0.9 · Vol(cid:18)Kt + + 0.2(cid:19) Vol(cid:18)K + 1 e 1T B(cid:19) ≤ 0.9 · Vol(cid:18)Kt + + 0.2(cid:19) Vol(cid:18)K + 0.80
1 T 1 T B(cid:19) . 1T 1T b(cid:19) である。 0.71
(7) B(cid:19) < 0.9 · Vol(cid:18)K + (7) B(cid:19) < 0.9 · Vol(cid:18)K + 0.84
1 T B(cid:19) . 1T b(cid:19) である。 0.69
Vol(cid:18)K + + Vol(cid:18)K + + 0.94
1 T 12 1T 12 0.81
Now, in each round where width(Kt, vt) < 50d/T , we incur at most 50d/T regret, so in total we incur at most T · (50d/T ) = 50d regret from such rounds. 現在、各ラウンドで幅(Kt, vt) < 50d/T となると、少なくとも 50d/T の後悔が生じるので、このラウンドから少なくとも T · (50d/T ) = 50d の後悔が生じる。 0.73
On the other hand, in other rounds we may incur up to kw∗ − ptk ≤ 2 regret per round. 一方、他のラウンドでは、1ラウンドあたり kw∗ − ptk ≤ 2 の後悔が生じることがある。 0.70
However, note that Vol(K1 + 1 T )B) ≤ 2dVol(B), whereas for any t, Vol(Kt + 1 T B) = T −dκd. ただし、Vol(K1 + 1 T )B) ≤ 2dVol(B) は任意の t に対して Vol(Kt + 1 T B) = T −dκd である。 0.85
Since in each such round we shrink this quantity by at least a factor of 0.9, it follows that the total number of such rounds is at most O(log(2T d)) = O(d log T ). 各ラウンドにおいて、少なくとも 0.9 の係数でこの数を縮小するため、これらのラウンドの総数は、O(log(2T d)) = O(d log T ) である。 0.74
It follows that the total regret from such rounds is at most O(d log T ), and thus the overall regret of this algorithm is at most O(d log T ). このようなラウンドからの後悔の総数は o(d log t ) 以上であり、したがってこのアルゴリズム全体の後悔は o(d log t ) 以上である。 0.73
T B) = Vol((1 + 1 T B) = Vol((1 + 1) 0.89
T B) ≥ Vol( 1 T B) ≥ Vol( 1) 0.92
5 List contextual recommendation, weak separation oracles, and 5 コンテキストレコメンデーションの一覧、分離の弱さ、及び 0.69
the curvature path In this section, we present two algorithms: 1. a poly(d) expected regret cutting-plane algorithm for weak separation oracles, and 2. an O(d2 log d) regret algorithm for list contextual recommendation with list size L = poly(d). 曲がりくねった道 本稿では,(1) 弱分離オラクルに対するポリ(d) 既約切削平面アルゴリズム,(2) リストサイズL=ポリ(d) によるリストのコンテキストレコメンデーションのためのO(d2 log d) 後悔アルゴリズムの2つのアルゴリズムを提案する。 0.70
The unifying feature of both algorithms is that they both involve analyzing a geometric object we call the curvature path of a convex body. 両アルゴリズムの統一的な特徴は、どちらも凸体の曲率経路と呼ばれる幾何学的対象を分析することである。 0.79
The curvature path of K is a bounded-degree rational curve contained within K that connects the center-of-gravity cg(K) with the Steiner point (limr→∞ cg(K + rB)) of K. In Section 5.1 we formally define the curvature path and demonstrate how to bound its length. K の曲率経路は、K の中心重力 cg(K) と K のスタイナー点 (limr→∞ cg(K + rB)) を接続する K に含まれる有界な有理曲線である。
訳抜け防止モード: K の曲率経路は、K の中心 cg(K ) と K のスタイナー点 (limr→∞ cg(K + rB ) を連結する K に含まれる有界次数有理曲線である。 どのように長さを束縛するかを 示しています
In Section 5.2, we show that randomly querying a point on a discretization of the curvature path leads to a poly(d) regret cutting-plane algorithm for weak separation oracles. 第5.2節では、曲率経路の離散化上の点をランダムに問合せすることで、弱い分離神託に対するポリ(d)後悔の切削平面アルゴリズムが導かれることを示す。 0.70
Finally, in Section 5.1, we show how to transform a discretization of the curvature path of the knowledge set into a list of actions for list contextual recommendation, obtaining a low regret algorithm. 最後に,第5.1節では,知識集合の曲率経路の離散化を,文脈的推薦をリスト化するための行動リストに変換する方法を示す。
訳抜け防止モード: 最後に,第5.1節では,知識集合の曲率経路の離散化を,文脈推薦リストのアクションリストに変換する方法について述べる。 後悔の少ないアルゴリズムが得られます
5.1 The curvature path An important fact (driving some of the recent results in contextual search, e g volume Vol(K + rB) is a d-dimensional polynomial in r. This fact is known as the Steiner formula: 5.1 曲率経路 文脈探索における最近の結果のいくつかを導いた重要な事実、e g volume Vol(K + rB) は r の d-次元多項式である。 0.76
[16]) is the fact that the Vol(K + rB) = [16])は Vol(K + rB) = 0.58
d Xi=0 Vd−i(K)κiri d Xi=0 Vd−i(K)κiri 0.74
(8) After normalization by the volume of the unit ball, the coefficients of this polynomial correspond to the : Convd → R+ for intrinsic volumes of K. The intrinsic volumes are a family of d + 1 functionals Vi i = 0, 1, . (8) 単位球の体積による正規化の後、この多項式の係数は、K の固有体積に対する Convd → R+ に対応する。
訳抜け防止モード: (8) 単位球の体積による正規化の後、この多項式の係数は、K の固有体積に対する Convd → R+ に対応する。 1 , .
. . , d that associate for each convex K ∈ Convd a non-negative value. . . , d は各凸 K ∈ Convd に対して非負の値である。 0.81
Some of these functionals have natural interpretations: Vd(K) is the standard volume Vol(K), Vd−1(K) is the surface area, V1(K) is the average width and V0(K) is 1 whenever K is non-empty and 0 otherwise. Vd(K) は標準体積 Vol(K) であり、Vd−1(K) は表面積、V1(K) は平均幅、V0(K) は K が空でなければ 1 である。
訳抜け防止モード: これらの函数のいくつかは自然な解釈を持ち、Vd(K) は標準体積 Vol(K) である。 Vd−1(K)は表面積、V1(K)は平均幅である K が空でないとき V0(K ) は 1 である 0。
There is an analogue of the Steiner formula for the centroid of K +rB, showing that it admits a description as a vector-valued rational function. K +rB のセントロイドに対するシュタイナーの公式の類似式があり、ベクトル値の有理関数として記述されていることを示す。 0.71
More precisely, there exist d + 1 functions ci : Convd → Rd for 0 ≤ i ≤ d such that: より正確には、0 ≤ i ≤ d に対して d + 1 個の函数 ci : Convd → Rd が存在する。 0.86
(9) cg(K + rB) = Pd (9) cg(K + rB) = Pd 0.85
i=0 Vd−i(K)κiri · ci(K) Pd i=0 Vd−i(K)κiri · ci(K) Pd 0.85
i=0 Vd−i(K)κiri i=0 Vd−i(K)κiri 0.69
The point c0(K) ∈ K corresponds to the usual centroid cg(K) and cd(K) corresponds to the Steiner point. 点 c0(K) ∈ K は通常のセントロイド cg(K) に対応し、cd(K) はスタイナー点に対応する。 0.70
The functionals ci are called curvature centroids since they can be computing by integrating a certain curvature measures associated with a convex body (a la Gauss-Bonnet). 関数ciは、凸体(ラ・ガウス・ボネット)に関連する特定の曲率測度を積分して計算できるので、曲率中心(curvature centroids)と呼ばれる。 0.73
We refer to Section 5.4 in Schneider [21] for a more thorough discussion discussion. より詳細な議論についてはschneider [21]の5.4節を参照してください。 0.66
For our purposes, however, the only important fact will be that each curvature centroid ci(K) is guaranteed to lie within K (note that this is not at all obvious from their definition). しかしながら、我々の目的のために、唯一の重要な事実は、各曲率中心体 ci(K) が K 内にあることが保証されていることである(これは定義からは全く明らかではないことに注意)。 0.71
Motivated by this, given a convex body K ⊆ Rd we define its curvature path to be the following curve in このことが動機となり、凸体 K > Rd が与えられたとき、曲率経路を次の曲線と定義する。 0.65
Rd: ρK : [0,∞] → K Rd: ρK : [0,∞] → K 0.81
ρK(r) = cg(K + rB) ρK(r) = cg(K + rB) 0.92
13 13 0.85
The path connects the centroid ρK(0) = cg(K) to the Steiner point ρK(∞). この経路はセントロイド ρK(0) = cg(K) をシュタイナー点 ρK(∞) に接続する。 0.77
Our main result will exploit the fact that the coordinates of the curvature path are rational functions of bounded degree to produce a discretization. 我々の主な結果は、曲率経路の座標が有界次数の有理関数であるという事実を利用して離散化を生成する。 0.72
We start by bounding the length of the path. 経路の長さの制限から始めます。 0.59
For reasons that will become clear, it will be more convenient to bound its length when transformed by the linear map in John’s Theorem. 明らかになる理由から、ジョンの定理の線型写像によって変換された場合、その長さを束縛することがより便利になる。 0.74
Lemma 5.1. Let K ∈ Convd \ {∅}, and let A be a linear transformation as in (John’s) Theorem 2.2. 通称5.1。 K ∈ Convd \ {a} とし、A を (John's) Theorem 2.2 のように線型変換とする。 0.67
Then the length of the path {AρK(r); r ∈ [0,∞]} is at most 4d3. このとき、経路 {AρK(r); r ∈ [0,∞]} の長さは、少なくとも 4d3 である。 0.86
Proof. The length of a path is the integral of the ℓ2-norm of its derivative. 証明。 経路の長さは、その微分の l2-ノルムの積分である。 0.69
We will bound the ℓ2 norm by the ℓ1 norm and then analyze each of its components. l2 のノルムを l1 のノルムで制限し、各成分を分析する。 0.44
length(AρK ) =Z ∞ length(AρK ) =Z ∞ 0.82
kAρ′ K(r))i is the i-th component of the vector Aρ′ kaρ′ k(r))i はベクトル aρ′ の第 i 成分である。 0.78
K(r)k2dr ≤Z ∞ K(r)k2dr ≤Z ∞ 0.86
kAρ′ 0 0 K(r)k1dr = kAρ 0 0 K(r)k1dr = 0.82
d Xi=1Z ∞ 0 d Xi=1Z ∞ 0 0.76
|(Aρ′ K (r))i|dr |(Aρ) K (r)i|dr 0.81
(10) where (Aρ′ K (r). (10) ここで (Aρ′ K (r)。 0.78
By equation (9), we know that there are degree-d polynomials p(r) and q(r) such that (Aρ′ K(r))i = p(r)/q(r) where q(r) > 0 for all r ≥ 0. 方程式 (9) により、すべての r ≥ 0 に対して (aρ′ k(r))i = p(r)/q(r) となる次数 d 多項式 p(r) と q(r) が存在することが分かる。 0.82
Hence we K (r))i = (p′(r)q(r)− p(r)q′(r))/(q(r)2) which can be re-written as h(r)/q(r)2 can write its derivative as: (Aρ′ for a polynomial h(r) of degree at most 2d − 1. したがって、 h(r)/q(r)2 と書き換えることができる K (r))i = (p′(r)q(r)− p(r)q′(r))/(q(r)2) は、次数 2d − 1 の次数の多項式 h(r) に対して、その微分を次のように書くことができる。 0.92
Now a polynomial of degree at most k can change signs at most k times. 次数多項式の最大 k は、符号を最大 k 回変更することができる。 0.65
So we can partition [0,∞] into at most 2d intervals I1, . したがって、[0,∞] を少なくとも 2d 区間 I1, に分割できる。 0.72
. . , I2d (some possibly empty) such that the sign of (Aρ′ K (r))i is the same within each region (treating zeros arbitrarily). . . Aρ′ K (r))i の符号が各領域で同じであるような I2d (いくつかは空であるかもしれない)。
訳抜け防止モード: . . ,I2d(おそらく空である) Aρ′ K ( r))i の符号は各領域において同じである(零点を任意に扱う)。
If Ij = [aj, bj], we can then write: Ij = [aj, bj] なら、次のように書ける。 0.72
Z ∞ 0 |(Aρ′ Z ∞ 0 |(Aρ) 0.80
K (r))i|dr = K(r))i|dr = 0.88
2d Xj=1Z bj 2d xj=1zbj 0.70
aj |(Aρ′ K(r))i| = aj |(Aρ) K(r))i| = 0.84
2d Xi=1 |(AρK (bj))i − (AρK (aj))i| ≤ 4d2 2d Xi=1 |(AρK (bj))i −(AρK (aj))i| ≤ 4d2 0.74
(11) where the last step follows from John’s theorem. (11) 最後のステップは、Johnの定理から導かれる。 0.76
Since A(ρK ) is in A(K) which is contained in a ball of radius d, the distance between the i-coordinate of two points is at most 2d. A(ρK ) は半径 d の球体に含まれる A(K) に属するため、二つの点の i-座標間の距離は最大 2d である。 0.84
Equations (10) and (11) together imply the statement of the lemma. 方程式 (10) と (11) はともに補題のステートメントを意味する。 0.85
Lemma 5.2. Given K ∈ Convd and a discretization parameter k, there exists a set D = {p0, p1, . 補題5.2。 K ∈ Convd と離散化パラメータ k が与えられたとき、集合 D = {p0, p1, が存在する。 0.62
. . , pk} ⊂ K such that for every r there is a point pi ∈ D such that: . . すべての r に対して点 pi ∈ D が存在して、次のようになる。 0.76
|hρK(r) − pi, ui| ≤ hρk(r) − pi, ui| ≤ 0.85
4d3 k · width(K, u), ∀u ∈ Sd−1. 4d3 k · width(K, u) は、u ∈ Sd−1 である。 0.75
Proof. Discretize the path Aρk into k pieces of equal length and let Ap0, Ap1, . 証明。 経路 Aρk を等しい長さの k 個の部分に分解し、Ap0, Ap1, とする。 0.58
. . , Apk correspond to the endpoints. . . , Apk はエンドポイントに対応する。 0.82
Let D = {p0, p1, . D = {p0, p1, とする。 0.74
. . , pk}. . . pk である。 0.75
We know by Lemma 5.1 that for any p = ρK(r), there exists a pi ∈ D such that: kApi − Apk2 ≤ 4d3/k. Lemma 5.1 は、任意の p = ρK(r) に対して pi ∈ D が存在して、kApi − Apk2 ≤ 4d3/k となることを知っている。 0.74
Now, for each unit vector u ∈ Sd−1, we have: さて、各単位ベクトル u ∈ Sd−1 に対して、 0.73
|hu, pi − pi| ≤ hA−T u, A(pi − p)i ≤ kA−T uk · kA(pi − p)k ≤ kA−T uk · 4d3/k |hu, pi − pi| ≤ hA−T u, A(pi − p)i ≤ kA−T uk · kA(pi − p)k ≤ kA−T uk · 4d3/k 0.86
Finally, we argue that kA−T uk ≤ width(K; u). 最後に、kA−T uk ≤ width (K; u) を議論する。 0.84
Let v = (A−T u)/kA−T uk and take x, y ∈ K that certify v = (a−t u)/ka−t uk and take x, y ∈ k that certify 0.86
the width of K in direction u: 方向 u における k の幅 0.72
width(K, u) = hu, x − yi = hA−T u, Ax − Ayi = kA−T uk · hv, Ax − Ayi 幅(K, u) = hu, x − yi = hA−T u, Ax − Ayi = kA−T uk · hv, Ax − Ayi 0.96
Finally note that Ax and Ay are respectively the maximizer and minimizer of hv, zi for z ∈ A(K) since: maxz∈A(K)hv, zi = maxx∈Khv, Axi = maxx∈KhAT v, xi = maxx∈Khu, xi/kA−T uk. 最後に、Ax と Ay はそれぞれ hv, zi for z ∈ A(K) の最大値および最小値であることに注意する: maxz・A(K)hv, zi = maxx・Khv, Axi = maxx・KhAT v, xi = maxx・Khu, xi/kA−T uk。 0.76
This implies that hv, Ax − Ayi = width(A(K), v) ≥ 1 by John’s Theorem since q + B ⊆ A(K). これは、hv, ax − ayi = width(a(k), v) ≥ 1 がジョンの定理により q + b から a(k) となることを意味する。 0.84
This completes the proof. これが証明を完了します。 0.61
14 14 0.85
5.2 Low-regret cutting-plane algorithms for weak separation oracles 5.2 弱分離オラクルのための低反射切削平面アルゴリズム 0.58
In this section we show how to use the discretization of the curvature path in Lemma 5.2 to construct a poly(d)-regret cutting-plane algorithm that works against a weak separation oracle. 本稿では、Lemma 5.2における曲率経路の離散化を用いて、弱い分離オラクルに対して作用するポリ(d)-レグレット切断平面アルゴリズムを構築する方法について述べる。 0.76
Recall that a weak separation oracle is a separation oracle that fixes the direction of the output hyperplane in advance (up to sign). 弱い分離オラクルは、(符号まで)出力されたハイパープレーンの方向を事前に修正する分離オラクルである。 0.62
That is, at the beginning of round t the oracle fixes some direction vt ∈ Sd−1 and returns either vt or −vt to the learner depending on the learner’s choice of query point qt. つまり、円tの先頭で、オラクルは何らかの方向 vt ∈ Sd−1 を修正し、学習者のクエリポイント qt の選択に応じて vt または −vt を学習者に返す。 0.81
One advantage of working with a weak separation oracle is that the width width(Kt; vt) of the knowledge set in the direction vt is fixed and independent of the query point pt of the learner. 弱い分離オラクルで作業する利点の1つは、方向vtに設定された知識の幅幅(Kt; vt)が学習者のクエリポイントptから独立していることである。 0.72
This means that if we can guess the width, we can run essentially the standard contextual search algorithm (of Section 2.2) by querying any point pt that lies on the hyperplane which decreases the potential corresponding to this width by a constant factor. つまり、幅を推測できるなら、その幅に対応する電位を定数係数で減少させる超平面上の任意の点 pt に問い合わせることで、基本的に標準的な文脈探索アルゴリズム(セクション2.2)を実行することができる。 0.79
One good way to guess the width turns out to choose a random point belonging to a suitably fine discretization of the curvature path. 幅を推測する良い方法の1つは、曲率経路の微妙な判別に属するランダムな点を選択することである。 0.82
Theorem 5.3. The cutting-plane algorithm which chooses a random point from the discretization of the curvature path of Kt into d4 pieces achieves a total regret of O(d5 log2 d) against any weak separation oracle. 理論5.3。 Ktの曲率経路をd4に離散化してランダム点を選択する切削平面アルゴリズムは、任意の弱い分離オラクルに対してO(d5 log2 d)を完全に後悔する。 0.68
Proof. Consider a fixed round t. Let vt be the direction fixed by the weak separation-oracle and let ω = width(Kt; vt). 証明。 固定円 t を考える。 vt を弱分離軌道によって固定された方向とし、ω = 幅 (Kt; vt) とする。 0.68
Let r = 2⌈lg(ω/16ed)⌉ (rounding ω/16ed to the nearest power of two). r = 2\lg(ω/16ed) とする(ω/16ed を 2 の最も近いパワーに囲む)。 0.64
If we could choose the point pt = ρKt(r) = cg(Kt + rB), then by Lemma 4.3, any separating hyperplane through pt would decrease this potential by a constant factor. pt = ρkt(r) = cg(kt + rb) を選ぶことができるなら、補題 4.3 により、pt を通る任意の分離超平面は、このポテンシャルを定数係数で減少させる。 0.70
However, we do not know r. Instead, we will choose a random point from the discretization D of the curvature path of Kt into O(d4) pieces, and argue that by Lemma 5.2 one of these points will be close enough to ρKt(r) to make the argument go through. しかし、r は分かっていない。代わりに、Kt の曲率経路の離散化 D から O(d4) の部分へのランダムな点を選び、Lemma 5.2 によってこれらの点のうちの 1 つは ρKt(r) に十分近いので議論を通すことができると論じる。 0.75
Formally, let D be the discretization of ρKt into 64ed4 pieces as per Lemma 5.2. 正式には、D を ρKt を Lemma 5.2 のように 64ed4 に離散化する。 0.69
By Lemma 5.2, there Lemma 5.2 による。 0.76
then exists a point pi ∈ D that satisfies そして、満足する点 pi ∈ D が存在する 0.86
|hρK(r) − pi, vti| ≤ hρk(r) − pi, vti| ≤ 0.85
1 16ed · width(Kt; vt). 1 16ed · width (Kt; vt)。 0.88
(12) Let H be a hyperplane through pi in the direction vt (i.e. (12) H を pi の方向 vt (すなわち) を通して超平面とする。 0.85
H = {hw − pi, vti = 0}), and let H divide Kt into the two regions K + and K −. H = {hw − pi, vti = 0}) とし、H を 2つの領域 K + と K − に分割する。 0.84
By Lemma 4.3 (with b = hρK(r) − pi, vti), since (12) holds, we have that (13) Now, consider the algorithm which queries a random point in D. With probability 1/|D| = Ω(d−4), equation (13) holds. 補題 4.3 (b = hρk(r) − pi, vti) によって、(12) が成り立つので、(13) が d のランダム点をクエリするアルゴリズムを考えると、確率 1/|d| = ω(d−4) で方程式 (13) が成り立つ。 0.81
Otherwise, it is still true that Vol(K + + rB) ≤ ·Vol(K + rB). さもなくば、Vol(K + + rB) ≤ ·Vol(K + rB) が成り立つ。 0.70
Therefore in expectation, Vol(K + + rB) ≤ 0.9 · Vol(K + rB). だから 期待して Vol(K + + rB) ≤ 0.9 · Vol(K + rB)。 0.82
E[Vol(Kt+1 + rB)] ≤(cid:0)1 − Ω(d−4)(cid:1) E[Vol(Kt + rB)]. E[Vol(Kt+1 + rB)] ≤(cid:0)1 − Ω(d−4)(cid:1) E[Vol(Kt + rB)]。 0.93
In particular, the total expected number of rounds we can have where r = 2−i is at most di/ log(1/(1 − Ω(d−4))) = O(id5). 特に、r = 2−i が高々 di/ log(1/(1 − Ω(d−4))) = O(id5) となるようなラウンドの総数が得られる。 0.86
In such a round, our maximum possible loss is at most width(Kt; vt) ≤ min(20dr, 2). そのようなラウンドにおいて、最大損失は最大幅(kt; vt) ≤ min(20dr, 2)である。 0.74
Summing over all i from 0 to ∞, we arrive at a total regret bound of Xi=log d すべての i を 0 から ∞ に総和すると、xi=log d の完全後悔境界に達する。 0.79
O(i2−i) = O(d5 log2 d). O(i2−i) = O(d5 log2 d)。 0.82
O(id5 min(d2−i, 1)) = O(id5 min(d2−i, 1)) = 0.88
O(id5) + d6 O(id5) + d6 0.92
∞ Xi=0 log d ∞ Xi=0 log d 0.76
Xi=0 ∞ 5.3 List contextual recommendation Xi=0 ∞ 5.3 リストコンテキストレコメンデーション 0.72
In this section, we consider the problem of list contextual recommendation. 本稿では,リストのコンテキストレコメンデーションの問題について考察する。 0.64
In this variant of contextual recommendation, we are allowed to offer a list of possible actions Lt ⊆ Xt and we measure regret against the best action in the list: このタイプのコンテキストレコメンデーションでは、可能なアクションのリストを提供することができ、リスト内の最善のアクションに対して後悔を計測します。 0.55
losst = hw∗, x∗ losst = hw∗, x∗ 0.99
ti − max x∈Lthw∗, xi. ti − マックス x-Lthw∗, xi。 0.67
15 15 0.85
Our main result is that if the list is allowed to be of size O(d4) then it is possible to achieve total regret O(d2 log d). 我々の主な結果は、リストがサイズ O(d4) であれば、完全な後悔 O(d2 log d) を達成することができるということである。 0.85
The recommended list of actions will be computed as follows: given the knowledge set Kt, let D be the discretization of the curvature path with parameter k = 200d4 obtained in Lemma 5.2. 推奨される行動のリストは次のように計算される: 知識集合 Kt が与えられたとき、D をパラメータ k = 200d4 を Lemma 5.2 で得られる曲率経路の離散化とする。 0.80
Then for each pi ∈ D find an arbitrary xi ∈ BR(pi) := arg maxx∈Xthpi, xi and let Lt = {x1, x2, . このとき、各 pi ∈ D に対して任意の xi ∈ BR(pi) := arg maxx⋅Xthpi, xi を求め、 Lt = {x1, x2, とする。 0.81
. . , xk}. . . xk} である。 0.82
Theorem 5.4. There exists an algorithm which plays the list Lt defined above and incurs a total regret of at most O(d2 log d). 理論5.4。 上述したリスト Lt を再生し、ほとんどの O(d2 log d) の完全後悔を引き起こすアルゴリズムが存在する。 0.66
Proof. The overall structure of the proof will be as follows: we will show that for each integer j ≥ 0, the algorithm can incur loss between 100d · 2−j and 200d · 2−j at most O(jd) times. 証明。 証明の全体構造は次のようになる: 各整数 j ≥ 0 に対して、アルゴリズムは100d · 2−j と 200d · 2−j の間の損失を、多くの o(jd) 時間に発生させることができる。 0.72
Hence the total loss of the algorithm can be bounded by P∞ したがって、アルゴリズムの全損失は p∞ で区切ることができる。 0.73
Potential function: This will be done via a potential function argument. ポテンシャル関数: これは潜在的な関数引数を通じて行われる。 0.85
As usual, we will keep track of knowledge Kt which corresponds to all possible values of w that are consistent with the observations seen so far. 通常のように、これまでに見てきた観測値と一致するすべての w の値に対応する知識 Kt の追跡を続ける。 0.74
K1 = B and: j=1 O(jd) · 2−jd ≤ O(d2 log d). K1 = B と: j = 1 O(jd) · 2−jd ≤ O(d2 log d)。 0.91
Associated with Kt we will keep track of a family of potential functions: ktに関連して、私たちは潜在的な機能のファミリーを追跡します。 0.63
Kt+1 = Kt ∩(cid:2)∩i∈Lt{w ∈ Rd;hx∗ − x, wi ≥ 0}(cid:3) Kt+1 = Kt >(cid:2)\\|Lt{w ∈ Rd;hx∗ − x, wi ≥ 0}(cid:3) 0.82
Φj t = Vol(Kt + 2−jB) シュイ t = Vol(Kt + 2−jB) 0.76
Since K1 ⊇ K2 ⊇ K3 ⊇ ... the potentials will be non-increasing: Φj property is that the potential functions are lower bounded: k1 {\displaystyle k2} は k3 {\displaystyle k3} であるので、ポテンシャルは増大しない: φj の性質は、ポテンシャル函数が有界でないことである。 0.47
1 ≥ Φj 2 ≥ Φj 1 ≥ .j 2 ≥ .j 0.92
3 ≥ .... One other important 3 ≥ .... もう一つ重要な点 0.61
Φt j ≥ Vol(2−j B) = 2−jdVol(B) t j ≥ Vol(2−j B) = 2−jdVol(B) 0.90
(14) We will argue that if we can bound the loss at any given step t by 200 · 2−jd, then Φj of the lower bound in equation 14, this can happen at most (14) 任意のステップ t における損失を 200 · 2−jd で結ぶことができれば、方程式 14 における下界の yj は、最も多くは起こり得ると論じる。 0.80
t+1 ≤ 0.9 · Φj t+1 ≤ 0.9 · 0.77
t . Because O log T。 なぜなら オログ 0.60
Φ1 j 2−jdVol(B)!! ~1j 2-jdVol(B)! 0.74
= O(cid:18)log(cid:18) (1 + 2−j)dVol(B) = O(cid:18)log(cid:18) (1 + 2−j)dVol(B) 0.89
2−jdVol(B) (cid:19)(cid:19) ≤ O(jd) 2-jdVol(B) (cid:19)(cid:19) ≤ O(jd) 0.79
Bounding the loss: We start by bounding the loss and depending on the loss we will show a constant 損失にバウンドすること: 損失にバウンドすることから始め、損失に応じて定数を示す 0.65
decrease in a corresponding potential function. 対応するポテンシャル関数を減少させます 0.78
Let If x∗ is in the convex hull of Lt then there must some of the points in xi ∈ Lt that is also optimal, in which case the algorithm incurs zero loss in this round and we can ignore it. いくぞ もし x∗ が Lt の凸包であるなら、xi ∈ Lt の点のいくつかは最適でなければならない。
訳抜け防止モード: いくぞ x∗ が Lt の凸包であるなら、xi ∈ Lt の点のいくつかは最適でなければならない。 この場合 アルゴリズムはこのラウンドでゼロの損失を発生させます 無視できます
Otherwise, we can assume that x∗ is not in the convex hull of Lt. さもなくば、x∗ は lt の凸包には存在しないと仮定できる。 0.66
In that case, define for each xi ∈ Lt the vector: この場合、各 xi ∈ Lt に対してベクトルを定義する。 0.82
x∗ ∈ arg max x∗ ∈ arg max 0.98
x∈Xt hw∗, xi xjavaxt hw∗, xi 0.64
vi = x∗ − xi kx∗ − xik2 VI = x∗ − xi kx∗ − xik2 0.69
Consider the index i that minimizes width(K; vi) and use this point to bound the loss: 幅(K; vi)を最小化し、この点を使って損失を束縛する指数 i を考える。 0.81
losst = min losst = min 0.85
x∈Lthw∗, x∗ − xi ≤ hw∗, x∗ − xii ≤ hw∗ − pi, x∗ − xii x ∈lthw∗, x∗ − xi ≤ hw∗, x∗ − xii ≤ hw∗ − pi, x∗ − xii 0.89
= hw∗ − pi, vii · kx∗ − xik ≤ 2hw∗ − pi, vii ≤ 2width(K, vi) = hw∗ − pi, vii · kx∗ − xik ≤ 2hw∗ − pi, vii ≤ 2width(K, vi) 0.97
The second inequality above follows from the definition of xi since xi ∈ arg maxx∈Xthpi, xi it follows that hpi, xi − x∗i ≥ 0. 上の2番目の不等式は xi ∈ arg maxx⋅Xthpi から xi の定義に従っており、xi は hpi, xi − x∗i ≥ 0 である。 0.77
16 16 0.85
Charging the loss to the potential We will now charge this loss to the potential. 損失を潜在的にチャージする 私たちは今、この損失を潜在的にチャージします。 0.62
For that we first define an index j such that: 最初に定義するのは そのような指標jは 0.65
With this definition we have: j = −(cid:24) width(K, vi) この定義では、 j = −(cid:24) 幅(K, vi) 0.73
100d (cid:25) 100d (cid:25) 0.78
Our final step is to show that the potential Φj combination of the discretization in Theorem 5.2 and the volume reduction guarantee in Lemma 4.3. 最後のステップは、Theorem 5.2 における離散化と Lemma 4.3 における体積減少保証との潜在的な sj 結合を示すことである。 0.68
t decreases by a constant factor. tは一定因子によって減少する。 0.70
For that we will use a losst ≤ 2width(K, vi) ≤ 200d2−j そのために私たちは losst ≤ 2width(k, vi) ≤ 200d2−j 0.71
First consider the point: まず ポイントを考えてみましょう 0.55
gi = cg(K + 2−jB) gi = cg(K + 2−jB) 0.96
Since it is on the curvature path, there is a discretized point pℓ ∈ D such that: 曲率経路上にあるので、次のように離散化された点 pl ∈ D が存在する。 0.70
|hvℓ, gi − pℓi| ≤ width(K, vℓ)/(50d) |hvl, gi − pli| ≤ width(K, vl)/(50d) 1.00
Together with the facts that hw∗, vℓi ≥ 0 and hpℓ, vℓi ≤ 0 we obtain that: hw∗, vli ≥ 0 と hpl の事実と合わせて、vli ≤ 0 はそれを得る。 0.72
hw∗ − gi, vℓi = hw∗ − pℓ, vℓi + hpℓ − gi, vℓi ≥ −width(K, vℓ)/(50d) hw∗ − gi, vli = hw∗ − pl, vli + hpl − gi, vli ≥ −width(K, vl)/(50d) 0.97
This in particular implies that: これは特にこう意味している。 0.54
We are now in the position of applying Lemma 4.3 with r = 2−j. 現在、我々は r = 2−j で Lemma 4.3 を適用する立場にある。 0.79
Note that Kt+1 ⊆ ˜Kt+1 := Kt ∩ {w ∈ Rd;hw − gi, vℓi ≥ −width(K, vℓ)/(50d)} 注意 Kt+1 := Kt > {w ∈ Rd;hw − gi, vli ≥ −width(K, vl)/(50d)} 0.65
r = 2−j ≤ width(K, vi) r = 2−j ≤ width (複数形 widths) 0.74
50d ≤ width(K, vℓ) 50d ≤ width (複数形 widths) 0.77
50d where the last inequality follows from the choice of the index i as the one minimizing width(K, vi). 50d 最後の不等式は、インデックス i の選択から、幅(k, vi) を最小化するものとして従う。 0.77
Applying the Theorem, we obtain that: 定理を適用すると、次のようになる。 0.46
which is the desired decrease in the Φj これはjの所望の減少です 0.57
t potential. This concludes the proof. tの可能性がある これが証明となる。 0.61
Vol(Kt+1 + 2−j B) ≤ Vol( ˜Kt+1 + 2−jB) ≤ 0.9 · Vol(Kt + 2−jB) Vol(Kt+1 + 2−jB) ≤ Vol(Kt+1 + 2−jB) ≤ 0.9 · Vol(Kt + 2−jB) 0.80
6 Local Contextual Recommendation 6 ローカルコンテクスト勧告 0.73
In this section, we consider the local contextual recommendation problem, in which we may choose a list , w∗(cid:11) ≥ maxx∈Lt hx, w∗i. この節では、局所文脈レコメンデーション問題を考察し、リスト , w∗(cid:11) ≥ maxx⋅Lt hx, w∗i を選択することができる。 0.63
In other words, of actions Lt ⊆ Xt and our feedback is some xloc the feedback may not be the optimal action but it must at least be as good as the local optimum in Lt. 言い換えれば、Lt > Xt と我々のフィードバックは xloc であり、フィードバックは最適なアクションではないかもしれないが、少なくとも Lt の局所最適値と同程度である必要がある。 0.73
The goal is the same as before: minimize the total expected regret E[Reg] = EhPT t − xt, w∗ii where t ∈ arg maxx∈Xthx, w∗i. E[Reg] = EhPT t − xt, w∗ii ここで t ∈ arg maxx⋅Xthx, w∗i となる。
訳抜け防止モード: 目標は前と同じである: 期待される総後悔e[reg ] = ehpt t − xt を最小にする。 ここで t ∈ arg maxx ∈xthx , w∗i である。
x∗ It should be noted that, in this model, it is impossible to achieve non-trivial regret if the list size |Lt| is only one, since the feedback will always be the unique element, providing no information at all. x∗ このモデルでは、リストのサイズ |Lt| が 1 であるならば、そのフィードバックは常にユニークな要素であり、全く情報を提供しないので、非自明な後悔を達成することは不可能である。 0.69
Below we show that it is possible to achieve bounded regret algorithm even when |Lt| = 2, although the regret does depend on the total number of possible actions each round, i.e. 以下は |Lt| = 2 であっても有界な後悔アルゴリズムが達成可能であることを示すが、その後悔は各ラウンド、すなわち各ラウンドの可能な行動の総数に依存する。 0.71
maxt |Xt|. Furthermore, we show that, even when |Lt| is allowed to be as large as 2Ω(d), the expected regret of any algorithm remains at least 2Ω(d). maxt |Xt| さらに、|Lt| が 2Ω(d) であるとしても、任意のアルゴリズムの期待された後悔は少なくとも 2Ω(d) のままであることを示す。 0.85
such that (cid:10)xloc そのような (cid:10)xloc 0.75
t=1hx∗ t t t=1hx∗ t t 0.70
6.1 Low-regret algorithms We use [a]+ as a shorthand for max{a, 0}. 6.1 低精細アルゴリズム max{a, 0} の略語として [a]+ を用いる。 0.83
Our algorithm employs a reduction similar to that of Theorem 3.1. このアルゴリズムは定理3.1と同様の還元を用いる。 0.75
Specifically, we prove the following: 具体的には、以下のことを証明します。 0.46
17 17 0.85
Theorem 6.1. Suppose that |Xt| ≤ A for all t ∈ N, and let H be any positive integer such that 2 ≤ H ≤ A. 理論6.1。 すべての t ∈ N に対して |Xt| ≤ A とし、H を 2 ≤ H ≤ A となる任意の正の整数とする。 0.72
Then, given a low-regret cutting-plane algorithm A with regret ρ, we can construct an O(ρ· A/(H − 1))-regret algorithm for local contextual recommendation where the list size |Lt| in each step is at most H. したがって、後悔 ρ を持つ低レグレット切断平面アルゴリズム a が与えられると、各ステップにおけるリストサイズ |lt| が最大 h である局所文脈推薦のための o(ρ· a/(h − 1))-レグレットアルゴリズムを構築することができる。 0.76
Before we prove Theorem 6.1, notice that it can be combined with Theorem 4.2 and Theorem 4.4 respec- Theorem 6.1を証明する前に、Theorem 4.2とTheorem 4.4と組み合わせることができることに気付く。 0.69
tively to yield the following algorithms for local contextual recommendation. ローカルなコンテクストレコメンデーションのために、以下のアルゴリズムを提供する。 0.56
Corollary 6.2. Suppose that |Xt| ≤ A for all t ∈ N, and let H be any positive integer such that 2 ≤ H ≤ A. 登録番号6.2。 すべての t ∈ N に対して |Xt| ≤ A とし、H を 2 ≤ H ≤ A となる任意の正の整数とする。 0.66
Then, there is an O (A/(H − 1) · exp(d log d))-regret algorithm for local contextual recommendation where the list size |Lt| in each step is at most H. Corollary 6.3. すると、各ステップにおけるリストサイズ |Lt| が最大 H. Corollary 6.3 であるような、局所的なコンテキストレコメンデーションのための O (A/(H − 1) · exp(d log d))-regret アルゴリズムが存在する。 0.83
Suppose that |Xt| ≤ A for all t ∈ N, and let H be any positive integer such that 2 ≤ H ≤ A. すべての t ∈ N に対して |Xt| ≤ A とし、H を 2 ≤ H ≤ A となる任意の正の整数とする。 0.86
Then, there is an O(A/(H − 1) · d log T )-regret algorithm for local contextual recommendation where the list size |Lt| in each step is at most H. 次に、各ステップにおけるリストサイズ |Lt| が最大 H であるような、局所的文脈推薦のための O(A/(H − 1) · d log T )-regret アルゴリズムが存在する。 0.84
Note that these algorithms work for list sizes as small as H = 2 but may also give a better regret bound これらのアルゴリズムは、H = 2 ほど小さいリストサイズで機能するが、より良い後悔の束縛を与えることもある。 0.72
if we allow larger lists. より大きなリストを許可すれば 0.74
We will now prove Theorem 6.1. 定理6.1を証明します 0.63
Proof of Theorem 6.1. Theorem 6.1 の証明。 0.77
Our algorithm is similar to that of Theorem 3.1, except that we also play H − 1 random actions from Xt in addition to the action determined by the answer of A. アルゴリズムは定理 3.1 と似ているが、A の解によって決定される作用に加えて、Xt から H − 1 個のランダムな作用も行う。 0.77
More formally, each round t of our algorithm works as follows: より正式には、我々のアルゴリズムの各ラウンドtは以下のとおり動作する。 0.68
• Ask A for its query pt to the separation oracle. • oracle の分離に対するクエリ pt を a に問い合わせる。 0.80
• Let xt = BRt(pt), and let L′ • Output the list Lt = {xt} ∪ L′ t. • Let xloc • xt = BRt(pt) とし、L′ • リスト Lt = {xt} > L′ t. • xloc を出力する。 0.82
• If xloc t •xloc の場合 t 0.85
t be the feedback. フィードバックです。 0.36
6= xt, do the following: 6=xt、下記のとおり。 0.80
t ⊆ Xt be a random subset of Xt of size min{H − 1,|Xt|}. t > Xt は大きさ min{H − 1,|Xt|} の Xt のランダムな部分集合である。 0.83
– Return vt = (xloc - return vt = (xloc) 0.93
t − xt)/kxloc t − xt)/kxloc 0.99
t − xtk to A. t − xtk から a へ。 0.89
– Update the knowledge set Kt+1 = {w ∈ Kt |(cid:10)xloc – 知識集合 Kt+1 = {w ∈ Kt |(cid:10)xloc を更新する。 0.83
t − xt, w(cid:11) ≥ 0}. t − xt, w(cid:11) ≥ 0} である。 0.85
We will now show that the expected regret of the algorithm is at most ρ · A/(H − 1). 現在、アルゴリズムの期待された後悔は、少なくとも ρ · A/(H − 1) であることを示す。 0.78
From the regret bound of A, the following holds regardless of the randomness of our algorithm: 後悔から a のバウンドは、アルゴリズムのランダム性に関係なく以下のようになる。 0.61
ρ ≥ Xt:xloc ρ ≥ Xt:xloc 0.85
t 6=xt(cid:28) xloc kxloc t 6=xt(cid:28)xlockxloc 0.82
t − xt t − xtk t − xt t − xtk 0.85
, w∗ − pt(cid:29) ≥ Xt:xloc , w∗ − pt(cid:29) ≥ Xt:xloc 0.94
t 6=xt t − xt, w∗ − pt(cid:11) 0.5(cid:10)xloc t − xt, w∗ − pt(cid:11)! t 6=xt t − xt, w∗ − pt(cid:11) 0.5(cid:10)xloc t − xt, w∗ − pt(cid:11)! 0.77
. = 0.5 Xt (cid:10)xloc t − xt, w∗ − pt(cid:11) by . = 0.5 Xt (cid:10)xloc t − xt, w∗ − pt(cid:11) by 0.85
From the requirement of xloc xloc の要件から 0.60
t , we may further bound (cid:10)xloc t ではさらに (cid:10)xloc 0.74
Hence, from the above two inequalities, we arrive at したがって、上記の2つの不等式から、我々は到着する。 0.56
t − xt, w∗ − pt(cid:11) ≥ max (cid:10)xloc t − xt, w∗ − pt(cid:11) ≥ max (cid:10)xloc 0.91
x∈Lt hx − xt, w∗ − pti = max x ∈lt hx − xt, w∗ − pti = max 0.90
x′∈L′ t [hx′ − xt, w∗ − pti]+. x′∂L′ t hx′ − xt, w∗ − pti]+ である。 0.62
2ρ ≥Xt max x′∈L′ t 2ρ ≥Xt max (複数形 maxs) 0.54
[hx′ − xt, w∗ − pti]+. hx′ − xt, w∗ − pti]+ である。 0.86
18 18 0.85
Next, observe that E(cid:20) max 次に ご覧ください E(cid:20)max 0.75
x′∈L′ t [hx′ − xt, w∗ − pti]+(cid:21) ≥ Pr[x∗ = |L′ t| |Xt| · hx∗ − xt, w∗ − pti H − 1 A · hx∗ − xt, w∗ − pti . x′∂L′ t [hx′ − xt, w∗ − pti]+(cid:21) ≥ Pr[x∗ = |L′ t| |Xt| · hx∗ − xt, w∗ − pti H − 1 A · hx∗ − xt, w∗ − pti である。 0.62
t ∈ L′ t] · hx∗ − xt, w∗ − pti t ∈ L′ t] · hx∗ − xt, w∗ − pti 0.97
≥ Combining the above two inequalities, we get ≥ 上記の2つの不等式を組み合わせると 0.76
2ρ ≥ H − 1 A · E"Xt 2ρ ≥ H-1 A · E"Xt 0.80
t − xt, w∗i# . t − xt, w∗i# である。 0.69
hx∗ From this, we can conclude that the expected regret, which is equal to E [Pt hx∗ O (ρ · A/(H − 1)) as desired. hx∗ このことから、期待された後悔は E [Pt hx∗ O (ρ · A/(H − 1)) に等しいと結論付けることができる。 0.78
t − xt, w∗i], is at most t − xt, w∗i] は 0.61
6.2 Lower Bound We will now prove our lower bound. 6.2 下界 私たちは今、下限を証明します。 0.77
The overall idea of the construction is simple: we provide an action set that contains a “reasonably good” (publicly known) action so that, unless the optimum is selected in the list, the adversary can return this reasonably good action, resulting in the algorithm not learning any new information at all. 構築の全体的な考え方は単純である:我々は「合理的に良い」(公に知られている)アクションを含むアクションセットを提供し、最適化がリストで選択されない限り、敵は合理的に良いアクションを返すことができ、結果としてアルゴリズムは新たな情報を全く学ばない。 0.77
Theorem 6.4. Any algorithm for the local contextual recommendation problem that can output a list of size up to 2Ω(d) in each step incurs expected regret of at least 2Ω(d). 理論6.4。 各ステップで最大2ω(d)のサイズのリストを出力できる局所文脈推奨問題のためのアルゴリズムは、少なくとも2ω(d)の期待後悔をもたらす。 0.66
Proof. Let S be any maximal set of vectors in Bd such that the first coordinate is zero and the inner product between any pair of them is at most 0.1. 証明。 S を Bd 内の任意の極大ベクトル集合とし、第1座標は 0 であり、それらの対の間の内積は少なくとも 0.1 である。 0.70
By standard volume argument, we have |S| ≥ 2Ω(d). 標準的な体積論では、|S| ≥ 2Ω(d) である。 0.63
Furthermore, let e1 be the first vector in the standard basis. さらに、e1 を標準基底の最初のベクトルとする。 0.75
Consider the adversary that picks u ∈ S uniformly at random and let w∗ = 0.2e1 + 0.8u and let Xt = S ∪{e1} for all t ∈ N. The adversary feedback is as follows: if u /∈ Lt, return e1; otherwise, return u. 任意の t ∈ N に対して u ∈ S をランダムに選び、w∗ = 0.2e1 + 0.8u とし、Xt = S >{e1} とする逆数を考える。 0.58
We will now argue that any algorithm occurs expected regret at least 2Ω(d), even when allows to output たとえ出力が許されたとしても、任意のアルゴリズムが少なくとも 2Ω(d) を後悔して起こると論じる。 0.73
a list Lt of size as large as ⌊p|S|⌋ = 2Ω(d) in each step. リスト lt は、各ステップにおいて sp|s|\ = 2ω(d) という大きさである。 0.60
From Yao’s minimax principle, it suffices to consider only any deterministic algorithm A. Yaoのミニマックス原理から、決定論的アルゴリズムAのみを考えるのに十分である。 0.71
Let L0 t denote the list output by A at step t if it had received feedback e1 in all previous steps. l0 t が前回のすべてのステップでフィードバックe1を受けた場合、ステップ t で a で出力されたリストを表す。 0.72
Observe also that in each step for which u /∈ Lt, the loss of A is at least 0.6. また、u /∂ Lt の各ステップにおいて、A の損失は少なくとも 0.6 である。 0.79
Furthermore, in the first m√|S| |S| ≤ 0.1. さらに、最初の m |S| |S| ≤ 0.1 である。 0.62
m = ⌊0.1p|S|⌋ rounds, the probability that the algorithm selects u in any list is at most Hence we can bound the the expected total regret of A as: 任意のリストにおいて、アルゴリズムが u を選択する確率は、最も高いので、A の予想される全後悔を次のように境界付けることができる。 0.65
E[0.6 · |{t | u /∈ Lt}|] ≥ 0.6m Pr[u /∈ ∪m E[0.6 · |{t | u /のLt}|] ≥ 0.6m Pr[u /のLt}|] 0.87
t=1Lt] = 0.6m Pr[u /∈ ∪m t=1lt] = 0.6m pr[u /の採用。 0.52
t=1L0 t ] ≥ 0.6m · 0.9 ≥ 2Ω(d) t=1L0 t ] ≥ 0.6m · 0.9 ≥ 2Ω(d) 0.59
which concludes our proof. References これが我々の証明だ 参考文献 0.60
[1] CJ Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang. [1]CJ Argue、Anupam Gupta、Guru Guruganesh、Ziye Tang。 0.61
Chasing convex bodies with linear competitive ratio. 直線的な競争比率で凸体を追いかける。 0.61
In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1519–1524. 第14回 ACM-SIAM Symposium on Discrete Algorithms, page 1519–1524 に参加して 0.78
SIAM, 2020. SIAM、2020年。 0.83
1.3 [2] Peter Auer. 1.3 [2]ピーター・オーアー。 0.66
Using confidence bounds for exploitation-explora tion trade-offs. エクスプロレーション-探索トレードオフに信頼境界を使用する。 0.47
Journal of Machine Learn- ing Research, 3(Nov):397–422, 2002. 機械学習の日誌 ing research, 3(nov):397-422, 2002年。 0.69
1 19 1 19 0.85
[3] Baruch Awerbuch and Robert D Kleinberg. Baruch Awerbuch氏とRobert D Kleinberg氏。 0.66
Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. エンドツーエンドフィードバックによる適応ルーティング: 分散学習と幾何学的アプローチ。 0.71
In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 45–53, 2004. 第36回年次acmコンピューティング理論シンポジウムの紀要(2004年45-53頁)。
訳抜け防止モード: 第30~6回ACMコンピューティング理論シンポジウムに参加して 45-53頁、2004年。
1.3 [4] Dimitris Bertsimas and Santosh Vempala. 1.3 [4]Dmitris BertsimasとSantosh Vempala。 0.58
Solving convex programs by random walks. ランダムウォークによる凸プログラムの解法 0.70
Journal of the journal (複数形 journals) 0.46
ACM (JACM), 51(4):540–556, 2004. ACM (JACM) 51(4):540-556, 2004。 0.92
2.1 [5] Jesús Bobadilla, Fernando Ortega, Antonio Hernando, and Abraham Gutiérrez. 2.1 5]Jesús Bobadilla、Fernando Ortega、Antonio Hernando、Abraham Gutiérrez。 0.60
Recommender systems survey. 推薦システム 調査。 0.67
Knowledge-based systems, 46:109–132, 2013. 知識ベースシステム, 46:109–132, 2013 0.71
1.3 [6] Sébastien Bubeck, Yin Tat Lee, and Mohit Singh. 1.3 6] Sébastien Bubeck, Yin Tat Lee, Mohit Singh。 0.62
A geometric alternative to nesterov’s accelerated ネステロフの加速に代わる幾何学的代替 0.73
gradient descent. CoRR, abs/1506.08187, 2015. 勾配降下 CoRR, abs/1506.08187, 2015。 0.57
URL http://arxiv.org/abs /1506.08187. URL http://arxiv.org/abs /1506.08187 0.46
1.3 [7] Sébastien Bubeck, Bo’az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. 1.3 Sébastien Bubeck氏、Bo’az Klartag氏、Yin Tat Lee氏、Yuanzhi Li氏、Mark Sellke氏。 0.63
Chasing nested convex bodies nearly optimally. 縫い目のある凸体はほぼ最適である。 0.48
In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1496–1508. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, page 1496–1508 に参加して 0.78
SIAM, 2020. SIAM、2020年。 0.83
1.3, 2.1, 2.1 1.3, 2.1, 2.1 0.59
[8] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. [8]Wei Chu、Lihong Li、Lev Reyzin、Robert Schapire。 0.64
Contextual bandits with linear payoff functions. 線形ペイオフ機能付きコンテキスト帯域。 0.58
In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. 第14回人工知能・統計国際会議の議事録208-214頁。 0.60
JMLR Workshop and Conference Proceedings, 2011. JMLR Workshop and Conference Proceedings, 2011 (英語) 0.82
1 [9] Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. 1 9] Maxime C Cohen, Ilan Lobel, Renato Paes Leme。 0.76
Feature-based dynamic pricing. 機能ベースの動的価格設定。 0.54
In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 817–817. 手続き中 2016 acm conference on economics and computation の817–817頁。 0.68
ACM, 2016. 2016年、ACM。 0.87
1.3 [10] Martin Grötschel, László Lovász, and Alexander Schrijver. 1.3 10] Martin Grötschel, László Lovász, Alexander Schrijver 0.58
The ellipsoid method and its consequences in combinatorial optimization. 楕円体法とその結果 組合せ最適化です 0.62
Combinatorica, 1(2):169–197, 1981. 1(2):169–197, 1981。 0.64
1.3 [11] András György and Gyorgy Ottucsak. 1.3 11] andrás györgy and gyorgy ottucsak. 0.63
Adaptive routing using expert advice. エキスパートアドバイスを用いた適応ルーティング。 0.66
The Computer Journal, The Computer Journal(英語) 0.67
49(2):180–189, 2006. 49(2):180–189, 2006. 0.88
1.3 [12] András György, Tamás Linder, Gábor Lugosi, and György Ottucsák. 1.3 12]András György, Tamás Linder, Gábor Lugosi, György Ottucsák 0.61
The on-line shortest path problem オンライン最短経路問題 0.65
under partial monitoring. Journal of Machine Learning Research, 8(10), 2007. 部分的監視下で Journal of Machine Learning Research, 8(10, 2007 0.71
1.3 [13] Ravi Kannan, László Lovász, and Miklós Simonovits. 1.3 13] Ravi Kannan, László Lovász, Miklós Simonovits。 0.61
Isoperimetric problems for convex bodies and a 凸体とaの等角性問題 0.64
localization lemma. ローカライゼーションの補題。 0.34
Discrete & Computational Geometry, 13(3):541–559, 1995. Discrete & Computational Geometry, 13(3):541–559, 1995。 0.94
4.1 [14] Leonid Genrikhovich Khachiyan. 4.1 14] Leonid Genrikhovich Khachiyan 0.57
A polynomial algorithm in linear programming. 線形プログラミングにおける多項式アルゴリズム 0.80
In Doklady Akademii In Doklady Akademii 0.85
Nauk, volume 244, pages 1093–1096. Nauk, volume 244, page 1093–1096。 0.89
Russian Academy of Sciences, 1979. 1979年ロシア科学アカデミー会員。 0.67
1.3 [15] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. 1.3 [15]Branislav Kveton, Zheng Wen, Azin Ashkan, Csaba Szepesvari。 0.64
Combinatorial cascading bandits. コンビニアル・カスケードの盗賊。 0.28
arXiv preprint arXiv:1507.04208, 2015. arXiv preprint arXiv:1507.04208, 2015 0.80
1.3 [16] Renato Paes Leme and Jon Schneider. 1.3 16] Renato Paes Leme と Jon Schneider。 0.66
Contextual search via intrinsic volumes. 固有ボリュームによる文脈探索。 0.61
In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 268–282. 2018年IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) 268–282頁。 0.80
IEEE, 2018. 2018年、IEEE。 0.52
1.1.2, 1.3, 5.1 1.1.2, 1.3, 5.1 0.50
[17] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. [17]Lihong Li、Wei Chu、John Langford、Robert E Schapire。 0.72
A contextual-bandit approach to personalized news article recommendation. パーソナライズされたニュース記事レコメンデーションへのコンテキスト帯域アプローチ 0.56
In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010. 第19回world wide web国際会議の議事録、2010年661-670頁。 0.74
1.3 [18] Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. 1.3 [18]Lihong Li、Wei Chu、John Langford、Xuanhui Wang。 0.64
Unbiased offline evaluation of contextualbandit-bas ed news article recommendation algorithms. 文脈帯域に基づくニュース記事推薦アルゴリズムの非バイアスオフライン評価 0.72
In Proceedings of the fourth ACM international conference on Web search and data mining, pages 297–306, 2011. 第4回 acm international conference on web search and data mining, pages 297–306, 2011 (英語) 0.77
1.3 [19] Allen Liu, Renato Paes Leme, and Jon Schneider. 1.3 [19]Allen Liu、Renato Paes Leme、Jon Schneider。 0.60
Optimal contextual pricing and extensions. 最適なコンテキスト価格と拡張。 0.73
In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1059–1078. 2021年 ACM-SIAM Symposium on Discrete Algorithms (SODA) の論文1059-1078頁。 0.74
SIAM, 2021. SIAM、2021年。 0.74
1.1.2, 1.2, 1.3, 2.2 1.1.2, 1.2, 1.3, 2.2 0.52
20 20 0.85
[20] Ilan Lobel, Renato Paes Leme, and Adrian Vladu. ilan Lobel氏、Renato Paes Leme氏、Adrian Vladu氏。 0.51
Multidimensional binary search for contextual 文脈の多次元二項探索 0.68
decision-making. Operations Research, 2017. 意思決定。 2017年、経営調査。 0.63
1.3 [21] Rolf Schneider. 1.3 ロルフ・シュナイダー(Rolf Schneider)。 0.55
Convex bodies: the Brunn–Minkowski theory. 凸体: ブラン・ミンコフスキー理論。 0.56
Number 151. Cambridge university press, 背番号151。 ケンブリッジ大学出版局。 0.64
2014. 5.1 [22] Mark Sellke. 2014. 5.1 22]マーク・セールケ 0.67
Chasing convex bodies optimally. 最適に凸体を追いかける。 0.58
In Proceedings of the Fourteenth Annual ACM-SIAM 第14回ACM-SIAM講演会報告 0.64
Symposium on Discrete Algorithms, pages 1509–1518. 離散アルゴリズムに関するシンポジウム 1509-1518頁。 0.76
SIAM, 2020. SIAM、2020年。 0.83
1.3 [23] Linqi Song, Cem Tekin, and Mihaela Van Der Schaar. 1.3 [23]Linqi Song、Cem Tekin、Mihaela Van Der Schaar。 0.60
Online learning in large-scale contextual recom- 大規模コンテキストレコメンデーションにおけるオンライン学習 0.69
mender systems. IEEE Transactions on Services Computing, 9(3):433–445, 2014. メンダーシステムズ IEEE Transactions on Services Computing, 9(3):433–445, 2014 0.58
1.3 [24] Mohammad Sadegh Talebi, Zhenhua Zou, Richard Combes, Alexandre Proutiere, and Mikael Johansson. 1.3 [24]Mohammad Sadegh Talebi、Zhenhua Zou、Richard Combes、Alexandre Proutiere、Mikael Johansson。 0.62
IEEE Transactions on Automatic IEEE Transactions on Automatic 0.85
Stochastic online shortest path routing: The value of feedback. 確率的オンライン最短経路ルーティング: フィードバックの価値。 0.69
Control, 63(4):915–930, 2017. コントロール, 63(4):915–930, 2017。 0.81
1.3 [25] Liang Tang, Yexi Jiang, Lei Li, and Tao Li. 1.3 [25]梁唐、江西江、李麗、高麗。 0.54
Ensemble contextual bandits for personalized recommendation. パーソナライズされたレコメンデーションのためにコンテキストブレイディットを組み立てる。 0.34
In Proceedings of the 8th ACM Conference on Recommender Systems, pages 73–80, 2014. 第8回acm conference on recommender systems, pp. 73-80, 2014 ページ。 0.74
1.3 [26] Romain Warlop, Alessandro Lazaric, and Jérémie Mary. 1.3 Romain Warlop氏、Alessandro Lazaric氏、Jérémie Mary氏。 0.58
Fighting boredom in recommender systems 推薦システムにおける退屈対策 0.58
with linear reinforcement learning. In Neural Information Processing Systems, 2018. 線形強化学習で 2018年、ニューラル情報処理システム。 0.59
1.3 [27] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. 1.3 [27]Yisong Yue, Josef Broder, Robert Kleinberg, Thorsten Joachims。 0.66
The k-armed dueling bandits k‐armed dueling bandits 0.90
problem. Journal of Computer and System Sciences, 78(5):1538–1556, 2012. 問題よ Journal of Computer and System Sciences, 78(5):1538–1556, 2012 0.79
1.3 [28] Zhenhua Zou, Alexandre Proutiere, and Mikael Johansson. 1.3 Zhenhua Zou氏、Alexandre Proutiere氏、Mikael Johansson氏。 0.55
Online shortest path routing: The value of オンライン最短経路ルーティング:値 0.65
information. In 2014 American Control Conference, pages 2142–2147. 情報だ 2014年、アメリカン・コントロール・カンファレンス2142-2147頁。 0.64
IEEE, 2014. 2014年、IEEE。 0.65
1.3 21 1.3 21 0.72

翻訳にはFugu-Machine Translatorを利用しています。