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

arXiv: https://arxiv.org/abs/2410.01112 · HTML: https://mlsanity.com/paper/2410.01112/

## Key facts

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

## Builds on (most cited first, 12 of 12)

- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [Self-Concordant Analysis of Generalized Linear Bandits with Forgetting](https://mlsanity.com/paper/2011.00819/) (2020)
- [Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance](https://mlsanity.com/paper/1902.03046/) (2019)
- [Exploration via linearly perturbed loss minimisation](https://mlsanity.com/paper/2311.07565/) (2023)
- [Self-Concordant Analysis of Frank-Wolfe Algorithms](https://mlsanity.com/paper/2002.04320/) (2020)

## Built on by (most cited first, 8 of 8)

- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [Eluder dimension: localise it!](https://mlsanity.com/paper/2601.09825/) (2026)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [On the Sublinear Regret of Continuous K-Max Bandits](https://mlsanity.com/paper/2502.13467/) (2025)
- [Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent](https://mlsanity.com/paper/2605.25590/) (2026)

## 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.