\section{Overview and main result}

Deep networks trained with gradient descent seem to have no trouble adapting
to arbitrary prediction problems, and are steadily displacing stalwart methods across
many domains.
In this work,
we provide a mathematical basis for this good performance
on arbitrary binary classification problems,
considering the simplest possible networks:
shallow ReLU networks where only the inner (input-facing) weights are trained
via vanilla gradient descent with a constant step size.
The central contributions are as follows.

\begin{enumerate}
  \item
    \textbf{Fully general classification tasks.}
    The joint distribution generating the $(x,y)$ pairs only requires $x$ to be bounded,
    and is otherwise arbitrary.  In particular, the underlying distribution may be noisy,
    meaning the true conditional model of the labels, $\Pr[Y=1 | X=x]$, is arbitrary.
    
    In this setting, we show that as data, width, and training time increase,
    the logistic loss \emph{measured over the population} converges
    to optimality over all measurable functions, which moreover implies that
    the induced conditional model (defined by a sigmoid mapping) converges to the true model,
    and the population misclassification rate also converges to optimality.
This is in contrast with prior analyses of gradient descent, which either only
    consider the training risk
    \citep{allen_deep_opt,du_iclr,zou_deep_opt,oymak_moderate,song_quadratic},
    or can only handle restricted conditional models
    \citep{allen_3_gen,arora_2_gen,cao_deep_gen,nitanda_refined,ziwei_ntk,gu_polylog}.

  \item
    \textbf{Adaptivity to data simplicity.}
    The required number of data samples, network nodes,
    and gradient descent iterations all shrink
    if the \emph{distribution}
    satisfies a natural notion of simplicity: the true conditional model $\Pr[Y=1|X=x]$ is 
    approximated well by a low-complexity infinite-width random feature model.

\end{enumerate}

Rounding out the story and contributions,
firstly we present a brief toy univariate model hinting towards
the necessity of early stopping: concretely,
any univariate predictor satisfying a \emph{local interpolation property} can not achieve
optimal test error for noisy distributions.
Secondly, our analysis is backed by a number of lemmas that could
be useful elsewhere; amongst these are a
\emph{multiplicative error} property of the logistic loss,
and separately a technique to control the effects of large network
width over not just a finite sample, but over the entire sphere.




\subsection{Main result: optimal test error via gradient descent}

The goal in this work is to minimize the logistic risk over the population:
letting $\mu$ denote an arbitrary Borel measure over $(x,y)$ pairs with compactly-supported 
marginal $\mu_x$ and
conditional $p_y$, with a data sample $((x_i,y_i))_{i=1}^n$, and a function $f$, define the
logistic loss,
empirical logistic risk, 
and logistic risk respectively as
\[
  \ell(r) := \ln(1+e^{-r}),
  \qquad
  \hcR(f) := \frac 1 n \sum_{k=1}^n \ell(y_kf(x_k)),
  \qquad
  \cR(f) := \bbE_{x,y} \ell(yf(x)).
\]
We use the logistic loss not only due to its practical prevalence,
but also due to an interesting multiplicative error property which strengthens our main results
(cf. \Cref{fact:logistic:error} and \Cref{fact:main}),
all while being Lipschitz.

We seek to make the risk $\cR(f)$ as small as possible: formally, we compare against
the Bayes risk
\[
  \overline{\cR} := \inf\cbr{ \cR(f)\ {}:\ {}\textup{measurable } f\!:\!\R^d \to \R}.
\]
While competing with $\overline{\cR}$ may seem a strenuous goal, in fact it simplifies many 
aspects of the learning task.
Firstly, due to the universal approximation properties of neural networks
\citep{funahashi_apx,nn_stone_weierstrass,cybenko,barron_nn},
we are effectively working over the space of all measurable functions already.
Secondly, as will be highlighted in the main result below,
via the theory of classification calibration
\citep{zhang_convex_consistency,bartlett_jordan_mcauliffe},
competing with the Bayes (convex) risk also recovers the true conditional model,
and minimizes the misclassification loss;
this stands in contrast with the ostensibly more modest goal of minimizing misclassification
over a restricted class of predictors, namely the \emph{agnostic learning} setting,
which suffers a variety of computational and statistical obstructions
\citep{pmlr-v119-goel20a,surbhi_hardness,ohad_relu_gd,frei_agnostic}.

Our predictors are shallow ReLU networks, trained via gradient descent --- the simplest
architecture which is not convex in its parameters, but satisfies universal approximation.
In detail,
letting $(a_j)_{j=1}^m$
be uniformly random $\pm 1$ signs, $(w_j)_{j=1}^m$ with $w_j\in\R^d$ be standard Gaussians,
and $\rho>0$ be a \emph{temperature},
we predict on an input $x\in\R^d$ with
\[
  f(x;\rho, a,W) := f(x;W) := \frac {\rho}{\sqrt m}\sum_{j=1}^m a_j \srelu(w_j^\T x),
\]
where $\srelu(z):=\max\{0,z\}$ is the ReLU; since only $W$ is trained, both $\rho$ and $a$ are
often dropped.  To train, we perform gradient descent with a constant step size
on the empirical risk:
\[
  W_{i+1} := W_i - \eta \nhcR(W_i),
  \qquad\textup{where }
  \hcR(W) := \hcR\del{ x\mapsto f(x; W) }.
\]
Our guarantees are for an iterate with small empirical risk and small norm:
$W_{\leq t} := \argmin\{ \hcR(W_i) : i\leq t, \|W_i-W_0\|\leq R_{\textup{gd}}\}$,
where $R_{\textup{gd}}$ is our \emph{early stopping radius}:
if $R_{\textup{gd}}$ is guessed correctly, our rates improve, but our analysis also
handles the case $R_{\textup{gd}}=\infty$ where no guess is made, and indeed this is used
in our final consistency analysis
(a pessimistic, fully general setting).

Our goal is to show that this iterate $W_{\leq t}$ has approximately optimal
\emph{population} risk: $\cR(W_{\leq t}) \approx \overline{\cR}$.
Certain prediction problems may seem simpler than others, and we want our analysis 
to reflect this while abstracting away as many coincidences of the training process as
possible.  Concretely, we measure simplicity via the performance and complexity
of an infinite-width random feature model over the true distribution, primarily based on the
following considerations.
\begin{itemize}
  \item
    By measuring performance over the population,
    random effects of the training sample are removed, and it is impossible
    for the random feature model to simply revert to memorizing data,
    as it never sees that training data.
  \item
    The random feature model has infinite width, and via sampling can be used as a benchmark
    for all possible widths simultaneously, but is itself freed from coincidences
    of random weights.
