Introduction
A memorization-to-generalization transition is a hallmark of modern AI models. At early stages of training, large models typically memorize individual instances of training data. As training progresses, the models discover more abstract features and transition from relying on example-specific details to forming reusable knowledge via internal representations. This phenomenon has received substantial attention in Large Language Models, where it is typically called “grokking” [1 , 2 , 3 , 4 , 5 ] . Similar observations have been made in Diffusion Models [6 , 7 , 8 , 9 ] , and Dense Associative Memories (DenseAMs) [8 ] . Interest in this phenomenon is motivated both by practical concerns – including privacy and copyright infringement arising from the memorization of training data – and by a more fundamental question: how do individual training examples turn into generalizable knowledge encoded in a model’s weights?
Although the notion of a memorization-to-generalization transition is intuitive and widely used, it remains difficult to characterize rigorously in the context of natural datasets. The underlying rules governing natural datasets are generally unknown. Consequently, there is no canonical criterion for determining when a model has transitioned from memorizing individual training examples to learning the underlying data-generating structure. This ambiguity also makes the transition difficult to quantify as a function of the training set size.
In this paper we study this problem in a simplified setting where precise results can be found. Specifically, we study how DenseAMs learn random instances of the XORSAT problem; equivalently, how they learn low-density parity-check codes over binary variables. DenseAMs are a prominent class of energy-based models, which have super-linear (in the size of the neural network) memory storage capacity [10 ] . They generalize the Hopfield network of associative memory, which has a linear memory storage capacity [11 ] . The generic feature of this class of models is that they have a very large number of basins of attraction (possibly exponentially large in the size of the network), and, at the same time, each basin has a substantial volume. The latter property makes if possible to perform error correction by following a trajectory of the dynamical system minimizing the energy of DenseAM. To set up the problem, we sample a small number of random codewords from expander low-density parity-check (LDPC) codes [12 , 13 ] to form the training set, and ask how many samples are needed until the DenseAM learns the underlying parity-checks (constraints) of the code, rather than simply memorizing individual instances from the training set. In other words, how many training samples are needed for DenseAM to recover the true underlying generative process of the LDPC codewords?
An LDPC code is a standard method for protecting digital information from errors during transmission or storage. When transmitting a string of bits, an LDPC code adds a finite fraction of redundant bits: the role of these redundant bits is to act as parity-checks on the original bits that encoded the logical information. The code is “low-density” when each bit is involved in only a finite-number of (small) parity-checks, and in turn each small check is a constraint involving only a finite number of bits. If some bits are corrupted by noise, the receiver can use the pattern of satisfied and violated checks to infer which bits are most likely incorrect. For random LDPC codes, this procedure works with high probability when a small O ( 1 ) O(1) O ( 1 )
The beauty of LDPC codes is that their codewords form a nice algorithmic dataset – every codeword comes from a clearly defined mathematical process: in this case, finding solutions to linear equations over F 2 \mathrm{F}_2 F 2
As we will show, DenseAM is a perfect model to train on random LDPC codewords. The model is defined by an energy function, which has a huge (possibly exponential in the size of the network) number of local minima. Inference dynamics corresponds to a temporal evolution of a dynamical system decreasing the energy, and the low-energy states correspond to plausible data-points. The appealing aspect of DenseAMs is that it is possible to train them both via a self-supervised learning via the backpropagation algorithm [14 ] , and, at the same time, via simpler Hebbian-style learning rules [10 ] . The latter eliminates the complexity of training process from the main phenomenon that we focus on in this work: how sample complexity of the data drives the memorization-to-generalization transition. For this reason we adopt DenseAMs as a toy model laboratory for studying this phenomenon.
In fact, the architecture of off-the-shelf DenseAM is more or less perfectly suited for the efficient learning of XORSAT. The reason is that under Hebbian learning, the real parity-checks of the code correspond to weights in the energy function that are maintained as large during training, while false parity-checks are equally likely to be obeyed or violated. Therefore under Hebbian learning, DenseAM learns to reduce the weight on false parity-checks until eventually, the energy landscape is dominated by the true parity-checks. Far past this point (with increasing training set size), the inference dynamics described in the previous paragraph amounts to gradient descent in the underlying Hamiltonian , where each codeword is a local minimum with a large energy basin around it. Even better, we may read off the underlying rules by identifying the large weights in the learned energy function. We can, therefore, quantitatively assess exactly how long it takes for DenseAM to learn the underlying code.
Our results are foreshadowed by earlier literature. For example, a long time ago, Valiant proposed a PAC theory of approximately-learnable problems, with satisfiability problems (which include XORSAT) as a prime application [15 ] . More recently, a systematic theory of sparse Hamiltonian learning [16 , 17 , 18 , 19 ] has been developed, where it is a well-known result that only O ( log n ) O(\log n) O ( log n ) poly ( n ) \operatorname{poly}(n) poly ( n ) exp [ O ( n ) ] \exp[O(n)] exp [ O ( n )] [20 ] ; these features do not make learning the Hamiltonian itself parametrically harder! The key point is that sparse learning is capable of using the same samples to independently discover many different low-order correlations corresponding to different interactions in the Hamiltonian.
The difference between sparse learning and the Hebbian learning rule of DenseAM is that the latter is a computationally efficient algorithm, without an all-purpose guarantee that it learns the correct problem. Of particular note is that sparse learning is increasingly slow when the temperature of the sampled Gibbs state is very low. It turns out, however, that XORSAT is a very special “sparse Hamiltonian” to learn – even at zero temperature (the limit of interest for our algorithmic dataset) we may still exactly learn the Hamiltonian. To achieve the optimal O ( log n ) O(\log n) O ( log n ) [21 , 22 ] , where the authors wished to mock the distribution of solutions to a satisfiability problem, rather than learn it exactly.
With or without thresholding, we can quantitatively describe the resulting memorization-to-generalization transition undergone by DenseAM as a function of training set size. In the limit of high thresholding, there is a transition between memorization and generalization, reminiscent of the reverse code engineering problem from classical LDPC codes [23 , 24 ] . We prove that this transition is surprisingly sharp: with a sufficiently small O ( log n ) O(\log n) O ( log n ) O ( 1 ) O(1) O ( 1 ) [10 , 11 ] and is dominated by the observed patterns. After seeing sufficiently many [ poly ( n ) ] [\operatorname{poly}(n)] [ poly ( n )]
Finally, we show that this optimal performance of DenseAM in learning XORSAT persists when a small fraction of the bits in XORSAT are not shown to the AI – they are latent. Again, the simplifying structure of XORSAT makes it possible for us to very efficiently learn the underlying latent variables, analogous to sparse latent learning [25 , 26 ] .
Basics of Dense Associative Memory
We are studying models where the patterns to learn are bitstrings of length n n n n n n ( ξ 1 μ , … , ξ n μ ) (\xi_1^\mu,\ldots,\xi_n^\mu) ( ξ 1 μ , … , ξ n μ ) ξ i μ ∈ { ± 1 } \xi_i^\mu\in\{\pm1\} ξ i μ ∈ { ± 1 } i , j , … ∈ { 1 , … , n } i,j,\ldots\in\{1,\ldots,n\} i , j , … ∈ { 1 , … , n } μ , ν , … \mu,\nu,\ldots μ , ν , … ξ μ ∈ C \xi^\mu\in\mathcal{C} ξ μ ∈ C C ⊆ { ± 1 } n \mathcal{C} \subseteq\{\pm1\}^n C ⊆ { ± 1 } n E ^ : { ± 1 } N → R \hat{E} : \{\pm1\}^N \to\mathbb{R} E ^ : { ± 1 } N → R C \mathcal{C} C E ^ \hat{E} E ^
A simple proposal is to choose E ^ \hat{E} E ^ m m m [10 ] :
E ^ ( σ ) = − 1 P ∑ μ = 1 P ( ∑ i = 1 n ξ i μ σ i ) m . (1) \hat{E}(\sigma)=-\frac{1}{P}\sum_{\mu=1}^{P}\left(\sum_{i=1}^{n}\xi_i^\mu\sigma_i\right)^m. \tag*{(1)} E ^ ( σ ) = − P 1 μ = 1 ∑ P ( i = 1 ∑ n ξ i μ σ i ) m . (1) It is convenient to introduce tensor
T i 1 ⋯ i m : = 1 P ∑ μ = 1 P ξ i 1 μ ⋯ ξ i m μ . (2) T_{i_1\cdots i_m}:=\frac{1}{P}\sum_{\mu=1}^{P}\xi_{i_1}^\mu\cdots\xi_{i_m}^\mu. \tag*{(2)} T i 1 ⋯ i m := P 1 μ = 1 ∑ P ξ i 1 μ ⋯ ξ i m μ . (2) and its thresholded version
T ^ i 1 ⋯ i m = ϕ a ( T i 1 ⋯ i m ) , (3) \hat{T}_{i_1\cdots i_m}=\phi_a(T_{i_1\cdots i_m}), \tag*{(3)} T ^ i 1 ⋯ i m = ϕ a ( T i 1 ⋯ i m ) , (3) where
ϕ a ( x ) : = 1 1 − a sign ( x ) max ( 0 , ∣ x ∣ − a ) . (4) \phi_a(x):=\frac{1}{1-a}\operatorname{sign}(x)\max(0,|x|-a). \tag*{(4)} ϕ a ( x ) := 1 − a 1 sign ( x ) max ( 0 , ∣ x ∣ − a ) . (4) For later purposes, we also write
E ^ ( σ ) = − ∑ i 1 , … , i m T ^ i 1 ⋯ i m σ i 1 ⋯ σ i m , (5) \hat{E}(\sigma)=-\sum_{i_1,\ldots,i_m}\hat{T}_{i_1\cdots i_m}\sigma_{i_1}\cdots\sigma_{i_m}, \tag*{(5)} E ^ ( σ ) = − i 1 , … , i m ∑ T ^ i 1 ⋯ i m σ i 1 ⋯ σ i m , (5) where the sum over indices i 1 , … , i m i_1,\ldots,i_m i 1 , … , i m (1) , we have a = 0 a=0 a = 0
T ^ i 1 ⋯ i m = ϕ a = 0 ( T i 1 ⋯ i m ) = 1 P ∑ μ = 1 P ξ i 1 μ ⋯ ξ i m μ . (6) \hat{T}_{i_1\cdots i_m}=\phi_{a=0}(T_{i_1\cdots i_m})=\frac{1}{P}\sum_{\mu=1}^{P}\xi_{i_1}^\mu\cdots\xi_{i_m}^\mu. \tag*{(6)} T ^ i 1 ⋯ i m = ϕ a = 0 ( T i 1 ⋯ i m ) = P 1 μ = 1 ∑ P ξ i 1 μ ⋯ ξ i m μ . (6) As we will see later, it is also interesting to consider a thresholded DenseAM (TDenseAM), where parameter 0 ≤ a < 1 0\leq a<1 0 ≤ a < 1 a a a E ^ \hat{E} E ^ E ^ \hat{E} E ^
Once we have a learned energy function E ^ \hat{E} E ^ E E E [27 ] .
LDPC codes
Whether or not the DenseAM can efficiently learn will clearly depend on the choice C \mathcal{C} C C \mathcal{C} C E E E
E ( σ ) : = − ∑ i 1 , … , i m J i 1 ⋯ i m σ i 1 ⋯ σ i m . (7) E(\sigma) := - \sum_{i_1,\ldots,i_m} J_{i_1\cdots i_m}\sigma_{i_1}\cdots\sigma_{i_m}. \tag*{(7)} E ( σ ) := − i 1 , … , i m ∑ J i 1 ⋯ i m σ i 1 ⋯ σ i m . (7) Then we would want to learn T ^ i 1 ⋯ i m = J i 1 ⋯ i m \widehat{T}_{i_1\cdots i_m}=J_{i_1\cdots i_m} T i 1 ⋯ i m = J i 1 ⋯ i m J i 1 ⋯ i m J_{i_1\cdots i_m} J i 1 ⋯ i m E E E σ ∈ C \sigma\in C σ ∈ C J i 1 ⋯ i m σ i 1 ⋯ σ i m ≥ 0 J_{i_1\cdots i_m}\sigma_{i_1}\cdots\sigma_{i_m} \ge0 J i 1 ⋯ i m σ i 1 ⋯ σ i m ≥ 0 J i 1 ⋯ i m ≥ 0 J_{i_1\cdots i_m} \ge0 J i 1 ⋯ i m ≥ 0 σ i 1 ⋯ σ i m = 1 \sigma_{i_1}\cdots\sigma_{i_m}=1 σ i 1 ⋯ σ i m = 1 J i 1 ⋯ i m > 0 J_{i_1\cdots i_m}>0 J i 1 ⋯ i m > 0 [13 ] .
It is more natural to switch to a binary representation:
ξ i μ : = 1 − 2 b i μ , (8) \xi_i^\mu:= 1 - 2b_i^\mu, \tag*{(8)} ξ i μ := 1 − 2 b i μ , (8) σ i : = 1 − 2 x i . (9) \sigma_i := 1 - 2x_i. \tag*{(9)} σ i := 1 − 2 x i . (9) The ground states of E E E C C C H H H
C = { b ∈ F 2 n : H b = 0 } , (10) C = \{b \in\mathbb{F}_2^n : Hb = 0\}, \tag*{(10)} C = { b ∈ F 2 n : H b = 0 } , (10) where F 2 = { 0 , 1 } \mathbb{F}_2 = \{0,1\} F 2 = { 0 , 1 } H H H F 2 \mathbb{F}_2 F 2 J i 1 ⋯ i m ≠ 0 J_{i_1\cdots i_m}\ne0 J i 1 ⋯ i m = 0 α \alpha α
H α i = { 1 i ∈ α = { i 1 , … , i m } 0 i ∉ α . (11) H_{\alpha i} =
\begin{cases}
1 & i \in\alpha= \{i_1,\ldots,i_m\} \\
0 & i \notin\alpha
\end{cases}. \tag*{(11)} H α i = { 1 0 i ∈ α = { i 1 , … , i m } i ∈ / α . (11) By construction, notice that C C C k k k ∣ C ∣ = 2 k |C|=2^k ∣ C ∣ = 2 k
Δ B : = { 1 Δ B is even 0 Δ B is odd . (12) \Delta_{\mathrm{B}} :=
\begin{cases}
1 & \Delta_{\mathrm{B}}\text{ is even} \\
0 & \Delta_{\mathrm{B}}\text{ is odd}
\end{cases}. \tag*{(12)} Δ B := { 1 0 Δ B is even Δ B is odd . (12) In practice, we will prefer to pick a random matrix H H H J i 1 ⋯ i m J_{i_1\cdots i_m} J i 1 ⋯ i m H H H [12 ] : pick a number Δ B < m \Delta_{\mathrm{B}}<m Δ B < m H H H m m m Δ B \Delta_{\mathrm{B}} Δ B § 7.1 . A useful representation of an LDPC code is a Tanner graph (or a factor graph), depicted in Figure 1 . The Tanner graph contains nodes that are either bits or checks, with an edge between bit i i i α \alpha α H α i = 1 H_{\alpha i}=1 H α i = 1 1 Δ B \Delta_{\mathrm{B}} Δ B Δ C = m \Delta_{\mathrm{C}} = m Δ C = m n → ∞ n \to\infty n → ∞
Figure 1. Illustration of a local patch of a Tanner graph of a random code with ( Δ B , Δ C ) = ( 3 , 4 ) (\Delta_{\mathrm{B}}, \Delta_{\mathrm{C}}) = (3,4) ( Δ B , Δ C ) = ( 3 , 4 ) i i i α \alpha α
k = ( 1 − Δ B m ) n + Δ ^ B . (13) k = \left(1 - \frac{\Delta_{\mathrm{B}}}{m}\right)n + \widehat{\Delta}_{\mathrm{B}}. \tag*{(13)} k = ( 1 − m Δ B ) n + Δ B . (13) Relatedly, the number N \mathcal{N} N m m m
N = Δ B m n + O ( 1 ) . (14) \mathcal{N} = \frac{\Delta_{\mathrm{B}}}{m}n + O(1). \tag*{(14)} N = m Δ B n + O ( 1 ) . (14) There are simple, yet useful, observations about the typical weights T i 1 ⋯ i m T_{i_1\cdots i_m} T i 1 ⋯ i m { i 1 , … , i m } \{i_1,\ldots,i_m\} { i 1 , … , i m } im ( H T ) \operatorname{im}(H^{\mathsf{T}}) im ( H T )
T i 1 ⋯ i m = 1. (15) T_{i_1\cdots i_m} = 1. \tag*{(15)} T i 1 ⋯ i m = 1. (15) Otherwise, ξ i 1 μ ⋯ ξ i m μ \xi_{i_1}^{\mu}\cdots\xi_{i_m}^{\mu} ξ i 1 μ ⋯ ξ i m μ ± 1 \pm1 ± 1
E [ T i 1 ⋯ i m ] = 0 , (16) \mathbb{E}[T_{i_1\cdots i_m}] = 0, \tag*{(16)} E [ T i 1 ⋯ i m ] = 0 , (16) E [ T i 1 ⋯ i m 2 ] = 1 P . (17) \mathbb{E}\left[T_{i_1\cdots i_m}^{2}\right] = \frac{1}{P}. \tag*{(17)} E [ T i 1 ⋯ i m 2 ] = P 1 . (17) Hoeffding’s inequality implies
P ( ∣ T I ∣ > s ) ≤ 2 e − P s 2 / 2 . (18) \mathbb{P}(|T_I| > s) \leq2e^{-Ps^{2}/2}. \tag*{(18)} P ( ∣ T I ∣ > s ) ≤ 2 e − P s 2 /2 . (18) In fact, these observations explain why we should choose C C C E E E T ^ i 1 ⋯ i m \widehat{T}_{i_1\cdots i_m} T i 1 ⋯ i m (6) to be equal weight superpositions of the observed patterns. So in general, TDenseAM does not perform Hamiltonian learning; it simply measures low-order correlations between spins when drawing samples uniformly at random from C \mathcal{C} C exactly match the terms in E E E E E E
Learning random codes
Now let us describe the learning process. Here we give an intuitive and non-rigorous discussion; all scaling arguments are established rigorously in Appendix § 7.2 .
It is useful to first briefly review how the regular DenseAM (a = 0 a = 0 a = 0 [10 ] . Suppose that the number of patterns P ∼ n α P \sim n^{\alpha} P ∼ n α α < m − 1 \alpha< m - 1 α < m − 1 (1) is dominated by the actual learned patterns, in the sense that there are deep energy wells surrounding every seen pattern ξ μ \xi^{\mu} ξ μ [28 ] .) In contrast, once α > m − 1 \alpha> m - 1 α > m − 1
The story changes when we train on random codewords of an LDPC code. Now the learned energy E ^ \widehat{E} E ∼ N \sim\mathcal{N} ∼ N P P P ∼ n m / P \sim\sqrt{n^{m}/P} ∼ n m / P (15) and (17) . If P ∼ n α P \sim n^{\alpha} P ∼ n α α > m − 2 \alpha> m - 2 α > m − 2 O ( 1 ) O(1) O ( 1 )
Δ E ^ ∼ N − n m P , (19) \Delta\widehat{E} \sim\mathcal{N} - \frac{n^{m}}{P}, \tag*{(19)} Δ E ∼ N − P n m , (19) where the first positive contribution counts the number of violated parity-checks, while the second negative contribution comes from the huge energy gain from pattern alignment in (1) . Using (14) , we see that until α ≥ m − 1 \alpha\ge m - 1 α ≥ m − 1 P / n m − 1 P/n^{m-1} P / n m − 1 O ( 1 ) O(1) O ( 1 ) not simply return a seen pattern – it will at worst give an approximation of the true codeword (with a bounded fraction of errors) when initialized on an arbitrary codeword.
Next, let us turn to the opposite regime of a → 1 a \to1 a → 1 [15 ] , and to the “reverse code engineering” problem [23 , 24 ] . For simplicity in the discussion that follows, let us assume that the first shown pattern is ξ i 1 = 1 \xi_i^1 = 1 ξ i 1 = 1 m m m σ i = 1 \sigma_i = 1 σ i = 1 m m m σ i = − 1 \sigma_i = -1 σ i = − 1 ∼ n m \sim n^m ∼ n m N \mathcal{N} N (16) , each subsequent shown random codeword ξ μ \xi^\mu ξ μ E ^ \widehat{E} E N + n m 2 − P \mathcal{N} + n^m 2^{-P} N + n m 2 − P
Denote H ^ ( P ) \widehat{H}(P) H ( P ) P P P H ^ ( P ) \widehat{H}(P) H ( P ) m m m m − 2 m-2 m − 2
k ^ ( P ) : = dim ( ker H ^ ( P ) ) . (20) \widehat{k}(P) := \dim\left(\ker\widehat{H}(P)\right). \tag*{(20)} k ( P ) := dim ( ker H ( P ) ) . (20) The number of minima of E ^ \widehat{E} E 2 k ^ 2^{\widehat{k}} 2 k E ^ \widehat{E} E E ^ \widehat{E} E
We conjecture that there is a sharp transition near
P ∗ = ( m − 1 ) log 2 n . (21) P_* = (m-1)\log_2 n. \tag*{(21)} P ∗ = ( m − 1 ) log 2 n . (21) Indeed, we can show that once P > P ∗ P > P_* P > P ∗ n n n
k ^ ≈ k − n m m ! 2 − P ; (22) \widehat{k} \approx k - \frac{n^m}{m!}2^{-P}; \tag*{(22)} k ≈ k − m ! n m 2 − P ; (22) the first term k = Θ ( n ) k = \Theta(n) k = Θ ( n ) P ∗ ∼ ( m − 1 + ϵ ) log 2 n P_* \sim(m-1+\epsilon)\log_2 n P ∗ ∼ ( m − 1 + ϵ ) log 2 n ϵ > 0 \epsilon> 0 ϵ > 0
The behavior for P < P ∗ P < P_* P < P ∗ m m m m = 2 m=2 m = 2 k ^ ≈ 2 P \widehat{k} \approx2^P k ≈ 2 P P ≪ log 2 k P \ll\log_2 k P ≪ log 2 k k k k
In contrast, for m > 2 m>2 m > 2
k ^ = P − 1 + Δ ^ B (23) \widehat{k} = P - 1 + \widehat{\Delta}_{\mathrm{B}} \tag*{(23)} k = P − 1 + Δ B (23) until P ∼ ( m − 1 ) log 2 n [ 1 + o ( 1 ) ] P \sim(m-1)\log_2 n[1+o(1)] P ∼ ( m − 1 ) log 2 n [ 1 + o ( 1 )] ∼ n m 2 − P \sim n^{m2^{-P}} ∼ n m 2 − P P = ( m − 1 ) log 2 n P=(m-1)\log_2 n P = ( m − 1 ) log 2 n m = 2 m=2 m = 2 w 1 w_1 w 1 w 2 w_2 w 2 w 1 + w 2 w_1+w_2 w 1 + w 2 w 1 + w 2 w_1 + w_2 w 1 + w 2 L L L ≳ 2 − P L n m L / 2 − 2 m \gtrsim2^{-P L n^{mL/2-2m}} ≳ 2 − P L n m L /2 − 2 m P ≲ c m log 2 n P \lesssim cm \log_2 n P ≲ c m log 2 n c ≤ 1 2 c \le\frac{1}{2} c ≤ 2 1 w 1 w_1 w 1 w 2 w_2 w 2 k ^ \hat{k} k ^ (23) as long as P ≲ c m log 2 n P \lesssim cm \log_2 n P ≲ c m log 2 n (23) is related to the fact that most random codes generated by picking k ∼ log n k \sim\log n k ∼ log n [24 ] ; it is then natural that a similar fact such as (23) can persist when given random codewords. It may be a little surprising, though, that the structure of the code reveals itself so rapidly!
The dramatic change in learnability of the LDPC code is very easy to see when training a weight-m m m a → 1 a \to1 a → 1 E ^ = 0 \hat{E} = 0 E ^ = 0 k ^ = n \hat{k} = n k ^ = n k ^ ( P ) \hat{k}(P) k ^ ( P ) m = 2 m = 2 m = 2 m > 2 m > 2 m > 2 Figure 2 .
Figure 2. k ^ \hat{k} k ^ P P P a → 1 a \to1 a → 1 n = 100 n = 100 n = 100 k ^ \hat{k} k ^ P P P m = 2 m = 2 m = 2 m = 4 m = 4 m = 4 (23) is clearly visible at small P P P
The punchline is that when m > 2 m > 2 m > 2 P P P a → 1 a \to1 a → 1 k ^ → k ^ + 1 \hat{k} \to\hat{k} + 1 k ^ → k ^ + 1 n → ∞ n \to\infty n → ∞ P = P ∗ P = P_* P = P ∗ generalize beyond the training data it has seen.
This behavior is reminiscent of the grokking phenomenon seen in neural networks [1 , 2 , 3 , 4 , 5 ] : one trains a neural network on “algorithmic datasets” such as ours, and observes that first the neural network learns to reproduce training data it has seen, only “discovering” the underlying rules generating the data long after reproducing training data. In neural networks, one could either talk about such a transition upon showing more training data, or optimizing network weights on a fixed dataset; in our context, only the former makes sense. In the context of our XORSAT problem, the TDenseAM is basically guaranteed by construction to always correctly reproduce training data it has already seen. The non-trivial step in the analogue “grokking” is to generalize, which in this context amounts to correctly assigning unseen codewords (solutions) to local minima in E ^ \hat{E} E ^ Figure 2 demonstrates our analogue of this “grokking” phenomenon in the m > 2 m > 2 m > 2 E ^ \hat{E} E ^ E ^ \hat{E} E ^ E ^ \hat{E} E ^
When 0 < a ≪ 1 0 < a \ll1 0 < a ≪ 1 (18) , TDenseAM will almost surely learn the code so long as
P > 2 m a 2 log 2 n . (24) P > \frac{2m}{a^2}\log_2 n. \tag*{(24)} P > a 2 2 m log 2 n . (24) This follows directly from a sub-optimal tail bound estimate on the probability of seeing a finite fraction ≥ 1 + a 2 \ge\frac{1+a}{2} ≥ 2 1 + a exp ( O ( n ) ) \exp(O(n)) exp ( O ( n )) O ( log n ) O(\log n) O ( log n )
We directly test this transition numerically by studying the behavior of the TDenseAM when it is initialized in an unseen codeword σ n e w \sigma^{\mathrm{new}} σ new σ → σ n e w \sigma\to\sigma^{\mathrm{new}} σ → σ new E ^ \hat{E} E ^ σ e n d \sigma^{\mathrm{end}} σ end
f n e w : = 1 n min μ d H ( ξ μ , σ e n d ) . (25) f_{\mathrm{new}} := \frac{1}{n}\min_{\mu}d_{\mathrm{H}}\left(\xi^\mu,\sigma^{\mathrm{end}}\right). \tag*{(25)} f new := n 1 μ min d H ( ξ μ , σ end ) . (25) Here d H d_{\mathrm{H}} d H m m m − ξ μ -\xi^\mu − ξ μ f n e w f_{\mathrm{new}} f new f n e w f_{\mathrm{new}} f new O ( 1 ) O(1) O ( 1 ) σ n e w \sigma^{\mathrm{new}} σ new
f f l i p : = 1 n d H ( σ n e w , σ e n d ) (26) f_{\mathrm{flip}} := \frac{1}{n}d_{\mathrm{H}}\left(\sigma^{\mathrm{new}},\sigma^{\mathrm{end}}\right) \tag*{(26)} f flip := n 1 d H ( σ new , σ end ) (26) Figure 3 shows the behavior of f f l i p f_{\mathrm{flip}} f flip f n e w f_{\mathrm{new}} f new P P P a ≪ 1 a \ll1 a ≪ 1 strict memorization – just like in the a = 0 a = 0 a = 0 (24) , TDenseAM begins to efficiently generalize: E ^ \hat{E} E ^
Figure 3. The memorization-generalization transition as a function of P P P f f l i p f_{\mathrm{flip}} f flip f n e w f_{\mathrm{new}} f new ( 3 , 4 ) (3,4) ( 3 , 4 ) n = 80 n = 80 n = 80 k = 20 k = 20 k = 20 a = 0.2 a = 0.2 a = 0.2 a → 1 a \to1 a → 1
The transition is clearly much more efficient when a → 1 a \to1 a → 1 f n e w f_{\mathrm{new}} f new P = 2 P = 2 P = 2
It is plausible that right at the memorization-generalization transition, at any a a a E ^ \hat{E} E ^ Figure 3 during the regime when both f f l i p f_{\mathrm{flip}} f flip f n e w f_{\mathrm{new}} f new
Discovering latent variables
It is often believed that when studying complex data patterns, some of the relevant degrees of freedom are not directly shown to the observer. Such bits are called latent . A potential example is that visible bits correspond to the pixels in an image, while latent bits describe what the image represents. There may not be a simple, local expression for E ^ \hat{E} E ^
Amazingly, we can also use TDenseAM to efficiently learn latent variables in XORSAT. Let the first n − n ˉ n - \bar{n} n − n ˉ n ˉ \bar{n} n ˉ x i x_i x i i = 1 , … , n − n ˉ i = 1, \ldots, n - \bar{n} i = 1 , … , n − n ˉ h α h_\alpha h α α = n − n ˉ + 1 , … , n \alpha= n - \bar{n} + 1, \ldots, n α = n − n ˉ + 1 , … , n
A conservative way to discover a latent variable is to detect what we call an observable 3-shadow. In the context of LDPC codes with weight-m m m 2 m − 2 2m-2 2 m − 2
w 1 = w ‾ 2 + w ‾ 3 , (27) w_1 = \overline{w}_2 + \overline{w}_3, \tag*{(27)} w 1 = w 2 + w 3 , (27) w 2 = w ‾ 3 + w ‾ 1 , (28) w_2 = \overline{w}_3 + \overline{w}_1, \tag*{(28)} w 2 = w 3 + w 1 , (28) w 3 = w ‾ 1 + w ‾ 2 . (29) w_3 = \overline{w}_1 + \overline{w}_2. \tag*{(29)} w 3 = w 1 + w 2 . (29) Here w ‾ 1 , 2 , 3 \overline{w}_{1,2,3} w 1 , 2 , 3 m − 1 m-1 m − 1 w 1 , 2 , 3 w_{1,2,3} w 1 , 2 , 3 m m m h h h
h + w ‾ 1 = h + w ‾ 2 = h + w ‾ 3 = 0. (30) h + \overline{w}_1 = h + \overline{w}_2 = h + \overline{w}_3 = 0. \tag*{(30)} h + w 1 = h + w 2 = h + w 3 = 0. (30) The key intuition is that if we observe three such patterns, rather than only two, we have clear insight as to where the latent variable must go. If we only saw w 1 w_1 w 1 w 2 , 3 w_{2,3} w 2 , 3 w ‾ 2 , 3 \overline{w}_{2,3} w 2 , 3
We now summarize how to build a latent TDenseAM, leaving details to Appendix § 7.3 . The strategy is to run TDenseAM looking for weight-( 2 m − 2 ) (2m-2) ( 2 m − 2 ) ≤ m \leq m ≤ m ≤ m \leq m ≤ m Figure 4 .
Figure 4. Illustration of a local patch of a Tanner graph of a random code with observed (black) and latent (white) bits. The latent TDenseAM learner will detect h 1 h_1 h 1 h 1 h_1 h 1 h 2 h_2 h 2
We prove in Appendix § 7.3 that, almost surely as n → ∞ n \to\infty n → ∞ ( Δ B , Δ C ) (\Delta_B,\Delta_C) ( Δ B , Δ C ) 5 < Δ B < Δ C 5 < \Delta_B < \Delta_C 5 < Δ B < Δ C
n ‾ < γ n (31) \overline{n} < \gamma n \tag*{(31)} n < γ n (31) for some O ( 1 ) O(1) O ( 1 ) γ \gamma γ
P > 4 ( m − 1 ) α 2 log 2 n . (32) P > \frac{4(m-1)}{\alpha^2}\log_2 n. \tag*{(32)} P > α 2 4 ( m − 1 ) log 2 n . (32) In a nutshell, the proof uses the fact that locally, random codes look rather tree-like. This property of the code, more accurately called expansion, guarantees that some latent variables will always have observable 3-shadows, and that any time an observable 3-shadow is found, it comes from an actual latent variable. This also guarantees that latent TDenseAM will never introduce incorrect constraints.
The guarantee above does not rely on the latent bits being distributed randomly amongst the code; every subset of n ‾ \overline{n} n (31) . This is interesting because it means that we can even learn latent bits which are only observable after ∼ log n \sim\log n ∼ log n
Outlook
We have presented a simple and largely solvable model for how a (thresholded) dense associative memory learns on a specific algorithmic dataset – randomly chosen codewords of an expander LDPC code. This architecture first learns by memorization of observed patterns ξ μ \xi^\mu ξ μ
Although we have not explicitly verified it, it is almost certain that the models described here can easily train on corrupted LDPC codewords, and any thresholding a > 0 a > 0 a > 0 Θ ( log n ) \Theta(\log n) Θ ( log n ) [29 ] doubly-exponentially faster in EBMs than in one-hot neural networks [1 , 2 , 3 , 4 , 5 ] . Perhaps the ideas we have fleshed out in a simplified setting may prove relevant more broadly in a theory of how AI learns structured data.
Acknowledgments
We thank MPI-PKS for hospitality as this work was initiated. ChatGPT 5.5/6 Pro was used to help write codes and to assist in proving the main theorems. Codex 5.5 Medium wrote the code to make figures on small sample sizes for the main text.
Review of binary linear codes
Basic definitions
In the text that follows we will use some convenient shorthand: [ n ] = { 1 , 2 , … , n } [n]=\{1,2,\ldots,n\} [ n ] = { 1 , 2 , … , n } n n n n n n [ I ] [I] [ I ] I I I I I I m m m [ I ] = { I ⊂ [ n ] : ∣ I ∣ = m } [I]=\{I\subset[n]:|I|=m\} [ I ] = { I ⊂ [ n ] : ∣ I ∣ = m }
1 [ X ] : = { 1 X is true 0 X is false . (33) \mathbb{1}[X]:=
\begin{cases}
1 & X\text{ is true}\\
0 & X\text{ is false}.
\end{cases} \tag*{(33)} 1 [ X ] := { 1 0 X is true X is false . (33) Lastly, we will sometimes refer to a vector x ∈ F 2 n x\in\mathbb{F}_2^n x ∈ F 2 n I ⊂ [ n ] I\subset[n] I ⊂ [ n ] I : = { i ∈ [ n ] : x i = 1 } I:=\{i\in[n]:x_i=1\} I := { i ∈ [ n ] : x i = 1 } I ∈ F 2 n I\in\mathbb{F}_2^n I ∈ F 2 n
Consider a vector space V V V F 2 = { 0 , 1 } \mathbb{F}_2=\{0,1\} F 2 = { 0 , 1 } F 2 \mathbb{F}_2 F 2 V ≅ F 2 k V\cong\mathbb{F}_2^k V ≅ F 2 k
Proposition A.1: Define a matrix G ∈ F 2 k × n G\in\mathbb{F}_2^{k\times n} G ∈ F 2 k × n
V = im ( G T ) , (34) V=\operatorname{im}(G^{\mathsf{T}}), \tag*{(34)} V = im ( G T ) , (34) namely the rows of G G G V ⊂ F 2 n V\subset\mathbb{F}_2^n V ⊂ F 2 n H ∈ F 2 m × n H\in\mathbb{F}_2^{m\times n} H ∈ F 2 m × n m ≥ n − k m\ge n-k m ≥ n − k H G T = 0 HG^{\mathsf{T}}=0 H G T = 0
ker ( H ) = im ( G T ) . (35) \ker(H)=\operatorname{im}(G^{\mathsf{T}}). \tag*{(35)} ker ( H ) = im ( G T ) . (35) We will denote V = ker ( H ) V=\ker(H) V = ker ( H ) V ⊥ : = im ( H T ) V^\perp:=\operatorname{im}(H^{\mathsf{T}}) V ⊥ := im ( H T ) 2
Definition A.2 (Canonical form): By Gaussian elimination we can always find a canonical form for the generator matrix G G G H H H
G = ( I k × k A ) , (36) G = \left(I_{k \times k}\ \ A\right), \tag*{(36)} G = ( I k × k A ) , (36) H = ( A T I ( n − k ) × ( n − k ) ) , (37) H = \left(A^{\mathsf{T}}\ \ I_{(n-k) \times(n-k)}\right), \tag*{(37)} H = ( A T I ( n − k ) × ( n − k ) ) , (37) Here A A A k × ( n − k ) k \times(n-k) k × ( n − k ) H H H H H H
Useful properties
The following observation is crucial to our subsequent analysis:
Proposition A.3: Let a i ∈ F 2 n a_i \in\mathbb{F}_2^n a i ∈ F 2 n I ⊆ { 1 , … , n } : = { i : a i = 1 } I \subseteq\{1,\ldots,n\} := \{i:a_i=1\} I ⊆ { 1 , … , n } := { i : a i = 1 }
ξ I μ : = ∏ i ∈ I ξ i μ . (38) \xi_I^\mu:= \prod_{i \in I} \xi_i^\mu. \tag*{(38)} ξ I μ := i ∈ I ∏ ξ i μ . (38) Then
1 2 dim V ∑ ξ ∈ V ξ I = { 1 a ∈ V ⊥ 0 a ∉ V ⊥ . (39) \frac{1}{2^{\dim V}} \sum_{\xi\in V} \xi_I =
\begin{cases}
1 & a \in V^\perp\\
0 & a \notin V^\perp
\end{cases}. \tag*{(39)} 2 d i m V 1 ξ ∈ V ∑ ξ I = { 1 0 a ∈ V ⊥ a ∈ / V ⊥ . (39) Here ξ ∈ V \xi\in V ξ ∈ V
Proof. Observe that
ξ I = ( − 1 ) ∑ i = 1 n a i b i . (40) \xi_I = (-1)^{\sum_{i=1}^{n} a_i b_i}. \tag*{(40)} ξ I = ( − 1 ) ∑ i = 1 n a i b i . (40) If b ∈ im ( H T ) = V ⊥ b \in\operatorname{im}(H^{\mathsf{T}}) = V^\perp b ∈ im ( H T ) = V ⊥ b ⋅ a = 0 b \cdot a = 0 b ⋅ a = 0 b ∈ ker ( H ) = V b \in\ker(H) = V b ∈ ker ( H ) = V
As for the second line, if a ∉ im ( H T ) = ker ( G ) a \notin\operatorname{im}(H^{\mathsf{T}}) = \ker(G) a ∈ / im ( H T ) = ker ( G ) c ∈ V = im ( G T ) c \in V = \operatorname{im}(G^{\mathsf{T}}) c ∈ V = im ( G T ) c ⋅ b = 1 c \cdot b = 1 c ⋅ b = 1 b b b b + c b+c b + c c + ( c + b ) = b c+(c+b)=b c + ( c + b ) = b ( − 1 ) a ⋅ b + ( − 1 ) a ⋅ ( b + c ) = 0 (-1)^{a\cdot b}+(-1)^{a\cdot(b+c)}=0 ( − 1 ) a ⋅ b + ( − 1 ) a ⋅ ( b + c ) = 0
Proposition A.4: Let { w a } a = 1 q \{w_a\}_{a=1}^{q} { w a } a = 1 q F 2 n / im ( H T ) \mathbb{F}_2^n/\operatorname{im}(H^{\mathsf{T}}) F 2 n / im ( H T ) { v a } a = 1 q ⊂ ker ( H ) \{v_a\}_{a=1}^{q} \subset\ker(H) { v a } a = 1 q ⊂ ker ( H )
w a ⋅ v a ′ = δ a a ′ . (41) w_a \cdot v_{a'} = \delta_{aa'}. \tag*{(41)} w a ⋅ v a ′ = δ a a ′ . (41) Proof. First look for a v 1 v_1 v 1 w 1 ⋅ v ~ 1 = 1 w_1 \cdot\tilde{v}_1 = 1 w 1 ⋅ v ~ 1 = 1 v ~ 1 \tilde{v}_1 v ~ 1 w 1 ∈ ker ( H ) w_1 \in\ker(H) w 1 ∈ ker ( H ) v ~ a \tilde{v}_a v ~ a q q q v ~ a \tilde{v}_a v ~ a w a w_a w a w a w_a w a q q q v ~ a \tilde{v}_a v ~ a M a b M_{ab} M ab v a = M a b v ~ b v_a = M_{ab}\tilde{v}_b v a = M ab v ~ b
Random expander codes
In this subsection, we will review established facts about random expander codes [13 ] , emphasizing points which are relevant for our discussion. Its purpose is just to summarize the key properties of random codes which provide provable guarantees on efficient learning of TDenseAM for the remainder of the paper. The reader should feel free to only refer to this section as results are referenced below.
Definition A.5 ((Δ B , Δ C \Delta_B, \Delta_C Δ B , Δ C ( Δ B , Δ C ) (\Delta_B, \Delta_C) ( Δ B , Δ C ) H H H Δ C \Delta_C Δ C Δ B \Delta_B Δ B 3 Δ B \Delta_B Δ B Δ C \Delta_C Δ C B B B C C C B = { 1 , … , n } B = \{1,\ldots,n\} B = { 1 , … , n } B 0 ⊆ B B_0 \subseteq B B 0 ⊆ B
{ c ∈ C : H c b = 1 for some b ∈ B 0 } = : ∂ B 0 ⊆ C . (42) \{c \in C : H_{cb} = 1\ \text{for some } b \in B_0\} =: \partial B_0 \subseteq C. \tag*{(42)} { c ∈ C : H c b = 1 for some b ∈ B 0 } =: ∂ B 0 ⊆ C . (42) An analogous definition (with H → H T H \to H^{\mathsf{T}} H → H T
It is actually quite easy to generate these codes randomly due to a clever algorithm known as the configuration model [30 ] : one simply generates random candidate codes and rejects them if they are “bad” – this will succeed with high probability after only a finite number of attempts, even as n → ∞ n \to\infty n → ∞
Theorem A.6. Propose a ( Δ B , Δ C ) (\Delta_B, \Delta_C) ( Δ B , Δ C ) Δ B \Delta_B Δ B Δ C \Delta_C Δ C n → ∞ n \to\infty n → ∞ 1 − e − ( Δ B − 1 ) ( Δ C − 1 ) / 2 1 - e^{-(\Delta_B-1)(\Delta_C-1)/2} 1 − e − ( Δ B − 1 ) ( Δ C − 1 ) /2 [31 ] .
We will use this simple generation algorithm below to prove some very useful facts about random LDPC codes. A key property about random codes is that they are expander codes, as defined below:
Definition A.7 (Left/right-expansion): A code has ( γ , δ ) (\gamma, \delta) ( γ , δ ) B 0 ⊂ B B_0 \subset B B 0 ⊂ B ∣ B 0 ∣ < γ n |B_0| < \gamma n ∣ B 0 ∣ < γ n ∣ ∂ B 0 ∣ ≥ Δ B ( 1 − δ ) ∣ B 0 ∣ |\partial B_0| \ge\Delta_B(1-\delta)|B_0| ∣ ∂ B 0 ∣ ≥ Δ B ( 1 − δ ) ∣ B 0 ∣ ( γ , δ ) (\gamma, \delta) ( γ , δ ) ∣ ∂ C 0 ∣ ≥ Δ C ( 1 − δ ) ∣ C 0 ∣ |\partial C_0| \ge\Delta_C(1-\delta)|C_0| ∣ ∂ C 0 ∣ ≥ Δ C ( 1 − δ ) ∣ C 0 ∣ ( γ , δ ) (\gamma, \delta) ( γ , δ )
Proposition A.8 (Unique-neighbor expansion): Given a code ( B , C ) (B, C) ( B , C ) ( γ , δ ) (\gamma, \delta) ( γ , δ ) B 0 ⊂ B B_0 \subset B B 0 ⊂ B ∣ B 0 ∣ < γ n |B_0| < \gamma n ∣ B 0 ∣ < γ n ∂ u B 0 ⊂ C \partial_u B_0 \subset C ∂ u B 0 ⊂ C
connect only to a single bit in B 0 B_0 B 0
∂ u B 0 : = { c ∈ C : ∣ ∂ c ∩ B 0 ∣ = 1 } . (43) \partial_{\mathrm{u}} B_0 := \{c \in C : |\partial c \cap B_0| = 1\}. \tag*{(43)} ∂ u B 0 := { c ∈ C : ∣ ∂ c ∩ B 0 ∣ = 1 } . (43) Then
∣ ∂ u B 0 ∣ ≥ ( 1 − 2 δ ) Δ B ∣ B 0 ∣ . (44) |\partial_{\mathrm{u}} B_0| \ge(1 - 2\delta)\Delta_B|B_0|. \tag*{(44)} ∣ ∂ u B 0 ∣ ≥ ( 1 − 2 δ ) Δ B ∣ B 0 ∣. (44) Proof. The number of edges between bits in B 0 B_0 B 0 C C C Δ B ∣ B 0 ∣ \Delta_B|B_0| Δ B ∣ B 0 ∣ Definition A.7 , there are edges to Δ B ( 1 − δ ) ∣ B 0 ∣ \Delta_B(1-\delta)|B_0| Δ B ( 1 − δ ) ∣ B 0 ∣
Δ B ∣ B 0 ∣ ≥ ∣ ∂ u B 0 ∣ + 2 ( Δ B ( 1 − δ ) ∣ B 0 ∣ − ∣ ∂ u B 0 ∣ ) , (45) \Delta_B|B_0| \ge|\partial_{\mathrm{u}} B_0| + 2\left(\Delta_B(1-\delta)|B_0| - |\partial_{\mathrm{u}} B_0|\right), \tag*{(45)} Δ B ∣ B 0 ∣ ≥ ∣ ∂ u B 0 ∣ + 2 ( Δ B ( 1 − δ ) ∣ B 0 ∣ − ∣ ∂ u B 0 ∣ ) , (45) which implies (A.11).
Corollary A.9: For any x x x ∣ x ∣ ≤ γ n |x| \le\gamma n ∣ x ∣ ≤ γ n ( γ , δ ) (\gamma,\delta) ( γ , δ )
∣ H x ∣ ≥ Δ B ( 1 − 2 δ ) ∣ x ∣ . (46) |Hx| \ge\Delta_B(1-2\delta)|x|. \tag*{(46)} ∣ H x ∣ ≥ Δ B ( 1 − 2 δ ) ∣ x ∣. (46) The code distance d ≥ γ n d \ge\gamma n d ≥ γ n 4
Proof. These are immediate consequences of Proposition A.8 . Any check in ∂ u B 0 \partial_{\mathrm{u}} B_0 ∂ u B 0 ∣ H x ∣ = 0 |Hx| = 0 ∣ H x ∣ = 0 x ∈ ker ( H ) x \in\operatorname{ker}(H) x ∈ ker ( H ) x = 0 x = 0 x = 0 ∣ x ∣ > γ n |x| > \gamma n ∣ x ∣ > γ n
Corollary A.10: In the setting of Proposition A.8 , we are guaranteed that there exists b ∈ B 0 b \in B_0 b ∈ B 0 ∣ ∂ b ∩ ∂ u B 0 ∣ ≥ m |\partial b \cap\partial_{\mathrm{u}} B_0| \ge m ∣ ∂ b ∩ ∂ u B 0 ∣ ≥ m
δ < 1 + Δ B − m 2 Δ B . (47) \delta< \frac{1+\Delta_B-m}{2\Delta_B}. \tag*{(47)} δ < 2 Δ B 1 + Δ B − m . (47) Proof. From (A.11), the average number of unique-neighbor checks in ∂ B 0 \partial B_0 ∂ B 0 Δ B ( 1 − 2 δ ) \Delta_B(1-2\delta) Δ B ( 1 − 2 δ ) Δ B ( 1 − 2 δ ) > m − 1 \Delta_B(1-2\delta) > m-1 Δ B ( 1 − 2 δ ) > m − 1 ∣ ∂ b ∩ ∂ u B 0 ∣ ≥ m |\partial b \cap\partial_{\mathrm{u}} B_0| \ge m ∣ ∂ b ∩ ∂ u B 0 ∣ ≥ m
The existence of useful codes is established by the following theorem, which we state without proof, although we do note that the bound on k k k F 2 \mathbb{F}_2 F 2
Theorem A.11. Take Δ B < Δ C \Delta_{\mathrm{B}} < \Delta_{\mathrm{C}} Δ B < Δ C ( Δ B , Δ C ) (\Delta_{\mathrm{B}}, \Delta_{\mathrm{C}}) ( Δ B , Δ C ) Theorem A.6 ). Then the code has a linear number of logical bits:
k = n ( 1 − Δ B Δ C ) + { 1 Δ B even 0 Δ B odd (48) k = n\left(1-\frac{\Delta_{\mathrm{B}}}{\Delta_{\mathrm{C}}}\right) + \begin{cases} 1 & \Delta_{\mathrm{B}}\ \text{even} \\ 0 & \Delta_{\mathrm{B}}\ \text{odd} \end{cases} \tag*{(48)} k = n ( 1 − Δ C Δ B ) + { 1 0 Δ B even Δ B odd (48) and with probability 1 − O ( n 1 − δ Δ B ) 1-O(n^{1-\delta\Delta_{\mathrm{B}}}) 1 − O ( n 1 − δ Δ B ) ( γ , δ ) (\gamma,\delta) ( γ , δ ) δ > 1 / Δ B \delta> 1/\Delta_{\mathrm{B}} δ > 1/ Δ B 0 < γ < γ max 0 < \gamma< \gamma_{\max} 0 < γ < γ m a x γ max \gamma_{\max} γ m a x
( 1 − 1 Δ B ) h ( γ max ) = 1 Δ C h ( Δ C ( 1 − δ ) γ max ) + Δ C γ max h ( 1 Δ C ( 1 − δ ) ) (49) \left(1-\frac{1}{\Delta_{\mathrm{B}}}\right)h(\gamma_{\max}) = \frac{1}{\Delta_{\mathrm{C}}}h\bigl(\Delta_{\mathrm{C}}(1-\delta)\gamma_{\max}\bigr) + \Delta_{\mathrm{C}}\gamma_{\max}h\left(\frac{1}{\Delta_{\mathrm{C}}(1-\delta)}\right) \tag*{(49)} ( 1 − Δ B 1 ) h ( γ m a x ) = Δ C 1 h ( Δ C ( 1 − δ ) γ m a x ) + Δ C γ m a x h ( Δ C ( 1 − δ ) 1 ) (49) with
h ( x ) : = − x log x − ( 1 − x ) log ( 1 − x ) . (50) h(x) := -x\log x-(1-x)\log(1-x). \tag*{(50)} h ( x ) := − x log x − ( 1 − x ) log ( 1 − x ) . (50) Lastly, the following result tells us that the interaction graph of a random LDPC code does not contain very many interesting small subgraphs, with very high probability. In other words, random LDPC codes look locally tree-like.
Proposition A.12: Let G G G V 0 V_0 V 0 E 0 E_0 E 0 V 0 V_0 V 0 E 0 E_0 E 0 O ( 1 ) O(1) O ( 1 ) ( Δ B , Δ C ) (\Delta_{\mathrm{B}}, \Delta_{\mathrm{C}}) ( Δ B , Δ C ) N G N_G N G G G G n → ∞ n \to\infty n → ∞ C < ∞ C < \infty C < ∞
E [ N G ] ≤ C n V 0 − E 0 . (51) \mathbb{E}[N_G] \le C n^{V_0-E_0}. \tag*{(51)} E [ N G ] ≤ C n V 0 − E 0 . (51) In words, there are a finite number of short cycles in an LDPC code, and these cycles are all far from each other.
Proof. We can use Theorem A.6 to constrain the properties of a random LDPC code: suppose that a random pairing of bits and checks has property X X X P b a r e ( X ) \mathbb{P}_{\mathrm{bare}}(X) P bare ( X ) q = e − ( Δ B − 1 ) ( Δ C − 1 ) / 2 q=e^{-(\Delta_{\mathrm{B}}-1)(\Delta_{\mathrm{C}}-1)/2} q = e − ( Δ B − 1 ) ( Δ C − 1 ) /2
P L D P C ( X ) q + P n o t L D P C ( X ) ( 1 − q ) = P b a r e ( X ) , (52) \mathbb{P}_{\mathrm{LDPC}}(X)q+\mathbb{P}_{\mathrm{not\ LDPC}}(X)(1-q)=\mathbb{P}_{\mathrm{bare}}(X), \tag*{(52)} P LDPC ( X ) q + P not LDPC ( X ) ( 1 − q ) = P bare ( X ) , (52) meaning that
P L D P C ( X ) ≥ P b a r e ( X ) q . (53) \mathbb{P}_{\mathrm{LDPC}}(X)\ge\frac{\mathbb{P}_{\mathrm{bare}}(X)}{q}. \tag*{(53)} P LDPC ( X ) ≥ q P bare ( X ) . (53) Now, in the configuration model, it is very easy to bound the probability of seeing a subgraph G G G { 1 , … , m 0 } ⊂ B \{1,\ldots,m_0\}\subset B { 1 , … , m 0 } ⊂ B { m 0 + 1 , … , V 0 } ⊂ C 0 \{m_0+1,\ldots,V_0\}\subset C_0 { m 0 + 1 , … , V 0 } ⊂ C 0 G G G
P ( G ∼ { 1 , … , m 0 } ∪ { m 0 + 1 , … , V 0 } ) = ∏ j = 0 E 0 − 1 1 Δ B n − j < ( Δ B n − E 0 ) − E 0 . (54) \mathbb{P}\left(G \sim\{1,\ldots,m_0\}\cup\{m_0+1,\ldots,V_0\}\right)=\prod_{j=0}^{E_0-1}\frac{1}{\Delta_{\mathrm{B}}n-j}<(\Delta_{\mathrm{B}}n-E_0)^{-E_0}. \tag*{(54)} P ( G ∼ { 1 , … , m 0 } ∪ { m 0 + 1 , … , V 0 } ) = j = 0 ∏ E 0 − 1 Δ B n − j 1 < ( Δ B n − E 0 ) − E 0 . (54) Now enumerating over the total number of possible such subgraphs, we bound
E [ N G ] < n m 0 ( Δ B n − E 0 ) E 0 ( Δ B Δ C n ) V 0 − m 0 < q C n V 0 − E 0 (55) \mathbb{E}[N_G]<\frac{n^{m_0}}{(\Delta_{\mathrm{B}}n-E_0)^{E_0}}\left(\frac{\Delta_{\mathrm{B}}}{\Delta_{\mathrm{C}}}n\right)^{V_0-m_0}<qC^nV_0-E_0 \tag*{(55)} E [ N G ] < ( Δ B n − E 0 ) E 0 n m 0 ( Δ C Δ B n ) V 0 − m 0 < q C n V 0 − E 0 (55) for some C < ∞ C<\infty C < ∞
The remaining results in this section are a collection of scattered but useful facts about expander codes, which will be useful in establishing how TDenseAM trains on random codes.
Theorem A.13: Pick a ( Δ B , Δ C ) (\Delta_{\mathrm{B}},\Delta_{\mathrm{C}}) ( Δ B , Δ C ) 2 < Δ B < Δ C 2<\Delta_{\mathrm{B}}<\Delta_{\mathrm{C}} 2 < Δ B < Δ C m m m s ∈ F 2 m s\in\mathbb{F}_2^m s ∈ F 2 m
∣ s ∣ r e d : = { ∣ s ∣ Δ B odd min ( ∣ s ∣ , m − ∣ s ∣ ) Δ B even . (56) |s|_{\mathrm{red}}:=\begin{cases}
|s| & \Delta_{\mathrm{B}}\ \text{odd}\\
\min(|s|,m-|s|) & \Delta_{\mathrm{B}}\ \text{even}.
\end{cases} \tag*{(56)} ∣ s ∣ red := { ∣ s ∣ min ( ∣ s ∣ , m − ∣ s ∣ ) Δ B odd Δ B even . (56) Then almost surely as n → ∞ n\to\infty n → ∞ s s s
∣ H T s ∣ ≥ κ ∣ s ∣ r e d (57) |H^{T}s|\ge\kappa|s|_{\mathrm{red}} \tag*{(57)} ∣ H T s ∣ ≥ κ ∣ s ∣ red (57) for some O ( 1 ) O(1) O ( 1 ) κ > 0 \kappa>0 κ > 0 check soundness .
Proof. Theorem A.11 shows that the dimension of the codespace is minimal – up to a sole redundant check when Δ B \Delta_{\mathrm{B}} Δ B ∣ s ∣ r e d |s|_{\mathrm{red}} ∣ s ∣ red
The desired property follows immediately from Definition A.7 if ∣ s ∣ < γ n |s|<\gamma n ∣ s ∣ < γ n ∣ s ∣ > γ n |s|>\gamma n ∣ s ∣ > γ n Proposition A.12 . Since ∣ s ∣ > γ n |s|>\gamma n ∣ s ∣ > γ n s s s p : = Δ B γ p:=\Delta_{\mathrm{B}}\gamma p := Δ B γ K : = κ ∣ s ∣ r e d K:=\kappa|s|_{\mathrm{red}} K := κ ∣ s ∣ red odd number of edges connecting to s s s
We can use the method of generating functions to bound this. Define the odd and even parts of the binomial distribution:
B e v e n ( z ) : = ∑ j e v e n ( Δ B j ) z j , (58) B_{\mathrm{even}}(z):=\sum_{j\ \mathrm{even}}\binom{\Delta_{\mathrm{B}}}{j}z^j, \tag*{(58)} B even ( z ) := j even ∑ ( j Δ B ) z j , (58) B o d d ( z ) : = ∑ j o d d ( Δ B j ) z j . (59) B_{\mathrm{odd}}(z):=\sum_{j\ \mathrm{odd}}\binom{\Delta_{\mathrm{B}}}{j}z^j. \tag*{(59)} B odd ( z ) := j odd ∑ ( j Δ B ) z j . (59) Then define
G ( z ) : = ∑ n = 0 ∞ G n z n : = B e v e n ( z ) n − K B o d d ( z ) K . (60) G(z) := \sum_{n=0}^{\infty} G_n z^n := B_{\mathrm{even}}(z)^{n-K} B_{\mathrm{odd}}(z)^K. \tag*{(60)} G ( z ) := n = 0 ∑ ∞ G n z n := B even ( z ) n − K B odd ( z ) K . (60) In the random generating model of Theorem A.6 , we see that
P b a r e ( K odd degree bits ) = ( n K ) ( Δ B n / Δ C ∣ s ∣ ) ( Δ B n Δ C ∣ s ∣ ) − 1 G Δ C ∣ s ∣ ≤ ( n K ) ( Δ B n / Δ C ∣ s ∣ ) ( Δ B n Δ C ∣ s ∣ ) − 1 inf z ( z − Δ C ∣ s ∣ G ( z ) ) . (61) \begin{aligned}
\mathbb{P}_{\mathrm{bare}}(K\ \text{odd degree bits}) =
\binom{n}{K}
\binom{\Delta_{\mathrm{B}}n/\Delta_{\mathrm{C}}}{|s|}
\binom{\Delta_{\mathrm{B}}n}{\Delta_{\mathrm{C}}|s|}^{-1}
G_{\Delta_{\mathrm{C}}|s|} \\
&\leq
\binom{n}{K}
\binom{\Delta_{\mathrm{B}}n/\Delta_{\mathrm{C}}}{|s|}
\binom{\Delta_{\mathrm{B}}n}{\Delta_{\mathrm{C}}|s|}^{-1}
\inf_{z}\left(z^{-\Delta_{\mathrm{C}}|s|}G(z)\right). \tag*{(61)}
\end{aligned} P bare ( K odd degree bits ) = ( K n ) ( ∣ s ∣ Δ B n / Δ C ) ( Δ C ∣ s ∣ Δ B n ) − 1 G Δ C ∣ s ∣ ≤ ( K n ) ( ∣ s ∣ Δ B n / Δ C ) ( Δ C ∣ s ∣ Δ B n ) − 1 z inf ( z − Δ C ∣ s ∣ G ( z ) ) . (61) Let ∣ s ∣ = η n |s|=\eta n ∣ s ∣ = η n γ < η ≤ Δ B / Δ C \gamma<\eta\leq\Delta_{\mathrm{B}}/\Delta_{\mathrm{C}} γ < η ≤ Δ B / Δ C n → ∞ n\to\infty n → ∞
1 n log inf z ( z − Δ C ∣ s ∣ G ( z ) ) = inf z ( log B e v e n ( z ) − Δ C η log z ) . (62) \frac{1}{n}\log\inf_{z}\left(z^{-\Delta_{\mathrm{C}}|s|}G(z)\right)
=
\inf_{z}\left(\log B_{\mathrm{even}}(z)-\Delta_{\mathrm{C}}\eta\log z\right). \tag*{(62)} n 1 log z inf ( z − Δ C ∣ s ∣ G ( z ) ) = z inf ( log B even ( z ) − Δ C η log z ) . (62) Observe that B e v e n ( z ) ≤ ( 1 + z Δ B / ( Δ B − 1 ) ) Δ B − 1 B_{\mathrm{even}}(z)\leq(1+z^{\Delta_{\mathrm{B}}/(\Delta_{\mathrm{B}}-1)})^{\Delta_{\mathrm{B}}-1} B even ( z ) ≤ ( 1 + z Δ B / ( Δ B − 1 ) ) Δ B − 1
inf z ( log B e v e n ( z ) − Δ C η log z ) = ( Δ B − 1 ) inf u ( log ( 1 + u ) − Δ C η Δ B log u ) = ( Δ B − 1 ) h ( Δ C η Δ B ) , (63) \begin{aligned}
\inf_{z}\left(\log B_{\mathrm{even}}(z)-\Delta_{\mathrm{C}}\eta\log z\right)
=
(\Delta_{\mathrm{B}}-1)\inf_{u}\left(\log(1+u)-\frac{\Delta_{\mathrm{C}}\eta}{\Delta_{\mathrm{B}}}\log u\right) \\
&=
(\Delta_{\mathrm{B}}-1)h\left(\frac{\Delta_{\mathrm{C}}\eta}{\Delta_{\mathrm{B}}}\right), \tag*{(63)}
\end{aligned} z inf ( log B even ( z ) − Δ C η log z ) = ( Δ B − 1 ) u inf ( log ( 1 + u ) − Δ B Δ C η log u ) = ( Δ B − 1 ) h ( Δ B Δ C η ) , (63) recalling the definition of h ( x ) h(x) h ( x ) n → ∞ n\to\infty n → ∞
P b a r e ( K odd degree bits ) ≤ e n [ h ( κ ) − ψ ] . (64) \mathbb{P}_{\mathrm{bare}}(K\ \text{odd degree bits})\leq e^{n[h(\kappa)-\psi]}. \tag*{(64)} P bare ( K odd degree bits ) ≤ e n [ h ( κ ) − ψ ] . (64) where
ψ = [ Δ B ( 1 − 1 Δ C ) − ( Δ B − 1 ) ] h ( Δ C η Δ B ) = ( 1 − Δ B Δ C ) h ( Δ C η Δ B ) > 0. (65) \psi=
\left[
\Delta_{\mathrm{B}}\left(1-\frac{1}{\Delta_{\mathrm{C}}}\right)-(\Delta_{\mathrm{B}}-1)
\right]h\left(\frac{\Delta_{\mathrm{C}}\eta}{\Delta_{\mathrm{B}}}\right)
=
\left(1-\frac{\Delta_{\mathrm{B}}}{\Delta_{\mathrm{C}}}\right)
h\left(\frac{\Delta_{\mathrm{C}}\eta}{\Delta_{\mathrm{B}}}\right)>0. \tag*{(65)} ψ = [ Δ B ( 1 − Δ C 1 ) − ( Δ B − 1 ) ] h ( Δ B Δ C η ) = ( 1 − Δ C Δ B ) h ( Δ B Δ C η ) > 0. (65) Choose any κ \kappa κ h ( κ ) < ψ h(\kappa)<\psi h ( κ ) < ψ n → ∞ n\to\infty n → ∞
Corollary A.14. In a random ( Δ B , Δ C ) (\Delta_{\mathrm{B}},\Delta_{\mathrm{C}}) ( Δ B , Δ C ) 2 < Δ B < Δ C 2<\Delta_{\mathrm{B}}<\Delta_{\mathrm{C}} 2 < Δ B < Δ C n → ∞ n\to\infty n → ∞ im ( H T ) \operatorname{im}(H^{\mathsf{T}}) im ( H T ) Δ C \Delta_{\mathrm{C}} Δ C Δ C \Delta_{\mathrm{C}} Δ C
N m = ( 1 + o ( 1 ) ) Δ B Δ C n . (66) \mathcal{N}_m=(1+o(1))\frac{\Delta_{\mathrm{B}}}{\Delta_{\mathrm{C}}}n. \tag*{(66)} N m = ( 1 + o ( 1 )) Δ C Δ B n . (66) Proof. By Theorem A.13 , it suffices to look at small combinations of checks with ∣ s ∣ < K ′ |s|<K' ∣ s ∣ < K ′ Theorem A.11 . For any δ > 1 / Δ B \delta>1/\Delta_{\mathrm{B}} δ > 1/ Δ B ∣ H s ∣ ≥ Δ C ( 1 − 2 δ ) ∣ s ∣ |H s|\geq\Delta_{\mathrm{C}}(1-2\delta)|s| ∣ H s ∣ ≥ Δ C ( 1 − 2 δ ) ∣ s ∣ Δ B ≥ 3 \Delta_{\mathrm{B}}\geq3 Δ B ≥ 3 δ \delta δ 1 / 3 1/3 1/3 ∣ s ∣ ≥ 3 |s|\geq3 ∣ s ∣ ≥ 3
claim is established.
Thus let us discuss the case of ∣ s ∣ = 2 |s| = 2 ∣ s ∣ = 2 ∣ s ∣ = 1 |s| = 1 ∣ s ∣ = 1 Proposition A.12 . For any Δ C ≥ 4 \Delta_{\mathrm{C}} \ge4 Δ C ≥ 4 Δ C \Delta_{\mathrm{C}} Δ C Figure 1 ) isomorphic to two bits connected to ≥ 3 \ge3 ≥ 3 ≥ 3 \ge3 ≥ 3 ≥ 2 \ge2 ≥ 2 V 0 < E 0 V_0 < E_0 V 0 < E 0 Theorem A.13 ), so the probability any one of them fails vanishes as n → ∞ n \to\infty n → ∞
Finally, let us verify that the number of checks of weight Δ C \Delta_{\mathrm{C}} Δ C Θ ( n ) \Theta(n) Θ ( n ) Δ B n / Δ C \Delta_{\mathrm{B}}n/\Delta_{\mathrm{C}} Δ B n / Δ C Proposition A.12 shows that the expected number of such cycles is Θ ( 1 ) \Theta(1) Θ ( 1 ) □ \square □
Corollary A.15: In a random ( Δ B , Δ C ) (\Delta_{\mathrm{B}}, \Delta_{\mathrm{C}}) ( Δ B , Δ C ) H H H 2 < Δ B < Δ C 2 < \Delta_{\mathrm{B}} < \Delta_{\mathrm{C}} 2 < Δ B < Δ C n → ∞ n \to\infty n → ∞
N r : = ∣ { w ∈ im ( H T ) : ∣ w ∣ = r } ∣ = o ( n r / 2 ) (67) N_r := \left|\{w \in\operatorname{im}(H^{\mathsf{T}}) : |w| = r\}\right| = o\left(n^{r/2}\right) \tag*{(67)} N r := { w ∈ im ( H T ) : ∣ w ∣ = r } = o ( n r /2 ) (67) for any O ( 1 ) O(1) O ( 1 ) r r r
Proof. Again, Theorem A.11 and Theorem A.13 imply we need only worry about combinations of O ( 1 ) O(1) O ( 1 ) Δ B > 2 \Delta_{\mathrm{B}} > 2 Δ B > 2 Proposition A.12 . Suppose we have a candidate subgraph of the Tanner graph containing s s s S 0 S_0 S 0 ∈ ∂ S 0 \in\partial S_0 ∈ ∂ S 0 r r r im ( H T ) \operatorname{im}(H^{\mathsf{T}}) im ( H T ) 1 2 ( Δ C s + r ) \frac{1}{2}(\Delta_{\mathrm{C}}s+r) 2 1 ( Δ C s + r ) r r r
V 0 − E 0 = s + Δ C s + r 2 − Δ C s = ( 1 − Δ C 2 ) s + r 2 < r − 1 2 . (68) V_0 - E_0 = s + \frac{\Delta_{\mathrm{C}}s+r}{2} - \Delta_{\mathrm{C}}s = \left(1-\frac{\Delta_{\mathrm{C}}}{2}\right)s+\frac{r}{2} < \frac{r-1}{2}. \tag*{(68)} V 0 − E 0 = s + 2 Δ C s + r − Δ C s = ( 1 − 2 Δ C ) s + 2 r < 2 r − 1 . (68) By Markov’s inequality (as N G ≥ 0 N_G \ge0 N G ≥ 0 1 − n − 1 / 4 1-n^{-1/4} 1 − n − 1/4 s s s O ( n r / 2 − 1 / 4 ) O(n^{r/2-1/4}) O ( n r /2 − 1/4 ) □ \square □
Corollary A.16: In the setting of Corollary A.15 , a random codeword b ∈ ker ( H ) b \in\ker(H) b ∈ ker ( H ) n / 2 n/2 n /2
lim n → ∞ P ( ∣ ∣ b ∣ − n 2 ∣ > n 1 / 2 + ϵ ) = 0. (69) \lim_{n \to\infty} \mathbb{P}\left(\left||b|-\frac{n}{2}\right|>n^{1/2+\epsilon}\right)=0. \tag*{(69)} n → ∞ lim P ( ∣ b ∣ − 2 n > n 1/2 + ϵ ) = 0. (69) Proof. Almost surely there are no checks of weight ≤ 2 \le2 ≤ 2 ± 1 \pm1 ± 1 ξ i \xi_i ξ i
K : = ∑ i = 1 n ξ i = n − 2 ∣ b ∣ . (70) K := \sum_{i=1}^{n}\xi_i = n - 2|b|. \tag*{(70)} K := i = 1 ∑ n ξ i = n − 2∣ b ∣. (70) Proposition A.3 shows that
E [ K 2 ] = n , (71) \mathbb{E}\left[K^2\right] = n, \tag*{(71)} E [ K 2 ] = n , (71) because the only n n n im ( H T ) \operatorname{im}(H^{\mathsf{T}}) im ( H T ) ( ξ i ) 2 = 1 (\xi_i)^2=1 ( ξ i ) 2 = 1
Corollary A.17: In a random ( Δ B , Δ C ) (\Delta_{\mathrm{B}},\Delta_{\mathrm{C}}) ( Δ B , Δ C ) 2 < Δ B < Δ C 2<\Delta_{\mathrm{B}}<\Delta_{\mathrm{C}} 2 < Δ B < Δ C n → ∞ n\to\infty n → ∞ I ∈ im ( H T ) I\in\operatorname{im}(H^{\mathsf{T}}) I ∈ im ( H T ) Δ C \Delta_{\mathrm{C}} Δ C x ∈ ker ( H ) x\in\ker(H) x ∈ ker ( H )
P [ ∑ i ∈ I x i = j ] = 1 2 Δ C − 1 ( Δ C j ) I ( j is even ) . (72) \mathbb{P}\left[\sum_{i\in I}x_i=j\right]=\frac{1}{2^{\Delta_{\mathrm{C}}-1}}\binom{\Delta_{\mathrm{C}}}{j}\mathbb{I}(j\text{ is even}). \tag*{(72)} P [ i ∈ I ∑ x i = j ] = 2 Δ C − 1 1 ( j Δ C ) I ( j is even ) . (72) Proof. Corollary A.14 shows that almost surely, the only parity-check with support in I I I I I I Δ C \Delta_{\mathrm{C}} Δ C π I : F 2 n → F 2 I \pi_I:\mathbb{F}_2^n\to\mathbb{F}_2^I π I : F 2 n → F 2 I I I I π I ( ker ( H ) ) \pi_I(\ker(H)) π I ( ker ( H )) π I \pi_I π I Δ C − 1 \Delta_{\mathrm{C}}-1 Δ C − 1
W w : = { x ∈ ker ( H ) : π I ( x ) = w } , (73) W_w:=\{x\in\ker(H):\pi_I(x)=w\}, \tag*{(73)} W w := { x ∈ ker ( H ) : π I ( x ) = w } , (73) then P ( W w 1 ) = P ( W w 1 + w 2 ) \mathbb{P}(W_{w_1})=\mathbb{P}(W_{w_1+w_2}) P ( W w 1 ) = P ( W w 1 + w 2 ) y ∈ W w 2 y\in W_{w_2} y ∈ W w 2 x x x x + y x+y x + y I I I
Learning random codes
In this section, we will show that the TDenseAM architecture above learns the codewords of classical low-density parity-check (LDPC) codes efficiently.
How many training examples are needed?
We now describe how the TDenseAM trains on random codewords of a high rate LDPC code with k / n ∼ O ( 1 ) k/n\sim O(1) k / n ∼ O ( 1 )
The first key observation is that the TDenseAMs do correctly learn the underlying code. In other words, the ground states of E ^ \hat{E} E ^ P P P a = 0 a=0 a = 0 not need to see every random codeword in order to recover all of them as local minima of E ^ \hat{E} E ^
Proposition B.1. Suppose that we train the p p p a > 0 a > 0 a > 0 P P P ≤ m \le m ≤ m d > 1 d > 1 d > 1
P > 2 a 2 ( m log n + log 2 ϵ ) (74) P > \frac{2}{a^2}\left(m\log n + \log\frac{2}{\epsilon}\right) \tag*{(74)} P > a 2 2 ( m log n + log ϵ 2 ) (74) for 0 < ϵ < 1 0 < \epsilon< 1 0 < ϵ < 1 E ^ \widehat{E} E V V V 1 − ϵ 1-\epsilon 1 − ϵ
If we consider the usual dense associative memory (a = 0 a = 0 a = 0 E ^ \widehat{E} E 5
P > 8 N 2 m ( m − 1 ) ! 2 ( m log N + log 2 ϵ ) (75) P > \frac{8N^{2m}}{(m-1)!^2}\left(m\log N + \log\frac{2}{\epsilon}\right) \tag*{(75)} P > ( m − 1 ) ! 2 8 N 2 m ( m log N + log ϵ 2 ) (75) Note that the scaling in this equation is suboptimal, if our goal is to learn an accurate representation of the overall energy landscape. We return to that issue in Theorem B.12 .
Proof. We first consider the case a > 0 a > 0 a > 0 E ^ \widehat{E} E
T I : = 1 P ∑ μ = 1 P ξ I μ . (76) T_I := \frac{1}{P}\sum_{\mu=1}^{P}\xi_I^\mu. \tag*{(76)} T I := P 1 μ = 1 ∑ P ξ I μ . (76) The distribution of these random variables is straightforward to see: each T I T_I T I 1 1 1 1 1 1 I ∈ im ( H T ) I \in\operatorname{im}(H^{\mathsf{T}}) I ∈ im ( H T ) P P P 1 / P 1/P 1/ P H H H p p p H H H P P P ∣ T I ∣ < a \lvert T_I\rvert< a ∣ T I ∣ < a I ∉ im ( H T ) I \notin\operatorname{im}(H^{\mathsf{T}}) I ∈ / im ( H T ) (18) . By the union bound, the probability that we fail and find E ^ ≠ E \widehat{E} \ne E E = E m ≥ 2 m \ge2 m ≥ 2
P [ f a i l ] < m ( n m ) ⋅ 2 e − P a 2 / 2 < 2 e m log n − P a 2 / 2 < ϵ . (77) \mathbb{P}[\mathrm{fail}] < m\binom{n}{m}\cdot2e^{-Pa^2/2} < 2e^{m\log n-Pa^2/2} < \epsilon. \tag*{(77)} P [ fail ] < m ( m n ) ⋅ 2 e − P a 2 /2 < 2 e m l o g n − P a 2 /2 < ϵ . (77) In the last step, we used (B.1) to give a bound on P P P
The case of a = 0 a = 0 a = 0 N m / ( m − 1 ) ! N^m/(m-1)! N m / ( m − 1 )! ≤ m \le m ≤ m I ∉ im ( H T ) I \notin\operatorname{im}(H^{\mathsf{T}}) I ∈ / im ( H T )
T ^ I < δ 0 = ( m − 1 ) ! 2 N m , (78) \widehat{T}_I < \delta_0 = \frac{(m-1)!}{2N^m}, \tag*{(78)} T I < δ 0 = 2 N m ( m − 1 )! , (78) then we are guaranteed that only codewords are ground states of E ^ \widehat{E} E T I = 1 T_I=1 T I = 1 I ∈ im ( H T ) I\in\operatorname{im}(H^{\mathsf{T}}) I ∈ im ( H T )
E ^ state with error − E ^ codeword > ( 1 − N m ( m − 1 ) ! δ 0 ) − N m ( m − 1 ) ! δ 0 > 0 (79) \widehat{E}_{\text{state with error}}-\widehat{E}_{\text{codeword}}>\left(1-\frac{N^{m}}{(m-1)!}\delta_0\right)-\frac{N^{m}}{(m-1)!}\delta_0>0 \tag*{(79)} E state with error − E codeword > ( 1 − ( m − 1 )! N m δ 0 ) − ( m − 1 )! N m δ 0 > 0 (79) using (B.5). So we should use Hoeffding’s inequality (18) and ask that each T I < δ 0 T_I<\delta_0 T I < δ 0
The above proposition guarantees that after seeing enough patterns, the TDenseAM learns the underlying code. Crucially, either (B.1) or even (B.2) are far smaller than the exp ( O ( N ) ) \exp(O(N)) exp ( O ( N )) not simply memorizing the training data, it is learning the underlying rules that generated the data set; namely, performing Hamiltonian learning. Amazingly, in the case a > 0 a>0 a > 0 V V V a > 0 a>0 a > 0 v 1 + v 2 v_1+v_2 v 1 + v 2 v 1 v_1 v 1 v 2 v_2 v 2
Dynamics of learning: a → 1 a \to1 a → 1
We will first discuss how the TDenseAM learns – in particular, the nature of the learned energy landscape E ^ \widehat{E} E P P P a → 1 a\to1 a → 1 [15 ] applied to the XORSAT (LDPC) problem: we reject a constraint if we ever see it violated a single time. Namely, T ^ I ≠ 0 \widehat{T}_I\ne0 T I = 0 ξ I μ = ξ I ν \xi_I^\mu=\xi_I^\nu ξ I μ = ξ I ν ( μ , ν ) (\mu,\nu) ( μ , ν )
In our discussion of the learning algorithm, it will be useful to separate out
E ^ ( σ ) = − ∑ I ∈ im ( H T ) T ^ I σ I − ∑ I ∉ im ( H T ) T ^ I σ I = : E + E j u n k , (80) \widehat{E}(\sigma)=-\sum_{I\in\operatorname{im}(H^{\mathsf{T}})}\widehat{T}_I\sigma_I-\sum_{I\notin\operatorname{im}(H^{\mathsf{T}})}\widehat{T}_I\sigma_I=:E+E_{\mathrm{junk}}, \tag*{(80)} E ( σ ) = − I ∈ im ( H T ) ∑ T I σ I − I ∈ / im ( H T ) ∑ T I σ I =: E + E junk , (80) where E E E E j u n k E_{\mathrm{junk}} E junk E j u n k E_{\mathrm{junk}} E junk E j u n k E_{\mathrm{junk}} E junk P P P
There are two useful ways to think about how the TDenseAM learns. Firstly, we can keep track of
J : = # { I : T ^ I > 0 } = ∑ I X I . (81) J:=\#\{I:\widehat{T}_I>0\}=\sum_I X_I. \tag*{(81)} J := # { I : T I > 0 } = I ∑ X I . (81) J J J E ^ \hat{E} E ^ E j u n k E_{\mathrm{junk}} E junk
X I : = I [ T ^ I ≠ 0 ] . (82) X_I := \mathbb{I}[\hat{T}_I \ne0]. \tag*{(82)} X I := I [ T ^ I = 0 ] . (82) The second thing we can keep track of is the rank of the learned codespace k ^ ≤ k \hat{k} \le k k ^ ≤ k
We will show that the way TDenseAM learns in the limit a → 1 a \to1 a → 1 m = 2 m = 2 m = 2 m > 2 m > 2 m > 2
Proposition B.2. Consider the task of learning a random LDPC code with m = 2 m = 2 m = 2 a → 1 a \to1 a → 1 k → ∞ k \to\infty k → ∞ P < ( 1 − ϵ ) log 2 k P < (1-\epsilon)\log_2 k P < ( 1 − ϵ ) log 2 k 0 < ϵ < 1 0 < \epsilon< 1 0 < ϵ < 1
k ^ = 2 P − 1 . (83) \hat{k} = 2^{P-1}. \tag*{(83)} k ^ = 2 P − 1 . (83) Proof. When m = 2 m = 2 m = 2 x i = x j x_i = x_j x i = x j x j = x k x_j = x_k x j = x k x i = x k x_i = x_k x i = x k [ n ] [n] [ n ]
S ( η 1 , … , η P ) : = { i ∈ [ n ] : ξ i μ = η i } . (84) S(\eta_1,\ldots,\eta_P) := \{i \in[n] : \xi_i^\mu= \eta_i\}. \tag*{(84)} S ( η 1 , … , η P ) := { i ∈ [ n ] : ξ i μ = η i } . (84) For convenience, it is useful to “gauge fix” the first ξ 1 1 = 1 \xi_1^1 = 1 ξ 1 1 = 1 S ( η 2 , … , η P ) S(\eta_2,\ldots,\eta_P) S ( η 2 , … , η P ) 2 P − 1 2^{P-1} 2 P − 1
The most general code with m = 2 m = 2 m = 2 k k k n − k n-k n − k i ∈ [ k ] i \in[k] i ∈ [ k ] S ( η 2 , … , η P ) S(\eta_2,\ldots,\eta_P) S ( η 2 , … , η P ) 2 − ( P − 1 ) 2^{-(P-1)} 2 − ( P − 1 )
P ( any S ( η 2 , … , η P ) = ∅ ) ≤ 2 P − 1 ( 1 − 2 − ( P − 1 ) ) k . (85) \mathbb{P}\left(\text{any }S(\eta_2,\ldots,\eta_P)=\varnothing\right) \le2^{P-1}\left(1-2^{-(P-1)}\right)^k. \tag*{(85)} P ( any S ( η 2 , … , η P ) = ∅ ) ≤ 2 P − 1 ( 1 − 2 − ( P − 1 ) ) k . (85) This event happens with probability < ϵ < \epsilon < ϵ
P − 1 + log 2 1 ϵ > k log 2 1 1 − 2 − ( P − 1 ) > 2 − ( P − 1 ) k (86) P-1+\log_2\frac{1}{\epsilon} > k\log_2\frac{1}{1-2^{-(P-1)}} > 2^{-(P-1)k} \tag*{(86)} P − 1 + log 2 ϵ 1 > k log 2 1 − 2 − ( P − 1 ) 1 > 2 − ( P − 1 ) k (86) In the limit of large k k k P < ( 1 − ϵ ) log 2 k P < (1-\epsilon)\log_2 k P < ( 1 − ϵ ) log 2 k ϵ > 0 \epsilon> 0 ϵ > 0
Proposition B.3. Let 0 < κ < 1 0 < \kappa< 1 0 < κ < 1 k = Θ ( n ) k = \Theta(n) k = Θ ( n )
P = ( m − κ ) log 2 n , (87) P = (m-\kappa)\log_2 n, \tag*{(87)} P = ( m − κ ) log 2 n , (87) almost surely as n → ∞ n \to\infty n → ∞
k ^ = k − 2 n k m ! ( 1 + o ( 1 ) ) . (88) \hat{k} = k - 2\frac{n^k}{m!}(1+o(1)). \tag*{(88)} k ^ = k − 2 m ! n k ( 1 + o ( 1 )) . (88) Proof. We begin with a useful lemma:
Lemma B.4: Let A ⊂ [ I ] \mathcal{A} \subset[\mathcal{I}] A ⊂ [ I ] a → 1 a \to1 a → 1 P P P
P [ T ^ I > 0 for all I ∈ A ] = 2 − ( P − 1 ) A (89) \mathbb{P}\left[\hat{T}_I > 0\text{ for all }I \in\mathcal{A}\right] = 2^{-(P-1)\mathcal{A}} \tag*{(89)} P [ T ^ I > 0 for all I ∈ A ] = 2 − ( P − 1 ) A (89) where
A : = rank ( A ) − rank ( A ∩ ker ( H ) ) . (90) A := \operatorname{rank}(\mathcal{A})-\operatorname{rank}(\mathcal{A}\cap\ker(H)). \tag*{(90)} A := rank ( A ) − rank ( A ∩ ker ( H )) . (90) Proof. When ∣ A ∣ = 1 |\mathcal{A}|=1 ∣ A ∣ = 1 I ∈ A I \in\mathcal{A} I ∈ A A = 0 A=0 A = 0 I ∉ ker ( H ) I \notin\ker(H) I ∈ / ker ( H ) ξ I μ \xi_I^\mu ξ I μ μ = 2 , … , P \mu=2,\ldots,P μ = 2 , … , P ξ I 1 \xi_I^1 ξ I 1 ± 1 \pm1 ± 1 1 2 \frac{1}{2} 2 1
Next, suppose that ∣ A ∣ > 1 |\mathcal{A}|>1 ∣ A ∣ > 1 A ∩ ker ( H ) = ∅ \mathcal{A}\cap\ker(H)=\varnothing A ∩ ker ( H ) = ∅ A \mathcal{A} A T ^ I \hat{T}_I T ^ I μ = 2 , … , P \mu=2,\ldots,P μ = 2 , … , P 2 − A 2^{-A} 2 − A v a v_a v a
An analogous argument applies in the case where A ∩ ker ( H ) = 0 \mathcal{A}\cap\ker(H)=0 A ∩ ker ( H ) = 0 A \mathcal{A} A T ^ I \hat{T}_I T ^ I
Lastly, suppose that A ∩ ker ( H ) ≠ ∅ \mathcal{A}\cap\ker(H)\ne\varnothing A ∩ ker ( H ) = ∅ ker ( H ) \ker(H) ker ( H ) A \mathcal{A} A A ∖ ker ( H ) \mathcal{A}\setminus\ker(H) A ∖ ker ( H ) A A A
Observe that
E [ J 2 ] = ∑ I 1 E [ X I 1 ] + ∑ I 1 ≠ I 2 E [ X I 1 X I 2 ] = ∑ I 1 E [ X I 1 ] + ∑ I 1 ≠ I 2 E [ X I 1 ] E [ X I 2 ] . (91) \mathbb{E}[J^2] = \sum_{I_1}\mathbb{E}[X_{I_1}] + \sum_{I_1\ne I_2}\mathbb{E}[X_{I_1}X_{I_2}] = \sum_{I_1}\mathbb{E}[X_{I_1}] + \sum_{I_1\ne I_2}\mathbb{E}[X_{I_1}]\mathbb{E}[X_{I_2}]. \tag*{(91)} E [ J 2 ] = I 1 ∑ E [ X I 1 ] + I 1 = I 2 ∑ E [ X I 1 X I 2 ] = I 1 ∑ E [ X I 1 ] + I 1 = I 2 ∑ E [ X I 1 ] E [ X I 2 ] . (91) The second equality follows from Lemma B.4 : any two inequivalent I I I
Var ( J ) ≤ E [ J ] = ( 1 + o ( 1 ) ) ( n m ) 2 − ( P − 1 ) = n m m ! 2 − ( P − 1 ) ( 1 + o ( 1 ) ) = 2 n k m ! ( 1 + O ( 1 ) ) . (92) \operatorname{Var}(J) \le\mathbb{E}[J] = (1+o(1))\binom{n}{m}2^{-(P-1)} = \frac{n^m}{m!}2^{-(P-1)}(1+o(1)) = 2\frac{n^k}{m!}(1+O(1)). \tag*{(92)} Var ( J ) ≤ E [ J ] = ( 1 + o ( 1 )) ( m n ) 2 − ( P − 1 ) = m ! n m 2 − ( P − 1 ) ( 1 + o ( 1 )) = 2 m ! n k ( 1 + O ( 1 )) . (92) Chebyshev’s inequality thus shows that
P [ ∣ J E [ J ] − 1 ∣ > s ] ≤ s 2 E [ J ] ≤ s 2 m ! 2 n κ . (93) \mathbb{P}\left[\left|\frac{J}{\mathbb{E}[J]}-1\right|>s\right]\leq\frac{s^2}{\mathbb{E}[J]}\leq\frac{s^2m!}{2n^\kappa}. \tag*{(93)} P [ E [ J ] J − 1 > s ] ≤ E [ J ] s 2 ≤ 2 n κ s 2 m ! . (93) This shows that we see 2 n κ / m ! × ( 1 + o ( 1 ) ) 2n^\kappa/m!\times(1+o(1)) 2 n κ / m ! × ( 1 + o ( 1 )) n → ∞ n\to\infty n → ∞
With high probability each bit is included in at most one surviving fake check. This is because for any I 1 ≠ I 2 I_1\ne I_2 I 1 = I 2 P [ X I 1 = 1 ∣ X I 2 = 1 ] = P [ X I 1 = 1 ] \mathbb{P}[X_{I_1}=1\mid X_{I_2}=1]=\mathbb{P}[X_{I_1}=1] P [ X I 1 = 1 ∣ X I 2 = 1 ] = P [ X I 1 = 1 ] Lemma B.4 . Therefore, supposing that bit 1 ∈ I 1 1\in I_1 1 ∈ I 1 X I 1 = 1 X_{I_1}=1 X I 1 = 1 1 1 1
P [ 2 surviving checks contain 1 ∣ 1 surviving check ] ≤ ∑ I 2 ≠ I 1 , 1 ∈ I 2 E [ X I 2 ] = ( n − 1 m − 1 ) 2 − ( P − 1 ) = 2 ( m − 1 ) ! n 1 − κ → 0. (94) \begin{aligned}
\mathbb{P}[2\text{ surviving checks contain }1\mid1\text{ surviving check}]\leq\sum_{\substack{I_2\ne I_1,1\in I_2}}\mathbb{E}[X_{I_2}] \\
&=\binom{n-1}{m-1}2^{-(P-1)}=\frac{2}{(m-1)!n^{1-\kappa}}\to0. \tag*{(94)}
\end{aligned} P [ 2 surviving checks contain 1 ∣ 1 surviving check ] ≤ I 2 = I 1 , 1 ∈ I 2 ∑ E [ X I 2 ] = ( m − 1 n − 1 ) 2 − ( P − 1 ) = ( m − 1 )! n 1 − κ 2 → 0. (94) This shows that almost every check is linearly independent as n → ∞ n\to\infty n → ∞
Theorem B.5: Consider the task of learning a random LDPC code with m ≥ 2 m\geq2 m ≥ 2 k / n = O ( 1 ) k/n=O(1) k / n = O ( 1 ) a → 1 a\to1 a → 1 ϵ > 0 \epsilon>0 ϵ > 0
P < ( m ( m − 1 ) 2 m − 1 − ϵ ) log 2 n . (95) P<\left(\frac{m(m-1)}{2m-1}-\epsilon\right)\log_2 n. \tag*{(95)} P < ( 2 m − 1 m ( m − 1 ) − ϵ ) log 2 n . (95) Then as n → ∞ n\to\infty n → ∞
k ^ = { P − 1 m odd , P m even . (96) \hat{k}=
\begin{cases}
P-1 & m\text{ odd},\\
P & m\text{ even}.
\end{cases} \tag*{(96)} k ^ = { P − 1 P m odd , m even . (96) Proof. The core strategy of this proof is to argue that when (B.22) is obeyed, each new observed codeword increases the rank only by 1. If we can establish this fact, (B.23) follows immediately from the fact that after being shown the first pattern ξ i 1 \xi_i^1 ξ i 1 E ^ \hat{E} E ^ m m m m m m ξ i 1 \xi_i^1 ξ i 1 − ξ i 1 -\xi_i^1 − ξ i 1
To do this, we proceed as follows. Define
α : = P log 2 n < m ( m − 1 ) 2 m − 1 − ϵ . (97) \alpha:=\frac{P}{\log_2 n}<\frac{m(m-1)}{2m-1}-\epsilon. \tag*{(97)} α := log 2 n P < 2 m − 1 m ( m − 1 ) − ϵ . (97) Lemma B.4 shows that the probability that any spurious check has survived is given by
q : = P [ T ^ I ≠ 0 if I ∉ im ( H T ) ] = 2 n − α , (98) q:=\mathbb{P}[\hat{T}_I\ne0\text{ if }I\notin\operatorname{im}(H^{\mathsf T})]=2n^{-\alpha}, \tag*{(98)} q := P [ T ^ I = 0 if I ∈ / im ( H T )] = 2 n − α , (98) which is quite small. At the same time, there are a huge number of spurious checks: ∼ n m \sim n^m ∼ n m
We will therefore establish (B.23) as follows. First, define K P K_P K P P P P
K P : = { w ∈ F 2 n : ∣ w ∣ = m and w ⋅ ( b μ − b 1 ) = 0 for 2 ≤ μ ≤ P } . (99) K_P := \{w \in\mathbb{F}_2^n : |w| = m \text{ and } w \cdot(b^\mu- b^1) = 0 \text{ for } 2 \le\mu\le P\}. \tag*{(99)} K P := { w ∈ F 2 n : ∣ w ∣ = m and w ⋅ ( b μ − b 1 ) = 0 for 2 ≤ μ ≤ P } . (99) Without loss of generality for what follows, we set b i 1 = 0 b_i^1=0 b i 1 = 0 α \alpha α dim ( span ( K P + 1 ) ) − dim ( span ( K P ) ) = 1 \dim(\operatorname{span}(K_{P+1}))-\dim(\operatorname{span}(K_P))=1 dim ( span ( K P + 1 )) − dim ( span ( K P )) = 1 w 1 , 2 ∈ K P + 1 ∖ K P w_{1,2}\in K_{P+1}\setminus K_P w 1 , 2 ∈ K P + 1 ∖ K P w 1 + w 2 ∈ K P + 1 w_1+w_2\in K_{P+1} w 1 + w 2 ∈ K P + 1 2 m 2m 2 m K P + 1 K_{P+1} K P + 1
Definition B.6 (Nice matching): Define the graph G n i c e G_{\mathrm{nice}} G nice K m , m K_{m,m} K m , m Figure 5 . A nice matching on K P K_P K P M M M m 2 + m m^2+m m 2 + m ( v 1 , … , v 2 m ; u 1 , … , u m 2 − m ) (v_1,\ldots,v_{2m};u_1,\ldots,u_{m^2-m}) ( v 1 , … , v 2 m ; u 1 , … , u m 2 − m ) v 1 , … , v 2 m v_1,\ldots,v_{2m} v 1 , … , v 2 m 2 m 2m 2 m G n i c e G_{\mathrm{nice}} G nice u 1 , … , u m 2 − m u_1,\ldots,u_{m^2-m} u 1 , … , u m 2 − m m 2 − m m^2-m m 2 − m G n i c e G_{\mathrm{nice}} G nice w 1 = { v 1 , … , v m } w_1=\{v_1,\ldots,v_m\} w 1 = { v 1 , … , v m } w 2 = { v m + 1 , … , v 2 m } w_2=\{v_{m+1},\ldots,v_{2m}\} w 2 = { v m + 1 , … , v 2 m } K P K_P K P
{ v } ∪ ⋃ e ∈ ∂ v { u e } ∈ K P . (100) \{v\}\cup\bigcup_{e\in\partial v}\{u_e\}\in K_P. \tag*{(100)} { v } ∪ e ∈ ∂ v ⋃ { u e } ∈ K P . (100) Figure 5. Illustration of G n i c e G_{\mathrm{nice}} G nice m = 5 m=5 m = 5
We also write U ( M ) : = { u 1 , … , u m 2 − m } U(M):=\{u_1,\ldots,u_{m^2-m}\} U ( M ) := { u 1 , … , u m 2 − m } A ( M ) A(M) A ( M ) ( m − 1 ) (m-1) ( m − 1 ) M M M v i v_i v i
We will restrict our study to candidate matchings where u 1 , … , u m ( m − 1 ) ∈ V u_1,\ldots,u_{m(m-1)}\in\mathcal{V} u 1 , … , u m ( m − 1 ) ∈ V V ⊂ [ n ] \mathcal{V}\subset[n] V ⊂ [ n ]
Lemma B.7: Suppose that k ≥ R n k\ge Rn k ≥ R n O ( 1 ) O(1) O ( 1 ) R R R n n n W ⊂ [ n ] W\subset[n] W ⊂ [ n ] ∣ W ∣ = 2 m |W|=2m ∣ W ∣ = 2 m O ( 1 ) O(1) O ( 1 ) 0 < ρ < R 0<\rho<R 0 < ρ < R V ⊂ [ n ] \mathcal{V}\subset[n] V ⊂ [ n ] ∣ V ∣ = ρ n |\mathcal{V}|=\rho n ∣ V ∣ = ρ n
such that the following holds. Let D : = im ( H T ) ⊕ span ( e i ) i ∈ W D := \operatorname{im}(H^{\mathsf{T}}) \oplus\operatorname{span}(e_i)_{i\in W} D := im ( H T ) ⊕ span ( e i ) i ∈ W e i e_i e i F 2 n \mathbb{F}_2^n F 2 n [ e i ] ∈ F 2 n / D [e_i] \in\mathbb{F}_2^n/D [ e i ] ∈ F 2 n / D { [ e i ] } i ∈ V \{[e_i]\}_{i\in V} {[ e i ] } i ∈ V b μ b^\mu b μ b i μ b_i^\mu b i μ P ( b i μ = 1 ) = 1 2 \mathbb{P}(b_i^\mu= 1) = \frac{1}{2} P ( b i μ = 1 ) = 2 1
Proof. Because we have dim ( im ( H T ) ) = ( 1 − R ) n \dim(\operatorname{im}(H^{\mathsf{T}})) = (1-R)n dim ( im ( H T )) = ( 1 − R ) n dim ( F 2 n / D ) ≥ R n − 2 m \dim(\mathbb{F}_2^n/D) \ge Rn - 2m dim ( F 2 n / D ) ≥ R n − 2 m ρ < R \rho< R ρ < R n n n { [ e i ] } i ∈ [ n ] \{[e_i]\}_{i\in[n]} {[ e i ] } i ∈ [ n ] ρ n \rho n ρ n P ( b i μ = 1 ) = 1 2 \mathbb{P}(b_i^\mu= 1) = \frac{1}{2} P ( b i μ = 1 ) = 2 1 i ∈ V i \in V i ∈ V b j μ b_j^\mu b j μ j ∈ W j \in W j ∈ W b i μ b_i^\mu b i μ i i i b i μ b_i^\mu b i μ V V V Theorem B.5 .
In what follows, we will condition on w 1 , 2 ⋅ b μ = 0 w_{1,2}\cdot b^\mu= 0 w 1 , 2 ⋅ b μ = 0 2 ≤ μ ≤ P 2 \le\mu\le P 2 ≤ μ ≤ P w 1 , 2 ⋅ b P + 1 = 1 w_{1,2}\cdot b^{P+1} = 1 w 1 , 2 ⋅ b P + 1 = 1 Lemma B.7 shows us that all b i μ b_i^\mu b i μ K P + 1 K_{P+1} K P + 1 w 1 , 2 w_{1,2} w 1 , 2 w 1 + w 2 ∈ span ( K P + 1 ) w_1+w_2 \in\operatorname{span}(K_{P+1}) w 1 + w 2 ∈ span ( K P + 1 )
X M : = I [ M is a nice matching on K P + 1 ] . (101) X_M := \mathbb{I}[M\text{ is a nice matching on }K_{P+1}]. \tag*{(101)} X M := I [ M is a nice matching on K P + 1 ] . (101) We further introduce independent Bernoulli random variables θ M \theta_M θ M P [ θ M = 1 ] = ν \mathbb{P}[\theta_M = 1] = \nu P [ θ M = 1 ] = ν ν \nu ν
M : = ∑ M θ M X M . (102) \mathcal{M} := \sum_M \theta_M X_M. \tag*{(102)} M := M ∑ θ M X M . (102) We do this by invoking the following improvement over Hoeffding’s inequality, discussed in [32 , 33 ] :
Lemma B.8: Let { X a } a = 1 N \{X_a\}_{a=1}^N { X a } a = 1 N X a ∈ { 0 , 1 } X_a \in\{0,1\} X a ∈ { 0 , 1 } a a a a a a b b b a ∈ ∂ b a \in\partial b a ∈ ∂ b A A A B B B { X a } a ∈ A \{X_a\}_{a\in A} { X a } a ∈ A { X b } b ∈ B \{X_b\}_{b\in B} { X b } b ∈ B
P [ ∑ a = 1 N X a = 0 ] ≤ exp ( − λ + Δ e 2 δ ) (103) \mathbb{P}\left[\sum_{a=1}^{N}X_a=0\right] \le\exp\left(-\lambda+\Delta e^{2\delta}\right) \tag*{(103)} P [ a = 1 ∑ N X a = 0 ] ≤ exp ( − λ + Δ e 2 δ ) (103) where
λ = ∑ a = 1 N E [ X a ] , (104) \lambda=\sum_{a=1}^{N}\mathbb{E}[X_a], \tag*{(104)} λ = a = 1 ∑ N E [ X a ] , (104) Δ = ∑ a = 1 N ∑ b ∈ ∂ a E [ X a X b ] . (105) \Delta=\sum_{a=1}^{N}\sum_{b\in\partial a}\mathbb{E}[X_aX_b]. \tag*{(105)} Δ = a = 1 ∑ N b ∈ ∂ a ∑ E [ X a X b ] . (105) δ = max a ∑ b ∈ ∂ a E [ X b ] . (106) \delta= \max_a \sum_{b\in\partial a} \mathbb{E}[X_b]. \tag*{(106)} δ = a max b ∈ ∂ a ∑ E [ X b ] . (106) The idea is to apply this lemma to bound P [ M = 0 ] \mathbb{P}[\mathcal{M}=0] P [ M = 0 ] M > 0 \mathcal{M}>0 M > 0 K P + 1 \mathcal{K}_{P+1} K P + 1 w 1 + w 2 ∈ span ( K P + 1 ) w_1+w_2\in\operatorname{span}(\mathcal{K}_{P+1}) w 1 + w 2 ∈ span ( K P + 1 ) Lemma B.8 . A useful way to do this is to say that M 1 ∈ ∂ M 2 M_1\in\partial M_2 M 1 ∈ ∂ M 2 M 1 ≠ M 2 M_1\ne M_2 M 1 = M 2 M 1 M_1 M 1 M 2 M_2 M 2
First, we evaluate
λ : = E [ M ] = ⌊ ρ n ⌋ ! ( ⌊ ρ n ⌋ − m 2 + m ) ! ν E [ X M ] (107) \lambda:= \mathbb{E}[\mathcal{M}] = \frac{\lfloor\rho n\rfloor!}{(\lfloor\rho n\rfloor-m^2+m)!}\nu\mathbb{E}[X_M] \tag*{(107)} λ := E [ M ] = (⌊ ρ n ⌋ − m 2 + m )! ⌊ ρ n ⌋! ν E [ X M ] (107) where the first combinatorial factor represents the number of candidate nice matchings: note that the order in which we assign the coordinates does matter, which is why there is not an additional 1 / ( m 2 − m ) ! 1/(m^2-m)! 1/ ( m 2 − m )! Lemma B.7 implies that in the coset space F 2 n / D \mathbb{F}_2^n/D F 2 n / D 2 m 2m 2 m 2 m − 1 2m-1 2 m − 1 w 1 + w 2 w_1+w_2 w 1 + w 2 Lemma B.4 , we then have
E [ X M = 1 ] = 2 − P ( 2 m − 1 ) = n − ( 2 m − 1 ) α . (108) \mathbb{E}[X_M=1] = 2^{-P(2m-1)} = n^{-(2m-1)\alpha}. \tag*{(108)} E [ X M = 1 ] = 2 − P ( 2 m − 1 ) = n − ( 2 m − 1 ) α . (108) Therefore, using (B.24),
λ ≥ ν ( ρ n ) m 2 − m n − ( 2 m − 1 ) α = ν ρ m 2 − m n ϵ . (109) \lambda\ge\nu(\rho n)^{m^2-m}n^{-(2m-1)\alpha} = \nu\rho^{m^2-m}n^\epsilon. \tag*{(109)} λ ≥ ν ( ρ n ) m 2 − m n − ( 2 m − 1 ) α = ν ρ m 2 − m n ϵ . (109) On average, there are many candidate perfect matchings.
We now need to evaluate Δ \Delta Δ δ \delta δ
Lemma B.9: Let M 1 M_1 M 1 M 2 M_2 M 2 M 1 ∈ ∂ M 2 M_1\in\partial M_2 M 1 ∈ ∂ M 2 6 ∣ U ( M 1 ) ∩ U ( M 2 ) ∣ = s |\mathcal{U}(M_1)\cap\mathcal{U}(M_2)|=s ∣ U ( M 1 ) ∩ U ( M 2 ) ∣ = s
dim ( row ( A ( M 1 ) ) ∩ row ( A ( M 2 ) ) ) = : r ≤ 2 m − 1 m ( m − 1 ) s = : a m s . (110) \dim(\operatorname{row}(\mathcal{A}(M_1))\cap\operatorname{row}(\mathcal{A}(M_2)))=:r\le\frac{2m-1}{m(m-1)}s=:a_m s. \tag*{(110)} dim ( row ( A ( M 1 )) ∩ row ( A ( M 2 ))) =: r ≤ m ( m − 1 ) 2 m − 1 s =: a m s . (110) In other words, any two matchings with many common checks must also share a large number of bits in common. As a consequence,
E [ X M 1 X M 2 ] ≤ 2 − P ( 2 ( 2 m − 1 ) − r ) = E [ X M 1 ] E [ X M 2 ] 2 P r . (111) \mathbb{E}[X_{M_1}X_{M_2}]\le2^{-P(2(2m-1)-r)}=\mathbb{E}[X_{M_1}]\mathbb{E}[X_{M_2}]2^{Pr}. \tag*{(111)} E [ X M 1 X M 2 ] ≤ 2 − P ( 2 ( 2 m − 1 ) − r ) = E [ X M 1 ] E [ X M 2 ] 2 P r . (111) Proof. Recall that a common vector between A ( M 1 ) \mathcal{A}(M_1) A ( M 1 ) A ( M 2 ) \mathcal{A}(M_2) A ( M 2 ) U ( M 1 ) ∩ U ( M 2 ) : = U ∗ \mathcal{U}(M_1)\cap\mathcal{U}(M_2):=\mathcal{U}_* U ( M 1 ) ∩ U ( M 2 ) := U ∗ U ∗ \mathcal{U}_* U ∗ M 1 , 2 M_{1,2} M 1 , 2 G n i c e G_{\mathrm{nice}} G nice U ( M 1 , 2 ) ∖ U ∗ \mathcal{U}(M_{1,2})\setminus\mathcal{U}_* U ( M 1 , 2 ) ∖ U ∗ c > 1 c>1 c > 1
r ≤ c − 1. (112) r \le c-1. \tag*{(112)} r ≤ c − 1. (112) Now suppose that we choose a connected component of A ⊂ G n i c e A \subset G_{\mathrm{nice}} A ⊂ G nice n 1 n_1 n 1 n 2 n_2 n 2 Figure 6 . Without loss of generality we may take n 1 + n 2 : = n s ≤ m n_1+n_2 := n_s \le m n 1 + n 2 := n s ≤ m
Figure 6. An illustration of a connected component A ⊂ G n i c e A \subset G_{\mathrm{nice}} A ⊂ G nice A A A n 1 = n 2 = 2 n_1=n_2=2 n 1 = n 2 = 2 m = 5 m=5 m = 5
∣ { e = ( v 1 , v 2 ) : v 1 ∈ A , v 2 ∉ A } ∣ ≥ ( n 1 + n 2 ) ( m − 1 ) − n 1 n 2 ≥ n s ( m − 1 ) − n s 2 2 ≥ m − 1 2 . (113) \left|\{e=(v_1,v_2):v_1\in A,v_2\notin A\}\right| \ge(n_1+n_2)(m-1)-n_1n_2 \ge n_s(m-1)-\frac{n_s^2}{2} \ge\frac{m-1}{2}. \tag*{(113)} ∣ { e = ( v 1 , v 2 ) : v 1 ∈ A , v 2 ∈ / A } ∣ ≥ ( n 1 + n 2 ) ( m − 1 ) − n 1 n 2 ≥ n s ( m − 1 ) − 2 n s 2 ≥ 2 m − 1 . (113) The last inequality can be checked by brute force since n s ∈ { 1 , … , m } n_s\in\{1,\ldots,m\} n s ∈ { 1 , … , m }
Since c ≥ 2 c\ge2 c ≥ 2 r > 0 r>0 r > 0 U ( M 1 ) \mathcal{U}(M_1) U ( M 1 )
s ≥ c m − 1 2 ≥ ( m − 1 ) m 2 m − 1 ( c − 1 ) , (114) s \ge c\frac{m-1}{2} \ge(m-1)\frac{m}{2m-1}(c-1), \tag*{(114)} s ≥ c 2 m − 1 ≥ ( m − 1 ) 2 m − 1 m ( c − 1 ) , (114) where the second inequality uses that c ≤ 2 m c\le2m c ≤ 2 m
Let us then count the number of neighboring pairs in the adjacency graph on matchings. Clearly, for s > 0 s>0 s > 0
∣ { ( M 1 , M 2 ) : ∣ U ( M 1 ) ∩ U ( M 2 ) ∣ = s } ∣ ≤ ( m 2 − m ) 2 s ( ρ n ) 2 m ( m − 1 ) − s , (115) \left|\{(M_1,M_2):|\mathcal{U}(M_1)\cap\mathcal{U}(M_2)|=s\}\right| \le(m^2-m)^{2s}(\rho n)^{2m(m-1)-s}, \tag*{(115)} ∣ {( M 1 , M 2 ) : ∣ U ( M 1 ) ∩ U ( M 2 ) ∣ = s } ∣ ≤ ( m 2 − m ) 2 s ( ρ n ) 2 m ( m − 1 ) − s , (115) where the first factor counts the number of candidate identifications of two edges in the matching with the same bit, while the second factor bounds the number of independent bits to choose between the matchings.
Now we can bound Δ \Delta Δ M 1 M_1 M 1 M 2 M_2 M 2
Δ ≤ ⌊ ρ n ⌋ ! ( ⌊ ρ n ⌋ − m 2 + m ) ! ν 2 ∑ M 2 ∈ ∂ M 1 E [ X M 1 X M 2 ] . (116) \Delta\le\frac{\lfloor\rho n\rfloor!}{(\lfloor\rho n\rfloor-m^2+m)!}\nu^2 \sum_{M_2\in\partial M_1}\mathbb{E}[X_{M_1}X_{M_2}]. \tag*{(116)} Δ ≤ (⌊ ρ n ⌋ − m 2 + m )! ⌊ ρ n ⌋! ν 2 M 2 ∈ ∂ M 1 ∑ E [ X M 1 X M 2 ] . (116) This sum can be broken up by rank r r r r = 0 r=0 r = 0 r > 0 r>0 r > 0
Δ ≤ ( ρ n ) 2 m ( m − 1 ) ν 2 E [ X M 1 ] 2 ( ∑ s = 1 m 2 − m ( m 2 ( m − 1 ) 2 ρ n ) s + ∑ r = 1 2 m − 1 ∑ s = ⌈ a m r ⌉ m 2 − m 2 P r ( m 2 ( m − 1 ) 2 ρ n ) s ) ≤ C λ 2 n − ϵ . (117) \begin{aligned}
\Delta\le(\rho n)^{2m(m-1)}\nu^2\mathbb{E}[X_{M_1}]^2\left(\sum_{s=1}^{m^2-m}\left(\frac{m^2(m-1)^2}{\rho n}\right)^s+\sum_{r=1}^{2m-1}\sum_{s=\lceil a_m r\rceil}^{m^2-m}2^{Pr}\left(\frac{m^2(m-1)^2}{\rho n}\right)^s\right) \\
&\le C\lambda^2 n^{-\epsilon}. \tag*{(117)}
\end{aligned} Δ ≤ ( ρ n ) 2 m ( m − 1 ) ν 2 E [ X M 1 ] 2 s = 1 ∑ m 2 − m ( ρ n m 2 ( m − 1 ) 2 ) s + r = 1 ∑ 2 m − 1 s = ⌈ a m r ⌉ ∑ m 2 − m 2 P r ( ρ n m 2 ( m − 1 ) 2 ) s ≤ C λ 2 n − ϵ . (117) for sufficiently small ϵ \epsilon ϵ n n n C C C r = 1 r=1 r = 1 s s s
Similarly it is easy to bound δ \delta δ [ m ( m − 1 ) ] 2 ( ρ n ) m ( m − 1 ) − 1 [m(m-1)]^2(\rho n)^{m(m-1)-1} [ m ( m − 1 ) ] 2 ( ρ n ) m ( m − 1 ) − 1
δ = m 2 ( m − 1 ) 2 ( ρ n ) m ( m − 1 ) − 1 n − ( 2 m − 1 ) α = m 2 ( m − 1 ) 2 λ ρ n . (118) \delta=m^2(m-1)^2(\rho n)^{m(m-1)-1}n^{-(2m-1)\alpha}=m^2(m-1)^2\frac{\lambda}{\rho n}. \tag*{(118)} δ = m 2 ( m − 1 ) 2 ( ρ n ) m ( m − 1 ) − 1 n − ( 2 m − 1 ) α = m 2 ( m − 1 ) 2 ρ n λ . (118) Now let us put everything together. We want to ensure that 2 δ < 1 2\delta<1 2 δ < 1 λ > 2 Δ e 2 δ \lambda>2\Delta e^{2\delta} λ > 2Δ e 2 δ λ > 6 Δ \lambda>6\Delta λ > 6Δ
λ > 6 C λ 2 n − ϵ . (119) \lambda>6C\lambda^2n^{-\epsilon}. \tag*{(119)} λ > 6 C λ 2 n − ϵ . (119) From (B.34), we see that (B.44) is satisfied for large enough n n n
ν = n − ϵ / 2 , (120) \nu=n^{-\epsilon/2}, \tag*{(120)} ν = n − ϵ /2 , (120) Lemma B.8 then shows that almost surely as n → ∞ n\to\infty n → ∞ w 1 , 2 ∈ K P ∖ K P + 1 w_{1,2}\in K_P\setminus K_{P+1} w 1 , 2 ∈ K P ∖ K P + 1 w 1 + w 2 ∈ span ( K P + 1 ) w_1+w_2\in\operatorname{span}(K_{P+1}) w 1 + w 2 ∈ span ( K P + 1 ) w 1 + w 2 ∉ span ( K P + 1 ) w_1+w_2\notin\operatorname{span}(K_{P+1}) w 1 + w 2 ∈ / span ( K P + 1 ) n n n
P [ removed more checks ] ≤ n m P exp ( − λ + Δ e 2 δ ) < exp ( − Θ ( n ϵ / 2 ) ) . (121) \mathbb{P}[\text{removed more checks}]\le n^mP\exp\left(-\lambda+\Delta e^{2\delta}\right)<\exp\left(-\Theta\left(n^{\epsilon/2}\right)\right). \tag*{(121)} P [ removed more checks ] ≤ n m P exp ( − λ + Δ e 2 δ ) < exp ( − Θ ( n ϵ /2 ) ) . (121) for sufficiently large n n n n → ∞ n\to\infty n → ∞
Dynamics of learning: a = 0 a = 0 a = 0
Next, we consider the opposite limit of a = 0 a = 0 a = 0 [10 ] , E ^ \widehat{E} E P P P
The first result is to establish an absence of stability of typical unseen perturbations until P ∼ n m − 1 P \sim n^{m-1} P ∼ n m − 1
Theorem B.10. Consider training the a = 0 a = 0 a = 0 ( Δ B , Δ C ) (\Delta_B,\Delta_C) ( Δ B , Δ C ) Δ C = m > Δ B > 2 \Delta_C = m > \Delta_B > 2 Δ C = m > Δ B > 2 E ^ \widehat{E} E c ∈ ker ( H ) c \in\ker(H) c ∈ ker ( H ) c + a c + a c + a ∣ a ∣ = β n |a| = \beta n ∣ a ∣ = β n
P = A n m − 1 , (122) P = A n^{m-1}, \tag*{(122)} P = A n m − 1 , (122) then almost surely as n → ∞ n \to\infty n → ∞
P [ E ^ ( c ) > E ^ ( c + a ) for some a ] → 1 (123) \mathbb{P}\left[\widehat{E}(c) > \widehat{E}(c+a)\text{ for some }a\right] \to1 \tag*{(123)} P [ E ( c ) > E ( c + a ) for some a ] → 1 (123) if A < A min ( β ) A < A_{\min}(\beta) A < A m i n ( β ) n n n A min A_{\min} A m i n A ( 0 ) = 0 A(0) = 0 A ( 0 ) = 0
Proof. Without loss of generality, we may consider the stability of the codeword c = 0 c = 0 c = 0 σ 1 \sigma^{1} σ 1 P P P ξ μ \xi^\mu ξ μ ker ( H ) \ker(H) ker ( H )
E ^ ( σ ) = − 1 P ∑ μ = 1 P ( σ ⋅ ξ μ ) m (124) \widehat{E}(\sigma) = -\frac{1}{P}\sum_{\mu=1}^{P}(\sigma\cdot\xi^\mu)^m \tag*{(124)} E ( σ ) = − P 1 μ = 1 ∑ P ( σ ⋅ ξ μ ) m (124) when a = 0 a = 0 a = 0 c = 0 c = 0 c = 0
Towards this end, let us consider the following setup. Let
Ξ 1 : = { i ∈ [ n ] : ξ i 1 = − 1 } (125) \Xi_1 := \{i \in[n] : \xi_i^1 = -1\} \tag*{(125)} Ξ 1 := { i ∈ [ n ] : ξ i 1 = − 1 } (125) denote the sites where the first (randomly drawn) codeword differs from σ 1 \sigma^1 σ 1 n → ∞ n \to\infty n → ∞ Corollary A.16 shows that
∣ Ξ 1 ∣ = ( 1 + o ( 1 ) ) n 2 . (126) |\Xi_1| = (1 + o(1))\frac{n}{2}. \tag*{(126)} ∣ Ξ 1 ∣ = ( 1 + o ( 1 )) 2 n . (126) Let B ⊂ Ξ 1 B \subset\Xi_1 B ⊂ Ξ 1
σ i B : = 1 − 2 I ( i ∈ B ) . (127) \sigma_i^B := 1 - 2\mathbb{I}(i \in B). \tag*{(127)} σ i B := 1 − 2 I ( i ∈ B ) . (127) We then consider the random variable
E : = E ^ ( σ i 1 ) − E ^ ( σ i B ) . (128) \mathcal{E} := \widehat{E}(\sigma^1_i) - \widehat{E}(\sigma^B_i). \tag*{(128)} E := E ( σ i 1 ) − E ( σ i B ) . (128) The goal will be to show that for large enough B B B E B > 0 \mathcal{E}_B > 0 E B > 0 P P P
Y μ : = ( σ B ⋅ ξ μ ) m − ( σ 1 ⋅ ξ μ ) m (129) Y^\mu:= \left(\sigma^B \cdot\xi^\mu\right)^m - \left(\sigma^1 \cdot\xi^\mu\right)^m \tag*{(129)} Y μ := ( σ B ⋅ ξ μ ) m − ( σ 1 ⋅ ξ μ ) m (129) since
E = ∑ μ = 1 P Y μ . (130) \mathcal{E} = \sum_{\mu=1}^{P} Y^\mu. \tag*{(130)} E = μ = 1 ∑ P Y μ . (130) It will also be useful to define
β : = ∣ B ∣ n . (131) \beta:= \frac{|B|}{n}. \tag*{(131)} β := n ∣ B ∣ . (131) Let us first consider the case μ = 1 \mu= 1 μ = 1
Y 1 = ( n − 2 ∣ Ξ 1 ∣ + 2 ∣ B ∣ ) m − ( n − 2 ∣ Ξ 1 ∣ ) m , (132) Y^1 = (n - 2|\Xi_1| + 2|B|)^m - (n - 2|\Xi_1|)^m, \tag*{(132)} Y 1 = ( n − 2∣ Ξ 1 ∣ + 2∣ B ∣ ) m − ( n − 2∣ Ξ 1 ∣ ) m , (132) deterministically. Assume that β > 0 \beta> 0 β > 0 O ( 1 ) O(1) O ( 1 ) n → ∞ n \to\infty n → ∞
Y 1 = ( 1 + o ( 1 ) ) ( 2 β n ) m (133) Y^1 = (1 + o(1))(2\beta n)^m \tag*{(133)} Y 1 = ( 1 + o ( 1 )) ( 2 β n ) m (133) In contrast, for μ = 2 , … , P \mu= 2,\ldots,P μ = 2 , … , P Y μ Y^\mu Y μ
Lemma B.11: Letting E E E β > 0 \beta> 0 β > 0
E [ Y μ ] = E ( σ 1 ) − E ( σ B ) , (134) \mathbb{E}[Y^\mu] = E(\sigma^1) - E(\sigma^B), \tag*{(134)} E [ Y μ ] = E ( σ 1 ) − E ( σ B ) , (134) E [ ( Y μ − E [ Y μ ] ) 2 ] < ( 1 + o ( 1 ) ) ⋅ 2 ( 2 m ) ! 2 m m ! ( 1 − ( 1 − 2 β ) m ) n m . (135) \mathbb{E}\left[(Y^\mu-\mathbb{E}[Y^\mu])^2\right] < (1+o(1))\cdot2\frac{(2m)!}{2^m m!}\left(1-(1-2\beta)^m\right)n^m. \tag*{(135)} E [ ( Y μ − E [ Y μ ] ) 2 ] < ( 1 + o ( 1 )) ⋅ 2 2 m m ! ( 2 m )! ( 1 − ( 1 − 2 β ) m ) n m . (135) Proof. Here it is useful to expand out
( σ ⋅ ξ μ ) m = ∑ i 1 , i 2 , … , i m ξ i 1 μ σ i 1 ⋯ ξ i m μ σ i m . (136) (\sigma\cdot\xi^\mu)^m = \sum_{i_1,i_2,\ldots,i_m}\xi^\mu_{i_1}\sigma_{i_1}\cdots\xi^\mu_{i_m}\sigma_{i_m}. \tag*{(136)} ( σ ⋅ ξ μ ) m = i 1 , i 2 , … , i m ∑ ξ i 1 μ σ i 1 ⋯ ξ i m μ σ i m . (136) Using Proposition A.3, we see that when averaging over codewords ξ μ \xi^\mu ξ μ ξ \xi ξ m m m Y μ Y^\mu Y μ
Now we turn to the second moment. It is useful to write it as follows. Let J 1 , 2 ⊂ [ n ] J_{1,2} \subset[n] J 1 , 2 ⊂ [ n ] m m m ξ \xi ξ
E [ ( Y μ ) 2 ] = ∑ J 1 , J 2 : ∣ J 1 , 2 ∣ = m E ξ [ ξ J 1 μ ξ J 2 μ ] ( σ J 1 B − σ J 1 1 ) ( σ J 2 B − σ J 2 1 ) . (137) \mathbb{E}\left[(Y^\mu)^2\right] = \sum_{J_1,J_2:\lvert J_{1,2}\rvert=m} \mathbb{E}_{\xi}\left[\xi_{J_1}^{\mu}\xi_{J_2}^{\mu}\right]\left(\sigma_{J_1}^{B}-\sigma_{J_1}^{1}\right)\left(\sigma_{J_2}^{B}-\sigma_{J_2}^{1}\right). \tag*{(137)} E [ ( Y μ ) 2 ] = J 1 , J 2 : ∣ J 1 , 2 ∣ = m ∑ E ξ [ ξ J 1 μ ξ J 2 μ ] ( σ J 1 B − σ J 1 1 ) ( σ J 2 B − σ J 2 1 ) . (137) Firstly, we can again use Proposition A.3 to conclude
E [ ξ J 1 μ ξ J 2 μ ] = I [ J 1 △ J 2 ∈ im ( H T ) ] . (138) \mathbb{E}\left[\xi_{J_1}^{\mu}\xi_{J_2}^{\mu}\right]=\mathbb{I}\left[J_1\mathbin{\triangle}J_2\in\operatorname{im}(H^{\mathsf{T}})\right]. \tag*{(138)} E [ ξ J 1 μ ξ J 2 μ ] = I [ J 1 △ J 2 ∈ im ( H T ) ] . (138) Notice the following simple bound: since
σ J 1 B − σ J 1 1 = − 2 I ( ∣ J 1 ∩ B ∣ o d d ) (139) \sigma_{J_1}^{B}-\sigma_{J_1}^{1}=-2\mathbb{I}(\lvert J_1\cap B\rvert\ \mathrm{odd}) \tag*{(139)} σ J 1 B − σ J 1 1 = − 2 I (∣ J 1 ∩ B ∣ odd ) (139) is either 0 or − 2 -2 − 2
E [ ( Y μ ) 2 ] < 4 ∑ J 1 , J 2 : ∣ J 1 , 2 ∣ = m I ( J 1 △ J 2 ∈ im ( H T ) ) I ( ∣ J 1 ∩ B ∣ o d d ) I ( ∣ J 2 ∩ B ∣ o d d ) (140) \mathbb{E}\left[(Y^\mu)^2\right]<4\sum_{J_1,J_2:\lvert J_{1,2}\rvert=m}\mathbb{I}(J_1\mathbin{\triangle}J_2\in\operatorname{im}(H^{\mathsf{T}}))\mathbb{I}(\lvert J_1\cap B\rvert\mathrm{odd})\mathbb{I}(\lvert J_2\cap B\rvert\mathrm{odd}) \tag*{(140)} E [ ( Y μ ) 2 ] < 4 J 1 , J 2 : ∣ J 1 , 2 ∣ = m ∑ I ( J 1 △ J 2 ∈ im ( H T )) I (∣ J 1 ∩ B ∣ odd ) I (∣ J 2 ∩ B ∣ odd ) (140) By Corollary A.15 , this sum is dominated by terms where J 1 J_1 J 1 J 2 J_2 J 2 w ∈ F 2 n w\in\mathbb{F}_2^n w ∈ F 2 n w ∈ im ( H T ) w\in\operatorname{im}(H^{\mathsf{T}}) w ∈ im ( H T ) n m − ∣ w ∣ N ∣ w ∣ = o ( n m ) n^{m-\lvert w\rvert}N_{\lvert w\rvert}=o(n^m) n m − ∣ w ∣ N ∣ w ∣ = o ( n m ) ∣ w ∣ > 0 \lvert w\rvert>0 ∣ w ∣ > 0 J 1 J_1 J 1 J 2 J_2 J 2 2 − m ( 2 m − 1 ) ! ! × n m 2^{-m}(2m-1)!!\times n^m 2 − m ( 2 m − 1 )!! × n m 2 m 2m 2 m i 1 ⋯ i 2 m i_1\cdots i_{2m} i 1 ⋯ i 2 m n m n^m n m
P ( ∣ J 1 ∩ B ∣ o d d ) = P ( ∣ J 2 ∩ B ∣ o d d ) = ∑ j o d d ( m j ) β j ( 1 − β ) m − j = 1 − ( 1 − 2 β ) m 2 . (141) \mathbb{P}(\lvert J_1\cap B\rvert\ \mathrm{odd})=\mathbb{P}(\lvert J_2\cap B\rvert\ \mathrm{odd})=\sum_{j\ \mathrm{odd}}\binom{m}{j}\beta^j(1-\beta)^{m-j}=\frac{1-(1-2\beta)^m}{2}. \tag*{(141)} P (∣ J 1 ∩ B ∣ odd ) = P (∣ J 2 ∩ B ∣ odd ) = j odd ∑ ( j m ) β j ( 1 − β ) m − j = 2 1 − ( 1 − 2 β ) m . (141) Therefore using that this contribution dominates E [ ( Y μ ) 2 ] \mathbb{E}[(Y^\mu)^2] E [( Y μ ) 2 ]
The crucial thing we learn from Lemma B.11 is that Y μ Y^\mu Y μ Y 2 + ⋯ + Y P Y^2+\cdots+Y^P Y 2 + ⋯ + Y P n → ∞ n\to\infty n → ∞ P = A n m − 1 P=An^{m-1} P = A n m − 1 E \mathcal{E} E
E [ E ] → P E [ E ( σ 1 ) − E ( σ B ) ] + ( 2 β n ) m , (142) \mathbb{E}[\mathcal{E}]\to P\mathbb{E}\left[\mathbb{E}(\sigma^1)-\mathbb{E}(\sigma^B)\right]+(2\beta n)^m, \tag*{(142)} E [ E ] → P E [ E ( σ 1 ) − E ( σ B ) ] + ( 2 β n ) m , (142) E [ ( E − E [ E ] ) 2 ] = ( 2 m ) ! 2 m − 1 m ! ( 1 − ( 1 − 2 β ) m ) n m P . (143) \mathbb{E}\left[(\mathcal{E}-\mathbb{E}[\mathcal{E}])^2\right]=\frac{(2m)!}{2^{m-1}m!}\left(1-(1-2\beta)^m\right)n^mP. \tag*{(143)} E [ ( E − E [ E ] ) 2 ] = 2 m − 1 m ! ( 2 m )! ( 1 − ( 1 − 2 β ) m ) n m P . (143) Since ξ 1 \xi^1 ξ 1 ± 1 \pm1 ± 1 ξ 1 \xi^1 ξ 1
E [ E ( σ 1 ) − E ( σ B ) ] = − 2 m ! N m ⋅ 1 2 m − 1 ∑ j e v e n ( m j ) ∑ k o d d ( j k ) ( 2 β ) k ( 1 − 2 β ) j − k = − m ! N m 2 m − 2 ∑ j e v e n ( m j ) 1 − ( 1 − 4 β ) 2 j 2 = ( − 1 + 1 2 m − 1 ( 2 − 4 β ) m + ( 4 β ) m 2 ) N m m ! = ( − 1 + ( 1 − 2 β ) m + ( 2 β ) m ) N m m ! = : y . (144) \begin{aligned}
\mathbb{E}\left[E(\sigma^1)-E(\sigma^B)\right]
&=-2m!\mathcal{N}_m\cdot\frac{1}{2^{m-1}}\sum_{\substack{j\ \mathrm{even}}}\binom{m}{j}\sum_{\substack{k\ \mathrm{odd}}}\binom{j}{k}(2\beta)^k(1-2\beta)^{j-k}\\
&=-\frac{m!\mathcal{N}_m}{2^{m-2}}\sum_{\substack{j\ \mathrm{even}}}\binom{m}{j}\frac{1-(1-4\beta)^{2j}}{2}\\
&=\left(-1+\frac{1}{2^{m-1}}\frac{(2-4\beta)^m+(4\beta)^m}{2}\right)\mathcal{N}_m m!\\
&=\left(-1+(1-2\beta)^m+(2\beta)^m\right)\mathcal{N}_m m! =: y. \tag*{(144)}
\end{aligned} E [ E ( σ 1 ) − E ( σ B ) ] = − 2 m ! N m ⋅ 2 m − 1 1 j even ∑ ( j m ) k odd ∑ ( k j ) ( 2 β ) k ( 1 − 2 β ) j − k = − 2 m − 2 m ! N m j even ∑ ( j m ) 2 1 − ( 1 − 4 β ) 2 j = ( − 1 + 2 m − 1 1 2 ( 2 − 4 β ) m + ( 4 β ) m ) N m m ! = ( − 1 + ( 1 − 2 β ) m + ( 2 β ) m ) N m m ! =: y . (144) The overall factor of m ! N m m!\mathcal{N}_m m ! N m m ! m! m ! E E E
Let us now combine everything together: we find that with high probability a real codeword is higher energy than our random perturbation towards a seen codeword (E > 0 \mathcal{E}>0 E > 0
P < 1 + o ( 1 ) Δ B ( m − 1 ) ! ( 2 β ) m 1 − ( 2 β ) m − ( 1 − 2 β ) m n m − 1 = : ( 1 + o ( 1 ) ) ⋅ A min ( β ) n m − 1 . (145) P<\frac{1+o(1)}{\Delta_{\mathrm{B}}(m-1)!}\frac{(2\beta)^m}{1-(2\beta)^m-(1-2\beta)^m}n^{m-1}=:(1+o(1))\cdot A_{\min}(\beta)n^{m-1}. \tag*{(145)} P < Δ B ( m − 1 )! 1 + o ( 1 ) 1 − ( 2 β ) m − ( 1 − 2 β ) m ( 2 β ) m n m − 1 =: ( 1 + o ( 1 )) ⋅ A m i n ( β ) n m − 1 . (145) Indeed, the variance of E \mathcal{E} E n m − 1 / 2 n^{m-1/2} n m − 1/2 P ∼ n m − 1 P\sim n^{m-1} P ∼ n m − 1 E [ E ] ∼ n m \mathbb{E}[\mathcal{E}]\sim n^m E [ E ] ∼ n m E [ E ] n − m > 0 \mathbb{E}[\mathcal{E}]n^{-m}>0 E [ E ] n − m > 0 n → ∞ n\to\infty n → ∞
Theorem B.12: In the same setting as Theorem B.10, if A > A max ( β ) A>A_{\max}(\beta) A > A m a x ( β ) 0 < β < γ 0<\beta<\gamma 0 < β < γ
P [ E ^ ( c ) < E ^ ( c + a ) for every a with ∣ a ∣ = β n ] → 1. (146) \mathbb{P}\left[\widehat{E}(c)<\widehat{E}(c+a)\text{ for every }a\text{ with }|a|=\beta n\right]\to1. \tag*{(146)} P [ E ( c ) < E ( c + a ) for every a with ∣ a ∣ = β n ] → 1. (146) Therefore, for sufficiently large A A A E ^ \widehat{E} E
Proof. This proof begins identically to that of Theorem B.10, but we will need to find more sophisticated bounds on the distribution of Y μ Y^\mu Y μ S ⊂ [ n ] S\subset[n] S ⊂ [ n ]
ζ S : = ∑ i ∈ S ζ i . (147) \zeta_S:=\sum_{i\in S}\zeta_i. \tag*{(147)} ζ S := i ∈ S ∑ ζ i . (147) Notice that
Y μ : = ( ξ S c μ − ξ S μ ) m − ( ξ S c μ + ξ S μ ) m . (148) Y^\mu:=(\xi^\mu_{S^c}-\xi^\mu_S)^m-(\xi^\mu_{S^c}+\xi^\mu_S)^m. \tag*{(148)} Y μ := ( ξ S c μ − ξ S μ ) m − ( ξ S c μ + ξ S μ ) m . (148) Using elementary inequalities we find
∣ Y μ ∣ ≤ 2 m ∣ ξ S μ ∣ ( ∣ ξ S μ ∣ + ∣ ξ S c μ ∣ ) m − 1 ≤ 2 m m ∣ ξ S μ ∣ ( ∣ ξ S μ ∣ m − 1 + ∣ ξ S c μ ∣ m − 1 ) . (149) |Y^\mu|\le2m|\xi^\mu_S|\left(|\xi^\mu_S|+|\xi^\mu_{S^c}|\right)^{m-1}\le2^m m|\xi^\mu_S|\left(|\xi^\mu_S|^{m-1}+|\xi^\mu_{S^c}|^{m-1}\right). \tag*{(149)} ∣ Y μ ∣ ≤ 2 m ∣ ξ S μ ∣ ( ∣ ξ S μ ∣ + ∣ ξ S c μ ∣ ) m − 1 ≤ 2 m m ∣ ξ S μ ∣ ( ∣ ξ S μ ∣ m − 1 + ∣ ξ S c μ ∣ m − 1 ) . (149) Now let us consider the L q L^q L q ker ( H ) \ker(H) ker ( H ) b b b ξ \xi ξ
∥ A ( ξ ) ∥ q : = [ 1 2 k ∑ ξ ∈ ker ( H ) ∣ A ( ξ ) ∣ q ] 1 / q . (150) \|A(\xi)\|_q := \left[\frac{1}{2^k}\sum_{\xi\in\ker(H)} |A(\xi)|^q\right]^{1/q}. \tag*{(150)} ∥ A ( ξ ) ∥ q := 2 k 1 ξ ∈ k e r ( H ) ∑ ∣ A ( ξ ) ∣ q 1/ q . (150) Hölder’s inequality then gives
∥ Y ∥ q ≤ 2 m m ∥ ξ S ∥ m q ( ( ∥ ξ S ∥ m q ) m − 1 + ( ∥ ξ S c ∥ m q ) m − 1 ) . (151) \|Y\|_q \le2^m m\|\xi_S\|_{mq}\left(\left(\|\xi_S\|_{mq}\right)^{m-1}+\left(\|\xi_{S^c}\|_{mq}\right)^{m-1}\right). \tag*{(151)} ∥ Y ∥ q ≤ 2 m m ∥ ξ S ∥ m q ( ( ∥ ξ S ∥ m q ) m − 1 + ( ∥ ξ S c ∥ m q ) m − 1 ) . (151) Lemma B.13. The following inequality holds for any q ≥ 2 q\ge2 q ≥ 2 q , n q,n q , n C > 0 C>0 C > 0
∥ ξ S ∥ q ≤ C q ∣ S ∣ . (152) \|\xi_S\|_q \le C\sqrt{q|S|}. \tag*{(152)} ∥ ξ S ∥ q ≤ C q ∣ S ∣ . (152) Proof. This is a useful generalization of Corollary A.16 (which immediately follows from this result by taking S = [ n ] S=[n] S = [ n ] [34 ] :
E [ e t ξ S ] = E [ ∏ i ∈ S ( cosh t + ξ i sinh t ) ] = ( cosh t ) ∣ S ∣ ∑ Λ ⊆ S : Λ ∈ im ( H T ) ( tanh t ) ∣ Λ ∣ < ( cosh t ) ∣ S ∣ ∏ i ∈ S ( 1 + ∑ connected Λ ⊆ S : Λ ∈ im ( H T ) , i ∈ Λ ( tanh t ) ∣ Λ ∣ ) < ( cosh t ) ∣ S ∣ ∏ i ∈ S ( 1 + ∑ s = m n ( e ( m − 1 ) Δ B tanh t ) min ( m , κ s ) ) < exp [ ∣ S ∣ ( log cosh t + ( e ( m − 1 ) Δ B tanh t ) m 1 − e ( m − 1 ) Δ B tanh t ) ] = : e c ( t ) ∣ S ∣ , (153) \begin{aligned}
\mathbb{E}\left[e^{t\xi_S}\right]
&=\mathbb{E}\left[\prod_{i\in S}(\cosh t+\xi_i\sinh t)\right]\\
&=(\cosh t)^{|S|}\sum_{\Lambda\subseteq S:\Lambda\in\operatorname{im}(H^T)}(\tanh t)^{|\Lambda|}\\
&<(\cosh t)^{|S|}\prod_{i\in S}\left(1+\sum_{\substack{\text{connected }\Lambda\subseteq S:\Lambda\in\operatorname{im}(H^T),\\i\in\Lambda}}(\tanh t)^{|\Lambda|}\right)\\
&<(\cosh t)^{|S|}\prod_{i\in S}\left(1+\sum_{s=m}^{n}\left(e(m-1)\Delta_B\tanh t\right)^{\min(m,\kappa_s)}\right)\\
&<\exp\left[|S|\left(\log\cosh t+\frac{\left(e(m-1)\Delta_B\tanh t\right)^m}{1-e(m-1)\Delta_B\tanh t}\right)\right]=:e^{c(t)|S|}, \tag*{(153)}
\end{aligned} E [ e t ξ S ] = E [ i ∈ S ∏ ( cosh t + ξ i sinh t ) ] = ( cosh t ) ∣ S ∣ Λ ⊆ S : Λ ∈ im ( H T ) ∑ ( tanh t ) ∣Λ∣ < ( cosh t ) ∣ S ∣ i ∈ S ∏ 1 + connected Λ ⊆ S : Λ ∈ im ( H T ) , i ∈ Λ ∑ ( tanh t ) ∣Λ∣ < ( cosh t ) ∣ S ∣ i ∈ S ∏ ( 1 + s = m ∑ n ( e ( m − 1 ) Δ B tanh t ) m i n ( m , κ s ) ) < exp [ ∣ S ∣ ( log cosh t + 1 − e ( m − 1 ) Δ B tanh t ( e ( m − 1 ) Δ B tanh t ) m ) ] =: e c ( t ) ∣ S ∣ , (153) with c ( t ) < t 2 c(t)<t^2 c ( t ) < t 2 0 < t < t 0 < 1 0<t<t_0<1 0 < t < t 0 < 1 m > 2 m>2 m > 2 ( e Δ B ( Δ C − 1 ) ) s (e\Delta_B(\Delta_C-1))^s ( e Δ B ( Δ C − 1 ) ) s [34 ] , with m = Δ C m=\Delta_C m = Δ C m m m Theorem A.13 ). We see that
E [ e t ξ S ] ≤ e ∣ S ∣ min ( t , c ( t ) ) ≤ e ∣ S ∣ ⋅ t 2 / t 0 . (154) \mathbb{E}\left[e^{t\xi_S}\right]\le e^{|S|\min(t,c(t))}\le e^{|S|\cdot t^2/t_0}. \tag*{(154)} E [ e t ξ S ] ≤ e ∣ S ∣ m i n ( t , c ( t )) ≤ e ∣ S ∣ ⋅ t 2 / t 0 . (154) Markov’s inequality gives
P [ ∣ ξ S ∣ > x ] ≤ inf t e ∣ S ∣ ⋅ t 2 / t 0 − x t = e − x 2 / ( 2 t 0 ∣ S ∣ ) . (155) \mathbb{P}[|\xi_S|>x]\le\inf_t e^{|S|\cdot t^2/t_0-xt}=e^{-x^2/(2t_0|S|)}. \tag*{(155)} P [ ∣ ξ S ∣ > x ] ≤ t inf e ∣ S ∣ ⋅ t 2 / t 0 − x t = e − x 2 / ( 2 t 0 ∣ S ∣ ) . (155) (B.75) follows from Gaussian-like scaling. More concretely,
∥ ξ S ∥ q = ∫ 0 ∞ d x ( − ∂ x P [ ξ S > x ] ) x q = q ∫ 0 ∞ d x x q − 1 P ( ξ S ≥ x ) ≤ q ∫ 0 ∞ d x x q − 1 e − x 2 / ( 2 t 0 ∣ S ∣ ) ≤ q ( C 0 q ⋅ 2 t 0 ∣ S ∣ ) q / 2 . (156) \|\xi_S\|_q = \int_0^\infty\mathrm{d}x\,(-\partial_x\mathbb{P}[\xi_S>x])x^q = q\int_0^\infty\mathrm{d}x\,x^{q-1}\mathbb{P}(\xi_S\geq x)\leq q\int_0^\infty\mathrm{d}x\,x^{q-1}e^{-x^2/(2t_0|S|)}
\leq q(C_0q\cdot2t_0|S|)^{q/2}. \tag*{(156)} ∥ ξ S ∥ q = ∫ 0 ∞ d x ( − ∂ x P [ ξ S > x ]) x q = q ∫ 0 ∞ d x x q − 1 P ( ξ S ≥ x ) ≤ q ∫ 0 ∞ d x x q − 1 e − x 2 / ( 2 t 0 ∣ S ∣ ) ≤ q ( C 0 q ⋅ 2 t 0 ∣ S ∣ ) q /2 . (156) for an O ( 1 ) O(1) O ( 1 ) C 0 C_0 C 0 q 1 / q → 1 q^{1/q}\to1 q 1/ q → 1 q q q C C C
Now the idea is to use Lemma B.13 to bound the tails of the probability distribution of E \mathcal{E} E [35 ] (we are deliberately simplifying/weakening their results, while maintaining sufficiency for our needs):
Theorem B.14: Let X 1 , … , X P X_1,\ldots,X_P X 1 , … , X P E [ X 1 ] = 0 \mathbb{E}[X_1]=0 E [ X 1 ] = 0 0 < α < 1 0<\alpha<1 0 < α < 1
P ( ∣ X 1 ∣ > x ) ≤ 2 exp [ − ( x x 0 ) α ] . (157) \mathbb{P}(|X_1|>x)\leq2\exp\left[-\left(\frac{x}{x_0}\right)^\alpha\right]. \tag*{(157)} P ( ∣ X 1 ∣ > x ) ≤ 2 exp [ − ( x 0 x ) α ] . (157) Then there exists a function F ( α ) \mathcal{F}(\alpha) F ( α ) α > 0 \alpha>0 α > 0 t > 0 t>0 t > 0
P ( ∣ ∑ i = 1 P X i ∣ > F ( α ) ( t 1 / α + P t ) x 0 ) ≤ 2 e − t . (158) \mathbb{P}\left(\left|\sum_{i=1}^{P}X_i\right|>\mathcal{F}(\alpha)\left(t^{1/\alpha}+\sqrt{Pt}\right)x_0\right)\leq2e^{-t}. \tag*{(158)} P ( i = 1 ∑ P X i > F ( α ) ( t 1/ α + P t ) x 0 ) ≤ 2 e − t . (158) The strategy is to apply Theorem B.14 as follows: write
Y ~ ( ξ ) : = Y ( ξ ) − y (159) \widetilde{Y}(\xi):=Y(\xi)-y \tag*{(159)} Y ( ξ ) := Y ( ξ ) − y (159) where y < 0 y<0 y < 0 E [ Y ~ ] = 0 \mathbb{E}[\widetilde{Y}]=0 E [ Y ] = 0
∥ Y ~ ∥ q ≤ ∥ Y ∥ q + y ≤ 2 ∥ Y ∥ q . (160) \|\widetilde{Y}\|_q\leq\|Y\|_q+y\leq2\|Y\|_q. \tag*{(160)} ∥ Y ∥ q ≤ ∥ Y ∥ q + y ≤ 2∥ Y ∥ q . (160) Next, combining Lemma B.13 with (B.74) and the fact that max ( ∣ S ∣ , ∣ S c ∣ ) ≤ n \max(|S|,|S^c|)\leq n max ( ∣ S ∣ , ∣ S c ∣ ) ≤ n
∥ Y ~ ∥ q ≤ 2 ∥ Y ∥ q ≤ 2 m ( 2 C ) m q m / 2 n ( m − 1 ) / 2 ∣ S ∣ = : C ′ n ( m − 1 ) / 2 ∣ S ∣ ⋅ q m / 2 . (161) \|\widetilde{Y}\|_q\leq2\|Y\|_q\leq2m(2C)^m q^{m/2}n^{(m-1)/2}\sqrt{|S|}=:C'n^{(m-1)/2}\sqrt{|S|}\cdot q^{m/2}. \tag*{(161)} ∥ Y ∥ q ≤ 2∥ Y ∥ q ≤ 2 m ( 2 C ) m q m /2 n ( m − 1 ) /2 ∣ S ∣ =: C ′ n ( m − 1 ) /2 ∣ S ∣ ⋅ q m /2 . (161) Then we have the following useful lemma [36 ] :
Lemma B.15: If ∥ X 1 ∥ q ≤ K q 1 / α \|X_1\|_q\leq Kq^{1/\alpha} ∥ X 1 ∥ q ≤ K q 1/ α q q q
x 0 ≤ ( 2 e log 2 ) 1 / α K . (162) x_0\leq\left(\frac{2e}{\log2}\right)^{1/\alpha}K. \tag*{(162)} x 0 ≤ ( log 2 2 e ) 1/ α K . (162) We now combine Lemma B.15 with (B.81) and (B.84) to find, as n → ∞ n \to\infty n → ∞ P = A n m − 1 P = An^{m-1} P = A n m − 1 Y ~ \widetilde{Y} Y α = 2 / m \alpha= 2/m α = 2/ m
P [ ∣ ∑ μ = 2 P Y μ − ( P − 1 ) y ∣ > C n ( m − 1 ) / 2 ∣ S ∣ ( P t + t m / 2 ) ] ≤ 2 e − t (163) \mathbb{P}\left[\left|\sum_{\mu=2}^{P}Y^\mu-(P-1)y\right|>Cn^{(m-1)/2}\sqrt{|S|}\left(\sqrt{Pt}+t^{m/2}\right)\right]\leq2e^{-t} \tag*{(163)} P [ μ = 2 ∑ P Y μ − ( P − 1 ) y > C n ( m − 1 ) /2 ∣ S ∣ ( P t + t m /2 ) ] ≤ 2 e − t (163) with
C : = 2 F ( 2 m ) C ′ . (164) C:=2F\left(\frac{2}{m}\right)C'. \tag*{(164)} C := 2 F ( m 2 ) C ′ . (164) So the tail bound (B.86) is strong when we set t = τ ∣ S ∣ t=\tau|S| t = τ ∣ S ∣ τ \tau τ ∣ S ∣ = β n |S|=\beta n ∣ S ∣ = β n ∣ S ∣ |S| ∣ S ∣
e − τ β n ( n ∣ S ∣ ) ≪ 1 (165) e^{-\tau\beta n}\binom{n}{|S|}\ll1 \tag*{(165)} e − τ β n ( ∣ S ∣ n ) ≪ 1 (165) or, recalling the binary entropy function h h h
τ β > h ( β ) . (166) \tau\beta>h(\beta). \tag*{(166)} τ β > h ( β ) . (166) Note that since h ( β ) ∼ − β log β h(\beta)\sim-\beta\log\beta h ( β ) ∼ − β log β β → 0 \beta\to0 β → 0 τ \tau τ β \beta β
In any event, let us finalize things. For τ \tau τ
0 > ( P − 1 ) y + C n m / 2 β ( P τ β n + ( τ β n ) m / 2 ) + ( 2 β n ) m , (167) 0>(P-1)y+Cn^{m/2}\sqrt{\beta}\left(\sqrt{P\tau\beta n}+(\tau\beta n)^{m/2}\right)+(2\beta n)^m, \tag*{(167)} 0 > ( P − 1 ) y + C n m /2 β ( P τ β n + ( τ β n ) m /2 ) + ( 2 β n ) m , (167) which would ensure that the cutoff in (B.86), along with the positive energy gain from Y 1 Y^1 Y 1 E > 0 \mathcal{E}>0 E > 0 μ = 2 , … , P \mu=2,\ldots,P μ = 2 , … , P E ^ \widehat{E} E
y ≥ ( 1 − 2 δ ) Δ B ⋅ β n , (168) y\geq(1-2\delta)\Delta_{\mathrm{B}}\cdot\beta n, \tag*{(168)} y ≥ ( 1 − 2 δ ) Δ B ⋅ β n , (168) for any δ < 1 / Δ B \delta<1/\Delta_{\mathrm{B}} δ < 1/ Δ B β < γ \beta<\gamma β < γ Theorem A.11 ensures we have a ( γ , δ ) (\gamma,\delta) ( γ , δ ) n → ∞ n\to\infty n → ∞
( 1 − 2 δ ) Δ B β ⋅ A > C β ( A h ( β ) + h ( β ) m / 2 ) + ( 2 β ) m (169) (1-2\delta)\Delta_{\mathrm{B}}\beta\cdot A>C\sqrt{\beta}\left(\sqrt{Ah(\beta)}+h(\beta)^{m/2}\right)+(2\beta)^m \tag*{(169)} ( 1 − 2 δ ) Δ B β ⋅ A > C β ( A h ( β ) + h ( β ) m /2 ) + ( 2 β ) m (169) Solve this quadratic inequality for 0 < β < γ 0<\beta<\gamma 0 < β < γ A > A max ( β ) A>A_{\max}(\beta) A > A m a x ( β )
Theorem B.10 and Theorem B.12 together imply a clear crossover when P = Θ ( n m − 1 ) P = \Theta(n^{m-1}) P = Θ ( n m − 1 )
Let us now confirm that, as claimed in the main text, codewords are lower energy than random configurations once P ∼ n m − 2 P \sim n^{m-2} P ∼ n m − 2
Proposition B.16: Starting at any codeword and flipping a random set S S S unseen codeword, we find (using the notation of Theorem B.10 ) that E ^ ( σ B ) > E ^ ( σ 1 ) \hat{E}(\sigma^{B}) > \hat{E}(\sigma^{1}) E ^ ( σ B ) > E ^ ( σ 1 ) n → ∞ n \to\infty n → ∞ P = n m − 2 + ϵ P = n^{m-2+\epsilon} P = n m − 2 + ϵ ϵ > 0 \epsilon> 0 ϵ > 0
Proof. We follow the proof of Theorem B.10 , but if the bits we flip point us towards an unseen codeword, we simply lose the deterministic ( 2 β n ) m (2\beta n)^m ( 2 β n ) m
∣ E [ E ] ∣ Var ( E ) = Δ B ( m − 1 ) ! ( 1 − ( 1 − 2 β ) m − ( 2 β ) m ) 2 1 − m ( 2 m ) ! / m ! ( 1 − ( 1 − 2 β ) m ) P n m − 2 ∼ n ϵ / 2 . (170) \frac{|\mathbb{E}[\mathcal{E}]|}{\sqrt{\operatorname{Var}(\mathcal{E})}} = \frac{\Delta_B(m-1)!(1-(1-2\beta)^m-(2\beta)^m)}{\sqrt{2^{1-m}(2m)!/m!(1-(1-2\beta)^m)}}\sqrt{\frac{P}{n^{m-2}}} \sim n^{\epsilon/2}. \tag*{(170)} Var ( E ) ∣ E [ E ] ∣ = 2 1 − m ( 2 m )! / m ! ( 1 − ( 1 − 2 β ) m ) Δ B ( m − 1 )! ( 1 − ( 1 − 2 β ) m − ( 2 β ) m ) n m − 2 P ∼ n ϵ /2 . (170) Since E \mathcal{E} E sign ( E ) < 0 \operatorname{sign}(\mathcal{E}) < 0 sign ( E ) < 0 n → ∞ n \to\infty n → ∞
Before P ∼ n m − 2 P \sim n^{m-2} P ∼ n m − 2
It would be very interesting to study the “mixed memories”, which have been studied in dense associative memories trained on random codewords [28 ] , to the architecture trained on XORSAT codewords. We leave this to future work.
Learning latent variables
With a sensible modification, the same TDenseAM architecture described above can (asymptotically) optimally recover latent variables – namely, degrees of freedom which are not shown to the model, but which sparsify the energy E ^ \hat{E} E ^ not achievable for arbitrary problems [37 ] . However, random LDPC codes are a setting where latent variables are often easy to learn, and we will indeed provide some provable guarantees on their learnability in what follows.
Let us first set up the discussion at a high level. Divide up the bits of an LDPC code into observed variables x 1 , … , x n − n ˉ x_1,\ldots,x_{n-\bar{n}} x 1 , … , x n − n ˉ h n − n ˉ + 1 , … , h n h_{n-\bar{n}+1},\ldots,h_n h n − n ˉ + 1 , … , h n n ˉ < n \bar{n}<n n ˉ < n h h h E ^ \hat{E} E ^
As the LDPC problem is perfectly suited to TDenseAM, as discussed above, this will indeed be possible in many circumstances. The strategy that we will explore is to identify latent variables by their observable shadows, which are defined as follows:
Definition C.1 (Observable m m m h α h_\alpha h α m m m p p p p ≥ 2 p \ge2 p ≥ 2 A , B ⊂ { 1 , … , n − n ˉ } A,B \subset\{1,\ldots,n-\bar{n}\} A , B ⊂ { 1 , … , n − n ˉ } ∣ A ∣ , ∣ B ∣ ≤ m − 1 |A|,|B| \le m-1 ∣ A ∣ , ∣ B ∣ ≤ m − 1 α ∪ A , α ∪ B ∈ im ( H T ) \alpha\cup A,\alpha\cup B \in\operatorname{im}(H^{\mathsf{T}}) α ∪ A , α ∪ B ∈ im ( H T )
Before continuing, let us make a few caveats. (1) h h h n ˉ = Θ ( n ) \bar{n} = \Theta(n) n ˉ = Θ ( n )
Returning to Definition C.1 , the key observation is that x A + x B = 0 x_A + x_B = 0 x A + x B = 0 2 m − 2 2m - 2 2 m − 2
Algorithm C.2 (p p p p p p V 0 = [ n − n ˉ ] \mathcal{V}_0 = [n - \bar{n}] V 0 = [ n − n ˉ ] P P P ≤ m \le m ≤ m H 0 H_0 H 0 t = 0 t = 0 t = 0
Run TDenseAM to learn all parity-checks of weight ≤ 2 m − 2 \le2m - 2 ≤ 2 m − 2 H t ′ H'_t H t ′
Z t = span ( H t ′ ) / span ( H t ) (171) Z_t = \operatorname{span}(H'_t)/\operatorname{span}(H_t) \tag*{(171)} Z t = span ( H t ′ ) / span ( H t ) (171) denote genuinely new higher-order constraints discovered.
Suppose there exist p ( p − 1 ) / 2 p(p - 1)/2 p ( p − 1 ) /2 w A ∈ F 2 n ˉ / span ( H t ) w_A \in\mathbb{F}_2^{\bar{n}}/\operatorname{span}(H_t) w A ∈ F 2 n ˉ / span ( H t ) w A w_A w A ≤ ( m − 1 ) \le(m - 1) ≤ ( m − 1 ) w A + w B ∈ span ( H t ′ ) / span ( H t ) w_A + w_B \in\operatorname{span}(H'_t)/\operatorname{span}(H_t) w A + w B ∈ span ( H t ′ ) / span ( H t ) latent bit h h h
h + w A = 0. (172) h + w_A = 0. \tag*{(172)} h + w A = 0. (172) In other words, h h h p p p Definition C.1 ).
If no h h h h h h V t + 1 : = V t ∪ { h } \mathcal{V}_{t+1} := \mathcal{V}_t \cup\{h\} V t + 1 := V t ∪ { h } H t H_t H t H t + 1 H_{t+1} H t + 1 t → t + 1 t \to t + 1 t → t + 1
The 2-latent TDenseAM is an aggressive learner, but will necessarily introduce many redundant latent variables. As a simple example, if m = 3 m = 3 m = 3 x 1 + x 2 + x 3 + x 4 = 0 x_1 + x_2 + x_3 + x_4 = 0 x 1 + x 2 + x 3 + x 4 = 0 x 1 + x 2 + h = x 3 + x 4 + h = 0 x_1 + x_2 + h = x_3 + x_4 + h = 0 x 1 + x 2 + h = x 3 + x 4 + h = 0 x 1 + x 3 + h ′ = x 2 + x 4 + h ′ = 0 x_1 + x_3 + h' = x_2 + x_4 + h' = 0 x 1 + x 3 + h ′ = x 2 + x 4 + h ′ = 0 [25 , 26 ] . In the context of the XORSAT problem, we can prove that the 3-latent TDenseAM is capable of learning an extensive number of latent variables, with high probability, on a random realization of the problem.
Theorem C.3. Consider a random ( Δ B , Δ C ) (\Delta_B, \Delta_C) ( Δ B , Δ C ) 5 ≤ Δ B < Δ C 5 \le\Delta_B < \Delta_C 5 ≤ Δ B < Δ C 6 ≤ Δ C ≤ 9 6 \le\Delta_C \le9 6 ≤ Δ C ≤ 9 Δ B = 5 \Delta_B = 5 Δ B = 5 B = B o b s ⊔ B l a t B = B_{\mathrm{obs}} \sqcup B_{\mathrm{lat}} B = B obs ⊔ B lat O ( 1 ) O(1) O ( 1 ) γ \gamma γ n n n ∣ B l a t ∣ < γ n \lvert B_{\mathrm{lat}}\rvert< \gamma n ∣ B lat ∣ < γ n n → ∞ n \to\infty n → ∞
P = ( 1 + ϵ ) 4 ( Δ C − 1 ) α 2 log n (173) P = (1 + \epsilon) \frac{4(\Delta_C - 1)}{\alpha^2} \log n \tag*{(173)} P = ( 1 + ϵ ) α 2 4 ( Δ C − 1 ) log n (173) random codewords as training examples, for any ϵ > 0 \epsilon> 0 ϵ > 0
Proof. Theorem A.11 shows that a random LDPC code is a ( γ , δ ) (\gamma, \delta) ( γ , δ ) O ( 1 ) O(1) O ( 1 ) γ \gamma γ δ > 1 / Δ B \delta> 1/\Delta_B δ > 1/ Δ B n → ∞ n \to\infty n → ∞ ( γ , δ ) (\gamma, \delta) ( γ , δ ) γ \gamma γ δ \delta δ B l a t B_{\mathrm{lat}} B lat
Lemma C.4. Define a clean 3-shadow as a triple of observed parity-checks of size 2 Δ C − 2 2\Delta_C - 2 2 Δ C − 2
x A + x B = x B + x C = x C + x A = 0 (174) x_A + x_B = x_B + x_C = x_C + x_A = 0 \tag*{(174)} x A + x B = x B + x C = x C + x A = 0 (174) with sets ∣ A ∣ = ∣ B ∣ = ∣ C ∣ = Δ C − 1 \lvert A\rvert= \lvert B\rvert= \lvert C\rvert= \Delta_C - 1 ∣ A ∣ = ∣ B ∣ = ∣ C ∣ = Δ C − 1 ( γ , δ ) (\gamma, \delta) ( γ , δ )
δ < Δ C + 2 6 Δ C , (175) \delta< \frac{\Delta_C + 2}{6\Delta_C}, \tag*{(175)} δ < 6 Δ C Δ C + 2 , (175) a clean 3-shadow certifies the existence of a unique (latent) bit h 0 h_0 h 0
x A + h 0 = x B + h 0 = x C + h 0 = 0. (176) x_A + h_0 = x_B + h_0 = x_C + h_0 = 0. \tag*{(176)} x A + h 0 = x B + h 0 = x C + h 0 = 0. (176) Proof. From Theorem A.13 , we see that if ∣ H T s ∣ = O ( 1 ) \lvert H^{\mathsf T}s\rvert= O(1) ∣ H T s ∣ = O ( 1 ) ∣ s ∣ = O ( 1 ) \lvert s\rvert= O(1) ∣ s ∣ = O ( 1 ) n → ∞ n \to\infty n → ∞ Definition A.7 applies: for any ∣ s ∣ < γ n \lvert s\rvert< \gamma n ∣ s ∣ < γ n 2 Δ C − 2 2\Delta_C - 2 2 Δ C − 2
∣ H T s ∣ = 2 Δ C − 2 ≥ Δ C ( 1 − 2 δ ) ∣ s ∣ . (177) \lvert H^{\mathsf T}s\rvert= 2\Delta_C - 2 \ge\Delta_C(1 - 2\delta)\lvert s\rvert. \tag*{(177)} ∣ H T s ∣ = 2 Δ C − 2 ≥ Δ C ( 1 − 2 δ ) ∣ s ∣ . (177) Clearly we must have ∣ s ∣ ≥ 2 \lvert s\rvert\ge2 ∣ s ∣ ≥ 2 ∣ s ∣ = 3 \lvert s\rvert= 3 ∣ s ∣ = 3 2 Δ C − 2 2\Delta_{\mathrm{C}}-2 2 Δ C − 2
Now, suppose that we see the pattern (C.4). There are exactly two ways this can happen. The first is that we see the pattern (C.6), where h 0 h_0 h 0
A = A 0 ⊔ { x , y } , (178) A = A_0 \sqcup\{x,y\}, \tag*{(178)} A = A 0 ⊔ { x , y } , (178) B = B 0 ⊔ { x , z } , (179) B = B_0 \sqcup\{x,z\}, \tag*{(179)} B = B 0 ⊔ { x , z } , (179) C = C 0 ⊔ { y , z } . (180) C = C_0 \sqcup\{y,z\}. \tag*{(180)} C = C 0 ⊔ { y , z } . (180) Because by assumption we have seen 3 ( Δ C − 1 ) 3(\Delta_{\mathrm{C}}-1) 3 ( Δ C − 1 )
It is clear that seeing a clean 3-shadow of a latent variable is a guarantee (with high probability) that we will correctly infer the intended latent variable. Now we prove that:
Lemma C.5: If ∣ B l a t ∣ < γ n |B_{\mathrm{lat}}| < \gamma n ∣ B lat ∣ < γ n n → ∞ n \to\infty n → ∞
Note that we will apply this lemma at each iteration of Algorithm C.2, so B l a t B_{\mathrm{lat}} B lat
Proof. If the latent subgraph of the LDPC code was a tree, this property would follow immediately, because Δ B ≥ 5 \Delta_{\mathrm{B}} \ge5 Δ B ≥ 5
Let B s h a r e ⊆ B B_{\mathrm{share}} \subseteq B B share ⊆ B
B s h a r e : = { b ∈ B : ∣ ∂ b ∩ ∂ b ′ ∣ > 1 for some b ≠ b ′ ∈ B } . (181) B_{\mathrm{share}} := \{b \in B : |\partial b \cap\partial b'| > 1 \text{ for some } b \ne b' \in B\}. \tag*{(181)} B share := { b ∈ B : ∣ ∂ b ∩ ∂ b ′ ∣ > 1 for some b = b ′ ∈ B } . (181) We observe that b ∈ B s h a r e b \in B_{\mathrm{share}} b ∈ B share b b b B s h a r e B_{\mathrm{share}} B share B s h a r e B_{\mathrm{share}} B share ∼ n − 1 \sim n^{-1} ∼ n − 1 O ( 1 ) O(1) O ( 1 ) r 0 r_0 r 0 B s h a r e B_{\mathrm{share}} B share r 0 r_0 r 0
With this in mind, we now provide a proof by contradiction for the lemma. Suppose that the latent set had no clean 3-shadows. Without loss of generality, we may assume that B l a t B_{\mathrm{lat}} B lat B l a t B_{\mathrm{lat}} B lat B l a t ∖ B s h a r e B_{\mathrm{lat}} \setminus B_{\mathrm{share}} B lat ∖ B share B l a t ∩ B s h a r e B_{\mathrm{lat}} \cap B_{\mathrm{share}} B lat ∩ B share
Δ B ( 1 − 2 δ ) ∣ B l a t ∣ ≤ ∣ ∂ u B l a t ∣ ≤ 2 ( ∣ B l a t ∣ − ∣ B l a t ∩ B s h a r e ∣ ) + 3 ∣ B l a t ∩ B s h a r e ∣ = 2 ∣ B l a t ∣ + ∣ B l a t ∩ B s h a r e ∣ . (182) \Delta_{\mathrm{B}}(1-2\delta)|B_{\mathrm{lat}}| \leq|\partial_u B_{\mathrm{lat}}| \leq2\left(|B_{\mathrm{lat}}|-|B_{\mathrm{lat}} \cap B_{\mathrm{share}}|\right)+3|B_{\mathrm{lat}} \cap B_{\mathrm{share}}|
=2|B_{\mathrm{lat}}|+|B_{\mathrm{lat}} \cap B_{\mathrm{share}}|. \tag*{(182)} Δ B ( 1 − 2 δ ) ∣ B lat ∣ ≤ ∣ ∂ u B lat ∣ ≤ 2 ( ∣ B lat ∣ − ∣ B lat ∩ B share ∣ ) + 3∣ B lat ∩ B share ∣ = 2∣ B lat ∣ + ∣ B lat ∩ B share ∣. (182) Notice that as long as we enforce (C.5) and Δ B ≥ 5 \Delta_{\mathrm{B}} \geq5 Δ B ≥ 5 Δ C ≥ 6 \Delta_{\mathrm{C}} \geq6 Δ C ≥ 6
Δ B ( 1 − 2 δ ) ≥ 5 ( 1 − 8 18 ) = 25 9 > 2. (183) \Delta_{\mathrm{B}}(1-2\delta) \geq5\left(1-\frac{8}{18}\right)=\frac{25}{9}>2. \tag*{(183)} Δ B ( 1 − 2 δ ) ≥ 5 ( 1 − 18 8 ) = 9 25 > 2. (183) Therefore, (C.10) can only hold if
∣ B l a t ∣ ≤ 9 7 ∣ B l a t ∩ B s h a r e ∣ . (184) |B_{\mathrm{lat}}| \leq\frac{9}{7}|B_{\mathrm{lat}} \cap B_{\mathrm{share}}|. \tag*{(184)} ∣ B lat ∣ ≤ 7 9 ∣ B lat ∩ B share ∣. (184) Let us analyze (C.12) on each connected component of B l a t B_{\mathrm{lat}} B lat B s h a r e B_{\mathrm{share}} B share Δ B ≥ 5 \Delta_{\mathrm{B}} \geq5 Δ B ≥ 5 B s h a r e B_{\mathrm{share}} B share B s h a r e B_{\mathrm{share}} B share 2 ≤ ∣ B l a t ∣ < 18 / 7 < 3 2 \leq|B_{\mathrm{lat}}| < 18/7 < 3 2 ≤ ∣ B lat ∣ < 18/7 < 3 ( Δ B − 2 ) ≥ 3 (\Delta_{\mathrm{B}}-2) \geq3 ( Δ B − 2 ) ≥ 3 B s h a r e B_{\mathrm{share}} B share B l a t B_{\mathrm{lat}} B lat ≥ r 0 \geq r_0 ≥ r 0 r 0 r_0 r 0
∣ B l a t ∩ B s h a r e ∣ ∣ B l a t ∣ ≤ 2 m 2 m + ( m − 1 ) r 0 (185) \frac{|B_{\mathrm{lat}} \cap B_{\mathrm{share}}|}{|B_{\mathrm{lat}}|} \leq\frac{2m}{2m+(m-1)r_0} \tag*{(185)} ∣ B lat ∣ ∣ B lat ∩ B share ∣ ≤ 2 m + ( m − 1 ) r 0 2 m (185) arises when B l a t B_{\mathrm{lat}} B lat m m m B s h a r e B_{\mathrm{share}} B share r 0 r_0 r 0 r 0 = 2 r_0=2 r 0 = 2 m > 1 m>1 m > 1 □ \square □
It is now clear that the strict latent TDenseAM will provably converge by learning, one at a time, the latent bits by detecting their clean 3-shadows. Lemma C.4 requires the condition (C.5) which enforces Δ C < 10 \Delta_{\mathrm{C}}<10 Δ C < 10 Δ B = 5 \Delta_{\mathrm{B}}=5 Δ B = 5 Δ B > 5 \Delta_{\mathrm{B}}>5 Δ B > 5 ( 2 Δ C − 2 ) (2\Delta_{\mathrm{C}}-2) ( 2 Δ C − 2 ) n → ∞ n \to\infty n → ∞ □ \square □
