* Castillo et al., (2015) Castillo, I., Schmidt-Hieber, J., and van der Vaart, A.W.  Bayesian linear regression with sparse priors.  Ann. Statist., 5:1986–2018.
  * Catoni, (2004) Catoni, O. (2004).  Statistical Learning Theory and Stochastic Optimization, Lecture Notes in Mathematics.  Springer-Verlag.
  * Chernozhukov and Hong, (2003) Chernozhukov, V. and Hong, H. (2003).  An MCMC approach to classical estimation.  J. Econometrics 115(2):293–346.
  * Chib et al., (2018) Chib, S., Shin, M., and Simoni, A. (2018).  Bayesian estimation and comparison of moment condition models.  J. Am. Stat. Assoc. 113(524):1656–1668.
  * Choudhuri et al., (2007) Choudhuri, N., Ghosal, S., and Roy, A. (2007).  Nonparametric binary regression using a Gaussian process prior.  Stat. Methodol. 4:227–243.
  * De Blasi and Walker, (2013) De Blasi, P., Walker, S. G. (2013).  Bayesian asymptotics with misspecified models.  Statist. Sinica 23:169–187.
  * Fraser, (2011) Fraser, D. A. S. (2011).  Is Bayes posterior just quick and dirty confidence?  Statist. Sci. 26(3):299–316.
  * Gan et al., (2019) Gan, L., Narisetty, N. N., and Liang, F. (2019).  Bayesian regularization for graphical models With unequal shrinkage.  J. Am. Stat. Assoc. 114(527):1218–1231.
  * Ghosal et al., (2000) Ghosal, S., Ghosh, J. K., and van der Vaart, A. W. (2000).  Convergence rates of posterior distributions.  Ann. Statist. 28(2):500–531.
  * Godambe, (1991) Godambe, V. P., ed. (1991).  Estimating Functions.  Oxford University Press, New York.
  * Grünwald, (2012) Grünwald, P. (2012).  The safe Bayesian: learning the learning rate via the mixability gap.  Algorithmic Learning Theory, Springer, Heidelberg, 7568:169–183.
  * Grünwald and Mehta, (2020) Grünwald, P. and Mehta N. (2020).  Fast rates for unbounded losses.  J. Mach. Learn. Res. 21:1–80.
  * Grünwald and van Ommen, (2017) Grünwald, P. and van Ommen, T. (2017).  Inconsistency of Bayesian inference for misspecified models, and a proposal for repairing it.  Bayesian Anal. 12:1069–1103.
  * Guedj, (2019) Guedj, B. (2019).  A primer on PAC-Bayes learning.  arXiv:1901.05353.
  * Hedayat et al., (2015) Hedayat, S., Wang, J., and Xu, T. (2015).  Minimum clinically important difference in medical studies.  Biometrics 71:33–41.
  * Hjört and Pollard, (1993) Hjört, N. L., and Pollard, D. (1993).  Asymptotics for minimisers of convex processes.  http://www.stat.yale.edu/~pollard/Papers/convex.pdf.
  * Holmes and Walker, (2017) Holmes, C. C., and Walker, S. G. (2017).  Assigning a value to a power likelihood in a general Bayesian model.  Biometrika 104(2):497–503.
  * Huber and Ronchetti, (2009) Huber, P.J., and Ronchetti, E. (2009).  Robust Statistics. 2nd ed.  Wiley, New York.
  * Jaescheke et al., (1989) Jaescheke, R., Signer, J., and Guyatt, G. (1989).  Measurement of health status: ascertaining the minimum clinically important difference.  Control. Clin. Trials 10:407–415.
  * Jiang and Tanner, (2008) Jiang, W. and Tanner, M. A. (2008).  Gibbs posterior for variable selection in high- dimensional classification and data mining.  Ann. Statist. 36:2207–2231.
  * Kim, (2002) Kim, J.-Y. (2002).  Limited information likelihood and Bayesian analysis.  J. Econom. 107(1-2):175–193.
  * Kleijn and van der Vaart, (2006) Kleijn, B. J. K. and van der Vaart, A. W. (2006).  Misspecification in infinite-dimensional Bayesian statistics.  Ann. Statist. 34(2):837–877.
  * Koltchinskii, (1997) Koltchinskii, V. (1997).  M-estimation, convexity and quantiles.  Ann. Statist. 25(2):435–477.
  * Koltchinskii, (2006) Koltchinskii, V. (1997).  Local Rademacher complexities and oracle inequalities in risk minimization.  Ann. Statist. 34(6):2593–2656.
  * Kruschke, (2015) Kruschke, J. K. (2015).  Doing Bayesian Data Analysis: A Tutorial with R, JAGS, and Stan. Elsevier, New York.
  * Lafftery et al., (2010) Lafferty, J., Liu, H., and Wasserman, L. (2010).  Chapter 10: Concentration of Measure.  In Statistical Machine Learning, http://www.stat.cmu.edu/~larry/=sml/Concentration.pdf.
  * Lyddon et al., (2019) Lyddon, S. P., Holmes, C. C., and Walker, S. G. (2019).  General Bayesian updating and the loss-likelihood bootstrap.  Biometrika. 106(2):465–478.
  * Mammen and Tsybakov, (1995) Mammen, E., and Tsybakov, A. B. (1995).  Asymptotical minimax recovery of sets with smooth boundaries.  Ann. Statist. 23(2):502–524.
  * Mammen and Tsybakov, (1999) Mammen, E., and Tsybakov, A. B. (1999).  Smooth discrimination analysis.  Ann. Statist. 27(6):1808–1829.
  * Maronna et al., (2006) Maronna, R. A., Martin, D. R., and Yohai, V. J. (2006).  Robust Statistics: Theory and Methods Wiley Series in Probability and Statistics.
  * Martin, (2019) Martin, R. (2019).  False confidence, non-additive beliefs, and valid statistical inference.  Int. J. Approx. Reason. 113:39–73.
  * Martin et al., (2013) Martin, R., Hong, L., and Walker, S.G. (2013).  A note on Bayesian convergence rates under local prior support conditions.  arXiv:1201.3102.
  * Martin et al., (2017) Martin, R., Mess, R., and Walker, S.G. (2017).  Empirical Bayes posterior concentration in sparse high-dimensional linear models.  Bernoulli 23:1822–1847.
  * Massart and Nedelec, (2006) Massart, P., and Nedelec, E. (2006).  Risk bounds for statistical learning.  Ann. Statist. 34(5):2326–2366.
  * McAllester, (1999) McAllester, D. (1999).  PAC-Bayesian model averaging.  COLT‘99 164–170.
  * Ramamoorthi et al., (2015) Ramamoorthi, R.V., Sriram, K., and Martin, R. (2015).  On posterior concentration in misspecified models.  Bayesian Anal. 10(4):759–789.
  * Shalizi, (2009) Shalizi, C. R. (2009).  Dynamics of Bayesian updating with dependent data and misspecified models.  Electron. J. Stat. 3:1039–1074.
  * Shen and Ghosal, (2015) Shen, W. and Ghosal, S. (2015).  Adaptive Bayesian procedures using random series priors.  Scand. J. Stat. 42:1194–1213.
  * Shen and Wasserman, (2001) Shen, X. and Wasserman, L. (2001).  Rates of convergence of posterior distributions.  Ann. Statist. 29(3):687–714.
  * Sriram et al., (2013) Sriram, K., Ramamoorthi, R. V., and Ghosh, P. (2013)  Posterior consistency of Bayesian quantile regression based on the misspecified asymmetric Laplace density.  Bayesian Anal. 8(2):479–504.
  * Syring and Martin, (2017) Syring, N. and Martin, R. (2017).  Gibbs posterior inference on the minimum clinically important difference.  J. Statist. Plann. Inference 187:67–77.
  * Syring and Martin, (2019) Syring, N. and Martin, R. (2019).  Calibration of general posterior credible regions.  Biometrika 106(2):479–486.
  * Syring and Martin, (2020) Syring, N. and Martin, R. (2020).  Robust and rate optimal Gibbs posterior inference on the boundary of a noisy image.  Ann. Statist. 48(3):1498–1513.
  * Takeuchi et al., (2006) Takeuchi, I., Le, Q. V., Sears, T. D., and Smola, A. J. (2006).  Nonparametric quantile estimation.  J. Mach. Learn. Res. 7:1231–1264.
  * Tsybakov, (2004) Tsybakov, A. (2004).  Optimal aggregation of classifiers in statistical learning  Ann. Statist. 32(1):135–166.
  * Valiant, (1984) Valiant, L.G. (1984).  A theory of the learnable.  Communications of the ACM 27(11):1134–1142.
  * van der Vaart, (1998) van der Vaart, A. W. (1998).  Asymptotic Statistics.  Cambridge University Press, Cambridge.
  * van Erven and Harremoës, (2014) van Erven, T. and Harremoës, P. (2014).  Rényi divergence and Kullback–Leibler divergence.  IEEE Trans. Inform. Theory 60(7):3797–3820.
  * van Erven et al., (2015) van Erven, T., Grünwald, P., Mehta, N., Reid, M. and Williamson, R. (2015).  Fast rates in statistical and online learning.  J. Mach. Learn. Res. 16:1793–1861.
  * Wang and Martin, (2020) Wang, Z. and Martin, R. (2020).  Model-free posterior inference on the area under the receiver operating characteristic curve.  J. Statist. Plann. Inference 209:174–186.
  * Wu and Martin, (2020) Wu, P.-S. and Martin, R. (2020).  A comparison of learning rate selection methods in generalized Bayesian inference.  arXiv:2012.11349.
  * Wu and Martin, (2021) Wu, P.-S. and Martin, R. (2021).  Calibrating generalized predictive distributions.  arXiv:2107.01688.
  * Zhang, (2006) Zhang, T. (2006).  Information theoretical upper and lower bounds for statistical estimation.  IEEE Trans. Inf. Theory 52(4):1307–1321.
  * Zhou et al., (2020) Zhou, Z, Zhao, J., and Bisson, L.J. (2020).  Estimation of data adaptive minimal clinically important difference with a nonconvex optimization procedure.  Stat. Methods Med. Res. 29(3):879–893.

##  Appendix A Proofs of the main theorems

###  A.1 Proof of Theorem 1

As a first step, we first state and prove a result that gives an in-
probability lower bound on the denominator of the Gibbs posterior, the so-
called partition function. The proof closely follows that of Lemma 1 in Shen
and Wasserman, (2001) but is, in some sense, more general, so we present the
details here for the sake of completeness.

######  Lemma 1.

Define

$D_{n}=\int
e^{-\omega\,n\\{R_{n}(\theta)-R_{n}(\theta^{\star})\\}}\,\Pi(d\theta).$ (57)

If $G_{n}=\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq\varepsilon_{n}^{r}\\}$ is as in (15), with
$\varepsilon_{n}$ satisfying $\varepsilon_{n}\to 0$ and
$n\varepsilon_{n}^{r}\to\infty$, then $D_{n}>\tfrac{1}{2}\Pi(G_{n})e^{-2\omega
n\varepsilon_{n}^{r}}$ with $P^{n}$-probability converging to 1.

###### Proof.

Define a standardized version of the empirical risk difference, i.e.,

$Z_{n}(\theta)=\frac{\\{nR_{n}(\theta)-nR_{n}(\theta^{\star})\\}-nm(\theta)}{\\{nv(\theta)\\}^{1/2}},$

where $m(\theta)=m(\theta,\theta^{\star})$ and
$v(\theta)=v(\theta,\theta^{\star})$, the mean and variance of the risk
difference. Of course, $Z_{n}(\theta)$ depends (implicitly) on the data
$U^{n}$. Let

$\mathcal{Z}_{n}=\\{(\theta,U^{n}):|Z_{n}(\theta)|\geq(n\varepsilon_{n}^{r})^{1/2}\\}.$

Next, define the cross-sections

$\mathcal{Z}_{n}(\theta)=\\{U^{n}:(\theta,U^{n})\in\mathcal{Z}_{n}\\}\quad\text{and}\quad\mathcal{Z}_{n}(U^{n})=\\{\theta:(\theta,U^{n})\in\mathcal{Z}_{n}\\}.$

For $G_{n}$ as above, since

$nR_{n}(\theta)-nR_{n}(\theta^{\star})=nm(\theta)+\\{nv(\theta)\\}^{1/2}Z_{n}(\theta),$

and $m$, $v$, and $Z_{n}$ are suitably bounded on
$G_{n}\cap\mathcal{Z}_{n}(U^{n})^{c}$, we immediately get

$D_{n}\geq\int_{G_{n}\cap\mathcal{Z}_{n}(U^{n})^{c}}e^{-\omega
nm(\theta)-\omega\\{nv(\theta)\\}^{1/2}Z_{n}(\theta)}\,\Pi(d\theta)\geq
e^{-2\omega
n\varepsilon_{n}^{r}}\Pi\\{G_{n}\cap\mathcal{Z}_{n}(U^{n})^{c}\\}.$

From this lower bound, we get

$\displaystyle P^{n}\\{D_{n}\leq\tfrac{1}{2}\Pi(G_{n})e^{-2\omega
n\varepsilon_{n}^{r}}\\}$ $\displaystyle\leq P^{n}\bigl{[}e^{-2\omega
n\varepsilon_{n}^{r}}\Pi\\{G_{n}\cap\mathcal{Z}_{n}(U^{n})^{c}\\}\leq\tfrac{1}{2}\Pi(G_{n})e^{-2\omega
n\varepsilon_{n}^{r}}\bigr{]}$
$\displaystyle=P^{n}\bigl{[}\Pi\\{G_{n}\cap\mathcal{Z}_{n}(U^{n})\\}\geq\tfrac{1}{2}\Pi(G_{n})\bigr{]}$
$\displaystyle\leq\frac{2P^{n}\Pi\\{G_{n}\cap\mathcal{Z}_{n}(U^{n})\\}}{\Pi(G_{n})},$

where the last line is by Markov’s inequality. We can then simplify the
expectation in the upper bound displayed above using Fubini’s theorem:

$\displaystyle P^{n}\Pi\\{G_{n}\cap\mathcal{Z}_{n}(U^{n})\\}$
$\displaystyle=\int\int 1\\{\theta\in
G_{n}\cap\mathcal{Z}_{n}(U^{n})\\}\,\Pi(d\theta)\,P^{n}(dU^{n})$
$\displaystyle=\int\int 1\\{\theta\in
G_{n}\\}\,1\\{\theta\in\mathcal{Z}_{n}(U^{n})\\}\,P^{n}(dU^{n})\,\Pi(d\theta)$
$\displaystyle=\int_{G_{n}}P^{n}\\{\mathcal{Z}_{n}(\theta)\\}\,\Pi(d\theta).$

By Chebyshev’s inequality,
$P^{n}\\{\mathcal{Z}_{n}(\theta)\\}\leq(n\varepsilon_{n}^{r})^{-1}$, and hence

$P^{n}\\{D_{n}\leq\tfrac{1}{2}\Pi(G_{n})e^{-2\omega
n\varepsilon_{n}^{r}}\\}\leq 2(n\varepsilon_{n}^{r})^{-1}.$

Finally, since $n\varepsilon_{n}^{r}\to\infty$, the left-hand side vanishes,
completing the proof. ∎

For the proof of Theorem 1, write

$\Pi_{n}(A_{n})=\frac{N_{n}(A_{n})}{D_{n}},$

where $A_{n}=\\{\theta:d(\theta;\theta^{\star})>M\varepsilon_{n}\\}$, $D_{n}$
is as in (57), and

$N_{n}(A_{n})=\int_{A_{n}}e^{-\omega\,n\\{R_{n}(\theta)-R_{n}(\theta^{\star})\\}}\,\Pi(d\theta).$

For $G_{n}$ as in Lemma 1, write $b_{n}=\frac{1}{2}\Pi(G_{n})e^{-2\omega
n\varepsilon_{n}^{r}}$ for the lower bound on $D_{n}$. Then

$\displaystyle\Pi_{n}(A_{n})$
$\displaystyle\leq\frac{N_{n}(A_{n})}{D_{n}}\,1(D_{n}>b_{n})+1(D_{n}\leq
b_{n})$ $\displaystyle\leq b_{n}^{-1}N_{n}(A_{n})+1(D_{n}\leq b_{n}).$

By Fubini’s theorem, independence of the data $U^{n}$, and Condition 1, we get

$P^{n}N_{n}(A_{n})=\int_{A_{n}}\\{Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}\\}^{n}\,\Pi(d\theta)<e^{-KM^{r}\omega
n\varepsilon_{n}^{r}}.$

Take expectation of $\Pi_{n}(A_{n})$ and plug in the upper bound above, along
with $\Pi(G_{n})\geq e^{-C_{1}n\varepsilon_{n}^{r}}$ from (15) and
$P^{n}(D_{n}\leq b_{n})\geq 2(n\varepsilon_{n}^{r})^{-1}$ from Lemma 1, to get

$P^{n}\Pi_{n}(A_{n})\leq 2e^{-(\omega
KM^{r}-C_{1}-2\omega)n\varepsilon_{n}^{r}}+2(n\varepsilon_{n}^{r})^{-1}.$

Since the right-hand side is vanishing for sufficiently large $M$, the claim
follows.

###  A.2 Proof of Theorem 2

A special case of this result was first presented in Bhattacharya and Martin,
(2020), but we are including the proof here for completeness.

Recall that the Gibbs posterior probability, $\Pi_{n}(A_{n})$, is a ratio,
namely, $N_{n}(A_{n})/D_{n}$. Both the numerator and denominator are
integrals, and the key idea here is to split the range of integration in the
numerator into countably many disjoint pieces as follows:

$\displaystyle N_{n}(A_{n})$
$\displaystyle=\int_{d(\theta,\theta^{\star})>M_{n}\varepsilon_{n}}e^{-\omega
n\\{R_{n}(\theta)-R_{n}(\theta^{\star})\\}}\,\Pi(d\theta)$
$\displaystyle=\sum_{t=1}^{\infty}\int_{tM_{n}\varepsilon_{n}<d(\theta,\theta^{\star})<(t+1)M_{n}\varepsilon_{n}}e^{-\omega
n\\{R_{n}(\theta)-R_{n}(\theta^{\star})\\}}\,\Pi(d\theta).$

Taking expectation of the left-hand side and moving it under the sum and under
the integral on the right-hand side, we need to bound

$\int_{tM_{n}\varepsilon_{n}<d(\theta,\theta^{\star})<(t+1)M_{n}\varepsilon_{n}}\\{Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}\\}^{n}\,\Pi(d\theta),\quad
t=1,2,\ldots.$

By Condition 1, on the given range of integration, the integrand is bounded
above by

$e^{-\omega Kn(tM_{n}\varepsilon_{n})^{r}}=e^{-\omega Kt^{r}M_{n}^{r}},$

so the expectation of the integral itself is bounded by

$e^{-Kt^{r}M_{n}^{r}}\Pi(\\{\theta:d(\theta,\theta^{\star})<(t+1)M_{n}\varepsilon_{n}\\}),\quad
t=1,2,\ldots$

Since $\Pi$ has a bounded density on the $q$-dimensional parameter space, we
clearly have

$\Pi(\\{\theta:d(\theta,\theta^{\star})<(t+1)M_{n}\varepsilon_{n}\\})\lesssim\\{(t+1)M_{n}\varepsilon_{n}\\}^{q}.$

Plug all this back into the summation above to get

$P^{n}N_{n}(A_{n})\lesssim(M_{n}\varepsilon_{n})^{q}\sum_{t=1}^{\infty}(t+1)^{q}e^{-\omega
Kt^{r}M_{n}^{r}}.$

The above sum is finite for all $n$ and bounded by a multiple of $e^{-\omega
M_{n}^{r}}$. Then $M_{n}^{q}$ times the sum is vanishing as $n\to\infty$ and,
consequently, we find that the expectation of the Gibbs posterior numerator is
$o(\varepsilon_{n}^{q})$.

For the denominator $D_{n}$, we can proceed just like in the proof of Lemma 1.
The key difference is that we redefine

$\mathcal{Z}_{n}=\\{(\theta,U^{n}):|Z_{n}(\theta)|\geq(Qn\varepsilon_{n}^{r})^{1/2}\\},$

with an arbitrary constant $Q>1$, so that

$P^{n}\\{D_{n}\leq\tfrac{1}{2}\Pi(G_{n})e^{-2Q\omega
n\varepsilon_{n}^{r}}\\}\leq 2(Qn\varepsilon_{n}^{r})^{-1}.$

Then, just like in the proof of Theorem 1, since $n\varepsilon_{n}^{r}=1$, we
have

$P^{n}\Pi_{n}(A_{n})\leq\frac{o(\varepsilon_{n}^{q})}{e^{-2Q\omega}\varepsilon_{n}^{q}}+2Q^{-1},$

which implies

$\limsup_{n\to\infty}P^{n}\Pi_{n}(A_{n})\leq 2Q^{-1}.$

Since $Q$ is arbitrary, we conclude that $P^{n}\Pi_{n}(A_{n})\to 0$,
completing the proof.

###  A.3 Proof of Theorem 3

The proof is nearly identical to that of Theorem 1. Begin with

$\Pi_{n}(A_{n})=\frac{N_{n}(A_{n})}{D_{n}},$

where $A_{n}=\\{\theta:d(\theta;\theta^{\star})>M\varepsilon_{n}\\}$, $D_{n}$
is as in (57), and

$N_{n}(A_{n})=\int_{A_{n}}e^{-\omega_{n}\,n\\{R_{n}(\theta)-R_{n}(\theta^{\star})\\}}\,\Pi(d\theta).$

When the learning rate is a sequence $\omega_{n}$ rather than constant, Lemma
1 can be applied with no alterations provided
$n\omega_{n}\varepsilon_{n}^{r}\rightarrow\infty$, as assumed in the statement
of Theorem 3. Then, for $G_{n}$ as in Lemma 1, write
$b_{n}=\frac{1}{2}\Pi(G_{n})e^{-2\omega_{n}n\varepsilon_{n}^{r}}$ for the
lower bound on $D_{n}$. Bound the posterior probability of $A_{n}$ by

$\displaystyle\Pi_{n}(A_{n})$
$\displaystyle\leq\frac{N_{n}(A_{n})}{D_{n}}\,1(D_{n}>b_{n})+1(D_{n}\leq
b_{n})$ $\displaystyle\leq b_{n}^{-1}N_{n}(A_{n})+1(D_{n}\leq b_{n}).$

By Fubini’s theorem, independence of the data $U^{n}$, and Condition 1, we get

$P^{n}N_{n}(A_{n})=\int_{A_{n}}\\{Pe^{-\omega_{n}(\ell_{\theta}-\ell_{\theta^{\star}})}\\}^{n}\,\Pi(d\theta)<e^{-KM^{r}\omega_{n}n\varepsilon_{n}^{r}}.$

Take expectation of $\Pi_{n}(A_{n})$ and plug in the upper bound above, along
with $\Pi(G_{n})\gtrsim e^{-C\omega_{n}n\varepsilon_{n}^{r}}$ from (17) and
$P^{n}(D_{n}\leq b_{n})=o(1)$ from Lemma 1, to get

$P^{n}\Pi_{n}(A_{n})\lesssim
e^{-(KM^{r}-C-2)\omega_{n}n\varepsilon_{n}^{r}}+o(1).$

Since the right-hand side is vanishing for sufficiently large $M$, the claim
follows.

###  A.4 Proof of Theorem 4

First note that if the conditions of Theorem 3 hold for $\omega_{n}$, then
$\Pi_{n}^{\omega_{n}/2}$ also concentrates at rate $\varepsilon_{n}$. That is,
at least asymptotically, there is no difference between the learning rates
$\omega_{n}$ and $\omega_{n}/2$.

