# A Mathematical Model for Curriculum Learning

Elisabetta Cornacchia Institute of Mathematics, École Polytechnique Fédérale
de Lausanne. Email<EMAIL_ADDRESS>Elchanan Mossel Department
of Mathematics and IDSS, Massachusetts Institute of Technology. Email:
<EMAIL_ADDRESS>
###### Abstract

Curriculum learning (CL) \- training using samples that are generated and
presented in a meaningful order - was introduced in the machine learning
context around a decade ago. While CL has been extensively used and analysed
empirically, there has been very little mathematical justification for its
advantages. We introduce a CL model for learning the class of $k$-parities on
$d$ bits of a binary string with a neural network trained by stochastic
gradient descent (SGD). We show that a wise choice of training examples,
involving two or more product distributions, allows to reduce significantly
the computational cost of learning this class of functions, compared to
learning under the uniform distribution. We conduct experiments to support our
analysis. Furthermore, we show that for another class of functions - namely
the ‘Hamming mixtures’ - CL strategies involving a bounded number of product
distributions are not beneficial, while we conjecture that CL with unbounded
many curriculum steps can learn this class efficiently.

##  1 Introduction

Several experimental studies have shown that humans and animals learn
considerably better if the learning materials are presented in a curated,
rather than random, order [EA84, RK90, AKB+97, SGG14]. This is broadly
reflected in the educational system of our society, where learning is guided
by an highly organized curriculum. This may involve several learning steps:
with easy concepts introduced at first and harder concepts built from previous
stages.

Inspired by this, [BLCW09] formalized a curriculum learning (CL) paradigm in
the context of machine learning and showed that for various learning tasks it
provided improvements in both the training speed and the performance obtained
at convergence. This seminal paper inspired many subsequent works, that
studied curriculum learning strategies in various application domains, e.g.
computer vision [SGNK17, DGZ17], computational biology [XHZ+21], auto-ML
[GBM+17], natural language modelling [SLJ13, ZS14, SLJ15, Cam21]. However,
from this extensive experimental literature, an unclear picture on the
usefulness of CL in machine learning has emerged. Indeed, in many machine
learning settings CL seems to provide only a modest improvement in the
learning performance. For this reason, CL sees limited popularity among
practitioners, with the exception of large language models where curricula are
standard practice [BMR+20].

While extensive empirical analysis of CL strategies have been carried out,
there is a lack of theoretical analysis. In this paper, we make progress in
this direction by defining a mathematical model for curriculum learning, by
proving rigorously its advantages and by providing further support by
experimentation. Our work is motivated by the following question:

> Can we define a curriculum learning strategy that provably allows to learn
> tasks that are hard to learn in the classic setting with no-curriculum?

A stylized family of functions that is known to pose computational barriers is
the class of $k$-parities over $d$ bits of a binary string. In this work we
focus on this class. To define this class: for each subset $S$ of coordinates,
the parity over $S$ is defined as $+1$ if the number of negative bits in $S$
is even, and $-1$ otherwise, i.e. $\chi_{S}(x):=\prod_{i\in S}x_{i}$,
$x_{i}\in\\{\pm 1\\}$. The class of $k$-parities contains all $\chi_{S}$ such
that $|S|=k$ and it has cardinality ${d\choose k}$. Learning $k$-parities
requires learning the support of $\chi_{S}$ by observing samples
$(x,\chi_{S}(x))$, $x\in\\{\pm 1\\}^{d}$, with the knowledge of the
cardinality of $S$ being $k$. This requires finding the right target function
among the ${d\choose k}$ functions belonging to the class.

The class of parities is interesting, as it is easy to learn via specialized
methods (e.g. Gaussian elimination over the field of two elements), but it is
considered hard to learn under the uniform distribution. The latter can be
explained as follows. Assume we sample our binary string uniformly at random,
i.e. for each $i\in\\{1,...,d\\}$,
$x_{i}\sim\operatorname{Rad}(1/2)$111$z\sim\operatorname{Rad}(p)$ if
$\mathbb{P}(z=1)=1-\mathbb{P}(z=-1)=p$.. Then, the covariance between two
parities $\chi_{S},\chi_{S^{\prime}}$ is given by:

$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\chi_{S}(x)\chi_{S^{\prime}}(x)\right]=\begin{cases}&1\quad\text{ if
}S=S^{\prime},\\\ &0\quad\text{ if }S\neq S^{\prime},\end{cases}$

where $x\sim\operatorname{Rad}(1/2)^{\otimes d}$ denotes the product measure
such that $x_{i}\overset{iid}{\sim}\operatorname{Rad}(1/2)$,
$i\in\\{1,...,d\\}$. More abstractly, a parity function of $k$ bits is
uncorrelated with any function of $k-1$ or less bits. This property makes
parities hard to learn for any progressive algorithm, such as gradient
descent. Indeed, when trying to learn the set of relevant features, a learner
cannot know how close its progressive guesses are to the true set. In other
words, all wrong guesses are indistinguishable, which suggests that the
learner might have to perform exhaustive search among all the ${d\choose k}$
sets.

The hardness of learning unbiased parities - and more in general any classes
of functions with low cross-correlations - with gradient descent has been
analysed e.g. in [AS20], where the authors show a lower bound on the
computational complexity of learning low cross-correlated classes with
gradient-based algorithms with bounded gradient precision. For $k$-parities,
this gives a computational lower bound of $d^{\Omega(k)}$ for any architecture
and initialization.

Of course, if we look at different product distributions, then learning
parities is actually easy. Suppose the inputs are generated as
$x\sim\operatorname{Rad}(p)^{\otimes d}$, for some $p\in(0,1)$. Then the
covariance between $\chi_{S}$ and $\chi_{S^{\prime}}$ is:

$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(p)^{\otimes d}}$
$\displaystyle\Big{[}(\chi_{S}(x)-\mathbb{E}[\chi_{S}(x)])\cdot(\chi_{S^{\prime}}(x)-\mathbb{E}[\chi_{S^{\prime}}(x)])\Big{]}$
$\displaystyle=\mu_{p}^{2k-|S\cap S^{\prime}|}-\mu_{p}^{2k},$

where we denoted by
$\mu_{p}:=\mathbb{E}_{z\sim\operatorname{Rad}(p)}[z]=2p-1$. This implies that
if for instance $|p-0.5|>0.1$, just computing correlations with each bit, will
recover the parity with complexity linear in $d$ and exponential in $k$. If we
choose $p=1-1/k$, say, we can get a complexity that is linear in $d$ and
polynomial in $k$. Moreover, the statements above hold even for parities with
random noise.

This may lead one to believe that learning biased parities is easy for
gradient descent based methods for deep nets. However, as our experiments show
(Figure 1), while gradient descent for a $p$ far from a half converges quickly
to error very close to $0$, the learned function actually has non-negligible
error when computed with respect to the uniform measure. This is intuitively
related to the fact that, by concentration of measure, there are essentially
no examples with Hamming weight222The Hamming weight of $x\in\\{\pm 1\\}^{d}$
is: $H(x)=\sum_{i=1}^{d}\mathds{1}(x_{i}=1)$. close to $d/2$ in the training
set sampled under $\operatorname{Rad}(p)^{\otimes d}$, and therefore it is not
reasonable to expect for a general algorithm like gradient descent (that does
not know that the target function is a parity) to learn the value of the
function on such inputs.

We thus propose a more subtle question: Is it possible to generate examples
from different product distributions and present them in a specific order, in
such a way that the error with respect to the unbiased measure becomes
negligible?

As we mentioned, training on examples sampled from a biased measure is not
sufficient to learn the parity under the unbiased measure. However, it does
identify the support of the parity, without performing exhaustive search and
reducing significantly the computational cost.

Our curriculum learning strategy is the following: We initially train on
inputs sampled from $\operatorname{Rad}(p)^{\otimes d}$ with $p$ close to $1$,
then we move (either gradually or by sharp steps) towards the unbiased
distribution $\operatorname{Rad}(1/2)^{\otimes d}$. We obtain that this
strategy reduces significantly the computational cost. Indeed, we show that we
can learn the $k$-parity problem with a computational cost of $d^{O(1)}$ with
SGD on the hinge loss or on the covariance loss (see Def. 5). Our results are
valid for any (even) $k$ and $d$, thus for large $k$ and $d$ our bound is far
below the $d^{\Omega(k)}$ computational limit for bounded gradient precision
models. Our experiments show the advantages of our CL strategy for learning
$k$-parities on a set of fully connected architectures.

As we mentioned earlier, the failure of learning parities under the uniform
distribution from samples coming from a different product measure is due to
concentration of Hamming weight: unless we have exponentially in $k$ many
samples, we do not expect to see any example with Hamming weight close to
$k/2$ among the relevant bits. This leads us to consider a family of functions
that we call Hamming mixtures. Given an input $x$, the output of a Hamming
mixture is a parity of a subset $S$ of the coordinates, where the subset $S$
depends on the Hamming weight of $x$ (see Def. 3). Our intuition is based on
the fact that given a polynomial number of samples from, say, the $p=1/4$
biased measure, it is impossible to distinguish between a certain parity
$\chi_{S}$ and a function that is $\chi_{S}$, for $x$’s whose Hamming weight
is at most $3/8d$, and a different function $\chi_{T}$, for $x$’s whose
Hamming weight is more than $3/8d$, for some $T$ that is disjoint from $S$. In
other words, a general algorithm does not know whether there is consistency
between $x$’s with different Hamming weight. We show a lower bound for
learning Hamming mixtures with curriculum strategies that do not allow to get
enough samples with relevant Hamming weight.

Of course, curriculum learning strategies with enough learning steps allow to
obtain samples from several product distributions, and thus with all relevant
Hamming weights. Therefore, we expect that CL strategies with unboundedly many
learning steps will be able to learn the Hamming mixtures.

While our results are restricted to a limited and stylized setting, we believe
they may open new research directions. Indeed, we believe that our general
idea of introducing correlation among subsets of the input coordinates to
facilitate learning, may apply to more general settings. We discuss some of
these future directions in the conclusion section of the paper.

#### Contributions.

Our contributions are the following.

  1. 1.

We propose and formalize a mathematical model for curriculum learning;

  2. 2.

We prove that our curriculum strategy allows to learn $k$-parities with a
computational cost of $d^{O(1)}$, with a $2$-layers fully connected network
trained by SGD with the hinge loss or with the covariance loss;

  3. 3.

We empirically verify the effectiveness of our curriculum strategy for a set
of fully connected architectures and parameters;

  4. 4.

We propose a class of functions - the Hamming mixtures \- that is provably not
learnable by some curriculum strategies with finitely many learning steps. We
conjecture that a continuous curriculum strategy (see Def. 4) may allow to
significantly improve the performance for learning such class of functions.

###  1.1 Related work

#### Learning parities on uniform inputs.

Learning $k$-parities over $d$ bits requires determining the set of relevant
features among ${d\choose k}$ possible sets. The statistical complexity of
this problem is thus $\theta(k\log(d))$. The computational complexity is
harder to determine. $k$-parities can be solved in $d^{O(1)}$ time by
specialized algorithms (e.g. Gaussian elimination) that have access to at
least $d$ samples. In the statistical query (SQ) framework [Kea98] \- i.e.
when the learner has access only to noisy queries over the input distribution
- $k$-parities cannot be learned in less then $\Omega(d^{k})$ computations.
[AS20, SSSS17] showed that gradient-based methods suffer from the same SQ
computational lower bound if the gradient precision is not good enough. On the
other hand, [AS20] showed that one can construct a very specific network
architecture and initialization that can learn parities beyond this limit.
This architecture is however far from the architectures used in practice.
[BEG+22] showed that SGD can learn sparse $k$-parities with SGD with batch
size $d^{\theta(k)}$ on a small network. Moreover, they empirically provide
evidence of ‘hidden progress’ during training, ruling out the hypothesis of
SGD doing random search. [APVZ14] showed that parities are learnable by a
$d^{\theta(k)}$ network. The problem of learning noisy parities (even with
small noise) is conjectured to be intrinsically computationally hard, even
beyond SQ models [Ale03].

#### Learning parities on non-uniform inputs.

Several works showed that when the input distribution is not the
$\operatorname{Unif}\\{\pm 1\\}^{d}$, then neural networks trained by
gradient-based methods can efficiently learn parities. [MKAS21] showed that
biased parities are learnable by SGD on a differentiable model consisting of a
linear predictor and fixed module implementing the parity. [DM20] showed that
sparse parities are learnable on a two layers network if the input coordinates
outside the support of the parity are uniformly sampled and the coordinates
inside the support are correlated. To the best of our knowledge, none of these
works propose a curriculum learning model to learn parities under the uniform
distribution.

#### Curriculum learning.

