Averaging gradient descent method

Sébastien Gadat · science forum beginner Joined: 07 Mar 2005 Posts: 6

Hi,

I am looking for informations about what happens to the dynamical system
(dimension n)

X_t = - 1/t \int_{0}^t gradient E(X_s) ds

It is something like a gradient descent averaged from time 0 to time t.
E is a smooth energy functionnal and X_t is the position of the point at
time t.
--
Sebastien

Hans Engler · science forum beginner Joined: 24 Mar 2005 Posts: 5

If you want continuous trajectories for t >= 0, then X_0 must satisfy X_0 +
E(X_0) = 0. And then X_t = X_0 is a solution for all t. So the dynamics are
rather trivial.

"Sébastien Gadat" <sebastien.gadat@free.fr> wrote in message
news:e1o6cm$9nc$1@news.ks.uiuc.edu...

Sébastien Gadat · science forum beginner Joined: 07 Mar 2005 Posts: 6

In fact, there was a mistake in the former formula. The good evolution
equation is:
X'_t = - 1/t \int_{0}^t gradient E(X_s) ds
starting from X_0 with X'_0=- Gradient E(X_0).
I do not find the conclusion so obvious with this equation.
--
Sebastien

"Hans Engler" <h.engler@verizon.net> a écrit dans le message de news:
e1u32f$fg$1@dizzy.math.ohio-state.edu...

Hans Engler · science forum beginner Joined: 24 Mar 2005 Posts: 5

That's less trivial indeed :)

Let's look at the simplest case: X_t \in R, E(x) = x. The integral equation
is equivalent to tX'' + X' + X = 0. With initial data X_0 = 1 = -X'_0, the
power series for the solution turns out to be
X_t = 0_F_1(;1,-t) = 1 - t + t^2/(2!)^2 - t^3/(3!)^2 + t^4/(4!)^2 ... , a
confluent hypergeometric limit function (see
http://mathworld.wolfram.com/ConfluentHypergeometricLimitFunction.html )
which can also be expressed in terms of a Bessel function of the first kind
as
X_t = J_0(2 \sqrt{t}) .

The asymptotics are known:

X_t ~ \pi^{-1/2}t^{-1/4} \cos(2 t^{1/2} - \pi/4).

Thus a very slow oscillatory decay to zero.

It's now easy to see what happens in the general linear case, X_t \in R^n
and E(x) = Ax + b with A symmetric and positive definite: Just transform to
principal components and deduce that |X_t - X*| ~ t^{-1/4}, where AX* + b =
0.

For general E (gradient of a multi-well coercive potential) the situation is
presumably much more complicated than for the "standard" case X_t = -E(X_t),
since the equation exhibits a "long term memory". It's most likely still
true that solutions with initial data near local minima of the potential
converge to the minimum. I'm not aware of much work on the general behavior
of such integral equations.

Hope this helps :)

"Sébastien Gadat" <sebastien.gadat@free.fr> wrote in message
news:e1uhdd$143$1@dizzy.math.ohio-state.edu...

Sébastien Gadat · science forum beginner Joined: 07 Mar 2005 Posts: 6

Hi,

This is exactly what I found, in the quadratic case, we can see that the
solutions are based on Bessel functions, and if we use linearisation
approximation, we can equally seen that equilibrium are stable with rate of
convergence in t^{-1/4}. Now my main problem is to justify that the
trajectory attains a neighbourhood of a minimum of E.
By the way, in most of my experiments in Matlab, I have seen this type of
oscillating convergence to the minimum. I am consequently optimist for the
nature of the result, but I really don't know how could I achieve it!

--
Sebastien

"Hans Engler" <h.engler@verizon.net> a écrit dans le message de news:
e1ura8$1bv$1@dizzy.math.ohio-state.edu...

Google