# Approximation of polynomials from Walsh tail spaces

Alexandros Eskenazis  (A. E.) CNRS, Institut de Mathématiques de Jussieu,
Sorbonne Université, France and Trinity College, University of Cambridge, UK.
<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Haonan Zhang  (H. Z.)
Department of Mathematics, University of South Carolina
Columbia, SC, 29208, USA<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We derive various bounds for the $L_{p}$ distance of polynomials on the
hypercube from Walsh tail spaces, extending some of Oleszkiewicz’s results
(2017) for Rademacher sums.

This material is based upon work supported by the NSF grant DMS-1929284 while
the authors were in residence at ICERM for the Harmonic Analysis and Convexity
program.

2020 Mathematics Subject Classification. Primary: 42C10; Secondary: 41A17,
60E15.

Key words. Discrete hypercube, polynomial inequalities, Rademacher sum, tail
space.

##  1\. Introduction

Given $n\in\mathbb{N}=\mathbb{Z}_{\geq 1}$, every function
$f:\\{-1,1\\}^{n}\to\mathbb{R}$ admits a unique Fourier–Walsh expansion

$\forall\ x\in\\{-1,1\\}^{n},\qquad
f(x)=\sum_{S\subseteq\\{1,\ldots,n\\}}\widehat{f}(S)w_{S}(x),$ (1)

where the Walsh function $w_{S}$ is given by $w_{S}(x)=\prod_{i\in S}x_{i}$
for $x=(x_{1},\ldots,x_{n})\in\\{-1,1\\}^{n}$. We shall say that $f$ is of
degree at most $k\in\\{1,\ldots,n\\}$ if $\widehat{f}(S)=0$ for every subset
$S$ of $\\{1,\ldots,n\\}$ with $|S|>k$. Similarly, we say that $f$ belongs on
the $k$-th tail space, where $k\in\\{1,\ldots,n\\}$, if $\widehat{f}(S)=0$ for
every subset $S$ with $|S|\leq k$. More generally, given a nonempty subset
$I\subseteq\\{0,1,\ldots,n\\}$, we denote by

$\mathscr{P}_{I}^{n}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\big{\\{}f:\\{-1,1\\}^{n}\to\mathbb{R}:\
\widehat{f}(S)=0\mbox{ for every }S\mbox{ with }|S|\notin I\big{\\}}.$ (2)

We shall also adopt the natural notations
$\mathscr{P}_{>k}^{n}=\mathscr{P}_{\\{k+1,\ldots,n\\}}^{n}$,
$\mathscr{P}_{\leq k}^{n}=\mathscr{P}_{\\{0,1,\ldots,k\\}}^{n}$,
$\mathscr{P}_{=k}^{n}=\mathscr{P}_{\\{k\\}}^{n}$ and so on.

Many modern developments in discrete analysis (see [18]) are centered around
quantitative properties of functions whose spectrum is bounded above or below,
in analogy with estimates established for polynomials in classical
approximation theory on the torus $\mathbb{T}^{n}$ or on $\mathbb{R}^{n}$. One
of the first results of this nature, going back at least to [3, 4], is the
important fact that all finite moments of low-degree Walsh polynomials are
equivalent to each other up to dimension-free factors. Namely, given any
$1\leq p\leq q<\infty$ and $k\in\mathbb{N}$, there exists a (sharp) constant
$\mathsf{M}_{p,q}(k)$ such that for any $n\geq k$, every polynomial
$f:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree at most $k$ satisfies

$\|f\|_{q}\leq\mathsf{M}_{p,q}(k)\|f\|_{p},$ (3)

where $\|\cdot\|_{r}$ always denotes the $L_{r}$ norm on $\\{-1,1\\}^{n}$ with
respect to the uniform probability measure. Note that the reverse of (3) holds
trivially with constant $1$ by Hölder’s inequality. We refer to [8, 13, 16]
for the best known bounds on the implicit constant $\mathsf{M}_{p,q}(k)$. In
the special case $k=1$, (3) is the celebrated Khintchine inequality [15] for
Rademacher sums.

Our starting point is the simple observation that the moment comparison
estimates (3) have the following (equivalent) dual formulation in terms of
distances from tail spaces.

######  Proposition 1.

For every $1\leq p\leq q<\infty$ and $k\in\mathbb{N}$, the constant
$\mathsf{M}_{p,q}(k)$ in inequality (3) is also the least constant for which
every function $f:\\{-1,1\\}^{n}\to\mathbb{R}$, where $n\geq k$, satisfies

$\inf_{g\in\mathscr{P}^{n}_{>k}}\|f-g\|_{p^{\ast}}\leq\mathsf{M}_{p,q}(k)\inf_{g\in\mathscr{P}^{n}_{>k}}\|f-g\|_{q^{\ast}},$
(4)

where the conjugate exponent $r^{\ast}$ of $r\in[1,\infty]$ satisfies
$\frac{1}{r^{\ast}}+\frac{1}{r}=1$.

Again, the reverse of (4) holds with constant $1$. In the special case $k=0$,
inequality (4) becomes trivial with $\mathsf{M}_{p,q}(0)=1$ as both sides are
equal to $|\mathbb{E}f|$. When $k=1$, which corresponds to the dual of the
classical Khintchine inequality, we derive the following more precise formula
for the distance from the tail space $\mathscr{P}_{>1}^{n}$.

######  Theorem 2.

For every $1<r\leq\infty$ and $n\in\mathbb{N}$, every
$f:\\{-1,1\\}^{n}\to\mathbb{R}$ satisfies111Throughout the paper we shall use
standard asymptotic notation. For instance, $\xi\lesssim\eta$ (or
$\eta\gtrsim\xi)$ means that there exists a universal constant $c>0$ such that
$\xi\leq c\eta$ and $\xi\asymp\eta$ stands for
$(\xi\lesssim\eta)\wedge(\eta\lesssim\xi)$. We shall use subscripts of the
form $\lesssim_{t},\gtrsim_{t},\asymp_{t}$ when the implicit constant $c$
depends on some prespecified parameter $t$.

$\inf_{g\in\mathscr{P}^{n}_{>1}}\|f-g\|_{r}\asymp|\mathbb{E}f|+\max_{i\in\\{1,\ldots,n\\}}\big{|}\widehat{f}(\\{i\\})\big{|}+\sqrt{\frac{r-1}{r}}\Big{(}\sum_{i=1}^{n}\widehat{f}(\\{i\\})^{2}\Big{)}^{1/2}.$
(5)

This is the dual to a well-known result of Hitczenko [10] (see also [17, 11]),
obtaining $p$-independent upper and lower bounds for the $L_{p}$-norms of
Rademacher sums, where $p\in[1,\infty)$.

At this point, we should point out that in both Proposition 1 and Theorem 2,
the exponents of the norms are always strictly greater than 1. For instance,
choosing $f_{1}(x)=\sum_{i=1}^{n}x_{i}$, (4) gives

$\forall\
r\in(1,\infty],\qquad\inf_{g\in\mathscr{P}^{n}_{>k}}\|f_{1}-g\|_{r}\asymp_{r,k}\inf_{g\in\mathscr{P}^{n}_{>k}}\|f_{1}-g\|_{2}=\sqrt{n}.$
(6)

On the other hand, it follows from a result of Oleszkiewicz [19], which is the
main precursor to this work, that the $L_{1}$-distance of $f_{1}$ from the
$k$-th tail space satisfies

$\inf_{g\in\mathscr{P}^{n}_{>k}}\|f_{1}-g\|_{1}\asymp\min\\{k,\sqrt{n}\\},$
(7)

and thus exhibits a starkly different behavior as $n\to\infty$ from the
$L_{r}$ norms with $r>1$.

More generally, it is shown in [19] that for every $a_{1}\geq\cdots\geq
a_{n}\geq 0$, we have

$\inf_{g\in\mathscr{P}^{n}_{>k}}\|f_{\boldsymbol{a}}-g\|_{1}\asymp\min_{r\in\\{0,1,\ldots,n\\}}\bigg{\\{}\Big{(}\sum_{i=1}^{r}a_{i}^{2}\Big{)}^{1/2}+ka_{r+1}\bigg{\\}},$
(8)

where for $\boldsymbol{a}=(a_{1},\ldots,a_{n})$ we denote
$f_{\boldsymbol{a}}(x)=\sum_{i=1}^{n}a_{i}x_{i}$ and we make the convention
that $a_{n+1}=0$. The quantity appearing on the right hand side of (8) can be
rephrased in terms of the $\mathsf{K}$-functional of real interpolation (see
[1, Chapter 3]). Recall that if $(A_{0},A_{1})$ is an interpolation pair, then
the Lions–Peetre $\mathsf{K}$-functional is defined for every $t\geq 0$ and
$a\in A_{0}+A_{1}$ as

$\mathsf{K}(a,t;A_{0},A_{1})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\inf\big{\\{}\|a_{0}\|_{A_{0}}+t\|a_{1}\|_{A_{1}}:\
a=a_{0}+a_{1}\big{\\}}.$ (9)

It is elementary to check (see [12]), that if $a_{1}\geq\cdots\geq a_{n}\geq
0$ and $k\in\mathbb{N}$, then