\end{itemize}

In detail, our infinite-width random feature model is as follows.
Let $\overline U_{\!\infty} :\R^d\to\R^d$ be an (uncountable) collection of weights
(indexed by $\R^d$), and define a prediction mapping via
\[
  f(x;\overline U_{\!\infty}) := \int \ip{\overline U_{\!\infty}(v)}{x\1[v^\T x\geq 0]}\dif\cN(v),
  \qquad
  \text{whereby }
  \cR(\overline U_{\!\infty}) := \cR(x\mapsto f(x;\overline U_{\!\infty})).
\]
Note that for each Gaussian random vector $v\sim \cN$, we construct a \emph{random feature}
$x\mapsto x\1[v^\T x\geq 0]$.  This particular choice is simply the gradient of a corresponding
ReLU $\nabla_v \srelu(v^\T x)$, and is motivated by the NTK literature
\citep{jacot_ntk,li_liang_nips,du_iclr}.
A similar object has appeared before in NTK convergence analyses
\citep{nitanda_refined,ziwei_ntk},
but the conditions on $\overline U_{\!\infty}$ were always strong (e.g., data separation with a margin).

What, then, does it mean for the data to be simple?  In this work, it is when there exists
a $\overline U_{\!\infty}$ with $\cR(\overline U_{\!\infty})\approx \overline{\cR}$, and moreover $\overline U_{\!\infty}$ has low norm; for technical
convenience, we measure the norm as the maximum over individual weight norms,
meaning $\sup_v \|\overline U_{\!\infty}(v)\|$.  To measure approximability, for sake of interpretation,
we use the \emph{binary Kullback-Leibler divergence (KL)}:
defining a conditional probability model $\phi_\infty$ corresponding to $\overline U_{\!\infty}$ via
\[
  \phi_\infty(x) := \phi(f(x;\overline U_{\!\infty})), \qquad\textup{where } \phi(r) := \frac {1}{1+\exp(-r)},
\]
then the binary KL can be written as
\[
  \cK_{\textup{bin}}(p_y, \phi_\infty) :=
  \int\del{p_y \ln\frac {p_y}{\phi_\infty} + (1-p_y)\ln\frac {1-p_y}{1-\phi_\infty}}\dif\mu_x
  = \cR(\overline U_{\!\infty}) - \overline{\cR}.
\]
This relationship between binary KL and the excess risk is a convenient property
of the logistic loss, which immediately implies calibration as a consequence of achieving
the optimal risk. 

The pieces are all in place to state our main result.

\begin{theorem}\label{fact:main}
  Let width $m\geq \ln(emd)$,
  temperature $\rho > 0$,
  and reference model
  $\overline U_{\!\infty}$ be given with $R := \max\{4, \rho, \sup_v\|\overline U_{\!\infty}(v)\|\}<\infty$,
  and define a corresponding conditional model $\phi_\infty(x) := \phi(f(x;\overline U_{\!\infty}))$.
  Let optimization accuracy $\eps_{\textup{gd}}$ and radius $R_{\textup{gd}}\geq R/\rho$
  be given,
  define effective radius
  $B := \min\cbr[1]{R_{\textup{gd}},\ {}\frac{3R}{\rho} + \frac{4e}{\rho} \sqrt{t}\sqrt{e^{\tau_0}\cR(\overline U_{\!\infty}) + R\tau_n} }$,
  and generalization, linearization, and sampling errors
  $(\tau_n,\tau_1,\tau_0)$ as
  \begin{align*}
    \tau_n :=
\tcO\del{\frac{(d\ln(1/\delta))^{3/2}}{\sqrt n}}\!\!,
\ \tau_1 :=
\tcO\del{\frac{\rho B^{4/3}\sqrt{d\ln(1/\delta)}}{m^{1/6}}}\!\!,
\ \tau_0
    :=
\tcO\del{\rho \ln(1/\delta) + \frac {\sqrt{d\ln(1/\delta)}}{m^{1/4}}}\!\!,
  \end{align*}
  where it is assumed $\tau_1\leq 2$, and $\tcO$ hides constants and $\ln(nmd)$.
  Choose step size $\eta := 4/\rho^2$, and run gradient descent
  for $t:=1/(8\eps_{\textup{gd}})$ iterations, selecting iterate
  $W_{\leq t} :=\argmin\{\hcR(W_i) : i \leq t, \|W_i-W_0\|\leq R_{\textup{gd}}\}$.
Then, with probability at least $1-25\delta$,
  \begin{align*}
& \cR(W_{\leq t}) - \overline{\cR}
    &\text{(logistic error)}\phantom{.}
    \\
  \leq\qquad& \cK_{\textup{bin}}(p_y, \phi_{\infty}) + \del[1]{e^{\tau_1 + \tau_0} - 1}\cR(\overline U_{\!\infty})
            &\text{(reference model error)}\phantom{.}
            \\
  + \quad & e^{\tau_1} R^2 \eps_{\textup{gd}}
          &\text{(optimization error)}\phantom{.}
          \\
  + \quad &
e^{\tau_1} (\rho B + R)\tau_n
          & \hspace{2em}\text{(generalization error)},\\
          \intertext{where the classification and calibration errors satisfy}
& {}\cR(W_{\leq t}) - \overline{\cR}
    &\text{(logistic error)}\phantom{.}
    \\
            \geq \qquad& 2\int \del{\phi(f(x;W_{\leq t})) - p_y}^2\dif\mu_x(x)
               &\text{(calibration error)}\phantom{.}
               \\
   \geq \qquad &\frac 1 2 \del{ \cRz(W_{\leq t}) - \overline{\cR}_{\textup{z}}}^2
                &\text{(classification error)}.
  \end{align*}
  Lastly, for any $\epsilon > 0$, there exists $\overline U_{\!\infty}^{(\eps)}$
  with $\sup_v \|\overline U_{\!\infty}^{(\eps)}(v)\|<\infty$
  and whose conditional model $\phi_{\infty}^{(\eps)}(x) := \phi(f((x,1)/\sqrt{2};\overline U_{\!\infty}^{(\eps)}))$
  satisfies $\cK_{\textup{bin}}(p_y, \phi_{\infty}^{(\eps)}) \leq \epsilon$.
\end{theorem}



