3
$\begingroup$

In order to solve the convex problem

$$ \min_x f(x)$$

I use the so-called approximate gradient descent algorithm, whose $(k+1)$th iterate has the form

$$ x_{k+1} = x_k - \gamma \tilde{\nabla}f(x_k),$$ where $\tilde{\nabla}f(x_k)$ is an approximation of $\nabla f(x_k)$ and $\gamma > 0$ is some sufficiently small step size.


Question: Is it possible for one to (formally) prove that

$$f(x_{k+1}) \leq f(x_k),$$

or, more generally, that the approximate gradient descent "works". If so, how?

Since I am not using a stochastic approximation to the gradient, probabilistic arguments are not useful in this case.


Any directions, either to relevant papers or thoughts on how one could proceed with a proof (i.e., conditions on $\gamma$ or $\epsilon(x_k) = \tilde\nabla f(x_k) - \nabla f(x_k)$) would be helpful.

$\endgroup$
5
  • $\begingroup$ You might try to tackle this from the standpoint of Lyapunov stability theory. I. e., you may consider $x_{k+1} = x_k - \gamma \tilde{\nabla}f(x_k)$ as a discrete-time dynamical system. $\endgroup$
    – Rubi Shnol
    Jan 13, 2017 at 19:29
  • $\begingroup$ Could you elaborate any or point to some relevant reading (at or near an intro-level)? $\endgroup$
    – user23658
    Jan 13, 2017 at 20:00
  • $\begingroup$ Typically, yes this algorithm works (i.e. it will converge to a solution of the minimization problem) -- as long as your error is "summable", i.e. $\sum_{n\in\mathbb{N}}\|\nabla f(x_k)-\widetilde{\nabla f}(x_k)\|<+\infty$ $\endgroup$
    – Zim
    Jun 10, 2020 at 2:28
  • $\begingroup$ Also it's pretty standard to require $\nabla f$ to be Lipschitz continuous with constant $L$ and impose that $\gamma\in]0,2/L[$. $\endgroup$
    – Zim
    Jun 10, 2020 at 2:34
  • $\begingroup$ Do you agree with my edits? $\endgroup$ Feb 19, 2021 at 13:15

1 Answer 1

2
$\begingroup$

One option is to consider the dynamical system

$$ e_k = x_k - x^*, $$

where $x^*$ is the extremum.

Then, $e_{k+1} = e_k - \alpha \nabla f(x_k)$.

Take a function $V(e_k) = V_k := e_k^2$.

Then,

$$ V_{k+1} - V_k = \alpha^2 ( \nabla f(x_k) )^2 - 2 \alpha e_k \nabla f(x_k) $$

If it is possible to show that $V_{k+1} - V_k < 0, \forall e \ne 0$, then it is called a Lyapunov function for the system and in turn $e_k$ converges asymptotically to the equilibrium $e = 0$ whence $x = x^*$.

Observe that $e_k < 0 \implies \nabla f(x_k) < 0$ and $e_k > 0 \implies \nabla f(x_k) > 0$. So, if $\alpha$ is to be taken as positive, the condition

$$ \alpha_k < 2\frac{|e_k|}{|\nabla f(x_k)|}, e_k = 0 \implies \alpha_k := 0 $$

is a possible choice of an adaptive gain $\alpha_k$ which renders the equilibrium asymptotically stable.

If the gradient is approximate, then a condition that its sign coincides with the sign of $e_k$ suffices for the argument to work. Otherwise, you need to define the region where this condition holds. Its complement is the attractor. Indeed, if in some region the gradient changes sign arbitrarily, then no stability can be shown.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .