Learning and Smoothed Analysis
Speaker: Adam Kalai , Microsoft Research
Date: Monday, November 2 2009
Time: 4:30PM to 5:30PM
Refreshments: 3:30PM
Location: 4-370
Host: Jonathan Kelner, CSAIL
Contact: Avisha Lalla, avisha@math.mit.edu
APPLIED MATHEMATICS COLLOQUIUM
Monday November 2nd 2009
Time: 4:30 PM
Location: MIT, Building 4, Room 370
Refreshments are available in Building 2, Room 290(Math Common Room) between 3:30 – 4:30 PM
Abstract: Computational learning theory, like most of the analysis of algorithms, is based on worst-case complexity, requiring algorithms that work for every problem instance.
We apply "smoothed analysis" (Spielman and Teng, 2001) to revisit some classic open problems in learning Boolean function, such as learning sparse polynomials, decision
trees, and DNF formulas, from random examples drawn from a product distribution over the n-dimensional hypercube. We give algorithms to efficiently learn such classes.
Smoothed analysis provides guarantees that lie in between worst-case and average-case complexity.
The talk will be self contained and will not require prior knowledge in computational learning theory. It is based on joint work with Alex Samorodnitsky and Shang-Hua Teng.
******
Applied Math Colloquium Website: http://math.mit.edu/amc/fall09/
Applied Math Colloquium poster: http://math.mit.edu/amc/fall09/Adam_Kalai.pdf
Massachusetts Institute of Technology
Department of Mathematics
Cambridge, MA 02139
http://math.mit.edu
See other events happening in November 2009
