First let us review the fundamental concentration inequality that is adopted in our proof.
[52]
Let $X_1,\cdots,X_m$ be independent random variables all taking values in the set $\mathcal{X}$. Let $f: \mathcal{X} \rightarrow \mathbb{R}$ be a function of
$X_1,\cdots,X_m$ that satisfies:

\[\sup_{\boldsymbol{x},\boldsymbol{x}'}|f(x_1,\cdots,x_i,\cdots, x_m) - f(x_1, \cdots,x'_i \cdots,x_,) | \le c_i,\]

with $\boldsymbol{x} \neq \boldsymbol{x}'$.
Then for all $\epsilon >0$,

\[\mathbb{P}[ \mathbb{E}(f) - f \ge \epsilon ] \le \exp\left(\dfrac{-2\epsilon^2}{\sum_{i=1}^mc_i^2} \right). \]

§.§ Properties of Rademacher Averages

The following lemmas are instrumental for our derivation of $\mauc$ Rademacher Complexity upper bounds in Lem.<ref> and Lem.<ref>.

First the Khinchin-Kahane inequality bridges the $\ell_p$ norm average to the $\ell_q$ norm average, given that $1<p<q<\infty$.
[39]
$\forall n \in \mathbb{N}$, let $\sigma_1, \cdots, \sigma_n$ be a family of i.i.d. Rademacher variables. Then for any $1<p<q<\infty$, we have:

\begin{equation*}
\bigg(\expe_{\sigma} \left[\big|\sum_{i=1}^n\sigma_if_i\big|^q\right]\bigg)^{\nicefrac{1}{q}} \le \left(\frac{q-1}{p-1}\right)^{\nicefrac{1}{2}} \cdot \bigg(\expe_{\sigma} \left[\big|\sum_{i=1}^n\sigma_if_i\big|^p\right]\bigg)^{\nicefrac{1}{p}}.
\end{equation*}

Dealing with the Rademacher complexities for  vector-valued function, we need the vector version of the well-known Talagrand contraction lemma, see [51, 14] for a proof.

Let $\mathcal{X}$ be any set, $n \in \mathcal{N}$, $(\x_1; \cdots; \x_N) \in X_n$, let $\mathcal{F}$ be a class of k-component-functions $f = (f^{(1)},\cdots,f^{(k)}): X \rightarrow \ell_2^k$ and let $h:\ell_2^k \rightarrow \mathbb{R}$ have Lipschitz norm $\phi$. Then,

\[\expe_{\sigma}\left[\sup_{f\in\mathcal{F}} \sum_{i=1}^N \sigma_i h(f(\x_i))\right] \le \sqrt{2}\phi\expe_{\sigma}\left[\sup_{f\in\mathcal{F}} \sum_{i=1}^N\sum_{k=1}^K \sigma_{i,k} (f^{(k)}(\x_i))\right],\]

where $\sigma_1 \cdots,\sigma_N$, and $\sigma_{1,1}, \cdots, \sigma_{1,K}, \cdots, \sigma_{N,K}$ are two sequences of independent Rademacher random variables.

The following Lemma is a simple extension of Lem.1 in [27] to double indexed Rademacher random sequence, which is the key to the derivation of Lem.<ref>.
Let $s$ be a 1-Lipschitz, positive-homogeneous activation function which is applied element-wise. Then for any class of vector-valued functions $\mathcal{F}$, and any convex and monotonically increasing function $g : \mathbb{R} \rightarrow [0,\infty)$, we have:

\begin{equation*}
\expe_{\sigma} \left[\sup_{f \in \mathcal{F}, ||W||_F \le R_W}  g\left(\left\|\sum_{i=1}^N \sum_{c=1}^{N_C} \sigma_{i,c} \cdot   s(\bm{W}f(\x_i)) \right\| \right)\right] \le 2 \expe_{\sigma} \left[ \sup_{f \in \mathcal{F}} g\left(R_W \cdot \left\|\sum_{i=1}^N \sum_{c=1}^{N_C} \sigma_{i,c} \cdot f(\x_i) \right\| \right)\right]
\end{equation*}

where $\{\sigma_{i,c}\}$ is a sequence of double indexed Rademacher random variables.

§.§ Lipschitz Properties of Softmax

In this section, we provide an $\ell_2$  Lipschitz Constant for softmax component function.
Given $\mathcal{X} \in \mathbb{R}^K$, the function $\mathsf{soft}_i,~ i = 1,2,\cdots,K$ is a mapping $\x = (x_1,\cdots, x_k) \in \mathcal{X} \rightarrow [0,1]$, defined as:

\[\mathsf{soft}_i(\x)  = \dfrac{\exp(x_i)}{\sum_{j=1}^K \exp(x_j)},\]

then $\mathsf{soft}_i(\cdot)$ is $\frac{\sqrt{2}}{2}$-Lipschitz continuous with respect to vector $\ell_2$ norm.

We only  need to prove that

\[\sup_{\x \in \mathcal{X}} \big\| \nabla_{\x}\mathsf{soft}_i(\x)\big\|_2 \le \frac{\sqrt{2}}{2}. \]

For any $\x \in \mathcal{X}$, we have:

\[\frac{\partial \mathsf{soft}_i(\x)}{\partial x_j} =  \mathsf{soft}_i(\x) \cdot \left(I[i = j] -\mathsf{soft}_{j}(\x) \right), ~ i,j= 1,\cdots,K  .\]

Then we have:

\begin{equation*}
\begin{split}
\big\| \nabla_{\x}\mathsf{soft}_i(\x)\big\|_2 = \left( \mathsf{soft}^2_i(\x)\cdot \sum_{j\neq i}\mathsf{soft}^2_j(\x)+ \mathsf{soft}_i(\x)^2\cdot \left(1-\mathsf{soft}_{j}(\x)\right)^2\right)^{1/2}.
\end{split}
\end{equation*}

Since $ \mathsf{soft}^2_i(\x) \le  \mathsf{soft}_i(\x)$, $\left(1-\mathsf{soft}_{j}(\x)\right)^2 \le \left(1-\mathsf{soft}_{j}(\x)\right)$, and $\sum_{j\neq i}\mathsf{soft}^2_j(\x) \le (1 - \mathsf{soft}_i(\x))$, we have:

\begin{equation*}
\big\| \nabla_{\x}\mathsf{soft}_i(\x)\big\|_2 \le \bigg(2 \cdot \mathsf{soft}_i(\x) \cdot \left(1 - \mathsf{soft}_i(\x)\right)\bigg)^{1/2} \le\frac{\sqrt{2}}{2},
\end{equation*}

which ends the proof.

§ $\MAUC$ RADEMACHER COMPLEXITY AND ITS PROPERTIES

§.§ $\mauc$ Symmetrization

In this section, we provide the derivation for $\mauc$ Symmetrization, which is the key technology for Thm.<ref>. The main idea is that exchanging instances, but not the terms, does not change the value of
\[\ess{\left[ \supf \left(\js - \jsp\right)\right]}.\]

The following inequality holds:

\[\ess{\left[ \supf \left(\js - \jsp\right)\right] } \le  \frac{4  \sR}{N_C(N_C-1)},\]

with the labels $\bm{Y}$ fixed for $\mathcal{S}$ and $\mathcal{S}'$.

Denote $\lfxy{\bm{x}}{\xp}  = \ell(f^{(i)}(\x_m)  - f^{(i)}(\x_n'))$ and define

\begin{equation}
\begin{split}
T^{i,j,m,n} =&\frac{\sigmai_m + \sigmaj_n}{2} \lfxy{\xp}{\xp} +\frac{\sigmai_m - \sigmaj_n}{2} \lfxy{\xp}{\x} \\
&-\frac{\sigmai_m - \sigmaj_n}{2} \lfxy{\x}{\xp}  -\frac{\sigmai_m + \sigmaj_n}{2} \lfxy{\x}{\x},
\end{split}
\end{equation}

we first show that

\begin{equation}
\begin{split}
& \ess{ \left[\supf \left(\jsp - \js\right)\right] } \\
&~ = \nc \ess{\expe_{\sigma} \left[\supf \sumauc T^{i,j,m,n}\right]}.
\end{split}
\end{equation}

Given $\mathcal{S}= \left\{(\bm{x}_i,y_i)\right\}_{i=1}^m$,  $\mathcal{S}'= \left\{(\bm{x}'_i,y_i)\right\}_{i=1}^m$, where we sort the instances such that $y_i \le y_j$ for $i \le j$ for the sake of convenience, since the instances are drawn independently, we employ the fact that:

\begin{equation}
\ess{\left[ \supf \left(\jsp - \js\right) \right] }  =  \ess{\left[  \supf \left(\jspt - \jst\right) \right] }
\end{equation}

where $\ts$ and $\tsp$ are permuted datasets obtained from $\mathcal{S}$ and $\mathcal{S}'$ respectively after exchanging $ 0 \le x \le N$ samples of $(\bm{x}_i,y_i)$ and $(\bm{x}'_i,y'_i)$ sharing the same index.

Next, we show that
for any sequence of i.i.d Rademacher random variables,  $\sigma = (\sigma^{(1)}_1, \cdots,\sigma^{(1)}_{n_1},\cdots,\sigma^{(2)}_{1} ,\cdots, \sigma^{(N_C)}_{n_C})$ and any $\mathcal{S}$, and $\mathcal{S}'$, there exists a pair of permuted datasets $\tilde{S}^\sigma$ and  $\tilde{S}'^\sigma$ such that

\begin{equation}
\supf \left[\sumauc T^{i,j,m,n}\right]
= \supf \left[ \jfunp{\sigma} - \jfun{\sigma}. \right]
\end{equation}

Specifically, we show this by induction.

Base Case. We assume that $\mathcal{S} = \left\{ (\bm{x}_1,1), (\bm{x}_2,2)\right\}$ $\mathcal{S}' = \left\{(\bm{x}'_1,1), (\bm{x}'_2,2)\right\}$, $\sigma = (\sigma^{(1)}_1,\sigma^{(2)}_1)$. Here we define

\[T^1 = T^{1,2,1,1}, T^2 = T^{2,1,1,1} .\]
We have the following cases:

(a) $\sigma^{(1)}_1 =1,\sigma^{(2)}_1 = 1$. We have:

\begin{equation}
\begin{split}
& T^1 = \ell(f^{(1)},\bm{\xp}_1,\bm{\xp}_2) - \ell(f^{(1)},\bm{\x}_1,\bm{\x}_2),\\
& T^2 = \ell(f^{(2)},\bm{\xp}_2,\bm{\xp}_1) - \ell(f^{(2)},\bm{\x}_2,\bm{\x}_1),\\
\end{split}
\end{equation}

This shows that

\begin{equation}
\supf \left[T^1 +T^2\right] = \supf \left[\jsp - \js\right].
\end{equation}

This suggests that $\tilde{\mathcal{S}}_{\sigma} = \mathcal{S}$, $\tilde{\mathcal{S}'}_{\sigma} = \mathcal{S}'$.

(b) $\sigma^{(1)}_1 =1,\sigma^{(2)}_1 =-1$.
\begin{equation}
\begin{split}
& T^1 = \ell(f^{(1)},\bm{\xp}_1,\bm{\x}_2) - \ell(f^{(1)},\bm{\x}_1,\bm{\xp}_2),\\
& T^2 = \ell(f^{(2)},\bm{\x}_2,\bm{\xp}_1) - \ell(f^{(2)},\bm{\xp}_2,\bm{\x}_1),\\
\end{split}
\end{equation}

This shows that

\begin{equation}
\supf \left[T^1 +T^2\right] = \supf \left[\jfunp{\sigma} - \jfun{\sigma}\right].
\end{equation}

where $\tilde{\mathcal{S}}_{\sigma} and \tilde{\mathcal{S}'}_{\sigma}$ are obtained by exchanging $(\bm{x}_2,2)$ and  $(\bm{x}'_2,2)$

(c) $\sigma^{(1)}_1 =-1,\sigma^{(2)}_1 =1$. One can show that the corresponding $\tilde{\mathcal{S}}_{\sigma},\tilde{\mathcal{S}'}_{\sigma}$  are obtained by exchanging $(\bm{x}_1,1)$ and  $(\bm{x}'_1,1)$.

(d) $\sigma^{(1)}_1 =-1,\sigma^{(2)}_1 =-1$. One can show that the corresponding $\tilde{\mathcal{S}}_{\sigma},\tilde{\mathcal{S}'}_{\sigma}$  are obtained by completely exchanging $\mathcal{S}$ and  $\mathcal{S}'$.

The arguments above complete the proof for base case.

Recursion. Given
\[\mathcal{S}^- =\{(\bm{x}_i,y_i)\}_{i=1}^{k},\mathcal{S}^{-'} =\{(\bm{x}'_i,y_i)\}_{i=1}^{k}, \forall \sigma^- \in \{-1,1\}^k,\]

we assume that $\mathcal{S}^-,\mathcal{S}^{-'}$ and $\sigma^-$ satisfy our conclusion, which is realized by $\tilde{\mathcal{S}}^-_{\sigma^-}$ and $\tilde{\mathcal{S}}^{-'}_{\sigma^-}$. We now show that given a new pair $(\x_{n}, i)$ , $(\x'_{n}, i)$ and $\sigma^{(i)}_{n} \in \{-1,1\}$ such that

\[\mathcal{S} = \mathcal{S}^-\cup\{(\x_{n}, i)\}, \mathcal{S}' = \mathcal{S}^{-'} \cup \{(\x'_{n}, i)\}, \sigma = (\sigma^-,\sigma^{(i)}_{new}) \]

still satisfies our conclusion. Obviously only $T^{i,*,n,*}$ and $T^{*,i,*,n}$ are involved with the new sample, where $*$ simply refers to all the possible choices.

For the case that $\sigma^{(i)}_{n}=-1$, we have the following cases:
First, we examine the terms $T^{i,*,n,*}$ by taking any specific $T^{i,j,n,m}$.

(a) $\sigma^{(j)}_m = 1$, we have:

\[T^{i,j,n,m} = \ell(f^{(i)},\bm{\x}_n,\bm{\xp}_m) - \ell(f^{(i)},\bm{\xp}_n,\bm{\x}_m).\]

(b) $\sigma^{(j)}_m = -1$, we have:

\[T^{i,j,n,m} = \ell(f^{(i)},\bm{\x}_n,\bm{\x}_m) - \ell(f^{(i)},\bm{\xp}_m,\bm{\xp}_n).\]

Moreover, for any  $T^{j,i,n,m}$, we have:

(a) $\sigma^{(j)}_m = 1$, we have:

\[T^{j,i,m,n} = \ell(f^{(j)},\bm{\xp}_m,\bm{\x}_n) - \ell(f^{(j)},\bm{\x}_m,\bm{\xp}_n).\]

(b) $\sigma^{(j)}_m = -1$, we have:

\[T^{i,j,n,m} = \ell(f^{(j)},\bm{\x}_m,\bm{\x}_n) - \ell(f^{(j)},\bm{\xp}_m,\bm{\xp}_n).\]

This shows that

\[\tilde{\mathcal{S}}_{\sigma} = \tilde{\mathcal{S}}^-_{\sigma^-} \cup \{(\x'_{n}, i)\}, ~ \tilde{\mathcal{S}}'_{\sigma} = \tilde{\mathcal{S}}^{-'}_{\sigma^-} \cup \{(\x_{n}, i)\}. \]

Similarly if $\sigma^{(i)}_n = 1$, we have

\[\tilde{\mathcal{S}}_{\sigma} = \tilde{\mathcal{S}}^-_{\sigma^-} \cup \{(\x_{n}, i)\}, ~ \tilde{\mathcal{S}}'_{\sigma} = \tilde{\mathcal{S}}^{-'}_{\sigma^-} \cup \{(\x'_{n}, i)\}. \]

In either case, we know that $\tilde{\mathcal{S}}_{\sigma}$ and $\tilde{\mathcal{S}}'_{\sigma}$ are obtained by exchanging the corresponding instances of $\mathcal{S}$ and $\mathcal{S}'$.

By the arguments in the base case and the recursion, we complete the proof with:

\begin{equation}
\supf \left[\sumauc T^{i,j,m,n}\right]
= \supf \left[ \jfunp{\sigma} - \jfun{\sigma} \right].
\end{equation}

It immediately suggests that

\begin{equation}
\begin{split}
&\ess{\expe_{\sigma} \bigg[\supf \sumauc T^{i,j,m,n}\bigg] } \\
&~~ = \expe_{\sigma}  \ess{\left[ \supf  \left(\jfunp{\sigma} - \jfun{\sigma}\right) \right] }\\
&~~ = \frac{1}{2^N} \cdot  \sum_{\sigma} \ess{\left[ \supf \left(\jfunp{\sigma} - \jfun{\sigma}\right) \right]}\\
&~~ = \frac{1}{2^N} \cdot  \sum_{\sigma} \ess{\left[\supf  \left(\jsp - \js\right) \right]}\\
&~~ = \frac{2^N}{2^N} \cdot   \ess{\left[\supf  \left(\jsp - \js\right) \right]}\\
&~~ = \ess{ \left[ \supf \left(\jsp - \js\right) \right]}.
\end{split}
\end{equation}

The proof then follows that

\begin{equation}
\ess{\expe_{\sigma} \left[\supf \sumauc T^{i,j,m,n}\right] } \le 4\sR.
\end{equation}

§.§ A General Result

In this section, we will provide a proof for the general result for $\mauc$ generalization bound, which is based on Lem.<ref>, and Lem.<ref>.

Given dataset $\mathcal{S} = \{(\bm{x}_i,y_i)\}_{i=1}^m$, where the instances are sampled independently, for all multiclass scoring functions $f \in \mathcal{H}$, if $dom\ell = [0,B]$, $\forall \delta \in (0,1)$, the following inequalities hold with probability at least $1 - \delta$:

\begin{equation*}
R_\ell(f) \le \js + \frac{4\empsR}{N_C(N_C-1)}  +  \frac{10B }{N_C}  \cdot \xi(\bm{Y}) \cdot \sqrt{\frac{\log(\nicefrac{2}{\delta})}{2N}}
\end{equation*}

where $\xi(\bm{Y}) = \sqrt{\sum_{i=1}^{n_C}\nicefrac{1}{\rho_i}}.$

Given $\mathcal{S}'$ as another dataset being independent with $\mathcal{S}$, since $\js = \mathbb{E}_{\mathcal{S}'}\jsp$, using the Jensen's inequality, we have:

\begin{equation*}
\begin{split}
\es{\left[\supf \left(\es{\js} - \js \right) \right]} &= \es {\supf \expe_{\mathcal{S}'}{ \left[\js-\jsp\right]  }}  \\
&\le \ \ \ \  \ess{ \left[\supf \left(\js-\jsp \right) \right]  }
\end{split}
\end{equation*}

From Lem.<ref>, we have:

\begin{equation}\label{eq:rade}
\begin{split}
\ess{\left[ \supf \left(\js - \jsp\right)\right] } \le 4\nc\sR.
\end{split}
\end{equation}

Given $\mathcal{S}$,  define $\mathcal{S}_m = ( \mathcal{S} ~ \backslash ~ \{(\bm{x}_m, y_m)\}) \cup {\{(\bm{x}'_m, y_m)\}}$.
We now proceed to derive the bounded difference property for the loss function. Suppose that $y_m = i$, we have:

\begin{equation*}
\begin{split}
d_i &=  |\supf(\es{\js} - \js ) - \supf(\mathbb{E}_{\mathcal{S}_i}{\jsi} - \jsi )|\\
&\le \supf |\js - \jsi|\\
& = \nicefrac{1}{N_C(N_C-1)} \supf \bigg[\suminj \sumxtwo \ninj |\ell(f^{(i)},\x_m,\x_n) - \ell(f^{(i)},\x'_m,\x_n)  | \\
&~~~~+ \suminj \sum_{\x_n \in \Nj} \ninj |\ell(f^{(j)},\x_n,\x_m) - \ell(f^{(j)},\x_n,\x'_m)  |   \bigg]\\
& \le \ \ \  \ \frac{2B}{N_C\ni}
\end{split}
\end{equation*}

Thus we have $\sum_{i=1}^N d_i^2 = 4 \nicefrac{B^2}{N_C^2} \cdot \sum_{i=1}^{n_C}\nicefrac{1}{n_i} $.
According to Eq.(<ref>) and Lem.<ref>, we know that fixing the labels $\bm{Y}$, with probability at least $1 - \nicefrac{\delta}{2}$, the following inequality  holds:

\begin{equation}\label{eq:half}
\es{\js} \le \js + \frac{4}{N_C(N_C-1)} \sR +  \frac{2 B }{N_C}\xi(\bm{Y})  \cdot \sqrt{\frac{\log(\nicefrac{2}{\delta})}{2N}}
\end{equation}

Using an analogous argument, we can prove that, fixing the labels $\bm{Y}$, with probability at least $1 - \nicefrac{\delta}{2}$, the following inequality  holds:

\begin{equation}\label{eq:half2}
\frac{\sR}{N_C(N_C-1)} \le \frac{\empsR}{N_C(N_C-1)} + \frac{2 B }{N_C} \xi(\bm{Y}) \cdot \sqrt{\frac{\log(\nicefrac{2}{\delta})}{2N}}.
\end{equation}

Combining Eq.(<ref>) and Eq.(<ref>), fixing  $\bm{Y}$, we have with probability at least $1 - \delta$ that:

\begin{equation}\label{eq:gen_xy}
\es{\js} \le \js + \frac{4}{N_C(N_C-1)} \empsR +  \frac{10B }{N_C} \xi(\bm{Y}) \cdot \sqrt{\frac{\log(\nicefrac{2}{\delta})}{2N}}
\end{equation}

Following the arguments in Thm.8 in [2], we have Eq.(<ref>) holds with probability (over $\bm{X}$ and $\bm{Y}$) at least $1 - \delta$.

§.§ Sub-Gaussian Property of the $\mauc$ Rademacher Complexity

[Sub-Gaussian Stochastic Process] A stochastic process $\theta \mapsto X_\theta$ with indexing set $\mathcal{T}$ is sub-Gaussian to a pseudo-metric $d$ on $\mathcal{T}$, if for all $\theta, \theta' \in \mathcal{T}$ and all $\lambda \in \mathbb{R}$,

\begin{equation}
\expe\left[\exp\left(\lambda \cdot (X_\theta - X_{\theta'})\right)\right] \le \exp\left(\frac{\lambda^2 d(\theta, \theta')^2}{2}\right).
\end{equation}

Define $\tfs = \empcompsim$, and recall that
\[T^{i,j,m,n} = \sigmaterm,\]
with the function $f$ chosen from an index set (in this case a function class) $\mathcal{F}$. We see that ${\tfs}_{f \in \mathcal{F}}$ is essentially a stochastic process of the Rademacher random variables $\sigma$, which is revealed by the following lemma:

Given an input feature set $\mathcal{D}_{\mathcal{X}} = \{\bm{x}_1, \cdots, \bm{x}_N\}$, $\mathcal{Z}_{\mathcal{D}}$ is defined as

\[ \big\{(\bm{x}, y): \bm{x} \in \mathcal{D}_{\mathcal{X} }, y \in \{1,2,\cdots, N_C\} \big\},\]

which is the cartesian product between $\mathcal{D}_{\mathcal{X}}$ and the label space.  Moreover, $\forall \bm{z}= (\bm{x}, i) \in \mathcal{Z}_{\mathcal{D}}$, $s(\bm{z}) = s^{(i)}(\bm{x})$.
With the notations above, if $\ell$ is $\phil$-Lipschitz continuous, we have that,  $\{C_G\cdot\tfs\}_{f \in \mathcal{H}}$ with $f = (f^{(1)},\cdots, f^{N_C})$ and $f^{(i)} = \mathsf{soft}^{(i)}\circ \s$ is a sub-Gaussian stochastic process in the sense that :

\begin{equation}
\expe_{\sigma}\Bigg[\exp\bigg(\lambda \cdot C_G \cdot \big(\tfsd\big)\bigg)\Bigg] \le \exp\left(\frac{\lambda^2 d_\infty(\cone{\s}, \ctwo{\st})^2}{2}\right).
\end{equation}

\begin{equation}
C_{G} = \dfrac{1} {\phil \cdot (N_C-1) \cdot \xi(\bm{Y}) \cdot \sqrt{\frac{1}{N}}},~~~d_{\infty, \mathcal{S}}(\s, \st) = \max_{\bm{z} \in \mathcal{Z}_{\mathcal{D}}} |\s(\bm{z}) - \st({\bm{z}}
\end{equation}

Denote $\sigone$ as a set of Rademacher random variables in the following form:

\[{\sigone}=(\sigma^{(1)}_1, \cdots, \sigma^{(1)}_{n_1}, \cdots ,\sigma^{(i)}_{1}, \cdots, \cone{\sigma^{(i)}_{k}}, \cdots, \sigma^{(i)}_{n_1}, \cdots, \sigma^{(N_C)}_{n_{N_C}})\]

and denote $\sigtwo$ as another set of Rademacher random variables with all entries of which  the same as $\sigma$ except that $\color{red}\sigma^{(i)}_k$ is replaced with $\color{c2}\tilde{\sigma}^{(i)}_k$, i.e,

\[ \sigtwo=(\sigma^{(1)}_1, \cdots, \sigma^{(1)}_{n_1}, \cdots ,\sigma^{(i)}_{1}, \cdots, {\color{c2}\tilde{\sigma}^{(i)}_{k}}, \cdots, \sigma^{(i)}_{n_1}, \cdots, \sigma^{(N_C)}_{n_{N_C}}).\]
We have the following bounded difference property for every possible choice of $(i,k)$:

\begin{equation*}
\begin{split}
diff_i &=   \left| \left(\tfsd\right) - \left( \tfsdi \right) \right|\\
& =  \bigg|\left(\frac{{\color{blue}{\sigma^{(i)}_k}}-{\color{red}\tilde{\sigma}^{(i)}_k}}{2}\right) \cdot \bigg[\suminj \sumxtwo  \cdot \ninj \left(\ell(\cone{f}^{(i)},\x_m,\x_n) - \ell(\ctwo{\funt}^{(i)},\x_m,\x_n) \right) \\
&~~~~+ \suminj \sum_{\x_n \in \Nj}  \ninj \left(\ell(\cone{f}^{(j)},\x_n,\x_m) - \ell(\ctwo{\funt}^{(j)},\x_n,\x_m) \right)\bigg]\bigg|\\
& \le \ \ \  \ \frac{2\cdot (N_C-1)}{\ni} \max_{i,~\x_m \in \Ni,~ \x_n \notin \Ni} \left|\ell(\cone{f}^{(i)},\x_m,\x_n) - \ell(\ctwo{\funt}^{(i)},\x_m,\x_n)\right|\\
&\le  \ \ \  \  \frac{4\cdot (N_C-1)}{\ni} \cdot \phil \cdot \max_{i,~\x \in \mathcal{D}_{\mathcal{X}} } \left|\cone{f}^{(i)}(\x) - \ctwo{\funt}^{(i)}(\x)\right|\\
&= \ \ \  \ \frac{4\cdot (N_C-1)}{\ni} \cdot \phil \cdot \max_{i,~\x \in \mathcal{D}_{\mathcal{X}} } \left|\int_0^1 \left<\nabla\mathsf{soft}^{(i)}\left(\tau \cdot \bm{\ctwo{\st}}(\x) + (1-\tau) \cdot \cone{\s}(\x)\right), ~\left(\cone{\s}(\x) - \ctwo{\st}(\x)\right)\right> d\tau\right|\\
&\le\ \ \ \  \frac{4\cdot (N_C-1)}{\ni} \cdot \phil \cdot \left(\sup_{\x}||\nabla\mathsf{soft}^{(i)}(\x)||_1\right) \cdot  \max_{\bm{z} \in \mathcal{Z}_{\mathcal{D}} }|\cone{\s}(\bm{z}) - \ctwo{\st}(\bm{z})| \\
& \le\ \ \ \ \frac{2\cdot (N_C-1)}{\ni} \cdot \phil \cdot \max_{\bm{z} \in \mathcal{Z}_{\mathcal{D}} }  |\cone{\s}(\bm{z}) - \ctwo{\st}(\bm{z})|.
\end{split}
\end{equation*}

It is now easy to see that $C_G \cdot \big(\tfsd\big)$ satisfies the bounded difference property (Def.<ref>). According to Lem.<ref>, we could choose $v$ therein as:

\begin{equation*}
v = \frac{1}{4} \sum_{i=1}^N C_G^2 \cdot diff_i^2 = \max_{\bm{z} \in \mathcal{Z}_{\mathcal{D}} } |\bm{\cone{s}}(\bm{z}) - \ctwo{\st}(\bm{z})|^2
\end{equation*}

This suffices to complete the proof based on Lem.<ref>.

§.§ Chaining Bounds

Now with the sub-Gaussian property proved in Lem.<ref>, we can derive chaining upper bounds  for the $\mauc$ Rademacher complexity based on the notion of covering number. Before presenting the results, let us start with the definition of $\epsilon$-covering and the covering number.
[$\epsilon$-covering] [39] Let $(\mathcal{H}, d)$ be a (pseudo)metric space, and $\Theta \in \mathcal{H}$. $\{h_1,\cdots, h_K\}$ is said to be an  $\epsilon$-covering of $\Theta$ if $\Theta \in \bigcup_{i=1}^K\mathcal{B}(h_i,\epsilon)$, i.e., $\forall \theta \in \Theta$, $\exists i ~s.t.~ d(\theta, h_i) \le \epsilon$.

[Covering Number] [39] Based on the notations in Def.<ref>, the covering number of $\Theta$ with radius $\epsilon$ is defined as:

\begin{equation*}
\mathfrak{C}(\epsilon,\Theta, d) = \min\left\{n: \exists \epsilon-\text{covering over $\Theta$ with size n}\right\}.
\end{equation*}

[Chaining Bounds for $\mauc$ Rademacher Complexity] Suppose that the score function $s^{(i)}$ maps $\mathcal{X}$ onto a bounded interval $[-R_s, R_s]$, the following properties hold for $\empsR$:

(a) For a decreasing precision sequence $\{\epsilon_k\}_{k=1}^K$, with $\epsilon_{k+1} = \frac{1}{2} \epsilon_{k},~ k=1,2,\cdots, K-1$ and $\epsilon_0 \ge R_s$, we have:

\begin{equation*}
\begin{split}
\empsR \le N_C \cdot (N_C -1) \cdot \phil\cdot \epsilon_K
+ 6\cdot \sum_{k=1}^K \epsilon_k \phil(N_C-1) \cdot \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon_k,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}}
\end{split}
\end{equation*}

(b) There exists a universal constant $C$, such that:

\[\empsR \le C\cdot \inf_{ R_s \ge \alpha \ge 0} \left(N_C \cdot (N_C -1)\cdot \phil \cdot \alpha + \phil \cdot (N_C-1) \cdot \xi(\bm{Y}) \cdot \int_{\alpha}^{R_s} \sqrt{\frac{\log(\mathfrak{C}(\epsilon,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}} d\epsilon  \right)\]

First of all, we have:

\begin{equation}
\begin{split}
2C_G \empsR  =& C_G \expe_{\sigma}\left[\sup_{\conef \in \mathcal{H}} T_{\conef}(\sigma) + \sup_{\ctwo{\funt} \in \mathcal{H}} T_{\ctwo{\funt} }(\sigma) \right]\\
&=C_G \expe_{\sigma}\left[\sup_{\conef \in \mathcal{H}} T_{f}(\sigma) +\sup_{\ctwo{\funt}  \in \mathcal{H}} T_{\ctwo{\funt} }(-\sigma) \right]\\
& = C_G \expe_{\sigma}\left[\sup_{\conef \in \mathcal{H}} T_{\conef}(\sigma) +\sup_{\ctwo{\funt}  \in \mathcal{H}} -T_{\ctwo{\funt} }(\sigma) \right]\\
& = C_G\expe_{\sigma}\left[\sup_{\conef,\ctwo{\funt}  \in \mathcal{H}} \left(T_{\conef}(\sigma) - T_{\ctwo{\funt}}(\sigma) \right)\right]
\end{split}
\end{equation}

Now define $\hat{\mathcal{H}}$ as an $\epsilon$-cover of $\mathcal{H}$ with the pseudo-metric $d_{\infty,\mathcal{S}}$. Choose ${\conehf}, {{\ctwohft}} \in \hat{\mathcal{H}}$, such that $d_{\infty,\mathcal{S}}(\conef, {\conehf})\le \epsilon$ and  $d_{\infty,\mathcal{S}}(\ctwo{\funt}, {\ctwohft})\le \epsilon$. We then have the following result:

\begin{equation}
\begin{split}
&C_G\expe_{\sigma}\left[\sup_{\conef,\ctwoft \in \mathcal{H}} \left(T_{\conef}(\sigma) - T_{\ctwoft}(\sigma) \right)\right] \\
&=C_G\expe_{\sigma}\left[\sup_{\conef,\ctwoft \in \mathcal{H}} \left(T_{\conef}(\sigma) - T_{\conehf}(\sigma)\right) + \left(T_{\conehf}(\sigma) -  T_{\ctwohft}(\sigma)\right) +  \left(T_{\ctwohft}(\sigma) -  T_{\ctwoft}(\sigma) \right)\right]\\
&\le 2C_G\expe_{\sigma}\left[\sup_{d_{\infty,\mathcal{N}}(\cones,\conehs)\le \epsilon} \left(T_{\conef}(\sigma) - T_{\conehf}(\sigma)\right)\right] +  C_G\expe_{\sigma}\left[\sup_{\conehs,\ctwohst \in \hat{\mathcal{H}}_{\epsilon}} \left(T_{\conehf}(\sigma) - T_{\ctwohft}(\sigma)\right)\right]
\end{split}
\end{equation}

Furthermore, let $\hat{\mathcal{H}}_k$ be an $\epsilon_k$-cover of $\mathcal{H}$. For each $k$, pick $\conehsk$, $\ctwohstk$ such that $d_{\infty, \mathcal{S}}(\conehsk, \cones) \le \epsilon_k$ and $d_{\infty, \mathcal{S}}(\ctwohstk, \ctwost) \le \epsilon_k$. Specifically, we take  $\epsilon_K = \epsilon$, $\epsilon_0 \ge R_s$,  which allows us to choose $\conehsn{0} = \ctwohstn{0}$,  $\epsilon_{k+1} = \frac{1}{2} \epsilon_k$, $\conehfn{K} = \conehf$, and $\ctwohftn{K} = \ctwohft$  . With $\conehfk = \mathsf{soft} \circ \conehsk$ and $\ctwohftk = \mathsf{soft} \circ \ctwohstk$. Then, for $\cones, \ctwost \in \hat{\mathcal{H}}_{\epsilon}$, we can decompose  $T_{\conehf}(\sigma)$  as

\[T_{\conehf}(\sigma) = T_{\conehfn{K}}(\sigma)= T_{\conehfn{0}}(\sigma) + \sum_{i=1}^K \left(T_{\conehfk}(\sigma) - T_{\conehfn{k-1}}(\sigma)\right)~~~ \text{and}~~~T_{\ctwohft}(\sigma) = T_{\ctwohftn{K}}(\sigma)= T_{\ctwohftn{0}}(\sigma) + \sum_{i=1}^K \left(T_{\ctwohftk}(\sigma) - T_{\ctwohftn{k-1}}(\sigma)\right). \]

Based on the decompositions, we have:

\begin{equation}\label{eq:chain1}
\begin{split}
C_G\expe_{\sigma}\left[\sup_{\conehs,\ctwohst \in \hat{\mathcal{H}}_{\epsilon}} \left(T_{\conehf}(\sigma) - T_{\ctwohft}(\sigma)\right)\right] \le  2 \cdot C_G \cdot \sum_{i=1}^K \expe_{\sigma}\left[\supcover \left(T_{\hat{f}_k}(\sigma) - T_{\hat{f}_{k-1}}(\sigma)\right)\right].
\end{split}
\end{equation}

According to maximal inequality (Lem.<ref>), we have:

\begin{equation}\label{eq:chain2}
C_G \expe_{\sigma}\left[\supcover \left(T_{\hat{f}_k}(\sigma) - T_{\hat{f}_{k-1}}(\sigma)\right)\right] \le  3\epsilon_{k} \sqrt{2\log{|\hat{\mathcal{H}}_{k}|\cdot |\hat{\mathcal{H}}_{k-1}|}} \le 6\epsilon_{k}\sqrt{\log(\mathfrak{C}(\epsilon_k,\mathcal{F}, d_{\infty, \mathcal{S}}))}.
\end{equation}

Following a similar derivation to Lem.<ref>, we have:

\begin{equation}\label{eq:chain3}
\expe_{\sigma}\left[\sup_{d_{\infty,\mathcal{N}}(\cones,\conehs)\le \epsilon_K} \left(T_{\conef}(\sigma) - T_{\conehf}(\sigma)\right)\right] \le N_C \cdot (N_C -1) \cdot \phil \cdot \epsilon_K
\end{equation}

Putting all together, we have:

\begin{equation*}
\begin{split}
\empsR &= \frac{1}{2} \cdot \expe_{\sigma}\left[\sup_{\conef,\ctwoft \in \mathcal{H}} \left(T_{\conef}(\sigma) - T_{\ctwoft}(\sigma) \right)\right]  \le N_C \cdot (N_C -1) \cdot \phil \cdot  \epsilon_K + \left(\frac{1}{C_G}\right) 6 \sum_{i=1} \epsilon_{k} \sqrt{\log(\mathfrak{C}(\epsilon_k,\mathcal{F}, d_{\infty, \mathcal{S}}))} \\
& \le  N_C \cdot (N_C -1) \cdot \phil\cdot \epsilon_K +  6 \sum_{i=1}^K \epsilon_{k}\phil\cdot (N_C-1) \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon_k,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}}
\end{split}
\end{equation*}

This ends the proof of (a).

Given the result of (a), we now turn to proof (b). First note that $\epsilon_k  = 2(\epsilon_{k} - \epsilon_{k+1})$ and that $\log(\mathfrak{C}(\epsilon,\mathcal{F}, d_{\infty, \mathcal{S}})$ is non-increasing with respect to $\epsilon$.
We then have:

\begin{equation*}
\begin{split}
&N_C \cdot (N_C -1) \cdot \phil\cdot \epsilon_K +  6 \sum_{i=1}^K \epsilon_{k} \phil\cdot (N_C-1) \cdot \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon_k,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}} \\
& \le 2 N_C \cdot (N_C -1) \cdot  \phil\cdot \epsilon_{K+1} +  12 \sum_{i=1}^K (\epsilon_{k} - \epsilon_{k+1}) \cdot (N_C-1)\phil\cdot \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon_k,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}}
\end{split}
\end{equation*}

Furthermore, we have:

\begin{equation*}
\begin{split}
\empsR &\le 12\phil \left( N_C \cdot (N_C -1) \cdot \epsilon_{K+1} +  \sum_{i=1}^K (\epsilon_{k} - \epsilon_{k+1})  \cdot (N_C-1) \cdot \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon_k,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}}\right)\\
&\le 12 \phil \bigg( N_C \cdot (N_C -1) \cdot \epsilon_{K+1} + \int_{\epsilon_{K+1}}^{R_s}   (N_C-1) \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}} d\epsilon \\
&~~~+\int_{R_s}^{\epsilon_0}  (N_C-1) \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}} d\epsilon  \bigg) \\
&= 12 \phil \left(N_C \cdot (N_C -1) \cdot \epsilon_{K+1} + \int_{\epsilon_{K+1}}^{R_s}  \xi(\bm{Y})\sqrt{\frac{\log(\mathfrak{C}(\epsilon,\mathcal{F}, d_{\infty, \mathcal{S}}))}{N}} d\epsilon \right)
\end{split}
\end{equation*}

It then becomes clear that the universal constant should be chosen as $C = 12$. Set $\alpha = \epsilon_{K+1}$.  By proper choices of $K$ and $\epsilon_0$ and let $\alpha = \frac{\epsilon_0}{2^{K+1}}$, we see that the inequality holds for all $\alpha \in [0, R_s]$, which thus completes the proof.

According to Thm.<ref>, we have the following theorem as a result of a new minorization technique which appears in a recent work [65].
[Transformation Upper Bound] Given the Hypothesis class
\[ \mathsf{soft} \circ \mathcal{F} = \bigg\{\bm{g}(\x) = \mathsf{soft}(\bm{s}(\x)):~ \s \in \mathcal{F}\bigg\}, \]
where $\mathsf{soft}(\cdot)$ is the softmax function. Suppose that $\s(x) \subseteq [-R_s, R_s]^{N_C}$ and $\ell$ is $\phil$-Lipschitz continuous, the following inequality holds:

\begin{equation}
\begin{split}
&\frac{\empsRF}{N_C(N_C-1)} \le \phil\bigg( 2^9 \cdot \frac{1}{N_C} \cdot  \sqrt{N_C}\cdot\xi(\bm{Y})\cdot \log^{3/2}\left(e \cdot R_s \cdot N \cdot N_C\right) \cdot \hat{\mathfrak{R}}_{N\cdot N_C}(\Pi \circ \mathcal{F})+ \sqrt{\frac{1}{N}}\bigg),
\end{split}
\end{equation}

where the Rademacher complexity  $\hat{\mathfrak{R}}_{N\cdot N_C}(\Pi \circ \mathcal{F})$ is defined as:

\begin{equation}
\begin{split}
&\hat{\mathfrak{R}}_{N\cdot N_C}(\Pi \circ \mathcal{F})  \\
&~~= \expe_{\sigma}\left[\sup_{f = (f^{(1)}, \cdots, f^{(N_C)})\in \mathcal{F} } \frac{1}{N\cdot N_C} \sum_{j=1}^{N_C} \sum_{i=1}^N \sigma^{(i)}_j \cdot f^{(j)}(\x_i)\right],
\end{split}
\end{equation}

where $\{\sigma^{(i)}_j\}_{(i,j)}$ is a sequence of independent Rademacher random variables.

With the help of the chaining bound in Thm.<ref>-a), the proof follows an analogous spirit as  <cit.>, with the parameters therein set as $\lambda = 1, ~\theta = 0, ~q = N_C, ~n = N.$

The result in Thm.<ref> directly relates the complicated pairwise Rademacher complexity $\empsRF$ to the instance-wise Rademacher complexity $\hat{\mathfrak{R}}_{N\cdot N_C}$. This makes the derivation of the generalization upper bound much easier.  Once a bound on the ordinary Rademacher complexity over the functional class $\mathcal{F}$ is available, we can directly plug it in to this theorem and find a resulting bound over the $\mauc$ complexity.

§ PRACTICAL GENERALIZATION BOUNDS

§.§ Practical Results for Linear Models

In this section, we provide concrete generalization bounds for two practical models.

Based on the assumptions of Thm.<ref>, we have the   Given the hypothesis space for $\ell_p$ norm penalized linear model as:

\begin{equation*}
\begin{split}
\mathcal{H}^{Lin}_{p,\gamma} = \big\{&f=(f^{(1)},\cdots,f^{(n_C)}): f^{(i)}(\x) = \bm{W}^{(i)}\bm{x},\\
&||\bm{W}^{(i)}||_p \le \gamma \big\},
\end{split}
\end{equation*}

if $\ell$ is $\phil$-Lipschitz continuous, and the input features are sampled from $\mathcal{X} \subset \mathcal{R}^{d}$, and for all $\bm{x} \in \mathcal{X}$, we have $||\bm{x}||^2_2 \le R$ with $0<p<\infty$, $\frac{1}{p} + \frac{1}{\bar{p}} =1$, for all $f\in \Hlin$, we have the following inequality holds with probability at least $1-\delta$:

\begin{equation*}
{R}_{\ell}(f) \le \hat{R}_{\ell, \mathcal{S}}(f)  +  \mathcal{I}_{{Lin}}\bigg(\chi(\bm{Y}),\xi({\bm{Y}}),\delta\bigg) \cdot \sqrt{\frac{1}{N}},
\end{equation*}

\begin{equation*}
\begin{split}
& \mathcal{I}_{{Lin}}\bigg(\chi(\bm{Y}),\xi({\bm{Y}}),\delta\bigg) =  \frac{4 \Rx\phil\gamma}{N_C-1} \cdot  \sqrt{\frac{2(\bar{p} -1)}{N_C}} \cdot \rchi(\bm{Y})  \\
&+  \dfrac{5B }{N_C } \cdot \sqrt{2\log\left(\dfrac{2}{\delta}\right)} \cdot \xi(\bm{Y}).
\end{split}
\end{equation*}

Follows Thm.<ref>, Lem.<ref>

§.§ Practical Results for Deep Fully-connected Neural Networks

Settings. We denote an $L$-layer deep fully-connected neural network with $N_C$-way output as :

\[ f(\x) =  \bm{W} f_{\bm{\omega},L}(\bm{x}) =\bm{W} s(\bm{\omega}_{L-2}\cdots s(\bm{\omega}_1\bm{x})),\]

The notations are as follows: $s(\cdot)$ is the activation function; $n_{h_j}$ is the number of hidden neurons for the $j$-th layer;  $\bm{\omega}_{j} \in \mathbb{R}^{n_{h_{j+1}} \times n_{h_{j}}}, j = 1,2,\cdots, L-2$ are the weights for the first $L-1$ layers; $\bm{W} \in \mathbb{R}^{n_{h_{L-1}}\times N_C }$ is the weight for the output layer. Moreover, the $i$-th output of the network is defined as :

\[ f^{(i)}(\x) =  \bm{W}^{(i)^\top} f_{\bm{\omega},L}(\bm{x}).\]

where $\bm{W}^{(i)^\top}$ is the i-th row of $\bm{W}$.  In the next theorem, we focus on a specific hypothesis class for such networks where the product of weight norms

\[\Pi_{\bm{W},\bm{\omega}} =  ||\bm{W}||_F \cdot\prod_{j=1}^{L-2}||\bm{\omega}_j||_F \]

are no more than $\gamma$. We denote such a hypothesis class as $\Hdnn$:

\begin{equation*}
\begin{split}
\Hdnn =\bigg\{&  f: f^{(i)}(\bm{x}) = \bm{W}^{(i)^\top} f_{\bm{\omega},L}(\bm{x}), ||f^{(i)}||_\infty \le R_s,~i =1,\cdots,N_C, ~ \Pi_{\bm{W},\bm{\omega}} \le \gamma\bigg\},
\end{split}
\end{equation*}

To obtain the final output, we perform a softmax operation over $f(\x)$. Thus, a valid model under this setting could be chosen  from the following hypothesis class:

\begin{equation*}
\begin{split}
\mathsf{soft} \circ \Hdnn =\bigg\{  g:& g^{(i)} = \dfrac{\exp(f^{(i)}(\x))}{\sum_{j=1}^{N_C} \exp(f^{(j)}(\x))},~ f \in \Hdnn  \bigg \}.
\end{split}
\end{equation*}

[Practical Generalization Bounds for Deep Models]
Based on the assumptions of Thm.<ref>
where  $s(\cdot)$ is a 1-Lipshiptz and positive homogeneous activation function.  If $\ell$ is $\phil$-Lipschitz continuous, and the input features are sampled from $\mathcal{X} \subset \mathbb{R}^{d}$, and for all $\bm{x} \in \mathcal{X}$, we have $||\bm{x}||^2_2 \le \Rx$,  for all $ f \in \mathsf{soft} \circ \Hdnn$, we have the following inequality holds with probability at least $1-\delta$:

\begin{equation*}
R_\ell(f) \le \js  + \min\bigg(\mathcal{I}_{{DNN,1}},~  \mathcal{I}_{{DNN,2}}\bigg) \cdot \sqrt{\frac{1}{N}}
\end{equation*}

where $\rchi(\bm{Y}) =\sqrt{\sumi \suminj \nicefrac{1}{\rho_i\rho_j}},~~ \xi(\bm{Y}) = \sqrt{\sumi \nicefrac{1}{\rho_i}}
, ~~\rho_i = \dfrac{\ni}{N},$

\begin{equation*}
\begin{split}
\mathcal{I}_{{DNN,1}} =  C_1\frac{\sqrt{2}}{2} \phil \cdot \frac{\rchi(\bm{Y})}{N_C-1} + \bigg( \frac{\sqrt{2}C_1\Rx\phil\gamma}{2}  \cdot C_3 +  \dfrac{C_2B }{{N_C}} \cdot \sqrt{2\log\left(\dfrac{2}{\delta}\right)}\bigg) \cdot \xi(\bm{Y}),
\end{split}
\end{equation*}

\begin{equation*}
\begin{split}
\mathcal{I}_{{DNN,2}}  =& C_1\phil\bigg( \frac{2^9}{N_C} \cdot \xi(\bm{Y})\cdot \log^{3/2}\left(K\cdot N \cdot N_C\right) \gamma \cdot \Rx \cdot (\sqrt{2\log(2)L}+1)+ 1\bigg) + C_2 \frac{ B\cdot\sqrt{{\log(\nicefrac{2}{\delta})}}\cdot \xi(\bm{Y})}{N_C}
\end{split}
\end{equation*}

$C_1$, $C_2$ are universal constants as thm.<ref>, $K = e\cdot R_s$, $C_3 =\frac{\sqrt{L\log2} + \sqrt{N_C}}{\sqrt{N_C-1}}$.

Follows Thm.<ref>, Lem.<ref>, Thm.<ref> and the fact that  $\hat{\mathfrak{R}}_{N\cdot N_C}(\Pi \circ \mathcal{F})\le \frac{\Rx\gamma (\sqrt{2\log(2)L}+1)}{N\cdot N_C}$ from Thm.1 in [27].

§.§ Practical Results for Deep Convolutional Neural Networks

Now we use the result in Thm.<ref> to derive a generalization bound for a general class of deep neural networks where fully-connected layers and convolutional layers coexist. In a nutshell, the result is essentially an application of Thm.<ref> to a recent idea appeared in [49].

General Setting. Now we are ready to introduce the setting of the deep neural networks employed in the forthcoming theoretical analysis, which is adopted from [49]. We focus on the deep neural networks with $N_{conn}$ fully-connected layers and $N_{conv}$ convolutional layers. The $i$-th convolutional layer has a kernel $\bm{K}^{(i)} \in \mathbb{R}^{k_i \times k_i \times c_{i-1} \times c_i}$. Recall that convolution is a linear operator. For a Given kernel $\bm{K}$, we denote its associated matrix as $op(\bm{K})$, such that $\bm{K}(\bm{x}) = op(\bm{K}) \bm{x}$. Moreover, we assume that, each time, the convolution layer is followed by a componentwise non-linear activation function and an optional pooling operation. We assume that the activation functions and the pooling operations are all $1$-Lipschitz. For the $i$-th fully-connected layer,  we denote its weight as $\bm{V}^{(i)}$. Above all, the complete parameter set of a given deep neural network could be represented as $\bm{P}= \{\bm{K}^{(1)},\cdots, \bm{K}^{(N_{conv})}, \bm{V}^{(1)}, \cdots, \bm{V}^{(N_{conn})}\}$. Again, we also assume that the loss function is $\phil$-Lipschitz and $Range\{\ell\} \subseteq [0,B]$. Finally, given two deep neural networks with parameters $\coneP$ and $\ctwoP$, we adopt a metric $d_{NN}(\cdot,\cdot)$ to measure their distance:

\begin{equation*}
d_{NN}(\coneP,\ctwoP) = \sum_{i=1}^{N_{conv}} ||op(\coneK) -op(\ctwoK)||_2 + \sum_{i=1}^{N_{conn}} ||\coneV - \ctwoV||_2
\end{equation*}

Constraints Over the Parameters. First, we define  $\mathcal{P}^{(0)}_{\nu}$ as the class for initialization of the parameters:

\begin{equation*}
\mathcal{P}^{(0)}_{\nu} = \bigg\{\bm{P}: \left(\max_{i\in \{1,\cdots, N_{conv}\}}||op(\bm{K}^{(i)})||_2 \right) \le 1+\nu, ~ \left(\max_{j \in \{1,\cdots, N_{conn}\}} ||\bm{V}^{(j)}||_2\right) \le 1+\nu \bigg\}
\end{equation*}

Now we further assume that the learned parameters should be chosen from a class denoted by $\mathcal{P}_{\beta, \nu}$, where the distance between the learned parameter and the fixed initialization residing in $\mathcal{P}^{(0)}_{\nu}$ is no bigger than $\beta$:

\begin{equation*}
\mathcal{P}_{\beta, \nu} = \bigg\{\bm{P}: d_{NN}(\coneP,\ctwoP_0) \le \beta, ~\ctwoP_0 \in \mathcal{P}^{(0)}_\nu \bigg\}.
\end{equation*}

The following result then provides a generalization upper bound based on Thm.<ref> and Lem.<ref>.

Based on the setting in Lem.<ref>, given dataset $\mathcal{S} = \{(\bm{x}_i,y_i)\}_{i=1}^m$, where the instances are sampled independently, for all multiclass scoring functions $f \in \mathsf{soft} \circ \mathcal{F}_{\beta,\nu}$, if $Range\{\ell\}\subseteq[0,B]$, $\forall \delta \in (0,1)$, the following inequalities hold with probability at least $1 - \delta$:

\begin{equation*}
\begin{split}
R_\ell(f) \le& \js + C_1 \cdot \left(\frac{\tilde{C}\cdot\phil  \cdot R_s \cdot \xi(\bm{Y})}{N_C} \cdot \sqrt\frac{N_{par}\left(\nu N_{L} + \beta + \log \left(3{\beta\Rx{N}}\right) \right)}{{N}}\right)+ C_2 \cdot \frac{B\cdot\xi(\bm{Y})}{N_C}   \cdot \sqrt{\frac{\log(\nicefrac{2}{\delta})}{{N}}}
\end{split}
\end{equation*}

where $C_1, C_2, \tilde{C}$ are universal constants.

§.§ Essential Lemmas

§.§.§ $\mauc$ Rademacher Complexity for p-norm penalized Linear Models

We have:

\begin{equation}
\empsRLin \le \Rx\phil\gamma \cdot  \sqrt{2(\bar{p} -1) \cdot N_C  } \cdot \rchi(\bm{Y}) \sqrt{\frac{1}{N}} \\
\end{equation}

$\rchi(\bm{Y}) =\sqrt{\sumi \suminj \frac{1}{\rho_i,\rho_j}}
, ~~\rho_i = \frac{\ni}{N}.$

\begin{equation*}
\begin{split}
\empsRLin &= \expe_\sigma \left[  \supf \empcomp \right]\\
\\
&=  \expe_\sigma  \left[ \supw \sumi \suminj \sumxone \sumxtwo \frac{\sigmai_m + \sigmaj_n }{2} \cdot \ninj \cdot  \ell(\bm{W}^{(i)^\top}(\x_m-\x_n)) \right] \\
\\
& \le  \sumi \suminj \sumxtwo   \expe_{\sigma^{(i)}}\left[  \supwi    \sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  \ell(\bm{W}^{(i)^\top}(\x_m-\x_n)) \right] \\ \\
&~~ + \sumi \sumxone    \expe_{\sigma^{(j)}}\left[  \supwi   \suminj  \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj \cdot  \ell(\bm{W}^{(i)^\top}(\x_m-\x_n)) \right] \\ \\
\end{split}
\end{equation*}

\begin{equation*}
\begin{split}
\empsRLin & \overset{(*)}{\le} \phil\sumi \suminj \sumxtwo   \expe_{\sigma^{(i)}}   \left[   \supwi\sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  \bm{W}^{(i)^\top}(\x_m-\x_n) \right] \\ \\
&~~ + \phil\sumi  \sumxone     \expe_{\sigma^{(j)}}\left[   \supwi   \suminj \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj \cdot  \bm{W}^{(i)^\top}(\x_m-\x_n) \right]
\end{split}
\end{equation*}

That is to say,

\begin{equation}
\begin{split}
\empsRLin & {\le} \phil\cdot\gamma \sumi  \suminj \sumxtwo   \expe_{\sigma^{(i)}}  \left[   \left\| \sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{\bar{p}}\right] \\ \\
&~~ + \phil\cdot\gamma \sumi \sumxone     \expe_{\sigma^{(j)}}  \left[   \left\| \suminj  \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{\bar{p}} \right] \\ \\
& \overset{(**)}{\le} \phil\cdot\gamma \sumi  \suminj \sumxtwo       \bigg(\expe_{\sigma^{(i)}} \left[\left\| \sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{\bar{p}}^{\bar{p}} \right]\bigg)^{\nicefrac{1}{\bar{p}}} \\ \\
&~~ + \phil\cdot\gamma \sumi \sumxone         \expe_{\sigma^{(j)}}  \left[\bigg(\left\|  \suminj  \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{\bar{p}}^{\bar{p}}\bigg)\right]^{\nicefrac{1}{\bar{p}}},  \\ \\
\end{split}
\end{equation}

where $(*)$ is due to the Talagrand contraction lemma, $(**)$ follows that fact that $()^{\nicefrac{1}{\bar{p}}}$ is concave for $\bar{p} > 1$ and Jensen's Inequality.

\begin{equation*}
\begin{split}
\empsRLin & \overset{(***)}{\le} \phil\cdot\gamma \sqrt{\bar{p}-1} \sumi  \suminj \sumxtwo      \expe_{\sigma^{(i)}} \left[ \left\| \sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{2}^{2}\right]^{\nicefrac{1}{2}} \\ \\
&~~ + \phil\cdot\gamma \cdot \sqrt{\bar{p}-1} \sumi \sumxone        \expe_{\sigma^{(j)}} \left[ \left\|   \suminj  \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{2}^{2}\right]^{\nicefrac{1}{2}}  \\ \\
& \overset{(****)}{\le} \phil\cdot\gamma \sqrt{\bar{p}-1} \sqrt{N\cdot N_C}          \bigg(\sumi\suminj \sumxtwo\expe_{\sigma^{(i)}} \left[ \left\| \sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  (\x_m-\x_n)\right\|_2^2 \right]  \\ \\
&~~~~~+ \sumxone \expe_{\sigma^{(j)}} \left[ \left\|   \suminj  \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{2}^{2}\right] \bigg)^{\nicefrac{1}{2}}\\ \\
& \le  \Rx \phil\gamma  \sqrt{2\frac{\bar{p}-1}{N}} \cdot \sqrt{N_C \sumi \cdot \suminj \frac{1}{\rho_i\rho_j}},
\end{split}
\end{equation*}

where $(***)$ is due to Lem.<ref>, and $(****)$ is due to $\forall \x \in \mathbb{R}^{N}$ $\|\x\|_1 \le \sqrt{N} \|\x\|_2$, and the last inequality follows that :

\begin{equation*}
\begin{split}
&\expe_{\sigma^{(i)}}\left[ \left\| \sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  (\x_m-\x_n)\right\|_2^2\right] \le \sumxone \frac{1}{4n_i^2n_j^2} \|\x_m-\x_n\|_2^2 \le  \sumxone  \frac{\Rx^2}{n_i^2n_j^2}\\
&\expe_{\sigma^{(j)}} \left [\left\|\suminj \sumxtwo\frac{\sigmaj_n}{2} \cdot \ninj \cdot  (\x_m-\x_n) \right\|_{2}^{2} \right] \le \suminj \sumxtwo \frac{1}{4n_i^2n_j^2} \|\x_m-\x_n\|_2^2   \le  \suminj\sumxtwo  \frac{\Rx^2}{n_i^2n_j^2}
\end{split}
\end{equation*}

§.§.§ $\mauc$ Rademacher Complexity for A class of Deep Fully-connected Neural Networks

we have:

\begin{equation*}
\begin{split}
&\empsRDnn \le \frac{\sqrt{2}}{2} \phil \Rx   \gamma N_C \xi(\bm{Y}) \bigg( \sqrt{\frac{L\log2(N_C-1)}{N}}+ \sqrt{\frac{N_C(N_C-1)}{N}}\bigg) \\
&~~  +  \frac{\sqrt{2}}{2} \phil N_C \rchi(\bm{Y}) \sqrt{\frac{1}{N}}
\end{split}
\end{equation*}

where $\rchi(\bm{Y}) =\sqrt{\sumi \suminj \frac{1}{\rho_i,\rho_j}}, \xi(\bm{Y}) = \sqrt{\sumi \frac{1}{\rho_i}}
, ~~\rho_i = \frac{\ni}{N}. $

Similar to Lem.<ref>, we can achieve the bound:

\begin{equation*}
\begin{split}
\empsRDnn &\le \phil\sumi \suminj \sumxtwo   \expe_{\sigma^{(i)}} \left[ \sup_{g \in \Hsdnn}    \sumxone \frac{\sigmai_m}{2} \cdot \ninj \cdot  ( g^{(i)}(\bm{x}_m)- g^{(i)}(\bm{x}_n) ) \right] \\ \\
&~~ + \phil\sumi  \sumxone     \expe_{\sigma^{(j)}} \left[  \sup_{g \in \Hsdnn}    \suminj \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj \cdot ( g^{(i)}(\bm{x}_m)- g^{(i)}(\bm{x}_n) ) \right] \\ \\
\end{split}
\end{equation*}

By the sub-additivity of supremum, we have:

\begin{equation}
\begin{split}
\empsRDnn&  \le \underbrace{\phil\sumi (N_C-1) \cdot   \expe_{\sigma^{(i)}} \left[ \sup_{g \in \Hsdnn}    \sumxone \frac{\sigmai_m}{2} \cdot \frac{1}{\ni} \cdot  ( g^{(i)}(\bm{x}_m) ) \right]}_{(a)} \\ \\
&~~ + \underbrace{\phil\sumi      \expe_{\sigma^{(j)}}  \left[ \sup_{g \in \Hsdnn}   \suminj \sumxtwo \frac{\sigmaj_n}{2} \cdot \frac{1}{\nj} \cdot (  g^{(i)}(\bm{x}_n) ) \right]}_{(b)} \\ \\
&~~ + \underbrace{\phil\sumi \suminj \sumxtwo   \expe_{\sigma^{(i)}}\left[  \sup_{g \in \Hsdnn}    ( g^{(i)}(\bm{x}_n) )\sumxone \frac{\sigmai_m}{2} \cdot \ninj    \right]}_{(c)} \\ \\
&~~ + \underbrace{\phil\sumi  \sumxone     \expe_{\sigma^{(j)}}  \sup_{g \in \Hsdnn}   \left[(g^{(i)}(\bm{x}_m) ) \cdot \suminj \sumxtwo \frac{\sigmaj_n}{2} \cdot \ninj   \right]}_{(d)}
\end{split}
\end{equation}

We first derive the bound for $(a)+(b)$.

According Lem.<ref> and Lem.<ref>, we know that:

\begin{equation*}
\begin{split}
(a)+(b)  \le \phil\sumi (N_C-1) \cdot   \expe_{\sigma^{(i)}}\bigg[  &\suphd    \sumxone  \sum_{c=1}^{N_C}\frac{\sigmai_{m,c}}{2} \cdot \frac{1}{\ni} \cdot  ( f^{(c)}(\bm{x}_m) ) \bigg] \\ \\
&~~ + \phil\sumi      \expe_{\sigma^{(j)}} \left[  \suphd     \suminj \sumxtwo \sum_{c=1}^{N_C} \frac{\sigmaj_{n,c}}{2} \cdot \frac{1}{\nj} \cdot (  f^{(c)}(\bm{x}_n) ) \right]
\end{split}
\end{equation*}

Using the Lem.<ref> recursively towards hierarchical structure of DNN, we have:

\begin{equation*}
\begin{split}
&\expe_{\sigma^{(i)}} \left[\suphd  \sumxone \sum_{c=1}^{N_C} \frac{\sigmai_{m,c}}{2}\cdot \ninj \cdot  ( f^{(c)}(\bm{x}_m) ) \right] \\
&~~~~~~ \le  \frac{1}{\lambda} \log \left( \exp \left( \lambda \cdot \expe_{\sigma^{(i)}}\left[ \suphd  \sumxone \sum_{c=1}^{N_C} \frac{\sigmai_{m,c}}{2}\cdot \ninj \cdot  ( f^{(c)}(\bm{x}_m) ) \right] \right) \right) \\
&~~~~~~ \le  \frac{1}{\lambda} \log \left( \left(  \expe_{\sigma^{(i)}} \left[ \suphd \exp   \left(\lambda \cdot \sumxone  \sum_{c=1}^{N_C} \frac{\sigmai_{m,c}}{2}\cdot \ninj \cdot  ( f^{(c)}(\bm{x}_m) )\right) \right] \right) \right) \\
&~~~~~~\le \frac{1}{\lambda}\log\bigg(2^L \cdot  \expe_{\sigmai} \left[  \exp\left(\lambda\gamma  \left\|\sumxone \sum_{c=1}^{N_C} \frac{\sigmai_{m,c}}{2}\cdot \ninj \cdot  \x_m\right\| \right) \right] \bigg) \\
\end{split}
\end{equation*}

\begin{equation*}
\begin{split}
&\expe_{\sigma^{(j)}} \left[   \suphd \suminj \sumxtwo \sum_{c=1}^{N_C} \frac{\sigmaj_{n,c}}{2} \cdot \ninj \cdot (  f^{(c)}(\bm{x}_n) )  \right] \\
&~~~~~~\le  \frac{1}{\lambda}\log\bigg(2^L \cdot  \expe_{\sigmaj} \left[ \exp\left(\lambda\gamma  \left\|\suminj \sumxtwo \sum_{c=1}^{N_C} \frac{\sigmaj_{n,c}}{2}\cdot \ninj \cdot  \x_n\right\| \right)\right] \bigg).
\end{split}
\end{equation*}

This suggests that:

\begin{equation*}
\begin{split}
(a+b)  \le
\phil\sumi \frac{1}{\lambda} \log\bigg(2^L \cdot  \expe_{\sigma} \bigg[  \exp\bigg(\lambda\gamma& (N_C-1)  \bigg\|\sumxone \sum_{c=1}^{N_C}  \frac{\sigmai_{m,c}}{2}\cdot \frac{1}{\ni} \cdot  \x_m\bigg\| \\
&+ \lambda\gamma    \left\|\suminj \sumxtwo \sum_{c=1}^{N_C}  \frac{\sigmaj_{n,c}}{2}\cdot \frac{1}{\nj} \cdot  \x_n\right\|  \bigg) \bigg] \bigg),
\end{split}
\end{equation*}

which is due to the property that $\expe_{\bm{a},\bm{b}}(f(\bm{a})\cdot g(\bm{a})) =  \expe_{\bm{a}}(f(\bm{a})) \cdot \expe_{\bm{b}}(g(\bm{b}))$, if $\bm{a}$ and $\bm{b}$ are independent.

\begin{equation}
\begin{split}
\bm{Z}_i = \gamma (N_C -1)  \bigg\| \sumxone  \sum_{c=1}^{N_C} & \frac{\sigmai_{m,c}}{2}\cdot \frac{1}{\ni} \cdot  \x_m\bigg\|
+ \gamma   \left\|\suminj \sumxtwo \sum_{c=1}^{N_C}  \frac{\sigmaj_{n,c}}{2}\cdot \frac{1}{\nj} \cdot  \x_n\right\|
\end{split}
\end{equation}

as a random variable with respect to the Rademacher random variables. We have:

\begin{equation*}
\begin{split}
(a) + (b) &\le \phil\left(\sumi \frac{L\log2+ \log(\expe_{\sigma}\exp(\lambda(\bm{Z}_i-\mathbb{E}(\bm{Z}_i)))}{\lambda} +\sumi \expe_{\sigma}(\bm{Z}_i) \right).\\
\end{split}
\end{equation*}

Similar to the proof of Lem.<ref>, we can bound

\begin{equation}
\sumi \expe_{\sigma}(\bm{Z}_i)\le \frac{\sqrt{2}}{2}  \gamma \cdot\Rx   \cdot (N_C)^{3/2} \left((N_C-1) \sumi \cdot \suminj \frac{1}{\rho_i}\right)^{1/2} \cdot \frac{1}{\sqrt{N}}.
\end{equation}

Utilizing the bounded difference inequality (Lem.<ref>) of $\bm{Z}_i$, we come to the following result:

\begin{equation}
\expe_{\sigma}\exp\left(\lambda(\bm{Z}_i-\mathbb{E}(\bm{Z}_i)\right) \le \exp\left( \frac{\lambda^2 v_i}{2}\right), ~~ v_i \le \frac{N_C}{4} \frac{(N_C - 1)^2}{\ni}\gamma^2\Rx^2 + \frac{N_C}{4}\suminj \frac{\gamma^2\Rx^2}{\nj},
\end{equation}

which leads to the bound:

\begin{equation}
\left(\sumi \frac{L\log2+ \log(\expe_{\sigma}\exp(\lambda(\bm{Z}_i-\mathbb{E}(\bm{Z}_i)))}{\lambda}\right) \le \left(\sumi \frac{L\log2+ ( \dfrac{\lambda^2 v_i}{2})}{\lambda}\right)
\end{equation}

By choosing $\lambda = \sqrt{\frac{2N_CL\log2}{\sumi v_i}}$, we reach the optimal bound as:

\begin{equation}
\begin{split}
\sumi \frac{L\log2+ \log(\expe_{\sigma}\exp(\lambda(\bm{Z}_i-\mathbb{E}(\bm{Z}_i)))}{\lambda}& \\ \\
&~~~\le \sqrt{{2N_CL\log2}\cdot {\sumi v_i}} \\
&~~~~ =  R \cdot \gamma \cdot \sqrt{\frac{L\log2}{2N}} \cdot \sqrt{\sumi \frac{N_C-1}{\rho_i}}.
\end{split}
\end{equation}

Putting all together, we have

\begin{equation}
\begin{split}
(a) +(b) \le \frac{\sqrt{2}}{2} \phil  \Rx  \gamma \cdot  (N_C(N_C-1))^{1/2} \xi(\bm{Y})  \left(  \sqrt{\frac{N_CL\log2}{N}}  + N_C\sqrt{\frac{1}{N}}  \right)
\end{split}
\end{equation}

For (c) and (d), we have:

\begin{equation}\label{eq:dc}
\begin{split}
(c) &\le \phil\sumi \suminj \sumxtwo   \expe_{\sigma^{(i)}} \left[ \left(\suphd  \left|f^{(i)}(\bm{x}_n) )\right|\right)  \cdot \left| \sumxone \frac{\sigmai_m}{2} \cdot \ninj    \right|\right] \\ \\
& \overset{(*)}{\le} \phil\cdot \sumi \suminj \sumxtwo   \expe_{\sigma^{(i)}} \left[   \left| \sumxone \frac{\sigmai_m}{2} \cdot \ninj    \right|\right]
\end{split}
\end{equation}

Similarly, we have :

\begin{equation}\label{eq:dd}
\begin{split}
(d) \overset{(**)}{\le} \phil\sumi \sumxone  \expe_{\sigma^{(j)}} \left[   \left|  \suminj \sumxtwo    \frac{\sigmaj_m}{2} \cdot \ninj    \right|\right],
\end{split}
\end{equation}

where (*) and (**) are due to the fact that the softmax function is upper bounded by 1, i.e.,

\[\suphd |f^{(i)}_{W,L}(\bm{x}_n) | \le 1 ~~ \text{and} ~~ \suphd |f^{(i)}_{W,L}(\bm{x}_m) | \le 1.\]

This finishes the proof for Eq.(<ref>) and Eq.(<ref>).

Now we can reach that:

\begin{equation}
\begin{split}
(c) +(d) & \le \phil\cdot  \sumi \suminj \sumxtwo   \expe_{\sigma^{(i)}} \left[   \left| \sumxone\sum_{c=1}^{N_C} \frac{\sigmai_{m,c}}{2} \cdot \ninj    \right|\right] \\ \\
&~~~~+ \phil\cdot \sumi \sumxone   \expe_{\sigma^{(j)}} \left[   \left|  \suminj \sumxtwo  \sum_{c=1}^{N_C}  \frac{\sigmai_{n,c}}{2} \cdot \ninj    \right|\right] \\  \\
&\le \phil\cdot \sumi \suminj \sumxtwo   \sqrt{\expe_{\sigma^{(i)}} \left[   \left( \sumxone  \sum_{c=1}^{N_C} \frac{\sigmai_{m,c}}{2} \cdot \ninj    \right)^2\right]} \\ \\
&~~~~+ \phil\cdot  \sumi \sumxone  \sqrt{\expe_{\sigma^{(j)}} \left[   \left(  \suminj \sumxtwo   \sum_{c=1}^{N_C}  \frac{\sigmai_{n,c}}{2} \cdot \ninj    \right)^2\right]}
\end{split}
\end{equation}

Similar to the proof of <ref>, we have:

\begin{equation}
(c) +(d)  \le \frac{\sqrt{2}}{2} \cdot  \phil   \cdot \rchi(\bm{Y}) \cdot N_C \sqrt{\frac{1}{N}}
\end{equation}

Now we provide an alternative upper bound by the chaining technique.

Under the setting of Thm.<ref>.

For all $ f \in \mathsf{soft} \circ \Hdnn$, we have the following inequality holds with probability at least $1-\delta$:

\begin{equation*}
R_\ell(f) \le \js  +  \mathcal{I}_{{DNN,2}}  \cdot \sqrt{\frac{1}{N}}
\end{equation*}

where $\xi(\bm{Y}) = \sqrt{\sumi \nicefrac{1}{\rho_i}}
, ~~\rho_i = \dfrac{\ni}{N},$

\begin{equation*}
\begin{split}
\mathcal{I}_{{DNN,2}}   =& C_1\phil\bigg( \frac{2^9}{N_C} \cdot \xi(\bm{Y})\cdot \log^{3/2}\left(K\cdot N \cdot N_C\right) \cdot \gamma \cdot \Rx \cdot (\sqrt{2\log(2)L}+1)+ 1\bigg) + C_2 \frac{ B\cdot\sqrt{{\log(\nicefrac{2}{\delta})}}\cdot \xi(\bm{Y})}{N_C}
\end{split}
\end{equation*}

$C_1$, $C_2$ are universal constants as thm.<ref>, $K = e\cdot R_s$.

The result follows from Thm.<ref>, and the fact that

\[\hat{\mathfrak{R}}_{N\cdot N_C}(\Pi \circ \mathcal{F}) \le \frac{\Rx\gamma\cdot(\sqrt{2\log(2)L}+1)}{\sqrt{N_C\cdot N}},
\]

which follows from Thm.1 in [27]

§.§.§ $\mauc$ Rademacher Complexity for A  Class of Deep Convolutional Neural Networks

Denote the hypothesis class,

\[ \mathsf{soft} \circ \mathcal{F}_{\beta,\nu} = \bigg\{\bm{g}(\x) = \mathsf{soft}(\bm{s}_{\bm{P}}(\x)):~ \bm{s}_{\bm{P}} \in\mathcal{F}_{\beta,\nu}\bigg\}, \]

\[\mathcal{F}_{\beta,\nu} = \{s_{\bm{P}}:\mathbb{R}^{N_{N_L-1}} \rightarrow \mathbb{R}^{N_C}| ~ \bm{P} \in \mathcal{P}_{\beta, \nu}, Range(\bm{s}_P) \subseteq [-R_s, R_s]^{N_C} \}\]

Moreover, define $\tilde{N} = \dfrac{1}{\sum_{i=1}^{N_C}\dfrac{1}{n_i}}$ we assume that $\sup_{x\in\mathcal{X}} ||vec(\bm{x})|| \le \Rx$ and

\[R_s >1/\min\left\{\sqrt{{N}}, \frac{\xi(\bm{Y})}{N_C} \cdot \sqrt{N_{par}\left(\nu N_L + \beta + \log (3\Rx\cdot \beta \cdot {N}) \right) } \right\},\]

we have:

\begin{equation}
\empsRFb \le \tilde{C} \left(\phil \cdot (N_C-1) \cdot R_s \cdot \xi(\bm{Y}) \cdot \sqrt\frac{N_{par}\left(\nu N_{L} + \beta + \log\left(3{\beta\Rx{N}}\right) \right)}{{N}} \right),
\end{equation}

where $N_L = N_{conv} + N_{conn}$, $N_{par}$ is total number of parameters in the neural network, and $\tilde{C}$ is a universal constant.

From <cit.>, we know that:

\begin{equation*}
\max_{z \in \mathcal{Z}_{\mathcal{D}}}|\bm{\cone{s}}_{\coneP}(\bm{z}) - \ctwo{\st}_{\ctwoP}(\bm{z})| \le \sup_{x \in \mathcal{X}}||\bm{\cone{s}}_{\coneP}(\bm{x}) - \ctwo{\st}_{\ctwoP}(\bm{x})||\le \Rx \cdot \beta\cdot\left(1+\nu + \frac{\beta}{N_L}\right)^{N_L} \cdot d_{NN}(\coneP, \ctwoP).
\end{equation*}

Furthermore, according to  <cit.>, we have:

\begin{equation*}
\log(\mathfrak{C}(\epsilon,\mathcal{F}_{\beta,\nu}, d_{\infty, \mathcal{S}}) \le N_{par} \cdot \log\left(\frac{3C_L}{\epsilon}\right),
\end{equation*}

where $C_L = \Rx \cdot \beta \exp(\nu N_L + \beta)$. Following Thm.<ref>-b), we have:

\[\empsR \le C\cdot \inf_{ R_s \ge \alpha \ge 0} \left(N_C \cdot(N_C-1) \cdot \phil \cdot \alpha + \phil \cdot (N_C-1) \cdot  \int_{\alpha}^{R_s} \sqrt\frac{N_{par}\left(\nu N_{L} + \beta + \log (3\beta\Rx/\epsilon) \right)}{\tilde{N}} d\epsilon  \right)\]

Since $R_s > 1/\sqrt{N}$, we can choose $\alpha = \sqrt{\frac{1}{{N}}}$, the result follows from the inequality that:

\begin{equation*}
\int_{\alpha}^{R_s} \sqrt\frac{N_{par}\left(\nu N_{L} + \beta + \log (3\beta\Rx/\epsilon) \right)}{\tilde{N}} d\epsilon  \le  R_s \cdot \xi(\bm{Y}) \cdot \sqrt\frac{N_{par}\left(\nu N_{L} + \beta + \log \left(3{\beta\Rx{N}}\right) \right)}{{N}}.
\end{equation*}

Together with the fact that  $R_s >1/ \left(\frac{\xi(\bm{Y})}{N_C} \cdot \sqrt{N_{par}\left(\nu N_L + \beta + \log (3\Rx\cdot \beta \cdot {N}) \right) } \right),$ we have :

\begin{equation}
\empsRFb \le 2 {C} \left(\phil \cdot (N_C-1) \cdot R_s \cdot \xi(\bm{Y}) \cdot \sqrt\frac{N_{par}\left(\nu N_{L} + \beta + \log\left(3{\beta\Rx{N}}\right) \right)}{{N}} \right).
\end{equation}

The proof is completed by choosing $\tilde{C} = 2 C$.

§ EFFICIENT COMPUTATION

In this section, we will  propose acceleration algorithms for loss and gradient evaluation for three well-known losses: exponential loss $\ell_{exp}(\alpha,t) = \exp(-\alpha t)$, squared loss $\ell_{sq}(t) = (\alpha- t)^2$, and hinge loss  $\ell_{hinge}(\alpha,t) = \max(\alpha-t,0)$.

Generally, the empirical surrogate risk functions $\hat{R}_{\ell} $ have the following abstract form:

\begin{equation*}
\hat{R}_{\ell} = \sumi \suminj \sumxone \sumxtwo \ninj \cdot   \ell(f^{(i)}(\x_m) - f^{(i)}(\x_n)),
\end{equation*}

\begin{equation*}
\text{where}~~ \fii = g_i(
\bm{W}\hth), \bm{W}= [\bm{w}^{(1)},\cdots, \bm{w}^{(N_C)}]^\top.
\end{equation*}

We adopt this general form since it covers a lot of popular models. For example, when $g_i(\cdot)$ is defined as the activation function of the last layer of a neural network (say a softmax function), $\bm{w}^{(i)}$ are the weights of the last layer, and $\hth[\cdot]$ is the neural net where the last layer is excluded, $\fii$ becomes a deep neural network architecture with the last layer designed as a fully-connected layer. As for another instance, if both $g_i(\x)= \x$ and $\hth =\x$, then we reach a simple linear multiclass scoring function. Note that the scalability with respect to sample size only depends on the choice of $\ell$. The choice of $g_i(\cdot)$ and  $\hth[\cdot]$ only affects the instance-wise chain rule. This allows us to provide a general acceleration framework once the surrogate loss is fixed.

Common Notations. Now we introduce the common notations we adopted in this section. We assume that $\bm{w}^{(i)}$ be a vector such that $\bm{w}^{(i)} \in \mathbb{R}^{n_h \times 1}$ . We let $\bm{W}$ be the matrix that concatenates  $\bm{w}^{(i)}$ column-wisely, i.e. ,

\begin{equation}\label{eq:weq}
\bm{W} = [\bm{w}^{(1)},\cdots, \bm{w}^{(N_C)} ]^\top, ~~\bm{W} \in \mathbb{R}^{N_C \times n_h}.
\end{equation}

For the sake of convenience, we rearrange $\bm{\theta}$ as a vector in $\mathbb{R}^{d_\theta \times 1}$ such that it concatenates all the parameters in the model except $\bm{W}$. For example, in a deep neural network, $\bm{\theta}$ concatenates all the parameters except the weights of the last layer. Note that this does not affect the result of the loss and gradient evaluation. A simple reshape suffices to transfer our calculation of gradient to its expected result if $\bm{\theta}$ has complicated structures. $\hth$ should be considered as a vector such that $\hth \in \mathbb{R}^{n_h \times 1}$.  $\bm{H}$ is then defined as the matrix that concatenates all the $\hth[\x]$ from every instance in the sense that:

\begin{equation}\label{eq:heq}
\bm{H} = [\hth[\bm{x}_1],\cdots,\hth[\bm{x}_{N}]]^\top, ~~ \bm{H} \in \mathbb{R}^{n_h \times N}.
\end{equation}

For intermediate partial derivatives, we denote:

\begin{equation}\label{eq:paritala}
\begin{split}
\pfij[\x] = \frac{\partial(\fjj)}{\partial \bm{w}^{(i)^\top} \hth[\x] }
\end{split}
\end{equation}

Furthermore, we have two compact expressions as:

\begin{equation}\label{eq:parital}
\begin{split}
&\bm{\partial}_{i,j} = [\pfij[\x_1], \cdots, \pfij[\x_N]]^\top, ~~ \bm{\partial}_{i,j} \in \mathbb{R}^{N \times 1}, \\
&\bm{\partial}_j(\x_k) =  [\partial_1[\fjj[\x_k]], \cdots,\partial_{N_C}(\fjj[\x_k]) ]^\top, ~~ \bm{\partial}_j(\x_k) \in \mathbb{R}^{N_C \times 1}.
\end{split}
\end{equation}

Another variable is also essential when applying the chain rule:

\begin{equation}\label{eq:udfin}
\bm{U}^{(j)} = [ \nabla_{\bm{\theta}}\hth[\x_1]\bm{W}^\top\bm{\partial}_j(\x_1), \cdots, \nabla_{\bm{\theta}}\hth[\x_N]\bm{W}^\top\bm{\partial}_j(\x_N)], ~~ \bm{U}^{(j)} \in \mathbb{R}^{d_\theta \times N}.
\end{equation}

Finally, we provide a compact notation of the weights $\frac{1}{\ni\nj}$ as:

\begin{equation}\label{eq:dlabel}
\bm{D}^{(i)} = [\frac{1}{n_in_{y_1}},\cdots, \frac{1}{n_in_{y_N}} ]^\top ,~~  \bm{D}^{(i)} \in \mathbb{R}^{N \times 1}.
\end{equation}

§.§ Exponential Loss

Loss Evaluation. For the exponential loss, we can simplify the computations by a factorization scheme:

\begin{equation*}
\begin{split}
\hat{R}_{exp} &= \sumi\sumxone  \suminj \sumxtwo \ninj \cdot  \exp\left(\alpha \cdot \left(\dfi \right)\right),\\
& = \sumi\underbrace{\left(\sumxone \exp(\alpha\cdot \fixm)\right)}_{(a_i)} \cdot \underbrace{\left(\suminj \sumxtwo \ninj \cdot  \exp(-\alpha\cdot\fixn)\right)}_{(b_i)}
\end{split}
\end{equation*}

From the derivation above, the loss evaluation could be done by first calculating $(a_i),(b_i)$ separately and then performing the multiplication, which only takes $O(NN_CT_\ell)$.  This is a significant improvement compared with the original $O(\sumi\suminj n_in_j N_C T_\ell)$ result.

Gradient Evaluation. Due to the factorization scheme, we can also accelerate the gradient evaluation in a similar spirit. According to. Eq.(<ref>)-Eq.(<ref>), we have:

\begin{equation*}
\begin{split}
\nabla_{\bm{w}^{(i)}}(a_j) &= \sumxone \alpha  \exp(\alpha \cdot \fjxm) \cdot \pfij[\x_m] \cdot \hth[\x_m] \\
&=\alpha\bm{H}(\mathcal{I}_i \odot \hat{\bm{y}}^{(i),+}_{exp} \odot \bm{\partial}_{i,j} ).\\
\nabla_{\bm{w}^{(i)}}(b_j)   &= -\suminj \sumxtwo \ninj \alpha \cdot \exp(-\alpha \cdot \fjxn) \cdot \pfij[\x_n] \cdot  \hth[\x_n]\\
&= -\alpha\bm{H}(\mathcal{I}_{\backslash i} \odot \bm{D}^{(i)} \odot \hat{\bm{y}}^{(i),-}_{exp} \odot  \bm{\partial}_{i,j} ), \\
\nabla_{\hth[\x_k]}(a_j) &= \underbrace{\mathcal{I}_j(\x_k) \cdot \alpha \cdot \exp(\alpha \cdot \fjj[\x_k] )}_{q_j(\x_k)}\cdot \sum_{i=1}^{N_C}\pfij[\x_k]  \cdot \wi, \\
& =  {q}_j(\x_k) \cdot \bm{W}^\top \bm{\partial}_j(\x_k)\\
\nabla_{\hth[\x_k]}(b_j) &= -\underbrace{\mathcal{I}_j^c(\x_k)  \cdot \bm{D}^{(i)}_{k} \cdot \alpha  \cdot \exp(-\alpha \cdot \fjj[\x_k] )}_{{\tilde{q}_j(\x_k)}} \cdot \sum_{i=1}^{N_C} \pfij[\x_k] \cdot \wi,\\
& = -\tilde{q}_j(\x_k) \cdot \bm{W}^\top \bm{\partial}_j(\x_k)
% \nabla_{vec(\bm{H})}(a_i) &  = \sumxone \alpha  \exp(\alpha \cdot \fixm) \cdot \hth[\x_m]
\end{split}
\end{equation*}

\begin{equation*}
\begin{split}
& \mathcal{I}_i = I\left[\bm{x}_i \in \Ni\right], ~ \mathcal{I}_{\backslash i} = I\left[\bm{x}_i \notin \Ni\right],~~ \mathcal{I}_j(\x) = \bm{I}\left[ x \in \Nj \right],~~  \mathcal{I}^c_j(\x) = 1 - \mathcal{I}_j(\x)\\
&\hat{\bm{y}}^{(i),+}_{exp} = [\exp(\alpha\cdot f^{(i)}(\bm{x}_1)), \cdots, \exp(\alpha \cdot f^{(i)}(\bm{x}_N))]^\top, \\
&\hat{\bm{y}}^{(i),-}_{exp} = [\exp(-\alpha\cdot f^{(i)}(\bm{x}_1)), \cdots, \exp(-\alpha \cdot f^{(i)}(\bm{x}_N))]^\top. \\
\end{split}
\end{equation*}

Furthermore, we define  $\bm{q}_j = [q_j(\x_1),\cdots, q_j(\x_N)]^\top$
and $\bm{\tilde{q}}_j = [\tilde{q}_j(\x_1),\cdots, \tilde{q}_j(\x_N)]^\top$. From Eq.(<ref>), we have:

\begin{equation*}
\begin{split}
\nabla_{\bm{\theta}}(a_j) &= \sum_{k=1}^N \nabla_{\bm{\theta}}(\hth[\x_k]) \nabla_{\hth[\x_k]}a_j= \bm{U}^{(j)}\bm{q}_j \\
\nabla_{\bm{\theta}}(b_j) &= \sum_{k=1}^N \nabla_{\bm{\theta}}(\hth[\x_k]) \nabla_{\hth[\x_k]}b_j= - \bm{U}^{(j)}\bm{\tilde{q}}_j
% \nabla_{vec(\bm{H})}(a_i) &  = \sumxone \alpha  \exp(\alpha \cdot \fixm) \cdot \hth[\x_m]
\end{split}
\end{equation*}

Then the gradient evaluation can be done by :

\begin{equation*}
\begin{split}
\nabla_{\wi}\hat{R}_{\ell} &= \sum_{j=1}^{N_C} \big(\nabla_{\wi}(a_j)\big) \cdot (b_j) + (a_j) \cdot \big(\nabla_{\wi}(b_j)\big) \\
&= \alpha \bm{H} \left(\sum_{j=1}^{N_C} b_j \mathcal{I}_i \odot \hat{\bm{y}}^{(i),+}_{exp} \odot \bm{\partial}_{i,j} - a_j \mathcal{I}_{\backslash i} \odot \bm{D}^{(i)} \odot \hat{\bm{y}}^{(i),-}_{exp} \odot \bm{\partial}_{i,j} \right),\\
\nabla_{\bm{\theta}}\hat{R}_{\ell} &= \sum_{j=1}^{N_C} \big(\nabla_{\bm{\theta}}(a_j)\big) \cdot (b_j) + (a_j) \cdot\big(\nabla_{\bm{\theta}}(b_j)\big) \\
&= \sum_{j=1}^{N_C} \left[\bm{U}^{(j)}(b_j\bm{q}_j -a_j\bm{\tilde{q}}_j)\right].
\end{split}
\end{equation*}

From the compact forms shown above, the acceleration enjoys a  $O(NN_CT_{grad})$ complexity  instead of the original $O(N_C\sumi\suminj n_in_jT_{grad})$ time.

§.§ Hinge loss

Loss Evaluation. First we put down the hinge surrogate loss as:

\begin{equation*}
\hat{R}_{hinge} = \sumi\sumxone  \suminj \sumxtwo \ninj \cdot  \left(\alpha - \left(\fixm - \fixn\right)\right)_+.
\end{equation*}

The key of our acceleration is to notice that the terms are non-zero only if $\left(\fixm - \fixn\right) \le \alpha$. Moreover, for these non-zero terms $\max(x,0) =x$. This means that the hinge loss degenerates to an identity function for the activated nonzero terms, which enjoys efficient computation. So the key step in our algorithm is to find out the non-zero terms in an efficient manner.

Given a fixed class $i$ and an instance $\x_m \in \Ni$, we denote:

\[\mathcal{A}^{(i)}(\x_m) =\{\x_n \notin \Ni, \alpha > \fixm -\fixn \}.\]

With $\mathcal{A}^{(i)}(\x_m)$, one can reformulate $\hat{R}_{hinge}$ as:

\begin{equation*}
\begin{split}
\hat{R}_{hinge} &= \sumi\sumxone \left[\left(\suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}(\x_m) } \ninj\right) \cdot  \left(\alpha - \fixm \right) + \suminj\sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}(\x_m) } \ninj \cdot \fixn  \right],\\
& =  \sumi\sumxone \left[\delta^{(i)}(\x_m) \cdot (\alpha - \fii[\x_m])+ \Delta^{(i)}(\x_m)\right],
\end{split}
\end{equation*}

\[\delta^{(i)}(\x_m)= \suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}(\x_m) } \ninj, ~~ \Delta^{(i)}(\x_m) = \suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}(\x_m) }  \ninj \fixn. \]

According to this reformulation, once $\delta^{(i)}(\x)$ and $\Delta^{(i)}(\x)$ are all fixed, we can calculate the loss function within $O(N)$. So the efficiency bottleneck comes from the calculations of $\delta^{(i)}(\x)$ and $\Delta^{(i)}(\x)$.

Next we propose an efficient way to calculate  $\delta^{(i)}(\x_m), \Delta^{(i)}(\x_m), \mathcal{A}^{(i)}(\x_m)$.  To do so, given a specific class $i$, we first sort the relevant (resp. irrelevant) instances descendingly according to their scores $\fii$:

\begin{equation*}
\begin{split}
&\fii[\bm{x}^\downarrow_0] \ge  \fii[\bm{x}^\downarrow_1] \cdots, \ge \fii[\bm{x}^\downarrow_{n_i-1}],~~~~  \bm{x}^\downarrow_i \in \mathcal{N}_i,  \\
&\fii[\bm{\tilde{x}}^\downarrow_0] \ge  \fii[\bm{\tilde{x}}^\downarrow_1] \cdots, \ge \fii[\bm{\tilde{x}}^\downarrow_{N-n_i-1}],~~~~ \bm{\tilde{x}}^\downarrow_i \notin \mathcal{N}_i.
\end{split}
\end{equation*}

It immediately follows that:

\begin{equation*}
\mathcal{A}^{(i)}(\bm{x}^\downarrow_0) \subseteq \mathcal{A}^{(i)}(\bm{x}^\downarrow_1) \subseteq \cdots \subseteq \mathcal{A}^{(i)}(\bm{x}^\downarrow_{\ni-1}).
\end{equation*}

This allows us to find out all $\mathcal{A}^{(i)}(\bm{x}^\downarrow_k), k=0,1,\cdots,n_i-1,$ within a single pass of the whole dataset with an efficient dynamic programming.

Based on the construction of $\mathcal{A}^{(i)}_k = \mathcal{A}^{(i)}(\bm{x}^\downarrow_k)$, we provide the following recursive rules to obtain $\delta^{(i)}(\x)$ and $\Delta^{(i)}(\x)$:

\begin{equation*}
\begin{split}
&\delta^{(i)}(\x^\downarrow_{k+1}) = \delta^{(i)}(\x^\downarrow_{k}) +  \suminj \sum_{ \Nj \cap  \mathcal{A}^{(i)}_{k+1} \backslash  \mathcal{A}^{(i)}_k } \ninj, \\
&\Delta^{(i)}(\x^\downarrow_{k+1}) = \Delta^{(i)}(\x^\downarrow_{k}) +  \suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}_{k+1} \backslash  \mathcal{A}^{(i)}_k  } \ninj \fixn.
\end{split}
\end{equation*}

These recursive rules induce an efficient dynamic programming which only requires a single pass of the whole dataset. Putting all together, we then come to a $O(N_C\bar{N}T_{l})$ time complexity speed-up for hinge loss evaluation. An implementation of this idea is detailed in  Alg.<ref> and Alg.<ref>.

[1]
$\x^\downarrow_0,\cdots, \x^\downarrow_{\ni-1}, \bm{\tilde{x}}^\downarrow_0, \cdots, \bm{\tilde{x}}^\downarrow_{N-\ni-1}, \alpha$.
$p\gets0$ pointer for current positive instance
$q\gets 0$ pointer for current negative instance
$\mathcal{I}_{0:(\ni-1)}= {0}$.  The index set that satisfies $\mathcal{A}^{(i)}_j = \{\xneg{i}{k}\}_{k=1}^{\mathcal{I}_k} $
$p < \ni, q < N - \ni $
$\fii[\xpos{i}{p}] - \fii[\xneg{i}{q}] < \alpha$
$q+=1$ If the current pair is nonzero, check the next  negative instance
$\mathcal{I}_p  = \max(q-1,0)$  The last element of $\mathcal{A}^{(i)}_p$ is $\xneg{i}{q-1}$
$q = N - \ni$
$\mathcal{I}_p = \max(q-1,0)$ The last element of $\mathcal{A}^{(i)}_p$ is $\xneg{i}{N-\ni-1}$
$p < \ni$ If $\mathcal{A}^{(i)}_p$ includes all the negative instances then for all $\mathcal{A}^{(i)}_{p'} =\mathcal{A}^{(i)}_p$, $p' > p$
$\mathcal{I}_{(p+1):(\ni-1)} = \mathcal{I}_p$

[1]
$\bm{X}, \bm{Y},\alpha$.
$\texttt{loss} \gets 0$

Obtain $\xpos{i}{0},\cdots, \xpos{i}{\ni-1} $ based on $\fii$
Obtain $\xpos{i}{0},\cdots, \xpos{i}{N-\ni-1}$ based on $\fii$

$\fii_+ = [\fii[\xpos{i}{0}],\cdots,\fii[\xpos{i}{\ni-1}]]$ .
$\bm{D}^{(i)}  = \left[\dfrac{1}{\ni n_{y(\xneg{i}{0})}},\cdots, \dfrac{1}{\ni n_{y(\xneg{i}{N-1})}}\right]$

$t_0  \gets 0,~~ \delta^{(i)}_{\rm{offset}} \gets 0,~ \Delta^{(i)}_{\rm{offset}} \gets 0, ~~loc= 0 $

$\bm{\Delta}^{(i)}_{0:(\ni-1)} \gets {0},~~ \bm{\delta}^{(i)}_{0:(\ni-1)} \gets 0 $

$\mathcal{I} \gets$ ($\xpos{i}{0},\cdots, \xpos{i}{\ni},\xneg{i}{0},\cdots, \xneg{i}{N-\ni-1},\alpha$)

$k < \ni$

$\mathcal{I}_k \neq t_0 -1$ continue scanning when $\mathcal{A}^{(k)} \neq \mathcal{A}^{(k-1)} $

$t_1 \gets \mathcal{I}_k +1$  make sure that $\mathcal{A}^{(i)}_{k+1} \backslash \mathcal{A}^{(i)}_k = \{\xneg{i}{u}\}_{u=t_0}^{t_1 -1} $

${\delta}^{(i)}_k \gets \delta^{(i)}_{\rm{offset}} + \sum_{u=t_0}^{t_1-1} \bm{D}^{(i)}_{u}$ Recursion for $\delta^{(i)}(\xpos{i}{k})$

${\Delta}^{(i)}_k \gets \Delta^{(i)}_{\rm{offset}} + \sum_{u=t_0}^{t_1-1} \bm{D}^{(i)}_{u} \cdot \fii[\xneg{i}{k}]$ Recursion for $\Delta^{(i)}(\xpos{i}{k})$

$t_0 \gets t_1$ Update the initial element.

$ \delta^{(i)}_{\rm{offset}} \gets {\delta}^{(i)}_k, ~~ \Delta^{(i)}_{\rm{offset}} \gets {\Delta}^{(i)}_k$ Update the offsets.

$I_k \neq N-\ni -1$ Check if $\mathcal{A}^{(k)} = \mathcal{A}^{(k-1)} $  and  $\mathcal{A}^{(k)} \neq \mathcal{N}_{\backslash i}$

$\delta^{(i)}_k =\delta^{(i)}_{\rm{offset}}, ~~\Delta^{(i)}_k =\Delta^{(i)}_{\rm{offset}}  $ Copy the last updates

Stop the iteration when $\mathcal{A}^{(k)} = \mathcal{N}_{\backslash i}$ and $\mathcal{A}^{(k)} = \mathcal{A}^{(k-1)}$.

$k +=1$

$k < \ni$
$\bm{\delta}^{(i)}_{k:(\ni-1)} = \delta^{(i)}_{\rm{offset}}, ~~ \bm{\Delta}^{(i)}_{k:(\ni-1)} = \Delta^{(i)}_{\rm{offset}}$ Set  $\mathcal{A}^{(i)}_{x} = \mathcal{A}^{(i)}_{k-1}, ~ \forall x \ge k$.

$\texttt{loss} += (\alpha - \fii_+ )^\top\bm{\delta}^{(i)} + \bm{\Delta}^{(i)}\bm{1} $

Gradient Evaluation. Similar to the loss evaluation, we can provide an efficient acceleration method for the gradient evaluation as well. Based on a similar analysis, we have:

\begin{equation*}
\begin{split}
\nabla_{\bm{\Theta}}\hat{R}_{hinge} & = \sumi\sumxone \left[-\left(\suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}(\x_m) } \ninj\right) \cdot \nabla_{\bm{\Theta}}\fixm   + \suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}(\x_m) } \ninj \nabla_{\bm{\Theta}}\fixn \right]\\
&~~~~ =  \sumi\sumxone \left(-\delta^{(i)}(\x_m) \cdot \nabla_{\bm{\Theta}}\fixm + \Gamma^{(i)}(\x_m)\right)\\
\end{split}
\end{equation*}