$\min_{r\in\\{0,1,\ldots,n\\}}\bigg{\\{}\Big{(}\sum_{i=1}^{r}a_{i}^{2}\Big{)}^{1/2}+ka_{r+1}\bigg{\\}}\asymp\mathsf{K}(\boldsymbol{a},k;\ell_{2}^{n},\ell_{\infty}^{n}).$
(10)

Note that the right-hand side is invariant under permutations of the entries
of $\boldsymbol{a}$. The main result of this work is an appropriate extension
of the upper bound in Oleszkiewicz’s result (8) to polynomials of arbitrary
degree on the discrete hypercube.

######  Theorem 3.

For every $d\in\mathbb{N}$, there exists $\mathsf{C}_{d}\in(0,\infty)$ such
that for any $n\geq k\geq d$, every polynomial $f:\\{-1,1\\}^{n}\to\mathbb{R}$
of degree at most $d$ satisfies

$\inf_{g\in\mathscr{P}_{>k}^{n}}\|f-g\|_{1}\leq\mathsf{K}\big{(}\widehat{f},\mathsf{C}_{d}k^{d};\ell_{2}^{m},\ell_{\frac{2d}{d-1}}^{m}\big{)},$
(11)

where $\widehat{f}$ is the vector of Fourier coefficients of $f$, viewed as an
element of $\mathbb{R}^{m}$ with $m=\binom{n}{0}+\cdots+\binom{n}{d}$.

As was already pointed out by Oleszkiewicz, the method of [19] does not appear
to extend beyond Rademacher sums. Instead, in our proof we shall employ the
discrete _Bohnenblust–Hille_ inequality from approximation theory (see [2, 7,
6, 5]) along with a classical bound of Figiel on the Rademacher projection of
polynomials. A discussion concerning the size of the implicit constant
$\mathsf{C}_{d}$ appearing in (11) is postponed to Section 2 (see Remark 8
there).

Unlike the two-sided inequality (8), our bound (11) is only one-sided and as a
matter of fact there are examples in which it is far from optimal. In
particular, for functions which are permutationally symmetric, we obtain a
more accurate estimate. In what follows, we shall denote by
$T_{k}(x)=\sum_{\ell=0}^{k}c(k,\ell)x^{\ell}$ the $k$-th Chebyshev polynomial
of the first kind characterized by the property
$T_{k}(\cos\theta)=\cos(k\theta)$, where $\theta\in\mathbb{R}$. Moreover, we
shall use the ad hoc notation

$\tilde{c}(k,\ell)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\begin{cases}c(k,\ell),&\mbox{
if }k-\ell\mbox{ is even}\\\ c(k-1,\ell),&\mbox{ if }k-\ell\mbox{ is
odd}\end{cases}.$ (12)

For $\ell\in\\{1,\ldots,n\\}$, let $f_{\ell}$ be the $\ell$-th elementary
symmetric multilinear polynomial

$\forall\ x\in\\{-1,1\\}^{n},\qquad
f_{\ell}(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{\begin{subarray}{c}S\subseteq\\{1,\ldots,n\\}:\\\
|S|=\ell\end{subarray}}w_{S}(x).$ (13)

We have the following bound on the distance of symmetric polynomials from tail
spaces.

######  Theorem 4.

Let $n,k,d\in\mathbb{N}$ with $n\geq k\geq d$. Then, every symmetric
polynomial

$f=\sum_{\ell=0}^{d}\alpha_{\ell}f_{\ell}$ (14)

of degree at most $d$ on $\\{-1,1\\}^{n}$ satisfies

$\inf_{g\in\mathscr{P}_{>k}^{n}}\|f-g\|_{1}\leq\sum_{\ell=0}^{d}|\alpha_{\ell}||\tilde{c}(k,\ell)|.$
(15)

This bound can sometimes be reversed and, in particular, it gives a sharp
estimate as $n\to\infty$ for the $L_{1}$-distance of the elementary symmetric
polynomial $f_{d}$ from the $k$-th tail space.

######  Corollary 5.

For every $n,k,d\in\mathbb{N}$ with $n\geq k\geq d$, there exists
$\varepsilon_{n}(k,d)>0$ such that

$|\tilde{c}(k,d)|-\varepsilon_{n}(k,d)\leq\inf_{g\in\mathscr{P}_{>k}^{n}}\|f_{d}-g\|_{1}\leq|\tilde{c}(k,d)|$
(16)

and $\lim_{n\to\infty}\varepsilon_{n}(k,d)=0$.

The main motivation behind the work [19] was a question of Bogucki, Nayar and
Wojciechowski, asking to estimate the $L_{1}$-distance of the Rademacher sum
$f_{1}$ from the $k$-th tail space. Corollary 5 extends (at least
asymptotically in $n$) the answer given by Oleszkiewicz to all symmetric
homogeneous polynomials. We point out though that for $k=1$, (16) is sharper
than Oleszkiewicz’s bound (7) as $n\to\infty$, as (7) is tight only up to a
multiplicative constant.

### Acknowledgements

We are grateful to Krzysztof Oleszkiewicz for valuable discussions. H. Z. is
grateful to Institut de Mathématiques de Jussieu for the hospitality during a
visit in 2023.

##  2\. Proofs

We proceed to the proofs of our results. We start with the simple duality
argument leading to Proposition 1, variants of which will be used throughout
the paper.

###### Proof of Proposition 1.

Consider the identity operator acting as $\mathsf{id}(h)=h$ on a function of
the form $h:\\{-1,1\\}^{n}\to\mathbb{R}$. Then, the optimal constant
$\mathsf{M}_{p,q}(k)$ can be expressed as

$\mathsf{M}_{p,q}(k)=\big{\|}\mathsf{id}:(\mathscr{P}_{\leq
k}^{n},\|\cdot\|_{p})\to(\mathscr{P}_{\leq
k}^{n},\|\cdot\|_{q})\big{\|}=\big{\|}\mathsf{id}^{*}:(\mathscr{P}_{\leq
k}^{n},\|\cdot\|_{q})^{\ast}\to(\mathscr{P}_{\leq
k}^{n},\|\cdot\|_{p})^{\ast}\big{\|}$ (17)

by duality. Moreover, observe that since $(\mathscr{P}_{\leq
k}^{n},\|\cdot\|_{r})$ is a subspace of $L_{r}$, its dual is isometric to

$(\mathscr{P}_{\leq
k}^{n},\|\cdot\|_{r})^{\ast}=L_{r^{\ast}}\big{/}(\mathscr{P}_{\leq
k}^{n})^{\perp}=L_{r^{\ast}}\big{/}\mathscr{P}_{>k}^{n},$ (18)

where $A^{\perp}$ is the annihilator of $A$. Since it is also clear that
$\mathsf{id}^{*}=\mathsf{id}$, (17) concludes the proof. ∎

Using a theorem of Hitczenko [10] as input and the same duality, we deduce
Theorem 2.

###### Proof of Theorem 2.

The result of [10] asserts that if $\boldsymbol{a}=(a_{0},a_{1},\ldots,a_{n})$
and $f_{\boldsymbol{a}}(x)=a_{0}+\sum_{i=1}^{n}a_{i}x_{i}$,

$\|f_{\boldsymbol{a}}\|_{r^{\ast}}=\bigg{(}\mathbb{E}\Big{|}\sum_{i=0}^{n}a_{i}x_{i}\Big{|}^{r^{*}}\bigg{)}^{1/r^{*}}\asymp\mathsf{K}(\boldsymbol{a},\sqrt{r^{\ast}};\ell_{1}^{n+1},\ell_{2}^{n+1}),$
(19)

where $x_{0},x_{1},\ldots,x_{n}$ are independent Bernoulli random variables,
and the first equality holds due to symmetry. In other words, the linear
operator

$T:\big{(}\mathbb{R}^{n+1},\mathsf{K}(\cdot,\sqrt{r^{\ast}};\ell_{1}^{n+1},\ell_{2}^{n+1})\big{)}\to(\mathscr{P}_{\leq
1}^{n},\|\cdot\|_{r^{\ast}})$ (20)

given by $T{\boldsymbol{a}}=f_{\boldsymbol{a}}$ is an isomorphism, and thus
the same holds for its adjoint. Recalling that

$\mathsf{K}(\boldsymbol{a},\sqrt{r^{\ast}};\ell_{1}^{n+1},\ell_{2}^{n+1})=\inf\big{\\{}\|\boldsymbol{b}\|_{\ell_{1}^{n+1}}+\sqrt{r^{\ast}}\|\boldsymbol{c}\|_{\ell_{2}^{n+1}}:\
\boldsymbol{a}=\boldsymbol{b}+\boldsymbol{c}\big{\\}}$ (21)

and the duality between sums and intersections of normed spaces [1, Theorem
2.7.1], we see that the dual space of
$(\mathbb{R}^{n+1},\mathsf{K}(\cdot,\sqrt{r^{\ast}};\ell_{1}^{n+1},\ell_{2}^{n+1}))$
can be identified with

$\forall\
y\in\mathbb{R}^{n+1},\qquad\|y\|_{(\mathbb{R}^{n+1},\mathsf{K}(\cdot,\sqrt{r^{\ast}};\ell_{1}^{n+1},\ell_{2}^{n+1}))^{\ast}}=\max\Big{\\{}\|y\|_{\ell_{\infty}^{n+1}},\frac{\|y\|_{\ell_{2}^{n+1}}}{\sqrt{r^{\ast}}}\Big{\\}}.$
(22)

By Parseval’s identity, the action of the adjoint

$T^{\ast}:L_{r}\big{/}\mathscr{P}_{>1}^{n}\to(\mathbb{R}^{n+1},\mathsf{K}(\cdot,\sqrt{r^{\ast}};\ell_{1}^{n+1},\ell_{2}^{n+1}))^{\ast}$
(23)

is given by

$T^{\ast}(f+\mathscr{P}_{>1}^{n})=\big{(}\mathbb{E}f,\widehat{f}(\\{1\\}),\ldots,\widehat{f}(\\{n\\})\big{)}$
(24)

and thus the conclusion is equivalent to fact that $T^{\ast}$ is an
isomorphism. ∎

We now proceed to the proof of the general upper bound for polynomials given
in Theorem 3. The first ingredient for the proof is a discrete version of the
classical Bohnenblust–Hille inequality from approximation theory (see the
survey [7]) proven in [2, 6]. This asserts that for every $d\in\mathbb{N}$,
there exists a (sharp) constant $\mathsf{B}_{d}\in(0,\infty)$ such that for
any $n\geq d$, every polynomial $f:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree at
most $d$ satisfies

$\Big{(}\sum_{S\subseteq\\{1,\ldots,n\\}}|\widehat{f}(S)|^{\frac{2d}{d+1}}\Big{)}^{\frac{d+1}{2d}}\leq\mathsf{B}_{d}\|f\|_{\infty}.$
(25)

Moreover, $\frac{2d}{d+1}$ is the least exponent for which the implicit
constant becomes independent of the ambient dimension $n$. The best known
upper bound $B_{d}\leq\exp(C\sqrt{d\log d})$ for the constant $\mathsf{B}_{d}$
is due to the work of Defant, Mastyło and Pérez [6].

The level $\ell$-Rademacher projection of a function
$f:\\{-1,1\\}^{n}\to\mathbb{R}$ is defined as

$\forall\
x\in\\{-1,1\\}^{n},\qquad\mathrm{Rad}_{\ell}f(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{\begin{subarray}{c}S\subseteq\\{1,\ldots,n\\}:\\\
|S|=\ell\end{subarray}}\widehat{f}(S)w_{S}(x).$ (26)

Moreover, we write $\mathrm{Rad}_{\leq d}=\sum_{\ell\leq
d}\mathrm{Rad}_{\ell}$. Apart from the discrete Bohnenblust–Hille inequality
(25), we will also use a standard bound on the norm of the $\ell$-Rademacher
projections which is usually attributed to Figiel (see also [9, Section 3] for
a short proof).

######  Proposition 6.

Let $n\geq k\geq d$. Then, every function $f:\\{-1,1\\}^{n}\to\mathbb{R}$ of
degree at most $k$ satisfies

$\forall\ 0\leq\ell\leq
d,\qquad\big{\|}\mathrm{Rad}_{\ell}f\big{\|}_{\infty}\leq|\tilde{c}(k,\ell)|\
\|f\|_{\infty},$ (27)

and thus,

$\big{\|}\mathrm{Rad}_{\leq
d}f\big{\|}_{\infty}\leq\sum_{\ell=0}^{d}\big{\|}\mathrm{Rad}_{\ell}f\big{\|}_{\infty}\leq\sum_{\ell=0}^{d}|\tilde{c}(k,\ell)|\
\|f\|_{\infty},$ (28)

where $\tilde{c}(k,\ell)$ is given by (12). It is moreover known that
$|\tilde{c}(k,\ell)|\leq\frac{k^{\ell}}{\ell!}$.

Combining the above with Parseval’s identity, we deduce the following bound.

######  Lemma 7.

Let $n\geq k\geq d$. Then, every function $f:\\{-1,1\\}^{n}\to\mathbb{R}$ of
degree at most $k$ satisfies

$\max\big{\\{}\big{\|}\widehat{\mathrm{Rad}_{\leq
d}(f)}\big{\|}_{\ell_{2}^{m}},\sigma(k,d)^{-1}\big{\|}\widehat{\mathrm{Rad}_{\leq
d}(f)}\big{\|}_{\ell_{\frac{2d}{d+1}}^{m}}\big{\\}}\leq\inf_{g\in\mathscr{P}_{>d}^{n}\cap\mathscr{P}_{\leq
k}^{n}}\|f-g\|_{\infty},$ (29)

where $m=\binom{n}{0}+\cdots+\binom{n}{d}$ and
$\sigma(k,d)=\mathsf{B}_{d}\sum_{\ell=0}^{d}|\tilde{c}(k,\ell)|$.

###### Proof.

Fix a function $g\in\mathscr{P}_{>d}^{n}\cap\mathscr{P}_{\leq k}^{n}$. Then,

$\big{\|}\widehat{\mathrm{Rad}_{\leq
d}(f)}\big{\|}_{\ell_{2}^{m}}\leq\big{\|}\widehat{f}-\widehat{g}\big{\|}_{\ell_{2}^{M}}=\|f-g\|_{2}\leq\|f-g\|_{\infty},$
(30)

where $M=\binom{n}{0}+\cdots+\binom{n}{k}$. Moreover, we have

$\big{\|}\widehat{\mathrm{Rad}_{\leq
d}(f)}\big{\|}_{\ell_{\frac{2d}{d+1}}^{m}}\stackrel{{\scriptstyle\eqref{eq:bh}}}{{\leq}}\mathsf{B}_{d}\big{\|}\mathrm{Rad}_{\leq
d}(f)\big{\|}_{\infty}=\mathsf{B}_{d}\big{\|}\mathrm{Rad}_{\leq
d}(f-g)\big{\|}_{\infty}\stackrel{{\scriptstyle\eqref{eq:figiel}}}{{\leq}}\mathsf{B}_{d}\sum_{\ell=0}^{d}|\tilde{c}(k,\ell)|\
\|f-g\|_{\infty}.\hfill\qed$

Equipped with Lemma 7, we can complete the proof of Theorem 3.

###### Proof of Theorem 3.

Consider the normed spaces $X=(\mathscr{P}_{\leq k}^{n},\|\cdot\|_{\infty})$
and $Y=(\mathbb{R}^{m},\|\cdot\|_{Y})$ with

$\forall\
y\in\mathbb{R}^{m},\qquad\|y\|_{Y}=\max\big{\\{}\|y\|_{\ell_{2}^{m}},\sigma(k,d)^{-1}\|y\|_{\ell_{\frac{2d}{d+1}}^{m}}\big{\\}}$
(31)

and $m=\binom{n}{0}+\cdots+\binom{n}{d}$. Moreover, let
$Z=\mathscr{P}^{n}_{>d}\cap\mathscr{P}_{\leq k}^{n}\subset X$, viewed as a
normed subspace of $X$. Lemma 7 asserts that the linear operator $A:X/Z\to Y$
given by

$\forall\ f\in X,\qquad
A(f+Z)=\big{(}\widehat{f}(S)\big{)}_{\begin{subarray}{c}|S|\leq
d\end{subarray}}$ (32)

has norm $\|A\|\leq 1$. Therefore, the same holds for its adjoint
$A^{*}:Y^{*}\to(X/Z)^{*}$.

By the usual duality between sums and intersections of normed spaces [1,
Theorem 2.7.1], we see that the space $Y^{*}$ is isometric to

$\forall\
w\in\mathbb{R}^{m},\qquad\|w\|_{Y^{\ast}}=\mathsf{K}\big{(}w,\sigma(k,d);\ell_{2}^{m},\ell_{\frac{2d}{d-1}}^{m}\big{)}.$
(33)

Moreover, as $X/Z$ is a quotient of $X$, its dual is the subspace of
$X^{*}=L_{1}/\mathscr{P}^{n}_{>k}$ which is identified with the annihilator of
$Z$ inside $X^{\ast}$. In other words, it is the set

$(X/Z)^{\ast}=\big{\\{}f+\mathscr{P}_{>k}^{n}:\ \mathbb{E}[fg]=0\ \mbox{for
every }g\in Z\big{\\}}=\big{\\{}f+\mathscr{P}_{>k}^{n}:\ f\in\mathscr{P}_{\leq
d}^{n}\big{\\}}=\mathrm{span}(\mathscr{P}_{\leq
d}^{n}\cup\mathscr{P}_{>k}^{n})\big{/}\mathscr{P}_{>k}^{n}$ (34)

equipped with the $L_{1}$ quotient norm. Finally, for a sequence
$\boldsymbol{a}=(a_{S})_{|S|\leq d}\in Y^{\ast}$ and an equivalence class
$f+Z\in X/Z$, we have

$\langle\boldsymbol{a},A(f+Z)\rangle=\sum_{\begin{subarray}{c}S\subseteq\\{1,\ldots,n\\}:\\\
|S|\leq
d\end{subarray}}a_{S}\widehat{f}(S)=\Big{\langle}\sum_{\begin{subarray}{c}S\subseteq\\{1,\ldots,n\\}:\\\
|S|\leq
d\end{subarray}}a_{S}w_{S}+\mathscr{P}_{>k}^{n},f+Z\Big{\rangle}=\langle
A^{*}(\boldsymbol{a}),f+Z\rangle,$ (35)

where the first brackets $\langle\cdot,\cdot\rangle$ denote the duality in $Y$
and the following brackets denote the duality in $X/Z$. Therefore, we conclude
that

$\forall\ \boldsymbol{a}\in Y^{*},\qquad
A^{*}(\boldsymbol{a})=\sum_{\begin{subarray}{c}S\subseteq\\{1,\ldots,n\\}:\\\
|S|\leq d\end{subarray}}a_{S}w_{S}+\mathscr{P}_{>k}^{n}$ (36)

and thus, the condition $\|A^{*}\|\leq 1$ means that for any
$f:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree at most $d$,

$\inf_{g\in\mathscr{P}_{>k}^{n}}\|f-g\|_{1}=\big{\|}A^{*}\big{(}\widehat{f}\big{)}\big{\|}_{(X/Z)^{*}}\leq\big{\|}\widehat{f}\big{\|}_{Y^{*}}=\mathsf{K}\big{(}\widehat{f},\sigma(k,d);\ell_{2}^{m},\ell_{\frac{2d}{d-1}}^{m}\big{)}.$
(37)

Finally, since

$\sigma(k,d)\leq\mathsf{B}_{d}\sum_{\ell=0}^{d}|\tilde{c}(k,\ell)|\leq\mathsf{B}_{d}\sum_{\ell=0}^{d}\frac{k^{\ell}}{\ell!}\leq
e\mathsf{B}_{d}k^{d},$ (38)

we deduce the conclusion of the theorem with $\mathsf{C}_{d}=e\mathsf{B}_{d}$.
∎

######  Remark 8.

To the best of our knowledge, there are no nonconstant lower bounds on the
size of the discrete Bohnenblust–Hille constant $\mathsf{B}_{d}$, so it is
even conceivable that the constant $\mathsf{C}_{d}$ in (11) can be chosen to
be independent of $d$.

######  Remark 9.

A duality argument similar to that employed for Theorem 3 shows that for every
$d\in\mathbb{N}$, the constant $\mathsf{B}_{d}$ in inequality (25) is also the
least constant for which every function $f:\\{-1,1\\}^{n}\to\mathbb{R}$, where
$n\geq d$, satisfies

$\inf_{g\in\mathscr{P}_{>d}^{n}}\|f-g\|_{1}\leq\mathsf{B}_{d}\bigg{(}\sum_{\begin{subarray}{c}S\subseteq\\{1,\ldots,n\\}:\\\
|S|\leq
d\end{subarray}}|\widehat{f}(S)|^{\frac{2d}{d-1}}\bigg{)}^{\frac{d-1}{2d}}.$
(39)

######  Remark 10.

It was pointed out to us by Oleszkiewicz that the main result (8) of [19] also
admits a dual formulation. Namely, for every
$\boldsymbol{a}=(a_{1},\ldots,a_{n})\in\mathbb{R}^{n}$, we have

$\inf\big{\\{}\|f_{\boldsymbol{a}}-g\|_{\infty}:\
g\in\mathscr{P}_{\\{0\\}\cup\\{2,\ldots,k\\}}^{n}\big{\\}}\asymp\max\Big{\\{}\|\boldsymbol{a}\|_{\ell_{2}^{n}},\frac{\|\boldsymbol{a}\|_{\ell_{1}^{n}}}{k}\Big{\\}}.$
(40)

This can be proven using similar ideas as in the proof of Theorem 3.

A slight variant of the arguments above also yields Theorem 4 for symmetric
functions.

###### Proof of Theorem 4.

Let $f$ be a symmetric function of the form
$f=\sum_{\ell=0}^{d}\alpha_{\ell}f_{\ell}$ where $f_{\ell}$ is the $\ell$-th
elementary symmetric polynomial. Then, the Hahn–Banach theorem gives

$\inf_{g\in\mathscr{P}_{>k}^{n}}\|f-g\|_{1}=\sup_{0\neq h\in\mathscr{P}_{\leq
k}^{n}}\frac{\mathbb{E}[fh]}{\|h\|_{\infty}}.$ (41)

Observe now that we can write

$\mathbb{E}[fh]=\sum_{\ell=0}^{d}\alpha_{\ell}\mathbb{E}[f_{\ell}h]=\sum_{\ell=0}^{d}\alpha_{\ell}\sum_{\begin{subarray}{c}S\subseteq\\{1,\ldots,n\\}:\\\
|S|=\ell\end{subarray}}\widehat{h}(S)=\sum_{\ell=0}^{d}\alpha_{\ell}\mathrm{Rad}_{\ell}h(1,\ldots,1).$
(42)

Thus, by Figiel’s bound (27),

$\mathbb{E}[fh]\leq\sum_{\ell=0}^{d}|\alpha_{\ell}|\
\|\mathrm{Rad}_{\ell}h\|_{\infty}\leq\sum_{\ell=0}^{d}|\alpha_{\ell}||\tilde{c}(k,\ell)|\
\|h\|_{\infty}$ (43)

and the desired inequality follows from (41). ∎

Equipped with Theorem 4, we present the proof of Corollary 5.

###### Proof of Corollary 5.

The upper bound in (16) follows immediately from Theorem 4. For the lower
bound, consider the auxiliary symmetric function
$H_{k,n}:\\{-1,1\\}^{n}\to\mathbb{R}$ given by

$\forall\ x\in\\{-1,1\\}^{n},\qquad
H_{k,n}(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}T_{k}\left(\frac{x_{1}+\cdots+x_{n}}{n}\right)=\sum_{\ell=0}^{k}\beta_{\ell,k,n}\
f_{\ell}(x),$ (44)

where $f_{\ell}$ is the $\ell$-th elementary symmetric polynomial, and notice
that $H_{k,n}$ has degree at most $k$. As $T_{k}(x)$ is odd or even when $k$
is odd or even respectively, it follows that $\beta_{\ell,k,n}=0$ if $k-\ell$
is odd. We distinguish two cases depending on the parity of $k-d$.

$\bullet$ Suppose that $k-d$ is even and consider the function
$\varphi_{d,k,n}:\\{-1,1\\}^{n}\to\mathbb{R}$ given by

$\forall\
x\in\\{-1,1\\}^{n},\qquad\varphi_{d,k,n}(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{0\leq\ell\leq
d:\ 2|d-\ell}\mathrm{sign}(\beta_{\ell,k,n})f_{\ell}(x)$ (45)

that is also symmetric and of degree at most $d$. Then, on one hand we know
that

$\inf_{g\in\mathscr{P}_{>k}^{n}}\|\varphi_{d,k,n}-g\|_{1}\stackrel{{\scriptstyle\eqref{eq:sym}}}{{\leq}}\sum_{0\leq\ell\leq
d:\ 2|d-\ell}|\tilde{c}(k,\ell)|=\sum_{0\leq\ell\leq d:\
2|d-\ell}|c(k,\ell)|.$ (46)

On the other hand, we have the following lower estimate,

$\inf_{g\in\mathscr{P}_{>k}^{n}}\|\varphi_{d,k,n}-g\|_{1}\stackrel{{\scriptstyle\eqref{eq:hb}}}{{=}}\sup_{0\neq
h\in\mathscr{P}_{\leq
k}^{n}}\frac{\mathbb{E}[\varphi_{d,k,n}h]}{\|h\|_{\infty}}\geq\frac{|\mathbb{E}[\varphi_{d,k,n}H_{k,n}]|}{\|H_{k,n}\|_{\infty}}.$
(47)

By definition, $\|H_{k,n}\|_{\infty}\leq\sup_{x\in[-1,1]}|T_{k}(x)|\leq 1$ and
$H_{k,n}(1,\ldots,1)=T_{k}(1)=1$. Therefore,

$\begin{split}\inf_{g\in\mathscr{P}_{>k}^{n}}\|\varphi_{d,k,n}-g\|_{1}\geq|\mathbb{E}[\varphi_{d,k,n}H_{k,n}]|&=\bigg{|}\sum_{0\leq\ell\leq
d:\
2|d-\ell}\mathrm{sign}(\beta_{\ell,k,n})\mathrm{Rad}_{\ell}H_{k,n}(1,\dots,1)\bigg{|}\\\
&=\sum_{0\leq\ell\leq d:\
2|d-\ell}\left|\mathrm{Rad}_{\ell}H_{k,n}(1,\dots,1)\right|.\end{split}$ (48)

To further estimate this sum, we use [14, Lemma 27] which implies that there
exists a positive constant $\varepsilon_{n}(k,d)>0$ with
$\varepsilon_{n}(k,d)=O_{k,d}(1/n)$ as $n\to\infty$, such that

$\sum_{0\leq\ell\leq d:\
2|d-\ell}\left|\mathrm{Rad}_{\ell}H_{k,n}(1,\dots,1)\right|\geq\sum_{0\leq\ell\leq
d:\ 2|d-\ell}|c(k,\ell)|-\varepsilon_{n}(k,d).$ (49)

Hence, combining the above we conclude that

$\inf_{g\in\mathscr{P}_{>k}^{n}}\|\varphi_{d,k,n}-g\|_{1}\geq\sum_{0\leq\ell\leq
d:\ 2|d-\ell}|c(k,\ell)|-\varepsilon_{n}(k,d).$ (50)

Finally, to bound from below the $L_{1}$-distance of $f_{d}$ from the tail
space, we write (putting $\varphi_{0,k,n}=\varphi_{-1,k,n}\equiv 0$)

$f_{d}=\mathrm{sign}(\beta_{d,k,n})(\varphi_{d,k,n}-\varphi_{d-2,k,n})$ (51)

and using the triangle inequality, we get

$\begin{split}\inf_{g\in\mathscr{P}_{>k}^{n}}&\left\|f_{d}-g\right\|_{1}\geq\inf_{g\in\mathscr{P}_{>k}^{n}}\left\|\varphi_{d,k,n}-g\right\|_{1}-\inf_{g\in\mathscr{P}_{>k}^{n}}\left\|\varphi_{d-2,k,n}-g\right\|_{1}\\\
&\stackrel{{\scriptstyle\eqref{ubb}\wedge\eqref{ineq:
sharp2}}}{{\geq}}\sum_{0\leq\ell\leq d:\
2|d-\ell}|c(k,\ell)|-\varepsilon_{n}(k,d)-\sum_{0\leq\ell\leq d-2:\
2|d-2-\ell}|c(k,\ell)|=|c(k,d)|-\varepsilon_{n}(k,d),\end{split}$ (52)

thus concluding the proof of the lower bound in (16).

$\bullet$ If $k-d$ is odd, we use the identity (putting
$\varphi_{0,k,n}=\varphi_{-1,k,n}=\varphi_{d,-1,n}\equiv 0$)

$f_{d}=\mathrm{sign}(\beta_{d,k-1,n})(\varphi_{d,k-1,n}-\varphi_{d-2,k-1,n}).$
(53)

The rest of the argument is identical. ∎

######  Remark 11.

In this paper, we studied dual versions of moment comparison estimates on the
hypercube (3) and investigated the endpoint case of their duals (4) for
polynomials. By formal reasoning similar to the proof of Proposition 1, one
can derive dual versions of various other polynomial inequalities, including
Bernstein–Markov inequalities and their reverses and bounds for the action of
the heat semigroup. We refer to [8] for a systematic treatment of such
estimates.

## References

  * [1] Jöran Bergh and Jörgen Löfström.  Interpolation spaces. An introduction, volume No. 223 of Grundlehren der Mathematischen Wissenschaften.  Springer-Verlag, Berlin-New York, 1976.
  * [2] Ron Blei.  Analysis in integer and fractional dimensions, volume 71 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2001.
  * [3] Aline Bonami.  Étude des coefficients de Fourier des fonctions de $L^{p}(G)$.  Ann. Inst. Fourier (Grenoble), 20(fasc. 2):335–402 (1971), 1970\.
  * [4] Jean Bourgain.  Walsh subspaces of $L^{p}$-product spaces.  In Seminar on Functional Analysis, 1979–1980 (French), pages Exp. No. 4A, 9. École Polytech., Palaiseau, 1980.
  * [5] Andreas Defant, Domingo García, Manuel Maestre, and Pablo Sevilla-Peris.  Dirichlet series and holomorphic functions in high dimensions, volume 37 of New Mathematical Monographs.  Cambridge University Press, Cambridge, 2019.
  * [6] Andreas Defant, Mieczysław Mastyło, and Antonio Pérez.  On the Fourier spectrum of functions on Boolean cubes.  Math. Ann., 374(1-2):653–680, 2019.
  * [7] Andreas Defant and Pablo Sevilla-Peris.  The Bohnenblust-Hille cycle of ideas from a modern point of view.  Funct. Approx. Comment. Math., 50(1, [2013 on table of contents]):55–127, 2014.
  * [8] Alexandros Eskenazis and Paata Ivanisvili.  Polynomial inequalities on the Hamming cube.  Probab. Theory Related Fields, 178(1-2):235–287, 2020.
  * [9] Alexandros Eskenazis and Paata Ivanisvili.  Learning low-degree functions from a logarithmic number of random queries.  In STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 203–207. ACM, New York, [2022] ©2022.
  * [10] Paweł Hitczenko.  Domination inequality for martingale transforms of a Rademacher sequence.  Israel J. Math., 84(1-2):161–178, 1993.
  * [11] Paweł Hitczenko and Stanisław Kwapień.  On the Rademacher series.  In Probability in Banach spaces, 9 (Sandjberg, 1993), volume 35 of Progr. Probab., pages 31–36. Birkhäuser Boston, Boston, MA, 1994.
  * [12] Tord Holmstedt.  Interpolation of quasi-normed spaces.  Math. Scand., 26:177–199, 1970.
  * [13] Paata Ivanisvili and Tomasz Tkocz.  Comparison of moments of Rademacher chaoses.  Ark. Mat., 57(1):121–128, 2019.
  * [14] Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, and Amir Yehudayoff.  Tight bounds on the Fourier growth of bounded functions on the hypercube.  ECCC 2021, Preprint available at https://arxiv.org/abs/2107.06309, 2021.
  * [15] Aleksandr Khintchine.  Über dyadische Brüche.  Math. Z., 18(1):109–116, 1923.
  * [16] Niv Levhari and Alex Samorodnitsky.  Hypercontractive inequalities for the second norm of highly concentrated functions, and Mrs. Gerber’s-type inequalities for the second Rényi entropy.  Entropy, 24(10):Paper No. 1376, 27, 2022.
  * [17] Stephen J. Montgomery-Smith.  The distribution of Rademacher sums.  Proc. Amer. Math. Soc., 109(2):517–522, 1990.
  * [18] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, New York, 2014.
  * [19] Krzysztof Oleszkiewicz.  On mimicking Rademacher sums in tail spaces.  In Geometric aspects of functional analysis, volume 2169 of Lecture Notes in Math., pages 331–337. Springer, Cham, 2017.


# A Relational Inductive Bias for Dimensional Abstraction in Neural Networks

Declan Campbell 1 Jonathan D. Cohen 1, 2
1 Princeton Neuroscience Institute
2 Princeton University Department of Psychology

###### Abstract

The human cognitive system exhibits remarkable flexibility and generalization
capabilities, partly due to its ability to form low-dimensional, compositional
representations of the environment. In contrast, standard neural network
architectures often struggle with abstract reasoning tasks, overfitting, and
requiring extensive data for training. This paper investigates the impact of
the relational bottleneck—a mechanism that focuses processing on relations
among inputs—on the learning of factorized representations conducive to
compositional coding and the attendant flexibility of processing. We
demonstrate that such a bottleneck not only improves generalization and
learning efficiency, but also aligns network performance with human-like
behavioral biases. Networks trained with the relational bottleneck developed
orthogonal representations of feature dimensions latent in the dataset,
reflecting the factorized structure thought to underlie human cognitive
flexibility. Moreover, the relational network mimics human biases towards
regularity without pre-specified symbolic primitives, suggesting that the
bottleneck fosters the emergence of abstract representations that confer
flexibility akin to symbols.

Keywords: Abstraction, Neural Networks, Reasoning

## Introduction

The flexibility and generativity of human cognition has been the focus of
intense research in cognitive science and machine learning. Fodor Pylyshyn
(1988) famously proposed that this depends on the property of compositionality
supported by symbolic processing which, they argued, was not supported by
neural network architectures. In contrast, a strong focus and much of the
success of early neural network architectures (McClelland ., 1986; Rumelhart
McClelland, 1986), as well as modern forms of deep learning (LeCun ., 2015),
has been on the ability to implement sophisticated forms of statistical
learning. In addition to achieving powerful forms of function approximation,
these architectures have been shown to achieve capabilities traditionally
associated with symbolic processing (Rogers McClelland, 2004), including the
ability of transformer-based, large-language models to solve challenging
analogical reasoning tasks (T. Webb ., 2023). Nevertheless: a) these models
fail on other forms of abstract reasoning tasks on which humans succeed
(Mitchell ., 2023); b) they require amounts of data and training that are far
in excess of what people require to achieve comparable performance (Mnih .,
2015); and c) at best, it is unclear whether they make use of the same kinds
of low dimensional, highly abstract, compositional (and, in the limit,
genuinely symbolic) forms of representation that Fodor and Pylyshyn had in
mind.