Curriculum Learning (CL) in the context of machine learning has been
extensively analysed from the empirical point of view [BLCW09, WCZ21, SIRS22].
However, theoretical works on CL seem to be more scarce. In [SMS22] the
authors propose an analytical model for CL for functions depending on a sparse
set of relevant features. In their model, easy samples have low variance on
the irrelevant features, while hard samples have large variance on the
irrelevant features. In contrast, our model does not require knowledge of the
target task to select easy examples. In [WCA18, WA20] the authors analyse
curriculum learning strategies in convex models and show an improvement on the
speed of convergence of SGD. In contrast, our work covers an intrinsically
non-convex problem. Some works also analysed variants of CL: e.g. self-paced
CL (SPCL), i.e. curriculum is determined by both prior knowledge and the
training process [JMZ+15], implicit curriculum, i.e. neural networks tend to
consistently learn the samples in a certain order [TSC+18]. Another form of
guided learning appears in [ABAB+21, AAM22], where the authors analyse
staircase functions - sum of nested monomials of increasing degree - and show
that the hierarchical structure of such tasks guides SGD to learn high degree
monomials. Furthermore, [RIG22, KKN+19] show that SGD learns functions of
increasing complexity during training.

##  2 Definitions and main results

We define a curriculum strategy for learning a general Boolean target
function. We will subsequently restrict our attention to the problem of
learning parities or mixtures of parities. For brevity, we denote
$[d]=\\{1,...,d\\}$. Assume that the network is presented with samples
$(x,f(x))$, where $x\in\\{\pm 1\\}^{d}$ is a Boolean vector and $f:\\{\pm
1\\}^{d}\to\mathbb{R}$ is a target function that generates the labels. We
consider a neural network $\operatorname{NN}(x;\theta)$, whose parameters are
initialized at random from an initial distribution $P_{0}$, and trained by
stochastic gradient descent (SGD) algorithm, defined by:

$\displaystyle\theta^{(t+1)}=\theta^{(t)}-\gamma_{t}\frac{1}{B}\sum_{i=1}^{B}\nabla_{\theta^{(t)}}L(\theta^{(t)},f,x^{t}_{i}),$
(1)

for all $t\in\\{0,...,T-1\\}$, where $L$ is an almost surely differentiable
loss-function, $\gamma_{t}$ is the learning rate, $B$ is the batch size and
$T$ is the total number of training steps. For brevity, we write
$L(\theta^{(t)},f,x):=L(\operatorname{NN}(.;\theta^{(t)}),f,x)$. We assume
that for all $i\in[B]$, $x_{i}^{t}\overset{iid}{\sim}\mathcal{D}^{t}$, where
$\mathcal{D}^{t}$ is a step-dependent input distribution supported on $\\{\pm
1\\}^{d}$. We define our curriculum learning strategy as follows. Recall that
$z\sim\operatorname{Rad}(p)$ if $\mathbb{P}(z=1)=1-\mathbb{P}(z=-1)=p$.

######  Definition 1 (r-steps curriculum learning (r-CL)).

For a fixed $r\in\mathbb{N}$, let $T_{1},...T_{r}\in\mathbb{N}$ and
$p_{1},...,p_{r}\in[0,1]$. Denote by $\bar{p}:=(p_{1},...,p_{r})$ and
$\bar{T}:=(T_{1},...,T_{r-1})$. We say that a neural network
$\operatorname{NN}(x;\theta^{(t)})$ is trained by SGD with a
r-CL$(\bar{T},\bar{p})$ if $\theta^{(t)}$ follows the iterations in (1) with:

$\displaystyle\mathcal{D}^{t}=\operatorname{Rad}(p_{1}),\qquad 0<t\leq T_{1},$
$\displaystyle\mathcal{D}^{t}=\operatorname{Rad}(p_{2}),\qquad T_{1}<t\leq
T_{2},$ $\displaystyle\cdots$
$\displaystyle\mathcal{D}^{t}=\operatorname{Rad}(p_{r}),\qquad T_{r-1}<t\leq
T.$

We say that $r$ is the number of curriculum steps.

We assume $r$ to be independent on $T$, in order to distinguish the $r$-CL
from the continuous-CL (see Def. 4 below). We hypothesize that $r$-CL may help
to learn several Boolean functions, if one chooses appropriate $r$ and
$\bar{p}$. However, in this paper we focus on the problem of learning unbiased
$k$-parities. For such class, we obtained that choosing $r=2$, a wise
$p_{1}\in(0,1/2)$ and $p_{2}=1/2$ brings a remarkable gain in the
computational complexity, compared to the standard setting with no curriculum.
An interesting future direction would be studying the optimal $r$ and
$\bar{p}$. Before stating our Theorem, let us clarify the generalization error
that we are interested in. As mentioned before, we are interested in learning
the target over the uniform input distribution.

######  Definition 2 (Generalization error).

We say that SGD on a neural network $\operatorname{NN}(x;\theta)$ learns a
target function $f:\\{\pm 1\\}^{d}\to\mathbb{R}$ with
$r$-CL$(\bar{T},\bar{p})$ up to error $\epsilon$, if it outputs a network
$\operatorname{NN}(x;\theta^{(T)})$ such that:

$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[L(\theta^{(T)},f,x)\right]\leq\epsilon,$ (2)

where $L$ is any loss function such that $L(f,f,x)=0$.

We state here our main theoretical result informally. We refer to Section 3.1
for the formal statement with exact exponents and remarks.

######  Theorem 1 (Main positive result, informal).

There exists a 2-CL strategy such that a 2-layer fully connected network of
$d^{O(1)}$ size trained by SGD with batch size $d^{O(1)}$ can learn any
$k$-parities (for $k$ even) up to error $\epsilon$ in at most
$d^{O(1)}/\epsilon^{2}$ iterations.

Let us analyse the computational complexity of the above. At each step, the
number of computations performed by a 2-layer fully connected network is given
by:

$\displaystyle(dN+N)\cdot B,$ (3)

where $d$ is the input size, $N$ is the number of hidden neurons and $B$ is
the batch size. Multiplying by the total number of steps and substituting the
bounds from the Theorem we get that we can learn the $k$-parity problem with a
2-CL strategy in at most $d^{O(1)}$ total computations. Specifically, $O(1)$
denotes quantities that do not grow with $k$ or $d$, and the statement holds
also for large $k,d$. We prove the Theorem in two slightly different settings,
see Section 3.1.

One may ask whether the $r$-CL strategy is beneficial for learning general
target tasks (i.e. beyond parities). While we do not have a complete picture
to answer this question, we propose a class of functions for which some $r$-CL
strategies are not beneficial. We call those functions the Hamming mixtures,
and we define them as follows.

######  Definition 3 ((S,T,$\epsilon)$-Hamming mixture).

For $\epsilon\in[0,1]$, $S,T\in[d]$, we say that $g:\\{\pm
1\\}^{d}\to\mathbb{R}$ is a (S,T,$\epsilon)$-Hamming mixture if

$\displaystyle G_{S,T,\epsilon}(x):=\chi_{S}(x)\mathds{1}(H(x)\leq\epsilon
d)+\chi_{T}(x)\mathds{1}(H(x)>\epsilon d),$

where $H(x):=\sum_{i=1}^{d}1(x_{i}=1)$ is the Hamming weight of $x$,
$\chi_{S}(x):=\prod_{i\in S}x_{i}$ and $\chi_{T}(x):=\prod_{i\in T}x_{i}$ are
the parity functions over set $S$ and $T$ respectively.

We will consider $\epsilon\neq 1/2$. The intuition of why such functions are
hard for some $r$-CL strategies is the following. Assume we train on samples
$(x,G_{S,T.\epsilon}(x))$, with $S,T$ disjoint and $\epsilon\in(0,1/2)$.
Assume that we use a $2$-CL strategy and we initially train on samples
$x\sim\operatorname{Rad}(p)^{\otimes d}$ for some $p<\epsilon$. If the input
dimension $d$ is large, then the Hamming weight of $x$ is with high
probability concentrated around $pd$ (e.g. by Hoeffding’s inequality). Thus,
in the first part of training the network will see, with high probability,
only samples of the type $(x,\chi_{S}(x))$, and it will not see the second
addend of $G_{S,T,\epsilon}$. When we change our input distribution to
$\operatorname{Rad}(1/2)^{\otimes d}$, the network will suddenly observe
samples of the type $(x,\chi_{T}(x))$. Thus, the pre-training on $p$ will not
help determining the support of the new parity $\chi_{T}$ (in some sense the
network will “forget” the first part of training). This intuition holds for
all $r$-CL such that $p_{1},...,p_{r-1}<\epsilon$. We state our negative
result for Hamming mixtures here informally, and refer to Section 4 for a
formal statement and remarks.

######  Theorem 2 (Main negative result, informal).

For each $r$-CL strategy with $r$ bounded, there exists a Hamming mixture
$G_{S,T,\epsilon}$ that is not learnable by any fully connected neural network
of $\operatorname{poly}(d)$ size and permutation-invariant initialization
trained by the noisy gradient descent algorithm (see Def. 6) with
$\operatorname{poly}(d)$ gradient precision in $\operatorname{poly}(d)$ steps.

Inspired by the hardness of Hamming mixtures, we define another curriculum
learning strategy, where, instead of having finitely many discrete curriculum
steps, we gradually move the bias of the input distribution during training
from a starting point $p_{0}$ to a final point $p_{T}$. We call this strategy
a continuous-CL strategy.

######  Definition 4 (Continuous curriculum learning (C-CL)).

Let $p_{0},p_{T}\in[0,1]$. We say that a neural network
$\operatorname{NN}(x;\theta^{(t)})$ is trained by SGD with a
C-CL$(p_{0},p_{T},T)$ if $\theta^{(t)}$ follows the iterations in (1) with:

$\displaystyle\mathcal{D}^{t}=\operatorname{Rad}\left(p_{0}+t\cdot\frac{p_{1}-p_{0}}{T}\right),\qquad
t\in[T].$ (4)

We conjecture that a well chosen C-CL might be beneficial for learning any
Hamming mixture. A positive result for C-CL and comparison between $r$-CL and
C-CL are left for future work.

##  3 Learning parities

###  3.1 Theoretical results

Our goal is to show that the curriculum strategy that we propose allows to
learn $k$-parities with a computational complexity of $d^{O(1)}$. We prove two
different results. In the first one, we consider SGD on the hinge loss and
prove that a network with $\theta(d^{2})$ hidden units can learn the
$k$-parity problem in $d^{O(1)}$ computations, if trained with a well chosen
$2$-CL strategy. Let us state our first Theorem.

######  Theorem 3 (Hinge Loss).

Let $k,d$ be both even integers, such that $k\leq d/2$. Let
$\operatorname{NN}(x;\theta)=\sum_{i=1}^{N}a_{i}\sigma(w_{i}x+b_{i})$ be a
2-layers fully connected network with activation
$\sigma(y):=\operatorname{Ramp}(y)$ (as defined in (9)) and
$N=\tilde{\theta}(d^{2}\log(1/\delta))$333$\tilde{\theta}(d^{c})=\theta(d^{c}\cdot\operatorname{poly}(\log(d)))$,
for all $c\in\mathbb{R}$.. Consider training $\operatorname{NN}(x;\theta)$
with SGD on the hinge loss with batch size
$B=\tilde{\theta}(d^{10}/\epsilon^{2}\log(1/\delta))$. Then, there exists an
initialization, a learning rate schedule, and a 2-CL strategy such that after
$T=\tilde{\theta}(d^{6}/\epsilon^{2})$ iterations, with probability
$1-3\delta$, SGD outputs a network with generalization error at most
$\epsilon$.

For our second Theorem, we consider another loss function, that is convenient
for the analysis, namely the covariance loss, for which we give a definition
here.

######  Definition 5 (Covariance loss).

Let $f:\mathcal{X}\to\mathbb{R}$ be a target function and let
$\hat{f}:\mathcal{X}\to\mathbb{R}$ be an estimator. Let

$\displaystyle\mathrm{cov}$
$\displaystyle(f,\hat{f},x,P_{\mathcal{X}}):=\Big{(}f(x)-\mathbb{E}_{x^{\prime}\sim
P_{\mathcal{X}}}[f(x^{\prime})]\Big{)}\cdot\Big{(}\hat{f}(x)-\mathbb{E}_{x^{\prime}\sim
P_{\mathcal{X}}}[\hat{f}(x^{\prime})]\Big{)},$

where $P_{\mathcal{X}}$ is an input distribution supported in $\mathcal{X}$.
We define the covariance loss as

$\displaystyle L_{\mathrm{cov}}(f,\hat{f},x,P_{\mathcal{X}})$
$\displaystyle:=\max\\{0,1-\mathrm{cov}(f,\hat{f},x,P_{\mathcal{X}})\\}.$

We show that SGD on the covariance loss can learn the $k$-parity problem in
$d^{O(1)}$ computations using a network with only $O(k)$ hidden units. The
reduction of the size of the network, compared to the hinge loss case, allows
to get a tighter bound on the computational cost (see Remark 1).

######  Theorem 4 (Covariance Loss).

Let $k,d$ be integers such that $k\leq d$ and $k$ even. Let
$\operatorname{NN}(x;\theta)=\sum_{i=1}^{N}a_{i}\sigma(w_{i}x+b_{i})$ be a
2-layers fully connected network with activation
$\sigma(y):=\operatorname{ReLU}(y)$ and $N=\tilde{\theta}(k\log(1/\delta))$.
Consider training $\operatorname{NN}(x;\theta)$ with SGD on the covariance
loss with batch size
$B=\tilde{\theta}(d^{2}k^{3}/\epsilon^{2}\log(1/\delta))$. Then, there exists
an initialization, a learning rate schedule, and a 2-CL strategy such that
after $T=\tilde{\theta}(k^{4}/\epsilon^{2})$ iterations, with probability
$1-3\delta$, SGD outputs a network with generalization error at most
$\epsilon$.

