## 3 The SMO-like Algorithm for the Nonsmooth Dual Problem of \(\varepsilon\)-In SVR
### Decomposition and Solution Based on Brent's Method  
The SMO algorithm updates only two variables in each iteration such that \(\alpha_{i}^{k+1}=\alpha_{i}^{k}-d_{j}\) and \(\alpha_{j}^{k+1}=\alpha_{j}^{k}+d_{j}\) to satisfy the equality constraint in (22). \(\alpha_{i}^{k}\) and \(\alpha_{j}^{k}\) represent the constant old parameter values, while \(d_{j}\) denotes the update length. By substituting \(\alpha_{i}=\alpha_{i}^{k}-d_{j}\) and \(\alpha_{j}=\alpha_{j}^{k}+d_{j}\) into (22) and discarding the constant terms, the decomposed problem for a single variable, \(d_{j}\), is as follows. \[ \begin{split}&\min\limits_{d_{j}\in R^{1}}\hat{J}\big{(}d_{j} \big{)}=\!\frac{1}{2}a_{ij}d_{j}^{2}+b_{ij}d_{j}+T(\alpha_{i}^{k}-d_{j})+T( \alpha_{j}^{k}+d_{j})+\varepsilon|\alpha_{i}^{k}-d_{j}|+\varepsilon|\alpha_{j }^{k}+d_{j}|\\ &\text{subject to }\quad lb\leq d_{j}\leq ub\end{split}  \tag{23}\]  
where \(lb=\max(-\hat{\mathcal{C}}-\alpha_{j}^{k},-\hat{\mathcal{C}}+\alpha_{i}^{k})\) and \(ub=\min(\hat{\mathcal{C}}-\alpha_{j}^{k},\hat{\mathcal{C}}+\alpha_{i}^{k})\), \(a_{ij}=K_{ii}+K_{jj}-2K_{ij}>0\), \(b_{ij}=\
abla f_{q}\big{(}\mathbf{\alpha}^{k}\big{)}_{j}-\
abla f_{q}\big{(}\mathbf{ \alpha}^{k}\big{)}_{i}\) with \(f_{q}\Big{(}\mathbf{\alpha}^{k}\Big{)}=\frac{1}{2}\Big{(}\mathbf{\alpha}^{k}\Big{)}^{T} \mathbf{K}\Big{(}\mathbf{\alpha}^{k}\Big{)}+\mathbf{p}^{T}\mathbf{\alpha}^{k}\) which is the quadratic part of the loss (22). **Definition 1** (Violating pair). : _If \(\{i,j\}\in\{1,\ldots,L\}\) and \(-\
abla f(\mathbf{\alpha})_{i}-\varepsilon sign^{+}(\alpha_{i})>-\
abla f(\mathbf{ \alpha})_{j}-\varepsilon sign^{-}\left(\alpha_{j}\right)\), then \(\{i,j\}\) is a \"violating pair\" where \(f(\mathbf{\alpha})=\frac{1}{2}\mathbf{\alpha}^{T}\mathbf{K}\mathbf{\alpha}+\mathbf{p}^{T}\mathbf{\alpha} +\sum\limits_{s=1}^{L}T(\alpha_{s})\) is the smooth part of the loss (22), \(sign^{+}(\alpha_{i})\stackrel{{\text{def}}}{{=}} \begin{cases}1,& \text{if }\alpha_{i}\geq 0\\ -1,&\text{if }\alpha_{i}<0\end{cases} \) and \(sign^{-}(\alpha_{i})\stackrel{{\text{def}}}{{=}}\begin{cases}1,& \text{if }\alpha_{i}>0\\ -1,&\text{if }\alpha_{i}\leq 0 where \(\breve{f}^{\prime}_{+}(d_{j})=\
abla\breve{f}(d_{j})+\epsilon sign^{+}(\alpha^{k}_{ j}+d_{j})-\epsilon sign^{-}(\alpha^{k}_{i}-d_{j})\) is the right-hand-side derivative of the loss function (23), \(\breve{f}(d_{j})=\frac{1}{2}a_{ij}d_{j}^{2}+b_{ij}d_{j}+T(\alpha^{k}_{i}-d_{j}) +T(\alpha^{k}_{j}+d_{j})\) is the smooth part of the loss (23), and \(m_{1}=\min\left(\alpha^{k}_{i},-\alpha^{k}_{j}\right)\) and \(m_{2}=\max\left(\alpha^{k}_{i},-\alpha^{k}_{j}\right)\) are the break points of this loss function. For the first case of (24), \(\partial\breve{f}(0)\in(0,\infty)\) since the pair \(\{i,j\}\) is a violating pair and satisfies \(\
abla\breve{f}(0)=\
abla f(\mathbf{\alpha})_{j}-\
abla f(\mathbf{\alpha})_{i}> \epsilon sign^{+}(\alpha_{i})-\epsilon sign^{-}(\alpha_{j})>2\varepsilon\) where \(d_{j}=m_{1}\leq m_{2}\) for this case. Similarly, for the second case of (24), \(\partial\breve{f}(0)\in(0,\infty)\) since \(\
abla\breve{f}(0)>0\) where \(d_{j}=m_{2}\geq m_{1}\). For the last case of (24), \(\breve{f}^{\prime}_{+}(0)=\
abla\breve{f}(0)+\epsilon sign^{+}(\alpha^{k}_{j} )-\epsilon sign^{-}(\alpha^{k}_{i})=\
abla f(\mathbf{\alpha})_{j}-\
abla f(\mathbf{ \alpha})_{i}+\epsilon sign^{-}(\alpha_{j})-\epsilon sign^{+}(\alpha_{i})>0\) for \(d_{j}\
eq m_{1}\) and \(d_{j}\
eq m_{2}\) since the pair \(\{i,j\}\) is a violating pair. Therefore, \(d^{*}_{j}<0\) since all subgradients at \(d_{j}=0\) are positive and the problem in (23) is strictly convex. If \(\{i,j\}\) is a violating pair and \(a_{ij}=K_{ii}+K_{jj}-2K_{ij}>0\), problem (23) has a global optimum defined as follows:  
\[d^{*}_{j}= \begin{cases}m_{1},\text{ if }0\leq\
abla\breve{f}(m_{1})\leq 2 \varepsilon\text{ and }lb\leq m_{1}\leq 0\\ m_{2},\text{ if }-2\varepsilon\leq\
abla\breve{f}(m_{2})\leq 0\text{ and }lb\leq m_{2}\leq 0\\ \{d_{j}|\breve{f}^{\prime}_{+}(d_{j})=0,lb\leq d_{j}<0\},\text{ otherwise}\end{cases}