4 ms·
'Breakthrough' algorithm exponentially faster than any previous one
- HelloNurse 8y agoAny link to a paper?
- FlukE_ 8y ago'The researchers will present their novel approach at two upcoming conferences: the ACM Symposium on Theory of Computing (STOC), June 25-29 and International Conference on Machine Learning (ICML), July 10 -15.' I couldn't find anything with some googling so I'm assuming this quote describes the first showing of the paper.
- rindalir 8y agohttps://scholar.harvard.edu/files/ericbalkanski/files/the-adaptive-complexity-of-maximizing-a-submodular-function.pdf https://scholar.harvard.edu/files/ericbalkanski/files/the-ad...
- MaxBarraclough 8y agoI don't think that's it. That's one of Singer's earlier works. I'm fairly sure the relevant one is https://arxiv.org/pdf/1804.06355.pdf https://arxiv.org/pdf/1804.06355.pdf (listed as 'under submission' at https://people.seas.harvard.edu/~yaron/papers.html https://people.seas.harvard.edu/~yaron/papers.html , in line with the article's description)
- rindalir 8y agoThe one I posted is the one that was accepted at STOC this year.
- MaxBarraclough 8y agohttps://arxiv.org/pdf/1804.06355.pdf https://arxiv.org/pdf/1804.06355.pdf
- LyndsySimon 8y agoExcellent, thank you! > This algorithm therefore achieves an exponential speedup in parallel running time for submodular maximization at the expense of an arbitrarily small loss in approximation quality. Based on this, it seems that this isn't so much a better search algorithm as much as it is a means of finding the optimum tradeoff between accuracy and speed in situations where processing the entire dataset is computationally prohibitive. I'm no computer scientist, and algorithms in generally aren't really my area, so take this with a large grain of salt.
- tzs 8y agoabstract: https://arxiv.org/abs/1804.06355 https://arxiv.org/abs/1804.06355
- Barjak 8y agoI think it's arXiv:1804.06355 "An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation"
- pmarreck 8y agoSo this is basically "early search-tree pruning"? Or, how is it different from that, exactly? (I believe early search-tree pruning has been used in chess algorithms for years.)
- sp332 8y agoIt samples from the data randomly, which can be massively parallelized. As it runs, it adapts the distribution that it samples from, which is similar to pruning.
- LyndsySimon 8y ago> It samples from the data randomly If this is true, then it's not an "optimization algorithm" at all.
- IshKebab 8y agoThis is too dumbed down to be understood by anyone. :/
- fhood 8y agoIs this satire? What algorithm is faster than what algorithm?!?! They have names! "State of the art" is not the name of a damn algorithm. Why is the abstract being coy?
- LyndsySimon 8y agoTo say this is vague would be an understatement. As for "adaptive sampling" - by definition, if some paths are being discarded without analysis, then there's no guarantee that your selection is truly the best available. I'm tentatively labeling this as "hype and marketing" unless I see something more detailed and accurate.
- Hnrobert42 8y agoI think the point is that they are willing to accept the risk of not choosing the truly best available solution in return for speed. Most practical solutions for these NP problems make the same sacrifice. The authors are just claiminng to be more effecient in deriving an approximate solution.
- bhouston 8y agoWhat is this? Adaptive Monte Carlo simulation or something similar? Randomized algorithms are great but generally they do not offer consistently repeatable results which can be problematic.
- Nerdfest 8y agoThe article claims it's reducing the number of paralellizable steps, but it sounds like it's actually reducing serial operations and become more parallel.
- sxv 8y agoMore recent IEEE post [0] links to a different version of the paper [1] than the arxiv preprint linked in previous comments [2]. [0] https://spectrum.ieee.org/tech-talk/computing/software/new-optimization-algorithm-exponentially-speeds-computation https://spectrum.ieee.org/tech-talk/computing/software/new-o... [1] https://scholar.harvard.edu/files/ericbalkanski/files/the-adaptive-complexity-of-maximizing-a-submodular-function.pdf https://scholar.harvard.edu/files/ericbalkanski/files/the-ad... [2] https://arxiv.org/pdf/1804.06355.pdf https://arxiv.org/pdf/1804.06355.pdf