Next, as in the proof of Theorem 1, denote the numerator and denominator of
$\Pi_{n}^{\hat{\omega}_{n}}(A)$ by $N_{n}^{\hat{\omega}_{n}}(A)$ and
$D_{n}^{\hat{\omega}_{n}}$. Let
$W=\\{U^{n}:\omega_{n}/2<\hat{\omega}_{n}<\omega_{n}\\}$. By the assumptions
of Theorem 4, $P^{n}1(W)\rightarrow 1$, so in the argument below we focus on
bounding the numerator and denominator of the Gibbs posterior given $W$.

Restricting to the set $W$, using Lemma 1, and noting that $\omega\mapsto
e^{-2n\omega\varepsilon_{n}^{r}}$ decreases in $\omega$ we have
$D_{n}^{\hat{\omega}_{n}}>b_{n}$ with $P^{n}-$probability approaching $1$
where

$b_{n}=\tfrac{1}{2}\Pi(G_{n})e^{-2n\omega_{n}\varepsilon_{n}^{r}}\gtrsim
e^{-C_{1}n\omega_{n}\varepsilon_{n}^{r}}$

for some $C_{1}>0$, where the last inequality follows from (17).

Set $\mathbb{W}=\\{\theta:R_{n}(\theta)-R_{n}(\theta^{\star})>0\\}$ and then
bound the numerator as as follows:

$\displaystyle N_{n}^{\hat{\omega}_{n}}(A_{n})$
$\displaystyle=N_{n}^{\hat{\omega}_{n}}(A_{n}\cap\mathbb{W})+N_{n}^{\hat{\omega}_{n}}(A_{n}\cap\mathbb{W}^{c})$
$\displaystyle\leq\int_{A_{n}\cap\mathbb{W}}e^{-\omega_{n}/2[R_{n}(\theta)-R_{n}(\theta^{\star})]}\Pi(d\theta)+\int_{A_{n}\cap\mathbb{W}^{c}}e^{-\omega_{n}[R_{n}(\theta)-R_{n}(\theta^{\star})]}\Pi(d\theta)$
$\displaystyle\leq\int_{A_{n}}e^{-\omega_{n}/2[R_{n}(\theta)-R_{n}(\theta^{\star})]}\Pi(d\theta)+\int_{A_{n}}e^{-\omega_{n}[R_{n}(\theta)-R_{n}(\theta^{\star})]}\Pi(d\theta)$
$\displaystyle=N_{n}^{\omega_{n}/2}(A_{n})+N_{n}^{\omega_{n}}(A_{n}).$

Then, by Condition 1, Fubini’s theorem, and independence of $U^{n}$, we have

$P^{n}N_{n}^{\hat{\omega}_{n}}(A_{n})\leq
2e^{-(1/2)KM^{r}n\omega_{n}\varepsilon_{n}^{r}}.$

Similar to the proof of Theorem 1, we can bound
$\Pi_{n}^{\hat{\omega}_{n}}(A_{n})$ using the above exponential bounds on
$N_{n}^{\hat{\omega}_{n}}(A_{n})$ and $D_{n}^{\hat{\omega}_{n}}$:

$\displaystyle\Pi_{n}^{\hat{\omega}_{n}}(A_{n})$ $\displaystyle\leq
1(W)N_{n}^{\hat{\omega}_{n}}(A_{n})/D_{n}^{\hat{\omega}_{n}}+1(W^{c})$
$\displaystyle\leq
1(W)b_{n}^{-1}N_{n}^{\hat{\omega}_{n}}(A_{n})+1(W)1(D_{n}\leq
b_{n})+1(W^{c}).$

Taking expectation of $\Pi_{n}^{\hat{\omega}_{n}}(A_{n})$ and applying the
numerator and denominator bounds and the fact $P^{n}(W)\rightarrow 1$, we have

$P^{n}\Pi_{n}^{\hat{\omega}_{n}}(A_{n})\lesssim
e^{-n\omega_{n}\varepsilon_{n}^{r}(M^{r}K/2-C_{1})}+o(1).$

The result follows since $M>0$ is arbitrary.

###  A.5 Proof of Theorem 5

The proof is very similar to that of Theorem 1. Start with the decomposition

$\Pi_{n}(A_{n})=\Pi_{n}(A_{n}\cap\Theta_{n})+\Pi_{n}(A_{n}\cap\Theta_{n}^{\text{\sc
c}}),$

where $A_{n}=\\{\theta:d(\theta;\theta^{\star})>M\varepsilon_{n}\\}$ and
$\Theta_{n}$ is defined in Condition 2. We consider the first term in the
above decomposition. As before, we have

$\Pi_{n}(A_{n}\cap\Theta_{n})=\frac{N_{n}(A_{n}\cap\Theta_{n})}{D_{n}},$

for $D_{n}$ is as in (57), and

$N_{n}(A_{n}\cap\Theta_{n})=\int_{A_{n}\cap\Theta_{n}}e^{-\omega\,n\\{R_{n}(\theta)-R_{n}(\theta^{\star})\\}}\,\Pi(d\theta).$

Apply Lemma 1, with $G_{n}=\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq(K_{n}\varepsilon_{n})^{r}\\}$, and write

$b_{n}=\tfrac{1}{2}\Pi(G_{n})e^{-2\omega nK_{n}^{r}\varepsilon_{n}^{r}}$

for the lower bound on $D_{n}$. This immediately leads to

$\displaystyle\Pi_{n}(A_{n}\cap\Theta_{n})$
$\displaystyle\leq\frac{N_{n}(A_{n}\cap\Theta_{n})}{D_{n}}\,1(D_{n}>b_{n})+1(D_{n}\leq
b_{n})$ $\displaystyle\leq b_{n}^{-1}N_{n}(A_{n}\cap\Theta_{n})+1(D_{n}\leq
b_{n}).$

By Fubini’s theorem, independence of the data $U^{n}$, and Condition 2, we get

$P^{n}N_{n}(A_{n}\cap\Theta_{n})=\int_{A_{n}\cap\Theta_{n}}\\{Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}\\}^{n}\,\Pi(d\theta)<e^{-K_{n}M^{r}\omega
n\varepsilon_{n}^{r}}.$

Take expectation of $\Pi_{n}(A_{n}\cap\Theta_{n})$ and plug in the upper bound
above, along with $\Pi(G_{n})\gtrsim e^{-CK_{n}n\varepsilon_{n}^{r}}$ from
(25) and $P^{n}(D_{n}\leq b_{n})=o(1)$ from Lemma 1, to get

$P^{n}\Pi_{n}(A_{n}\cap\Theta_{n})\lesssim
e^{-(M^{r}\omega-C-2)K_{n}n\varepsilon_{n}^{r}}+o(1).$

Since the right-hand side is vanishing for sufficiently large $M$, we can
conclude that

$\limsup_{n\to\infty}P^{n}\Pi_{n}(A_{n}\cap\Theta_{n})\leq\limsup_{n\to\infty}P^{n}\Pi_{n}(A_{n}\cap\Theta_{n}^{\text{\sc
c}}).$

Of course, if (26), then the upper bound in the above display is 0 and we
obtained the claimed Gibbs posterior concentration rate result.

##  Appendix B A strategy for checking (26)

######  Lemma 2.

The Gibbs posterior distribution satisfies (26) if the following conditions
hold:

  1. 1.

$\theta\mapsto\ell_{\theta}(u)$ is convex,

  2. 2.

$\inf_{\\{\theta:d(\theta,\theta^{\star})>\delta\\}}R(\theta)-R(\theta^{\star})>0$
for all $\delta>0$, and

  3. 3.

The prior distribution satisfies (15).

###### Proof.

Let $A:=\\{\theta:d(\theta,\theta^{\star})>\varepsilon\\}$ for any fixed
$\varepsilon>0$ and write the Gibbs posterior probability of $A$ as

$\Pi_{n}(A)=\frac{N_{n}(A)}{D_{n}}:=\frac{\int_{A}e^{-n[R_{n}(\theta)-R_{n}(\theta^{\star})]}\Pi(d\theta)}{\int
e^{-n[R_{n}(\theta)-R_{n}(\theta^{\star})]}\Pi(d\theta)}.$

Assumption 2 implies the minimizer $\hat{\theta}_{n}$ of $R_{n}(\theta)$
converges to $\theta^{\star}$ in $P^{n}$-probability; see Hjört and Pollard,
(1993), Lemmas 1–2. Therefore, assume
$d(\hat{\theta}_{n},\theta^{\star})\leq\varepsilon/2$ since

$\\{U^{n}:(\Pi_{n}(A)>a)\cap(d(\hat{\theta}_{n},\theta^{\star})>\varepsilon/2)\\}\rightarrow
0$

in $P^{n}-$probability. By convexity, and the fact that
$\hat{\theta}_{n}\notin A$,

$R_{n}(\theta)-R_{n}(\theta^{\star})\geq\inf_{u}\\{R_{n}(\theta^{\star}+(\varepsilon/2)u)-R_{n}(\theta^{\star})\\},$

where the infimum is over all unit vectors. The infimum on the RHS of the
above display converges to a positive number, say $\psi>0$, in
$P^{n}-$probability by Lemma 1 in Hjört and Pollard, (1993). Therefore,

$\lim\inf_{\theta\in A}R_{n}(\theta)-R_{n}(\theta^{\star})\geq\eta$

with $P^{n}-$probability converging to $1$. Uniform convergence of the
empirical risk functions implies

$N_{n}(A)\leq e^{-n\psi}\Pi(A)$

with $P^{n}$-probability converging to $1$ as $n\to\infty$. Combining this
upper bound on $N_{n}(A)$ with the lower bound on $D_{n}$ provided by Lemma 1
we have

$\Pi_{n}(A)\leq e^{-n(\psi-C_{1}\varepsilon_{n}^{r})}\rightarrow 0$

where the bound vanishes because $\psi>C_{1}\varepsilon_{n}^{r}$ for all large
enough $n$. By the bounded convergence theorem, $P^{n}\Pi_{n}(A)\rightarrow
0$, as claimed. ∎

##  Appendix C Details for the examples in Section 5

###  C.1 Proof of Proposition 1

The proof proceeds by checking the conditions of the extended version of
Theorem 2, that based on Condition 2. First, we confirm that $R(\theta)$ is
minimized at $\theta^{\star}$. Write

$\displaystyle R(\theta)=\int_{\mathbb{X}}\Bigl{[}$
$\displaystyle(\tau-1)\int_{-\infty}^{\theta^{\top}f(x)}\\{y-\theta^{\top}f(x)\\}\,p_{x}(y)\,dy$
$\displaystyle+\tau\int_{\theta^{\top}f(x)}^{\infty}\\{y-\theta^{\top}f(x)\\}\,p_{x}(y)\,dy\Bigr{]}\,P(dx).$

Assumption 1.1–2 implies $R(\theta)$ can be differentiated twice under the
integral:

$\displaystyle\dot{R}(\theta)$ $\displaystyle=\int
f(x)\\{P_{x}(\theta^{\top}f(x))-\tau\\}\,P(dx)$
$\displaystyle\ddot{R}(\theta)$ $\displaystyle=\int
f(x)f(x)^{\top}\,p_{x}(\theta^{\top}f(x))\,P(dx),$

where $P_{x}$ denotes the distribution function corresponding to the density
$p_{x}$. By definition, $P_{x}(\theta^{\star\top}f(x))=\tau$, so it follows
that $\dot{R}(\theta^{\star})=0$. Moreover, the following Taylor approximation
holds in the neighborhood $\\{\theta:\|\theta-\theta^{\star}\|<\delta\\}$:

$R(\theta)=\tfrac{1}{2}(\theta-\theta^{\star})^{\top}\ddot{R}(\theta^{\star})(\theta-\theta^{\star})+o(\|\theta-\theta^{\star}\|^{2}),$

where Assumption 1.2. implies $\ddot{R}(\theta^{\star})$ is positive definite.
Then, $R(\theta)$ is convex and minimized at $\theta^{\star}$.

Next, note $\ell_{\theta}(u)$ satisfies a Lipschitz property:

$\|\ell_{\theta}-\ell_{\theta^{\prime}}\|\leq L\|\theta-\theta^{\prime}\|,$

