Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
Ziwei Ji Matus Telgarsky


Non-equilibrium photons from the bottom-up thermalization scenario
    Oscar Garcia-Montero  

 Institut für Theoretische Physik,
                     Universität Heidelberg,
 Philosophenweg 16,
                     69120 Heidelberg, Germany

    December 30, 2023
===============================================================================================================================================================================




  Recent theoretical work has guaranteed that overparameterized networks trained
  by gradient descent achieve arbitrarily low training error, and sometimes even
  low test error.
  The required width, however, is always polynomial in at least one of the
  sample size n, the (inverse) target error 1/, and the
  (inverse) failure probability 1/δ.
  This work shows that (1/) iterations of gradient
  descent with (1/^2) training examples on two-layer
  ReLU networks of any width exceeding
  (n, 1/, 1/δ) suffice to achieve a test
  misclassification error of .
  We also prove that stochastic gradient descent can achieve  test error
  with polylogarithmic width and (1/) samples.
  The analysis relies upon the separation margin of the limiting kernel, which
  is guaranteed positive, can distinguish between true labels and random
  labels, and can give a tight sample-complexity analysis in the infinite-width
  setting.




§ INTRODUCTION


Despite the extensive empirical success of deep networks,
their optimization and generalization properties are still not
fully understood.
Recently, the neural tangent kernel (NTK) has provided the following insight into the
problem.
In the infinite-width limit, the NTK converges to a limiting kernel which stays
constant during training; on the other hand, when the width is large enough, the
function learned by gradient descent follows the NTK <cit.>.
This motivates the study of overparameterized networks trained by gradient
descent, using properties of the NTK.
In fact, parameters related to the NTK, such as the minimum eigenvalue of the
limiting kernel, appear to affect optimization and generalization
<cit.>.

However, in addition to such NTK-dependent parameters, prior work also requires
the width to depend polynomially on n, 1/δ or 1/ϵ, where n
denotes the size of the training set, δ denotes the failure probability,
and ϵ denotes the target error.
These large widths far exceed what is used empirically,
constituting a significant gap between theory and practice.



  
Our contributions.

In this paper, we narrow this gap by showing that a two-layer ReLU network
with Ω(ln(n/δ)+ln(1/ϵ)^2) hidden units trained by gradient
descent achieves classification error ϵ on test data, meaning
both optimization and generalization occur.
Unlike prior work, the width is fully polylogarithmic in n, 1/δ,
and 1/ϵ; the width will additionally depend on the
separation margin of the limiting kernel, a quantity which is guaranteed
positive (assuming no inputs are parallel), can distinguish between true labels
and random labels, and can give a tight sample-complexity analysis in the
infinite-width setting.
The paper organization together with some details are described below.

    
  <Ref> studies gradient descent on the training set.
    Using the ℓ_1 geometry inherent in classification tasks, we prove that
    with any width at least polylogarithmic and any constant step size no larger
    than 1, gradient descent achieves training error  in
    (1/ϵ) iterations (cf.  <Ref>).
    As is common in the NTK literature <cit.>, we also show
    the parameters hardly change, which will be essential to our generalization
    analysis.

    
  <Ref> gives a test error bound.
    Concretely, using the preceding gradient descent analysis, and standard
    Rademacher tools and exploiting how little the weights moved, we show that
    with (1/ϵ^2) samples and (1/ϵ) iterations,
    gradient descent finds a solution with ϵ test error (cf.
    <Ref> and <Ref>).
    (As discussed in <Ref>, (1/ϵ) samples also
    suffice via a smoothness-based generalization bound, at the expense of large
    constant factors.)

    
  <Ref> considers stochastic gradient descent (SGD) with
    access to a standard stochastic online oracle.
    We prove that with width at least polylogarithmic and (1/ϵ)
    samples, SGD achieves an arbitrarily small test error (cf. <Ref>).

    
  <Ref> discusses the separation margin, which is in general a
    positive number, but reflects the difficulty of the classification problem
    in the infinite-width limit.
    While this margin can degrade all the way down to O(1/√(n)) for random
    labels, it can be much larger when there is a strong relationship between
    features and labels: for example, on the noisy 2-XOR data introduced
    in <cit.>, we show that the margin is Ω(1/ln(n)), and our
    SGD sample complexity is tight in the infinite-width case.

    
  <Ref> concludes with some open problems.




 §.§ Related work


There has been a large literature studying gradient descent on overparameterized
networks via the NTK.
The most closely related work is <cit.>,
which shows that a two-layer network trained by gradient descent with the logistic
loss can achieve a small test error, under the same assumption that the NTK with
respect to the first layer can separate the data distribution.
However, they analyze smooth activations, while we handle the ReLU.
They require Ω(1/ϵ^2) hidden units, (1/ϵ^4)
data samples, and O(1/ϵ^2) steps, while our result only needs
polylogarithmic hidden units, (1/ϵ^2) data samples, and
(1/ϵ) steps.

Additionally on shallow networks, <cit.> prove that on an
overparameterized two-layer network, gradient descent can globally minimize the
empirical risk with the squared loss.
Their result requires Ω(n^6/δ^3) hidden units.
<cit.> further reduce the required
overparameterization, but there is still a (n) dependency.
Using the same amount of overparameterization as <cit.>,
<cit.> further show that the two-layer network learned by gradient
descent can achieve a small test error, assuming that on the data distribution
the smallest eigenvalue of the limiting kernel is at least some positive
constant.
They also give a fine-grained characterization of the predictions made by
gradient descent iterates; such a characterization makes use of a special
property of the squared loss and cannot be applied to the logistic regression
setting.
<cit.> show that stochastic gradient descent (SGD) with the cross
entropy loss can learn a two-layer network with small test error, using
(ℓ,1/ϵ) hidden units, where ℓ is at least the covering
number of the support of the feature distribution using balls whose radii
are no larger than the smallest distance between two data points with different
labels.
<cit.> consider SGD on a two-layer network, and a variant of SGD on
a three-layer network.
The three-layer analysis further exhibits some properties not captured by the
NTK.
They assume a ground truth network with infinite-order smooth activations, and
they require the width to depend polynomially on 1/ϵ and some constants
related to the smoothness of the activations of the ground truth network.

On deep networks,
a variety of works have established low training error
<cit.>.
<cit.> show that SGD can minimize the regression loss for
recurrent neural networks, and <cit.> further prove a low
generalization error.
<cit.> show that using the same number of training examples, a
three-layer ResNet can learn a function class with a much lower test error than
any kernel method.
<cit.> assume that the NTK with respect to the second layer of a
two-layer network can separate the data distribution, and prove that gradient
descent on a deep network can achieve ϵ test error with
Ω(1/ϵ^4) samples and Ω(1/ϵ^14) hidden units.
<cit.> consider SGD with an online oracle and give a general
result.
Under the same assumption as in <cit.>, their result requires
Ω(1/ϵ^14) hidden units and sample complexity
(1/ϵ^2).
By contrast, with the same online oracle, our result only needs polylogarithmic
hidden units and sample complexity (1/ϵ).



 §.§ Notation


The dataset is denoted by {(x_i,y_i)}_i=1^n where x_i∈^d and
y_i∈-1,+1.
For simplicity, we assume that x_i_2=1 for any 1≤ i≤ n, which is
standard in the NTK literature.

The two-layer network has weight matrices W∈^m× d and a∈^m.
We use the following parameterization, which is also used in
<cit.>:

    f(x;W,a):=1/√(m)∑_s=1^ma_sσw_sx,

with initialization

    s0∼𝒩(0,I_d),  and   a_s∼unif-1,+1.

Note that in this paper, st denotes the s-th row of W at step t.
We fix a and only train W, as in
<cit.>.
We consider the ReLU activation σ(z):=max0,z, though our analysis
can be extended easily to Lipschitz continuous, positively homogeneous
activations such as leaky ReLU.

