\section{Declarations}
\begin{itemize}
\item
Funding: Cape Breton University RISE grant 80306
\item
Conflicts of interest/Competing interests: None
\item
Availability of data and material: N/A
\item
Code availability: N/A
\item
Authors' contributions: All the sole author's work
\end{itemize}

\section{Introduction}\label{s:intro}

For other basic graph theory definitions, please see \cite{bo:rd}. In this paper a triangle in a graph will be defined as a set of three distinct vertices with an edge between each pair of vertices.
We are interested in graphs such that every edge is in at least one triangle, we refer to this as {\em the triangle property}.
In particular, we are looking for graphs which have the fewest triangles in them with regards their regularity and number of vertices while still having the triangle property; such graphs we will call {\em optimal}.
By our definition of a triangle multiple edges are permitted in graphs with the triangle property but loops cannot be in a triangle since they must repeat a vertex. Any triangle that contains a multiple edge will lead to multiple triangles using those same three vertices.

The same fundamental lemma from \cite{ar:PR} which characterises all 4-regular graphs with the triangle property is also still true for any regular graph:

\begin{lem}\label{l:triv} \cite{ar:PR}
A graph $G$ has the triangle property if and only if, for every vertex $v \in V (G)$,
the graph induced by the neighbourhood of $v$ contains no isolated vertices.
\end{lem}

For 2-regular and 3-regular graphs with the triangle property the only graphs are disjoint copies of complete graphs, $y K_3$ and $z K_4$, respectively, for any positive integers $y$ and $z$, so there is nothing more to say about them. However, one consequence of lemma \ref{l:triv} is the following lower bound for the number of triangles in an optimal graph with even regularity:

\begin{thm}\label{t:eventri}
If $r$ is an even positive integer and $G$ is a graph with $n$ vertices  which is $r$-regular and has the triangle property, then there are at least $\frac{nr}{6}$ triangles. In the optimal case these triangles are also arranged in a distinctive pattern.
\end{thm}

\begin{proof}
Let $G$ be an $r$-regular graph with $n$ vertices which has every edge in a triangle, and let $r:=2s$ for any non-negative integer $s$.
By lemma \ref{l:triv} the $2s$ neighbours of any vertex in $G$ must induce a graph with no isolated vertices, and the graph satisfying this with fewest edges is $sK_2$ which has $s$ edges. Since each edge in the induced neighbourhood produces a triangle in $G$ there are at least $s$ triangles at any vertex. Thus, when we count the triangles at every vertex, and each triangle is counted three times, the number of triangles in $G$ is at least $\frac{ns}{3}=\frac{nr}{6}$.

Now suppose that $J$ is a optimal $2s$-regular graph with $n$ vertices and $ns$ edges which are all in exactly one of the $\frac{ns}{3}$ triangles in $J$. By the above we can see that there are exactly $s$ triangles at each vertex and now we can form a new graph $H$ from $J$ by creating a vertex for each triangle and adding an edge between any two vertices in $H$ if their triangles in $J$ shared a vertex.

Since each vertex in $H$ corresponds to a triangle in $J$ and at each vertex in $J$ there are $s$ triangles, there are $3(s-1)$ triangles in $H$ which share a vertex with every triangle. $H$ is therefore a $3(s-1)$-regular graph and each vertex in $H$ is incident with $3$ copies of $K_s$.\qed
\end{proof}

Immediately we can see this confirms what we said about 2-regular graphs; when $r=2$ we need $H$ to be a 0-regular graph and so must be copies of $K_1$. Replacing each vertex in $H$ by a triangle we get a number of copies of $K_3$ as expected.

\begin{cor}
Optimal 4-regular graphs are line graphs of 3-regular triangle-free graphs.
\end{cor}

