# Tight Time-Space Lower Bounds for Constant-Pass Learning

Xin Lyu111Department of Computer Science, University of California, Berkeley.
Email<EMAIL_ADDRESS>Supported by Avishay Tal’s Sloan Research
Fellowship and NSF CAREER Award CCF-2145474, and Jelani Nelson’s ONR grant
N00014-18-1-2562. Avishay Tal222Department of Computer Science, University of
California, Berkeley. Email<EMAIL_ADDRESS>Supported by a Sloan Research
Fellowship and NSF CAREER Award CCF-2145474. Hongxun Wu333Department of
Computer Science, University of California, Berkeley. Email:
<EMAIL_ADDRESS>Supported by Avishay Tal’s Sloan Research Fellowship, NSF
CAREER Award CCF-2145474, and Jelani Nelson’s ONR grant N00014-18-1-2562.
Junzhao Yang444Institute for Interdisciplinary Information Sciences, Tsinghua
University. Email<EMAIL_ADDRESS>
###### Abstract

In his breakthrough paper, Raz showed that any parity learning algorithm
requires either quadratic memory or an exponential number of samples [FOCS’16,
JACM’19]. A line of work that followed extended this result to a large class
of learning problems. Until recently, all these results considered learning in
the streaming model, where each sample is drawn independently, and the learner
is allowed a single pass over the stream of samples. Garg, Raz, and Tal
[CCC’19] considered a stronger model, allowing multiple passes over the
stream. In the $2$-pass model, they showed that learning parities of size $n$
requires either a memory of size $n^{1.5}$ or at least $2^{\sqrt{n}}$ samples.
(Their result also generalizes to other learning problems.)

In this work, for any constant $q$, we prove tight memory-sample lower bounds
for any parity learning algorithm that makes $q$ passes over the stream of
samples. We show that such a learner requires either $\Omega(n^{2})$ memory
size or at least $2^{\Omega(n)}$ samples. Beyond establishing a tight lower
bound, this is the first non-trivial lower bound for $q$-pass learning for any
$q\geq 3$. Similar to prior work, our results extend to any learning problem
with many nearly-orthogonal concepts.

We complement the lower bound with an upper bound, showing that parity
learning with $q$ passes can be done efficiently with $O(n^{2}/\log q)$
memory.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
  2. 2 Technical Overview
    1. 2.1 Recap of the One-Pass Lower Bound
    2. 2.2 The Proof Framework: Two Passes
    3. 2.3 New Ingredient: Bias Counters
    4. 2.4 Transfer Lemma
    5. 2.5 Extending to Multiple Passes
    6. 2.6 Organization of the Proofs
  3. 3 Preliminaries
    1. 3.1 Notation
    2. 3.2 Norms and Inner Products
    3. 3.3 Learning Tasks and $L2$-Extractors
    4. 3.4 Computational Model
  4. 4 Setup for Two Passes
    1. 4.1 Modifying the Program
    2. 4.2 The First Pass
    3. 4.3 The Second Pass
    4. 4.4 Two-Pass Main Result
  5. 5 Potential Analysis
    1. 5.1 Definition and Overview
    2. 5.2 Evolution of Potential
    3. 5.3 Potential Grows Slowly
    4. 5.4 Upper Bounding the Probability of $\mathrm{cnt}_{\mathrm{bias}}$ Overflow
  6. 6 Transfer Lemma
    1. 6.1 Overview
    2. 6.2 Proof of the Transfer Lemma
  7. 7 Proof of the Two-Pass Result
    1. 7.1 Analyzing the Success Probability
  8. 8 Setup for Multiple Passes
    1. 8.1 Modifying the Program
    2. 8.2 Stopping Rules
    3. 8.3 Multi-Pass Learning: Main Result
  9. 9 Multi-Pass Transfer Lemma
    1. 9.1 Overview
    2. 9.2 Extending Good Events to Multi-Pass
    3. 9.3 Proof of the Multi-Pass Transfer Lemma
  10. 10 Tight Lower Bound for Constant-Pass Learning
    1. 10.1 Potential Analysis
    2. 10.2 Proof of the Main Result
  11. 11 Acknowledgement
  12. A Probability of Reaching Significant States
    1. A.1 Setup
    2. A.2 Understanding $\mathbb{P}_{x|v}$ and $\mathbb{P}_{x|e}$
    3. A.3 Bounding the Norm of $\mathbb{P}_{v_{1}\to s}$
    4. A.4 Measuring the Progress
  13. B Missing Proofs for Multi-Pass
    1. B.1 Fixing the Randomness
    2. B.2 Potential Analysis for Multi-Pass
  14. C A Learning Algorithm with Multiple Passes
    1. C.1 Setup
    2. C.2 Block circuit
    3. C.3 Proof of Theorem 7

##  1 Introduction

A growing recent line of works studied the efficiency of learning under memory
constraints [Sha14, SVW16, Raz16, KRT17, MT17, MM17, Raz17, MM18, GRT18,
BGY18, DS18, GRT19, SSV19, DKS19, GKR20, GKLR21, MSSV22, LRZ23]. This study
was initiated by the beautiful works of Shamir [Sha14] and Steinhardt,
Valiant, and Wager [SVW16]. Specifically, Steinhardt et al. [SVW16]
conjectured that any learning parity algorithm requires either quadratic
memory or an exponential number of examples. In a breakthrough result, Raz
[Raz16] proved this conjecture. While we have two simple algorithms for parity
learning: (i) Gaussian Elimination that uses $O(n^{2})$ space and $O(n)$
samples, and (ii) Brute-force search that uses $O(n)$ space and $O(2^{n})$
samples, Raz showed that there is no learning algorithm that uses $o(n^{2})$
space and $2^{o(n)}$ samples [Raz16]. This demonstrated that efficient
learning requires a large memory – in this case, at least $\Omega(n^{2})$
memory bits.

Follow-up work extended and generalized the lower bounds techniques to a wide
array of learning problems such as learning sparse parities, learning DNFs,
learning decision trees, learning juntas, [KRT17, GRT18] learning low-degree
polynomials [BGY18, GRT18], learning from sparse equations and low-degree
equations [GRT18], learning codewords from random coordinates [Raz17, MM18,
GRT18], learning parities with noisy inputs [GKLR21], and more. In all the
above, it is shown that any learning algorithm for the corresponding concept
class on input size $n$, requires either super-linear size memory, or super
polynomial number of samples. Work towards a tight characterization of memory-
samples lower bounds was done by [GLM20], but such a full characterization is
still missing with polynomial gaps on the memory required for efficiently
learning classical concepts classes such as juntas, DNFs, decision trees
[KRT17].

Most of the works above modeled the learner as a streaming algorithm,
observing the random labeled examples one at a time. More precisely, the lower
bounds proved were in the stronger model of read-once branching programs that
captures bounded-space streaming computation in a non-uniform setting. Recent
exciting work by [LRZ23] extended the model to include quantum memory in
addition to classical memory and showed that Raz’s result extends even if the
learner has additionally $o(n)$ qubits at its disposal.

Dagan and Shamir [DS18] and Garg, Raz, and Tal [GRT19] considered the model of
multi-pass learners. In this model, the learner makes several passes over the
stream of examples in the same order. Dagan and Shamir [DS18] proved
polynomial lower bounds on the number of samples in such setting. Garg, Raz
and Tal [GRT19] obtained a subexponential lower bound on the number of samples
$2^{\Omega(\sqrt{n})}$ for any _two-pass_ learning parity algorithm with
$o(n^{1.5})$ space. The result more generally implies lower bounds for any of
the aforementioned learning problems. Indeed, the lower bounds are proved in
the extractor-based framework of [GRT18] and all the aforementioned learning
problems fall under this framework.

Despite the strong lower bound, the GRT result was not known to be tight for
two-pass learning, as no efficient algorithm with $o(n^{2})$ space was known
in this setting. Moreover, their result did not translate to the multi-pass
setting with more than two passes, and, as indicated in their paper, some of
their techniques are quite delicate, and it is far from clear how to extend
them to more than two passes [GRT19].

Proving lower bounds for multi-pass learners is much more challenging, as such
learners can store information during the first pass that would make examples
in the second pass somewhat predictable, correlated with one another, or
correlated with the hidden vector.

One might wonder whether more passes can help in learning. Indeed, when the
number of passes is quasi-polynomial, a parity learning algorithm with
$n^{O(\log n)}$ passes, $n^{O(\log n)}$ samples, and $O(n)$ space follows from
the following two facts: (i) solving linear equations can be done in
$O(\log^{2}n)$ depth [Csa76] (ii) Barrington’s simulation of $O(\log^{2}n)$
depth by length $n^{O(\log n)}$ read-once branching programs [Bar86].

###  1.1 Our Results

We study time-space lower bounds for multi-pass learning problems. We provide
a nearly tight lower bound for two-pass learning parity algorithms:

######  Theorem 1 (Informal version of Theorem 5).

Any two-pass algorithm for $n$-bit parity learning requires either
$\Omega(n^{2})$ bits of memory or $2^{\Omega(n)}$ many samples. Otherwise, the
algorithm succeeds with probability at most $2^{-\Omega(n)}$.

Moreover, our results generalize to any constant-pass learner and, moreover,
imply nearly similar bounds for any algorithm with at most $o(\log\log n)$
passes.

######  Theorem 2 (Informal version of Theorem 6).

There is a universal constant $C>0$ such that the following holds. For any
$q\geq 2$, letting $c_{q}=C\cdot 100^{3^{q}}$, any $q$-pass algorithm for
$n$-bit parity learning requires either $n^{2}/c_{q}$ bits of memory or
$\exp({n/c_{q}})$ many samples. Otherwise, the algorithm succeeds with
probability at most $2^{-(n/c_{q})}$.

We stress that the multi-pass lower bound is not a direct generalization of
the two-pass one. It requires us to revisit a key technique in the two-pass
proof (which we call the “transfer lemma”), and extend the technique to the
multi-pass case with a significantly more involved argument.

##### Extractor-based framework.

Our results apply more generally to any learning problem with many nearly
pairwise orthogonal concepts (i.e. concepts that agree on roughly half of the
inputs). Alternatively, to any learning problem whose associated matrix (as
defined in [Raz17]) exhibits an extractor-property [GRT18], as defined next.

Let $A$ be a finite domain, and let $X$ be a concept class over $A$, where
each $x\in X$ represents a function (or concept) mapping $A$ to $\\{-1,1\\}$.
We naturally associate with the concept class a matrix
$M\in\\{-1,1\\}^{A\times X}$ whose rows correspond to samples and columns
correspond to concepts/functions. Then, $M$ describes the following learning
problem: An unknown $x\in X$ is chosen uniformly at random. A learner tries to
learn $x$ from a stream of labeled samples,
$(a_{1},M(a_{1},x)),(a_{2},M(a_{2},x)),\ldots$ where each $a_{i}$ is uniformly
distributed over $A$. In particular, we consider the setting in which the
learner can see the _same_ stream of samples for $q\geq 2$ passes.

Our lower bounds apply to any learning problem whose corresponding matrix $M$
has certain extractor properties: Any large submatrix of $M$ has a similar
fraction of $1$’s and $-1$’s. More precisely, we say that $M$ is a
$(k,\ell,r)$-extractor if for any submatrix of at least $2^{-k}\cdot|A|$ rows
and at least $2^{-\ell}\cdot|X|$ columns, the fraction of entries with value
$1$ is $\frac{1}{2}\pm 2^{-r}$. (For example, parity learning has parameters
$k,\ell,r=\Omega(n)$.) We show that any two-pass learning for the learning
problem associated with $M$ requires either $\Omega(k\cdot\min(\ell,k))$
memory or at least $2^{\Omega(r)}$ samples. For $q$-pass learning, we show
that the learning problem requires either $\Omega(k\cdot\min(\ell,k))/c_{q}$
memory or at least $2^{\Omega(r/c_{q})}$ samples for $c_{q}=100^{3^{q}}$.

Our main theorems, Theorem 5 and Theorem 6, are actually stated for matrices
that are $L_{2}$-extractors, since these extractors are more convenient to
work with in our proof. However, a simple reduction from [GRT18, Corollary 3]
shows that any standard extractor as above is also a
$(\Omega(k+r),\Omega(\ell+r),\Omega(r))$-$L_{2}$-Extractor. Our results thus
apply to all the aforementioned concept classes (juntas, DNFs, Decision trees,
low-degree polynomials, codewords) as their corresponding matrices form
$L_{2}$-Extractors with good parameters.

##### A non-trivial multi-pass algorithm.

One might wonder whether the lower bound can be strengthened to show that any
$n^{o(1)}$-pass learner requires either $\Omega(n^{2})$-memory or
$2^{\Omega(n)}$ samples to learn parity. Our next result shows that this is
not the case, and efficient learning with $o(n^{2})$ memory is possible for
any $q=\omega(1)$.

######  Theorem 3 (Informal version of Theorem 7).

For any $q\leq 2^{n}$, there is a $q$-pass algorithm for $n$-bit parity
learning that uses $O(n^{2}/\log(q))$ bits of memory and $O(qn)$ samples.

##  2 Technical Overview

In this section, we will present the road map for our paper, including the
difficulties and a sketch of our main ideas for bypassing them.

###  2.1 Recap of the One-Pass Lower Bound

Both our work and the previous work on the two-pass learning bound [GRT19] are
based on the proof techniques for one-pass lower bound [Raz17, GRT18]. Let us
sketch its main idea.

##### Computational Model.

The proof models the computation as a read-once branching program: The input
to the branching program is a sequence of pairs
$(a_{1},b_{1}),(a_{2},b_{2}),\dots,(a_{T},b_{T})\in A\times\\{-1,1\\}$. Each
of them represents an equation $M(a_{i},x)=b_{i}$. These
$a_{1},a_{2},\dots,a_{T}\in A$ are sampled uniformly at random, while
$b_{1},b_{2},\dots,b_{T}$ are all generated according to the hidden vector
$x\in X$. (In our paper, for simplicity, we will identify $X$ with
$\\{0,1\\}^{n}$.) We label the layers of the branching program by
$0,1,2,\dots,T$. Let $v$ be the current vertex. Initially, it is equal to the
starting vertex of the branching program at layer $0$. At each layer $i$, we
read $(a_{i+1},b_{i+1})$ and move $v$ along one corresponding edge to layer
$i+1$. At the end of the computation, $v$ will reach the last layer $T$. Then,
it outputs a vector $x_{v}$. We say it is successful if and only if $x_{v}=x$.

The length of this branching program is the number of samples $T$. The width
is $2^{S}$ where $S\leq n^{2}/16$ is the memory bound. We want to prove that
when $S\leq n^{2}/16$ and $T\leq 2^{n/16}$, the program cannot succeed with
constant probability.

##### Main Idea of the One-Pass Lower Bound.

When outputting $x_{v}$, the optimal strategy is to output the $x^{\prime}$
with the highest posterior probability $\mathbb{P}_{x\mid v}(x^{\prime})$.
Intuitively, if the distribution $\mathbb{P}_{x\mid v}$ is very spread,
measured by its $\ell_{2}$ norm, the vertex $v$ will have a small chance of
answering $x$ correctly. We will define its $\ell_{2}$ norm as

$\|\mathbb{P}_{x\mid v}\|_{2}\coloneqq\mathop{\mathbf{E}}_{x^{\prime}\sim
X}\left[\mathbb{P}_{x\mid v}^{2}(x^{\prime})\right]^{\frac{1}{2}}.$

Initially, as $X=\\{0,1\\}^{n}$, the uniform prior $\mathbb{P}_{x}$ has
$\|\mathbb{P}_{x}\|_{2}=2^{-n}$. As $v$ moves along the computational path,
the posterior distribution $\mathbb{P}_{x\mid v}$ evolves. In the end, one can
show that, for some $\epsilon>0$, if $\|\mathbb{P}_{x\mid v}\|_{2}\leq
2^{\epsilon n}\cdot 2^{-n}$, the probability that $v$ answers $x$ correctly
will be less than $2^{-\Theta(n)}$. (Think of $\epsilon$ as a small constant,
say $\epsilon=0.1$.)

Hence, to upper bound the success probability, it is sufficient to upper bound
the probability that we ever reach a vertex $v$ with $\|\mathbb{P}_{x\mid
v}\|_{2}>2^{\epsilon n}\cdot 2^{-n}$ on our computational path. To show this,
we will enumerate all target vertices $t$ with $\|\mathbb{P}_{x\mid
t}\|_{2}>2^{\epsilon n}\cdot 2^{-n}$ and prove that the probability of
reaching a fixed $t$ is less than $2^{-\Theta(n^{2})}$. Then, our desired
upper bound follows from a union bound over all $2^{n^{2}/16+O(n)}$
possibilities of vertex $t$.

##### Progress Measure.

To study the probability of reaching $t$, we need to look at the similarity
between our current posterior $\mathbb{P}_{x\mid v}$ and the target
$\mathbb{P}_{x\mid t}$, captured by their inner product
$\langle\mathbb{P}_{x\mid v},\mathbb{P}_{x\mid t}\rangle$, defined as

$\left\langle\mathbb{P}_{x\mid v},\mathbb{P}_{x\mid
t}\right\rangle\coloneqq\mathop{\mathbf{E}}_{x^{\prime}\sim
X}\left[\mathbb{P}_{x\mid v}(x^{\prime})\cdot\mathbb{P}_{x\mid
t}(x^{\prime})\right]=\frac{1}{|X|}\sum_{x^{\prime}\in X}\mathbb{P}_{x\mid
v}(x^{\prime})\cdot\mathbb{P}_{x\mid t}(x^{\prime}).$

This measures our progress towards $t$. To show that we reach $t$ with a very
small probability, we will show that for a uniform random $a\in A$, reading
equation $M(a,x)=b$ will, w.h.p., makes little progress.

Let the posterior distribution after reading this equation be
$\mathbb{P}^{(a,b)}_{x\mid v}$. Then after normalization, the similarity
becomes

$\left\langle\mathbb{P}^{(a,b)}_{x\mid v},\mathbb{P}_{x\mid
t}\right\rangle=\frac{1}{|X|}\cdot\sum_{\begin{subarray}{c}x^{\prime}\in X\\\
M(a,x^{\prime})=b\end{subarray}}\mathbb{P}_{x\mid
v}(x^{\prime})\cdot\mathbb{P}_{x\mid
t}(x^{\prime})\Bigg{/}\sum_{\begin{subarray}{c}x^{\prime}\in X\\\
M(a,x^{\prime})=b\end{subarray}}\mathbb{P}_{x\mid v}(x^{\prime}).$

We say $a\in A$ cuts $\mathbb{P}_{x\mid v}$ evenly if

$\sum_{x^{\prime}\in X:M(a,x^{\prime})=0}\mathbb{P}_{x\mid
v}(x^{\prime})\approx\sum_{x^{\prime}\in X:M(a,x^{\prime})=1}\mathbb{P}_{x\mid
v}(x^{\prime}).$

Similarly, we say $a\in A$ cuts the point-wise product $\mathbb{P}_{x\mid
v}\cdot\mathbb{P}_{x\mid t}$ evenly if this holds for $\mathbb{P}_{x\mid
v}\cdot\mathbb{P}_{x\mid t}$ instead of $\mathbb{P}_{x\mid v}$.

