## 3 The SMO-like Algorithm for the Nonsmooth Dual Problem of \(\varepsilon\)-In SVR
### Working Set Selection  
The SMO algorithm solves the optimization problem by optimizing only two Lagrange multipliers in each iteration. The procedure for determining these two Lagrange multipliers, called the working set selection procedure, is the most critical part of the SMO algorithm that affects its computational cost. The WSS procedure should be both easy to compute and provide a sufficient reduction in the consecutive loss function values. To achieve this, the proposed WSS procedure relies on defining an upper bound for the second-order Taylor polynomial approximation of consecutive loss functions and selects the following easy-to-compute working set that satisfies being a violating pair. \[ \begin{array}{ll}\text{(1)}&\text{For all t, s define }a_{ts}=K_{tt}+K_{ss}-2K_{ts}>0\\ &\text{select}\\ &i\in\text{argmax}_{t\in\left\{t|a_{t}<\hat{c}\right\}}\left\{g_{t}\left(\mathbf{ \alpha}^{k}\right)\right\}\\ &j\in\text{argmin}_{t\in\left\{t|a_{t}>-\hat{c}\right\}}\left\{\frac{-h_{it} ^{2}}{a_{it}}|G_{t}\left(\mathbf{\alpha}^{k}\right)<g_{i}\left(\mathbf{\alpha}^{k} \right)\right\}\\ &\text{where }h_{it}=g_{i}(\mathbf{\alpha}^{k})-G_{t}(\mathbf{\alpha}^{k})\\ \text{(2)}&\text{Return }\{i,j\}\end{array}  \tag{36}\]  
Since \(d_{j}^{*}<0\) as shown in Proposition 2, the left-hand-side derivatives are employed to obtain an upper bound on the quadratic approximation using a Taylor series expansion of the difference between consecutive loss function values around \(d_{j}^{*}=0\). \[J(\mathbf{\alpha}^{k+1})-J(\mathbf{\alpha}^{k})=\hat{J}(d_{j}^{*})-\hat{J}(0)<\hat{J} (d_{j})-\hat{J}(0)\approx\hat{J}_{-}^{\prime}(0)d_{j}+\frac{\hat{J}_{-}^{ \prime\prime}(0)}{2}d_{j}^{2} \tag{38}\]  
Instead of directly finding the pair \(\{i,j\}\) minimizing the difference of the consecutive loss functions \(J(\mathbf{\alpha}^{k+1})-J(\mathbf{\alpha}^{k})\), it is more computationally efficient to find the pair \(\{i,j\}\) minimizing the second-order [PERSON] polynomial approximation. The following proposition suggests an upper bound associated with minimizing this approximation, which is easy to compute. **Proposition 4**. : _if \(\{i,j\}\) is a violating pair, there is an upper bound on the second-order [PERSON] polynomial approximation of consecutive loss function values (38) such that_  
\[\min_{d_{j}}\hat{J}_{-}^{\prime}(0)d_{j}+\frac{\hat{J}_{-}^{\prime\prime}(0)}{ 2}d_{j}^{2}<-\frac{h_{ij}^{2}}{a_{ij}} \tag{39}\]  
_and the optimal value of the minimization problem in (39) satisfies \(d_{j}^{*}<0\)._  
Proof. : Since the Taylor polynomial approximation is quadratic, its minimum value is at \(d_{j}^{*}=-\frac{\hat{J}_{-}^{\prime}(0)}{\hat{J}_{-}^{\prime\prime}(0)}\). Substituting it in (39) results in  
\[\hat{J}_{-}^{\prime}(0)d_{j}^{*}+\frac{\hat{J}_{-}^{\prime\prime}(0)}{2}(d_{j }^{*})^{2}\leq-\frac{1}{2}\frac{[\hat{J}_{-}^{\prime}(0)]^{2}}{\hat{J}_{-}^{ \prime\prime}(0)} \tag{40}\]  
where \(\hat{J}_{-}^{\prime}(0)=\
abla\hat{J}(0)+\varepsilon sign^{-}\left(\alpha_{j }^{k}\right)-\varepsilon sign^{+}\left(\alpha_{i}^{k}\right)=\
abla f(\mathbf{ \alpha})_{j}-\
abla f(\mathbf{\alpha})_{i}+\varepsilon sign^{-}\left(\alpha_{j}^{ k}\right)-\varepsilon sign^{+}\left(\alpha_{i}^{k}\right)=g(i)-G(j)=h_{ij}>0\) and \(\hat{J}_{-}^{\prime\prime}(0)=\
abla^{2}\hat{J}(0)=a_{ij}+\frac{\hat{c}}{\eta_ {2}[\hat{C}^{2}-(\alpha_{i}^{k})^{2}]}+\frac{\hat{c}}{\eta_{2}[\hat{C}^{2}-( \alpha_{i}^{k})^{2}]}\geq a_{ij}+\frac{2}{\eta_{2}\hat{C}}>a_{ij}>0\). Therefore, it is obtained that  
\[-\frac{1}{2}\frac{[\hat{J}_{-}^{\prime}(0)]^{2}}{\hat{J}_{-}^{\prime\prime}(0) }<-\frac{h_{ij}^{2}}{a_{ij}} \tag{41}\]  
since \(\hat{J}_{-}^{\prime}(0)=h_{ij}\) and \(\hat{J}_{-}^{\prime\prime}(0)>a_{ij}\). It is obvious that \(d_{j}^{*}<0\) and (40) with (41) conclude the proof.