# Algorithm

We consider linear regression model, where we are given i.i.d. pairs , , , with vectors and response variables are given by

Here is the vector of coefficients, is measurement noise with mean zero and variance . Moreover, denotes the standard scalar product in .

In matrix form, letting and denoting by the design matrix with rows , we have

Note: We are primarily interested in high-dimensional regime, where the number of parameters is larger than the number of samples , although our method applies to the classical low-dimensional setting as well.

Goal

Given response vector and design matrix , we want to construct confidence intervals for each single coefficient .
Furthermore, we are interested in testing individual null hypothesis versus the alternative , and assigning -values for these tests.

Method:

Here, we provide a simple explanation of our method. For more details and discussions, please see our paper.

Our method is based on constructing a ‘de-biased’ version of LASSO.

Let be the LASSO estimator with regularization parameter . For a matrix , define

For a suitable choice of matrix , we characterize distribution of the de-biased estimator , from which we construct asymptotically valid confidence intervals, as follows:

For and significance , we let

Here, is the quantile function of the standard normal distribution and is a consistent estimator of .

For testing the null hypothesis , we construct a two-sided -value as follows:

How to choose matrix M?

For input parameter , the de-biasing matrix is constructed via the following optimization problem:

1. for do

Let be a solution of the convex program:

where is the vector with one at the -th position and zero everywhere else.

2. Set ( Rows of are the vectors .)

In our code, the user can either give parameters and as input or let the algorithm select their values automatically.