where $L=\max\\{\tau,1-\tau\\}\|f(x)\|$. This follows from considering the
cases $y<\theta^{\top}f(x)<\theta^{\prime\top}f(x)$,
$\theta^{\top}f(x)<y<\theta^{\prime\top}f(x)$, and
$\theta^{\top}f(x)<\theta^{\prime\top}f(x)<y$, and the Cauchy–Schwartz
inequality. By Assumption 1.1., $L$ is uniformly bounded in $x$. Then, using
the Taylor approximation for $R(\theta)$ above and following the strategy laid
out in Section 4.1 we have

$Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}\leq
e^{-\omega\|\theta-\theta^{\star}\|^{2}(a-\omega L^{2}/2)}$

where $2a>0$ is bounded below by the smallest eigenvalue of
$\ddot{R}(\theta^{\star})$. Therefore, Condition 2 holds for all sufficiently
small learning rates, i.e., $\omega<2aL^{-2}$.

Assumption 1.3 says the prior density is bounded away from zero in a
neighborhood of $\theta^{\star}$. By the above computations,

$\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq\delta\\}\supset\\{\theta:\|\theta-\theta^{\star}\|<C\delta\\}$

for all small enough $\delta>0$ and some $C>0$. Therefore,

$\Pi(\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq\delta\\})\geq\Pi(\\{\theta:\|\theta-\theta^{\star}\|<C\delta\\})\gtrsim\delta^{J},$

verifying (16).

Since $\theta\mapsto\ell_{\theta}(u)$ is convex and the Taylor approximation
for $R(\theta)$ implies that

$\|\theta-\theta^{\star}\|>\delta\implies
m(\theta,\theta^{\star})\gtrsim\delta^{2},$

the conditions of Lemma 2 hold.

###  C.2 Proof of Proposition 2

For $\lambda\in(0,1)$ as in Assumption 2.1, define

$\omega_{n}=\frac{m+n}{2mn}\Bigl{(}\frac{\tau_{10}}{\lambda}+\frac{\tau_{01}}{1-\lambda}\Bigr{)}^{-1},$

where $\tau_{10}$ and $\tau_{01}$ are not both 0, so that

$(m+n)\omega_{n}\to\\{2(\lambda\tau_{01}+(1-\lambda)\tau_{10})\\}^{-1}.$

For any deterministic sequence $a_{n}$, with $a_{n}\to\infty$, the learning
rate $a_{n}\omega_{n}$ vanishes strictly more slowly than $\min(m,n)^{-1}$,
and, therefore, according to Theorem 1 in Wang and Martin, (2020), the Gibbs
posterior with learning rate $a_{n}\omega_{n}$ concentrates at rate $n^{-1/2}$
in the sense of Definition 4(b). By the law of large numbers,
$\hat{\tau}_{01}\rightarrow\tau_{01}$ and
$\hat{\tau}_{10}\rightarrow\tau_{10}$ in $P^{n}$-probability, so

$(m+n)\hat{\omega}_{n}\rightarrow\\{2(\lambda\tau_{01}+(1-\lambda)\tau_{10})\\}^{-1}\quad\text{in
$P^{n}$-probability}.$

Therefore, for any $\alpha\in(1/2,1)$, we have

$P(\tfrac{1}{2}a_{n}\omega_{n}<\alpha
a_{n}\hat{\omega}_{n}<a_{n}\omega_{n})\to 1,$

and it follows from Theorem 4 that the Gibbs posterior with learning rate
$\alpha a_{n}\hat{\omega}_{n}$ also concentrates at rate $n^{-1/2}$. Finally,
since $a_{n}$ is arbitrary, the constant $\alpha$ is unimportant and may be
implicitly absorbed into $a_{n}$. Therefore, the conclusion of Proposition 2,
omitting $\alpha$, also holds.

###  C.3 Proof of Proposition 3a

The proof proceeds by checking the conditions of Theorem 2. The excess loss
can be written
$\ell_{\theta}(u)-\ell_{\theta^{\star}}(u)=(\theta^{\star}-\theta)^{\top}x\,\\{2y-(\theta+\theta^{\star})^{\top}x\\}$.
To verify Condition 1, we start by computing the conditional expectation of
$e^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}$, given $X=x$, using the
fact that $P_{Y|x}Y=x^{\top}\theta^{\star}$. Throughout we take
$\omega<(4Bb)^{-1}$, where Assumption 3a(2). implies $|\theta^{\top}X|<B$ and
$b$ is given in Assumption 3a. Specifically, $Y$ given $x$ is subexponential
with parameters $(\sigma^{2},\,b)$, so that
$Pe^{tY}<\exp\\{tx^{\top}\theta^{\star}+t^{2}\sigma^{2}/2\\}$ for all
$t<(2b)^{-1}$. In the loss difference, add and subtract
$2\omega(\theta^{\star}-\theta)^{\top}x$ times $x^{\top}\theta^{\star}$ and
apply Assumption 3a(1) to get the following bounds:

$\displaystyle Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}$
$\displaystyle=Pe^{-\omega(\theta^{\star}-\theta)^{\top}X\\{2Y-(\theta+\theta^{\star})^{\top}X\\}}$
$\displaystyle\leq
P_{X}P_{Y|X}e^{\omega(\theta^{\star}-\theta)^{\top}X(\theta+\theta^{\star})^{\top}X}e^{-2\omega(\theta^{\star})^{\top}X(\theta^{\star}-\theta)^{\top}X}e^{-2\omega(\theta^{\star}-\theta)^{\top}X(Y-X^{\top}\theta^{\star})}$
$\displaystyle\leq
P_{X}e^{\omega(\theta^{\star}-\theta)^{\top}X(\theta+\theta^{\star})^{\top}X}e^{-2\omega(\theta^{\star})^{\top}X(\theta^{\star}-\theta)^{\top}X}e^{2\omega^{2}\sigma^{2}[(\theta^{\star}-\theta)^{\top}X]^{2}}$
$\displaystyle\leq
P_{X}e^{-\omega(1-2\omega\sigma^{2})\\{(\theta^{\star}-\theta)^{\top}X\\}^{2}}.$

From Assumptions 3a(2) and 3a(3), respectively, we have
$(\theta^{\star}-\theta)^{\top}(PXX^{T})(\theta^{\star}-\theta)\geq
c\|\theta-\theta^{\star}\|_{2}^{2}$ for some $c>0$ and
$\\{(\theta^{\star}-\theta)^{\top}X\\}^{2}\leq 4B^{2}$. These bounds, together
with Lemma 7.26 in Lafftery et al., (2010), imply

$\displaystyle Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}$
$\displaystyle\leq
P_{X}e^{-\omega(1-2\omega\sigma^{2})\\{(\theta^{\star}-\theta)^{\top}X\\}^{2}}$
$\displaystyle\leq
e^{-\omega(1-2\omega\sigma^{2})P_{X}\\{(\theta^{\star}-\theta)^{\top}X\\}^{2}}e^{H\omega^{2}(1-2\omega\sigma^{2})^{2}P_{X}\\{(\theta^{\star}-\theta)^{\top}X\\}^{4}}$
$\displaystyle\leq
e^{-\omega(1-2\omega\sigma^{2})\|\theta-\theta^{\star}\|_{2}^{2}\\{c-4B^{2}CH\omega(1-2\omega\sigma^{2})\\}}$
$\displaystyle\leq e^{-c_{2}\omega\|\theta^{\star}-\theta\|^{2}_{2}}$

where

$H=\\{\omega^{2}(1-2\sigma^{2})^{2}16B^{4}\\}^{-1}\bigl{\\{}e^{\omega(1-2\omega\sigma^{2})4B^{2}}-1-\omega(1-2\omega\sigma^{2})4B^{2}\bigr{\\}},$

and where the last line holds for some $c_{2}>0$ and for all sufficiently
small $\omega>0$. In particular, $\omega$ must satisfy
$c>4B^{2}CH\omega(1-2\omega\sigma^{2})$.

To verify (16), we need upper bounds on $m(\theta,\theta^{\star})$ and
$v(\theta,\theta^{\star})$. From above, we have
$m(\theta,\theta^{\star})=(\theta^{\star}-\theta)^{\top}(PXX^{T})(\theta^{\star}-\theta)$
and by Assumption 3a(2) it follows $m(\theta,\theta^{\star})\leq
C\|\theta-\theta^{\star}\|_{2}^{2}$ for some $C>0$. To bound
$v(\theta,\theta^{\star})$, use the total variance formula “$V(X)=E\\{V(X\mid
Y)\\}+V\\{E(X\mid Y)\\}$,” noting $V(Y\mid X)\leq\sigma^{2}$ by Assumption
3a(1). Then,

$\displaystyle v(\theta,\theta^{\star})$
$\displaystyle\leq\sigma^{2}(\theta^{\star}-\theta)^{\top}(PXX^{T})(\theta^{\star}-\theta)+V\\{(\theta^{\star}-\theta)^{\top}XX^{T}(\theta^{\star}-\theta)\\}$
$\displaystyle\leq
C\sigma^{2}\|\theta-\theta^{\star}\|_{2}^{2}+P\\{(\theta^{\star}-\theta)^{\top}XX^{T}(\theta^{\star}-\theta)\\}^{2}$
$\displaystyle\leq
C\sigma^{2}\|\theta-\theta^{\star}\|_{2}^{2}+4B^{2}P\\{(\theta^{\star}-\theta)^{\top}XX^{T}(\theta^{\star}-\theta)\\}$
$\displaystyle\leq(C\sigma^{2}+4CB^{2})\|\theta-\theta^{\star}\|_{2}^{2}.$

Then, by Cauchy–Schwartz,

$\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq\delta\\}\supset\\{\theta:\|\theta-\theta^{\star}\|\leq
C_{1}^{-1/2}\delta^{1/2}\\}$

where $C_{1}=\max\\{C,C\sigma^{2}+4CB^{2}\\}$. Assumption 3a(4) says the prior
density is bounded away from zero in a neighborhood of $\theta^{\star}$, so
that

$\Pi(\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq\delta\\})\geq\Pi(\\{\theta:\|\theta-\theta^{\star}\|\leq
C^{-1/2}\delta^{1/2}\\})\gtrsim\delta^{J/2},$

which verifies $\eqref{eq:prior.rootn}$.

###  C.4 Proof of Proposition 3b

The proof proceeds by checking the conditions of Theorem 6 A number of bounds
are derived below based on the tail behavior in Assumption 3b. In every case
the strictest bound is obtained when $s^{\star}=s$, and, therefore, we assume
$s^{\star}=s$ throughout.

We begin by finding upper and lower bounds for the surrogate risk
$P\ell_{\theta}^{n}$. Note we can write the expectation

$\displaystyle E[\\{Y-\theta^{\top}X\\}^{2}]$
$\displaystyle=E[\\{Y-X^{\top}\theta^{\star}+X^{\top}\theta^{\star}-\theta^{\top}X\\}^{2}]$
$\displaystyle=E\\{V(Y\mid X)\\}+E\\{(\theta-\theta^{\star})^{\top}X\\}^{2}$
$\displaystyle\leq E\\{V(Y\mid X)\\}+a_{1}\|\theta-\theta^{\star}\|_{2}^{2},$

where we used the fact that Assumption 3a(3) implies
$E\\{(\theta-\theta^{\star})^{\top}X\\}^{2}\leq
a_{1}\|\theta-\theta^{\star}\|_{2}^{2}$ for some $a_{1}>0$. Also, note
$E\\{V(Y\mid X)\\}$ is bounded by the marginal variance of $Y$, denoted
$\sigma^{2}$, which exists by Assumption 3b. Then, we upper bound the risk as

