multiparty_linear_regression.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Demo of Secure Multi-Party Linear Regression\n",
    "\n",
    "Source: Section 2 of *Secure multi-party linear regression at plaintext speed*\n",
    "\n",
    "https://github.com/jbloom22/DASH"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:43.983256Z",
     "start_time": "2019-08-14T21:22:43.018887Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from scipy.stats import t\n",
    "from statsmodels.api import OLS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SIMULATE data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:43.999774Z",
     "start_time": "2019-08-14T21:22:43.988665Z"
    }
   },
   "outputs": [],
   "source": [
    "np.random.seed(0)\n",
    "\n",
    "K = 10\n",
    "\n",
    "# Alice's data\n",
    "N1 = 1000\n",
    "y1 = np.random.randn(N1)\n",
    "C1 = np.random.randn(N1, K)\n",
    "\n",
    "# Bob's data\n",
    "N2 = 2000\n",
    "y2 = np.random.randn(N2)\n",
    "C2 = np.random.randn(N2, K)\n",
    "\n",
    "# Carla's data\n",
    "N3 = 1500\n",
    "y3 = np.random.randn(N3)\n",
    "C3 = np.random.randn(N3, K)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PRIVATE COMPUTATION - Compress"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:44.014314Z",
     "start_time": "2019-08-14T21:22:44.005022Z"
    }
   },
   "outputs": [],
   "source": [
    "# Alice\n",
    "yy1 = y1.T @ y1\n",
    "Cty1 = C1.T @ y1\n",
    "CtC1 = C1.T @ C1\n",
    "\n",
    "# Bob\n",
    "yy2 = y2.T @ y2\n",
    "Cty2 = C2.T @ y2\n",
    "CtC2 = C2.T @ C2\n",
    "\n",
    "# Carla\n",
    "yy3 = y3.T @ y3\n",
    "Cty3 = C3.T @ y3\n",
    "CtC3 = C3.T @ C3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MULTI-PARTY COMPUTATION - Combine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Computation is now independent of the sample sizes. Practical security follows from non-invertibility of compression. For theoretical guarantees, do the following one, two, or three cells with secure multi-party computation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:44.027231Z",
     "start_time": "2019-08-14T21:22:44.019216Z"
    }
   },
   "outputs": [],
   "source": [
    "D = N1 + N2 + N3 - K\n",
    "yty = yy1 + yy2 + yy3\n",
    "Cty = Cty1 + Cty2 + Cty3\n",
    "CtC = CtC1 + CtC2 + CtC3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To limit secure computation to addition, parties could choose to share `D`, `yty`, `Cty`, and `CtC`, and compute the remaining cells privately. Note that this leaks info beyond the per-coefficient statistics and p-values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:44.027231Z",
     "start_time": "2019-08-14T21:22:44.019216Z"
    }
   },
   "outputs": [],
   "source": [
    "invCtC = np.linalg.inv(CtC)\n",
    "beta = invCtC @ Cty\n",
    "residual_sq = (yty - beta @ CtC @ beta) / D\n",
    "sigma_sq = np.diag(invCtC) * residual_sq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To reduce secure computation, parties could choose to share `beta` and `sigma_sq` and compute the remaining cell privately."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:44.027231Z",
     "start_time": "2019-08-14T21:22:44.019216Z"
    }
   },
   "outputs": [],
   "source": [
    "sigma = np.sqrt(sigma_sq)\n",
    "tstat = beta / sigma\n",
    "pval = 2 * t.cdf(-abs(tstat), D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:44.068892Z",
     "start_time": "2019-08-14T21:22:44.059128Z"
    },
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "df = pd.DataFrame({'beta': beta,\n",
    "                   'sigma': sigma, \n",
    "                   'tstat': tstat,\n",
    "                   'pval': pval})\n",
    "\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### VERIFY correctness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Computing results using OLS model from statsmodel API:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:44.093115Z",
     "start_time": "2019-08-14T21:22:44.074893Z"
    }
   },
   "outputs": [],
   "source": [
    "y = np.concatenate([y1 ,y2, y3])\n",
    "C = np.concatenate([C1, C2, C3])\n",
    "\n",
    "res = OLS(y, C, hasconst=False).fit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df2 = pd.DataFrame({'beta': res.params,\n",
    "                    'sigma': res.bse, \n",
    "                    'tstat': res.tvalues, \n",
    "                    'pval': res.pvalues})\n",
    "\n",
    "df2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verify agreement up to 10 digits after the decimal point:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-08-14T21:22:44.167421Z",
     "start_time": "2019-08-14T21:22:44.111173Z"
    },
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "df = df.apply(lambda x: round(x, 10))\n",
    "df2 = df2.apply(lambda x: round(x, 10))\n",
    "np.array(df == df2).all() # Returns TRUE"
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}