# Unified Embedding: Battle-Tested Feature Representations for Web-Scale ML
Systems

Benjamin Coleman∗
Google Research, Brain Team
<EMAIL_ADDRESS>
Wang-Cheng Kang∗
Google Research, Brain Team
<EMAIL_ADDRESS>
Matthew Fahrbach
Google Research
<EMAIL_ADDRESS>
Ruoxi Wang
Google Research, Brain Team
<EMAIL_ADDRESS>
Lichan Hong
Google Research, Brain Team
<EMAIL_ADDRESS>
Ed H. Chi
Google Research, Brain Team
<EMAIL_ADDRESS>
Derek Zhiyuan Cheng
Google Research, Brain Team
<EMAIL_ADDRESS>

###### Abstract

Learning high-quality feature embeddings efficiently and effectively is
critical for the performance of web-scale machine learning systems. A typical
model ingests hundreds of features with vocabularies on the order of millions
to billions of tokens. The standard approach is to represent each feature
value as a $d$-dimensional embedding, introducing hundreds of billions of
parameters for extremely high-cardinality features. This bottleneck has led to
substantial progress in alternative embedding algorithms. Many of these
methods, however, make the assumption that each feature uses an independent
embedding table. This work introduces a simple yet highly effective framework,
_Feature Multiplexing_ , where one single representation space is used across
many different categorical features. Our theoretical and empirical analysis
reveals that multiplexed embeddings can be decomposed into components from
each constituent feature, allowing models to distinguish between features. We
show that multiplexed representations lead to Pareto-optimal parameter-
accuracy tradeoffs for three public benchmark datasets. Further, we propose a
highly practical approach called _Unified Embedding_ with three major
benefits: simplified feature configuration, strong adaptation to dynamic data
distributions, and compatibility with modern hardware. Unified embedding gives
significant improvements in offline and online metrics compared to highly
competitive baselines across five web-scale search, ads, and recommender
systems, where it serves billions of users across the world in industry-
leading products.

11footnotetext: Equal contribution.

##  1 Introduction

There have been many new and exciting breakthroughs across academia and
industry towards large-scale models recently. The advent of larger datasets
coupled with increasingly powerful accelerators has enabled machine learning
(ML) researchers and practitioners to significantly scale up models. This
scale has yielded surprising emergent capabilities, such as human-like
conversation and reasoning (Bubeck et al., 2023; Wei et al., 2022a).
Interestingly, large-scale model architectures are headed towards two extreme
scenarios. In natural language understanding, speech, and computer vision, the
transformer (Vaswani et al., 2017) dominates the Pareto frontier. Most
transformer parameters are located in the hidden layers, with very small
embedding tables (e.g., ~0.63B embedding parameters in the 175B GPT-3 (Brown
et al., 2020)). On the other hand, search, ads, and recommendation (SAR)
systems require staggering scale for state-of-the-art performance (e.g., 12T
parameters in Mudigere et al. (2022)), but here, most of the parameters are in
the embedding tables. Typical downstream hidden layers are 3–4 magnitudes
smaller than the embedding tables. Recent work blurs the boundary between
these extremes—large transformers started adopting bigger embedding tables for
new types of tokens, and new SAR models leverage deeper and ever more-
complicated networks. Therefore, embedding learning is a core technique that
we only expect to become more critical and relevant to large-scale models in
the future.

Motivated by web-scale ML for SAR systems, we study the problem of learning
embeddings for categorical (sparse) features.111For simplicity, we call this
problem “feature embedding learning,” but we are primarily concerned with
representing sparse features such as zipcodes, word tokens, and product IDs.
The weekend golf warriors in the ML community may appreciate our analogy
between embeddings and the golf club grip (Hogan and Wind, 1985). In golf, the
quality of your grip (feature embeddings) dictates the quality of your swing
(model performance). Feature embeddings are the only point of contact between
the data and the model, so it is critical to learn effective, high-quality
representations.

Feature embedding learning has been a highly active research area for nearly
three decades (Rumelhart et al., 1986; Bengio et al., 2000; Mikolov et al.,
2013; Papyan et al., 2020). In the linear model era, sparse features were
represented as one-hot vectors. Linear sketches for dimension reduction became
a popular way to avoid learning coefficients for each coordinate (Weinberger
et al., 2009). In deep learning models, sparse features are not sketched but
rather represented directly as embeddings. Learned feature embeddings carry a
significant amount of semantic information, providing avenues to meaningfully
model interactions in the high-dimensional latent space.

#### In practice

The simplest transformation is to represent each feature value by a row in an
$N\times d$ matrix (i.e., an embedding table). This approach is sufficient for
many language tasks, but SAR features often have massive vocabulary (e.g.,
tens of billions of product IDs in commerce) and highly dynamic power-law
distributions. It is impractical to store and serve the full embedding table.

The hashing trick (Moody, 1988; Weinberger et al., 2009) provides a workaround
by randomly assigning feature values to one of $M$ rows using a hash function.
Hash embeddings (Svenstrup et al., 2017a) are a variation on the hashing trick
where each feature value is assigned to multiple rows in the table. The final
embedding is a weighted sum of rows, similar to a learned form of two-choice
hashing (Mitzenmacher, 2001). Compositional embeddings (Shi et al., 2020) look
up the feature in several independent tables and construct the final embedding
from the components by concatenation, addition, or element-wise product.
HashedNet embeddings (Chen et al., 2015) independently look up each dimension
of the embedding in a flattened parameter space. ROBE embeddings (Desai et
al., 2022) look up chunks, instead of single dimensions, to improve cache
efficiency. Tsang and Ahle (2022) learn a sparse matrix to describe the
row/dimension lookups, and deep hash embeddings (Kang et al., 2021) use a
neural network to directly output the embedding.

#### In theory

The analysis of embedding algorithms is heavily influenced by linear models
and the work of Weinberger et al. (2009) on the hashing trick. This line of
reasoning starts with the assumption that all inputs have a “true”
representation in a high-dimensional space that preserves all of the
properties needed for learning (e.g., the one-hot encoding). The next step is
to perform linear dimension reduction to compress the ground-truth
representation into a smaller embedding, while approximately preserving inner
products and norms. The final step is to extend the inner product argument to
models that only interact with their inputs through inner products and norms
(e.g., kernel methods).

In this framework, a key opportunity for improving performance is to reduce
the dimension-reduction error. Early methods were based on the
Johnson–Lindenstrauss lemma and sparse linear projections (Achlioptas, 2001;
Li et al., 2006; Weinberger et al., 2009). Since then, a substantial effort
has gone into improving the hash functions (Dahlgaard et al., 2017) and
tightening the theoretical analysis of feature hashing (Dasgupta and Gupta,
2003; Freksen et al., 2018). Learned embeddings are now state-of-the-art, but
the focus on dimension reduction remains: most recent algorithms are motivated
by dimension reduction arguments. Previous attempts to understand hash
embeddings do not study the full give-and-take relationship between feature
encoding and the downstream learning problem. In this work, we carry the
analysis forward to better understand learned embeddings.

#### Contributions

We present an embedding learning framework called Feature Multiplexing, where
multiple features share one representation space. Our theoretical analysis and
experimental studies on public benchmark datasets show that Feature
Multiplexing is theoretically sound and generalizable to many popular
embedding methods. We also propose a highly-efficient multiplexed approach
called Unified Embedding, which has been battle-tested by serving billions of
users in industry-leading products via various web-scale search, ads, and
recommendation models.

  1. 1.

Feature multiplexing: We propose the Feature Multiplexing framework, where a
single representation space (embedding table) is used to support different
sparse features. All of the SOTA benchmark embedding algorithms in our
experiments show better results when adopting Feature Multiplexing.
Furthermore, the Unified Embedding approach (i.e., multiplexing + hashing
trick) outperforms many SOTA embedding methods that are noticeably more
complicated to implement and impractical for serving low-latency systems with
modern day hardware.

  2. 2.

Analysis beyond collision counts: We analyze hash embeddings in the standard
framework as well as in a supervised learning setting to capture interactions
between feature embedding and downstream learning. Our analysis gives insights
and testable predictions about unified embeddings that cannot be obtained by
dimension reduction arguments alone.

  3. 3.

Battle-tested approach and industrial experiments at scale: Multi-size Unified
Embedding has been launched in over a dozen web-scale SAR systems,
significantly improving user engagement metrics and key business metrics. In
addition, Unified Embedding presents major practical benefits: simplified
feature configuration, strong adaptation to dynamic data distributions, and
compatibility with modern hardware. In Section 5.2, we share our insights,
challenges, and practical lessons on adopting Unified Embedding.

##  2 Preliminaries

SAR applications often present supervised learning problems over categorical
(sparse) features that represent properties of users, queries, and items. Each
categorical feature consists of one or more _feature values_ $v$ drawn from
the _vocabulary_ of the feature $V$. For a concrete example, consider the
classic click-through rate (CTR) prediction task for Ads systems, where we
want to predict the probability of a user clicking on an advertisement. The
“ad_id” feature may take on hundreds of billions of possible values—one for
each unique ad served by the platform—while “site_id” describes the website
where that ad was shown (a.k.a., the publisher).

We _embed_ the values of each feature into a space that is more suitable for
modeling, e.g., $\mathbb{R}^{d}$ or the unit $(d-1)$-sphere. Given a
vocabulary of $N$ tokens $V=\\{v_{1},v_{2},\dots,v_{N}\\}$, we learn a
transformation that maps $v\in V$ to an embedding vector
$\mathbf{e}\in\mathbb{R}^{d}$. After repeating this process for each
categorical feature, we get a set of embeddings that get concatenated and fed
as input to a neural network (Covington et al., 2016; Anil et al., 2022).

#### Problem statement

We are given a dataset
$D=\\{(\boldsymbol{x}_{1},y_{1}),(\boldsymbol{x}_{2},y_{2}),\dots,(\boldsymbol{x}_{|D|},y_{|D|})\\}$
of examples with labels. The examples consist of values from $T$ different
categorical features having vocabularies $\\{V_{1},V_{2},\dots,V_{T}\\}$,
where feature $t$ has vocabulary $V_{t}$. Unless otherwise stated, we do not
consider multivalent features and instead assume that each example
$\boldsymbol{x}$ has one value for each categorical feature, i.e.,
$\boldsymbol{x}=\begin{bmatrix}v_{1},v_{2},\dots,v_{T}\end{bmatrix}$ where
$v_{i}\in V_{i}$. However, this is for notational convenience only—the
techniques in this paper extend to missing and multivalent feature values
well.

Formally, the embedding table is a matrix $\mathbf{E}\in\mathbb{R}^{M\times
d}$ and the embedding function $g(\mathbf{x};\mathbf{E})$ transforms the
categorical feature values into embeddings. We let $h(v):V\rightarrow[M]$ be a
2-universal hash function (Vadhan et al., 2012) that assigns a feature value
to a row of the embedding table. We also consider a model function
$f(\mathbf{e};\boldsymbol{\theta})$ that transforms the concatenated
embeddings into a model prediction, which is penalized by a loss $\ell$. Using
this decomposition, we define the joint feature learning problem as follows:

$\operatorname*{arg\,min\,}_{\mathbf{E},\boldsymbol{\theta}}\mathcal{L}_{D}(\mathbf{E},\boldsymbol{\theta}),\quad\text{where}\quad\mathcal{L}_{D}(\mathbf{E},\boldsymbol{\theta})=\sum_{(\boldsymbol{x},y)\in
D}\ell(f(g(\boldsymbol{x};\mathbf{E});\boldsymbol{\theta}),y).$ (1)