\begin{remark}\label{rem:main}
  The key properties of \Cref{fact:main} are as follows.

  \begin{enumerate}


    \item
      \textbf{(Achieving error $\cO(\eps)$ in three different regimes.)}
      As \Cref{fact:main} is quite complicated, consider three different situations,
      which vary the reference model $\overline U_{\!\infty}$ and its norm upper bound
      $R := \max\{4, \rho, \sup_v\|\overline U_{\!\infty}(v)\|\}<\infty$,
      as well as the early stopping radius $R_{\textup{gd}}$.  Let target population (excess)
      risk $\eps>0$
      be given, set $\eps_{\textup{gd}} = \eps$ and $t = 1/(8\eps_{\textup{gd}})$ as in \Cref{fact:main},
      and suppose $n \geq 1/\eps^2$ samples: in each of the
      three following settings,
      the other parameters parameters (namely $\rho$ and $m$) will be chosen
      to ensure a final error $\cR(W_{\leq t}) - \overline{\cR} = \cO(\eps)$.

      \begin{enumerate}
        \item
          \textbf{(Easy data.)}  Suppose a setting with \emph{easy data}:
          specifically, suppose that for chosen target accuracy $\eps>0$,
          there exists $\overline U_{\!\infty}$ with
          $\cK_{\textup{bin}}(p_y, \phi_\infty) = \cR(\overline U_{\!\infty}) - \overline{\cR} \leq \cR(\overline U_{\!\infty}) \leq \eps$.
          If we set $\rho = 1$ and $m \geq R^8$, then $(\tau_n,\tau_1,\tau_0)$ are all
          constant, and we get a final bound
          $\cR(W_{\leq t}) - \overline{\cR} = \cO(\eps)$.

          Note crucially that $m \approx R^8$ sufficed for this setting; this was
          a goal of the present analysis, as it recovers the \emph{polylogarithmic width}
          analyses from prior work \citep{ziwei_ntk,gu_polylog}.
          Those works however either used a separation condition due to
          \citet{nitanda_refined} in the shallow case, or an assumption on the approximation
          properties of the sampled weights (a random variable) in the deep case, and thus the
          present analysis provides not just a re-proof, but a simplification and generalization.
          This was the motivation for the strange \emph{multiplicative} form of the errors
          in \Cref{fact:main}: had we used the more common additive errors with standard
          linearization tools, a polylogarithmic
          width proof would fail.

        \item
          \textbf{(General data, clairvoyant early stopping radius $R_{\textup{gd}}$.)}
          Suppose that we are in the general noisy case, meaning
          any $\overline U_{\!\infty}$ we pick has a large error
          $\cK_{\textup{bin}}(p_y, \phi_\infty)$, but we magically know the
          $R$ corresponding to a good $\overline U_{\!\infty}$, and can choose $R_{\textup{gd}} = R/\rho$.
          Unlike the previous case, to achieve some target error $\eps$,
          we need to work harder to control the term $\sbr{\exp(\tau_1+\tau_0) - 1}\cR(\overline U_{\!\infty})$,
          since we no longer have small $\cR(\overline U_{\!\infty})$; to this end,
          since $\tau_1 =\tcO(R^{4/3} / (m \rho^2)^{1/6})$ and $\tau_0 = \tcO(\rho + 1/m^{1/4})$,
          choosing $\rho = m^{-1/8}$ and $m = 1/\eps^{8}$ gives
          $\tau_1=\tcO(\eps)$ and $\tau_0 = \tcO(\eps)$, and together
          $\cR(W_{\leq t}) - \overline{\cR} = \cO(\eps)$.

        \item
          \textbf{(General data, worst-case early stopping.)}
          Suppose again the case of general noisy data
          with large error
          $\cK_{\textup{bin}}(p_y, \phi_\infty)$ for any $\overline U_{\!\infty}$ we pick,
          but now suppose we have
          no early stopping hint,
          and pessimistically set $R_{\textup{gd}} = \infty$.
          As a consequence of all of this,
          the term $B$ can scale as $t^{2/3}/\rho= 1 / (\rho \eps^{2/3})$,
          thus to control $\tau_1 = \tcO( (1/\eps)^{2/3} / (m\rho^2)^{1/6})$ and 
          $\tau_0 = \tcO(\rho + 1/m^{1/4})$,
          we can again choose $\rho = m^{-1/8}$, but need a larger width
          $m = 1/\eps^{40/3}$.  Together, we once again achieve population excess risk
          $\cR(W_{\leq t}) - \overline{\cR} = \cO(\eps)$.
      \end{enumerate}

      Summarizing, a first key point is that arbitrarily small excess risk $\cO(\eps)$
      is always possible; as discussed, this is in contrast to prior work,
      which either only gave training error guarantees, or required restrictive conditions for
      small test error.  A second key point is that the parameters of the bound, most notably
      the required width, will shrink greatly when either the data is easy, or an optimal
      stopping radius $R_{\textup{gd}}$ is known.

    \item
      \textbf{(Consistency.)}
      \emph{Consistency} is a classical statistical goal of achieving the optimal test error
      almost surely
      \emph{over all possible predictors} as $n\to\infty$; here it is
      proved as a consequence of \Cref{fact:main}, namely the preceding argument
      that we can achieve excess risk $\cO(\eps)$ even with general prediction problems
      and no early stopping hints ($R_{\textup{gd}}=\infty$).
      The consistency guarantee is stated formally in \Cref{fact:consistency}.
      The statement takes the width to infinity, and demonstrates another advantage of using 
      an infinite-width reference model: within the proof, after fixing a target accuracy,
      the reference model is \emph{fixed} and used for all widths simultaneously.

\begin{figure}[b!]
\begin{tcolorbox}[enhanced jigsaw, empty, sharp corners, colback=white,borderline north = {1pt}{0pt}{black},borderline south = {1pt}{0pt}{black},left=0pt,right=0pt,boxsep=0pt,rightrule=0pt,leftrule=0pt]
\centering
    \includegraphics[width=0.7\textwidth]{figs/venn.pdf}
    \caption{The setting of this paper, contrasted with standard settings.  \Cref{fact:main}
      considers iterate $W_{\leq t}$, which is somewhere in the \emph{early-stopped} ball
      around the initial random choice $W_0$.
      This early-stopped ball is well inside the \emph{near initialization} or \emph{NTK}
      ball, since in noisy settings, the early-stopped ball will not reach zero training error,
      whereas the NTK ball will.  Meanwhile, the NTK itself requires early stopping and is a
      subset of the space of all parameters.
    }
    \label{fig:venn}
   \end{tcolorbox}
\end{figure}
    \item
      \textbf{(Non-vacuous generalization, and an estimate of $R$.)}
      There is extensive concern throughout the community that generalization estimates
      are hopelessly loose
      \citep{nati_implicit_gen,zhang_gen,roy_vacuous}; to reduce the concern here,
      we raise two points.  Firstly, these concerns usually involve explicit calculations of
      generalization bounds which have terms scaling with some combination
      of $\|W\|$ (not $\|W - W_0\|$)
      and $m$; e.g,. one standard bound has spectral norms $\|W\|_2$
      and $(2,1)$ matrix norms $\|(W - W_0)^\T\|_{2,1}$, which are upper bounded by
      $\|W - W_0\|\sqrt{m}$ \citep{spec}.
      By contrast, the present work uses a new generalization bound
      technique
      (cf. \Cref{fact:shallow:gen:frob:1})
      which first \emph{de-linearizes} the network, then applies a \emph{linear
      generalization bound} which has only $\|W-W_0\|$ and no explicit $\poly(m)$, and then
      \emph{re-linearizes}.

      Secondly, there may still be concern that the story here is broken due to the term $R$,
      and namely the non-existence of good choices for $\overline U_{\!\infty}$.  For this, we conducted a simple
      experiment.  Noting that we can freeze the initial features and train linear predictors of
      the form $f^{(0)}(x;V)$ for weights $V\in\R^{m\times d}$ (cf. \cref{sec:notation}),
      and that the performance converges to the infinite-width performance as $m\to\infty$,
      we fixed a large width and trained two prediction tasks: an \emph{easy} task
      of MNIST 1 vs 5 until $R_{\text{easy}}/\sqrt{n} \approx 1/2$, and a \emph{hard} task
      of MNIST 3 vs 5 until $R_{\text{hard}}/\sqrt{n} \approx 1/2$.
      After training, we obtained test error $\cR(V_{\text{easy}}) \approx 0.01$
      and $\cR(V_{\text{hard}})\approx 0.08$.  Plugging all of these terms back in to the bound,
      firstly these techniques can yield a non-vacuous generalization bound, secondly they
      do not exhibit bad scaling with large width, and thirdly they do reflect the difficulty
      of the problem, as desired.







    \item
      \textbf{(Early stopping and the NTK.)}
      As discussed above, when the data is noisy, the method is explicitly early stopped,
      either by clairvoyantly choosing $R_{\textup{gd}}$, or by making $t$ small.  In this setting,
      the optimization accuracy $\eps_{\textup{gd}}$ is an \emph{excess} empirical risk, meaning in particular
      that $0$ training error (the \emph{interpolation regime} \citep{double_descent})
      will \emph{not} be reached.  This is in stark contrast to standard
      NTK analyses \citep{allen_deep_opt}, which guarantee zero training error, but can not
      ensure good test error in general.  Since the NTK itself is an early stopping (as in,
      if one continues to optimizes, one exits the NTK), then the early stopping in this work
      is even earlier than the NTK early stopping; this situation is summarized in
      \Cref{fig:venn},
      and will be revisited for the lower bound in \Cref{sec:intro:lb}.





    \item
      \textbf{(Classification and calibration.)}
      The relationship to classification and calibration errors is merely a restatement
      of existing results \citep{zhang_convex_consistency,bartlett_jordan_mcauliffe},
      though it is reproved here in an elementary way for the special case of the logistic loss.
      Similarly, the guarantee that
      $\cK_{\textup{bin}}(p_y, \phi_{\infty}^{(\eps)})$ can be made arbitrarily small is also not a primary
      contribution, and indeed most of the heavy lifting is provided both by prior work
      in neural network approximation \citep{barron_nn}, and by the
      existing and reliable machinery
      for proving consistency \citep{schapire_freund_book_final}.
      As such, the consistency result is stated only much later in \Cref{fact:consistency},
      and our focus is on the exact risk guarantees in \Cref{fact:main}.

    \item
      \textbf{(Inputs with bias: $(x,1)/\sqrt{2}\in\R^{d+1}$.)}
      The end of \Cref{fact:main} appends a constant to the input (and rescales),
      which simulates a bias
      term inside each ReLU; this is necessary since our models 
      are (sigmoid mappings of) homogeneous functions, whereas $p_y$ is general.
Biases are also simulated in this way in the consistency result in \Cref{fact:consistency}.
      \qedhere
  \end{enumerate}
\end{remark}



Further discussion of \Cref{fact:main}, including the formal consistency result
(cf. \Cref{fact:consistency}) and a proof sketch, all appear in \Cref{sec:gd}.
Full proofs appear in the appendices.


\subsection{Should we early stop?}
\label{sec:intro:lb}

\begin{figure}[b!]
\begin{tcolorbox}[enhanced jigsaw, empty, sharp corners, colback=white,borderline north = {1pt}{0pt}{black},borderline south = {1pt}{0pt}{black},left=0pt,right=0pt,boxsep=0pt,rightrule=0pt,leftrule=0pt]
\centering
    \begin{subfigure}[t]{0.46\textwidth}
      \centering
      \includegraphics[width=\textwidth]{figs/interp1}
      \caption{Conditional model $p_y$ and some noisy data.  A smoothed prediction rule
      would perform well.}
      \label{fig:interp:1}
    \end{subfigure}\hfill
    \begin{subfigure}[t]{0.46\textwidth}
      \centering
      \includegraphics[width=\textwidth]{figs/interp2}
      \caption{A \emph{local interpolation rule} working very hard to fit the noisy data.}
      \label{fig:interp:2}
    \end{subfigure}\caption{When data is noisy, it's best to give up on a few points.  The shaded region here
      highlights
      consecutive points with the wrong label; as in \Cref{fact:lb:local},
      prediction rules that locally interpolate will have a large population risk in these
      regions.
    }
    \label{fig:interp}
   \end{tcolorbox}
\end{figure}

\Cref{fact:main} uses early stopping: it can blow up if
$\overline{\cR} > 0$ and the two gradient descent parameters $R_{\textup{gd}}$ and $1/\eps_{\textup{gd}}$
are taken to $\infty$ in an uncoordinated fashion.
Part of this is purely technical: as with many neural network optimization proofs,
the analysis breaks when far from initialization.
It is of course natural to wonder what happens
if one trains indefinitely, entering the actively-studied \emph{interpolation regime}
\citep{daniel_interpolation,double_descent,peter_benign}. Furthermore, there is evidence
that gradient descent on shallow networks limits towards a particular interpolating
choice, one with large margins
\citep{nati_logistic,riskparam_logreg,kaifeng_jian_margin,chizat_bach_imp,ziwei_directional}.
Is this behavior favorable?