\begin{proof}
If $s=2$ and $J$ is a minimal 4-regular graph with every edge in a triangle then, by Theorem \ref{t:eventri}, $H$ corresponds to the line graph of a 3-regular graph, one of the base families of graphs with the triangle property in \cite{ar:PR}. However, we need to ensure that $H$ is triangle-free, as otherwise, any triangle in $J$ will also appear in $H$ as a triangle too, and will not come from the three edges incident at a vertex in $H$.\qed
\end{proof}

It is also possible to create an optimal 6-regular graph from a 4-regular one and in general any optimal even regular graph if we start with a suitably large 4-regular graph and sequentially add triangles between the vertices of the previous optimal graph without creating any triangles with the existing graph edges.

For instance, as shown in figure \ref{f:pete}, in the Petersen graph there are five sets of three edges which have two edges between them. If we take the line graph there are then five sets of three vertices distance 3 apart from each other. One set of three is shown in the figure, the other sets are rotations of these, and together they can be used to make five new triangles which can be added to the line graph to create a 6-regular graph with $\frac{nr}{6}=\frac{15 \times 6}{6} = 15$ triangles.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.9\textwidth]{peteandlineplus.png}
\end{center}
\caption{Edges in Petersen at distance 3 giving a 6 regular graph with 15 triangles}\label{f:pete}
\end{figure}

However, for 5-regular graphs, the situation is more complicated. The structure of the family of 5-regular graphs is investigated in an upcoming paper by the author
but the base graphs in that paper can contain multiple edges or copies of $K_4$ and do not have the minimal number of triangles.

\begin{thm}\label{c:triv}
In a 5-regular graph with $2n$ vertices which has the triangle property, there are at least $2n$ triangles and $n$ edges which are in two triangles or more.
\end{thm}

\begin{proof}
If $v$ is a vertex in a 5-regular graph $G$ with the triangle property then we can use Lemma \ref{l:triv}; if $v$ is adjacent to five distinct vertices in $G$ then the induced neighbourhood graph of $v$ has at least 3 edges, and hence a vertex $w$ of degree at least 2, which gives rise to at least two triangles containing the edge $vw$ in $G$.
Similarly, if there is a multiple edge incident with $v$ then there must be at least one other edge $e$ incident with $v$ in a triangle and so $e$ is therefore in at least two triangles, using each edge of the multiple edge separately.

In addition to these triangles at $v$ they use at most three neighbours of $v$ and since the degree of $v$ is 5 there are two more vertices which haven't yet been included in a triangle, and must because $G$ has the triangle property, so there are at least three triangles at $v$. Counting the triangles at each vertex and dividing by the number of vertices in a triangle gives us at least $\frac{6n}{3} = 2n$ triangles in $G$.

Since at all $2n$ vertices there is at least one edge in two triangles or more, there are at least $n$ edges in $G$ which are in at least two triangles.
\qed
\end{proof}

\begin{remark}\label{r:odd}
We can argue similarly for $(2r+1)$-regular graphs with the triangle property for $r>2$. It will be necessary to have at least one vertex of degree 2 in the induced neighbourhood graph of every vertex, and so we have at least $(r+1)$ triangles incident with every vertex. Thus there must be at least $\frac{(r+1)n}{3}$ triangles in such a graph.
\end{remark}

\section{A family of optimal quintic graphs}

It turns out that, for $n\geq 7$, there do exist simple graphs that satisfy the inequality in Theorem \ref{c:triv}, such as by the following construction of a 5-regular or quintic graph $L_n$:
\begin{enumerate}[label=(\alph*)]
  \item Create $n$ vertices labelled 0 to $n-1$ with edges joined in a cycle
\item
For all $k$ from 0 to $n-1$, join vertex $k$ to a new vertex labelled $n+k$.
\item For $k$ from 0 to $n-1$ add an edge between vertex $n+k$  and
\begin{enumerate}[label=(\roman*)]
\item vertex $n+((k+2){\rm ~\!mod~} n)$.
 \item vertex $((k-2){\rm ~\!mod~} n)$
