Tuesday, April 12, 2016 - 12:00pm to 1:00pm
Location:3305 Newell-Simon Hall
Speaker:SHIVA KAUL, Ph.D. Student http://www.cs.cmu.edu/~skkaul/
We introduce a simple new algorithm for improper, agnostic learning of halfspaces, a problem closely related to learning sparse parities with noise. It uses exponentially less data than previous algorithms, particularly ones based on fitting polynomials. It is provably correct in a wide range of settings, but not necessarily fast. The algorithm is very practical and achieves good experimental performance for both natural and artificial problems. The lynchpin of this algorithm is a new hypothesis class called smooth lists of halfspaces. They are more flexible than halfspaces, but do not require more data to train in the worst case. These new classifiers enable an iterative approach which is fundamentally different than update rules such as perceptron and multiplicative weights. Our analysis involves a dual interpretation of the algorithm as a dynamical system. Joint work with Geoff Gordon. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.