Sign-Constrained Regularized Loss Minimization
Tsuyoshi Kato†,∗ , Misato Kobayashi† , Daisuke Sano⋄
†

arXiv:1710.04380v1 [cs.LG] 12 Oct 2017

⋄

Division of Electronics and Informatics, Faculty of Science and Technology, Gunma
University, Tenjin-cho 1-5-1, Kiryu, Gunma 376-8515, Japan.
Department of Civil and Environmental Engineering, Graduate School of Engineering,
Tohoku University, Aoba 6–6–06, Aramaki, Aoba-ku, Sendai, Miyagi 980–8579, Japan.

Abstract

in I+ and I− ,

In practical analysis, domain knowledge about analysis target
has often been accumulated, although, typically, such knowledge has been discarded in the statistical analysis stage, and
the statistical tool has been applied as a black box. In this paper, we introduce sign constraints that are a handy and simple representation for non-experts in generic learning problems. We have developed two new optimization algorithms for
the sign-constrained regularized loss minimization, called the
sign-constrained Pegasos (SC-Pega) and the sign-constrained
SDCA (SC-SDCA), by simply inserting the sign correction
step into the original Pegasos and SDCA, respectively. We
present theoretical analyses that guarantee that insertion of
the sign correction step does not degrade the convergence
rate for both algorithms. Two applications, where the signconstrained learning is effective, are presented. The one is
exploitation of prior information about correlation between
explanatory variables and a target variable. The other is introduction of the sign-constrained to SVM-Pairwise method.
Experimental results demonstrate significant improvement of
generalization performance by introducing sign constraints in
both applications.

1

for h ∈ I+ ,

The problem of regularized loss minimization (e.g. Hastie
et al. (2009)) is often described as

where

wrt w ∈ Rd ,
λ
1
P (w) := kwk2 + Φ(X ⊤ w),
2
n
X := [x1 , . . . , xn ] ∈ Rd×n ,

wh′ ≤ 0.

(2)

Sign constraints can introduce prior knowledge directly to
learning machines. For example, let us consider a binary classification task. In case that h-th explanatory variable xh is
positively correlated to a binary class label y ∈ {±1}, then a
positive weight coefficient wh is expected to achieve a better
generalization performance than a negative coefficient, because without sign constraints, the entry wh in the optimal
solution might be negative due to small sample problem. On
the other hand, in case that xh is negatively correlated to the
class label, a negative weight coefficient wh would yield better
prediction. If sign constraints were explicitly imposed, then
inadequate signs of coefficients could be avoided.
The strategy of sign constraints for generic learning problems has rarely been discussed so far, although there are
extensive reports for non-negative least square regression
supported by many successful applications including sound
source localization: (Lin et al., 2004), tomographic imaging
(Ma, 2013), spectral analysis (Zhang et al., 2007), hyperspectral image super-resolution (Dong et al., 2016), microbial
community pattern detection (Cai et al., 2017), face recognition (Ji et al., 2009; He et al., 2013), and non-negative image restoration (Henrot et al., 2013; Landi and Piccolomini,
2012; Wang and Ma, 2007; Shashua and Hazan, 2005). In
most of them, non-negative least square regression is used
as an important ingredient of bigger methods such as nonnegative matrix factorization (Lee and Seung, 2001; Wang
et al., 2017; Kimura et al., 2016; Févotte and Idier, 2011;
Ding et al., 2006).
Several efficient algorithms for the non-negative least
square regression have been developed. The active set method
by Lawson and Hanson (1995) has been widely used in many
years, and several work (Kim et al., 2010, 2007; Bierlaire
et al., 1991; Portugal et al., 1994; Moré and Toraldo, 1991;
Lin and Moré, 1999; Morigi et al., 2007) have accelerated optimization by combining the active set method with the projected gradient approach. Interior point methods (Bellavia
et al., 2006; Heinkenschloss et al., 1999; Kanzow and Klug,
2006) have been proposed as an alternative algorithm for nonnegative least square regression. However, all of them cannot
be applied to generic regularized loss minimization problems.
In this paper, we present two algorithms for the signconstrained regularized loss minimization problem with

Introduction

min

wh ≥ 0, for h′ ∈ I− ,

P (w)

(1)

aiming to obtain a linear predictor hw, xi for an unknown
input x ∈ Rd . Therein, Φ : Rn → R is a loss function
P which is
the sum of convex losses for n examples: Φ(z) := ni=1 φi (zi )
⊤
for z := [z1 , . . . , zn ] ∈ Rn . This problem covers a large
class of machine learning algorithms including support vector
machine, logistic regression, support vector regression, and
ridge regression.
In this study, we pose sign constraints (Lawson and Hanson, 1995) to the entries in the model parameter w ∈ Rd in
the unconstrained minimization problem (1). We divide the
index set of d entries into three exclusive subsets, I+ , I0 , and
I− , as {1, . . . , d} = I+ ∪ I0 ∪ I− and impose on the entries
1

generic loss functions. A surge of algorithms for unconstrained regularized empirical loss minimization have been
developed such as SAG (Roux et al., 2012; Schmidt et al.,
2016), SVRG (Johnson and Zhang, 2013), Prox-SVRG (Xiao
and Zhang, 2014), SAGA (Defazio et al., 2014a), Kaczmarz
(Needell et al., 2015), EMGD (Zhang et al., 2013), and Finito
(Defazio et al., 2014b). This study focuses on two popular algorithms, Pegasos (Shalev-Shwartz et al., 2011) and
SDCA (Shalev-Shwartz and Zhang, 2013). A prominent characteristic of the two algorithms is unnecessity to choose a step
size. Some of the other optimization algorithms guarantee
convergence to the optimum under the assumption of a small
step size, although the step size is often too small to be used.
Meanwhile, the theorem of Pegasos has been developed with
a step size ηt = 1/(λt) which is large enough to be adopted
actually. SDCA needs no step size. Two new algorithms developed in this study for the sign-constrained problems are
simple modifications of Pegasos and SDCA.
The contributions of this study are summarized as follows.

Assumption 2.1. Throughout this paper, the following
assumptions are used:
(a) Φ(·) is a convex function.
(c) ∀s ∈ Rn , Φ(s) ≥ 0.

1
Φ(0) ≤ rloss .
n
(d) ∀i, kxi k ≤ R.

(b)

Most of widely used loss functions satisfy the above assumptions. Several examples of such loss functions are described in Table 1. If the hinge loss is chosen, the learning
machine is a well-known instance called the support vector
machine. If the square error loss is chosen, the learning machine is called the ridge regression. We denote the optimal solution to the constraint problem by w⋆ := argmin P (w). We
w∈S

assume two types of loss functions: L-Lipschitz continuous
function and (1/γ)-smooth function. Function φi : R → R is
said to be an L-Lipschitz continuous funciton if

• Sign constraints are introduced to generic regularized loss
minimization problems.

∀s, ∀δ ∈ R,

|φi (s + δ) − φi (s)| ≤ L|δ|.

(6)

Such functions are often said shortly to be L-Lipschitz in
this paper. Function φi : R → R is a (1/γ)-smooth function
if its derivative function is L-Lipschitz. For an index subset
A ⊆ {1, . . . , n} and a vector v ∈ Rn , let vA be the subvector
of v containing entries corresponding to A. Let XA be a
sub-matrix in X containing columns corresponding to A. Let
• Our theoretical analysis ensures that both SC-Pega and Φ(· ; A) : R|A| → R be defined as
SC-SDCA do not degrade the convergence rates of the
X
Φ(sA ; A) :=
φi (si ).
original algorithms.
(7)

• Two optimization algorithms for the sign-constrained
regularized loss minimization, called SC-Pega and SCSDCA, were developed by simply inserting the sign correction step, introduced in Section 3, to the original Pegasos and SDCA.

i∈A

• Two attractive applications, where the sign-constrained
learning is effective, are presented. The one is exploitation of prior information about correlation between exSign-Constrained Pegasos
planatory variables and a target variable. The other 3
is introduction of the sign-constrained to SVM-Pairwise
In the original Pegasos algorithm (Shalev-Shwartz et al.,
method (Liao and Noble, 2003).
2011), φi is assumed to be the classical hinge loss function
• Experimental results demonstrate significant improve- (See Table 1 for the definition). Each iterate consists of three
ment of generalization performance by introducing sign steps: the mini-batch selection step, the gradient step, and the
constraints in both two applications.
projection-onto-ball step. Mini-batch selection step chooses a
subset At ⊆ {1, . . . , n} from n examples at random. The cardinality of the subset is predefined as |At | = k. Gradient step
2 Problem Setting
computes the gradient of
The feasible region can be expressed simply as

S := w ∈ Rd c ⊙ w ≥ 0d

λ
1
⊤
(8)
w ; At ).
kwk2 + Φ(XA
t
2
k
which approximates the objective function P (w). The current solution wt is moved toward the opposite gradient direction as
1
wt+1/2 := wt − ∇Pt (wt )
λt
(9)
t−1
1
⊤
w
;
A
).
=
w−
XAt ∇Φ(XA
t
t
t
t
kλt
At the projection-onto-ball step, the norm of the solution is
if the norm is over √λkw1
:
shortened to be √λkw1
t+1/2 k
t+1/2 k
!
1
wt+1/2 .
(10)
wt+1 := min 1, √
λkwt+1/2 k
Pt (w) :=

(3)

⊤

where c = [c1 , . . . , cd ] ∈ {0, ±1}d, each entry is given by


for h ∈ I+ ,
+1
(4)
ch := 0
for h ∈ I0 ,


−1
for h ∈ I− .

Using S, the optimization problem discussed in this paper
can be expressed as
min

P (w)

wrt

w ∈ S.

(5)

2

⊤

Table 1: Loss functions and their properties. Suppose 0 ≤ γ ≤ 1. Let y := [y1 , . . . , yn ] .
Name
Classical hinge loss
Smoothed hinge loss
Logistic loss
Square error loss
Absolute error loss

Definition
φi (s) := max(0,
1 − yi s)

1 − yi s − 0.5γ
if yi s ∈ (−∞, 1 − γ],

φi (s) := (1 − yi s)2 /(2γ)
if yi s ∈ (1 − γ, 1),


0
if yi s ∈ [1, +∞).
φi (s) := log(1 + exp(−yi s))
φi (s) := 0.5(s − yi )2
φi (s) := |s − yi |

Label
yi ∈ {±1}

Type
1-Lipschitz

yi ∈ {±1}

(1/γ)-smooth

yi ∈ {±1}
yi ∈ R
yi ∈ R

0.25-smooth
1-smooth
1-Lipschitz

rloss
1
1−

γ
2

log(2)
kyk2 /(2n)
kyk1 /n

Algorithm 1 Generic Sign-Constrained Pegasos
continuous, it holds that
Require: Data matrix X ∈ Rd×n , loss function Φ : Rn → R,
p
2 1 + log(T )
regularization parameter λ ∈ R, sign constraint parame.
E [P (w̃)] − P (w⋆ ) ≤
rloss λ + LR
ter c ∈ {±1, 0}d, and mini-batch size k.
λT
1: begin
(12)
2: w1 := 0d ; {Initialization}
3: for t := 1, . . . , T do
4:
Choose At ⊆ {1, . . . , n} uniformly at random such that
See Subsection A.1 for proof of Theorem 1. This bound is
|At | = k.
exactly
same as the original Pegasos, yet Algorithm 1 contains
1
⊤
5:
wt+1/3 := t−1
t wt − λt XAt ∇Φ(XAt wt−1 ; At );
the sign correction step.
6:
wt+2/3 := wt+1/3 + c ⊙ (−c ⊙ wt+1/3 )+ ;

√
7:
wt+1 := min 1, rloss λ−1 kwt+2/3 k−1 wt+2/3 ;
8: end for
4 Sign-Constrained SDCA
PT
9: return w̃ :=
w
/T
;
t
t=1
The original SDCA is a framework for the unconstrained
10: end.
problems (1). In SDCA, a dual problem is solved instead
of the primal problem. Namely, the dual objective is maxiThe projection-onto-ball step plays an important role in get- mized in a iterative fashion with respect to the dual variables
⊤
ting a smaller upper-bound of the norm of the gradient of the α := [α1 , . . . , αn ] ∈ Rn . The problem dual to the unconregularization term in the objective, which eventually reduces strained problem (1) is given by
the number of iterates to attain an ǫ-approximate solution
min D(α)
wrt α ∈ Rn ,
(13)
(i.e. P (w̃) − P (w⋆ ) ≤ ǫ).
In the algorithm developed in this study, we simply inserts where
between those two steps, a new step that corrects the sign of
2
each entry in the current solution w as
1
λ 1
(14)
Xα − Φ∗ (−α).
D(α) := −
2 λn
n


for h ∈ I+ ,
max(0, wh )
wh ← min(0, wh )
(11) To find the maximizer of D(α), a single example i is chofor h ∈ I− ,

sen randomly at each iterate t, and a single dual variable αi

wh
for h ∈ I0 ,
is optimized with the other (n − 1) variables α1 , . . . , αi−1 ,
αi+1 , . . . , αn frozen. If we denote by α(t−1) ∈ Rn the value
which can be rewritten equivalently as w ← w + c ⊙ (−c ⊙ of the dual vector at the previous iterate (t − 1), the dual
w)+ where the operator (·)+ is defined as ∀x ∈ Rd , (x)+ := vector is updated as α(t) := α(t−1) + ∆αe where ∆α ∈ R
i
max(0, x).
is determined so that ∆α ∈ argmax Dt (∆α ; w(t−1) ) where
The algorithm can be summarized as Algorithm 1. Here,
∆α∈R
1
Xα(t−1) and
the loss function is not limited to the classical hinge loss. In w(t−1) = λn
the
√ projection-onto-ball step,√ the solution is projected onto
2
rloss λ−1 -ball instead of (1/ λ)-ball to handle more general
λ
1
∆α
(t−1)
D
(∆α
;
w)
:=
−
−∆α).
x
− φ∗i (−αi
w
+
t
i
settings. Recall that rloss = 1 if φi is the hinge loss employed
2
λn
n
in the original Pegasos. It can be shown that the objective
(15)
gap is bounded as follows.
In case of the hinge loss, the maximizer of Dt (· ; w(t−1) ) can
be found within O(d) computation. The primal variable w(t)
can also be maintained within O(d) computation by w(t) :=
w(t−1) + ∆α
λn xi .

Theorem 1. Consider Algorithm 1. If φi are L-Lipschitz

3

Algorithm 2 Generic Sign-Constrained SDCA.
Require: Data matrix X ∈ Rd×n , loss function Φ : Rn →
R, regularization parameter λ ∈ R, and sign constraint
parameter c ∈ {±1, 0}d.
1: begin
2: α(0) := 0n ; w̄ (0) := 0d ; w (0) := 0d ; {Initialization}
3: for t := 1, . . . , T do
4:
∆α ∈ argmax Dt (∆α ; w(t−1) );

See Subsections A.6 for proof of Theorem 2. Theorem 2
suggests that the convergence rate of Algorithm 2 is not deteriorated compared to the original SDCA in both cases of
L-Lipschitz and smooth losses, despite insertion of the sign
correction step.

5

Multiclass Classification

∆α∈R

In this section, we extend our algorithms to the multi-class
classification setting of m classes. Here, the model parameter
6:
is a W ∈ Rd×m instead of a vector w ∈ Rd . The loss function
7:
for each example xi ∈ Rd is of an m-dimensional vector. Here,
8:
the prediction is supposed to be done by taking the class
9:
with the maximal score among s1 := hw1 , xi , . . . , and sm :=
hwm , xi. Here, without loss of generality, the set of the class
Now let us move on the sign-constrained problem. In addi- labels are given by Y := {1, . . . , m}. Several loss functions
m
m
tion to Algorithm 1 that is derived from Pegasos, we present φi : R → R are used for multiclass classification as follows.
another algorithm based on SDCA for solving the minimizer
• Soft-max loss:
of P (w) subject to the sign constraint c ⊙ w ≥ 0d . Like Algo

rithm 1 that has been designed by inserting the sign correction
X

φm
exp (sy − syi )
(20)
step into the original Pegasos iterate, the new algorithm has
i (s) := log
y∈Y
been developed by simply adding the sign correction step in
each SDCA iterate. The resultant algorithm is described in
Therein, yi is the true class label of i-th example.
Algorithm 2.
For some loss functions, maximization at step 5 in Algo• Max-hinge loss;
rithm 2 cannot be given in a closed form. Alternatively, step 4
φm
can be replaced to
i (s) := max (sy − syi + δy,yi ) .
(21)
y∈Y
5:

w̄(t) := w̄(t−1) + ∆α
λn xi ;
w(t) := w̄(t) + c ⊙ (−c ⊙ w̄(t) )+ ;
end for
PT
1
(t−1)
;
return w̃ := T −T
t=T0 +1 w
0
end.

4 : ∆α := sq,

where

s := Clip[0,s−1 ]
lb



1 z (t) αi + φ∗i (−αi ) + φi (z (t) )
+
2
γq 2



• Top-k hinge loss (Lapin et al., 2015):

slb .

φm
i (s)

k

1X
:=
(I − 1e⊤
yi )s + 1 − eyi [j] .
k j=1

(22)
(16)
Therein, we have defined slb := λnγ/(λnγ + R2 ), z (t) :=
(t−1)
, and Clip[a,b] (x) :=
w(t−1) , xi , q (t) := −∇φi (z (t) ) − αi
Therein, x[j] denotes the j-th largest value in a vecmax(a, min(b, x)). See Subsection A.4 for derivation of (16).
tor x ∈ Rm .
We have found the following theorem that states the red×m
is defined as
quired number of iterates guaranteeing the expected primal The objective function for learning W ∈ R
objective gap below a threshold ǫ under the sign constraints.
n
λ
1X m
P m (W ) := kW k2F +
φ (W ⊤ xi ).
(23)
2
n i=1 i
Theorem 2. Consider Algorithm 2. In case that φi are
L-Lipschitz continuous (i.e. (6)), it holds that E[P (w̃)] −
P (w⋆ ) ≤ ǫ if T and T0 are specified so that

 
2λnrloss
4G
(17)
+ max 0, n log
T0 ≥
λǫ
G
and



G
T ≥ T0 + max n,
λǫ



The learning problem discussed is minimization of P m (W )
with respect to W subject to sign constraints
∀(h, j) ∈ E+ , Wh,j ≥ 0,
∀(h′ , j ′ ) ∈ E− , Wh′ ,j ′ ≤ 0,

(24)

with two exclusive set E+ and E− such that
E+ ∪ E− ⊆ {(h, j) ∈ N2 | h ∈ [1, d], j ∈ [1, m]}.

(18)

Introducing C ∈ {0, ±1}d×m


+1
Ch,j := −1


0

where G := 4R2 L2 . If φi are hinge loss functions, then
G := R2 L2 . In case that φi are (1/γ)-smooth, E[P (w̃)] −
P (w⋆ ) ≤ ǫ is established if





R2
rloss
R2
log
n+
.
T > T0 ≥ n +
λγ
λγ (T − T0 )ǫ
(19)

as
for (h, j) ∈ E+ ,
for (h, j) ∈ E− ,
o.w.

the feasible region can be expressed as

S m := W ∈ Rd×m C ⊙ W ≥ Od×m .
4

(25)

(26)

(27)

Algorithm 3 Sign-Constrained Pegasos for Multiclass Clas- Algorithm 4 Sign-Constrained SDCA for Multiclass Classisification.
fication.
Require: Data matrix X ∈ Rd×n , loss function Φm : Require: Data matrix X ∈ Rd×n , loss function Φ : Rm×n →
Rm×n → R, regularization parameter λ ∈ R, sign conR, regularization parameter λ ∈ R, and sign constraint
straint parameter C ∈ {0, ±1}d×m, and mini-batch size
parameter C ∈ {±1, 0}d×m.
k.
1: begin
1: begin
2: A(0) := O; W̄ (0) := O; W (0) := O;
{Initialization}
2: W1 := 0d ; {Initialization}
3: for t := 1, . . . , T do
3: for t := 1, . . . , T do
4:
∆α ∈ argmax Dt (∆α ; W (t−1) );
∆α∈Rm
4:
Choose At ⊆ {1, . . . , n} uniformly at random such that
1
(t)
xi ∆α⊤ ;
5:
W̄
:=
W̄ (t−1) + λn
|At | = k.
(t)
(t)
⊤
6:
W := W̄ + C ⊙ max(O, −C ⊙ W̄ (t) );
5:
Zt := Wt−1
XAt ;
7: end for
⊤
1
PT
6:
Wt+1/3 := t−1
1
t Wt − λt XAt (∇Φ(Zt ; At )) ;
(t−1)
8:
return
W̃
:=
;
t=T0 +1 W
T
−T
0
7:
Wt+2/3 := Wt+1/3 + C ⊙ max(O, −C ⊙ Wt+1/3 );


9: end.
rloss
Wt+2/3 ;
8:
Wt+1 := min 1, √λkW
k
t+2/3 F

9:
10:

11:

end for
P
return W̃ := Tt=1 Wt /T ;
end.

6.1

Prediction Performance

The pattern recognition performance of the sign-constrained
learning was examined on two tasks: Escherichia coli (E. coli)
prediction and protein function prediction.

The goal is here to develop algorithms that find
W⋆ := arg minm P m (W ).

(28) E. coli Prediction The first task is to predict E. coli
counts in river water. The E. coli count has been used as
an indicator for fecal contamination in water environment in
Define Φm (· ; A) : Rm×k → R as
many parts of the world (Scott et al., 2002). In this experiX
Φm (SA ; A) :=
φm
(s
)
i
i
(29) ment, the data points with E. coli counts over 500 most probable number (MPN)/100 mL are assigned to positive class,
i∈A
and the others are negative. The hydrological and water qualwhere SA is the horizontal concatenation of columns in S := ity monitoring data are used for predicting E. coli counts to
[s1 , . . . , sn ] ∈ Rm×n selected by a minibatch A. We here be positive or negative.
use the following assumptions: Φm (·) is a convex function;
For ensuring the microbial safety in water usage, it is meanΦm (O) ≤ nrloss ; ∀S ∈ Rm×n , Φm (S) ≥ 0; ∀i, kxi k ≤ R.
ingful to predict E. coli counts on a real-time basis. The conBy extending Algorithm 1, an algorithm for minimization
centration of E. coli in water, which is measured by cultureof P m (W ) subject to the sign constraints can be developed dependent methods (Kobayashi et al., 2013), has been used to
as described in Algorithm 3.
monitor the fecal contamination in water environment, and
The SDCA-based learning algorithm can also be develhas been proved to be effective to prevent waterborne inoped for the multiclass classification task. In the algo- fectious diseases in varied water usage styles. On the other
rithm, the dual variables are represented as a matrix A :=
hand, the real-time monitoring of E. coli counts has not yet
[α1 , . . . , αn ] ∈ Rm×n . At each iterate t, one of n columns, αi , been achieved. It take at least ten hours to obtain E. coli
is chosen at random instead of choosing one of a dual vari- counts by culture-dependent methods, and also at least sevable to update the matrix as A(t) := A(t−1) +∆αe⊤
i where we eral hours are needed to measure the concentration of E. coli
have used the iterate number (t) as the superscript of A. To by culture-independent methods (Ishii et al., 2014b,a), such
determine the value of ∆α, the following auxiliary funcition as polymerase chain reaction. Since it is possible to measure
is introduced:
the some of the hydrological and water quality data with realtime sensors, the real-time prediction of E. coli counts will be
2
kxi k
Dt (∆α ; W ) := − 2 k∆αk2
realized if the hydrological and water quality data are avail2λ n
able for the E. coli count prediction.
(t−1)
− ∆α). (30)
− W ⊤ xi , ∆α − φ∗i (−αi
Many training examples are required to obtain a better
generalization performance. A serious issue, however, is that
For both algorithms (Algorithms 3 and 4), we can bound
measuring the concentration of E. Coli is time-consuming and
the required number of iterations similar to those presented
the cost of reagents is expensive. We here demonstrate that
in Theorems 1 and 2.
this issue can be relaxed by exploiting the domain knowledge
hoarded in the field of water engineering.
The hydrological and water quality data contain nine ex6 Experiments
planatory variables, WT, pH, EC, SS, DO, BOD, TN, TP, and
In this section, experimental results are reported in order to flow rate. The explanatory variable pH is divided into two
illustrate the effects of the sign constraints on classification variables, pH+ ← max(0, pH−7) and pH− ← max(0, 7−pH).
and to demonstrate the convergence behavior.
It is well-known, in the field of water engineering, that E. coli
W ∈S

5

(b) ROC score

20
10
0
-0.4

-0.2

0

Improvement

0.2

0.4

Normalized frequency

Normalized frequency

(a) PRBEP

20
10
0
-0.4

-0.2

0

0.2

0.4

Improvement

Figure 1: Improvements of generalization performances on
E. Coli prediction.
is increased, as WT, EC, SS, BOD, TN, and TP are larger,
and as pH+ , pH− DO, and the flow rate are smaller. From this
fact, we restrict the sign of entries in the predictor parameter
w as follows.

Table 2: ROC Scores for protein
Category
SC-SVM
1
0.751 (0.011)
2
0.740 (0.016)
3
0.753 (0.011)
4
0.762 (0.010)
5
0.769 (0.012)
6
0.690 (0.014)
7
0.713 (0.024)
8
0.725 (0.019)
9
0.655 (0.024)
10
0.743 (0.016)
11
0.535 (0.019)
12
0.912 (0.011)

function prediction.
SVM
0.730 (0.010)
0.680 (0.015)
0.721 (0.011)
0.734 (0.010)
0.691 (0.013)
0.614 (0.014)
0.618 (0.022)
0.667 (0.019)
0.578 (0.023)
0.710 (0.014)
0.492 (0.018)
0.901 (0.011)

x1 , . . . , xn . If we suppose that the first n+ proteins in the
• Coefficients wh of six explanatory variables, WT, EC, training set are in positive class and the rest are negative,
SS, BOD, TN, and TP must be non-negative.
then the first n+ similarities x1 , . . . , xn+ are sequence simi• Coefficients wh of four explanatory variables, pH+ , pH− , larities to positive examples, and xn+ +1 , . . . , xn are similarities to negative examples. The n-dimensional vectors are fed
DO, flow rate must be non-positive.
⊤
to SVM and get the weight coefficients w := [w1 , . . . , wn ] .
We actually measured the concentrations of E. coli 177 times Then, the prediction score of the target protein is expressed
from December 5th, 2011 to April 17th, 2013. We obtained as
n+
n
X
X
177 data points including 88 positives and 89 negatives. We
wi xi +
wi xi .
(31)
chose ten examples out of 177 data points at random to use
i=1
i′ =n+ +1
them for training, and the other 167 examples were used for
testing. The prediction performance is evaluated by the preci- The input protein sequence is predicted to have some particsion recall break-even point (PRBEP) (Joachims, 2005) and ular cellular function if the score is over a threshold. It should
the ROC score. We compared the classical SVM with the be preferable that the first n+ weight coefficients w1 , . . . , wn+
sign-constrained SVM (SC-SVM) to examine the effects of are non-negative and that the rest of (n − n+ ) weight coefsign constraints. We repeated this procedure 10,000 times ficients wn+ +1 , . . . , wn are non-positive. The SVM-Pairwise
approach does not ensure those requirements. Meanwhile,
and obtained 10,000 PRBEP and 10,000 ROC scores.
SC-SVM achieved significant improvement compared to the our approach is capable to explicitly impose the constraints
classical SVM. SC-SVM achieved PRBEP and ROC score of of
0.808 and 0.863 on average over 10,000 trials, whereas those of
w1 ≥ 0, . . . , wn+ ≥ 0, and wn+ +1 ≤ 0, . . . , wn ≤ 0. (32)
the classical SVM were 0.757 and 0.810, respectively. The difference from the classical SVM on each trial is plotted in the
histograms of Figure 1. Positive improvements of ROC scores
This approach was applied to predict protein functions
were obtained in 8,932 trials out of 10,000 trials, whereas in Saccharomyces cerevisiae (S. cerevisiae). The annotaROC scores were decreased only for 796 trials. For PRBEP, tions of the protein functions are provided in MIPS Compositive improvements were obtained on 7,349 trials, whereas prehensive Yeast Genome Database (CYGD). The dataset
deteriorations were observed only on 1,069 trials.
contains 3,583 proteins. The Smith-Waterman similarities
available from https://noble.gs.washington.edu/proj/
Protein Function Prediction In the field of molecular sdp-svm/ were used as sequence similarities among the probiology, understanding the functions of proteins is positioned teins. The number of categories was 12. Some proteins
as a key step for elucidation of cellular mechanisms. Sequence have multiple cellular functions. Indeed, 1,343 proteins in
similarities have been a major mean to predict the function the dataset have more than one function. From this reason,
of an unannotated protein. At the beginning of this century, we pose 12 independent binary classification tasks instead of
the prediction accuracy has been improved by combining se- a single multi-class classification task. 3,583 proteins were
quence similarities with discriminative learning. The method, randomly splited in half to get two datasets. The one was
named SVM-Pairwise (Liao and Noble, 2003), uses a feature used for training, and the other was for testing. For 12 classivector that contains pairwise similarities to annotated protein fication tasks, we repeated this procedure 100 times, and we
sequences. Several other literature (Liu et al., 2014; Ogul and obtained 100 ROC scores.
Table 2 reports the ROC scores averaged over 100 trials and
Mumcuoglu, 2006; Lanckriet et al., 2004b,a) have also provided empirical evidences for the fact that the SVM-Pairwise the standard deviations for 12 binary classification tasks. The
approach is a powerful framework. Basically, if n proteins sign constraints significantly surpassed the classical training
are in a training dataset, the feature vector has n entries, for all 12 tasks. Surprisingly, we observed that the ROC score
6

(a) Covtype

(b) W8a
SC-Pega, k=10
SC-Pega, k=100
SC-SDCA

10

10

10-3

100
10-1
10-2
-3

SC-Pega, k=10
SC-Pega, k=100
SC-SDCA

10-1
Objective Gap

-2

100
SC-Pega, k=10
SC-Pega, k=100
SC-SDCA

1

Objective Gap

10-1
Objective Gap

(c) Phishing

102

100

10-2
10-3

10
10-4

10-4

10-4
10-5

10-4

10-3
Epoch

10-2

10-1

10-4 10-3 10-2 10-1 100
Epoch

101

102

103

10-4

10-3

10-2

10-1
100
Epoch

101

102

Figure 2: Comparison of different optimization methods.

References

of SC-SVM is larger than that of the classical SVM in every
trial.

6.2

Bellavia, S., Macconi, M., and Morini, B. (2006). An interior point newtonlike method for non-negative least-squares problems with degenerate solution. Numerical Linear Algebra with Applications, 13(10), 825–846.
doi: 10.1002/nla.502.

Convergence

Bierlaire, M., Toint, P., and Tuyttens, D. (1991). On iterative algorithms
for linear least squares problems with bound constraints. Linear Algebra
and its Applications, 143, 111–143. doi: 10.1016/0024-3795(91)90009-l.

We carried out empirical evaluation of the proposed optimization methods, the sign-constrained Pegasos (SC-Pega) and
the sign-constrained SDCA (SC-SDCA), in order to illustrate
the convergence of our algorithms to the optimum. For SCPega, we set the mini-batch size to k = 10 and k = 100.
In this experiments, we used the smoothed hinge loss with
γ = 0.01 and λ = 1/n. We used three datasets, Covtype (n =
581, 012 and d = 54), W8a (n = 49, 749 and d = 300), and
Phishing (n = 11, 055 and d = 68). The three datasets are
for binary classification and available from LIBSVM web site
(https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/).
Figure 2 depicts the primal objective gap against epochs,
where the primal objective gap is defined as P (w) − P (w⋆ ).
As expected in theoretical results, SC-SDCA converged to the
optimum faster than SC-Pega except on the dataset Phishing.
No significant difference between different mini-batch sizes is
observed.

7

Cai, Y., Gu, H., and Kenney, T. (2017). Learning microbial community
structures with supervised and unsupervised non-negative matrix factorization. Microbiome, 5(1), 110.
Defazio, A., Bach, F., and Lacoste-julien, S. (2014a). Saga: A fast incremental gradient method 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.
Defazio, A. J., Caetano, T. S., and Domke, J. (2014b).
Finito: A
faster, permutable incremental gradient method for big data problems.
arXiv:1407.2710 .
Ding, C., Li, T., Peng, W., and Park, H. (2006). Orthogonal nonnegative matrix tri-factorizations for clustering. In Proceedings of the 12th
ACM SIGKDD international conference on Knowledge discovery and
data mining - KDD06 . ACM Press. doi:10.1145/1150402.1150420.
Dong, W., Fu, F., Shi, G., Cao, X., Wu, J., Li, G., and Li, G. (2016).
Hyperspectral image super-resolution via non-negative structured sparse
representation. IEEE Trans Image Process, 25(5), 2337–52.
Févotte, C. and Idier, J. (2011). Algorithms for nonnegative matrix factorization with the β-divergence. Neural Computation, 23(9), 2421–2456.
doi:10.1162/neco a 00168, [pdf].

Conclusions

In this paper, we presented two new algorithms for minimizing
regularized empirical loss subject to sign constraints. The two
algorithms are based on Pegasos and SDCA, both of which
have a solid theoretical support for convergence. The signconstrained versions, named SC-Pega and SC-SDCA, respectively, enjoy the same convergence rate as the corresponding original algorithms. The algorithms were demonstrated
in two applications. The one is posing sign constraints according to domain knowledge, and the other is improving the
SVM-Pairwise method by sign constraints.

Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning – Data Mining, Inference, and Prediction. Springer,
2nd edition.
Hazan, E., Agarwal, A., and Kale, S. (2007). Logarithmic regret algorithms
for online convex optimization. Machine Learning, 69(2-3), 169–192.
doi:10.1007/s10994-007-5016-8.
He, R., Zheng, W. S., Hu, B. G., and Kong, X. W. (2013). Two-stage
nonnegative sparse representation for large-scale face recognition. IEEE
Trans Neural Netw Learn Syst, 24(1), 35–46.
Heinkenschloss, M., Ulbrich, M., and Ulbrich, S. (1999).
Superlinear
and quadratic convergence of affine-scaling interior-point newton methods for problems with simple bounds without strict complementarity assumption. Mathematical Programming, 86(3), 615–635. doi:
10.1007/s101070050107.

Acknowledgements

Henrot, S., Moussaoui, S., Soussen, C., and Brie, D. (2013). Edge-preserving
nonnegative hyperspectral image restoration. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE.
doi: 10.1109/icassp.2013.6637926.

TK was supported by JPSP KAKENHI Grant Number
26249075 and 40401236.
7

Lin, Y., Lee, D., and Saul, L. (2004). Nonnegative deconvolution for time of
arrival estimation. In 2004 IEEE International Conference on Acoustics,
Speech, and Signal Processing. IEEE. doi:10.1109/icassp.2004.1326273.

Ishii, S., Kitamura, G., Segawa, T., Kobayashi, A., Miura, T., Sano, D.,
and Okabe, S. (2014a). Microfluidic quantitative pcr for simultaneous
quantification of multiple viruses in environmental water samples. Appl
Environ Microbiol, 80(24), 7505–11.
Ishii, S., Nakamura, T., Ozawa, S., Kobayashi, A., Sano, D., and Okabe, S.
(2014b). Water quality monitoring and risk assessment by simultaneous
multipathogen quantification. Environ Sci Technol, 48(9), 4744–9.

Liu, B., Zhang, D., Xu, R., Xu, J., Wang, X., Chen, Q., Dong, Q., and
Chou, K. C. (2014). Combining evolutionary information extracted from
frequency profiles with sequence-based kernels for protein remote homology detection. Bioinformatics, 30(4), 472–479.

Ji, Y., Lin, T., and Zha, H. (2009). Mahalanobis distance based nonnegative sparse representation for face recognition.
In 2009 International Conference on Machine Learning and Applications. IEEE.
doi:10.1109/icmla.2009.50.

Ma, J. (2013). Algorithms for non-negatively constrained maximum penalized likelihood reconstruction in tomographic imaging. Algorithms, 6(1),
136–160. doi: 10.3390/a6010136.
Moré, J. J. and Toraldo, G. (1991). On the solution of large quadratic
programming problems with bound constraints. SIAM Journal on Optimization, 1(1), 93–113. doi: 10.1137/0801008.

Joachims, T. (2005). A support vector method for multivariate performance
measures. In L. D. Raedt and S. Wrobel, editors, Proceedings of the
22nd International Conference on Machine Learning (ICML-05), pages
377–384.

Morigi, S., Reichel, L., Sgallari, F., and Zama, F. (2007). An iterative
method for linear discrete ill-posed problems with box constraints. Journal of Computational and Applied Mathematics, 198(2), 505–520. doi:
10.1016/j.cam.2005.06.053.

Johnson, R. and Zhang, T. (2013). Accelerating stochastic gradient descent
using predictive variance reduction. In Advances in Neural Information
Processing Systems 26: Proceedings of a meeting held December 5-8,
2013, Lake Tahoe, Nevada, United States., pages 315–323.

Needell, D., Srebro, N., and Ward, R. (2015). Stochastic gradient descent,
weighted sampling, and the randomized kaczmarz algorithm. Mathematical Programming, 155(1-2), 549–573. doi:10.1007/s10107-015-0864-7.

Kanzow, C. and Klug, A. (2006).
On affine-scaling interiorpoint newton methods for nonlinear minimization with bound constraints. Computational Optimization and Applications, 35(2), 177–197.
doi:10.1007/s10589-006-6514-5.

Ogul, H. and Mumcuoglu, E. U. (2006). Svm-based detection of distant
protein structural relationships using pairwise probabilistic suffix trees.
Comput Biol Chem, 30(4), 292–299.

Kim, D., Sra, S., and Dhillon, I. S. (2007). Fast newton-type methods for
the least squares nonnegative matrix approximation problem. In Proceedings of the 2007 SIAM International Conference on Data Mining, pages 343–354. Society for Industrial and Applied Mathematics.
doi:10.1137/1.9781611972771.31.

Portugal, L. F., Júdice, J. J., and Vicente, L. N. (1994). A comparison of
block pivoting and interior-point algorithms for linear least squares problems with nonnegative variables. Mathematics of Computation, 63(208),
625–625. doi:10.1090/s0025-5718-1994-1250776-4.

Kim, D., Sra, S., and Dhillon, I. S. (2010). Tackling box-constrained optimization via a new projected quasi-newton approach. SIAM Journal on
Scientific Computing, 32(6), 3548–3563. doi:10.1137/08073812x.

Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press,
Princeton, NJ.
Roux, N. L., Schmidt, M., and Bach, F. R. (2012). A stochastic gradient
method with an exponential convergence rate for finite training sets. In
F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Advances
in Neural Information Processing Systems 25 , pages 2663–2671. Curran
Associates, Inc.

Kimura, K., Kudo, M., and Tanaka, Y. (2016). A column-wise update
algorithm for nonnegative matrix factorization in bregman divergence
with an orthogonal constraint. Machine Learning, 103(2), 285–306.
doi:10.1007/s10994-016-5553-0, [pdf].
Kobayashi, A., Sano, D., Hatori, J., Ishii, S., and Okabe, S. (2013). Chickenand duck-associated bacteroides-prevotella genetic markers for detecting
fecal contamination in environmental water. Appl Microbiol Biotechnol,
97(16), 7427–37.

Schmidt, M., Roux, N. L., and Bach, F. (2016). Minimizing finite sums with
the stochastic average gradient. Mathematical Programming, 162(1-2),
83–112. doi:10.1007/s10107-016-1030-6.

Lanckriet, G. R., Deng, M., Cristianini, N., Jordan, M. I., and Noble, W. S.
(2004a). Kernel-based data fusion and its application to protein function
prediction in yeast. Pac Symp Biocomput, -(-), 300–11.

Scott, T. M., Rose, J. B., Jenkins, T. M., Farrah, S. R., and Lukasik, J.
(2002). Microbial source tracking: current methodology and future directions. Appl Environ Microbiol, 68(12), 5796–803.

Lanckriet, G. R., Bie, T. D., Cristianini, N., Jordan, M. I., and Noble, W. S.
(2004b). A statistical framework for genomic data fusion. Bioinformatics,
20(16), 2626–35.

Shalev-Shwartz, S. and Zhang, T. (2013). Stochastic dual coordinate ascent
methods for regularized loss. J. Mach. Learn. Res., 14(1), 567–599.
Shalev-Shwartz, S. and Zhang, T. (2016). Accelerated proximal stochastic
dual coordinate ascent for regularized loss minimization. Mathematical
Programming, 155(1), 105–145.

Landi, G. and Piccolomini, E. L. (2012). NPTool: a Matlab software for nonnegative image restoration with Newton projection methods. Numerical
Algorithms, 62(3), 487–504. doi: 10.1007/s11075-012-9602-x.

Shalev-Shwartz, S., Singer, Y., Srebro, N., and Cotter, A. (2011). Pegasos:
primal estimated sub-gradient solver for SVM. Math. Program., 127(1),
3–30.

Lapin, M., Hein, M., and Schiele, B. (2015). Top-k multiclass svm. In
C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett,
editors, Advances in Neural Information Processing Systems 28 , pages
325–333. Curran Associates, Inc.
Solving Least Squares
Applied Mathematics.

Shashua, A. and Hazan, T. (2005). Non-negative tensor factorization with
applications to statistics and computer vision. In Proceedings of the 22nd
international conference on Machine learning - ICML’05 . ACM Press.
doi:10.1145/1102351.1102451.

Lee, D. D. and Seung, H. S. (2001). Algorithms for non-negative matrix
factorization. In Advances in neural information processing systems,
pages 556–562. [pdf].

Wang, J., Tian, F., Yu, H., Liu, C. H., Zhan, K., and Wang, X. (2017). Diverse non-negative matrix factorization for multiview data representation.
IEEE Trans Cybern, -(-), –.

Liao, L. and Noble, W. S. (2003). Combining pairwise sequence similarity
and support vector machines for detecting remote protein evolutionary
and structural relationships. J Comput Biol, 10(6), 857–68.

Wang, Y. and Ma, S. (2007). Projected barzilai–borwein method for largescale nonnegative image restoration. Inverse Problems in Science and
Engineering, 15(6), 559–583. doi: 10.1080/17415970600881897.

Lin, C.-J. and Moré, J. J. (1999). Newton’s method for large boundconstrained optimization problems. SIAM Journal on Optimization,
9(4), 1100–1127. doi: 10.1137/s1052623498345075.

Xiao, L. and Zhang, T. (2014). A proximal stochastic gradient method with
progressive variance reduction. SIAM Journal on Optimization, 24(4),
2057–2075. doi:10.1137/140961791.

Lawson, C. L. and Hanson, R. J. (1995).
Problems.
Society for Industrial and
doi:10.1137/1.9781611971217.

8

A.2

Zhang, L., Mahdavi, M., and Jin, R. (2013). Linear convergence with condition number independent access of full gradients. In Proceedings of the
26th International Conference on Neural Information Processing Systems, NIPS’13, pages 980–988, USA. Curran Associates Inc.

Proof of Lemma A.2

Lemma A.2 states the following three claims.
• B ∩ S is a closed and convex set.

Zhang, Q., Wang, H., Plemmons, R., and Pauca, V. P. (2007). Spectral
unmixing using nonnegative tensor factorization. In Proceedings of the
45th annual southeast regional conference on ACM-SE 45 . ACM Press.
doi: 10.1145/1233341.1233449.

• (35) is hold.
• (36) is hold.

A
A.1

Apparently, B ∩ S is a closed and convex set because the both
sets are closed and convex. We shall show (35) and then (36).

Proofs and Derivations
Proof of Theorem 1

Proof of (35) To prove (35), it suffices to show the projecShalev-Shwartz et al. (2011) have used the following lemma,
tion from a point z ∈ Rd onto the set B ∩ S is given by
given below, to obtain the bound.
)
( r
rloss
ΠS (z).
(38)
ΠB∩S (z) = min 1,
2
λ kΠS (z)k
Lemma A.1 (Hazan et al. (2007)). Let f1 , . . . , fT be a
sequence of λ-strongly convex functions. Let C be a closed
The projection problem can be expressed as
convex set and define ΠC (w) := argmin kw′ − wk. Let
w ′ ∈C

w1 , . . . , wT +1 be a sequence of vectors such that w1 ∈ C
and for t ≥ 1, wt+1 := ΠC (wt − ∇t /(λt)), where ∇t ∈
∂ft (wt ). Assume that ∀t ∈ N, k∇t k ≤ G. Then, for
∀u ∈ C, it holds that
T
T
1 X
(1 + log(T ))G2
1 X
.
ft (wt ) ≤
ft (u) +
T t=1
T t=1
2λT

min
subject to

1
kx − zk2
wrt x ∈ Rd
2
rloss
kxk2 ≤
, c ⊙ x ≥ 0d .
λ

(39)

With non-negative dual variables β ∈ Rd+ and η ∈ R+ , the
Lagrangian function is given by

(33)

LB∩S (x, β, η) :=

1
kx − zk2
2

η
rloss 
We, too, have used Lemma A.1 to obtain Theorem 1 for
− hβ, c ⊙ xi +
kxk2 −
. (40)
2
λ
our sign-constrained learning problem (5). To this end, we
find the following lemma.
Let
(x⋆ , β⋆ , η⋆ )
be
the
saddle
point
of
minx maxβ,η LB∩S (x, β, η). Then, x⋆ = ΠB∩S (z). At
the saddle point, it holds that ∇x LB∩S = 0, yielding
√
Lemma A.2. Let B be rloss / λ-ball defined as
1
r


x=
(z + c ⊙ β).
(41)
r
loss
η+1
(34)
B := w ∈ Rd kwk ≤
.
λ
The dual objective is written as
and S be the set defined in (3). Then, the intersection
DB∩S (β, η) = min LB∩S (x, β, η)
of the two sets are closed and convex. It holds that
x


1
1
= LB∩S (
(z + c ⊙ β), β, η)
(35)
wt+1 = ΠB∩S wt − ∇Pt (wt )
(42)
η
+
1
λt
η
1
1
kz + c ⊙ βk2 +
+ kzk2 .
=−
for ∀t ∈ N. Furthermore, the optimal solution w⋆ :=
2(η + 1)
2λ 2
argmin P (w) is in the intersection of the two sets.
w∈S
This implies that DB∩S (·, ·) is maximized when β = (−c ⊙
Namely,
z)+ . Note that this does not depend on the value of η. Subw⋆ ∈ B ∩ S.
(36)
stituting this into (41), we have
1
1
x=
(z + c ⊙ (−c ⊙ z)+ ) =
ΠS (z),
(43)
See Subsection A.2 for proof of Lemma A.2. The above
η+1
η+1
lemma suggests that the setting of ft := Pt , C := B ∩ S and
u := w⋆ fulfills the assumptions of Lemma A.1. An upper where the last equality follows from the fast that ΠS (z) = z+
c⊙(−c⊙z)+ which can be shown as follows. The Lagrangian
bound of the norm of the gradient of ft is given by
p
function for the problem of projection of z onto S is given by
(37)
k∇ft (wt )k = k∇Pt (wt )k ≤ rloss λ + LR.
LS (x, β) = LB∩S (x, β, 0), and, with a similar derivation, the
See
Subsection
A.3
for
derivation
of
(37).
By
setting
G
=
dual
objective is DS (β) = DB∩S (β, 0) which is maximized at
√
rloss λ + LR, Theorem 1 is established.
β = (−c ⊙ z)+ yielding ΠS (z) = z + (−c ⊙ z)+ .
9

where the first inequality, the third and fourth equalities,
and the last inequality follow from Assumption 2.1(c), no
1
rloss
1
DB∩S ((−c ⊙ z)+ , η) = − kΠS (z)k2 (η + 1)−1 −
η + kzk2duality gap, (49), and (50), respectively. Therefore, w⋆ ∈
2
2λ
2
(44) B. Furthermore, w⋆ is feasible so w⋆ ∈ S. Hence, (36) is
established.
with the derivative
Next, we find the optimal η. The dual objective is

rloss
1
kΠS (z)k2 (η + 1)−2 −
.
2
2λ
(45)
A.3 Derivation of (37)
Setting the derivative to zero and noting that η is a nonnegative variable, we get
This inequality leads to a bound of The norm of the gradient
!
r
of the loss term in Pt (·) can be bounded as
λ
η⋆ = max 0,
kΠS (z)k − 1 .
(46)
rloss
∇η DB∩S ((−c ⊙ z)+ , η) =

X
∂
⊤
w ; At ) =
Φ(XA
xi ∇φi (hxi , wi)
t
∂w
i∈At
X
≤
kxi k ∇φi (hxi , wi) ≤ kLR. (52)

Substituting this into (43), we obtain
ΠB∩S (z) = x⋆ =

1
p
ΠS (z)
1 + max(0, λ/rloss kΠS (z)k − 1)
i∈At


√
rloss
= min 1, √
ΠS (z). (47)
λ kΠS (z)k
Using this, (37) is derived as

Thus, (38) is established.
k∇ft (wt )k = k∇Pt (wt )k

Proof of (36) We use the following problem dual to (5):




1 ∂
⊤
w ; At )
Φ(XA
≤ λ k∇wt k +
t
k ∂w
r
kLR p
rloss
≤λ
+
≤ rloss λ + LR.
λ
k

2

1 ∗
Φ (−α) wrt α ∈ Rn .
n
(48)
Let α⋆ be the solution optimal to the dual problem (48).
The primal optimal solution can be recovered by


1
(49)
Xα⋆
w⋆ = ΠS
λn
max

−

λ
ΠS
2

Xα
λn

−

A.4

with no duality gap. The loss term in the objective of the
dual problem is bounded from above as
1
1
− Φ∗ (−α) = − maxn (hs, −αi − Φ(s))
n
n s∈R
1
= minn (hs, αi + Φ(s))
n s∈R
1
1
= (h0, αi + Φ(0)) = Φ(0) ≤ rloss .
n
n

(50)

(53)

Derivation of (16)

Exploiting proof techniques used in ProxSDCA (ShalevShwartz and Zhang, 2016), we here limit the form of ∆α to
(t−1)
and ui ∈ −∂φi (zi ).
sq where q := ui − αi

Denote by D0 (α) the objective function of the dual problem (48). Suppose that i-th example is chosen at t-th iterate.
The new value of the regularization term in D0 (α) is given
by

The square norm of the primal optimal solution is bounded
as

 2

 sq

2
λ
λ
X(α + sqei )
1
1
−
≥−
xi
Π
ΠS w̄(t−1) +
S
2
2
2
kw⋆ k = kw⋆ k + kw⋆ k
2
λn
2
λn
2


 2

2
2
λ
s
1 s
1 λ
1
1
≥−
w(t−1) − zi q −
R2 q 2 . (54)
kw⋆ k2 + Φ(X ⊤ w⋆ )
≤ kw⋆ k2 +
2
n
2λ
n
2
λ 2
n
1
1
= kw⋆ k2 + P (w⋆ )
where the first inequality follows from the following inequality
2
λ
!

 2
(51)
λ
Xα⋆
1
1
1
−
ΠS
− Φ∗ (−α⋆ )
= kw⋆ k2 +
(55)
∀v, ∀∆ ∈ Rd , kΠS (v) + ∆k ≥ kΠS (v + ∆)k ,
2
λ
2
λn
n


1 λ
1
1
2
kw⋆ k + Φ∗ (−α⋆ )
= kw⋆ k2 −
and the second
inequality is derived from the fact of w(t−1) =
2
λ 2
n

(t−1)
ΠS w̄
and the assumption of kxi k ≤ R. We shall prove
rloss
1
= − Φ∗ (−α⋆ ) ≤
(55) in Subsection A.5.
λn
λ
10

The improvement of the dual objective is expressed as

• In case of v < 0 and ∆ < −v,

bh (∆ ; v) = 0.5∆2 ≥ 0 = ah (v + ∆).
(65)
D0 (α(t−1) + sqei ) − D0 (α(t−1) )
 2

2
λ
λ
X(α + sqei )
• In case of v < 0 and ∆ ≥ −v,
=−
+
ΠS
w(t−1)
2
λn
2
bh (∆ ; v) − ah (v + ∆) = 0.5∆2 − 0.5(∆ + v)2
1
1
− φi (−αi − sq) + φi (−αi )
n
n
= −v∆ − 0.5v 2 = −0.5((∆ + v) + ∆)v
(66)
1  s 2 2 2 (1 − s)sγ 2
2
R q +
q
≥ −0.5v∆ ≥ 0.5v ≥ 0.
≥−
2λ 
n
2n

s (t)
z αi + φ∗i (−αi ) − φ∗i (−ui ) − z (t) u
+
Therefore, we get bh (∆; v) ≥ ah (v + ∆) for h ∈ I+ . Finally,
n


we assume h ∈ I− .
2
2
γq
s
s
z (t) αi + φ∗i (−αi ) + φi (z (t) ) +
= − q 2 γs−1
(
lb +
2n
n
2
0.5(∆ + v)2
for v ≤ 0,
(56)
bh (∆ ; v) =
(67)
2
0.5∆
for v > 0.
Thus, the value of s maximizing the lower-bound can be
given by
We need to analyze the following three cases:


(t)
∗
(t)
1 z αi + φi (−αi ) + φi (z )
• In case of v ≤ 0,
s = Clip[0,s−1 ]
slb . (57)
+
lb
2
γq 2
bh (∆ ; v) = 0.5(∆ + v)2 ≥ ah (v + ∆).
(68)
Thus, (16) is derived.
• In case of v > 0 and ∆ > −v,

A.5

Derivation of (55)

For h = 1, . . . , d, letting

2

0.5(∆ + (v)+ )
bh (∆; v) := 0.5(∆ + v)2


0.5(∆ + (−v)+ )2
and


2

0.5(v)+
ah (v) := 0.5(v)2


0.5(−v)2+

bh (∆ ; v) = 0.5∆2 ≥ 0 = ah (v + ∆).
for h ∈ I+ ,
for h ∈ I0 ,
for h ∈ I− ,
for h ∈ I+ ,
for h ∈ I0 ,
for h ∈ I− ,

• In case of v > 0 and ∆ ≤ −v,

d
X

bh (∆h ; vh ),

d
X

ah (vh + ∆h )

bh (∆ ; v) − ah (v + ∆) = 0.5∆2 − 0.5(∆ + v)2

(58)

= −v∆ − 0.5v 2 = 0.5(−(∆ + v) − ∆)v
≥ 0.5(−∆)v ≥ 0.5v ≥ 0.

(59)

The above leads to bh (∆; v) ≥ ah (v + ∆) for h ∈ I− .

A.6

RHS of (55) =

(60)

(61)

h=1

To show the inequality (55), it suffices to show that
∀h = 1, . . . , d, ∀v, ∀∆ ∈ R,

bh (∆; v) ≥ ah (v + ∆).

Proof of Theorem 2

A key observation that leads to the discovery of Theorem 2
is the following lemma:

h=1

and

(70)

2

both the sides in (55) can be rewritten as
LHS of (55) =

(69)

(62)

Lemma A.3. Let g : Rd → R ∪ {+∞} be defined as
g(w) := 12 kwk2 + δS (w) where δS (·) is the indicator
function of the feasible region S given in (3). Namely,
δS (w) = +∞ if w 6∈ S; otherwise δS (w) = 0. Then,
with d-dimensional vector c defined in (4), the gradient
of its convex conjugate (Rockafellar, 1970) is expressed
as ∇g ∗ (w̄) = w̄ + c ⊙ (−c ⊙ w̄)+ .

Apparently, bh (∆; v) = ah (v + ∆) for h ∈ I0 . Assume h ∈ I+
See Subsections A.7 for proof of Lemma A.3.
for a while.
The function g defined in Lemma A.3 is 1-strongly convex.
(
Then,
if we view g as a regularization function in replace0.5(∆ + v)2
for v ≥ 0,
bh (∆ ; v) =
(63)
ment
of
the square L2-norm regularizer, the sign-constrained
0.5∆2
for v < 0.
optimization problem (5) can be rewritten as
The following three cases must be considered:
• In case of v ≥ 0,
bh (∆ ; v) = 0.5(∆ + v)2 ≥ ah (v + ∆).

min

λg(w) +

1
Φ(X ⊤ w)
n

wrt

w ∈ Rd .

(71)

This is a class of optimization problems targeted by a vari(64) ant of SDCA named Prox-SDCA (Shalev-Shwartz and Zhang,
11

2016) which maintains the convergence rate of the vanilla
SDCA yet the regularization function can be extended to be
a 1-strongly convex function. The difference from the vanilla
SDCA is that the primal variable is recovered from the gradient of the convex conjugate of g(·) at the end of each iterate.
It can be seen that Algorithm 2 is generated by applying ProxSDCA to our problem setting with g defined in Lemma A.3.
From this observation, Theorem 2 is established.

A.7

Proof of Lemma A.3

The convex conjugate of g is
g∗ (w̄) = max (hw̄, wi − g(w))
w∈Rd


1
2
= max hw̄, wi − kwk − δS (w)
2
w∈Rd


1
2
= max hw̄, wi − kwk
w∈S
2
1
1
= kw̄k2 − min kw − w̄k2 .
2
2 w∈S

(72)

We use Danskin’s theorem to get the derivative as:
∇g ∗ (w̄) = ΠS (w̄).

(73)

12