While we do not rule out that the interpolating solutions found by neural networks
perform well, we show that at least in the low-dimensional (univariate!) setting,
if a prediction
rule perfectly labels the data and is not too wild between training points, then it is guaranteed
to achieve poor test loss on noisy problems.
This negative observation is not completely at odds with the interpolation literature,
where the performance of some rules improves with dimension \citep{daniel_interpolation}.

\begin{proposition}
  \label{fact:lb:local}
  Given a finite sample $((x_i,y_i))_{i=1}^n$ with $x_i\in\R$ and $y_i\in\{\pm 1\}$,
  let $\cF_n$ denote the collection of \emph{local interpolation rules}
  (cf. \Cref{fig:interp}):
  letting $x_{(i)}$ index examples in sorted order, meaning
  $x_{(1)} \leq x_{(2)}\leq \cdots \leq x_{(n)}$,
  define $\cF_n$ as
  \begin{align*}
    \cF_n
    := \big\{ f : \R \to \R \ : \ {}
    &\forall i\ {}f(x_{(i)}) = y_{(i)}, \text{ and}
      \\
    &\text{if } y_{(i)} = y_{(i+1)}, \text{ then }
    \inf_{\alpha\in[0,1]} f\del[1]{ \alpha x_{(i)} + (1-\alpha)x_{(i+1)} }y_{(i)} > 0
    \big\}.
  \end{align*}
  Then there exists a constant $c>0$ so that with probability at least $1-\delta$ over the draw of $((x_i,y_i))_{i=1}^n$
  with $n \geq \ln(1/\delta)/c$,
  every $f\in\cF_n$ satisfies $\cRz(f) \geq \bar\cRz(f) + c$.
\end{proposition}

Although a minor contribution, this result will be discussed briefly
in \Cref{sec:lb:local}, with detailed proofs appearing in the appendices.
For a similar discussion for nearest neighbor classifiers albeit under a few additional
assumptions, see \citep{nakkiran_bansal}.

\subsection{Related work}






\paragraph{Analyses of gradient descent.}
The proof here shares the most elements with recent works whose width could be polylogarithmic
in the sample size and desired target accuracy $1/\eps$
\citep{ziwei_ntk,gu_polylog}.  Similarities include using a regret inequality as the core
of the proof, using an infinite-width target network \citep{nitanda_refined,ziwei_ntk},
and using a \emph{linearization inequality} \citep{gu_polylog,allen_deep_opt}.
On the technical side, the present work differs in the detailed treatment of the logistic loss,
and in the linearization inequality which is extended to hold over the population risk;
otherwise, the core gradient descent analysis here is arguably simplified relative
to these prior works.
It should be noted that the use of a regret inequality here and in the previous works crucially
makes use of a negated term which was dropped in some classical treatments;
this trick is now re-appearing
in many places \citep{orabona2021parameterfree,frei_agnostic}.

There are many other, somewhat less similar works in the vast literature of gradient descent on neural networks,
in particular in the neural tangent regime
\citep{jacot_ntk,li_liang_nips,du_iclr}.
These works often handle not only training error, but also testing error
\citep{allen_3_gen,arora_2_gen,cao_deep_gen,nitanda_refined,ziwei_ntk,gu_polylog}.
As was mentioned before, these works do not appear to handle arbitrary target
models; see for instance the modeling discussion in \citep[Section 6]{arora_2_gen}.
As another interesting recent example,
some works explicitly handle certain noisy conditional models,
but with error terms that do not go to zero in general
\citep{liang2021achieving}.

\paragraph{Consistency.}
Consistency of deep networks with classification loss and
\emph{some} training procedure is classical; e.g.,
in \citep{lugosi_consistency}, the authors show that it suffices to
run a computationally intractable algorithm on an architecture chosen to balance VC dimension
and universal approximation.  Similarly, the work here makes use of Barron's superposition
analysis in an infinite-width form to meet the Bayes risk
\citep{barron_nn,ntk_apx}.
The statistics literature has many other works giving
beautiful analyses of neural networks, e.g., even with minimax rates
\citep{schmidthieber}, though it appears this literature generally does not consider gradient
descent and arbitrary classification objectives.

In the boosting literature, most consistency proofs only consider classification loss
\citep{bartlett_traskin_adaboost,schapire_freund_book_final},
though there is a notable exception which controls the convex loss (and thus calibration),
although the algorithm has a number of modifications \citep{zhang_yu_boosting}.
In all these works, arbitrary $p_y$ are not handled explicitly as here, but rather
\emph{implicitly} via assumptions on the expressiveness of the weak learners.
One exception is the logistic loss boosting proof of \citet{mjt_log_cons},
which explicitly handles measurable $p_y$ via Lusin's theorem as is done here,
but ultimately the proof only controls classification loss.


Following the arXiv posting of this work, a few closely related works appeared.
Firstly, \citet{ilja_consistency} show that the expected excess risk can scale with
$\|W_t-W_0\|_\tF / n^\alpha$, though in contrast with the present work, it is not shown
that this ratio can go to zero for arbitrary prediction problems, and moreover the
bound is in expectation only.  Secondly, the work of \citet{smoking_gun} is even closer,
however it requires a condition on the Fourier spectrum of the conditional model $p_y$,
which is circumvented here
via a more careful Fourier analysis due to \citet{ntk_apx}.

\paragraph{Calibration.}
There is an increasing body of work considering the (in)ability of networks trained
with the logistic loss to recover the underlying conditional model.
Both on the empirical side \citep{guo2017calibration} and on the theoretical side
\citep{bai2021dont}, the evidence is on the side of the logistic loss doing poorly, specifically
being \emph{overconfident}, meaning the sigmoid outputs are too close to $0$ or $1$.
This overconfident regime corresponds to large margins; indeed,
since gradient descent can be proved in some settings
to exhibit unboundedly large unnormalized margins on
all training points \citep{kaifeng_jian_margin}, the sigmoid mapping of the
predictions will necessarily limit to exactly $0$ or $1$.
On the other hand, as mentioned in \citep{bai2021dont}, regularization suffices
to circumvent this issue. In the present work, a combination of early stopping
and small temperature are employed.
As mentioned before, calibration is proved here as an immediate corollary of meeting
the optimal logistic risk via classification calibration
\citep{zhang_convex_consistency,bartlett_jordan_mcauliffe}.

















\subsection{Further notation and technical background}
\label{sec:notation}

The loss $\ell$, risks $\cR$ and $\hcR$, and network $f$ have been defined.
The misclassification risk $\cRz(f) = \Pr[\sgn(f(X))\neq Y]$ appeared in \Cref{fact:main},
where $\sgn(f(x)) = 2\cdot \1[f(x)\geq 0] - 1$.

Next, consider the ``gradient'' of $f$ with respect to weights $W$:
\[
  \nabla f(x;W) := \frac {\rho}{\sqrt m}\sum_{j=1}^m a_j \1[w_j^\T x \geq 0] \ve_jx^\T;
\]
it may seem the nondifferentiability at $0$ is concerning, but in analyses close to initialization
(as is the one here), few activations change, and their behavior is treated in a worst-case
fashion.  Note that, as is easily checked with this expression,
$\|\nabla f(W)\| \leq \rho$, which is convenient in many places in the proofs.
Here $\|\cdot\|$ denotes the Frobenius norm; $\|\cdot\|_2$ will denote the spectral norm.

Given weight matrix $W_i$ at time $i$, let $(w_{i,j}^\T)_{j=1}^m$ refer to its rows.
Define features $f^{(i)}$ at time $i$ and a corresponding empirical risk $\hcR^{(i)}$ using
the features at time $i$ as
\begin{align*}
  f^{(i)}(x;V)
  &:= \ip{\nf(x;W_i)}{V} = \frac \rho {\sqrt m} \sum_j a_j v_j^\T x \1[w_{i,j}^\T x\geq 0],
  \\
  \hcR^{(i)}(x;V) &:= \hcR(x\mapsto f^{(i)}(x;V)).
\end{align*}
By $1$-homogeneity of the ReLU, $f^{(i)}(x;W_i) = f(x;W_i)$, which will also be used often.
These features at time $i$, meaning $f^{(i)}$ and $\hcR^{(i)}$,
are very useful in analyses near initialization, as they do not change much.
As such, $\ff{0}$ and $\cR^{(0)}$ and $\hcR^{(0)}$ will all appear often as well.

To be a bit pedantic about the measure $\mu$: as before, there is a joint distribution $\mu$,
which is over the Borel $\sigma$-algebra on $\R^d\times\{\pm 1\}$, where $\|x\|\leq 1$ almost
surely.  This condition suffices to grant both a \emph{disintegration} of $\mu$ into
marginal $\mu_x$ and conditional $p_y$ \citep[Chapter 6]{kallenberg2002foundations},
and also Lusin's theorem \citep[Theorem 7.10]{folland}, which is used to switch from a
measurable function to a continuous one in the consistency proof (cf. \Cref{fact:consistency}).
















\section{Discussion and proof sketch of \Cref{fact:main}}
\label{sec:gd}

This section breaks down the proof and discussion into four subsections: a section
with common technical tools,
then sections for the analysis of generalization, optimization, and approximation.

\subsection{Key technical lemmas}

There are two main new technical ideas which power many parts of the proofs: a multiplicative
error property of the logistic loss, and a \emph{linearization over the sphere}.

The logistic loss property is simple enough: for any $a\geq b$, it holds that
$\ell(-a)/\ell(-b)\leq \exp(a-b)$.  On the surface, this seems innocuous, but this simple
inequality allows us to reprove existing polylogarithmic width results for easy data
\citep{ziwei_ntk,gu_polylog}, however making use of a proof scheme which is slightly more
standard, or at the very least more apparently a smooth convex proof with just this one
special property of the logistic loss (as opposed to a few special properties).

The second tool is more technical, and is used crucially in many places in the proof.
Many prior analyses near initialization bound the quantity
\[
  f(x;V) - f(x;W) - \ip{\nf(x;W)}{V-W},
\]
where $V$ and $W$ are both close to initialization
\citep{allen_deep_opt,cao_deep_gen,gu_polylog}.  These proofs are typically performed on
a fixed example $x_k$, and then a union bound carries them over to the whole training set.
Here, instead, such a bound is extended to hold \emph{over the entire sphere}, as follows.


\begin{lemma}[Simplification of \Cref{fact:shallow:linearization:frob}]\label{fact:shallow:linearization:frob:simplified}
  Let scalars $\delta>0$ and $R_V\geq 1$ and $R_B\geq 0$ be given.
  \begin{enumerate}


    \item
With probability at least $1-3n\delta$,
      \[
\sup_{\substack{\|W_i - W_0\| \leq R_V\\
            \|W_j - W_0\| \leq R_V\\
        \|B - W_0\|\leq R_B}}
        \frac {\hcR^{(i)}(B)}{\hcR^{(j)}(B)}
        \leq
\exp\del{
          \frac {6\rho \del{R_B + 2R_V}R_V^{1/3}\ln(e/\delta)^{1/4}}{m^{1/6}}
        }
        .
      \]



    \item
Suppose $m \geq \ln(edm)$.
      With probability at least $1- (1 + 3 (d^2m)^{d})\delta$, 
      \[
        \sup_{\|W_i - W_0\| \leq R_V}
        \frac {\cR(W_i)}{\cR^{(0)}(W_i)}
        \leq
\exp\del{
          \frac {25 \rho R_V^{4/3} \sqrt{\ln(edm/\delta)}}{m^{1/6}}
        }
        .
      \]
  \end{enumerate}
\end{lemma}

The preceding \namecref{fact:shallow:linearization:frob} combines both the linearization
technique and the multiplicative error property: it bounds how much the empirical and true risk
change for a fix weight matrix if we swap in and out the features at different iterations.
That these bounds are a ratio is due to the multiplicative error property.  That the second
part holds over the true risk, in particular controlling behavior over all $\|x\|\leq 1$,
is a consequence of the new more powerful linearization technique.
This linearization over the sphere is used crucially in three separate places:
we use it when controlling the range in the generalization proofs,
when \emph{de-linearizing} after generalization,
and when sampling from the infinite-width model $\overline U_{\!\infty}$.
The method of proof is
inspired by the concept of \emph{co-VC dimension} \citep{gurvits_koiran}:
the desired inequality is first union bounded over a cover of the sphere,
and then relaxed to all points on the sphere.
A key difficulty here is the non-smoothness of the ReLU, and a key lemma
establishes a smoothness-like inequality (cf. \Cref{fact:covc:helper}).
These techniques appear in full in the appendices.















\subsection{Generalization analysis}

