---
abstract: 'We study generalized Bayesian inference under misspecification, i.e. when the model is ‘wrong but useful’. Generalized Bayes equips the likelihood with a learning rate $\eta$. We show that for generalized linear models (GLMs), $\eta$-generalized Bayes concentrates around the best approximation of the truth within the model for specific $\eta \neq 1$, even under severely misspecified noise, as long as the tails of the true distribution are exponential. We then derive MCMC samplers for generalized Bayesian lasso and logistic regression, and give examples of both simulated and real-world data in which generalized Bayes outperforms standard Bayes by a vast margin.'
bibliography:
- 'safebayesbib.bib'
---

Introduction
============

Over the last ten years it has become abundantly clear that Bayesian inference can behave quite badly under misspecification, i.e. if the model ${\ensuremath{\mathcal F}}$ under consideration is ‘wrong but useful’ [@GrunwaldL07; @ErvenGR07; @muller2013risk; @syring2017calibrating; @yao2018using; @holmes2017assigning; @grunwald2017inconsistency]. For example, @GrunwaldL07 exhibit a simple nonparametric classification setting in which, even though the prior puts positive mass on the unique distribution in ${\ensuremath{\mathcal F}}$ that is closest in KL divergence to the data generating distribution $P$, the posterior never concentrates around this distribution. @grunwald2017inconsistency give a simple linear regression problem in which standard Bayesian ridge regression, model selection and model averaging severely overfit the data (the prior does not regularize nearly enough) for small samples. They also propose a remedy for this problem: equip the likelihood with an exponent or [ *learning rate*]{} $\eta$ (see  below). Such a [*generalized Bayesian*]{} (also known as [*fractional*]{} or [ *tempered*]{} Bayesian) approach was considered earlier by e.g. [@barron1991minimum; @WalkerH02; @zhang2006information]. In practice, $\eta$ will usually (but not always — see Section \[sec:lassoandhs\] below) be chosen smaller than one, making the prior have a stronger regularizing influence. @grunwald2017inconsistency show that for Bayesian ridge regression and model selection/averaging, this results in excellent performance, being competitive with standard Bayes if the model is correct and very significantly outperforming standard Bayes if it is not. Extending Zhang’s ([-@zhang2006epsilon; -@zhang2006information]) earlier work, @grunwald2016fast (GM from now on) show that, under what was earlier called the $\bar\eta$-[*central condition*]{} (Definition \[def:central\] below), generalized Bayes with a specific finite learning rate $\bar\eta$ (usually $\neq 1$) will indeed, with high probability, concentrate in the neighborhood of the ‘best’ $f \in {\ensuremath{\mathcal F}}$, closest in KL divergence to $P$. Yet three important parts of the story are missing in this existing line of work: (1) Can Grünwald-Van Ommen-type examples, showing failure of standard Bayes $(\eta = 1)$ and empirical success of generalized Bayes with the right $\eta$, be given more generally, for different priors $\pi$ (say of lasso-type ($\pi(f) \propto \exp(- \lambda \| f\|_1)$) rather than ridge-type $\pi(f) \propto \exp(-\lambda \| f \|_2^2)$), and for different models, say for [*generalized*]{} linear models (GLMs)? (2) Can we find examples of generalized Bayes outperforming standard Bayes with real-world data rather than with toy problems such as those considered by Grünwald and Van Ommen? (3) Under what circumstances does the central condition — which allows for good theoretical behavior of generalized Bayes — hold for GLMs?

Here we show that the answer to all three questions is affirmative:[^1] in Section \[sec:genglm\] in Section \[sec:bad\] below, we give a toy example on which the Bayesian lasso and the Horseshoe estimator fail; later in the paper, in Section \[sec:examples\] we also give a toy example on which standard Bayes logistic regression fails, and two real-world data sets on which standard Bayesian lasso and Horseshoe regression fail; in all cases generalized Bayes with the right $\eta$ shows much better performance. In Section \[sec:genglm\], we show that for GLMs, even if the noise is severely misspecified, as long as the distribution of the predictor variable $Y$ has exponentially small tails (which is automatically the case in classification, where the domain of $Y$ is finite), the central condition holds for some $\eta > 0$, so GM’s theoretical results suggest that generalized Bayes with this $\eta$ should lead to good results — this is corroborated by our experimental results in Section \[sec:examples\]. These findings are not obvious: one might for example think that the sparsity-inducing prior used by Bayesian lasso regression circumvents the need for the additional regularization induced by taking an $\eta < 1$. Indeed in the original setting of Grünwald and Van Ommen, the standard Bayesian lasso $(\eta =1)$ succeeds; yet Example \[ex:basic\] below shows that under a modification of their example, it fails after all. In order to demonstrate the failure of standard Bayes and the success of generalized Bayes, we devise (in Section \[sec:sampling\]) MCMC algorithms for generalized Bayes posterior sampling for Bayesian lasso and logistic regression; these algorithms are an additional contribution of this paper.

Below we first define our setting more precisely, we then (Section \[sec:bad\]) give a first example of bad standard-Bayesian behavior. Section \[sec:consistency\] recalls a theorem from GM indicating that under the $\bar\eta$-central condition, generalized Bayes for $\eta < \bar\eta$ should perform well. We then present new theoretical results, showing that, if $|Y|$ has exponential tails and the noise (not the regression function) is misspecified, then the central condition does hold for GLMs. We next (Section \[sec:sampling\]), present our algorithms for generalized Bayesian posterior sampling, and we continue (Section \[sec:examples\]) to empirically demonstrate how generalized Bayes outperforms standard Bayes under misspecification. All proofs are in Appendix \[app:proofs\].

The setting
===========

