The greatest demand for today's computing is machine learning. This paper
analyzes three machine learning algorithms: transformers, spatial convolution,
and FFT. The analysis is novel in three aspects. First, it measures the cost of
memory access on an abstract memory hierarchy, instead of traditional time or
space complexity. Second, the analysis is asymptotic and identifies the primary
sources of the memory cost. Finally, the result is symbolic, which can be used
to select algorithmic parameters such as the group size in grouped query
attention for any dimension size and number of heads and the batch size for
batched convolution for any image size and kernel size.

该论文通过分析 transformers、spatial convolution 和 FFT 三种机器学习算法，提出了三个创新点。首先，它使用抽象的内存层次结构来衡量内存访问成本，而不是传统的时间或空间复杂度。其次，该分析是渐近的，并确定了内存成本的主要来源。最后，该结果是符号的，可以用于选择算法参数，例如分组查询关注力的组大小，以及任意尺寸和头数的批量卷积的批量大小。

DMC4ML: 机器学习的数据移动复杂性

DMC4ML: Data Movement Complexity for Machine Learning

This paper introduces a generalization of Convolutional Neural Networks
(CNNs) from low-dimensional grid data, such as images, to graph-structured
data. We propose a novel spatial convolution utilizing a random walk to uncover
the relations within the input, analogous to the way the standard convolution
uses the spatial neighborhood of a pixel on the grid. The convolution has an
intuitive interpretation, is efficient and scalable and can also be used on
data with varying graph structure. Furthermore, this generalization can be
applied to many standard regression or classification problems, by learning the
the underlying graph. We empirically demonstrate the performance of the
proposed CNN on MNIST, and challenge the state-of-the-art on Merck molecular
activity data set.

本研究介绍了一种卷积神经网络的泛化方法，使其适用于图形结构数据，使用随机游走揭示输入数据内部关系，通过学习底层图将其应用于许多标准分类或回归问题。