カーネル法と深層学習の数理
鈴木大慈
東京大学大学院情報理工学系研究科数理情報学専攻
理研 AIP

2020 年 8 月 28 日/29 日@広島市立大学集中講義

1 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

2 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

3 / 68

機械学習の問題設定
教師あり学習データが入力とそれに対するラベルの組で与えられる．
新しい入力が来た時に対応するラベルを予測する問題．
問題の例：回帰，判別(, 3) ( , 5)

教師なし学習
データにラベルが付いていない．
問題の例：クラスタリング，音源分離，異常検知

半教師あり学習一部のデータにラベルが付いている．
強化学習
試行錯誤しながら自分でデータを集める．
4 / 68

機械学習の流れ
特徴抽出: 画像などの対象を何らかの方法でベクトルに変換．(分野ごとのノウハウ)
一度特徴ベクトルに変換してしまえばあとは統計の問題．
パラメータ推定特徴ベクトル
特徴抽出

x1
x2

分析

xd




予測モデルの構築 (θ: モデルのパラメータ)（教師有り学習） y = f (x; θ)※深層学習は特徴抽出の部分をネットワーク構造を工夫することで学習に組み込んでいる．
5 / 68損失関数を用いた定式化
教師あり/なし学習，いずれも損失関数の最小化として定式化できる．
データの構造を表すパラメータ θ ∈ Θ (Θ は仮説集合 (モデル))← 「学習」≈ θ の推定損失関数: パラメータ θ がデータ z = (x, y ) をどれだけよく説明しているか;ℓ(z, θ) (= ℓ(y , f (x; θ))).
汎化誤差 (期待誤差)：損失の期待値 → 汎化誤差最小化 ≈「学習」

min EZ [ℓ(Z , θ)].
θ∈Θ

訓練誤差（経験誤差）：観測されたデータで代用,

1∑ℓ(zi , θ).
θ∈Θ n
n

min

i=1

※ 訓練誤差と汎化誤差に差があることが機械学習における最適化の特徴．
6 / 68

モデルの例 (教師あり)回帰

z = (x, y ) ∈ Rd+1ℓ(z, θ) = (y − θ⊤ x)2(二乗誤差)
n
n
1∑
1∑
min
ℓ(zi , θ) = min(yi − θ⊤ xi )2θ∈Rd nθ∈Rd ni=1(最小二乗法)i=1

zi

7 / 68

教師あり学習の損失関数（回帰）のデータ z = (x, y ) における f = x ⊤ θ の損失.
二乗損失:ℓ(y , f ) = 12 (y − f )2 .

τ -分位点損失:ℓ(y , f ) = (1 − τ ) max{f − y , 0} + τ max{y − f , 0}.
ただし，τ ∈ (0, 1). 分位点回帰に用いられる．
ϵ-感度損失:ℓ(y , f ) = max{|y − f | − ϵ, 0},
ただし，ϵ > 0. サポートベクトル回帰に用いられる．
3

τ
Huber
ǫ

2

1

0
-3

-2

-1

0
f-y

1

2

3

8 / 68

教師あり学習の損失関数（判別）y ∈ {±1}
ロジスティック損失:
ヒンジ損失:
指数損失:
平滑化ヒンジ損失:ℓ(y , f ) = log((1 + exp(−yf ))/2).
ℓ(y , f ) = max{1 − yf , 0}.
ℓ(y , f ) = exp(−yf ).
0,(yf ≥ 1),
(yf < 0),(otherwise).

ℓ(y , f ) = 12 − yf ,1
2
2 (1 − yf ) ,

0-1

4

3

2

1

0
-3

-2

-1

0
yf

1

2

3

9 / 68

過学習
経験誤差最小化と汎化誤差最小化には大きなギャップがある．
単なる経験誤差最小化は「過学習」を引き起こす．

4
2

True
Overfitting

0

y

6

8

10

12

cubic spline fitting

5

10

15

20

Index

10 / 68

正則化法
普通のロス関数 (負の対数尤度) 最小化:

min
β

n
∑

ℓ(yi , β ⊤ xi ).

i=1

正則化付き損失関数最小化:

min
β

n
∑
i=1

ℓ(yi , β ⊤ xi ) + ψ(β) .
| {z }
正則化項

正則化項の例:
リッジ正則化 (ℓ2 -正則化): ψ(β) = λ∥β∥22ℓ1 -正則化: ψ(β) = λ∥β∥1
トレースノルム正則化: ψ(W ) = Tr[(W ⊤ W )1/2 ] (W ∈ RN×M : 行列)

11 / 68

正則化法
普通のロス関数 (負の対数尤度) 最小化:

min
β

n
∑

ℓ(yi , β ⊤ xi ).

i=1

正則化付き損失関数最小化:

min
β

n
∑
i=1

ℓ(yi , β ⊤ xi ) + ψ(β) .
| {z }
正則化項

正則化項の例:
リッジ正則化 (ℓ2 -正則化): ψ(β) = λ∥β∥22ℓ1 -正則化: ψ(β) = λ∥β∥1
トレースノルム正則化: ψ(W ) = Tr[(W ⊤ W )1/2 ] (W ∈ RN×M : 行列)
正則化項により分散が抑えられ，過学習が防がれる．
その分，バイアスが乗る．
→ 適切な正則化の強さ (λ) を選ぶ必要がある．
11 / 68

正則化の例： リッジ正則化と過学習
多項式回帰（15 次多項式）1∑{yi − (β1 xi + β2 xi2 + · · · + β15 xi15 )}2 + λ∥β∥22
n
n

min15

θ∈R

i=1

12 / 68

正則化の例：ℓ1 -正則化（スパース推定）β̂ = arg min
β∈Rp

∑
1∑
|βj |.
(yi − xi⊤ β)2 + λ
n
n

p

i=1

j=1

R. Tsibshirani (1996). Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc
B., Vol. 58, No. 1, pages 267–288.

13 / 68

スパース性の恩恵
yi = xi⊤ β ∗ + ϵi (i = 1, . . . , n)．β ∗ : 真のベクトル．
β̂ = arg min
β∈Rp

∑
1∑
(yi − xi⊤ β)2 + λ|βj |.
n
n

p

i=1

j=1

xi ∈ Rp (p 次元), d = ∥β ∗ ∥0 (真の非 0 要素の数) とする．

Theorem (Lasso の収束レート)
ある条件のもと，ある定数 C が存在して∥β̂ − β ∗ ∥22 ≤ C

dlog(p).
n※全体の次元 p はたかだか O(log(p)) でしか影響しない !
実質的次元 d が支配的．

(Lasso)d log(p)n≪p(最小二乗法)n
14 / 68

制限固有値条件 (Restricted eigenvalue condition)
A = n1 X ⊤ X とする．

Definition (制限固有値条件 (RE(k ′ , C )))ϕRE (k ′ , C ) = ϕRE (k ′ , C , A) :=inf