\[\Gamma^{(i)}(\x_m) = \suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}(\x_m) }  \ninj  \nabla_{\bm{\Theta}}\fixn. \]

For any $\x \in \mathcal{S}$, and any class $j$, based on Eq.(<ref>)-Eq.(<ref>), we can calculate $\nabla_{\Theta}\fjj$ from:

\begin{equation*}
\begin{split}
&\nabla_{\wi} \fjj = \pfij[\x] \cdot \hth[\x], \\
&\nabla_{\hth[\x]} \fii = \bm{W}^\top \bm{\partial}_j(\x),\\
&\nabla_{\bm{\theta}} \fii = \nabla_{\bm{\theta}}\hth \bm{W}^\top \bm{\partial}_j(\x).
\end{split}
\end{equation*}

We can also adopt a dynamic programming scheme similar to the loss evaluation to speed it up. The first step is exactly the same: obtain $\bm{x}^\downarrow_{0}, \cdots, \bm{x}^\downarrow_{\ni-1}$ and $\bm{\tilde{x}}^\downarrow_{0}, \cdots, \bm{\tilde{x}}^\downarrow_{N-\ni-1}$ with the same method as the loss evaluation and  get $\mathcal{A}^{(i)}_k= \mathcal{A}^{(i)}(\x^\downarrow_k)$. Then, we have the following recursive expression for the new variable $\Gamma^{(i)}(\x^\downarrow_{k})$:

\begin{equation*}
\begin{split}
\Gamma^{(i)}(\x^\downarrow_{k+1}) = \Gamma^{(i)}(\x^\downarrow_{k}) +  \suminj \sum_{\x_n \in \Nj \cap \mathcal{A}^{(i)}_{k+1} \backslash  \mathcal{A}^{(i)}_k  } \ninj \nabla_{\bm{\Theta}}\fixn.
\end{split}
\end{equation*}

Now we can use a similar algorithm to evaluate the gradients, the details are omitted here due to its resemblance to Alg.<ref>.

§.§ Squared Loss

Loss Evaluation.
For each fixed class $i$, we construct an affinity matrix $\boldsymbol{Aff}^{(i)}$ such that

\begin{equation*}
\boldsymbol{Aff}^{(i)}_{m,n} =
\begin{cases}
\dfrac{1}{n_in_{y_m}}, & n \in \Ni, m \notin \Ni, \\
\dfrac{1}{n_in_{y_n}}, & m \in \Ni, n \notin \Ni, \\
0, & \text{Otherwise},
\end{cases}
\end{equation*}

which could be written in a matrix form,

\begin{equation*}
\boldsymbol{Aff}^{(i)} = \bm{D}^{(i)}({{\mathbf{1}}}-{{\mathbf{Y}}^{(i)}}){{\mathbf{Y}}^{(i)}}^{\top
}+{{\mathbf{Y}}^{(i)}}{{({{\mathbf{1}}}-{{\mathbf{Y}}^{(i)}})}^{\top }}\bm{D}^{(i)},
\end{equation*}

