logistic_SCAD_MCP_cp_MODULE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Set up the class fundementals \n",
    "\n",
    "## Kai Yang\n",
    "## <kai.yang2 \"at\" mail.mcgill.ca>\n",
    "## License :: OSI Approved :: GNU Affero General Public License v3 or later (AGPLv3+)\n",
    "## [GPG Public key Fingerprint: B9F863A56220DBD56B91C3E835022A1A5941D810](https://keys.openpgp.org/vks/v1/by-fingerprint/B9F863A56220DBD56B91C3E835022A1A5941D810)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-08-09T22:25:06.087399Z",
     "start_time": "2022-08-09T22:25:05.893902Z"
    }
   },
   "outputs": [],
   "source": [
    "import warnings\n",
    "\n",
    "warnings.filterwarnings('ignore')\n",
    "# import os, sys\n",
    "# import collections\n",
    "# import numpy as np\n",
    "import cupy as _cp\n",
    "# import matplotlib.markers as markers\n",
    "# import matplotlib.pyplot as plt\n",
    "# import timeit\n",
    "# import collections\n",
    "# from scipy.linalg import toeplitz, block_diag\n",
    "# from scipy.stats import median_abs_deviation as mad\n",
    "# import multiprocessing\n",
    "# import cProfile\n",
    "# import itertools\n",
    "# from numba import jit, njit, cuda, vectorize\n",
    "# import warnings\n",
    "# warnings.filterwarnings('ignore') # this is just to hide all the warnings\n",
    "# import rpy2.robjects as robjects\n",
    "# import matplotlib.pyplot as plt # change font globally to Times\n",
    "# plt.style.use('ggplot')\n",
    "# plt.rcParams.update({\n",
    "#     \"text.usetex\": True,\n",
    "#     \"font.family\": \"Times New Roman\",\n",
    "#     \"font.sans-serif\": [\"Times New Roman\"],\n",
    "#     \"font.size\": 12})\n",
    "\n",
    "# os.chdir(sys.path[0]) # ensure working direcotry is set same as the file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-08-09T22:25:06.098456Z",
     "start_time": "2022-08-09T22:25:06.088862Z"
    }
   },
   "outputs": [],
   "source": [
    "######################################  some SCAD and MCP things  #######################################\n",
    "def soft_thresholding(x, lambda_):\n",
    "    '''\n",
    "    To calculate soft-thresholding mapping of a given ONE-DIMENSIONAL tensor, BESIDES THE FIRST TERM (so beta_0 will not be penalized). \n",
    "    This function is to be used for calculation involving L1 penalty term later. \n",
    "    '''\n",
    "    return _cp.hstack((_cp.array([x[0]]),\n",
    "                       _cp.where(\n",
    "                           _cp.abs(x[1:]) > lambda_,\n",
    "                           x[1:] - _cp.sign(x[1:]) * lambda_, 0)))\n",
    "\n",
    "\n",
    "def SCAD(x, lambda_, a=3.7):\n",
    "    '''\n",
    "    To calculate SCAD penalty value;\n",
    "    #x can be a mult# import os, sys\n",
    "# import collections\n",
    "import numpy as np\n",
    "import cupy as cp\n",
    "import matplotlib.markers as markers\n",
    "import matplotlib.pyplot as plt\n",
    "import timeit\n",
    "# import collections\n",
    "from scipy.linalg import toeplitz, block_diag\n",
    "from scipy.stats import median_abs_deviation as mad\n",
    "# import multiprocessing\n",
    "# import cProfile\n",
    "# import itertools\n",
    "from numba import jit, njit, cuda, vectorize\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore') # this is just to hide all the warnings\n",
    "# import rpy2.robjects as robjects\n",
    "# import matplotlib.pyplot as plt # change font globally to Times \n",
    "# plt.style.use('ggplot')\n",
    "# plt.rcParams.update({\n",
    "#     \"text.usetex\": True,\n",
    "#     \"font.family\": \"Times New Roman\",\n",
    "#     \"font.sans-serif\": [\"Times New Roman\"],\n",
    "#     \"font.size\": 12})\n",
    "\n",
    "# os.chdir(sys.path[0]) # ensure working direcotry is set same as the filei-dimensional tensor;\n",
    "    lambda_, a are scalars;\n",
    "    Fan and Li suggests to take a as 3.7 \n",
    "    '''\n",
    "    # here I notice the function is de facto a function of absolute value of x, therefore take absolute value first to simplify calculation\n",
    "    x = _cp.abs(x)\n",
    "    temp = _cp.where(\n",
    "        x <= lambda_, lambda_ * x,\n",
    "        _cp.where(x < a * lambda_,\n",
    "                  (2 * a * lambda_ * x - x**2 - lambda_**2) / (2 * (a - 1)),\n",
    "                  lambda_**2 * (a + 1) / 2))\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp\n",
    "\n",
    "\n",
    "def SCAD_grad(x, lambda_, a=3.7):\n",
    "    '''\n",
    "    To calculate the gradient of SCAD wrt. icput x; \n",
    "    #x can be a multi-dimensional tensor. \n",
    "    '''\n",
    "    # here decompose x to sign and its absolute value for easier calculation\n",
    "    sgn = _cp.sign(x)\n",
    "    x = _cp.abs(x)\n",
    "    temp = _cp.where(\n",
    "        x <= lambda_, lambda_ * sgn,\n",
    "        _cp.where(x < a * lambda_, (a * lambda_ * sgn - sgn * x) / (a - 1), 0))\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp\n",
    "\n",
    "\n",
    "def MCP(x, lambda_, gamma):\n",
    "    '''\n",
    "    To calculate MCP penalty value; \n",
    "    #x can be a multi-dimensional tensor. \n",
    "    '''\n",
    "    # the function is a function of absolute value of x\n",
    "    x = _cp.abs(x)\n",
    "    temp = _cp.where(x <= gamma * lambda_, lambda_ * x - x**2 / (2 * gamma),\n",
    "                     .5 * gamma * lambda_**2)\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp\n",
    "\n",
    "\n",
    "def MCP_grad(x, lambda_, gamma):\n",
    "    '''\n",
    "    To calculate MCP gradient wrt. icput x; \n",
    "    #x can be a multi-dimensional tensor. \n",
    "    '''\n",
    "    temp = _cp.where(\n",
    "        _cp.abs(x) < gamma * lambda_,\n",
    "        lambda_ * _cp.sign(x) - x / gamma, _cp.zeros_like(x))\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp\n",
    "\n",
    "\n",
    "def SCAD_concave(x, lambda_, a=3.7):\n",
    "    '''\n",
    "    The value of concave part of SCAD penalty; \n",
    "    #x can be a multi-dimensional tensor. \n",
    "    '''\n",
    "    x = _cp.abs(x)\n",
    "    temp = _cp.where(\n",
    "        x <= lambda_, 0.,\n",
    "        _cp.where(x < a * lambda_,\n",
    "                  (lambda_ * x - (x**2 + lambda_**2) / 2) / (a - 1),\n",
    "                  (a + 1) / 2 * lambda_**2 - lambda_ * x))\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp\n",
    "\n",
    "\n",
    "def SCAD_concave_grad(x, lambda_, a=3.7):\n",
    "    '''\n",
    "    The gradient of concave part of SCAD penalty wrt. icput x; \n",
    "    #x can be a multi-dimensional tensor. \n",
    "    '''\n",
    "    sgn = _cp.sign(x)\n",
    "    x = _cp.abs(x)\n",
    "    temp = _cp.where(\n",
    "        x <= lambda_, 0.,\n",
    "        _cp.where(x < a * lambda_, (lambda_ * sgn - sgn * x) / (a - 1),\n",
    "                  -lambda_ * sgn))\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp\n",
    "\n",
    "\n",
    "def MCP_concave(x, lambda_, gamma):\n",
    "    '''\n",
    "    The value of concave part of MCP penalty; \n",
    "    #x can be a multi-dimensional tensor. \n",
    "    '''\n",
    "    # similiar as in MCP\n",
    "    x = _cp.abs(x)\n",
    "    temp = _cp.where(x <= gamma * lambda_, -(x**2) / (2 * gamma),\n",
    "                     (gamma * lambda_**2) / 2 - lambda_ * x)\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp\n",
    "\n",
    "\n",
    "def MCP_concave_grad(x, lambda_, gamma):\n",
    "    '''\n",
    "    The gradient of concave part of MCP penalty wrt. icput x; \n",
    "    #x can be a multi-dimensional tensor. \n",
    "    '''\n",
    "    temp = _cp.where(\n",
    "        _cp.abs(x) < gamma * lambda_, -x / gamma, -lambda_ * _cp.sign(x))\n",
    "    temp[0] = 0.  # this is to NOT penalize intercept beta later\n",
    "    return temp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-08-09T22:25:06.493219Z",
     "start_time": "2022-08-09T22:25:06.199360Z"
    }
   },
   "outputs": [],
   "source": [
    "def _update_smooth_grad_convex_logistic(N, X, beta_md, y):\n",
    "    '''\n",
    "    Update the gradient of the smooth convex objective component.\n",
    "    '''\n",
    "    return (X.T @ (_cp.tanh(X @ beta_md / 2.) / 2. - y + .5)) / (2. * N)\n",
    "\n",
    "\n",
    "def _update_smooth_grad_convex_logistic(N, X, beta_md, y):\n",
    "    '''\n",
    "    Update the gradient of the smooth convex objective component.\n",
    "    '''\n",
    "    return 1. / N * X.T @ (X @ beta_md - y)\n",
    "\n",
    "\n",
    "def _update_smooth_grad_SCAD_logistic(N, X, beta_md, y, _lambda, a):\n",
    "    '''\n",
    "    Update the gradient of the smooth objective component for SCAD penalty.\n",
    "    '''\n",
    "    return _update_smooth_grad_convex_logistic(\n",
    "        N=N, X=X, beta_md=beta_md, y=y) + SCAD_concave_grad(\n",
    "            x=beta_md, lambda_=_lambda, a=a)\n",
    "\n",
    "\n",
    "def _update_smooth_grad_MCP_logistic(N, X, beta_md, y, _lambda, gamma):\n",
    "    '''\n",
    "    Update the gradient of the smooth objective component for MCP penalty.\n",
    "    '''\n",
    "    return _update_smooth_grad_convex_logistic(\n",
    "        N=N, X=X, beta_md=beta_md, y=y) + MCP_concave_grad(\n",
    "            x=beta_md, lambda_=_lambda, gamma=gamma)\n",
    "\n",
    "\n",
    "def _eval_obj_SCAD_logistic(N, X, beta_md, y, _lambda, a, x_temp):\n",
    "    '''\n",
    "    evaluate value of the objective function.\n",
    "    '''\n",
    "    error = y - X @ x_temp\n",
    "    return (error.T @ error) / (2. * N) + _cp.sum(\n",
    "        SCAD(x_temp, lambda_=_lambda, a=a))\n",
    "\n",
    "\n",
    "def _eval_obj_MCP_logistic(N, X, beta_md, y, _lambda, gamma, x_temp):\n",
    "    '''\n",
    "    evaluate value of the objective function.\n",
    "    '''\n",
    "    error = y - X @ x_temp\n",
    "    return (error.T @ error) / (2 * N) + _cp.sum(\n",
    "        SCAD(x_temp, lambda_=_lambda, gamma=gamma))\n",
    "\n",
    "\n",
    "def lambda_max_logistic(X, y):\n",
    "    \"\"\"\n",
    "    Calculate the lambda_max, i.e., the minimum lambda to nullify all penalized betas.\n",
    "    \"\"\"\n",
    "    #     X_temp = X.copy()\n",
    "    #     X_temp = X_temp[:,1:]\n",
    "    #     X_temp -= _cp.mean(X_temp,0).reshape(1,-1)\n",
    "    #     X_temp /= _cp.std(X_temp,0)\n",
    "    #     y_temp = y.copy()\n",
    "    #     y_temp -= _cp.mean(y)\n",
    "    #     y_temp /= _cp.std(y)\n",
    "    grad_at_0 = y @ X[:, 1:] / len(y)\n",
    "    lambda_max = _cp.linalg.norm(grad_at_0, ord=_cp.infty)\n",
    "    return lambda_max\n",
    "\n",
    "\n",
    "def _strong_rule_seq_logistic(X, y, beta_old, lambda_new, lambda_old):\n",
    "    \"\"\"\n",
    "    Use sequential strong to determine which betas to be nullified next.\n",
    "    \"\"\"\n",
    "    #     X_temp = X.copy()\n",
    "    #     X_temp -= _cp.mean(X_temp,0).reshape(1,-1)\n",
    "    #     X_temp /= _cp.std(X_temp,0)\n",
    "    #     y_temp = y.copy()\n",
    "    #     y_temp -= _cp.mean(y)\n",
    "    #     y_temp /= _cp.std(y)\n",
    "    grad = _cp.abs((y - X[:, 1:] @ beta_old[1:]) @ X[:, 1:] / (2 * len(y)))\n",
    "    eliminated = (grad < 2 * lambda_new - lambda_old\n",
    "                  )  # True means the value gets eliminated\n",
    "    eliminated = _cp.hstack(\n",
    "        (_cp.array([False]),\n",
    "         eliminated))  # because intercept coefficient is not penalized\n",
    "    return eliminated\n",
    "\n",
    "\n",
    "def UAG_logistic_SCAD_MCP(design_matrix,\n",
    "                          outcome,\n",
    "                          beta_0=_cp.ones(1),\n",
    "                          tol=1e-2,\n",
    "                          maxit=500,\n",
    "                          _lambda=.5,\n",
    "                          penalty=\"SCAD\",\n",
    "                          a=3.7,\n",
    "                          gamma=2.,\n",
    "                          L_convex=1.1,\n",
    "                          add_intercept_column=True):\n",
    "    '''\n",
    "    Carry out the optimization for penalized logistic model for a fixed lambda.\n",
    "    '''\n",
    "    X = design_matrix.copy()\n",
    "    y = outcome.copy()\n",
    "    N = X.shape[0]\n",
    "    if _cp.all(beta_0 == _cp.ones(1)):\n",
    "        cov = (y - _cp.mean(y)) @ (X - 1 / N * _cp.sum(X, 0).reshape(1, -1))\n",
    "        beta = cov / _cp.var(X, 0)\n",
    "    else:\n",
    "        beta = beta_0\n",
    "#     add design matrix column for the intercept, if it's not there already\n",
    "    if add_intercept_column == True:\n",
    "        if _cp.any(\n",
    "                X[:, 0] != X[0, 0]\n",
    "        ):  # check if design matrix has included a column for intercept or not\n",
    "            intercept_design = _cp.ones(N).reshape(-1, 1)\n",
    "            X = _cp.hstack((intercept_design, X))\n",
    "            beta = _cp.hstack((_cp.array([0.]), beta))\n",
    "    # passing other parameters\n",
    "    p = X.shape[1]  # so here p includes the intercept design matrix column\n",
    "    smooth_grad = _cp.ones(p)\n",
    "    beta_ag = beta.copy()\n",
    "    beta_md = beta.copy()\n",
    "    k = 0\n",
    "    converged = False\n",
    "    opt_alpha = 1.\n",
    "    #     L_convex = 1/N*_cp.max(_cp.linalg.eigvalsh(X@X.T)[-1]).item()\n",
    "    if L_convex == 1.1:\n",
    "        L_convex = 1 / N * (_cp.linalg.eigvalsh(X @ X.T)[-1])\n",
    "    else:\n",
    "        pass\n",
    "    old_speed_norm = 1.\n",
    "    speed_norm = 1.\n",
    "    restart_k = 0\n",
    "\n",
    "    if penalty == \"SCAD\":\n",
    "        L = max([L_convex, 1. / (a - 1)])\n",
    "        #         L = _cp.linalg.norm(_cp.array([L_convex, 1./(a-1)]), ord=_cp.infty)\n",
    "        opt_beta = .99 / L\n",
    "        while ((not converged) or (k < 3)) and k <= maxit:\n",
    "            k += 1\n",
    "            if old_speed_norm > speed_norm and k - restart_k >= 3:  # in this case, restart\n",
    "                opt_alpha = 1.  # restarting\n",
    "                restart_k = k  # restarting\n",
    "            else:  # restarting\n",
    "                opt_alpha = 2 / (\n",
    "                    1 + (1 + 4. / opt_alpha**2)**.5\n",
    "                )  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            opt_lambda = opt_beta / opt_alpha  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            beta_md_old = beta_md.copy()  # restarting\n",
    "            beta_md = (1 - opt_alpha) * beta_ag + opt_alpha * beta\n",
    "            old_speed_norm = speed_norm  # restarting\n",
    "            speed_norm = _cp.linalg.norm(beta_md - beta_md_old,\n",
    "                                         ord=2)  # restarting\n",
    "            converged = (_cp.linalg.norm(beta_md - beta_md_old, ord=_cp.infty)\n",
    "                         < tol)\n",
    "            smooth_grad = _update_smooth_grad_SCAD_logistic(N=N,\n",
    "                                                            X=X,\n",
    "                                                            beta_md=beta_md,\n",
    "                                                            y=y,\n",
    "                                                            _lambda=_lambda,\n",
    "                                                            a=a)\n",
    "            beta = soft_thresholding(x=beta - opt_lambda * smooth_grad,\n",
    "                                     lambda_=opt_lambda * _lambda)\n",
    "            beta_ag = soft_thresholding(x=beta_md - opt_beta * smooth_grad,\n",
    "                                        lambda_=opt_beta * _lambda)\n",
    "#             converged = _cp.all(_cp.max(_cp.abs(beta_md - beta_ag)/opt_beta) < tol).item()\n",
    "#             converged = (_cp.linalg.norm(beta_md - beta_ag, ord=_cp.infty) < (tol*opt_beta))\n",
    "    else:\n",
    "        L = max([L_convex, 1. / gamma])\n",
    "        #         L = _cp.linalg.norm(_cp.array([L_convex, 1./(gamma)]), ord=_cp.infty)\n",
    "        opt_beta = .99 / L\n",
    "        while ((not converged) or (k < 3)) and k <= maxit:\n",
    "            k += 1\n",
    "            if old_speed_norm > speed_norm and k - restart_k >= 3:  # in this case, restart\n",
    "                opt_alpha = 1.  # restarting\n",
    "                restart_k = k  # restarting\n",
    "            else:  # restarting\n",
    "                opt_alpha = 2 / (\n",
    "                    1 + (1 + 4. / opt_alpha**2)**.5\n",
    "                )  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            opt_lambda = opt_beta / opt_alpha  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            beta_md_old = beta_md.copy()  # restarting\n",
    "            beta_md = (1 - opt_alpha) * beta_ag + opt_alpha * beta\n",
    "            old_speed_norm = speed_norm  # restarting\n",
    "            speed_norm = _cp.linalg.norm(beta_md - beta_md_old,\n",
    "                                         ord=2)  # restarting\n",
    "            converged = (_cp.linalg.norm(beta_md - beta_md_old, ord=_cp.infty)\n",
    "                         < tol)\n",
    "            smooth_grad = _update_smooth_grad_MCP_logistic(N=N,\n",
    "                                                           X=X,\n",
    "                                                           beta_md=beta_md,\n",
    "                                                           y=y,\n",
    "                                                           _lambda=_lambda,\n",
    "                                                           gamma=gamma)\n",
    "            beta = soft_thresholding(x=beta - opt_lambda * smooth_grad,\n",
    "                                     lambda_=opt_lambda * _lambda)\n",
    "            beta_ag = soft_thresholding(x=beta_md - opt_beta * smooth_grad,\n",
    "                                        lambda_=opt_beta * _lambda)\n",
    "#             converged = _cp.all(_cp.max(_cp.abs(beta_md - beta_ag)/opt_beta) < tol).item()\n",
    "#             converged = (_cp.linalg.norm(beta_md - beta_ag, ord=_cp.infty) < (tol*opt_beta))\n",
    "    return k, beta_md\n",
    "\n",
    "\n",
    "# def vanilla_proximal(self):\n",
    "#     '''\n",
    "#     Carry out optimization using vanilla gradient descent.\n",
    "#     '''\n",
    "#     if self.penalty == \"SCAD\":\n",
    "#         L = max([self.L_convex, 1/(self.a-1)])\n",
    "#         self.vanilla_stepsize = 1/L\n",
    "#         self._eval_obj_SCAD_logistic(self.beta_md, self.obj_value)\n",
    "#         self._eval_obj_SCAD_logistic(self.beta, self.obj_value_ORIGINAL)\n",
    "#         self._eval_obj_SCAD_logistic(self.beta_ag, self.obj_value_AG)\n",
    "#         self.old_beta = self.beta_md - 10.\n",
    "#         while not self.converged:\n",
    "#             self.k += 1\n",
    "#             if self.k <= self.maxit:\n",
    "#                 self._update_smooth_grad_SCAD_logistic()\n",
    "#                 self.beta_md = self.soft_thresholding(self.beta_md - self.vanilla_stepsize*self.smooth_grad, self.vanilla_stepsize*self._lambda)\n",
    "#                 self.converged = _cp.all(_cp.max(_cp.abs(self.beta_md - self.old_beta)) < self.tol).item()\n",
    "#                 self.old_beta = self.beta_md.copy()\n",
    "#                 self._eval_obj_SCAD_logistic(self.beta_md, self.obj_value)\n",
    "#                 self._eval_obj_SCAD_logistic(self.beta, self.obj_value_ORIGINAL)\n",
    "#                 self._eval_obj_SCAD_logistic(self.beta_ag, self.obj_value_AG)\n",
    "#             else:\n",
    "#                 break\n",
    "#     else:\n",
    "#         L = max([self.L_convex, 1/self.gamma])\n",
    "#         self.vanilla_stepsize = 1/L\n",
    "#         self._eval_obj_MCP_logistic(self.beta_md, self.obj_value)\n",
    "#         self._eval_obj_MCP_logistic(self.beta, self.obj_value_ORIGINAL)\n",
    "#         self._eval_obj_MCP_logistic(self.beta_ag, self.obj_value_AG)\n",
    "#         self.old_beta = self.beta_md - 10.\n",
    "#         while not self.converged:\n",
    "#             self.k += 1\n",
    "#             if self.k <= self.maxit:\n",
    "#                 self._update_smooth_grad_MCP_logistic()\n",
    "#                 self.beta_md = self.soft_thresholding(self.beta_md - self.vanilla_stepsize*self.smooth_grad, self.vanilla_stepsize*self._lambda)\n",
    "#                 self.converged = _cp.all(_cp.max(_cp.abs(self.beta_md - self.old_beta)) < self.tol).item()\n",
    "#                 self.old_beta = self.beta_md.copy()\n",
    "#                 self._eval_obj_MCP_logistic(self.beta_md, self.obj_value)\n",
    "#                 self._eval_obj_MCP_logistic(self.beta, self.obj_value_ORIGINAL)\n",
    "#                 self._eval_obj_MCP_logistic(self.beta_ag, self.obj_value_AG)\n",
    "#             else:\n",
    "#                 break\n",
    "#     return self.report_results()\n",
    "\n",
    "\n",
    "def solution_path_logistic(design_matrix,\n",
    "                           outcome,\n",
    "                           lambda_,\n",
    "                           beta_0=_cp.ones(1),\n",
    "                           tol=1e-2,\n",
    "                           maxit=500,\n",
    "                           penalty=\"SCAD\",\n",
    "                           a=3.7,\n",
    "                           gamma=2.,\n",
    "                           add_intercept_column=True):\n",
    "    '''\n",
    "    Carry out the optimization for the solution path without the strong rule.\n",
    "    '''\n",
    "    #     add design matrix column for the intercept, if it's not there already\n",
    "    if add_intercept_column == True:\n",
    "        if _cp.any(\n",
    "                X[:, 0] != X[0, 0]\n",
    "        ):  # check if design matrix has included a column for intercept or not\n",
    "            intercept_design = _cp.ones(N).reshape(-1, 1)\n",
    "            _design_matrix = design_matrix.copy()\n",
    "            _design_matrix = _cp.hstack((intercept_design, _design_matrix))\n",
    "        else:\n",
    "            _design_matrix = design_matrix\n",
    "    else:\n",
    "        _design_matrix = design_matrix\n",
    "    beta_mat = _cp.zeros((len(lambda_) + 1, _design_matrix.shape[1]))\n",
    "    for j in range(len(lambda_)):\n",
    "        beta_mat[j + 1, :] = UAG_logistic_SCAD_MCP(\n",
    "            design_matrix=_design_matrix,\n",
    "            outcome=outcome,\n",
    "            beta_0=beta_mat[j, :],\n",
    "            tol=tol,\n",
    "            maxit=maxit,\n",
    "            _lambda=lambda_[j],\n",
    "            penalty=penalty,\n",
    "            a=a,\n",
    "            gamma=gamma,\n",
    "            add_intercept_column=False)[1]\n",
    "    return beta_mat[1:, :]\n",
    "\n",
    "\n",
    "# with strong rule\n",
    "def _UAG_logistic_SCAD_MCP_strongrule(design_matrix,\n",
    "                                      outcome,\n",
    "                                      beta_0=_cp.ones(1),\n",
    "                                      tol=1e-2,\n",
    "                                      maxit=500,\n",
    "                                      _lambda=.5,\n",
    "                                      penalty=\"SCAD\",\n",
    "                                      a=3.7,\n",
    "                                      gamma=2.,\n",
    "                                      L_convex=1.1,\n",
    "                                      add_intercept_column=True,\n",
    "                                      strongrule=True):\n",
    "    '''\n",
    "    Carry out the optimization for a fixed lambda with strong rule.\n",
    "    '''\n",
    "    X = design_matrix.copy()\n",
    "    y = outcome.copy()\n",
    "    N = X.shape[0]\n",
    "    if _cp.all(beta_0 == _cp.ones(1)):\n",
    "        cov = (y - _cp.mean(y)) @ (X - 1 / N * _cp.sum(X, 0).reshape(1, -1))\n",
    "        beta = cov / _cp.var(X, 0)\n",
    "    else:\n",
    "        beta = beta_0\n",
    "#     add design matrix column for the intercept, if it's not there already\n",
    "    if add_intercept_column == True:\n",
    "        if _cp.any(\n",
    "                X[:, 0] != X[0, 0]\n",
    "        ):  # check if design matrix has included a column for intercept or not\n",
    "            intercept_design = _cp.ones(N).reshape(-1, 1)\n",
    "            X = _cp.hstack((intercept_design, X))\n",
    "            beta = _cp.hstack((_cp.array([0.]), beta))\n",
    "    if strongrule == True:\n",
    "        _lambda_max = lambda_max_logistic(X, y)\n",
    "        p_original = X.shape[1]\n",
    "        elim = _strong_rule_seq_logistic(X,\n",
    "                                         y,\n",
    "                                         beta_old=_cp.zeros(p_original),\n",
    "                                         lambda_new=_lambda,\n",
    "                                         lambda_old=_lambda_max)\n",
    "        X = X[:, _cp.logical_not(elim)]\n",
    "        beta = beta[_cp.logical_not(elim)]\n",
    "\n",
    "    # passing other parameters\n",
    "    p = X.shape[1]  # so here p includes the intercept design matrix column\n",
    "    smooth_grad = _cp.ones(p)\n",
    "    beta_ag = beta.copy()\n",
    "    beta_md = beta.copy()\n",
    "    k = 0\n",
    "    converged = False\n",
    "    opt_alpha = 1.\n",
    "    #     L_convex = 1/N*_cp.max(_cp.linalg.eigvalsh(X@X.T)[-1]).item()\n",
    "    if L_convex == 1.1:\n",
    "        L_convex = 1 / N * (_cp.linalg.eigvalsh(X @ X.T)[-1])\n",
    "    else:\n",
    "        pass\n",
    "    old_speed_norm = 1.\n",
    "    speed_norm = 1.\n",
    "    restart_k = 0\n",
    "\n",
    "    if penalty == \"SCAD\":\n",
    "        L = max([L_convex, 1 / (a - 1)])\n",
    "        #         L = _cp.linalg.norm(_cp.array([L_convex, 1./(a-1)]), ord=_cp.infty)\n",
    "        opt_beta = .99 / L\n",
    "        while ((not converged) or (k < 3)) and k <= maxit:\n",
    "            k += 1\n",
    "            if old_speed_norm > speed_norm and k - restart_k >= 3:  # in this case, restart\n",
    "                opt_alpha = 1.  # restarting\n",
    "                restart_k = k  # restarting\n",
    "            else:  # restarting\n",
    "                opt_alpha = 2. / (\n",
    "                    1. + (1. + 4. / opt_alpha**2)**.5\n",
    "                )  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            opt_lambda = opt_beta / opt_alpha  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            beta_md_old = beta_md.copy()  # restarting\n",
    "            beta_md = (1. - opt_alpha) * beta_ag + opt_alpha * beta\n",
    "            old_speed_norm = speed_norm  # restarting\n",
    "            speed_norm = _cp.linalg.norm(beta_md - beta_md_old,\n",
    "                                         ord=2)  # restarting\n",
    "            converged = (_cp.linalg.norm(beta_md - beta_md_old, ord=_cp.infty)\n",
    "                         < tol)\n",
    "            smooth_grad = _update_smooth_grad_SCAD_logistic(N=N,\n",
    "                                                            X=X,\n",
    "                                                            beta_md=beta_md,\n",
    "                                                            y=y,\n",
    "                                                            _lambda=_lambda,\n",
    "                                                            a=a)\n",
    "            beta = soft_thresholding(x=beta - opt_lambda * smooth_grad,\n",
    "                                     lambda_=opt_lambda * _lambda)\n",
    "            beta_ag = soft_thresholding(x=beta_md - opt_beta * smooth_grad,\n",
    "                                        lambda_=opt_beta * _lambda)\n",
    "#             converged = _cp.all(_cp.max(_cp.abs(beta_md - beta_ag)/opt_beta) < tol).item()\n",
    "#             converged = (_cp.linalg.norm(beta_md - beta_ag, ord=_cp.infty) < (tol*opt_beta))\n",
    "    else:\n",
    "        L = max([L_convex, 1 / gamma])\n",
    "        #         L = _cp.linalg.norm(_cp.array([L_convex, 1./(gamma)]), ord=_cp.infty)\n",
    "        opt_beta = .99 / L\n",
    "        while ((not converged) or (k < 3)) and k <= maxit:\n",
    "            k += 1\n",
    "            if old_speed_norm > speed_norm and k - restart_k >= 3:  # in this case, restart\n",
    "                opt_alpha = 1.  # restarting\n",
    "                restart_k = k  # restarting\n",
    "            else:  # restarting\n",
    "                opt_alpha = 2 / (\n",
    "                    1. + (1. + 4. / opt_alpha**2)**.5\n",
    "                )  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            opt_lambda = opt_beta / opt_alpha  #parameter settings based on minimizing Ghadimi and Lan's rate of convergence error upper bound\n",
    "            beta_md_old = beta_md.copy()  # restarting\n",
    "            beta_md = (1. - opt_alpha) * beta_ag + opt_alpha * beta\n",
    "            old_speed_norm = speed_norm  # restarting\n",
    "            speed_norm = _cp.linalg.norm(beta_md - beta_md_old,\n",
    "                                         ord=2)  # restarting\n",
    "            converged = (_cp.linalg.norm(beta_md - beta_md_old, ord=_cp.infty)\n",
    "                         < tol)\n",
    "            smooth_grad = _update_smooth_grad_MCP_logistic(N=N,\n",
    "                                                           X=X,\n",
    "                                                           beta_md=beta_md,\n",
    "                                                           y=y,\n",
    "                                                           _lambda=_lambda,\n",
    "                                                           gamma=gamma)\n",
    "            beta = soft_thresholding(x=beta - opt_lambda * smooth_grad,\n",
    "                                     lambda_=opt_lambda * _lambda)\n",
    "            beta_ag = soft_thresholding(x=beta_md - opt_beta * smooth_grad,\n",
    "                                        lambda_=opt_beta * _lambda)\n",
    "\n",
    "\n",
    "#             converged = _cp.all(_cp.max(_cp.abs(beta_md - beta_ag)/opt_beta) < tol).item()\n",
    "#             converged = (_cp.linalg.norm(beta_md - beta_ag, ord=_cp.infty) < (tol*opt_beta))\n",
    "#     if strongrule == True:\n",
    "#         _beta_output = _cp.zeros((p_original))\n",
    "# #         _ = _cp.argwhere(_cp.logical_not(elim)).flatten()\n",
    "# #         print(_)\n",
    "# #         for j in range(len(_)):\n",
    "# #             if j<10:\n",
    "# #                 print(j)\n",
    "# #                 print(_[j])\n",
    "# #             _beta_output[_[j]] = beta_md[j]\n",
    "# #             if j<10:\n",
    "# #                 print(_beta_output[_[j]])\n",
    "#         _beta_output[~elim] = beta_md  # this line of code can't compile\n",
    "#     else:\n",
    "#         _beta_output = beta_md\n",
    "    return k, beta_md, elim\n",
    "\n",
    "\n",
    "def UAG_logistic_SCAD_MCP_strongrule(design_matrix,\n",
    "                                     outcome,\n",
    "                                     beta_0=_cp.ones(1),\n",
    "                                     tol=1e-2,\n",
    "                                     maxit=500,\n",
    "                                     _lambda=.5,\n",
    "                                     penalty=\"SCAD\",\n",
    "                                     a=3.7,\n",
    "                                     gamma=2.,\n",
    "                                     L_convex=1.1,\n",
    "                                     add_intercept_column=True,\n",
    "                                     strongrule=True):\n",
    "    \"\"\"\n",
    "    Carry out the optimization for a fixed lambda for penanlized logistic model with strong rule.\n",
    "    \"\"\"\n",
    "    _k, _beta_md, _elim = _UAG_logistic_SCAD_MCP_strongrule(\n",
    "        design_matrix=design_matrix,\n",
    "        outcome=outcome,\n",
    "        beta_0=beta_0,\n",
    "        tol=tol,\n",
    "        maxit=maxit,\n",
    "        _lambda=_lambda,\n",
    "        penalty=penalty,\n",
    "        a=a,\n",
    "        gamma=gamma,\n",
    "        L_convex=L_convex,\n",
    "        add_intercept_column=add_intercept_column,\n",
    "        strongrule=strongrule)\n",
    "    output_beta = _cp.zeros(len(_elim))\n",
    "    output_beta[_cp.logical_not(_elim)] = _beta_md\n",
    "    return _k, output_beta\n",
    "\n",
    "\n",
    "def solution_path_logistic_strongrule(design_matrix,\n",
    "                                      outcome,\n",
    "                                      lambda_,\n",
    "                                      beta_0=_cp.ones(1),\n",
    "                                      tol=1e-2,\n",
    "                                      maxit=500,\n",
    "                                      penalty=\"SCAD\",\n",
    "                                      a=3.7,\n",
    "                                      gamma=2.,\n",
    "                                      add_intercept_column=True):\n",
    "    '''\n",
    "    Carry out the optimization for the solution path of a penalized logistic model with strong rule.\n",
    "    '''\n",
    "    #     add design matrix column for the intercept, if it's not there already\n",
    "    _design_matrix = design_matrix.copy()\n",
    "    if add_intercept_column == True:\n",
    "        if _cp.any(\n",
    "                design_matrix[:, 0] != design_matrix[0, 0]\n",
    "        ):  # check if design matrix has included a column for intercept or not\n",
    "            intercept_design = _cp.ones(N).reshape(-1, 1)\n",
    "            _design_matrix = _cp.hstack((intercept_design, _design_matrix))\n",
    "    beta_mat = _cp.empty((len(lambda_) + 1, _design_matrix.shape[1]))\n",
    "    beta_mat[0, :] = 0.\n",
    "    _lambda_max = lambda_max_logistic(_design_matrix, outcome)\n",
    "    lambda_ = _cp.hstack((_cp.array([_lambda_max]), lambda_))\n",
    "    elim = _cp.array([False] * _design_matrix.shape[1])\n",
    "    for j in range(len(lambda_) - 1):\n",
    "        _elim = _strong_rule_seq_logistic(X=_design_matrix,\n",
    "                                          y=outcome,\n",
    "                                          beta_old=beta_mat[j, :],\n",
    "                                          lambda_new=lambda_[j + 1],\n",
    "                                          lambda_old=lambda_[j])\n",
    "        elim = _cp.logical_and(elim, _elim)\n",
    "        _beta_0 = beta_mat[j, :]\n",
    "        _new_beta = _cp.zeros(_design_matrix.shape[1])\n",
    "        _new_beta[_cp.logical_not(elim)] = UAG_logistic_SCAD_MCP(\n",
    "            design_matrix=_design_matrix[:, _cp.logical_not(elim)],\n",
    "            outcome=outcome,\n",
    "            beta_0=_beta_0[_cp.logical_not(elim)],\n",
    "            tol=tol,\n",
    "            maxit=maxit,\n",
    "            _lambda=lambda_[j],\n",
    "            penalty=penalty,\n",
    "            a=a,\n",
    "            gamma=gamma,\n",
    "            add_intercept_column=False)[1]\n",
    "        beta_mat[j + 1, :] = _new_beta\n",
    "    return beta_mat[1:, :]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-08-09T22:25:17.428571Z",
     "start_time": "2022-08-09T22:25:06.494858Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import cupy as cp\n",
    "import matplotlib.markers as markers\n",
    "import matplotlib.pyplot as plt\n",
    "import timeit\n",
    "from scipy.linalg import toeplitz, block_diag\n",
    "\n",
    "# this cell is for profiling the function\n",
    "cp.random.seed(0)\n",
    "N = 1000\n",
    "SNR = 5.\n",
    "true_beta = cp.array([.5, -.5, .8, -.8] + [0] * 2000)\n",
    "X_cov = toeplitz(.6**np.arange(true_beta.shape[0]))\n",
    "X_cov = cp.asarray(X_cov)\n",
    "mean = cp.zeros(true_beta.shape[0])\n",
    "X = cp.random.multivariate_normal(mean, X_cov, N)\n",
    "X -= cp.mean(X, 0).reshape(1, -1)\n",
    "X /= cp.std(X, 0)\n",
    "intercept_design_column = cp.ones(N).reshape(N, 1)\n",
    "X_sim = cp.concatenate((intercept_design_column, X), 1)\n",
    "true_sigma_sim = cp.sqrt(true_beta.T @ X_cov @ true_beta / SNR)\n",
    "true_beta_intercept = cp.concatenate((cp.array([0.5]), true_beta))\n",
    "signal = X_sim @ true_beta_intercept + cp.random.normal(0, true_sigma_sim, N)\n",
    "y_sim = cp.random.binomial(1, cp.tanh(signal / 2) / 2 + .5)\n",
    "\n",
    "fit1 = UAG_logistic_SCAD_MCP(design_matrix=X_sim,\n",
    "                             outcome=y_sim,\n",
    "                             tol=1e-2,\n",
    "                             maxit=500,\n",
    "                             _lambda=.2,\n",
    "                             penalty=\"SCAD\",\n",
    "                             a=3.7,\n",
    "                             gamma=2.)\n",
    "\n",
    "fit2 = solution_path_logistic(design_matrix=X_sim,\n",
    "                              outcome=y_sim,\n",
    "                              tol=1e-2,\n",
    "                              maxit=500,\n",
    "                              lambda_=cp.linspace(.005, .08, 60)[::-1],\n",
    "                              penalty=\"SCAD\",\n",
    "                              a=3.7,\n",
    "                              gamma=2.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-08-09T22:26:09.668304Z",
     "start_time": "2022-08-09T22:25:17.430076Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.27 s ± 264 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "4.94 s ± 632 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit UAG_logistic_SCAD_MCP(design_matrix=X_sim, outcome=y_sim, tol=1e-2, maxit=500, _lambda=.2, penalty=\"SCAD\", a=3.7, gamma=2.)\n",
    "%timeit solution_path_logistic(design_matrix=X_sim, outcome=y_sim, tol=1e-2, maxit=500, lambda_=np.linspace(.01,.1,60)[::-1], penalty=\"SCAD\", a=3.7, gamma=2.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-08-09T22:26:09.674486Z",
     "start_time": "2022-08-09T22:26:09.670011Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 3.10810980e-01,  2.59046096e-01,  0.00000000e+00, ...,\n",
       "         0.00000000e+00,  0.00000000e+00,  0.00000000e+00],\n",
       "       [ 3.21878372e-01,  2.66695937e-01,  0.00000000e+00, ...,\n",
       "         0.00000000e+00,  0.00000000e+00,  0.00000000e+00],\n",
       "       [ 3.27929128e-01,  2.70614887e-01,  0.00000000e+00, ...,\n",
       "         0.00000000e+00,  0.00000000e+00,  0.00000000e+00],\n",
       "       ...,\n",
       "       [ 3.34991116e-01,  2.76008884e-01,  8.61094537e-02, ...,\n",
       "         0.00000000e+00, -4.85490743e-04,  0.00000000e+00],\n",
       "       [ 3.34991116e-01,  2.76008884e-01,  8.84737378e-02, ...,\n",
       "         0.00000000e+00, -9.24845347e-04, -2.02562177e-04],\n",
       "       [ 3.34991116e-01,  2.76008884e-01,  9.04812184e-02, ...,\n",
       "         0.00000000e+00, -1.48692129e-03, -6.62681425e-04]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fit2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.8"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "nbTranslate": {
   "displayLangs": [
    "*"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": true,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  },
  "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()) "
    }
   },
   "position": {
    "height": "877.844px",
    "left": "2188px",
    "right": "20px",
    "top": "120px",
    "width": "352px"
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}