Fast Algorithms via Convex Relaxation

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


Duration: 1:12:42
1,930 views
10

In Theoretical CS many of the fastest algorithms are obtained by considering the Linear Programming (LP) relaxation of the problem. In this talk, I will survey several results on the effectiveness of employing the more general *convex* relaxation. We discovered that for a host of classical problems, their convex relaxation is often a more natural starting point to design fast algorithms. Examples include submodular minimization, market equilibrium computation and approximate Caratheodory. Our journey will involve some fun interplay of convex optimization with tools from discrete optimization and economics.

See more at https://www.microsoft.com/en-us/research/video/fast-algorithms-via-convex-relaxation/



Other Videos By Microsoft Research


2018-03-13Bridging the Gap Between Theory and Practice in Machine Learning
2018-03-12Dreaming Contextual Memory
2018-03-12Extreme Classification in Healthcare
2018-03-12Deep Learning Approach for Extreme Multi-label Text Classification
2018-03-12A Parallel Primal-Dual Sparse Method for Extreme Classification
2018-03-12EZLearn: Exploiting Organic Supervision in Large-Scale Data Annotation
2018-03-12Extreme Multi-label Learning via Nearest Neighbor Graph Partitioning and Embedding
2018-03-12Microsoft Hands-Free Music
2018-03-12Deep Attention Mechanism for Multimodal Intelligence: Perception, Reasoning, & Expression
2018-03-09The Four Big Bets (Illustrated via a Journey in Program Synthesis)
2018-03-09Fast Algorithms via Convex Relaxation
2018-03-08CLAW: A Multifunctional Handheld Haptic Controller for Grasping, Touching, and Triggering in VR
2018-03-08Haptic Revolver: Touch, Shear, Texture, & Shape Rendering on a Reconfigurable VR Controller
2018-03-07Panel Discussion: Ai-Perception and Applications
2018-03-06Learning and Efficiency of Outcomes in Games
2018-03-06Extreme Classification - New Paradigm for Ranking and Recommendation
2018-03-06Automated Economic Reasoning with Quantifier Elimination
2018-03-05Algorithms in Strategic or Noisy Environments
2018-03-05Structured Probabilistic Models for Computational Social Science
2018-03-05Improving Machine Learning Beyond the Algorithm
2018-03-02Machine Learning and the InnerEye for Cancer Treatment with Dr. Antonio Criminisi


Tags:
microsoft research
linear programming
convex relaxation