The proofs of Theorem 3 and Theorem 4 follow a similar outline. Firstly, we
prove that training the first layer of the network on one batch of size
$d^{O(1)}$, sampled from a biased input distribution (with appropriate bias),
allows to recover the support of the parity. We then show that training the
second layer on the uniform distribution allows to achieve the desired
generalization error under the uniform distribution. We refer to Appendices A
and B for restatements of the Theorems and their full proofs.

######  Remark 1.

Let us look at the computational complexity given by the two Theorems. Theorem
3 tells that we can learn $k$-parities in $dNB+(T-1)N=\tilde{\theta}(d^{19})$
computations. We remark that our result holds also for large $k$ (we however
need to assume $k,d$ even and $k\leq d/2$, for technical reasons). On the
other hand, Theorem 4 tells that we can learn $k$-parities in
$\tilde{\theta}(d^{3}k^{8})$, which is lower than the bound given by Theorem
3. Furthermore, the proof holds for all $k\leq d$. The price for getting this
tighter bound is the use of a loss that (to the best of our knowledge) is not
common in the machine learning literature, and that is particularly convenient
for our analysis.

######  Remark 2.

We remark that our proofs extend to the gradient descent model with bounded
gradient precision, used in [AS20], with gradient precision bounded by
$d^{O(1)}$ (see Remark 7 in Appendix A). Thus, for large $k,d$, our result
provides a separation to the $d^{\Omega(k)}$ computational lower bound for
learning $k$-parities under the uniform distribution with no curriculum,
obtained in [AS20].

######  Remark 3.

Let us comment on the $p_{1}$ (i.e. the bias of the initial distribution) that
we used. In both Theorems we take $p_{1}$ close to $1$. In Theorem 3 we take
$p_{1}\approx 1-\theta(1/d)$, and the proof is constructed specifically for
this value of $p_{1}$. In Theorem 4, the proof holds for any $p_{1}\in(1/2,1)$
and the asymptotic complexity in $d$ does not depend on the specific choice of
$p_{1}$. However, to get $\operatorname{poly}(k)$ complexity we need to take
$p_{1}=1-\theta(1/k)$, while we get $\exp(k)$ complexity for all
$p_{1}=\theta_{d,k}(1)$.

Our theoretical analysis captures a fairly restricted setting: in our proofs
we use initializations and learning schedules that are convenient for the
analysis. We conduct experiments to verify the usefulness of our CL strategy
in more standard settings of fully connected architectures.

###  3.2 Empirical results

Figure 1: Learning $20$-parities with $2$-steps curriculum, with initial bias
$p_{1}=39/40$ (top-left), $p_{1}=19/20$ (top-center), $p_{1}=1/20$ (top-
right), with continuous curriculum (bottom-left) and with no curriculum
(bottom-right). In all plots, we use a 2-layers ReLU MLP with batch size 1024,
input dimension 100, and 100 hidden units.

Figure 2: Convergence time for different values of $d$, $k$. Left: we take
$p_{1}=1/16$ and a 2-layers $\operatorname{ReLU}$ architecture with with
$N=2^{k}$ hidden units. Right: we take $p_{1}=1-\frac{1}{2k}$ and a 2-layers
$\operatorname{ReLU}$ architecture with $N=d$ hidden units.

In all our experiments we use fully connected $\operatorname{ReLU}$ networks
and we train them by SGD on the square loss.

In Figure 1, we compare different curriculum strategies for learning
$20$-parities over $100$ bits, with a fixed architecture, i.e. a $2$-layer
$\operatorname{ReLU}$ network with $100$ hidden units. We run a $2$-steps
curriculum strategy for $3$ values of $p_{1}$, namely
$p_{1}=39/40,19/20,1/20$. In all the $2$-CL experiments we train on the biased
distribution until convergence, and then we move to the uniform distribution.
We observe that training with an initial bias of $p_{1}=39/40$ allows to learn
the $20$-parity in $16,000$ epochs. One can see that during the first part of
training (on the biased distribution), the test error under the uniform
distribution stays at $1/2$ (orange line), and then drops quickly to zero when
we start training on the uniform distribution. This trend of hidden progress
followed by a sharp drop has been already observed in the context of learning
parities with SGD in the standard setting with no-curriculum [BEG+22]. Here,
the length of the ‘hidden progress’ phase is controlled by the length of the
first phase of training. Interestingly, when training with continuous
curriculum, we do not have such hidden progress and the test error under the
uniform distribution decreases slowly to zero. With no curriculum, the network
does not achieve non-trivial correlation with the target in $25,000$ epochs.
We refer to Appendix E for further experiments with smaller batch size and
$3$-layers networks.

In Figure 2 we study the convergence time of a $2$-CL strategy on a $2$-layers
$\operatorname{ReLU}$ network for different values of the input dimension
($d$) and size of the parity ($k$). We take two slightly different settings.
In the plot on the left, we take a fixed initial bias $p_{1}=1/16$ and
$N=2^{k}$ hidden units. On the right we take $p_{1}=1-\frac{1}{2k}$ initial
bias and an architecture with $N=d$ hidden units. The convergence time is
computed as $T_{1}+T_{2}$, where $T_{1}$ and $T_{2}$ are the number of steps
needed to achieve training error below $0.01$ in the first and second part of
training, respectively. We compute the convergence time for $k=5,6,7,8,9,10$
and $d=25,50,75,100$, and for each $k$ we plot the convergence time with
respect to $d$ in log-log scale. Each point is obtained by averaging over $10$
runs. We observe that for each $k$, the convergence time scales (roughly)
polynomially as $d^{c_{k}}$, with $c_{k}$ varying mildly with $k$.

Figure 3: Convergence time with respect to the initial bias $p_{1}$. We
compute the convergence time for learning a $10$-parity over $100$ bits with a
2-layer $\operatorname{ReLU}$ network. We omitted all points with convergence
time above $100,000$.

In Figure 3, we study the convergence time of a $2$-CL strategy for different
values of the initial bias $p_{1}$. We consider the problem of learning a
$10$-parity over $100$ bits with a $2$-layers $\operatorname{ReLU}$ network
with $N=100$ hidden units. As before, we computed the convergence time as
$T_{1}+T_{2}$, where $T_{1}$ and $T_{2}$ are the number of steps needed to
achieve training error below $0.01$ in the first and second part of training,
respectively. We ran experiments for
$p_{1}=0.001,0.05,0.1,0.15,...,0.95,0.999$. We omitted from the plot any point
for which the convergence time exceeded $100,000$ iterations: these correspond
to $p_{1}$ near $1/2$ and $p_{1}=0.001,0.999$. Each point is obtained by
averaging over $10$ runs. We observe that the convergence time is smaller for
$p_{1}$ close to $0$ or to $1$. Moreover, $T_{2}$ has modest variations across
different $p_{1}$’s.

##  4 Learning Hamming mixtures

In this section we consider the class of functions defined in Def. 3 and named
Hamming mixtures. We consider a specific descent algorithm, namely the noisy
GD algorithm with batches (used also in [AS20, AKM+21]). We give a formal
definition here of noisy GD with curriculum.

######  Definition 6 (Noisy GD with CL).

Consider a neural network $\operatorname{NN}(.;\theta)$, with initialization
of the weights $\theta^{(0)}$. Given an almost surely differentiable loss
function, the updates of the noisy GD algorithm with learning rate
$\gamma_{t}$ and gradient range $A$ are defined by

$\displaystyle\theta^{(t+1)}=\theta^{(t)}-\gamma_{t}\left(\mathbb{E}_{x^{t}}[\nabla_{\theta^{t}}L(\theta^{(t)},f,x^{t})]_{A}+Z^{t}\right),$
(5)

where for all $t\in\\{0,...,T-1\\}$, $Z^{t}$ are i.i.d.
$\mathcal{N}(0,\tau^{2})$, for some $\tau$, and they are independent from
other variables, $x^{t}\sim\mathcal{D}^{t}$, for some time-dependent input
distribution $\mathcal{D}^{t}$, $f$ is the target function, from which the
labels are generated, and by $[.]_{A}$ we mean that whenever the argument is
exceeding $A$ (resp. $-A$) it is rounded to $A$ (resp. $-A$). We call $A/\tau$
the gradient precision. In the noisy-GD algorithm with $r$-CL, we choose
$\mathcal{D}^{t}$ according to Def. 1.

Let us state our hardness result for learning Hamming mixtures with $r$-CL
strategies with $r$ bounded.

######  Theorem 5.

Assume the network observes samples generated by $G_{S,V,\epsilon}(x)$ (see
Def. 3), where $|S|=k_{S}$, $|V|=k_{V}$ such that $k_{S},k_{V}=o(\sqrt{d})$,
and $|S\cap V|=0$. Then, for any $r$-CL$(\bar{T},\bar{p})$ with $r$ bounded
and $p_{r}=1/2$, there exists an $\epsilon$ such that the noisy GD algorithm
with $r$-CL$(\bar{T},\bar{p})$ (as in (5)) on a fully connected neural network
with $|\theta|$ weights and permutation-invariant initialization, after $T$
training steps, outputs a network $\operatorname{NN}(x,\theta^{(T)})$ such
that

$\displaystyle\Big{|}$
$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[G_{S,V,\epsilon}(x)\cdot\operatorname{NN}(x;\theta^{(T)})\right]\Big{|}\leq\frac{2AT\sqrt{|\theta|}}{\tau}\left({d\choose
k_{V}}^{-1/2}+e^{-d\delta^{2}}\right)+\frac{2k_{S}k_{V}}{d}+O(d^{-2}),$

where $A,\tau$ are the gradient range and the noise level in the noisy-GD
algorithm and $\delta$ is a constant.

The proof uses an SQ-like lower bound argument for noisy GD, in a similar
flavour of [ACHM22, ABA22]. We refer to Appendix C for the full proof.

######  Remark 4.

In Theorem 5, the neural network can have any fully connected architecture and
any activation such that the gradients are well defined almost everywhere. The
initialization can be from any distribution that is invariant to permutations
of the input neurons.

For the purposes of
$\mathbb{E}\left[G_{S,V,\epsilon}(x)\cdot\operatorname{NN}(x;\theta^{(T)})\right]$,
it is assumed that the neural network outputs a guess in $\\{\pm 1\\}$. This
can be done with any form of thresholding, e.g. taking the sign of the value
of the output neuron.

######  Remark 5.

One can remove the $\frac{2k_{S}k_{V}}{d}$ term in the right hand side by
further assuming e.g. that set $S$ is supported on the first $d/2$ coordinates
and set $V$ on the last $d/2$ coordinates. This also allows to weaken the
assumption on the cardinality of $S$ and $V$. We formalize this in the
following Corollary.

######  Corollary 1.

Assume the network observes samples generated by $G_{S,V,\epsilon}(x)$, where
$S\subseteq\\{1,...,d/2\\}$, and $V\subseteq\\{d/2+1,...,d\\}$ (where we
assumed $d$ to be even for simplicity). Denote $k_{V}=|V|$. Then, for any
$r$-CL$(\bar{T},\bar{p})$ with $r$ bounded and $p_{r}=1/2$, there exists an
$\epsilon$ such that the noisy GD algorithm with $r$-CL$(\bar{T},\bar{p})$ (as
in (5)) on a fully connected neural network with $|\theta|$ weights and
permutation-invariant initialization, after $T$ training steps, outputs a
network $\operatorname{NN}(x,\theta^{(T)})$ such that

$\displaystyle\Big{|}$
$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[G_{S,V,\epsilon}(x)\cdot\operatorname{NN}(x;\theta^{(T)})\right]\Big{|}\leq\frac{2AT\sqrt{|\theta|}}{\tau}\left({d/2\choose
k_{V}}^{-1/2}+e^{-d\delta^{2}}\right),$

for some $\delta>0$.

The proof of Corollary 1 is deferred to Appendix D.

Theorem 5 and Corollary 1 state failure at the weakest form of learning, i.e.
achieving correlation better than guessing in the asymptotic of large $d$.
More specifically, it tells that if the network size, the number of training
steps and the gradient precision (i.e. $A/\tau$) are such that
$\frac{AT\sqrt{|\theta|}}{\tau}=o(d^{-k_{V}/2})$, then the network achieves
correlation with the target of $o_{d}(1)$ under the uniform distribution.
Corollary 2 follows immediately from the Theorem.

######  Corollary 2.

Under the assumptions of Theorem 5, if $k_{V}=\omega_{d}(1)$ (i.e. $k_{V}$
grows with $d$), $|\theta|,A/\tau,T$ are all polynomially bounded in $d$, then

$\displaystyle\Big{|}$
$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[G_{S,V,\epsilon}(x)\cdot\operatorname{NN}(x;\theta^{(T)})\right]\Big{|}=o_{d}(1),$
(6)

i.e. in $\operatorname{poly}(d)$ computations the network will fail at weak-
learning $G_{S,V,\epsilon}$.

