10
$\begingroup$

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily terminate. However, the algorithm does satisfy the following properties.

(1) It can begin in any valid state (any valid flow can be used to initialize Ford-Fulkerson).

(2) At each step of the algorithm, there may be more than one choice, and the algorithm chooses arbitrarily between them (there may be more than one augmenting path, and Ford-Fulkerson chooses one arbitrarily).

(3) If the algorithm does not terminate, it converges to a (not necessarily optimal) state (if Ford-Fulkerson does not terminate, it converges to a (not necessarily maximum) flow).

Note that (3) is in contrast to algorithms which do not terminate because they cycle, such as certain pivoting rules of the Simplex algorithm.

Whenever a non-terminating algorithm satisfies the above properties, we can regard it as a transfinite algorithm whose run-time is an ordinal number as follows. If a run of the algorithm terminates after a finite number of steps, then its run-time is the corresponding finite ordinal. Otherwise, by (3) it converges to some state $S$. By (1) we can let $\omega$ steps pass and reinitialize the algorithm beginning with $S$. We then recurse. The (worst-case) ordinal run-time is the worst run-time over all valid runs of the algorithm (there are multiple possible runs by (2)).

Question. Are there other examples of non-terminating algorithms which satisfy properties (1), (2), and (3)? If so, have their ordinal run-times been analyzed?

In this paper, Spencer Backman and I proved that the ordinal run-time of the Ford-Fulkerson algorithm on a network with $m$ arcs is $\omega^{\Theta(m)}$. The only other example we know of is chip firing on metric graphs, by Backman. We are aware of the work of Hamkins and Lewis on Infinite Time Turing Machines, but as far as we can tell the above question is of a slightly different flavour.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ I think some very basic algorithms from calculus, like Newton's method, might qualify in a trivial way as an example of what you're looking for. $\endgroup$
    – Sam Hopkins
    Commented Apr 8, 2020 at 18:48
  • 1
    $\begingroup$ What's the purpose of (2)? I'm not sure if I think it's overly restrictive or meaningless, but I think it's one of those two things... $\endgroup$
    – Stella Biderman
    Commented Apr 8, 2020 at 19:37
  • $\begingroup$ I am interpreting (3) to mean that starting from any fixed state, the states produced by the algorithm after each finite number of steps converge to some state. If this is the correct interpretation then I see how to define the algorithm's state on steps $\omega$, $\omega + \omega$ and so on. But how do you define what the algorithm does at step $\omega^2$? $\endgroup$
    – Patrick Lutz
    Commented Apr 9, 2020 at 3:02
  • $\begingroup$ @StellaBiderman For Ford-Fulkerson, it turns out that non-termination is a result of making poor choices. The Edmonds-Karp algorithm (which always chooses a shortest augmenting path), will always terminate (even with irrational capacities). So, you can interpret the ordinal run-time as the 'height' of the search tree of the algorithm. Of course, the question still makes sense for algorithms which satisfy only (1) and (3). $\endgroup$
    – Tony Huynh
    Commented Apr 9, 2020 at 3:10
  • $\begingroup$ @PatrickLutz You are correct that a little care needs to be taken to ensure that a state exists for every ordinal. For Ford-Fulkerson, this can be done by transfinite induction. The linked paper with Spencer has all the formal details. In general, we probably need something like (4) There is a strictly increasing parameter associated to each step of the algorithm, and this parameter is bounded. For Ford-Fulkerson, this parameter is the value of the current flow. $\endgroup$
    – Tony Huynh
    Commented Apr 9, 2020 at 3:17

2 Answers 2

Reset to default
2
$\begingroup$

There are many algorithms in machine learning that seem to fit your formal definition, but don't seem to produce anything useful when you analyze them in your model.

Hill climbers or SGD are a good example of this. If you add an oracle for determining that you are at the global optimum, a hill climbing algorithm can be run until it finds a local optimum, then thrown into an infinite loop in which it stays in place. It only actually terminates at the global optimum.

Even when run on a simple curve like $\sin(x)/x$ it is possible for the algorithm to never find the global optimum.

Worse, your algorithm could enter a "transfinite loop" where, although no individual run of the algorithm loops, running it starting with $x$ converges to $y$ and running it starting with $y$ converges to $x$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The problem here seems to be that the states the algorithm could converge to are also fixed points of the algorithm. Presumably running the algorithm for transfinitely many steps is only interesting when the algorithm does not always get stuck at a fixed point on step $\omega$. $\endgroup$
    – Patrick Lutz
    Commented Apr 9, 2020 at 3:04
  • $\begingroup$ Thanks for your answer! We can avoid ''transfinite loops'' by adding the property (4) There is a strictly increasing parameter associated to each step of the algorithm, and this parameter is bounded. For Ford-Fulkerson, this parameter is the value of the current flow. $\endgroup$
    – Tony Huynh
    Commented Apr 9, 2020 at 3:19
  • $\begingroup$ @Patrick That handles the specific example of a hill climber, but not the extension to transfinite loops. $\endgroup$
    – Stella Biderman
    Commented Apr 9, 2020 at 3:37
  • $\begingroup$ @Tony I’m not sure if that is going to do exactly what you think it does, but it seems to be on the right track. My intuition is that the “right way” to handle this problem would assign a hill climber a value of $n\omega$, where $n$ is the largest number of local optima that it can get stuck in. Do you agree? $\endgroup$
    – Stella Biderman
    Commented Apr 9, 2020 at 3:42
  • $\begingroup$ @Stella Yeah I just meant the problem with the specific example you gave, not the only problem in general. $\endgroup$
    – Patrick Lutz
    Commented Apr 9, 2020 at 7:10
1
$\begingroup$

In this paper Jay Kienzle and I consider traversal algorithms over infinite, well-ordered graphs. The situation is a little different than your conditions (1)-(3): the algorithms are deterministic and the graphs are infinite, but the algorithms are transfinite with a well-defined ordinal "run time." Moreover, this paper is explicitly concerned with deriving tight upper bounds for said run times in terms of the order type of the original graph. So in that sense, I think this paper is close to the spirit of your question.

Improve this answer
$\endgroup$

You must log in to answer this question.

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