We use the logistic (binary cross entropy) loss ℓ(z):=ln1+exp(-z)
and gradient descent.
For any 1≤ i≤ n and any W, let f_i(W):=f(x_i;W,a).
The empirical risk and its gradient are given by

    (W):=1/n∑_i=1^nℓy_if_i(W),  and  (W)=1/n∑_i=1^nℓ'y_if_i(W)y_i∇ f_i(W).

For any t≥0, the gradient descent step is given by
t+1:=t-η_t(t).
Also define

    f_i^(t)(W):=∇ f_i(t)W,  and  ^(t)(W):=1/n∑_i=1^nℓy_if_i^(t)(W).

Note that f_i^(t)(t)=f_i(t).
This property generally holds due to homogeneity: for any W and
any 1≤ s≤ m,

    ∂ f_i/∂ w_s=1/√(m)a_sw_sx_i>0x_i,  and  ∂ f_i/∂ w_sw_s=1/√(m)a_sσw_sx_i,

and thus ∇ f_i(W)W=f_i(W).



§ EMPIRICAL RISK MINIMIZATION


In this section, we consider a fixed training set and empirical risk
minimization.
We first state our assumption on the separability of the NTK, and then give our
main result and a proof sketch.

The key idea of the NTK is to do the first-order Taylor approximation:

    f(x;W,a)≈ f(x;0,a)+∇_Wf(x;0,a)W-0.

In other words, we want to do learning using the features given by
∇ f_i(0)∈^m× d.
A natural assumption is that there exists ∈^m× d which can
separate [1]∇ f_i(0),y_i_i=1^n with a positive margin:

    min_1≤ i≤ ny_i∇ f_i(0)=min_1≤ i≤ ny_i 1/√(m)∑_s=1^ma_s ⟨_s,x_i⟩⟨s0,x_i⟩>0>0.


The infinite-width limit of <ref> is formalized as
<Ref>, with an additional bound on the (2,∞) norm of the
separator.
A concrete construction of  using <Ref> is given in
<ref>.

Let μ_𝒩 denote the Gaussian measure on ℝ^d, given by
the Gaussian density with respect to the Lebesgue measure on ℝ^d.
We consider the following Hilbert space

    ℋ:=w:ℝ^d→ℝ^d∫w(z)_2^2μ_𝒩(z)<∞.

For any x∈^d, define ϕ_x∈ by

    ϕ_x(z):=xzx>0,

and particularly define ϕ_i:=ϕ_x_i for the training input x_i.


    There exists ∈ℋ and γ>0, such that
    (z)_2≤ 1 for any z∈ℝ^d, and for any
    1≤ i≤ n,
    
    y_iϕ_i_:=y_i∫(z)ϕ_i(z)μ_(z)≥γ.



As discussed in <Ref>, the space  is the reproducing kernel
Hilbert space (RKHS) induced by the infinite-width NTK with respect to W, and
ϕ_x maps x into .
<Ref> supposes that the induced training set
{(ϕ_i,y_i)}_i=1^n can be separated by some ∈, with an
additional bound on (z)_2 which is crucial in our analysis.
It is also possible to give a dual characterization of the separation margin
(cf. <ref>), which also allows us to show that
<Ref> always holds when there are no parallel inputs (cf.
<Ref>).
However, it is often more convenient to construct  directly; see
<Ref> for some examples.

With <Ref>, we state our main empirical risk result.

    Under <Ref>, given any risk target ϵ∈(0,1) and
    any δ∈(0,1/3), let
    
    λ:=√(2ln(4n/δ))+ln(4/ϵ)/γ/4,  and   M:=4096λ^2/γ^6.

    Then for any m≥ M and any constant step size η≤1, with
    probability 1-3δ over the random initialization,
    
    1/T∑_t<T^(t)≤ϵ,  where   T:=⌈2λ^2/ηϵ⌉.

    Moreover for any 0≤ t<T and any 1≤ s≤ m,
    
    st-s0_2≤4λ/γ√(m).



While the number of hidden units required by prior work all have a polynomial
dependency on n, 1/δ or 1/ϵ, <Ref> only requires
m=Ωln(n/δ)+ln(1/ϵ)^2.
The required width has a polynomial dependency on 1/γ, which is an
adaptive quantity: while 1/γ can be (n) for random labels (cf.
<Ref>), it can be (n) when there is a strong
feature-label relationship, for example on the noisy 2-XOR data introduced in
<cit.> (cf. <Ref>).
Moreover, we show in <Ref> that if we want
[1]∇ f_i(0),y_i_i=1^n to be separable, which is the
starting point of an NTK-style analysis, the width has to depend polynomially
on 1/γ.

In the rest of <Ref>, we give a proof sketch of <Ref>.
The full proof is given in <Ref>.



 §.§ Properties at initialization


In this subsection, we give some nice properties of random initialization.

Given an initialization (0,a), for any 1≤ s≤ m, define

    _s:=1/√(m)a_s(s0),

where  is given by <Ref>.
Collect _s into a matrix ∈ℝ^m× d.
It holds that _s_2≤1/√(m), and [1]_F≤1.



<Ref> ensures that with high probability  has a positive
margin at initialization.

    Under <Ref>, given any δ∈(0,1) and any
    ϵ_1∈(0,γ), if m≥2ln(n/δ)/ϵ_1^2, then
    with probability 1-δ, it holds simultaneously for all 1≤ i≤ n
    that
    
    y_if_i^(0)[1]=y_i∇ f_i(0)≥γ-√(2ln(n/δ)/m)≥γ-ϵ_1.



For any W, any ϵ_2>0, and any 1≤ i≤ n, define

    α_i(W,ϵ_2)=1/m∑_s=1^mw_sx_i≤ϵ_2.

<Ref> controls α_i(0,ϵ_2).
It will help us show that  has a good margin during the training process.

    Under the condition of <Ref>, for any ϵ_2>0, with
    probability 1-δ, it holds simultaneously for all 1≤ i≤ n that
    
    α_i0,ϵ_2≤√(2/π)ϵ_2+√(ln(n/δ)/2m)≤ϵ_2+ϵ_1/2.



Finally, <Ref> controls the output of the network at
initialization.

    Given any δ∈(0,1), if m≥25ln(2n/δ), then with probability
    1-δ, it holds simultaneously for all 1≤ i≤ n that
    
    f(x_i;0,a)≤√(2ln4n/δ).





 §.§ Convergence analysis of gradient descent


We analyze gradient descent in this subsection.
First, define

    (W):=1/n∑_i=1^n-ℓ'y_if_i(W).

We have the following observations.

    
  * For any W and any 1≤ s≤ m,
    ∂ f_i/∂ w_s_2≤1/√(m), and thus
    ∇ f_i(W)_F≤1.
    Therefore by the triangle inequality, (W)_F≤(W).

    
  * The logistic loss satisfies 0≤-ℓ'≤1, and thus
    0≤(W)≤1.

    
  * The logistic loss satisfies -ℓ'≤ℓ, and thus
    (W)≤(W).


The quantity  first appeared in the perceptron analysis <cit.>
for the ReLU loss, and has also been analyzed in prior work <cit.>.
In this work,  specifically helps us prove the following result, which
plays an important role in obtaining a width which only depends on
(1/ϵ).

    For any t≥0 and any , if η_t≤1, then
    
    η_t(t)≤t-_F^2-t+1-_F^2+2η_t^(t)[1].

    Consequently, if we use a constant step size η≤1 for 0≤τ<t,
    then
    
    η∑_τ<t^(τ)+t-_F^2≤0-_F^2+2η∑_τ<t^^(τ)[1].


The proof of <Ref> starts from the standard iteration
guarantee:

    t+1-_F^2=t-_F^2-2η_t(t)t-+η_t^2(t)_F^2.

We can then handle the inner product term using the convexity of ℓ and
homogeneity of ReLU, and control (t)_F^2 by (t) using
the above properties of (t).
<Ref> is similar to
<cit.>, where the squared loss is
considered.

