Proximal Gradient Algorithm

 The objectives are as follows:

-Derive the proximal Gradient Algorithm for regularized least-squares problems. 

-Apply this algorithm to Ridge Regression. 

Proximal Gradient Descent Solves Regularized Least squares problems. r(w) is the regularizer and λ is the tuning parameter.

2 Types of Regularizers are Ridge Tikhonov Regularizer and LASSO regularizer. 

The idea of Proximal gradient descent is to find the minimum of the squared error + the λ. 

We want to find a function gk such that gk touches f(w) and f(w) is below gk(w). 

We keep repeating this process, and we want to find the minimum of gk+1 and we solve a sequence of simpler problems, and is very useful. r(w) can be a sum of cross function of w(i). I will demonstrate below. 

We want to minimize g(k) which causes f(w) to increase.

Inside the 2norm of the error add Aw(k) and subtract A(w(k)) and multiply them together. Since the function is squared, we would want to write the transpose. Add the regularizer in the final area. 

The norm of the product of a matrix is bounded by the operator norm * norm. 

Then we define a step size, which is bounded by one over the operator norm of A, which 1/τ is greater than A operator norm. 

Gk should be a simple optimizer. As long as r(w) is separable, then in this form, this is already a separable function. It can be written in terms of the separable functions and only involve wi. 

w(k+1) is equivalent to the argmin of gk(w).

The step and clue is to alternate Least Squares Gradient Descent and Regularization. 

If I can write my recularizer to only depend on w(i), then write the regularization proglam that minimize the difference between the following algorithm. Perform n optimizations. 

Our regularizer scales the values to smaller size, in order to shrink towards the origin. 

When the regularizer gets more complicated, a proximal gradient approach comes up with an iterative algorithm to solve the regularized least-squares problem.