Shang-Hua Teng: Optimization, Machine Learning, and Game Theory: From the Lens of Smoothed Analysis
Channel: Stanford Computer Science Theory
Date: 2011-10-16

Video from Beyond Worst Case Analysis Workshop 
Stanford, CA 
Sept. 19-21, 2011 

Shang-Hua Teng: Optimization, Machine Learning, and Game Theory: From the Lens of Smoothed Analysis

I will discuss some recent work on the smoothed analysis of multi-objective optimization, PAC learning, and data clustering. I will then conclude the talk by drawing the contrast between these optimization problems and equilibrium computation (in game theory & mathematical economics) from the lens of smoothed analysis.

Joint work with Daniel Spielman (Yale), Heiko Roglin (Bonn University), Adam Kalai (Microsoft New England Lab), Alex Samorodnitsky (Hebrew University), Xi Chen (Columbia University), and Xiaotie Deng (University of Liverpool).