A First Look at Gradient Descent

In this problem, we’re doing to give a computational introduction to two fundamental ideas of modern computational machine learning:

1. Minimizing a function is often a useful thing to do and
2. This can often be done by moving in directions guided by the derivative of the function.

For our first example, we’ll see how minimizing a function by iteratively moving in the direction of the derivatives can be used to solve a familiar math problem.

Let ${\mathbb{R}}^{+}$ be the set of strictly positive real numbers. Let $a\in {\mathbb{R}}^{+}$. Consider the function $g_a:{\mathbb{R}}^{+}\to \mathbb{R}$ with formula

Here and elsewhere in this class, $\log$ always refers to the natural log (base $e$), which you may have also seen written $\ln$.

$$g_a(x)=\frac{1}{2}{x}^2-a\log x.$$

Part A

A critical point of $g_a$ is a point $x_0$ where $\frac{d{g}_a(x_0)}{dx}=0$. Find the critical point of this function in the set ${\mathbb{R}}^{+}$. We’ll call this point $x_a$.

Part B

Use the second derivative test to show that $g_a$ is strictly convex on the set ${\mathbb{R}}^{+}$. It follows that the critical point $x_a$ is a global minimum of $g_a$.

Part C

Implement the following algorithm as a Python function:

Inputs: $a\in {\mathbb{R}}^{+}$, tolerance $ϵ>0$, learning rate $\alpha$, $\mathrm{maxsteps}=100$.

1. Start with an initial guess $x=a$.
2. Set $x^{\prime }\leftarrow 2a$ and $j\leftarrow 0$.
3. While $|x^{\prime }-x|>ϵ$:
   • if $j>\mathrm{maxsteps}$
     • Break
   • $x\leftarrow x^{\prime }$
   • $x^{\prime }\leftarrow x-\alpha \frac{d{g}_a(x)}{dx}$;.
   • $j\leftarrow j+1$.
4. Return $x$.

You should use the formula for $\frac{d{g}_a(x)}{dx}$ that you found in Part A.

Test your function like this:

mystery_fun(a = 9, epsilon = 1e-8, alpha = 0.2)

Please show:

1. One setting of $\alpha$ for which your function returns a real number very close to the exact value of $x_a$.
2. One setting of $\alpha$ for which your function fails to return a real number close to the exact value of $x_a$ within the maximum number of steps.

Part D

Is it possible to compute the positive square root of a positive real number using only the operations of addition, subtraction, multiplication, and division?

© Phil Chodrow, 2025