J⊆{1,...,n},v ∈Rp :|J|≤k ′ ,C ∥vJ ∥1 ≥∥vJ c ∥1v ⊤ Av∥vJ ∥22に対し，ϕRE > 0 が成り立つ．
ほぼスパースなベクトルに制限して定義した最小固有値．
k ′ = 2d で成り立っていればよい．
ランダムな X に対して高確率で成り立つことが示せる: Johnson
Lindenstrauss の補題 (Johnson et al., 1986, Dasgupta and Gupta, 1999, Rudelson andZhou, 2013)．
J
一次独立

相関が小さい15 / 68

正則化と最適化
モデルの制限による正則化

Early stopping による正則化

真の関数

訓練誤差最小化元
（過学習）

バイアス
推定量

Early stopping

バリアンス

初期値

モデル

バイアス-バリアンス分解ˆ∥f − f ∥L2 (PX ) ≤ ∥f o − fˇ∥L2 (PX ) + ∥fˇ − fˆ∥L2 (PX )
|
{z
} |
{z
} |
{z
}
o

Estimation error

Approximation error(bias)

Sample deviation(variance)

訓練誤差最小化元に達する前に止める (early stopping) ことで正則化が働く．
→ 深層学習，Boosting の常套手段．
16 / 68

Early stopping による過学習の回避

Hands-On Machine Learning with Scikit-Learn and TensorFlow by Aurlien Gron.
Chapter 4. Training Models.
https://www.oreilly.com/library/view/hands-on-machine-learning/9781491962282/ch04.html

17 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

18 / 68

（今からお話しする）学習理論 ≈

{
sup

f ∈F

経験過程の理論}n1∑
f (xi ) − E[f ]ni=1の評価が重要．

19 / 68

歴史: 経験過程の理論

1933

Glivenko, Cantelli

1933

Kolmogorov

1952

Donsker

1967
1968

DudleyVapnik, Chervonenkis

1996a

Talagrand

Glivenko-Catelli の定理(一様大数の法則)
Kolmogorov-Smirnov 検定(収束レート，漸近分布)
Donsker の定理(一様中心極限定理)
Dudley 積分
VC 次元(一様収束の必要十分条件)
Talagrand の不等式

20 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

21 / 68

問題設定
教師有り学習教師データ: Dn = {(x1 , y1 ), . . . , (xn , yn )} ∈ (X × Y)nロス関数: ℓ(·, ·) : Y × R → R+
仮説集合 (モデル): F

入力と出力の i.i.d. 系列
間違いへのペナルティ
X → R なる関数の集合

fˆ: 推定量. サンプル (xi , yi )ni=1 から構成される F の元.

抑えたい量 (汎化誤差):
E(X ,Y ) [ℓ(Y , fˆ(X ))] − inf E(X ,Y ) [ℓ(Y , f (X ))]f :可測関数| {z }
テストデータ

汎化誤差は収束する？
その速さは?
22 / 68

Bias-Variance の分解∑n
経験リスク: L̂(f ) = n1 i=1 ℓ(yi , f (xi )),期待リスク: L(f ) = E(X ,Y ) [ℓ(Y , f (X ))]汎化誤差 =L(fˆ) −inf

f :可測関数L(f )= L(fˆ) − inf L(f ) + inf L(f ) − inf L(f )
f ∈F
f ∈F
f :可測関数
{z
} |
|
{z
}
推定誤差

モデル誤差

簡単のため f ∗ ∈ F が存在して inf f ∈F L(f ) = L(f ∗ ) とする．

23 / 68

Bias-Variance の分解∑n
経験リスク: L̂(f ) = n1 i=1 ℓ(yi , f (xi )),期待リスク: L(f ) = E(X ,Y ) [ℓ(Y , f (X ))]汎化誤差 =L(fˆ) −inf

f :可測関数L(f )= L(fˆ) − inf L(f ) + inf L(f ) − inf L(f )
f ∈F
f ∈F
f :可測関数
{z
} |
|
{z
}
推定誤差

モデル誤差

簡単のため f ∗ ∈ F が存在して inf f ∈F L(f ) = L(f ∗ ) とする．

※モデル誤差については今回は触れない．
しかし，モデリングの問題は非常に重要．

Sieve 法, Cross validation, 情報量規準, モデル平均, ...
カーネル法におけるモデル誤差の取り扱い: interpolation space の理論 (Steinwart et al., 2009, Eberts and Steinwart, 2012, Bennett and Sharpley, 1988).
以降，モデル誤差は十分小さいとする．
23 / 68

経験誤差最小化
経験誤差最小化 (ERM):

fˆ = arg min L̂(f )f ∈F

正則化付き経験誤差最小化 (RERM):

fˆ = arg min L̂(f ) + ψ(f )
|{z}
f ∈F

正則化項

RERM に関する研究も非常に沢山ある (Steinwart and Christmann, 2008,
Mukherjee et al., 2002).
ERM の延長線上．

24 / 68

経験誤差最小化
経験誤差最小化 (ERM): ☆

fˆ = arg min L̂(f )f ∈F

正則化付き経験誤差最小化 (RERM):

fˆ = arg min L̂(f ) + ψ(f )
|{z}
f ∈F

正則化項

RERM に関する研究も非常に沢山ある (Steinwart and Christmann, 2008,
Mukherjee et al., 2002).
ERM の延長線上．

24 / 68

出発点
ほとんどのバウンドの導出は次の式から始まる:⇒L̂(fˆ) ≤ L̂(f ∗ )(∵ 経験誤差最小化)∗
L(fˆ) − L(f ) ≤ L(fˆ) − L̂(fˆ) + L̂(f ∗ ) − L(f ∗ )Reminder: L̂(f ) = n1∑ni=1 ℓ(yi , f (xi )), L(f ) = E(X ,Y ) [ℓ(Y , f (X ))]25 / 68

出発点
ほとんどのバウンドの導出は次の式から始まる:⇒L̂(fˆ) ≤ L̂(f ∗ )(∵ 経験誤差最小化)∗ˆˆ
L(f ) − L(f ) ≤ L(f ) − L̂(fˆ) + L̂(f ∗ ) − L(f ∗ )
|
{z
} |
{z
} |
{z
}
汎化誤差

Reminder: L̂(f ) = n1?

√
Op (1/ n) (後述)∑ni=1 ℓ(yi , f (xi )), L(f ) = E(X ,Y ) [ℓ(Y , f (X ))]25 / 68

出発点
ほとんどのバウンドの導出は次の式から始まる:⇒L̂(fˆ) ≤ L̂(f ∗ )(∵ 経験誤差最小化)∗ˆˆ
L(f ) − L(f ) ≤ L(f ) − L̂(fˆ) + L̂(f ∗ ) − L(f ∗ )
|
{z
} |
{z
} |
{z
}
汎化誤差

?

√
Op (1/ n) (後述)

安易な解析

{
L(fˆ) − L̂(fˆ)→0√= Op (1/ n)(∵ 大数の法則!!)(∵ 中心極限定理!!)

楽勝！
！
！

Reminder: L̂(f ) = n1∑ni=1 ℓ(yi , f (xi )), L(f ) = E(X ,Y ) [ℓ(Y , f (X ))]25 / 68

出発点
ほとんどのバウンドの導出は次の式から始まる:⇒L̂(fˆ) ≤ L̂(f ∗ )(∵ 経験誤差最小化)∗ˆˆ
L(f ) − L(f ) ≤ L(f ) − L̂(fˆ) + L̂(f ∗ ) − L(f ∗ )
|
{z
} |
{z
} |
{z
}
汎化誤差

?

√
Op (1/ n) (後述)

安易な解析

{
L(fˆ) − L̂(fˆ)→0√= Op (1/ n)(∵ 大数の法則!!)(∵ 中心極限定理!!)

楽勝！
！
！
ダメです

fˆ と教師データは独立ではない
Reminder: L̂(f ) = n1∑ni=1 ℓ(yi , f (xi )), L(f ) = E(X ,Y ) [ℓ(Y , f (X ))]25 / 68なにが問題か？

L(f)f*
L(f ) = E[ℓ(Y , f (X ))], b
L(f ) = n1f∑ni=1 ℓ(yi , f (xi ))26 / 68なにが問題か？

L(f)

^
L(f)

f*

f^

f

“たまたま” うまくいくやつがいる (過学習) かもしれない．
実際，F が複雑な場合収束しない例が
26 / 68なにが問題か？

L(f)一様なバウンド

^
L(f)

f^ f*

f

一様なバウンドによって「たまたまうまくいく」が (ほとんど) ないことを保証
それは自明ではない (経験過程の理論)
26 / 68

一様バウンド{}L(fˆ) − L̂(fˆ) ≤ sup L(f ) − L̂(f ) ≤ (?)
f ∈F一様にリスクを抑えることが重要

27 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

28 / 68

まずは有限から|F| < ∞

29 / 68

有用な不等式
Hoeﬀding の不等式
Zi (i = 1, . . . , n): 独立で (同一とは限らない) 期待値 0 の確率変数 s.t.
|Zi | ≤ mi
)
( ∑n
)
(
| i=1 Zi |t2√
P> t ≤ 2 exp − ∑nn2 i=1 mi2 /nBernstein の不等式
Zi (i = 1, . . . , n): 独立で (同一とは限らない) 期待値 0 の確率変数 s.t.
E[Zi2 ] = σi2 , |Zi | ≤ M
(
)
)
( ∑n
| i=1 Zi |t2√
> t ≤ 2 exp − 1 ∑n
Pn
2( n i=1 σi2 + √1n Mt)
分散の情報を利用
30 / 68

有用な不等式: 拡張版
Hoeﬀding の不等式 (sub-Gaussian tail)Zi (i = 1, . . . , n): 独立で (同一とは限らない) 期待値 0 の確率変数 s.t.
2 2E[e τ Zi ] ≤ e σi τ /2 (∀τ > 0)
( ∑n
)
(
)
| i=1 Zi |t2∑√
P> t ≤ 2 exp −nn2 i=1 σi2 /nBernstein の不等式
Zi (i = 1, . . . , n): 独立で (同一とは限らない) 期待値 0 の確率変数 s.t.
2 k−2
E[Zi2 ] = σi2 , E|Zi |k ≤ k!
(∀k ≥ 2)
2σ M
(
)
( ∑n
)
| i=1 Zi |t2√
P> t ≤ 2 exp − 1 ∑nn
2( n i=1 σi2 + √1n Mt)(ヒルベルト空間版もある)
31 / 68

有限集合の一様バウンド 1: Hoeﬀding の不等式版
これだけでも知っていると有用．(f ← ℓ(y , g (x)) − Eℓ(Y , g (X )) として考える)

F = {fm (m = 1, . . . , M)} 有限個の関数集合: どれも期待値 0 (E[fm (X )] = 0).
Hoeﬀding の不等式 (Zi = fm (Xi ) を代入)
( ∑n
)
(
)
2
| i=1 fm (Xi )|√P> t ≤ 2 exp − 2∥ftm ∥2n∞

一様バウンド
(
•P

max

1≤m≤M

[
•E

P

max

|

max

1≤m≤M

(
(導出)

|

1≤m≤M

|

∑n

√

> max ∥fm ∥∞ 2 log (2M/δ) ≤ δmn]√
i=1 fm (Xi )|√≤ C max ∥fm ∥∞ log(1 + M)mni=1 fm (Xi )|

n

)

∑n

∑n

√

√

i=1 fm (Xi )|

)
>t




(
)
{ ∑n
}
M
∑
| i=1 fm (Xi )|t2>t ≤2exp −√n
2∥fm ∥2∞
m=1
1≤m≤M

=P

∪

32 / 68

有限集合の一様バウンド 2: Bernstein の不等式版
F = {fm (m = 1, . . . , M)} 有限個の関数集合: どれも期待値 0 (E[fm (X )] = 0).
Bernstein の不等式
( ∑n
P

|

f (X )|
i=1
√m i
n

(
)
2
> t ≤ 2 exp − 2(∥f ∥2 +t√1 ∥f ∥
m L
2

n

)

m ∞ t)

一様バウンド
[
E

max

|

∑n

i=1 fm (Xi )|

]

√

n
√
1
≲ √ max ∥fm ∥∞ log(1 + M) + max ∥fm ∥L2 log(1 + M)mmn√
※ 一様バウンドはせいぜい log(M) オーダで増える．
1≤m≤M

33 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

34 / 68

有限から無限へ仮説集合の要素が無限個あったら？
連続濃度をもっていたら？

F = {x ⊤ β | β ∈ Rd , ∥β∥ ≤ 1}

F = {f ∈ H | ∥f ∥H ≤ 1}

6

4

2

0

-2

-4

-6
-5

-4

-3

-2

-1

0

1

2

3

4

5

35 / 68

基本的なアイディア

有限個の元で代表させるF

36 / 68

Rademacher 複雑さ
ϵ1 , ϵ2 , . . . , ϵn : Rademacher 変数, i.e., P(ϵi = 1) = P(ϵi = −1) = 12 .
Rademacher 複雑さ[
R(F) := E{ϵi },{xi }1 ∑sup
ϵi f (xi )f ∈F n
n

]

i=1

対称化:

[

(期待値)

1 ∑
(f (xi ) − E[f ])E supf ∈F nn]≤ 2R(F).

i=1

もし ∥f ∥∞ ≤ 1 (∀f ∈ F ) なら

(
(裾確率)

P

1 ∑
sup
(f (xi ) − E[f ]) ≥ 2R(F) +f ∈F n
n

i=1

√

t
2n

)
≤ e −t .

Rademacher 複雑さを抑えれば一様バウンドが得られる！
37 / 68

Rademacher 複雑さの各種性質
Contraction inequality: もし ψ が Lipschitz 連続なら, i.e.,|ψ(f ) − ψ(f ′ )| ≤ B|f − f ′ |,R({ψ(f ) | f ∈ F}) ≤ 2BR(F).
凸包: conv(F) を F の元の凸結合全体からなる集合とする.

R(conv(F)) = R(F)38 / 68

Rademacher 複雑さの各種性質
Contraction inequality: もし ψ が Lipschitz 連続なら, i.e.,|ψ(f ) − ψ(f ′ )| ≤ B|f − f ′ |,R({ψ(f ) | f ∈ F}) ≤ 2BR(F).
凸包: conv(F) を F の元の凸結合全体からなる集合とする.

R(conv(F)) = R(F)
特に最初の性質が有り難い．

|ℓ(y , f ) − ℓ(y , f ′ )| ≤ |f − f ′ | なら，[]
E sup |L̂(f ) − L(f )| ≤ 2R(ℓ(F)) ≤ 2R(F),f ∈F

ただし，ℓ(F) = {ℓ(·, f (·)) | f ∈ F}.
よって F の Rademacher complexity を抑えれば十分！
Lipschitz 連続性はヒンジロス, ロジスティックロスなどで成り立つ．さらに y とF が有界なら二乗ロスなどでも成り立つ．
Reminder: L̂(f ) = n1∑ni=1 ℓ(yi , f (xi )), L(f ) = E(X ,Y ) [ℓ(Y , f (X ))]38 / 68

カバリングナンバー
Rademacher complexity を抑える方法．
カバリングナンバー: 仮説集合 F の複雑さ・容量．
F

ϵ-カバリングナンバー
N(F, ϵ, d)
ノルム d で定まる半径 ϵ のボールで F を覆うために必要な最小のボールの数．
有限個の元で F を近似するのに最低限必要な個数．

Theorem (Dudley 積分)∥f ∥2n := n1∑n2i=1 f (xi ) とすると，{R(F) ≤ C inf

α>01
α + √ EDn
n

[∫ ∞

√
log(N(F, ϵ, ∥ · ∥n ))dϵ

]}
.

α

(Boucheron et al. (2013) の Lemma 11.4 や Wainwright (2019) の Theorem 5.22
を参照)
39 / 68Dudley 積分のイメージ
C
R(F) ≤ √ EDn
n

[∫ ∞

√

]
log(N(F, ϵ, ∥ · ∥n ))dϵ .

0

有限個の元で F を近似する．
その解像度を細かくしていって，似ている元をまとめ上げてゆくイメー
ジ．
チェイニングという．

40 / 68これまでのまとめ⇒L̂(fˆ) ≤ L̂(f ∗ )(∵ 経験誤差最小化)
L(fˆ) − L(f ∗ ) ≤ L(fˆ) − L̂(fˆ) + L̂(f ∗ ) − L(f ∗ )
|
{z
}
{z
}
|
これを抑えたい√Op (1/ n) (Hoeﬀding)ℓ が 1-Lipschitz (|ℓ(y , f ) − ℓ(y , f ′ )| ≤ |f − f ′ |) かつ ∥f ∥∞ ≤ 1 (∀f ∈ F ) のとき,
L(fˆ) − L̂(fˆ) ≤ sup (L(f ) − L̂(f ))f ∈F√t≤ R(ℓ(F)) +(with prob. 1 − e −t )n√t
≤ 2R(F) +(contraction ineq., Lipschitz 連続)
n
[∫ ∞
] √
√
t
2
log N(F, ϵ, ∥ · ∥n )dϵ +(Dudley 積分).
≤ √ EDnnn0※カバリングナンバーが小さいほどリスクは小さい→ Occam’s Razor
41 / 68例: 線形判別関数
6⊤F = {f (x) = sign(x β + c) | β ∈ R , c ∈ R}
d

N(F, ϵ, ∥ · ∥n ) ≤ C (d + 2)

( c )2(d+1)

4

2

0

-2

ϵ

-4

-6
-5

-4

-3

-2

-1

0

1

2

3

4

5

すると，0-1 ロス ℓ に対し

(

[∫ 1
])
√
1
√ EDn
log N(F, ϵ, ∥ · ∥n )dϵ
n
0
(
)
∫ 1 √
1
≤ Op √
C d log(1/ϵ) + log(d)dϵ
n
(√ )0
d
.
≤ Op
n

L(fˆ) − L̂(fˆ) ≤ Op

42 / 68

例: VC 次元
F は指示関数の集合: F = {1C | C ∈ C}.
C はある集合族 (例: 半空間の集合)
細分: F がある与えられた有限集合 Xn = {x1 , . . . , xn } を細分する⇔ 任意のラベル Yn = {y1 , . . . , yn } (yi ∈ {±1}) に対して Xn を F が正しく判別できる．
VC 次元 VF : F が細分できる集合が存在しない n の最小値.
N(F, ϵ, ∥ · ∥n ) ≤ KVF (4e)VF√⇒ 汎化誤差 = Op ( VF /n)( )2(VF −1)1ϵ

http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Qinbo_diameter/e_net.htm から拝借

VC 次元が有限であることが ERM の期待リスクが収束することの必要十分条件．
43 / 68例: カーネル法
F = {f ∈ H | ∥f ∥H ≤ 1}

カーネル関数 k
再生核ヒルベルト空間 H
k(x, x) ≤ 1 (∀x ∈ X ) を仮定, e.g., ガウスカー
ネル.
直接∑n Rademacher∑複雑さを評価してみる．
∑nni=1∑ϵni f (xi ) = ⟨ i=1 ϵi k(xi , ·), f ⟩H ≤ ∥ i=1 ϵi k(xi , ·)∥H ∥f ∥H≤ ∥ i=1 ϵi k(xi , ·)∥H を使う．

[ ∑n]∥ i=1 ϵi k(xi , ·)∥H
R(F) = E sup
≤E
n
n
f ∈F
√ [
]
∑n
 √∑n

E
ϵ
ϵ
k(x
,
x
)
i
j
i
j
i,j=1
i,j=1 ϵi ϵj k(xi , xj )≤= E(Jensen)nn√∑ni=1 k(xi , xi )
1
≤√
=
n
n
[

|

∑n

i=1 ϵi f (xi )|]44 / 68

例: ランダム行列の作用素ノルム
A = (aij ): p × q 行列で各 aij は独立な期待値 0 かつ |aij | ≤ 1 なる確率変数．
A の作用素ノルム ∥A∥ := max ∥Az∥ =max w ⊤ Az.
∥z∥≤1
z∈Rq

∥w ∥≤1,∥z∥≤1
w ∈Rp ,z∈Rq

F = {fw ,z (aij , (i, j)) = aij wi zj | w ∈ Rp , z ∈ Rq } ⇒ ∥A∥ = sup∑f ∈F i,jf (aij , (i, j))n = pq 個のサンプルがあるとみなす．
∑p,q
1
2
′ ′ 2
′ 2
′ 2
∥fw ,z − fw ′ ,z ′ ∥2n = pqi,j=1 |aij (wi zj − wi zj )| ≤ pq (∥w − w ∥ + ∥z − z ∥ ){√√≤ C ( pqϵ)−(p+q) , (ϵ ≤ 2/ pq),
∴ N(F, ϵ, ∥ · ∥n )= 1,(otherwise).
[E]√∫ √1pq √√1p+qC(p + q) log(C / pqϵ)dϵ ≤sup w ⊤ Az ≤ √pq w ,zpq 0
pq√
よって，A の作用素ノルムは Op ( p + q).
→ 低ランク行列推定, Robust PCA, ...
詳しくは Tao (2012), Davidson and Szarek (2001) を参照．
45 / 68

例: Lasso の収束レート
デザイン行列 X = (Xij ) ∈ Rn×p . p (次元) ≫ n (サンプル数).
真のベクトル β ∗ ∈ Rp : 非ゼロ要素の個数がたかだか d 個 (スパース).
モデル : Y = X β ∗ + ξ.

1β̂ ← arg min ∥X β − Y ∥22 + λn ∥β∥1 .
pn
β∈RTheorem (Lasso の収束レート (Bickel et al., 2009, Zhang, 2009))
デザイン行列が Restricted eigenvalue condition (Bickel et al., 2009) かつ
2 2
maxi,j |Xij | ≤ 1 を満たし，ノイズが E[e τ ξi ] ≤ e σ τ /2 (∀τ > 0) を満たすなら, 確率1−δで
d log(p/δ).
∥β̂ − β ∗ ∥22 ≤ C
n※次元が高くても，たかだか log(p) でしか効いてこない．実質的な次元 d が支
配的．
46 / 68

log(p) はどこからやってきたか？
有限個の一様バウンドからやってきた．

⇒

1
1∥X β̂ − Y ∥22 + λn ∥β̂∥1 ≤ ∥X β ∗ − Y ∥22 + λn ∥β ∗ ∥1nn
2
1
∥X (β̂ − β ∗ )∥22 + λn ∥β̂∥1 ≤ ∥X ⊤ ξ∥∞ ∥β̂ − β ∗ ∥1 + λn ∥β ∗ ∥1nn | {z }これ1 ⊤1∑∥X ξ∥∞ = max |Xij ξi |1≤j≤p nnni=147 / 68

log(p) はどこからやってきたか？
有限個の一様バウンドからやってきた．

⇒

1
1∥X β̂ − Y ∥22 + λn ∥β̂∥1 ≤ ∥X β ∗ − Y ∥22 + λn ∥β ∗ ∥1nn
2
1
∥X (β̂ − β ∗ )∥22 + λn ∥β̂∥1 ≤ ∥X ⊤ ξ∥∞ ∥β̂ − β ∗ ∥1 + λn ∥β ∗ ∥1nn | {z }これ1 ⊤1∑∥X ξ∥∞ = max |Xij ξi |1≤j≤p nnni=1

Hoeﬀding の不等式由来の一様バウンドにより, 確率 1 − δ で√n1∑
2 log(2p/δ)max |Xij ξi | ≤ σ.
1≤j≤p nni=147 / 68

Talagrand の concentration inequality

汎用性の高い不等式．

Theorem (Talagrand (1996b), Massart (2000), Bousquet (2002))∑nσ := supf ∈F E[f (X )2 ], Pn f := n1 i=1 f (xi ), Pf := E[f (X )] とする.
[
( [
)]
] √
t
t
P sup (Pn f − Pf ) ≥ C E sup (Pn f − Pf ) +σ+≤ e −t
n
n
f ∈F
f ∈F
Fast learning rate を示すのに有用．

48 / 68その他のトピック
Johnson-Lindenstrauss の補題 (Johnson and Lindenstrauss, 1984, Dasgupta
and Gupta, 1999)
n 個の点 {x1 , . . . , xn } ∈ Rd を k 次元空間へ射影する. k ≥ cδ log(n) なら, k次元へのランダムプロジェクション A ∈ Rk×d (ランダム行列) は(1 − δ)∥xi − xj ∥ ≤ ∥Axi − Axj ∥ ≤ (1 + δ)∥xi − xj ∥を高い確率で満たす．
→ restricted isometory (Baraniuk et al., 2008, Candès, 2008)

Gaussian concentration inequality, concentration inequality on productspace (Ledoux, 2001)1∑
ξi f (xi )f ∈F nnsup(xi : ガウス分布など)

i=1

Majorizing measure: ガウシアンプロセスにまつわる上界, 下界 (Talagrand,2000).
49 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

50 / 68

√Op (1/ n) オーダより速いレートは示せる？

51 / 68

ロス関数の強凸性を積極的に利用

L(f)一様なバウンドf*f^f

ロスの強凸性を使うと fˆ の存在範囲が制限される→よりきついバウンド
52 / 68

ロス関数の強凸性を積極的に利用

L(f)一様なバウンドff^
同じ論理を何度も適用させることによって fˆ のリスクが小さいことを示す．
fˆ が f ∗ に近いことを利用→ “局所”Rademacher 複雑さ
52 / 68

局所 Rademacher 複雑さ
局所 Rademacher 複雑さ: Rδ (F) := R({f ∈ F | E[(f − f ∗ )2 ] ≤ δ}).
次の条件を仮定してみる.

F は 1 で上から抑えられている: ∥f ∥∞ ≤ 1 (∀f ∈ F ).
ℓ は Lipschitz 連続かつ強凸:
E[ℓ(Y , f (X ))] − E[ℓ(Y , f ∗ (X ))] ≥ BE[(f − f ∗ )2 ] (∀f ∈ F ).

Theorem (Fast learning rate (Bartlett et al., 2005))δ ∗ = inf{δ | δ ≥ Rδ (F)} とすると，確率 1 − e −t で(t)L(fˆ) − L(f ∗ ) ≤ C δ ∗ +.
n±δ ∗ ≤ R(F) は常に成り立つ (右図参照).
これを Fast learning rate と言う．

R± (F )±*±
53 / 68

Fast learning rate の例
log N(F, ϵ, ∥ · ∥n ) ≤ C ϵ−2ρ のとき，(Rδ (F) ≤ C

1−ρ

1
δ 2
√ ∨ n− 1+ρ
n),が示され，δ ∗ の定義から確率 1 − e −t で次が成り立つ:(
1t)
L(fˆ) − L(f ∗ ) ≤ C n− 1+ρ +.
n√※ 1/ n よりタイト！
参考文献
局所 Rademacher 複雑さの一般論: Bartlett et al. (2005), Koltchinskii (2006)
判別問題, Tsybakov の条件: Tsybakov (2004), Bartlett et al. (2006)
カーネル法における fast learning rate: Steinwart and Christmann (2008)

Peeling device: van de Geer (2000)
54 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

55 / 68

最適性ある学習方法が「最適」とは？
どの学習方法もデータの分布に応じて得意不得意がある．
「この場合はうまくいくがこの場合はうまくいかない」

主な最適性の規準
許容性
常に性能を改善させる方法が他にない．

minimax 最適性
一番不得意な場面でのリスクが最小．

56 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

57 / 68

許容性
分布のモデル: {Pθ |θ ∈ Θ}Pθ における推定量 fˇ のリスクの期待値:

L̄θ (fˇ) := EDn ∼Pθ [E(X ,Y )∼Pθ [ℓ(Y , fˇ(X ))]]

Definition (許容性)fˆ が許容的 (admissible)⇔ L̄θ (fˇ) ≤ L̄θ (fˆ) (∀θ ∈ Θ) かつ, ある θ′ ∈ Θ で L̄θ′ (fˇ) < L̄θ′ (fˆ) なる推定量 fˇ が存在しない．
θ¹µ (f^)L¹µ (f·)Lθ¹µ (f^)
L

58 / 68例
簡単のためサンプル Dn = {(x1 , . . . , xn )} ∼ Pθn から Pθ (θ ∈ Θ) を推定する問題
を考える．
一点賭け: ある θ0 を常に用いる．その θ0 に対する当てはまりは最良だが他の θ には悪い．
ベイズ推定量: 事前分布 π(θ), リスク L(θ0 , P̂)∫P̂ = arg min EDn ∼Pθ0 [L(θ0 , P̂)]π(θ0 )dθ0 .
P̂:推定量∫二乗リスク L(θ, θ̂) = ∥θ − θ̂∥2 : θ̂ = θπ(θ|Dn )dθ (事後平均)∫
KL-リスク L(θ, P̂) = KL(Pθ ||P̂): P̂ = P(·|θ)π(θ|Dn )dθ (ベイズ予測分布)

ベイズ推定量の定義より，常にリスク L(θ, P̂) を改善する推定量は存在しない．

59 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

60 / 68

minimax 最適性
Definition (minimax 最適性)fˆ が minimax 最適⇔ max L̄θ (fˆ) = min max L̄θ (fˇ)．
θ∈Θ

fˇ:推定量 θ∈Θ

学習理論では定数倍を許すことが多い: ∃C で

max L̄θ (fˆ) ≤ C min max L̄θ (fˇ)
fˇ:推定量 θ∈Θ

θ∈Θ

(∀n).

そういう意味で「minimax レートを達成する」と言ったりする．
θ¹µ (f^)
L

61 / 68

minimax レートを求める方法
Introduction to nonparametric estimation (Tsybakov, 2008) に詳しい記述.
F を有限個の元で代表させ，そのうち一つ最良なものを選ぶ問題を考える．
(もとの問題より簡単→リスクの下限を与える){f1 , . . . , fMn } ⊆ F

εn fj

F

個数 Mn と誤差 εn のトレードオフ: Mn が小さい方が最適な元を選ぶのが簡単になるが誤差 εn が大きくなる.

cf. Fano の不等式, Assouad の補題.
62 / 68

ノイズがガウスのノンパラメトリック回帰 minimax
レート
Yang and Barron (1999) の情報理論的方法(Raskutti et al. (2012b) でより整理された形を利用).
εn > 0: 任意
log(N) = log(N(F, εn , ∥ · ∥L2 (PX ) ))
に対して，
2

ε
inf sup EDn [∥fˆ − f ∗ ∥2L2 (PX ) ] ≥ n
2fˆ f ∗ ∈F⇒ ϵ2n ≃()
log(N) + 2σn 2 ε2n + log(2)1−.
8 log(N)log(N)となるように ϵn を選べば，
nminimax レート ≳ ϵ2n .

63 / 68

スパース推定の minimax レート

Theorem (Raskutti and Wainwright (2011))
ある条件のもと，確率 1/2 以上で，

min

max

β̂:推定量 β ∗ :d-スパース∥β̂ − β ∗ ∥2 ≥ C

d log(p/d).
nLasso は minimax レートを達成する ( d log(d)の項を除いて)．
n

この結果を Multiple Kernel Learning に拡張した結果: Raskutti et al. (2012a),
Suzuki and Sugiyama (2012).

64 / 68

Outline1

機械学習概要2

学習理論概要3

一様バウンド
基本的な不等式
Rademacher 複雑さと Dudley 積分
局所 Rademacher 複雑さ

4

最適性
許容性
minimax 最適性

5

ベイズの学習理論

65 / 68

ベイズの学習理論
ノンパラベイズの統計的性質
教科書: Ghosh and Ramamoorthi (2003), Bayesian Nonparametrics.
Springer, 2003.
収束レート
一般論: Ghosal et al. (2000)
Dirichlet mixture: Ghosal and van der Vaart (2007)
Gaussian process: van der Vaart and van Zanten (2008a,b, 2011).

66 / 68

ベイズの学習理論
ノンパラベイズの統計的性質
教科書: Ghosh and Ramamoorthi (2003), Bayesian Nonparametrics.
Springer, 2003.
収束レート
一般論: Ghosal et al. (2000)
Dirichlet mixture: Ghosal and van der Vaart (2007)
Gaussian process: van der Vaart and van Zanten (2008a,b, 2011).

PAC-Bayes

L(fˆπ ) ≤ inf ρ{∫[L(f )ρ(df ) + 2

2

KL(ρ||π)+log ϵ
λC 2
+
n
λ

]}
(Catoni, 2007)

元論文: McAllester (1998, 1999)
オラクル不等式: Catoni (2004, 2007)
スパース推定への応用: Dalalyan and Tsybakov (2008), Alquier and Lounici(2011), Suzuki (2012)
66 / 68

スパース推定文献情報
R の glmnet, LiblineaR およぼ，python の scikit-learn.
SPAMS: 最適化ソルバー, C++で実装．matlab, R, python インターフェイスが付いている．
http://spams-devel.gforge.inria.fr/
冨岡亮太著『スパース性に基づく機械学習』，講談社．
鈴木大慈著『確率的最適化』，講談社．
Hastie, Tibshirani, Friedman: The Elements of Statistical Learning.
Hastie, Tibshirani, Wainwright: Statistical Learning with Sparsity: The Lassoand Generalizations.

67 / 68

まとめ
一様バウンドが重要

{
sup

f ∈F

}
n
1∑
ℓ(yi , f (xi )) − E[ℓ(Y , f (X ))]ni=1

Rademacher 複雑さ
カバリングナンバー
仮説集合が単純であればあるほど，速い収束．

L(f)一様なバウンド

最適性規準

^
L(f)

許容性

minimax 最適性f^ f*f
68 / 68

P. Alquier and K. Lounici. PAC-Bayesian bounds for sparse regression estimation
with exponential weights. Electronic Journal of Statistics, 5:127–145, 2011.
R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin. A simple proof of therestricted isometry property for random matrices. Constructive Approximation,
28(3):253–263, 2008.
P. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. The
Annals of Statistics, 33:1487–1537, 2005.
P. Bartlett, M. Jordan, and D. McAuliﬀe. Convexity, classification, and riskbounds. Journal of the American Statistical Association, 101:138–156, 2006.
C. Bennett and R. Sharpley. Interpolation of Operators. Academic Press, Boston,
1988.
P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of Lasso and
Dantzig selector. The Annals of Statistics, 37(4):1705–1732, 2009.
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A
Nonasymptotic Theory of Independence. OUP Oxford, 2013. ISBN
9780199535255. URL
https://books.google.co.jp/books?id=koNqWRluhP0C.
O. Bousquet. A Bennett concentration inequality and its application to supremaof empirical process. C. R. Acad. Sci. Paris Ser. I Math., 334:495–500, 2002.
68 / 68

E. Candès. The restricted isometry property and its implications for compressedsensing. Compte Rendus de l’Academie des Sciences, Paris, Serie I, 346:
589–592, 2008.
F. P. Cantelli. Sulla determinazione empirica della leggi di probabilità. G. Inst.
Ital. Attuari, 4:221–424, 1933.
O. Catoni. Statistical Learning Theory and Stochastic Optimization. Lecture
Notes in Mathematics. Springer, 2004. Saint-Flour Summer School on
Probability Theory 2001.
O. Catoni. PAC-Bayesian Supervised Classification (The Thermodynamics ofStatistical Learning). Lecture Notes in Mathematics. IMS, 2007.
A. Dalalyan and A. B. Tsybakov. Aggregation by exponential weighting sharp
PAC-Bayesian bounds and sparsity. Machine Learning, 72:39–61, 2008.
S. Dasgupta and A. Gupta. An elementary proof of the johnson-lindenstrauss
lemma. Technical Report 99–006, U.C. Berkeley, 1999.
K. R. Davidson and S. J. Szarek. Local operator theory, random matrices andBanach spaces, volume 1, chapter 8, pages 317–366. North Holland, 2001.
M. Donsker. Justification and extension of doob’s heuristic approach to thekolmogorov-smirnov theorems. Annals of Mathematical Statistics, 23:277–281,
1952.
R. M. Dudley. The sizes of compact subsets of hilbert space and continuity ofgaussian processes. J. Functional Analysis, 1:290–330, 1967.
68 / 68

M. Eberts and I. Steinwart. Optimal learning rates for least squares svms using
gaussian kernels. In Advances in Neural Information Processing Systems 25,
2012.
S. Ghosal and A. W. van der Vaart. Posterior convergence rates of dirichlet
mixtures at smooth densities. The Annals of Statistics, 35(2):697–723, 2007.
S. Ghosal, J. K. Ghosh, and A. W. van der Vaart. Convergence rates of posterior
distributions. The Annals of Statistics, 28(2):500–531, 2000.
J. Ghosh and R. Ramamoorthi. Bayesian Nonparametrics. Springer, 2003.
V. I. Glivenko. Sulla determinazione empirica di probabilità. G. Inst. Ital. Attuari,
4:92–99, 1933.
W. B. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into ahilbert space. In Conference in Modern Analysis and Probability, volume 26,
pages 186–206, 1984.
W. B. Johnson, J. Lindenstrauss, and G. Schechtman. Extensions of lipschitz
maps into banach spaces. Israel Journal of Mathematics, 54(2):129–138, 1986.
A. Kolmogorov. Sulla determinazione empirica di una legge di distribuzione. G.
Inst. Ital. Attuari, 4:83–91, 1933.
V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk
minimization. The Annals of Statistics, 34:2593–2656, 2006.
M. Ledoux. The concentration of measure phenomenon. American MathematicalSociety, 2001.
68 / 68

P. Massart. About the constants in talagrand’s concentration inequalities for
empirical processes. The Annals of Probability, 28(2):863–884, 2000.
D. McAllester. Some PAC-Bayesian theorems. In the Anual Conference on
Computational Learning Theory, pages 230–234, 1998.
D. McAllester. PAC-Bayesian model averaging. In the Anual Conference on
Computational Learning Theory, pages 164–170, 1999.
S. Mukherjee, R. Rifkin, and T. Poggio. Regression and classification withregularization. In D. D. Denison, M. H. Hansen, C. C. Holmes, B. Mallick, andB. Yu, editors, Lecture Notes in Statistics: Nonlinear Estimation andClassification, pages 107–124. Springer-Verlag, New York, 2002.
G. Raskutti and M. J. Wainwright. Minimax rates of estimation for
high-dimensional linear regression over ℓq -balls. IEEE Transactions on
Information Theory, 57(10):6976–6994, 2011.
G. Raskutti, M. Wainwright, and B. Yu. Minimax-optimal rates for sparse additivemodels over kernel classes via convex programming. Journal of Machine
Learning Research, 13:389–427, 2012a.
G. Raskutti, M. J. Wainwright, and B. Yu. Minimax-optimal rates for sparse
additive models over kernel classes via convex programming. The Journal of
Machine Learning Research, 13(1):389–427, 2012b.
M. Rudelson and S. Zhou. Reconstruction from anisotropic randommeasurements. IEEE Transactions of Information Theory, 39, 2013.
68 / 68

I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008.
I. Steinwart, D. Hush, and C. Scovel. Optimal rates for regularized least squares
regression. In Proceedings of the Annual Conference on Learning Theory, pages
79–93, 2009.
T. Suzuki. Pac-bayesian bound for gaussian process regression and multiple kernel
additive model. In JMLR Workshop and Conference Proceedings, volume 23,
pages 8.1–8.20, 2012. Conference on Learning Theory (COLT2012).
T. Suzuki and M. Sugiyama. Fast learning rate of multiple kernel learning:
Trade-oﬀ between sparsity and smoothness. In JMLR Workshop and Conference
Proceedings 22, pages 1152–1183, 2012. Fifteenth International Conference on
Artificial Intelligence and Statistics (AISTATS2012).
M. Talagrand. New concentration inequalities in product spaces. Invent. Math.,
126:505–563, 1996a.
M. Talagrand. New concentration inequalities in product spaces. Inventiones
Mathematicae, 126:505–563, 1996b.
M. Talagrand. The generic chaining. Springer, 2000.
T. Tao. Topics in random matrix theory. American Mathematical Society, 2012.
A. Tsybakov. Optimal aggregation of classifiers in statistical learning. Annals of
Statistics, 35:135–166, 2004.
A. B. Tsybakov. Introduction to nonparametric estimation. Springer Series in
Statistics. Springer, 2008.
68 / 68

S. van de Geer. Empirical Processes in M-Estimation. Cambridge University Press,
2000.
A. W. van der Vaart and J. H. van Zanten. Rates of contraction of posterior
distributions based on Gaussian process priors. The Annals of Statistics, 36(3):1435–1463, 2008a.
A. W. van der Vaart and J. H. van Zanten. Reproducing kernel Hilbert spaces ofGaussian priors. Pushing the Limits of Contemporary Statistics: Contributionsin Honor of Jayanta K. Ghosh, 3:200–222, 2008b. IMS Collections.
A. W. van der Vaart and J. H. van Zanten. Information rates of nonparametricgaussian process methods. Journal of Machine Learning Research, 12:
2095–2119, 2011.
V. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative
frequencies of events to their probabilities. Soviet Math. Dokl., 9:915–918,
1968.
M. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint.
Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge
University Press, 2019.
Y. Yang and A. Barron. Information-theoretic determination of minimax rates of
convergence. The Annals of Statistics, 27(5):1564–1599, 1999.
T. Zhang. Some sharp performance bounds for least squares regression with l1
regularization. The Annals of Statistics, 37(5):2109–2144, 2009.
68 / 68

P. Alquier and K. Lounici. PAC-Bayesian bounds for sparse regression estimation
with exponential weights. Electronic Journal of Statistics, 5:127–145, 2011.
R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin. A simple proof of therestricted isometry property for random matrices. Constructive Approximation,
28(3):253–263, 2008.
P. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. The
Annals of Statistics, 33:1487–1537, 2005.
P. Bartlett, M. Jordan, and D. McAuliﬀe. Convexity, classification, and riskbounds. Journal of the American Statistical Association, 101:138–156, 2006.
C. Bennett and R. Sharpley. Interpolation of Operators. Academic Press, Boston,
1988.
P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of Lasso and
Dantzig selector. The Annals of Statistics, 37(4):1705–1732, 2009.
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A
Nonasymptotic Theory of Independence. OUP Oxford, 2013. ISBN
9780199535255. URL
https://books.google.co.jp/books?id=koNqWRluhP0C.
O. Bousquet. A Bennett concentration inequality and its application to supremaof empirical process. C. R. Acad. Sci. Paris Ser. I Math., 334:495–500, 2002.
68 / 68

E. Candès. The restricted isometry property and its implications for compressedsensing. Compte Rendus de l’Academie des Sciences, Paris, Serie I, 346:
589–592, 2008.
F. P. Cantelli. Sulla determinazione empirica della leggi di probabilità. G. Inst.
Ital. Attuari, 4:221–424, 1933.
O. Catoni. Statistical Learning Theory and Stochastic Optimization. Lecture
Notes in Mathematics. Springer, 2004. Saint-Flour Summer School on
Probability Theory 2001.
O. Catoni. PAC-Bayesian Supervised Classification (The Thermodynamics ofStatistical Learning). Lecture Notes in Mathematics. IMS, 2007.
A. Dalalyan and A. B. Tsybakov. Aggregation by exponential weighting sharp
PAC-Bayesian bounds and sparsity. Machine Learning, 72:39–61, 2008.
S. Dasgupta and A. Gupta. An elementary proof of the johnson-lindenstrauss
lemma. Technical Report 99–006, U.C. Berkeley, 1999.
K. R. Davidson and S. J. Szarek. Local operator theory, random matrices andBanach spaces, volume 1, chapter 8, pages 317–366. North Holland, 2001.
M. Donsker. Justification and extension of doob’s heuristic approach to thekolmogorov-smirnov theorems. Annals of Mathematical Statistics, 23:277–281,
1952.
R. M. Dudley. The sizes of compact subsets of hilbert space and continuity ofgaussian processes. J. Functional Analysis, 1:290–330, 1967.
68 / 68

M. Eberts and I. Steinwart. Optimal learning rates for least squares svms using
gaussian kernels. In Advances in Neural Information Processing Systems 25,
2012.
S. Ghosal and A. W. van der Vaart. Posterior convergence rates of dirichlet
mixtures at smooth densities. The Annals of Statistics, 35(2):697–723, 2007.
S. Ghosal, J. K. Ghosh, and A. W. van der Vaart. Convergence rates of posterior
distributions. The Annals of Statistics, 28(2):500–531, 2000.
J. Ghosh and R. Ramamoorthi. Bayesian Nonparametrics. Springer, 2003.
V. I. Glivenko. Sulla determinazione empirica di probabilità. G. Inst. Ital. Attuari,
4:92–99, 1933.
W. B. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into ahilbert space. In Conference in Modern Analysis and Probability, volume 26,
pages 186–206, 1984.
W. B. Johnson, J. Lindenstrauss, and G. Schechtman. Extensions of lipschitz
maps into banach spaces. Israel Journal of Mathematics, 54(2):129–138, 1986.
A. Kolmogorov. Sulla determinazione empirica di una legge di distribuzione. G.
Inst. Ital. Attuari, 4:83–91, 1933.
V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk
minimization. The Annals of Statistics, 34:2593–2656, 2006.
M. Ledoux. The concentration of measure phenomenon. American MathematicalSociety, 2001.
68 / 68

P. Massart. About the constants in talagrand’s concentration inequalities for
empirical processes. The Annals of Probability, 28(2):863–884, 2000.
D. McAllester. Some PAC-Bayesian theorems. In the Anual Conference on
Computational Learning Theory, pages 230–234, 1998.
D. McAllester. PAC-Bayesian model averaging. In the Anual Conference on
Computational Learning Theory, pages 164–170, 1999.
S. Mukherjee, R. Rifkin, and T. Poggio. Regression and classification withregularization. In D. D. Denison, M. H. Hansen, C. C. Holmes, B. Mallick, andB. Yu, editors, Lecture Notes in Statistics: Nonlinear Estimation andClassification, pages 107–124. Springer-Verlag, New York, 2002.
G. Raskutti and M. J. Wainwright. Minimax rates of estimation for
high-dimensional linear regression over ℓq -balls. IEEE Transactions on
Information Theory, 57(10):6976–6994, 2011.
G. Raskutti, M. Wainwright, and B. Yu. Minimax-optimal rates for sparse additivemodels over kernel classes via convex programming. Journal of Machine
Learning Research, 13:389–427, 2012a.
G. Raskutti, M. J. Wainwright, and B. Yu. Minimax-optimal rates for sparse
additive models over kernel classes via convex programming. The Journal of
Machine Learning Research, 13(1):389–427, 2012b.
M. Rudelson and S. Zhou. Reconstruction from anisotropic randommeasurements. IEEE Transactions of Information Theory, 39, 2013.
68 / 68

I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008.
I. Steinwart, D. Hush, and C. Scovel. Optimal rates for regularized least squares
regression. In Proceedings of the Annual Conference on Learning Theory, pages
79–93, 2009.
T. Suzuki. Pac-bayesian bound for gaussian process regression and multiple kernel
additive model. In JMLR Workshop and Conference Proceedings, volume 23,
pages 8.1–8.20, 2012. Conference on Learning Theory (COLT2012).
T. Suzuki and M. Sugiyama. Fast learning rate of multiple kernel learning:
Trade-oﬀ between sparsity and smoothness. In JMLR Workshop and Conference
Proceedings 22, pages 1152–1183, 2012. Fifteenth International Conference on
Artificial Intelligence and Statistics (AISTATS2012).
M. Talagrand. New concentration inequalities in product spaces. Invent. Math.,
126:505–563, 1996a.
M. Talagrand. New concentration inequalities in product spaces. Inventiones
Mathematicae, 126:505–563, 1996b.
M. Talagrand. The generic chaining. Springer, 2000.
T. Tao. Topics in random matrix theory. American Mathematical Society, 2012.
A. Tsybakov. Optimal aggregation of classifiers in statistical learning. Annals of
Statistics, 35:135–166, 2004.
A. B. Tsybakov. Introduction to nonparametric estimation. Springer Series in
Statistics. Springer, 2008.
68 / 68

S. van de Geer. Empirical Processes in M-Estimation. Cambridge University Press,
2000.
A. W. van der Vaart and J. H. van Zanten. Rates of contraction of posterior
distributions based on Gaussian process priors. The Annals of Statistics, 36(3):1435–1463, 2008a.
A. W. van der Vaart and J. H. van Zanten. Reproducing kernel Hilbert spaces ofGaussian priors. Pushing the Limits of Contemporary Statistics: Contributionsin Honor of Jayanta K. Ghosh, 3:200–222, 2008b. IMS Collections.
A. W. van der Vaart and J. H. van Zanten. Information rates of nonparametricgaussian process methods. Journal of Machine Learning Research, 12:
2095–2119, 2011.
V. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative
frequencies of events to their probabilities. Soviet Math. Dokl., 9:915–918,
1968.
M. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint.
Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge
University Press, 2019.
Y. Yang and A. Barron. Information-theoretic determination of minimax rates of
convergence. The Annals of Statistics, 27(5):1564–1599, 1999.
T. Zhang. Some sharp performance bounds for least squares regression with l1
regularization. The Annals of Statistics, 37(5):2109–2144, 2009.
68 / 68