\item vertex $((k+1){\rm ~\!mod~} n)$.
\end{enumerate}
\end{enumerate}
$L_n$ is simple and 5-regular for $n\geq 5$; vertices 0 to $n-1$ are joined to two others in the cycle in (a) and one in (b) and two in (c), and the remaining $n$ vertices are joined to one vertex in (b) and four via (c). In $L_n$ the edges from vertex $k$ to vertex $n+k$, shown as the radial blue dashed spokes in figure \ref{f:l7} for $n=7$, are in exactly two triangles, with vertex $(k+1) {\rm ~\!mod~} n$ and vertex $n+ ((k+2){\rm ~\!mod~} n)$. The other two edges from vertex $k$ are to $(k-1){\rm ~\!mod~} n$ and $n+ ((k-1){\rm ~\!mod~} n)$ which also have an edge between them. Similarly, vertex $n+k$ is adjacent to vertices $(k-2){\rm ~\!mod~} n$ and $n+ ((k-2){\rm ~\!mod~} n)$ and so are part of that triangle. All of the different types of edges are in a triangle and so $L_n$ has the triangle property; there are only three triangles at vertices $k$ and $n+k$ and since $L_n$ is formed symmetrically, that is true for all vertices of $L_n$.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.5\textwidth]{L7.png}
\end{center}
\caption{The quintic graph $L_7$ which contains 14 vertices and 14 triangles}\label{f:l7}
\end{figure}

Note that this implies that $L_n$ contains exactly $2n$ triangles too, by counting the triangles at each vertex and dividing by the number of vertices in each triangle.
Additionally these triangles are arranged as $n$ edge-disjoint subgraphs isomorphic to the ${\rm diamond}$ ($K_{2,1,1}$ or $K_4^-$). This structure must hold for any simple 5-regular graph with $2n$ vertices and $2n$ triangles. In the remaining figures the edges that are in two triangles will again be coloured blue and dashed to highlight them.
If $n\leq 6$ then extra triangles are formed in $L_n$ using edges between vertices $n$ to $2n-1$, and for $n\leq 4$ multiple edges are created by this construction, so the graphs created are not optimal. $L_7$ is the graph with the fewest vertices which is optimal, as shown by an computer search using nauty \cite{ar:nauty}.

As in section \ref{s:intro}, examples of optimal odd-regular graphs can be constructed from an optimal 5-regular graph $F$ with $2n$ vertices by carefully adding triangles between triples of vertices of $F$ so as not to create any triangles other than those we are choosing to add. Note that this is only possible, by remark \ref{r:odd}, if $n$ is a multiple of 3 or $r$ is congruent to 2 mod 3.

For instance, if we take $L_{3j}$ for $j\geq 5$ and add edges between the triples of vertices between 0 and $3j-1$ that are congruent mod $j$, and then similarly join the vertices between $3j$ and $6j-1$ based on their congruence mod $j$, we will only create those $2j$ extra triangles, and so we have a family of optimal 7-regular graphs.

\section{Construction of all simple optimal quintic graphs}

\subsection{Diamonds and even cycle decompositions}
If we contract the $n$ blue dashed edges of $L_n$ between vertices $k$ and $n+k$ for $k$ from 0 to $n-1$ (the vertices of degree 3 in each ${\rm diamond}$ subgraph) then we get a 4-regular graph with $m$ vertices. We can trace even length cycles through these vertices corresponding to the arrangement of the ${\rm diamond}$s in $L_n$ since the degree 3 vertices in one ${\rm diamond}$ must be identified with the degree 2 vertices in another ${\rm diamond}$, and this continues on until the original ${\rm diamond}$ is repeated an even number of ${\rm diamond}$s later. This gives us an even cycle decomposition (as defined in \cite{ar:ecd}), but we will need a subset of these decompostions for our purposes:

If we list the cycles each starting with the same orientation of a ${\rm diamond}$ then each ${\rm diamond}$ will occur once in an even position in the sequence, the other in an odd one. For instance, in $L_7$, labelling the ${\rm diamond}$s cyclically from $a$ to $g$, we can get the following Eulerian cycle of the graph of ${\rm diamond}$s: $[a, c, b, d, c, e, d, f, e, g, f, a, g, b]$.

