On the Optimization of Margin Distribution

1 Introduction

Margin has played an important role on the design of learning algorithms from the pioneer work [Vapnik, 1982], which proposed the famous Support Vector Machines (SVMs) by maximizing the minimum margin, i.e. the smallest distance from the instances to the classification boundary. Boser et al. [1992] introduced the kernel technique for SVMs to relax the linear separation. Large margin has been one of the most important principles on the design of learning algorithms in the history of machine learning [Cortes and Vapnik, 1995; Schapire et al., 1998; Rosset et al., 2003; Shivaswamy and Jebara, 2010; Ji et al., 2021], even for recent deep learning [Sokoli´c et al., 2017; Weinstein et al., 2020].

Various margin-based bounds have been presented to study the generalization performance of learning algorithms. Bartlett and Shawe-Taylor [1999] possibly presented the first generalization margin bounds based on VC dimension and fat-shattering dimension. Bartlett and Mendelson [2002] introduced the famous margin bounds based on Rademacher complexity, a data-dependent and finite-sample complexity measure. Kab´an and Durrant [2020] took advantage of geometric structure to provide margin bounds for compressive learning. Grønlund et al. [2020] presented the near-tight margin generalization bound for SVMs. Margin has also been an ingredient to analyze the generalization performance for other algorithms such as boosting [Schapire et al., 1998; Breiman, 1999; Gao and Zhou, 2013], and deep learning [Bartlett et al., 2017; Wei and Ma, 2020].

Margin distribution has been considered as an important ingredient on the design and analysis of learning algorithms, and the basic idea is to optimize some margin statistics, relevant to the whole margin distribution rather than single margin. Garg and Roth [2003] introduced the model complexity measure to optimize margin distribution. Pelckmans et al. [2007] optimized margin distribution via average margin, while Aiolli et al. [2008] tried to maximize the minimum margin and average margin. Zhang and Zhou [2014] proposed the large margin distribution machine by considering average margin and margin variance simultaneously, which motivates the design of a series learning algorithms on the optimization of margin distribution [Cheng et al., 2016; Rastogi et al., 2020]. For deep learning, Jiang et al. [2019] introduced some margin distribution statistics, such as total variation, median quartile, etc., to analyze the generalization of neural networks. There is a relative paucity of theoretical understanding on how to correlate margin distribution with the generalization of learning algorithms.

This work tries to fill the gap between theoretical and empirical studies on the optimization of margin distribution, and the main contributions can be summarized as follows:

• We present a new generalization error bound, which is heavily relevant to margin distribution by incorporating factors such as average margin and semi-variance. Here, semi-variance is a new statistics, counting the average of squared distances between average margin and the instances' margin, that is smaller than average margin.
• Motivated from our theoretical result, we develop the MSVMAv approach, which tries to achieve better generalization performance by optimizing margin distribution in terms of empirical average margin and semi-variance. We find the closed-form solution in optimization, and improve its efficiency via Sherman-Morrison formula.

• We conduct extensive empirical studies to validate the effectiveness of the MSVMAv approach in comparisons with the state-of-the-art algorithms on large-margin or margin distribution optimization.

The rest of this paper is organized as follows. Section 2 introduces some preliminaries. Section 3 presents theoretical analysis. Section 4 proposes the MSVMAv approach. Section 5 conducts extensive empirical studies, and Section 6 concludes with future work.

2 Preliminaries

Let X ⊆ Rd and Y = {+1,-1} denote the instance and label space, respectively. Suppose that D is an underlying (unknown) distribution over the product space X ×Y. Let

be a training sample with each element drawn independently and identically (i.i.d.) from distribution D. We use PrD[·] and ED[·] to refer to the probability and expectation according to distribution D, respectively.

Let H = {h: X → [-1,+1]} be a function space. We define the classification error (or generalization risk) with respect to function h ∈ H and distribution D, as

where the sign function sgn[·] returns +1, 0 and -1 if the argument is positive, zero and negative, respectively, and the indicator function I[·] returns 1 when the argument is true, and 0 otherwise.

Given an example (x, y), the margin of h ∈ H is defined as yh(x), which can be viewed as a measure of the confidence of the classification. We further define the average margin of h ∈ H over distribution D as

We also introduce the empirical Rademacher complexity [Bartlett and Mendelson, 2002] to measure the complexity of function space H as follows:

where each σi is a Rademacher variable with Pr[σi = +1] = Pr[σi = -1] = 1/2 for i ∈ [n].

We finally introduce some notations used in this work. Write [d] = {1, 2, . . . , d} for integer d > 0, and 〈w, x〉 represents the inner product of w and x. Let Id be the identity matrix of size d × d, and denote by ⊤ the transpose of vectors or matrices. For positive f(n) and g(n), we write f(n) = O(g(n)) if g(n)/f(n) → c for constant c < +∞.

3 Theoretical Analysis

We begin with the squared margin loss as follows:

Definition 1. For θ > 0, we define the squared margin loss ℓθ with respect to function h ∈ H as

This is a simple extension from the traditional margin loss [Bartlett and Mendelson, 2002], while we consider the squared loss and unbounded constraint for the negative yh(x). The margin parameter θ is generally irrelevant to learned function h and data distribution in most previous theoretical and algorithmic studies.

In this work, we select margin parameter θ as the average margin when θh > 0, to correlate generalization performance with margin distribution, that is,

which is dependent on data distribution and learned function. Given training sample Sn, we try to learn a function h by minimizing the squared margin loss as follows:

For simplicity, we further introduce the notion of margin semi-variance [Markowitz, 1952] as follows:

Definition 2. Given function h ∈ H and training sample Sn, we define the margin semi-variance as

where θh denotes the average margin defined by Eqn. (1).

The margin semi-variance essentially counts the average of squared deviation between average margin and the margins yih(xi), which are smaller than average margin. This yields an equivalent expression for Eqn. (2) as follows:

that is, optimizing the squared margin loss with parameter θ = θh is equivalent to minimizing margin semi-variance and maximizing average margin simultaneously.

For most real applications, we could learn some relativelygood functions from sufficient training data. Motivated from the notion of weak learner in boosting [Freund and Schapire, 1996], we formally define the set of relatively-good functions for function space H as follows:

Essentially, a relatively-good function is similar to a weak learner, which achieves slightly better performance than the randomly-guessed classifier.

We now present the main theoretical result as follows:

Theorem 1. For small constant ν ≥ 0, let H be a function space with relative-good set Hν. For any δ ∈ (0, 1) and for every h ∈ Hν, the following holds with probability at least 1 - δ over the training sample Sn

with empirical Rademacher complexity ̂Rn(Hν) ≤ ̂Rn(H).

This theorem presents a new generalization error bound, which is heavily relevant to margin distribution by incorporating factors such as average margin and semi-variance. This could shed some new insights on the design of algorithms on the optimization of margin distribution as shown in Section 4.

The proof follows the empirical Rademacher complexity [Bartlett and Mendelson, 2002], while the challenge lies in the distribution-dependent average margin θh. We solve it by constructing a sequence of intervals for average margin θh, and the detailed proof is presented in [Qian et al., 2022].

It remains to study the empirical Rademacher complexity in Theorem 1, and we focus on linear and kernel functions. For instance space X = {x ∈ Rd : ‖x‖ ≤ r} and linear function space H = {h(x) = w⊤x: ‖w‖ ≤ Λ}, let Hν denote the set of relatively-good classifiers. We upper bound the empirical Rademacher complexity as

from the work of [Shalev-Shwartz and Ben-David, 2014]. For kernel function κ(·, ·), we have the kernel function space

We could upper bound the empirical Rademacher complexity for kernel functions, from [Bartlett and Mendelson, 2002],

.

It is also noteworthy that the average margin θh is unknown on the design of new algorithms because of the unknown distribution D, and we resort to the empirical average margin from training sample Sn in practice.

4 The MSVMAv Approach

Motivated from Theorem 1, this section develops the MSVMAv approach on the optimization of margin distribution, and we focus on linear and kernel functions.

4.1 Linear Functions

For linear space H = {hw(x) = 〈w, x〉: ‖w‖ = 1} and training sample Sn, we have the empirical average margin

For simplicity, we omit a bias term on the design of algorithm, and we will augment w and instance x with bias term b and 1 in experiments, respectively, as shown in Section 5. Our optimization problem can be formally written as

where empirical average margin ˆ θw > 0 and empirical margin semi-variance ̂ SV(w) = ∑ni=1 [(ˆ θw - yi〈w, xi〉)+]2 /n. Obviously, this is a non-convex optimization problem, and we would optimize the empirical margin semi-variance and average margin alternatively.

Initialize the linear function w0 by optimizing empirical average margin, that is,

where we solve w0 from its dual problem using Lagrangian function, and the details are given by Qian et al. [2022].

Optimization of Empirical Margin Semi-variance

In the k-th iteration (k ≥ 1) with previous classifier wk-1, we first calculate the empirical average margin ˆ θwk-1 as

We then introduce the minimization of empirical margin semi-variance as follows:

where βk is a proximal regularization parameter. We now introduce the following index set, to present a closed-form solution for the above minimization,

i.e., the index set of instance with margins below the empirical average margin ˆ θwk-1 . We can rewrite the minimization of empirical margin semi-variance as

Denote by w′k the minimizer of the above problem, and we obtain the closed-form solution for w′k as follows

One problem is to calculate the inverse in Eqn. (6), which takes O(d3 ) computational costs (d is dimensionality). This remains one challenge to deal with high-dimensional tasks.

We now present an efficient method to calculate of the inverse in Eqn. (6). For simplicity, we denote by

and it is easy to derive the following recursive relation:

with M0 = Id.

We calculate Mk efficiently from Mk-1 and ShermanMorrison formula [Sherman and Morrison, 1950]. In other

Algorithm 1 The MSVMAv Approach

Input: Training sample Sn, iteration number T , and proximal parameters αk and βk

Output: w

• 1: InitializeM0 = Id, A0 = ∅ and w0 by Eqn. (3)
• 2: for k = 1, 2, · · · , T do
• 3: Compute empirical average margin ˆ θwk-1 by Eqn. (4)
• 4: Solve the index set Ak by Eqn. (5)
• 5: Compute Mk = (Id + ∑i∈Ak xix⊤i /nβk )-1 by Eqns. (7) and (8)
• 6: Compute theminimizerw′k for empirical margin semivariance by Eqn. (9)
• 7: Solve the empirical average margin maximizer wk by Eqn. (10), and normalize wk = wk/ ‖wk‖2
• 8: end for
• 9: return w =wT

words, we initialize M′ = Mk-1, and make the following updates iteratively, based on Sherman-Morrison formula,

We then obtain Mk = M ′ , and the minimizer of empirical margin semi-variance is given by

Optimization of Empirical Average Margin

We now study the maximization of empirical average margin, which can be formalized as:

where αk is a proximal regularization parameter. It is easy to obtain the closed-form solution as follows:

We obtain wk = wk/‖wk‖ in the k-th iteration. Algorithm 1 presents a detailed description of our MSVMAv approach.

4.2 Kernelization

This section focuses on kernel mapping φ : X → H for Hilbert space H, we consider h(x) = 〈w, φ(x)〉 with w ∈ H and φ(x) ∈ H. The optimization problem is given by

where average margin ˆ θw = ∑ni=1 yi〈w, φ(xi)〉/n > 0, and margin semi-variance

It is intractable to solve such optimization problem directly because of high or even infinity dimensionality. According to Representer theorem [Sch¨olkopf et al., 2002], we first have w∗ = ∑ni=1 aiφ(xi), spanned by {φ(xi), i ∈ [n]} with coefficients a1, · · · , an. This follows the prediction

where κ(·, ·) denotes the kernel function. For simplicity, denote by a = (a1, a2, · · · , an)⊤, and write the gram matrix of instances in Sn as

where Ki denotes the k-th column of matrix K. Hence, our optimization problem can be further rewritten as

where the empirical average margin ˆ θa = ∑ni=1 yi〈Ki, a〉/n and semi-variance ̂ SV(a) = ∑ni=1 [(ˆ θa - yi〈Ki, a〉)+]2 /n.

We first initialize the classifier a0 by maximizing the empirical average margin as follows:

In the k-th iteration with previous classifier ak-1, we minimize the margin semi-variance based on previous average margin ˆ θak-1 . We write

and the optimization problem can be given by

where βk is a proximal regularization parameter. We introduce the index set Ak = {i : yi〈Ki, a〉 < ˆ θak-1 for i ∈ [n]}, and obtain the empirical margin semi-variance minimizer

where we use the Sherman-Morrison formula to calculate

We finally maximize the empirical average margin based on the following optimization problem:

where αk is a proximal regularization parameter, and it is easy to get the closed-form solution as follows:

We get the final ak = ak/‖ak‖K in the k-th iteration.

5 Empirical Study

In this section, we present extensive empirical studies to verify the effectiveness of our proposed MSVMAv approach. We consider 30 datasets, including 20 regular and 10 largescale datasets. The number of instances varies from 208 to 88588 while the feature dimensionality ranges from 2 to 1836, covering a wide range of properties. The statistics for all datasets can be found in [Qian et al., 2022].

We compare our proposed MSVMAv approach with stateof-the-art algorithms on large-margin and margin distribution optimization: 1) SVM [Boser et al., 1992], 2) SVR [Drucker et al., 1997] with binary targets, 3) LSSVM [Suykens et al., 2002], 4) MAMC [Pelckmans et al., 2007], 5) ODM [Zhang and Zhou, 2019], 6) FMM [Ji et al., 2021]. The details of compared algorithms can be found in [Qian et al., 2022].

For each dataset, we scale all features into the interval [0, 1], and augment each instance x with constant 1 for the bias of linear model. The empirical average margin θw may be smaller than zero in experiments, when the proximal regularization parameter βk is set too small. In such case, we take the opposite model -w so as to keep the positiveness of empirical average margin.

For our MSVMAv approach, parameters αk and βk are set to be constant and selected by 5-fold cross validation from {2-10 , 2-8 , · · · , 210 }, and the width of Gaussian kernel is chosen from {2-10 /d, 2-8 /d, · · · , 210 /d}. We select the maximum iteration number T = 100 as a stopping criteria for MSVMAv . For SVM, SVR, LSSVM and ODM, we set regularization parameter C ∈ {2-10 , 2-8 , · · · , 210 } by 5fold cross validation again, and the others are set according to their respective references, also shown in [Qian et al., 2022].

We first compare the margin distributions of our proposed MSVMAv approach with other algorithms. Figure 1 illustrates the cumulative margin distributions of different algorithms on four datasets, and similar trends can be observed on other datasets. As can be seen, the curves of our MSVMAv approach generally lie on the rightmost side, which shows the margin distributions of MSVMAv are generally better than that of SVM, ODM and FMM.

We further analyze the generalization performance of our proposed MSVMAv approach with other compared algorithms. All algorithms are evaluated by 30 times of random partitions of datasets with 80% and 20% of data for training and testing, respectively. The test accuracies are obtained by averaging over 30 times. Tables 1 and 2 show the empirical results of our MSVMAv and other algorithms with linear and Gaussian kernel functions, respectively.

From Tables 1 and 2, our proposed MSVMAv approach takes significantly better performance than other algorithms for linear and kernel functions, since win/tie/loss counts show that our approach wins for most datasets, and rarely losses. One intuitive explanation is that our MSVMAv approach achieves better margin distribution by maximizing the empirical average margin and minimizing empirical margin semi-variance, as shown in Figure 1. SVM, SVR and FMM maximize the minimum margin, which ignores the margin distribution. LSSVM and MAMC essentially maximize average margin only, which fails to learn from other margin statistics. ODM takes the average margin and margin variance into consideration, but the process of margin variance minimization could constrain some large margins.

This section omits partial empirical results due to the page limit, including the empirical curves of margin distributions, as well as running time comparisons for our MSVMAv and other compared algorithms. Relevant results can be found in our full work [Qian et al., 2022].

6 Conclusion

Large margin has been one of the most important principles on the design of algorithms in machine learning, and recent empirical studies show new insights on the optimization of margin distribution yet without theoretical supports. This work takes one step on this direction by providing a new generalization error bound, which is heavily relevant to margin distribution by incorporating factors such as average margin and semi-variance. Based on the theoretical results, we develop the MSVMAv approach for margin distribution optimization, and extensive experiments verify its superiority. An interesting future work is to exploit more effective statistics to characterize the whole margin distribution.

Acknowledgements

The authors want to thank the reviewers for helpful comments and suggestions. This work is partially supported by the NSFC (61921006, 61876078, 62006088). Wei Gao is the corresponding author.