論文の概要、ライセンス

# (参考訳) メジャー化対策、シーケンス複雑性、オンライン学習 [全文訳有]

Majorizing Measures, Sequential Complexities, and Online Learning ( http://arxiv.org/abs/2102.01729v1 )

ライセンス: CC BY 4.0
Adam Block, Yuval Dagan, and Sasha Rakhlin(参考訳) 本稿では, シーケンシャルなRademacher複雑性を制御するために, ジェネリックチェアリングと大規模化手法を導入する。 本研究は,水平独立な方法での逐次スケールセンシティブな次元の観点で支配される分数被覆数の概念を大規模化することで,さらに複雑性の仮定により,逐次スケールセンシティブな次元の積分による最悪ケースシーケンシャルなラデマッハ複雑性の厳密な制御を確立する。 最後に、最悪ケースシーケンシャルなRademacher複雑性に対して、厳密な収縮不等式を確立する。 上記は、経験的過程の古典的理論を逐次ケースに拡張する上で顕著なオープン問題の数の解決を構成し、その結果、オンライン学習のための鋭い結果を確立します。

We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dominated in terms of sequential scale-sensitive dimensions in a horizon-independent way, and, under additional complexity assumptions establish a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension. Finally, we establish a tight contraction inequality for worst-case sequential Rademacher complexity. The above constitutes the resolution of a number of outstanding open problems in extending the classical theory of empirical processes to the sequential case, and, in turn, establishes sharp results for online learning.
公開日: Tue, 2 Feb 2021 19:52:58 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
Majorizing Measures, Sequential Complexities, and Online Learning メジャー化対策、シーケンス複雑性、オンライン学習 0.77
Adam Block Yuval Dagan アダム・ブロック Yuval (複数形 Yuvals) 0.50
Alexander Rakhlin Alexander Rakhlin 0.85
MIT MIT MIT MIT MIT MIT 0.85
February 4, 2021 Abstract 2021年2月4日 概要 0.58
We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. 本稿では, シーケンシャルなRademacher複雑性を制御するために, ジェネリックチェアリングと大規模化手法を導入する。 0.48
We relate majorizing measures to the notion of fractional covering numbers, which we show to be dominated in terms of sequential scale-sensitive dimensions in a horizon-independent way, and, under additional complexity assumptions establish a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension. 本研究は,水平独立な方法での逐次スケールセンシティブな次元の観点で支配される分数被覆数の概念を大規模化することで,さらに複雑性の仮定により,逐次スケールセンシティブな次元の積分による最悪ケースシーケンシャルなラデマッハ複雑性の厳密な制御を確立する。 0.73
Finally, we establish a tight contraction inequality for worst-case sequential Rademacher complexity. 最後に、最悪ケースシーケンシャルなRademacher複雑性に対して、厳密な収縮不等式を確立する。 0.52
The above constitutes the resolution of a number of outstanding open problems in extending the classical theory of empirical processes to the sequential case, and, in turn, establishes sharp results for online learning. 上記は、経験的過程の古典的理論を逐次ケースに拡張する上で顕著なオープン問題の数の解決を構成し、その結果、オンライン学習のための鋭い結果を確立します。 0.64
Keywords: Online learning, Majorizing Measures, Sequential Rademacher Complexity, Chain- キーワード:オンライン学習、メジャー化対策、シーケンシャルラデマチャー複雑性、チェーン- 0.75
ing 1 Introduction ing 1 はじめに 0.74
One of the primary goals of learning theory is to understand how the sample complexity of learning depends on the complexity of the model. 学習理論の主な目的の1つは、学習のサンプルの複雑さがモデルの複雑さに依存するかを理解することである。 0.85
Classically, much of the research focused on the case where data are drawn independently from some population distribution. 伝統的に、研究の多くは、ある人口分布から独立してデータが引き出されるケースに焦点を当てた。 0.71
The mismatch between sample and population inevitably leads to questions of uniform convergence. サンプルと人口のミスマッチは必然的に一様収束の問題につながる。 0.61
To answer such questions, the theory of empirical processes was developed, with seminal papers establishing nonasymptotic rates of convergence in terms of covering numbers, chaining (Dudley, 1973), VC dimension (Vapnik & Chervonenkis, 1971), and scale-sensitive combinatorial parameters (Bartlett et al. そのような疑問に答えるために、経験過程の理論が発展し、数、連鎖(Dudley, 1973)、VC次元(Vapnik & Chervonenkis, 1971)、スケールに敏感な組合せパラメータ(Bartlett et al)という用語で収束の漸近速度を確立した。 0.72
, 1996; Kearns & Schapire, 1994). 1996年、kearns & schapire、1994年)。 0.75
A central notion of complexity is the (empirical) Rademacher complexity (Gin´e & Zinn, 1984), 複雑性の中心的な概念は(現代的)ラデマチャー複雑性(Gin ́e & Zinn, 1984)である。 0.69
1 2 0 2 b e F 2 1 2 0 2 b e F 2 0.85
] L M . t a t s [ ]L M . t a t s [ 0.84
1 v 9 2 7 1 0 1 v 9 2 7 1 0 0.85
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
defined for a data set z1, . データセット z1 に定義します。 0.75
. . , zn ∈ Z and a real-valued function class F on Z as . . , zn ∈ Z と Z 上の実値関数類 F を言う。 0.86
where εt are independent Rademacher random variables. εt は独立な Rademacher 確率変数である。 0.66
It is a classical result that bRn(F) deter- bRn(F)デターは古典的な結果である 0.74
mines the rate of convergence of uniform laws of large numbers over the function class F. Sharp upper and lower bounds on sample complexity of prediction and estimation have been established via Rademacher complexity and its localized versions (Bartlett & Mendelson, 2002). シャープの上と下の境界は、Rademacher複雑性とその局所化バージョン(Bartlett & Mendelson, 2002)を通して、予測と推定のサンプルの複雑さに関するものである。
訳抜け防止モード: 関数クラス F 上の大数の一様法則の収束速度をマイニングする。Rademacher の複雑性により、予測と推定のサンプル複雑性に関するシャープ上界と下界が確立されている。 そしてローカライズされた版(Bartlett & Mendelson、2002年)。
0.68
Just as important as the introduction of these notions of complexity has been the development of the relationships among them. これらの複雑さの概念の導入と同じくらい重要であるのは、それらの間の関係の発展である。 0.69
In particular, it is a result of Dudley (Dudley, 1973) that the Rademacher complexity is controlled by integrating a function of the covering number and this, 特に、ダドリー (Dudley, 1973) の結果、ラデマッハ複雑性は被覆数とこれとの函数を統合することによって制御される。 0.63
1 bRn(F) = Eε"sup 1 bRn(F) = Eε"sup 0.90
f∈F εtf (zt)# , f∈F εtf (zt)# , 0.78
1 n nXt=1 (1) 1n nXt=1 (1) 0.73
英語(論文から抽出)日本語訳スコア
in turn, can be bounded by the integral of the square root of the scale-sensitive combinatorial dimension, as shown by Mendelson & Vershynin (2003); Rudelson & Vershynin (2006). 逆に、Mendelson & Vershynin (2003), Rudelson & Vershynin (2006) で示されているように、スケール感受性の組合せ次元の平方根の積分によって有界にすることができる。 0.74
On the other hand, closely related Gaussian averages, obtained by replacing Rademacher with Gaussian random variables in (1), are known to be tightly (up to a constant) controlled via generic chaining and majorizing measures (Fernique, 1975; Talagrand, 1996), and may be strictly smaller than the bounds provided by Dudley’s chaining technique. 一方、(1)でRademacherをガウス変数に置き換えることによって得られる密接に関連したガウス平均は、ジェネリック連鎖とメジャー化手段(Fernique、1975; Talagrand、1996)によって厳密に(定数まで)制御されることが知られており、Dudleyの連鎖技術によって提供される境界よりも厳密に小さいかもしれません。 0.67
It is fair to say that the foundations of statistical learning when the data are i.i.d. データがi.i.dである場合の統計学の基礎は公平であると言える。 0.76
and presented all at once are fairly well-understood. すべて一度に提示することはかなりよく理解されています。 0.36
In contrast to statistical learning, in online learning the data arrive sequentially. 統計学習とは対照的に、オンライン学習ではデータが順次到着します。 0.70
The learner is tested on the new datum, observes the outcome, and updates the model with the new information. 学習者は、新しいdatum上でテストされ、結果を観察し、新しい情報でモデルを更新する。 0.81
In the common formulation of the online learning problem, the sequence as treated as non-stochastic (individual), or even adaptively and adversarially chosen (Cesa-Bianchi & Lugosi, 2006). オンライン学習問題の一般的な定式化では、非定型的(個人的)あるいは適応的かつ敵対的に選択される(cesa-bianchi & lugosi, 2006)。 0.73
For online binary classification, the fundamental result of Littlestone (1988) (and the agnostic generalization of Ben-David et al. オンライン二項分類の場合、Littlestone (1988) の基本的な結果と Ben-David et al の非依存的な一般化である。 0.69
(2009)) characterizes learnability in terms of finiteness of Littlestone dimension, the counterpart to VC dimension in statistical learning. 2009)) は、統計学習におけるVC次元と同等であるリトルストーン次元の有限性の観点から学習可能性を特徴づける。 0.67
Motivated by these results, Rakhlin et al. これらの結果に動機づけられ、Rakhlinら。 0.64
(2010) developed sequential analogues of Rademacher averages, covering numbers, and scale-sensitive dimensions, and showed that sample complexity of online learning can be related to these quantities. (2010)では,Rademacher平均値,被覆数,スケール感性次元の逐次アナログが開発され,オンライン学習におけるサンプルの複雑さがこれらの量と関係があることが確認された。 0.64
For example, for online supervised learning with indicator or absolute value loss, the minimax regret Vn(F), defined as the average loss of an algorithm minus the average prediction loss of the best model in F, is—up to a multiplicative factor of 2—equal to the worst-case sequential Rademacher complexity of F (Rakhlin et al. 例えば、指標や絶対値損失のあるオンライン教師付き学習の場合、アルゴリズムの平均損失として定義されるミニマックス後悔Vn(F)は、Fの最良のモデルの平均予測損失を減らし、Fの最悪のシーケンシャルなラデマッハ複雑性(Rakhlin et al)に等しい乗算係数2までである。 0.80
, 2010), a quantity we shall define below. 2010年) 以下で定義する量。 0.46
Furthermore, in parallel to the close relationship between statistical learning and uniform laws of large numbers, the sample complexity of online learning can be viewed through the lens of uniform martingale laws of large numbers (Rakhlin et al. さらに、統計的学習と大数の一様法則との密接な関係と並行して、オンライン学習のサンプル複雑さは、大数の一様マーチンゲール法則(Rakhlin et al.)のレンズを通して見ることができる。 0.73
, 2015). In recent years, sequential complexities have been used in an increasing range of topics, including private learning (Alon et al. , 2015). 近年では,プライベートラーニング(alon et al)など幅広いトピックにおいて,逐次的複雑度が使用されている。 0.78
, 2019; Bun et al. 2019年、bun et al。 0.67
, 2020; Jung et al. 2020年、Jung et al。 0.69
, 2020; Ghazi et al. 2020年、Ghaziら。 0.55
, 2020), adversarial robustness of sampling streaming data (Alon et al. ストリーミングデータ(Alon et al., 2020)のサンプリングの敵対的堅牢性。 0.72
, 2021), denoising in autoregressive models (Hall et al. 2021年)、自己回帰モデル(Hall et al。 0.53
, 2016; Foster et al. 2016年、Fosterら。 0.51
, 2020), contextual bandits (Foster & Rakhlin, 2020), among others. 以下、2020年)、コンテクスト・バンディット(foster & rakhlin、2020年)、その他。 0.60
While many of the parallels between the classical results in empirical process theory and their sequential (or martingale) counterparts have been established, a number of the fundamental relationships and techniques (such as generic chaining, a sharp contraction principle) are still missing. 経験的プロセス理論における古典的結果とその連続的な(またはマーチンゲール)同等物の間の平行の多くは確立されているが、多くの基本的な関係と技術(一般的な連鎖、鋭い収縮原理など)は未だに欠けている。 0.74
This paper addresses some of these gaps. 本稿ではこれらのギャップに対処する。 0.55
Before stating our contributions, we define the main object of study, sequential Rademacher averages. 私たちの貢献を述べる前に、研究の主な目的、シーケンシャルラデマチャー平均を定義します。 0.69
We are primarily interested in certain dyadic martingales. 私達は特定のdyadic martingalesに主に興味があります。 0.63
As before, let ε1, . 前と同様に、ε1 を 。 0.67
. . , εn be independent Rademacher random variables, and let zt(ε)1≤t≤n be a predictable process with respect to the filtration At = σ(ε1, . . . εn を独立ラデマッハ確率変数とし、zt(ε)1ψthtmln を σ(ε1, ) での濾過に関して予測可能な過程とする。 0.80
. . , εt); equivalently, we can think of z as a complete binary tree of depth n with each vertex zt(ε) labelled by an element of Z according to the path ε1, . . . 同様に、z を深さ n の完全な二分木とみなすことができ、各頂点 zt(ε) は経路 ε1, . に従って Z の元によってラベル付けされる。 0.82
. . , εt−1 (see the bottom of this section for complete definitions). . . εt−1 である(完全な定義については、このセクションの下部を参照)。 0.74
Given a real-valued function class F on Z, we follow (Rakhlin et al. Z 上の実数値関数クラス F が与えられたとき、我々は (Rakhlin et al) に従う。 0.71
, 2010) and define the sequential Rademacher complexity as シーケンシャルRademacherの複雑さを定義します。 0.45
Rn(F, z) = Eε"sup Rn(F, z) = Eε"sup 0.93
f∈F εtf (zt(ε))# f∈F εtf (zt(ε))# 0.77
1 n nXt=1 (2) 1n nXt=1 (2) 0.73
We note that if z is a tree whose labels are constant as a function of t, i.e., zt(ε) is independent of ε, we recover the classical notion of Rademacher complexity in (1). z が t の函数としてラベルが定数である木、すなわち zt(ε) が ε とは独立であるならば、(1) におけるラデマッハ複雑性の古典的な概念を回復する。 0.69
Much of (Rakhlin et al. 多く (rakhlin et al.)。 0.78
, 2010) is devoted to demonstrating that this is, in some sense, the “correct” extension to the online case and this paper is primarily concerned with developing upper bounds for this quantity in terms of various complexity measures of F. このことは、ある意味では、オンラインの場合の「正しい」拡張であり、本論文は、Fの様々な複雑さ対策の観点から、この量について上界を発達させることに主眼を置いている。 0.66
2 2 0.85
英語(論文から抽出)日本語訳スコア
The structure of the paper is given by the order of the following contributions: 論文の構造は、次の貢献の順序で与えられます。 0.66
1. We introduce a notion of majorizing measure in the online setting and show that the sequential 1. オンライン設定におけるメジャー化尺度の概念を導入し、シーケンシャルが示す。 0.76
Rademacher complexity is bounded: Rademacher の複雑さは次の通りです。 0.48
Rn(F, z) . Rn(F, z) である。 0.76
inf supp µ⊆F(z) inf supp (複数形 supps) 0.79
sup v∈F(z) ε∈{±1}n sup v∈F(z) ε∈{±1}n 0.86
1 √nZ 1 0 slog 1 ^nZ1 0 slog 0.80
1 µ(Bδ(v, ε)) 1 μ(Bδ(v, ε)) 0.89
dδ (3) The upper bound can be viewed as an analogue of the corresponding upper bound via majorizing measures (Fernique, 1975; Talagrand, 1996). dδ (3) 上界は、メジャー化測度(Fernique, 1975; Talagrand, 1996)を通して対応する上界の類似と見なすことができる。 0.78
In proving the above, we introduce a new concentration inequality for martingales. 上記の証明では、マーチンゲールの新しい濃度不等式を紹介します。 0.56
2. We extend the notion of fractional cover introduced by Alon et al. 2. Alon et alによって導入された分数被覆の概念を拡張します。 0.70
(2021) to real-valued function classes and show that this notion of complexity controls the upper bound given by a majorizing measure. (2021) 実数値関数クラスに対して、この複雑性の概念がメジャー化測度によって与えられる上限を制御していることを示す。
訳抜け防止モード: (2021 ) to real-valued function class and show that この複雑性の概念は 最大化測度によって与えられる上限を制御します
0.77
3. We prove a sequential analogue of the results of Mendelson & Vershynin (2003) for fractional 3. 我々は分数に対するmendelson & vershynin (2003)の結果の逐次類似性を証明する 0.83
covers, showing that N′(F, δ) . カバーして N′(F, δ)。 0.63
(cid:18) C δ(cid:19)fatcδ(F) (cid:18)c δ(cid:19)fatcδ(F) 0.84
(4) thereby resolving an open question raised in (Rakhlin et al. (4) したがって、 (Rakhlin et al) で提起されたオープンな疑問を解決する。 0.68
, 2015). Here fat is a sequential scale-sensitive dimension, defined below. , 2015). ここで、脂肪は下記の連続的なスケール感応次元である。 0.75
4. We prove a sequential analogue of the results of Rudelson & Vershynin (2006), showing that 4. Rudelson & Vershynin(2006)の結果の連続的な類似性を証明する。 0.76
Rn(F) . Z 1 0 pfatδ(F)dδ Rn(F)。 Z1 0 pfatδ(F)dδ 0.80
(5) where Rn(F) = supz Rn(F, z) is the worst-case Rademacher complexity over all trees z. (5) ここで Rn(F) = supz Rn(F, z) は全ての木 z 上の最悪の場合である。 0.80
For sufficiently simple classes F, we show that this inequality can be reversed and apply the result to prove a dimension-independen t contraction inequality for sequential Rademacher complexity, thereby resolving another open problem from (Rakhlin et al. 十分に単純なクラス F に対して、この不等式は逆転し、その結果をシーケンシャルなラデマッハ複雑性に対して次元非独立な縮約不等式を証明することを示し、それによって (Rakhlin et al) から別の開問題を解く。 0.58
, 2015). Notation. , 2015). 表記。 0.70
Bold lower-case letters will denote complete binary trees. 折りたたみ小文字は完全な二分木を表す。 0.57
Given a depth n binary tree v, denote by ε ∈ {±1}n a path from the root to a leaf of the tree, where εt = −1 signifies that node t + 1 of the path is the left child of node t. A real-valued tree is a tree labelled by real numbers. 深さ n の二分木 v が与えられたとき、 ε ∈ {±1}n は木の根から葉への経路を表し、そこで εt = −1 は経路のノード t + 1 がノード t の左子であることを表す。 0.66
If v, v′ are real-valued trees, define by v(ε) = (v1(ε), . v, v′ が実値木であれば、v(ε) = (v1(ε) で定義する。 0.81
. . , vn(ε)) the values of v on the path ε, and let . . , vn(ε)) は経路 ε 上の v の値であり、 0.82
Given a real-valued tree v, we let Tv be the associated tree process, the random variable 実数値木 v が与えられたとき、Tv を関連するツリープロセス、ランダム変数とする。 0.69
nXt=1(cid:0)vt(ε) − v′t(ε)(cid:1)2 . nXt=1(cid:0)vt(ε) − v′t(ε)(cid:1)2。 0.76
(cid:12)(cid:12)(cid :12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)2 = nXt=1 (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)2 = nXt=1 0.71
εtvt(ε). Tv(ε) = εtvt(ε)。 Tv(ε) = 0.85
(6) (7) If z is a Z-valued tree that is clear from context and f is a real-valued function on Z, we often abbreviate Tf = T f (z) and write F(z) = {f ◦ z : f ∈ F}. (6) (7) z が文脈から明らかな Z 値木であり、f が Z 上の実値関数であるなら、しばしば Tf = T f (z) を省略し、F(z) = {f y z : f ∈ F} と書く。 0.86
For two quantities a, b, we say that a . 2 つの量 a, b に対して、a は成り立つ。 0.61
b if there exists a universal constant C, independent of the quantities that determine a, b, such that a ≤ Cb. b が普遍定数 C が存在するとき、a ≤ Cb であるような a, b を決定する量に依存しない。 0.82
3 3 0.85
英語(論文から抽出)日本語訳スコア
2 Majorizing Measures and Upper Bounds 2 メジャー化措置と上界 0.69
In the classical setting, one of the most fundamental quantities that controls the size of the supremum of a stochastic process is the covering number of the underlying index set, i.e., the minimal number of points such that every member of the index set is within δ of one of the chosen points. 古典的設定において、確率過程の上限の大きさを制御する最も基本的な量の1つは、根底にある指数集合の被覆数、すなわち、指数集合のすべてのメンバーが選択された点のδ内であるような最小の点数である。
訳抜け防止モード: 古典的設定において,最も基本的な量の1つ 確率過程の基点の大きさを制御する 基本となるインデックスセットのカバー数、すなわち、その数です。 最小の点数が 指数集合のすべての元は、選択された点の1つのうちの δ 以内である。
0.84
In (Rakhlin et al. で (Rakhlin et al。 0.77
, 2015), this definition is extended to the sequential setting: Definition 1. この定義は次のシーケンシャルな設定に拡張される。 0.45
Let z be a Z-valued tree of depth n and let F ⊂ RZ. z を深さ n の Z 値木とし、F を RZ とする。 0.81
A covering at scale δ is a set of binary real-valued trees v1,··· , vN such that for all f ∈ F and all ε ∈ {±1}n, there is some j such that (8) スケール δ は、すべての f ∈ f とすべての ε ∈ {±1}n に対して (8) となる j が存在するような二元実数値木 v1,···· , vn の集合である。 0.85
The covering number N (F, δ, z) of a class F for a tree z at scale δ is the minimal N such that there exists a δ-covering of size N . スケール δ における木 z に対するクラス F の被覆数 N (F, δ, z) は、大きさ N の δ 被覆が存在するような最小の N である。 0.89
(cid:12)(cid:12)(cid :12)(cid:12)f (z(ε)) − v (cid:12)(cid:12)(cid :12)(cid:12)f(z(ε)) − v 0.86
j(ε)(cid:12)(cid:12)(ci d:12)(cid:12)2 j(ε)(cid:12)(cid:12)(ci d:12)2 0.98
≤ nδ2. As noted in (Rakhlin & Sridharan, 2015; Rakhlin et al. ≤ nδ2。 Rakhlin & Sridharan, 2015; Rakhlin et al)に記載されている。 0.79
, 2010), we can recover the classical definition by restricting to trees z, whose values are path-independent. 2010年) 値は経路非依存である木 z に制限することで古典的な定義を復元することができる。 0.73
In analogy with the statistical learning regime, we may apply the chaining technique to bound the sequential Rademacher complexity in terms of these covering numbers; in fact, for uniformly bounded function classes, (Rakhlin et al. 統計的学習体制と類似して、これらの被覆数の観点からシーケンシャルラデマチャー複雑性に連鎖技術を適用することができる; 実際、一様境界関数クラス(Rakhlin et al.)に対しては、(Rakhlin et al.)。 0.66
, 2015, Theorem 3) guarantees , 2015, theorem 3) が保証する 0.86
Rn(F, z) . Rn(F, z) である。 0.76
inf α>0(cid:18)α + inf α>0(cid:18)α + 0.91
1 √nZ 1 α plog N (F, δ, z)dδ(cid:19) . 1 ^nZ1 α plog N (F, δ, z)dδ(cid:19) 。 0.82
(9) Looking back to the classical case, we note that the generic chaining and majorizing measure approaches (Talagrand, 2014, 1996; Fernique, 1975) would suggest that the bound in (9) is not tight in all cases. (9) 古典的ケースを振り返ると、一般的な連鎖化と偏化測度アプローチ(Talagrand, 2014; 1996; Fernique, 1975)は、すべてのケースにおいて (9) の有界性は厳密でないことを示唆する。 0.83
In the classical setting, generic chaining approaches give significant improvements over the Dudley entropy integral, as can be seen, for example, from the case of ellipsoids in Hilbert space (Talagrand, 2014, Sec 2.5). 古典的な設定では、一般的な連鎖のアプローチは、例えばヒルベルト空間の楕円体の場合(Talagrand, 2014 Sec 2.5)から見られるように、ダドリーエントロピー積分を有意に改善する。 0.65
Such improvements go well beyond logarithmic factors. このような改善は対数的要因をはるかに超える。 0.57
Furthermore, Rakhlin et al. さらに、Rakhlinらも。 0.54
(2015) note that a clean, n-independent upper bound for the sequential covering number in terms of the sequential scale-sensitive dimension in the style of (Mendelson & Vershynin, 2003) is not yet known, resulting in additional looseness when using (9). (2015)は、(Mendelson & Vershynin, 2003)のスタイルにおける連続的スケール感受性次元の点において、連続被覆数に対するクリーンでn非依存な上限がまだ知られていないことに注意し、(9)の使用時に追加の緩みをもたらす。 0.65
We now introduce a generalization of majorizing measures to the sequential case. 本稿では,逐次的な対策の一般化について述べる。 0.65
Definition 2. For a collection of [0, 1]-valued binary trees V of depth n, for v ∈ V and for a fixed path ε, let Bδ(v, ε) be the set of trees v′ in V such that ||v(ε) − v′(ε)||2 ≤ nδ2. 定義2。 深さ n, v ∈ V と固定経路 ε に対して[0, 1] の値を持つ二分木 V の集合に対して、Bδ(v, ε) を V 内の木 v′ の集合とし、||v(ε) − v′(ε)||2 ≤ nδ2 とする。 0.77
For a measure µ on the set of [0, 1]-valued trees of depth n, and 0 ≤ α ≤ 1, let 深さ n の [0, 1]-値木と 0 ≤ α ≤ 1 の成す集合上の測度 μ に対して、 0.81
1 √nZ 1 α slog 1 ^nZ1 α slog 0.80
1 µ(Bδ(v, ε)) 1 μ(Bδ(v, ε)) 0.89
dδ. (10) We let dδ。 (10) 我々は 0.79
I α µ (v, ε) = α + I α μ (v, ε) = α + 0.85
I α µ = sup v∈V I α μ = sup v∈V 0.92
ε∈{±1}n I α µ (v, ε) ε∈{±1}n I α μ (v, ε) 0.87
I α F,z = inf I α F,z = inf 0.85
supp µ⊆F(z) supp (複数形 supps) 0.74
I α µ I α F = sup I α μ I α F = sup 0.85
I α F,z z (11) I α F,z z (11) 0.85
To see that this definition extends the classical one, consider the special case where V is restricted to contain only trees that are constant on vertices of equal depth, corresponding to the batch setting; thus, the path ε in the above definition becomes irrelevant and we recover the classical notion of a majorizing measure (Talagrand, 2014, p. 177). この定義が古典的なものを拡張することを確かめるために、V がバッチ設定に対応する等しい深さの頂点に定数を持つ木のみを含むように制限されている特別な場合を考える。
訳抜け防止モード: この定義が古典的定義を拡張することを確かめる。 V が制限された特別な場合を考える バッチ設定に対応する,深さが等しい頂点に一定である木のみを含む したがって、上記の定義における ε の経路は無関係となる。 そして古典的な偏微分測度の概念を回復する(Talagrand, 2014, pp. 177 )。
0.81
This notion of complexity is not very useful unless it actually controls the size of our stochastic process; fortunately, we have: この複雑さの概念は、私たちの確率的プロセスのサイズを実際に制御しない限り、あまり役に立たない。 0.74
4 4 0.85
英語(論文から抽出)日本語訳スコア
Theorem 3. Let F be a separable [0, 1]-valued function class on Z. 理論3。 F を Z 上の分離可能な [0, 1] 値関数クラスとする。 0.73
Let z be a Z-valued binary tree of depth n. Then with probability at least 1 − ρ over ε and for any α ≥ 0 z を深さ n の Z 値二分木とし、かつ確率が ε 上の少なくとも 1 − ρ かつ任意の α ≥ 0 に対して 0.76
In particular, the sequential Rademacher complexity is bounded by 特に、シーケンシャルなRademacherの複雑さは有界である。 0.63
n sup f∈F(cid:18) 1 α>0α + n sup f∈F(cid:18) 1 α>0*α + 0.81
T f (z)(ε)(cid:19) . T f(z)(ε)(cid:19)。 0.86
I α F,z +slog 1 I α F,z +slog 1 0.92
n ρ inf supp µ⊂F(z) n ρ inf supp (複数形 supps) 0.82
1 √nZ 1 α slog 1 ^nZ1 α slog 0.80
sup v∈F(z) ε∈{±1}n sup v∈F(z) ε∈{±1}n 0.86
(12) (13) 1 (12) (13) 1 0.85
µ(Bδ(v, ε)) μ(Bδ(v, ε)) 0.94
dδ Rn(F, z) . dδ! Rn(F, z) である。 0.60
inf The proof of Theorem 3 is somewhat technical and thus deferred to Appendix A. inf Theorem 3 の証明は幾分技術的であり、したがって Appendix A に導かれる。 0.80
The proof rests on the following new martingale concentration inequality that can be viewed as a stronger version of (Bartlett et al. この証明は、(Bartlett et al)のより強いバージョンと見なせる新しいマルティンゲール濃度の不等式に基づいている。 0.69
, 2008, Lemma 2): 2008年、Lemma 2)。 0.56
Lemma 4. Let v be a [−1, 1]-labelled binary tree of depth n and ε1, . レマ4。 v を深度 n と ε1, . の [−1, 1] ラベル付き二元木とする。 0.65
. . , εn independent Rademacher variables. . . εn 独立な Rademacher 変数。 0.83
Then there is a constant C such that with probability at least 1 − ρ over the εt, このとき、εt 上の少なくとも 1 − ρ の確率を持つ定数 c が存在する。 0.84
|Pn ||v(ε)||qlog 1 |Pn ||v(ε)||qlog 1 0.72
t=1 εtvt(ε)| ρ + log log e√n ||v(ε)|| t=1 εtvt(ε)| ρ + log log e n ||v(ε)|| 0.82
≤ C (14) For the probabilist, an equivalent rephrasing of Lemma 4 is to let Mt be a martingale sequence whose differences are conditionally symmetric and bounded in absolute value by 1. ≤C (14) 確率論者にとって、補題4の等価な再帰は、mt を条件付き対称で絶対値が 1 で有界なマルティンゲール列とすることである。 0.81
Let [M ]t be its quadratic variation process. M をその二次的変化過程とみなす。 0.60
Then the above says that with high probability, そして、上記は確率が高いと言います。 0.82
r[M ]n(cid:16)log 1 r[M ]n(cid:16)log 1 1.00
|Mn| ρ + log log en |Mn| ρ + log log en 0.92
[M ]n(cid:17) . [M ]n(cid:17)。 0.85
1 (15) One way of thinking about this is to consider it as a non-asymptotic version of the martingale Laws of the Iterated Logarithm proved in (de la Pe˜na, 1999; Bercu & Touati, 2008). 1 (15) これについて考える一つの方法は、反復対数のマルティンゲール法則の非漸近的バージョンと考えることである(de la pe ína, 1999; bercu & touati, 2008)。 0.80
Much like the classical case, structural results of the function class can help control the ma- 古典の場合と同様に、関数クラスの構造結果はmaを制御するのに役立ちます。 0.74
jorizing measure’s upper bound. jorizing measureの上限は上限だ。 0.66
One example of such a result concerns Lipschitz compositions: Proposition 5. このような結果の1つの例はリプシッツ合成である。 0.48
Let F ⊆ [0, 1]Z and let ℓ : [0, 1] → [0, 1] be L-Lipschitz. F を [0, 1]Z とし、l : [0, 1] → [0, 1] を L-Lipschitz とする。 0.90
Then I α ℓ◦F,z ≤ LI α F,z. そして、iα l,F,z ≤ LI α F,z。 0.84
While majorizing measures in the classical case fully characterize the associated Gaussian process, constructing these multi-scale measures for a given class of functions at hand is notoriously difficult. 古典的な場合のメジャー化は、関連するガウス過程を完全に特徴づけるが、与えられた関数のクラスに対するこれらのマルチスケール測度の構築は、悪名高いほど困難である。 0.57
In the following section, inspired by (Alon et al. 以下の節では (Alon et al) にインスパイアされている。 0.57
, 2021) for the binary-valued case, we introduce a single-scale measure that is easier to analyze than the multi-scale construction. 2021年) の二値化事例では, マルチスケール化よりも解析が容易な単スケール化手法を提案する。 0.68
3 Fractional Covers As we just remarked, the multi-scale nature of the majorizing measure makes it difficult to apply the technique to practical function classes. 3つの分数カバー 先ほど述べたように、メジャー化測度のマルチスケール性は、実際的な関数クラスにこの技術を適用するのを困難にしている。
訳抜け防止モード: 3つの分数カバー 先ほど述べたように、主要な尺度のマルチスケール性は この手法を実用的機能クラスに適用することは困難である。
0.64
Thus we introduce the fractional covering number for real-valued function classes as a single-scale alternative: そこで,実数値関数クラスに対する分数被覆数を単一スケールの代替として導入する。 0.64
5 5 0.85
英語(論文から抽出)日本語訳スコア
Definition 6. Let z a binary, Z-valued tree of depth n and let F ⊂ RZ. 定義6。 z を深さ n の二進 Z 値木とし、F を RZ とする。 0.76
A measure µ on the space of binary real-valued trees of depth n is a fractional covering at scale δ of size γ if for all f ∈ F and ε ∈ {±1}n, we have 深さ n の二進実値木の空間上の測度 μ は、すべての f ∈ F と ε ∈ {±1}n に対して、大きさ γ のスケール δ における分数被覆である。 0.83
µ(cid:16)nv : ||v(ε) − f (z(ε))||2 ≤ nδ2o(cid:17) ≥ μ(cid:16)nv : ||v(ε) − f(z(ε))||2 ≤ nδ2o(cid:17) ≥ 0.83
1 γ . (16) 1 γ . (16) 0.85
The fractional covering number N′(F, δ, z) of F at scale δ is the smallest γ such that there exists a fractional cover of F at scale δ of size γ. スケール δ における F の分数被覆数 N′(F, δ, z) は、サイズ γ のスケール δ において F の分数被覆が存在するような最小の γ である。 0.91
Let N′(F, δ) = supz N′(F, δ, z). N′(F, δ) = supz N′(F, δ, z) とする。 0.89
We see immediately (and prove in Appendix D) that this new notion of size is controlled by the 我々は、この新しい大きさの概念が、すぐに(そしてAppendix Dで証明)、制御されるのを見る。 0.66
sequential covering number introduced in (Rakhlin et al. Rakhlin et al. で導入されたシーケンシャルカバー番号。 0.57
, 2010): Lemma 7. 2010年 - レマ7世。 0.44
For any z, F, δ, we have N′(F, δ, z) ≤ N (F, δ, z). 任意の z, F, δ に対して、N′(F, δ, z) ≤ N (F, δ, z) を持つ。 0.87
Interestingly, at least in the classical case, the reverse inequality holds as well: 興味深いことに、少なくとも古典的な場合、逆不等式も同様に成り立つ。 0.58
Lemma 8. Let z be a tree whose labels are constant as a function of depth. 第8回。 z をラベルが深さの関数として定数である木とする。 0.62
Then N (F, 2δ, z) ≤ N′(F, δ, z) ≤ N (F, δ, z). すると N (F, 2δ, z) ≤ N′(F, δ, z) ≤ N (F, δ, z) となる。 0.95
The proof of Lemma 8 is deferred to Appendix D. Thus, at least in the classical case, the fractional covering number does not provide any improvement over the classical notion of covering number; whether such a result holds in the sequential case remains open, due to the lack of packingcovering duality in this setting. 補題8の証明は付録dに延期されるので、少なくとも古典的な場合では、分数被覆数(英語版)は被覆数(英語版)(covering number)の古典的な概念よりも改善されない。
訳抜け防止モード: Lemma 8の証明は付録Dに延期される。 少なくとも古典的なケースでは、分数被覆数は被覆数という古典的な概念を何ら改善しない。 パッキングの欠如が原因でこの設定の二重性をカバーします。
0.51
To understand the connection between fractional covers and majorizing measures, we note that 分数表紙とメジャー化対策の関係を理解するために、我々は注意してください。 0.55
Definition 6 can be rephrased to say that µδ is a δ-fractional cover of size γ if 定義 6 は、μδ がサイズ γ の δ-フラクショナル被覆であると言い換えることができる。 0.83
Applying Theorem 3 and setting α = 0 for ease of exposition, we see that, after putting the supremum inside of the integral, Theorem 3 と α = 0 をエクスポジションの容易性に適用すると、積分の最高値が積分の内側に置かれることが分かる。 0.73
log sup f∈F ログ sup f∈F 0.71
ε∈{±1}n 1 µδ (Bδ(f (z), ε)) ε∈{±1}n 1 μδ (Bδ(f(z), ε)) 0.88
= log γ. は log γ である。 0.73
(17) E"sup (17) E"sup 0.85
f∈F Tf (ε)# . f∈F Tf (ε)#。 0.66
√n sup ≤ √nZ 1 ~n sup ≤ ~nZ 1 0.67
f∈F ε∈{±1}nZ 1 f∈F ε∈{±1}nZ 1 0.75
0 slog slog 0 slog slog 0.85
0 sup f∈F ε∈{±1}n 0 sup f∈F ε∈{±1}n 0.81
1 µ(Bδ(f (z), ε) 1 μ(Bδ(f(z), ε) 0.85
dδ 1 µ(Bδ(f (z), ε)) dδ 1 μ(Bδ(f(z), ε)) 0.83
dδ (18) (19) dδ (18) (19) 0.83
for all measures µ. すべての測定μのため。 0.68
The last integrand above almost looks like the left-hand side of (17) and so 上の最後の積分は (17) の左側のように見えます。 0.69
we might hope that we can replace this integrand with plog N′(F, δ, z). この積分を plog N′(F, δ, z) に置き換えることを望むかもしれない。 0.70
The problem with this last step is that the measure µδ of the fractional cover is allowed to depend on the scale while the majorizing measure is not; thus it is not obvious that a chaining bound with fractional covers follows from Theorem 3. これの問題点 最後のステップは、分数被覆の測度 μδ がスケールに依存することが許されるが、分数化測度がそうでないため、分数被覆に束縛された鎖が定理3から従うことは明らかではない。 0.66
Fortunately, as the following proposition demonstrates, we are still able to control the majorizing measure by fractional covers and thus the above critique does not apply: 幸運にも、以下の命題が示すように、分数被覆によるメジャー化測度を制御できるので、上記の批判は適用されない。 0.60
Proposition 9. Let z be a Z-valued binary tree of depth n and let F be a class of real-valued functions on Z. 命題9。 z を深度 n の Z 値二項木とし、F を Z 上の実値関数のクラスとする。 0.69
Then In other words, fractional covers dominate majorizing measures, up to a constant. その後 言い換えると、分数被覆は、定数まで主要な測度を支配する。 0.62
I α F,z . α + I α F,z。 α + 0.81
1 √nZ 1 α plog N′(F, δ, z)dδ 1 ^nZ1 α plog N′(F, δ, z)dδ 0.85
(20) 6 (20) 6 0.85
英語(論文から抽出)日本語訳スコア
A proof of Proposition 9 can be found in Appendix D. An immediate corollary of the above, 命題9の証明は Appendix D で見ることができる。 0.47
which follows from combining Theorem 3 and Proposition 9 is Theorem 3 と Proposition 9 を組み合わせることから続く。 0.77
Corollary 10. Let F be a separable [0, 1]-valued function class on Z. 定員10名。 F を Z 上の分離可能な [0, 1] 値関数クラスとする。 0.70
Let z be a Z-valued binary tree of depth n. Let N′(F, δ) be the fractional covering number at scale δ. z を深さ n の Z 値のバイナリツリーとし、N′(F, δ) をスケール δ における分数被覆数とする。 0.75
Then with probability at least 1 − ρ over ε, for all α ≥ 0, すると、すべての α ≥ 0 に対して ε 上の確率が 1 − ρ である。 0.75
In particular, the sequential Rademacher complexity is bounded by the Dudley integral: 特に、シーケンシャルラデマチャーの複雑さはダドリー積分によって有界である。 0.56
f∈F(cid:18) 1 f∈F(cid:18) 1 0.71
sup n T f (z)(ε)(cid:19) . sup n T f(z)(ε)(cid:19)。 0.85
α + Rn(F, z) . α + Rn(F, z) である。 0.81
inf α>0(cid:18)α + inf α>0(cid:18)α + 0.91
1 α plog N′(F, δ, z)dδ +s log 1 √nZ 1 α plog N′(F, δ, z)dδ(cid:19) . 1 α plog N′(F, δ, z)dδ +s log 1,nZ 1 α plog N′(F, δ, z)dδ(cid:19) 。 0.88
√nZ 1 n 1 ρ ^nZ1 n 1 ρ 0.81
. (21) If we apply Lemma 7 to Corollary 10, we recover the chaining bound with respect to sequential non-fractional covers of (Rakhlin et al. . (21) Lemma 7 を Corollary 10 に適用すると、(Rakhlin et al.) の連続非フラクショナル被覆に関して結合された連鎖を回復します。 0.80
, 2015). As a first application of our results, using the techniques of Rakhlin et al. , 2015). この結果の最初の応用として,rakhlinらによる手法を用いた。 0.80
(2015) we get a high-probability uniform deviations bound: (2015) 高い確率の均一な偏差を束縛する。 0.66
Corollary 11. Let Z1, . 定員11名。 Z1を、。 0.68
. . , Zt, . . . . 、Zt、。 . 0.79
. be a sequence of Z-valued random variables adapted to a filtration At and let F be a [0, 1]-valued function class on Z. . フィルタリングに適応した z-値確率変数の列で、f を z 上の[0, 1]-値関数クラスとする。
訳抜け防止モード: . フィルターに適応したZ-値のランダム変数の列である そして F を Z 上の [ 0 , 1] 値関数クラスとする。
0.83
Then with probability at least 1 − 4ρ, 確率は少なくとも 1 − 4ρ である。 0.79
sup f∈F(cid:12)(cid:12)(ci d:12)(cid:12)(cid:12 ) sup fvcf(cid:12)(cid:12) (cid:12)(cid:12) 0.79
1 n nXt=1 f (Zt) − E[f (Zt)|At](cid:12)(cid:12)(cid :12)(cid:12)(cid:12) 1n nXt=1 f(Zt) − E[f(Zt)|At](cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12) 0.70
. inf α>0 . inf α>0。 0.90
I α . inf α>0(cid:18)α + I α . inf α>0(cid:18)α + 0.88
ρ n F +s log 1 α plog N′(F, δ)dδ(cid:19) +s log 1 √nZ 1 ρ n F +s log 1 α plog N′(F, δ)dδ(cid:19) +s log 1 ^nZ 1 0.86
n 1 ρ Corollary 11 significantly improves on the results of (Rakhlin et al. n 1 ρ Corollary 11 は (Rakhlin et al) の結果を大きく改善する。 0.85
, 2015, Section 7) in two ways: first, we chain with respect majorizing measures and fractional covering numbers which are guaranteed to be at least as good as sequential covering numbers by Lemma 7; second, our bound removes an extraneous factor polynomial in log n and now matches the form of uniform concentration bounds from the classical regime. 第一に、我々は、Lemma 7による連続被覆数よりも少なくとも良いことが保証されているメジャー化措置と分数被覆数を尊重してチェーンします。第二に、私たちの有界は、ログnの余素な因子多項式を削除し、今、古典的な体制からの均一な濃度境界の形に一致します。
訳抜け防止モード: ,2015,第7節)2つの方法 : 第1に,主要な措置を尊重して連鎖する 数をさかのぼると 補題7による 逐次被覆数と同等の精度が保証されています 第二に、我々の境界はlog n 内の外因数多項式を取り除く そして今 古典体制からの 一様濃度境界の形式に一致しています
0.75
In the following section, we show how combinatorial properties of F can help us bound fractional covering numbers. 次のセクションでは、F の結合特性が分数被覆数を束ねるのにどのように役立つかを示します。 0.65
(22) (23) (24) (22) (23) (24) 0.85
4 Fractional Covering and Fat-Shattering Dimension 4 フラクショナル被覆と脂肪散乱寸法 0.81
Thus far, we have been focused on somewhat abstract results, providing upper bounds on stochastic processes in terms of majorizing measures and fractional covering numbers without any evidence that these new quantities improve on the sequential covering numbers introduced in Rakhlin et al. これまでのところ、我々はいくつかの抽象的な結果に焦点を当てており、これらの新しい量がRakhlin et alで導入された順次被覆数に改善する証拠なしで、メジャー化措置と分数被覆数の観点から確率過程上の上限を提供します。 0.65
(2010); here, we rectify that and focus on how to control the fractional covering numbers with combinatorial and structural properties of the function class. (2010) ここでは、これを修正し、関数クラスの組合せ的および構造的性質を持つ分数被覆数を制御する方法に焦点を当てる。 0.80
One of the cornerstones in classical learning theory was the development of Vapnik-Chernovenkis 古典的学習理論の基盤の1つは、ヴァプニク・チェルノヴェンキスの発展であった。 0.65
theory and how it relates to uniform convergence over a binary-valued function class (Vapnik & Chervonenkis, 1981). 理論とそれが二値函数クラス上の一様収束とどのように関係するか(Vapnik & Chervonenkis, 1981)。 0.78
This theory was then extended to real-valued functions with the development of fatshattering or scale-sensitive dimension (Bartlett et al. この理論はその後、脂肪散乱やスケール感受性次元(Bartlett et al)の発展とともに実数値関数へと拡張された。 0.59
, 1996; Kearns & Schapire, 1994). 1996年、kearns & schapire、1994年)。 0.75
In the online world, Littlestone (1988) introduced an analogue of the VC dimension and Rakhlin et al. オンラインの世界では、Littlestone (1988) はVC次元と Rakhlin et al の類似を導入した。 0.84
(2015) extended this definition to a sequential notion of the fat-shattering dimension. (2015)はこの定義をファット散乱次元の逐次概念へと拡張した。 0.74
Here, we 7 ここでは 7 0.76
英語(論文から抽出)日本語訳スコア
recall the definition of the fat-shattering dimension and then use it to bound the fractional covering numbers independently of n in a sequential analogue of the results of Mendelson & Vershynin (2003). 脂肪散乱次元の定義を思い出し、それを n とは独立に、メンデルソン & ヴェルシニン (2003) の結果の逐次的な類似の中で、分数被覆数に結び付けるために使う。 0.71
We then show that, when integrated in the chaining upper bound of Corollary 10, we can further improve the bound and provide a sequential analogue of the results of Rudelson & Vershynin (2006), which is tight in the Donsker case. 次に、Corollary 10 の連鎖上界に統合すると、さらに境界を改善し、Donsker ケースでタイトである Rudelson & Vershynin (2006) の結果の連続的なアナログを提供することができることを示します。 0.70
Finally, we apply these results to prove a tight (up to constants) Lipschitz contraction bound on worst-case Rademacher complexity, improving on the structural results of Rakhlin et al. 最後に,これらの結果を用いて,ラドマッチャーの最悪の複雑性に縛られたリプシッツ収縮を(定数まで)厳密に証明し,ラークリンらの構造的結果を改善した。 0.71
(2015). We begin by recalling the fat-shattering dimension from (Rakhlin et al. (2015). まず, (Rakhlin et al) から脂肪の破砕次元を想起することから始める。 0.67
, 2015, Definition 7): 2015年、定義7)。 0.59
Definition 12. Let z a Z-labelled binary tree of depth n and let F a real-valued function class. 定員12名。 z を深さ n の二進木とし、F を実数値関数類とする。 0.62
We say that F is shattered by z at scale δ if there exists a real-valued binary tree s such that for all ε ∈ {±1}n, there exists an f ∈ F such that for all 1 ≤ t ≤ n, δ 2 f がスケール δ において z で破れるとは、すべての ε ∈ {±1}n に対して、すべての 1 ≤ t ≤ n, δ 2 に対して f ∈ f が存在するような実数値二分木 s が存在するときである。 0.82
εt (f (zt(ε)) − st(ε)) ≥ εt (f (zt(ε)) − st(ε)) ≥ 0.90
(25) . The (sequential) fat-shattering dimension fatδ(F) is the maximal n such that there exists a tree z of depth n that shatters F at scale δ. (25) . 脂肪散乱次元 (sequential) fat-shattering dimension fatδ(F) は、深さ n のツリー z が存在して、スケール δ で F を粉砕する最大 n である。 0.82
A sequential version of the Sauer-Shelah lemma was also proven in Rakhlin et al. Sauer-Shelah lemma の連続版も Rakhlin et al で証明された。 0.77
(2015) and this was used to bound the ℓ∞ sequential covering numbers by the fat shattering dimension. (2015) とこれを用いて, 脂肪破砕次元によるl∞シーケンシャル被覆数に束縛した。 0.74
In particular, (Rakhlin et al. 特に、 (rakhlin et al.)。 0.72
, 2015, Corollary 1) tells us that if F takes values in [0, 1] then for any tree z of depth n, 2015年、corollary 1) は f が [0, 1] の値を取ると、深さ n の任意の木 z に対して値を取ると述べる。 0.67
N (F, δ, z) ≤ N∞(F, δ, z) ≤(cid:18) 2en N (F, δ, z) ≤ N∞(F, δ, z) ≤(cid:18) 2en 0.96
δ (cid:19)fatδ(F) δ (cid:19)fatδ(F) 0.88
(26) (27) where N∞ denotes the covering number with respect to ℓ∞. (26) (27) N∞ は l∞ に関して被覆数を表す。 0.84
As noted in situ, this method cannot provide n-independent covering number bounds for the ℓ2 regime because the ℓ∞ covering numbers cannot be independent of dimension in general. 上述の通り、この方法は l∞ 被覆数は一般に次元に依存しないため、l2 状態に対して n 独立被覆数境界を与えることはできない。 0.66
In the classical setting, Dudley extraction, pioneered in Dudley (1973), allows for dimension-independen t bounds, but, due to the lack of coveringpacking duality in the sequential case, this method cannot be applied in the online regime. 古典的な設定では、ダドリー (1973) で先駆的なダドリー抽出(英語版)は次元非依存境界を許容するが、シーケンシャルな場合において包括的双対性が欠如しているため、この方法がオンライン体制では適用できない。 0.59
A major advantage of the fractional covering number is that we are able to eliminate the dependence on n and control the fractional covering numbers by the fat-shattering dimension. 分数被覆数の主な利点は、n への依存を排除し、脂肪散乱次元によって分数被覆数を制御することができるということです。 0.66
We have the following bound: 以下の境界があります。 0.55
Theorem 13. Let F : Z → [0, 1] be a function class. 理論13。 F : Z → [0, 1] を関数クラスとする。 0.70
There exist universal constants C, c such that for all δ > 0, and all trees z すべてのδ > 0 とすべての木 z に対して普遍定数 C, c が存在する。 0.85
N′(F, δ, z) ≤(cid:18) C N′(F, δ, z) ≤(cid:18) C 0.97
δ(cid:19)3fatcδ(F) δ(cid:19)3fatcδ(F) 0.81
The details of the proof of Theorem 13 can be found in Appendix B, but we provide a sketch Theorem 13の証明の詳細はAppendix Bで確認できるが、スケッチを提供している。 0.74
here. We follow Rakhlin et al. ここだ rakhlinとalをフォローする。 0.62
(2015) and discretize the unit interval into sub-intervals of length proportional to δ; this discretization transforms the real-valued function class F into one that takes on finitely many values. (2015) 単位区間を δ に比例する長さのサブインターバルに離散化する; この離散化は実数値関数類 f を有限個の値を取るものに変換する。 0.77
Using this transformation, it suffices to bound the fractional covering number of a simpler class of functions F : Z → {0, 1, . この変換を用いることで、より単純な函数のクラス F : Z → {0, 1, の分数被覆数を有界にすることができる。 0.81
. . , m} by fat2(F), i.e., it suffices to prove Proposition 14. . . , m} by fat2(F),すなわち、命題14を証明するのに十分である。 0.84
Suppose that F : Z → Y = {0, 1, . F : Z → Y = {0, 1, と仮定する。 0.83
. . , m} and that fat2(F) = d. Then there is a . . , m} であり、fat2(f) = d である。 0.82
universal constant C such that N′(cid:0)F, 2 N′(cid:0)F, 2 となる普遍定数 C 0.85
3 , z(cid:1) ≤ (Cm)3d. 3 , z(cid:1) ≤ (Cm)3d。 0.87
We provide full details in Appendix B, but provide a sketch here: 詳細は appendix b で提供していますが、こちらのスケッチをご覧ください。 0.64
8 8 0.85
英語(論文から抽出)日本語訳スコア
Sketch. We fix the tree z and construct the fractional cover recursively. スケッチ。 木 z を固定し、分数被覆を再帰的に構成する。 0.64
The idea of the construction is to partition the function class F into sub-classes Fj taking the value j on the root. 構成の考え方は、関数クラス F をルートに値 j を取るサブクラス Fj に分割することである。 0.80
Lemma 23, proved in Appendix B, tells us that there are at most two such sub-classes such that fat2(Fj) = fat2(Fj′) = fat2(F) and that |j − j′| ≤ 1. レンマ23はアペンディックスBで証明され、ファット2(Fj) = fat2(Fj′) = fat2(F) と |j − j′| ≤ 1 という2つのサブクラスが存在する。 0.79
Let j∗ be the minimal j such that fat2(Fj) = fat2(F) and notice that j∗ and j∗ + 1 are potentially the only values of j such that fat2(Fj) = fat2(F). j を、fat2(Fj) = fat2(F) のような最小の j とし、j と j* + 1 が j の唯一の値であり、fat2(Fj) = fat2(F) となることに気付く。 0.82
We construct the fractional cover µ recursively as the following mixture: with probability 1 − p, where p is a small number to be specified, we label the root as j∗ + 1/2 and label the two subtrees of the root independently, using the fractional cover with respect to the complete class F. Otherwise, with probability p, we draw a uniformly random j ∈ {0, . 確率 1 − p で p を指定すべき小さな数として、根を j∗ + 1/2 とラベル付けし、根の2つの部分木を独立にラベル付けし、完全類 f に関して分数被覆を用いる。
訳抜け防止モード: フラクショナルカバーμを次の混合物として再帰的に構築する:確率1 − p, p が指定する小数である場合、ルートを j* + 1/2 とラベル付けします。 ルートの2つのサブツリーを独立してラベル付けします。 完全なクラス F に関して分数被覆を用いる。 均一にランダムな j ∈ { 0 , . を描画します。
0.77
. . , m} \ {j∗, j∗ + 1}, label the root as j and each of the two subtrees independently from the fractional covers with respect to the subclass Fj, which satisfies fat2(Fj) ≤ fat2(F)− 1. . . , m} \ {j∗, j∗ + 1} は根を j とラベル付けし、分数被覆とは独立に2つの部分木のそれぞれを、F2(Fj) ≤ fat2(F)− 1 を満たす部分類 Fj に対して表す。 0.82
An induction proof relying on the recursive construction, found in Appendix B as Lemma 24, then tells us that if fat2(F) ≤ d and µ is as constructed above, then for any integer k, 帰納的構成に依存する帰納的証明は、アペンディックス B で Lemma 24 として発見され、ファット2(F) ≤ d と μ が上のような構成であれば、任意の整数 k に対して成立する。 0.71
inf f∈F ε∈{±1}n inf f∈F ε∈{±1}n 0.79
Setting k = δn, p = d 1 then it is at most 1 ||v(ε) − f (z(ε))||2 ≤ m2δn + 1 fractional cover. k = δn, p = d 1 を設定すると、最大 1 ||v(ε) − f (z(ε))||2 ≤ m2δn + 1 分数被覆となる。 0.84
nXt=0 1|vt(ε)−f (z(tε))|≥1 ≤ k)! nXt=0 1|vt(ε)−f (z(tε))|≥1 ≤ k)! 0.77
≥ (1 − p)n+1+k(cid:16) p ≥ (1 − p)n+1+k(cid:16) p 0.78
µ (v| n , the right hand side is at least (cδ/m)d. By the construction, if |vt(ε) − f (zt(ε))| < 2 and otherwise, |vt(ε) − f (zt(ε))| ≤ m. Thus if v is in the above set, then 36m2 , the result follows by the definition of a (cid:4) μ (v| n , 右辺が少なくとも (cδ/m)d である: |vt(ε) − f (zt(ε))| < 2 でなければ |vt(ε) − f (zt(ε))| ≤ m となるから、v が上記の集合であれば 36m2 となる。
訳抜け防止モード: μ ( v| n, 右辺は少なくとも (cδ / m)d である。 もし |vt(ε ) − f ( zt(ε))| < 2 でなければ、 |vt(ε ) − f ( zt(ε))| ≤ m である。 v は上記のセットです。 次に、36m2 、結果は a (cid:4 ) の定義によって続きます。
0.90
m(cid:17)d(cid:18)k + d d (cid:19) . m(cid:17)d(cid:18)k + d d (cid:19)。 0.81
4 (1 − δ)n. Thus if δ ≤ 7 4 (1 − δ)n ならば δ ≤ 7 である。 0.93
(28) Note that Proposition 14 is already a major improvement over (Rakhlin et al. (28) 提案14は (rakhlin et al.) よりもすでに大きな改善点である。 0.82
, 2015, Corollary 1), the analogue for non-fractional sequential covers; in addition, our result matches the form of the classical counterpart, proven in Mendelson & Vershynin (2003). 2015年、Corollary 1)、非フラクショナルシーケンシャルカバーのアナログ;さらに、私たちの結果はメンデルソン&ヴェルシニン(2003)で証明された古典的なものの形に一致します。 0.70
Interestingly, the proof of Proposition 14 relies on the independence of sub-trees inherent to the online case; thus, the same proof does not apply to the classical analogue, proven by use of Dudley extraction. 興味深いことに、命題14の証明はオンラインの場合に固有の部分木の独立性に依存しているため、ダドリー抽出によって証明された古典的類似物には同じ証明が適用されない。 0.65
The key lemma, Lemma 23, very much takes advantage of the sequential setting and thus the Proposition 14 and consequently Theorem 13, provide important examples of results that are proved more easily in the sequential case than in the classical setting. キー補題 lemma 23 はシーケンシャルな設定を大いに活用しており、従って命題14と定理13は、古典的設定よりもシーケンシャルな場合においてより容易に証明される結果の重要な例を提供する。 0.78
An interesting future direction would be to extend the proof method to the classical regime and reprove the analogue of Theorem 13 without the use of Dudley extraction. 興味深い今後の方向性は、証明法を古典的体系に拡張し、ダドリー抽出を使わずに定理13の類似性を再証明することである。 0.64
If we plug the result of Theorem 13 into that of Corollary 10, we are able to bound the sequential Theorem 13の結果をCorollary 10の結果にプラグインすれば、シーケンシャルをバインドすることができます。 0.75
Rademacher complexity as follows: Rademacherの複雑さは次のとおりです。 0.51
Rn(F) = sup Rn(F) = sup 0.85
Rn(F, z) . Rn(F, z) である。 0.76
depth(z)=n depth(z)=n 0.99
1 √nZ 1 0 rfatδ(F) log 1 ^nZ1 0 rfatδ(F) log 0.84
1 δ dδ (29) 1 δ dδ (29) 0.83
where we take α = 0 in Corollary 10 for the sake of simplicity of exposition. ここで我々は博覧会の単純さのためにCorollary 10でα = 0を取る。 0.73
Equation (29) improves the results of Rakhlin et al. Equation (29) は Rakhlin et al の結果を改善する。 0.90
(2015) in that it shaves off a factor polynomial in log n, but we might hope for an even better bound that removes the log 1 δ factor. (2015) では、log n の因子多項式を削るが、log 1 δ ファクタを削除するより優れたバウンドを期待するかもしれない。 0.71
In the classical regime, it was shown in Rudelson & Vershynin (2006) that this is indeed possible and that 古典的体制では、ルデルソン&ヴェルシニン (2006) でこれが実際に可能であり、そのことが示されている。 0.69
where just in (30), the Rademacher complexity and fat shattering dimension are the classical notions rather than the sequential notions. ちょうど(30)で、Rademacherの複雑さおよび脂肪質の粉砕次元は連続的な概念よりむしろ古典的な概念です。 0.65
In fact, we do get a sequential analogue to (30) and the proof is much simpler than that in the classical regime. 実際、我々は (30) のシーケンシャルな類似点を得ており、証明は古典的体制のそれよりもはるかに単純である。 0.76
We have: Rn(F) . 我々 はあります。 Rn(F)。 0.63
1 √nZ 1 0 pfatδ(F)dδ 1 ^nZ1 0 pfatδ(F)dδ 0.82
(30) 9 (30) 9 0.85
英語(論文から抽出)日本語訳スコア
Proposition 15. Let F be a class of functions from Z to [0, 1]. 第15話。 F を Z から [0, 1] までの関数のクラスとする。 0.63
Then for all b > 0, するとすべての b > 0, 0.89
Z 1 b plog N′(F, δ)dδ . Z 1 b plog N′(F, δ)dδ 。 0.88
Z 1 cb pfatδ(F)dδ. Z1 cb pfatδ(F)dδ。 0.80
(31) As main step in this proof, we bound the fractional covering numbers with respect to multiple (31) この証明の主なステップとして、我々は複数に関して分数被覆数を束縛した。 0.75
fat numbers: Proposition 16. There exist universal constants c, C > 0 such that the following holds: Let F be a class of functions from Z to Y = [0, 1]. 脂肪数: 16歳。 普遍定数 c, C > 0 が存在して、以下が成り立つ: F を Z から Y = [0, 1] への函数の類とする。 0.67
Then for all δ > 0, するとすべての δ > 0, 0.90
sketch. Similarly to the proof of Theorem 13, by discretizing [0, 1] into sub-intervals of length ≈ δ, it suffices for us to prove the following: if F is a {0, . スケッチ 同様に、[0, 1] を長さ δ の亜区間に離散化することにより、F が {0, .} であれば、以下のことを証明するのに十分である。 0.55
. . , m}-valued function class, then . . , m}-値付き関数クラス、 0.81
N′(F, δ) ≤ N′(F, δ) ≤ 0.96
∞Yi=1 C i·fatc·2iδ(F) ∞Yi=1 c i·fatc·2iδ(f) 0.51
(32) N′(F, 2) ≤ (32) N′(F, 2) ≤ 0.90
log mYi=1 C ifat2i (F). log mYi=1 C ifat2i (F)。 0.77
To prove the above statement, we construct a fractional cover µ recursively, in the same spirit as the proof of Proposition 14. 上記の主張を証明するために、命題14の証明と同じ精神で分数被覆 μ を再帰的に構成する。 0.70
Partition F into sub-classes Fj taking the value j on the root, and Lemma 23 tells us that there are at most 2i classes j with fat2i(Fj) = fat2i(F) and any two such classes j, j′ satisfy |j−j′| < 2i. F を根上の値 j を取る部分クラス Fj に分割すると、Lemma 23 は、少なくとも Fat2i(Fj) = fat2i(F) を持つ 2i クラス j が存在し、そのようなクラス j, j′ が |j−j′| < 2i を満たすことを言う。 0.75
Define by i(j) as the maximal integer i such that fat2i(Fj) < fat2i(F), and let j∗ be any minimizer of i(j). i(j) を最大整数 i として f2i(Fj) < fat2i(F) と定義し、j を i(j) の任意の最小値とする。 0.84
Intuitively, Fj∗ has the same high-scale fat numbers as F. The fractional cover is defined as the mixture that labels the root as j∗ with probability 1 − p for a small 0 < p < 1 and for any other j, with probability p · 4−i(j)−1. Fj∗ は F と同じ高スケールの脂肪数を持つ。 分数被覆は、小さな 0 < p < 1 の確率 1 − p と、確率 p · 4 − i(j)−1 の任意の j に対して、根を j∗ とラベル付けする混合物として定義される。 0.80
The remainder of the tree is recursively drawn, as in Proposition 14. 命題14のように、木の残りは再帰的に描画される。 0.75
By an inductive formula, we derive that for any numbers k1, k2, . 帰納公式により、任意の数 k1, k2, に対して導かれる。 0.66
. . , klog m and any bounds d1, . . . klog m と任意の有界 d1, . 0.85
. . , dlog m on the fat numbers fat21(F), . . . , 脂肪数%21(F), ではdlogmであった。 0.80
. . , fat2log m(F), the fractional cover µ satisfies . . , fat2log m(F), the fractional cover μ satisfies 0.87
inf f∈F ε∈{±1}n inf f∈F ε∈{±1}n 0.79
µ v : ∀i = 1, . µ v : 「i = 1」。 0.73
. . , log2 m, . . ,log2mであった。 0.73
nXt=0 1|vt(ε)−f (zt(ε))|≥2i| ≤ nXt=0 1|vt(ε)−f(zt(ε))|\2i|≤ 0.74
≥ (1 − p)n+1 ≥ (1 − p)n+1 0.94
ki′  log2 mXi′=i 4i+1(cid:17)di(cid:18)k i + di di (cid:19). 4i+1(cid:17)di(cid:18)k i + di di (cid:19)。 0.78
log2 mYi=1 (1 − p)ki(cid:16) p log2 mYi=1 (1 − p)ki(cid:16) p 0.85
(33) Substituting ki = 8−in, we obtain that any v in the above set satisfies kv(ε) − f (z(ε))k ≤ O(1). (33) ki = 8−in を代入すると、上記の集合の任意の v は kv(ε) − f(z(ε))k ≤ O(1) を満たす。 0.83
Bounding the binomial coefficients similarly to Proposition 14, the proof concludes, as we derive a lower bound on the fraction of trees close to f (z) on any path ε. 双対係数は命題14と類似しており、証明は任意の経路 ε 上の f(z) に近い木の分数に下界を導出すると結論付ける。 0.67
(cid:4) While admittedly still somewhat technical, we observe that the proof of Proposition 15, appearing in Appendix C, is actually significantly easier than that required for the analogous result in the classical regime, appearing in (Rudelson & Vershynin, 2006). (cid:4) 明らかにやや技術的にはあるが、付録 C に現れる命題 15 の証明は、(Rudelson & Vershynin, 2006) に現れる古典体制における類似の結果に必要なものよりもはるかに簡単である。 0.76
Miraculously, for function classes F that are not too complex, Proposition 15 gives a tight bound on the worst-case sequential Rademacher complexity, up to constants. 奇跡的に、複雑すぎない関数クラス F に対して、命題 15 は、定数まで、最悪のケースであるシーケンシャルな Rademacher 複雑性に厳しい境界を与える。 0.72
In order to state such a result, we need to define what it means for a function class to be simple. このような結果を記述するためには、関数クラスがシンプルであることの意味を定義する必要があります。 0.78
10 10 0.85
英語(論文から抽出)日本語訳スコア
Definition 17. For a constant c > 0 and 0 ≤ p < 2, we say that a function class is (c, p)-bounded if for all 0 < δ < 1, (34) 定員17名。 定数 c > 0 と 0 ≤ p < 2 に対して、函数類が (c, p)-有界であるとは、すべての 0 < δ < 1, (34) について言う。 0.68
fatδ(F) ≤ cδ−p. fatδ(F) ≤ cδ−p。 0.73
We note that many practical function classes are (c, p)-bounded; for example, Littlestone classes 多くの実用的関数クラスは (c, p)-バウンドであり、例えばリトルストーンクラスである。 0.80
satisfy the above for c = Ldim(F) and p = 0. c = Ldim(F) と p = 0 に対して上記を満たす。 0.88
We have the following corollary: 以下のコースがあります。 0.39
Corollary 18. Let F be a (c, p)-bounded class of functions. 定員18名。 F を (c, p)-有界関数のクラスとする。 0.66
Then 0 pfatδ(F)dδ . その後 0 pfatδ(F)dδ 。 0.77
√nRn(F) . Z 1 Z 1 略称はRn(F)。 Z 1 Z 1 0.72
0 pfatδ(F)dδ 0 pfatδ(F)dδ 0.92
(35) where the constants depend on F only through c, p. The upper bound holds with no restriction on the complexity of the class F. (35) 定数が c を通して f にのみ依存する場合、p は上界がクラス f の複雑性に何の制限も与えない。 0.82
Thus for many classes of interest, we have a tight characterization of sequential Rademacher complexity, matching the characterization in the offline case. したがって、多くの興味のあるクラスに対して、オフラインケースのキャラクタリゼーションにマッチするシーケンシャルラデマッハ複雑性を厳密に特徴づける。 0.65
A challenging open problem remains, however: in the classical setting, majorizing measures provide both an upper and lower bound on the supremum of a Gaussian process. しかし、古典的な設定では、メジャー化措置はガウス過程の上限に上と下の両方の境界を提供する。
訳抜け防止モード: しかし 難解な未解決問題は残っています 古典的設定では、メジャー化測度はガウス過程の上限の上限と下限の両方を提供する。
0.62
While our results can be extended to give an upper bound for the sequential Gaussian complexity, where the path is determined by the signs of independent Gaussian multipliers, the lower bound remains to be shown. 私たちの結果は、独立ガウス乗算器の符号によってパスが決定される連続ガウス複雑性のために上限を与えるために拡張することができるが、下限は示されるべきである。 0.66
As an application of our results, we prove a tight Lipschitz contraction statement for worst-case Rademacher complexity in the (c, p)-bounded regime that is dimension-independen t, the first such statement in the online case. 結果の応用として, 次元に依存しない (c, p) 結合系における最悪の場合のラデマチャー複雑性に対するリプシッツ縮約文をオンラインケースで最初に証明した。 0.72
Corollary 19. Let F be a (c, p)-bounded class of functions. 定員19名。 F を (c, p)-有界関数のクラスとする。 0.65
If ℓ is an L-Lipschitz function, we have l が L-Lipschitz 関数であれば、 0.84
Rn (ℓ ◦ F) . Rn (l, F) である。 0.71
LRn(F) (36) LRn(F) (36) 0.85
where, again, the constant depends on F only through c and p. ここでも、定数は c と p によってのみ F に依存する。 0.78
Importantly, the statement of Corollary 19 is one about worst-case Rademacher complexity as opposed to tree-dependent Rademacher complexity. 重要なのは、Corollary 19の記述は、ツリー依存のRademacherの複雑さとは対照的に、最悪の場合のRademacherの複雑さに関するものです。
訳抜け防止モード: 重要なのは、Corollary 19の声明は最悪のものです。 -木とは対照的にラデマチャーの複雑さ。 Rademacherの複雑さに依存します。
0.50
A similar statement with a factor polynomial in log n was proved as (Rakhlin et al. 対数 n の係数多項式を持つ同様の言明が (Rakhlin et al) として証明された。 0.69
, 2015, Lemma 7). 2015年、第7回)。 0.64
Whether an analogous result holds in the tree-dependent case remains a challenging open question. 木に依存したケースで類似の結果が保持されるかどうかは、未だに難しい問題である。 0.50
5 Sample Complexity of Online Learning オンライン学習の5つのサンプル複雑さ 0.69
We finish this paper with a discussion of online learning, showing that our techniques lead to sharp estimates on minimax regret. この論文はオンライン学習の議論で締めくくり、我々の手法がミニマックスの後悔を鋭く見積もっていることを示す。 0.67
The online supervised learning problem is defined as follows. オンライン教師付き学習問題を次のように定義する。 0.58
We fix a class of functions F ⊆ [−1, 1]X, known to the learner. 学習者に知られている関数のクラス F > [−1, 1]X を固定する。 0.75
The online prediction problem proceeds over n rounds. オンライン予測問題はnラウンドで進行する。 0.75
On round Predictions may be randomized, in which case the learner selects a distribution qt on round t and ラウンド予測はランダム化され得るが、この場合、学習者はラウンド t 上の分布 qt を選択し、 0.74
t, the learner observes xt ∈ X, makes a prediction byt ∈ R, and observes the outcome yt ∈ Y ⊆ R. draws byt ∼ qt. t は、学習者が xt ∈ X を観測し、予測を t ∈ R とし、結果 yt ∈ Y ・ R を観測する。 0.74
Regret is defined as Regn(F) = E" 1 Regret は Regn(F) = E" 1 と定義される 0.93
ℓ(f (xt), yt)# . l(f(xt), yt)# である。 0.84
(37) n nXt=1 (37) n nXt=1 0.76
ℓ(byt, yt) − inf l(byt, yt) − inf 0.85
f∈F 1 n nXt=1 f∈F 1n nXt=1 0.64
In turn, the minimax regret is defined as 順番に、minimax の後悔が定義されます。 0.46
Vn(F) = min Vn(F) = min 0.85
τ max π Regn(F) τ マックス π Regn (複数形 Regns) 0.75
(38) 11 (38) 11 0.85
英語(論文から抽出)日本語訳スコア
where minimum is taken over all randomized strategies of the learner, and maximum is over all strategies of Nature for selecting the sequence (potentially adaptively and adversarially). 学習者のランダム化戦略は最小限に抑えられ、列を(潜在的に適応的かつ逆向きに)選択するための自然のすべての戦略は最大である。 0.81
While this minimax object appears to be complicated, by writing down a repeated sequence of minima and maxima per time step, it is possible to upper bound the minimax regret by a supremum of a collection of martingales indexed by F (Abernethy et al. このミニマックスオブジェクトは複雑に見えるが、時間ステップごとに繰り返しミニマと最大値の列を書き留めることで、F(Abernethy et al)でインデックス付けされたマリンタレの集合の上限によってミニマックスの後悔を上界にすることができる。 0.67
, 2009; Rakhlin et al. 2009年 - Rakhlin et al。 0.69
, 2010). In particular, it is shown in (Rakhlin et al. , 2010). 特に(Rakhlin et al.)で示されています。 0.83
, 2010) that for binary classification with Y = {0, 1}, F ⊆ YX, and ℓ(a, b) = I{a 6= b}, , 2010) Y = {0, 1}, F > YX, l(a, b) = I{a 6= b} の二項分類について。 0.76
where Rn(F) = supx Rn(F, x). ここで Rn(F) = supx Rn(F, x) である。 0.91
The tight characterization (39) also holds for prediction with absolute value loss (ℓ(a, b) = |a − b|, Y = [−1, 1], and F ⊆ YX), as well as for prediction with linear loss (ℓ(a, b) = −ab, Y = [−1, 1], F ⊆ YX) (Rakhlin et al. 厳密な特徴付け (39) は、絶対値損失 (l(a, b) = |a − b|, Y = [−1, 1], F > YX) の予測や、線形損失 (l(a, b) = −ab, Y = [−1, 1], F > YX) (Rakhlin et al) の予測にも用いられる。 0.77
, 2010). For the online learning problems mentioned above, we conclude that , 2010). 上記のオンライン学習問題に対して、我々は結論を下す。 0.76
Rn(F) ≤ Vn(F) ≤ 2R(F) Rn(F) ≤ Vn(F) ≤ 2R(F) 0.91
(39) improving on the corresponding estimates in (Rakhlin et al. (39) 対応する推定値の改善 (rakhlin et al.)。 0.79
, 2010). lary 18, for classes satisfying Definition 17, the minimax regret , 2010). lary 18, 定義17を満たすクラスのために, ミニマックスは後悔する 0.76
Vn(F) . inf Vn(F)。 inf 0.80
α≥0(cid:26)α + α≥0(cid:26)α + 0.75
1 √nZ 1 α pfatδ(F)dδ(cid:27) , 1 ^nZ1 α pfatδ(F)dδ(cid:27), 0.81
(40) In particular, from Corol- (40) 特にCorol (複数形Corols) 0.68
Vn(F) ≍ . (41) Vn(F)~ . (41) 0.82
1 √nZ 1 0 pfatδ(F)dδ ≍ r c 1 ^nZ1 0 pfatδ(F)dδ ・ r c 0.84
n In particular, for binary classification, this recovers the sharp result of (Alon et al. n 特に二項分類の場合、これは (Alon et al) の鋭い結果を取り戻す。 0.79
, 2021), as fatδ(F) reduces to the Littlestone dimension in this case. この場合、脂肪δ(F) はリトルストーン次元に還元される。 0.55
More generally, (40) provides a succinct and sharp characterization of optimal regret in terms of combinatorial parameters of the class. より一般的に、(40)はクラスの組み合わせパラメータの観点から最適な後悔の簡潔で鋭い特徴づけを提供する。 0.78
Using the techniques developed in this paper, we can sharpen and remove extraneous logarithmic factors in a number of bounds in (Rakhlin et al. 本論文で開発した技術を用いて,Rakhlin et al. のいくつかの境界において,異常な対数因子を削り取り除くことができる。 0.71
, 2010). We mention that for online regression with square loss, optimal regret is characterized in terms of a localized notion of sequential Rademacher complexity (offset complexity), and the study of its behavior in terms of the notions introduced in this paper is left for future work. , 2010). 平方損失を伴うオンライン回帰の場合、最適な後悔は、シーケンシャルラデマチャー複雑性(オフセット複雑性)の局所化された概念の観点で特徴付けられ、この論文で紹介された概念の行動の研究は、将来の作業のために残されている。 0.78
Acknowledgements AB acknowledges support from the National Science Foundation Graduate Research Fellowship under Grant No. 認識 ABは、グラントNo.1の国立科学財団大学院研究フェローシップからの支持を認めています。 0.56
1122374. AR acknowledges support from the ONR through award #N00014-201-2336. 1122374. ARはONRから賞#N00014-201-2336までのサポートを認めています。 0.68
References Abernethy, Jacob, Agarwal, Alekh, Bartlett, Peter L, & Rakhlin, Alexander. 参考文献 Abernethy, Jacob, Agarwal, Alekh, Bartlett, Peter L, & Rakhlin, Alexander 0.71
2009. A stochastic 2009. stochastic (複数形 stochastics) 0.59
view of optimal regret through minimax duality. ミニマックス双対性による後悔の最適観。 0.59
arXiv preprint arXiv:0903.5328. arXiv preprint arXiv:0903.5328 0.71
Alon, Noga, Livni, Roi, Malliaris, Maryanthe, & Moran, Shay. Alon, Noga, Livni, Roi, Malliaris, Maryanthe, & Moran, Shay。 0.82
2019. Private PAC learning implies finite littlestone dimension. 2019. プライベートpac学習は有限小石次元を含む。 0.76
Pages 852–860 of: 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019. 第51回ACM SIGACT Symposium on Theory of Computing, STOC 2019のページ 0.58
Association for Computing Machinery. コンピュータ機械協会会員。 0.63
Alon, Noga, Ben-Eliezer, Omri, Dagan, Yuval, Moran, Shay, Naor, Moni, & Yogev, Eylon. Alon, Noga, Ben-Eliezer, Omri, Dagan, Yuval, Moran, Shay, Naor, Moni, & Yogev, Eylon。 0.89
2021. Adversarial Laws of Large Numbers and Optimal Regret in Online Classification. 2021. オンライン分類における大多数の逆法則と最適法則 0.76
12 12 0.85
英語(論文から抽出)日本語訳スコア
Bartlett, Peter, Dani, Varsha, Hayes, Thomas, Kakade, Sham, Rakhlin, Alexander, & Tewari, Ambuj. Bartlett, Peter, Dani, Varsha, Hayes, Thomas, Kakade, Sham, Rakhlin, Alexander, & Tewari, Ambuj。 0.83
2008. High-probability regret bounds for bandit online linear optimization. 2008. バンディットオンライン線形最適化における高確率後悔限度 0.75
Pages 335– 342 of: Proceedings of the 21st Annual Conference on Learning Theory-COLT 2008. 論文335-342: Proceedings of the 21st Annual Conference on Learning Theory-COLT 2008 0.87
Omnipress. Bartlett, Peter L, & Mendelson, Shahar. Omnipress Bartlett、Peter L、& Mendelson、Shahar。 0.62
2002. Rademacher and Gaussian complexities: Risk 2002. Rademacher と Gaussian complexities: リスク 0.83
bounds and structural results. 境界と構造的な結果です 0.63
Journal of Machine Learning Research, 3(Nov), 463–482. Journal of Machine Learning Research, 3(Nov), 463–482。 0.86
Bartlett, Peter L, Long, Philip M, & Williamson, Robert C. 1996. Bartlett, Peter L, Long, Philip M, & Williamson, Robert C. 1996 0.83
Fat-shattering and the learn- ability of real-valued functions. 脂肪散乱と学習- 実値関数の能力。 0.77
journal of computer and system sciences, 52(3), 434–452. journal of computer and system sciences, 52(3), 434–452 を参照。 0.92
Ben-David, Shai, P´al, D´avid, & Shalev-Shwartz, Shai. Ben-David, Shai, P ́al, D ́avid, & Shalev-Shwartz, Shai 0.74
2009. Agnostic Online Learning. 2009. Agnostic Online Learning の略。 0.78
Page 1 of: COLT, vol. 1ページ の:COLT、vol。 0.68
3. Bercu, Bernard, & Touati, Abderrahmen. 3. Bercu, Bernard, & Touati, Abderrahmen。 0.83
2008. Exponential inequalities for self-normalized mar- 2008. 自己正規化マルの指数不等式 0.65
tingales with applications. tingalesとアプリケーション。 0.62
The Annals of Applied Probability, 18(5), 1848–1869. The Annals of Applied Probability, 18(5), 1848–1869。 0.87
Bun, Mark, Livni, Roi, & Moran, Shay. Bun, Mark, Livni, Roi, & Moran, Shay。 0.81
2020. An Equivalence Between Private Classification and 2020. 個人分類と個人分類の等価性 0.79
Online Prediction. In: 61st Annual IEEE Symposium on Foundations of Computer Science. オンライン予測。 第61回IEEE Symposium on Foundations of Computer Scienceに参加。 0.74
Cesa-Bianchi, Nicolo, & Lugosi, G´abor. Cesa-Bianchi, Nicolo, & Lugosi, G ́abor 0.84
2006. Prediction, learning, and games. 2006. 予測、学習、ゲーム。 0.71
Cambridge univer- ケンブリッジ・ユニバー 0.48
sity press. sity press所属。 0.72
de la Pe˜na, Victor H. 1999. ビクター・H・1999(Victor H. 1999)。 0.56
A general class of exponential inequalities for martingales and ratios. マルティンゲールと比率に対する指数的不等式の一般クラス。 0.57
The Annals of Probability, 27(1), 537–564. The Annals of Probability, 27(1), 537–564。 0.87
Dudley, R. M. 1973. ダドリー、R.M. 1973。 0.67
Sample Functions of the Gaussian Process. ガウス過程のサンプル関数。 0.57
Ann. Probab., 1(1), 66–103. アン。 例:1(1),66–103。 0.57
Fernique, Xavier. フェルニク、ザビエル。 0.50
1975. Regularit´e des trajectoires des fonctions al´eatoires gaussiennes. 1975. 規則は、ファンクションとガウスシエンヌを横断します。 0.59
Pages 1–96 of: Ecole d’Et´e de Probabilit´es de Saint-Flour IV—1974. 1-96ページ のEcole d’Et èe de Probabilit ́es de Saint-Flour IV—1974。 0.64
Springer. Foster, Dylan, & Rakhlin, Alexander. Springer Foster、Dylan、及びRakhlin、Alexander。 0.64
2020. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. 2020. beyond ucb: レグレッションオラクルによる最適かつ効率的なコンテキストバンディット。 0.70
Pages 3199–3210 of: International Conference on Machine Learning. ページ3199-3210の:マシンラーニングに関する国際会議。 0.73
PMLR. Foster, Dylan, Sarkar, Tuhin, & Rakhlin, Alexander. PMLR。 Foster, Dylan, Sarkar, Tuhin, & Rakhlin, Alexander 0.77
2020. Learning nonlinear dynamical systems 2020. 非線形力学系の学習 0.78
from a single trajectory. Pages 851–861 of: Learning for Dynamics and Control. 一つの軌道から ページ 851-861 of: Learning for Dynamics and Control。 0.76
PMLR. Ghazi, Badih, Golowich, Noah, Kumar, Ravi, & Manurangsi, Pasin. PMLR。 Ghazi, Badih, Golowich, Noah, Kumar, Ravi, & Manurangsi, Pasin 0.77
2020. Sample-efficient proper 2020. サンプル効率 0.76
PAC learning with approximate differential privacy. 近似差分プライバシーを用いたPAC学習 0.75
arXiv preprint arXiv:2012.03893. arXiv preprint arXiv:2012.03893 0.71
Gin´e, Evarist, & Zinn, Joel. Gin ́e, Evarist, & Zinn, Joel 0.87
1984. Some limit theorems for empirical processes. 1984. 経験過程に対するいくつかの極限定理。 0.69
The Annals of Annals of the Annals 0.80
Probability, 929–989. 確率 929-989。 0.83
Hall, Eric C, Raskutti, Garvesh, & Willett, Rebecca. Hall, Eric C, Raskutti, Garvesh, & Willett, Rebecca。 0.82
2016. Inference of high-dimensional autore- 2016. 高次元オートルの推論- 0.69
gressive generalized linear models. グレッシブ一般化線形モデル。 0.75
arXiv preprint arXiv:1605.02693. arXiv preprint arXiv:1605.02693 0.71
Jung, Young, Kim, Baekjin, & Tewari, Ambuj. Jung, Young, Kim, Baekjin, & Tewari, Ambuj 0.72
2020. On the Equivalence between Online and Private Learnability beyond Binary Classification. 2020. バイナリ分類を超えたオンライン学習とプライベート学習の等価性について 0.73
Advances in Neural Information Processing Systems, 33. ニューラル情報処理システムの進歩、33。 0.64
Kearns, Michael J, & Schapire, Robert E. 1994. Kearns, Michael J, & Schapire, Robert E. 1994。 0.90
Efficient distribution-free learning of probabilistic 確率の効率的な分布フリー学習 0.71
concepts. Journal of Computer and System Sciences, 48(3), 464–497. コンセプトだ journal of computer and system sciences, 48(3), 464–497 を参照。 0.78
13 13 0.85
英語(論文から抽出)日本語訳スコア
Littlestone, Nick. リトルストーン、ニック。 0.64
1988. Learning quickly when irrelevant attributes abound: A new linear-threshold 1988. 非関連属性が多ければすぐに学習する:新しい線形閾値 0.78
algorithm. Machine learning, 2(4), 285–318. アルゴリズム。 機械学習, 2(4), 285–318。 0.77
Mendelson, Shahar, & Vershynin, Roman. Mendelson, Shahar, & Vershynin, Roman 0.69
2003. Entropy and the combinatorial dimension. 2003. エントロピーおよび組合せ次元。 0.70
Inven- tiones mathematicae, 152(1), 37–55. Inven- Mathematicae, 152(1), 37–55。 0.75
Rakhlin, Alexander, & Sridharan, Karthik. Rakhlin, Alexander, & Sridharan, Karthik。 0.82
2015. On Martingale Extensions of Vapnik– Chervonenkis Theory with Applications to Online Learning. 2015. Vapnik–Chervonenkis理論のMartingale拡張とオンライン学習への応用について 0.80
Pages 197–215 of: Measures of Complexity. 197-215頁:複雑度の測定。 0.73
Springer. Rakhlin, Alexander, Sridharan, Karthik, & Tewari, Ambuj. Springer Rakhlin, Alexander, Sridharan, Karthik, & Tewari, Ambuj 0.64
2010. Online Learning: Random Averages, Combinatorial Parameters, and Learnability. 2010. オンライン学習: ランダム平均、組合せパラメータ、学習可能性。 0.81
Advances in Neural Information Processing Systems, 23, 1984–1992. ニューラル情報処理システムの進歩、1984-1992年3月23日。 0.61
Rakhlin, Alexander, Sridharan, Karthik, & Tewari, Ambuj. Rakhlin, Alexander, Sridharan, Karthik, & Tewari, Ambuj 0.75
2015. Sequential complexities and uniform martingale laws of large numbers. 2015. 順序的複雑性と多数の一様マーチンゲール法則。 0.78
Probability Theory and Related Fields, 161(1-2), 111–153. 確率理論と関連分野, 161 (1-2), 111–153。 0.83
Rudelson, Mark, & Vershynin, Roman. Rudelson, Mark, & Vershynin, ローマ語。 0.75
2006. Combinatorics of random processes and sections of 2006. ランダムなプロセスとセクションの組合せ。 0.78
convex bodies. Annals of Mathematics, 603–648. 凸体。 Annals of Mathematics, 603–648。 0.69
Talagrand, Michel. タラグランド、ミシェル。 0.52
1996. Majorizing measures: the generic chaining. 1996. メジャー化対策:ジェネリックチェーン。 0.72
The Annals of Probability, 24(3), 1049–1103. 確率の年代表。 24(3), 1049–1103. 0.74
Talagrand, Michel. タラグランド、ミシェル。 0.52
2014. Upper and lower bounds for stochastic processes: modern methods and 2014. 確率過程の上下境界--現代的な方法と方法 0.75
classical problems. Vol. 古典的問題。 Vol。 0.72
60. Springer Science & Business Media. 60. Springer Science & Business Mediaの略。 0.80
van Handel, Ramon. van Handel、Ramon。 0.66
2014. Probability in high dimension. 2014. 高次元での確率。 0.80
Tech. rept. PRINCETON UNIV NJ. 技術。 レパート。 PRINCETON UNIV NJ所属。 0.62
Vapnik, VN, & Chervonenkis, A Ya. Vapnik, VN, & Chervonenkis, A Ya。 0.82
1971. On uniform convergence of the frequencies of events to 1971. 事象の周波数の均一収束について 0.78
their probabilities. Teoriya Veroyatnostei i ee Primeneniya, 16(2), 264–279. 彼らの確率です Teoriya Veroyatnostei i ee Primeneniya, 16(2), 264–279。 0.71
Vapnik, VN, & Chervonenkis, A Ya. Vapnik, VN, & Chervonenkis, A Ya。 0.82
1981. The necessary and sufficient conditions for the uniform convergence of averages to their expected values. 1981. 平均値と期待値の均一な収束のための必要かつ十分な条件。 0.83
Teoriya Veroyatnostei i Ee Primeneniya, 26(3), 543–564. Teoriya Veroyatnostei i Ee Primeneniya, 26(3), 543–564。 0.86
A Proof of Theorem 3 We use the technique of chaining. 定理の証明 3 私たちは鎖のテクニックを使います。 0.64
In order to apply it, we need an adaptive tail bound for the tree process. それを適用するには、ツリープロセスにバインドされた適応的な尾が必要です。 0.69
We have Lemma 20. Let v be a labelled binary tree and let ε1, . 我々は レマ20。 v をラベル付き二項木とし、ε1, . とする。 0.64
. . , εn be independent Rademacher random variables. . . εn は独立した Rademacher ランダム変数である。 0.79
Then for any y > 0, with probability at least 1 − ρ, we have 任意の y > 0 に対して、確率が少なくとも 1 − ρ であれば、 0.78
implies that nXt=1 (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) つまり nXt=1 (cid:12)(cid:12)(cid :12)(cid:12) 0.64
vt(ε)2 ≤ y vt(ε)2 ≤ y 0.85
nXt=1 εtvt(ε)(cid:12)(cid:12)(ci d:12)(cid:12)(cid:12 ) ≤ 2r2y log nXt=1 εtvt(ε)(cid:12)(cid:12)(ci d:12)(cid:12)(cid:12 )(≤ 2r2y log 0.72
14 1 ρ (42) 14 1 ρ (42) 0.85
(43) (43) 0.85
英語(論文から抽出)日本語訳スコア
Proof. Let Ms =Xt≤s 証明。 はじめに Ms = Xt≤s 0.50
εtvt(ε) (44) εtvt(ε) (44) 0.92
dent and the vt are adapted. dent と vt が適応されます。 0.73
Note that the quadratic variation is given by [Ms] = Pn 二次変動は[Ms] = Pn によって与えられることに注意。 0.72
Note that Ms is a martingale with conditionally symmetric increments because the εt are indepent=1 vt(ε)2. Ms は条件付き対称インクリメントを持つマーチンゲールであり、εt は indepent=1 vt(ε)2 である。 0.69
Thus by de la Pena’s inequality (see de la Pe˜na (1999); Bercu & Touati (2008)), we have for any x, y > 0, このようにして、デ・ラ・ペナの不等式 (de la pena) (1999), bercu & touati (2008) により、任意の x, y > 0 に対して成り立つ。 0.66
(45) (cid:4) (45) (cid:4) 0.82
Setting x = 2q2y log 1 x = 2q2y log 1 0.76
ρ concludes the proof. ρは証明を締めくくる。 0.72
Using Lemma 20, we are able to prove Lemma 4. Lemma 20を使用すると、Lemma 4を証明できます。 0.75
P (|MT| ≥ x, [MT ] ≤ y) ≤ 2e− x2 P (|MT| ≥ x, [MT ] ≤ y) ≤ 2e− x2 0.90
2y Proof of Lemma 4. 2y Lemma 4の証明。 0.73
Let yj = 2−jn and let ρj = ρj−2. yj = 2−jn とし、ρj = ρj−2 とする。 0.61
Then for any fixed j, Lemma 20 tells us that そして、任意の固定 j に対して、Lemma 20 は私たちに言う。 0.58
P |Tv| > Csyj log P |Tv| > Csyj log 0.88
j ρ and ||v||2 ≤ yj! j ρ と ||v||2 ≤ yj! 0.74
≤ 6 π2 ρj (46) ≤ 6 π2 ρj (46) 0.83
for some C. Summing 6 1 − ρ, for all j, ある C に対して 6 1 − ρ, for all j, 0.80
π2 ρj gives ρ and so a union bound tells us that with probability at least π2 ρj は ρ を与えるので、結合境界は、少なくとも確率で 0.73
If ||v|| ≤ √n2−j 場合 ||v||≤ ^n2−j 0.59
Then |Tv| ≤ Csn2−j log 次に |Tv| ≤ Csn2−j ログ 0.54
j ρ (47) On the event that ||v|| = 0 the result is trivial. j ρ (47) ||v| = 0 の場合、結果は自明である。 0.78
Thus, suppose otherwise and take j = ⌈e log n ||v||2⌉; the above holds. したがって、そうでなければ j = s e log n ||v||2 と仮定する。 0.70
Plugging in, we see that the “if” statement is valid for this j and thus we have プラグインすると、この j に対して “if” ステートメントが有効であることがわかります。 0.61
|Tv| ≤ Csn2−j log |Tv| ≤ Csn2−j log 0.59
j ρ ≤ Cs||v||2 log j ρ ≤ Cs||v||2 log 0.69
log en ||v||2 ρ log en ||v||2 ρ 0.59
with probability at least 1 − ρ. 少なくとも 1 − ρ の確率を持つ。 0.82
(48) (cid:4) (48) (cid:4) 0.82
We will also need a lemma to relate probability over the majorizing measure to probability over また、メジャー化測度上の確率と確率を関連付けるための補題も必要である。 0.67
the ε. We have: ε。 我々 はあります。 0.55
Lemma 21. Let µ a measure over binary trees v and consider indicator variables U (v, ε) and let α, ρ ∈ (0, 1). レマ21号。 μ を二分木 v 上の測度とし、指標変数 U (v, ε) を考え、α, ρ ∈ (0, 1) とする。 0.67
Suppose that for each v ∈ supp µ, Eε(U (v, ε)) ≤ αρ. 各 v ∈ supp μ に対して Eε(U (v, ε)) ≤ αρ とする。 0.81
Then with probability at least 1 − ρ on the ε, (49) その後、 ε 上の少なくとも 1 − ρ の確率で (49) 0.90
Eµ (U (v, ε)) ≤ α Eμ (U (v, ε)) ≤ α 0.92
Proof. This follows immediately from Fubini’s theorem and Markov’s inequality. 証明。 これはフビニの定理とマルコフの不等式からすぐに続く。 0.57
(cid:4) We are now ready to prove the main chaining bound with the fractional covering number. (cid:4) 現在、分数被覆数と結合する主鎖の証明の準備が整っている。 0.71
For v, v′ ∈ V binary trees, we fix のために v, v′ ∈ V二分木 修正します 0.65
T v,v′(ε) = T v,v′(ε) = 0.90
nXt=1 εt(vt(ε) − v′t(ε)) nXt=1 εt(vt(ε) − v′t(ε)) 0.77
(50) 15 (50) 15 0.85
英語(論文から抽出)日本語訳スコア
and we recall that the norm is With this notation fixed, we can prove the theorem. 私たちはこの規範が この表記法を固定すれば、定理を証明できる。 0.53
We prove the following lemma: 次の補題を証明します 0.68
(cid:12)(cid:12)(cid :12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) = (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12) = 0.72
nXt=1 (vt(ε) − v′t(ε))2 nXt=1 (vt(ε) − v′t(ε))2 0.78
(51) Lemma 22. (51) レマ22。 0.73
Let µ be a probability distribution over [0, 1] valued trees of depth n and define ν = µ ⊗ µ. μ を[0, 1] の深さ n の値木上の確率分布とし、ν = μ > μ を定義する。 0.84
With probability 1 − ρ, the following holds: uniformly, for any γ ≥ 2, 確率 1 − ρ では、以下のことが成り立つ:任意の γ ≥ 2 に対して。 0.84
µ(cid:18)(cid:26)v : |Tv(ε)| > Crn log ν ((v, v′) : (cid:12)(cid:12)T μ(cid:18)(cid:26)v : |Tv(ε)| > Crn log ν ((v, v′) : (cid:12)(cid:12)T 0.90
v,v′(ε)(cid:12)(cid:12) > C(cid:12)(cid:12)(ci d:12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)slog v,v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)(cid:12 )(cid:12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)slog 0.77
γ ρ(cid:27)(cid:19) ≤ γ ρ(cid:27)(cid:19)≤ 0.86
1 γ γ ρ + log log 1 γ γ ρ ログログ。 0.77
3√n ||v(ε) − v′(ε)||)! 3分。 ||v(ε) − v′(ε)||)! 0.57
≤ 1 γ (52) ≤ 1 γ (52) 0.85
(53) Proof. We first note that it suffices to prove the result uniformly on γj = 2j. (53) 証明。 まず、γj = 2j 上で均一に結果を証明できることに注意してください。
訳抜け防止モード: (53) 証明。 まず注意すべきは 結果は γj = 2j 上で一様に証明できる。
0.74
For any γ, let γj maximal power of 2 that is at most γ. 任意の γ に対して、最も γ である 2 の最大パワー γj とする。 0.86
Then the sets in the statement of the lemma for γ are contained in the corresponding sets for γj. その後、γ の補題の文中の集合は γj の対応する集合に含まれる。 0.76
Moreover, γj differs from γ by at most a factor of 2, that can be eaten into the constants C in the statement. さらに、γj は γ と最大 2 の因子で異なっており、これは文中の定数 C に食べられる。 0.68
More formally, we have もっと正式には、私たちは 0.67
µ(cid:18)(cid:26)v : |Tv(ε)| > 2Crn log μ(cid:18)(cid:26)v : |Tv(ε)| > 2Crn log 0.88
γ ρ(cid:27)(cid:19) ≤ µ(cid:18)(cid:26)v : |Tv(ε)| > Crn log ≤ µ(cid:18)(cid:26)v : |Tv(ε)| > Crn log γ ρ(cid:27)(cid:19) ≤ μ(cid:18)(cid:26)v : |Tv(ε)| > Crn log ≤ μ(cid:18)(cid:26)v : |Tv(ε)| > Crn log 0.87
≤ 2 γj ≤ 1 γ ≤ 2 γj ≤ 1 γ 0.88
γ 2ρ(cid:27)(cid:19) 2ρ(cid:27)(cid:19) γ 2ρ(cid:27)(cid:19)(cid :27)(cid:19) 0.80
γj and similarly for the other event; thus, it suffices to prove the result only for γ powers of 2. γj 同様に、他の事象もそうである。したがって、結果は 2 の γ パワーに対してのみ証明するのに十分である。 0.71
Now, setting y = √n and applying Lemma 20, we get これで y = *n を設定して Lemma 20 を適用します。 0.69
P|Tv(ε)| > Csn log P |Tv(ε)| > Csn log 0.93
γ2 j ρ  = P|Tv(ε)| > Csn log γ2 j ρ ε)| > csn log である。 0.76
≤ ρ 6γ2 j γ2 j ρ ≤ ρ 6γ2 j γ2 j ρ 0.86
and ||v(ε)|| ≤ √n と ||v(ε)|| ≤ n である。 0.61
 (54) (55)  (54) (55) 0.85
