Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits

Heyang Zhao · Dongruo Zhou · Jiafan He · Quanquan Gu

Exhibit Hall 1 #328
[ ]
[ PDF [ Poster

Abstract: We study the problem of online generalized linear regression in the stochastic setting, where the label is generated from a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical *follow-the-regularized-leader* (FTRL) algorithm to cope with the label noise. More specifically, for σ-sub-Gaussian label noise, our analysis provides a regret upper bound of O(σ2dlogT)+o(logT), where d is the dimension of the input vector, T is the total number of rounds. We also prove an Ω(σ2dlog(T/d)) lower bound for stochastic online linear regression, which indicates that our upper bound is nearly optimal. In addition, we extend our analysis to a more refined Bernstein noise condition. As an application, we study generalized linear bandits with heterogeneous noise and propose an algorithm based on FTRL to achieve the first variance-aware regret bound.

Chat is not available.