The generalization statement appears as \Cref{fact:shallow:gen:frob:1} in the appendices,
together with its proofs,
but here is a sketch of the key elements.
To start, rather than directly studying uniform convergence properties of the networks
reachable by gradient descent,
\Cref{fact:shallow:linearization:frob:simplified}
is applied over the training set to convert the network to a linear predictor,
and only then is generalization \emph{of linear predictors} applied;
this use of generalization for linear predictors and not of general networks is how the bound
pays only logarithmically in the width, and otherwise has just a Frobenius norm dependence on
the weight matrices (minus initialization), which is in contrast with standard generalization
bounds.
Thereafter, \Cref{fact:shallow:linearization:frob:simplified} is applied once more,
but on the population risk (which
uses the approximation guarantee over the entire sphere and not just the training set), which \emph{de-linearizes} the
linear predictor used for generalization and gives a test error guarantee for the original network.

Typically the easiest step in proving generalization is to provide a
worst-case estimate on the range of the predictor, however a standard worst-case estimate
in this setting
incurs a polynomial dependence on network width.
To avoid this, we once again use the tools of
\Cref{fact:shallow:linearization:frob:simplified} to control the range with high
probability.


\subsection{Gradient descent analysis}

A common tool in linear prediction is the regret inequality
\[
  \|v_t - z\|^2 + 2\eta\sum_{i<t} \hcR(v_{i+1}) \leq \|v_0 - z\|^2 + 2t\eta \hcR(z),
\]
which can be derived by expanding the square in $\|v_t - z\|^2$ and applying
smoothness and convexity.  The term $\|v_t-z\|^2$ is often dropped, but can be used in a very
convenient way:  by the triangle inequality, if $\|v_t-v_0\|\geq 2\|z-v_0\|$, then the norm
terms above
may be canceled from both sides, which leaves only the empirical risk terms; overall, this
argument ensures both small norm and small empirical risk.
This idea has appeared in a variety of works
\citep{shamir2020gradient,gd_reg}, and is used here to provide a convenient norm control,
allowing linearization and all other proof parts to go through.  Combining this idea
with the earlier generalization analysis and a few other minor tricks
gives the following bounds, which in turn provide most of \Cref{fact:main}.

\begin{lemma}\label{fact:shallow:magic:linearized}
  Let
  temperature $\rho > 0$,
  step size $\eta \leq 4/\rho^2$,
  optimization accuracy $\eps_{\textup{gd}} > 0$,
  radius $R_{\textup{gd}}>0$,
  network width $m\geq \ln(emd)$,
  reference matrix $Z\in\R^{m\times d}$,
  corresponding scalar $R_Z\leqR_{\textup{gd}}$ where $R_Z \geq \max\{1, \eta \rho, \|W_0 - Z\|\}$,
  and $t \geq 1 / (2\eta\rho^2 \eps_{\textup{gd}})$ be given;
  correspondingly define $W_{\leq t} := \argmin\{ \hcR(W_i) : i \leq t, \|W_i-W_0\|\leq R_{\textup{gd}}\}$.
  Define effective radius
  $B := \min\cbr[1]{R_{\textup{gd}},\ {}3R_Z + 2e \sqrt{\eta t \hcR^{(0)}(Z)} }$,
  and linearization and generalization errors
  \[
\tau := \frac {25 \rho B^{4/3}\sqrt{d\ln(em^2d^3/\delta)}}{m^{1/6}},
    \qquad
    \tau_n := \frac {80\del{d \ln(em^2 d^3/\delta)}^{3/2}}{\sqrt n},
  \]
  and suppose $\tau \leq 2$.
  Then, with probability at least $1-3n\delta$, 
  the selected iterate $W_{\leq t}$
  satisfies $\|W_{\leq t}-W_0\|\leq B$,
  along with the empirical risk guarantee
  \begin{align*}
    \hcR(W_{\leq t}) \leq e^{2\tau} \hcR^{(0)}(Z) + e^{\tau} (\rho R_Z)^2 \eps_{\textup{gd}},
  \end{align*}
  and by discarding an additional $16\delta$ failure probability,
  then $\hcR^{(0)}(Z) \leq \cR^{(0)}(Z) + \rho R_Z \tau_n$,
  and
  \begin{align*}
    \cR(W_{\leq t})
    &\leq
    e^{4\tau} \cR^{(0)}(Z)
    + e^{3\tau} (\rho R_Z)^2 \eps_{\textup{gd}}
    +
    e^{4\tau} (B+R_Z)\rho \tau_n.
\end{align*}
\end{lemma}


This version of the statement, unlike \Cref{fact:main}, features an arbitrary reference
\emph{matrix} $Z$.  This is powerful, though it can be awkward, since $W_0$ is a random variable.


\subsection{Approximation analysis, consistency, and the proof of \Cref{fact:main}}


Rather than trying to reason about good predictors which may happen to be close to random
initialization,
the approach here is instead to start from deterministic predictors over the population
(e.g., $\overline U_{\!\infty}$),
and to use their structure to construct approximants
near the initial iterate, the random matrix $W_0$.
Specifically, the approach here is fairly brute force: given initial weights
$W_0$ with rows $(w_{0,j}^\T)_{j=1}^m$, the rows $(\overline u_j)_{j=1}^m$
of the finite width reference matrix $\overline U\in\R^{m\times d}$ intended to mimic $\overline U_{\!\infty}$
(which is after all a mapping $\overline U_{\!\infty} :\R^d \to \R^d$)
are simply
\begin{equation}
  \overline u_j := \frac {a_j \overline U_{\!\infty}(w_{0,j})}{\rho\sqrt{m}} + w_{0,j}.
  \label{eq:barUi:sample}
\end{equation}
By construction, $\|\overline U - W_0\|\leq R/\rho$, where $R:=\sup_v \|\overline U_{\!\infty}(v)\|$.
To argue that $\cR^{(0)}(\overline U)$ and $\cR(\overline U_{\!\infty})$ are close,
the risk control over the sphere in
\Cref{fact:shallow:linearization:frob:simplified}
is again used.
Plugging this $\overline U$ into 
\Cref{fact:shallow:magic:linearized} and introducing $\cK_{\textup{bin}}(p_y, \phi_\infty)$
gives the first part of \Cref{fact:main}, and the second part
of \Cref{fact:main} is from a few properties of the logistic loss summarized
in \Cref{fact:logistic:error}.