$\displaystyle P\ell_{\theta}^{n}$
$\displaystyle=E(Y-\theta^{\top}X)^{2}1(\theta^{\top}X-t_{n}^{1/2}\leq
Y\leq\theta^{\top}X+t_{n}^{1/2})$
$\displaystyle\qquad+t_{n}\\{P(Y\leq\theta^{\top}X-t_{n}^{1/2})+P(Y\geq\theta^{\top}X+t_{n}^{1/2})\\}$
$\displaystyle\leq
E(Y-\theta^{\top}X)^{2}+t_{n}\\{P(Y\leq\theta^{\top}X-t_{n}^{1/2})+P(Y\geq\theta^{\top}X+t_{n}^{1/2})\\}$
$\displaystyle\leq E\\{V(Y\mid
X)\\}+a_{1}\|\theta-\theta^{\star}\|_{2}^{2}+t_{n}\\{P(Y\leq
B-t_{n}^{1/2})+P(Y\geq-B+t_{n}^{1/2})\\}$ $\displaystyle\leq E\\{V(Y\mid
X)\\}+a_{1}\|\theta-\theta^{\star}\|_{2}^{2}+2(s-1)^{-1}t_{n}(t_{n}^{1/2}-B)^{1-s}$
$\displaystyle\leq E\\{V(Y\mid
X)\\}+a_{1}\|\theta-\theta^{\star}\|_{2}^{2}+\tfrac{2}{s-1}t_{n}^{-(s-3)/2}.$

Similarly,

$\displaystyle P\ell_{\theta}^{n}$ $\displaystyle\geq
E(Y-\theta^{\top}X)^{2}1(\theta^{\top}X-t_{n}^{1/2}\leq
Y\leq\theta^{\top}X+t_{n}^{1/2})$
$\displaystyle=E(Y-\theta^{\top}X)^{2}-E(Y-\theta^{\top}X)^{2}1(Y<\theta^{\top}X-t_{n}^{1/2}\text{
or }Y>\theta^{\top}X+t_{n}^{1/2})$ $\displaystyle\geq E\\{V(Y\mid
X)\\}+a_{0}\|\theta-\theta^{\star}\|_{2}^{2}$
$\displaystyle\qquad-\int_{-\infty}^{B-t_{n}^{1/2}}(y-\theta^{\top}x)^{2}\,f(y)\,dy\,P(dx)-\int_{t_{n}^{1/2}-B}^{\infty}(y-\theta^{\top}x)^{2}\,f(y)\,dy\,P(dx)$
$\displaystyle\geq E\\{V(Y\mid
X)\\}+a_{0}\|\theta-\theta^{\star}\|_{2}^{2}-\tfrac{2^{s-2}}{s-3}t_{n}^{-(s-3)/2},$

where the third line follows from bounding
$E\\{(\theta-\theta^{\star})^{\top}X\\}^{2}\geq
a_{0}\|\theta-\theta^{\star}\|_{2}^{2}$ for some $a_{0}>0$ using Assumption
3a(3). The fourth line follows by bounding $|\theta^{\top}x|\leq B$ and by
noting $B-t_{n}^{1/2}<-\tfrac{1}{2}t_{n}^{1/2}$ for all sufficiently large
$n$.

These bounds show that, for $s>3$, the surrogate risk converges to the risk:
$P\ell_{\theta}^{n}\rightarrow P\ell_{\theta}$. And, further, the surrogate
risk difference
$m_{n}(\theta,\theta^{\star}):=P\ell_{\theta}^{n}-P\ell_{\theta^{\star}}^{n}$
satisfies

$m_{n}(\theta,\theta^{\star})\geq
a_{0}\|\theta-\theta^{\star}\|_{2}^{2}-(\tfrac{2^{s-2}}{s-3}+\tfrac{2}{s-1})t_{n}^{-(s-3)/2}.$

Next, we upper bound the surrogate variance term
$v_{n}(\theta,\theta^{\star}):=P[\\{\ell_{\theta}^{n}-\ell_{\theta^{\star}}^{n}\\}^{2}-m_{n}(\theta,\theta^{\star})^{2}]$.
By construction the second moment of the surrogate loss difference satisfies
$P[\\{\ell_{\theta}^{n}-\ell_{\theta^{\star}}^{n}\\}^{2}]\leq
P[\\{\ell_{\theta}-\ell_{\theta^{\star}}\\}^{2}]$, which implies

$v_{n}(\theta,\theta^{\star})\leq
v(\theta,\theta^{\star})+m(\theta,\theta^{\star})^{2}-m_{n}(\theta,\theta^{\star})^{2}.$

As in the proof of Proposition 3a, the tail behavior of $Y$ given $x$ implies
$Y$ has a finite variance, $\sigma^{2}$, for all $x$ and, as a result
$v(\theta,\theta^{\star})\leq(C\sigma^{2}+4CB^{2})\|\theta-\theta^{\star}\|_{2}^{2}$.

Further, since $m_{n}(\theta,\theta^{\star})\geq
m(\theta,\theta^{\star})-(\tfrac{2^{s-2}}{s-3}+\tfrac{2}{s-1})t_{n}^{-(s-3)/2}$
from the above risk bounds, it follows that

$\displaystyle v_{n}(\theta,\theta^{\star})$
$\displaystyle\leq(C\sigma^{2}+4CB^{2}+2(\tfrac{2^{s-2}}{s-3}+\tfrac{2}{s-1})t_{n}^{-(s-3)/2})\|\theta-\theta^{\star}\|_{2}^{2}$
$\displaystyle\leq C_{2}\|\theta-\theta^{\star}\|_{2}^{2}$

for some constant $C_{2}$, which can be taken smaller than
$C\sigma^{2}+4CB^{2}+1$ for all large $n$.

Next, we apply the inequality in (19), along with the above lower and upper
bounds on $m_{n}(\theta,\theta^{\star})$ and $v_{n}(\theta,\theta^{\star})$,
noting that by construction

$|\ell_{\theta}^{n}(U)-\ell_{\theta^{\star}}^{n}(U)|<(2B+1)t_{n}^{1/2},\quad\text{for
all large $n$}.$

That is, for $\theta$ such that
$\|\theta-\theta^{\star}\|_{2}>M_{n}\varepsilon_{n}$, (19) provides the bound

$\displaystyle Pe^{-\omega_{n}(\ell_{\theta}^{n}-\ell_{\theta^{\star}}^{n})}$
$\displaystyle\leq\exp\Bigl{[}-\omega_{n}m_{n}(\theta,\theta^{\star})+\omega_{n}^{2}v_{n}(\theta,\theta^{\star})\bigl{\\{}\tfrac{e^{\omega_{n}(2B+1)t_{n}^{1/2}}-1-\omega_{n}(2B+1)t_{n}^{1/2}}{\omega_{n}^{2}t_{n}(2B+1)^{2}}\bigr{\\}}\Bigr{]}$
$\displaystyle\leq\exp\\{-\omega_{n}(M_{n}^{2}-C_{1}^{2})\varepsilon_{n}^{2}+\omega_{n}^{2}C_{3}M_{n}^{2}\varepsilon_{n}^{2}\\}$
$\displaystyle\leq\exp(-n^{-1}M_{n}^{2}\log n/2\\},$

which holds for all large $n$, where
$C_{1}=(\tfrac{2^{s-2}}{s-3}+\tfrac{2}{s-1})^{2}$ and

$C_{2}\bigl{\\{}\tfrac{e^{\omega_{n}(2B+1)t_{n}^{1/2}}-1-\omega_{n}(2B+1)t_{n}^{1/2}}{\omega_{n}^{2}t_{n}(2B+1)^{2}}\bigr{\\}}\leq
C_{3}\leq C_{2}e^{2B+1}.$

The upper bound above follows from the facts that $\omega_{n}\rightarrow 0$,
that the bracketed term multiplying $C_{2}$ is a constant by the choices of
$t_{n}$ and $\omega_{n}$, and that, for the choice of $\varepsilon_{n}$, we
have $n\omega_{n}\varepsilon_{n}^{2}=\log n$. This verifies Condition 1.

By the above arguments,
$v_{n}(\theta,\theta^{\star})\lesssim\|\theta-\theta^{\star}\|_{2}^{2}$ and
$m_{n}(\theta,\theta^{\star})\leq
C_{4}\|\theta-\theta^{\star}\|_{2}^{2}+C_{5}t_{n}^{-(s-3)/2}$. By definition,
$\varepsilon_{n}^{2}=t_{n}^{-(s-3)/2}$, so that

$\Pi(\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq\varepsilon_{n}^{2}\\})\geq\Pi(\\{\theta:\|\theta-\theta^{\star}\|_{2}^{2}\leq
C_{6}\varepsilon_{n}^{2}\\})$

for some $C_{6}>0$. By the Cauchy–Schwartz inequality, and the fact that the
prior density is bounded away from zero in a neighborhood of $\theta^{\star}$,

$\displaystyle\Pi(\\{\theta:\|\theta-\theta^{\star}\|_{2}^{2}\leq
C_{6}\varepsilon_{n}^{2}\\})$
$\displaystyle\geq\Pi(\\{\theta:\|\theta-\theta^{\star}\|^{2}\leq
C_{6}\varepsilon_{n}^{2}\\})$ $\displaystyle\gtrsim\varepsilon_{n}^{J}$
$\displaystyle>e^{-C_{7}\log n}=e^{-C_{7}n\omega_{n}\varepsilon_{n}^{2}},$

for a constant $C_{7}>0$ depending on $s$ and $J$. Therefore, (28) holds.

###  C.5 Proof of Proposition 4

Proposition 4 follows from a slight refinement of Theorem 3. We verify
Condition 1 and a prior bound essentially equivalent to (17). We also use an
argument similar to the proof of Theorem 2 to improve the bound on expectation
of the numerator of the Gibbs posterior distribution derived in the proof of
Theorem 3.

Towards verifying Condition 1, we first need to define the loss function being
used. Even though the $x_{i}$ values are technically not “data” in this inid
setting, it is convenient to express the loss function in terms of the $(x,y)$
pairs. Moreover, while the quantity of interest is the mean function $\theta$,
since we have introduced the parametric representation $\theta=\theta_{\beta}$
and the focus shifts to the basis coefficients in the $\beta$ vector, it makes
sense to express the loss function in terms of $\beta$ instead of $\theta$.
That is, the squared error loss is

$\ell_{\beta}(x,y)=\\{y-\theta_{\beta}(x)\\}^{2}.$

For $\beta^{\dagger}=\beta_{n}^{\dagger}$ as defined in Section 5.4, the loss
difference equals

$\ell_{\beta}(x,y)-\ell_{\beta^{\dagger}}(x,y)=\\{\theta_{\beta}(x)-\theta_{\beta^{\dagger}}(x)\\}^{2}+2\\{\theta_{\beta^{\dagger}}(x)-\theta_{\beta}(x)\\}\\{y-\theta_{\beta^{\dagger}}(x)\\}.$
(58)

Since the responses are independent, the expectation in Condition 1 can be
expressed as the product

$\displaystyle P^{n}e^{-n\omega\\{r_{n}(\beta)-r_{n}(\beta^{\dagger})\\}}$
$\displaystyle=\prod_{i=1}^{n}e^{-\omega\\{\theta_{\beta}(x_{i})-\theta_{\beta^{\dagger}}(x_{i})\\}^{2}}P_{i}e^{-2\omega\\{\theta_{\beta^{\dagger}}(x_{i})-\theta_{\beta}(x_{i})\\}\\{Y_{i}-\theta_{\beta^{\dagger}}(x_{i})\\}}$
$\displaystyle=e^{-n\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2}}\prod_{i=1}^{n}P_{i}e^{-2\omega\\{\theta_{\beta^{\dagger}}(x_{i})-\theta_{\beta}(x_{i})\\}\\{Y_{i}-\theta_{\beta^{\dagger}}(x_{i})\\}}.$

According to Assumption 4(2), $Y_{i}$ is sub-Gaussian, so the product in the
last line above can be upper-bounded by

$e^{4n\omega^{2}\sigma^{2}\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2}}\times
e^{-2\omega_{n}\sum_{i=1}^{n}\\{\theta_{\beta^{\dagger}}(x_{i})-\theta_{\beta}(x_{i})\\}\\{\theta^{\star}(x_{i})-\theta_{\beta^{\dagger}}(x_{i})\\}}.$

The second exponential term above is identically $1$ because the exponent
vanishes—a consequence of the Pythagorean theorem. To see this, first write
the quantity in the exponent as an inner product

