Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my travels, I have come across at least three algorithms which have the following structure:

  • The goal is to find some $x$ that simultaneously satisfies multiple conditions.
  • We begin by selecting $x_0$ totally at random.
  • At each step, select one of the conditions, and compute $x_{n+}$ by modifying $x_n$ in such a way that the condition holds (or at least becomes closer to holding).

It's not surprising that you can perform such an algorithm. What surprises me is that it works! That is, the sequence $x_n$ eventually converges to a value that really does satisfy all the conditions simultaneously.

I'm curious as to how/why it works, and under what circumstances.

In case anybody thinks I'm only talking about one narrow subject, let me give some broad examples of this algorithm in the wild:

  • Given a system of equations $x=f(y)$ and $y=g(x)$, initialise $x_0$ and $y_0$ to random real numbers, and then repeatedly compute one variable from the other. The numbers eventually converge to a pair $(x,y)$ which does in fact solve the given equations. (I'm not 100% sure whether this only works for linear equations, or whether any arbitrary polynomial would work - or perhaps even more general functions than that...)
  • One method of (supervised) training of artificial neural networks is error back-propogation: Feed an input into the network. Compare the output to the desired output. Feed the output error backwards through the network, adjusting the connection weights "slightly" so as to bring the output closer to the desired output. Repeat for a bazillion input/output pairs, and the network gradually "learns" to produce the desired output.
  • I saw an algorithm for blind deconvolution of image data. It begins with a blurry image, and a randomly-chosen point spread function. At each step, we apply FFT or inverse-FFT and update either the estimated point spread function or the estimated deblurred image based on constraints. (E.g., an image cannot contain negative colours.) After enough iterations, a fairly accurate estimate of the original non-blurred image emerges.

Although different, all of these algorithms are clearly instances of the same general procedure. Some of them deal with simple real numbers, some with matrix data, some with the configuration of an entire neural network! But they all work by successive refinement starting from a random initial. It is surprising to me that this doesn't just result in a sequence that jumps around all over the place and never converges to anything.

Can anyone offer some insight into what's going on here? When does such a technique work? When does it not work?

share|improve this question
    
This really only works under certain limited circumstances, mostly having to do with the functions equations having smooth approximations to a global optimum. It wouldn't necessarily work in a situation where there are several local optima obscuring the global optimum. –  Foo Barrigno Feb 5 at 13:35
    
@FooBarrigno Certainly supervised learning is notorious for getting "stuck" in local optima... –  MathematicalOrchid Feb 5 at 13:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.