We conjecture that if we take instead a C-CL strategy with an unbounded number
of curriculum steps, we can learn efficiently (i.e. in
$\operatorname{poly}(d)$ time) any $G_{S,V,\epsilon}$ (even with
$k_{V}=\omega_{d}(1)$ and for any $\epsilon$).

######  Conjecture 1.

There exists a C-CL strategy that allows to learn $G_{S,V,\epsilon}$ for all
$S,V,\epsilon$ in $\operatorname{poly}(d)$ training steps of a gradient-based
algorithm with $\operatorname{poly}(d)$ gradient precision on a network of
$\operatorname{poly}(d)$ size.

Furthermore, we believe the Conjecture to hold for any bounded mixture, i.e.
any function of the type:

$\displaystyle\sum_{m=1}^{M}\chi_{S_{m}}(x)\mathds{1}(\epsilon_{m-1}d\leq
H(x)<\epsilon_{m}d),$ (7)

with $S_{1},...,S_{M}$ being distinct sets of coordinates,
$0=\epsilon_{0}<\epsilon_{1}...<\epsilon_{M}\leq 1$, and $M$ bounded.

##  5 Conclusion and future work

In this work, we mainly focused on learning parities and Hamming mixtures with
$r$-CL strategies with bounded $r$. Some natural questions arise, for
instance: does the depth of the network help? What it the optimal number of
curriculum steps for learning parities? We leave to future work the analysis
of C-CL with unboundedly many curriculum steps and the comparison between
$r$-CL and C-CL. In the previous Section, we also raised a Conjecture
concerning the specific case of Hamming mixtures.

Furthermore, we believe that our results can be extended to more general
families of functions. First, consider the set of $k$-Juntas, i.e., the set of
functions that depend on $k$ out of $d$ coordinates. This set of functions
contains the set of $k$-parities so it is at least as hard to learn. Moreover,
as in the case of parities, Juntas are correlated with each of their inputs
for generic $p$, see e.g. [MOS04]. So it is natural to expect that curriculum
learning can learn such functions in time $d^{O(1)}2^{O(k)}$ (the second term
is needed since there is a doubly exponential number of Juntas on $k$ bits).
We further believe that our general idea of introducing correlation among
subsets of the input coordinates to facilitate learning may apply to more
general non-Boolean settings.

In this work we propose to learn parities using a mixture of product
distributions, but there are other ways to correlate samples that may be of
interest. For example, some works in PAC learning showed that, even for the
uniform measure, samples that are generated by a random walk often lead to
better learning algorithms [BMOS05, AM08]. Do such random walk based
algorithms provide better convergence for gradient based methods?

## Acknowledgement

This work was supported in part by the Simons-NSF Collaboration on the
Theoretical Foundations of Deep Learning (deepfoundations.ai). It started
while E.C. was visiting the MIT Institute for Data, Systems, and Society
(IDSS) under the support of the collaboration grant. E.M is also partially
supported Vannevar Bush Faculty Fellowship award ONR-N00014-20-1-2826 and by a
Simons Investigator Award in Mathematics (622132).

## References

  * [AAM22] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz.  The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks.  In Conference on Learning Theory, pages 4782–4887. PMLR, 2022.
  * [ABA22] Emmanuel Abbe and Enric Boix-Adsera.  On the non-universality of deep learning: quantifying the cost of symmetry.  arXiv preprint arXiv:2208.03113, 2022.
  * [ABAB+21] Emmanuel Abbe, Enric Boix Adsera, Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj.  The staircase property: How hierarchical structure can guide deep learning.  In Advances in Neural Information Processing Systems, volume 34, 2021.
  * [ACHM22] Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, and Christopher Marquis.  An initial alignment between neural network and target is needed for gradient descent to learn.  In International Conference on Machine Learning, pages 33–52. PMLR, 2022.
  * [AKB+97] Judith Avrahami, Yaakov Kareev, Yonatan Bogot, Ruth Caspi, Salomka Dunaevsky, and Sharon Lerner.  Teaching by examples: Implications for the process of category acquisition.  The Quarterly Journal of Experimental Psychology Section A, 50(3):586–606, 1997.
  * [AKM+21] Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro.  On the power of differentiable learning versus PAC and SQ learning.  In Advances in Neural Information Processing Systems, volume 34, 2021.
  * [Ale03] Michael Alekhnovich.  More on average case vs approximation complexity.  In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 298–307. IEEE, 2003.
  * [AM08] Jan Arpe and Elchanan Mossel.  Agnostically learning juntas from random walks.  arXiv preprint arXiv:0806.4210, 2008.
  * [APVZ14] Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang.  Learning polynomials with neural networks.  In International conference on machine learning, pages 1908–1916. PMLR, 2014.
  * [AS20] Emmanuel Abbe and Colin Sandon.  On the universality of deep learning.  In Advances in Neural Information Processing Systems, volume 33, pages 20061–20072, 2020.
  * [BEG+22] Boaz Barak, Benjamin L Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang.  Hidden progress in deep learning: Sgd learns parities near the computational limit.  arXiv preprint arXiv:2207.08799, 2022.
  * [BLCW09] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.  Curriculum learning.  In Proceedings of the 26th annual international conference on machine learning, pages 41–48, 2009.
  * [BMOS05] Nader H Bshouty, Elchanan Mossel, Ryan O’Donnell, and Rocco A Servedio.  Learning dnf from random walks.  Journal of Computer and System Sciences, 71(3):250–265, 2005.
  * [BMR+20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [Cam21] Daniel Campos.  Curriculum learning for language modeling.  arXiv preprint arXiv:2108.02170, 2021.
  * [DGZ17] Qi Dong, Shaogang Gong, and Xiatian Zhu.  Multi-task curriculum transfer deep learning of clothing attributes.  In 2017 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 520–529. IEEE, 2017.
  * [DM20] Amit Daniely and Eran Malach.  Learning parities with neural networks.  Advances in Neural Information Processing Systems, 33:20356–20365, 2020.
  * [EA84] Renee Elio and John R Anderson.  The effects of information order and learning mode on schema abstraction.  Memory & cognition, 12(1):20–30, 1984.
  * [GBM+17] Alex Graves, Marc G Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu.  Automated curriculum learning for neural networks.  In international conference on machine learning, pages 1311–1320. PMLR, 2017.
  * [JMZ+15] Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G Hauptmann.  Self-paced curriculum learning.  In Twenty-ninth AAAI conference on artificial intelligence, 2015\.
  * [Kea98] Michael Kearns.  Efficient noise-tolerant learning from statistical queries.  Journal of the ACM, 45(6):983–1006, 1998.
  * [KKN+19] Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang.  Sgd on neural networks learns functions of increasing complexity.  Advances in neural information processing systems, 32, 2019.
  * [MKAS21] Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro.  Quantifying the benefit of using differentiable learning over tangent kernels.  In International Conference on Machine Learning, pages 7379–7389. PMLR, 2021.
  * [MOS04] Elchanan Mossel, Ryan O’Donnell, and Rocco A Servedio.  Learning functions of k relevant variables.  Journal of Computer and System Sciences, 69(3):421–434, 2004.
  * [MSS20] Eran Malach and Shai Shalev-Shwartz.  Computational separation between convolutional and fully-connected networks.  arXiv preprint arXiv:2010.01369, 2020.
  * [RIG22] Maria Refinetti, Alessandro Ingrosso, and Sebastian Goldt.  Neural networks trained with sgd learn distributions of increasing complexity.  arXiv preprint arXiv:2211.11567, 2022.
  * [RK90] Brian H Ross and Patrick T Kennedy.  Generalizing from the use of earlier examples in problem solving.  Journal of Experimental Psychology: Learning, Memory, and Cognition, 16(1):42, 1990.
  * [SGG14] Patrick Shafto, Noah D Goodman, and Thomas L Griffiths.  A rational account of pedagogical reasoning: Teaching by, and learning from, examples.  Cognitive psychology, 71:55–89, 2014.
  * [SGNK17] Nikolaos Sarafianos, Theodore Giannakopoulos, Christophoros Nikou, and Ioannis A Kakadiaris.  Curriculum learning for multi-task classification of visual attributes.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 2608–2615, 2017.
  * [SIRS22] Petru Soviany, Radu Tudor Ionescu, Paolo Rota, and Nicu Sebe.  Curriculum learning: A survey.  International Journal of Computer Vision, pages 1–40, 2022.
  * [SLJ13] Yangyang Shi, Martha Larson, and Catholijn M Jonker.  K-component recurrent neural network language models using curriculum learning.  In 2013 IEEE Workshop on Automatic Speech Recognition and Understanding, pages 1–6. IEEE, 2013.
  * [SLJ15] Yangyang Shi, Martha Larson, and Catholijn M Jonker.  Recurrent neural network language model adaptation with curriculum learning.  Computer Speech & Language, 33(1):136–154, 2015.
  * [SMS22] Luca Saglietti, Stefano Sarao Mannelli, and Andrew Saxe.  An analytical theory of curriculum learning in teacher–student networks.  Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114014, 2022.
  * [SS+12] Shai Shalev-Shwartz et al.  Online learning and online convex optimization.  Foundations and Trends® in Machine Learning, 4(2):107–194, 2012.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding machine learning: From theory to algorithms.  Cambridge university press, 2014.
  * [SSSS17] Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah.  Failures of gradient-based deep learning.  In International Conference on Machine Learning, pages 3067–3075. PMLR, 2017.
  * [TSC+18] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon.  An empirical study of example forgetting during deep neural network learning.  arXiv preprint arXiv:1812.05159, 2018.
  * [WA20] Daphna Weinshall and Dan Amir.  Theory of curriculum learning, with convex loss functions.  Journal of Machine Learning Research, 21(222):1–19, 2020.
  * [WCA18] Daphna Weinshall, Gad Cohen, and Dan Amir.  Curriculum learning by transfer learning: Theory and experiments with deep networks.  In International Conference on Machine Learning, pages 5238–5246. PMLR, 2018.
  * [WCZ21] Xin Wang, Yudong Chen, and Wenwu Zhu.  A survey on curriculum learning.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021\.
  * [XHZ+21] Yuanpeng Xiong, Xuan He, Dan Zhao, Tingzhong Tian, Lixiang Hong, Tao Jiang, and Jianyang Zeng.  Modeling multi-species rna modification through multi-task curriculum learning.  Nucleic acids research, 49(7):3719–3734, 2021.
  * [ZS14] Wojciech Zaremba and Ilya Sutskever.  Learning to execute.  arXiv preprint arXiv:1410.4615, 2014.

##  Appendix A Proof of Theorem 3

######  Theorem 6 (Theorem 3, restatement).

Let $k,d$ be both even integers, such that $k\leq d/2$. Let
$\operatorname{NN}(x;\theta)=\sum_{i=1}^{N}a_{i}\sigma(w_{i}x+b_{i})$ be a
2-layers fully connected network with activation
$\sigma(y):=\operatorname{Ramp}(y)$ (as defined in (9)) and
$N\geq(d+1)(d-k+1)\log((d+1)(d-k+1)/\delta)$. Consider training
$\operatorname{NN}(x;\theta)$ with SGD on the hinge loss with batch size
$B\geq(8\zeta^{2}N^{2})^{-1}\log(\frac{Nd+N}{\delta})$, with
$\zeta\leq\frac{\epsilon\mu^{k}}{24(d+1)^{2}(d-k+1)^{2}N}$ and
$\mu=\sqrt{1-\frac{1}{2(d-k)}}$. Then, there exists an initialization, a
learning rate schedule, and a 2-CL strategy such that after
$T\geq\frac{64}{\epsilon^{2}}(d-k+1)^{3}(d+1)N$ iterations, with probability
$1-3\delta$ SGD outputs a network with generalization error at most
$\epsilon$.

###  A.1 Proof setup

We consider a 2-layers neural network, defined as:

$\displaystyle\operatorname{NN}(x;\theta)=\sum_{i=1}^{N}a_{i}\sigma(w_{i}x+b_{i}),$
(8)

where $N$ is the number of hidden units, $\theta=(a,b,w)$ and
$\sigma:=\operatorname{Ramp}$ denotes the activation defined as:

$\displaystyle\operatorname{Ramp}(x)=\begin{cases}0\quad x\leq 0,\\\ x\quad
0<x\leq 1,\\\ 1\quad x>1\end{cases}\,.$ (9)

Without loss of generality, we assume that the labels are generated by
$\chi_{[k]}(x):=\prod_{i=1}^{k}x_{i}$. Indeed, SGD on fully connected networks
with permutation-invariant initialization is invariant to permutation of the
input neurons, thus our result will hold for all $\chi_{S}(x)$ such that
$|S|=k$. Our proof scheme is the following:

  1. 1.

We train only the first layer of the network for one step on data
$(x_{i},\chi_{[k]}(x_{i}))_{i\in[B]}$ with
$x_{i}\sim\operatorname{Rad}(p)^{\otimes d}$ for $i\in[B]$, with
$p=\frac{1}{2}\sqrt{1-\frac{1}{2(d-k)}}+\frac{1}{2}$;

  2. 2.

We show that after one step of training on such biased distribution, the
target parity belongs to the linear span of the hidden units of the network;

  3. 3.

We subsequently train only the second layer of the network on
$(x_{i},\chi_{[k]}(x_{i}))_{i\in[B]}$ with
$x_{i}\sim\operatorname{Rad}(1/2)^{\otimes d}$ for $i\in[B]$, until
convergence;

  4. 4.

We use established results on convergence of SGD on convex losses to conclude.

We train our network with SGD on the hinge loss. Specifically, we apply the
following updates, for all $t\in\\{0,1,...,T-1\\}$:

$\displaystyle w_{i,j}^{(t+1)}$
$\displaystyle=w_{i,j}^{(t)}-\gamma_{t}\frac{1}{B}\sum_{s=1}^{B}\nabla_{w_{i,j}^{(t)}}L(\theta^{(t)},\chi_{[k]},x_{s}^{t}),$
$\displaystyle a_{i}^{(t+1)}$
$\displaystyle=a_{i}^{(t)}-\xi_{t}\frac{1}{B}\sum_{s=1}^{B}\nabla_{a_{i}^{(t)}}L(\theta^{(t)},\chi_{[k]},x_{s}^{t})+c_{t},$
(10) $\displaystyle b_{i}^{(t+1)}$
$\displaystyle=\lambda_{t}\left(b_{i}^{(t)}+\psi_{t}\frac{1}{B}\sum_{s=1}^{B}\nabla_{b_{i}^{(t)}}L(\theta^{(t)},\chi_{[k]},x_{s}^{t})\right)+d_{t},$

where
$L(\theta^{t},\chi_{[k]},x)=\max\\{0,1-\chi_{[k]}(x)\operatorname{NN}(x;\theta^{t})\\}$.
Following the 2-steps curriculum strategy introduced above, we set

$\displaystyle
x_{s}^{0}\overset{iid}{\sim}\operatorname{Rad}\left(p\right)^{\otimes
d}\qquad$ $\displaystyle\forall s\in[B],\qquad$ (11) $\displaystyle
x_{s}^{t}\overset{iid}{\sim}\operatorname{Rad}\left(1/2\right)^{\otimes
d}\quad\qquad$ $\displaystyle\forall t\geq 1,s\in[B],\qquad$ (12)

where $p=\frac{1}{2}\sqrt{1-\frac{1}{2(d-k)}}+\frac{1}{2}$. For brevity, we
denote $\mu:=2p-1=\sqrt{1-\frac{1}{2(d-k)}}$. We set the parameters of SGD to:

$\displaystyle\gamma_{0}=\mu^{-(k-1)}2N,$
$\displaystyle\gamma_{t}=0\qquad\forall t\geq 1,\qquad$ (13)
$\displaystyle\xi_{0}=0,$
$\displaystyle\xi_{t}=\frac{\epsilon}{2N}\qquad\forall t\geq 1,\qquad$ (14)
$\displaystyle\psi_{0}=\frac{N}{\mu^{k}},$
$\displaystyle\psi_{t}=0\qquad\forall t\geq 1,\qquad$ (15) $\displaystyle
c_{0}=-\frac{1}{2N},$ $\displaystyle c_{t}=0\qquad\forall t\geq 1,\qquad$ (16)
$\displaystyle\lambda_{0}=(d+1),$ $\displaystyle\lambda_{t}=1\qquad\forall
t\geq 1,\qquad$ (17) $\displaystyle d_{0}=0,$ $\displaystyle
d_{t}=0\qquad\forall t\geq 1,\qquad$ (18)

and we consider the following initialization scheme:

$\displaystyle w_{i,j}^{(0)}$ $\displaystyle=0\qquad\forall i\in[N],j\in[d];$
$\displaystyle a_{i}^{(0)}$ $\displaystyle=\frac{1}{2N}\qquad\forall i\in[N];$
(19) $\displaystyle b_{i}^{(0)}$
$\displaystyle\sim\operatorname{Unif}\Big{\\{}\frac{b_{lm}}{d+1}+\frac{1}{2}:l\in\\{0,...,d\\},m\in\\{-1,...,d-k\\}\Big{\\}},$

where we define

$\displaystyle b_{lm}:=-d+2l-\frac{1}{2}+\frac{m+1}{d-k}.$ (20)

Note that such initialization is invariant to permutations of the input
neurons. We choose such initialization because it is convenient for our proof
technique. We believe that the argument may generalize to more standard
initialization (e.g. uniform, Gaussian), however this would require more work
and it may not be a trivial extension.

###  A.2 First step: Recovering the support

As mentioned above, we train our network for one step on
$(x_{i},\chi_{[k]}(x_{i}))_{i\in[B]}$ with
$x_{i}\sim\operatorname{Rad}(p)^{\otimes d}$.

#### Population gradient at initialization.

Let us compute the population gradient at initialization. Since we set
$\xi_{0}=0$, we do not need to compute the initial gradient for $a$. Note that
at initialization $|\operatorname{NN}(x;\theta^{0})|<1$. Thus, the initial
population gradients are given by

$\displaystyle\forall j\in[k],i\in[N]\qquad G_{w_{i,j}}$
$\displaystyle=-a_{i}\mathbb{E}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left[\prod_{l\in[k]\setminus j}x_{l}\cdot\mathds{1}(\langle
w_{i},x\rangle+b_{i}\in[0,1])\right]$ (21) $\displaystyle\forall
j\not\in[k],i\in[N]\qquad G_{w_{i,j}}$
$\displaystyle=-a_{i}\mathbb{E}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left[\prod_{l\in[k]\cup j}x_{l}\cdot\mathds{1}(\langle
w_{i},x\rangle+b_{i}\in[0,1])\right]$ (22) $\displaystyle\forall i\in[N]\qquad
G_{b_{i}}$
$\displaystyle=-a_{i}\mathbb{E}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left[\prod_{l\in[k]}x_{l}\cdot\mathds{1}(\langle
w_{i},x\rangle+b_{i}\in[0,1])\right]$ (23)

######  Lemma 1.

Initialize $a,b,w$ according to (19). Then,

$\displaystyle\forall j\in[k],\qquad$ $\displaystyle
G_{w_{i,j}}=-\frac{\mu^{k-1}}{2N};$ (24) $\displaystyle\forall
j\not\in[k],\qquad$ $\displaystyle G_{w_{i,j}}=-\frac{\mu^{k+1}}{2N};$ (25)
$\displaystyle G_{b_{i}}=-\frac{\mu^{k}}{2N}.$ (26)

###### Proof.

If we initialize according to (19), we have $\langle
w_{i},x\rangle+b_{i}\in[0,1]$ for all $i$. The results holds since
$\mathbb{E}_{x\sim\operatorname{Rad}(p)^{\otimes d}}[\chi_{S}(x)]=\mu^{|S|}$.
∎

#### Effective gradient at initialization.

######  Lemma 2.

Let

$\displaystyle\hat{G}_{w_{i,j}}:=\frac{1}{B}\sum_{s=1}^{B}\nabla_{w_{i,j}^{0}}L(\theta^{0},\chi_{[k]},x_{s}^{t})$
(27)
$\displaystyle\hat{G}_{b_{i}}:=\frac{1}{B}\sum_{s=1}^{B}\nabla_{b_{i}^{0}}L(\theta^{0},\chi_{[k]},x_{s}^{t})$
(28)

be the effective gradients at initialization. If
$B\geq(8\zeta^{2}N^{2})^{-1}\log(\frac{Nd+N}{\delta})$, then with probability
$1-2\delta$,

$\displaystyle\|\hat{G}_{w_{i,j}}-G_{w_{i,j}}\|_{\infty}$
$\displaystyle\leq\zeta,$ (29)
$\displaystyle\|\hat{G}_{b_{i}}-G_{b_{i}}\|_{\infty}$
$\displaystyle\leq\zeta,$ (30)

where $G_{w_{i,j}},G_{b_{i}}$ are the population gradients.

###### Proof.

We note that $\mathbb{E}[\hat{G}_{w_{i,j}}]=G_{w_{i,j}}$,
$\mathbb{E}[\hat{G}_{b_{i}}]=G_{b_{i}}$, and
$|\hat{G}_{w_{i,j}}|,|\hat{G}_{b_{i}}|\leq\frac{1}{2N}$

$\displaystyle\mathbb{P}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left(\mid\hat{G}_{w_{i,j}}-G_{w_{i,j}}\mid\geq\zeta\right)\leq
2\exp\left(-8\zeta^{2}N^{2}B\right)\leq\frac{2\delta}{Nd+N},$ (31)
$\displaystyle\mathbb{P}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left(\mid\hat{G}_{b_{i}}-G_{b_{i}}\mid\geq\zeta\right)\leq
2\exp\left(-8\zeta^{2}N^{2}B\right)\leq\frac{2\delta}{Nd+N}.$ (32)

The result follows by union bound. ∎

######  Lemma 3.

Let

$\displaystyle w_{i,j}^{(1)}=w_{i,j}^{(0)}-\gamma_{0}\hat{G}_{w_{i,j}}$ (33)
$\displaystyle
b_{i}^{(1)}=\lambda_{0}\left(b_{i}^{(0)}-\psi_{0}\hat{G}_{b_{i}}\right)$ (34)

If $B\geq(8\zeta^{2}N^{2})^{-1}\log(\frac{Nd+N}{\delta})$, with probability
$1-2\delta$

  1. i)

