4
$\begingroup$

I am trying to acquire an intuition and understanding of cases in which gradient descent (GD) diverges.

I have found some questions (1, 2, 3) in which people tried to minimize a popular cost function using GD, but it diverged.
However, I am looking for very simple examples aimed directly at understanding the foundations, without all of the "noise" that a solution to a real-world problem comes with.

Let's denote:

  • $f(x)$ - a convex function to find the minimum of (using GD)
  • $m = \text{argmin }f(x)$
  • $k$ - step number
  • $x(k)$ - the input to $f$ after step $k$
  • $d(k) = |x(k)-m|$, i.e. the distance from the minimum (with regard to inputs to $f$)
  • $\eta(k)$ - learning rate


The examples I look for:

  1. $\eta(k)$ is constant, and $\underset{k\rightarrow\infty}{\text{lim}}\space d=\infty$.
  2. $\eta(k)$ is constant, and $\underset{k\rightarrow\infty}{\text{lim}}\space d\not=\infty,0$, i.e. the GD doesn't converge to infinity, but "stuck in some infinite loop".
  3. $\underset{k\rightarrow\infty}{\text{lim}}\space \eta (k)=0$ and $\underset{k\rightarrow\infty}{\text{lim}}\space d=\infty$, i.e. the GD converges to infinity, even though $\eta$ converges to $0$.
$\endgroup$
4
$\begingroup$

Example 1: $\eta(k)$ is constant, and $\underset{k\rightarrow\infty}{\text{lim}}\space d=\infty$

Let $f=x^2$.
Then: $$ \begin{gathered}m=0\\ \nabla f\left(x\right)=2x\\ d\left(k+1\right)=\left|x\left(k+1\right)-m|=|x\left(k\right)-\eta\left(k\right)\nabla f\left(x\left(k\right)\right)-0\right|=\\ \left|x\left(k\right)-\eta\left(k\right)2x\left(k\right)\right|=\left|x\left(k\right)\right|\cdot\left|1-2\eta\left(k\right)\right|=\\ \left|x\left(k\right)-m\right|\cdot\left|1-2\eta\left(k\right)\right|=d\left(k\right)\left|1-2\eta\left(k\right)\right|\\ \downarrow\\ d\left(k+1\right)=d\left(k\right)\left|1-2\eta\left(k\right)\right| \end{gathered} $$

Therefore, assuming that $x(0)\not=0$, it holds that $d(k)$ is a geometric progression that converges to $\infty$ for any $\eta>1$.

E.g. for $\eta=1.01$:
Example 1 (Points get darker as $k$ increases.)

Example 2: $\eta(k)$ is constant, and $\underset{k\rightarrow\infty}{\text{lim}}\space d\not=\infty,0$

Let $f=x^2$.
As shown above, $d\left(k+1\right)=d\left(k\right)\left|1-2\eta\left(k\right)\right|$, so for $\eta=1$, we get $d\left(k+1\right)=d\left(k\right)\left|1-2\right|=d\left(k\right)$, i.e. $d(k)$ is constant, and $x(k)$ is the sequence $x(0), -x(0), x(0), -x(0), ...$

Example 2


By the way, it is interesting to see that for $\eta=0.5$, the GD converges after a single step for any $x(0)\not=0$.

Example 3: $\underset{k\rightarrow\infty}{\text{lim}}\space \eta (k)=0$ and $\underset{k\rightarrow\infty}{\text{lim}}\space d=\infty$

Let:

  • $f=x^4$
  • $\eta\left(k\right)=\frac{1}{k+1}$.
  • $x(0)=1$