It remains to prove that for any $p_y$, there exists $\overline U_{\!\infty}$ with
$\phi(x\mapsto f((x,1)/\sqrt{2};\overline U_{\!\infty})) \approx p_y$
(we must include a bias term, as mentioned in \Cref{rem:main}).
If $p_y$ were continuous, there is a variant
of \citeauthor{barron_nn}'s seminal universal approximation construction which explicitly
gives an infinite-width network of the desired form \citep{barron_nn,ntk_apx}.
To address continuity is even easier: \emph{Lusin's theorem} \citep[Theorem 7.10]{folland}
lets us take the measurable
function $p_y$, and obtain a continuous function that agrees with it on all but a negligible
fraction of the domain.  This completes the proof.

As mentioned, a key property of the reference model $\overline U_{\!\infty}$
is that it depends on neither the random sampling of data, nor the random sampling of weights.
This vastly simplifies the proof of consistency, where the proof scheme first fixes an $\eps>0$
and chooses a $\overline U_{\!\infty}$, and leaves it fixed as $m$ and $n$ vary.

\begin{corollary}\label{fact:consistency}
  Let early stopping parameter $\xi\in(0,1)$ be given,
  and for each sample size $n$, define a weight matrix $\widehat W_n \in \R^{m^{(n)}\times (d+1)}$
  and corresponding conditional probability model 
  $\widehat \phi_n(x) := \phi(f((x,1)/\sqrt 2;\widehat W_n))$ as follows.
  For each sample size $n$, let $(W^{(n)}_i)_{i\geq 0}$
  denote the corresponding sequence of gradient descent iterates obtained with parameter choices
$\rho^{(n)} := (m^{(n)})^{-1/8}$,
  and $m^{(n)} := n^{\frac{40}{3}(1-\xi)}$,
  and $\eta^{(n)} := 4/(\rho^{(n)})^2$,
  and $\eps_{\textup{gd}}^{(n)} := n^{\xi-1}$,
  and $t^{(n)} := n^{1-\xi}/8$,
  and choose the empirical risk minimizer over the sequence, meaning
  $\widehat W_n := \argmin\cbr[1]{\hcR(W^{(n)}_i) : i \leq t^{(n)} }$
  (in the notation of \Cref{fact:main}, this is $W_\leq t$ with $R_{\textup{gd}} = \infty$).
  Then
  \[
    \cR(\widehat W_n) \xrightarrow{\phantom{\ {}L_2(\mu_x)}\ {}}  \overline{\cR} \text{ a.s.,}
    \qquad
    \quad
    \cRz(\widehat W_n) \xrightarrow{\phantom{\ {}L_2(\mu_x)\ {}}} \overline{\cR}_{\textup{z}} \text{ a.s.,}
    \qquad
    \quad
    \widehat \phi_n \xrightarrow{\ {}L_2(\mu_x)\ {}} p_y \text{ a.s.,}
  \]
  where the last convergence is in the $L_2(\mu_x)$ metric.
\end{corollary}

The use of a parameter $\xi\in(0,1)$ is standard in similar consistency results; see for instance
the analogous parameter in the consistency analysis of AdaBoost
\citep{bartlett_traskin_adaboost}.
Proofs, as usual, are in the appendices.

\section{Discussion and proof sketch of \Cref{fact:lb:local}}
\label{sec:lb:local}

\Cref{fact:lb:local} asserts that univariate \emph{local interpolation rules} --- 
predictors which perfectly fit the data, and are not too wild between data points of the
same label --- will necessarily achieve suboptimal population risk.
The proof idea seems simple enough: if the true conditional probability $p_y$
is not one of $\{0,\nicefrac 1 2,1\}$
everywhere, and is also continuous, then there must exist a region where it is well separated
from these three choices.
It seems natural that a constant fraction of the data in these regions
will form adjacent pairs with the wrong label; a local interpolation rule will fail on exactly
these adjacent noisy pairs,
which suffices to give the bound.  In reality, while this is indeed the proof scheme followed here,
the full proof must contend with many technicalities
and independence issues.  It appears in the appendices.

While the motivation in \Cref{sec:intro:lb} focused on neural networks which interpolate, and also
maximum margin solutions,
the behavior on this noisy univariate
data is also well-illustrated by $k$-nearest-neighbors classifiers ($k$-nn).
Specifically, $1$-nn is a local interpolant, and \Cref{fact:lb:local} applies.
On the other hand, choosing $k = \Theta(\ln(n))$ is known to provide
enough smoothing to achieve consistency and avoid interpolation \citep{DGL}.

It should be stressed again that even if the remaining pieces could be proved to apply this result
to neural networks, namely necessitating early stopping,
it would still be a univariate result only,
leaving open many interesting possibilities in higher dimensions.

\section{Concluding remarks and open problems}
\label{sec:open}

\paragraph{Empirical performance.}
Does the story here match experiments?  E.g., is it often the case that if a neural network
performs well, then so does a random feature model?  Do neural networks fail on noisy data if
care is not taken with temperature and early stopping?  Most specifically, is this part
of what happens in existing results reporting such failures \citep{guo2017calibration}?

\paragraph{Temperature parameter $\rho$.}
Another interesting point of study is the temperature parameter $\rho$.  It arises here
in a fairly technical way: if $p_y$ is often close to $1/2$,
then the random initialization of $W_0$ gets in the way of learning $p_y$.  The temperature
$\rho$ is in fact a brute-force method of suppressing this weight initialization noise.
On the other hand,
temperature parameters are common across many works which rely heavily on the detailed
real-valued outputs of sigmoid and softmax mappings; e.g., in the distillation literature
\citep{distillation}.  The temperature also plays the same role as the scale parameter
in the \emph{lazy training} regime
\citep{bach_chizat_note}.
Is $\rho$ generally useful, and does the analysis here relate to its practical utility?

\paragraph{Random features, and going beyond the NTK.}
The analysis here early stops before the feature learning begins to occur.
How do things fare outside the NTK?  Is there an analog of \Cref{fact:main},
still stopping shy of the interpolation pitfalls of \Cref{fact:lb:local},
but managing to beat random features with some generality?

\paragraph{The logistic loss.}
One reason the logistic is used here is its simple interplay with calibration
(e.g., see the elementary proof of \Cref{fact:logistic:error}, as compared with the full
machinery of classification calibration
\citep{zhang_convex_consistency,bartlett_jordan_mcauliffe}).
The other key reason was the multiplicative error property \Cref{fact:logistic:error}.
Certainly, the logistic loss is widely used in practice; are the preceding technical points
at all related to the widespread empirical use of the logistic loss?













\subsubsection*{Acknowledgments}
The authors are grateful for support from the NSF under grant IIS-1750051.
MT thanks many friends for illuminating and motivating discussions:
Daniel Hsu,
Phil Long,
Maxim Raginsky,
Fanny Yang.


