AI Lunch and Seminar

Shiva Kaul - Agnostic linear classification

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.