Competitive Classification

SHARE:

Event Speaker: 

Alon Orlitsky, UCSD

Event Location: 

32-141

Card Description: 

Competitive Classification, speaker Alon Orlitsky, UCSD, Tuesday, October 16, 2012, 4:15p.m. in 32-14. Reception at 3:45pm in RSA G5 Lounge. Jointly hosted with Theory of Computation.

Event Date/Time: 

Tuesday, October 16, 2012 - 4:15pm

Reception at 3:45pm in the RSA G5 Lounge

This talk is jointly hosted with Theory of Computation.

Abstract
Building on recent computer-science and information theoretic approaches, we derive competitive algorithms for the classical classification problem. A classifier takes two training and one test
sequence, and associates the test sequence with the training sequence that was generated by the same
distribution. With no assumptions on the support size or the distance between the underlying distributions, we construct a linear-complexity classifier that requires at most n^(3/2) samples to
attain the n-sample accuracy of the best classifier designed with all essential knowledge of the two distributions. Conversely, we show that for any classifier, there are distributions that require at least n^(7/6) samples to achieve the n-sample accuracy of the best classifier designed with knowledge of the
distributions. Joint work with Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Shengjun Pan, and Ananda Suresh.

Biography
Alon Orlitsky received B.Sc. degrees in Mathematics and Electrical Engineering from Ben Gurion University in 1980 and 1981, and M.Sc. and Ph.D. degrees in Electrical Engineering from Stanford University in 1982 and 1986.

From 1986 to 1996 he was with the Communications Analysis Research Department of Bell Laboratories. He spent the following year as a quantitative analyst at D.E. Shaw and Company, an investment firm
in New York city. In 1997 he joined the University of California, San Diego, where he is currently a professor of Electrical and Computer Engineering and of Computer Science and Engineering, and directs the Information Theory and Applications Center and the Center for Wireless Communications. His research concerns information theory, statistical modeling, machine learning, and speech recognition.

Alon is a recipient of the 1981 ITT International Fellowship and the 1992 IEEE W.R.G. Baker Paper Award, and co-recipient of the 2006 Information Theory Society Paper Award. He co-authored two papers for which his students received student-paper awards: the 2003 Capocelli Prize and the 2010 ISIT Student Paper Award. He is a fellow of the IEEE, and holds the Qucalcomm Chair for Information Theory and its Applications at UCSD.