Then the empirical risk function under the squared surrogate loss could be reformulated as:

\begin{equation*}
\hat{R}_{sq}   = \sumi   \bm{\Delta}^{(i)^\top}_{sq}
\mathcal{L}^{(i)}\bm{\Delta}^{(i)}_{sq},
\end{equation*}

\begin{equation}
\bm{\Delta}^{(i)}_{sq} = \bm{Y}^{(i)} - \fii[\bm{X}], ~~\fii[\bm{X}] = [\fii[\x_1],\cdots,\fii[\x_N] ]^\top,
\end{equation}

and $\mathcal{L}^{(i)} = diag(\bm{Aff}^{(i)}\bm{1}) - \bm{Aff}^{(i)}$ is the graph Laplacian matrix associated with $\bm{Aff}^{(i)}$. Based on this reformulation, one can find that the structure of $\mathcal{L}^{(i)}$ provides an efficient factorization scheme to speed-up loss evaluation. To see this,  we have:

\begin{equation*}
\hat{R}_{sq}   = \sumi   \frac{1}{2}\bm{\Delta}^{(i)\top}_{sq} (\bm{\kappa}^{(i)}\odot\bm{\Delta}^{(i)}_{sq}) -{\Delta}^{(i)}_1\cdot {\Delta}^{(i)}_2,
\end{equation*}