We use independent hash functions $h_{t}(v)$ for each feature $t\in[T]$ so
that tokens which appear in multiple vocabularies get mapped to potentially
different locations, depending on the feature. We use the notation
$\mathbf{e}_{m}$ to denote the $m$-th row of $\mathbf{E}$, which means
$\mathbf{e}_{h(u)}$ is the embedding of $u$. Lastly, we use the indicator
variable $\mathbbm{1}_{u,v}$ to denote a hash collision between $u$ and $v$,
i.e., $h(u)=h(v)$.

##  3 Feature Multiplexing: The Inter-Feature Hashing Trick

It is standard practice to use a different hash table for each categorical
feature. There are a few approaches that deviate from this common practice—for
example, HashedNet and ROBE-Z models perform parameter sharing across all
features, depending on the implementation. However, common wisdom suggests
that each categorical vocabulary benefits from having an independent
representation, so shared representations are not well-studied.

#### Parameter reuse

We present a _Feature Multiplexing_ framework that only uses one embedding
table to represent all of the feature vocabularies. In contrast, typical
models in SAR systems have hundreds of embedding tables, each representing one
input feature. Multiplexed embeddings allow models to reuse parameters and
lookup operations, improving efficiency in terms of both space and time. This
is critical for models that must fit into limited GPU/TPU memory or obey
latency and serving cost constraints. In principle, any feature embedding
scheme (e.g., hashing trick, multihash, compositional, or ROBE-Z) can be used
as the shared representation for feature multiplexing. In Section 5, we
experiment with multiplexed versions of six different embedding algorithms.
Here, we focus on the multiplexed version of the feature hashing trick (Figure
1), which we call Unified Embedding. Unified Embedding presents unique
practical advantages that we describe in Section 5.2.

Figure 1: Embedding methods for two categorical features. We highlight the
lookup process for the first value $v_{1}$ of each feature. Hash tables
randomly share representations within each feature, while Unified Embedding
shares representations across features. To implement Unified Embedding with
different dimensions (i.e., multi-size or variable-length), we perform
multiple lookups and concatenate the results.

#### Multi-size unified embeddings

By using a unified table, we make the architectural assumption that all
features share the same embedding dimension. However, this is often sub-
optimal in practice since independent tuning of individual embedding
dimensions can significantly improve model performance. For use-cases where
different features require different embedding dimensions, we concatenate the
results of a variable number of table lookups to obtain the final embedding.
While this limits the output dimension to multiples of the table dimension,
this is not a limiting constraint (and is needed by other methods such as
ROBE-Z and product quantization).

#### Shared vocabulary

It is common for categorical feature vocabularies to share tokens. For
example, two features that represent character bigrams of different text
fields (e.g. query and document) might have substantial overlap. Our default
approach is to use a different hash function for each feature, via setting
different hashing seed for each feature. However, in occasional cases where
many semantically-similar features are present, the performance may slightly
improve when using the same hash function.

##  4 Analysis of Feature Multiplexing

In this section, we present theoretical arguments on the feature multiplexing
trick. We start with a brief analysis of unified embeddings in the dimension-
reduction framework, suggesting that unified embeddings optimally load balance
feature vocabularies across buckets in the table. This classical framework,
however, cannot be used to distinguish between collisions that happen within
the vocabulary of a feature (i.e., _intra-feature_) and those occurring across
features (i.e., _inter-feature_).

To understand these interactions, we also need to consider the learning task
and model training. Thus, we analyze the gradient updates applied to each
bucket under a simplified but representative model—binary logistic regression
with learnable feature embeddings for CTR prediction. Our analysis
demonstrates a novel relationship between the embedding parameters and model
parameters through gradient descent. Specifically, we find that the effect of
inter-feature collisions can be mitigated if the model projects different
features using orthogonal weight vectors. In Section 4.2, we empirically
verify this by training models on public benchmark on click-through prediction
(Criteo) and finding that the weight vectors do, in fact, orthogonalize. We
defer the proofs and detailed derivations in this section to Appendix A.

###  4.1 Parameter Efficiency in The Dimension-Reduction Framework

In the feature hashing problem, we are given two vectors
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{N}$ that we project using a linear map
$\phi:\mathbb{R}^{N}\rightarrow\mathbb{R}^{M}$ given by the sparse $\\{\pm
1\\}$ matrix in Weinberger et al. (2009). The goal is for $\phi$ to minimally
distort inner product, i.e.,
$\langle\phi(\mathbf{x}),\phi(\mathbf{y})\rangle\approx\langle\mathbf{x},\mathbf{y}\rangle$.
Since the estimation error directly depends on the variance, it is sufficient
to compare hashing schemes based on the moments of their inner product
estimators. We will examine the variance of the hashing trick and multiplexing
trick.

To analyze multiple features at once in this framework, we consider the
concatenations $\mathbf{x}=[\mathbf{x}_{1},\mathbf{x}_{2}]$ and
$\mathbf{y}=[\mathbf{y}_{1},\mathbf{y}_{2}]$. The components
$\mathbf{x}_{1}\in\\{0,1\\}^{N_{1}}$ and $\mathbf{x}_{2}\in\\{0,1\\}^{N_{2}}$
are the one-hot encodings (or bag-of-words) for the two vocabularies $V_{1}$
and $V_{2}$. The standard hashing trick approximates
$\langle\mathbf{x},\mathbf{y}\rangle$ by independently projecting
$\mathbf{x}_{1}$ to dimension $M_{1}$ and $\mathbf{x}_{2}$ to dimension
$M_{2}$. The unified embedding version uses a single projection, but into
dimension $M_{1}+M_{2}$. Now, we formalize the hashing trick of Weinberger et
al. (2009), but with slightly revised notation. Given a set of tokens from the
vocabulary, the embedding is the signed sum of value counts within each hash
bucket.

######  Definition 4.1.

Let $h:V\rightarrow\\{1,2,\dots,M\\}$ be a 2-universal hash function and
$\xi:V\rightarrow\\{-1,+1\\}$ be a sign hash function. The function
$\phi_{h,\xi}:2^{V}\rightarrow\mathbb{R}^{M}$ is defined as
$\phi_{h,\xi}(W)=\sum_{w\in W}\xi(w)\mathbf{u}_{h(w)},$ where $\mathbf{u}_{i}$
is the $i$-th unit basis vector in $\mathbb{R}^{M}$.

The following result compares unified and standard embeddings in the dimension
reduction framework. Note that the randomness is over the choice of hash
functions $h(v)$ and $\xi(v)$. This result also directly extends to
concatenating $T$ feature embeddings.

######  Proposition 4.2.

For any $\mathbf{x}_{1},\mathbf{y}_{1}\in\\{0,1\\}^{N_{1}}$ and
$\mathbf{x}_{2},\mathbf{y}_{2}\in\\{0,1\\}^{N_{2}}$, let
$\mathbf{x}=[\mathbf{x}_{1},\mathbf{x}_{2}]$,
$\mathbf{y}=[\mathbf{y}_{1},\mathbf{y}_{2}]$ denote their concatenations. Let
$\mu_{U}$, $\mu_{H}$, $\sigma^{2}_{U}$, and $\sigma^{2}_{H}$ be the mean and
variance of $\langle\phi_{h,\xi}(\mathbf{x}),\phi_{h,\xi}(\mathbf{y})\rangle$
for unified and hash encodings, respectively. Then,
$\mu_{U}=\mu_{H}=\langle\mathbf{x},\mathbf{y}\rangle$ and

$\displaystyle\sigma^{2}_{U}$
$\displaystyle=\frac{\|\mathbf{x}\|_{2}^{2}\|\mathbf{y}\|_{2}^{2}+\langle\mathbf{x},\mathbf{y}\rangle^{2}-2\left\langle\mathbf{x},\mathbf{y}\right\rangle}{M_{1}+M_{2}},$
$\displaystyle\sigma^{2}_{H}$
$\displaystyle=\frac{\|\mathbf{x}_{1}\|_{2}^{2}\|\mathbf{y}_{1}\|_{2}^{2}+\langle\mathbf{x}_{1},\mathbf{y}_{1}\rangle^{2}-2\left\langle\mathbf{x}_{1},\mathbf{y}_{1}\right\rangle}{M_{1}}+\frac{\|\mathbf{x}_{2}\|_{2}^{2}\|\mathbf{y}_{2}\|_{2}^{2}+\langle\mathbf{x}_{2},\mathbf{y}_{2}\rangle^{2}-2\left\langle\mathbf{x}_{2},\mathbf{y}_{2}\right\rangle}{M_{2}}.$

#### Observations

Proposition 4.2 shows that unified embeddings can do a good job balancing hash
collisions across the parameter space. Consider the problem of estimating the
inner product $\langle\mathbf{x},\mathbf{y}\rangle$. Suppose that
$\|\mathbf{x}_{1}\|_{2}^{2}=\|\mathbf{y}_{1}\|_{2}^{2}=k_{1}$ and
$\|\mathbf{x}_{2}\|_{2}^{2}=\|\mathbf{y}_{2}\|_{2}^{2}=k_{2}$, i.e., features
1 and 2 are multivalent with $k_{1}$ and $k_{2}$ values, and assume x and y
are orthogonal, i.e., $\langle\mathbf{x},\mathbf{y}\rangle=0$. Proposition 4.2
tells us that $\sigma_{U}^{2}=(k_{1}+k_{2})^{2}/(M_{1}+M_{2})$ and
$\sigma_{H}^{2}=k_{1}^{2}/M_{1}+k_{2}^{2}/M_{2}$. The difference
$\sigma_{H}^{2}-\sigma_{U}^{2}$ factors as
$(\sqrt{M_{1}/M_{2}}k_{1}-\sqrt{M_{2}/M_{1}}k_{2})^{2}/(M_{1}+M_{2})$, which
is non-negative, implying $\sigma_{U}^{2}\leq\sigma_{H}^{2}$.

###  4.2 Trajectories of Embeddings During SGD for Single-Layer Neural
Networks

Intuition suggests that inter-feature collisions are less problematic than
intra-feature collisions. For example, if $x\in V_{1}$ collides with $y\in
V_{2}$ but no other values collide across vocabularies, then the embeddings
from other tokens in $V_{1}$ and $V_{2}$ are free to rotate around the shared
embedding for $x,y$ to preserve their optimal similarity relationships.

We analyze a logistic regression model with trainable embeddings for binary
classification (i.e., a single-layer neural network with hashed one-hot
encodings as input). This corresponds to Equation Equation 1 where
$f(\mathbf{z};\boldsymbol{\theta})$ is the sigmoid function
$\sigma_{\boldsymbol{\theta}}(\mathbf{z})=1/(1+\exp(-\langle\mathbf{z},\boldsymbol{\theta}\rangle))$,
$\ell$ is the binary cross-entropy loss, and $y\in\\{0,1\\}$ (e.g., click or
non-click). We concatenate the embeddings of each feature, which means that
the input to $f(\mathbf{z};\boldsymbol{\theta})$ is
$\mathbf{z}=g(\boldsymbol{x};\mathbf{E})=[\mathbf{e}_{h_{1}(\boldsymbol{x}_{1})},\mathbf{e}_{h_{2}(\boldsymbol{x}_{2})},\dots,\mathbf{e}_{h_{T}(\boldsymbol{x}_{T})}]$,
where $\mathbf{e}_{h_{t}(\boldsymbol{x}_{t})}$ is the embedding for the $t$-th
feature value in example $\boldsymbol{x}$. We write the logistic regression
weights as
$\boldsymbol{\theta}=[\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2},\dots,\boldsymbol{\theta}_{T}]$
so that embedding $\mathbf{e}_{h_{t}(\boldsymbol{x}_{t})}$ for feature $t$ is
projected via $\boldsymbol{\theta}_{t}\in\mathbb{R}^{M}$. We illustrate this
simple but representative model architecture in Figure 2.