Using <Ref>, we
can prove <Ref>.
Below is a proof sketch; the full proof is given in <Ref>.

    
  * We first show that as long as
    st-s0_2≤4λ/(γ√(m)) for all
    1≤ s≤ m, it holds that
    ^(t)[1]0+λ≤ϵ/4.
    To see this, let us consider ^(0) first.
    For any 1≤ i≤ n, <Ref> ensures that
    |⟨_i(0),0⟩| is bounded, while <Ref>
    ensures that ⟨_i(0),⟩ is concentrated
    around γ with a large width.
    As a result, with the chosen λ in <Ref>, we can show that
    ⟨_i(0),0+λ⟩ is large, and
    ^(0)(0+λ) is small due to the exponential tail of the
    logistic loss.
    To further handle ^(t), we use a standard NTK argument to control
    ⟨_i(t)-_i(0),0+λ⟩ under
    the condition
    that st-s0_2≤4λ/(γ√(m)).

    
  * We then prove by contradiction that the above
    bound on st-s0_2 holds for at least the first T iterations.
    The key observation is that as long as
    ^(t)(0+λ)≤ϵ/4, we can use it and
    <Ref> to control ∑_τ<t^(τ), and
    then just invoke
    st-s0_2≤η∑_τ<t^(τ)/√(m).

    The quantity ∑_τ<t^(τ) has also been considered in
    prior work <cit.>, where it is bounded by
    √(t)√(∑_τ<t^(τ)^2) using the Cauchy-Schwarz
    inequality, which introduces a √(t) factor.
    To make the required width depend only on
    (1/ϵ), we also need an upper bound on
    ∑_τ<t^(τ) which depends only on
    (1/ϵ).
    Since the above analysis results in a √(t) factor, and in our case
    Ω(1/ϵ) steps are needed, it is unclear how to get a
    (1/ϵ) width using the analysis in
    <cit.>.
    By contrast, using <Ref>, we can show that
    ∑_τ<t^(τ)≤4λ/γ, which only depends on
    ln(1/ϵ).

    
  * The claims of <Ref> then follow directly from the above two
    steps and <Ref>.




§ GENERALIZATION


To get a generalization bound, we naturally extend <Ref> to the
following assumption.

    There exists ∈ℋ and γ>0, such that
    (z)_2≤ 1 for any z∈ℝ^d, and
    
    y∫(z)xzx>0μ_𝒩(z)≥γ

    for almost all (x,y) sampled from the data distribution .

The above assumption is also made in <cit.> for smooth
activations.
<cit.> make a similar separability assumption, but in the RKHS
induced by the second layer a; by contrast, <Ref> is on
separability in the RKHS induced by the first layer W.

Here is our test error bound with <Ref>.

    Under <Ref>, given any ϵ∈(0,1) and any
    δ∈(0,1/4), let λ and M be given as in
    <Ref>:
    
    λ:=√(2ln(4n/δ))+ln(4/ϵ)/γ/4,  and   M:=4096λ^2/γ^6.

    Then for any m≥ M and any constant step size η≤1, with probability
    1-4δ over the random initialization and data sampling,
    
    P_(x,y)∼yf(x;k,a)≤0≤2ϵ+16√(2ln(4n/δ))+ln(4/ϵ)/γ^2√(n)+6√(ln(2/δ)/2n),

    where k denotes the step with the minimum empirical risk before
    ⌈2λ^2/ηϵ⌉.


Below is a direct corollary of <Ref>.

    Under <Ref>, given any ϵ,δ∈(0,1), using
    a constant step size no larger than 1 and let
    
    n=1/γ^4ϵ^2,  and   m=Ωln(n/δ)+ln(1/ϵ)^2/γ^8,

    it holds with probability 1-δ that
    P_(x,y)∼yf(x;k,a)≤0≤ϵ, where k denotes the
    step with the minimum empirical risk in the first
    (1/γ^2ϵ) steps.


The proof of <Ref> uses the sigmoid mapping
-ℓ'(z)=e^-z/(1+e^-z), the empirical average (k), and the
corresponding population average
(k):=𝔼_(x,y)∼-ℓ'yf(x;k,a).
As noted in <cit.>, because
P_(x,y)∼yf(x;k,a)≤0≤2(k), it is enough to control
(k).
As (k) is controlled by <Ref>, it is enough to control
the generalization error (k)-(k).
Moreover, since -ℓ' is supported on [0,1] and 1-Lipschitz, it is enough
to bound the Rademacher complexity of the function space explored by gradient
descent.
Invoking the bound on k^⊤-0^⊤_2,∞ finishes the
proof.
The proof details are given in <Ref>.


    To get <Ref>, we use a Lipschitz-based Rademacher complexity
    bound.
    One can also use a smoothness-based Rademacher complexity bound
    <cit.> and get a sample complexity
    (1/γ^4ϵ).
    However, the bound will become complicated and some large constant will be
    introduced.
    It is an interesting open question to give a clean analysis based on
    smoothness.




§ STOCHASTIC GRADIENT DESCENT


There are some different formulations of SGD.
In this section, we consider SGD with an online oracle.
We randomly sample 0 and a, and fix a during training.
At step i, a data example (x_i,y_i) is sampled from the data distribution.
We still let f_i(W):=f(x_i;W,a), and perform the following update

    i+1:=i-η_iℓ'y_if_i(i)y_i_i(i).

Note that here i starts from 0.

Still with <Ref>, we show the following result.

    Under <Ref>, given any ϵ,δ∈(0,1), using
    a constant step size and m=Ωln(1/δ)+ln(1/ϵ)^2/γ^8, it holds with probability 1-δ that
    
    1/n∑_i=1^nP_(x,y)∼yf(x;i,a)≤0≤ϵ,  for   n=(1/γ^2ϵ).



Below is a proof sketch of <Ref>; the complete proof is given in
<Ref>.
For any i and W, define

    _i(W):=ℓy_i_i(i)W,  and  _i(W):=-ℓ'y_i_i(i)W.

Due to homogeneity, it holds that _i(i)=ℓy_if_i(i) and
_i(i)=-ℓ'y_if_i(i).



The first step is an extension of <Ref> to the SGD setting,
with a similar proof.

    With a constant step size η≤1, for any  and any i≥0,
    
    η∑_t<i^_t(t)+i-_F^2≤0-_F^2+2η∑_t<i^_t[1].



With <Ref>, we can also extend <Ref> to the SGD
setting and get a bound on ∑_i<n^_i(i), using a similar proof.
To further get a bound on the cumulative population risk
∑_i<n^(i), the key observation is that
∑_i<n^(i)-_i(i) is a martingale.
Using a martingale Bernstein bound, we prove the following lemma; applying it
finishes the proof of <Ref>.

    Given any δ∈(0,1), with probability 1-δ,
    
    ∑_t<i^(t)≤4 ∑_t<i^_t(t)+4ln1/δ.





§ ON SEPARABILITY


In this section we give some discussion on <Ref>, the
separability of the NTK.
The proofs are all given in <Ref>.

Given a training set (x_i,y_i)_i=1^n, the linear kernel is defined as
K_0(x_i,x_j):=x_ix_j.
The maximum margin achievable by a linear classifier is given by

    γ_0:=min_q∈Δ_n√(q⊙ y^⊤ K_0q⊙ y).

where Δ_n denotes the probability simplex and ⊙ denotes the
Hadamard product.
In addition to the dual definition <ref>, when γ_0>0 there
also exists a maximum margin classifier  which gives a primal
characterization of γ_0: it holds that _2=1 and
y_ix_i≥γ_0 for all i.

In this paper we consider another kernel, the infinite-width NTK with respect to
the first layer:

    K_1x_i,x_j    :=𝔼∂ f(x_i;0,a)/∂0,∂ f(x_j;0,a)/∂0
        =𝔼_w∼𝒩(0,I_d)[2]⟨ x_i⟨ x_i,w⟩>0,x_j⟨ x_j,w⟩>0⟩=⟨ϕ_i,ϕ_j⟩_.

