mlsanityData to 7 Oct 2026

Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits

arXiv 2410.01112 ↗First posted 1 Oct 2024cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We prove that single-parameter natural exponential families with subexponential tails are self-concordant with polynomial-sized parameters. For subgaussian natural exponential families we establish an exact characterization of the growth rate of the self-concordance parameter. Applying these findings to bandits allows us to fill gaps in the literature: We show that optimistic algorithms for generalized linear bandits enjoy regret bounds that are both second-order (scale with the variance of the optimal arm's reward distribution) and free of an exponential dependence on the bound of the problem parameter in the leading term. To the best of our knowledge, ours is the first regret bound for generalized linear bandits with subexponential tails, broadening the class of problems to include Poisson, exponential and gamma bandits.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 12 of its 33 references that are in the map. First posted on arXiv 1 Oct 2024.

Builds on

12 of 33 references.

References · 12

  1. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  2. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  3. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 63
  4. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
  5. 2017Generalized Self-Concordant Functions: A Recipe for Newton-Type Methodscited by 33
  6. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  7. 2020Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Banditscited by 31
  8. 2018Finite-sample analysis of M-estimators using self-concordancecited by 30
  9. 2020Self-Concordant Analysis of Generalized Linear Bandits with Forgettingcited by 29
  10. 2019Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordancecited by 28
  11. 2023Exploration via linearly perturbed loss minimisationcited by 13
  12. 2020Self-Concordant Analysis of Frank-Wolfe Algorithmscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 5.

8 papers.

  1. 2025Generalized Linear Bandits: Almost Optimal Regret with One-Pass Updatecited by 16
  2. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Banditscited by 2
  3. 2026Eluder dimension: localise it!cited by 2
  4. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  5. 2026Generalized Linear Bandits with Memorycited by 1
  6. 2025On the Sublinear Regret of Continuous K-Max Banditscited by 0
  7. 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 0
  8. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0