$(\beta-\beta^{\dagger})^{\top}F_{n}^{\top}\\{\theta^{\star}(x_{1:n})-F_{n}\beta^{\dagger}\\}=(\beta-\beta^{\dagger})^{\top}\\{F_{n}^{\top}\theta^{\star}(x_{1:n})-F_{n}^{\top}F_{n}\beta^{\dagger}\\}.$

Recall from the discussion in Section 5.4 that $\beta^{\dagger}$ satisfies
$(F_{n}^{\top}F_{n})\beta^{\dagger}=F_{n}^{\top}\theta^{\star}(x_{1:n})$; from
this, it follows that the above display vanishes for all vectors $\beta$.
Therefore,

$P^{n}e^{-n\omega\\{r_{n}(\beta)-r_{n}(\beta^{\dagger})\\}}\leq
e^{-n\omega\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2}(1-2\omega\sigma^{2})},$

and Condition 1 is satisfied since provided the learning rate $\omega$ is less
than $(2\sigma^{2})^{-1}$.

Next, we derive a prior bound similar to (17). By Assumption 4(3), all
eigenvalues of $F_{n}^{\top}F_{n}$ are bounded away from zero and infinity,
which implies

$\|\beta-\beta^{\dagger}\|_{2}^{2}\lesssim\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2}\lesssim\|\beta-\beta^{\dagger}\|_{2}^{2}.$
(59)

In the arguments that follow, we show that
$\|\theta_{\beta^{\star}}-\theta_{\beta^{\dagger}}\|_{n,2}\lesssim\varepsilon_{n}$
which implies, by (59), that
$\|\beta^{\star}_{n}-\beta^{\dagger}\|_{2}^{2}\lesssim\varepsilon_{n}^{2}$.
The approximation property in (44) implies that
$\|\beta_{n}^{\star}\|_{\infty}<H$. Therefore, $\|\beta^{\dagger}\|_{\infty}$
is bounded because, if it were not bounded, then (59) would be contradicted.

Since $\|\beta^{\dagger}\|_{\infty}$ is bounded, Assumption 4(5) implies that
the prior for $\beta$ satisfies

$\widetilde{\Pi}(\\{\beta:\|\beta-\beta^{\dagger}\|_{2}\leq\varepsilon_{n}\\})\gtrsim\varepsilon_{n}^{J_{n}}e^{-J_{n}\log
C}.$ (60)

Recall that (17) involves the mean and variance of the empirical risk, and we
can directly calculate these. For the mean,

$\displaystyle m(\theta_{\beta},\theta_{\beta^{\dagger}})$
$\displaystyle=\bar{r}_{n}(\beta)-\bar{r}_{n}(\beta^{\dagger})$
$\displaystyle=\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2}+\sum_{i=1}^{n}\\{\theta_{\beta^{\dagger}}(x_{i})-\theta^{\star}(x_{i})\\}\\{\theta_{\beta^{\dagger}}(x_{i})-\theta_{\beta}(x_{i})\\}$
$\displaystyle=\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2},$

where the last equality is by the same Pythagorean theorem argument presented
above. Similarly, the variance is given by
$v(\theta_{\beta},\theta_{\beta^{\dagger}})=4\sigma^{2}n^{-1}\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2}$.
Therefore,

$\\{m(\theta_{\beta},\theta_{\beta^{\dagger}})\vee
v(\theta_{\beta},\theta_{\beta^{\dagger}})\\}\lesssim\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}^{2},$

and (60) and (59) imply

$\displaystyle\tilde{\Pi}(\\{\beta:m(\theta_{\beta},\theta_{\beta^{\dagger}})\vee
v(\theta_{\beta},\theta_{\beta^{\dagger}})\leq\varepsilon_{n}^{2}\\})$
$\displaystyle\gtrsim\varepsilon_{n}^{J_{n}}e^{-CJ_{n}}.$

The fact that $n\varepsilon_{n}^{2}=J_{n}$ along with Lemma 1 implies

$D_{n}\gtrsim\varepsilon_{n}^{J_{n}}e^{-(2\omega+\log C)J_{n}}$

with $P^{n}$-probability converging to $1$ as $n\rightarrow\infty$.

We briefly verify the claim made just before the statement of Proposition 4,
i.e., that $\eqref{eq:prior.sqr}$ holds for a independence prior consisting of
strictly positive densities. To see this, note that the volume of a
$J_{n}$-dimensional sphere with radius $\varepsilon$ is a constant multiple of
$\varepsilon^{J_{n}}$, so that, if the joint prior density is bounded away
from zero by $C^{J_{n}}$ on the sphere, then we have
$\widetilde{\Pi}(\\{\beta:\|\beta-\beta^{\prime}\|_{2}\leq\varepsilon\\})\gtrsim(C\varepsilon)^{J_{n}}$,
which is (45). So we must verify the bound on the prior density. Suppose
$\tilde{\Pi}$ has a density $\tilde{\pi}$ equal to the a product of
independent prior densities $\tilde{\pi}_{j}$, $j=1,\ldots,J_{n}$. Since the
cube $\\{\beta:\|\beta-\beta^{\prime}\|_{\infty}\leq
J_{n}^{1/2}\varepsilon\\}$ contains the ball
$\\{\beta:\|\beta-\beta^{\prime}\|_{2}\leq\varepsilon\\}$ by Cauchy–Schwartz,
the infimum of the prior density on the ball is no smaller than the infimum of
the prior density on the cube. To bound the prior density on the cube consider
any of the $J$ components and note $|\beta_{j}-\beta^{\prime}_{j}|\leq
J_{n}^{1/2}\varepsilon_{n}$ implies
$\beta_{j}\in[-H-J_{n}^{1/2}\varepsilon_{n},H+J_{n}^{1/2}\varepsilon_{n}]$
since $\|\beta^{\prime}\|_{\infty}\leq H$. Moreover, since $\alpha\geq 1/2$ we
have $J_{n}^{1/2}\varepsilon_{n}\rightarrow 0$ so that this interval lies
within a compact set, say, $[-H-1,H+1]$. And, since the prior density
$\tilde{\pi}_{j}$ is strictly positive, it is bounded away from zero by a
constant $C$ on this compact set. Finally, by independence, we have
$\pi(\beta)\geq C^{J}$ for all
$\beta\in\\{\beta:\|\beta-\beta^{\prime}\|_{2}\leq\varepsilon\\}$, which
verifies the claim concerning (45).

In order to obtain the optimal rate of
$\varepsilon_{n}=n^{-\alpha/(1+2\alpha)}$, without an extra logarithmic term,
we need a slightly better bound on $P^{n}N_{n}(A_{n})$ than that used to prove
Theorem 3. Our strategy, as in the proof of Theorem 2, will be to split the
range of integration in the numerator into countably many disjoint pieces, and
use bounds on the prior probability on those pieces to improve the numerator
bound. Define
$\tilde{A}_{n}:=\\{\beta:\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}>M_{n}\varepsilon_{n}\\}$
and write the numerator $N_{n}(\tilde{A}_{n})$ as follows

$\displaystyle N_{n}(\tilde{A}_{n})$
$\displaystyle=\int_{\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}>M_{n}\varepsilon_{n}}e^{-n\omega\\{r_{n}(\beta)-r_{n}(\beta^{\dagger})\\}}\,\tilde{\Pi}(d\beta)$
$\displaystyle=\sum_{t=1}^{\infty}\int_{tM_{n}\varepsilon_{n}<\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}<(t+1)M_{n}\varepsilon_{n}}e^{-n\omega\\{r_{n}(\beta)-r_{n}(\beta^{\dagger})\\}}\,\tilde{\Pi}(d\beta).$

Taking expectation of the left-hand side and moving it under the sum and under
the integral on the right-hand side, we need to bound

$\int_{tM_{n}\varepsilon_{n}<\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}<(t+1)M_{n}\varepsilon_{n}}P^{n}e^{-n\omega\\{r_{n}(\beta)-r_{n}(\beta^{\dagger})\\}}\,\tilde{\Pi}(d\beta),\quad
t=1,2,\ldots.$

By Condition 1, verified above, on the given range of integration the
integrand is bounded above by $e^{-n\omega(tM_{n}\varepsilon_{n})^{2}/2}$, so
the expectation of the integral itself is bounded by

$e^{-n\omega_{n}(tM_{n}\varepsilon_{n})^{2}/2}\Pi(\\{\beta:\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}<(t+1)M_{n}\varepsilon_{n}\\}),\quad
t=1,2,\ldots$

Since $\tilde{\Pi}$ has a bounded density on the $J_{n}-$dimensional parameter
space, we clearly have

$\Pi(\\{\beta:\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}<(t+1)M_{n}\varepsilon_{n}\\})\lesssim\\{(t+1)M_{n}\varepsilon_{n}\\}^{J_{n}}.$

Plug all this back into the summation above to get

$P^{n}N_{n}(\tilde{A}_{n})\lesssim(M_{n}\varepsilon_{n})^{J_{n}}\sum_{t=1}^{\infty}(t+1)^{J_{n}}e^{-\omega(tM_{n})^{2}J_{n}/2}.$

The above sum is finite for all $n$ and bounded by a multiple of $e^{-\omega
M_{n}^{2}J_{n}/4}$. Consequently, we find that the expectation of the Gibbs
posterior numerator is bounded by a constant multiple of
$(M_{n}\varepsilon_{n})^{J_{n}}e^{-\omega M_{n}^{2}J_{n}/4}$.

Combining the in-expectation and in-probability bounds on
$N_{n}(\tilde{A}_{n})$ and $D_{n}$, respectively, as in the proof of Theorem
1, we find that

$P^{n}\Pi_{n}(\tilde{A}_{n})\lesssim e^{-J_{n}(\omega M_{n}^{2}/4-\log
M_{n}-2\omega-\log C)}$

which vanishes as $n\rightarrow\infty$ for any sufficiently large constant
$M_{n}\equiv M>0$.

The above arguments establish that the Gibbs posterior $\widetilde{\Pi}_{n}$
for $\beta$ satisfies

$P^{n}\widetilde{\Pi}_{n}(\\{\beta\in\mathbb{R}^{J}:\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}>M_{n}\varepsilon_{n}\\})\to
0.$ (61)

But this is equivalent to the proposition’s claim, with
$\theta_{\beta^{\dagger}}$ replaced by $\theta^{\star}$. To see this, first
recall that Assumption 4.4 implies the existence of a $J$-vector
$\beta^{\star}=\beta_{n}^{\star}$ such that
$\|\theta_{\beta^{\star}}-\theta^{\star}\|_{\infty}$ is small. Next, use the
triangle inequality to get

$\|\theta_{\beta}-\theta^{\star}\|_{n,2}\leq\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}+\|\theta_{\beta^{\dagger}}-\theta^{\star}\|_{n,2}.$

Now apply the Pythagorean theorem argument as above to show that

$\|\theta_{\beta^{\star}}-\theta^{\star}\|_{n,2}^{2}=\|\theta_{\beta^{\star}}-\theta_{\beta^{\dagger}}\|_{n,2}^{2}+\|\theta_{\beta^{\dagger}}-\theta^{\star}\|_{n,2}^{2}.$

Since the sup-norm dominates the empirical $L_{2}$ norm, the left-hand side is
bounded by $CJ^{-2\alpha}$ for some $C>0$. But both terms on the right-hand
side are non-negative, so it must be that the right-most term is also bounded
by $CJ^{-2\alpha}$. Putting these together, we find that

$\|\theta_{\beta}-\theta^{\star}\|_{n,2}>M_{n}^{\prime}\varepsilon_{n}\implies\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}>M_{n}^{\prime}\varepsilon_{n}-C^{1/2}J^{-\alpha}.$

Therefore, with $\varepsilon_{n}=n^{-\alpha/(2\alpha+1)}\log n$ and
$J=J_{n}=n^{1/(2\alpha+1)}$, the lower bound on the right-hand side of the
previous display is a constant multiple of $\varepsilon_{n}$. We can choose
$M_{n}^{\prime}$ such that the aforementioned sequence is at least as big as
$M_{n}$ above. In the end,

