The ODE modeling for gradient descent with decreasing step sizes

Question

The gradient descent (GD) with constant stepsize $\alpha^{k}=\alpha$ takes the form

$$x^{k+1} = x^{k} -\alpha\nabla f(x^{k}).$$

Then, by constructing a continuous-time version of GD iterates satisfying $X(k\alpha)=x^{k}$ and taking $\alpha\to 0$, we could obtain a limiting ODE for constant-stepsize GD of the form

$$\lim_{\alpha\to 0}\frac{X(t+\alpha)-X(t)}{\alpha} =- \nabla f(X(t))\Rightarrow\frac{dX(t)}{dt} = -\nabla f(X(t)).$$

My question is: if we use the diminishing step size with the form

$$\alpha^k = \frac{\alpha}{(k+1)^\beta}, \qquad \beta \in (\frac{1}{2},~1),$$

could we derive the corresponding ODE as $\alpha\to 0$?

Some literatures claim that (without proof) the limiting ODE for diminishing-stepsize GD takes the form of

$$\frac{dX(t)}{dt} = -\frac{1}{(t+1)^{\beta}}\nabla f(X(t)).$$

But the ODE that I could prove is

$$\frac{dX(t)}{dt} = -\frac{1}{t^{\beta}}\nabla f(X(t)),$$ which is hard to be dealt with (due to its singularity at $t=0$).

Any help appreciated!

Answer 1

I intend to give some glimpses, like this one.

Let us consider the minimization problem $$g({\bf a})=\min_{\textbf{x}\in A}{g(\textbf{x})}$$ to some continuously differentiable function $\textbf{g}:A\to \mathbb{R}$, where $A$ is an open set of $\mathbb{R}^m$ containing $\textbf{a}$. Now, if you have some differentiable curve $\textbf{u}:(a,b)\to A$, you can apply the chain rule to obtain $$\frac{d\, g({\bf u}(t))}{dt}= \left\langle {\bf u}'(t), \nabla g({\bf u}(t))\right\rangle,$$ in which $\langle \cdot,\cdot\rangle$ denotes the inner product.

A natural choice to ${\bf u}(t)$ is given by the the initial value problem (IVP) $$\left\{\begin{array}{rl}{\bf u}'(t)&=&-\alpha \nabla g({\bf u}(t))\\ {\bf u}(0)&=&{\bf u}_0\end{array}\right.,$$to some $\alpha>0$.

If you use Euler method to solve this IVP numerically, you find the gradient descent method. This method, with step size $h_j$, takes the form $${\bf u}_{j+1}=\phi({\bf u}_j),$$ to $$\phi({\bf u})={\bf u}-h_j\alpha\nabla g({\bf u}),$$ as a fixed point iteration to solve $$\nabla g({\bf u})={\bf 0},\qquad \phi({\bf a})={\bf a}.$$ It converges when $$\|\phi'({\bf a})\|=\|I-h_j\alpha Hg({\bf a})|=\max_{1\leq i\leq m}|1-h_j\alpha s_i|<1,$$ if you have a good choice to ${\bf u}_0$. Here $s_i$ is a singular value of the hessian matrix $H g({\bf a})$.

It holds the inequality $$\frac{d\, g({\bf u}(t))}{dt}= -\alpha\|\nabla g({\bf u}(t))\|^2\leq 0,$$ and $g({\bf u}(t))$ is nonincreasing.

Remark:

1. Note that, if you choose the curve ${\bf u}(t)$ given by the IVP $$\left\{\begin{array}{rl}{\bf u}'(t)&=&-\beta(t) \nabla g({\bf u}(t))\\ {\bf u}(0)&=&{\bf u}_0\end{array}\right.,$$ to some $\beta(t)>0$ (in a way that the ${\bf u}(t)$ exists). You still has the inequality $$\frac{d\, g({\bf u}(t))}{dt}= -\beta(t)\|\nabla g({\bf u}(t))\|^2\leq 0,$$ and $g({\bf u}(t))$ is nonincreasing.

2. I am trying to find some results using this last IVP on SearchOnMath, and I found one in the direction you want. Please see comments around equations (3.10) and (3.11) in this arxiv file. It follows that, if you let $s=\rho(t)$, with $\rho(0)=0$ and $\rho'(t)=\beta(t)$, then $$\left\{\begin{array}{rlrr}{\bf u}'(s)&=&\displaystyle\frac{d\,{\bf u}}{dt}\frac{dt}{ds}&=&- \nabla g({\bf u}(s))\\ {\bf u}(0)&=&{\bf u}_0\end{array}\right..$$