For all $j\in[k]$, $i\in[N]$,
$|w_{i,j}^{(1)}-1|\leq\frac{2N\zeta}{\mu^{k-1}}$;

  2. ii)

For all $j\not\in[k]$,
$|w_{i,j}^{(1)}-(1-\frac{1}{2(d-k)})|\leq\frac{2N\zeta}{\mu^{k-1}}$ ;

  3. iii)

For all $i\in[N]$,
$|b_{i}^{(1)}-(d+1)(b_{i}^{(0)}-\frac{1}{2})|\leq\frac{N(d+1)\zeta}{\mu^{k}}$.

###### Proof.

We apply Lemma 3:

  1. i)

For all $j\in[k]$, $i\in[N]$,
$|\hat{w}_{i,j}^{(1)}-1|=\gamma_{0}|\hat{G}_{w_{i,j}}-G_{w_{i,j}}|\leq\frac{2N\zeta}{\mu^{k-1}}$;

  2. ii)

For all $j\not\in[k]$, $i\in[N]$,
$|\hat{w}_{i,j}-(1-\frac{1}{2(d-k)})|=\gamma_{0}|\hat{G}_{w_{i,j}}-G_{w_{i,j}}|\leq\frac{2N\zeta}{\mu^{k-1}}$;

  3. iii)

For all $i\in[N]$,

$\displaystyle|\hat{b}_{i}^{(1)}-(d+1)(b_{i}^{(0)}-\frac{1}{2})|$
$\displaystyle=|\lambda_{0}(b_{i}^{(0)}+\psi_{0}\hat{G}_{b_{i}})-\lambda_{0}(b_{i}^{(0)}+\psi_{0}G_{b_{i}})|$
(36)
$\displaystyle\leq|\lambda_{0}|\cdot|\psi_{0}|\cdot|\hat{G}_{b_{i}}-G_{b_{i}}|$
(37) $\displaystyle\leq\frac{N(d+1)\zeta}{\mu^{k}}.$ (38)

∎

######  Lemma 4.

If $N\geq(d+1)(d-k+1)\log((d+1)(d-k+1)/\delta)$, then with probability
$1-\delta$, for all $l\in\\{0,...,d\\}$, and for all $m\in\\{-1,...,d-k\\}$
there exists $i$ such that $b_{i}^{(0)}=\frac{b_{lm}}{d+1}+\frac{1}{2}$.

###### Proof.

The probability that there exist $l,m$ such that the above does not hold is

$\displaystyle\left(1-\frac{1}{(d+1)(d-k+1)}\right)^{N}\leq\exp\left(-\frac{N}{(d+1)(d-k+1)}\right)\leq\frac{\delta}{(d+1)(d-k+1)}.$
(39)

The result follows by union bound. ∎

######  Lemma 5.

Let
$\sigma_{lm}(x)=\operatorname{Ramp}\left(\sum_{j=1}^{d}x_{j}-\frac{1}{2(d-k)}\sum_{j>k}x_{j}+b_{lm}\right)$,
with $b_{lm}$ given in (20). If
$B\geq(8\zeta^{2}N^{2})^{-1}\log(\frac{Nd+N}{\delta})$ and
$N\geq(d+1)(d-k+1)\log((d+1)(d-k+1)/\delta)$, with probability $1-3\delta$,
for all $l,m$ there exists $i$ such that

$\displaystyle\Big{|}\sigma_{lm}(x)-\operatorname{Ramp}\left(\sum_{j=1}^{d}\hat{w}_{i,j}^{(1)}x_{j}+\hat{b}_{i}^{(1)}\right)\Big{|}\leq
3N(d+1)\zeta\mu^{-k}.$ (40)

###### Proof.

By Lemma 4, with probability $1-\delta$, for all $l,m$ there exists $i$ such
that $b_{i}^{(0)}=\frac{b_{lm}}{d+1}+\frac{1}{2}$. For ease of notation, we
replace indices $i\mapsto(lm)$, and denote
$\hat{\sigma}_{lm}(x)=\operatorname{Ramp}\left(\sum_{j=1}^{d}w_{lm,j}^{(1)}x_{j}+b_{lm}^{(1)}\right)$.
Then, by Lemma 3 with probability $1-2\delta$,

