term $\mathcal{E}$ with $||\mathcal{E}||\leq \epsilon$. Our observation, denoted $\mathbf{\bar{\Omega}}$, is the set of 3-tuples:

$$\mathbf{\bar{\Omega}} := \{ (i,j,M_{ij}) : (i,j) \in \Omega\}$$

We treat $\Omega$ as a set-valued random variable. In particular, $\Omega$ samples $\tau$ entries from $[n] \times [m]$ without replacement according to some distribution $Q$. Like [@negahban2012restricted], we assume that probability matrix $Q$ is rank-1: $Q_{ij} = \pi_i\rho_j$ for some $n$-dimensional and $m$-dimensional probability vectors $\boldsymbol{\pi}$ and $\boldsymbol{\rho}$, respectively. In principle, if $\boldsymbol{\pi}$ and $\boldsymbol{\rho}$ are known, they may be used directly. In our applications, we estimate them from training data using empirical frequencies of access **f** for users and **g** for items, respectively.

We refer to a collaborative filter $\mathcal{A}$ as an algorithm that inputs the observation $\mathbf{\bar{\Omega}}$ and outputs an estimate of $M^*$, denoted $\Hat{M} \gets \mathcal{A}(\mathbf{\bar{\Omega}})$. The goal of the filter is to minimize the $Q$-weighted Frobenius loss:

$$||\Hat{M} - M^*||^2_Q = \sum_{i,j \in \Omega} \pi_i\rho_j (\hat{M}_{ij} - M_{ij}^*)^2$$

### Matrix Factorization

In MF we define $\mathcal{A}$ as solving the following optimization problem

$$\min_{W, V} \sum_{i,j \in \Omega} ( \textbf{w}_i^{T} \textbf{v}_j - M_{ij})^2$$

where user $W^{T} = [\textbf{w}_{0}, ..., \textbf{w}_{n-1}]$ and item $V^{T} = [\textbf{v}_{0}, ..., \textbf{v}_{m-1}]$ embedding matrices correspond to an $r$-dimensional embedding layer. 