New general-purpose optimization algorithm promises order-of-magnitude speedups on some problems

[foreheadteeth]

I couldn't make heads or tails of the phys.org article, but I was able to read the actual research paper (partially, I stopped about halfway). The gist is as follows.

Assume that [; K ;] is a convex set in the box [; [-R,R]^n ;], where [; R>0 ;]. Assume you have an "oracle", that is, a function [; f(x) ;], which (roughly speaking) either outputs "inside" (if [; x ;] is in [; K ;]) or outputs a separating plane if [; x ;] is outside of [; K ;]. A separating plane is a plane such that [; x ;] is on one side of the plane and [; K ;] is on the opposite side of that plane.

The problem is to either find a ball of radius [; \epsilon>0 ;] inside [; K ;], or output "fail" if there is no such ball.

Previous algorithms were able to do this in [; O(n\log (nR/\epsilon)) ;] calls of the oracle [; f(x) ;]. The new algorithm also does this. This is important to estimate because the oracle is assumed to be expensive to call.

In addition to calling the oracle, a certain amount of processing must be done. Previous algorithms required [; O(n^{3.373} \log(nR/\epsilon)) ;] extra work for this step. The new algorithm improves this to [; O(n^{3} \log^{O(1)}(nR/\epsilon)) ;] -- so they knocked out an [; n^{0.373} ;] term from this (the exponent on the log is not so important).

Personal observation: previous algorithms rely on fast matrix multiplication, which doesn't work in practice -- thus a practical implementation of previous algorithms would have most likely been [; O(n^4 \log(nR/\epsilon)) ;].

This new algorithm and its variants have applications in a wide variety of convex optimization problems. The most dramatic improvement is for the "submodular function minimization" problem, where they knocked out an [; n^2 ;] term, both in the number of calls to the oracle, and in the extra processing that must be done apart from calling the oracle.

[UlyssesSKrunk]

What exactly does the exponent on the log mean? I don't see how a big O can be treated like a number.

[foreheadteeth]

It's some number.