The following analysis holds in general for $T$ features, but we consider the
problem for two categorical features with vocabularies $V_{1}$ and $V_{2}$ to
simplify the presentation. We write the logistic regression objective as
follows in Equation (2), using $C_{u,v,1}$ and $C_{u,v,0}$ to denote the
number of examples for which $\boldsymbol{x}=[u,v]$ and $y=1$ and $y=0$,
respectively. We present a full derivation in Section A.2.

$\mathcal{L}_{D}(\mathbf{E},\boldsymbol{\theta})=-\sum_{u\in V_{1}}\sum_{v\in
V_{2}}C_{u,v,0}\log\exp(\boldsymbol{\theta}^{\top}\mathbf{e}_{u,v})-(C_{u,v,0}+C_{u,v,1})\log(1+\exp(\boldsymbol{\theta}^{\top}\mathbf{e}_{u,v}))$
(2)

Figure 2:  Single-layer neural embedding model with per-feature weights
$\boldsymbol{\theta}_{t}$ (left). Mean embedding $\ell^{2}$-norm (middle) and
mean angle between all pairs of weight vectors
$\boldsymbol{\theta}_{t_{1}},\boldsymbol{\theta}_{t_{2}}$ (right) as a
function of table size for Criteo across all 26 categorical features. Note the
log scale.

To understand the effect of hash collisions on training dynamics, we take the
gradient with respect to $\mathbf{e}_{h_{1}(u)}$, i.e., the embedding
parameters that represent $u\in V_{1}$. By studying the gradients for
collisionless, hash, and unified embeddings, we can quantify the effects of
intra-feature and inter-feature collisions. Interestingly, all three gradients
can be written using the following three terms.

$\displaystyle\nabla_{\mathbf{e}_{h_{1}(u)}}\mathcal{L}_{D}(\mathbf{E},\boldsymbol{\theta})$
$\displaystyle=\boldsymbol{\theta}_{1}\sum_{v\in
V_{2}}C_{u,v,0}-(C_{u,v,0}+C_{u,v,1})\sigma_{\boldsymbol{\theta}}(\mathbf{e}_{u,v})$
(3) $\displaystyle\hskip
9.95863pt+\boldsymbol{\theta}_{1}\sum_{\begin{subarray}{c}w\in V_{1}\\\ w\neq
u\end{subarray}}\mathbbm{1}_{u,w}\sum_{v\in
V_{2}}C_{w,v,0}-(C_{w,v,0}+C_{w,v,1})\sigma_{\boldsymbol{\theta}}(\mathbf{e}_{u,v})$
(4) $\displaystyle\hskip 9.95863pt+\boldsymbol{\theta}_{2}\sum_{v\in
V_{2}}\mathbbm{1}_{u,v}\sum_{w\in
V_{1}}C_{w,v,0}-(C_{w,v,0}+C_{w,v,1})\sigma_{\boldsymbol{\theta}}(\mathbf{e}_{w,v}).$
(5)

For collisionless embeddings, component (3) is the full gradient. For hash
embeddings, the gradient is the sum of components (3) and (4). The unified
embedding gradient is the sum of all three terms.

#### Insights

Our core observation is that embedding gradients can be decomposed into a
collisionless (true) component (3), an intra-feature component (4), and an
inter-feature component (5). The components from hash collisions act as a
gradient bias. The intra-feature component is in the same direction as the
true component, implying that intra-feature collisions are not resolvable by
the model. This agrees with intuition since intra-feature hash collisions
effectively act as value merging.

Inter-feature collisions, however, push the gradient in the direction of
$\boldsymbol{\theta}_{2}$, which creates an opportunity for model training to
mitigate their effect. To see this, consider a situation where
$\boldsymbol{\theta}_{1}$ and $\boldsymbol{\theta}_{2}$ are initialized to be
orthogonal and do not change direction during training.222This restriction
does not affect the representation capacity because learned embeddings can
rotate around $\boldsymbol{\theta}$, i.e., for any
$\boldsymbol{\theta},\mathbf{e}$, and nonzero constant $\mathbf{u}$, we can
learn some $\mathbf{e}^{\prime}$ that satisfies
$\langle\mathbf{e}^{\prime},\mathbf{u}\rangle=\langle\mathbf{e},\boldsymbol{\theta}\rangle$.
During SGD, the embedding $\mathbf{e}_{h_{1}(u)}$ is a linear combination of
gradients over the training steps, which means $\mathbf{e}_{h_{1}(u)}$ can be
decomposed into a true and intra-feature component, in the
$\boldsymbol{\theta}_{1}$ direction, and an inter-feature component in the
$\boldsymbol{\theta}_{2}$ direction. Since
$\langle\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2}\rangle=0$, the
projection of $\boldsymbol{\theta}_{1}^{\top}\mathbf{e}_{h_{1}(u)}$
effectively _eliminates the inter-feature component_.

#### Empirical study

These theoretical observations allow us to form two testable hypotheses.
First, we expect the projection vectors
$[\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2},\dots,\boldsymbol{\theta}_{T}]$
to orthogonalize since this minimizes the effect of inter-feature collisions
(and improves the loss). The orthogonalization effect should be stronger for
embedding tables with fewer hash buckets since that is when inter-feature
collisions are most prevalent. Second, intra-feature and inter-feature
gradient contributions add approximately $O(N/M)$ for each of their dimensions
to the collisionless gradient since $\mathbb{E}[\mathbbm{1}_{u,v}]=1/M$.
Therefore, we expect the squared embedding norms to scale roughly as $O(N/M)$.

To investigate these hypotheses, we train a single-layer neural network on the
categorical features of the Criteo click-through prediction task. We
initialize
$\boldsymbol{\theta}=[\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2},\dots,\boldsymbol{\theta}_{T}]$
with each $\boldsymbol{\theta}_{t}$ component in the same direction (i.e., the
worst-case) to see if multiplexing encourages the weights to orthogonalize. We
plot the results in Figure 2, which support our hypotheses.

###  4.3 Why Can Features Share a Single Table?

Returning to our parameter efficiency argument of Section 4.1, we can finally
explain the full benefits of feature multiplexing. The dimension reduction
argument shows that, given a parameter budget, Unified Embedding has the same
overall number of hash collisions as a well-tuned hash embedding. Our gradient
analysis, however, shows that not all collisions are equally problematic.
Inter-feature collisions can be mitigated by a single-layer neural network
because different features are processed by different model parameters. While
our theoretical results are limited to single-layer neural networks, we expect
deeper and more complicated network architectures to exhibit analogs of weight
orthogonalization due to their relative overparameterization. However, we
believe this is still compelling evidence that shared embedding tables work by
load balancing unrecoverable collisions across a larger parameter space, and
effectively use a massive table for each feature.

##  5 Experiments

Finally, we present experimental results on three public benchmark datasets,
followed by anonymized, aggregate results from our industrial deployments
across multiple web-scale systems. Appendix B contains more details, including
full parameter-accuracy tradeoffs, additional experiments, and the neural
network architectures we used.

###  5.1 Experiments with Public Benchmark Datasets

#### Datasets

Criteo and Avazu are ad click-prediction tasks where the training data
consists of many days worth of logged categorical user, context, and ad
features. The task is to predict a binary label corresponding to “click” and
“non-click.” Movielens is the most popular dataset for recommendation system
research, which we normalize to a binary prediction task by assigning “1”s to
all examples with rating $\geq 3$, and “0”s to the rest. For Criteo and
Movielens, we apply the same continuous feature transformations, train-test
split, and other preprocessing steps as described in Wang et al. (2021). For
Avazu, we use the train-test split and preprocessing from Song et al. (2019).

#### Experiment design

To find the Pareto frontier on the memory-AUC curve, we train a neural network
on various embedding representations at 16 logarithmically-spaced memory
budgets. Models can overfit on the second epoch, but compressed embeddings
sometimes need multiple epochs to train. To showcase the best performance, we
follow the guidelines of Tsang and Ahle (2022) and report the test performance
of the best model found over three epochs. As baselines, we implement
collisionless embeddings, the feature hashing trick, hash embeddings,
HashedNets, ROBE-Z, compositional embeddings with element-wise product (QR),
and compositional embeddings with concatenation, i.e., product quantization
(PQ). We ran all experiments on an internal shared cluster.

#### Implementation and hyperparameters

All methods are implemented in Tensorflow 2.0 using the TensorFlow
Recommenders (TFRS) framework.333https://github.com/tensorflow/recommenders
For a fair comparison, all models are identical except for the embedding
component. Following other studies (Naumov et al., 2019; Wang et al., 2021),
we use the same embedding dimension for all features ($d=39,32$ and $30$ for
Criteo, Avazu, and Movielens respectively). This is followed by a stack of 1-2
DCN cross layers and 1-2 DNN feed-forward layers – we provide a full
description of the architecture in Appendix B. We run a grid search to tune
all embedding algorithm hyperparameters and conduct five runs per combination.
When allocating embedding parameters to features, we size tables based on the
cardinality of their vocabulary (e.g., a feature with 10% of the total
vocabulary receives 10% of the memory budget).

#### Results

Table 1 shows the results for academic datasets. We give three points on the
parameter-accuracy tradeoff and highlight the pareto-optimal choices, but
present the full tradeoff (including standard deviations across runs) in
Appendix B. Figure 3 presents the Pareto frontier of the parameter-accuracy
tradeoff for all multiplexed and non-multiplexed methods. We observe that
feature multiplexing is Pareto-optimal. We also find that unified hash
embeddings outperform several embedding techniques (e.g., ROBE-Z) that were
previously SOTA. This is particularly true for low-memory tables—at 10x
compression, unified embedding outperforms all existing (non-multiplexed)
baselines on Criteo.

