www-ai.cs.tu-dortmund.de/de/LEHRE/VORLESUNGEN/LOPT/SS16/papers/ShaSS07.pdf
paper.dvi
Pegasos does not depend on
10 2
10 3
10 4
10 5
10 6
10 −1
10 0
10 1
10 2
T
Pegasos Norma
10 2
10 3
10 4
10 5
10 6
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
T
Pegasos Zhang
Figure 2.Comparisons of Pegasos to [...] = 1, 2, . . . , T
ChooseAt ⊆ S, where|At| = k SetA+
t = {(x, y) ∈ At : y 〈wt,x〉 < 1} Setηt = 1
λt Setwt+ 1
2 = (1 − ηt λ)wt + ηt
k
∑
(x,y)∈A+
t
y x
Setwt+1 = min
{
1, 1/ √
λ ‖w
t+ 1 2
‖
}
wt+ 1 2
OUTPUT: [...] To do so, we use the fact that there exists a vectorα⋆ ∈ [0, 1]m such that
λ
2 ‖w⋆‖2+
1
m
∑
(x,y)∈S
ℓ(w⋆; (x, y)) = −λ
2 ‖w⋆‖2+
‖α⋆‖1
m .
(The above equality is derived by applying the strong dual- ity theorem …