A *learning problem* can be characterized by a tuple $(P, {\ensuremath{\ell}}, {\ensuremath{\mathcal F}})$, where ${\ensuremath{\mathcal F}}$ is a set of predictors, also referred to as [*model*]{}, $P$ is a distribution on sample space ${\ensuremath{\mathcal Z}}$ and ${\ensuremath{\ell}}: {\ensuremath{\mathcal F}}\times {\ensuremath{\mathcal Z}}\rightarrow {{\mathbb R}}\cup \{\infty \}$ is a loss function. We denote by ${\ensuremath{\ell}}_f(z) \coloneqq {\ensuremath{\ell}}(f,z)$ the loss of predictor $f \in {\ensuremath{\mathcal F}}$ under outcome $z \in {\ensuremath{\mathcal Z}}$. If $Z \sim P$, we abbreviate ${\ensuremath{\ell}}_f(Z)$ to ${\ensuremath{\ell}}_f$. In all our examples, ${\ensuremath{\mathcal Z}}= {\ensuremath{\mathcal X}}\times {\ensuremath{\mathcal Y}}$. We obtain e.g. standard (random-design) regression with squared loss by taking ${\ensuremath{\mathcal Y}}= {{\mathbb R}}$ and ${\ensuremath{\mathcal F}}$ to be some subset of the class of all functions $f: {\ensuremath{\mathcal X}}\rightarrow {{\mathbb R}}$ and, for $z=(x,y)$, ${\ensuremath{\ell}}_f(x,y) = (y -f(x))^2$; logistic regression is obtained by taking ${\ensuremath{\mathcal F}}$ as before, ${\ensuremath{\mathcal Y}}= \{-1,1\}$ and ${\ensuremath{\ell}}_f(x,y) = \log (1 + \exp(- y f(x))$. We get conditional density estimation by taking $\{p_f(Y \mid X) :f \in {\ensuremath{\mathcal F}}\}$ to be a family of conditional probability mass or density functions (defined relative to some measure $\mu$), extended to $n$ outcomes by the i.i.d. assumption, and taking conditional log-loss $\ell_f(x,y) \coloneqq - \log p_f(y \mid x)$.

We are given an i.i.d. sample $Z^n \coloneqq Z_1, Z_2, \ldots, Z_n \sim P$ where each $Z_i$ takes values in ${\ensuremath{\mathcal Z}}$, and we consider, as our learning algorithm, the [ *generalized Bayesian posterior*]{}, also known as the [*Gibbs posterior*]{}, $\Pi_n$ on ${\ensuremath{\mathcal F}}$, defined by its density $$\label{eq:bayesgenpost}
\pi_n (f) 
\coloneqq  \frac{\exp\left(-\eta \sum_{i=1 }^{n} {\ensuremath{\ell}}_f(z_i) \right) \cdot \pi_0(f)}{\int_{\mathcal{F}}\exp\left(-\eta \sum_{i= 1 }^{n} {\ensuremath{\ell}}_f(z_i)\right) \cdot \pi_0(f) \text{d} \rho(f)},$$ where $\eta>0$ is the *learning rate*, and $\pi_0$ is the density of some prior distribution $\Pi_0$ on ${\ensuremath{\mathcal F}}$ relative to an underlying measure $\rho$. Note that, in the conditional log-loss setting, we get that $$\label{eq:genbayeslik}
  \pi_n (f) \propto \prod_{i=1}^n (p_f(y_i \mid x_i))^{\eta} \pi_0(f),$$ which, if further $\eta=1$, reduces to standard Bayesian inference. While GM’s result (quoted as Theorem \[thm:metric\] below) works for arbitrary loss functions, in our novel results of this paper, Theorem \[thm:expfam-exptails\] and our empirical simulations, we concentrate on (generalized) linear models, in which has two equivalent interpretations: first, in terms of the original loss functions $\ell_f$; second, in terms of the conditional likelihood $p_f$. For example, for regression, with fixed $\eta$, with ${\ensuremath{\ell}}_f(x,y) = (y -f(x))^2$, (\[eq:bayesgenpost\]) induces the same posterior distribution $\pi_n(f)$ over ${\ensuremath{\mathcal F}}$ as does (\[eq:genbayeslik\]) with the conditional distributions $p_f(y|x) \propto \exp(-(y-f(x))^2$, which is again the same with (\[eq:bayesgenpost\]) with $\ell_f$ replaced by the conditional log-loss $\ell' _f(x,y) \coloneqq - \log p_f(y|x)$, giving a likelihood corresponding to Gaussian errors with a particular fixed variance; an analogous statement holds for logistic regression. Thus, all our examples can be interpreted in terms of (\[eq:genbayeslik\]) for a model which is misspecified, i.e. the density of $P(Y|X)$ is not equal to $p_f$ for any $f \in {\ensuremath{\mathcal F}}$. As is customary (see, e.g. GM or @bartlett2005local), we assume throughout that there exists an optimal ${{f^*}}\in {\ensuremath{\mathcal F}}$ that achieves the smallest *risk* (expected loss) ${\operatorname{\mathbf{E}}}[{\ensuremath{\ell}}_{{{f^*}}}(Z)] = \inf_{f \in {\ensuremath{\mathcal F}}} {\operatorname{\mathbf{E}}}[{\ensuremath{\ell}}_f(Z)]$. If ${\ensuremath{\mathcal F}}$ is a GLM, the risk minimizer again has additional interpretations: first, $f^*$ minimizes, among all $f \in {\ensuremath{\mathcal F}}$, the conditional KL divergence ${\bf E}_{(X,Y) \sim P} [\log \left( p(Y|X)/ p_f(Y|X) \right)]$ to the true distribution $P$. Second, if there is an $f \in {\ensuremath{\mathcal F}}$ with ${\bf E}_{X,Y \sim P}[Y \mid X] = f(X)$ (i.e. ${\ensuremath{\mathcal F}}$ contains the [*true regression function*]{}, or equivalently, [*true conditional mean*]{}), then the risk minimizer satisfies $f^* = f$.

Bad Behavior of Standard Bayes {#sec:bad}
------------------------------

\[ex:basic\][ We consider a Bayesian lasso regression setting [@Park] with random design, with a Fourier basis. We sample data $Z_i = (X_i,
    Y_i)$ i.i.d. $\sim P$, where $P$ is defined as follows: we first sample [*preliminary*]{} $(X'_i,Y'_i)$ with $X'_i \overset{i.i.d.}{\sim}$ Uniform$[-1,1]$; the dependent variable $Y'_i$ is set to $Y'_i = 0
    + \epsilon$, with $\epsilon \sim {\ensuremath{\mathcal N}}(0, \sigma^2)$ for some fixed value of $\sigma$, independently of $X'_i$. In other words: the true distribution for $(X'_i, Y'_i)$ is ‘zero with Gaussian noise’. Now we toss a fair coin for each $i$. If the coin lands heads, we set the actual $(X_i,Y_i) \coloneqq (X'_i,Y'_i)$, i.e. we keep the $(X'_i, Y'_i)$ as they are, and if the coin lands tails, we put the pair to zero: $(X_i, Y_i) \coloneqq (0,0)$. We model the relationship between $X$ and $Y$ with a $p$th order Fourier basis. Thus, ${\ensuremath{\mathcal F}}= \{ f_{\beta}: \beta \in {{\mathbb R}}^{2p+1} \}$, with $f_{\beta}(x)$ given by $$\left\langle \beta,  \frac{1}{\pi} \cdot  \left[2^{-1/2}, \cos(x), \sin(x), \cos(2x),  {\hbox to 1em{.\hss.\hss.}},  \sin(px)\right] \right\rangle,$$ and the $\eta$-posterior is defined by (\[eq:bayesgenpost\]) with $\ell_{f_{\beta}}(x,y) = (y- f_{\beta}(x))^2$; the prior is the Bayes lasso prior whose definition we recall in Section \[sec:lassosamp\]. Since our ‘true’ regression function ${\bf E}[Y_i \mid X_i]$ is $0$, in an actual sample around $50\%$ of points will be noiseless, *easy* points, lying on the true regression function. The actual sample of $(X_i,Y_i)$ having less noise then the original sample $(X'_i, Y'_i)$, we would thus expect our Baysian lasso regression to learn the correct regression function, but as we see in the blue line in Figure \[fig:ex1\], it overfits and learns the noise instead (later on (Figure \[fig:risk-simulaties resultaten\] in Section \[sec:lassoandhs\]) we shall see that, not surprisingly, this results in terrible predictive behavior). By removing the noise in half of the datapoints, we misspecified the model: we made the noise heteroscedastic, whereas the model assumes homoscedastic noise. Thus, in this experiment the [ *model is wrong*]{}. Still, the distribution in ${\ensuremath{\mathcal F}}$ closest to the true $P$, both in KL divergence and in terms of minimizing the squared error risk, is given by (the conditional distribution corresponding to) $Y_i = 0 + \epsilon_i$, where $\epsilon_i$ is i.i.d. $\sim {\ensuremath{\mathcal N}}(0,\sigma^2)$. While this element of ${\ensuremath{\mathcal F}}$ is in fact [*favored*]{} by the prior (the lasso prior prefers $\beta$ with small $\|\beta\|_1$), nevertheless, for small samples, the standard Bayesian posterior puts most if its mass at $f$ with many nonzero coefficients. In contrast, the generalized posterior with $\eta = 0.25$ gives excellent results here. To learn this $\eta$ from the data, we can use the Safe-Bayesian algorithm of @Grunwald12. The result is depicted as the red line in Figure \[fig:ex1\]. Implementation details are in Section \[sec:lassosamp\] and Appendix \[app:impl\]; the details of the figure are in Appendix \[ap:detailsfigures\]. ]{}

![‘True’ distribution (green) and predictions of standard Bayes (blue) and SafeBayes (red), $n=50$. \[fig:ex1\]](Eersteplaatje-eps-converted-to.pdf){width="50.00000%"}

The example is similar to that of @grunwald2017inconsistency, who use multidimensional $X$ and a ridge (normal) prior on $\|\beta\|$; in their original example standard Bayes succeeds when equiped with a lasso prior; by using a trigonometric basis we can let it ‘fail’ after all. @grunwald2017inconsistency relate the potential for the overfitting-type of behavior of standard Bayes, as well as the potential for full (i.e. even holding as $n \rightarrow \infty$) inconsistency as noted by @GrunwaldL07 to properties of the Bayes predictive distribution ${\bar{p}(Y _{n+1} \mid X_{n+1}, Z^n)} \coloneqq {\int p_f(Y_{n+1}
  \mid X_{n+1}) \pi_n(f \mid Z^n) \text{d} \rho(f)}$. Being a mixture of $f \in {\ensuremath{\mathcal F}}$, $\bar{p}(Y_{n+1} \mid X_n+1)$, is a member of the convex hull of densities ${\ensuremath{\mathcal F}}$ but not necessarily of ${\ensuremath{\mathcal F}}$ itself. As explained by Grünwald and Van Ommen, severe overfitting may take place if $\bar{p}(Y_{n+1} \mid X_{n+1}, Z^n)$ is ‘far’ from any of the distributions in ${\ensuremath{\mathcal F}}$. It turns out that this is exactly what happens in the lasso example above, as we see from Figure \[fig:predvar\] (details in Appendix \[ap:detailsfigures\]). In this figure we plotted the datapoints as $(X_i, 0)$ to indicate their location, from which we see that the predictive variance of standard Bayes fluctuates, and is small around the data points and large elsewhere, whereas obviously, for every density $p_f$ in our model ${\ensuremath{\mathcal F}}$, the variance is fixed independently of $X$ — and thus $\bar{p}(Y_{n+1} \mid X_{n+1}, Z^n)$ is indeed very far from any particular $p_f$ with $f \in {\ensuremath{\mathcal F}}$. In contrast, for the generalized Bayesian lasso with $\eta = 0.25$, the corresponding predictive variance is almost constant, thus at the level $\eta = 0.25$, the predictive distribution is almost ‘in-model’ (in machine learning terminology, we may say that $\bar{p}$ is ‘proper’ [@shalev2014understanding]; and then the overfitting behavior does not occur anymore.

![Variance of Predictive Distribution $\bar{p}(Y_{n+1} \mid X_{n+1}, Z^n)$ for a single run with $n=50$.[]{data-label="fig:predvar"}](predvar-eps-converted-to.pdf){width="50.00000%" height="4.5cm"}

When Generalized Bayes Concentrates {#sec:consistency}
-----------------------------------

Having just seen bad behavior for $\eta=1$, we now recall some results from GM, who show that, under some conditions, generalized Bayes, for appropriately chosen $\eta$, does concentrate at fast rates even under misspecification. We first recall a (very special case) of the asymptotic behavior under misspecification theorem of GM. GM bound (a) the [*misspecification metric*]{} ${{d}}_{\bar\eta}$ in terms of (b) the [*information complexity*]{}. The bound (c) holds under a simple condition on the learning problem that was termed the [*central condition*]{} by @erven2015fast. Before presenting the theorem we explain (a)-(c). As to (a), we define the [ *misspecification metric*]{} ${{d}}_{\bar\eta}$ in terms of its square by $$\begin{aligned}
{{d}}^2_{\bar\eta}(f,f') \coloneqq \frac{2}{\bar{\eta}} \left(1- \int \sqrt{p_{f,\bar\eta}(z) p_{f',\bar\eta}(z)} \text{d} \mu(z) \right)\end{aligned}$$ which is the squared Hellinger distance between $p_{f,\bar\eta}$ and $p_{f',\bar\eta}$ defined as $$\nonumber
p_{f,\bar\eta}(z) 
\coloneqq p(z) \frac{\exp(-\bar\eta {L_{f}}(z))}{{\operatorname{\mathbf{E}}}[\exp(-\bar\eta {L_{f}}(Z))]},$$ where ${L_{f}} = {\ensuremath{\ell}}_f - {\ensuremath{\ell}}_{{{f^*}}}$ is the [*excess loss*]{} of $f$. GM show that ${{d}}_{\bar\eta}$ defines a metric for all $\bar\eta > 0$. If $\bar\eta=1$, $\ell$ is log-loss, and the model is well-specified, then it is straightforward to check $p_{f,\bar\eta} = p_f$ and ${{d}}_{\bar\eta}$ becomes the standard Hellinger metric.

As to (b), we denote by ${\mathrm{IC}}_{n, \eta}(\Pi_0)$ the information complexity, defined as: $$\begin{aligned}
{\mathrm{IC}}_{n,\eta}(\Pi_0) 
\coloneqq {\ensuremath{\mathbf E}}_{{\underline{f}} \sim {\ensuremath{\Pi}}_n} \left[ \frac{1}{n} \sum_{i=1}^n {L_{{\underline{f}}}(Z_i)} \right]
+ \frac{{\text{\sc KL}}( {\ensuremath{\Pi}}_n \operatorname*{\|}{\ensuremath{\Pi_0}})}{\eta \cdot n  } = 
\nonumber \hspace*{-0.5 cm} \\ \  \hspace*{-2 cm} \ \label{eq:bayesmarginal} 
- \frac{1}{ \eta n} \log \int \pi_0(f) e^{- \eta \sum_{i=1}^n \ell_f(Z_i)} \text{d} \rho(f) -
\sum_{i=1}^n \ell_{f^* }(Z_i),\end{aligned}$$ where ${\underline{f}}$ denotes the predictor sampled from the posterior $\Pi_n$; we suppress dependency of ${\mathrm{IC}}$ on ${{f^*}}$ in the notation. The fact that both lines above are equal (noticed by, among others, @zhang2006information; GM give an explicit proof) allows us to write the information complexity in terms of a generalized Bayes predictive density which is also known as [ *extended stochastic complexity*]{} [@Yamanishi98]. It also plays a central role in the field of prediction with expert advice as the [*mix-loss*]{} [@erven2015fast; @CesaBianchiL06] and coincides with the minus log of the standard Bayes predictive density if $\eta=1$ and $\ell$ is log-loss. It can be thought of as a complexity measure analogous to VC dimension and Rademacher complexity.

As to (c), GM’s result holds under the *central condition* ([@li1999estimation]; name due to [@erven2015fast]) which expresses that, for some fixed $\bar\eta > 0$, for all fixed $f$, the probability that its loss exceeds that of the optimal $f^*$ by $a/\bar\eta$ is exponentially small in $a$:

\[def:central\] Let $\bar{\eta} > 0$. We say that ${({P},{\ensuremath{\ell}},{\mathcal{F}})}$ satisfies the *$\bar\eta$-strong central condition* if for all $f \in {\ensuremath{\mathcal F}}$: ${\operatorname{\mathbf{E}}}\left[e^{-\bar\eta {L_{f}}}  \right] \leq 1$.

As straightforward rewriting shows, this condition holds [ *automatically*]{}, for any $\bar\eta \leq 1$ in the density estimation setting, if the model is correct; @erven2015fast provide some other cases in which it holds, and show that many other conditions on $\ell$ and $P$ that allow fast rate convergence that have been considered before in the statistical and on-line learning literature, such as [*exp-concavity*]{} [@CesaBianchiL06], the [*Tsybakov*]{} and [*Bernstein*]{} conditions [@bartlett2005local; @Tsybakov04] and several others, can be viewed as special cases of the central condition; yet they don’t discuss GLMs. Here is GM’s result:

\[thm:metric\] Suppose that the $\bar{\eta}$-strong central condition holds. Then for any $0 < \eta < \bar\eta$, the metric ${{d}}_{\bar\eta}$ satisfies $$\begin{aligned}
    {\operatorname{\mathbf{E}}}_{Z^n \sim P} {\operatorname{\mathbf{E}}}_{{\underline{f}} \sim {\ensuremath{\Pi}}_n} \left[ {{d}}^2_{\bar\eta}({{f^*}}, {\underline{f}}) \right] 
    \leq  C_{\eta} \cdot {\operatorname{\mathbf{E}}}_{Z^n \sim P}\left[ {\mathrm{IC}}_{n,\eta}(\Pi_0) \right]
    \end{aligned}$$ with $C_{\eta} = \eta / (\bar\eta- \eta)$. In particular, $C_{\eta} < \infty$ for $0 < \eta < \bar\eta$, and $C_{\eta} = 1$ for $\eta = \bar\eta/2$.

Thus, we expect the posterior to concentrate at a rate dictated by ${\bf E}[{\mathrm{IC}}_{n,\eta}]$ in neighborhoods of the best (risk-minimizing, KL optimal, or even true regression function) $f^*$. The misspecification metric ${{d}}^2_{\bar\eta}$ on the left hand side is a weak metric, however, in Appendix \[sec:witness\] we show that we can replace it by stronger notions such as KL-divergence, squared error or logistic loss. Theorem \[thm:metric\] is a generalization to the the misspecified setting of previous results (e.g. @zhang2006epsilon [@zhang2006information]). In the well-specified case, Zhang, as well as several other authors [@WalkerH02; @martin2017empirical], state a result that holds for any $\eta < 1$ but not $\eta=1$. This shows that there is an advantage to taking $\eta$ slightly smaller than one even when the model is well-specified (for more details see @zhang2006epsilon).

To make the theorem work for GLMs under misspecification, we must verify (a) that the central condition still holds (which is in general not guaranteed) and that (b) the information complexity is sufficiently small. As to (a), in the following section we show that the central condition holds (with $\bar\eta$ usually $\neq 1$) for $1$-dimensional exponential families and high-dimensional generalized linear models (GLMs) if the noise is misspecified, as long as $P$ has exponentially small tails, and we relate $\bar\eta$ to the variance of $P$. As to (b), if the model is correct (the conditional distribution $P(Y \mid X)$ has density $f$ equal to $p_f$ with $f \in {\ensuremath{\mathcal F}}$), where ${\ensuremath{\mathcal F}}$ represents a $d$-dimensional GLM, then it is known (see e.g. @zhang2006information) that, for any prior $\Pi_0$ with continuous, strictly positive density on ${\ensuremath{\mathcal F}}$, the information complexity satisfies $$\label{eq:bic}
   {\bf E}_{Z^n \sim P} \left[   {\mathrm{IC}}_{n,\eta}(\Pi_0)\right] = O \left( \frac{d}{n} \cdot \log n
      \right),$$ which leads to bounds within a log-factor of the minimax optimal rate (among all possible estimators, Bayesian or not), which is $O(d/n)$. While such results were only established for the well-specified case, in Proposition \[prop:tenerife\] below, we show that, for GLMs, they continue to hold for the misspecified case.

Generalized GLM Bayes {#sec:genglm}
=====================

Below we first show that the central condition holds for natural univariate exponential families; we then extend this result to the GLM case, and establish bounds in information complexity of GLMs. Let the class ${\ensuremath{\mathcal F}}= \{ p_{\theta}: \theta \in \Theta\}$ be a univariate natural exponential family of distributions on ${\ensuremath{\mathcal Z}}= {\ensuremath{\mathcal Y}}$, represented by their densities, indexed by natural parameter $\theta \in \Theta
\subset {{\mathbb R}}$ [@BarndorffNielsen78]. The elements of this restricted family have probability density functions $$\begin{aligned}
\label{eq:expfamdef}
p_\theta(y) \coloneqq \exp( \theta y - F(\theta) + r(y) ) ,\end{aligned}$$ for log-normalizer $F$ and carrier measure $r$. We denote the corresponding distribution as $P_{\theta}$. In the first part of the theorem below we assume that $\Theta$ is restricted to an arbitrary closed interval $[\underline\theta,\bar\theta]$ with $\underline\theta < \bar\theta$ that resides in the interior of the natural parameter space $\bar{\Theta} = \{ \theta: F(\theta) < \infty\}$. Such $\Theta$ allow for a simplified analysis because within $\Theta$ the log-normalizer $F$ as well as all its derivatives are uniformly bounded from above and below; see in Appendix \[app:proofs\]. As is well-known (see e.g. @BarndorffNielsen78), exponential families can equivalently be parameterized in terms of the mean-value parameterization: there exists a $1$-to-$1$ strictly increasing function $\mu: \bar{\Theta} \rightarrow {{\mathbb R}}$ such that ${\operatorname{\mathbf{E}}}_{Y \sim
  P_{\theta}}[Y] = \mu(\theta)$. As is also well-known, the density $p_{{{f^*}}} \equiv p_{\theta^*}$ within ${\ensuremath{\mathcal F}}$ minimizing KL divergence to the true distribution $P$ satisfies $\mu(\theta^*) = {\bf E}_{Y\sim
  P}[Y]$, whenever the latter quantity is contained in $\mu(\Theta)$ [@Grunwald07]. In words, the best approximation to $P$ in ${\ensuremath{\mathcal F}}$ in terms of KL divergence has the same mean of $Y$ as $P$.

\[thm:expfam-exptails\] Consider a learning problem ${({P},{\ensuremath{\ell}},{\mathcal{F}})}$ with ${\ensuremath{\ell}}_{\theta}(y) = -
  \log p_{\theta}(y)$ the log loss and ${\ensuremath{\mathcal F}}= \{p_{\theta}: \theta \in
  \Theta\}$ a univariate exponential family as above.\
(1). Suppose that $\Theta = [\underline\theta,\bar\theta]$ is compact as above and that $\theta^* = \arg\min_{\theta \in \bar\Theta} D(P\|
  P_{\theta})$ lies in $\Theta$. Let $\sigma^2> 0$ be the true variance ${\operatorname{\mathbf{E}}}_{Y \sim P}(Y - E[Y])^2$ and let $(\sigma^*)^2$ be the variance ${\operatorname{\mathbf{E}}}_{Y \sim P_{\theta^*}}(Y - E[Y])^2$ according to $\theta^*$. Then (i) for all $\bar\eta >
  (\sigma^*)^2/\sigma^2$, the $\bar\eta$-central condition does [ *not*]{} hold. (ii) Suppose there exists $\eta^{\circ} > 0$ such that [$\bar{C} \coloneqq {\operatorname{\mathbf{E}}}_P[\exp(\eta^{\circ} |Y|)] < \infty$.]{} Then there exists $\bar\eta > 0$, depending only on $\eta^{\circ}$, $\bar{C}, \underline{\theta}$ and $\overline{\theta}$ such that the $\bar\eta$-central condition holds. Moreover, (iii), for all $\delta > 0$, there is an $\epsilon > 0$ such that, for all $\bar\eta \leq (\sigma^*)^2/\sigma^2 - \delta$, the $\bar{\eta}$-central condition holds relative to the restricted model ${\ensuremath{\mathcal F}}_{\epsilon} = \{p_{\theta}: \theta \in [\theta^*-
    \epsilon,\theta^*+\epsilon]$}.

[*(2). Suppose that $P$ is Gaussian with variance $\sigma^2> 0$ and that ${\ensuremath{\mathcal F}}$ indexes a full Gaussian location family. Then $\bar\eta$-central holds iff $\bar\eta \leq
        (\sigma^*)^2/\sigma^2$.* ]{}

We provide (iii) just to give insight — ‘locally’, i.e. in restricted models that are small neighborhoods around the best-approximating $\theta^*$, the smallest $\bar\eta$ for which central holds is determined by a ratio of variances. The final part shows that for the Gaussian family, the same holds not just locally but globally (note that we do not make the compactness assumption on $\Theta$ there); we warn the reader though that the standard posterior ($\eta=1$) based on a model with fixed variance $\sigma^*$ is quite different from the generalized posterior with $\eta = (\sigma^*)^2/\sigma^2$ and a model with variance $\sigma^2$ [@grunwald2017inconsistency]. Finally, while in practical cases we often find $\bar\eta < 1$ (suggesting that Bayes may only succeed if we learn ‘slower’ than with the standard $\eta =1$, i.e. the prior becomes more important), the result shows that we can also very well have $\bar\eta > 1$; a practical example is given at the end of Section \[sec:examples\]. Theorem \[thm:expfam-exptails\] is new and supplements the various examples of ${\ensuremath{\mathcal F}}$ which satisfy the central condition given by . In the proposition we require that both tails of $Y$ have exponentially small probability.

#### Central Condition: GLMs

Let ${\ensuremath{\mathcal F}}$ be the generalized linear model [@McCullaghN89] (GLM) indexed by parameter $\beta \in {\ensuremath{\mathcal B}}\subset {{\mathbb R}}^d$ with link function $g: {{\mathbb R}}\rightarrow
{{\mathbb R}}$. By definition this means that there exists a set ${\ensuremath{\mathcal X}}\subset
{{\mathbb R}}^{d}$ and a univariate exponential family ${\ensuremath{\mathcal Q}}= \{ p_{\theta} : \theta \in
\bar\Theta \}$ on ${\ensuremath{\mathcal Y}}$ of the form such that the conditional distribution of $Y$ given $X=x$ is, for all possible values of $x \in {\ensuremath{\mathcal X}}$, a member of the family ${\ensuremath{\mathcal Q}}$, with mean-value parameter $g^{-1}(\langle \beta, x  \rangle)$. Then the class ${\ensuremath{\mathcal F}}$ can be written as ${\ensuremath{\mathcal F}}= \{ p_\beta: \beta \in
\mathcal{B}\}$, a set of conditional probability density functions such that $$\begin{aligned}
p_\beta(y \mid x) 
\coloneqq \exp \bigl( \theta_x(\beta) y - F(\theta_x(\beta)) + r(y) \bigr),
\label{eq:toulon}\end{aligned}$$ where $\theta_x(\beta) \coloneqq \mu^{-1}(g^{-1}(\langle \beta, x  \rangle))$, and $\mu^{-1}$, the inverse of $\mu$ defined above, sends mean parameters to natural parameters. We then have ${\operatorname{\mathbf{E}}}_{P_\beta} [ Y \mid X ] =
g^{-1}(\langle \beta, X  \rangle)$, as required.

\[prop:tenerife\] Under the following three assumptions, the learning problem ${({P},{\ensuremath{\ell}},{\mathcal{F}})}$ with ${\ensuremath{\mathcal F}}$ as above satisfies the $\bar\eta$-central condition for some $\bar\eta>0$ depending only on the parameters of the problem:

1.  (Conditions on $g$): the inverse link function $g^{-1}$ has bounded derivative on the domain ${\ensuremath{\mathcal B}}\times {\ensuremath{\mathcal X}}$, and the image of the inverse link on the same domain is a bounded interval in the interior of the mean-value parameter space $\{ \mu\in {{\mathbb R}}: \mu = {\operatorname{\mathbf{E}}}_{Y \sim q}[Y]\; :\; q \in {\ensuremath{\mathcal Q}}\}$ (for all standard link functions, this can be enforced by restricting ${\ensuremath{\mathcal B}}$ and ${\ensuremath{\mathcal X}}$ to an (arbitrarily large but still) compact domain).

2.  (Condition on ‘true’ $P$): for some $\eta > 0$ we have\
    ${\sup}_{x \in {\ensuremath{\mathcal X}}} {\operatorname{\mathbf{E}}}_{Y \sim P}[\exp(\eta | Y|) \mid X=x] < \infty$.

3.  (Well-specification of conditional mean): there exists $\beta^{\circ} \in {\ensuremath{\mathcal B}}$ such that ${\operatorname{\mathbf{E}}}[ Y \mid
        X ] = g^{-1}(\langle \beta^{\circ}, X  \rangle)$.

A simple argument (differentiation with respect to $\beta$) shows that under the third condition, it must be the case that $\beta^{\circ} = \beta^*$, where $\beta^* \in {\ensuremath{\mathcal B}}$ is the index corresponding to the density $p_{{{f^*}}} \equiv p_{\beta^*}$ within ${\ensuremath{\mathcal F}}$ that minimizes KL divergence to the true distribution $P$. Thus, our conditions imply that ${\ensuremath{\mathcal F}}$ contains a $\beta^*$ which correctly captures the conditional mean (and this will then be the risk minimizer); thus, as is indeed the case in Example \[ex:basic\], the regression function must be well-specified but the noise can be severely misspecified.

We stress that the three conditions have very different statuses. The first is mathematically convenient; it can be enforced by truncating parameters and data, which is awkward but may not lead to substantial deterioriation in practice. Whether it is even really needed or not is not clear (and may in fact depend on the chosen exponential family). The second condition is really necessary — as can immediately be seen from Definition \[def:central\], the strong central condition cannot hold if $Y$ has polynomial tails and for some $f$ and $x$, ${\ensuremath{\ell}}_f(x,Y)$ increases polynomially in $Y$ (in Section 6 of their paper, GM consider weakenings of the central condition that still work in such situations). For the third condition, however, we suspect that there are many cases in which it does not hold yet still the strong central condition holds; so then the GM convergence result would still be applicable under ‘full misspecification’; investigating this will be the subject of future work.

#### GLM Information Complexity

To apply Theorem \[thm:metric\] to get convergence bounds for exponential families and GLMs, we need to verify that the central condition holds (which we just did) and we need to bound the information complexity, which we proceed to do now. It turns out that the bound on ${\mathrm{IC}}_{n,\eta}$ of $O( (d/n) \log n)$ of (\[eq:bic\]) continues to hold unchanged under misspecification, as is an immediate corollary of applying the following proposition to the definition of ${\mathrm{IC}}_{n,\eta}$ given above (\[eq:bayesmarginal\]):

\[prop:entroboundb\] Let ${({P},{\ensuremath{\ell}},{\mathcal{F}})}$ be a learning problem with ${\ensuremath{\mathcal F}}$ a GLM satisfying Conditions 1–3 above. Then for all $f \in {\ensuremath{\mathcal F}}$, $ {\operatorname{\mathbf{E}}}_{X,Y \sim P}[L_f] = {\operatorname{\mathbf{E}}}_{X,Y \sim P_{{{f^*}}}} [L_f].
    $

This result follows almost immediately from the ‘robustness property of exponential families’ (Chapter 19 of @Grunwald07); for convenience we provide a proof in Appendix \[app:proofs\]. The result implies that any bound in ${\mathrm{IC}}_{n,\eta}(\Pi_0)$ for a particular prior in the well-specified GLM case, in particular (\[eq:bic\]), immediately transfers to the same bound for the misspecified case, as long as our regularity conditions hold, allowing us to apply Theorem \[thm:metric\] to obtain the parameteric rate for GLMs under misspecification.

MCMC Sampling {#sec:sampling}
=============

Below we devise MCMC algorithms for obtaining samples from the $\eta$-generalized posterior distribution for two problems: regression and classification. In the regression context we consider one of the most commonly used sparse parameter estimation techniques, the lasso. For classification we use the logistic regression model. In our experiments in Section \[sec:examples\], we compare the performance of generalized Bayesian lasso with Horseshoe regression [@horseshoe]. The derivations of samplers are given in Appendix \[app:impl\].

Bayesian lasso regression {#sec:lassosamp}
-------------------------

Consider the regression model $Y= X \beta+{\varepsilon}$, where $\beta\in{\mathbb{R}}^p$ is the vector of parameters of interest, , , and is a noise vector. The Least Absolute Shrinkage and Selection Operator (LASSO) of @Lasso is a regularization method used in regression problems for shrinkage and selection of features. The lasso estimator is defined as $$\begin{aligned}
\label{eq:betalasso}
{\hat{\beta}}_{\text{lasso}} \coloneqq \operatorname*{arg\,min}_{{\beta}} \| Y -  X{\beta}\|_2^2 + \lambda \|\beta\|_1\,.\end{aligned}$$ where $\|\cdot\|_1,\|\cdot\|_2$ are $l_1$ and $l_2$ norms correspondingly. It can be interpreted as a Bayesian posterior mode (MAP) estimate when the priors on $\beta$ are given by independent Laplace distributions. As discovered by @Park, the same posterior on $\beta$ is also obtained by the following Gibbs sampling scheme: set $\eta = 1$ and denote $ {D_\tau}\coloneqq{{\text{diag}}}(\tau_1,\dots,\tau_n).$ Also, let $a\coloneqq\frac{\eta}{2}(n-1) + \frac p2 + \alpha$ and $b_\tau\coloneqq\frac{\eta}{2}( {{Y}-X\beta})^T  ( {{Y}-X\beta}) + \frac12 {\beta}^T  {D_\tau}^{-1}  {\beta} + \gamma$, where $\alpha,\gamma>0$ are hyperparameters. Then the Gibbs sampler is constructed as follows. $$\begin{aligned}
\begin{split}
 {\beta} \sim &\,{\ensuremath{\mathcal N}}\left( \eta M_\tau {X}^T {{Y}}, \sigma^2M_\tau \right), 
\end{split} \\ 
\begin{split}
\sigma^2 \sim &\,\text{Inv-Gamma} \left( a, b_\tau \right),
\end{split} \quad
{\tau^{-2}_j} \sim \,\text{IG}\left(\displaystyle \sqrt{{\lambda^2\sigma^2}/{\beta_j^2}}, \lambda^2\right),\end{aligned}$$ where IG is the inverse Gaussian distribution and $M_\tau\coloneqq(\eta {X}^T {X} + {D_\tau}^{-1})^{-1}$. Following @Park, we put a Gamma prior on the shrinkage parameter $\lambda$. Now, in their paper @Park only give the scheme for $\eta = 1$ but as is straightforward to derive from their paper, the scheme above actually gives the $\eta$-[*generalized*]{} posterior corresponding to the lasso prior for general $\eta$ (more details in Appendix \[app:impl\]). We will use the Safe-Bayesian algorithm for choosing the optimal $\eta$ developed by @grunwald2017inconsistency (see Appendix \[ap:safebayesimpl\]).

#### Horseshoe estimator

The Horseshoe prior is the state-of-the-art global-local shrinkage prior for tackling high-dimensional regularization, introduced by @horseshoe. Unlike the Baysian lasso it has flat Cauchy-like tails, which allow strong signals to remain unshrunk a posteriori. For completeness we include the horseshoe in our regression comparison, using the implementation of @vanderpas2016horseshoe.

Bayesian logistic regression
----------------------------

Consider the standard logistic regression model $\{ f_{\beta}: \beta \in {{\mathbb R}}^{p}\}$, the data $Y_1,\dots, Y_n\in\{0,1\}$ are independent binary random variables observed at the points $X_1,\dots,X_n\in \mathbb{R}^p$ with $$\nonumber
P_{f_{\beta}}(Y_i=1 \mid X_i) \coloneqq p_{f_{\beta}}(1 \mid X_i) \coloneqq \frac{e^{X_i^T\beta}}{1+e^{X_i^T\beta}}.$$ The standard Bayesian approach involves putting a Gaussian prior on the parameter $\beta\sim {\ensuremath{\mathcal N}}(b,B)$ with mean $b\in{\mathbb{R}}^p$ and the covariance matrix $B\in{\mathbb{R}}^{p\times p}$. To sample from the $\eta$-generalised posterior we modify a P[ó]{}lya–Gamma latent variable scheme sampler described in @polson2013bayesian. Let $\kappa\coloneqq(Y_1-1/2,\dots, Y_n-1/2)^T$, ${V_\omega\coloneqq(X^T\Omega X+B^{-1})^{-1}}$, and $ {m_\omega\coloneqq V_\omega(\eta X^T\kappa+B^{-1}b)}$. Then the Gibbs sampler for $\eta$-generalized posterior is given by $$\begin{aligned}
\omega_i\sim \text{PG}(\eta, X_i^T\beta), \quad
\beta\sim {\ensuremath{\mathcal N}}(m_\omega, V_\omega), \end{aligned}$$ where PG is the P[ò]{}lya-Gamma distribution.

Experiments {#sec:examples}
===========

Below we present the results of experiments that compare the performance of the derived Gibbs samplers with their standard counterparts. More details/experiments are in Appendix \[ap:detailsfigures\].

Simulated data {#sec:lassoandhs}
--------------

#### Regression

In our experiments we focus on prediction, and we run simulations to determine the *square-risk* (expected squared error loss) of our estimate relative to the underlying distribution $P$: , where $X\beta$ would be the conditional expectation, and thus the square-risk minimizer, if $\beta$ would be the true parameter (vector).

Consider the data generated as described in Example \[ex:basic\]. We study the performance of the $\eta$-generalised Bayesian lasso with $\eta$ chosen by the SafeBayes algorithm (we call it the Safe-Bayesian lasso) in comparison with two popular estimation procedures for this context: the Bayesian lasso (which corresponds to $\eta$=1), and the Horseshoe method. In Figure \[fig:risk-simulaties resultaten\] the empirical square-risk is plotted as a function of the sample size for all three methods. We average over enough samples so that the graph appears to be smooth ($25$ iterations for SafeBayes, $1000$ for the two standard Bayesian methods). It shows that both the standard Bayesian lasso and the Horseshoe perform significantly worse than the Safe-Bayesian lasso. Moreover we see that the risks for the standard methods initially grows with the sample size (additional experiments not reported here suggest that Bayes will ‘recover’ at very large $n$).

![Empirical squared error risk with respect to $P$ as function of sample size for the *wrong-model* experiments of Section \[sec:lassoandhs\] according to the posterior predictive distribution of the standard Bayesian lasso (green, solid), the Safe-Bayesian lasso (red, dotted), both with standard improper priors, and the Horseshoe (blue, dashed); and $201$ Fourier basis functions. \[fig:risk-simulaties resultaten\]](RegressionRiskPlot.pdf){width="45.00000%"}

#### Classification {#sec:logisticregression}

We focus on finding coefficients $ \beta$ for prediction, and our error measure is the expected logarithmic loss, which we call *log-risk*: , where $ \text{Li}_\beta(Y{\, |\, }X)\coloneqq {e^{YX^T\beta}}/({1+e^{X^T\beta}})$. We start with an example that is very similar to the previous one. We generate a $n\times p$ matrix of independent standard normal random variables with $p=25$. For every feature vector $ X_i$ we sample a corresponding $Z_i \sim {\ensuremath{\mathcal N}}(0, \sigma^2)$, as before, and we misspecify the model by putting approximately half of the $Z_i$ and the corresponding $X_{i,1}$ to zero. Next, we sample the labels $Y_i \sim \text{Binom}(\exp(Z_i) / (1 + \exp(Z_i))$. We compare standard Bayesian logistic regression ($\eta=1$) to a generalized version ($\eta = 0.125$). In Figure \[fig:logregrisk\] we plot the empirical log-risk as a function of the sample size. As in the regression case, the risk for standard Bayesian logistic regression ($\eta=1$) is substantially worse than the one for generalized Bayes ($\eta=0.125$). Even for generalized Bayes, the risk initially goes up a little bit, the reason being that the prior is [*too good*]{}: it is strongly concentrated around the risk-optimal $\beta^* =0$. Thus, the first prediction made by the Bayes predictive distribution coincides with the optimal $(\beta=0)$ prediction, and in the beginning, due to noise in the data, predictions will first get slightly worse. This is a phenomenon that also applies to standard Bayes with well-specified models; see for example [@GrunwaldH04 Example 3.1].

![Empirical logistic risk as function of sample size for the *wrong-model* experiments of Section \[sec:logisticregression\] according to the posterior predictive distribution of standard Bayesian logistic regression (green, solid), and generalized Bayes ($\eta=0.125$, red, dotted) with $25$ noise dimensions. \[fig:logregrisk\]](Logit.pdf){width="40.00000%"}

Even for the well-specified case it can be beneficial to use $\eta\neq 1$. It is easy to see that the maximum [*a posteriori*]{} for the generalized logistic regression corresponds to the ridge logistic regression method (which penalises large $\|\beta\|_2$) with the shrinkage parameter $\lambda=\eta^{-1}$. However, when the the prior mean is zero but the risk minimizer $\beta^*$ is far from zero, penalising large norms of $\beta$ is inefficient, and we find that the best performance is achieved with $\eta>1$.

Real World Data {#sec:real}
---------------

We present two examples with real world data to demonstrate that bad behavior under misspecification also occurs in practice. For these datasets, we compare the performance of Safe-Bayesian lasso and standard Bayesian lasso. As the first example we consider the data of the daily maximum temperatures at Seattle Airport as a function of the time and date (source: $\texttt{R}$-package $\texttt{weatherData}$, also available at $\texttt{www.wunderground.com}$). A second example is London air pollution data (source: $\texttt{R}$-package $\texttt{Openair}$, for more details see @openair1 [@openair2]). Here the quantity of interest is the concentration of nitrogen dioxide (NO$_2$), again as a function of time and date. In both settings we divide the data in a training set and a test set, and focus on the prediction. In both examples, SafeBayes picks an $\hat\eta$ strictly smaller than one. Also, for both data sets the SafeBayes lasso substantially outperforms the standard Bayesian lasso and the Horseshoe in terms of mean square prediction error, as seen from Table \[table:seattleandlondon\] (details in Appendix \[ap:detailsfigures\]).

[0.48]{}[| l | X | X | X |]{} & Horse-shoe & Bayesian lasso & SafeBayes lasso\
MSE ($(^{\circ} \text{C})^2$) & $6.53$ & $6.16$ & $6.04$\
MSE ($(\text{ppm})^2$) & $1169$ & $1201$ & $1142$\

Future work
===========

We provide both theoretical and empirical evidence that $\eta$-generalized Bayes can significantly outperform standard Bayes for GLMs. However, the empirical examples are only given for Bayesian lasso linear regression and logistic regression. In future work we would like to devise generalized posteriors samplers for other GLMs and speed up the sampler for the generalized Bayesian logistic regression, since our current implementation is slow, and (unlike our linear regression implementation) cannot deal with high-dimensional (and thus, real-world) data yet. Furthermore, the SafeBayes algorithm of [@Grunwald12], used to learn $\eta$, enjoys good theoretical performance but is computationally very slow. Since learning $\eta$ for which the central condition holds (preferably the largest possible value, since small values of $\eta$ mean slower learning) is essential for using generalized Bayes in practice, there is a necessity for speeding up SafeBayes or finding an alternative. A potential solution might be using cross-validation to learn $\eta$, but its theoretical properties (e.g.satisfying central condition) are yet to be established.

\[3\][\#3]{}

\[3\][\#2]{}

Outline {#app:outline}
=======

The appendix of this paper is organized as follows:

-   Appendix \[app:proofs\] provides the proofs for Section \[sec:genglm\].

-   Appendix \[sec:witness\] shows how we can replace ${{d}}^2_{\bar\eta}$ in Theorem \[thm:metric\] by stronger notions.

-   Appendix \[app:impl\] provides (implementation) details on the $\eta$-generalized Bayesian lasso and logistic regression; and the Safe-Bayesian algorithm.

-   Appendix \[ap:detailsfigures\] contains details for the experiments and figures in the main text, and provides additional figures.

Proofs {#app:proofs}
======

Proof of Theorem \[thm:expfam-exptails\]
----------------------------------------

The second part of the theorem about the Gaussian location family is a straightforward calculation, which we omit. As to the first part (Part (i)—(iii)), we will repeatedly use the following fact: for every $\Theta$ that is a nonempty compact subset of the interior of $\bar{\Theta}$, in particular for $\Theta = [\underline{\theta},\bar{\theta}]$ with $\underline\theta < \bar\theta$ both in the interior of $\overline{\Theta}$, we have: $$\label{eq:ineccsi}
\begin{aligned}
- \infty <  \inf_{\theta \in \Theta} F(\theta) &< \sup_{\theta \in \Theta} F(\theta) < \infty \\
- \infty < \inf_{\theta \in \Theta} F'(\theta) &< \sup_{\theta \in \Theta} F'(\theta) < \infty \\
0 <  \inf_{\theta \in \Theta} F''(\theta) &< \sup_{\theta \in \Theta} F''(\theta) < \infty.
\end{aligned}$$ Now, let $\theta, \theta^* \in \Theta$. We can write $$\begin{aligned}
\label{eq:basecamp}
    {\operatorname{\mathbf{E}}}\left[ e^{-\eta ({{\ensuremath{\ell}}_\theta - {\ensuremath{\ell}}_{\theta^*}})} \right]  
    = {\operatorname{\mathbf{E}}}_{Y \sim P} \left[ \left( \frac{p_\theta(Y)}{p_{\theta^*}(Y)} \right)^\eta \right]
     = \exp \left (-G(\eta(\theta- \theta^*))
    + \eta F(\theta^*) - \eta F(\theta) \right).
    \end{aligned}$$ where $G(\lambda) =  - \log {\operatorname{\mathbf{E}}}_{Y \sim P} \left[ \exp( \lambda Y)\right]$. If this quantity is $- \infty$ for all $\eta > 0$, then (i) holds trivially. If not, then (i) is implied by the following statement: $$\label{eq:limitvariance}
                \limsup_{\epsilon \rightarrow 0} \left\lbrace \eta: \text{for all $\theta \in [\theta^*- \epsilon,\theta^* + \epsilon]$},  
        \ {\operatorname{\mathbf{E}}}[\exp(\eta {L_{p_{\theta}}})] \leq 1 \right\rbrace = \frac{(\sigma^*)^2}{\sigma^2}.
        $$ Clearly, this statement also implies (iii). To prove (i), (ii) and (iii), it is thus sufficient to prove (ii) and (\[eq:limitvariance\]). We prove both by a second-order Taylor expansion (around $\theta^*$) of the right-hand side of .

[*Preliminary Facts*]{}. By our assumption there is a $
        \eta^{\circ}> 0 $ such that ${\operatorname{\mathbf{E}}}[\exp(\eta^\circ |Y|)] =
        \bar{C} < \infty$. Since $\theta^* \in \Theta =
            [\underline\theta,\overline\theta]$ we must have for every $0 < \eta < \eta^{\circ}/(2 |\overline\theta -
            \underline\theta|)$, every $\theta \in \Theta$, $$\label{eq:finite}
    \begin{aligned}
      {\operatorname{\mathbf{E}}}[ \exp(2 \eta (\theta - \theta^*) \cdot Y)] \leq
          {\operatorname{\mathbf{E}}}[ \exp(2 \eta | \theta - \theta^*| \cdot |Y|)] \leq 
      {\operatorname{\mathbf{E}}}[ \exp(\eta^{\circ} (| \theta - \theta^*|/|\overline\theta -
        \underline\theta|) \cdot |Y|)] \leq \bar{C} < \infty.
    \end{aligned}$$ The first derivative of the right of is: $$\label{eq:ffirst}
    \eta {\operatorname{\mathbf{E}}}\left[ (Y - F'(\theta)) \exp \Bigl( \eta \bigl( (\theta - \theta^*) Y + F(\theta^*) - F(\theta) \bigr) \Bigr) \right] .$$ The second derivative is: $$\label{eq:fsecond}
    {\operatorname{\mathbf{E}}}\left[ \left( -\eta F''(\theta) + \eta^2 (Y - F'(\theta))^2 \right) 
  \cdot \exp \Bigl( \eta \bigl( (\theta - \theta^*) Y + F(\theta^*) - F(\theta) \bigr) \Bigr) \right] .$$ We will also use the standard result [@Grunwald07; @BarndorffNielsen78] that, since we assume $\theta^* \in \Theta$, $$\label{eq:expfacts}
    \begin{aligned}
    {\operatorname{\mathbf{E}}}[Y] = {\operatorname{\mathbf{E}}}_{Y  \sim P_{\theta^*}}[Y] = \mu(\theta^*);  \qquad
     \text{for all $\theta \in 
        \bar{\Theta}$:} 
    \ F'(\theta) = \mu(\theta); \qquad
    F''(\theta) = {\operatorname{\mathbf{E}}}_{Y  \sim P_{\theta}}(Y- E(Y))^2,
    \end{aligned}$$ the latter two following because $F$ is the cumulant generating function.

[*Part (ii)*]{}. We use an exact second-order Taylor expansion via the Lagrange form of the remainder. We already showed there exist $\eta' > 0$ such that, for all $0 < \eta \leq \eta'$, all $\theta \in {\Theta}$, ${\operatorname{\mathbf{E}}}[\exp(2\eta (\theta- \theta^*) Y)] <
    \infty$. Fix any such $\eta$. For some $\theta' \in \left\{ (1 -
    \alpha) \theta + \alpha \theta^* \colon \alpha \in [0, 1] \right\}$, the (exact) expansion is: $$\nonumber
    \begin{multlined}
    {\operatorname{\mathbf{E}}}\left[ e^{-\eta ({{\ensuremath{\ell}}_\theta - {\ensuremath{\ell}}_{\theta^*}})} \right]  
    = 1 + \eta (\theta - \theta^*) {\operatorname{\mathbf{E}}}\left[ Y - F'(\theta^*) \right] \label{eqn:d-cgf-is-mean} 
    - \frac{\eta}{2} (\theta - \theta^*)^2 F''(\theta') 
\cdot   {\operatorname{\mathbf{E}}}\left[ \exp \Bigl( \eta \bigl( (\theta' - \theta^*) Y 
    + F(\theta^*) - F(\theta')
    \bigr)
    \Bigr) \right]
     \nonumber \\
    + \frac{\eta^2}{2} (\theta - \theta^*)^2    {\operatorname{\mathbf{E}}}\left[ (Y - F'(\theta'))^2 \right.
    \cdot \left. \exp \Bigl( \eta \bigl( (\theta' - \theta^*) Y 
    + F(\theta^*) - F(\theta')
    \bigr) \Bigr)
    \right] . \nonumber 
    \end{multlined}$$ Defining $\Delta = \theta' - \theta$, and since $F'(\theta^*) = {\operatorname{\mathbf{E}}}[ Y
    ]$ (see ), we see that the central condition is equivalent to the inequality: $$\begin{aligned}
    \eta {\operatorname{\mathbf{E}}}\left[ (Y - F'(\theta'))^2 e^{\eta \Delta Y} \right] 
    \leq F''(\theta') {\operatorname{\mathbf{E}}}\left[ e^{\eta \Delta Y} \right] .
    \end{aligned}$$ From Cauchy-Schwarz, to show that the $\eta$-central condition holds it is sufficient to show that $$\begin{aligned}
    \eta \left \| (Y - F'(\theta'))^2 \right\|_{L_2(P)} \left \| e^{\eta \Delta Y} \right\|_{L_2(P)} 
    \leq F''(\theta') {\operatorname{\mathbf{E}}}\left[ e^{\eta \Delta Y} \right] ,
    \end{aligned}$$ which is equivalent to $$\label{eqn:eta-expfam-upper-bound}
    \begin{aligned}
    \eta 
    \leq \frac{F''(\theta') {\operatorname{\mathbf{E}}}\left[ e^{\eta \Delta Y} \right]}
    {
        \sqrt{{\operatorname{\mathbf{E}}}\left [ (Y - F'(\theta'))^4 \right] 
            {\operatorname{\mathbf{E}}}\left[e^{2 \eta \Delta Y} \right]}
    } . 
    \end{aligned}$$ We proceed to lower bound the RHS by lower bounding each of the terms in the numerator and upper bounding each of the terms in the denominator. We begin with the numerator. $F'(\theta)$ is bounded by . Next, by Jensen’s inequality, $${\operatorname{\mathbf{E}}}\left[ \exp({\eta \Delta Y}) \right] \geq \exp( {\operatorname{\mathbf{E}}}[\eta 
    \Delta \cdot Y ])\geq \exp(- \eta^{\circ} |\overline\theta -
    \underline\theta| | \mu( \theta^*)| )$$ is lower bounded by a positive constant. It remains to upper bound the denominator. Note that the second factor is upper bounded by the constant $\bar{C}$ in . The first factor is bounded by a fixed multiple of ${\operatorname{\mathbf{E}}}|Y|^4 + {\operatorname{\mathbf{E}}}[F'(\theta)^4]$. The second term is bounded by , so it remains to bound the first term. By assumption ${\operatorname{\mathbf{E}}}[\exp(\eta^{\circ} |Y|)] \leq \bar{C}$ and this implies that ${\operatorname{\mathbf{E}}}|Y^4| \leq a^4 + \bar{C}$ for any $a \geq e$ such that $a^4 \leq  \exp(\eta^{\circ} a)$; such an $a$ clearly exists and only depends on $\eta^{\circ}$.

We have thus shown that the RHS of is upper bounded by a quantity that only depends on $\bar{C}, \eta^{\circ}$ and the values of the extrema in , which is what we had to show.

[*Proof of (iii)*]{}. We now use the asymptotic form of Taylor’s theorem. Fix any $\eta > 0$, and pick any $\theta$ close enough to $\theta^*$ so that is finite for all $\theta'$ in between $\theta$ and $\theta^*$; such a $\theta \neq \theta^*$ must exist since for any $\delta > 0$, if $|\theta - \theta^*| \leq \delta$, then by assumption must be finite for all $\eta \leq \eta^\circ/\delta$. Evaluating the first and second derivative and at $\theta = \theta^*$ gives: $$\begin{multlined}
       {\operatorname{\mathbf{E}}}\left[ e^{-\eta ({{\ensuremath{\ell}}_\theta - {\ensuremath{\ell}}_{\theta^*}})} \right]   =   1 + \eta (\theta - \theta^*) {\operatorname{\mathbf{E}}}\left[ Y - F'(\theta^*) \right] 
    - \left( \frac{\eta}{2}
    (\theta - \theta^*)^2 F''(\theta^*) 
    - \frac{\eta^2}{2} (\theta - \theta^*)^2 
     \cdot  {\operatorname{\mathbf{E}}}\left[ (Y -
    F'(\theta^*))^2 \right] \right) \\
     + h(\theta)(\theta - \theta^*)^2   
    = 1 - \frac{\eta}{2}
    (\theta - \theta^*)^2 F''(\theta^*) 
    + \frac{\eta^2}{2} (\theta - \theta^*)^2 {\operatorname{\mathbf{E}}}\left[ (Y -
    F'(\theta^*))^2 \right]  + h(\theta) (\theta - \theta^*)^2, 
    \end{multlined}$$ where $h(\theta)$ is a function satisfying $\lim_{\theta \rightarrow \theta^*} h(\theta) = 0$, where we again used , i.e. that $F'(\theta^*) = {\operatorname{\mathbf{E}}}\left[Y\right]$. Using further that $\sigma^2 =  {\operatorname{\mathbf{E}}}\left[ (Y - F'(\theta^*))^2
    \right]$ and $F''(\theta^*) = (\sigma^*)^2$, we find that ${\operatorname{\mathbf{E}}}\left[ e^{-\eta ({{\ensuremath{\ell}}_\theta - {\ensuremath{\ell}}_{\theta^*}})} \right] \leq 1$ iff $$- \frac{\eta}{2}  (\theta - \theta^*)^2 (\sigma^*)^2
    + \frac{\eta^2}{2} (\theta - \theta^*)^2 \sigma^2  + h(\theta) (\theta - \theta^*)^2 \leq 0.$$ It follows that for all $\delta > 0$, there is an $\epsilon > 0$ such that for all $\theta \in [\theta^*- \epsilon,\theta^* + \epsilon]$, all $\eta > 0$, $$\begin{aligned}
    \frac{\eta^2}{2} \sigma^2 \leq \frac{\eta}{2} (\sigma^*)^2  - \delta  
    & \Rightarrow {\operatorname{\mathbf{E}}}\left[ e^{-\eta ({{\ensuremath{\ell}}_\theta - {\ensuremath{\ell}}_{\theta^*}})} \right] \leq 1 \label{eq:goodcondition} \\ \label{eq:badcondition}
    \frac{\eta^2}{2} \sigma^2 \geq \frac{\eta}{2} (\sigma^*)^2  +  \delta  
    & \Rightarrow {\operatorname{\mathbf{E}}}\left[ e^{-\eta ({{\ensuremath{\ell}}_\theta - {\ensuremath{\ell}}_{\theta^*}})} \right] \geq  1\end{aligned}$$ The condition in is implied if: $$0 < \eta \leq \frac{(\sigma^*)^2}{\sigma^2} -   \frac{2 \delta}{\eta \sigma^2}.$$ Setting $C = 4 \sigma^2/(\sigma^*)^4$ and $\eta_{\delta} = (1- C {\delta}) (\sigma^*)^2/\sigma^2$ we find that for any $\delta < (\sigma^*)^4/(8 \sigma^2)$, we have $1- C {\delta} \geq 1/2$ and thus $\eta_{\delta} > 0$ so that in particular the premise in is satisfied for $\eta_{\delta}$. Thus, for all small enough $\delta$, both the premise and the conclusion in hold for $\eta_{\delta} > 0$; since $\lim_{\delta \downarrow 0} \eta_{\delta} = (\sigma^*)^2/\sigma^2$, it follows that there is an increasing sequence $\eta_{(1)}, \eta_{(2)}, \ldots$ converging to $(\sigma^*)^2/\sigma^2$ such that for each $\eta_{(j)}$, there is $\epsilon_{(j)} > 0$ such that for all $\theta \in [\theta^*- \epsilon_{(j)}, \theta^*+\epsilon_{(j)}]$, ${\operatorname{\mathbf{E}}}\left[ e^{-\eta_{(j)} ({{\ensuremath{\ell}}_\theta - {\ensuremath{\ell}}_{\theta^*}})} \right] \leq 1$. It follows that the $\lim \sup$ in is at least $(\sigma^*)^2/\sigma^2$. A similar argument (details omitted) using shows that the $\lim \sup$ is at most this value; the result follows.

Proof of Proposition \[prop:entroboundb\]
-----------------------------------------

For arbitrary conditional densities $p'(y \mid x)$ with corresponding distribution $P'\mid X$ for which $$\label{eq:daling}
    {\operatorname{\mathbf{E}}}_{P'}[Y |X] = g^{-1}(\langle \beta,X),$$ and densities $p_{{{f^*}}} = p_{\beta^*}$ and $p_\beta$ with $\beta^*,\beta \in {\ensuremath{\mathcal B}}$, we can write: $$\begin{aligned}
    {\operatorname{\mathbf{E}}}_{X\sim P} {\operatorname{\mathbf{E}}}_{Y \sim P'\mid X}\left[ \log  \frac{p_{\beta^*}(Y \mid X)}{p_{\beta}(Y | X)}\right] 
    &=   {\operatorname{\mathbf{E}}}{\operatorname{\mathbf{E}}}\left[ (\theta_X(\beta^*) - \theta_X(\beta) )  Y -  \log 
    \frac{F(\theta_X(\beta^*))}{F(\theta_X(\beta))}   \mid X \right]\\
     &= {\operatorname{\mathbf{E}}}_{X \sim P} 
    \left[ (\theta_X(\beta^*) - \theta_X(\beta) )g^{-1}(\langle \beta, X\rfloor_d \rangle 
 -  \log F(\theta_X(\beta^*)) + \log F(\theta_X(\beta))   \mid X \right],
    \end{aligned}$$ where the latter equation follows by . The result now follows because both holds for the ‘true’ $P$ and for $P_{{{f^*}}}$.

Proof of Proposition \[prop:tenerife\]
--------------------------------------

The fact that under the three imposed conditions the $\bar\eta$-central condition holds for some $\bar\eta > 0$ is a simple consequence of Theorem \[thm:expfam-exptails\]: Condition 1 implies that there is some compact $\Theta$ such that for all $x \in {\ensuremath{\mathcal X}}$, $\beta \in
    {\ensuremath{\mathcal B}}$, $\theta_x(\beta) \in \Theta$. Condition 3 then ensures that $\theta_x(\beta)$ lies in the interior of this $\Theta$. And Condition 2 implies that $\bar\eta$ in Theorem \[thm:expfam-exptails\] can be chosen uniformly for all $x \in {\ensuremath{\mathcal X}}$.

Excess risk and KL divergence instead of generalized Hellinger distance {#sec:witness}
=======================================================================

The misspecification metric/generalized Hellinger distance ${{d}}_{\bar\eta}$ appearing in Theorem \[thm:metric\] is rather weak (it is ‘easy’ for two distributions to be close) and lacks a clear interpretation for general, non-logarithmic loss functions. Motivated by these facts, GM study in depth under what additional conditions the (square of this) metric can be replaced by a stronger and more readily interpretable divergence measure. They come up with a new, surprisingly weak condition, the [*witness condition*]{}, under which ${{d}}_{\bar\eta}$ can be replaced by the [*excess risk*]{} ${\bf E}_P[L_f]$, which is the additional risk incurred by $f$ as compared to the optimal $f^*$. For example, with the squared error loss, this is the additional mean square error of $f$ compared to $f^*$; and with (conditional) log-loss, it is the well-known [*generalized KL divergence*]{} ${\bf
  E}_{X,Y \sim P}[\log \frac{p_{f^*}(Y \mid X)}{p_f(Y|X)}]$, coinciding with standard KL divergence if the model is correctly specified. Bounding the excess risk is a standard goal in statistical learning theory; see for example [@bartlett2005local; @erven2015fast].

The following definition appears (with substantial explanation including the reason for its name) as Definition 12 in GM:

\[def:witness\] We say that ${({P},{\ensuremath{\ell}},{\mathcal{F}})}$ satisfies the $(u,c)$-*empirical witness of badness condition* (or *witness condition*) for constants $u > 0$ and $c \in (0,1]$ if for all $f \in {\ensuremath{\mathcal F}}$ $$\begin{aligned}
    {\operatorname{\mathbf{E}}}\left[ ({{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}}) \cdot {\mathop{{\bf 1}_{\{{{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}} \leq u\}}}} \right] \geq c {{\operatorname{\mathbf{E}}}[ {{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}} ]} .
    \end{aligned}$$ More generally, for a function $\tau: {{\mathbb R}}^+ \to [1,\infty)$ and constant $c \in (0,1)$ we say that ${({P},{\ensuremath{\ell}},{\mathcal{F}})}$ satisfies the *$(\tau,c)$-witness condition* if for all $f \in {\ensuremath{\mathcal F}}$, ${{\operatorname{\mathbf{E}}}[ {{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}} ]} < \infty$ and $$\begin{aligned}
     {\operatorname{\mathbf{E}}}\left[ ({{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}}) \cdot {\mathop{{\bf 1}_{\{{{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}} \leq \tau({{\operatorname{\mathbf{E}}}[ {{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}} ]})\}}}} \right] \geq c {{\operatorname{\mathbf{E}}}[ {{\ensuremath{\ell}}_{f} - {\ensuremath{\ell}}_{{{f^*}}}} ]} .
    \end{aligned}$$

It turns out that the $(\tau,c)$-witness condition holds in many practical situations, including our GLM-under-misspecification setting. Before elaborating on this, let us review (a special case of) Theorem 12 of GM, which is the analogue of Theorem \[thm:metric\] but with the misspecification metric replaced by the excess risk.

First, let, for arbitrary $0 < \eta < \bar\eta$, $c_u \coloneqq \frac{1}{c} \frac{\eta u + 1}{1 - \frac{\eta}{\bar{\eta}}}$. Note that for large $u$, $c_u$ is approximately linear in $u/c$.

[**\[Specialization of Theorem 12 of GM\]**]{} Consider a learning problem ${({P},{\ensuremath{\ell}},{\mathcal{F}})}$. Suppose that the $\bar\eta$-strong central condition holds. If the $(u,c)$-witness condition holds, then for any $\eta \in (0,\bar\eta)$, $$\begin{aligned}
\label{eq:same}
    {\bf E}_{Z^n \sim P} {\operatorname{\mathbf{E}}}_{{\underline{f}} \sim {\ensuremath{\Pi}}_n}\left[{{\operatorname{\mathbf{E}}}[ {L_{f}} ]}\right] 
    \leq   
    c_u \cdot {\bf E}_{Z^n \sim P} \left[
          {\mathrm{IC}}_{n,\eta} \left( \Pi_0 \right) \right],
    \end{aligned}$$ with $c_u$ as above. If instead the $(\tau,c)$-witness condition holds for some nonincreasing function $\tau$ as above, then for any $\lambda > 0$, $$    {\bf E}_{Z^n \sim P} {\operatorname{\mathbf{E}}}_{{\underline{f}} \sim {\ensuremath{\Pi}}_n} \left[{{\operatorname{\mathbf{E}}}[ {L_{f}} ]} \right] 
    \ \leq  \ 
    \lambda + c_{\tau(\lambda)} \cdot {\bf E}_{Z^n \sim P} \left[ {\mathrm{IC}}_{n,\eta} \left( \Pi_0\right)\right]. \nonumber$$

The actual theorem given by GM generalizes this to an in-probability statement for general (not just generalized Bayesian) learning methods. If the $(u,c)$-witness condition holds, then, as is obvious from (\[eq:same\]) and Theorem \[thm:metric\], the same rates can be obtained for the excess risk as for the squared misspecification metric. For the $(\tau,c)$-witness condition things are a bit more complicated; the following lemma (Lemma 16 of GM) says that, under an exponential tail condition, $(\tau,c)$-witness holds for a sufficiently ‘nice’ function $\tau$, for which we loose at most a logarithmic factor:

\[lem:kl-hell-exp-tails\] Define $M_{\kappa} \coloneqq \sup_{f \in {\ensuremath{\mathcal F}}} {\operatorname{\mathbf{E}}}\left[ e^{\kappa {L_{f}}} \right]$ and assume that the excess loss $L_f$ has a uniformly exponential upper tail, i.e. $M_{\kappa} < \infty$. Then, for the map $\tau: x \mapsto 1 \operatorname*{\vee}\kappa^{-1} {\log \frac{2 M_\kappa }{\kappa x}} = O(1 \operatorname*{\vee}\log (1/x))$, the $(\tau,c)$-witness condition holds with $c = \nicefrac{1}{2}$.

As an immediate consequence of this lemma, GM’s theorem above gives that for any $\eta \in (0,\bar\eta)$, (using $\lambda=
1/n$), there is $C_{\eta} < \infty$ such that $$\begin{aligned}
 \label{eqn:kl-hell-exp-tails-2} 
{\bf E}_{Z^n \sim P} {\operatorname{\mathbf{E}}}_{{\underline{f}} \sim {\ensuremath{\Pi}}_n} \left[ {{\operatorname{\mathbf{E}}}[ {L_{{\underline{f}}}} ]} \right] \leq 
\frac{1}{n}
+ C_{\eta} \cdot (\log n) \cdot {\bf E}_{Z^n \sim P} \left[{\mathrm{IC}}_{\eta,n} \left( {{f^*}}\operatorname*{\|}{{\ensuremath{\Pi}}_|}\right) \right],\end{aligned}$$ so our excess risk bound is only a log factor worse than the bound that can be obtained for the squared misspecifation metric in Theorem \[thm:metric\]. We now apply this to the misspecified GLM setting:

#### Generalized Linear Models and Witness

Recall that the central condition holds for generalized linear models under the three assumptions made in Proposition \[prop:tenerife\]. Let ${\ensuremath{\ell}}_\beta \coloneqq
        {\ensuremath{\ell}}_\beta(X,Y) = -\log p_\beta(Y \mid X)$ be the loss of action $\beta \in {\ensuremath{\mathcal B}}$ on random outcome $(X,Y) \sim P$, and let $\beta^*$ denote the risk minimizer over ${\ensuremath{\mathcal B}}$. The first two assumptions taken together imply, via , that there is a $\kappa > 0$ such that $$\begin{aligned}
    \sup_{\beta \in B} {\operatorname{\mathbf{E}}}_{X,Y \sim P}\left[ 
    e^{\kappa ({\ensuremath{\ell}}_\beta - {\ensuremath{\ell}}_{\beta^*})} \right] 
    &\leq 
    \sup_{\beta \in {\ensuremath{\mathcal B}}, x \in {\ensuremath{\mathcal X}}} {\operatorname{\mathbf{E}}}_{Y \sim P \mid X=x}\left[ 
    e^{\kappa ({\ensuremath{\ell}}_\beta - {\ensuremath{\ell}}_{\beta^*})}
    \right] \\ 
    &= \sup_{\beta \in {\ensuremath{\mathcal B}}, x \in {\ensuremath{\mathcal X}}} 
    \left( \frac{F_{\theta_x(\beta)}}{F_{\theta_x(\beta^*)}}\right)^{\kappa} \cdot {\operatorname{\mathbf{E}}}_{Y \sim P \mid X=x}\left[ 
    e^{\kappa | Y| }\right]
    < \infty.
    \end{aligned}$$ The conditions of Lemma \[lem:kl-hell-exp-tails\] are thus satisfied, and so the $(\tau,c)$-witness condition holds for the $\tau$ and $c$ in that lemma. From we now see that we get an $O((\log n)^2/n)$ bound on the expected excess risk, which is equal to the parametric (minimax) rate up to a $(\log n)^2$ factor. Thus, fast learning rates in terms of excess risks and KL divergence under misspecification with GLMs are possible under the conditions of Proposition \[prop:tenerife\].

MCMC Sampling {#app:impl}
=============

The $\eta$-generalized Bayesian lasso
-------------------------------------

Here, following @Park we consider a slightly more general version of the regression problem: $$Y=\mu+  X  \beta+{\varepsilon},$$ where $\mu\in{\mathbb{R}}^n$ is the overall mean, $\beta\in{\mathbb{R}}^p$ is the vector of parameters of interest, $y\in{\mathbb{R}}^n$, $X\in{\mathbb{R}}^{n\times p}$, and ${\varepsilon}\sim N(0,\sigma^2 I_n)$ is a noise vector. For a given shrinkage parameter $\lambda>0$ the Bayesian lasso of @Park can be represented as follows. $$\begin{aligned}
\label{eq:hiermodelbayesianlassopark}
 {Y} \rvert \mu,  {X},  {\beta}, \sigma^2 &\sim N(\mu +  {X\beta}, \sigma^2 {I_n}) \, , \\ \nonumber
 {\beta} \rvert \tau_1^2, \ldots, \tau_p^2, \sigma^2 &\sim N( {0}, \sigma^2  {D}_\tau), \, \, \, \,  {D}_\tau = {{\text{diag}}}(\tau_1^2, \ldots, \tau_p^2) \, , \\ \nonumber
\tau_1^2, \ldots, \tau_p^2 &\sim \prod_{j=1}^p \frac{\lambda^2}{2} e^{-\lambda^2\tau_j^2 /2} d\tau_j^2, \, \, \, \, \tau_1^2, \ldots, \tau_p^2 > 0 \, , \\ \nonumber
\sigma^2 &\sim \pi(\sigma^2) \, d\sigma^2 \, .\end{aligned}$$

In this model formulation the $\mu$ on which the outcome variables $Y$ depend, is the overall mean, from which ${X\beta}$ are deviations. The parameter $\mu$ can be given a flat prior and subsequently integrated out, as we do in the coming sections.

We will use the typical inverse gamma prior distribution on $\sigma^2$, i.e. for $\sigma^2>0$ $$\pi(\sigma^2)=\frac{\gamma^\alpha}{\Gamma(\alpha)}\sigma^{-2\alpha-2}e^{-\gamma/\sigma^2},$$ where $\alpha,\gamma>0$ are hyperparameters. With the hierarchy of the joint density for the posterior with the likelihood to the power $\eta$ becomes

$$\begin{gathered}
\label{eq:joint generalized density}
(f({Y} \rvert \mu,  {\beta}, \sigma^2))^\eta \, \pi(\sigma^2) \, \pi(\mu) \prod_{j=1}^p \, \pi( {\beta}_j \rvert \tau_j^2, \sigma^2 ) \, \pi(\tau_j^2) = \\ 
=\left( \frac{1}{(2\pi\sigma^2)^{n/2}} \,  e^{\frac{1}{2\sigma^2} ( {Y} -\mu  {1}_n -  {X \beta})^T  ( {Y} -\mu  {1}_n -  {X \beta})  }   \right) ^\eta 
\frac{\gamma^\alpha}{\Gamma(\alpha)}\sigma^{-2\alpha-2}e^{-\frac{\gamma}{\sigma^2}} \prod_{j=1}^p \frac{1}{(2\sigma^2\tau_j^2)^{1/2}} \, e^{- \frac{1}{2\sigma^2\tau_j^2}  {\beta}_j^2} \frac{\lambda^2}{2} \, e^{- \lambda^2\tau^2_j /2} \,.\end{gathered}$$

Let $ {\tilde{Y}}$ be $ {Y - \overline{Y}}$. If we integrate out $\mu$, the joint density marginal over $\mu$ is proportional to

$$\begin{aligned}
\label{eq:joint generalized density marginalized over mu}
\sigma^{-\eta(n-1)} \,  e^{-\frac{\eta}{2\sigma^2} ( {\tilde{Y}-X\beta})^T  ( {\tilde{Y}-X\beta})  } \,
\sigma^{-2\alpha-2} \, e^{-\frac{\gamma}{\sigma^2}} \prod_{j=1}^p \frac{1}{(\sigma^2\tau_j^2)^{1/2}} \, e^{- \frac{1}{2\sigma^2\tau_j^2}  {\beta}_j^2} \, e^{- \lambda^2\tau^2_j /2} .\end{aligned}$$

First, observe that the full conditional for $  \beta$ is multivariate normal: the exponent terms involving $ {\beta}$ in are

$$-\frac{\eta}{2\sigma^2} ( {\tilde{Y}-X\beta})^T  ( {\tilde{Y}-X\beta}) - \frac{1}{2\sigma^2}  {\beta}^T  {D_\tau}^{-1}  {\beta}= -\frac{1}{2\sigma^2} \left\lbrace ( {\beta}^T (\eta  {X}^T {X} +  {D_\tau}^{-1} ) {\beta} - 2\eta {\tilde{Y}X\beta} + \eta {\tilde{Y}}^T  {\tilde{Y}} ) \right\rbrace.$$

If we now write $M_\tau = (\eta  {X}^T {X} +  {D_\tau}^{-1})^{-1}$ and complete the square, we arrive at $$\begin{aligned}
&-\frac{1}{2\sigma^2} \left\lbrace ( {\beta} - \eta M_\tau  {X}^T  {\tilde{Y}})^T {M_\tau^{-1}} \, ( {\beta} - \eta {M_\tau} {X}^T  {\tilde{Y}}) +  {\tilde{Y}}^T (\eta  {I}_n - \eta^2  {X}^{-1}M_\tau {X}^T)  {\tilde{Y}} \right\rbrace .\end{aligned}$$

Accordingly we can see that $ {\beta}$ is conditionally multivariate normal with mean $\eta {M_\tau} {X}^T  {\tilde{Y}}$ and variance $\sigma^2 {M_\tau}$.\
The terms in that involve $\sigma^2$ are:

$$(\sigma^2)^{ \{ -\eta(n-1)/2 - p/2 - \alpha - 1 \} }
\exp \Big\{ -\frac{\eta}{2\sigma^2}( {\tilde{Y}-X\beta})^T  ( {\tilde{Y}-X\beta}) - \frac{1}{2\sigma^2} {\beta}^T  {D_\tau}^{-1}  {\beta} - \frac{\gamma}{\sigma^2}  \Big\} .$$

We can conclude that $\sigma^2$ is conditionally inverse gamma with shape parameter $\displaystyle \eta \, \frac{n-1}{2} + \frac{p}{2} + \alpha$ and scale parameter $\displaystyle \frac{\eta}{2}( {\tilde{Y}-X\beta})^T  ( {\tilde{Y}-X\beta}) +  {\beta}^T  {D_\tau}^{-1}  {\beta} /2 + \gamma$.\
\
Since $\tau_j^2$ is not involved in the likelihood, we need not modify the implementation of it and follow @Park: $$\frac{1}{\tau^2_j} \sim \text{IG}\left(\displaystyle \sqrt{{\lambda^2\sigma^2}/{\beta_j^2}}, \, \lambda^2\right).$$ Summarizing, we can implement a Gibbs sampler with the following distributions:

$$\begin{aligned}
 \label{Blasso:condbetagen}
 {\beta} &\sim \text{N} \left( \eta(\eta {X}^T {X} +  {D_\tau}^{-1})^{-1} {X}^T {\tilde{Y}}, \, \sigma^2(\eta {X}^T {X} +  {D_\tau}^{-1})^{-1} \right) \, , \\ \label{Blasso:condsigmagen}
\sigma^2 & \sim \text{Inv-Gamma} \big( \frac{\eta}{2}(n-1) + p/2 + \alpha,\, \frac{\eta}{2}( {\tilde{Y}-X\beta})^T  ( {\tilde{Y}-X\beta}) +  {\beta}^T  {D_\tau}^{-1}  {\beta}/2 + \gamma \big) \, , \\ \label{Blasso:condtausqgen}
\frac{1}{\tau^2_j} &\sim \text{IG}\left(\displaystyle \sqrt{{\lambda^2\sigma^2}/{\beta_j^2}}, \, \lambda^2\right) \, .\end{aligned}$$

There are several ways to deal with the shrinkage parameter $\lambda$. We follow the hierarchical Bayesian approach and place a hyperprior on the parameter. In our implementation we provide three ways to do so: a point mass (resulting in a fixed $\lambda$), a gamma prior on $\lambda^2$ following @Park and a beta prior following @deloscampos, details about the implementation of the latter two priors can be found in those papers respectively.

The $\eta$-generalized Bayesian logistic regression {#ap:logreg}
---------------------------------------------------

We follow the construction of the P[ó]{}lya–Gamma latent variable scheme for constructing a Bayesian estimator in the logistic regression context described in [@polson2013bayesian].

First, for $b>0$ consider the density function of a P[ó]{}lya-Gamma random variable $PG(b,0)$ $$p(x{\, |\, }b,0)=\frac{2^{b-1}}{\Gamma(b)}\sum_{n=1}^\infty (-1)^n\frac{\Gamma(n+b)}{\Gamma(n+1)}\frac{(2n+b)}{\sqrt{2\pi x^3}}e^{-\frac{(2n+b)^2}{8x}}.$$ The general class $PG(b,c)$ ($b,c>0$) is defined through an exponential tilting of the $PG(b,0)$ and has the density function $$p(x{\, |\, }b,c)=\frac{e^{-\frac{c^2x}2}p(x|b,0)}{{{\mathbb{E}}}e^{-\frac{c^2\omega}2}},$$ where $\omega\sim PG(b,0)$.

To derive our Gibbs sampler we use the following result from [@polson2013bayesian].

\[PG\_thm\] Let $p_{b,0}(\omega)$ denote the density of $PG(b,0)$. Then for all $a\in {\mathbb{R}}$ $$\frac{(e^\psi)^a}{(1+e^\psi)^b}=2^{-b}e^{\kappa \psi}\int_0^\infty e^{-\omega\psi^2/2}p_{b,0}(\omega)d\omega,$$ where $\kappa=a-b/2.$

According to Theorem \[PG\_thm\] the likelihood contribution of the observation $i$ taken to the power $\eta$ can be written as $$L_{i,\eta}(\beta)=\left[\frac{(e^{X_i^T\beta)^{y_i }}}{1+e^{X_i^T\beta}}\right]^\eta\propto e^{\eta\kappa_iX_i^T\beta}\int_0^\infty e^{-\omega_i\frac{(X_i^T\beta)^2}2}p(\omega_i{\, |\, }\eta,0),$$ where $\kappa_i\coloneqq y_i-1/2$ and $p(\omega_i{\, |\, }\eta,0)$ is the density function of $PG(\eta,0)$.

Let $$\begin{gathered}
X\coloneqq (X_1,\dots, X_n)^T, \quad Y\coloneqq (Y_1,\dots,Y_n)^T, \quad \kappa\coloneqq (\kappa_1,\dots,\kappa_n)^T, \\
\omega\coloneqq (\omega_1,\dots,\omega_n)^T,  \quad \Omega\coloneqq {{\text{diag}}}(\omega_1,\dots,\omega_n).\end{gathered}$$ Also, denote the density of the prior on $\beta$ by $\pi(\beta)$. Then the conditional posterior of $\beta$ given $\omega$ is $$p(\beta{\, |\, }\omega,Y)\propto \pi(\beta) \prod_{i=1}^n L_{i,\eta}(\beta{\, |\, }\omega_i)=\pi(\beta)\prod_{i=1}^ne^{\eta\kappa_iX_i^T\beta-\omega_i\frac{(X_i^T\beta)^2}2}\propto \pi(\beta)e^{-\frac12 (z-X\beta)^T\Omega(z-X\beta)},$$ where $z\coloneqq \eta(\frac{\kappa_1}{\omega_1},\dots,\frac{\kappa_n}{\omega_n})$. Observe that the likelihood part is conditionally Gaussian in $\beta$. Since the prior on $\beta$ is Gaussian, a simple linear-model calculation leads to the following Gibbs sampler. To sample from the the $\eta$-generalized posterior one has to iterate these two steps $$\begin{aligned}
\omega_i{\, |\, }\beta\sim& PG(\eta, X_i^T\beta),\\
\beta{\, |\, }Y,\omega\sim& {\ensuremath{\mathcal N}}(m_\omega, V_\omega), \end{aligned}$$ where $$\begin{aligned}
V_\omega\coloneqq &(X^T\Omega X+B^{-1})^{-1}, \\
m_\omega\coloneqq &V_\omega(\eta X^T\kappa+B^{-1}b).\end{aligned}$$

To sample from the P[ólya]{}-Gamma distribution $PG(b,c)$ we adopt a method from [@PG2014], which is based on the following representation result. According to [@polson2013bayesian] a random variable $\omega\sim PG(b,c)$ admits the following representation $$\omega {\overset{\mathrm{d}}{=}}\sum_{n=0}^\infty \frac{g_n}{d_n},$$ where $g_n\sim Ga(b,1)$ are independent Gamma distributed random variables, and $$d_n\coloneqq 2\pi^2(n+\frac12)^2+2c^2.$$

Therefore, we approximate the PG random variable by a truncated sum of weighted Gamma random variables. [@PG2014] shows that the approximation method performs well with the truncation level $N=300$. Furthermore, we performed our own comparison of the sampler with the STAN implementation for Bayesian logistic regression, which showed no difference between the methods (for $\eta=1$).

The Safe-Bayesian Algorithms {#ap:safebayesimpl}
----------------------------

The version of the Safe-Bayesian algorithm we are using for the experiments is called *R-log-SafeBayes*, more details and other versions can be found in @grunwald2017inconsistency. The $\hat{\eta}$ is chosen from a grid of learning rates $\eta$ that minimizes the *cumulative Posterior-Expected Posterior-Randomized log-loss*: $$\begin{aligned}
\sum_{i=1}^n \, {\operatorname{\mathbf{E}}}_{\beta, \sigma^2 \sim \Pi \rvert z^{i-1}, \eta}  \left[-\log f(Y_i \rvert X_i, \beta, \sigma^2) \right].\end{aligned}$$ Minimizing this comes down to minimizing $$\begin{aligned}
\sum_{i=1}^{n-1} \, \, \textsc{av} \left[ \frac{1}{2} \log 2 \pi \sigma^2_{i,\eta} + \frac{1}{2} \frac{(Y_{i+1} - X_{i+1}\beta_{i, \eta})^2}{\sigma^2_{i,\eta}} \right].\end{aligned}$$ The loss between the brackets is averaged over many draws of $(\beta_{i, \eta}, \sigma^2_{i,\eta})$ from the posterior, where $\beta_{i, \eta}$ (or $\sigma^2_{i,\eta}$) denotes one random draw from the conditional $\eta$-generalized posterior based on data points $z^{i}$. For the sake of completeness we present the algorithm below.\

$\mathcal{S}_n \coloneqq \{1, 2^{-\mathcal{K}_{\text{STEP}}}, 2^{-2\mathcal{K}_{\text{STEP}}}, 2^{-3\mathcal{K}_{\text{STEP}}}, \ldots, 2^{-\mathcal{K}_{\text{MAX}}}, \} $ Choose $\hat{\eta} \coloneqq \operatorname*{arg\,min}_{\eta \in \mathcal{S}_n} \{ s_\eta \}$ (if min achieved for several $\eta \in \mathcal{S}_n$, pick largest)

Details for the experiments and figures {#ap:detailsfigures}
=======================================

Below we present the results of additional simulation experiments for Section \[sec:lassoandhs\] (Appendix \[ap:simulations\]) and the description of experiments with real-world data (Appendix \[ap:realworld\]). We also give details for Figure \[fig:predvar\] in Appendix \[ap:delete\].

Additional Figures for Section \[sec:lassoandhs\] {#ap:simulations}
-------------------------------------------------

Consider the regression context described in Section \[sec:lassoandhs\]. Here, we explore different choices of the number of Fourier basis functions, showing that regardless of the choice Safe-Baysian lasso outperforms its standard counterpart. In Figures \[fig:b vs sb\] and \[fig:1\] we see conditional expectations ${\operatorname{\mathbf{E}}}\left[ Y \mid X \right]$ according to the posteriors of the standard Bayesian lasso (blue) and the Safe-Bayesian lasso (red, $\hat\eta = 0.5$) for the *wrong-model* experiment described in Section \[sec:lassoandhs\], with $100$ data points. We take $201$ and $25$ Fourier basis functions respectively.

Now we consider logistic regression setting and show that even for some well-specified problems it is beneficial to choose $\eta\neq 1$. In Figure \[fig:logregriskwell\] we see a comparison of the log-risk for $\eta=1$ and $\eta=3$ in the well-specified logistic regression case (described in Section \[sec:logisticregression\]). Here $p=1$ and $\beta=4$.

![Prediction of standard Bayesian lasso (blue) and Safe-Bayesian lasso (red, $\eta = 0.5$) with $n=200$, $p=100$.\[fig:b vs sb\]](Plaatje_B_vs_SB-eps-converted-to.pdf){width="50.00000%"}

![Prediction of standard Bayesian lasso (blue) and Safe-Bayesian lasso (red, $\eta = 0.5$) with $n=200$, $p=12$.\[fig:1\]](Bayes_vs_SB_dim25-eps-converted-to.pdf){width="50.00000%"}

![The empirical logistic risk as a function of the sample size for the *correct-model* experiments described in Section \[sec:logisticregression\] according to the posterior predictive distribution of standard Bayesian logistic regression ($\eta=1$), and generalized Bayes ($\eta=3$). \[fig:logregriskwell\]](LogitWell.pdf){width="45.00000%"}

Real-world data {#ap:realworld}
---------------

#### Seattle Weather Data {#ap:seattle}

The $\texttt{R}$-package $\texttt{weatherData}$ [@weatherData] loads weather data available online from $\texttt{www.wunderground.com}$. Besides data from many thousands of personal weather stations and government agencies, the website provides access to data from Automated Surface Observation Systems (ASOS) stations located at airports in the US, owned and maintained by the Federal Aviation Administration. Among them is a weather station at Seattle Tacoma International Airport, Washington (WMO ID $72793$). From this station we collected the data for this experiment.

The training data are the maximum temperatures for each day of the year 2011 at Seattle airport. We divided the data randomly in a training set (300 measurements) and a test set (65 measurements). First, we sampled the posterior of the standard Bayesian lasso with a 201-dimensional Fourier basis and standard improper priors on the training set, and we did the same for the Horseshoe. Next, we sampled the generalized posterior with the learning rate $\hat\eta$ learnt by the Safe-Bayesian algorithm, with the same model and priors on the same training set. The grid of $\eta$’s we used was $1, 0.9, 0.8, 0.7, 0.6, 0.5$. We compare the performance of the standard Bayesian lasso and Horseshoe and the Safe-Bayesian versions of the lasso (SB) in terms of mean square error. In all experiments performed with different partitions, priors and number of iterations, SafeBayes never picked $\hat\eta = 1$. We averaged over 10 runs. Moreover, whichever learning rate was chosen by SafeBayes, it always outperformed standard Bayes (with $\eta =1$) in an unchanged set-up. Experiments with different priors for $\lambda$ yielded similar results.

#### London Air Pollution Data {#ap:air}

As training set we use the following data. We start with the first four weeks of the year $2013$, starting at Monday January $7$ at midnight. We have a measurement for (almost) every hour until Sunday February $3^\text{rd}$, $23.00$. We also have data for the first four weeks of $2014$, starting at Monday January $6$ at midnight, until Sunday February $2^\text{nd}$, $23.00$. For each hour in the four weeks we randomly pick a data point from either $2013$ or $2014$. We remove the missing values. We predict for the same time of year in $2015$: starting at Monday January $5$ at midnight, until Sunday February $1^\text{st}$ at $23.00$. We do this with a (Safe-)Bayesian lasso and Horseshoe with a $201$-dimensional Fourier basis and standard improper priors. The grid of $\eta$’s we used for the Safe-Bayesian algorithm was again $1, 0.9, 0.8, 0.7, 0.6, 0.5$. We look at the mean square prediction errors, and average the errors over $20$ runs of the generalized Bayesian lasso with the $\eta$ learnt by SafeBayes, and the standard Bayesian lasso and Horseshoe. Again we find that SafeBayes performs substantially better than standard Bayes.

Details for Figure \[fig:predvar\] {#ap:delete}
----------------------------------

Here we sampled the posteriors of the standard and generalized Bayesian lasso ($\eta = 0.25$) on $50$ model-wrong data points (approximately half easy points) with $101$ Fourier basis functions, and estimated the predictive variance on a grid of new data points $X_{\text{new}} = \{ -1.00, -0.99, \ldots, 1.00 \}$ with the Monte Carlo estimate: $$\hat{\textsc{var}}(Y_{\text{new}} \mid X_{\text{new}}, Z_{\text{old}}) = \operatorname{\textbf{E}}_{\theta \mid Z_{\text{old}}} \left[ \textsc{var}(Y_{\text{new}} \mid \theta) \right] + \hat{\textsc{var}} \left[ \operatorname{\textbf{E}}(Y_{\text{new}} \mid \theta) \right],$$ where

$$\begin{gathered}
\operatorname{\textbf{E}}_{\theta \mid Z_{\text{old}}} \left[ \textsc{var}(Y_{\text{new}} \mid \theta) \right]  = \frac{1}{m} \sum_{k=1}^m \sigma^{2 \left[k \right]}
= \,\overline{\sigma^2},\\ 
\hat{\textsc{var}} \left[ \operatorname{\textbf{E}}(Y_{\text{new}} \mid \theta) \right] = \,\hat{\textsc{var}} \left[X_{\text{new}}\beta \right]=  \frac{1}{m} \sum_{k=1}^m \left( X_{\text{new}}\beta^{\left[ k \right]} \right)^2 - \left(X_{\text{new}}\overline{\beta}\right)^2.\end{gathered}$$

Here $\overline{\beta}$ is the posterior mean of the parameter for the coefficients and $\overline{\sigma^2}$ is the posterior mean of the variance.

[^1]: Some of the results in Section \[sec:genglm\] have been derived some time ago, and can also be found in the initial arxiv versions of GM. However, after consultation with the associate journal editor, it was decided that they are best placed in another paper; thus, in version v4 of the arxiv paper and the upcoming journal publication of GM, they have been removed.