\begin{lem}\label{l:mint}
Optimal simple quintic graphs with $2n$ can all be formed from an even cycle decomposition of a 4-regular graph with $n$ vertices, by replacing the vertices by diamonds. The only restrictions for the even cycle decompositions are that it has these extra rules for any vertices $x$, $y$ and $z$ in the even cycle decomposition of the 4-regular graph:
\begin{enumerate}[label=(\roman*)]
\item
Either $[x,y]$ or $[y,x]$ can appear in cycles, not both, and only once.
\item
If $[x,y]$ and $[y,z]$ appear non-consecutively in cycles then $[z,x]$ cannot
\end{enumerate}
\end{lem}

\begin{proof}
As earlier, any optimal quintic graph $G$ must have one diamond and one triangle at each vertex. Since every vertex needs both and these are the only triangles in the graph, the vertices of degree 2 in the diamonds must be the triangles for other vertices. Thus, if $G$ has $2n$ vertices then there are $n$ diamonds joined together, comprising all $5n$ edges of $G$.

If we pick any diamond $D$ to start with and pick either diamond which is adjacent to it, we can traverse through the diamonds in the graph until we return in an even number of steps to $D$. If all diamonds are counted twice in this we are done, otherwise we repeat the process and get another even cycle of diamonds.

However, neither of the two cases specified in the lemma can occur without creating
additional triangles outside of the diamonds which cannot occur in an optimal graph as shown in figure \ref{f:moretri}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.8\textwidth]{dotsanddashes.png}
\end{center}
\caption{Dotted edges are also in more than one triangle}\label{f:moretri}
\end{figure}

In the left figure we have $[x,y]$ and $[y,x]$ appearing in our sequences and note that the dotted line is from both diamonds and therefore in two extra triangles with the blue dashed lines so the resulting graph is not optimal. Similarly, if $[x,y]$, $[y,z]$ and $[z,y]$ all appear then there is a triangle formed by edges of the diamonds which is not part of one of the original $n$ diamonds. Any larger cycles formed by the diamonds will not create any extra triangles, though.

Note that for $L_n$ we do get $[x,y,z,x]$ appearing as a cycle and no extra triangles are formed, but that isn't forbidden by the rules since they are consecutive diamonds. Additionally, within two cycles we cannot have $[x,y,z]$ and $[z,x]$ since $x$ and $z$ are the same parity in the former and the opposite parity in the latter, but each ${\rm diamond}$ must appear only twice, once in each parity.
\qed\end{proof}

\subsection{Multiple edges}

Lemma \ref{l:mint} also implies that each vertex in a simple optimal quintic graph must have the feature that all vertices are in exactly three triangles.
If a graph $G$ contains a vertex $v$ adjacent to a double edge $e$ then it is also possible for $v$ to be adjacent to three triangles, two triangles including either edge of $e$ and one other triangle to two other vertices.

Using this idea, one can try to create optimal quintic graphs with multiple edges at each vertex  by adding extra edges from a 1-factor of an optimal quartic graph to that graph as is done for the line graph of the cube in figure \ref{f:multopt}.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.5\textwidth]{optmult.png}
     \end{center}
\caption{A quintic graph with multiple edges with 12 vertices and 14 triangles}\label{f:multopt}
\end{figure}

However, if the original 3-regular graph had $2n$ vertices, then its line graph will have $3n$ vertices and $2n$ triangles. Adding double edges according to the 1-factor will add $\frac{3n}{2}$ more triangles and
thus the 5-regular graph will have $2n + \frac{3n}{2} = \frac{7n}{2} > 3n$ triangles, so such a graph cannot be optimal.

It is not possible to have a mix of double edges along with the diamond arrangement, since then there will be a vertex which is not in a double edge, but is in a triangle $T$ with one. At each vertex like this there will be more than three triangles, two with $T$ and at least two more as in lemma \ref{l:triv} again.

