Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions. (arXiv:2205.13056v1 [stat.ML])

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 …

arxiv learning linear ml near online learning