Learning Parities with Neural Networks

Introduction

The remarkable success of neural-networks has sparked great theoretical interest in understanding their behavior. Impressively, a large number of papers have established polynomial-time learnability of various models by neural networks algorithms (i.e. gradient based methods). Yet, to the best of our knowledge, with the single exception of learning one neuron , all these results prove learnability of linear models. Namely, models that can be realized by a linear classifier, on top of a (possibly random) embedding that is fixed and does not depend on the data. This is not surprising, as the majority of these papers prove learnability via “linearization" of the network at the vicinity of the initial random weights.

While these results achieved a remarkable progress in understanding neural-networks, they are still disappointing in some sense. Indeed, in practice, neural-networks’ performance is far better than linear methods, a fact that is not explained by these works. Moreover, learning a linear classifier on top of a fixed embedding seems to completely miss the “deepness" of deep learning.

Recently, a few works have provided theoretical results demonstrating that neural-networks are stronger than random features - a linear model where the embedding map is randomly drawn from some predefined distribution . These works show problems that are easy to learn with neural-networks, while being hard to learn with random features. The work of shows that random features cannot approximate a distribution generated by a single neuron and Gaussian inputs, which is known to be learnable by a neural-network. The work of shows that neural-networks are more efficient than random features, in terms of sample complexity and run-time, for some regression problems generated by a ResNet-like network. A work by shows other family of distributions where neural-networks with quadratic activation outperform random features, when the number of features is smaller than the dimension.

Our result differs from these works in several aspects. First, and study the power of approximating a regression problems, and hence their results cannot be applied to the setting of classification, which we cover in this work. Second, we give an exponential separation, while and only give polynomial separation. Namely, the problems for which they show that networks performs better than linear methods are still poly-time learnable by linear methods.

Problem Setting

Let ${\cal H}$ be some class of functions from ${\cal X}$ to ${\cal Y}$. We define the loss of ${\cal H}$ with respect to the distribution ${\cal D}$ to be the loss of the best function in ${\cal H}$:

So, $L_{\cal D}({\cal H})$ measures whether ${\cal H}$ can approximate the distribution ${\cal D}$.

Our target functions will be parities on $k$ bits of the input. Let $A\subset[n]$ be some subset of size $|A|=k$, for some odd $k\geq 3$, and define $f_{A}$ to be the parity of the bits in $A$, namely $f_{A}({\mathbf{x}})=\operatorname*{sign}(\prod_{i\in A}x_{i})$. For every subset $A\subset[n]$, we construct a distribution on the instances $\mathcal{X}$ that is easy to learn with neural-networks. Let $\mathcal{D}_{A}^{(1)}$ be the uniform distribution on $\mathcal{X}$, and let $\mathcal{D}_{A}^{(2)}$ be the distribution that is uniform on all the bits in $[n]\setminus A$, and the bits in $A$ are all $1$ w.p. $\frac{1}{2}$ and $-1$ w.p. $\frac{1}{2}$. Let $\mathcal{D}_{A}$ be a distribution over $\mathcal{X}\times\mathcal{Y}$ where we samples ${\mathbf{x}}\sim\mathcal{D}_{A}^{(1)}$ w.p. $\frac{1}{2}$ and ${\mathbf{x}}\sim\mathcal{D}_{A}^{(2)}$ w.p. $\frac{1}{2}$, and set $y=f_{A}({\mathbf{x}})$. This defines a family of distributions $\mathcal{F}=\{\mathcal{D}_{A}~{}:~{}A\subseteq[n],\left\lvert A\right\rvert=k\}$.

The training algorithm.

for some choice of $\eta_{1},\dots,\eta_{T}$ and $\lambda_{1},\dots,\lambda_{T}$.

We assume the network is initialized with a symmetric initialization: for every $i\in[q]$ initialize ${\mathbf{w}}^{(0)}_{i}\sim U(\{-1,0,1\}^{n})$ and then initialize ${\mathbf{w}}^{(0)}_{q+i}=-{\mathbf{w}}_{i}$, initialize $b^{(0)}_{i}=\frac{1}{8k}$ and $b^{(0)}_{q+i}=-\frac{1}{8k}$ and initialize $u^{(0)}_{i}\sim U([-\frac{n}{k},\frac{n}{k}])$ and $u^{(0)}_{q+i}=-u^{(0)}_{i}$.