Interestingly, it has recently been shown that introducing simple inductive
biases to standard neural network architectures can promote the efficient
learning of and flexible use of abstract representations and, in some cases,
the emergence of genuinely symbolic forms of processing (TW. Webb ., 2020;
Kerg ., 2022; Altabaa ., 2023). These inductive biases implement a form of
relational bottleneck: a processing component that restricts the flow of
information to relations among the inputs (TW. Webb ., 2023), upon which
further processing is based. This isolation between processing of the data and
processing that is restricted to only relational information inherent in the
data forces the latter to learn abstract representations, and functions that
use these, that can be generalized to new, never seen inputs that exhibit the
same relations.

One corollary of the idea that a relational bottleneck can induce the learning
of abstract representations is that this should be facilitated by
representation of data in a compositional form — that is, factorized in a form
that the relational structure is most apparent. The learning of such
factorized representations are a requisite for compositional coding. One
example of such factorization that has been an important goal of research on
deep learning (Higgins ., 2016; Kim Mnih, 2018) is the learning of dimensional
structure that may exist in the data (e.g., the color, size, and brightness of
visual images). Here, we explore the possibility that the relational
bottleneck can play an important role in promoting the learning of such
representations. Specifically, we test the hypothesis that, insofar as
factorized representations of distinct, task-relevant feature dimensions make
learning relations easier, then imbuing a network with a relational bottleneck
may put pressure on the network to learn such representations, improving
generalization performance on relational tasks, and better aligning network
performance with human behavioral biases.

To test this hypothesis, we focused on the learning of similarity relations
using the simplest form of a relational bottleneck, which can be implemented
in a contrastive network. Specifically, we implemented two standard multilayer
perceptron (MLP) pathways with shared encoder weights (as input streams for
the two items to be compared), that converged on a layer in which the distance
(e.g., cosine similarity) was computed between pairs of embeddings. This was
used to evaluate the similarity between the embeddings in each input stream,
that was taken as the response. The network was trained to produce the correct
response (i.e., how similar the two inputs were) for each pair of stimuli.
This implementation of the relational bottleneck is comparable to the CoRelNet
architecture described by Kerg . (2022). We compared the performance of this
network, and the representations it learned, with a standard feedforward
neural network that lacked a relational bottleneck (i.e., the direct
similarity computation).

We carried out two sets of simulations to evaluate these networks. In the
first, we evaluated the extent to which they developed orthogonal (factorized)
representations of distinct feature dimensions in the embedding layers, using
a training dataset comprised of features that varied along two orthogonal
dimensions. In the second set of simulations, we extended the approach to a
richer feature space of geometric forms previously generated using symbolic
primitives, and tested the extent to which the networks captured the
difference between performance of humans and non-humans that has previously
been explained using models explicitly imbued with symbolic primitives
(Dehaene ., 2022; Sablé-Meyer ., 2021, 2022).

## Relational Bottleneck and Dimensional Representations

Our initial investigation focused on a simple similarity judgment task, to
evaluate the extent to which a relational bottleneck induced the learning of
factorized representations of two orthogonal feature dimensions in its
embeddings. In contrast to existing unsupervised methods for learning
factorized representations (Higgins ., 2016; Kim Mnih, 2018), we used a
contrastive loss function that measures the relation (distance) between pairs
of inputs within the metric space defined by the dataset’s latent features. We
show that this approach encourages the model to learn “factorized”
representations of the task features. We then investigate the degree to which
this factorization contributes to learning and generalization.

### Methods

#### Networks

We compared two simple forms of feedforward neural networks that differed only
in how they computed stimulus similarity (Fig. 1). For the relational model,
we implemented a simple form of the relational bottleneck (comparable to Kerg
. (2022); Altabaa . (2023)), in which similarity was computed directly as the
Euclidean distance between pairs of embeddings learned by the encoding layers;
this was then used to determine the response (red pathway in Fig. 1). We
compared this to a standard feedforward network, without any explicit
similarity computation, in which the encoding layer projected to a multilayer
perceptron (MLP) that generated the response (blue pathway in Fig. 1).

Figure 1: Network Architecture Feedforward networks used to perform identity
and similarity judgement tasks over two input stimuli (see text).

#### Task and training data

The task involved making similarity judgements over pairs of inputs that
varied parametrically along two orthogonal dimensions. The inputs were pairs
of grayscale images depicting geometric forms in which size and luminosity
varied parametrically and independently across pairs (in the Appendix, we
report similar results for the case in which features of the inputs were
encoded as one-hots, rather than varying parametrically).

### Results

First we examined both the rate at which the two networks learned to perform
the task, and at which out of distribution (OOD) generalization improved —
that is how quickly they learned to generalize performance to stimuli that
were not only held out of the training corpus but that had feature values
outside the range of those used in the training corpus. We found that that the
relational network both learned to master the training data and exhibit OOD
generalization substantially faster than the standard network (Fig. 2a). Next,
we examined the structure of the representations learned in the encoding
layers of the networks using PCA. Fig. 2b shows that the relational network
learned orthogonal representations of the two feature dimensions, but that
this was not the case for the standard network. These findings clearly
indicate that imposing a simple form of the relational bottleneck in a
standard feedforward network not only improves sample efficiency and the rate
at which OOD generalization is achieved, but also imposes factorial structure
on the representations learned immediately prior to the bottleneck — a form of
representation that is fundamental to compositional coding and that is known
to be a feature of, and fundamental to the flexibility of human cognitive
function. In the next set of simulations, we more directly examined the extent
to which the relational bottleneck reproduces empirical observations about
biases in human similarity judgments.

Figure 2: (a) Learning curves for training loss and generalization performance
indicate that the relational architecture learns more rapidly than the
feedforward architecture. (b) 2-dimension PCA of network embeddings learned by
each network. Note that relational network learns orthogonal representations
for each dimension, whereas the feed-forward network learns a non-linear
manifold.

## Dimensional Representations Align with Human Behavior

Here, we examined the extent to which the relational bottleneck can explain
findings in human performance reflecting biases towards regularity (e.g.,
symmetry and parallelism) in geometric figures, and that have previously been
hypothesized to reflect the presence of pre-specified symbolic representations
(Sablé-Meyer ., 2021). To do so, we trained the network described above
(Figure 1a, red pathway) on an oddball detection task involving simple
quadrilateral figures, used in Sablé-Meyer . (2021) to compare the performance
of humans to non-human primates and artificial agents. That study was offered
as evidence not only that humans exhibit a regularity bias in processing
geometric figures that is not observed in non-human primates, but also that
this bias can be captured by models that are explicitly imbued with pre-
specified symbolic primitives but not standard deep learning neural networks
that are trained directly on the images. Here, we tested whether a network
imbued with a relational bottleneck — but not any symbolic primitives — could
reproduce the regularity bias observed in humans.

### Methods

The relational network described above (Fig. 1, red pathway) and SimCLR — a
standard contrastive learning method, implemented here using a ResNet encoder
— were trained and tested on approximately $60,000$ trials using the same
stimuli and following the same protocol used with humans and non-human
primates in Sablé-Meyer . (2021). On each trial during the test phase, each
network was presented with six images of quadrilateral figures, five of which
were symmetric and identical in shape but varied in size and/or rotation, and
one of which — the “oddball” — was different in shape (Fig. 3). The oddballs
were constructed by perturbing the bottom right vertex of the reference shape
to violate its regularity in the same way as in Sablé-Meyer . (2021). For each
trial, we extracted the embedding in the model for each of the six images, and
used these to identify the oddball as the one that was furthest from the
centroid of the set (defined as the mean of the embeddings). We then computed
the average error rate for each shape category and correlated the model error
rates with the human and non-human primate error rates.

Figure 3: Oddball construction & trial structure Stimuli consisted of
quadrilateral forms varying in their regularity/symmetry. Each trial was
comprised of five variants of the same stimulus varying only in size and
rotation, and one ”oddball” stimulus constructed by perturbing the bottom
right vertex of the reference stimulus to violate its regularity. Participants
and networks were evaluated on their accuracy in identifying the oddballs.
Figure 4: Relational Network and SimCLR performance on oddball task: (a) Error
rates for the relational network and SimCLR at representative points during
training. Note that the relational network’s error rates exhibit a positive
slope as a function of decreasing geometric regularity, consistent with human
performance on this task, while the SimCLR network displays no sensitivity to
geometric regularity. (b) Correlation coefficients between the model error
rates and human and baboon error rates. Note that SimCLR most closely
resembles baboon performance on this task while the relational network most
closely corresponds with the human error rates. (c) t-SNE plot of reference
shape embeddings from the relational network colored according to stimulus
regularity calculated as the sum of the binary symbolic properties for each
stimulus.

### Results

We found that the network exhibited a pattern of performance as a function of
both learning and regularity of shapes that closely resembled that observed by
Sablé-Meyer . (2021) for humans but not for non-human primates (Fig. 4a-b).
The network exhibited this pattern despite the fact that it was not endowed
with any pre-specified symbolic primitives, nor any specific inputs that would
have made these easier to discover. Rather, the results are attributable to
the presence of the relational bottleneck, which has been shown in other
settings to predispose to the discovery of low dimensional, abstract
representations that can function as symbols (TW. Webb ., 2020; Kerg ., 2022;
Altabaa ., 2023). Moreover, these biases towards human-like performance on
this task emerge early during learning and are persistent over the course of
network training (Fig. 4c). The relational training scheme yielded networks
that learned well structured representations of the underlying category
structure of the task (Fig 4d). While standard contrastive training has also
been shown to produce networks sensitive to category information, our
objective was to instead evaluate the degree of representational factorization
within both relational and standard contrastive network architectures.

To do so, we assessed whether features associated with stimulus regularity
were distinctly encoded in the network embeddings by applying linear
regression models on the first 50 principal components of the networks’
embeddings using 20-fold cross validation. The results indicated a more robust
representation of stimulus regularity in the relational network ($R^{2}=0.89$)
compared to the standard contrastive model ($R^{2}=0.68$). Notably, these
findings were observed despite the fact that classifiers more accurately
predicted the stimulus category from the standard contrastive networks’
representations compared to the relational network representations ($92\%$ and
$86\%$, respectively). This suggests that the improved decoding of stimulus
regularity in the relational network is not due to a clearer representation of
stimulus category, and is instead a product of the network’s tendency to
encode features along implicitly factorized and more linearly separable
subspaces within the relational networks’ embeddings.

## Discussion

