mlsanityData to 14 Oct 2026

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

arXiv 2202.13603 ↗First posted 28 Feb 2022cs.LG math.OC stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

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(σ2 d log T) + o(log T), where d is the dimension of the input vector, T is the total number of rounds. We also prove a Omega(σ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 heteroscedastic noise and propose an algorithm based on FTRL to achieve the first variance-aware regret bound.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 14 of its 49 references that are in the map. First posted on arXiv 28 Feb 2022.

Builds on

14 of 49 references.

References · 14

  1. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  2. 2013Non-stationary Stochastic Optimizationcited by 175
  3. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  4. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 64
  5. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 60
  6. 2019Exact minimax risk for linear least squares, and the lower tail of sample covariance matricescited by 34
  7. 2019Online Forecasting of Total-Variation-bounded Sequencescited by 31
  8. 2020An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Banditscited by 26
  9. 2018Uniform regret bounds over Rd for the sequential linear regression problem with the square losscited by 14
  10. 2021Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridgecited by 10
  11. 2014Heteroscedastic Treed Bayesian Optimisationcited by 9
  12. 2020Non-stationary Online Regressioncited by 6
2 more
  1. 2016Towards a Theoretical Analysis of PCA for Heteroscedastic Datacited by 3
  2. 2015Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problemcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 0; 2025: 1; 2026: 3.

5 papers.

  1. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  2. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 5
  3. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  4. 2025Second-Order Bounds for [0,1]-Valued Regression via Betting Losscited by 0
  5. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0