\begin{equation*}
\begin{split}
&{\Delta}^{(i)}_2 = \Yit \bm{\Delta}^{(i)}_{sq} \\
&{\Delta}^{(i)}_1 = \bm{\Delta}^{(i)^\top}_{sq}\Di (\Yni)\\
&\bm{\kappa}^{(i)} = \ni \Di (\Yni) + \dfrac{N_C-1}{\ni} \Yi.
\end{split}
\end{equation*}

Obviously both terms in the equation above require only $O(N_CNT_l)$ time. We summarize this factorization scheme in Alg.<ref>.

[1]
$\bm{X}, \bm{Y},\alpha, \varphi(\cdot)$.
$\texttt{loss} \gets 0$

Obtain $\Di$

$\bm{\Delta}^{(i)} \gets (\boldsymbol{Y}^{(i)} - \fii[\bm{X}]) $

$\bm{\kappa}^{(i)} \gets \ni \Di (\Yni) + \dfrac{N_C-1}{\ni} \Yi$

${\Delta}^{(i)}_1 \gets \left(\bm{\Delta}^{(i)^\top}_{sq}(\Di \Yni)\right) $

${\Delta}^{(i)}_2 \gets \Yit \bm{\Delta}^{(i)}_{sq} $

$\texttt{loss} += \frac{1}{2}\bm{\Delta}^{(i)\top}_{sq} (\bm{\kappa}^{(i)}\odot\bm{\Delta}^{(i)}_{sq}) - {\Delta}^{(i)}_1\cdot {\Delta}^{(i)}_2$

