Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions
Due to the drastic gap in complexity between sequential and batch statistical
learning, recent work has studied a smoothed sequential learning setting, where
Nature is constrained to select contexts with density bounded by 1/{\sigma}
with respect to a known measure {\mu}. Unfortunately, for some function
classes, there is an exponential gap between the statistically optimal regret
and that which can be achieved efficiently. In this paper, we give a
computationally efficient algorithm that is the first to enjoy the
statistically optimal log(T/{\sigma}) regret for realizable K-wise linear
classification. We extend our results to settings where the true classifier is
linear in an over-parameterized polynomial featurization of the contexts, as
well as to a realizable piecewise-regression setting assuming access to an
appropriate ERM oracle. Somewhat surprisingly, standard disagreement-based
analyses are insufficient to achieve regret logarithmic in 1/{\sigma}. Instead,
we develop a novel characterization of the geometry of the disagreement region
induced by generalized linear classifiers. Along the way, we develop numerous
technical tools of independent interest, including a general anti-concentration
bound for the determinant of certain matrix averages.