Table 1: AUC of embedding methods on click-through data. We give results for several points on the parameter-accuracy tradeoff, listed as sub-headings under the dataset that describe the total embedding size. Note that for Avazu and Criteo, a 0.02% increase in test AUC is considered significant. | Criteo | Avazu | Movielens-1M
---|---|---|---
Method | 25MB | 12.5MB | 2.5MB | 32.4MB | 3.24MB | 324kB | 1.6MB | 791kB | 158kB
Collisionless | 80.70 | – | – | 77.35 | – | – | 88.72 | – | –
Hashing Trick | 80.21 | 79.98 | 79.44 | 77.24 | 76.71 | 75.10 | 85.37 | 83.00 | 77.07
Hash Embedding | 79.82 | 80.34 | 80.40 | 77.29 | 76.89 | 76.86 | 88.28 | 87.71 | 86.05
HashedNet | 80.54 | 80.50 | 80.42 | 77.30 | 77.19 | 76.89 | 87.92 | 87.92 | 87.31
ROBE-Z Embedding | 80.55 | 80.52 | 80.41 | 77.32 | 77.18 | 76.88 | 88.05 | 87.92 | 87.40
PQ Embedding | 80.29 | 80.25 | 79.82 | 77.39 | 77.11 | 76.48 | 88.49 | 88.38 | 87.32
QR Embedding | 80.29 | 80.21 | 79.74 | 76.98 | 76.61 | 75.86 | 88.49 | 88.63 | 88.22
Unified Embedding | 80.43 | 80.47 | 80.49 | 77.35 | 77.18 | 76.86 | 87.74 | 86.93 | 82.00
Multiplex HashEmb | 80.52 | 80.42 | 80.31 | 77.28 | 77.16 | 76.82 | 88.79 | 88.74 | 87.66
Multiplex HashedNet | 80.53 | 80.55 | 80.48 | 77.30 | 77.23 | 76.94 | 87.95 | 87.93 | 87.57
Multiplex ROBE-Z | 80.57 | 80.56 | 80.50 | 77.32 | 77.24 | 76.94 | 88.00 | 88.03 | 87.62
Multiplex PQ | 80.43 | 80.49 | 80.54 | 77.39 | 77.29 | 76.96 | 88.81 | 88.69 | 88.09
Multiplex QR | 80.22 | 80.28 | 80.48 | 77.29 | 77.16 | 76.90 | 88.83 | 88.53 | 88.27
Figure 3: Pareto frontier of multiplexed and original (non-multiplexed)
embedding methods (top-left is better).

###  5.2 Industrial Deployments of Unified embedding in Web-scale Systems

Among the proposed approaches, Unified Embedding (hashing trick +
multiplexing) is uniquely positioned to address infrastructure and latency
constraints associated with training and serving web-scale systems. To adapt
to features with variable dimensions, we adopt Multi-size Unified Embedding in
practice, and perform variable (typically 1~6) row lookups for each feature
(with concatenation) depending on the desired width. This is similar to
Multiplex PQ, which looks up multiple rows for all features. We discuss how to
adopt Unified Embedding in production SAR systems, where it has already served
billions of users through launches in over a dozen models. We also present an
experimental study of Unified Embedding in offline and online A/B experiments.

#### Experiment and production setup

To test the robustness and generalization capability of Unified Embedding, we
conduct offline and online experiments with five key models from various SAR
domains , including commerce, apps, and short-form videos. These systems
represent a diverse set of production model architectures powered by state-of-
the-art techniques, including two-tower retrieval models with LogQ correction
(Yi et al., 2019), DCN-V2 (Wang et al., 2021), and MMOE (Zhao et al., 2019).
These models handle a wide range of prediction tasks, including candidate
retrieval, click-through rate (CTR), conversion rate (CVR) prediction
(Chapelle, 2014), and multi-task user engagement modeling.

All of these production models are continuously trained and updated in a
streaming fashion, with the embedding tables being the dominant component
(often >99%) in terms of model parameters (Anil et al., 2022; Fahrbach et al.,
2023). Many of the baseline embedding methods are intuitive yet quite strong
(e.g., feature hashing and multiple hashing), and have been tuned by AutoML
and human heuristics (Anil et al., 2022). In fact, these baseline embedding
learning approaches have roughly stayed the same for the past five years, with
various efforts failing to improve them through novel techniques.

#### Practical benefits

Unified Embedding tables offer solutions to several challenging and practical
issues in large-scale embedding learning systems.

  * $\bullet$

Simple configuration: With standard embedding methods, we must independently
tune the table size and dimension for each feature. Hyperparameter tuning is
an arduous process due to the large number of categorical features used in
production (hundreds if not thousands). Unified Embedding tables are far
simpler to configure: the total table size is calculated based on the total
memory budget, and we only need to tune the dimension on a per-feature
basis—easily accomplished via AutoML (Bender et al., 2020) or attention-based
search methods (Yasuda et al., 2023). This yields roughly a 50% reduction in
hyperparameters.

  * $\bullet$

Adapt to dynamic feature distributions: In practice, the vocabulary size of
each feature changes over time (new IDs enter the system on a daily basis,
while stale items gradually vanish). For example, in a short video platform,
we expect a highly dynamic video ID vocabulary with severe churn. In
e-commerce, a significant number of new products are added during the holiday
season compared to off-season. Thus, a fixed number of buckets for a given
table can often lead to sub-optimal performance. Unified Embedding tables
offer a large parameter space that is shared across all features, which can
better accommodate fluctuations in feature distributions.

  * $\bullet$

Hardware compatibility: Machine learning accelerators and frameworks have co-
evolved with algorithms to support common use-cases, and the “row embedding
lookup” approach has been the standard technique for the past decade. While
Unified Embedding tables are well-supported by the latest TPUs (Jouppi et al.,
2023) and GPUs (Wei et al., 2022b; Mudigere et al., 2022), many of the latest
advanced embedding methods require memory access patterns that are not as
compatible with ML accelerators.

#### Offline and online results

Table 2 displays the results of our offline and online experiments for Unified
Embedding. It was applied to production models with vocabulary sizes spanning
from 10M to 10B. We observe substantial improvements across all models. Note
that the offline metrics and the key business metrics for different models may
be different, and the gains are not directly comparable. For offline, the
models are evaluated using AUC (higher is better), Recall@1 (higher is
better), and RMSE (lower is better). From these experiments, we found it
provides greater benefits in scenarios where (i) the vocabulary sizes for
features are larger, and (ii) the vocabulary is more dynamic (e.g., suffers
from a high churn rate). For instance, an overwhelming number of new short-
form videos are produced daily, creating a large and dynamic vocabulary.

Table 2: Unified Embedding applied to different production model architectures and tasks across various domains. Note that +0.1% is considered significant due to the large traffic in online A/B experiments. All multiplexed models are neutral or better in model size and training/serving costs. Task | pCTR | Retrieval | Multi-Task Ranking | pCVR | pCTR
---|---|---|---|---|---
Domain | Products | Products | Short-form videos | Apps | Apps
Architecture | DCN-V2 | Two-tower | MMOE | DCN-V2 | DCN-V2
Vocabulary Size | ~10B | ~10B | ~1B | ~10M | ~10M
Offline Metric | AUC +2.2% |  Recall@1 +7.3% |  AUC +0.39% (task 1) RMSE -0.53% (task 2) | AUC +0.25% | AUC +0.17%
Online Metric | Positive | Positive | +0.62% | +0.44% | +0.11%

##  6 Conclusion

In this work, we propose a highly generalizable Feature Multiplexing framework
that allows multiple features to share the same embedding space. One of our
crucial observations is that models can learn to mitigate the effects of
inter-feature collisions, enabling a single embedding vector to represent
feature values from different vocabularies. Multiplexed versions of SOTA
embedding methods provide a Pareto-optimal tradeoff, and Unified Embedding
proves to be a particularly simple yet effective approach. We demonstrate that
a unified embedding table performs significantly better in both offline and
online experiments compared to highly-competitive baselines across multiple
web-scale ML systems. We believe that the interplay between feature
multiplexing, dynamic vocabularies, power-law feature distributions, and DNNs
provides interesting and important opportunities for future work.

## Acknowledgements

The authors would like to thank our amazing collaborators in helping develop
the research, integrate our approaches into production, and reviewing our
paper. Here is the list of contributors sorted in alphabetical order by last
name: Shuchao Bi, Bo Chang, Kevin Chang, Shuo Chen, Chen Cheng, Chris Collins,
Evan Ettinger, Minjie Fan, Gang Fu, Xing Gao, Eu-jin Goh, Matthew Gonzalgo,
Cristos Goodrow, Wenshuo Guo, Zhongze Hu, Gui Huan, Da Huang, Yanhe Huang,
Samuel Ieong, Arpith Jacob, Maciej Kula, George Kurian, Duo Li, Yang Li,
Yueling Li, Silva Lin, Liang Liu, Wenjing Ma, Lifeng Nai, Abdul Saleh, Mahesh
Sathiamoorthy, Edward Shen, Rakesh Shivanna, Jaideep Singh, Ryan Smith, Myles
Sussman, Jiaxi Tang, Alice Xu, Luning Yang, Tiansheng Yao, Wenxing Ye, Xinyang
Yi, Angel Yu, David Zats, Fan Zhang, Jerry Zhang, Tianyin Zhou, Yun Zhou,
Qinyun Zhu.