$a\sim A$$\mathbb{P}_{x\mid v}$$X$

$a\sim A$$\mathbb{P}_{x\mid v}\cdot\mathbb{P}_{v\mid t}$$X$

Figure 1: A uniformly random equation $a\sim A$ will w.h.p. cut both
$\mathbb{P}_{x\mid v}$ and $\mathbb{P}_{x\mid v}\cdot\mathbb{P}_{x\mid t}$
almost evenly into two parts: (1) those $x\in X$ with $M(a,x)=0$ and (2) those
$x\in X$ with $M(a,x)=1$.

As shown in Figure 1, due to the extractor property of $M$, when
$\mathbb{P}_{x\mid v}$ and $\mathbb{P}_{x\mid v}\cdot\mathbb{P}_{x\mid t}$ are
spread enough, a _uniformly random_ $a\in A$ cuts both $\mathbb{P}_{x\mid v}$
and $\mathbb{P}_{x\mid v}\cdot\mathbb{P}_{x\mid t}$ in half with high
probability ($1-2^{-\Theta(n)}$). Hence each time we see a random equation, it
will most likely halve both the numerator and the denominator, which will not
help us make progress. Suppose we are unlucky. the rare event with probability
$2^{-\Theta(n)}$ happens. Let us see how the similarity might change:

  1. 1.

If $a\in A$ cuts $\mathbb{P}_{x\mid v}$ unevenly: When the denominator
$\sum_{x^{\prime}\in X,M(a,x^{\prime})=b}\mathbb{P}_{x\mid
v}(x^{\prime})<2^{-c}$, the similarity may be larger by a factor of $2^{c}$.
This causes huge progress. For now, we ignore this issue and assume it never
arises. We will later handle it by designing certain “stopping rules”.

  2. 2.

If $a\in A$ cuts $\mathbb{P}_{x\mid v}\cdot\mathbb{P}_{x\mid t}$ unevenly but
still cut $\mathbb{P}_{x\mid v}$ evenly: In this case, the worst case is that
the numerator does not decrease at all, while the denominator is still halved.
Then the similarity doubles.

Initially, the similarity between uniform prior and target $t$ is
$\left\langle\mathbb{P}_{x},\mathbb{P}_{x\mid t}\right\rangle=2^{-2n}$. In
order to reach the target node $t$, which has similarity
$\langle\mathbb{P}_{x\mid t},\mathbb{P}_{x\mid t}\rangle=\|\mathbb{P}_{x\mid
t}\|_{2}^{2}\geq 2^{2\epsilon n}\cdot 2^{-2n}$ with itself, the second case
has to happen $2\epsilon n$ times. Intuitively, this tells us the probability
of reaching $t$ is less than $\left(2^{-\Theta(n)}\right)^{2\epsilon
n}=2^{-\Theta(n^{2})}$.

##### Stopping Rules.

Now we turn to handle the first case. Although it happens with probability at
most $2^{-\Theta(n)}$, it only needs to happen once to make a huge progress.
Thus, the $2^{-\Theta(n)}$ probability is not enough to afford the union bound
over all $2^{\Theta(n^{2})}$ many targets $t$.

Luckily, we do not have to do union-bound. Observe that whether $a\in A$ cuts
$\mathbb{P}_{x\mid v}$ evenly is independent of the target $t$. Whenever we
see an equation $a\in A$ that cuts $\mathbb{P}_{x\mid v}$ unevenly in our
computational path, we can stop right away. Since there are $T\approx
2^{n/16}$ layers in our branching program, a simple union bound over them
shows that the overall probability of stopping is still $2^{-\Theta(n)}$.
Moreover, if we did not stop, the previous argument shows that we reach any
target vertex $t$ with probability $2^{-\Theta(n^{2})}$. Overall, our
algorithm succeeds with a very small probability.

But this is not the only stopping rule. Recall that a uniformly random $a\in
A$ cuts both $\mathbb{P}_{x\mid v}$ and $\mathbb{P}_{x\mid
v}\cdot\mathbb{P}_{x\mid t}$ evenly w.h.p. (by extractor property) only when
they are spread enough. We also need stopping rules to guarantee this.
Formally, we have the following stopping rules.

  * •

(Bad Edge) If $a$ does not cut $\mathbb{P}_{x\mid v}$ evenly, we stop.

  * •

(Significant State) If $\|\mathbb{P}_{x\mid v}\|_{2}\geq 2^{\epsilon n}\cdot
2^{-n}$, we stop.

This guarantees that the distribution of $\mathbb{P}_{x\mid v}$ will be spread
enough for the extractor property.

  * •

(Significant Value) If $\mathbb{P}_{x\mid v}(x)>2^{\epsilon n}\cdot 2^{-n}$,
we stop.

After applying this rule, we know $\|\mathbb{P}_{x\mid v}\|_{\infty}\leq
2^{\epsilon n}$. Since $\|\mathbb{P}_{x\mid v}\cdot\mathbb{P}_{x\mid
t}\|_{2}\leq\|\mathbb{P}_{x\mid v}\|_{\infty}\cdot\|\mathbb{P}_{x\mid
t}\|_{2}$, this guarantees that $\mathbb{P}_{x\mid v}\cdot\mathbb{P}_{x\mid
t}$ will be spread enough for the extractor property.

###  2.2 The Proof Framework: Two Passes

Our work builds on the approach taken by the previous two-pass lower bound
[GRT19]. We will now sketch their proof framework.

##### Computational Model.

A two pass branching program reads its input
$(a_{1},b_{1}),(a_{2},b_{2}),\dots,(a_{T},b_{T})$ twice in the _exact same
order_. At the first pass, the starting vertex is $v_{0}$, and after reading
its input, the computational path reaches a vertex $v_{1}$ at the end of the
first pass (which is also the first layer of the second pass). In the second
pass, the computational path starts from $v_{1}$ and reaches $v_{2}$ at the
last layer after reading the input again. Then it will output a vector
$x_{v_{2}}\in X$.

For any two vertices $u$ and $v$ in the program, we use $u\ \widetilde{\to}\
v$ to denote the following event (over $x,a_{1},a_{2},\dots,a_{T}$): Imagine
that we set the starting vertex of the branching program at $u$, the path from
$u$ determined by $x,a_{1},a_{2},\dots,a_{T}$ reaches $v$ without stopping.

  * •

For a vertex $v_{1}$ in the last layer of the first pass, $v_{0}\
\widetilde{\to}\ v_{1}$ means that the first pass ends at $v_{1}$.

  * •

For any vertex $v_{1}$ in the last layer of the first pass, and vertex $v_{2}$
in the last layer of the second pass, $v_{1}\ \widetilde{\to}\ v_{2}$ means
that the second pass will end at $v_{2}$ if it were starting at $v_{1}$.

##### First Attempt.

Moving from one pass to two passes, one might consider the following natural
approach: First, apply the above argument to the first pass and conclude that,
at the end of the first pass, the similarity $\langle\mathbb{P}_{x\mid
v},\mathbb{P}_{x\mid t}\rangle$ is small. Second, apply it to the second pass
and argue that such similarity grows slowly in the second pass too.

However, such a direct approach would not work. Consider a program that (1)
magically learns $x$, (2) remembers $x\oplus a_{1}$ (thinking of $x$ and
$a_{1}$ as bit strings), and (3) forgets $x$ and $a_{1}$ at the end of the
first pass. Conditioning on what $v$ remembers, $x\oplus a_{1}$, the
distribution $\mathbb{P}_{x\mid v}$ is uniformly random, just like the prior
$\mathbb{P}_{x}$. This is because $x$ is encrypted by the one-time pad using
$a_{1}$. So in the eyes of our analysis, this magical first pass is no
different from a trivial first pass. If we do not rule out the possibility of
such a magical first pass, what could happen in the second pass is that, after
seeing $a_{1}$ again, the program combines $a_{1}$ with its knowledge of
$x\oplus a_{1}$ and immediately decodes $x$.

##### Remembering the First Pass.

To prove any non-trivial lower bound for two passes, it is necessary to rule
out such a program. This program shows that analyzing two passes separately
would not work (at least for this specific argument). Therefore, we will
analyze two passes together.

The first observation is that one can w.l.o.g. assume that, when at the $i$-th
layer of the second pass, the program knows which vertex it was at in the
$i$-th layer of the first pass. This is because the program can keep a copy of
the first pass in its memory, which only blows up the memory by a factor of
two.

$(a,b)$$(a^{\prime},b^{\prime})$$(a,b)$$(a^{\prime},b^{\prime})$$(a,b)$$(a^{\prime},b^{\prime})$The
first passThe second passModified second passmodification Figure 2:
Remembering the first pass.

More formally, we modify the second pass (See Figure 2), so that every vertex
is now a pair of an original first-pass vertex and an original second-pass
vertex. The initial starting vertex of the second pass becomes
$(v_{0},v_{1})$. When the program reads the first equation $(a_{1},b_{1})$, if
in the first pass $v_{0}\ \widetilde{\to}\ v^{\prime}$ and in the second pass
$v_{1}\ \widetilde{\to}\ v$, in the modified second pass, $(v_{0},v_{1})\
\widetilde{\to}\ (v^{\prime},v)$. For the exact details of this modification,
please refer to Section 4.

Now in the modified program, every modified vertex $v$ in the second pass
corresponds to (“remembers”) a unique vertex $v^{\prime}$ in the first pass.
The event $v_{1}\ \widetilde{\to}\ v$ now implies $v_{0}\ \widetilde{\to}\
v^{\prime}$, in the sense that for any input $x,a_{1},a_{2},\dots,a_{T}$ such
that $v_{1}\ \widetilde{\to}\ v$ happens, the event $v_{0}\ \widetilde{\to}\
v^{\prime}$ must also happen.

$v_{0}$$v^{\prime}$$v_{1}$$v_{1}$$v$

Figure 3: The computational path of two passes.

Furthermore, we require every vertex in the second pass to remember $v_{1}$,
the starting vertex of the second pass. This can be achieved with a similar
modification. By this modification, for any vertex $v$ in the second pass
(which remembers its corresponding vertex $v^{\prime}$ in the first pass),

$\displaystyle(v_{0}\ \widetilde{\to}\ v)$ $\displaystyle=(v_{0}\
\widetilde{\to}\ v^{\prime})\land(v^{\prime}\ \widetilde{\to}\
v_{1})\land(v_{1}\ \widetilde{\to}\ v)$ $\displaystyle=(v_{1}\
\widetilde{\to}\ v)\land(v^{\prime}\ \widetilde{\to}\ v_{1}).$

Here the last equality holds because $v_{1}\ \widetilde{\to}\ v$ implies
$v_{0}\ \widetilde{\to}\ v^{\prime}$, and $v_{1}$ is unique since $v$
remembers it.

When $v=v_{2}$ for some vertex $v_{2}$ in the last layer (of the second pass),
this simplifies to

$\displaystyle(v_{0}\ \widetilde{\to}\ v_{2})$ $\displaystyle=(v_{0}\
\widetilde{\to}\ v_{1})\land(v_{1}\ \widetilde{\to}\ v_{2})$
$\displaystyle=(v_{1}\ \widetilde{\to}\ v_{2}).$

##### Progress Measure.

When the program reaches $v_{2}$, the optimal strategy for it is to output the
$x^{\prime}\in X$ with the highest $\mathbb{P}_{x\mid v_{0}\ \widetilde{\to}\
v_{2}}(x^{\prime})$. Note that this equals $\mathbb{P}_{x\mid v_{1}\
\widetilde{\to}\ v_{2}}(x^{\prime})$ (by the equation above).

Hence, similar to the one-pass case, when the distribution $\mathbb{P}_{x\mid
v_{1}\ \widetilde{\to}\ v_{2}}$ is spread enough ($\|\mathbb{P}_{x\mid v_{1}\
\widetilde{\to}\ v_{2}}\|_{2}\geq 2^{\epsilon n}\cdot 2^{-n}$), vertex $v_{2}$
cannot answer $x$ correctly. To upper bound the probability of answering $x$
correctly, we only need to upper bound the probability of reaching any target
state $t$ with $\|\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ t}\|_{2}\geq
2^{\epsilon n}\cdot 2^{-n}$.

Initially, $\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v_{1}}=\mathbb{P}_{x}$.
As the current vertex $v$ moves along the computational path from $v_{1}$, the
posterior $\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v}$ evolves similarly to
the one-pass case. Let the similarity $\langle\mathbb{P}_{x\mid v_{1}\
\widetilde{\to}\ v},\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ t}\rangle$ be
the progress measure, and let $\mathbb{P}^{(a,b)}_{x\mid v_{1}\
\widetilde{\to}\ v}$ be the posterior after reading a new equation $(a,b)$. We
have,

$\left\langle\mathbb{P}^{(a,b)}_{x\mid v_{1}\ \widetilde{\to}\
v},\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
t}\right\rangle=\frac{1}{|X|}\sum_{\begin{subarray}{c}x^{\prime}\in X\\\
M(a,x^{\prime})=b\end{subarray}}\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
v}(x^{\prime})\cdot\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
t}(x^{\prime})\Bigg{/}\sum_{\begin{subarray}{c}x^{\prime}\in X\\\
M(a,x^{\prime})=b\end{subarray}}\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
v}(x^{\prime}).$

Until now, this seems like a natural generalization of the one-pass case.
However, for one pass, we heavily rely on the fact that $a\in A$ is uniformly
random. In the second pass, we no longer have this property. For example, the
program could simply remember $a_{1}\in A$ from the first pass, then in the
second pass, $a_{1}$ is completely deterministic, with no randomness at all.

##### High-Probability Edges.

The previous work [GRT19] calls such $a_{i}\in A$ that is remembered by the
program a _high-probability edge_. Formally, for a vertex $v$ in the $i$-th
layer of the second pass, we say that $a$ is a high-probability edge at $v$
(denoted by $a\in\mathrm{High}(v)$) if and only if

$\mathop{\mathbf{Pr}}[a_{i+1}=a\mid v_{0}\ \widetilde{\to}\ v]\geq
2^{\epsilon\cdot n}\cdot 2^{-n}.$

Since these edges occur with too large probability (much higher than the
uniform case, $2^{-n}$), we cannot simply stop when they cut distributions
unevenly (like we did for one-pass).

  1. 1.

If this $a\in A$ cuts $\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v}$ unevenly:
When the denominator $\sum_{x^{\prime}\in
X,M(a,x^{\prime})=b}\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
v}(x^{\prime})<2^{-c}$, the similarity might be larger by a factor of $2^{c}$,
causing huge progress. For now, we ignore this issue and assume that it never
arises. We will explain how we handle it in Section 2.3.

  2. 2.

If this $a\in A$ cuts $\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
v}\cdot\mathbb{P}_{v_{1}\ \widetilde{\to}\ t}$ unevenly, but still cuts
$\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v}$ evenly: In this case, the worst
case is the same as in one-pass. Namely, the numerator does not decrease,
while the denominator is halved. Then the similarity at most doubles.

Their key observation is the following. Intuitively, to remember a single
$a\in A$, we need at least $\Omega(n)$ memory. Since the memory bound $S\leq
n^{2}/16$, the program can only remember $O(n)$ many such $a$’s. So there can
be at most $O(n)$ high probability edges.

Hence, to handle the case in Item 2, we observe that these $O(n)$ many high-
probability edges only blow up the similarity by $2^{O(n)}$. Since initially
similarity $\langle\mathbb{P}_{x},\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
t}\rangle=2^{-2n}$, and we want to prove that it would increase to
$\|\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ t}\|_{2}^{2}\geq 2^{2\epsilon
n}\cdot 2^{-2n}$ with very small probability. As long as the constant hidden
by big $O$ is much smaller than $\epsilon$, this blow-up is negligible. We
will pick the correct constants to ensure that this is indeed the case.

###  2.3 New Ingredient: Bias Counters

As mentioned in the first case, if a high probability edge $a$ cuts
$\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v}$ unevenly, the similarity might
grow a lot. First, we explain how the previous work [GRT19] gets around this
issue. Then, we will introduce our new idea. This is the key idea for proving
the tight memory lower bound for two passes.

##### Very-bad edge.

To get around this issue, they defined “very-bad edges”, which is the high
probability edges $a$ that cut $\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v}$
in a very biased way. Formally, $a\in\mathrm{High}(v)$ is “very-bad” if

$\sum_{\begin{subarray}{c}x^{\prime}\in X\\\
M(a,x^{\prime})=b\end{subarray}}\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
v}(x^{\prime})\leq 2^{-\sqrt{n}}.$

  * •

On the one hand, when a high probability edge is not very-bad, it only blows
up the similarity at most by a factor of $2^{\sqrt{n}}$.

If we set the memory bound $S$ to be $O(n^{3/2})$, there can only be
$c\cdot\sqrt{n}$ many high probability edges for some constant $0<c<1$ (since
remembering one needs $\Omega(n)$ memory). Then these $c\cdot\sqrt{n}$ many
high probability not-very-bad edges can blow up the potential by at most
$2^{cn}$. As long as $c\ll\epsilon$, this will be acceptable for our purpose.

  * •

On the other hand, when an edge $(a,b)$ is very-bad, conditioning on we
reached this vertex, $x$ is distributed as $\mathbb{P}_{x\mid v_{1}\
\widetilde{\to}\ v}$. Over the randomness of $x$, the probability that we
traverse this edge $(a,b)$ instead of $(a,-b)$ is at most $2^{-\sqrt{n}}$.

First of all, note this is completely independent of the target $t$. So we do
not have to union bound over $t$. Then if we set the sample bound $T$ to be
$2^{O(\sqrt{n})}$, we can stop immediately whenever we meet a very bad edge.
For each step, we stop with probability $2^{-\sqrt{n}}$. By union-bound over
all $T$ steps, we conclude that the overall stopping probability is still
$2^{-\Omega(\sqrt{n})}$.

Therefore, they can prove that for some constant $\epsilon>0$, any two-pass
algorithm with $S\leq\epsilon n^{3/2}$ memory and $T\leq 2^{\epsilon\sqrt{n}}$
samples cannot succeed with constant probability.

##### New Idea: Bias Counter.

Instead of stopping immediately at biased “very-bad edges”, we introduce a
counter $\mathrm{cnt}_{\mathrm{bias}}$ to keep track of the accumulated
biases: In the second pass, initially, when we were at the starting vertex
$v_{1}$, we let $\mathrm{cnt}_{\mathrm{bias}}\leftarrow 0$. For any high
probability edge $(a,b)$ from current vertex $v$ (satisfying
$a\in\mathrm{High}(v)$), we say it is $\Delta$-biased if

$\sum_{\begin{subarray}{c}x^{\prime}\in X\\\
M(a,x^{\prime})=b\end{subarray}}\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
v}(x^{\prime})\in[2^{-\Delta-1},2^{-\Delta}).$

Whenever we traverse a $\Delta$-biased edge, we will update our counter
(roughly) by

$\mathrm{cnt}_{\mathrm{bias}}\leftarrow\mathrm{cnt}_{\mathrm{bias}}+\Delta.$

Note a $\Delta$-biased edge has to be a high probability edge. There can be at
most $O(n)$ high probability edges when $S\leq n^{2}/16$. Hence we will make
at most $O(n)$ such updates.

  * •

