A note relating ridge regression and OLS p-values to preconditioned sparse penalized regression
When the design matrix has orthonormal columns, "soft thresholding" the ordinary least squares (OLS) solution produces the Lasso solution [Tibshirani, 1996]. If one uses the Puffer preconditioned Lasso [Jia and Rohe, 2012], then this result generalizes from orthonormal designs to full rank designs (Theorem 1). Theorem 2 refines the Puffer preconditioner to make the Lasso select the same model as removing the elements of the OLS solution with the largest p-values. Using a generalized Puffer preconditioner, Theorem 3 relates ridge regression to the preconditioned Lasso; this result is for the high dimensional setting, p > n. Where the standard Lasso is akin to forward selection [Efron et al., 2004], Theorems 1, 2, and 3 suggest that the preconditioned Lasso is more akin to backward elimination. These results hold for sparse penalties beyond l1; for a broad class of sparse and non-convex techniques (e.g. SCAD and MC+), the results hold for all local minima.
\section{}
\begin{abstract}
When the design matrix has orthonormal columns, ``soft thresholding" the ordinary least squares (OLS) solution produces the Lasso solution \citep{tibshirani1996regression}.  If one uses the Puffer preconditioned Lasso \citep{jia2012preconditioning}, then this result generalizes from orthonormal designs to full rank designs (Theorem 1).  Theorem 2 refines the Puffer preconditioner to make the Lasso select the same model as removing  the elements of the OLS solution with the largest p-values.  
Using a generalized Puffer preconditioner, Theorem 3 relates ridge regression to the preconditioned Lasso; this result is for the high dimensional setting, $p>n$.
Where the standard Lasso is akin to forward selection \citep{efron2004least}, Theorems 1, 2, and 3 suggest that the preconditioned Lasso is more akin to backward elimination.  These results hold for sparse penalties beyond $\ell_1$;  for a broad class of sparse and non-convex techniques (e.g. SCAD and MC+), the results hold for all local minima.


\end{abstract}

\section{Introduction}

Preconditioning is a classical computational technique in numerical linear algebra that creates fast algorithms.  Several papers have recently proposed and studied the ``preconditioned" Lasso \citep{paul2008preconditioning, huang2011variable, rauhut2011sparse, jia2012preconditioning, qian2012pattern, wauthier2013comparative}. Instead of accelerating standard Lasso algorithms, preconditioning the Lasso creates a new statistical estimator that retains several properties of the Lasso while making the solution less sensitive to the correlation between the columns of the design matrix.  This paper demonstrates how penalized least squares estimators with various forms of preconditioning are equivalent to classical quantities in linear regression--the OLS estimator, OLS p-values, and ridge regression.   


 The theorems below do not make any assumptions on the design matrix beyond full rank.  Nor do they assume a linear model $Y = \ensuremath{{\mathbf{X}}} \beta + \epsilon$, or assume some conditions on an error term $\epsilon$.  Instead of studying the statistical estimation properties of preconditioned penalized least squares problems, the following theorems study the preconditioned Lasso estimators as functions of data $(\ensuremath{{\mathbf{X}}}, Y)$ that return a vector $\hat \beta$.  The theorems compare these new functions to classical ``functions" like $ols$ and ridge regression. 
 

\subsection{Preliminaries}
While the theorems below do not require the linear model, it is the linear model that motivates the estimators (i.e. functions) studied in this paper. The linear model is
\begin{equation}\label{linearModel}
Y = \ensuremath{{\mathbf{X}}} \beta + \epsilon,
\end{equation}
where $Y \in R^n$ and $\ensuremath{{\mathbf{X}}} \in R^{n \times p}$ are observed, and $\epsilon \in R^n$ is random noise satisfying $E(\epsilon) = 0$ and $E(\epsilon \epsilon') = \sigma^2 I_p$.  The goal is to estimate $\beta \in R^p$ with $\ensuremath{{\mathbf{X}}}$ and $Y$.   

Throughout the paper, we will assume that $\ensuremath{{\mathbf{X}}}$ is full rank (when $n<p$, it is full row rank). Define $\|x\|_q = (\sum_i x_i^q)^{1/q}$.
For $n>p$, define 
 \[\hat \beta^{ols} =  \arg \min_{b\in R^p} \|  Y -   \ensuremath{{\mathbf{X}}} b\|_2^2 = (\ensuremath{{\mathbf{X}}}'\ensuremath{{\mathbf{X}}})^{-1} \ensuremath{{\mathbf{X}}}' Y \in R^p\]
 as the standard OLS estimator.
\begin{definition}
Define the function $Lasso_\lambda$,
\[Lasso_\lambda(  \ensuremath{{\mathbf{X}}},   Y) = \arg \min_{b\in R^p} \|  Y -   \ensuremath{{\mathbf{X}}} b\|_2^2 + \lambda \|b\|_1.\]
\end{definition}


For $a\in R$, define $\textrm{sign}(a)$ as $-1, 0,$ or $1$, depending on whether $a$ is negative, zero, or positive.  Define $(a)^+$ as equal to $a$ if $a$ is nonnegative and equal to zero if $a$ is negative.  The soft-thresholding function is defined as 
\[t_\lambda(x) = sign(x) (|x| - \lambda)^+.\]
To apply $t_\lambda$ to a vector $x$, apply it element-wise, $[t_\lambda(x)]_j = t_\lambda(x_j)$. 

\begin{lemma}\label{classicalRelation} (Equation 3 in \citep{tibshirani1996regression})
If the design matrix $\ensuremath{{\mathbf{X}}}$ is orthonormal, 
\begin{equation} \label{classical}
Lasso_\lambda(\ensuremath{{\mathbf{X}}}, Y) = t_\lambda(\ensuremath{{\hat \beta^{ols}}}).
\end{equation}
\end{lemma}










\section{Preconditioning the Lasso}
Sections 2 and 3 study the low dimensional setting $n > p$.  For these sections, let   $\ensuremath{{\mathbf{X}}} = UDV'$ be the ``skinny" SVD; $U \in R^{n \times p}$ and $V\in R^{p \times p}$ have orthonormal columns and $D$ is a diagonal matrix.  The Puffer transform is defined as $\ensuremath{F} = U D^{-1} U'$ \citep{jia2012preconditioning}.  After preconditioning, Equation \eqref{linearModel} becomes
\begin{equation} \label{precondModel}
\ensuremath{F} Y = (\ensuremath{F} \ensuremath{{\mathbf{X}}}) \beta + \ensuremath{F} \epsilon.
\end{equation}
 While $(\ensuremath{F} \ensuremath{{\mathbf{X}}}) =U V'$ is an orthonormal matrix, it is not orthogonalized by rotating the columns as in a QR decomposition; this would correspond to \textit{right} multiplying $\ensuremath{{\mathbf{X}}}$ by some matrix.  Rotating the columns would create a new basis and make the Lasso penalize in the incorrect basis.  By \textit{left} multiplying, each row of $\ensuremath{F} \ensuremath{{\mathbf{X}}}$ is a linear combination of the rows in $\ensuremath{{\mathbf{X}}}$. 
Importantly, the regression estimators that use $(\ensuremath{F} \ensuremath{{\mathbf{X}}}, \ensuremath{F} Y)$ instead of $(\ensuremath{{\mathbf{X}}}, Y)$ still estimate the same vector $\beta$ and the Lasso penalizes in the correct basis; the original regression model in Equation \eqref{linearModel} contains the exact same $\beta$ as Equation \eqref{precondModel}. Define 
\begin{eqnarray*}
\textit{Puffer}(\ensuremath{{\mathbf{X}}}, Y) &=& (\ensuremath{F} \ensuremath{{\mathbf{X}}} , \ensuremath{F} Y) \in \ensuremath{{\mathbb{R}}}^{n \times p} \times \ensuremath{{\mathbb{R}}}^n \ \mbox{ and } \\ 
Lasso_\lambda(\textit{Puffer}(\ensuremath{{\mathbf{X}}}, Y)) &=& Lasso_\lambda(\ensuremath{F} \ensuremath{{\mathbf{X}}}, \ensuremath{F} Y). 
\end{eqnarray*}
\cite{jia2012preconditioning} showed that if the smallest singular value of $\ensuremath{{\mathbf{X}}}$ is bounded from below, then with $p$ fixed and $n\rightarrow \infty$, the preconditioned Lasso, $Lasso_\lambda(\textit{Puffer}(\ensuremath{{\mathbf{X}}}, Y))$, is sign consistent.  Importantly, the Puffer preconditioned Lasso does not require the Irrepresentable Condition from \cite{zhao2006model}.  The next theorem shows how this estimator relates to the classical estimator $\hat \beta^{ols} \in R^p$, computed on the full model.  This  extends the relationship in Lemma \ref{classicalRelation} from the case where $\ensuremath{{\mathbf{X}}}$ is orthonormal, to the case where $\ensuremath{{\mathbf{X}}}$ is full rank.
 
 









\begin{theorem}\label{theorem1}
If $\ensuremath{{\mathbf{X}}}$ is full rank and $n>p$, then
\begin{equation}\label{threshold}
Lasso_\lambda(\textit{Puffer}(\ensuremath{{\mathbf{X}}},  Y)) = t_\lambda(\hat \beta^{ols} ).
\end{equation}
\end{theorem}
  In general, the relationship in Equation \eqref{threshold} does not hold without \textit{Puffer}.
All proofs are contained in the Appendix.







\section{Correcting for the heterogeneous variability in $\hat \beta^{ols}$}

Under the linear model, 
\begin{equation}\label{olsSE}
cov(\ensuremath{{\hat \beta^{ols}}}) = \sigma^2 (\ensuremath{{\mathbf{X}}}'\ensuremath{{\mathbf{X}}})^{-1}.
\end{equation}
Define 
\[\Sigma^{ols} = cov(\ensuremath{{\hat \beta^{ols}}}). \ \mbox{ Then, } variance(\ensuremath{{\hat \beta_j^{ols}}}) = \Sigma_{jj}^{ols}.\]
If the diagonal elements of $\Sigma^{ols}$ are not all equal, then some elements of $\ensuremath{{\hat \beta^{ols}}}$ will have greater variability than others.  Classical confidence intervals and p-values account for this uncertainty.  However, the preconditioned Lasso estimator above (i.e. $t_\lambda( \ensuremath{{\hat \beta^{ols}}}) $) does not account for this known heteroskedasticity  of $\ensuremath{{\hat \beta^{ols}}}$ by applying a stronger penalty to terms with larger variance.

Classical versions of model selection test the following null hypotheses in various ways:
\[H_{0,j}: \beta_j = 0,  \ \mbox{ for } j \in 1, \dots, p.\]
Under the linear model \eqref{linearModel} and $H_{0,j}$, 
\begin{equation}\label{teststat}
Z_j = \sqrt{n} \frac{\hat \beta_j^{ols}}{\sqrt{\sigma^2 (\ensuremath{{\mathbf{X}}}'\ensuremath{{\mathbf{X}}})_{jj}^{-1}}} \stackrel{d}{\Rightarrow}N(0,1) \ \mbox{ as $n \rightarrow \infty$}.
\end{equation}
The classical ``marginal" p-values are defined as
\begin{equation}\label{pvalue}
p_j = 2(1 - \Phi(|Z_j|)), \mbox{ for $j = 1, \dots, p$
\end{equation}
where $\Phi$ is the cdf of the standard normal distribution.


\subsection{Scaling matters}


Standard Lasso packages normalize the columns of $\ensuremath{{\mathbf{X}}}$ so that they all have equal $\ell_2$ length. This ensures that each element of the Lasso estimator is equally penalized.  However, it does not ensure that the elements of the estimator are equally variable. This section  \textit{right} preconditions $\ensuremath{{\mathbf{X}}}$ with a diagonal matrix $N$, making the column lengths heterogeneous.   The column lengths are chosen so that the penalty strengths align with the heteroskedasticity of $\ensuremath{{\hat \beta^{ols}}}$, ensuring equal variability among the elements of the estimator $\hat \beta$.  

After left and right preconditioning with $\ensuremath{F}$ and $N$ respectively, the regression equation becomes
\[\ensuremath{F} Y = (\ensuremath{F} \ensuremath{{\mathbf{X}}} N)(N^{-1}\beta) + \ensuremath{F} \epsilon.\]
Define $\nu \in R^p$ as the diagonal elements of $(\ensuremath{{\mathbf{X}}}' \ensuremath{{\mathbf{X}}})^{-1}$ and let $N \in R^{ p \times p}$ be a diagonal matrix with 
$N_{jj} = \sqrt{\nu_j}. $
Because $\ensuremath{{\mathbf{X}}}$ is assumed full column rank and $N_{jj}$ is proportional to the standard error of $\ensuremath{{\hat \beta_j^{ols}}}$, $N_{jj}$ exists and is strictly positive.  This ensures that $\textrm{sign}(N^{-1}\beta) = \textrm{sign}(\beta).$ So, inferences in the transformed space carry over to the original model.


Take the SVD of $\ensuremath{{\mathbf{X}}} N = U_N D_N V_N'$. Then, define $\ensuremath{F}_N = U_N D_N^{-1} U_N'$ and 
\[\textit{Puffer}_N(\ensuremath{{\mathbf{X}}}, Y) = (\ensuremath{F}_N \ensuremath{{\mathbf{X}}} N, \ensuremath{F}_N Y) \in \ensuremath{{\mathbb{R}}}^{n \times p} \times \ensuremath{{\mathbb{R}}}^n.\]
Theorem \ref{pvalueLasso} shows that 
if $\lambda = 1.96 \sigma/\sqrt{n}$, then $Lasso_\lambda(\textit{Puffer}_N(\ensuremath{{\mathbf{X}}}, Y))$ selects the same variables as fitting the standard OLS estimator and removing any variables with p-value greater than $.05$.  


\begin{theorem} \label{pvalueLasso}
If $\ensuremath{{\mathbf{X}}}$ is full rank and $n>p$, denote
\[\hat \beta^N(\lambda) = Lasso_\lambda(\textit{Puffer}_N(\ensuremath{{\mathbf{X}}}, Y)).\]
Let $Z_j$ be the classical test statistic defined in Equation \eqref{teststat}, let $p_j$ be the classical p-value defined in Equation \eqref{pvalue}, and let $\Phi$ represent the cdf of the standard normal distribution. 
\[\hat \beta_j^N(\lambda) \ne 0 \ \  \ \Leftrightarrow  \ \ \ |Z_j| > \lambda \sqrt{n} / \sigma \ \ \ \Leftrightarrow \ \ \ p_j \le 2\left(1-\Phi(\lambda \sqrt{n} /\sigma)\right).\]

\end{theorem}

Importantly, this is an algebraic equivalence between $Lasso_\lambda(\textit{Puffer}_N(\ensuremath{{\mathbf{X}}}, Y))$ and the classical OLS p-values in Equation \eqref{pvalue}.  This requires only a full rank design matrix $\ensuremath{{\mathbf{X}}}$ and does not make any assumption on the error distribution or the elements of $\beta$.  Theorem 2 asserts nothing about the statistical reliability of these p-values.  If one wishes to use the p-value for statistical inference, then Theorem \ref{pvalueLasso} needs additional assumptions on the error term, $\epsilon$.






\subsection{Generalizing to other methods}

For simplicity, Theorems 1 and 2 are stated for the Lasso.  However, both theorems hold more generally.
For $\lambda \ge 0$ and penalty function $\ensuremath{\mbox{pen}}: \ensuremath{{\mathbb{R}}} \rightarrow \ensuremath{{\mathbb{R}}}_+$, define the function $sparse(\ensuremath{{\mathbf{X}}},Y,\lambda, \ensuremath{\mbox{pen}})$ as 
\begin{equation}
sparse(\ensuremath{{\mathbf{X}}},Y,\lambda, \ensuremath{\mbox{pen}}) = \arg \min_b \frac{1}{2}\|Y - \ensuremath{{\mathbf{X}}} b\|_2^2 + \lambda \sum_j \ensuremath{\mbox{pen}}(b_j).
\end{equation}
Whenever $\ensuremath{\mbox{pen}}$ has a thresholding function $\tilde t_\lambda$ that satisfies a version of Lemma \ref{classicalRelation} with orthonormal designs, i.e.
\[sparse(\ensuremath{{\mathbf{X}}}, Y,\lambda, \ensuremath{\mbox{pen}}) = \tilde t_\lambda(\ensuremath{{\hat \beta^{ols}}}) \ \mbox{ for orthonormal } \ensuremath{{\mathbf{X}}},\]
then modified versions of Theorems 1 and 2 also apply for this penalty:
\begin{eqnarray*}
&sparse(\textit{Puffer}(\ensuremath{{\mathbf{X}}}, Y),\lambda, \ensuremath{\mbox{pen}}) &= \tilde t_\lambda(\ensuremath{{\hat \beta^{ols}}})  \\
&\left[ sparse(\textit{Puffer}_N(\ensuremath{{\mathbf{X}}}, Y),\lambda, \ensuremath{\mbox{pen}})\right]_j &= \tilde t_\lambda(  \sigma Z_j / \sqrt{n} ).
\end{eqnarray*}
For example, $\ensuremath{\mbox{pen}}$ could be an $\ell_q$ penalty for $q \in [0,1]$, the elastic net penalty, or a concave penalty such as SCAD or MC+ \citep{fan2001variable, zhang2010nearly}.  After preconditioning, a broad class of penalties  select the same sequence of models as the Lasso.



\section{Relating to ridge regression}

For $p > n$, take the ``skinny" SVD of 
$\ensuremath{{\mathbf{X}}} = UDV'$, where $U \in R^{n \times n}, V \in R^{p \times n}, D \in R^{n \times n}$.  Consider a generalized Puffer transformation
\[\ensuremath{F}_\tau = U(D^2 + \tau I)^{-1/2}U' \ \mbox{ and } \textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y) = (\ensuremath{F}_\tau \ensuremath{{\mathbf{X}}}, \ensuremath{F}_\tau Y).\]
Theorem \ref{mainresult} relates $sparse(\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y), \lambda, \ensuremath{\mbox{pen}})$  to  the ridge estimator \citep{hoerl1970ridge}.  For $\tau > 0$, the ridge estimator is 
\begin{eqnarray}
\ensuremath{{\ensuremath{\hat \beta_{ridge}(\tau)     }}} &=& \arg \min_b \|Y - \ensuremath{{\mathbf{X}}} b\|_2^2 + \tau \|b\|_2^2 \label{ridge} \\
 &=& (\ensuremath{{\mathbf{X}}}'\ensuremath{{\mathbf{X}}} + \tau I)^{-1} \ensuremath{{\mathbf{X}}}' Y. \nonumber
\end{eqnarray}
Define $\hat \beta_{ridge}(0)$ as the Moore-Penrose estimator 
\begin{eqnarray*}
\hat \beta_{ridge}(0) &=&\arg \min_{b: \ensuremath{{\mathbf{X}}} b = Y}  \|b\|_2^2 \\
 &=& (\ensuremath{{\mathbf{X}}}'\ensuremath{{\mathbf{X}}})^{+} \ensuremath{{\mathbf{X}}}' Y,
\end{eqnarray*}
where $(\ensuremath{{\mathbf{X}}}'\ensuremath{{\mathbf{X}}})^{+}$ is the Moore-Penrose pseudoinverse, $VD^{-2}V'$.\footnote{In what follows, replace any matrix inversion with the Moore-Penrose pseudoinverse if $\tau =0$ and the true inverse does not exist.}

Define $\ensuremath{\mathscr{P}_\tau}: \ensuremath{{\mathbb{R}}}^p \rightarrow \ensuremath{{\mathbb{R}}}^p$ as
\begin{eqnarray}
\ensuremath{\mathscr{P}_\tau}(v) &=& \ensuremath{{\mathbf{X}}}'(\ensuremath{{\mathbf{X}}}\X' + \tau I)^{-1} \ensuremath{{\mathbf{X}}} v. \label{proj} 
\end{eqnarray}
For $\tau = 0$, $\ensuremath{\mathscr{P}_0}$ projects onto the row space of $\ensuremath{{\mathbf{X}}}$.  Under the linear model (Equation \ref{linearModel}), $\ensuremath{{\ensuremath{\hat \beta_{ridge}(\tau)     }}}$ is an unbiased estimator of $\ensuremath{\mathscr{P}_\tau}(\beta)$.

The following theorem assumes that $sparse$ uses a penalty function satisfying the following assumptions.
\begin{definition} \label{sparsepen}
Define a function $\ensuremath{\mbox{pen}}$ as a \textbf{regular sparse penalty} if it is 
\begin{enumerate}
\item non-differentiable at zero and differentiable everywhere else;
\item symmetric, $\ensuremath{\mbox{pen}}(a) = \ensuremath{\mbox{pen}}(-a)$; 
\item monotonically increasing away from zero, $\ensuremath{\mbox{pen}}(a) \ge \ensuremath{\mbox{pen}}(b)$ if $|a| > |b|$; 
\item Lasso derivative in the neighborhood of zero,
\[\lim_{x \rightarrow 0} |\ensuremath{\mbox{pen}}'(x)| = 1,\] 
where $\ensuremath{\mbox{pen}}'$ is the first derivative of $\ensuremath{\mbox{pen}}$.
\end{enumerate}
\end{definition}
This includes the Lasso, elastic net, SCAD, and MC+.  However, $\ell_q$ penalties fail condition (4) when $q < 1$.  Such penalties have an unbounded derivative in the neighborhood of zero which creates discontinuities in the solution path;  previous research has also excluded such penalties (e.g. \cite{zhang2012general, loh2013regularized}).

Theorem \ref{mainresult} says that if $\ensuremath{\mbox{pen}}$ is a regular sparse penalty, then any local minimum for the objective function in $sparse(\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y), \lambda, \ensuremath{\mbox{pen}} )$, transformed by $\ensuremath{\mathscr{P}_\tau}$, is close to the ridge estimator $\ensuremath{{\ensuremath{\hat \beta_{ridge}(\tau)     }}}$.  Moreover, $\lambda$ controls the distance between these estimators.  

\begin{theorem} \label{mainresult}
Let $\ensuremath{\mbox{pen}}$ be a regular sparse penalty (Definition \ref{sparsepen}) and let $p\ge n$.  Let 
\[\hat \beta = sparse(\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y), \lambda, \ensuremath{\mbox{pen}} ).\] 
If $\hat \beta_j \ne 0$, then
\[\ensuremath{{\ensuremath{\hat \beta_{ridge,j}(\tau)     }}} - \ensuremath{\mathscr{P}_\tau}(\hat \beta)_j = \lambda \ensuremath{\mbox{pen}}'(\hat \beta_j),\]
where $\ensuremath{\mbox{pen}}'$ is the derivative of $\ensuremath{\mbox{pen}}$.  If $\hat \beta_j = 0$, then 
\[|\ensuremath{{\ensuremath{\hat \beta_{ridge,j}(\tau)     }}} - \ensuremath{\mathscr{P}_\tau}(\hat \beta)_j| \le \lambda.\]
Moreover, these results still hold if $\hat \beta$ is any local minimizer of the objective function for $sparse(\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y), \lambda, \ensuremath{\mbox{pen}} )$.
\end{theorem}

Importantly, $sparse$ has been computed with the preconditioned data, $\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y)$, while $\ensuremath{{\ensuremath{\hat \beta_{ridge}(\tau)     }}}$ is the traditional estimator computed with the original data.  When $\lambda$ is small, these two estimators are aligned in the row space of $\ensuremath{{\mathbf{X}}}$.  Determining the statistically appropriate scale of $\lambda$ requires some care because after preconditioning, the scale of the problem changes; $\|\ensuremath{{\mathbf{X}}}\|_F^2 = O(np)$, but $\|\ensuremath{F}_\tau \ensuremath{{\mathbf{X}}}\|_F^2 = O(n)$.  A forthcoming revision to \cite{jia2012preconditioning},  shows that $sparse(\textit{Puffer}_0(\ensuremath{{\mathbf{X}}}, Y), \lambda, \| \cdot \|_1)$ is sign consistent when $\min_j \beta_j$ is larger than $\log n / \sqrt{n}$ and 
\[\lambda = O\left(\left(\frac{\log n \log p}{p} \right)^{1/2}\right).\]
In the high dimensional setting, this $\lambda$ is clearly converging to zero.

If Theorem 3 held without $\ensuremath{\mathscr{P}_\tau}$, then it would say that $Lasso_\lambda(\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y)) = t_\lambda(\ensuremath{{\ensuremath{\hat \beta_{ridge}(\tau)     }}})$, which would make a clear analogy to backward elimination.  However, the inclusion of $\ensuremath{\mathscr{P}_\tau}$ stains the analogy to backward elimination. In fact, it is not even true that $\ensuremath{\mathscr{P}_\tau}\left(Lasso_\lambda(\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y))\right) = t_\lambda(\ensuremath{{\ensuremath{\hat \beta_{ridge}(\tau)     }}})$; the left side is in the row space of $\ensuremath{{\mathbf{X}}}$, but the right side is not. That said,
typical algorithms to compute the Lasso  solution path (e.g. \cite{efron2004least}) start at $\lambda =\infty$ with $Lasso_{\lambda= \infty}(\ensuremath{{\mathbf{X}}}, Y) = 0$ and decrease $\lambda$, increasing the number of terms in the model.  This resembles forward selection.
The results of Theorem 3 are ``backwards" in the sense that for $\lambda \rightarrow 0$, $\ensuremath{\mathscr{P}_\tau}(Lasso_\lambda(\textit{Puffer}_\tau(\ensuremath{{\mathbf{X}}}, Y))) \rightarrow \ensuremath{{\ensuremath{\hat \beta_{ridge}(\tau)     }}}$.

Suppose $\hat \beta^{(1)}$ and $\hat \beta^{(2)}$ are both local minima of $sparse(\textit{Puffer}_0(\ensuremath{{\mathbf{X}}}, Y),\lambda, \ensuremath{\mbox{pen}})$ for a regular sparse penalty $\ensuremath{\mbox{pen}}(x)$ that is concave on $\{x:x>0\}$.  By concavity and the definition of regular sparse penalty, it follows that $|\ensuremath{\mbox{pen}}'(x)| \le 1$ for $x\ne0$.  So, the triangle inequality around $\hat \beta_{ridge,j}(0)$ yields
\begin{equation}\label{closeMins}
\ensuremath{\mathscr{P}_0}( \hat \beta^{(1)}_j  - \hat \beta^{(2)}_j ) \le 2 \lambda.
\end{equation}
So after preconditioning, local minima are exceedingly similar in the row space of $\ensuremath{{\mathbf{X}}}$.  Moreover, even if $\hat \beta^{(1)}$ and $\hat \beta^{(2)}$ are (local) minima from different penalty functions, then Equation \ref{closeMins} holds so long as (i) both $\ensuremath{\mbox{pen}}$ functions are regular and concave and (ii) both are computed with the same tuning parameter $\lambda$.\footnote{If they have different tuning parameters $\lambda_1$ and $\lambda_2$, then the bound $2 \lambda$ is replaced by $\lambda_1 + \lambda_2$.}  In general, $\beta$ is not identifiable when $p>n$; only the projection of $\beta$ into the row space of $\ensuremath{{\mathbf{X}}}$ is identifiable \citep{shao2012estimation}.  This suggests that, after preconditioning, it is difficult statistically distinguish the difference between local minima or the difference between penalty functions.



\section{Discussion}



Several previous papers have studied different preconditioners for the Lasso \citep{paul2008preconditioning, huang2011variable, rauhut2011sparse, jia2012preconditioning, qian2012pattern, wauthier2013comparative}.  
This paper connects two types of preconditioning techniques to the classical OLS solution.  When performing model selection in the classical setting of $n>>p$, the marginal p-values from OLS are typically considered more informative than the absolute sizes of the elements in $\hat \beta^{ols}$; the p-values account for the potentially heterogeneous standard errors across $\hat \beta^{ols}$.  This suggests that $Lasso_\lambda(\textit{Puffer}_N(\ensuremath{{\mathbf{X}}}, Y))$ should be preferred to $Lasso_\lambda(\textit{Puffer}(\ensuremath{{\mathbf{X}}}, Y))$.  However, classical intuitions also suggest that two variables might have statistically insignificant p-values because these variables are correlated with each other(see Section 10.1 in \cite{weisberg2014applied}).  As such, a backward procedure should have multiple steps.  On each step, remove the variable with the largest p-value and refit the OLS with the remaining predictors.  Neither of the preconditioning techniques above  creates a Lasso solution path that is equivalent to this multi-step approach.  A preconditioner that is designed to match this path must be a function of $Y$ and $\lambda$, thus becoming much more complicated. 

 
 The Lasso (without preconditioning) is akin to forward selection \citep{efron2004least}.  Classical methods of forward selection are not model selection consistent, unless the columns of the design matrix are only  weakly correlated \citep{tropp2007signal}.  Similarly, the Lasso is not sign consistent unless the design matrix satisfies the Irrepresentable Condition \citep{zhao2006model}.  After preconditioning with the (generalized) Puffer transformation, Theorems 1, 2, and 3 show that  the Lasso is akin to backward elimination.   This preconditioner makes the design orthogonal when $n>p$, trivially satisfying all consistency conditions (e.g. Irrepresentable Condition, RIP, etc.).  As such, Theorem 1 implies that a one step backward elimination is also sign consistent.  
 
This suggests that backward procedures are sign consistent when  forward procedures are not.
 However, backward procedures are not a panacea. They will become unstable whenever the OLS p-values are incorrect (e.g. when $p$ is large compared to $n$  and the CLT does not hold for the test statistic $Z_j$ in Equation \eqref{teststat}).





\bibliographystyle{plainnat}


2014-12-04T02:13:57.000
1411
1411.7405
en
https://arxiv.org/abs/1411.7405
When the design matrix has orthonormal columns, "soft thresholding" the ordinary least squares (OLS) solution produces the Lasso solution [Tibshirani, 1996]. If one uses the Puffer preconditioned Lasso [Jia and Rohe, 2012], then this result generalizes from orthonormal designs to full rank designs (Theorem 1). Theorem 2 refines the Puffer preconditioner to make the Lasso select the same model as removing the elements of the OLS solution with the largest p-values. Using a generalized Puffer preconditioner, Theorem 3 relates ridge regression to the preconditioned Lasso; this result is for the high dimensional setting, p > n. Where the standard Lasso is akin to forward selection [Efron et al., 2004], Theorems 1, 2, and 3 suggest that the preconditioned Lasso is more akin to backward elimination. These results hold for sparse penalties beyond l1; for a broad class of sparse and non-convex techniques (e.g. SCAD and MC+), the results hold for all local minima.
Machine Learning (stat.ML); Methodology (stat.ME)
A note relating ridge regression and OLS p-values to preconditioned sparse penalized regression
Qwen/Qwen-72B
1. YES
2. YES