Label Optimal Regret Bounds for Online Local Learning
Report ID: TR-992-15Author: Lai, Kevin
Date: 2015-06-11
Pages: 50
Download Formats: |PDF|
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 (2014a) called \online local learning" captures this broad class of problems, which includes online max cut and online gambling. In the online local learning setting, we receive pairs of items from some set of items of size n, and we must label them from some set of labels of size l. Christiano (2014a) provides a Follow-the-Regularized-Leader algorithm using a log determinant regularizer that obtains regret O( p nl3T). In this thesis, we improve the analysis of Christiano's algorithm to obtain regret O( p nlT). We also 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(n1=2). We then show a similar reduction from the planted dense subgraph problem, which is believed to be even harder than the planted clique problem. This thesis is a more detailed treatment of the material from Awasthi et al. (2015), which rst showed these results.