On one hand, when the counter $\mathrm{cnt}_{\mathrm{bias}}\leq\epsilon\cdot
n$, the high probability edges we have traversed can blow up the similarity by
at most $2^{\epsilon n}$.

This follows almost directly from the definition of $\Delta$: We increase the
counter by $\Delta$ if and only if we traversed a $\Delta$-biased edge. As we
have discussed, such an edge would blow up the similarity by at most
$2^{\Delta}$. Hence in total, they can blow up the similarity by at most
$2^{\mathrm{cnt}_{\mathrm{bias}}}$.

  * •

On the other hand, the overall probability that
$\mathrm{cnt}_{\mathrm{bias}}>\epsilon\cdot n$ is small. If we stop whenever
the counter exceeds the threshold $\epsilon\cdot n$, we can show the overall
stopping probability will be small.

This is because we traverse a $\Delta$-biased edge $(a,b)$ instead of the
other edge $(a,-b)$ with probability at most $2^{-\Delta}$ over the randomness
of $x$. To gain some intuition, let us think about two extreme cases:

    * –

Case 1: Each time, the counter increases a little, e.g., $\Delta\approx 100$.
In this case, w.p. $1-(2^{-100})^{(\epsilon/100)\cdot n}=1-2^{-\epsilon n}$,
the counter $\mathrm{cnt}_{\mathrm{bias}}$ is going to increase like this for
less than $(\epsilon/100)\cdot n$ times.

(For $\Delta\ll 100$, since there are at most $O(n)$ updates, as long as the
constant hiding by this big-$O$ is much smaller than $\epsilon$, we can ignore
these updates, as the total increase due to them is negligible compared to
$\epsilon\cdot n$.)

    * –

Case 2: Each time, the counter increases a lot, i.e., $\Delta=\delta n$ for
$0<\delta<1$. In this case, w.p. $1-(2^{-\delta
n})^{(\epsilon/\delta)}=1-2^{-\epsilon n}$, the counter
$\mathrm{cnt}_{\mathrm{bias}}$ will increase like this for less than
$\frac{\epsilon}{\delta}$ times.

In both cases, the counter $\mathrm{cnt}_{\mathrm{bias}}$ will not overflow
with high probability. To make $\mathrm{cnt}_{\mathrm{bias}}$ larger than
$\epsilon\cdot n$, it is necessary to have a sufficiently large number of
(correspondingly) sufficiently large $\Delta$, and this is very unlikely. This
resembles a famous quote:

> “You can fool some of the people all of the time, and all of the people some
> of the time, but you can not fool all of the people all of the time.”—
> Abraham Lincoln

Formally, we can show that for each layer $i\in[T]$, the counter overflows at
layer $i$ with probability at most $2^{-\epsilon n}$. Together with a union
bound over $T\ll 2^{\epsilon n}$ layers, we prove that the overall stopping
probability for counter overflow is small.

This allows us to prove that for some constant $\epsilon^{\prime}>0$, any two-
pass algorithm with $S\leq\epsilon^{\prime}n^{2}$ memory and $T\leq
2^{\epsilon^{\prime}n}$ samples cannot success with constant probability. This
new idea is the key to proving a tight lower bound for two-pass learning.

In our actual proof, we will modify the program so that each vertex $v$ will
“remember” a unique counter value $\mathrm{cnt}_{\mathrm{bias}}(v)$. More
details about this modification, the bias counter, and related stopping rules
will be presented in Section 4.

##### Potential Argument.

To implement the idea, we will introduce a new stopping rule: We stop whenever
the counter $\mathrm{cnt}_{\mathrm{bias}}$ exceeds $\epsilon\cdot n$. We have
to prove that overall, we stop due to this new rule with a small probability.

Unlike previous stopping rules, this new stopping rule is “soft”, in the sense
that when a rare event of probability $2^{-\Delta}$ happens, it does not stop
right away. Instead, it accumulates such rare events and only stops when
enough rare events have occurred. Previously, we only need to analyze stopping
probability based on the randomness at the current step. But now, we have to
look at the computation history and exploit the fact that we stop only when a
lot of rare events have happened in history.

This makes it harder to analyze the stopping probability. Our main technical
contribution to two-pass is to come up with a potential analysis resolving the
issue. Roughly speaking, our potential function is defined as $\Phi\approx
2^{\mathrm{cnt}_{\mathrm{bias}}}.$ Initially, the expectation of $\Phi$ is $1$
(as we have $\mathrm{cnt}_{\mathrm{bias}}=0$ at the starting vertex). Since in
each step, $\mathrm{cnt}_{\mathrm{bias}}$ increases by $\Delta$ with
probability roughly $2^{-\Delta}$, the expectation of $\Phi$ (of the current
state $v$) will be (almost) non-increasing. At the end of the computation, we
can use Markov’s inequality to bound the probability of
$\mathop{\mathbf{Pr}}[\mathrm{cnt}_{\mathrm{bias}}>\epsilon\cdot n]$ by
$\frac{1}{2^{\epsilon n}}$.

We will give a more detailed overview and more intuitions at Section 5.1.

###  2.4 Transfer Lemma

However, the proof still has the last important missing piece. In Section 2.3,
we argued intuitively that for a $\Delta$-biased edge $(a,b)$, with only
$2^{-\Delta}$ probability over the randomness of $x$, we traverse $(a,b)$
instead of $(a,-b)$. But there is one important subtlety.

##### Informal discussion.

Note we defined the $\Delta$-biased edges w.r.t. the posterior distribution
$\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v}$. So we actually showed is the
following:

> For all starting vertex $v_{1}$ of the second pass, after $v_{1}\
> \widetilde{\to}\ v$, the computational path will then traverse a
> $\Delta$-biased edge from $v$ w.p. at most $2^{-\Delta}$.

But ideally, we want to argue about the two-pass branching program, starting
from $v_{0}$. The ideal statement will be:

> For the starting vertex $v_{0}$ of the first pass, after $v_{0}\
> \widetilde{\to}\ v$, the computational path will then traverse a
> $\Delta$-biased edge from $v$ w.p. at most $2^{-\Delta}$.

If $v=v_{2}$ is a vertex in the last layer of the second pass, as explained in
Section 2.2, we know that $v_{0}\ \widetilde{\to}\ v_{2}$ is equivalent to
$v_{1}\ \widetilde{\to}\ v_{2}$. This is because the second pass remembers the
first pass, so $v_{1}\ \widetilde{\to}\ v_{2}$ can “certify” that the first
pass indeed reaches $v_{1}$.

But for stopping rules, it is crucial that we stop or update counters in the
middle of the program. So $v$ is not always going to be in the last layer.
Suppose $v$ is in the middle of the second layer and $v^{\prime}$ is its
corresponding vertex in the first layer. As explained in Section 2.2, we have

$(v_{0}\ \widetilde{\to}\ v)=(v_{1}\ \widetilde{\to}\ v)\land(v^{\prime}\
\widetilde{\to}\ v_{1}).$

Hence the statement we showed differs from the ideal one. Intuitively, this is
because $v_{1}\ \widetilde{\to}\ v$ can only certify that $v_{0}\
\widetilde{\to}\ v^{\prime}$. We need extra arguments for controlling
$v^{\prime}\ \widetilde{\to}\ v_{1}$. This is why we need the transfer lemma,
to transfer the statement we showed into the ideal statement we want.

This is the most technical part of [GRT19]. In Section 6, we will frame this
subtlety as an adaptive issue and give a slightly simplified proof together
with a clean interpretation. This perspective enables us to generalize this
lemma to multiple passes.

##### Distribution Mismatch.

To explain this subtlety in full clarity, let us carefully examine the
definition of being $\Delta$-biased. We say that a high probability edge
$(a,b)$ is $\Delta$-biased if,

$\sum_{\begin{subarray}{c}x^{\prime}\in X\\\
M(a,x^{\prime})=b\end{subarray}}\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\
v}(x^{\prime})\leq[2^{-\Delta-1},2^{-\Delta}).$

Note that the vector $x$ is sampled conditioning on the event $v_{1}\
\widetilde{\to}\ v$. Hence it corresponds to the following random process:

  * •

First, sample a uniformly random $x\in X$ and let $v=v_{1}$.

  * •

At the $i$-th step uniformly sample $a_{i}\in A$ and move $v$ along the edge
$(a_{i},M(a_{i},x))$.

The definition of $\Delta$-biased edges is saying that conditioning on this
process reaches $v$, the probability that $M(a,x)=b$ is at most $2^{-\Delta}$.
However, when we talk about our overall stopping probability, we are referring
to a different random process:

  * •

First, sample a random $x\sim\mathbb{P}_{x\mid v_{0}\to v_{1}}$ and let
$v=v_{1}$.

  * •

At the $i$-th step uniformly sample $a_{i}\sim\mathop{\mathbf{Pr}}[a_{i}\mid
v_{0}\to v]$ and move $v$ along edge $(a_{i},M(a_{i},x))$.

We can see there is a distribution mismatch between these two. Conditioning on
we reached $v$, in the first process, the posterior distribution of $x$ is
$\mathbb{P}_{x\mid v_{1}\ \widetilde{\to}\ v}$, while in the second process,
the posterior distribution of $x$ is $\mathbb{P}_{x\mid v_{0}\
\widetilde{\to}\ v}$. As explained in Section 2.2, in general for a vertex
$v$, $(v_{0}\ \widetilde{\to}\ v)=(v_{1}\ \widetilde{\to}\ v)\land(v^{\prime}\
\widetilde{\to}\ v_{1})$. The posterior distribution at the end of the second
process

$\mathbb{P}_{x\mid v_{0}\ \widetilde{\to}\ v}=\mathbb{P}_{x\mid(v_{1}\
\widetilde{\to}\ v)\land(v^{\prime}\ \widetilde{\to}\ v_{1})}$

which is not only conditioning on (1) the event that the path from $v_{1}$
reaches $v$ but also on (2) the event that in the first pass, the path from
$v^{\prime}$ picks $v_{1}$ as the end vertex.

The issue is that we ultimately want to prove that the stopping probability is
small in the second process $v_{0}\ \widetilde{\to}\ v$. But as $\Delta$-bias
has been defined w.r.t. the first process, our previous argument only shows
that the stopping probability is small in the first process $v_{1}\
\widetilde{\to}\ v$.

##### Transfer Lemma.

To resolve this, [GRT19] introduced the following lemma, “transferring” an
upper bound on the stopping probability of the first process $v_{1}\
\widetilde{\to}\ v$ to an upper bound on the stopping probability of the
second process $v_{0}\ \widetilde{\to}\ v$.

##### Informal Statement:

For any two-pass algorithm, suppose for all fixed starting vertex $v_{1}$, the
computational path from $v_{1}$ stops with probability less than $2^{-cn}$ for
some $0<c<1$. The computational path from $v_{0}$ will stop in the second pass
with probability less than $2^{-(c-\epsilon)n}$ for some $0<\epsilon<1$.

##### Our Perspective.

Note the assumption of this lemma says that _for all fixed $v_{1}$_, over the
randomness of $x$ and $a_{1},a_{2},\dots,a_{T}$, the probability of stopping
is small. The reason there is this distribution mismatch is that the vertex
$v_{1}$ is not fixed beforehand but picked by the first pass adaptively
(depending on $x,a_{1},a_{2},\dots,a_{T}$ as well). Hence this is really an
issue caused by adaptivity.

We will then interpret the proof as exploiting the fact that the first pass (a
memory-bounded one-pass algorithm) has a limited ability to adaptively choose
the worst $v_{1}$. This perspective, which seems missing from the previous
works, is crucial for us to generalize this lemma to multiple passes. A more
detailed overview will be given in Section 6.

###  2.5 Extending to Multiple Passes

To extend this to multiple passes, we first adapt our modification on the
program and stop rules beyond two passes. This turns out to be simple, and the
details will be presented in Section 8. Our new counter and its potential
analysis extend to multi-pass smoothly as well. This will be included in
Section 10.1.

##### Main Challenge: Transfer Lemma.

However, for the transfer lemma, the original proof crucially relies on the
fact that the algorithm has only two passes. Subtle technical difficulties
arise when generalizing it to multiple passes. We will give detailed
intuitions and discussions in Section 9.

##### Current Bottleneck: Transfer Lemma.

Currently, our lower bound stops at $O(\log\log n)$ many passes. This is
because of the transfer lemma. To prove a lower bound for $q$-passes, we will
use our result for $(q-1)$-passes in a black-box way. This implicitly applies
the transfer lemma for $q-1$ times. It turns out that each application of the
transfer lemma is quite costly: In the informal statement in Section 2.4, the
original $2^{-cn}$ bound on stopping probability is demoted to a
$2^{-(c-\epsilon)n}$ bound after applying transfer lemma. Roughly speaking, if
$\epsilon>0$ is a constant, we can at most apply this lemma a constant number
of times. Then we can only prove a lower bound for a fixed constant number of
passes.

By carefully choosing parameters, we can prove that for any algorithm with $q$
passes, to succeed with constant probability, it necessarily requires either
$\Omega\\!\left(\frac{n^{2}}{c_{q}}\right)$ memory or
$2^{\Omega\left(n/c_{q}\right)}$ samples where $c_{q}=100^{3^{q}}$. In
particular, this implies a $n^{2-o(1)}$ memory lower bound for $o(\log\log
n)$-pass learning. The bottleneck in improving these results beyond
$O(\log\log n)$ passes is the successive application of the transfer lemma. It
remains an interesting open problem whether a better tradeoff such as
$c_{q}=\exp(q)$ or even $c_{q}=\poly(q)$ can be proved. For example: can a
$n^{o(1)}$-pass algorithm learn the hidden vector $x$ using $n^{2-\Omega(1)}$
memory and $2^{n^{1-\Omega(1)}}$ samples?

###  2.6 Organization of the Proofs

####  2.6.1 Two-Pass Learning Lower bound

##### Setup.

In our analysis, we will always assume that the second pass program remembers
the first pass and counters. In Section 4.1, we will prove that this is
without loss of generality by showing that we can modify any two-pass
branching program into such a program. In the rest of Section 4, we will
introduce the stopping rules formally.

##### Analysis.

First, we need to show that the probability of stopping is small. Such
analysis will be divided into the following sections in Figure 4.
Specifically, for two stopping rules, counter overflow and significant value,
we will need the transfer lemma in Section 6.

Bias counter overflow (Section 5)Significant valueHigh-probability edge
overflowBad edge but not high-probability Significant state (Appendix
A)$\underbrace{\hskip 54.06006pt}$Others$\underbrace{\hskip
61.17325pt}$$\mathbf{Pr}[\text{Stop}]\ll 1$$\underbrace{\hskip
36.98866pt}$Transfer lemma (Section 6)$\underbrace{\hskip 22.76228pt}$Section
7.1 Figure 4: Upper-bound the stopping probability for two passes.

Second, if the branching program does not stop (specifically, it does not
reach any significant state), we will show that it is going to correctly guess
$x$ with small probability in Section 7.1.6.

####  2.6.2 Multi-Pass Learning Lower bound

##### Setup.

For multi-pass, we will w.l.o.g. assume that each pass of the branching
program is going to remember all the previous passes and counters. We will
present corresponding modification in Section 8.1. In the rest of Section 8,
we will present the stopping rules.

##### Analysis.

First, we show that the probability of stopping is small. Such analysis will
be divided into the following sections in Figure 5.

Bias counter overflow (Section 10.1)Significant valueHigh-probability edge
overflowBad edge but not high-probability Significant state (Appendix
A)$\underbrace{\hskip 54.06006pt}$Others$\underbrace{\hskip
61.17325pt}$$\mathbf{Pr}[\text{Stop}]\ll 1$$\underbrace{\hskip
36.98866pt}$Transfer lemma (Section 9)$\underbrace{\hskip 22.76228pt}$Section
10.2 Figure 5: Upper-bound the stopping probability for multiple passes.

Second, if the branching program does not stop, we will show that it is going
to correctly guess $x$ with small probability in Section 10.2.4.

##  3 Preliminaries

###  3.1 Notation

Let $(x,y,z)$ be a joint random variable. We use $x\perp y$ to denote that $x$
and $y$ are _independent_. $x\perp y\mid z=z^{\prime}$ denotes that $x$ and
$y$ are independent, _conditioned_ on $z=z^{\prime}$.

$\mathbb{R}^{+}$ denotes the set of non-negative real numbers. All the
logarithms will have base $2$.

For a list of items $a=(a_{1},a_{2},\dots,a_{T})$, we use $a_{\leq i}$ (resp.
$a_{>i}$) to define the length-$i$ prefix (resp. length-$(n-i)$ suffix) of
$a$.

###  3.2 Norms and Inner Products

In this paper, we will deal with functions of the form $f:X\to\mathbb{R}$.
Given $p\geq 1$, define the $\ell_{p}$-norm of $f$ as

$\|f\|_{p}=\left(\mathop{\mathbf{E}}_{x\sim X}[f(x)^{p}]\right)^{1/p}.$

Let $f,g$ be two functions. We define $\langle
f,g\rangle:=\mathop{\mathbf{E}}_{x\sim X}[f(x)\cdot g(x)]$ as the inner
product between $f$ and $g$. We collect some basic facts about norms in the
following.

  * •

Monotonicity: $\|f\|_{p}\leq\|f\|_{q}$ for every $p\leq q$.

  * •

Cauchy-Schwarz inequality: $\langle f,g\rangle\leq\|f\|_{2}\cdot\|g\|_{2}$

  * •

(Special case of) Hölder’s inequality:
$\|fg\|_{p}\leq\|f\|_{p}\cdot\|g\|_{\infty}$.

  * •

Truncation trick: Suppose $\|f\|_{2}\leq A$. Let
$f^{>B}(x)=\mathbbm{1}_{f(x)>B}\cdot f(x)$. Then

$\|f^{>B}\|_{1}:=\mathop{\mathbf{E}}_{x\sim
X}[f(x)\cdot\mathbbm{1}_{f(x)>B}]\leq\mathop{\mathbf{E}}_{x\sim
X}\left[\frac{f(x)^{2}}{B}\right]\leq\frac{A^{2}}{B}.$

###  3.3 Learning Tasks and $L2$-Extractors

Following [GRT18], we use a matrix $M\in\\{-1,1\\}^{A\times X}$ to describe a
learning task. Here, $X$ is the domain of concepts, and $A$ is the domain of
possible inputs. $M$ corresponds to the following learning problem: An unknown
element $x\in X$ was chosen uniformly at random. The learner tries to learn
$x$ from a stream of samples, $(a_{1},b_{1}),(a_{2},b_{2}),\dots$, where for
each $i$, $a_{i}\in A$ is uniformly at random chosen and $b_{i}=M(a_{i},x)$.
In particular, we consider the setting where the learner is allowed to see the
same stream of samples for $q\geq 2$ passes.

######  Definition 1.

We say a learning matrix $M:A\times X\to\\{-1,1\\}$ a
$({k_{\mathrm{ext}}},{\ell_{\mathrm{ext}}},{r_{\mathrm{ext}}})$-$L2$-Extractor,
if for every non-negative $f\colon X\to\mathbb{R}$ with
$\frac{\|f\|_{2}}{\|f\|_{1}}\leq 2^{{\ell_{\mathrm{ext}}}}$, there are at most
$2^{-{k_{\mathrm{ext}}}}\cdot|A|$ rows $a\in A$ with

