論文の概要、ライセンス

# (参考訳) スケールフリーの対向型多武装バンディット [全文訳有]

Scale Free Adversarial Multi Armed Bandits ( http://arxiv.org/abs/2106.04700v1 )

ライセンス: CC BY 4.0
Sudeep Raja Putta, Shipra Agrawal(参考訳) 我々は、プレイヤーが損失の規模や大きさではなく、腕数n$しか知らない、スケールフリーのマルチアームバンド(MAB)問題を考える。 損失ベクトルは l_1,\dots, l_T \in \mathbb{R}^n$ である。 その目的は、後悔を$n$と$l_1,\dots,l_t$の関数に縛ることである。 規則化リーダ(ftrl)アルゴリズムに従うように設計し,mabに対する最初のスケールフリーな後悔保証を提供する。 ログバリア正規化器、重み付き推定器の重要性、適応学習率、適応探索パラメータを使用する。 本稿では,FTRL と Online Mirror Descent (OMD) の残差不等式を,ポテンシャル関数と混合ブレグマンを用いた確率的単純度に基づいて簡易に統一する手法を提案する。 また,Bregman Divergencesの局所ノルム下限を求める新たな手法を開発した。 これらのツールは独立したものかもしれない。

We consider the Scale-Free Adversarial Multi Armed Bandit(MAB) problem, where the player only knows the number of arms $n$ and not the scale or magnitude of the losses. It sees bandit feedback about the loss vectors $l_1,\dots, l_T \in \mathbb{R}^n$. The goal is to bound its regret as a function of $n$ and $l_1,\dots, l_T$. We design a Follow The Regularized Leader(FTRL) algorithm, which comes with the first scale-free regret guarantee for MAB. It uses the log barrier regularizer, the importance weighted estimator, an adaptive learning rate, and an adaptive exploration parameter. In the analysis, we introduce a simple, unifying technique for obtaining regret inequalities for FTRL and Online Mirror Descent(OMD) on the probability simplex using Potential Functions and Mixed Bregmans. We also develop a new technique for obtaining local-norm lower bounds for Bregman Divergences, which are crucial in bandit regret bounds. These tools could be of independent interest.
公開日: Tue, 8 Jun 2021 21:26:57 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] G L . 8 ] G L。 0.81
s c [ 1 v 0 0 7 4 0 sc [ 1 v 0 0 7 4 0 0.68
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Scale Free Adversarial Multi Armed Bandits スケールフリーの対向型多武装バンディット 0.64
Sudeep Raja Putta Columbia University New York, NY 10027 Sudeep Raja Putta Columbia University New York, NY 10027 0.85
sp3794@columbia.edu. edu sp3794@columbia.edu. edu 0.52
Shipra Agrawal Shipra (複数形 Shipras) 0.27
Columbia University New York, NY 10027 コロンビア大学ニューヨーク校10027年 0.62
sa3305@columbia.edu. edu SA3305@columbia.edu. edu 0.51
Abstract We consider the Scale-Free Adversarial Multi Armed Bandit(MAB) problem, where the player only knows the number of arms n and not the scale or magnitude of the losses. 概要 プレイヤーは、損失の規模や大きさではなく、武器数nのみを知ればよい、スケールフリーのマルチアームバンド(MAB)問題を考える。
訳抜け防止モード: 概要 我々は,mab(scale-free adversarial multi armed bandit)問題を考える。 プレイヤーは武器の数だけを知っていて、損失の規模や大きさを知らない。
0.60
It sees bandit feedback about the loss vectors l1, . 損失ベクトル l1, . 0.29
. . , lT ∈ Rn. . . , lT ∈ Rn。 0.83
The goal is to bound its regret as a function of n and l1, . 目的は、後悔を n と l1 の関数として束ねることである。 0.79
. . , lT . We design a Follow The Regularized Leader(FTRL) algorithm, which comes with the first scale-free regret guarantee for MAB. . . 、lT。 規則化リーダ(ftrl)アルゴリズムに従うように設計し,mabに対する最初のスケールフリーな後悔保証を提供する。 0.75
It uses the log barrier regularizer, the importance weighted estimator, an adaptive learning rate, and an adaptive exploration parameter. ログバリア正規化器、重み付き推定器の重要性、適応学習率、適応探索パラメータを使用する。 0.64
In the analysis, we introduce a simple, unifying technique for obtaining regret inequalities for FTRL and Online Mirror Descent(OMD) on the probability simplex using Potential Functions and Mixed Bregmans. 本稿では,FTRL と Online Mirror Descent (OMD) の残差不等式を,ポテンシャル関数と混合ブレグマンを用いた確率的単純度に基づいて簡易に統一する手法を提案する。 0.80
We also develop a new technique for obtaining local-norm lower bounds for Bregman Divergences, which are crucial in bandit regret bounds. また,Bregman Divergencesの局所ノルム下限を求める新たな手法を開発した。
訳抜け防止モード: 私たちはまた 新しい技術を開発しました bregman divergences の局所-ノルム下限の取得は、バンドイットの後悔の限界において不可欠である。
0.56
These tools could be of independent interest. これらのツールは独立したものかもしれない。 0.54
1 Introduction The adversarial Multi Armed Bandit(MAB) problem proceeds as a sequential game of T rounds between a player and an adversary. 1 はじめに 敵のMulti Armed Bandit(MAB)問題は、プレイヤーと敵の間のTラウンドのシーケンシャルゲームとして進行する。 0.71
In each round t = 1, . 各ラウンド t = 1 において。 0.75
. . , T , the player selects a distribution pt over the n-arms and the adversary selects a loss vector lt belonging to some set L ⊆ Rn. . . , T, プレイヤーは、n−アーム上の分布ptを選択し、敵は、ある集合 L > Rn に属する損失ベクトルlt を選択する。 0.81
An action it is sampled from pt and the player observes the loss lt(it). ptからサンプリングされたアクションで、プレーヤーはロスlt(it)を観察します。 0.69
The (expected) regret of the player is: プレイヤーの(予想された)後悔は次のとおりである。 0.61
(cid:34) T(cid:88) (cid:34)T(cid:88) 0.78
t=1 (cid:35) t=1。 (cid:35) 0.62
T(cid:88) t=1 t(cid:88) t=1。 0.63
RT = E lt(it) − min i∈[n] RT = E lt(it) − min i∂[n] 0.82
lt(i) lt (複数形 lts) 0.52
The goal of the player is to sequentially select the distributions p1, . プレイヤーのゴールは、分配p1, を順次選択することである。 0.74
. . , pT such that RT is minimized. . . RT が最小となる pT である。 0.82
The MAB problem has been studied extensively, so we refer to the texts [7, 17, 22] for greater details. MAB問題は広く研究されており、詳細についてはテキスト(7, 17, 22)を参照。 0.73
Under the assumption that L = [0, 1]n, it is a well established fact that minimax rate of regret is Θ( L = [0, 1]n という仮定の下では、後悔のミニマックスレートが() であることはよく確立された事実である。 0.62
nT ). The Exp3 algorithm [5] has a O((cid:112)nT log(n)) regret bound, which is minimax in T . nT)。 Exp3 アルゴリズム[5] は O((cid:112)nT log(n)) の後悔境界を持ち、T の最小値である。 0.78
The POLY-INF algorithm [2] removes the(cid:112)log(n) factor making it minimax in both T and n. POLY-INFアルゴリズム[2]は、(cid:112)log(n)因子を除去し、T と n の両方で最小化する。 0.77
√ If L were different, the problem can be reduced to the previous case by scaling and translating the losses. √ L が異なる場合、損失を拡大し、翻訳することで、問題を前のケースに還元することができる。 0.77
However, this requires knowing L beforehand. しかし、これは事前に L を知る必要がある。 0.62
In the Scale-Free problem, the algorithm only knows n and does not know anything about L. The losses can be completely arbitrary. スケールフリー問題では、アルゴリズムは n のみを知っており、L については何も知らない。
訳抜け防止モード: スケール-自由問題では、アルゴリズムは n しか知らない lについて何も知りません。損失は完全に任意です。
0.70
Despite this, if the algorithm’s regret can be bounded as a function of n and the magnitude of loss vectors l1, . それにもかかわらず、アルゴリズムの後悔が n の関数と損失ベクトル l1 の大きさとして境界化することができる。 0.80
. . , lT , then the algorithm is said to be scale-free. . . lt では、アルゴリズムはスケールフリーであると言われている。 0.78
Scale-free algorithms were studied in the full-information setting (where the player sees the complete vector lt in each round). スケールフリーなアルゴリズムはフルインフォメーション設定(プレイヤーは各ラウンドの完全なベクトルltを見る)で研究された。 0.81
For the Experts problem, which is the full-information counterpart of adversarial MAB, the AdaHedge algorithm [23, 11] has a t=1 (cid:107)lt(cid:107) 2∞)). AdaHedge アルゴリズム [23, 11] は t=1 (cid:107)lt(cid:107) 2∞) を持つ。
訳抜け防止モード: 敵MABに匹敵する完全情報であるエキスパート問題について AdaHedgeアルゴリズム[23,11]はt=1(cid:107)lt(cid:107 )2∞ ) である。
0.80
If one knows maxt (cid:107)lt(cid:107) ∞ < G in advance, scale-free regret bound of O( maxt (cid:107)lt(cid:107) ∞ < G in advance, scale-free regret bound of O() 0.88
then Hedge’s [13] regret is Θ(G(cid:112)T log(n)). すると、ヘッジの[13]後悔はθ(g(cid:112)t log(n))である。 0.73
Thus, in full-information, the price of scale-freeness is したがって、フルインフォメーションでは、スケールフリーネスの価格は 0.73
(cid:113) log(n)((cid:80)T (cid:113) log(n)((cid:80)T 0.90
O(1). Preprint. O(1)。 プレプリント。 0.74
Under review. レビュー中。 0.58
英語(論文から抽出)日本語訳スコア
Many classical algorithms for MABs (such as Exp3, POLY-INF) and full information Online Learning can be re-cast as instances of either Follow The Regularized Leader(FTRL) or Online Mirror Descent(OMD). MAB(Exp3、POLY-INF)やオンライン学習のための多くの古典的アルゴリズムは、FTRL(Follow The Regularized Leader)またはOMD(Online Mirror Descent)のいずれかのインスタンスとして再放送することができる。 0.71
This view greatly simplifies the analysis of these algorithms through the use of Bregman Divergences. この見解は、ブレグマン分枝を用いてこれらのアルゴリズムの分析を大幅に単純化する。 0.67
We refer to [10, 21, 15, 18] for a detailed history of these algorithms. これらのアルゴリズムの詳細な歴史について [10, 21, 15, 18] を参照する。 0.80
Scalefree versions of FTRL and OMD for full-information online learning were studied in [19]. フル情報オンライン学習のためのFTRLとOMDのスケールフリーバージョンを[19]で検討した。 0.71
The typical approach for extension to bandit feedback is to reduce the problem to full-information via the importance-weighted estimator and use a local-norm regret inequality for the algorithm. 帯域幅フィードバックへの拡張の典型的なアプローチは、重要度重み付け推定器を通じて問題を全情報に還元し、アルゴリズムに局所ノルム後悔の不等式を用いることである。 0.63
As the regret inequalities developed in [19] are not local-norm, the reduction approach does not work for the algorithms presented there. 19)で発達した後悔の不等式は局所ノルムではないので、還元法はそこで提示されるアルゴリズムには効かない。 0.56
1.1 Our Contributions We present the first scale-free algorithm for the adversarial MAB problem. 1.1 貢献 逆MAB問題に対する最初のスケールフリーアルゴリズムを提案する。 0.76
It is an instance of FTRL with the log-barrier regularizer. これは、ログバリア正規化器を備えたFTRLの例である。 0.62
The importance-weighted estimator is used to handle bandit feedback. 重要度重み付き推定器は、バンディットのフィードバックを処理するために使用される。 0.41
Adaptive learning rate ηt and an adaptive exploration parameter γt are used to achieve exploration-exploita tion trade-off. 適応学習率ηtと適応探索パラメータγtを用いて探索-探索トレードオフを実現する。 0.71
We derive a novel scale-free bound for this algorithm. 我々はこのアルゴリズムの新たなスケールフリー境界を導出する。 0.65
An equally important contribution of our work is new analysis techniques for OMD and FTRL. omdとftrlの新しい分析技術も同じように重要な貢献をしています。 0.55
We provide a simple analysis of these algorithms on the probability simplex with Legendre regularizers constructed from Potential Functions [3, 4]. ポテンシャル関数 [3, 4] から構築したレギュラー正則化器を用いて,これらのアルゴリズムを単純に解析する。 0.79
In this case, the iterates have a simple closed-form expression. この場合、イテレートは単純な閉形式表現を持つ。 0.62
We introduce a generalized notion of Bregman divergence called Mixed Bregmans to unify the analysis. この分析を統一するために,混合ブレグマンと呼ばれるブレグマン分岐の一般化概念を導入する。 0.53
Finally, we show an easy technique for obtaining local-norm lower bounds for Bregman divergences. 最後に,bregman divergencesの局所ノルム下限を得るための簡単な手法を示す。 0.66
These lower bounds immediately imply a local dual-norm upper bound for the regret. これらの下界は直ちに、後悔に対する局所的双対ノルム上界を意味する。 0.59
Due to their generality, these techniques are of independent interest. 一般性のため、これらの技術は独立した関心を持つ。 0.62
1.2 Related Work variance of the losses were shown in [16, 8]. 1.2関連作品 損失のばらつきは [16, 8] で示された。 0.74
Path length bounds that depend on(cid:80)T−1 bound depending on(cid:80)T cid:80)T−1が(cid:80)Tに依存する経路の長さ境界 0.79
Scale-Free bounds are a special class of Data-dependent regret bounds. スケールフリー境界は、データ依存の後悔境界の特別なクラスである。 0.55
These bounds use a “measure of hardness" of the sequence of loss vectors instead of T . これらの境界は、t の代わりに損失ベクトル列の「硬度の測定」を用いる。 0.77
Algorithms that have a Data-dependent regret bound perform better than the worst-case regret, when the sequence of losses is “easy" according to the measure of hardness used. データ依存の後悔バウンドを持つアルゴリズムは、使用するハードネスの尺度に従って損失のシーケンスが“容易”である場合、最悪の場合の後悔よりもパフォーマンスがよい。 0.70
For instance, First-order bounds [1, 12, 20], also known as t=1 lt(i). 例えば、一階境界 [1, 12, 20] は t=1 lt(i) としても知られる。 0.76
Bounds that depend on the empirical small-loss or L(cid:63) bounds depend on L(cid:63) = mini∈[n] t=1 (cid:107)lt − lt+1(cid:107) or a similar quantity appear in [24, 9]. 経験的小損失またはl(cid:63)境界に依存する境界は、l(cid:63) = miniψ[n] t=1 (cid:107)lt − lt+1(cid:107) または同様の量が [24, 9] に現れる。 0.73
For stochastic losses and linearly separable losses, there are gap-dependent bounds [25]. 確率的損失と線形分離可能な損失については、ギャップ依存境界[25]がある。 0.66
Our bound is comparable to a result in [8], where they derive a regret t=1 (cid:107)lt(cid:107) 2 2. 私たちの境界は [8] の結果に匹敵し、そこでは後悔 t=1 (cid:107)lt(cid:107) 2 が導かれる。 0.67
However, all these results require some condition on the losses, either L = [0, 1]n or L = [−1, 1]n. In the case when L = [0,∞)n, [1] show that a variant of Exp3 has regret O(T ν/2+2/3) if t=1 lt(i)2 = O(T ν+1). L = [0, 1]n または L = [−1, 1]n である場合、[1] は Exp3 の変種が t = 1 lt(i)2 = O(T ν+1) であれば、O(T ν/2+2/3) を後悔していることを示す。
訳抜け防止モード: しかし、これらの結果は損失に対して何らかの条件を必要とする。 L = [ 0, 1]n または L = [ −1, 1]n のいずれかである。 L = [ 0,∞)n の場合、[ 1 ] が Exp3 の変種が t=1 lt(i)2 = O(T ν+1 ) であれば、O(T ν/2 + 2/3 ) を後悔することを示す。
0.78
[14] give an algorithm that uses a restarting Exp3 along with maxi∈[n] a doubling-trick to handle unbounded positive losses. [14] は Exp3 を再起動するアルゴリズムと maxi・[n] を2倍のトリックで非有界な正の損失を処理するアルゴリズムを与える。 0.64
Combining it with an epoch-wise learning rate schedule, they show a ˜O(n(maxt (cid:107)lt(cid:107) ∞) L(cid:63)) regret bound. これをエポックな学習率のスケジュールと組み合わせると、 >O(n(maxt (cid:107)lt(cid:107) ∞) L(cid:63)) の後悔境界を示す。 0.75
While it may be possible to use an algorithm on L = [−1, 1]n (like in [8]) along with the restarting and doubling procedures of [14] to handle losses in Rn, such an algorithm would not further our understanding of online learning. L = [−1, 1]n([8]のように)のアルゴリズムと[14]の再開と2倍の手順を併用してRnの損失を処理することができるが、そのようなアルゴリズムはオンライン学習に対する我々の理解をさらに深めるものではない。 0.88
Our algorithm can handle any sequence of loss vectors in Rn and also has a scale-free regret bound without using any doubling or restating. 我々のアルゴリズムは、Rn の任意の損失ベクトル列を処理でき、また、倍数や再帰を使わずに、スケールフリーの後悔境界を持つ。 0.69
So, we believe that it is a novel contribution to the field. そのため、この分野への新たな貢献であると考えています。 0.66
(cid:80)T (cid:80)T (cid:80)t (cid:80)t 0.82
√ 1.3 Organization Section 2 presents the Scale-Free MAB algorithm (Algorithm 1) and its scale-free regret bound (Theorem 1). √ 1.3 組織 第2節は、スケールフリーMABアルゴリズム(Algorithm 1)とそのスケールフリー後悔境界(Theorem 1)を示す。 0.77
In Section 3, we present the new regret analysis techniques we have developed for OMD and FTRL, which might be of independent interest. 第3節では,OMDとFTRLのために開発した新たな後悔分析手法について述べる。 0.58
In Section 4, we use the results from Section 3 to prove our scale-free regret bound for Algorithm 1. 第4節では,第3節の結果を用いて,アルゴリズム1に対するスケールフリーな後悔を証明する。 0.71
Finally in Section 5, we discuss the design choices that were made in our algorithm and argue why it may not be improvable. 最後に、第5節では、アルゴリズムで行った設計上の選択について議論し、なぜ即興化できないのかを論じる。 0.67
All proofs that do not appear immediately after a statement are in the Appendix. 文の直後に現れないすべての証明は付録に含まれている。 0.63
2 2 0.85
英語(論文から抽出)日本語訳スコア
2 Algorithm Let ∆n be the probability simplex {p ∈ Rn :(cid:80)n 2アルゴリズム n を確率 simplex {p ∈ rn :(cid:80)n とする。 0.77
i=1 p(i) = 1, p(i) ≥ 0, i ∈ [n]} and let ej be the vector with ej(j) = 1 and ej(i) = 0 for all i (cid:54)= j. i=1 p(i) = 1, p(i) ≥ 0, i ∈ [n]} であり、ej をすべての i (cid:54)= j に対して ej(j) = 1 と ej(i) = 0 を持つベクトルとする。 0.97
Our scale-free MAB algorithm is described below: Algorithm 1: Scale-Free Multi Armed Bandit スケールフリーmabアルゴリズム:アルゴリズム1:スケールフリーマルチ武装バンディット 0.59
1 Starting Parameters: η0 = 1, γ0 = 1/2 1 開始パラメータ:η0 = 1, γ0 = 1/2 0.86
2 Regularizer F (q) = 2正則化 f (q) = 0.74
(f (q(i)) − f (1/n)), where f (x) = − log(x) (f (q(i)) − f (1/n)) ここで f (x) = − log(x) 0.90
n(cid:88) i=1 n(cid:88) i=1 0.71
3 First iterate p1 = (1/n, . 3 第一に p1 = (1/n, 。 0.65
. . , 1/n) 4 for t = 1 to T do 5 . . , 1/n) 4 for t = 1 to T do 5 0.89
Compute Sampling distribution: p(cid:48) Sample Arm it ∼ p(cid:48) 計算機サンプリング分布:p(cid:48)サンプルアーム;p(cid:48) 0.85
t and see loss lt(it). t の損失 lt(it) を参照してください。 0.59
(cid:32) t(cid:88) (cid:32) t(cid:88) 0.81
Compute ηt = Compute ηt = 0.94
ls(is)2 p(cid:48) s(is) Construct Loss Estimator ˜lt(i) = ls(is)2 p(cid:48) s(is) Construct Loss Estimator >lt(i) = 0.94
1 + s=1 t = (1 − γt−1)pt + (cid:32) (cid:33)−1/2 1 + s=1 t = (1 − γt−1)pt + (cid:32) (cid:33)−1/2 0.73
and γt = lt(it) p(cid:48) t(it) そして γt = lt(it) p(cid:48) t(it) 0.93
eit(i) 1 2 eit(i) 1 2 0.85
(cid:34) γt−1 n (cid:34) γt−1 n 0.69
t(cid:88) s=1 t(cid:88) s=1 0.71
1 + Compute next iterate by FTRL: pt+1 = arg min q∈∆n 1 + 次のイテレートを ftrl で計算する: pt+1 = arg min q linkedin 0.71
F (q) + ηt F (q) + ηt 0.97
6 7 8 9 (cid:33)−1/2 6 7 8 9 (cid:33)−1/2 0.80
|ls(is)| p(cid:48) s(is) |ls(is)| p(cid:48) s(is) 0.97
t(cid:88) s=1 t(cid:88) s=1 0.71
q(cid:62)˜ls (cid:35) q(cid:62) (cid:35) 0.86
The scale-free expected regret bound for the above algorithm is: Theorem 1. 上記のアルゴリズムのスケールフリーな期待後悔は次のとおりである。 0.64
For any l1, . . . l1 の場合。 . . 0.77
, lT ∈ Rn, the expected regret of Algorithm 1 is atmost: , lT ∈ Rn, 予想されるアルゴリズム 1 の後悔は以下の通りである。 0.74
Where L∞ = maxt (cid:107)lt(cid:107) ∞, L2 =(cid:80)T L∞ = maxt (cid:107)lt(cid:107) ∞, L2 = (cid:80)T 0.89
2 + (n log(1 + S∞) + 4) 2 + (n log(1 + S∞) + 4) 0.91
(cid:112) t=1 (cid:107)lt(cid:107) 2 (cid:112) t=1(cid:107)lt(cid:107 )2 0.73
1 + L2 +(cid:0)2nL2∞ + nL∞ + 2(cid:1)(cid:112) 2, L1 =(cid:80)T t=1 (cid:107)lt(cid:107) 1 and S∞ = (cid:107)(cid:80)T 1 + L2 + (cid:0)2nL2∞ + nL∞ + 2(cid:112) 2, L1 = (cid:80)T t=1 (cid:107)lt (cid:107)1 and S∞ = (cid:107)(cid:80)T 0.81
1 + L1 t=1 lt(cid:107)∞ 1 + L1 t=1 lt(cid:107)∞ 0.84
3 Analysis 3.1 Preliminaries 3 分析 3.1 予備 0.73
Definition 2 (Potential Function). 定義 2 (Potential Function)。 0.73
A function ψ : (−∞, a) → (0, +∞) for some a ∈ R ∪ {+∞} is called a Potential if it is convex, strictly increasing, continuously differentiable and satisfies: ある a ∈ R に対する函数 t : (−∞, a) → (0, +∞) は、それが凸であり、厳密に増加し、連続的に微分可能であり、満足であるときにポテンシャルと呼ばれる。 0.87
lim x→−∞ ψ(x) = 0 lim x→−∞ ψ(x) = 0 0.88
and lim x→a そして lim x→a 0.71
ψ(x) = +∞ For instance, exp(x) is a potential function with a = ∞ and −1/x is a potential with a = 0. ψ(x) = +∞ 例えば、exp(x) は a = ∞ のポテンシャル函数であり、−1/x は a = 0 のポテンシャルである。 0.92
A potential function typically looks like Figure 1. ポテンシャル関数は通常図1に似ています。 0.72
This definition is slightly different from the definition of a potential in [3, 4]. この定義は[3, 4]におけるポテンシャルの定義と少し異なる。 0.75
We do not have the requirement that ψ−1 is integrable on [0, 1]. ψ−1 が [0, 1] 上で可積分である必要はない。 0.68
Figure 1: Potential Function Definition 3 (Legendre function). 図1:潜在的な機能 定義3(レジェンドル関数)。 0.76
A continuous function F : D → R is Legendre if F is strictly convex, continuously differentiable on Interior(D) and limx→D/Interior(D) (cid:107)∇F (x)(cid:107) = +∞. 連続函数 f : d → r がルジャンドルであるとは、f が厳密に凸で、内部(d) と limx→d/interior(d) (cid:107) で連続微分可能であることを言う。 0.81
For instance, the function x log(x) − x, −√ Definition 4 (Bregman Divergence). 例えば、函数 x log(x) − x, − 定義 4 (Bregman Divergence) である。 0.75
The Bregman Divergence of function F is: 関数 F のブレグマンダイバージェンス (Bregman Divergence) は、 0.73
x, − log(x) are all Legendre on (0,∞) x, − log(x) は (0,∞) 上のすべてのレジェンドである 0.86
BregF (x(cid:107)y) = F (x) − F (y) − ∇F (y)(cid:62)(x − y). BregF (x(cid:107)y) = F (x) − F (y) − yF (y)(cid:62)(x − y)。 0.92
3 3 0.85
英語(論文から抽出)日本語訳スコア
We introduce a novel concept of Mixed Bregman which will simplify our analysis. 我々は、分析を簡素化するMixed Bregmanという新しい概念を導入する。 0.78
Definition 5 (Mixed Bregman). 定義5(Mixed Bregman)。 0.74
For α, β > 0 the (α, β)-Mixed Bregman of function F is: α, β > 0 に対して、函数 F の (α, β)-混合ブレグマンは、 0.86
Bregα,β F (x(cid:107)y) = Bregα,β F(x(cid:107)y) = 0.96
F (x) α − ∇F (y) F (x) α f (y) である。 0.74
(cid:62) − F (y) β F (x(cid:107)x) may not be zero. (cid:62) − F (y) β F (x(cid:107)x) は 0 でないかもしれない。 0.82
However, we do have the (x − y). しかし、私たちには (x − y)。 0.76
β The Mixed Bregman is not a divergence as Bregα,β relation αBregα,α β 混合ブレグマンは、ブレグα,β関係αBregα,αとして分岐しない 0.72
F (x(cid:107)y) = BregF (x(cid:107)y). F(x(cid:107)y) = BregF(x(cid:107)y) 0.92
i=1 ψ(θ(i) + λ). i=1 >(θ(i) + λ)。 0.88
3.2 Potentials, Probabilities and Legendre Functions 3.2 ポテンシャル,確率,レジェンドル関数 0.74
i=1 ∈ ∆n forms a probability distribution. i=1 ∈ sn は確率分布を形成する。 0.73
Lemma 6. For every θ ∈ Rn, there exists a unique λ such that g(θ, λ) = 1 第6回。 すべての θ ∈ Rn に対して、g(θ, λ) = 1 となる一意な λ が存在する。 0.72
Consider a function g : Rn × R → R+ defined as g(θ, λ) =(cid:80)n Using Lemma 6, we can define a function λ(θ) such that g(θ, λ(θ)) =(cid:80)n Since ψ(θ(i) + λ(θ)) ≥ 0 and(cid:80)n fψ(z) =(cid:82) ψ−1(z)dz. g(θ, λ) =(cid:80)n と定義される函数 g: rn × r → r+ を考えると、g(θ, λ(θ)) =(cid:80)n が ψ(θ(i) + λ(θ)) ≥ 0 かつ(cid:80)n fψ(z) =(cid:82) ψ−1(z)dz となるような函数 λ(θ) を定義することができる。 0.92
Observe that f(cid:48) the function Fψ : Rn → R as Fψ(x) =(cid:80)n f(cid:48) 関数 fψ : rn → r を fψ(x) =(cid:80)n とする。 0.81
i=1 ψ(θ(i) + λ(θ)) = 1. i=1 ψ(θ(i) + λ(θ)) = 1, we can see that the vector ψ(θ + λ(θ)) ≡ {ψ(θ(i) + λ(θ))}n Associated with a potential ψ, we define a function fψ : (0, +∞) → R as the antiderivative i=1 ψ(θ(i) + λ(θ)) = 1. i=1 ψ(θ(i) + λ(θ)) = 1 は、ベクトル ψ(θ + λ(θ)) , {ψ(θ(i) + λ(θ))}n がポテンシャル ψ と関係していることが分かるので、関数 fψ : (0, +∞) → r を反導関数として定義する。 0.94
ψ−1(z) |= +∞ and fψ is strictly convex, proving that fψ is a Legendre function on (0,∞). ψ−1(z) |= +∞ であり、fψ は厳密に凸であり、fψ が (0,∞) 上のルジャンドル函数であることを証明している。
訳抜け防止モード: −1(z ) |= + ∞ で f は厳密な凸である。 f が (0,∞ ) 上のルジャンドル函数であることを証明する。
0.76
Define i=1[fψ(x(i)) − fψ(1/n)]. i=1[f-(x(i)) − f-(1/n)] を定義する。 0.83
This function is Legendre on (0,∞)n. We will use Fψ(x) as the regularizer for OMD and FTRL in the subsequent analysis. この関数は (0,∞)n 上のルジャンドルであり、その後の解析では、OMD と FTRL の正則化子として F =(x) を用いる。 0.70
Given a potential ψ : (−∞, a) → (0, +∞) and its associated function fψ, the Legendre-Fenchel dual ψ(u) = supz>0(zu − fψ(z)). ポテンシャル ψ : (−∞, a) → (0, +∞) とその関連する函数 fψ が与えられると、ルジャンドル・フェンシェル双対 ψ(u) = supz>0(zu − fψ(z)) となる。 0.89
The supremum is achieved at ψ : (−∞, a) → R defined as f (cid:63) of fψ is f (cid:63) −1(u) = ψ(u). 上限は、 f の f (cid:63) が f (cid:63) −1(u) = s(u) と定義される s : (−∞, a) → R で達成される。 0.88
So we have that f (cid:63) ψ(u) = uψ(u) − fψ(ψ(u)). したがって f (cid:63) ψ(u) = uψ(u) − fψ(ψ(u)) となる。 0.86
This implies f (cid:63) z = f(cid:48) (u) = ψ(u) ψ (cid:48)(cid:48) and f (cid:63) ψ これは f (cid:63) z = f(cid:48) (u) = .(u) . (cid:48)(cid:48) and f (cid:63) . 0.85
(u) = ψ(cid:48)(u). (u) = ψ(cid:48)(u)。 0.92
Further, using integration by parts on(cid:82) ψ(u)du and substituting ψ(u) = s: ψ(u) =(cid:82) ψ(u)du. さらに、(cid:82) ψ(u)du 上の部分による積分と ψ(u) = s: ψ(u) =(cid:82) ψ(u)du の置換を用いる。 0.84
The following property will be useful in the analysis: 分析には以下の性質が役立ちます。 0.72
ψ(z) =(cid:2)ψ(cid:48)(ψ−1(z))(cid:3)−1. ψ(z) =(cid:2)ψ(cid:48)(ψ−1(z))(cid:3)−1。 0.82
So limz→0 | ψ−1(s)ds = uψ(u) − fψ(ψ(u)) = f (cid:63) limz→0 | ψ−1(s)ds = uψ(u) − fψ(ψ(u)) = f (cid:63) 0.90
Thus f (cid:63) Lemma 7. f (cid:63) Lemma 7。 0.81
Let x, y be such that x = ψ(u) and y = ψ(v). x, y を x = ψ(u) かつ y = ψ(v) とする。 0.72
Then Bregfψ ψ(z) = ψ−1(z) and f(cid:48)(cid:48) そしてbregfψ ψ(z) = ψ−1(z) および f(cid:48)(cid:48) 0.73
(y(cid:107)x) = Bregf (cid:63) (y(cid:107)x) = Bregf (cid:63) 0.90
(u(cid:107)v) (u(cid:107)v) 0.94
tψ(cid:48)(u)du = uψ(u) − tψ(cid:48)(u)du = uψ(u) − 0.93
ψ(u)du = uψ(u) − ψ(u)du = uψ(u) − 0.92
(cid:48) ψ (cid:48) ψ 0.82
ψ ψ(u) (cid:90) ψ ψ(u) (cid:90) 0.83
(cid:90) (cid:90) (cid:90) (cid:90) 0.78
3.3 Unifying Online Algorithms on the Simplex 3.3 Simplex上のオンラインアルゴリズムの統合 0.68
Typically OMD and FTRL are viewed as two different families of algorithms and they are also analyzed quite differently. 通常、OMDとFTRLは2つの異なるアルゴリズムのファミリーと見なされ、また全く異なる解析を行う。 0.76
This is certainly true in general, but on the probability simplex we observe that OMD and FTRL are essentially equivalent to the Implicitly Normalized Forecaster(INF) algorithm of [2] with different Loss Aggregators. これは一般には正しいが、確率的単純性では、OMDとFTRLは本質的に、異なるロスアグリゲータを持つ[2]のImplicitly Normalized Forecaster(INF)アルゴリズムと等価である。 0.78
Let us consider OMD first. まずはOMDについて考えてみましょう。 0.39
The iterates under the two forms are summarized in Table 1. 2つの形態の反復は表1にまとめられる。 0.70
In the optimization form, p1 = arg minq∈∆n Fψ(q) and in the INF form θ0 = 0. 最適化形式では、p1 = arg minqコメント(q) と INF 形式では θ0 = 0 となる。 0.78
The Loss Aggregator for s=1 ηsls. s=1 ηsls の損失アグリゲータ。 0.72
As seen in the last row Table 1, we can express OMD iterates using an 最後の行表1に示すように、OMD の反復を A を使って表現できます。 0.68
OMD is θt = −(cid:80)t OMD は θt = −(cid:80)t である 0.76
optimization directly on the aggregator as well. アグリゲータの最適化も直接行う。 0.58
The iterates of FTRL are summarized in Table 2. FTRLの繰り返しを表2にまとめる。 0.62
In the optimization form, p1 = arg minq∈∆n Fψ(q) and in the INF form θ0 = 0 and η0 > 0. 最適化形式では、p1 = arg minqコメント(q) と INF 形式では θ0 = 0 と η0 > 0 である。 0.81
FTRL is usually written as an optimization on its Loss Aggregator, θt = −ηt s=1 ls, as seen in the first row. FTRLは通常、第1行で見られるように、ロスアグリゲータ θt = −ηt s=1 ls の最適化として記述される。 0.77
However, we prove that FTRL can be written similar to 1-step OMD and 2-step OMD as well. しかし FTRL は 1 段階の OMD や 2 段階の OMD と同様に書けることが証明された。 0.81
In the optimization form, this makes use of the Mixed Bregman instead of the Bregman Divergence. 最適化形式では、これはBregman Divergenceの代わりにmixed Bregmanを使用する。 0.75
The 2-step versions are valid only if ˜pt+1 exists at each step. 2段階のバージョンは、各ステップに spt+1 が存在する場合にのみ有効である。 0.58
The 1-step and aggregator versions are always valid and are in-fact equivalent. 1ステップとアグリゲータバージョンは常に有効であり、インファクト同等である。 0.60
These results appear in the Appendix. これらの結果はAppendixに掲載されている。 0.58
For a quick proof of FTRL, form the Lagrangian L(q, α) = Fψ(q)+ηt i=1 q(i)). FTRL の素早い証明は、ラグランジアン L(q, α) = F(q)+ηt i=1 q(i)) となる。 0.83
Taking the gradient and equating to 0, we see that the solution is q = ψ(θt + α) such that q is a probability distribution. 勾配を取り、0 に等しくすると、解は q が確率分布であるような q = ψ(θt + α) であることが分かる。 0.82
Using Lemma 6, we know that the unique solution is α = λ(θt). Lemma 6 を用いると、一意解が α = λ(θt) であることが分かる。 0.82
Therefore pt+1 = ψ(θt + λ(θt)). したがって pt+1 = ψ(θt + λ(θt)) となる。 0.75
s q−α(1−(cid:80)n s q−α(1−(cid:80)n 0.76
(cid:80)t s=1 l(cid:62) (cid:80)t s=1 l(cid:62) 0.74
(cid:80)t 4 (cid:80)t 4 0.85
英語(論文から抽出)日本語訳スコア
Optimization Form 1-step OMD 最適化フォーム 1ステップOMD 0.69
2-step OMD pt+1 = arg min q∈∆n 2ステップOMD pt+1 = arg min q苦情 0.64
˜pt+1 = arg min q∈Rn pt+1 = arg min q∈∆n pt+1=arg min qبrn pt+1=arg min q、15n 0.48
Aggregator OMD pt+1 = arg min q∈∆n Aggregator OMD pt+1 = arg min q苦情 0.75
Fψ(q) + Table 1: OMD Updates fψ(q) + 表1:OMDのアップデート 0.89
(cid:105) (cid:105) (cid:105)(cid:105) 0.74
(cid:104) (cid:104) (cid:34) (cid:104)(cid:104)(c id:34) 0.71
ηtl(cid:62) ηtl(cid:62) BregFψ ηtl(cid:62) ηtl(cid:62) bregfψ 0.65
t q + BregFψ t q + BregF' 0.90
t q + BregFψ (q(cid:107)˜pt+1) t q + BregF' (q(cid:107) >pt+1) 0.74
(q(cid:107)pt) (q(cid:107)pt) (q(cid:107)pt) (q(cid:107)pt) 0.93
(cid:35) ηsl(cid:62) s q (cid:35) ηsl(cid:62) s q 0.80
t(cid:88) s=1 t(cid:88) s=1 0.71
Optimization Form FTRL 最適化フォーム FTRL 0.82
pt+1 = arg min q∈∆n pt+1 = arg min q苦情 0.65
1-step FTRL pt+1 = arg min q∈∆n 1段階のFTRL pt+1 = arg min q苦情 0.58
2-step FTRL ˜pt+1 = arg min q∈Rn pt+1 = arg min q∈∆n 2段階FTRL pt+1=arg min qبrn pt+1=arg min q、15n 0.63
3.4 Regret of OMD and FTRL 3.4 OMD および FTRL の更新 0.78
(cid:34) (cid:104) (cid:104) (cid:34) (cid:104) (cid:104) 0.74
Table 2: FTRL Updates 表2: FTRLのアップデート 0.92
(cid:35) t(cid:88) (cid:35) t(cid:88) 0.81
s=1 l(cid:62) s q s=1 l(cid:62) s q 0.75
Fψ(q) + ηt l(cid:62) t q + Bregηt,ηt−1 F(q) + ηt l(cid:62) t q + Bregηt,ηt−1 0.81
Fψ (q(cid:107)pt) fψ (q(cid:107)pt) 0.82
l(cid:62) t q + Bregηt,ηt−1 (q(cid:107)˜pt+1) BregFψ l(cid:62) t q + Bregηt,ηt−1 (q(cid:107) 0.84
Fψ (q(cid:107)pt) fψ (q(cid:107)pt) 0.82
(cid:105) (cid:105) (cid:105)(cid:105) 0.74
Table 3: Regret Inequalities 表3:Regretの不平等 0.73
t=1 T(cid:88) t (pt − p) l(cid:62) (cid:104) T(cid:88) (cid:104) ≤ T(cid:88) t=1。 T(cid:88) t (pt − p) l(cid:62) (cid:104) T(cid:88) (cid:104) ≤ T(cid:88) 0.65
1 ηt t=1 = 1 ηt t=1。 = 0.73
1 ηt (cid:104) (cid:104) 1 ηt (cid:104)(cid:104) 0.81
t=1 = 1 ηT ≤ 1 ηT t=1。 = 1ηT ≤ 1ηT 0.72
OMD 2-step OMD OMD 2ステップOMD 0.74
FTRL 2-step FTRL FTRL 2段階FTRL 0.81
BregFψ BregFψ ブレグファクトリー ブレグファクトリー 0.37
(p(cid:107)pt) − BregFψ (p(cid:107)pt)- BregF' 0.90
(p(cid:107)pt) − BregFψ (p(cid:107)pt)- BregF' 0.90
(p(cid:107)pt+1) (p(cid:107)pt+1) 0.78
(p(cid:107)pt+1) (p(cid:107)pt+1) 0.78
(cid:105) (cid:105) (cid:105)(cid:105) 0.74
+ + + t=1 + + + t=1。 0.75
T(cid:88) T(cid:88) (cid:104) T(cid:88) (cid:104) T(cid:88) T(cid:88) T(cid:88) (cid:104) T(cid:88) (cid:104) T(cid:88) 0.77
t=1 t=1 + t=1。 t=1。 + 0.59
t=1 (cid:105) (cid:105) t=1。 (cid:105)(cid:105) 0.60
BregFψ BregFψ ブレグファクトリー ブレグファクトリー 0.37
(p(cid:107)p1) − BregFψ (p(cid:107)p1) − BregF' 0.82
(p(cid:107)p1) − BregFψ (p(cid:107)p1) − BregF' 0.82
(p(cid:107)pT +1) (p(cid:107)pT+1) 0.82
(p(cid:107)pT +1) (p(cid:107)pT+1) 0.82
t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) 0.74
Fψ (pt+1(cid:107)pt) fψ (pt+1(cid:107)pt) 0.74
t (pt − ˜pt+1) − Bregηt,ηt−1 l(cid:62) t (pt − spt+1) − Bregηt,ηt−1 l(cid:62) 0.72
Fψ (˜pt+1(cid:107)pt) fψ (pt+1(cid:107)pt) 0.73
The regret of different versions of OMD and FTRL are summarized in Table 3. OMDとFTRLの異なるバージョンの後悔は表3にまとめられている。 0.81
For OMD and FTRL, we are able to show an equality and for the 2-step versions, we get inequalities. OMD と FTRL では等式を示すことができ、2 段階のバージョンでは不等式が得られる。 0.62
The 2-step version’s regret is identical to the 1-step version, except for ˜pt+1 replacing pt+1 in the second term, for both FTRL and OMD. 2段階版の後悔は1段階版と同一であるが、FTRLとOMDの両方で、第2項でpt+1を置き換えている。 0.77
In the second term for OMD, we have a Bregman Divergence, where as in FTRL it is replaced by a Mixed Bregman. OMDの2番目の項では、Bregman Divergenceがあり、FTRLのようにMixed Bregmanに置き換えられる。 0.70
Finally, the first term in OMD’s regret is a sum but in case of FTRL, it is a single term. 最後に、OMDの後悔の最初の項は和であるが、FTRLの場合、1つの項である。 0.65
This is because, we are able to telescope the summation which appears in FTRL’s analysis. これは、FTRLの分析で現れる和を望遠鏡で観測できるためである。
訳抜け防止モード: これは、 我々は、FTRLの分析で現れる和を望遠鏡で観測することができる。
0.76
In OMD, this telescoping does not immediately occur, unless further assumptions about ηt are made. OMDでは、ηtに関するさらなる仮定がなされない限り、このテレスコープはすぐには発生しない。 0.56
5 INF Form θt = θt−1 − ηtlt θt = θt−1 − ηtlt 5 INF形式 θt = θt−1 − ηtlt θt = θt−1 − ηtlt 0.74
pt+1 = ψ(θt + λ(θt)) pt+1 = (θt + λ(θt)) 0.94
˜pt+1 = ψ(θt + λ(θt−1)) pt+1 = ψ(θt + λ(θt)) pt+1 = ψ(θt + λ(θt−1)) pt+1 = ψ(θt + λ(θt)) 0.77
θt = − t(cid:88) θt = − t(cid:88) 0.86
ηsls pt+1 = ψ(θt + λ(θt)) ηsls pt+1 = (θt + λ(θt)) 0.86
s=1 INF Form θt = −ηt s=1 INF Form θt = −ηt 0.69
t(cid:88) s=1 t(cid:88) s=1 0.71
ls pt+1 = ψ(θt + λ(θt)) ls pt+1 = (θt + λ(θt)) 0.89
θt−1 − ηtlt θt−1 − ηtlt 0.59
θt = θt = ηt ηt−1 θt = θt = ηt−1 0.81
ηt ηt−1 pt+1 = ψ(θt + λ(θt)) ηt−1 pt+1 = (θt + λ(θt)) 0.81
θt−1 − ηtlt θt−1 − ηtlt 0.59
˜pt+1 = ψ(θt + t + = θt + である。 0.55
ηt ηt−1 λ(θt−1)) ηt−1 λ(θt−1) 0.77
pt+1 = ψ(θt + λ(θt)) pt+1 = (θt + λ(θt)) 0.94
(cid:20) (cid:20) (cid:20)(cid:20) 0.73
t (pt − pt+1) − 1 l(cid:62) ηt t (pt − ˜pt+1) − 1 l(cid:62) ηt t (pt − pt+1) − 1 l (cid:62) ηt t (pt − シュプ+1) − 1 l (cid:62) ηt 0.85
BregFψ BregFψ ブレグファクトリー ブレグファクトリー 0.37
(pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.78
(˜pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.75
(cid:21) (cid:21) (cid:21)(cid:21) 0.73
(cid:105) (cid:105) (cid:105)(cid:105) 0.74
英語(論文から抽出)日本語訳スコア
We prove FTRL’s result here as it is used in Section 4. ここではFTRLの結果が第4節で使われていることを証明している。 0.68
The other regret results are in the Appendix. その他の残念な結果はAppendixにある。 0.79
Theorem 8. For any p ∈ ∆n and any sequence of losses l1, . 理論8。 任意の p ∈ sn と損失の列 l1, に対して。 0.68
. . , lT , the iterates of FTRL satisfy the . . , lT, FTRLの繰り返しが満たされる。 0.83
regret equality(cid:80)T 後悔の平等 (cid:80)T 0.71
t=1 l(cid:62) t=1 l(cid:62) 0.71
t (pt − p) t (pt − p) 0.85
(cid:104) = (cid:104) = 0.82
1 ηT BregFψ 1ηT ブレグファクトリー 0.60
(p(cid:107)p1) − BregFψ (p(cid:107)p1) − BregF' 0.82
(cid:105) (p(cid:107)pT +1) (cid:105) (p(cid:107)pT+1) 0.80
T(cid:88) (cid:104) t(cid:88) (cid:104) 0.79
t=1 + t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) t=1。 + t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) 0.68
Fψ (pt+1(cid:107)pt) fψ (pt+1(cid:107)pt) 0.74
(cid:105) Proof. (cid:105) 証明。 0.70
Note that ∇Fψ(pt+1) = ψ−1(pt+1) = θt + λ(θt). 注意すべき点として、sf(pt+1) = t−1(pt+1) = θt + λ(θt) である。 0.57
For any p ∈ ∆n, we have : 任意の p ∈ (n) に対して、 0.48
t (pt − p) = l(cid:62) l(cid:62) t (pt − p) = l(cid:62) l(cid:62) 0.94
t (pt+1 − p) + l(cid:62) t (pt+1 − p) + l(cid:62) 0.88
(cid:18)∇Fψ(pt) − λ(θt−1) (cid:18)∇Fψ(pt) ηt−1 − ∇Fψ(pt+1) (cid:18)-fψ(pt) − λ(θt−1) (cid:18)-fψ(pt) ηt−1--fψ(pt+1) 0.72
− θt t (pt − pt+1) = ηt − ∇Fψ(pt+1) − λ(θt) (cid:19)(cid:62) θt t (pt − pt+1) = ηt − λ(θt) (cid:19)(cid:62) 0.86
(pt+1 − p) + l(cid:62) (pt+1 − p) + l(cid:62) 0.86
ηt−1 ηt = = ηt−1 ηt = = 0.74
ηt−1 ηt t (pt − pt+1) ηt−1 ηt t (pt − pt+1) 0.72
(pt+1 − p) + l(cid:62) (pt+1 − p) + l(cid:62) 0.86
t (pt − pt+1) t (pt − pt+1) 0.92
(pt+1 − p) + l(cid:62) (pt+1 − p) + l(cid:62) 0.86
t (pt − pt+1) t (pt − pt+1) 0.92
(cid:18) θt−1 (cid:18)θt−1 0.57
(cid:19)(cid:62) (cid:19)(cid:62) (cid:19)(cid:62)(cid :19)(cid:62) 0.73
Let α be any number. α を任意の数とする。 0.77
The first term above is equal to: 上記の第1項は以下のとおりである。 0.60
Bregα,ηt−1 Bregα,ηt−1 0.59
Fψ (p(cid:107)pt) − Bregα,ηt fψ (p(cid:107)pt) − Bregα,ηt 0.79
Fψ (p(cid:107)pt+1) − Bregηt,ηt−1 fψ (p(cid:107)pt+1) − Bregηt,ηt−1 0.69
Fψ (pt+1(cid:107)pt) fψ (pt+1(cid:107)pt) 0.74
Taking summation over t, we have: t 上の和をとると、次のようになる。 0.28
T(cid:88) T(cid:88) t(cid:88) t(cid:88) 0.80
(cid:104) t (pt − p) = l(cid:62) (cid:104) t (pt − p) = l(cid:62) 0.89
Bregα,ηt−1 Bregα,ηt−1 0.59
Fψ (p(cid:107)pt) − Bregα,ηt fψ (p(cid:107)pt) − Bregα,ηt 0.79
Fψ (p(cid:107)pt+1) fψ (p(cid:107)pt+1) 0.74
t=1 t=1 = Bregα,η0 Fψ t=1。 t=1。 =Bregα,η0 0.59
(p(cid:107)p1) − Bregα,ηT (p(cid:107)p1) − Bregα,ηT 0.83
Fψ (p(cid:107)pT +1) + fψ (p(cid:107)pT +1) + 0.80
Since p1 = (1/n, . p1 = (1/n, 。 0.81
. . , 1/n), we see that: . . , 1/n)です。 0.73
Bregα,η0 Fψ (p(cid:107)p1) − Bregα,ηT Bregα,η0 (p(cid:107)p1) − Bregα,ηT 0.88
Fψ (p(cid:107)pT +1) = fψ (p(cid:107)pT +1) = 0.80
(cid:104) 1 ηT (cid:104) 1ηT 0.81
BregFψ (cid:105) T(cid:88) ブレグファクトリー (cid:105)t(cid:88) 0.56
t=1 + (cid:104) t=1。 + (cid:104) 0.70
T(cid:88) (cid:104) t(cid:88) (cid:104) 0.79
t=1 t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) t=1。 t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) 0.60
Fψ (cid:105) fψ (cid:105) 0.74
(pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.78
(cid:105) (pt+1(cid:107)pt) (cid:105) (pt+1(cid:107)pt) 0.78
t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) (cid:105) t (pt − pt+1) − Bregηt,ηt−1 l(cid:62) (cid:105) 0.73
Fψ (p(cid:107)p1) − BregFψ fψ (p(cid:107)p1) − BregF' 0.76
(p(cid:107)pT +1) (p(cid:107)pT+1) 0.82
(cid:4) 3.5 Local-Norm Lower-Bounds for Bregman Divergences Let ψ be a potential and x, y ∈ R+. (cid:4) 3.5 のブレグマンダイバージェンスに対する局所ノルム下界 をポテンシャルと x, y ∈ R+ とする。 0.76
For scalar l and positive η, consider the expression sscalar l および positive η について、式を考える 0.71
Suppose we have the lower bound Bregfψ (y(cid:107)x) ≤ l(x − y) − l(x − y) − 1 η 下限bregfψ (y(cid:107)x) ≤ l(x − y) − l(x − y) − 1 η とする。 0.80
Bregfψ 1 2ηw(x) Bregfō 1 2ηw(x) 0.79
(y(cid:107)x) ≥ 1 (y(cid:107)x) ≥ 1 0.98
l(x − y) − 1 η l(x − y) − 1 η 0.85
(y(cid:107)x) (y(cid:107)x) 0.94
Bregfψ 2w(x) (x − y)2, for some function w. Then: (x − y)2 ≤ sup s∈Rn bregfψ 2w(x) (x − y)2, ある函数 w に対して: (x − y)2 ≤ sup s ≤rn 0.91
2ηw(x) ls − 2ηw(x) ls − 0.85
(cid:20) (cid:21) (cid:20) (cid:21) 0.78
η 2 s2 = 1 η 2 s2 = 1 0.83
w(x)l2 We show a general way of obtaining such lower bounds using potential functions. w(x)l2 ポテンシャル関数を用いてそのような下界を得る一般的な方法を示す。 0.83
Lemma 9. Let ψ be a potential and x ∈ R+ such that x = ψ(u) for some u. 第9回。 ψ をポテンシャルとし、x ∈ r+ をある u に対して x = ψ(u) とする。 0.70
Let φ be a nonnegative function such that ψ(u + φ(u)) exists. φ を φ(u + φ(u)) が存在するような非負函数とする。 0.88
Define the function m(z) = ψ(z+φ(z))−ψ(z) . 関数 m(z) = ψ(z+φ(z))−ψ(z) を定義する。 0.87
For all 0 ≤ y ≤ ψ(u + φ(u)) we have the lower bound: Bregfψ すべての 0 ≤ y ≤ ψ(u + φ(u)) に対し、下界はbregfψ である。 0.81
(y(cid:107)x) ≥ 1 (y(cid:107)x) ≥ 1 0.98
m(ψ−1(x)) (x−y)2 m(ψ−1(x)) (x−y)2 0.89
φ(z) 2 6 φ(z) 2 6 0.85
英語(論文から抽出)日本語訳スコア
Figure 2: v ≤ u 図 2: v ≤ u 0.82
Figure 3: u ≤ v ≤ u + φ(u) 図3: u ≤ v ≤ u + φ(u) 0.82
Proof. Let v be such that y = ψ(v). 証明。 v を y = ψ(v) とする。 0.65
Using Lemma 7, we have Bregfψ the fact that f (cid:63) Lemma 7 を用いて、f が (cid:63) であるという事実を Bregf\ とする。 0.59
ψ(u) =(cid:82) ψ(u)du, we have: シュ(u) =(cid:82) シュ(u)du, we have: 0.74
Bregf (cid:63) Bregf (複数形 Bregfs) 0.44
ψ (u(cid:107)v) = f (cid:63) ψ (u(cid:107)v) = f(cid:63) 0.87
ψ(u) − f (cid:63) ψ(u) − f (cid:63) 0.98
ψ(v) − f (cid:63) ψ(v) − f (cid:63) 0.98
ψ (cid:48) ψ (cid:48) 0.82
(v)(u − v) = (v)(u − v) = 0.85
(y(cid:107)x) = Bregf (cid:63) (y(cid:107)x) = Bregf (cid:63) 0.90
ψ (u(cid:107)v). ψ (u(cid:107)v)。 0.86
Using ψ(s) − y(u − v) 利用 ψ(s) − y(u − v) 0.80
(cid:90) u v (cid:90)u v 0.80
ψ (u(cid:107)v) using the potential function. ψ (u(cid:107)v)ポテンシャル関数を用いる。 0.85
When v ≤ u, it is the area with green v ≤ u の場合、緑のある領域である。 0.79
We can visualize Bregf (cid:63) borders in Figure 2 and when u ≤ v, it is the area with green borders in Figure 3. 図2で Bregf (cid:63) 境界を視覚化することができ、u ≤ v の場合、図3で緑色の境界を持つ領域となる。 0.76
Consider the line passing through (u, x) and (u + φ(u), ψ(u + φ(u)). (u, x) と (u + φ(u) を通り抜ける直線を考えると、(u + φ(u)) は (u + φ(u)) となる。 0.74
Its slope is m(u) ≥ ψ(cid:48)(u) > 0. 斜面は m(u) ≥ ψ(cid:48)(u) > 0 である。 0.79
In both cases, the height of the red triangle is |x − y| and its base is |x−y| m(u) . どちらの場合も、赤三角形の高さは |x − y| であり、その基底は |x −y| m(u) である。 0.68
So, the area of the red (x−y)2 (u(cid:107)v), we have the lower triangle will be 1 m(u) . したがって、赤 (x−y)2 (u(cid:107)v) の面積は、下方三角形が 1 m(u) となる。 0.79
Since the triangle is always smaller than Bregf (cid:63) 2 (y(cid:107)x) ≥ 1 (cid:4) bound Bregfψ 三角形は常に Bregf (cid:63) 2 (y(cid:107)x) ≥ 1 (cid:4) より小さいからである。 0.81
m(ψ−1(x)) (x−y)2 m(ψ−1(x)) (x−y)2 0.89
2 ψ 4 Proof of Theorem 1 Consider the potential function ψ(u) = −1 2 ψ 4 定理 1 の証明は、ポテンシャル函数 (u) = −1 を考える。 0.84
u restricted to the domain (−∞, 0). u は領域 (−∞, 0) に制限される。 0.69
Its associated function i=1[fψ(x(i) − fψ(1/n)]. その関連関数 i=1[fψ(x(i) − fψ(1/n)] である。 0.81
Since the algorithm does FTRL updates with loss sequence ˜l1, . アルゴリズムは、損失シーケンス ~l1 で FTRL を更新する。 0.80
. . , ˜lT and learning rate sequence (cid:105) . . , slT, 学習速度 (cid:105) 0.79
fψ(x) = − log(x). fψ(x) = − log(x) である。 0.91
The regularizer used in Algorithm 1 is Fψ(x) = (cid:80)n η0, . アルゴリズム1で使われる正則化器は、 (cid:80)n η0, である。 0.75
. . , ηT , we use Theorem 8. . . ηT, Theorem 8 を使用します。 0.85
For any p ∈ ∆n we have(cid:80)T (cid:104)˜l(cid:62) t (pt − pt+1) − Bregηt,ηt−1 (cid:105) p ∈ >n に対して (cid:80)T (cid:104) >l(cid:62) t (pt − pt+1) − Bregηt,ηt−1 (cid:105) となる。 0.68
(p(cid:107)p1) − BregFψ T(cid:88) (p(cid:107)p1) − BregF' T(cid:88) 0.81
t (pt − p) is ˜l(cid:62) t (pt − p) はエル (cid:62) 0.84
(pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.78
(p(cid:107)pT +1) (p(cid:107)pT+1) 0.82
T(cid:88) BregFψ t(cid:88) ブレグファクトリー 0.59
1 ηT (cid:104) 1ηT (cid:104) 0.81
(cid:105) t=1 (cid:105) t=1。 0.62
t=1 + = Fψ t=1。 + = fψ 0.72
t (pt − pt+1) − Bregηt,ηt−1 t (pt − pt+1) − Bregηt,ηt−1 0.72
Fψ (pt+1(cid:107)pt) fψ (pt+1(cid:107)pt) 0.74
(cid:104)˜l(cid:62) (cid:104)(cid:62) 0.81
≤ Fψ(p) ηT ≤ F (p) ηT 0.94
+ t=1 As Fψ(pt+1) ≥ 0 and ηt are non-increasing we have Bregηt,ηt−1 + t=1。 fψ(pt+1) ≥ 0 と ηt は非増大であるため、bregηt,ηt−1 を持つ。 0.62
Fψ (pt+1(cid:107)pt) ≥ 1 fψ (pt+1(cid:107)pt) ≥ 1 0.77
ηt−1 BregFψ ηt−1 ブレグファクトリー 0.42
(pt+1(cid:107)pt). (pt+1(cid:107)pt) 0.82
T(cid:88) t=1 t(cid:88) t=1。 0.63
(cid:20) T(cid:88) (cid:20) t(cid:88) 0.79
t=1 t (pt − p) ≤ Fψ(p) ˜l(cid:62) ηT t=1。 t (pt − p) ≤ fψ(p) sl(cid:62) ηt 0.69
+ t (pt − pt+1) − 1 ˜l(cid:62) ηt−1 + t (pt − pt+1) − 1 シュル(cid:62) ηt−1 0.81
BregFψ (pt+1(cid:107)pt) ブレグファクトリー (pt+1(cid:107)pt) 0.58
Let φ(u) = ψ−1(1) − u and apply Lemma 9. φ(u) = φ−1(1) − u とし、Lemma 9 を適用する。 0.80
The slope m(u) will be: 傾斜m(u)は次のようになる。 0.61
m(u) = ψ(u + φ(u)) − ψ(u) m(u) = ψ(u + φ(u)) − ψ(u) 0.85
φ(u) = ψ(u + ψ−1(1) − u) − ψ(u) φ(u) = ψ(u + ψ−1(1) − u) − ψ(u) 0.88
φ(u) 7 = 1 + 1 u−1 − u φ(u) 7 = 1 + 1 u−1 − u 0.87
= −1 u = ψ(u) = −1u =ψ(u) 0.78
(cid:21) (cid:21) 0.78
英語(論文から抽出)日本語訳スコア
Thus, we have the lowerbound: (pt+1(cid:107)pt) = したがって、下界: (pt+1(cid:107)pt) = 0.78
Bregfψ Using the lowerbound, we get all p ∈ ∆n: ηt−1 bregfψ 下限を用いて、すべての p ∈ ηn: ηt−1 を得る。 0.58
T(cid:88) BregFψ t(cid:88) ブレグファクトリー 0.59
n(cid:88) T(cid:88) n(cid:88) T(cid:88) 0.81
i=1 t (pt − p) ≤ Fψ(p) ˜l(cid:62) ηT i=1 t (pt − p) ≤ fψ(p) sl(cid:62) ηt 0.75
+ (pt+1(i)(cid:107)pt(i)) ≥ n(cid:88) n(cid:88) + (pt+1(i)(cid:107)pt(i)) ≥ n(cid:88) n(cid:88) 0.86
Fψ(p) i=1 pt(i)˜lt(i)2 = fψ(p) i=1 pt(i) はlt(i)2 = 0.80
1 2 T(cid:88) 1 2 t(cid:88) 0.83
t=1 p(cid:48) t(it)2 For any given p ∈ ∆n, let p = (1 − )p + /n. t=1。 p(cid:48) t(it)2 は任意の p ∈ sn に対して、p を (1 − s)p + s/n とする。 0.65
In Algorithm 1, since we sample from p(cid:48) step, we have: アルゴリズム1では、p(cid:48)ステップからサンプルを取ります。 0.67
ηT t=1 t=1 ηT t=1。 t=1。 0.57
i=1 2 2 + (*) i=1 2 2 + (*) 0.80
t at each ηt−1 それぞれt ηt−1 0.49
pt(it)lt(it)2 pt(it)lt(it)2 0.85
(pt+1(i) − pt(i))2 (pt+1(i) − pt(i))2 0.98
pt(i) ˜l(cid:62) t (p(cid:48) pt(i) l(cid:62) t (p(cid:48) 0.84
t − p) = T(cid:88) (cid:124) t − p) = T(cid:88)(124) 0.83
t=1 t (pt − p) ˜l(cid:62) (cid:123)(cid:122) (cid:125) t=1。 t (pt − p ) (cid:62) (cid:123) (cid:122) (cid:125) 0.66
+ T(cid:88) + t(cid:88) 0.83
t (p − p) + ˜l(cid:62) t (p] − p) + sl(cid:62) 0.86
t=1 For term (1), we use inequality (*) and simplify. t=1。 項(1)では、不等式(*)を用いて単純化する。 0.54
We have(cid:80)T (cid:32) 我々は(cid:80)t (cid:32) 0.80
t(it)2 ≤ Fψ(p) p(cid:48) T(cid:88) t(it)2 ≤ F(p)p(cid:48)T(cid:8 8) 0.94
≤ Fψ(p) pt(it)lt(it)2 ≤ F (p) pt(it)lt(it)2 0.82
T(cid:88) Fψ(p) t(cid:88) F (複数形 Fs) 0.71
ηt−1 ηT ηT ηt−1 ηT ηT 0.68
t=1 t=1 + t=1。 t=1。 + 0.59
+ (1) 2 t=1 ηt−1 + (1) 2 t=1 ηt−1 0.75
2(1 − γt−1) 2(1 − γt−1) 0.82
t=1 T(cid:88) t − pt) t (p(cid:48) ˜l(cid:62) (cid:123)(cid:122) (cid:125) (cid:124) t (pt − p) ˜l(cid:62) lt(it)2 (cid:33)−1/2 p(cid:48) t−1(cid:88) t(it) t=1。 t(cid:88) t − pt) t (p(cid:48) sl(cid:62) (cid:123)(cid:122) (cid:125) (cid:124) t (pt − p) sl(cid:62) lt(it)2 (cid:33)−1/2 p(cid:48) t−1(cid:88) t(it) 0.63
(2) + t=1 (2) + t=1。 0.72
lt(it)2 p(cid:48) t(it) lt(it)2 p(cid:48) t(it) 0.97
1 + s=1 ls(is)2 p(cid:48) t(it) 1 + s=1 ls(is)2 p(cid:48) t(it) 0.80
(Use Lemma 17) (**) (ルムマ17号) (**) 0.72
(As 2(1 − γt−1) ≥ 1) (2(1 − γt−1) ≥ 1) 0.94
T(cid:88) t=1 t(cid:88) t=1。 0.63
T(cid:88) T(cid:88) (cid:32) T(cid:88)T(cid:88)(c id:32) 0.78
lt(it)2 p(cid:48) t(it) lt(it)2 p(cid:48) t(it) 0.97
+ max t lt(it)2 p(cid:48) t(it) +max t lt(it)2 p(cid:48) t(it) 0.85
≤ Fψ(p) + 4 f ≤(p ) + 4 である。 0.82
ηT + n max ηT + n の最大値 0.73
t lt(it)2 γt−1 t lt(it)2 γt−1 0.84
ηt−1 lt(it)2 p(cid:48) t(it) ηt−1 lt(it)2 p(cid:48) t(it) 0.72
= ηT (cid:33)1/2 = ηT (cid:33)1/2 0.76
≤ Fψ(p) + t=1 ≤ F (p) + t=1。 0.70
ηT ≤ Fψ(p) ηT ≤ F (p) 0.79
T(cid:88) For term (2), we have(cid:80)T T(cid:88) (2), we have (cid:80)T 0.85
≤ Fψ(p) + 4 f ≤(p ) + 4 である。 0.82
t=1 nL2∞ γT t=1 nL2∞ γT 0.52
+ 4 1 + ηT + 4 1 + ηT 0.83
ηT + = T(cid:88) ≤ T(cid:88) (cid:32) ηT + = T(cid:88) ≤ T(cid:88) (cid:32) 0.82
t=1 t=1 ≤ 2 t=1。 t=1。 ≤ 2 0.59
lt(it) p(cid:48) t(it) lt(it) p(cid:48) t(it) 0.98
γt−1 t=1 ˜l(cid:62) t (p(cid:48) γt−1 t=1。 l(cid:62) t (p(cid:48) 0.59
t − pt): T(cid:88) t(it) − pt(it)) = (p(cid:48) T(cid:88) (cid:33)1/2 t − pt): T(cid:88) t(it) − pt(it)) = (p(cid:48) T(cid:88) (cid:33)1/2 0.91
lt(it) p(cid:48) t(it) | lt(it) | p(cid:48) t(it) lt(it) p(cid:48) t(it) | lt(it) | p(cid:48) t(it) 0.98
(cid:32) 1 2 (cid:32) 1 2 0.82
t=1 t=1 = t=1。 t=1。 = 0.59
| lt(it) | p(cid:48) t(it) | lt(it) | p(cid:48) t(it) | lt(it) | p(cid:48) t(it) | lt(it) | p(cid:48) t(it) 0.97
T(cid:88) 1 2 t(cid:88) 1 2 0.83
(cid:18) 1 t−1(cid:88) (cid:18) 1 t−1(cid:88) 0.71
γt−1 (cid:19) (cid:33)−1/2 γt−1 (cid:19) (cid:33)−1/2 0.55
− pt(it) n | ls(is) | p(cid:48) t(it) -pt(it) n | ls(is) | p(cid:48) t(it) 0.77
1 + s=1 t=1 lt(i). 1 + s=1 t=1 lt(i) である。 0.71
Let ei(cid:63) be the vector with ei(cid:63) をベクトルとする 0.84
| lt(it) | γt−1 | lt(it) | γt−1 0.86
| lt(it) | p(cid:48) t(it) | lt(it) | p(cid:48) t(it) 0.96
≤ 1 γT n 2 ≤ 2 + nL∞ ≤ 1 γT n2 ≤ 2 + nL∞ 0.89
t t + + t=1 t t + + t=1。 0.77
t=1 1 + max t=1。 1 + マックス 0.67
max (cid:34) T(cid:88) マックス (cid:34)T(cid:88) 0.74
lt(it) − lt(i(cid:63)) lt(it) − lt(i(cid:63)) 0.98
(cid:80)T (cid:35) (cid:34) T(cid:88) Suppose the best arm in hindsight is i(cid:63) = arg mini∈[n] ei(cid:63) (i(cid:63)) = 1 and ei(cid:63) (i) = 0 for all i (cid:54)= i(cid:63). (cid:80)T (cid:35) (cid:34) T(cid:88) 後ろ向きのベストアームは i(cid:63) = arg mini・[n] ei(cid:63) (i(cid:63)) = 1 と ei(cid:63) (i) = 0 for all i (cid:54)= i(cid:63) とする。 0.85
The expected regret of Algorithm 1 is: t − ei(cid:63) ) RT = E +(cid:0)2nL2∞ + nL∞ + 2(cid:1) E (cid:21)(cid:33)1/2 (cid:20) lt(it)2 T(cid:88) (cid:112) (cid:21)(cid:33)1/2 (cid:20)| lt(it) | T(cid:88) t − ei(cid:63) ) RT = E +(cid:0)2nL2∞ + nL∞ + 2(cid:1) E (cid:21)(cid:33)1/2 (cid:20) lt(it)2 T(cid:88) (cid:112) (cid:21)(cid:33)1/2 (cid:20)| lt(it) | T(cid:88) 0.81
(cid:20) 1 (cid:21) (cid:33)1/2 ≤ (cid:32)  ) ≤ n log(1/). (cid:20) 1 (cid:21) (cid:33)1/2 ≤ (cid:32) s ) ≤ n log(1/)。 0.79
Using Jensen’s inequality: (cid:33)1/2 ≤ (cid:32) Jensenの不等式を使う: (cid:33)1/2 ≤ (cid:32) 0.70
(cid:35) (cid:35)  − ei(cid:63) ) T(cid:88) T(cid:88) (cid:35) (cid:35) - ei(cid:63) ) t(cid:88) t(cid:88) 0.81
(cid:34) T(cid:88) (cid:34) T(cid:88) (cid:21) (cid:20) 1 (cid:21) (cid:20) 1 (cid:34) T(cid:88) (cid:34) T(cid:88) (cid:21) (cid:20) 1 (cid:21) (cid:20) 1 0.76
(cid:35) t − ei(cid:63) ) (cid:21) (cid:35) t − ei(cid:63) ) (cid:21) 0.82
The first term can be bounded as 2S∞ and Fψ(ei(cid:63) 第一項は 2 対∞ と fψ(ei(cid:63)) で有界である。 0.54
(cid:32) (cid:32) 〜(cid:32)〜(cid:32) 0.56
(cid:20) 1  ) + 4)E (cid:20)1 e) + 4 である。 0.80
+ (Fψ(ei(cid:63) +(F)(cid:63) 0.87
˜l(cid:62) t (ei(cid:63) l(cid:62) t (ei(cid:63) 0.81
p(cid:48) t(it) p(cid:48) t(it) 0.96
˜l(cid:62) t (p(cid:48) l(cid:62) t (p(cid:48) 0.83
l(cid:62) t (p(cid:48) l(cid:62) t (p(cid:48) 0.86
(cid:112) 1 + L1 (cid:112) 1 + L1 0.86
1 + L2 ≤ E = E 1 + L2 ≤E =E 0.82
= E = E = E 2γT =E =E =E 2γT 0.69
2γT 1 + 1 + 2γT 1 + 1 + 0.76
1 + 1 + ηT 1 + 1 + ηT 0.83
ηT t=1 t=1 ηT t=1。 t=1。 0.57
t=1 t=1 t=1 t=1。 t=1。 t=1。 0.46
E E E E = = E E E E = = 0.85
lt(it)2 p(cid:48) t(it) | lt(it) | p(cid:48) t(it) lt(it)2 p(cid:48) t(it) | lt(it) | p(cid:48) t(it) 0.97
p(cid:48) t(it) p(cid:48) t(it) 0.96
2γT t=1 (Applying (**)) 2γT t=1。 (※) 0.45
(Use Lemma 17) t=1 (ルムマ17号) t=1。 0.53
8 8 0.85
英語(論文から抽出)日本語訳スコア
Let  = (1 + S∞)−1, we get: 1 + S∞)−1 とすると、次のようになる。 0.71
RT ≤ 2S∞ + (n log(1/) + 4) ≤ 2 + [n log(1 + S∞) + 4] rt ≤ 2/s∞ + (n log(1/i) + 4) ≤ 2 + [n log(1 + s∞) + 4] 0.94
(cid:112) 1 + L2 +(cid:0)2nL2∞ + nL∞ + 2(cid:1)(cid:112) (cid:112) 1 + L2 +(cid:0)2nL2∞ + nL∞ + 2(cid:1)(cid:112) (cid:112) 1 + L2 +(cid:0)2nL2∞ + nL∞ + 2(cid:112) (cid:112) 1 + L2 +(cid:0)2nL2∞ + nL∞ + 2(cid:112) 0.85
1 + L1 1 + L1 1 + L1 1 + L1 0.94
5 Discussion √ √ The regret bound stated in Theorem 1 is scale-free as the algorithm only knows n and the bound holds for any sequence of loss vectors. 5 討論 √ 定理 1 で述べられている後悔の束縛は、アルゴリズムが n のみを知っていて損失ベクトル列の束縛しか持たないので、スケールフリーである。 0.72
If one knows L∞ ≤ G in advance, the regret is Θ(G nT ) using POLY-INF [2]. 前もって L∞ ≤ G を知っていれば、その後悔は POLY-INF [2] を用いて (G nT ) となる。 0.70
Without knowing G, our algorithm implies a regret bound of O(nG log(GT ) nT + nT ). G を知らなければ、我々のアルゴリズムは O(nG log(GT ) nT + nT ) の遺言境界を意味する。 0.80
Thus the price of scale-freeness in MAB is at most O(nG3/2 + n log(GT )). したがって、MAB のスケールフリーネスの価格は、最大 O(nG3/2 + n log(GT )) である。 0.75
Either the nG5/2 the scale-free MAB regret bound is improvable or there exists a lower-bound showing that it is not. nG5/2 のスケールのない MAB 後悔境界は即効可能であるか、そうでないことを示す下界が存在するかのいずれかである。 0.59
Both these questions remain open. これらの疑問はどちらも未解決のままである。 0.35
From an algorithmic standpoint, we conjecture that this bound may not be improvable. アルゴリズムの観点から、我々はこの境界は即効的でないかもしれないと推測する。 0.59
In MAB literature, the three most common choices of regularizer are x log(x) − x,− log(x) and the form(cid:80)n −√ x. MAB文学において、正則化の最も一般的な3つの選択は、x log(x) − x, − log(x) と (cid:80)n − = x である。 0.79
In order to bound the regret with importance weighted estimator, the second term has to be of ˜lt(i)2pt(i)s for some s ≥ 1. 重要重み付き推定子と後悔を結び付けるために、第二項は、ある s ≥ 1 に対して s(i)2pt(i)s でなければならない。 0.71
In the table below, the first row represents prior results with different regularizers. 以下の表では、最初の行は異なる正規化子で前の結果を表す。 0.64
These results hold when ˜lt ≥ 0. これらの結果は、slt ≥ 0 であるときに成立する。 0.47
Due to the scale-free requirement, we need this to hold for ˜lt ∈ Rn. スケールフリーな要求のため、このことはエルト ∈ Rn に対して成り立つ必要がある。 0.66
Using Lemma 9 with φ(u) = ψ−1(1) − u gives the second row for different regularizers. φ(u) = φ−1(1) − u で Lemma 9 を使用すると、異なる正則化子に対する2番目の行が得られる。 0.66
Thus, − log(x) is possibly the only suitable regularizer for this application. したがって − log(x) は、おそらくこのアプリケーションに適した正規化子である。 0.79
√ i=1 f (x) = x log(x) − x √ i=1 f (x) = x log(x) − x 0.76
˜lt ≥ 0 (cid:80)n ˜lt ∈ Rn (cid:80)n 0 (cid:80)n)n (cid:80)n) である。 0.72
i=1 i=1 ˜lt(i)2pt(i) ˜lt(i)2 pt(i)−1 i=1 i=1 ~lt(i)2pt(i) ~lt(i)2pt(i)−1 0.68
log pt(i) − log(x) log pt(i) - log(x) 0.83
(cid:80)n (cid:80)n (cid:80)n (cid:80)n 0.81
i=1 i=1 −√ ˜lt(i)2pt(i)2 (cid:80)n ˜lt(i)2pt(i) (cid:80)n i=1 i=1 − > (i) 2pt(i)2 (cid:80)n > (i)2pt(i) (cid:80)n 0.69
x i=1 i=1 ˜lt(i)2pt(i)3/2 ˜lt(i)2pt(i)1/2 x i=1 i=1 ジルト(i)2pt(i)3/2 ジルト(i)2pt(i)1/2 0.68
(p(cid:107)pt)/ηT , which With a non-increasing ηt, the first term in OMD’s regret is at most maxt BregFψ could be unbounded. (p(cid:107)pt)/ηT で、非増加のηt では、OMDの後悔の最初の項は、少なくともBregF は無界である可能性がある。 0.62
So, we use FTRL, where the first term is at most F (p)/ηT . したがって、FTRL を使い、最初の項は F (p)/ηT である。 0.75
But the second term in FTRL is tricky to bound due to there being a ηt−1. しかし、FTRL の第二項は ηt−1 が存在するため、束縛されにくい。 0.72
For this we had to inject exploration through γt−1 and use Lemma 17. そのため、γt−1による探索を注入し、Lemma 17を使用する必要があった。 0.49
Ideally, if we had a regret inequality where the first term is F (p)/ηT and second term has ηt, then we can get scale-free regret without injecting exploration. 理想的には、第一項が f (p)/ηt で第二項が ηt であるような後悔の不平等があった場合、探索を使わずにスケールフリーの後悔が得られる。 0.58
Here we use (cid:16) ここで使うもの (cid:16) 0.77
1 +(cid:80)t 1 +(cid:80)t 0.92
√ ηt = n (cid:17)−1/2 √ ηt = n (cid:17)−1/2 0.79
s=1 ls(is)2 ps(is) s=1 ls(is)2 ps(is) 0.72
(cid:34) 2S∞ + E (cid:34) 2-S∞ + E 0.71
n log(1/) ηT n log(1/) ηT 0.88
+ ηt lt(it)2 pt(it) + ηt lt(it)2 pt(it) 0.83
T(cid:88) t=1 t(cid:88) t=1。 0.63
and bound the sum using Lemma 18. Lemma 18を使って和を束縛する。 0.69
√ ≤ 2 + n(log(1 + S∞) + 2) √ ≤ 2 + n(log(1 + S∞) + 2) 0.87
(cid:112) 1 + L2 (cid:112) 1 + L2 0.86
First Term OMD maxt BregFψ FTRL F (p)/ηT Ideal F (p)/ηT 第一期 OMD maxt BregF' FTRL F (p)/ηT Ideal F (p)/ηT 0.73
(p(cid:107)pt)/ηT (p(cid:107)pt)/ηT 0.81
Second Term (cid:80)T (cid:80)T (cid:80)T 第二項 (cid:80)T (cid:80)T (cid:80)T 0.74
(cid:80)n (cid:80)n (cid:80)n (cid:80)n (cid:80)n (cid:80)n 0.80
i=1 i=1 t=1 ηt t=1 ηt−1 t=1 ηt i=1 i=1 t=1 ηt t=1 ηt−1 t=1 ηt 0.54
˜lt(i)2pt(i) ~lt(i)2pt(i) 0.87
˜lt(i)2pt(i) ~lt(i)2pt(i) 0.87
i=1 ˜lt(i)2pt(i) i=1:lt(i)2pt(i) 0.82
√ n log(GT )). √ n log(gt ) である。 0.83
However, such an ideal regret In the ideal case, the price of scale-freeness is O( inequality seems unlikely. しかし、理想的な場合、スケールフリーネスの価格はo(不等式)であるような理想的な後悔はありそうにない。 0.62
In FTRL, the first term is favourable and the second term is not ideal, but it is still controllable. FTRLでは、第一項は好ましく、第二項は理想的ではないが、制御可能である。 0.76
In OMD, the first term is unbounded and the second term is favourable. OMDでは、第一項は非有界であり、第二項は好ましい。 0.62
This is summarized in the table above. これは上記の表にまとめられている。 0.77
Thus FTRL seems to be the only choice to get a scale-free regret bound for bandits. したがって、FTRLは盗賊に無スケールの後悔を与える唯一の選択肢である。 0.73
(cid:35) 9 (cid:35) 9 0.82
英語(論文から抽出)日本語訳スコア
References [1] C. Allenberg, P. Auer, L. Györfi, and G. Ottucsák. 参考文献[1] c. allenberg, p. auer, l. györfi, g. ottucsák 0.81
Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. 部分的監視下での無制限損失の場合のオンライン学習におけるhannan一貫性 0.59
In J. L. Balcázar, P. M. Long, and F. Stephan, editors, Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006, Proceedings, volume 4264 of Lecture Notes in Computer Science, pages 229–243. J. L. Balcázar, P. M. Long, F. Stephan, editors, Algorithmic Learning Theory, 17th International Conference, ALT 2006 Barcelona, Spain, October 7-10, 2006, Proceedings, volume 4264 of Lecture Notes in Computer Science, page 229–243. 0.96
Springer, 2006. doi: 10.1007/11894841\_20 . Springer, 2006. doi: 10.1007/11894841\_20 。 0.61
URL https://doi.org/10.1 007/11894841_20. URL https://doi.org/10.1 007/11894841_20。 0.39
[2] J. Audibert and S. Bubeck. J. Audibert と S. Bubeck の略。 0.74
Minimax policies for adversarial and stochastic bandits. minimax policy for adversarial and stochastic bandits(英語) 0.68
In COLT 2009The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009. 2009年6月18-21日、カナダ、ケベック州モントリオールで第22回学習理論会議が開催された。
訳抜け防止モード: COLT 2009 第22回学習理論会議,モントリオール,ケベック Canada , June 18 - 21 , 2009 , 2009 .
0.80
URL http://www.cs.mcgill .ca/%7Ecolt2009/pape rs/022.pdf#page=1. URL http://www.cs.mcgill .ca/%7Ecolt2009/pape rs/022.pdf#page=1。 0.40
[3] J. Audibert, S. Bubeck, and G. Lugosi. J. Audibert, S. Bubeck, G. Lugosi. 0.69
Minimax policies for combinatorial prediction games. 組合せ予測ゲームのためのミニマックスポリシー。 0.73
In S. M. Kakade and U. von Luxburg, editors, COLT 2011 - The 24th Annual Conference on Learning Theory, June 9-11, 2011, Budapest, Hungary, volume 19 of JMLR Proceedings, pages 107–132. S. M. Kakade と U. von Luxburg, editors, COLT 2011 - The 24th Annual Conference on Learning Theory, June 9-11, June 9-11, Hungary, volume 19 of JMLR Proceedings, page 107–132. ^ ^ ^ ^ 公式サイト 0.81
JMLR.org, 2011. JMLR.org、2011年。 0.58
URL http://proceedings.m lr.press/v19/audiber t11a/audibert11a.pdf . URL http://proceedings.m lr.press/v19/audiber t11a/audibert11a.pdf 0.29
[4] J. Audibert, S. Bubeck, and G. Lugosi. J. Audibert, S. Bubeck, G. Lugosi. 0.69
Regret in online combinatorial optimization. オンライン組合せ最適化の見直し。 0.63
Math. Oper. Res., 39 (1):31–45, 2014. doi: 10.1287/moor.2013.05 98. 数学。 Oper Res., 39 (1):31–45, 2014 doi: 10.1287/moor.2013.05 98. 0.64
URL https://doi.org/10.1 287/moor.2013.0598. URL https://doi.org/10.1 287/moor.2013.0598 0.36
[5] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire. 0.86
The nonstochastic multiarmed bandit problem. 非確率的多重武装バンディット問題 0.57
SIAM J. Comput., 32(1):48–77, 2002. doi: 10.1137/S00975397013 98375. SIAM J。 Comput., 32(1):48-77, 2002. doi: 10.1137/S00975397013 98375 0.75
URL https://doi.org/10. URL https://doi.org/10。 0.58
1137/S00975397013983 75. 1137/S00975397013983 75。 0.54
[6] P. Auer, N. Cesa-Bianchi, and C. Gentile. [6]P. Auer,N. Cesa-Bianchi,C. Gentile. 0.84
Adaptive and self-confident on-line learning algorithms. 適応的で自信のあるオンライン学習アルゴリズム。 0.58
J. Comput. Syst. J.Comput シスト。 0.65
Sci., 64(1):48–75, 2002. doi: 10.1006/jcss.2001.17 95. Sci., 64(1):48–75, 2002. doi: 10.1006/jcss.2001.17 95 0.65
URL https://doi.org/10.1 006/ jcss.2001.1795. URL https://doi.org/10.1 006/jcss.2001.1795 0.42
[7] S. Bubeck and N. Cesa-Bianchi. [7]S. BubeckとN. Cesa-Bianchi。 0.76
Regret analysis of stochastic and nonstochastic multi-armed bandit problems. 確率的および非確率的多重武装バンディット問題の回帰解析 0.64
Found. Trends Mach. 見つかった トレンドマッハ。 0.58
Learn., 5(1):1–122, 2012. doi: 10.1561/2200000024. 5(1):1–122, 2012 doi: 10.1561/2200000024。 0.75
URL https: //doi.org/10.1561/22 00000024. URL https: //doi.org/10.1561/22 00000024 0.46
[8] S. Bubeck, M. B. Cohen, and Y. Li. [8]S. Bubeck, M. B. Cohen, Y. Li. 0.93
Sparsity, variance and curvature in multi-armed bandits. 多腕バンディットにおけるスパルシリティ, 分散, 曲率 0.60
In F. Janoos, M. Mohri, and K. Sridharan, editors, Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, volume 83 of Proceedings of Machine Learning Research, pages 111–127. F. Janoos, M. Mohri, K. Sridharan, editors, Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, Volume 83 of Proceedings of Machine Learning Research, page 111–127. ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 0.76
PMLR, 2018. 2018年、PMLR。 0.68
URL http://proceedings.m lr.press/v83/bubeck1 8a.html. URL http://proceedings.m lr.press/v83/bubeck1 8a.html 0.35
[9] S. Bubeck, Y. Li, H. Luo, and C. Wei. [9]S. Bubeck、Y. Li、H. Luo、C. Wei。 0.87
Improved path-length regret bounds for bandits. 盗賊に対するパス長後悔境界の改善 0.61
In A. Beygelzimer and D. Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 508–528. a. beygelzimer と d. hsu, editors, conference on learning theory, colt 2019, 25-28 june 2019, phoenix, az, usa, volume 99 of proceedings of machine learning research, pp508–528。 0.83
PMLR, 2019. 2019年、PMLR。 0.72
URL http://proceedings.m lr.press/v99/bubeck1 9b.html. URL http://proceedings.m lr.press/v99/bubeck1 9b.html 0.35
[10] N. Cesa-Bianchi and G. Lugosi. [10]Cesa-BianchiとG. Lugosi。 0.83
Prediction, learning, and games. 予測、学習、ゲーム。 0.57
Cambridge University Press, 2006. ケンブリッジ大学出版局、2006年。 0.58
ISBN 978-0-521-84108-5. doi: 10.1017/CBO978051154 6921. ISBN 978-0-521-84108-5. doi: 10.1017/CBO978051154 6921 0.40
URL https://doi.org/10.1 017/ CBO9780511546921. URL https://doi.org/10.1 017/CBO9780511546921 0.49
[11] S. de Rooij, T. van Erven, P. D. Grünwald, and W. M. Koolen. 11] S. de Rooij, T. van Erven, P. D. Grünwald, W. M. Koolen. 0.94
Follow the leader if you can, hedge if you must. できるならリーダーをフォローしなさい、必要であればヘッジしなさい。 0.60
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res., 15(1):1281–1316, 2014. res., 15(1):1281–1316, 2014年。 0.76
URL http://dl.acm.org/ci tation.cfm?id= 2638576. URL http://dl.acm.org/ci tation.cfm?id= 2638576 0.55
[12] D. J. Foster, Z. Li, T. Lykouris, K. Sridharan, and É. Tardos. [12]D.J. Foster、Z. Li、T. Lykouris、K. Sridharan、É. Tardos。 0.88
Learning in games: Robustness of fast convergence. ゲームでの学習: 速い収束のロバストさ。 0.80
In D. D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 4727–4735, 2016. D.D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, R. Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, December 2016, Barcelona, Spain, page 4727–4735, 2016 0.96
URL https://proceedings. URL https://proceedings. com 0.68
neurips.cc/paper/201 6/hash/b3f61131b6ece eb2b14835fa648a48ff- Abstract.html. neurips.cc/paper/201 6/hash/b3f61131b6ece eb2b14835fa648a48ff- Abstract.html 0.11
[13] Y. Freund and R. E. Schapire. 13] Y. Freund と R. E. Schapire 0.85
A decision-theoretic generalization of on-line learning and an application to boosting. オンライン学習の意思決定論的一般化と促進への応用 0.71
J. Comput. Syst. J.Comput シスト。 0.65
Sci., 55(1):119–139, 1997. doi: 10.1006/jcss.1997.15 04. Sci., 55(1):119-139, 1997. doi: 10.1006/jcss. 1997.1504. 0.62
URL https: //doi.org/10.1006/jc ss.1997.1504. URL https: //doi.org/10.1006/jc ss.1997.1504 0.37
[14] M. Gagliolo and J. Schmidhuber. 14] M. Gagliolo と J. Schmidhuber 0.81
Algorithm portfolio selection as a bandit problem with unbounded losses. 無制限損失を伴うバンディット問題としてのアルゴリズムポートフォリオ選択。 0.65
Ann. Math. Artif. Ann 数学。 Artif 0.60
Intell., 61(2):49–86, 2011. doi: 10.1007/s10472-011-9 228-z. Intell., 61(2):49–86, 2011 doi: 10.1007/s10472-011-9 228-z。 0.56
URL https: //doi.org/10.1007/s1 0472-011-9228-z. URL https: //doi.org/10.1007/s1 0472-011-9228-z 0.31
[15] E. Hazan. [15]E. Hazan. 0.90
Introduction to online convex optimization. オンライン凸最適化入門 0.63
Found. Trends Optim., 2(3-4):157–325, 2016. doi: 見つかった Trends Optim., 2(3-4):157–325, 2016 doi: 0.74
10.1561/2400000013. 10.1561/2400000013. 0.50
URL https://doi.org/10.1 561/2400000013. URL https://doi.org/10.1 561/2400000013。 0.43
[16] E. Hazan and S. Kale. 16]E. HazanとS. Kale。 0.75
Better algorithms for benign bandits. 良質なバンディットのためのより良いアルゴリズム。 0.53
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res., 12:1287–1311, 2011. 12:1287-1311、2011年。 0.60
URL http://dl.acm.org/ci tation.cfm?id=2021042. URL http://dl.acm.org/ci tation.cfm?id=2021042 0.49
10 10 0.85
英語(論文から抽出)日本語訳スコア
[17] T. Lattimore and C. Szepesvári. 17] t. lattimoreとc. szepesvári。 0.75
Bandit Algorithms. バンディットアルゴリズム。 0.62
Cambridge University Press, 2020. doi: 10.1017/ ケンブリッジ大学出版、2020年 doi: 10.1017/ 0.64
9781108571401. 9781108571401. 0.85
[18] F. Orabona. F. Orabona. 0.48
A modern introduction to online learning. オンライン学習の現代的展開。 0.78
CoRR, abs/1912.13213, 2019. CoRR, abs/1912.13213, 2019。 0.73
URL http: //arxiv.org/abs/1912 .13213. URL http: /arxiv.org/abs/1912. 13213。 0.54
[19] F. Orabona and D. Pál. F. Orabona と D. Pál. 0.65
Scale-free online learning. スケールフリーオンライン学習。 0.70
Theor. Comput. Theor Comput 0.50
Sci., 716:50–69, 2018. doi: 10.1016/j. Sci., 716:50–69, 2018. doi: 10.1016/j. 0.62
tcs.2017.11.021. 2017年11.021 0.43
URL https://doi.org/10.1 016/j.tcs.2017.11.02 1. URL https://doi.org/10.1 016/j.tcs.2017.11.02 1 0.30
[20] R. Pogodin and T. Lattimore. 20] r. pogodin と t. lattimore 0.67
On first-order bounds, variance and gap-dependent bounds for adversarial bandits. 逆バンディットに対する一階境界、分散およびギャップ依存境界について 0.54
In A. Globerson and R. Silva, editors, Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pages 894–904. A. Globerson and R. Silva, editors, Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, Volume 115 of Proceedings of Machine Learning Research, page 894–904. 英語) 0.93
AUAI Press, 2019. AUAI Press、2019年。 0.79
URL http://proceedings.m lr.press/v115/ pogodin20a.html. URL http://proceedings.m lr.press/v115/ pogodin20a.html 0.41
[21] S. Shalev-Shwartz. 21]shalev-shwartz氏。 0.70
Online learning and online convex optimization. オンライン学習とオンライン凸最適化。 0.73
Found. Trends Mach. 見つかった トレンドマッハ。 0.58
Learn., 4(2): 107–194, 2012. doi: 10.1561/2200000018. 学ぶ。 4(2) 107–194, 2012 doi: 10.1561/2200000018。 0.61
URL https://doi.org/10.1 561/2200000018. URL https://doi.org/10.1 561/2200000018 0.46
[22] A. Slivkins. 22] a. slivkins. 0.68
Introduction to multi-armed bandits. Found. マルチ武器の盗賊。 見つかった 0.56
Trends Mach. Learn., 12(1-2):1–286, 2019. doi: トレンドマッハ。 12(1-2):1-286, 2019. doi 0.64
10.1561/2200000068. 10.1561/2200000068. 0.50
URL https://doi.org/10.1 561/2200000068. URL https://doi.org/10.1 561/2200000068 0.46
[23] T. van Erven, P. Grunwald, W. M. Koolen, and S. de Rooij. T. van Erven, P. Grunwald, W. M. Koolen, S. de Rooij. 0.79
Adaptive hedge. In J. ShaweTaylor, R. S. Zemel, P. L. Bartlett, F. C. N. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. 適応ヘッジ。 J. ShaweTaylor, R. S. Zemel, P. L. Bartlett, F. C. N. Pereira, K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011 0.79
Proceedings of a meeting held 12-14 December 2011, Granada, Spain, pages 1656–1664, 2011. 2011年12月12日から14日にかけてスペインのグラナダで1656-1664頁の会議が行われた。 0.52
URL https://proceedings. neurips.cc/paper/201 1/hash/ 64223ccf70bbb65a3a4a ceac37e21016-Abstrac t.html. URL https://proceedings. neurips.cc/paper/201 1/hash/ 64223ccf70b65a3a4ace ac37e21016-Abstract. html 0.23
[24] C. Wei and H. Luo. [24]C. WeiとH. Luo。 0.90
More adaptive algorithms for adversarial bandits. 逆バンディットに対するより適応的なアルゴリズム。 0.60
In S. Bubeck, V. Perchet, and P. Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1263–1291. s. bubeck, v. perchet, p. rigollet, editors, conference on learning theory, colt 2018, stockholm, sweden, 6-9 july 2018, volume 75 of proceedings of machine learning research, pages 1263–1291。 0.82
PMLR, 2018. 2018年、PMLR。 0.68
URL http: //proceedings.mlr.pr ess/v75/wei18a.html. URL http: //proceedings.mlr.pr ess/v75/wei18a.html 0.35
[25] J. Zimmert and Y. Seldin. 25]j・ジマートとy・セルディン 0.55
Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. tsallis-inf: 確率的および逆的バンディットの最適アルゴリズム。 0.74
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res., 22:28:1–28:49, 2021. 22:28:1-28:49, 2021。 0.54
URL http://jmlr.org/pape rs/v22/19-753.html. URL http://jmlr.org/pape rs/v22/19-753.html 0.35
A Potential Functions Lemma 6. A potential function Lemma 6 (英語) 0.75
For every θ ∈ Rn, there exists a unique λ such that g(θ, λ) = 1 すべての θ ∈ Rn に対して、g(θ, λ) = 1 となる一意な λ が存在する。 0.87
Proof. For every θ ∈ Rn, we have that g(θ, λ) = +∞. 証明。 すべての θ ∈ Rn に対して、g(θ, λ) = +∞ となる。 0.76
As g is monotonically increasing and continuous, by the intermediate value theorem, for every θ ∈ Rn (cid:4) there exists a unique λ such that g(θ, λ) = 1. g は単調に増加し連続であるので、中間値定理により、すべての θ ∈ Rn (cid:4) に対して g(θ, λ) = 1 となる一意な λ が存在する。 0.80
λ→−∞ g(θ, λ) = 0 and lim λ→−∞ g(θ, λ) = 0 と lim 0.94
λ→a−mini(θ(i)) λ→a−mini(θ(i)) 0.78
lim Lemma 7. Let x, y be such that x = ψ(u) and y = ψ(v). リム 第7回。 x, y を x = ψ(u) かつ y = ψ(v) とする。 0.58
Then Bregfψ (y(cid:107)x) = Bregf (cid:63) そしてbregfψ (y(cid:107)x) = Bregf (cid:63) 0.74
ψ (u(cid:107)v) ψ (u(cid:107)v) 0.90
Proof. Use the fact that f (cid:63) (y(cid:107)x) = Bregfψ 証明。 f (cid:63) (y(cid:107)x) = Bregf\ 0.70
Bregfψ ψ(u) = uψ(u) − f (ψ(u)). Bregfō ψ(u) = uψ(u) − f(ψ(u)) である。 0.80
(ψ(v)(cid:107)ψ(u)) = fψ(ψ(v)) − fψ(ψ(u)) − f(cid:48) (ψ(v)(cid:107)ψ(u)) = fψ(ψ(v)) − fψ(ψ(u)) − f(cid:48) 1.00
ψ(ψ(u))(ψ(v) − ψ(u)) ψ(u))(ψ(v) − ψ(u)) 0.74
= vψ(v) − f (cid:63) ψ(u) − f (cid:63) = f (cid:63) = vψ(v) − f (cid:63) ψ(u) − f (cid:63) = f (cid:63) 0.92
ψ(v) − (uψ(u) − f (cid:63) ψ(v) − f (cid:63)(cid:48) ψ(v) − (uψ(u) − f (cid:63) ψ(v) − f (cid:63)(cid:48) 0.94
ψ(u)) − u(ψ(v) − ψ(u)) ψ(u) − u(ψ(v) − ψ(u)) 0.79
ψ(v)(u − v) = Bregf (cid:63) ψ(v)(u − v) = bregf (cid:63) 0.91
(u(cid:107)v) (u(cid:107)v) 0.94
ψ B Iterates of OMD and FTRL Lemma 10. ψ B OMDとFTRL Lemma 10のイテレーション。 0.76
Let θ, θ(cid:48) ∈ Rn. θ, θ(cid:48) ∈ Rn とする。 0.82
If θ(cid:48)(i) = θ(i) + c for all i ∈ [n], then ψ(θ(cid:48) + λ(θ(cid:48))) = ψ(θ + λ(θ)) θ(cid:48)(i) = θ(i) + c for all i ∈ [n] ならば ψ(θ(cid:48) + λ(θ(cid:48))) = ψ(θ + λ(θ)) である。 0.97
11 (cid:4) 11 (cid:4) 0.82
英語(論文から抽出)日本語訳スコア
Proof. Observe that g(θ, c + λ(θ(cid:48))) = 証明。 観察する g(θ, c + λ(θ(cid:48)) = 0.73
n(cid:88) i=1 n(cid:88) i=1 0.71
ψ(θ(i) + c + λ(θ(cid:48))) = ψ(θ(i) + c + λ(θ(cid:48)) = 0.89
n(cid:88) i=1 n(cid:88) i=1 0.71
ψ(θ(cid:48)(i) + λ(θ(cid:48))) = g(θ(cid:48), λ(θ(cid:48))) = 1 ψ(θ(cid:48)(i) + λ(θ(cid:48))) = g(θ(cid:48), λ(θ(cid:48))) = 1 0.99
Since λ(θ) is the unique solution to g(θ, λ) = 1, we must have that λ(θ) = c + λ(θ(cid:48)). λ(θ) は g(θ, λ) = 1 の唯一の解であるため、λ(θ) = c + λ(θ(cid:48)) でなければならない。 0.88
Hence, we have that ψ(θ(i) + λ(θ)) = ψ(θ(i) + c + λ(θ) − c) = ψ(θ(cid:48)(i) + λ(θ(cid:48)) for all i ∈ [n] (cid:4) したがって、すべての i ∈ [n] (cid:4) に対して ψ(θ(i) + λ(θ)) = ψ(θ(i) + c + λ(θ) − c) = ψ(θ(cid:48)(i) + λ(θ(cid:48)) となる。 0.96
Lemma 10 states that translating θ along the all ones vector 1 does not change the distribution. lemma 10 は、θ をすべてのベクトル 1 に沿って変換しても分布は変わらないと述べる。 0.73
This fact is useful in showing that the iterates of OMD/FTRL have a simple functional form using ψ. この事実は、OMD/FTRL のイテレートが単純関数形式であることを示すのに有用である。 0.72
The following lemmas are useful in analyzing the iterates of OMD/FTRL. 以下の補題はOMD/FTRLの反復解析に有用である。 0.74
Lemma 11. Let p(cid:48) ∈ ∆n such that p(cid:48) = ψ(θ(cid:48) + λ(θ(cid:48))) for some vector θ(cid:48). 背番号11。 任意のベクトル θ(cid:48) に対して p(cid:48) = λ(cid:48) + λ(cid:48)) となるような p(cid:48) ∈ λn とする。 0.65
Consider the optimization p = arg minq∈∆n 最適化 p = arg minq linkedin を考える 0.69
. Suppose θ = −αl + α . θ = −αl + α とする。 0.77
β θ(cid:48) then p = ψ(θ + λ(θ)) β θ(cid:48) ならば、p = λ(θ + λ(θ)) 0.91
l(cid:62)q + Bregα,β l(cid:62)q + Bregα,β 0.90
(q(cid:107)p(cid:48) ) (q(cid:107)p(cid:48) ) 0.86
(cid:16) (cid:17) (cid:16) (cid:17) 0.78
Fψ Proof. The Lagrangian for the optimization problem is: fψ 証明。 最適化問題のラグランジアンは 0.62
Taking the gradient and equating to 0, we have: 勾配をとり、0に等しくすると、次のようになる。 0.46
L(q, µ) = l(cid:62)q + Bregα,β L(q, μ) = l(cid:62)q + Bregα,β 1.00
Fψ (q(cid:107)p(cid:48) ) + µ(1 − q(cid:62)1) fψ (q(cid:107)p(cid:48) ) + μ(1 − q(cid:62)1) 0.81
∇Fψ(q) = ψ−1(q) = −αl + α β fψ(q) = ψ−1(q) = −αl + α β 0.87
= −αl + θ(cid:48) + = −αl + θ(cid:48) + 0.83
∇Fψ(p(cid:48)) + µ α β λ(θ(cid:48)) + µ = θ + ∇Fψ(p(cid:48)) + µ α β λ(θ(cid:48)) + µ = θ + 0.94
λ(θ(cid:48)) + µ λ(θ(cid:48)) + μ 0.98
α β (cid:18) α β (cid:18) 0.82
α β α β q = ψ α β α β q = ψ 0.85
θ + λ(θ(cid:48)) + µ θ + λ(θ(cid:48)) + μ 0.92
(cid:19) Using Lemma 6, since p ∈ ∆n, the unique solution to µ = λ Using Lemma 10, we have: (cid:19) Lemma 6 は p ∈ λn であるため、Lemma 10 を用いて μ = λ の唯一の解となる。 0.78
θ + α β λ(θ(cid:48)) θ + α βλ(θ(cid:48)) 0.90
(cid:18) (cid:18) (cid:18) (cid:18) 0.78
p = ψ θ + λ(θ(cid:48)) + λ p = ψ θ + λ(θ(cid:48)) + λ 0.89
α β θ + λ(θ(cid:48)) α β θ + λ(θ(cid:48)) 0.88
α β (cid:17) α β (cid:17) 0.82
(cid:16) (cid:19)(cid:19) (cid:16)(cid:19)(cid :19) 0.72
= ψ(θ + λ(θ)) = ψ(θ + λ(θ)) 0.85
(cid:4) (cid:80)t s=1 ls, α = β = 1 and θ(cid:48) = 0 gives the INF form for (cid:4) (cid:80)t s=1 ls, α = β = 1, θ(cid:48) = 0 は INF 形式を与える。 0.83
We have the following implications: 私たちは以下の意味を持っている。 0.42
1. Applying Lemma 11 with l = ηt 1. l = ηt による Lemma 11 の適用 0.81
2. Applying Lemma 11 l =(cid:80)t 2. Lemma 11 l =(cid:80)t を適用する 0.83
pt+1 in FTRL. pt+1とftrl。 0.66
s=1 ηsls, α = β = 1 and θ(cid:48) = 0 gives the INF form for pt+1 in 3. s=1 ηsls, α = β = 1, θ(cid:48) = 0 は pt+1 の INF 形式を与える。 0.87
Repeatedly applying Lemma 11 from t = 1 . t = 1 から Lemma 11 を繰り返し適用する。 0.82
. . , T with l = lt, α = β = ηt and p(cid:48) = pt . . , T with l = lt, α = β = ηt, p(cid:48) = pt 0.89
Aggregator OMD. Aggregator OMD 0.56
gives INF form for pt+1 in 1-step OMD. 1ステップ OMD で pt+1 のINF 形式を与える。 0.65
4. Repeatedly applying Lemma 11 from t = 1 . 4. t = 1 から Lemma 11 を繰り返し適用する。 0.84
. . , T with l = lt, α = ηt, β = ηt−1 and . . , T with l = lt, α = ηt, β = ηt−1, 0.87
p(cid:48) = pt gives INF form for pt+1 in 1-step FTRL. p(cid:48) = pt は 1 ステップ FTRL において pt+1 に対して INF 形式を与える。 0.65
Lemma 12. Let p(cid:48) ∈ ∆n such that p(cid:48) = ψ(θ(cid:48) + λ(θ(cid:48))) for some vector θ(cid:48). 背番号12。 任意のベクトル θ(cid:48) に対して p(cid:48) = λ(cid:48) + λ(cid:48)) となるような p(cid:48) ∈ λn とする。 0.66
Consider the optimization β λ(θ(cid:48))) if ˜p ˜p = arg minq∈Rn exists. 最適化 β λ(θ(cid:48)) を考えると、p = arg minqıRn が存在する。 0.85
β θ(cid:48). β θ (cid:48)。 0.86
Then ˜p = ψ(θ + α すると、n = θ + α となる。 0.71
. Suppose θ = −αl + α . θ = −αl + α とする。 0.77
l(cid:62)q + Bregα,β l(cid:62)q + Bregα,β 0.90
(q(cid:107)p(cid:48) ) (q(cid:107)p(cid:48) ) 0.86
Fψ (cid:16) fψ (cid:16) 0.74
(cid:17) 12 (cid:17) 12 0.82
英語(論文から抽出)日本語訳スコア
Proof. Taking the gradient of the objective and equating to 0, we get: 証明。 目的の勾配を取り、0に等しくすると、次のようになる。 0.59
∇F (q) = ψ−1(q) = −αl + tF (q) = s−1(q) = −αl + 0.82
∇F (p(cid:48)) = −αl + sF (p(cid:48)) = −αl + 0.79
α β θ(cid:48) + α β θ(cid:48) + 0.87
α β α β λ(θ(cid:48)) = θ + α β α β λ(θ(cid:48)) = θ + 0.90
λ(θ(cid:48)) λ(θ(cid:48)) 0.94
α β Thus, if ˜p exits, then ˜p = ψ(θ + α α β ゆえに、p が退出するならば、\p = ψ(θ + α) となる。 0.73
β λ(θ(cid:48))) βλ(θ(cid:48)) 0.92
(cid:4) Lemma 13. (cid:4) 背番号13。 0.65
Let ˜p ∈ Rn p = arg minq∈∆n BregFψ p ∈ Rn p = arg minqコメントする。 0.76
+ and such that y = ψ(θ) for some vector θ. とすると、あるベクトル θ に対して y = ψ(θ) となる。 0.81
Consider the optimization (x(cid:107)y), then p = ψ(θ + λ(θ)) 最適化 (x(cid:107)y) を考えると、p = λ(θ + λ(θ)) となる。 0.81
Proof. The Lagrangian for the optimization problem is: 証明。 最適化問題のラグランジアンは 0.57
L(q, µ) = BregFψ Taking the gradient and equating to 0, we have: l(q, μ) = bregfψ 勾配を取って 0 に等しくなると、次のようになる。 0.59
(q(cid:107)˜p) + µ(1 − q(cid:62)1) (q(cid:107) ,p) + μ(1 − q(cid:62)1) 0.92
Using Lemma 6, since p ∈ ∆n, the unique solution to µ = λ(θ). Lemma 6 は p ∈ λn であるため、μ = λ(θ) の唯一の解である。 0.79
Thus p = ψ(θ + λ(θ)) したがって、p = θ(θ + λ(θ)) 0.89
∇Fψ(q) = ψ−1(q) = ∇F (˜p) + µ = θ + µ σ(q) = ψ−1(q) = τf(q) + μ = θ + μ である。 0.76
(cid:4) We have the following implications: (cid:4) 私たちは以下の意味を持っている。 0.60
1. Repeatedly applying Lemma 12 and Lemma 13 from t = 1 . 1. t = 1 から Lemma 12 と Lemma 13 を繰り返し適用する。 0.85
. . , T with l = lt, α = β = ηt . . , T with l = lt, α = β = ηt 0.87
and p(cid:48) = pt, ˜p = ˜pt+1 gives INF form for ˜pt+1 and pt+1 in 2-step OMD. そして p(cid:48) = pt, >p = >pt+1 は 2 段階の OMD において >pt+1 および pt+1 に対して INF 形式を与える。 0.60
ηt−1 and p(cid:48) = pt, ˜p = ˜pt+1 gives INF form for ˜pt+1 and pt+1 in 2-step FTRL. ηt−1 と p(cid:48) = pt は 2 ステップ ftrl において ηt+1 と pt+1 の inf 形式を与える。 0.64
2. Repeatedly applying Lemma 12 and Lemma 13 from t = 1 . 2. t = 1 から Lemma 12 と Lemma 13 を繰り返し適用する。 0.85
. . , T with l = lt, α = ηt, β = . . , T with l = lt, α = ηt, β = 0.87
C Regret of OMD and FTRL Theorem 14. OMD と FTRL Theorem 14 の C リスト。 0.69
For any p ∈ ∆n and any sequence of losses l1, . 任意の p ∈ sn と損失の列 l1, に対して。 0.73
. . , lT , the iterates of 1-step OMD . . , lT は 1 ステップ OMD の繰り返しである 0.82
satisfy the regret equality(cid:80)T 後悔の平等(cid:80)tを満たす 0.76
t=1 l(cid:62) t=1 l(cid:62) 0.71
t (pt − p) t (pt − p) 0.85
(cid:104) T(cid:88) (cid:104) t(cid:88) 0.79
t=1 1 ηt = t=1。 1 ηt = 0.73
BregFψ (p(cid:107)pt) − BregFψ ブレグファクトリー (p(cid:107)pt)- BregF' 0.63
(p(cid:107)pt+1) (p(cid:107)pt+1) 0.78
(cid:105) T(cid:88) (cid:105) t(cid:88) 0.79
t=1 + (cid:20) t=1。 + (cid:20) 0.70
t (pt − pt+1) − 1 l(cid:62) ηt t (pt − pt+1) − 1 l(cid:62) ηt 0.87
(cid:21) BregFψ (cid:21) ブレグファクトリー 0.58
(pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.78
Proof. For any p ∈ ∆n, we have: 証明。 任意の p ∈ (n) に対して、 0.56
t (pt+1 − p) + l(cid:62) t (pt − pt+1) t (pt − p) = l(cid:62) l(cid:62) (θt−1 − θt)(cid:62)(pt+1 − p) + l(cid:62) 1 ηt t (pt+1 − p) + l(cid:62) t (pt − pt+1) t (pt − p) = l(cid:62) l(cid:62) (θt−1 − θt)(cid:62)(pt+1 − p) + l(cid:62) 1 ηt 0.84
= (cid:18)∇Fψ(pt) − λ(θt−1) (cid:18)∇Fψ(pt) − ∇Fψ(pt+1) = (cid:18)-fψ(pt) − λ(θt−1) (cid:18)-fψ(pt) −-fψ(pt+1) 0.81
t (pt − pt+1) − ∇Fψ(pt+1) − λ(θt) (cid:19)(cid:62) t(pt − pt+1) − t(pt+1) − λ(θt) (cid:19)(cid:62) 0.82
(pt+1 − p) + l(cid:62) (pt+1 − p) + l(cid:62) 0.86
ηt ηt = = ηt ηt ηt = = ηt 0.81
ηt (cid:19)(cid:62) ηt (cid:19)(cid:62) 0.77
(pt+1 − p) + l(cid:62) (pt+1 − p) + l(cid:62) 0.86
t (pt − pt+1) t (pt − pt+1) 0.92
t (pt − pt+1) t (pt − pt+1) 0.92
We can write the first term as: 最初の項を次のように書くことができる。 0.51
13 13 0.85
英語(論文から抽出)日本語訳スコア
(cid:62) (∇Fψ(pt) − ∇Fψ(pt+1)) (cid:62)〔fψ(pt)−〔pt+1〕) 0.69
Taking summation over t, we have(cid:80)T T(cid:88) t 上の和をとると、(cid:80)T (cid:88) 0.75
(p(cid:107)pt) − BregFψ (pt+1 − p) = BregFψ t (pt − p) = (cid:20) (cid:105) T(cid:88) (p(cid:107)pt) − BregF' (pt+1 − p) = BregF' t (pt − p) = (cid:20) (cid:105) T(cid:88) 0.86
t=1 l(cid:62) t=1 l(cid:62) 0.71
(cid:104) (p(cid:107)pt) − BregFψ (cid:104) (p(cid:107)pt)- BregF' 0.84
(p(cid:107)pt+1) (p(cid:107)pt+1) 0.78
BregFψ + ブレグファクトリー + 0.61
1 ηt t=1 t (pt − pt+1) − 1 l(cid:62) ηt 1 ηt t=1。 t (pt − pt+1) − 1 l(cid:62) ηt 0.74
t=1 (cid:21) t=1。 (cid:21) 0.62
(pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.78
BregFψ (p(cid:107)pt+1) − BregFψ ブレグファクトリー (p(cid:107)pt+1) − BregF' 0.57
(pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.78
(cid:4) Theorem 15. (cid:4)定理15。 0.74
For any p ∈ ∆n and any sequence of losses l1, . 任意の p ∈ sn と損失の列 l1, に対して。 0.73
. . , lT , the iterates of 2-step OMD . . , lT , 2段階 OMD の反復 0.81
satisfy the regret inequality(cid:80)T ≤ T(cid:88) 後悔の不等式(cid:80)T ≤ T(cid:88)を満たす 0.72
(cid:104) BregFψ (cid:104) ブレグファクトリー 0.58
1 ηt t=1 Proof. 1 ηt t=1。 証明。 0.65
For any p ∈ ∆n, we have: 任意の p ∈ (n) に対して、 0.50
t=1 l(cid:62) t=1 l(cid:62) 0.71
t (pt − p) t (pt − p) 0.85
(p(cid:107)pt) − BregFψ (p(cid:107)pt)- BregF' 0.90
(p(cid:107)pt+1) (p(cid:107)pt+1) 0.78
(cid:105) T(cid:88) (cid:105) t(cid:88) 0.79
t=1 + (cid:20) t=1。 + (cid:20) 0.70
t (pt − ˜pt+1) − 1 l(cid:62) ηt t (pt-1) − 1 l(cid:62) ηt 0.90
(cid:21) BregFψ (cid:21) ブレグファクトリー 0.58
(˜pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.75
t (pt − p) = l(cid:62) t (˜pt+1 − p) + l(cid:62) t (pt − ˜pt+1) l(cid:62) (θt−1 − θt)(cid:62)(˜pt+1 − p) + l(cid:62) 1 ηt t (pt − p) = l(cid:62) t ( >pt+1 − p) + l(cid:62) t (pt − >pt+1) l(cid:62) (θt−1 − θt)(cid:62)( >pt+1 − p) + l(cid:62) 1 ηt 0.79
= (cid:18)∇Fψ(pt) − λ(θt−1) (cid:18)∇Fψ(pt) − ∇Fψ(˜pt+1) = (cid:18)-fψ(pt) − λ(θt−1) (cid:18)-fψ(pt) −-fψ(pt+1) 0.81
ηt = = ηt ηt ηt = = ηt ηt 0.81
t (pt − ˜pt+1) t (pt-1) である。 0.65
− ∇Fψ(˜pt+1) − λ(θt−1) (cid:19)(cid:62) − λ(θt−1) (cid:19)(cid:62) 0.81
ηt (˜pt+1 − p) + l(cid:62) ηt (=pt+1 −p) + l(cid:62) 0.78
t (pt − ˜pt+1) t (pt-1) である。 0.65
(cid:19)(cid:62) (cid:19)(cid:62) 0.75
(˜pt+1 − p) + l(cid:62) (=pt+1 −p) + l(cid:62) 0.77
t (pt − ˜pt+1) t (pt-1) である。 0.65
We can write the first term as: 最初の項を次のように書くことができる。 0.51
(cid:62) (∇Fψ(pt) − ∇Fψ(˜pt+1)) (cid:62)(pt)−fψ(pt+1)) 0.72
(˜pt+1 − p) = BregFψ ≤ BregFψ (pt+1 − p) = bregf ≤ ≤ bregfψ 0.67
(p(cid:107)pt) − BregFψ (p(cid:107)pt) − BregFψ (p(cid:107)pt) − BregF. (p(cid:107)pt) − BregF. 0.85
(p(cid:107)˜pt+1) − BregFψ (p(cid:107)pt+1) − BregFψ (p(cid:107) >pt+1) − BregF > (p(cid:107)pt+1) − BregF > 0.68
(˜pt+1(cid:107)pt) (˜pt+1(cid:107)pt) (pt+1(cid:107)pt)(pt+1(cid:107)pt) 0.74
This is because BregFψ これはbregfψが 0.51
(p(cid:107)pt+1) ≤ BregFψ (p(cid:107)pt+1)≤ BregF' 0.81
(p(cid:107)˜pt+1) for all p ∈ ∆n as shown below: (p(cid:107) >pt+1) 以下に示すすべての p ∈ >n について。 0.62
(p(cid:107)˜pt+1) − BregFψ (p(cid:107) >pt+1) − BregF' 0.70
(p(cid:107)pt+1) (p(cid:107)pt+1) 0.78
BregFψ = Fψ(pt+1) − Fψ(˜pt+1) − ∇Fψ(˜pt+1)(cid:62)(p − ˜pt+1) + ∇Fψ(pt+1)(cid:62)(p − pt+1) = BregFψ ≥ (∇Fψ(pt+1) − ∇Fψ(˜pt+1))(cid:62)(p − pt+1) = (θt + λ(θt) − θt − λ(θt−1))(cid:62)(p − pt+1) = 0 bregfψ = fψ(pt+1) − fψ( spt+1) − sfψ( spt+1)(cid:62)(p − spt+1) + sfψ(pt+1)(cid:62)(p − pt+1) = bregfψ ≥ (fψ(pt+1) − sfψ( spt+1))(cid:62)(p − pt+1) = (θt + λ(θt) − θt − λ(θt−1))(cid:62)(p − pt+1) = 0。 0.72
(pt+1(cid:107)˜pt+1) + (∇Fψ(pt+1) − ∇Fψ(˜pt+1))(cid:62)(p − pt+1) (pt+1(cid:107) > > > > > > > > > (cid:62)(p − pt+1) 0.76
Taking summation over t, we have(cid:80)T T(cid:88) t 上の和をとると、(cid:80)T (cid:88) 0.75
(cid:104) (p(cid:107)pt) − BregFψ (cid:104) (p(cid:107)pt)- BregF' 0.84
BregFψ 1 ηt ブレグファクトリー 1 ηt 0.63
t=1 t=1 l(cid:62) t=1。 t=1 l(cid:62) 0.58
t (pt − p) ≤ (cid:20) (cid:105) T(cid:88) t (pt − p) ≤ (cid:20) (cid:105) T(cid:88) 0.88
(p(cid:107)pt+1) (p(cid:107)pt+1) 0.78
+ t (pt − ˜pt+1) − 1 l(cid:62) ηt + t (pt-1) − 1 l(cid:62) ηt 0.87
(cid:21) (˜pt+1(cid:107)pt) (cid:21) (pt+1(cid:107)pt) 0.77
BregFψ (cid:4) ブレグファクトリー (cid:4) 0.58
t=1 14 t=1。 14 0.66
英語(論文から抽出)日本語訳スコア
Theorem 16. For any p ∈ ∆n and any sequence of losses l1, . 理論16。 任意の p ∈ sn と損失の列 l1, に対して。 0.69
. . , lT , the iterates of 2-step FTRL . . 2段階FTRLの繰り返し 0.71
satisfy the regret inequality(cid:80)T 後悔の不平等を満たす (cid:80)T 0.62
t=1 l(cid:62) t=1 l(cid:62) 0.71
t (pt − p) t (pt − p) 0.85
(cid:105) T(cid:88) (cid:105) t(cid:88) 0.79
(cid:104) t=1 (cid:104) t=1。 0.62
+ t (pt − ˜pt+1) − Bregηt,ηt−1 l(cid:62) + t (pt − spt+1) − Bregηt,ηt−1 l(cid:62) 0.78
Fψ (˜pt+1(cid:107)pt) fψ (pt+1(cid:107)pt) 0.73
(cid:105) (cid:104) (cid:105) (cid:104) 0.78
≤ 1 ηT BregFψ ≤ 1 ηt ブレグファクトリー 0.64
(p(cid:107)p1) − BregFψ (p(cid:107)p1) − BregF' 0.82
(p(cid:107)pT +1) (p(cid:107)pT+1) 0.82
Proof. Note that ∇Fψ(pt+1) = ψ−1(pt+1) = θt + λ(θt). 証明。 注意すべき点として、sf(pt+1) = t−1(pt+1) = θt + λ(θt) である。 0.59
For any p ∈ ∆n, we have : 任意の p ∈ (n) に対して、 0.48
t (pt − p) = l(cid:62) l(cid:62) t (pt − p) = l(cid:62) l(cid:62) 0.94
t (˜pt+1 − p) + l(cid:62) t(spt+1 − p) + l(cid:62) 0.86
(cid:32)∇Fψ(pt) − λ(θt−1) − (cid:18)∇Fψ(pt) ηt−1 − ∇Fψ(˜pt+1) (cid:32) (fψ(pt) − λ(θt−1) − (cid:18)) (fψ(pt) ηt−1 − s(pt+1) 0.70
t (pt − ˜pt+1) = (cid:19)(cid:62) t (pt-1) = (cid:19)(cid:62) 0.81
ηt−1 ηt = = ηt−1 ηt = = 0.74
(cid:18) θt−1 (cid:18)θt−1 0.57
(cid:19)(cid:62) (cid:19)(cid:62) 0.75
− θt ηt ∇Fψ(˜pt+1) − ηt λ(θt−1) −θt ηt シュフェー(θpt+1) − ηt λ(θt−1) 0.69
ηt−1 (cid:33)(cid:62) ηt−1 (cid:33)(cid:62) 0.61
ηt−1 ηt (˜pt+1 − p) + l(cid:62) ηt−1 ηt (=pt+1 −p) + l(cid:62) 0.67
t (pt − ˜pt+1) t (pt-1) である。 0.65
(˜pt+1 − p) + l(cid:62) (=pt+1 −p) + l(cid:62) 0.77
t (pt − ˜pt+1) t (pt-1) である。 0.65
(˜pt+1 − p) + l(cid:62) (=pt+1 −p) + l(cid:62) 0.77
t (pt − ˜pt+1) t (pt-1) である。 0.65
Let α be any number. α を任意の数とする。 0.77
The first term above is equal to: 上記の第1項は以下のとおりである。 0.60
= Bregα,ηt−1 ≤ Bregα,ηt−1 = Bregα,ηt−1 ≤ Bregα,ηt−1 0.62
Fψ Fψ (p(cid:107)pt) − Bregα,ηt (p(cid:107)pt) − Bregα,ηt fψ fψ (p(cid:107)pt) − Bregα,ηt (p(cid:107)pt) − Bregα,ηt 0.76
Fψ Fψ (p(cid:107)˜pt+1) − Bregηt,ηt−1 (p(cid:107)pt+1) − Bregηt,ηt−1 fψ fψ (p(cid:107) >pt+1) − Bregηt,ηt−1 (p(cid:107)pt+1) − Bregηt,ηt−1 0.68
Fψ Fψ (˜pt+1(cid:107)pt) (˜pt+1(cid:107)pt) fψ fψ (pt+1(cid:107)pt)(pt+1(cid:107)pt) 0.71
This is because Bregα,ηt Fψ これはBregα,ηt F が原因である。 0.54
(p(cid:107)pt+1) ≤ Bregα,ηt (p(cid:107)pt+1)≤ Bregα,ηt 0.81
Fψ (p(cid:107)˜pt+1) For all p ∈ ∆n as shown below: fψ (p(cid:107) >pt+1) 以下に示すすべての p ∈ >n について。 0.66
(p(cid:107)˜pt+1) − Bregα,ηt (p(cid:107) ]pt+1) − bregα,ηt 0.73
(p(cid:107)pt+1)) (p(cid:107)pt+1) 0.84
ηt(Bregα,ηt Fψ = Fψ(pt+1) − Fψ(˜pt+1) − ∇Fψ(˜pt+1)(cid:62)(p − ˜pt+1) + ∇Fψ(pt+1)(cid:62)(p − pt+1) = BregFψ ≥ (∇Fψ(pt+1) − ∇Fψ(˜pt+1))(cid:62)(p − pt+1) ηt(Bregα,ηt F ) = F (pt+1) − F ( spt+1) − sf( spt+1)(cid:62)(p − spt+1) + sf(pt+1)(cid:62)(p − pt+1) = BregF ≥ ( sf(pt+1)) − sf( spt+1))(cid:62)(p − pt+1)) 0.69
(pt+1(cid:107)˜pt+1) + (∇Fψ(pt+1) − ∇Fψ(˜pt+1))(cid:62)(p − pt+1) (pt+1(cid:107) > > > > > > > > > (cid:62)(p − pt+1) 0.76
Fψ (cid:19)(cid:62) fψ (cid:19)(cid:62) 0.73
(cid:18) = (cid:18) = 0.82
θt + λ(θt) − θt − ηt ηt−1 θt + λ(θt) − θt − ηt ηt−1 0.74
λ(θt−1) (p − pt+1) = 0 λ(θt−1) (p − pt+1) = 0 0.84
Taking summation over t, we have: t 上の和をとると、次のようになる。 0.28
T(cid:88) t (pt − p) ≤ T(cid:88) t(cid:88) t (pt − p) ≤ T(cid:88) 0.90
l(cid:62) (cid:104) l(cid:62) (cid:104) 0.81
Bregα,ηt−1 Bregα,ηt−1 0.59
Fψ (p(cid:107)pt) − Bregα,ηt fψ (p(cid:107)pt) − Bregα,ηt 0.79
Fψ (p(cid:107)pt+1) fψ (p(cid:107)pt+1) 0.74
t=1 t=1 = Bregα,η0 Fψ t=1。 t=1。 =Bregα,η0 0.59
(p(cid:107)p1) − Bregα,ηT (p(cid:107)p1) − Bregα,ηT 0.83
Fψ (p(cid:107)pT +1) + fψ (p(cid:107)pT +1) + 0.80
(cid:105) T(cid:88) (cid:105)t(cid:88) 0.76
t=1 + (cid:104) t=1。 + (cid:104) 0.70
Since p1 = (1/n, . p1 = (1/n, 。 0.81
. . , 1/n), we see that: . . , 1/n)です。 0.73
Bregα,η0 Fψ (p(cid:107)p1) − Bregα,ηT Bregα,η0 (p(cid:107)p1) − Bregα,ηT 0.88
Fψ (p(cid:107)pT +1) = fψ (p(cid:107)pT +1) = 0.80
(cid:104) 1 ηT (cid:104) 1ηT 0.81
BregFψ T(cid:88) ブレグファクトリー t(cid:88) 0.59
(cid:104) t=1 (cid:104) t=1。 0.62
t (pt − ˜pt+1) − Bregηt,ηt−1 l(cid:62) t (pt − spt+1) − Bregηt,ηt−1 l(cid:62) 0.72
Fψ (cid:105) fψ (cid:105) 0.74
(˜pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.75
(cid:105) t (pt − ˜pt+1) − Bregηt,ηt−1 l(cid:62) (cid:105) (cid:105) t (pt − spt+1) − Bregηt,ηt−1 l(cid:62) (cid:105) 0.75
Fψ (p(cid:107)p1) − BregFψ fψ (p(cid:107)p1) − BregF' 0.76
(p(cid:107)pT +1) (p(cid:107)pT+1) 0.82
(˜pt+1(cid:107)pt) (pt+1(cid:107)pt) 0.75
(cid:4) D Summation Lemma (cid:4) d 要約補題 0.67
We omit the proof for the following lemmas and refer to their original proofs. 我々は、以下の補題の証明を省略し、元の証明を参照する。 0.67
15 15 0.85
英語(論文から抽出)日本語訳スコア
Lemma 17 (Lemma 4.8 in Pogodin and Lattimore [20]). Lemma 17 (Lemma 4.8 in Pogodin and Lattimore [20]) 0.79
Let x1, . . . x1 とする。 . . 0.80
, xt be non-negative reals. xt は非負実数である。 0.64
We have: Lemma 18 (Lemma 3.5 in Auer et al [6]). あります。 Lemma 18 (Lemma 3.5 in Auer et al [6]) 0.56
Let x1, . . . x1 とする。 . . 0.80
, xt be non-negative reals. xt は非負実数である。 0.64
We have: ≤ 4 s=1 xs あります。 ≤ 4 s=1 xs 0.63
xt + max xt xt + max xt 0.85
t T(cid:88) t t(cid:88) 0.83
t=1 (cid:113) t=1。 (cid:113) 0.62
xt 1 +(cid:80)t−1 T(cid:88) xt 1 +(cid:80)t−1 T(cid:88) 0.81
(cid:113) t=1 (cid:113) t=1。 0.62
1 +(cid:80)t 1 +(cid:80)t 0.92
xt s=1 xs (cid:118)(cid:117)(c id:117)(cid:116)1 + T(cid:88) (cid:118)(cid:117)(c id:117)(cid:116)1 + xt s=1 xs (cid:118)(cid:117)(c id:117)(cid:116)1 + t(cid:88) (cid:118)(cid:117)(c id:117)(cid:116)1 + 0.77
≤ 2 t=1 T(cid:88) ≤ 2 t=1。 t(cid:88) 0.71
t=1 xt 16 t=1。 xt 16 0.72
                                 ページの最初に戻る

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