---
abstract: '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 sign-constrained 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.'
---

Introduction
============

The problem of regularized loss minimization (e.g. @HasTibFri-book09a) is often described as

\[eq:prob-rlm-uncon\] & P()\^[d]{},\
& P() := \^[2]{} + (\^),\
& := \^[dn]{},

aiming to obtain a linear predictor $\left<{{\bm{w}}},{{\bm{x}}}\right>$ for an unknown input ${{\bm{x}}}\in{{\mathbb{R}}}^{d}$. Therein, $\Phi :{{\mathbb{R}}}^{n}\to{{\mathbb{R}}}$ is a loss function which is the sum of convex losses for $n$ examples: $\Phi({{\bm{z}}}) := \sum_{i=1}^{n}\phi_{i}(z_{i})$ for ${{\bm{z}}}:= \left[z_{1},\dots,z_{n}\right]^\top\in{{\mathbb{R}}}^{n}$. 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* [@Lawson1995solving] to the entries in the model parameter ${{\bm{w}}}\in{{\mathbb{R}}}^{d}$ in the unconstrained minimization problem . We divide the index set of $d$ entries into three exclusive subsets, ${{\mathcal{I}}}_{+}$, ${{\mathcal{I}}}_{0}$, and ${{\mathcal{I}}}_{-}$, as $\{1,\dots,d\}
 =
 {{\mathcal{I}}}_{+}\cup{{\mathcal{I}}}_{0}\cup{{\mathcal{I}}}_{-}$ and impose on the entries in ${{\mathcal{I}}}_{+}$ and ${{\mathcal{I}}}_{-}$,

\[eq:sgncon\] &h\_[+]{},w\_[h]{}0, && h’\_[-]{},w\_[h’]{}0.

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 $x_{h}$ is positively correlated to a binary class label $y\in\{\pm 1\}$, then a positive weight coefficient $w_{h}$ is expected to achieve a better generalization performance than a negative coefficient, because without sign constraints, the entry $w_{h}$ in the optimal solution might be negative due to small sample problem. On the other hand, in case that $x_{h}$ is negatively correlated to the class label, a negative weight coefficient $w_{h}$ 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: [@YuanqingLin2004-icassp], tomographic imaging [@JunMa2013-algo], spectral analysis [@QiangZhang07-asrc], hyperspectral image super-resolution [@DonFuShi16], microbial community pattern detection [@CaiGuKen17], face recognition [@YangfengJi2009-icmla; @HeZheHu13], and non-negative image restoration [@Henrot2013-icassp; @Landi2012-na; @YanfeiWang2007-ipse; @Shashua2005-icml]. In most of them, non-negative least square regression is used as an important ingredient of bigger methods such as non-negative matrix factorization [@lee2001algorithms; @WanTiaYu17; @Kimura2016column; @Fvotte2011algo; @Ding2006ortho].