$|\langle M_{a},f\rangle|\geq 2^{-{r_{\mathrm{ext}}}}\cdot\|f\|_{1},$

where $M_{a}\in\\{-1,1\\}^{X}$ denotes the restriction of $M$ to the $a$-th
row.

Below, we collect a few examples of learning tasks from [GRT18], whose
matrices are good $L2$-extractors. For a more comprehensive list, see [GRT18].

  * •

_Parities._ In parity learning, one identifies $X=\\{0,1\\}^{n}$ and
$A=\\{0,1\\}^{n}$. Then, $M(a,x)=(-1)^{\langle a,x\rangle}$ for every $a,x$.
It can be shown that $M$ is an $L2$-extractor with

${k_{\mathrm{ext}}}=\Omega(n),\quad{\ell_{\mathrm{ext}}}=\Omega(n),\quad{r_{\mathrm{ext}}}=\Omega(n).$

  * •

_Sparse Parities._ In sparse parity learning, the hidden vector $x$ is known
to have Hamming weight exactly $\ell$. We still identify $A=\\{0,1\\}^{n}$.
But now $X=\\{x\in\\{0,1\\}^{n}\mid\sum_{i}x_{i}=\ell\\}$. The learning matrix
$M(a,x)=(-1)^{\langle a,x\rangle}$ is an $L2$-extractor with

${k_{\mathrm{ext}}}=\Omega(n),\quad{\ell_{\mathrm{ext}}},{r_{\mathrm{ext}}}=\Omega(\ell)\qquad\text{Assuming
$\ell\leq n/2$.}$
${k_{\mathrm{ext}}}=\Omega(n/\ell^{0.1}),\quad{\ell_{\mathrm{ext}}},{r_{\mathrm{ext}}}=\Omega(\ell\log(\ell))\qquad\text{Assuming
$\ell\leq n^{0.9}$.}$

Indeed, the problem requires either superlinear samples or superpolynomial
memory for any $\ell=\omega(\log(n)/\log\log(n))$ [KRT17].

  * •

_Random matrix._ Consider a random learning matrix $M\in\\{\pm 1\\}^{A\times
X}$ with $|A|=|X|=2^{n}$, where every entry of $M$ is chosen from $\\{-1,1\\}$
uniformly at random. With high probability, the resulting matrix $M$ is an
$L2$-extractor with

${k_{\mathrm{ext}}}=\Omega(n),\quad{\ell_{\mathrm{ext}}}=\Omega(n),\quad{r_{\mathrm{ext}}}=\Omega(n).$

That means, a “random” learning task will be subject to our lower bound with
high probability.

###  3.4 Computational Model

In this paper, we will model a $q$-pass learning algorithm as a $q$-pass
ordered branching program, which can see exactly the same input stream $q$
times in the same order.

######  Definition 2 ($q$-pass branching program for learning).

A $q$-pass (ordered) branching program for learning, with length $T$ and width
$d$, is a directed (muti) graph with vertices arranged in $nT+1$ layers, and
each layer contains at most $d$ vertices. In the first layer which we think of
as layer $0$, we fix the vertex $0$ to be the starting vertex, denoted by
$v_{0}$. The $j$-th pass vertices are those vertices from layer $(j-1)T$ to
layer $jT+1$. We will denote these $j$-th pass layers using vertex sets
$V^{(j)}_{0},V^{(j)}_{1},\dots,V^{(j)}_{T}$. Note for all $j>1$,
$V^{(j)}_{0}=V^{(j-1)}_{T}$.

Every vertex except the last layer has $2^{n+1}$ many outgoing edges. Each
edge is labeled by a unique pair $(a,b)\in A\times\\{-1,1\\}$. Every last-
layer vertex is labeled by one element $\widetilde{x}(v)\in X$, which is the
output of the program when reaching that vertex.

######  Definition 3 (Computational Path).

Initially, the current vertex is the start vertex , $v\leftarrow v_{0}$. Given
the input $(a_{1},b_{1}),(a_{2},b_{2}),\dots,(a_{T},b_{T})\in
A\times\\{-1,1\\}$, in the $i$-th step ($i=1,2,\dots,T$), the program reads
$(a_{i},b_{i})$, move from its current vertex $v$ in $V^{(j)}_{i-1}$ along the
edge with that label, and arrive at a vertex in $V^{(j)}_{i}$. Once $v\in
V_{T}^{(q)}$, the program will stop and output $\widetilde{x}(v)$. This
defines a computational path.

######  Definition 4 (Success Probability).

The success probability of a program is defined as

$\mathop{\mathbf{Pr}}_{\begin{subarray}{c}a_{1},a_{2},\dots,a_{T}\sim A,\
x\sim X\\\ \forall i\in[T]\ b_{i}=M(a_{i},x)\end{subarray}}\left[\text{The
output of the program matches $x$}\right]$

where $x$ and $a_{1},a_{2},\dots,a_{T}$ are sampled uniformly at random.

##  4 Setup for Two Passes

###  4.1 Modifying the Program

To ease our analysis, we would like to have the following modifications to the
program. The modification will be a two-stage process. We will use $B_{0}$ to
denote the original program, use $B_{1}$ to denote the program after the first
stage, and use $B_{2}$ to denote the final program.

$v_{0}$$v^{\prime}$$v_{1}$$v_{1}$$v$

Figure 6: The computational path of two passes.

##### Stage 1: Remember the First Pass.

We keep the first pass of the program unchanged. For the second pass of the
program, we will now force it to remember the last state of the first pass,
which we denote as $v_{1}\in V^{(1)}_{T}$. (This is also the starting vertex
of the second pass because $V^{(1)}_{T}=V^{(2)}_{0}$.) Besides this, the
second pass program also runs a copy of the first pass in its memory. Namely,
we modify the second pass so that now each vertex in layer $i$ is a triple
$(v^{\prime},v_{1},v_{B_{0}})\in V^{(1)}_{i}\times V^{(1)}_{T}\times
V^{(2)}_{i}$, which means:

  * •

The program remembers that the first pass leads to the vertex $v_{1}$.

  * •

When traversing for the first pass, it visited vertex $v^{\prime}\in
V^{(1)}_{i}$ in the $i$-th layer.

  * •

The (original) second pass program visits $v_{B_{0}}$ in the $i$-th layer.

Having this definition in mind, it is easy to modify the topology of the
program. Namely, if after reading the sample $(a_{i+1},b_{i+1})$, $v_{B_{0}}$
reaches $w_{B_{0}}$ and $v^{\prime}$ reaches $w^{\prime}$, we add an edge from
$(v^{\prime},v_{1},v_{B_{0}})$ to $(w^{\prime},v_{1},w_{B_{0}})$ with label
$(a_{i+1},b_{i+1})$.

Note such modification only blows up the memory by a constant factor (from
$\log d$ to $3\log d$ if the branching program has width $d$). We can without
loss of generality only work with modified programs. In the following, we will
use $v_{B_{1}}$ to denote a (modified) vertex in the second pass. That is,
$v_{B_{1}}=(v^{\prime},v_{1},v_{B_{0}})$. Note that $v_{B_{1}}$ uniquely
determines both $v^{\prime}$ and $v_{1}$. We use $B_{1}$ to denote the program
after this modification.

##### Stage 2: Biasness and High-probability edge Counters.

In this stage, we also keep the first pass of the program unchanged. For the
second pass, we will further attach two “counters” to each state, denoted by
$\mathrm{cnt}_{\mathrm{bias}}$ and $\mathrm{cnt}_{\mathrm{high}}$. Initially,
they are both zero. When we traverse with an edge $(a,b)$ from vertex
$v_{B_{1}}$, we will increase these two counters by some amount that is
uniquely determined by $v_{B_{1}}$ and $(a,b)$. The update rules will be
specified later in Section 4.3.

Similar to how we added $v^{\prime}$ and $v_{1}$ to the memory of the second
pass in Stage 1, we will also add $\mathrm{cnt}_{\mathrm{bias}}$ and
$\mathrm{cnt}_{\mathrm{high}}$ to the memory. Namely, for each vertex
$v_{B_{1}}$, we will create many duplicates of it and label them by
$(v_{B_{1}},\mathrm{cnt}_{\mathrm{high}},\mathrm{cnt}_{\mathrm{bias}})$. In
this way, a vertex in the second pass remembers not only
$v_{B_{1}}=(v^{\prime},v_{1},v_{B_{0}})$ but also
$\mathrm{cnt}_{\mathrm{high}}$ and $\mathrm{cnt}_{\mathrm{bias}}$. We will
apply the modification layer-by-layer as we describe in the next.

Now we will describe how we modify the edges. In layer-$0$ of the second pass,
the counters are initialized to $0$. In general, suppose we have modified the
first $i-1$ layers. Every vertex in layer $i$ should be of the form
$(v_{B_{1}},\mathrm{cnt}_{\mathrm{high}},\mathrm{cnt}_{\mathrm{bias}})$. Fix
one such vertex $v_{B_{1}}$. For each edge labeled $(a,b)$ in $B_{1}$ that
goes from $v_{B_{1}}$ to $w_{B_{1}}$, we calculate the increased value of the
counters, $c_{1}$ and $c_{2}$, based on the available information:
$v_{B_{1}},\mathrm{cnt}_{\mathrm{high}},\mathrm{cnt}_{\mathrm{bias}}$ and
$(a,b)$. Then we add an edge from
$(v_{B_{1}},\mathrm{cnt}_{\mathrm{high}},\mathrm{cnt}_{\mathrm{bias}})$ to
$(w_{B_{1}},c_{1},c_{2})$ with label $(a,b)$. We apply the modification for
each edge between the $i$-th layer and the $(i+1)$-th layer in $B_{1}$.

We will restrict the range of the counters to be integers in $[0,\log|X|]$.
Hence, they require only $O(\log\log|X|)$ bits to store. Since the desired
output $x\in X$ already requires at least $\log|X|$ memory to store, we can
without loss of generality ignore the memory blowup of this modification.
Hence we will only work with the modified program $B_{2}$. In the paper, we
simply use $v$ to denote a vertex in the program $B_{2}$. Note that in the
second pass, $v$ uniquely determines
$v^{\prime},v_{1},v_{B_{0}},\mathrm{cnt}_{\mathrm{bias}},\mathrm{cnt}_{\mathrm{high}}$.
As the counters $\mathrm{cnt}_{\mathrm{bias}}$ and
$\mathrm{cnt}_{\mathrm{high}}$ are now uniquely determined by vertex $v$, we
will denote them by $\mathrm{cnt}_{\mathrm{bias}}(v)$ and
$\mathrm{cnt}_{\mathrm{high}}(v)$.

Finally, note that our modification does not change the functionality of $B$.
Therefore, if $B_{2}$ succeeds in learning with very low probability, so does
$B$.

##### Comparison with [GRT19].

The idea of “running a copy of the previous pass” is inherited from their
work. However, our implementation is slightly simpler. For one, we observed
that we don’t need to remember the set of indices on which the second pass
traverses a high-probability edge. Only knowing the number of high-probability
edges one has traversed so far, i.e. $\mathrm{cnt}_{\mathrm{high}}$, is
sufficient.

The introduction of the new counter $\mathrm{cnt}_{\mathrm{bias}}$ is novel in
our work. Although $\mathrm{cnt}_{\mathrm{bias}}$ and
$\mathrm{cnt}_{\mathrm{high}}$ require us to modify the program in the same
way, these two counters are for completely different purposes. This new
counter $\mathrm{cnt}_{\mathrm{bias}}$ is crucial for achieving the tight
quadratic lower bound on the memory of any efficient parity learner (and more
generally the tight lower bound on the memory for any learning problem whose
corresponding matrix is an $L_{2}$-Extractor).

##### Comparison with [LRZ23].

This recent work by Liu, Raz and Zhan introduced a notion of “badness level”,
which is a technical alternative to the previous potential function in [Raz17,
GRT18], namely, the function $\langle\mathbb{P}_{x\mid v},\mathbb{P}_{x\mid
s}\rangle^{k}$. Although such “badness level” has also a counter-like
definition, $\mathrm{cnt}_{\mathrm{bias}}$ and “badness level” are counting
completely different things. In our work, the potential function is nice
enough to work with and gives shorter proofs. So we will use the original
potential function of [Raz17, GRT18].

###  4.2 The First Pass

In this section, we will set up the notation and stopping rules for the first
pass.

##### Computational Path.

The computational path starting from $v_{0}$ is uniquely determined by $x\in
X,a_{1},a_{2},\dots,a_{T}\in A$. We use $v_{0}\ \widetilde{\to}\
\widetilde{v}$ to denote the event that the (untruncated) computational path
reaches $\widetilde{v}$ (on $x,a_{1},\dots,a_{T}$).

For a vertex $v^{\prime}\in V^{(1)}_{i}$, we can consider the subprogram which
consists of only layers $i,i+1,\dots,T$. In this subprogram, we set
$v^{\prime}$ as the starting vertex. The computational path starting from
$v^{\prime}$ is uniquely determined by $x\in X,a_{i+1},a_{i+2},\dots,a_{T}$.
We use $v^{\prime}\ \widetilde{\to}\ \widetilde{v}$ to denote the event that
the (untruncated) computational path from $v^{\prime}$ reaches $\widetilde{v}$
(on $x,a_{i+1},a_{i+2},\dots,a_{T}$).

To define the stopping rules, we need to first define truncated paths.

##### Truncated Path from $v_{0}$ (Informal).

For any $x\in X,a_{1},a_{2},\dots,a_{T}\in A$, we have a uniquely determined
computational path. The truncated path will be a prefix of it. The stopping
rules specify when the truncated path stops. We will let
$v_{0}\to\widetilde{v}$ denote the event that from $v_{0}$, we reached
$\widetilde{v}$ without stopping. Even if we arrived at $\widetilde{v}$ and
then stopped, this still counts as $v_{0}\to\widetilde{v}$ since we have
reached $\widetilde{v}$.

We will give the formal definition of the truncated path after we have
introduced the stopping rules. For any vertex $v^{\prime}\in V^{(1)}_{i}$, we
will define the truncated path starting from $v^{\prime}$. But this definition
is much more subtle. We will defer it to after the formal definition.

##### Bad Events and Stopping Rules.

In the definition of stopping rules, we will need $\mathbb{P}_{x\mid v_{0}\to
v^{\prime}}$, defined as the distribution of $x$ conditioning on events
$v_{0}\to v^{\prime}$. (The prior distribution of $x,a_{1},\dots,a_{T}$ is
uniform.) Although $v_{0}\to v^{\prime}$ is defined using the stopping rules,
this is not a circular definition because we will define stopping rules and
truncated paths layer by layer: For $v^{\prime}\in V^{(1)}_{i}$, the event
$v_{0}\to v^{\prime}$ will only depend on the stopping rules of layers
$1,2,\dots,i-1$. Also the stopping rules of layer $i$ will only depend on
events $v_{0}\to v^{\prime}$ for $v^{\prime}\in V^{(1)}_{i}$.

Suppose at layer $i$, the truncated path currently reaches vertex
$v^{\prime}\in V^{(1)}_{i}$. Recall that $\mathbb{P}_{x\mid v_{0}\to
v^{\prime}}$ is the distribution of $x$ conditioning on event $v_{0}\to
v^{\prime}$. Based on it, we define the following bad events. They will appear
in the layer $i$ stopping rules.

  * •

_Bad edges._ The set of bad edges at state $v^{\prime}$ is defined as

$\mathrm{Bad}(v^{\prime})=\left\\{(a^{\prime},b^{\prime})\in
A\times\\{-1,1\\}:\mathop{\mathbf{Pr}}_{x^{\prime}\sim\mathbb{P}_{x|v_{0}\to
v^{\prime}}}[M(a^{\prime},x^{\prime})=1]\not\in\left(\frac{1}{2}-2^{-{r_{\mathrm{ext}}}},\frac{1}{2}+2^{-{r_{\mathrm{ext}}}}\right)\right\\}.$

Note that an edge $(a^{\prime},b^{\prime})$ being bad or not only depends on
$a^{\prime}$. For brevity, we sometimes abuse notation by using
$\mathrm{Bad}(v^{\prime})$ to refer to a subset of $A$, which consists of all
“bad” $a^{\prime}\in A$.

  * •

_Significant States._ If $v^{\prime}$ is a state that satisfies
$\|\mathbb{P}_{x|v_{0}\to v^{\prime}}\|_{2}\geq 2^{-n}\cdot
2^{\ell_{\mathrm{sigs}}^{(1)}}$, we will call $v^{\prime}$ a significant
state.

  * •

_Significant Values._ Define the set of significant values at $v^{\prime}$ as

$\mathrm{SigV}(v^{\prime})=\\{x^{\prime}:\mathbb{P}_{x|v_{0}\to
v^{\prime}}(x^{\prime})\geq 2^{-n+{\ell_{\mathrm{sigv}}}}\\}.$

In the first pass, we will immediately stop whenever we encounter these bad
events. Formally, these are the stopping rules that are applied _before_
traversing from $V^{(1)}_{i}$ to $V^{(1)}_{i+1}$:

  1. 1.

If we are currently at $v^{\prime}\in V^{(1)}_{i}$, which is itself a
significant state, then we stop.

  2. 2.

If $v^{\prime}$ is not significant, but the next edge $(a,b)$ satisfies that
$a\in\mathrm{Bad}(v^{\prime})$, then we stop.

  3. 3.

If $v^{\prime}$ is not significant but $x\in\mathrm{SigV}(v^{\prime})$, then
we stop.

If none of these rules apply, we take a step forward from $v^{\prime}$ to some
$\widetilde{v}\in V^{(1)}_{i+1}$ following the next edge. Then we say the
truncated path reaches $\widetilde{v}$.

##### Truncated Path from $v_{0}$ (Formal).

Initially for layer $0$, $v_{0}\to v_{0}$ is always true. Suppose we have
finished the definition for layers $0,1,\dots,i$. Then, for each
$\widetilde{v}\in V^{(1)}_{i+1}$, we can define $v_{0}\to\widetilde{v}$
recursively.

$v_{0}\to\widetilde{v}\equiv\bigvee_{\widetilde{u}\in
V^{(1)}_{i}}(v_{0}\to\widetilde{u})\land\left[\begin{aligned} &\text{From
$\widetilde{u}$, we traverse an edge and reach $\widetilde{v}$}\\\
&\text{without triggering any stopping rules at
$\widetilde{u}$}\end{aligned}\right].$

##### Truncated Path from $v^{\prime}$.

For a vertex $v^{\prime}\in V_{i}^{(1)}$, we now define the truncated path
starting from $v^{\prime}$. First, from $x,a_{i+1},a_{i+2},\dots,a_{T}$, we
can uniquely determine the computational path from $v^{\prime}$. Then
$v^{\prime}\to\widetilde{v}$ is defined as the event that the computational
path reaches $\widetilde{v}$ without triggering the stopping rules.

The subtlety here is that the conditional distributions $\mathbb{P}_{x\mid
v_{0}\to\widetilde{v}}$ in the stopping rules are still defined using
truncated paths from $v_{0}$ instead of that from $v^{\prime}$. Formally, for
each $\widetilde{v}\in V_{i+1}$,

$v^{\prime}\to\widetilde{v}\equiv\bigvee_{\widetilde{u}\in
V^{(1)}_{i}}(v^{\prime}\rightarrow\widetilde{u})\land\left[\begin{aligned}
&\text{From $\widetilde{u}$, we traverse an edge and reach $\widetilde{v}$}\\\
&\text{without triggering any stopping rules at $\widetilde{u}$ where}\\\
&\text{the distributions $\mathbb{P}_{x\mid v_{0}\to\widetilde{u}}$ in the
stopping rules}\\\ &\text{are still defined w.r.t.
$v_{0}\to\widetilde{u}$.}\end{aligned}\right]$

We will list several facts to fully explain the subtlety. They are heavily
used in both the previous work [GRT19] and ours:

  * •

For any vertex $v_{1}$ in the first pass, the event $v_{0}\to v_{1}$ is
implied by $(v_{0}\to v^{\prime})\land(v^{\prime}\to v_{1})$.
This fact emphasizes that when we define $v^{\prime}\to v_{1}$, we are still
defining the stopping rules w.r.t. the truncated paths from $v_{0}$, not
$v_{1}$. Otherwise, this fact would not hold.

  * •

The probability $\mathop{\mathbf{Pr}}[v^{\prime}\to\widetilde{v}]$ can be
interpreted as follows: First, we sample $x\in X$ and
$a_{i+1},a_{i+2},\dots,a_{T}$ _uniformly at random_. Then,
$\mathop{\mathbf{Pr}}[v^{\prime}\to\widetilde{v}]$ is the probability the
truncated path from $v^{\prime}$ defined by $x,a_{i+1},a_{i+2},\dots,a_{T}$
reaches $\widetilde{v}$. We emphasize its comparison to the next item.

  * •

The probability $\mathop{\mathbf{Pr}}[v^{\prime}\to\widetilde{v}\mid v_{0}\to
v^{\prime}]$ can be interpreted as follows: First we sample $x\in X$
_according to $\mathbb{P}_{x\mid v_{0}\to v^{\prime}}$_. (Note the event
$v_{0}\to v^{\prime}$ only depends on $x,a_{1},a_{2},\dots,a_{i}$.) Then we
sample $a_{i+1},a_{i+2},\dots,a_{T}$ _uniformly at random_ , because $v_{0}\to
v^{\prime}$ is independent of them.

Then, $\mathop{\mathbf{Pr}}[v^{\prime}\to\widetilde{v}\mid v_{0}\to
v^{\prime}]$ is the probability that the truncated path from $v^{\prime}$
determined by these $x,a_{i+1},a_{i+2},\dots,a_{T}$ reaches $\widetilde{v}$.

##### The first pass stops with small probability.

The following theorem is proved in [GRT18].

######  Theorem 4 (Main Theorem of [GRT18]).

Suppose $M$ is a
$({k_{\mathrm{ext}}},{\ell_{\mathrm{ext}}},{r_{\mathrm{ext}}})$-$L_{2}$-extractor.
Let $\ell,r$ be two parameters satisfying:

  * •

$4\ell\leq\min\\{{k_{\mathrm{ext}}},{\ell_{\mathrm{ext}}}\\}-4$,

  * •

$r\leq\frac{1}{3}\min\\{{r_{\mathrm{ext}}},{k_{\mathrm{ext}}},\ell\\}$.

Let $B$ be a one-pass branching program for the learning task of $M$. Suppose
$B$ has:

  * •

Width: $2^{\frac{1}{8}{k_{\mathrm{ext}}}\ell}$.

  * •

Length: $T=2^{r}$.

Then, over uniformly random $x\sim X$, $(a_{1},\dots,a_{T})\sim A^{T}$, the
probability that $B$ stops is at most $2^{-2r}$. Put in other words, there
exists an event $G\subseteq X\times A^{T}$ such that

$\mathop{\mathbf{Pr}}_{x,a_{1},\dots,a_{T}}[(x,a_{1},\dots,a_{T})\not\in
G]\leq 2^{-\ell}.$

Furthermore, denote by $v_{0}$ the starting vertex of $B$. For any final
vertex $v$ of $B$, it holds that

$\displaystyle\|\mathbb{P}_{x|(v_{0}\ \widetilde{\to}\ v)\land G}\|_{2}\leq
2^{\ell+1}2^{-n},\quad\text{and}$ $\displaystyle\|\mathbb{P}_{x|(v_{0}\
\widetilde{\to}\ v)\land G}\|_{\infty}\leq 2^{3\ell+4}2^{-n}.$

###  4.3 The Second Pass

Now we will set up the second pass. Below we will fix a vertex $v_{1}\in
V^{(2)}_{0}$ as the starting vertex. Let $\ell$ be a “meta” parameter. Most of
the relevant parameters in our proof are stated as multiples of $\ell$ for
brevity.

##### Computational Path from $v_{1}$.

For the subprogram containing layers
$V^{(2)}_{0},V^{(2)}_{1},\dots,V^{(2)}_{T}$, we set the vertex $v_{1}\in
V^{(2)}_{0}$ as the starting vertex. For any $x\in
X,a_{1},a_{2},\dots,a_{T}\in A$, the (untruncated) computational path from
$v_{1}$ is defined as the computational path in that subprogram. Recall that
we use $v_{1}\ \widetilde{\to}\ v$ to denote the event that the computational
path from $v_{1}$ reaches $v$.

##### Truncated Path from $v_{1}$.

We use $v_{1}\to v$ to denote the event that from $v_{1}$, the computational
path reached $v$ without stopping. Here we are only considering the second
pass subprogram.

To avoid circular definitions, we will define truncated paths and stopping
rules layer by layer. In layer $i$, as the stopping rules for all previous
layers are well-defined, the event $v_{1}\to v$ will be well-defined for all
$v\in V^{(2)}_{i}$. Then we can define the layer $i$ bad events and stopping
rules.

Since truncated paths with an arbitrary starting vertex in the second pass are
not used in our two-pass result, we will not define them here.

##### Truncated Path from $v_{0}$.

For a vertex $v$ in the second pass, we use $v_{0}\to v$ to denote the event
that (1) the computational path starting from $v_{0}$ reaches $v$ and (2)
before reaching $v$ it did not trigger any first pass or second pass stopping
rule. Note $v_{0}\to v$ is equivalent to $v_{0}\to v_{1}\land v_{1}\to v$.

##### Bad Events

Let $v\in V^{(2)}_{i}$ be a vertex in layer $i$ of the second pass. We will
define the bad events of layer-$i$. Unlike the first pass, we do _not_ always
stop immediately when we encounter them.

  * •

_High-probability edges._ An input $a^{\prime}\in A$ is of high-probability,
if

$\mathop{\mathbf{Pr}}[a_{i+1}=a^{\prime}|v_{0}\to v]\geq 2^{-n}\cdot
2^{\frac{{k_{\mathrm{ext}}}}{2}}.$

We define $\mathrm{High}(v)\subseteq A$ as the set of such inputs at
$v$.555Observe that there is no analog of such set for the first pass since
there, conditioned on the past, the next $a_{i+1}$ is completely random.

  * •

_Bad edges._ Define the set of bad edges at $v$ as

$\mathrm{Bad}(v)=\left\\{a^{\prime}\in
A:\mathop{\mathbf{Pr}}_{x^{\prime}\sim\mathbb{P}_{x|v_{1}\to
v}}[M(a^{\prime},x^{\prime})=1]\not\in\left(\frac{1}{2}-2^{-{r_{\mathrm{ext}}}},\frac{1}{2}+2^{-{r_{\mathrm{ext}}}}\right)\right\\}.$

  * •

_Significant Values._ $\mathrm{SigV}(v)$ is the set of all $x^{\prime}\in X$
such that $\mathbb{P}_{x|v_{1}\to v}(x^{\prime})\geq 2^{-n}\cdot
2^{{\ell_{\mathrm{sigv}}}}$, where ${\ell_{\mathrm{sigv}}}=50\ell$.

  * •

_Significant States._ Finally, $v$ is called a significant state, if
$\|\mathbb{P}_{x|v_{1}\to v}\|_{2}\geq 2^{-n}\cdot
2^{\ell_{\mathrm{sigs}}^{(2)}}$ where $\ell_{\mathrm{sigs}}^{(2)}=18\ell$.

Recall that, from the second stage of Section 4.1, we create two counters
$\mathrm{cnt}_{\mathrm{high}}(v)$ and $\mathrm{cnt}_{\mathrm{bias}}(v)$. They
are uniquely determined by the vertex $v$. We will now define their update-
rules.

##### High-probability Counter.

Whenever we traverse an edge labeled $(a^{\prime},b^{\prime})\in
A\times\\{-1,1\\}$ from $v$ to a new vertex $w$, if
$a^{\prime}\in\mathrm{High}(v)$, we will increase the counter
$\mathrm{cnt}_{\mathrm{high}}$ by $1$, i.e.
$\mathrm{cnt}_{\mathrm{high}}(w)=\mathrm{cnt}_{\mathrm{high}}(v)+1$. Otherwise
$\mathrm{cnt}_{\mathrm{high}}(w)=\mathrm{cnt}_{\mathrm{high}}(v)$.

##### Biasness Counter.

Whenever we traverse an edge labeled $(a^{\prime},b^{\prime})\in
A\times\\{-1,1\\}$ from $v$ to a new vertex $w$, if
$a^{\prime}\in\mathrm{High}(v)$, we will increase the bias-counter
$\mathrm{cnt}_{\mathrm{bias}}$ by

$\Delta=\left\lfloor-\log\left(\mathop{\mathbf{Pr}}_{x^{\prime}\sim\mathbb{P}_{x\mid
v_{1}\to v}}[M(a^{\prime},x^{\prime})=b^{\prime}]\right)\right\rfloor.$

Hence
$\mathrm{cnt}_{\mathrm{bias}}(w)=\mathrm{cnt}_{\mathrm{bias}}(v)+\Delta$. If
$a^{\prime}\notin\mathrm{High}(v)$, set
$\mathrm{cnt}_{\mathrm{bias}}(w)=\mathrm{cnt}_{\mathrm{bias}}(v)$.

##### Stopping Rules.

We will now define the stopping rules.

Now for a vertex $v\in V_{i}^{(2)}$, we have the following stopping rules.
They are applied after we visit $v$ and before we reach $V_{i+1}^{(2)}$.

  1. 1.

Before traversing the next edge, if $x\in\mathrm{SigV}(v)$, we stop.

  2. 2.

When we are traversing an edge $(a,b)$ where
$a\in\mathrm{Bad}(v)\setminus\mathrm{High}(v)$, we stop.

  3. 3.

Recall that from the first stage of Section 4.1, we are keeping a copy of the
first pass in our memory. If that first pass copy stops for any reason, we
also stop.

  4. 4.

If $v$ is a significant state, we stop.

  5. 5.

When $\mathrm{cnt}_{\mathrm{high}}(v)>\ell_{\mathrm{high}}^{(2)}\coloneqq\ell$
or $\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}\coloneqq
14\ell$, we stop.

###  4.4 Two-Pass Main Result

The following statement summarizes our main result for the two-pass learning
lower bound.

######  Theorem 5.

Suppose $M$ is a
$({k_{\mathrm{ext}}},{\ell_{\mathrm{ext}}},{r_{\mathrm{ext}}})$-$L2$-extractor.
Let $\ell,{r_{\mathrm{len}}}$ be two parameters satisfying

  * •

$\ell\leq\min\\{\frac{{\ell_{\mathrm{ext}}}-4}{100},\frac{{k_{\mathrm{ext}}}}{8}\\}$,

  * •

${r_{\mathrm{len}}}\leq\min\\{\frac{1}{2}{r_{\mathrm{ext}}},\frac{\ell}{3}-4\\}$.

Let $B$ be a two-pass learning program for the learning task of $M$. Suppose
$B$ has

  * •

Width $2^{\frac{1}{32}{k_{\mathrm{ext}}}\ell}$.666This width upper bound is
_before_ modifying the program. After modifying $B$ as described in Section
4.1, we can ensure the resulting program has width at most
$2^{\frac{1}{8}{k_{\mathrm{ext}}}\ell}$.

  * •

Length of each pass $T=2^{{r_{\mathrm{len}}}}$.

Denote by $v_{0}$ the starting vertex of $B$. Then, there exists an event
$G\subseteq X\times A^{T}$ (which captures that the program $B$ does not stop
early) such that

$\mathop{\mathbf{Pr}}_{x,a_{1},\dots,a_{T}}[(x,a_{1},\dots,a_{T})\notin G]\leq
2^{-\frac{2}{3}\ell},$

and for any final vertex $v$ of $B$, it holds that

$\displaystyle\|\mathbb{P}_{x|(v_{0}\ \widetilde{\to}\ v)\land G}\|_{2}\leq
2^{18\ell+1}\cdot 2^{-n},\quad\text{and}$
$\displaystyle\|\mathbb{P}_{x|(v_{0}\ \widetilde{\to}\ v)\land
G}\|_{\infty}\leq 2^{50\ell+1}\cdot 2^{-n}.$

####  4.4.1 Keeping Track of Parameters

For a better presentation, we would like to provide the following table,
summarizing the main parameters of the two-pass proof and providing a name for
each. These parameters are written as multiples of $\ell$, where we assume
$\ell$ to be sufficiently large. Also, for the first time reading, we
recommend considering ${\ell_{\mathrm{ext}}}$ and ${k_{\mathrm{ext}}}$ as
large compared with $\ell$ (e.g.,
$\min\\{{\ell_{\mathrm{ext}}},{k_{\mathrm{ext}}}\\}=1000\ell$). The last row
is only required in Section 6. We will explain its meaning by then.

Name | Explanation | Quantity
---|---|---
${r_{\mathrm{len}}}$ |  $2^{{r_{\mathrm{len}}}}$: Length of the program | ${r_{\mathrm{len}}}\leq\frac{1}{3}\ell-4$
$\ell_{\mathrm{sigs}}^{(1)}$ | First-pass Significant State Threshold | $\ell$
$\ell_{\mathrm{sigs}}^{(2)}$ | Second-pass Significant State Threshold | $18\ell$
$\ell_{\mathrm{high}}^{(2)}$ | Second-pass $\mathrm{cnt}_{\mathrm{high}}$ Threshold | $\ell$
$\ell_{\mathrm{bias}}^{(2)}$ | Second-pass $\mathrm{cnt}_{\mathrm{bias}}$ Threshold | $14\ell$
${\ell_{\mathrm{sigv}}}$ | Significant Value Threshold for Both Passes | $50\ell$
$\ell_{\mathrm{flat}}^{(1)}$ | First-Pass Flat Threshold (Only for Section 6) | $3\ell$
Table 1: Parameters for the two-pass proof

##  5 Potential Analysis

In this section, we analyze the stopping probability due to
$\mathrm{cnt}_{\mathrm{bias}}$ overflow.

For every fixed $v_{1}\in V^{(2)}_{0}$, every layer $i\in[T]$, and every
$v^{\prime}\in V^{(1)}_{i}$, we show the program, when starting from $v_{1}$,
stops due to $\mathrm{cnt}_{\mathrm{bias}}$ overflow at the $i$-th layer with
small probability, even _conditioning on $v_{0}\to v^{\prime}$_. That is, we
show

$\displaystyle\mathop{\mathbf{Pr}}_{v_{1}\to v,v\in
V^{(2)}_{i}}[\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}\mid
v_{0}\to v^{\prime}]\leq 2^{-\ell_{\mathrm{bias}}^{(2)}+\ell+O(1)}.$ (1)

However, this statement is not sufficient, because what we want to understand
is

$\displaystyle\mathop{\mathbf{Pr}}_{v_{0}\to v,v\in
V^{(2)}_{i}}[\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}]=\sum_{v_{1}\in
V^{(2)}_{0}}\mathop{\mathbf{Pr}}[v_{0}\to
v_{1}]\cdot\mathop{\mathbf{Pr}}_{v_{1}\to
v}[\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}\mid v_{0}\to
v_{1}].$

Namely, we would like to bound: (note the change of conditioned event)

$\displaystyle\mathop{\mathbf{Pr}}_{v_{1}\to v,v\in
V^{(2)}_{i}}[\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}\mid
v_{0}\to v_{1}].$ (2)

In Section 6, we show how (1) implies that (2) is small. In this section, we
mainly focus on bounding (1).

###  5.1 Definition and Overview

##### Definition

Recall that for each vertex $v$, we maintained two counters
$\mathrm{cnt}_{\mathrm{high}}(v)$ and $\mathrm{cnt}_{\mathrm{bias}}(v)$. For
any vertex $v$, we define its potential to be

$\Phi(v)\coloneqq
2^{\mathrm{cnt}_{\mathrm{bias}}(v)-\mathrm{cnt}_{\mathrm{high}}(v)}.$

For any edge $e$ between $(u,v)$ with label $(a^{\prime},b^{\prime})$ define
its potential to be

$\Phi(e)=\Phi^{(a^{\prime},b^{\prime})}(u)\coloneqq\Phi(v).$

If we stop in the second pass on a vertex $u$ _not_ due to counter overflow,
we will force the next vertex $v$ to be a special vertex $\mathbf{halt}$.
Similarly, in the second pass, if we stopped when traversing an edge $(a,b)$
(due to $(a,b)\in\mathrm{Bad}(u)\setminus\mathrm{High}(u)$), we will also let
$v\leftarrow\mathbf{halt}$. We define $\Phi(\mathbf{halt})\coloneqq 0$. Once
$v$ becomes $\mathbf{halt}$, it remains $\mathbf{halt}$ for the rest of the
second pass.

##### Probability Space

Before getting into our proof strategy, we first rigorously define the
underlying probability space.

Fixing a vertex $v_{1}\in V_{0}^{(2)}$ and a layer $i\in[T]$, we uniformly at
random sample $x\in X$ and $a_{1},a_{2},\dots,a_{T}\in A^{T}$. They determine
the realization of the truncated path from $v_{1}$, denoted by
$\mathcal{T}^{(2)}_{v_{1}}$. We emphasize that we start the truncated path
from $v_{1}$ right away, _regardless_ of whether $v_{0}\to v_{1}$ happens or
not under $(x,a_{1},\dots,a_{T})$. For any realization of
$\mathcal{T}^{(2)}_{v_{1}}$, we use $\mathcal{T}^{(2)}_{v_{1}}[i]$ to denote
the $i$-th layer vertex traversed in $\mathcal{T}^{(2)}_{v_{1}}$, and
$\mathcal{T}^{(2)}_{v_{1}}[i,i+1]$ to denote the edge from $V^{(2)}_{i}$ to
$V^{(2)}_{i+1}$ traversed in $\mathcal{T}^{(2)}_{v_{1}}$. We use
$|\mathcal{T}^{(2)}_{v_{1}}|$ to denote the length of the truncated path
(before stopping). For $i>|\mathcal{T}^{(2)}_{v_{1}}|$, we define
$\mathcal{T}^{(2)}_{v_{1}}[i]=\mathbf{halt}$ and
$\mathcal{T}^{(2)}_{v_{1}}[i,i+1]=\mathbf{halt}$. When $i$ is fixed in
context, we write $v\sim\mathcal{T}^{(2)}_{v_{1}}$ to express that $v$ is
determined by the random process $\mathcal{T}^{(2)}_{v_{1}}$.

