Fast and Simple Algorithms for Constrained Submodular Maximization

Channel:
Microsoft Research
Subscribers:
342,000
Published on ● Video Link: https://www.youtube.com/watch?v=TZT6XNoDHAY


Duration: 1:00:32
265 views
5

Submodular maximization captures both classical problems in combinatorial optimization and recent more practical applications that arise in other disciplines, e.g., machine learning and data mining. The size of the inputs in these applications is usually very large. Hence, it is interesting to devise approximation algorithms that in addition to providing a provable guarantee are also very fast and simple to use. In this talk I will present one such example and consider the problem of submodular maximization with a cardinality constraint. Additionally, more general constraints will be mentioned with some related open questions.



Other Videos By Microsoft Research


2016-06-21X1-Locally Non-linear Embeddings for Extreme Multi-label Learning
2016-06-21Large-scale Linear and Kernel Classification - Part 2
2016-06-21Submodular Optimization and Machine Learning - Part 1
2016-06-21Large-scale Linear and Kernel Classification - Part 1
2016-06-21Probability and Prejudice: Bridging the Gap Between Machine Learning and Programming Languages
2016-06-21Stan Future Plans
2016-06-21Shogun Future Plans
2016-06-21Submodular Optimization and Machine Learning - Part 2
2016-06-21Active Learning and Annotation
2016-06-21Vowpal Wabbit Future Plans
2016-06-21Fast and Simple Algorithms for Constrained Submodular Maximization
2016-06-21Manifold correspondence: a signal processing perspective
2016-06-21Distributed Machine Learning Algorithms: Communication-Computation Trade-offs - Part 1
2016-06-21Reinforcement Learning: An Introduction
2016-06-21MSR India Research Overview
2016-06-21Mathematica Tech Talk with Wolfram
2016-06-21Near Optimal LP Rounding for Correlation Clustering on Complete Graphs
2016-06-21Standing on the Shoulders of a Giant: One Person’s Experience of Turing’s Impact
2016-06-21UW - MSR Machine Learning workshop 2015 - Session 4
2016-06-21Scaling Up Reinforcement Learning
2016-06-21Debugging Machine Learning Tasks with PSI


Tags:
microsoft research
machine learning
deep neural networks