## References

  * Achlioptas (2001) D. Achlioptas.  Database-friendly random projections.  In _Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems_ , pages 274–281, 2001.
  * Anil et al. (2022) R. Anil, S. Gadanho, D. Huang, N. Jacob, Z. Li, D. Lin, T. Phillips, C. Pop, K. Regan, G. I. Shamir, R. Shivanna, and Q. Yan.  On the factory floor: ML engineering for industrial-scale ads recommendation models.  In J. Vinagre, M. Al-Ghossein, A. M. Jorge, A. Bifet, and L. Peska, editors, _Proceedings of the 5th Workshop on Online Recommender Systems and User Modeling co-located with the 16th ACM Conference on Recommender Systems, ORSUM@RecSys_ , 2022.
  * Bender et al. (2020) G. Bender, H. Liu, B. Chen, G. Chu, S. Cheng, P. Kindermans, and Q. V. Le.  Can weight sharing outperform random architecture search? An investigation with TuNAS.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR_ , pages 14311–14320. Computer Vision Foundation / IEEE, 2020.
  * Bengio et al. (2000) Y. Bengio, R. Ducharme, and P. Vincent.  A neural probabilistic language model.  In _Advances in Neural Information Processing Systems_ , pages 932–938, 2000.
  * Brown et al. (2020) T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33_ , 2020.
  * Bubeck et al. (2023) S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, P. Lee, Y. T. Lee, Y. Li, S. Lundberg, et al.  Sparks of artificial general intelligence: Early experiments with GPT-4.  _arXiv preprint arXiv:2303.12712_ , 2023.
  * Chapelle (2014) O. Chapelle.  Modeling delayed feedback in display advertising.  In _The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 1097–1105. ACM, 2014.
  * Chen et al. (2015) W. Chen, J. Wilson, S. Tyree, K. Weinberger, and Y. Chen.  Compressing neural networks with the hashing trick.  In _International Conference on Machine Learning_ , pages 2285–2294. PMLR, 2015.
  * Covington et al. (2016) P. Covington, J. Adams, and E. Sargin.  Deep neural networks for YouTube recommendations.  In _Proceedings of the 10th ACM Conference on Recommender Systems_ , pages 191–198, 2016.
  * Dahlgaard et al. (2017) S. Dahlgaard, M. Knudsen, and M. Thorup.  Practical hash functions for similarity estimation and dimensionality reduction.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Dasgupta and Gupta (2003) S. Dasgupta and A. Gupta.  An elementary proof of a theorem of Johnson and Lindenstrauss.  _Random Structures & Algorithms_, 22(1):60–65, 2003.
  * Desai and Shrivastava (2022) A. Desai and A. Shrivastava.  The trade-offs of model size in large recommendation models : 100GB to 10MB criteo-tb DLRM model.  In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=c9I_NArDIjD.
  * Desai et al. (2022) A. Desai, L. Chou, and A. Shrivastava.  Random offset block embedding (ROBE) for compressed embedding tables in deep learning recommendation systems.  _Proceedings of Machine Learning and Systems_ , 4:762–778, 2022.
  * Fahrbach et al. (2023) M. Fahrbach, A. Javanmard, V. Mirrokni, and P. Worah.  Learning rate schedules in the presence of distribution shift.  _arXiv preprint arXiv:2303.15634_ , 2023.
  * Freksen et al. (2018) C. B. Freksen, L. Kamma, and K. Green Larsen.  Fully understanding the hashing trick.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Hogan and Wind (1985) B. Hogan and H. W. Wind.  _Five Lessons: The Modern Fundamentals of Golf_.  1985\.
  * Jouppi et al. (2023) N. P. Jouppi, G. Kurian, S. Li, P. Ma, R. Nagarajan, L. Nai, N. Patil, S. Subramanian, A. Swing, B. Towles, et al.  Tpu v4: An optically reconfigurable supercomputer for machine learning with hardware support for embeddings.  _Proceedings of the 50th International Symposium of Computer Architecture_ , 2023.
  * Kang et al. (2021) W.-C. Kang, D. Z. Cheng, T. Yao, X. Yi, T. Chen, L. Hong, and E. H. Chi.  Learning to embed categorical features without embedding tables for recommendation.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 840–850, 2021.
  * Li et al. (2006) P. Li, T. J. Hastie, and K. W. Church.  Very sparse random projections.  In _Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 287–296, 2006.
  * Mikolov et al. (2013) T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean.  Distributed representations of words and phrases and their compositionality.  In _Advances in Neural Information Processing Systems_ , pages 3111–3119, 2013.
  * Mitzenmacher (2001) M. Mitzenmacher.  The power of two choices in randomized load balancing.  _IEEE Transactions on Parallel and Distributed Systems_ , 12(10):1094–1104, 2001.
  * Moody (1988) J. Moody.  Fast learning in multi-resolution hierarchies.  _Advances in Neural Information Processing Systems_ , 1988.
  * Mudigere et al. (2022) D. Mudigere, Y. Hao, J. Huang, Z. Jia, A. Tulloch, S. Sridharan, X. Liu, M. Ozdal, J. Nie, J. Park, L. Luo, J. A. Yang, L. Gao, D. Ivchenko, A. Basant, Y. Hu, J. Yang, E. K. Ardestani, X. Wang, R. Komuravelli, C. Chu, S. Yilmaz, H. Li, J. Qian, Z. Feng, Y. Ma, J. Yang, E. Wen, H. Li, L. Yang, C. Sun, W. Zhao, D. Melts, K. Dhulipala, K. R. Kishore, T. Graf, A. Eisenman, K. K. Matam, A. Gangidi, G. J. Chen, M. Krishnan, A. Nayak, K. Nair, B. Muthiah, M. khorashadi, P. Bhattacharya, P. Lapukhov, M. Naumov, A. Mathews, L. Qiao, M. Smelyanskiy, B. Jia, and V. Rao.  Software-hardware co-design for fast and scalable training of deep learning recommendation models.  In _The 49th Annual International Symposium on Computer Architecture_ , pages 993–1011. ACM, 2022.
  * Naumov et al. (2019) M. Naumov, D. Mudigere, H.-J. M. Shi, J. Huang, N. Sundaraman, J. Park, X. Wang, U. Gupta, C.-J. Wu, A. G. Azzolini, et al.  Deep learning recommendation model for personalization and recommendation systems.  _arXiv preprint arXiv:1906.00091_ , 2019.
  * Papyan et al. (2020) V. Papyan, X. Han, and D. L. Donoho.  Prevalence of neural collapse during the terminal phase of deep learning training.  _Proceedings of the National Academy of Sciences_ , 117(40):24652–24663, 2020.
  * Rumelhart et al. (1986) D. E. Rumelhart, G. E. Hinton, and R. J. Williams.  Learning representations by back-propagating errors.  _Nature_ , 323(6088):533, 1986.
  * Shi et al. (2020) H.-J. M. Shi, D. Mudigere, M. Naumov, and J. Yang.  Compositional embeddings using complementary partitions for memory-efficient recommendation systems.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 165–175, 2020.
  * Song et al. (2019) W. Song, C. Shi, Z. Xiao, Z. Duan, Y. Xu, M. Zhang, and J. Tang.  Autoint: Automatic feature interaction learning via self-attentive neural networks.  In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_ , pages 1161–1170, 2019.
  * Svenstrup et al. (2017a) D. Svenstrup, J. Hansen, and O. Winther.  Hash embeddings for efficient word representations.  _Advances in Neural Information Processing Systems_ , 2017a.
  * Svenstrup et al. (2017b) D. Svenstrup, J. M. Hansen, and O. Winther.  Hash embeddings for efficient word representations.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA_ , pages 4928–4936, 2017b.  URL http://papers.nips.cc/paper/7078-hash-embeddings-for-efficient-word-representations.
  * Tsang and Ahle (2022) H. L.-H. Tsang and T. D. Ahle.  Clustering embedding tables, without first learning them.  _arXiv preprint arXiv:2210.05974_ , 2022.
  * Vadhan et al. (2012) S. P. Vadhan et al.  Pseudorandomness.  _Foundations and Trends in Theoretical Computer Science_ , 7(1–3):1–336, 2012.
  * Vaswani et al. (2017) A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin.  Attention is all you need.  _Advances in Neural Information Processing Systems_ , 2017.
  * Wang et al. (2021) R. Wang, R. Shivanna, D. Z. Cheng, S. Jain, D. Lin, L. Hong, and E. H. Chi.  DCN V2: improved deep & cross network and practical lessons for web-scale learning to rank systems.  In _The Web Conference 2021_ , pages 1785–1797. ACM / IW3C2, 2021\.
  * Wei et al. (2022a) J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou.  Chain of thought prompting elicits reasoning in large language models.  _arXiv preprint arXiv:2201.11903_ , 2022a.
  * Wei et al. (2022b) Y. Wei, M. Langer, F. Yu, M. Lee, J. Liu, J. Shi, and Z. Wang.  A GPU-specialized inference parameter server for large-scale deep recommendation models.  In _Sixteenth ACM Conference on Recommender Systems_ , pages 408–419. ACM, 2022b.
  * Weinberger et al. (2009) K. Weinberger, A. Dasgupta, J. Langford, A. Smola, and J. Attenberg.  Feature hashing for large scale multitask learning.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pages 1113–1120, 2009.
  * Yasuda et al. (2023) T. Yasuda, M. Bateni, L. Chen, M. Fahrbach, G. Fu, and V. Mirrokni.  Sequential attention for feature selection.  In _Proceedings of the 11th International Conference on Learning Representations (ICLR)_ , 2023.
  * Yi et al. (2019) X. Yi, J. Yang, L. Hong, D. Z. Cheng, L. Heldt, A. Kumthekar, Z. Zhao, L. Wei, and E. H. Chi.  Sampling-bias-corrected neural modeling for large corpus item recommendations.  In _Proceedings of the 13th ACM Conference on Recommender Systems_ , pages 269–277. ACM, 2019.
  * Zhao et al. (2019) Z. Zhao, L. Hong, L. Wei, J. Chen, A. Nath, S. Andrews, A. Kumthekar, M. Sathiamoorthy, X. Yi, and E. H. Chi.  Recommending what video to watch next: a multitask ranking system.  In _Proceedings of the 13th ACM Conference on Recommender Systems_ , pages 43–51. ACM, 2019.

##  Appendix A Theory

###  A.1 Missing analysis from Section 4.1

######  Lemma A.1 ((Weinberger et al., 2009, Lemma 2)).

For any $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$,
$\mathbb{E}_{h,\xi}[\langle\phi(\mathbf{x}),\phi(\mathbf{y})\rangle]=\langle\mathbf{x},\mathbf{y}\rangle.$
Furthermore, we have

$\displaystyle\textnormal{Var}_{h,\xi}\left(\left\langle\phi(\mathbf{x}),\phi(\mathbf{y})\right\rangle\right)$
$\displaystyle=\frac{1}{m}\sum_{i\neq
j}x_{i}^{2}y_{j}^{2}+x_{i}y_{i}x_{j}y_{j}$
$\displaystyle=\frac{1}{m}\left(\left\langle\mathbf{x},\mathbf{x}\right\rangle\left\langle\mathbf{y},\mathbf{y}\right\rangle+\left\langle\mathbf{x},\mathbf{y}\right\rangle\left\langle\mathbf{x},\mathbf{y}\right\rangle-2\left\langle\mathbf{x}\circ\mathbf{y},\mathbf{x}\circ\mathbf{y}\right\rangle\right),$

where $\mathbf{x}\circ\mathbf{y}\in\mathbb{R}^{n}$ denotes the Hadamard
product of $\mathbf{x}$ and $\mathbf{y}$.

See 4.2

###### Proof.

The results for $\mu_{U}$, $\mu_{H}$ and $\sigma_{U}^{2}$ directly follow from
Lemma A.1, and observing that

$\left\langle\mathbf{x}\circ\mathbf{y},\mathbf{x}\circ\mathbf{y}\right\rangle=\left\langle\mathbf{x}\circ\mathbf{x},\mathbf{y}\circ\mathbf{y}\right\rangle=\left\langle\mathbf{x},\mathbf{y}\right\rangle,$

since $\mathbf{x},\mathbf{y}\in\\{0,1\\}^{N_{1}+N_{2}}$.

To compute $\sigma_{H}^{2}$, first decompose the inner product

$\langle\phi(\mathbf{x}),\phi(\mathbf{y})\rangle=\langle\phi_{h_{1},\xi_{1}}(\mathbf{x}_{1}),\phi_{h_{1},\xi_{1}}(\mathbf{y}_{1})\rangle+\langle\phi_{h_{2},\xi_{2}}(\mathbf{x}_{2}),\phi_{h_{2},\xi_{2}}(\mathbf{y}_{2})\rangle.$

Since the hash functions $h_{1}$, $\xi_{1}$, $h_{2}$, $\xi_{2}$ are
independent, it follows that $\sigma_{H}^{2}$ is the sum of the variances of
$\langle\phi_{h_{1},\xi_{1}}(\mathbf{x}_{1}),\phi_{h_{1},\xi_{1}}(\mathbf{y}_{1})\rangle$
and
$\langle\phi_{h_{2},\xi_{2}}(\mathbf{x}_{2}),\phi_{h_{2},\xi_{2}}(\mathbf{y}_{2})\rangle$,
so we can again invoke Lemma A.1. ∎

###  A.2 Derivation of gradients

For easy reference, we re-introduce our logistic regression setting here. In
Figure 4, we reproduce part of Figure 2 from the main text to further help
clarify our notation.

Recall from the main text that we are interested in a logistic regression
model with trainable embeddings for binary classification (i.e., a single-
layer neural network with hashed one-hot encodings as input). This corresponds
to our supervised learning framework (Equation 1) where
$f(\mathbf{z};\boldsymbol{\theta})$ is the sigmoid function
$\sigma_{\boldsymbol{\theta}}(\mathbf{z})=1/(1+\exp(-\langle\mathbf{z},\boldsymbol{\theta}\rangle))$
and $\ell$ is the binary cross-entropy loss.