(56) (57) (58) (56) (57) (58) 0.85
for C large enough, where the equality follows from the fact that |vt(ε)| ≤ 1 and so ||v(ε)|| ≤ √n almost surely. 十分大きい c に対して、等式は |vt(ε)| ≤ 1 であり、したがって ||v(ε)|| ≤ sn がほぼ確実に成り立つという事実から従う。 0.79
Applying Lemma 21 tells us that for all j, with probability at least 1 − ρ Lemma 21 を適用すると、確率が少なくとも 1 − ρ であるすべての j に対しては、
訳抜け防止モード: Lemma 21の適用 すべての j に対して、確率は少なくとも 1 − ρ である。
0.83
, we have 6γj v : |Tv(ε)| > Csn log 私たちには 6γj v : |Tv(ε)| > Csn log 0.74
µ Taking a union bound and noting that 1 γj log factor tells us that with probability at least 1 − ρ µ(cid:18)(cid:26)v : |Tv(ε)| > Crn log 1 γj ログファクタは、確率が少なくとも 1 − ρ μ(cid:18)(cid:26)v : |Tv(ε)| > Crn log であることを示す。 0.72
γ2 j ρ  ≤ ρ(cid:27)(cid:19) ≤ γ2 j ρ = ≤ ρ(cid:27)(cid:19) ≤ 0.86
γj = 2−j is summable, then pulling the square out of the γj = 2−j は和可能で、正方形を引き出す。 0.79
6 , we have, uniformly in j, 6 であり,j では一様であった。 0.61
1 γj (60) 1 γj 1γj (60) 1γj 0.86
(59) 16 (59) 16 0.85
英語(論文から抽出)日本語訳スコア
Now we look at the second event. さて、第2のイベントを見ます。 0.73
The identical argument serves to allow us to only consider γj. 同一の引数は γj のみを考慮できるように役立ちます。 0.71
We now apply Lemma 4 to Lemma 21 instead of Lemma 20. 現在、Lemma 20の代わりにLemma 4をLemma 21に適用しています。 0.49
In particular, note that for any γj, and any v, v′, we have 特に、任意の γj と任意の v, v′ に対して、我々は 0.76
+ log log (61) ログログ。 (61) 0.73
by Lemma 4. Lemma 4 による。 0.62
Thus, applying Lemma 21 with the measure ν, we have that with probability at least 1 − ρ したがって、測度 ν に補題 21 を適用すると、確率は少なくとも 1 − ρ となる。 0.78
γj , P(cid:12)(cid:12)T γj , は (cid:12)(cid:12)T 0.78
6γ2 j ρ v,v′(ε)(cid:12)(cid:12) > C(cid:12)(cid:12)(ci d:12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)slog v,v′(ε)(cid:12)(cid:12) > C(cid:12)(cid:12)(ci d:12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)slog 6γ2 j ρ v,v′(ε)(cid:12)(cid:12) > c(cid:12)(cid:12)(ci d:12)(cid:12)(cid:12 )(cid:12)(cid:12)(ci d:12)(cid:12)slog v,v′(ε)(cid:12)(cid:12) > c(cid:12)(cid:12)(ci d:12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12)slog 0.81
ν (v, v′) : (cid:12)(cid:12)T ν (v, v′) : (cid:12)(cid:12)T 0.83
ρ 6γ2 j 6√n ||v(ε) − v′(ε)|| ≤ ||v(ε) − v′(ε)||  ≤ ρ 6γ2 j 6 ||v(ε) − v′(ε)||\ ≤ ||v(ε) − v′(ε)||\ ≤ である。 0.73
3√n Applying a union bound and taking out the square from the logarithm and putting it into the constant C concludes the proof. 3分。 結合を適用し、対数から正方形を取り出し、それを定数 C に入れることは証明を締めくくる。 0.44
(cid:4) For the remainder, assume that the event of Lemma 22 holds and we will show how to bound f (z). (cid:4) 残りについては、補題22の事象が成立し、f(z) の束縛方法を示すと仮定する。 0.71
Define δj = 2−j and for any f, ε, define γj(f, ε) = 1/µ(Bδj (f, ε)). δj = 2−j と定義し、任意の f, ε に対して γj(f, ε) = 1/μ(bδj (f, ε)) を定義する。 0.76
Let N the supremum over T be the maximal integer such that δN ≥ 2α. N にしよう。 t 上の上限は δn ≥ 2α となる極大整数である。 0.67
Notice that it suffices to prove that (under the event of Lemma 22), for any f ∈ F, 任意の f ∈ F に対して (Lemma 22 のとき) を証明するのに十分であることに注意してください。
訳抜け防止モード: 十分であることに気付きます 任意の f ∈ f に対して(補題 22 の事象の下で)証明する
0.77
γ2 j ρ + log log γ2 j ρ ログログ。 0.78
1 γj (62) + nδN + √n 1γj (62) +nδN+n 0.82
1 ρ Tf (ε) ≤ Crn log ≤ Crn log rj(f, ε) = Cδj√nslog 1 ρ Tf (ε) ≤ C rn log ≤ C rn log rj(f, ε) = Cδj nslog 0.87
1 ρ + nα + √n δjqlog γj(f, ε) NXj=0 2−jslog NXj=0 1 ρ +nα+n δjqlog γj(f, ε)\ NXj=0 2−jslog NXj=0 0.79
µ(B2−j (f, ε)) . μ(B2−j (f, ε)) = 。 0.79
1 γj+1(f, ε) 1 γj+1(f, ε) 0.84
ρ + log log 3 δj ρ ログログ。 3 δj 0.78
Define (63) (64) 定義 (63) (64) 0.79
(65) for a sufficiently large C > 0 and j ≥ 0 integer. (65) 十分に大きな C > 0 と j ≥ 0 の整数に対して。 0.87
We write rj and γj when f, ε are obvious from context. f, ε が文脈から明らかであるとき rj と γj を書く。 0.80
We have that the following holds for any f, ε and j ≥ 1 (we refer to these inequalities as (†)): 任意の f, ε および j ≥ 1 に対して、以下が成り立つ(これらの不等式を ( ) と呼ぶ)。 0.67
µ ({v : |Tv(ε)| > r0(f, ε)}) ≤ μ ({v : |Tv(ε)| > r0(f, ε)}) ≤ 0.93
4γ0(f, ε) ν(cid:0)(cid:8)(v, v′) : (cid:12)(cid:12)T 4γ0(f, ε) ν(cid:0)(cid:8)(v, v′) : (cid:12)(cid:12)T 0.87
1 v,v′(ε)(cid:12)(cid:12) > rj(f, ε) and (cid:12)(cid:12)(cid :12)(cid:12)v(ε) − v(ε′)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj√n(cid:9)(cid:1) 1 v,v′(ε)(cid:12)(cid:12) > rj(f, ε) and (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) v(ε) − v(ε′)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj\n(cid:9)(cid:1) 0.80
. 9γj (f, ε)γj+1(f, ε) . 9γj (f, ε)γj+1(f, ε) 0.85
≤ 1 (66) (67) ≤ 1 (66) (67) 0.85
(68) Indeed, the first inequality is obtained from Lemma 22 by substituting γ = 4γ0(f, ε) and the second inequality is obtained by taking γ = 9γj(f, ε)γj+1(f, ε) ≤ 9γj+1(f, ε)2. mations for f (z) on the path ε, and obtain the bound (68) 実際、第1の不等式は γ = 4γ0(f, ε) を代入して Lemma 22 から得られ、第2の不等式は γ = 9γj(f, ε)γj+1(f, ε) ≤ 9γj+1(f, ε)2. f (z) を経路 ε 上で取ることで得られる。 0.85
Our goal is to construct a chain of elements vf,0, . 私たちの目標は、vf,0, . 要素の連鎖を構築することです。 0.60
. . , vf,N that provide finer and finer approxi- . . より細く、より良いapproxiを提供する、vf、N。 0.73
Tf (z) ≤ Tvf,0 + Tf (z) ≤ Tvf,0 + 0.94
N−1Xj=0 Tvf,j ,vf,j+1 + T N−1Xj=0 Tvf,j ,vf,j+1 + T 0.66
vf,N ,f (z). vf,n ,f (z) である。 0.80
17 17 0.85
英語(論文から抽出)日本語訳スコア
The approximations will be chosen from the sets A′j(f, ε) defined below: 近似は、以下に定義される集合 A′j(f, ε) から選択される。 0.73
Aj(f, ε) =(cid:8)v|||v(ε) − f (z(ε))|| ≤ √nδj(cid:9) A′j(f, ε) =(cid:26)v ∈ Aj(f, ε) : µ(cid:0)(cid:8)v′|(cid:12)(cid:12)T Aj(f, ε) =(cid:8)v||v(ε) − f(z(ε))|| ≤ anδj(cid:9) A′j(f, ε) =(cid:26)v ∈ Aj(f, ε) : μ(cid:0)(cid:8)v|(cid:12)(cid:12)T 0.86
3γj+1(cid:27) As a first step, we would like to lower bound µ(A′j(f, ε)) assuming we have ε such that (†) holds. 3γj+1(cid:27) 最初のステップとして、(\) が成り立つ ε を持つと仮定して、境界 μ(a′j(f, ε)) を下げたい。 0.77
v,v′(ε)(cid:12)(cid:12) > rj(f, ε) and (cid:12)(cid:12)(cid :12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj√n(cid:9)(cid:1) ≤ v,v′(ε)(cid:12)(cid:12) > rj(f, ε) および (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj\n(cid:9)(cid:1) ≤ である。 0.73
(69) (70) 1 (69) (70) 1 0.85
By construction, µ(Aj(f, ε)) ≥ 1 構成により、μ(Aj(f, ε)) ≥ 1 0.85
γj (f,ε) . For any v, let γj (f,ε)。 任意の v に対して、 0.70
B(v) =(cid:8)v′|(cid:12)(cid:12)T B(v) =(cid:8)v′|(cid:12)(cid:12)T 0.80
v,v′(ε)(cid:12)(cid:12) > rj(f, ε) and (cid:12)(cid:12)(cid :12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj√n(cid:9) v,v′(ε)(cid:12)(cid:12) > rj(f, ε) and (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj\n(cid:9) 0.75
and let Let From (†), we know that ν(B) ≤ そして、 はじめに から、 ν(B) ≤ を知っています。 0.51
9γj γj+1 . 9γj γj+1 . 0.65
By construction of ν, we have ν の構築により、私たちは 0.81
(71) (72) (73) (71) (72) (73) 0.85
(74) (75) (76) (74) (75) (76) 0.85
(77) (79) (80) (77) (79) (80) 0.85
B =[v [v′∈B(v)(cid:8)(v, v′)(cid:9) eB =(cid:26)v|µ(B(v)) > 3γj+1(cid:27) ν(B) ≥ µ(cid:16)B(v)|v ∈ eB(cid:17) µ(cid:16)eB(cid:17) B =[v[v′∂B(v)(cid:8)(v, v′)(cid:9) eB =(cid:26)v|μ(B(v)) > 3γj+1(cid:27) ν(B) ≥ μ(cid:16)B(v)|v ∈ eB(cid:17) μ(cid:16)eB(cid:17) 0.83
1 1 Thus we have 1 1 だから私たちは 0.80
µ (B(v)) ≥ μ (B(v)) ≥ 0.85
By construction, if v ∈ eB, then µ(cid:16)eB(cid:17) ≤ µ(cid:16)B(v)|v ∈ eB(cid:17) ≤ µ(A′j(f, ε)) ≥ µ(Aj(f, ε)) − µ(eB) ≥ v ∈ eB であれば、μ(cid:16)eB(cid:17) ≤ μ(cid:16)B(v)|v ∈ eB(cid:17) ≤ μ(A′j(f, ε)) ≥ μ(Aj(f, ε)) − μ(eB) ≥ 0.96
Thus we see that ν(B) だから私たちは ν(B) 0.75
3γj+1 1 1 9γj γj+1 3γj+1 1 1 9γj γj+1 0.63
1 3γj+1 = 1 3γj 1 3γj+1 = 1 3γj 0.70
1 γj − 1 3γj 1 γj − 1 3γj 0.82
= 2 3γj . As a final remark before we construct the chain, note that if v ∈ Aj(f, ε) and v′ ∈ Aj+1(f, ε), then by the triangle inequality, = 2 3γj . チェーンを構築する前に最後の発言として、v ∈ Aj(f, ε) と v′ ∈ Aj+1(f, ε) が三角不等式であることに注意してください。 0.81
(cid:12)(cid:12)(cid :12)(cid:12)v(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ ||v(ε) − f (z(ε))|| +(cid:12)(cid:12)(cid :12)(cid:12)v′(ε) − f (z(ε))(cid:12)(cid:12)(c id:12)(cid:12) ≤ δj√n + δj+1√n ≤ 2δj√n (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12)(cid:12)(cid :12) ≤ ||v(ε) − f(z(ε))|| +(cid:12)(cid:12)(cid :12)(cid:12)v′(ε) − f(z(ε))(cid:12)(cid:12)(c id:12)(cid:12)(cid:1 2)(cid:12)(cid:12) ≤ δj\n + δj+1\n ≤ 2δj\n) 0.71
We are now ready to construct the chain. 私たちは今、チェーンを構築する準備ができています。 0.56
Fix ε such that (†) holds. ) が保持する ε を修正します。 0.70
For notational simplicity, we suppress the dependence of vf,j,ε on ε and simply write vf,j; this causes no confusion as we have fixed ε. 表記の単純さのために、私たちはε に対する vf,j,ε の依存性を抑圧し、単純に vf,j を記述します。 0.71
For any f , we have 任意の f に対して、我々はある。 0.51
(78) Thus, letting j = 0, we see that there exists a vf,0 ∈ A′0(f, ε) such that (78) したがって、j = 0 とすると、vf,0 ∈ A′0(f, ε) が存在することが分かる。 0.83
µ(cid:0)A′j(f, ε) ∩ {v||Tv(ε)| > rj(f, ε)}c(cid:1) ≥ (cid:12)(cid:12)Tvf, 0(ε)(cid:12)(cid:12) ≤ r0(f, ε). μ(cid:0)A′j(f, ε) > {v||Tv(ε)| > rj(f, ε)c(cid:1) ≥ (cid:12)(cid:12)Tvf, 0(ε)(cid:12)(cid:12) ≤ r0(f, ε)。 0.82
18 2 3γj − 18 2 3γj − 0.82
1 3γj = 1 3γj 1 3γj = 1 3γj 0.75
> 0 > 0 0.85
英語(論文から抽出)日本語訳スコア
Now suppose that we have chosen vf,j ∈ A′j(f, ε). さて、vf,j ∈ a′j(f, ε) を選んだと仮定する。 0.74
We wish to select an element vf,j+1 ∈ A′j+1(f, ε) we have by definition 定義により有する元 vf,j+1 ∈ a′j+1(f, ε) を選択したい 0.84
such that(cid:12)(cid:12) Tvf,j,vf,j+1(ε)(cid:12)(cid:12) is small. cid:12)(cid:12)Tvf,j ,vf,j+1(ε)(cid:12)(cid:12)は小さい。 0.86
To see that this is possible, we remark that, as vf,j ∈ A′j(f, ε), これが可能であることを確かめるために、vf,j ∈ A′j(f, ε) として述べる。 0.82
µ(cid:0)(cid:8)v′|(cid:12)(cid:12)T μ(cid:0)(cid:8)v′|(cid:12)(cid:12)T 0.72
vf,j,v′(ε)(cid:12)(cid:12) > rj(f, ε) and (cid:12)(cid:12)(cid :12)(cid:12)vf,j(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj√n(cid:9)(cid:1) ≤ vf,j,v′(ε)(cid:12)(cid:12) > rj(f, ε) および (cid:12)(cid:12)(cid :12)(cid:12)vf,j(ε) − v′(ε)(cid:12)(cid:12)(ci d:12)(cid:12) ≤ 2δj\n(cid:9)(cid:1) ≤ である。 0.78
1 3γj+1 But we have already seen that 1 3γj+1 しかし、すでに見ています。 0.63
µ(A′j+1(f, ε)) ≥ μ(A′j+1(f, ε)) ≥ 0.86
2 3γj+1 1 and as noted, for any v′ ∈ A′j+1(f, ε), ||vf,j(ε) − v′(ε)|| ≤ 2δj√n. 2 3γj+1 1 そして、任意の v′ ∈ a′j+1(f, ε) に対して ||vf,j(ε) − v′(ε)|| ≤ 2δj\n である。 0.71
Thus µ takes measure at least on the set of such desirable next links in the chain and so such a vf,j+1 exists. したがって μ は少なくとも鎖内の望ましい次のリンクの集合上で測度を取るので、そのような vf,j+1 が存在する。 0.72
Thus for any f , on this ε, we have a chain vf,j for j ≥ 0 such that vf,j ∈ A′j(f, ε). したがって、この ε 上の任意の f に対して、vf,j ∈ A′j(f, ε) となるような j ≥ 0 の連鎖 vf,j が存在する。 0.83
Note that, by (78) and the way we have constructed the chain, we have that for all f , 注意すべき点は、 (78) と私たちがチェーンを構築した方法によって、すべての f に対してそうであることです。
訳抜け防止モード: 注意すべきなのは、(78)と私たちがチェーンを構築した方法です。 全てFだ
0.69
3γj+1 (81) 3γj+1 (81) 0.62
(82) (83) (84) (82) (83) (84) 0.85
(85) (86) (87) (85) (86) (87) 0.85
(88) We also have for any f that (88) また、すべての f に対してです。 0.70
Thus we see that on this ε, for every f , したがって、この ε 上、すべての f に対して、それを見る。 0.63
(cid:12)(cid:12)Tvf, j ,vf,j+1(ε)(cid:12)(cid:12) ≤ rj(f, ε). (cid:12)(cid:12)Tvf, j ,vf,j+1(ε)(cid:12)(cid:12) ≤ rj(f, ε)。 0.86
(cid:12)(cid:12)Tvf, 0(cid:12)(cid:12) ≤ r0(f, ε). (cid:12)(cid:12)Tvf, 0(cid:12)(cid:12)≤ r0(f, ε) 0.81
Tvf,j,ε,vf,j+1,ε(ε) + T Tvf,j,ε,vf,j+1,ε(ε) + T 0.95
f (z),vf,N,ε(ε) f(z)、vf、N、ε(ε) 0.79
≤ r0(f, ε) + ≤ r0(f, ε) + 0.94
Tf (ε) = Tvf,0,ε(ε) + XN≥j≥0 N−1Xj=0 N−1Xj=0 N−1Xj=0 Tf (ε) = Tvf,0,ε(ε) + XN≥j≥0 N−1Xj=0 N−1Xj=0 N−1Xj=0 0.53
≤ Crn log ≤ Crn log ≤ Crn log ≤ Crn log 0.85
1 ρ + 1 ρ + 1 ρ + 1 ρ + 0.85
rj(f, ε) + Cnδn(f, ε) rj(f, ε) + Cnδn(f, ε) 0.97
C√n qlog γj(f, ε) +slog log C√nqlog γj(f, ε)δj + δN (f, ε)n Cn qlog γj(f, ε) +slog log Cnqlog γj(f, ε)δj + δN (f, ε)n 0.93
3 δj! δj + δN (f, ε)n 3 δj! δj + δN (f, ε)n 0.90
where the inequality Tf (z),vf,N,ε(ε) follows from Cauchy-schwarz and the fact that vf,N ∈ AN (f, ε). ここで、不等式 Tf (z)、vf,N,ε(ε) はコーシーシュワルツと vf,N ∈ AN (f, ε) から従う。
訳抜け防止モード: ここで、不等式 Tf ( z)、vf, N, ε(ε ) はコーシー・シュワルツから続く。 そして、vf, N ∈ AN (f, f) が ε ) .
0.78
As (†) occurs with probability at least 1 − ρ, we have with the same probability that the above is bounded. 少なくとも 1 − ρ の確率で (\) が存在するので、上述の確率が有界であるのと同じ確率である。 0.78
This concludes the proof. B Proof of Theorem 13 これが証明である。 B Theorem 13の証明 0.77
In this appendix, we prove the auxiliary lemmata required to complete the proof of Theorem 13. この付録では、定理13の証明を完了させるために必要な補助レマタを証明している。 0.59
We begin with a result from Rakhlin et al. 私たちはRakhlinらの結果から始めます。 0.68
(2015): Lemma 23 (Rakhlin et al. (2015): Lemma 23 (Rakhlin et al。 0.83
(2015)). Let z be a Z-valued binary tree, F a class of functions Z → {0, 1, . (2015)). z を Z 値二項木とし、F を函数 Z → {0, 1, のクラスとする。 0.85
. . , m}, z0 the root of the tree, and Fj = {f ∈ F|f (z0) = j}. . . , m}, z0 は木の根であり、Fj = {f ∈ F|f (z0) = j} である。 0.87
Let r ≥ 1 be an integer. r ≥ 1 を整数とする。 0.73
If j, j′ ∈ {0, . j, j′ ∈ {0, である。 0.78
. . , m} such that fatr(Fj) = fatr(Fj′) = fatr(F), then |j − j′| < r. In particular, there can be at most r values of j such that fatr(Fj) = fatr(F). . . fj) = fatr(Fj′) = fatr(F), then |j − j′| < r. , m} である。
訳抜け防止モード: . . fatr(Fj ) = fatr(Fj′ ) = fatr(F ) のような ,m } である。 そして、 |j − j′| < r である。特に、fastr(Fj ) = fatr(F ) であるような j の r 値が最も多くある。
0.86
19 19 0.85
英語(論文から抽出)日本語訳スコア
Proof. Suppose that j, j′ ∈ {0, . 証明。 j, j′ ∈ {0, とする。 0.69
. . , m} such that j ≥ j′ + r. Let z(−1) and z(1) denote trees of depth fatr(F) that shatter at scale r the classes Fj and Fj′. . . j ≥ j′ + r となるように、z(−1) と z(1) は、スケール r において fj と fj′ のクラスを破る深さ fr(f) の木を表す。 0.82
Then, we can construct a tree of depth fatr(F) + 1 that r-shatters F by taking z0 as a root and taking z(±1) as subtrees of the root. すると、z0 を根とし、z(±1) を根の部分木とすることで、r が F を振る舞う深さ脂肪(F) + 1 の木を構築することができる。 0.74
This contradicts the fact that fatr(F) is the maximal depth of a tree that shatters F at scale r. The result follows. これは、fatr(f) がスケール r において f を粉砕する木の最大深さであるという事実と矛盾する。 0.81
(cid:4) We now provide the detailes for the proof of Proposition 14, sketched in the text. (cid:4) 現在,提案14の証明の詳細な内容がテキストにスケッチされている。 0.72
Proof of Proposition 14. Given a tree z and F, we construct the fractional cover µz,F recursively. 命題14の証明。 木 z と F を与えられると、分数被覆 μz,F を再帰的に構築する。 0.63
If z is an empty tree then define µz,F to have a unit mass on the empty tree. z が空木であれば、μz,F を空木上に単位質量を持つように定義する。 0.74
Otherwise, define by z0, z(−1) and z(1) its root and left and right subtrees, respectively (if the tree has depth zero then z(±1) are emty trees). さもなければ、z0, z(−1) と z(1) でその根と左と右のサブツリーをそれぞれ定義する(木が深さゼロの場合には、z(±1) はエンティツリーである)。 0.77
Further, define Fj = {f ∈ F : f (z0) = j} for 0 ≤ j ≤ m. We form µ as a mixture of measures µz,Fj,j and µz,F,j, where µz,G,j is defined as the measure on Y-valued trees v such that the root is labeled by i almost surely and the left and right subtrees are sampled independently from µz(−1),G and µz(1),G. さらに、0 ≤ j ≤ m に対して fj = {f ∈ f : f (z0) = j} を定義する。 μ を測度 μz,fj,j と μz,f,j の混合として形成する。
訳抜け防止モード: さらに、0 ≤ j ≤ m に対して Fj = { f ∈ F : f ( z0 ) = j } を定義する。 ここで μz, G, j は Y 上の測度として定義される -価値ある木v、そのような木v 根は私によって ほぼ確実にラベル付けされています そして、左右のサブツリーは μz(−1)G と μz(1),G と独立にサンプリングされる。
0.77
To define the mixture coefficients, we use Lemma 23 which tells us that if j < j′ are such that fat2(Fj) = fat2(Fj′) = fat2(F), then j′ = j + 1. 混合係数を定義するために、Lemma 23を使用し、j < j′ が Fat2(Fj) = fat2(Fj′) = fat2(F) であるなら、j′ = j + 1 である。 0.85
Let j∗ be the minimal j such that fat2(Fj) = fat2(F) (if such a j exists, if not let j∗ = 0) and notice that for j 6∈ {j∗, j∗ + 1}, it hold that fat2(Fj) ≤ fat2(F) − 1. j を最小 j とすると、fat2(Fj) = fat2(F) となる(もしそのような j が存在し、j が 0 を許さなければ)、j 6∈ {j\, j\ + 1} に対して、fat2(Fj) ≤ fat2(F) − 1 が成り立つ。 0.88
Fix 0 < p < 1 to be determined later and construct µz,F by sampling µz,F,j∗+1/2 with probability m−1 for all other j. 0 < p < 1 を後で決定し、他のすべての j に対して確率 m−1 で μz,f,j∗+1/2 をサンプリングすることで μz,f を構成する。
訳抜け防止モード: 修正 0 < p < 1。 後で決定される μz , F を他のすべての j に対して確率 m−1 でサンプリングして構成する。
0.85
We claim that with an appropriate 1− p, and sampling µz,Fj,j with probability choice of p, the above construction yields a 2 3 -fractional cover of the correct size. 適切な 1 − p で、μz,Fj,j を p の確率選択でサンプリングすると、上記の構成は正しい大きさの 2 3-フラクタル被覆が得られると主張する。 0.76
p In order to prove the claim, for a depth n binary tree z, let p この主張を証明するために、深度 n の二分木 z に対して、 0.76
φ(k, F, z) = min f∈F ε∈{±1}n φ(k, F, z) = min f∈F ε∈{±1}n 0.95
µ (v : nXt=0 μ (v): nXt=0 0.76
1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! 1{|vt(ε)−f(zt(ε))|*1} ≤ k)! 0.97
and let φ(k, d, n) = そして、 φ(k, d, n) = 0.73
min fat2(F)≤d 分 fat2(F)≤d 0.77
depth of z≤n φ(k, F, z). z≤n の深さ φ(k, f, z) である。 0.75
(89) (90) We claim (and prove as Lemma 24 at the conclusion of this proof so as not to interrupt the (89) (90) 我々は、この証明が中断しないように、この証明の結論において、レンマ24として主張(および証明する)する 0.76
argument) that φ(k, d, n) ≥ (1 − p)n+1+k(cid:18) p 議論) φ(k, d, n) ≥ (1 − p)n+1+k(cid:18) p 0.66
m(cid:17)d(cid:18) k d(cid:19)d k(cid:1) ≥ (n/k)k. for all 0 < p < 1, where the second inequality comes from the elementary lower bound(cid:0)n m(cid:17)d(cid:18)kd (cid:19)d k(cid:1) ≥ (n/k)k. for all 0 < p < 1 ここで2番目の不等式は初等下界(cid:0)nから来る。 0.76
d (cid:19) ≥ (1 − p)n+1+k(cid:16) p d (cid:19) ≥ (1 − p)n+1+k(cid:16) p 0.78
m − 1(cid:19)d(cid:18)k + d m − 1(cid:19)d(cid:18)k + d 0.92
Now, letting k = δn for δ = 7 ここで k = δn を δ = 7 とする。 0.85
n , we note that for n ≥ 2d, n は n ≥ 2d であることに注意する。 0.79
36m2 < 1 and p = d 36m2 < 1 と p = d 0.93
(91) φ(k, d, n) ≥(cid:18)1 − (91) φ(k, d, n) ≥(cid:18)1 − 0.88
≥ c(cid:18) e2δ dm(cid:19)d ≥ c(cid:18) e2δ dm(cid:19)d 0.78
d n(cid:19)2n(cid:18) d d n(cid:19)2n(cid:18)d 0.81
mn δn d (cid:19)d mn δn d (cid:19)d 0.84
Note that as vt(ε), f (zt(ε)) ∈ (cid:8)0, . vt(ε) として、f (zt(ε)) ∈ (cid:8)0, である。 0.81
. . , m, j∗ + 1 . . , m, j∗ + 1 0.89
Thus, if 2(cid:9), if |vt(ε) − f (zt(ε))| < 1, then it is at most 1 だから もし 2(cid:9), if |vt(ε) − f (zt(ε))| < 1 ならば、少なくとも 1 である。 0.77
2 . . (92) 2 . . (92) 0.85
nXt=0 1{|vt(ε)−f (zt(ε))|≥1} ≤ δn nXt=0 1{|vt(ε)−f (zt(ε))|≥1} ≤ δn 0.79
(93) 20 (93) 20 0.85
英語(論文から抽出)日本語訳スコア
then Recall that δ = 7 じゃあ δ = 7 をリコールする 0.75
||vt(ε) − f (zt(ε))||2 = 36m2 and this concludes the proof. ||vt(ε) − f (zt(ε))||2 = 36m2 で証明が終わる。 0.84
nXt=1 (vt(ε) − f (zt(ε)))2 ≤ m2δn + nXt=1 (vt(ε) − f (zt(ε)))2 ≤ m2δn + 0.94
1 2 (1 − δ)n. 1 2 (1 − δ)n である。 0.85
(94) (cid:4) (94) (cid:4) 0.82
We now prove the technical lemma used above: 上記の技術的難問を証明します 0.52
Lemma 24. Let φ(k, d, n) be as defined in the above proof. レマ24号。 φ(k, d, n) を上記の証明で定義する。 0.64
Then for all 0 < p < 1, and n ≥ −1 (where n = −1 corresponds to an empty tree), このとき、すべての 0 < p < 1 と n ≥ −1 に対して n = −1 は空の木に対応する)。 0.85
φ(k, d, n) ≥ (1 − p)n+1+k(cid:18) p φ(k, d, n) ≥ (1 − p)n+1+k(cid:18) p 0.90
m − 1(cid:19)d(cid:18)k + d d (cid:19) m − 1(cid:19)d(cid:18)k + d d (cid:19) 0.88
(95) Proof. We prove the result by induction on n. If n = −1 then the left hand side of (95) equals 1, while the right hand side equals (95) 証明。 n = −1 であれば、(95) の左辺は 1 に等しいが、右辺は 1 に等しい。 0.67
(1 − p)k(cid:18) p (1 − p)k(cid:18) p 1.00
m − 1(cid:19)d(cid:18)k + d m − 1(cid:19)d(cid:18)k + d 0.92
d (cid:19) ≤ (1 − p)kpd(cid:18)k + d d (cid:19) ≤ d (cid:19) ≤ (1 − p)kpd(cid:18)k + d d (cid:19) ≤ 0.93
(1 − p)k+d−ℓpℓ(cid:18)k + d ℓ (cid:19) k+dXℓ=0 = ((1 − p) + p)k+d = 1. 1 − p)k+d−lpl(cid:18)k + d l(cid:19)k+dXl=0 = ((1 − p) + p)k+d = 1 0.83
Thus, we may assume that n ≥ 0. したがって、n ≥ 0 と仮定できる。 0.69
We prove the following recursive formula: 次の再帰式を証明します。 0.66
φ(k, d, n) ≥ min φ(k, d, n) ≥ min である。 0.85
 p (1 − p)φ(k − 1, d, n − 1) + p m−1 φ(k, d − 1, n − 1) ∞  p (1 − p)φ(k − 1, d, n − 1) + p m−1 φ(k, d − 1, n − 1) ∞ 0.87
(1 − p)φ(k, d, n − 1), (1 − p)φ(k, d, n − 1), 0.80
m−1 φ(k, d − 1, n − 1) m−1 φ(k, d − 1, n − 1) 0.97
if k, d > 0 if k = 0, d > 0 if d = 0 k, d > 0 ならば k = 0, d > 0 ならば d = 0 である。 0.89
 (96)  (96) 0.85
To see this, consider a fixed f, ε. これを見るには、固定 f, ε を考える。 0.78
We divide into cases: 私たちはケースに分けます。 0.52
1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! 1{|vt(ε)−f(zt(ε))|*1} ≤ k)! 0.97
nXt=0 ≥ (1 − p)µz,F,j∗+1/2 (v : nXt=0 nXt=0 ≥ (1 − p)μz,F,j∗+1/2 (v : nXt=0) 0.74
If f (z0) ∈ {j∗, j∗ + 1}. f (z0) ∈ {j\,j\ + 1} ならば。 0.85
Recall that µz,F samples µz,F,j∗+1/2 with probability 1 − p. For any v ∈ support(µz,F,j∗+1/2) it holds that v0 = j∗ + 1/2 and so |v0 − f (z0)| ≤ 1 µz,F (v : 任意の v ∈ サポート (μz,F,j∗+1/2) に対して、v0 = j∗ + 1/2 であり、したがって |v0 − f (z0)| ≤ 1 μz,F (v :) である。 0.80
1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! 1{|vt(ε)−f(zt(ε))|*1} ≤ k)! 0.97
≥ (1 − p)φ(k, d, n − 1). ≥ (1 − p) φ(k, d, n − 1) である。 0.89
If f (z0) = j 6∈ {j∗, j∗ + 1} and k, d > 0. f (z0) = j 6 ≤ {j∗, j∗ + 1} と k, d > 0 である。 0.88
Here, differently from the previous case, for v ∈ support(µz,F,j∗+1/2) it holds that |v0 − f (z0)| ≥ 1. ここで、前例と異なり、v ∈ サポート(μz,F,j*+1/2) の場合、 |v0 − f (z0)| \ 1 である。 0.81
Additionally, recall that µz,F samples µz,Fj,j with probability m−1 . さらに、確率 m−1 の μz,F サンプル μz,Fj,j を思い出す。 0.81
For any v ∈ support(µz,Fj ,j), it holds that v0 = f (z0). 任意の v ∈ サポート (μz,Fj ,j) に対して、v0 = f (z0) となる。 0.90
Further, recall that fat2(Fj) ≤ fat2(F) − 1. さらに、fat2(Fj) ≤ fat2(F) − 1 を思い出す。 0.82
Hence, we see that in this case, したがって、この場合、私たちはそれを見る。 0.70
2 < 1. Hence, 2 < 1. それゆえ 0.77
p 1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! p 1{|vt(ε)−f(zt(ε))|*1} ≤ k)! 0.91
≥ (1−p)µz,F,j∗+1/2 (v : ≥ (1-p)μz,F,j∗+1/2 (v : 0.75
1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! 1{|vt(ε)−f(zt(ε))|*1} ≤ k)! 0.97
µz,F (v : nXt=0 μz,F(v: nXt=0 0.77
+ p m − 1 µz,Fj,j (v| + p m − 1 μz,Fj,j (v|) 0.83
nXt=0 nXt=0 1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! nXt=0 nXt=0 1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! 0.79
≥ (1 − p)φ(k − 1, d, n − 1) + ≥ (1 − p)φ(k − 1, d, n − 1) + 0.85
21 p m − 1 21 p m − 1 0.85
φ(k, d − 1, n − 1). φ(k, d − 1, n − 1) である。 0.90
英語(論文から抽出)日本語訳スコア
If f (z0) = j 6∈ {j∗, j∗ + 1} and k = 0, d > 0. f (z0) = j 6∂ {j∗, j∗ + 1} と k = 0, d > 0 である。 0.88
Similarly to the previous case, we have µz,F (v : 前例と同様、μz,F (v :) がある。 0.66
1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! 1{|vt(ε)−f(zt(ε))|*1} ≤ k)! 0.97
≥ µz,Fj,j (v| ≥ μz,Fj,j (v|) 0.82
1{|vt(ε)−f (zt(ε))|≥1} ≤ k)! 1{|vt(ε)−f(zt(ε))|*1} ≤ k)! 0.97
p m − 1 nXt=0 p m − 1 nXt=0 0.76
nXt=0 ≥ p m − 1 nXt=0 ≥ p m − 1 0.78
φ(k, d − 1, n − 1). φ(k, d − 1, n − 1) である。 0.90
If f (z0) = j 6∈ {j∗, j∗ + 1} and d = 0. f (z0) = j 6ب {j∗, j∗ + 1} と d = 0 である。 0.87
This case cannot hold. この事件は耐えられない。 0.55
Assume that it does towards contradiction. 矛盾に向いたと仮定する。 0.72
Since f (z0) = j 6∈ {j∗, j∗ + 1}, we have fat2(Fj) ≤ fat2(F) − 1 = −1, which derives the contradiction since the fat numbers are nonnegative. f (z0) = j 6∂ {j∗, j∗ + 1} であるため、脂肪数は非負であるため矛盾を生じる脂肪2(Fj) ≤ fat2(F) − 1 = −1 を持つ。 0.90
Thus we have shown (96). したがって、示した(96)。 0.82
We divide into cases. 私たちは事件に分かれる。 0.65
If the minimum in the right hand side of (96) equals (1 − p)φ(k, d, n − 1) then the claim trivially follows by induction hypothesis. 96) の右辺の最小値が (1 − p) φ(k, d, n − 1) と等しいなら、その主張は帰納的仮説によって自明に従う。 0.75
Otherwise, we divide into cases according to d, k. If k, d > 0 then もし k, d > 0 ならば、k は d, k に従ってケースに分割する。 0.74
φ(k, d, n) ≥ (1 − p)φ(k − 1, d, n − 1) + φ(k, d, n) ≥ (1 − p)φ(k − 1, d, n − 1) + 0.85
≥ (1 − p)n+k+1(cid:18) p ≥ (1 − p)n+k+1(cid:18) p 0.78
m − 1(cid:19)d(cid:18)(c id:18)k + d − 1 m − 1(cid:19)d(cid:18)(c id:18)k + d − 1 0.89
d p m − 1 φ(k, d − 1, n − 1) d p m − 1 φ(k, d − 1, n − 1) である。 0.86
(cid:19) +(cid:18)k + d − 1 (cid:19) +(cid:18)k + d − 1 0.90
d − 1 (cid:19)(cid:19) = (1 − p)n+k+1(cid:18) p d − 1 (cid:19)(cid:19) = (1 − p)n+k+1(cid:18) p 0.80
m − 1(cid:19)d(cid:18)k + d d (cid:19). m − 1(cid:19)d(cid:18)k + d d (cid:19)。 0.85
If k = 0, d > 0, we have k = 0, d > 0 であれば、 0.67
φ(k, d, n) ≥ φ(k, d, n) ≥ 0.85
p m − 1 φ(k, d − 1, n − 1) p m − 1 φ(k, d − 1, n − 1) である。 0.87
≥ (1 − p)n+1(cid:18) p ≥ (1 − p)n+1(cid:18) p 0.88
m − 1(cid:19)d(cid:18)d − 1 m − 1(cid:19)d(cid:18)d − 1 0.92
d − 1(cid:19) = (1 − p)n+1(cid:18) p d − 1(cid:19) = (1 − p)n+1(cid:18) p 0.88
m − 1(cid:19)d(cid:18)d d(cid:19), m − 1(cid:19)d(cid:18)d( cid:19) 0.93
as required. Lastly, the case d = 0 cannot hold, as we assumed that the minimum in the right hand side of (96) doe not equal (1 − p)φ(k, d, n − 1). 必要に応じて 最後に、(96) の右辺の最小値は (1 − p)φ(k, d, n − 1) と等しくないと仮定したように、d = 0 は保持できない。
訳抜け防止モード: 必要に応じて 最後に、(96 ) の右辺の最小値は (1 − p)φ(k,) と等しくないと仮定したので、d = 0 の場合を保持することはできない。 d , n − 1 ) である。
0.80
This concludes the proof. (cid:4) これが証明である。 (cid:4) 0.76
Using Proposition 14, we can bound the fractional covering number of a real valued function class, with respect to its fat-shattering dimension. 命題14を使用すると、脂肪散乱次元に関して、実値関数クラスの分数被覆数をバインドすることができる。 0.65
We introduce some notation. 表記法をいくつか導入する。 0.47
For any α > 0 and function class F taking values in the unit interval, let ⌊F⌋α be the α 2 -discretization of f , i.e., 2j 2f αk. 任意の α > 0 および関数クラス F に対して、単位間隔で値を取るとき、f の α 2-解離、すなわち 2j 2f αk とする。 0.88
Let G = 1 for any f ∈ F, let ⌊f⌋α = α α⌊F⌋α. 任意の f ∈ F に対して G = 1 とすると、 t f = α α = F となる。 0.67
We have the following lemma, reproven for the sake of completeness: 我々は以下の補題を持ち、完全性のために是正する。 0.62
Lemma 25 (Rakhlin et al. Lemma 25 (Rakhlin et al。 0.81
(2015)). With the notation as above, we have fat2(G) ≤ fatα(F). (2015)). 上記の表記法では、脂肪2(G)≤脂肪α(F) が存在する。 0.80
Proof. Multiplying by α, the statement is equivalent to fat2α(⌊F⌋α) ≤ fatα(F). 証明。 α を乗算すると、このステートメントは Fat2α ≤ fatα(F) と等価である。 0.72
Let w be a tree that shatters ⌊F⌋α at scale α of depth r. By definition, there exists a tree s such that for all ε ∈ {±1}r, there is an f ∈ F such that for all 1 ≤ t ≤ r 定義により、すべての ε ∈ {±1}r に対して、すべての 1 ≤ t ≤ r に対して f ∈ F が存在するような木 s が存在する。
訳抜け防止モード: w を深度 r のスケール α で「F」α を粉砕する木とする。 すべての ε ∈ { ±1}r に対して、木 s が存在する。 すべての 1 ≤ t ≤ r に対して f ∈ F が存在する。
0.83
Note that by construction, |⌊f⌋α − f| ≤ α 構造上は、|- f| ≤ α である。 0.75
εt (⌊f (wt(ε)⌋α − st(ε)) ≥ α 2 . εt ( εf (wt(ε))-α − st(ε)) ≥ α 2 である。 0.80
Thus for this f ∈ F, したがって、この f ∈ f に対して 0.74
εt (f (wt(ε) − st(ε)) ≥ εt (f (wt(ε) − ⌊f (wt(ε)⌋α) + εt (⌊f (wt(ε)⌋α − st(ε)) εt (f (wt(ε) − st(ε))) ≥ εt (f (wt(ε) − εf (wt(ε)/α) + εt ( wt(ε)/α − st(ε))) 0.91
Thus z also shatters F at scale α. したがって、z はスケール α で F を分解する。 0.62
≥ α − α 2 ≥ ≥ α − α 2 ≥ 0.85
α 2 (97) (98) α 2 (97) (98) 0.85
(99) (cid:4) (99) (cid:4) 0.82
22 22 0.85
英語(論文から抽出)日本語訳スコア
We are now ready to prove Theorem 13: 定理13を証明する準備ができています 0.69
Proof of Theorem 13. Theorem 13の証明。 0.77
We claim that for α = 6 α = 6 であると主張する。 0.78
N′(cid:0)G, 2 N′(cid:0)G, 2 0.86
3 , z(cid:1). 3, z(cid:1。 0.74
To see this, note that if v such that ||v(ε) − ⌊f⌋α(z(ε))|| ≤ 4 これを見るには、v が ||v(ε) − \f\α(z(ε))|| ≤ 4 となると注意する。 0.77
triangle inequality implies 7 δ and with the notation defined above, N′(F, δ, z) ≤ 7 δn, then we see that the 三角形の不等式は 7 δ で、上述の記法で定義される n′(f, δ, z) ≤ 7 δn とすると、そのことが分かる。 0.63
||v(ε) − f (z(ε)|| ≤ ||v(ε) − ⌊f⌋α(z(ε))|| + ||f (z(ε)) − ⌊f⌋α(z(ε))|| ≤ ||v(ε) − f (z(ε)|| ≤ ||v(ε) − ||f\α(z(ε))|||||||f(z(ε))|| ≤ 0.97
4 7 δn + 3 7 4 7 δn + 3 7 0.86
δn = δn (100) δn = δn (100) 0.82
Thus if µ is a 4 α = 6 したがって μ が 4 α = 6 であれば 0.94
(cid:8)0, 1, . (cid:8)0,1。 0.69
. . ,(cid:4) 2 . . ,(cid:4) 2 0.90
7 δ fractional cover on ⌊F⌋α, then it is a δ-cover on F for α = 6 7 δ の分数被覆で、α = 6 の f 上の δ-被覆である。 0.79
7 δ shows that if N′(cid:0)⌊F⌋α, 4 α(cid:5)(cid:9). 7 δ は N′(cid:0) であるなら 4 α(cid:5)(cid:9) を示す。 0.80
Thus, setting m = 2 N′(F, δ, z) ≤ N′(cid:18)G, したがって、設定 m = 2 N′(F, δ, z) ≤ N′(cid:18)G, 0.93
3δ and applying Proposition 14 gives 3δ と Proposition 14 の適用 0.90
7 δ, z(cid:1) = N′(cid:0)G, 2 3 , z(cid:1). 7 δ, z(cid:1) = N′(cid:0)G, 2 3 , z(cid:1)。 0.86
Now, by construction, G takes values in , z(cid:19) ≤ C 36e 3δ(cid:19)3!fat2(G 7 (cid:18) 7 ここで G は , z(cid:19) ≤ C 36e 3δ(cid:19)3!fat2(G 7 (cid:18) 7 の値を取る。 0.84
≤ C(cid:18) 4e ≤ C(cid:18) 4e 0.82
147δ3(cid:19)fat 6 147δ3(cid:19)fat 6 0.75
7 δ. Scaling by 7 δ. スケーリング 0.62
α = 7 7 δ(F) α = 7 7 δ(F) 0.85
(101) 2 3 as desired. (101) 2 3 好きなように 0.74
(cid:4) C Proof of Proposition 15 (cid:4) C Proposition 15 の証明 0.78
We start by proving Proposition 16. 提案16の証明から始めます。 0.71
We first consider the case Y = {1, . まず、ケース Y = {1, . を考える。 0.64
. . , m} and prove: Proposition 26. . . , m} と証明する: 命題26。 0.82
Suppose that F is a collection of functions from Z to Y = {1, . F が Z から Y = {1, . への関数の集合であると仮定する。 0.83
. . , m} and δ ≥ 2. . . , m} と δ ≥ 2 である。 0.85
Then where C > 0 is a universal constant. その後 ここで c > 0 は普遍定数である。 0.78
N′(F, δ) ≤ N′(F, δ) ≤ 0.96
log mYi=1 (cid:18) C i log mYi=1 (cid:18) C i 0.78
δ (cid:19)fat2i (F) δ (cid:19)fat2i (F) 0.81
, (102) Below, we present the proof of Proposition 26 and then we prove Proposition 16 and finally Proposition 15. , (102) 以下に、提案26の証明を提示し、提案16と最終的に提案15を証明します。 0.78
First, we can assume that m is an integer power of 2. まず、m が 2 の整数の力であると仮定することができる。 0.73
Given a tree z and a concept class F, we construct the fractional cover µ = µz,F inductively. 木 z と概念類 F を与えられると、分数被覆 μ = μz,F を帰納的に構築する。 0.76
We define µ to be a sub-probability distribution, namely, each element has a non-negative measure and the sum of measures is at most 1. μ をサブ確率分布と定義し、すなわち各要素は非負の測度を持ち、測度の合計は最大 1 である。 0.78
By normalizing µ, one can derive a proper probability measure. μ を正規化することで、適切な確率測度を導出できる。 0.72
Suppose we have a binary tree z. バイナリツリー z があると仮定する。 0.62
If z is an empty tree then µz,F has a unit mass on the empty tree. z が空木であれば、μz,F は空木上に単位質量を持つ。 0.68
Otherwise, define by z0, z(−1) and z(1) its root and left and right sub-trees, respectively (if the tree has depth zero then z(±1) are empty trees). さもなくば、z0, z(−1) と z(1) の根と右部分木によって定義される(木が深さ 0 であれば、z(±1) は空木である)。 0.76
For any concept-class G, define by µz,G,i the measure on Y-valued trees v such that the root is labeled by i almost surely and the left and right sub-trees are sampled independently from µz(−1),G and µz(1),G. 任意の概念クラス G に対して、 μz,G,i によって定義される Y 値木 v 上の測度は、根が i によってほぼ確実にラベル付けされ、左右のサブツリーは μz(−1),G と μz(1),G から独立してサンプリングされる。 0.74
Define Fj = {f ∈ F : f (z0) = j} for j ∈ [m]. j ∈ [m] に対して Fj = {f ∈ F : f (z0) = j} を定義する。 0.93
For j = 1, . j = 1 の場合。 0.75
. . , m denote i(j) = max{i : 1 ≤ i ≤ log2 m, fat2i(Fj) < fat2i(F)} . . m は i(j) = max{i : 1 ≤ i ≤ log2 m, fat2i(Fj) < fat2i(F)} を表す。 0.87
with i(j) = 0 if fat2i(Fj) = fat2i(F) for all i. i(j) = 0 の場合、すべての i に対して fat2i(Fj) = fat2i(F) である。 0.77
Let j∗ be an (arbitrarily chosen) minimizer of i(j). j を i(j) の最小値(任意に選択)とする。 0.69
We define µz,F. μz,F を定義する。 0.78
which is parametrized by some parameter p to be set later, as follows: For any パラメータ p がパラメータ p でパラメータ化して後で設定すると、次のようになる。 0.67
binary tree v, define µz,F(v) = (1 − p)µz,F,j∗(v) + 二分木 v の定義 μz,F(v) = (1 − p)μz,F,j*(v) + 0.84
mXj=1 λjµz,Fj,j(v), where λj = 4−i(j)−1p. mXj=1 λjμz,Fj,j(v) ここで λj = 4−i(j)−1p となる。 0.67
23 23 0.85
英語(論文から抽出)日本語訳スコア
Observe that the first measure in the sum, µz,F,j∗, corresponds to the class F while the remaining measures, µz,Fj,j for j ∈ [m], correspond to the restricted concept classes Fj. 和の最初の測度である μz,F,j* は F 類に対応し、残りの測度である μz,Fj,j は j ∈ [m] に対して制限された概念類 Fj に対応する。 0.75
Second, note that sub-probability measure, it suffices to show that this sum is upper bounded by 1. 第二に、sub-probability measureは、この和が 1 で上界であることを示すのに十分である。 0.69
To do this, we use Lemma 23 from Appendix B. これを行うには、Appendix BのLemma 23を使用します。 0.72
the sum of mixture coefficients, 1 − p +Pj λj, does not necessarily equal 1. 混合係数 1 − p + pj λj の和は必ずしも 1 に等しいとは限らない。 0.85
Since, we define a 以来、a を定義する。 0.59
By Lemma 23, there are at most 2i+1 classes with i(j) = i, hence, Lemma 23 では、 i(j) = i を持つ最大 2i+1 クラスが存在する。 0.87
1 − p + mXj=1 1 − p + mXj=1 0.72
λj ≤ 1 − p + λj ≤ 1 − p + 0.97
log2 mXi=0 log2 mXi=0 0.59
|{j : i(j) = i}| |{j : i(j) = i}| 0.85
p 4i+1 ≤ 1 − p + p 4i+1 ≤ 1 − p + 0.86
log2 mXi=0 log2 mXi=0 0.59
2i+1p 4i+1 = 1 − p + 2i+1p 4i+1 = 1 − p + 0.63
log2 mXi=0 log2 mXi=0 0.59
p 2i+1 ≤ 1, p 2i+1 ≤ 1。 0.77
which implies that we defined a sub-probability distribution as required. つまり、サブ確率分布を必要に応じて定義しました。 0.67
We claim that with an appropriate choice of p, the above construction yields a δ-fractional cover of the correct size. p の適切な選択により、上記の構成は正しいサイズのδ-フラクショナル被覆が得られると主張している。 0.74
In order to prove the claim, we introduce some notation. その主張を証明するために、いくつかの表記を導入する。 0.56
For a depth n binary tree z, a vector −→k = (k1, . 深さ n の二分木 z に対して、ベクトル −→k = (k1, .)。 0.57
. . , klog2 m) a concept class F, a function f and a path ε, denote the following set of [m]-labelled trees that contains all trees that are close to f (z) on some path ε, where the closeness is measured with respect to −→k : . . , klog2 m) 概念類 F, 関数 f, 経路ε は、ある経路ε 上の f(z) に近いすべての木を含む[m]-ラベル付き木の次の集合を表し、そこで近さは −→k : に関して測定される。 0.83
E(−→k , f, ε, z) = E(−−−k , f, ε, z) = 0.87
. ki′ log2 mXi′=i 2 ≤ CPi 4iki/n. . i 2 ≤ CPi 4iki/n。 0.76
(103) v : ∀i = 1, . (103) v : 「i = 1」。 0.76
. . , log2 m,|{t : 0 ≤ t ≤ n,|vt(ε) − f (zt(ε))| ≥ 2i}| ≤ . . , log2 m,|{t : 0 ≤ t ≤ n,|vt(ε) − f (zt(ε))| ≥ 2i}| ≤ である。 0.87
As we shall show later, for all v ∈ E(−→k , f, ε, z) it holds that kv(ε) − f (z(ε))k2 後で示すように、すべての v ∈ e(−→k , f, ε, z) に対して、kv(ε) − f(z(ε))k2 が成り立つ。 0.86
Next, we define: φ(−→k , F, z) = min f∈F ε∈{±1}n 次に定義します φ(−→k , F, z) = min f∈F ε∈{±1}n 0.77
µ(cid:16)E(−→k , f, ε, z)(cid:17) μ(cid:16)E(−→k , f, ε, z)(cid:17) 0.88
Where µ is as constructed above. μ は上述の通りである。 0.69
Notice that φ(−→k , F, z) can be used to bound the fractional covering numbers of F, since E(−→k , f, ε, z) contains trees that approximate f on ε. Lastly, for a vector −→d = (d1, . e(−→k , f, ε, z) は e(−→k , f, ε, z) が ε 上の f に近似する木を含むので、f の分数被覆数を束縛するために φ(−→k , f, z) が用いられることに注意する。 0.75
. . , dlog2 m), the following definition bounds the minimal value of ϕ taken over concept-classes F whose fat covering numbers are bounded in terms of −→d , as defined below: . . 以下の定義は、次の定義で定義されるように、脂肪被覆数が −→d の点で有界である概念クラス F に取られる φ の最小値にバインドされる。 0.81
ϕ(−→k ,−→d , n) = φ(−→k ,−→d , n) = 0.98
min F,z : ∀i=1,...,log2 m,fat2i (F)≤di min F,z : i = 1, ...,log2 m,fat2i (F)≤di 0.79
depth of z≤n φ(−→k , F, z). z≤n の深さ φ(−→k , F, z)。 0.77
(104) Here, n ≥ −1 where n = −1 corresponds to the empty tree. (104) ここで、n = −1 が空木に対応する n は −1 である。 0.82
Define ei as the vector with 1 in coordinate i and zeros otherwise. ei を座標 i と零点で 1 のベクトルとして定義する。 0.82
One can prove the following inductive formula: 次の誘導式を証明できます。 0.72
Lemma 27. For any n ≥ 0, レマ27号。 任意の n ≥ 0 に対して 0.67
ϕ(−→k ,−→d , n) ≥ φ(−→k ,−→d , n) ≥ 0.98
min i=0,...,log2 m 分 i=0,...,log2 m 0.76
ϕi(−→k ,−→d , n). φi(−→k ,−→d , n)。 0.82
where ϕ0(−→k ,−→d , n) = (1 − p)ϕ(−→k ,−→d , n − 1) and for all i = 1, . φ0(−→k ,−→d , n) = (1 − p)φ(−→k ,−→d , n − 1) であり、すべての i = 1 である。 0.93
. . , log2 m . . ,log2m 0.84
ϕi(−→k ,−→d , n) = φi(−→k ,−→d , n) = 0.89
4−i−1pϕ(−→k ,−→d − ei, n) + (1 − p)ϕ(−→k − ei,−→d , n − 1) ki, di > 0 4−i−1pϕ(−→k ,−→d − ei, n) ∞ 4−i−1pφ(−→k ,−→d − ei, n) + (1 − p)φ(−→k − ei,−→d , n − 1) ki, di > 0 4−i−1pφ(−→k ,−→d − ei, n) ∞ 0.84
ki = 0, di > 0 di = 0 ki = 0, di > 0 di = 0 0.85
. 24 . 24 0.85
英語(論文から抽出)日本語訳スコア
Proof. Fix z and F such that fat2i(F) ≤ di for all i. 証明。 すべての i に対して fat2i(F) ≤ di となるような z と F を修正する。 0.65
Fix f and ε, denote j = f (z0). f と ε を固定し、j = f (z0) と表す。 0.79
We would like to argue that µ(E(−→k , f, ε, z)) ≥ ϕi(j)(−→k ,−→d , n). μ(E(−→k , f, ε, z)) ≥ φi(j)(−→k ,−→d , n) である。 0.78
For any tree v, denote by v(ε) the sub-tree of v, 任意の木 v に対して、v(ε) を v の部分木で表す。 0.71
rooted by a child of the root of v, that contains the sub-path ε1:n. To derive the proof, we divide into cases: v の根の子供によって根ざされ、証明を引き出すための部分パス ε1:n を含む。
訳抜け防止モード: v のルートの子によってルート化され、サブパス ε1 : n を含む。 証明を導き出す。 私たちはケースに分けます
0.75
1. If i(j) = 0: This follows from the fact that |j − j∗| < 2i(j)+1 = 2 and from the definition of 1. i(j) = 0 ならば、これは |j − j | < 2i(j)+1 = 2 であるという事実と、定義から従う。 0.87
E(−→k , f, ε, z), one has: E(−→k , f, ε, z) が成り立つ。 0.75
E(−→k , f, ε, z) ⊇ {v : v E(−→k , f, ε, z) , {v : v 0.94
(ε) ∈ E(−→k , f, ε1:n, z (ε) ∈ E(−→k , f, ε1:n, z 0.99
(ε)), root(v) = j∗}. (ε)), root(v) = j∗} である。 0.87
As a consequence, µz,F,j∗(E(−→k , f, ε, z)) ≥ µz(ε),F(E(−→k , f, ε1:n, z 結果として。 μz,F,j∗(E(−→k , f, ε, z)) ≥ μz(ε),F(E(−→k , f, ε1:n, z) 0.87
(ε))) ≥ φ(−→k , F, z (ε))) ≥ φ(−→k , f, z 0.95
(ε)). Therefore, (ε)). そのため 0.81
µ(E(−→k , f, ε, z)) ≥ (1 − p)µz,F,j∗(E(−→k , f, ε, z)) μ(E(−→k , f, ε, z)) ≥ (1 − p)μz,F,j∗(E(−→k , f, ε, z)) 0.96
≥ (1 − p)φ(−→k , F, z (ε)) ≥ (1 − p)ϕ(−→k ,−→d , n − 1) = ϕ0(−→k ,−→d , n). ≥ (1 − p)φ(−→k , F, z (ε)) ≥ (1 − p)φ(−→k ,−→d , n − 1) = φ0(−→k ,−→d , n)。 0.93
2. If i(j) > 0 and ki(j), di(j) > 0: First, notice that 2. i(j) > 0 および ki(j) の場合、di(j) > 0: まず、そのことに注意してください。 0.84
E(−→k , f, ε, z) ⊇ {v : v E(−→k , f, ε, z) , {v : v 0.94
(ε) ∈ E(−→k , f, ε1:n, z (ε) ∈ E(−→k , f, ε1:n, z 0.99
(ε)), root(v) = j}. (ε), root(v) = j} である。 0.84
This implies that µz,Fj ,j(E(−→k , f, ε, z)) ≥ µz(ε),Fj これが意味する。 μz,Fj ,j(E(−→k , f, ε, z)) ≥ μz(ε),Fj 0.77
(E(−→k , f, ε1:n, z (E(−→k , f, ε1:n, z) 0.88
(ε))) ≥ φ(−→k , Fj, z (ε))) ≥ φ(−→k , fj, z 0.94
(ε)). Further, using the fact that i(j) > 0, one has (ε)). さらに、i(j) > 0 であるという事実を使用して、 0.83
E(−→k , f, ε, z) ⊇ {v : v E(−→k , f, ε, z) , {v : v 0.94
(ε) ∈ E(−→k − ei(j), f, ε1:n, z (ε) ∈ E(−→k − ei(j), f, ε1:n, z 0.93
(ε)), root(v) = j∗}, (ε)), root(v) = j∗}, 0.73
which implies that (105) (106) つまり (105) (106) 0.67
(107) (108) (107) (108) 0.85
(109) (110) (109) (110) 0.85
(111) (112) (111) (112) 0.85
(113) µz,F,j∗(E(−→k , f, ε, z)) ≥ µz(ε),F(E(−→k − ei(j), f, ε1:n, z (113) μz,F,j∗(E(−→k , f, ε, z)) ≥ μz(ε), F(E(−→k − ei(j), f, ε1:n, z) 0.92
(ε))) ≥ φ(−→k − ei(j), F, z (ε))) ≥ φ(−→k − ei(j), f, z 0.88
(ε)). (114) (ε)). (114) 0.85
From (112) and (114), から(112)と(114)。 0.66
µ(E(−→k , f, ε, z)) ≥ (1 − p)µz,F,j∗(E(−→k − ei(j), f, ε, z)) + 4−i(j)−1pµz,Fj,j(E(−→k , f, ε, z)) μ(E(−→k , f, ε, z)) ^ (1 − p)μz, F,j(E(−→k − ei(j), f, ε, z)) + 4−i(j)−1pμz, Fj,j(E(−→k , f, ε, z)) 0.98
≥ (1 − p)ϕ(−→k − ei(j), F, z ≥ (1 − p)φ(−→k − ei(j), F, z 0.89
(ε)) + 4−i(j)−1pφ(−→k , Fj, z (ε) + 4−i(j)−1pφ(−→k , Fj, z 0.86
(ε)). From the definition of i(j), one has that fat2i(j)(Fj) < fat2i(j) (F). (ε)). i(j) の定義から、その fat2i(j)(Fj) < fat2i(j) (F) を持つ。 0.84
Hence, from (115), µ(E(−→k , f, ε, z)) ≥ (1 − p)ϕ(−→k − ei(j),−→d , n − 1) + 4−i(j)−1pϕ(−→k ,−→d − ei(j), n − 1) したがって、 (115), μ(e(−→k , f, ε, z)) ≥ (1 − p) φ(−→k − ei(j),−→d , n − 1) + 4−i(j)−1pφ(−→k ,−→d − ei(j), n − 1) から。 0.96
= ϕi(j)(−→k ,−→d , n). = φi(j)(−→k ,−→d ,n)。 0.89
25 (115) (116) 25 (115) (116) 0.85
(117) (117) 0.85
英語(論文から抽出)日本語訳スコア
3. If i(j) > 0, ki(j) = 0 and di(j) > 0: Using a similar argument as in the previous case, 3. i(j) > 0 の場合、ki(j) = 0 と di(j) > 0: 前の例のように同様の引数を使用します。 0.85
µ(E(−→k , f, ε, z)) ≥ 4−i(j)−1pµz,Fj,j(E(−→k , f, ε, z)) ≥ 4−i(j)−1pφ(−→k , Fj, z μ(E(−→k , f, ε, z)) ≥ 4−i(j)−1pμz, Fj,j(E(−→k , f, ε, z)) ≥ 4−i(j)−1pφ(−→k , Fj, z)) 0.84
≥ 4−i(j)−1pϕ(−→k ,−→d − ei(j), n − 1) = ϕi(j)(−→k ,−→d , n). ≥ 4−i(j)−1pφ(−→k ,−→d − ei(j), n − 1) = φi(j)(−→k ,−→d , n)。 0.89
(ε)) 4. If i(j) > 0 and di(j) = 0: this cannot hold, since 0 ≤ fat2i(j)(Fj) < fat2i(j)(F) ≤ di(j). (ε)) 4. i(j) > 0 および di(j) = 0 の場合: 0 ≤ fat2i(j)(Fj) < fat2i(j)(F) ≤ di(j) なので、これは保持できない。 0.89
We proceed with bounding ϕ(−→k ,−→d ,−→n ): φ(−→k ,−→d ,−→n ) を境界とする。 0.79
Lemma 28. Let φ(−→k ,−→d , n) be as defined in the above proof. レマ28号。 φ(−→k ,−→d , n) を上記の証明で定義する。 0.69
Then for all 0 < p < 1, n ≥ −1 and k1, . このとき、すべての 0 < p < 1, n ≥ −1 と k1, に対して。 0.71
. . , klog2 m, d1, . . . klog2 m, d1, . 0.88
. . , dlog2 m ≥ 0, . . , dlog2 m ≥ 0。 0.87
φ(−→k ,−→d , n) ≥ (1 − p)n+1+P φ(−→k ,−→d ,n) ≥ (1 − p)n+1+P 0.85
log2 m i=1 log2 m i=1 0.67
ki log2 mYi=1 (cid:16) p キ log2 mYi=1 (cid:16) p 0.64
di (cid:19). di (cid:19)。 0.81
4i+1(cid:17)di(cid:18)k i + di 4i+1(cid:17)di(cid:18)k i + di 0.74
(118) Proof. We prove the result by induction on n. For the base of induction, we assume that n = −1. (118) 証明。 誘導の基底に対して、n = −1 と仮定する。
訳抜け防止モード: (118) 証明。 n 上の誘導により結果を証明します。 n = −1 と仮定する。
0.71
Then the left hand side of (118) equals 1, while the right hand side is at most 1, as follows from the following argument: For all i, すると(118) の左辺は 1 に等しいが、右辺は次の引数で示されるように、最大 1 に等しい。
訳抜け防止モード: その後、(118)の左側が1に等しい。 以下の引数から次のように、右側が最大1である間:すべてのiのために、。
0.80
(cid:4) (1 − p)ki(cid:16) p (cid:4) (1 − p)ki(cid:16) p 0.89
4i+1(cid:17)di(cid:18)k i + di 4i+1(cid:17)di(cid:18)k i + di 0.74
di (cid:19) ≤ (1 − p)kipdi(cid:18)ki + di di (cid:19) di (cid:19) ≤ (1 − p)kipdi(cid:18)ki + di (cid:19) 0.96
ki+diXℓ=0 (1 − p)ki+di−ℓpℓ(cid:18)ki + di ℓ (cid:19) ki+diXl=0 (1 − p)ki+di−lpl(cid:18)ki+di l(cid:19) 0.59
≤ = ((1 − p) + p)ki+di = 1. ≤ = ((1 − p) + p)ki+di = 1。 0.94
(119) (120) (119) (120) 0.85
(121) For n ≥ 0, we would like to lower bound ϕi(−→k ,−→d , n) by the right hand side of (118), for all i = 0, . (121) n ≥ 0 に対して、すべての i = 0, に対して (118) の右辺で境界 φi(−→k ,−→d , n) を下げたい。 0.80
. . , log n. First, for i = 0, this follows directly from the induction hypothesis. . . まず、i = 0 の場合、これは誘導仮説から直接従います。 0.75
For i ≥ 1, divide into cases. i ≥ 1 の場合、ケースに分割する。 0.77
First, assume that ki, di > 0. まず、ki, di > 0 と仮定します。 0.83
Then, by induction hypothesis ϕi(−→k ,−→d , n) = すると、帰納仮説φi(−→k ,−→d , n) = 0.82
p using the equality 26 p 平等を使って 26 0.84
4i+1 ϕ(−→k ,−→d − ei, n) + (1 − p)ϕ(−→k − ei,−→d , n − 1) ≥ (1 − p)n+Pi′6=i ki′Yi′6=i(cid:16) p (cid:18) p 4i+1 · (1 − p)ki(cid:16) p = (1 − p)n+1+P 4i+1 φ(−→k ,−→d − ei, n) + (1 − p)φ(−→k − ei,−→d ,n − 1) ≥ (1 − p)n+Pi′6=i Ki′Yi′6=i(cid:18)p 4i+1 · (1 − p)ki(cid:16)p = (1 − p)n+1+P 0.84
4i′+1(cid:17)di′(cid:18)ki′ + di′ di′ (cid:19)· 4i+1(cid:17)di−1(cid:18)ki + di − 1 4i′+1(cid:17)di′(cid:18)ki′ + di′ di′(cid:19)· 4i+1(cid:17)di−1(cid:18)ki + di − 1 0.67
log2 m i=1 log2 m i=1 0.67
ki di − 1 (cid:19) + (1 − p) · (1 − p)ki−1(cid:16) p 4i+1(cid:17)di(cid:18)k i + di di (cid:19), k (cid:19) +(cid:18)n − 1 k − 1(cid:19). キ di − 1 (cid:19) + (1 − p) · (1 − p)ki−1(cid:16) p 4i+1(cid:17)di(cid:18)k i + di (cid:19), k (cid:19) +(cid:18)n − 1 k − 1(cid:19)。 0.74
log2 mYi=1 (cid:16) p (cid:18)n k(cid:19) =(cid:18)n − 1 log2 mYi=1 (cid:16) p (cid:18)n k(cid:19) =(cid:18)n − 1 0.78
4i+1(cid:17)di(cid:18)k i − 1 + di 4i+1(cid:17)di(cid:18)k i − 1 + di 0.78
di (cid:19)(cid:19) ディ (cid:19)(cid:19) 0.63
英語(論文から抽出)日本語訳スコア
Next, assume that ki = 0. 次に ki = 0 と仮定します。 0.83
Then, ϕi(−→k ,−→d , n) = そしたら φi(−→k ,−→d , n) = 0.76
p p ≥ 4i+1 ϕ(−→k ,−→d − ei, n) 4i′+1(cid:17)di′(cid:18)ki′ + di′ 4i+1 · (1 − p)n+Pi′6=i ki′Yi′6=i(cid:16) p 4i′+1(cid:17)di′(cid:18)ki′ + di′ di′ (cid:19) ·(cid:16) p = ·(1 − p)n+Pi′6=i ki′Yi′6=i(cid:16) p di (cid:19). p p ≥ 4i+1 φ(−→k ,−→d − ei, n) 4i′+1(cid:17)di′(cid:18)ki′ + di′ 4i+1 · (1 − p)n+Pi′6=i Ki′Yi′6=i(cid:16)p 4i′+1(cid:17)di′(cid:18)ki′ + di′ di′ (cid:19) ·(cid:16)p = ·(1 − p)n+Pi′6=i Ki'6=i(cid:16)p di′(cid:19) 0.80
4i+1(cid:17)di(cid:18)k i + di log2 mYi=1 (cid:16) p 4i+1(cid:17)di(cid:18)k i + di log2 mYi=1 (cid:16) p 0.71
= (1 − p)n+1+P = (1 − p)n+1+P 0.78
log2 m i=1 log2 m i=1 0.67
ki 4i+1(cid:17)di−1(cid:18)di − 1 di − 1(cid:19) di′ (cid:19) ·(cid:16) p 4i+1(cid:17)di(cid:18)d i di(cid:19) キ 4i+1(cid:17)di−1(cid:18)di − 1 di − 1(cid:19) di′ (cid:19) ·(cid:16) p 4i+1(cid:17)di(cid:18)d i di(cid:19) 0.66
Lastly, assume that di = 0. 最後に、 di = 0 と仮定する。 0.83
Then, ϕi(−→k ,−→d , n) = ∞, and the statement holds as well. すると φi(−→k ,−→d ,n) = ∞ となり、その言明も成り立つ。 0.83
Proof of Proposition 26. プロポーション26の証明。 0.63
Define ki = 8−iδn for i = 1, . i = 1 に対して ki = 8−iδn を定義する。 0.66
. . , log2 n and notice that it suffices to show that . . 対訳 log2 n かつそれを示すのに十分であることに気付きます 0.76
(cid:4) log2 mYi=1 (cid:0)ciδ(cid:1)fat2i (F) Indeed, for any f, ε, and any v ∈ E(−→k , f, ε, z), it holds that (cid:4) log2 mYi=1 (cid:0)ciδ(cid:1)fat2i (F) 実際、任意の f, ε および任意の v ∈ E(−→k , f, ε, z) に対して、それは成り立つ。 0.79
ϕ(−→k ,−→d , n) ≥ φ(−→k ,−→d , n) ≥ 0.98
. kv(ε) − f (z(ε))k2 =vuut 1 . kv(ε) − f (z(ε))k2 =vuut 1 0.90
n + 1 nXt=0 n + 1 nXt=0 0.72
(vt(ε) − f (zt(ε)))2 ≤ Cδ, (vt(ε) − f(zt(ε)))2 ≤ Cδ, 0.89
for some universal constant C > 0. ある普遍定数 C > 0 に対して。 0.80
This implies that the lower bound on ϕ(−→k ,−→d , n) can be directly translated to an upper bound on the fractional ℓ2 covering numbers. これは、φ(−→k ,−→d , n) 上の下界は、分数 l2 被覆数上の上界に直接変換できることを意味する。 0.63
Applying Lemma 28 with the parameter p = d1/n, using d1 = fat2(F) ≥ fat2i(F) = di for all d1 = fat2(F) ≥ fat2i(F) = di を用いて、パラメータ p = d1/n を Lemma 28 に適用する 0.86
i ≥ 1 and using the inequality(cid:0)n ϕ(−→k ,−→d , n) ≥ (1 − i ≥ 1 であり、不等式(cid:0)n φ(−→k ,−→d ,n) ≥ (1 −) を用いる。 0.79
k(cid:1) ≥ (n/k)k, we derive that di(cid:19)di 4i+1n(cid:19)di(cid:18) ki k(cid:1) ≥ (n/k)k, di(cid:19)di 4i+1n(cid:19)di(cid:18) ki 0.81
log nYi=1(cid:18) d1 log nYi=1(cid:18) d1 0.69
)2n d1 n ≥ ce−2d1 )2n d1 n ≥ ce−2d1 0.76
log nYi=1(cid:18) δ log nYi=1(cid:18) δ 0.75
4 · 32i(cid:19)di 4 · 32i(cid:19)di 0.86
, as required. (cid:4) , 必要に応じて (cid:4) 0.79
Using Proposition 26, we can bound the fractional covering number of a real valued function 命題26を用いて実値関数の分数被覆数を有界にすることができる 0.81
class, with respect to its fat-shattering dimension. 脂肪の粉砕の次元に関してクラス、。 0.59
Proof of Proposition 16. 原題: Proposition 16。 0.62
We apply Lemma 25 and replicate the proof of Theorem 13 found in Appendix B. We apply Lemma 25 and replicate the proof of Theorem 13 found in Appendix B。 0.78
With the notation from that section, we note that for any z by the results of that proof, そのセクションの表記で、我々は、その証明の結果による任意のzのために、注意してください。 0.57
, z(cid:19) N′(F, δ, z) ≤ N′(cid:18) 1 α⌊F⌋α(cid:19) = fat2α (⌊F⌋α) ≤ fatα(F) fat2(cid:18) 1 , z(cid:19) N′(F, δ, z) ≤ N′(cid:18) 1 α = F2α(cid:19) = fat2α ≤ Fatα(F) fat2(cid:18) 1 0.84
α⌊F⌋α, δ α − 通称α。 δ α − 0.67
1 2 (122) (123) 1 2 (122) (123) 0.85
27 27 0.85
英語(論文から抽出)日本語訳スコア
Letting α = 2 3 δ and plugging into the result of Proposition 26 gives us α = 2 とする 3 δ と Proposition 26 の結果へのプラグングは私たちに与えます。 0.79
N′(F, δ, z) ≤ N′(cid:18) 1 δYi=1 N′(F, δ, z) ≤ N′(cid:18) 1 δYi=1 0.82
log c ≤ α⌊F⌋α, 1, z(cid:19) ≤ ログC ≤ α,f,α, 1, z(cid:19) ≤ 0.74
C fat2icδ(F) C fat2icδ(F) 0.78
log c δYi=1 C ログC δYi=1 C 0.63
α − 1 δ 2!fat2i( 1 α − 1 δ 2!fat2i(1) 0.80
α⌊F⌋α) (124) 通称α)。 (124) 0.67
(125) (cid:4) (125) (cid:4) 0.82
as desired. Proof of Theorem 15. 好きなように Theorem 15の証明。 0.64
We start by bounded in plog N′(F, δ) for a single value of δ. まず、 plog N′(F, δ) で δ の単一の値の境界から始める。 0.75
Taking a logarithm in (32), one obtains テイキング logarithm (複数形 logarithms または logarithms) 0.58
Using the subadditivity of the square root, one obtains: 平方根の部分加法により、次の値が得られる。 0.54
Each term corresponding to i can be bounded by i に対応する各用語は、境界づけられる 0.74
1 2i−1cδZ 2icδ 1 2i−1cδZ 2icδ 0.59
Hence, we derive that √C それゆえ私たちは ○C 0.61
i · fat2icδ(F). i · fat2icδ(F)。 0.77
log N′(F, δ) ≤ C log N′(F, δ) ≤ C 0.94
plog N′(F, δ) ≤ x=2i−1cδpifatx(F) ≤ 2Z 2icδ plog N′(F, δ) ≤ x=2i−1cδpifatx(F) ≤ 2Z 2icδ 0.67
log(1/δ)+C′Xi=1 log(1/δ)+C′Xi=1 pi · fat2icδ(F). log(1/δ)+C′Xi=1 log(1/δ)+C′Xi=1 pi · fat2icδ(F)。 0.59
≤ CZ 2icδ x=cδplog(Cx/δ)fatx(F) plog N′(F, δ) ≤ CZ 1 x=cδplog(x/δ)fatx(F) Z 1 b plog N′(F, δ)dδ ≤ CZ 1 δ=bZ 1 = CZ 1 x=cbpfatx(F)Z x/c ≤ C′Z 1 x=cbpfatx(F)dx. ≤ CZ 2icδ x=cδplog(Cx/δ)fatx(F) ≤ CZ 1 x=cδplog(x/δ)fatx(F) Z 1 b plog N′(F, δ)dδ ≤ CZ 1 δ=bZ 1 = CZ 1 x=cbpfatx(F)Z x/c ≤ C′Z 1 x=cbpfatx(F)dx。 0.90
x=2i−1cδpifatx(F) x=2i−1cδpifatx(F) 0.45
x x x dxdδ x x x dxdδ 0.83
δ=b plog(Cx/δ) δ=bplog(cx/δ) 0.71
x Next, we combine the above bound by taking an integral, and switching the order of integration: x 次に、積分を取り、統合の順序を切り替えることで、上記の境界を結合します。 0.77
x=2i−1cδplog(Cx/δ)fatx(F) x=2i−1cδplog(Cx/δ)fatx(F) 0.56
x (126) (127) x (126) (127) 0.85
. (128) dδdx . (128) dδdx 0.76
(cid:4) D Miscellaneous Proofs (cid:4) d 各種の証明 0.70
Proof of Proposition 5. By scaling, it suffices to consider L = 1. 命題5の証明。 スケーリングによって、L = 1を考えるのに十分である。 0.58
Let eµ = ℓ#µ be the pushforward eμ = l#μ をプッシュフォワードとする 0.81
of µ by ℓ. l による μ の値です 0.61
Because ℓ is Lipschitz, we note that ℓ ◦ Bδ(f (z), ε) ⊆ Bδ(ℓ ◦ f (z), ε). l は Lipschitz なので、l は Bδ(f(z), ε) は Bδ(l は f(z), ε) であることに注意する。 0.83
By monotonicity of measures, we then have 測定の単調性によって、私たちはそれを持つ 0.47
slog 1 eµ(Bδ(ℓ ◦ f (z), ε)) ≤slog ログ 1 eμ(Bδ(l ) f (z, ε)) ≤slog 0.81
1 eµ(ℓ(Bδ(f (z), ε)) 1 eμ(l(Bδ(f(z), ε)) 0.88
=slog where the equality follows from the definition of the push-forward. slog ここで、等価性はプッシュフォワードの定義に従います。 0.63
The result follows by taking an infimum over measures µ. 結果は測度 μ 上のインフィムを取ることによって従う。 0.64
(cid:4) 1 µ(Bδ(f (z), ε)) (cid:4) 1 μ(Bδ(f(z), ε)) 0.83
(129) 28 (129) 28 0.85
英語(論文から抽出)日本語訳スコア
Proof of Lemma 7. Lemma 7の証明。 0.69
Let v1, . . を v1 とする。 . 0.76
. , vN be a δ-cover and let µ be a a measure that takes vj with probability 1 N . . , vN をδ被覆とし、 μ を確率 1 N で vj を取る測度とする。 0.81
Then by definition of the covering numbers, µ is a δ-fractional cover of size N . 被覆数の定義により、μ は大きさ n の δ-フラクタル被覆である。 0.74
The result follows. 結果は次の通りです。 0.61
(cid:4) Proof of Lemma 8. (cid:4) Lemma 8の証明。 0.73
The upper bound follows from Lemma 7. 上の境界はLemma 7から続く。 0.56
Fix a z. As we are in the offline world, we have packing-covering duality (see, for example, (van Handel, 2014, Lemma 5.12)). z を固定する。 私たちはオフラインの世界にいるので、パッキングカバーの二重性があります(例:van Handel, 2014 Lemma 5.12)。 0.72
Thus, it suffices to show that D (F, 2δ) ≤ N′(F, δ). したがって、D (F, 2δ) ≤ N′(F, δ) であることは十分である。 0.83
To see this, consider a set of points x1, . これを見るには、点 x1 の集合を考える。 0.67
. . , xN that are 2δ-packed and consider the balls Bδ(xi). . . 2δ-packed の xN であり、球 Bδ(xi) を考える。 0.83
By definition of a fractional cover, if µ is such, then µ(Bδ(xi)) ≥ 1 γ for all i. by the fact that the xi are packed, the sets Bδ(xi) are pairwise disjoint and so by additivity of the measure and the fact that it is a probability measure, 分数被覆の定義により、μ がそのような場合、すべての i に対して μ(Bδ(xi)) ≥ 1 γ となる。
訳抜け防止モード: 分数被覆の定義により、μ がそのような場合、すべての i に対して μ(bδ(xi ) ) ≥ 1 γ となる。 xiは満員です。 集合 bδ(xi ) はその測度の加法性によって一対的に不連結である そしてそれが確率測度であるという事実 ,
0.86
the result follows. 1 ≥ µ [1≤i≤N 結果は次の通りです 1 ≥ μ である。 0.79
Bδ(xi) ≥ N µ (Bδ(x1)) ≥ bδ(xi)> ≥ n μ (bδ(x1)) ≥ 0.96
N γ (130) (cid:4) N γ (130) (cid:4) 0.83
Proof of Proposition 9. Proposition 9の証明。 0.72
A majorizing measure is multi-scale, while a fractional cover is single-scale; to turn the latter into the former, we consider the following mixture distribution. 主要な尺度はマルチスケールであるが、分数被覆はシングルスケールであり、後者を前者に変換するため、以下の混合分布を考える。 0.71
If the integral of the fractional cover is infinite then there is nothing to prove; thus, assume that the this quantity is finite. 分数被覆の積分が無限であれば、証明すべきことは何もない。したがって、この量は有限であると仮定する。 0.75
Suppose α = 0. α = 0 とする。 0.90
Let δj be the smallest δ such that N′(V, δ) ≤ 22j and let µj be an optimal δj-fractional cover. δj を N′(V, δ) ≤ 22j の最小 δ とし、μj を最適 δj-フラクショナル被覆とする。 0.84
Let j−2µj はじめに j−2μj 0.35
(131) µ = cXj (131) μ = cXj 0.85
Note that the above sum is over all j sufficiently large by the assumption that the integral is finite and we let c be a normalizing constant. 上記の和は、積分が有限であり、c を正規化定数とする仮定により、十分大きいすべての j 上である。 0.70
Now, we have for any v, ε, さて、任意の v, ε に対して成り立つ。 0.59
Iµ(v, ε) =Z 1 Iμ(v, ε) = Z 1 0.94
0 slog 1 µ(Bδ(v, ε)) 0 slog 1 μ(Bδ(v, ε)) 0.88
dδ ≤Xj Z δj−1 dδ ≤Xj Z δj−1 0.59
δj slog 1 µ(Bδ(v, ε)) δj slog 1 μ(Bδ(v, ε)) 0.89
dδ (132) By construction, for any δ ≥ δj, dδ (132) 構成により、任意の δ ≥ δj に対して 0.78
µ(Bδ(v, ε)) ≥ µ(Bδj (v, ε)) ≥ μ(Bδ(v, ε)) ≥ μ(Bδj(v, ε)) ≥ 0.97
1 j2 µj(Bδj (v, ε)) ≥ 1 j2 μj(Bδj (v, ε)) ≥ 0.90
1 j222j ≥ 1 1 j222j ≥ 1 0.82
22×2j Thus we have 22×2j だから私たちは 0.59
Thus, δj slog Z δj−1 よって、 δj slog Z δj−1 0.67
1 µ(Bδ(v, ε)) 1 μ(Bδ(v, ε)) 0.89
dδ ≤ cδj−12 dδ ≤ cδj−12 0.52
j 2 ≤ c′δj−12 j 2 ≤ c′δj−12 0.69
j−1 2 Iµ(v, ε) ≤Xj j−12 Iμ(v, ε) ≤Xj 0.90
c′δj−12 j−1 c′δj−12 j−1 0.46
2 ≤ CZ 1 0 plog N′(V, δ)dδ 2 ≤ CZ 1。 0 plog N′(V, δ)dδ 0.95
(133) (134) (133) (134) 0.85
(135) If α > 0, simply cut off j such that δj ≥ α. (135) α > 0 であれば、単に δj ≥ α となる j を切断する。 0.84
The same technique applies, concluding the proof. 同じ手法が適用され、証明が確定する。 0.69
(cid:4) Proof of Corollary 11. (cid:4) 登録者11の証明。 0.68
By (Rakhlin et al. 略称は(rakhlin et al)。 0.53
, 2015, Lemma 4), we have for any x > 0 , 2015, Lemma 4) は任意の x > 0 に対して成立する。 0.83
f∈F(cid:12)(cid:12)(ci d:12)(cid:12)(cid:12 ) Pε sup fvcf(cid:12)(cid:12) (cid:12)(cid:12)pε sup 0.71
1 n nXt=1 f (Zt) − E[f (Zt)|At](cid:12)(cid:12)(cid :12)(cid:12)(cid:12) ≥ x! 1n nXt=1 f (Zt) − E[f (Zt)|At](cid:12)(cid:12)(cid :12)(cid:12)(cid:12) (cid:12) ≥ x! 0.71
≤ 4Pε (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) ≤ 4Pε (cid:12)(cid:12)(cid :12)(cid:12)(cid:12) 0.71
1 n nXt=1 εtf (zt(ε))(cid:12)(cid:12)(c id:12)(cid:12)(cid:1 2) 1n nXt=1 εtf(zt(ε))(cid:12)(cid:12)(c id:12)(cid:12)(cid:1 2) 0.71
! (136) (cid:4) ! (136) (cid:4) 0.83
By Theorem 10, we can control the right hand side of (136) and conclude the proof. Theorem 10によって、私達は(136)の右側を制御し、証明を締めることができます。 0.81
29 29 0.85
英語(論文から抽出)日本語訳スコア
Proof of Corollary 18. The upper bound follows immediately from setting α = 0 in the second statement of Theorem 10 and then bounding the resulting integral by Proposition 15. 18巻の証明。 上界は定理10の第2のステートメントで α = 0 とするとすぐに続き、結果の積分を命題15で束縛する。 0.59
For the lower bound, we first need to show that if F is (c, p)-bounded, then 下界に対しては、まず F が (c, p) 有界であれば、それを示す必要がある。 0.74
To do this, we note that the function δ 7→ fatδ(F) is monotone non-increasing. このために、関数 δ 7→ fatδ(f) が単調でないことに注意する。 0.77
Thus we have Z 1 0 pfatδ(F)dδ = だから私たちは Z 1 0 pfatδ(F)dδ = 0.84
∞Xj=1 2−jpfat2−j (F) ∞Xj=1 2−jpfat2−j (F) 0.53
2−1 p 2√c 1 − 2 2−1 p 2c 1 − 2 0.76
Z 1 0 pfatδ(F)dδ ≤ ∞Xj=1Z 2−j+1 2−j pfatδ(F)dδ ≤ ∞Xj=1 2−j√c2jp ≤ Z 1 0 pfatδ(F)dδ ≤ ∞Xj=1Z 2−j+1 2−j pfatδ(F)dδ ≤ ∞Xj=1 2−j\c2jp ≤ 0.57
2√c 1 − 2 2−1 2c 1 − 2 2−1 0.71
p ≤ Now, noting that fat1(F) ≥ 1, we see that the above implies that for any α < 1, p ≤ さて、fat1(F) ≥ 1 とすると、上記のことは任意の α < 1 に対して意味があることが分かる。 0.81
Z 1 0 pfatδ(F)dδ ≤ Z 1 0 pfatδ(F)dδ ≤ 0.98
2√c 1 − 2 p 2c 1 − 2 p 0.84
2−1 ≤ 2√c 1 − 2 2−1 ≤ 2c 1 − 2 0.77
p 2−1 sup δ>α p 2−1 sup δ>α 0.76
δpfatδ(F) Note that the definition of a (c, p)-bounded class ensures that the right hand side of Proposition 15 tends to a finite limit as b ↓ 0; call this finite limit A. δpfatδ(F) a (c, p)-有界クラスの定義は命題15の右辺が有限極限を b ~ 0 とすることを保証し、この有限極限を a と呼ぶことに注意する。 0.79
To get the lower bound, we apply (Rakhlin et al. 下限を得るには、 (rakhlin et al.) を適用する。 0.71
, 2015, Lemma 2), which says that 2015年、lemma 2) です。 0.46
δr min(fatδ(F), n) δr min(fatδ(F), n) 0.93
32 sup δ>0 32 sup δ>0。 0.89
≤ √nRn(F) (141) ≤ \nRn(F) (141) 0.87
and, moreover, that if δ > 2Rn(F), then fatδ(F) < n. Thus, using the upper bound on Rn(F) just proven, we see that さらに、δ > 2rn(f) であればfatδ(f) < n となるので、rn(f) 上の上界を用いることが証明された。
訳抜け防止モード: さらに、δ > 2Rn(F ) の場合、fatδ(F) となる。 したがって、Rn(F)上の上界を使用することが証明されたばかりです。 ご覧の通り
0.86
√nRn(F) ≥ C′ ~nRn(F) ≥ C′ 0.83
sup δ>2Rn(F) sup δ>2Rn(F) 0.91
δpfatδ(F) ≥ C′ δpfatδ(F) ≥ C′ 1 − 2 δpfatδ(F) ≥ C′ δpfatδ(F) ≥ C′ 1 − 2 0.86
2√c δ> c′√n R 1 2−1 2c δ> c′\n R 1 2−1 0.62
p sup 0 √fatδ(F)dδ p sup 0 \fatδ(F)dδ 0.84
Z 1 0 pfatδ(F)dδ Z 1 0 pfatδ(F)dδ 0.96
δpfatδ(F) The result follows. δpfatδ(F) 結果は次の通りです。 0.72
≥ C′ sup δ> c′ A√n ≥ C′ sup δ> c′ An 0.83
Proof of Corollary 19. Corollary 19の証明。 0.67
By scaling it suffices to consider the case L = 1. スケールすることで L = 1 の場合を考えるのに十分である。 0.64
By Theorem 10 we have Theorem 10 までには 0.77
(137) (138) (137) (138) 0.85
(139) (140) (139) (140) 0.85
(142) (143) (142) (143) 0.85
(cid:4) (144) (cid:4) (144) 0.82
It is immediate from the definition of the fractional covering number that N′(ℓ◦F, δ, z) ≤ N′(F, δ, z). これは、分数被覆数 N′(l*F, δ, z) ≤ N′(F, δ, z) の定義から直ぐである。 0.80
Applying Proposition 15 and Corollary 18 concludes the proof. 命題15と参列者18が証明を結論づける。 0.72
(cid:4) Rn(ℓ ◦ F) ≤ (cid:4) Rn(l ) F) ≤ 0.81
C √nZ 1 0 plog N′(ℓ ◦ F, δ, z)dδ C ^nZ1 0 plog N′(l, F, δ, z)dδ 0.84
30 30 0.85
                                                             ページの最初に戻る

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