--- title: "Optimal Margin Distribution Machine for Multi-Instance Learning" authors: - "Teng Zhang" - "Hai Jin" doi: "10.24963/ijcai.2020/330" url: "https://ijcai.org/proceedings/2020/330" pdf: "https://ijcai.org/proceedings/2020/0330.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "2383-2389" track: "Main track" keywords: - "Machine Learning: Multi-instance;Multi-label;Multi-view learning" - "Machine Learning: Classification" --- # Optimal Margin Distribution Machine for Multi-Instance Learning Teng Zhang, Hai Jin *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 2383-2389. DOI: [10.24963/ijcai.2020/330](https://doi.org/10.24963/ijcai.2020/330) ## Abstract Multi-instance learning (MIL) is a celebrated learning framework where each example is represented as a bag of instances. An example is negative if it has no positive instances, and vice versa if at least one positive instance is contained. During the past decades, various MIL algorithms have been proposed, among which the large margin based methods is a very popular class. Recently, the studies on margin theory disclose that the margin distribution is of more importance to generalization ability than the minimal margin. Inspired by this observation, we propose the multi-instance optimal margin distribution machine, which can identify the key instances via explicitly optimizing the margin distribution. We also extend a stochastic accelerated mirror prox method to solve the formulated minimax problem. Extensive experiments show the superiority of the proposed method. ## Full text ## 1 Introduction Multi-instance learning (MIL) is a celebrated learning framework [Foulds and Frank, 2010; Amores, 2013; Herrera et al., 2016] where each example is represented as a collection (bag) of feature vectors (instances). A bag is negative if it has no positive instances, and vice versa if at least one positive instance is contained. The learner can only access the bag labels, while the instance labels are not available. Compared to the classical supervised learning where each bag just consists of one instance, MIL provides a much more natural representation and is well suited for many complicated problems. For example in drug discovery and development [Dietterich et al., 1997], one molecule (bag) could have many low-energy shapes (instances), and the model should predict whether a new molecule is qualified to make a special drug or not by learning from a set of known molecules. In content-based image retrieval (CBIR) [Zhou et al., 2005], the image (bag) is decompose into several regions (instances), and the system should retrieve all the images that are relevant to the concept queried by users. Besides the prediction of bag labels, detecting the key instance which triggers the positive bag label is a more difficult task. For the former, it is to determine which low-energy shapes are responsible for the observed biological activity. For the latter, it is to identify which regions in the image make users have interest in it. In the past decades, various MIL algorithms have been proposed, e.g., the diverse density (DD) algorithm [Maron and Ratan, 1998] and EM-DD [Zhang and Goldman, 2001], citation-kNN and its variant [Zhou et al., 2005], MISVM [Andrews et al., 2003] and its variants [Bi et al., 2005; Li et al., 2009], among which, the large margin based methods have always been popular. More specifically, MI-SVM starts with a SVM using some multi-instance kernel [G¨artner et al., 2002] and identifies the key instances according to the decision values, after that retrains the SVM model based on the new key instance assignments (bag labels). The convergence of this procedure can be easily guaranteed once it is viewed as a specialization of the constrained concave-convex programming (CCCP) method. Although in each iteration, MI-SVM only solves a SVM-like convex optimization, the whole problem is still non-convex and thus it may get stuck in the local minima. On the other hand, the KI-SVM overcomes this difficulty by relaxing the mixed-integer programming as a convex optimization by minimax saddle point theory. It applies the cutting-plane method for optimization by generating a violated key instance assignment (kernel) to the constraint set in each iteration. Aforementioned methods are based on the large margin principle, i.e., maximizing the minimal distance from the instances to the decision hyperplane. Recently, the studies on margin theory [Gao and Zhou, 2013] show that margin distribution is of more importance to generalization ability than minimal margin, which gives rise to the optimal margin distribution learning ([Zhang and Zhou, 2019]). Due to the superiority to the traditional large margin based methods, this new learning paradigm has quickly attracted a lot of attentions and been extended to many learning settings ([Zhang and Zhou, 2018a; Zhang and Zhou, 2018b; Tan et al., 2020]). These great successes suggest that the existing large margin based MIL algorithms still have enough room for enhancement. Based on this recognition, we propose the multi-instance optimal margin distribution machine (MI-ODM). It can identify the key instance via explicitly optimizing the margin distribution. Specifically, we characterize the margin distribution by its first- and second-order statistics, i.e., the margin mean and margin variance. As suggested in [Gao and Zhou, 2013], we maximize the former and minimize the latter simultaneously. To solve the resultant minimax saddle point problem, we extend a stochastic accelerated mirror prox method which enjoys the optimal convergence rate. Extensive experiments verify the superiority of the proposed method. The rest of the paper is organized as follows. We first introduce some preliminaries, and then present the proposed MI-ODM. After that we detail the optimization techniques, followed by the experimental results and empirical observations. Finally we conclude the paper with future work. ## 2 Preliminaries For convenience, we first make some notation conventions. Throughout the paper, we denote scalars with lower case letters (e.g., y), and vectors with bold face letters (e.g., x). Sets are designated by upper case letters with mathcal font (e.g., S). Let X ⊆ Rn and Y = {1,-1} denote the input and output spaces, respectively. For any m ≥ 1, the set of integers {1, . . . ,m} is denoted by [m]. The feature mapping associated to some positive definite kernel κ is denoted by φ : X ↦→H. ## 2.1 ODM The margin γ(x, y) of a labeled instance (x, y) is defined as the signed decision value, i.e., γ(x, y) = yw⊤φ(x). 1 This value can be viewed as the confidence (or safety) of the prediction. The larger the margin, the more confidence we have on the predicted label, and (x, y) is misclassified if and only if it produces a negative margin. It is well known that SVMs employ the large margin principle to pick the decision boundary [Cristianini and ShaweTaylor, 2000]. As a result, the obtained separating hyperplane just consists of a small amount of instances, a.k.a. the support vectors (SVs), and the rest instances are totally ignored. When noisy instances exist, the learner may be misled and produce a suboptimal decision boundary [Zhou, 2014]. As a counterpart, optimizing the margin distribution is a more robust strategy by exploiting the whole data set and preventing from being cheated by the noisy instances. As for how to characterize the margin distribution, a straightforward way is through the first- and second- statistics, i.e., the margin mean and variance. Moreover, as suggested in [Gao and Zhou, 2013], maximizing the former and minimizing the latter simultaneously can yield a tighter generalization bound, the optimal margin distribution machine (ODM) is initially formulated as: where η and λ are the parameters for trading-off the regularization, and ¯ γ is the margin mean. Note that ξi and ϵi are deviations of γ(xi, yi) from the margin mean, thus the last term ∑i∈[m] (ξ 2 i + ϵ2i )/m is exactly the margin variance. 1 Often an offset term b is included, but as this can be implemented by augmenting each x with an additional element whose value is always one, we do not explicitly include it here. To make the model more clean and powerful, ODM further introduces three modifications to Eqn. (1). First is simplifying the formulation by fixing the margin mean as one. 2 Second is assigning different weights to different deviations respectively. Third is tolerating the deviation smaller than the given threshold θ to achieve a sparse solution. Therefore, the final formulation of ODM is: where ν is the weight for trading-off different deviations, and (1 - θ)2 is to scale the second term as a surrogate loss. ## 3 The ProposedMethod Given a training set of m bags S = {Bi, yi}i∈[m] where Bi = {xi,1, . . . , xi,mi } is the i-th bag, yi ∈ {±1} is the label and mi is the number of instances in bag Bi, we assume the first p bags are positive and the rest q = m- p bags are negative without loss of generality, i.e., all bags are ordered such that The prediction of a bag is determined by the largest decision value of its instances, i.e., f(Bi) = maxj∈[mi] w⊤φ(xi,j). Substituting into Eqn. (2), we get where λ1, λ2 are the parameters for trading-off empirical losses on positive and negative bags, respectively. For each positive bag Bi, we introduce a binary vector to indicate the key instance with the largest decision value. Following the traditional MIL setting, we assume that each positive bag has only one key instance, 3 and hence we have e⊤ai = 1, where e is an all-one column vector. In the following, let c = [a1; . . . ; ap] and C be its domain, then the constraints yi maxj∈[mi] w⊤φ(xi,j) ≥ 1-θ-ξi corresponding to positive bags in Eqn. (3) can be equivalently rewritten as maxai ∑j∈[mi] ai,jw⊤φ(xi,j ) ≥ 1 - θ - ξi. 2 Note that scaling w does not affect the prediction. 3 Sometimes one may want the positive bag has more than one key instances. The proposed method can be simply extended to this case by setting e⊤ai = k. For each negative bag Bi whose instances are all negative, the corresponding constraints Eqn. (3) can be replaced by Moreover, to make the model more relaxable, we allow the bags have different slack variables, i.e., where index s(i, j) = Ji-1 -Jp +j +p ranges from p+1 to Jm - Jp + p and Ji = ∑it=1 mt (J0 is set to 0). Combining all these together, Eqn. (3) turns into As kernel methods, the inner minimization of Eqn. (4) is usually processed via the dual form due to the underlying infinite dimensional feature mapping. Introduce the dual variables u = [u1; . . . ; u2(Jm-Jp+p)] ⪰ 0, the Lagrangian of Eqn. (4) leads to where U is the non-negative quadrant and Ki,j = Ψ⊤i Ψj ∈ Rq×q is the kernel matrix with To overcome the difficulty caused by the mixed-integer programming, some convex relaxation methods should be applied, e.g., the semi-definite programming relaxation [Xu et al., 2004], and the minimax relaxation [Li et al., 2009]. Since the latter is proven to be tighter than the former, we also employ minimax relaxation in this paper. Interchanging the order of maxu∈U and minc∈C, we have where D(u, c) denotes the objective function of Eqn. (5). Moreover, with an equivalent rewriting for the inner optimization, the above formulation turns to Again introduce the dual variables v = [v1; . . . ; v|C|] ⪰ 0 for the inner optimization, the Lagrangian of Eqn. (6) leads to Setting the derivative of d to zero, we have ∑k:ck∈C vk = 1 and the dual problem turns to where V = {v ∈ R|C| + | e⊤v = 1} is the simplex in R|C| . For simplicity, denote ∑k:ck∈C vkD(u, ck) as G(u, v), and substitute Eqn. (7) into Eqn. (6), we have Note that G(u, v) is a convex combination of negative definite quadratic functions, thus it is convex in v and concave in u, and according to Siont's minimax theorem [Sion, 1958], there exists a saddle point (u⋆ , v⋆ ) ∈ U × V such that Combining with the minimax inequality all the inequalities in Eqn. (8) hold as equations, thus the MIODM finally can be formulated as and the optimal solution is the saddle point (u⋆ , v⋆ ). ## 4 Optimization In this section, we first give a simple introduction to the minimax problem. After that, we detail the stochastic accelerated mirror prox method which can quickly find the optimal solution. ## 4.1 Minimax Problem Note that G(u, ·) and -G(·, v) are both convex functions, according to the first order inequality of convexity, for any pair (ˆu, ˆ v) ∈ U × V, we have Adding the above two inequalities together and augmenting u and v, we have where w = [u; v] and g( ˆw) = [-∂uG( ˆw); ∂vG( ˆw)]. Compared to the general convex optimization, it can be found that g( ˆw) plays a similar role as "gradient". Since Eqn. (10) holds for any u and v, particularly we have The LHS of Eqn. (11) can be further decomposed as two gaps between current point (ˆu, ˆ v) and saddle point (u⋆ , v⋆ ): Since the two gaps are both non-negative, and the smaller the two gaps, the closer to the saddle point, the LHS of Eqn. (11) can be viewed as the "duality gap" in the general convex optimization and serves as a stopping criteria for the algorithm design. ## 4.2 Stochastic AcceleratedMirror Prox The feasible field of u and v are box and simplex respectively. To exploit this structural information, we resort to the mirror descent method [Beck and Teboulle, 2003]. Specifically, for variable u, the common Euclidean distance mirror map ψU(u) = ‖u‖22 /2 can work well, while for variable v, the negative entropy mirror map ψV(v) = ∑k vk log vk is most suitable, since it can make the time complexity only have a logarithmic dependence on the dimension. The mirror descent style methods perform gradient descent in the dual space induced by the mirror maps. To make the minimax structure more easily handled like the general optimization problem, we introduce the joint mirror map ψ(w) = aψU (u)+bψV (v) , where a = √2/τ √Jm - Jp + p and b = 1/√log |C|, respectively. It can be shown that ∇ψU(u) = u and ∇ψV(v) = logv + e. Combining the two components together we have ∇ψ(w) = [au; b log v + be]. As shown in Figure 1, at the t-th iteration, we first map the current point wt = [ut; vt] into the dual space ∇ψ(wt) = [aut; b log vt + be] and perform one step of gradient descent where η is the step size, then map the ∇ψ( ˆwt) back to primal space, i.e., to find ˆwt = [ˆut; ˆ vt] such that which implies that ˆut = ut + η∂uG(ut, vt)/a and ˆ vt = vt exp(-η∂vG(ut, vt)/b). Finally, we project [ˆut; ˆ vt] back to U × V based on the Bregman distance induced by the mirror maps. To be specific, the Euclidean distance mirror map induces the common Euclidean distance, while the negative entropy mirror map induces the Kullback-Leibler divergence. This can be formulated as the following two optimization sub-problems: Figure 1: One iteration of mirror descent. ![Image](https://ijcai.org/proceedings/2020/fulltext/330/image_000000_94ea00b876d1c56519d3a59e62adfd4d4dcb04e75ee6462e41ace89d6746e936.png) Fortunately, both two problems have a closed-form solution. The former is to project ˆut onto the non-negative quadrant, thus ut+1 = max{ˆut, 0}. For the latter, we introduce the dual variable z, and the Lagrangian leads to Setting the derivative of v to zero, we have log(v/ˆ vt) + e + ze = 0, which implies that vt+1 = ˆ vt exp(-1 - z). Note that vt+1 belongs to a simplex, hence Substituting with exp(-1-z) = 1/‖ˆ vt‖1, we get the closedform solution vt+1 = ˆ vt/‖ˆ vt‖1. Once we have yt+1 ≜ [ut+1; vt+1], repeat the above procedure fromwt one more time, except that when performing gradient descent in the dual space, we use the gradient at yt+1 rather than wt. In other words, a two-step mirror descent is carried out in each iteration, which starts from the same point but the gradient used in the second time is evaluated at the ending point of the first time. This is exactly the mirror prox method [Nemirovski, 2005], which has been proved enjoying better convergence rate. Figure 2 illustrates one iteration of this method. The mirror prox method can be further accelerated via the Nesterov accelerated technique [Nesterov, 2003]. The intuition is that besides {wt} and {yt}, we also maintain another two sequences {wt } and {wt}, which are the convex combination of {wt} and {yt}. Specifically, at the t-th iteration, first update wt = (1-γt)wt+γtyt, where γt is the Nesterov accelerated coefficient, usually set as 2/(t + 1). After that, perform two-step mirror descent based on wt to get yt+1 and wt+1. Finally, update update wt+1 = (1 - γt)wt + γtwt+1. Moreover, to make the method scale well for big data, we also extend a stochastic version of our method, and the key problem turns to finding the unbiased noisy gradient ∂u ˜G(ut, vt) and ∂v ˜G(ut, vt). Note that G(u, v) = ∑k:ck∈C vkD(u, ck), we have Figure 2: One iteration of mirror prox. The two-step mirror descent both starts from the same point but with gradients evaluated at different points. ![Image](https://ijcai.org/proceedings/2020/fulltext/330/image_000001_0b67ffaa5ca1b7eae58664b8375cd1812798839c64de06bd2354e308d72cdeaf.png) Randomly sampling an index it according to the distribution vt on {1, 2, . . . , |C|}, we can obtain ∂u ˜G(ut, vt, it) = ∂uD(ut, cit ). On the other hand, uniformly sampling an index jt from {1, 2, . . . , |C|}, we can obtain ∂v ˜G(ut, vt, jt) = [0, . . . , |C|D(ut, cjt ) . . . , 0]. Thus it can be shown that and ˜ g(wt) = [-∂u ˜G(ut, vt, it); ∂v ˜G(ut, vt, jt)] is the targeted unbiased estimation of g(wt). Putting the above all together, we come up with the stochastic accelerated mirror prox method for MI-ODM. Algorithm 1 summarizes the pseudo-code. ## 4.3 Discussion Resorting to the monotone stochastic variational inequality technique [Juditsky et al., 2011; Chen et al., 2017], we can prove the time complexity is O(1/√ϵ + 1/ϵ + 1/ϵ2 ), where the dominated term 1/ϵ2 comes from the noise introduced by the stochastic optimization. On the other hand, the stateof-the-art cutting-plane based algorithms have the same time complexity O(1/ϵ2 ) [Zhao et al., 2008]. Further note that in each iteration, cutting-plane based algorithms need to find the most violated key instance assignment and retrain a SVM model, while our method just preforms some random samplings and two steps of gradient descent followed by a projection with closed-form solutions, therefore our method is much more efficient. ## 5 Empirical Studies We empirically study our method on CBIR image data sets in Sec. 5.1 and benchmark data sets in Sec. 5.2, respectively. ## 5.1 Experiments on Image Data The data set contains 500 images (bags) with resolution 160 × 160 from five categories: castle, firework, mountain, ## Algorithm 1 MI-ODM - 1: Input: ODMparameters λ1, λ2, ν, θ, maximum iteration number T , stopping criteria ζ. - 2: Initialize u0 ← 0, v0 ← [1/|C|, . . . , 1/|C|], t ← 0, [u0; v0] ← [u0; v0], [ˆu0; ˆ v0] ← [u0; v0]. - 3: while t < T do - 4: γt ← 2/(t +1). - 5: [ut ; vt ] ← (1 - γt)[ut; vt] + γt[ut; vt]. - 6: Select it from {1, 2, . . . , |C|} according to vt . - 7: ∂u ˜G← ∂uD(ut , cit ). - 8: Uniformly select jt from {1, 2, . . . , |C|}. - 9: ∂v ˜G← [0, . . . , |C|D(ut , cjt ) . . . , 0]. - 10: [ˆut; ˆ vt] ← [ut + η∂u ˜G/a; vt exp(-η∂v ˜G/b)]. - 11: [˜ut+1; ˜ vt+1] ← [max{ˆut, 0}; ˆ vt/‖ˆ vt‖1]. - 12: Select i′t from {1, 2, . . . , |C|} according to ˜ vt+1. - 13: ∂u ˜G← ∂uD(˜ut+1, ci′t ). - 14: Uniformly select j ′t from {1, 2, . . . , |C|}. - 15: ∂v ˜G← [0, . . . , |C|D(˜ut+1, cj ′t ) . . . , 0]. - 16: [ˆut+1; ˆ vt+1] ← [ut + η∂u ˜G/a; vt exp(-η∂v ˜G/b)]. - 17: [ut+1; vt+1] ← [max{ˆut+1, 0}; ˆ vt+1/‖ˆ vt+1‖1]. - 18: [ut+1; vt+1] ← (1 - γt)[ut; vt] + γt[ut+1; vt+1]. - 19: t ← t + 1. - 20: if duality gap smaller than the stopping criteria ζ then - 21: Break. - 22: end if - 23: end while - 24: Output: u, v. sunset and waterfall. Each instance is a region in the image with resolution 20 × 20. Some of the regions are manually labeled as key instances. Table 1 summarizes the statistics of these data sets. We randomly sample 50 images from each category as training data and the rest are used as test data. The training/test split are repeated for 10 times. The average accuracies as well as the standard deviations are recorded. The proposed method is compared to the following five large margin based methods: 1) Ins-KI-SVM [Li et al., 2009]; 2) Bag-KI-SVM [Li et al., 2009]; 3) MI-SVM [Andrews et al., 2003]; 4) mi-SVM [Andrews et al., 2003]; 5) MIKernel [G¨artner et al., 2002]. The parameters C1, C2, λ1, λ2 are selected from {1, 10, 100, 1000}, and ν, θ are selected from {0.2, 0.4, 0.6, 0.8}. The RBF kernel is applied for all the methods and the width is selected from the set of {2-4 δ, 2-2 δ, 20 δ, 22 δ, 24 δ}, where δ is the reciprocal of dimension. Three classical non-large margin based methods, i.e., DD [Maron and Ratan, 1998], EM-DD [Zhang and Goldman, 2001] and CkNN-ROI [Zhou et al., 2005], which can locate key instances, are also included as baselines. All the parameters are selected by 5-fold cross validation. Table 1: Characteristics of experimental data sets. | categories | #images | #key-instance per image | |--------------|-----------|---------------------------| | castle | 100 | 19.39 | | firework | 100 | 27.23 | | mountain | 100 | 24.93 | | sunset | 100 | 2.32 | | waterfall | 100 | 13.89 | Table 2: Success rate (%) on identifying the key instances. The best performance on each data set is bolded. | | methods | castle | firework | mountain | sunset | waterfall | |------------------|------------|-------------|-------------|-------------|-------------|-------------| | margin based | Ins-KI-SVM | 64.74±6.64 | 83.70±15.43 | 76.78±5.46 | 66.85±6.03 | 63.41±10.56 | | margin based | Bag-KI-SVM | 60.63±7.53 | 54.00±22.13 | 72.70±7.66 | 47.78±13.25 | 45.04±21.53 | | margin based | MI-SVM | 56.63±5.06 | 58.04±20.31 | 67.63±8.43 | 33.30±2.67 | 33.30±8.98 | | margin based | mi-SVM | 51.44±4.93 | 40.74±4.24 | 67.37±4.48 | 32.19±1.66 | 22.04±4.97 | | margin based | MI-Kernel | 50.52±4.46 | 36.37±7.92 | 65.67±5.18 | 32.15±1.67 | 19.93±4.65 | | margin based | MI-ODM | 76.80±4.99 | 84.12±7.42 | 77.05±7.94 | 67.15±2.48 | 65.91±7.15 | | non-margin based | DD | 35.89±15.23 | 38.67±30.67 | 68.11±7.54 | 57.00±18.40 | 37.78±29.61 | | non-margin based | EM-DD | 76.00±4.63 | 79.89±19.25 | 77.22±13.29 | 53.56±16.81 | 44.33±15.13 | | non-margin based | CkNN-ROI | 51.48±4.59 | 43.63±12.40 | 60.59±4.38 | 34.59±2.57 | 30.48±6.34 | Table 3: Accuracy (%) on the benchmark data sets. The best performance on each data set is bolded. DD could not return results on some data sets in 48 hours. | | methods | Musk1 | Musk2 | Elephant | Fox | Tiger | |------------------|------------|---------|---------|------------|-------|---------| | margin based | Ins-KI-SVM | 84.0 | 84.4 | 83.5 | 63.4 | 82.9 | | | Bag-KI-SVM | 88.0 | 82.0 | 84.5 | 60.5 | 85.0 | | | MI-SVM | 77.9 | 84.3 | 81.4 | 59.4 | 84.0 | | | mi-SVM | 87.4 | 83.6 | 82.0 | 58.2 | 78.9 | | | MI-Kernel | 88.0 | 89.3 11 | 84.3 | 60.3 | 84.2 | | | MI-ODM | 88.2 | 89.8 | 84.5 | 63.9 | 85.2 | | non-margin based | DD | 88.0 | 84.0 | N/A | N/A | N/A | | | EM-DD | 84.8 | 84.9 | 78.3 | 56.1 | 72.1 | Following the setting in [Li et al., 2009], we evaluate the success rate, i.e., the ratio of the number of successes divided by the total number of relevant images. Table 2 shows the results of al the compared methods. As can be seen, MIODM beats all the large margin based methods. As for the non-margin based methods, MI-ODM is also better than DD, CkNN-ROI, and highly comparable to EM-DD. Specifically, MI-ODM achieves the best performance on four categories, while EM-DD achieves the best performance on the remaining one (mountain). ## 5.2 Experiments on Benchmark Data We have also evaluated our method on five benchmark data sets commonly used in the literature of MIL, i.e., Musk1, Musk2, Elephant, Fox and Tiger. Musk1 has 47 positive bags and 45 negative bags. Musk2 consists of 39 positive bags and 63 negative bags. The remaining three data sets all contains 100 positive bags and 100 negative bags. The detail of these data sets can be found in [Dietterich et al., 1997; Andrews et al., 2003]. The setting is the same with the previous experiment. We adopt the 5-fold cross validation to measure the performance. DD could not return results on some data sets in 48 hours because it lacks high efficient packages. As shown in Table 3, our method is always better or comparable, almost never worse than other baselines. ## 6 Conclusions Recent studies on margin theory discloses the importance of margin distribution to generalization ability, which gives rise to a promising research direction, i.e., the optimal margin distribution learning. Based on this observation, we propose the MI-ODM, which can identify the key instance via explicitly optimizing the margin distribution. Extensive experimental results verify the superiority of the new learning paradigm. In the future, we will apply the variance reduction technique [Johnson and Zhang, 2013] to further accelerate our method and extend it to other learning settings, e.g., multi-instance multi-label learning [Zhou et al., 2012]. ## References 1. [Amores, 2013] Jaume Amores. Multiple instance classifica- tion: Review, taxonomy and comparative study. Artificial Intelligence, 201(4):81-105, 2013. 2. [Andrews et al., 2003] Stuart Andrews, Ioannis Tsochan- taridis, and Thomas Hofmann. Support vector machines for multiple-instance learning. In Advances in Neural Information Processing Systems, pages 561-568, Cam- bridge, MA, 2003. 3. [Beck and Teboulle, 2003] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient meth- ods for convex optimization. Operations Research Letters, 31(3):167-175, 2003. 4. [Bi et al., 2005] Jinbo Bi, Yixin Chen, and James Z. Wang. A sparse support vector machine approach to region-based image categorization. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1121-1128, San Diego, CA, 2005. 5. [Chen et al., 2017] Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. Accelerated schemes for a class of variational inequalities. Mathematical Programming, 165(1):113-149, 2017. 6. [Cristianini and Shawe-Taylor, 2000] Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vec- tor Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge, UK, 2000. 7. [Dietterich et al., 1997] Thomas G. Dietterich, Richard H. Lathrop, and Tomás Lozano-Pérez. Solving the multiple instance problem with axis-parallel rectangles. Artificial Intelligence, 89(1-2):31-71, 1997. 8. [Foulds and Frank, 2010] James Richard Foulds and Eibe Frank. A review of multi-instance learning assumptions. Knowledge Engineering Review, 25(1):1-25, 2010. 9. [Gao and Zhou, 2013] Wei Gao and Zhi-Hua Zhou. On the doubt about margin explanation of boosting. Artificial In- telligence, 203:1-18, 2013. 10. [Gärtner et al., 2002] Thomas Gärtner, Peter A. Flach, Adam Kowalczyk, and Alexander J. Smola. Multi-instance ker- nels. In Proceedings of the 19th International Conference on Machine Learning, pages 179-186, Sydney, Australia, 2002. 11. [Herrera et al., 2016] Francisco Herrera, Sebastián Ventura, Rafael Bello, Chris Cornelis, Amelia Zafra, Dánel Sánchez-Tarragó, and Sarah Vluymans. Multiple Instance Learning: Foundations and Algorithms. Springer, Cham, Switzerland, 2016. 12. [Johnson and Zhang, 2013] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315-323, Lake Tahoe, NV, 2013. 13. [Juditsky et al., 2011] Anatoli Juditsky, Arkadii Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011. 14. [Li et al., 2009] Yu-Feng Li, James T. Kwok, Ivor W. Tsang, and Zhi-Hua Zhou. A convex method for locating regions of interest with multi-instance learning. In Proceedings of the 20th European Conference on Machine Learning, pages 15-30, Bled, Slovenia, 2009. 15. [Maron and Ratan, 1998] Oded Maron and Aparna Lakshmi Ratan. Multiple-instance learning for natural scene classi- fication. In Proceedings of the 15th International Confer- ence on Machine Learning, pages 341-349, Madison, WI, 1998. 16. [Nemirovski, 2005] Arkadi Nemirovski. Prox-method with rate of convergence O(1/T) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2005. 17. [Nesterov, 2003] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, New York, NY, 2003. 18. [Sion, 1958] Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176, 1958. 19. [Tan et al., 2020] Zhi-Hao Tan, Peng Tan, Yuan Jiang, and Zhi-Hua Zhou. Multi-label optimal margin distribution machine. Machine Learning, 109(3):623-642, 2020. 20. [Xu et al., 2004] Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In Advances in Neural Information Processing Systems, pages 1537-1544, Vancouver, Canada, 2004. 21. [Zhang and Goldman, 2001] Qi Zhang and Sally A. Gold- man. EM-DD: An improved multiple-instance learning technique. In Advances in Neural Information Processing Systems, pages 1073-1080, Cambridge, MA, 2001. 22. [Zhang and Zhou, 2018a] Teng Zhang and Zhi-Hua Zhou. Optimal margin distribution clustering. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 4474-4481, New Orleans, LA, 2018. 23. [Zhang and Zhou, 2018b] Teng Zhang and Zhi-Hua Zhou. Semi-supervised optimal margin distribution machines. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 3104-3110, Stockholm, Swe- den, 2018. 24. [Zhang and Zhou, 2019] Teng Zhang and Zhi-Hua Zhou. Optimal margin distribution machine. IEEE Transactions on Knowledge and Data Engineering, 32(6):1143-1156, 2019. 25. [Zhao et al., 2008] Bin Zhao, Fei Wang, and Changshui Zhang. Efficient maximum margin clustering via cutting plane algorithm. In Proceedings of the SIAM International Conference on Data Mining, pages 751-762, Atlanta, GA, 2008. 26. [Zhou et al., 2005] Zhi-Hua Zhou, Xiao-Bing Xue, and Yuan Jiang. Locating regions of interest in cbir with multi- instance learning techniques. In Proceedings of the 18th Australian Joint Conference on Advances in Artificial In- telligence, pages 92-101, Sydney, Australia, 2005. 27. [Zhou et al., 2012] Zhi-Hua Zhou, Min-Ling Zhang, Sheng- Jun Huang, and Yu-Feng Li. Multi-instance multi-label learning. Artificial Intelligence, 176(1):2291-2320, 2012. 28. [Zhou, 2014] Zhi-Hua Zhou. Large margin distribution learning. In Proceedings of the 6th IAPR International Workshop on Artificial Neural Networks in Pattern Recog- nition, pages 1-11, Montreal, Canada, 2014.