Then: $$\begin{gathered}m=0\\ \nabla f\left(x\right)=4x^{3}\\ d\left(k+1\right)=\left|x\left(k+1\right)-m|=|x\left(k\right)-\eta\left(k\right)\nabla f\left(x\left(k\right)\right)\right|=\\ \left|x\left(k\right)-\eta\left(k\right)4\left(x\left(k\right)\right)^{3}\right|=\left|x\left(k\right)\right|\cdot\left|1-4\eta\left(k\right)\left(x\left(k\right)\right)^{2}\right|=\\ d\left(k\right)\cdot\left|1-4\frac{\left(d\left(k\right)\right)^{2}}{k+1}\right|\\ \downarrow\\ d\left(k+1\right)=d\left(k\right)\cdot\left|1-4\frac{\left(d\left(k\right)\right)^{2}}{k+1}\right| \end{gathered} $$ Therefore, if $d(k)\ge k+1$ (which also means that $d(k)\ge 1$), then: $$\begin{gathered} \frac{\left(d\left(k\right)\right)^{2}}{k+1}\ge1\\ \downarrow\\ \left|1-4\frac{\left(d\left(k\right)\right)^{2}}{k+1}\right|\ge3\\ \downarrow\\ d\left(k+1\right)\ge3d\left(k\right) \end{gathered} $$ and also: $$\begin{gathered}d\left(k+1\right)\ge3d\left(k\right)\ge3\left(k+1\right)\ge k+2\\ \downarrow\\ d\left(k+1\right)\ge k+2 \end{gathered} $$ We chose $x(0)=1$, so $d\left(0\right)\ge0+1$, and we can prove by induction that $d\left(k+1\right)\ge3d\left(k\right)$ for any $k\in\mathbb N$.
Thus, $d(k)$ is a geometric progression that converges to $\infty$.

Example 3 ($x^4$ is truly a wild function, so the GD explodes so fast that I managed to get a reasonable image for only 6 points, and I had to use $x(0)=0.76945$.)



Here is my code for making the animations, from which the images were taken:

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation


def f1(x):
    return x ** 2

f2 = f1

def f3(x):
    try:
        return x ** 4
    except OverflowError:
        print('x is too large... (The growth of x ** 4 is just crazy)\n'
              'I am afraid you have to just make INTERVAL bigger, and be '
              'satisfied with 3 data points :( ')
        exit()

def f1_grad(x):
    return 2 * x

f2_grad = f1_grad

def f3_grad(x):
    return 4 * x ** 3

func_to_grad_dict = {f1: f1_grad,
                     f2: f2_grad, 
                     f3: f3_grad}
func_to_sane_range_dict = {f1: (-1.8, 1.8, 0.01),
                           f2: (-1.8, 1.8, 0.01), 
                           f3: (-5, 5, 0.01)}
func_to_color_diff_dict = {f1: 0.03,
                           f2: 0.03, 
                           f3: 0.3}


def learning_rate_1(k):
    return 1.01

def learning_rate_2(k):
    return 1

def learning_rate_3(k):
    return 1 / (k + 1)

x0_1 = 1
x0_2 = 1
x0_3 = 0.76945

def plot_func(axe, f):
    xs = np.arange(*func_to_sane_range_dict[f])
    vf = np.vectorize(f)
    ys = vf(xs)
    return axe.plot(xs, ys, color='grey')

def next_color(color, f):
    color[1] -= func_to_color_diff_dict[f]
    color[1] = max(0, color[1])
    return color[:]


###########################################
# script parameters
X0 = x0_1
F = f1
LEARNING_RATE = learning_rate_1
INTERVAL = 1
INTERVAL = 3e1
INTERVAL = 9e2
INTERVAL = 3e2
###########################################


k = 0
x = X0
f = F
f_grad = func_to_grad_dict[f]
cur_color = [0, 1, 1]

fig, (k_and_x, x_and_y) = plt.subplots(1, 2, figsize=(9,5))
k_and_x.set_xlabel('k')
k_and_x.set_ylabel('x', rotation=0)
x_and_y.set_xlabel('x')
x_and_y.set_ylabel('y', rotation=0)
plot_func(x_and_y, f)
k_and_x.plot(k, x, '.', color=cur_color[:])
x_and_y.plot(x, f(x), '.', color=cur_color[:])
plt.tight_layout()

def update(frame):
    global k, x

    gradient = f_grad(x)
    x -= LEARNING_RATE(k) * gradient
    k += 1

    color = next_color(cur_color, f)

    print(f'k: {k}\n'
          f'x: {x}\n')

    k_x_marker, = k_and_x.plot(k, x, '.', color=color)
    x_y_marker, = x_and_y.plot(x, f(x), '.', color=color)

    return k_x_marker, x_y_marker

ani = FuncAnimation(fig, update, blit=False, repeat=False, interval=INTERVAL)
plt.show()
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.