<div dir="ltr">Dear faculty and students,<br><br>We look forward to seeing you this Tuesday, April 12th, at noon in NSH 3305 for AI lunch. To learn more about the seminar and lunch, or to volunteer to give a talk, please visit the <a href="http://www.cs.cmu.edu/~aiseminar/">AI Lunch webpage</a>. <b>We are looking for someone to give a talk on May 10th</b>.<br><br>On Tuesday, Shiva Kaul will give a talk titled "Agnostic linear classification."<br><br><b>Abstract:</b> 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.<br><br>Best,<br>Ellen and Ariel<span style="font-size:12.8px"><br></span></div>