Low dimensional, factorized representations that can be used compositionally
are generally thought to be a foundational requirement on which the
flexibility of computation exhibited by humans is built. Most models that seek
to describe such forms of computation have either used traditional symbolic
processing mechanisms (Anderson, 2013; Newell, 1994) or have explicitly imbued
neural networks with pre-specified symbolic primitives over which they can
operate (Garcez ., 2002). Some neural network models have used unsupervised
learning coupled with specialized loss functions (Higgins ., 2016; Kim Mnih,
2018), but these require sensitive hyper-parameter tuning to discover
dimensional structure. Another approach has been to supply the latent factors
as fully supervised training targets with generative models (Tran ., 2017).
Our method provides an intermediate form of supervision between unsupervised
and fully supervised methods. By using a scalar similarity target that
implicitly captures the task’s relational structure along the relevant
dimensions, it implements a simple relational bottleneck (TW. Webb ., 2023)
that, in turn, encourages the emergence of factorized representations, without
explicitly providing them as targets. This approach affords the network the
benefits of encoding task relevant features in its embeddings, while also
remaining flexible enough to encode other features that may be relevant to the
performance of other downstream tasks.

This method may also better account for how children construct factorized
representations of their environments by receiving signals about the
similarity structure of the world, either from cues in the environment or from
explicit instruction by teachers and/or parents (Markman Hutchinson, 1984;
Gelman Markman, 1986). Given the constancy of objects implicit in real-world
environments, viewing these objects under multiple viewing conditions and in
contrast to distinct objects may help carve out representations that factorize
the relevant dimensions of variation. Furthermore, explicit instruction about
the similarity of novel objects compared to known ones may implicitly provide
information about the dimensional structure of the world that further
facilitates factorization that can be exploited by architectures that include
a form of relational bottleneck. In this way, agents may learn factorized
representations of latent features without requiring explicit instruction
about all of the particular features of the relevant stimuli. Instead, a
training signal providing rich information about the similarity of objects in
combination with the appropriate mechanisms for computing relations may be
sufficient to leverage this comparatively weak form of supervision to learn
factorized representations.

Furthermore, if an agent’s experience does not encompass a sufficiently rich
sampling of the underlying feature space, as is often the case in many
naturalistic learning settings, relational architectures may insulate agents
from the risks of overfitting that are common in more traditional
architectures (Srivastava ., 2014; Goodfellow ., 2016). This protective effect
is especially pronounced in environments where latent features are
categorical, and stimuli consist of various combinations of these categorical
features (see Supplementary information for a more detailed consideration and
examples of this point). In cases of sparse feature sampling, traditional
neural networks tend to overfit by picking up on spurious correlations across
independent feature dimensions. Relational bottleneck models, however, are
more resistant to this, thereby reducing the likelihood of overfitting in such
situations TW. Webb ., 2023. Moreover, the benefits of relational processing
in promoting generalization and rapid learning are not only present in simple
representation learning tasks as tested in the simulations reported here, but
also across a range of challenging visual reasoning and analogy tasks (Mondal
., 2023; TW. Webb ., 2020).

Previous work has demonstrated how augmenting neural networks with an explicit
mechanism for computing relations provides substantial benefits in learning
efficiency and generalization in navigational tasks (Whittington ., 2020) and
in basic reasoning tasks (Altabaa ., 2023; TW. Webb ., 2020), approaching the
sample efficiency and generalization abilities of human learners in these
domains. Here, we show that these same computational elements may favor the
formation of factorized upstream representations, that facilitate the
discovery of relational structure.

This architecture may also provide structural/mechanistic insights into human
brain function. Several studies have indicated that regions of the medial
temporal lobe and hippocampus play an important role in navigation by
providing a mechanism for binding features (Whittington ., 2020) and computing
the similarity of the current state with those stored in memory (Norman
O’Reilly, 2003; O’Reilly McClelland, 1994). Such machinery for estimating
similarity relations among distinct representations may provide a powerful
architectural inductive bias not just useful memory retrieval, but also for
factorizing representations. This hypothesis is consistent with recent
evidence suggesting that regions that provide direct input to the hippocampus
such as the entorhinal cortex encode highly factorized representations of
space, time, and other cognitive variables (Fyhn ., 2004; Aronov ., 2017;
Constantinescu ., 2016; Chandra ., 2023). The work reported here provides one
account for why these representations may emerge in regions providing input to
the hippocampus. Furthermore, the framework suggests that other structures and
mechanisms in the brain, that have similar functional attributes, may support
relational abstraction and representational factorization in other domains
(for example, the cerebellum and parietal cortex in the domain of motor
function (Ravizza ., 2006; D’Mello ., 2020; McDougle ., 2022)).

## Conclusion

Our findings extend previous work, which has demonstrated that the use of a
relational bottleneck (TW. Webb ., 2023) can induce a network to learn
abstract rules and use these for extreme forms of generalization (TW. Webb .,
2020; Kerg ., 2022; Altabaa ., 2023). We show that the same inductive bias can
induce the system to discover factorized, compositional representations of
feature dimensions relevant to task performance in a data efficient manner,
and in a form that approximates the efficiency of coding and flexibility of
processing exhibited by the human brain.