We concatenate the embeddings of each feature, which means that the input to
$f(\mathbf{z};\boldsymbol{\theta})$ is
$\mathbf{z}=g(\mathbf{x};\mathbf{E})=[\mathbf{e}_{h_{1}(\mathbf{x}_{1})},\mathbf{e}_{h_{2}(\mathbf{x}_{2})},\dots,\mathbf{e}_{h_{T}(\mathbf{x}_{T})}]$,
where $\mathbf{e}_{h_{t}(\mathbf{x}_{t})}$ is the embedding for the $t$-th
feature value in example $\mathbf{x}$.

We also partition the logistic regression weights
$\boldsymbol{\theta}=[\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2},\dots,\boldsymbol{\theta}_{T}]$,
so that embedding $\mathbf{e}_{h_{t}(\mathbf{x}_{t})}$ for feature $t$ is
projected via $\boldsymbol{\theta}_{t}\in\mathbb{R}^{M}$.

For notational convenience we also partition the dataset by label. We write
$D_{0}=\\{(\mathbf{x}_{i},y_{i})\in D:y_{i}=0\\}$ and
$D_{1}=\\{(\mathbf{x}_{i},y_{i})\in D:y_{i}=1\\}$. Using this notation, we can
write the logistic regression objective as follows:

$\mathcal{L}_{D}(\mathbf{E},\boldsymbol{\theta})=-\sum_{(\mathbf{x},y)\in
D_{0}}\log\left(\frac{1}{1+\exp(-\langle\boldsymbol{\theta},g(\mathbf{x};\mathbf{E})\rangle)}\right)-\sum_{(\mathbf{x},y)\in
D_{1}}\log\left(\frac{1}{1+\exp(\langle\boldsymbol{\theta},g(\mathbf{x};\mathbf{E})\rangle)}\right).$

We proceed by writing the loss as a sum over vocabulary pairs rather than
examples. We consider the problem for two categorical features with
vocabularies $V_{1}$ and $V_{2}$ to simplify the presentation, and we use the
notation $C_{u,v,0}$ to denote the number of co-occurences of $(u,v)\in
V_{1}\times V_{2}$ in dataset $D_{0}$. Likewise, $C_{u,v,1}$ denotes the
corresponding quantity for $D_{1}$. We also let
$\mathbf{e}_{u,v}=[\mathbf{e}_{h_{1}(u)},\mathbf{e}_{h_{2}(v)}]$ so that the
inner product
$\langle[\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2}],[\mathbf{e}_{h_{1}(u)},\mathbf{e}_{h_{2}(v)}]\rangle$
can be written concisely as $\boldsymbol{\theta}^{\top}\mathbf{e}_{u,v}$. It
follows that

$\mathcal{L}_{D}(\mathbf{E},\boldsymbol{\theta})=-\sum_{u\in V_{1}}\sum_{v\in
V_{2}}C_{u,v,0}\log\left(\frac{1}{1+\exp(-\boldsymbol{\theta}^{\top}\mathbf{e}_{u,v})}\right)+C_{u,v,1}\log\left(\frac{1}{1+\exp(\boldsymbol{\theta}^{\top}\mathbf{e}_{u,v})}\right).$

After combining the sigmoid functions, we get the following expression:

$\mathcal{L}_{D}(\mathbf{E},\boldsymbol{\theta})=-\sum_{u\in V_{1}}\sum_{v\in
V_{2}}C_{u,v,0}\log\exp(\boldsymbol{\theta}^{\top}\mathbf{e}_{u,v})-(C_{u,v,0}+C_{u,v,1})\log(1+\exp(\boldsymbol{\theta}^{\top}\mathbf{e}_{u,v})).$

Figure 4: Illustration of the logistic regression model, annotated with
notation that corresponds to our theoretical analysis.

To get the gradients with respect to $\mathbf{E}_{h(u)}$ (the embedding
parameters used to represent value $u$), we first take the gradient with
respect to $\mathbf{E}_{m}$. These parameters accumulate gradient
contributions from any value assigned to bucket $m$ (i.e. for which
$\mathbbm{1}_{u,m}$ is one). It is then straightforward to express
$\nabla_{\mathbf{E}_{h(u)}}\mathcal{L}_{D}(\mathbf{E},\theta)$ in terms of the
other values $v$ that collide with $u$ (i.e. for which $\mathbbm{1}_{u,v}$ is
one).

#### Collisionless Embeddings:

Because each row $\mathbf{E}_{m}$ corresponds to a single value, we can take
the gradient with respect to $\mathbf{E}_{h(u)}$ directly.

$\nabla_{\mathbf{E}_{h(u)}}\mathcal{L}_{D}(\mathbf{E},\theta)=\theta_{1}\sum_{v\in
V_{2}}C_{u,v,0}-(C_{u,v,0}+C_{u,v,1})\sigma_{\theta}(\mathbf{e}_{u,v})$

#### Hash Embeddings:

Here, row $m$ corresponds to any value that is assigned to bucket $m$ (i.e.
for which $\mathbbm{1}_{u,m}$ is one). We find the gradient for the embedding
table corresponding to the first feature $V_{1}$.

$\nabla_{\mathbf{E}_{m}}\mathcal{L}_{D}(\mathbf{E},\theta)=\sum_{u\in
V_{1}}\mathbbm{1}_{u,m}\theta_{1}\sum_{v\in
V_{2}}C_{u,v,0}-(C_{u,v,0}+C_{u,v,1})\sigma_{\theta}(\mathbf{e}_{u,v})$

The interpretation of this equation is that with hash collisions, the gradient
now contains contributions from any value assigned to the bucket. If we
consider the bucket selected by a specfic value $u\in V_{1}$, we can write
this gradient as follows.

$\displaystyle\nabla_{\mathbf{E}_{h(u)}}\mathcal{L}_{D}(\mathbf{E},\theta)$
$\displaystyle=\theta_{1}\sum_{v\in
V_{2}}C_{u,v,0}-(C_{u,v,0}+C_{u,v,1})\sigma_{\theta}(\mathbf{e}_{u,v})$
$\displaystyle+\theta_{1}\sum_{\begin{subarray}{c}w\in V_{1}\\\ w\neq
u\end{subarray}}\mathbbm{1}_{u,w}\sum_{v\in
V_{2}}C_{u,w,0}-(C_{u,w,0}+C_{u,w,1})\sigma_{\theta}(\mathbf{e}_{u,v})$

#### Unified Embeddings:

Here, row $m$ might correspond to any value – even ones from other features.
The gradient with respect to $\mathbf{E}_{m}$ now contains additional
components.

$\displaystyle\nabla_{\mathbf{E}_{m}}\mathcal{L}_{D}(\mathbf{E},\theta)$
$\displaystyle=\sum_{u\in V_{1}}\mathbbm{1}_{u,m}\theta_{1}\sum_{v\in
V_{2}}C_{u,v,0}-(C_{u,v,0}+C_{u,v,1})\sigma_{\theta}(\mathbf{e}_{u,v})$
$\displaystyle+\sum_{v\in V_{2}}\mathbbm{1}_{v,m}\theta_{2}\sum_{u\in
V_{1}}C_{u,v,0}-(C_{u,v,0}+C_{u,v,1})\sigma_{\theta}(\mathbf{e}_{u,v})$

Re-writing this gradient to be in terms of $\mathbf{E}_{h(u)}$ (for $u\in
V_{1}$) reveals that in the unified embedding case, the gradient contains the
collisionless component, an intra-feature component, and an inter-feature
component.

$\displaystyle\nabla_{\mathbf{E}_{h(u)}}\mathcal{L}_{D}(\mathbf{E},\theta)$
$\displaystyle=\theta_{1}\sum_{v\in
V_{2}}C_{u,v,0}-(C_{u,v,0}+C_{u,v,1})\sigma_{\theta}(\mathbf{e}_{u,v})$
$\displaystyle+\theta_{1}\sum_{\begin{subarray}{c}w\in V_{1}\\\ w\neq
u\end{subarray}}\mathbbm{1}_{u,w}\sum_{v\in
V_{2}}C_{w,v,0}-(C_{w,v,0}+C_{w,v,1})\sigma_{\theta}(\mathbf{e}_{u,v})$
$\displaystyle+\theta_{2}\sum_{v\in V_{2}}\mathbbm{1}_{u,v}\sum_{w\in
V_{1}}C_{w,v,0}-(C_{w,v,0}+C_{w,v,1})\sigma_{\theta}(\mathbf{e}_{w,u})$

##  Appendix B Experiments

Figure 5: Illustration of baseline embedding methods, all which are compatible
with feature multiplexing.

Figure 5 illustrates our baselines. We describe the methods (and their
hyperparameters) below.

  1. 1.

Collisionless tables assign each value of each feature a unique d-dimensional
representation. The only hyperparameter is $d$, the embedding dimension.

  2. 2.

Hashing trick tables begin with a fixed number of representations and allow
values to collide within features. Here, each table has two hyperparameters:
$d$ (the dimension) and $M$ (the table size). The inspiration for this method
is most commonly attributed to Weinberger et al. (2009), and it is widely used
across industry.

  3. 3.

Unified embeddings use a similar process but allow values to collide within
and across features. Unified embeddings have the same hyperparameters as hash
tables, but there is now only one table size to tune.

  4. 4.

Compositional QR tables use multiple small tables for each feature, then
perform element-wise multiplication of the resulting embeddings. The
hyperparameters are $k$ (the number of tables), $M$ (the table size), and $d$
(the embedding dimension). This method corresponds to the compositional
embedding of Shi et al. (2020), using the “concatenation” aggregation
strategy.

  5. 5.

Compositional PQ tables use multiple small tables for each feature, then
perform concatenation. We call this “product quantization” because it is
similar to the vector compression technique. The hyperparameters are the same
as for QR tables. This method corresponds to the compositional embedding of
Shi et al. (2020), using the “element-wise product” aggregation strategy.

  6. 6.

HashedNet tables look up each dimension of each embedding separately in a
flat, shared memory. The only extra hyperparameter is the size of the shared
parameter array. This is the method of Chen et al. (2015), but with the
HashedNet algorithm applied only to the embedding tables.

  7. 7.

ROBE-Z tables look up contiguous blocks of $Z$ dimensions in a shared memory
(we show $Z=2$). ROBE-Z has two extra hyperparameters: the size of the shared
parameter array, and the number of blocks. Note that one can use a different
$Z$ for each block. For simplicity, we do not do this. This is the method used
by Desai et al. (2022) and by Desai and Shrivastava (2022).

  8. 8.

Hash embedding tables (or multihash, in Figure 5) perform multiple lookups
into the same table, then combine the embeddings using a learned weighted
combination. Multihash tables have several hyperparameters and are therefore
trickier to tune well. The parameters are $M_{1}$, the size of the embedding
table, $M_{2}$, the size of the importance weight table, $k$, the number of
lookups and the dimension of the importance weight table, and $d$, the
embedding dimension. This method was proposed by Svenstrup et al. (2017b).

#### Hyperparameter tuning:

For all methods, we consider sixteen logarithmically-spaced memory budgets:
[0.001, 0.002, 0.005, 0.007, 0.01, 0.02, 0.05, 0.07, 0.1, 0.2, 0.5, 0.7, 1.0,
2.0, 5.0, 10.0] times the memory required for the collisionless table. We
conduct 5 independent training runs for each hyperparameter configuration. For
non-multiplexed representations, we allocate parameters to features based on
vocabulary size. For example, a feature with 10% of the total vocabulary will
be allocated 10% of the total parameter budget. We also tuned the network
architecture and optimizer parameters. To avoid biasing our results in favor
of any one method, we only used collisionless tables to tune these parameters.
The embedding hyperparameters were tuned using grid search over the following
choices.

  * $\bullet$

