Outlineεύʔεਪఆͷ਺ཧɿ౷‫ܭ‬ཧ࿦͔Β‫ࢉܭ‬ख๏·Ͱ
† ‡

ླ໦ɹେ࣊

1

εύʔεਪఆͷϞσϧ

2

͍Ζ͍Ζͳεύʔεਖ਼ଇԽ3

εύʔεਪఆͷཧ࿦n ≫ p ͷཧ࿦n ≪ p ͷཧ࿦ΑΓߴ౓ͳτϐοΫ

4ߴ࣍‫ݩ‬ઢ‫ܗ‬ճ‫ؼ‬ͷ‫ݕ‬ఆ5

εύʔεਪఆͷ࠷దԽख๏

†౦‫ۀ޻ژ‬େֶ‡JST ͖͕͚͞

2015 ೥ 12 ݄ 24 ೔Ԡ༻਺ཧֶձʮՊֶٕज़‫਺ͱࢉܭ‬஋ղੳʯ‫ڀݚ‬෦ձηϛφʔ

1 / 95ߴ࣍‫ݩ‬σʔλͰͷ໰୊ҙࣝ

2 / 95ྺ࢙: εύʔεਪఆͷख๏ͱཧ࿦

ήϊϜσʔλۚ༥σʔλ‫ڠ‬ௐϑΟϧλϦϯά

1992 Donoho and Johnstone

Wavelet shrinkage(Soft-thresholding)1996 Tibshirani

Lasso ͷఏҊ

2000 Knight and Fu

Lasso ͷ઴ۙ෼෍(n ≫ p)ίϯϐϡʔλϏδϣϯ

ѹॖηϯγϯά
(੍‫ݶ‬౳௕ੑɼ‫׬‬શ෮‫ݩ‬ɼp ≫ n)2006 Candes and Tao,
DonohoԻ੠ೝࣝ࣍‫ ݩ‬d = 10000 ͷ࣌ɼαϯϓϧ਺ n = 1000 Ͱਪఆ͕Ͱ͖Δ͔ʁͲͷΑ͏ͳ৚͕݅͋Ε͹ਪఆ͕Մೳ͔ʁ

2009 Bickel et al., ZhangԿΒ͔ͷ௿࣍‫ݩ‬ੑ (εύʔεੑ) Λར༻ɽ2013 van de Geer et al.,
Lockhart et al.

੍‫ݻݶ‬༗஋৚݅
(Lasso ͷϦεΫධՁ, p ≫ n)εύʔεਪఆʹ͓͚Δ‫ݕ‬ఆ(p ≫ n)͜ΕҎલʹ΋൓ࣹ๏஍਒୳ࠪ΍ը૾ࡶԻআ‫ڈ‬ɼ๨٫෇͖ߏ଄ֶशʹ L1 ਖ਼ଇԽ͸࢖ΘΕ͍ͯͨɽৄ͠
͘͸ాதར޾ (2010) Λࢀর.
3 / 95ߴ࣍‫ݩ‬σʔλղੳ

Outline1εύʔεਪఆͷϞσϧ

2

͍Ζ͍Ζͳεύʔεਖ਼ଇԽ3

εύʔεਪఆͷཧ࿦n ≫ p ͷཧ࿦n ≪ p ͷཧ࿦ΑΓߴ౓ͳτϐοΫ

4ߴ࣍‫ݩ‬ઢ‫ܗ‬ճ‫ؼ‬ͷ‫ݕ‬ఆ5

εύʔεਪఆͷ࠷దԽख๏

4 / 95αϯϓϧ਺ ≪ ࣍‫ݩ‬όΠΦΠϯϑΥ
5 / 95ςΩετσʔλը૾σʔλ6 / 95ߴ࣍‫ݩ‬σʔλղੳεύʔεਪఆ

αϯϓϧ਺ ≪ ࣍‫ݩ‬ʷ ‫ݹ‬యత਺ཧ౷‫ֶܭ‬ɿαϯϓϧ਺ ≫ ࣍‫ݩ‬αϯϓϧ਺ ≪ ࣍‫ݩ‬ແବͳ৘ใΛ੾Γམͱ͢ˠεύʔεੑ

Lasso ਪఆྔόΠΦΠϯϑΥ

ςΩετσʔλR. Tsibshirani (1996). Regression shrinkage and selection via the lasso.
J. Royal. Statist. Soc B., Vol. 58, No. 1, pages 267–288.
Ҿ༻਺ɿ14728 (2015 ೥ 12 ݄ 23 ೔)ը૾σʔλ6 / 957 / 95ม਺બ୒ͷ໰୊ʢઢ‫ܗ‬ճ‫ؼ‬ʣม਺બ୒ͷ໰୊ʢઢ‫ܗ‬ճ‫ؼ‬ʣσβΠϯߦྻ X = (Xij ) ∈ Rn×p ,Ԡ౴ม਺ Y = (Yi ) ∈ Rn
p (࣍‫ ≫ )ݩ‬n (αϯϓϧ਺).
ਅͷϕΫτϧ β ∗ ∈ Rp : ඇθϩཁૉͷ‫ ͔͔͕ͩͨ਺ݸ‬d ‫( ݸ‬εύʔε).

σβΠϯߦྻ X = (Xij ) ∈ Rn×p ,Ԡ౴ม਺ Y = (Yi ) ∈ Rn
p (࣍‫ ≫ )ݩ‬n (αϯϓϧ਺).
ਅͷϕΫτϧ β ∗ ∈ Rp : ඇθϩཁૉͷ‫ ͔͔͕ͩͨ਺ݸ‬d ‫( ݸ‬εύʔε).

Ϟσϧ : Y = X β ∗ + ǫ
Pp(Yi = j=1 Xij βj∗ + ǫi )Ϟσϧ : Y = X β ∗ + ǫ
Pp(Yi = j=1 Xij βj∗ + ǫi )(i = 1, . . . , n))(Y , X ) ͔Β β ∗ Λਪఆɽ࣮࣭ਪఆ͠ͳͯ͘͸͍͚ͳ͍ม਺ͷ਺͸ d ‫ݸ‬ˠม਺બ୒ɽ

(i = 1, . . . , n))(Y , X ) ͔Β β ∗ Λਪఆɽ࣮࣭ਪఆ͠ͳͯ͘͸͍͚ͳ͍ม਺ͷ਺͸ d ‫ݸ‬ˠม਺બ୒ɽ

Mallows’ Cp , AIC:β̂MC = argmin kY − X βk2 + 2σ 2 kβk0
β∈Rpͨͩ͠ kβk0 = |{j | βj 6= 0}|.
ˠ 2p ‫ݸ‬ͷީิΛ୳ࡧɽNP-ࠔ೉ɽ
8 / 958 / 95Lasso ਪఆྔβ̂MC = argmin kY − X βk2 + 2σ 2 kβk0 .

Mallows’ Cp ࠷খԽ:β∈Rp໰୊఺: kβk0 ͸ತؔ਺Ͱ͸ͳ͍ɽ࿈ଓͰ΋ͳ͍ɽ୔ࢁͷ‫࠷ॴہ‬దղɽˠ ತؔ਺Ͱۙࣅɽ

Lasso [L1 ਖ਼ଇԽ]β̂Lasso = argmin kY − X βk2 + λkβk1
β∈Rpͨͩ͠ kβk1 =http://www.astroml.org/sklearn_tutorial/practical.html

Pp

j=1 |βj |.

ˠ ತ࠷దԽʂ
L1 ϊϧϜ͸ L0 ϊϧϜͷ [−1, 1]p ʹ͓͚Δ
ತแ (Լ͔Β཈͑Δ࠷େͷತؔ਺)
L1 ϊϧϜ͸ཁૉ਺ؔ਺ͷ Lovász ֦ு

y = b + β 1 x + β2 x 2 + · · · + β d x d + ǫ

9 / 95

10 / 95

Lasso ਪఆྔͷεύʔεੑ

Lasso ਪఆྔͷεύʔεੑp = n, X = I ͷ৔߹ɽ

⇒

p

X
1
|βj |.
β̂ = arg min kX β − Y k22 + λn
p
n
β∈R

1
kY − βk2 + C kβk1
β̂Lasso = argmin2β∈Rp1(yi − b)2 + C |b|β̂Lasso,i = argmin
2b∈R((|yi | > C )sign(yi )(yi − C )=0(|yi | ≤ C ).

j=1

খ͍͞γάφϧ͸ 0 ʹॖখ͞ΕΔˠεύʔεʂ11 / 95εύʔεੑͷԸ‫ܙ‬12 / 95

਺஋ྫp

Y = X β + ǫ.

j=1

n = 1, 000, p = 10, 000, d = 500.

X
1
β̂ = arg min kX β − Y k22 + λn|βj |.
β∈Rp n10

True

Theorem (Lasso ͷऩଋϨʔτ)98

͋Δ৚݅ͷ΋ͱɼఆ਺ C ͕ଘࡏͯ͠ߴ͍֬཰Ͱ࣍ͷෆ౳͕ࣜ੒Γཱͭɿ

7

6

dlog(p).
kβ̂ − β ∗ k22 ≤ Cn54˞࣍‫ͯ͘ߴ͕ݩ‬΋ɼ͔͔ͨͩ log(p) Ͱ͔͠ޮ͍ͯ͜ͳ͍ɽ࣮࣭తͳ࣍‫ ݩ‬d ͕ࢧ഑తɽʢʮ͋Δ৚݅ʯʹ͍ͭͯ͸‫ࡉৄͰޙ‬Λઆ໌ʣ

3

2

1

0
0

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

13 / 95਺஋ྫ

14 / 95

਺஋ྫY = X β + ǫ.

Y = X β + ǫ.

n = 1, 000, p = 10, 000, d = 500.

n = 1, 000, p = 10, 000, d = 500.

12

12

True
Lasso

10

True
Lasso
LeastSquares

10

8

8

6

6

4

4

2

2

0

0

-2

-2
0

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

0

14 / 95

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

14 / 95

Lasso ΛҰൠԽOutline1εύʔεਪఆͷϞσϧ

2

͍Ζ͍Ζͳεύʔεਖ਼ଇԽ

Lasso:n1X(yi − xi⊤ β)2 + kβk1 .
| {z }
n

minp

β∈R
3

εύʔεਪఆͷཧ࿦n ≫ p ͷཧ࿦n ≪ p ͷཧ࿦ΑΓߴ౓ͳτϐοΫ

4ߴ࣍‫ݩ‬ઢ‫ܗ‬ճ‫ؼ‬ͷ‫ݕ‬ఆ5

εύʔεਪఆͷ࠷దԽख๏

i=1

ਖ਼ଇԽ߲

15 / 95

16 / 95

Lasso ΛҰൠԽ
L1 ਖ਼ଇԽʹΑͬͯεύʔεʹͳΔཧ༝ɿ࠲ඪ࣠ʹԊͬͯ ઑ͍ͬͯΔɽ
Lasso:
n

minp

β∈R

1X
(yi − xi⊤ β)2 + kβk1 .
| {z }ni=1ਖ਼ଇԽ߲ҰൠԽͨ͠εύʔεਖ਼ଇԽਪఆ๏:
n

minp

w ∈R

1X
ℓ(zi , β) + ψ(β).
ni=1L1 ਖ਼ଇԽ߲Ҏ֎ʹͲͷΑ͏ͳਖ਼ଇԽ߲͕༗༻Ͱ͋Ζ͏͔ʁਖ਼ଇԽ߲ͷ ઑΓํ Λ޻෉͢Δ͜ͱͰ༷ʑͳεύʔεੑ͕ಘΒΕΔɽ

16 / 95άϧʔϓਖ਼ଇԽ

άϧʔϓਖ਼ଇԽͷԠ༻ྫ
ॏෳͳ͠

C

X
g∈G

17 / 95ॏෳ͋ΓϚϧνλεΫֶश Lounici et al. (2009)T ‫ݸ‬ͷλεΫͰಉ࣌ʹਪఆ:

kβg k

(t)

yi

(t)⊤ (t)≈ xi(i = 1, . . . , n(t) , t = 1, . . . , T ).

β

(t)

min
β (t)

άϧʔϓ಺͢΂ͯͷม਺͕ಉ࣌ʹ 0 ʹͳΓ΍͍͢ɽΑΓੵ‫ۃ‬తʹεύʔεʹͰ͖Δɽ

T X
nX
t=1 i=1β(1) β(2)Ԡ༻ྫɿήϊϜϫΠυ૬ؔղੳ(t)⊤ (t) 2(yi − xiβ ) +C

p
X
k=1

|

(1)

(T )

k(βk , . . . , βk )k.
{zάϧʔϓਖ਼ଇԽβ(T)}*URXS

‫؞؞؞ ؞؞؞‬*URXS

*URXS

λεΫؒ‫ڞ‬௨Ͱඇθϩͳม਺Λબ୒
18 / 95

19 / 95άϧʔϓਖ਼ଇԽͷԠ༻ྫτϨʔεϊϧϜਖ਼ଇԽϚϧνλεΫֶश Lounici et al. (2009)T ‫ݸ‬ͷλεΫͰಉ࣌ʹਪఆ:(t)yi(t)⊤ (t)≈ xi(i = 1, . . . , n(t) , t = 1, . . . , T ).

β

(t)

n
T X
X

min
β (t)

t=1 i=1(t)⊤ (t) 2(yi − xiβ ) +CpX
k=1|

β(1) β(2)W : M × N ߦྻɽ
min{M,N}

(1)

{z

}

άϧʔϓਖ਼ଇԽ

β(T)

X

1

kW kTr = Tr[(WW ⊤ ) 2 ] =(T )k(βk , . . . , βk )k.

σj (W )j=1

σj (W ) ͸ W ͷ j ൪໨ͷಛҟ஋ (ඇෛͱ͢Δ)ɽ

*URXS

ಛҟ஋ͷ࿨ = ಛҟ஋΁ͷ L1 ਖ਼ଇԽ ˠ ಛҟ஋͕εύʔε*URXS

‫؞؞؞ ؞؞؞‬ಛҟ஋͕εύʔε = ௿ϥϯΫ

*URXS

λεΫؒ‫ڞ‬௨Ͱඇθϩͳม਺Λબ୒
19 / 95

ྫ: ਪનγεςϜ

20 / 95

ྫ: ਪનγεςϜ
ϥϯΫ 1 ͱԾఆ͢Δ

өը A

өը B

өը C

···

өը X

Ϣʔβ 1

4

8

*

···

2

Ϣʔβ 2

2

*

2

···

Ϣʔβ 3

2

4

*

···

..
.

өը A

өը B

өը C

···

өը X

Ϣʔβ 1

4

8

4

···

2

*

Ϣʔβ 2

2

4

2

···

1

*

Ϣʔβ 3

2

4

2

···

1

..
.

(e.g., Srebro et al. (2005), NetFlix Bennett and Lanning (2007))(e.g., Srebro et al. (2005), NetFlix Bennett and Lanning (2007))
X(i,j)∈T(Yi,j − Wi,j )2 + λkW kTr

21 / 95

ྫ: ਪનγεςϜ

21 / 95

ྫ: ॖখϥϯΫճ‫ؼ‬ॖখϥϯΫճ‫( ؼ‬Anderson, 1951, Burket, 1964, Izenman, 1975)
NϚϧνλεΫֶश (Argyriou et al., 2008)
映画W*=ॖখϥϯΫճ‫ؼ‬
X

Y

M

=

n

W*

N

W

+

ユーザ
N

M

ˠ ௿ϥϯΫߦྻิ‫׬‬:௿ϥϯΫߦྻͷ Rademacher Complexity: Srebro et al. (2005).

Compressed sensing: Candès and Tao (2009), Candès and Recht (2009).

W ∗ ͸ ௿ϥϯΫ.
22 / 95

23 / 95εύʔε‫ڞ‬෼ࢄબ୒b = 1 Pn xk x ⊤ .
Σ
k
k=1
n

xk ∼ N(0, Σ) (i.i.d., Σ ∈ Rp×p ),Ŝ = argmin
S:൒ਖ਼ఆରশ

b +λ− log(det(S)) + Tr[S Σ]

p
X

i,j=1


|Si,j | .

(Meinshausen and B uhlmann, 2006, Yuan and Lin, 2007, Banerjee et al., 2008)Σ ͷ‫ ྻߦٯ‬S ΛਪఆɽSi,j = 0 ⇔ X(i) , X(j) ͕৚݅෇͖ಠཱɽ
Ψ΢γΞϯάϥϑΟΧϧϞσϧ͕ತ࠷దԽͰਪఆͰ͖Δɽ

NASDAQ ໏ฑ͔ΒϥϯμϜநग़ͨ͠ 50 ໏ฑɽ‫ג‬ՁσʔλΛ༻͍ͨ෼ࢄ‫ڞ‬෼ࢄબ୒. ࣌ؒࠩ΋ߟྀɽ
(2011 ೥ 1 ݄ 4 ೔͔Β 2014 ೥ 12 ݄ 31 ೔·Ͱ)(Lie Michael, Bachelor thesis)

24 / 95(ҰൠԽ) Fused Lasso

25 / 95ඇತਖ਼ଇԽψ(β) = CX(i,j)∈E



/
6&$'
0&3
/T T |βi − βj |.

(Tibshirani et al. (2005), Jacob et al. (2009))








Fused lasso ʹΑΔҨ఻ࢠσʔλղੳ (Tibshirani and















SCAD (Smoothly Clipped Absolute Deviation) (Fan and Li, 2001)
MCP (Minimax Concave Penalty) (Zhang, 2010)
Lq ਖ਼ଇԽ (q < 1), Bridge ਖ਼ଇԽ (Frank and Friedman, 1993)

TV σϊΠδϯά (Chambolle ‘04)

Taylor ‘11)ΑΓεύʔεͳղɽͦͷ୅ΘΓ࠷దԽ͸೉͘͠ͳΔɽ
26 / 95

ͦͷଞ L1 ਖ਼ଇԽͷ֦ு27 / 95

OutlineAdaptive Lasso (Zou, 2006)
͋ΔҰகਪఆྔ β̃ ͕͋Δͱͯ͠ɼͦΕΛར༻ɽ
ψ(β) = C

p
X
|βj |

|β̃j |γj=1

Lasso ΑΓ΋খ͍͞όΠΞε (઴ۙෆภ)ɽ
ΦϥΫϧϓϩύςΟɽεύʔεՃ๏Ϟσϧ(Hastie and Tibshirani, 1999, Ravikumar et al., 2009)Pp
f (x) = j=1 fj (xj ) ͳΔඇઢ‫਺ؔܗ‬Λਪఆɽfj ∈ Hj (Hj : ࠶ੜ֩ώϧϕϧτۭؒ) ͱ͢Δɽ

ψ(f ) = CpX
j=1

kfj kHj1εύʔεਪఆͷϞσϧ

2

͍Ζ͍Ζͳεύʔεਖ਼ଇԽ3

εύʔεਪఆͷཧ࿦n ≫ p ͷཧ࿦n ≪ p ͷཧ࿦ΑΓߴ౓ͳτϐοΫ

4ߴ࣍‫ݩ‬ઢ‫ܗ‬ճ‫ؼ‬ͷ‫ݕ‬ఆ5

εύʔεਪఆͷ࠷దԽख๏

Group Lasso ͷҰൠԽɽ
Multiple Kernel Learning ͱ΋‫ݺ‬͹ΕΔɽ28 / 95

29 / 95໰୊ઃఆ؆୯ͷͨΊઢ‫ܗ‬ճ‫ؼ‬Λߟ͑Δɽn ≫ p ͷཧ࿦Y = X β ∗ + ǫ.
Y ∈ R : Ԡ౴ม਺, X ∈ R
n

n×p

⊤

: આ໌ม਺, ǫ = [ǫ1 , . . . , ǫn ] ∈ R .
nҰൠԽઢ‫ܗ‬ճ‫΁ؼ‬ͷҰൠԽ΋Մೳɽ

30 / 95

31 / 95

Lasso ͷ઴ۙ෼෍

Adaptive Lasso ͷΦϥΫϧϓϩύςΟp ͸‫ݻ‬ఆɼn → ∞ ͷ઴ۙతৼΔ෣͍Λߟ͑Δɽβ̃ ͸͋ΔҰகਪఆྔɽp
1 ⊤n X X −→ C ≻ O.

p

X |βj |
1.
β̂ = argmin kY − X βk2 + λnn|β̃j |γβϊΠζ ǫi ͸ฏ‫ ۉ‬0 ෼ࢄ σ 2 ͱ͢Δ.

j=1

Theorem (Lasso ͷ઴ۙ෼෍ (Knight and Fu, 2000))√
λn n → λ0 ≥ 0 ͳΒ√∗Theorem (Adaptive Lasso ͷΦϥΫϧϓϩύςΟ (Zou, 2006))dn(β̂ − β ) −→ argmin V (u),uPp⊤ͨͩ͠ɼV (u) = u Cu − 2u ⊤ W + λ0 j=1 [uj sign(βj∗ )1(βj∗ 6= 0) + |uj |1(βj∗ = 0)],W ∼ N(0, σ 2 C ).
√β̂ ͸ n-consistent Ͱ͋Δɽ∗βj = 0 ͳΔ੒෼Ͱ β̂j ͸ ਖ਼ͷ֬཰Ͱ 0 ͱͳΔɽୈࡾ߲ͷ͍ͤͰɼ઴ۙతʹόΠΞε͕࢒ΔɽPpβ̂ = argminβ n1 kY − X βk2 + λn j=1 |βj |.

√1+γλn n → 0, λn n 2 → ∞ ͷͱ͖ɼ1limn→∞ P(Ĵ = J) → 1(Ĵ := {j | |β̂j | 6= 0}, J := {j | |βj∗ | 6= 0}),√d−12n(β̂J − βJ∗ ) −→ N(0, σ 2 CJJ).
ม਺બ୒ͷҰகੑ͋Γɽ઴ۙෆภɼ઴ۙਖ਼‫ن‬ੑ͋Γɽ√ͨͩ͠ɼβ ∗ ͷ͋Δ੒෼͕‫ͮۙ͘ʹ఺ݪ‬Α͏ͳ‫ॴہ‬తͳٞ࿦ (βj∗ = O(1/ n)ͳΔঢ়‫͍ͯͭʹ )گ‬͸Կ΋‫ʹͱ͍͜ͳ͍ͯͬݴ‬஫ҙɽ32 / 95

33 / 95

Lass ͷϦεΫͷ্քpX
1β̂ = arg min kX β − Y k22 + λn|βj |.
β∈Rp nj=1

Theorem (Lasso ͷऩଋϨʔτ (Bickel et al., 2009, Zhang, 2009))n ≪ p ͷཧ࿦σβΠϯߦྻ͕ Restricted eigenvalue condition (Bickel et al., 2009) ͔ͭ
2 2maxi,j |Xij | ≤ 1 Λຬͨ͠ɼϊΠζ͕ E[e τ ξi ] ≤ e σ τ /2 (∀τ > 0) Λຬͨ͢ͳΒ, ֬཰1−δͰd log(p/δ)
kβ̂ − β ∗ k22 ≤ C.
n࣍‫ͯ͘ߴ͕ݩ‬΋ɼ͔͔ͨͩ log(p) Ͱ͔͠ޮ͍ͯ͜ͳ͍ɽ࣮࣭తͳ࣍‫ ݩ‬d ͕ࢧ഑తɽϊΠζͷ৚݅͸αϒΨ΢γΞϯͷඞཁे෼৚݅ɽ

34 / 95

35 / 95

Lasso ͷ minimax ࠷దੑ੍‫ݻݶ‬༗஋৚݅ (Restricted eigenvalue condition)
A = n1 X ⊤ X ͱ͢ΔɽDefinition (੍‫ݻݶ‬༗஋৚݅ (RE(k ′ , C )))Theorem (ϛχϚΫε࠷దϨʔτ (Raskutti and Wainwright, 2011))

φRE (k ′ , C ) = φRE (k ′ , C , A) :=͋Δ৚݅ͷ΋ͱɼ֬཰ 1/2 Ҏ্Ͱɼminβ̂:ਪఆྔ

infJ⊆{1,...,n},v ∈Rp :|J|≤k ′ ,C kvJ k1 ≥kvJ c k1

d log(p/d).
maxkβ̂ − β k ≥ Cnβ ∗ :d-εύʔε∗ 2v ⊤ Av
kvJ k22ʹର͠ɼφRE > 0 ͕੒Γཱͭɽ΄΅εύʔεͳϕΫτϧʹ੍‫ͯ͠ݶ‬ఆٛͨ͠࠷খ‫ݻ‬༗஋ɽ

Lasso ͸ minimax ϨʔτΛୡ੒͢Δ ( d log(d)ͷ߲Λআ͍ͯ)ɽ
n

J

ইঝছথॡ

͜ͷ݁ՌΛ Multiple Kernel Learning ʹ֦ுͨ݁͠Ռ: Raskutti et al. (2012),
Suzuki and Sugiyama (2013).

ৼঢ়ऋ৵औः
36 / 95

37 / 95

ద߹ੑ৚݅ (Compatibility condition)੍‫ݶ‬౳௕ੑ৚݅ (Restricted isometory condition)

A = n1 X ⊤ X ͱ͢ΔɽDefinition (੍‫ݶ‬౳௕ੑ৚݅ (RI(k ′ , δ)) (Candes and Tao, 2005))

Definition (ద߹ੑ৚݅ (COM(J, C )))͋Δ 1 > δ > 0 ʹର͠ɼφCOM (J, C ) = φCOM (J, C , A) :=infv ∈Rp :
C kvJ k1 ≥kvJ c k1

kv ⊤ Av
kvJ k21(1 − δ)kβk2 ≤ kX βk2 ≤ (1 + δ)kβk2′

͕શͯͷ k -εύʔεͳϕΫτϧ β ∈ Rp ʹରͯ͠੒Γཱͭɽʹର͠ɼφCOM > 0 ͕੒Γཱͭɽ

Johnson-Lindenstrauss ͷิ୊.
ѹॖηϯγϯάʹ͓͚Δ‫׬‬શ෮‫ݩ‬ͷจ຺ͰΑ͘༻͍ΒΕΔɽ

|J| ≤ k ′ ͳΒɼRE ΑΓ΋ऑ͍৚݅ɽ

38 / 95֤৚݅ͷؔ܎ͱऩଋϨʔτ੍‫ݻݶ‬༗஋৚݅ (RE) ͕੒ཱ͢Δ֬཰੍‫ݻݶ‬༗஋৚݅͸ͲΕ͚ͩ੒Γཱͪ΍͍͔͢ʁβ̂ : Lasso ਪఆྔ.
J := {j | βj∗ 6= 0}. d := |J|.
‫͍ڧ‬RI(Cd, δ)ˠp ࣍‫཰֬ݩ‬ม਺ Z ͕౳ํత: E[hZ , zi2 ] = kzk22 (∀z ∈ Rp ).
αϒΨ΢γΞϯϊϧϜ kZ kψ2 Λ࣍ͷΑ͏ʹఆٛ͢Δ:kZ kψ2 = supz∈Rp ,kzk=1 inf t {t | E[exp(hZ , zi)2 /t 2 ] ≤ 2}.

1∗ 2
n kX (β̂ − β )k2kβ̂ − β ∗ k22 kβ̂ − β ∗ k21ѹॖηϯγϯάʹ͓͚Δ‫׬‬શ෮‫ݩ‬

1. Z = [Z1 , Z2 , . . . , Zn ]⊤ ∈ Rn×p ͷ֤ߦ Zi ∈ Rp ͕ಠཱͳ౳ํతαϒΨ΢γΞ
ϯ֬཰ม਺ͱ͢Δɽ
2. ͋Δ൒ਖ਼ఆରশߦྻ Σ ∈ Rp×p Λ༻͍ͯ X = Z Σ Ͱ͋Δͱ͢Δɽ+ ੍‫ݶ‬௚ަੑ⇓RE(2d, 3)ˠd log(p)nd log(p)nd 2 log(p)nˠd log(p)nd 2 log(p)nd 2 log(p)n⇓COM(J, 3)ऑ͍39 / 95

Theorem (Rudelson and Zhou (2013))
max (Σ )2

i ,ikZi kψ2 ≤ κ (∀i) ͱ͢Δɽ͋Δීวఆ਺ c0 ͕ଘࡏ͠ m = c0 φ2 i(k,9,Σ)ʹର͠ɼREn ≥ 4c0 mκ4 log(60ep/(mκ)) ͳΒ͹b ≥ 1 φRE (k, 9, Σ) ≥ 1 − 2 exp(−n/(4c0 κ4 )).
P φRE (k, 3, Σ)
2ؔ࿈ࣄ߲ͷৄࡉ͸ Bühlmann and van de Geer (2011) ʹ໢ཏ͞Ε͍ͯΔɽ
‫׬‬શ෮‫ݩ‬͸੍‫ݶ‬௚ަੑ (Candes and Tao, 2005) ͳ͠Ͱ΋ࣔͤΔ (Candès, 2008).
RI ͱ RE ͷؔ܎͸ Rudelson and Zhou (2013) Ͱ΋࿦͡ΒΕ͍ͯΔɽ
40 / 95

ͭ·Γɼਅͷ෼ࢄ‫ڞ‬෼ࢄߦྻ੍͕‫ݻݶ‬༗஋৚݅Λຬͨ͢⇒ ‫ݧܦ‬త෼ࢄ‫ڞ‬෼ࢄߦྻ΋ߴ͍֬཰Ͱಉ৚݅Λຬͨ͢ɽ

41 / 95ತ࠷దԽΛ༻͍ͳ͍εύʔεਪఆ๏ͷੑ࣭ΑΓߴ౓ͳτϐοΫɿઢ‫ܗ‬ճ‫ؼ‬Ҏ֎ͷεύʔεਪఆ৘ใྔ‫ن‬४‫ܕ‬ਪఆྔ: Massart (2003), Bunea et al. (2007), Rigollet andTsybakov (2011).
p
minp kY − X βk2 + C σ 2 kβk0 1 + log
.
β∈R
kβk0

ෳ਺ͷσʔλιʔεΛऔࣺબ୒͠౷߹͢Δํ๏ɽ

Bayes ਪఆྔ: Dalalyan and Tsybakov (2008), Alquier and Lounici (2011),
Suzuki (2012).

ϊϯύϥϝτϦοΫεύʔεਪఆɿεύʔεՃ๏Ϟσϧߴ࣍૬ؔͷਪఆɿ௿ϥϯΫςϯιϧϞσϧ

ΦϥΫϧෆ౳ࣜ: X ʹ Կ΋৚݅Λ՝ͣ͞ʹ ࣍ͷෆ౳͕ࣜ੒Γཱͭ:


1
d
p
.
kX β ∗ − X β̂k2 ≤ C σ 2 log 1 +nnd ϛχϚοΫε࠷దɽ ತਖ਼ଇԽਪఆ๏ͱେ͖ͳΪϟοϓɽ ‫ͱྔࢉܭ‬౷‫ܭ‬తੑ࣭ͷτϨʔυΦϑɽ42 / 95εύʔεՃ๏ϞσϧεύʔεՃ๏Ϟσϧઢ‫ܗ‬Ϟσϧ͔Βඇઢ‫ܗ‬Ϟσϧ΁֦ு (ߴ࣍‫ݩ‬ϊϯύϥϝτϦοΫਪఆ)ઢ‫ܗ‬Ϟσϧ͔Βඇઢ‫ܗ‬Ϟσϧ΁֦ு (ߴ࣍‫ݩ‬ϊϯύϥϝτϦοΫਪఆ)

yi =

p
X

43 / 95(j)x i b j + ǫi

j=1

−→

yi =

p
X

(j)

fj (xi ) + ǫi

yi =

j=1

p
X

(j)

x i b j + ǫi

j=1

−→

yi =

p
X

(j)

fj (xi ) + ǫi

j=1

44 / 95

Multiple Kernel Learning

Multiple Kernel Learning

Multiple Kernel Learning (MKL) (Lanckriet et al., 2004, Bach et al., 2004)
fˆ =

M
X

m=1

fˆm ← minfm ∈Hm

n
X
i=1

yi −

44 / 95MX

m=1

fm (xi )

!2

+C

M
X

m=1

Multiple Kernel Learning (MKL) (Lanckriet et al., 2004, Bach et al., 2004)fˆ =kfm kHmM
X

m=1(Hm : ͋Δ࠶ੜ֩ώϧϕϧτۭؒ)fˆm ← minfm ∈Hm

n
X
i=1

yi −

M
X

m=1

fm (xi )

!2

+C

M
X

m=1

kfm kHm(Hm : ͋Δ࠶ੜ֩ώϧϕϧτۭؒ)άϧʔϓਖ਼ଇԽͷແ‫֦ݩ࣍ݶ‬ுεύʔεͳղ: ଟ͘ͷ fˆm ͕ 0.
༗‫࠷ݩ࣍ݶ‬దԽ໰୊ʹ‫ؼ‬ண (ද‫ݱ‬ఆཧ) (Sonnenburg et al., 2006,
Rakotomamonjy et al., 2008, Suzuki and Tomioka, 2009)άϧʔϓਖ਼ଇԽͷແ‫֦ݩ࣍ݶ‬ுεύʔεͳղ: ଟ͘ͷ fˆm ͕ 0.
༗‫࠷ݩ࣍ݶ‬దԽ໰୊ʹ‫ؼ‬ண (ද‫ݱ‬ఆཧ) (Sonnenburg et al., 2006,
Rakotomamonjy et al., 2008, Suzuki and Tomioka, 2009)ਖ਼ଇԽ߲͸ҰൠԽͯ͠Α͍PM

m=1 kfm kHm−→ ψ((kfm kHm )M
m=1 ),

e.g., ℓp -ਖ਼ଇԽ (Micchelli and Pontil, 2005, Kloft et al., 2009)ɼΤϥεςΟοΫωοτਖ਼ଇԽ (Shawe-Taylor, 2008, Tomioka and Suzuki, 2009)ɼVariable Sparsity Kernel
Learning (VSKL) (Aflalo et al., 2011).
45 / 95

45 / 95Ԡ༻ྫεύʔεՃ๏Ϟσϧͷछʑͷ౷‫ܭ‬తੑ࣭όΠΦΠϯϑΥϚςΟΫε

ίϯϐϡʔλϏδϣϯ

༷ʑͳख๏ɾঢ়‫͚͓ʹگ‬ΔऩଋϨʔτ.
1Ұൠͷਖ਼ଇԽ‫ֶܕ‬श (Suzuki, 2011)


2s
1
2s
M log(M) kfˆ − f ∗ k2L2 (Π) = Op M 1− 1+s n− 1+s (k1kψ∗ kf ∗ kψ ) 1+s +.
n2ਅ͕εύʔεͳ৔߹ͷ elastic-net ‫ܕ‬ਖ਼ଇԽֶश (Suzuki and Sugiyama, 2013)


2s
1−s
1
d log(M)1+s,
d 1+s n− 1+s R1,f
∗ +
n

 1+q
2s
1+q
d log(M)−1+q+skfˆ − f ∗ k2L2 (Π) = Op d 1+q+s n 1+q+s R2,g+,∗nkfˆ − f ∗ k2L2 (Π) = Op

(L1)
(Gehler&Nowozin, CVPR2009)(Elastic)(Widmer et al., BMC Bioinformatics 2010)

Time varying coefficient model3ϕΠζ๏: Ψ΢εաఔճ‫ ؼ‬+ Ϟσϧฏ‫( ۉ‬Suzuki, 2012)
EY1:n |x1:n

h





i
X − 1
|I
|
Me
0
o 2
ˆ
1+s
.
m +
n
kf − f kn = Op 
logn
κ|I0 |
m∈I0

ɹˠ Restricted Eigenvalue Condition ͳ͠ͰϛχϚΫεϨʔτΛୡ੒ɽϊϯύϥϝτϦοΫͳঢ়‫Ͱگ‬΋ਅͷඇθϩཁૉ਺͕ࢧ഑తɽ

⊤ x (Lu et al., 2015)
f(t) (x) = β(t)46 / 95

εϖΫτϧ৚݅ (s)47 / 95

ςϯιϧσʔλ0 < s < 1: ࠶ੜ֩ώϧϕϧτۭؒͷෳࡶ͞.
Χʔωϧͷల։ (cf., Mercer ͷఆཧ):P∞
km (x, x ′ ) = ℓ=1 µℓ,m φℓ,m (x)φℓ,m (x ′ ),ͨͩ͠ {φℓ,m }∞ℓ=1 ͸ L2 (P) ʹؔ͢Δਖ਼‫ن‬௚ަ‫ج‬ఈ.
͋Δ 0 < s < 1 ͕ଘࡏͯ͠
1µℓ,m ≤ C ℓ− s

User

ユーザ

εϖΫτϧ৚݅ (s)(∀ℓ, m).

Context

映画

େ͖ͳ s ͸ෳࡶɼখ͞ͳ s ͸୯७.
ෳࡶ͞ s ͷ࠶ੜ֩ώϧϕϧτۭؒʹ͓͚Δ࠷దͳֶशϨʔτ: Op (n

1
− 1+s

Xij =

).

Proposition (Steinwart et al. (2009))

ߦྻPd(1) (2)
r =1 ur ,i ur ,j

−→

Movie

ςϯιϧ (ଟॏઢ‫ܗ‬ΦϖϨʔλʔ)Pd(1) (2) (3)Xijk = r =1 ur ,i ur ,j ur ,k1µℓ,m ∼ ℓ− s ⇔ log N(B(Hm ), ǫ, L2 (P)) ∼ ǫ−2s
48 / 95ͦͷଞԠ༻

49 / 95

ςϯιϧͷճ‫ؼ‬໰୊ςϯιϧิ‫׬‬ɿਪનγεςϜContext

4
4 2 3
3 4 Rating
1 21 41 2 1 42 2 4Item2
3 3 1 1
3 33 211 4 1
2 2
22
Prediction 4
1
11 3
2
2
User

Yi = hXi , A∗ i + Wi .
1 ×...MK: ςϯιϧ.
A∗ , Xi ∈ RMP
hXi , A∗ i := j1 ,...,jK Xi,(j1 ,...,jK ) Aj∗1 ,...,jK .
Wi ∼ N (0, σ 2 ): observational noise.
E.g., Xi = ej1 ⊗ ej2 ⊗ · · · ⊗ ejK ͳΒςϯιϧิ‫׬‬໰୊.

ϚϧνλεΫֶशreԾఆ: A∗ ͸ “௿ϥϯΫ”.

Task type 1

featu

Ta
sk

typ
e2

ࣗવ‫ॲޠݴ‬ཧ (୯‫ޠ‬ͷϕΫτϧද‫)ݱ‬
ۭ࣌ؒղੳ
ؔ܎σʔλ
50 / 95

51 / 95ςϯιϧͷճ‫ؼ‬໰୊ςϯιϧͷϥϯΫ: CP-ϥϯΫ
Yi = hXi , A∗ i + Wi .

1 ×...MKA∗ , Xi ∈ RMP: ςϯιϧ.
hXi , A∗ i := j1 ,...,jK Xi,(j1 ,...,jK ) Aj∗1 ,...,jK .
Wi ∼ N (0, σ 2 ): observational noise.
E.g., Xi = ej1 ⊗ ej2 ⊗ · · · ⊗ ejK ͳΒςϯιϧิ‫׬‬໰୊.

CP-෼ղ (Canonical Polyadic Decomp.)(Hitchcock, 1927a,b)

Ծఆ: A ͸ “௿ϥϯΫ”.
∗(figure is from (Kolda and Bader, 2009))

Pd

Xijk = r =1 air bjr ckr =: [[A, B, C ]].
CP-෼ղ͸ CP-ϥϯΫΛఆٛ͢Δ.

ತਖ਼ଇԽͷΞϓϩʔν:nX(Yi − hXi , A∗ i)2 + pen(A).

CP-෼ղ͸ NP-ࠔ೉.
CP-ϥϯΫ͸ςϯιϧͷลͷ௕͞ΑΓେ͖͘ͳΓ͏Δɽ

CP-ϥϯΫͷತ֦ு࿨‫ ܕ‬Schatten-1 ϊϧϜ (Tomioka et al., 2011)৞ΈࠐΈ‫ ܕ‬Schatten-1 ϊϧϜ (Tomioka and Suzuki, 2013)௚ަ෼ղ͕ଘࡏ͢Δͱ͸‫ݶ‬Βͳ͍ (ରশςϯιϧͰ΋).

min

A∈RM1 ×M2 ×···×MK

i=1

ತ֦ுͷ‫ࢉܭ‬͸ NP-ࠔ೉ɽߦྻͷϥϯΫͷತ֦ு͸‫͠ࢉܭ‬΍͍͢ɽ
51 / 95࿨‫ ܕ‬Schatten-1 ϊϧϜ|||A|||S1 /1 :=

K
X
k=1

kA

(k)

52 / 95৞ΈࠐΈ‫ ܕ‬Schatten-1 ϊϧϜ|||A|||S1 /1 :=

kTr

inf

A=A1 +A2 +···+AK

K
X
k=1

(k)

kAk kTr৞ΈࠐΈ‫ ܕ‬Schatten1 ϊϧϜਖ਼ଇԽ࿨‫ ܕ‬Schatten-1 ϊϧϜਖ਼ଇԽAb = arg min2
Ab = arg min |||Y − A|||F + λn |||A|||S1 /1 .

A

A

Tucker-ϥϯΫ͕খ͞ͳςϯιϧΛਪఆ.

s.t.

2

|||Y − A|||F + λn |||A|||S1 /1 ,
A=

K
X
k=1

(k ′ )Ak , kAk kS∞ ≤αp
N/nk ′ (∀k ′ 6= k).
KϥϯΫͷখ͞ͳํ޲Λ‫͚ͭݟ‬Δɽ

−→

A
A(1)

A

A(2)

A1

=
↓

A(3)

A2

+
↓

(1)
A1

A3

+
↓

(2)
A2

(3)

A3

53 / 95ऩଋϨʔτղੳ

54 / 95

ϕΠζਪఆ
n

1X
(Yi − hXi , Ai)2 + pen(A).
A∈RM1 ×M2 ×···×MK n
min

i=1





࿨‫( ܕ‬Tomioka et al., 2011)1b − A∗ |||2 ≤ C
|||A
F
N
n



√
1 PK
k=1 ( Mk +Kp৞ΈࠐΈ‫( ܗ‬Tomioka and Suzuki, 2013):
1
b − A∗ |||2 ≤ C
|||A
F
N
n



2  P√ 2
K
1
N/Mk )
rk
k=1
K

ϕΠζ๏Ͱ௿ϥϯΫςϯιϧਪఆΛߦͬͨ࣌ͷ౷‫ܭ‬తੑ࣭Λௐ΂ΔɽΑΓগͳ͍৚݅Ͱ࠷దϨʔτΛୡ੒.

2p√maxk ( Mk + N/Mk ) mink rk

Square deal (Mu et al., 2014):min{
1kÂ − A∗ k22 ≤ C
MQk∈I1 rk ,nQk∈I2 rk }Qk∈I1 Mk +Q

k∈I2 Mkͨͩ͠ɼI1 ͱ I2 ͸ΠϯσοΫε {1, . . . , K } ͷ೚ҙͷ෼ׂ.
‫ྔࢉܭ‬: গͳ͍.
౷‫ܭ‬తੑ࣭: վળՄೳ. ˠ ϕΠζਪఆ๏,

55 / 95

56 / 95ϕΠζࣄ‫ޙ‬෼෍ͷऩଋϛχϚοΫε࠷దੑkA∗ kmax,2 ≤ Rσp ΛԾఆ.
(ਅͷςϯιϧ͸ࣄલ෼෍ͷ୆ʹ‫·ؚ‬Ε͍ͯΔ)
ϛχϚοΫε࠷దϦεΫɿͲΜͳਪఆྔ Ͱ΋௒͑ΒΕͳ͍ϦεΫɽ

Theorem
Hd (R) := A ∈ RM1 ×···×MK | CP-ϥϯΫ d, kAkmax,2 ≤ R .

͋Δ n, {Mk }k ͱ͸ؔ܎ͳ͍ఆ਺ C ͕ଘࡏͯ͠ɼ


Z
1
∗ 2
kA
−
A
k
(‫ݻ‬ఆσβΠϯ)EY1:n |X1:ndΠ(A|X
,
Y
)
1:n
1:n
n
2σ 2
PK


#

d( k=1 Mk )σK √1 ∨ R 2 log K ξp nR K .
≤C
n


Z
1
kA − A∗ k2L2 dΠ(A|X1:n , Y1:n )(ϥϯμϜσβΠϯ)EY1:n |X1:n
2
2σ
PK



d( k=1 Mk ) #σK √1 ∨ R 2(K +1) log K ξp nR K .
≤Cn(ϥϯΫ d ͷςϯιϧͷू߹)

Theorem
Hd (R) ্ͷςϯιϧਪఆྔͷϛχϚοΫε࠷దϨʔτ͸ҎԼͰ༩͑ΒΕΔ:
min

max

b A∗ ∈Hd (R)A

E[kAb − A∗ k2L2 ] &d(M1 + · · · + MK ).
n

˞ ઌͷऩଋϨʔτ͸ log ߲Λআ͍ͯϛχϚοΫε࠷దϨʔτΛୡ੒ɽ͜ͷϨʔτ͸σβΠϯߦྻʹ ‫ڧ‬ತੑΛԾఆͤͣ ʹಘΒΕΔɽ

57 / 95

ತਖ਼ଇԽख๏ͱͷൺֱ58 / 95‫ࠩޡ‬ͷεέʔϧ






VHWWLQJVHWWLQJVHWWLQJVHWWLQJVHWWLQJ

































$FWXDOLQVDPSOHDFF







VHWWLQJ%D\HV
VHWWLQJ&RQYH[
VHWWLQJ%D\HV
VHWWLQJ&RQYH[



2XWRIVDPSOHDFF

,QVDPSOHDFF







VHWWLQJ%D\HV
VHWWLQJ&RQYH[
VHWWLQJ%D\HV
VHWWLQJ&RQYH[



6FDOHGLQVDPSOHDFF











Q








Q

V















Q









3

ߴ࣍‫ݩ‬ઢ‫ܗ‬ճ‫ؼ‬ͷ‫ݕ‬ఆ5

εύʔεਪఆͷ࠷దԽख๏





Q







V

actual accuracyPKd( k=1 Mk )/n

60 / 95όΠΞεআ‫ʹڈ‬ΑΔํ๏ΞΠσΟΞɿLasso ਪఆྔ β̂ ͔ΒόΠΞεΛআ‫ڈ‬.
(van de Geer et al., 2014, Javanmard and Montanari, 2014)εύʔεਪఆͷཧ࿦n ≫ p ͷཧ࿦n ≪ p ͷཧ࿦ΑΓߴ౓ͳτϐοΫ

4



Figure: ‫ݻ‬ఆσβΠϯ: The scaled predictive accuracy (left) and the actual predictive
accuracy (right) against the number of samples.

Outline

͍Ζ͍Ζͳεύʔεਖ਼ଇԽ









59 / 95

2





V

scaled accuracy =εύʔεਪఆͷϞσϧ







V

Figure: ϕΠζਪఆ๏ͱತਖ਼ଇԽ๏ (࿨‫ ܕ‬Schatten-1 ϊϧϜ) ͱͷൺֱ.

1




M ͕ (X ⊤ X )−1 ͳΒɼ⊤β̃ = β̂ + MX (Y − X β̂)∗⊤β̃ = β + (X X )

−1




⊤

X ǫ.

ˠ όΠΞεͳ͠ɼ (઴ۙ) ਖ਼‫ن‬ɽ໰୊఺: p ≫ n ͷͱ͖ɼX ⊤ X ͸ඇՄ‫ٯ‬ɽ61 / 95

62 / 95

M ͷ‫ٻ‬Ίํ:M ͷ‫ٻ‬Ίํ:b ⊤ − I |∞ .
|ΣM

min

M∈Rp×pM∈Rp×p(| · |∞ ͸த਎ΛϕΫτϧͱΈͳͨ͠ແ‫ݶ‬େϊϧϜ)

Theorem (Javanmard and Montanari (2014))2

ǫi ∼ N(0, σ ) (i.i.d.) ͱ͢Δɽ√Theorem (Javanmard and Montanari (2014))b ⊤ ),Z ∼ N(0, σ 2 M ΣM√

b − I )(β ∗ − β̂).
n(M Σp·ͨɼX ͕ϥϯμϜͰ෼ࢄ‫ڞ‬෼ࢄߦྻ͕ਖ਼ఆͳ࣌ɼλn = cσ log(p)/n ͱ͢Δͱɼ√k∆k∞ = Op d log(p).
nn(β̃ − β ∗ ) = Z + ∆,b ⊤ − I |∞ .
|ΣM

min

(| · |∞ ͸த਎ΛϕΫτϧͱΈͳͨ͠ແ‫ݶ‬େϊϧϜ)∆=√n(β̃ − β ∗ ) = |{z}Z +ਖ਼‫ن‬෼෍∆|{z}

X ͕ඇՄ‫͋Ͱٯ‬Δ͜ͱʹΑΔ࢒ΓΧε৚͕݅ྑ͍࣌ 0 ΁ऩଋ√˞ n ≫ d 2 log2 (p) ͳΒ͹ ∆ ≈ 0 Ͱɼ n(β̃ − β ∗ ) ͸΄΅ਖ਼‫ن‬෼෍ʹै͏ɽˠ ৴པ۠ؒͷߏங΍‫ݕ‬ఆ͕Ͱ͖Δɽ√˞ n ≫ d 2 log2 (p) ͳΒ͹ ∆ ≈ 0 Ͱɼ n(β̃ − β ∗ ) ͸΄΅ਖ਼‫ن‬෼෍ʹै͏ɽˠ ৴པ۠ؒͷߏங΍‫ݕ‬ఆ͕Ͱ͖Δɽ

63 / 95‫ڞ‬෼ࢄ‫ݕ‬ఆ౷‫( ྔܭ‬Lockhart et al., 2014)
0

2

4

6

8

10

10

0

500

1000

1500

2000

2500

3000

0
−600

−400

−200

Coefficients

200

400

600

਺஋࣮‫ݧ‬

63 / 95

L1 Norm(a) ਓ޻σʔλʹ͓͚Δ 95%৴པ۠ؒ.
(n, p, d) = (1000, 600, 10).

(b) ਓ ޻ σ ʔ λ ʹ ͓ ͚ Δ p ஋ ͷ CDF.
(n, p, d) = (1000, 600, 10).

ਤ͸ Javanmard and Montanari (2014) ͔ΒҾ༻ɽ

64 / 95‫ڞ‬෼ࢄ‫ݕ‬ఆ౷‫( ྔܭ‬Lockhart et al., 2014)
2

4

6

8

10

Outline101εύʔεਪఆͷϞσϧ

2

͍Ζ͍Ζͳεύʔεਖ਼ଇԽ3

εύʔεਪఆͷཧ࿦n ≫ p ͷཧ࿦n ≪ p ͷཧ࿦ΑΓߴ౓ͳτϐοΫ

4ߴ࣍‫ݩ‬ઢ‫ܗ‬ճ‫ؼ‬ͷ‫ݕ‬ఆ5

εύʔεਪఆͷ࠷దԽख๏

0
−600

−400

−200

Coefficients

200

400

600

0

65 / 95

0

500

1000

1500

2000

2500

3000

L1 Norm

J = supp(β̂(λk )), J ∗ = supp(β ∗ ),β̃(λk+1 ) :=argminkY − XJ βJ k2 + λk+1 kβJ k1 .
β:βJ ∈R|J| ,βJ c =0

J ∗ ⊆ J ͳΒ͹ (ͭ·Γ βj∗ = 0)ɼ
dTk = hY , X β̂(λk+1 )i − hY , X β̃(λk+1 )i /σ 2 −→ Exp(1)(n, p → ∞).
65 / 95

66 / 95εύʔεਪఆʹ͓͚Δ࠷దԽͷ໰୊ҙࣝ

R(β) =

εύʔεਪఆʹ͓͚Δ࠷దԽͷ໰୊ҙࣝ

nXℓ(yi , xi⊤ β) + ψ(β)| {z }
ਖ਼ଇԽ߲}|i=1 {zR(β) =

f (β):ϩεؔ਺nXℓ(yi , xi⊤ β) + ψ(β)| {z }
ਖ਼ଇԽ߲}|i=1 {zf (β):ϩεؔ਺= f (β) + ψ(β)= f (β) + ψ(β)ψ ͕ઑ͍ͬͯΔˠඍ෼ෆՄೳɽઑ͍ͬͯΔؔ਺ͷ࠷దԽ͸ ೉͍͠ɽf ͸ͳΊΒ͔ͳ৔߹͕ଟ͍ɽψ ͷߏ଄Λར༻ ͢Ε͹ɼ͔͋ͨ΋ R ͕ͳΊΒ͔ Ͱ͋Δ͔ͷΑ͏ʹ࠷దԽՄೳɽψ ͕ઑ͍ͬͯΔˠඍ෼ෆՄೳɽઑ͍ͬͯΔؔ਺ͷ࠷దԽ͸ ೉͍͠ɽf ͸ͳΊΒ͔ͳ৔߹͕ଟ͍ɽψ ͷߏ଄Λར༻ ͢Ε͹ɼ͔͋ͨ΋ R ͕ͳΊΒ͔ Ͱ͋Δ͔ͷΑ͏ʹ࠷దԽՄೳɽయ‫ྫܕ‬ɿL1 ਖ਼ଇԽ ψ(β) = C

67 / 95

࠲ඪ߱Լ๏Pp

j=1 |βj | ˠ ࠲ඪ͝ͱʹ෼͔Ε͍ͯΔ.

Ұ࣍‫ݩ‬ͷ࠷దԽ minb {(b − y )2 + C |b|} ͸ ؆୯.

67 / 95࠲ඪ߱Լͷ஫ҙ఺࠲ඪ߱Լ๏ͷखॱ
1 ࠲ඪ j ∈ {1, . . . , p} Λ ԿΒ͔ͷํ๏ Ͱબ୒ɽ2 j ൪໨ͷ࠲ඪ βj Λߋ৽ɽʢҎԼ͸ߋ৽ํ๏ͷྫʣ
(k+1)

βj

(k)

(k)

← argminβj R([β1 , . . . , βj , . . . , βp ]).

(β (k) )gj = ∂f ∂β
ͱͯ͠ɼ
j
(k+1)
(k)
βj
← argminβj hgj , βj i + ψj (βj ) + η2k kβj − βj k2 .

failure࠲ඪΛҰͭͣͭͰ͸ͳ͘ෳ਺‫ݸ‬બͿ͜ͱ΋ଟ͍: ϒϩοΫ࠲ඪ߱Լ๏ɽ

success

ࠨଆ: ࠲ඪ߱Լ͕ࣦഊɽ߱Լํ޲͕ͳ͍ɽ

࠲ඪ͸͋ΔϧʔϧʹैͬͯબΜͩΓɼϥϯμϜʹબΜͩΓ͢Δɽ

࠲ඪ߱ԼΛ੒ޭͤ͞Δʹ͸, ໨తؔ਺͸߱Լํ޲͕ͳͯ͘͸͍͚ͳ͍. ཧ૝Ppతʹ͸࠲ඪ͝ͱʹ෼཭ f (x) = j=1 fj (xj ).
68 / 95

࠲ඪ߱Լ๏ͷऩଋ69 / 95େ‫ن‬໛σʔλʹ͓͚Δ࠲ඪ߱Լ๏

minx {P(x)} = minx {f (x) + ψ(x)} = minx {f (x) +Hydra: ฒྻ෼ࢄ‫ࢉܭ‬Λ༻͍ͨ࠲ඪ߱Լ๏ (Richtárik and Takáč, 2013, Fercoq
et al., 2014).

Pp

j=1 ψj (xj )}.

Ծఆ: f ͸ ֤࠲ඪ͝ͱ ʹ γ-ฏ‫∂|( ׈‬xj f (x) − ∂xj f (x + aej )| ≤ γa)αΠΫϦοΫͳߋ৽ (Saha and Tewari, 2013, Beck and Tetruashvili, 2013)
(0)

∗ 2

P(x (t) ) − R(x ∗ ) ≤ γpkx 2t−x k = O(pγ/t).
ϥϯμϜͳબ୒ (Nesterov, 2012, Richtárik and Takáč, 2014)
Ճ଎ͳ͠: O(pγ/t).
Nesterov ͷՃ଎: O(γ(p/t)2 ) (Fercoq and Richtárik, 2013).
f ͕ α-‫ڧ‬ತ: O(exp(−C (α/γ)t/p)).
pf ͕ α-‫ڧ‬ತ + Ճ଎: O(exp(−C α/γt/p)) (Lin et al., 2014).

࠲ඪ͸ϥϯμϜʹબ୒͢Ε͹ྑ͍ɽେ‫ن‬໛ Lasso (p = 5 × 108 , n = 109 ) ʹ͓͚Δ Hydra ͷ‫( ཰ޮࢉܭ‬Richtárik andTakáč, 2013)ɽ128 ϊʔυɼ4,096 ίΞɽ༗༻ͳαʔϕΠ࿦จ: Wright (2015).

70 / 95

71 / 95ۙ઀ޯ഑๏‫ܕ‬ख๏ۙ઀ࣸ૾ͷྫ: L1 ਖ਼ଇԽ
f (β) +ψ(β)
|{z}



1
prox(q|C k · k1 ) = arg min C kxk1 + kx − qk22xઢ‫ࣅۙܗ‬

Pk

gk ∈ ∂f (β (k) ), ḡk = k1

τ =1 gτ .

ۙ઀ޯ഑๏:= (sign(qj ) max(|qj | − C , 0))j .

→ Soft-thresholding ؔ਺. ղੳղ!

noηkβ (k+1) = arg min gk⊤ β + ψ(β) + kβ − β (k) k2 .
2β∈Rpਖ਼ଇԽ૒ରฏ‫ۉ‬๏ (Xiao, 2009, Nesterov, 2009):noηkβ (k+1) = arg min ḡk⊤ β + ψ(β) + kβk2 .
p
2
β∈R


1
‫ͳͱݤ‬Δ‫ࢉܭ‬͸ۙ઀ࣸ૾: prox(q|ψ) := arg min ψ(x) + kx − qk2 .
2x
L1 ਖ਼ଇԽͳΒ؆୯ʹ‫͖Ͱࢉܭ‬Δ (Soft-thresholding ؔ਺)ɽψ ͕ྼϞδϡϥؔ਺ͷ Lovasz ֦ுɿྼϞδϡϥੑΛ࢖ͬͨޮ཰త࠷దԽ
72 / 95

ۙ઀ޯ഑๏‫ܕ‬ख๏ͷऩଋϨʔτ

f ͷੑ࣭
‫ڧ‬ತ
ඇ‫ڧ‬ತ

1

‫׈‬Β͔
p
exp(− α/Lk)

73 / 95֦ுϥάϥϯδΞϯ‫ܕ‬ख๏

min f (β) + ψ(β)ඇ‫׈‬Β͔

1
k2

β

⇔

1
k
1
√
k

min f (x) + ψ(y ) s.t. x = y .
x,y࠷దԽͷ೉͠͞Λ ෼཭ɽ֦ுϥάϥϯδΞϯ: L(x, y , λ) = f (x) + ψ(y ) − λ⊤ (y − x) + ρ2 ky − xk2 .

‫׈‬Β͔ͳ৔߹ɼNesterov ͷՃ଎๏Λ࢖ͬͨ࣌ͷऩଋϨʔτΛ͍ࣔͯ͠Δ (Nesterov, 2007, Zhang et al., 2010)ɽ

৐਺๏ (Hestenes, 1969, Powell, 1969, Rockafellar, 1976)2Ճ଎๏Λ࢖Θͳ͚Ε͹ɼͦΕͧΕ exp(−(α/L)k), k1 ʹͳΔɽ3্ͷΦʔμʔ͸ޯ഑৘ใͷΈΛ༻͍Δํ๏ (First order method) ͷதͰ࠷దɽ

1 (x (k+1) , y (k+1) ) = argminx,y L(x, y , λ(k) ).
2 λ(k+1) = λ(k) − ρ(y (k+1) − x (k+1) ).

x, y Ͱͷಉ࣌࠷దԽ͸΍΍໘౗ ˠ ަ‫޲ํޓ‬৐਺๏ɽ

74 / 95ަ‫޲ํޓ‬৐਺๏

75 / 95

֬཰త࠷దԽ
min f (x) + ψ(y ) s.t. x = y .
x,yρL(x, y , λ) = f (x) + ψ(y ) − λ⊤ (y − x) + ky − xk2 .
2αϯϓϧ਺ͷଟ͍େ‫ن‬໛σʔλ Ͱ༗༻ɽҰճͷߋ৽ʹ͢΂ͯͷαϯϓϧΛಡΈࠐ·ͳ͍Ͱ΋େৎ෉.

 ΦϯϥΠϯ‫ܕ‬
FOBOS (Duchi and Singer, 2009)ަ‫޲ํޓ‬৐਺๏ (Gabay and Mercier, 1976)
ρx= arg min f (x) + λx + ky (k) − xk22xρy (k+1) = arg min ψ(y ) − λ(k)⊤ y + ky − x (k+1) k2 (= prox(x (k+1) + λ(k) /ρ|ψ/ρ))
2
y
(k+1)

(k)⊤

RDA (Xiao, 2009) όον‫ܕ‬
SVRG (Stochastic Variance Reduced Gradient) (Johnson and Zhang, 2013)
SDCA (Stochastic Dual Coordinate Ascent) (Shalev-Shwartz and Zhang, 2013)
SAG (Stochastic Averaging Gradient) (Le Roux et al., 2013)

λ(k+1) = λ(k) − ρ(y (k+1) − x (k+1) )x, y ͷಉ࣌࠷దԽ͸ަ‫࠷ʹޓ‬దԽ͢Δ͜ͱͰճආɽy ͷߋ৽͸ۙ઀ࣸ૾ɽL1 ਖ਼ଇԽͷΑ͏ͳ৔߹͸؆୯ɽߏ଄తਖ਼ଇԽ΁ͷ֦ு΋༰қɽ࠷దղʹऩଋ͢Δอূ͋ΓɽҰൠతʹ͸ O(1/k) (He and Yuan, 2012), ‫ڧ‬ತͳΒ͹ઢ‫ܗ‬ऩଋ (Deng and Yin,
2012, Hong and Luo, 2012)ɽ

֬཰తަ‫޲ํޓ‬৐਺๏: Suzuki (2013), Ouyang et al. (2013), Suzuki (2014).

76 / 95

77 / 95֬཰త࠷దԽͷ‫ج‬ຊํ਑ΦϯϥΠϯ‫ܕ‬ख๏min EZ ∼P(Z ) [ℓ(Z , w )] + ψ(w )n

R(w ) =

1Xℓ(zi , w ) + ψ(w )
n
i=1
|
{z
}

w

1

ॏ͍

2

େ͖ͳ໰୊Λ෼ׂͯ͠‫ݸ‬ผʹॲཧσʔλ {zi }ni=1 ͔ΒҰͭʢ΋͘͠͸ʣগ਺ΛϥϯμϜʹநग़ύϥϝʔλ w Λߋ৽˞֤ߋ৽Ͱ O(1) (΋͘͠͸ O(p)) ͷ‫ྔࢉܭ‬.

3

ϥϯμϜʹ zt ∼ P(Z ) Λੜ੒.
Pt
gt ∈ ∂w ℓ(zt , w (t−1) ), ḡt = 1t τ =1 gτ .

SDA (Stochastic Dual Averaging):
1
w (t) = arg min ḡt⊤ w + ψ̃(w ) +kw k2 .
2ηt
w ∈Rp



ΦϯϥΠϯ‫ܕ‬ɿ√SGD, SDA˞ޯ഑͸̍ͭͷσʔλͷΈͰ‫ࢉܭ‬

SGD (Stochastic Gradient Descent):
1kw − w (t−1) k2 .
w (t) = arg min gt⊤ w + ψ(w ) +
2ηt
w ∈Rp

[Ծఆ] E[kgt k2 ] ≤ G 2 , E[kxt − x ∗ k2 ] ≤ D 2 (∀t) (SDA ͸ೋͭ໨ͷԾఆΛ؇ΊΒΕΔ)
P (t)
2GR
w
(ඇฏ‫׈‬, ඇ‫ڧ‬ತ) Polyak-Ruppert ฏ‫ۉ‬Խ w̄ (T ) = tTR(w̄ (T ) ) ≤ √TP
2G 2
tw (t)
R(w̄ (T ) ) ≤(ඇฏ‫׈‬, ‫ڧ‬ತ) ଟ߲ࣜฏ‫ۉ‬Խ w̄ (T ) = T (Tt +1)/2µT

Ұൠ: O(1/ T )‫ڧ‬ತ: O(1/T )όον‫ܕ‬ɿSVRG, SAG, SDCA
T
exp(− n+λ/γ)
78 / 95όον‫཰֬ܕ‬త࠷దԽख๏

79 / 95

໰୊ઃఆP(x) = n1|αϯϓϧαΠζ͸‫ݻ‬ఆ (ΦϯϥΠϯ‫ܕ‬͸͔࣍Β࣍΁ͱσʔλΛಡΈࠐΉ)

1
n

n
X

ℓ(zi , w ) + ψ(w )

Ծఆ:

i=1

Pn

i=1 ℓi (x) + ψ(x)

{z

}

ฏ‫׈‬

| {z }‫ڧ‬ತ

ℓi : ଛࣦؔ਺͸ γ-ฏ‫׈‬.
(k∇ℓi (x) − ∇ℓi (x ′ )k ≤ Lkx − x ′ k)ψ: ਖ਼ଇԽؔ਺͸ λ-‫ڧ‬ತ. (ψ(x) − λ2 kxk2 √͕ತؔ਺)య‫ܕ‬తʹ͸ λ = O(1/n) ·ͨ͸ O(1/ n).

୅දతͳ̏ͭͷख๏֬཰తฏ‫ޯۉ‬഑๏
Stochastic Average Gradient descent, SAG(Le Roux et al., 2012, Schmidt et al., 2013, Defazio et al., 2014)ྫ:֬཰త෼ࢄॖখޯ഑๏
Stochastic Variance Reduced Gradient descent, SVRG

ଛࣦؔ਺

ਖ਼ଇԽؔ਺

ฏ‫׈‬Խώϯδଛࣦ

(Johnson and Zhang, 2013, Xiao and Zhang, 2014)

L2 ਖ਼ଇԽ

ϩδεςΟοΫଛࣦ֬཰త૒ର࠲ඪ߱Լ๏
Stochastic Dual Coordinate Ascent, SDCAΤϥεςΟοΫωοτਖ਼ଇԽψ̃(x) + λkxk2(Shalev-Shwartz and Zhang, 2013)- SAG ͱ SVRG ͸ ओ໰୊ Λղ͘ํ๏.
- SDCA ͸ ૒ର໰୊ Λղ͘ํ๏.

0080 / 95όον‫ܕ‬ख๏ͷಛ৭

81 / 95

֬཰త૒ର࠲ඪ߱Լ๏
૒ର໰୊ ʹ͓͍ͯ֬཰త࠲ඪ߱Լ๏Λద༻ɽ̍ճͷߋ৽ʹ̍σʔλͷΈར༻ (ΦϯϥΠϯ‫ͱܕ‬ಉ͡),ઢ‫ܗ‬ऩଋ (ΦϯϥΠϯ‫ͱܕ‬ҧ͏):૒ରͷ֤࠲ඪ͸֤σʔλ఺ʹରԠɽˠ ʮҰͭͷ࠲ඪΛߋ৽ʯ = ʮҰͭͷσʔλ఺Λ‫؍‬ଌͯ͠ߋ৽ʯ‫ ࠩޡ‬ǫ ·Ͱʹඞཁͳ൓෮਺:




γ
n + γ/λT ≥C n+.
log
λǫ

T > (n + γ/λ)log(1/ǫ)ճͷߋ৽Ͱ ǫ ‫ࠩޡ‬Λୡ੒ɽͨͩ͠ γ-ฏ‫ͳ׈‬ଛࣦͱ λ-‫ڧ‬ತͳਖ਼ଇԽΛԾఆ.
௨ৗͷޯ഑๏ (֤൓෮Ͱશσʔλ࢖༻) ͷ‫ྔࢉܭ‬:ˠ ઢ‫ܗ‬ऩଋɽೋॏϧʔϓ͸ඞཁͳ͍ɽ
˞ଞͷόον‫ܕ‬ख๏Ͱ͋Δ SVRG ͸ೋॏϧʔϓ

T > nγ/λ log(1/ǫ)

[௨ৗ]



n(γ/λ)log(1/ǫ) ˠ


[֬཰త]

(n + γ/λ)log(1/ǫ)


82 / 95

Ծఆ:ℓ(zi , ·) ͸ γ-ฏ‫ ↔( ׈‬ℓ∗ (zi , ·) ͸ 1/γ-‫ڧ‬ತ)ψ ͸ λ-‫ڧ‬ತ (↔ ψ ∗ ͸ 1/λ-ฏ‫)׈‬83 / 95ϧδϟϯυϧม‫׵‬ྫ૒ରۭؒ (ޯ഑ͷۭؒ) Ͱఆٛ͞Εͨؔ਺.

Definition (ϧδϟϯυϧม‫)׵‬

ೋ৐ଛࣦ

f (x)
1 2
x
2

(ඇತ͔΋͠Εͳ͍) ؔ਺ f : Rp → R̄ ʹର͠ɼͦͷ‫ڞ‬໾ؔ਺͸࣍ͷΑ͏ʹఆٛ͞ΕΔ:f ∗ (y ) := sup {hx, y i − f (x)}.

ώϯδଛࣦ

max{1 − x, 0}x∈Rp

f ͔Β f ∗ ΁ͷม‫׵‬Λϧδϟϯυϧม‫Ϳݺͱ׵‬.
˞ ‫ڞ‬໾ؔ਺͸ತؔ਺ɽϩδεςΟοΫଛࣦlog(1 + exp(−x))

L1 ਖ਼ଇԽ

kxk1
p
j=1 |xj |(p > 1)y∞f ∗ (y )1 2
y2(−1 ≤ y ≤ 0),(otherwise).

(−y ) log(−y ) + (1 + y ) log(1 + y )∞((−1 ≤ y ≤ 0),(otherwise).

0(maxj |yj | ≤ 1),∞ (otherwise).
p
Pd
p−1
p−1
p |yj |
j=1

Pd

Lp ਖ਼ଇԽ˞ ತؔ਺ f ʹର͠ f ∗ ͸ͦͷ ཪͷ࢟ɽ

(

(

p p−1

f(x)
line with gradient y
0

1

f(x*)

0
x*

x

L1 ϊϧϜ

0f*(y)ϩδεςΟοΫ

ͦͷ૒ର

ͦͷ૒ର

84 / 95૒ର໰୊֬཰త૒ର࠲ඪ߱Լ๏

∃fi : R → R ͳΔؔ਺͕͋ͬͯ ℓ(zi , x) = fi (ai⊤ x) ͱॻ͚ΔͱԾఆ.
A = [a1 , . . . , an ] ͱ͢Δ.

( n
)
1X
(Primal)inf pfi (ai⊤ x) + ψ(x)
x∈R
n
i=1



85 / 95[Fenchel ͷ૒ରఆཧ]



y ∈R


(Dual)

inf

y ∈Rn

(


)
n
1
1X ∗
∗
fi (yi ) + ψ − Ay
n
n
i=1
{z
}
|
{z
}
|
‫ڧ‬ತ





2
3

Pick up an index i ∈ {1, . . . , n} uniformly at random.
Calculate x (t−1) = ∇ψ ∗ (−A⊤ y (t−1) /n).
Update the i-th coordinate yi so that the objective function is decreased:
(t)



• yi



n
o
1
(t−1) 2∈ argmin fi ∗ (yi ) − hx (t−1) , ai yi i + kyi − yi
k
2η
yi ∈R
(t−1)

= prox(yi•ฏ‫׈‬ͳ͓࣍ͷࣜΛ༻͍ͨ:PPf (α) = ni=1 fi (αi ) ʹର͠ f ∗ (β) = ni=1 fi ∗ (βi ).

Iterate the following for t = 1, 2, . . .
1

inf {f (A⊤ x) + nψ(x)} = − inf n {f ∗ (y ) + nψ ∗ (−Ay /n)}x∈Rp֬཰త૒ର࠲ඪ߱Լ๏ (Shalev-Shwartz and Zhang, 2013)

(t)
(t−1)
yj =yj+ ηai⊤ x (t−1) |ηfi ∗ ),(for j 6= i).

x (t) ͸ओ໰୊ͷղʹͳΔҰճ͝ͱͷ‫ྔࢉܭ‬͸খ͍͞ψ̃(x) = nψ(x) ʹର͠ ψ̃ ∗ (y ) = nψ ∗ (y /n).

86 / 95όον‫཰֬ܕ‬త࠷దԽख๏ͷ·ͱΊ

Method
ओ/૒ର
ϝϞϦޮ཰
ͦͷଞ

֤छख๏ͷੑ࣭
SDCA
SVRG
૒ର
ओ
✓
✓
ℓi (β) = fi (xi⊤ β) ೋॏϧʔϓ

87 / 95֬཰తަ‫޲ํޓ‬৐਺๏ઢ‫੍ܗ‬໿෇͖૒ର໰୊
Let A = [a1 , a2 , . . . , an ] ∈ Rp×n .
n
o
n1 X
min
fi (ai⊤ w ) + ψ(B ⊤ w )
w
n
i=1
 
n
o
n1 X
y
Ax + By = 0⇔ minfi ∗ (xi ) + ψ ∗nx∈Rn ,y ∈Rd n

SAGA
ओ
△
ฏ‫ͳ׈‬ਖ਼ଇԽ

(Primal)(Dual)i=1‫ ࠩޡ‬ǫ ·Ͱͷ‫ྔࢉܭ‬:γ
n+log(1/ǫ).
λۙ઀ࣸ૾ͷ‫͠ࢉܭ‬΍͍͢ ψ ͱ ઢ‫ܗ‬ม‫ ׵‬B ⊤ ͷ૊ΈͰଟ͘ͷਖ਼ଇԽ߲ΛΧόʔɿߏ଄తਖ਼ଇԽɽ
֬཰తަ‫޲ํޓ‬৐਺๏ = ֬཰త࠷దԽ + ަ‫޲ํޓ‬৐਺๏ΦϯϥΠϯ‫ܕ‬: Suzuki (2013), Ouyang et al. (2013)όον‫( ܕ‬૒ର࠲ඪ߱Լ): SDCA-ADMM (Suzuki, 2014)
r 


nγ
T =O
n+
log(1/ǫ) .
λՃ଎๏΋͋Δ (Catalyst (Lin et al., 2015), Acc-SDCA (Lin et al., 2014)):
r 

nγ
n+
log(1/ǫ)λˠ Ճ଎๏ͱಉ͡ऩଋϨʔτ.
88 / 95

89 / 95ߏ଄తਖ਼ଇԽͷྫߏ଄తਖ਼ଇԽͷྫ: (ҰൠԽ) Fused Lasso

ψ(β) = Cॏෳ͋Γ ͷάϧʔϓਖ਼ଇԽX(i,j)∈E

Fused Lasso ਖ਼ଇԽ (Tibshirani et al., 2005, Jacob et al., 2009).

|βi − βj |.

(Tibshirani et al. (2005), Jacob et al. (2009))

௿ϥϯΫςϯιϧਖ਼ଇԽ (Signoretto et al., 2010; Tomioka et al., 2011).

Robust PCA (Candés et al., 2009).
ͲΕ΋ۙ઀ࣸ૾ͷ‫͠ࢉܭ‬΍͍ؔ͢਺ ψ ͱߦྻ B Λ༻͍ͯψ(B ⊤ x) = ψ̃(x)ͷΑ͏ʹॻ͚Δɽ
Fused lasso ʹΑΔҨ఻ࢠσʔλղੳ (Tibshirani andTV σϊΠδϯά (Chambolle ‘04)

Taylor ‘11)

90 / 95֬཰తަ‫޲ํޓ‬৐਺๏

91 / 95

୯७Խͨ͠ํ๏

֬཰త࠲ඪ߱Լ‫޲ํޓަܕ‬৐਺๏ (Suzuki, 2014)
Q = ρ(ηB Id − B ⊤ B), GI ,I = ρ(ηZ ,I I|I | − ZI⊤ ZI ),Split the index set {1, . . . , n} into K groups (I1 , I2 , . . . , IK ).
For each t = 1, 2, . . .
Choose k ∈ {1, . . . , K } uniformly at random, and set I = Ik .
ny (t) ← arg min nψ ∗ (y /n) − hw (t−1), Ax (t−1) +By iyͱ͢Ε͹ɼprox(q|ψ) + prox(q|ψ ∗ ) = q Λ༻͍ͯߋ৽ࣜΛ୯७ԽͰ͖Δɽ

୯७Խͨ͠ SDCA-ADMM⊤

B
For q (t) = y (t−1) + ρη{w (t−1) − ρ(Zx (t−1) + By (t−1) )}, let
B

o

1
ρ
+ kAx (t−1) + By k2 + ky − y (t−1) k2Q ,
2
n2P
(t)
(t−1)
∗
, AI xI + By (t) ixI ← arg mini∈I fi (xi ) − hw

y (t) ← q (t) − prox(q (t) |nψ(ρηB · )/(ρηB )),(t)

For pI

xI

o
ρ
1
(t−1)
(t−1) 2+ kAI xI +A\I x\I +By (t) k2 + kxI − xI
kGI ,I ,22
w (t) ←w (t−1) − γρ{n(Ax (t) + By (t) )

(t−1)

= xI

Z⊤

+ ρηIZ ,I {w (t−1) − ρ(Zx (t−1) + By (t) )}, let(t)xi− (n − n/K )(Ax (t−1) + By (t−1) )}.

(t)← prox(pi |fi ∗ /(ρηZ ,I )) (∀i ∈ I ).

⋆ x ͷߋ৽͸ฒྻԽՄೳɽy ͷߋ৽͸ ψ ʹؔ͢Δۙ઀ࣸ૾ (‫͠ࢉܭ‬΍͍͢)ɽ

where Q, G are some appropriate positive semidefinite matrices.
92 / 95֬཰తަ‫޲ํޓ‬৐਺๏

93 / 95·ͱΊ༷ʑͳεύʔεϞσϦϯά
L1 ਖ਼ଇԽ
άϧʔϓਖ਼ଇԽ
τϨʔεϊϧϜਖ਼ଇԽ

Empirical Risk

RDA
23*í$'00
5'$í$'00
2/í$'00%DWFKí$'00
6'&$í$'00

Lasso ͷ઴ۙతৼΔ෣͍઴ۙ෼෍
Adaptive Lasso ͷΦϥΫϧϓϩύςΟ
੍‫ݻݶ‬༗஋৚݅ˠ kβ̂ − β ∗ k2 = Op (d log(p)/n)ΑΓਐΜͩ࿩୊

εύʔεՃ๏Ϟσϧ௿ϥϯΫςϯιϧਪఆ‫ݕ‬ఆόΠΞεআ‫ڈ‬๏ɼ‫ڞ‬෼ࢄ‫ݕ‬ఆ౷‫ྔܭ‬࠷దԽख๏CPU time (s)

࠲ඪ߱Լ๏
ۙ઀ޯ഑๏
(ަ‫ )޲ํޓ‬৐਺๏֬཰త࠷దԽख๏ˠେ‫ن‬໛σʔλʹ͓͚Δ࠷దԽͰ༗༻
94 / 95

95 / 95

J. Aflalo, A. Ben-Tal, C. Bhattacharyya, J. S. Nath, and S. Raman. Variable
sparsity kernel learning. Journal of Machine Learning Research, 12:565–592,
2011.

J. Bennett and S. Lanning. The netflix prize. In Proceedings of KDD Cup andWorkshop 2007, 2007.

P. Alquier and K. Lounici. PAC-Bayesian bounds for sparse regression estimation
with exponential weights. Electronic Journal of Statistics, 5:127–145, 2011.
T. Anderson. Estimating linear restrictions on regression coefficients for
multivariate normal distributions. Annals of Mathematical Statistics, 22:
327–351, 1951.

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.
P. Bühlmann and S. van de Geer. Statistics for high-dimensional data. Springer,
2011.
F. Bunea, A. Tsybakov, and M. Wegkamp. Aggregation for gaussian regression.
The Annals of Statistics, 35(4):1674–1697, 2007.

A. Argyriou, C. A. Micchelli, M. Pontil, and Y. Ying. A spectral regularization
framework for multi-task structure learning. In Y. S. J.C. Platt, D. Koller and
S. Roweis, editors, Advances in Neural Information Processing Systems 20,
pages 25–32, Cambridge, MA, 2008. MIT Press.
F. Bach, G. Lanckriet, and M. Jordan. Multiple kernel learning, conic duality, andthe SMO algorithm. In the 21st International Conference on Machine Learning,
pages 41–48, 2004.
O. Banerjee, L. E. Ghaoui, and A. d’Aspremont. Model selection through sparse
maximum likelihood estimation for multivariate gaussian or binary data. Journalof Machine Learning Research, 9:485–516, 2008.
A. Beck and L. Tetruashvili. On the convergence of block coordinate descent type
methods. SIAM Journal on Optimization, 23(4):2037–2060, 2013.

G. R. Burket. A study of reduced-rank models for multiple prediction, volume 12of Psychometric monographs. Psychometric Society, 1964.
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.
E. Candès and T. Tao. The power of convex relaxations: Near-optimal matrix
completion. IEEE Transactions on Information Theory, 56:2053–2080, 2009.
E. J. Candès and B. Recht. Exact matrix completion via convex optimization.
Foundations of Computational Mathematics, 9(6):717–772, 2009.
E. J. Candes and T. Tao. Decoding by linear programming. Information Theory,
IEEE Transactions on, 51(12):4203–4215, 2005.

95 / 95

E. J. Candes and T. Tao. Near-optimal signal recovery from random projections:
Universal encoding strategies? IEEE Transactions on Information Theory, 52(12):5406–5425, 2006.
A. Dalalyan and A. B. Tsybakov. Aggregation by exponential weighting sharp
PAC-Bayesian bounds and sparsity. Machine Learning, 72:39–61, 2008.
A. Defazio, F. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradientmethod with support for non-strongly convex composite objectives. In
Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger,
editors, Advances in Neural Information Processing Systems 27, pages
1646–1654. Curran Associates, Inc., 2014.
W. Deng and W. Yin. On the global and linear convergence of the generalized
alternating direction method of multipliers. Technical report, Rice University
CAAM TR12-14, 2012.
D. Donoho. Compressed sensing. IEEE Transactions of Information Theory, 52(4):1289–1306, 2006.
D. L. Donoho and J. M. Johnstone. Ideal spatial adaptation by wavelet shrinkage.
Biometrika, 81(3):425–455, 1994.
J. Duchi and Y. Singer. Efficient online and batch learning using forward
backward splitting. Journal of Machine Learning Research, 10:2873–2908, 2009.
J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its
oracle properties. Journal of the American Statistical Association, 96(456),
2001.
95 / 95

95 / 95

O. Fercoq and P. Richtárik. Accelerated, parallel and proximal coordinate descent.
Technical report, 2013. arXiv:1312.5799.
O. Fercoq, Z. Qu, P. Richtárik, and M. Takáč. Fast distributed coordinate descentfor non-strongly convex losses. In Proceedings of MLSP2014: IEEE
International Workshop on Machine Learning for Signal Processing, 2014.
I. E. Frank and J. H. Friedman. A statistical view of some chemometrics
regression tools. Technometrics, 35(2):109–135, 1993.
D. Gabay and B. Mercier. A dual algorithm for the solution of nonlinear
variational problems via finite-element approximations. Computers &Mathematics with Applications, 2:17–40, 1976.
T. Hastie and R. Tibshirani. Generalized additive models. Chapman & Hall Ltd,1999.
B. He and X. Yuan. On the O(1/n) convergence rate of the Douglas-Rachford
alternating direction method. SIAM J. Numerical Analisis, 50(2):700–709, 2012.
M. Hestenes. Multiplier and gradient methods. Journal of Optimization Theory &Applications, 4:303–320, 1969.
F. L. Hitchcock. The expression of a tensor or a polyadic as a sum of products.
Journal of Mathematics and Physics, 6:164–189, 1927a.
F. L. Hitchcock. Multilple invariants and generalized rank of a p-way matrix or
tensor. Journal of Mathematics and Physics, 7:39–79, 1927b.
95 / 95

M. Hong and Z.-Q. Luo. On the linear convergence of the alternating direction
method of multipliers. Technical report, 2012. arXiv:1208.3922.

K. Knight and W. Fu. Asymptotics for lasso-type estimators. The Annals of
Statistics, 28(5):1356–1378, 2000.
T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM
A. J. Izenman. Reduced-rank regression for the multivariate linear model. Journal
Review, 51(3):455–500, 2009.
of Multivariate Analysis, pages 248–264, 1975.
G. Lanckriet, N. Cristianini, L. E. Ghaoui, P. Bartlett, and M. Jordan. Learning
L. Jacob, G. Obozinski, and J.-P. Vert. Group lasso with overlap and graph lasso.
the kernel matrix with semi-definite programming. Journal of Machine Learning
In Proceedings of the 26th International Conference on Machine Learning, 2009.
Research, 5:27–72, 2004.
A. Javanmard and A. Montanari. Confidence intervals and hypothesis testing for
N. Le Roux, M. Schmidt, and F. R. Bach. A stochastic gradient method with anhigh-dimensional regression. Journal of Machine Learning, page to appear,
exponential convergence rate for finite training sets. In F. Pereira, C. Burges,
2014.
L. Bottou, and K. Weinberger, editors, Advances in Neural Information
R. Johnson and T. Zhang. Accelerating stochastic gradient descent using
Processing Systems 25, pages 2663–2671. Curran Associates, Inc., 2012.
predictive variance reduction. In C. Burges, L. Bottou, M. Welling,
N. Le Roux, M. Schmidt, and F. Bach. A stochastic gradient method with an
Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information
exponential convergence rate for strongly-convex optimization with finite
Processing Systems 26, pages
training sets. In Advances in Neural Information Processing Systems 25, 2013.
315–323. Curran Associates, Inc., 2013. URL http://papers.nips.cc/paper/
H. Lin, J. Mairal, and Z. Harchaoui. A universal catalyst for first-order4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.
optimization. Technical report, 2015. arXiv:1506.02186.
pdf.
Q. Lin, Z. Lu, and L. Xiao. An accelerated proximal coordinate gradient method
M. Kloft, U. Brefeld, S. Sonnenburg, P. Laskov, K.-R. Müller, and A. Zien.
and its application to regularized empirical risk minimization. Technical report,
Efficient and accurate ℓp -norm multiple kernel learning. In Advances in Neural
2014. arXiv:1407.1296.
Information Processing Systems 22, pages 997–1005, Cambridge, MA, 2009.
R. Lockhart, J. Taylor, R. J. Tibshirani, and R. Tibshirani. A significance test for
MIT Press.
the lasso. The Annals of Statistics, 42(2):413–468, 2014.
95 / 95

95 / 95

K. Lounici, A. Tsybakov, M. Pontil, and S. van de Geer. Taking advantage ofsparsity in multi-task learning. 2009.
J. Lu, M. Kolar, and H. Liu. Post-regularization confidence bands for highdimensional nonparametric models with local sparsity, 2015. arXiv:1503.02978.
P. Massart. Concentration Inequalities and Model Selection: Ecole d’été deProbabilités de Saint-Flour 23. Springer, 2003.
N. Meinshausen and P. B uhlmann. High-dimensional graphs and variableselection with the lasso. The Annals of Statistics, 34(3):1436–1462, 2006.
C. A. Micchelli and M. Pontil. Learning the kernel function via regularization.
Journal of Machine Learning Research, 6:1099–1125, 2005.
C. Mu, B. Huang, J. Wright, and D. Goldfarb. Square deal: Lower bounds andimproved relaxations for tensor recovery. In Proceedings of the 31th
International Conference on Machine Learning, pages 73–81, 2014.
Y. Nesterov. Gradient methods for minimizing composite objective function.
Technical Report 76, Center for Operations Research and Econometrics(CORE), Catholic University of Louvain (UCL), 2007.
Y. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical
Programming, Series B, 120:221–259, 2009.
Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization
problems. SIAM Journal on Optimization, 22(2):341–362, 2012.

H. Ouyang, N. He, L. Q. Tran, and A. Gray. Stochastic alternating direction
method of multipliers. In Proceedings of the 30th International Conference on
Machine Learning, 2013.
M. Powell. A method for nonlinear constraints in minimization problems. In
R. Fletcher, editor, Optimization, pages 283–298. Academic Press, London,
New York, 1969.
A. Rakotomamonjy, F. Bach, S. Canu, and G. Y. SimpleMKL. Journal of Machine
Learning Research, 9:2491–2521, 2008.
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, 2012.
P. Ravikumar, J. Lafferty, H. Liu, and L. Wasserman. Sparse additive models.
Journal of the Royal Statistical Society: Series B, 71(5):1009–1030, 2009.
P. Richtárik and M. Takáč. Distributed coordinate descent method for learningwith big data. Technical report, 2013. arXiv:1310.2059.
P. Richtárik and M. Takáč. Iteration complexity of randomized block-coordinate
descent methods for minimizing a composite function. Mathematical
Programming, 144:1–38, 2014.

95 / 95

P. Rigollet and A. Tsybakov. Exponential screening and optimal rates of sparse
estimation. The Annals of Statistics, 39(2):731–771, 2011.
R. T. Rockafellar. Augmented Lagrangians and applications of the proximal point
algorithm in convex programming. Mathematics of Operations Research, 1:
97–116, 1976.
M. Rudelson and S. Zhou. Reconstruction from anisotropic randommeasurements. IEEE Transactions of Information Theory, 39, 2013.
A. Saha and A. Tewari. On the non-asymptotic convergence of cyclic coordinate
descent methods. SIAM Journal on Optimization, 23(1):576–601, 2013.
M. Schmidt, N. Le Roux, and F. R. Bach. Minimizing finite sums with thestochastic average gradient, 2013. hal-00860051.
S. Shalev-Shwartz and T. Zhang. Stochastic dual coordinate ascent methods forregularized loss minimization. Journal of Machine Learning Research, 14:
567–599, 2013.
J. Shawe-Taylor. Kernel learning for novelty detection. In NIPS 2008 Workshop
on Kernel Learning: Automatic Selection of Optimal Kernels, Whistler, 2008.
S. Sonnenburg, G. Rätsch, C. Schäfer, and B. Schölkopf. Large scale multiple
kernel learning. Journal of Machine Learning Research, 7:1531–1565, 2006.
N. Srebro, N. Alon, and T. Jaakkola. Generalization error bounds for collaborative
prediction with low-rank matrices. In Advances in Neural Information
Processing Systems (NIPS) 17, 2005.

95 / 95

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. Unifying framework for fast learning rate of non-sparse multiple kernel
learning. In Advances in Neural Information Processing Systems 24, pages
1575–1583, 2011. NIPS2011.
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. Dual averaging and proximal gradient descent for online alternating
direction multiplier method. In Proceedings of the 30th International
Conference on Machine Learning, pages 392–400, 2013.
T. Suzuki. Stochastic dual coordinate ascent with alternating direction method ofmultipliers. In Proceedings of the 31th International Conference on Machine
Learning, pages 736–744, 2014.
T. Suzuki and M. Sugiyama. Fast learning rate of multiple kernel learning:trade-off between sparsity and smoothness. The Annals of Statistics, 41(3):1381–1405, 2013.
T. Suzuki and R. Tomioka. SpicyMKL, 2009. arXiv:0909.5026.
R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of theRoyal Statistical Society, Series B, 58(1):267–288, 1996.

95 / 95

R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity andsmoothness via the fused lasso. 67(1):91–108, 2005.
R. Tomioka and T. Suzuki. Sparsity-accuracy trade-off in MKL. In NIPS 2009
Workshop: Understanding Multiple Kernel Learning Methods, Whistler, 2009.
R. Tomioka and T. Suzuki. Convex tensor decomposition via structured schatten
norm regularization. In Advances in Neural Information Processing Systems 26,
page accepted, 2013. NIPS2013.
R. Tomioka, T. Suzuki, K. Hayashi, and H. Kashima. Statistical performance of
convex tensor decomposition. In Advances in Neural Information Processing
Systems 24, pages 972–980, 2011. NIPS2011.
S. van de Geer, P. B uehlmann, Y. Ritov, and R. Dezeure. On asymptotically
optimal confidence regions and tests for high-dimensional models. The Annalsof Statistics, 42(3):1166–1202, 2014.
S. J. Wright. Coordinate descent algorithms. Mathematical Programming, 151(1):
3–34, 2015.
L. Xiao. Dual averaging methods for regularized stochastic learning and online
optimization. In Advances in Neural Information Processing Systems 23, 2009.
L. Xiao and T. Zhang. A proximal stochastic gradient method with progressive
variance reduction. SIAM Journal on Optimization, 24:2057–2075, 2014.
M. Yuan and Y. Lin. Model selection and estimation in the Gaussian graphicalmodel. Biometrika, 94(1):19–35, 2007.
95 / 95

95 / 95

C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty.
The Annals of Statist, 38(2):894–942, 2010.
P. Zhang, A. Saha, and S. V. N. Vishwanathan. Regularized risk minimization bynesterov’s accelerated gradient methods: Algorithmic extensions and empiricalstudies. CoRR, abs/1011.0472, 2010.
T. Zhang. Some sharp performance bounds for least squares regression with l1
regularization. The Annals of Statistics, 37(5):2109–2144, 2009.
H. Zou. The adaptive lasso and its oracle properties. Journal of the American
Statistical Association, 101(476):1418–1429, 2006.
ాதར޾. ѹॖηϯγϯάͷ਺ཧ. IEICE Fundamentals Review, 4(1):39–47, 2010.

95 / 95