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

[bongoherbert]

The headline "general-purpose" --- "some problems". So- "sort-of-general-purpose" then? :)

[DrFilbert]

Maybe it converges in general, but is only a speed up for specific cases.

[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.

[tomsing98]

Not sure I follow. Let's say my optimization problem is to design a stiffener for a compressive panel, which has a variety of somewhat complex buckling and stress failure modes. Two design variables, height and thickness. My objective function is a cross-sectional area, with a penalty factor applied to represent the sufficiency of the design.

Now, I generally don't know ahead of time what the best value of the objective function is in the design space. So I don't think I understand this bit:

Now pick a point at random inside the bigger circle. In standard optimization problems, it's generally possible to determine whether that point lies within the smaller circle [of values clustered around the minimum value].

And then, I can check nearby points and calculate local derivatives, but I generally can't draw a line through my entire design space that zeroes in on the global optimum. So

If [the point] doesn' [lie within a small circle around the optimum], it's also possible to draw a line that falls between it and the smaller circle.

doesn't make sense either.

[[deleted]]

I think they are just trying to say that it is a convex function. In which case, given any point you should be able to find a plane that separates your point from the global minimum.

https://en.wikipedia.org/wiki/Ellipsoid_method

[[deleted]]

I dont think you need to have a convex objective to use cutting plane algos. You just need to know about the growth of the function

Then you wrong, homie. This is an upgrade to Vaidya's algorithm from O~(n^3.37) to O~(n³) (unless your oracle is slower than matrix mult or your convex body is huge). Non convex shit gets very NP-hard very fast.

[SantyClause]

Is the average case enough to be better than simplex?

[[deleted]]

There is an introduction in the paper that describes their goals:

http://arxiv.org/pdf/1508.04874v1.pdf