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

We study how tail properties of the base distribution of a NEF impose limits on the NEF: if the base distribution is subexponential (subgaussian), we show that the NEF is self-concordant with a stretch factor that grows inverse quadratically (respectively, linearly) 2.