1 Introduction↩︎

In this work, we consider the setting of completing multiple matrices in a sequential and active way, under a budget constraint on the number of observations the learner may request. The learner’s objective is to estimate each of these matrices well (in some precise sense that we define later) and is akin to the pure exploration problems considered in the multi-armed bandits [1], [2]. As the learner is trying to solve multiple learning problems simultaneously, a decent strategy should naturally allocate a larger portion of the observational budget to harder problems. Such challenge is for example considered in a very different model by [3]. Of course, since knowing the hardness or complexity of each instance is typically out of reach in practice, a good strategy should be adaptive to the different complexity scenarios, without requiring any tuning. This is in contrast with previous results for regret minimization with a low-rank structure [4], [5], where the learner explicitly takes advantage of the rank-\(1\) structure of the setting.

We consider matrix completion in the trace-regression model [6]–[9]. There are important reasons regarding this choice as opposed to the Bernoulli model [10], [11], another common model for the matrix completion. In particular, in the trace-regression model it is possible that some of the matrix entries are sampled multiple times. In the Bernoulli model, this cannot happen, as each entry is observed either never or once with probability \(p\) in the simplest model. The implication of this multi-sampling is fundamental as it allows, in the trace-regression model, to construct honest confidence sets that adapt to the rank of the matrix, even if the level of noise is unknown. On the other hand, it has been shown that in the Bernoulli model such confidence sets provably do not exist [12]. This is very important, as we will see that our adaptive strategy crucially depends on the existence of these adaptive confidence sets: Consider for example the problem of minimizing the maximum of the losses across multiple matrix completion problems. A good strategy should roughly equalize the diameter of the confidence sets across instances when the budget expires, as it pays the price for the largest diameter by definition of the maximum loss. In order to do that, it is important to leverage adaptive confidence sets.

The main application domain we target is market segmentation [13] and polling. However, being able to multi-sample decides the situations where exactly this model applies. For example, for music recommendations in music streaming services, it is possible that the users listen to the same song twice or more and we can get multiple samples of their appreciations, either by rating or by not-skipping. For movie or product ratings, multi-sampling is much less applicable. Yet it is possible to ask the customer for a second opinion later in time. In other situations, the multi-sampling happens by design. For example,in tasting experiments, the human subjects are sometimes given same two samples, that they have to taste and evaluate with a week-long break in between. Our algorithm and results apply to these situations, whether the multiple-sample for the same entry are possible because of the nature of the setting or by design.

In this work, we introduce the active multiple matrix completion problem and propose an anytime algorithm (MALocate) that solves this problem adaptively to the unknown ranks of each sub-problem. For the \(\max\) loss, which corresponds to the case where the learner pays the price of the largest loss on the set of matrix completion problems it has to solve, we show that our strategy is optimal by deriving a matching lower bound. Finally, we show that MALocate indeed performs well with a synthetic experiment.

2 Multiple matrix completion setting↩︎

We start by defining the single matrix completion problem and state the known results that we build on. Then, we introduce our active setting, which can be thought of as solving \(K\) matrix completion problems simultaneously (as the objective is to optimize the loss when the budget \(n\) expires) and sequentially as we may decide where to allocate our budget at round \(t \leq n\).

2.1 Single matrix completion setting↩︎

