Budget-Constrained Item Cold-Start Handling via Optimal Design in Collaborative Filtering Recommenders
% You can go ahead and credit any number of authors here
% e.g. one 'row of three' or two rows (consisting of one row of three % and a second row of one
two or three). % % The command \alignauthor (no curly braces needed) should % precede each author name
affiliation/snail-mail address and % e-mail address. Additionally
tag each line of % affiliation/address with \affaddr
and tag the % e-mail address with \email. % % 1st. author \alignauthor Oren Anava
\affaddr{Technion
Haifa
Israel
It is well known that collaborative filtering (CF) based recommender systems provide better modeling of users and items associated with considerable rating history. The lack of historical ratings results in the user and the item cold-start problems. The latter is the main focus of this work. Most of the current literature addresses this problem by integrating content-based recommendation techniques to model the new item. However, in many cases such content is not available, and the question arises is whether this problem can be mitigated using CF techniques only. We formalize this problem as an optimization problem: given a new item, a pool of available users, and a budget constraint, select which users to assign with the task of rating the new item in order to minimize the prediction error of our model. We show that the objective function is monotone-supermodular, and propose efficient optimal design based algorithms that attain an approximation to its optimum. Our findings are verified by an empirical study using the Netflix dataset, where the proposed algorithms outperform several baselines for the problem at hand.
baseline.tex
%\vspace{\secSpace}
\subsection{Baselines}
\label{baseline}

%In this section we formulate the item cold start problem, and present several approaches to tackle it.
%In this section we present baseline approaches for both problems: first, for the rating prediction problem, and second, for the user selection problem. All presented baselines follow methods previously proposed in the literature, and evolve from the most na\"{i}ve ones to more sophisticated.

We turn to present several common and less common baselines from the recent literature. Recall that our problem (as defined in Equation~\eqref{prob_def}) was divided into two separate problems, and thus we consider two types of baselines. We begin with baselines for \textbf{Problem A}: rating prediction. 

\vspace{\secSpace}
%\subsection{Ratings Prediction Given Reviews}
%\label{problem1}
%
%Assume we are given a new item $i \not\in \mathcal{I}$, and a subset of %users
%users   $\mathcal{V}^i_B \subset \mathcal{V}^i$ who provided their ratings for this item. Our task is to  predict $\tilde{r}_{ui}$ for all $u \in \mathcal{U}$. 
%Recall our modeling assumption regarding each of ratings $r_{ui}$ from Equation \eqref{eq:LFM}.
%In particular, we assume that the ratings of the new item $i$ by the users within $\mathcal{V}^i_B $ follow this model as well, where  $ \mu $, $ b_u  $ and $  P_u  $ are given by our prediction model (Section \ref{pre}), whereas $ b_i  $ and $ Q_i $ are unknown to us (since the new item was not considered while training the model). 
%Therefore, all baseline predictors we present are aimed at estimating $ {b}_i $ and $ {Q}_i $, and consequently generate a prediction
%$$\tilde{r}_{ui} =  \mu + \tilde{b}_i  + b_u+  \tilde{Q}_i ^\top P_u .$$
%From now on, we denote by $ ( {b}_i , {Q}_i ^\top) $ the $(k+1)$-dimensional concatenation of $b_i$ and the vector $Q_i^\top$; the notation $ ( \tilde{b}_i , \tilde{Q}_i ^\top) $ shall stand for the corresponding estimator.  
%
%
%Recall, that user rating is generated by the following function:
%$$
%\tilde{r}_{ui} =  \mu + b_u + \tilde{b}_i +   \tilde{Q}_i ^\top P_u .
%$$
%where $\mu$, $b_u$ and $P_u$ are already known as we assume to have a trained LFM model. 
%Following are the 4 baseline predictors we consider:
%There are several methods one may consider to predict $\tilde{r}_{ui}$ for any $  u \in \mathcal{U} _i \setminus \mathcal{V}^i_B $ . We focus on the LFM based methods, in which we wish to define estimators $ ( \tilde{b}_i , \tilde{Q}_i ) $ and consequently generate a prediction:
%$$
%\tilde{r}_{ui} =  \mu + b_u + \tilde{b}_i +  P_u ^\top \tilde{Q}_i .
%$$
%Recall that $\mu$, $b_u$ and $P_u$ are known to us at this stage as we already have a trained model.
%\vspace{\parSpace}
%\paragraph{Mean rating predictor (A1)} The most na\"{i}ve predictor we consider uses the estimator $ ( \tilde{b}_i , \tilde{Q}_i ^\top) = \left( 0 , \bold{0}^\top \right)$. This predictor ignores the ratings of the $B$ users within $\mathcal{V}^i_B $, and simply predicts $ \tilde{r}_{ui} =   \mu + b_u$ for each of the users in $ \mathcal{U}$. Notice that for a given user $u$, this predictor assigns the same predicted rating $\tilde{r}_{ui}$, regardless of the new item considered. This rating is affected only by the previously provided ratings of the user, and the overall rating average.

%.  This predicted rating is affected only by the mean past rating of the userthe user provided to other items and the is overall rating average in the system. The resulting SSE for this estimator will be 
%$$
%\text{SSE} ( \tilde{b}_i , \tilde{Q}_i )   =  \sum_{u \in  \mathcal{U}_i \setminus  \mathcal{U}_{B}} \left( r_{ui} - \mu - b_u  \right)^2  .
%$$
%
%
% is affected only by the user bias and the overall rating average, but entirely ignores the item bias and the user-item interaction. Intuitively,  this predictor rates all unrated items based on the mean rating the user provided to other items and the is overall rating average in the system. The resulting SSE for this estimator will be 
%$$
%\text{SSE} ( \tilde{b}_i , \tilde{Q}_i )   =  \sum_{u \in  \mathcal{U}_i \setminus  \mathcal{U}_{B}} \left( r_{ui} - \mu - b_u  \right)^2  .
%$$
%[\textbf{comment:} we may add the expression of the resulting SSE. The later applies for all the methods]
%\vspace{\parSpace}
%\paragraph{Item bias predictor (A2)} A slightly less na\"{i}ve predictor assigns predicted ratings which are based on the average rating of the users within $\mathcal{V}^i_B $. The estimator is then  defined as follows:
% $$ \big(  \tilde{b}_i , \tilde{Q}_i^\top \big)  =  \left( \frac{1}{| \mathcal{V}^i_B |} \cdot \sum_{v \in \mathcal{V}^i_B } \left( r_{vi}  - b_v \right) - \mu \ \ , \ \ \bold{0}^\top \right) .$$
%This estimator ignores the user-item interaction as well, while the item bias is estimated by subtracting the average user bias and the overall rating average from the average rating of the $B$ users. For instance, if we get an average rating of $4$ by querying the $B$ users regarding item $i$, but in fact we know that these users tend to rate $0.2$ higher than the average, then the item bias is estimated as follows: $ \tilde{b}_i = 4 - 0.2 - \mu $. 
%Here also, we can explicitly write the resulting SSE:
% $$
%\text{SSE} ( \tilde{b}_i , \tilde{Q}_i )   =  \sum_{u \in  \mathcal{U}_i \setminus  \mathcal{U}_{B}} \left( r_{ui}  - b_u  -  \frac{1}{| \mathcal{V}^i_B |}  \sum_{v \in  \mathcal{V}^i_B  } \left( r_{vi}  - b_v \right)  \right)^2  .
%$$
\vspace{-0.3cm}
 \paragraph{Similarity based estimator} Just like the least squares estimator, this baseline seeks to estimate $( b_i , Q_i ) $ and consequently generate a prediction $\tilde{r}_{ui} =  \mu + \tilde{b}_i  + b_u+  \tilde{Q}_i  P_u $.
 The estimation uses the assigned users who liked the item, and relies on 
%  to generate $\tilde{Q}_i$ \cite{Paterek_KDD2007}. 
the following underlying assumption: ``good'' user-item interaction is expressed by the closeness of the corresponding representative vectors in the LFM space. 
%if the user's LFM vector is close enough to the users LFM vectors who liked this item, the user has a high chance to like this item as well. 
% This can be done by conjecturing that ``good'' user-item interaction is expressed by the closeness of the corresponding representative vectors in the LFM space. 
% Thus, yielding the following 
Thus, yielding the estimator:
 \begin{align*} 
 \tilde{b}_i & =   \frac{1}{| \mathcal{U}^i_B |} \cdot \sum_{v \in  \mathcal{U}^i_B  } \left( r_{vi}  - b_v \right) - \mu \ , \\
\tilde{Q}_i & =   \frac{1}{ \left| \{ v \in \mathcal{U}^i_B | r_{vi} \geq \gamma \} \right| } \cdot \sum_{v \in \mathcal{U}^i_B | r_{vi} \geq \gamma} P_v  \ ,
\end{align*}
where $\gamma$ is a predefined threshold (e.g., $4$ or $5$ for the Netflix dataset). Notice that the item's bias is estimated by subtracting the average user bias and the overall rating average from the average rating of the users within $\mathcal{U}^i_B$.
This approach was successfully practiced in \cite{Paterek_KDD2007,Koren_KDD2008,Aharon-Kagian-Koren-Lempel_RecSys2012,Aizenberg-Koren-Somekh_WWW2012}.
%\todo[inline]{OLEG:Why do we present SSE for some predictors and not for all of them?}
\vspace{\parSpace}

We continue with presenting baselines for \textbf{Problem B}: user selection.
\vspace{-0.3cm}

%
%\paragraph{Least squares predictor (A4)} Finally, we consider a theoretically optimal predictor, which  aims to estimate $( b_i , Q_i ^\top ) $ by minimizing the MSE over the set $\mathcal{V}^i_B$. More formally, we solve the following problem: 
%\begin{equation*} 
%\min_{ \substack{b \in \mathbb{R} \\\ q \in  \mathbb{R}^k }}  \left\{ \frac{1}{ \left|  \mathcal{V}^i_B  \right|  } \cdot \sum_{ v \in \mathcal{V}^i_B } \left(  r_{vi} - q^\top P_v- b - b_v - \mu \right)^2     
%\right\}  .
%\end{equation*}
%%\begin{align*} 
%%& ( \tilde{b}_i , \tilde{Q}_i )  = \arg\min_{(b,q) \in \mathbb{R}^{\ell+1}}  \Bigg\{ \sum_{u \in \mathcal{V}^i_B } \left(  r_{ui} - q^\top P_u- b - b_u - \mu \right)^2     \nonumber\\
%%&  \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \quad  +  \lambda \left( \| q \|_2^2 + b^2 \right)\Bigg\}  ,
%%\end{align*}
%%$$ ( \tilde{b}_i , \tilde{Q}_i )  = \arg\min_{(b,q) \in \mathbb{R}^{\ell+1} } \Bigg\{ \sum_{u \in \mathcal{V}^i_B } \left(  r_{ui} - q^\top P_u- b - b_u - \mu \right)^2  + \lambda \left( \| q \|_2^2 + b^2 \right)\Bigg\}  , $$
%%where $\lambda$ is a regularization parameter.
%This minimization problem is in fact analytically solvable, and yields the following solution:
%\begin{equation*} 
%\big(  \tilde{b}_i , \tilde{Q}_i^\top \big) 
%= \left( \sum_{ v \in \mathcal{V}^i_B } (r_{vi} - b_v - \mu ) \cdot {P}_v^{\prime \top} \right) \left(  \sum_{ v \in \mathcal{V}^i_B } {P}^\prime_v {P}_v^{\prime \top} \right)^{-1}  ,
%\end{equation*}
%%\begin{align*} 
%%& ( \tilde{b}_i , \tilde{Q}_i )  \nonumber\\
%%& = \left( \sum_{u \in \mathcal{V}^i_B } (r_{ui} - b_u - \mu ) \cdot {P}_u^{\prime \top} \right) \left( \lambda \cdot I + \sum_{u \in \mathcal{V}^i_B } {P}^\prime_u {P}_u^{\prime \top} \right)^{-1}  ,
%%\end{align*}
%%$$ ( \tilde{b}_i , \tilde{Q}_i ) =  \left( \sum_{u \in \mathcal{V}^i_B } (r_{ui} - b_u - \mu ) \cdot {P}_u^{\prime \top} \right) \left( \lambda \cdot I + \sum_{u \in \mathcal{V}^i_B } {P}^\prime_u {P}_u^{\prime \top} \right)^{-1}  ,$$
%where $   {P}^\prime_v $ is the concatenated column vector $  ( 1 ,  {P}^\top_v )^\top $.
%
%\vspace{\parSpace}
%
%The above might  not be well-defined since $\sum_{ v \in \mathcal{V}^i_B } {P}^\prime_v {P}_v^{\prime \top}$ need not be invertible in general. In practice,  a regularization term of the form $\lambda \left( \| q \|_2^2 + b^2 \right)$ is usually added to the objective function to avoid this problem. The estimator $ ( \tilde{b}_i , \tilde{Q}_i ^\top )$  then takes the following form:
% \begin{equation*} 
% \left( \sum_{v \in \mathcal{V}^i_B} (r_{vi} - b_v - \mu ) \cdot {P}_v^{\prime \top} \right) \left( \lambda \cdot I + \sum_{v \in \mathcal{V}^i_B } {P}^\prime_v {P}_v^{\prime \top} \right)^{-1}  .
%\end{equation*}
%In the sequel, we will assume that $\sum_{ v \in \mathcal{V}^i_B } {P}^\prime_v {P}_v^{\prime \top}$ is invertible to ease the readability of the paper. We emphasize that all the  results presented in this paper would still hold for the regularized predictor.
%
%\vspace{\parSpace}
%
%In the experimental section, we compare the performances of the aforementioned predictors, and show that the least squares predictor (A4) outperforms the other predictors (A1-A3), regardless of the selection method of $ \mathcal{V}^i_B$.
%
%% 
%% The problem then takes the following form:
%%\begin{align*} 
%%& ( \tilde{b}_i , \tilde{Q}_i )  = \arg\min_{(b,q) \in \mathbb{R}^{\ell+1}}  \Bigg\{ \sum_{u \in \mathcal{V}^i_B } \left(  r_{ui} - q^\top P_u- b - b_u - \mu \right)^2     \nonumber\\
%%&  \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \quad  +  \lambda \left( \| q \|_2^2 + b^2 \right)\Bigg\}  ,
%%\end{align*}
%%where $\lambda$ is a regularization parameter. The corresponding solution is 
%%\begin{align*} 
%%& ( \tilde{b}_i , \tilde{Q}_i )  \nonumber\\
%%& = \left( \sum_{u \in \mathcal{V}^i_B } (r_{ui} - b_u - \mu ) \cdot {P}_u^{\prime \top} \right) \left( \lambda \cdot I + \sum_{u \in \mathcal{V}^i_B } {P}^\prime_u {P}_u^{\prime \top} \right)^{-1}  ,
%%\end{align*}
%
%%, and $I$ is the identity matrix of size ${(\ell+1)\times (\ell+1) }$.
%%
%%
%%Notice that if we define $ \tilde{Q}_i = \left( b_i , Q_i \right)$, $ \tilde{q} = \left( b , q \right)$, $ \tilde{P}_u = \left( 1 , P_u \right)$, and $ \tilde{r}_{ui} = r_{ui} - b_u - \mu $ we can equivalently write:
%%$$ \tilde{Q}_i   = \arg\min_{\tilde{q} \in \mathbb{R}^{\ell+1} } \left\{ \sum_{u \in U_{B_i}} \left(  \tilde{r}_{ui} - \tilde{q}^\top \tilde{P}_u  \right)^2  + \lambda \left( \| \tilde{q} \|_2^2 \right)\right\}  ,$$
%%and this problem is analytically solvable and yields the solution:
%%$$ \tilde{Q}_i =  \left( \sum_{u \in U_{B_i}} \tilde{r}_{ui} \tilde{P}_u \right) \left( \lambda \cdot I_{(\ell+1)\times (\ell+1) } + \sum_{u \in U_{B_i}} \tilde{P}_u \tilde{P}_u^\top \right)^{-1}  .$$
%
%%We compare the yielded RMSE for the aforementioned methods (A1-A4) in the experiments section and show that, as expected, the performance is improving from (A1) to (A4).
%
%
%%Figure \ref{fig2} compares the resulting RMSE for each of the aforementioned methods (1a-1d), averaged over 50 random selections of $ \mathcal{V}^i_B$ for each of the 100 movies in the test set.  We note that similar results are obtained for any other selection of  $\mathcal{V}^i_B$ (rather than only random), and thus omitted here. 
%%\begin{figure}[h!] 
%%  \centering
%%    \includegraphics[width=0.45 \textwidth]{compare_calc}
%%     \caption{\textbf{Baseline comparison.} Each of the four methods (1a-1d) was tested on 100 new movies. For each of these movies we randomly selected $B$ users ($B=2,4,\ldots,100$), and applied all four methods to generate predictions for the remaining users. This routine was repeated 50 times and then averaged to ensure stability.}
%%          \label{fig2}
%%\end{figure}
%
%\vspace{\secSpace}
%
%\subsection{user Selection}
%\label{problem2}
%
%Next, we consider several baselines for tackling the problem of selecting the subset $\mathcal{V}^i_B \subset \mathcal{V}^i$. 
%\vspace{\parSpace}

\paragraph{Forward greedy selection (B1)} This baseline relies as well on the optimal design approach, and specifically on the A-optimality criterion. Basically, it aims to minimize the trace of the inverse of the information matrix $P_B P_B^\top$, similarly to our first algorithm. However, the selection is done in a forward manner: starting with an empty set, and greedily adding the user whose contribution is the highest. This approach was successfully practiced in many fields of active learning, rather than only for the item cold-start problem of CF-based recommenders (see \cite{krause2007near} for a more comprehensive survey). However, we are not aware of any performance guarantee for this algorithm. 

%We are not aware of any performance guarantee for this algorithm, yet it is one the most common algorithms in the active learning literature 

\vspace{-0.1cm}

\paragraph{Clustering (B2)} Intuitively, having a heterogeneous set of users will result in a more objective ratings of the item. To this end, we suggest to cluster the users with respect to their representation in the Euclidean LFM space and subsequently sample from the resulting clusters. For the clustering task, we use the standard $k$-means algorithm with cosine similarity set to be its similarity measure.

\vspace{-0.1cm}

We propose two clustering-based baselines for the selection problem, each differs in the number of clusters and the sampling procedure: (1) split  the pool of available users into $B$ clusters, and select the users 
that are closest to the cluster center of mass (one user per cluster); and (2) split the pool of available users into $c$ clusters (where $c<B$), and from each cluster select number of users at random and proportionally to the cluster size. For this baseline, the value of $c$ is determined empirically.

\vspace{-0.1cm}

\paragraph{Random selection (B3)} In this baseline, the $B$ users are selected randomly  from the pool of available users. 
At first glance, this baseline seems rather weak. However, if $B$ is sufficiently large, then $\mathcal{U}^i_B $ is a statistically good representative of $ \mathcal{U}^i$, and this baseline cannot be easily beaten. Moreover, this baseline has many practical appeals and is thus very popular with state-of-the-art recommenders.

\vspace{-0.1cm}

\paragraph{Frequent raters (B4)} Here we select users who tend to provide many ratings. This baseline utilizes the following conjecture: users with extensive rating history have better modeling in CF-based recommender systems. Therefore, preferring these users over users that have limited rating history seems reasonable in our setting. 

\vspace{-0.1cm}

\paragraph{Edgy raters (B5)} This baseline selects users that provide diverse ratings, or more accurately, ratings with large variance. Intuitively, these users provide more information regarding an item they like or dislike, than users that tend to rate all items in a similar manner. 

\vspace{-0.1cm}

\paragraph{Early birds raters (B6)} This baseline slightly differs from the previous baselines: instead of actively selecting users to rate the new item, we 
conceptually invite all users to opine on the new item at their convenience, and  
consider the (chronologically) first $B$ returned ratings as our selection. The intention here is not to offer another active selection baseline, but rather to study the utility of early reviews, coming from people who are enthusiastic about trying out the new item, for modeling the rest of the population.

\vspace{-0.1cm}




conclusions.tex
\vspace{\secSpace}
\section{Conclusions and Future Work}
\label{sec:conc}

In this work we started with a mature LFM model and tried to tackle the item cold-start problem by answering two questions: (a) given ratings of $B$ users, how can we estimate other users' ratings of an arbitrary new item without retraining the model? and (b) how to choose the set of $B$ users? We showed that in order to get approximately optimal results in terms of mean squared error, the above questions should be tackled jointly. In particular, we applied optimal design techniques and devised two greedy algorithms that achieve that goal under certain assumptions. We used the Netflix dataset to demonstrate the superiority of the proposed algorithms over a set of previously considered and non-considered baselines.

Our work can be seen as a ``one-shot'', non-adaptive active learning scheme that selects the $B$ userrs at once. This leaves three interesting variants for future work.
The first variant we consider is an {\em adaptive active learning} scheme, in which users are chosen sequentially, with each selection done only after receiving the ratings of the previously chosen user.
The second variant tackles an {\em online} version of the problem, where potential users arrive one by one and the publisher must decide whether to assign them the item or not. In several recommendation settings, e.g. news recommendations, new items constantly arrive and have very short lifetimes, thereby requiring that the publisher identifies quickly which users to recommend them to. 
The tradeoff between (1) selecting a good set of users, and (2) quickly completing the reviewing process of the item, presents a challenging optimization problem. The third variant discusses a {\em multi-item} setting, where the publisher must concurrently explore several new items while users can review only one or a small fixed number of items. Note that the multi-item setting can be investigated in both the offline and the online settings.


In addition to the above variants, an interesting direction would be to study the user cold-start problem using the techniques we presented in this work. As discussed in the related work section, the user and the item cold-start problem are essentially different, mainly due to the ability to adaptively interview new users in order to bootstrap their modeling. Whereas this enables decision tree type solutions for user cold-start handling (which are currently the state-of-the-art), such solutions cannot be implemented in the setting considered in this paper. However, applying the optimal design approach to the user cold-start problem is possible and may potentially lead to better theoretical and empirical guarantees. 
experiments.tex
\vspace{\secSpace}
\section{Experimental results}
\label{sec:results}
%[\textbf{comment:} I think there is inconsistency with the notion of the sets]
This section compares the performance of the proposed algorithms with that of several baselines. We start by presenting the dataset and model, followed by our experimental setup.

\subsection{Dataset and Model}
\label{sec:setup}

%\subsection{Dataset and Model} 
We consider a large movie ratings dataset released by Netflix as the basis of a well publicized competition \cite{Bennett-Lanning_KDD2007}. The original dataset contains more than $100$ million date-stamped ratings (integers between $1$ and $5$) collected between Nov. 11, 1999 and Dec. 31, 2005, from about $480,000$ anonymous Netflix customers on $17,770$ movies. 
%Ratings are integers ranging between $1$ and $5$.


The dataset is processed as follows: a new ratings matrix (denoted henceforth by $\mathcal{R}$) is constructed from $17,000$ arbitrarily chosen movies. The matrix $\mathcal{R}$ contains about $96$ million ratings from the same number of users as in the original dataset. The other 770 movies are used as ``new items'' in the various experiments we conducted. Note that since most users have not rated most of the movies, the ratings matrix $\mathcal{R}$ is very sparse (only $1\%$ of all ratings exist).

We factorize $\mathcal{R}$ using the LFM (Equation \eqref{eq:LFM}), with its dimension set to be $k=20$. We use the common Root Mean Squared Error (RMSE) metric to measure the prediction accuracy of the resulted model. For the task of minimizing this metric, we apply the Stochastic Gradient Descent (SGD) algorithm, where the learning rate is inspired by the AdaGrad algorithm of  \cite{duchi2011adaptive}. Due to lack of space, the technical details regarding the model construction and evaluation are omitted here.

\subsection{Experimental Setup}
We now describe how we test algorithms for user selection in an offline manner on the Netflix dataset.
As mentioned before, a set of $770$ movies is withheld from our model. We henceforth denote this set by $\mathcal{N}$, and think of it as a set of movies that are new to our recommender system. 
For each movie $i \in \mathcal{N}$, we denote by $\mathcal{R}(i)$ the set of Netflix users who have actually rated this movie. We then adapt the dataset to our setting as follows:
\vspace{-0.1cm}
\begin{description}
\vspace{-0.07cm}
\item[The pool of available users:] we consider the set $\mathcal{R}(i)$ as the pool of available users to rate movie $i$, i.e., we set $\mathcal{U}_i = \mathcal{R}(i)$.
Note that indeed, $\mathcal{U}^i$ changes for every movie $i$, as the actual available ratings differ from one movie to another in the Netflix dataset. This coincides with the pool of available users changing in time.
\vspace{-0.07cm}
\item[Selecting a subset of users:] the conceptual step of assigning a subset of users $\mathcal{U}^i_{B} \subset  \mathcal{U}^i$ to rate movie $i$ corresponds to the action of revealing their actual ratings in the dataset. 
\vspace{-0.07cm}
\item[The set of all users:] due to the small portion of actual ratings in the dataset, we cannot measure the prediction error on all users. Thus,
after revealing the actual ratings of the subset $\mathcal{U}^i_{B} $, we use the remaining unrevealed ratings for this task, i.e., we set $\mathcal{U} = \mathcal{U}_i \setminus \mathcal{U}_B^i$.  Note that we {\em  essentially use the non-selected users for the evaluation task} in this step. 
\end{description}
\vspace{-0.1cm}
Despite the fact that our analysis was carried out using the MSE metric, we measure the prediction error of the different approaches using the RMSE metric:
\begin{equation*}
\text{RMSE} \big( \mathcal{U}^i_B \big) =  \sqrt{ \frac{1}{\left| \mathcal{U} \right|} \sum_{u \in \mathcal{U}} \left(  {r}_{ui} - \tilde{r}_{ui} \right)^2 }  .
\end{equation*}
Since the root square is a monotone function, minimizing the MSE is equivalent to minimizing the RMSE (in the sense that both problems has the same minimizer). Thus, to be consistent with previous works, our experimental results are presented using the RMSE metric.


\input{baseline}


\subsection{Results}
We separately report the results for each of the considered problems, starting with the rating prediction problem and moving on to the user selection problem.

\subsubsection{Rating Prediction Comparison}
We compare the performance of the least squares estimator and the similarity based estimator.
%In this section we compare the performances of the rating prediction baselines, which are described in Section \ref{problem1}.  
To this end, we selected 300 movies from the set $\mathcal{N}$, arbitrarily.  For each of these movies, we randomly selected $B$ users ($B=2,4,\ldots,100$), and applied both estimators to generate predictions for the remaining users. The prediction accuracy was measured using the RMSE metric over all predictions (and not separately for each movie).
This routine was averaged over 50 runs to ensure stability. 
\begin{figure}[tb] 
  \centering
    \includegraphics[width=0.45 \textwidth]{comparecalc-eps-converted-to.pdf}
     \caption{\textbf{Rating prediction comparison.} }
          \label{fig1}
\end{figure}

As evident in Figure \ref{fig1}, the least squares estimator outperforms the considered baseline. 
Qualitatively, similar results were obtained when applying the other (non-random) selection schemes of $B$ users, and are thus omitted here. 

\subsubsection{User Selection Comparison}
Here the performance of our approach is compared with the baselines (presented in Section \ref{baseline}) for \textbf{Problem B}. To carry out  the experiment, we select 300 movies from the set $\mathcal{N}$, arbitrarily.  For each of these movies, we apply all six baselines (B1-B6) and our two algorithms (denoted by BGS1 and BGS2) to select a subset of $B$ users. We then generate $( \tilde{b}_i , \tilde{Q}_i )$ using the least squares estimator (or the generalized least squares estimator for BGS2), regardless of how the selection was made. Since this estimator outperforms the similarity based estimator for any selection of $B$ users (as demonstrated in Figure \ref{fig1}), we do not lose information by omitting them. Here again, we measure the prediction accuracy using the RMSE metric over all predictions. For the non-deterministic baselines: Clustering (B2) and Random (B3), we averaged the results over 50 runs  to ensure stability.


\begin{figure}[t!]
  \centering
    \includegraphics[width=0.45 \textwidth]{comparison-eps-converted-to.pdf}
     \caption{User selection comparison.} 
          \label{fig2}
\end{figure}


As can be seen in Figure \ref{fig2}, the optimal design based algorithms outperform the other baselines for almost any budget. 
In particular, BGS2 (which  accounts for independent yet not identically distributed noises) significantly surpasses BGS1 and B1 (which are practically indistinguishable) for any budget. The second best performing baseline is B5, which utilizes the ratings of the ``edgy'' users. We conjecture that such users provide more information regarding a new item, in addition to being well-scattered in the LFM space. Baselines B2 and B3 (Random and Clustering\footnote{We present here only the better performing clustering technique, which is the second one discussed in Section \ref{baseline}.}) seem to perform similarly in our setting, yet a closer look discovers that by clustering the users in the LFM space we get more stable results (in the sense of lower variance of the resulted RMSE). We remind the reader that our basic CF model was trained using state-of-the-art algorithms, where every percent of improvement is not easily achieved.  
%
%In particular, the GS2 algorithm (which  accounts for independent yet not identically distributed noises) beats all baselines already for small budget values $B>10$, while the GS1 algorithm beats all baselines for mild budget values $B>45$. Moreover, the two algorithms achieve similar results with increasing budget values $B>75$. For low budget values $B<10$ the random selection baseline prevails. Also notable is the fact that the Edgy selection baseline beats the other baselines for budget values $B>60$. We remind the reader that our basic CF model was trained using state-of-the-art algorithms, where every percent of improvement (e.g.,  $\sim 2\%$ improvement on average of GS2 for $B=30$) is not easily achieved.  


%\oa{Can someone add some insights?}
%\oa{the plots will be replaced by nicer ones}


introduction.tex
\section{Introduction}
\label{intro}
Recommendation technologies are increasingly being used to route relevant and enjoyable information to users. Whether they try to navigate through overwhelming Web content, choose a restaurant, or simply find a book to read, users  find themselves being guided by modern online services that use recommendation systems.  Usually, such services are based on users' feedback and stated preferences, and use editors, content analysis or wisdom of the crowds to tag their database items.

One of the most common and effective recommendation techniques is Collaborative filtering (CF). This technique relies only on past user behavior (e.g., previous transactions or feedback), and does not require the creation of explicit profiles. Moreover, it requires no domain knowledge or content analysis, and excels at exploiting popularity trends, which drive much of the observed user interaction. 

One of the fundamental problems arising when employing CF techniques is the \textit{cold-start} problem. Roughly speaking, the cold-start problem is caused by the system's incapability of dealing with new items or new users due to the lack of relevant transaction history. 

This work focuses on the item cold-start problem, \textit{without} assuming any availability of context nor content-based information. In particular, we consider the following setting: a publisher has a set of users, and is aware of those users' historical ratings of items (movies, books, etc.). Now the publisher is interested in evaluating a new item, on which she has no prior knowledge. At her disposal is a pool of available users, from which she can assign $B$ users to the task of rating the new item. After receiving their ratings, the publisher estimates, to the best extent possible, how the remaining users will rate the new item. 

In order to mitigate the reviewing period, the $B$ users are all selected at once - the publisher does not have the luxury to receive some ratings, and then to adaptively select additional users based on that signal. An important aspect of this problem setting is that the satisfaction of the assigned users does not factor into the equation - there is no cost associated with selecting a user who will dislike the item. The sole purpose is to select  users who will provide best characterization of the new item. 


The rest of this paper is organized as follows: the remaining of this section presents informal statement of our results, and surveys the related work. Section~\ref{pre} introduces notations and concretely defines the problem. Section~\ref{optimal} then presents our optimal design based algorithms and analysis.
%Section~\ref{sec:setup} describes the experimental setup. 
Experimental results are reported in Section~\ref{sec:results}. We conclude and discuss future work in Section~\ref{sec:conc}.



\subsection{Informal Statement of Results} \label{informal}
We adopt a common assumption in \textit{Matrix Factorization} (MF)-based CF \cite{Koren-Bell-Volinsky_IEEE-Comp-2009}:  ratings of items by users can be well approximated by the product of two low-dimensional matrices, one representing low-dimensional latent vectors of users, and the other holding latent representations of items. The problem at hand then translates to the following mathematical abstraction: given latent vectors representing each of the users, and a new item whose latent vector is unknown, choose which $B$ ratings to reveal so that the item's latent vector could be estimated most accurately.


The main contributions of this work are as follows: (1) We cast this budget-constrained user selection problem as an optimization problem, in which the objective function stands for the expected prediction error of our model. (2) We devise two novel optimal design based algorithms for the problem, each attains approximation to the optimum under certain assumptions. (3) We validate the theoretical results with an empirical study, by simulating the setting of the problem using the Netflix dataset and comparing the effectiveness of our algorithms to that of several baselines.
%
%\vspace{\parSpace}
%\begin{enumerate}
%\item We cast this budget-constrained user selection problem as an optimization problem, in which the objective function stands for the expected prediction error of our model.
%\vspace{-0.1cm}
%\item We devise two optimal design based algorithms for the optimization problem, each attains approximation to the optimum under certain assumptions.
%%RL: removing this. It falls under the "certain assumptions" statement anyway, and it is unclear at this point what estimation noises are. In any case, one could argue that the iid case is just "warm up" for the more general case.
%%The algorithm comes in two flavors. A setting where the estimation noises are assumed i.i.d., and a setting where estimation noises are identically distributed but are allowed to have different variances.
%\vspace{-0.1cm}
%\item We validate the theoretical results with an empirical study, by simulating the setting of the problem with the Netflix dataset and comparing the effectiveness of our algorithms to that of several baselines.
%\end{enumerate}

\vspace{\parSpace}


\subsection{Related Work}
\label{sec:related}
\input{previous}

%
%Recommendation technologies are increasingly being used to route relevant and enjoyable information to users. Whether they try to navigate through overwhelming Web content, choose a restaurant, or simply find a book to read, users  find themselves being guided by modern online services that use recommendation systems.  Usually, such services are based on users' feedback and stated preferences, and use editors, content analysis or wisdom of the crowds to tag their database items.
%
%One of the most common and effective recommendation techniques is Collaborative filtering (CF). This technique relies only on past user behavior (e.g., previous transactions or feedback), and does not require the creation of explicit profiles. Moreover, it requires no domain knowledge or content analysis, and excels at exploiting popularity trends, which drive much of the observed user interaction. %, and typically would be completely missed by content based approaches. 
%%RL: removed the "completely missed" sentence as that may piss off content folks. Furthermore, one can incorporate popularity signals without CF.
%In addition, relying directly on user behavior allows uncovering complex and unexpected patterns that would be difficult to profile using known data attributes.
%
%\vspace{\parSpace}
%
%One of the fundamental problems arising when employing CF techniques is the \textit{cold-start} problem. Roughly speaking, the cold-start problem is caused by the system's incapability of dealing with new items or new users due to the lack of relevant transaction history. 
%
%%A great deal of work has been done on solving the user cold-start problem, mainly exploiting the ability to query the new user regarding his preferences. This can be done either by directly querying the user, or by performing a simple analysis of his relevant historical background (if available). The item cold start problem is in a sense harder, since we cannot query the item regarding its preferred users.
%
%\vspace{\parSpace}
%
%This work focuses on the item cold-start problem, \textit{without} assuming any availability of context nor content-based information. In particular, we consider the following setting: a publisher has a set of customers, and is aware of those customers' historical ratings of items (movies, books, etc.). Now the publisher is interested in evaluating a new item. At her disposal is a pool of available reviewers, from which she can assign $B$ reviewers to the task of rating the new item. After receiving their ratings, the publisher estimates, to the best extent possible, how the customers will rate the new item. 
%%Naturally, the publisher's ability to effectively recommend the item to her customers depends on her ability to identify $B$ reviewers that model the customers well.
%
%\vspace{\parSpace}
%
%We assume that the publisher has no prior knowledge about the new item when selecting the reviewers. To mitigate the reviewing period, the $B$ reviewers are all selected at once for the task - the publisher does not have the luxury to receive some ratings, and then to adaptively select additional reviewers based on that signal. An important aspect of this problem setting is that the satisfaction of the reviewers from the item does not factor into the equation - there is no cost (or regret) associated with selecting a reviewer who will dislike the item. The sole purpose is to understand how the customer base will react to the new item.
%
%\vspace{\parSpace}
%
%We adopt a common assumption in \textit{Matrix Factorization} (MF)-based CF \cite{Koren-Bell-Volinsky_IEEE-Comp-2009}:  ratings of items by people (in this case, both reviewers and customers) can be approximated by the product of two low-dimensional matrices, one representing low-dimensional latent vectors of people, and the other holding latent representations of items. The problem at hand then translates to the following mathematical abstraction: given latent vectors representing each reviewer and user, and given a new item whose latent vector is unknown, choose which $B$ ratings of reviewers to reveal so that the item's latent vector could be estimated most accurately.
%
%\vspace{\parSpace}
%
%The main contributions of this work are as follows:
%\vspace{\parSpace}
%\begin{enumerate}
%\item We formulate this budget-constrained reviewer selection problem as an optimization problem, in which the objective function stands for the prediction error of the users' ratings.
%\vspace{-0.1cm}
%\item We devise two optimal design based algorithms for the optimization problem, each attains approximation to the optimum under certain assumptions.
%%RL: removing this. It falls under the "certain assumptions" statement anyway, and it is unclear at this point what estimation noises are. In any case, one could argue that the iid case is just "warm up" for the more general case.
%%The algorithm comes in two flavors. A setting where the estimation noises are assumed i.i.d., and a setting where estimation noises are identically distributed but are allowed to have different variances.
%\vspace{-0.1cm}
%\item We validate the theoretical results with an empirical study, by simulating the setting of the problem with the Netflix dataset and comparing the effectiveness of our algorithms to that of several baselines.
%\end{enumerate}
%
%\vspace{\parSpace}
%
%The rest of this paper is organized as follows. Section~\ref{sec:related} surveys related work.
%Section~\ref{pre} introduces notations and concretely defines the problem. Section~\ref{baseline} proposes several baselines to tackle the problem at hand. Section~\ref{optimal} then presents our algorithms, based on optimal design.
%%Section~\ref{sec:setup} describes the experimental setup. 
%Results are reported in Section~\ref{sec:results}. We conclude in Section~\ref{sec:conc}.

itemColdStart_WWW2014.tex
% THIS IS SIGPROC-SP.TEX - VERSION 3.1
% WORKS WITH V3.2SP OF ACM_PROC_ARTICLE-SP.CLS
% APRIL 2009
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V3.2SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V3.2SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
% ---------------------------------------------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@hq.acm.org
%
% For tracking purposes - this is V3.1SP - APRIL 2009

\documentclass{acm_proc_article-sp}

\usepackage{algorithmic}
\usepackage{algorithm}

\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{url}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{graphics}
\usepackage{theorem}
\usepackage{euscript}
\usepackage{psfrag}
\usepackage{bbm}
\usepackage{todonotes}

\usepackage{flushend}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

% MATH -------------------------------------------------------------------
\newcommand{\Real}{\mathcal Re}
\newcommand{\Imaginary}{\mathcal Im}
\newcommand{\RPlus}{\Real^{+}}
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\seq}[1]{\left<#1\right>}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\BX}{\mathbf{B}(X)}
\newcommand{\A}{\mathcal{A}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\Lom}{\mathcal{L}}
\newcommand{\Comp}{\mathcal{K}}
\newcommand{\Basis}{\mathcal{B}}

\newcommand{\Bepsilon}{\boldsymbol{\epsilon}}
\newcommand{\Bb}{\text{\textbf{\textit{b}}}}
\newcommand{\Boldit}[1]{\textbf{\textit{#1}}}
\newcommand{\Boldsf}[1]{\textbf{\textsf{#1}}}
\newcommand{\Boldcal}[1]{\mathbf{\mathcal{#1}}}
\newcommand{\Bs}[1]{\boldsymbol{#1}}
\newcommand{\EuS}[1]{\EuScript{#1}}
\newcommand{\Mfr}[1]{\mathfrak{#1}}
\newcommand{\vct}[1]{\boldsymbol{#1}}
\newcommand{\Mat}[1]{\boldsymbol{#1}}

\newcommand{\Indic}[1]{\mathbbmtt{1}_{\set{#1}}}

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{conj}{Conjecture}
\newtheorem{assumption}{Assumption}


\def\E{{\mathbb E}}        % expectation



%--------------------various
\newcommand{\zk}[1]{\noindent{\textcolor{blue}{\{{\bf ZK:} \em #1\}}}}
\newcommand{\oa}[1]{\noindent{\textcolor{magenta}{\{{\bf OA:} \em #1\}}}}

\def\myscale{0.5}
\def\secSpace{0cm}
\def\parSpace{-0.08cm}
\renewcommand{\baselinestretch}{1.0}

\newcommand{\comment}[1]{}
\newcommand{\paren}[1]{\left( #1 \right)}
\newcommand{\bracket}[1]{\left[ #1 \right]}

\usepackage{etoolbox} \makeatletter \patchcmd{\maketitle}{\@copyrightspace}{}{}{} \makeatother 

\begin{document}

%\title{An Optimal Design Approach for Budget-Constrained Item Cold-Start Handling in Collaborative Filtering Recommenders}
%RL: two possible 2-line variants with the application stated upfront
\title{Budget-Constrained Item Cold-Start Handling in Collaborative Filtering Recommenders via Optimal Design }
%\title{Budget-Constrained Item Cold-Start Handling via Optimal Design in Collaborative Filtering Recommenders}
%\titlenote{(Does NOT produce the permission block, copyright information nor page numbering). For use with ACM\_PROC\_ARTICLE-SP.CLS. Supported by ACM.}}

%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{6} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Oren Anava\\
       \affaddr{Technion, Haifa, Israel}\\
       \email{oanava@tx.technion.ac.il}
% 2nd. author
\alignauthor
Shahar Golan\\
       \affaddr{Yahoo Labs, Haifa, Israel}\\
       \email{shaharg@yahoo-inc.com}
% 3rd. author
\alignauthor Nadav Golbandi\\
       \affaddr{Yahoo Labs, Haifa, Israel}\\
       \email{nadavg@yahoo-inc.com}
\and  % use '\and' if you need 'another row' of author names
% 4th. author
\alignauthor Zohar Karnin\\
       \affaddr{Yahoo Labs, Haifa, Israel}\\
       \email{zkarnin@yahoo-inc.com}
% 5th. author
\alignauthor Ronny Lempel\thanks{Work was done while the author was at Yahoo Labs.} \\
       \affaddr{Outbrain Inc., Netanya, Israel}\\
       \email{rlempel@outbrain.com}
% 6th. author
\alignauthor Oleg Rokhlenko\\
       \affaddr{Yahoo Labs, Haifa, Israel}\\
       \email{olegro@yahoo-inc.com}
\and
\alignauthor Oren Somekh\\
      \affaddr{Yahoo Labs, Haifa, Israel}\\
     \email{orens@yahoo-inc.com}
}
%% There's nothing stopping you putting the seventh, eighth, etc.
%% author on the opening page (as the 'third row') but we ask,
%% for aesthetic reasons that you place these 'additional authors'
%% in the \additional authors block, viz.
%\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
%email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
%(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
%\date{30 July 1999}
%% Just remember to make sure that the TOTAL number of authors
%% is the number that will appear on the first page PLUS the
%% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}
It is well known that collaborative filtering (CF) based recommender systems provide better modeling of users and items associated with considerable rating history. The lack of historical ratings results in the user and the item cold-start problems. The latter is the main focus of this work. Most of the current literature addresses this problem by integrating content-based recommendation techniques to model the new item. However, in many cases such content is not available, and the question arises is whether this problem can be mitigated using  CF techniques only. We formalize this problem as an optimization problem: given a new item, a pool of available users, and a budget constraint, select which users to assign with the task of rating the new item in order to minimize the prediction error of our model. We show that the objective function is monotone-supermodular, and propose efficient optimal design based algorithms that attain an approximation to its optimum. Our findings are verified by an empirical study using the Netflix dataset, where the proposed algorithms outperform several baselines for the problem at hand. 
\end{abstract}

\vspace{-0.2cm}
% A category with the (minimum) three required fields
\category{H.2.8}{Database Management}{Database Applications}[Data Mining]
\vspace{-0.2cm}
\terms{Algorithms, Experimentation}
\vspace{-0.2cm}
\keywords{collaborative filtering, item cold-start, optimal design} % NOT required for Proceedings

\input{introduction}
\input{preliminaries}
%\input{baseline}
\input{optimal}
\input{experiments}
\input{conclusions}

% ------------------------------------------------------------------------
% Bibliography
% ------------------------------------------------------------------------
%\additionalauthors{Additional author: Oren Somekh (Yahoo! Labs, Haifa, Israel, email: {\texttt{orens@yahoo-inc.com}}).}

\bibliographystyle{plain}
\bibliography{itemColdStart}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%\appendix
%\input{appendices}
%\balancecolumns
\end{document}



optimal.tex
%\vspace{-0.3cm}
\section{Algorithms and Analysis}
\label{optimal}

In this section we tie together the two problems described in Section \ref{pre}, and present a holistic approach that tackles the unified problem as a whole - the optimal design approach. \textit{Optimal design} is a statistic paradigm  \cite{atkinson1992optimum,Wu78} that is aimed at selecting which experiments to conduct out of a given pool in order to maximize the result accuracy. In our setting, we wish to select a subset of users such that the prediction error of our model is minimized. Roughly speaking, the optimal design approach seeks to estimate the MSE (over the entire user set) for each selection of $B$ users, \emph{without} exposing their actual ratings. This way, we can evaluate the merit of any given subset of users (in terms of MSE), and make the selection accordingly.


Basically, the optimal design approach relies on the assumption that the ratings are generated via Equation~\eqref{eq:LFM_ground}, and consequently on the optimal solution for \textbf{Problem A}: least squares estimation. To make this point clearer we first introduce this estimator.


\subsection{Least Squares Estimation}
Assume we are given a new item $i \not\in \mathcal{I}$, and a subset of %users
users   $\mathcal{U}^i_B \subset \mathcal{U}^i$ who provided their ratings for this item. Our task is to  predict $\tilde{r}_{ui}$ for all $u \in \mathcal{U}$. 
Recall our modeling assumption regarding each of ratings $r_{ui}$ from Equation \eqref{eq:LFM_ground}.
In particular, we assume that the ratings of the new item $i$ by the users within $\mathcal{U}^i_B $ follow this model as well, where  $ \mu $, $ b_u  $ and $  P_u  $ are given by our prediction model (Section \ref{pre}), whereas $ b_i  $ and $ Q_i $ are unknown to us (since the new item was not considered while training the model). 
Therefore, the least squares estimator seeks to estimate $ {b}_i $ and $ {Q}_i $, and consequently to generate a prediction
$$\tilde{r}_{ui} =  \mu + \tilde{b}_i  + b_u+  \tilde{Q}_i  P_u .$$
From now on, we denote by $ ( {b}_i , {Q}_i ) $ the $(k+1)$-dimensional concatenation of $b_i$ and the vector $Q_i$; the notation $ ( \tilde{b}_i , \tilde{Q}_i ) $ shall stand for the corresponding estimator.  

Using these notations, the least squares estimator aims to estimate $( b_i , Q_i  ) $ by minimizing the MSE over the set $\mathcal{U}^i_B$, that is, to solve the following problem:
\begin{equation*} 
\min_{ \substack{b \in \mathbb{R} \\\ q \in  \mathbb{R}^k }}  \left\{ \frac{1}{ \left|  \mathcal{U}^i_B  \right|  } \cdot \sum_{ v \in \mathcal{U}^i_B } \left(  r_{vi} - q^\top P_v- b - b_v - \mu \right)^2     
\right\}  .
\end{equation*}
%\begin{align*} 
%& ( \tilde{b}_i , \tilde{Q}_i )  = \arg\min_{(b,q) \in \mathbb{R}^{\ell+1}}  \Bigg\{ \sum_{u \in \mathcal{U}^i_B } \left(  r_{ui} - q^\top P_u- b - b_u - \mu \right)^2     \nonumber\\
%&  \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \quad  +  \lambda \left( \| q \|_2^2 + b^2 \right)\Bigg\}  ,
%\end{align*}
%$$ ( \tilde{b}_i , \tilde{Q}_i )  = \arg\min_{(b,q) \in \mathbb{R}^{\ell+1} } \Bigg\{ \sum_{u \in \mathcal{U}^i_B } \left(  r_{ui} - q^\top P_u- b - b_u - \mu \right)^2  + \lambda \left( \| q \|_2^2 + b^2 \right)\Bigg\}  , $$
%where $\lambda$ is a regularization parameter.
This minimization problem is in fact analytically solvable, and yields the following solution:
\begin{equation*} 
\big(  \tilde{b}_i , \tilde{Q}_i \big) 
= \left(  \sum_{ v \in \mathcal{U}^i_B } {P}^\prime_v {P}_v^{\prime \top} \right)^{-1} \left( \sum_{ v \in \mathcal{U}^i_B } (r_{vi} - b_v - \mu ) \cdot {P}_v^{\prime} \right)   ,
\end{equation*}
%\begin{align*} 
%& ( \tilde{b}_i , \tilde{Q}_i )  \nonumber\\
%& = \left( \sum_{u \in \mathcal{U}^i_B } (r_{ui} - b_u - \mu ) \cdot {P}_u^{\prime \top} \right) \left( \lambda \cdot I + \sum_{u \in \mathcal{U}^i_B } {P}^\prime_u {P}_u^{\prime \top} \right)^{-1}  ,
%\end{align*}
%$$ ( \tilde{b}_i , \tilde{Q}_i ) =  \left( \sum_{u \in \mathcal{U}^i_B } (r_{ui} - b_u - \mu ) \cdot {P}_u^{\prime \top} \right) \left( \lambda \cdot I + \sum_{u \in \mathcal{U}^i_B } {P}^\prime_u {P}_u^{\prime \top} \right)^{-1}  ,$$
where $   {P}^\prime_v $ is the concatenated column vector $  ( 1 ,  {P}_v ) $.


The above might  not be well-defined since $\sum_{ v \in \mathcal{U}^i_B } {P}^\prime_v {P}_v^{\prime \top}$ need not be invertible in general. In practice,  a regularization term of the form $\lambda \left( \| q \|_2^2 + b^2 \right)$ is usually added to the objective function to avoid this problem. The estimator $ ( \tilde{b}_i , \tilde{Q}_i  )$  then takes the following form:
 \begin{equation*} 
 \left( \lambda \cdot I + \sum_{v \in \mathcal{U}^i_B } {P}^\prime_v {P}_v^{\prime \top} \right)^{-1}   \left( \sum_{v \in \mathcal{U}^i_B} (r_{vi} - b_v - \mu ) \cdot {P}_v^{\prime} \right) .
\end{equation*}
In the sequel, we will assume that $\sum_{ v \in \mathcal{U}^i_B } {P}^\prime_v {P}_v^{\prime \top}$ is invertible to ease the readability of the paper. We emphasize that all the  results presented in this paper would still hold for the regularized estimator.

\subsection{The Optimal Design Approach}
We proceed to formally define necessary notations that will help us adapting the optimal design approach to our setting.
We somewhat abuse notations and denote by $ P $ the matrix whose columns correspond to the latent factor vectors $ P_u^\prime $ for $ u \in \mathcal{U}  $, and by ${P}_B$ the matrix whose columns correspond to the latent factor vectors $ P_v ^\prime$ for $ v \in \mathcal{U}^i_B  $.
  Similarly, we use the notations $\varepsilon_{\mathcal{U}} $ and $\varepsilon_B$ for vectors whose elements correspond to $ \varepsilon_{ui} $ for $ u \in \mathcal{U}$ and $ \varepsilon_{vi} $ for $ v \in \mathcal{U}_{B}^i $, respectively. Finally, we use $r_B$ to denote the vector whose elements correspond to $(r_{vi} - b_v - \mu)$ for $ v \in \mathcal{U}_{B}^i $.

%Optimal design or optimal experimental design [\textbf{comment:} we should decide on a story and stick to it. If we are using the use-case of users than we should stick to it and explain how we conduct our experiments (use the set of users that rate the item) in the evaluation section]   Intuitively, given the set of $B$ users who rated item $i$, the optimal design approach seeks to estimate the SSE on the set of the remaining users \textit{without} exposing their true ratings. 
%In order to do so, it relies on the assumption that the true ratings come from the following statistical model:
%
%Recall our modeling assumption regarding the generation of each rating $r_{ui}$:
%\begin{equation} \label{stat_model}
%r_{ui} =  \mu + b_u + b_i  +  Q_i^{ \top} P_u  + \varepsilon_{ui}.
%\end{equation}
%In particular, this assumption holds for $i \not\in \mathcal{I}$, yet $ b_i  $ and $ Q_i $ are unknown to us (due to the fact that item $i$ was not considered in our model), and thus needed to be estimated.
%The noise terms $\set{\varepsilon_{ui}} $ are  zero-mean random variables. 
%Recall that our goal is to construct estimates  $\tilde{b}_i  $ and $ \tilde{Q}_i $, and consequently predict 
%\begin{equation*}
%\tilde{r}_{ui} =  \mu + b_u + \tilde{b}_i  +  \tilde{Q}_i^{ \top} P_u  ,
%\end{equation*}
%for any $ u \in \mathcal{U}_i \setminus \mathcal{U}_B$. 
 We divide the analysis into two cases: (1) the noise terms $\set{\varepsilon_{ui}}$ are assumed to be zero-mean and i.i.d.; and (2) the noise terms $\set{\varepsilon_{ui}}$ are only assumed to be zero-mean and independent (but not necessarily identically distributed).
 
 


%
%we assume that the ratings of the new item by the users within $\mathcal{U}_B$ follow this model as well, when  $ \mu $ , $ b_u  $ and $  P_u  $ are as estimated by our model (Section \ref{pre}), whereas $ b_i  $ and $ Q_i $ are unknown to us (due to the fact that the new item was not considered in our model). The noise terms $\set{\varepsilon_{ui}} $ are assumed to be zero-mean random variables. Recall that our goal is to construct estimates  $\tilde{b}_i  $ and $ \tilde{Q}_i $, and consequently predict 
%\begin{equation*}
%\tilde{r}_{ui} =  \mu + b_u + \tilde{b}_i  +  \tilde{Q}_i^{ \top} P_u  ,
%\end{equation*}
%for any $ u \in \mathcal{U}_i \setminus \mathcal{U}_B$. Roughly speaking, the optimal design approach seeks to estimate the SSE for each selection of $\mathcal{U}_B$ without exposing the true ratings. We divide the analysis into two cases: (1) the noise terms $\set{\varepsilon_{ui}} $ are assumed to be i.i.d., and (2) the noise terms $\set{\varepsilon_{ui}} $ are only independent (and not necessarily identically distributed).
%
%Throughout this section we use the following notations: we denote by ${P}_B$ the matrix whose columns correspond to the latent factor vectors $ P_v ^\prime$ for $ v \in \mathcal{U}^i_B  $, and by $ P $ the matrix whose columns correspond to the latent factor vectors $ P_u^\prime $ for $ u \in \mathcal{U}  $.  Similarly, we use the notations $\varepsilon_B$ and $\varepsilon_{\mathcal{U}} $ for vectors whose elements correspond to $ \varepsilon_{vi} $ for $ v \in \mathcal{U}_{B}^i $ and $ u \in \mathcal{U}$, respectively. Finally, we use $r_B$ to denote the vector whose elements correspond to $r_{vi} - b_v - \mu$ for $ v \in \mathcal{U}_{B}^i $.

\subsubsection{Identically Distributed Noise Terms} \label{iid}
The following is our key observation: the optimization problem considered in Equation \eqref{prob_def} can be reduced to a simpler problem, if the noise terms are assumed to be i.i.d. and the least squares estimator is used for estimating  $ ( b_i , Q_i ) $. This observation is stated and proven below in Lemma \ref{TRACE}. 


Before we continue, we will assume without loss of generality that $ P P ^\top = \left| \mathcal{U} \right| \cdot I_{(k+1) \times (k+1)}$, meaning that the user vectors are in isotropic position. Otherwise , we can simply apply an invertible linear transformation to the LFM space of the users and its inverse to the space of the items; this does not affect our results as $(F ^\top x)^\top (F^{-1}y) =  x^\top y $ for all vectors $x,y$ and invertible linear transformation $F$. 
This assumption is here merely to simplify the statements and proof; the statements hold without it as well, and in particular, one is not required to compute the inverse of $P P ^\top$ when implementing the algorithm. 


 \begin{lemma} \label{TRACE}
Assume there exist $ b_i $ and  $  Q_i  $, such that for every $u \in \mathcal{U}$ it holds that  $r_{ui} =  \mu + b_u + b_i  +  Q_i^{ \top} P_u  + \varepsilon_{ui}$, where $ \mathbb{E} \left[ \varepsilon_{ui} \right] =0 $ and $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma^2 $. Then, the following is equivalent\footnote{The equivalence here between the two problems is in the following sense: the value of both objective functions is the same for any subset $ \mathcal{U}^i_{B}  \subset  \mathcal{U}^i$.}   to the problem presented in Equation \eqref{prob_def}:
$$
 \min_{ \mathcal{U}^i_{B} \subset  \mathcal{U}^i}  \left\{    \sigma^2  \cdot \text{Trace} \Big( \left( P_B P_B^{\top} \right)^{-1}  \Big) +\sigma^2   \right\},
 $$
 if the least squares estimator is considered.
 \end{lemma}

 
The expression in the lemma above  has the following interpretation: the additive $\sigma^2$ term is the inherent model error. I.e., this is the term that cannot be avoided as long as we assume a latent factor model of dimension $k$. The second term of $\sigma^2  \cdot \text{Trace} \big( \big( P_B P_B^{\top} \big)^{-1}  \big)$ represents the error originating from a sub-optimal choice of the item's parameters, i.e.,\ from the distance between $( \tilde{b}_i , \tilde{Q}_i  ) $ and $( b_i , Q_i ) $.  We turn now to prove the lemma.


\begin{proof}
Let $i$ be a new item, and $\mathcal{U}^i $ its corresponding set of available users. 
%Without loss of generality, we can assume that 
%$$ P P ^\top = \left| \mathcal{U} \right| \cdot I_{(k+1) \times (k+1)} \ ,$$
%that is, equal to the identity matrix, multiplied by the number of users. Otherwise, we can simply apply an invertible linear transformation to the LFM space of the users and its inverse to the space of the items; this does not affect our results as $(Fx)^\top (F^{-1}y) =  x^\top y $ for all vectors $x,y$ and invertible linear transformation $F$.
Now, given a set of $B$ users $ \mathcal{U}_{B}^i \subset  \mathcal{U}^i $, we can estimate $ ( b_i , Q_i ) $ using the least squares estimator:
\begin{align}   \label{analytic_solution}  
 \big( \tilde{b}_i , \tilde{Q}_i \big) 
& = \left(  \sum_{ v \in \mathcal{U}^i_B } {P}^\prime_v {P}_v^{\prime \top} \right)^{-1} \left( \sum_{ v \in \mathcal{U}^i_B } (r_{vi} - b_v - \mu ) \cdot {P}_v^{\prime} \right)   \nonumber\\
& =  \left( P_B P_B^{ \top} \right)^{-1}  P_B r_B .
\end{align}
%\begin{equation}  \label{analytic_solution}  
%( \tilde{b}_i , \tilde{Q}_i ) =  \left( \sum_{u \in \mathcal{U}_B } (r_{ui} - b_u - \mu ) \cdot {P}_u^{\prime \top} \right) \left( \sum_{u \in \mathcal{U}_B } {P}^\prime_u {P}_u^{\prime \top} \right)^{-1}  = r_B P_B^\top \left( P_B P_B^\top \right)^{-1}. 
%\end{equation}
Notice that according to Equation \eqref{eq:LFM_ground} we can also express the vector $r_B$ as follows:
$$ r_B  =   {P}_B^\top  \big( b_i , Q_i \big)   + \varepsilon_{B} ,$$
and by substituting the above in Equation \eqref{analytic_solution} and shifting sides we get that
\begin{equation} \label{dist}
  \big(  \tilde{b}_i , \tilde{Q}_i \big) -  \big( b_i , Q_i  \big)  =    \left( P_B P_B^{ \top} \right)^{-1} P_B   \varepsilon_B .
\end{equation}
%\begin{equation} \label{dist}
%( \tilde{b}_i , \tilde{Q}_i )  - ( {b}_i , {Q}_i )  =   \left( \sum_{u \in \mathcal{U}_B } \varepsilon_{ui}\cdot {P}^{\prime \top}_u \right)  \left( \sum_{u \in \mathcal{U}_B } {P}^\prime_u {P}_u^{\prime \top} \right)^{-1} . 
%\end{equation}
We denote by $\text{MSE} (  \mathcal{U}^i_B ) $  the resulted MSE value by using the ratings of the users within $  \mathcal{U}^i_B $ in our prediction model, that is, $ \text{MSE} \big(  \mathcal{U}^i_B \big) = \frac{1}{\left| \mathcal{U} \right|} \sum_{u \in  \mathcal{U}  } \left( \tilde{r}_{ui} - {r}_{ui} \right)^2 $.

Then, we can derive:
%
%\begin{align*} 
%\text{MSE} \big(  \mathcal{U}^i_B \big)  &   = \frac{1}{\left| \mathcal{U} \right|}  \sum_{u \in  \mathcal{U}  } \left( \tilde{r}_{ui} - {r}_{ui} \right)^2   \nonumber\\
%& = \frac{1}{\left| \mathcal{U} \right|}  \sum_{u \in  \mathcal{U}  } \left(  \tilde{Q}_i   ^\top P_u  + \tilde{b}_i + b_u + \mu - r_{ui}\right)^2 \nonumber\\
%& = \frac{1}{\left| \mathcal{U} \right|}   \sum_{u \in  \mathcal{U}  } \left( \left( ( \tilde{b}_i , \tilde{Q}_i )  - ( {b}_i , {Q}_i ^\top) \right)  P_u^\prime+ \varepsilon_{ui} \right)^2 \nonumber\\
%& = \frac{1}{\left| \mathcal{U} \right|}   \left\|  \left( ( \tilde{b}_i , \tilde{Q}_i )  - ( {b}_i , {Q}_i ^\top) \right)  P + \varepsilon_{\mathcal{U}}^\top \right\| _2^2 \nonumber\\
%& \stackrel{(1)}{=} \frac{1}{\left| \mathcal{U} \right|}  \left\| \varepsilon_B ^\top P_B^{ \top}   \left( P_B P_B^{ \top} \right)^{-1} P + \varepsilon_{\mathcal{U}}^\top \right\| _2^2 \nonumber\\
%&  \stackrel{(2)}{=} \frac{1}{\left| \mathcal{U} \right|}   \left\| \varepsilon_B ^\top P_B^{ \top}   \left( P_B P_B^{ \top} \right)^{-1}P  \right\| _2^2 + \frac{ \left\| \varepsilon_{\mathcal{U}} \right\| _2^2 }{ \left| \mathcal{U} \right| } ,
%\end{align*}
\begin{align*} 
\E \Big[ \text{MSE} \big(  \mathcal{U}^i_B \big) \Big]  &   = \frac{1}{\left| \mathcal{U} \right|} \E \left[ \sum_{u \in  \mathcal{U}  } \left( \tilde{r}_{ui} - {r}_{ui} \right)^2 \right]   \nonumber\\
& = \frac{1}{\left| \mathcal{U} \right|}  \E \left[  \left\| P^\top \left( ( \tilde{b}_i , \tilde{Q}_i)  - ( {b}_i , {Q}_i) \right)  + \varepsilon_{\mathcal{U}} \right\| _2^2 \right] \nonumber\\
& \stackrel{(1)}{=} \frac{1}{\left| \mathcal{U} \right|} \E \Bigg[  \left\|  P^\top  \left( P_B P_B^{ \top} \right)^{-1} P_B   \varepsilon_B  +  \varepsilon_{\mathcal{U}} \right\| _2^2 \Bigg] \nonumber\\
&  \stackrel{(2)}{=} \frac{1}{\left| \mathcal{U} \right|} \E \Bigg[  \left\| P^\top  \left( P_B P_B^{ \top} \right)^{-1} P_B   \varepsilon_B   \right\| _2^2 + \left\| \varepsilon_{\mathcal{U}} \right\| _2^2  \Bigg] ,
\end{align*}
where the expectation is taken over the noise $\eps_{vi}$ and $\eps_{ui}$. Equality (1) follows by substituting Equation \eqref{dist}; equality (2) holds since $ \mathbb{E} \left[ \varepsilon_{ui} \right] =0 $ for all $ u \in \mathcal{U} $, and also since $\varepsilon_B$ and $\varepsilon_\mathcal{U}$ are independent.




Next, we  use the assumption  $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma^2 $  to get:
\begin{align*} 
\mathbb{E} \left[ \text{MSE} \big(  \mathcal{U}^i_B \big) \right] &   =  \frac{1}{\left| \mathcal{U} \right|} \mathbb{E} \left[  \left\| P^\top  \left( P_B P_B^{ \top} \right)^{-1} P_B   \varepsilon_B  \right\| _2^2 \right]  +  \sigma^2 \nonumber\\
&  \stackrel{(3)}{=} \frac{1}{\left| \mathcal{U} \right|} \left\|    P^\top  \left( P_B P_B^{ \top} \right)^{-1} P_B C_B  \right\|_F^2 +\sigma^2 \nonumber\\
&  \stackrel{(4)}{=}  \sigma^2 \cdot \text{Trace} \left( \left( P_B P_B^{\top} \right)^{-1}  \right) +\sigma^2  ,
\end{align*}
where $ C_B $ denotes the square root of the covariance matrix of $ \varepsilon_{B} $; equality (3) follows from the definition of the Frobenius norm $ \| \cdot \|_F $, and equality (4) holds since $C_B = \sigma^2 \cdot I_{B \times B}$, and since we assume that $ P P ^\top = \left| \mathcal{U} \right| \cdot I_{(k+1) \times (k+1)} $. 

Thus, the lemma is obtained.
 \end{proof}
%


%
% Thus, our problem, as defined in Equation \eqref{prob_def}, can be rewritten as follows:
%\begin{equation*}\label{eq: SSE with expectation}
%\min_{\mathcal{U}^i_{B} \subset  \mathcal{U}_i }   \left\{ \frac{1}{\left| \mathcal{U} \right|} \cdot \mathbb{E} \left[  \left\| \varepsilon_B ^\top P_B   \left( P_B^{ \top} P_B \right)^{-1} P + \varepsilon_{\mathcal{U}} \right\| _2^2 \right] \right\} .
%\end{equation*}
%Next, we use the facts that $ \mathbb{E} \left[ \varepsilon_{ui} \right] =0 $ and $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma^2 $ for all $ u \in \mathcal{U} $ to derive:
%\begin{align*} 
%& \frac{1}{\left| \mathcal{U} \right|} \cdot \mathbb{E} \left[  \left\| \varepsilon_B ^\top P_B   \left( P_B^{ \top} P_B \right)^{-1} P + \varepsilon_{\mathcal{U}} \right\| _2^2 \right]
%   \nonumber\\
%&  = \frac{1}{\left| \mathcal{U} \right|} \cdot \mathbb{E} \left[  \left\| \varepsilon_B ^\top P_B   \left( P_B^{ \top} P_B \right)^{-1} P  \right\| _2^2 \right]  + \frac{1}{\left| \mathcal{U} \right|} \cdot \mathbb{E} \left[ \left\| \varepsilon_{\mathcal{U}} \right\| _2^2 \right]
%\nonumber\\
%& = \frac{1}{\left| \mathcal{U} \right|} \cdot  \sum_{u \in  \mathcal{U}  } \left( \left( ( \tilde{b}_i , \tilde{Q}_i )  - ( {b}_i , {Q}_i ^\top) \right)  P_u^\prime+ \varepsilon_{ui} \right)^2 \nonumber\\
%& = \frac{1}{\left| \mathcal{U} \right|} \cdot \left\| \varepsilon_B ^\top P_B   \left( P_B^{ \top} P_B \right)^{-1} P + \varepsilon_{\mathcal{U}} \right\| _2^2,
%\end{align*}
%
%
%
%
%
%$$
%\text{SSE} ( \tilde{b}_i , \tilde{Q}_i ) =  \sum_{u \in  \mathcal{U}_i \setminus  \mathcal{U}_{B} } \left(  \tilde{r}_{ui} - r_{ui} \right)^2 = \sum_{u \in  \mathcal{U}_i \setminus  \mathcal{U}_{B} } \left(  \tilde{Q}_i   ^\top P_u  + \tilde{b}_i + b_u + \mu - r_{ui}\right)^2  .
%$$
%Notice that the above can also be written as follows:
%$$
%\text{SSE} ( \tilde{b}_i , \tilde{Q}_i )  =  \sum_{u \in  \mathcal{U}_i \setminus  \mathcal{U}_{B} } \left( \left( ( \tilde{b}_i , \tilde{Q}_i )  - ( {b}_i , {Q}_i ) \right) ^\top P_u^\prime+ \varepsilon_{ui} \right)^2 ,
%$$
%and by substituting Equation \eqref{dist} we get that
%$$
%\text{SSE} ( \tilde{b}_i , \tilde{Q}_i )   =  \sum_{u \in  \mathcal{U}_i \setminus  \mathcal{U}_{B} } \left( \left( \sum_{v \in U_{B_i}} \varepsilon_{vi} {P}_v^{\prime \top} \right) \left( \sum_{v \in U_{B_i}} {P}_v^\prime {P}_v^{\prime \top} \right)^{-1}  {P}_u ^{\prime} + \varepsilon_{ui} \right)^2 .
%$$
%$$
%\text{SSE} ( \tilde{b}_i , \tilde{Q}_i )   = \left\|  \varepsilon_B P_B^{\prime \top} \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1} P_{B^c}^\prime + \varepsilon_{B^c} \right\| _2^2.
%$$
% Thus, our problem, as defined in Equation \eqref{prob_def}, can be rewritten as follows:
%\zk{the transition from the equation above to the one below is not clear. I recommend jumping to equation (7) via a lemma in the appendix. That is, state that ${\cal U}_B$ minimizing SSE is the same one minimizing the expression in equation (7). The transitions leading there are purely technical, and do not have to be in the main body.}
%\begin{equation*}\label{eq: SSE with expectation}
%\min_{\mathcal{U}^i_{B} \subset  \mathcal{U}_i }   \left\{  \mathbb{E} \left[ \left\|  \varepsilon_B ^\top P_B   \left( P_B^{ \top} P_B \right)^{-1} P   \right\| _2^2 \right] \right\} .
%\end{equation*}
%$$
% \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i}   \mathbb{E} \left[ \sum_{u \in \mathcal{U}_i \setminus \mathcal{U}_{B} } \left( \left( \sum_{v \in \mathcal{U}_{B}} \varepsilon_{vi} {P}_v^{\prime \top} \right) \left( \sum_{v \in \mathcal{U}_{B} } {P}_v^\prime {P}_v^{\prime \top} \right)^{-1}  {P}_u ^{\prime} \right)^2 \right] .
%$$
%Note that the additive $ \varepsilon_{ui} $ is omitted from the objective function  due to the facts that we are performing a least squares minimization, and the noise terms are assumed to be zero-mean. 
%%[\textbf{comment:} maybe you should elaborate some more mentioning the fact that the noises assumed to haze zero mean]
%%The root square and the average do not affect the solution and hence can be omitted here. The expectation is needed since the noise terms are unknown to us at any stage of the optimization. 
%The following lemma shows that it is equivalent to consider an objective function that estimates the SSE over the entire set $\mathcal{U}_i$, instead of only over $ \mathcal{U}_i \setminus \mathcal{U}_B$. 
%%[\textbf{comment:} I guess the Lemma is true only if we assume the noises to have the same variences]
%\begin{lemma} \label{FIRST}
%Denote by $P_{\mathcal{U}_i}^\prime$ the matrix whose columns correspond to the latent factor vectors $P_u^\prime$ for $ u \in \mathcal{U}_i $. Then, the following holds
%%$$
%% \mathbb{E} \left[ \left\|  \varepsilon_B P_B^\top \left( P_B P_B^\top \right)^{-1} P_{\mathcal{U}_i} \right\| _2^2 - 
%% \left\|  \varepsilon_B P_B^\top \left( P_B P_B^\top \right)^{-1} P_{B^c} \right\| _2^2 \right] = B  \sigma^2.
%%$$
%\begin{align*} 
%&  \mathbb{E} \left[ \left\|  \varepsilon_B  P_B^{\prime \top} \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1} P_{\mathcal{U}_i}^\prime \right\| _2^2 \right]    \nonumber\\
%& = \mathbb{E} \left[ \left\|  \varepsilon_B P_B^{\prime \top} \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1} P_{B^c}^\prime \right\| _2^2 \right] + B  \sigma^2.
%\end{align*}
%\end{lemma}
%We defer the proof to the appendix, and continue with the analysis.
%Thus, from Lemma \ref{FIRST} it follows that we can equivalently consider the following minimization problem:
%\begin{align*} 
% \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i} &  \left\{  \mathbb{E} \left[ \left\|  \varepsilon_B  P_B^{\prime \top} \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1} P_{\mathcal{U}_i}^\prime \right\| _2^2 \right]  \right\} \nonumber\\
%& =  \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i}  \left\{  \left\|  C_B  P_B^{\prime \top} \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1} P_{\mathcal{U}_i}^\prime  \right\|_F^2 \right\} .
%\end{align*}
%when $ \| \cdot \|_F $ refers to the Frobenius norm and $ C_B $ is the square root of the covariance matrix of $ \varepsilon_{ui} $ for $ u \in \mathcal{U}_{B} $.
%Now, since we assume $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma^2 $ for all $u$, and $\sum_{u \in \mathcal{U}_B } {P}^\prime_u {P}_u^{\prime \top} \propto I_{d \times d} $, it is equivalent to consider the following problem:
%%\begin{align*} 
%%&   \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i}  \left\| P_B^{\prime \top} \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1} P_{\mathcal{U}_i}^\prime  \right\|_F^2   \nonumber\\
%%& = \text{Trace} \left( \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1}  P_{\mathcal{U}_i}^\prime P_{\mathcal{U}_i}^{\prime \top} \right) .
%%\end{align*}
%\begin{equation}  \label{object}
% \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i} \left\{ \text{Trace} \left( \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1}  \right) \right\} ,
%\end{equation}
%
%\begin{align}  \label{object}
% \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i} & \text{Trace} \left( \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1}  P_{\mathcal{U}_i}^\prime P_{\mathcal{U}_i}^{\prime \top} \right)  \nonumber\\
%& =  \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i} \text{Trace} \left( \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1}  \right) .
%\end{align}
%
%\begin{equation} \label{object}
% \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i}  \left\| P_B ^ \top \left( P_B P_B^\top \right)^{-1} P_{\mathcal{U}_i}^\prime  \right\|_F^2 =   \text{Tr} \left( \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1}  P_{\mathcal{U}_i}^\prime P_{\mathcal{U}_i}^{\prime \top} \right) .
%\end{equation}
%
%The expression in the above lemma has the following interpretation: The additive $\sigma^2$ term is the inherent model error. That is, this is the term that cannot be avoided as long as we assume a latent factor model of dimension $k$. The second term of $\sigma^2  \cdot \text{Trace} \Big( \left( P_B P_B^{\top} \right)^{-1}  \Big)$ represents the error originating from a sub-optimal choice of the item's parameters, i.e.\ from the distance between $( \tilde{b}_i , \tilde{Q}_i  ) $ and $( b_i , Q_i^\top ) $. This second term typically decays linearly with $1/B$. In particular for sufficiently large values of $B$, such as the entire pool of users $|{\cal V}^i|$, it can be thought of as zero.

After establishing a new (and equivalent) optimization problem, we turn now to present a simple greedy algorithm for finding an approximation to its optimum. Here, $P_{B \setminus v_j} $ refers to the matrix $P_B$, where the column that  corresponds to the user ${v_j}$ is removed.

\vspace{\parSpace}


\begin{algorithm}[h!]
\caption{Backward Greedy Selection (BGS1)}
\label{alg2}
\begin{algorithmic}[1]
\STATE Input: users set $\mathcal{U}^i$, and corresponding matrix $P_{\mathcal{U}^i}$.
\STATE Output: users subset ${\mathcal{U}_B^{ALG}}$.
\STATE Initialize $P_{B}=P_{\mathcal{U}^i}$ and $\mathcal{U}_B^{ALG} =\mathcal{U}^i$.
\FOR {$j=1$ to $ | \mathcal{U}^i | - B$}
\STATE 
%\begin{multline}
$v_j \leftarrow \arg\min_{v \in \mathcal{U}_B^{ALG} } \left\{  \text{Trace} \left( \left( P_{B \setminus v}  P_{B \setminus v} ^{ \top} \right)^{-1}   \right)  \right\} 
$%\end{multline}
\STATE Update $P_{B} \leftarrow P_{B \setminus v_j} $.
\STATE Update $\mathcal{U}_B^{ALG} \leftarrow \mathcal{U}_B^{ALG} \setminus v_j $.
\ENDFOR
\end{algorithmic}
\end{algorithm}

\vspace{\parSpace}


Before stating our main theorem, we introduce some necessary definitions:
\begin{defn}
let $f:\mathbb{R}_{+} \to \mathbb{R}$. For a positive definite matrix $A \in R^{k \times k}$ with the decomposition
$ A = U^\top \text{Diag}(\lambda_1,\ldots,\lambda_k) U $,
we extend the definition of  $f$ as follows:
$$ f(A) = U^\top \text{Diag}(f(\lambda_1),\ldots,f(\lambda_k)) U .$$
\end{defn}
\begin{defn}
We say that $f$ is \emph{operator monotone} if for any positive definite matrices $A$ and $B$:
$$  
A \preceq B \Rightarrow f(A) \preceq f (B) .
$$
\end{defn}
\begin{defn}
We say that $f$ is \emph{operator antitone} if $-f$ is operator monotone.
\end{defn}
\begin{defn}
We say that $f:2^{E} \rightarrow \mathbb{R} $ is \emph{supermodular} if 
$$ f(A \cup \left\{x\right\} ) - f(A) \geq  f(B \cup \left\{x\right\} ) - f(B) ,$$
for any $A \subset B \subset E$ and $x \in E \setminus B$.
\end{defn}
\begin{defn}
The steepness of a decreasing supermodular function $f$ is denoted by $s$ and defined as follows: 
$$
s= \max_{x \in E} \frac{  \left[  f(\phi)-f(x) \right] -  \left[ f(E \setminus \left\{x\right\} ) - f(E) \right]  }{  \left[  f(\phi)-f(x) \right]  } .
$$
\end{defn}
In the last definition, if $ f(\phi)$ is not defined we can simply extend it as follows:
\begin{equation} \label{extension}
 f(\phi) = \max_{ \substack{A,B \subset E \\\ A \cap B = \phi }}  \left\{ f(A) + f(B)  -  f(A \cup B)  \right\} 
\end{equation}


%After establishing the above definitions, we can state the following proposition:
%
%\begin{prop}
%Let  $\mathcal{U}_D^i  \subset  \mathcal{U}^i $, and $P_D$ be the matrix whose columns correspond to $P_v^{\prime}$ for $v \in \mathcal{U}_D^i $. Then, for $f:\R_{+} \to \R$ such that $f^\prime$ is operator monotone, it holds that 
%$$ \Phi ( \mathcal{U}_D^i  ) = \text{Trace} \left( f \big( P_D P_D^\top \big) \right) $$
%is supermodular.
%\end{prop}
%
%In our case $f(x) = \frac{1}{x}$, and its derivative  $f^\prime (x) = - \frac{1}{x^2}$ is operator monotone, which implies that $ \Phi$ is supermodular.
%The proof resembles the proof of Corollary 2.4 of  \cite{sagnol2013approximation}, albeit plugging operator monotone derivative instead of operator antitone one.


%Before stating our main theorem, we introduce the following important proposition:
%\begin{prop}
%Denote by $\text{MSE} (  \mathcal{U}^i ) $ the resulted MSE value of using the ratings of all users for our prediction model. Then, it holds that:
%$$
%\text{MSE} (  \mathcal{U}^i ) = \sigma^2 + O\left( \frac{k}{ \left| \mathcal{U}^i \right|  } \right) .
%$$ 
%\end{prop}
%Intuitively, this assumption states that by querying $n$ users regarding their preference of item $i$, our prediction error converges to the squared error of the model $\sigma^2$. The convergence rate then behaves like $\frac{1}{n}$.

The following is our main theorem:

\vspace{\parSpace}

\begin{theorem} \label{GREEDY}
Let $i$ be a new item, and $\mathcal{U}^i $ its corresponding set of available users, and assume that  $ \mathbb{E} \left[ \varepsilon_{ui} \right] =0 $ and $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma^2 $ for all $u \in \mathcal{U}$. Then, Algorithm \ref{alg2} generates a subset $\mathcal{U}^{ALG}_B \subset  \mathcal{U}^i$ for which:
\begin{equation*} \label{approx}
\E \left[ \text{MSE} \big(  \mathcal{U}^{ALG}_B \big) \right] \leq   \sigma^2 + \frac{ e^t - 1  }{t} \cdot \left( \E \left[  \text{MSE} \big(  \mathcal{U}^{*}_B \big) \right] - \sigma^2 \right)   .
\end{equation*}
where $t=\frac{s}{1-s}$ and ${\cal U}_B^*$ is the optimal subset of $B$ users, minimizing the expected MSE.
\end{theorem}

\vspace{\parSpace}


The above statement can be interpreted as follows. Both Algorithm \ref{alg2} and the optimal solution have an additive term of $\sigma^2$, corresponding to the inherent LFM error. The additional term, corresponding to the sub-optimality of the choice of $( \tilde{b}_i , \tilde{Q}_i  ) $, is multiplicatively approximated by a factor of $(e^t-1)/t$ compared to the optimal selection. Notice that the stated guarantee strictly dominates the following one: 
$$\E \left[ \text{MSE} \big(  \mathcal{U}^{ALG}_B \big) \right] \leq  \frac{ e^t - 1  }{t} \cdot \E \left[  \text{MSE} \big(  \mathcal{U}^{*}_B \big) \right] ,$$
since $\sigma^2 >0$ (trivially holds). We shall proceed to prove the main theorem.

\vspace{\parSpace}

\begin{proof}
We first define an auxiliary function $\Phi : 2 ^{\mathcal{U}^i } \rightarrow \mathbb{R}$ as follows:
$$ \Phi ( \mathcal{U}^i_{D} ) = \text{Trace} \left(\left( P_D P_D^{ \top} \right)^{-1}  \right) - \varphi_i ,$$ where $\varphi_i =  \text{Trace} \big(\left( P_{\mathcal{U}^i} P_{\mathcal{U}^i}^{ \top} \right)^{-1}  \big)$, and  $ \Phi ( \varnothing )$ is defined as in Equation~\eqref{extension}. 
Notice that $\Phi$ is well-defined for any subset $\mathcal{U}_D^i \subset \mathcal{U}^i$ (of size $0\leq D \leq  \left| \mathcal{U}^i \right| $), and not only for subsets of size $B$. The matrix ${P}_D$ is then defined as the matrix whose columns correspond to the latent factor vectors $ P_v ^\prime$ for $ v \in \mathcal{U}^i_D  $.

\vspace{\parSpace}

Next, we show that $ \Phi $ has the following three properties: it is supermodular, monotonically  decreasing, and equal to 0 at $ \mathcal{U}^i $. 
For such functions, \cite{Ilev01} proved that the backward greedy algorithm, eliminating elements one by one, attains an $\big( \frac{ e^t - 1  }{t} \big)$-approximation to the optimum. 
The third property follows immediately from the definitions of $\Phi$ and $\varphi_i$, and thus we are left to prove the other two properties.

\vspace{\parSpace}

Before proving these properties, we provide a simple intuition. 
Notice first that $ \E \left[ \text{MSE} (\mathcal{U}_D^i ) \right] $ can be written as a linear function of $\Phi (\mathcal{U}_D^i )$:
$$ \E \left[ \text{MSE} (\mathcal{U}_D^i ) \right] = \sigma^2  \cdot \left( \Phi (\mathcal{U}_D^i ) + \varphi_i + 1 \right).$$
Thus, minimizing $\Phi$ is equivalent to minimizing the MSE. Now, the monotonicity of $\Phi$ gives rise to the following insight: the MSE decreases as the number of users increases. The supermodularity then translates into the following rational: the marginal return of a user diminishes as the set of selected users expands. 

\vspace{\parSpace}


We shall proceed to formally prove these properties.
For the monotonicity, we take two subsets $\mathcal{U}_D^i , \mathcal{U}_E^i \subset \mathcal{U}^i$, such that $\mathcal{U}_D^i \subset \mathcal{U}_E^i $, and prove that $ \Phi ( \mathcal{U}_D^i ) \geq \Phi ( \mathcal{U}_E^i )$.  Thus, denote by $P_D$ and $P_E$ the matrices that correspond to $\mathcal{U}_D^i$ and $\mathcal{U}_E^i$, respectively. Then, it holds that $ P_E P_E^\top \succeq P_D P_D^\top$, which also implies that 
$$ \left( P_E P_E^\top \right)^ {-1} \preceq \left( P_D P_D^\top \right)^ {-1} .$$
Now, since the trace of a positive semidefinite (PSD) matrix is the sum of its eigenvalues, the above also implies that 
$$ \text{Trace} \left( \left( P_E P_E^\top \right)^ {-1} \right) \leq \text{Trace} \left( \left( P_D P_D^\top \right)^ {-1} \right) ,$$
which proves that $\Phi$ is monotonically decreasing.

\vspace{\parSpace}


%For the supermodularity, we use recent techniques presented in \cite{friedland2010submodular}.  Thus, from 
%Theorem 1 of \cite{friedland2010submodular} we know that if we can represent 
%%These techniques imply that if we can write 
%$$ \Phi ( \mathcal{U}_D^i  ) = \text{Trace} \left( f \big( P_D P_D^\top \big) \right) ,$$
%where $f$ is the primitive  of a function that is operator monotone, then $\Phi$ is supermodular.  We note that $f: \mathbb{R} \rightarrow \mathbb{R}$, yet for a positive semidefinite (PSD) matrix $A$, $f(A)$ is defined as $ \sum_{j=1} ^m f( \lambda_j ) $, where $\lambda_1,\ldots,\lambda_m$ are the eigenvalues of $A$.
%In our case $f(x) = x^{-1}$, which is the primitive function of the operator monotone function $ - x ^{-2}$.  This proves that $\Phi$ is supermodular.

%We defer the formal definitions and the statement of  Theorem 1 of \cite{friedland2010submodular} to the appendix. 
For the supermodularity, we use recent techniques presented in \cite{sagnol2013approximation}, and specifically the following proposition:
% We defer the formal definitions and the statement of the main result we use from \cite{sagnol2013approximation} to  Appendix \ref{super}. 
\begin{prop} 
Let  $\mathcal{U}_D^i  \subset  \mathcal{U}^i $, and $P_D$ be the matrix whose columns correspond to $P_v^{\prime}$ for $v \in \mathcal{U}_D^i $. Then, for $f:\mathbb{R}_{+} \to \mathbb{R}$ such that $f^\prime$ is operator monotone, it holds that 
$$ \Phi ( \mathcal{U}_D^i  ) = \text{Trace} \left( f \big( P_D P_D^\top \big) \right) $$
is supermodular.
\end{prop}

\vspace{\parSpace}

In our case $f(x) = \frac{1}{x}$, and its derivative  $f^\prime (x) = - \frac{1}{x^2}$ is operator monotone, which implies that $ \Phi$ is supermodular.
The proof resembles the proof of Corollary 2.4 of  \cite{sagnol2013approximation}, albeit plugging operator monotone derivative instead of operator antitone one.


\vspace{\parSpace}



Finally, as mentioned before, these three properties yield an $\big( \frac{ e^t - 1  }{t} \big)$-approximation to the problem of minimizing $\Phi$. That is, Algorithm \ref{alg2} generates a subset $ \mathcal{U}_{B} ^{ALG}$ for which:
\begin{align*}
 \Phi \big( \mathcal{U}_{B} ^{ALG} \big) & \leq \left( \frac{ e^t - 1  }{t} \right)  \min_{ \mathcal{U}^i_{B} \subset  \mathcal{U}^i}   \Phi \big( \mathcal{U}_{B} ^{i} \big)  \\
 & =   \left( \frac{ e^t - 1  }{t} \right)  \min_{ \mathcal{U}^i_{B} \subset  \mathcal{U}^i} \left\{ \frac{ \E \left[ \text{MSE} (\mathcal{U}_B^{i}) \right] }{ \sigma^2 } - 1 - \varphi_i  \right\}  \\
 & \leq  \left( \frac{ e^t - 1  }{t} \right)   \min_{ \mathcal{U}^i_{B} \subset  \mathcal{U}^i} \left\{ \frac{ \E \left[ \text{MSE} (\mathcal{U}_B^{i}) \right] }{ \sigma^2 } -1 \right\}  - \varphi_i   \\
 & =   \left( \frac{ e^t - 1  }{t} \right)  \cdot \left( \frac{ \E \left[ \text{MSE} (\mathcal{U}_B^{*}) \right] }{ \sigma^2 } - 1 \right) - \varphi_i   .
\end{align*}
By substituting $\Phi (\mathcal{U}_B^{ALG} )  = \frac{ \E \left[ \text{MSE} (\mathcal{U}_B^{ALG}) \right] }{ \sigma^2 } - \varphi_i - 1 $ in the inequality above,
 we get the stated result.
%it holds that: $ \Phi ( \mathcal{U}^i_{B} ) = 0$
%
%We then show that  follows immediately by noticing that the function $ \Phi ( \mathcal{U}_{B} ) = \text{Trace} \big( \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1}  \big) $ is supermodular and monotone decreasing. This result is stated in Lemma \ref{supermodular}, and proven in the appendix. For such functions, it is well-known [???] that the greedy procedure obtains the stated approximation.
%\begin{lemma} \label{supermodular}
%Let $i$ be a new item, and $\mathcal{U}_i $ its corresponding set of available users for review, Then, the function $\Phi : 2 ^{\mathcal{U}_i } \rightarrow \mathbb{R}$, which is defined as follows:
%$$ \Phi ( \mathcal{U}_{B} ) = \text{Trace} \left( \left( P_B^{\prime} P_B^{\prime \top} \right)^{-1}  \right) , $$
%is supermodular and monotone decreasing.
%\end{lemma}
\end{proof}


%The objective function can be shown to be supermodular and monotone (see [???] for instance), and thus can be optimized efficiently via the greedy procedure presented below. 
%
%It can be shown that the greedy procedure yields an $\big( \frac{e}{e-1} \big)$-approximation to the optimum.
%
%\zk{This section should be renamed to something in the spirit of `label independent formulation in iid noise'. The conclusion should be equation (7). In another section we should prove that the new formulation is sub modular and that this means that a greedy approach gives an approximation}
%
\subsubsection{Non-Identically Distributed Noise Terms} \label{niid}
The analysis in Section \ref{iid}  relies heavily on the assumption that $\set{\varepsilon_{ui}}$ are identically distributed. However,  it is sometimes reasonable to assume that each user has a different noise distribution with respect to the employed model. In such cases, the identical distribution assumption only weakens our model. In this section we extend our analysis to the case where each of the users has a different  (yet  known in advance) noise distribution. 
%Note that in our setting the variance of the noise associated with each user is not known, but can be estimated based on past ratings.


Thus, let $i$ be a new item, and $ \mathcal{U}_{B}^i \subset  \mathcal{U}^i $ a subset of users assigned for the task of rating it.
We start by introducing a new estimator for $ (b_i , Q_i ) $, which generalizes the least squares estimator:
$$ \big( \tilde{b}_i , \tilde{Q}_i  \big)  
 = \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  r_B  , $$
where again, $ C_B $ is the square root of the covariance matrix that corresponds to $ \varepsilon_{vi} $ for $ v \in \mathcal{U}^i_{B} $. Intuitively, this estimator is a least squares estimator that considers variance-scaled users. In the sequel, we refer to this estimator as \emph{generalized least squares estimator}. The following lemma states that this is indeed an unbiased estimator for $ (b_i , Q_i ) $. 
\begin{lemma} \label{SECOND}
Assume there exist $ b_i $ and  $  Q_i  $, such that for every $u \in \mathcal{U} $ it holds that  $r_{ui} =  \mu + b_u + b_i  +  Q_i^{ \top} P_u  + \varepsilon_{ui}$, where $ \mathbb{E} \left[ \varepsilon_{ui} \right] =0 $ and $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma_u^2 $. Then,
\begin{equation} \label{generalized}
 \big( \tilde{b}_i , \tilde{Q}_i  \big)  
 = \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  r_B  
 \end{equation}
is an unbiased estimator for $ (b_i , Q_i ^\top)$. 
\end{lemma}
\begin{proof}
By taking expectation we have that:
\begin{align*}
\mathbb{E} \left[  \big( \tilde{b}_i , \tilde{Q}_i \big)   \right] &= \mathbb{E} \left[ \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  r_B  \right] \\
& = \mathbb{E} \left[  \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2} {P}_B^\top  \big( b_i , Q_i \big)   \right] \\
& \quad + \mathbb{E} \left[ \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  \varepsilon_{B} \right] \\
& =   \big( {b}_i , {Q}_i \big)  +  \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  \mathbb{E} \big[ \varepsilon_B \big]   \\
& =  \big( {b}_i , {Q}_i \big) ,
\end{align*}
where in the second equality  we used the assumption that $r_B  =   {P}_B^\top  \big( b_i , Q_i \big)   + \varepsilon_{B}$.
\end{proof}
%The proof is technical and appears in Appendix \ref{TRACE2}. 
We proceed to state and prove the lemma that encapsulates our parallel key observation for the case of non-identically distributed noise terms.
\vspace{\parSpace}
 \begin{lemma} \label{trace2}
Assume there exist $ b_i $ and  $  Q_i  $, such that for every $u \in \mathcal{U}$ it holds that  $r_{ui} =  \mu + b_u + b_i  +  Q_i^{ \top} P_u  + \varepsilon_{ui}$, where $ \mathbb{E} \left[ \varepsilon_{ui} \right] =0 $ and $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma_u^2 $. Then, the following is equivalent  to the problem presented in Equation \eqref{prob_def}:
$$
 \min_{ \mathcal{U}^i_{B} \subset  \mathcal{U}^i}  \left\{  \text{Trace} \left( \left( P_B C_B^{-2} P_B^{\top} \right)^{-1}  \right) +  \frac{1 }{ \left| \mathcal{U} \right| }  \sum_{u \in \mathcal{U} } \sigma_u^2 \right\},
 $$
 if the generalized least squares estimator is considered.
 \end{lemma}


\begin{proof}
Recall that as before we assume that
$$ P P ^\top = \left| \mathcal{U} \right| \cdot I_{(k+1) \times (k+1)} \ .$$
Now, let $i$ be a new item, and $ \mathcal{U}_{B}^i \subset  \mathcal{U}^i $ a subset of users assigned for the task of rating it.
Then, we can  substitute $r_B$ in the generalized least squares estimator (Equation \eqref{generalized}) to get the following result:
$$
\big( \tilde{b}_i , \tilde{Q}_i   \big)  - \big( {b}_i , {Q}_i   \big)  =  \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  \varepsilon_{B}  .
$$
We substitute the above in the MSE equation, and rewrite our motivation problem:
\begin{align*} 
& \E \left[ \text{MSE} \big(  \mathcal{U}^i_B \big) \right] \\
&   = \frac{1}{\left| \mathcal{U} \right|} \E \left[  \sum_{u \in  \mathcal{U}  } \left( \tilde{r}_{ui} - {r}_{ui} \right)^2 \right]  \nonumber\\
& = \frac{1}{\left| \mathcal{U} \right|}  \E \left[  \left\|  P^\top \left( ( \tilde{b}_i , \tilde{Q}_i)  - ( {b}_i , {Q}_i) \right)  + \varepsilon_{\mathcal{U}} \right\| _2^2  \right] \nonumber\\
& = \frac{1}{\left| \mathcal{U} \right|} \E \left[  \left\| P^\top  \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  \varepsilon_{B}  + \varepsilon_{\mathcal{U}} \right\| _2^2\right]   \nonumber\\
& = \frac{1}{\left| \mathcal{U} \right|} \E \left[   \left\|   P^\top  \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  \varepsilon_{B}   \right\| _2^2 \right] +  \frac{  \E \left[  \left\| \varepsilon_{\mathcal{U}} \right\| _2^2  \right]  }{ \left| \mathcal{U} \right| } \\
%.
%\end{align*}
%Next, we use the assumption  $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma_u^2 $  to get:
%\begin{align*} 
%& \mathbb{E} \left[ \text{MSE} \big(  \mathcal{U}^i_B \big) \right]  \nonumber\\
&= \frac{ 1 }{\left| \mathcal{U} \right|}  \mathbb{E} \left[ \left\|   P^\top  \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-2}  \varepsilon_{B}   \right\| _2^2 \right] + \frac{1 }{ \left| \mathcal{U} \right| }  \sum_{u \in \mathcal{U} } \sigma_u^2 
 \nonumber\\
& = \frac{1}{\left| \mathcal{U} \right|}  \left\| P^\top  \left( P_B C_B^{-2} P_B^{ \top} \right)^{-1}  P_B C_B^{-1}     \right\|_F^2 +  \frac{1 }{ \left| \mathcal{U} \right| }  \sum_{u \in \mathcal{U} } \sigma_u^2  \nonumber\\
&  =  \text{Trace} \left( \left( P_B C_B^{-2} P_B^{\top} \right)^{-1}  \right) +  \frac{1 }{ \left| \mathcal{U} \right| }  \sum_{u \in \mathcal{U} } \sigma_u^2   ,
\end{align*}
where the equalities follow similarly to Lemma \ref{TRACE}.
\end{proof}

%& = \frac{1}{\left| \mathcal{U} \right|}  \E \left[  \left\| P^\top \left( ( \tilde{b}_i , \tilde{Q}_i)  - ( {b}_i , {Q}_i) \right)  + \varepsilon_{\mathcal{U}} \right\| _2^2 \right] \nonumber\\
%& \stackrel{(1)}{=} \frac{1}{\left| \mathcal{U} \right|} \E \Bigg[  \left\|  P^\top  \left( P_B P_B^{ \top} \right)^{-1} P_B   \varepsilon_B  +  \varepsilon_{\mathcal{U}} \right\| _2^2 \Bigg] \nonumber\\
%&  \stackrel{(2)}{=} \frac{1}{\left| \mathcal{U} \right|} \E \Bigg[  \left\| P^\top  \left( P_B P_B^{ \top} \right)^{-1} P_B   \varepsilon_B   \right\| _2^2 + \left\| \varepsilon_{\mathcal{U}} \right\| _2^2  \Bigg] ,

\vspace{\parSpace}


After establishing here also an equivalent optimization problem, we turn to present a simple adaptation of Algorithm \ref{alg2} to this problem. Here, the notation
$ C_{\mathcal{U}^i} $ refers to the square root of the covariance matrix of all available users, and the notations $P_{B \setminus v_j} $ and $C_{B \setminus v_j} $ are as defined in   Section \ref{iid}.

\vspace{\parSpace}


\begin{algorithm}[h!]
\caption{Backward Greedy Selection (BGS2)}
\label{alg3}
\begin{algorithmic}[1]
\STATE Input: users set $\mathcal{U}^i$, and corresponding matrix $P_{\mathcal{U}^i}$.
\STATE Output: users subset ${\mathcal{U}_B^{ALG}}$.
\STATE Initialize $P_{B}=P_{\mathcal{U}^i}$, $C_{B}=C_{\mathcal{U}^i}$, and $\mathcal{U}_B^{ALG} =\mathcal{U}^i$.
\FOR {$j=1$ to $ | \mathcal{U}^i | - B$}
\STATE 
%\begin{multline}
$v_j \leftarrow \arg\min_{v \in \mathcal{U}_B^{ALG} } \Big\{  \text{Trace} \Big( \left( P_{B \setminus v} C_{B \setminus v}^{-2} P_{B \setminus v} ^{ \top} \right)^{-1}   \Big)  \Big\} 
$%\end{multline}
\STATE Update $P_{B} \leftarrow P_{B \setminus v_j} $ and $C_{B} \leftarrow C_{B \setminus v_j} $. 
\STATE Update $\mathcal{U}_B^{ALG} \leftarrow \mathcal{U}_B^{ALG} \setminus v_j $.
\ENDFOR
\end{algorithmic}
\end{algorithm}

For Algorithm \ref{alg3} we can prove the following:
\begin{theorem} \label{greedy2}
Let $i$ be a new item, and $\mathcal{U}^i $ its corresponding set of available users, and assume that  $ \mathbb{E} \left[ \varepsilon_{ui} \right] =0 $ and $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma_u^2 $ for all $u \in \mathcal{U}$. Then, Algorithm \ref{alg3} generates a subset $\mathcal{U}^{ALG}_B \subset  \mathcal{U}^i$, for which the following holds:
\begin{align*} \label{approx}
\E \left[ \text{MSE} \big(  \mathcal{U}^{ALG}_B \big) \right] &  \leq \frac{1 }{ \left| \mathcal{U} \right| }  \sum_{u \in \mathcal{U} } \sigma_u^2   \\
& +   \frac{e^t-1}{t} \left( \E \left[  \text{MSE} \big(  \mathcal{U}^{*}_B \big) \right] -  \frac{1 }{ \left| \mathcal{U} \right| }  \sum_{u \in \mathcal{U} } \sigma_u^2 \right).
\end{align*}
\end{theorem}
The proof relies on the same techniques of Theorem \ref{GREEDY}, albeit plugging the variance-scaled matrix $ P_B C_B^{-1}$ instead of the matrix $P_B$, and is thus omitted here.



\paragraph{Reduction to unknown variances}
Until now, we assumed that each user has its own noise variance with respect to the model. Our analysis relied on the fact that these variances are known to us in advance. Clearly, this is never the case in real life.  However, in the setting of CF-based recommender systems, we can utilize the past ratings of a given user to estimate this variance. Formally, let $\mathcal{R} (u)$ be the set of items that user $u$ has rated. Then, $\sigma_u^2$ can be estimated as follows:
$$
\tilde{\sigma}_u^2 = \frac{1}{ | \mathcal{R}(u)  | } \sum_{i \in \mathcal{R}(u) } ( \tilde{r}_{ui} - {r}_{ui} )^2 ,
$$
where $ \tilde{r}_{ui} $ is as predicted by the LFM (Equation~\eqref{eq:LFM}). 
%
In the experimental section, we show that despite the fact that the variances are estimated and not known, Algorithm \ref{alg3} outperforms all the baselines (including Algorithm \ref{alg2}).
%Proving these results (or similar) to the actual variances might be possible, yet is outside the scope of this paper.

%Notice that in oppose to the analysis of the previous section, we cannot replace $P_{B^c}^{\prime}$ in the above with $P_{\mathcal{U}_i}^{\prime} $, due to the variance differences between users. It is also not clear to us whether the objective function is supermodular in this case, and thus we consider the following approximation for the objective function:
%\begin{equation} \label{objective_niid}
%  \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i} \left\{ \text{Trace} \left( \left( P_B^{\prime} C_B^{-2}  P_B^{\prime \top} \right)^{-1}  P_{\mathcal{U}_i}^\prime P_{\mathcal{U}_i}^{\prime \top} \right) \right\} .
%\end{equation}
%Basically, $P_{B^c}^\prime$ is replaced with $P_{\mathcal{U}_i}^\prime$ to ensure that the objective function is supermodular. In our setting we assume that $B$ is relatively small with respect to $\left| \mathcal{U}_i \right| $, and thus the approximation is reasonable. However, we cannot quantify this conjecture without further assumptions on the noise terms.
%Notice that since the objective function in Equation \eqref{objective_niid} is supermodular and monotone, and thus we can apply the greedy procedure to get an $\big( \frac{e}{e-1} \big)$-approximation to the optimum.
%

%
%
%In particular, we assume that the ratings of the users within $\mathcal{U}_B$ for the new item follow this model as well, when  $ \mu $ , $ b_u  $ and $  P_u  $ are as estimated by our model (Section \ref{pre}), whereas $ b_i  $ and $ Q_i $ are unknown to us (due to the fact that the new item was not considered in our model). Recall that our goal is to construct estimators  $\tilde{b}_i  $ and $ \tilde{Q}_i $, and consequently predict 
%\begin{equation}
%\tilde{r}_{ui} =  \mu + b_u + \tilde{b}_i  +  \tilde{Q}_i^{ \top} P_u  ,
%\end{equation}
%for any $ u \in \mathcal{U}_i \setminus \mathcal{U}_B$. Roughly speaking, the optimal design approach seeks to estimate the SSE for each selection of $\mathcal{U}_B$ without exposing the true ratings. We divide the analysis into two parts: (a) the noise terms $\set{\varepsilon_{ui}} $ are i.i.d., and (b) the noise terms $\set{\varepsilon_{ui}} $ are only independent (not necessarily identically distributed).
%

 
%\comment{Now, we denote by $P_B$ the matrix whose columns correspond to the vectors $ P_u $ for $ u \in \mathcal{U}_{B} $, and by $ P_{B^c} $ the matrix whose columns correspond to the vectors $ P_u $ for $ u \in \mathcal{U}_i \setminus \mathcal{U}_{B} $. }Next we observe that \eqref{eq: SSE with expectation} can be rewritten as:
%$$
% \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i}  \left\|  C_B \cdot P_B ^ \top \left( P_B P_B^\top \right)^{-1} P_{B^c}  \right\|_F^2,
%$$
%when $ \| \cdot \|_F $ refers to the Frobenius norm and $ C_B $ is the square root of the covariance matrix of $ \varepsilon_{ui} $ for $ u \in \mathcal{U}_{B} $.
%Now, since we assume $ \mathbb{E} \left[ \varepsilon_{ui}^2 \right] = \sigma^2 $ for all $u$, it is equivalent to solve the following problem:
%$$
% \min_{ \mathcal{U}_{B} \subset  \mathcal{U}_i}  \left\| P_B ^ \top \left( P_B P_B^\top \right)^{-1} P_{B^c}  \right\|_F^2 .
%$$
%The objective function can be shown to be ?? [\textbf{comment:} something is missing here]
%
%
%[\textbf{comment:} many bugs in Algorithm 2]
%The following algorithm shows how to select $U_{B_i}$:


preliminaries.tex
%\vspace{\secSpace}
\section{Preliminaries and Model}
\label{pre}

%\vspace{\parSpace}

%We start by providing necessary notations and defining the prediction model we use throughout this work - the LFM. We then turn to define the problem at hand.


We start by introducing the LFM and its notations. We then turn to define the problem at hand.


\subsection{The Latent Factor Model}
We denote by  $\mathcal{I}$ the set of all items, and by $\mathcal{U}$ the set of all users. The cardinality of these sets is denoted by  $ \left| \mathcal{I} \right| = m$, and $ \left| \mathcal{U} \right| = n$. We use $\mathcal{R}$ to denote the rating matrix, which is of size $n \times m$. A rating $r_{ui}$ indicates the preference of item $i$ by user $u$, where high values mean stronger preference. The matrix $\mathcal{R}$  is typically sparse, since most users rate just a small portion of the items.
%
%
%
%We denote by $\mathcal{R}$ a rating matrix which is of size $n \times m$, where $n$ denotes the number of users and $m$ denotes the number of items. We denote by $\mathcal{U}$ the set of all users, and by $\mathcal{I}$ the set of all items. A rating $r_{ui}$ indicates the preference of item $i$ by user $u$, where high values mean stronger preference. The matrix $\mathcal{R}$  is typically sparse, since most users rate just a small subset of the items.

Using the notations above, the LFM (with $k$ denoting its dimension) seeks to estimate each rating ${r}_{ui}$ as follows:
\begin{equation}
{r}_{ui} \approx \mu + b_i + b_u +  Q_i ^\top P_u \  ,
\label{eq:LFM}
\end{equation}
% assumes that each rating ${r}_{ui}$ complies with the following noisy model:
%\begin{equation}
%{r}_{ui} = \mu + b_i + b_u +  Q_i ^\top P_u + \varepsilon_{ui} \ ,
%\label{eq:LFM}
%\end{equation}
where $b_i \in  \mathbb{R}$ and $Q_i \in  \mathbb{R}^k$ are the bias and the latent factor vector of item $i$, respectively; $b_u  \in  \mathbb{R}$ and $P_u  \in  \mathbb{R}^k$ are the bias and the latent factor vector of user $u$, respectively; and $\mu \in \mathbb{R}$ denotes the overall average rating in $\mathcal{R}$. We use $\varepsilon_{ui}$ to denote the residual error of our model with respect to user $u$ and item $i$.


Intuitively, the term $Q_i ^\top P_u$ captures the interaction (or affinity) between user $u$ and item $i$, where high values implies stronger preference and vice versa. We denote by $Q$ the $k \times m$ matrix, whose columns correspond to the vectors $Q_i$ for $i=1,\ldots,m$, and by $P$ the $k \times n$ matrix, whose columns correspond to the vectors $P_u$ for $u=1,\ldots,n$. 
%We note that the employed LFM  learns all of the parameters $ \mu$, $ b_i$,  $ b_u $, $  Q_i $, and $ P_u$, and consequently generates a predicted rating $\tilde{r}_{ui} $ as follows:
%\begin{equation}
%\tilde{r}_{ui} = \mu + b_i + b_u +  Q_i ^\top P_u .
%\label{eq:LFM_prediction}
%\end{equation}
%We discuss metrics for evaluating the merit of a given LFM in Section \ref{sec:setup}.

An important aspect of our work is the following: as training the LFM is a completely orthogonal task to ours, we assume that we are given an already trained model and refer to it as ground truth. Practically, we assume that  each rating ${r}_{ui}$ complies with the following noisy model:
\begin{equation}
{r}_{ui} = \mu + b_i + b_u +  Q_i ^\top P_u + \varepsilon_{ui} \ ,
\label{eq:LFM_ground}
\end{equation}
where $\varepsilon_{ui}$ is assumed to be a zero-mean noise term. This assumption is very common and can be found in several previous works (see \cite{Yu-Bi-TrespI_CML2006} for instance). Moreover, a simple sanity check can verify that the assumption complies with the employed LFM: test the significance of the residuals as generated from a Gaussian distribution. 

%We define the prediction error on user $u$ and item $i$ as  $\varepsilon_{ui}=r_{ui}-\tilde{r}_{ui}$, and will henceforth assume that our model produces errors of zero mean. A common criterion for measuring the quality of a given model on offline data is the RMSE metric, which is defined as follows:
%$$
%\text{RMSE}(\mathcal{T}) = \sqrt{ \frac{1}{|\mathcal{T}| }  \sum_{r_{ui} \in  \mathcal{T} } \left( r_{ui} - \tilde{r}_{ui} \right) ^2  }
%=  \sqrt{ \frac{1}{|\mathcal{T}| } \sum_{r_{ui} \in  \mathcal{T} } \varepsilon_{ui}^2  } .
%$$
%Here, $ \mathcal{T} $  denotes the test set and $|\mathcal{T}|$ is the cardinality of $ \mathcal{T} $.


\subsection{Problem Definition}
We proceed to formally define our problem. Let $i$ be a new item ($i \not\in \mathcal{I}$), and denote by $\mathcal{U}^i \subset \mathcal{U}$ the pool of available users to rate it.
% We emphasize that $\mathcal{V}^i$ is a subset of $\mathcal{U}$, which is crucial for ensuring that users and reviewers follow the same prediction model. Otherwise, the  provided ratings (by the reviewers) are irrelevant to the task of predicting the users' ratings, and the setting is somewhat ill-defined.
 Also, we denote the budget constraint by $B$ (i.e., $B$  is the number of users we are allowed to assign with the task of rating item $i$), and use the notation $\mathcal{U}^i_B $ for subsets of $\mathcal{U}^i$, which are of size $B$.

%\todo[inline]{Ronny: Note that following our discussion yesterday, I'm separating the notations for reviewers and users. }

%Henceforth we use the following notations:\\
%$U$ - the set of all users.\\
%$U_i$ - the set of all users who rated item $i$.\\
%$B$ - a predefined integer that represent our budget.\\
%$U_{B_i}$ - the set of chosen $B$ users for item $i$.\\
%$r_{ui}$ - the true evaluation of item $i$ by user $u$.\\
%$r_{ui}^{U_B}$ - predicted evaluation of item $i$ by user $u$, based on evaluations of users in $U_{B_i}$.\\

%\vspace{\parSpace}

Now, given a budget constraint $B$, our goal is to select $B$ users to rate  item $i$ in order to minimize the expected MSE on the set of the remaining users $\mathcal{U}  \setminus \mathcal{U}^i_{B}$. More formally, we wish to solve the following optimization problem:
\begin{equation*} 
\min_{ \mathcal{U}^i_{B} \subset  \mathcal{U}^i} \left\{ \mathbb{E} \bigg[  \frac{1}{\left| \mathcal{U} \setminus \mathcal{U}^i_{B} \right|} \cdot \sum_{u \in  \mathcal{U}  \setminus \mathcal{U}^i_{B} } \left( \tilde{r}_{ui} - {r}_{ui} \right)^2 \bigg] \right\} ,
 \end{equation*}
 where $ \tilde{r}_{ui}$ denotes our prediction of $ {r}_{ui}$, and the expectation is taken over the noise terms consisting the ratings $\set{{r}_{ui}}$ (as defined in Equation~\eqref{eq:LFM_ground}).
 
 \vspace{\parSpace}


 To simplify the notations, in the sequel we refer to the set of the remaining users as $\mathcal{U}$ (instead of $\mathcal{U} \setminus \mathcal{U}_B^i$). 
 Essentially,  this means that the sets $\mathcal{U}$ and $\mathcal{U}_B^i$ are disjoint, and the problem of interest is thus translated to:
 \begin{equation} \label{prob_def}
\min_{ \mathcal{U}^i_{B} \subset  \mathcal{U}^i} \left\{ \mathbb{E} \bigg[  \frac{1}{\left| \mathcal{U} \right|} \cdot \sum_{u \in  \mathcal{U} } \left( \tilde{r}_{ui} - {r}_{ui} \right)^2 \bigg] \right\} .
 \end{equation}
Clearly, the objective function inherently depends on how we generate the predictions $\set{\tilde{r}_{ui}}$ given the set of  $B$ users 
$\mathcal{U}^i_{B}$, and their ratings of item $i$.
Thus we can divide the problem in Equation \eqref{prob_def} into two distinct problems:
\vspace{\parSpace}
\begin{description}
\item[Rating Prediction (Problem A):] given a subset of users $\mathcal{U}^i_B \subset \mathcal{U}^i$ and their ratings of item $i$, generate predictions $\set{\tilde{r}_{ui}}$ for all $ u \in \mathcal{U}$.
\vspace{-0.07cm}
\item[User Selection (Problem B):] given a pool of available users $\mathcal{U}^i$, select a subset of users $\mathcal{U}^i_B \subset \mathcal{U}^i$ to reveal their ranking of item $i$.
\end{description}
%\oa{maybe add here a sentence about the order of the problems? Chronologically, it should be Problem B and the Problem A. However, it is in fact Problem B that is affected by Problem A, and not vice versa.}

We shall point out that viewing the latent factor model as ground truth gives rise to an optimal solution for \textbf{Problem A}: least squares estimation (detailed in Section~\ref{optimal}). However, in the CF literature there exist other approaches that can potentially function better in practice (especially if the data is not well represented by the LFM). These approaches are presented in Section~\ref{baseline}, and will serve us as baselines for evaluating the merit of our approach.

%using a least squares estimator is a natural approach to Problem A, as we assume latent factor model as our ground truth. Thus in the remaining of the paper we focus on the user selection problem while assuming least squares estimation.  
%
%
%Compositions of solutions to these two separate problems will serve as our baselines.
%Section~\ref{optimal} will then present a holistic approach to the problem in Equation \eqref{prob_def}, which will be shown to outperform the baseline methods.  
%\todo[inline]{Ronny: Note the new names of Problems A and B}



previous.tex
%\vspace{\secSpace}

%\subsection{Collaborative Filtering}

%A popular and successful approach for constructing recommender systems in recent years is \textit{Collaborative Filtering} (CF), a term coined by the developers of Tapestry - the first recommender system \cite{Goldberg-Nichols-Oki-Terry_Commun1992}. In principle, CF does not require domain knowledge, and relies only on past behavior of the users (e.g., ratings and historical transactions). In particular, it captures interdependencies between items and interrelationships among users, to predict new user-item associations. CF is popular among developers since it is domain independent, and can detect aspects of data that are difficult or impossible to profile using known data attributes.
%As mentioned before, CF is one of the most successful techniques for constructing a recommender system.
 The two major fields of CF are \textit{neighborhood methods} and \textit{Latent Factor Models} (LFM). 
% 
% As the main technical contribution of our paper heavily relies on LFM, we find it useful to overview some of its principal properties.
% 
% Throughout this work we consider the LFM as our prediction model, and thus we find it useful to overview its main properties. 
 LFM characterizes both items and users as vectors in a space automatically inferred from observed data patterns. The latent space representation strives to capture the semantics of items and users, which drive most of their observed interactions. One of the most successful realizations of LFM, which combines good scalability with predictive accuracy, is based on low-rank MF  (e.g., see \cite{Koren-Bell-Volinsky_IEEE-Comp-2009}). In particular, low-rank MF provides a substantial expressive power that allows modeling specific data characteristics such as temporal effects \cite{koren_CommACM2010}, item taxonomy \cite{Dror-Koenigstein-Koren_RecSys2011}, and attributes \cite{Agarwal-Chen_KDD2009}. 

%Neighborhood methods compute the relationships among users or, alternatively, between items. For example,
%the item-item approach \cite{Linden-Smith-York_InternetComputing2003,Sarwar-Karypis-Konstan-Riedl_WWW2001} predicts the tendency of a user to an item by inspecting her ratings of ``neighboring'' items (items that tend to be rated similarly by users).

\vspace{\parSpace}




%The two major fields of CF are \textit{neighborhood methods} and \textit{latent factor models}. Neighborhood methods compute the relationships among users or, alternatively, between items. 
%%\oa{the following is an example for a neighborhood method?} 
%For example,
%the item-item approach \cite{Linden-Smith-York_InternetComputing2003,Sarwar-Karypis-Konstan-Riedl_WWW2001} predicts the tendency of a user to an item by inspecting her ratings of ``neighboring'' items (items that tend to be rated similarly by users). Latent factor models (LFM) characterize both items and users as vectors in a space automatically inferred from observed data patterns. The latent space representation strives to capture the semantics of items and users, which drive their observed interactions. One of the most successful realizations of LFM, which combines good scalability with predictive accuracy and is adopted in this work, is based on low-rank \textit{matrix factorization}  (e.g., see \cite{Koren-Bell-Volinsky_IEEE-Comp-2009}). In particular, MF provides a substantial expressive power that allows modeling specific data characteristics such as temporal effects \cite{koren_CommACM2010}, item taxonomy \cite{Dror-Koenigstein-Koren_RecSys2011}, and attributes \cite{Agarwal-Chen_KDD2009}. 

%\subsection{Cold-start problem}

One of the inherent limitations of MF is the need for historical user-item interactions. When such history is limited, MF-based recommenders cannot reliably model new entities, leading to the item and user cold-start problems. Despite the fact that users and items are usually represented similarly in the latent space, these two problems are essentially different due to the ability  to interview new users when joining the service in order to bootstrap their modeling. Moreover, each of these problems has a different line of previous works, as surveyed below.

\vspace{\parSpace}
%\subsubsection{User cold-start problem}

\paragraph{User cold-start problem}
Modeling the preferences of new users can be done most effectively by asking them to rate several carefully selected items of a seed set during a short interview \cite{Kohrs-Merialdo_ICMF2001,Rashid-Albert-Cosley-Lam-McNee-Konstan-Riedl_IUI2002,Rashid-Karypis-Riedl_KDD2008,Golbandi-Koren-Lempel_CIKM2010}. Item seed sets were constructed according to various criteria such as \textit{popularity} (items should be known to the users), \textit{contention} (items should be indicative of users' tendencies), and \textit{coverage} (items should possess predictive power on other items).

\vspace{\parSpace}

The importance of adaptive interviewing process using adaptive seed sets was already recognized in \cite{Rashid-Albert-Cosley-Lam-McNee-Konstan-Riedl_IUI2002}. Adaptive interviewing is commonly implemented by decision trees algorithms \cite{Rashid-Karypis-Riedl_KDD2008,Lee_ESA2010,Golbandi-Koren-Lempel_WSDM2011}. 
%\oa{the next two sentences are very confusing. in particular, RFM, NRS, and C4.5 overload the reader} In \cite{Lee_ESA2010} a commodity-retail recommendation methodology is explored, where a limited set of target customers is selected based on RFM (recency, frequency, monetary) scores. Then, correlation-based similarities are replaced with NRS (normalized relative spending) values, and a C4.5 decision tree is employed instead of association rules to explore the associations between commodities. In \cite{Golbandi-Koren-Lempel_WSDM2011}, the authors advocate a specialized version of decision trees as the most appropriate tool for adaptive interviewing. An efficient tree learning algorithm, specifically tailored to the unique properties of the problem, is shown  to outperform previous approaches such as the user clusters approach presented in \cite{Rashid-Karypis-Riedl_KDD2008}. Lastly, 
A method for solving the problem of initial interview construction within the context of learning user and item profiles is presented in \cite{Zhou-Yang-Zha_SIGIR2011}.

%\subsubsection{Item cold-start problem}
\vspace{\parSpace}

\paragraph{Item cold-start problem}
To mitigate the item-cold problem of CF, a common practice involves utilizing external content on top of users' feedback. The basic approach is to leverage items' attributes and combine them with the CF model in a way that allows treating new items
% for which not much users' feedback exists
\cite{Agarwal-Chen_KDD2009,Gunawardana-Meek_RECSYS2008,Gunawardana-Meek_RECSYS2009,Park-Chu_RECSYS2009}. In \cite{Agarwal-Chen_KDD2009} the authors proposed a regression-based latent factor model for cold-start recommendation. 
%\oa{I would summarize the next 6 lines, in a less dense sentence}
In their model a dyadic response matrix $\bold{Y}$ is estimated by a latent factor model $\bold{Y} \approx \bold{U}^\top \bold{V}$, where the latent factor matrices, $\bold{U}$ and $\bold{V}$, are estimated by regression $\bold{U}\approx \bold{F}\bold{X}$ and $\bold{V}\approx\bold{M}\bold{Z}$. The matrices $\bold{X}$ and $\bold{Z}$ are the user attribute and item feature matrices, and $\bold{F}$ and $\bold{M}$ are weight matrices learnt by regression. In a later work \cite{Park-Chu_RECSYS2009}, the authors improve the performance achieved in \cite{Agarwal-Chen_KDD2009} by solving a convex optimization problem that estimates the weight matrices, instead of computing the low-rank matrix decomposition of \cite{Agarwal-Chen_KDD2009}.
Another approach to tackle the item cold-start issue by combining content information with CF,  based on \textit{Boltzmann machines},  is studied in \cite{Gunawardana-Meek_RECSYS2008,Gunawardana-Meek_RECSYS2009}. 
%Unified Boltzmann Machines \cite{Gunawardana-Meek_RECSYS2009} are probabilistic models that learn from collaborative and content information by combining Untied Boltzmann Machines. The latter capture correlations between items, with Tied Boltzmann Machines \cite{Gunawardana-Meek_RECSYS2008} that take content information into account.

\vspace{\parSpace}

The  works described above require content or context data for new items. However, such data may not be available. In such cases, ratings for new items are arriving and one wishes to predict the missing ratings, with increasing accuracy, as more feedback is provided. Due to the incremental nature of the problem, one cannot afford to retrain the CF model with each arriving rating. A common heuristic approach is to estimate a new item's latent vector by a linear combination of the latent vectors of its raters and their respective ratings. It is based on the fact that users and items coexist as vectors in the same latent space and that ratings are usually estimated by user-item vector similarities. This principle was successfully practiced in various MF techniques \cite{Paterek_KDD2007,Koren_KDD2008,Aharon-Kagian-Koren-Lempel_RecSys2012,Aizenberg-Koren-Somekh_WWW2012}.
%\oa{here I would not mention the names explicitly, but only say that this approach will serve us as baseline in our work} 
%We note that this approach relates directly to the \textit{similarity based predictor} combined with the \textit{early birds raters} reviewer selection of Section \ref{baseline}. 
%\oa{the optimality here has not been defined yet. I propose omitting this sentence since it is not part of related work.} 
%RL - I agree, we're not doing the same thing - our setting isn't really the same
%In this work we take this principle a step further and given a set of raters we provide the optimal new item latent vector estimator in terms of RMSE.  
We note that this approach will serve us as baseline, as it does not require any content-based information and is thus suitable for our setting. 

\vspace{\secSpace}

%\subsection{Optimal design}
\paragraph{The optimal design approach} 
In the  statistical field called {\it optimal design of experiments}, or just {\it optimal design} \cite{atkinson1992optimum,Wu78}, a statistician is faced with the task of choosing a limited amount of experiments to perform from a given pool, with the goal of gaining the most informative results. There are various measurements for the gain obtained from a subset of experiments. The measure of interest in our setting is referred to as the $A$-optimality criterion. According to this criterion, the experiments correspond to noisy outputs of a (usually linear) regression function and the goal is to minimize the Mean Squared Error (MSE) over all the possible inputs of the regressor. 

%Formally, consider a pool of possible  experiments denoted $x_1,...,x_n \in \mathbb{R}^k$, and their corresponding labels $ y_i = f (x_i) + \varepsilon_i$. The noise terms $\set{\varepsilon_i}$ are usually assumed to be zero-mean, and $f$ is assumed to have a certain structure (e.g., linear in $x_i$). Now, given a budget constraint $B$, the designer is allowed to select $B$ experiments to reveal their labels in order to minimize the prediction error. 

\vspace{\parSpace}

An early attempt to tackle the user cold-start problem using optimal design techniques and an interviewing process appears in \cite{Yu-Bi-TrespI_CML2006}.
In this work, an adaptation of $A$-optimality, also referred to as \emph{transductive optimal design}, aims to minimize the MSE over some arbitrary (yet known in advance) set of points (or users, in our context).
Despite the original presentation in the setting of the user cold-start problem, the generality of the employed techniques allows handling the item cold-start problem in a similar manner.
 However, their work differs from ours due to the absence of performance guarantee for the proposed algorithms, and the use of an inferior prediction model.

%lack  differs from ours in aspects of the employed prediction model, and the absence of performance guarantee
%
%their work considers a different prediction model, and differs from ours in the aspects of the considered prediction model, the tackles the user cold-start problem, and utilizes interviewing techniques for this purpose. In addition, \cite{Yu-Bi-TrespI_CML2006} do not provide performance guarantee for their algorithms differs from ours in many aspects: first, we utilize state-of-the-art models for prediction; second, 
%
% and referred to as transductive optimal design.
%An adaptation of $A$-optimality, also referred to as transductive optimal design \cite{Yu-Bi-TrespI_CML2006}, aims to minimize the MSE over some arbitrary set of points, that is known in advance, rather than over the entire set of possible inputs.
%
%%\vspace{\parSpace}
%
%In this paper we discuss an optimal design approach to the item cold start problem that is similar to the $A$-optimal design and transductive $A$-optimal design. We present how the known techniques can be used in the item cold-start problem and obtain analytical guarantees taking advantage of the supermodularity and monotonicity of the problem. 


%Formally, consider a pool of possible  experiments denoted $x_1,...,x_n \in \mathbb{R}^d$. 
%The goal of the designer is to choose a distribution over the pool of experiments, such that experiments chosen according to this distribution produce a hypothesis $\hat{\bold{w}}$ that is as close as possible to the true linear function behind the data. The distance between the hypothesis and true linear function can be measured in different ways, each corresponding to a different \emph{optimality criteria}. The common property of the criteria is that they all minimize the variance of the hypothesis. Since the variance is not a scalar but a $d \times d$ matrix, the different criteria differ by the fact that each one minimizes a different function $\Phi: \mathbb{R}^{d\times d} \to \mathbb{R}$ over the covariance matrix. Common criteria are the $A$-, $D$-, and $E$-optimality criteria. $D$-optimality, minimizes the determinant of the covariance matrix, and thus minimizes the volume of the confidence region. In $A$-optimality the trace of the covariance matrix, i.e. the total variance of the parameter estimates, is minimized. $E$-optimality minimizes the maximum eigenvalue of the covariance matrix, and thus minimizes the size of the major axis of the confidence region.
%
%\vspace{\parSpace}
%
%The above criteria do not directly characterize the quality of predictions on test data. Several papers address this issue; a relevant example is by \cite{Yu-Bi-TrespI_CML2006} where the criteria is aimed to minimize the mean variance over the given data points. This is similar to $A$-optimality where the mean variance is minimized for a random unit vector (as opposed to a uniformly chosen data point).
 
%\cite{He-Min-Cai-Zhou_SIGIR2007}

itemColdStart_WWW2014.bbl
\begin{thebibliography}{10}

\bibitem{Agarwal-Chen_KDD2009}
Deepak Agarwal and Bee-Chung Chen.
\newblock Regression-based latent factor models.
\newblock In {\em Proc. KDD}, 2009.

\bibitem{Aharon-Kagian-Koren-Lempel_RecSys2012}
Michal Aharon, Amit Kagian, Yehuda Koren, and Ronny Lempel.
\newblock Dynamic personalized recommendation of comment-eliciting stories.
\newblock In {\em Proc. {RecSys}}, 2012.

\bibitem{Aizenberg-Koren-Somekh_WWW2012}
Natalie Aizenberg, Yehuda Koren, and Oren Somekh.
\newblock Build your own music recommender by modeling internet radio streams.
\newblock In {\em Proc. WWW}, 2012.

\bibitem{atkinson1992optimum}
A.~C. Atkinson and A.~N. Donev.
\newblock {\em Optimum Experimental Designs}.
\newblock Oxford Univ. Press, 1992.

\bibitem{Bennett-Lanning_KDD2007}
J.~Bennett and S.~Lanning.
\newblock The netflix prize.
\newblock In {\em Proc. KDD Cup and Workshop}, 2007.

\bibitem{Dror-Koenigstein-Koren_RecSys2011}
Gideon Dror, Noam Koenigstein, and Yehuda Koren.
\newblock Yahoo! music recommendations: Modeling music ratings with temporal
  dynamics and item.
\newblock In {\em Proc. {RecSys}}, 2011.

\bibitem{duchi2011adaptive}
John Duchi, Elad Hazan, and Yoram Singer.
\newblock Adaptive subgradient methods for online learning and stochastic
  optimization.
\newblock {\em Journal of Machine Learning Research (JMLR)}, 12:2121--2159,
  2011.

\bibitem{Golbandi-Koren-Lempel_CIKM2010}
Nadav Golbandi, Yehuda Koren, and Ronny Lempel.
\newblock On bootstrapping recommender systems.
\newblock In {\em Proc. CIKM}, 2010.

\bibitem{Golbandi-Koren-Lempel_WSDM2011}
Nadav Golbandi, Yehuda Koren, and Ronny Lempel.
\newblock Adaptive bootstrapping of recommender systems using decision trees.
\newblock In {\em Proc. WSDM}, 2011.

\bibitem{Gunawardana-Meek_RECSYS2008}
Asela Gunawardana and Christopher Meek.
\newblock Tied boltzmann machines for cold start recommendations.
\newblock In {\em Proc. {RecSys}}, 2008.

\bibitem{Gunawardana-Meek_RECSYS2009}
Asela Gunawardana and Christopher Meek.
\newblock A unified approach to building hybrid recommender systems.
\newblock In {\em Proc. {RecSys}}, 2009.

\bibitem{Ilev01}
Victor~P. Il'ev.
\newblock An approximation guarantee of the greedy descent algorithm for
  minimizing a supermodular set function.
\newblock {\em Discrete Applied Mathematics}, 114(1):131--146, 2001.

\bibitem{Kohrs-Merialdo_ICMF2001}
Arnd Kohrs and Bernard Merialdo.
\newblock Improving collaborative filtering for new users by smart object
  selection.
\newblock In {\em Proc. International Conference on Media Features (ICMF)},
  2001.

\bibitem{Koren_KDD2008}
Yehuda Koren.
\newblock Factorization meets the neighborhood: a multifaceted collaborative
  filtering model.
\newblock In {\em Proc. KDD}, 2008.

\bibitem{koren_CommACM2010}
Yehuda Koren.
\newblock Collaborative filtering with temporal dynamics.
\newblock {\em Commun. of the ACM}, 53(4):89--97, 2010.

\bibitem{Koren-Bell-Volinsky_IEEE-Comp-2009}
Yehuda Koren, Robert~M. Bell, and Chris Volinsky.
\newblock Matrix factorization techniques for recommender systems.
\newblock {\em Computer, IEEE}, 42(8):30--37, 2009.

\bibitem{krause2007near}
Andreas Krause and Carlos Guestrin.
\newblock Near-optimal observation selection using submodular functions.
\newblock In {\em AAAI}, volume~7, pages 1650--1654, 2007.

\bibitem{Lee_ESA2010}
Shao-Lun Lee.
\newblock Commodity recommendations of retail business based on decision tree
  induction.
\newblock {\em Expert Systems with Applications}, 37(5):3685--3694, 2010.

\bibitem{Park-Chu_RECSYS2009}
Seung-Taek Park and Wei Chu.
\newblock Pairwise preference regression for cold-start recommendation.
\newblock In {\em Proc. {RecSys}}, 2009.

\bibitem{Paterek_KDD2007}
Arkadiusz Paterek.
\newblock Improving regularized singular value decomposition for collaborative
  filtering.
\newblock In {\em Proc. KDD cup and workshop}, 2007.

\bibitem{Rashid-Albert-Cosley-Lam-McNee-Konstan-Riedl_IUI2002}
Al~Mamunur Rashid, Istvan Albert, Dan Cosley, Shyong~K Lam, Sean~M McNee,
  Joseph~A Konstan, and John Riedl.
\newblock Getting to know you: learning new user preferences in recommender
  systems.
\newblock In {\em Proc. International Conference on Intelligent User
  Interfaces}, 2002.

\bibitem{Rashid-Karypis-Riedl_KDD2008}
Al~Mamunur Rashid, George Karypis, and John Riedl.
\newblock Learning preferences of new users in recommender systems: an
  information theoretic approach.
\newblock {\em ACM SIGKDD Explorations Newsletter}, 10(2):90--100, 2008.

\bibitem{sagnol2013approximation}
Guillaume Sagnol.
\newblock Approximation of a maximum-submodular-coverage problem involving
  spectral functions, with application to experimental designs.
\newblock {\em Discrete Applied Mathematics}, 161(1):258--276, 2013.

\bibitem{Wu78}
Chien-Fu Wu.
\newblock Some algorithmic aspects of the theory of optimal designs.
\newblock {\em Annals of Statistics}, 6(6):1286--1301, 1978.

\bibitem{Yu-Bi-TrespI_CML2006}
Kai Yu, Jinbo Bi, and Volker Tresp.
\newblock Active learning via transductive experimental design.
\newblock In {\em Proc. ICML}, 2006.

\bibitem{Zhou-Yang-Zha_SIGIR2011}
Ke~Zhou, Shuang-Hong Yang, and Hongyuan Zha.
\newblock Functional matrix factorizations for cold-start recommendation.
\newblock In {\em Proc. SIGIR}, 2011.

\end{thebibliography}
