{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP : Coordinate descent for LASSO Regression\n",
"\n",
"The goal of this TP is to study coordinate descent for the LASSO Regression, first theoretically and then empirically by implementing the algorithm on a dataset.\n",
"\n",
"Given a dataset $(x_i,y_i)_{i = 1 \\dots n} \\in \\mathbb{R}^d \\times \\mathbb{R}$, the LASSO regression problem is given by\n",
"$$ \\min_{(\\beta_0,\\beta) \\in \\mathbb{R}^{d+1}} \\frac{1}{2} \\sum_{i=1}^n (y_i - \\beta_0 - \\beta^T x_i)^2 + \\lambda {\\lVert}\\beta{\\rVert}_1$$\n",
"where ${\\lVert}\\beta{\\rVert}_1 = \\sum_{j=1}^d {\\lvert}\\beta_j{\\rvert}$. Note that the intercept $\\beta_0$ is not penalized by the $L^1$ norm.\n",
"\n",
"## Derivation of the optimization algorithm\n",
"\n",
"** 1) Let's assume first that the design matrix $X$ satisfies $X^TX = I$.\n",
"Prove that the lasso problem has a closed form solution given by \n",
"$$ \\hat \\beta_j = sign(\\bar \\beta_j) ({\\lvert}\\bar \\beta_j{\\rvert} - \\lambda)_+$$ where $\\bar \\beta$ is the solution of the ordinary least squares problem (without regression).**\n",
"\n",
"** 2) Now in the general case, compute the gradient of the objective function of the LASSO (we will denote by $X_j$ be the $j-th$ column of $X$).**\n",
"\n",
"** 3) Given a fixed $\\beta \\in \\mathbb{R}^d$, solve the j-th coordinate optimisation problem given by $$ \\min_{\\beta_j \\in \\mathbb{R}} \\frac{1}{2n} \\sum_{i=1}^n (y_i - \\beta_0 - \\beta^T x_i)^2 + \\lambda {\\lVert}\\beta{\\rVert}_1$$**\n",
"\n",
"** 4) Derive an iterative algorithm to solve the LASSO problem\n",
"**\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implementation\n",
"\n",
"We'll consider the polynomial regression problem from TP1, but this time we'll add L1 penalty to avoid overfitting.\n",
"\n",
"**5) Generate data $(x_i,y_i) \\in \\mathbb{R}^2$ where $x$ is a random vector and $y = f(x) + \\varepsilon$ with $f$ and $\\varepsilon$ are the function and white noise of your choice. Display the data along with $f$.**\n",
"\n",
"**6)Solve the linear regression problem for polynomials of various degrees $d$ and plot the associated solutions.**\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"** 7) Implement the coordinate descent algorithm from question 4 to solve the lasso problem. Advice : first, implement auxiliary funtions `soft_thresholding` and `lasso_step` which solve the partial problem for a given index $j$.**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**8) Plot the solution of the lasso problem for different values of $\\lambda$ and compare it to linear regression**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"anaconda-cloud": {},
"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.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}