Here ϕ and  are defined at the beginning of <Ref>.
Similar to the dual definition of γ_0, the margin given by K_1 is
defined as

    γ_1:=min_q∈Δ_n√(q⊙ y^⊤ K_1q⊙ y).

We can also give a primal characterization of γ_1 when it is positive.

    If γ_1>0, then there exists ∈ℋ such that
    _ℋ=1, and
    y_iϕ_i_≥γ_1 for any 1≤ i≤ n.
    Additionally (z)_2≤1/γ_1 for any z∈ℝ^d.

The proof is given in <Ref>, and uses the Fenchel duality theory.
Using the upper bound (z)_2≤1/γ_1, we can see that
γ_1 satisfies <Ref> with γ≥γ_1^2.
However, such an upper bound (z)_2≤1/γ_1 might be too
loose, which leads to a bad rate.
In fact, as shown later, in some cases we can construct  directly which
satisfies <Ref> with a large γ.
For this reason, we choose to make <Ref> instead of assuming a
positive γ_1.

However, we can use γ_1 to show that <Ref> always holds
when there are no parallel inputs.
<cit.> prove that if for any two feature vectors
x_i and x_j, we have x_i-x_j_2≥θ and x_i+x_j_2≥θ
for some θ>0, then the minimum eigenvalue of K_1 is at least
θ/(100n^2).
For arbitrary labels y∈{-1,+1}^n, since
q⊙ y_2≥1/√(n), we have the worst case bound
γ_1^2≥θ/100n^3.
A direct improvement of this bound is θ/100n_S^3, where n_S
denotes the number of support vectors, which could be much smaller than n with
real world data.

On the other hand, given any training set (x_i,y_i)_i=1^n which may
have a large margin, replacing y with random labels would destroy the margin,
which is what should be expected.

    Given any training set (x_i,y_i)_i=1^n, if the true labels y
    are replaced with random labels
    ϵ∼unif{-1,+1}^n, then with probability 0.9
    over the random labels, it holds that γ_1≤1/√(20n).


Although the above bounds all have a polynomial dependency on n, they hold for
arbitrary or random labels, and thus do not assume any relationship between the
features and labels.
Next we give some examples where there is a strong feature-label relationship,
and thus a much larger margin can be proved.









 §.§ The linearly separable case


Suppose the data distribution is linearly separable with margin γ_0:
there exists a unit vector  such that yx≥γ_0 almost
surely.
Then we can define (z):= for any z∈^d.
For almost all (x,y), we have

    y∫(z)xzx>0μ_(z)     =∫ yxzx>0μ_(z) 
       ≥γ∫zx>0μ_(z) 
        =γ_0/2,

and thus <Ref> holds with γ=γ_0/2.



 §.§ The noisy 2-XOR distribution


We consider the noisy 2-XOR distribution introduced in <cit.>.
It is the uniform distribution over the following 2^d
points:

    (x_1,x_2,y,x_3,…,x_d)∈   [3]1/√(d-1),0,1,0,1/√(d-1),-1,-1/√(d-1),0,1,0,-1/√(d-1),-1
       ×-1/√(d-1),1/√(d-1)^d-2.

The factor 1/√(d-1) ensures that x_2=1, and ×
above denotes the Cartesian product.
Here the label y only depends on the first two coordinates of the input x.

To construct , we first decompose ^2 into four regions:

    A_1     :=(z_1,z_2)z_1≥0,|z_1|≥|z_2|, 
    
        A_2     :=(z_1,z_2)z_2>0,|z_1|<|z_2|, 
    
        A_3     :=(z_1,z_2)z_1≤0,|z_1|≥|z_2|∖{(0,0)}, 
    
        A_4     :=(z_1,z_2)z_2<0,|z_1|<|z_2|.

Then  can de defined as follows.
It only depends on the first two coordinates of z.

    (z):=
        
            (1,0,0,…,0)    if (z_1,z_2)∈ A_1, 
    
            (0,-1,0,…,0)    if (z_1,z_2)∈ A_2, 
    
            (-1,0,0,…,0)    if (z_1,z_2)∈ A_3, 
    
            (0,1,0,…,0)    if (z_1,z_2)∈ A_4.


The following result shows that γ=Ω(1/d).
Note that n could be as large as 2^d, in which case γ is basically
O1/ln(n).

    For any (x,y) sampled from the noisy 2-XOR distribution and any d≥3,
    it holds that
    
    y∫(z)xzx>0μ_(z)≥1/60d.



We can prove two other interesting results for the noisy 2-XOR data.



  
The width needs a (1/γ) dependency for initial separability.

The first step of an NTK analysis is to show that
[1]∇ f_i(0),y_i_i=1^n is separable.
<Ref> gives an example where
[1]∇ f_i(0),y_i_i=1^n is nonseparable when the network
is narrow.

    Let D={(x_i,y_i)}_i=1^4 denote an arbitrary subset of the noisy 2-XOR
    dataset such that x_i's have the same last (d-2) coordinates.
    For any d≥20, if m≤√(d-2)/4, then with probability 1/2 over
    the random initialization of 0, for any weights V∈^m× d,
    it holds that y_iV∇ f_i(0)≤0 for at least one
    i∈{1,2,3,4}.


For the noisy 2-XOR data, the separator  given by <ref>
has margin γ=Ω(1/d), and 1/γ=O(d).
As a result, if we want [1]∇ f_i(0),y_i_i=1^n to be
separable, the width has to be Ω(1/√(γ)).
For a smaller width, gradient descent might still be able to solve the problem,
but a beyond-NTK analysis would be needed.



  
A tight sample complexity upper bound for the infinite-width NTK.

<cit.> give a d^2 sample complexity lower bound for any NTK
classifier on the noisy 2-XOR data.
It turns out that γ could give a matching sample complexity upper
bound for the NTK and SGD.

<cit.> consider the infinite-width NTK with respect to both layers.
For the first layer, the infinite-width NTK K_1 is defined in <Ref>,
and the corresponding RKHS  and RKHS mapping ϕ is defined in
<Ref>.
For the second layer, the infinite width NTK is defined by

    K_2x_i,x_j    :=𝔼∂ f(x_i;0,a)/∂ a,∂ f(x_j;0,a)/∂ a
        =𝔼_w∼𝒩(0,I_d)[2]σ⟨ w,x_i⟩σ⟨ w,x_j⟩.

The corresponding RKHS  and inner product ⟨ w_1,w_2⟩_ are
given by

    :=w:^d→∫ w(z)^2μ_𝒩(z)<∞,  and  ⟨ w_1,w_2⟩_=∫ w_1(z)w_2(z)μ_𝒩(z).

Given any x∈^d, it is mapped into ψ_x∈, where
ψ_x(z):=σ⟨ z,x⟩.
It holds that K_2(x_i,x_j)=⟨ψ_x_i,ψ_x_j⟩_.
The infinite-width NTK with respect to both layers is just K_1+K_2.
The corresponding RHKS is just × with the inner product

    ⟨ (v_1,w_1),(v_2,w_2)⟩_×=⟨ v_1,v_2⟩_+⟨ w_1,w_2⟩_.


The classifier  considered in <ref> has a unit norm (i.e.,
_=1) and margin γ on the space .
On ×, it is enough to consider (,0), which also has a unit
norm and margin γ.
Since the infinite-width NTK model is a linear model in ×,
<cit.> can be used to show that SGD on the RKHS
× could obtain a test error of ϵ with a sample complexity
of (1/γ^2ϵ).
(The analysis in <cit.> is done in ^d, but it still works with a
well-defined inner product.)
Since γ=Ω(1/d), to achieve a constant test accuracy we need
(d^2) samples.
This mathces (up to logarithmic factors) the sample complexity lower bound of
d^2 given by <cit.>.



§ OPEN PROBLEMS


In this paper, we analyze gradient descent on a two-layer network in the NTK
regime, where the weights stay close to the initialization.
It is an interesting open question if gradient descent learns something beyond
the NTK, after the iterates move far enough from the initial weights.
It is also interesting to extend our analysis to other architectures, such as
multi-layer networks,
convolutional networks, and residual networks.
Finally, in this paper we only discuss binary classification; it is interesting
to see if it is possible to get similar results for other tasks, such as
regression.



 §.§ Acknowledgements


The authors are grateful for support from the NSF under grant IIS-1750051,
and from NVIDIA via a GPU grant.


plainnat





§ OMITTED PROOFS FROM <REF>



    By <Ref>, given any 1≤ i≤ n,
    
    μ:=𝔼_w∼𝒩(0,I_d)y_i(w)x_iwx_i>0≥γ.

    On the other hand,
    
    y_if_i^(0)[1]=1/m∑_s=1^my_i(s0)x_is0x_i>0

    is the empirical mean of i.i.d. r.v.'s supported on [-1,+1] with mean
    μ.
    Therefore by Hoeffding's inequality, with probability
    1-δ/n,
    
    y_if_i^(0)[1]-γ≥ y_if_i^(0)[1]-μ≥-√(2ln(n/δ)/m).

    Applying a union bound finishes the proof.



    Given any fixed ϵ_2 and 1≤ i≤ n,
    
    𝔼α_i(0,ϵ_2)=wx_i≤ϵ_2≤2ϵ_2/√(2π)=√(2/π)ϵ_2,

    because wx_i is a standard Gaussian r.v. and the density of
    standard Gaussian has maximum 1/√(2π).
    Since α_i(0,ϵ_2) is the empirical mean of Bernoulli r.v.'s, by
    Hoeffding's inequality, with probability 1-δ/n,
    
    α_i(0,ϵ_2)≤𝔼α_i(0,ϵ_2)+√(ln(n/δ)/2m)≤√(2/π)ϵ_2+√(ln(n/δ)/2m).

    Applying a union bound finishes the proof.


To prove <Ref>, we need the following technical result.


    Consider the random vector X=(X_1,…,X_m), where X_i=σ(Z_i) for
    some σ:ℝ→ℝ that is 1-Lipschitz, and Z_i are
    i.i.d. standard Gaussian r.v.'s.
    Then the r.v. X_2 is 1-sub-Gaussian, and thus with probability
    1-δ,
    
    X_2-𝔼X_2≤√(2ln(1/δ)).



    Given a∈ℝ^m, define
    
    f(a)=√(∑_i=1^mσ(a_i)^2)=σ(a)_2,

    where σ(a) is obtained by applying σ coordinate-wisely to a.
    For any a,b∈ℝ^m, by the triangle inequality, we have
    
    f(a)-f(b)= σ(a)_2-σ(b)_2   ≤σ(a)-σ(b)_2=√(∑_i=1^mσ(a_i)-σ(b_i)^2),

    and by further using the 1-Lipschitz continuity of σ, we have
    
    f(a)-f(b)≤√(∑_i=1^mσ(a_i)-σ(b_i)^2)≤√(∑_i=1^m(a_i-b_i)^2)=a-b_2.

    As a result, f is a 1-Lipschitz continuous function w.r.t. the ℓ_2
    norm, indeed f(X) is 1-sub-Gaussian
    and the bound follows by Gaussian concentration
    <cit.>.



    Given 1≤ i≤ n, let h_i=σ(0x_i)/√(m).
    By <Ref>, h_i_2 is sub-Gaussian with variance
    proxy 1/m, and with probability at least 1-δ/2n over
    0,
    
    h_i_2-𝔼h_i_2≤√(2ln(2n/δ)/m)≤√(2ln(2n/δ)/25ln(2n/δ))≤1-√(2)/2.

    On the other hand, by Jensen's inequality,
    
    𝔼h_i_2≤√(𝔼h_i_2^2)=√(2)/2.

    As a result, with probability 1-δ/2n, it holds that
    h_i_2≤1.
    By a union bound, with probability 1-δ/2 over 0,
    for all 1≤ i≤ n, we have h_i_2≤1.

    For any 0 such that the above event holds, and for any 1≤ i≤ n,
    the r.v. h_ia is sub-Gaussian with variance proxy
    h_i_2^2≤1.
    By Hoeffding's inequality, with probability 1-δ/2n over
    a,
    
    h_ia=f(x_i;0,a)≤√(2ln4n/δ).

    By a union bound, with probability 1-δ/2 over a,
    for all 1≤ i≤ n, we have
    f(x_i;0,a)≤√(2ln4n/δ).

    The probability that the above events all happen is at least
    (1-δ/2)(1-δ/2)≥1-δ, over 0
    and a.



    We have
    
    t+1-_F^2=t-_F^2-2η_t(t)t-+η_t^2(t)_F^2.

    The first order term of <ref> can be handled using the convexity of
    ℓ and homogeneity of ReLU:
    
    (t)t-    =1/n∑_i=1^nℓ'y_if_i(t)y_i_i(t)t-
        =1/n∑_i=1^nℓ'y_if_i(t)y_if_i(t)-y_if_i^(t)[1]
       ≥1/n∑_i=1^nℓy_if_i(t)-ℓy_if_i^(t)[1]=(t)-^(t)[1].


    The second-order term of <ref> can be bounded as follows
    
    η_t^2(t)_F^2≤η_t^2(t)^2≤η_t(t)≤η_t(t),

    because (t)_F≤(t), and η_t,(t)≤1, and
    (t)≤(t).
    Combining <ref> gives
    
    η_t(t)≤t-_F^2-t+1-_F^2+2η_t^(t)[1].

    Telescoping gives the other claim.



    The required width ensures that with probability 1-3δ,
    <Ref> hold with
    ϵ_1=γ^2/8 and ϵ_2=4λ/(γ√(m)).

    Let t_1 denote the first step such that there exists 1≤ s≤ m with
    st_1-s0_2>4λ/(γ√(m)).
    Therefore for any 0≤ t<t_1 and any 1≤ s≤ m, it holds that
    st-s0_2≤4λ/(γ√(m)).
    In addition, we let :=0+λ.

    We first prove that for any 0≤ t<t_1, it holds that
    ^(t)[1]≤ϵ/4.
    Since ln(1+r)≤ r for any r,
    the logistic satisfies ℓ(z) = ln(1+exp(-z))≤exp(-z),
    and it is enough to prove that for any 1≤ i≤ n,
    
    y_i_i(t)≥ln4/ϵ.

    We will split the left hand side into three terms and control them individually:
    
    y_i_i(t)=y_i_i(0)0+y_i_i(t)-_i(0)0+λ y_i_i(t).

    
        
  * The first term of <ref> can be controlled using
        <Ref>:
        
    y_i_i(0)0≤√(2ln(4n/δ)).


        
  * The second term of <ref> can be written as
        
    y_i_i(t)-_i(0)0=y_i 1/√(m)∑_s=1^ma_s[1]stx_i>0-[1]s0x_i>0s0x_i.

        Let S_c:=s[1]stx_i>0-[1]s0x_i>00,1≤ s≤ m.
        Note that s∈ S_c implies
        
    s0x_i≤st-s0x_i≤st-s0_2x_i_2=st-s0_2≤4λ/(γ√(m)) = _2.

        Therefore <Ref> ensures that
        
    |S_c|
              ≤ s  |s0x_i| ≤_2 ≤ m4λ/γ√(m)+ϵ_1/2=m4λ/γ√(m)+γ^2/16.

        and thus
        
    y_i_i(t)-_i(0)0≤1/√(m)·|S_c|·4λ/γ√(m)≤16λ^2/γ^2√(m)+λγ/4≤λγ/2,

        where in the last step we use the condition that
        m≥4096λ^2/γ^6.

        
  * The third term of <ref> can be bounded as follows:
          by <Ref>,
        
    y_i_i(t)    =y_i_i(0)+y_i_i(t)-_i(0)
       ≥γ-ϵ_1+y_i_i(t)-_i(0).

        In addition,
        
    y_i_i(t)-_i(0)    =y_i1/m∑_i=1^mstx_i>0-s0x_i>0(s0)x_i
       ≥-1/m·|S_c|≥-4λ/γ√(m)-ϵ_1/2≥-γ^2/16-ϵ_1/2,

        where we use m≥4096λ^2/γ^6.
        Therefore,
        
    y_i_i(t)≥γ-ϵ_1-γ^2/16-ϵ_1/2=γ-γ^2/4≥3γ/4.

    
    Putting <ref> into <ref>, we
    have
    
    y_i_i(t)≥-√(2ln4n/δ)-λγ/2+3λγ/4=λγ/4-√(2ln4n/δ)=ln4/ϵ,

    for the λ given in the statement of <Ref>.
    Consequently, for any 0≤ t<t_1, it holds that
    ^(t)[1]≤ϵ/4.

    Let T:=⌈2λ^2/ηϵ⌉.
    The next claim is that t_1≥ T.
    To see this, note that <Ref> ensures
    
    t_1-_F^2≤0-_F^2+2η∑_t<t_1^^(t)[1]≤λ^2+ϵ/2η t_1.

    Suppose t_1<T, then we have t_1≤2λ^2/ηϵ,
    and thus t_1-_F^2≤2λ^2.
    As a result, using _F≤ 1 and the definition of ,
    
    √(2)λ≥t_1-_F≥t_1-    =t_1-0--0
       ≥t_1-0-λ.

    Moreover, due to <ref>,
    
    t_1-0=-η∑_τ<t_1^(τ)    =η∑_τ<t_1^1/n∑_i=1^n-ℓ'y_if_i(τ)y_i_i(τ)
       ≥η∑_τ<t_1^(τ)3γ/4.

    As a result,
    
    η∑_τ<t_1^(τ)≤4(√(2)+1)λ/3γ≤4λ/γ.

    Furthermore, by the triangle inequality, for any 1≤ s≤ m
    
    st-s0_2    ≤η∑_τ<t^1/n∑_i=1^nℓ'y_if_i(τ)y_i∂ f_i/∂sτ_2 
       ≤η∑_τ<t^1/n∑_i=1^nℓ'y_if_i(τ)·∂ f_i/∂sτ_2 
       ≤η∑_τ<t^(τ)1/√(m)
       ≤η∑_τ<t_1^(τ)1/√(m)≤4λ/γ√(m),

    which contradicts the definition of t_1.
    Therefore t_1≥ T.

    Now we are ready to prove the claims of <Ref>.
    The bound on st-s0_2 follow by repeating the
    steps in <ref>.
    The risk guarantee follows from <Ref>:
    
    1/T∑_t<T^(t)≤0-_F^2/η T+2/T∑_t<T^^(t)[1]≤ϵ/2+ϵ/2=ϵ.





§ OMITTED PROOFS FROM <REF>


The proof of <Ref> is based on Rademacher complexity.
Given a sample S=(z_1,…,z_n) (where z_i=(x_i,y_i)) and a function class
, the Rademacher complexity of  on S is defined as

    ∘ S:=1/n𝔼_ϵ∼{-1,+1}^nsup_h∈∑_i=1^nϵ_ih(z_i).


We will use the following general result.
<cit.>
    If h(z)∈[a,b], then with probability 1-δ,
    
    sup_h∈𝔼_z∼h(z)-1/n∑_i=1^nh(z_i)≤2∘ S+3(b-a)√(ln(2/δ)/2n).



We also need the following contraction lemma.
Consider a feature sample X=(x_1,…,x_n) and a function class  on
X.
For each 1≤ i≤ n, let g_i:ℝ→ℝ denote a
K-Lipschitz function.
Let g∘ denote the class of functions which map x_i to
g_i(f(x_i)) for some f∈.
<cit.>
    g∘∘ X≤ K∘ X.


To prove <Ref>, we need one more Rademacher complexity bound.
Given a fixed initialization (0,a), consider the following classes:

    _ρ:=W∈ℝ^m× dw_s-s0_2≤ρ for any 1≤ s≤ m,

and

    _ρ:=x↦ f(x;W,a)W∈_ρ.

Given a feature sample X, the following <Ref> controls the Rademacher
complexity of _ρ∘ X.
A similar version was given in <cit.>, and the proof is
similar to the proof of <cit.> which
also pushes the supremum through and handles each hidden unit separately.

    _ρ∘ X≤ρ√(m/n).


    We have
    
    𝔼_ϵsup_W∈_ρ∑_i=1^nϵ_if(x_i;W,a)    =𝔼_ϵsup_W∈_ρ∑_i=1^nϵ_i ∑_s=1^m1/√(m)a_sσw_sx_i
        =𝔼_ϵ1/√(m)sup_W∈_ρ∑_s=1^m∑_i=1^nϵ_ia_sσw_sx_i
        =𝔼_ϵ1/√(m)∑_s=1^msup_w_s-s0_2≤ρ∑_i=1^nϵ_ia_sσw_sx_i
        =1/√(m)∑_i=1^m𝔼_ϵsup_w_s-s0_2≤ρ∑_i=1^nϵ_ia_sσw_sx_i.

    Note that for any 1≤ s≤ m, the mapping z↦ a_sσ(z) is
    1-Lipschitz, and thus <Ref> gives
    
    𝔼_ϵsup_W∈_ρ∑_i=1^nϵ_if(x_i;W,a)   ≤1/√(m)∑_i=1^m𝔼_ϵsup_w_s-s0_2≤ρ∑_i=1^nϵ_ia_sσw_sx_i
       ≤1/√(m)∑_i=1^m𝔼_ϵsup_w_s-s0_2≤ρ∑_i=1^nϵ_iw_sx_i.

    Invoking the Rademacher complexity of linear classifiers
    <cit.> then gives
    
    Rad_ρ∘ X=1/n𝔼_ϵsup_W∈_ρ∑_i=1^nϵ_if(x_i;W,a)≤ρ√(m)/√(n).



Now we are ready to prove the main generalization result <Ref>.

    Fix an initialization (0,a), and let
    :=(x,y)↦-ℓ'yf(x)f∈_ρ.
    Since for any h∈ and any z, h(z)∈[0,1], <Ref>
    ensures that with probability 1-δ over the data sampling,
    
    sup_h∈𝔼_z∼h(z)-1/n∑_i=1^nh(z_i)=sup_W∈_ρ(W)-(W)≤2∘ S+3√(ln(2/δ)/2n).

    Since for each 1≤ i≤ n, the mapping z↦-ℓ'(y_iz) is
    (1/4)-Lipschitz, <Ref> further ensures that
    ∘ S≤_ρ∘ X/4, and thus
    
    sup_W∈_ρ(W)-(W)≤ρ√(m)/2√(n)+3√(ln(2/δ)/2n).


    On the other hand, <Ref> ensures that under the conditions of
    <Ref>, for any fixed dataset, with probability 1-3δ over
    the random initialization, we have
    
    (k)≤(k)≤ϵ,  and  sk-s0_2≤4λ/γ√(m).

    As a result, invoking <ref> with
    ρ=4λ/(γ√(m)), with probability 1-4δ over
    the random initialization and data sampling,
    
    (k)≤(k)+2λ/γ√(n)+3√(ln(2/δ)/2n)≤ϵ+8√(2ln(4n/δ))+ln(4/ϵ)/γ^2√(n)+3√(ln(2/δ)/2n).

    Invoking P_(x,y)∼yf(x;W,a)≤0≤2(W) finishes the proof.




