Graduate School of Science and Engineering, Yamagata University, Jonan 4-3-16,
Yonezawa-shi Yamagata, 992-8510<EMAIL_ADDRESS>School of Science and Engineering, Yamagata University, Jonan 4-3-16,
Yonezawa-shi Yamagata, 992-8510 Japan. Kei Uchizawa and Haruki Abe [100]Theory
of computation Models of computation 1 2021 1

# Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and
Energy

Kei Uchizawa  Haruki Abe

###### Abstract

In this paper, we investigate computational power of threshold circuits and
other theoretical models of neural networks in terms of the following four
complexity measures: size (the number of gates), depth, weight and energy.
Here the energy complexity of a circuit measures sparsity of their
computation, and is defined as the maximum number of gates outputting non-zero
values taken over all the input assignments.

As our main result, we prove that any threshold circuit $C$ of size $s$, depth
$d$, energy $e$ and weight $w$ satisfies $\log(rk(M_{C}))\leq ed(\log s+\log
w+\log n)$, where $rk(M_{C})$ is the rank of the communication matrix $M_{C}$
of a $2n$-variable Boolean function that $C$ computes. Thus, such a threshold
circuit $C$ is able to compute only a Boolean function of which communication
matrix has rank bounded by a product of logarithmic factors of $s,w$ and
linear factors of $d,e$. This implies an exponential lower bound on the size
of even sublinear-depth threshold circuit if energy and weight are
sufficiently small. For example, we can obtain an exponential lower bound
$s=2^{\Omega(n^{1/3})}$ even for threshold circuits of depth $n^{1/3}$, energy
$n^{1/3}$ and weight $2^{o(n^{1/3})}$. We also show that the inequality is
tight up to a constant factor when the depth $d$ and energy $e$ satisfies
$ed=o(n/\log n)$.

For other models of neural networks such as a discretized ReLE circuits and
decretized sigmoid circuits, we prove that a similar inequality also holds for
a discretized circuit $C$: $rk(M_{C})=O(ed(\log s+\log w+\log n)^{3})$. We
obtain this inequality by showing that any discretized circuit can be
simulated by a threshold circuit with moderate increase of size, depth, energy
and weight. Thus, if we consider the number of non-zero output values as a
measure for sparse activity of a neural network, our results suggest that
larger depth linearly helps neural networks to acquire sparse activity.

###### keywords:

Circuit complexity, disjointness function, eqaulity function, neural networks,
threshold circuits, ReLU cicuits, sigmoid circuits, sprase activity

##  1 Introduction

Background. DiCarlo and Cox argued that constructing good internal
representations is crucial to perform visual information processing, such as
object recognition, for neural networks in the brain [6]. Here, an internal
representation is described by a vector in a very high dimensional space,
where each axis is one neuron’s activity and the dimensionality equals to the
number (e.g., $\sim$1 million) of neurons in a feedforward neural network.
They call representations good if a given pair of two images that are hard to
distinguish at the input space, but the resulting representations for them are
easy to separate by simple classifiers such as a linear classifier. While such
internal representations are likely to play fundamental role in information
processing in the brain, it is also known that a neuron needs relatively high
energy to be active [19, 30], and hence neural networks are forced to acquire
representations supported by only a small number of active neurons [8]. These
observations pose a question: for what information processing can neural
networks construct good internal representations?

In the paper [44], Uchizawa _et al._ address the question from the viewpoint
of circuit complexity. More formally, they employed threshold circuits as a
model of neural networks [26, 27, 31, 34, 36, 37, 38], and introduced a
complexity measure, called energy complexity, for sparsity of their internal
representations. A threshold circuit is a feedforward logic circuit whose
basic computational element computes a linear threshold function, and energy
of a circuit is defined as the maximum number of internal gates outputting
ones over all the input assignments. (See also [7, 17, 35, 39, 47] for studies
on energy complexity of other types of logic circuits). Uchizawa _et al._ then
show that the energy complexity is closely related to the rank of linear
decision trees. In particular, they prove that any linear decision tree of $l$
leaves can be simulated by a threshold circuit of size $O(l)$ and energy
$O(\log l)$. Thus, even logarithmic-energy threshold circuits have certain
computational power: any linear decision tree of polynomial number of leaves
can be simulated by a polynomial-size and logarithmic-energy threshold
circuit.

Following the paper [44], a sequence of papers show relations among other
major complexity measures such as size (the number of gates), depth, weight
and fan-in [24, 40, 41, 45, 43, 42, 46]. In particular, Uchizawa and Takimoto
[45] showed that any threshold circuit $C$ of depth $d$ and energy $e$
requires size $s=2^{\Omega(n/e^{d})}$ if $C$ computes a high bounded-error
communication complexity function such as Inner-Product function. Even for low
communication complexity functions, an exponential lower bound on the size is
known for constant-depth threshold circuits: any threshold circuit $C$ of
depth $d$ and energy $e$ requires size $s=2^{\Omega(n/e2^{e+d}\log^{e}n)}$ if
$C$ computes the parity function [43]. These results provide exponential lower
bounds if the depth is constant and energy is sub-linear [45] or sub-
logarithmic [43], while both Inner-Product function and Parity function are
computable by linear-size, constant-depth, and linear energy threshold
circuits. Thus these results imply that the energy complexity strongly related
to representational power of threshold circuits. However these lower bounds
break down when we consider threshold circuits of larger depth and energy,
say, non-constant depth and sub-linear energy.

Our Results for Threshold Circuits. In this paper, we prove that simple
Boolean functions are hard even for sub-linear depth and sub-linear energy
threshold circuits. Let $C$ be a threshold circuit with Boolean input
variables ${\mathbf{x}}=(x_{1},x_{2},\dots,x_{n})$ and
${\mathbf{y}}=(y_{1},y_{2},\dots,y_{n})$. A communication matrix $M_{C}$ of
$C$ is a $2^{n}\times 2^{n}$ matrix where each row (resp., each column) is
indexed by an assignment ${\mathbf{a}}\in\\{0,1\\}^{n}$ to ${\mathbf{x}}$
(resp., ${\mathbf{b}}\in\\{0,1\\}^{n}$ to ${\mathbf{y}}$), and the value
$M_{C}[{\mathbf{a}},{\mathbf{b}}]$ is defined to be the output of $C$ given
${\mathbf{a}}$ and ${\mathbf{b}}$. We denote by $rk(M_{C})$ the rank of
$M_{C}$ over $\mathbb{F}_{2}$. Our main result is the following relation among
size, depth energy and weight.

######  Theorem 1.1.

Let $s,d,e$ and $w$ be integers satisfying $2\leq s,d$, $10\leq e$, $1\leq w$.
If a threshold circuit $C$ computes a Boolean function of $2n$ variables, and
has size $s$, depth $d$, energy $e$ and weight $w$, then it holds that

$\log(rk(M_{C}))\leq ed(\log s+\log w+\log n).$ (1)

The theorem implies exponential lower bounds for sub-linear depth and sub-
linear energy threshold circuits. As an example, let us consider a Boolean
function defined as follows: For a $2n$ input variables $x_{1},\dots,x_{n}$
and $y_{1},\dots,y_{n}$,

We note that is a biologically motivated Boolean function: Maass [22] defined
to model coincidence detection or a pattern matching, and Lynch and Musco [20]
introduced a related problem, called Filter problem, for studying theoretical
aspect of spiking neural networks. Since is the complement of the well-studied
Boolean function, the disjointness function, the rank of is $2^{n}$ [15].
Thus, the theorem implies that

$n\leq ed(\log s+\log w+\log n)$ (2)

holds if a threshold circuit $C$ computes . Arranging Eq. (2), we can obtain a
lower bound $2^{n/(ed)}/(wn)\leq s$ which is exponential in $n$ if both $d$
and $e$ are sub-linear and $w$ is sub-exponential. For example, we can obtain
an exponential lower bound $s=2^{\Omega(n^{1/3})}$ even for threshold circuits
of depth $n^{1/3}$, energy $n^{1/3}$ and weight $2^{o(n^{1/3})}$. We can
obtain similar lower bounds for the Inner-Product function and the equality
function, since they have linear rank.

Comparing the lower bound $s=2^{\Omega(n/e^{d})}$ given in [45] to ours, our
lower bound is meaningful only for sub-exponential weight, but improves on it
in two-fold: the lower bound is exponential even if $d$ is sub-linear, and
provide a nontrivial lower bound for Boolean functions with much weaker
condition: Threshold circuits need exponential size even for Boolean functions
of the standard rank $\Omega(n)$.

Threshold circuits have received considerable attention in circuit complexity,
and a number of lower bound arguments have developed for threshold circuits
under some restrictions on computational resources including size, depth,
energy and weight [1, 2, 4, 10, 11, 14, 16, 24, 29, 33, 43, 45, 46]. However,
the arguments for lower bounds are designated for constant-depth threshold
circuits, and hence cannot provide meaningful ones when the depth is not
constant. In particular, is computable by a depth-2 and linear-size threshold
circuit. Thus, directly applying known techniques are unlikely to yield an
exponential lower bound for .

To complement Theorem 1.1, we also show that the lower bound is tight up to a
constant factor if the product of $e$ and $d$ are small:

######  Theorem 1.2.

For any integers $e$ and $d$ such that $2\leq e$ and $2\leq d$,
$\mathrm{DISJ}_{n}$ is computable by a threshold circuit of size

$s\leq(e-1)(d-1)\cdot 2^{\frac{n}{(e-1)(d-1)}}.$

depth $d$, energy $e$ and weight

$w\leq\left(\frac{n}{(e-1)(d-1)}\right)^{2}.$

Substituting $s,d,e$ and $w$ of a threshold circuit given in Theorem 1.2 to
the right hand side of Eq. (2), we have

$\displaystyle ed(\log s+\log w+\log n)$ $\displaystyle\leq$ $\displaystyle
ed\left(\frac{n}{(e-1)(d-1)}\\!+\\!\log(e-1)(d-1)\\!+\\!\log\left(\frac{n}{(e-1)(d-1)}\right)^{2}\\!+\\!\log
n\right)$ $\displaystyle\leq$ $\displaystyle 4n+O(ed\log n),$

which almost matches the left hand side of Eq. (2) if $ed=o(n/\log n)$. Thus,
Theorem 1.1 neatly captures the computational aspect of threshold circuits
computing . Recall that any linear decision tree of polynomial number of
leaves can be simulated by a polynomial-size and logarithmic-energy threshold
circuit [44]. Also, it is known that any Boolean function is computable by a
threshold circuit of energy one if exponential size is allowed [24]. Thus, we
believe that the situation $ed=o(n/\log n)$ is not too restrictive. we We also
show that the lower bound is also tight for the equality function.

Our Result for Discretized Circuits. Besides threshold circuits, we consider
other other well-studied model of neural network, where an activation function
and weights of an computational element are discretized (such as, discretized
sigmoid or ReLU circuits). The size, depth, energy and weight are important
parameters also for artificial neural networks. The size and depth are major
topics on success of deep learning. The energy is related to important
techniques for deep learning method such as regularization, sparse coding, or
sparse autoencoder [12, 18, 28]. The weight resolution is closely related to
chip resources in neuromorphic hardware systems [32], and quantization schemes
received attention [5, 13].

We define similar notions for the energy and weight of a discretized circuit,
and show that any discretized circuit can be simulated by a threshold circuit
with a moderate increase in size, depth, energy, and weight. Consequently,
combining with Theorem 1.1, we can show that the rank is bounded by a product
of the polylogarithmic factors of $s,w$ and linear factors of $d,e$ for
discretized circuits. For example, we can obtain the following proposition for
sigmoid circuits:

######  Theorem 1.3.

If a sigmoid circuit $C$ of size $s$, depth $d$, energy $e$, and weight $w$
computes a Boolean function $f$, then it holds that

$\log(rk(M_{C}))=O(ed(\log s+\log w+\log n)^{3}).$

Maass, Schnitger and Sontag [21] showed that a sigmoid circuit could be
simulated by a threshold circuit, but their simulation was optimized to be
depth-efficient and did not consider energy. Thus, their result does not fit
into our purpose.

Theorems 1.1 and 1.3 imply that a threshold circuit or discretized circuit are
able to compute a Boolean function of bounded rank. Thus, we can consider
these theorems as bounds on corresponding concept classes. According to the
bound, $c$ times larger depth is comparable to $2^{c}$ times larger size.
Thus, large depth could enormously help neural networks to increase its
expressive power. Also, the bound suggests that increasing depth could also
help a neural network to acquire sparse activity when we have hardware
constraints on both the number of neurons and the weight resolution. These
observations may shed some light on the reason for the success of deep
learning.

Organization. The rest of the paper is organized as follows. In Section 2, we
define terms needed for analysis. In Section 3, we present our main lower
bound result. In Section 4, we show the tightness of the bound by constructing
a threshold circuit computing . In Section 5, we show that a discretized
circuit can be simulated by a threshold circuit. In Section 6, we conclude
with some remarks.

##  2 Preliminaries

For an integer $n$, we denote by $[n]$ a set $\\{1,2,\dots n\\}$. The base of
the logarithm is two unless stated otherwise. In Section 2.1, we define terms
on threshold circuits and discretized circuits. In Section 2.2, we define
communication matrix, and present some known facts.

###  2.1 Circuit Model

In Sections 2.1.1 and 2.1.2, we give definitions of threshold and discritized
circuits, respectively.

####  2.1.1 Threshold Circuits

Let $k$ be a positive integer. A _threshold gate_ $g$ with $k$ input variables
$\xi_{1},\xi_{2},\dots,\xi_{k}$ has weights $w_{1},w_{2},\dots,w_{k}$, and a
threshold $t$. We define the output $g(\xi_{1},\xi_{2},\dots,\xi_{k})$ of $g$
as

$\displaystyle
g(\xi_{1},\xi_{2},\dots,\xi_{k})=\mathrm{sign}\left(\sum_{i=1}^{k}w_{i}\xi_{i}-t\right)=\left\\{\begin{array}[]{ll}1&\mbox{
if }t\leq\sum_{i=1}^{k}w_{i}\xi_{i};\\\ 0&\mbox{ otherwise}\end{array}\right.$

To evaluate the weight resolution, we assume single synaptic weight to be
discrete, and that $w_{1},w_{2},\dots,w_{n}$ are integers. The _weight $w_{g}$
of $g$_ is defined as the maximum of the absolute values of
$w_{1},w_{2},\dots,w_{k}$. In other words, we assume that
$w_{1},w_{2},\dots,w_{k}$ are $O(\log w_{g})$-bit coded discrete values.
Throughout the paper, we allow a gate to have both positive and negative
weights, although biological neurons are either excitatory (all the weights
are positive) or inhibitory (all the weights are negative). As mentioned in
[22], this relaxation has basically no impact on circuit complexity
investigations, unless one cares about constant blowup in computational
resources. This is because a single gate with positive and negative weights
can be simulated by a pair of excitatory and inhibitory gates.

A _threshold circuit_ $C$ is a combinatorial circuit consisting of threshold
gates, and is expressed by a directed acyclic graph. The nodes of in-degree 0
correspond to input variables, and the other nodes correspond to gates. Let
$G$ be a set of the gates in $C$. For each gate $g\in G$, the _level_ of $g$,
denoted by $\mathrm{lev}(g)$, is defined as the length of a longest path from
an input variable to $g$ on the underlying graph of $C$. For each $l\in[d]$,
we define $G_{l}$ as a set of gates in the $l$th level:

$G_{l}=\\{g\in G\mid\mathrm{lev}(g)=l\\}.$

Given an input assignment $({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$ to
$({\mathbf{x}},{\mathbf{y}})$, the outputs of the gates in $C$ are inductively
determined from the bottom level.

In this paper, we consider a threshold circuit $C$ for a Boolean function
$f:\\{0,1\\}^{2n}\to\\{0,1\\}$. Thus, $C$ has $2n$ Boolean input variables
${\mathbf{x}}=(x_{1},x_{2},\dots,x_{n})$ and
${\mathbf{y}}=(y_{1},y_{2},\dots,y_{n})$, and a unique output gate, denoted by
$g^{\mathrm{clf}}$, which is a linear classifier separating internal
representations given by the gates in the lower levels (possibly together with
input variables). Consider a gate $g$ in $C$. Let
$w^{x}_{1},w^{x}_{2},\dots,w^{x}_{n}$ (resp.,
$w^{y}_{1},w^{y}_{2},\dots,w^{y}_{n}$) be the weights for
$x_{1},x_{2},\dots,x_{n}$ (resp., $y_{1},y_{2},\dots,y_{n}$), and $t_{g}$ be
threshold of $g$. For each gate $h$ directed to $g$, let $w_{h,g}$ be a weight
of $g$ for the output of $h$. Then the output $g({\mathbf{x}},{\mathbf{y}})$
of $g$ is defined as

$g({\mathbf{x}},{\mathbf{y}})=\mathrm{sign}\left(p_{g}({\mathbf{x}},{\mathbf{y}})-t_{g}\right)$

where $p_{g}({\mathbf{x}},{\mathbf{y}})$ denotes a potentials of $g$ invoked
by the input variables and gates:

$p({\mathbf{x}},{\mathbf{y}})=\sum_{i=1}^{n}w^{x}_{i}x_{i}+\sum_{i=1}^{n}w^{y}_{i}y_{i}+\sum_{l=1}^{\mbox{{\scriptsize
lev}}(g)-1}\sum_{h\in G_{l}}w_{h,g}h({\mathbf{x}},{\mathbf{y}}).$

We sometimes write $p^{x}_{g}({\mathbf{x}})$ (resp.,
$p^{y}_{g}({\mathbf{y}})$) for the potential invoked by ${\mathbf{x}}$ (resp.,
${\mathbf{y}}$):

$p^{x}_{g}({\mathbf{x}})=\sum_{i=1}^{n}w^{x}_{i}x_{i}\quad\mbox{ and }\quad
p^{y}_{g}({\mathbf{y}})=\sum_{i=1}^{n}w^{y}_{i}y_{i}.$

Although the inputs to $g$ are not only ${\mathbf{x}}$ and ${\mathbf{y}}$ but
the outputs of gates in the lower levels, we write
$g({\mathbf{x}},{\mathbf{y}})$ for the output of $g$, because ${\mathbf{x}}$
and ${\mathbf{y}}$ inductively decide the output of $g$. We say that $C$
_computes_ a Boolean function $f:\\{0,1\\}^{2n}\to\\{0,1\\}$ if
$g^{\mathrm{clf}}({\mathbf{a}},{\mathbf{b}})=f({\mathbf{a}},{\mathbf{b}})$ for
every $({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$.

Let $C$ be a threshold circuit. We define _size_ $s$ of $C$ as the number of
the gates in $C$, and _depth_ $d$ of $C$ as the level of $g^{\mathrm{clf}}$.
We define the _energy_ $e$ of $C$ as

$e=\max_{({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}}\sum_{g\in
G}g({\mathbf{a}},{\mathbf{b}}).$

We define _weight_ $w$ of $C$ as the maximum of the weights of the gates in
$C$: $w=\max_{g\in G}w_{g}$.

####  2.1.2 Discretized Circuits

Let $\varphi$ be an activation function. Let $\delta$ be a discretizer that
maps a real number to a number representable by a bitwidth $b$. We define a
discretized activation function $\delta\circ\varphi$ as a composition of
$\varphi$ and $\delta$, that is, $\delta\circ\varphi(x)=\delta(\varphi(x))$
for any number $x$. We say that $\delta\circ\varphi$ has _silent range for an
interval $I$_ if $\delta\circ\varphi(x)=0$ if $x\in I$, and
$\delta\circ\varphi(x)\neq 0$, otherwise. For example, if we use the ReLU
function as the activation function $\varphi$, then $\delta\circ\varphi$ has
silent range for $I=(-\infty,0]$ for any discretizer $\delta$. If we use the
sigmoid function as the activation function $\varphi$ and linear partition as
discretizer $\delta$, then $\delta\circ\varphi$ has silent range for
$I=(-\infty,t_{\max}]$ where $t_{\max}=\ln(1/(2^{b}-1))$ where $\ln$ is the
natural logarithm.

Let $\delta\circ\varphi$ be a discretized activation function with silent
range. A _$(\delta\circ\varphi)$ -gate_ $g$ with $k$ input variables
$\xi_{1},\xi_{2},\dots,\xi_{k}$ has weights $w_{1},w_{2},\dots,w_{k}$ and a
threshold $t$, where each of the weights and threshold are discretized by
$\delta$. The output $g(\xi_{1},\xi_{2},\dots,\xi_{k})$ of $g$ is then defined
as

$\displaystyle
g(\xi_{1},\xi_{2},\dots,\xi_{k})=\delta\circ\varphi\left(\sum_{i=1}^{k}w_{i}\xi_{i}-t\right).$

A _$(\delta\circ\varphi)$ -circuit_ is a combinatorial circuit consisting of
$(\delta\circ\varphi)$-gates except that the top gate $g^{\mathrm{clf}}$ is a
threshold gate, that is, a linear classifier. We define size and depth of a
$(\delta\circ\varphi)$-circuit same as the ones for a threshold circuit. We
define energy $e$ of a $(\delta\circ\varphi)$-circuit as the maximum number of
gates outputting non-zero values in the circuit:

$e=\max_{({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}}\sum_{g\in G}\llbracket
g({\mathbf{a}},{\mathbf{b}})\neq 0\rrbracket$

where $\llbracket\mathrm{P}\rrbracket$ for a statement $P$ denote a notation
of the function which outputs one if $\mathrm{P}$ is true, and zero otherwise.
We define _weight_ $w$ of $C$ as $w=2^{2b}$, where $2b$ is the bitwidth
possibly needed to represent a potential value invoked by a single input of a
gate in $C$.

###  2.2 Communication Matrix and its Rank

Let $Z\subseteq\\{0,1\\}^{n}$. For a Boolean function $f:Z\times
Z\to\\{0,1\\}$, we define a communication matrix $M_{f}$ over $Z$ as a
$2^{|Z|}\times 2^{|Z|}$ matrix where each row and column are indexed by
${\mathbf{a}}\in Z$ and ${\mathbf{b}}\in Z$, respectively, and each entry is
defined as $M_{f}({\mathbf{a}},{\mathbf{b}})=f({\mathbf{a}},{\mathbf{b}})$. We
denote by $rk(M_{f})$ the rank of $M_{f}$ over $\mathbb{F}_{2}$. If a circuit
$C$ computes $f$, we may write $M_{C}$ instead of $M_{f}$. If a Boolean
function $f$ does not have an obvious separation of the input variables to
${\mathbf{x}}$ and ${\mathbf{y}}$, we may assume a separation so that
$rk(M_{f})$ is maximized.

Let $k$ and $n$ be natural numbers such that $k\leq n$. Let

$Z_{k}=\\{{\mathbf{a}}\in\\{0,1\\}^{n}\mid\mbox{The number of ones in
${\mathbf{a}}$ is at most $k$}\\}.$

A $k$-disjointness function $\mathrm{DISJ}_{n,k}$ over $Z_{k}$ is defines as
follows:

$\mathrm{DISJ}_{n,k}({\mathbf{x}},{\mathbf{y}})=\bigwedge_{i=1}^{n}\overline{x_{i}}\vee\overline{y_{i}}$

where the input assignments are chosen from $Z_{k}$. The book [15] contains a
simple proof showing $\mathrm{DISJ}_{n,k}$ has full rank.

######  Theorem 2.1 (Theorem 13.10 [15]).

$rk(M_{\mathrm{DISJ}_{n,k}})=\sum_{i=0}^{k}{n\choose i}$. In particular,
$rk(M_{\mathrm{DISJ}_{n,n}})=2^{n}$.

is the complement of $\mathrm{DISJ}_{n,n}$. We can obtain the same bound for ,
as follows:

######  Corollary 2.2.

$rk(M)=2^{n}$.

We also use well-known facts on the rank. Let $A$ and $B$ be two matrices of
same dimensions. We denote by $A+B$ the summation of $A$ and $B$, and by
$A\circ B$ the Hadamard product of $A$ and $B$.

######  Fact 15.

For two matrices $A$ and $B$ of same dimensions, we have

(i)

$rk(A+B)\leq rk(A)+rk(B)$;

(ii)

$rk(A\circ B)\leq rk(A)\cdot rk(B)$.

##  3 Lower Bound for Threshold Circuits

In this section, we give the inequality relating the rank of the communication
matrix to the size, depth, energy and weight.

######  Theorem 3.1 (Theorem 1 restated).

Let $s,d,e$ and $w$ be integers satisfying $2\leq s,d$, $11\leq e$, $1\leq w$.
Suppose a threshold circuit $C$ computes a Boolean function of $2n$ variables,
and has size $s$, depth $d$, energy $e$, and weight $w$. Then it holds that

$\log(rk(M_{C}))\leq ed(\log s+\log w+\log n).$

We prove the the theorem by showing that $M_{C}$ is a sum of matrices each of
which corresponds to an internal representation that arises in $C$. Since $C$
has bounded energy, the number of internal representations is also bounded. We
then show by the inclusion-exclusion principle that each matrix corresponding
an internal representation has bounded rank. Thus, Fact 1 implies the theorem.

######  Proof 3.2.

Let $C$ be a threshold circuit that computes a Boolean function of $2n$
variables, and has size $s$, depth $d$, energy $e$ and weight $w$. Let $G$ be
a set of the gates in $C$. For $l\in[d]$, let $G_{l}$ be a set of the gates in
$l$-th level of $C$. Without loss of generality, we assume that
$G_{d}=\\{g^{\mathrm{clf}}\\}$. We evaluate the rank of $M_{C}$, and prove
that

$\displaystyle rk(M_{C})\leq\left(\frac{c\cdot
s}{e-1}\right)^{e-1}\\!\cdot\left(\left(\frac{c\cdot
s}{e-1}\right)^{e-1}\\!\cdot(2nw+1)^{e-1}\right)^{d-1}\\!\cdot(2nw+1)$ (4)

where $c<3$. Equation (4) implies that

$\displaystyle rk(M_{C})$ $\displaystyle\leq$ $\displaystyle\left(\frac{c\cdot
s}{e-1}\cdot(2nw+1)\right)^{(e-1)d}$ $\displaystyle\leq$
$\displaystyle\left(snw\right)^{ed},$

where the last inequality holds if $e\geq 11$. Taking the logarithm of the
inequality, we obtain the theorem.

Below we verify that Eq. (4) holds. Let
${\mathbf{P}}=(P_{1},P_{2},\dots,P_{d})$, where $P_{l}$ is defined as a subset
of $G_{l}$ for each $l\in[d]$. Given an input
$({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$, we say that an _internal
representation ${\mathbf{P}}$ arises for $({\mathbf{a}},{\mathbf{b}})$_ if,
for every $l\in[d]$, $g({\mathbf{a}},{\mathbf{b}})=1$ for every $g\in P_{l}$,
and $g({\mathbf{a}},{\mathbf{b}})=0$ for every $g\not\in P_{l}$. We denote by
${\mathbf{P}}^{*}({\mathbf{a}},{\mathbf{b}})$ the internal representation that
arises for $({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$. We then define
$\mathcal{P}_{1}$ as a set of internal representations that arise for
$({\mathbf{a}},{\mathbf{b}})$ such that
$g^{\mathrm{clf}}({\mathbf{a}},{\mathbf{b}})=1$:

$\mathcal{P}_{1}=\\{{\mathbf{P}}^{*}({\mathbf{a}},{\mathbf{b}})\mid
g^{\mathrm{clf}}({\mathbf{a}},{\mathbf{b}})=1\\}.$

Note that, for any
${\mathbf{P}}=(P_{1},P_{2},\dots,P_{d})\in\mathcal{P}_{1}(C)$,

$|P_{1}|+|P_{2}|+\cdots+|P_{d-1}|\leq e-1$

and $|P_{d}|=1$. Thus we have

$\displaystyle|\mathcal{P}_{1}|\leq\sum_{k=0}^{e-1}{s\choose
k}\leq\left(\frac{c\cdot s}{e-1}\right)^{e-1}.$ (5)

For each ${\mathbf{P}}\in\mathcal{P}_{1}$, let $M_{{\mathbf{P}}}$ be a
$2^{n}\times 2^{n}$ matrix such that, for every
$({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$,

$M_{{\mathbf{P}}}({\mathbf{a}},{\mathbf{b}})=\left\\{\begin{array}[]{ll}1&\mbox{
if }{\mathbf{P}}={\mathbf{P}}^{*}({\mathbf{a}},{\mathbf{b}});\\\ 0&\mbox{ if
}{\mathbf{P}}\neq{\mathbf{P}}^{*}({\mathbf{a}},{\mathbf{b}}).\end{array}\right.$

By the definitions of $\mathcal{P}_{1}$ and $M_{{\mathbf{P}}}$, we have

$M_{C}=\sum_{{\mathbf{P}}\in\mathcal{P}_{1}}M_{{\mathbf{P}}},$

and hence Fact 1(i) implies that

$rk(M_{C})\leq\sum_{{\mathbf{P}}\in\mathcal{P}_{1}}rk(M_{{\mathbf{P}}}).$

Thus Eq. (5) implies that

$rk(M_{{\mathbf{P}}})\leq\left(\frac{c\cdot
s}{e-1}\right)^{e-1}\cdot\max_{{\mathbf{P}}\in\mathcal{P}_{1}}rk(M_{{\mathbf{P}}}).$

We complete the proof by showing that, for any
${\mathbf{P}}\in\mathcal{P}_{1}(C)$, it holds that

$rk(M_{{\mathbf{P}}})\leq\left(\left(\frac{2c\cdot
s}{e-1}\right)^{e-1}\cdot(2nw+1)^{e-1}\right)^{d-1}\cdot(2nw+1).$

In the following argument, we consider an arbitrary fixed internal
representation ${\mathbf{P}}=(P_{1},P_{2},\dots,P_{d})$ in $\mathcal{P}_{1}$.
We call a gate a _threshold function_ if the inputs of the gate consists of
only ${\mathbf{x}}$ and ${\mathbf{y}}$. For each $g\in G$, we denote by
$\tau[g,{\mathbf{P}}]$ a threshold function defined as

$\tau[g,{\mathbf{P}}]({\mathbf{x}},{\mathbf{y}})=\mathrm{sign}\left(p^{x}_{g}({\mathbf{x}})+p^{y}_{g}({\mathbf{y}})+t_{g}[{\mathbf{P}}]\right).$

where $t_{g}[{\mathbf{P}}]$ is a threshold of $g$, being assumed that the
internal representation ${\mathbf{P}}$ arises:

$t_{g}[{\mathbf{P}}]=\sum_{l=1}^{{\mathrm{lev}(g)}-1}\sum_{h\in
P_{l}}w_{h,g}-t_{g}.$

For each $l\in[d]$, we define a set $T_{l}$ of threshold functions as

$T_{l}=\\{\tau[g,{\mathbf{P}}]\mid g\in G_{l}\\}.$

Since every gate in $G_{1}$ is a threshold function, $T_{1}$ is identical to
$G_{1}$.

For any set $T$ of threshold functions, we denote by $M[T]$ a $2^{n}\times
2^{n}$ matrix such that, for every
$({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$,

$M[T]({\mathbf{a}},{\mathbf{b}})=\left\\{\begin{array}[]{ll}1&\mbox{ if
}\forall\tau\in T,\tau({\mathbf{a}},{\mathbf{b}})=1;\\\ 0&\mbox{ if
}\exists\tau\in T,\tau({\mathbf{a}},{\mathbf{b}})=0.\end{array}\right.$

It is well-known that the rank of $M[T]$ is bounded [9, 10], as follows.

######  Claim 16.

$rk(M[T])\leq(2nw+1)^{|T|}$.

We give a proof of the claim in Appendix for completeness.

For each $l\in[d]$, based on $P_{l}$ in ${\mathbf{P}}$, we define a set
$Q_{l}$ of threshold functions as

$Q_{l}=\\{\tau[g,{\mathbf{P}}]\mid g\in P_{l}\\}\subseteq T_{l}$

and a family $\mathcal{P}(Q_{l})$ of sets $T$ of threshold functions as

$\mathcal{T}(Q_{l})=\\{T\subseteq T_{l}\mid Q_{l}\subseteq T\mbox{ and
}|T|\leq e-1\\}.$

Following the inclusion-exclusion principle, we define a $2^{n}\times 2^{n}$
matrix

$H[Q_{l}]=\sum_{T\in\mathcal{T}(Q_{l})}(-1)^{|T|-|Q_{l}|}M[T].$

We can show that $M_{{\mathbf{P}}}$ is expressed as the Hadamard product of
$H[Q_{1}],H[Q_{2}],\dots,H[Q_{d}]$:

######  Claim 17.

$M_{{\mathbf{P}}}=H[Q_{1}]\circ H[Q_{2}]\circ\dots\circ H[Q_{d}].$

The proof of the claim is given in Appendix.

We finally evaluate $rk(M_{{\mathbf{P}}})$. Claim 17 and Fact 1(ii) imply that

$rk(M_{\mathbf{P}})=rk\left(H[Q_{1}]\circ H[Q_{2}]\circ\dots\circ
H[Q_{d}]\right)\leq\prod_{l=1}^{d}rk(H[Q_{l}]).$ (6)

Since

$|\mathcal{T}(Q_{l})|\leq\left(\frac{c\cdot s}{e-1}\right)^{e-1}$

Fact 1(i) and Claim 16 imply that

$\displaystyle rk(H[Q_{l}])$ $\displaystyle\leq$
$\displaystyle\sum_{T\in\mathcal{P}(Q_{l})}rk(M[T])$ (7) $\displaystyle\leq$
$\displaystyle\left(\frac{c\cdot s}{e-1}\right)^{e-1}\cdot(2nw+1)^{e-1}$

for every $l\in[d-1]$, and

$\displaystyle rk(H[Q_{d}])\leq 2nw+1.$ (8)

Equations (6)-(8) imply that

$rk(M_{\mathbf{P}})\leq\left(\left(\frac{c\cdot
s}{e-1}\right)^{e-1}\cdot(2nw+1)^{e-1}\right)^{d-1}\cdot(2nw+1)$

as desired. We thus have verified Eq. (4).

Combining Theorem 2.2 and Corollary 3.1, we obtain the following corollary:

######  Corollary 3.3.

Let $s,d,e$ and $w$ be integers satisfying $2\leq s,d$, $10\leq e$, $1\leq w$.
Suppose a threshold circuit $C$ of size $s$, depth $d$, energy $e$, and weight
$w$ computes . Then it holds that

$n\leq ed(\log s+\log w+\log n).$

Equivalently, we have $2^{n/(ed)}/(nw)\leq s$.

Theorem 3.1 implies lower bounds for other Boolean functions with linear rank.
For example, consider another Boolean function $\mathrm{EQ}_{n}$ asking if
${\mathbf{x}}={\mathbf{y}}$:

$\mathrm{EQ}_{n}({\mathbf{x}},{\mathbf{y}})=\bigwedge_{i=1}^{n}\overline{x_{i}\oplus
y_{i}}$

Since $M_{\mathrm{EQ}_{n}}$ is the identity matrix with full rank, we have the
same lower bound.

######  Corollary 3.4.

Let $s,d,e$ and $w$ be integers satisfying $2\leq s,d$, $10\leq e$, $1\leq w$.
Suppose a threshold circuit $C$ of size $s$, depth $d$, energy $e$, and weight
$w$ computes $\mathrm{EQ}_{n}$. Then it holds that

$n\leq ed(\log s+\log w+\log n).$

Equivalently, we have $2^{n/(ed)}/(nw)\leq s$.

##  4 Tightness of the Lower Bound

In this section, we show that the lower bound given in Theorem 3.1 is almost
tight if the depth and energy are small.

###  4.1 Definitions

Let $z$ be a positive integer, and $f$ be a Boolean function of $2n$
variables. We say that $f$ is $z$-piecewise with $f_{1},f_{2},\dots,f_{z}$ if
the following conditions are satisfied: Let

$B_{j}=\\{i\in[n]\mid\mbox{$x_{i}$ or $y_{i}$ are fed into $f_{j}$}\\},$

then

(i)

$B_{1},B_{2},\dots,B_{z}$ compose a partition of $[n]$;

(ii)

$|B_{j}|\leq\lceil n/z\rceil$ for every $j\in[z]$;

(iii)

$f({\mathbf{x}},{\mathbf{y}})=\bigvee_{j=1}^{z}f_{j}({\mathbf{x}},{\mathbf{y}})\quad\mbox{or}\quad
f({\mathbf{x}},{\mathbf{y}})=\overline{\bigvee_{j=1}^{z}f_{j}({\mathbf{x}},{\mathbf{y}})}.$

We say that a set of threshold gates sharing input variables is a neural set,
and a neural set is selective if at most one of the gates in the set outputs
one for any input assignment. A selective neural set $S$ computes a Boolean
function $f$ if for every assignment in $f^{-1}(0)$, no gates in $S$ outputs
one, while for every assignment in $f^{-1}(1)$, exactly one gate in $S$
outputs one. We define the size and weight of $S$ as $|S|$ and $\max_{g\in
S}w_{g}$, respectively.

By a DNF-like construction, we can obtain a selective neural set of
exponential size that computes $f$ for any Boolean function $f$.

######  Theorem 4.1.

For any Boolean function $f$ of $n$ variables, there exists a selective neural
set of size $2^{n}$ and weight one that computes $f$.

###  4.2 Upper Bounds

The following proposition shows that we can a construct threshold circuits of
small energy for piecewise functions.

######  Lemma 4.2.

Let $e$ and $d$ be integers satisfying $2\leq e$ and $2\leq d$, and
$z=(e-1)(d-1)$. Suppose $f:\\{0,1\\}^{2n}\to\\{0,1\\}$ is a $z$-piecewise
function with $f_{1},f_{2},\dots,f_{z}$. If $f_{j}$ is computable by a
selective neural set of size at most $s^{\prime}$ and weight $w^{\prime}$ for
every $j\in[z]$, $f$ is computable by a threshold circuit of size

$s\leq z\cdot s^{\prime}+1,$

depth $d$, energy $e$ and weight

$w\leq\frac{2n}{z}\cdot w^{\prime}.$

Clearly, is $z$-piecewise, and so the lemma gives our upper bound for .

######  Theorem 4.3 (Theorem 1.2 restated).

For any integers $e$ and $d$ such that $2\leq e$ and $2\leq d$, is computable
by a threshold circuit of size

$s\leq(e-1)(d-1)\cdot 2^{\frac{n}{(e-1)(d-1)}}.$

depth $d$, energy $e$ and weight

$w\leq\left(\frac{n}{(e-1)(d-1)}\right)^{2}.$

We can also obtain a similar proposition for $\mathrm{EQ}_{n}$.

######  Theorem 4.4.

For any integers $e$ and $d$ such that $2\leq e$ and $2\leq d$,
$\mathrm{EQ}_{n}$ is computable by a threshold circuit of size

$s\leq(e-1)(d-1)\cdot 2^{\frac{2n}{(e-1)(d-1)}}.$

depth $d$, energy $e$ and weight

$w\leq\frac{n}{(e-1)(d-1)}.$

##  5 Simulating Discretized Circuits

In this section, we show that any discretized circuit can be simulated using a
threshold circuit with a moderate increase in size, depth, energy, and weight.
Thus, a similar inequality holds for discretized circuits. Recall that we
define energy of discretized circuits differently from those of threshold
circuits.

######  Theorem 5.1 (Theorem 1.3 restated).

Let $\delta$ be a discretizer and $\varphi$ be an activation function such
that $\delta\circ\varphi$ has a silent range. If a
$(\delta\circ\varphi)$-circuit $C$ of size $s$, depth $d$, energy $e$, and
weight $w$ computes a Boolean function $f$, then it holds that

$\log(rk(M_{C}))=O(ed(\log s+\log w+\log n)^{3}).$

Our simulation is based on a binary search of the potentials of a discretized
gate, we employ a conversion technique from a linear decision tree to a
threshold circuit presented in [44].

##  6 Conclusions

In this paper, we consider threshold circuits and other theoretical models of
neural networks in terms of four complexity measures, size, depth energy and
weight. We prove that if the communication matrix of a Boolean function $f$
has linear rank, any threshold circuit of sub-linear depth, sub-linear energy
and sub-exponential weight needs exponential size to compute $f$.

We believe that circuit complexity arguments provide insights into neural
computation. Besides the famous Marr’s three-level approach towards
understanding the brain computation (computational level, algorithmic level,
and implementation level) [25], Valiant [48] added an additional requirement
that it has to incorporate some understanding of the quantitative constraints
that are faced by cortex. We expect that circuit complexity arguments could
shed light on a quantitative constraint through a complexity measure. Maass
_et al_. [23] pointed out a difficulty to uncover a neural algorithm employed
by the brain, because its hardware could be extremely adopted to the task, and
consequently the algorithm vanishes: even if we know to the last detail its
precise structure, connectivity, and vast array of numerical parameters (an
artificial neural network given by deep learning is the case), it is still
hard to extract an algorithm implemented in the network. A lower bound does
not provide a description of an explicit neural algorithm, but could give a
hint for computational natures behind neural computation, because a lower
bound argument necessarily deals with _every_ algorithm which a theoretical
model of a neural network is able to implement. We expect that developing
lower bound proof techniques for a theoretical model of neural networks can
push this line of research.

## References

  * [1] Kazuyuki Amano.  On the size of depth-two threshold circuits for the Inner Product mod 2 function.  In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications, pages 235–247, Cham, 2020. Springer International Publishing.
  * [2] Kazuyuki Amano and Akira Maruoka.  On the complexity of depth-2 circuits with threshold gates.  In Proc. of the 30th international conference on Mathematical Foundations of Computer Science, pages 107–118, 2005.
  * [3] Boris Barbour, Nicolas Brunel, Vincent Hakim, and Jean-Pierre Nadal.  What can we learn from synaptic weight distributions?  Trends in Neurosciences, 30(12):622–629, 2007.  URL: https://www.sciencedirect.com/science/article/pii/S0166223607002615, doi:https://doi.org/10.1016/j.tins.2007.09.005.
  * [4] Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan.  Average-case lower bounds and satisfiability algorithms for small threshold circuits.  Theory of Computing, 14(9):1–55, 2018.
  * [5] Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David.  Binaryconnect: Training deep neural networks with binary weights during propagations.  In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2, NIPS’15, pages 3123–3131, Cambridge, MA, USA, 2015. MIT Press.
  * [6] James J. DiCarlo and David D. Cox.  Untangling invariant object recognition.  Trends in Cognitive Sciences, 11(8):333–341, 2007.  doi:10.1016/j.tics.2007.06.010.
  * [7] Krishnamoorthy Dinesh, Samir Otiv, and Jayalal Sarma.  New bounds for energy complexity of boolean functions.  Theoretical Computer Science, 845:59–75, 2020.
  * [8] Peter Földiák.  Sparse coding in the primate cortex.  In M. A. Arbib, editor, The Handbook of Brain Theory and Neural Networks, pages 1064–1068. MIT Press, 2003.
  * [9] Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon.  Relations between communication complexity, linear arrangements, and computational complexity.  In Proc. of the 21st International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 171–182, 2001.
  * [10] András Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, and György Turán.  Threshold circuits of bounded depth.  Journal of Computer and System Sciences, 46:129–154, 1993.
  * [11] Johan Håstad and Mikael Goldmann.  On the power of small-depth threshold circuits.  Computational Complexity, 1(2):113–129, 1991.
  * [12] Yunlong He, Koray Kavukcuoglu, Yun Wang, Arthur Szlam, and Yanjun Qi.  Unsupervised feature learning by deep sparse coding.  In Proc. of SIAM International Conference on Data Mining, pages 902–910, 2014.
  * [13] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Quantized neural networks: Training neural networks with low precision weights and activations.  Journal of Machine Learning Research, 18(187):1–30, 2018.  URL: http://jmlr.org/papers/v18/16-456.html.
  * [14] Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks.  Size-depth tradeoffs for threshold circuits.  SIAM Journal on Computing, 26(3):693–707, 1997.
  * [15] Stasys Jukna.  Extremal Combinatorics with Applications in Computer Science.  Springer-Verlag Berlin Heidelberg, 2011.
  * [16] D. M. Kane and R. Williams.  Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits.  In Proc. of the 48th Annual ACM Symposium on Theory of Computing, pages 633–643, 2016.
  * [17] O. M. Kasim-zade.  On a measure of active circuits of functional elements (russian).  Mathematical problems in cybernetics “Nauka”, (4):218?–228, 1992.
  * [18] Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Y. Ng.  Efficient sparse coding algorithms.  In Proc. of the 19th Advances in Neural Information Processing Systems, pages 801–808, 2006.
  * [19] Peter Lennie.  The cost of cortical computation.  Current Biology, 13:493–497, 2003.
  * [20] Nancy Lynch and Cameron Musco.  A Basic Compositional Model for Spiking Neural Networks, pages 403–449.  Springer Nature Switzerland, 2022.  doi:10.1007/978-3-031-15629-8_22.
  * [21] Wolffanf Maass, Georg. Schnitger, and Eduardo D. Sontag.  On the computational power of sigmoid versus boolean threshold circuits.  In Proc. of 32nd Annual Symposium of Foundations of Computer Science, pages 767–776, 1991.  doi:10.1109/SFCS.1991.185447.
  * [22] Wolfgang Maass.  Networks of spiking neurons: The third generation of neural network models.  Neural Networks, 10(9):1659–1671, 1997.
  * [23] Wolfgang Maass, Christos H. Papadimitriou, Santosh Vempala, and Robert Legenstein.  Brain Computation: A Computer Science Perspective, pages 184–199.  Springer International Publishing, 2019.  doi:10.1007/978-3-319-91908-9_11.
  * [24] Hiroki Maniwa, Takayuki Oki, Akira Suzuki, Kei, and Xiao Zhou.  Computational power of threshold circuits of energy at most two.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101.A(9):1431–1439, 2018.
  * [25] David Marr.  Vision: A Computational Investigation into the Human Representation and Processing of Visual Information.  W.H.Freeman & Co Ltd, 1982.
  * [26] Warren S. McCulloch and Walter Pitts.  A logical calculus of the ideas immanent in nervous activity.  The bulletin of mathematical biophysics, 5:115–133, 1943.
  * [27] Marvin Minsky and Seymour Papert.  Perceptrons: An Introduction to Computational Geometry.  MIT Press, 1988.
  * [28] Andrew Ng.  Sparse autoencoder.  CS294A Lecture notes, 2011.
  * [29] Noam Nisan.  The communication complexity of threshold gates.  Proceeding of “Combinatorics, Paul Erd$\ddot{o}$s is Eighty”, pages 301–315, 1993.
  * [30] Bruno A Olshausen and David J Field.  Sparse coding of sensory inputs.  Current Opinion in Neurobiology, 14(4):481–487, 2004.
  * [31] Ian Parberry.  Circuit Complexity and Neural Networks.  MIT Press, 1994.
  * [32] Thomas Pfeil, Tobias Potjans, Sven Schrader, Wiebke Potjans, Johannes Schemmel, Markus Diesmann, and Karlheinz Meier.  Is a 4-bit synaptic weight resolution enough? - constraints on enabling spike-timing dependent plasticity in neuromorphic hardware.  Frontiers in Neuroscience, 6:90, 2012.  URL: https://www.frontiersin.org/article/10.3389/fnins.2012.00090, doi:10.3389/fnins.2012.00090.
  * [33] Alexander A. Razborov and Alexander A. Sherstov.  The sign-rank of AC0.  SIAM Journal on Computing, 39(5):1833–1855, 2010.
  * [34] Frank Rosenblatt.  The perceptron: A probabilistic model for information storage and organization in the brain.  Psychological Review, 65(6):386–408, 1958.
  * [35] Janio Carlos Nascimento Silva and Uéverton S. Souza.  Computing the best-case energy complexity of satisfying assignments in monotone circuits.  Theoretical Computer Science, 932:41–55, 2022.  URL: https://www.sciencedirect.com/science/article/pii/S0304397522004777, doi:https://doi.org/10.1016/j.tcs.2022.08.005.
  * [36] K. Y. Siu and J. Bruck.  On the power of threshold circuits with small weights.  SIAM Journal on Discrete Mathematics, 4(3):423–435, 1991.
  * [37] Kai-Yeung. Siu, Vwani Roychowdhury, and Thomas Kailath.  Discrete Neural Computation: A Theoretical Foundation.  Prentice Hall, 1995.
  * [38] Kai-Yeung Siu and Vwani P. Roychowdhury.  On optimal depth threshold circuits for multiplication and related problems.  SIAM Journal on Discrete Mathematics, 7(2):284–292, 1994.
  * [39] Xiaoming Sun, Yuan Sun, Kewen Wu, and Zhiyu Xia.  On the relationship between energy complexity and other boolean function measures.  In Proc. of the 25th International Computing and Combinatorics Conference, pages 516–528, 2019.
  * [40] Akira Suzuki, Kei Uchizawa, and Xiao Zhou.  Energy-efficient threshold circuits computing MOD functions.  In Proc. of the 17th Computing: the Australasian Theory Symposium, pages 105–110, 2011.
  * [41] Akira Suzuki, Kei Uchizawa, and Xiao Zhou.  Energy-efficient threshold circuits computing MOD functions.  International Journal of Foundations of Computer Science, 24(1):15–29, 2013.
  * [42] Kei Uchizawa.  Lower bounds for threshold circuits of bounded energy.  Interdisciplinary Information Sciences, 20(1):27–50, 2014.
  * [43] Kei Uchizawa.  Size, Depth and Energy of Threshold Circuits Computing Parity Function.  In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation (ISAAC 2020), volume 181 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2020/13398, doi:10.4230/LIPIcs.ISAAC.2020.54.
  * [44] Kei Uchizawa, Rodney Douglas, and Wolfgang Maass.  On the computational power of threshold circuits with sparse activity.  Neural Computation, 18(12):2994–3008, 2008.
  * [45] Kei Uchizawa and Eiji Takimoto.  Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity.  Theoretical Computer Science, 407(1–3):474–487, 2008.
  * [46] Kei Uchizawa, Eiji Takimoto, and Takao Nishizeki.  Size-energy tradeoffs of unate circuits computing symmetric Boolean functions.  Theoretical Computer Science, 412:773–782, 2011.
  * [47] M. N. Vaintsvaig.  On the power of networks of functional elements (Russian).  Doklady Akademii Nauk, 139(2):320?323, 1961.
  * [48] Leslie G Valiant.  What must a global theory of cortex explain?  Current Opinion in Neurobiology, 25:15–19, 2014.  doi:https://doi.org/10.1016/j.conb.2013.10.006.

##  7 Appendix

###  7.1 Proof of Claim 16

Let $z=|T|$, and $\tau_{1},\tau_{2},\dots,\tau_{z}$ be an arbitrary order of
threshold functions in $T$. For each $k\in[z]$, we define

$R_{k}=\\{p^{x}_{\tau_{k}}({\mathbf{a}})\mid{\mathbf{a}}\in\\{0,1\\}^{n}\\}.$

Since a threshold function receives a value between $-w$ and $w$ from a single
input, we have $|R_{k}|\leq 2nw+1$. For
${\mathbf{r}}=(r_{1},r_{2},\dots,r_{z})\in R_{1}\times R_{2}\times\dots\times
R_{z}$, we define $R({\mathbf{r}})=X({\mathbf{r}})\times Y({\mathbf{r}})$ as a
combinatorial rectangle where

$X({\mathbf{r}})=\\{{\mathbf{x}}\mid\forall
k\in[z],p_{\tau_{k}}({\mathbf{x}})=r_{k}\\}$

and

$Y({\mathbf{r}})=\\{{\mathbf{y}}\mid\forall k\in[z],t_{\tau_{k}}\leq
r_{k}+p^{y}_{\tau_{k}}({\mathbf{y}})\\}.$

Clearly, all the rectangles are disjoint, and hence $M[T]$ can be expressed as
a sum of rank-1 matrices given by $R({\mathbf{r}})$’s taken over all the
${\mathbf{r}}$’s. Thus Fact 1(i) implies that its rank is at most
$|R_{1}\times R_{2}\times\dots\times R_{z}|\leq(2nw+1)^{z}$.

###  7.2 Proof of Claim 17

Consider an arbitrary fixed assignment
$({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$. We show that

$H[Q_{1}]({\mathbf{a}},{\mathbf{b}})\circ
H[Q_{2}]({\mathbf{a}},{\mathbf{b}})\circ\dots\circ
H[Q_{d}]({\mathbf{a}},{\mathbf{b}})=0,$

if $M_{{\mathbf{P}}}({\mathbf{a}},{\mathbf{b}})=0$, and

$H[Q_{1}]({\mathbf{a}},{\mathbf{b}})\circ
H[Q_{2}]({\mathbf{a}},{\mathbf{b}})\circ\dots\circ
H[Q_{d}]({\mathbf{a}},{\mathbf{b}})=1,$

if $M_{{\mathbf{P}}}({\mathbf{a}},{\mathbf{b}})=1$. We write
${\mathbf{P}}^{*}=(P^{*}_{1},P^{*}_{2},\dots,P_{d}^{*})$ to denote
${\mathbf{P}}^{*}({\mathbf{a}},{\mathbf{b}})$ for a simpler notation.

Suppose $M_{{\mathbf{P}}}({\mathbf{a}},{\mathbf{b}})=0$. In this case, we have
${\mathbf{P}}\neq{\mathbf{P}}^{*}$, and hence there exists a level $l\in[d]$
such that $P_{l}\neq P^{*}_{l}$ while $P_{l^{\prime}}=P^{*}_{l^{\prime}}$ for
every $l^{\prime}\in[l-1]$. For such $l$, it holds that

$\displaystyle\tau[g,{\mathbf{P}}^{*}]({\mathbf{a}},{\mathbf{b}})=\tau[g,{\mathbf{P}}]({\mathbf{a}},{\mathbf{b}})$
(9)

for every $g\in G_{l}$. We show that $H[Q_{l}]({\mathbf{a}},{\mathbf{b}})=0$
by considering two cases: $P_{l}\backslash P^{*}_{l}\neq\emptyset$ and
$P_{l}\subset P_{l}^{*}$.

Consider the case where $P_{l}\backslash P^{*}_{l}\neq\emptyset$, then there
exists $g\in P_{l}\backslash P^{*}_{l}$. Since $g\not\in P^{*}_{l}$, we have
$\tau[g,{\mathbf{P}}^{*}]({\mathbf{a}},{\mathbf{b}})=0$. Thus, Eq. (9) implies
that $\tau[g,{\mathbf{P}}]({\mathbf{a}},{\mathbf{b}})=0$, and hence
$M[T]({\mathbf{a}},{\mathbf{b}})=0$ for every $T$ such that $Q_{l}\subseteq
T$. Therefore, for every $T\in\mathcal{T}(Q_{l})$, we have
$M[T]({\mathbf{a}},{\mathbf{b}})=0$, and hence

$H[Q_{l}]({\mathbf{a}},{\mathbf{b}})=\sum_{T\in\mathcal{T}(Q_{l})}M[T]({\mathbf{a}},{\mathbf{b}})=0.$

Consider the other case where $P_{l}\subset P_{l}^{*}$. Let
$Q^{*}_{l}=\\{\tau[g,{\mathbf{P}}^{*}]\mid g\in P^{*}_{l}\\}$. Equation (9)
implies that $M[T]({\mathbf{a}},{\mathbf{b}})=1$ if $T$ satisfies
$Q_{l}\subseteq T\subseteq Q^{*}_{l}$, and
$M[T]({\mathbf{a}},{\mathbf{b}})=0$, otherwise. Thus,

$\displaystyle H[Q_{l}]({\mathbf{a}},{\mathbf{b}})$ $\displaystyle=$
$\displaystyle\sum_{T\in\mathcal{T}(Q_{l})}(-1)^{|T|-|Q_{l}|}M[T]$
$\displaystyle=$ $\displaystyle\sum_{Q_{l}\subseteq T\subseteq
Q^{*}_{l}}(-1)^{|T|-|Q_{l}|}$

Therefore, by the binomial theorem,

$\displaystyle H[Q_{l}]({\mathbf{a}},{\mathbf{b}})$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{|Q^{*}_{l}|-|Q_{l}|}{|Q^{*}_{l}|-|Q_{l}|\choose
k}(-1)^{k}$ $\displaystyle=$ $\displaystyle(1-1)^{|Q^{*}_{l}|-|Q_{l}|}$
$\displaystyle=$ $\displaystyle 0.$

Suppose $M_{{\mathbf{P}}}({\mathbf{a}},{\mathbf{b}})=1$. In this case, we have
${\mathbf{P}}={\mathbf{P}}^{*}$. Thus, for every $l\in[d]$, Eq. (9) implies
that $M[T]({\mathbf{a}},{\mathbf{b}})=1$ if $T=Q_{l}$, and
$M[T]({\mathbf{a}},{\mathbf{b}})=0$, otherwise. Therefore,

$\displaystyle H[Q_{l}]({\mathbf{a}},{\mathbf{b}})$ $\displaystyle=$
$\displaystyle\sum_{T\in\mathcal{T}(Q_{l})}(-1)^{|T|-|Q_{l}|}M[T]({\mathbf{a}},{\mathbf{b}})$
(10) $\displaystyle=$ $\displaystyle(-1)^{|Q_{l}|-|Q_{l}|}$ (11)
$\displaystyle=$ $\displaystyle 1.$ (12)

Consequently

$H[Q_{1}]({\mathbf{a}},{\mathbf{b}})\circ
H[Q_{2}]({\mathbf{a}},{\mathbf{b}})\circ\dots\circ
H[Q_{d}]({\mathbf{a}},{\mathbf{b}})=1,$

as desired.

###  7.3 Proof of Lemma 4.2

Let $z=(e-1)(d-1)$. For simplicity, we assume that $n$ is divisible by $z$.
Let $f:\\{0,1\\}^{2n}\to\\{0,1\\}$ be $z$-piecewise with
$f_{1},f_{2},\dots,f_{z}$. We first prove the proposition for the case where
$f$ satisfies

$f({\mathbf{x}},{\mathbf{y}})=\bigvee_{j=1}^{z}f_{j}({\mathbf{x}},{\mathbf{y}}).$

Let us relabel $f_{l}$ for $l\in[z]$ as $f_{k,l}$ for $k\in[e-1]$, and
$l\in[d-1]$. We then denote by $B_{k,l}=\\{i\in[n]\mid\mbox{$x_{i}$ or $y_{i}$
is fed into $f_{k,l}$}\\}$ for $k\in[e-1]$, and $l\in[d-1]$, each of which
contains $n/z$ integers. Thus, we have

$f({\mathbf{x}},{\mathbf{y}})=\bigvee_{k\in[e-1]}\bigvee_{l\in[d-1]}f_{k,l}({\mathbf{x}},{\mathbf{y}}).$

By the assumption, $f_{k,l}$ is computable by a selective neural set $S_{k,l}$
for every pair of $k\in[e-1]$ and $l\in[d-1]$.

We construct the desired threshold circuit $C$ by arranging and connecting the
selective neural sets, where $C$ has a simple layered structure consisting of
the selective neural sets. After we complete the construction of $C$, we show
that $C$ computes $f$, and evaluate its size, depth, energy, and weight.

We start from the bottom level. First, we put in the first level the gates in
$S_{k,1}$ for every $k\in[e-1]$. Then, for each $l$, $2\leq l\leq d-1$, we add
at the $l$th level the gates $g\in S_{k,l}$ for every $k\in[e-1]$, and connect
the outputs of all the gates at the lower level to every $g\in S_{k,l}$ with
weight $-2nw^{\prime}/z$. For $g\in S_{k,l}$ and
$({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$, we denote by
$g^{C}({\mathbf{a}},{\mathbf{b}})$ the output of the gate $g$ placed in $C$.
Finally, we add $g^{\mathrm{clf}}$ that computes a conjunction of all gates in
the layers $1,2\dots,d-1$:

$g^{\mathrm{clf}}({\mathbf{x}},{\mathbf{y}})=\mathrm{sign}\left(\sum_{k\in[e-1]}\sum_{l\in[d-1]}\sum_{g\in
S_{k,l}}g^{C}({\mathbf{x}},{\mathbf{y}})-1\right).$

We here show that $C$ computes $f$. By construction, the following claim is
easy to verify:

######  Claim 22.

For any $g\in S_{k,l}$,

$g^{C}({\mathbf{x}},{\mathbf{y}})=\left\\{\begin{array}[]{ll}g({\mathbf{x}},{\mathbf{y}})&\mbox{if
every gate at the levels $1,\dots,l-1$ outputs zero};\\\
0&\mbox{otherwise}.\end{array}\right.$

######  Proof 7.1.

If every gate at the levels $1,\dots,l-1$ outputs zero, the output of $g^{C}$
is identical to the counterpart of $g$, and hence
$g^{C}({\mathbf{x}},{\mathbf{y}})=g({\mathbf{x}},{\mathbf{y}})$. Otherwise,
there is a gate outputting one at the lower levels. Since $g^{C}$ receives an
output from the gate at the lower level, the value $-2w^{\prime}n/z$ is
subtracted from the potential of $g^{C}$. Since $g$ receives at most $2n/z$
positive weights bounded by $w^{\prime}$, the potential of $g^{C}$ is now
below its threshold. Otherwise, $g$ outputs one for any input assignment,
which implies that, since $S_{k,l}$ is selective, $f_{k,l}$ is the constant
function. This contradicts the fact that $f$ is $z$-piecewise.

Suppose $f({\mathbf{a}},{\mathbf{b}})=0$. In this case, for every $k\in[e-1]$,
$l\in[d-1]$, and $g\subseteq S_{k,l}$, $g{k,l}({\mathbf{a}},{\mathbf{b}})=0$.
Therefore, Claim 22 implies that no gate in $C$ outputs one.

Suppose $f({\mathbf{a}},{\mathbf{b}})=1$. In this case, there exists
$l^{*}\in[d-1]$ such that $f_{k,l^{*}}({\mathbf{a}},{\mathbf{b}})=1$ for some
$k\in[e-1]$, while $f_{k,l}({\mathbf{a}},{\mathbf{b}})=0$ for every $1\leq
k\leq e-1$ and $1\leq l\leq l^{*}-1$. Since $S_{k,l^{*}}$ compute $f_{k,l}$,
Claim 22 implies that there exists $g\in S_{k,l^{*}}$ such that
$g^{C}({\mathbf{a}},{\mathbf{b}})=1$, which implies that
$g^{\mathrm{clf}}({\mathbf{x}},{\mathbf{y}})=1$.

Finally, we evaluate the size, depth, energy, and weight of $C$. Since $C$
contains at most $s^{\prime}$ gates for each pair of $k\in[e-1]$ and
$l\in[d-1]$ where $z=(e-1)(d-1)$, we have in total $s\leq zs^{\prime}+1$. The
additional one corresponds to the output gate. Because the gates $g\in
S_{k,l}$ are placed at the $l$-th level for $l\in[d-1]$, the level of
$g^{\mathrm{clf}}$ is clearly $d$, and hence, $C$ has depth $d$. Claim 22
implies that if there is a gate outputting one at level $l$, then no gate in
higher levels outputs one. In addition, since $S_{k,l}$ is selective, at most
one gate $g\in S_{k,l}$ outputs one. Therefore, at most $e-1$ gates at the
$l$th level output one, followed by $g^{\mathrm{clf}}$ gates outputting one.
Thus, $C$ has an energy $e$. Any connection in $C$ has weight at most
$w^{\prime}$ or $2nw^{\prime}/z$. Thus, the weight of $C$ is $2nw^{\prime}/z$.

Consider the other case where

$f({\mathbf{x}},{\mathbf{y}})=\overline{\bigvee_{j=1}^{z}f_{j}({\mathbf{x}},{\mathbf{y}})}.$

We can obtain the desired circuit $C$ by the same construction as above except
that $g^{\mathrm{clf}}$ computes the complement of a conjunction of all gates
in the layers $1,2\dots,d-1$:

$g^{\mathrm{clf}}({\mathbf{x}},{\mathbf{y}})=\mathrm{sign}\left(\sum_{k\in[e-1]}\sum_{l\in[d-1]}\sum_{g\in
S_{k,l}}-g^{C}({\mathbf{x}},{\mathbf{y}})\right).$

###  7.4 Proof of Theorem 4.3

For simplicity, we consider the case where $n$ is a multiple of $z$. It
suffices to show that is $z$-piecewise, and computable by a neural set of size
$s^{\prime}=2^{n/z}$ and weight $w^{\prime}=n/z$.

We can verify that is $z$-piecewise, since

where

$f_{j}({\mathbf{x}},{\mathbf{y}})=\bigvee_{i\in B_{j}}x_{i}\wedge y_{i}.$

and $B_{j}=\\{i\in[n]\mid(j-1)\lceil n/z\rceil+1\leq i\leq jn/z\\}$.

Consider an arbitrary fixed $j\in[z]$. Below we show that $f_{j}$ is
computable by a neural set of size

$s^{\prime}\leq 2^{n/z}$

and weight $w^{\prime}\leq n/z$.

Recall that we denote by $\llbracket\mathrm{P}\rrbracket$ for a statement
$\mathrm{P}$ a function that outputs one if $\mathrm{P}$ is true, and zero
otherwise. Then $f_{j}$ can be expressed as

$\displaystyle f_{j}({\mathbf{x}},{\mathbf{y}})=\bigvee_{\emptyset\subset
B\subseteq B_{j}}F^{B}_{j}({\mathbf{x}},{\mathbf{y}})$ (13)

where

$F^{B}_{j}({\mathbf{x}},{\mathbf{y}})=\bigwedge_{i\in B}\llbracket
x_{i}=1\rrbracket\wedge\bigwedge_{i\not\in B}\llbracket
x_{i}=0\rrbracket\wedge\bigvee_{i\in B}y_{i}.$

For any assignment ${\mathbf{a}}\in\\{0,1\\}^{n}$, we define
$B^{*}({\mathbf{a}})$ as

$B^{*}({\mathbf{a}})=\\{i\in B_{j}\mid a_{i}=1\\}.$

Then, for every $({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$,

$\displaystyle
F^{B}_{j}({\mathbf{a}},{\mathbf{b}})=\left\\{\begin{array}[]{ll}1&\mbox{ if
}B=B^{*}({\mathbf{a}})\mbox{ and }\exists i\in B,b_{i}=1;\\\ 0&\mbox{
otherwise}.\end{array}\right.$ (16)

The function $F^{B}_{j}$ is computable by a threshold gate.

######  Claim 26.

For any $B\subseteq B_{j}$, $F^{B}_{j}$ can be computed by a threshold gate
$g^{B}_{j}$ with weights $w^{x}_{i}$, $w^{y}_{i}$; the threshold $t$ is
defined as follows: for every $i\in[n]$,

$w^{x}_{i}=\left\\{\begin{array}[]{ll}0&\mbox{ if }i\not\in B_{j};\\\
|B|&\mbox{ if }i\in B\subseteq B_{j};\\\ -|B|&\mbox{ if }i\in B_{j}\backslash
B,\end{array}\right.$

and

$w^{y}_{i}=\left\\{\begin{array}[]{ll}0&\mbox{ if }i\not\in B_{k,l};\\\
1&\mbox{ if }i\in B\subseteq B_{k,l};\\\ 0&\mbox{ if }i\in B_{k,l}\backslash
B,\end{array}\right.$

and $t=|B|^{2}+1$.

######  Proof 7.2.

Suppose $F^{B}_{j}({\mathbf{x}},{\mathbf{y}})=1$, that is,
$B=B^{*}({\mathbf{x}})$, and there exists $i^{*}\in B$ such that
$y_{i^{*}}=1$. Then, we have

$\sum_{i\in B_{j}}w^{x}_{i}x_{i}+\sum_{i\in
B}w^{y}_{i}y_{i}\geq|B|\cdot|B|+1=t;$

thus, $g^{B}_{j}$ outputs one.

Suppose $F^{B}_{j}({\mathbf{x}},{\mathbf{y}})=0$. There are two cases: $B\neq
B^{*}({\mathbf{x}})$ and $y_{i}=0$ for every $i\in B_{j}$

Consider the first case. If there exists $i^{*}\in
B^{*}({\mathbf{x}})\backslash B$, then

$\sum_{i\in B_{j}}w^{x}_{i}x_{i}\leq\sum_{i\in
B}w^{x}_{i}x_{i}+w^{x}_{i^{*}}\leq|B|\cdot|B|-|B|.$

Thus,

$\sum_{i\in B_{j}}w^{x}_{i}x_{i}+\sum_{i\in
B}w^{y}_{i}y_{i}\leq(|B|\cdot|B|-|B|)+|B|\leq|B|^{2}<t,$

and consequently, $g^{B}_{k,l}$ outputs zero. If $B^{*}({\mathbf{x}})\subset
B$, then

$\sum_{i\in B_{j}}w^{x}_{i}x_{i}\leq(|B|-1)\cdot|B|.$

Thus,

$\sum_{i\in B_{j}}w^{x}_{i}x_{i}+\sum_{i\in
B}w^{y}_{i}y_{i}\leq((|B|-1)\cdot|B|)+|B|\leq|B|^{2}<t,$

and hence, $g^{B}_{j}$ outputs zero.

In the second case, we have

$\sum_{i\in B}w^{y}_{i}y_{i}=0.$

Thus,

$\sum_{i\in B_{j}}w^{x}_{i}x_{i}+\sum_{i\in
B}w^{y}_{i}y_{i}\leq|B|\cdot|B|<t,$

and hence, $g^{B}_{j}$ outputs zero.

For any ${\mathbf{a}}\in\\{0,1\\}^{n}$, Eq. (16) implies that only
$g^{B^{*}({\mathbf{a}})}_{j}$ are allowed to output one. Thus, by Eq. (13), a
selective neural set

$S_{j}=\\{g^{B}_{j}\mid\emptyset\subset B\subseteq B_{j}\\}$

computes $f_{j}$. Since $|B_{j}|\leq n/z$, we have $|S_{j}|\leq 2^{n/z}$.
Claim 26 implies that $w^{\prime}\leq n/z$.

###  7.5 Proof of Theorem 4.4

Let $z=(e-1)(d-1)$. $\mathrm{EQ}_{n}$ is $z$-piecewise, since

$\mathrm{EQ}_{n}({\mathbf{x}},{\mathbf{y}})=\overline{\bigvee_{j=1}^{z}f_{j}({\mathbf{x}},{\mathbf{y}})}$

where

$f_{j}({\mathbf{x}},{\mathbf{y}})=\bigvee_{i\in B_{j}}x_{i}\oplus y_{i}$

and $B_{j}=\\{i\in[n]\mid(j-1)\lceil n/z\rceil+1\leq i\leq jn/z\\}$. Then the
theorem implies that $f_{j}$ is computable by a selective neural set of size
$s^{\prime}=2^{2n/z}$ and $w^{\prime}=1$.

###  7.6 Proof of Theorem 5.1

Let $\delta$ be a discretizer and $\varphi$ be an activation function such
that $\delta\circ\varphi$ has a silent range for $I$. In the proof, we only
consider an open interval $I=(t_{\min},t_{\max})$ because the proofs for the
other cases are similar. Let $C$ be a $(\delta\circ\varphi)$-circuit of size
$s$, depth $d$, energy $e$, and weight $w$. We obtain the desired threshold
circuit $C^{\prime}$ by showing a procedure by which any
$(\delta\circ\varphi)$-gate $g$ in $C$ can be safely replaced by a set of
threshold gates.

Let $g$ be an arbitrary $(\delta\circ\varphi)$-gate in $C$ that computes
$g({\mathbf{x}},{\mathbf{y}})=\delta\circ\varphi\left(p({\mathbf{x}},{\mathbf{y}}).\right)$
We first consider $[t_{\max},\infty)$. Let $P_{g}$ be a set of potential
values for which $g$ outputs a non-zero value:

$P_{g}=\\{p({\mathbf{a}},{\mathbf{b}})\mid({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n},t_{\max}\leq
p({\mathbf{a}},{\mathbf{b}})\\}.$

Since the activation function and weights are discretized, we have
$|P_{g}|=O((s+n)w)$.

We operate the binary search over $P_{g}$, and construct a threshold gate that
outputs one for every input $({\mathbf{a}},{\mathbf{b}})$ such that
$p({\mathbf{a}},{\mathbf{b}})$ takes a particular value in $P$. For any
$Q\subseteq P_{g}$, we define $\mathrm{mid}(Q)$ as the median of the integers
in $Q$, and $Q^{+}$ (resp., $Q^{-}$) as the upper (resp., lower) half of $Q$:

$Q^{+}=\\{p\in Q\mid p\leq\mathrm{mid}(Q)\\}\quad\mbox{ and }\quad
Q^{-}=\\{p\in Q\mid\mathrm{mid}(Q)<p\\}.$

If $Q$ contains an even number of values, we take the greater value of the two
median values .

Let ${\mathbf{s}}$ be a binary string. We inductively construct a threshold
gate $g_{{\mathbf{s}}}$ on the length of ${\mathbf{s}}$. For two strings
${\mathbf{t}}$ and ${\mathbf{s}}$, we write ${\mathbf{t}}\prec{\mathbf{s}}$ if
${\mathbf{t}}$ is a proper prefix of ${\mathbf{s}}$. We denote a string
${\mathbf{t}}$ followed by 0 (resp., by 1) by ${\mathbf{t}}0$ (resp.,
${\mathbf{t}}1$).

As the base of our construction, we consider the empty string $\epsilon$. Let
$P_{\epsilon}=P_{g}$. We constructs a threshold gate $g_{\epsilon}$ that
computes

$g_{\epsilon}({\mathbf{x}},{\mathbf{y}})=\mathrm{sign}\left(p({\mathbf{x}},{\mathbf{y}})-t_{g}[\epsilon]\right),$

where $t_{g}[\epsilon]=\mathrm{mid}(P_{\epsilon})$.

Suppose we have constructed gates $g_{{\mathbf{t}}}$ for every ${\mathbf{t}}$
satisfying $|{\mathbf{t}}|\leq k-1$. Consider a string ${\mathbf{s}}$ of
length $k$. By the induction hypothesis, we have gates $g_{{\mathbf{t}}}$ for
every ${\mathbf{t}}$ and ${\mathbf{t}}\prec{\mathbf{s}}$. Let
${\mathbf{s}}^{\prime}$ be a string obtained by dropping the last symbol of
${\mathbf{s}}$. Then, we define

$P_{\mathbf{s}}=\left\\{\begin{array}[]{ll}P_{{\mathbf{s}}^{\prime}}^{+}&\mbox{if
the last symbol of ${\mathbf{s}}$ is 1};\\\
P_{{\mathbf{s}}^{\prime}}^{-}&\mbox{if the last symbol of ${\mathbf{s}}$ is
0}.\end{array}\right.$

Let $W=3(s+n)w$. We construct a threshold gate $g_{{\mathbf{s}}}$ as follows:

$g_{{\mathbf{s}}}({\mathbf{x}},{\mathbf{y}})=\mathrm{sign}\left(p({\mathbf{x}},{\mathbf{y}})+\sum_{{\mathbf{t}}\prec{\mathbf{s}}}w_{{\mathbf{t}},{\mathbf{s}}}\cdot
g_{{\mathbf{t}}}({\mathbf{x}},{\mathbf{y}})-t_{g}[{{\mathbf{s}}}]\right),$

where $w_{{\mathbf{t}},{\mathbf{s}}}$ is the weight of the output of
$g_{{\mathbf{t}}}$ and is defined as

$w_{{\mathbf{t}},{\mathbf{s}}}=\left\\{\begin{array}[]{ll}W&\mbox{if
${\mathbf{t}}1$ is a prefix of ${\mathbf{s}}$};\\\ -W&\mbox{if ${\mathbf{t}}0$
is a prefix of ${\mathbf{s}}$};\\\ 0&\mbox{otherwise},\end{array}\right.$

and $t_{g}[{\mathbf{s}}]=\mathrm{mid}(P_{\mathbf{s}})-W\cdot
N_{1}({\mathbf{s}})$, where $N_{1}({\mathbf{s}})$ is the number of ones in
${\mathbf{s}}$.

We repeatedly apply the above procedure until $|P_{\mathbf{s}}|=1$. Since we
apply the binary search over $P$, we have $O(|P|)=O((s+n)w)$ gates and the
length of $|{\mathbf{s}}|$ as $O(\log(s+n)+\log w)$ for any gate
$g_{{\mathbf{s}}}$.

Consider the strings ${\mathbf{s}}$ for which we have constructed
$g_{{\mathbf{s}}}$. Let

$S_{g}=\\{{\mathbf{s}}\mid 2\leq|P_{\mathbf{s}}|\\}\quad\mbox{ and }\quad
L_{g}=\\{{\mathbf{s}}\mid|P_{\mathbf{s}}|=1\\}.$

For each $({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$, we denote the unique
string that satisfies
$P_{{\mathbf{s}}^{*}({\mathbf{a}},{\mathbf{b}})}=\\{p({\mathbf{a}},{\mathbf{b}})\\}$
by ${\mathbf{s}}^{*}({\mathbf{a}},{\mathbf{b}})\in L_{g}$. The following
claims show that the $g_{\mathbf{s}}$s are useful for simulating $g$.

######  Claim 27.

Let $({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$ be an input assignment that
satisfies $t_{\max}\leq p({\mathbf{a}},{\mathbf{b}})$.

(i)

For ${\mathbf{s}}\in S_{g}$, $g_{\mathbf{s}}$ outputs one if and only if
${\mathbf{s}}1$ is a prefix of ${\mathbf{s}}^{*}({\mathbf{a}},{\mathbf{b}})$.

(ii)

For ${\mathbf{s}}\in L_{g}$, $g_{{\mathbf{s}}}$ outputs one if and only if
${\mathbf{s}}={\mathbf{s}}^{*}({\mathbf{a}},{\mathbf{b}})$.

######  Proof 7.3.

Consider an arbitrary input assignment
$({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$ that satisfies $t_{\max}\leq
p({\mathbf{a}},{\mathbf{b}})$. For notational simplicity, we write
${\mathbf{s}}^{*}$ for ${\mathbf{s}}^{*}({\mathbf{a}},{\mathbf{b}})$.

Proof of (i). We verify the claim by induction on the length of
${\mathbf{s}}$. For the base case, we consider ${\mathbf{\epsilon}}$. It
suffices to show that $g_{\epsilon}({\mathbf{a}},{\mathbf{b}})=1$ if the first
symbol of ${\mathbf{s}}^{*}$ is 1; otherwise,
$g_{\epsilon}({\mathbf{a}},{\mathbf{b}})=0$. If the first symbol is 1, we have
$p({\mathbf{a}},{\mathbf{b}})\in P^{+}_{\epsilon}$, which implies that
$t_{g}[\epsilon]\leq p({\mathbf{a}},{\mathbf{b}})$. Thus,
$g_{\epsilon}({\mathbf{a}},{\mathbf{b}})=1$. Similarly, if the first symbol is
zero, we have $p({\mathbf{a}},{\mathbf{b}})\in P^{-}_{\epsilon}$, implying
that $p({\mathbf{a}},{\mathbf{b}})<t_{g}[\epsilon]$. Thus,
$g_{\epsilon}({\mathbf{a}},{\mathbf{b}})=0$.

We assume that for the induction hypothesis, $g_{\mathbf{t}}$ outputs one if
and only if ${\mathbf{t}}1$ is a prefix of
${\mathbf{s}}^{*}({\mathbf{a}},{\mathbf{b}})$ for every ${\mathbf{t}}$ of
length $k-1$, at most, for a positive integer $k$. Next, we consider a string
${\mathbf{s}}$ of length $k$.

We first verify that $g_{\mathbf{s}}$ outputs zero if ${\mathbf{s}}$ itself is
not a prefix of ${\mathbf{s}}^{*}({\mathbf{a}},{\mathbf{b}})$. If
${\mathbf{s}}$ is not a prefix of ${\mathbf{s}}^{*}$, there exists a prefix
${\mathbf{t}}^{\prime}$ of ${\mathbf{s}}$ such that ${\mathbf{t}}^{\prime}0$
(resp., ${\mathbf{t}}^{\prime}1$) is a prefix of ${\mathbf{s}}$, whereas
${\mathbf{t}}^{\prime}1$ (resp., ${\mathbf{t}}^{\prime}0$) is not a prefix of
${\mathbf{s}}^{*}$.

Consider the case where ${\mathbf{t}}^{\prime}0$ is a prefix of
${\mathbf{s}}^{*}$ (i.e., ${\mathbf{t}}^{\prime}1$ is a prefix of
${\mathbf{s}}$). In this case, the induction hypothesis implies that:
$g_{{\mathbf{t}}^{\prime}}({\mathbf{a}},{\mathbf{b}})=0$. In addition, since
${\mathbf{t}}^{\prime}1$ is a prefix of ${\mathbf{s}}$, we have
$w_{{\mathbf{t}}^{\prime},{\mathbf{s}}}=W$. Thus, the potential of
$g_{{\mathbf{s}}}$ for $({\mathbf{a}},{\mathbf{b}})$ is at most

$\displaystyle
p({\mathbf{a}},{\mathbf{b}})+\sum_{{\mathbf{t}}\prec{\mathbf{s}}}w_{{\mathbf{t}},{\mathbf{s}}}\cdot
g_{{\mathbf{t}}}({\mathbf{a}},{\mathbf{b}})-t_{g}[{{\mathbf{s}}}]$
$\displaystyle\leq$ $\displaystyle
p({\mathbf{a}},{\mathbf{b}})+W\cdot(N_{1}({\mathbf{s}})-1)-\mathrm{mid}(P_{{\mathbf{s}}})-W\cdot
N_{1}({\mathbf{s}})$ $\displaystyle\leq$ $\displaystyle
p({\mathbf{a}},{\mathbf{b}})-\mathrm{mid}(P_{{\mathbf{s}}})-W,$

which is less than zero because $p({\mathbf{a}},{\mathbf{b}})\leq(s+n)w$.

Consider the case in which ${\mathbf{t}}^{\prime}1$ is a prefix of
${\mathbf{s}}^{*}$ (i.e., ${\mathbf{t}}^{\prime}0$ is a prefix of
${\mathbf{s}}$). In this case, the induction hypothesis implies that
$g_{{\mathbf{t}}^{\prime}}({\mathbf{a}},{\mathbf{b}})=1$. In addition, since
${\mathbf{t}}^{\prime}0$ is a prefix of ${\mathbf{s}}$,
$w_{{\mathbf{t}}^{\prime},{\mathbf{s}}}=-W$. Thus, the potential of
$g_{{\mathbf{s}}}$ for $({\mathbf{a}},{\mathbf{b}})$ is at most

$\displaystyle
p({\mathbf{a}},{\mathbf{b}})+\sum_{{\mathbf{t}}\prec{\mathbf{s}}}w_{{\mathbf{t}},{\mathbf{s}}}\cdot
g_{{\mathbf{t}}}({\mathbf{a}},{\mathbf{b}})-t_{g}[{{\mathbf{s}}}]$
$\displaystyle\leq$ $\displaystyle p({\mathbf{a}},{\mathbf{b}})+(W\cdot
N_{1}({\mathbf{s}})-W)-\mathrm{mid}(P_{{\mathbf{s}}})-W\cdot
N_{1}({\mathbf{s}})$ $\displaystyle\leq$ $\displaystyle
p({\mathbf{a}},{\mathbf{b}})-\mathrm{mid}(P_{{\mathbf{s}}})-W,$

which is again less than zero because $p({\mathbf{a}},{\mathbf{b}})\leq
2(s+n)w$.

Suppose ${\mathbf{s}}$ is a prefix of ${\mathbf{s}}^{*}$. The induction
hypothesis implies that the potential of $g_{\mathbf{s}}$ is equal to

$\displaystyle
p({\mathbf{a}},{\mathbf{b}})+\sum_{{\mathbf{t}}\prec{\mathbf{s}}}w_{{\mathbf{t}},{\mathbf{s}}}\cdot
g_{{\mathbf{t}}}({\mathbf{a}},{\mathbf{b}})-t_{g}[{{\mathbf{s}}}]$
$\displaystyle=$ $\displaystyle p({\mathbf{a}},{\mathbf{b}})+W\cdot
N_{1}({\mathbf{s}})-\mathrm{mid}(P_{{\mathbf{s}}})-W\cdot N_{1}({\mathbf{s}})$
$\displaystyle=$ $\displaystyle
p({\mathbf{a}},{\mathbf{b}})-\mathrm{mid}(P_{{\mathbf{s}}}).$

Thus, similar to the base case, we can show that
$g_{\mathbf{s}}({\mathbf{a}},{\mathbf{b}})=1$ if ${\mathbf{s}}1$ is a prefix
of ${\mathbf{s}}^{*}$, and $g_{\mathbf{s}}(({\mathbf{a}},{\mathbf{b}}))=0$
otherwise. More formally, if ${\mathbf{s}}1$ is a prefix of
${\mathbf{s}}^{*}$, we have $p({\mathbf{a}},{\mathbf{b}})\in
P^{+}_{\mathbf{s}}$, which implies that $\mathrm{mid}(P_{\mathbf{s}})\leq
p({\mathbf{a}},{\mathbf{b}})$. Thus,
$g_{\mathbf{s}}({\mathbf{a}},{\mathbf{b}})=1$. If ${\mathbf{s}}0$ is a prefix
of ${\mathbf{s}}^{*}$, we have $p({\mathbf{a}},{\mathbf{b}})\in
P^{-}_{\mathbf{s}}$, which implies that
$p({\mathbf{a}},{\mathbf{b}})<\mathrm{mid}(P_{\mathbf{s}})$. Thus,
$g_{\mathbf{s}}({\mathbf{a}},{\mathbf{b}})=0$.

Proof of (ii). Consider ${\mathbf{s}}\in L_{g}$. Similar to claim (i), we can
verify that $g_{\mathbf{s}}({\mathbf{a}},{\mathbf{b}})=0$ if
${\mathbf{s}}\neq{\mathbf{s}}^{*}$. If ${\mathbf{s}}={\mathbf{s}}^{*}$, claim
(i) also implies that the potential of $g_{{\mathbf{s}}^{*}}$ is equal to

$\displaystyle
p({\mathbf{a}},{\mathbf{b}})+\sum_{{\mathbf{t}}\prec{\mathbf{s}}^{*}}w_{{\mathbf{t}},{\mathbf{s}}^{*}}\cdot
g_{{\mathbf{t}}}({\mathbf{a}},{\mathbf{b}})-t_{g}[{{\mathbf{s}}^{*}}]$
$\displaystyle=$ $\displaystyle p({\mathbf{a}},{\mathbf{b}})+W\cdot
N_{1}({\mathbf{s}})-\mathrm{mid}(P_{{\mathbf{s}}})-W\cdot N_{1}({\mathbf{s}})$
$\displaystyle=$ $\displaystyle
p({\mathbf{a}},{\mathbf{b}})-\mathrm{mid}(P_{{\mathbf{s}}^{*}}).$

Since $P_{{\mathbf{s}}^{*}}=\\{p({\mathbf{a}},{\mathbf{b}})\\}$,
$\mathrm{mid}(P_{{\mathbf{s}}^{*}})=p({\mathbf{a}},{\mathbf{b}})$. Thus, we
have

$\displaystyle
p({\mathbf{a}},{\mathbf{b}})-\mathrm{mid}(P_{{\mathbf{s}}^{*}})=0,$

which implies that $g_{{\mathbf{s}}^{*}}({\mathbf{a}},{\mathbf{b}})=1$.

######  Claim 28.

For any $({\mathbf{a}},{\mathbf{b}})\in\\{0,1\\}^{2n}$ that satisfies
$p({\mathbf{a}},{\mathbf{b}})<t_{\max}$, every gate $g_{\mathbf{s}}$ outputs
zero.

######  Proof 7.4.

Since $p({\mathbf{a}},{\mathbf{b}})<t_{\max}\leq\mathrm{mid}({P_{g}})$,
$g_{\epsilon}({\mathbf{a}},{\mathbf{b}})=0$, which is implied by a similar
argument to Claim 27, all the gates $g_{\mathbf{s}}$ such that ${\mathbf{s}}$
contains a symbol 1. If ${\mathbf{s}}$ consists of only 0s, we have
$p({\mathbf{a}},{\mathbf{b}})<t_{\max}\leq\mathrm{mid}(Q)$ for any $Q\subseteq
P_{g}$, which implies that $g_{\mathbf{s}}({\mathbf{a}},{\mathbf{b}})=0$.

Claims 27 and 28 imply that we can safely replace $g$ with $g_{\mathbf{s}}$s,
${\mathbf{s}}\in S_{g}\cup L_{g}$, by connecting the output of each gate
$g_{{\mathbf{s}}}$, ${\mathbf{s}}\in L_{g}$, with weight
$w_{g,g^{\prime}}\cdot(\delta\circ\varphi(p))$, where $p$ is the unique value
in $P_{\mathbf{s}}$ to every gate $g^{\prime}$ that the gate $g$ is originally
connected to in $C$. Since $|S_{g}\cup L_{g}|=O((s+n)w)$ and the length of
${\mathbf{s}}$ is $O(\log(s+n)+\log w)$, the size and depth increase by these
factors, respectively.

We can construct another set of threshold gates for $(-\infty,t_{\min}]$ in a
similar manner to the above procedure That is, it suffices to consider a gate
obtained by multiplying $-1$ by the weights and threshold of $g$ together with
an interval $[-t_{\min},\infty)$.

Using the above procedure, we replace every gate $g\in
G\backslash\\{g^{\mathrm{clf}}\\}$ in $C$ with a set of threshold gates, and
complete the construction of $C^{\prime}$. Clearly, the size of $C^{\prime}$
is $O(s\cdot(s+n)w)$. Since $g_{\mathbf{s}}$ receives the outputs of
$g_{{\mathbf{t}}}$ for every ${\mathbf{t}}\prec{\mathbf{s}}$ and the length of
${\mathbf{s}}$ is $O(\log(s+n)+\log w)$, the depth of $C^{\prime}$ is
$O(d\cdot(\log(s+n)+\log w))$. Claims 27 and 28 imply that the energy of
$C^{\prime}$ is $O(e\cdot(\log(s+n)+\log w))$. Clearly, the weight of
$C^{\prime}$ is $W=O((s+n)w)$. Thus, Theorem 3.1 implies that $rk(M_{C})$ is
bounded by

$\displaystyle O(e(\log(s+n)+\log w)\\!\cdot\\!d(\log(s+n)+\log
w)\\!\cdot\\!(\log s+\log w+\log n))$ $\displaystyle=$ $\displaystyle
O(ed(\log s+\log n+\log w)^{3}),$

as desired.


# BAMBINO-LM: (Bilingual-)Human-Inspired Continual Pretraining of BabyLM

Zhewen Shen1 Aditya Joshi 1 Ruey-Cheng Chen2
1 University of New South Wales, Sydney, Australia
2 Canva, Sydney, Australia
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Children from bilingual backgrounds benefit from interactions with parents and
teachers to re-acquire their heritage language. In this paper, we investigate
how this insight from behavioral study can be incorporated into the learning
of small-scale language models. We introduce BAMBINO-LM, a continual
pretraining strategy for BabyLM that uses a novel combination of alternation
and PPO-based perplexity reward induced from a parent Italian model. Upon
evaluation on zero-shot classification tasks for English and Italian, BAMBINO-
LM improves the Italian language capability of a BabyLM baseline. Our ablation
analysis demonstrates that employing both the alternation strategy and PPO-
based modeling is key to this effectiveness gain. We also show that, as a side
effect, the proposed method leads to similar degradation in L1 effectiveness
as human children would have had in an equivalent learning scenario.

BAMBINO-LM: (Bilingual-)Human-Inspired Continual Pretraining of BabyLM

Zhewen Shen1 Aditya Joshi 1 Ruey-Cheng Chen2 1 University of New South Wales,
Sydney, Australia 2 Canva, Sydney, Australia<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

The recently held BabyLM challenge (Warstadt et al., 2023) explores
pretraining of language models using a constrained dataset analogous to the
linguistic exposure of a 13-year-old English-speaking child. In this paper, we
extend the BabyLM challenge to a bilingual setting, drawing inspiration from
parent-child interactions in heritage language acquisition Lohndal et al.
(2019). Immigrant children in western societies, who may have acquired their
home language at a young age, can sometimes need to re-acquire the same
language during the school years when the language becomes a minority. These
heritage speakers typically benefit from an extended exposure to the minority
language at home or in the community, owing largely to feedback and stimuli
provided by parents and family members Montrul (2010). This observation about
child bilingualism is in line with the behaviorist theory for child language
development Demirezen (1988). Inspired by this line of work, we ask the
following research question:

> _Can a small-scale language model trained on the majority language (e.g.
> English) be continually pretrained on the minority language, leveraging the
> feedback of a second model that is fluent in the latter language?_

To address this question, we introduce ‘Bilingual language Acquisition
Modeling Based on INterleaved Optimization of Language Models (BAMBINO-LM)’, a
novel continual pretraining strategy that uses a combination of alternation
and proximal policy optimization (PPO) using a reward from a second model
playing the parent role (i.e., a large language model pretrained in the
minority language). We experiment with BabyLM trained on English, and
continually pretrain this model on an assumed second language, Italian. In its
connection to cognitive processing, our work makes the following
contributions:

  * •

BAMBINO-LM draws inspiration from bilingual language acquisition and learns
from interactions with a second model by incorporating a perplexity-based
reward for language model pretraining.

  * •

We show that BAMBINO-LM can acquire Italian to a reasonable degree with some
expected degradation in its English capability. The findings hints at a common
learning trajectories for second language acquisition shared by language
models and humans.

##  2 Related Work

Pretraining small-scale language models is an emerging field that has garnered
some interest from the language acquisition community. BabyBERTa Huebner et
al. (2021) is an early adaptation to this scenario. Warstadt et al. (2023)
introduce the BabyLM challenge to provide an atypically small dataset for
benchmarking small-scale language models. This shared task enables research in
not only language acquisition but sample-efficient pretraining.

Our work is primarily focused on continual pretraining and conducted in a
setup similar to Yadavalli et al. (2023), where a tiered first/second language
acquisition process is attempted. Samuel (2023) also experiments with a
teacher-student setting but only tests the approach on English tasks. Evanson
et al. (2023) is another closely related work, which investigates the learning
trajectory of large-scale language models by probing their syntactic and
semantic capabilities at each step. Contrasting GPT-2 models with children,
the study shows that the linguistic skills are acquired sequentially in a
similar order.

Reinforcement learning from human feedback (RLHF) utilizes human preferences
for serving reward signals when dealing with sparse training labels Christiano
et al. (2017); Stiennon et al. (2020), and has been shown successful for
generative tasks such as dialogues and summarization. This approach is further
extended in Bai et al. (2022) by using AI feedback (RLAIF) to remove the
dependency on human preference data, leading to better scalability and signal
availability. Our work departs from these prior efforts in the way a
perplexity reward is induced and blended into the learning process.

##  3 Methods

Figure 1: Architecture of BAMBINO-LM.

Figure 1 shows the two phases of BAMBINO-LM. The learning phase involves
continual pretraining a small-scale language model (_baby model_
$\mathcal{B}$) whose initial pretraining was originally done on English data,
while the feedback phase involves interactions with the Italian language model
(_parent model_ $\mathcal{P}$). During the learning phase, pretraining for
$\mathcal{B}$ is continued by employing causal language modeling on Italian
data. Causal language modeling (CLM), also known as next token prediction, is
a standard technique to train a decoder-only model. The objective is defined
as follows:

$\mathcal{L}_{\operatorname{CLM}}=-\frac{1}{|x|}\sum_{i=0}^{|x|}\log\mathbb{P}(x_{t}\mid
x_{0},\ldots,x_{t-1}).$

There are two architectural innovations in BAMBINO-LM:

### Feedback phase based on PPO

We construct prompt $x$ by selecting the first $k$ tokens from the training
example, and solicit output $y_{\mathcal{B}}=\mathcal{B}(x)$ from the baby
model. We then use Proximal Policy Optimization (PPO) where $\mathcal{B}$’s
parameters are updated according to a clipped surrogate objective Schulman et
al. (2017). This objective moderates updates to the policy, facilitating
stable and efficient learning by incorporating a clipping mechanism. Its
definition is given as follows:

$\mathcal{L}_{\text{PPO}}=\mathbb{E}_{t}\left[\min\left(r_{t}(\theta)\hat{A}_{t},\operatorname{clip}(r_{t}(\theta),1-\epsilon,1+\epsilon)\hat{A}_{t}\right)\right].$

Note that the advantage function $\hat{A}_{t}$ is of the form:

$\hat{A}_{t}=R+\gamma V(s_{t+1})-V(s_{t}).$

The reward $R$ for the advantage function is then calculated using the
following function:

$R(y_{\mathcal{B}})=\frac{\alpha}{\beta(\operatorname{PPL}_{\mathcal{P}}(y_{\mathcal{B}})-\tau)},$
(1)

where $\alpha$ and $\beta$ are parameters, $\operatorname{PPL}_{\mathcal{P}}$
represents the perplexity of the parent model $\mathcal{P}$ for the sequence
$y_{\mathcal{B}}$, and $\tau$ is a threshold value for perplexity. We use the
following formulation of perplexity:

$\operatorname{PPL}(x)=\exp\left[\sum_{i=0}^{|x|}\log\mathbb{P}(x_{t}\mid
x_{0},\ldots,x_{t-1})\right].$

### Alternating run

We adopt an alternating run strategy between the learning and feedback phases,
which is summarized in Algorithm 1. The rationale behind this is two-fold: 1)
this strategy simulates frequent interactions between a child and its parent
through dialogues, which has been our main motivation behind this study; 2)
using multiple rewards is shown beneficial for reinforcement learning Dann et
al. (2023). To expand on the second point, our findings further suggest that
using perplexity as a reward can lead to exploitation when baby model
$\mathcal{B}$ attempts to produce similar utterances to those coming from
parent model $\mathcal{P}$. Without this strategic alternation between CLM and
PPO, the pretraining tends to produce undesirable behaviours such as repeating
words.

Algorithm 1 BAMBINO-LM Training.

1:procedure Train($\mathcal{D},\mathcal{B},\mathcal{P}$)

2: input: pretraining dataset $\mathcal{D}$, baby model $\mathcal{B}$, and
parent model $\mathcal{P}$.

3: $r_{\operatorname{CLM}},r_{\operatorname{PPO}}\leftarrow 10,2$

4: $r\leftarrow r_{\operatorname{CLM}}+r_{\operatorname{PPO}}$

5: for $i,x\in\operatorname{enumerate}(\mathcal{D}$) do

6: if $i\%r<r_{\operatorname{CLM}}$ then

7: perform CLM step

8: else

9: $y_{\mathcal{B}}\leftarrow\mathcal{B}(x[1..k])$

10: reward $\leftarrow R(y_{\mathcal{B}})$

11: perform PPO step

12: end if

13: end for

14:end procedure

##  4 Experiment Setup

Mimicking their process to create the BabyLM challenge corpus (Warstadt et
al., 2023), we created an Italian dataset that is comparable in size to the
_strict-small_ track of the challenge, and perform identical
preprocessing111https://github.com/babylm/babylm_data_preprocessing; Accessed
on 13th May, 2024.. Table 1 shows the statistics of the Italian language
dataset.

For the choice of the baby model, we use English baseline OPT-125m Zhang et
al. (2022) model for the _strict-small_ track provided by the BabyLM
organizers. For the parent model, we use gpt2-small-italian model by de Vries
and Nissim (2021). Using the Italian dataset described above, we conduct
continual pretraining over 10 epochs, consisting of 10 learning phase steps
followed by 2 feedback phase steps. We use $k=5$ to solicit the first few
tokens for prompting the baby model. All models are trained using
HuggingFace’s transformer (Wolf et al., 2020) and trl (von Werra et al., 2020)
library.

Dataset | %
---|---
CHILDES (MacWhinney, 2000) | 2.23
DailyDialog (Li et al., 2017) | 4.45
QED (Abdelali et al., 2014) | 11.86
OpenSubtitles Lison and Tiedemann (2016) | 27.58
Standardised Project Gutenberg Corpus Gerlach and Font-Clos (2020) | 16.19
Children’s Story 222https://www.gutenberg.org/ebooks/bookshelf/353 | 18.57
Wikipedia 333https://dumps.wikimedia.org/itwiki/ | 19.10
Table 1: Italian dataset used for continual pretraining.

For downstream tasks, we use four Italian language tasks in UINAUIL Basile et
al. (2023) and four English language tasks in GLUE Wang et al. (2018). The
tasks were selected primarily based on computational constraints for the
project. We also include BLiMP Warstadt et al. (2020) for that it is used in
the original BabyLM challenge. All tasks are conducted in a zero-shot
classification setting.

##  5 Results

Task / Model | BabyLM | BAMBINO-LM
---|---|---
UINAUIL
HaSpeeDe | 0.4774 | 0.4592
IronITA | 0.4966 | 0.5516
SENTIPOLC | 0.1575 | 0.4050
Textual Entailment | 0.4950 | 0.5525
Average | 0.3416 | 0.4613
GLUE
MNLI | 0.3472 | 0.3530
MNLI-MM | 0.3483 | 0.3521
RTE | 0.5271 | 0.5199
SST2 | 0.5034 | 0.5241
Average | 0.4315 | 0.4373
BLiMP
Average | 0.6255 | 0.5503
Table 2: Comparison of BAMBINO-LM with BabyLM.

Table 2 shows a significant improvement in Italian downstream tasks for
BAMBINO-LM as compared with the BabyLM baseline. Specifically, we achieve an
average improvement of 0.1197 $(0.3416\to 0.4613)$ without substantial
differences in English classification tasks. However, we notice an expected
decrease of 0.0752 $(0.6255\to 0.5503)$ in the English language BLiMP dataset.
These observations are in line with Yadavalli et al. (2023) which show that
native child-directed speech can lead to negative cross-lingual transfer and
impede L2 acquisition depending on the choice of L1.

In Table 3 we examine two ablated versions of our model: (a) w/o PPO: Trained
solely on the CLM objective with no feedback phase; (b) w/o alternating: Use
BAMBINO-LM with no alternating runs. Instead, it trains with the CLM objective
for the first $85\%$ of each epoch and then switches to the PPO objective for
the remaining $15\%$.

Removing the interactive feedback mechanism (w/o PPO) and the alternating
strategy (w/o alternating) significantly decreases Italian performance
compared to our primary model. On UINAUIL tasks, the average score drops from
0.4613 to 0.4000 (w/o PPO) and 0.3513 (w/o alternating). However, we do not
observe significant improvements in performance in both the English language
task sets (GLUE and BLiMP). For GLUE tasks, the average scores remain
consistent, with 0.4373 for BAMBINO-LM, 0.4375 for w/o PPO, and 0.4357 for w/o
alternating. On the BLiMP dataset, the average scores are 0.5503 for BAMBINO-
LM and 0.5554 for w/o PPO.

Task / Model |  BAMBINO-LM w/o PPO |  BAMBINO-LM w/o alternating
---|---|---
UINAUIL
HaSpeeDe |  0.4798 |  0.4925
IronITA |  0.4966 |  0.4989
SENTIPOLC |  0.2775 |  0.1580
Textual Entailment |  0.5500 |  0.5500
Average |  0.4000 |  0.3513
GLUE
MNLI |  0.3540 |  0.3522
MNLI-MM |  0.3502 |  0.3545
RTE |  0.5343 |  0.5271
SST2 |  0.5115 |  0.5092
Average |  0.4375 |  0.4357
BLiMP
Average |  0.5554 |  0.5268
Table 3: Results of the ablation experiments.

These results indicate that PPO modeling and alternating runs are both crucial
for improving the bilingual ability of BAMBINO-LM without negatively impacting
English performance. Furthermore, the lack of significant changes in English
scores reinforces that these strategies enhance bilingual capabilities without
compromising performance on existing benchmarks.

##  6 Conclusion

This paper introduces BAMBINO-LM, a continual pretraining strategy mimicking
the process of second language acquisition under an interactive setting.
BAMBINO-LM uses a two-phase approach: it incorporates reward from a parent
Italian model into a PPO-based mechanism, and alternates this procedure
together with causal language modeling on top of Italian text. Our experiments
demonstrate systematic improvement in Italian with a marginal but expected
decrease in English, which echoes the past results in second language
acquisition for large language models Evanson et al. (2023). These findings
highlight the efficacy of our approach in enhancing bilingual capabilities
while maintaining performance in the original language.

In future work, we aim to explore the effect of alternative metrics and
different reward learning mechanisms that better align with human feedback
behaviors. This also includes exploring rewards that capture linguistic
quality and provide direct, “constructive” corrections to the model output
which is commonly known as an effective learning strategy for language
development.

## Limitations

The approach relies on availability of a base model in a language, English in
our case. Although we download Italian language datasets from known Italian
sources, we do not explicitly validate the language of the text. We use the
PPO model as is, and do not experimentally tune its parameters. Similarly,
using perplexity as a metric for computing rewards may not be the optimal
solution, as perplexity itself is influenced by many factors of the parent
model.

## Ethics Statement

The paper uses publicly available datasets for training and evaluation that do
not possess known harms. The evaluative tasks are typical language learning
tasks. However, the resultant models are not tested for harmful or biased
content.

## References

  * Abdelali et al. (2014) Ahmed Abdelali, Francisco Guzman, Hassan Sajjad, and Stephan Vogel. 2014.  The AMARA corpus: Building parallel language resources for the educational domain.  In _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , pages 1856–1862, Reykjavik, Iceland. European Language Resources Association (ELRA).
  * Bai et al. (2022) Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. 2022.  Constitutional AI: Harmlessness from AI feedback.  _arXiv preprint arXiv:2212.08073_.
  * Basile et al. (2023) Valerio Basile, Livio Bioglio, Alessio Bosca, Cristina Bosco, and Viviana Patti. 2023.  UINAUIL: A unified benchmark for Italian natural language understanding.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 3: System Demonstrations)_ , pages 348–356, Toronto, Canada. Association for Computational Linguistics.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30.
  * Dann et al. (2023) Christoph Dann, Yishay Mansour, and Mehryar Mohri. 2023.  Reinforcement learning can be more efficient with multiple rewards.  In _International Conference on Machine Learning_ , pages 6948–6967. PMLR.
  * de Vries and Nissim (2021) Wietse de Vries and Malvina Nissim. 2021.  As good as new. how to successfully recycle English GPT-2 to make models for other languages.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 836–846, Online. Association for Computational Linguistics.
  * Demirezen (1988) Mehmet Demirezen. 1988.  Behaviorist theory and language learning.  _Hacettepe Üniversitesi Eğitim Fakültesi Dergisi_ , 3(3).
  * Evanson et al. (2023) Linnea Evanson, Yair Lakretz, and Jean Rémi King. 2023.  Language acquisition: do children and language models follow similar learning stages?  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 12205–12218.
  * Gerlach and Font-Clos (2020) Martin Gerlach and Francesc Font-Clos. 2020.  A standardized project gutenberg corpus for statistical analysis of natural language and quantitative linguistics.  _Entropy_ , 22(1).
  * Huebner et al. (2021) Philip A Huebner, Elior Sulem, Fisher Cynthia, and Dan Roth. 2021.  BabyBERTa: Learning more grammar with small-scale child-directed language.  In _Proceedings of the 25th Conference on Computational Natural Language Learning_ , pages 624–646.
  * Li et al. (2017) Yanran Li, Hui Su, Xiaoyu Shen, Wenjie Li, Ziqiang Cao, and Shuzi Niu. 2017.  DailyDialog: A manually labelled multi-turn dialogue dataset.  In _Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 986–995, Taipei, Taiwan. Asian Federation of Natural Language Processing.
  * Lison and Tiedemann (2016) Pierre Lison and Jörg Tiedemann. 2016.  OpenSubtitles2016: Extracting large parallel corpora from movie and TV subtitles.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_ , pages 923–929, Portorož, Slovenia. European Language Resources Association (ELRA).
  * Lohndal et al. (2019) Terje Lohndal, Jason Rothman, Tanja Kupisch, and Marit Westergaard. 2019.  Heritage language acquisition: What it reveals and why it is important for formal linguistic theories.  _Language and Linguistics Compass_ , 13(12):e12357.
  * MacWhinney (2000) Brian MacWhinney. 2000.  _The CHILDES project: The database_ , volume 2.  Psychology Press.
  * Montrul (2010) Silvina Montrul. 2010.  Current issues in heritage language acquisition.  _Annual Review of Applied Linguistics_ , 30:3–23.
  * Samuel (2023) David Samuel. 2023.  Mean BERTs make erratic language teachers: the effectiveness of latent bootstrapping in low-resource settings.  In _Proceedings of the BabyLM Challenge at the 27th Conference on Computational Natural Language Learning_ , pages 221–237.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021.
  * von Werra et al. (2020) Leandro von Werra, Younes Belkada, Lewis Tunstall, Edward Beeching, Tristan Thrush, Nathan Lambert, and Shengyi Huang. 2020.  TRL: Transformer reinforcement learning.  https://github.com/huggingface/trl.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. 2018.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _International Conference on Learning Representations_.
  * Warstadt et al. (2023) Alex Warstadt, Aaron Mueller, Leshem Choshen, Ethan Wilcox, Chengxu Zhuang, Juan Ciro, Rafael Mosquera, Bhargavi Paranjabe, Adina Williams, Tal Linzen, and Ryan Cotterell. 2023.  Findings of the BabyLM challenge: Sample-efficient pretraining on developmentally plausible corpora.  In _Proceedings of the BabyLM Challenge at the 27th Conference on Computational Natural Language Learning_ , pages 1–34, Singapore. Association for Computational Linguistics.
  * Warstadt et al. (2020) Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mohananey, Wei Peng, Sheng-Fu Wang, and Samuel R Bowman. 2020.  BLiMP: The benchmark of linguistic minimal pairs for english.  _Transactions of the Association for Computational Linguistics_ , 8:377–392.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Yadavalli et al. (2023) Aditya Yadavalli, Alekhya Yadavalli, and Vera Tobin. 2023.  SLABERT talk pretty one day: Modeling second language acquisition with BERT.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 11763–11777, Toronto, Canada. Association for Computational Linguistics.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. 2022.  OPT: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_.