$\displaystyle|\sigma_{lm}(x)-\hat{\sigma}_{lm}(x)|$
$\displaystyle\leq\Big{|}\sum_{j=1}^{k}(w_{lm,j}^{(1)}-1)x_{j}+\sum_{j=k+1}^{d}\left(w_{lm,j}^{(1)}-\left(1-\frac{1}{2(d-k)}\right)\right)x_{j}+b_{lm}^{(1)}-b_{lm}\Big{|}$
(41) $\displaystyle\leq
k2N\zeta\mu^{-(k-1)}+(d-k)2N\zeta\mu^{-(k-1)}+N(d+1)\zeta\mu^{k}$ (42)
$\displaystyle\leq 3N(d+1)\zeta\mu^{-k}.$ (43)

∎

######  Lemma 6.

There exists $a^{*}$ with $\|a^{*}\|_{\infty}\leq 4(d-k)$ such that

$\displaystyle\sum_{l=0}^{d}\sum_{m=-1}^{d-k}a_{lm}^{*}\sigma_{lm}(x)=\chi_{[k]}(x).$
(44)

###### Proof.

Recall, that we assumed $d,k$ even and recall that

$\displaystyle\sigma_{lm}(x)=\operatorname{Ramp}\left(\sum_{j=1}^{d}x_{j}-\frac{1}{2(d-k)}\sum_{j>k}x_{j}+b_{lm}\right),$
(45)

where $b_{lm}=-d+2l-\frac{1}{2}+\frac{m+1}{d-k}$ for
$l\in[d],m\in\\{-1,...,d-k+1\\}$ and
$\operatorname{Ramp}(x)=\begin{cases}0\quad x\leq 0,\\\ x\quad 0<x\leq 1,\\\
1\quad x>1\end{cases}\,.$

Let $\sum_{j=1}^{d}x_{j}=d-2t$, where $t$ is the total number of $-1$, and
similarly let $-\sum_{j=k+1}^{d}x_{j}=(d-k)-2s$, where $s$ is the number of
$+1$ outside the support of the parity $\chi_{[k]}(x)$.We have,

$\displaystyle\sigma_{lm}(x)=\operatorname{Ramp}\left(2(l-t)+\frac{m+1-s}{d-k}\right).$
(46)

We take

$\displaystyle a_{lm}^{*}=(-1)^{l}(-1)^{m}2(d-k)\qquad\forall l\in[d],m=-1,$
(47) $\displaystyle a_{lm}^{*}=(-1)^{l}(-1)^{m}4(d-k)\qquad\forall
l\in[d],m\in\\{0,1,...,d-k-2\\},$ (48) $\displaystyle
a_{lm}^{*}=(-1)^{l}(-1)^{m}3(d-k)\qquad\forall l\in[d],m=d-k-1,$ (49)
$\displaystyle a_{lm}^{*}=(-1)^{l}(-1)^{m}(d-k)\qquad\forall l\in[d],m=d-k,$
(50)

Note that for all $l<t$,

$\displaystyle 2(l-t)+\frac{m+1-s}{d-k}\leq-2+\frac{d-k+1}{d-k}\leq 0,$ (51)

thus, $\sigma_{lm}(x)=0$ for all $m$. Moreover, for all $l>t$,

$\displaystyle 2(l-t)+\frac{m-s+1}{d-k}\geq 2-\frac{d-k}{d-k}=1.$ (52)

Thus, $\sigma_{lm}(x)=1$ for all $m$ and

$\displaystyle\sum_{m=-1}^{d-k}a_{lm}^{*}\sigma_{lm}(x)=\sum_{m=-1}^{d-k}a_{lm}^{*}=0.$
(53)

If $l=t$,

$\displaystyle\sum_{m=-1}^{d-k}$ $\displaystyle a_{tm}^{*}\sigma_{tm}(x)$
$\displaystyle=(-1)^{t}(d-k)\left[\sum_{m=0}^{d-k-2}4(-1)^{m}\operatorname{Ramp}\left(\frac{m+1-s}{d-k}\right)-3\operatorname{Ramp}\left(\frac{d-k-s}{d-k}\right)+\operatorname{Ramp}\left(\frac{d-k+1-s}{d-k}\right)\right]$
$\displaystyle=(-1)^{t}\left[\sum_{m=s}^{d-k-2}4(-1)^{m}\left(m+1-s\right)_{+}-3\left(d-k-s\right)_{+}+\left(d-k+1-s\right)_{+}\right]$
$\displaystyle=(-1)^{t}(-1)^{s}.$

Since we assumed $d,k$ even, $(-1)^{s}=\prod_{i=k+1}^{d}x_{i}$. Moreover,
observe that $\chi_{[k]}(x)=\prod_{i=k+1}^{d}x_{i}\cdot\prod_{i=1}^{d}x_{i}$.
Thus,

$\displaystyle\sum_{lm}a_{lm}^{*}\sigma_{lm}(x)=(-1)^{t}(-1)^{s}=\chi_{[k]}(x).$
(54)

∎

######  Lemma 7.

Let $f^{*}(x)=\sum_{l,m}a_{lm}^{*}\sigma_{lm}(x)$ and let
$\hat{f}(x)=\sum_{l,m}a^{*}_{lm}\hat{\sigma}_{lm}(x)$, with
$\sigma_{lm},\hat{\sigma}_{lm}$ defined in Lemma 11 and $a^{*}$ defined in
Lemma 6. If $B\geq(8\zeta^{2}N^{2})^{-1}\log(\frac{Nd+N}{\delta})$ and
$N\geq(d+1)(d-k+1)\log((d+1)(d-k+1)/\delta)$, with probability $1-3\delta$ for
all $x$,

$\displaystyle L(\hat{f},f^{*},x)\leq(d+1)^{2}(d-k+1)^{2}12N\zeta\mu^{-k}.$
(55)

###### Proof.

$\displaystyle|f^{*}(x)-\hat{f}(x)|$
$\displaystyle=\Big{|}\sum_{l,m}a_{l,m}^{*}(\sigma_{lm}(x)-\hat{\sigma}_{lm}(x)\Big{|}$
(56) $\displaystyle\leq
d(d-k+1)\|a^{*}\|_{\infty}\sup_{lm}|\sigma_{lm}(x)-\hat{\sigma}_{lm}(x)|$ (57)
$\displaystyle\leq(d+1)^{2}(d-k+1)^{2}12N\zeta\mu^{-k}.$ (58)

Thus,

$\displaystyle(1-f(x)f^{*}(x))_{+}$ $\displaystyle\leq|1-f(x)f^{*}(x)|$ (59)
$\displaystyle=|f^{*^{2}}(x)-f(x)f^{*}(x)|$ (60)
$\displaystyle=|f^{*}(x)|\cdot|f^{*}(x)-f(x)|\leq(d+1)^{2}(d-k+1)^{2}12N\zeta\mu^{-k},$
(61)

which implies the result. ∎

###  A.3 Second step: Convergence

To conclude, we use an established result on convergence of SGD on convex
losses (see e.g. [SS+12, SSBD14, DM20, MSS20, BEG+22]).

######  Theorem 7.

Let $\mathcal{L}$ be a convex function and let
$a^{*}\in\operatorname{argmin}_{\|a\|_{2}\leq\mathcal{B}}\mathcal{L}(a)$, for
some $\mathcal{B}>0$. For all $t$, let $\alpha^{(t)}$ be such that
$\mathbb{E}\left[\alpha^{(t)}\mid
a^{(t)}\right]=-\nabla_{a^{(t)}}\mathcal{L}(a^{(t)})$ and assume
$\|\alpha^{(t)}\|_{2}\leq\rho$ for some $\rho>0$. If $a^{(0)}=0$ and for all
$t\in[T]$ $a^{(t+1)}=a^{(t)}+\gamma\alpha^{(t)}$, with
$\gamma=\frac{\mathcal{B}}{\rho\sqrt{T}}$, then :

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathcal{L}(a^{(t)})\leq\mathcal{L}(a^{*})+\frac{\mathcal{B}\rho}{\sqrt{T}}.$
(62)

Let $\mathcal{L}(a):=\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[L((a,b^{(1)},w^{(1)}),\chi_{[k]},x)\right]$. Then, $\mathcal{L}$ is
convex in $a$ and for all $t\in[T]$,

$\displaystyle\alpha^{(t)}$
$\displaystyle=-\frac{1}{B}\sum_{s=1}^{B}\nabla_{a^{(t)}}L((a^{(t)},b^{(1)},w^{(1)}),\chi_{[k]},x)$
(63) $\displaystyle=-\frac{1}{B}\sum_{s=1}^{B}\sigma(w^{(1)}x+b^{(1)}).$ (64)

Thus, recalling $\sigma=\operatorname{Ramp}$, we have
$\|\alpha^{(t)}\|_{2}\leq\sqrt{N}$. Let $a^{*}$ be as in Lemma 6. Clearly,
$\|a^{*}\|_{2}\leq 4(d-k+1)^{3/2}(d+1)^{1/2}.$ Moreover, $a^{(1)}=0$. Thus, we
can apply Theorem 7 with $\mathcal{B}=4(d-k+1)^{3/2}(d+1)^{1/2}$,
$\rho=\sqrt{N}$ and obtain that if

  1. 1.

$N\geq(d+1)(d-k+1)\log((d+1)(d-k+1)/\delta)$;

  2. 2.

$\zeta\leq\frac{\epsilon\mu^{k}}{24(d+1)^{2}(d-k+1)^{2}N}$;

  3. 3.

$B\geq(8\zeta^{2}N^{2})^{-1}\log(\frac{Nd+N}{\delta})$;

  4. 4.

$T\geq\frac{64}{\epsilon^{2}}(d-k+1)^{3}(d+1)N$.

then, with probability $1-3\delta$ over the initialization

$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\min_{t\in[T]}L\left(\theta^{(t)},\chi_{[k]},x\right)\right]\leq\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon.$
(65)

######  Remark 6.

We assume $k\leq d/2$ to avoid exponential dependence of $\zeta$ (and
consequently of the batch size and of the computational complexity) in $d$.
Indeed, if $k\leq d/2$, then,

$\displaystyle\mu^{k}=\left(1-\frac{1}{2(d-k)}\right)^{k/2}\geq\left(1-\frac{1}{d}\right)^{d/4}\sim
e^{-1/4}.$ (66)

######  Remark 7 (Noisy-GD).

We remark that the proof extends to the noisy-GD algorithm with noise level
$\tau\leq\frac{\zeta}{\sqrt{2}}\cdot\log\left(\frac{Nd+n}{\delta}\right)^{-1/2}$
(see Def. 6). Indeed, one can replace Lemma 2 with the following Lemma, and
keep the rest of the proof unchanged.

######  Lemma 8 (Noisy-GD).

Let

$\displaystyle\hat{G}_{w_{i,j}}:=G_{w_{i,j}}+Z_{w_{i,j}},$ (67)
$\displaystyle\hat{G}_{b_{i}}:=G_{b_{i}}+Z_{b_{i}},$ (68)

be the effective gradients at initialization, where $G_{w_{i,j}},G_{b_{i}}$
are the population gradients at initialization and $Z_{w_{i,j}},Z_{b_{i}}$ are
iid $\mathcal{N}(0,\tau^{2})$. If
$\tau\leq\frac{\zeta}{\sqrt{2}}\cdot\log\left(\frac{Nd+n}{\delta}\right)^{-1/2}$,
with probability $1-2\delta$:

$\displaystyle\|\hat{G}_{w_{i,j}}-G_{w_{i,j}}\|_{\infty}\leq\zeta,$ (69)
$\displaystyle\|\hat{G}_{b_{i}}-G_{b_{i}}\|_{\infty}\leq\zeta.$ (70)

###### Proof.

By concentration of Gaussian random variables:

$\displaystyle\mathbb{P}\left(|\hat{G}_{w_{i,j}}-G_{w_{i,j}}|\geq\zeta\right)\leq
2\exp\left(-\frac{\zeta^{2}}{2\tau^{2}}\right)\leq\frac{2\delta}{Nd+N},$ (71)
$\displaystyle\mathbb{P}\left(|\hat{G}_{b_{i}}-G_{b_{i}}|\geq\zeta\right)\leq
2\exp\left(-\frac{\zeta^{2}}{2\tau^{2}}\right)\leq\frac{2\delta}{Nd+N}.$ (72)

The result follows by union bound. ∎

##  Appendix B Proof of Theorem 4

######  Theorem 8 (Theorem 4, restatement).

Let $k,d$ be integers, such that $d\geq k$ and $k$ even. Let
$\operatorname{NN}(x;\theta)=\sum_{i=1}^{N}a_{i}\sigma(w_{i}x+b_{i})$ be a
2-layers fully connected network with activation
$\sigma(y):=\operatorname{ReLU}(y)$ and $N\geq(k+1)\log(\frac{k+1}{\delta})$.
Consider training $\operatorname{NN}(x;\theta)$ with SGD on the covariance
loss with batch size $B\geq(2\zeta^{2})^{-1}\log(\frac{dN}{\delta})$, with
$\zeta\leq\frac{\epsilon(\mu^{k-1}-\mu^{k+1})}{64k^{2}N}\cdot\left(1+\frac{d-k}{k}\right)^{-1}$,
for some $\mu\in(0,1)$. Then, there exists an initialization, a learning rate
schedule, and a 2-CL strategy such that after
$T\geq\frac{64k^{3}N}{\epsilon^{2}}$ iterations, with probability $1-3\delta$
SGD outputs a network with generalization error at most $\epsilon$.