Notice that $(x,a_{1},a_{2},\dots,a_{T})\in X\times A^{T}$ also determines
realization of the truncated path from $v_{0}$, denoted by
$\mathcal{T}^{(1)}_{v_{0}}$. This gives us a natural coupling between
$\mathcal{T}^{(1)}_{v_{0}}$ and $\mathcal{T}^{(2)}_{v_{1}}$. Namely, we draw
$(x,a_{1},\dots,a_{T})$, and consider the realization of
$\mathcal{T}^{(1)}_{v_{0}}$ and $\mathcal{T}^{(2)}_{v_{1}}$ under the same
input. Let $v^{\prime}=\mathcal{T}^{(1)}_{v_{0}}[i]$ be the $i$-th layer
vertex in the first pass. Recall that the second pass of the program remembers
the first pass. Hence from $v$, we can uniquely determine the corresponding
Pass-$1$ vertex $v^{\prime}$.

On the other hand, conditioning on any realization of
$v^{\prime}=\mathcal{T}^{(1)}_{v_{0}}[i]$, the vertex
$v=\mathcal{T}^{(2)}_{v_{1}}[i]$ is naturally a random variable. Formally,
this is the random variable
$\mathcal{T}^{(2)}_{v_{1}}[i]\mid\mathcal{T}^{(1)}_{v_{0}}[i]=v^{\prime}$
under the natural coupling between $\mathcal{T}^{(1)}_{v_{0}}$ and
$\mathcal{T}^{(2)}_{v_{1}}$. To avoid such heavy notation, in this section, we
will always fix a $v_{1}\in V^{(2)}_{0}$ and denote the random variable as
$(v\mid v_{0}\rightarrow v^{\prime})$. Note if
$|\mathcal{T}^{(2)}_{v_{1}}|<i$, we would have $v=\mathbf{halt}$. Hence
$\mathbf{halt}$ is also in the support of such a random variable.

##### Proof Strategy

Having defined the probability space, we will show that:

  1. 1.

For any fixed $v^{\prime}\in V^{(1)}_{i},v_{1}\in V^{(2)}_{0}$, we show that
the expected potential $\mathop{\mathbf{E}}_{v\mid v_{0}\to
v^{\prime}}[\Phi(v)]$ is small.

  2. 2.

By our stopping rule, $\mathrm{cnt}_{\mathrm{high}}(v)$ is always at most
$\ell$.

Together these show that $\mathop{\mathbf{E}}_{v\mid v_{0}\to
v^{\prime}}[2^{\mathrm{cnt}_{\mathrm{bias}}(v)}]$ is small. Hence we can upper
bound the probability that the counter $\mathrm{cnt}_{\mathrm{bias}}$
overflows. Namely:

$\mathop{\mathbf{Pr}}[\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}\mid
v_{0}\to v^{\prime}]\leq\frac{\mathop{\mathbf{E}}_{v\mid v_{0}\to
v^{\prime}}[2^{\mathrm{cnt}_{\mathrm{bias}}(v)}]}{2^{\ell_{\mathrm{bias}}^{(2)}}}\leq\frac{\mathop{\mathbf{E}}_{v\mid
v_{0}\to v^{\prime}}[\Phi(v)]\cdot
2^{\ell}}{2^{\ell_{\mathrm{bias}}^{(2)}}}\leq
2^{\ell-\ell_{\mathrm{bias}}^{(2)}}.$

##### Intuition.

We give some intuition for this potential function: After traversing an edge
with input $a\in\mathrm{High}(v)$, the counter $\mathrm{cnt}_{\mathrm{bias}}$
increases when some small-probability bad event happens. More specifically,
when traversing an edge $(a,b)$ with label $b$ where
$\mathop{\mathbf{Pr}}[M(a,x)=b\mid v_{1}\to v]=2^{-\Delta}\ll\frac{1}{2}$.
Moreover, the amount of increase is $\left\lfloor\Delta\right\rfloor$, the
logarithm of that probability (up to the rounding).

In other words, with probability $2^{-\Delta}$ we traverse $(a,b)$ and the
counter $\mathrm{cnt}_{\mathrm{bias}}$ increases by $\lfloor{\Delta\rfloor}$.
With probability $1-2^{-\Delta}$, we traverse the edge $(a,-b)$, in which case
we do not update the counter. Overall, the expected increase of
$2^{\mathrm{cnt}_{\mathrm{bias}}(v)}$, after traversing an edge $(a,*)$ with
$a\in\mathrm{High}(v)$, is

$2^{-\Delta}\cdot 2^{\lfloor{\Delta\rfloor}}+(1-2^{-\Delta})\leq 2.$

So the expectation of $2^{\mathrm{cnt}_{\mathrm{bias}}(v)}$ at most doubles
after traversing a high-probability edge. Thus, by introducing an extra
$2^{-\mathrm{cnt}_{\mathrm{high}}(v)}$ term to account for the high-
probability edges traversed so far, we can show the expectation of
$\Phi(v)=2^{\mathrm{cnt}_{\mathrm{bias}}(v)-\mathrm{cnt}_{\mathrm{high}}(v)}$
is almost777In the real proof, we need to analyze the expectation
_conditioning_ on the event $v_{0}\to v^{\prime}$. The conditioning makes the
argument more subtle. As a result, the expectation of $\Phi$ might grow by a
factor of $(1+2^{-{r_{\mathrm{len}}}})$ after traversing a layer. Since there
are at most $i\leq T$ layers, the total growth is bounded by $O(1)$. non-
increasing.

###  5.2 Evolution of Potential

Let us first analyze how the potential function changes after traversing an
edge. Below we will always fix a vertex $v_{1}\in V_{0}^{(2)}$ and a layer
$i\in[T]$. For the second second-pass-only truncated path
$\mathcal{T}^{(2)}_{v_{1}}$ and any vertex $u\in V^{(2)}_{i-1}$, we will let
$(v_{1}\to u)$ denote the event $\mathcal{T}^{(2)}_{v_{1}}(i-1)=u$.

######  Lemma 1.

Fixing $v_{1}\in V_{0}^{(2)}$, for any vertex $u$ in the second pass and an
edge labeled $(a,b)$,

$\Phi^{a,b}(u)\leq\Phi(u)\cdot\frac{1+2\cdot
2^{-{r_{\mathrm{ext}}}}}{2\mathop{\mathbf{Pr}}_{x\mid v_{1}\to u}[M(a,x)=b]}.$

###### Proof.

We need to discuss the four cases: Let $v$ be the vertex we reach after
traversing this edge.

  * •

We stopped on $u$ due to stopping rules. Then
$\Phi^{a,b}(u)=\Phi(\mathbf{halt})=0$ since we force $u$ to traverse to
$\mathbf{halt}$ after reading $(a,b)$.

  * •

$a\not\in\mathrm{Bad}(u)$: In this case, both $\mathrm{cnt}_{\mathrm{bias}}$
and $\mathrm{cnt}_{\mathrm{high}}$ are unchanged. We know
$\Phi^{a,b}(u)=\Phi(u)$. By the definition of bad edges, we know that

$\mathop{\mathbf{Pr}}_{x\mid v_{1}\to
u}[M(a,x)=b]\in\left(\frac{1}{2}-2^{-{r_{\mathrm{ext}}}},\frac{1}{2}+2^{-{r_{\mathrm{ext}}}}\right).$

As a result

$\frac{\Phi^{a,b}(u)}{\Phi(u)}=1\leq\frac{1+2\cdot
2^{-{r_{\mathrm{ext}}}}}{2\mathop{\mathbf{Pr}}_{x\mid v_{1}\to u}[M(a,x)=b]}.$

  * •

$a\in\mathrm{Bad}(u)\setminus\mathrm{High}(u)$: By our stopping rule, we will
stop on this edge. Hence $\Phi^{a,b}(u)=\Phi(\mathbf{halt})=0$. The inequality
trivially holds.

  * •

$a\in\mathrm{High}(u)$: In this case, the counter
$\mathrm{cnt}_{\mathrm{high}}(v)=\mathrm{cnt}_{\mathrm{high}}(u)+1$ and
$\mathrm{cnt}_{\mathrm{bias}}(v)=\mathrm{cnt}_{\mathrm{bias}}(u)+\Delta$ with
$\Delta=\left\lfloor-\log\left(\mathop{\mathbf{Pr}}_{x\mid v_{1}\to
v}[M(a,x)=b]\right)\right\rfloor$. Hence,

$\frac{\Phi^{a,b}(u)}{\Phi(u)}=2^{\Delta-1}\leq\frac{1}{2\mathop{\mathbf{Pr}}_{x\mid
v_{1}\to u}[M(a,x)=b]}.$

Having verified all possible cases, we conclude the validity of the lemma. ∎

###  5.3 Potential Grows Slowly

As mentioned in Section 5.1, we will analyze the conditional expectation:

$\mathop{\mathbf{E}}[\Phi(v)\mid v_{0}\to v^{\prime}].$

We observe that

$\mathop{\mathbf{E}}[\Phi(v)\mid v_{0}\to
v^{\prime}]=\frac{\mathop{\mathbf{E}}_{v\sim\mathcal{T}^{(2)}_{v_{1}}}[\Phi(v)\cdot\mathbbm{1}[v_{0}\to
v^{\prime}]]}{\mathop{\mathbf{Pr}}[v_{0}\to v^{\prime}]}.$

Here $v\sim\mathcal{T}^{(2)}_{v_{1}}$ is a random variable determined by the
random process $\mathcal{T}^{(2)}_{v_{1}}$, while $(v_{0}\to v^{\prime})$ is
an event for the random process $\mathcal{T}^{(1)}_{v_{0}}$. As explained in
Section 5.1, we are taking the natural coupling between
$\mathcal{T}^{(1)}_{v_{0}}$ and $\mathcal{T}^{(2)}_{v_{1}}$. So the
expectation on the numerator is well-defined. Since $v$ runs a copy of the
first pass, the indicator $\mathbbm{1}[v_{0}\to v^{\prime}]$ is the same as
$\mathbbm{1}[v^{\prime}\text{ is remembered in }v]$.

We are ready to state the core lemma in this section.

######  Lemma 2.

For every $i\in[T]$ and every $v^{\prime}\in V^{(1)}_{i}$ such that
$\mathop{\mathbf{Pr}}[v_{0}\to v^{\prime}]\neq 0$, we have

$\mathop{\mathbf{E}}[\Phi(v)\mid v_{0}\to
v^{\prime}]=\frac{\mathop{\mathbf{E}}_{v\sim\mathcal{T}^{(2)}_{v_{1}}}[\Phi(v)\cdot\mathbbm{1}[v_{0}\to
v^{\prime}]]}{\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]}\leq(1+2^{-2{r_{\mathrm{len}}}+2})^{i}.$

###### Proof.

We use induction on $i\in[T]$. For the case that $i=0$, $v_{0}\in V^{(1)}_{0}$
(resp. $v_{1}\in V^{(1)}_{1}$) is the only vertex such that
$\mathop{\mathbf{Pr}}[v_{0}\to v_{0}]\neq 0$ (resp.
$\mathop{\mathbf{Pr}}[v_{1}\to v_{1}]\neq 0$). The lemma holds trivially.
Next, suppose the lemma holds for $i$. We prove it for the case of $i+1$.

For any edge $e^{\prime}$ linking $u^{\prime}\in V^{(1)}_{i}$ and
$v^{\prime}\in V^{(1)}_{i+1}$, let $v_{0}\to e^{\prime}$ denote the event that
the program traverses the edge $e^{\prime}$ without stopping at $u^{\prime}$.
(In particular, this implies that $e^{\prime}\notin\mathrm{Bad}(u^{\prime})$).

Fix $v^{\prime}\in V^{(1)}_{i+1}$. Denote by $\Gamma^{-}(v^{\prime})$ the set
of incoming edge $e^{\prime}$ to $v^{\prime}$ such that
$\mathop{\mathbf{Pr}}[v_{0}\to e^{\prime}]\neq 0$. We observe that

$\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]=\sum_{e^{\prime}\in\Gamma^{-}(v^{\prime})}\mathop{\mathbf{Pr}}[v_{0}\to
e^{\prime}],$

and

$\mathop{\mathbf{E}}[\Phi(v)\cdot\mathbbm{1}[v_{0}\to
v^{\prime}]]=\sum_{e^{\prime}\in\Gamma^{-}(v^{\prime})}\mathop{\mathbf{E}}_{e\sim\mathcal{T}^{(2)}_{v_{1}}[i,i+1]}[\Phi(e)\cdot\mathbbm{1}[v_{0}\to
e^{\prime}]].$

Again, when we write $\mathbbm{1}[v_{0}\to e^{\prime}]$ in the expectation, we
are considering the natural coupling between $\mathcal{T}^{(1)}_{v_{0}}$ and
$\mathcal{T}^{(2)}_{v_{1}}$. Thus, $\mathbbm{1}[v_{0}\to e^{\prime}]$ denotes
the event that the first pass traverses the edge $e^{\prime}$. Observe that
the event indicator $\mathbbm{1}[v_{0}\to e^{\prime}]$ is determined after
conditioning on $v_{1}\to e$. More precisely, suppose $e^{\prime}$ connects
$(u^{\prime},v^{\prime})$ and has label $(a^{\prime},b^{\prime})$. Then
$\mathbbm{1}[v_{0}\to e^{\prime}]$ is true, if and only if $e$ links two
vertices $(u,v)$ where $u$ remembers $u^{\prime}$, and the label of $e$ is
exactly $(a^{\prime},b^{\prime})$.

The following lemma is the key step in the induction proof.

######  Lemma 3.

Assuming that for every $u^{\prime}\in V^{(1)}_{i}$ with
$\mathop{\mathbf{Pr}}[v_{0}\to u^{\prime}]\neq 0$, we have

$\mathop{\mathbf{E}}[\Phi(u)\mid v_{0}\to
u^{\prime}]:=\frac{\mathop{\mathbf{E}}_{u\sim\mathcal{T}^{(2)}_{v_{1}}}[\Phi(u)\cdot\mathbbm{1}[v_{0}\to
u^{\prime}]]}{\mathop{\mathbf{Pr}}[v_{0}\to
u^{\prime}]}\leq(1+2^{-2{r_{\mathrm{len}}}+2})^{i}.$

Then, for every $e^{\prime}$ being an edge from $V^{(1)}_{i}$ to
$V^{(1)}_{i+1}$ such that $\mathop{\mathbf{Pr}}[v_{0}\to e^{\prime}]\neq 0$,
we have

$\frac{\mathop{\mathbf{E}}_{e\sim\mathcal{T}^{(2)}_{v_{1}}[i,i+1]}[\Phi(e)\cdot\mathbbm{1}[v_{0}\to
e^{\prime}]]}{\mathop{\mathbf{Pr}}[v_{0}\to
e^{\prime}]}\leq(1+2^{-2{r_{\mathrm{len}}}+2})^{i+1}.$

We defer the proof of Lemma 3 to the end of the subsection. Assuming Lemma 3
for now, we quickly finish the proof of Lemma 2. Note that

$\displaystyle\mathop{\mathbf{E}}[\Phi(v)\cdot\mathbbm{1}[v_{0}\to
v^{\prime}]]$
$\displaystyle=\sum_{e^{\prime}\in\Gamma^{-}(v^{\prime})}\mathop{\mathbf{E}}_{e\sim\mathcal{T}^{(2)}_{v_{1}}[i,i+1]}[\Phi(e)\cdot\mathbbm{1}[v_{0}\to
e^{\prime}]]$
$\displaystyle\leq\sum_{e^{\prime}\in\Gamma^{-}(v^{\prime})}\mathop{\mathbf{Pr}}[v_{0}\to
e^{\prime}]\cdot(1+2^{-2{r_{\mathrm{len}}}+2})^{i+1}$
$\displaystyle\leq\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]\cdot(1+2^{-2{r_{\mathrm{len}}}+2})^{i+1}.$

Re-arranging proves the desired bound for $v^{\prime}$. As this holds for
every $v^{\prime}\in V^{(1)}_{i+1}$, we have verified the lemma for $i+1$. By
induction on $i$, this completes the proof. ∎

We prove Lemma 3 now.

###### Proof of Lemma 3.

Suppose $e^{\prime}$ links $(u^{\prime},v^{\prime})\in V^{(1)}_{i}\times
V^{(1)}_{i+1}$ with label $(a^{\prime},b^{\prime})$. As
$\mathop{\mathbf{Pr}}[v_{0}\to e^{\prime}]>0$, we know $e^{\prime}$ is not a
bad edge. Thus,

$\displaystyle\mathop{\mathbf{Pr}}[v_{0}\to e^{\prime}]$
$\displaystyle=\mathop{\mathbf{Pr}}[a_{i+1}=a^{\prime}]\cdot\mathop{\mathbf{Pr}}_{\mathcal{T}^{(1)}_{v_{0}}}[(v_{0}\to
u^{\prime})\land(x\notin\mathrm{SigV}(u^{\prime}))\land(M(a^{\prime},x)=b^{\prime})\mid
a_{i+1}=a^{\prime}]$ $\displaystyle\geq
2^{-n}\cdot\mathop{\mathbf{Pr}}[v_{0}\to
u^{\prime}]\left(\mathop{\mathbf{Pr}}_{x^{\prime}\sim\mathbb{P}_{x|v_{0}\to
u^{\prime}}}[M(a^{\prime},x^{\prime})=b^{\prime}]-\mathop{\mathbf{Pr}}_{x^{\prime}\sim\mathbb{P}_{x|v_{0}\to
u^{\prime}}}[x^{\prime}\in\mathrm{SigV}(u^{\prime})]\right)$
$\displaystyle\geq 2^{-n}\cdot\mathop{\mathbf{Pr}}[v_{0}\to
u^{\prime}]\left(\frac{1}{2}-2^{-{r_{\mathrm{ext}}}}-2^{{\ell_{\mathrm{sigv}}}^{(1)}-{\ell_{\mathrm{sigv}}}}\right)$
($a^{\prime}$ is not bad) $\displaystyle\geq\mathop{\mathbf{Pr}}[v_{0}\to
u^{\prime}]\cdot
2^{-n}\cdot\left(\frac{1}{2}-2^{-2{r_{\mathrm{len}}}}\right).$

