Solving L1 Regularized Least Squares via Proximal Gradient Descent

 The l1 regularized least squares problems is idea for proximal gradient descent. It is in a form that is ideally suited for proximal gradient gradient descent, since l1 is separable. We want to approximate a label |di| and we can put this all in the matrix equation. We want to minimize the squared 2 norm of the error plus lambda times the one norm of the weights (sparse, and the columns that matter). The nonzero entries in w, select columns in A close to the features. 

Proximal gradient Descent Algorithm, alternates between 2 stages, a gradient descent stage , and solve a regularized problem, obtaining a w close to z. 

The regularization steps involves a series of scalar minimizations. We want to minimize the sum of all the individual elements of w, and since the cost function is a sum of scalar cost functions, we just want to minimize the scalar cost functions. 

The case where wi is greater that or equal to 0 , we can werite thie problem, and we can set the derivative to wi to equal to 0, and that will give our solution for wi, and I can solve for wi. Recall we must have wi greater than or equal to 2. 

and the subtraction equation just yields the opposite equations. We put these 2 cases together and subsequently grab the result as shown. 

Therefore, the algorithm alterates the gradient descent and shrinkage algorithms, and we call this the soft threshold. We start at the origin, and go through the graph like the following: We can go higher and higher up the sides as a result of the cost function. We keep shrinking w2 to 0 and a lot of these stps start oscillating, where w(1) is the minimized weight and w2 = 0.