###  B.1 Proof setup

Similarly as before, we consider a 2-layers neural network, defined as
$\operatorname{NN}(x;\theta)=\sum_{i=1}^{N}a_{i}\sigma(w_{i}x+b_{i}),$ where
$N$ is the number of hidden units, $\theta=(a,b,w)$ and
$\sigma:=\operatorname{ReLU}$. Our proof scheme is similar to the previous
Section. Again, we assume without loss of generality that the labels are
generated by $\chi_{[k]}(x):=\prod_{i=1}^{k}x_{i}$. We assume $k$ to be even.
We train our network with SGD on the covariance loss, defined in Def. 5. We
use the same updates as in (10) with:

$\displaystyle x_{s}^{0}\overset{iid}{\sim}\operatorname{Rad}(p)^{\otimes
d}\qquad\forall s\in[B],$ (73) $\displaystyle
x_{s}^{t}\overset{iid}{\sim}\operatorname{Rad}(p)^{\otimes d}\qquad\forall
t\geq 1,s\in[B],$ (74)

for some $p\in(1/2,1)$. We denote $\mu:=2p-1$. We set the parameters to:

$\displaystyle\gamma_{0}=16N(\mu^{k-1}-\mu^{k+1})^{-1}k^{-1},$
$\displaystyle\gamma_{t}=0\qquad\forall t\geq 1,\qquad$ (75)
$\displaystyle\xi_{0}=0,$
$\displaystyle\xi_{t}=\frac{\epsilon}{8N}\quad\forall t\geq 1,\qquad$ (76)
$\displaystyle\psi_{0}=0,$ $\displaystyle\psi_{t}=0\qquad\forall t\geq
1,\qquad$ (77) $\displaystyle c_{0}=-1,$ $\displaystyle c_{t}=0\qquad\forall
t\geq 1,\qquad$ (78) $\displaystyle\lambda_{0}=1,$
$\displaystyle\lambda_{t}=1\qquad\forall t\geq 1,\qquad$ (79) $\displaystyle
d_{0}=-1,$ $\displaystyle d_{t}=0\qquad\forall t\geq 1,\qquad$ (80)

and we consider the following initialization scheme:

$\displaystyle w_{i,j}^{(0)}$ $\displaystyle=0\qquad\forall i\in[N],j\in[d];$
$\displaystyle a_{i}^{(0)}$ $\displaystyle=\frac{1}{16N}\qquad\forall
i\in[N];$ (81) $\displaystyle b_{i}^{(0)}$
$\displaystyle\sim\operatorname{Unif}\Big{\\{}\frac{2(i+1)}{k}:i\in\\{0,1,...,k\\}\Big{\\}}.$

###  B.2 First step: Recovering the support

#### Population gradient at initialization.

At initialization, we have $|\operatorname{NN}(x;\theta^{0})|<\frac{1}{4}$,
thus

$\displaystyle\Big{|}\mathrm{cov}(\chi_{[k]},\theta^{0},x,\operatorname{Rad}(p)^{\otimes
d})\Big{|}$ $\displaystyle<1.$ (82)

The initial gradients are therefore given by:

$\displaystyle\forall i,j\qquad G_{w_{i,j}}$
$\displaystyle=-a_{i}\mathbb{E}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left[\Big{(}\prod_{l\in[k]}x_{l}-\mu^{k}\Big{)}\cdot\Big{(}x_{j}\mathds{1}(\langle
w_{i},x\rangle+b_{i}>0)-\mathbb{E}x_{j}\mathds{1}(\langle
w_{i},x\rangle+b_{i}>0)\Big{)}\right]$ (83) $\displaystyle\forall
i\in[N]\qquad G_{b_{i}}$
$\displaystyle=-a_{i}\mathbb{E}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left[\Big{(}\prod_{l\in[k]}x_{l}-\mu^{k}\Big{)}\cdot\Big{(}\mathds{1}(\langle
w_{i},x\rangle+b_{i}>0)-\mathbb{E}\mathds{1}(\langle
w_{i},x\rangle+b_{i}>0)\Big{)}\right]$ (84)

If we initialize $a,b,w$ according to (81). Then,

$\displaystyle\forall j\in[k],\qquad$ $\displaystyle
G_{w_{i,j}}=-\frac{\mu^{k-1}-\mu^{k+1}}{16N};$ (85) $\displaystyle\forall
j\not\in[k],\qquad$ $\displaystyle G_{w_{i,j}}=0;$ (86) $\displaystyle
G_{b_{i}}=0.$ (87)

#### Effective gradient at initialization.

######  Lemma 9.

Let

$\displaystyle w_{i,j}^{(1)}=w_{i,j}^{(0)}-\gamma_{0}\hat{G}_{w_{i,j}}$ (88)
$\displaystyle
b_{i}^{(1)}=\lambda_{0}\left(b_{i}^{(0)}+\psi_{0}\hat{G}_{b_{i}}\right)+d_{0},$
(89)

where
$\hat{G}_{w_{i,j}}:=\frac{1}{B}\sum_{s=1}^{B}\nabla_{w_{i,j}^{0}}L(\theta^{0},\chi_{[k]},x_{s}^{t})$
and
$\hat{G}_{b_{i}}:=\frac{1}{B}\sum_{s=1}^{B}\nabla_{b_{i}^{0}}L(\theta^{0},\chi_{[k]},x_{s}^{t})$
are the gradients estimated from the initial batch. Then, with probability
$1-2\delta$, if $B\geq(2\zeta^{2})^{-1}\log\left(\frac{dN}{\delta}\right)$,

  1. i)

For all $j\in[k]$, $i\in[N]$, $|w_{i,j}^{(1)}-\frac{1}{k}|\leq\frac{\zeta
16N}{k(\mu^{k-1}-\mu^{k+1})}$;

  2. ii)

For all $j\not\in[k]$, $|w_{i,j}^{(1)}|\leq\frac{\zeta
16N}{k(\mu^{k-1}-\mu^{k+1})}$ ;

  3. iii)

For all $i\in[N]$, $b_{i}^{(1)}=b^{(0)}-1$

###### Proof.

By Lemma 3 ,if $B\geq(2\zeta^{2})^{-1}\log\left(\frac{dk}{\delta}\right)$,
then for all $j\in[k],i\in[N]$, $|\hat{G}_{w_{i,j}}-G_{w_{i,j}}|\leq\zeta$.
Thus,

  1. i)

For all $j\in[k]$, $i\in[N]$,
$|w_{i,j}^{(1)}-\frac{1}{k}|=\gamma_{0}|\hat{G}_{w_{i,j}}-G_{w_{i,j}}|\leq\frac{\zeta
16N}{k(\mu^{k-1}-\mu^{k+1})}$;

  2. ii)

For all $j\in[k]$, $i\in[N]$,
$|w_{i,j}^{(1)}|=\gamma_{0}|\hat{G}_{w_{i,j}}-G_{w_{i,j}}|\leq\frac{\zeta
16N}{k(\mu^{k-1}-\mu^{k+1})}$;

iii) follows trivially. ∎

######  Lemma 10.

If $N\geq(k+1)\log\left(\frac{k+1}{\delta}\right)$, with probability
$1-\delta$ for all $i\in\\{0,...,k\\}$ there exists $l\in[N]$ such that
$b_{l}^{(0)}=\frac{2(i+1)}{k}$.

###### Proof.

The probability that there exists $i$ such that the above does not hold is

$\displaystyle\left(1-\frac{1}{k+1}\right)^{N}\leq\exp\left(-\frac{N}{k+1}\right)\leq\frac{\delta}{k+1}.$
(91)

The result follows by union bound. ∎

######  Lemma 11.

Let
$\sigma_{i}(x):=\operatorname{ReLU}\left(\frac{1}{k}\sum_{j=1}^{k}x_{j}+b_{i}\right)$,
with $b_{i}=-1+\frac{2(i+1)}{k}$. Then, with probability $1-3\delta$, for all
$i\in\\{0,...,k\\}$ there exists $l\in[N]$ such that

$\displaystyle\Big{|}\sigma_{i}(x)-\operatorname{ReLU}\left(\sum_{j=1}^{d}w_{l,j}^{(1)}x_{j}+b_{l}^{(1)}\right)\Big{|}\leq\frac{\zeta
16N}{\mu^{k-1}-\mu^{k+1}}\cdot\left(1+\frac{d-k}{k}\right).$ (92)

###### Proof.

By Lemma 10 and Lemma 9, with probability $1-3\delta$, for all $i$ there
exists $l$ such that $b^{(1)}_{l}=-1+\frac{2(i+1)}{k}$, and

$\displaystyle\Big{|}\sigma_{i}(x)-\operatorname{ReLU}\left(\sum_{j=1}^{d}w_{l,j}^{(1)}x_{j}+b_{l}^{(1)}\right)\Big{|}$
$\displaystyle\leq\Big{|}\sum_{j=1}^{k}\left(\frac{1}{k}-w_{l,j}^{(1)}x_{j}\right)\Big{|}+\Big{|}\sum_{j=k+1}^{d}w_{l,j}^{(1)}x_{j}\Big{|}$
(93) $\displaystyle\leq\frac{\zeta 16N}{\mu^{k-1}-\mu^{k+1}}+\frac{\zeta
16N(d-k)}{(\mu^{k-1}-\mu^{k+1})k}$ (94) $\displaystyle=\frac{\zeta
16N}{\mu^{k-1}-\mu^{k+1}}\cdot\left(1+\frac{d-k}{k}\right).$ (95)

∎

######  Lemma 12.

There exist $a^{*}$ with $\|a^{*}\|_{\infty}\leq 2k$ such that

$\displaystyle\sum_{i=0}^{k}a_{i}^{*}\sigma_{i}(x)=\chi_{[k]}(x).$ (96)

###### Proof.

We assume $k$ to be even. Let $\sum_{j=1}^{k}x_{j}=k-2t$, where
$t:=|\\{i:x_{i}=-1,i\in[k]\\}|$. Thus,

$\displaystyle\sigma_{i}(x)=\operatorname{ReLU}\left(\frac{2(i+1-t)}{k}\right).$
(97)

We choose

$\displaystyle a_{i}^{*}=(-1)^{i}2k\qquad\forall i\in\\{0,1,...,k-2\\},$ (98)
$\displaystyle a_{i}^{*}=(-1)^{i}\frac{3}{2}k\qquad i=k-1,$ (99)
$\displaystyle a_{i}^{*}=(-1)^{i}\frac{1}{2}k\qquad i=k.$ (100)

One can check that with these $a^{*}_{i}$ the statement holds. ∎

######  Lemma 13.

Let $f^{*}(x)=\sum_{i=0}^{k}a_{i}^{*}\sigma_{i}(x)$ and let
$\hat{f}(x)=\sum_{i=0}^{k}a^{*}_{i}\hat{\sigma}_{i}(x)$, with $\sigma_{i}(x)$
defined above and
$\hat{\sigma}_{i}(x):=\operatorname{ReLU}(\sum_{j=1}^{d}w_{i,j}^{(1)}x_{j}+b_{i}^{(1)})$.
Then, with probability $1-3\delta$ for all $x$,

$\displaystyle(1-f(x)f^{*}(x))_{+}\leq\frac{32k^{2}\zeta
N}{\mu^{k-1}-\mu^{k+1}}\cdot\left(1+\frac{d-k}{k}\right),$ (101)

where $(z)_{+}:=\max\\{0,z\\}$.

###### Proof.

$\displaystyle|f^{*}(x)-\hat{f}(x)|$
$\displaystyle=\Big{|}\sum_{i}a_{i}^{*}(\sigma_{i}(x)-\hat{\sigma}_{i}(x)\Big{|}$
(102) $\displaystyle\leq
k\|a^{*}\|_{\infty}\sup_{i}|\sigma_{i}(x)-\hat{\sigma}_{i}(x)|$ (103)
$\displaystyle\leq\frac{32k^{2}\zeta
N}{\mu^{k-1}-\mu^{k+1}}\cdot\left(1+\frac{d-k}{k}\right).$ (104)

Thus,

$\displaystyle(1-f(x)f^{*}(x))_{+}$ $\displaystyle\leq|1-f(x)f^{*}(x)|$ (105)
$\displaystyle=|f^{*^{2}}(x)-f(x)f^{*}(x)|$ (106)
$\displaystyle=|f^{*}(x)|\cdot|f^{*}(x)-f(x)|\leq\frac{32k^{2}\zeta
N}{\mu^{k-1}-\mu^{k+1}}\cdot\left(1+\frac{d-k}{k}\right).$ (107)

∎

###  B.3 Second step: Convergence

We apply Theorem 7 with
$\mathcal{L}(a):=\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[L_{\mathrm{cov}}((a,b^{(1)},w^{(1)}),\chi_{[k]},x)\right]$,
$\rho=2\sqrt{N}$, $\mathcal{B}=2k\sqrt{k}$. We get that if

  1. 1.

$N\geq(k+1)\log(\frac{k+1}{\delta})$;

  2. 2.

$\zeta\leq\frac{\epsilon(\mu^{k-1}-\mu^{k+1})}{64k^{2}N}\cdot\left(1+\frac{d-k}{k}\right)^{-1}$;

  3. 3.

$B\geq(2\zeta^{2})^{-1}\log(\frac{dN}{\delta})$;

  4. 4.

$T\geq\frac{64k^{3}N}{\epsilon^{2}}$ .

then with probability $1-3\delta$ over the initialization,

$\displaystyle\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\min_{t\in[T]}L_{\mathrm{cov}}\left(\chi_{[k]},\theta^{(t)},x,\operatorname{Rad}(1/2)^{\otimes
d}\right)\right]\leq\epsilon.$ (108)