\subsection{Removable edges}
One useful feature of any optimal simple 5-regular graph $G$ is that all edges $e$ in $G$ have the property that $G-e$ does not have every edge in a triangle. We shall call $e$ an {\em unremovable} edge and all other edges {\em removable}.

\begin{thm}\label{t:elig}
The only quintic graphs with the triangle property and with all edges as unremovable are the optimal graphs.
\end{thm}

\begin{proof}
Suppose $G$ is a quintic graph with the triangle property which has more triangles than vertices and all of the edges of $G$ are unremovable. $G$ cannot have a multiple edge since any edge that is part of a multiple edge is removable. Since there are more triangles than vertices there must be more than $m$ edges in $G$ which are in at least two triangles and hence there exist two such edges $e_1$ and $e_2$ which have a vertex $v$ in common. Because $G$ is simple and quintic and $e_1$ and $e_2$ are both in at least two triangles, at least two of the triangles at $v$ must have an edge in common. This edge is not $e_1$ or $e_2$ and it is also in at least two triangles.

\begin{enumerate}[label=\roman*)]
\item
Let us first suppose that $G$ does not contain a $K_4$.
Because $v$ has degree 5 we can now assume that $e_1$ and $e_2$ are two edges in two triangles which are also part of a triangle with each other, and, moreover, that the third edge of that triangle, $e_3$ is also in at least two triangles since otherwise it is removable, and we therefore have the symmetrical situation shown in figure \ref{f:blueadj}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.4\textwidth]{dashedtri.png}
\end{center}
\caption{No $K_4$ and adjacent edges in more than one triangle}\label{f:blueadj}
\end{figure}

 If $u_i = u_j$ (for some $i\not =j$), or $u_jv_j$ is an edge then we have $K_4$ as a subgraph, contrary to our supposition. We will thus assume that all 6 vertices are distinct and have no edges from any $v_j$ other than those shown in figure \ref{f:blueadj}.

All three vertices $v_1$, $v_2$ and $v_3$ in figure \ref{f:blueadj} need to be degree 5, and so need one more edge that must be in a triangle.
If all are adjacent to the same vertex then there is again a $K_4$, so we can assume that $v_3$, say, is adjacent to a vertex, $w_3$ that isn't a neighbour of $v_1$ and $v_2$ . There must be an edge from $w_3$ to either $u_1$ or $u_2$, and there is symmetry, so we can assume $w_3u_2$ is an edge, but that means that $v_3u_2$ is in two triangles.
This now implies that $u_2v_1$ is in two triangles too, as otherwise it is removable.

We therefore must have, in $G$, a ${\rm diamond}$ which has all five edges which are in at least two triangles, and thus there must be four triangles each with an edge from the 4-cycle of the ${\rm diamond}$. Either a $K_4$ will be formed or the edge $f_1$ in figure \ref{f:bluedtri}will be removable unless it is part of a triangle which doesn't have any of these vertices in, as with vertex $y$.
However, in this case, the four triangles must all have blue edges if they are to be removable, but then edge $f_2$ will be removable.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.4\textwidth]{megadiamond.png}
\end{center}
\caption{Many edges in more than one triangle}\label{f:bluedtri}
\end{figure}

\item
If there is a $K_4$ in $G$ then each edge of it is in two triangles in the $K_4$ alone. Moreover, each is removable unless it is part of another triangle. However, there are only two more edges to add, so at least one of the edges from each vertex in the $K_4$ is also in at least two triangles. This means that there must now be a subgraph which is isomorphic to $K_5 \backslash E(K_2)$, and all edges are necessarily in at least two triangles. Now, as before, each of these edges will be removable unless they are part of a triangle with a new vertex, which tells us that there must be a subgraph isomorphic to $K_6\backslash E(K_3)$. However, the edges between the vertices of degree 5 in this subgraph are removable.
\end{enumerate}
\qed
\end{proof}


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