On the other hand, consider a realization of
$(\mathcal{T}^{(1)}_{v_{0}},\mathcal{T}^{(2)}_{v_{1}})$ (under the natural
coupling). Given $e\sim\mathcal{T}^{(2)}_{v_{1}}[i,i+1]$, recall that
$\mathbbm{1}[v_{0}\to e^{\prime}]$ is true if and only if $e$ has label
$(a^{\prime},b^{\prime})$ and connects two vertices $(u,v)$ where $u$
remembers $u^{\prime}$. We consider the distribution of $(u,x)$ under
$\mathcal{T}^{(2)}_{v_{1}}$, where $u=\mathcal{T}^{(2)}_{v_{1}}[i]$ and $x\in
X$ is the hidden vector. We then calculate the probability that the program
traverses an edge from $V^{(2)}_{i}$ to $V^{(2)}_{i+1}$ with label
$(a^{\prime},b^{\prime})$. That is, we can write

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{T}^{(2)}_{v_{1}}}[\Phi(e)\cdot\mathbbm{1}[v_{0}\to
e^{\prime}]]$
$\displaystyle=\mathop{\mathbf{E}}_{(u,x)\sim\mathcal{T}^{(2)}_{v_{1}}}\left[\Phi^{a^{\prime},b^{\prime}}(u)\cdot\mathbbm{1}[v_{0}\to
u^{\prime}]\cdot\mathbbm{1}[(x\notin\mathrm{SigV}(u))\land(M(a^{\prime},x)=b^{\prime})]\right]\cdot$
$\displaystyle\qquad\mathop{\mathbf{Pr}}[a_{i+1}=a^{\prime}]$ ($a_{i+1}$ is
independent of $(u,x^{\prime})$) $\displaystyle\leq
2^{-n}\mathop{\mathbf{E}}_{u\sim\mathcal{T}^{(2)}_{v_{1}}}\left[\Phi^{a^{\prime},b^{\prime}}(u)\cdot\mathbbm{1}[v_{0}\to
u^{\prime}]\cdot\mathop{\mathbf{Pr}}_{x^{\prime}\sim\mathbb{P}_{x|v_{1}\to
u}}[M(a^{\prime},x^{\prime})=b^{\prime}]\right]$ (Dropping
$\mathbbm{1}[x\notin\mathrm{SigV}(u)]$) $\displaystyle\leq
2^{-n}\mathop{\mathbf{E}}\left[\Phi(u)\cdot\frac{1+2^{-{r_{\mathrm{ext}}}+1}}{2}\mathbbm{1}[v_{0}\to
u^{\prime}]\right]$ (Lemma 1)
$\displaystyle\leq\mathop{\mathbf{E}}\left[\Phi(u)\cdot\mathbbm{1}[v_{0}\to
u^{\prime}]\right]\cdot
2^{-n}\left(\frac{1}{2}+2^{-{r_{\mathrm{ext}}}}\right).$

Combining the two inequalities and using the assumption, we obtain

$\displaystyle\frac{\mathop{\mathbf{E}}_{e}[\Phi(e)\cdot\mathbbm{1}[v_{0}\to
e^{\prime}]]}{\mathop{\mathbf{Pr}}[v_{0}\to
e^{\prime}]}\leq\frac{\mathop{\mathbf{E}}_{u}[\Phi(u)\cdot\mathbbm{1}[v_{0}\to
u^{\prime}]]}{\mathop{\mathbf{Pr}}[v_{0}\to
u^{\prime}]}\cdot\frac{\frac{1}{2}+2^{-{r_{\mathrm{ext}}}}}{\frac{1}{2}-2^{-2{r_{\mathrm{len}}}}}\leq(1+2^{-2{r_{\mathrm{len}}}+2})^{i+1},$

as claimed. ∎

###  5.4 Upper Bounding the Probability of $\mathrm{cnt}_{\mathrm{bias}}$
Overflow

######  Corollary 1.

For any layer $i\in[T]$, $v_{1}\in V^{(2)}_{0}$ and $v^{\prime}\in
V^{(1)}_{i}$, we have

$\mathop{\mathbf{Pr}}[\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}\mid
v_{0}\to v^{\prime}]\leq\frac{(1+2^{-2{r_{\mathrm{len}}}+2})^{i}\cdot
2^{\ell}}{2^{\ell_{\mathrm{bias}}^{(2)}}}\leq
2^{\ell-\ell_{\mathrm{bias}}^{(2)}+1}.$

###### Proof.

By the stopping rule for $\mathrm{cnt}_{\mathrm{high}}$, we know that if we
have not stopped, we always have $\mathrm{cnt}_{\mathrm{high}}(v)\leq\ell$.
Consequently, we have $\Phi(v)\geq 2^{\mathrm{cnt}_{\mathrm{bias}}(v)-\ell}$.
Thus,

$\mathop{\mathbf{Pr}}[\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}\mid
v_{0}\to v^{\prime}]\leq\frac{\mathop{\mathbf{E}}_{v\mid v_{0}\to
v^{\prime}}[2^{\mathrm{cnt}_{\mathrm{bias}}(v)}]}{2^{\ell_{\mathrm{bias}}^{(2)}}}\leq\frac{\mathop{\mathbf{E}}_{v\mid
v_{0}\to v^{\prime}}[\Phi(v)]\cdot 2^{\ell}}{2^{\ell_{\mathrm{bias}}^{(2)}}}.$

We finish the proof by noting that $\mathop{\mathbf{E}}_{v\mid v_{0}\to
v^{\prime}}[\Phi(v)]\leq(1+2^{-2{r_{\mathrm{len}}}+2})^{i}\leq 2$. ∎

##  6 Transfer Lemma

In this section, we will present a key lemma (the “transfer lemma”) used in
the analysis, which is a generalization of Lemma 9 in [GRT19] (proceeding
version). Jumping ahead, the statement we will prove in this section is the
following lemma.

######  Lemma 4 (Transfer Lemma).

Let $v^{\prime}\in V^{(1)}_{i}$ be a vertex in the $i$-th layer of the first
pass, and $v_{1}\in V^{(2)}_{0}$ be a vertex at the beginning of the second
pass. Define a set

$S_{v^{\prime},v_{1},i}\coloneqq\\{v\in V^{(2)}_{i}:\text{$v$ remembers
$v^{\prime}$ and $v_{1}$}\\}.$

Let $E:X\times V^{(2)}_{i}\to\\{0,1\\}$ be any event such that $E(x,v)$ that
only depends on $x$ and $v$. Assume that for all fixed $v^{\prime}\in
V^{(1)}_{i},v_{1}\in V^{(2)}_{0}$,

$\displaystyle\ \sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[(v_{1}\to v)\land
E(x,v)]\leq\mathop{\mathbf{Pr}}[v_{0}\to v^{\prime}]\cdot 2^{-k}.$ (3)

This implies for all $v^{\prime}\in V^{(1)}_{i}$,

$\sum_{v_{1}\in V^{(2)}_{0}}\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[(v_{0}\to v)\land
E(x,v)]\leq\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]\cdot(2^{-k+12\ell_{\mathrm{sigs}}^{(1)}+4}+2^{-\ell_{\mathrm{sigs}}^{(1)}+2}).$

Lemma 4 is the _only_ technical statement in this section that is required in
Section 7 (the main proof of the two-pass lower bound). We will use the lemma
to bound the stopping probability due to Significant Value and
$\mathrm{cnt}_{\mathrm{bias}}$ overflow in the second pass.

The rest of the section is devoted to the proof of Lemma 4. We will give a
clean interpretation and a simplified proof of it.

###  6.1 Overview

For each layer $i$, we would like to prove that the probability the program
stops at the $i$-th layer of the second pass (i.e. $V^{(2)}_{i}$) is small.
Since a layer-$i$ vertex $v$ in the second pass remembers the corresponding
layer-$i$ vertex $v^{\prime}$ in the first pass, we have

$\displaystyle\mathop{\mathbf{Pr}}_{x,a_{1},a_{2},\dots,a_{T}}\left[\text{truncated
path from }v_{0}\text{ stops at $V^{(2)}_{i}$}\right]$
$\displaystyle\quad=\sum_{v^{\prime}\in
V^{(1)}_{i}}\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]\cdot\mathop{\mathbf{Pr}}_{x,a_{1},a_{2},\dots,a_{T}}\left[\text{truncated
path from }v_{0}\text{ stops at $V^{(2)}_{i}$}\ \middle|\ v_{0}\to
v^{\prime}\right].$ (4)

##### Informal Statement.

Let $k$ be a parameter (think of $k$ as a large constant times $\ell$). Assume
the following inequality holds on the truncated path _from $v_{1}$_:

$\forall v^{\prime}\in V_{i}^{(1)},v_{1}\in
V^{(2)}_{0},\quad\mathop{\mathbf{Pr}}_{x,a_{\leq i}}\left[\text{truncated path
from }v_{1}\text{ stops at $V^{(2)}_{i}$}\ \middle|\ v_{0}\to
v^{\prime}\right]\leq 2^{-k}.$ (5)

Given the assumption, we prove the following bound on the truncated path _from
$v_{0}$_:

$\forall v^{\prime}\in
V_{i}^{(1)},\quad\mathop{\mathbf{Pr}}_{x,a_{1},a_{2},\dots,a_{T}}\left[\text{truncated
path from }v_{0}\text{ stops at $V^{(2)}_{i}$}\ \middle|\ v_{0}\to
v^{\prime}\right]\leq 2^{-k+O(\ell)}.$ (6)

Plugging (6) into (4) shows that the program stops at $V_{i}^{(2)}$ with an
exponentially small probability. Summing up $i\in[T]$ shows that the
probability of stopping somewhere along the second pass is also small. Thus,
it remains to prove (6).

##### Intuition.

To get some intuition, let us looks at a much stronger assumption than (5). It
will trivially imply (6), but at the same time, is too good to be true:

$\forall v^{\prime}\in V_{i}^{(1)},\quad\mathop{\mathbf{Pr}}_{x,a_{\leq
i}}\left[\exists v_{1}\in V^{(2)}_{0},\text{truncated path from }v_{1}\text{
stops at $V^{(2)}_{i}$}\ \middle|\ v_{0}\to v^{\prime}\right]\leq 2^{-k}.$ (7)

Note here we are simply changing the order between the qualifier and the
probability. It is a stronger statement because there are
$2^{\Theta(n^{2})}\gg 2^{k}$ many possibilities of $v_{1}$. Hence (7) cannot
be derived from (5) by a simple union bound.

Now we will prove that trivially
$\eqref{equ:strong}\implies\eqref{equ:transfer-conclu}$. Given $v_{0}\to
v^{\prime}$, the vertex $v_{1}$ is determined by the truncated path from
$v^{\prime}$, which depends on $x,a_{>i}$. By (7), with probability at least
$1-2^{-k}$, for all vertex $v_{1}$, the truncated path from $v_{1}$ will not
stop at $V_{i}^{(2)}$. As a result, starting at the particular vertex $v_{1}$
picked by the program does not stop at $V^{(2)}_{i}$.

But for $\eqref{equ:transfer-asumpt}\implies\eqref{equ:transfer-conclu}$, the
argument breaks down. This is due to the following adaptivity issue: Consider
an adversary who, after observing $(a_{i+1},b_{i+1}),\dots,(a_{T},b_{T})$,
figures out the value of $x$, and picks the worst vertex $v_{1}$ maximizing
$\mathop{\mathbf{Pr}}_{a_{\leq i}}\left[\text{truncated path from }v_{1}\text{
stops at $V^{(2)}_{i}$}\ \middle|\ \text{value of }x,\ v_{0}\to
v^{\prime}\right].$ Then we will have no control over such probability.

$v_{0}$$v^{\prime}$$v_{1}$$v_{1}$$v$$x,a_{\leq i}$$x,a_{>i}$

Figure 7: The adaptivity issue.

Here the adaptivity issue comes from the following fact: The choice of $v_{1}$
(conditioning on $v_{0}\to v^{\prime}$) depends on $x$, but at the same time,
the truncated path from $v_{1}$ (before layer $i$) also depends on $x$. (See
Figure 7.) Although the choice of $v_{1}$ depends on $v^{\prime},x,a_{>i}$, we
observe that $v^{\prime}$ and $a_{>i}$ do not contribute to the adaptivity
issue. This is because (1) we have already conditioned on a fixed
$v^{\prime}$, and (2) $a_{\leq i}$ and $v^{\prime}$ are (jointly) independent
of $a_{>i}$.

Luckily, such an adversary does not exist in our setting. This is because not
only $v_{1}$ is picked depending on $v^{\prime},x,a_{\leq i}$, but also it is
picked by a _one-pass algorithm with a small memory_. Since a one-pass
algorithm does not learn much about $x$, it cannot pick an adversarial $v_{1}$
based on $x$. This is the main idea of our proof.

##### Proof Overview.

We will now formalize the intuition that the one-pass algorithm $v^{\prime}\
\widetilde{\to}\ v_{1}$ cannot be a powerful adversary. By the analysis for
one-pass algorithms, there are two possibilities.

  * •

With $1-2^{-\Theta(\ell)}$ probability, $v^{\prime}\ \widetilde{\to}\ v_{1}$
does not trigger any stopping rule. We will denote this case as the “good
event” $G_{v^{\prime}}$. In this case, the algorithm learns only a negligible
amount of information about $x$.

More specifically, by our stopping rules, the posterior $\mathbb{P}_{x\mid
G_{v^{\prime}}\land v^{\prime}\ \widetilde{\to}\ v_{1}}$ cannot have
significant values, i.e., $\mathbb{P}_{x\mid G_{v^{\prime}}\land v^{\prime}\
\widetilde{\to}\ v_{1}}(x^{\prime})<2^{O(\ell)}\cdot 2^{-n}$.888We will
formally define $G_{v^{\prime}}$ in Definition 5. For technical reasons,
$G_{v^{\prime}}\land v^{\prime}\ \widetilde{\to}\ v_{1}$ is not the same as
$v^{\prime}\to v_{1}$. We will explain such difference fully in the remark
following Definition 5.  We say the distribution $\mathbb{P}_{x\mid
G_{v^{\prime}}\land v^{\prime}\ \widetilde{\to}\ v_{1}}$ is flat if and only
if this holds. This implies that for all $x^{\prime}\in X$,

$\displaystyle\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\
\widetilde{\to}\ v_{1})\mid x=x^{\prime}]$
$\displaystyle=\frac{\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\
\widetilde{\to}\ v_{1})]\cdot\mathbb{P}_{x\mid G_{v^{\prime}}\land(v^{\prime}\
\widetilde{\to}\ v_{1})}(x^{\prime})}{\mathop{\mathbf{Pr}}[x=x^{\prime}]}$
$\displaystyle\leq
2^{O(\ell)}\cdot\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\
\widetilde{\to}\ v_{1})].$

Intuitively, because the distribution $\mathbb{P}_{x\mid
G_{v^{\prime}}\land(v^{\prime}\ \widetilde{\to}\ v_{1})}$ is flat, when
$G_{v^{\prime}}$ happens, the choice of $v_{1}$ almost does not depend on the
value of $x$. Hence the adversary is picking $v_{1}$ “almost non-adaptively”.

  * •

With $2^{-\Theta(\ell)}$ probability, $v^{\prime}\ \widetilde{\to}\ v_{1}$
stops. We denote this as the event $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}$, and this is saying that for all fixed $v^{\prime}$,
$\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]\leq 2^{-\Theta(\ell)}$. If $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}$ happens, the one pass adversary $v^{\prime}\
\widetilde{\to}\ v_{1}$ may have learned some nontrivial information about
$x$.

We need to upper bound the overall probability that, from $v_{0}$, we reach a
vertex $v^{\prime}\in V^{(1)}_{i}$ such that $G_{v^{\prime}}$ happens.
Formally, this is the probability

$\sum_{v^{\prime}\in V^{(1)}_{i}}\mathop{\mathbf{Pr}}[(v_{0}\to
v^{\prime})\land\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}].$

Note the events $\\{v_{0}\to v^{\prime}\\}_{v^{\prime}\in V_{i}^{(1)}}$ are
disjoint. So we can interpret it as follows: A one-pass adversary $v_{0}\to
v^{\prime}$ picks a vertex $v^{\prime}$. Then we check if $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}$ happens for that $v^{\prime}$.

Here a similar adaptivity issue arises: $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G}_{v^{\prime}}$ depends on $x,a_{>i}$, but $v^{\prime}$ is picked by the
adversary $v_{0}\to v^{\prime}$ which depends on $x,a_{\leq i}$. Luckily, we
are able to perform the same trick again. In this case, the posterior
distribution $\mathbb{P}_{x\mid v_{0}\to v^{\prime}}$ is flat (for all
$x^{\prime}$, $\mathbb{P}_{x\mid v_{0}\to v^{\prime}}(x^{\prime})\leq
2^{O(\ell)}\cdot 2^{-n}$) due to our stopping rules.999Technically, $v_{0}\to
v^{\prime}$ only ensures that $v_{0}$ reaches $v^{\prime}$, and those
$x\in\mathrm{SigV}(v^{\prime})$ is not truncated yet. So the
$\mathbb{P}_{x\mid v_{0}\to v^{\prime}}$ may not be flat. This will make the
actual analysis a bit more complicated. We will handle this issue in Section
6.2.1.  Hence,

$\mathop{\mathbf{Pr}}[v_{0}\to v^{\prime}\mid
x=x^{\prime}]=\frac{\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]\cdot\mathbb{P}_{x\mid v_{0}\to
v^{\prime}}(x^{\prime})}{\mathop{\mathbf{Pr}}[x=x^{\prime}]}\leq
2^{O(\ell)}\cdot\mathop{\mathbf{Pr}}[v_{0}\to v^{\prime}].$

Intuitively, because $\mathbb{P}_{x\mid v_{0}\to v_{1}}$ is flat, the choice
of $v^{\prime}$ almost does not depend on the value of $x$. The adaptivity
issue then goes away.

###  6.2 Proof of the Transfer Lemma

We prove the transfer lemma in this section. We need two technical
ingredients, introduced in Section 6.2.1 and Section 6.2.2. The statement and
the proof of the lemma are given in Section 6.2.3.

####  6.2.1 Flat Truncated Path

First, we can assume $v^{\prime}$ is not significant (as otherwise the program
stops in the first pass anyway). For proving the transfer lemma, we introduce
$v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}$ to denote the event

$(v_{0}\to v^{\prime})\land\mathbbm{1}[\mathbb{P}_{x|v_{0}\to
v^{\prime}}(x)\leq 2^{\ell_{\mathrm{flat}}^{(1)}}\cdot 2^{-n}],$

where we define $\ell_{\mathrm{flat}}^{(1)}=3\ell_{\mathrm{sigs}}^{(1)}$ (note
that this is _different_ from the significant value threshold).

This definition ensures that $\mathbb{P}_{x\mid
v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}}$ is “flat”, in the
sense that it contains no significant values, as captured by the following
claim.

######  Claim 1.

For all $x^{\prime}\in X$, $\mathbb{P}_{x\mid
v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}}(x^{\prime})\leq
2^{\ell_{\mathrm{flat}}^{(1)}+1}\cdot 2^{-n}.$

###### Proof.

As $v^{\prime}$ is not significant, we have $\|\mathbb{P}_{x\mid v_{0}\to
v^{\prime}}\|\leq 2^{\ell_{\mathrm{sigs}}^{(1)}}\cdot 2^{-n}$. Hence, we have

$c\coloneqq\sum_{x^{\prime}\in X}\mathbb{P}_{x\mid v_{0}\to
v^{\prime}}(x^{\prime})\cdot\mathbbm{1}[\mathbb{P}_{x\mid v_{0}\to
v^{\prime}}(x^{\prime})\geq 2^{\ell_{\mathrm{flat}}^{(1)}}\cdot
2^{-n}]\leq\frac{2^{n}\cdot\|\mathbb{P}_{x\mid v_{0}\to
v^{\prime}}\|^{2}}{2^{\ell_{\mathrm{flat}}^{(1)}}\cdot
2^{-n}}\leq\frac{1}{2}.$

On the other hand, if $\mathbb{P}_{x\mid
v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}}(x^{\prime})>0$, we
must have $\mathbb{P}_{x\mid v_{0}\to v^{\prime}}(x^{\prime})\leq
2^{\ell_{\mathrm{flat}}^{(1)}}\cdot 2^{-n}$. Putting these two together, we
get