######  Remark 8.

We remark that if $\mu=\theta_{d,k}(1)$, then $\zeta$ decreases exponentially
fast in $k$, and as a consequence the batch size and the computational cost
grow exponentially in $k$. If however we choose $\mu=1-1/k$, then we get
$\zeta=1/\operatorname{poly}(k)$ and, as a consequence, the batch size and the
computational cost grow polynomially in $k$.

##  Appendix C Proof of Theorem 5

Let us consider $r=2$. The case of general $r$ follows easily. Let us state
the following Lemma.

######  Lemma 14.

Let $x\sim\operatorname{Rad}(p)^{\otimes d}$ and let
$H(x):=\sum_{i=1}^{d}\mathds{1}(x_{i}=1)$ be the Hamming weight of $H(x)$.
Assume $\epsilon<p<\epsilon^{\prime}$ for some
$\epsilon,\epsilon^{\prime}\in[0,1/2]$, then,

$\displaystyle\mathbb{P}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left(H(x)\geq\epsilon^{\prime}d\right)\leq
2\exp\left(-(\epsilon^{\prime}-p)^{2}d\right);$ (109)
$\displaystyle\mathbb{P}_{x\sim\operatorname{Rad}(p)^{\otimes
d}}\left(H(x)\leq\epsilon d\right)\leq 2\exp\left(-(p-\epsilon)^{2}d\right).$
(110)

###### Proof of Lemma 14.

We apply Hoeffding’s inequality with $\mathbb{E}[H(x)]=pd$ and
$\sum_{i=1}^{d}x_{i}=d-2H(x)$:

$\displaystyle\mathbb{P}(|H(x)-pd|\geq td)\leq 2\exp\left(-(t-p)^{2}d\right).$
(111)

∎

Take $\epsilon$ such that $|p_{1}-\frac{1}{2}|>\epsilon$, and consider the
following algorithm:

  1. 1.

Take a fully connected neural network $\operatorname{NN}(x;\psi)$ with the
same architecture as $\operatorname{NN}(x;\theta)$ and with initialization
$\psi^{(0)}=\theta^{(0)}$;

  2. 2.

Train $\operatorname{NN}(x;\psi)$ on data $(x,\chi_{S}(x))$, with
$x\sim\operatorname{Rad}(p_{1})^{\otimes d}$, for $T_{1}$ epochs;

  3. 3.

Train $\operatorname{NN}(x;\psi)$ with initialization $\psi^{(T_{1})}$ on data
$(x,\chi_{V}(x))$, with $x\sim\operatorname{Rad}(1/2)^{\otimes d}$, for
$T-T_{1}$ epochs.

The result holds by the following two Lemmas.

######  Lemma 15.

$\operatorname{TV}(\theta^{(T)};\psi^{(T)})\leq\frac{AT\sqrt{|\theta|}}{\tau}\cdot\exp(-d\delta^{2})$,
where $\delta=\min\\{|\epsilon-p_{1}|,|1/2-\epsilon|\\}$ and
$\operatorname{TV}$ denotes the total variation distance between the law of
$\theta^{(T)}$ and $\psi^{(T)}$.

###### Proof of Lemma 15.

Clearly, $\operatorname{TV}(\theta^{(0)};\psi^{(0)})=0$. Then, using
subadditivity of TV

$\displaystyle\operatorname{TV}(\theta^{(T)};\psi^{(T)})$
$\displaystyle\leq\sum_{t=1}^{T}\operatorname{TV}(\theta^{(t)};\psi^{(t)}|\\{Z^{i}\\}_{i\leq
t-2})$ (112)
$\displaystyle=\sum_{t=1}^{T}\operatorname{TV}(\gamma(g_{\theta^{(t-1)}}+Z^{t-1});\gamma(g_{\psi^{(t-1)}}+Z^{t-1})|\\{Z^{i}\\}_{i\leq
t-1}),$ (113)

where $g_{\theta^{(t-1)}},g_{\psi^{(t-1)}}$ denote the population gradients in
$\theta^{(t-1)}$ and $\psi^{(t-1)}$, respectively. Then, recalling that the
$Z^{t-1}$ are Gaussians, we get

$\displaystyle\operatorname{TV}(\theta^{(T)};\psi^{(T)})$
$\displaystyle\overset{(a)}{\leq}\sum_{t=1}^{T}\frac{1}{2\tau\gamma}\|\gamma
g_{\theta^{(t-1)}}-\gamma g_{\psi^{(t-1)}}\|_{2}$ (114)
$\displaystyle\overset{(b)}{\leq}\sum_{t=1}^{T_{r-1}}\frac{1}{2\tau\gamma}\cdot
2\sqrt{|\theta|}A\gamma\cdot\mathbb{P}(H(x)\geq\epsilon
d)+\sum_{t=T_{r-1}}^{T}\frac{1}{2\tau\gamma}\cdot
2\sqrt{|\theta|}A\gamma\cdot\mathbb{P}(H(x)\leq\epsilon d)$ (115)
$\displaystyle\overset{(c)}{\leq}\frac{AT\sqrt{|\theta|}}{\tau}\exp(-d\delta^{2}).$
(116)

In $(a)$ we applied the formula for the TV between Gaussian variables with
same variance. In $(b)$ we used that each gradient is in $[-A,A]$ and that
during the first part of training, for all $x$ with $H(x)<\epsilon$, the two
gradients are the same, and, similarly, in the second part of training, for
all $x$ with $H(x)>\epsilon d$, the two gradients are the same. In $(c)$ we
applied Lemma 14. ∎

We apply Theorem 3 from [AS20], which we restate here for completeness.

######  Theorem 9 (Theorem 3 in [AS20]).

Let $\mathcal{P}_{k}$ be the set of $k$-parities over $d$ bits. Noisy-GD on
any neural network $\operatorname{NN}(x;w)$ of size $|w|$ and any
initialization, after $T$ steps of training on samples drawn from the uniform
distribution, outputs a network such that

$\displaystyle\frac{1}{|\mathcal{P}_{k}|}\sum_{f\in\mathcal{P}_{k}}\Big{|}\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\operatorname{NN}(x;w^{(T)})\cdot
f(x)\right]\Big{|}\leq\frac{T\sqrt{|\theta|}A}{\tau}\cdot{d\choose k}^{-1/2}.$
(117)

In our case, this implies:

$\displaystyle\mathbb{E}_{V}\Big{|}\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\operatorname{NN}(x;\psi^{(T)})\cdot\chi_{V}(x)\right]\Big{|}\leq\frac{(T-T_{r-1})\sqrt{|\theta|}A}{\tau}\cdot{d\choose
k_{V}}^{-1/2},$ (118)

where by $\mathbb{E}_{V}$ we denote the expectation over set $V$ sampled
uniformly at random from all subsets of $[d]$ of cardinality $k_{V}$. By Lemma
14, this further implies:

$\displaystyle\mathbb{E}_{V}\Big{|}\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\operatorname{NN}(x;\psi^{(T)})\cdot
G_{S,V,\epsilon}(x)\right]\Big{|}\leq\frac{(T-T_{r-1})\sqrt{|\theta|}A}{\tau}\cdot{d\choose
k_{V}}^{-1/2}+\exp(-d\delta^{2}).$ (119)

To conclude our proof, note that:

$\displaystyle\mathbb{E}_{V}\Big{|}\mathbb{E}_{x}$
$\displaystyle\left[\operatorname{NN}(x,\psi^{(T)})\cdot
G_{S,V,\epsilon}(x)\right]\Big{|}$ (120)
$\displaystyle=\mathbb{E}_{V}\left[\Big{|}\mathbb{E}_{x}\left[\operatorname{NN}(x,\psi^{(T)})\cdot
G_{S,V,\epsilon}(x)\right]\Big{|}\mid\Big{|}S\cap
V\Big{|}=0\right]\cdot\mathbb{P}_{V}(|S\cap V|=0)$ (121)
$\displaystyle\quad+\mathbb{E}_{V}\left[\Big{|}\mathbb{E}_{x}\left[\operatorname{NN}(x,\psi^{(T)})\cdot
G_{S,V,\epsilon}(x)\right]\Big{|}\mid\Big{|}S\cap
V\Big{|}>0\right]\cdot\mathbb{P}_{V}(|S\cap V|>0).$ (122)

One can check that,

$\displaystyle\mathbb{P}_{V}(|S\cap V|>0)=1-\frac{2k_{S}k_{V}}{d}+O(d^{-2}).$
(123)

Moreover, since both the initialization and noisy-GD on fully connected
networks are invariant to permutation of the input neurons, for any $V$ such
that $|S\cap V|=0$, the algorithm achieves the same correlation. Thus,
applying Lemma 15:

$\displaystyle\Big{|}\mathbb{E}_{x}$
$\displaystyle\left[\operatorname{NN}(x;\theta^{(T)})\cdot
G_{S,V,\epsilon}(x)\right]\Big{|}$
$\displaystyle\qquad\leq\frac{(T-T_{r-1})\sqrt{|\theta|}A}{\tau}\cdot{d\choose
k_{V}}^{-1/2}+\frac{2AT\sqrt{|\theta|}}{\tau}\exp(-d\delta^{2})+\frac{2k_{S}k_{V}}{d}+O(d^{-2}).$

The argument for general $r$ holds by taking $\epsilon$ such that
$|p_{l}-\frac{1}{2}|>\epsilon$ for all $l\in[r-1]$ and by replacing step $2$
of the algorithm above with the following:

  1. 2.

Train $\operatorname{NN}(x;\psi)$ on data $(x,\chi_{S}(x))$ using a
$(r-1)$-CL($(T_{1},...,T_{r-1}),(p_{1},...,p_{r-1})$) strategy.

##  Appendix D Proof of Corollary 1

We use the same proof strategy of Theorem 5: specifically, we use the same
algorithm for training a network $\operatorname{NN}(x;\psi)$ with the same
architecture as $\operatorname{NN}(x;\theta)$, so that Lemma 15 still holds.
We import Theorem 3 from [AS20] in the following form.

######  Theorem 10 (Theorem 3 in [AS20]).

Let $\mathcal{F}$ be the set of $k$-parities over set $\\{d/2+1,...,d\\}$.
Noisy-GD on any neural network $\operatorname{NN}(x;w)$ of size $|w|$ and any
initialization, after $T$ steps of training on samples drawn from the uniform
distribution, outputs a network such that

$\displaystyle\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\Big{|}\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\operatorname{NN}(x;w^{(T)})\cdot
f(x)\right]\Big{|}\leq\frac{T\sqrt{|\theta|}A}{\tau}\cdot{d/2\choose
k}^{-1/2}.$ (124)

Similarly as before, Theorem 10 and Lemma 14 imply:

$\displaystyle\mathbb{E}_{V}\Big{|}\mathbb{E}_{x\sim\operatorname{Rad}(1/2)^{\otimes
d}}\left[\operatorname{NN}(x;\psi^{(T)})\cdot
G_{S,V,\epsilon}(x)\right]\Big{|}\leq\frac{(T-T_{r-1})\sqrt{|\theta|}A}{\tau}\cdot{d/2\choose
k_{V}}^{-1/2}+\exp(-d\delta^{2}),$ (125)

where by $\mathbb{E}_{V}$ we denote the expectation over set $V$ sampled
uniformly at random from all subsets of $\\{d/2+1,...,d\\}$ of cardinality
$k_{V}$. Since both the initialization and noisy-GD on fully connected
networks are invariant to permutation of the input neurons, for any
$V\subseteq\\{d/2+1,...,d\\}$, the algorithm achieves the same correlation.
Thus, applying Lemma 15:

$\displaystyle\Big{|}\mathbb{E}_{x}\left[\operatorname{NN}(x;\theta^{(T)})\cdot
G_{S,V,\epsilon}(x)\right]\Big{|}$
$\displaystyle\leq\frac{(T-T_{r-1})\sqrt{|\theta|}A}{\tau}\cdot{d/2\choose
k_{V}}^{-1/2}+\frac{2AT\sqrt{|\theta|}}{\tau}\exp(-d\delta^{2}).$ (126)

##  Appendix E Further experiments

Figure 4: Learning $20$-parities over $100$ bits, with a 2-layer neural
network with $100$ hidden units trained by SGD with batch size $32$ (left),
$64$ (center), $128$ (right).

Figure 5: Learning $20$-parities over $100$ bits, with a 3-layer neural
network with $100$ hidden units trained by SGD with batch size $32$ (left),
$64$ (center) $1024$ (right).