Hash embeddings: For hash embeddings (and multiplexed hash embeddings), we
chose the number of lookups $k$ from [2, 3]. We also introduce an allocation
parameter $p$ that describes what fraction of the memory budget is used for
the embedding table (e.g., $M_{1}$) versus the importance table (e.g.,
$M_{2}$). For example, $p=0.2$ means that the embedding table are allocated
80% of the budget and the importance weight tables receives the remaining 20%.
We chose $p$ from [0.05, 0.1, 0.2].

  * $\bullet$

ROBE-Z: We chose the number of lookups from [2, 4, 8, 16]. This corresponds to
different values of $Z$ depending on the embedding dimension of the dataset.

  * $\bullet$

PQ embeddings: For PQ embeddings (and multiplexed PQ), we selected the number
of lookups $k$ from [2, 3, 4, 8, 16]. We note that this parameter affects
performance in different ways depending on the parameter budget – smaller
budgets require a greater number of lookups for performance.

  * $\bullet$

QR embeddings: For QR embeddings (and multiplexed QR), we selected the number
of components $k$ from [2, 3, 4].

  * $\bullet$

Other methods: Our other methods did not require search over extra
hyperparameters. For the special case of collisionless embeddings, we simply
ran 5 replicates at a single parameter budget (1.0).

Taken together, we conducted 3205 training runs for each dataset to produce
Figure 3. Note that in some cases (e.g., Avazu with a budget of $5,10$), some
runs with expensive configurations did not finish – we report only those
results that completed training within 2 days. Finally, the total number of
training runs (across all datasets) is somewhat higher, to account for our
preliminary tuning over the architecture and optimizer parameters. We estimate
that roughly 10,000 training runs were performed in total.

#### Criteo:

We use the 7-day version of Criteo from the Kaggle competition. It is widely-
known that additional filtering / merging of the vocabulary is necessary to
achieve SOTA results on Criteo. We merge the least-frequent values, trimming
the vocabulary down to the size listed in Table 4. For the network, we used a
stack of two DCN cross layers followed by a 2-layer neural network with 748
nodes in each layer. This model gives a realistic picture of the tradeoff
because near-SOTA performance on Criteo can be achieved with a well-tuned
3-layer feedforward network with 748 nodes and collisionless embeddings (Wang
et al., 2021). We trained with a batch size of 512 for 300K steps using Adam
with a learning rate of 0.0002. The full parameter-accuracy tradeoffs are
presented in Figure 6.

#### Avazu:

We use the version of Avazu from the Kaggle competition, but we use a
different train-test split than the original. Following the practice of Song
et al. (2019), we combine the train and test sets and do a 90-10 split after
shuffling. We also apply vocabulary pruning to this dataset, with the results
in Table 4. Note that we mod the “hour” feature by $24$ and do not use the
“id” feature. For the neural network, we use a stack of one DCN cross layer
followed by two fully connected feedforward layers of 512 nodes each. We
trained with a batch size of 512 for 300K steps using Adam with a learning
rate of 0.0002. The full parameter-accuracy tradeoffs are presented in Figure
7.

#### Movielens:

We use the Movielens-1M dataset with the same preprocessing used by Wang et
al. (2021). We only use the “userId,” “movieId,” “zipcode,” “age,”
“occupation” and “gender” features. We always use a collisionless table to
embed the “gender” feature due to small vocabulary size. We used a network
composed of a single DCN cross layer followed by a single fully-connected
layer with 192 nodes. We trained with a batch size of 128 for 300K steps using
Adam with a learning rate of 0.0002. The full parameter-accuracy tradeoffs are
presented in Figure 8.

Figure 6: Full parameter-accuracy tradeoffs for all methods on the Criteo
dataset. Naming convention is the same as in Table 1. Note the log scale and
that plots do not share the y-axis scale. The error bar width denotes the
standard deviation over 5 model training runs.

Figure 7:  Full parameter-accuracy tradeoffs for all methods on the Avazu
dataset. Naming convention is the same as in Table 1. Note the log scale and
that plots do not share the y-axis scale. The error bar width denotes the
standard deviation over 5 model training runs.

Figure 8:  Full parameter-accuracy tradeoffs for all methods on the
Movielens-1M dataset. Naming convention is the same as in Table 1. Note the
log scale and that plots do not share the y-axis scale. The error bar width
denotes the standard deviation over 5 model training runs.

Table 3: Criteo Vocabulary Pruning. Feature | Vocabulary Size
---|---
14 | 676
15 | 533
16 | 17447
17 | 19995
18 | 180
19 | 13
20 | 9693
21 | 337
22 | 3
23 | 14637
24 | 4378
25 | 17795
26 | 3067
27 | 26
28 | 6504
29 | 18679
30 | 10
31 | 3102
32 | 1557
33 | 3
34 | 18230
35 | 10
36 | 14
37 | 13079
38 | 56
39 | 10581

Table 4: Avazu Vocabulary Pruning. Feature | Vocabulary Size
---|---
C1 | 8
C14 | 2309
C15 | 9
C16 | 10
C17 | 405
C18 | 5
C19 | 66
C20 | 167
C21 | 56
app_category | 29
app_domain | 277
app_id | 4438
banner_pos | 8
device_conn_type | 5
device_id | 67767
device_ip | 163804
device_model | 6217
device_type | 6
site_category | 24
site_domain | 3887
site_id | 3317
hour | 24


reader, we include a proof for the simpler two phase setting. In that case one
has to prove (83) with

(84)
$\tilde{E}^{B_{1}}_{t}(u,\beta)=\frac{1}{\sqrt{t}}\int_{B_{1}}\beta(1-u)G_{t}*udx,\
u:B_{1}\to[0,1]$

and

(85) $\tilde{E}_{t}(u)=\frac{1}{\sqrt{t}}\int_{B_{1}}k_{t}*(1-u)udx,\
u:B_{1}\to[0,1].$

###### Proof of Theorem 16 in the two phase setting.

Clearly, statement (83) is a consequence of the following two items.

(86) $\displaystyle\sqrt{h_{1}}^{k+1}E_{h_{1}}^{B_{1}}(u,\beta)$
$\displaystyle\leq\sqrt{h_{2}}^{k+1}E_{h_{2}}^{B_{1}}(u,\beta)\ $
$\displaystyle\forall 0<h_{1}\leq h_{2},$ (87) $\displaystyle
E_{N^{2}h}^{B_{1}}(u,\beta)$ $\displaystyle\leq
E_{h}^{B_{1}}(u,\beta)+C(N-1)\sqrt{h}\|D\beta\|_{\infty}\tilde{E}_{h}(u)\ $
$\displaystyle\forall N\in\mathbf{N},\ \forall h>0.$

To see this, let $0<h\leq h_{0}$. Let $N\in\mathbf{N}$ be such that

$(N-1)\sqrt{h}\leq\sqrt{h_{0}}<N\sqrt{h}.$

Then we have

$\displaystyle E_{h_{0}}^{B_{1}}(u,\beta)$
$\displaystyle\stackrel{{\scriptstyle{\eqref{eq:logarithmic_mon}}}}{{\leq}}\left(\frac{N\sqrt{h}}{\sqrt{h_{0}}}\right)^{k+1}E_{N^{2}h}^{B_{1}}(u,\beta)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:disc_mon}}}{{\leq}}\left(\frac{N\sqrt{h}}{\sqrt{h_{0}}}\right)^{k+1}\left(E_{h}^{B_{1}}(u,\beta)+C(N-1)\sqrt{h}\|D\beta\|_{\infty}\tilde{E}_{h}(u)\right)$
$\displaystyle\stackrel{{\scriptstyle\phantom{\eqref{}}}}{{\leq}}\left(\frac{\sqrt{h}+\sqrt{h_{0}}}{\sqrt{h_{0}}}\right)^{k+1}E_{h}^{B_{1}}(u,\beta)+C\sqrt{h_{0}}\|D\beta\|_{\infty}\tilde{E}_{h}(u).$

We are thus left with proving (86) and (87).
Item (86). This follows by showing that

$\frac{d}{d\sqrt{h}}\left(\sqrt{h}^{k+1}E_{h}^{B_{1}}(u,\beta)\right)\geq 0,$

which follows by differentiation. Indeed,

$\displaystyle\frac{d}{d\sqrt{h}}\left(\sqrt{h}^{k+1}E_{h}^{B_{1}}(u,\beta)\right)$
$\displaystyle=\frac{d}{d\sqrt{h}}\int_{B_{1}}\beta(1-u)G_{1}\left(\frac{z}{\sqrt{h}}\right)udx$
$\displaystyle=-\frac{1}{\sqrt{h}}\int_{B_{1}}\beta(1-u)\nabla
G_{1}\left(\frac{z}{\sqrt{h}}\right)\cdot\frac{z}{\sqrt{h}}udx\geq 0.$

Item (87). We let $0<h_{0}$ be such that $\sqrt{h_{0}}=\sqrt{h_{1}}+\sqrt{h}$.
Then we observe that

$\displaystyle\begin{aligned}
\mathllap{\sqrt{h_{0}}E_{h_{0}}^{B_{1}}(u,\beta)}&=\int_{B_{1}}\int_{\mathbf{R}^{k}}\beta(x)(1-u)(x)G_{1}(z)u(x-\sqrt{h_{1}}z-\sqrt{h}z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
\mathllap{}\leq&\int_{B_{1}}\int_{\mathbf{R}^{k}}\beta(x)(1-u)(x-\sqrt{h_{1}}z)G_{1}(z)u(x-\sqrt{h_{1}}z-\sqrt{h}z)dzdx\\\
&+\int_{B_{1}}\int_{\mathbf{R}^{k}}\beta(x)(1-u)(x)G_{1}(z)u(x-\sqrt{h_{1}}z)dzdx,\end{aligned}$

where we used the inequality

$\displaystyle(1-u)u^{\prime\prime}\leq(1-u^{\prime})u^{\prime\prime}+(1-u)u^{\prime},\
\forall u,u^{\prime},u^{\prime\prime}\in[0,1],$

applied to
$u=u(x),u^{\prime}=u(x-\sqrt{h_{1}}z),u^{\prime\prime}=u(x-\sqrt{h}z-\sqrt{h_{1}}z)$.
We record that the second term on the right hand side is equal to

$\displaystyle\sqrt{h_{1}}E_{h_{1}}^{B_{1}}(u,\beta).$

The other term is estimated as follows. First we change variable in $x$, and
then we estimate
$|\beta(x)-\beta(x-\sqrt{h_{1}}z)|\leq\|D\beta\|_{\infty}\sqrt{h_{1}}|z|$ to
get

$\displaystyle\begin{aligned}
\int_{\mathbf{R}^{k}}\int_{B_{1}-\sqrt{h_{1}}z}\beta(x+\sqrt{h}z)(1-u)(x)G_{1}(z)u(x-\sqrt{h}z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
\leq&\int_{\mathbf{R}^{k}}\int_{B_{1}-\sqrt{h_{1}}z}\beta(x)(1-u)(x)G_{1}(z)u(x-\sqrt{h}z)dxdz\\\
&+\sqrt{h_{1}}\|D\beta\|_{\infty}\int_{\mathbf{R}^{k}}\int_{B_{1}-\sqrt{h_{1}}z}(1-u)(x)|z|G_{1}(z)u(x-\sqrt{h}z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
=&\int_{\mathbf{R}^{k}}\int_{B_{1}}\beta(x)(1-u)(x)G_{1}(z)u(x-\sqrt{h}z)dxdz\\\
&+\sqrt{h_{1}}\|D\beta\|_{\infty}\int_{\mathbf{R}^{k}}\int_{B_{1}-\sqrt{h_{1}}z}(1-u)(x)k_{1}(z)u(x-\sqrt{h}z)dzdx,\end{aligned}$

where in the last equality we used the fact that $\beta$ is supported in
$B_{1}$. Observe that

$\displaystyle\begin{aligned}
\int_{\mathbf{R}^{k}}\int_{B_{1}-\sqrt{h_{1}}z}(1-u)(x)k_{1}(z)u(x-\sqrt{h}z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
\leq\int_{\mathbf{R}^{k}}\int_{\mathbf{R}^{k}}(1-u)(x)k_{1}(z)u(x-\sqrt{h}z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
=&\int_{\mathbf{R}^{k}}\int_{\mathbf{R}^{k}}(1-u)(x)k_{h}(z)u(x-z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
=&\int_{\mathbf{R}^{k}}\int_{\mathbf{R}^{k}}(1-u)(x)k_{h}(z-x)u(z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
=&\int_{\mathbf{R}^{k}}\int_{B_{1}}(1-u)(x)k_{h}(z-x)u(z)dzdx\end{aligned}$
$\displaystyle\begin{aligned}
=&\int_{B_{1}}k_{h}*(1-u)(z)u(z)dz=\sqrt{h}\tilde{E}_{h}(u).\end{aligned}$

Here we used that $u$ is supported in $B_{1}$. Putting things together we
obtain that

(88) $\displaystyle\sqrt{h_{0}}E_{h_{0}}^{B_{1}}(u,\beta)\leq$
$\displaystyle\sqrt{h_{1}}E_{h_{1}}^{B_{1}}(u,\beta)+\sqrt{h}E_{h}^{B_{1}}(u,\beta)$
$\displaystyle+\sqrt{h_{1}}\sqrt{h}\|D\beta\|_{\infty}\tilde{E}_{h}(u).$

If we now apply inductively (88) with $h_{1}=(N-1)^{2}h$ and $h_{0}=N^{2}h$
one gets

$\displaystyle N\sqrt{h}E_{N^{2}h}^{B_{1}}(u,\beta)$ $\displaystyle\leq
N\sqrt{h}E_{h}^{B_{1}}(u,\beta)+\sum_{i=1}^{N-1}ih\|D\beta\|_{\infty}\tilde{E}_{h}(u)$
$\displaystyle=N\sqrt{h}E_{h}^{B_{1}}(u,\beta)+\frac{(N-1)N}{2}h\|D\beta\|_{\infty}\tilde{E}_{h}(u).$

Dividing by $N\sqrt{h}$ yields (87). ∎

## Data Availability

The datasets generated during and/or analysed during the current study are
available in the GitHub repository https://github.com/jonalelmi/Data-th-en.

## Acknowledgements

This project has received funding from the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) under Germany’s Excellence Strategy –
EXC-2047/1 – 390685813.

## References

  * [1] Giovanni Alberti and Giovanni Bellettini.  A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies.  European Journal of Applied Mathematics, 9(3):261–284, 1998.
  * [2] Luigi Ambrosio, Guido De Philippis, and Luca Martinazzi.  Gamma-convergence of nonlocal perimeter functionals.  Manuscripta Mathematica, 134(3-4):377–403, 2011.
  * [3] Guy Barles and Christine Georgelin.  A simple proof of convergence for an approximation scheme for computing motions by mean curvature.  SIAM Journal on Numerical Analysis, 32(2):484–500, 1995.
  * [4] Andrea Braides.  $\Gamma$-convergence for beginners, volume 22 of Oxford Lecture Series in Mathematics and its Applications.  Oxford University Press, Oxford, 2002.
  * [5] Jeff Calder.  Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data.  SIAM Journal on Mathematics of Data Science, 1(4):780–812, 2019\.
  * [6] Jeff Calder and Nicolás García Trillos.  Improved spectral convergence rates for graph Laplacians on $\varepsilon$-graphs and $k$-NN graphs.  Applied and Computational Harmonic Analysis., 60:123–175, 2022\.
  * [7] Jeff Cheeger, Mikhail Gromov, and Michael Taylor.  Finite propagation speed, kernel estimates for functions of the Laplace operator, and the geometry of complete Riemannian manifolds.  Journal of Differential Geometry, 17(1):15–53, 1982.
  * [8] Ronald R. Coifman and Stéphane Lafon.  Diffusion maps.  Applied and Computational Harmonic Analysis., 21(1):5–30, 2006\.
  * [9] Gianni Dal Maso.  An introduction to $\Gamma$-convergence, volume 8 of Progress in Nonlinear Differential Equations and their Applications.  Birkhäuser Boston, Inc., Boston, MA, 1993.
  * [10] Ennio De Giorgi and Tullio Franzoni.  Su un tipo di convergenza variazionale.  Atti della Accademia Nazionale dei Lincei. Rendiconti. Classe di Scienze Fisiche, Matematiche e Naturali. Serie VIII, 58(6):842–850, 1975.
  * [11] Matthew M. Dunlop, Dejan Slepčev, Andrew M. Stuart, and Matthew Thorpe.  Large data and zero noise limits of graph-based semi-supervised learning algorithms.  Applied and Computational Harmonic Analysis., 49(2):655–697, 2020\.
  * [12] Selim Esedoḡlu and Felix Otto.  Threshold dynamics for networks with arbitrary surface tensions.  Communications on Pure and Applied Mathematics, 68(5):808–864, 2015\.
  * [13] Lawrence C. Evans.  Convergence of an algorithm for mean curvature motion.  Indiana University Mathematics Journal, 42(2):533–557, 1993.
  * [14] Herbert Federer.  Geometric measure theory.  Die Grundlehren der mathematischen Wissenschaften, Band 153. Springer-Verlag New York Inc., New York, 1969.
  * [15] Irene Fonseca and Stefan Müller.  Relaxation of quasiconvex functionals in ${\rm BV}(\Omega,{\bf R}^{p})$ for integrands $f(x,u,\nabla u)$.  Archive for Rational Mechanics and Analysis, 123(1):1–49, 1993\.
  * [16] Nicolás García Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepčev.  Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator.  Foundations of Computational Mathematics., 20(4):827–887, 2020\.
  * [17] Nicolás García Trillos and Dejan Slepčev.  Continuum limit of total variation on point clouds.  Archive for Rational Mechanics and Analysis, 220(1):193–241, 2016\.
  * [18] Nicolás García Trillos and Dejan Slepčev.  A variational approach to the consistency of spectral clustering.  Applied and Computational Harmonic Analysis., 45(2):239–281, 2018\.
  * [19] Alexander Grigor’yan.  Heat kernel and analysis on manifolds, volume 47 of AMS/IP Studies in Advanced Mathematics.  American Mathematical Society, Providence, RI; International Press, Boston, MA, 2009.
  * [20] Matthias Hein, Jean-Yves Audibert, and Ulrike von Luxburg.  Graph Laplacians and their convergence on random neighborhood graphs.  Journal of Machine Learning Research (JMLR), 8:1325–1368, 2007\.
  * [21] Matt Jacobs.  A fast MBO scheme for multiclass data classification.  Sixth International Conference on Scale Space and Variational Methods in Computer Vision, 2016.
  * [22] Tim Laux and Jona Lelmi.  Large data limit of the MBO scheme for data clustering: Convergence of the dynamics.  In Preparation.
  * [23] Tim Laux and Jona Lelmi.  De Giorgi’s inequality for the thresholding scheme with arbitrary mobilities and surface tensions.  Calculus of Variations and Partial Differential Equations, 61(1):Paper No. 35, 42, 2022.
  * [24] Tim Laux and Felix Otto.  Convergence of the thresholding scheme for multi-phase mean-curvature flow.  Calculus of Variations and Partial Differential Equations, 55(5):Paper No .129 pp. 74, 2016.
  * [25] Tim Laux and Felix Otto.  Brakke’s inequality for the thresholding scheme.  Calculus of Variations and Partial Differential Equations, 59(1):Paper No. 39, pp. 26, 2020.
  * [26] Tim Laux and Felix Otto.  The thresholding scheme for mean curvature flow and De Giorgi’s ideas for minimizing movements.  Advanced Studies in Pure Mathematics 85, The Role of Metrics in the Theory of Partial Differential Equations, pages 63–93, 2020.
  * [27] Tim Laux and Drew Swartz.  Convergence of thresholding schemes incorporating bulk effects.  Interfaces and Free Boundaries., 19(2):273–304, 2017.
  * [28] Pierre Mascarenhas.  Diffusion generated motion by mean curvature.  CAM Reports, Department of Mathematics, University of California, Los Angeles, 1992.
  * [29] Ekaterina Merkurjev, Cristina Garcia-Cardona, Andrea L. Bertozzi, Arjuna Flenner, and Allon G. Percus.  Diffuse interface methods for multiclass segmentation of high-dimensional data.  Applied Mathematics Letters., 33:29–34, 2014.
  * [30] Ekaterina Merkurjev, Tijana Kostić, and Andrea L. Bertozzi.  An MBO scheme on graphs for classification and image processing.  SIAM Journal on Imaging Sciences, 6(4):1903–1930, 2013.
  * [31] Barry Merriman, James K. Bence, and Stanley J. Osher.  Diffusion generated motion by mean curvature.  CAM Reports, Department of Mathematics, University of California, Los Angeles, 1992.
  * [32] Barry Merriman, James K. Bence, and Stanley J. Osher.  Motion of multiple functions: a level set approach.  Journal of Computational Physics, 112(2):334–363, 1994.
  * [33] Michele Miranda, Jr., Diego Pallara, Fabio Paronetto, and Marc Preunkert.  Heat semigroup and functions of bounded variation on Riemannian manifolds.  Journal für die Reine und Angewandte Mathematik., 613:99–119, 2007.
  * [34] Michele Miranda, Jr., Diego Pallara, Fabio Paronetto, and Marc Preunkert.  Short-time heat flow and functions of bounded variation in $\mathbb{R}^{N}$.  Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série 6, 16(1):125–145, 2007.
  * [35] Steven Rosenberg.  The Laplacian on a Riemannian manifold, volume 31 of London Mathematical Society Student Texts.  Cambridge University Press, Cambridge, 1997.  An Introduction to Analysis on Manifolds.
  * [36] Alberto G. Setti.  Gaussian estimates for the heat kernel of the weighted Laplacian and fractal measures.  Canadian Journal of Mathematics., 44(5):1061–1078, 1992.
  * [37] Dejan Slepčev and Matthew Thorpe.  Analysis of $p$-Laplacian regularization in semisupervised learning.  SIAM Journal on Mathematical Analysis, 51(3):2085–2120, 2019.
  * [38] Yves van Gennip, Nestor Guillen, Braxton Osting, and Andrea L. Bertozzi.  Mean curvature, threshold dynamics, and phase field theory on finite graphs.  Milan Journal of Mathematics, 82(1):3–65, 2014.