Main Result

Our main result shows a separation between neural-networks and any linear method (i.e., learning a linear classifier over some fixed embedding). This result is composed of two parts: first, we show that the family ${\cal F}$ cannot be approximated by any polynomial-size linear method. Second, we show that neural-networks can be trained to approximate the family ${\cal F}$ using gradient-descent.

The following theorem implies that the class ${\cal F}$ cannot be approximated by a linear classifiers on top of a fixed embedding, unless the embedding dimension or the norm of the weights is exponential:

Fix some $\Psi:\mathcal{X}\to^{N}$, and define:

Then, if $k\leq\frac{n}{16}$, there exists some ${\cal D}_{A}\in{\cal F}$ such that:

The following result shows that neural-networks can learn the family $\mathcal{F}$ with gradient-descent. That is, for every distribution $\mathcal{D}_{A}\in\mathcal{F}$, a large enough neural-network achieves a small error when trained with gradient-descent on the distribution $\mathcal{D}_{A}$. Together with theorem 1, it establishes an (exponential) separation between the class of distributions that can be learned with neural-networks, and the class of distributions that can be learned by linear methods.

Fix some ${\cal D}_{A}\in{\cal F}$. Assume we run gradient-descent for $T$ iterations, with $\eta_{1}=1,\lambda_{1}=\frac{1}{2}$ and $\eta_{t}=\frac{k^{2}}{T\sqrt{q}},\lambda_{t}\leq\frac{k}{n}$ for every $t>1$. Assume that $n\geq\Omega(1)$ and $7\leq k\leq O(\sqrt{n})$. Fix some $\delta>0$, and assume that the number of neurons satisfies $q\geq\Omega(k^{7}\log\frac{k}{\delta})$. Then, with probability at least $1-\delta$ over the initialization, there exists $t\leq T$ such that:

Proof of Theorem 1

Let $\mathcal{L}_{A}({\mathbf{w}}):=L_{{\cal D}_{A}^{(1)}}(\left\langle\Psi({\mathbf{x}}),{\mathbf{w}}\right\rangle)$ and define the objective $G_{A}({\mathbf{w}}):=\mathcal{L}_{A}({\mathbf{w}})+\frac{\lambda}{2}\left\|{\mathbf{w}}\right\|^{2}$. Observe that for every $i\in[N]$ we have:

Since $\{f_{A}\}_{A\subseteq[n]}$ is a Fourier basis, we have:

Where we use the fact that $\binom{n}{k}\geq(n/k)^{k}\geq 16^{k}$. Using Jensen inequality we get:

Note that $G_{A}$ is $\lambda$-strongly convex, and therefore, for every ${\mathbf{w}},{\mathbf{u}}$ we have:

Let ${\mathbf{w}}^{*}_{A}:=\arg\min_{\mathbf{w}}G_{A}({\mathbf{w}})$, and so $\nabla G_{A}({\mathbf{w}}^{*}_{I})=0$. Using the above we get:

Now, notice that $\mathcal{L}_{A}$ is $\sqrt{N}$-Lipschitz, since:

Denote $\hat{{\mathbf{w}}}_{A}=\arg\min_{\left\|{\mathbf{w}}\right\|\leq B}\mathcal{L}_{A}({\mathbf{w}})$, and by optimality of ${\mathbf{w}}^{*}_{A}$ we have:

Taking an expectation and plugging in (1) we get:

Since this is true for all $\lambda$, taking $\lambda=\frac{\sqrt{2N}}{2^{k}B}$ we get:

Therefore, there exists some $A\subseteq[n]$ with $\left\lvert A\right\rvert=k$ such that $\min_{h\in\mathcal{H}_{\Psi}^{B}}L_{{\cal D}_{A}^{(1)}}(h)\geq 1-\frac{\sqrt{2N}B}{2^{k}}$. Since ${\cal D}_{A}=\frac{1}{2}{\cal D}_{A}^{(1)}+\frac{1}{2}{\cal D}_{A}^{(2)}$ we get the required. ∎

Proof of Theorem 2

We start by giving a rough sketch of the proof of Theorem 2. We divide the proof into two steps:

First gradient step. We show that after the first gradient step, there is a subset of “good” neurons in the first layer that approximately implement the function $\psi_{j}({\mathbf{x}}):=\sigma(\tau_{j}\sum_{i\in A}x_{i}+b_{j})$, for some $\tau_{j}$ and $b_{j}$. Indeed, observe that the correlation between every bit outside the parity and the label is zero, and so the gradient with respect to this bit becomes very small. However, for the bits in the parity, the correlation is large, and so the gradient is large as well.

Convergence of online gradient-descent. Notice that the parity can be implemented by a linear combination of the features $\psi_{1}({\mathbf{x}}),\dots,\psi_{q^{\prime}}({\mathbf{x}})$, when $\tau_{1},\dots,\tau_{q^{\prime}}$ are distributed uniformly. Hence, from the previous argument, after the first gradient step there exists some choice of weights for the second layer that implements the parity (and hence, separates the distribution). Now, we show that for a sufficiently large network and sufficiently small learning rate, the weights of the first layer stay close to their value after the first iteration. Thus, a standard analysis of online gradient-descent shows that gradient-descent (on both layers) reaches a good solution.

In the rest of this section, we give a detailed proof, following the above sketch. For lack of space, some of the proofs for the technical lemmas appear in the appendix.

We want to show that for some “good” neurons, the weights ${\mathbf{w}}_{i}^{(1)}$ are close enough to $\tau_{i}\sum_{j\in A}e_{j}$ for some constant $\tau_{i}$ depending on $u_{i}^{(0)}$. We start by showing that the irrelevant coordinates ($j\notin A$) and the bias have very small gradient. To do this, we first analyze the gradient with respect to the uniform part of the distribution $\mathcal{D}_{A}^{(1)}$, and show that it is negligible, with high probability over the initialization of a neuron:

Using a union bound on the previous lemma, we get that the above result holds for all irrelevant coordinates (and the bias), with constant probability:

of Lemma 4. Choose $c=C(n-1)$ and use union bound on the result of Lemma 3 over all choices of $j\notin A$ and the bias. ∎

Now, we show that for neurons with $\sum_{j\in A}w_{i}=0$, the gradient of the irrelevant coordinate and the bias is zero on the distribution $\mathcal{D}_{A}^{(2)}$ (the non-uniform part of the distribution $\mathcal{D}_{A}$):

Combining the above lemmas implies that for some “good” neurons, the gradient on the distribution $\mathcal{D}_{A}$ is negligible, for the irrelevant coordinates and the bias. Now, it is left to show that for the coordinates of the parity ($j\in A$), the gradient on the distribution $\mathcal{D}_{A}$ is large. To do this, we show that the gradient on the relevant coordinate is almost independent from the gradient of the activation function. Since the gradient with respect to the hinge-loss at the initialization is simply the correlation, this is sufficient to show that the gradient of the relevant coordinates is large.

From all the above, we get that with non-negligible probability, the weights of a given neuron are approximately $\alpha_{i}\sum_{j\in A}e_{j}$, for some choice of $\alpha_{i}$ depending on $u_{i}^{(0)}$:

Assume $n\geq 9\log 7$ and $7\leq k\leq\frac{1}{2\sqrt{2}}\sqrt{n}$. Fix some $i\in[q]$. Then, with probability at least $\frac{1}{14\sqrt{k}}$ over the choice of ${\mathbf{w}}_{i}^{(0)}$, we have that: $\max_{j\in A}\left\lvert w^{(0)}_{i,j}-\frac{\alpha_{i}}{\sqrt{n}}u_{i}^{(0)}\right\rvert\leq C_{1}$, $\max_{j\notin A}\left\lvert w^{(0)}_{i,j}-\frac{\alpha_{i}}{\sqrt{n}}u_{i}^{(0)}\right\rvert\leq\frac{C_{2}}{n-1}$ and $\left\lvert b^{(1)}-b^{(0)}\right\rvert\leq\frac{C_{3}}{\sqrt{n}}$ for some universal constants $C_{1},C_{2},C_{3}$, and some $\alpha_{i}\in\left[\frac{1}{4},1\right]$ depending on ${\mathbf{w}}^{(0)}_{i}$.

Finally, we show that the features implemented by the “good” neurons can express the parity function, using a linear separator with low norm. In the next two lemmas we show explicitly what are the features that the “good” neurons approximate:

Let $b=\frac{1}{8k}$, $\alpha\in[\frac{1}{4},1]$ and $r\in\{-k,-k+2,\dots,k-2,k\}$. Denote $\phi_{r}(z)=\sigma(-\operatorname*{sign}(r)z+\left\lvert r\right\rvert))$. Let $u\sim U([-\frac{n}{k},\frac{n}{k}])$. Then, for every $\epsilon\leq kr$, with probability at least $\frac{\epsilon}{8k^{2}}$ over the choice of $u$ we have $\left\lvert\frac{\left\lvert r\right\rvert}{b}\sigma(\frac{\alpha}{n}uz+b)-\phi_{r}(z)\right\rvert\leq\epsilon$, for every $z\in[-k,k]$.

Fix $\epsilon>0$ and assume that $n\geq 9\log 7$ and $7\leq k\leq c\sqrt{\epsilon}\sqrt{n}$, for some universal constant $c$. Fix $r\in\{-k,-k+2,\dots,k-2,k\}$, $\epsilon\leq kr$ and define $\psi_{r}({\mathbf{x}})=\sigma(-\operatorname*{sign}(r)\sqrt{n}\sum_{j\in A}x_{j}+\left\lvert r\right\rvert)$. Fix some $i\in[q]$. Then, with probability at least $\frac{\epsilon}{112k^{2.5}}$ over the choice of ${\mathbf{w}}_{i}^{(0)},u_{i}^{(0)}$ then for $\widehat{\psi}_{i}({\mathbf{x}})=\frac{\left\lvert r\right\rvert}{b_{i}^{(0)}}\sigma\left(\left\langle{\mathbf{w}}_{i}^{(1)},{\mathbf{x}}\right\rangle+b_{i}^{(1)}\right)$ we have $\left\lvert\widehat{\psi}_{r}({\mathbf{x}})-\psi_{r}({\mathbf{x}})\right\rvert\leq 2\epsilon$ for all ${\mathbf{x}}\in\mathcal{X}$.

Using the above, we show that there exists a choice for the weights for the second layer that implement the parity, with high probability over the initialization:

This concludes the analysis of the first gradient step.

2 Convergence of Gradient-Descent

Our main result in this part relies on the standard analysis of online gradient-descent. Specifically, this analysis shows that performing gradient-descent on a sequence of convex functions reaches a set of parameters that competes with the optimum (in hindsight). We give this result in general, when we optimize the functions $f_{1},\dots,f_{t}$ with respect to the parameter $\theta$:

(Online Gradient Descent) Fix some $\eta$, and let $f_{1},\dots,f_{T}$ be some sequence of convex functions. Fix some $\theta_{1}$, and assume we update $\theta_{t+1}=\theta_{t}-\eta\nabla f_{t}(\theta_{t})$. Then for every $\theta^{*}$ the following holds:

Note that in the previous part we showed that the value of the weights of the first layer is “good” with high probability. In other words, optimizing only the second layer after the first gradient step is sufficient to achieve a good solution. However, since we optimize both layers with gradient-descent, we need to show that the weights of the first layer stay close to their value after the first initialization. We start by bounding the weights pf the second layer after the first iteration:

Assume $\eta_{1}=1$ and $\lambda_{1}=\frac{1}{2}$. Then for every $i\in[q]$ we have $\left\lvert u^{(1)}_{i}\right\rvert\leq\frac{k}{\sqrt{n}}$.

Using this, we can bound how much the first layer changes after at every gradient-step:

Assume that $\eta_{1}=1,\lambda_{1}=\frac{1}{2}$ and $\eta_{t}=\eta,\lambda_{t}=\lambda$ for every $t>1$, for some fixed value $\eta,\lambda\in[0,\frac{1}{2}]$. For every $t$ and every $i\in[2q]$ we have $\left\lvert u_{i}^{(t)}\right\rvert\leq+6\eta t+\frac{k}{\sqrt{n}}$, $\left\|{\mathbf{w}}_{i}^{(t)}-{\mathbf{w}}_{i}^{(1)}\right\|\leq 6\eta^{2}t^{2}+\eta t\frac{k}{\sqrt{n}}2\eta t\lambda\frac{n}{k}t$ and $\left\lvert b_{i}^{(t)}-b_{i}^{(1)}\right\rvert\leq 6\eta^{2}t^{2}+\eta t\frac{k}{\sqrt{n}}$.

Using the above we bound the difference in the loss between optimizing the first layer and keeping it fixed, for every choice of ${\mathbf{u}}^{*}$ for the second layer:

Finally, using all the above we can prove our main theorem:

Using Lemma 14 we get that for every $t$ we have:

From this, there exists some $2\leq t\leq T+1$ such that:

And since the hinge-loss upper bounds the zero-one loss, we get the required. ∎

Experiment

In section 3 we showed a family of distributions ${\cal F}$ that separates linear classes from neural-networks. To validate that our theoretical results apply to a more realistic setting, we perform an experiment that imitates the parity problem using the MNIST dataset. We observe the following simple task: given a strip with $k$ random digits from the MNIST dataset, determine whether the sum of the digits is even or odd. We compare the performance of a ReLU network with one hidden-layer, against various linear models.

In the case where $k=1$, the MNIST-parity task is just a simplified version of the standard MNIST classification task, where instead of $10$ classes there are only $2$ classes of numbers. In this case, we observe that both the neural-network model and the linear models obtain similar performance, with only slight advantage to the neural-network model. However, when $k=3$, the task becomes much harder: it is not enough to merely memorize the digits and assign them to classes, as the model needs to compute the parity of their sum. In this case, we observe a dramatic gap between the performance of the ReLU network and the performance of the linear models. While the ReLU network achieves performance of almost $80\%$ accuracy, the linear models barely perform better than a chance. The results of the experiment are shown in Figure 1.

In the MNIST-parity experiment we train a neural-network model, as well as various linear models, to predict the parity of the sum of digits in the strip. Our neural-network architecture is a one-hidden layer network with ReLU activation and $512$ neurons in the hidden layer. We compare this network to a network of a similar architecture, except that we force the network to stay in the regime of the linear approximation induced by the network’s gradient - i.e., the neural-tangent-kernel (NTK) regime . To do this, we use an architecture that decouples the gating from the linearity of the ReLU funcion, and keeps the gates fixed throughout the training process (as suggested in ). Namely, we use the fact that: $\textrm{ReLU}(\left\langle{\mathbf{w}},{\mathbf{x}}\right\rangle)=\left\langle{\mathbf{w}},{\mathbf{x}}\right\rangle\cdot\mathbf{1}\{\left\langle{\mathbf{w}},{\mathbf{x}}\right\rangle\}$, and by decoupling the first and second term during the optimization, we force the network to stay in the NTK regime. We compare these architectures to standard random-features models, where we randomly initialize the first layer, but train only the second layer. Such models are known to be an efficient method for approximating kernel-SVM (see ). We use both ReLU random-features (standard random initialization with ReLU activation), and Gaussian random features, which approximate the RBF kernel. Both models have 512 features in the first layer. All models are trained with AdaDelta optimizer, for 20 epochs, with batch size 128.

Discussion and Future Work

In this work we showed exponential separation between learning neural networks with gradient-descent and learning linear models - i.e., learning linear separators over fixed representation of the data. This shows that learning neural networks is a strictly stronger learning model than any linear model, including linear classifiers, kernel methods and random features. In other words, neural networks are not just “glorified” kernel methods, as might be implied from previous works in the field. This demonstrates that our current understanding of neural networks learning is very limited, as only a few works so far have given positive results beyond the linear case.

There are various open questions which we leave for future work. The first immediate research direction is to find other distribution families that are learnable with neural networks via gradient-descent, but not using linear models. Another interesting question is finding distribution families with separation between deep and shallow networks. Specifically, finding a family of distributions that are learnable with gradient-descent using depth-three networks, but cannot be learned using depth-two networks. Finally, we believe that understanding the behavior of neural networks trained on specific “non-linear” distribution families will allow us to induce specific properties of the distributions that make them learnable using neural networks. Characterizing such distributional properties is another promising direction for future research.

Broader Impact

As the primary focus of this paper is on theoretical results and theoretical analysis, a Broader Impact discussion is not applicable.

References

Appendix A Additional Proof Details

of Lemma 3. Fix some ${\mathbf{w}}$. Denote $h({\mathbf{x}})=x_{j}\cdot\sigma^{\prime}({\mathbf{w}}^{\top}{\mathbf{x}}+b>0)$. Let $A^{\prime}\subseteq[n]$ be some subset with $\left\lvert A^{\prime}\right\rvert=k$ and $j\notin A^{\prime}$.

Since the above holds for all ${\mathbf{w}}$, we get that:

Fix some $A^{\prime}\subseteq[n]$ (with $\left\lvert A^{\prime}\right\rvert=k$ and $j\notin A^{\prime}$), and observe that, from symmetry to permutations of the uniform distribution, we have:

of Lemma 5. W.l.o.g., assume $A=[k]$ and $j=k+1$. We will show that the conclusion of the lemma is true even if we condition of the value of $x_{k+1},\ldots,x_{n}$. Indeed, in that case the conditional expectation of $x_{j}f({\mathbf{x}})\cdot\sigma^{\prime}({\mathbf{w}}^{\top}{\mathbf{x}}+b>0)$ is

Similarly, the conditional expectation of $f({\mathbf{x}})\cdot\sigma^{\prime}({\mathbf{w}}^{\top}{\mathbf{x}}+b>0)$ is

of Lemma 6. Fix some $y\in\{\pm 1\}$. Denote $\hat{S}$ to be the random variable $\hat{S}:=\sum_{j\notin A}w_{j}x_{j}=\sum_{j\in J}w_{j}x_{j}$. Notice that for every $y\in\{\pm 1\}$, the following holds:

Since the above is true for every $y\in\{\pm 1\}$, we get that:

of Lemma 7. Denote ${\mathbf{w}}:={\mathbf{w}}^{(0)}_{i}$, $b:=b^{(0)}_{i}$. We show that with probability at least $\frac{1}{14\sqrt{k}}$ over the choice of ${\mathbf{w}}_{i}^{(0)}$ we have:

$\left\lvert J\right\rvert:=\left\lvert\{j\in[n]\setminus A~{}:~{}w_{j}\neq 0\}\right\rvert\geq\frac{n-k}{3}$

We start by calculating the probability to get each of the above separately:

From Lemma 4, this holds with probability at least $1-\frac{1}{14\sqrt{k}}$.

Now, conditioning on the event that $\left\lvert A_{0}\right\rvert$ is odd, we have:

All in all, we get that 2 holds with probability at least $\frac{1}{6\sqrt{k}}$.

To calculate the probability that both 1,2 and 3 hold, note that 2 and 3 are independent, and therefore the probability that both of them hold is at least $\frac{1}{7\sqrt{k}}$. Using the union bound we get that the probability that all 1-3 hold is at least $\frac{1}{14\sqrt{k}}$.

Now, we assume that the above hold. In this case we have:

Where we use the result of Lemma 5 and the above conditions. Now, for all $j\in[n]$ we have:

So, denote $h({\mathbf{x}})=\sqrt{n}x_{j}f_{A}({\mathbf{x}})$ and note that for every $j\in A$ we get $h({\mathbf{x}})\equiv 1$. So, from Lemma 6 we get that for every $j\in A$ we have:

of Lemma 9. From Lemma 7, with probability at least $\frac{1}{14\sqrt{k}}$ over the choice of ${\mathbf{w}}_{i}^{(0)}$, we have that: $\max_{j\in A}\left\lvert w^{(0)}_{i,j}-\frac{\alpha_{i}}{\sqrt{n}}u_{i}^{(0)}\right\rvert\leq C_{1}$, $\max_{j\notin A}\left\lvert w^{(0)}_{i,j}-\frac{\alpha_{i}}{\sqrt{n}}u_{i}^{(0)}\right\rvert\leq\frac{C_{2}}{n-1}$ and $\left\lvert b^{(1)}-b^{(0)}\right\rvert\leq\frac{C_{3}}{\sqrt{n}}$ for some universal constants $C_{1},C_{2},C_{3}$, and some $\alpha_{i}\in\left[\frac{1}{4},1\right]$ depending only on ${\mathbf{w}}^{(0)}_{i}$. From Lemma 8, with probability at least $\frac{\epsilon}{8k^{2}}$ over the choice of $u_{i}^{(0)}$ (and independently of the choice of ${\mathbf{w}}_{i}^{(0)}$), we have $\left\lvert\frac{\left\lvert r\right\rvert}{b_{i}^{(0)}}\sigma(\frac{\alpha}{n}u_{i}^{(0)}z+b_{i}^{(0)})-\phi_{r}(z)\right\rvert\leq\epsilon$ for every $z\in[-k,k]$.

Assume the results of both lemmas hold, which happens with probability at least $\frac{\epsilon}{112k^{2.5}}$. Now, fix some ${\mathbf{x}}\in\mathcal{X}$ and let $z=\sqrt{n}\sum_{j\in A}x_{j}\in[-k,k]$. Then we have:

For some universal constant $C_{4}$. Using the assumption on $k$ concludes the proof. ∎

of Lemma 10. Fix some $r\in\{-k,-k+2,\dots,k-2,k\}$. Let $\epsilon=\frac{1}{10k}$, and from Lemma 9, with probability at least $\frac{1}{1120k^{3.5}}$ over the choice of ${\mathbf{w}}_{i}^{(0)},u_{i}^{(0)}$ we have:

Assume $q\geq 2\cdot 1120^{2}k^{7}\log(\frac{k+1}{\delta})$. Denote $I_{r}=\{i\in[q]~{}:~{}\left\lvert\widehat{\psi}_{i}({\mathbf{x}})-\psi_{r}({\mathbf{x}})\right\rvert\leq\frac{1}{10k}\}$. Denote $p:=\frac{1}{1120k^{3.5}}$, and using Hoeffding’s inequality, with probability at least $1-\exp\{-\frac{p^{2}}{2}q\}\geq 1-\frac{\delta}{k+1}$ we have $\left\lvert I_{r}\right\rvert\geq\frac{p}{2}q$. Therefore, using the union bound we get that with probability at least $1-\delta$, for every $r\in\{-k,-k+2,\dots,k-2,k\}$ we have $\left\lvert I_{r}\right\rvert\geq\frac{p}{2}q$. Let $J_{r}\subset I_{r}$ be some subset of size $\left\lvert J_{r}\right\rvert=\frac{p}{2}q$. Define:

Observe that $\sum_{r}(-1)^{\frac{k-r}{2}}v_{r}\psi_{r}({\mathbf{x}})=f_{A}({\mathbf{x}})$. Therefore, we have that:

Now, we have $\left\lvert u_{i}\right\rvert\leq\frac{2}{pq}10(k+1)k\leq\frac{Bk^{5.5}}{q}$ where $B$ is a universal constant. Therefore, we get that $\left\|{\mathbf{u}}^{*}\right\|\leq\sqrt{\frac{q(k+1)}{2240k^{2}}}\cdot\frac{Bk^{5.5}}{q}=B^{\prime}\frac{k^{5}}{\sqrt{q}}$. From what we showed, such ${\mathbf{u}}^{*}$ achieves the required. ∎

of Theorem 11. We follow an analysis similar to . Let $R_{t}(\theta)=\sum_{i=1}^{t}\left\langle\theta,\nabla f_{i}\right\rangle+\frac{1}{2\eta}\left\|\theta\right\|^{2}$, and notice that $\arg\min_{\theta}R_{t}=-\eta\sum_{i=1}^{t}\nabla f_{i}=\theta_{t+1}-\theta_{1}$. We show by induction that for every $\theta^{*}$ we have:

since $\theta_{2}-\theta_{1}$ minimizes $R_{1}$. Now, assume the above is true for $T-1$, then we have:

And by adding $\left\langle\theta_{T+1}-\theta_{1},\nabla f_{T}(\theta_{T})\right\rangle$ to both sides we get:

Using Cauchy-Schwartz inequality and rearranging the above yields:

Finally, from convexity of $f_{t}$ we get:

of Lemma 12. W.l.o.g., assume $A=[k]$. Denote $I_{even}:=\{{\mathbf{z}}\in\{\pm\frac{1}{\sqrt{n}}\}^{k}~{}:~{}\prod_{i}z_{i}>0\}$ and $I_{odd}:=\{{\mathbf{z}}\in\{\pm\frac{1}{\sqrt{n}}\}^{k}~{}:~{}\prod_{i}z_{i}<0\}$. Notice that since $k$ is odd, we have $I_{odd}=-I_{even}$. From the symmetric initialization we have $g^{(0)}\equiv 0$. By definition of the gradient-updates, we have:

And since $\sigma$ is $1$-Lipschitz we get:

Where we use the fact that $\sigma$ is $1$-Lipschitz. ∎

of Lemma 13. From Lemma 12 we have that $\left\lvert u_{i}^{(1)}\right\rvert\leq\frac{k}{\sqrt{n}}$. For every $t>1$:

of Lemma 14. Denote the support of $u^{*}$ by $I:=\{i\in[2q]~{}:~{}u_{i}^{*}\neq 0\}$. Then we have: