# SVM-Based Multiple Instance Classification via DC Optimization
## 3 Solving DC-MIL using a Nonsmooth DC Algorithm
Therefore, we denote the two bundles of information as  
\[\mathcal{B}_{1}=\{(g_{i}^{(1)},\alpha_{i}^{(1)}):i\in I\}\]  
and  
\[\mathcal{B}_{2}=\{(g_{l}^{(2)},\alpha_{l}^{(2)}):l\in L\}\]  
where, for every \(i\in I\), \(g_{i}^{(1)}\in\partial f_{1}(y_{i})\) with  
\[\alpha_{i}^{(1)}=f_{1}(z)-\left(f_{1}(y_{i})+g_{i}^{(1)\mathsf{T}}(z-y_{i}) \right),\]  
and, for every \(l\in L\), \(g_{l}^{(2)}\in\partial f_{2}(y_{l})\) with  
\[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]0  
We remark that both component functions, along with their subgradients, could be evaluated at some iterate-point, and, indeed, we assume that \((g^{(1)}(z),0)\in\mathcal{B}_{1}\) and \((g^{(2)}(z),0)\in\mathcal{B}_{2}\), where \(g^{(1)}(z)\in\partial f_{1}(z)\) and \(g^{(2)}(z)\in\partial f_{2}(z)\). To approximate the difference function  
\[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]1at a given iteration \(k\) the following nonconvex model function \(\Gamma_{k}(d)\) is introduced  
\[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]2  
which is defined as the maximum of finitely many concave piecewise-affine functions. The model-function \(\Gamma_{k}\) is used to state a sufficient descent condition of the type  
\[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]3  
where \(m\in(0,1)\). The interesting property of such a model-function is that whenever the sufficient descent is not achieved at points that are close to the stability center, say \(z+\bar{d}\), then an improved cutting-plane model can be obtained by only updating the bundle of \(f_{1}\) with the appropriate information related to the point \(z+\bar{d}\). On the other hand, it looks obviously difficult to adopt the minimization of the model-function \(\Gamma_{k}\) as a building block of any algorithm, given its nonconvexity. In fact, DCPCA does not require the direct minimization of \(\Gamma_{k}(d)\), but the search direction can be obtained by solving the following auxiliary quadratic problem:  
\[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]4 \[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]5  
where \(\bar{I}\in L(0)\triangleq\{l\in L:\alpha_{l}^{(2)}=0\}\). We observe that \(L(0)\
eq\emptyset\) as \(\mathcal{B}_{2}\) is assumed to contain the information about the current stability center. More precisely, DCPCA works by forcing \(L(0)\) to be a singleton, hence by letting \(g_{l}^{(2)}=g^{(2)}(z)\). Denoting the unique optimal solution of Equation (\(QP(I)\)) by \((\bar{d},\bar{v})\), a standard duality argument ensures that  
\[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]6 \[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]7  
where \(\bar{\lambda}_{i}\geq 0\), \(i\in I\), are the optimal variables of the dual of \(QP(I)\), with \(\sum_{i\in I}\bar{\lambda}_{i}=1\). Given that any starting point \(z=y_{0}\), DCPCA returns an approximate critical point \(z^{*}\), see (Theorem 1, [30]). The following parameters are adopted: the optimality parameter \(\theta>0\), the subgradient threshold \(\eta>0\), the linearization-error threshold \(\varepsilon>0\), the approximate line-search parameter \(m\in(0,1)\), and the step-size reduction parameter \(\sigma\in(0,1)\). In Algorithm 1, we report an algorithmic scheme of the main iteration, namely of the set of steps where the stability center is unchanged. An exit from the main iteration is obtained as soon as a stopping criterion is satisfied or whenever the stability center is updated. To make the presentation clearer, without impairing convergence properties, we skip the description of some rather technical steps, which are strictly related to the management of bundle \(\mathcal{B}_{2}\). Details can be found in [30].