$\mathbb{P}_{x\mid
v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}}(x^{\prime})\leq\frac{\mathbb{P}_{x\mid
v_{0}\to v^{\prime}}(x^{\prime})}{1-c}\leq
2^{\ell_{\mathrm{flat}}^{(1)}+1}\cdot 2^{-n},$

as desired. ∎

For “flat” distributions, we have the following lemma. It will come in handy
in our analysis.

######  Lemma 5.

Consider drawing uniformly random $(x,a_{1},\dots,a_{T})$. Let $E\subseteq
X\times A^{T}$ be an event. Suppose there exists $p>0$ such that
$\mathop{\mathbf{Pr}}_{x,a_{1},\dots,a_{T}}[x=x^{\prime}|E]\leq 2^{p}\cdot
2^{-n}$ for all $x^{\prime}\in X$. Then, for all $x^{\prime}\in X$,

$\mathop{\mathbf{Pr}}_{a_{1},\dots,a_{T}}[E|x=x^{\prime}]\leq
2^{p}\cdot\mathop{\mathbf{Pr}}_{x,a_{1},\dots,a_{T}}[E].$

###### Proof.

By Bayes’ rule:

$\mathop{\mathbf{Pr}}[E|x=x^{\prime}]=\frac{\mathop{\mathbf{Pr}}[x=x^{\prime}|E]\cdot\mathop{\mathbf{Pr}}[E]}{\mathop{\mathbf{Pr}}[x=x^{\prime}]}\leq
2^{p}\cdot\mathop{\mathbf{Pr}}[E].$

∎

####  6.2.2 Good Events

Before we present the transfer lemma, we have to make some definitions and
claims about the one-pass learning algorithm.

######  Definition 5 (Good Event $G_{v^{\prime}}$).

Let $B$ be our branching program. For every vertex $v^{\prime}\in
V^{(1)}_{i}$, consider the sub-program $B^{\prime}$ starting at $v^{\prime}$
and ending in the last layer of the first pass.

Consider this sub-program $B^{\prime}$ as _the whole program_ and $v^{\prime}$
as the starting point. We define $G_{v^{\prime}}$ as the event given by
applying Theorem 4 on $B^{\prime}$ with parameters
$(4\cdot\ell_{\mathrm{sigs}}^{(1)},{r_{\mathrm{len}}})$.

All we need from $G_{v^{\prime}}$ are the following two properties stated in
Theorem 4. First,

$\mathop{\mathbf{Pr}}_{x,a_{i+1},\dots,a_{T}}[(x,a_{i+1},\dots,a_{T})\not\in
G_{v^{\prime}}]\leq 2^{-4\ell_{\mathrm{sigs}}^{(1)}}.$ (8)

Moreover, for every $v_{1}\in V^{(0)}_{T}$, we have

$\|\mathbb{P}_{x|(v^{\prime}\ \widetilde{\to}\ v_{1})\land
G_{v^{\prime}}}\|_{\infty}\leq 2^{12\ell_{\mathrm{sigs}}^{(1)}+4}\cdot
2^{-n}.$ (9)

##### Remark on Definition 5

For $G_{v^{\prime}}$, the subtlety is that the conditional probabilities used
in the stopping rules are defined w.r.t. _the truncated paths in $B^{\prime}$
starting from $v^{\prime}$_ instead of _the truncated paths in $B$ starting
from $v_{0}$_. This makes a huge difference, for example,
$G_{v^{\prime}}\land(v^{\prime}\ \widetilde{\to}\ v_{1})$ is not the same as
$v^{\prime}\to v_{1}$. (except for the special case of $v^{\prime}=v_{0}$,
where the two events $G_{v_{0}}\land(v_{0}\ \widetilde{\to}\ v_{1})$ and
$v_{0}\to v_{1}$ do coincide.)

We will need the fact that such a good event usually happens.

######  Claim 2 ($G_{v^{\prime}}$ usually happens).

For every non-significant state $v^{\prime}\in V_{i}^{(1)}$, it holds that

$\mathop{\mathbf{Pr}}[(v_{0}\to v^{\prime})\land\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]\leq
2^{-\ell_{\mathrm{sigs}}^{(1)}+2}\cdot\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}].$

###### Proof.

Depending on whether $v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}$
happens, we have

$\mathop{\mathbf{Pr}}[(v_{0}\to v^{\prime})\land\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]\leq\mathop{\mathbf{Pr}}[(v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime})\land\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]+\mathop{\mathbf{Pr}}[(v_{0}\to
v^{\prime})\land\lnot(v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime})].$

For the first term, we have

$\displaystyle\mathop{\mathbf{Pr}}[(v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime})\land\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]$ $\displaystyle=\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]\mathop{\mathbf{Pr}}[v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}\mid\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}].$

Observe that $v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}$ depends
on $x,a_{\leq i}$, while $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}$ depends on $x,a_{>i}$. This means that for all
$x^{\prime}\in X$,

$(v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime})\perp(G_{v^{\prime}})\mid
x=x^{\prime}.$

Hence,

$\displaystyle\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]\mathop{\mathbf{Pr}}[v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}\mid\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]$ $\displaystyle\leq\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}]\cdot\max_{x^{\prime}\in
X}\\{\mathop{\mathbf{Pr}}[v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}\mid
x=x^{\prime}]\\}$ $\displaystyle\leq
2^{-4\ell_{\mathrm{sigs}}^{(1)}}\cdot\max_{x^{\prime}\in
X}\\{\mathop{\mathbf{Pr}}[v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}\mid
x=x^{\prime}]$ (Eq. (8)) $\displaystyle\leq
2^{-4\ell_{\mathrm{sigs}}^{(1)}}\cdot\mathop{\mathbf{Pr}}[v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime}]\cdot
2^{\ell_{\mathrm{flat}}^{(1)}+1}$ (1, Lemma 5) $\displaystyle\leq
2^{-\ell_{\mathrm{sigs}}^{(1)}+1}\cdot\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}].$

For the second term, we have

$\displaystyle\mathop{\mathbf{Pr}}[(v_{0}\to
v^{\prime})\land\lnot(v_{0}\overset{\mathrm{flat}}{\longrightarrow}v^{\prime})]$
$\displaystyle=\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]\cdot\mathop{\mathbf{Pr}}_{x\sim\mathbb{P}_{x|v_{0}\to
v^{\prime}}}[\mathbb{P}_{x|v_{0}\to v^{\prime}}(x)\geq
2^{3\ell_{\mathrm{sigs}}^{(1)}-n}]$
$\displaystyle\leq\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]\cdot\frac{2^{n}\cdot\|\mathbb{P}_{x|v_{0}\to
v^{\prime}}\|^{2}}{2^{3\ell_{\mathrm{sigs}}^{(1)}-n}}$
($\ell_{\infty}$-truncation trick) $\displaystyle\leq
2^{-\ell_{\mathrm{sigs}}^{(1)}+1}\cdot\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}].$ ($v^{\prime}$ is not significant)

Combining both cases completes the proof. ∎

####  6.2.3 Proof of the Main Lemma

With these preparations, we can prove this subsection’s main lemma, which
helps us “transfer” from $(v_{1}\to v)$ to $(v_{0}\to v)$. We recall the
statement below.

See 4

###### Proof.

We first decompose our goal according to the event $G_{v^{\prime}}$,

$\displaystyle\sum_{v_{1}\in V^{(1)}_{T}}\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[(v_{0}\to v)\land E(x,v)]$
$\displaystyle\leq$ $\displaystyle\sum_{v_{1}\in V^{(1)}_{T}}\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v_{0}\to
v)\land E(x,v)]+$ (10) $\displaystyle\sum_{v_{1}\in V^{(1)}_{T}}\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}\land(v_{0}\to v)].$ (11)

For the first term, note that $v_{0}\to v$ is equivalent to $(v_{1}\to
v)\land(v^{\prime}\to v_{1})$. Simply by chain rule

$\displaystyle\eqref{equ:non-stop}$ $\displaystyle=\sum_{v_{1}\in
V^{(1)}_{T}}\sum_{v\in S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[(v_{1}\to
v)\land E(x,v)\leavevmode\nobreak\ \land\leavevmode\nobreak\
G_{v^{\prime}}\land(v^{\prime}\to v_{1})]$ $\displaystyle=\sum_{v_{1}\in
V^{(1)}_{T}}\sum_{v\in S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[(v_{1}\to
v)\land E(x,v)]\cdot\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\to
v_{1})\mid(v_{1}\to v)\land E(x,v)]$ $\displaystyle\leq\sum_{v_{1}\in
V^{(1)}_{T}}\sum_{v\in S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[(v_{1}\to
v)\land E(x,v)]\cdot\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\
\widetilde{\to}\ v_{1})\mid(v_{1}\to v)\land E(x,v)].$

Here the inequality holds since $v^{\prime}\to v_{1}$ implies $v^{\prime}\
\widetilde{\to}\ v_{1}$. Notice that the event $G_{v^{\prime}}\land
v^{\prime}\ \widetilde{\to}\ v_{1}$ only depends on $x$ and $a_{>i}$ while the
event $v_{1}\to v\land E(x,v)$ only depends on $x$ and $a_{\leq i}$. This
means that for all $x^{\prime}\in\\{0,1\\}^{n}$,

$((v_{1}\to v)\land E(x,v))\perp(G_{v^{\prime}}\land(v^{\prime}\
\widetilde{\to}\ v_{1}))\mid x=x^{\prime}.$

Hence,

$\displaystyle\eqref{equ:non-stop}$ $\displaystyle\leq\sum_{v_{1}\in
V^{(1)}_{T}}\left(\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[(v_{1}\to v)\land
E(x,v)]\right)\cdot\max_{x^{\prime}\in
X}\\{\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\ \widetilde{\to}\
v_{1})\mid x=x^{\prime}]\\}$ $\displaystyle\leq\sum_{v_{1}\in
V^{(1)}_{T}}\mathop{\mathbf{Pr}}[v_{0}\to v^{\prime}]\cdot
2^{-k}\cdot\max_{x^{\prime}\in
X}\\{\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\ \widetilde{\to}\
v_{1})\mid x=x^{\prime}]\\}$ (By Assumption (3))
$\displaystyle\leq\sum_{v_{1}\in V^{(1)}_{T}}\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}]\cdot
2^{-k}\cdot\mathop{\mathbf{Pr}}[G_{v^{\prime}}\land(v^{\prime}\
\widetilde{\to}\ v_{1})]\cdot 2^{12\ell_{\mathrm{sigs}}^{(1)}+4}$ (By Lemma 5
and Eq. (9)) $\displaystyle\leq\mathop{\mathbf{Pr}}[v_{0}\to v^{\prime}]\cdot
2^{12\ell_{\mathrm{sigs}}^{(1)}-k+4}.$

For the second term, notice that $v_{0}\to v$ implies $(v_{0}\to
v^{\prime})\land(v^{\prime}\ \widetilde{\to}\ v)$. We have

$\displaystyle\eqref{equ:stop}$ $\displaystyle=\sum_{v_{1}\in
V^{(1)}_{T}}\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}\land(v_{0}\to v)]$ $\displaystyle\leq\sum_{v_{1}\in
V^{(1)}_{T}}\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}\land(v_{0}\to v^{\prime})\land(v^{\prime}\
\widetilde{\to}\ v)]$ $\displaystyle\leq\mathop{\mathbf{Pr}}[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{G_{v^{\prime}}}\land(v_{0}\to v^{\prime})]$ (The events $\\{v^{\prime}\
\widetilde{\to}\ v\\}_{v\in V^{(2)}_{i}}$ are mutually exclusive)
$\displaystyle\leq
2^{-\ell_{\mathrm{sigs}}^{(1)}+1}\cdot\mathop{\mathbf{Pr}}[v_{0}\to
v^{\prime}].$ (By Claim 2)

These two parts together finish the proof of this lemma. ∎

##  7 Proof of the Two-Pass Result

We are ready to prove Theorem 5.

###  7.1 Analyzing the Success Probability

First, we would like to show that the program stops with a very small
probability. We will analyze stopping due to different rules separately. Here
is an outline:

  * •

Stop in the first pass: see Section 7.1.1

  * •

Stop due to traversing too many high-probability edges: see Section 7.1.2.

  * •

Stop due to traversing a bad edge in the second pass: see Section 7.1.3.

  * •

Stop due to significant values or $\mathrm{cnt}_{\mathrm{bias}}$ overflow in
the second pass: see Section 7.1.4.

  * •

Stop due to reaching a significant state in the second pass: see Section
7.1.5.

Finally, we wrap up the analysis in Section 7.1.6.

####  7.1.1 Stop in the First Pass

Applying Theorem 4 and verifying the parameters, we conclude that the program
stops in the first pass with probability at most $2^{-\ell}$.

####  7.1.2 Too Many High-Probability Edges

For each vertex $v_{1}$ at the end of the first pass, let $E_{v_{1}}$ be the
event the program starts from $v_{1}$ and traverses more than
$\ell_{\mathrm{high}}=\ell$ high-probability edges. We would like to prove

$\sum_{v_{1}}\mathop{\mathbf{Pr}}[v_{0}\to
v_{1}]\mathop{\mathbf{Pr}}[E_{v_{1}}|v_{0}\to v_{1}]\leq
2^{-\frac{{k_{\mathrm{ext}}}\ell}{4}}.$

We observe that

$\displaystyle\sum_{v_{1}}\mathop{\mathbf{Pr}}[v_{0}\to
v_{1}]\mathop{\mathbf{Pr}}[E_{v_{1}}|v_{0}\to
v_{1}]\leq\sum_{v_{1}}\mathop{\mathbf{Pr}}[E_{v_{1}}].$

Fix one vertex $v_{1}$. It suffices to show that
$\mathop{\mathbf{Pr}}[E_{v_{1}}]\leq 2^{-\frac{{k_{\mathrm{ext}}}\ell}{3}}$.
The desired bound follows because there are at most
$2^{\frac{{k_{\mathrm{ext}}}\ell}{32}}$ many $v_{1}$’s.

We first observe a simple fact.

######  Fact 1.

For any vertex $v$ in the second pass, it holds that $|\mathrm{High}(v)|\leq
2^{n-\frac{{k_{\mathrm{ext}}}}{2}}$.

This follows because, under some distribution over the next sample $a_{i+1}$
(namely, the distribution of $a_{i+1}$ conditioned on $v_{0}\to v$), each
high-probability edge occurs with probability at least
$2^{-n+\frac{{k_{\mathrm{ext}}}}{2}}$. As such, there can be at most
$2^{n-\frac{{k_{\mathrm{ext}}}}{2}}$ such edges.

Now we are ready to upper bound $\mathop{\mathbf{Pr}}[E_{v_{1}}]$. The key
point is that when we analyze $E_{v_{1}}$ without conditioning anything about
$a_{i}$, we have that _all of_ $a_{i}$’s are uniformly random. Since
$|\mathrm{High}(v)|\leq 2^{n-\frac{{k_{\mathrm{ext}}}}{2}}$ by Fact 1, over
uniformly random samples, the next edge $a_{i+1}$ belongs to
$\mathrm{High}(v)$ with probability at most
$2^{-\frac{{k_{\mathrm{ext}}}}{2}}$. We can union-bound over the $T$ edges,
and conclude that

$\mathop{\mathbf{Pr}}[E_{v_{1}}]\leq\binom{T}{\ell}2^{-\frac{{k_{\mathrm{ext}}}\ell}{2}}\leq
2^{-\frac{{k_{\mathrm{ext}}}\ell}{3}}.$

Finally, summing up $\mathop{\mathbf{Pr}}[E_{v_{1}}]$ over $v_{1}$ completes
the proof.

##### Comparison with [GRT19].

We note that our proof for high-probability edge overflow is significantly
simpler than the one presented in [GRT19], which required the use of
information theory and a quite delicate calculation. Furthermore, our proof
can upper bound the stopping probability by an exponentially small quantity,
whereas [GRT19] can only get a constant (e.g., $\frac{1}{100}$) upper bound.
Having an exponentially small stopping probability is crucial for extending
our result to the multi-pass case.

####  7.1.3 Stop Due to Bad Edges

By the extractor property, for each non-significant $v$ in the second pass, we
have $|\mathrm{Bad}(v)|\leq 2^{n-{k_{\mathrm{ext}}}}$. Therefore,

$\displaystyle\mathop{\mathbf{Pr}}[\text{stop due to bad edge in the second
pass}]$ $\displaystyle\qquad=\sum_{i=0}^{T-1}\sum_{v\in
V^{(2)}_{i}}\mathop{\mathbf{Pr}}[v_{0}\to
v]\cdot\mathop{\mathbf{Pr}}[a_{i+1}\in\mathrm{Bad}(v)\setminus\mathrm{High}(v)|v_{0}\to
v]$ $\displaystyle\qquad\leq\sum_{i=0}^{T-1}\mathop{\mathbf{Pr}}[v_{0}\to
v]\cdot 2^{n-{k_{\mathrm{ext}}}}\cdot 2^{\frac{{k_{\mathrm{ext}}}}{2}-n}$
$\displaystyle\qquad\leq T\cdot 2^{-\frac{{k_{\mathrm{ext}}}}{2}}.$

####  7.1.4 Stop Due to Significant Values and Bias Counters (via the Transfer
Lemma)

We show that the probability of stopping due to significant values or counter-
overflow is small, using the tools developed in Section 5 and Section 6.

Fix one $i\in[T]$. We define the “bad event” indicator $E:X\times
V^{(2)}_{i}\to\\{0,1\\}$. For each $v\in V^{(2)}_{i}$, we define:

  * •

If $v$ is a significant state, we set $E(x,v)\equiv 0$ for all $x$. We will
bound the probability of reaching such states in Section 7.1.5.

  * •

If $v$ not significant but
$\mathrm{cnt}_{\mathrm{bias}}(v)>\ell_{\mathrm{bias}}^{(2)}$, then
$E(x,v)\equiv 1$ for all $x$.

  * •

Otherwise, we set $E(x,v)=\mathbbm{1}[x\in\mathrm{SigV}(v)]$.

We would like to show that

$\sum_{v\in V^{(2)}_{i}}\mathop{\mathbf{Pr}}[(v_{0}\to v)\land E(x,v)]\leq
2^{-\ell+O(1)}.$

Once this is established, we can union-bound over $i\in[T]$ to finish the
proof.

We would like to apply Lemma 4. Let us first establish the assumption required
in Lemma 4. Fix $v^{\prime}\in V^{(1)}_{i}$ and $v_{1}\in V^{(2)}_{0}$. Recall
we have defined $S_{v^{\prime},v_{1},i}$ as the set of $v\in V^{(2)}_{i}$ that
remembers $v^{\prime}$ and $v_{1}$. Then, observe that

$\displaystyle\sum_{\begin{subarray}{c}v\in S_{v^{\prime},v_{1},i}\\\ v\text{
not significant}\end{subarray}}\mathop{\mathbf{Pr}}[(v_{1}\to
v)\land\mathbbm{1}[x\in\mathrm{SigV}(v)]]$ $\displaystyle\qquad\leq\sum_{v\in
S_{v^{\prime},v_{1},i}}\mathop{\mathbf{Pr}}[v_{1}\to v]\cdot
2^{2\ell_{\mathrm{sigs}}^{(2)}-{\ell_{\mathrm{sigv}}}}$ (by
$\ell_{\infty}$-truncation trick)