Several efficient algorithms for the non-negative least square regression have been developed. The active set method by @Lawson1995solving has been widely used in many years, and several work [@DongminKim2010-siamjsc; @DongminKim2007-siam; @Bierlaire1991-laa; @Portugal1994comparison; @More91-siamjo; @ChihJenLin1999-siamjo; @Morigi2007-joam] have accelerated optimization by combining the active set method with the projected gradient approach. Interior point methods [@Bellavia2006; @Heinkenschloss99-mp; @Kanzow06-coa] have been proposed as an alternative algorithm for non-negative 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 sign-constrained regularized loss minimization problem with generic loss functions. A surge of algorithms for unconstrained regularized empirical loss minimization have been developed such as SAG [@Roux12a-sag; @Schmidt2016-sag], SVRG [@Johnson13a-svrg], Prox-SVRG [@LinXiao2014-siamjo], SAGA [@Defazio2014-nips], Kaczmarz [@Needell2015], EMGD [@LijunZhang2013-nips], and Finito [@defazio2014finito]. This study focuses on two popular algorithms, Pegasos [@Shalev-Shwartz11-pegasos] and SDCA [@Shalev-Shwartz2013a-SDCA]. 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 $\eta_{t}=1/(\lambda 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.

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

-   Two optimization algorithms for the sign-constrained regularized loss minimization, called *SC-Pega* and *SC-SDCA*, were developed by simply inserting the *sign correction step*, introduced in Section \[s:scpega\], to the original Pegasos and SDCA.

-   Our theoretical analysis ensures that both SC-Pega and SC-SDCA do not degrade the convergence rates of the original algorithms.

-   Two attractive applications, where the sign-constrained 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 [@LiaNob03-jcb].

-   Experimental results demonstrate significant improvement of generalization performance by introducing sign constraints in both two applications.

Problem Setting
===============

The feasible region can be expressed simply as

\[eq:fearegion\] := { \^[d]{}| \_[d]{}}

where ${{\bm{c}}}= \left[ c_{1},\dots,c_{d} \right]^\top\in\{0,\pm 1\}^{d}$, each entry is given by

\[eq:scvec-c-def\] c\_[h]{} :=

+1 &h\_[+]{},\
0 &h\_[0]{},\
-1 &h\_[-]{}.

Using ${{\mathcal{S}}}$, the optimization problem discussed in this paper can be expressed as

\[eq:prob-rlm-signcon\] & P().

\[assum:four-for-rlm-signcon\] Throughout this paper, the following assumptions are used: $$\begin{aligned}
  \text{(a) } & \text{$\Phi(\cdot)$ is a convex function.}
  &
  \text{(b) } & \text{$\frac{1}{n}\Phi({{\bm{0}}})\le {r_{\text{loss}}}$.}
  \\
  \text{(c) } & \text{$\forall {{\bm{s}}}\in{{\mathbb{R}}}^{n}$, $\Phi({{\bm{s}}})\ge 0$.}
  &
  \text{(d) } & \text{$\forall i$, $\lVert{{\bm{x}}}_{i}\rVert \le R$. }\end{aligned}$$

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
           Name          Definition                                                                                     Label                    Type                  ${r_{\text{loss}}}$
  ---------------------- ------------------------------------------------------------------------------------ -------------------------- --------------------- -----------------------------------
   Classical hinge loss  $\phi_{i}(s) := \max(0,1-y_{i}s)$                                                       $y_{i}\in\{\pm 1\}$         $1$-Lipschitz                     $1$

   Smoothed hinge loss   $\phi_{i}(s) :=                                                                         $y_{i}\in\{\pm 1\}$      $(1/\gamma)$-smooth         $1-\frac{\gamma}{2}$
                               \begin{cases}                                                                                                                   
                                 1 - y_{i}s -0.5\gamma \,\, &\text{ if } y_{i}s\in(-\infty,1-\gamma],                                                          
                                 \\                                                                                                                            
                                 (1-y_{i}s)^{2}/(2\gamma)  \,\, &\text{ if } y_{i}s\in(1-\gamma,1),                                                            
                                 \\                                                                                                                            
                                 0 &\text{ if } y_{i}s\in [1,+\infty).                                                                                         
                               \end{cases}$                                                                                                                    

      Logistic loss      $\phi_{i}(s) := \log( 1 + \exp(-y_{i}s))$                                               $y_{i}\in\{\pm 1\}$         $0.25$-smooth                  $\log(2)$

    Square error loss    $\phi_{i}(s) := 0.5( s - y_{i} )^{2}$                                                 $y_{i}\in{{\mathbb{R}}}$       $1$-smooth        $\lVert{{\bm{y}}}\rVert^{2}/(2n)$

   Absolute error loss   $\phi_{i}(s) := | s - y_{i} |$                                                        $y_{i}\in{{\mathbb{R}}}$      $1$-Lipschitz       $\lVert{{\bm{y}}}\rVert_{1}/n$
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Most of widely used loss functions satisfy the above assumptions. Several examples of such loss functions are described in Table \[tab:loss\]. 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 ${{\bm{w}}}_{\star}:={\mathop{\textrm{argmin}}\limits}_{{{\bm{w}}}\in{{\mathcal{S}}}}P({{\bm{w}}}). $ We assume two types of loss functions: *$L$-Lipschitz continuous* function and *$(1/\gamma)$-smooth* function. Function $\phi_{i}:{{\mathbb{R}}}\to{{\mathbb{R}}}$ is said to be an $L$-Lipschitz continuous funciton if

\[eq:Lipschitz-def\] s,, |\_[i]{}(s+)-\_[i]{}(s)| L ||.

Such functions are often said shortly to be *$L$-Lipschitz* in this paper. Function $\phi_{i}:{{\mathbb{R}}}\to{{\mathbb{R}}}$ is a $(1/\gamma)$-smooth function if its derivative function is $L$-Lipschitz. For an index subset ${{\mathcal{A}}}\subseteq\{1,\dots,n\}$ and a vector ${{\bm{v}}}\in{{\mathbb{R}}}^{n}$, let ${{\bm{v}}}_{{{\mathcal{A}}}}$ be the subvector of ${{\bm{v}}}$ containing entries corresponding to ${{\mathcal{A}}}$. Let ${{\bm{X}}}_{{{\mathcal{A}}}}$ be a sub-matrix in ${{\bm{X}}}$ containing columns corresponding to ${{\mathcal{A}}}$. Let $\Phi(\cdot\,;\,{{\mathcal{A}}}):{{\mathbb{R}}}^{|{{\mathcal{A}}}|}\to{{\mathbb{R}}}$ be defined as

(\_;) := \_[i]{}\_[i]{}(s\_[i]{}).

Sign-Constrained Pegasos {#s:scpega}
========================

In the original Pegasos algorithm [@Shalev-Shwartz11-pegasos], $\phi_{i}$ is assumed to be the classical hinge loss function (See Table \[tab:loss\] for the definition). Each iterate consists of three steps: the *mini-batch selection step*, the *gradient step*, and the *projection-onto-ball step*. Mini-batch selection step chooses a subset ${{\mathcal{A}}}_{t}\subseteq\{1,\dots,n\}$ from $n$ examples at random. The cardinality of the subset is predefined as $|{{\mathcal{A}}}_{t}| = k$. Gradient step computes the gradient of

P\_[t]{}() := \^[2]{} + (\_[\_[t]{}]{}\^;\_[t]{}).

which approximates the objective function $P({{\bm{w}}})$. The current solution ${{\bm{w}}}_{t}$ is moved toward the opposite gradient direction as

\_[t+1/2]{} &:= \_[t]{} - P\_[t]{}(\_[t]{})\
&= - \_[\_[t]{}]{} (\_[\_[t]{}]{}\^\_[t]{};\_[t]{}).

At the projection-onto-ball step, the norm of the solution is shortened to be $\frac{1}{\sqrt{\lambda}\lVert{{\bm{w}}}_{t+1/2}\rVert}$ if the norm is over $\frac{1}{\sqrt{\lambda}\lVert{{\bm{w}}}_{t+1/2}\rVert}$:

\_[t+1]{} := ( 1, ) \_[t+1/2]{}.

The projection-onto-ball step plays an important role in getting a smaller upper-bound of the norm of the gradient of the regularization term in the objective, which eventually reduces the number of iterates to attain an $\epsilon$-approximate solution (i.e. $P(\tilde{{{\bm{w}}}})-P({{\bm{w}}}_{\star})\le\epsilon$).

In the algorithm developed in this study, we simply inserts between those two steps, a new step that corrects the sign of each entry in the current solution ${{\bm{w}}}$ as

w\_[h]{}

(0,w\_[h]{})&h\_[+]{},\
(0,w\_[h]{})&h\_[-]{},\
w\_[h]{}&h\_[0]{},

which can be rewritten equivalently as ${{\bm{w}}}\leftarrow {{\bm{w}}}+ {{\bm{c}}}\odot(-{{\bm{c}}}\odot{{\bm{w}}})_{+}$ where the operator $(\cdot)_{+}$ is defined as $\forall {{\bm{x}}}\in{{\mathbb{R}}}^{d}$, $({{\bm{x}}})_{+}:=\max({{\bm{0}}},{{\bm{x}}})$.

Data matrix ${{\bm{X}}}\in{{\mathbb{R}}}^{d\times n}$, loss function $\Phi:{{\mathbb{R}}}^{n}\to{{\mathbb{R}}}$, regularization parameter $\lambda\in{{\mathbb{R}}}$, sign constraint parameter ${{\bm{c}}}\in\{\pm 1,0\}^{d}$, and mini-batch size $k$. **begin** ${{\bm{w}}}_{1}:={{\bm{0}}}_{d}$; {Initialization} Choose ${{\mathcal{A}}}_{t}\subseteq\{1,\dots,n\}$ uniformly at random such that $|A_{t}|=k$. ${{\bm{w}}}_{t+1/3}
  :=
  \frac{t-1}{t}{{\bm{w}}}_{t} -
  \frac{1}{\lambda t}{{\bm{X}}}_{{{\mathcal{A}}}_{t}}\nabla\Phi({{\bm{X}}}_{{{\mathcal{A}}}_{t}}^\top{{\bm{w}}}_{t-1};{{\mathcal{A}}}_{t})$; ${{\bm{w}}}_{t+2/3}
  :=
  {{\bm{w}}}_{t+1/3}
  + {{\bm{c}}}\odot(-{{\bm{c}}}\odot{{\bm{w}}}_{t+1/3})_{+}$; ${{\bm{w}}}_{t+1}
  :=
  \min\left(
  1, \sqrt{{r_{\text{loss}}}\lambda^{-1}}\lVert{{\bm{w}}}_{t+2/3}\rVert^{-1}
  \right)
  {{\bm{w}}}_{t+2/3}$; **return** $\tilde{{{\bm{w}}}}:=\sum_{t=1}^{T}{{\bm{w}}}_{t}/T$; **end.**

The algorithm can be summarized as Algorithm \[alg:srpega-mbtch\]. Here, the loss function is not limited to the classical hinge loss. In the projection-onto-ball step, the solution is projected onto $\sqrt{{r_{\text{loss}}}\lambda^{-1}}$-ball instead of $(1/\sqrt{\lambda})$-ball to handle more general settings. Recall that ${r_{\text{loss}}}=1$ if $\phi_{i}$ is the hinge loss employed in the original Pegasos. It can be shown that the objective gap is bounded as follows.

\[thm:srpega-bound\] Consider Algorithm \[alg:srpega-mbtch\]. If $\phi_{i}$ are $L$-Lipschitz continuous, it holds that

- P(\_) ( + L R )\^[2]{} .

See Subsection \[ss:proof-thm:srpega-bound\] for proof of Theorem \[thm:srpega-bound\]. This bound is exactly same as the original Pegasos, yet Algorithm \[alg:srpega-mbtch\] contains the sign correction step.

Sign-Constrained SDCA
=====================

The original SDCA is a framework for the unconstrained problems . In SDCA, a dual problem is solved instead of the primal problem. Namely, the dual objective is maximized in a iterative fashion with respect to the dual variables ${{\bm{\alpha}}}:=\left[\alpha_{1},\dots,\alpha_{n}\right]^\top\in{{\mathbb{R}}}^{n}$. The problem dual to the unconstrained problem  is given by

\[eq:dual-rlm-uncon\] & D()\^[n]{},

where

&D() := - \^[2]{} - \^[\*]{}(-).

To find the maximizer of $D({{\bm{\alpha}}})$, a single example $i$ is chosen randomly at each iterate $t$, and a single dual variable $\alpha_{i}$ is optimized with the other $(n-1)$ variables $\alpha_{1},\dots,\alpha_{i-1}$, $\alpha_{i+1},\dots,\alpha_{n}$ frozen. If we denote by ${{\bm{\alpha}}}^{(t-1)}\in{{\mathbb{R}}}^{n}$ the value of the dual vector at the previous iterate $(t-1)$, the dual vector is updated as ${{\bm{\alpha}}}^{(t)}:={{\bm{\alpha}}}^{(t-1)}+\Delta\alpha{{\bm{e}}}_{i}$ where $\Delta\alpha\in{{\mathbb{R}}}$ is determined so that $\Delta \alpha \in {\mathop{\textrm{argmax}}\limits}_{\Delta \alpha\in{{\mathbb{R}}}}D_{t}(\Delta \alpha\,;\,{{\bm{w}}}^{(t-1)})$ where ${{\bm{w}}}^{(t-1)}=\frac{1}{\lambda n}{{\bm{X}}}{{\bm{\alpha}}}^{(t-1)}$ and $$\begin{gathered}
  D_{t}(\Delta \alpha\,;\,{{\bm{w}}})
  :=
  -\frac{\lambda}{2}\left\lVert{{\bm{w}}}+ \frac{\Delta \alpha}{\lambda n}{{\bm{x}}}_{i}\right\rVert^{2}
  -\frac{1}{n}\phi^{*}_{i}(-\alpha^{(t-1)}_{i}-\Delta \alpha). \end{gathered}$$ In case of the hinge loss, the maximizer of $D_{t}(\cdot\,;\,{{\bm{w}}}^{(t-1)})$ can be found within $O(d)$ computation. The primal variable ${{\bm{w}}}^{(t)}$ can also be maintained within $O(d)$ computation by ${{\bm{w}}}^{(t)}:={{\bm{w}}}^{(t-1)} + \frac{\Delta\alpha}{\lambda n}{{\bm{x}}}_{i}$.

Now let us move on the sign-constrained problem. In addition to Algorithm \[alg:srpega-mbtch\] that is derived from Pegasos, we present another algorithm based on SDCA for solving the minimizer of $P({{\bm{w}}})$ subject to the sign constraint ${{\bm{c}}}\odot{{\bm{w}}}\ge{{\bm{0}}}_{d}$. Like Algorithm \[alg:srpega-mbtch\] that has been designed by inserting the sign correction step into the original Pegasos iterate, the new algorithm has been developed by simply adding the sign correction step in each SDCA iterate. The resultant algorithm is described in Algorithm \[alg:srsdca\].

Data matrix ${{\bm{X}}}\in{{\mathbb{R}}}^{d\times n}$, loss function $\Phi:{{\mathbb{R}}}^{n}\to{{\mathbb{R}}}$, regularization parameter $\lambda\in{{\mathbb{R}}}$, and sign constraint parameter ${{\bm{c}}}\in\{\pm 1,0\}^{d}$. **begin** ${{\bm{\alpha}}}^{(0)}:={{\bm{0}}}_{n}$; $\bar{{{\bm{w}}}}^{(0)}:={{\bm{0}}}_{d}$; ${{\bm{w}}}^{(0)}:={{\bm{0}}}_{d}$; {Initialization} $\Delta \alpha \in {\mathop{\textrm{argmax}}\limits}_{\Delta \alpha\in{{\mathbb{R}}}}D_{t}(\Delta \alpha\,;\,{{\bm{w}}}^{(t-1)})$; $\bar{{{\bm{w}}}}^{(t)}:=\bar{{{\bm{w}}}}^{(t-1)} + \frac{\Delta\alpha}{\lambda n}{{\bm{x}}}_{i}$; ${{\bm{w}}}^{(t)} :=
  \bar{{{\bm{w}}}}^{(t)}
  + {{\bm{c}}}\odot(-{{\bm{c}}}\odot\bar{{{\bm{w}}}}^{(t)})_{+}$; **return** $\tilde{{{\bm{w}}}}:=\frac{1}{T-T_{0}}\sum_{t=T_{0}+1}^{T}{{\bm{w}}}^{(t-1)}$; **end.**

For some loss functions, maximization at step 5 in Algorithm \[alg:srsdca\] cannot be given in a closed form. Alternatively, step 4 can be replaced to

\[eq:sdca-prox-update\] [4: ]{}& := sq,\
&s := \_[\[0,s\^[-1]{}\_\]]{} ( + )s\_.

Therein, we have defined $s_{\text{lb}}:=\lambda n \gamma / (\lambda n \gamma+R^{2})$, $z^{(t)}:=\left<{{\bm{w}}}^{(t-1)},{{\bm{x}}}_{i}\right>$, $q^{(t)}:=-\nabla\phi_{i}(z^{(t)})-\alpha_{i}^{(t-1)}$, and $\text{Clip}_{[a,b]}(x) := \max(a,\min(b,x))$. See Subsection \[ss:deriv-eq:sdca-prox-update\] for derivation of . We have found the following theorem that states the required number of iterates guaranteeing the expected primal objective gap below a threshold $\epsilon$ under the sign constraints.

\[thm:converg-srsdca\] Consider Algorithm \[alg:srsdca\]. In case that $\phi_{i}$ are $L$-Lipschitz continuous (i.e. ), it holds that ${{\mathbb{E}}}[P(\tilde{{{\bm{w}}}})]-P({{\bm{w}}}_{\star})\le\epsilon$ if $T$ and $T_{0}$ are specified so that

T\_[0]{} + { 0, n}

and

T T\_[0]{} + { n, }

where $G:=4R^{2}L^{2}$. If $\phi_{i}$ are hinge loss functions, then $G:=R^{2}L^{2}$. In case that $\phi_{i}$ are $(1/\gamma)$-smooth, ${{\mathbb{E}}}[P(\tilde{{{\bm{w}}}})]-P({{\bm{w}}}_{\star})\le\epsilon$ is established if

T &gt; T\_[0]{} ( n + ) ( ( n + ) ).

See Subsections \[ss:proof-thm:converg-srsdca\] for proof of Theorem \[thm:converg-srsdca\]. Theorem \[thm:converg-srsdca\] suggests that the convergence rate of Algorithm \[alg:srsdca\] is not deteriorated compared to the original SDCA in both cases of $L$-Lipschitz and smooth losses, despite insertion of the sign correction step.

Multiclass Classification
=========================

In this section, we extend our algorithms to the multi-class classification setting of $m$ classes. Here, the model parameter is a ${{\bm{W}}}\in{{\mathbb{R}}}^{d\times m}$ instead of a vector ${{\bm{w}}}\in{{\mathbb{R}}}^{d}$. The loss function for each example ${{\bm{x}}}_{i}\in{{\mathbb{R}}}^{d}$ is of an $m$-dimensional vector. Here, the prediction is supposed to be done by taking the class with the maximal score among $s_{1}:=\left<{{\bm{w}}}_{1},{{\bm{x}}}\right>, \dots$, and $s_{m}:=\left<{{\bm{w}}}_{m},{{\bm{x}}}\right>$. Here, without loss of generality, the set of the class labels are given by ${{\mathcal{Y}}}:=\{1,\dots,m\}$. Several loss functions $\phi^{\text{m}}_{i}:{{\mathbb{R}}}^{m}\to{{\mathbb{R}}}$ are used for multiclass classification as follows.

-   Soft-max loss:

    \^\_[i]{}() := ( \_[y]{} ( s\_[y]{} -s\_[y\_[i]{}]{} ) )

    Therein, $y_{i}$ is the true class label of $i$-th example.

-   Max-hinge loss;

    \^\_[i]{}() := \_[y]{} ( s\_[y]{} -s\_[y\_[i]{}]{} + \_[y,y\_[i]{}]{} ).

-   Top-$k$ hinge loss [@lapin-nips2015]:

    \^\_[i]{}() := \_[j=1]{}\^[k]{} ( (-\_[y\_[i]{}]{}\^)+ - \_[y\_[i]{}]{} )\_[\[j\]]{}.

    Therein, $x_{[j]}$ denotes the $j$-th largest value in a vector ${{\bm{x}}}\in{{\mathbb{R}}}^{m}$.

The objective function for learning ${{\bm{W}}}\in{{\mathbb{R}}}^{d\times m}$ is defined as

P\^() := \_\^[2]{} + \_[i=1]{}\^[n]{}\^\_[i]{}(\^\_[i]{}).

The learning problem discussed is minimization of $P^{\text{m}}({{\bm{W}}})$ with respect to ${{\bm{W}}}$ subject to sign constraints

(h,j)\_[+]{}, &W\_[h,j]{}0,\
(h’,j’)\_[-]{}, &W\_[h’,j’]{}0,

with two exclusive set ${{\mathcal{E}}}_{+}$ and ${{\mathcal{E}}}_{-}$ such that

\_[+]{}\_[-]{}{(h,j)\^[2]{}|h, j}.

Introducing ${{\bm{C}}}\in\{0,\pm1\}^{d\times m}$ as

C\_[h,j]{} :=

+1 &(h,j)\_[+]{},\
-1 &(h,j)\_[-]{},\
0 &

the feasible region can be expressed as

\^ := { \^[dm]{}| \_[dm]{} }.

The goal is here to develop algorithms that find

\_:=\_[\^]{}P\^().

Define $\Phi^{\text{m}}(\cdot\,;\,{{\mathcal{A}}}):{{\mathbb{R}}}^{m\times k}\to{{\mathbb{R}}}$ as

\^(\_;) := \_[i]{}\^\_[i]{}(\_[i]{})

where ${{\bm{S}}}_{{{\mathcal{A}}}}$ is the horizontal concatenation of columns in ${{\bm{S}}}:=\left[{{\bm{s}}}_{1},\dots,{{\bm{s}}}_{n}\right]\in{{\mathbb{R}}}^{m\times n}$ selected by a minibatch ${{\mathcal{A}}}$. We here use the following assumptions: $\Phi^{\text{m}}(\cdot)$ is a convex function; $\Phi^{\text{m}}({{\bm{O}}})\le n{r_{\text{loss}}}$; $\forall {{\bm{S}}}\in{{\mathbb{R}}}^{m\times n}$, $\Phi^{\text{m}}({{\bm{S}}})\ge 0$; $\forall i$, $\lVert{{\bm{x}}}_{i}\rVert \le R$.

By extending Algorithm \[alg:srpega-mbtch\], an algorithm for minimization of $P^{\text{m}}({{\bm{W}}})$ subject to the sign constraints can be developed as described in Algorithm \[alg:srpega-mbtch-mc\].

Data matrix ${{\bm{X}}}\in{{\mathbb{R}}}^{d\times n}$, loss function $\Phi^{\text{m}}:{{\mathbb{R}}}^{m\times n}\to{{\mathbb{R}}}$, regularization parameter $\lambda\in{{\mathbb{R}}}$, sign constraint parameter ${{\bm{C}}}\in\{0,\pm 1\}^{d\times m}$, and mini-batch size $k$. **begin** ${{\bm{W}}}_{1}:={{\bm{0}}}_{d}$; {Initialization} Choose ${{\mathcal{A}}}_{t}\subseteq\{1,\dots,n\}$ uniformly at random such that $|A_{t}|=k$. ${{\bm{Z}}}_{t}:={{\bm{W}}}_{t-1}^\top{{\bm{X}}}_{{{\mathcal{A}}}_{t}}$; ${{\bm{W}}}_{t+1/3}
  :=
  \frac{t-1}{t}{{\bm{W}}}_{t} -
  \frac{1}{\lambda t}{{\bm{X}}}_{{{\mathcal{A}}}_{t}}\left(\nabla\Phi({{\bm{Z}}}_{t}\,;\,{{\mathcal{A}}}_{t})\right)^\top$; ${{\bm{W}}}_{t+2/3}
  :=
  {{\bm{W}}}_{t+1/3}
  + {{\bm{C}}}\odot\max({{\bm{O}}},-{{\bm{C}}}\odot{{\bm{W}}}_{t+1/3})$; ${{\bm{W}}}_{t+1}
  :=
  \min\left(
  1, \frac{{r_{\text{loss}}}}{\sqrt{\lambda}\lVert{{\bm{W}}}_{t+2/3}\rVert_{\text{F}}}
  \right)
  {{\bm{W}}}_{t+2/3}$; **return** $\tilde{{{\bm{W}}}}:=\sum_{t=1}^{T}{{\bm{W}}}_{t}/T$; **end.**

The SDCA-based learning algorithm can also be developed for the multiclass classification task. In the algorithm, the dual variables are represented as a matrix ${{\bm{A}}}:=\left[{{\bm{\alpha}}}_{1},\dots,{{\bm{\alpha}}}_{n}\right]\in{{\mathbb{R}}}^{m\times n}$. At each iterate $t$, one of $n$ columns, ${{\bm{\alpha}}}_{i}$, is chosen at random instead of choosing one of a dual variable to update the matrix as ${{\bm{A}}}^{(t)}:= {{\bm{A}}}^{(t-1)}+\Delta{{\bm{\alpha}}}{{\bm{e}}}_{i}^\top$ where we have used the iterate number $(t)$ as the superscript of ${{\bm{A}}}$. To determine the value of $\Delta{{\bm{\alpha}}}$, the following auxiliary funcition is introduced: $$\begin{gathered}
  D_{t}(\Delta {{\bm{\alpha}}}\,;\,{{\bm{W}}})
  := 
  -\frac{\lVert{{\bm{x}}}_{i}\rVert^{2}}{2\lambda^{2}n}
  \lVert\Delta{{\bm{\alpha}}}\rVert^{2}
  \\
  -\left<{{\bm{W}}}^\top
  {{\bm{x}}}_{i}, 
  \Delta{{\bm{\alpha}}}\right>
  -\phi^{*}_{i}(-{{\bm{\alpha}}}^{(t-1)}_{i}-\Delta {{\bm{\alpha}}}). \end{gathered}$$

Data matrix ${{\bm{X}}}\in{{\mathbb{R}}}^{d\times n}$, loss function $\Phi:{{\mathbb{R}}}^{m\times n}\to{{\mathbb{R}}}$, regularization parameter $\lambda\in{{\mathbb{R}}}$, and sign constraint parameter ${{\bm{C}}}\in\{\pm 1,0\}^{d\times m}$. **begin** ${{\bm{A}}}^{(0)}:={{\bm{O}}}$; $\bar{{{\bm{W}}}}^{(0)}:={{\bm{O}}}$; ${{\bm{W}}}^{(0)}:={{\bm{O}}}$; {Initialization} $\Delta {{\bm{\alpha}}}\in {\mathop{\textrm{argmax}}\limits}_{\Delta{{\bm{\alpha}}}\in{{\mathbb{R}}}^{m}}D_{t}(\Delta{{\bm{\alpha}}}\,;\,{{\bm{W}}}^{(t-1)})$; $\bar{{{\bm{W}}}}^{(t)}:=\bar{{{\bm{W}}}}^{(t-1)} + \frac{1}{\lambda n}{{\bm{x}}}_{i}\Delta{{\bm{\alpha}}}^\top$; ${{\bm{W}}}^{(t)}
  :=
  \bar{{{\bm{W}}}}^{(t)}
  + {{\bm{C}}}\odot\max({{\bm{O}}},-{{\bm{C}}}\odot\bar{{{\bm{W}}}}^{(t)})$; **return** $\tilde{{{\bm{W}}}}:=\frac{1}{T-T_{0}}\sum_{t=T_{0}+1}^{T}{{\bm{W}}}^{(t-1)}$; **end.**

For both algorithms (Algorithms \[alg:srpega-mbtch-mc\] and \[alg:srsdca-mc\]), we can bound the required number of iterations similar to those presented in Theorems \[thm:srpega-bound\] and \[thm:converg-srsdca\].

Experiments
===========

In this section, experimental results are reported in order to illustrate the effects of the sign constraints on classification and to demonstrate the convergence behavior.

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.

#### *E. coli* Prediction {#e.coli-prediction .unnumbered}

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 many parts of the world [@ScoRosJen02-aem]. In this experiment, the data points with *E. coli* counts over 500 most probable number (MPN)/100 mL are assigned to positive class, and the others are negative. The hydrological and water quality monitoring data are used for predicting *E. coli* counts to be positive or negative.

For ensuring the microbial safety in water usage, it is meaningful to predict *E. coli* counts on a real-time basis. The concentration of *E. coli* in water, which is measured by culture-dependent methods [@KobSanHat13-amb], has been used to monitor the fecal contamination in water environment, and has been proved to be effective to prevent waterborne infectious diseases in varied water usage styles. On the other hand, the real-time monitoring of *E. coli* counts has not yet been achieved. It take at least ten hours to obtain *E. coli* counts by culture-dependent methods, and also at least several hours are needed to measure the concentration of *E. coli* by culture-independent methods [@IshNakOza14-est; @IshKitSeg14-aem], such as polymerase chain reaction. Since it is possible to measure the some of the hydrological and water quality data with real-time sensors, the real-time prediction of *E. coli* counts will be realized if the hydrological and water quality data are available for the *E. coli* count prediction.

Many training examples are required to obtain a better generalization performance. A serious issue, however, is that measuring the concentration of *E. Coli* is time-consuming and the cost of reagents is expensive. We here demonstrate that 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 explanatory variables, WT, pH, EC, SS, DO, BOD, TN, TP, and flow rate. The explanatory variable $pH$ is divided into two variables, $\text{pH}_{+}\leftarrow\max(0,\text{pH}-7)$ and $\text{pH}_{-}\leftarrow\max(0,7-\text{pH})$. It is well-known, in the field of water engineering, that *E. coli* is increased, as WT, EC, SS, BOD, TN, and TP are larger, and as $\text{pH}_{+}$, $\text{pH}_{-}$，DO, and the flow rate are smaller. From this fact, we restrict the sign of entries in the predictor parameter ${{\bm{w}}}$ as follows.

-   Coefficients $w_{h}$ of six explanatory variables, WT, EC, SS, BOD, TN, and TP must be non-negative.

-   Coefficients $w_{h}$ of four explanatory variables, $\text{pH}_{+}$, $\text{pH}_{-}$, DO, flow rate must be non-positive.

We actually measured the concentrations of *E. coli* 177 times from December 5th, 2011 to April 17th, 2013. We obtained 177 data points including 88 positives and 89 negatives. We chose ten examples out of 177 data points at random to use them for training, and the other 167 examples were used for testing. The prediction performance is evaluated by the precision recall break-even point (PRBEP) [@Joachims05-icml] and the ROC score. We compared the classical SVM with the sign-constrained SVM (SC-SVM) to examine the effects of sign constraints. We repeated this procedure 10,000 times and obtained 10,000 PRBEP and 10,000 ROC scores.

[ll]{} (a) PRBEP & (b) ROC score\
\
![ Improvements of generalization performances on *E. Coli* prediction. \[fig:prot404-demo332-mizu\]](001-k.demo332_02.prbep.eps "fig:"){width="22.00000%"} & $\qquad$ ![ Improvements of generalization performances on *E. Coli* prediction. \[fig:prot404-demo332-mizu\]](002-k.demo332_02.roc.eps "fig:"){width="22.00000%"}

SC-SVM achieved significant improvement compared to the classical SVM. SC-SVM achieved PRBEP and ROC score of 0.808 and 0.863 on average over 10,000 trials, whereas those of 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 \[fig:prot404-demo332-mizu\]. Positive improvements of ROC scores were obtained in 8,932 trials out of 10,000 trials, whereas ROC scores were decreased only for 796 trials. For PRBEP, positive improvements were obtained on 7,349 trials, whereas deteriorations were observed only on 1,069 trials.

  ----------------------------------------------------------------- ------------------------------------------------------------- ------------------------------------------------------------------
  \(a) Covtype                                                      \(b) W8a                                                      \(c) Phishing
  ![image](003-k.demo423_05.f.covtype.gap.eps){width="30.00000%"}   ![image](004-k.demo423_05.f.w8a.gap.eps){width="30.00000%"}   ![image](005-k.demo423_05.f.phishing.gap.eps){width="30.00000%"}
  ----------------------------------------------------------------- ------------------------------------------------------------- ------------------------------------------------------------------

#### Protein Function Prediction {#protein-function-prediction .unnumbered}

   Category        SC-SVM              SVM
  ---------- ------------------- ---------------
      1       **0.751** (0.011)   0.730 (0.010)
      2       **0.740** (0.016)   0.680 (0.015)
      3       **0.753** (0.011)   0.721 (0.011)
      4       **0.762** (0.010)   0.734 (0.010)
      5       **0.769** (0.012)   0.691 (0.013)
      6       **0.690** (0.014)   0.614 (0.014)
      7       **0.713** (0.024)   0.618 (0.022)
      8       **0.725** (0.019)   0.667 (0.019)
      9       **0.655** (0.024)   0.578 (0.023)
      10      **0.743** (0.016)   0.710 (0.014)
      11      **0.535** (0.019)   0.492 (0.018)
      12      **0.912** (0.011)   0.901 (0.011)

  : ROC Scores for protein function prediction. \[tab:demo383\]

In the field of molecular biology, understanding the functions of proteins is positioned as a key step for elucidation of cellular mechanisms. Sequence similarities have been a major mean to predict the function of an unannotated protein. At the beginning of this century, the prediction accuracy has been improved by combining sequence similarities with discriminative learning. The method, named SVM-Pairwise [@LiaNob03-jcb], uses a feature vector that contains pairwise similarities to annotated protein sequences. Several other literature [@LiuZhaXu14; @OguMum06; @LanBieCri04; @LanDenCri04] have also provided empirical evidences for the fact that the SVM-Pairwise approach is a powerful framework. Basically, if $n$ proteins are in a training dataset, the feature vector has $n$ entries, $x_{1}, \dots, x_{n}$. If we suppose that the first $n_{+}$ proteins in the training set are in positive class and the rest are negative, then the first $n_{+}$ similarities $x_{1}, \dots, x_{n_{+}}$ are sequence similarities to positive examples, and $x_{n_{+}+1}, \dots, x_{n}$ are similarities to negative examples. The $n$-dimensional vectors are fed to SVM and get the weight coefficients ${{\bm{w}}}:=\left[w_{1},\dots,w_{n}\right]^\top$. Then, the prediction score of the target protein is expressed as

\_[i=1]{}\^[n\_[+]{}]{}w\_[i]{}x\_[i]{} + \_[i’=n\_[+]{}+1]{}\^[n]{}w\_[i]{}x\_[i]{}.

The input protein sequence is predicted to have some particular cellular function if the score is over a threshold. It should be preferable that the first $n_{+}$ weight coefficients $w_{1},\dots,w_{n_{+}}$ are non-negative and that the rest of $(n-n_{+})$ weight coefficients $w_{n_{+}+1},\dots,w_{n}$ are non-positive. The SVM-Pairwise approach does not ensure those requirements. Meanwhile, our approach is capable to explicitly impose the constraints of

w\_[1]{}0,…,w\_[n\_[+]{}]{}0, w\_[n\_[+]{}+1]{}0,…,w\_[n]{}0.

This approach was applied to predict protein functions in *Saccharomyces cerevisiae* (*S. cerevisiae*). The annotations of the protein functions are provided in MIPS Comprehensive Yeast Genome Database (CYGD). The dataset contains 3,583 proteins. The Smith-Waterman similarities available from <https://noble.gs.washington.edu/proj/sdp-svm/> were used as sequence similarities among the proteins. The number of categories was 12. Some proteins have multiple cellular functions. Indeed, 1,343 proteins in the dataset have more than one function. From this reason, we pose 12 independent binary classification tasks instead of a single multi-class classification task. 3,583 proteins were randomly splited in half to get two datasets. The one was used for training, and the other was for testing. For 12 classification tasks, we repeated this procedure 100 times, and we obtained 100 ROC scores.

Table \[tab:demo383\] reports the ROC scores averaged over 100 trials and the standard deviations for 12 binary classification tasks. The sign constraints significantly surpassed the classical training for all 12 tasks. Surprisingly, we observed that the ROC score of SC-SVM is larger than that of the classical SVM in every trial.

Convergence
-----------

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 SC-Pega, we set the mini-batch size to $k=10$ and $k=100$. In this experiments, we used the smoothed hinge loss with $\gamma=0.01$ and $\lambda=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 \[fig:demo423-gap\] depicts the primal objective gap against epochs, where the primal objective gap is defined as $P({{\bm{w}}})-P({{\bm{w}}}_{\star})$. 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.

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 sign-constrained 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.

Acknowledgements {#acknowledgements .unnumbered}
================

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

Bellavia, S., Macconi, M., and Morini, B. (2006). An interior point newton-like method for non-negative least-squares problems with degenerate solution. , [**13**]{}(10), 825–846. doi: 10.1002/nla.502.

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

Cai, Y., Gu, H., and Kenney, T. (2017). Learning microbial community structures with supervised and unsupervised non-negative matrix factorization. , [**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. .

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. , [**25**]{}(5), 2337–52.

F[é]{}votte, C. and Idier, J. (2011). Algorithms for nonnegative matrix factorization with the $\beta$-divergence. , [**23**]{}(9), 2421–2456. doi:10.1162/neco\_a\_00168, [\[pdf\]](https://ts3.pl.cs.gunma-u.ac.jp/tsattach1/kato/170717/Fevotte-2011,-Algorithms-for-nonnegative-matrix-factorization-with-the-beta-divergence.pdf).

Hastie, T., Tibshirani, R., and Friedman, J. (2009). . Springer, 2nd edition.

Hazan, E., Agarwal, A., and Kale, S. (2007). Logarithmic regret algorithms for online convex optimization. , [**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. , [**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. , [**86**]{}(3), 615–635. doi: 10.1007/s101070050107.

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.

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. , [**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. , [**48**]{}(9), 4744–9.

Ji, Y., Lin, T., and Zha, H. (2009). Mahalanobis distance based non-negative sparse representation for face recognition. In [*2009 International Conference on Machine Learning and Applications*]{}. [IEEE]{}. doi:10.1109/icmla.2009.50.

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.

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.

Kanzow, C. and Klug, A. (2006). On affine-scaling interior-point newton methods for nonlinear minimization with bound constraints. , [**35**]{}(2), 177–197. doi:10.1007/s10589-006-6514-5.

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.

Kim, D., Sra, S., and Dhillon, I. S. (2010). Tackling box-constrained optimization via a new projected quasi-newton approach. , [**32**]{}(6), 3548–3563. doi:10.1137/08073812x.

Kimura, K., Kudo, M., and Tanaka, Y. (2016). A column-wise update algorithm for nonnegative matrix factorization in bregman divergence with an orthogonal constraint. , [**103**]{}(2), 285–306. doi:10.1007/s10994-016-5553-0, [\[pdf\]](https://ts3.pl.cs.gunma-u.ac.jp/tsattach1/kato/170717/Kimura-2016,-A-column-wise-update-algorithm-for-nonnegative-matrix-factorization-in-Bregman-divergence-with-an-orthogonal-constraint.pdf).

Kobayashi, A., Sano, D., Hatori, J., Ishii, S., and Okabe, S. (2013). Chicken- and duck-associated bacteroides-prevotella genetic markers for detecting fecal contamination in environmental water. , [**97**]{}(16), 7427–37.

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. , [**-**]{}(-), 300–11.

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

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

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.

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

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\]](https://ts3.pl.cs.gunma-u.ac.jp/tsattach1/kato/170717/Daniel-Lee-2001,-Algorithms-for-non-negative-matrix-factorization.pdf).

Liao, L. and Noble, W. S. (2003). Combining pairwise sequence similarity and support vector machines for detecting remote protein evolutionary and structural relationships. , [**10**]{}(6), 857–68.

Lin, C.-J. and Mor[é]{}, J. J. (1999). Newton’s method for large bound-constrained optimization problems. , [**9**]{}(4), 1100–1127. doi: 10.1137/s1052623498345075.

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.

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. , [**30**]{}(4), 472–479.

Ma, J. (2013). Algorithms for non-negatively constrained maximum penalized likelihood reconstruction in tomographic imaging. , [**6**]{}(1), 136–160. doi: 10.3390/a6010136.

Mor[é]{}, J. J. and Toraldo, G. (1991). On the solution of large quadratic programming problems with bound constraints. , [**1**]{}(1), 93–113. doi: 10.1137/0801008.

Morigi, S., Reichel, L., Sgallari, F., and Zama, F. (2007). An iterative method for linear discrete ill-posed problems with box constraints. , [ **198**]{}(2), 505–520. doi: 10.1016/j.cam.2005.06.053.

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

Ogul, H. and Mumcuoglu, E. U. (2006). Svm-based detection of distant protein structural relationships using pairwise probabilistic suffix trees. , [**30**]{}(4), 292–299.

Portugal, L. F., Jú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. , [**63**]{}(208), 625–625. doi:10.1090/s0025-5718-1994-1250776-4.

Rockafellar, R. T. (1970). . 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.

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

Scott, T. M., Rose, J. B., Jenkins, T. M., Farrah, S. R., and Lukasik, J. (2002). Microbial source tracking: current methodology and future directions. , [**68**]{}(12), 5796–803.

Shalev-Shwartz, S. and Zhang, T. (2013). Stochastic dual coordinate ascent methods for regularized loss. , [**14**]{}(1), 567–599.

Shalev-Shwartz, S. and Zhang, T. (2016). Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. , [**155**]{}(1), 105–145.

Shalev-Shwartz, S., Singer, Y., Srebro, N., and Cotter, A. (2011). primal estimated sub-gradient solver for [SVM]{}. , [**127**]{}(1), 3–30.

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.

Wang, J., Tian, F., Yu, H., Liu, C. H., Zhan, K., and Wang, X. (2017). Diverse non-negative matrix factorization for multiview data representation. , [**-**]{}(-), –.

Wang, Y. and Ma, S. (2007). Projected barzilaiborwein method for large-scale nonnegative image restoration. , [**15**]{}(6), 559–583. doi: 10.1080/17415970600881897.

Xiao, L. and Zhang, T. (2014). A proximal stochastic gradient method with progressive variance reduction. , [**24**]{}(4), 2057–2075. doi:10.1137/140961791.

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.

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.

Proofs and Derivations
======================

Proof of Theorem \[thm:srpega-bound\] {#ss:proof-thm:srpega-bound}
-------------------------------------

@Shalev-Shwartz11-pegasos have used the following lemma, given below, to obtain the bound.

\[lem:pega-lem01\] Let $f_{1},\dots,f_{T}$ be a sequence of $\lambda$-strongly convex functions. Let ${{\mathcal{C}}}$ be a closed convex set and define $\Pi_{{{\mathcal{C}}}}({{\bm{w}}}):={\mathop{\textrm{argmin}}\limits}_{{{\bm{w}}}'\in{{\mathcal{C}}}}\|{{\bm{w}}}'-{{\bm{w}}}\|$. Let ${{\bm{w}}}_{1},\dots,{{\bm{w}}}_{T+1}$ be a sequence of vectors such that ${{\bm{w}}}_{1}\in{{\mathcal{C}}}$ and for $t\ge 1$, ${{\bm{w}}}_{t+1}:=\Pi_{{{\mathcal{C}}}}({{\bm{w}}}_{t}-\nabla_{t}/(\lambda t))$, where $\nabla_{t}\in\partial f_{t}({{\bm{w}}}_{t})$. Assume that $\forall t\in{{\mathbb{N}}}$, $\|\nabla_{t}\|\le G$. Then, for $\forall {{\bm{u}}}\in{{\mathcal{C}}}$, it holds that $$\begin{aligned}
    \frac{1}{T}\sum_{t=1}^{T}f_{t}({{\bm{w}}}_{t})
    \le
    \frac{1}{T}\sum_{t=1}^{T}f_{t}({{\bm{u}}})
    +
    \frac{(1+\log(T))G^{2}}{2\lambda T}. 
  \end{aligned}$$

We, too, have used Lemma \[lem:pega-lem01\] to obtain Theorem \[thm:srpega-bound\] for our sign-constrained learning problem . To this end, we find the following lemma.

\[lem:hazen-applicable\] Let ${{\mathcal{B}}}$ be ${r_{\text{loss}}}/\sqrt{\lambda}$-ball defined as

:= {\^[d]{}| }.

and ${{\mathcal{S}}}$ be the set defined in . Then, the intersection of the two sets are closed and convex. It holds that

\[eq:update-lem:hazen-applicable\] \_[t+1]{} = \_ (\_[t]{}-P\_[t]{}(\_[t]{}) )

for $\forall t\in{{\mathbb{N}}}$. Furthermore, the optimal solution ${{\bm{w}}}_{\star} := {\mathop{\textrm{argmin}}\limits}_{{{\bm{w}}}\in{{\mathcal{S}}}}P({{\bm{w}}})$ is in the intersection of the two sets. Namely,

\[eq:opt-lem:hazen-applicable\] \_.

See Subsection \[ss:proof-lem:hazen-applicable\] for proof of Lemma \[lem:hazen-applicable\]. The above lemma suggests that the setting of $f_{t}:=P_{t}$, ${{\mathcal{C}}}:={{\mathcal{B}}}\cap{{\mathcal{S}}}$ and ${{\bm{u}}}:={{\bm{w}}}_{\star}$ fulfills the assumptions of Lemma \[lem:pega-lem01\]. An upper bound of the norm of the gradient of $f_{t}$ is given by

\[eq:ub-for-setting-G-in-pega\] f\_[t]{}(\_[t]{}) = P\_[t]{}(\_[t]{}) + LR.

See Subsection \[ss:deriv-eq:ub-for-setting-G-in-pega\] for derivation of . By setting $G=\sqrt{{r_{\text{loss}}}\lambda} + LR$, Theorem \[thm:srpega-bound\] is established.

Proof of Lemma \[lem:hazen-applicable\] {#ss:proof-lem:hazen-applicable}
---------------------------------------

Lemma \[lem:hazen-applicable\] states the following three claims.

-   ${{\mathcal{B}}}\cap{{\mathcal{S}}}$ is a closed and convex set.

-   is hold.

-   is hold.

Apparently, ${{\mathcal{B}}}\cap{{\mathcal{S}}}$ is a closed and convex set because the both sets are closed and convex. We shall show and then .

#### Proof of  {#proof-of .unnumbered}

To prove , it suffices to show the projection from a point ${{\bm{z}}}\in{{\mathbb{R}}}^{d}$ onto the set ${{\mathcal{B}}}\cap{{\mathcal{S}}}$ is given by

\[eq:update-prime-lem:hazen-applicable\] \_() = { 1, } \_().

The projection problem can be expressed as

& -\^[2]{} \^[d]{}\
& \^[2]{}, \_[d]{}.

With non-negative dual variables ${{\bm{\beta}}}\in{{\mathbb{R}}}^{d}_{+}$ and $\eta\in{{\mathbb{R}}}_{+}$, the Lagrangian function is given by $$\begin{gathered}
  {{\mathcal{L}}}_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}({{\bm{x}}},{{\bm{\beta}}},\eta)
  :=
  \frac{1}{2}\|{{\bm{x}}}-{{\bm{z}}}\|^{2}
  \\
  -
  \left<{{\bm{\beta}}},{{\bm{c}}}\odot{{\bm{x}}}\right>
  +
  \frac{\eta}{2}
  \left(
  \|{{\bm{x}}}\|^{2}
  -
  \frac{{r_{\text{loss}}}}{\lambda}
  \right). \end{gathered}$$ Let $({{\bm{x}}}_{\star},{{\bm{\beta}}}_{\star},\eta_{\star})$ be the saddle point of $\min_{{{\bm{x}}}}\max_{{{\bm{\beta}}},\eta} {{\mathcal{L}}}_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}({{\bm{x}}},{{\bm{\beta}}},\eta)$. Then, ${{\bm{x}}}_{\star} = \Pi_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}({{\bm{z}}})$. At the saddle point, it holds that $\nabla_{{{\bm{x}}}}  {{\mathcal{L}}}_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}={{\bm{0}}}$, yielding

\[eq:01-proof-of-lem:pegaproj-onto-B-cap-S\] = (+).

The dual objective is written as

\_(,) &= \_\_(,,)\
&= \_((+),,)\
&= -+\^[2]{} + + \^[2]{}.

This implies that ${{\mathcal{D}}}_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}(\cdot,\cdot)$ is maximized when ${{\bm{\beta}}}= (-{{\bm{c}}}\odot{{\bm{z}}})_{+}$. Note that this does not depend on the value of $\eta$. Substituting this into , we have

\[eq:02-proof-of-lem:pegaproj-onto-B-cap-S\] = (+(-)\_[+]{}) = \_(),

where the last equality follows from the fast that $\Pi_{{{\mathcal{S}}}}({{\bm{z}}})={{\bm{z}}}+{{\bm{c}}}\odot(-{{\bm{c}}}\odot{{\bm{z}}})_{+}$ which can be shown as follows. The Lagrangian function for the problem of projection of ${{\bm{z}}}$ onto ${{\mathcal{S}}}$ is given by ${{\mathcal{L}}}_{{{\mathcal{S}}}}({{\bm{x}}},{{\bm{\beta}}}) = {{\mathcal{L}}}_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}({{\bm{x}}},{{\bm{\beta}}},0)$, and, with a similar derivation, the dual objective is ${{\mathcal{D}}}_{{{\mathcal{S}}}}({{\bm{\beta}}}) = {{\mathcal{D}}}_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}({{\bm{\beta}}},0)$ which is maximized at ${{\bm{\beta}}}= (-{{\bm{c}}}\odot{{\bm{z}}})_{+}$ yielding $\Pi_{{{\mathcal{S}}}}({{\bm{z}}}) = {{\bm{z}}}+(-{{\bm{c}}}\odot{{\bm{z}}})_{+}$.

Next, we find the optimal $\eta$. The dual objective is

\_((-)\_[+]{},) = -\_()\^[2]{}(+1)\^[-1]{} - + \^[2]{}

with the derivative

\_\_((-)\_[+]{},) = \_()\^[2]{}(+1)\^[-2]{} - .

Setting the derivative to zero and noting that $\eta$ is a non-negative variable, we get

\_ = ( 0, \_()-1 ).

Substituting this into , we obtain $$\begin{gathered}
  \Pi_{{{\mathcal{B}}}\cap{{\mathcal{S}}}}({{\bm{z}}})
  =
  {{\bm{x}}}_{\star}
  =
  \frac{1}{1+\max( 0, \sqrt{\lambda/{r_{\text{loss}}}}
    \left\lVert\Pi_{{{\mathcal{S}}}}({{\bm{z}}})\right\rVert-1 )}
  \Pi_{{{\mathcal{S}}}}({{\bm{z}}})
  \\
  =
  \min\left\{1,\frac{\sqrt{{r_{\text{loss}}}}}{\sqrt{\lambda}
     \left\lVert\Pi_{{{\mathcal{S}}}}({{\bm{z}}})\right\rVert}\right\}\Pi_{{{\mathcal{S}}}}({{\bm{z}}}). \end{gathered}$$ Thus, is established.

#### Proof of  {#proof-of-1 .unnumbered}

We use the following problem dual to :

\[eq:dual-rlm-signcon\] - \_()\^[2]{} -\^[\*]{}(-) \^[n]{}.

Let ${{\bm{\alpha}}}_{\star}$ be the solution optimal to the dual problem . The primal optimal solution can be recovered by

\[eq:wst-recovery-from-alphst\] \_ = \_(\_)

with no duality gap. The loss term in the objective of the dual problem is bounded from above as

\[eq:loss-in-dual-bounded\] -\^[\*]{}(-) &= -\_[\^[n]{}]{} ( - () )\
& = \_[\^[n]{}]{} ( + () )\
&= ( + () ) = () [r\_]{}.

The square norm of the primal optimal solution is bounded as

&\_\^[2]{} = \_\^[2]{} + \_\^[2]{}\
& \_\^[2]{} + ( \_\^[2]{} + (\^\_) )\
&= \_\^[2]{} + P(\_)\
&= \_\^[2]{} + ( - \_()\^[2]{} -\^[\*]{}(-\_) )\
&= \_\^[2]{} - ( \_\^[2]{} + \^[\*]{}(-\_) )\
&= -\^[\*]{}(-\_)

where the first inequality, the third and fourth equalities, and the last inequality follow from Assumption \[assum:four-for-rlm-signcon\](c), no duality gap, , and , respectively. Therefore, ${{\bm{w}}}_{\star}\in{{\mathcal{B}}}$. Furthermore, ${{\bm{w}}}_{\star}$ is feasible so ${{\bm{w}}}_{\star}\in{{\mathcal{S}}}$. Hence, is established.

Derivation of  {#ss:deriv-eq:ub-for-setting-G-in-pega}
--------------

This inequality leads to a bound of The norm of the gradient of the loss term in $P_{t}(\cdot)$ can be bounded as $$\begin{gathered}
  \left\lVert
  \frac{\partial}{\partial{{\bm{w}}}} \Phi({{\bm{X}}}_{{{\mathcal{A}}}_{t}}^\top{{\bm{w}}}\,;\,{{\mathcal{A}}}_{t})
  \right\rVert
  =
  \left\lVert  
  \sum_{i\in{{\mathcal{A}}}_{t}}{{\bm{x}}}_{i} \nabla \phi_{i}(\left<{{\bm{x}}}_{i},{{\bm{w}}}\right>)
  \right\rVert
  \\
  \le
  \sum_{i\in{{\mathcal{A}}}_{t}}  \left\lVert {{\bm{x}}}_{i}  \right\rVert
  \nabla \phi_{i}(\left<{{\bm{x}}}_{i},{{\bm{w}}}\right>)
  \le
  kLR. \end{gathered}$$ Using this, is derived as

f\_[t]{}(\_[t]{}) &= P\_[t]{}(\_[t]{})\
& \_[t]{} + (\_[\_[t]{}]{}\^;\_[t]{})\
& + + LR.

Derivation of  {#ss:deriv-eq:sdca-prox-update}
--------------

Exploiting proof techniques used in ProxSDCA [@Shalev-Shwartz2013a-Accelerated], we here limit the form of $\Delta\alpha$ to $sq$ where $q:=u_{i}-\alpha_{i}^{(t-1)}$ and $u_{i}\in-\partial\phi_{i}(z_{i})$.

Denote by $D^{0}({{\bm{\alpha}}})$ the objective function of the dual problem . Suppose that $i$-th example is chosen at $t$-th iterate. The new value of the regularization term in $D^{0}({{\bm{\alpha}}})$ is given by $$\begin{gathered}
  -\frac{\lambda}{2}
  \left\lVert\Pi_{{{\mathcal{S}}}}\left(\frac{{{\bm{X}}}({{\bm{\alpha}}}+sq{{\bm{e}}}_{i})}{\lambda n}\right)\right\rVert^{2}
  \ge
  -\frac{\lambda}{2}
  \left\lVert\Pi_{{{\mathcal{S}}}}\left(\bar{{{\bm{w}}}}^{(t-1)}\right)
  +
  \frac{sq}{\lambda n}{{\bm{x}}}_{i}\right\rVert^{2}
  \\
  \ge
  -\frac{\lambda}{2}
  \left\lVert{{\bm{w}}}^{(t-1)}\right\rVert^{2}
  -
  \frac{s}{n}z_{i}q
  -
  \frac{1}{2\lambda}
  \left(\frac{s}{n}\right)^{2}R^{2}q^{2}. \end{gathered}$$ where the first inequality follows from the following inequality

\[eq:ub-of-gst-2nd\] , \^[d]{}, \_()+ \_(+),

and the second inequality is derived from the fact of ${{\bm{w}}}^{(t-1)}=\Pi_{{{\mathcal{S}}}}\left(\bar{{{\bm{w}}}}^{(t-1)}\right)$ and the assumption of $\lVert{{\bm{x}}}_{i}\rVert\le R$. We shall prove in Subsection \[ss:deriv-eq:ub-of-gst-2nd\].

The improvement of the dual objective is expressed as

& D\^[0]{}(\^[(t-1)]{}+sq\_[i]{})-D\^[0]{}(\^[(t-1)]{})\
&= - \_()\^[2]{} + \^[(t-1)]{}\^[2]{}\
&-\_[i]{}(-\_[i]{}-sq) +\_[i]{}(-\_[i]{})\
& - ()\^[2]{}R\^[2]{}q\^[2]{} + q\^[2]{}\
&+ ( z\^[(t)]{}\_[i]{} + \_[i]{}\^[\*]{}(-\_[i]{})-\_[i]{}\^[\*]{}(-u\_[i]{}) - z\^[(t)]{}u )\
&= - q\^[2]{}s\_\^[-1]{} + ( z\^[(t)]{}\_[i]{} + \_[i]{}\^[\*]{}(-\_[i]{}) + \_[i]{}(z\^[(t)]{}) + )

Thus, the value of $s$ maximizing the lower-bound can be given by

s = \_[\[0,s\^[-1]{}\_\]]{} ( + )s\_.

Thus, is derived.

Derivation of  {#ss:deriv-eq:ub-of-gst-2nd}
--------------

For $h=1,\dots,d$, letting

[[b]{}]{}\_[h]{}(;v) :=

0.5(+(v)\_[+]{})\^[2]{} &h\_[+]{},\
0.5(+v)\^[2]{} &h\_[0]{},\
0.5(+(-v)\_[+]{})\^[2]{} &h\_[-]{},

and

[[a]{}]{}\_[h]{}(v) :=

0.5(v)\_[+]{}\^[2]{} &h\_[+]{},\
0.5(v)\^[2]{} &h\_[0]{},\
0.5(-v)\_[+]{}\^[2]{} &h\_[-]{},

both the sides in can be rewritten as

= \_[h=1]{}\^[d]{}[[b]{}]{}\_[h]{}(\_[h]{};v\_[h]{}),

and

= \_[h=1]{}\^[d]{}[[a]{}]{}\_[h]{}(v\_[h]{}+\_[h]{})

To show the inequality , it suffices to show that

h=1,…,d, v, , [[b]{}]{}\_[h]{}(;v) [[a]{}]{}\_[h]{}(v+).

Apparently, ${{b}}_{h}(\Delta;v) = {{a}}_{h}(v+\Delta)$ for $h\in{{\mathcal{I}}}_{0}$. Assume $h\in{{\mathcal{I}}}_{+}$ for a while.

[[b]{}]{}\_[h]{}(;v) =

0.5(+v)\^[2]{} &v0,\
0.5\^[2]{} &v&lt; 0.

The following three cases must be considered:

-   In case of $v\ge 0$,

    [[b]{}]{}\_[h]{}(;v) = 0.5(+v)\^[2]{} [[a]{}]{}\_[h]{}(v+).

-   In case of $v< 0$ and $\Delta<-v$,

    [[b]{}]{}\_[h]{}(;v) = 0.5\^[2]{} 0 = [[a]{}]{}\_[h]{}(v+).

-   In case of $v< 0$ and $\Delta\ge-v$,

    &[[b]{}]{}\_[h]{}(;v)-[[a]{}]{}\_[h]{}(v+) = 0.5\^[2]{} - 0.5(+v)\^[2]{}\
    &= - v- 0.5v\^[2]{} = -0.5 ((+v)+)v\
    &-0.5 v 0.5v\^[2]{}0.

Therefore, we get ${{b}}_{h}(\Delta;v) \ge {{a}}_{h}(v+\Delta)$ for $h\in{{\mathcal{I}}}_{+}$. Finally, we assume $h\in{{\mathcal{I}}}_{-}$.

[[b]{}]{}\_[h]{}(;v) =

0.5(+v)\^[2]{} &v0,\
0.5\^[2]{} &v&gt; 0.

We need to analyze the following three cases:

-   In case of $v\le 0$,

    [[b]{}]{}\_[h]{}(;v) = 0.5(+v)\^[2]{} [[a]{}]{}\_[h]{}(v+).

-   In case of $v> 0$ and $\Delta>-v$,

    [[b]{}]{}\_[h]{}(;v) = 0.5\^[2]{} 0 = [[a]{}]{}\_[h]{}(v+).

-   In case of $v> 0$ and $\Delta\le-v$,

    &[[b]{}]{}\_[h]{}(;v)-[[a]{}]{}\_[h]{}(v+) = 0.5\^[2]{} - 0.5(+v)\^[2]{}\
    &= - v- 0.5v\^[2]{} = 0.5 (-(+v)-)v\
    &0.5 (-)v 0.5v\^[2]{}0.

The above leads to ${{b}}_{h}(\Delta;v) \ge {{a}}_{h}(v+\Delta)$ for $h\in{{\mathcal{I}}}_{-}$.

Proof of Theorem \[thm:converg-srsdca\] {#ss:proof-thm:converg-srsdca}
---------------------------------------

A key observation that leads to the discovery of Theorem \[thm:converg-srsdca\] is the following lemma:

\[lem:nabla-convconj-g-corrects-sign\] Let $g:{{\mathbb{R}}}^{d}\to{{\mathbb{R}}}\cup\{+\infty\}$ be defined as $g({{\bm{w}}}) := \frac{1}{2}\lVert{{\bm{w}}}\rVert^{2} + \delta_{{{\mathcal{S}}}}({{\bm{w}}})$ where $\delta_{{{\mathcal{S}}}}(\cdot)$ is the indicator function of the feasible region ${{\mathcal{S}}}$ given in . Namely, $\delta_{{{\mathcal{S}}}}({{\bm{w}}})=+\infty$ if ${{\bm{w}}}\not\in{{\mathcal{S}}}$; otherwise $\delta_{{{\mathcal{S}}}}({{\bm{w}}})=0$. Then, with $d$-dimensional vector ${{\bm{c}}}$ defined in , the gradient of its convex conjugate [@rockafellar70convex] is expressed as $\nabla g^{*}(\bar{{{\bm{w}}}}) =
    \bar{{{\bm{w}}}}
    + {{\bm{c}}}\odot(-{{\bm{c}}}\odot\bar{{{\bm{w}}}})_{+}$.

See Subsections \[ss:proof-lem:nabla-convconj-g-corrects-sign\] for proof of Lemma \[lem:nabla-convconj-g-corrects-sign\].

The function $g$ defined in Lemma \[lem:nabla-convconj-g-corrects-sign\] is $1$-strongly convex. Then, if we view $g$ as a regularization function in replacement of the square L2-norm regularizer, the sign-constrained optimization problem  can be rewritten as

& g() + (\^) \^[d]{}.

This is a class of optimization problems targeted by a variant of SDCA named Prox-SDCA [@Shalev-Shwartz2013a-Accelerated] 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(\cdot)$ at the end of each iterate. It can be seen that Algorithm \[alg:srsdca\] is generated by applying Prox-SDCA to our problem setting with $g$ defined in Lemma \[lem:nabla-convconj-g-corrects-sign\]. From this observation, Theorem \[thm:converg-srsdca\] is established.

Proof of Lemma \[lem:nabla-convconj-g-corrects-sign\] {#ss:proof-lem:nabla-convconj-g-corrects-sign}
-----------------------------------------------------

The convex conjugate of $g$ is

g\_[\*]{}(|) &= \_[\^[d]{}]{} ( - g() )\
&= \_[\^[d]{}]{} ( - \^[2]{} - \_() )\
&= \_ ( - \^[2]{} )\
&= |\^[2]{} - \_ -|\^[2]{}.

We use Danskin’s theorem to get the derivative as:

g\^[\*]{}(|) = \_(|).