§ OMITTED PROOFS FROM <REF>



    Recall that _t(t)_F≤1, we have
    
    t+1-_F^2    ≤t-_F^2-2ηℓ'y_tf_t(t)y_t_t(t)t-+η^2ℓ'y_tf_t(t)^2.

    Similar to the proof of <Ref>, the first order term of
    <ref> can be handled using the convexity of ℓ and
    homogeneity of ReLU as follows
    
    ℓ'y_tf_t(t)y_t_t(t)t-≥_t(t)-_t[1],

    and the second-order term of <ref> can be bounded as follows
    
    η^2ℓ'y_tf_t(t)^2≤-ηℓ'y_tf_t(t)≤ηℓy_tf_t(t)=η_t(t),

    since η,-ℓ'≤1 and -ℓ'≤ℓ.
    Combining <ref> gives
    
    η_t(t)≤t-_F^2-t+1-_F^2+2η_t[1].

    Telescoping gives the claim.


With <Ref>, we give the following result, which is an
extension of <Ref> to the SGD setting.

    Under <Ref>, given any ϵ∈(0,1), any
    δ∈(0,1/3), and any positive integer n_0, let
    
    λ:=√(2ln(4n_0/δ))+ln(4/ϵ)/γ/4,  and   M:=4096λ^2/γ^6.

    For any m≥ M and any constant step size η≤1, if
    n_0≥ n:=⌈2λ^2/ηϵ⌉, then with
    probability 1-3δ,
    
    1/n∑_i<n^_i(i)≤ϵ.



    We first sample n_0 data examples
    (x_0,y_0),…,(x_n_0-1,y_n_0-1), and then feed (x_i,y_i) to SGD
    at step i.
    We only consider the first n_0 steps.

    The proof is similar to the proof of <Ref>.
    Let n_1 denote the first step before n_0 such that there exists some
    1≤ s≤ m with
    sn_1-s0_2>4λ/(γ√(m)).
    If such a step does not exist, let n_1=n_0.

    Let :=0+λ, in exactly the same way as in
    <Ref>, we can show that with probability 1-3δ, for any
    0≤ i<n_1,
    
    y_i_i(i)≥ln4/ϵ,  and thus  _i[1]≤ϵ/4.


    Now consider n:=⌈2λ^2/ηϵ⌉.
    Using <Ref>, in the same way as the proof of
    <Ref> (replacing (τ) with _i(i), etc.), we
    can show that n≤ n_1.
    Then invoking <Ref> again, we get
    
    1/n∑_i<n^_i(i)≤1/n∑_i<n^_i(i)≤[1]0-_F^2/η n+2/n∑_i<n^_i[1]≤ϵ/2+ϵ/2=ϵ.



Next we prove <Ref>.
We need the following martingale Bernstein bound.
<cit.>
    Let (M_t,ℱ_t)_t≥0 denote a martingale with M_0=0 and
    ℱ_0 be the trivial σ-algebra.
    Let (Δ_t)_t≥1 denote the corresponding martingale difference
    sequence, and let
    
    V_t:=∑_j=1^t𝔼[Δ_j^2|ℱ_j-1]

    denote the sequence of conditional variance.
    If Δ_t≤ R a.s., then for any δ∈(0,1), with probability at
    least 1-δ,
    
    M_t≤V_t/R(e-2)+Rln(1/δ).



    For any i≥0, let z_i denote (x_i,y_i), and z_0,i denote
    (z_0,…,z_i).
    Note that the quantity ∑_t<i^(t)-_t(t) is a
    martingale w.r.t. the filtration σ(z_0,i-1).
    The martingale difference sequence is given by
    (t)-_t(t), which satisfies
    
    (t)-_t(t)=_(x,y)∼-ℓ'yf(x;t,a)+ℓ'y_tf(x_t;t,a)≤1,

    since -1≤ℓ'≤0.
    Moreover, we have
    
    (t)-_t(t)^2|σ(z_0,t-1)
    
            =     (t)^2-2(t)_t(t)|σ(z_0,t-1)+_t(t)^2|σ(z_0,t-1)
    
            =     -(t)^2+_t(t)^2|σ(z_0,t-1)
    ≤    _t(t)^2|σ(z_0,t-1)
    ≤    _t(t)|σ(z_0,t-1)
    
            =     (t).

    Invoking <Ref> with <ref> gives
    that with probability 1-δ,
    
    ∑_t<i^(t)-_t(t)≤(e-2)∑_t<i^(t)+ln1/δ.

    Consequently,
    
    ∑_t<i^(t)≤ 4∑_t<i^_t(t)+4ln1/δ.



Finally, we prove <Ref>.

    Suppose the condition of <Ref> holds.
    Then we have for n=⌈2λ^2/ηϵ⌉, with
    probability 1-3δ,
    
    1/n∑_i<n^_i(i)≤ϵ.

    Further invoking <Ref> gives that with probability
    1-4δ,
    
    1/n∑_i<n^(i)≤4/n∑_i<n^_i(i)+4/nln1/δ≤ 5ϵ.

    Since P_(x,y)∼yf(x;W,a)≤0≤2(W), we get
    
    1/n∑_i=1^nP_(x,y)∼yf(x;i,a)≤0≤ 10ϵ.


    For the condition of <Ref> to hold, it is enough to let
    
    n_0=Θln(1/δ)/ηγ^2ϵ^2,

    which gives
    
    M=Θln(1/δ)+ln(1/ϵ)^2/γ^8  and   n=Θln(1/δ)+ln(1/ϵ)^2/γ^2ϵ.





§ OMITTED PROOFS FROM <REF>



    Define f:ℋ→ℝ by
    
    f(w):=1/2∫w(z)_2^2μ_𝒩(z)=1/2w_ℋ^2.

    It holds that f is continuous, and f^* has the same form.
    Define g:ℝ^n→ℝ by
    
    g(p):=max_1≤ i≤ np_i,

    with conjugate
    
    g^*(q)=
            
                0,    if q∈Δ_n, 
    
                +∞,    o.w.

    Finally, define the linear mapping A:ℋ→ℝ^n by
    (Aw)_i=y_iwϕ_i_.

    Since f, f^*, g and g^* are lower semi-continuous, and
    𝐝𝐨𝐦 g-A 𝐝𝐨𝐦 f=ℝ^n, and
    𝐝𝐨𝐦 f^*-A^*𝐝𝐨𝐦 g^*=ℋ,
    Fenchel duality may be applied in each direction <cit.>,
    and ensures that
    
    inf_w∈ℋf(w)+g(Aw)=sup_q∈ℝ^n-f^*(A^*q)-g^*(-q).

    with optimal primal-dual solutions (,).
    Moreover
    
    inf_w∈ℋ(f(w)+g(Aw))     =inf_w∈ℋ,u∈ℝ^nsup_q∈ℝ^n(f(w)+g(Aw+u)+⟨ q,u⟩) 
       ≥sup_q∈ℝ^ninf_w∈ℋ,u∈ℝ^n(f(w)+g(Aw+u)+⟨ q,u⟩) 
        =sup_q∈ℝ^ninf_w∈ℋ,u∈ℝ^nf(w)-A^*qw_+g(Aw+u)--qAw+u
        =sup_q∈ℝ^n-f^*(A^*q)-g^*(-q).

    By strong duality, the inequality holds with equality.
    It follows that
    
    =A^*,  and  𝐬𝐮𝐩𝐩(-)⊂_1≤ i≤ n (A)_i.


    Now let us look at the dual optimization problem.
    It is clear that
    
    sup_q∈ℝ^n-f^*(A^*q)-g^*(-q)=-inf_q∈Δ_nf^*(A^*q).

    In addition, we have
    
    f^*(A^*q)     =1/2∫∑_i=1^nq_iy_iϕ_i(z)_2^2μ_𝒩(z) 
        =1/2∫∑_i,j=1^nq_iq_jy_iy_jϕ_i(z)ϕ_j(z)μ_𝒩(z) 
        =1/2∑_i,j=1^nq_iq_jy_iy_j∫ϕ_i(z)ϕ_j(z)μ_𝒩(z) 
       =1/2∑_i,j=1^nq_iq_jy_iy_jK_1(i,j)=1/2(q⊙ y)^⊤ K_1(q⊙ y),

    and thus f^*(A^*)=γ_1^2/2.
    Since =A^*, we have that
    _ℋ=γ_1.
    In addition,
    
    g(A)=-f^*A^*-f=-γ_1^2,

    and thus - has margin γ_1^2.
    Moreover, we have
    
    (z)=∑_i=1^n_iy_iϕ_i(z)=∑_i=1^n_iy_ix_izx_i>0,

    and thus (z)_2≤1.
    Therefore, =-/γ_1 satisfies all requirements of
    <Ref>.



    Let  denote the uniform probability vector
    (1/n,…,1/n).
    Note that
    
    _ϵ∼unif{-1,+1}^n⊙ϵ^⊤ K_1⊙ϵ    =_ϵ∼unif{-1,+1}^n∑_i,j=1^n1/n^2ϵ_iϵ_jK_1(x_i,x_j)
        =1/n^2∑_i,j=1^n_ϵ∼unif{-1,+1}^nϵ_iϵ_jK_1(x_i,x_j)
        =1/n^2∑_i=1^nK_1(x_i,x_i)=1/2n.

    Since 0≤⊙ϵ^⊤ K_1⊙ϵ≤1
    for any ϵ, by Markov's inequality with probability 0.9, it holds
    that ⊙ϵ^⊤ K_1⊙ϵ≤1/(20n),
    and thus γ_1≤1/√(20n).



    By symmetry, we only need to consider an (x,y) where
    (x_1,x_2,y)=(1/√(d-1),0,1).
    Let z_p,q denote (z_p,z_p+1,…,z_q), and similarly define
    x_p,q.
    We have
    
    y∫(z)xzx>0μ_(z) 
    
            =     y∫∫(z)xzx>0μ_(z_3,d)μ_(z_1,2) 
    
            =     y∫(z)_1,2x_1,2∫z_1,2x_1,2+z_3,dx_3,d>0μ_(z_3,d)μ_(z_1,2) 
    
            =     ∑_i=1^4y∫(z)_1,2x_1,2∫z_1,2x_1,2+z_3,dx_3,d>0μ_(z_3,d)z_1,2∈ A_iμ_(z_1,2),

    where <ref> is due to the independence between z_1,2 and
    z_3,d, and in <ref> we use the fact that (z)_1,2
    only depends on z_1,2 and (z)_3,d are all zero.
    Since (z)_1,2x_1,2=0 for z_1,2∈ A_2∪ A_4, we only
    need to consider A_1 and A_3 in <ref>.
    For simplicity, we will denote z_1,2 by p∈^2, and (z)_1,2
    by (p), and z_3,d by q∈^d-2.

    For any nonzero p∈ A_1, we have -p∈ A_3, and
    (p)x_1,2=1/√(d-1).
    Therefore
    
    y(p)x_1,2∫px_1,2+qx_3,d>0μ_(q)
        +y(-p)x_1,2∫-px_1,2+qx_3,d>0μ_(q)
    
            =     1/√(d-1)∫p_1/√(d-1)+qx_3,d>0--p_1/√(d-1)+qx_3,d>0μ_(q) 
    
            =     1/√(d-1)-p_1/√(d-1)≤qx_3,d≤p_1/√(d-1).

    Let φ denote the density function of the standard Gaussian
    distribution, and for c>0, let U(c) denote the probability that a
    standard Gaussian random variable lies in the interval [-c,c]:
    
    U(c):=∫_-c^cφ(t) t.

    Since qx_3,d is a Gaussian variable with standard deviation
    √((d-2)/(d-1)), we have
    
    -p_1/√(d-1)≤qx_3,d≤p_1/√(d-1)=Up_1/√(d-2).

    Plugging <ref> into <ref>
    gives:
    
    y∫(z)xzx>0μ_(z)     =1/√(d-1)∫ Up_1/√(d-2)p∈ A_1μ_(p) 
        =1/√(d-1)∫_0^∞ Up_1/√(d-2)∫_-p_1^p_1φ(p_2) p_2φ(p_1) p_1 
        =1/√(d-1)∫_0^∞ Up_1/√(d-2)U(p_1)φ(p_1) p_1 
       ≥1/√(d-1)∫_0^1Up_1/√(d-2)U(p_1)φ(p_1) p_1.

    For t∈[-1,+1], it holds that φ(t)≥1√(2π e), and thus
    
    U(a)=∫_-a^aφ(t) t≥2a/√(2π e).

    Therefore <ref> is lower bounded by
    
    1/√(d-1)∫_0^1Up_1/√(d-2)U(p_1)φ(p_1) p_1    ≥1/√(d-1)∫_0^1 2/√(2π e)·p_1/√(d-2)·2p_1/√(2π e)·1/√(2π e) p_1 
       ≥1/20√((d-1)(d-2))∫_0^1p_1^2 p_1 
        =1/60√((d-1)(d-2))
       ≥1/60d.



To prove <Ref>, we need the following technical lemma.

    Given z_1∼(0,1) and z_2∼(0,b^2) that are independent where
    b>1, we have
    
    |z_1|<|z_2|>1-1/b.



    First note that for z_3∼(0,1) which is independent of z_1,
    
    |z_1|<|z_2|=|z_1|<b|z_3|=1-|z_3|<1/b|z_1|.

    Still let φ denote the density of (0,1), and let U(c) denote
    the probability that z_3∈[-c,c].
    We have
    
    |z_3|<1/b|z_1|    =∫∫|z_3|<1/b|z_1|φ(z_3)φ(z_1) z_3 z_1 
        =∫ U1/b|z_1|φ(z_1) z_1 
       ≤2/√(2π)b∫|z_1|φ(z_1) z_1= 2/π b<1/b,

    where we use the facts that U(c)≤2c/√(2π) and
    [|z_1|]=√(2/π).


We now give the proof of <Ref> using <Ref>.

    By symmetry, we only need to consider the following training set:
    
    x_1=(1,0,1,…,1),       y_1=1, 
    
            x_2=(0,1,1,…,1),       y_2=-1, 
    
            x_3=(-1,0,1,…,1),       y_3=1, 
    
            x_4=(0,-1,1,…,1),       y_4=-1.

    The 1/√(d-1) factor is omitted also because we only discuss the 0/1
    loss.

    For any s, let A_s denote the event that
    
    w_sx_1>0=w_sx_2>0=w_sx_3>0=w_sx_4>0.

    We will show that if m≤√(d-2)/4, then A_s is true for all
    1≤ s≤ m with probability 1/2, and <Ref> follows from
    the fact that the XOR data is not linearly separable.

    For any s and i,
    
    w_sx_i=(w_s)_1(x_i)_1+(w_s)_2(x_i)_2+∑_j=3^d(w_s)_j.

    Since (x_i)_1,(x_i)_2 is (1,0) or (0,1) or (-1,0) or (0,-1),
    event A_s will happen as long as
    
    (w_s)_1<∑_j=3^d(w_s)_j,  and  (w_s)_2<∑_s=3^d(w_s)_j.

    Note that (w_s)_1,(w_s)_2∼(0,1) while
    ∑_j=3^d(w_s)_j∼(0,d-2).
    As a result, due to <Ref>,
    
    (w_s)_1<∑_j=3^d(w_s)_j=(w_s)_2<∑_s=3^d(w_s)_j>1-1/√(d-2).

    Using a union bound, (A_s)>1-2/√(d-2).
    If m≤√(d-2)/4, then by a union bound again,
    
    ⋃_1≤ s≤ mA_s>1-2/√(d-2)m≥1-2/√(d-2)√(d-2)/4=1/2.



