# On the Optimization of Margin Distribution

Meng-Zhang Qian1 Zheng Ai1 Teng Zhang2&Wei Gao1
1National Key Laboratory for Novel Software Technology, Nanjing University,
China
2School of Computer Science and Technology, Huazhong University of Science and
Technology, China
{qianmz, aiz<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Margin has played an important role on the design and analysis of learning
algorithms during the past years, mostly working with the maximization of the
minimum margin. Recent years have witnessed the increasing empirical studies
on the optimization of margin distribution according to different statistics
such as medium margin, average margin, margin variance, etc., whereas there is
a relative paucity of theoretical understanding.

In this work, we take one step on this direction by providing a new
generalization error bound, which is heavily relevant to margin distribution
by incorporating ingredients such as average margin and semi-variance, a new
margin statistics for the characterization of margin distribution. Inspired by
the theoretical findings, we propose the MSVMAv, an efficient approach to
achieve better performance by optimizing margin distribution in terms of its
empirical average margin and semi-variance. We finally conduct extensive
experiments to show the superiority of the proposed MSVMAv approach.

##  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. 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ć 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 Bartlett and
Shawe-Taylor (1999) possibly presented the first generalization margin bounds
based on VC dimension and fat-shattering dimension. Bartlett and Mendelson
Bartlett and Mendelson (2002) introduced the famous margin bounds based on
Rademacher complexity, a data-dependent and finite-sample complexity measure.
Kabán and Durrant Kabán and Durrant (2020) took advantage of geometric
structure to provide margin bounds for compressive learning. Grønlund et al.
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 attracted much attention on the design and analysis of
learning algorithms in recent years, which distinguishes from most traditional
margin algorithms by maximizing the minimum margin. Garg and Roth Garg and
Roth (2003) proposed a model complexity measure to optimize margin
distribution. Pelckmans et al. Pelckmans et al. (2007) optimized margin
distribution via average margin, while Aiolli et al. Aiolli et al. (2008)
tried to maximize the minimum margin and average margin. Zhang and Zhou 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.
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 $\mathcal{X}\subseteq\mathbb{R}^{d}$ and $\mathcal{Y}=\\{+1,-1\\}$ denote
the instance and label space, respectively. Suppose that $\mathcal{D}$ is an
underlying (unknown) distribution over the product space
$\mathcal{X}\times\mathcal{Y}$. Let

$S_{n}=\\{(\bm{x}_{1},y_{1}),(\bm{x}_{2},y_{2}),\cdots,(\bm{x}_{n},y_{n})\\}$

be a training sample with each element drawn independently and identically
(i.i.d.) from distribution $\mathcal{D}$. We use $\Pr_{\mathcal{D}}[\cdot]$
and $E_{\mathcal{D}}[\cdot]$ to refer to the probability and expectation
according to distribution $\mathcal{D}$, respectively.

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

$\mathcal{E}(h)=\Pr\nolimits_{\mathcal{D}}[\text{sgn}[h(\bm{x})]\neq
y]=E_{\mathcal{D}}[\mathbb{I}[yh(\bm{x})\leq 0]]\ ,$

where the sign function $\text{sgn}[\cdot]$ returns $+1$, $0$ and $-1$ if the
argument is positive, zero and negative, respectively, and the indicator
function $\mathbb{I}[\cdot]$ returns $1$ when the argument is true, and $0$
otherwise.

Given an example $(\bm{x},y)$, the _margin_ of $h\in\mathcal{H}$ is defined as
$yh(\bm{x})$, which can be viewed as a measure of the confidence of the
classification. We further define the average margin of $h\in\mathcal{H}$ over
distribution $\mathcal{D}$ as

$\theta_{h}=E_{(\bm{x},y)\sim\mathcal{D}}[yh(\bm{x})]\ .$ (1)

We also introduce the empirical Rademacher complexity Bartlett and Mendelson
(2002) to measure the complexity of function space $\mathcal{H}$ as follows:

$\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H})=E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}h(\bm{x}_{i})\right],$

where each $\sigma_{i}$ is a Rademacher variable with
$\Pr[\sigma_{i}=+1]=\Pr[\sigma_{i}=-1]=1/2$ for $i\in[n]$.

We finally introduce some notations used in this work. Write
$[d]=\\{1,2,\ldots,d\\}$ for integer $d>0$, and $\langle\bm{w},\bm{x}\rangle$
represents the inner product of $\bm{w}$ and $\bm{x}$. Let $\bm{I}_{d}$ be the
identity matrix of size $d\times 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)\to c$ for constant $c<+\infty$.

##  3 Theoretical Analysis

We begin with the squared margin loss as follows:

######  Definition 1.

For $\theta>0$, we define the squared margin loss $\ell_{\theta}$ with respect
to function $h\in\mathcal{H}$ as

$\ell_{\theta}\big{(}h,(\bm{x},y)\big{)}=\big{[}(1-yh(\bm{x})/\theta)_{+}\big{]}^{2}\
,$

where $(a)_{+}=\max(0,a)$.

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(\bm{x})$. The margin parameter $\theta$ is generally
irrelevant to learned function $h$ and data distribution in most previous
theoretical and algorithmic studies.

In this work, we select margin parameter $\theta$ as the average margin when
$\theta_{h}>0$, to correlate generalization performance with margin
distribution, that is,

$\theta=\theta_{h}=E_{\mathcal{D}}[yh(\bm{x})]\ ,$

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

$\min_{h\in\mathcal{H}\colon\theta_{h}>0}\left\\{\frac{1}{n}\sum_{i=1}^{n}\left[\left(1-\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}\right)_{+}\right]^{2}\right\\}\
.$ (2)

For simplicity, we further introduce the notion of _margin semi-variance_
Markowitz (1952) as follows:

######  Definition 2.

Given function $h\in\mathcal{H}$ and training sample $S_{n}$, we define the
margin semi-variance as

$\text{SV}(h)=\frac{1}{n}\sum_{i=1}^{n}\left[\left(\theta_{h}-y_{i}h(\bm{x}_{i})\right)_{+}\right]^{2}\
,$

where $\theta_{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 $y_{i}h(\bm{x}_{i})$, which are smaller
than average margin. This yields an equivalent expression for Eqn. (2) as
follows:

$\min_{h\in\mathcal{H}:\theta_{h}\geq\nu>0}\
\big{\\{}\text{SV}(h)/\theta_{h}^{2}\big{\\}}\ ,$

that is, optimizing the squared margin loss with parameter $\theta=\theta_{h}$
is equivalent to minimizing margin semi-variance and maximizing average margin
simultaneously.

For most real applications, we could learn some relatively-good 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 $\mathcal{H}$ as follows:

$\mathcal{H}_{\nu}=\\{h\in\mathcal{H},\theta_{h}\geq\nu\\}\ \text{ for some
small constant }\ \nu>0\ .$

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 $\nu\geq 0$, let $\mathcal{H}$ be a function space with
relative-good set $\mathcal{H}_{\nu}$. For any $\delta\in(0,1)$ and for every
$h\in\mathcal{H}_{\nu}$, the following holds with probability at least
$1-\delta$ over the training sample $S_{n}$

$\mathcal{E}(h)\leq\frac{\text{SV}(h)}{\theta_{h}^{2}}+O\left(\frac{\widehat{\mathfrak{R}}_{n}(\mathcal{H}_{\nu})}{\theta_{h}^{2}}+\sqrt{\frac{1}{2n}\ln\frac{4n}{\delta}}\right)\
,$

with empirical Rademacher complexity
$\widehat{\mathfrak{R}}_{n}(\mathcal{H}_{\nu})\leq\widehat{\mathfrak{R}}_{n}(\mathcal{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
$\theta_{h}$. We solve it by constructing a sequence of intervals for average
margin $\theta_{h}$, and the detailed proof is presented in the Appendix A.

It remains to study the empirical Rademacher complexity in Theorem 1, and we
focus on linear and kernel functions. For instance space
$\mathcal{X}=\\{\bm{x}\in\mathbb{R}^{d}\colon\|\bm{x}\|\leq r\\}$ and linear
function space
$\mathcal{H}=\\{h(\bm{x})=\bm{w^{\top}x}\colon\|\bm{w}\|\leq\Lambda\\}$, let
$\mathcal{H}_{\nu}$ denote the set of relatively-good classifiers. We upper
bound the empirical Rademacher complexity as

$\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})\leq\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H})\leq
r\Lambda/\sqrt{n}$

from the work of Shalev-Shwartz and Ben-David (2014). For kernel function
$\kappa(\cdot,\cdot)$, we have the kernel function space

$\mathcal{H}=\Big{\\{}h(\bm{x})=\sum_{i=1}^{n}a_{i}\kappa(\bm{x}_{i},\bm{x})\colon\sum_{i,j=1}^{n}a_{i}a_{j}\kappa(\bm{x}_{i},\bm{x}_{j})\leq\Lambda^{2}\Big{\\}}.$

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

$\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})\leq\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H})\leq\frac{2\Lambda}{n}\Big{(}\sum_{i=1}^{n}\kappa(\bm{x}_{i},\bm{x}_{i})\Big{)}^{1/2}\
.$

It is also noteworthy that the average margin $\theta_{h}$ is unknown on the
design of new algorithms because of the unknown distribution $\mathcal{D}$,
and we resort to the empirical average margin from training sample $S_{n}$ 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
$\mathcal{H}=\\{h_{\bm{w}}(\bm{x})=\langle\bm{w},\bm{x}\rangle\colon\|\bm{w}\|=1\\}$
and training sample $S_{n}$, we have the empirical average margin

$\hat{\theta}_{\bm{w}}=\frac{1}{n}\sum_{i=1}^{n}y_{i}\langle\bm{w},\bm{x}_{i}\rangle\
.$

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

$\min_{\|\bm{w}\|_{2}=1}\Big{\\{}\frac{\widehat{\text{SV}}(\bm{w})}{\hat{\theta}_{\bm{w}}}\Big{\\}}\
,$

where empirical average margin $\hat{\theta}_{\bm{w}}>0$ and empirical margin
semi-variance
$\widehat{\text{SV}}(\bm{w})=\sum_{i=1}^{n}[(\hat{\theta}_{\bm{w}}-y_{i}\langle\bm{w},\bm{x}_{i}\rangle)_{+}]^{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 $\bm{w}_{0}$ by optimizing empirical average
margin, that is,

$\bm{w}_{0}=\mathop{\arg\max}_{\|\bm{w}\|^{2}_{2}=1}\sum_{i=1}^{n}\frac{y_{i}\langle\bm{w},\bm{x}_{i}\rangle}{n}=\sum_{i=1}^{n}\frac{y_{i}\bm{x}_{i}}{\|\sum_{i=1}^{n}y_{i}\bm{x}_{i}\|_{2}}\
,$ (3)

where we solve $\bm{w}_{0}$ from its dual problem using Lagrangian function,
and the details can be found in Appendix B.

#### Optimization of empirical margin semi-variance

In the $k$-th iteration $(k\geq 1)$ with previous classifier $\bm{w}_{k-1}$,
we first calculate the empirical average margin $\hat{\theta}_{\bm{w}_{k-1}}$
as

$\hat{\theta}_{\bm{w}_{k-1}}=\frac{1}{n}\sum_{i=1}^{n}y_{i}\langle\bm{w}_{k-1},\bm{x}_{i}\rangle\
.$ (4)

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

$\min_{\bm{w}}\Big{\\{}\sum_{i=1}^{n}\frac{[(\hat{\theta}_{\bm{w}_{k-1}}-y_{i}\langle\bm{w},\bm{x}_{i}\rangle)_{+}]^{2}}{n}+\beta_{k}\left\|\bm{w}-\bm{w}_{k-1}\right\|_{2}^{2}\Big{\\}},$

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

$\mathcal{A}_{k}=\big{\\{}i\colon
y_{i}\langle\bm{w}_{k-1},\bm{x}_{i}\rangle<\hat{\theta}_{\bm{w}_{k-1}}\quad\text{for}\quad
i\in[n]\big{\\}}\ ,$ (5)

i.e., the index set of instance with margins below the empirical average
margin $\hat{\theta}_{\bm{w}_{k-1}}$. We can rewrite the minimization of
empirical margin semi-variance as

$\min_{\bm{w}}\Big{\\{}\sum_{i\in\mathcal{A}_{k}}\frac{(\hat{\theta}_{\bm{w}_{k-1}}-y_{i}\langle\bm{w},\bm{x}_{i}\rangle)^{2}}{n}+\beta_{k}\left\|\bm{w}-\bm{w}_{k-1}\right\|_{2}^{2}\Big{\\}}\
.$

Denote by $\bm{w}^{\prime}_{k}$ the minimizer of the above problem, and we
obtain the closed-form solution for $\bm{w}^{\prime}_{k}$ as follows

$\Big{(}\bm{I}_{d}+\sum_{i\in\mathcal{A}_{k}}\frac{\bm{x}_{i}\bm{x}_{i}^{\top}}{n\beta_{k}}\Big{)}^{-1}\Big{(}\frac{\hat{\theta}_{\bm{w}_{k-1}}}{n\beta_{k}}\sum_{i\in\mathcal{A}_{k}}y_{i}\bm{x}_{i}+\bm{w}_{k-1}\Big{)}.$
(6)

One problem is to calculate the inverse in Eqn. (6), which takes $O(d^{3})$
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

$\bm{M}_{k}=\Big{(}\bm{I}_{d}+\sum\nolimits_{i\in\mathcal{A}_{k}}{\bm{x}_{i}\bm{x}_{i}^{\top}}\big{/}{n\beta_{k}}\Big{)}^{-1}\
\text{ for }\ k=1,2,\cdots,$

and it is easy to derive the following recursive relation:

$\bm{M}^{-1}_{k}=\bm{M}_{k-1}^{-1}-\sum_{i\in\mathcal{A}_{k-1}\setminus\mathcal{A}_{k}}\frac{\bm{x}_{i}\bm{x}_{i}^{\top}}{n\beta}+\sum_{i\in\mathcal{A}_{k}\setminus\mathcal{A}_{k-1}}\frac{\bm{x}_{i}\bm{x}_{i}^{\top}}{n\beta}\
,$

with $\bm{M}_{0}=\bm{I}_{d}$.

We calculate $\bm{M}_{k}$ efficiently from $\bm{M}_{k-1}$ and Sherman-Morrison
formula Sherman and Morrison (1950). In other words, we initialize
$\bm{M}^{\prime}=\bm{M}_{k-1}$, and make the following updates iteratively,
based on Sherman-Morrison formula,

$\displaystyle\bm{M}^{\prime}=\bm{M}^{\prime}-\frac{\bm{M}^{\prime}\bm{x}_{i}\bm{x}_{i}^{\top}\bm{M}^{\prime}}{\bm{x}_{i}^{\top}\bm{M}^{\prime}\bm{x}_{i}-n\beta_{k}}\
\ \text{ for }\ \ i\in\mathcal{A}_{k-1}\setminus\mathcal{A}_{k}\ ,$ (7)
$\displaystyle\bm{M}^{\prime}=\bm{M}^{\prime}-\frac{\bm{M}^{\prime}\bm{x}_{i}\bm{x}_{i}^{\top}\bm{M}^{\prime}}{\bm{x}_{i}^{\top}\bm{M}^{\prime}\bm{x}_{i}+n\beta_{k}}\
\ \text{ for }\ \ i\in\mathcal{A}_{k}\setminus\mathcal{A}_{k-1}\ .$ (8)

We then obtain $\bm{M}_{k}=\bm{M}^{\prime}$, and the minimizer of empirical
margin semi-variance is given by

$\bm{w}^{\prime}_{k}=\bm{M}^{\prime}\Big{(}\frac{\hat{\theta}_{\bm{w}_{k-1}}}{n\beta_{k}}\sum_{i\in\mathcal{A}_{k}}y_{i}\bm{x}_{i}+\bm{w}_{k-1}\Big{)}.$
(9)

#### Optimization of empirical average margin

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

$\bm{w}_{k}=\mathop{\arg\min}_{\bm{w}}\Big{\\{}-\frac{1}{n}\sum_{i=1}^{n}y_{i}\langle\bm{w},\bm{x}_{i}\rangle+\alpha_{k}\left\|\bm{w}-\bm{w}^{\prime}_{k}\right\|_{2}^{2}\Big{\\}},$

where $\alpha_{k}$ is a proximal regularization parameter. It is easy to
obtain the closed-form solution as follows:

$\bm{w}_{k}=\bm{w}^{\prime}_{k}+\frac{1}{2\alpha_{k}n}\sum_{i=1}^{n}y_{i}\bm{x}_{i}\
.$ (10)

We obtain $\bm{w}_{k}=\bm{w}_{k}/\|\bm{w}_{k}\|$ in the $k$-th iteration.
Algorithm 1 presents a detailed description of our MSVMAv approach.

Algorithm 1 The MSVMAv Approach

Input: Training sample $S_{n}$, iteration number $T$, and proximal parameters
$\alpha_{k}$ and $\beta_{k}$
Output: $\bm{w}$

1: Initialize $\bm{M}_{0}=\bm{I}_{d}$, $A_{0}=\emptyset$ and $\bm{w}_{0}$ by
Eqn. (3)

2: for $k=1,2,\cdots,T$ do

3: Compute empirical average margin $\hat{\theta}_{\bm{w}_{k-1}}$ by Eqn. (4)

4: Solve the index set $\mathcal{A}_{k}$ by Eqn. (5)

5: Compute
$\bm{M}_{k}=\big{(}\bm{I}_{d}+\sum_{i\in\mathcal{A}_{k}}{\bm{x}_{i}\bm{x}_{i}^{\top}}\big{/}{n\beta_{k}}\big{)}^{-1}$
by Eqns. (7) and (8)

6: Compute the minimizer $\bm{w}_{k}^{\prime}$ for empirical margin semi-
variance by Eqn. (9)

7: Solve the empirical average margin maximizer $\bm{w}_{k}$ by Eqn. (10), and
normalize $\bm{w}_{k}=\bm{w}_{k}/\left\|\bm{w}_{k}\right\|_{2}$

8: end for

9: return $\bm{w}=\bm{w}_{T}$

###  4.2 Kernelization

This section focuses on kernel mapping $\bm{\phi}:\mathcal{X}\to\mathbb{H}$
for Hilbert space $\mathbb{H}$, we consider
$h(\bm{x})=\langle\bm{w},\bm{\phi}(\bm{x})\rangle$ with $\bm{w}\in\mathbb{H}$
and $\bm{\phi}(\bm{x})\in\mathbb{H}$. The optimization problem is given by

$\min_{\bm{w}}\Big{\\{}\frac{\widehat{\text{SV}}(\bm{w})}{\hat{\theta}_{\bm{w}}}\Big{\\}}\
,$

where average margin
$\hat{\theta}_{\bm{w}}=\sum_{i=1}^{n}y_{i}\langle\bm{w},\bm{\phi}(\bm{x}_{i})\rangle/n>0$,
and margin semi-variance

$\widehat{\text{SV}}(\bm{w})=\frac{1}{n}\sum_{i=1}^{n}\left[\left(\hat{\theta}_{\bm{w}}-y_{i}\langle\bm{w},\bm{\phi}(\bm{x}_{i})\rangle\right)_{+}\right]^{2}\
.$

Figure 1: Cumulative frequency versus margin of our MSVMAv and other algorithms such as SVM, ODM and FMM. The more right the curve, the better the margin distribution. Table 1: Comparisons of the test accuracies (mean$\pm$std.) on 30 datasets. $\bullet/\circ$ indicates that our MSVMAv approach is significantly better/worse than the corresponding algorithms (pairwise t-tests at 95% significance level). ‘N/A’ indicates that LSSVM does not return results on the data set within 12 hours.  Dataset |  MSVMAv | SVM | SVR | LSSVM | ODM | MAMC | FMM
---|---|---|---|---|---|---|---
advertise |  .9837$\pm$.0015 |  .9823$\pm$.0021$\bullet$ |  .9825$\pm$.0024$\bullet$ |  .9819$\pm$.0019$\bullet$ |  .9701$\pm$.0021$\bullet$ |  .9132$\pm$.0007$\bullet$ |  .9799$\pm$.0025$\bullet$
australian |  .8314$\pm$.0079 |  .8167$\pm$.0077$\bullet$ |  .8171$\pm$.0048$\bullet$ |  .8220$\pm$.0036$\bullet$ |  .8104$\pm$.0065$\bullet$ |  .7700$\pm$.0201$\bullet$ |  .8295$\pm$.0100
bibtex |  .7417$\pm$.0040 |  .7378$\pm$.0069$\bullet$ |  .7469$\pm$.0060$\circ$ |  .7478$\pm$.0046$\circ$ |  .7469$\pm$.0053$\circ$ |  .6689$\pm$.0123$\bullet$ |  .7371$\pm$.0062$\bullet$
biodeg |  .8712$\pm$.0087 |  .8741$\pm$.0068 |  .8490$\pm$.0107$\bullet$ |  .8741$\pm$.0068 |  .8681$\pm$.0075 |  .6872$\pm$.0000$\bullet$ |  .8613$\pm$.0089$\bullet$
breastw |  .9730$\pm$.0038 |  .9725$\pm$.0041 |  .9701$\pm$.0051$\bullet$ |  .9684$\pm$.0051$\bullet$ |  .8428$\pm$.0099$\bullet$ |  .4088$\pm$.0000$\bullet$ |  .9720$\pm$.0063
diabetes |  .7530$\pm$.0088 |  .7561$\pm$.0104 |  .7478$\pm$.0077$\bullet$ |  .7491$\pm$.0078$\bullet$ |  .6110$\pm$.0146$\bullet$ |  .5974$\pm$.0000$\bullet$ |  .7496$\pm$.0082
emotions |  .8216$\pm$.0074 |  .7983$\pm$.0130$\bullet$ |  .7675$\pm$.0181$\bullet$ |  .8036$\pm$.0127$\bullet$ |  .8084$\pm$.0111$\bullet$ |  .6975$\pm$.0000$\bullet$ |  .7697$\pm$.0218$\bullet$
german |  .7518$\pm$.0097 |  .7457$\pm$.0095$\bullet$ |  .7525$\pm$.0107 |  .7530$\pm$.0106 |  .7502$\pm$.0095 |  .6800$\pm$.0000$\bullet$ |  .7525$\pm$.0102
halloffame |  .9644$\pm$.0025 |  .9617$\pm$.0047$\bullet$ |  .9593$\pm$.0041$\bullet$ |  .9617$\pm$.0047$\bullet$ |  .9620$\pm$.0028$\bullet$ |  .9280$\pm$.0000$\bullet$ |  .9598$\pm$.0036$\bullet$
hill-valley |  .7771$\pm$.0631 |  .5972$\pm$.0195$\bullet$ |  .6999$\pm$.0572$\bullet$ |  .5972$\pm$.0195$\bullet$ |  .8898$\pm$.0079$\circ$ |  .5000$\pm$.0000$\bullet$ |  .8526$\pm$.0296$\circ$
kc1 |  .8713$\pm$.0025 |  .8711$\pm$.0039 |  .8642$\pm$.0026$\bullet$ |  .8711$\pm$.0039 |  .8690$\pm$.0035$\bullet$ |  .8649$\pm$.0000$\bullet$ |  .8701$\pm$.0028$\bullet$
parkinsons |  .9222$\pm$.0277 |  .8923$\pm$.0388$\bullet$ |  .9342$\pm$.0315 |  .9444$\pm$.0338$\circ$ |  .8863$\pm$.0342$\bullet$ |  .7949$\pm$.0000$\bullet$ |  .8932$\pm$.0266$\bullet$
pbcseq |  .6626$\pm$.0074 |  .6439$\pm$.0147$\bullet$ |  .6595$\pm$.0104 |  .6555$\pm$.0104$\bullet$ |  .6562$\pm$.0125$\bullet$ |  .6700$\pm$.0187$\circ$ |  .6549$\pm$.0117$\bullet$
sleepdata |  .6925$\pm$.0056 |  .6743$\pm$.0051$\bullet$ |  .6833$\pm$.0064$\bullet$ |  .6712$\pm$.0124$\bullet$ |  .5691$\pm$.0156$\bullet$ |  .5659$\pm$.0000$\bullet$ |  .6833$\pm$.0047$\bullet$
students |  .8957$\pm$.0062 |  .8913$\pm$.0088$\bullet$ |  .8870$\pm$.0064$\bullet$ |  .8867$\pm$.0069$\bullet$ |  .8893$\pm$.0046$\bullet$ |  .5133$\pm$.0129$\bullet$ |  .8898$\pm$.0040$\bullet$
titanic |  .7658$\pm$.0038 |  .7636$\pm$.0000$\bullet$ |  .7636$\pm$.0000$\bullet$ |  .7636$\pm$.0000$\bullet$ |  .7509$\pm$.0211$\bullet$ |  .6386$\pm$.0000$\bullet$ |  .7636$\pm$.0000$\bullet$
tokyo1 |  .9351$\pm$.0040 |  .9307$\pm$.0031$\bullet$ |  .9337$\pm$.0027$\bullet$ |  .9281$\pm$.0054$\bullet$ |  .9248$\pm$.0053$\bullet$ |  .7523$\pm$.0534$\bullet$ |  .9363$\pm$.0037
vehicle |  .9708$\pm$.0057 |  .9422$\pm$.0473$\bullet$ |  .9746$\pm$.0031$\circ$ |  .9748$\pm$.0034$\circ$ |  .9720$\pm$.0061 |  .7041$\pm$.0000$\bullet$ |  .9718$\pm$.0083
vertebra |  .8194$\pm$.0197 |  .7978$\pm$.0149$\bullet$ |  .7731$\pm$.0144$\bullet$ |  .7753$\pm$.0131$\bullet$ |  .7957$\pm$.0105$\bullet$ |  .7581$\pm$.0000$\bullet$ |  .7763$\pm$.0100$\bullet$
wdbc |  .9778$\pm$.0067 |  .9787$\pm$.0084 |  .9725$\pm$.0030$\bullet$ |  .9696$\pm$.0044$\bullet$ |  .9237$\pm$.0094$\bullet$ |  .5398$\pm$.1287$\bullet$ |  .9655$\pm$.0064$\bullet$
a9a |  .8433$\pm$.0009 |  .8417$\pm$.0007$\bullet$ |  .8403$\pm$.0007$\bullet$ |  .8358$\pm$.0006$\bullet$ |  .8430$\pm$.0012 |  .7577$\pm$.0000$\bullet$ |  .8390$\pm$.0012$\bullet$
acoustic |  .7494$\pm$.0011 |  .7321$\pm$.0037$\bullet$ |  .7394$\pm$.0004$\bullet$ |  N/A$\bullet$ |  .7406$\pm$.0023$\bullet$ |  .7206$\pm$.0055$\bullet$ |  .7402$\pm$.0005$\bullet$
bank |  .9057$\pm$.0004 |  .8960$\pm$.0008$\bullet$ |  .9015$\pm$.0004$\bullet$ |  N/A$\bullet$ |  .9021$\pm$.0006$\bullet$ |  .8854$\pm$.0000$\bullet$ |  .9021$\pm$.0005$\bullet$
eurgbp |  .5332$\pm$.0027 |  .5042$\pm$.0061$\bullet$ |  .5317$\pm$.0028$\bullet$ |  N/A$\bullet$ |  .5111$\pm$.0084$\bullet$ |  .4985$\pm$.0000$\bullet$ |  .5288$\pm$.0028$\bullet$
jm1 |  .8125$\pm$.0015 |  .8132$\pm$.0012 |  .8119$\pm$.0016 |  .8123$\pm$.0015 |  .8065$\pm$.0000$\bullet$ |  .8065$\pm$.0000$\bullet$ |  .8076$\pm$.0010$\bullet$
magic |  .7998$\pm$.0005 |  .7976$\pm$.0012$\bullet$ |  .7928$\pm$.0008$\bullet$ |  .7912$\pm$.0009$\bullet$ |  .7943$\pm$.0007$\bullet$ |  .6514$\pm$.0000$\bullet$ |  .7987$\pm$.0014$\bullet$
nomao |  .9453$\pm$.0005 |  .9421$\pm$.0061$\bullet$ |  .9439$\pm$.0005$\bullet$ |  N/A$\bullet$ |  .9452$\pm$.0004 |  .7062$\pm$.0000$\bullet$ |  .9442$\pm$.0008$\bullet$
phishing |  .9388$\pm$.0011 |  .9405$\pm$.0017$\circ$ |  .9371$\pm$.0007$\bullet$ |  .9343$\pm$.0008$\bullet$ |  .9386$\pm$.0014 |  .5532$\pm$.0008$\bullet$ |  .9318$\pm$.0009$\bullet$
pol |  .9054$\pm$.0013 |  .8746$\pm$.0398$\bullet$ |  .9002$\pm$.0019$\bullet$ |  .9041$\pm$.0018$\bullet$ |  .6788$\pm$.0037$\bullet$ |  .6740$\pm$.0000$\bullet$ |  .8866$\pm$.0016$\bullet$
run-walk |  .7260$\pm$.0007 |  .7169$\pm$.0000$\bullet$ |  .7077$\pm$.0004$\bullet$ |  N/A$\bullet$ |  .7104$\pm$.0061$\bullet$ |  .5431$\pm$.0757$\bullet$ |  .7261$\pm$.0054
Win/Tie/Loss | 23/6/1 | 24/4/2 | 23/4/3 | 22/6/2 | 29/0/1 | 22/7/1

It is intractable to solve such optimization problem directly because of high
or even infinity dimensionality. According to Representer theorem Schölkopf et
al. (2002), we first have
$\bm{w}^{*}=\sum_{i=1}^{n}a_{i}\bm{\phi}(\bm{x}_{i})$, spanned by
$\\{\bm{\phi}(\bm{x}_{i}),i\in[n]\\}$ with coefficients $a_{1},\cdots,a_{n}$.
This follows the prediction

$h(\bm{x})=\langle\bm{w},\bm{\phi}(\bm{x})\rangle=\sum_{i=1}^{n}a_{i}\kappa(\bm{x},\bm{x}_{i})\
,$

where $\kappa(\cdot,\cdot)$ denotes the kernel function. For simplicity,
denote by $\bm{a}=(a_{1},a_{2},\cdots,a_{n})^{\top}$, and write the gram
matrix of instances in $S_{n}$ as

$\bm{K}=(\bm{K}_{1},\bm{K}_{2},\cdots,\bm{K}_{n})=\big{(}K_{ij}\big{)}_{n\times
n}=\big{(}\kappa(\bm{x}_{i},\bm{x}_{j})\big{)}_{n\times n},$

where $\bm{K}_{i}$ denotes the $k$-th column of matrix $\bm{K}$. Hence, our
optimization problem can be further rewritten as

$\min_{\bm{a}}\Big{\\{}\frac{1}{n}\sum_{i=1}^{n}\left[\Big{(}1-\frac{y_{i}\langle\bm{K}_{i},\bm{a}\rangle}{\hat{\theta}_{\bm{a}}}\Big{)}_{+}\right]^{2}\Big{\\}}=\min_{\bm{a}}\Big{\\{}\frac{\widehat{\text{SV}}(\bm{a})}{\hat{\theta}_{\bm{a}}}\Big{\\}}\
,$

where the empirical average margin
$\hat{\theta}_{\bm{a}}=\sum_{i=1}^{n}y_{i}\langle\bm{K}_{i},\bm{a}\rangle/n$
and semi-variance
$\widehat{\text{SV}}(\bm{a})=\sum_{i=1}^{n}[(\hat{\theta}_{\bm{a}}-y_{i}\langle\bm{K}_{i},\bm{a}\rangle)_{+}]^{2}/n$.

We first initialize the classifier $\bm{a}_{0}$ by maximizing the empirical
average margin as follows:

$\bm{a}_{0}=\mathop{\arg\max}_{\bm{a}^{\top}\bm{K}\bm{a}=1}\Big{\\{}\frac{1}{n}\sum_{i=1}^{n}y_{i}\langle\bm{K}_{i},\bm{a}\rangle\Big{\\}}.$

In the $k$-th iteration with previous classifier $\bm{a}_{k-1}$, we minimize
the margin semi-variance based on previous average margin
$\hat{\theta}_{\bm{a}_{k-1}}$. We write

$\big{\|}\bm{a}-\bm{a}_{k-1}\big{\|}_{\bm{I}_{n}+\bm{K}}=\big{(}(\bm{a}-\bm{a}_{k-1})^{\top}(\bm{I}_{n}+\bm{K}\big{)}\big{(}\bm{a}-\bm{a}_{k-1})\big{)}^{1/2}\
,$

and the optimization problem can be given by

$\min_{\bm{a}}\Big{\\{}\sum_{i=1}^{n}\frac{[(\hat{\theta}_{\bm{a}_{k-1}}-y_{i}\langle\bm{K}_{i},\bm{a}\rangle)_{+}]^{2}}{n}+\beta_{k}\|\bm{a}-\bm{a}_{k-1}\|^{2}_{\bm{I}_{n}+\bm{K}}\Big{\\}},$

where $\beta_{k}$ is a proximal regularization parameter. We introduce the
index set $\mathcal{A}_{k}=\\{i\colon
y_{i}\langle\bm{K}_{i},\bm{a}\rangle<\hat{\theta}_{\bm{a}_{k-1}}\text{ for
}i\in[n]\\}$, and obtain the empirical margin semi-variance minimizer

$\bm{a}^{\prime}_{k}=\bm{M}_{k}\Big{(}(\bm{K}+\bm{I}_{n})\bm{a}_{k-1}+\hat{\theta}_{\bm{a}^{\prime}_{k}}\sum_{i\in\mathcal{A}_{k}}\frac{y_{i}\bm{K}_{i}^{\top}}{n\beta}\Big{)}$

with
$\bm{M}_{k}=(\sum_{i\in\mathcal{A}_{k}}{\bm{K}_{i}^{\top}\bm{K}_{i}}/{n\beta}+\bm{K}+\bm{I}_{n})^{-1}$,
which can be calculated efficiently by Sherman-Morrison formula again.

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

$\min_{\bm{a_{k}}}\Big{\\{}-\frac{1}{n}\sum_{i=1}^{n}y_{i}\bm{K}_{i}\bm{a}_{k}+\alpha_{k}(\bm{a}_{k}-\bm{a}^{\prime}_{k})^{\top}\bm{K}(\bm{a}_{k}-\bm{a}^{\prime}_{k})\Big{\\}},$

where $\alpha_{k}$ is a proximal regularization parameter, and it is easy to
get the closed-form solution as follows:

$\bm{a}_{k}=\bm{a}^{\prime}_{k}+{[y_{1},y_{2},\cdots,y_{n}]^{\top}}/{2\alpha_{k}n}\
.$

We get the final $\bm{a}_{k}=\bm{a}_{k}/\|\bm{a}_{k}\|_{\bm{K}}$ in the $k$-th
iteration.

Table 2: Comparisons of the test accuracies (mean$\pm$std.) on 20 datasets. We use Gaussian kernel for all algorithms. $\bullet/\circ$ indicates that our MSVMAv approach is significantly better/worse than the corresponding algorithms (pairwise t-tests at 95% significance level). Dataset |  MSVMAv | SVM | SVR | LSSVM | ODM | MAMC | FMM
---|---|---|---|---|---|---|---
advertise |  .9837$\pm$.0014 |  .9820$\pm$.0023$\bullet$ |  .9835$\pm$.0019 |  .9848$\pm$.0016$\circ$ |  .9838$\pm$.0016 |  .9547$\pm$.0026$\bullet$ |  .9810$\pm$.0028$\bullet$
australian |  .8580$\pm$.0078 |  .8225$\pm$.0087$\bullet$ |  .8210$\pm$.0080$\bullet$ |  .8357$\pm$.0111$\bullet$ |  .8329$\pm$.0088$\bullet$ |  .8302$\pm$.0122$\bullet$ |  .8237$\pm$.0060$\bullet$
bibtex |  .7554$\pm$.0036 |  .7506$\pm$.0050$\bullet$ |  .7508$\pm$.0053$\bullet$ |  .7505$\pm$.0056$\bullet$ |  .7570$\pm$.0045 |  .6714$\pm$.0397$\bullet$ |  .7509$\pm$.0050$\bullet$
biodeg |  .8834$\pm$.0081 |  .8687$\pm$.0115$\bullet$ |  .8580$\pm$.0089$\bullet$ |  .8712$\pm$.0093$\bullet$ |  .8845$\pm$.0095 |  .8559$\pm$.0098$\bullet$ |  .8915$\pm$.0096$\circ$
breastw |  .9783$\pm$.0013 |  .9710$\pm$.0013$\bullet$ |  .9703$\pm$.0050$\bullet$ |  .9713$\pm$.0018$\bullet$ |  .9710$\pm$.0013$\bullet$ |  .9774$\pm$.0022$\bullet$ |  .9710$\pm$.0013$\bullet$
diabetes |  .7576$\pm$.0074 |  .7574$\pm$.0094 |  .7502$\pm$.0096$\bullet$ |  .7411$\pm$.0112$\bullet$ |  .7504$\pm$.0082$\bullet$ |  .6779$\pm$.0197$\bullet$ |  .7385$\pm$.0105$\bullet$
emotions |  .7986$\pm$.0122 |  .7899$\pm$.0156$\bullet$ |  .7756$\pm$.0164$\bullet$ |  .8115$\pm$.0124$\circ$ |  .8101$\pm$.0147$\circ$ |  .7952$\pm$.0120 |  .8078$\pm$.0126$\circ$
german |  .7465$\pm$.0099 |  .7443$\pm$.0096 |  .7198$\pm$.0174$\bullet$ |  .7353$\pm$.0143$\bullet$ |  .7285$\pm$.0156$\bullet$ |  .7198$\pm$.0154$\bullet$ |  .7277$\pm$.0127$\bullet$
halloffame |  .9677$\pm$.0025 |  .9625$\pm$.0020$\bullet$ |  .9578$\pm$.0053$\bullet$ |  .9523$\pm$.0060$\bullet$ |  .9617$\pm$.0025$\bullet$ |  .9510$\pm$.0028$\bullet$ |  .9590$\pm$.0034$\bullet$
hill-valley |  .6826$\pm$.0184 |  .6668$\pm$.0177$\bullet$ |  .6482$\pm$.0135$\bullet$ |  .7116$\pm$.0678$\circ$ |  .5950$\pm$.0360$\bullet$ |  .5402$\pm$.0320$\bullet$ |  .7886$\pm$.0299$\circ$
kc1 |  .8739$\pm$.0042 |  .8701$\pm$.0057$\bullet$ |  .8689$\pm$.0045$\bullet$ |  .8703$\pm$.0044$\bullet$ |  .8716$\pm$.0055 |  .8764$\pm$.0027$\circ$ |  .8706$\pm$.0038$\bullet$
parkinsons |  .9573$\pm$.0223 |  .9282$\pm$.0203$\bullet$ |  .9393$\pm$.0193$\bullet$ |  .9393$\pm$.0224$\bullet$ |  .9385$\pm$.0157$\bullet$ |  .9214$\pm$.0174$\bullet$ |  .9402$\pm$.0167$\bullet$
pbcseq |  .7350$\pm$.0143 |  .7214$\pm$.0152$\bullet$ |  .7317$\pm$.0151 |  .7312$\pm$.0165 |  .7269$\pm$.0221$\bullet$ |  .7076$\pm$.0149$\bullet$ |  .7238$\pm$.0184$\bullet$
sleepdata |  .7407$\pm$.0129 |  .7192$\pm$.0105$\bullet$ |  .7211$\pm$.0061$\bullet$ |  .7037$\pm$.0083$\bullet$ |  .7050$\pm$.0083$\bullet$ |  .7055$\pm$.0056$\bullet$ |  .7182$\pm$.0094$\bullet$
students |  .8977$\pm$.0119 |  .8920$\pm$.0079$\bullet$ |  .8665$\pm$.0098$\bullet$ |  .8898$\pm$.0072$\bullet$ |  .8805$\pm$.0142$\bullet$ |  .6543$\pm$.0185$\bullet$ |  .8993$\pm$.0062
titanic |  .7825$\pm$.0048 |  .7823$\pm$.0052 |  .7823$\pm$.0052 |  .7823$\pm$.0052 |  .7767$\pm$.0075$\bullet$ |  .7823$\pm$.0052 |  .7823$\pm$.0052
tokyo1 |  .9406$\pm$.0037 |  .9241$\pm$.0050$\bullet$ |  .9257$\pm$.0060$\bullet$ |  .9337$\pm$.0054$\bullet$ |  .9253$\pm$.0053$\bullet$ |  .9229$\pm$.0039$\bullet$ |  .9248$\pm$.0050$\bullet$
vehicle |  .9793$\pm$.0083 |  .9795$\pm$.0090 |  .9856$\pm$.0073$\circ$ |  .9899$\pm$.0070$\circ$ |  .9722$\pm$.0088$\bullet$ |  .9625$\pm$.0105$\bullet$ |  .9805$\pm$.0093
vertebra |  .8280$\pm$.0240 |  .7898$\pm$.0098$\bullet$ |  .7957$\pm$.0183$\bullet$ |  .8108$\pm$.0176$\bullet$ |  .8000$\pm$.0122$\bullet$ |  .7769$\pm$.0126$\bullet$ |  .7962$\pm$.0153$\bullet$
wdbc |  .9819$\pm$.0081 |  .9810$\pm$.0056 |  .9772$\pm$.0066$\bullet$ |  .9842$\pm$.0035 |  .9795$\pm$.0052 |  .9526$\pm$.0089$\bullet$ |  .9526$\pm$.0089$\bullet$
Win/Tie/Loss | 15/5/0 | 16/3/1 | 13/3/4 | 14/5/1 | 17/2/1 | 14/3/3

##  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 large-scale 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 details of datasets can be
found in Appendix C.

We implement our proposed MSVMAv approach according to Section 4 with slight
modifications. We first augment $\bm{w}$ and instance $\bm{x}$ with $b$ and
$1$ to deal with the bias term as mentioned in Section 4. In real-world
application, it is possible for empirical average margin $\theta_{\bm{w}}$ to
fall below zero if the proximal regularization parameter $\beta_{k}$ is set
too small, which violates our constraint in Section 4. We take the opposite
vector of $\bm{w}$ or $\bm{a}$ under this situation to force the empirical
average margin positive all the time.

We compare our proposed MSVMAv approach with state-of-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). Relevant algorithmic introductions can be found in Appendix
D.

For each dataset, we scale all features into the interval $[0,1]$. For our
proposed MSVMAv approach, parameters $\alpha_{k}$ and $\beta_{k}$ are set to
be constant and selected by $5$-fold cross validation from
$\\{2^{-10},2^{-8},\cdots,2^{10}\\}$, and the width of Gaussian kernel is
chosen from $\\{2^{-10}/d,2^{-8}/d,\cdots,2^{10}/d\\}$. We set the maximum
iteration number $T=100$ as a unified stopping criteria for our MSVMAv
approach. For SVM, SVR, LSSVM and ODM, we select the regularization parameter
$C\in\\{2^{-10},2^{-8},\cdots,2^{10}\\}$ by $5$-fold cross validation again.
Other parameters are set as that of their respective work which can also be
found in Appendix D.

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 some representative 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. In other words, our proposed MSVMAv approach produces the largest
margin for most instances.

For generalization, we then analyze the performance of our proposed MSVMAv
approach and other 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 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 as shown in Figure 1 by maximizing the empirical average
margin and empirical margin semi-variance. SVM, SVR and FMM maximize the
minimum margin, ignoring the margin distribution. LSSVM and MAMC essentially
maximize average margin only, failing to learn information from other
statistics. ODM takes the average margin and margin variance into
consideration, but the minimization of margin variance could constrain some
large margins.

Due to page limit, we omit some empirical results in this section, including
more experiments on the margin distributions and the running time comparison
between our MSVMAv approach and other algorithms. These experimental results
can be found in Appendix E.

##  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 other effective statistics for margin distribution, along with
efficient calculation.

##  7 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.

## References

  * Aiolli et al. [2008] F. Aiolli, G. Da San Martino, and A. Sperduti.  A kernel method for the optimization of the margin distribution.  In ICANN, pages 305–314, 2008.
  * Bartlett and Mendelson [2002] P. Bartlett and S. Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  JMLR, 3:463–482, 2002.
  * Bartlett and Shawe-Taylor [1999] P. Bartlett and J. Shawe-Taylor.  Generalization performance of support vector machines and other pattern classifiers.  Advances in Kernel Methods: Support Vector Learning, pages 43–54, 1999.
  * Bartlett et al. [2017] P. Bartlett, D. J. Foster, and M. Telgarsky.  Spectrally-normalized margin bounds for neural networks.  In NIPS 30, pages 6240–6249. 2017.
  * Boser et al. [1992] B. E. Boser, I. M. Guyon, and V. Vapnik.  A training algorithm for optimal margin classifiers.  In COLT, pages 144–152, 1992.
  * Breiman [1999] L. Breiman.  Prediction games and arcing algorithms.  Neural Comput., 11(7):1493–1517, 1999.
  * Cheng et al. [2016] F.-Y. Cheng, J. Zhang, and C.-H. Wen.  Cost-sensitive large margin distribution machine for classification of imbalanced data.  Pattern Recognit. Lett., 80:107–112, 2016.
  * Cortes and Vapnik [1995] C. Cortes and V. Vapnik.  Support-vector networks.  Mach. Learn., 20(3):273–297, 1995.
  * Drucker et al. [1997] H. Drucker, J. C. Burges, L. Kaufman, A. Smola, and V. Vapnik.  Support vector regression machines.  In NIPS 9, pages 155–161. 1997.
  * Fan et al. [2008] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin.  LIBLINEAR: A library for large linear classification.  JMLR, 9:1871–1874, 2008.
  * Freund and Schapire [1996] Y. Freund and R. E. Schapire.  Experiments with a new boosting algorithm.  In ICML, pages 148–156, 1996.
  * Gao and Zhou [2013] W. Gao and Z.-H. Zhou.  On the doubt about margin explanation of boosting.  Artif. Intell., 203:1–18, 2013.
  * Garg and Roth [2003] A. Garg and D. Roth.  Margin distribution and learning.  In ICML, pages 210–217, 2003.
  * Grønlund et al. [2020] A. Grønlund, L. Kamma, and K. G. Larsen.  Near-tight margin-based generalization bounds for support vector machines.  In ICML, pages 3779–3788, 2020.
  * Ji et al. [2021] Z.-W. Ji, N. Srebro, and M. Telgarsky.  Fast margin maximization via dual acceleration.  In ICML, pages 4860–4869, 2021.
  * Jiang et al. [2019] Y. Jiang, D. Krishnan, H. Mobahi, and S. Bengio.  Predicting the generalization gap in deep networks with margin distributions.  In ICLR, 2019.
  * Kabán and Durrant [2020] Ata Kabán and Robert J Durrant.  Structure from randomness in halfspace learning with the zero-one loss.  JAIR, 69:733–764, 2020.
  * Markowitz [1952] Harry Markowitz.  Portfolio selection.  Journal of Finance, 7(1):77–91, 1952.
  * Pelckmans et al. [2007] K. Pelckmans, J. A. K. Suykens, and B. De Moor.  A risk minimization principle for a class of parzen estimators.  In NIPS 20, pages 1137–1144. 2007.
  * Rastogi et al. [2020] R. Rastogi, P. Anand, and S. Chandra.  Large-margin distribution machine-based regression.  Neural Comput. Appl., 32(8):3633–3648, 2020.
  * Rosset et al. [2003] S. Rosset, J. Zhu, and T. Hastie.  Margin maximizing loss functions.  In NIPS 16, pages 1237–1244. 2003.
  * Schapire et al. [1998] R. E. Schapire, Y. Freund, P. Bartlett, and W. S. Lee.  Boosting the margin: A new explanation for the effectiveness of voting methods.  Ann. Stat., 26(5):1651–1686, 1998.
  * Schölkopf et al. [2002] B. Schölkopf, A. J. Smola, and F. Bach.  Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond.  MIT Press, Cambridge, 2002.
  * Shalev-Shwartz and Ben-David [2014] S. Shalev-Shwartz and S. Ben-David.  Understanding Machine Learning: From Theory to Algorithms.  Cambridge University Press, Cambridge, 2014.
  * Sherman and Morrison [1950] J. Sherman and W. J. Morrison.  Adjustment of an inverse matrix corresponding to a change in one element of a given matrix.  Ann. Math. stat., 21(1):124–127, 1950.
  * Shivaswamy and Jebara [2010] P. K. Shivaswamy and T. Jebara.  Maximum relative margin and data-dependent regularization.  JMLR, 11(2), 2010.
  * Sokolić et al. [2017] J. Sokolić, R. Giryes, G. Sapiro, and M. R. Rodrigues.  Robust large margin deep neural networks.  IEEE Trans. Signal Process., 65(16):4265–4280, 2017.
  * Suykens et al. [2002] J. A. K. Suykens, T. Van Gestel, J. De Brabanter, B. De Moor, and J. Vandewalle.  Least Squares Support Vector Machines.  World Scientific, Singapore, 2002.
  * Vapnik [1982] V. Vapnik.  Estimation of Dependences based on Empirical Data.  Springer-Verlag, New York, 1982.
  * Wei and Ma [2020] C. Wei and T.-Y. Ma.  Improved sample complexities for deep neural networks and robust classification via an all-layer margin.  In ICLR, 2020.
  * Weinstein et al. [2020] B. Weinstein, S. Fine, and Y. Hel-Or.  Margin-based regularization and selective sampling in deep neural networks.  CoRR, abs/2009.06011, 2020.
  * Zhang and Zhou [2014] T. Zhang and Z.-H. Zhou.  Large margin distribution machine.  In KDD, pages 313–322, 2014.
  * Zhang and Zhou [2019] T. Zhang and Z.-H. Zhou.  Optimal margin distribution machine.  IEEE Trans. Knowl. Data Eng., 32(6):1143–1156, 2019.

