# SVM-Based Multiple Instance Classification via DC Optimization
## 3 Solving DC-MIL using a Nonsmooth DC Algorithm  
We start by recalling some preliminary property of the DC optimization problem, by adopting the same notation as above. Given the DC optimization problem  
\[\min_{y}[f_{1}(y)-f_{2}(y)] \tag{4}\]  
where both \(f_{1}\) and \(f_{2}\) are convex nonsmooth functions, we say that a point \(y^{*}\) is a local minimizer if \(f_{1}(y^{*})-f_{2}(y^{*})\) is finite and there exists a neighborhood \(\mathcal{N}\) of \(y^{*}\) such that  
\[f_{1}(y^{*})-f_{2}(y^{*})\leq f_{1}(y)-f_{2}(y),\ \ \forall y\in\mathcal{N}. \tag{5}\]  
Considering that, in general, the Clarke subdifferential calculus cannot be used to compute subgradients of the DC function since  
\[\partial_{cl}f(y)\subseteq\partial f_{1}(y)-\partial f_{2}(y), \tag{6}\]  
where \(\partial_{cl}f(\cdot)\) denotes Clarke's subdifferential, different stationary points can be defined for nonsmooth DC functions. A point \(y^{*}\) is called inf-stationary for problem Equation (4) if  
\[\emptyset\
eq\partial f_{2}(y^{*})\subseteq\partial f_{1}(y^{*}). \tag{7}\]  
Furthermore, a point \(y^{*}\) is called Clarke stationary for problem Equation (4) if  
\[0\in\partial_{cl}f(y^{*}), \tag{8}\]  
while, it is called a critical point of \(f\) if  
\[\partial f_{2}(y^{*})\cap\partial f_{1}(y^{*})\
eq\emptyset. \tag{9}\]  
Denoting the set of inf-stationary points by \(S_{inf}\), the set of Clarke stationary points by \(S_{cl}\), and the set of critical points of the function \(f\) by \(S_{cr}\), the following inclusions hold  
\[S_{inf}\subseteq S_{cl}\subseteq S_{cr}\]  
as shown in (Proposition 3, [30]). Nonsmooth DC functions have attracted the interest of several researchers, both, from the theoretical and from the algorithmic viewpoint. Focusing in particular on the algorithmic side, the most relevant contribution has probably been provided by the methods based on the linearization of function \(f_{2}\) (see, [41] and references therein), where the problem is tackled via successive convexifications of function \(f\). In the last years, nonsmooth-tailored DC programming has experienced a lot of attention as it has a lot of practical applications (see [28; 42]). In fact, several nonsmooth DC algorithms have been developed ([30; 43; 44; 45; 46; 47]). Here, we adopt the algorithm DCPCA, a bundle-type method introduced in [30] to solve problem Equation (4), which is based on a model function built by combining two convex piecewise approximations, each related to one component function. More in details, a simplified version of DCPCA works as follows:  
* It iteratively builds two separate piecewise-affine approximations of the component functions, grouping the corresponding information in two separate bundles. * It combines the two convex piecewise-affine approximations and generates a DC piecewise-affine model. * The DC (hence, nonconvex) model is locally approximated using an auxiliary quadratic program, whose solution is used to certify approximate criticality, or to generate a descent search-direction to be explored via a backtracking line-search approach. * Whenever no descent is achieved along the search direction, the bundle of the first function is enriched, thus, obtaining a better model function with this being the fundamental feature of any cutting plane algorithm. In fact, the DCPCA is based on constructing a model function as the pointwise maximum of several concave piecewise-affine pieces. To construct this model, starting from some cutting-plane ideas, the information coming from the two component functions are kept separate in two bundles. We denote the stability center by \(z\) (i.e., an estimate of the minimizer), and by \(I\) and \(L\), the index sets of the points generated by the algorithm where the information of function \(f_{1}\) and \(f_{2}\) have been evaluated, respectively.