Gradient Evaluation. From Alg.<ref>, Eq.(<ref>)-Eq.(<ref>) and the chain rule, we have:

\begin{equation*}
\nabla_{\bm{w}^{(i)}}\hat{R}_{sq}  = \sumi \frac{1}{2} \cdot \nabla_{\bm{\bm{w}}^{(i)}} \bm{\Delta}^{(i)\top}_{sq} (\bm{\kappa}^{(i)}\odot\bm{\Delta}^{(i)}_{sq})  - \nabla_{\bm{w}^{(i)}}{\Delta}^{(i)}_1\cdot {\Delta}^{(i)}_2
\end{equation*}

\begin{equation*}
\begin{split}
\frac{1}{2} \nabla_{\bm{w}^{(i)}} \bm{\Delta}^{(j)^\top }_{sq}(\bm{\kappa}^{(j)}\odot \bm{\Delta}^{(j)}_{sq}) &= \bm{H}(\bm{\Delta}^{(j)}_{sq} \odot \bm{\kappa}^{(j)}\odot \bm{\partial}_{i,j}   ),\\
\nabla_{\bm{w}^{(i)}}{\Delta}^{(i)}_1 {\Delta}^{(i)}_2 &= \bm{H}\left[\left({\Delta}^{(i)}_2 \cdot\Di(\Yni) + {\Delta}^{(i)}_1 \Yi  \right) \odot \bm
{\partial}_{i,j} \right],\\
\frac{1}{2} \nabla_{\bm{\theta}} \bm{\Delta}^{(j)^\top }_{sq}(\bm{\kappa}^{(j)}\odot \bm{\Delta}^{(j)}_{sq}) &= \bm{U}^{(j)} ( \kappa^{(j)} \odot \bm{\Delta}^{(j)}),\\
\nabla_{\bm{\theta}}{\Delta}^{(i)}_1 {\Delta}^{(i)}_2 &= \bm{U}^{(j)}\left[{\Delta}^{(i)}_2 \cdot\Di(\Yni) + {\Delta}^{(i)}_1 \Yi  \right],
\end{split}
\end{equation*}

Again this shows that the gradient evaluation could be done within $O(N_CNT_{grad})$ time.

§.§ Acceleration Scheme for general losses

Unfortunately, the lossless acceleration for general losses is impossible in general. In this subsection, following the spirit of [75], we provide a discussion on how to accelerate general loss functions approximately. However, we can, in turn, construct an approximation framework based on the Bernstein Polynomials. Note that the key difference between our work and [75] is that we do not need the minimax reformulation. Moreover, we also present a nice property of such approximations in terms of consistency.

First of all, we define the Berstein Polynomials as the following.

The Berstein Polynomials of degree $m$ of the function $\varphi:[0,1]\rightarrow \mathbb{R}$ are defined, for any $u \in [0,1]$, by

\begin{equation}
\mathbb{B}_m(\varphi, u) = \sum_{i=1}^m \varphi\left(\frac{k}{m}\right) \cdot \binom{m}{k}\cdot u^k \cdot (1-u)^{m-k} = \sum_{i=1}^m \binom{m}{k} \cdot \Delta^k\varphi(0)  \cdot u^k.
\end{equation}

where $ \Delta^k\varphi(0) = \sum_{j=0}^k(-1)^{k-j} \tbinom{k}{j} \varphi\left(\frac{j}{m}\right)$ is the forward difference operator on $\varphi$ at 0.

Note that the domain of the scoring functions $f^{(i)}$ are restricted to $[0,1]$, by choosing $\varphi(u) = \ell(2s-1)$, we have:

\begin{equation}
\begin{split}
\ell(\fixm -\fixn ) &\approx \mathbb{B}_{K}\left(\varphi, \frac{1+ \fixm - \fixn}{2}\right)\\
& = \sum_{k=0}^K \binom{m}{k} \Delta^k\varphi(0) \left(\varphi, \frac{1+ \fixm - \fixn}{2}\right)^k\\
& = \frac{1}{K+1} \sum_{k=0}^m f^{(i)}_k(\x_m) \cdot \tilde{f}^{(i)}_k(\x_n)
\end{split}
\end{equation}

\begin{equation*}
\begin{split}
& f^{(i)}_k(\x_m)  =\left(\frac{1}{2} + f^{(i)}(\x_m)\right)^k\\
& f^{(i)}_k(\x_n)  = \sum_{j=k}^m \binom{m}{j} \cdot \binom{j}{k} \cdot \frac{(m+1) \cdot \Delta^k \varphi(0)}{2^j} \cdot \left(\frac{1}{2} - \fixn\right)^{j-k}.
\end{split}
\end{equation*}

With the Bernstein Polynomials, we now construct generic acceleration methods for surrogate risk computation.

Acceleration for General Loss Calculation. Through the lens of the Bernstein polynomials, the loss function could be approximated by the following derivation:

\begin{equation*}
\begin{split}
\hat{R}_{\ell} &= \sumi\sumxone  \suminj \sumxtwo \ninj \cdot  \ell\left(\fixm - \fixn\right)\\
&\approx \sumi\sumxone  \suminj \sumxtwo \ninj \cdot \frac{1}{K+1} \sum_{k=0}^K f^{(i)}_k(\x_m) \cdot \tilde{f}^{(i)}_k(\x_n)\\
&= \sumi \frac{1}{K+1} \bm{e}_+^{(i)\top} \bm{e}_-^{(i)}\\
& \triangleq \hat{R}^K_{\ell}
\end{split}
\end{equation*}

\begin{equation*}
\begin{split}
\bm{e}_+^{(i)}  &= \left[\sumxone \frac{f^{(i)}_1(\x_m)}{n_i}, \cdots,  \sumxone \frac{f^{(i)}_{K}(\x_m)}{n_i} \right]^\top,\\
\bm{e}_-^{(i)}  &= \left[\suminj \sumxtwo \frac{\tilde{f}^{(i)}_1(\x_n)}{n_j}, \cdots,  \suminj \sumxtwo \frac{\tilde{f}^{(i)}_K(\x_n)}{n_j} \right]^\top.
\end{split}
\end{equation*}

Obviously, it only requires $O(K\cdot N_C \cdot N)$ time to finish the loss computation.

Acceleration for General Gradient Calculation. Similarly, the gradient calculation could be approximated by the following derivation:

\begin{equation*}
\begin{split}
\nabla \hat{R}^K_{\ell} &= \sumi\sumxone  \suminj \sumxtwo \ninj \cdot \nabla \ell\left(\fixm - \fixn\right)\\
&\approx \sumi\sumxone  \suminj \sumxtwo \ninj \cdot \frac{1}{K+1} \sum_{k=0}^K f^{(i)}_k(\x_m) \cdot \nabla \tilde{f}^{(i)}_k(\x_n)\\
&= \sumi \frac{1}{K+1}  (\nabla \bm{e}_+^{(i)})^\top \bm{e}_-^{(i)}  + \bm{e}_+^{(i)\top} (\nabla \bm{e}_-^{(i)} )
\end{split}
\end{equation*}

$\nabla \bm{e}_+^{(i)}$ and $\nabla \bm{e}_-^{(i)}$ could be obtained in a similar spirit to the calculation of the exponential loss. It thus  requires $O(K\cdot N_C \cdot N \cdot T_{grad})$ time to finish  the gradient computation.

Consistency of the Approximated Loss function Now, we proceed to present an elegant property of the approximated risk functions. Specifically, we show that $\hat{R}^K_\ell$
is, in itself, a consistent loss function if $\ell$ is consistent. To do this, we need the following theorem about the Bernstein polynomials.

If $f \in C^k[0,1]$, for some $k \ge 0$, then :

\begin{equation*}
m \le \frac{d^k(f(x))}{dx^k} \le M, ~\Rightarrow~ c_k \cdot m \le \frac{d^k(\mathbb{B}_K(f,x))}{dx^k} \le c_k \cdot M
\end{equation*}

Then the following corollary gives the final result.

For all surrogate loss function $\ell \in C^2[0,1]$,

\[\hat{R}_\ell ~\text{is}~ \mauc ~\text{consistent}~  \Rightarrow  \hat{R}^K_\ell ~\text{is}~ \mauc ~\text{consistent}~ \]

Again, by choosing $\varphi(u)= \ell(2s-1)$, we have $\varphi(u) \in C^2[0,1]$. The result follows directly from Thm.<ref>, and Thm.<ref>.

§.§ Summary and Concluding Remarks

Acceleration for three losses , where  $\bar{N} = \sumi \ni \log \ni + (N-\ni) \log (N-\ni)$

Algorithms        1lloss     1lgradient     1lrequirement

exp + acceleration         $O(N_C \cdot N \cdot T_\ell)$          $O(N_C \cdot N \cdot T_{grad})$     $\min_i \ni \gg 2$

squared + acceleration     $O(N_C \cdot N \cdot T_\ell)$         $O(N_C \cdot N \cdot T_{grad})$     $e^{\frac{1}{2} (N-\ni)} \gg  \ni \gg N - e^{\frac{1}{2}\ni}$

hinge + acceleration       $O(N_C\cdot \bar{N} \cdot  T_\ell)$          $O(N_C \cdot \bar{N} \cdot T_{grad})$     $\min_i \ni \gg 2$

general + acceleration       $O(K \cdot N_C\cdot N \cdot  T_\ell)$          $O( K \cdot N_C \cdot N \cdot T_{grad})$     $e^{\frac{1}{2} (N-\ni)} \gg  \ni \gg N - e^{\frac{1}{2}\ni}$

w/o  acceleration        $O(\sumi \suminj n_in_j\cdot T_\ell)$       $O(\sumi \suminj n_in_j\cdot T_{grad})$     $\backslash$

\begin{equation*}
\sumi \suminj n_in_j - N_C \cdot N =  \sumi \left[ n_i(N-\ni) -  (\ni + (N-\ni))  \right].
\end{equation*}

To ensure $N_C \cdot N < \sumi \suminj n_in_j$, one must let
\[n_i(N-\ni) >  (\ni + (N-\ni)),~~~\forall i. \]
Obviously, this requirement could be met when $\min_i \ni \gg 2$. Similarly, we have:

\begin{equation*}
\sumi \suminj n_in_j - N_C \cdot \bar{N} =  \sumi \left[ n_i(N-\ni) -  \ni\log(\ni) - (N-\ni)\log(N-\ni)  \right].
\end{equation*}

In this sense  $N_C \cdot \bar{N} < \sumi \suminj n_in_j$ could be satisfied if
\[\frac{1}{2} (N-\ni) >  \log(\ni),~~ \frac{1}{2} (\ni) >  \log(N - \ni), ~~ \forall i.\]
This means that

\[ \exp(\frac{1}{2} (N-\ni)) \gg  \ni \gg N - \exp(\frac{1}{2}\ni), ~~\forall i. \]

should be guaranteed to ensure a significant improvement. It is easy to see that all the requirements are essentially loose restricts on the data distribution which could be satisfied for the majority of real-world datasets.  As another remark, we do not provide a detailed calculation of $\nabla_{\bm{\theta}}\hth$, since it follows the chain rule and could be obtained from off-the-shelf toolboxes such as tensorflow and pytorch where auto differentiation is supported.  Moreover, our acceleration schemes are based either on changing the order of operations or on reformulating the original loss. Hence, when the model is implemented in such auto differentiation platforms, the gradient acceleration does not need to be explicitly implemented. One just needs to implement the accelerated loss evaluation to fix the computational graph, the gradient evaluation then follows the graph naturally.

§ EXPERIMENTS

§.§ Numerical Validations for the Acceleration Algorithms

Acceleration Ratio vs. Sample Scale

Setting. As a warm-up experiment, we first validate the effectiveness of our proposed speed-up methods detailed in Sec.<ref>. Note that our algorithms only concern loss and gradient evaluations, which do not depend on the optimization algorithms in question. Hence, to be fair, we will perform stand-alone running time tests where no optimization algorithms are involved. Following this spirit, our comparisons are based on the results from 30 repetitions of pure loss and gradient evaluations. To do this, we randomly generate a series of dataset $\bm{Z}_i = (\bm{X}_i, \bm{Y}_i), ~ i=1,2,\cdots,5$, where $\bm{X}_i \in \mathbb{R}^{N_k \times d}, \bm{Y}_i \in \mathbb{R}^{N_i \times N_C}$ are the input  feature matrix and the output one-hot label matrix. Specifically, we set $N_i = \{32,64,128,256,512,1024\},~ d = 100, ~ N_C = 5$. $\bm{X}_i$ is generated from the uniform distribution within $[0,1]$. Denote $\rho_i = \nicefrac{\ni}{N}$, then $\bm{Y}$ is generated such that $\rho_1 = 0.2, \rho_2 = 0.1, \rho_3= 0.2, \rho_4 = 0.4, \rho_5 = 0.1$. Moreover, we fix a linear scoring function $f(\cdot)$ with softmax output $f^{(i)}(\bm{x}) = \mathsf{softmax}(\bm{W}^{(i)}\bm{x})$, where the weight matrix $\bm{W} = [\bm{W}^{(1)},\cdots, \bm{W}^{(5)}]$ is generated in the same way as $\bm{X}$. Then we test the running time of the naive evaluation algorithm and our speed-up algorithms respectively over different $\bm{Z}_i$.

Results and Analysis. To show the efficiency improvements, we plot the mean of the acceleration ratio in Fig.<ref>, which is  defined as:

\begin{equation*}
\begin{split}
&\text{acceleration ratio} \\
&=\frac{\text{Running time of the naive method}}{ \text{Running time of the acceleration method}}.
\end{split}
\end{equation*}

over 30 repetitions against the scale of the datasets. We have the following two findings: (a) The proposed algorithms generate significant speed-up over all sample scales being tested.
They produce $10\sim100$x speed-up when the sample size remains as small as 32 while the result gradually climbs-up as the sample size enlarges and finally reaches  $10000$x speed-up for the squared and the exponential loss when the sample size becomes 1024.  This shows that the proposed algorithms could both work for mini-batch-based and full-batch-based optimization methods. (b) The curves suggest that the acceleration ratios are roughly scaled as $O(N)$, which is consistent with the complexity analysis shown in Tab.<ref>. To see this, for squared and exponential loss, we have:

\begin{equation*}
\begin{split}
\text{acceleration ratio}&\approx \frac{\sumi \suminj n_in_j}{N_C\cdot N }\\
&= \frac{\sumi \suminj \rho_i\cdot \rho_j}{N_C} \cdot N
\end{split}
\end{equation*}

Note that we keep $\rho_i$ and $N_C$ as constants in our experiment, this suggests that the acceleration ratio should be $O(N)$. For hinge loss, there are extra factors from $\log \ni$ and $\log(N-\ni)$. However, these factors mostly remain at a constant level considering that the number of samples being tested is not large. This is why we also observe an almost linear scale-up of the acceleration ratio of hinge loss. Moreover, for hinge loss, we see that the increase of the acceleration ratio becomes slower for the gradient evaluations when the number of samples surpasses 500. A proper reason for this phenomenon is that the evaluation algorithms for hinge loss are partially implemented by . For a large scale dataset, the contribution of a   implementation should be more significant for loss than for gradient. This is because that  the matrix operations in gradient evaluation could be accelerated by proper and compact use of  even without , while the loss evaluations, containing mostly elementary operations, enjoy a shaper speed-up from  .

§.§ Dataset Description

Basic Information of the Datasets

Dataset     1c$\#samples$     1c$\#classes$     1c$\#features$     1c$r_\chi$

