text:
\section{Introduction}

Ensemble~\cite{dietterich2000ensemble,hansen1990neural,polikar2006ensemble,krogh1994neural,perrone1992networks,opitz1999popular,perrone1992networks,rokach2010ensemble,zhou2002ensembling} (aka\xspace. model\xspace averaging)\xspace is\xspace one\xspace of\xspace the\xspace oldest\xspace and\xspace most\xspace powerful\xspace techniques\xspace in\xspace practice\xspace to\xspace improve\xspace the\xspace performance\xspace of\xspace deep\xspace learning\xspace models\xspace. By\xspace simply\xspace averaging\xspace the\xspace output\xspace of\xspace a\xspace few\xspace independently\xspace trained\xspace neural\xspace networks\xspace over\xspace the\xspace same\xspace training\xspace data\xspace set\xspace, it\xspace can\xspace significantly\xspace boost\xspace the\xspace prediction\xspace accuracy\xspace over\xspace the\xspace test\xspace set\xspace comparing\xspace to\xspace each\xspace individual\xspace model\xspace. Moreover\xspace, it\xspace is\xspace also\xspace known\xspace that\xspace such\xspace performance\xspace boost\xspace holds\xspace \emph{even\xspace when\xspace} all\xspace the\xspace neural\xspace networks\xspace have\xspace the\xspace same\xspace architecture\xspace and\xspace are\xspace trained\xspace using\xspace the\xspace same\xspace training\xspace algorithm\xspace over\xspace the\xspace same\xspace training\xspace data\xspace set\xspace. The\xspace only\xspace difference\xspace is\xspace the\xspace randomness\xspace used\xspace to\xspace initialize\xspace these\xspace neural\xspace networks\xspace and\xspace/or\xspace the\xspace randomness\xspace during\xspace training\xspace (e\xspace.g\xspace. if\xspace stochastic\xspace gradient\xspace descent\xspace is\xspace used)\xspace.  For\xspace example\xspace, on\xspace the\xspace standard\xspace CIFAR\xspace-100 data\xspace set\xspace, averaging\xspace the\xspace output\xspace of\xspace ten\xspace independently\xspace trained\xspace ResNet\xspace-34 can\xspace easily\xspace offer\xspace a\xspace $5\%$\xspace  improvement\xspace in\xspace terms\xspace of\xspace test\xspace accuracy\xspace.  Later\xspace, it\xspace is\xspace also\xspace discovered\xspace in\xspace the\xspace seminal\xspace work~\cite{hinton2015distilling} that\xspace such\xspace superior\xspace test\xspace-time\xspace performance\xspace of\xspace the\xspace ensemble\xspace can\xspace be\xspace transferred\xspace into\xspace a\xspace single\xspace model\xspace (of\xspace the\xspace same\xspace size\xspace as\xspace the\xspace individual\xspace models)\xspace using\xspace a\xspace technique\xspace called\xspace \emph{knowledge\xspace distillation\xspace}: that\xspace is\xspace, simply\xspace train\xspace a\xspace single\xspace model\xspace to\xspace match\xspace the\xspace output\xspace of\xspace the\xspace ensemble\xspace as\xspace opposite\xspace to\xspace the\xspace true\xspace data\xspace labels\xspace, over\xspace the\xspace same\xspace training\xspace data\xspace set\xspace.

On\xspace the\xspace theory\xspace side\xspace, there\xspace are\xspace quite\xspace a\xspace few\xspace works\xspace focusing\xspace on\xspace understanding\xspace the\xspace superior\xspace performance\xspace of\xspace ensemble\xspace from\xspace a\xspace principled\xspace perspective~\cite{rokach2008data,friedman2001greedy,freund1997decision,rodriguez2006rotation,kolter2007dynamic,freund1999short,freedman1981bootstrapping,bolon2019ensembles,kittler1998combining,friedman2000additive,ho1998random,kuncheva2014combining,schapire1998boosting,kohavi1997wrappers,rodriguez2006rotation,galar2011review,breiman1996bagging}. However\xspace, most\xspace of\xspace these\xspace works\xspace only\xspace apply\xspace to\xspace (1). Boosting\xspace: where\xspace the\xspace coefficients\xspace associated\xspace with\xspace the\xspace combinations\xspace of\xspace the\xspace single\xspace models\xspace are\xspace actually\xspace trained\xspace, instead\xspace of\xspace simply\xspace taking\xspace average\xspace. (2). Bootstrap\xspace aggregation\xspace: where\xspace the\xspace training\xspace data\xspace are\xspace different\xspace for\xspace each\xspace single\xspace model\xspace. (3). Ensemble\xspace of\xspace models\xspace of\xspace different\xspace types\xspace and\xspace architectures\xspace. (4). Ensemble\xspace of\xspace random\xspace features\xspace or\xspace decision\xspace trees\xspace.

To\xspace the\xspace best\xspace of\xspace our\xspace knowledge\xspace, \emph{non\xspace of\xspace these\xspace theoretical\xspace works\xspace} apply\xspace to\xspace the\xspace setting\xspace of\xspace when\xspace we\xspace just\xspace average\xspace the\xspace output\xspace of\xspace the\xspace learners\xspace, which\xspace are\xspace neural\xspace networks\xspace with\xspace the\xspace \emph{same\xspace} architecture\xspace and\xspace are\xspace trained\xspace by\xspace stochastic\xspace gradient\xspace descent\xspace over\xspace the\xspace \emph{same\xspace} training\xspace data\xspace set\xspace. Nor\xspace can\xspace they\xspace explain\xspace why\xspace the\xspace superior\xspace performance\xspace of\xspace ensemble\xspace can\xspace also\xspace be\xspace distilled\xspace into\xspace a\xspace single\xspace model\xspace using\xspace knowledge\xspace distillation~\cite{hinton2015distilling,zhu2018knowledge,cui2017knowledge,fukuda2017efficient,freitag2017ensemble,chebotar2016distilling,liu2019improving}. In\xspace fact\xspace, as\xspace we\xspace shall\xspace argue\xspace in\xspace our\xspace paper\xspace, some\xspace traditional\xspace views\xspace of\xspace ensemble\xspace, such\xspace as\xspace ensemble\xspace can\xspace enlarge\xspace the\xspace feature\xspace space\xspace in\xspace random\xspace feature\xspace mappings\xspace, \emph{cannot\xspace} explain\xspace knowledge\xspace distillation\xspace at\xspace all\xspace.

Motivate\xspace by\xspace the\xspace gap\xspace between\xspace theory\xspace and\xspace practice\xspace in\xspace {ensemble\xspace and\xspace knowledge\xspace distillation\xspace in\xspace deep\xspace learning\xspace}, in\xspace this\xspace work\xspace, \textbf{we focus on the simplest, and the most practical ensemble setting in deep learning where we merely taking an unweighted average the output of a few independently trained neural networks}, and\xspace we\xspace would\xspace like\xspace to\xspace formally\xspace study\xspace the\xspace following\xspace question\xspace for\xspace \textbf{multi-class classification problems}:

\begin{mdframed}[frametitle={\colorbox{white}{\space Our theoretical questions:\space}},
frametitleaboveskip=-\ht\strutbox,
frametitlealignment=\center
]
How\xspace does\xspace ensemble\xspace improve\xspace the\xspace test\xspace-time\xspace performance\xspace in\xspace deep\xspace learning\xspace when\xspace we\xspace simply\xspace average\xspace over\xspace a\xspace few\xspace independently\xspace trained\xspace neural\xspace networks\xspace? -- Especially\xspace when\xspace all\xspace the\xspace neural\xspace networks\xspace have\xspace the\xspace same\xspace architecture\xspace, are\xspace trained\xspace over\xspace the\xspace same\xspace data\xspace set\xspace using\xspace the\xspace same\xspace standard\xspace training\xspace algorithm\xspace (i\xspace.e\xspace. stochastic\xspace gradient\xspace descent\xspace with\xspace the\xspace same\xspace learning\xspace rate\xspace and\xspace sample\xspace regularization)\xspace, and\xspace even\xspace when\xspace all\xspace single\xspace models\xspace already\xspace have\xspace \emph{$100 \%$\xspace  training\xspace accuracy\xspace}? How\xspace can\xspace such\xspace superior\xspace test\xspace-time\xspace performance\xspace of\xspace ensemble\xspace be\xspace later\xspace ``distilled\xspace'' into\xspace a\xspace single\xspace neural\xspace network\xspace of\xspace the\xspace same\xspace architecture\xspace, simply\xspace by\xspace training\xspace the\xspace single\xspace model\xspace to\xspace match\xspace the\xspace output\xspace of\xspace the\xspace ensemble\xspace over\xspace the\xspace same\xspace training\xspace data\xspace set\xspace?
\end{mdframed}

\subsection{Our Theoretical Results at a High Level}

In\xspace this\xspace work\xspace, we\xspace make\xspace (to\xspace the\xspace best\xspace of\xspace our\xspace knowledge)\xspace a\xspace first\xspace step\xspace towards\xspace answering\xspace these\xspace questions\xspace in\xspace deep\xspace learning\xspace. On\xspace the\xspace \emph{theory\xspace side\xspace}, we\xspace prove\xspace that\xspace over\xspace certain\xspace multi\xspace-class\xspace classification\xspace tasks\xspace with\xspace a\xspace special\xspace structure\xspace that\xspace we\xspace shall\xspace refer\xspace to\xspace as\xspace \textbf{multi-view}, with\xspace a\xspace training\xspace set\xspace $\motosilurante{Z}$\xspace  consisting\xspace of\xspace $N$\xspace  i\xspace.i\xspace.d\xspace. samples\xspace from\xspace some\xspace unknown\xspace distribution\xspace $\mathcal{D}$\xspace , for\xspace certain\xspace two\xspace-layer\xspace convolution\xspace network\xspace $f$\xspace  with\xspace (smoothed\xspace-)ReLU\xspace activation\xspace:
\begin{itemize}
\item (Single\xspace model\xspace has\xspace bad\xspace test\xspace accuracy)\xspace: there\xspace is\xspace a\xspace value\xspace $\mu > 0$\xspace  such\xspace that\xspace when\xspace a\xspace single\xspace model\xspace $f$\xspace  is\xspace trained\xspace over\xspace $\motosilurante{Z}$\xspace  using\xspace the\xspace cross\xspace-entropy\xspace loss\xspace, via\xspace gradient\xspace descent\xspace (GD)\xspace starting\xspace from\xspace random\xspace Gaussian\xspace initialization\xspace, the\xspace model\xspace can\xspace reach\xspace zero\xspace training\xspace error\xspace \emph{efficiently\xspace}. However\xspace, w\xspace.h\xspace.p\xspace. the\xspace prediction\xspace (classification)\xspace error\xspace of\xspace $f$\xspace  over\xspace $\mathcal{D}$\xspace  is\xspace between\xspace $0.49 \mu$\xspace  and\xspace $0.51 \mu$\xspace .
\item (Ensemble\xspace provably\xspace improves\xspace test\xspace accuracy)\xspace: let\xspace $f_1, f_2, \cdots, f_{L}$\xspace  be\xspace $L$\xspace  independently\xspace trained\xspace single\xspace models\xspace as\xspace above\xspace with\xspace $L = \tilde{\Omega}(1)$\xspace , then\xspace w\xspace.h\xspace.p\xspace. $F = \sum_{\ell} f_{\ell}$\xspace  will\xspace have\xspace prediction\xspace error\xspace at\xspace most\xspace $0.01 \mu$\xspace  over\xspace $\mathcal{D}$\xspace .
\item  (Ensemble\xspace can\xspace be\xspace distilled\xspace into\xspace a\xspace single\xspace model)\xspace: if\xspace we\xspace further\xspace train\xspace (using\xspace GD\xspace from\xspace random\xspace initialization)\xspace another\xspace network\xspace $f_0$\xspace  to\xspace match\xspace the\xspace output\xspace of\xspace $F$\xspace  merely\xspace over\xspace the\xspace same\xspace training\xspace data\xspace set\xspace $\motosilurante{Z}$\xspace , then\xspace $f_0$\xspace  can\xspace be\xspace trained\xspace \emph{efficiently\xspace} and\xspace w\xspace.h\xspace.p\xspace. $f_0$\xspace  will\xspace have\xspace prediction\xspace error\xspace at\xspace most\xspace $0.01 \mu$\xspace  over\xspace $\mathcal{D}$\xspace  as\xspace well\xspace.
\item  (\emph{Self\xspace-distillation\xspace}~\cite{furlanello2018born,mobahi2020self} also\xspace improves\xspace test\xspace accuracy\xspace, see~\sbollisce{fig:cifar}): if\xspace we\xspace further\xspace train\xspace (using\xspace GD\xspace from\xspace random\xspace initialization)\xspace another\xspace network\xspace $f'$\xspace  to\xspace match\xspace the\xspace output\xspace of\xspace \emph{a\xspace single\xspace model\xspace} $f_1$\xspace  merely\xspace over\xspace the\xspace same\xspace training\xspace data\xspace set\xspace $\motosilurante{Z}$\xspace , then\xspace  $f'$\xspace  can\xspace be\xspace trained\xspace \emph{efficiently\xspace} and\xspace w\xspace.h\xspace.p\xspace. $f'$\xspace  will\xspace have\xspace prediction\xspace error\xspace at\xspace most\xspace $\leq 0.26 \mu$\xspace  over\xspace $\mathcal{D}$\xspace . The\xspace main\xspace idea\xspace is\xspace that\xspace self\xspace-distillation\xspace is\xspace performing\xspace ``\emph{implicit\xspace ensemble\xspace + knowledge\xspace distillation\xspace}'', as\xspace we\xspace shall\xspace argue\xspace in\xspace Section~\ref{sec:self}.
\end{itemize}

\noindent
Thus\xspace, on\xspace the\xspace theory\xspace side\xspace, we\xspace make\xspace a\xspace step\xspace towards\xspace understanding\xspace ensemble\xspace and\xspace knowledge\xspace distillation\xspace in\xspace deep\xspace learning\xspace both\xspace computationally\xspace (training\xspace efficiency)\xspace and\xspace statistically\xspace (generalization\xspace error)\xspace.

\subsection{Our Empirical Results at a High Level}

On\xspace the\xspace \emph{empirical\xspace side\xspace}, to\xspace further\xspace justify\xspace our\xspace approach\xspace studying\xspace ensemble\xspace and\xspace knowledge\xspace distillation\xspace in\xspace {deep\xspace learning\xspace}, we\xspace show\xspace:

\begin{figure}[t!]
\centering
\vspace{-5mm}
{\includegraphics[page=2,trim={25mm 115mm 25mm 25mm},clip,width=0.9\linewidth]{ensemble-exp}}
\caption{Comparing\xspace the\xspace performances\xspace of\xspace (1) training\xspace 10 independent\xspace single\xspace models\xspace $f_1,\dots,f_{10}$\xspace , (2) their\xspace ensemble\xspace, (3) training\xspace $f_1+\cdots+f_{10}$\xspace  directly\xspace, (4) knowledge\xspace distillation\xspace of\xspace the\xspace ensemble\xspace into\xspace a\xspace single\xspace model\xspace, and\xspace (5) training\xspace a\xspace single\xspace model\xspace using\xspace self\xspace-distillation\xspace.
\newline
(NTK\xspace' = the\xspace original\xspace finite\xspace-width\xspace neural\xspace network\xspace first\xspace-order\xspace approximation~\cite{als18dnn}, NTK\xspace = the\xspace more\xspace popular\xspace variant\xspace where\xspace for\xspace each\xspace output\xspace label\xspace one\xspace learns\xspace a\xspace different\xspace linear\xspace function\xspace over\xspace the\xspace NTK\xspace features\xspace (e\xspace.g\xspace. \cite{arora2019exact}), and\xspace GP\xspace = training\xspace only\xspace the\xspace last\xspace layer\xspace of\xspace a\xspace finite\xspace-width\xspace random\xspace neural\xspace network~\cite{daniely2017sgd}.  All\xspace the\xspace neural\xspace networks\xspace in\xspace these\xspace experiments\xspace are\xspace trained\xspace to\xspace $\sim 100\%$\xspace  training\xspace accuracy\xspace, and\xspace the\xspace single\xspace model\xspace performances\xspace match\xspace the\xspace state\xspace-of\xspace-the\xspace-art\xspace for\xspace these\xspace models\xspace on\xspace CIFAR\xspace-10/100. For\xspace experiment\xspace details\xspace, see\xspace \antinfiammatoria{app:exp:single-ensemble-distill}.)
\label{fig:cifar}}
\end{figure}

\begin{itemize}
\item \textcolor{blue}{\textbf{Model averaging (i.e., ensemble) in deep learning works very differently from model averaging in random feature mappings}} --- in\xspace particular\xspace, different\xspace from\xspace the\xspace neural\xspace tangent\xspace kernel\xspace (NTK)\xspace approach~\cite{als18dnn,li2018learning,al19-rnngen,als18,du2018gradient,arora2019finegrained,arora2019exact,zou2018stochastic,du2018gradient2,dfs16,jacot2018neural,ghorbani2019linearized,li2019towards,hanin2019finite,yang2019scaling,cao2019generalization}.

Let\xspace us\xspace do\xspace a\xspace thought\xspace experiment\xspace. If\xspace ensemble\xspace works\xspace, can\xspace we\xspace obtain\xspace the\xspace same\xspace test\xspace performance\xspace of\xspace ensemble\xspace by\xspace training\xspace the\xspace sum\xspace of\xspace over\xspace $L$\xspace  neural\xspace networks\xspace $F = \sum_{\ell \in [L]} f_{\ell}$\xspace  directly\xspace? (As\xspace opposite\xspace to\xspace training\xspace each\xspace $f_{\ell}$\xspace  independently\xspace and\xspace then\xspace average\xspace them\xspace.) Actually\xspace, this\xspace ``direct\xspace training\xspace'' approach\xspace in\xspace deep\xspace learning\xspace is\xspace unable\xspace to\xspace improve\xspace the\xspace test\xspace accuracy\xspace even\xspace comparing\xspace to\xspace single\xspace models\xspace, not\xspace to\xspace say\xspace the\xspace ensemble\xspace model\xspace. See\xspace \sbollisce{fig:cifar}.

In\xspace contrast\xspace, when\xspace each\xspace $f_{\ell}$\xspace  is\xspace a\xspace linear\xspace function\xspace over\xspace random\xspace feature\xspace mappings\xspace (e\xspace.g\xspace., the\xspace NTK\xspace feature\xspace mappings\xspace given\xspace by\xspace the\xspace random\xspace initialization\xspace of\xspace the\xspace network)\xspace, although\xspace the\xspace ensemble\xspace of\xspace these\xspace random\xspace feature\xspace models\xspace \emph{does\xspace improve\xspace} test\xspace accuracy\xspace, training\xspace directly\xspace over\xspace $F = \sum_{\ell  \in [L]} f_{\ell}$\xspace  gives\xspace even\xspace superior\xspace test\xspace accuracy\xspace comparing\xspace to\xspace the\xspace ensemble\xspace. See\xspace \sbollisce{fig:cifar}.

\item Knowledge\xspace distillation\xspace works\xspace for\xspace ensemble\xspace of\xspace neural\xspace networks\xspace but\xspace not\xspace for\xspace ensemble\xspace of\xspace random\xspace feature\xspace mappings\xspace on\xspace standard\xspace data\xspace sets\xspace.

When\xspace  $f_{\ell}$\xspace  is\xspace a\xspace linear\xspace function\xspace over\xspace random\xspace feature\xspace mappings\xspace (e\xspace.g\xspace., the\xspace NTK\xspace feature\xspace mappings)\xspace, the\xspace superior\xspace test\xspace performance\xspace of\xspace ensemble\xspace \emph{cannot\xspace be\xspace distilled\xspace} into\xspace a\xspace single\xspace model\xspace. In\xspace contrast\xspace, in\xspace deep\xspace learning\xspace, such\xspace superior\xspace performance\xspace can\xspace be\xspace later\xspace distilled\xspace into\xspace a\xspace single\xspace model\xspace using~\cite{hinton2015distilling}. The\xspace situation\xspace is\xspace similar\xspace for\xspace \emph{self\xspace-distillation\xspace}, where\xspace it\xspace hardly\xspace works\xspace on\xspace improving\xspace test\xspace performance\xspace for\xspace neural\xspace kernel\xspace methods\xspace, but\xspace works\xspace quite\xspace well\xspace for\xspace training\xspace real\xspace neural\xspace networks\xspace. See\xspace \sbollisce{fig:cifar}.
Together\xspace with\xspace the\xspace first\xspace point\xspace, experiments\xspace suggest\xspace that\xspace to\xspace understand\xspace the\xspace benefit\xspace of\xspace ensemble\xspace and\xspace knowledge\xspace distillation\xspace in\xspace deep\xspace learning\xspace, it\xspace is\xspace perhaps\xspace \textbf{inevitable to study deep learning as a feature learning process}, instead\xspace of\xspace feature\xspace selection\xspace process\xspace (e\xspace.g\xspace. NTK\xspace or\xspace other\xspace neural\xspace kernel\xspace methods)\xspace where\xspace only\xspace the\xspace linear\xspace combinations\xspace of\xspace prescribed\xspace features\xspace are\xspace trained\xspace.

\item Special\xspace structures\xspace in\xspace the\xspace data\xspace (such\xspace as\xspace the\xspace ``multi\xspace-view\xspace'' structure\xspace we\xspace shall\xspace introduce)\xspace is\xspace arguably\xspace necessary\xspace for\xspace ensemble\xspace to\xspace work\xspace. Over\xspace certain\xspace data\xspace sets\xspace with\xspace no\xspace multi\xspace-view\xspace structure\xspace, ensemble\xspace \emph{does\xspace not\xspace improve\xspace the\xspace test\xspace-time\xspace performance\xspace in\xspace deep\xspace learning\xspace} --- despite\xspace having\xspace a\xspace non\xspace-convex\xspace training\xspace objective\xspace and\xspace different\xspace random\xspace seeds\xspace are\xspace used\xspace. See\xspace \sbollisce{fig:syn112}.
In\xspace contrast\xspace, real\xspace-life\xspace data\xspace sets\xspace such\xspace as\xspace CIFAR\xspace-10/100 do\xspace have\xspace the\xspace multi\xspace-view\xspace structure\xspace, moreover\xspace, standard\xspace neural\xspace networks\xspace such\xspace as\xspace ResNet\xspace do\xspace utilize\xspace this\xspace structure\xspace during\xspace the\xspace training\xspace process\xspace in\xspace the\xspace same\xspace way\xspace as\xspace we\xspace show\xspace in\xspace our\xspace theory\xspace. See\xspace \sbollisce{fig:cifar-vis}.

\item  For\xspace neural\xspace networks\xspace, knowledge\xspace distillation\xspace has\xspace learned\xspace most\xspace of\xspace the\xspace features\xspace from\xspace the\xspace ensemble\xspace, and\xspace the\xspace use\xspace of\xspace \emph{hard\xspace labels\xspace} (together\xspace with\xspace the\xspace aforementioned\xspace multi\xspace-view\xspace structure\xspace of\xspace the\xspace data)\xspace is\xspace arguably\xspace another\xspace key\xspace for\xspace why\xspace ensemble\xspace works\xspace.

   Specifically\xspace, if\xspace one\xspace evaluates\xspace an\xspace ensemble\xspace over\xspace models\xspace that\xspace are\xspace already\xspace (independently\xspace at\xspace random)\xspace trained\xspace from\xspace knowledge\xspace distillation\xspace, its\xspace performance\xspace does\xspace not\xspace exceed\xspace the\xspace ensemble\xspace over\xspace the\xspace original\xspace single\xspace models\xspace (see\xspace \sbollisce{fig:ens-dist-ens}). This\xspace means\xspace, models\xspace trained\xspace via\xspace knowledge\xspace distillation\xspace have\xspace learned\xspace most\xspace of\xspace the\xspace features\xspace from\xspace the\xspace ensemble\xspace, and\xspace has\xspace less\xspace variety\xspace comparing\xspace to\xspace the\xspace original\xspace models\xspace --- despite\xspace the\xspace knowledge\xspace distillation\xspace training\xspace objective\xspace is\xspace still\xspace as\xspace non\xspace-convex\xspace as\xspace the\xspace original\xspace training\xspace objective\xspace and\xspace different\xspace random\xspace seeds\xspace are\xspace used\xspace; only\xspace the\xspace training\xspace labels\xspace are\xspace changed\xspace from\xspace hard\xspace to\xspace soft\xspace labels\xspace.

\end{itemize}

\begin{figure}[t!]
\centering
\vspace{-5mm}
{\includegraphics[page=4,trim={25mm 180mm 25mm 25mm},clip,width=0.9\linewidth]{ensemble-exp}}
\caption{Single\xspace models\xspace (+ their\xspace ensemble)\xspace vs\xspace. Knowledge\xspace distillations\xspace (+ their\xspace ensemble)\xspace. Details\xspace in\xspace \antinfiammatoria{app:exp:ens-dist-ens}.
\label{fig:ens-dist-ens}}
\end{figure}

\subsection{Ensemble in Deep Learning v.s. Ensemble of Feature Mappings}

The\xspace recent\xspace advance\xspace in\xspace deep\xspace learning\xspace theory\xspace shows\xspace that\xspace under\xspace certain\xspace circumstances\xspace, deep\xspace learning\xspace can\xspace be\xspace treated\xspace as\xspace a\xspace linear\xspace function\xspace over\xspace random\xspace feature\xspace mappings~\cite{als18dnn,li2018learning,al19-rnngen,als18,du2018gradient,arora2019finegrained,arora2019exact,zou2018stochastic,du2018gradient2,dfs16,jacot2018neural,ghorbani2019linearized,li2019towards,hanin2019finite,yang2019scaling,cao2019generalization}. In\xspace particular\xspace, the\xspace theory\xspace shows\xspace that\xspace when\xspace $f : \mathbb{R}^{D + d} \to \mathbb{R}$\xspace  is\xspace a\xspace neural\xspace network\xspace with\xspace inputs\xspace $x \in \mathbb{R}^d$\xspace  and\xspace weights\xspace $W \in \mathbb{R}^D$\xspace , in\xspace some\xspace cases\xspace, $f(W, x)$\xspace  can\xspace be\xspace approximated\xspace by\xspace:
$$f(W, x) \approx f(W_0, x) + \langle W - W_0, \nabla_{W} f(W_0 , x) \rangle$$

Where\xspace $W_0$\xspace  is\xspace the\xspace random\xspace initialization\xspace of\xspace the\xspace neural\xspace network\xspace, and\xspace $\Phi_{W_0} (x) :=  \nabla_{W} f(W_0 , x) $\xspace  is\xspace the\xspace neural\xspace tangent\xspace kernel\xspace (NTK)\xspace feature\xspace mapping\xspace. This\xspace is\xspace known\xspace as\xspace the\xspace neural\xspace tangent\xspace kernel\xspace (NTK)\xspace approach\xspace. If\xspace this\xspace approximation\xspace holds\xspace, then\xspace training\xspace a\xspace neural\xspace network\xspace can\xspace be\xspace approximated\xspace by\xspace learning\xspace a\xspace linear\xspace function\xspace over\xspace $\Phi_{W_0} (x)$\xspace , which\xspace is\xspace very\xspace theory\xspace-friendly\xspace.

When\xspace training\xspace a\xspace linear\xspace function\xspace over\xspace such\xspace NTK\xspace features\xspace, traditional\xspace theorems~\cite{brown2005diversity,tsymbal2005diversity,bryll2003attribute,alhamdoosh2014fast} suggest\xspace that\xspace the\xspace ensemble\xspace of\xspace $L$\xspace  independently\xspace trained\xspace models\xspace can\xspace indeed\xspace improve\xspace test\xspace-time\xspace performance\xspace, as\xspace it\xspace enlarges\xspace the\xspace feature\xspace space\xspace from\xspace $\Phi_{W_0} (x) $\xspace  to\xspace $\{ \Phi_{W_0^{(i)}} (x) \}_{i \in [L]}$\xspace  for\xspace $L$\xspace  many\xspace independently\xspace sampled\xspace $W_0^{(i)}$\xspace . In\xspace this\xspace case\xspace, ensemble\xspace and\xspace knowledge\xspace distillation\xspace can\xspace be\xspace viewed\xspace as\xspace a\xspace feature\xspace selection\xspace process~\cite{opitz1999feature,rokach2010pattern,cai2018feature,oliveira2003feature,alvarez2012semantic} to\xspace improve\xspace generalization\xspace. Motivate\xspace by\xspace this\xspace line\xspace of\xspace research\xspace, we\xspace ask\xspace:

\begin{center}
\emph{Can\xspace we\xspace understand\xspace ensemble\xspace and\xspace knowledge\xspace distillation\xspace in\xspace deep\xspace learning\xspace as\xspace feature\xspace selections\xspace?}

\emph{(in\xspace particular\xspace, using\xspace the\xspace NTK\xspace approach\xspace?)}
\end{center}

In\xspace this\xspace work\xspace, we\xspace provide\xspace empirical\xspace evidence\xspace towards\xspace \textcolor{blue}{\textbf{rejecting this point of view}}, see\xspace \sbollisce{fig:cifar}.
In\xspace these\xspace experiments\xspace, we\xspace confirm\xspace that\xspace ensemble\xspace\footnote{As\xspace we\xspace mentioned\xspace, in\xspace this\xspace paper\xspace, we\xspace only\xspace focus\xspace on\xspace the\xspace simplest\xspace ensemble\xspace, i\xspace.e\xspace. taking\xspace an\xspace unweighted\xspace average\xspace of\xspace the\xspace output\xspace of\xspace independently\xspace trained\xspace models\xspace.} of\xspace linear\xspace functions\xspace over\xspace NTK\xspace feature\xspace mappings\xspace: $f_i(x) = \langle W^{(i)}, \nabla_{W} f(W_0^{(i)} , x) \rangle$\xspace  does\xspace improve\xspace the\xspace test\xspace accuracy\xspace, however\xspace, such\xspace improvement\xspace might\xspace be\xspace mainly\xspace due\xspace to\xspace a\xspace larger\xspace set\xspace of\xspace features\xspace in\xspace the\xspace ensemble\xspace model\xspace $\{ \Phi_{W_0^{(i)}} (x) \}_{i \in [L]}$\xspace , whose\xspace combinations\xspace contain\xspace functions\xspace that\xspace generalize\xspace better\xspace. To\xspace see\xspace this\xspace, we\xspace observe\xspace that\xspace a\xspace superior\xspace performance\xspace (than\xspace the\xspace ensemble\xspace model)\xspace can\xspace indeed\xspace be\xspace obtained\xspace by\xspace directly\xspace training\xspace $F(x) = \sum_{i \in [L]} \langle W^{(i)}, \nabla_{W} f(W_0^{(i)} , x) \rangle$\xspace  from\xspace the\xspace start\xspace, without\xspace training\xspace individual\xspace models\xspace separately\xspace. Moreover\xspace, we\xspace observe\xspace that\xspace the\xspace result\xspace obtained\xspace by\xspace ensemble\xspace can\xspace not\xspace be\xspace distilled\xspace at\xspace all\xspace into\xspace individual\xspace models\xspace (the\xspace test\xspace accuracy\xspace is\xspace sometimes\xspace even\xspace worse)\xspace, indicating\xspace the\xspace features\xspace selected\xspace by\xspace ensemble\xspace \emph{is\xspace not\xspace contained\xspace} in\xspace the\xspace feature\xspace $\Phi_{W_0^{(i)}} (x) $\xspace  of\xspace any\xspace individual\xspace model\xspace.

On\xspace the\xspace other\xspace hand\xspace, multi\xspace-layer\xspace neural\xspace networks\xspace, when\xspace trained\xspace {as\xspace a\xspace feature\xspace learning\xspace process\xspace instead\xspace of\xspace feature\xspace selection\xspace process\xspace} (i\xspace.e\xspace., the\xspace hidden\xspace layers\xspace are\xspace trained\xspace to\xspace learn\xspace features\xspace, instead\xspace of\xspace staying\xspace close\xspace to\xspace random\xspace initialization)\xspace behave\xspace fundamentally\xspace different\xspace from\xspace the\xspace aforementioned\xspace case\xspace. In\xspace particular\xspace, when\xspace we\xspace train\xspace directly\xspace using\xspace the\xspace sum\xspace of\xspace all\xspace the\xspace models\xspace: $F(x) = \sum_{i \in [L]} f_i(x)$\xspace , it\xspace indeed\xspace does\xspace not\xspace have\xspace any\xspace test\xspace accuracy\xspace gain\xspace comparing\xspace to\xspace individual\xspace $f_i$\xspace  anymore\xspace, as\xspace now\xspace all\xspace $f_i$\xspace 's\xspace \emph{are\xspace capable\xspace of\xspace learning\xspace the\xspace same\xspace set\xspace of\xspace features\xspace}.
Furthermore\xspace, the\xspace test\xspace accuracy\xspace gain\xspace of\xspace the\xspace ensemble\xspace can\xspace be\xspace distilled\xspace into\xspace a\xspace single\xspace model\xspace simply\xspace by\xspace training\xspace the\xspace single\xspace model\xspace to\xspace match\xspace the\xspace output\xspace of\xspace the\xspace ensemble\xspace over\xspace the\xspace original\xspace training\xspace data\xspace set\xspace. This\xspace also\xspace indicates\xspace that\xspace in\xspace actual\xspace deep\xspace learning\xspace, ensemble\xspace \emph{does\xspace not\xspace enlarge\xspace feature\xspace space\xspace}: an\xspace individual\xspace model\xspace $f(x)$\xspace  is\xspace still\xspace capable\xspace of\xspace \emph{learning\xspace the\xspace features\xspace} of\xspace the\xspace ensemble\xspace model\xspace.

Hence\xspace, we\xspace believe\xspace that\xspace to\xspace understand\xspace the\xspace benefit\xspace of\xspace ensemble\xspace and\xspace knowledge\xspace distillation\xspace in\xspace deep\xspace learning\xspace, it\xspace is\xspace \textbf{inevitable} to\xspace study\xspace deep\xspace learning\xspace as\xspace a\xspace \textbf{feature learning process} (where\xspace features\xspace are\xspace trained)\xspace, instead\xspace of\xspace feature\xspace selection\xspace process\xspace (where\xspace the\xspace features\xspace are\xspace prescribed\xspace and\xspace only\xspace the\xspace linear\xspace combinations\xspace are\xspace trained)\xspace. Moreover\xspace, we\xspace point\xspace out\xspace another\xspace fundamental\xspace difficulty\xspace here\xspace:
\begin{mdframed}[frametitle={\colorbox{white}{\space Key challenge:\space}},
frametitleaboveskip=-\ht\strutbox,
frametitlealignment=\center
]
If\xspace a\xspace single\xspace deep\xspace learning\xspace model\xspace is\xspace capable\xspace of\xspace --- through\xspace knowledge\xspace distillation\xspace --- learning\xspace the\xspace features\xspace of\xspace the\xspace ensemble\xspace model\xspace and\xspace achieving\xspace better\xspace test\xspace accuracy\xspace comparing\xspace to\xspace training\xspace the\xspace single\xspace model\xspace directly\xspace (and\xspace the\xspace same\xspace training\xspace accuracy\xspace, typically\xspace at\xspace global\xspace optimal\xspace of\xspace $100 \%$\xspace ), then\xspace why\xspace the\xspace single\xspace model\xspace \emph{cannot\xspace learn\xspace} these\xspace features\xspace directly\xspace when\xspace we\xspace train\xspace the\xspace model\xspace to\xspace match\xspace the\xspace true\xspace data\xspace labels\xspace? What\xspace is\xspace the\xspace \textbf{dark knowledge} hidden\xspace in\xspace the\xspace output\xspace of\xspace ensemble\xspace comparing\xspace to\xspace the\xspace original\xspace label\xspace?
\end{mdframed}

\subsection{Ensemble in Deep Learning: a Feature Learning Process}

Before\xspace addressing\xspace the\xspace key\xspace challenge\xspace, we\xspace point\xspace out\xspace that\xspace prior\xspace works\xspace are\xspace very\xspace limited\xspace with\xspace respect\xspace to\xspace studying\xspace neural\xspace network\xspace training\xspace as\xspace a\xspace feature\xspace learning\xspace process\xspace, due\xspace to\xspace the\xspace extreme\xspace non\xspace-convexity\xspace obstacle\xspace in\xspace optimization\xspace.

Most\xspace of\xspace the\xspace existing\xspace works\xspace proving\xspace that\xspace neural\xspace networks\xspace can\xspace learn\xspace features\xspace only\xspace focus\xspace on\xspace the\xspace case\xspace \emph{when\xspace the\xspace input\xspace is\xspace Gaussian\xspace or\xspace Gaussian\xspace-like\xspace}~\cite{kawaguchi2016deep,soudry2016no,xie2016diversity,ge2017learning,soltanolkotabi2017theoretical,tian2017analytical,brutzkus2017globally,zhong2017recovery,li2017convergence,boob2017theoretical,li2017algorithmic,vempala2018polynomial,ge2018learning,bakshi2018learning,oymak2019towards,yehudai2019power,li2017convergence,li2017provable,li2016recovery,li2020can,allen2020feature,li2020learning}. However\xspace, as\xspace we\xspace demonstrate\xspace in\xspace \sbollisce{fig:syn112},

\begin{figure}[t!]
\centering
\vspace{-5mm}
{\includegraphics[page=3,trim={25mm 195mm 35mm 25mm},clip,width=0.9\linewidth]{ensemble-exp}}
\caption{When\xspace data\xspace is\xspace Gaussian\xspace-like\xspace, and\xspace when\xspace the\xspace target\xspace label\xspace is\xspace generated\xspace by\xspace some\xspace fully\xspace-connected(fc) /\xspace residual(res) /\xspace convolutional(conv)\xspace network\xspace, \emph{ensemble\xspace does\xspace not\xspace} seem\xspace to\xspace improve\xspace test\xspace accuracy\xspace. ``{ xx\xspace\% (yy\xspace\%)}'' means\xspace $xx\%$\xspace  accuracy\xspace for\xspace single\xspace model\xspace and\xspace $yy\%$\xspace  for\xspace ensemble\xspace. More\xspace experiments\xspace in\xspace \antinfiammatoria{app:exp:gaussian}.
\label{fig:syn112}}
\end{figure}

\begin{mdframed}[frametitle={\colorbox{white}{\space Ensemble in DL might not improve test accuracy when inputs are Gaussian-like:\space}},
frametitleaboveskip=-\ht\strutbox,
frametitlealignment=\center
]
Empirically\xspace, ensemble\xspace \emph{does\xspace not\xspace} improve\xspace test\xspace accuracy\xspace in\xspace deep\xspace learning\xspace, in\xspace certain\xspace scenarios\xspace when\xspace the\xspace distribution\xspace of\xspace the\xspace input\xspace data\xspace is\xspace Gaussian\xspace or\xspace even\xspace mixture\xspace of\xspace Gaussians\xspace. This\xspace is\xspace true\xspace over\xspace various\xspace learner\xspace network\xspace structures\xspace (fully\xspace-connected\xspace, residual\xspace, convolution\xspace neural\xspace networks)\xspace and\xspace various\xspace labeling\xspace functions\xspace (when\xspace the\xspace labels\xspace are\xspace generated\xspace by\xspace linear\xspace functions\xspace, fully\xspace-connected\xspace, residual\xspace, convolutional\xspace networks\xspace, with\xspace/without\xspace label\xspace noise\xspace, with\xspace/without\xspace classification\xspace margin)\xspace.
\end{mdframed}

Some\xspace prior\xspace works\xspace also\xspace try\xspace to\xspace attribute\xspace the\xspace benefit\xspace of\xspace ensemble\xspace as\xspace reducing\xspace the\xspace variance\xspace of\xspace individual\xspace solutions~\cite{munson2009feature,valentini2004bias,mehta2019high,valentini2005experimental,brown2005managing} due\xspace to\xspace label\xspace noise\xspace or\xspace non\xspace-convex\xspace landscape\xspace of\xspace the\xspace training\xspace objective\xspace (so\xspace some\xspace individual\xspace models\xspace might\xspace simply\xspace not\xspace be\xspace trained\xspace very\xspace well\xspace by\xspace over\xspace-fitting\xspace to\xspace the\xspace label\xspace noise\xspace or\xspace stuck\xspace at\xspace a\xspace bad\xspace local\xspace minimal)\xspace. However\xspace, we\xspace point\xspace out\xspace that\xspace

(A)\xspace. Reducing\xspace variance\xspace can\xspace indeed\xspace reduce\xspace test\xspace loss\xspace (typically\xspace cross\xspace-entropy)\xspace, but\xspace not\xspace necessarily\xspace test\xspace error\xspace (classification\xspace error)\xspace . For\xspace example\xspace, even\xspace taking\xspace the\xspace average\xspace of\xspace the\xspace outputs\xspace of\xspace random\xspace models\xspace can\xspace reduce\xspace test\xspace loss\xspace comparing\xspace to\xspace each\xspace random\xspace model\xspace (due\xspace to\xspace the\xspace convexity\xspace of\xspace cross\xspace-entropy\xspace loss)\xspace, but\xspace the\xspace prediction\xspace of\xspace the\xspace average\xspace is\xspace still\xspace random\xspace. Moreover\xspace, in\xspace many\xspace of\xspace the\xspace synthetic\xspace experiments\xspace in~\sbollisce{fig:syn112}, after\xspace ensemble\xspace several\xspace independently\xspace trained\xspace neural\xspace networks\xspace, the\xspace variance\xspace of\xspace the\xspace models\xspace is\xspace being\xspace reduced\xspace, but\xspace the\xspace test\xspace accuracy\xspace is\xspace \emph{not\xspace improved\xspace}.

(B)\xspace. In\xspace deep\xspace learning\xspace, despite\xspace the\xspace (huge)\xspace non\xspace-convexity\xspace in\xspace the\xspace optimization\xspace landscape\xspace,\begin{itemize}
\item For\xspace standard\xspace deep\xspace learning\xspace data\xspace sets\xspace (e\xspace.g\xspace. CIFAR\xspace-10/100), all\xspace individual\xspace neural\xspace networks\xspace (such\xspace as\xspace a\xspace ResNet\xspace-34) are\xspace typically\xspace trained\xspace efficiently\xspace by\xspace SGD\xspace and\xspace already\xspace converge\xspace to\xspace global\xspace optimals\xspace with\xspace 100 \% training\xspace accuracy\xspace and\xspace nearly\xspace zero\xspace training\xspace loss\xspace.
\item For\xspace standard\xspace deep\xspace learning\xspace data\xspace set\xspace (e\xspace.g\xspace. CIFAR\xspace-10/100), ensemble\xspace helps\xspace even\xspace when\xspace there\xspace is\xspace essentially\xspace no\xspace label\xspace noise\xspace. On\xspace the\xspace other\xspace hand\xspace, in\xspace our\xspace synthetic\xspace experiments\xspace,  ensemble\xspace does\xspace not\xspace help\xspace on\xspace Gaussian\xspace-like\xspace data\xspace even\xspace when\xspace there\xspace is\xspace label\xspace noise\xspace.
\item For\xspace standard\xspace neural\xspace networks\xspace (e\xspace.g\xspace. ResNet)\xspace trained\xspace on\xspace standard\xspace data\xspace set\xspace (e\xspace.g\xspace. CIFAR\xspace-10/100), when\xspace all\xspace the\xspace individual\xspace models\xspace are\xspace well\xspace-trained\xspace with\xspace the\xspace same\xspace learning\xspace rate\xspace/weight\xspace decay\xspace and\xspace only\xspace differ\xspace by\xspace their\xspace random\xspace seeds\xspace, there\xspace is\xspace \emph{almost\xspace no\xspace variance\xspace} in\xspace terms\xspace of\xspace test\xspace accuracy\xspace for\xspace individual\xspace models\xspace (e\xspace.g\xspace. $0.1\sim0.4\%$\xspace  std\xspace on\xspace CIFAR\xspace-100, see\xspace \sbollisce{fig:cifar}). Hence\xspace with\xspace high\xspace probability\xspace, all\xspace individual\xspace models\xspace are\xspace trained\xspace \emph{almost\xspace equally\xspace well\xspace}, yet\xspace ensemble\xspace them\xspace offers\xspace a\xspace huge\xspace benefit\xspace in\xspace test\xspace performance\xspace.

\item For\xspace neural\xspace networks\xspace trained\xspace on\xspace our\xspace Gaussian\xspace-like\xspace data\xspace, there\xspace is\xspace relatively\xspace \emph{higher\xspace variance\xspace} (e\xspace.g\xspace. $0.5\sim1.0\%$\xspace  std\xspace in\xspace test\xspace accuracies\xspace, see\xspace \sbollisce{fig:synthetic:std} in\xspace the\xspace appendix)\xspace, yet\xspace ensemble\xspace offers\xspace no\xspace benefit\xspace at\xspace all\xspace.

\item For\xspace individual\xspace neural\xspace networks\xspace trained\xspace using\xspace the\xspace knowledge\xspace distillation\xspace objective\xspace (matching\xspace the\xspace soft\xspace labels)\xspace, ensemble\xspace does\xspace not\xspace improve\xspace test\xspace accuracy\xspace that\xspace much\xspace. Together\xspace with\xspace previous\xspace points\xspace, we\xspace can\xspace see\xspace that\xspace \emph{the\xspace non\xspace-convexity\xspace of\xspace deep\xspace learning\xspace training\xspace objectives\xspace in\xspace both\xspace synthetic\xspace experiments\xspace and\xspace real\xspace-world\xspace data\xspace set\xspace does\xspace not\xspace guarantee\xspace that\xspace ensemble\xspace shall\xspace improve\xspace test\xspace accuracy\xspace. }
\end{itemize}

\noindent
Hence\xspace, to\xspace understand\xspace the\xspace true\xspace benefit\xspace of\xspace ensemble\xspace in\xspace deep\xspace learning\xspace in\xspace theory\xspace, we\xspace would\xspace like\xspace to\xspace \textbf{consider a setting tied to practice}, where\xspace:
\begin{itemize}
\item The\xspace input\xspace distribution\xspace is\xspace more\xspace structured\xspace than\xspace standard\xspace Gaussian\xspace and\xspace there\xspace is\xspace no\xspace label\xspace noise\xspace. (In\xspace particular\xspace, ensemble\xspace cannot\xspace work\xspace for\xspace deep\xspace learning\xspace distribution\xspace-freely\xspace, nor\xspace even\xspace under\xspace Gaussian\xspace distribution)\xspace.
\item The\xspace individual\xspace neural\xspace networks\xspace all\xspace are\xspace well\xspace-trained\xspace, in\xspace the\xspace sense\xspace that\xspace the\xspace training\xspace accuracy\xspace at\xspace the\xspace end\xspace is\xspace $100\%$\xspace ,  and\xspace there\xspace is\xspace nearly\xspace no\xspace variance\xspace in\xspace the\xspace test\xspace accuracy\xspace for\xspace individual\xspace models\xspace. (So\xspace training\xspace and\xspace generalization\xspace never\xspace fails)\xspace.
\end{itemize}

We\xspace would\xspace like\xspace to\xspace re\xspace-elaborate\xspace the\xspace \emph{key\xspace challenge\xspace}: `ensemble\xspace improves\xspace test\xspace accuracy\xspace' implies\xspace that\xspace different\xspace single\xspace models\xspace need\xspace to\xspace learn\xspace different\xspace sets\xspace of\xspace features\xspace; however\xspace, all\xspace these\xspace models\xspace have\xspace the\xspace same\xspace architecture\xspace, and\xspace trained\xspace using\xspace the\xspace same\xspace learning\xspace algorithm\xspace (SGD\xspace with\xspace momentum)\xspace with\xspace identical\xspace learning\xspace rates\xspace, and\xspace each\xspace the\xspace (learned)\xspace sets\xspace of\xspace features\xspace in\xspace each\xspace model\xspace {lead\xspace to\xspace the\xspace perfect\xspace $100\%$\xspace  training\xspace accuracy\xspace and\xspace an\xspace almost\xspace identical\xspace test\xspace accuracy\xspace}. Thus\xspace, the\xspace difference\xspace of\xspace the\xspace features\xspace \emph{must\xspace not\xspace be\xspace} due\xspace to\xspace `difference\xspace in\xspace the\xspace data\xspace set\xspace', `difference\xspace in\xspace the\xspace models\xspace', `difference\xspace in\xspace the\xspace training\xspace algorithms\xspace', `difference\xspace in\xspace the\xspace learning\xspace rates\xspace', `failure\xspace in\xspace training\xspace occasionally\xspace', `failure\xspace in\xspace generalization\xspace in\xspace some\xspace cases\xspace', etc\xspace. Additional\xspace principles\xspace need\xspace to\xspace be\xspace developed\xspace to\xspace incorporate\xspace the\xspace effect\xspace of\xspace ensemble\xspace in\xspace deep\xspace learning\xspace.

Hence\xspace, in\xspace this\xspace work\xspace, we\xspace propose\xspace to\xspace study\xspace a\xspace setting\xspace of\xspace data\xspace set\xspace that\xspace we\xspace refer\xspace to\xspace as\xspace \textbf{multi-view}, where\xspace the\xspace above\xspace two\xspace conditions\xspace both\xspace hold\xspace when\xspace we\xspace train\xspace a\xspace two\xspace-layer\xspace neural\xspace networks\xspace with\xspace (smoothed\xspace-)ReLU\xspace activations\xspace. Moreover\xspace, we\xspace show\xspace: (1). Ensemble\xspace provably\xspace improves\xspace test\xspace accuracy\xspace over\xspace well\xspace-trained\xspace single\xspace models\xspace. (2). Ensemble\xspace can\xspace later\xspace be\xspace provably\xspace distilled\xspace into\xspace a\xspace single\xspace model\xspace, by\xspace training\xspace a\xspace single\xspace model\xspace to\xspace match\xspace the\xspace output\xspace of\xspace the\xspace ensemble\xspace on\xspace the\xspace training\xspace data\xspace set\xspace, and\xspace the\xspace single\xspace model\xspace matches\xspace the\xspace test\xspace performance\xspace of\xspace ensemble\xspace. (3). Self\xspace-distillation\xspace also\xspace provably\xspace improves\xspace test\xspace accuracy\xspace over\xspace individual\xspace model\xspace. (4). We\xspace also\xspace argue\xspace that\xspace the\xspace multi\xspace-view\xspace structure\xspace of\xspace the\xspace input\xspace data\xspace we\xspace consider\xspace is\xspace fairly\xspace common\xspace in\xspace the\xspace data\xspace sets\xspace used\xspace in\xspace deep\xspace learning\xspace, in\xspace particular\xspace for\xspace vision\xspace tasks\xspace. We\xspace give\xspace more\xspace details\xspace below\xspace.

\subsection{Our Approach: Learning Multi-View Data}
\label{sec:intro:our}

Let\xspace us\xspace first\xspace give\xspace a\xspace thought\xspace experiment\xspace to\xspace illustrate\xspace our\xspace approach\xspace, and\xspace we\xspace present\xspace the\xspace precise\xspace mathematical\xspace definition\xspace of\xspace the\xspace ``multi\xspace-view\xspace'' structure\xspace in\xspace Section~\ref{sec:PS}. Consider\xspace a\xspace binary\xspace classification\xspace problem\xspace and\xspace four\xspace ``features\xspace'' $v_1, v_2, v_3, v_4$\xspace . The\xspace first\xspace two\xspace features\xspace correspond\xspace to\xspace the\xspace first\xspace class\xspace label\xspace, and\xspace the\xspace next\xspace two\xspace features\xspace correspond\xspace to\xspace the\xspace second\xspace class\xspace label\xspace. In\xspace the\xspace data\xspace distribution\xspace:
\begin{itemize}

\item When\xspace the\xspace label\xspace is\xspace class\xspace $1$\xspace , then\xspace:
\begin{align*
\item When\xspace the\xspace label\xspace is\xspace class\xspace $2$\xspace , then\xspace
\begin{align*
\end{itemize}

We\xspace call\xspace the\xspace $80 \%$\xspace  of\xspace the\xspace data\xspace \emph{multi\xspace-view\xspace data\xspace}: these\xspace are\xspace the\xspace data\xspace where\xspace multiple\xspace features\xspace exist\xspace and\xspace can\xspace be\xspace used\xspace to\xspace classify\xspace them\xspace correctly\xspace. We\xspace call\xspace the\xspace reset\xspace $20 \%$\xspace  of\xspace the\xspace data\xspace \emph{single\xspace-view\xspace data\xspace}: some\xspace features\xspace for\xspace the\xspace correct\xspace labels\xspace are\xspace missing\xspace.

\rintiepidendo{How\xspace individual\xspace neural\xspace networks\xspace learn\xspace}
In\xspace this\xspace data\xspace set\xspace, if\xspace we\xspace train\xspace the\xspace neural\xspace network\xspace using\xspace the\xspace cross\xspace-entropy\xspace loss\xspace via\xspace gradient\xspace descent\xspace (GD)\xspace from\xspace random\xspace initialization\xspace, during\xspace the\xspace training\xspace process\xspace of\xspace the\xspace individual\xspace networks\xspace, we\xspace show\xspace that\xspace:
\begin{itemize}
\item The\xspace network\xspace will\xspace quickly\xspace pick\xspace up\xspace one\xspace of\xspace the\xspace feature\xspace $v \in \{ v_1, v_2\}$\xspace  for\xspace the\xspace first\xspace label\xspace, and\xspace one\xspace of\xspace the\xspace features\xspace $v' \in \{v_3, v_4\}$\xspace  for\xspace the\xspace second\xspace label\xspace. So\xspace, $90 \%$\xspace  of\xspace the\xspace training\xspace examples\xspace, consisting\xspace of\xspace all\xspace multi\xspace-view\xspace data\xspace and\xspace half\xspace of\xspace the\xspace single\xspace-view\xspace data\xspace (those\xspace with\xspace feature\xspace $v$\xspace  or\xspace $v'$\xspace ), are\xspace classified\xspace correctly\xspace. These\xspace data\xspace begin\xspace to\xspace contribute\xspace negligible\xspace gradient\xspace after\xspace wards\xspace.
\item The\xspace network\xspace will\xspace memorize\xspace (using\xspace for\xspace example\xspace the\xspace noise\xspace in\xspace the\xspace data)\xspace the\xspace remaining\xspace $10 \%$\xspace  of\xspace the\xspace training\xspace examples\xspace without\xspace learning\xspace any\xspace new\xspace features\xspace, due\xspace to\xspace insufficient\xspace amount\xspace of\xspace left\xspace-over\xspace samples\xspace after\xspace the\xspace first\xspace phase\xspace, thus\xspace achieving\xspace training\xspace accuracy\xspace $100 \%$\xspace  but\xspace test\xspace accuracy\xspace $90 \%$\xspace .
\end{itemize}

\rintiepidendo{How\xspace ensemble\xspace improves\xspace test\xspace accuracy\xspace}
We\xspace show\xspace that\xspace depending\xspace on\xspace the\xspace randomness\xspace of\xspace the\xspace initialization\xspace, each\xspace individual\xspace network\xspace will\xspace pick\xspace up\xspace $v_1$\xspace  or\xspace $v_2$\xspace  each\xspace with\xspace probability\xspace $0.5$\xspace . Hence\xspace, we\xspace can\xspace prove\xspace that\xspace as\xspace long\xspace as\xspace we\xspace ensemble\xspace $\tilde{O}(1)$\xspace  many\xspace independently\xspace trained\xspace models\xspace, w\xspace.h\xspace.p\xspace. the\xspace ensemble\xspace model\xspace will\xspace be\xspace able\xspace to\xspace pick\xspace up\xspace both\xspace features\xspace $\{v_1,v_2\}$\xspace , and\xspace both\xspace features\xspace $\{v_3,v_4\}$\xspace . Thus\xspace, all\xspace the\xspace data\xspace will\xspace be\xspace classified\xspace correctly\xspace.

\rintiepidendo{How\xspace knowledge\xspace distillation\xspace works\xspace}
Since\xspace ensemble\xspace learns\xspace all\xspace the\xspace features\xspace $v_1, v_2, v_3, v_4$\xspace , on\xspace the\xspace multi\xspace-view\xspace data\xspace with\xspace label\xspace $1$\xspace , the\xspace ensemble\xspace model\xspace will\xspace actually\xspace output\xspace $\propto (2, 0.1)$\xspace , where\xspace the\xspace $2$\xspace  comes\xspace from\xspace features\xspace $v_1, v_2$\xspace  and\xspace $0.1$\xspace  comes\xspace from\xspace one\xspace of\xspace $v_3, v_4$\xspace . On\xspace the\xspace other\xspace hand\xspace, an\xspace individual\xspace model\xspace that\xspace only\xspace learns\xspace one\xspace of\xspace $v_3, v_4$\xspace  will\xspace actually\xspace output\xspace $\propto (2, 0)$\xspace  when\xspace the\xspace feature\xspace $v_3$\xspace  or\xspace $v_4$\xspace  in\xspace the\xspace data\xspace does\xspace not\xspace match\xspace the\xspace one\xspace learned\xspace by\xspace the\xspace model\xspace. Hence\xspace, by\xspace training\xspace the\xspace individual\xspace model\xspace to\xspace match\xspace the\xspace output\xspace of\xspace the\xspace ensemble\xspace, the\xspace individual\xspace model\xspace is\xspace forced\xspace to\xspace learn\xspace both\xspace features\xspace $v_3, v_4$\xspace , even\xspace though\xspace it\xspace has\xspace already\xspace perfectly\xspace classified\xspace the\xspace training\xspace data\xspace. \textbf{This is the ``dark knowledge'' hidden in the ensemble model}.

\rintiepidendo{Generality\xspace of\xspace our\xspace multi\xspace-view\xspace hypothesis\xspace}
We\xspace point\xspace out\xspace that\xspace such\xspace ``multi\xspace-view\xspace'' structure\xspace is\xspace very\xspace common\xspace in\xspace standard\xspace data\xspace set\xspace for\xspace deep\xspace learning\xspace. For\xspace example\xspace, in\xspace vision\xspace tasks\xspace, most\xspace of\xspace the\xspace cars\xspace can\xspace be\xspace classified\xspace correctly\xspace comparing\xspace to\xspace cat\xspace, by\xspace looking\xspace at\xspace either\xspace the\xspace wheel\xspace feature\xspace, or\xspace the\xspace window\xspace feature\xspace, or\xspace even\xspace the\xspace light\xspace feature\xspace. For\xspace a\xspace small\xspace fraction\xspace of\xspace the\xspace car\xspace images\xspace, some\xspace of\xspace these\xspace features\xspace might\xspace be\xspace missing\xspace (for\xspace example\xspace, when\xspace a\xspace car\xspace is\xspace facing\xspace front\xspace and\xspace the\xspace wheels\xspace cannot\xspace be\xspace seen)\xspace. Moreover\xspace, some\xspace car\xspace might\xspace also\xspace have\xspace a\xspace small\xspace fraction\xspace of\xspace ``cat\xspace features\xspace'', for\xspace example\xspace the\xspace side\xspace mirror\xspace might\xspace appear\xspace similar\xspace to\xspace the\xspace ear\xspace of\xspace a\xspace cat\xspace. This\xspace can\xspace be\xspace used\xspace as\xspace the\xspace ``dark\xspace knowledge\xspace'' by\xspace the\xspace single\xspace model\xspace to\xspace learn\xspace from\xspace the\xspace ensemble\xspace.
In\xspace \sbollisce{fig:cifar-vis}, we\xspace plot\xspace the\xspace ``heatmap\xspace'' for\xspace some\xspace car\xspace images\xspace in\xspace the\xspace CIFAR10\xspace dataset\xspace, to\xspace illustrate\xspace that\xspace single\xspace models\xspace (trained\xspace from\xspace different\xspace random\xspace seeds)\xspace indeed\xspace pick\xspace up\xspace different\xspace parts\xspace of\xspace the\xspace input\xspace image\xspace to\xspace classify\xspace it\xspace as\xspace a\xspace car\xspace.
In\xspace \sbollisce{fig:cifar-views}, we\xspace also\xspace manually\xspace delete\xspace for\xspace instance\xspace 7/8 of\xspace the\xspace channels\xspace in\xspace some\xspace intermediate\xspace layer\xspace of\xspace a\xspace ResNet\xspace, and\xspace show\xspace that\xspace the\xspace test\xspace accuracy\xspace may\xspace not\xspace be\xspace affected\xspace by\xspace much\xspace after\xspace ensemble\xspace --- thus\xspace supporting\xspace that\xspace the\xspace multi\xspace-view\xspace hypothesis\xspace can\xspace indeed\xspace exist\xspace even\xspace in\xspace the\xspace intermediate\xspace layers\xspace of\xspace a\xspace neural\xspace network\xspace and\xspace ensemble\xspace is\xspace indeed\xspace collecting\xspace all\xspace these\xspace views\xspace.

\rintiepidendo{Significance\xspace of\xspace our\xspace technique\xspace}
Our\xspace work\xspace belongs\xspace to\xspace the\xspace generic\xspace framework\xspace where\xspace one\xspace can\xspace prove\xspace that\xspace certain\xspace aspects\xspace of\xspace the\xspace learning\xspace algorithm\xspace (in\xspace this\xspace paper\xspace, the\xspace randomness\xspace of\xspace the\xspace initialization)\xspace affects\xspace the\xspace order\xspace where\xspace the\xspace features\xspace are\xspace learned\xspace, {which\xspace we\xspace believe\xspace is\xspace also\xspace one\xspace of\xspace the\xspace key\xspace ingredients\xspace to\xspace understand\xspace the\xspace role\xspace of\xspace the\xspace learning\xspace algorithm\xspace in\xspace terms\xspace of\xspace generalization\xspace in\xspace deep\xspace learning\xspace}.
This\xspace is\xspace \textbf{fundamentally different from convex optimization} in\xspace machine\xspace learning\xspace, such\xspace as\xspace kernel\xspace method\xspace, where\xspace (with\xspace an\xspace $\ell_2$\xspace  regularization)\xspace there\xspace is\xspace an\xspace unique\xspace \emph{global\xspace minimum\xspace} so\xspace the\xspace choice\xspace of\xspace optimization\xspace algorithm\xspace or\xspace the\xspace random\xspace seed\xspace of\xspace the\xspace initialization\xspace does\xspace not\xspace matter\xspace (in\xspace particular\xspace, ensemble\xspace does\xspace not\xspace help\xspace at\xspace all\xspace in\xspace this\xspace case\xspace since\xspace all\xspace the\xspace individual\xspace models\xspace are\xspace the\xspace same\xspace after\xspace training)\xspace. There\xspace are\xspace other\xspace works\xspace that\xspace consider\xspace other\xspace aspects\xspace, such\xspace as\xspace the\xspace choice\xspace of\xspace learning\xspace rate~\cite{li2019towards}, that\xspace can\xspace affect\xspace the\xspace order\xspace where\xspace the\xspace features\xspace are\xspace learned\xspace in\xspace deep\xspace learning\xspace. In\xspace that\xspace work~\cite{li2019towards}, the\xspace two\xspace ``features\xspace'' are\xspace asymmetric\xspace: memorizable\xspace feature\xspace and\xspace generalizable\xspace feature\xspace, so\xspace the\xspace learning\xspace rate\xspace will\xspace decide\xspace which\xspace feature\xspace to\xspace be\xspace picked\xspace. While\xspace in\xspace our\xspace work\xspace, the\xspace features\xspace are\xspace ``symmetric\xspace'', so\xspace the\xspace randomness\xspace of\xspace the\xspace initialization\xspace will\xspace decide\xspace which\xspace feature\xspace to\xspace be\xspace picked\xspace.

We\xspace believe\xspace that\xspace our\xspace work\xspace {extends\xspace the\xspace reach\xspace of\xspace traditional\xspace optimization\xspace and\xspace statistical\xspace machine\xspace learning\xspace theory\xspace}, where\xspace typically\xspace the\xspace statistics\xspace (generalization)\xspace is\xspace separated\xspace from\xspace optimization\xspace (training)\xspace. As\xspace we\xspace have\xspace pointed\xspace out\xspace, such\xspace ``separate\xspace'' treatment\xspace might\xspace not\xspace be\xspace possible\xspace to\xspace understand\xspace (at\xspace least\xspace ensemble\xspace or\xspace knowledge\xspace distillation\xspace in)\xspace deep\xspace learning\xspace.

\begin{figure}[t!]
\centering
\vspace{-5mm}
{\includegraphics[width=0.7\linewidth]{vis}}
\caption{Ten\xspace independently\xspace trained\xspace ResNet\xspace-34 models\xspace (and\xspace their\xspace ensemble)\xspace detect\xspace car\xspace images\xspace through\xspace different\xspace reasonings\xspace, suggesting\xspace that\xspace the\xspace data\xspace has\xspace multi\xspace views\xspace, and\xspace independently\xspace trained\xspace neural\xspace networks\xspace do\xspace utilize\xspace this\xspace structure\xspace.
The\xspace numerical\xspace experiments\xspace in\xspace \sbollisce{fig:cifar-views} also\xspace suggest\xspace the\xspace existence\xspace of\xspace multi\xspace views\xspace.
\label{fig:cifar-vis}}
\end{figure}

\begin{figure}[t!]
\centering
\vspace{-1mm}
\boxed{\includegraphics[page=5,trim={0mm 140mm 142mm 0mm},clip,width=0.9\linewidth]{ensemble-plots.pdf}}
\caption{Visualization\xspace of\xspace the\xspace channels\xspace in\xspace layer\xspace-23 of\xspace a\xspace ResNet\xspace-34 trained\xspace on\xspace CIFAR\xspace-10, picture\xspace from\xspace \cite{allen2020backward}.
\label{fig:cifar-vis2}}
\end{figure}

\begin{figure}[t!]
\centering
{\includegraphics[page=1,trim={25mm 191mm 25mm 25mm},clip,width=0.95\linewidth]{ensemble-exp}}
\caption{Justify\xspace the\xspace multi\xspace-view\xspace hypothesis\xspace in\xspace practice\xspace. We\xspace regard\xspace some\xspace intermediate\xspace layer\xspace of\xspace a\xspace pre\xspace-trained\xspace ResNet\xspace as\xspace ``input\xspace'' with\xspace multiple\xspace channels\xspace (this\xspace pre\xspace-trained\xspace network\xspace stays\xspace fixed\xspace and\xspace shared\xspace for\xspace all\xspace individual\xspace models)\xspace. Then\xspace, we\xspace train\xspace a\xspace new\xspace model\xspace either\xspace starting\xspace from\xspace this\xspace input\xspace (i\xspace.e\xspace. the\xspace ``\emph{original\xspace}'' column)\xspace, or\xspace from\xspace a\xspace fraction\xspace of\xspace the\xspace input\xspace (i\xspace.e\xspace., ``\emph{split\xspace into\xspace 4}'' means\xspace using\xspace only\xspace 1/4 of\xspace the\xspace input\xspace channels)\xspace, or\xspace from\xspace an\xspace average\xspace of\xspace the\xspace input\xspace (i\xspace.e\xspace., ``\emph{average\xspace over\xspace 4}'' means\xspace averaging\xspace every\xspace four\xspace channels)\xspace. Details\xspace in\xspace \antinfiammatoria{app:exp:justify-views}.
\newline
\textbf{Observation 1.} Even\xspace when\xspace we\xspace significantly\xspace collapse\xspace the\xspace input\xspace channels\xspace (through\xspace averaging\xspace or\xspace throwing\xspace away\xspace most\xspace of\xspace them)\xspace, most\xspace of\xspace the\xspace single\xspace model\xspace test\xspace accuracies\xspace do\xspace not\xspace drop\xspace by\xspace much\xspace. Moreover\xspace, it\xspace's\xspace known~\cite{olah2017feature} that\xspace in\xspace ResNet\xspace, most\xspace channels\xspace are\xspace indeed\xspace learning\xspace different\xspace features\xspace (views)\xspace of\xspace the\xspace input\xspace, also\xspace see\xspace \sbollisce{fig:cifar-vis2} for\xspace an\xspace illustration\xspace. This\xspace indicates\xspace that\xspace many\xspace data\xspace can\xspace be\xspace classified\xspace correctly\xspace using\xspace completely\xspace views\xspace.
\newline
\textbf{Observation 2.} Even\xspace when\xspace single\xspace model\xspace accuracy\xspace drops\xspace noticeably\xspace, ensemble\xspace accuracy\xspace does\xspace not\xspace change\xspace by\xspace much\xspace.  We\xspace believe\xspace this\xspace is\xspace a\xspace strong\xspace evidence\xspace that\xspace there\xspace are\xspace multiple\xspace views\xspace in\xspace the\xspace data\xspace (even\xspace at\xspace intermediate\xspace layers)\xspace, and\xspace \textbf{ensemble can collect all of them even when some models have missing views.}
\label{fig:cifar-views}}
\end{figure}

\section{Problem Setup}\label{sec:PS}

In\xspace this\xspace paper\xspace, we\xspace consider\xspace the\xspace following\xspace data\xspace distribution\xspace with\xspace ``multi\xspace-view\xspace'', that\xspace allows\xspace us\xspace to\xspace formally\xspace prove\xspace our\xspace result\xspace on\xspace Ensemble\xspace and\xspace knowledge\xspace distillation\xspace for\xspace two\xspace-layer\xspace neural\xspace networks\xspace. The\xspace data\xspace distribution\xspace is\xspace a\xspace straight\xspace-forward\xspace generalization\xspace of\xspace the\xspace intuitive\xspace setting\xspace in\xspace Section~\ref{sec:intro:our}.
For\xspace simplicity\xspace, in\xspace the\xspace main\xspace body\xspace, we\xspace use\xspace example\xspace choices\xspace of\xspace the\xspace parameters\xspace mainly\xspace a\xspace function\xspace of\xspace $k$\xspace  (such\xspace as\xspace $P=k^2$\xspace , $\gamma=\frac{1}{k^{1.5}}$\xspace , $\mu = \frac{k^{1.2}}{N}$\xspace , $\rho=k^{-0.01}$\xspace , $\sigma_0 = 1/\sqrt{k}$\xspace  as\xspace we\xspace shall\xspace see\xspace in\xspace this\xspace section)\xspace, and\xspace we\xspace consider\xspace the\xspace case\xspace when\xspace $k$\xspace  is\xspace sufficiently\xspace large\xspace. In\xspace our\xspace formal\xspace statements\xspace of\xspace the\xspace theorems\xspace in\xspace the\xspace appendix\xspace, we\xspace shall\xspace give\xspace a\xspace much\xspace larger\xspace range\xspace of\xspace parameters\xspace for\xspace the\xspace theorems\xspace to\xspace hold\xspace.

\subsection{Data Distribution and Notations} \label{sec:data}
\begin{figure}[t!]
\centering
{\includegraphics[page=4,trim={0mm 120mm 120mm 0mm},clip,width=0.9\linewidth]{ensemble-plots}}
\caption{Illustration\xspace of\xspace a\xspace multi\xspace-view\xspace and\xspace a\xspace single\xspace-view\xspace data\xspace point\xspace; the\xspace feature\xspace vectors\xspace can\xspace also\xspace be\xspace combined\xspace with\xspace feature\xspace noise\xspace and\xspace random\xspace noise\xspace.
\label{fig:data}}
\end{figure}
We\xspace consider\xspace learning\xspace a\xspace $k$\xspace -class\xspace classification\xspace problem\xspace over\xspace $P$\xspace -patch\xspace inputs\xspace, where\xspace each\xspace patch\xspace has\xspace dimension\xspace $d$\xspace . In\xspace symbols\xspace, each\xspace labelled\xspace data\xspace is\xspace represented\xspace by\xspace $(X,y)$\xspace  where\xspace $X = (x_1, x_2, \cdots, x_P) \in (\mathbb{R}^d)^P$\xspace  is\xspace the\xspace data\xspace vector\xspace and\xspace $y\in [k]$\xspace  is\xspace the\xspace data\xspace label\xspace. For\xspace simplicity\xspace, we\xspace focus\xspace on\xspace the\xspace case\xspace when\xspace $P = k^{2}$\xspace , and\xspace $d = \poly(k)$\xspace  for\xspace a\xspace large\xspace polynomial\xspace.

We\xspace consider\xspace the\xspace setting\xspace when\xspace $k$\xspace  is\xspace sufficiently\xspace large\xspace. \emph{If\xspace we\xspace want\xspace to\xspace work\xspace with\xspace fixed\xspace $k$\xspace , say\xspace $k = 2$\xspace , our\xspace theorem\xspace can\xspace also\xspace be\xspace modified\xspace to\xspace that\xspace setting\xspace by\xspace increasing\xspace the\xspace number\xspace of\xspace features\xspace per\xspace class\xspace. In\xspace this\xspace case\xspace, a\xspace subset\xspace of\xspace features\xspace per\xspace class\xspace will\xspace be\xspace learned\xspace by\xspace each\xspace individual\xspace neural\xspace network\xspace. We\xspace keep\xspace our\xspace current\xspace setting\xspace with\xspace two\xspace features\xspace to\xspace simplify\xspace the\xspace proof\xspace}. We\xspace use\xspace ``w\xspace.h\xspace.p\xspace.'' to\xspace denote\xspace with\xspace probability\xspace at\xspace least\xspace $1 - e^{-\Omega(\log^2 k)}$\xspace , and\xspace use\xspace $\tilde{O}, \tilde{\Theta}, \tilde{\Omega}$\xspace  notions\xspace to\xspace hide\xspace polylogarithmic\xspace factors\xspace in\xspace $k$\xspace .

We\xspace would\xspace like\xspace to\xspace assume\xspace that\xspace each\xspace class\xspace $j \in [k]$\xspace  has\xspace multiple\xspace associated\xspace features\xspace, say\xspace \emph{two\xspace features\xspace} for\xspace simplicity\xspace of\xspace the\xspace math\xspace, represented\xspace by\xspace unit\xspace \emph{feature\xspace vectors\xspace} $v_{j, 1}, v_{j, 2} \in \mathbb{R}^d$\xspace . For\xspace simplicity\xspace, we\xspace assume\xspace that\xspace all\xspace the\xspace features\xspace are\xspace orthogonal\xspace, although\xspace our\xspace work\xspace also\xspace extends\xspace to\xspace the\xspace ``in\xspace-coherent\xspace'' case\xspace trivially\xspace.
Namely\xspace,
\anobio

\noindent
We\xspace denote\xspace
\polistirene
We\xspace now\xspace consider\xspace the\xspace following\xspace data\xspace and\xspace label\xspace distribution\xspace.
Let\xspace $C_p$\xspace  be\xspace a\xspace global\xspace constant\xspace, $s \in [1, k^{0.2}]$\xspace  be\xspace a\xspace global\xspace parameter\xspace to\xspace control\xspace feature\xspace sparsity\xspace, $\sigma_p = \frac{1}{\sqrt{d} \polylog(k)}$\xspace  be\xspace a\xspace parameter\xspace to\xspace control\xspace magnitude\xspace of\xspace the\xspace \emph{random\xspace noise\xspace}, $\gamma = \frac{1}{k^{1.5}}$\xspace  be\xspace a\xspace parameter\xspace to\xspace control\xspace the\xspace \emph{feature\xspace noise\xspace}. (Our\xspace proof\xspace in\xspace the\xspace appendix\xspace holds\xspace for\xspace a\xspace wider\xspace range\xspace of\xspace $\gamma$\xspace .)

To\xspace be\xspace concise\xspace, we\xspace define\xspace the\xspace \emph{multi\xspace-view\xspace distribution\xspace} $\mathcal{D}_m$\xspace  and\xspace \emph{single\xspace-view\xspace distribution\xspace} $\mathcal{D}_s$\xspace  together\xspace.

\begin{definition}[data distributions $\mathcal{D}_m$ and $\mathcal{D}_s$]\label{def:dist}
Given\xspace $\mathcal{D} \in \{\mathcal{D}_m, \mathcal{D}_s\}$\xspace , we\xspace define\xspace $(X, y) \sim \mathcal{D} $\xspace  as\xspace follows\xspace.
First\xspace choose\xspace the\xspace label\xspace $y\in[k]$\xspace  uniformly\xspace at\xspace random\xspace.
Then\xspace, the\xspace data\xspace vector\xspace $X$\xspace  is\xspace generated\xspace as\xspace follows\xspace (see\xspace also\xspace an\xspace illustration\xspace in\xspace \sbollisce{fig:data}).

\begin{enumerate}
\item Sample\xspace a\xspace set\xspace $\motosilurante{V}'$\xspace  of\xspace features\xspace uniformly\xspace at\xspace random\xspace from\xspace $\{v_{j', 1}, v_{j', 2}\}_{j' \not= y}$\xspace , each\xspace with\xspace probability\xspace $\frac{s}{k}$\xspace .

\item Denote\xspace $\motosilurante{V}(X) = \motosilurante{V}' \cup \{ v_{y, 1}, v_{y, 2} \}$\xspace  as\xspace the\xspace set\xspace of\xspace feature\xspace vectors\xspace used\xspace in\xspace data\xspace $X$\xspace .

\item For\xspace each\xspace $v \in \motosilurante{V}(X)$\xspace , pick\xspace $C_p$\xspace  many\xspace disjoint\xspace patches\xspace in\xspace $[P]$\xspace  and\xspace denote\xspace it\xspace as\xspace $\motosilurante{P}_v(X)$\xspace  (the\xspace distribution\xspace of\xspace these\xspace patches\xspace can\xspace be\xspace arbitrary)\xspace. We\xspace denote\xspace $\motosilurante{P}(X) = \cup_{v \in \motosilurante{V}(X)} \motosilurante{P}_v(X)$\xspace .

\item If\xspace $\mathcal{D} = \mathcal{D}_s$\xspace  is\xspace the\xspace single\xspace-view\xspace distribution\xspace, pick\xspace a\xspace value\xspace $\hat{\ell} = \hat{\ell}(X) \in [2]$\xspace  uniformly\xspace at\xspace random\xspace.

\item For\xspace each\xspace $p \in \motosilurante{P}_v(X)$\xspace  for\xspace some\xspace $v \in \motosilurante{V}(X)$\xspace , we\xspace set\xspace
\atterrei
Above\xspace, each\xspace $\alpha_{p, v'} \in [0, \gamma]$\xspace  is\xspace the\xspace feature\xspace noise\xspace, and\xspace $\xi_p \sim \mathcal{N}(0, \sigma_p^2 \attaccabottoni{I})$\xspace  is\xspace an\xspace  (independent)\xspace  random\xspace Gaussian\xspace noise\xspace.
The\xspace coefficients\xspace $z_p \geq 0$\xspace  satisfy\xspace that\xspace:

In\xspace the\xspace case\xspace of\xspace multi\xspace-view\xspace distribution\xspace $\mathcal{D}=\mathcal{D}_m$\xspace

\begin{itemize}
\item $\sum_{p \in \motosilurante{P}_v(X)} z_p \in [1, O(1)]$\xspace  when\xspace $v \in \{ v_{y, 1}, v_{y, 2} \}$\xspace ,

and\xspace the\xspace marginal\xspace distribution\xspace of\xspace $\sum_{p \in \motosilurante{P}_v(X)} z_p$\xspace  is\xspace left\xspace-close\xspace;%
\footnote{We\xspace say\xspace a\xspace distribution\xspace $p$\xspace  over\xspace a\xspace real\xspace interval\xspace $[a, b]$\xspace  for\xspace constants\xspace $a, b$\xspace  is\xspace \emph{left\xspace-close\xspace}, if\xspace there\xspace is\xspace a\xspace $\varepsilon \leq \frac{1}{\polylog (k)}$\xspace  such\xspace that\xspace $\Pr_{z \sim p}[ z \leq a + \varepsilon] \geq \frac{1}{\polylog(k)}$\xspace , and\xspace is\xspace \emph{right\xspace-close\xspace} if\xspace $\Pr_{z \sim p}[ z \geq b - \varepsilon] \geq \frac{1}{\polylog(k)}$\xspace .
For\xspace instance\xspace, here\xspace $Z = \sum_{p \in \motosilurante{P}_v(X)} z_p$\xspace  can\xspace be\xspace a\xspace uniform\xspace distribution\xspace over\xspace $[1, 2]$\xspace .}
\item $\sum_{p \in \motosilurante{P}_v(X)} z_p \in [\Omega(1), 0.4]$\xspace  when\xspace $v \in \motosilurante{V}(X) \setminus \{ v_{y, 1}, v_{y, 2} \}$\xspace ,

and\xspace the\xspace marginal\xspace distribution\xspace of\xspace $\sum_{p \in \motosilurante{P}_v(X)} z_p$\xspace  is\xspace right\xspace-close\xspace.%
\footnote{For\xspace instance\xspace, $Z = \sum_{p \in \motosilurante{P}_v(X)} z_p$\xspace  can\xspace be\xspace a\xspace uniform\xspace distribution\xspace over\xspace $[0.2, 0.4]$\xspace .}
\end{itemize}

In\xspace the\xspace case\xspace of\xspace single\xspace-view\xspace distribution\xspace $\mathcal{D}=\mathcal{D}_s$\xspace

\begin{itemize}
\item $\sum_{p \in \motosilurante{P}_v(X)} z_p \in [1, O(1)]$\xspace  when\xspace $v =  v_{y, \hat{\ell}}$\xspace ,
\item $\sum_{p \in \motosilurante{P}_v(X)} z_p \in [\rho, O(\rho)]$\xspace  when\xspace $v = v_{y, 3 - \hat{\ell}}$\xspace ,
\hfill for\xspace a\xspace parameter\xspace $\rho = k^{-0.01}$\xspace %
\item $\sum_{p \in \motosilurante{P}_v(X)} z_p \in [\Omega(\Gamma),  \Gamma]$\xspace  when\xspace $v \in \motosilurante{V}(X) \setminus \{ v_{y, 1}, v_{y, 2} \}$\xspace .
\hfill for\xspace a\xspace parameter\xspace $\Gamma = \frac{1}{\polylog(k)}$\xspace
\end{itemize}

\item For\xspace each\xspace $p \in [P] \setminus \motosilurante{P}(X)$\xspace , we\xspace set\xspace:
\equivarremo

where\xspace each\xspace $\alpha_{p, v'} \in [0, \gamma]$\xspace  is\xspace the\xspace feature\xspace noise\xspace and\xspace $\xi_p \sim \mathcal{N}(0, \frac{\gamma^2k^2}{d} \attaccabottoni{I})$\xspace  is\xspace the\xspace (independent)\xspace Gaussian\xspace noise\xspace.%

\end{enumerate}

\end{definition}

\begin{remark}
The\xspace distribution\xspace of\xspace how\xspace we\xspace pick\xspace $\motosilurante{P}(X)$\xspace  and\xspace how\xspace to\xspace assign\xspace $\sum_{p \in \motosilurante{P}_v(X)} z_p$\xspace  to\xspace each\xspace patch\xspace in\xspace $p\in \motosilurante{P}_v(X)$\xspace  can\xspace be\xspace arbitrary\xspace (and\xspace can\xspace depend\xspace on\xspace other\xspace randomness\xspace in\xspace the\xspace data\xspace as\xspace well)\xspace. Except\xspace the\xspace marginal\xspace distributions\xspace of\xspace the\xspace sum\xspace of\xspace some\xspace $z_p$\xspace 's\xspace are\xspace left\xspace-close\xspace or\xspace right\xspace-close\xspace, but\xspace we\xspace also\xspace do\xspace not\xspace have\xspace other\xspace restrictions\xspace on\xspace how\xspace $z_p$\xspace 's\xspace are\xspace distributed\xspace within\xspace the\xspace summation\xspace.
In\xspace particular\xspace, we\xspace have\xspace allowed\xspace \textbf{different features} $v_{j, 1}$\xspace , $v_{j, 2}$\xspace  to\xspace show\xspace up\xspace with\xspace \textbf{different weights} in\xspace the\xspace data\xspace (for\xspace example\xspace, for\xspace multi\xspace-view\xspace data\xspace, some\xspace view\xspace $v_{y,1}$\xspace  can\xspace consistently\xspace have\xspace larger\xspace $z_p$\xspace  comparing\xspace to\xspace $v_{y,2}$\xspace .) Yet\xspace, we\xspace shall\xspace prove\xspace that\xspace the\xspace order\xspace to\xspace learn\xspace these\xspace features\xspace by\xspace the\xspace learner\xspace network\xspace \emph{can\xspace still\xspace be\xspace flipped\xspace} depending\xspace on\xspace the\xspace randomness\xspace of\xspace network\xspace initialization\xspace. We\xspace also\xspace do\xspace not\xspace have\xspace any\xspace restriction\xspace on\xspace the\xspace distribution\xspace of\xspace the\xspace feature\xspace noise\xspace $\alpha_{p, v'}$\xspace  (they\xspace can\xspace depend\xspace on\xspace other\xspace randomness\xspace of\xspace the\xspace data\xspace distribution\xspace as\xspace well)\xspace.
\end{remark}

\rintiepidendo{Generality\xspace and\xspace significance\xspace of\xspace our\xspace data\xspace distribution\xspace}
Our\xspace setting\xspace is\xspace very\xspace common\xspace and\xspace in\xspace fact\xspace a\xspace down\xspace-sized\xspace version\xspace of\xspace how\xspace convolution\xspace networks\xspace apply\xspace to\xspace image\xspace classification\xspace data\xspace. With\xspace a\xspace small\xspace kernel\xspace size\xspace, the\xspace good\xspace features\xspace in\xspace an\xspace image\xspace typically\xspace appears\xspace only\xspace on\xspace a\xspace few\xspace patches\xspace,%
\footnote{For\xspace example\xspace, in\xspace image\xspace classification\xspace when\xspace the\xspace image\xspace is\xspace of\xspace size\xspace $64 \times 64$\xspace , at\xspace the\xspace first\xspace layer\xspace, each\xspace patch\xspace can\xspace be\xspace a\xspace sub\xspace-image\xspace of\xspace size\xspace $d = 48 = 4 \times 4 \times 3$\xspace  ($3$\xspace  RGB\xspace channels)\xspace, and\xspace there\xspace are\xspace $256$\xspace  patches\xspace. At\xspace the\xspace second\xspace layer\xspace, we\xspace can\xspace have\xspace higher\xspace dimension\xspace $d$\xspace  per\xspace patch\xspace, such\xspace as\xspace $d = 4 \times 4 \times 64$\xspace  when\xspace more\xspace channels\xspace are\xspace introduced\xspace. In\xspace convolution\xspace networks\xspace, there\xspace are\xspace typically\xspace over\xspace-laps\xspace between\xspace patches\xspace, we\xspace point\xspace out\xspace that\xspace our\xspace setting\xspace is\xspace more\xspace general\xspace: In\xspace fact\xspace, for\xspace example\xspace for\xspace a\xspace data\xspace $X = (a, b, c, d)$\xspace  with\xspace patches\xspace $(a, b, c)$\xspace  and\xspace $(b, c , d)$\xspace , we\xspace can\xspace simply\xspace define\xspace $x_1 = (a, b, c)$\xspace  and\xspace $x_2 = (b, c, d)$\xspace . Moreover\xspace, our\xspace $X$\xspace  can\xspace also\xspace be\xspace viewed\xspace as\xspace intermediate\xspace output\xspace of\xspace the\xspace previous\xspace convolution\xspace layer\xspace in\xspace a\xspace convolution\xspace network\xspace.}
and\xspace most\xspace other\xspace patches\xspace are\xspace simply\xspace random\xspace noise\xspace or\xspace low\xspace-magnitude\xspace feature\xspace noises\xspace that\xspace are\xspace more\xspace or\xspace less\xspace irrelevant\xspace to\xspace the\xspace label\xspace.

More\xspace importantly\xspace, the\xspace above\xspace concept\xspace class\xspace (namely\xspace, labeled\xspace data\xspace distribution\xspace in\xspace \scocciatore{def:dist}) is\xspace \textbf{not learnable by linear classifiers or constant degree polynomials}. Indeed\xspace, if\xspace we\xspace only\xspace use\xspace a\xspace linear\xspace classifier\xspace, then\xspace the\xspace total\xspace accumulated\xspace (low\xspace-magnitude)\xspace feature\xspace noise\xspace from\xspace all\xspace patches\xspace can\xspace be\xspace as\xspace large\xspace as\xspace $\gamma P \gg 1$\xspace  by\xspace our\xspace choice\xspace of\xspace $\gamma = \frac{1}{k^{1.5}}$\xspace  and\xspace $P = k^2$\xspace . This\xspace is\xspace much\xspace larger\xspace than\xspace the\xspace magnitude\xspace of\xspace the\xspace signal\xspace. On\xspace the\xspace other\xspace hand\xspace, by\xspace Markov\xspace brother\xspace's\xspace inequality\xspace, low\xspace-degree\xspace polynomials\xspace also\xspace lack\xspace the\xspace power\xspace to\xspace be\xspace approximately\xspace linear\xspace (to\xspace fit\xspace the\xspace signal)\xspace when\xspace the\xspace input\xspace is\xspace large\xspace, while\xspace being\xspace sub\xspace-linear\xspace when\xspace there\xspace are\xspace low\xspace-magnitude\xspace feature\xspace noises\xspace. We\xspace also\xspace conjecture\xspace that\xspace one\xspace can\xspace prove\xspace this\xspace concept\xspace class\xspace is\xspace not\xspace efficiently\xspace learnable\xspace by\xspace kernel\xspace methods\xspace in\xspace general\xspace, using\xspace the\xspace recent\xspace development\xspace of\xspace kernel\xspace lower\xspace bounds~\cite{allen2020backward,AL2019-resnet}. Thus\xspace, we\xspace believe\xspace a\xspace (convolution)\xspace neural\xspace network\xspace with\xspace ReLU\xspace-like\xspace activation\xspace is\xspace in\xspace some\xspace sense\xspace necessary\xspace to\xspace learn\xspace this\xspace concept\xspace class\xspace.

Our\xspace final\xspace data\xspace distribution\xspace $\mathcal{D}$\xspace , and\xspace the\xspace training\xspace data\xspace set\xspace $\mathcal{Z}$\xspace  are\xspace formally\xspace given\xspace as\xspace follows\xspace.

\begin{definition}[$\mathcal{D}$ and $\mathcal{Z}$] \label{set:1}
We\xspace assume\xspace that\xspace the\xspace final\xspace distribution\xspace $\mathcal{D}$\xspace  consists\xspace of\xspace data\xspace from\xspace $\mathcal{D}_m$\xspace  w\xspace.p\xspace. $1 - \mu$\xspace  and\xspace from\xspace $\mathcal{D}_s$\xspace  w\xspace.p\xspace. $\mu$\xspace .
We\xspace are\xspace given\xspace $N = \poly(k)$\xspace  training\xspace samples\xspace from\xspace $\mathcal{D}$\xspace , and\xspace denote\xspace the\xspace training\xspace data\xspace set\xspace as\xspace $\motosilurante{Z} = \motosilurante{Z}_m \cup \motosilurante{Z}_s$\xspace  where\xspace $\motosilurante{Z}_m$\xspace  and\xspace $\motosilurante{Z}_s$\xspace  respectively\xspace represent\xspace multi\xspace-view\xspace and\xspace single\xspace-view\xspace training\xspace data\xspace.
We\xspace write\xspace $(X, y) \sim \motosilurante{Z}$\xspace  as\xspace $(X, y)$\xspace  sampled\xspace uniformly\xspace at\xspace random\xspace from\xspace the\xspace empirical\xspace data\xspace set\xspace, and\xspace denote\xspace $N_s = |\motosilurante{Z}_s|$\xspace .
We\xspace again\xspace for\xspace simplicity\xspace focus\xspace on\xspace the\xspace setting\xspace when\xspace $\mu = k^{1.2} / N$\xspace  so\xspace each\xspace label\xspace $i$\xspace  appears\xspace at\xspace least\xspace $\tilde{\Omega}(1)$\xspace  in\xspace $\mathcal{Z}_s$\xspace . Although\xspace our\xspace result\xspace trivially\xspace applies\xspace to\xspace other\xspace choices\xspace of\xspace $\mu$\xspace .
\end{definition}

\subsection{Learner Network}
\label{sec:learner}

We\xspace consider\xspace a\xspace learner\xspace network\xspace using\xspace the\xspace following\xspace smoothed\xspace ReLU\xspace activation\xspace function\xspace $\tilde{\mathsf{ReLU}}$\xspace :
\begin{definition}\label{def:srelu}
For\xspace an\xspace integer\xspace $q \geq 2$\xspace  and\xspace a\xspace threshold\xspace $\varrho = \frac{1}{\polylog(k)}$\xspace , the\xspace smoothed\xspace ReLU\xspace function\xspace
$$\tilde{\mathsf{ReLU}}(z) \stackrel{\mathrm{\scriptscriptstyle def}}{=} \left\{ \begin{array}{ll
\end{definition}
Since\xspace $\tilde{\mathsf{ReLU}}$\xspace  has\xspace continuous\xspace gradient\xspace and\xspace we\xspace denote\xspace it\xspace as\xspace $\tilde{\mathsf{ReLU}}'(z)$\xspace . For\xspace simplicity\xspace, we\xspace focus\xspace on\xspace the\xspace choice\xspace $q = 4$\xspace , although\xspace our\xspace result\xspace applies\xspace to\xspace other\xspace constants\xspace $q \geq 3$\xspace  (see\xspace appendix)\xspace or\xspace most\xspace other\xspace forms\xspace of\xspace smoothing\xspace trivially\xspace. As\xspace mentioned\xspace in\xspace previous\xspace section\xspace, the\xspace (smoothed)\xspace ReLU\xspace activation\xspace has\xspace a\xspace desired\xspace property\xspace such\xspace that\xspace $\tilde{\mathsf{ReLU}}(z)$\xspace  is\xspace linear\xspace when\xspace $z$\xspace  is\xspace large\xspace, but\xspace becomes\xspace much\xspace smaller\xspace when\xspace $z$\xspace  is\xspace small\xspace. This\xspace allows\xspace the\xspace network\xspace to\xspace effectively\xspace reduce\xspace the\xspace impact\xspace of\xspace low\xspace-magnitude\xspace feature\xspace noises\xspace from\xspace the\xspace input\xspace patches\xspace for\xspace better\xspace classification\xspace.

The\xspace \emph{learner\xspace network\xspace} $F(X)=(F_1(X),\dots,F_k(X)) \in \mathbb{R}^k$\xspace  is\xspace a\xspace two\xspace-layer\xspace convolutional\xspace network\xspace parameterized\xspace by\xspace $w_{i, r} \in \mathbb{R}^d$\xspace  for\xspace $i \in  [k], r \in [m]$\xspace , satisfying\xspace
\begin{align*

Although\xspace there\xspace exists\xspace ground\xspace truth\xspace network\xspace with\xspace $m = 2$\xspace  that\xspace can\xspace classify\xspace the\xspace data\xspace correctly\xspace (e\xspace.g\xspace. $w_{i, r} = v_{i, r} $\xspace  for\xspace $r \in [2]$\xspace ), in\xspace this\xspace paper\xspace,  for\xspace efficient\xspace optimization\xspace purpose\xspace it\xspace is\xspace convenient\xspace to\xspace work\xspace on\xspace a\xspace moderate\xspace level\xspace of\xspace over\xspace-parameterization\xspace: $m \in [\polylog(k), k]$\xspace , which\xspace people\xspace also\xspace typically\xspace use\xspace in\xspace practice\xspace to\xspace train\xspace neural\xspace networks\xspace.

\rintiepidendo{Training\xspace a\xspace Single\xspace Model\xspace}
We\xspace learn\xspace the\xspace concept\xspace class\xspace (namely\xspace, the\xspace labeled\xspace data\xspace distribution)\xspace using\xspace gradient\xspace descent\xspace with\xspace learning\xspace rate\xspace $\eta>0$\xspace , over\xspace the\xspace cross\xspace-entropy\xspace loss\xspace function\xspace $L$\xspace  using\xspace $N$\xspace  training\xspace data\xspace points\xspace $\mathcal{Z} = \{ (X_i, y_i) \}_{i \in [N]}$\xspace .
We\xspace denote\xspace the\xspace empirical\xspace loss\xspace as\xspace:
\abrasiva
where\xspace $L(F; X, y) = - \log \frac{e^{F_{y}(X)}}{\sum_{j \in [k]} e^{F_j(X)}}$\xspace . We\xspace \textbf{randomly initialize} the\xspace network\xspace $F$\xspace  by\xspace letting\xspace each\xspace $w_{i, r}^{(0)} \sim \mathcal{N}(0, \sigma_0^2 I)$\xspace  for\xspace $\sigma_0^2 = \frac{1}{k}$\xspace , which\xspace is\xspace the\xspace most\xspace standard\xspace initialization\xspace people\xspace use\xspace in\xspace practice\xspace.

More\xspace specifically\xspace, to\xspace train\xspace a\xspace single\xspace model\xspace, at\xspace each\xspace iteration\xspace $t$\xspace  we\xspace update\xspace using\xspace gradient\xspace descent\xspace (GD)\xspace:
\begin{align} \label{eq:update
We\xspace run\xspace the\xspace algorithm\xspace for\xspace $T = \frac{\poly(k)}{\eta}$\xspace  many\xspace iterations\xspace. \footnote{Our\xspace result\xspace also\xspace trivially\xspace extends\xspace to\xspace the\xspace case\xspace when\xspace there\xspace is\xspace a\xspace weight\xspace decay\xspace (i\xspace.e\xspace. $\ell_2$\xspace  regularizer)\xspace: $w_{i, r}^{(t + 1)} \gets (1 - \eta \lambda) w_{i, r}^{(t)} - \eta \E_{(X,y)\sim\mathcal{Z}} \nabla_{w_{i, r}} L(F^{(t)}; X,y)$\xspace  as\xspace long\xspace as\xspace $\lambda$\xspace  is\xspace not\xspace too\xspace large\xspace. We\xspace keep\xspace this\xspace basic\xspace version\xspace without\xspace weight\xspace decay\xspace to\xspace simplify\xspace the\xspace analysis\xspace.} We\xspace use\xspace $F^{(t)}$\xspace  to\xspace denote\xspace the\xspace model\xspace $F$\xspace  with\xspace hidden\xspace weights\xspace $\{ w_{i, r}^{(t)} \}$\xspace  at\xspace iteration\xspace $t$\xspace .

\newcommand{\mathbf{logit}}{\mathbf{logit}}
\rintiepidendo{Notations\xspace}
We\xspace denote\xspace by\xspace $ \mathbf{logit}_i(F, X) \stackrel{\mathrm{\scriptscriptstyle def}}{=}   \frac{e^{F_i(X)}}{ \sum_{j \in [k]} e^{F_j(X)}}  $\xspace .
Using\xspace this\xspace, we\xspace can\xspace write\xspace down\xspace
\corbelleria

\section{Main Theorems and Explanations}
\label{sec:main-theorems}

We\xspace now\xspace state\xspace the\xspace main\xspace theorems\xspace in\xspace this\xspace paper\xspace.%
\footnote{We\xspace shall\xspace restate\xspace these\xspace theorems\xspace in\xspace the\xspace appendix\xspace with\xspace more\xspace details\xspace and\xspace wider\xspace range\xspace of\xspace parameters\xspace. }
Recall\xspace the\xspace learner\xspace network\xspace and\xspace its\xspace learning\xspace process\xspace are\xspace given\xspace in\xspace \equoreo{sec:learner}, and\xspace the\xspace data\xspace distribution\xspace is\xspace in\xspace \equoreo{sec:data}.
\begin{reptheorem}{thm:single}[single model]
For\xspace every\xspace sufficiently\xspace large\xspace $k > 0$\xspace , every\xspace $m \in [\polylog(k), k]$\xspace , every\xspace $\eta \leq \frac{1}{\poly(k)}$\xspace , suppose\xspace we\xspace train\xspace a\xspace single\xspace model\xspace using\xspace the\xspace gradient\xspace descent\xspace update\xspace \eqref{eq:update} starting\xspace from\xspace the\xspace random\xspace initialization\xspace defined\xspace in\xspace \equoreo{sec:learner}, then\xspace after\xspace $T =  \frac{\poly(k)}{\eta}$\xspace  many\xspace iterations\xspace, with\xspace probability\xspace $\geq 1-e^{-\Omega(\log^2 k)}$\xspace , the\xspace model\xspace $F^{(T)}$\xspace  satisfies\xspace:
\begin{itemize}
\item (training\xspace accuracy\xspace is\xspace perfect)\xspace: meaning\xspace for\xspace all\xspace $(X, y) \in \motosilurante{Z}$\xspace ,  all\xspace $i \in [k] \setminus \{y\}$\xspace : $F_y^{(T)} (X) > F_i^{(T)} (X)$\xspace .
\item (test\xspace accuracy\xspace is\xspace bad\xspace but\xspace consistent)\xspace:  meaning\xspace that\xspace:
$$\Pr_{(X, y) \sim \mathcal{D}}[ \exists i \in [k] \setminus\{y\} \colon  F_y^{(T)} (X) <  F_i^{(T)} (X) ] \in [0.49 \mu, 0.51 \mu] \enspace.$$
\end{itemize}
\end{reptheorem}

\noindent
We\xspace shall\xspace give\xspace technical\xspace intuitions\xspace about\xspace why\xspace \seduciamo{thm:single} holds\xspace in\xspace \antinfiammatoria{app:single-model}. But\xspace, at\xspace a\xspace high\xspace-level\xspace, we\xspace shall\xspace construct\xspace a\xspace ``lottery\xspace winning\xspace'' set\xspace $\motosilurante{M} \subseteq [k]\times[2]$\xspace  of\xspace cardinality\xspace $|\motosilurante{M}| \in [k(1-o(1)), k]$\xspace . It\xspace only\xspace depends\xspace on\xspace the\xspace random\xspace initialization\xspace of\xspace $F$\xspace . Then\xspace, with\xspace some\xspace effort\xspace we\xspace can\xspace prove\xspace that\xspace, for\xspace every\xspace $(i,\ell)\in\motosilurante{M}$\xspace , at\xspace the\xspace end\xspace of\xspace the\xspace training\xspace $F^{(T)}$\xspace  will\xspace learn\xspace feature\xspace $v_{i,\ell}$\xspace  but\xspace not\xspace learn\xspace feature\xspace $v_{i,3-\ell}$\xspace . This\xspace means\xspace for\xspace those\xspace single\xspace-view\xspace data\xspace $(X,y)$\xspace  with\xspace $y=i$\xspace  and\xspace $\hat{\ell}(X)=3-\ell$\xspace , the\xspace final\xspace network\xspace $F^{(T)}$\xspace  will\xspace predict\xspace its\xspace label\xspace wrong\xspace. This\xspace is\xspace why\xspace the\xspace final\xspace test\xspace accuracy\xspace is\xspace around\xspace $0.5 \mu$\xspace .

We\xspace remark\xspace also\xspace the\xspace property\xspace that\xspace test\xspace accuracy\xspace consistently\xspace belongs\xspace to\xspace the\xspace range\xspace $[0.49 \mu, 0.51 \mu]$\xspace  should\xspace be\xspace reminiscent\xspace of\xspace message\xspace \text{\ding{176}}\xspace in\xspace \sbollisce{fig:cifar}, where\xspace multiple\xspace single\xspace models\xspace, although\xspace starting\xspace from\xspace different\xspace random\xspace initialization\xspace, in\xspace practice\xspace does\xspace have\xspace a\xspace relatively\xspace small\xspace variance\xspace in\xspace terms\xspace of\xspace test\xspace accuracy\xspace.

\rintiepidendo{Ensemble\xspace}
Suppose\xspace $\{F^{[\ell]} \}_{\ell \in [K]}$\xspace  are\xspace $K = \tilde{\Omega}(1)$\xspace  independently\xspace trained\xspace models\xspace of\xspace $F$\xspace  with\xspace $m=\polylog(k)$\xspace  for\xspace $T = O\big(\frac{\poly(k)}{\eta}\big)$\xspace  iterations\xspace (i\xspace.e\xspace., the\xspace same\xspace setting\xspace as\xspace \seduciamo{thm:single} except\xspace we\xspace only\xspace need\xspace a\xspace small\xspace over\xspace-parameterization\xspace $m=\polylog(k)$\xspace ). Let\xspace us\xspace define\xspace their\xspace ensemble\xspace
\begin{align} \label{eq:ens

Our\xspace next\xspace theorem\xspace states\xspace that\xspace the\xspace ensemble\xspace model\xspace has\xspace much\xspace higher\xspace test\xspace accuracy\xspace.
\begin{reptheorem}{thm:ensemble}[ensemble]
In\xspace the\xspace same\xspace setting\xspace as\xspace above\xspace, we\xspace have\xspace for\xspace the\xspace ensemble\xspace model\xspace $G$\xspace  in\xspace \eqref{eq:ens}, with\xspace probability\xspace at\xspace least\xspace $1-e^{-\Omega(\log^2 k)}$\xspace :
\begin{itemize}
\item (training\xspace accuracy\xspace is\xspace perfect)\xspace: meaning\xspace for\xspace all\xspace $(X, y) \in \motosilurante{Z}$\xspace ,  for\xspace all\xspace $i \in [k]\setminus\{y\}$\xspace : $G_y(X)  > G_i(X)$\xspace .
\item (test\xspace accuracy\xspace is\xspace good)\xspace: meaning\xspace that\xspace:
\isocronico
\end{itemize}
\end{reptheorem}

\noindent
As\xspace we\xspace discussed\xspace in\xspace \equoreo{sec:intro:our}, the\xspace reason\xspace \seduciamo{thm:ensemble} holds\xspace attributes\xspace to\xspace the\xspace fact\xspace that\xspace those\xspace lottery\xspace winning\xspace sets\xspace $\motosilurante{M}$\xspace  depend\xspace on\xspace the\xspace random\xspace initialization\xspace of\xspace the\xspace networks\xspace; and\xspace therefore\xspace, when\xspace multiple\xspace models\xspace are\xspace put\xspace together\xspace, their\xspace ``union\xspace'' of\xspace $\motosilurante{M}$\xspace  shall\xspace cover\xspace all\xspace possible\xspace features\xspace $\{v_{i,\ell}\}_{(i,\ell)\in[k]\times [2]}$\xspace . Moreover\xspace, our\xspace theorem\xspace only\xspace requires\xspace individual\xspace $K = \tilde{\Omega}(1)$\xspace  models\xspace for\xspace ensemble\xspace, which\xspace is\xspace indeed\xspace ``averaging\xspace the\xspace output\xspace of\xspace \emph{a\xspace few\xspace} independently\xspace trained\xspace models\xspace''.

\rintiepidendo{Roadmap\xspace} We\xspace shall\xspace restate\xspace
and\xspace prove\xspace the\xspace general\xspace versions\xspace of\xspace \seduciamo{thm:single} and\xspace \ref{thm:ensemble} in\xspace \antinfiammatoria{app:single-main}, after\xspace establishing\xspace core\xspace lemmas\xspace in\xspace \antinfiammatoria{app:single-model} and\xspace \ref{app:single-proof}.

\subsection{Knowledge Distillation for Ensemble}

We\xspace consider\xspace a\xspace knowledge\xspace distillation\xspace algorithm\xspace given\xspace the\xspace existing\xspace ensemble\xspace model\xspace $G$\xspace  (see\xspace \eqref{eq:ens}) as\xspace follows\xspace.
For\xspace every\xspace label\xspace $i\in[k]$\xspace , let\xspace us\xspace define\xspace the\xspace truncated\xspace scaled\xspace logit\xspace as\xspace (for\xspace $\tau = \frac{1}{\log^2 k}$\xspace ):
\begin{align}\label{eqn:logit-thres
(This\xspace logit\xspace function\xspace should\xspace be\xspace reminiscent\xspace of\xspace the\xspace logit\xspace function\xspace with\xspace temperature\xspace used\xspace by\xspace the\xspace original\xspace knowledge\xspace distillation\xspace work\xspace \cite{hinton2015distilling}; we\xspace use\xspace truncation\xspace instead\xspace which\xspace is\xspace easier\xspace to\xspace analyze\xspace.)

Now\xspace, we\xspace train\xspace a\xspace new\xspace network\xspace $F$\xspace  from\xspace random\xspace initialization\xspace (where\xspace the\xspace randomness\xspace is\xspace independent\xspace of\xspace all\xspace of\xspace those\xspace used\xspace in\xspace $F^{[\ell]}$\xspace ). At\xspace every\xspace iteration\xspace $t$\xspace , we\xspace update\xspace each\xspace weight\xspace $w_{i, r}$\xspace  by\xspace:
\begin{align}\label{eqn:distill

\rintiepidendo{Notation\xspace}
Throughout\xspace the\xspace paper\xspace we\xspace denote\xspace by\xspace $[a]^+ = \max\{0,a\}$\xspace  and\xspace $[a]^- = \min\{0,a\}$\xspace .

This\xspace knowledge\xspace distillation\xspace method\xspace \eqref{eqn:distill} is\xspace almost\xspace identical\xspace to\xspace the\xspace one\xspace used\xspace in\xspace the\xspace original\xspace work~\cite{hinton2015distilling}, except\xspace we\xspace use\xspace a\xspace truncation\xspace during\xspace the\xspace training\xspace to\xspace make\xspace it\xspace more\xspace (theoretically)\xspace stable\xspace. Moreover\xspace, we\xspace update\xspace the\xspace distillation\xspace objective\xspace using\xspace a\xspace larger\xspace learning\xspace rate\xspace $\eta'$\xspace  comparing\xspace to\xspace $\eta$\xspace  of\xspace the\xspace cross\xspace-entropy\xspace objective\xspace. This\xspace is\xspace also\xspace consistent\xspace with\xspace the\xspace training\xspace schedule\xspace used\xspace in~\cite{hinton2015distilling}.

Let\xspace $F^{(t)}$\xspace  be\xspace the\xspace resulting\xspace network\xspace obtained\xspace by\xspace \eqref{eqn:distill} at\xspace iteration\xspace $t$\xspace . We\xspace have\xspace the\xspace following\xspace theorem\xspace:

\begin{reptheorem}{thm:ensemble_distill}[ensemble distillation]
Consider\xspace the\xspace distillation\xspace algorithm\xspace \eqref{eqn:distill} in\xspace which\xspace $G$\xspace  is\xspace the\xspace ensemble\xspace model\xspace defined\xspace in\xspace \eqref{eq:ens}.
For\xspace every\xspace $k > 0$\xspace , for\xspace $m =\polylog(k)$\xspace , for\xspace every\xspace $\eta \leq \frac{1}{\poly(k)}$\xspace , setting\xspace $\eta' = \eta \poly(k)$\xspace , after\xspace $T =  \frac{\poly(k)}{\eta}$\xspace  many\xspace iterations\xspace with\xspace probability\xspace at\xspace least\xspace $1-e^{-\Omega(\log^2 k)}$\xspace , for\xspace at\xspace least\xspace 90\% of\xspace the\xspace iterations\xspace $t\leq T$\xspace :
\begin{itemize}
\item (training\xspace accuracy\xspace is\xspace perfect)\xspace: meaning\xspace for\xspace all\xspace $(X, y) \in \motosilurante{Z}$\xspace ,  all\xspace $i \in [k]\setminus\{y\}$\xspace : $F_y^{(t)}(X)  > F_i^{(t)}(X)$\xspace .

\item (test\xspace accuracy\xspace is\xspace good)\xspace: meaning\xspace that\xspace:
\stereoisomero
\end{itemize}
\end{reptheorem}

\noindent
We\xspace shall\xspace restate\xspace the\xspace general\xspace version\xspace of\xspace \seduciamo{thm:ensemble_distill} in\xspace \antinfiammatoria{app:distill-statement}, and\xspace prove\xspace it\xspace in\xspace \antinfiammatoria{app:distill}.

\subsection{Self Knowledge Distillation as implicit Ensemble}\label{sec:self}

Self\xspace distillation\xspace \cite{furlanello2018born,mobahi2020self} refers\xspace to\xspace training\xspace a\xspace single\xspace model\xspace to\xspace match\xspace the\xspace output\xspace of\xspace another\xspace single\xspace model\xspace.
In\xspace this\xspace paper\xspace we\xspace also\xspace show\xspace that\xspace self\xspace-distillation\xspace can\xspace also\xspace improve\xspace test\xspace accuracy\xspace under\xspace our\xspace multi\xspace-view\xspace setting\xspace. Let\xspace us\xspace consider\xspace the\xspace following\xspace self\xspace-distillation\xspace algorithm\xspace.

Let\xspace $F = F^{(T)},G = G^{(T)}$\xspace  be\xspace two\xspace single\xspace models\xspace trained\xspace in\xspace the\xspace same\xspace setting\xspace as\xspace \seduciamo{thm:single} using\xspace independent\xspace random\xspace initializations\xspace. We\xspace scale\xspace them\xspace up\xspace by\xspace a\xspace small\xspace factor\xspace $\tilde{\Theta}(1)$\xspace  similar\xspace to\xspace \eqref{eq:ens}.
Then\xspace, starting\xspace from\xspace $F^{(T)}$\xspace , we\xspace apply\xspace the\xspace following\xspace updates\xspace for\xspace another\xspace $T'$\xspace  iterations\xspace:
\begin{align}\label{eqn:distill2

This\xspace objective\xspace is\xspace considered\xspace as\xspace ``self\xspace-distillation\xspace'' since\xspace $G$\xspace  is\xspace an\xspace individual\xspace model\xspace (trained\xspace using\xspace an\xspace identical\xspace manner\xspace as\xspace $F$\xspace , only\xspace from\xspace a\xspace different\xspace random\xspace initialization)\xspace. In\xspace particular\xspace, if\xspace $F = G$\xspace , then\xspace $  \mathbf{logit}_{i}^{\tau}(F^{(t)}, X)  -\mathbf{logit}_{i}^{\tau}(G, X) = 0 $\xspace  so\xspace the\xspace weights\xspace are\xspace no\xspace longer\xspace updated\xspace. However\xspace, as\xspace we\xspace will\xspace actually\xspace prove\xspace, this\xspace training\xspace objective\xspace will\xspace actually\xspace learn\xspace an\xspace $F$\xspace  that\xspace \emph{has\xspace better\xspace generalization\xspace comparing\xspace to\xspace $G$\xspace }.

This\xspace time\xspace, \emph{for\xspace simplicity\xspace}, let\xspace us\xspace make\xspace the\xspace following\xspace additional\xspace assumption\xspace on\xspace the\xspace data\xspace:
\begin{assumption}[balanced $\mathcal{D}_m$]\label{ass:balanced}
In\xspace \scocciatore{def:dist}, for\xspace multi\xspace-view\xspace data\xspace $(X,y)$\xspace , we\xspace additionally\xspace assume\xspace that\xspace the\xspace marginal\xspace distributions\xspace of\xspace $\sum_{p \in \motosilurante{P}_v(X)} z_p^q \in [1, O(1)]$\xspace  for\xspace $v \in \{ v_{y, 1}, v_{y, 2} \}$\xspace .
\end{assumption}

The\xspace rationale\xspace for\xspace this\xspace assumption\xspace is\xspace quite\xspace simple\xspace. Suppose\xspace $\motosilurante{M}$\xspace  is\xspace the\xspace aforementioned\xspace ``lottery\xspace winning\xspace'' set\xspace of\xspace training\xspace a\xspace single\xspace model\xspace without\xspace knowledge\xspace distillation\xspace.
\occultatore{ass:balanced} will\xspace ensure\xspace that\xspace each\xspace $(i,1)$\xspace  and\xspace $(i,2)$\xspace  will\xspace belong\xspace to\xspace $\motosilurante{M}_F$\xspace  with\xspace equal\xspace probability\xspace. If\xspace we\xspace train\xspace two\xspace models\xspace $F$\xspace  and\xspace $G$\xspace , their\xspace combined\xspace lottery\xspace winning\xspace set\xspace $\motosilurante{M}_F \cup \motosilurante{M}_G$\xspace  shall\xspace be\xspace of\xspace cardinality\xspace around\xspace $\frac{3}{2}k(1-o(1))$\xspace . Therefore\xspace, if\xspace we\xspace can\xspace distill\xspace the\xspace knowledge\xspace of\xspace $G$\xspace  to\xspace $F$\xspace , the\xspace test\xspace accuracy\xspace can\xspace be\xspace improved\xspace from\xspace $1 - \frac{1}{2}\mu$\xspace  to\xspace $1 - \frac{1}{4}\mu$\xspace . See\xspace the\xspace following\xspace theorem\xspace:%
\footnote{\label{footnote:balanced}%
One\xspace can\xspace trivially\xspace relax\xspace \occultatore{ass:balanced} so\xspace that\xspace the\xspace two\xspace views\xspace have\xspace different\xspace distributions\xspace but\xspace with\xspace a\xspace constant\xspace ratio\xspace between\xspace their\xspace expectations\xspace; in\xspace this\xspace way\xspace the\xspace improved\xspace accuracy\xspace is\xspace no\xspace longer\xspace $1 - \frac{1}{4}\mu$\xspace  but\xspace shall\xspace depend\xspace on\xspace this\xspace constant\xspace ratio\xspace. For\xspace simplicity\xspace of\xspace this\xspace paper\xspace, we\xspace do\xspace not\xspace state\xspace the\xspace result\xspace of\xspace that\xspace more\xspace general\xspace case\xspace.}

\begin{reptheorem}{thm:self_distill}[self-distillation]
Under\xspace this\xspace additional\xspace \occultatore{ass:balanced}, consider\xspace the\xspace distillation\xspace algorithm\xspace \eqref{eqn:distill2} where\xspace $G$\xspace  is\xspace an\xspace independently\xspace trained\xspace single\xspace model\xspace (in\xspace the\xspace same\xspace setting\xspace as\xspace \seduciamo{thm:single}).
For\xspace every\xspace $k > 0$\xspace , every\xspace $m \in [\polylog(k), k]$\xspace , every\xspace $\eta \leq \frac{1}{\poly(k)}$\xspace , after\xspace $T' =  \frac{\poly(k)}{\eta}$\xspace  many\xspace iterations\xspace of\xspace algorithm\xspace \eqref{eqn:distill2}, with\xspace probability\xspace at\xspace least\xspace $1-e^{-\Omega(\log^2 k)}$\xspace :
\begin{itemize}
\item (training\xspace accuracy\xspace is\xspace perfect)\xspace: meaning\xspace for\xspace all\xspace $(X, y) \in \motosilurante{Z}$\xspace ,  all\xspace $i \neq y$\xspace : $F_y^{(T+T')}(X)  > F_i^{(T+T')}(X)$\xspace .

\item (test\xspace accuracy\xspace is\xspace better)\xspace: meaning\xspace that\xspace:
$$\Pr_{(X, y) \sim \mathcal{D}}[ \exists i \in [k] \setminus\{y\}\colon  F_y^{(T+T')} (X) < F_i^{(T+T')} (X) ] \leq 0.26 \mu$$
\end{itemize}
\end{reptheorem}

\noindent
Recall\xspace from\xspace \seduciamo{thm:single}, all\xspace individual\xspace models\xspace should\xspace have\xspace test\xspace error\xspace at\xspace least\xspace $0.49 \mu \gg 0.26 \mu$\xspace . Hence\xspace the\xspace model\xspace $F$\xspace  generalizes\xspace better\xspace (comparing\xspace to\xspace both\xspace the\xspace original\xspace model\xspace $F$\xspace  before\xspace self\xspace-distillation\xspace and\xspace the\xspace individual\xspace model\xspace $G$\xspace ) after\xspace self\xspace-distillation\xspace to\xspace the\xspace individual\xspace model\xspace $G$\xspace . We\xspace shall\xspace restate\xspace the\xspace general\xspace version\xspace of\xspace \seduciamo{thm:self_distill} in\xspace \antinfiammatoria{app:distill-statement}, and\xspace prove\xspace it\xspace in\xspace \antinfiammatoria{app:distill}.

\paragraph{Why\xspace does\xspace self\xspace-distillation\xspace improve\xspace test\xspace accuracy\xspace? -- \textcolor{blue}{Self-distillation is performing implicit ensemble + knowledge distillation:}} As\xspace the\xspace main\xspace idea\xspace of\xspace behind\xspace the\xspace proof\xspace, we\xspace actually\xspace show\xspace that\xspace self\xspace-distillation\xspace is\xspace performing\xspace implicit\xspace ensemble\xspace together\xspace with\xspace knowledge\xspace distillation\xspace. In\xspace particular\xspace, let\xspace $\motosilurante{M}_F, \motosilurante{M}_G \subseteq{V}$\xspace  be\xspace the\xspace features\xspace learned\xspace by\xspace individual\xspace models\xspace $F, G$\xspace  starting\xspace from\xspace (independent)\xspace random\xspace initializations\xspace $W_F^{(0)}$\xspace  and\xspace $W_G^{(0)}$\xspace  respectively\xspace when\xspace trained\xspace on\xspace the\xspace original\xspace data\xspace set\xspace, now\xspace, if\xspace we\xspace further\xspace train\xspace the\xspace individual\xspace model\xspace $F$\xspace  to\xspace match\xspace the\xspace output\xspace of\xspace individual\xspace model\xspace $G$\xspace , $F$\xspace  is\xspace actually\xspace going\xspace to\xspace learn\xspace a\xspace larger\xspace set\xspace of\xspace features\xspace $\motosilurante{M}_G \cup \motosilurante{M}_F$\xspace , where\xspace features\xspace in\xspace $\motosilurante{M}_F$\xspace  come\xspace from\xspace gradient\xspace of\xspace the\xspace original\xspace objective\xspace, and\xspace features\xspace in\xspace $\motosilurante{M}_G$\xspace  come\xspace from\xspace the\xspace gradient\xspace of\xspace the\xspace knowledge\xspace distillation\xspace objective\xspace w\xspace.r\xspace.t\xspace. $G$\xspace . This\xspace is\xspace equivalent\xspace to\xspace first\xspace ensemble\xspace $F$\xspace  and\xspace $G$\xspace , then\xspace train\xspace an\xspace additional\xspace model\xspace $H$\xspace  from\xspace random\xspace initialization\xspace to\xspace match\xspace the\xspace ensemble\xspace --- Self\xspace-distillation\xspace implicitly\xspace merge\xspace ``ensemble\xspace individual\xspace models\xspace $F$\xspace , $G$\xspace  and\xspace distill\xspace the\xspace ensemble\xspace to\xspace another\xspace individual\xspace model\xspace $H$\xspace ''  into\xspace ``ensemble\xspace individual\xspace models\xspace $F$\xspace , $G$\xspace  and\xspace distill\xspace the\xspace ensemble\xspace to\xspace the\xspace individual\xspace model\xspace $F$\xspace '' since\xspace $F$\xspace  and\xspace $H$\xspace  have\xspace the\xspace same\xspace structure\xspace. Then\xspace eventually\xspace it\xspace is\xspace merged\xspace directly\xspace into\xspace ``training\xspace an\xspace individual\xspace model\xspace  $F$\xspace  via\xspace self\xspace-distillation\xspace to\xspace match\xspace the\xspace output\xspace of\xspace an\xspace individual\xspace model\xspace  $G$\xspace ''.

\section{Discussion: Ensemble and Knowledge Distillation}

In\xspace this\xspace work\xspace, we\xspace show\xspace, to\xspace the\xspace best\xspace of\xspace our\xspace knowledge\xspace, the\xspace first\xspace theoretical\xspace result\xspace towards\xspace understanding\xspace how\xspace ensemble\xspace work\xspace in\xspace deep\xspace learning\xspace. As\xspace our\xspace main\xspace contribution\xspace, we\xspace provide\xspace empirical\xspace evidence\xspace that\xspace ensemble\xspace might\xspace work\xspace very\xspace differently\xspace in\xspace deep\xspace learning\xspace comparing\xspace to\xspace ensemble\xspace in\xspace random\xspace feature\xspace models\xspace. Moreover\xspace, ensemble\xspace does\xspace not\xspace always\xspace improve\xspace test\xspace accuracy\xspace in\xspace deep\xspace learning\xspace, especially\xspace when\xspace the\xspace input\xspace data\xspace comes\xspace from\xspace Gaussian\xspace-like\xspace distribution\xspace.

Motivated\xspace by\xspace these\xspace empirical\xspace observations\xspace, we\xspace propose\xspace a\xspace generic\xspace structure\xspace of\xspace the\xspace data\xspace we\xspace refer\xspace to\xspace as\xspace multi\xspace-view\xspace, and\xspace prove\xspace that\xspace ensemble\xspace improves\xspace test\xspace accuracy\xspace for\xspace two\xspace-layer\xspace neural\xspace networks\xspace in\xspace this\xspace setting\xspace. Moreover\xspace, we\xspace also\xspace prove\xspace that\xspace ensemble\xspace model\xspace can\xspace be\xspace distilled\xspace into\xspace a\xspace single\xspace model\xspace. Meaning\xspace that\xspace, through\xspace training\xspace a\xspace single\xspace model\xspace to\xspace ``simulate\xspace'' the\xspace output\xspace of\xspace the\xspace ensemble\xspace over\xspace the\xspace same\xspace training\xspace data\xspace set\xspace, single\xspace model\xspace is\xspace able\xspace to\xspace match\xspace the\xspace test\xspace accuracy\xspace of\xspace the\xspace ensemble\xspace, and\xspace thus\xspace being\xspace superior\xspace to\xspace any\xspace single\xspace model\xspace that\xspace is\xspace clean\xspace, directly\xspace trained\xspace on\xspace the\xspace original\xspace data\xspace's\xspace labels\xspace.

We\xspace believe\xspace that\xspace our\xspace framework\xspace can\xspace be\xspace applied\xspace to\xspace other\xspace settings\xspace as\xspace well\xspace, for\xspace example\xspace, data\xspace augmentation\xspace using\xspace random\xspace cropping\xspace could\xspace be\xspace potentially\xspace regarded\xspace as\xspace another\xspace way\xspace to\xspace enforce\xspace the\xspace network\xspace to\xspace learn\xspace ``multi\xspace-views\xspace''. We\xspace hope\xspace that\xspace our\xspace new\xspace theoretical\xspace insights\xspace on\xspace how\xspace neural\xspace network\xspace pick\xspace up\xspace features\xspace during\xspace the\xspace training\xspace process\xspace can\xspace also\xspace help\xspace in\xspace practice\xspace to\xspace design\xspace new\xspace, principled\xspace approach\xspace to\xspace improve\xspace test\xspace accuracy\xspace of\xspace a\xspace neural\xspace network\xspace, potentially\xspace matching\xspace that\xspace of\xspace the\xspace ensemble\xspace.

\bigskip

redpajama_set_name: RedPajamaArXiv