of embedding vectors based on embedding popularity. In principle, nothing precludes the compound use of our proposed technique and most other compression algorithms or compressed architectures. This is an interesting direction for future investigation.

Finally, we note that non-uniform and deterministic sampling has been addressed in the matrix completion literature in a line of work [@negahban2012restricted], but only in so far as how to correct for popularity so as to improve statistical recovery performance, or build theoretical guarantees for completion under non-uniform sampling [@papadopoulos2012popularity]. As far as we know, we are the first to leverage popularity to actually reduce parameter counts in large-scale embedding layers.

Problem and Model Formulation
=============================

We pose the problem formulations for CF and CTR tasks. For each task, we also describe the relevant models.

Collaborative Filtering Problem
-------------------------------

Inspired by the apparent inefficiencies of using uniform dimension vectors in the non-uniform sampling regime, we formally state the central formulation of study in the noisy setting, similar to that of [@negahban2012restricted].

Let $M^* \in \mathbb{R}^{n \times m}$, for $n \geq m$, be an unknown target matrix. Let $\Omega \subset [n] \times [m]$ denote a sample of indices. Define $M := M^* + \mathcal{E}$ for some noise 