algorithm_bag.tex

\documentclass[letterpaper,11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath, amssymb, setspace, esint}
\usepackage{algorithm}
\usepackage{graphicx}
\usepackage{placeins}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{hdim_macros}
\allowdisplaybreaks[1]

% \makeatletter
% \newcommand\blx@unitmark{23sp}
% \makeatother
%
% \newcommand{\LOne}[1]{ \lvert \lvert #1 \rvert \rvert_1 }
% \newcommand{\LTwoSqr}[1]{ \lvert \lvert #1 \rvert \rvert_2^2 }
% \newcommand{\LInf}[1]{ \lvert \lvert #1 \rvert \rvert_{\infty} }
%
% \newcommand\tikzmark[1]{%
%   \tikz[remember picture,overlay]\node[inner sep=2pt] (#1) {};}
% \newcommand\DrawBox[3][]{%
%   \tikz[remember picture,overlay]\draw[#1] ([xshift=-3.5em,yshift=7pt]#2.north west) rectangle (#3.south east);}
%
% \algnewcommand\algorithmicinput{\textbf{Input:}}
% \algnewcommand\Input{\item[\algorithmicinput]}
%
% \algnewcommand\algorithmicoutput{\textbf{Output:}}
% \algnewcommand\Output{\item[\algorithmicoutput]}
%
% \algdef{SE}[DOWHILE]{Do}{doWhile}{\algorithmicdo}[1]{\algorithmicwhile\ #1}%

\begin{document}

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{DG ( Duality Gap ) }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{a}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Current $\beta$ }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }\tikzmark{b}
    \State $\epsilon \gets X \beta - Y$
    \State $f_{\beta} \gets \LTwoSqr{ \epsilon } + \lambda \LOne{ \beta }$\Comment{Primal Objective function}
    \State $\alpha \gets \frac{\lambda}{ \LInf{ 2 X^T \epsilon } }$
    \State $\alpha_0$ $\gets Y^T \epsilon$
    \State $\mathcal{S} \gets \min \{ \max \{ \alpha, \alpha_0 \}, - \alpha \}$\Comment{Dual Point}
    \State $\widetilde{\nu} \gets \frac{-2 \mathcal{S} }{ \lambda } \epsilon + \frac{2}{\lambda} Y$
    \State $d_{\nu} \gets \frac{1}{4} \lambda^2 \LTwoSqr{ \widetilde{\nu} } - \LTwoSqr{ Y }$\Comment{Dual Objective function}
  \end{algorithmic}
  \Return $f_{\beta} + d_{\nu}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{DGT ( Duality Gap Target ) }
  \begin{algorithmic}[1]
    \Statex
    \Input\tikzmark{c}
    \Statex $\gamma \in \mathbb{R}$ \Comment{ \dots }
    \Statex $C \in \mathbb{R}$  \Comment{ \dots }
    \Statex $r_{Stats It} \in \mathbb{N}$  \Comment{ Index of the current grid element ( outer loop iteration number ) }
    \Statex $n \in \mathbb{N}$  \Comment{ Number of rows in the design matrix $X \in \mathbb{R}^{ n \times p}$ }\tikzmark{d}
    \State dgt $\gets \gamma C^2 \frac{ r_{Stats It}^2 }{ n }$
  \end{algorithmic}
  \Return dgt
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{$f_{\beta}$ }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{e}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Current $\beta$ }\tikzmark{f}
    \State $f \gets X \beta - Y$.
  \end{algorithmic}
  \Return $\LTwoSqr{ f }$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{$f_{\widetilde{ \beta }}$ }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{g}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ The $k$'th $\beta$ vector }
  \Statex $\beta' \in \mathbb{R}^n$  \Comment{ The $k-1$'th $\beta$ vector }
  \Statex $L \in \mathbb{R}$  \Comment{ The current Lipschitz constant, as computed by backtracking line search }\tikzmark{h}
    \State $f \gets X \beta - Y$.
    \State $t_0 \gets \LTwoSqr{ f }$
    \State $\nabla f \gets 2 X^T f$
    \State $\Delta_{\beta} \gets \beta - \beta'$
    \State $t_1 \gets \nabla f^T \Delta_{\beta}$
    \State $t_2 \gets \frac{L}{2} \LTwoSqr{ \Delta_{\beta} }$
  \end{algorithmic}
  \Return $t_0 + t_1 + t_2$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{$\tau$ ( Matrix-wise Soft-Thresholding / Proximal Operator ) }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{i}
  \Statex $X \in \mathbb{R}^{n \times m} $ \Comment{ An arbitrary matrix }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ The thresholding parameter }\tikzmark{j}
    \State $\widetilde{X} \gets X$ \Comment{Make a copy of $X$.}
    \For { $\widetilde{x}_{i,j} \in \widetilde{X}$ }
      \State $\widetilde{x}_{i,j} \gets \text{sign}( \widetilde{x}_{i,j} ) \left( \lvert \widetilde{x}_{i,j} \rvert - \lambda \right)^{+}$
    \EndFor
  \end{algorithmic}
  \Return $\widetilde{X}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{ISTA with backtracking line search and duality gap convergence criteria}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Starting vector }
  \Statex $L_0 \in \mathbb{R}$  \Comment{ Initial Lipschitz constant, used by backtracking line search }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }
  \Statex $\eta \in \mathbb{R}$  \Comment{ Step size when updating Lipschitz constant }
  \Statex $\mathcal{D} \in \mathbb{R}$  \Comment{ Duality gap target }\tikzmark{l}
    \State $\widetilde{\beta} \gets \beta$ \Comment{ Make a copy of $\beta$ that will be updated during back tracking.}
      \Do
        \State $ \widetilde{\beta} \gets \tau( \beta - \frac{1}{L} \nabla f( X, Y, \widetilde{\beta}, L ) )$
        \While{ $f_{\beta} ( X, Y, \widetilde{\beta} ) > f_{\widetilde{\beta}}( X, Y, \widetilde{\beta}, \beta_, L) $ }
          \State $L \gets \eta L$
          \State $ \widetilde{\beta} \gets \tau( \beta - \frac{1}{L} \nabla f( X, Y, \beta ) )$
        \EndWhile
        \State $\beta \gets \tau( \beta - \frac{1}{L} \nabla f( X, Y, \beta, L ) )$ \Comment{ Update $\beta$ once $L$ is sufficiently large.}
      \doWhile{ DG $( X, Y, \beta, \lambda ) > \mathcal{D}$ }\\
  \end{algorithmic}
  \Return $\beta$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{Coordinate Descent with duality gap convergence criteria}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Starting vector }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }
  \Statex $\mathcal{D} \in \mathbb{R}$  \Comment{ Duality gap target }\tikzmark{l}
    \State $\widetilde{\beta} \gets \beta$ \Comment{ Make a copy of $\beta$ }
      \Do
        \For{ $i \in 1, 2, \dots, p$ }
          \State $t \gets \frac{ \lambda }{ 2 \LTwoSqr{ X_i } }$ \Comment{ Scale grid element by norm of the i'th column of design matrix }
          \State $X_{-i} \gets X_{ \forall j \neq i}$ \Comment{ Take all columns of design matrix not equal to $i$ }
          \State $\widetilde{\beta}_{-i} \gets \widetilde{\beta}_{ \forall j \neq i}$ \Comment{ Take all elements of predictors vectors not equal to $i$ }
          \State $r \gets \frac{ X_i^T\left( Y - X_{-i} \widetilde{\beta}_{-i}\right) }{ \LTwoSqr{ X_i } }$ \Comment{ Compute the scaled residual }
          \State $\widetilde{\beta}_i \gets \tau \left( r, t \right)$ \Comment{ Update the i'th element of Beta }
        \EndFor
      \doWhile{ DG $( X, Y, \widetilde{\beta}, \lambda ) > \mathcal{D}$ }\\
  \end{algorithmic}
  \Return $\widetilde{\beta}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{Coordinate Descent with Lazy Evaluation}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Starting vector }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }
  \Statex $\mathcal{D} \in \mathbb{R}$  \Comment{ Duality gap target }\tikzmark{l}
    \State $\widetilde{\beta} \gets \beta$ \Comment{ Make a copy of $\beta$ }
    \State $R \gets Y - X \widetilde{\beta}$ \Comment{ Initialize Intermediary Residual }
      \Do
        \For{ $i \in 1, 2, \dots, p$ }
          \State $t \gets \frac{ \lambda }{ 2 \LTwoSqr{ X_i } }$ \Comment{ Scale grid element by norm of the i'th column of design matrix }
          \If{ $ \widetilde{\beta}_i \neq 0 $ }{
            $R \gets R + X_i \widetilde{B}_i$
          }
          \EndIf
          \State $\widetilde{\beta}_i \gets \tau \left( \frac{X_i^T R}{ \LTwoSqr{ X_i } }, t \right)$ \Comment{ Update the i'th element of Beta }
          \If{ $ \widetilde{\beta}_i \neq 0 $ }{
            $R \gets R - X_i \widetilde{B}_i$
          }
          \EndIf
        \EndFor
      \doWhile{ DG $( X, Y, \widetilde{\beta}, \lambda ) > \mathcal{D}$ }\\
  \end{algorithmic}
  \Return $\widetilde{\beta}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{Coordinate Descent with standardized data}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The standardized $\bar{X_i} = 0, \sigma_{X_i} = 1$ design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Starting vector }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }
  \Statex $\mathcal{D} \in \mathbb{R}$  \Comment{ Duality gap target }\tikzmark{l}
    \State $\widetilde{\beta} \gets \beta$ \Comment{ Make a copy of $\beta$ }
      \Do
        \For{ $i \in 1, 2, \dots, p$ }
          \State $t \gets \frac{ \lambda }{ 2 n }$ \Comment{ Scale grid element by norm of the i'th column of design matrix }
          \State $X_{-i} \gets X_{ \forall j \neq i}$ \Comment{ Take all columns of design matrix not equal to $i$ }
          \State $\widetilde{\beta}_{-i} \gets \widetilde{\beta}_{ \forall j \neq i}$ \Comment{ Take all elements of predictors vectors not equal to $i$ }
          \State $r \gets \frac{ X_i^T\left( Y - X_{-i} \widetilde{\beta}_{-i}\right) }{ n }$ \Comment{ Compute the scaled residual }
          \State $\widetilde{\beta}_i \gets \tau \left( r, t \right)$ \Comment{ Update the i'th element of Beta }
        \EndFor
      \doWhile{ DG $( X, Y, \widetilde{\beta}, \lambda ) > \mathcal{D}$ }\\
  \end{algorithmic}
  \Return $\widetilde{\beta}$
\end{algorithm}
\FloatBarrier

The next algorthim is a modified version of Coordinate Descent that seeks to reduce
redunant computations as much as possible.
This algorthim relies on the fact that many computation required by
Coordinate Descent can be broken up into constant and non-constant parts. The
constant parts of the computation can be performed ahead of time and stored for later use.

Of particular note is the scaled residual computation, which when written down naively reads:

\begin{center}
$ r \gets \frac{ X_i^T\left( Y - X_{-i} \widetilde{\beta}_{-i}\right) }{ \LTwoSqr{ X_i } } $.
\end{center}

Which we can re-write as,

\begin{center}
$ r \gets \frac{ X_i^T Y }{ \LTwoSqr{ X_i } } - \frac{ X_i^T X_{-i} }{ \LTwoSqr{ X_i } } \widetilde{\beta}_{-i}$.
\end{center}

Note that since the design matrix $X$ and the vector of predictors $Y$ are fixed,
 the terms $ \frac{ X_i^T Y }{ \LTwoSqr{ X_i } } $ and $\frac{ X_i^T X_{-i} }{ \LTwoSqr{ X_i } }$
do not change as the values of $\widetilde{\beta}$ are updated. Our strategy will be to
compute these values for each column of $X$ and store them in an array of size $p$,
from which they will be access as $\widetilde{B}$ is updated.

Note for this algorthim we establish the convention that array of a given data type
will be declared as follows:
\begin{center}
( \textit{type} )[ \textit{\# elements in array} ]
\end{center}

As an example an array of real numbers numbers of size $n \in \mathbb{N}$
would be written as:
\begin{center}
( $\mathbb{R}$ )[ $n$ ]
\end{center}

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{Coordinate Descent with Minimal Data Copying}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Starting vector }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }
  \Statex $\mathcal{D} \in \mathbb{R}$  \Comment{ Duality gap target }\tikzmark{l}
    \State $\gimel \gets (\mathbb{R})[ p ]$ \Comment{ Initialize array of size p to hold threshold parameters }
    \State $p_1 \in (\mathbb{R})[ p ]$ \Comment{ Blank array for part of residual computation }
    \State $p_2 \in (\mathbb{R}^{ 1 \times p})[ p ]$ \Comment{ Blank array to row vectors of size p which will be used for part of residual computation }
    \For{ $i \in 1, 2, \dots, p$ }
      \State $\beth \gets \frac{1}{\LTwoSqr{X_i}}$
      \State $\gimel [ i ] \gets \frac{1}{2} \beth$
      \State $p_1[ i ] \gets \beth X_i^T Y$
      \State $p_2[ i ] \gets \beth X_i^T X$
    \EndFor
    \State $\widetilde{\beta} \gets \beta$ \Comment{ Make a copy of $\beta$ }
      \Do
        \For{ $i \in 1, 2, \dots, p$ }
          \State $\widetilde{\gamma} \gets \widetilde{\beta}_j$ \textbf{if} $j \neq i$ \textbf{else} 0 \Comment{Copy all of beta expect i'th element which is assigned to 0}
          \State $r \gets p_1[ i ] - p_2[ i ]\widetilde{\gamma}$ \Comment{ Compute the scaled residual }
          \State $t \gets \lambda \gimel [ i ]$ \Comment{Compute threshold parameter}
          \State $\widetilde{\beta}_i \gets \tau \left( r, t \right)$ \Comment{ Update the i'th element of Beta }
        \EndFor
      \doWhile{ DG $( X, Y, \widetilde{\beta}, \lambda ) > \mathcal{D}$ }\\
  \end{algorithmic}
  \Return $\widetilde{\beta}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{FISTA with backtracking line search and duality gap convergence criteria}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Starting vector }
  \Statex $L_0 \in \mathbb{R}$  \Comment{ Initial Lipschitz constant, used by backtracking line search }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }
  \Statex $\eta \in \mathbb{R}$  \Comment{ Step size when updating Lipschitz constant }
  \Statex $\mathcal{D} \in \mathbb{R}$  \Comment{ Duality gap target }\tikzmark{l}
  \Statex $y_{k-1} \in \mathbb{R}^b$ \Comment{ Beta vector from previous iteration of FISTA}
  \Statex $x_{k-1} \in \mathbb{R}^b$ \Comment{ Intermediary vector from previous iteration of FISTA}
    \State $y_k \gets \beta$
      \Do
        \State $y_{k-1} \gets x_k$
        \State $t_k \gets 0$
        \State $ \widetilde{y_k} \gets \tau( \beta - \frac{1}{L} \nabla f( X, Y, y_k ) )$
        \While{ $f_{\beta} ( X, Y, \widetilde{y_k} ) > f_{\widetilde{\beta}}( X, Y, \widetilde{y_k}, y_k, L) $ }
          \State $L \gets \eta L$
          \State $\widetilde{y_k} \gets \tau( \beta - \frac{1}{L} \nabla f( X, Y, \beta ) )$
        \EndWhile
        \State $x_{k-1} \gets x_k$
        \State $x_k \gets \tau( \beta - \frac{1}{L} \nabla f( X, Y, \widetilde{y_k} ) )$
        \State $t_{k+1} = \frac{ \left( 1 + \sqrt{ 1 + 4 t_k^2} \right) }{ 2 }$
        \State $y_k \gets x_k + \frac{ \left( t_k - 1 \right) }{ t_{k+1} } \left( x_k - x_{k-1} \right)$
      \doWhile{ DG $( X, Y, \beta, \lambda ) > \mathcal{D}$ }\\
  \end{algorithmic}
  \Return $y_k, y_{k-1}, x_{k-1}, t_{k+1}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{ $\lambda$GRID }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{i}
  \Statex $X \in \mathbb{R}^{n \times m} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^{n} $ \Comment{ The vector of predictors }
  \Statex $M \in \mathbb{N} $ \Comment{ The number of grid elements required }\tikzmark{j}
    \State $ r_{max} \gets 2 \lvert \lvert X^T Y \rvert \rvert_{\infty}$
    \State $ r_{min} \gets \frac{1}{1000} r_{max}$
    \State $ \Delta_r \gets \left( r_{max} - r_{min} \right)$
    \State Let $\Lambda \in \mathbb{R}^M$ \Comment{Initialize empty array of size M}
    \For { $i \in [ 1, 2, \dots, M ]$ }
      \State $\delta_l \gets \Delta_r \frac{ i }{ M - 1 } + r_{min}$ \Comment{ Compute linear step }
      \State $\Lambda[i] \gets 10^{\delta_l}$ \Comment{ Convert to logarithmic step }
    \EndFor
  \end{algorithmic}
  \Return $\Lambda$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{ SCC: Stats Continutation Condition }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{i}
  \Statex $C \in \mathbb{R}$ \Comment{ The design matrix }
  \Statex $statsIt \in \mathbb{N}$ \Comment{ The vector of predictors }
  \Statex $\lambda \in \mathbb{R}$ \Comment{ Current grid element }
  \Statex $\Lambda \in \mathbb{R}^M$ \Comment{ Vector of grid elements }
  \Statex $X \in \mathbb{R}^{ n \times p }$ \Comment{ Vector of grid elements }
  \Statex $\beta_s \in \mathbb{R}^{ n \times M }$ \Comment{ Betas matrix }\tikzmark{j}
    \State condition $\gets$ false
    \For { $i \in [ 1, 2, \dots, statsIt ]$ }
      \State $r_k \gets \Lambda_k$
      \State $\Delta_{\beta} \gets \beta_{statsIt} - \beta_i$
      \State check $\gets \frac{ n \LInf{ \Delta_{\beta} } }{ r_{statsIt} + r_k }$
      \State condition $\gets$ condition $\And$ ( check $\leq C$ )
    \EndFor
  \end{algorithmic}
  \Return condition
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{FOS}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^n$  \Comment{ Starting vector }
  \Statex $L_0 \in \mathbb{R}$  \Comment{ Initial Lipschitz constant, used by backtracking line search }
  \Statex $M \in \mathbb{M}$  \Comment{ Number of grid elements }
  \Statex $\eta \in \mathbb{R}$  \Comment{ Step size when updating Lipschitz constant }
  \Statex $C \in \mathbb{R}$
  \Statex $\gamma \in \mathbb{R}$\tikzmark{l}
    \State $\widetilde{X} \gets \frac{1}{\sigma_X}\left( X - \mu_X \right)$. \Comment{Normalize X to mean 0 and standard deviation 1.}
    \State $\widetilde{Y} \gets \frac{1}{\sigma_Y} \left( Y - \mu_Y \right)$. \Comment{Normalize Y.}
    \State $\Lambda \gets \lambda$GRID$( X, Y, M )$ \Comment{Initialize grid elements}
    \State $\beta_s \in \mathbb{R}^{ n \times m } = 0_{n,m}$. \Comment{Initialize matrix of Betas to zero matrix}
      \While { statsCont $\And$ ( statsCont $<$ M ) }
        \State $stats_{It} \gets stats_{It} + 1$
        \State $\widetilde{\beta} \gets \beta_{k-1}$ \Comment{Initialize old beta vector with the k - 1'th Column of the Betas matrix.}
        \State $r_{statsIt} \gets \Lambda_k$ \Comment{ Extract the k'th grid element. }
          \If{ $ DG( X, Y, \beta_k, r_{statsIt} ) \leq DGT( \gamma, C, r_{statsIt}, n )$}
            \State $\beta_k \gets \beta_{k-1}$
          \Else
            \State $\beta_k \gets \text{ISTA}( X, Y, \beta_{k-1}, L_0, r_{statsIt}, \eta, gap )$
          \EndIf
          \State $statsCont \gets$ SCC $( C, statsIt, r_{statsIt}, \Lambda, X, \beta_s )$
      \EndWhile
  \end{algorithmic}
  \Return $\beta_{statsIt-1}, \Lambda_{statsIt}, statsIt$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{DP ( Dual Point ) }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{a}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^p$  \Comment{ Current $\beta$ }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }\tikzmark{b}
    \State $R \gets Y - X \beta $
    % \State $f_{\beta} \gets \LTwoSqr{ \epsilon } + \lambda \LOne{ \beta }$\Comment{Primal Objective function}
    \State $\alpha \gets \frac{1}{ \LInf{ X^TR } }$
    \State $s \gets \min \{ \max \{ \frac{Y^TR}{\lambda\LTwoSqr{R}}, -\alpha \}, \alpha \}$
    % \State $\nu \gets sR$
    % \State $d_{\nu} \gets \frac{1}{4} \lambda^2 \LTwoSqr{ \widetilde{\nu} } - \LTwoSqr{ Y }$\Comment{Dual Objective function}
  \end{algorithmic}
  \Return $sR$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{DG2 ( Duality Gap for Problem~\ref{eq:lasso_half} ) }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{a}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^p$  \Comment{ Current primal point }
  \Statex $\nu \in \mathbb{R}^n$  \Comment{ Current dual point }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }\tikzmark{b}
    \State $f_{\beta} \gets \frac{1}{2}\LTwoSqr{ Y - X \beta } + \lambda \LOne{ \beta }$\Comment{Primal Objective function}
    \State $d_{\nu} \gets \frac{1}{2} \LTwoSqr{Y} - \frac{\lambda^2}{2}\LTwoSqr{\nu - \frac{Y}{\lambda}} $\Comment{Dual Objective function}
  \end{algorithmic}
  \Return $f_{\beta} - d_{\nu}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{SAS ( Safe Active Set ) }
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{a}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $c \in \mathbb{R}^n$  \Comment{ Center of the ball }
  \Statex $r \geq 0$  \Comment{ Radius of the ball }\tikzmark{b}
  \State $\mathcal{A} \gets \emptyset$ \Comment{ Initialize Active Set With Empty Set}
  \For{ $j\in\{1,\ldots,p\}$}
    \If{ $|X_j^Tc|+r\|X_j\|_2 \geq 1$}
       \State $\mathcal{A}\gets \mathcal{A} \cup \{j\}$
    \EndIf
  \EndFor
    \end{algorithmic}
  \Return $\mathcal{A}$
\end{algorithm}
\FloatBarrier

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{CDSR (Coordinate Descent With Lazy Evaluation and Screening Rule) \label{alg:cd_sr}}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k} 
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  \Statex $\beta \in \mathbb{R}^p$  \Comment{ Starting vector }
  \Statex $\lambda \in \mathbb{R}$  \Comment{ Grid element }
  \Statex $\mathcal{D} \in \mathbb{R}$  \Comment{ Duality gap target }\tikzmark{l}
    \State $\widetilde{\beta} \gets \beta$ \Comment{ Make a copy of $\beta$ }
    \State $R \gets Y - X \widetilde{\beta}$ \Comment{ Initialize Intermediary Residual }
    \State $\mathcal{A} \gets \{1,\ldots,p\}$ \Comment{ Initialize Active Set }
    \State $optimCont \gets true$ 
      \While{ optimCont }
      \State $\nu \gets \text{DP}(X_{\mathcal{A}},Y, \widetilde{\beta}_{\mathcal{A}}, \lambda)$ \Comment{ Dual point }
      \State $\mathcal{G} \gets \text{DG2}(X_{\mathcal{A}},Y, \widetilde{\beta}_{\mathcal{A}}, \nu, \lambda)$ \Comment{ Duality gap } 
      \State $\mathcal{A} \gets \text{SAS}(X, \nu, \sqrt{\frac{2}{\lambda^2}\mathcal{G}})$ \Comment{ Safe Active Set }
      \If{ $\mathcal{G} \leq \mathcal{D}$ }
      	\State $optimCont \gets false$
      \Else
        \For{ $i \in \mathcal{A}$ }
          \State $t \gets \frac{ \lambda }{ \LTwoSqr{ X_i } }$ \Comment{ Scale grid element by norm of the i'th column of design matrix }
          \If{ $ \widetilde{\beta}_i \neq 0 $ }{
            $R \gets R + X_i \widetilde{\beta}_i$
          }
          \EndIf
          \State $\widetilde{\beta}_i \gets \tau \left( \frac{X_i^T R}{ \LTwoSqr{ X_i } }, t \right)$ \Comment{ Update the i'th element of Beta }
          \If{ $ \widetilde{\beta}_i \neq 0 $ }{
            $R \gets R - X_i \widetilde{\beta}_i$
          }
          \EndIf  
        \EndFor
        \EndIf
        \State $\widetilde{\beta}_{\mathcal{A}^c}=0$ \Comment{ Set to 0 coefficients not in $\mathcal{A}$ }
      \EndWhile
  \end{algorithmic}
  \Return $\widetilde{\beta}$
\end{algorithm}
\FloatBarrier

Note that Algorithm~\ref{alg:cd_sr} solves the problem
\begin{equation}\label{eq:lasso_half}
\arg\min_{\beta\in\mathbb{R}^p}\frac{1}{2}\LTwoSqr{Y-X\beta} + \lambda\LOne{\beta}
\end{equation}

\FloatBarrier
\begin{algorithm}[!htbp]
  \caption{FOS With Screening Rule}
  \begin{algorithmic}[1]
  \Statex
  \Input\tikzmark{k}
  \Statex $X \in \mathbb{R}^{n \times p} $ \Comment{ The design matrix }
  \Statex $Y \in \mathbb{R}^n$  \Comment{ The vector of predictors }
  % \Statex $\beta \in \mathbb{R}^p$  \Comment{ Starting vector }
  % \Statex $L_0 \in \mathbb{R}$  \Comment{ Initial Lipschitz constant, used by backtracking line search }
  \Statex $M \in \mathbb{N}$  \Comment{ Number of grid elements }
  % \Statex $\eta \in \mathbb{R}$  \Comment{ Step size when updating Lipschitz constant }
  \Statex $C > 0$
  \Statex $\gamma > 0$\tikzmark{l}
    \State $\widetilde{X} \gets \frac{1}{\sigma_X}\left( X - \mu_X \right)$ \Comment{Normalize X to mean 0 and standard deviation 1.}
    \State $\widetilde{Y} \gets \frac{1}{\sigma_Y} \left( Y - \mu_Y \right)$ \Comment{Normalize Y.}
    \State $\Lambda \gets \lambda$GRID$( \widetilde{X}, \widetilde{Y}, M )$ \Comment{Initialize grid elements}
    \State $\beta_s \in \mathbb{R}^{ p \times M } \gets 0_{p,M}$ \Comment{Initialize matrix of Betas to zero matrix}
    \State $statsCont \gets true$
    \State $statsIt \gets 1$
      \While { statsCont $\And$ ( statsIt $< M$ ) }
        \State $statsIt \gets statsIt + 1$
        % \State $\widetilde{\beta} \gets \beta_{k-1}$ \Comment{Initialize old beta vector with the k - 1'th Column of the Betas matrix.}
        % \State $r_{statsIt} \gets \Lambda_k$ \Comment{ Extract the k'th grid element. }
        \State $\mathcal{D} \gets DGT( \gamma, C, \Lambda_{statsIt}, n )$ \Comment{ Duality gap target}          
        \State $\beta_{statsIt} \gets \text{CDSR}( \widetilde{X}, \widetilde{Y}, \beta_{statsIt-1}, \Lambda_{statsIt}/2, \mathcal{D}/2 )$
        \State $statsCont \gets$ SCC $( C, statsIt, \Lambda_{statsIt}, \Lambda, X, \beta_s )$
      \EndWhile
  \end{algorithmic}
  \Return $\beta_{statsIt-1}, \Lambda_{statsIt-1}, statsIt$
\end{algorithm}
\FloatBarrier

\end{document}