3 ms·
Any link to a paper?
by HelloNurse 8y ago
Any 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"