This is a review of work by Omar Shamir et al. on the difficulty of learning parity with gradient descent. Namely, the papers Distribution-Specific Hardness of Learning Neural Networks (DSHLNN) and Failures of Gradient-Based Deep Learning (FGBDL).

Together, DSHLNN and FGBDL cover much more than the hardness of learning parity, so the purpose of this piece is twofold.

1. To give a slimmed-down version of the papers containing only the parity result.
2. To give a version without a page limit, with all the steps explicit.

Lemma 1, Lemma 3, and Lemma 4 are also left as exercises for the reader, so I've filled those in. Any illusion of intelligence found here should be credited to the authors.

Background

Let's start by considering worst-case complexity of learning a parity function from examples. The parity functions in this piece take as input a bit string, pick a subset of the bits, then return $-1$ if the number of $1$s in the subset is odd and $1$ otherwise. Formally, the family of parity functions is

where $\langle v, x\rangle\coloneqq\Sigma_{i=1}^nv_ix_i$ is the inner product and $n$ is the input length.

Our task is, given an unknown $h\in\mathcal{H}$ and set of examples $\{(x^{(i)},h(x^{(i)}))\mid 0\leq i < t\}$, to determine the value of $h$. In the worst case, this takes $t>2^{n-1}$ examples. Because, letting $x^{(i)}_j$ denote the $j$th element of $x^{(i)}$, consider the case where $\exists j\forall i, x^{(i)}_j=0$. In this case, letting $h=x\mapsto(-1)^{\langle v, x\rangle}$ and $v'$ be the element of $[2]^n$ satisfying $v'_k\neq v_k\leftrightarrow j=k$, for $h'=x\mapsto(-1)^{\langle v', x\rangle}$ we have

As $h$ and $h'$ output the same value on every example input, it is ambiguous which is the true function based on our examples. There is a set of examples of size $[2]^{n-1}$ satisfying $\exists j\forall i, x^{(i)}_j=0$, so in the worst case learning $h$ takes $t>2^{n-1}$ examples.

Shamir's work shows, even when the examples are drawn from a nice distribution (i.e. don't have the $\exists j\forall i, x^{(i)}_j=0$ property), gradient descent can take an exponential (in $n$) number of steps to learn some $h\in\mathcal{H}$. In my view, the star of the show is Theorem 1, which establishes when the gradient of the loss is similar for all elements of $\mathcal{H}$, the gradient carries little information about what element of $\mathcal{H}$ should actually be learned. This small ``signal'' is then lost in noise from finite precision arithmetic and sampling.

Gradient Descent

In the typical machine learning setting, for some target function $h:\mathbb{R}^n\rightarrow\mathbb{R}^m$ and neural network architecture $p_w$ parameterized by weights $w\in\mathbb{R}^{|w|}$ we'd like to compute

where $F_h(w)$ is the expected loss given a choice of $w$.

One approach is to use a variation of gradient descent. This starts by selecting an initial value for $w$, call it $w^{(0)}$, then procedures to iteratively update the weights according to the formula

where $\eta$ is the learning rate. Intuitively, this works because $(\frac{\partial}{\partial w}F_h)(w^{(i)})$ is an element of $\mathbb{R}^{|w|}$ pointing in the direction of steepest increase of $\mathbb{E}_x\|h(x)-p_w(x)\|^2$, i.e. the loss. By inverting and subtracting this value from $w_i$ we move the weights in a direction that decreases the loss.

In practice, computing $\mathbb{E}_x\|h(x)-p_w(x)\|^2$, and in turn $\frac{\partial}{\partial w}F_h$, is computationally infeasible, as $x$'s distribution is unknown. As such, the standard approach is to sample $x_1,x_2,\dots,x_t$ and approximate $F_h(w)$ as

$\frac{\partial}{\partial w}F_h$ can be approximated in turn, and gradient descent run using the approximation.

Approximate Gradient Descent

We'll model this approximation with two definitions, approximate gradient oracles capture the error involved in computing $\frac{\partial}{\partial w}F_h$ and approximate gradient-based methods use these approximations.

Parity Hardness

Now, consider a family of functions $\mathcal{H}=\{h_1,h_2,\dots\}$ and the variance of the gradient at $w$ with respect to any $h\in\mathcal{H}$.

To show parity is difficult to learn, we'll show when $\mathcal{H}$ is the family of parity functions, this variance is exponentially small w.r.t. the length of the parity function's inputs. In turn, an adversarial approximate gradient oracle can repeatedly return $\mathbb{E}_{h'}((\frac{\partial}{\partial w}F_{h'})(w))$ instead of $(\frac{\partial}{\partial w}F_h)(w)$ while staying within its $\epsilon$ error tolerance. Because $\mathbb{E}_{h'}((\frac{\partial}{\partial w}F_{h'})(w))$ is independent of the $h\in\mathcal{H}$ being learned, an approximate gradient-based method using this adversarial oracle can converge to a value independent of the target function, $h$, unless it takes an exponentially large number of steps.

Proof. By Chebyshev's inequality and the hypothesis, we have

So, consider the adversarial approximate gradient oracle

Using our Chebyshev inequality, we can bound the likelihood of $O_{F_h,\epsilon}$'s $\text{otherwise}$ case.

Because $\mathbb{E}_h((\frac{\partial}{\partial w}F_h)(w))$ is independent of what $h$ is being learned, the inequality above bounds the likelihood $O_{F_h,\epsilon}(w)$ is dependent on $h$.

Now, for any approximate gradient-based method learning $h\in\mathcal{H}$, $w^{(0)}$ is independent of $h$, as nothing has been sampled from the gradient when it is chosen. As

evidently, $w^{(1)}$ is dependent on the $h$ being learned if $O_{F_h,\epsilon}(w^{(0)})$ is, and, per the inequality above, the likelihood of this is $\leq\epsilon$. Repeating this argument, let $A^{(i)}$ be the event $O_{F_h,\epsilon}(w^{(i)})$ is dependent on $h$. We have $\mathbb{P}(A^{(i)})\leq\epsilon$, so by the union bound

If $\mathbb{P}(\bigvee_{i=1}^IA^{(i)})<1$, then there is an $I$ step run of our gradient-based method where $w^{(I)}$ is independent of the target function, $h$. Solving for $I$ using the equation above gives the desired bound: If $I<1/\epsilon$, then there is a run of the gradient-based method where $w^{(\lfloor \epsilon^{-1} \rfloor)}$ is independent of $h$ (I am simplifying somewhat here because for the case we're interested $\epsilon^{-1}$ will not be an integer and flooring gives the strict $<$ inequality we want, but if you're feeling picky $I=\lceil \epsilon^{-1}\rceil -1$ will do).

$\blacksquare$

Proof. Shamir wordlessly invokes this, but it took me several hours on an airplane and help from ChatGPT to see. By induction on $d$. When $d=2$,

For the inductive step,

$\blacksquare$

Proof.

$\blacksquare$

Proof. Notice $g(a)\coloneqq\mathbb{E}_x\|f(x)-a\|^2$ is (strictly) convex, so the value of $a$ satisfying $(\frac{\partial}{\partial a}g)(a)=0$ is a global minimum. Computing this derivative and solving gives $a=\mathbb{E}_x(f(x))$, as desired. This corresponds to the intuitive idea that the mean minimizes the expected difference between it and all other values.

$\blacksquare$

Proof. Intuitively, this says that projecting $x$ onto an orthonormal basis won't increase its size.Let $a_i$ be $\langle x, e_i\rangle$ and $y$ be $\Sigma_{i\in I}a_i e_i$, i.e. $y$ is the projection of $x$ onto the basis formed by $\{e_i\mid i\in I\}$, and $a_i$ is the component of $x$ lying on the $i$th element of the basis. Now, let the residual $r$ be $x-y$ and note $r$ is perpendicular to each $e_i$

In turn, $r$ is perpendicular to $y$,

So, because $x=y+r$ and $y$ and $r$ are perpendicular, by Pythagoras',

$\blacksquare$

Proof. First, invoking Lemma 3 with $a=\mathbb{E}_{x}(p_w(x)(\frac{\partial}{\partial w}p_w)(x))$, we have

Next, note

So, using Lemma 2 to invoke Lemma 4 we get the desired bound.

$\blacksquare$

Theorem 2 bounds the variance of the gradient of the family of parity functions, so together with Theorem 1 we get our goal result on the hardness of learning parity. For another cool use of Theorem 1 see Intractability of Learning the Discrete Logarithm with Gradient-Based Methods by Takhanov et. al..

Conclusion

This is a subtle result. For example, consider the family of functions,

As these differ only by a constant factor, the variance of their gradient trivially satisfies Theorem 1. In turn, in the worst case gradient descent might converge to a value independent of the target function unless we take an exponential number of steps! But this actually isn't so bad in practice, because the functions are so similar that following $\mathbb{E}_{g\in\mathcal{G}}((\frac{\partial}{\partial w}F_g)(w))$ will likely yield a good approximation.

In turn, saying Theorem 1 and Theorem 2 give a result about the ``hardness'' of learning parity requires subtle assumptions. Really the result is, unless we take an exponential number of steps, gradient descent might converge to a value independent of the target element of $\mathcal{H}$. For parity, this is probably reasonable, because unlike $\mathcal{G}$ parity functions are quite different.

Second, this result only applies when our neural network might converge to any element of $\mathcal{H}$. To illustrate this, in SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver by Wang et. al. they learn parity with an inductive bias by weaving the input through their model. For example, on a length-$4$ input, their model's output is

By inspection, the only two elements of $\mathcal{H}$ this can learn are the trivial case when the subset of bits considered is empty, and full-parity. In fact, there are only $16$ functions from $[2]^2\rightarrow[2]$, so in this case parity can easily be learned by brute force.