 |
|
|
|
|
|
|
|
|
|
|
|
|
 |
|
|||||||||||
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
 |
 |
|
||||||||||
 |
|
|||||||||||
 |
|
|||||||||||
 |
 |
|
||||||||||
| Seminar Schedule (Seminar Organizer: Prof. Ziv Bar-Joseph) | |
Machine Learning Lunchtime Chats
|
Spring 2007 Seminar
Date: May 10, 2007 Time: 10:00 AM - 11:00 AM Location: 4623 Wean Hall Speaker: Leonid Kontorovich Ph.D. Candidate Title: Measure Concentration of Strongly Mixing Processes with Applications Abstract: The concentration of measure phenomenon was first discovered in the 1930's by Paul Levy and has been investigated since then, with increasing intensity in recent decades. The probability-theoretic results have been gradually percolating throughout the mathematical community, finding applications in Banach space geometry, analysis of algorithms, statistics and machine learning. There are several approaches to proving concentration of measure results; we shall offer a brief survey of these. The principal contribution of this thesis is a new concentration inequality for nonproduct measures. The inequality is proved by elementary means, yet enables one, with minimal effort, to recover and generalize the best current results for Markov chains, as well as to obtain new results for hidden Markov chains and Markov trees. As an application of our inequalities, we give a strong law of large numbers for a broad class of non-independent processes. In particular, this allows one to analyze the convergence of inhomogeneous Markov Chain Monte Carlo algorithms. We also give some partial results on extending the Rademacher-type generalization bounds to processes with arbitrary dependence. Committee: John Lafferty, CMU (Chair) Kavita Ramanan, CMU Larry Wasserman, CMU Gideon Schechtman, Weizmann Institute of Science