We first introduce the matrix completion setting and a matrix lasso estimator. Let \({\boldsymbol{M}}_0 \in \mathbb{R}^{d_1 \times d_2}\) be an unknown matrix. The task of matrix completion is that of estimating \({\boldsymbol{M}}_0\) accurately in some precise sense, that we define later, by an estimator \(\widehat{{\boldsymbol{M}}}\) given \(n\) independent random pairs \(({\boldsymbol{X}}_i,Y_i)_{i\leq n}\) such that \[Y_i \triangleq \mathop{\mathrm{Tr}}({\boldsymbol{X}}_i^\mathsf{\scriptscriptstyle T}{\boldsymbol{M}}_0) + \sigma\varepsilon_i,\] where the \(\varepsilon_i\) are centered independent random variables with unit variance.¹ We consider the matrix completion setting where \({\boldsymbol{X}}_i^\mathsf{\scriptscriptstyle T}\) are i.i.d. uniformly distributed on the set \[\mathcal{X} \triangleq \left\{e_i\left(d_1\right)e_j^\mathsf{\scriptscriptstyle T}\left(d_2\right), i\in [d_1], j \in[d_2] \right\}\mathbin{\raisebox{0.5ex}{,}}\] where \(e_i(d)\) are the canonical basis vectors in \(\mathbb{R}^d\). Typically, in this setting, we do not observe the entire matrix of size \(d_1\times d_2\) as we have \(n \ll d_1 d_2\), and we consider matrices of low rank \(r\), with respect to \(\min(d_1,d_2)\), for which completion is still possible despite the low number of observations. Let \(d \triangleq \max(d_1, d_2)\) and \(\left\lVert{\boldsymbol{M}}\right\rVert_F\) is the Frobenius norm of a matrix \({\boldsymbol{M}}= ({\boldsymbol{M}}_{ij}) \in \mathbb{R}^{d_1 \times d_2}\) defined as \[{\left\lVert{\boldsymbol{M}}\right\rVert_F^2 \triangleq \sum_{i=1}^{d_1}\sum_{j=1}^{d_2} {\boldsymbol{M}}_{ij}^2 = \mathop{\mathrm{Tr}}({\boldsymbol{M}}^\mathsf{\scriptscriptstyle T}{\boldsymbol{M}})}.\] For this problem, it is possible to construct good estimators \(\widehat{{\boldsymbol{M}}}_n\) such that \[\frac{\|\widehat{{\boldsymbol{M}}}_n - {\boldsymbol{M}}_0\|_F^2}{d_1 d_2} \leq \rho(r,n,d),\] where \(\rho(r,n,d) \ll \left\lVert{\boldsymbol{M}}_0\right\rVert_\infty\) for \(r \ll \min(d_1, d_2)\) and \(n \geq r d\). Intuitively, the higher the rank \(r\) of \({\boldsymbol{M}}\), the harder the problem should be, as there are more parameters to estimate. A good estimator should be adaptive to the rank of the matrix without requiring it as an input to allow the tuning of hyperparameters.

2.2 Square-root lasso estimator↩︎

In this work, we consider the matrix square-root lasso estimator, which has been shown to have favorable properties ([6], [8], [14], [15]). We define the nuclear norm of a matrix\[\left\lVert{\boldsymbol{M}}\right\rVert_\star \triangleq \mathop{\mathrm{Tr}}\left(\sqrt{{\boldsymbol{M}}^\mathsf{\scriptscriptstyle T}{\boldsymbol{M}}}\right) = \sum_{i=1}^{r} \sigma_i,\] where \(\sigma_i\) are the singular values of \({\boldsymbol{M}}\). The matrix square-root lasso estimator is defined as \[\label{eq:min} \!\!\!\!\!\widehat{{\boldsymbol{M}}}_n(\lambda) \!\in \!\!\!\mathop{\mathrm{arg\,min}}_{{\boldsymbol{M}}\in \mathbb{R}^{d_1 \times d_2}}\!\! \left\{\!\!\sqrt{\sum_{i=1}^n\! \frac{(Y_i \!- \!\langle {\boldsymbol{X}}_i, {\boldsymbol{M}} \rangle)^2}{n}}\! +\! \lambda \|{\boldsymbol{M}}\|_\star \!\!\right\}\cdot\tag{1}\] Importantly, for this estimator [6] showed that \[\rho(r,n,d) = \mathcal{O}\left(\frac{rd\log d}{n}\right)\] for \(\lambda\) defined in the following proposition, that does not depend on \(r\), the unknown rank of matrix \({\boldsymbol{M}}\). It also does not require the variance \(\sigma^2\) of the noise as an input to tune \(\lambda\), only an upper bound such that \(A \geq \sigma\).

We also restate a lower bound for the single matrix completion problem shown by [8], which shows that the previous procedure is minimax optimal up to an extra \(\log d_k\) factor.

This result easily extends to the bounded noise case.

2.3 Adaptive confidence sets↩︎

