Kevin Lai will present his MSE thesis talk on Friday, May 8th, 2015 at 3pm in CS 302. The members of his committee are: Moses Charikar (advisor) and Elad Hazan Everyone is invited to attend his talk. His abstract follows below. Title: Label optimal regret bounds for online local learning Abstract: In many settings, we would like to make predictions about the local structure of a problem rather than explicitly trying to learn some global structure. For instance, given two teams from some set of teams, we may want to know if one team will beat the other, while we may not be explicitly interested in a ranking of all of the teams. A recent framework proposed by Christiano 2014 called "online local learning'' captures this broad class of problems, which includes online max cut and online gambling. Christiano provides a Follow-the-Regularized-Leader algorithm using a log determinant regularizer to obtain low regret in this setting. In this work, we improve the analysis of Christiano's algorithm and present a matching lower bound based on a reduction from the planted clique problem, which is believed to have no polynomial-time algorithm for planted cliques of size k = o(n^(1/2)). Joint work with Pranjal Awasthi, Moses Charikar, and Andrej Risteski