  With the continuous increase of users and items, conventional recommender
systems trained on static datasets can hardly adapt to changing environments.
The high-throughput data requires the model to be updated in a timely manner
for capturing the user interest dynamics, which leads to the emergence of
streaming recommender systems. Due to the prevalence of deep learning-based
recommender systems, the embedding layer is widely adopted to represent the
characteristics of users, items, and other features in low-dimensional vectors.
However, it has been proved that setting an identical and static embedding size
is sub-optimal in terms of recommendation performance and memory cost,
especially for streaming recommendations. To tackle this problem, we first
rethink the streaming model update process and model the dynamic embedding size
search as a bandit problem. Then, we analyze and quantify the factors that
influence the optimal embedding sizes from the statistics perspective. Based on
this, we propose the \textbf{D}ynamic \textbf{E}mbedding \textbf{S}ize
\textbf{S}earch (\textbf{DESS}) method to minimize the embedding size selection
regret on both user and item sides in a non-stationary manner. Theoretically,
we obtain a sublinear regret upper bound superior to previous methods.
Empirical results across two recommendation tasks on four public datasets also
demonstrate that our approach can achieve better streaming recommendation
performance with lower memory cost and higher time efficiency.
