Adam Kalai

Probabilistic and On-line Methods in Machine Learning Degree Type: Ph.D. in Computer Science
Advisor(s): Avrim Blum
Graduated: May 2001

Abstract:

On the surface, the three on-line machine learning problems analyzed in this thesis may seem unrelated. The first is an on-line investment strategy introduced by Tom Cover. We begin with a simple analysis that extends to the case of fixed-percentage transaction costs. We then describe an efficient implementation that runs in time polynomial in the number of stocks. The second problem is k-fold cross validation, a popular technique in machine learning for estimating the error of a learned hypothesis. We show that this is a valid technique by comparing it to the hold-out estimate. Finally, we discuss work towards a dynamically-optimal adaptive binary search tree algorithm.

Thesis Committee:
Avrim Blum (Chair)
Manuel Blum
Danny Sleator
Santosh Vempala

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Algorithms, on-line algorithms, machine learning, O.S.