Proximal GD Idea Explained

Classical Gradient Step for Minimizing $g(x)$

If we were minimizing only $g(x)$, the standard gradient descent step would be derived from a first-order approximation:

Here:

• The first two terms are the first-order Taylor expansion of $g(y)$ around $x_t$.
• The third term is a quadratic regularization (proximal term) that keeps updates close to $x_t$ to prevent large jumps.
  Actually, this term is the second-order Taylor expansion of $g(y)$ around $x_t$.

Adding the $h(y)$ Term

When we introduce $h(y)$, which is possibly non-smooth, we modify the update by keeping the gradient step for $g(x)$ the same but adding $h(y)$ explicitly:

Now, the function consists of:

1. A linear approximation of $g(y)$.
2. A quadratic proximity term.
3. The non-smooth function $h(y)$**.

Completing the Square

Since $g(x_t)$ is independent of $y$, we ignore it in the minimization problem. The key step is recognizing that the first two terms can be rewritten using the squared norm:

This term is the first-order approximation of $g(x)$ plus a regularization, and it can be rewritten in a more compact form:

Understanding the Completing-the-Square Step

We need to rewrite the quadratic expression:

into a squared norm form plus a constant term.

Step-by-Step Breakdown

1. Expand the squared norm

The Euclidean norm squared is given by:

So, we rewrite the term:

2. Introduce a shift using $\gamma \mathrm{\nabla }g(x_t)$

We want to introduce a shifted term in the form $y-(x_t-\gamma \mathrm{\nabla }g(x_t))$, so we add and subtract $\gamma \mathrm{\nabla }g(x_t)$ cleverly.

Observe that:

This suggests rewriting the term as:

3. Expand the squared norm

Consider the squared term:

Expanding it:

Breaking it down:

Expanding using the identity $(a+b{)}^T(a+b)=a^{T}a+2a^{T}b+b^{T}b$:

Dividing everything by $2\gamma$:

Thus:

4. Rearrange the expression

Comparing with the original form:

We get:

This is the final transformed expression!

BUT! The final formula looks like this:

This is beacuse the term $\frac{\gamma }{2}\parallel \mathrm{\nabla }g(x_t){\parallel }^2$ is a constant with respect to $y$ and can be ignored in the minimization problem :)