An important theoretical result in the trace-regression model with uniform sampling of the entries is the existence of adaptive and honest confidence bands on the error \(||\widehat{{\boldsymbol{M}}} - {\boldsymbol{M}}||_F^2\). Importantly, the knowledge of \(\sigma\) is again not necessary for this estimator. This procedure, EstimateError, is described in Section 3, and makes use of the entries \(X_i\) that have been observed twice to compute an unbiased estimator of the error. This procedure comes with the following guarantee.

For minimax-optimal estimation procedures, such as the square-root lasso, we can show (by bounding both the estimation error as above and \(N \geq Cn^2/d^2\) for some numerical constant \(C\), on a favorable event) that with high probability, \[\widehat{R_N} + 8A^2\sqrt{\frac{\log d}{N}} \leq \mathcal{O}\left(\frac{rd\log d}{n}\right)\mathbin{\raisebox{0.5ex}{,}}\] which shows that this quantity is an adaptive (as it does not require the rank as an input) and honest (as it upper bounds the true error with high probability) confidence band on \(\|\widehat{{\boldsymbol{M}}} - {\boldsymbol{M}}\|_F^2.\)

2.4 Active multiple matrix completion↩︎

In the active multiple matrix completion, the learner’s goal is to complete multiple matrices \(\{{\boldsymbol{M}}^k\}_k\) simultaneously, by actively choosing from which matrix it should ask for a new observation in a sequential and adaptive manner. For ease of notation, we restrict this setting to square matrices of dimension \(d_k\), but our techniques directly extend to non-square matrices. At each round the active learner has to choose an action \(k_t \in [K]\) and receives a pair \(({\boldsymbol{X}}_t^{k_t},Y_t^{k_t})\) such that \({\boldsymbol{X}}_{t}^{k_t}\) corresponds to the location of the entry \((i_{k_t,t}, j_{k_t,t})\) of the \(k_t\)-th data matrix \({\boldsymbol{M}}^{k_t} = ({\boldsymbol{M}}^{k_t}_{ij}) \in \mathbb{R}^{d_{k_t} \times d_{k_t}}\) chosen uniformly at random such that \(i_{k_t,t} \in [d_{k_t}]\) and \(j_{k_t,t} \in [d_{k_t}]\), and \[\begin{align} Y_t^{k_t} & \triangleq \mathop{\mathrm{Tr}}(e_{i_{k_t,t}}(d_{k_t})e^\mathsf{\scriptscriptstyle T}_{j_{k_t,t}}(d_{k_t}) {\boldsymbol{M}}^{k_t}) + \varepsilon_{k_t,t} \\&= {\boldsymbol{M}}_{i_{k_t,t} j_{k_t,t}} + \varepsilon_{k_t,t}, \end{align}\] where the \(e_i(d)\) are the canonical basis vectors of \(\mathbb{R}^d\). Here, \({\boldsymbol{X}}_t^{k_t} = e_{i_{k_t,t}}(d_{k_t})e^\mathsf{\scriptscriptstyle T}_{j_{k_t,t}}(d_{k_t})\). Informally, the learner chooses to observe one of the \(K\) matrices, and receives a noisy observation of one of the entries (corrupted by \(\varepsilon_{k_t,t}\)) chosen uniformly at random from that matrix. The goal of the learner is to adaptively choose which matrix \({\boldsymbol{M}}^{k_{t}}\) to sample based on the observations collected so far up to round \(t-1\), \[\left\{({\boldsymbol{X}}_{1}^{k_1}, Y_{1}^{k_1}),\dots, ({\boldsymbol{X}}^{k_{t-1}}_{t-1}, Y^{k_{t-1}}_{t-1})\right\}\cdot\] At the end of the game, once it has collected at most \(n\) pairs \(({\boldsymbol{X}}_t^{k_t},Y_t^{k_t})\), the learner has to output estimates \(\widehat{{\boldsymbol{M}}}^k_n\) of each matrix \({\boldsymbol{M}}^k\) to suffer the following loss, \[\begin{align} \mathcal{L}_n^p \triangleq\left(\sum_{k\in [K]} \|\widehat{{\boldsymbol{M}}}^k_n - {\boldsymbol{M}}^k\|_F^{2p}\right)^{\!\!\!1/p}\!\!\!\!\!, \end{align}\] where \(p\) characterizes the objective and is decided as part by the learner at the start of the game. As special and interesting cases, for \(p=1\), we recover the unnormalized squared Frobenius norm if the sub-problems were the blocks of a block-diagonal matrix, and for \(p= \infty\) the max loss \(\max_{k\in [K]} \|\widehat{{\boldsymbol{M}}}^k_n - {\boldsymbol{M}}^k\|_F^2\).

For each matrix \({\boldsymbol{M}}_k\), \(k \in [K]\), we denote by \(r_k\), the rank of \({\boldsymbol{M}}^k\). We further assume that all the observations \(Y_{t}^{k_t}\) and the entries of \({\boldsymbol{M}}^k\) are bounded by some known constant \(A\). The first condition is \(|Y_{t}^k| \leq A\) for any \(k,t\) and the second condition is simply \(\|{\boldsymbol{M}}^k\|_\infty \leq A\). This is a mild assumption in applications such as recommendation systems, where ratings are bounded.

3 MALocate algorithm↩︎

We now describe our active strategy MALocate for the active multiple matrix completion given as Algorithm 1. The input for MALocate is the maximum budget input \(n\) and the loss parameter \(p\). This parameter defines which loss \(\mathcal{L}^p_n\) the strategy should optimize for. We shall see that \(p\) governs the exploration. During the initialization, while \(B_k(t) = \infty\), the strategy requests for each \({\boldsymbol{M}}^k\) a dataset \(\mathcal{D}^k_t\) of size \(\mathcal{O}(d_k \log d_k)\). MALocate uses the requested samples for two goals: computing the estimators and adaptively estimating their error. In particular, the first half of the requested sample is used to compute an estimator \(\widehat{{\boldsymbol{M}}}^k_t\) of \({\boldsymbol{M}}^k\) using the square-root lasso estimator. The second half of the sample is used by the EstimateError\((\widehat{{\boldsymbol{M}}}^k_t, \mathcal{D}^k_t)\) sub-procedure to construct an estimator of the error \(\widehat{R}_{N_k^t}\) and an upper-bound on this error \(B_k(t)\), using the double-sampled entries. After the initialization, at round \(t\), the strategy allocates the next samples to the matrix \[m \triangleq \arg\max_k d_k^2 B_k(t) T_k(t)^{-1/p},\] where \(T_k(t)\) is the number of samples allocated to matrix \(k\) up to round \(t\). The previous estimator \(\widehat{{\boldsymbol{M}}}^m\) for matrix \(m\) is then replaced by \(\widehat{{\boldsymbol{M}}}^m_t\) only if the upper bound on the error has decreased. The strategy operates on a doubling schedule: Each round an index \(m\) is chosen, a new dataset \(\mathcal{D}^m_t\) of size \(T_m(t)\) (and thus, a total budget of \(2T_m(t)\) is spent on \(m\)) is used to construct a new estimator \(\widehat{{\boldsymbol{M}}}^m_t\), and estimate its error.

In this case, \(B_m(t)\) is also updated to the new (smaller) upper bound on the error. This ensures that the estimation error is non-increasing with \(t\) for every matrix. This is a crucial ingredient for the proof of Theorem [thm:algoub], which characterizes the performance of MALocate. The loop is repeated until the budget has been used, at which point the algorithm stops and outputs estimator \(\widehat{{\boldsymbol{M}}}^k\) for each matrix \(k\).

3.0.0.1 Computing the estimator

As explained previously, we use the square-root lasso estimator. Notice that we perform a splitting of the sample \(\mathcal{D}^k_t\), where the first half is used to compute the estimator, and the second half is used to estimate its error. In practice, we propose instead to split the sample between entries that have been sampled only once to compute the estimator, and the other entries to estimate the error. While this introduces a small dependence (as we may only estimate the error for entries on which the estimator was not trained) which is difficult to analyze, in practice, this greatly improves the power of the estimator.

3.0.0.2 Estimating the error

The sub-procedure \(\normalfont \textcolor[rgb]{0.5,0.2,0}{\texttt{EstimateError}}\) uses the second half of a dataset \(\mathcal{D}^k_t\) to build an estimator of the error for some estimator \(\widehat{{\boldsymbol{M}}}^k\) of the matrix \({\boldsymbol{M}}^k\). It proceeds as the estimator of [12] by finding entries \((X_i, Y_i)\) and \((X_j, Y_j)\) such that \(X_i = X_j\) to form the triplet \((X_i, Y_i, Y_j)\), and the dataset \(\mathcal{D}'\) of double-sampled entries with \(N^k_t \triangleq |\mathcal{D}'|\). \(\mathcal{D}'\) is then used to compute the unbiased estimator of the error, \[\widehat{R_N} \triangleq \frac{1}{N}\sum_{i = 1}^{N} \left(Y_i - \langle X_i, \widehat{{\boldsymbol{M}}} \rangle\right)\left(Y'_i - \langle X_i, \widehat{{\boldsymbol{M}}} \rangle\right),\] which does not require the variance of the noise as an input to the estimation procedure. We can then deduce an upper bound on \(\widehat{R_N}\) that holds with high probability \(B_k(t) \triangleq \widehat{R_{N^k_t}} + 8A^2\sqrt{\log(d_k)/N^k_t}\). Importantly, this upper bound on the error is honest and adaptive to the unknown rank \(r_k\) as proved by [12] and is upper bounded as \(\mathcal{O}\left(r_k d_k^3 \log(d_k)/T_k(t)\right)\), as \(\widehat{R_{N_t^k}}\) dominates the stochastic error term.

3.0.0.3 The sampling criterion

The exploration crucially depends on the interplay between the loss parameter \(p\), \(T_k(t)\), and the upper bound on the error \(B_k(t)\) rescaled by \(d_k^2\). For \(p=1\) (sum loss), the chosen index is \[\arg\max_k d_k^2 B_k(t) T_k(t)^{-1},\] and can be interpreted as the index that maximizes the error per sample, which is a rough approximation of \(\partial B_k(t)/\partial T_k(t)\). The idea behind this heuristic is that since we expect the sum loss to decrease the most for this matrix, the next sample is allocated to this index. On the other hand, for \(p = \infty\), the index chosen is simply the one that currently suffers the largest upper bound on the rescaled error.

More generally, by plugging the upper bound given by Proposition 1 into the loss \(\mathcal{L}^p_n\), we see that a good allocation is one that minimizes \[\sum_k \left(\frac{r_k d_k^3\log d_k }{T_k(n)}\right)^{\!p}\] under the constraint \(\sum_k T_k(n)=n\). By solving the corresponding optimization problem, we see that this good allocation should be such that \[T_k(n)^{1+1/p} = (r_k d_k^3\log d_k )C(n),\] where \(C(n)\) is constant for all \(k\). Note however, that this good allocation is de facto out of reach for the learner, which does not have access to the underlying ranks \(\{r_k\}_{k\in[K]}\) of the matrices. Now, as \(d_k^2 B_k(t)\) can be upper bounded as \(\mathcal{O}\left(r_k d_k^3 \log d_k /T_k(t)\right)\), it is clear that our strategy, which picks the index that maximizes \(d_k^2B_k(t)T_k(t)^{-1/p}\) mimics the good allocation that keeps the quantity \[r_k d_k^3 \log(d_k) T_k(n)^{-(1+1/p)}\] constant across the arms.

4 Analysis↩︎

In this section, we give guarantees on the performance of MALocate for general \(p\), and prove a lower bound in the case \(p = \infty\), showing that our strategy is optimal for the max loss, up to logarithmic factors.

4.1 Upper bound on the loss of MALocate↩︎

We start with upper bounding the loss of MALocate that holds with high probability.

We prove this result in Appendix 7. It relies on a careful bounding of the estimation error of \(\widehat{{\boldsymbol{M}}}_n\) directly, as it is not possible² to prove bounds on \(T_k(n)\), the number of times that each arm has been sampled at the end of the horizon, as opposed to many regret analyses used for bandit settings. In particular, the proof proceeds by showing that the following bounds on the error hold with high probability. First, using the sampling criterion we prove that for all \(k\) a bound of the form \[\begin{align} &\left\lVert\widehat{{\boldsymbol{M}}}^k-{\boldsymbol{M}}^k\right\rVert_F^{2} \\ &\quad\;\leq \mathcal{O}\left(T_k(n)^\frac{1}{p} \left(\sum_k{ (r_k d_k^3\log d_k)^\frac{p}{p+1}}\right)^{\!\!\!\frac{p+1}{p}} \!\!\! n^{-\frac{p+1}{p}}\right). \end{align}\] Importantly, this grows with \(T_k(n).\) On the other hand, Proposition 1 yields that \[{\left\lVert\widehat{{\boldsymbol{M}}}^k-{\boldsymbol{M}}^k\right\rVert_F^2 \leq \mathcal{O}\left(\frac{r_kd_k^3\log d_k}{T_k(n)}\right)} \mathbin{\raisebox{0.5ex}{,}}\] which decreases with \(T_k(n)\). By balancing both bounds with respect to \(T_k(n)\), we get an upper bound on the estimation error that does not depend on \(T_k(n)\).

This result shows that the complexity of the problem crucially depends on the interaction between both the intrinsic difficulty of each sub-problem associated with \({\boldsymbol{M}}_k\), characterized by \(r_k\) and \(d_k\), and the loss parameter \(p\). Namely, if we set \[c_k \triangleq r_k d_k^3 \log(d_k)\] for the complexity of problem \(k\), and \({\boldsymbol{c}}= (c_1, \dots, c_K)\), then the complexity of the active problem is \(\left\lVert{\boldsymbol{c}}\right\rVert_{\frac{p}{p+1}}\) i.e., the loss is upper bounded as \[\mathcal{O}\left(\left\lVert{\boldsymbol{c}}\right\rVert_{\frac{p}{p+1}}n^{-1}\right).\] On the other hand, it is easy to see that the uniform strategy suffers a loss of order \(\frac{K}{n}\left\lVert{\boldsymbol{c}}\right\rVert_p\), which is always larger³ than \(\frac{1}{n}\left\lVert{\boldsymbol{c}}\right\rVert_{\frac{p}{p+1}}\). This shows that our active strategy, MALocate, adapts on-the-fly to the difficulty of the problem at hand, without requiring any input parameter that depends on this complexity.

We now rewrite the previous theorem for the important case \(p = \infty\).

This result is a direct corollary of our main upper bound. It shows that interestingly, even in the case \(p = \infty\), the complexity of each individual problem comes into play. Namely, in this setting, the total complexity is simply the sum of the complexities for each sub-problem.

4.2 Lower bound↩︎

We now show a lower bound for the active multiple matrix completion problem in the case \(p = \infty\). The offline part of our lower bound proof is inspired by [8]. The challenge of our proof is the active setting as we have to consider strategies that may actively spread their observations over the different matrices.

We prove this theorem in Appendix 8. The main argument is that for any active strategy \(\mathcal{S}\), for any fixed problem \(P\), there exists one index \(m \in [K]\) such that \[\mathbb{E}_{P,\mathcal{S}}\left[T_k(n)\right] \leq \frac{r_md_m^3}{\sum_k r_k d_k^3}n.\] Then, we carefully adapt the arguments of the lower bound for \(K=1\) to our active setting.

This shows that our active strategy is minimax-optimal (up to logarithmic factors) over the class of problems with dimension \(\{d_k\}_{k \in [K]}\) and ranks at most \(\{r_k \}_{k \in [K]}\), fully adaptive to the unknown ranks of the sub-problems. Importantly, the lower bound also holds for strategies that have a priori knowledge of \(\{r_k \}_{k \in [K]}\).

5 Synthetic experiments↩︎

We now support our analysis MALocate with synthetic experiments. To create a square matrix of rank \(r\) and dimension \(d\), we generate two matrices \({\boldsymbol{U}}\in \mathbb{R}^{d \times r}\) and \({\boldsymbol{V}}\in \mathbb{R}^{r \times d}\) with entries distributed as \(\mathcal{N}(0, \sigma_r^2 \triangleq r^{-1/2})\). The standard deviation \(\sigma_r\) is chosen such that the entries of \({\boldsymbol{M}}= {\boldsymbol{U}}{\boldsymbol{V}}\) have the same scaling, regardless of the rank of the matrix. Observations are corrupted with Gaussian white noise \(\mathcal{N}(0, \sigma \triangleq 0.1)\). We consider both objectives \(\mathcal{L}_p\) for \(p=1\) and \(p=\infty\), on which we run MALocate also with both parameters \(p=1\) and \(p=\infty\). We also compare MALocate to the naïve uniform strategy, and for the max loss also with the oracle strategy that has access to the true Frobenius error of the estimators and allocates the next samples to the index \(\arg\max_k \|\widehat{{\boldsymbol{M}}}^k_t - {\boldsymbol{M}}\|_F^2\). Note that this strategy (for a fixed estimation procedure) is optimal for \(p = \infty\), as the max loss may only decrease if the worst estimator is improved.

As our goal is to study the active advantage of MALocate, all the strategies have access to the same estimator \(\texttt{SoftImpute}\), tuned with the same parameters. Moreover, we discretize time in a similar fashion for all the strategies: The initialization phase of each estimator is done with \(8d_k\) samples and after that, the budget is divided evenly in approximately \(100\) sub-samples. This allows to bypass the negative effects associated with a doubling schedule. As our strategy is naturally anytime, we plot the results as the time horizon grows from the initialization up to \(n = Kd^2/2\). At each round \(t\) where a new estimator has been trained, we use the knowledge of \({\boldsymbol{M}}^k\) to compute \(\mathcal{L}^p_t\) for \(p \in \{1, \infty\}\). For both experiments, we draw and fix the problem, and average the results over \(15\) runs.

5.0.0.1 First experiment

We fix \(d_k \triangleq d \triangleq 200\), \(K \triangleq 10\), and the ranks are such that \(r_k \triangleq 10\) for all \(k\) besides \(r_1 = 40\). We choose this instance as it forces the strategy into a tradeoff with respect to the loss parameter \(p\). Heuristically, to optimize the sum loss (\(p=1\)), reaching a good error on each of the easy problems is very important. On the other hand, to optimize the max loss, it is necessary to spend a large portion of the budget on the hardest instance. In Figure 5, we see that our strategies perform favorably in the setting they are designed for. We also see that the uniform strategy only catches up when the number of samples is high enough such that the careful sample allocation has little effect on the performance.

5.0.0.2 Second experiment

We fix \(d_k \triangleq d \triangleq 200\) and \(K \triangleq 15\). The ranks \(r_k\) are given by \(r_k \triangleq 18 + 0.0015 k^4\). Note that the hardest instance is such that \(r_{15} = 76\) and half of the sub-problems have rank at most \(22\). This set of problems is more varied than the previous one and shows the adaptivity of our strategy (Figure 6).

5.0.0.3 Implementation of MALocate

As we discuss in Remark 4, our generic strategy can be used for any estimator, which may be chosen appropriately with respect to the exact noise setting. For performance reasons, we used the SoftImpute estimator [17] from the python package fancyimpute, which we tweak to have a warm-start heuristic that fills missing entries with the previous estimator \(\widehat{{\boldsymbol{M}}}^k\). This allows us to speed-up the running time. More generally, online matrix completion results such as the ones by [18]–[20] fit in our active and sequential framework. We tune the confidence intervals on the error in a conservative way. As we use a time discretization instead of a geometric grid, we also re-use samples throughout the run. Finally, as explained in Section 3, instead of splitting the entire sample, we use entries that have been observed once to train the estimator, and the other entries (sampled at least twice) to estimate the error.

Across the experiments, we see that MALocate run with the proper loss parameter \(p\) indeed performs better on the associated loss \(\mathcal{L}^p\). For the max loss, we also see that MALocate with \(p=\infty\) performs only slightly worse than the optimal oracle strategy in this setting. On the other hand, the uniform strategy performs poorly across the problems. We see that for the max loss, the loss peters out when the hardest matrix to estimate has been sampled \(d_k^2\) times, as we cap the number of observations for each matrix to \(d_k^2\). We remark however that we are interested in settings with smaller \(n \ll Kd_k^2\), where we see that MALocate with \(p=\infty\) performs very favorably.

6 Conclusion and discussion↩︎

We presented a new active matrix completion setting and provided MALocate, an active strategy that is able to adapt to the different complexities of the problems and proved that up to log factors, it achieves minimax-optimal guarantees. We also showed that empirically, it performs in accordance with its theoretical guarantees for two loss settings. We see our work as the first step towards a more systematic understanding of the links between adaptive confidence sets (in any statistical setup) and the corresponding active learning setting.

We considered the high-dimensional regime where the number of samples \(n\) satisfies \(d \leq n \ll d^2\). The number of doubly-sampled entries scales (w.h.p.) by Proposition 6 as \(n^2/d^2\) for any \(n\) in this interval. This remains true for \(n \gg d^2\) and generally our results would also hold in this regime. However, we do not address this case here at all, as from an algorithmic point of view, much simpler estimation strategies solve this problem, for example, least squares with a projection on the set of rank \(r\) matrices coupled with Lepski’s method to adapt to the rank.

Finally it is, unfortunately, not possible to extend our approach to datasets where entries are not observed twice, because it is provably impossible to obtain a good estimator of the error.

6.0.0.1 Acknowledgements

The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, Inria and Otto-von-Guericke-Universität Magdeburg associated-team north-European project Allocate, and French National Research Agency projects ExTra-Learn (n.ANR-14-CE24-0010-01) and BoB (n.ANR-16-CE23-0003). The work of A. Carpentier is also partially supported by the Deutsche Forschungsgemeinschaft (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1), by the DFG - 314838170, GRK 2297 MathCoRe, by the DFG GRK 2433 DAEDALUS, by the DFG CRC 1294 Data Assimilation, Project A03, and by the UFA-DFH through the French-German Doktorandenkolleg CDFA 01-18. This research has also benefited from the support of the FMJH Program PGMO and from the support to this program from Criteo.

7 Upper bound for MALocate↩︎

As explained in Section 2, in order to simplify the analysis, we only consider square matrices of dimension \(d_k\) or \(d\) below when we restate results for \(K = 1\).

We now define favorable events for which the estimators are within their confidence bounds for all datasets \(\mathcal{D}_t^k\), estimators \(\widehat{{\boldsymbol{M}}}_t^k\), and errors \(\widehat{R_{N_t^k}}\) for well chosen rounds \(t\), where \(N_t^k\) is the number of entries sampled twice in the second half of the sample \(\mathcal{D}_t^k\). For \(d_k \log d_k \leq t \leq d_k^2\), we write \(\xi_1(t,k)\) for the event when these three bounds hold simultaneously, \[\begin{align} &(1)\quad \frac{\|\widehat{{\boldsymbol{M}}}_t^k - {\boldsymbol{M}}^k\|_F^2}{d_k^2} \leq CA^2 \cdot \frac{r_k d_k\log d_k}{t}\mathbin{\raisebox{0.5ex}{,}}\\ &(2)\quad N_t^k \geq \frac{t^2}{64d_k^2} \mathbin{\raisebox{0.5ex}{,}}\\ &(3)\quad\left|\widehat{R_N} - \frac{\|\widehat{{\boldsymbol{M}}}_t^k-{\boldsymbol{M}}^k\|_F^2}{d_k^2}\right| \leq 8A^2\sqrt{\frac{\log d_k}{N_t^k}} \cdot \end{align}\] Then we consider the following event \(\xi_2(k)\), \[\xi_2(k) = \bigcap_{s \in [2\log_2(d_k)]} \xi_1(2^s T_k^{I}, k), \quad \text{where} \quad T_k^I \triangleq 2\left\lceil\frac{d_k \log(d_k)+1}{2}\right\rceil\cdot\]

8 Lower bound for max loss (\(p = \infty\))↩︎

References↩︎