$\widetilde{\Pi}_{n}(\\{\beta:\|\theta_{\beta}-\theta^{\star}\|_{n,2}>M_{n}^{\prime}\varepsilon_{n}\\})\leq\widetilde{\Pi}_{n}(\\{\beta:\|\theta_{\beta}-\theta_{\beta^{\dagger}}\|_{n,2}>M_{n}\varepsilon_{n}\\}),$

so the Gibbs posterior concentration claim in the proposition follows from
that established above. Finally, by definition of the prior and Gibbs
posterior for $\theta$, we have that

$P^{n}\Pi_{n}(\\{\theta\in\Theta:\|\theta-\theta^{\star}\|_{n,2}>M_{n}^{\prime}\varepsilon\\})\to
0,$

which completes the proof.

###  C.6 Proof of Proposition 5a

The proof proceeds by checking the conditions of Theorem 1. We begin by
verifying (15). Evaluate $m(\theta,\theta^{\star})$ and
$v(\theta,\theta^{\star})$ for the loss function $\ell_{\theta}$ as defined
above:

$\displaystyle m(\theta;\theta^{\star})$
$\displaystyle=P\\{Y\neq\phi_{\theta}(X)\\}-P\\{Y\neq\phi_{\theta^{\star}}(X)\\}$
$\displaystyle=\int_{x^{\top}\theta<0,x^{\top}\theta^{\star}>0}(2\eta-1)\,dP+\int_{x^{\top}\theta>0,x^{\top}\theta^{\star}<0}(1-2\eta)\,dP$
$\displaystyle v(\theta,\theta^{\star})$ $\displaystyle\leq
P(\ell_{\theta}-\ell_{\theta^{\star}})^{2}$
$\displaystyle=P(X^{\top}\theta<0,X^{\top}\theta^{\star}>0)+P(X^{\top}\theta>0,X^{\top}\theta^{\star}<0)$
$\displaystyle=P(\phi_{\theta}-\phi_{\theta^{\star}})^{2}.$

It follows from arguments in Tsybakov, (2004) that, under the margin condition
in Assumption 5a.5, with $h\in(0,1)$, we have

$hP(\phi_{\theta}-\phi_{\theta^{\star}})^{2}\leq m(\theta,\theta^{\star}).$

Further, rewrite $m(\theta,\theta^{\star})$ as

$\displaystyle m(\theta;\theta^{\star})$
$\displaystyle=\int\eta(x)\\{\phi_{\theta^{\star}}(x)-\phi_{\theta}(x)\\}\,P(dx)+\int[1-\eta(x)]\\{\phi_{\theta}(x)-\phi_{\theta^{\star}}(x)\\}\,P(dx)$
$\displaystyle\leq 2\int|\phi_{\theta}(x)-\phi_{\theta^{\star}}(x)|\,P(dx),$
(62)

where the latter inequality follows since $\eta<1$. Since
$\phi_{\theta}-\phi_{\theta^{\star}}$ is a difference of indicators

$P(\phi_{\theta}-\phi_{\theta^{\star}})^{2}=P|\phi_{\theta}-\phi_{\theta^{\star}}|\quad\text{and}\quad
m(\theta,\theta^{\star})\lesssim P(\phi_{\theta}-\phi_{\theta^{\star}})^{2}.$

This latter inequality will be useful below. Under the stated assumptions, the
integrand in (C.6) can be handled exactly like in Lemma 4 of Jiang and Tanner,
(2008). That is, if $\|\beta-\beta^{\star}\|_{1}$ is sufficiently small, then
$m(\theta;\theta^{\star})\lesssim\|\beta-\beta^{\star}\|_{1}$. Since
$v(\theta;\theta^{\star})\lesssim m(\theta;\theta^{\star})$, it follows that

$\\{\theta:m(\theta;\theta^{\star})\vee
v(\theta;\theta^{\star})\leq\varepsilon^{2}\\}\supseteq\\{\theta=(\alpha,\beta):\|\beta-\beta^{\star}\|_{1}\leq
c\varepsilon^{2}\\},$

for a constant $c>0$. To lower-bound the prior probability of the event on the
right-hand side, we follow the proof of Lemma 2 in Castillo et al., (2015).
First, for $S^{\star}$ the configuration of $\beta^{\star}$, we can
immediately get

$\Pi(\\{\beta:\|\beta-\beta^{\star}\|_{1}\leq
c\varepsilon^{2}\\})\geq\pi(S^{\star})\int_{\|\beta_{S^{\star}}-\beta_{S^{\star}}^{\star}\|_{1}\leq
c\varepsilon^{2}}g_{S^{\star}}(\beta_{S^{\star}})\,d\beta_{S^{\star}}.$

Now make a change of variable $b=\beta_{S^{\star}}-\beta_{S^{\star}}^{\star}$
and note that

$g_{S^{\star}}(\beta_{S^{\star}})=g_{S^{\star}}(b+\beta_{S^{\star}}^{\star})\geq
e^{-\lambda\|\beta^{\star}\|_{1}}g_{S^{\star}}(b).$

Therefore,

$\Pi(\\{\beta:\|\beta-\beta^{\star}\|_{1}\leq
c\varepsilon^{2}\\})\geq\pi(S^{\star})e^{-\lambda\|\beta^{\star}\|_{1}}\int_{\|b\|_{1}\leq
c\varepsilon^{2}}g_{S^{\star}}(b)\,db,$

and after plugging in the definition of $\pi(S^{\star})$, using the bound in
Equation (6.2) of Castillo et al., (2015), and simplifying, we get

$\Pi(\\{\beta:\|\beta-\beta^{\star}\|_{1}\leq c\varepsilon^{2}\\})\gtrsim
f(|S^{\star}|)\,q^{-2|S^{\star}|}e^{-\lambda\|\beta^{\star}\|_{1}}.$

From the form of the complexity prior $f$, the bounds on $\lambda$, and the
assumption that $\|\beta^{\star}\|_{\infty}=O(1)$, we see that the lower bound
is no smaller than $e^{-C|S^{\star}|\log q}$ for some constant $C>0$, which
implies (15), i.e.,

$\Pi(\\{\theta:m(\theta;\theta^{\star})\vee
v(\theta;\theta^{\star})\leq\varepsilon_{n}^{2}\\})\gtrsim
e^{-Cn\varepsilon_{n}^{2}},$

where $\varepsilon_{n}=\\{n^{-1}|S^{\star}|\log q\\}^{1/2}$.

Next, we verify Condition 1. By direct computation, we get

$\displaystyle Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}$
$\displaystyle=1-P(\phi_{\theta}-\phi_{\theta^{\star}})^{2}+e^{-\omega}\int\eta(x)1\\{x^{\top}\theta\leq
0,x^{\top}\theta^{\star}>0\\}\,P(dx)$
$\displaystyle\qquad+e^{-\omega}\int(1-\eta(x))1\\{x^{\top}\theta>0,x^{\top}\theta^{\star}\leq
0\\}\,P(dx)$
$\displaystyle\qquad+e^{\omega}\int(1-\eta(x))1\\{x^{\top}\theta\leq
0,x^{\top}\theta^{\star}>0\\}\,P(dx)$
$\displaystyle\qquad+e^{\omega}\int\eta(x)1\\{x^{\top}\theta>0,x^{\top}\theta^{\star}\leq
0\\}\,P(dx).$

Using the Massart margin condition, we can upper bound the above by

$\displaystyle Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}$
$\displaystyle\leq 1-\min\\{a,b\\}P(\phi_{\theta}-\phi_{\theta^{\star}})^{2}$

where $a=1-e^{-\omega}-(\tfrac{1}{2}-\tfrac{h}{2})(e^{\omega-e^{-\omega}})$
and $b=1-e^{\omega}+(\tfrac{1}{2}+\tfrac{h}{2})(e^{\omega-e^{-\omega}})$. For
all small enough $\omega$, both $a$ and $b$ are $O(h\omega)$, so for some
constants $c,c^{\prime}>0$,

$\displaystyle Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}$
$\displaystyle\leq 1-ch\omega P(\phi_{\theta}-\phi_{\theta^{\star}})^{2}$
$\displaystyle\leq 1-c^{\prime}\omega m(\theta,\theta^{\star}).$

Then Condition 1 follows from the elementary inequality $1-t\leq e^{-t}$ for
$t>0$.

###  C.7 Proof of Proposition 5b

The proof proceeds by checking the conditions of Theorem 3. We begin by
verifying (17). The upper bounds on $m(\theta,\theta^{\star})$ and
$v(\theta,\theta^{\star})$ given in the proof of Proposition 5a are also valid
in this setting, which means

$\Pi(\\{\theta:m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\leq\varepsilon^{2}\\})\geq\Pi(\\{\theta:\|\beta-\beta^{\star}\|_{1}\leq
C_{1}\varepsilon^{2}\\})$

for some $C_{1}>0$. Further, Assumption 5b implies

$\Pi(\\{\theta:\|\beta-\beta^{\star}\|_{1}\leq
C_{1}\varepsilon^{2}\\})\gtrsim\varepsilon^{2q}=e^{-2q\log\varepsilon}.$

By definition of $\varepsilon_{n}$ and $\omega_{n}$ we have that

$\exp(-2q\log\varepsilon_{n})\geq\exp\\{-n\omega_{n}\varepsilon_{n}^{(2+2\gamma)/\gamma}\\},$

which, combined with the previous display, verifies (17).

Next, to verify Condition 1 we note the misclassification error loss function
difference $\ell_{\theta}(u)-\ell_{\theta^{\star}}(u)$ is bounded in absolute
value by $1$, so we can proceed with using the moment-generating function
bound from Lemma 7.26 in Lafftery et al., (2010); see (19) above. Proposition
1 in Tsybakov, (2004) provides the lower bound on $m(\theta,\theta^{\star})$
we need, i.e., Tsybakov proves that

$\text{our Assumption~{}\ref{asmp:tsybakov}(2)}\implies
m(\theta,\theta^{\star})\gtrsim
d(\theta,\theta^{\star})^{(2+2\gamma)/\gamma}.$

With this and the upper bound on $v(\theta,\theta^{\star})$ derived above,
(19) implies

$Pe^{-\omega_{n}(\ell_{\theta}-\ell_{\theta^{\star}})}\leq
e^{-C_{2}\omega_{n}\varepsilon_{n}^{(2+2\gamma)/\gamma}}$

for some $C_{2}>0$, which verifies Condition 1.

###  C.8 Proof of Proposition 6

The proof proceeds by checking the conditions of Theorem 5. First, we verify
(17). Starting with $m(\theta,\theta^{\star})$, by direct calculation,

$\displaystyle
m(\theta,\theta^{\star})=\frac{1}{2}\int_{\mathbb{X}}\Bigl{\\{}$
$\displaystyle\int\bigl{(}|\theta(x)\vee\theta^{\star}(x)-y|-|\theta(x)\wedge\theta^{\star}(x)-y|\bigr{)}\,P_{x}(dy)$
$\displaystyle+(1-2\tau)|\theta(x)-\theta^{\star}(x)|\Bigr{\\}}\,P(dx).$

Partitioning the range of integration with respect to $y$, for given $x$, into
the disjoint intervals $(-\infty,\theta\wedge\theta^{\star}]$,
$(\theta\wedge\theta^{\star},\theta\vee\theta^{\star})$, and
$[\theta\vee\theta^{\star},\infty)$, and simplifying, we get

$m(\theta,\theta^{\star})=\frac{1}{2}\int_{\mathbb{X}}\int_{\theta(x)\wedge\theta^{\star}(x)}^{\theta(x)\vee\theta^{\star}(x)}\\{\theta(x)\vee\theta^{\star}(x)-y\\}\,P_{x}(dy)\,P(dx).$
(63)

It follows immediately that
$m(\theta,\theta^{\star}_{n})\lesssim\|\theta-\theta^{\star}\|_{L_{1}(P)}$.
Also, since $\theta\mapsto\ell_{\theta}(x,y)$ clearly satisfies the fixed-$x$
Lipschitz bound