Supplementary Material (Appendix)

##  Appendix A Proof of Theorem 1

We first begin with some useful lemmas.

######  Lemma 1.

(McDiarmid’s inequality Bartlett and Mendelson [2002]) Let
$X_{1},X_{2},\cdots,X_{n}$ be independent random variables taking values in a
set A, and assume that $f\colon A^{n}\to\mathbb{R}$ satisfies

$\sup_{x_{1},x_{2},\cdots,x_{n},x^{\prime}_{i}\in
A}\Big{|}f(x_{1},x_{2},\cdots,x_{n})-f(x_{1},x_{2},\cdots,x_{i-1},x^{\prime}_{i},x_{i+1},\cdots,x_{n})\Big{|}\leq
c_{i}$

for every $i\in[n]$. Then, for every $t>0$,

$\Pr\Big{[}f(X_{1},X_{2},\cdots,X_{n})-E\big{[}f(X_{1},X_{2},\cdots,X_{n})\big{]}\geq
t\Big{]}\leq e^{-2t^{2}/\sum_{i=1}^{n}c_{i}^{2}}\ ,$

where $e=2.718\cdots$ denotes the Euler’s number.

By applying McDiarmid’s inequality, we propose Lemma 2 to prove the uniform
convergence of our squared margin loss.

######  Lemma 2.

Let $\mathcal{H}=\\{h\colon\mathcal{X}\to[-1,+1]\\}$ be a real-valued function
space, and $\ell_{\theta}$ denote the squared margin loss for some constant
$\theta$. Then, for every $h\in\mathcal{H}$ and $S_{n}\sim\mathcal{D}$, the
following holds :

$\Pr_{S_{n}}\left[\sup_{h\in\mathcal{H}}\Big{\\{}\mathcal{E}(h)-E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta}((\bm{x},y);h)\big{]}\Big{\\}}\geq\left(\frac{4}{\theta}+\frac{4}{\theta^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H})+3\epsilon\right]\leq
2\exp\left(\frac{-2\epsilon^{2}\theta^{4}n}{(1+\theta)^{4}}\right)\ .$

###### Proof.

For simplicity, we define $\phi_{\theta}(t)=(1-t/\theta)_{+}^{2}(-1\leq t\leq
1)$ and we write $\widetilde{\mathcal{H}}=\\{(\bm{x},y)\to yh(\bm{x})\colon
h\in\mathcal{H}\\}$. Then, we have
$\ell_{\theta}((\bm{x},y);h)=\phi_{\theta}(yh(\bm{x}))$, and the function
space of the composition of $\ell_{\theta}$ and $\mathcal{H}$ can be given by

$\mathcal{F}_{\theta}=\Big{\\{}\phi_{\theta}\circ\tilde{h}\colon\tilde{h}\in\widetilde{\mathcal{H}}\Big{\\}}=\Big{\\{}\ell_{\theta}((\bm{x},y);h)\colon
h\in\mathcal{H}\Big{\\}}\ .$

For simplicity, we define

$\Phi_{\theta}(S_{n})=\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}E_{(x,y)\sim\mathcal{D}}\big{[}f(\bm{x},y)\big{]}-E_{(x,y)\sim
S_{n}}\big{[}f(\bm{x},y)\big{]}\Big{\\}}\ ,$

and thus, we have

$\Phi_{\theta}(S_{n})-\Phi_{\theta}(S^{\prime}_{n})\leq\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}E_{(x,y)\sim
S^{\prime}_{n}}\big{[}f(\bm{x},y)\big{]}-E_{(x,y)\sim
S_{n}}\big{[}f(\bm{x},y)\big{]}\Big{\\}}=\frac{1}{n}\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}f(\bm{x}_{j},y_{j})-f(\bm{x}^{\prime}_{j},y^{\prime}_{j})\Big{\\}}\
,$

where $S^{\prime}_{n}$ denotes the training sample different from $S_{n}$ by
only one instance with index $j$: $(\bm{x}_{j},y_{j})$ in $S_{n}$ and
$(\bm{x}^{\prime}_{j},y^{\prime}_{j})$ in $S^{\prime}_{n}$.

Since $h\in\mathcal{H}$ maps any instance $(\bm{x},y)$ into the interval
$[-1,1]$, and $y_{i}\in\\{-1,1\\}$, we could obtain
$\tilde{h}(\bm{x}_{i},y_{i})\in[-1,1]$ for any
$x_{1},x_{2},\cdots,x_{n},x^{\prime}_{j}$, and any
$\tilde{h}\in\widetilde{\mathcal{H}}$, which yields

$\Phi_{\theta}(S_{n})-\Phi_{\theta}(S^{\prime}_{n})\leq\frac{1}{n}\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}f(\bm{x}_{j},y_{j})-f(\bm{x}^{\prime}_{j},y^{\prime}_{j})\Big{\\}}=\frac{1}{n}\sup_{\tilde{h}\in\widetilde{\mathcal{H}}}\Big{\\{}\phi_{\theta}(\tilde{h}(\bm{x}_{j},y_{j}))-\phi_{\theta}(\tilde{h}(\bm{x}^{\prime}_{j},y^{\prime}_{j}))\Big{\\}}\leq\frac{1}{n}\left(1+\frac{1}{\theta}\right)^{2}\
.$

Similarly, we can obtain
$\Phi_{\theta}(S^{\prime}_{n})-\Phi_{\theta}(S_{n})\leq\frac{1}{n}\left(1+\frac{1}{\theta}\right)^{2}$,
thus
$|\Phi_{\theta}(S_{n})-\Phi_{\theta}(S^{\prime}_{n})|\leq\frac{1}{n}\left(1+\frac{1}{\theta}\right)^{2}$.

By applying the McDiarmid inequality, we could get

$\Pr_{S_{n}}\Big{[}\Phi_{\theta}(S_{n})-E_{S_{n}}\big{[}\Phi_{\theta}(S_{n})\big{]}\geq\epsilon\Big{]}\leq\exp\left(\frac{-2\epsilon^{2}\theta^{4}n}{(1+\theta)^{4}}\right)\
.$ (11)

We next bound the term $E_{S_{n}}\big{[}\Phi_{\theta}(S_{n})\big{]}$ as
follows:

$\displaystyle E_{S_{n}}\big{[}\Phi_{\theta}(S_{n})\big{]}$ $\displaystyle=$
$\displaystyle
E_{S_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}E_{(x,y)\sim\mathcal{D}}\big{[}f(\bm{x},y)\big{]}-E_{(x,y)\sim
S_{n}}\big{[}f(\bm{x},y)\big{]}\Big{\\}}\right]$ $\displaystyle=$
$\displaystyle
E_{S_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}E_{S^{\prime}_{n}\sim\mathcal{D}}\big{[}E_{(\bm{x},y)\sim
S^{\prime}_{n}}[f(\bm{x},y)\big{]}-E_{(x,y)\sim
S_{n}}\big{[}f(\bm{x},y)]\big{]}\Big{\\}}\right]$ $\displaystyle\leq$
$\displaystyle
E_{S_{n},S^{\prime}_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}E_{(\bm{x},y)\sim
S^{\prime}_{n}}[f(\bm{x},y)\big{]}-E_{(x,y)\sim
S_{n}}\big{[}f(\bm{x},y)]\Big{\\}}\right]$ $\displaystyle=$ $\displaystyle
E_{S_{n},S^{\prime}_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\frac{1}{n}\sum_{i=1}^{n}\left(f(\bm{x}^{\prime}_{i},y^{\prime}_{i})-f(\bm{x}_{i},y_{i})\right)\right]$
$\displaystyle=$ $\displaystyle
E_{S_{n},S^{\prime}_{n},\sigma_{1},\sigma_{2},\cdots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\left(f(\bm{x}^{\prime}_{i},y^{\prime}_{i})-f(\bm{x}_{i},y_{i})\right)\right]$
$\displaystyle\leq$ $\displaystyle
E_{S^{\prime}_{n},\sigma_{1},\sigma_{2},\cdots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(\bm{x}^{\prime}_{i},y^{\prime}_{i})\right]+E_{S_{n},\sigma_{1},\sigma_{2},\cdots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\frac{1}{n}\sum_{i=1}^{n}-\sigma_{i}f(\bm{x}_{i},y_{i})\right]$
$\displaystyle=$ $\displaystyle
2E_{S_{n},\sigma_{1},\sigma_{2},\cdots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(\bm{x}_{i},y_{i})\right]=2\mathfrak{R}_{n}(\mathcal{F}_{\theta})\
,$

where $\mathfrak{R}_{n}(\mathcal{F}_{\theta})$ is the Rademacher complexity of
function class $\mathcal{F}_{\theta}$ defined as
$\mathfrak{R}_{n}(\mathcal{F}_{\theta})=E_{S_{n}}\Big{[}\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{F}_{\theta})\Big{]}$.
Thus, we could obtain the following inequality from Eqn. (11):

$\Pr_{S_{n}}\Big{[}\Phi_{\theta}(S_{n})\geq
2\mathfrak{R}_{n}(\mathcal{F}_{\theta})+\epsilon\Big{]}\leq\exp\left(\frac{-2\epsilon^{2}\theta^{4}n}{(1+\theta)^{4}}\right)\
.$ (12)

Recall the definition

$\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{\mathcal{F}_{\theta}})=E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(\bm{x}_{i})\right]\
,$

and we have the following inequality:

$\displaystyle\left|\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{\mathcal{F}_{\theta}})-\widehat{\mathfrak{R}}_{S^{\prime}_{n}}(\mathcal{\mathcal{F}_{\theta}})\right|$
$\displaystyle=$
$\displaystyle\left|E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\left[\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(\bm{x}_{i})\right]-\sup_{f\in\mathcal{F}_{\theta}}\left[\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(\bm{x}_{i})-\frac{1}{n}\sigma_{j}f(\bm{x}_{j})+\frac{1}{n}\sigma_{j}f(\bm{x}^{\prime}_{j})\right]\right]\right|$
$\displaystyle\leq$
$\displaystyle\left|E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\left[\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(\bm{x}_{i})-\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(\bm{x}_{i})+\frac{1}{n}\sigma_{j}f(\bm{x}_{j})-\frac{1}{n}\sigma_{j}f(\bm{x}^{\prime}_{j})\right]\right]\right|$
$\displaystyle=$
$\displaystyle\left|E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{f\in\mathcal{F}_{\theta}}\left[\frac{1}{n}\sigma_{j}f(\bm{x}_{j})-\frac{1}{n}\sigma_{j}f(\bm{x}^{\prime}_{j})\right]\right]\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}\left(1+\frac{1}{\theta}\right)^{2}\ .$

By applying the McDiarmid inequality again, we could obtain

$\Pr_{S_{n}}\Big{[}\mathfrak{R}_{n}(\mathcal{\mathcal{F}_{\theta}})\geq\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{\mathcal{F}_{\theta}})+\epsilon\Big{]}\leq\exp\left(\frac{-2\epsilon^{2}\theta^{4}n}{(1+\theta)^{4}}\right)\
.$ (13)

We use the union bound to combine inequalities Eqn. (12) and Eqn. (13), which
yields the following inequality:

$\Pr_{S_{n}}\Big{[}\Phi_{\theta}(S_{n})\geq
2\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{\mathcal{F}_{\theta}})+3\epsilon\Big{]}\leq
2\exp\left(\frac{-2\epsilon^{2}\theta^{4}n}{(1+\theta)^{4}}\right)\ .$

Note that the $\phi_{\theta}(t)=(1-t/\theta)_{+}^{2}$ is
$(\frac{2}{\theta}+\frac{2}{\theta^{2}})$-Lipschitz, i.e.,
$|\phi_{\theta}(t_{1})-\phi_{\theta}(t_{2})|\leq(\frac{2}{\theta}+\frac{2}{\theta^{2}})|t_{1}-t_{2}|$
for any $t_{1},t_{2}\in[-1,1]$, and we could further bound the empirical
Rademacher complexity of $\mathcal{F}_{\theta}$ as follows:

$\displaystyle\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{\mathcal{F}_{\theta}})$
$\displaystyle\leq$
$\displaystyle\left(\frac{2}{\theta}+\frac{2}{\theta^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\widetilde{\mathcal{H}})$
$\displaystyle=$
$\displaystyle\left(\frac{2}{\theta}+\frac{2}{\theta^{2}}\right)E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{\tilde{h}\in\widetilde{\mathcal{H}}}\left[\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\tilde{h}(\bm{x}_{i})\right]\right]$
$\displaystyle=$
$\displaystyle\left(\frac{2}{\theta}+\frac{2}{\theta^{2}}\right)E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{h\in\mathcal{H}}\left[\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}y_{i}h(\bm{x}_{i})\right]\right]$
$\displaystyle=$
$\displaystyle\left(\frac{2}{\theta}+\frac{2}{\theta^{2}}\right)E_{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}}\left[\sup_{h\in\mathcal{H}}\left[\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}h(\bm{x}_{i})\right]\right]$
$\displaystyle=$
$\displaystyle\left(\frac{2}{\theta}+\frac{2}{\theta^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H})$

which could yield the following inequality:

$\Pr_{S_{n}}\left[\Phi_{\theta}(S_{n})\geq\left(\frac{4}{\theta}+\frac{4}{\theta^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H})+3\epsilon\right]\leq
2\exp\left(\frac{-2\epsilon^{2}\theta^{4}n}{(1+\theta)^{4}}\right)\ .$ (14)

From the definition of $\Phi_{\theta}(S_{n})$, we could obtain

$\displaystyle\Phi_{\theta}(S_{n})$ $\displaystyle=$
$\displaystyle\sup_{f\in\mathcal{F}_{\theta}}\Big{\\{}E_{(\bm{x},y)\sim\mathcal{D}}\big{[}f(\bm{x},y)\big{]}-E_{(\bm{x},y)\sim
S_{n}}\big{[}f(\bm{x},y)\big{]}\Big{\\}}$ $\displaystyle=$
$\displaystyle\sup_{h\in\mathcal{H}}\Big{\\{}E_{(\bm{x},y)\sim\mathcal{D}}\big{[}\ell_{\theta}((\bm{x},y);h)\big{]}-E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta}((\bm{x},y);h)\big{]}\Big{\\}}$ $\displaystyle\geq$
$\displaystyle\sup_{h\in\mathcal{H}}\Big{\\{}E_{(\bm{x},y)\sim\mathcal{D}}\big{[}\mathbb{I}[yh(\bm{x})\leq
0\big{]}-E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta}((\bm{x},y);h)\big{]}\Big{\\}}$ $\displaystyle=$
$\displaystyle\sup_{h\in\mathcal{H}}\Big{\\{}\mathcal{E}(h)-E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta}((\bm{x},y);h)\big{]}\Big{\\}}\ .$

Hence, we could finally get the conclusion of Lemma 2 as follows:

$\Pr_{S_{n}}\left[\sup_{h\in\mathcal{H}}\Big{\\{}\mathcal{E}(h)-E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta}((\bm{x},y);h)\big{]}\Big{\\}}\geq\left(\frac{4}{\theta}+\frac{4}{\theta^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H})+3\epsilon\right]\leq
2\exp\left(\frac{-2\epsilon^{2}\theta^{4}n}{(1+\theta)^{4}}\right)\ .$

∎

Now, we start our proof for Theorem 1.

###### Proof.

We construct a finite sequence $a_{0},a_{1},\cdots,a_{K}$ such that
$(1-\nu)/K\in(1/2n,1/n)$ and

$a_{i}=\nu+\frac{(1-\nu)i}{K},\quad\text{for}\quad i=0,1,2,\cdots,K\ .$

From Lemma 2, we could obtain

$\Pr_{S_{n}}\left[\sup_{h\in\mathcal{H}_{\nu}}\Big{\\{}\mathcal{E}(h)-E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{a_{i}}((\bm{x},y);h)\big{]}\Big{\\}}\geq\left(\frac{4}{a_{i}}+\frac{4}{a_{i}^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})+3\epsilon\right]\leq
2\exp\left(\frac{-2\epsilon^{2}a_{i}^{4}n}{(1+a_{i})^{4}}\right)\leq
2\exp\left(\frac{-2\epsilon^{2}\nu^{4}n}{(1+\nu)^{4}}\right)$

for all $i=0,1,2,\cdots,K$. It is noteworthy that the function class
investigated here is $\mathcal{H}_{\nu}$, which consists of relatively-good
classifiers. By applying the union bound, the following inequality holds:

$\Pr_{S_{n}}\left[\mathop{\sup_{h\in\mathcal{H}_{\nu}}}_{0\leq i\leq
K-1}\Big{\\{}\mathcal{E}(h)-E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{a_{i}}((\bm{x},y);h)\big{]}\Big{\\}}\geq\left(\frac{4}{a_{i}}+\frac{4}{a_{i}^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})+3\epsilon\right]\leq
2K\exp\left(\frac{-2\epsilon^{2}\nu^{4}n}{(1+\nu)^{4}}\right)\ .$

For any $\theta_{h}\in[\nu,1)$, there exists an $a_{i^{*}}$ such that

$a_{i^{*}-1}\leq\theta_{h}<a_{i^{*}}\ .$

By setting
$\delta=2K\exp\left(\frac{-2\epsilon^{2}\nu^{4}n}{(1+\nu)^{4}}\right)$, we
have $\epsilon=\sqrt{(1+\nu)^{4}\ln(2K/\delta)/(2\nu^{4}n)}$, and the
following holds for every $h\in\mathcal{H}_{\nu}$ with probability at least
$1-\delta$:

$\mathcal{E}(h)\leq E_{(\bm{x},y)\sim
S_{n}}\Big{[}\ell_{a_{i^{*}}}\big{(}(\bm{x},y);h\big{)}\Big{]}+\left(\frac{4}{a_{i^{*}}}+\frac{4}{a_{i^{*}}^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})+\frac{3(1+\nu)^{2}}{\nu^{2}}\sqrt{\frac{\ln\frac{2K}{\delta}}{2n}}\
.$ (15)

To further upper bound the term $E_{(\bm{x},y)\sim
S_{n}}[\ell_{a_{i^{*}}}((\bm{x},y);h)]$, we need to consider each sample
$(\bm{x}_{i},y_{i})\in S_{n}$. If $y_{i}h(\bm{x}_{i})\geq a_{i^{*}}$, we have

$\ell_{a_{i^{*}}}\big{(}(\bm{x}_{i},y_{i});h\big{)}=0=\left(1-\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}\right)_{+}^{2}=\ell_{\theta_{h}}\big{(}(\bm{x}_{i},y_{i});h\big{)}\
.$

If $\theta_{h}\leq y_{i}h(\bm{x}_{i})<a_{i^{*}}$,
$\ell_{\theta_{h}}((\bm{x}_{i},y);h)=0$, and we have

$\ell_{a_{i^{*}}}\big{(}(\bm{x}_{i},y_{i});h\big{)}=\left(1-\frac{y_{i}h(\bm{x}_{i})}{a_{i^{*}}}\right)^{2}\leq\left(\frac{a_{i^{*}}-\theta_{h}}{a_{i^{*}}}\right)^{2}\leq\ell_{\theta_{h}}\big{(}(\bm{x}_{i},y_{i});h\big{)}+\frac{(1-\nu)^{2}}{K^{2}\nu^{2}}\
.$

If $y_{i}h(\bm{x}_{i})<\theta_{h}$, we could obtain

$\displaystyle\ell_{a_{i^{*}}}\big{(}(\bm{x}_{i},y_{i});h\big{)}$
$\displaystyle=$
$\displaystyle\left(1-\frac{y_{i}h(\bm{x}_{i})}{a_{i^{*}}}\right)^{2}$
$\displaystyle=$
$\displaystyle\left(1-\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}+\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}-\frac{y_{i}h(\bm{x}_{i})}{a_{i^{*}}}\right)^{2}$
$\displaystyle=$
$\displaystyle\left(1-\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}\right)^{2}+2\left(1-\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}\right)\left(\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}-\frac{y_{i}h(\bm{x}_{i})}{a_{i^{*}}}\right)+\left(\frac{y_{i}h(\bm{x}_{i})}{\theta_{h}}-\frac{y_{i}h(\bm{x}_{i})}{a_{i^{*}}}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\ell_{\theta_{h}}\big{(}(\bm{x}_{i},y_{i});h\big{)}+2\left(1+\frac{1}{\nu}\right)\frac{1-\nu}{K\nu^{2}}+\frac{(1-\nu)^{2}}{K^{2}\nu^{2}}\
.$

In summary, we have

$E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{a_{i^{*}}}((\bm{x},y);h)\big{]}=\frac{1}{n}\sum_{i=1}^{n}\ell_{a_{i^{*}}}((\bm{x}_{i},y_{i});h)\leq
E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta_{h}}((\bm{x},y);h)\big{]}+2\left(1+\frac{1}{\nu}\right)\frac{1-\nu}{K\nu^{2}}+\frac{(1-\nu)^{2}}{K^{2}\nu^{2}}\
.$

By combining with eqn. (15), we could obtain that, the following holds for
every $h\in\mathcal{H}_{\nu}$ with probability at least $1-\delta$:

$\displaystyle\mathcal{E}(h)$ $\displaystyle\leq$ $\displaystyle
E_{(\bm{x},y)\sim
S_{n}}\Big{[}\ell_{a_{i^{*}}}\big{(}(\bm{x},y);h\big{)}\Big{]}+\left(\frac{4}{a_{i^{*}}}+\frac{4}{a_{i^{*}}^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})+\frac{3(1+\nu)^{2}}{\nu^{2}}\sqrt{\frac{\ln\frac{2K}{\delta}}{2n}}$
$\displaystyle\leq$ $\displaystyle E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta_{h}}((\bm{x},y);h)\big{]}+2\left(1+\frac{1}{\nu}\right)\frac{1-\nu}{K\nu^{2}}+\frac{(1-\nu)^{2}}{K^{2}\nu^{2}}+\left(\frac{4}{\theta_{h}}+\frac{4}{\theta_{h}^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})+\frac{3(1+\nu)^{2}}{\nu^{2}}\sqrt{\frac{\ln\frac{2K}{\delta}}{2n}}$
$\displaystyle\leq$ $\displaystyle E_{(\bm{x},y)\sim
S_{n}}\big{[}\ell_{\theta_{h}}((\bm{x},y);h)\big{]}+\frac{2+2\nu}{m\nu^{3}}+\frac{1}{m^{2}\nu^{2}}+\left(\frac{4}{\theta_{h}}+\frac{4}{\theta_{h}^{2}}\right)\widehat{\mathfrak{R}}_{S_{n}}(\mathcal{H}_{\nu})+\frac{3(1+\nu)^{2}}{\nu^{2}}\sqrt{\frac{1}{2n}\ln\frac{4n}{\delta}}$
$\displaystyle=$
$\displaystyle\frac{\text{SV}(h)}{\theta_{h}^{2}}+O\left(\frac{\widehat{\mathfrak{R}}_{n}(\mathcal{H}_{\nu})}{\theta_{h}^{2}}+\sqrt{\frac{1}{2n}\ln\frac{4n}{\delta}}\right)\
,$

which completes the proof. ∎

##  Appendix B Initialization of MSVMAv

This section introduces the detailed proof for the closed-form solution in
Eqn. (3) as follows:

###### Proof.

The primal optimization problem for empirical average margin maximization is
as follows:

$\bm{w}_{0}=\mathop{\arg\max}_{\|\bm{w}\|^{2}_{2}=1}\sum_{i=1}^{n}\frac{y_{i}\langle\bm{w},\bm{x}_{i}\rangle}{n}=\mathop{\arg\min}_{\|\bm{w}\|^{2}_{2}=1}-\sum_{i=1}^{n}\frac{y_{i}\langle\bm{w},\bm{x}_{i}\rangle}{n}\
.$

It is necessary to introduce a Lagrange multiplier $\lambda\geq 0$ for the
constraint $\left\|w\right\|_{2}^{2}=1$, and we could get the Lagrangian
function

$L(\bm{w},\lambda)=-\frac{1}{n}\sum_{i=1}^{n}y_{i}\langle\bm{w},\bm{x}_{i}\rangle+\lambda\left(\left\|\bm{w}\right\|_{2}^{2}-1\right)\
,$

and its partial derivative is given by

$\frac{\partial
L(\bm{w},\lambda)}{\partial\bm{w}}=-\frac{1}{n}\sum_{i=1}^{n}y_{i}\bm{x}_{i}+2\lambda\bm{w}\
.$

By setting the partial derivative of $\bm{w}$ to zero, we could obtain

$\bm{w}=\frac{1}{2\lambda n}\sum_{i=1}^{n}y_{i}\bm{x}_{i}\ ,$

which yields the dual problem as follows:

$\max_{\lambda}-\frac{1}{n}\sum_{j=1}^{n}y_{j}\left\langle\frac{1}{2\lambda
n}\sum_{i=1}^{n}y_{i}\bm{x}_{i},\bm{x}_{j}\right\rangle+\lambda\left(\left\|\frac{1}{2\lambda
n}\sum_{i=1}^{n}y_{i}\bm{x}_{i}\right\|_{2}^{2}-1\right)=-\frac{1}{4\lambda
n^{2}}\left\|\sum_{i=1}^{n}y_{i}\bm{x}_{i}\right\|_{2}^{2}-\lambda\ .$

It is obvious that the optimal value of $\lambda$ equals to

$\lambda^{*}=\frac{1}{2n}\left\|\sum_{i=1}^{n}y_{i}\bm{x}_{i}\right\|_{2}\ .$

Hence, the empirical average margin maximizer, i.e., the initial value, is as
follows:

$\bm{w}_{0}=\sum_{i=1}^{n}\frac{y_{i}\bm{x}_{i}}{\left\|\sum_{i=1}^{n}y_{i}\bm{x}_{i}\right\|_{2}}\
,$

which completes the proof. ∎

##  Appendix C Detailed information of Datasets

Table 3: Characteristic of 30 datasets. Scale | Dataset | #Instance | #Feature | Dataset | #Instance | #Feature
---|---|---|---|---|---|---
Regular | advertise | 3279 | 1558 | kc1 | 2109 | 21
| australian | 690 | 14 | parkinsons | 208 | 60
| bibtex | 7395 | 1836 | pbcseq | 1113 | 21
| biodeg | 1055 | 41 | sleepdata | 1024 | 2
| breastw | 683 | 9 | students | 1000 | 18
| diabetes | 768 | 8 | titanic | 2201 | 3
| emotions | 593 | 72 | tokyo1 | 959 | 44
| german | 1000 | 24 | vehicle | 846 | 18
| halloffame | 1320 | 22 | vertebra | 310 | 6
| hill-valley | 1212 | 100 | wdbc | 569 | 30
Large | a9a | 32561 | 123 | magic | 19020 | 10
| acoustic | 78823 | 50 | nomao | 34465 | 118
| bank | 45211 | 51 | phishing | 11055 | 68
| eurgbp | 43825 | 10 | pol | 15000 | 44
| jm1 | 10880 | 21 | run-walk | 88588 | 6

This section introduces further experimental settings. We select 30 open-
source datasets, including 20 regular scale and 10 large scale datasets, to
verify the effectiveness of our proposed MSVMAv approach. All datasets can be
found on the UCI datasets website or the OpenML website. Table 3 shows the
detailed information of each dataset.

Figure 2: Cumulative frequency versus margin of our MSVMAv and other
algorithms such as SVM, ODM and FMM. The more right the curve, the better the
margin distribution.

##  Appendix D Introductions to Other Algorithms

This section introduces detailed information about six state-of-the-art
algorithms that we compare our MSVMAv approach with and the implementation of
these algorithms. SVM (Support Vector Machine) is one of the most famous
linear classification algorithms. Traditional hard-margin SVM maximizes the
minimum margin. The classifier can be obtained via the following optimization
problem:

$\displaystyle\min_{\bm{w}}$ $\displaystyle\frac{1}{2}\|\bm{w}\|_{2}^{2}$
$\displaystyle s.t.$ $\displaystyle
y_{i}\langle\bm{w},\bm{\phi}(\bm{x}_{i})\rangle\geq 1,\forall i\in[n].$

For non-separable data, the training data cannot be separated without error.
Hence, the soft-margin SVM is proposed, which requires the solution of the
following optimization problem:

$\displaystyle\min_{\bm{w},b,\bm{\xi}}$
$\displaystyle\frac{1}{2}\|\bm{w}\|_{2}^{2}+C\sum_{i=1}^{m}\xi_{i}$
$\displaystyle s.t.$ $\displaystyle
y_{i}(\langle\bm{w},\bm{\phi}(\bm{x}_{i})\rangle+b)\geq 1-\xi_{i},$
$\displaystyle\xi_{i}\geq 0,$

where $C>0$ is the penalty parameter for the error term, i.e., the hinge loss.
On one hand, soft-margin SVM maximizes the minimum margin, while on the other
hand, it tries to minimize the hinge loss. The optimization problems for SVR
(Support Vector Regression) and LSSVM (Least-square Support Vector Machine)
are similar to SVM’s, while the only difference lies in the error term. SVR
adopts the $\epsilon$-insensitive loss function while LSSVM uses the squared
loss.

MAMC (Maximal Average Margin for Classifiers) and ODM (Optimal Margin
Distribution Machine) considers to optimize the margin distribution directly.
MAMC Pelckmans et al. [2007] maximizes the average margin. The algorithm is
very time-efficient because the optimization problem has closed-form solution.
However, the experimental results indicate that the overall performance is the
worst in most situations since MAMC considers the average margin only. ODM
Zhang and Zhou [2019] considers to optimize the empirical average margin and
the empirical margin variance simultaneously. However, ODM introduces three
hyper-parameters, which makes it difficulty to tune these parameters.

Recently, Ji et al. Ji et al. [2021] has proposed a new method to directly
maximize the minimum margin, i.e.,
$\min_{i}y_{i}\langle\bm{w},\bm{x}_{i}\rangle/\|\bm{w}\|_{2}^{2}$, via
momentum-based gradient method. We call this method as FMM (Fast Margin
Maximization) in this paper for short.

For linear SVM and SVR, we use the LIBLINEAR implementation, while for kernel
SVM and SVR, we use the LIBSVM implementation insteadFan et al. [2008]. We use
the LS-SVMlib111https://www.esat.kuleuven.be/sista/lssvmlab/ to implement
LSSVMSuykens et al. [2002]. We use the source code from authors’
website222http://www.lamda.nju.edu.cn/code_ODM.ashx to implement ODMZhang and
Zhou [2014]. We implement MAMCPelckmans et al. [2007] and FMMJi et al. [2021]
exactly according to their own respective work.

Apart from $\alpha_{k}$, $\beta_{k}$ for our MSVMAv approach, $C$ for SVM,
SVR, LSSVM, ODM and the width of Gaussian kernel, the parameter $\mu$ and
$\theta$ for ODM are selected from $\\{0.2,0.4,0.6,0.8\\}$ Zhang and Zhou
[2019]. For FMM, $\theta$, which can be viewed as the learning rate, is
selected from the set $\\{2^{-10},2^{-8},\cdots,2^{0}\\}$ and $T$, which
controls the maximum iteration number, is selected from
$\\{50,100,200,400,800,1600\\}$.

##  Appendix E Further Empirical Results

Due to page limit, we present more experimental results and running time
comparison in this section.

Figure 3: Full training time of our MSVMAv, SVM, SVR, LSSVM, ODM and FMM.

Figure 2 illustrates the curves of the cumulative margin distributions for our
MSVMAv approach and other algorithms on four more datasets. As can be seen,
our MSVMAv approach takes the rightmost curve, indicating better margin
distribution in comparisons with other algorithms.

We compare the training time on a training set of one partition of our method
with SVM, SVR, LSSVM, ODM, and FMM. For fair comparisons, we run all
experiments on the same computer with a single CPU (Intel Core i5-9500 @
3.00GHz), 16GB memory and Windows 10 operating system. The running time (in
seconds) of these methods on each dataset is shown in Figure 3, which shows
that our MSVMAv approach has comparable time cost to other methods.