## 3 A Brief Introduction to Linear Regression Model  
In this section, we first briefly describe the computational procedure for linear regression. We then show a method to compute the optimal parameters of a linear model by minimizing the sum of the square of errors. This classical method is called the least square method [4; 25].  
Formally, linear regression is a linear approach to modeling the relationship between a response \(y\) and a set of \(m\) independent variables \(x_{1},x_{2},\ldots,x_{m}\) in an experiment. It can be expressed as  
\[y=\beta_{0}+\beta_{1}x_{1}+\cdots+\beta_{m}x_{m}.\]  
These independent variables \(x_{1},x_{2},\ldots,x_{m}\) are also called the features of the model.  
Suppose \(n\) experiments have been performed, each with different settings for the features \(x_{1},x_{2},\ldots,x_{m}\). With a set of \(n\) observed data, we obtain \(n\) equations.  
\[y_{i}=\beta_{0}+\beta_{1}x_{1}^{i}+\beta_{2}x_{2}^{i}+\cdots+\beta_{m}x_{m}^{ i},\quad i=1,2,\ldots,n,\]  
where \(x_{j}^{i}\) is the value of variable \(x_{j}\) used in the \(i\)-th experiment. It is convenient to write these \(n\) equations in matrix form. Let \(\vec{x}_{i}=[x_{1}^{i},x_{2}^{i},\ldots,x_{m}^{i}]\), and let the model coefficients be: \(\vec{\beta}=[\beta_{0},\beta_{1},\ldots,\beta_{m}]\). The model prediction would be  
\[y_{i}=\beta_{0}+\sum_{j=1}^{m}\beta_{j}x_{j}^{i}.\]  
If each \(\vec{x}_{i}\) is extended to \(\vec{x}_{i}=[1,x_{1}^{i},x_{2}^{i},\ldots,x_{m}^{i}]\), then  
\[y_{i}=\sum_{j=0}^{m}\beta_{j}x_{j}^{i}=\vec{\beta}\vec{x}_{i}^{T}.\]  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & **[PERSON]’s** & **[PERSON]’s** & **[PERSON]’s** & **[PERSON]’s** & **[PERSON]’s** & **[PERSON]’s** & **[PERSON]’s** & **Ours** \\  & **[**11**]** & **[**12**]** & **[**20**]** & **[**13**]** & **[**15**]** & **[**14**]** & **[**21**]** & \\ \hline TA & Y & Y & N & Y & Y & Y & Y & N \\ \hline HE & Y & Y & Y & Y & Y & Y & Y & N \\ \hline YG(SMC) & N & Y & N & N & Y & Y & N & N \\ \hline CF & Y & N & Y & N & N & N & N & Y \\ \hline Security & C & C & C & C & C & C & C & P \\ \hline \hline \end{tabular}  
TA: needs trusted or semi-trusted authority. HE: uses homomorphic encryption. YG(SMC): uses Yao’s garbled circuit for secure multiparty computation. CF uses closed-form formula to compute optimal parameters. Security: C means computationally secure; P means perfectly secure.  
\end{table}
Table 1: Comparison of related protocols.  
In constructing a linear model, the coefficients \(\beta_{0},\beta_{1},\ldots,\beta_{m}\) are unknowns. A set of \(n\) experiments can be performed to determine possible values of these \(m+1\) unknowns. These \(m+1\) unknowns \(\beta_{0},\beta_{1},\ldots,\beta_{m}\) are called parameters of the linear regression model.  
If all the experiments have no errors and the setting of the variables \(\vec{x}_{i}\) is independent, then \(m+1\) experiments are sufficient to determine the \(m+1\) unknowns \(\beta_{0},\beta_{1},\ldots,\beta_{m}\). However, almost all experiments cannot avoid errors. More than \(m+1\) experiments--usually many more experiments--are needed to obtain \"optimal\" values of \(\beta_{0},\beta_{1},\ldots,\beta_{m}\).  
To define the optimal values for these parameters, we first define the loss function. Given a set of values for \(\vec{\beta}=[\beta_{0},\beta_{1},\ldots,\beta_{m}]\), we can compute the loss with respect to \(\vec{\beta}\) as  
\[L(\vec{\beta})=\sum_{i=1}^{n}\Big{(}\vec{\beta}\vec{x}_{i}^{T}-y_{i}\Big{)}^{ 2}.\]  
In the least square setting, the optimum parameter is defined as the one that minimizes the sum of the mean square loss:  
\[\vec{\beta}=\arg\min L\Big{(}\vec{\beta}\Big{)}=\arg\min\sum_{i=1}^{n}\Big{(} \vec{\beta}\vec{x}_{i}^{T}-y_{i}\Big{)}^{2}.\]