$|\ell_{\theta}(x,y)-\ell_{\theta^{\star}}(x,y)|\leq|\theta(x)-\theta^{\star}(x)|,\quad\text{for
all $(x,y)$},$ (64)

we get a similar bound for the variance, i.e.,
$v(\theta,\theta^{\star}_{n})\leq\|\theta-\theta^{\star}\|^{2}_{L_{2}(P)}$.

Let $J_{n}=n^{1/(1+2\alpha)}$ and $\hat{\theta}_{J,\beta}:=\beta^{\top}f$, and
define a sup-norm ball around $\theta^{\star}$

$B_{n}^{\star}=\\{(\beta,J):\beta\in\mathbb{R}^{J},J=J_{n},\|\theta^{\star}-\hat{\theta}_{J,\beta}\|_{\infty}\leq
CJ_{n}^{-\alpha}\\}.$

By the above upper bounds on $m(\theta,\theta^{\star})$ and
$v(\theta,\theta^{\star})$ in terms of
$\|\theta-\theta^{\star}\|_{L_{2}(P)}^{2}$, we have

$\|\theta^{\star}-\hat{\theta}_{J,\beta}\|_{\infty}\leq
CJ_{n}^{-\alpha}\implies\\{m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\\}\lesssim J_{n}^{-2\alpha}.$

Then, by Assumptions A6.3-4, and using the same argument as in the proof of
Theorem 1 in Shen and Ghosal, (2015) we have

$\displaystyle\Pi^{(n)}(\\{m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\\}\lesssim J_{n}^{-2\alpha})$
$\displaystyle=\Pi(\\{m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\\}\lesssim J_{n}^{-2\alpha})/\Pi(\Theta_{n})$
$\displaystyle\geq\Pi(\\{m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\\}\lesssim J_{n}^{-2\alpha})$
$\displaystyle\geq\Pi(B_{n}^{\star})\gtrsim e^{-C_{1}J_{n}\log n},$

for some $C_{1}>0$. By the definitions of $\varepsilon_{n}$ and $\omega_{n}$
in Proposition 6 it follows that
$J_{n}^{-2\alpha}\leq\Delta_{n}^{-2}\varepsilon_{n}^{2}$ for $\Delta_{n}$ as
defined in Condition 2. Define $K_{n}\propto\Delta_{n}^{-1}$, with precise
proportionality determined below. Then,

$C_{1}J_{n}(\log n)\leq CnK_{n}^{2}\omega_{n}\varepsilon_{n}^{2},$

for a sufficiently small $C>0$ and all large enough $n$, which verifies the
prior condition in (25) with $r=2$.

Next we verify Condition 2. Define the sets
$A_{n}:=\\{\theta:\|\theta-\theta^{\star}\|_{L_{2}(P)}>M\varepsilon_{n}\\}$
and $\Theta_{n}:=\\{\theta:\|\theta\|_{\infty}\leq\Delta_{n}\\}$. Note that
Assumption 6.4 implies that $\Pi_{n}(A_{n}\cap\Theta_{n}^{\text{\sc c}})=0$,
and, therefore,

$\Pi_{n}(A_{n})=\Pi_{n}(A_{n}\cap\Theta_{n}).$

The following computations provide a lower bound on $m(\theta,\theta^{\star})$
for $\theta\in\Theta_{n}$. Partition $\mathbb{X}$ as
$\mathbb{X}=\mathbb{X}_{1}\cup\mathbb{X}_{2}$ where
$\mathbb{X}_{1}=\\{x:|\theta(x)-\theta^{\star}(x)|\geq\delta\\}$ and
$\mathbb{X}_{2}=\mathbb{X}_{1}^{\text{\sc c}}$ and where $\delta>0$ is as in
Assumption 6.2. Using (63), the mean function can be expressed as

$\displaystyle 2m(\theta,\theta^{\star})$
$\displaystyle=\int_{\mathbb{X}_{1}}\int_{\theta(x)\wedge\theta^{\star}(x)}^{\theta(x)\vee\theta^{\star}(x)}\\{\theta(x)\vee\theta^{\star}(x)-y\\}\,P_{x}(dy)\,P(dx)$
$\displaystyle\qquad+\int_{\mathbb{X}_{2}}\int_{\theta(x)\wedge\theta^{\star}(x)}^{\theta(x)\vee\theta^{\star}(x)}\\{\theta(x)\vee\theta^{\star}(x)-y\\}\,P_{x}(dy)\,P(dx).$

For convenience, refer to the two integrals on the right-hand side of the
above display as $I_{1}$ and $I_{2}$, respectively. Using Assumption 6.2 and
replacing the range of integration in the inner integral by a
$(\delta/2)$-neighborhood of $\theta^{\star}(x)$ we can lower bound $I_{1}$ as

$\displaystyle I_{1}$
$\displaystyle\geq\int_{\mathbb{X}_{1}\cap\\{x:\theta^{\star}(x)>\theta(x)\\}}\int_{\theta^{\star}(x)-\delta}^{\theta^{\star}(x)-\delta/2}\\{\theta^{\star}(x)-y\\}\,P_{x}(dy)\,P(dx)$
$\displaystyle\qquad+\int_{\mathbb{X}_{1}\cap\\{x:\theta^{\star}(x)\leq\theta(x)\\}}\int_{\theta^{\star}(x)}^{\theta^{\star}(x)+\delta/2}\\{\theta(x)-y\\}\,P_{x}(dy)\,P(dx)$
$\displaystyle\geq(\beta\delta^{2}/4)\,P(\mathbb{X}_{1}).$

Next, for $I_{2}$, we can again use Assumption 6.2 to get the lower bound

$\displaystyle I_{2}$
$\displaystyle\geq\int_{\mathbb{X}_{2}}\int_{\theta(x)\wedge\theta^{\star}(x)}^{\\{\theta(x)+\theta^{\star}(x)\\}/2}\\{\theta(x)\vee\theta^{\star}(x)-y\\}\,P_{x}(dy)\,P(dx)$
$\displaystyle\geq\frac{\beta}{2}\int_{\mathbb{X}_{2}}|\theta(x)-\theta^{\star}(x)|^{2}\,P(dx).$

Similarly, for sufficiently large $n$, if $\theta\in\Theta_{n}$, then the
$L_{2}(P)$ norm is bounded as

$\|\theta-\theta^{\star}\|_{L_{2}(P)}^{2}\leq\int_{\mathbb{X}_{2}}|\theta(x)-\theta^{\star}(x)|^{2}\,P(dx)+(\Delta_{n})^{2}\,P(\mathbb{X}_{1}).$

Comparing the lower and upper bounds for $m(\theta,\theta^{\star})$ and
$\|\theta-\theta^{\star}\|_{L_{2}(P)}^{2}$ in terms of integration over
$\mathbb{X}_{1}$ and $\mathbb{X}_{2}$ we have

$\int_{\mathbb{X}_{2}}|\theta(x)-\theta^{\star}(x)|^{2}\,P(dx)\lesssim I_{2},$

and

$(\Delta_{n})^{-2}\int_{\mathbb{X}_{1}}|\theta(x)-\theta^{\star}(x)|^{2}\,P(dx)\lesssim
I_{1},$

which together imply

$m(\theta,\theta^{\star})\gtrsim(\Delta_{n})^{-2}\|\theta-\theta^{\star}\|_{L_{2}(P)}^{2}.$

Recall, from (64), that $\theta\mapsto\ell_{\theta}(x,y)$ is $1-$Lipschitz.
Therefore, if $\theta\in\Theta_{n}$, for large enough $n$, then the loss
difference is bounded by $\Delta_{n}$, so Lemma 7.26 in Lafftery et al.,
(2010), along with the lower and upper bounds on $m(\theta,\theta^{\star})$
and $v(\theta,\theta^{\star})$, can be used to verify Condition 2. That is,
there exists a $K>0$ such that for all $\theta\in\Theta_{n}$

$\displaystyle Pe^{-\omega_{n}(\ell_{\theta}-\ell_{\theta^{\star}})}$
$\displaystyle\leq\exp\\{2\omega_{n}^{2}v(\theta,\theta^{\star})-K\omega_{n}m(\theta,\theta^{\star})\\}$
$\displaystyle\leq\exp[-K\omega_{n}\Delta_{n}^{-2}\|\theta-\theta^{\star}\|_{L_{2}(P)}^{2}\\{1-2\omega_{n}\Delta_{n}^{2}\\}]$
$\displaystyle\leq\exp(-K_{n}\omega_{n}\varepsilon_{n}^{2})$

where the last inequality holds for $K_{n}=(K/2)\Delta_{n}^{-2}$. Given
Assumption 6.4, the above inequality verifies Condition 2 for $\omega_{n}$ and
$\Delta_{n}$ as in Proposition 6.

##  Appendix D Proof of Proposition 7

Proposition 7 follows from Theorem 1 by verifying (15) and Condition 1.

First, we verify (15). By definition

$\displaystyle m(\theta,\theta^{\star})$
$\displaystyle=R(\theta)-R(\theta^{\star})$
$\displaystyle=\int_{\mathbb{Z}}\int_{\theta(z)\wedge\theta^{\star}(z)}^{\theta(z)\vee\theta^{\star}(z)}|2\eta_{z}(x)-1|P(dx)P(dz).$

And, since $\ell_{\theta}$ is bounded by $1$,

$v(\theta,\theta^{\star})\leq\int_{\mathbb{Z}}\int_{\theta(z)\wedge\theta^{\star}(z)}^{\theta(z)\vee\theta^{\star}(z)}P(dx)P(dz)=d(\theta,\theta^{\star}).$

Since $|2\eta_{z}(x)-1|\leq 1$ and, by Assumption A7.5,

$\int_{\theta(z)\wedge\theta^{\star}(z)}^{\theta(z)\vee\theta^{\star}(z)}P(dx)\lesssim|\theta(z)-\theta^{\star}(z)|,$

it follows that

$\\{m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\\}\lesssim\|\theta-\theta^{\star}\|_{L_{1}(P)}:=\int_{\mathbb{Z}}|\theta(z)-\theta^{\star}(z)|\,P(dz).$

Let $J_{n}=n^{1/(1+\alpha)}$ and define a sup-norm ball around
$\theta^{\star}$

$B_{n}^{\star}=\\{(\beta,J):\beta\in\mathbb{R}^{J},J=J_{n},\|\theta^{\star}-\hat{\theta}_{J,\beta}\|_{\infty}\leq
CJ_{n}^{-\alpha}\\}.$

Then, by Assumption A7.3, and using the same argument as in the proof of
Theorem 1 in Shen and Ghosal, (2015) we have

$\Pi(B_{n}^{\star})\gtrsim e^{-CJ_{n}\log n},$

for some $C>0$. Since $J_{n}\log n\lesssim n\omega\varepsilon_{n}$ and
$\theta\in B_{n}^{\star}$ implies $\\{m(\theta,\theta^{\star})\vee
v(\theta,\theta^{\star})\\}\lesssim\varepsilon_{n}$, it follows that (15)
holds with $r=1$.

Next, we verify Condition 1. By Assumption A7.4

$\displaystyle m(\theta,\theta^{\star})$ $\displaystyle\geq
h\int_{\mathbb{Z}}\int_{\theta(z)\wedge\theta^{\star}(z)}^{\theta(z)\vee\theta^{\star}(z)}P(dx)P(dz)=h\,d(\theta,\theta^{\star}).$

Then, Lemma 7.26 in Lafftery et al., (2010) implies

$\displaystyle Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}$
$\displaystyle\leq\exp\\{C\omega^{2}v(\theta,\theta^{\star})-\omega
m(\theta,\theta^{\star})\\}$
$\displaystyle\leq\exp\\{-\omega(h-C\omega)\,d(\theta,\theta^{\star})\\},$

where $C>0$ depends only on $\omega$. For small $\omega$, $C=O(1+\omega)$, so
if $\omega(1+\omega)\leq h$, then

$Pe^{-\omega(\ell_{\theta}-\ell_{\theta^{\star}})}\leq\exp\\{-K\omega
d(\theta,\theta^{\star})\\}$

for a constant $K$ depending on $h$, which verifies Condition 1 with $r=1$.