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 (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.