## References

  * Altabaa . (2023) altabaa2023abstractorsAltabaa, A., Webb, T., Cohen, J. Lafferty, J.  2023\.  Abstractors: Transformer Modules for Symbolic Message Passing and Relational Reasoning Abstractors: Transformer modules for symbolic message passing and relational reasoning.  arXiv preprint arXiv:2304.00195.
  * Anderson (2013) anderson2013adaptiveAnderson, JR.  2013\.  The adaptive character of thought The adaptive character of thought.  Psychology Press.
  * Aronov . (2017) aronov2017mappingAronov, D., Nevers, R. Tank, DW.  2017\.  Mapping of a non-spatial dimension by the hippocampal–entorhinal circuit Mapping of a non-spatial dimension by the hippocampal–entorhinal circuit.  Nature5437647719–722.
  * Chandra . (2023) chandra2023highChandra, S., Sharma, S., Chaudhuri, R. Fiete, I.  2023\.  High-capacity flexible hippocampal associative and episodic memory enabled by prestructured”spatial”representations High-capacity flexible hippocampal associative and episodic memory enabled by prestructured”spatial”representations.  bioRxiv2023–11.
  * Constantinescu . (2016) constantinescu2016organizingConstantinescu, AO., O’Reilly, JX. Behrens, TE.  2016\.  Organizing conceptual knowledge in humans with a gridlike code Organizing conceptual knowledge in humans with a gridlike code.  Science35262921464–1468.
  * Dehaene . (2022) dehaene2022symbolsDehaene, S., Al Roumi, F., Lakretz, Y., Planton, S. Sablé-Meyer, M.  2022\.  Symbols and mental programs: a hypothesis about human singularity Symbols and mental programs: a hypothesis about human singularity.  Trends in Cognitive Sciences.
  * D’Mello . (2020) d2020evidenceD’Mello, AM., Gabrieli, JD. Nee, DE.  2020\.  Evidence for hierarchical cognitive control in the human cerebellum Evidence for hierarchical cognitive control in the human cerebellum.  Current Biology30101881–1892.
  * Fodor Pylyshyn (1988) fodor1988connectionismFodor, JA. Pylyshyn, ZW.  1988\.  Connectionism and cognitive architecture: A critical analysis Connectionism and cognitive architecture: A critical analysis.  Cognition281-23–71.
  * Fyhn . (2004) fyhn2004spatialFyhn, M., Molden, S., Witter, MP., Moser, EI. Moser, MB.  2004\.  Spatial representation in the entorhinal cortex Spatial representation in the entorhinal cortex.  Science30556881258–1264.
  * Garcez . (2002) garcez2002neuralGarcez, ASd., Broda, K. Gabbay, DM.  2002\.  Neural-symbolic learning systems: foundations and applications Neural-symbolic learning systems: foundations and applications.  Springer Science & Business Media.
  * Gelman Markman (1986) gelman1986categoriesGelman, SA. Markman, EM.  1986\.  Categories and induction in young children Categories and induction in young children.  Cognition233183–209.
  * Goodfellow . (2016) goodfellow2016deepGoodfellow, I., Bengio, Y. Courville, A.  2016\.  Deep learning Deep learning.  MIT press.
  * Higgins . (2016) higgins2016betaHiggins, I., Matthey, L., Pal, A., Burgess, C., Glorot, X., Botvinick, M.Lerchner, A.  2016\.  beta-vae: Learning basic visual concepts with a constrained variational framework beta-vae: Learning basic visual concepts with a constrained variational framework.  International conference on learning representations. International conference on learning representations.
  * Kerg . (2022) kerg2022neuralKerg, G., Mittal, S., Rolnick, D., Bengio, Y., Richards, B. Lajoie, G.  2022\.  On neural architecture inductive biases for relational tasks On neural architecture inductive biases for relational tasks.  arXiv preprint arXiv:2206.05056.
  * Kim Mnih (2018) kim2018disentanglingKim, H. Mnih, A.  2018\.  Disentangling by factorising Disentangling by factorising.  International Conference on Machine Learning International conference on machine learning ( 2649–2658).
  * LeCun . (2015) lecun2015deepLeCun, Y., Bengio, Y. Hinton, G.  2015\.  Deep learning Deep learning.  nature5217553436–444.
  * Markman Hutchinson (1984) markman1984childrenMarkman, EM. Hutchinson, JE.  1984\.  Children’s sensitivity to constraints on word meaning: Taxonomic versus thematic relations Children’s sensitivity to constraints on word meaning: Taxonomic versus thematic relations.  Cognitive psychology1611–27.
  * McClelland . (1986) mcclelland1986appealMcClelland, JL., Rumelhart, DE. Hinton, GE.  1986\.  The appeal of parallel distributed processing The appeal of parallel distributed processing.  MIT Press, Cambridge MA344.
  * McDougle . (2022) mcdougle2022continuousMcDougle, SD., Tsay, JS., Pitt, B., King, M., Saban, W., Taylor, JA. Ivry, RB.  2022\.  Continuous manipulation of mental representations is compromised in cerebellar degeneration Continuous manipulation of mental representations is compromised in cerebellar degeneration.  Brain145124246–4263.
  * Mitchell . (2023) mitchell2023comparingMitchell, M., Palmarini, AB. Moskvichev, A.  2023\.  Comparing Humans, GPT-4, and GPT-4V on abstraction and reasoning tasks Comparing humans, gpt-4, and gpt-4v on abstraction and reasoning tasks.  arXiv preprint arXiv:2311.09247.
  * Mnih . (2015) mnih2015humanMnih, V., Kavukcuoglu, K., Silver, D., Rusu, AA., Veness, J., Bellemare, MG.others  2015\.  Human-level control through deep reinforcement learning Human-level control through deep reinforcement learning.  nature5187540529–533.
  * Mondal . (2023) mondal2023learningMondal, SS., Webb, T. Cohen, JD.  2023\.  Learning to reason over visual objects Learning to reason over visual objects.  arXiv preprint arXiv:2303.02260.
  * Newell (1994) newell1994unifiedNewell, A.  1994\.  Unified theories of cognition Unified theories of cognition.  Harvard University Press.
  * Norman O’Reilly (2003) norman2003modelingNorman, KA. O’Reilly, RC.  2003\.  Modeling hippocampal and neocortical contributions to recognition memory: a complementary-learning-systems approach. Modeling hippocampal and neocortical contributions to recognition memory: a complementary-learning-systems approach.  Psychological review1104611.
  * O’Reilly McClelland (1994) o1994hippocampalO’Reilly, RC. McClelland, JL.  1994\.  Hippocampal conjunctive encoding, storage, and recall: Avoiding a trade-off Hippocampal conjunctive encoding, storage, and recall: Avoiding a trade-off.  Hippocampus46661–682.
  * Ravizza . (2006) ravizza2006cerebellarRavizza, SM., McCormick, CA., Schlerf, JE., Justus, T., Ivry, RB. Fiez, JA.  2006\.  Cerebellar damage produces selective deficits in verbal working memory Cerebellar damage produces selective deficits in verbal working memory.  Brain1292306–320.
  * Rogers McClelland (2004) rogers2004semanticRogers, TT. McClelland, JL.  2004\.  Semantic cognition: A parallel distributed processing approach Semantic cognition: A parallel distributed processing approach.  MIT press.
  * Rumelhart McClelland (1986) rumelhart1986learningRumelhart, DE. McClelland, JL.  1986\.  On learning the past tenses of English verbs On learning the past tenses of english verbs.
  * Sablé-Meyer . (2022) sable2022languageSablé-Meyer, M., Ellis, K., Tenenbaum, J. Dehaene, S.  2022\.  A language of thought for the mental representation of geometric shapes A language of thought for the mental representation of geometric shapes.  Cognitive Psychology139101527.
  * Sablé-Meyer . (2021) sable2021sensitivitySablé-Meyer, M., Fagot, J., Caparos, S., van Kerkoerle, T., Amalric, M. Dehaene, S.  2021\.  Sensitivity to geometric shape regularity in humans and baboons: A putative signature of human singularity Sensitivity to geometric shape regularity in humans and baboons: A putative signature of human singularity.  Proceedings of the National Academy of Sciences11816e2023123118.
  * Srivastava . (2014) srivastava2014dropoutSrivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I. Salakhutdinov, R.  2014\.  Dropout: a simple way to prevent neural networks from overfitting Dropout: a simple way to prevent neural networks from overfitting.  The journal of machine learning research1511929–1958.
  * Tran . (2017) tran2017disentangledTran, L., Yin, X. Liu, X.  2017\.  Disentangled representation learning gan for pose-invariant face recognition Disentangled representation learning gan for pose-invariant face recognition.  Proceedings of the IEEE conference on computer vision and pattern recognition Proceedings of the ieee conference on computer vision and pattern recognition ( 1415–1424).
  * T. Webb . (2023) webb2023emergentWebb, T., Holyoak, KJ. Lu, H.  2023\.  Emergent analogical reasoning in large language models Emergent analogical reasoning in large language models.  Nature Human Behaviour791526–1541.
  * TW. Webb . (2023) webb2023relationalWebb, TW., Frankland, SM., Altabaa, A., Krishnamurthy, K., Campbell, D., Russin, J.Cohen, JD.  2023\.  The relational bottleneck as an inductive bias for efficient abstraction The relational bottleneck as an inductive bias for efficient abstraction.  arXiv preprint arXiv:2309.06629.
  * TW. Webb . (2020) webb2020emergentWebb, TW., Sinha, I. Cohen, JD.  2020\.  Emergent symbols through binding in external memory Emergent symbols through binding in external memory.  arXiv preprint arXiv:2012.14601.
  * Whittington . (2020) whittington2020tolmanWhittington, JC., Muller, TH., Mark, S., Chen, G., Barry, C., Burgess, N. Behrens, TE.  2020\.  The Tolman-Eichenbaum machine: unifying space and relational memory through generalization in the hippocampal formation The tolman-eichenbaum machine: unifying space and relational memory through generalization in the hippocampal formation.  Cell18351249–1263.

## Supplementary Information

Figure 5: Performance on category task We trained ten relational and
feedforward neural networks, which differed solely in their initial weight
configurations, on a categorical same/different task. The task involved simple
binary stimuli, each represented by two one-hot encoded features. Each feature
could take one of 30 possible values, resulting in a total of 900 unique
stimuli. For training, we randomly selected a training set of 30 stimuli,
which constituted $3.\overline{3}\%$ of the entire stimulus set. The objective
for the networks was to learn to make similarity judgments on this holdout
set. During the testing phase, we evaluated the networks’ performance on the
remaining $96.\overline{6}\%$ of the stimuli, which they had not seen during
training. The networks’ were evaluated on their ability to accurately judge
the similarity of previously unseen stimuli. Performance on the task was
computed as accuracy on the task after binarizing the networks’ similarity
judgements by thresholding. Both the relational and feedforward networks
achieved perfect accuracy on the training set. Notably, the relational network
learned to perform the task more rapidly than the feedforward network. In
terms of generalization, the relational network’s performance on the holdout
set was nearly perfect, while the feedforward network’s performance was
significantly lower. Accuracy on the task is higher initially in the
relational network due to the relational bottlenecks sensitivity to the
trivially separated features present in the input data.


2023 CMU-HCII-23-103

Dr. Chris Harrison, Co-Chair, CMU
Dr. Mayank Goel, Co-Chair, CMU
Dr. Nikolas Martelaro, CMU
Dr. Andrew D. Wilson, Microsoft Research

#  Practical and Rich User Digitization

Karan Ahuja

(August 2023)

###### Abstract

A long-standing vision in computer science has been to evolve computing
devices into proactive assistants that enhance our productivity, health and
wellness, and many other facets of our lives. User digitization is crucial in
achieving this vision as it allows computers to intimately understand their
users, capturing activity, pose, routine, and behavior. Today’s consumer
devices – like smartphones and smartwatches – provide a glimpse of this
potential, offering coarse digital representations of users with metrics such
as step count, heart rate, and a handful of human activities like running and
biking. Even these very low-dimensional representations are already bringing
value to millions of people’s lives, but there is significant potential for
improvement. On the other end, professional, high-fidelity comprehensive user
digitization systems exist. For example, motion capture suits and multi-camera
rigs that digitize our full body and appearance, and scanning machines such as
MRI capture our detailed anatomy. However, these carry significant user
practicality burdens, such as financial, privacy, ergonomic, aesthetic, and
instrumentation considerations, that preclude consumer use. In general, the
higher the fidelity of capture, the lower the user’s practicality. Most
conventional approaches strike a balance between user practicality and
digitization fidelity.

My research aims to break this trend, developing sensing systems that increase
user digitization fidelity to create new and powerful computing experiences
while retaining or even improving user practicality and accessibility,
allowing such technologies to have a societal impact. Armed with such
knowledge, our future devices could offer longitudinal health tracking, more
productive work environments, full-body avatars in extended reality, and
embodied telepresence experiences, to name just a few domains.

###### keywords:

Motion capture, Pose, Mobile, Context-awareness, Activity recognition,
Sensing, Smartphones, Extended Reality, Privacy, Human Digital Twin, Digital
Representation

###### Acknowledgements.

At the culmination of this challenging and rewarding journey, I am profoundly
grateful to the individuals who have been my pillars of strength. To my
parents, Reshma and Deepak Ahuja, your unwavering support fueled my
determination. My achievements are a reflection of the values you instilled in
me. To my grandparents, your wisdom and stories have been a guiding light,
shaping my path with resilience and curiosity. My heartfelt appreciation
extends to my friends and collaborators, your collective enthusiasm has
enriched my academic journey. To my advisors and thesis committee members,
thanks for your constant support, encouragement, mentorship and insights that
have elevated my work.