180 PROOFS AND DERIVATIONS
B.2.2 Proof of Proposition 9.2
Proof We derive the solution of PAMR-1 following the same procedure as the
derivation of PAMR. If the loss is nonzero, we get a Lagrangian
L(b, ξ, τ, μ, λ) =
1
2
b −b
t
2
+τ(x
t
·b −) +ξ(C −τ −μ) +λ(1 ·b−1).
Setting the partial derivatives of L with respect to b to zero gives
0 =
∂L
∂b
= (b −b
t
) +τx
t
+λ1,
Multiplying both sides by 1
, we can get λ =−τ
x
t
·1
m
=−τ
¯
x
t
. And the solution is
b = b
t
−τ(x
t
−¯x
t
1).
Next, note that the minimum of the term ξ(C −τ −μ) with respect to ξ is zero when-
ever C −τ −μ = 0.IfC −τ −μ = 0, then the minimum can be made to approach
−∞. Since we need to maximize the dual, we can rule out the latter case and pose
the following constraint on the dual variables, C −τ −μ = 0. The KKT conditions
confine μ to be nonnegative, so we conclude that τ ≤ C. We can project τ to the
interval [0,C] and get
τ = max
"
0, min
"
C,
b
t
·x
t
−
x
t
−¯x
t
1
2
##
= min
"
C,
t
x
t
−¯x
t
1
2
#
.
Again, we simplify the notation according to Equation 9.1 and show a unified update
scheme.
B.2.3 Proof of Proposition 9.3
Proof We derive the solution similar to the derivations of PAMR and PAMR-1. In
case that the loss is not 0, we can get the Lagrangian,
L(b, ξ, τ, μ, λ) =
1
2
b −b
t
2
+τ(b ·x
t
−) +Cξ
2
−τξ +λ(1 ·b−1).
Setting the partial derivatives of L with respect to b to zero gives
0 =
∂L
∂b
= (b −b
t
) +τx
t
+λ1,
Multiplying both sides by 1
, we can get λ =−τ
x
t
·1
m
=−τ ¯x. And the solution is
b = b
t
−τ(x
t
−¯x1).
Setting the partial derivatives of L with respect to ξ to zero gives
0 =
∂L
∂ξ
= 2Cξ −τ =⇒ ξ =
τ
2C
.
T&F Cat #K23731 — K23731_A002 — page 180 — 9/28/2015 — 20:47