Slashdot Mirror
New Algorithm Provides Huge Speedups For Optimization Problems (mit.edu)
An anonymous reader writes: MIT graduate students have developed a new "cutting-plane" algorithm, a general-purpose algorithm for solving optimization problems. They've also developed a new way to apply their algorithm to specific problems, yielding orders-of-magnitude efficiency gains. Optimization problems look to find the best set of values for a group of disparate parameters. For example, the cost function around designing a new smartphone would reward battery life, speed, and durability while penalizing thickness, cost, and overheating. Finding the optimal arrangement of values is a difficult problem, but the new algorithm shaves a significant amount of operations (PDF) off those calculations. Satoru Iwata, professor of mathematical informatics at the University of Tokyo, said, "This is indeed an astonishing paper. For this problem, the running time bounds derived with the aid of discrete geometry and combinatorial techniques are by far better than what I could imagine."
Satoru Iwata, professor of mathematical informatics at the University of Tokyo, said, "This is indeed an astonishing paper.
I'm assuming this isn't the same Satoru Iwata of Nintendo fame... who sadly passed away earlier this year. :/
"I like to lick butts!" by MobileTatsu-NJG (#32700246) (Score:5, Informative)
And as it turns out, P=NP. Stay tuned for more exciting developments!
How can I believe you when you tell me what I don't want to hear?
I believe someone already invented a knife, guys.
I guess they never heard of the "No Free Lunch" theorem for optimization, which believe it or not is the name of a proven theorem by David Wolpert that says the following is rigrorously true.
Averaged over all optimization problems every possible algorithm (that does not repeat a previous move) takes exactly the same amount of time to find the global minimum.
The collorary for this is that: If you show your algorithm outperforms other algorithms on a test set, then you have just proven it performs slower on all other problems.
That is the better it works on a finite class of problem, the worse it is on most problems.
it is even true that a hill climbing algorithm blunders into the minimum in the same average time as a hill descending algorithm. (yes that is true!).
Look it up. It's the bane of people who don't understand optimization.
The only things that distinguishes one optimization algorithm from another is:
1) if your problems are restricted to a subspace with special properties that your algorithm takes advantage of
2) your performance metric is different then the average time it takes to find the global minimum. for example, something that limits the worst case time to get within epsilon of the minimum.
Some drink at the fountain of knowledge. Others just gargle.
Is not an attribute to penalize. Thicker phones are sturdier (less prone to bending, among other things), easier to grip (more surface area on the edges, where you grip it while talking, and feel more substantial. Phone cases offer protection for the device and mitigate all these shortcomings.
Looking back, Zoolander only got one dimension right when it comes to phone size. The joke now would be a phone that is the size of a sheet of paper (and the 13.9" screen has 6204ppi).
https://en.wikipedia.org/wiki/...
Some drink at the fountain of knowledge. Others just gargle.
This is not a special case for a given data set, its a basic improvement in cutting-plane performance, and a derivation of special cases which can gain up to n^6 in speed. So given a problem, you would decide which class it falls into and write your optimization code to gain the smaller speedup, or the larger speedup.
This is NOT an engineering tweak to a gradient solver!
I read the summary. I didn't understand it. Then I read the article. I didn't understand it either.
If their algorithm is any good then they should run it on their algorithm.
Imagine the results. Mind blown.
Some very interesting results, but the two key contributions are (almost verbatim from the article):
1) With the best general-purpose cutting-plane method, the time required to select each new point to test was proportional to the number of elements raised to the power 3.373. Sidford, Lee, and Wong get that down to 3.
2) And in many of those cases (submodular minimization, submodular flow, matroid intersection, and semidefinite programming), they report dramatic improvements in efficiency, from running times that scale with the fifth or sixth power of the number of variables down to the second or third power.
So this seems to be a better cutting plane approach that improves the cutting process by reducing the time to find the next test point (in general), and for certain structured problems (like SDPs) this approach reduces the computation time significantly.
This does raise some interesting questions, such as: is there a limit to how fast you can (in a general problem, not using a specific problem's structure) find the next test point? Even if we don't know what algorithm gets us there, it would be useful to have a bound for future research.
"Averaged over all problems, the time it takes to figure out which special case one has plus the time to solve that special case has to be the same as any other algorithm."
In practice you know what type of problem you're solving, and use the appropriate approach.
So for example a Neural Network 'fast solve' is currently derived as a back propagation gradient solver. The math is resolved like that and then coded like that. My stock predictor algo is a cutting plane solver because I can exclude large amounts of suboptimal results very quickly.
Your thinking seems to be that you are given a black box, about which you know nothing, but with inputs and outputs and your solver needs to be the fasted way to solve this black box.
So it would be like taking a hammer to every problem and saying that "hitting it with a hammer only works sometimes".
Congress is really slow and converging to the optimal law. Maybe this could help?
Algorithms can be fast, or use low amount of memory. Doesn't the bucketing used here require additional memory over other methods? In the end, just an optimization of speed, while requiring more memory?
What use are the tables comparing different algorithms when only the computational complexity is given, but not the memory requirements?
This paper is about convex optimization, and says nothing about designing smartphones -- and smartphones are not designed by solving a convex optimization problem with variables representing battery life, speed, etc. So wtf is the summary talking about smartphones for? It's completely wrong.
Smartphone design is not an application of this paper, at least not at all in the way the summary suggests. It's true that some aspects of circuit design are achieved using convex optimization, and this paper could potentially be useful there, but that is completely different.
Replace all intersections with roundabouts. Problem solved. No, not really, somebody will still find a way to mess things up.
If you read the press release from MIT, this discovery was about problems squarely inside P. Namely, they were (for a certain class of problems in P) able to reduce the complexity from N^^5 or N^^6 down to N^^2 or N^^3. So there would seem to be no implications for the P=NP problem.
One of the tricks that people play when they claim to have parallelized something or improved computational complexity is that they don't back up their claims with any real runtimes. They provide a theoretical evaluation, but they haven't actually shown that anything is actually FASTER in a practical way. Maybe it is, maybe it isn't. They haven't made a proper case for it. Maybe I missed it. I'm also not sure they actually coded it up and tried it. As a researcher who puts time and effort into actually implementing the ideas I develop, it really angers me when people get crap published where they are lazy or play with the statistics or use the wrong metrics.
intersections and roundabouts are solutions to multi-way traffic junctions. roundabouts work well up to certain criteria, usually demands as a factor of road capacity. After that, they can completely starve traffic due to imbalances in traffic direction, unlike intersections, which will provide forward progress.
for those nitpickers, if the exit from a roundabout and an intersection are full, neither provides meaningful progress.
You know what actually works well? Cloverleafs. Expensive, though.
Me I want to redesign *everything*.
I'd like to build a town where dwellings and stores are up on pylons like mushroom heads; that allows a huge amount of ground to be devoted to nature as compared to dwellings on the ground. I want them separated from neighboring dwellings by at least 50 feet of open space.
I want transport between/along the dwellings to be a dual purpose line where one half is a monorail with community cars, and one half is a walkway, and I want that up in the air with the dwellings, also on pylons. Nothing on the ground. No streetlights. Just daylight/IR cameras that send sidewalk activity to a central, secure, automated recording location in order to prevent hooligans from becoming a problem. The related records would be freed up for law enforcement only in the case of robbery or assault.
The entire town would be a park. You want transport, you signal for a car, it'll come get you and switch as required to get where you want to go, including the garage outside the town limits where you store your vehicle(s), assuming you even need one (for travel elsewhere, you might want one.)
No vehicles would be allowed on the ground. You can walk there any time. No hunting.
As soon as I make my first billion...
I've fallen off your lawn, and I can't get up.
Assistant professor, computational mathematician and optimizer here. The paper is of theoretical significance because it reduced provable bounds on the runtime complexity of a certain class of algorithms for convex optimization.
The catch is, no-one uses the algorithms in question in practice. There are significantly more powerful methods that are vastly more performant when applied in practice, but for which said bounds have not been (or even cannot be) proved.
So the impact on computational practice will be very limited. No new codes, solvers, and no relevant problems will be solved any faster than before.
tl;dr: Nothing to see here, move along.
All these algorithms are exponential for optimal solutions. (Well, unless P=NP, but that looks more and more unlike all the time. And even if it was true, high-exponent polynomial is not really better in practice anyways.) Hence _nobody_ uses the algorithms for optimal solutions in practice. What is used are approximation algorithms that provide a good solution, and there the quality measure is not "speed", but speed vs. result quality.
This may be nice theoretical research, but the practical impact is rather non-existent.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
You have it upside down. If all the 'stuff' is elevated, the ground winds up being dead because it doesn't get enough sun.
Sleep your way to a whiter smile...date a dentist!