2018-12-20 Taiji Suzuki e-mail: [email protected] Solve the following problems.

Reporting assignment

「機械学習と深層学習の数理と応用」

2018-12-20 Taiji Suzuki e-mail: [email protected] Solve the following problems.

Due date: 10 January/2019.

1. Consider a linear model

Y = Xβ ^∗ + ϵ

where Y ∈ R ⁿ , X ∈ R ^{n × p} , and ϵ = (ϵ _i ) ⁿ _i=1 ∈ R ⁿ . Suppose that ϵ _i is an i.i.d. noise such that E[ϵ _i ] = 0 and E[ϵ ² _i ] = σ ² and X ^⊤ X is full rank. In this setting, evaluate the in-sample predictive error

E Y | X

[ 1

n ∥ Xβ ^∗ − X β ˆ LS ∥ ² ]

. of the least squared estimator ˆ β LS ∈ R ^p .

2. (Stein’s shrinkage estimator) Let X = [X 1 , . . . , X d ] ^⊤ ∈ R ^d be distributed from multivariate normal N(µ, I) (mean µ and variance-covariance I). Assume d ≥ 3. Then, show that

δ = (

1 − (d − 2)

∥ X ∥ ² )

X satisfies

E _{X ∼ N (µ,I)} [ ∥ X − µ ∥ ² ] > E _{X ∼ N (µ,I)} [ ∥ δ(X) − µ ∥ ² ] ( ∀ µ ∈ R ^d ).

You may use the following Stein’s identy without proof: For a function f : R ^d → R ^d (X 7→ f (X ) = [f 1 (X), . . . , f d (X )] ^⊤ ) such that E X [f i (X )] exists and f i is differentiable almost everywhere for all i, it holds that

E X [ − 2 ⟨ µ − X, f (X ) ⟩ ] = 2σ ² E X

[ _d

∑

i=1

∂f i (X )

∂X i

] .

3. For 1 ≤ q < ∞ , let ∥ w ∥ q := ( ∑ d

i=1 | w _i | ^q ) ^1/q for w ∈ R ^d , and H q := { f (x) = w ^⊤ x (x ∈ R ^d ) | ∥ w ∥ q ≤ 1, w ∈ R ^d } . Given x 1 , . . . , x n ∈ R ⁿ , its empirical Rademacher complexity is denoted by

R ˆ _n ( H q ) = E _σ [

sup

f ∈H

1 n

∑ n i=1

σ _i f (x _i )

x ₁ , . . . , x _d ]

.

Now, suppose that 1 ≤ p, q < ∞ satisfies q < p. Then, show that R ˆ n ( H p ) ≤ d ^1/p

^{− 1/q}

R ˆ n ( H q ) where p ^∗ = p/(p − 1) and q ^∗ = q/(q − 1).

4. Prove the Massart’s theorem: For a finite set of functions F = { f 1 , . . . , f M } where each f i (i = 1, . . . , M ) is a function from R ^d to R satisfying sup _x | f i (x) | ≤ R, it holds that

R ˆ _n ( F ) ≤ R

√ 2 log M

n .

Hint: You may use the following inequalities:

• Jensen’s inequality: exp(sE _σ [g(σ ₁ , . . . , σ _n )]) ≤ E _σ [exp(sg(σ ₁ , . . . , σ _n ))] for s ∈ R and g : R ⁿ → R .

• exp(max _{f ∈F} F(f )) ≤ ∑

f ∈F exp(F (f)) for F : F → R .

• Hoeffding’s inequality: E σ

[exp(σ i a)] ≤ exp(a ² /2) for a ∈ R .

5. Suppose that ∥ x ∥ ∞ < 1 (a.s.). Derive an upper bound of the Rademacher complexity of a neural network model:

F =

 



∑ M j=1

α j η(a ^⊤ _j x) | α j ∈ R , a j ∈ R ^d , max

1 ≤ j ≤ M ∥ a j ∥ p ≤ C 1 , ∥ α ∥ q ≤ C 2

 

 where 1 ≤ p, q ≤ ∞ and η(u) = max { u, 0 } .

1