Inner products of neural network feature maps arises in a wide variety of
machine learning frameworks as a method of modeling relations between inputs.
This work studies the approximation properties of inner products of neural
networks. It is shown that the inner product of a multi-layer perceptron with
itself is a universal approximator for symmetric positive-definite relation
functions. In the case of asymmetric relation functions, it is shown that the
inner product of two different multi-layer perceptrons is a universal
approximator. In both cases, a bound is obtained on the number of neurons
required to achieve a given accuracy of approximation. In the symmetric case,
the function class can be identified with kernels of reproducing kernel Hilbert
spaces, whereas in the asymmetric case the function class can be identified
with kernels of reproducing kernel Banach spaces. Finally, these approximation
results are applied to analyzing the attention mechanism underlying
Transformers, showing that any retrieval mechanism defined by an abstract
preorder can be approximated by attention through its inner product relations.
This result uses the Debreu representation theorem in economics to represent
preference relations in terms of utility functions.

通过分析内积关系，研究了神经网络特征图的内积在模拟输入之间的关系方面的广泛应用，证明了多层感知器自身的内积是对称正定关系函数的普遍逼近器，而两个不同多层感知器的内积是非对称关系函数的普遍逼近器，并通过内积关系将任何抽象预订定义的检索机制近似为注意力机制，从而应用于分析 Transformer 背后的注意力机制。同时，利用经济学中的 Debreu 表示定理以效用函数的形式表示偏好关系。

关系函数和注意力机制的近似

Approximation of relation functions and attention mechanisms

In this paper, we consider a heavy inner product identification problem,
which generalizes the Light Bulb problem~(\cite{prr89}): Given two sets $A
\subset \{-1,+1\}^d$ and $B \subset \{-1,+1\}^d$ with $|A|=|B| = n$, if there
are exact $k$ pairs whose inner product passes a certain threshold, i.e.,
$\{(a_1, b_1), \cdots, (a_k, b_k)\} \subset A \times B$ such that $\forall i
\in [k], \langle a_i,b_i \rangle \geq \rho \cdot d$, for a threshold $\rho \in
(0,1)$, the goal is to identify those $k$ heavy inner products. We provide an
algorithm that runs in $O(n^{2 \omega / 3+ o(1)})$ time to find the $k$ inner
product pairs that surpass $\rho \cdot d$ threshold with high probability,
where $\omega$ is the current matrix multiplication exponent. By solving this
problem, our method speed up the training of neural networks with ReLU
activation function.

我们考虑一种重内积识别问题，通过解决这个问题，我们的方法可以加速具有 ReLU 激活函数的神经网络的训练。

神经网络训练中权重和输入之间的快速重要内积识别

Fast Heavy Inner Product Identification Between Weights and Inputs in  Neural Network Training

Let $X$ be a set of $n$ points of norm at most $1$ in the Euclidean space
$R^k$, and suppose $\varepsilon>0$. An $\varepsilon$-distance sketch for $X$ is
a data structure that, given any two points of $X$ enables one to recover the
square of the (Euclidean) distance between them up to an {\em additive} error
of $\varepsilon$. Let $f(n,k,\varepsilon)$ denote the minimum possible number
of bits of such a sketch. Here we determine $f(n,k,\varepsilon)$ up to a
constant factor for all $n \geq k \geq 1$ and all $\varepsilon \geq
\frac{1}{n^{0.49}}$. Our proof is algorithmic, and provides an efficient
algorithm for computing a sketch of size $O(f(n,k,\varepsilon)/n)$ for each
point, so that the square of the distance between any two points can be
computed from their sketches up to an additive error of $\varepsilon$ in time
linear in the length of the sketches. We also discuss the case of smaller
$\varepsilon>2/\sqrt n$ and obtain some new results about dimension reduction
in this range. In particular, we show that for any such $\varepsilon$ and any
$k \leq t=\frac{\log (2+\varepsilon^2 n)}{\varepsilon^2}$ there are
configurations of $n$ points in $R^k$ that cannot be embedded in $R^{\ell}$ for
$\ell < ck$ with $c$ a small absolute positive constant, without distorting
some inner products (and distances) by more than $\varepsilon$. On the positive
side, we provide a randomized polynomial time algorithm for a bipartite variant
of the Johnson-Lindenstrauss lemma in which scalar products are approximated up
to an additive error of at most $\varepsilon$. This variant allows a reduction
of the dimension down to $O(\frac{\log (2+\varepsilon^2 n)}{\varepsilon^2})$,
where $n$ is the number of points.

本文研究欧几里得空间中距离草图和维度约简等方面的问题，并讨论了相应的算法和理论。