Balance     $625$       $3 $        $4$         $5.88$

Dermatology     $357 $      $6$         $34$        $5.55$

Ecoli     $336 $      $8$         $7$         $71.50$

New-thyroid     $215$       $3$         $5$         $5.00$

Pageblocks     $548 $      $5$         $10$        $164.00$

SegmentImb     $749$       $7$         $18 $       $20.31$

Shuttle     $2,175 $     $5$         $9$         $853.00$

Svmguide2     $391$       $3$         $20$        $4.17$

Yeast     $1,484$      10        8        $92.60$

CIFAR-100-Imb     $23,350$     $100$     $2,048$     $50.00$

User-Imb     $24,400$     $12$     $21,527$     $20.00$

iNaturalList2017      $675,170$       $5,089$       $2,048$        $276.4$

$\ni$ for User-Imb

class     1lsample

F23-      $800$

F24-26     $400$

F27-28     $400$

F29-32     $800$

F33-42     $1,600$

F43+      $400$

M22-      $1,600$

M23-26     $8,000$

M27-28     $800$

M29-31     $1,600$

M32-38     $8,000$

M39+      $8,000$

The label distribution for CIFAR-100-Imb Dataset, where each cell in the table presents a specific $\ni$. The row title in the left shows the range of id in the row. The class ids are numbered in the same way as the original dataset.

11cnumber of samples in each class

$1\sim10$     [rgb] .984,  .851,  .82$100$     [rgb] .996,  .898,  .859$50$     [rgb] .918,  .62,  .604$360$     [rgb] 1,  .922,  .882$20$     [rgb] 1,  .922,  .88220     [rgb] .933,  .675,  .655$300$     [rgb] .906,  .565,  .553$420$     [rgb] 1,  .922,  .882$20$     [rgb] .984,  .851,  .82$100$     [rgb] .957,  .765,  .737$200$

$11\sim20$     [rgb] .984,  .851,  .82100     [rgb] .984,  .851,  .82$100$     [rgb] .859,  .404,  .404$600$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] .996,  .898,  .859$50$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] .984,  .851,  .82$100$     [rgb] .984,  .851,  .82$100$

$21\sim30$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] .859,  .404,  .404$600$     [rgb] .984,  .851,  .82$100$     [rgb] .996,  .898,  .859$50$     [rgb] .859,  .404,  .404$600$     [rgb] .984,  .851,  .82$100$     [rgb] 1,  .922,  .882$20$     [rgb] .957,  .765,  .737$200$     [rgb] 1,  .922,  .882$20$

$31\sim40$     [rgb] .859,  .404,  .404$600$     [rgb] .984,  .851,  .82$100$     [rgb] .984,  .851,  .82$100$     [rgb] .933,  .675,  .655$300$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] 1,  .922,  .882$20$     [rgb] .859,  .404,  .404$600$     [rgb] .984,  .851,  .82$100$     [rgb] .859,  .404,  .404$600$

$41\sim50$     [rgb] 1,  .922,  .882$20$     [rgb] .859,  .404,  .404$600$     [rgb] .984,  .851,  .82$100$     [rgb] .933,  .675,  .655$300$     [rgb] 1,  .922,  .882$20$     [rgb] .933,  .675,  .655$300$     [rgb] .906,  .565,  .553$420$     [rgb] .859,  .404,  .404$600$     [rgb] .89,  .514,  .506$480$     [rgb] .984,  .851,  .82$100$

$51\sim60$     [rgb] 1,  .922,  .882$20$     [rgb] 1,  .922,  .882$20$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] 1,  .922,  .882$20$     [rgb] .906,  .565,  .553$420$     [rgb] .859,  .404,  .404$600$     [rgb] .996,  .898,  .859$50$     [rgb] 1,  .922,  .882$20$     [rgb] .984,  .851,  .82$100$

$61\sim70$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] .957,  .765,  .737$200$     [rgb] .918,  .62,  .604$360$     [rgb] .984,  .851,  .82$100$     [rgb] .984,  .851,  .82$100$     [rgb] .984,  .851,  .82$100$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] .996,  .898,  .859$50$

$71\sim80$     [rgb] .996,  .898,  .859$50$     [rgb] .969,  .808,  .776$150$     [rgb] .859,  .404,  .404$600$     [rgb] .996,  .898,  .859$50$     [rgb] .933,  .675,  .655$300$     [rgb] 1,  .922,  .882$20$     [rgb] .969,  .808,  .776$150$     [rgb] 1,  .922,  .882$20$     [rgb] 1,  .922,  .882$20$     [rgb] .984,  .851,  .82$100$

$81\sim90$     [rgb] 1,  .922,  .882$20$     [rgb] .89,  .514,  .506$480$     [rgb] .996,  .898,  .859$50$     [rgb] .996,  .898,  .859$50$     [rgb] .984,  .851,  .82$100$     [rgb] 1,  .922,  .882$20$     [rgb] .996,  .898,  .859$50$     [rgb] 1,  .922,  .88220     [rgb] .933,  .675,  .655$300$     [rgb] .996,  .898,  .859$50$

$91\sim100$     [rgb] .996,  .898,  .859$50$     [rgb] .918,  .62,  .604$360$     [rgb] .984,  .851,  .82$100$     [rgb] .969,  .808,  .776$150$     [rgb] 1,  .922,  .882$20$     [rgb] .984,  .851,  .82$100$     [rgb] .984,  .851,  .82$100$     [rgb] 1,  .922,  .882$20$     [rgb] .984,  .851,  .82$100$     [rgb] .996,  .898,  .859$50$

Here, we provide a more detailed description for traditional datasets from LIBSVM and KEEL.

(a)  LIBSVM Datasets.    <https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/>

* Abalone$\star$. The task of this dataset is to predict the age of abalone from physical measurements. The features include  basic information such as the gender, length, height of a given subject. To construct a multi-class problem from this dataset. We regard each possible age as a class. On top of this, we  merge the first three classes, and we also merge  all the classes greater than 20.

* Shuttle. The shuttle dataset contains 9 features all of which are numerical. The first one being time. The last column is the class which has been coded as follows: 1 Rad Flow,,2 Fpv Close,3 Fpv Open,4 High,5 Bypass,6 Bpv Close,7 Bpv Open.

* Svmguide-2. [34] released this dataset when the authors are providing a guidance for the  library.  This dataset comes from a bacteria protein subcellular localization dataset which was proposed in [26].

(b) KEEL Datasets.   <http://www.keel.es/>

* Balance. This data set was generated to model psychological experimental results. Each example is classified as having the balance scale tip to the right, tip to the left, or be balanced. The attributes are the left weight, the left distance, the right weight, and the right distance.

* Dermatology. The differential diagnosis of erythemato-squamous diseases is a real problem in dermatology. They all share the clinical features of erythema and scaling, with few differences. The diseases in this group are psoriasis, seborrheic dermatitis, lichen planus, pityriasis rosea, chronic dermatitis, and pityriasis rubra pilaris. Usually a biopsy is necessary for the diagnosis, but, unfortunately, these diseases share many histopathological features as well. Another difficulty for the differential diagnosis is that a disease may show the features of another disease at the beginning stage and may have the characteristic features at the following stages. Patients were first evaluated clinically with 12 features. Afterwards, skin samples were taken for the evaluation of 22 histopathological features. The values of the histopathological features are determined by an analysis of the samples under a microscope. In the dataset constructed for this domain, the family history feature has the value 1 if any of these diseases has been observed in the family, and 0 otherwise. The age feature simply represents the age of the patient. Every other feature (clinical and histopathological) was given a degree in the range of 0 to 3. Here, 0 indicates that the feature was not presented, 3 indicates the largest amount possible, and 1, 2 indicate the relative intermediate values.

* Ecoli. The task of this dataset is to predict protein localization sites, where the features are given as a series of scores evaluated by standard detection methods.

* Glass. A Glass type identification dataset with 9 features.

* New Thyroid. This is a Thyroid Disease (New Thyroid) dataset with three classes: normal hyper and hypo.

* Page Blocks. The task of this dataset is to classify all the blocks of the page layout of a document that has been detected by a segmentation process, where each of the observed blocks has 10 features describing its basic information.

* Wine. A Wine classification dataset where the model should classify a given data point to one of the types of wines based on 13 dimensions of features.

(c) Other Datasets:

(1) CIFAR-100-Imb. We sampled an imbalanced version of the CIFAR-100 [<https://www.cs.toronto.edu/ kriz/cifar.html>] dataset, which originally contains 100 image classes each with 600 instances.  The 100 classes are encoded as $1,\cdots 100$. For each class $i$, we randomly sampled $n_i$ instances shown in Tab.<ref> to gain an imbalanced version of the dataset.

(2) User-Imb. The original dataset is collected from TalkingData, a famous third-party mobile data platform from China, which predicts mobile users’ demographic characteristics based on their app usage records. The dataset is collected for the Kaggle Competition named Talking Data Mobile User Demographics. [<https://www.kaggle.com/c/talkingdata-mobile-user-demographics/data>] The raw features include logged events, app attributes, and device information. There are 12 target classes 'F23-', 'F24-26','F27-28','F29-32', 'F33-42', 'F43+', 'M22-', 'M23-26', 'M27-28', 'M29-31', 'M32-38', 'M39+', which describe the demographics (gender and age) of users. In our experiments, we sample an imbalanced subset of the original dataset to leverage a class-skewed dataset. The number of instances in each class after resampling is listed as Tab.<ref>.

iNaturalist2017. iNaturalist Challenge 2017 dataset[https://www.kaggle.com/c/inaturalist-challenge-at-fgvc-2017] is a large-scale image classification benchmark with 675,170 images covering 5,089 different species of plants and animals. We split the dataset into the training set, validation set, and test set at a ratio of 0.7:0.15:0.15. Since directly training deep models in such a large-scale dataset is time-consuming, we instead generate 2048-d features with a ResNet-50 model pre-trained on ImageNet for each image and train models with three fully-connected layers for all methods. We utilize Adam optimizer to train the models, with an initial learning rate of $10^{-5}$. To ensure all categories are covered in a mini-batch, the batch size is set to 8196. Other hyperparameters are the same as those in the CIFAR-100-Imb dataset.

§.§ Implementation Details

Infrastructure. All the experiments are carried out on a ubuntu 16.04.6 server  equipped with  Intel(R) Xeon(R) CPU E5-2620 v4 cpu and a TITAN RTX GPU. The codes are implemented via , the basic dependencies are:  (v-1.1.0),  (v-0.21.3),  (v-1.16.2). For traditional datasets, we implement our proposed algorithms with the help of the  and . For hinge loss, we use Cython to accelerate the dynamic programming algorithm. For the deep learning datasets, our proposed algorithms are implemented with .

Evaluation Metric. Given a trained scoring function $f = (f^{(1)},\cdots, f^{(N_C)})$, all the forthcoming results are evaluated with reward reversion of MAUC, where we denote it as $\mathsf{MAUC}^\uparrow$:

\begin{equation*}
\mathsf{MAUC}^\uparrow  = \frac{1}{N_C \cdot (N_C - 1)} \cdot \sumi\suminj \frac{\left|\left\{(\x_1,\x_2): \x_1 \in \mathcal{N}_i, ~\x_2 \in \mathcal{N}_j, f^{(i)}(\x_1) > f^{(i)}(\x_2) \right\}\right|}{\ni\nj}
\end{equation*}

in this subsection.

Traditional Datasets. For all the experiments, hyper-parameters are tuned based on the training and validation set while the performances are evaluated over a test set, where the training, valid, and test set accounts for $80\%,~ 10\%,~ 10\%$ of the original dataset, respectively. To remain the label distribution of the overall dataset, the dataset splits are generated with a stratified sampling strategy with respect to classes.  The experiments are done with 15 repetitions for each involved algorithm. Since all the datasets fall in this class contains simple features, we use a linear model composited with a softmax transformation as the scoring function. More formally, given an instance $\x$, we have $f(\x)= \mathsf{softmax}(\bm{W}\bm{x})$, where $\bm{W} = [\bm{\omega}^{(1)}, \cdots, \bm{\omega}^{(N_C)}] \in \mathbb{R}^{d \times N_C}$ is the weight of the linear function. For the sampling-based competitors, the corresponding sampling algorithm is first performed on the dataset, then a scoring function is trained based on the multiclass cross-entropy loss. For LR, the scoring function is directly trained based on the multiclass cross-entropy loss without sampling. For our proposed algorithms, we directly wrap the $\mauc$ surrogate losses on the scoring function $f$ and perform the training process without any simpling procedure. The hyper-parameters we adopted to produce the performance of our algorithms are shown in Tab.<ref>.

Best parameters for ($\lambda, \alpha$) over traditonal datasets

Dataset       Ours1     Ours2     Ours3

balance     $(1e\text{-}4,0.9)$     $(1e\text{-}4,0.9)$     $(1e\text{-}4,0.7)$

dermatology     $(1e\text{-}4,0.9)$     $(1e\text{-}4,0.9)$     $(1e\text{-}4,0.3)$

ecoli     $(6e\text{-}4,0.6)$     $(4e\text{-}4,0.9)$     $(1e\text{-}4,0.2)$

new-thyroid     $(1e\text{-}4,0.9)$     $(1e\text{-}4,0.5)$     $(1e\text{-}4,0.9)$

pageblocks     $(6e\text{-}4,0.8)$     $(2e\text{-}4,0.9)$     $(6e\text{-}4,0.5)$

segmentImb     $(2e\text{-}4,0.9)$     $(4e\text{-}4,0.9)$     $(1e\text{-}4,0.3)$

shuttle     $(2e\text{-}4,0.8)$     $(1e\text{-}4,0.7)$     $(1e\text{-}4,0.5)$

svmguide2     $(1e\text{-}4,0.9)$     $(1e\text{-}4,0.9)$     $(2e\text{-}4,0.4)$

yeast     $(6e\text{-}4,0.3)$     $(9e\text{-}3,0.1)$     $(1e\text{-}4,0.2)$

The Common Architecture for CIFAR-100-Imb Dataset

layers     1l$n_{units}$     activation      1l$BN$

$fc_1$      $1,024$     relu

$fc_2$      $256$     relu

$output$     $100$     softmax

The Common Architecture for  User-Imb Dataset

layers     1l$n_{units}$     activation      1l$BN$

$fc_1$      $128$     relu

$fc_2$      $64$     relu

$output$     $12$     softmax

Deep Learning Datasets. For all the experiments, hyper-parameters are tuned based on the training and validation set while the performances are evaluated over a test set, where the training, valid, and test set accounts for $80\%,~ 10\%,~ 10\%$ of the original dataset, respectively. To remain the label distribution of the overall dataset, the dataset splits are generated with a stratified sampling strategy with respect to classes. For these two datasets, all the models are constructed with a deep neural network. The scoring functions share a common form as $f(\x) = \mathsf{softmax}(fc_2(fc_1(\x)))$, where $fc_1, fc_2$ are fully-connected layers. For CIFAR-100-Imb, we adopt the ResNet-50 pre-trained features from  after average pooling as the input for each method. For User-Imb, the models are trained from scratch. The architecture we use for  CIFAR-100-Imb and User-Imb are shown in Tab.<ref> and Tab.<ref>, respectively. For the sampling-based competitors, the corresponding sampling algorithm is first performed on the dataset, then a scoring function is trained based on the multiclass cross-entropy loss together with a three-layered deep neural network. For LR, the scoring function is directly trained based on the multiclass cross-entropy loss and the neural net without sampling. For our proposed algorithms, we directly wrap the $\mauc$ surrogate losses on the neural net $f$ and perform the training process without any simpling procedure. The hyper-parameters we adopted to produce the performance of  our algorithms are shown in Tab.<ref> and Tab.<ref>, respectively for CIFAR-100-Imb and User-Imb.

Hyperparameters for CIFAR-100-Imb

batch size     lr        weight decay     lr decay     epoch     gamma     #epochs before lr decay

Ours1     $1000$      $0.0012 $   $ 0.000005$    $0.97$      $50.00$        $1.00$         $5.00$

Ours2     $1000$      $0.001$     $0.000001 $    $0.99$      $48.00$        $4.00$         $5.00$

Ours3     $1000$      $0.001$     $0.00005$      $0.99$      $50.00$        $4.00$         $3.00$

Hyperparameters for User-Imb

batch size     lr        weight decay     lr decay     gamma     #epochs before lr decay

Ours1     $32$        $0.005$    $ .0001$     $0.97$      $0.5$         $1.00$

Ours2     $32$        $0.005$    $ .0001$     $0.97$      $2.0$         $1.00$

Ours3     $32$        $0.005$    $ .0001$     $0.97$      $2.0$         $1.00$

§.§ Running Time Comparison for Deep Learning Datasets.

To validate the effectiveness of our acceleration method, we report the average running time per epoch in Tab.<ref> here for all  three deep learning datasets. Accelerated refers to our proposed method. For the Selected method, the sample indexes of different classes are cached in different tensors. Naive refers to a straightforward implementation.

Running Time Comparison for Different Implementation Schemes, - Refers to the Fact that the Running Time is Longer than 12 h.

loss      implementation     1cCIFAR-100     1cUser     1ciNaturalist

3[1]*Square     Accelerated     0.95      8.59      121.8347

Selected     3111.1     89.35     -

Naïve     51747.03     360.36     -

3[1]*EXP     Accelerated     0.97      9.41      117.4387

Selected     2392.55     72.31     -

Naïve     56138.42     352.77     -

3[2]*Hinge     Accelerated     0.83      8.42      115.4508

Selected     2703.15     75.15     -

Naïve     51302.48     352.45     -