Timezone: »

 
Poster
Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions
Adam Block · Max Simchowitz

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #728
in Poster Session 6 »
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.
Keywords: Online Learning · smoothed online learning · convex geometry
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Adam Block (MIT)
Max Simchowitz (MIT)

More from the Same Authors