1 Introduction↩︎

Overparametrized statistical models have far more parameters than training points. Their empirical success in the context of deep learning has elicited a flurry of theoretical activity on the reasons such models are able to generalize well. With so many parameters, these models can perfectly fit the training data with simple and efficient algorithms minimizing an empirical loss without hurting generalization performance [1]. With such an overparametrization one expects the existence of a large set of points in the parameter space with zero training error, suggesting that good generalization is a property of the specific algorithm used to minimize the loss function, rather than a consequence of an explicit control on the model’s complexity, as might be done by explicit regularization [2]. This phenomenon, known as implicit regularization, has been the topic of much research showing that gradient descent and its variants tend to find solutions of some minimum norm, thereby selecting a model in a statistically favorable way; see for instance [3], [4].

In this paper we are interested in the generalization properties of the set of interpolators: points in parameter space with zero training error. We want to understand the full profile of possible generalization performances, beyond the ones algorithmically selected via empirical risk minimization, and investigate whether there is a typical performance achieved by “most" interpolators.

We consider the simple setting of linear binary classification with fixed margin \(\kappa\), in \(d\) dimensions and with \(n\) samples, under two distinct data-generating distributions of constant signal-to-noise ratio \(\lambda\): a mixture of two Gaussians, and the logistic model with Gaussian features. In each case we provide a precise asymptotic characterization of the fraction of interpolators having any desired generalization performance \(x\), in the proportional limit \(n \to\infty\) and \(n/d \to \alpha\), and \(\alpha\) small enough. Our result takes the form of a “quenched" large deviation principle (LDP) on the event that a point chosen uniformly at random from the set of interpolators achieves a performance approximately \(x\). The rate function of this LDP is given by a variational problem whose maximum is achieved at a value \(x_{\star} = x_{\star}(\alpha,\kappa,\lambda)\), the performance of a ‘typical’ interpolator. As a byproduct, we establish that with high probability over the data, all but an exponentially small fraction of interpolators have a performance near \(x_{\star}\).

We next remark that this typical performance is lower than the ones algorithmically achieved: we compare the value of \(x_{\star}\) to the performances \(x_{\rm\tiny LP}\) and \(x_{\rm\tiny GD}\) of two interpolators respectively found by a linear programming procedure proposed in [5], and gradient descent on the logistic loss function analyzed in [6]. We find that \(x_{\star}\) is smaller than \(x_{\rm\tiny LP}\) and \(x_{\rm\tiny GD}\) for a large range of parameters. We deduce that “good" interpolators — in the sense of being at least as good as the two aforementioned efficient baseline algorithms — are exceedingly rare in this high-dimensional, constant SNR, overparametrized regime.

For further comparison we also derive an asymptotic characterization of the Bayes optimal performance \(x_{\rm\tiny Bayes}\) – that of a parameter vector drawn from the posterior distribution given the data – under both data-generating distributions. This is similarly done by establishing an LDP on the generalization performance under the corresponding posterior distributions.

Our result confirms a conjecture of Theisen, Klusowski and Mahoney [7] that the generalization error of a uniformly random interpolator should concentrate around a typical value. They address in their work the question of ‘abundance of good interpolators’ where they conduct a heuristic analysis of this typical error in the setting of the Gaussian mixture model, leading them to claim that “good classifiers are abundant in the interpolation regime", seemingly at odds with our findings. But their analysis implicitly assumes a concentration condition about the Gram matrix of the data which can only hold at high SNR: the separation between the Gaussian centers must be growing with the dimension. In this paper we reach a more nuanced conclusion, namely that good interpolators are exceedingly rare in the constant SNR regime – making implicit regularization a genuinely nontrivial phenomenon – and that the typical performance \(x_\star\) increases with the SNR \(\lambda\) (and with the sampling ratio \(\alpha\)) leading to a good typical performance in the large SNR limit, in accordance with the results of [7] in that limit.

2 Settings↩︎

We consider the setting of binary classification with data \((X_i,y_i)_{i=1}^n\) where \(X_i \in \mathbb{R}^d\) is a vector of \(d\) covariates and \(y_i \in \{-1,+1\}\) is the class label. Let \(\theta_{\star} \in \mathbb{S}^{d-1}(\sqrt{d})\) be a distinguished ‘signal’ direction. We consider two data-generating distributions:

1. The Gaussian mixture model \(\mathcal{D}_{\mathrm{\small \tiny gmm}}\): independently for \(i=1,\cdots,n\) let \(y_i = \pm 1\) with equal probability, and \[\label{eq:gmm95dist} X_i \,|\, y_i \sim N\left(\sqrt{\frac{\lambda}{d}}\, y_i \theta_\star\,,\,I_d\right)\,\tag{1}\] for a fixed signal-to-noise ratio (SNR) parameter \(\lambda > 0\).

2. The logistic model \(\mathcal{D}_{\mathrm{\small \tiny logistic}}\): independently for \(i=1,\cdots,n\) let \(X_i \sim N(0,I_d)\) and conditionally on \(X_i\), \[\label{eq:logistic95dist} y_i = \begin{cases} +1 &with prob. ~~\varphi \big(\sqrt{\lambda/d}\,\langle X_i ,\theta_{\star}\rangle\big)\,, \\ -1 &with prob. ~~1 - \varphi \big(\sqrt{\lambda/d}\,\langle X_i ,\theta_{\star}\rangle\big)\,, \end{cases}\tag{2}\] for a fixed SNR \(\lambda > 0\). Here \(\varphi: \mathbb{R}\to [0,1]\) is an increasing link function which we fix throughout the paper to have the sigmoid form \[\label{eq:sigmoid} \varphi(x) = \frac{1}{1+e^{-x}}\,.\tag{3}\] We will denote the Rademacher distribution on \(\{-1,+1\}\) with probability \(p\) assigned to \(+1\) by \(\text{Rad}(p)\), hence we can write \[y_i \, |\, X_i \sim \text{Rad}\Big(\varphi \big(\sqrt{\lambda/d}\,\langle X_i ,\theta_{\star}\rangle\big)\Big)\,.\]

Let \(X \in \mathbb{R}^{n \times d}\) be the matrix with the vectors \(X_i\) as its rows, and let \(\kappa \in \mathbb{R}\) be a fixed margin parameter. We consider the set \(S_{\kappa}(X,y) \subset \mathbb{S}^{d-1}(\sqrt{d})\) of directions \(\theta\) that correctly classifies all data points up to margin \(\kappa\): \[\label{eq:interpolators} S_{\kappa}(X,y) := \Big\{\theta \in \mathbb{S}^{d-1}(\sqrt{d}) ~:~ y_i \langle X_i, \theta \rangle \ge \kappa \sqrt{d} ~\text{ for all }1 \le i \le n\Big\}\,.\tag{4}\] This is the set of linear interpolators with margin \(\kappa\).

The generalization error of an estimator of \(\theta_\star\), a measurable function \(\hat{\theta}_n : (\mathbb{R}^d \times \{-1,+1\})^n \to \mathbb{S}^{d-1}(\sqrt{d})\), is the probability of misclassifying a new data point: \[\mathcal{E}(\hat{\theta}_n) = \operatorname{\mathbb{P}}\big(y\langle X, \hat{\theta}_n \rangle < 0\big),\] where \((X,y) \sim \mathcal{D}\in\{\mathcal{D}_{\mathrm{\small \tiny gmm}},\mathcal{D}_{\mathrm{\small \tiny logistic}}\}\). We remark that by rotational invariance of the Gaussian distribution, the above error only depends on the inner product \(\langle \hat{\theta}_n, \theta_\star \rangle/d\) of which it is a monotonically decreasing function. Therefore we can measure performance by amount of overlap instead of generalization error.

2.0.0.1 Large deviations for interpolating linear classifiers

Let \(\mu_{X,y}\) denote the uniform measure over \(S_{\kappa}(X,y)\), Eq. 4 , whenever this set is non empty (and define \(\mu_{X,y}\) arbitrarily otherwise). We want to establish an asymptotic, high-probability formula for the random quantity \[\label{eq:log-ratio} \frac{1}{d} \log \mu_{X,y}\big(\{\theta : |\langle \theta, \theta_\star \rangle/d - x| \le \varepsilon\}\big) \, ,\tag{5}\] where \(n\) and \(d\) are proportionally large and \(\varepsilon\) is an arbitrary small number, capturing the fraction of interpolators with overlap near \(x\) with \(\theta_\star\) in the exponential scale. Equivalently we would like to establish a ‘quenched’ large deviation principle for the event that \(\langle \theta, \theta_\star \rangle/d \approx x\), where \(\theta\) is drawn uniformly at random from \(S_{\kappa}(X,y)\). From 5 this boils down to estimating the logarithm of the area of \(S_{\kappa}(X,y)\) (as a measurable subset of the sphere) and that of its slices \[\label{eq:slices} S_{x,\varepsilon}(X,y) := S_{\kappa}(X,y) \cap \{\theta : |\langle \theta , \theta_\star\rangle/d - x| \le \varepsilon\}\,,~~~ x \in (-1,1)\,,~~\varepsilon>0\,,\tag{6}\] corresponding to all points having overlap approximately \(x\) with the signal direction \(\theta_\star\). The quantity in 5 is then equal to \((1/d) \log \big(|S_{x,\varepsilon}(X,y) | / |S_{\kappa}(X,y)|\big)\), where \(|A|\) denotes the \(d-1\) dimensional surface area of any Lebesgue measurable subset of \(\mathbb{S}^{d-1}(\sqrt{d})\). This will be the content of Theorem 1.

2.0.0.2 Large deviations for Bayes-optimal classifiers

We also consider a Bayesian setting where the signal direction \(\theta_\star\) is drawn uniformly at random from the sphere \(\mathbb{S}^{d-1}(\sqrt{d})\). If the data \((X,y)\) conditional on \(\theta_\star\) are drawn from \(\mathcal{D}\in \{\mathcal{D}_{\mathrm{\small \tiny GMM}}, \mathcal{D}_{\mathrm{\small \tiny Logistic}}\}\), the density of the posterior distribution (relative to the normalized area measure on \(\mathbb{S}^{d-1}(\sqrt{d})\)) of \(\theta_\star\) given \((X,y)\) takes the form \[\label{eq:posterior} p_{X,y}(\theta) = \frac{1}{Z_{X,y}} \prod_{i=1}^n \exp u\left(\frac{y_i\big\langle X_i ,\theta\big\rangle}{\sqrt{d}}\right)\,, ~~~ \theta \in \mathbb{S}^{d-1}(\sqrt{d})\,,\tag{7}\] where \(u(x) = \sqrt{\lambda} \, x\) for \(\mathcal{D}= \mathcal{D}_{\mathrm{\small \tiny GMM}}\), and \(u(x) = \log \varphi(\sqrt{\lambda}\, x)\) for \(\mathcal{D}= \mathcal{D}_{\mathrm{\small \tiny Logistic}}\). The denominator \(Z_{X,y}\) is the normalizing constant called the partition function of \(p_{X,y}\).

We will similarly be interested in quantifying the probability of the large deviation event \(\{|\langle \theta, \theta_\star \rangle/d - x| \le \varepsilon\}\), when \(\theta\) is drawn from the posterior distribution 7 , and this amounts to establishing an asymptotic formula for \[\label{eq:log-posterior} \frac{1}{d} \log p_{X,y}\big(\{\theta : |\langle \theta, \theta_\star \rangle/d - x| \le \varepsilon\}\big)\,.\tag{8}\] This will be the content of Theorem 4.

3 Main results↩︎

Fix the parameters \(\alpha,\kappa,\lambda\), a function \(u: (-1,1) \to [-\infty,\infty)\), and a random variable \(S\). Consider the following function defined on \((-1,1) \times [0,1) \to \mathbb{R}\): \[\label{eq:phi95master} \begin{align} \Phi(x,q) &= \alpha \operatorname{\mathbb{E}}\log \operatorname{\mathbb{E}}_{W} \exp u\Big( x S + \sqrt{(1-x^2)q}Z + \sqrt{(1-x^2)(1-q)} W \Big) \\ & + \frac{1}{2} \frac{q}{1-q} + \frac{1}{2} \log\big((1-x^2)(1-q)\big) \,, \end{align}\tag{9}\] where \(S, Z, W\) are mutually independent, and \(Z, W \sim N(0,1)\). \(\operatorname{\mathbb{E}}_W\) is the expectation with respect to \(W\) while \(\operatorname{\mathbb{E}}\) averages over \(Z\) and \(S\).

3.1 LDP for a uniform interpolator↩︎

In this section we state our main results on the large deviations of the overlap under the uniform measure \(\mu_{X,y}\) on the set of interpolators. We let \[\label{eq:complementary95cdf95normal} \mathcal{N}(x) = \int_{x}^{+\infty} e^{-z^2/2} \frac{\mathrm{d}z}{\sqrt{2\pi}}\tag{10}\] be the complementary c.d.f.of the standard normal distribution, and let \[u(x) = \begin{cases} 0 &if ~~x \ge \kappa\,,\\ -\infty & otherwise\,. \end{cases}\] The expression of \(\Phi\) simplifies to \[\begin{align} \label{eq:phi95interp} \Phi(x,q) &= \alpha \operatorname{\mathbb{E}}\log \mathcal{N}\Biggl( \frac{\kappa- x S - \sqrt{(1-x^2)q}Z}{\sqrt{(1-x^2)(1-q)}} \Biggr) + \frac{1}{2} \frac{q}{1-q} + \frac{1}{2} \log\big((1-x^2)(1-q)\big)\,. \end{align}\tag{11}\]

The law of the random variable \(S\) will depend on the data-generating distribution:

• If \(\big\{ (X_i, y_i) \big\}_{i=1}^n \sim \mathcal{D}_{\mathrm{\small \tiny GMM}}\) we let \[\label{eq:defSgmm} S = \sqrt{\lambda} + G\,,~~~~G \sim N(0,1)\,.\tag{12}\]

• If \(\big\{ (X_i, y_i) \big\}_{i=1}^n \sim \mathcal{D}_{\mathrm{\small \tiny Logistic}}\) we let \[\label{eq:defSlogistic} S = YG\,,~~~~G \sim N(0,1)\,,~~~~ Y|G \sim \text{Rad}\big(\varphi(\sqrt{\lambda}G)\big)\,.\tag{13}\]

We are now in position to state our quenched large deviation principle for the uniform measure \(\mu_{X,y}\) on \(S_{\kappa}(X,y)\). Let \[\label{eq:minmax} \phi = \sup_{x \in (-1,1)}\inf_{q \in [0,1)}\Phi(x,q)\,,\tag{14}\] and for an interval \(I \subseteq (-1,1)\), \[\label{eq:ratefct} \bar{\phi}(I) = \sup_{x \in I} \inf_{q \in [0,1)}\Phi(x,q) - \phi\,.\tag{15}\] Further let \(\kappa_+ = \max\{\kappa, 0\}\).

The quantity \(\delta=\delta(\alpha, \lambda, \kappa_+)\) is defined in (?? ); for \(\alpha \le \alpha_0\), we have \(\delta \le 1/10\). We furthermore note that as a corollary of our proof, the above results hold for any prescribed \(\delta > 0\) if now \(\alpha \le \alpha_0(\delta, \lambda, \kappa_+)\). The above theorem characterizes the area of the set of interpolators and the rate function of the LDP for the overlap with the signal direction under \(\mu_{X,y}\). This shows that the normalized overlap \(\langle \theta , \theta_\star\rangle/d\) is exponentially concentrated around the maximizers of the function \(x \mapsto \inf_{q} \Phi(x,q)\) when \(\theta \sim \mu_{X,y}\), with high probability over the data. (Note the bound (?? ) shows that the set of interpolators with normalized overlap outside \([-1+\delta, 1-\delta]\) makes an exponentially small contribution.)

We remark that \(\alpha_0\) depends on the margin \(\kappa\) only when the latter is positive; we will show in Appendix 6 that one can take \(\alpha_0(\lambda,\kappa) = c(\lambda)/(1+\kappa^2)\) in this case. For negative margin the result holds as long as \(\alpha\) is small enough as a function of the SNR \(\lambda\) only.

We further show that for \(\alpha\) small enough the ‘sup-inf’ saddle point problem 14 is achieved at a unique pair \((x,q) \in [0,1)^2\) which satisfies a system of two nonlinear equations. We state the results for the Gaussian mixture model and the logistic model in two separate propositions.

Let \(\mathcal{A}\) be the inverse of Mills’ ratio \[\label{eq:mills} \mathcal{A}(x) = - \mathcal{N}'(x)/\mathcal{N}(x) = \frac{1}{\sqrt{2 \pi}}\frac{e^{-x^2/2}}{\mathcal{N}(x)}\,.\tag{16}\] We will say that the saddle point problem \(\sup\inf \Phi\) is uniquely achieved if there is a unique \(x_{\star} \in [0,1)\) achieving \(\sup_{x \in (-1,1)} \inf_{q \in [0,1)} \Phi(x,q)\), and if there is a unique \(q_{\star} \in [0,1)\) achieving \(\inf_{q \in [0,1)}\Phi(x_{\star},q)\).

Furthermore, in both the above cases, \((x_{\star}, q_\star) \in [0, K\alpha]^2\) where \(K>0\) depends on \(\lambda\) and \(\kappa_+\).

3.1.0.1 Physical interpretation of \(q\):

While the parameter \(x_\star\) represents the asymptotic amount of overlap a direction \(\theta \sim \mu_{X,y}\) has with \(\theta_\star\), the parameter \(q_\star\) has an equally concrete interpretation: let \(\theta\) and \(\theta'\) be two independent copies from \(\mu_{X,y}\) conditional on the same realization of the data \((X,y)\), and denote by \(\bar{\theta}\) and \(\bar{\theta}'\) their projections (of norm \(\sqrt{d}\)) orthogonal to \(\theta_\star\). Then \(q_\star\) represents the asymptotic value of the overlap \(\langle \bar{\theta},\bar{\theta}' \rangle/d\). A crucial step in the proofs of the above formulas is to show that this overlap indeed concentrates around \(q_\star\).

3.2 LDP for the posterior distribution↩︎

We state a similar result for the posterior distribution 7 in the Bayesian setting. Recall the function \(\Phi\) from 9 . In this Bayesian case both the function \(u\) and the random variable \(S\) depend on the data-generating distribution.

• If \(\big\{ (X_i, y_i) \big\}_{i=1}^n \sim \mathcal{D}_{\mathrm{\small \tiny GMM}}\) we let \[\label{eq:defuSgmm} S = \sqrt{\lambda} + G~~~and ~~~ u(x) = \sqrt{\lambda}\,x\,.\tag{17}\]

• If \(\big\{ (X_i, y_i) \big\}_{i=1}^n \sim \mathcal{D}_{\mathrm{\small \tiny Logistic}}\) we let \[\label{eq:defuSlogistic} S = YG ~~~and ~~~ u(x) = \log \varphi(\sqrt{\lambda}\,x)\,,\tag{18}\] where as before, \(G \sim N(0,1)\) and \(Y|G \sim \text{Rad}\big(\varphi(\sqrt{\lambda}G)\big)\).

We have the following quenched LDP for the posterior distribution \(p_{X,y}\). Let \[\label{eq:minmaxBayes} \phi = \sup_{x \in (-1,1)}\inf_{q \in [0,1)}\Phi(x,q)\,,\tag{19}\] and for \(I \subset (-1,1)\), \[\label{eq:ratefctBayes} \bar{\phi}(I) = \sup_{x \in I} \inf_{q \in [0,1)}\Phi(x,q) - \phi\,.\tag{20}\]

Here, \(\delta=\delta(\alpha, \lambda)\) is defined in (?? ); for \(\alpha \le \alpha_0\), we have \(\delta \le 1/10\). Again, the above results hold for any prescribed \(\delta > 0\) if \(\alpha \le \alpha_0(\delta, \lambda)\). (The bound (?? ) shows that the set of interpolators with normalized overlap outside \([-1+\delta, 1-\delta]\) makes an exponentially small contribution.)

Similarly in this case, the sup-inf saddle point problem is uniquely achieved:

The uniqueness results combined with ?? shows exponential concentration of the normalized overlap under the posterior distribution, and characterizes the Bayes-optimal performance in estimating the signal direction \(\theta_\star\). Again, in both of the above cases, \((x_{\star}, q_\star) \in [0, K\alpha]^2\) where \(K>0\) depends on \(\lambda\).

3.2.0.1 A special relation between \(x\) and \(q\):

Keeping in mind the interpretation of \(q\) mentioned in the previous section, the present Bayesian setting imposes a special relation between \(x\) and \(q\): for two independent copies \(\theta,\theta'\) from \(p_{X,y}\) we have by the law of iterated expectations \[\label{eq:nishimori} \operatorname{\mathbb{E}}\langle \theta, \theta_\star\rangle = \operatorname{\mathbb{E}}\langle \theta, \theta'\rangle \,.\tag{21}\] Therefore by concentration of the random variables inside each of the above expectations (see Appendix 9.3) the Pythagorean theorem would impose the relation \[x = x^2 + (1-x^2) q\,, ~~~i.e.,~~~ x = \frac{q}{1-q}\,.\] This identity is apparent in the Gaussian mixture case, see Eq. ?? , but is less clear in the logistic case. We show a similar result:

This allows to search for the pair \((x_{\rm\tiny Bayes},q_{\rm\tiny Bayes})\) along a univariate curve, usually referred to as the Nishimori line, see [8] and [9]. No such simplification occurs in general outside the Bayesian setting. In particular the system of equations governing the pair \((x_\star,q_\star)\) concerning the uniform measure \(\mu_{X,y}\) treated in the previous section remains genuinely bivariate.

The proofs of Theorems 1 and 4 can be found in Appendix 8.1. The proofs of Propositions 2, 3, 5, 6, and Lemma 1 can be found in Appendix 10.4.

3.3 Comparisons and numerical simulations↩︎

In this section we compare the performance of a typical interpolator relative to that of a draw from the posterior and to two efficient algorithms for finding points in \(S_{\kappa}(X,y)\). (Note that the posterior distribution is not supported on the set of interpolators; a draw from \(p_{X,y}\) will typically not belong to \(S_{\kappa}(X,y)\) for any \(\kappa\).) For convenience we rescale the parameter space by \(\sqrt{d}\) in this section, so that \(\theta_{\star}\) and all its estimators have unit \(\ell_2\) norm.

The first algorithm is a second-order cone programming procedure \[\label{eq:lp} \mathrm{LP}~:~~~\max_{\theta \in \mathbb{R}^d} ~ \frac{1}{n}\sum_{i=1}^n \big\langle y_i X_i , \theta\big\rangle ~~subj.\;to ~~ \|\theta\|_2 \le 1\,,~~ \big\langle y_i X_i , \theta \big\rangle \ge \kappa \,,~\forall i \in [n]\,.\tag{22}\]

Note that the spherical constraint \(\|\theta\|_2 = 1\) is relaxed to a unit ball norm constraint \(\|\theta\|_2 \le 1\) making the optimization problem convex. By abuse of terminology we refer to this procedure as a linear program (LP), emphasizing the linear nature of the objective and the data-related constraints. This LP maximizes the correlation with the vector \(v = (1/n)\sum_{i=1}^n y_iX_i\) representing a proxy of the signal direction, while staying on the correct side of the hyperplane corresponding to each data point. In [5] it was shown that when the data is drawn from \(\mathcal{D}_{\mathrm{\small \tiny Logistic}}\), the norm constraint is saturated, resulting in an estimator \(\hat{\theta}_{\rm\tiny LP}\) lying on the unit sphere, \(\|\hat{\theta}_{\rm\tiny LP}\|_2=1\) with high probability. Thus the algorithm produces a point in \(S_{\kappa}(X,y)\) with high probability.

The second algorithm is empirical risk minimization of a smooth loss function via gradient descent: \[\label{eq:erm} \min_{\theta \in \mathbb{R}^d} ~ \Big\{R(\theta) := \sum_{i=1}^n \ell\big(\big\langle y_i X_i , \theta\big\rangle - \kappa \|\theta\|_2\big)\Big\}\,,\tag{23}\] where \(\ell : \mathbb{R}\to \mathbb{R}_{\ge 0}\) is a decreasing function with \(\lim_{x \to +\infty} \ell(x) = 0\); we only consider the logistic loss \(\ell(x) = \log(1+e^{-x})\) for concreteness. The gradient descent iteration on \(R\) reads \[\begin{align} \label{eq:gd} \begin{aligned} \mathrm{GD}~:~~~ \theta^{t+1} &= \theta^t - \eta\nabla R(\theta^t) \\ &= \theta^t -\eta \sum_{i=1}^n \big(y_i X_i - \kappa \theta^t/\|\theta^t\|\big) \ell'\big(\big\langle y_i X_i , \theta^t\big\rangle - \kappa \|\theta\|_2\big) \,, \end{aligned} \end{align}\tag{24}\] where \(\eta>0\) is a fixed stepsize and \(t \in \{0,1,\cdots\}\). It was shown in [5] that under smoothness assumptions on \(\ell\) (satisfied by the logistic loss) and for small enough stepsize \(\eta\), this iteration produces a margin-\(\kappa\) classifier: \[\lim_{t\to \infty} \min_{1\le i \le n} \big\langle y_i X_i , \theta^t/\|\theta^t\|_2 \big\rangle \ge \kappa\,,\] as long as \(\|\theta^{t}\|_2 \to \infty\) as \(t \to \infty\).

For both data distributions \(\mathcal{D}_{\mathrm{\small \tiny logistic}}\) and \(\mathcal{D}_{\mathrm{\small \tiny GMM}}\) and both the LP and GD algorithms we perform a Monte Carlo estimate of the squared \(\ell_2\) distance \(\|\hat{\theta}- \theta_\star\|_2^2 = 2(1-\langle \hat{\theta}, \theta_\star\rangle)\) over \(T=20\) trials where the data is freshly resampled. We fix the dimension to \(d=3000\), the margin to \(\kappa = 0\), the signal-to-noise ratio to \(\lambda = 1\) and vary the number of samples-to-dimension ratio \(\alpha\) in the range \(\{0.01,\cdots,1\}\) in increments of 0.1.

In the case of LP we use a specialized numerical solver to obtain a solution \(\hat{\theta}_{\rm\tiny LP}\) to 22 and verify that the normalization condition \(\|\hat{\theta}_{\rm\tiny LP}\|_2=1\) is satisfied to \(10^{-2}\) accuracy in all instances.

In the case of GD we run the iteration 24 with step size \(\eta = 1.5\) until either the \(\ell_2\) norm of the gradient of \(R\) is smaller than \(10^{-8}\) or a maximum number of iterations of \(500\) is reached. We verify that the margin condition \(\min_{1\le i \le n} \langle y_i X_i , \hat{\theta}_{\rm\tiny GD} \rangle \ge \kappa\) is satisfied in all instances, where \(\hat{\theta}_{\rm\tiny GD} = \theta^t/\|\theta^t\|_2\) at the terminal time step \(t\).

We compare these empirically obtained values to our theoretical predictions of the squared \(\ell_2\) distances achieved by a typical interpolator \(\theta \sim \mu_{X,y}\): \[\rm err_{\star} := \lim_{d \to \infty} \operatorname{\mathbb{E}}\|\theta- \theta_\star\|_2^2 = 2(1 - x_{\star}),\] where \(x_{\star}\) is described in Lemmas 2 and 3 for the data-generating distributions \(\mathcal{D}_{\mathrm{\small \tiny GMM}}\) and \(\mathcal{D}_{\mathrm{\small \tiny Logistic}}\) respectively, and the error achieved by the posterior mean \(\hat{\theta}^{\rm\tiny Bayes}\), \[\rm err_{\rm\tiny Bayes} := \lim_{d \to \infty}\operatorname{\mathbb{E}}\|\hat{\theta}^{\rm\tiny Bayes}- \theta_\star\|_2^2 = 1 - x_{\rm\tiny Bayes},\] where \(x_{\rm\tiny Bayes}\) is described in Lemmas 5 and 6 for these same distributions. The corresponding fixed point equations are numerically solved via bisection.

The numerical results are summarized in Figure 1. We see that both algorithms significantly outperform a typical interpolator under both distributions and across all tested values of \(\alpha\), with the Bayes error being smallest overall. Since this error concentrates exponentially in \(d\) under the uniform measure on \(S_{\kappa}(X,y)\) (Theorem 1), only an exponentially small fraction of points in \(S_{\kappa}(X,y)\) perform at least as well as LP or GD.

This numerical finding can supported by theory: for data generated from the logistic model, [5] established that the LP (22 ) achieves correlation \(x_{\rm\tiny LP} = \Theta(\sqrt{\alpha})\) in the limit \(\kappa\rightarrow -\infty\) with \(\lambda\) fixed; see Lemmas 22, 23, 24 therein. In contrast we have \(x_{\star} = O(\alpha)\) for \(\kappa\le 0\). This comparison again establishes that for small \(\alpha\), only an exponentially small fraction of points in \(S_{\kappa}(X, y)\) perform as well as the LP, in line with the results of our numerical simulations.

We remark that this effect is purely due to overparametrization: the performance gap between the above estimators vanishes as the sampling ratio \(\alpha\) is increased. Heuristically this can be seen from the fact that the area of the set \(S_{\kappa}(X,y)\) is a decreasing function of \(\alpha\) since the map \(\alpha \mapsto \phi\) (Eq. 14 ) is decreasing, leading to consistent estimation for large enough \(\alpha\) (or \(\lambda \to \infty\)). This is in agreement with the results of [5] who provided bounds on the maximum and minimum estimation performance of the points in \(S_{\kappa}(X,y)\). These bounds converge towards a common value as \(\alpha\) increases (see Figure 4 therein).

4 Related work and discussion↩︎

4.0.0.1 Statistical literature and benign overfitting

There has been an impressive amount of work on overparametrization and implicit regularization over the last decade suggesting that overparametrization not only does not hurt statistical performance, but is essential for algorithmic tractability. We refer to [10], [11] for a partial synthesis of the literature. Most existing work analyzes the performance of specific algorithms and statistical procedures in the overparametrized regime and establish their success under suitable data-generating assumptions. A subset of this literature is concerned with obtaining exact high-dimensional asymptotics in (generalized) linear models under idealized data distributions, allowing a precise tracking of the generalization error and other metrics as the parameters of the model are changed. In this line of work we mention the analysis of maximum likelihood and M-estimation in logistic regression [6], [12], Bayes-optimal estimation in GLMs [13], boosting and minimum \(\ell_1\) norm interpolators [14]–[16], maximum margin interpolators [4], [17], among many others.

Closer to our setting, [5] identify sharp bounds on the interpolation threshold for data generated from the logistic model: the maximum value of \(\alpha = n/d\) under which interpolators exist with positive probability, and above which the set of interpolators is empty with high probability. They prove bounds on the generalization performance of any element of \(S_{\kappa}(X,y)\) and leave open the question of whether there exists a value within those bounds which is typical. They additionally analyze the performance of the linear program 22 , while [6] analyze the ERM 23 , which are both compared against in the previous section.

Our work is closely related to [7], [18] who address the question of abundance of good interpolators and tempered overfitting of randomly selected interpolating neural networks. As mentioned earlier [7] conducts a heuristic analysis in the same setting as ours, under the Gaussian mixture model, and conclude that most interpolators have good generalization performance, in the sense of being close to Bayes-optimal. A careful reading of their argument reveals a seemingly innocuous assumption (Eq.(12) therein) which can only hold at high SNR: the separation between the Gaussian centers need to grow faster than \(\sqrt{d} \log n\), and is otherwise violated at constant separation. [18] considers the setting of fully connected multi-layer neural networks (NN) under binary features \(x\) and clean labels \(h_\star(x) \in \{-1,1\}\) corrupted with bit flip noise; see also [19]. When the clean labels are generated by a “teacher" network \(h_\star\) with \(N_\star\) number of neurons, they prove that the generalization of a randomly picked interpolating”student" neural network (of potentially much larger size) with \(N\) neurons is close to Bayes-optimal when the number of samples \(n\) is roughly larger than \(N_\star^4 \vee N\). Importantly, the number of weights of the student network is absent from the sample complexity, which can be very large without hurting generalization, leading to tempered overfitting. But the term \(N_\star^4\) in the sample complexity is roughly quadratic in the number of weights of the teacher network, and an analogy with our setting where the teacher and the student have the same number of parameters \(d\) suggests that this is still a “large \(\alpha\) regime" as \(n\) needs to grow at least like \(d^2\).

4.0.0.2 High dimensional spin glasses and the perceptron model

The set of interpolators is also known as the set of solutions to the spherical perceptron model (or the half-space model when \(\kappa=0\)): if one draws \(n\) uniformly random half-spaces of margin \(\kappa\) in \(d\) dimensions, when is their common intersection with the sphere typically non-empty? And what is the typical area of this intersection? Motivated by questions of learning with threshold functions, Cover [20] determined the interpolation threshold in this model, also known as the storage capacity for \(\kappa=0\): the set is typically non-empty if \(n \le 2(1-o(1))d\) and typically empty if otherwise \(n\ge 2(1+o(1))d\), with additional finer understanding of the critical window. Gardner [21], [22] proposed formulas which would later bear her name in the literature for the storage capacity and for the logarithm of the surface area, based on the non-rigorous replica method, for general \(\kappa \ge0\).

These formulas were proved by Shcherbina and Tirozzi [23] leveraging convexity and concentration of measure. Stojnic [24] found an elegant and simple Gaussian comparison argument establishing Gardner’s storage capacity for \(\kappa \ge 0\). Talagrand’s books [25], [26] present a unified treatment of a larger family of models and incorporate additional important techniques such as Guerra’s interpolation method [27], [28] into their study.

The behavior of the spherical perceptron model when \(\kappa<0\) is much more delicate and few results are available. [29] showed that Gardner’s formula obtained for \(\kappa \ge0\) is an upper bound when \(\kappa < 0\). [5] prove upper and lower bounds on the capacity for \(\kappa \le 0\) which match as \(\kappa \to -\infty\), and a detailed study at the physics level of rigor can be found in [30]. An algorithm for finding a feasible point was proposed in [31] and was shown to work for \(\kappa<0\) under an unproved analytic condition regarding the structure of a certain variational problem.

The binary version of the problem where the sphere is replaced by the binary hypercube has also been intensely studied. The storage capacity question has recently been resolved: the existence of a sharp threshold sequence was established in [32], [33] and the capacity formula predicted by Krauth and Mézard [34] was established in [35], [36]. In addition, peculiar structural phenomena of freezing and preponderance of isolated solutions were established in a symmetric version of this model [37]–[39] but remain open otherwise, and efficient algorithms for finding (a connected set of) solutions were proposed in [40].

5 Proof ideas and roadmap↩︎

The proofs are executed in a unified way by considering the random probability density on the sphere, \[\label{eq:gibbs95measure0} \mu(\theta) = \frac{1}{Z} \mathbf{1}\big\{|\theta_1/\sqrt{d} -x | \le \varepsilon\big\} \prod_{i=1}^n \exp u\big(\langle g_i ,\theta \rangle / \sqrt{d}\big)\,, ~~~ \theta \in \mathbb{S}^{d-1}(\sqrt{d})\,,\tag{25}\] where \(x\) and \(\varepsilon>0\) are fixed, \(u : \mathbb{R}\to \mathbb{R}\) is a smooth concave function with derivatives of controlled growth, and the \(g_i\)’s are i.i.d.random vectors whose first coordinates are copies of a random variable \(S\) drawn from a general strongly log-concave density, and the remaining coordinates are standard normal. Without loss of generality we can set \(\theta_\star = \sqrt{d} e_1\), and the density \(\mu\) corresponds to each case of interest by appropriately choosing \(u\) and the law of \(S\); see Eqs. 12 , 13 for the (formal) correspondence with \(\mu_{X,y}\) and Eqs. 17 , 18 for the correspondence with \(p_{X,y}\).

The goal is then to estimate the normalized logarithm of the restricted partition function \(Z\), called the free energy. We follow Talagrand’s approach in proving the Gardner formula for the spherical perceptron model [25], [26], with additional technical work required for handling the ‘signal part’ of the data: the vectors \(y_i X_i\) have a non-Gaussian component with law \(S\) in the direction of \(\theta_\star\) and are otherwise Gaussian on the complement subspace. This effectively turns the model into a spherical perceptron with Gaussian disorder and random inhomogeneous margins. While Talagrand’s treatment is restricted to \(\kappa \ge 0\), we are able to extend his techniques to our case. By constraining the overlap \(\langle \theta, \theta_\star\rangle/d = \theta_1/\sqrt{d} \simeq x\) and leveraging the log-concavity of the law of \(S\) we can control the fluctuations of the first coordinate to any desired accuracy. This allows us to conduct our analysis for \(\kappa<0\) as long as \(\alpha\) is suitably small. We additionally remark that as a corollary of our proof, we prove the Gardner formula for the spherical perceptron model for all \(\kappa\le 0\) and \(\alpha \le \alpha_0\) smaller than a universal constant.

We mention that our analysis does not operate on the Nishimori line, in contrast to the recent activity in Bayesian settings; see for instance [9], [13], [41]. As already mentioned in Section 3.2, Eq. 21 , there is no special relation between the one-replica and two-replica overlaps \(\langle \theta,\theta_\star\rangle\), \(\langle \theta^1,\theta^2\rangle\) outside the Bayesian setting. Such a relation can simplify interpolation and concentration arguments, and usually lead to a simpler variational formula. The fact that we are outside this special line when studying the uniform measure \(\mu_{X,y}\) on interpolators is responsible for the ‘sup-inf’ structure of the variational formulas we obtain. Finally, we note that although our arguments are lengthy, all known proofs of the Gardner formula are technically involved [23], [25], [26], [42].

In the remaining of this section we present at a high-level the main steps of the proof.

5.1 Relaxation to the Gaussian reference measure↩︎

In more detail, the first step is to relax the spherical constraint to full space by switching to a Gaussian reference measure, and we let \[\label{eq:gibbs95measure1} \mu_{\beta}(\theta) = \frac{1}{Z_\beta} \mathbf{1}\big\{|\theta_1/\sqrt{d} -x | \le \varepsilon\big\} \exp \left(\sum_{i=1}^n u\big(\langle g_i ,\theta \rangle / \sqrt{d}\big) -\beta \|\theta\|^2\right)\,, ~~~ \theta \in \mathbb{R}^d\,,\tag{26}\] now defined relative the Lebesgue measure on \(\mathbb{R}^d\), and where \(\beta >0\) is a parameter. The quadratic term acts as a confining potential.

The measure \(\mu_\beta\) is a log-concave density which has strong concentration properties. In particular the normalized squared norm \(\|\theta\|^2/d\) of a draw \(\theta \sim \mu_{\beta}\), and the normalized overlap \(\langle \theta^1, \theta^2\rangle /d\) of two independent draws from \(\mu_{\beta}\) both concentrate around their expectations. We then use the Gaussian interpolation method to prove a Gardner formula for \(Z_\beta\) of the form \[\label{eq:gardner95relaxed} \frac{1}{d} \log Z_{\beta} = \inf_{0 \le q \le \rho} \Big\{ \bar{\Phi}(x,q,\rho) - \beta(\rho + x^2)\Big\} + O(\varepsilon) + o_{\operatorname{\mathbb{P}}}(1)\,,\tag{27}\] where \(o_{\operatorname{\mathbb{P}}}(1) \to 0\) in probability in the limit \(d\to \infty\) and \(n/d \to \alpha\), and \[\begin{align} \label{eq:phi95master95rho} \bar{\Phi}(x,q,\rho) &:= \alpha \operatorname{\mathbb{E}}\log \operatorname{\mathbb{E}}_{W} \exp u\Big( x S + \sqrt{q}Z + \sqrt{\rho-q} W \Big) + \frac{1}{2} \frac{q}{\rho-q} + \frac{1}{2} \log\big(\rho-q\big) \,, \end{align}\tag{28}\] This is the content of Appendix 6. Central to the successful application of this technique are 1) strong concentration of measure statements of the interpolating Gibbs measures and 2) uniqueness of the solution to the system of Replica-Symmetric (RS) equations Eq.(40 ). We demonstrate these in Appendix 9.3 and Appendix 10 respectively.

The unique minimizers \((q_\star,\rho_\star)\) of the formula in 27 are respectively the asymptotic values of \[\operatorname{\mathbb{E}}\Big[\operatorname{\mathbb{E}}_{(\theta^1,\theta^2) \sim \mu_\beta \times \mu_\beta} \big[\langle \bar{\theta}^1, \bar{\theta}^2\rangle /d\big]\Big]\,,~~~~ and~~~~ \operatorname{\mathbb{E}}\Big[\operatorname{\mathbb{E}}_{\theta \sim \mu_\beta} \big[\|\bar{\theta}\|^2/d\big]\Big]\,,\] where \(\bar{\theta} = (\theta_2,\cdots,\theta_d)\) omits the first coordinate of \(\theta\), and similarly for \(\bar{\theta}^1, \bar{\theta}^2\).

We remark that in the Bayesian setting with data generated from \(\mathcal{D}_{\mathrm{\small \tiny GMM}}\) we have \(u(x) = \sqrt{\lambda} x\) which allows for explicit computations of the log-partition function via a contour integral, and one can obtain the desired formula without resorting to these techniques. Nevertheless we do not pursue this and provide a unified treatment here.

5.2 Turning off the mollification↩︎

To obtain an asymptotic expression for the area of the set of interpolators with fixed overlap with the signal direction, \(S_{\kappa}(X,y) \cap \{|\langle\theta,\theta_\star\rangle/d - x|\le \varepsilon\}\), we turn off the mollification \(\exp u(x)\) appearing in 26 and 28 into a hard step function \(\mathbf{1}\{ x \ge \kappa\}\), under the Gaussian reference measure, and then convert back to the spherical setting. Regarding the first step, showing that the desired statement 27 survives this passage to a hard step function is done by adding one constraint at a time. (Note the \(i\)-th datapoint imposes the constraint \(\langle g_i, \theta \rangle \ge \kappa \sqrt{d}\) on the set of possible interpolators \(\theta \in \mathbb{S}^{d-1}(\sqrt{d})\), and henceforth we refer to the datapoints also as constraints.) Let \[\begin{align} \label{eq:Ui95init95def} U_i = \big\{\theta \in \mathbb{S}^{d-1}(\sqrt{d}): \langle g_i,\theta\rangle \ge \kappa \sqrt{d} \big\}\,, \end{align}\tag{29}\] and \[\label{eq:a95m} a_m = \frac{1}{d}\operatorname{\mathbb{E}}\log \int_{\bigcap_{i < m} U_i} \mathbf{1}\big\{|\theta_1/\sqrt{d} -x | \le \varepsilon\big\} \exp \left(\sum_{i=m}^n u\big(\langle g_i ,\theta \rangle / \sqrt{d}\big) -\beta \|\theta\|^2\right) \mathrm{d}\theta\,,~~~ m \le n\,.\tag{30}\] We want to estimate the difference \(a_{m+1} - a_m\) which can be written as \[\label{eq:difference} a_{m+1} - a_m = \frac{1}{d}\operatorname{\mathbb{E}}\log G_{m}(U_{m}) - \frac{1}{d}\operatorname{\mathbb{E}}\log G_{m}\big(e^{u(\langle g_m ,\theta \rangle / \sqrt{d})}\big)\,,\tag{31}\] where \(G_m\) is the measure with density proportional to \[\mathbf{1}\Big\{\theta \in \bigcap_{i<m} U_i,\, |\theta_1/\sqrt{d}-x|\le \varepsilon\Big\}\, \exp\left(\sum_{i>m}u(\langle g_i,\theta\rangle / \sqrt{d}) - \beta \|\theta\|^2\right)\,,\] which does not involve the \(m\)-th constraint. If \(\exp u\) approximates the step function to accuracy \(\varepsilon'\) then we can hope to establish \(|a_{m+1}-a_m | \le \varepsilon'/d\), then sum over \(m \in [n]\). The main difficulty is that \(G_m(U_m)\) may apriori be too small compared to the second term in 31 ; for instance the additional constraint \(U_m\) may have an empty intersection with \(\cap_{i<m}U_i\). Talagrand’s approach is to truncate the logarithm in the definition of \(a_m\), Eq. 30 to a minimum floor value \(e^{-cd}\), \(c>0\), and control the probability that \(G_m(U_m)\) falls below this threshold. We will show that \(G_m(U_m)\) is very unlikely to be exponentially small by extracting an exponential number of nearly orthogonal directions in \(\cap_{i<m}U_i\), conditional on this set being large (this is provided by the truncation), and show that the fresh constraint \(U_m\) has a small probability of being violated by all these directions simultaneously. This is a geometric argument executed via the tools of Gaussian processes. A minor adaptation is needed in our case to handle the non-Gaussian, but still strongly log-concave, first coordinate. This argument will also be used to establish concentration of the logarithms of the relevant partition functions, and is executed in Appendix 7. We point out a version of this argument in [32] which handles arbitrary i.i.d.sub-Gaussian vectors \(g_i\), at the price of a suboptimal concentration rate that scales like a fractional power of \(d\).

5.3 Conversion to the spherical reference measure↩︎

We convert back from the Gaussian measure to the spherical measure by exploiting the concentration of \(\bar{\theta}\) on a thin shell of width \(o(\sqrt{d})\) around a sphere of radius approximately \(\sqrt{\rho_\star d}\) when \(\theta \sim \mu_{\beta}\). The parameter \(\beta\) is then chosen to satisfy the unit radius condition \(x^2 + \rho_\star = 1\). A formula for \((1/d)\log Z\), Eq. 25 can then be obtained from 27 via a volume-to-surface comparison argument. This eliminates the parameters \(\beta\) and \(\rho\) from the equation 28 , leading to a variational formula with \(q\) as the only parameter. The overlap constraint on the first coordinate can be eliminated by taking a maximum over \(x\), resulting in the ‘max-min’ structure of the variational formula. This allows us to finish the proof of the large deviation result for the posterior distributions in the Bayesian setting (in Section 3.2) since the function \(u\) already satisfies the required smoothness properties. To obtain the LDP for uniform measure on the set of interpolators (in Section 3.1) we apply this argument after the mollification has been turned off. This is the content of Appendix 8; see Theorems 22 and 23. This completes the proof of Theorems 1 and 4.

5.3.0.1 Statement on use of AI:

The authors used ChatGPT 5.1 to produce the code used for the numerical simulations presented in Section 3.3. The authors instructed the AI to write Julia code for the Monte Carlo experiment and the numerical solvers for the fixed point equations in \((x,q)\) appearing in Section 3. The code was thoroughly checked by the authors. The authors used ChatGPT 5.5 and Gemini 3.1 and 3.5 to establish Part [it:part2] in the proof of Propositions 2, 3, 5, 6, in writing the fixed point argument for the map \(T_\alpha\), Eq. 286 , in the proof of Lemma 1, and to prove Proposition 14 and Lemma 24.

5.3.0.2 Acknowledgements:

AC would like to thank Shuangping Li for stimulating discussions. AE was supported by the National Science Foundation grant DMS-2450867.

6 Computing the expected log-partition function↩︎

Recall the definition of \(Z_{\beta}\) from 26. The goal of this section is to compute the free energy – the expected log-partition function \((1/d) \operatorname{\mathbb{E}}\log Z_{\beta}\) – in the asymptotic regime \(d \rightarrow \infty, \frac{n}{d}\rightarrow \alpha > 0\) for \(\alpha \le \alpha_0\), where \(\alpha_0\) is defined in 37. Our expression depends on the solution to an explicit two-variable system of equations known as the Replica-Symmetric (RS) equations, defined in 40. Our precise results for the free energy are then given in Theorems 7, 8.

6.0.0.1 Notation.

By rotational symmetry, we assume without loss of generality that \(\theta_\star = \sqrt{d} e_1\) as per Section 5. We then let \(s_i=y_i X_{i1}\) for \(1 \le i \le n\), the component of \(y_i X_i\) in the span of \(\theta_\star\). Letting \(\mathcal{D}\) denote the density of the \(s_i\), we impose the following technical assumption on \(\mathcal{D}\) which is satisfied when \(\mathcal{D}\in \{\mathcal{D}_{\mathrm{\small \tiny Logistic}}, \mathcal{D}_{\mathrm{\small \tiny GMM}}\}\).

Note \(\beta_{\mathrm{\small signal}}\), \(K_{\mathrm{\small signal}}\) depend only on \(\lambda\) (and the link function \(\varphi\) when \(\mathcal{D}\equiv \mathcal{D}_{\mathrm{\small \tiny Logistic}}\), which we suppress for notational simplicity). We let \(\varphi_{0}\) denote the PDF of a standard univariate normal \(N(0,1)\), and let \(\varphi_{1}\) denote the PDF of \(S \sim \mathcal{D}\).

We now formally define the quantities we are interested in understanding. Following the notation in Section 5, for any \(\theta\in\mathbb{R}^d\), \(\bar\theta = (\theta_2, \ldots, \theta_d)\) omits its first coordinate. For all \(1 \le i \le n\), we let \[\begin{align} \label{eq:Si95def} S_i = S_i(\theta) := \frac{1}{\sqrt{d}}\Big( s_i \theta_1 + \langle g_i, \bar \theta \rangle \Big)\,, \end{align}\tag{32}\] where \(s_i \sim \mathcal{D}\), \(g_i \sim N(0, I_{d-1})\) are i.i.d., and where \(g_{i,j}\) denotes the \(j-1\)-st coordinate of \(g_i\). Hence we consider \(2 \le j \le d\). This notation is not to be confused with the definition of \(g_i\) in Section 5, and for the rest of this paper, we define \(g_i \sim N(0, I_{d-1})\).

Next, for an arbitrary function \(u:\mathbb{R}\rightarrow \mathbb{R}\) such that the following integrals 34, 35 exist, we define the Hamiltonian \[\begin{align} H(\theta) = H_{n, d}(\theta) := \sum_{1 \le i\le n} u(S_i) \,.\label{eq:pfs95hamiltonian95def} \end{align}\tag{33}\] Dependence on \(u(\cdot)\) is suppressed here in Appendix 6 and will always be clear from context. Since \(\theta_{\star} = \sqrt{d} e_1\), \(s_1 \theta_1 + \langle g_i, \bar{\theta}\rangle = y_i \langle X_i, \theta \rangle\). Thus 33 is identical in law to \(\sum_{i=1}^n u\big(\langle y_i X_i \rangle/\sqrt{d}\big)\). Finally, for any \(\beta>0\) and any interval \(I \subseteq \mathbb{R}\), we define the restricted quantities \[\begin{align} Z_{\beta}(I) &= Z_{\beta, n, d}(I) := \int \mathbf{1}\{\theta_1/\sqrt{d} \in I\} \, \exp\Big( H_{n, d}(\theta) - \beta\|\theta\|^2 \Big) \, \mathrm{d}\theta\,, \tag{34}\\ \phi_{\beta}(I) &= \phi_{\beta, n, d}(I) := \frac{1}{d}\operatorname{\mathbb{E}}\log Z_{\beta, n, d}(I)\,. \tag{35} \end{align}\] In the above definitions, we omit dependence on \(n, d\) when they are clear from context.

We are now in position to state the main results of this section, regarding the free energy of the interpolators and posterior respectively. For the interpolators, our result applies for \(u(\cdot)\) such that \(\exp u(x)\) is as a sufficiently accurate approximation to \(\mathbf{1}\{x \ge \kappa\}\).

For the posterior, \(u(\cdot)\) is now fixed based on the assumed data generation process; our result applies for \(u(\cdot)\) from 17 in the GMM case or 18 in the logistic case.

In both Theorems, \(\mathrm{\small RSG}_I\) is well-defined thanks to Proposition 9. Also, note that \(d\) does not need to be large enough in terms of \(\alpha_0\). This is because we apply the bound \(\alpha_0\le 2\) in the bounds arising in the following proofs, and hence dependence on \(\alpha_0\) in \(d\) is captured by a universal constant. We now define \(\alpha_0\) and \(\mathrm{\small RSG}_I\) that appear in the above Theorems.

Defining \(\alpha_0\): For both the interpolators and the posterior, we let \[\begin{align} \beta_0 = \frac{1}{8}\, , \beta_1 = 10\, ,C_{\mathrm{\small sol}}= \max\Big\{ \frac{1}{\beta_0}, 4\beta_1 \Big\}+1\,.\label{eq:csoldef} \end{align}\tag{36}\] For the interpolators, we now consider \(\bar \alpha_0, c_0 \in (0, 2]\) small enough in terms of \(\beta_0, C_{\mathrm{\small sol}}, \lambda\), and define \[\begin{align} \alpha_0= \alpha_0(\lambda, \kappa_+) := \begin{cases} \bar \alpha_0 &: \kappa< 0\,, \\ \frac{c_0}{\kappa^2+1} &: \kappa\ge 0 \,. \end{cases}\label{eq:alpha0def} \end{align}\tag{37}\] For the posterior, consider \(u(\cdot)\) from 17 in the GMM case or 18 in the logistic case. In both cases, note \(|u^{(l)}| \le D = D(\lambda)\) for \(l=1,2,3,4\). We let \(C_{\mathrm{\small sol}}\) be large enough in terms of \(D, \lambda\). Our results now apply for \(\alpha_0\in (0,2]\) small enough in terms of \(\beta_0, \beta_1, D, C_{\mathrm{\small sol}}\), and therefore small enough in terms of \(\beta_0, \beta_1, \lambda\).

Defining \(\mathrm{\small RSG}\) and the RS equations: We now define \(\mathrm{\small RSG}\). To do so, we must define the Replica-Symmetric (RS) equations. Let \(S \sim \mathcal{D}\), \(Z, W \sim N(0,1)\) be independent. Recall the definition of \(\bar\Phi(x,q,\rho)\) for any \(0 \le q < \rho\) and \(x \in \mathbb{R}\) from 28. In what follows consider \(\bar\Phi(x,q,\rho)\) with \(u(x)\) therein given by \(\exp u(x) = \mathbf{1}\{x \ge \kappa\}\) for the interpolators, and given by \(u(\cdot)\) from 17 in the GMM case or 18 in the logistic case for the posterior. In turn, for all such \((x, q, \rho)\) and any interval \(I \subseteq \mathbb{R}\) we define \[\label{eq:Fqrhodef} \begin{align} F_I(x,q,\rho) &:= \bar\Phi(x, q, \rho) - \beta \big(\rho + r_I(x)\big)\, \\ &= \alpha \operatorname{\mathbb{E}}\log \operatorname{\mathbb{E}}_{W} \exp u\big( x S+ \sqrt{q} Z+ \sqrt{\rho-q} W\big) + \frac{1}{2} \frac{q}{\rho-q} + \frac{1}{2} \log\big(\rho-q\big) \\ &\qquad \qquad - \beta \big(\rho + r_I(x)\big)\,, \end{align}\tag{38}\] where \[\begin{align} \label{eq:intervalrxdef} r_I(x) &:= \begin{cases} 0 &: 0 \in I\,, \\ x^2 &: 0 \not\in I\,.\end{cases} \end{align}\tag{39}\] and where dependence on \(\alpha, \beta\) is implicit in the definition of \(F\). Fixing \(x \in [-1,1]\) and \(I\), we define the RS equations by \[\begin{align} \frac{\partial F_I}{\partial q} = \frac{\partial F_I}{\partial \rho}=0\, .\label{eq:niceRSeqs} \end{align}\tag{40}\] We will establish in Appendix 10.2 the following crucial property of the system 40, which applies for both the interpolators and posterior.

Define in terms of \(F_I\) the following quantities, which implicitly depend on \(u(\cdot)\): \[\begin{align} \mathrm{\small RS}_{0, I}(\alpha, \beta, x) &:= F_I\big(x, q_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big)\,,\tag{41}\\ \mathrm{\small RSG}_I(\alpha, \beta, x) &:= \mathrm{\small RS}_{0, I}(\alpha , \beta, x) + \frac{1}{2} \log(2\pi e) \,.\tag{42} \end{align}\]

Theorems 7 and 8 are proven with a unified strategy that uses a Gaussian interpolation argument. This argument proceeds by understanding the expected contribution of adding each datapoint or constraint \(i\) on the free energy \((1/d) \operatorname{\mathbb{E}}\log Z_{\beta}\) for each \(1 \le i \le n\). See Proposition 10. The free energy then can be written as a sum of such expected contributions.

This interpolation argument is carried out in Appendix 6.1. We then show in Appendix 6.2 that under the conditions on \(u(x)\) in Theorem 7, we can replace \(u(x)\) by \(\mathbf{1}\{x \ge \kappa\}\) only changes the the free energy by at most \(\varepsilon\). This yields an expression that does not depend on \(u(\cdot)\) and depends explicitly on the solution to the RS equations. Finally, we sum these expressions across all the datapoints \(i, 1 \le i \le n\) and finish the proof of Theorem 7 for the interpolators and Theorem 8 in Appendix 6.3 and Appendix 6.4 respectively.

Crucial to executing this proof strategy is Proposition 9 – that the RS equations have a unique solution. This is done by showing that the RS equations satisfy a particular convex-concave structure. Establishing this with the signal in the data and the case \(\kappa< 0\) does not directly follow from the arguments of Talagrand in [25]; we discuss our steps to handle these complications in Appendix 10.

6.1 Interpolating each datapoint via cavity in \(n\)↩︎

Here in Appendix 6.1, we fix any \(d\ge 1\) and \(n\) such that \(1 \le n\le \alpha_0d\), and define \(\alpha = \frac{n}{d}\). To compute the free energy \(\phi_{\beta, n, d}(I)\), we consider two interpolations. One interpolation is over a parameter \(v, 0 \le v \le 1\), and aims to elucidate the effect of the \(n\)-th datapoint or constraint on the original probability distribution. When \(v=1\), the \(n\)-th datapoint is fully present, and when \(v=0\), it is eliminated. Hence this interpolation is called ‘cavity in \(n\)’. The other interpolation is over a parameter \(t, 0 \le t \le 1\), and aims to elucidate the effect of the \(d\)-th coordinate. When \(t=1\), the \(d\)-th coordinate is fully present, and when \(t=0\), it is eliminated. Hence this interpolation is called ‘cavity in \(d\)’.

Specifically, the cavity in \(n\) provides us with an approximate expression for \(\phi_{\beta, n, d}(I) - \phi_{\beta, n-1, d}(I)\). This expression depends on the mollifier \(u(\cdot)\) and the overlaps \(q_{n,d}, \rho_{n,d}\) given in 47; see Proposition 10. Establishing this result is the main goal of Appendix 6.1. However to define the cavity in \(n\), we will first need to define the cavity in \(d\). We will then use the cavity in \(d\) more extensively next in Appendix 6.2 to relate \(q_{n,d}, \rho_{n,d}\) in the expression from Proposition 10 to \(q_0, \rho_0\) from Proposition 9, and eliminate \(u(\cdot)\) in the case of the interpolators. This lets us rewrite the aforementioned expression for \(\phi_{\beta, n, d}(I) - \phi_{\beta, n-1, d}(I)\) in terms of \(\mathrm{\small RSG}_I\).

Finally, we note that many of our following bounds do not explicitly depend on \(\alpha_0\); this is because we use the upper bound \(\alpha_0\le 2\).

6.1.0.1 Cavity in \(d\):

To define the cavity in \(n\) in its full generality, we must first set up the cavity in \(d\). For any \(1 \le i\le n\) and \(t \in [0,1]\), define \[\begin{align} S_{i, t} = S_{i, t}(\theta) := \frac{s_i\theta_1}{\sqrt{d}}+\frac{1}{\sqrt{d}} \sum_{2 \le j\le d-1} g_{i, j} \theta_j+ \sqrt{\frac{t}{d}} g_{i, d} \theta_d\,.\notag \end{align}\] In terms of \(S_{i, t}\), define \[\begin{align} H_{t, n, d}(\theta) := \sum_{1 \le i\le n} u\big(S_{i, t}(\theta) \big) + \theta_d\sqrt{(1-t)r} Y - \frac{(1-t)(r-\bar{r})}{2} \theta_d^2\,,\label{eq:interpolateinthamiltonian} \end{align}\tag{43}\] where \(r,\bar{r}\) will be chosen next in 51, 52, and where \(Y \sim N(0, 1)\). Let \(\langle \,\cdot\, \rangle_t\) denote the Gibbs average w.r.t. \[\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \, \exp\big( H_{t, n, d}(\theta) - \beta\| \theta\|^2 \big)\,,\] and let \[\begin{align} \label{eq:nu95t95def} \nu_t(\cdot) := \operatorname{\mathbb{E}}\langle \,\cdot\, \rangle_t\,. \end{align}\tag{44}\] When we write \(H_t\) without explicitly stating \(n\), we will assume this refers to \(H_{t,n,d}\) as written in 43. Now consider the overlaps \[\begin{align} \label{eq:overlap95defs95thispaper} R_{1,2} = \frac{1}{d} \langle \bar{\theta}^1,\bar{\theta}^2\rangle\,,\,R_{1,1} = \frac{1}{d}\|\bar{\theta}\|^2\,, \end{align}\tag{45}\] where we view \(R_{1, 1}\) as a function on \(\mathbb{R}^{d-1}\) and \(R_{1, 2}\) as a function on \((\mathbb{R}^{d-1})^2\). Let \[\begin{align} q_t := \nu_t(R_{1,2})\, \le\, \rho_t := \nu_t(R_{1,1}) \,.\label{eq:interpolationrhoqdefgeneralt} \end{align}\tag{46}\] Note \(\langle \,\cdot\, \rangle_1\) corresponds to exactly the Hamiltonian \(H_{n, d}(\theta) - \beta\| \theta\|^2\). Indeed, specializing to \(t=1\), we define \[\begin{align} q_{n, d} := q_1 \, ,\, \rho_{n, d} := \rho_1\,,\label{eq:interpolationrhoqdef} \end{align}\tag{47}\] Consequently \(q_{n, d} \le \rho_{n, d}\). Now consider independent \(Z, W\sim N(0, 1)\), and \(S\sim \mathcal{D}\) following the law of each \(s_i\). For arguments \(0 \le q < \rho\), define \[\begin{align} \label{eq:approxconstraint} \eta= \eta(q, \rho) := x S+ \sqrt{q}Z+ \sqrt{\rho - q}W\, . \end{align}\tag{48}\] We define the functions \[\begin{align} \psi_{\alpha}(q, \rho) &:= \alpha \operatorname{\mathbb{E}}\Big( \frac{\operatorname{\mathbb{E}}_{W} [ u'(\eta) \exp u(\eta) ] }{ \operatorname{\mathbb{E}}_{W}[ \exp u(\eta) ] } \Big)^2\, ,\tag{49}\\ \bar{\psi}_{\alpha}(q, \rho) &:= \alpha \operatorname{\mathbb{E}}\Big[ \frac{\operatorname{\mathbb{E}}_{W} [ (u''(\eta) + u'(\eta)^2) \exp u(\eta) ] }{ \operatorname{\mathbb{E}}_{W}[ \exp u(\eta) ] } \Big]\, .\tag{50} \end{align}\] In turn, we let \[\begin{align} r &= \psi_{\alpha}\big(q,\rho\big)=\alpha\operatorname{\mathbb{E}}\Bigg[ \Bigg( \frac{\operatorname{\mathbb{E}}_{W}\big[ u'(\eta)\exp u(\eta) \big]}{\operatorname{\mathbb{E}}_{W}\big[ \exp u(\eta)\big]} \Bigg)^2 \Bigg] = \frac{\alpha}{\rho-q} \operatorname{\mathbb{E}}\Bigg[ \Bigg( \frac{\operatorname{\mathbb{E}}_{W}\big[ W\exp u(\eta) \big]}{\operatorname{\mathbb{E}}_{W}\big[ \exp u(\eta) \big]} \Bigg)^2 \Bigg]\,,\tag{51} \\ \bar{r} &= \bar{\psi}_{\alpha} \big(q, \rho \big) = \alpha \operatorname{\mathbb{E}}\frac{\operatorname{\mathbb{E}}_{W}\big[ (u''(\eta) + u'(\eta)^2 ) \exp u(\eta)\big] }{\operatorname{\mathbb{E}}_{W}\big[ \exp u(\eta)\big]} = \frac{\alpha}{\rho - q} \operatorname{\mathbb{E}}\frac{\operatorname{\mathbb{E}}_{W}\big[ (W^2 - 1) \exp u(\eta)\big] }{\operatorname{\mathbb{E}}_{W}\big[ \exp u(\eta)\big]}\,,\tag{52} \end{align}\] where the second equality is only valid when \(\rho>q\). Here the equality follows by Gaussian Integration by Parts. As we will justify later in Lemma 41, we have \(r \ge \bar{r}\) (irrespective of whether \(\rho=q\) or \(\rho>q\)). As \(|u'|, |u''| \le D\) in both the interpolators and GMM case and as \(\alpha \le \alpha_0\le 2\), we have \(r, \bar{r} \le K(D)\), which we use repeatedly in the following. We also note \(r, \bar{r}\) are independent of \(\varepsilon''\).

6.1.0.2 Cavity in \(n\):

We next consider another interpolation parameter \(v \in [0,1]\). To set up the cavity in \(n\), we need to introduce the notion of replicas. Given a probability distribution \(\nu\), we consider \(L\) i.i.d. draws \(\theta^{\ell}, 1 \le \ell\le L\) from \(\nu\). These i.i.d. draws are known \(\theta^{\ell}\) are known as replicas. That is, \((\theta^{\ell})_{\ell=1}^L \sim \nu^{\otimes L}\). It is often useful to consider functions of \(L> 1\) replicas; one example is the overlap \(R_{1,2} = \frac{1}{d} \langle \bar\theta^1, \bar\theta^2 \rangle\). In particular, functions of \(L> 1\) replicas naturally arise when differentiating quantities of interest such as \(R_{1,1}\) and \(R_{1,2}\) with respect to \(t\) and \(v\) in the cavity in \(d\) and \(n\).

Proceeding with the setup, we let \(Z\) and \(W^{\ell}\) denote i.i.d. \(N(0, 1)\) scalars independent of everything else for each replica \(\ell\), \(1 \le \ell\le L\). For \(v \in [0,1]\), define for each replica \(\ell\), \(1 \le \ell\le L\), \[\begin{align} S_{n, t, v}^\ell= S_v^\ell&:= \sqrt{v} \Big(\frac{1}{\sqrt{d}} \sum_{2 \le j\le d-1} g_{n, j} \theta^{\ell}_{j} + \sqrt{\frac{t}{d}} g_{n, d} \theta^{\ell}_{d} \Big) + \sqrt{1-v} \big( \sqrt{q_{n, d}} Z+ \sqrt{\rho_{n, d} -q_{n, d}} W^\ell\big) \notag \\ &\qquad \qquad + s_n\Big(v\frac{\theta^\ell_1}{\sqrt{d}} + (1-v) x \Big) \,.\notag \end{align}\] Note that in the following when we consider \(S_{n, t, v}^\ell\), \(t\) will be always held fixed. When it is clear from context we will just write \(S_{v}^\ell\). Note \(S_{n, t, 1}^\ell= S_{n, t}^\ell\).

Next, we let \(\langle\, \cdot\, \rangle_{t, \sim}\) denote a Gibbs measure defined by \[\begin{align} \langle f \rangle_{t, \sim} &:= \frac{1}{Z_{t,n-1,d}^L} \int \operatorname{\mathbb{E}}_{W} \Bigg[ f\, \prod_{1 \le \ell\le L} \mathbf{1}\{\theta^{\ell}_1/\sqrt{d} \in I\} \exp\big( H_{t, n-1, d}(\theta^{\ell}) - \beta\| \theta^{\ell} \|^2 \big) \Bigg]\, \mathrm{d}\theta^1 \cdots \mathrm{d}\theta^L\label{eq:interpolationtildemeasure} \end{align}\tag{53}\] for \(f\) a function of \(L\) replicas and the corresponding annealed disorder \(W^{\ell}\), where we define: \[\begin{align} Z_{t,n-1,d}&:= \int \mathbf{1}\{\theta_1/\sqrt{d} \in I\} \exp\big( H_{t, n-1, d}(\theta) - \beta\| \theta\|^2 \big) \, \mathrm{d}\theta\,,\notag \\ H_{t, n-1, d}(\theta) &:= \sum_{1 \le i\le n-1} u(S_{i, t}(\theta)) + \theta_d\sqrt{(1-t)r} Y - \frac{(1-t)(r-\bar{r})}{2} \theta_{d}^2\,. \end{align}\] (Note for a fixed value of \(L\), if \(f\) is a function of \(L+1\) replicas, the Gibbs measure 53 will use \(\ell+1\) replicas \(\ell=1, \ldots, \ell, \ell+1\).) Now let \[\begin{align} \label{eq:nu95t95v95def} \nu_{t, v}(f) := \operatorname{\mathbb{E}}\frac{\big\langle f \exp \big( \sum_{1 \le \ell\le L} u(S_v^\ell) \big) \big\rangle_{t, \sim} }{\big\langle \exp u(S_v^1)\big\rangle_{t, \sim}^L} = \operatorname{\mathbb{E}}\frac{\big\langle f \exp \big( \sum_{1 \le \ell\le L} u(S_{n, t, v}^\ell) \big) \big\rangle_{t, \sim} }{ \big\langle \exp u(S_{n, t, v}^{L+1})\big\rangle_{t, \sim}^L}\,. \end{align}\tag{54}\] Observe that \(\nu_{t} \equiv \nu_{t,1}\). We will establish that as one datapoint is removed, the resulting difference in the free energy approximately equals the following expression:

To prove Proposition 10, we will need to establish the following. First, in Appendix 9.1, we will show the following critical Lemma, which lets us transfer expectations from \(\nu_{t, v}\) to \(\nu_{t, 1}\).

We will apply the above for \(f=|R_{1, 1}-\rho_{n, d}|, |R_{1,2}-q_{n, d}|\), and thus are left with the task of controlling \(\nu_{t, 1}\big( |R_{1, 1}-\rho_{n, d}| \big), \nu_{t, 1}\big( |R_{1, 2}-q_{n, d}| \big)\) that appear on the right hand side of the above Lemma. To this end, we will also establish the following via concentration of Lipschitz functions of log-concave measures in Appendix 9.3.

We also cite a simple fact to bound higher order moments of relevant random variables:

Now we have the necessary tools to prove Proposition 10.

6.2 Simplifying the expression from cavity in \(n\)↩︎

Again let \(\alpha = n/d\), and let \(\psi_{\alpha}, \bar{\psi}_{\alpha}\) be defined in terms of \(\alpha\) as per 49, 50. Our goal here in Appendix 6.2 is to show that the expression from Proposition 10, specifically \[\begin{align} \label{eq:interpolate95oneattime95expression} \frac{1}{d} \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( x s_n+ \sqrt{q_{n, d}} Z+ \sqrt{\rho_{n, d}-q_{n, d}}W\big) \Big]\,, \end{align}\tag{55}\] is very close to \(\mathrm{\small RSG}_I\). The difference between 55 and \(\mathrm{\small RSG}_I\) is that \(\mathrm{\small RSG}_I\) instead depends on \(\rho_0, q_0\), and additionally for the interpolators, the mollifier \(u(\cdot)\) in 55 is replaced by the hard step function \(\mathbf{1}\{x \ge \kappa\}\) in \(\mathrm{\small RSG}_I\).

Here we will do the work in this argument that is common to the proof for the interpolators and posterior, specifically Propositions 12, 13, 14. The additional work for the interpolators that is needed to replace the mollifier \(u(\cdot)\) in 55 by the hard step function \(\mathbf{1}\{x \ge \kappa\}\) in \(\mathrm{\small RSG}_I\) is done in Propositions 16 and 15, presented later in Appendix 6.3.

Beginning with the argument, consider the following system of four variables and four equations: \[\begin{align} r = \psi_{\alpha}(q, \rho)\, ,\, \bar{r} = \bar{\psi}_{\alpha}(q, \rho)\, ,\, \rho = \frac{1}{2\beta+r-\bar{r}} + \frac{r}{(2\beta+r-\bar{r})^2}\, ,\, q = \frac{r}{(2\beta+r-\bar{r})^2}\, .\label{eq:realRSequations} \end{align}\tag{56}\] We will establish that \(\rho_{n, d}, q_{n, d}\) approximately satisfy 56. This is where we use the careful choice of \(r, \bar{r}\) in terms of \(\psi_{\alpha}, \bar{\psi}_{\alpha}\) from 51, 52, which lets us complete the cavity in \(n\) argument. In particular, in Appendix 9.2, we will complete the cavity in \(n\) and also execute the cavity in \(d\) to establish the following.

With Lemma 4 in hand, we now establish:

In Appendix 10.1, we will establish:

We will use Proposition 12 and 13 to establish the following.

Note this argument is where we use that \(|\delta_1|, |\delta_2|\) from ?? are upper bounded independently of \(\alpha\). In particular this lets us take \(\varepsilon''_{\mathrm{\ref{prop:boundedapproxRSeq}}}=\varepsilon''_{\mathrm{\ref{prop:boundedapproxRSeq}}}(u, \beta_0, \beta_1, \lambda)\) independently of \(\alpha\), which is crucial as we will use the same \(\varepsilon''\) across \(n=1, 2, \ldots, d\) when computing the expected free energy. The compactness supplied from the above Proposition is crucial in the arguments to follow in Propositions 16 and 15.

The above work lets us interpolate one datapoint at a time and compute the difference in free energy, as we do in Appendix 6.3. The last step we need is to compute \(\phi_{\beta, 0, d}(I)\), which is the base case arising when all \(n\) datapoints have been accounted for.

6.3 Proof of Theorem 7 for interpolators↩︎

We now complete the proof of Theorem 7 by summing Proposition 10 and the results of Appendix 6.2 across all datapoints \(i\), \(1 \le i \le n\). We first handle the necessary steps to replace the mollifier \(u(\cdot)\) in 55 by the hard step function \(\mathbf{1}\{x \ge \kappa\}\) in \(\mathrm{\small RSG}_I\). Specifically, this is done in the following Propositions 15 and 16, which establish that the impact of the mollifier \(u(\cdot)\) is insignificant. At a high level, this is because the conditions of Theorem 7 imply \(u(\cdot)\) is an accurate approximation to \(\mathbf{1}\{x \ge \kappa\}\).

We next use the uniqueness of the solution \((q_0, \rho_0)\) to 40, given by Proposition 9, to control the difference of \((q_{n,d}, \rho_{n,d})\) vs. \((q_0, \rho_0)\).

We now complete the proof of Theorem 7. As \(C_{\mathrm{\small sol}}\) only depends on \(\beta_0, \beta_1\), we may let \(H_1=H_1(\beta_0, \beta_1, \kappa, \lambda)\) denote an upper bound on the norm of the gradient of the \(C^\infty\) function \(\operatorname{\mathbb{E}}\big[ \log \operatorname{\mathbb{P}}_{W}\big(xS+ \sqrt{q}Z+ \sqrt{\rho-q}W\ge \kappa\big) \big]\) over the compact set \(\big\{ (x, \rho, q) : -1 \le x \le 1, 0 \le q \le C_{\mathrm{\small sol}}, \frac{1}{C_{\mathrm{\small sol}}} \le \rho \le C_{\mathrm{\small sol}}, \frac{1}{\rho-q} \le C_{\mathrm{\small sol}}\big\}\). Here the function is \(C^\infty\) in this compact domain as \(\rho-q \ge \frac{1}{C_{\mathrm{\small sol}}}\). Dependence on \(\lambda\) arises as the law of \(S\) depends on \(\lambda\). Without loss of generality suppose \(H_1 \ge 1\).

By Proposition 9, we may also let \(H_2=H_2(\beta_0, \beta_1, \kappa, \lambda)\) be an upper bound on the gradient of the \(C^\infty\) function \(\operatorname{\mathbb{E}}\big[ \log \operatorname{\mathbb{P}}_{W} \big( xS+ \sqrt{q_0(\alpha, \beta, x)}Z+ \sqrt{\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) }W\ge \kappa\big) \big]\) on \((\alpha, \beta, x) \in [0,\alpha_0]\times [\beta_0, \beta_1] \times [-1,1]\). Here the function is \(C^\infty\) in this compact domain as \(\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) \ge \frac{1}{2C_{\mathrm{\small sol}}}\) by Proposition 9.

Now, we let \[\begin{align} \delta = \delta(\varepsilon, \beta_0, \beta_1, \kappa, \lambda) & := \frac{\varepsilon}{12H_1}\,, \\ \varepsilon' = \varepsilon'(\varepsilon, \beta_0, \beta_1, \kappa, \lambda) &:= \min\Big\{ \varepsilon'_{\mathrm{\ref{prop:mollifiererror}}}(\delta, C_{\mathrm{\small sol}}, \kappa^+, \lambda ), \varepsilon'_{\mathrm{\ref{prop:diffvsuniquesol}}}(\delta) \Big\}\,, \\ \varepsilon_{\mathrm{\small RS}_0} = \varepsilon_{\mathrm{\small RS}_0}(\varepsilon, u, \beta_0, \beta_1, \kappa, \lambda) &:= \min\Big\{ \varepsilon''_{\mathrm{\ref{prop:boundedapproxRSeq}}}(u, \beta_0, \beta_1, \lambda), \frac{\varepsilon}{12 K_{\mathrm{\ref{prop:interpolationperconstraint}}}(D, \beta_0, \beta_1, \kappa, \lambda)}, \varepsilon''_{\mathrm{\ref{lem:interpolationlastcalc}}}(\varepsilon/4) \Big\}\,. \end{align}\] Consider any \(0 < \varepsilon'' \le \varepsilon_{\mathrm{\small RS}_0}\) as in the statement of this Theorem. (Note dependence on \(\varepsilon'\) in \(\varepsilon_{\mathrm{\small RS}_0}\) comes implicitly through \(u\).) Finally we let \[\begin{align} d(\varepsilon, \varepsilon'', \beta_0, \beta_1, \kappa, \lambda) &:= \max\Big\{ d_{\mathrm{\ref{prop:boundedapproxRSeq}}}(\varepsilon''), \frac{12H_2}{\varepsilon}, d_{\mathrm{\ref{lem:interpolationlastcalc}}}(\varepsilon/4), d_{\mathrm{\ref{prop:interpolationperconstraint}}}(\varepsilon'') \Big\}\,. \end{align}\] Consider any \(d \ge d(\varepsilon, \varepsilon'', \beta_0, \beta_1, \kappa, \lambda)\) as in the statement of this Theorem. We now consider any \(n\) such that \(\frac{n}{d} \in [0, \alpha_0]\).

Next, we consider any \(1 \le i \le n\) and let \(\alpha = \frac{i}{d}\). In what follows, we apply the results from Appendices 6.1, 6.2 with \(i\) in place of \(n\). By Proposition 10 and as \(d \ge d_{\mathrm{\ref{prop:interpolationperconstraint}}}(\varepsilon'')\) and \(\varepsilon'' \le \frac{\varepsilon}{12K_{\mathrm{\ref{prop:interpolationperconstraint}}}(D, \beta_0, \beta_1, \kappa, \lambda)}\), we have \[\label{eq:interpolate95free95energy95finish1} \begin{align} &\Big| \phi_{\beta, i, d}(I) - \phi_{\beta, i-1, d}(I) - \frac{1}{d} \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( x s_i + \sqrt{q_{i, d}} Z+ \sqrt{\rho_{i, d}-q_{i, d}}W\big) \Big] \Big| \\ &\quad \le \frac{K_{\mathrm{\ref{prop:interpolationperconstraint}}}(D, \beta_0, \beta_1, \kappa, \lambda)}{d} \varepsilon'' \le \frac{\varepsilon}{12d}\,. \end{align}\tag{65}\] By Proposition 14, as \(\varepsilon'' \le \varepsilon''_{\mathrm{\ref{prop:boundedapproxRSeq}}}(u, \beta_0, \beta_1, \lambda)\) and \(d \ge d_{\mathrm{\ref{prop:boundedapproxRSeq}}}(\varepsilon'')\), we have \[\begin{align} \big( q_{i, d}, \rho_{i, d} \big) \in [0, C_{\mathrm{\small sol}}] \times \Big[ \frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}\Big]\,,\, \frac{1}{\rho_{i,d} - q_{i,d}} \le C_{\mathrm{\small sol}}\,. \end{align}\] Consequently by Proposition 15, as \(\varepsilon' \le \varepsilon'_{\mathrm{\ref{prop:mollifiererror}}}(\delta, C_{\mathrm{\small sol}}, \kappa^+, \lambda)\) and \(s_i \sim \mathcal{D}\), \[\label{eq:interpolate95free95energy95finish2} \begin{align} &\Big| \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( xs_i + \sqrt{q_{i, d}}Z+ \sqrt{\rho_{i, d}-q_{i, d}}W\big) \Big] \\ &\qquad \qquad \qquad - \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{P}}_{W} \big( xs_i + \sqrt{q_{i, d}}Z+ \sqrt{\rho_{i, d}-q_{i, d}}W\ge \kappa\big) \Big] \Big| \le \delta \le \frac{\varepsilon}{12}\, . \end{align}\tag{66}\] Next, by Proposition 16, we have \[\begin{align} \big| q_{i,d} - q_0(\alpha, \beta, x) \big|\,,\,\big|\rho_{i,d} - \rho_0(\alpha, \beta, x)\big| \le \delta = \frac{\varepsilon}{12H_1}\,. \end{align}\] Consequently \[\label{eq:interpolate95free95energy95finish3} \begin{align} &\Big| \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{P}}_{W} \big( xs_i + \sqrt{q_{i, d}}Z+ \sqrt{\rho_{i, d}-q_{i, d}}W\ge \kappa\big) \Big] \\ &\qquad \qquad - \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{P}}_{W} \big( xs_i + \sqrt{q_0(\alpha, \beta, x)}Z+ \sqrt{\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) }W\ge \kappa\big) \Big] \Big| \\ &\quad \le \frac{\varepsilon\sqrt{2}}{12H_1} \cdot H_1 < \frac{\varepsilon}{8}\,. \end{align}\tag{67}\] Finally, observe that for any \(\alpha' \in \big[\frac{i-1}{d}, \frac{i}{d} \big]\), \(\big|\alpha - \alpha'\big| \le \frac{1}{d}\), so as \(d \ge 12H_2/\varepsilon\) we have \[\label{eq:interpolate95free95energy95finish4} \begin{align} &\Big| \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{P}}_{W} \big( xs_i + \sqrt{q_0(\alpha, \beta, x)}Z+ \sqrt{\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) }W\ge \kappa\big) \Big] \\ &\qquad \qquad - \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{P}}_{W} \big( xs_i + \sqrt{q_0(\alpha', \beta, x)}Z+ \sqrt{\rho_0(\alpha', \beta, x) - q_0(\alpha', \beta, x) }W\ge \kappa\big) \Big] \Big| \\ &\quad \le H_2 \cdot \frac{1}{d} \le \frac{\varepsilon}{12}\,. \end{align}\tag{68}\] By Proposition 9, as \(\beta, x, I\) are fixed, we may consider \(\frac{\mathrm{d}}{\mathrm{d}\alpha} \mathrm{\small RS}_{0,I}(\alpha)\). Since \(\big(q_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big)\) solves \(\frac{\partial F_I}{\partial q} = \frac{\partial F_I}{\partial \rho}=0\), we have \[\begin{align} \frac{\mathrm{d}}{\mathrm{d}\alpha} \mathrm{\small RS}_{0,I}(\alpha) &= \frac{\partial F_I}{\partial \alpha} \big(x, q_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) \\ &\qquad \qquad + \frac{\partial F_I}{\partial q} \big(x, q_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) \cdot \frac{\partial}{\partial \alpha} q_0(\alpha, \beta, x) \\ &\qquad \qquad + \frac{\partial F_I}{\partial \rho} \big(x, q_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) \cdot \frac{\partial}{\partial \alpha} \rho_0(\alpha, \beta, x) \\ &=\operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{P}}_{W} \big( xs_i + \sqrt{q_0(\alpha, \beta, x)}Z+ \sqrt{\rho_0(\alpha) - q_0(\alpha, \beta, x) }W\ge \kappa\big) \Big]\,, \end{align}\] as \(s_i \sim \mathcal{D}\) and as independent of \(Z, W\). The Mean Value Theorem now implies that for some \(\alpha' \in \big[\frac{i-1}{d}, \frac{i}{d} \big]\), \[\label{eq:interpolate95free95energy95finish5} \begin{align} &\mathrm{\small RS}_0\Big(\frac{i}{d}\Big) - \mathrm{\small RS}_{0,I}\Big(\frac{i-1}{d}\Big) \\ &\quad = \frac{1}{d} \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{P}}_{W} \big( xs_i + \sqrt{q_0(\alpha', \beta, x)}Z+ \sqrt{\rho_0(\alpha') - q_0(\alpha', \beta, x) }W\ge \kappa\big) \Big]\,. \end{align}\tag{69}\] Combining 65, 66, 67, 68, 69 implies for all \(1 \le i \le n\), \[\begin{align} \Big| \phi_{\beta, i, d}(I) - \phi_{\beta, i-1, d}(I) - \Big( \mathrm{\small RS}_{0,I}\Big(\frac{i}{d}\Big) - \mathrm{\small RS}_{0,I}\Big(\frac{i-1}{d}\Big) \Big) \Big| < \frac{3\varepsilon}{8d}\,. \end{align}\] Summing across all such \(i\) and noting there are at most \(n \le \alpha_0d \le 2d\) such \(i\) yields \[\begin{align} \Big| \phi_{\beta, n, d}(I) - \phi_{\beta, 0, d}(I) - \Big( \mathrm{\small RS}_{0,I}\Big(\frac{n}{d}\Big) - \mathrm{\small RS}_{0,I}(0) \Big) \Big| < \frac{3\varepsilon}{4}\,. \end{align}\] Last, we combine with Lemma 5, yielding \[\begin{align} \Big| \phi_{\beta, n, d}(I) - \Big( \mathrm{\small RS}_{0,I}\Big(\frac{n}{d}\Big) + \frac{1}{2} \log(2\pi e) \Big) \Big| < \varepsilon\,. \end{align}\] This completes the proof of Theorem 7.

6.4 Proof of Theorem 8 for posterior↩︎

Here we prove Theorem 8 with the same argument as the proof of Theorem 7. Note \(u(x) \ge -D(\lambda)(1+|x|)\) for \(u(x)\) from 17, 18. Next, by the same argument as the proof of Proposition 16, we have the following for any \((\beta, x) \in [\beta_0, \beta_1] \times [-1, 1]\). For all \(\varepsilon'' \le \varepsilon''_{\mathrm{\ref{prop:boundedapproxRSeq}}}\), all \(d \ge d_{\mathrm{\ref{prop:boundedapproxRSeq}}}\), and all \(n \ge 1\) with \(n/d = \alpha\), \[\begin{align} \label{eq:posterior95diffvsuniquesol} \big| q_{n,d} - q_0(\alpha, \beta, x) \big|\, ,\, \big|\rho_{n,d} - \rho_0(\alpha, \beta, x) \big| \le \delta\,. \end{align}\tag{70}\] Here the proof follows by the same argument as the proof of Proposition 16, using Propositions 9, 12, and 14, but now we do not consider the \(u_k\) or replace \(u_k\) by \(\mathbf{1}\{x \ge \kappa\}\) as \(k \rightarrow \infty\). Here we use that a solution to 56 solves 40 where \(u(\cdot)\) is identical in both systems; this can be seen via Gaussian integration by parts.

Now to prove Theorem 7, we let \(H_1=H_1(\beta_0, \beta_1, \lambda)\) be an upper bound on the gradient of the continuously differentiable function \(\operatorname{\mathbb{E}}\big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big(xS+ \sqrt{q}Z+ \sqrt{\rho-q}W\big) \big]\) over the compact set \(\big\{ (x, \rho, q) : -1 \le x \le 1, 0 \le q \le C_{\mathrm{\small sol}}, \frac{1}{C_{\mathrm{\small sol}}} \le \rho \le C_{\mathrm{\small sol}}, \frac{1}{\rho-q} \le C_{\mathrm{\small sol}}\big\}\). Here we can verify that the function is continuously differentiable as \(\rho-q \ge \frac{1}{C_{\mathrm{\small sol}}}\), as \(u\) is twice differentiable, and as \(u(x) \ge -D(\lambda)(1+|x|)\). Without loss of generality suppose \(H_1 \ge 1\).

Similarly by Proposition 9, we may let \(H_2=H_2(\beta_0, \beta_1, \lambda)\) be an upper bound on the gradient of the continuously differentiable \(\operatorname{\mathbb{E}}\big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( xS+ \sqrt{q_0(\alpha, \beta, x)}Z+ \sqrt{\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) }W\big) \big]\) on \((\alpha, \beta, x) \in [0,\alpha_0]\times [\beta_0, \beta_1] \times [-1,1]\). Here we use that \(\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) \ge \frac{1}{2C_{\mathrm{\small sol}}}\) by Proposition 9. Now, we let \[\begin{align} \delta = \delta(\varepsilon, \beta_0, \beta_1, \lambda) &:= \frac{\varepsilon}{12H_1}\,, \\ \varepsilon_{\mathrm{\small RS}_0} = \varepsilon_{\mathrm{\small RS}_0}(u, \beta_0, \beta_1, \lambda) &:= \min\Big\{ \varepsilon''_{\mathrm{\ref{prop:boundedapproxRSeq}}}(u, \beta_0, \beta_1, \lambda), \frac{\varepsilon}{12 K_{\mathrm{\ref{prop:interpolationperconstraint}}}(D, \beta_0, \beta_1, \lambda)}, \varepsilon''_{\mathrm{\ref{lem:interpolationlastcalc}}}(\varepsilon/4) \Big\}\,. \end{align}\] Considering any \(0 < \varepsilon'' \le \varepsilon_{\mathrm{\small RS}_0}\) as in the statement of this Theorem, we let \[\begin{align} d(\varepsilon, \varepsilon'', \beta_0, \beta_1, \lambda) &:= \max\Big\{ d_{\mathrm{\ref{prop:boundedapproxRSeq}}}(\varepsilon''), \frac{12H_2}{\varepsilon}, d_{\mathrm{\ref{lem:interpolationlastcalc}}}(\varepsilon/4), d_{\mathrm{\ref{prop:interpolationperconstraint}}}(\varepsilon'') \Big\}\,. \end{align}\] Consider any \(d \ge d(\varepsilon, \varepsilon'', \beta_0, \beta_1, \lambda)\) as in the statement of this Theorem. We now consider any \(n\) such that \(\frac{n}{d} \in [0, \alpha_0]\). For any \(1 \le i \le n\), letting \(\alpha = \frac{i}{d}\), we obtain by Proposition 10 that \[\begin{align} &\Big| \phi_{\beta, i, d}(I) - \phi_{\beta, i-1, d}(I) - \frac{1}{d} \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( x s_i + \sqrt{q_{i, d}} Z+ \sqrt{\rho_{i, d}-q_{i, d}}W\big) \Big] \Big| \le \frac{\varepsilon}{12d}\,.\notag \end{align}\] By Proposition 14, we have \[\begin{align} \big( q_{i, d}, \rho_{i, d} \big) \in [0, C_{\mathrm{\small sol}}] \times \Big[ \frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}\Big]\,,\, \frac{1}{\rho_{i,d} - q_{i,d}} \le C_{\mathrm{\small sol}}\,. \end{align}\] Next by 70, we have \[\begin{align} \big| q_{i,d} - q_0(\alpha, \beta, x) \big|\,,\,\big|\rho_{i,d} - \rho_0(\alpha, \beta, x)\big| \le \delta = \frac{\varepsilon}{12H_1}\,. \end{align}\] Consequently \[\begin{align} &\Big| \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( xs_i + \sqrt{q_{i, d}}Z+ \sqrt{\rho_{i, d}-q_{i, d}}W\big) \Big] \notag \\ &\qquad \qquad - \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( xs_i + \sqrt{q_0(\alpha, \beta, x)}Z+ \sqrt{\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) }W\big) \Big] \Big| < \frac{\varepsilon}{8}\,. \notag \end{align}\] Finally, we observe that for any \(\alpha' \in \big[\frac{i-1}{d}, \frac{i}{d} \big]\), we have \(\big|\alpha - \alpha'\big| \le \frac{1}{d}\), so as \(d \ge 12H_2/\varepsilon\), \[\begin{align} &\Big| \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( xs_i + \sqrt{q_0(\alpha, \beta, x)}Z+ \sqrt{\rho_0(\alpha, \beta, x) - q_0(\alpha, \beta, x) }W\big) \Big] \notag \\ &\qquad \qquad - \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\big( xs_i + \sqrt{q_0(\alpha', \beta, x)}Z+ \sqrt{\rho_0(\alpha', \beta, x) - q_0(\alpha', \beta, x) }W\big) \Big] \Big| \le \frac{\varepsilon}{12}\,. \notag \end{align}\] With the above bounds in hand, we finish identically to the proof of Theorem 7, using Proposition 9 and Lemma 5. This proves Theorem 8.

7 Concentration with respect to Gaussian Measure↩︎

The goal of this section is to show that the log-partition function concentrates with respect to the Gaussian measure, as stated in Theorem 17 for interpolators and Theorem 18 for the posterior below. Recall that in Theorems 7, 8, we computed the value of the free energy, that is the expected normalized log-partition function, corresponding to the interpolators and the posterior respectively. Here, we upgrade these statements to exponentially high-probability concentration of the normalized log-partition function about this same value.

7.0.0.1 Theorem 17 for interpolators:

Recall the definition of the set \(U_i\) interpolating the \(i\)-th datapoint \(i=1, \ldots, n\) (equivalently, satisfying each constraint) defined in (29 ), and consider \(C\), the intersection of all the \(U_i\). Recalling the definition of \(S_i\) in 32, these sets are defined by \[\begin{align} U_i &:= \bigl\{ \theta \in \mathbb{R}^d \, :\, S_i \ge \kappa\bigr\}\quad\text{and}\quad C := \bigcap_{i=1}^n U_i \,.\label{eq:hyperplane95intersection95def} \end{align}\tag{71}\] In Theorem 7, we showed \(\phi_{\beta, n, d}(I)\) from 35 equals \(\mathrm{\small RSG}_I(n/d, \beta, x)\), where \(\phi_{\beta, n, d}(I)\) is the normalized logarithm of 34. We now show after replacing the mollifier \(\sum_{1 \le i \le n} u\big(\big( s_i \theta_1 + \langle g_i, \bar\theta\rangle \big)/\sqrt{d} \big)\) in 34 by the indicator \(\mathbf{1}\{\bigcap_{1 \le i \le n} U_i\}\), the corresponding normalized log-partition-function concentrates exponentially around the same value. Note this hard indicator arises as we want to study the set of interpolators. We now are in a position to state Theorem 17:

We prove Theorem 17 in Appendix 7.1. Specifically, we must handle the non-Gaussian signal component to establish several key technical results on stochastic processes and concentration of measure, which establishes the key ‘add one constraint’ style estimate Theorem 21. This result upper bounds the probability that a Gibbs measure places small mass on one side of a given constraint. This is done in Appendix 7.1.1. To handle the non-Gaussianity, it turns out we need the width \(\varepsilon''\) of \(I\) to be small enough in terms of \(\lambda\) but independent of \(d\). See the discussion at the start of Appendix 7.1.1 for more details.

7.0.0.2 Theorem 18 for posterior:

We have the following similar result for the posterior, which establishes exponential concentration of the log-partition function about \(\mathrm{\small RSG}_I\). Note this Theorem does not involve hard indicators as we are interested in studying the posterior \(p_{X,y}\) in 7, which is defined in terms of \(u(x)\) from 17, 18 in the GMM and logistic cases respectively.

We prove Theorem 18 in Appendix 7.2. Unlike Theorem 17, the proof of Theorem 18 is relatively direct as a consequence of concentration of Lipschitz functions of log-concave measures, as stated below. Note that in contrast, such tools are not available to prove Theorem 17 due to the hard indicators in the Hamiltonian therein.

7.0.0.3 Concentration of Lipschitz functions log-concave measures.

We next introduce concentration of Lipschitz functions of strongly log-concave measures in the form given in Theorem 19 below, originally credited to B. Maurey. See also the text of Bakry, Gentil, and Ledoux [43], Chapter 5. This fact allows us to establish the high-probability concentration bounds of both Theorem 17 and Theorem 18. We will also use this fact crucially in proving Proposition 11 in Appendix 9.3.

Note that this Theorem holds when \(\psi\) can take on the value \(-\infty\), that is when \(\psi\) is supported on a convex set that is a strict subset of \(\mathbb{R}^d\), as noted in (3.21) of [25]. Technically, this result is written in [25] when \(f\) is \(H\)-Lipschitz on all of \(\mathbb{R}^d\); the result writte in [25] immediately implies the following by the McShane-Whitney Extension Theorem [44], [45].

7.1 Proof of Theorem 17 for interpolators↩︎

Here throughout Appendix 7.1, we let \(Z_{\beta}(I)\) be as per ??. The goal of this section is to prove Theorem 17, and to this end there are two main steps.

1. First, we establish high-probability concentration of the normalized logarithm of 34 around its expectation \(\mathrm{\small RSG}_I(n/d, \beta, x)\), and more generally, concentration of the normalized free energy around its expectation. In particular, this also applies for ??. This is done via a technically involved application of Bernstein’s Inequality in Lemma 12.

2. Second, we show that the mollifier \(u(\cdot)\) in 34 can be eliminated without significantly changing the expectation of its logarithm, as discussed in the proof ideas in Section 5. This is a delicate step done in Lemma 14.

With both of these steps in hand, we then prove Theorem 17. All these steps are done in Appendix 7.1.2. Preliminary steps on stochastic processes and concentration of measure necessary to prove these Lemmas – specifically, the key ‘add one constraint’ style estimate, Theorem 21 – are presented in Appendix 7.1.1. These initial steps are important but highly technical.

7.1.1 Preliminaries↩︎

Central to the subsequent proof in Appendix 7.1.2 will be the combination of the following Theorem 21 and Lemma 10. These are important results on concentration of measure that let us control hard-to-bound quantities which involve the addition of the \(i\)-th datapoint or constraint, which behave at an exponential scale. In turn, these results hinge on the key Lemma 9 on stochastic processes, which is proved by several comparison inequalities.

Although similar in spirit, the statements and proofs differ from those in Section 8.2 of [26], as handling the non-Gaussian ‘signal’ component \(s_i \sim \mathcal{D}\) of the disorder requires more technical ingredients. Notably, these results hinge on being able to choose the width \(\varepsilon''\) of \(I\) small enough in terms of \(\lambda\), but still independently of \(d\), so that for \(d \ge d(\varepsilon'')\), various partition functions are lower bounded by \(\exp(-O(d))\) where \(O(\cdot)\) is independent of \(\varepsilon''\). In particular, see the assumption \(Z \ge \exp(-ad)\) in Theorem 21; this assumption applies in the proof of Theorem 17 with exponentially high probability by Lemma 12.

Recall as per Appendix 6 that \(K_{\mathrm{\small signal}}, \beta_{\mathrm{\small signal}}\) depend on \(\lambda\). However the following bounds depend delicately on these parameters, so here in Appendix 7.1.1 and only here, we will make the dependence on \(K_{\mathrm{\small signal}}, \beta_{\mathrm{\small signal}}\) fully explicit.

We begin with several preliminary results on stochastic processes.

We will now prove the crucial Lemma 9 that combines the above results. Its aim is to upper bound the probability of the following event: that for \(L\) replicas, the number of \(\ell, 1 \le \ell \le L\) such that \(\frac{1}{\sqrt{d}}\big( \theta_1^{\ell} s + \langle \bar\theta^{\ell}, \bar g \rangle \big) \ge \kappa\) is small. The proof is involved and spans the next several pages. We will then leverage Lemma 9 to prove the important Theorem 21.

We also cite the following fact from [26]. Technically, in [26], Theorem 20 is stated with \(\theta\) in place of \(\bar \theta\) in the conclusion ??, ??, however the proof is identical.

Now we prove the following very useful result that upper bounds the probability that a Gibbs measure places small mass on one side of a random hyperplane in \(\mathbb{R}^d\), where the hyperplane has law identical to the constraints (the probability is over the hyperplane). We will use this result repeatedly next in Appendix 7.1.2.

Now we find a generic way to upper bound random variables satisfying the implication in Theorem 21. This is analogous to Lemma 8.3.8 of [26], but we require some more generality.

We will also need the following useful fact:

7.1.2 Proof of Theorem 17↩︎

We now have established the technical ingredients necessary to prove Theorem 17. As discussed earlier, the proof proceeds through two key Lemmas. In Lemma 12 we show concentration of the normalized free energy around its expectation for quite general mollified Hamiltonians. This generality is needed as we apply this result for both \(u(\cdot)\) from Theorem 7 and with \(\exp u(x)=\mathbf{1}\{x \ge \kappa\}\). In Lemma 14 we show the impact of the mollifier on the expectation is small.

Since these arguments will involve changing the mollifier \(u(\cdot)\), overloading notation, we make the following definitions for only Appendix 7.1. For any function \(u(\cdot)\) and interval \(I \subseteq \mathbb{R}\), let \[\begin{align} \label{eq:gaussian95mollifier95freeenergy} H_u(\theta) := \sum_{1 \le i \le n} u(S_i)\quad\text{and}\quad Z_u(I) := \int \mathbf{1}\{\theta_1/\sqrt{d} \in I\} \exp \Big( H_u(\theta) - \beta\| \theta\|^2 \Big)\, \mathrm{d}\theta\, . \end{align}\tag{99}\] We do not vary \(\beta\) in this proof, so there will be no ambiguity in the above definitions.

Next, for \(A \ge 0\), we define the truncated logarithm \[\begin{align} \label{eq:truncated95log95def} \log_A x := \max(\log x, -A)\, . \end{align}\tag{100}\] Several useful properties of the truncated logarithm, Lemmas 55, 56, 57, are presented in Appendix 11.1. The reason we introduce the truncated logarithm is to truncate various partition functions \(Z\) by \(\log_{ad}(Z)\), allowing us to use Theorem 21. Later in the proof when we conclude Theorem 17, we will choose \(a\) large enough so the truncation is of no impact with high probability using the concentration result Lemma 12.

Our first step is to show strong concentration properties of \(\log_{ad}Z_{u}(I)\). From here on out, following the convention of this paper excluding Appendix 7.1.1, we express dependence on the quantities \(K_{\mathrm{\small signal}}, \beta_{\mathrm{\small signal}}\) through the signal-to-noise ratio \(\lambda\) governing them.

Note Lemma 12 applies for any concave \(u \le 0\) with \(u(x)=0\) for all \(x \ge \kappa\), and does not impose further regularity assumptions on \(u\). In particular, it applies for \(u\) given by \(\exp u(x) = \mathbf{1}\{x \ge \kappa\}\).

Our next goal is to show that when the \(\varepsilon'\) defining the mollifiers \(u(\cdot)\) are chosen suitably, the mollification has only a minor impact on the free energy.

Finally, we put all these steps together to prove Theorem 17.

7.2 Proof of Theorem 18 for posterior↩︎

Our strategy will be to apply Theorem 19 on concentration of Lipschitz functions of strongly log-concave measures. Specifically, we consider \(\frac{1}{d} \log Z_{\beta}(I)\) as a function of the disorder \((s_i, \bar g_i)_{i=1}^n\), and bound its resulting Lipschitz constant; recall as in Appendix 6 that the first four derivatives of \(u\) are upper bounded by some quantity \(D\), which only depends on \(\lambda\). Here in this proof we write dependence on \(D\), and in fact we only need the bound on the first derivative of \(u\).

Let us begin by considering the space \(\mathcal{S} = \mathbb{R}^{nd}\) where the first \(n\) coordinates correspond to the \(s_j\) and the next \((n-1)d\) coordinates correspond to \(g_{i,j}\). We endow \(\mathcal{S}\) with the product measure \(\gamma\) where the measure on each coordinate is given by law of each corresponding part of the disorder (that is, \(s_j\) or \(g_{i,j}\)). Define \[\begin{align} \tag{133} &\begin{aligned} B^{\star} &:= \Big( \sum_{i=1}^n \| \bar{g}_i \|^2 \Big)^{1/2} + \frac{1}{16d} \sum_{j=2}^d \Big(\sum_{i=1}^n g_{ij}\Big)^2 \\ &\qquad \qquad + \Big(n \sum_{i=1}^n s_i^2 \Big)^{1/2} + \frac{1}{8dK_{\mathrm{\small signal}}} \Big( \sum_{i=1}^n s_i \Big)^2 + Y^2 + Z^2 + \sqrt{2\pi/\beta_0} d \,, \end{aligned} \\ &\mathcal{C}:= \{ B^{\star} \le 3K_{\mathrm{\ref{lem:posteriorgaussian95Bstar95control}}}(\beta_0, \lambda)\, d \}\,, \tag{134} \end{align}\] where \(K_{\mathrm{\ref{lem:posteriorgaussian95Bstar95control}}}(\beta_0, \lambda)\) is from Lemma 21. Note \(B^{\star}\) is a convex function of the disorder and therefore \(\mathcal{C}\) is a convex subset of \(\mathbb{R}^d\). Also recall \(K_{\mathrm{\small signal}}\) depends solely on \(\lambda\).

Next, let \(\gamma'\) be a probability measure defined on \(\mathcal{C}\) with density proportional to that of \(\gamma\). By Assumption 1, \(\gamma'\) is \(\min\{1, \beta_{\mathrm{\small signal}}\}\) strongly log-concave.

Now, let us differentiate \(\frac{1}{d} \log Z_{\beta}(I)\) w.r.t. the disorder, letting \(\langle \cdot \rangle\) below and in what follows here in Appendix 7.2 denote the Gibbs average w.r.t \(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \exp\big( \sum_{i=1}^n u(S_i) - \beta \| \theta \|^2 \big)\): \[\begin{align} \frac{\partial}{\partial s_i} \Big( \frac{1}{d} \log Z_{\beta}(I) \Big) &= \frac{1}{d} \Bigg( \displaystyle\int_{\mathbb{R}^d} \mathbf{1}\{\theta_1/\sqrt{d} \in I\} \exp\Big( \sum_{i=1}^n u(S_i) - \beta \| \theta \|^2 \Big) \cdot u'(S_i) \cdot \theta_1/\sqrt{d}\, \mathrm{d}\theta \Bigg) / Z_{\beta}(I) \\ &= \frac{1}{d} \big\langle u'(S_i) \theta_1/\sqrt{d} \big\rangle\,, \\ \frac{\partial}{\partial g_{ij}} \Big( \frac{1}{d} \log Z_{\beta}(I) \Big) &= \frac{1}{d} \Bigg( \displaystyle\int_{\mathbb{R}^d} \mathbf{1}\{\theta_1/\sqrt{d} \in I\} \exp\Big( \sum_{i=1}^n u(S_i) - \beta \| \theta \|^2 \Big) \cdot u'(S_i) \cdot \theta_j/\sqrt{d}\, \mathrm{d}\theta \Bigg) / Z_{\beta}(I) \\ &= \frac{1}{d} \big\langle u'(S_i) \theta_j/\sqrt{d} \big\rangle\,. \end{align}\] Therefore, letting \(\nabla\) denote the gradient of \(\frac{1}{d} \log Z_{\beta}(I)\) w.r.t. the disorder, and defining \(R_{1,1}\) as per 45, we have \[\begin{align} \label{eq:posteriorgaussian95lipschitzbd} \| \nabla\|^2 &= \frac{1}{d^2} \Big( \sum_{i=1}^n \big\langle u'(S_i) \theta_1/\sqrt{d} \big\rangle^2 + \sum_{i=1}^n \sum_{j=1}^d \big\langle u'(S_i) \theta_j/\sqrt{d} \big\rangle \Big) \notag \\ &\le \frac{1}{d^2} \Big( \sum_{i=1}^n \big\langle u'(S_i)^2 \theta_1^2/ d \big\rangle + \sum_{i=1}^n \sum_{j=1}^d \big\langle u'(S_i)^2 \theta_j^2/d \big\rangle^2 \Big) \notag \\ &\le \frac{D^2 n}{d^2} \Big( 4 + \sum_{j=1}^d \big\langle \theta_j^2/d \big\rangle \Big) \notag \\ &\le \frac{2D^2}{d} \big( 4 + R_{1,1} \big)\,. \end{align}\tag{135}\] Here we used that \(n \le \alpha_0d \le 2d\), and that \(\big\langle \theta_1^2/d \big\rangle \le 4\) due to the indicator \(\mathbf{1}\{\theta_1/\sqrt{d} \in I\}\) in the Gibbs average \(\langle \cdot \rangle\).

7.2.0.1 Upper bounding \(R_{1,1}\).

We now upper bound \(R_{1,1}\) in terms of \(B^{\star}\) defined in 133. To this end we introduce the following Lemmas.

Technically the above Lemma is stated in [25] for \(C = \mathbb{R}^d\) and with \(a_0=0\), but the proof is identical. Note we will need this Lemma with \(a_0\) depending on the annealed disorder \(W\) from the interpolation argument in Appendix 9.3.

We next find a way to upper bound the moments w.r.t. a measure in the form of Lemma 18, provided that the normalizing constant is not too small.

Now, note that \(u(x) \ge -D(1+|x|)\) where \(u(x)\) is from 17, 18 in the GMM and logistic cases respectively. Thus Lemma 31 implies that for \(d \ge d(\varepsilon'')\), we have \[\begin{align} \label{eq:posteriorgaussian95partitionfunc} Z_{\beta}(I) \ge \exp\big( -K(D, \beta_0, \beta_1, \lambda) B^{\star} \big)\,, \end{align}\tag{136}\] where \(B^{\star}\) is given in 133. (The proof of Lemma 31 is deferred to Appendix 9.3 for simplicity of notation, since the Lemma is stated for the interpolating Gibbs measures from Appendix 6, of which the measure considered here is a special case with \(t=v=1\).)

We now show in both the GMM and logistic cases that \[\begin{align} \label{eq:posteriorgaussian95R11bd} R_{1,1} \le \frac{K(D, \beta_0, \beta_1, \lambda)\,B^{\star} }{d}\,. \end{align}\tag{137}\]

• In the logistic case where \(u(x)\) is from 18, we have \(\varphi \le 1\) and therefore \(u \le 0\). Hence by 136, we may apply Lemma 19 with the \(a_j=0\), which gives 137.

• In the GMM case where \(u(x)\) is from 17, as \(u(x) = \sqrt{\lambda} x\), we can write \[\begin{align} \label{eq:posteriorgaussian95GMM95aj} \sum_{i=1}^n u(S_i) = \sum_{i=1}^n \sqrt{\frac{\lambda}{d} } \Big( s_i \theta_1 + \sum_{j=2}^d g_{ij} \theta_j \Big) = \sqrt{\frac{\lambda}{d}} \Big(\sum_{i=1}^n s_i \Big) \theta_1 + \sum_{j=2}^d \sqrt{\frac{\lambda}{d}} \Big( \sum_{i=1}^n g_{ij} \Big) \theta_j\,. \end{align}\tag{138}\] Thus applying Lemma 19 with 136, we obtain that \[\begin{align} R_{1,1} \le \frac{1}{d} \Bigg( K(D, \beta_0, \beta_1, \lambda) B^{\star} + \frac{\lambda}{2\beta_0 d} \Big( \sum_{i=1}^n s_i \Big)^2 + \frac{\lambda}{2\beta_0 d} \sum_{j=2}^d \Big( \sum_{i=1}^n g_{ij} \Big)^2 \Bigg) \le \frac{K(D, \beta_0, \beta_1, \lambda)\,B^{\star} }{d}\,, \end{align}\] where the last step follows from the definition of \(B^{\star}\) in 133. Again this proves 137.

7.2.0.2 Completing the argument.

Now we apply Theorem 19 with \(f=\frac{1}{d} \log Z_{\beta}(I)\) and the strongly log-concave measure \(\gamma'\). By 135 and 137, \(f\) is Lipschitz with constant \(K(D, \beta_0, \beta_1, \lambda) / \sqrt{d}\) on \(\mathcal{C}\). Since \(\gamma'\) is supported on \(\mathcal{C}\) and \(\mathcal{C}\) is convex, Theorem 19 yields for \(d \ge d(\varepsilon'')\) that \[\begin{align} \label{eq:posteriorgaussian95logconcaveconcentration} \operatorname{\mathbb{P}}_{\gamma'}\Big( \Big| \frac{1}{d} \log Z_{\beta}(I) - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] \Big| \ge \varepsilon/2 \Big) \le \exp\big( -d / K(\varepsilon, D, \beta_0, \beta_1, \lambda)\big)\,, \end{align}\tag{139}\] where \(\varepsilon>0\) is as in the statement of Theorem 18.

We next state the following Lemma that essentially lets us reduce the desired tail bound in Theorem 18 to 139. Its proof will be presented later.

We will now prove Theorem 18 given Lemma 20. Let \[\begin{align} E_{\varepsilon}' &:= \Big\{ \Big| \frac{1}{d} \log Z_{\beta}(I) - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] \Big| \ge \varepsilon/4 \Big\}\,. \label{eq:posteriorgaussian95ezeventdef} \end{align}\tag{140}\] By Lemma 20, for \(d \ge d(\varepsilon, \varepsilon'', D, \beta_0, \beta_1, \lambda)\), \[\begin{align} &\operatorname{\mathbb{P}}_{\gamma}\Big( \Big| \frac{1}{d} \log Z_{\beta}(I) - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \big] \Big| \ge \varepsilon/2 \Big) \notag \\ &\quad= \operatorname{\mathbb{P}}_{\gamma}\Big( \Big| \frac{1}{d} \log Z_{\beta}(I) - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] + \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \big] \Big| \ge \varepsilon/2 \Big) \notag \\ &\quad \le \operatorname{\mathbb{P}}_{\gamma}\Big( \Big| \frac{1}{d} \log Z_{\beta}(I) - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] \Big| \ge \varepsilon/4 \Big) \notag \\ &\quad = \operatorname{\mathbb{E}}_{\gamma}\Big[ \mathbf{1}\{E'_{\varepsilon} \} \Big] \notag \\ &\quad = \operatorname{\mathbb{E}}_{\gamma}\Big[ \mathbf{1}\{ E'_{\varepsilon}\} \mathbf{1}\{\mathcal{C}\} \Big] + \operatorname{\mathbb{E}}_{\gamma}\Big[ \mathbf{1}\{ E'_{\varepsilon} \} \mathbf{1}\{\mathcal{C}^c\} \Big] \notag \\ &\quad \le \gamma(\mathcal{C}) \operatorname{\mathbb{E}}_{\gamma'}\Big[ \mathbf{1}\{ E'_{\varepsilon}\} \mathbf{1}\{\mathcal{C}\} \Big] + \operatorname{\mathbb{E}}_{\gamma}\Big[ \mathbf{1}\{\mathcal{C}^c\} \Big] \notag \\ &\quad \le \exp\big( -d / K(\varepsilon, D, \beta_0, \beta_1, \lambda)\big)\,. \label{eq:posteriorgaussian95concentrationfinish} \end{align}\tag{141}\] Here in the last inequality, we applied 139.

Finally, recall by Theorem 8 that for \(d \ge d(\varepsilon, \varepsilon'', D, \beta_0, \beta_1, \lambda)\), we have \[\begin{align} \Big| \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \big] - \mathrm{\small RSG}_I(n/d, \beta, x) \Big| \le \varepsilon/2\,. \end{align}\] Therefore combining with 141 gives \[\begin{align} \operatorname{\mathbb{P}}_{\gamma}\Big( \Big| \frac{1}{d} \log Z_{\beta}(I) - \mathrm{\small RSG}_I(n/d, \beta, x) \big] \Big| \ge \varepsilon\Big) &\le \operatorname{\mathbb{P}}_{\gamma}\Big( \Big| \frac{1}{d} \log Z_{\beta}(I) - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \big] \Big| \ge \varepsilon/2 \Big) \\ &\le \exp\big( -d / K(\varepsilon, D, \beta_0, \beta_1, \lambda)\big)\,. \end{align}\] This proves Theorem 18 given Lemma 20.

7.2.0.3 Proof of Lemma 20.

Finally, we prove Lemma 20. We first introduce the following Lemma which gives us a tail bound on \(B^{\star}\). This Lemma follows as a corollary of the proof of Lemma 30, which is proven later in Appendix 9.3.

Given Lemma 21, by the definition of \(\mathcal{C}\), we directly obtain ??. To prove ??, we introduce an additional Lemma:

Now to prove ??, we write \[\begin{align} \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \big] &= \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}\} \big] + \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}^c\} \big] \\ &= \frac{1}{d} \gamma(\mathcal{C}) \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] + \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}^c\} \big]\,, \end{align}\] where we note \(\operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}\} \big] = \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big]\) as the support of \(\gamma'\) equals \(\mathcal{C}\). Therefore \[\begin{align} &\frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \big] \notag \\ &\quad = \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] - \Big( \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}\} \big] + \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}^c\} \big] \Big) \notag \\ &\quad = \frac{1-\gamma(\mathcal{C})}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big] - \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}^c\} \big]\,.\label{eq:posteriorgaussian95rewritediff} \end{align}\tag{142}\] By Lemma 22, and since \(\gamma'\) is supported on \(\mathcal{C}\) on which \(B^{\star} \le K(D, \beta_0, \beta_1, \lambda) d\), we have \[\begin{align} \label{eq:posteriorgaussian95bounddiff1} \Big| \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \log Z_{\beta}(I) \big]\Big| \le \frac{1}{d} \operatorname{\mathbb{E}}_{\gamma'}\big[ \big|\log Z_{\beta}(I) \big| \big] \le K(D, \beta_0, \beta_1, \lambda)\,. \end{align}\tag{143}\] Next by Lemma 21, note \[\begin{align} \label{eq:posteriorgaussian95tailbd} \operatorname{\mathbb{P}}_{\gamma}\big(B^{\star} \ge t\big) \le \big(K_{\mathrm{\ref{lem:posteriorgaussian95Bstar95control}}}(D, \beta_0, \beta_1, \lambda) / t \big)^d \text{ for all }t \ge 0\,. \end{align}\tag{144}\] Thus by Lemma 22 and integrating the tail bound 144, we have \[\begin{align} \Big| \operatorname{\mathbb{E}}_{\gamma}\big[ \log Z_{\beta}(I) \mathbf{1}\{\mathcal{C}^c\} \big] \Big| &\le K(D, \beta_0, \beta_1, \lambda) \operatorname{\mathbb{E}}_{\gamma}\big[ B^{\star} \mathbf{1}\{\mathcal{C}^c\} \big] \notag \\ &\le K(D, \beta_0, \beta_1, \lambda) \int_{ 3K_{\mathrm{\ref{lem:posteriorgaussian95Bstar95control}}}(D, \beta_0, \beta_1, \lambda) d }^\infty \operatorname{\mathbb{P}}_{\gamma}\big(B^{\star} \ge t\big)\, \mathrm{d}t \notag \\ &\le K(D, \beta_0, \beta_1, \lambda) \exp(-d)\,.\label{eq:posteriorgaussian95boundwtailbd} \end{align}\tag{145}\] Combining ??, 142, 143, 145 now proves ?? for \(d \ge d(\varepsilon, \varepsilon'', D, \beta_0, \beta_1, \lambda)\), finishing the proof of Lemma 20.

8 Conversion from Gaussian to spherical measure: proof of Theorems 1, 4↩︎

Here we complete the proof of our main results Theorems 1, 4. Theorem 1 on interpolators and Theorem 4 on the posterior follow as a corollary of the following Theorems 22, 23 respectively.

8.0.0.1 Theorem 22 for interpolators:

This result states that for a narrow interval \(I\) near \(x \in [-1,1]\) (whose width is independent of \(d\)), the normalized logarithm of the spherical measure of the interpolators constrained to this interval, approximately equals \(\inf_{q \in [0,1)}\Phi(x, q)\) for \(d\) large enough:

8.0.0.2 Theorem 23 for posterior:

This result is similar to Theorem 22, but now is for the normalized logarithm of the integral of the posterior constrained to the interval \(I\), rather than the spherical measure of the interpolators:

We will prove Theorem 22 in the \(\kappa< 0\) case in Appendix 8.2, prove Theorem 22 in the \(\kappa\ge 0\) case in Appendix 8.3, and prove Theorem 23 in Appendix 8.4. All three proofs follow the same unified strategy that leverages our work in Appendix 7, specifically Theorem 17 for the interpolators and Theorem 18 for the posterior. We present a full proof for \(\kappa< 0\) in Appendix 8.2 and highlight the necessary modifications to complete the proof when \(\kappa>0\) or for the posterior in Appendices 8.3, 8.4.

Before we present the proofs of Theorems 22, 23, we combine them with an application of the Laplace Method over \(x \in [-1,1]\) to prove our main results: Theorem 1 on interpolators and Theorem 4 on the posterior respectively. Note the Laplace Method gives the ‘\(\sup_x \inf_q\)’ structure therein. In preparation, we will present the following properties of the RS equations, which follow from the convex-concave structure established in Appendix 10. The proof of this Lemma is in Appendix 10.3.

We now prove Theorems 1, 4 using Theorems 22, 23 and the above Lemma 23.

8.1 Proof of Theorems 1, 4↩︎

We provide the proof of Theorem 1 using Theorem 22 when \(\kappa< 0\); the proof of Theorem 1 in the \(\kappa\ge 0\) case and the proof of Theorem 4 using Theorem 23 are analogous. Recall that \(y_i X_i \equiv (s_i, g_i)^T\) in law as random variables and that without loss of generality we can set \(\theta_\star = \sqrt{d} e_1\).

First, we show ??, ?? with the interval \(I\) replaced by any interval \(I \subseteq [-1+\delta, 1-\delta]\). Recall as per 36 that \(\beta_0, \beta_1\) are universal constants, therefore in this proof we will not explicitly write dependence on them.

8.1.0.1 Proof of ??:

Note for \(d \ge d(\varepsilon)\), \(\frac{1}{d} \log \mu_d \bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in [-1/\sqrt{d}, 1/\sqrt{d}] \}\bigr) \le \varepsilon\). Now if \(0 \in I\), we subdivide \(I\) into the two closed intervals \(I_1 = I \cap [-1, -1/\sqrt{d}]\), \(I_2 = I \cap [1/\sqrt{d}, 1]\), and the remaining part \(I-I_1-I_2\) (if \(0 \not\in I\) this step is not necessary, and we can just apply the same argument as in the following upper bound for \(I_1\)).

We now upper bound \(\frac{1}{d} \log \mu_d \bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in I_1 \} \cap C\bigr)\), the upper bound for \(I_2\) being analogous. We divide the closed interval \(I_1\) into a set of consecutive closed intervals \(\bar I_k\) each of width \(\varepsilon_{\mathrm{\small RSG}}=\varepsilon_{\mathrm{\small RSG}}(\varepsilon, \alpha_0, \kappa, \lambda)\) (recall \(\beta_0, \beta_1\) are universal constants), \(1 \le k \le K(\varepsilon_{\mathrm{\small RSG}})\), that overlap at exactly their endpoints. Here \(\varepsilon_{\mathrm{\small RSG}}\) comes from Theorem 17.

For each interval \(\bar I_k=[a,b]\), note \(0<a< b \le 1\), \(b-a \le \varepsilon_{\mathrm{\small RSG}}\). Letting \(\varepsilon'' = \frac{b-a}{2-a} < b-a\) and \(x = b-\varepsilon''\), we have \(\bar I_k = [a,b] = \big[\frac{x-\varepsilon''}{1-\varepsilon''}, x+\varepsilon'' \big]\), \(x>\varepsilon''\), \(\varepsilon'' \le b-a \le \varepsilon_{\mathrm{\small RSG}}\). Since \(\varepsilon'' \ge b-a = \varepsilon_{\mathrm{\small RSG}}=\varepsilon_{\mathrm{\small RSG}}(\varepsilon, \alpha_0, \kappa, \lambda)\), Theorem 22 yields that for \(d \ge d(\varepsilon, \alpha, \kappa, \lambda)\), with probability at least \(1-\exp\bigl(- d / K(\varepsilon, \alpha, \kappa, \lambda) \bigr)\), \[\begin{align} \frac{1}{d} \log \mu_d \Bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in \bar I_k\} \cap C \Bigr) &\le \inf_{q \in [0,1)}\Phi(x, q) + \varepsilon\le \sup_{x \in I} \inf_{q \in [0,1)}\Phi(x, q) + \varepsilon\,. \end{align}\] Here the second inequality uses that \(\bar I_k \subseteq I_1\). As we have \(K(\varepsilon_\mathrm{\small RSG})\) such intervals \(\bar I_k\), combining the above bound over all \(1 \le k \le K(\varepsilon_\mathrm{\small RSG})\) and applying a Union Bound (note we sum the bounds on \(\mu_d \bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in I_1\} \cap C \bigr)\), which behaves at the exponential scale) yields that for \(d \ge d(\varepsilon, \alpha, \kappa, \lambda)\), with probability at least \(1-\exp\big(-d / K(\varepsilon, \alpha, \kappa, \lambda) \bigr)\), \[\begin{align} \frac{1}{d} \log \mu_d \Bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in I_1\} \cap C \Bigr) \le \sup_{x \in I} \inf_{q \in [0,1)}\Phi(x, q) + 2\varepsilon\,. \end{align}\] An analogous bound applies for \(I_2\) via the same proof, and for \(I-I_1-I_2\) we recall the bound \(\frac{1}{d} \log \mu_d \bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in [-1/\sqrt{d}, 1/\sqrt{d}] \}\bigr) \le \varepsilon\). Combining these three upper bounds and applying a Union Bound yields for \(d \ge d(\varepsilon, \alpha, \kappa, \lambda)\), with probability at least \(1-\exp\bigl(-d / K(\varepsilon, \alpha, \kappa, \lambda) \bigr)\), \[\begin{align} \frac{1}{d} \log \mu_d \Bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C\Bigr) \le \sup_{x \in I} \inf_{q \in [0,1)}\Phi(x, q) + 4\varepsilon\,. \end{align}\] Upon taking \(\varepsilon\leftarrow \varepsilon/4\), this proves ?? for this \(I\).

8.1.0.2 Proof of ??:

In this proof, we write \(I = [a,b]\) for \(-1 \le a < b \le 1\). Note it suffices to prove the result when \(\varepsilon< \frac{1}{K'(\alpha, \kappa, \lambda)}\). First, continuity from Lemma 23 implies \(\sup_{x \in I} \inf_{q \in [0,1)}\Phi(x, q)\) is attained at some \(x^\star \in I\). Noting \(\inf_{q \in [0,1)}\Phi(x, q)\) only depends on \(\alpha, \kappa, \lambda\), by continuity supplied by Lemma 23 and compactness, we let \(\bar\delta = \bar\delta(\varepsilon, \alpha, \kappa, \lambda)\) be small enough so that \[\begin{align} \label{eq:sphericalconversion95laplace95uniformcontinuity} \big| \inf_{q \in [0,1)}\Phi(x_1, q) - \inf_{q \in [0,1)}\Phi(x_2, q) \big| \le \varepsilon\,, \qquad \forall\, x_1,x_2 \in [-1+\delta, 1-\delta]\,,\, |x_1-x_2| \le \bar\delta\,. \end{align}\tag{146}\] Since \(\varepsilon\le \varepsilon_0\), taking \(\varepsilon_0\) small enough in terms of \(\alpha, \kappa, \lambda, |I|\), we may suppose that \(|I| \ge \bar\delta\).

We first prove the result when \(I \subseteq [0, \infty)\); the proof when \(I \subseteq (-\infty, 0]\) is analogous, and later we will provide the argument when neither case holds.

1. Suppose \(x^{\star} > 0\) is distance at least \(\bar\delta/4\) from \(a, b\). Let \(\bar\varepsilon= \bar\varepsilon(\varepsilon, \bar\delta, \alpha, \lambda) \le \min\{ \bar\delta/8, \varepsilon\}\) and \(\varepsilon'' < \min\big\{ \varepsilon_{\mathrm{\small RS}}(\bar\varepsilon, \alpha, \kappa, \lambda), \bar\delta/8 \big\}\) be small enough, where \(\varepsilon_{\mathrm{\small RS}}\) comes from Theorem 22. Let \[\begin{align} \label{eq:sphericalconversion95laplace95barIdef} \bar I := \Big[\frac{x^\star-\varepsilon''}{1+\bar\varepsilon}, x^\star+\varepsilon'' \Big]\,. \end{align}\tag{147}\] As \(|a| \le 1\), \(\bar\varepsilon+ \varepsilon'' < \bar\delta/4\), \(|x^{\star}| \le 1\) and \(x^\star\) is distance at least \(\bar\delta/4\) from \(a,b\), we have \(\bar I \subseteq I\). Also, clearly \(x^\star \ge \bar\delta/4 > \varepsilon''\). Applying Theorem 22, recalling that \(\bar\delta\) and \(\bar\varepsilon\) depend only on \(\varepsilon, \alpha, \kappa, \lambda\), we obtain for \(d \ge d(\bar\varepsilon, \varepsilon'', \alpha, \kappa, \lambda) = d(\varepsilon, \alpha, \kappa, \lambda)\) that with probability at least \(1-\exp\bigl(-d / K(\varepsilon, \alpha, \kappa, \lambda) \bigr)\), \[\begin{align} \frac{1}{d} \log \mu_d \Bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \Bigr) &\ge \frac{1}{d} \log \mu_d \Bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in \bar I\} \cap C \Bigr) \notag \\ &\ge \inf_{q \in [0,1)}\Phi(x^\star, q) - \varepsilon\,, \label{eq:sphericalconversion95laplace95basiclowerbd} \end{align}\tag{148}\] where we use that \(\bar\varepsilon\le \varepsilon\) in the last inequality.

2. Suppose \(x^\star\) is within distance \(\bar\delta/4\) from \(a,b\). Now, we simply apply the above argument with \(x^\star\) replaced by \(\bar x^\star = a+\bar\delta/4\) if \(|a-x^\star| \le \bar\delta/4\) or \(\bar x^\star = b-\bar\delta/4\) if \(|b-x^\star| \le \bar\delta/4\). Since \(|I| \ge \bar\delta\), the resulting \(\bar x^\star\) is always distance at least \(\bar\delta/4\) from \(a,b\), and hence \(\bar x^\star > \varepsilon''\) as well. Define \(\bar \varepsilon\), \(\varepsilon''\) identically to case 1) above and \(\bar I\) now in terms of \(\bar x^\star\) as per 147. Applying Theorem 22 analogously, by \(|x^\star - \bar x^\star | \le \bar\delta\) and 146, we obtain for the same \(d\) and with the same probability as 148 that \[\begin{align} \frac{1}{d} \log \mu_d \Bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \Bigr) &\ge \frac{1}{d} \log \mu_d \Bigl(\mathbf{1}\{\theta_1/\sqrt{d} \in \bar I\} \cap C \Bigr) \notag \\ &\ge \inf_{q \in [0,1)}\Phi(\bar x^\star, q) - \bar\varepsilon\notag \\ &\ge \inf_{q \in [0,1)}\Phi(x^\star, q) - 2\varepsilon\,.\label{eq:sphericalconversion95laplace95lowerbd2} \end{align}\tag{149}\]

Finally suppose \(I\) is not contained within \([0,\infty)\) or \((-\infty, 0]\). We suppose \(x^\star \ge 0\) in what follows, the argument when \(x^\star < 0\) is analogous.

1. Suppose \(\big| I \cap [0, \infty) \big| \ge \bar\delta/2\). If \(x^\star \ge \bar\delta/4\) we simply apply the argument in either cases 1) or 2) above, defining \(\bar\varepsilon, \varepsilon'',\bar I\) the same way as there. In particular, we still have \(\bar I \subseteq I\) as \(\big| I \cap [0, \infty)\big| \ge \bar\delta/2\); if we need to define \(\bar x^\star\) as in case 2) above (note this only arises when \(x^\star\) is within \(\bar\delta/4\) of the right endpoint of \(I\)), since \(\big| I \cap [0, \infty)\big| \ge \bar\delta/2\), the resulting \(\bar x^\star\) is always distance at least \(\bar\delta/4 > \varepsilon''\) from the endpoints of \(I\) and 0.

   Next suppose \(0 \le x^\star \le \bar\delta/4\). We apply the argument in case 2) above with \(\bar x^\star = \bar\delta/4\). Note that defining \(\bar I\) analogously, we have \(\bar I \subseteq I\) as \(\big| I \cap [0, \infty)\big| \ge \bar\delta/2\). Combining with the fact that \(|\bar x^\star - x^\star| \le \bar\delta/4\) and 146, we obtain 149.

2. Suppose \(\big| I \cap [0, \infty)\big| < \bar\delta/2\). Therefore as \(|I| \ge \bar\delta\), \(\big| I \cap (-\infty, 0] \big| \ge \bar\delta/2\). We now apply the argument in either cases 1) or 2) above now with \(\bar x^{\star} = -\bar\delta/4\), defining \(\bar \varepsilon, \varepsilon''\) analogously and now defining \(\bar I := \big[ \bar x^{\star} -\varepsilon'', \frac{\bar x^{\star}+\varepsilon''}{1+\bar\varepsilon} \big]\).

   Since the interval \(I\) is not fully contained in \([0, \infty)\) or \((-\infty, 0]\) and \(\big| I \cap (-\infty, 0] \big| \ge \bar\delta/2\), we have \(\bar x^\star \in I\), and furthermore that \(\bar I \subseteq I \cap (-\infty, 0]\). Also, \(|\bar x^\star| \ge \bar\delta/4 > \varepsilon''\). Finally, as \(x^\star \ge 0\) and \(\big| I \cap [0, \infty)\big| < \bar\delta/2\), we have \(|\bar x^\star - x^\star| \le 3\bar\delta/4\). Combining with 146 gives 149.

This yields the desired lower bound in all cases. Now, ?? follows by taking \(\varepsilon\leftarrow \varepsilon/2\).

To complete the proof, we must upper bound \(\frac{1}{d} \log \mu_d\big( \mathbf{1}\{|\theta_1/\sqrt{d}| \ge 1-\delta\} \cap C \big)\). As \(\delta \le \frac{1}{10}\), it remains to show that with probability at least \(1 - \exp\big(-d/K(\varepsilon, \alpha, \kappa, \lambda)\big)\) for \(d \ge d(\varepsilon, \alpha, \kappa, \lambda)\), we have the following for a universal constant \(c>0\). For the interpolators, \[\begin{align} \label{eq:interpolants95finish95desired} \frac{1}{d} \log \mu_d\Big( \mathbf{1}\big\{|\theta_1/\sqrt{d}| \ge 9/10 \big\} \cap C \Big) < \sup_{x \in [-1 + \delta, 1-\delta]} \inf_{q \in [0,1)} \Phi(x,q) - c\,, \end{align}\tag{150}\] and for the posterior, defining \(Z(I)\) as per ??, \[\begin{align} \label{eq:posterior95finish95desired} \frac{1}{d} \log \Big( Z\big( [-1, -9/10] \big) + Z\big( [9/10, 1] \big) \Big) - \frac{1}{2} \log(2\pi e) < \sup_{x \in [-1 + \delta, 1-\delta]} \inf_{q \in [0,1)} \Phi(x,q) - c\,. \end{align}\tag{151}\] We now upper bound the \(\small\rm LHS\) in 150, 151. By following the same proof as that of Lemma 24, we have with probability at least \(1 - \exp\big(-d/K(\varepsilon, \alpha, \kappa, \lambda)\big)\), \[\begin{align} \label{eq:posterior95spherical95finish95gmmbd} \sup_{\theta \in \mathbb{S}^{d-1}(\sqrt{d})} \sum_{i=1}^n u(S_i) \le K(\lambda) \sqrt{n d}\,. \end{align}\tag{152}\] Standard bounds on the surface area of a spherical cap gives \[\begin{align} \frac{1}{d} \log \mu_d\Big( \mathbf{1}\{ |\theta_1/\sqrt{d}| \ge 9/10 \Big) \le -c'\,, \end{align}\] where \(c'>0\) is a universal constant. Letting \(\small\rm LHS\) denote the \(\small\rm LHS\) in 150, 151, combined with the bounds \(u = \log \varphi \le 0\) for the logistic case for the posterior or 152 for the GMM case for the posterior, we obtain with probability at least \(1 - \exp\big(-d/K(\varepsilon, \alpha, \kappa, \lambda)\big)\) and for \(d \ge K\), \[\begin{align} \label{eq:posterior95spherical95finish95lhsbd} \small\rm LHS\le -c' + K(\lambda) \sqrt{\alpha}\,. \end{align}\tag{153}\] On the other hand, by the proof of 1) in Appendix 10.4, we have \(\sup_{x \in [-1,1]} \inf_{q \in [0,1)} \Phi(x,q) = \Phi(x^\star, q^\star)\) for a unique \((x^\star, q^\star) \in [0, K(\lambda) \alpha]^2\). Since \(\alpha \le \alpha_0(\lambda, \kappa_+)\) and \(\delta \le 1/10\), the bound 276 implies that \[\begin{align} \label{eq:posterior95spherical95finish95rhsbd} \sup_{x \in [-1 + \delta, 1-\delta]} \inf_{q \in [0,1)} \Phi(x,q) = \Phi(x^\star, q^\star) \ge -\alpha K(\lambda, \kappa_+)\,. \end{align}\tag{154}\] Since \(\alpha \le \alpha_0(\lambda, \kappa_+)\) and \(c'>0\) is a universal constant, combining 153, 154 now implies 150 for the interpolators or 151 for the posterior. This completes the proof of Theorems 1, 4.

8.2 Proof of Theorem 22 for interpolators: \(\kappa< 0\)↩︎

Throughout this proof, we let \(\bar I := [x-\varepsilon'', x+\varepsilon'']\). Note \(0 \not\in \bar I\) as \(|x|>\varepsilon''\). Consequently recalling 38, we note \(\mathrm{\small RSG}_{\bar I}\) does not depend on \(\varepsilon''\) as \(r_{\bar I}(x)\), the only part depending on \(\bar I\), equals \(x^2\). In the following Appendices 8.2, 8.3, 8.4, we let \(\mathrm{Area}(A)\) refer to the surface area any Lebesgue measurable subset of \(v \mathbb{S}^{d-1}(\sqrt{d})\) for any \(v>0\).

8.2.0.1 Preliminaries:

Due to the lack of continuity caused by the hard indicator functions, we instead use the monotonicity from the following comparison inequalities. For any \(v>0\), consider \[\begin{align} vU_i = \Bigl\{ v\theta \in \mathbb{R}^{d} \, :\, \frac{1}{\sqrt{d}}\Bigl( s_i \theta_1 + \langle g_i, \bar{\theta} \rangle \Bigr) \ge \kappa\Bigr\} = \Bigl\{ \theta \in \mathbb{R}^{d} \, :\, \frac{1}{\sqrt{d}}\Bigl( s_i \theta_1 + \langle g_i, \bar{\theta} \rangle \Bigr) \ge v\kappa\Bigr\}\, , \label{eq:v95plane95logic} \end{align}\tag{155}\] where the last equality follows from the transformation \(\theta\leftarrow v\theta\). Therefore as \(\kappa< 0\), we have \[\begin{align} &\text{For v \ge 1:}\quad vU_i \supseteq \Bigl\{ \theta \in \mathbb{R}^{d} \, :\, \frac{1}{\sqrt{d}}\Bigl( s_i \theta_1 + \langle g_i, \bar{\theta} \rangle \Bigr) \ge \kappa\Bigr\} = U_i, \text{ hence } vC \supseteq C\,, \tag{156}\\ &\text{For v \le 1:}\quad vU_i \subseteq \Bigl\{ \theta \in \mathbb{R}^{d} \, :\, \frac{1}{\sqrt{d}}\Bigl( s_i \theta_1 + \langle g_i, \bar{\theta} \rangle \Bigr) \ge \kappa\Bigr\} = U_i, \text{ hence } vC \subseteq C\, .\tag{157} \end{align}\] We next set up several comparison inequalities letting us to relate the indicator \(\mathbf{1}\{\theta_1/\sqrt{d} \in I\}\) to \(\mathbf{1}\{\theta_1/\sqrt{d} \in \bar I\}\) (the difference is between \(I, \bar I\)). For any interval \([a,b]\), remark \[\begin{align} &\text{For 1 \le v \le w}:\quad v[a, b] \supseteq [wa, b]\text{ if b \ge a \ge 0}\quad , \quad v[a,b] \supseteq [a, wb]\text{ if a \le b \le 0}\,,\tag{158} \\ &\text{For w \le v \le 1}:\quad v[a, b] \subseteq [wa, b]\text{ if b \ge a \ge 0}\quad , \quad v[a,b] \subseteq [a, wb]\text{ if a \le b \le 0}\,.\tag{159} \end{align}\]

8.2.0.2 Proof of ??:

Let \(w=1-\varepsilon''\) here in the proof of ?? and let \(I\) be as per ??. Consider any \(\beta\in [\beta_0, \beta_1]\). By 157 and 159, we have the following. If \(x \ge \varepsilon'' >0\), \[\begin{align} \small\rm LHS:= &\int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\\ &\ge \text{Vol}\Bigl(\mathbf{1}\big\{\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon''] \big\} \cap C \cap \mathbf{1}\big\{w^2 d \le \|\theta\|^2 \le d \big\} \Bigr) \exp(-\beta d) \\ &= \exp(-\beta d)\sqrt{d}\int_w^1 \mathrm{Area}\Big( \mathbf{1}\big\{\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon'']\big\} \cap C \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big) \, \mathrm{d}v \\ &\ge \exp(-\beta d)\sqrt{d}\int_w^1 \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in v \Big[ \frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big]\Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &= \exp(-\beta d) \sqrt{d} \int_w^1 \mathrm{Area}\Big( \mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[\frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big]\Big\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big) v^{d-1}\, \mathrm{d}v \\ &= \exp(-\beta d)\, \mathrm{Area}\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \frac{1}{\sqrt{d}}\, (1-w^d)\, \\ &\ge \exp(-\beta d)\, \mathrm{Area}\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \frac{1}{2\sqrt{d}}\,. \end{align}\] Here we used the change of variable \(\theta \leftarrow v \theta\), and that \(w^d = (1-\varepsilon'')^d \le \frac{1}{2}\) for \(d \ge d(\varepsilon'')\). Similarly if \(x \le -\varepsilon''<0\), by an analogous derivation as above, again using 157 and 159, \[\begin{align} \small\rm LHS &\ge \exp(-\beta d)\sqrt{d}\int_w^1 \mathrm{Area}\Big(\mathbf{1}\big\{\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon'']\big\} \cap C \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\ge \exp(-\beta d)\sqrt{d}\int_w^1 \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in v \Big[ x-\varepsilon'', \frac{x+\varepsilon''}{w} \Big]\Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\ge \exp(-\beta d)\, \mathrm{Area}\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \frac{1}{2\sqrt{d}}\,. \end{align}\] For both cases, taking logarithms gives \[\begin{align} \label{eq:sphericalconversion95upperbd95comparisonresult} \frac{1}{d} \log\big( \small\rm LHS\big) &\ge -\beta+ \frac{1}{d} \log \mathrm{Area}\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big) + \frac{1}{d} \log\Big( \frac{1}{2\sqrt{d}}\Big)\, . \end{align}\tag{160}\] By Theorem 17 applied with the interval \(\bar I\), since \(\varepsilon'' \le \varepsilon_{\mathrm{\small RSG}}(\varepsilon, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\), we have for \(d \ge d(\varepsilon, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) with probability at least \(1-\exp\big(-d / K(\varepsilon, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\big)\), \[\begin{align} &\frac{1}{d} \log\big( \small\rm LHS\big) \in \Big[ \mathrm{\small RSG}_{\bar I}(n/d, \beta, x) - \varepsilon, \mathrm{\small RSG}_{\bar I}(n/d, \beta, x) + \varepsilon\Big]\, .\label{eq:sphericalconversion95upperbd95gaussian1} \end{align}\tag{161}\] By Proposition 9, as \(0 \not\in \bar I\), the Lipschitz constant of \(\mathrm{\small RSG}_{\bar I}(\alpha, \beta, x)\) over \((\alpha, \beta, x) \in [0, \alpha_0] \times [\beta_0, \beta_1] \in [-1, 1]\) is upper bounded in terms of \(\alpha_0, \beta_0, \beta_1, \kappa, \lambda\). Therefore, we obtain that for \(d \ge d(\varepsilon, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\), we have \(\big| \mathrm{\small RSG}_{\bar I}(n/d, \beta, x) - \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) \big| \le \varepsilon\). Noting \[\begin{align} \mathrm{Area}\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big) = \mu_d\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \Big) \mathrm{Area}\big( \mathbb{S}^{d-1}(\sqrt{d}) \big)\, , \end{align}\] combining with 160, 161 yields for the same \(d\) and the same probability as 161 that \[\label{eq:sphericalconversionupperboundfinal} \begin{align} &\frac{1}{d} \log \mu_d\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \Big) \\ &\quad \le \beta+ \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) + 2\varepsilon+ \frac{\log(2\sqrt{d})}{d} - \frac{1}{d} \log \mathrm{Area}(\mathbb{S}^{d-1}(\sqrt{d}))\, . \end{align}\tag{162}\] By Lemma 23, as \(\alpha \le \alpha_0\) and as \(0 \not\in \bar I\), \(\inf_{q \in [0,1)} \Phi(x, q)=\beta+\mathrm{\small RSG}_{\bar I}(\alpha,\beta, x)-\frac{1}{2} \log(2\pi e)\) for \(\beta=\beta(\alpha, x)\). Moreover, recall \(\lim_{d\rightarrow\infty} \frac{1}{d} \log \mathrm{Area}(\mathbb{S}^{d-1}(\sqrt{d})) = \frac{1}{2} \log(2e\pi)\).

Taking \(\beta=\beta(\alpha, x)\) in 162 thus gives for \(d \ge d(\varepsilon, \varepsilon'', \alpha, \beta_0, \beta_1, \kappa, \lambda)\) and with probability at least \(1-\exp\big(-d / K(\varepsilon, \alpha, \beta_0, \beta_1, \kappa, \lambda)\big)\), \[\frac{1}{d} \log \mu_d\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \Big) \le \inf_{q \in [0,1)} \Phi(x, q) + 3\varepsilon\, ,\] where we note \(\lim_{d\rightarrow\infty} \frac{1}{d} \log \mathrm{Area}(\mathbb{S}^{d-1}(\sqrt{d}))-\frac{1}{2} \log(2e\pi) = 0\). The result follows taking \(\varepsilon\leftarrow \varepsilon/3\).

8.2.0.3 Proof of ??:

We proceed with a similar strategy to the proof of ?? above, though this direction is more involved. First, by the second part of Proposition 9, \(\rho_0(\alpha, \beta, x)\) is infinitely differentiable in \(\beta\) and \(x\) for \((\beta, x) \in [\beta_0, \beta_1] \times [-1, 1]\). We thus may define \[\begin{align} \underline{H}= \underline{H}(\alpha, \kappa, \lambda) &:= \inf_{(\beta, x) \in [\beta_0, \beta_1] \times [-1, 1]} -\frac{\partial}{\partial \beta} \rho_0(\alpha,\beta, x)\,, \tag{163}\\ \overline{H}= \overline{H}(\alpha, \kappa, \lambda) &:= \sup_{(\beta, x) \in [\beta_0, \beta_1] \times [-1, 1]} -\frac{\partial}{\partial \beta} \rho_0(\alpha,\beta, x)\,.\tag{164} \end{align}\] By Lemma 23, Proposition 9, and compactness, \(\underline{H}> 0\). \(\underline{H}> 0\) yields strong convexity, which will be crucial in our subsequent arguments. For the rest of the proof of ??, we consider \(\varepsilon< \min\big\{1, \frac{1}{12} \underline{H}\big\}\).

8.2.0.4 Choice of parameters and properties of variational problem.

Let \(w = 1 + \varepsilon\) and define \[\begin{align} \label{eq:sphericalconversion95barf95def} \bar f(\alpha, \beta, x) := \bar\Phi\big(x, q_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) - \beta\big(\rho_0(\alpha, \beta, x) + x^2)\,, \end{align}\tag{165}\] where consider \(\bar\Phi(x,q,\rho)\) with \(u(x)\) therein such that \(\exp u(x) = \mathbf{1}\{x \ge \kappa\}\). (Here as \(0 \not\in \bar I\), we have \(\bar f = \mathrm{\small RSG}_{\bar I} - \frac{1}{2} \log(2\pi e)\), however since \(\bar I\) is technically defined in terms of \(\varepsilon''\), we will define \(\varepsilon_{\mathrm{\small RS}}\) in terms of \(\bar f\) and then consider \(0 < \varepsilon'' \le \varepsilon_{\mathrm{\small RS}}\).) We now define the following positive parameters: \[\begin{align} \bar\delta>0 &\text{ as the unique solution to } \rho_0\big(\alpha, \beta(\alpha, x) - \bar\delta, x\big) = w^2 - x^2\, ,\tag{166} \\ \bar\delta_1, \bar\delta_2 &:= \bar\delta/ 2, \tag{167}\\ \varepsilon_1 &\le \min\Big\{ \frac{1}{3} \Big( \bar f\big(\alpha, \beta(\alpha, x) - \bar\delta_1, x\big) - \big( \bar\delta_1 + \bar f\big(\alpha, \beta(\alpha, x), x\big) \big) \Big), \varepsilon\Big\} \, ,\tag{168}\\ \varepsilon_2 &\le\min\Big\{ \frac{1}{6} \underline{H}\bar\delta_2^2, \varepsilon\Big\} \, ,\tag{169} \\ \beta&:= \beta(\alpha, x) - \bar\delta_1 > \beta_0 = \frac{1}{8}\, .\tag{170} \end{align}\] Therefore, \(\bar\delta, \bar\delta_1, \bar\delta_2, \varepsilon_1, \varepsilon_2\) above depend on \(x, \varepsilon, \alpha, \beta_0, \beta_1, \kappa, \lambda\). Later on we will show \(\varepsilon_1, \varepsilon_2\) can be taken independently of \(x\). First we will justify the statements implicit in the above, including positivity, and derive some useful estimates. Recall by Lemma 23, \(\beta(\alpha, x) \ge \frac{1}{4}\). Now note:

• By definition of \(\underline{H}\), for small enough \(\varepsilon\le \min\big\{1, \frac{1}{12}\underline{H}\big\}\), we have \[\begin{align} \rho_0\big(\alpha, 1/8, x \big) &\ge \rho_0\big(\alpha, \beta(\alpha, x), x \big) + \underline{H}\big( \beta(\alpha, x) - 1/8 \big) \\ &\ge 1-x^2+3\varepsilon\\ &> w^2 - x^2 \\ &> 1-x^2 = \rho_0\big(\alpha, \beta(\alpha, x), x \big)\, . \end{align}\] As \(\rho_0(\alpha, \beta, x)\) is strictly decreasing on \([\beta_0, \beta_1]\) by Lemma 23, it follows that such a \(\bar\delta\) exists, is unique, and that \(\bar\delta>0\). This justifies 166.

• We have \[\begin{align} 1+\varepsilon\ge w &= \sqrt{\rho_0\big(\alpha, \beta(\alpha, x) - \bar\delta, x\big) +x^2 } \ge \sqrt{\rho_0\big(\alpha, \beta(\alpha, x), x \big) + x^2 + \underline{H}\bar\delta} = \sqrt{1+\underline{H}\bar\delta}\, , \end{align}\] thus as \(\varepsilon\le \frac{1}{12}\underline{H}\), we have \(\bar\delta< \frac{1}{8}\). Hence, \(\beta(\alpha, x) - \bar\delta_1 \ge \frac{1}{4} - \bar\delta_1 > \frac{1}{8}\), justifying 170.

• By Lemma 23, we have for all \(\beta\in [\beta_0, \beta_1]\) that \[\beta+ \bar f\big(\alpha, \beta, x\big) > \beta(\alpha, x) + \bar f\big(\alpha, \beta(\alpha, x), x \big)\, .\] Taking \(\beta= \beta(\alpha, x) - \bar\delta_1 > \frac{1}{8} = \beta_0\) in the above justifies \(\varepsilon_1>0\) and hence 168. Moreover by the definition of \(\varepsilon_1\), the above display gives \[\begin{align} -\bar\delta_1 + \bar f\big(\alpha, \beta(\alpha, x) - \bar\delta_1, x\big) > \bar f\big(\alpha, \beta(\alpha, x), x \big) + 3\varepsilon_1\, .\label{eq:sphericalvarproblem1} \end{align}\tag{171}\]

• Let \(F(x, q, \rho) := \bar\Phi(x, q, \rho) - \beta (\rho + x^2)\) and let \(\rho_0 = \rho_0(\alpha, \beta, x), q_0 = q_0(\alpha, \beta, x)\). Note \(\frac{\partial F}{\partial \rho}=\frac{\partial F_I}{\partial \rho}\), \(\frac{\partial F}{\partial q}=\frac{\partial F_I}{\partial q}\) for any interval \(I\), thus \(\frac{\partial F}{\partial \rho}(x, q_0, \rho_0) = \frac{\partial F}{\partial q}(x, q_0, \rho_0) = 0\). Now for all \(\beta \in [\beta_0, \beta_1]\), \[\begin{align} \frac{\partial}{\partial \beta} \bar f(\alpha, \beta, x) &= - \big( \rho_0(\alpha, \beta, x) + x^2 \big) + \frac{\partial F}{\partial \rho}(x, q_0, \rho_0) \cdot \frac{\partial \rho_0}{\partial \beta} + \frac{\partial F}{\partial q}(x, q_0, \rho_0) \cdot \frac{\partial q_0}{\partial \beta} \notag \\ &= - \big( \rho_0(\alpha, \beta, x) + x^2 \big)\,.\label{eq:fbarfirstderiv} \end{align}\tag{172}\] Thus by definition of \(\underline{H}\), we have for all \(\beta \in [\beta_0, \beta_1]\), \[\begin{align} \frac{\partial^2}{\partial \beta^2}\bar f(\alpha, \beta, x) = -\frac{\partial}{\partial \beta} \rho_0(\alpha, \beta, x) \ge \underline{H}> 0\,. \label{eq:fbarsecondderiv} \end{align}\tag{173}\] Now in what follows, let \(\beta=\beta(\alpha, x)-\bar\delta_1\) as per 170, thus \(\beta-\bar\delta_2 = \beta(\alpha, x)-\bar\delta\) as \(\bar\delta_1+\bar\delta_2=\bar\delta\). By our choice of \(w\), \(\bar\delta\) from 166, we obtain that for this choice of \(\beta=\beta(\alpha, x)-\bar\delta_1\), \[\begin{align} \bar f(\alpha, \beta, x) &\ge \bar f(\alpha, \beta-\bar\delta_2, x) + \bar\delta_2 \frac{\partial}{\partial \beta} \bar f(\alpha,\beta-\bar\delta_2, x)+\frac{1}{2} \underline{H}\bar\delta_2^2 \notag \\ &= \bar f(\alpha, \beta-\bar\delta_2, x) - \bar\delta_2 \big( \rho_0(\alpha,\beta-\bar\delta_2, x ) + x^2 \big) + \frac{1}{2}\underline{H}\bar\delta_2^2 \notag \\ &= \bar f(\alpha, \beta-\bar\delta_2, x) - \bar\delta_2 w^2 + \frac{1}{2} \underline{H}\bar\delta_2^2 \notag \\ &\ge \bar f(\alpha, \beta-\bar\delta_2, x) - \bar\delta_2 w^2 + 3\varepsilon_2\, .\label{eq:sphericalvarproblem2} \end{align}\tag{174}\]

As our last preliminary, we claim we can take \(\varepsilon_1, \varepsilon_2\), and \[\begin{align} \varepsilon_{\mathrm{\small RS}} := \min\big\{ \varepsilon_{\mathrm{\small RSG}}(\varepsilon_1, \alpha_0, \beta_0, \beta_1, \kappa, \lambda), \varepsilon_{\mathrm{\small RSG}}(\varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda) \big\} > 0 \label{eq:sphericalconversion95epsRS95def} \end{align}\tag{175}\] independently of \(x\), where \(\varepsilon_{\mathrm{\small RSG}}\) is from Theorem 17. To this end first observe \[\begin{align} w^2 - x^2 &= \rho_0\big( \alpha, \beta(\alpha, x) - \bar\delta, x \big) \le \rho_0\big( \alpha, \beta(\alpha, x), x \big) + \overline{H}\bar\delta= 1-x^2 + \overline{H}\bar\delta\,. \end{align}\] Since \(w=1+\varepsilon\), it follows that \(\bar\delta> \frac{2}{\overline{H}} \varepsilon\), and hence \(\bar\delta, \bar\delta_1, \bar\delta_2\) are lower bounded independently of \(x\). Next note \[\begin{align} \frac{\partial}{\partial \beta} \big( \beta + \bar f(\alpha, \beta, x) \big) = 1 - \big( \rho_0(\alpha, \beta, x) + x^2 \big)\,,\,\frac{\partial^2}{\partial \beta^2} \big( \beta + \bar f(\alpha, \beta, x) \big) = -\frac{\partial}{\partial \beta} \rho_0(\alpha, \beta, x) \ge \underline{H}> 0 \end{align}\] by 172, 173. Thus as \(\rho_0(\alpha, \beta(\alpha, x), x) = 1-x^2\) by Lemma 23, we have \[\begin{align} \beta(\alpha, x) - \bar\delta_1 + \bar f\big(\alpha, \beta(\alpha, x) - \bar\delta_1, x \big) &\ge \beta(\alpha, x) + \bar f\big(\alpha, \beta(\alpha, x), x \big) - \bar\delta_1 \frac{\partial}{\partial \beta} \big( \beta + \bar f(\alpha, \beta, x) \big)+ \frac{1}{2} \underline{H}\bar\delta_1^2 \\ &\ge \beta(\alpha, x) + \bar f\big(\alpha, \beta(\alpha, x), x \big) + \frac{1}{2} \underline{H}\bar\delta_1^2\,. \end{align}\] Therefore \[\begin{align} \bar f\big(\alpha, \beta(\alpha, x) - \bar\delta_1, x \big) \ge \bar\delta_1 + \bar f\big(\alpha, \beta(\alpha, x), x \big) + \frac{\underline{H}}{2} \bar\delta_1^2\,. \end{align}\] Since \(\bar\delta> \frac{2}{\overline{H}} \varepsilon\), it follows from the above display and 168 that \(\varepsilon_1\) can be taken independently of \(x\). Recalling \(\bar\delta_2\) is lower bounded independently of \(x\) and \(\underline{H}\) does not depend on \(x\), it follows that \(\varepsilon_2\) can be taken independently of \(x\). Hence \(\varepsilon_{\mathrm{\small RS}}\) can also be taken independently of \(x\).

We now turn to establishing ??. We consider any \(\varepsilon''\), \(0 < \varepsilon'' \le \varepsilon_{\mathrm{\small RS}}\), and define \(I\) as in ??. Note \(0 \not\in \bar I\) as \(|x|>\varepsilon''\). In the following proofs, we take \(\beta = \beta(\alpha, x) - \bar\delta_1\) as per 170.

8.2.0.5 Initial Bound.

Suppose \(x \ge \varepsilon''>0\). Recall \(I = [\frac{x-\varepsilon''}{w}, x+\varepsilon'']\) where \(w=1+\varepsilon\). By 156 and 158, \[\begin{align} \small\rm LHS&:= \int \mathbf{1}\big\{ \{\theta_1/\sqrt{d} \in \bar I\} \cap C \cap \{d\le \|\theta\|^2 \le w^2 d\} \big\} \exp\big(-\beta\| \theta\|^2\big)\, \mathrm{d}\theta\notag \\ &\le \exp(-\beta d) \text{Vol}\Big( \mathbf{1}\big\{\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon''] \big\} \cap C \cap \big\{ d\le \| \theta\| \le w^2 d\big\} \Big)\notag \\ &= \exp(-\beta d) \sqrt{d}\int_1^w \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[w \cdot \frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big] \Big\} \cap C \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v\notag \\ &\le \exp(-\beta d) \sqrt{d} \int_1^w \mathrm{Area}\Big( \mathbf{1}\Big\{\theta_1/\sqrt{d} \in v\Big[\frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big] \Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \notag \\ &= \exp(-\beta d) \sqrt{d} \int_1^w \mathrm{Area}\Big( \mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[\frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big] \Big\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big) v^{d-1}\, \mathrm{d}v\notag \\ &\le \exp(-\beta d)\frac{1}{\sqrt{d}} (w^d-1) \mathrm{Area}\Big( \mathbf{1}\{\theta_1/\sqrt{d} \in I \} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\, .\label{eq:sphericalconversionlowerboundstep1} \end{align}\tag{176}\] Analogously, when \(x \le -\varepsilon''<0\), we have by 156 and 158 that \[\begin{align} \small\rm LHS&\le \exp(-\beta d) \sqrt{d}\int_1^w \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[x-\varepsilon'', w \cdot \frac{x+\varepsilon''}{w} \Big] \Big\} \cap C \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\le \exp(-\beta d) \sqrt{d} \int_1^w \mathrm{Area}\Big( \mathbf{1}\Big\{\theta_1/\sqrt{d} \in v\Big[x-\varepsilon'', \frac{x+\varepsilon''}{w} \Big] \Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\le \exp(-\beta d)\frac{1}{\sqrt{d}} (w^d-1) \mathrm{Area}\Big( \mathbf{1}\{\theta_1/\sqrt{d} \in I \} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\,. \end{align}\] This yields the same inequality as 176 in the \(x<0\) case. (Note here that \(0 \ge \frac{x+\varepsilon''}{w} > x+\varepsilon''\) as \(x\le -\varepsilon''<0\).) Next, note \[\begin{align} \small\rm LHS= \mathrm{\small (I)}- \mathrm{\small (II)}- \mathrm{\small (III)}\, , \end{align}\] where \[\begin{align} \mathrm{\small (I)}&:= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\, ,\\ \mathrm{\small (II)}&:= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| \le \sqrt{d}\} \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\, , \\ \mathrm{\small (III)}&:= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| > w\sqrt{d}\} \big\}\exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\, . \end{align}\] We now lower bound \(\mathrm{\small (I)}\) and upper bound \(\mathrm{\small (II)}, \mathrm{\small (III)}\) via Theorem 17.

8.2.0.6 Lower bounding \(\mathrm{\small (I)}\):

As \(\varepsilon'' \le \varepsilon_{\mathrm{\small RS}}\), by definition of \(\varepsilon_{\mathrm{\small RS}}\) in 175, and as \(\beta = \beta(\alpha, x) \in [\beta_0, \beta_1]\) by 170, Theorem 17 applied with \(\varepsilon=\frac{1}{2} \varepsilon_1 \wedge \varepsilon_2\) and the interval \(\bar I\) implies that for \(d \ge d(\varepsilon_1, \varepsilon_2, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and probability at least \(1-\exp\big(-d / K(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda) \big)\), \[\begin{align} \mathrm{\small (I)}&= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\notag \\ &\ge \max\Big\{ \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(n/d, \beta, x) - \varepsilon_1/2 \big)d \Big), \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(n/d, \beta, x) - \varepsilon_2/2 \big) \Big) d\Big\} \notag \\ &\ge \max\Big\{ \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon_1 \big) d\Big), \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon_2 \big) d\Big) \Big\}\, .\label{eq:sphericalconversion95lowerbd95lowerbdI} \end{align}\tag{177}\] Here, we used the second part of Proposition 9 in the last inequality, following identical reasoning as the proof for the upper bound to convert from \(\mathrm{\small RSG}_{\bar I}(n/d, \beta, x)\) to \(\mathrm{\small RSG}_{\bar I}(\alpha, \beta, x)\).

8.2.0.7 Upper bounding \(\mathrm{\small (II)}\):

As \(\varepsilon'' \le \varepsilon_{\mathrm{\small RS}} \le \varepsilon_{\mathrm{\small RSG}}(\varepsilon_1, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and \(\beta \in [\beta_0, \beta_1]\), by Theorem 17, for \(d \ge d(\varepsilon_1, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and probability at least \(1-\exp\big(-d / K(\varepsilon_1, \alpha_0, \beta_0, \beta_1, \kappa, \lambda) \big)\), \[\begin{align} \mathrm{\small (II)}&= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| \le \sqrt{d}\} \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\notag \\ &= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| \le \sqrt{d}\} \big\} \exp\big( -(\beta+ \bar\delta_1) \| \theta\|^2 \big) \exp\big( \bar\delta_1 \| \theta\|^2 \big)\, \mathrm{d}\theta\notag \\ &\le \exp(\bar\delta_1 d)\int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \big\} \exp\big( -(\beta+ \bar\delta_1) \| \theta\|^2 \big)\, \mathrm{d}\theta\notag \\ &\le \exp(\bar\delta_1 d) \cdot \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(n/d, \beta+\bar\delta_1, x) + \varepsilon_1/2 \big) d \Big) \notag \\ &\le \exp(\bar\delta_1 d) \cdot \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta+\bar\delta_1, x) + \varepsilon_1 \big) d \Big) \notag \\ &= \exp\Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta+\bar\delta_1, x) + \bar\delta_1 + \varepsilon_1 \big)d \Big)\,.\label{eq:sphericalconversion95lowerbd95upperbdIIinit} \end{align}\tag{178}\] Here we again use Proposition 9 to convert from \(\mathrm{\small RSG}_{\bar I}(n/d, \beta, x)\) to \(\mathrm{\small RSG}_{\bar I}(\alpha, \beta, x)\). Now by 171 and as \(\bar f = \mathrm{\small RSG}_{\bar I} - \frac{1}{2} \log(2\pi e)\) as \(0 \not\in \bar I\), combining 177, 178 yields that for \(d \ge d(\varepsilon_1, \varepsilon_2, \varepsilon'', \alpha, \beta_0, \beta_1, \kappa, \lambda)\), with probability at least \(1-\exp\big(d / K(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda) \big)\), \[\begin{align} \label{eq:sphericalconversion95lowerbd95upperbdII} \mathrm{\small (I)}&\ge \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon_1 \big) d\Big) \notag \\ &\ge \exp(\varepsilon_1 d)\exp\Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta+\bar\delta_1, x) + \bar\delta_1 + \varepsilon_1 \big) d\Big) \ge 4\mathrm{\small (II)}\,. \end{align}\tag{179}\]

8.2.0.8 Upper bounding \(\mathrm{\small (III)}\):

As \(\varepsilon'' \le \varepsilon_{\mathrm{\small RS}} \le \varepsilon_{\mathrm{\small RSG}}(\varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and \(\beta \in [\beta_0, \beta_1]\), by Theorem 17, for \(d \ge d(\varepsilon_2, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and probability at least \(1-\exp\big(-d / K(\varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\big)\), \[\begin{align} \mathrm{\small (III)}&= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| > w\sqrt{d}\} \big\}\exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\notag \\ &= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| > w\sqrt{d}\} \big\} \exp(- (\beta- \bar\delta_2) \| \theta\|^2) \exp(-\bar\delta_2 \| \theta\|^2)\, \mathrm{d}\theta\notag \\ &\le \exp(-\bar\delta_2 w^2 d) \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I\} \cap C \big\} \exp(- (\beta- \bar\delta_2) \| \theta\|^2)\, \mathrm{d}\theta\notag \\ &\le \exp(-\bar\delta_2 w^2 d) \cdot \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(n/d, \beta-\bar\delta_2, x) + \varepsilon_2/2 \big) d \Big) \notag \\ &\le \exp(-\bar\delta_2 w^2 d) \cdot \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta-\bar\delta_2, x) + \varepsilon_2 \big) d \Big) \notag \\ &= \exp\Big( \big(\mathrm{\small RSG}_{\bar I}(\alpha, \beta-\bar\delta_2, x) - \bar\delta_2 w^2 + \varepsilon_2 \big) d\Big)\, .\label{eq:sphericalconversion95lowerbd95upperbdIIIinit} \end{align}\tag{180}\] Here, we again used Proposition 9. By 174 and as \(\bar f = \mathrm{\small RSG}_{\bar I} - \frac{1}{2} \log(2\pi e)\), we obtain that for \(d \ge d(\varepsilon_1, \varepsilon_2, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and probability at least \(1-\exp\big(-d / K(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda) \big)\), \[\begin{align} \mathrm{\small (I)}&\ge \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon_2 \big) d \Big) \notag \\ &\ge \exp(\varepsilon_2 d) \exp\Big( \big(\mathrm{\small RSG}_{\bar I}(\alpha, \beta-\bar\delta_2, x) -\bar\delta_2 w^2 + \varepsilon_2 \big) d\Big) \ge 4\mathrm{\small (III)}\,.\label{eq:sphericalconversion95lowerbd95upperbdIII} \end{align}\tag{181}\]

8.2.0.9 Finish.

Combining 179, 181, we obtain for \(d \ge d(\varepsilon_1, \varepsilon_2, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\), with probability at least \(1-\exp\big(-d / K(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\big)\), we have \[\begin{align} \small\rm LHS= \mathrm{\small (I)}- \mathrm{\small (II)}- \mathrm{\small (III)}\ge \mathrm{\small (I)}- \frac{1}{4} \mathrm{\small (I)}- \frac{1}{4} \mathrm{\small (I)}= \frac{1}{2} \mathrm{\small (I)}\,. \end{align}\] Combining the above display with 176 and 177 gives for \(d \ge d(\varepsilon_1, \varepsilon_2, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\), with probability at least \(1-\exp\big(-d / K(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\big)\), \[\begin{align} \mathrm{Area}\Big( \mathbf{1}\{\theta_1/\sqrt{d} \in I \} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big) &\ge \frac{\sqrt{d}}{w^d-1} \cdot \exp(\beta d) \cdot \frac{1}{2} \mathrm{\small (I)}\notag \\ &\ge \frac{\sqrt{d}}{2} \exp\Big( \big(- \log w + \beta+ \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon\big) d \Big)\, ,\label{eq:sphericalconversionlowerboundstep2} \end{align}\tag{182}\] where we recall that \(\varepsilon_1, \varepsilon_2 \le \varepsilon\). Recall \(\beta\in [\beta_0, \beta_1]\), so by Lemma 23 and as \(0 \not\in \bar I\), \[\beta+ \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) \ge \inf_{q \in [0,1)} \Phi(x, q) + \frac{1}{2} \log(2e\pi)\, .\] Since \(\log w \le w-1 \le \varepsilon\), we obtain for the same \(d\) and the same probability as 182, \[\begin{align} \label{eq:sphericalconversionlowerbound95step3} \mu_d\Big( \mathbf{1}\{\theta_1/\sqrt{d} \in I \} \cap C \Big) \mathrm{Area}(\mathbb{S}^{d-1}(\sqrt{d})) \ge \frac{\sqrt{d}}{2} \exp\Big( \Big(\inf_{q \in [0,1)} \Phi(x, q) + \frac{1}{2}\log (2 e \pi) - 2\varepsilon\Big) d \Big)\,. \end{align}\tag{183}\] Again recall \(\lim_{d\rightarrow\infty} \frac{1}{d} \log \mathrm{Area}(\mathbb{S}^{d-1}(\sqrt{d})) = \frac{1}{2} \log(2e\pi)\), and that \(\varepsilon_1, \varepsilon_2\) depend only on \(\varepsilon\), \(\alpha\), \(\beta_0, \beta_1\), \(\kappa\), \(\lambda\) and do not depend on \(x\) as justified earlier. Rearranging 183 yields for \(d \ge d(\varepsilon, \varepsilon'', \alpha, \beta_0, \beta_1, \kappa, \lambda)\) and probability at least \(1-\exp\big(-d / K(\varepsilon, \alpha, \beta_0, \beta_1, \kappa, \lambda) \big)\), \[\begin{align} \frac{1}{d} \log \mu_d\Big( \mathbf{1}\{\theta_1/\sqrt{d} \in I \}\cap C \Big) \ge \inf_{q \in [0,1)} \Phi(x, q) - 4\varepsilon\, . \end{align}\] Taking \(\varepsilon\leftarrow \varepsilon/4\) completes the proof of ??.

8.3 Proof of Theorem 22 for interpolators: \(\kappa\ge 0\)↩︎

Again, we let \(\bar I := [x-\varepsilon'', x+\varepsilon'']\), and we still have \(0 \not\in \bar I\) as \(|x| > \varepsilon''\). In this proof many details are analogous to Appendix 8.2 above and we only highlight the differences. The notation in the following is also identical to Appendix 8.2. Since \(\kappa\ge 0\), 155 now yields the comparison inequalities \[\begin{align} \label{eq:intersection95containment95positivemargin} vC \subseteq C \text{ for } v \ge 1\quad , \quad vC \supseteq C \text{ for } v \le 1\,. \end{align}\tag{184}\] Now for any interval \([a,b]\), we have \[\begin{align} &\text{For 1 \le v \le w}:\quad v[a, b] \subseteq [a, bw]\text{ if b \ge a \ge 0}\quad , \quad v[a,b] \subseteq [aw, b]\text{ if a \le b \le 0}\,,\tag{185} \\ &\text{For w \le v \le 1}: \quad v[a, b] \supseteq [a, bw]\text{ if b \ge a \ge 0}\quad , \quad v[a,b] \supseteq [aw, b]\text{ if a \le b \le 0}\,.\tag{186} \end{align}\]

8.3.0.1 Proof of ??:

Let \(w=1+\varepsilon''\) for the proof of this upper bound. For any \(\beta \in [\beta_0, \beta_1]\), we obtain the following from 184, 185. When \(x > \varepsilon''\) we have for \(d \ge d(\varepsilon'')\), \[\begin{align} \small\rm LHS&:= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I\} \cap C \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\\ &\ge \exp(-\beta w^2 d)\sqrt{d}\int_1^w \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon'']\Big\} \cap C \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\ge \exp(-\beta w^2 d)\sqrt{d}\int_1^w \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in v \Big[ x-\varepsilon'', \frac{x+\varepsilon''}{w} \Big]\Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\ge \exp(-\beta w^2 d)\, \mathrm{Area}\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \frac{1}{2\sqrt{d}}\,. \end{align}\] Similarly when \(x<-\varepsilon''\), for \(d \ge d(\varepsilon'')\) we have \[\begin{align} \small\rm LHS&\ge \exp(-\beta w^2 d)\sqrt{d}\int_1^w \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon'']\Big\} \cap C \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\ge \exp(-\beta w^2 d)\sqrt{d}\int_1^w \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in v \Big[ \frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big]\Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\ge \exp(-\beta w^2 d)\, \mathrm{Area}\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \frac{1}{2\sqrt{d}}\,. \end{align}\] In either case, applying Theorem 17 with the interval \(\bar I\), we have for \(d \ge d(\varepsilon, \varepsilon'', \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and with probability at least \(1-\exp\big(- d / K(\varepsilon, \alpha_0, \beta_0, \beta_1, \kappa, \lambda) \big)\), \[\begin{align} \label{eq:sphericalconversion95upperbound95whpbound} &\frac{1}{d} \log\bigl( \small\rm LHS\big) \in \Big[ \mathrm{\small RSG}_{\bar I}(n/d, \beta, x) - \varepsilon, \mathrm{\small RSG}_{\bar I}(n/d, \beta, x) + \varepsilon\Big]\, . \end{align}\tag{187}\] We apply the second part of Proposition 9 identically as the proof in the \(\kappa< 0\) case to convert the first argument of \(\mathrm{\small RSG}_{\bar I}(n/d, \beta, x)\) to \(\mathrm{\small RSG}_{\bar I}(\alpha, \beta, x)\) for \(d \ge d(\varepsilon, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\). We obtain for the same \(d\) and the same probability as 187, \[\begin{align} &\frac{1}{d} \log \mu_d\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \Big) \le \beta w^2 + \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) + K\varepsilon- \frac{1}{d} \log \mathrm{Area}(\mathbb{S}^{d-1}(\sqrt{d})) + \frac{1}{d} \log(2\sqrt{d})\,. \end{align}\] We now take \(\beta=\beta(\alpha, x)\) in the above, use Lemma 23 and the fact that \(0 \not\in \bar I\), and finish identically to the proof of the upper bound in the \(\kappa< 0\) case. Here we account for the presence of \(\beta w^2\) rather than \(\beta\) by noting \(\beta (w^2-1) \le 3\varepsilon'' \beta_1 \le 30 \varepsilon\). This proves ?? for the \(\kappa\ge 0\) case.

8.3.0.2 Proof of ??:

We let \(w = 1 - \varepsilon\). We define \(\underline{H}= \underline{H}(\alpha, \kappa, \lambda)\), \(\overline{H}= \overline{H}(\alpha, \kappa, \lambda)\) identically as 163, 164 and define \(\bar f\) identically as 165. We now let \[\begin{align} \bar\delta= \bar\delta(\varepsilon, \alpha, \beta_0, \beta_1, \kappa, \lambda) := \min\Big\{\frac{1}{4}, \frac{1}{2\overline{H}} \varepsilon\Big\}\,. \end{align}\] By definition of \(\overline{H}\) and as \(\frac{\partial}{\partial \beta}\rho_0(\alpha, \beta, x)<0\) by Lemma 23, it follows that uniformly in \(x \in [-1, 1]\), \[\begin{align} \big| \rho_0(\alpha, \beta(\alpha, x), x) - \rho_0(\alpha, \beta(\alpha, x) + 2\bar\delta, x) \big| \le \varepsilon\,, \end{align}\] and hence by Lemma 23, \[\begin{align} \rho_0(\alpha, \beta(\alpha, x) + 2\bar\delta, x) \ge 1-x^2-\varepsilon\,.\label{eq:spherical95conversion95marginpositive95rhoineq} \end{align}\tag{188}\] Also note \(2\bar\delta+\beta(\alpha, x) < \beta_1=10\), where we use that \(\beta(\alpha, x) \le 9\). By 172, 173, and Lemma 23, we obtain \[\begin{align} \bar f(\alpha, \beta(\alpha, x) + \bar\delta, x) &\ge \bar f(\alpha, \beta(\alpha, x), x) + \bar\delta\frac{\partial}{\partial \beta} \bar f(\alpha, \beta(\alpha, x), x) + \frac{1}{2} \underline{H}\bar\delta^2 \notag \\ &= \bar f(\alpha, \beta(\alpha, x), x) - \bar\delta\big( \rho_0(\alpha, \beta(\alpha, x), x) + x^2 \big) + \frac{1}{2} \underline{H}\bar\delta^2 \notag \\ &= \bar f(\alpha, \beta(\alpha, x), x) - \bar\delta+ \frac{1}{2} \underline{H}\bar\delta^2\,. \label{eq:spherical95conversion95marginpositive95ineq951} \end{align}\tag{189}\] Similarly we obtain \[\begin{align} \bar f(\alpha, \beta(\alpha, x) + \bar\delta, x) &\ge \bar f(\alpha, \beta(\alpha, x) + 2\bar\delta, x) - (-\bar\delta) \big( \rho_0(\alpha, \beta(\alpha, x) + 2\bar\delta, x) + x^2 \big) + \frac{1}{2} \underline{H}\bar\delta^2 \notag \\ &\ge \bar f(\alpha, \beta(\alpha, x) + 2\bar\delta, x) + \bar\delta(1-\varepsilon) + \frac{1}{2} \underline{H}\bar\delta^2 \notag \\ &\ge \bar f(\alpha, \beta(\alpha, x) + 2\bar\delta, x) + \bar\delta w^2 + \frac{1}{2} \underline{H}\bar\delta^2\,,\label{eq:spherical95conversion95marginpositive95ineq95w} \end{align}\tag{190}\] where we used 188 and \(w=1-\varepsilon\) combined with \(\varepsilon<1\). Finally, we let \[\begin{align} \varepsilon_1, \varepsilon_2 &:= \min\Big\{ \frac{1}{6} \underline{H}\bar\delta^2, \varepsilon\Big\}\,, \tag{191} \\ \varepsilon_{\mathrm{\small RS}} &:= \min\big\{ \varepsilon_{\mathrm{\small RSG}}(\varepsilon_1, \alpha_0, \beta_0, \beta_1, \kappa, \lambda), \varepsilon_{\mathrm{\small RSG}}(\varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda) \big\} > 0\,.\tag{192} \end{align}\] We now turn to establishing ??. We consider any \(\varepsilon''\), \(0 < \varepsilon'' \le \varepsilon_{\mathrm{\small RS}}\), and define \(I\) as in ??. Thus \(0 \not \in \bar I\) as \(|x| > \varepsilon''\). We now let \(\beta=\beta(\alpha, x)+\bar\delta\) for the rest of this proof. First suppose \(x \ge \varepsilon'' > 0\). Here we have by 184, 186 that \[\begin{align} \small\rm LHS&:= \int \mathbf{1}\big\{ \{\theta_1/\sqrt{d} \in \bar I\} \cap C \cap \{w^2 d\le \|\theta\|^2 \le d\} \big\} \exp\big(-\beta\| \theta\|^2\big)\, \mathrm{d}\theta\notag \\ &\le \exp(-\beta w^2 d) \text{Vol}\Big( \mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[x-\varepsilon'', w \cdot \frac{x+\varepsilon''}{w} \Big] \Big\} \cap C \cap \{ w^2 d\le \| \theta\| \le d\} \Big)\notag \\ &\le \exp(-\beta w^2 d) \sqrt{d} \int_w^1 \mathrm{Area}\Big( \mathbf{1}\Big\{\theta_1/\sqrt{d} \in v\Big[x-\varepsilon'', \frac{x+\varepsilon''}{w} \Big] \Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \notag \\ &\le \exp(-\beta w^2 d)\frac{1}{\sqrt{d}} \mathrm{Area}\Big( \mathbf{1}\{\theta_1/\sqrt{d} \in I \} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\, .\label{eq:sphericalconversionlowerboundstep195marginpositive} \end{align}\tag{193}\] Analogously, when \(x \le -\varepsilon''<0\), we have \[\begin{align} \small\rm LHS&\le \exp(-\beta w^2 d) \sqrt{d}\int_w^1 \mathrm{Area}\Big(\mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[w \cdot \frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big] \Big\} \cap C \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\le \exp(-\beta w^2 d) \sqrt{d} \int_w^1 \mathrm{Area}\Big( \mathbf{1}\Big\{\theta_1/\sqrt{d} \in v\Big[ \frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big] \Big\} \cap vC \cap v\mathbb{S}^{d-1}(\sqrt{d}) \Big)\, \mathrm{d}v \\ &\le \exp(-\beta w^2 d)\frac{1}{\sqrt{d}} \mathrm{Area}\Big( \mathbf{1}\{\theta_1/\sqrt{d} \in I \} \cap C \cap \mathbb{S}^{d-1}(\sqrt{d}) \Big)\,. \end{align}\] (Note here that \(0 \ge x-\varepsilon'' > \frac{x-\varepsilon''}{w}\).) Now note \[\begin{align} \small\rm LHS= \mathrm{\small (I)}- \mathrm{\small (II)}- \mathrm{\small (III)}\, , \end{align}\] where \[\begin{align} \mathrm{\small (I)}&:= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\, ,\\ \mathrm{\small (II)}&:= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| \ge \sqrt{d}\} \big\} \exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\, , \\ \mathrm{\small (III)}&:= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| \le w\sqrt{d}\} \big\}\exp(-\beta\| \theta\|^2)\, \mathrm{d}\theta\, . \end{align}\] We again lower bound \(\mathrm{\small (I)}\) and upper bound \(\mathrm{\small (II)}, \mathrm{\small (III)}\) via Theorem 17. First, by Theorem 17 with interval \(\bar I\) and the second part of Proposition 9, as \(\varepsilon'' \le \varepsilon_{\mathrm{\small RS}}\) and \(\beta \in [\beta_0, \beta_1]\), we have for \(d \ge d(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and probability at least \(1 - \exp\big( - d / K(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\big)\), \[\begin{align} \mathrm{\small (I)}\ge \max\Big\{ \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon_1 \big) d \Big), \exp \Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon_2 \big) d \Big) \Big\}\, . \end{align}\] By Theorem 17 and Proposition 9, for the same \(d\) and with the same probability, \[\begin{align} \mathrm{\small (II)}&= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| \ge \sqrt{d}\} \big\} \exp(-(\beta-\bar\delta) \| \theta\|^2) \exp(-\bar\delta\| \theta\|^2) \, \mathrm{d}\theta\\ &\le \exp(-\bar\delta d) \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \big\} \exp(-(\beta-\bar\delta) \| \theta\|^2) \, \mathrm{d}\theta\\ &\le \exp\Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta - \bar\delta, x) - \bar\delta+ \varepsilon_1 \big) d \Big)\,. \end{align}\] Analogously, for the same \(d\) and with the same probability, \[\begin{align} \mathrm{\small (III)}&= \int \mathbf{1}\big\{\{\theta_1/\sqrt{d} \in \bar I \} \cap C \cap \{ \| \theta\| \le w\sqrt{d}\} \big\}\exp(- (\beta+ \bar\delta) \| \theta\|^2) \exp(\bar\delta\| \theta\|^2)\, \mathrm{d}\theta\\ &\le \exp\Big( \big( \mathrm{\small RSG}_{\bar I}(\alpha, \beta+\bar\delta, x) + \bar\delta w^2 + \varepsilon_2 \big) d \Big)\,. \end{align}\] Recall \(\beta-\bar\delta= \beta(\alpha, x)\) and \(\bar f = \mathrm{\small RSG}_{\bar I} - \frac{1}{2} \log(2\pi e)\) as \(0 \not \in \bar I\). Thus applying 189, 190 to upper bound \(\mathrm{\small (II)}\), \(\mathrm{\small (III)}\) respectively gives for \(d \ge d(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\) and probability at least \(1 - \exp\big( - d / K(\varepsilon_1, \varepsilon_2, \alpha_0, \beta_0, \beta_1, \kappa, \lambda)\big)\), we have \(\mathrm{\small (II)}, \mathrm{\small (III)}\le \frac{1}{4} \mathrm{\small (I)}\). Therefore as \(\varepsilon_1, \varepsilon_2 \le \varepsilon\), for the same \(d\) and with the same probability, \[\begin{align} \small\rm LHS\ge \frac{1}{2} \mathrm{\small (I)}\ge \frac{1}{2} \exp\Big( \big(\mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon\big) d\Big)\,. \notag \end{align}\] Via the same steps as the \(\kappa< 0\) case, combining the above display with 193 yields that for the same \(d\) and with the same probability, \[\begin{align} \frac{1}{d} \log \mu_d\Big(\mathbf{1}\{\theta_1/\sqrt{d} \in I\} \cap C \Big) + \frac{1}{d} \log \mathrm{Area}(\mathbb{S}^{d-1}(\sqrt{d})) \ge \beta w^2 + \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) - \varepsilon+ \frac{1}{d} \log \Big(\frac{\sqrt{d}}{2}\Big)\,. \end{align}\] Note that as \(\beta \le \beta_1 = 10\), we have \(\beta w^2 \ge \beta - 3\beta \varepsilon\ge \beta - 30 \varepsilon\). Finally, as \(0 \not\in \bar I\), we recall \(\beta + \mathrm{\small RSG}_{\bar I}(\alpha, \beta, x) \ge \inf_{q \in [0,1)} \Phi(x, q)\) by Lemma 23. Combining these steps with the above display and taking \(\varepsilon\leftarrow \varepsilon/K\) for universal constant \(K\), ?? follows.

8.4 Proof of Theorem 23 for posterior↩︎

Much of this proof is identical to the above and we will only highlight the differences. We again define \(\bar I := [x-\varepsilon'', x+\varepsilon'']\) and follow the same notation as Appendices 8.2, 8.3. Similarly as before, we parametrize \(\mathbb{R}^d\) by the scalar \(v = \|\theta\|/\sqrt{d}\) and \(\theta \in \mathbb{S}^{d-1}(\sqrt{d})\).

By Lipschitzness of \(u(x)\), instead of the comparison inequalities relating \(vC\) and \(C\), we directly study how \(u\big( (s_i \theta_1 + \langle g_i , \bar\theta\rangle) / \sqrt{d} \big)\) changes in \(v\) via the following Lemma.

We now have the technical ingredients in place to prove Theorem 23.

8.4.0.1 Proof of ??:

Let \(K'(\lambda) := K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}(\lambda)\), where \(K'\) is as in the statement of Theorem. We thus consider \(\varepsilon'' \le \min\{ \varepsilon/ K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}(\lambda), \varepsilon_{\mathrm{\small RSG}}\}\) and let \(I\) be as per ??. Let \(w=1+\varepsilon''\).

For any \(\beta \in [\beta_0, \beta_1]\), by 185, we obtain the following, very similarly to the proof of ??. When \(x > \varepsilon''\), we have for \(d \ge d(\varepsilon'')\), \[\begin{align} \small\rm LHS&:= \int \mathbf{1}\{\theta_1/\sqrt{d} \in \bar I\} \exp\Big( \sum_{i=1}^n u\big(S_i(\theta)\big)-\beta\| \theta\|^2 \Big)\, \mathrm{d}\theta\\ &\ge \int \mathbf{1}\Big\{ \big\{\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon''] \big\} \cap \big\{d \le \|\theta\|^2 \le w^2 d \big\} \Big\} \exp\Big( \sum_{i=1}^n u\big(S_i(\theta)\big)-\beta\| \theta\|^2 \Big)\, \mathrm{d}\theta\\ &\ge \exp(-\beta w^2 d)\sqrt{d}\int_1^w \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\big\{v\theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon'']\big\} v^{d-1} \exp\Big( \sum_{i=1}^n u\big(S_i(v\theta)\big) \Big) \, \mathrm{d}\theta \mathrm{d}v \\ &\ge \exp(-\beta w^2 d)\sqrt{d}\int_1^w \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[ x-\varepsilon'', \frac{x+\varepsilon''}{w} \Big] \Big\} v^{d-1} \exp\Big( \sum_{i=1}^n u\big(S_i(v\theta)\big) \Big) \, \mathrm{d}\theta \mathrm{d}v \,, \end{align}\] where the last inequality uses 185. When \(x < -\varepsilon''\), we have for \(d \ge d(\varepsilon'')\), now using 185 in the \(a \le b \le 0\) case, \[\begin{align} \small\rm LHS\ge \exp(-\beta w^2 d)\sqrt{d}\int_1^w \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[ \frac{x-\varepsilon''}{w}, x+\varepsilon''\Big] \Big\} v^{d-1} \exp\Big( \sum_{i=1}^n u\big(S_i(v\theta)\big) \Big) \, \mathrm{d}\theta \mathrm{d}v \,. \end{align}\] By Lemma 24, with probability at least \(1-\exp\big( -d / K(\lambda) \big)\), we have for all \(\theta \in \mathbb{S}^{d-1}(\sqrt{d})\) and all \(v, 1 \le v \le w\) that \[\begin{align} \Big| \sum_{i=1}^n u\big( S_i(v \theta) \big) - \sum_{i=1}^n u\big( S_i(\theta) \big) \Big| \le K_{\mathrm{\ref{lem:posterior95spherical95continuity}}} |v-1| d \le \varepsilon d\,, \end{align}\] where we use that \(1 \le v \le w \le 1+\varepsilon/K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}\). Combining the above displays and recalling the definition of \(I\) in ?? yields that for \(d \ge d(\varepsilon'')\), with probability at least \(1-\exp\big( d / K(\lambda) \big)\), \[\begin{align} \small\rm LHS&\ge \exp \big(-\beta w^2 d - \varepsilon d \big) \sqrt{d} \int_1^w \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\big\{ \theta_1/\sqrt{d} \in I \big\} v^{d-1} \exp\Big(\sum_{i=1}^n u\big( S_i(\theta) \big) \Big)\, \mathrm{d}\theta \mathrm{d}v \notag \\ &\ge \frac{\exp \big(-\beta w^2 d - \varepsilon d \big)}{2\sqrt{d}} \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\big\{ \theta_1/\sqrt{d} \in I \big\} \exp\Big(\sum_{i=1}^n u\big( S_i(\theta) \big) \Big)\, \mathrm{d}\theta\,.\notag \end{align}\] That is, \[\begin{align} \label{eq:posterior95spherical95upperbd95main} \frac{1}{d} \log Z(I) \le \frac{1}{d} \log(\small\rm LHS) + \frac{1}{d} \log(2\sqrt{d}) + \beta w^2 + \varepsilon\,. \end{align}\tag{198}\]

With 198, the rest of the proof of ?? now follows identically as the proof of ??, the one difference being that we apply Theorem 18 rather than Theorem 23 to control \(\frac{1}{d} \log(\small\rm LHS)\).

8.4.0.2 Proof of ??:

Let \(K_{\mathrm{\ref{lem:posterior95spherical95continuity}}} = K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}(\lambda) \ge 1\), and \(w=1- \frac{\varepsilon}{K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}}\). Recall that Lemma 23, Proposition 9 still hold here, where the RS equations are given in terms of \(u(x)\) rather than the hard indicator \(\mathbf{1}\{\cdot \ge \kappa\}\). Thus we may perform the following steps.

In particular, define \(\underline{H}, \overline{H}\) as in 163, 164. We now define \[\begin{align} \label{eq:posterior95sphericalconversion95barf95def} \bar f(\alpha, \beta, x) := \bar\Phi\big(x, q_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) - \beta\big(\rho_0(\alpha, \beta, x) + x^2)\,, \end{align}\tag{199}\] where consider \(\bar\Phi(x,q,\rho)\) given with \(u(x)\) (rather than the hard indicator function \(\mathbf{1}\{\cdot \ge \kappa\}\) for the interpolators). We now let \[\begin{align} \bar\delta= \bar\delta(\varepsilon, \alpha, \beta_0, \beta_1, \lambda) := \min\Big\{\frac{1}{4}, \frac{1}{2\overline{H}K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}} \varepsilon\Big\}\,. \end{align}\] Analogously as the proof of 188, we have uniformly in \(x \in [-1, 1]\): \[\begin{align} \rho_0(\alpha, \beta(\alpha, x) + 2\bar\delta, x) \ge 1-x^2-\frac{\varepsilon}{K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}}\,.\label{eq:posterior95spherical95conversion95marginpositive95rhoineq} \end{align}\tag{200}\] Again analogously the proof of 189, 190, now using 200 and \(\varepsilon<1, K_{\mathrm{\ref{lem:posterior95spherical95continuity}}} \ge 1\), we obtain \[\begin{align} \bar f(\alpha, \beta(\alpha, x) + \bar\delta, x) &\ge \bar f(\alpha, \beta(\alpha, x), x) - \bar\delta+ \frac{1}{2} \underline{H}\bar\delta^2\,, \tag{201} \\ \bar f(\alpha, \beta(\alpha, x) + \bar\delta, x) &\ge \bar f(\alpha, \beta(\alpha, x) + 2\bar\delta, x) + \bar\delta w^2 + \frac{1}{2} \underline{H}\bar\delta^2\,.\tag{202} \end{align}\] Finally, we again let \[\begin{align} \varepsilon_1 = \varepsilon_2 &:= \min\Big\{ \frac{1}{6} \underline{H}\bar\delta^2, \varepsilon\Big\}\,, \tag{203} \\ \varepsilon_{\mathrm{\small RS}} &:= \min\big\{ \varepsilon_{\mathrm{\small RSG}}(\varepsilon_1, \alpha_0, \beta_0, \beta_1, \lambda), \varepsilon_{\mathrm{\small RSG}}(\varepsilon_2, \alpha_0, \beta_0, \beta_1, \lambda) \big\} > 0\,,\tag{204} \end{align}\] where now \(\varepsilon_{\mathrm{\small RSG}}\) comes from Theorem 18.

We now turn to establishing ??. Again, consider any \(\varepsilon''\), \(0 < \varepsilon'' \le \varepsilon_{\mathrm{\small RS}}\), and define \(I\) as in ??. Thus \(0 \not \in \bar I\) as \(|x| > \varepsilon''\). We now let \(\beta=\beta(\alpha, x)+\bar\delta\) for the rest of this proof. First suppose \(x \ge \varepsilon'' > 0\). Here we have by 186 that \[\begin{align} \small\rm LHS&:= \int \mathbf{1}\big\{ \{\theta_1/\sqrt{d} \in \bar I\} \cap \{w^2 d\le \|\theta\|^2 \le d\} \big\} \exp\Big( \sum_{i=1}^n u\big( S_i(\theta) \big) -\beta\| \theta\|^2\Big)\, \mathrm{d}\theta\notag \\ &\le \exp(-\beta w^2 d) \sqrt{d} \int_w^1 \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\big\{v \theta_1/\sqrt{d} \in [x-\varepsilon'', x+\varepsilon''] \big\} v^{d-1} \exp\Big( \sum_{i=1}^n u\big( S_i(v\theta) \big) \Big)\, \mathrm{d}\theta\mathrm{d}v \notag \\ &\le \exp(-\beta w^2 d) \sqrt{d} \int_w^1 \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\Big\{ \theta_1/\sqrt{d} \in \Big[ x-\varepsilon'', \frac{x+\varepsilon''}{w} \Big] \Big\} v^{d-1} \exp\Big( \sum_{i=1}^n u\big( S_i(v\theta) \big) \Big)\, \mathrm{d}\theta\mathrm{d}v \, .\notag \end{align}\] Analogously, when \(x \le -\varepsilon''<0\), we have \[\begin{align} \small\rm LHS&\le \exp(-\beta w^2 d) \sqrt{d} \int_w^1 \mathbf{1}\Big\{\theta_1/\sqrt{d} \in \Big[ \frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big] \Big\} v^{d-1} \exp\Big( \sum_{i=1}^n u\big( S_i(v\theta) \big) \Big)\, \mathrm{d}\theta\mathrm{d}v \, . \end{align}\] By Lemma 24, with probability at least \(1-\exp\big( -d / K(\lambda) \big)\), we have for all \(\theta \in \mathbb{S}^{d-1}(\sqrt{d})\) and all \(v, w \le v \le 1\) that \[\begin{align} \Big| \sum_{i=1}^n u\big( S_i(v \theta) \big) - \sum_{i=1}^n u\big( S_i(\theta) \big) \Big| \le K_{\mathrm{\ref{lem:posterior95spherical95continuity}}} |v-1| d \le \varepsilon d\,, \end{align}\] where we use that \(1-\varepsilon/K_{\mathrm{\ref{lem:posterior95spherical95continuity}}}=w \le v \le 1\). Note as \(K_{\mathrm{\ref{lem:posterior95spherical95continuity}}} \ge 1\), \(w \ge 1-\varepsilon\). Therefore by the definition of \(I\) in ??, \[\begin{align} \Big[ x-\varepsilon'', \frac{x+\varepsilon''}{w} \Big] \subseteq I \text{ when } x \ge \varepsilon''\,,\, \Big[ \frac{x-\varepsilon''}{w}, x+\varepsilon'' \Big] \subseteq I \text{ when }x \le -\varepsilon''\,. \end{align}\] Combining the above displays now yields that with probability at least \(1-\exp\big( d / K(\lambda) \big)\), \[\begin{align} \small\rm LHS&\le \exp \big(-\beta w^2 d + \varepsilon d \big) \sqrt{d} \int_w^1 \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\big\{ \theta_1/\sqrt{d} \in I \big\} v^{d-1} \exp\Big(\sum_{i=1}^n u\big( S_i(\theta) \big) \Big)\, \mathrm{d}\theta \mathrm{d}v \notag \\ &\le \frac{\exp \big(-\beta w^2 d + \varepsilon d \big)}{\sqrt{d}} \int_{\mathbb{S}^{d-1}(\sqrt{d})} \mathbf{1}\big\{ \theta_1/\sqrt{d} \in I \big\} \exp\Big(\sum_{i=1}^n u\big( S_i(\theta) \big) \Big)\, \mathrm{d}\theta\,.\notag \end{align}\] That is, \[\begin{align} \label{eq:posterior95spherical95lowerbd95main} \frac{1}{d} \log Z(I) \ge \frac{1}{d} \log(\small\rm LHS) + \frac{1}{d} \log \sqrt{d} + \beta w^2 - \varepsilon\,. \end{align}\tag{205}\]

With 205, the rest of the proof of ?? now follows identically as the proof of ?? in the \(\kappa\ge 0\) case. We again write \[\begin{align} \small\rm LHS= \mathrm{\small (I)}- \mathrm{\small (II)}- \mathrm{\small (III)}\,, \end{align}\] where now \(\mathbf{1}\{C\}\) in the definition of \(\mathrm{\small (I)}, \mathrm{\small (II)}, \mathrm{\small (III)}\) is replaced by \(\exp\big( \sum_{i=1}^n u(S_i(\theta))\big)\). (Observe that in the proof of ??, \(C\) takes the same form, for \(u(x) = \mathbf{1}\{x \ge \kappa\}\).) We now apply Theorem 18 to establish high-probability formulas for \(\mathrm{\small (I)}, \mathrm{\small (II)}, \mathrm{\small (III)}\) up to accuracy \(\varepsilon_1, \varepsilon_2\), where \(\varepsilon_1, \varepsilon_2\) are as defined in 203. Combined with 201, 202, this proves that \[\begin{align} \frac{1}{4} \mathrm{\small (I)}\ge \mathrm{\small (II)}, \mathrm{\small (III)}\,. \end{align}\] Combining with 205 and finishing as in the proof of ?? now establishes ??.

9 Technical results for proof of Theorems 7, 8↩︎

Here we prove the intermediate technical results Lemma 2, Lemma 4, and Proposition 11 on the interpolation argument and concentration of measure, used in the proof of Theorems 7 and 8. Throughout Appendix 9, for the interpolators we let \(D\) be as stated in Theorem 7, and for the posterior we recall that \(|u^{l}| \le D=D(\lambda)\) for \(l=1,2,3,4\). Also here in Appendix 9, as per the proof for the interpolators, we will always write dependence on \(\kappa\) in \(K\) when it is present in the following proofs; note there is no such dependence for the posterior.

We first prove Lemma 2, which lets us ‘transfer’ expectations of the form \(\nu_{t,v}(f)\) for \(0 \le v \le 1\) to expectations \(\nu_{t,1}(f)\) when \(v=1\), using some of the ideas from cavity in \(n\). We then finish the cavity in \(n\) argument and execute the cavity in \(d\) argument to prove Lemma 4, which gives us control over the derivatives \(\big| \frac{\mathrm{d}}{\mathrm{d}t} \nu_t\big( \theta_{d}^1 \theta_{d}^2 \big) \big|\), \(\big| \frac{\mathrm{d}}{\mathrm{d}t} \nu_t\big( (\theta_{d}^1)^2 \big) \big|\) arising in the interpolation argument. Both these arguments will crucially use Proposition 11 on concentration of the interpolating Gibbs measure \(\nu_{t,v}(\cdot)\), which we prove later in Appendix 9.3. The proof of Proposition 11 will crucially use classical results on concentration of Lipschitz functions of strongly log-concave measures; note the quadratic component \(-\beta \| \theta \|^2\) we added when relaxing to the Gaussian measure is strongly concave and \(u(\cdot)\) in Theorem 7 is concave.

9.1 Proof of Lemma 2↩︎

Our first step will be to establish the following on the derivative of \(\nu_{t,v}\) w.r.t. \(v\).

For proving Lemma 2 we will only need Lemma 25 with \(B_v = 1\). However the full generality where \(B_v\) equals 1, \(u'(S_{n, t, v}^1) u'(S_{n, t, v}^2) = u'(S_v^1) u'(S_v^2)\), or \(u''(S_v^1) + u'(S_v^1)^2\) will be needed in proving Lemma 4 later, specifically in the proof of Lemma 28.

We will also use the following variant of Grönwall’s Inequality:

Now we return to the proof of Lemma 2. By the second part of Proposition 11, \[\begin{align} \nu_{t,v}\Big( \Big\{ \big|R_{\ell, \ell} - \rho_{n, d}\big| \ge K(D, \beta_0, \beta_1, \kappa, \lambda) \Big\} \Big) &\le K\exp(-N)\,, \\ \nu_{t,v}\Big( \Big\{ \big|R_{\ell_1,\ell_2} - q_{n, d}\big| \ge K(D, \beta_0, \beta_1, \kappa, \lambda) \Big\} \Big) &\le K\exp(-N)\text{ for }\ell_1 \neq \ell_2\,. \end{align}\] Here to bound \(\rho_{n,d}, q_{n,d}\) we apply Proposition 11 with \(t=v=1\). Additionally, the second pat of Proposition 11 combined with Lemma 3 implies that \[\begin{align} \nu_{t,v}\big( (R_{\ell, \ell} - \rho_{n, d})^4 \big)^{1/4}\,,\,\nu_{t,v}\big( (R_{\ell_1,\ell_2} - q_{n, d})^4 \big)^{1/4} \le K(D, \beta_0, \beta_1, \kappa, \lambda)\,. \end{align}\] Now Hölder’s Inequality implies that \[\begin{align} &\nu_{t,v}\big( |f| \big|R_{\ell, \ell} - \rho_{n, d}\big| \big) \\ &\quad \le K(D,\beta_0,\beta_1, \kappa, \lambda)\nu_{t,v}\big( |f| \mathbf{1}\{ |R_{\ell, \ell} - \rho_{n, d}| \le K(D, \beta_0, \beta_1, \kappa, \lambda) \} \big) \\ &\qquad \qquad + K(D,\beta_0,\beta_1, \kappa, \lambda) \nu_{t,v}\big( f^2 \big)^{1/2} \nu_{t,v}\big( \big|R_{\ell, \ell} - \rho_{n, d}\big|^4 \big)^{1/4} \nu_{t,v}\big( \mathbf{1}\{ |R_{\ell, \ell} - \rho_{n, d}| \le K(D, \beta_0, \beta_1, \kappa, \lambda)\} \big)^{1/4} \\ &\quad \le K(D,\beta_0,\beta_1, \kappa, \lambda) \nu_{t,v}\big( |f| \big) + K(D,\beta_0,\beta_1, \kappa, \lambda) \exp(-N) \nu_{t,v}\big( f^2 \big)^{1/2}\, . \end{align}\] The same argument as above establishes the same upper bound on \(\nu_{t,v}\big( |f| \big|R_{\ell_1,\ell_2} - q_{n, d}\big| \big)\).

Now applying Lemma 25 with \(B_v = 1\), and combining with the above, we obtain that \[\begin{align} \Big| \frac{\partial}{\partial v} \nu_{t,v}(f) \Big| &\le K(D, \beta_0, \beta_1, \kappa, \lambda, L)\Bigg( \sum_{\ell\le L+1} \nu_{t,v}\big( |f| \big|R_{\ell, \ell} - \rho_{n, d}\big| \big) \\ &\qquad \qquad \qquad \qquad \qquad \qquad \qquad + \sum_{1 \le \ell_1 \neq \ell_2 \le L+2} \nu_{t,v}\big( |f| \big|R_{\ell_1,\ell_2} - \rho_{n, d}\big| \big) \\ &\qquad \qquad \qquad \qquad \qquad \qquad \qquad + \Big(\varepsilon''+\frac{1}{d} \Big) \nu_{t,v}(f^2)^{1/2} \Bigg) \\ &\le K(D, \beta_0, \beta_1, \kappa, \lambda, L) \Bigg( \nu_{t,v}\big( |f| \big) + \Big(\varepsilon'' + \frac{1}{d} + \exp(-d) \Big) \nu_{t,v}\big( f^2 \big)^{1/2} \Bigg)\, . \end{align}\] For \(f \ge 0\) we thus have \[\begin{align} \Big| \frac{\partial}{\partial v} \nu_{t,v}(f) \Big| &\le K(D, \beta_0, \beta_1, \kappa, \lambda, L) \Bigg( \nu_{t,v}\big( f \big) + \Big(\varepsilon'' + \frac{1}{d} \Big) \sup_{t,v \in [0,1]^2} \nu_{t,v}\big( f^2 \big)^{1/2} \Bigg)\, . \end{align}\] Recalling \(\nu_t \equiv \nu_{t,1}\), we conclude Lemma 2 via Lemma 26.

9.2 Proof of Lemma 4↩︎

First we explicitly compute the derivative \(\frac{\mathrm{d}}{\mathrm{d}t}\nu_{t}(f)\) using Gaussian Integration by Parts:

Next collecting like terms from Lemma 27, we obtain \[\label{eq:approxrealRSequationsderivexpression} \begin{align} \Big| \frac{\mathrm{d}}{\mathrm{d}t}\nu_{t}(f) \Big| &\le \frac{1}{2} \sum_{\ell\le L} \Big( \alpha \nu_t\big( (\theta_{d}^{\ell})^2 (u''(S^{\ell}_{n, t}) + u'(S^{\ell}_{n, t})^2) f \big) - \bar{r} \nu_t\big( (\theta_{d}^{\ell})^2 f \big) \Big) \\ &\qquad + \sum_{1 \le \ell_1 < \ell_2 \le L} \Big( \alpha \nu_t\big( \theta_{d}^{\ell_1} \theta_{d}^{\ell_2} u'(S^{\ell_1}_{n, t}) u'(S^{\ell_2}_{n,t}) f \big) - r \nu_t\big( \theta_{d}^{\ell_1} \theta_{d}^{\ell_2} f \big) \Big) \\ &\qquad - L\sum_{\ell\le L} \Big( \alpha \nu_t\big( \theta_{d}^{\ell} \theta_{d}^{L+1} u'(S^{\ell}_{n, t}) u'(S^{L+1}_{n, t}) f \big) - r \nu_t\big( \theta_{d}^{\ell} \theta_{d}^{L+1} f \big) \Big) \\ &\qquad + \frac{L(L+1)}{2} \Big( \alpha \nu_t\big( \theta_{d}^{L+1} \theta_{d}^{L+2} u'(S^{L+1}_{n, t}) u'(S^{L+2}_{n, t}) f \big) - r \nu_t\big( \theta_{d}^{L+1} \theta_{d}^{L+2} f \big) \Big)\,. \end{align}\tag{211}\] We now upper bound the right hand side in the above. This is where we use the particular choice of \(r,\bar{r}\) from 51, 52. Specifically, we will employ cavity in \(n\) over the parameter \(v\) to prove:

Combining Lemma 28 and 211, it follows that for \(f = \big(\theta_{d}^1\big)^2\) or \(\theta_{d}^1 \theta_{d}^2\), we have \[\begin{align} \Big| \frac{\mathrm{d}}{\mathrm{d}t}\nu_{t}(f) \Big| \le K(D, \beta_0, \beta_1, \kappa, \lambda, L) \Bigg( \nu_t\big( (R_{1,2} - q_{n, d})^2 \big)^{1/2} + \nu_t\big( (R_{1,1} - \rho_{n, d})^2 \big)^{1/2} + \Big(\varepsilon''+\frac{1}{d}\Big)\Bigg)\,. \end{align}\] By Proposition 11, we have \[\begin{align} \nu_t\big( (R_{1,1} - \rho_{n, d})^2 \big)^{1/2} &\le K \nu_t\big( (R_{1,1} - \nu_t(R_{1,1}) )^2 \big)^{1/2} + 2 \big| \nu_t(R_{1,1}) - \nu_1(R_{1,1}) \big| \\ &\le \frac{K(D, \beta_0, \beta_1, \kappa, \lambda)}{\sqrt{d}} + 2 \big| \nu_t(R_{1,1}) - \nu_1(R_{1,1}) \big|\,, \end{align}\] and similarly for \(R_{1,2}\). Here we use that \(\rho_{n, d} = \nu_1(R_{1,1})\), \(q_{n, d} = \nu_1(R_{1,2})\). Thus combining the above two displays, to complete the proof of Lemma 4, it suffices to upper bound \[\begin{align} \Big| \frac{\mathrm{d}}{\mathrm{d}t} \nu_t(R_{1,1}) \Big|\, ,\, \Big| \frac{\mathrm{d}}{\mathrm{d}t} \nu_t(R_{1,2}) \Big| \le \frac{K(D, \beta_0, \beta_1, \kappa, \lambda)}{\sqrt{d}} \,. \end{align}\] To this end, considering \(f = R_{1,2}\) and following the notation of Lemma 27, we note that \[\begin{align} \mathrm{\small (I)}_f = \mathrm{\small (I)}_f - \nu_t(R_{1,2}) = \mathrm{\small (I)}_{f-\nu_t(R_{1,2})}\,, \end{align}\] because \(\nu_t(R_{1,2})\) is just a constant (note that for any constant function \(c\), \(\mathrm{\small (I)}_c=0\)). Similarly \(\mathrm{\small (II)}_f = \mathrm{\small (II)}_{f-\nu_t(R_{1,2})}\), \(\mathrm{\small (III)}_f = \mathrm{\small (III)}_{f-\nu_t(R_{1,2})}\), \(\mathrm{\small (IV)}_f = \mathrm{\small (IV)}_{f-\nu_t(R_{1,2})}\), \(\mathrm{\small (V)}_f = \mathrm{\small (V)}_{f-\nu_t(R_{1,2})}\). However note that \(\alpha \le \alpha_0\) and \(r,\bar{r} \le K(D, \alpha_0)\). Thus by Proposition 11, since \(|u'|, |u''| \le D\), \(\alpha \le \alpha_0\le 2\), and by Hölder’s Inequality used on each individual summand comprising the following expressions, we obtain \[\begin{align} &\mathrm{\small (I)}_{f-\nu_t(R_{1,2})}\,,\,\mathrm{\small (II)}_{f-\nu_t(R_{1,2})}\,,\,\mathrm{\small (III)}_{f-\nu_t(R_{1,2})}\,,\,\mathrm{\small (IV)}_{f-\nu_t(R_{1,2})}\,,\,\mathrm{\small (V)}_{f-\nu_t(R_{1,2})} \le \frac{K(D, \beta_0, \beta_1, \kappa, \lambda)}{\sqrt{d}}\,. \end{align}\] The same derivation applies for \(f = R_{1,1}\), thus completing the proof of Lemma 4.

9.3 Proof of Proposition 11↩︎

Here, we prove Proposition 11. For only Appendix 9.3, we define the following Gibbs average \(\langle \cdot \rangle\): \[\begin{align} \langle f \rangle := \frac{\big\langle f \exp \big( \sum_{1 \le \ell\le L} u(S_{n, t, v}^\ell) \big) \big\rangle_{t, \sim} }{\big\langle \exp u(S_{n, t, v}^{L+1})\big\rangle_{t, \sim}^L}\,. \end{align}\] Consequently by 54, we have \(\nu_{t,v}(f) = \operatorname{\mathbb{E}}\langle f \rangle\). Note we can rewrite \(\langle f \rangle\) as \[\begin{align} \frac{1}{Z'^L} \int \operatorname{\mathbb{E}}_{W}\Bigg[ f \prod_{1 \le l \le L} \mathbf{1}\{\theta_1^l/\sqrt{d} \in I\} \exp\Big( u\big(S^l_{n,t,v}(\theta^l)\big) + H_{t,n-1,d}(\theta^l) - \beta \| \theta^l \|^2 \Big) \Bigg] \, \mathrm{d}\theta^1 \cdots \mathrm{d}\theta^L\,,\label{eq:gibbsmeasurerewriteconcentration} \end{align}\tag{216}\] where \[\begin{align} Z' &= \int_{\mathbb{R}^d} \operatorname{\mathbb{E}}_{W}\Big[ \mathbf{1}\{\theta_1/\sqrt{d} \in I\} \exp\Big( u(S_{n,t,v}) + H_{t,n-1,d}(\theta) - \beta \| \theta\|^2 \Big) \Big]\, \mathrm{d}\theta\,.\label{eq:Z39def} \end{align}\tag{217}\] Note the constraint \(\prod_{1 \le l \le L} \mathbf{1}\{\theta_1^l/\sqrt{d} \in I\}\) is convex, \(u\) is concave, the \(S_{n,t,v}\) and \(S_{i,t}\) are affine in \(\theta\), and the rest of \(H_{t,n-1,d}\) is log-concave or affine in \(\theta\). It follows that the measure \(\langle \cdot \rangle\) is \(\beta\)-strongly log-concave in \(\theta\), a fact that will be exploited repeatedly via concentration of Lipschitz functions of strongly log-concave measures (Theorem 19) in what follows.

9.3.1 First part of Proposition 11↩︎

We prove the first part of Proposition 11 by directly combining the following Propositions 24, 25. First, we have the following concentration property of \(f = R_{1, 1}\) or \(R_{1, 2}\) about their average \(\langle f \rangle\) with the quenched disorder fixed:

Second, we have concentration of \(\langle f \rangle\) about \(\operatorname{\mathbb{E}}\langle f \rangle\):

Combining Proposition 24 and Proposition 25 yields the first part of Proposition 11. For the rest of the proof of the first part of Proposition 11, we assume \(u(\cdot)\) satisfies the conditions of Theorem 7. Central in the proofs of both Proposition 24 and Proposition 25 is concentration of Lipschitz functions w.r.t strongly log-concave measures, as written in Theorem 19. We will also use the following fact which follows by a standard symmetrization argument, see (3.22) of [25].

9.3.1.1 Proof of Proposition 24:

We now prove Proposition 24. First, we show that \(B^{\star}\) can be controlled on the exponential scale:

We next lower bound the partition function \(Z'\) in order to apply Lemma 19 to control the relevant overlaps.

We now have the ingredients needed to prove Proposition 24.

9.3.1.2 Proof of Proposition 25

We will follow the strategy of [25] of considering \(\langle R_{1, 1} \rangle\) and \(\langle R_{1, 2}\rangle\) as functions of the disorder \((s_j)_{j \le n} \times (g_{i, j})_{2 \le i \le n, 1 \le j \le d} \times (W^l)_{1 \le l \le L} \times Z\times Y\). The density of the disorder is strongly log-concave by Assumption 1, and to apply Theorem 19 on concentration of Lipschitz functions of strongly log-concave measures, we need to establish control on the Lipschitz constant of these functions.

We now aim to upper bound the expressions appearing in the bound from Lemma 32.

To bound the other term in Lemma 32, define the matrix \(M\) as follows: for all \(1 \le i \le n\) and \(1 \le j \le d\), we let \[\begin{align} (M)_{i, j} &:= \begin{cases} s_i &: 1 \le i \le n-1, j=1 \\ g_{i, j} &: 1 \le i \le n-1, 2 \le j \le d-1 \\ \sqrt{t} g_{i, d} &: 1 \le i \le n-1, j=d \\ vs_n &: i=n, j=1 \\ \sqrt{v} g_{n,j} &: i=n, 2 \le j \le d-1 \\ \sqrt{vt} g_{n,d} &: i=n, j=d\,.\end{cases} \tag{229} \\ B' &:= \| M \|_{\mathrm{\small op}}\,.\tag{230} \end{align}\] We now control \(B'\) as follows:

Next note for any sequences \((x_j)_{j \le d}\), \((y_i)_{i \le n}\), we have \[\sum_{i \le n, j \le d} M_{i, j} x_j y_i \le B' \Big( \sum_{j \le d} x_j^2 \Big)^{1/2} \Big( \sum_{i \le n} y_i^2 \Big)^{1/2}\,.\] Now applying the above inequality for \(x_j = \sum_{i \le n} M_{i, j} y_i\), we obtain that \[\begin{align} \Big( \sum_{j \le d} \Big( \sum_{i \le n} M_{i, j} y_i \Big)^2 \Big)^{1/2} \le B' \Big( \sum_{i \le n} y_i^2 \Big)^{1/2}\,.\label{eq:opnormboundtal347} \end{align}\tag{234}\]

We now have done the necessary preparation to prove Proposition 25.

As noted before, combining Proposition 24 and Proposition 25 proves the first part of Proposition 11.

9.3.2 Second part of Proposition 11↩︎

Recall that we have 223 by Lemma 31 and Lemma 19. Now by Hölder’s Inequality and 219, taking \(K(D, \beta_0, \beta_1, \kappa, \lambda)\) appropriately and combining with 223, we obtain \[\begin{align} \log \nu_{t,v}\Big( \exp \Big( \frac{\| \bar{\theta} \|^2}{K(D, \beta_0, \beta_1, \kappa, \lambda} \Big) \Big) &= \log \operatorname{\mathbb{E}}\Big\langle \exp \Big( \frac{\| \bar{\theta} \|^2}{K(D, \beta_0, \beta_1, \kappa, \lambda)} \Big) \Big\rangle \\ &\le \log \operatorname{\mathbb{E}}\Big\langle \exp \Big( \frac{ \beta \| \bar{\theta} \|^2}{2} \Big) \Big\rangle^{\frac{1}{1+K_{\mathrm{\ref{lem:logconcaveboundmomentslemma}}}(K_{\mathrm{\ref{lem:lem316}}}, D, \beta_0, \beta_1, \kappa, \lambda)}} \\ &\le \log \operatorname{\mathbb{E}}\exp(B^{\star}) \\ &\le K(\lambda)\, d\,. \end{align}\] It remains to prove that \[\begin{align} \label{eq:second95part95concentration95step1} \log \nu_{t,v}\Big( \exp \Big( \frac{\theta_{d}^2}{K(D, \beta_0, \beta_1, \kappa, \lambda)} \Big) \Big) \le K(D, \beta_0, \beta_1, \kappa, \lambda)\,. \end{align}\tag{235}\] To this end, we cite the following Lemma from [25]. This function is stated for concave \(T \le 0\) and \(\beta'>0\) in [25], however the proof therein applies verbatim under the conditions stated below.

We will also need the following corollary of the Prékopa-Leindler Inequality:

We now complete the proof of the second part of Proposition 11. By Theorem 19 applied with the 1-Lipschitz function \(\theta\rightarrow \theta_d\), we have \[\begin{align} \label{eq:second95part95concentration95step2} \Big\langle \exp \Big( \frac{(\theta_d - \langle \theta_d \rangle)^2}{K(\beta_0)} \Big) \Big\rangle \le K\,. \end{align}\tag{236}\] Next, note by convexity of the function \(\exp x^2\) that for \(f_1, f_2\) satisfying \(\nu_{t,v}\big( \exp(f_1^2 / K) \big) \le K\), \(\nu_{t,v}\big( \exp(f_2^2 / K) \big) \le K\), we have the upper bound \(\nu_{t,v}\big( \exp\big( (f_1+f_2)^2 / K \big) \big) \le K\) (here \(K\) can differ). Thus taking expectations of 236 and applying this observation, to establish 235, it thus remains to show that \[\begin{align} \operatorname{\mathbb{E}}\Big[ \exp \Big( \frac{\langle \theta_d \rangle^2}{K(D, \beta_0, \beta_1, \kappa, \lambda)} \Big) \Big] \le K(D, \beta_0, \beta_1, \kappa, \lambda)\,.\label{eq:logconcavelastcoordgoal} \end{align}\tag{237}\] To this end, we apply Lemma 37. Define the convex set \(C = \mathbb{R}^d \cap \mathbf{1}\{\theta_1/\sqrt{d}\in I\}\), and let \[\begin{align} T_0(\theta, W) := \sum_{1 \le i \le n} u(S_{i,t}) + u(S_{n,t,v})\,. \end{align}\] Since \(S_{i,t}\) is affine in \(\theta\) and as \(S_{n,t,v}\) is jointly affine in \(\theta\) and \(W\), since \(u\) is concave, it follows that \(T_0(\theta, W)\) is concave jointly in \(\theta, W\). Thus letting \(T(\theta) := \log \operatorname{\mathbb{E}}_{W}\big[ \exp T_0(\theta) \big]\), \(T\) is concave by Lemma 38.

Next, let \(\beta' = \frac{(1-t)(r-\bar{r})}{2} \ge 0\), where the inequality follows as \(r \ge \bar{r}\). Define \(a_j\) for \(1 \le j \le d\) by letting \(a_j = 0\) for all \(j \le d-1\) and \(a_d = \sqrt{(1-t) r}Y\). Defining \(\mu\) from Lemma 37 with these choices, as dependence on \(W\) in \(\nu_{t,v}\) is only via \(S_{n,t,v}(\theta)\), as \(T(\theta)\) is defined with expectation w.r.t. \(W\), and as the number of replicas \(L=1\) here, it follows that \(\mu\) is exactly the Gibbs average \(\langle \cdot \rangle\).

Note \(C'=\big\{ \theta \in \mathbb{R}\,:\,\exists \theta' \in \mathbb{R}^{d-1}\text{ s.t. }(\theta', \theta) \in C\} = \mathbb{R}\). Hence by Lemma 37, the following function is concave on all of \(\mathbb{R}\): \[\begin{align} f(\theta_d) &:= \log \int_{\theta = (\theta', \theta_d) \in \mathbb{R}^d \cap \mathbf{1}\{\theta_1/\sqrt{d}\in I\}} \operatorname{\mathbb{E}}_{W}\Big[ \exp\Big( T_0(\theta, W) - \beta \sum_{j \le d-1} \theta_j^2 \Big) \Big]\, \mathrm{d}\theta'\,. \end{align}\] Moreover, by Lemma 37, we know that letting \[\begin{align} w(\theta) := f(\theta) - \Big(\beta + \frac{(1-t)(r-\bar{r})}{2}\Big) \theta^2 + \sqrt{(1-t)r}Y \theta\,, \end{align}\] the law of \(\theta_d\) under \(\mu\) is the measure on \(\mathbb{R}\) with density proportional to \(\exp w(\theta)\).

As \(r \ge \bar{r}\), we know \(\beta + \frac{(1-t)(r-\bar{r})}{2} > 0\), and thus \(w(\theta)\) is \(\beta\) strongly concave and attains a unique maximum \(\theta^{\star}\) on \(\mathbb{R}\). By Lemma 54, it follows that \(\big\langle (\theta_d - \theta^{\star})^2 \big\rangle \le K(\beta_0)\). By Jensen and Triangle Inequality, we thus have \(\langle \theta_d \rangle \le K(\beta_0) + |\theta^{\star}|\) (for a different \(K\)).

Note that \(w'(\theta^{\star})=0\). Since \(w\) is \(\beta\) strongly concave, \(|w'(0)| = |w'(\theta^{\star}) - w'(0)| \ge 2\beta |\theta^{\star}|\). Note \(w'(0) = f'(0) + \sqrt{(1-t)r} Y\). Combining the above steps yields \[\begin{align} \label{eq:concentration95logconcave95end1} \big\langle \theta_d \big\rangle \le K(\beta_0) \Big(1+|f'(0)|+\sqrt{(1-t)r}|Y|\Big)\,. \end{align}\tag{238}\] Note since \(Y\) is a standard Gaussian, we have \(\exp (Y^2) \le K\). By 238, since \(r \le K(D)\), it suffices to prove the following to establish 237 and hence complete the proof: \[\begin{align} \label{eq:concentration95logconcave95end2} \operatorname{\mathbb{E}}\Big[ \exp \Big( \frac{f'(0)^2}{K(D, \beta_0, \beta_1, \kappa, \lambda)} \Big) \Big] \le K(D, \beta_0, \beta_1, \kappa, \lambda)\,. \end{align}\tag{239}\] Let \(\langle \cdot \rangle_f\) denote the Gibbs average defined as follows: for any test function \(h\), \[\begin{align} \langle h \rangle_f &= \frac{1}{\bar Z} \int_{\theta=(\theta', \theta_d) \in \mathbb{R}^d \cap \mathbf{1}\{\theta_1/\sqrt{d}\in I\}} \operatorname{\mathbb{E}}_{W}\Big[ h \exp\Big( T_0(\theta, W) - \beta \sum_{j \le d-1} \theta_j^2 + \sqrt{(1-t)r}Y \theta_d \Big) \Big]\, \mathrm{d}\theta\,, \end{align}\] where \(\bar Z\) denotes the corresponding normalizing constant. Explicitly calculating yields \[\begin{align} f'(\theta_d) &= \Bigg\langle \sum_{1 \le i \le n-1} u'(S_{i,t}) \sqrt{\frac{t}{d}} g_{i,d} + u'(S_{n,t,v}) \sqrt{\frac{tv}{d} } g_{n,d} \Bigg\rangle_f\,.\label{eq:concentration95logconcave95writeasmixture} \end{align}\tag{240}\] Notice that when \(\theta_d=0\), \(S_{i,t}\), \(S_{n,t,v}\), \(\sqrt{(1-t)r}Y \theta_d=0\), and therefore \(T_0(\theta, W)\) do not depend on \((g_{i,d})_{1 \le i \le n}, Y\). Hence when \(\theta_d=0\), \(\bar Z\) also does not depend on \((g_{i,d})_{1 \le i \le n}, Y\). 240 thus implies that \(f'(0)\) can be written as a linear combination of \((g_{i,d})_{1 \le i \le n}\) with coefficients independent of \((g_{i,d})_{1 \le i \le n}\). Specifically, these coefficients are Gibbs averages of \(u'(S_{i,t}) \sqrt{\frac{t}{d}}\), \(u'(S_{n,t,v}) \sqrt{\frac{tv}{d}}\) (where we consider \(S_{i,t}, S_{n,t,v}\) with \(\theta_d=0\)) w.r.t. \(\langle \cdot \rangle_f\).

Since the \((g_{i,d})_{1 \le i \le n} \sim N(0,1)\), it follows that \(f'(0)\) is a Gaussian. Let \(\bar{\operatorname{\mathbb{E}}}\) denote expectation in the \(g_{i,d}\). As \(|u'| \le D\), the corresponding coefficients on the \(g_{i,d}\) are most \(D / \sqrt{d}\) in magnitude. By the independence of the \(g_{i,d}\), it follows that \[\begin{align} \bar\operatorname{\mathbb{E}}\big[ f'(0)^2 \big] \le \frac{n}{d} \cdot D^2 \le K(D)\,, \end{align}\] where we use that \(n/d \le \alpha_0\le 2\). Since \(f'(0)\) is Gaussian, it follows from standard upper bounds for the MGF of a Gaussian with a given variance (see (A.11) in [25]) that for suitable \(K(D, \beta_0, \beta_1, \kappa, \lambda)\), \[\begin{align} \operatorname{\mathbb{E}}\Big[ \exp \Big( \frac{f'(0)^2}{K(D, \beta_0, \beta_1, \kappa, \lambda)} \Big) \Big] = \operatorname{\mathbb{E}}\bar\operatorname{\mathbb{E}}\Big[ \exp \Big( \frac{f'(0)^2}{K(D, \beta_0, \beta_1, \kappa, \lambda)} \Big)\Big] \le 2\,. \end{align}\] This establishes 239 and hence establishes Proposition 11.

10 Properties of the RS equations↩︎

Here, we establish several important properties of the RS equations. Specifically, we prove Proposition 13 in Appendix 10.1, Proposition 9 in Appendix 10.2, and Lemma 23 in Appendix 10.3. Throughout this section, recall that \(\varphi_{0}\) denotes the PDF of a standard univariate normal \(N(0,1)\) and \(\varphi_{1}\) denotes the PDF of \(S \sim \mathcal{D}\).

All three of these results are critical, and are proved through similar ideas. Discussing the proof of Proposition 9 for the interpolators for concreteness, we must establish that the RS equations exhibit a particular convex-concave structure. Talagrand’s proof of this convex-concave structure in Section 3.3, [25] proceeds by showing each part of the expression for the relevant second derivatives is of the correct sign. This relies crucially on the fact that \(\kappa\ge 0\) and that there is no signal in the data.

Here we instead proceed by showing the part of the expression for the relevant second derivatives whose signs are not correct are small in magnitude, and therefore do not eliminate the desired convex-concave structure. We must also bound similar terms in proving Proposition 13. The magnitude of these terms all can be upper bounded by \(\alpha \operatorname{\mathbb{E}}\Big[f\big(\frac{\kappa- xS - \sqrt{q} Z}{\sqrt{\rho-q}}\big) \Big]\) for a function \(f(x) \le O(|x|^2+1)\) that depends on the Inverse Mills’ Ratio from 16, where expectation is over \(Z, S\).

The magnitude of the expression for each such part can be directly shown to be of order \(O\Big(\alpha \cdot \frac{\kappa^2+q+1}{\rho-q}\Big)\) for all \(\kappa\in \mathbb{R}\). However, to establish our result for all \(\alpha \le \alpha_0\) for all \(\kappa< 0\), such a bound is not sufficient. The idea is instead as follows. When \(\frac{\kappa- xS - \sqrt{q} Z}{\sqrt{\rho-q}} \le 0\), the relevant quantities are simple to control by properties of the Inverse Mills’ Ratio. Else, we let \(\kappa' := \kappa- xS\) be the ‘effective margin’ and analyze the sign of \(\kappa'\).

• If \(|S| < |\kappa|\), as \(|x| \le 1\), we must have \(\kappa' < 0\). In this case, observe that the probability over \(Z\) that \(\frac{\kappa- xS - \sqrt{q} Z}{\sqrt{\rho-q}} = \frac{\kappa' - \sqrt{q} Z}{\sqrt{\rho-q}} > 0\) is exponentially small in \(|\kappa'|^2/q\).

• Else, the probability over \(S\) that \(|S| \ge |\kappa|\) is exponentially small in \(|\kappa|^2\) as the law of \(S^2\) is sub-Exponential.

Combining both these bounds enables us to upper bound \(\operatorname{\mathbb{E}}\Big[f\big(\frac{\kappa- xS - \sqrt{q} Z}{\sqrt{\rho-q}}\big) \Big]\) independently of \(\kappa\) for \(\kappa< 0\), which is sufficient for our purposes.

10.1 Proof of Proposition 13↩︎

We consider an arbitrary solution \((q, \rho, r, \bar{r})\) of 56 and show that \((q, \rho) \in [0, C_{\mathrm{\small sol}}) \times [0, C_{\mathrm{\small sol}})\) and \(\frac{1}{\rho-q} < C_{\mathrm{\small sol}}\). This is sufficient to establish Proposition 13, up to showing \(q > 0\). To this end, note \(q=0\) implies \(r=0\). Now as \(\lambda>0\), we have \(u' > 0\) on a set of positive Lebesgue measure. It follows that for every \(Z, S\), there exists a set of \(W\) with positive Lebesgue measure such that \(u'(\eta) \exp u(\eta) > 0\), where \(\eta\) is given in terms of \(W, Z, S\) by 48. Since \(u' \exp u \ge 0\) pointwise, it follows that \(r > 0\) by definition of 56. Hence \(q=0\) yields contradiction, so as \(q \ge 0\), we must have \(q>0\).

10.1.0.1 Proof for posterior.

The proof of Proposition 13 for the posterior is direct. Recall that \(|u^l| \le D=D(\lambda)\) for \(l=1,2,3,4\). Thus by definition of \(\psi_{\alpha}\), \(\bar{\psi}_{\alpha}\) in 51, 52, we have \(|r|, |\bar r| \le K(D)\). Also note \(r \ge 0\) by definition of \(\psi_{\alpha}\). Since \(r \ge \bar r\), the definition of the system 56 implies \(0 \le q, \rho \le K(D)\). Next, we note \(\rho, \rho-q \ge \frac{1}{2\beta+r - \bar r} \ge \frac{1}{K(D)}\). This proves Proposition 13 for the posterior.

10.1.0.2 Proof for interpolators.

The rest of Appendix 10.1 is now devoted to the proof of Proposition 13 for the interpolators, which poses significantly more difficulties. We first state and prove the following Lemmas which we will need in the following proof. In the following, we recall the definition of \(\eta= \eta(q, \rho)\) from 48.

Now we return to the proof of Proposition 13.

10.1.0.3 Bounding \(q, \rho\):

First, clearly \(0 \le q \le \rho\) by definition of the system 56. It remains to upper bound \(q, \rho\). Now, note as \(r \ge \bar{r}\) by Lemma 41, \[\begin{align} \label{eq:boundedsols95q95init} \rho - q = \frac{1}{2\beta+ r - \bar{r}} \le \frac{1}{2\beta_0} \,. \end{align}\tag{241}\] It thus remains to upper bound \(q\). If \(0 \le q \le 1\) we obtain \[\begin{align} 0 \le q, \rho \le \frac{1}{2\beta_0} + 1 < C_{\mathrm{\small sol}}\,, \end{align}\] yielding the required bound. We now suppose that \(q > 1\). Now by definition of 56, we have \[\begin{align} r = q (2\beta + r - \bar{r})^2 = \frac{q}{(\rho-q)^2}\,.\label{eq:realRSboundedeq1} \end{align}\tag{242}\] Next by Lemma 40, letting \(Y := \frac{\kappa- xS- \sqrt{q}Z}{\sqrt{\rho-q}}\), we have \[\begin{align} r &= \psi_{\alpha}\big(q,\rho\big) = \frac{\alpha}{\rho - q} \operatorname{\mathbb{E}}\Big( \frac{\operatorname{\mathbb{E}}_{W}\big[ W\exp u(\eta) \big]}{\operatorname{\mathbb{E}}_{W}\big[ \exp u(\eta) \big]} \Big)^2 \le \frac{\alpha}{\rho - q}\Big( K_{\mathrm{\ref{lem:RSboundedupperboundr}}} + \operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big] \Big)\, .\label{eq:realRSbounded95rbound} \end{align}\tag{243}\] Now we upper bound \(\operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big]\).

10.1.0.4 Upper bound for \(\kappa\ge 0\).

Using \(\operatorname{\mathbb{E}}[S^2] \le K_{\mathrm{\small signal}}\), \(\operatorname{\mathbb{E}}[Z^2]=1\), \(x^2 \le 1\), we have \[\begin{align} \label{eq:bound95sols95positivemargin} \operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big] \le \operatorname{\mathbb{E}}[Y^2] &\le \frac{3}{\rho-q} \operatorname{\mathbb{E}}\big[ \kappa^2 + x^2 S^2 + qZ^2 \big] \le \frac{3(\kappa^2 + K_{\mathrm{\small signal}}+ q)}{\rho-q}\,. \end{align}\tag{244}\]

10.1.0.5 Upper bound for \(\kappa< 0\).

Here as we would like to establish this result for all \(\alpha \le \alpha_0\) at most a universal constant, the proof idea is more complicated. Define the ‘effective margin’ \[\begin{align} \label{eq:effective95margin95def} \kappa' := \kappa- xS\,. \end{align}\tag{245}\] We now analyze the sign of \(\kappa'\). Note:

• If \(|S| < |\kappa|\), as \(|x| \le 1\), we must have \(\kappa'=\kappa- xS< 0\). Then for \(Y < 0\) to occur, we must have \(|Z| \ge \frac{|\kappa'|}{\sqrt{q}}\), the probability of which over \(Z\) is exponentially unlikely in \(|\kappa'|/\sqrt{q}\).

• Else, the probability over \(S\) that \(|S| \ge |\kappa|\) is exponentially unlikely in \(|\kappa|^2\) as the law of \(S^2\) is sub-Exponential.

Thus in both cases we can upper bound \(\operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big]\). We now execute this idea. Write \[\begin{align} \operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big] &= \int_{s, z} \frac{(\kappa' - z\sqrt{q})^2}{\rho - q} \mathbf{1}\{ \kappa' \ge z\sqrt{q} \} \varphi_{0}(z) \varphi_{1}(s)\, \mathrm{d}z \mathrm{d}s \\ &= \int_{s:|s| < |\kappa|} \int_z \frac{(\kappa' - z\sqrt{q})^2}{\rho - q} \mathbf{1}\{\kappa' \ge z\sqrt{q} \} \varphi_{0}(z) \varphi_{1}(s)\, \mathrm{d}z \mathrm{d}s \\ &\qquad \qquad + \int_{s:|s| \ge |\kappa|} \int_z \frac{(\kappa' - z\sqrt{q})^2}{\rho-q} \mathbf{1}\{\kappa' \ge z\sqrt{q} \} \varphi_{0}(z) \varphi_{1}(s)\, \mathrm{d}z \mathrm{d}s\, . \end{align}\] If \(|s| < |\kappa|\), then \(|xs| < |\kappa|\), so \(\kappa' = \kappa-xs < 0\) as \(\kappa< 0\). Recall \(q \ge 1\), otherwise the proof is already completed. Thus \(\kappa' \ge z\sqrt{q}\) implies that \(|z| \ge \frac{|\kappa'|}{\sqrt{q}}\). Hence \[\begin{align} & \int_{s:|s| < |\kappa|} \int_z \frac{(\kappa' - z\sqrt{q})^2}{\rho - q} \mathbf{1}\{\kappa' \ge z\sqrt{q} \} \varphi_{0}(z) \varphi_{1}(s)\, \mathrm{d}z \mathrm{d}s \\ &\quad\le \frac{q}{\rho-q} \int_{s:|s| < |\kappa|} \int_z 2\Big( \frac{|\kappa'|^2}{q} + z^2 \Big) \cdot \exp(-|\kappa'|^2/4q) \cdot \frac{1}{\sqrt{2\pi}} \exp(-z^2/4) \varphi_{1}(s)\, \mathrm{d}z \mathrm{d}s \\ &\quad \le \frac{2q}{\rho-q} \Big(\int_s \varphi_{1}(s) \, \mathrm{d}s \Big) \Bigg( \int_z \Big( \frac{|\kappa'|^2}{q} + z^2 \Big) \cdot \exp(-|\kappa'|^2/4q) \exp(-z^2/4)\, \mathrm{d}z \Bigg) \\ &\quad \le \frac{10q}{\rho-q}\, . \end{align}\] When \(|s| \ge |\kappa|\), we employ a similar strategy, but now we analyze the probability in \(S\) rather than \(Z\). Since \(q \ge 1\), we may bound \[\begin{align} &\int_{s:|s| \ge |\kappa|} \int_z \frac{(\kappa' - z\sqrt{q})^2}{\rho-q} \mathbf{1}\{\kappa' \ge z\sqrt{q} \} \varphi_{0}(z) \varphi_{1}(s)\, \mathrm{d}z \mathrm{d}s \\ &\quad \le \frac{2q}{\rho-q} \int_{s:|s| \ge |\kappa|} \int_z \Big( z^2 + \frac{2(\kappa^2+s^2 )}{q} \Big) \varphi_{0}(z) \varphi_{1}(s)\, \mathrm{d}z \mathrm{d}s \\ &\quad \le \frac{2q}{\rho-q} \Big( \int_z z^2 \varphi_{0}(z)\, \mathrm{d}z + 2 \int_s s^2 \varphi_{1}(s)\, \mathrm{d}s + 2\kappa^2 \int_{s:|s| \ge |\kappa|} \varphi_{1}(s)\, \mathrm{d}s \Big) \\ &\quad \le \frac{2q}{\rho-q} \Big(1 + 2 K_{\mathrm{\small signal}}+ 2\kappa^2 \operatorname{\mathbb{P}}\Big( S^2 > \kappa^2 \Big) \Big) \\ &\quad \le \frac{2q}{\rho-q} \Big(1 + 2 K_{\mathrm{\small signal}}+ 4\kappa^2 \exp\Big( -\frac{\kappa^2}{ K_{\mathrm{\small signal}}} \Big) \Big) \\ &\quad \le \frac{2q}{\rho-q} \Big( 1 + 3.5 K_{\mathrm{\small signal}}\Big) \,. \end{align}\] Here we used that \(S^2\) is \(K_{\mathrm{\small signal}}\) sub-Exponential to upper bound \(\operatorname{\mathbb{P}}( S^2 > \kappa^2 )\), and used Assumption 1 to upper bound \(\operatorname{\mathbb{E}}[S^2] \le K_{\mathrm{\small signal}}\). Combining the above displays yields \[\begin{align} \label{eq:bound95sols95negativemargin} \operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big] \le \frac{q}{\rho-q} \Big( 12 + 7 K_{\mathrm{\small signal}}\Big)\,. \end{align}\tag{246}\]

Having upper bounded \(\operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big]\) in both cases, in the \(\kappa>0\) case we obtain via 243 and 244, using that \(q \ge 1\) by assumption here (else we have already finished the proof) and that \(K_{\mathrm{\small signal}}\ge 1\), \[\begin{align} q = r(\rho-q)^2 &\le (\rho-q)^2 \cdot \frac{\alpha}{\rho-q} \Big( K_{\mathrm{\ref{lem:RSboundedupperboundr}}} + \operatorname{\mathbb{E}}\big[ Y^2 \mathbf{1}\{Y \ge 0\}\big] \Big) \\ &\le \alpha K_{\mathrm{\ref{lem:RSboundedupperboundr}}} (\rho-q) + 3 \alpha q \big(\kappa^2 + K_{\mathrm{\small signal}}+ 1 \big)\,. \end{align}\] Similarly in the \(\kappa< 0\) case we have by 243 and 246, \[\begin{align} q = r(\rho-q)^2 &\le \alpha K_{\mathrm{\ref{lem:RSboundedupperboundr}}} (\rho-q) + \alpha q \big( 12 + 7 K_{\mathrm{\small signal}}\big)\, . \end{align}\] Since \(\alpha_0\le \min\big\{ \frac{1}{2 K_{\mathrm{\ref{lem:RSboundedupperboundr}}}}, \frac{1}{24 + 14 K_{\mathrm{\small signal}}} \big\}\) when \(\kappa< 0\) and \(\alpha_0\le \frac{1}{3(\kappa^2 + K_{\mathrm{\small signal}}+ 1)}\) when \(\kappa\ge 0\), combining with 241 yield that in either case, we have \[q \le \frac{q}{2} + \frac{\rho-q}{2} = \frac{\rho}{2} \le \frac{q}{2} + \frac{1}{4\beta_0}\,,\quad\text{thus}\quad q \le \frac{1}{2\beta_0}\, .\] Consequently we obtain \(\rho \le \frac{1}{\beta_0}\) from 241, and thus \(0 \le q, \rho < C_{\mathrm{\small sol}}\).

10.1.0.6 Upper bounding \(\frac{1}{\rho-q}\):

From the definition of the system 56, we have \[\frac{1}{\rho - q} = 2\beta+ r - \bar{r} = 2\beta - \alpha \operatorname{\mathbb{E}}\big[ v''\big(\sqrt{q}Z\big) \big]\, .\] Next by Gaussian Integration by Parts and as \(v' \ge 0\), we have \[\begin{align} \operatorname{\mathbb{E}}\big[ v''\big(\sqrt{q}Z\big) \big] &= \frac{1}{\sqrt{q}} \operatorname{\mathbb{E}}\big[ Zv'\big(\sqrt{q}Z\big) \big] \\ &\ge \frac{1}{\sqrt{q}} \operatorname{\mathbb{E}}\big[ \mathbf{1}\{Z\le 0\} \cdot Zv'\big(\sqrt{q}Z\big) \big] \\ &\ge -\frac{1}{\sqrt{q}} \operatorname{\mathbb{E}}\big[ Z^2 \mathbf{1}\{Z\le 0\} \big]^{1/2} \cdot \operatorname{\mathbb{E}}\big[ v'\big(\sqrt{q}Z\big)^2 \big]^{1/2} \\ &= -\frac{1}{\sqrt{2q}} \operatorname{\mathbb{E}}\big[ v'\big(\sqrt{q}Z\big)^2 \big]^{1/2}\,. \end{align}\] Combining the above with Lemma 39 gives \[\frac{1}{\rho - q} \le 2\beta+ \frac{\alpha}{\sqrt{2q}}\operatorname{\mathbb{E}}\big[ v'\big(\sqrt{q}Z\big)^2 \big]^{1/2} = 2\beta+ \sqrt{\frac{\alpha r}{2q} }\, .\] Combining the above with 242 and using \(\alpha \le \alpha_0\le 1/2\) yields \[\frac{1}{\rho-q} \le 2\beta+ \sqrt{\frac{\alpha}{2}} \cdot \frac{1}{\rho-q}\,,\quad\text{thus}\quad\frac{1}{\rho - q} \le 4\beta\le 4\beta_1 < C_{\mathrm{\small sol}}\, .\]

10.2 Proof of Proposition 9↩︎

Throughout Appendix 10.2, \(I\) is held fixed, and so we denote \(F_I\) by \(F\) for simplicity of notation. As done in Chapter 3 of [25], consider the transformation \[y = \frac{q}{\rho-q}\,.\] Hence given \(y\), we set \(q=\frac{y \rho}{1+y}\), and have \(\rho > q\). Define \[\begin{align} G(y,\rho) &:= F\Big(\frac{y \rho}{1+y},\rho \Big) \notag\,. \end{align}\] Thus we have \[\label{eq:G95transformed95def} \begin{align} G(y, \rho) &= \alpha \operatorname{\mathbb{E}}\Big[ \log \operatorname{\mathbb{E}}_{W} \exp u\Big( x S+ \sqrt{\frac{y \rho}{1+y}} Z+ \sqrt{\frac{\rho}{1+y}} W\Big)\Big] + \frac{y}{2} + \frac{1}{2} \log \rho - \frac{1}{2} \log(1+y) \\ &\qquad \qquad - \beta \big(\rho + r_I(x)\big)\,, \end{align}\tag{247}\] where \(u(\cdot)\) is given by \(\exp u(x) = \mathbf{1}\{x \ge \kappa\}\) for the interpolators, and by 17 in the GMM case or 18 in the logistic case for the posterior. Consider the system \[\begin{align} \frac{\partial G}{\partial \rho}=\frac{\partial G}{\partial y}=0\,.\label{eq:RStransformed} \end{align}\tag{248}\] Note this system does not depend on the \(-\beta r(x)\) term in the definition of \(G(y, \rho)\).

Thus in what follows, we now work with 248.

10.2.0.1 Preliminary calculations for interpolators.

We first explicitly write the system 248 and establish some of its useful properties. Since we consider \(\rho_0 \ge \frac{1}{C_{\mathrm{\small sol}}} > 0\), we may divide by \(\rho\) in the following. Now let \[\begin{align} V:= \sqrt{\frac{1+y}{\rho}}(\kappa- xS) - \sqrt{y}Z= \sqrt{\frac{1+y}{\rho}} \kappa' - \sqrt{y}Z\,,\label{eq:RS95Vexpression95def} \end{align}\tag{249}\] where here and in the following, as in the proof of Proposition 13, we define the ‘effective margin’ \(\kappa' := \kappa- x S\) as per 245. Hence letting \(\mathcal{N}(\cdot)\) denote the complementary c.d.f. of the standard normal as per 10, we have \[\begin{align} \label{eq:convert95to95complementarycdf} \log \operatorname{\mathbb{P}}_{W} \Big( xS + \sqrt{\frac{y \rho}{1+y}}Z + \sqrt{\frac{\rho}{1+y}}W \ge \kappa\Big) \equiv \log \mathcal{N}\Big( \sqrt{\frac{1+y}{\rho}} (\kappa- xS) - \sqrt{y}Z\Big)\,. \end{align}\tag{250}\] Recalling the definition of the Inverse Mills’ Ratio \(\mathcal{A}(x)\) in 16, we record a few of its properties.

We now explicitly write the system 248. By explicit calculation and 250, we have \[\begin{align} \frac{\partial G}{\partial \rho} &= \frac{\alpha}{2} \operatorname{\mathbb{E}}\Big[ (\kappa- xS) \frac{(1+y)^{1/2}}{\rho^{3/2}} \mathcal{A}(V)\Big] + \frac{1}{2\rho} - \beta= \frac{\alpha}{2} \operatorname{\mathbb{E}}\Big[ \kappa' \frac{(1+y)^{1/2}}{\rho^{3/2}} \mathcal{A}(V)\Big] + \frac{1}{2\rho} - \beta\,,\label{eq:partialGrho} \\ \frac{\partial G}{\partial y} &= \alpha \operatorname{\mathbb{E}}\Big[ \Big( -\frac{\kappa- xS}{2\rho^{1/2} (1+y)^{1/2}} + \frac{Z}{2y^{1/2}} \Big) \mathcal{A}(V) \Big] + \frac{y}{2(1+y)} \,. \end{align}\tag{251}\] Applying Gaussian Integration by Parts and Lemma 43, \[\begin{align} \operatorname{\mathbb{E}}\Big[ \frac{Z}{\sqrt{y}} \mathcal{A}(V) \Big] = -\operatorname{\mathbb{E}}\Big[ \mathcal{A}'(V) \Big] &= \operatorname{\mathbb{E}}\Big[ -\mathcal{A}(V)^2 + V\mathcal{A}(V) \Big] \\ &= \operatorname{\mathbb{E}}\Big[ -\mathcal{A}(V)^2 \Big] + \operatorname{\mathbb{E}}\Big[ \Big( (\kappa- xS)\sqrt{\frac{1+y}{\rho}} - \sqrt{y}Z \Big) \mathcal{A}(V) \Big]\,. \end{align}\] Rearranging yields \[\begin{align} \frac{Z}{\sqrt{y}} \operatorname{\mathbb{E}}[\mathcal{A}(V)] = \frac{1}{1+y}\operatorname{\mathbb{E}}\Big[-\mathcal{A}(V)^2 + (\kappa- xS)\sqrt{\frac{1+y}{\rho}} \mathcal{A}(V) \Big]\,. \end{align}\] We thus obtain \[\begin{align} \frac{\partial G}{\partial y} = -\frac{\alpha}{2(1+y)} \operatorname{\mathbb{E}}\Big[ \mathcal{A}(V)^2 \Big] + \frac{y}{2(1+y)} \,.\label{eq:partialGy} \end{align}\tag{252}\] Following the argument of [23], [25], we establish that 251, 252 have a unique solution by considering \(\frac{\partial^2 G}{\partial^2 \rho}\) and the sign of \(\frac{\partial G}{\partial y}\), and arguing that the signs work out to yield a saddle point and thus a unique solution to 248. We first compute from 251, \[\begin{align} \frac{\partial^2 G}{\partial \rho^2} &= -\frac{3\alpha(1+y)^{1/2} }{4 \rho^{5/2}} \operatorname{\mathbb{E}}\Big[ \kappa' \mathcal{A}(V) \Big] + \frac{\alpha (1+y)^{1/2}}{2 \rho^{3/2}} \operatorname{\mathbb{E}}\Big[ \kappa' \mathcal{A}'(V) \cdot -\frac{1}{2} (1+y)^{1/2} \rho^{-3/2} \kappa' \Big] - \frac{1}{2\rho^2} \notag \\ &= -\frac{3\alpha (1+y)^{1/2}}{4 \rho^{5/2}} \operatorname{\mathbb{E}}\Big[ \kappa' \mathcal{A}(V) \Big] - \frac{\alpha (1+y)}{4 \rho^3} \operatorname{\mathbb{E}}\Big[ \kappa'^2 \mathcal{A}'(V) \Big] - \frac{1}{2\rho^2}\,.\label{eq:partialGrhosecondderiv} \end{align}\tag{253}\] Now in preparation on our work on the sign of \(\frac{\partial G}{\partial y}\), we define \[\begin{align} g(y, \rho) := y-\alpha \operatorname{\mathbb{E}}\big[ \mathcal{A}(V)^2 \big]\,,\quad\text{thus}\quad\frac{\partial G}{\partial y}(y, \rho) = \frac{g(y, \rho)}{2(1+y)}\,.\label{eq:partialGpartialyhelperfunc} \end{align}\tag{254}\] We will need to show \(\frac{\partial g}{\partial y} > 0\) in an appropriate domain, which we do in Lemma 48. In preparation, we compute \[\begin{align} \frac{\partial g}{\partial y} &= 1-\alpha \operatorname{\mathbb{E}}\Big[ 2\mathcal{A}(V) \mathcal{A}'(V) \Big( \frac{\kappa'}{2\sqrt{\rho(1+y)}} - \frac{1}{2} Zy^{-1/2} \Big)\Big] \\ &= 1 - \frac{\alpha}{\sqrt{\rho(1+y)}} \operatorname{\mathbb{E}}\Big[ \kappa' \mathcal{A}(V) \mathcal{A}'(V) \Big] + \frac{\alpha}{\sqrt{y}} \operatorname{\mathbb{E}}\Big[ Z\mathcal{A}(V) \mathcal{A}'(V) \Big]\,. \end{align}\] Notice \(\frac{\partial V}{\partial Z} = -\sqrt{y}\), so Gaussian Integration by Parts gives \[\operatorname{\mathbb{E}}\Big[ Z\mathcal{A}(V) \mathcal{A}'(V) \Big] = -\sqrt{y} \operatorname{\mathbb{E}}\Big[ \mathcal{A}'^2(V)+\mathcal{A}(V)\mathcal{A}''(V) \Big]\,.\] Thus \[\begin{align} \frac{\partial g}{\partial y} = 1 - \frac{\alpha}{\sqrt{\rho(1+y)}} \operatorname{\mathbb{E}}\Big[ \kappa' \mathcal{A}(V) \mathcal{A}'(V) \Big] - \alpha \operatorname{\mathbb{E}}\Big[ \mathcal{A}'^2(V)+\mathcal{A}(V)\mathcal{A}''(V) \Big]\,.\label{eq:partialGpartialysecond} \end{align}\tag{255}\] To control the signs of the above, since we do not have non-negative margin – \(\kappa\ge 0\) or \(\kappa' = \kappa- xS\ge 0\) is not uniformly true – the signs of each component of the derivative do not work out directly in the same way as in [23]. Rather we show that for \(\alpha \le \alpha_0\), the part of the derivatives that do not have the correct sign are small in magnitude. We will carry this argument out in the proofs to follow.

10.2.0.2 Preliminary calculations for posterior.

We now define \[\begin{align} \label{eq:RSeqs95barV95def95posterior} \bar V := xS + \sqrt{\frac{y \rho}{1+y}}Z + \sqrt{\frac{\rho}{1+y}}W\,. \end{align}\tag{256}\] Here in Appendix 10.2, we let \(\langle \cdot \rangle\) denote a Gibbs average w.r.t. \(\operatorname{\mathbb{E}}_W \exp u(\bar V)\). In what follows, when the derivatives \(u^{l}\) are written, they are taken with argument \(\bar V\) unless otherwise stated. We obtain by Gaussian Integration by Parts, \[\begin{align} \frac{\partial G}{\partial \rho} &= \frac{\alpha}{2} \operatorname{\mathbb{E}}\big\langle u'' + u'^2 \big\rangle - \frac{\alpha y}{2(1+y)} \operatorname{\mathbb{E}}\big\langle u' \big\rangle^2 + \frac{1}{2\rho} - \beta\,, \tag{257}\\ \frac{\partial G}{\partial y} &= -\frac{\alpha \rho}{2(1+y)^2} \operatorname{\mathbb{E}}\big\langle \exp u' \big\rangle^2 + \frac{y}{2(1+y)}\,. \tag{258} \end{align}\] We will follow the same strategy as in the interpolators of establishing the saddle point structure of the RS equations. As such we compute \[\begin{align} \label{eq:posterior95partialGrho95twice} \frac{\partial^2 G}{\partial \rho^2} &= \frac{\alpha}{4}\Big( \mathrm{\small (I)}+ \mathrm{\small (II)}+ \mathrm{\small (III)}+ \mathrm{\small (IV)}\Big) -\frac{1}{2\rho^2} \,, \end{align}\tag{259}\] where \[\label{eq:posterior95secondderiv95expressions} \begin{align} \mathrm{\small (I)}&:= \frac{1}{1+y} \operatorname{\mathbb{E}}\Big[ \big\langle u'''' + 4u''' u' + 3u''^2 + 6 u'' u'^2 + u'^4 \big\rangle - \big\langle u'' + u'^2 \big\rangle^2 \Big]\,, \\ \mathrm{\small (II)}&:= \frac{y}{1+y} \operatorname{\mathbb{E}}\Big[ \big\langle u'''' + 4u''' u' + 3u''^2 + 6 u'' u'^2 + u'^4 \big\rangle + 2 \big\langle u''+ u'^2 \big\rangle \big\langle u' \big\rangle^2 \\ &\qquad \qquad \qquad \qquad \qquad - \big\langle u''' + 3u'' u' + u'^3 \big\rangle \big\langle u' \big\rangle - \big\langle u''' + 3u'' u' + u'^3 \big\rangle \big\langle u'' + u'^2 \big\rangle \Big]\,, \\ \mathrm{\small (III)}&:= \frac{-y}{2(1+y)^2} \operatorname{\mathbb{E}}\Big[ \big\langle u''' + 3u'' u' + u'^3 \big\rangle\big\langle u' \big\rangle - \big\langle u'' + u'^2 \big\rangle \big\langle u' \big\rangle^2 \Big] \,, \\ \mathrm{\small (IV)}&:= \frac{-y^2}{2(1+y)^2} \operatorname{\mathbb{E}}\Big[ \big\langle u'' + u'^2 \big\rangle^2 + \big\langle u''' + 3u''u' + u'^3 \big\rangle \big\langle u' \big\rangle + 3 \big\langle u' \big\rangle^4 - 5\big\langle u'' + u'^2 \big\rangle \big\langle u' \big\rangle^2 \Big]\,. \end{align}\tag{260}\] We also define similarly to 254, \[\begin{align} \label{eq:posterior95RS95g95def} g(y) := y(1+y) - \alpha \rho \operatorname{\mathbb{E}}\big\langle \exp u' \big\rangle^2\,,\quad\text{thus}\quad \frac{\partial G}{\partial y}(y, \rho) = \frac{g(y)}{2(1+y)^2}\,. \end{align}\tag{261}\] Again in Lemma 48, we show \(\frac{\partial g}{\partial y}>0\). In preparation, we compute \[\begin{align} \label{eq:posterior95secondderiv95y} \frac{\partial g}{\partial y} = 1 + 2y - \frac{\alpha \rho}{(1+y)^2} \Big( \mathrm{\small (I)}+ \mathrm{\small (II)}\Big)\,, \end{align}\tag{262}\] where \[\label{eq:posterior95secondderiv95y95expressions} \begin{align} \mathrm{\small (I)}&:= \operatorname{\mathbb{E}}\Big[ -\big\langle u''' + 3u'' u' + u'^3 \big\rangle \big\langle u' \big\rangle + \big\langle u'' + u'^2 \big\rangle \big\langle u' \big\rangle^2 \Big] \,, \\ \mathrm{\small (II)}&:= \operatorname{\mathbb{E}}\Big[ \big\langle u'' + u'^2 \big\rangle^2 + \big\langle u''' + 3u''u' + u'^3 \big\rangle \big\langle u' \big\rangle + 3 \big\langle u' \big\rangle^4 - 5\big\langle u'' + u'^2 \big\rangle \big\langle u' \big\rangle^2 \Big] \end{align}\tag{263}\]

10.2.0.3 Bounding relevant quantities for the interpolators.

To study the system 248 for the interpolators, we will need to bound various quantities involving the Inverse Mills’ Ratio. This step is not necessary to study 248 for the posterior. To this end, we first control \(\operatorname{\mathbb{E}}[\mathcal{A}(V)^2]\) in terms of \(y\). We then use this to upper bound \(y\). Finally we use these two upper bounds to upper bound the quantities of interest, namely \(\operatorname{\mathbb{E}}\big[\mathcal{A}(V)\big], \operatorname{\mathbb{E}}\big[\mathcal{A}(V)^2\big], \operatorname{\mathbb{E}}\big[|\kappa- xS|\mathcal{A}(V)\big]\).

The last preliminary step we need is the following Lemma, which lets us control various expectations of \(\mathcal{A}(V)\).

10.2.0.8 Finishing the argument.

By Lemma 45, to show 248 has a unique solution in the desired domain, it suffices to show 248 has a unique solution in \((y,\rho) \in [0,1] \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\). Now, we consider the signs of the derivatives of \(G\) in \(y\) and \(\rho\). This is done for the interpolators and posterior together in a unified manner.

The above Lemmas establish the desired convex-concave structure of the RS equations, and we are now ready to complete the proof of Proposition 9.

Finally, recall that for \((\alpha, \beta) \in [0, \alpha_0] \times [\beta_0, \beta_1]\), if there is a solution \((y,\rho) \in [0,\infty) \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\), then this solution must be in \([0,1] \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\) by Lemma 45. We conclude that 248 has a unique solution \((y,\rho) \in [0,\infty) \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\) (in particular, this solution must be in \([0,1] \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\)). By our initial remarks in this proof, it follows that 40 have a unique solution \((q, \rho) \in [0, C_{\mathrm{\small sol}}] \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\), as desired. Finally, as this unique solution \((y, \rho) \in [0,1] \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\), we have \(\rho - q = \frac{\rho}{y+1} \ge \frac{1}{2C_{\mathrm{\small sol}}}\). This proves the first part of Proposition 9.

We now prove the second part of Proposition 9. First, recall \(\frac{\partial^2 G}{\partial^2 y}\big(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x) \big)\) and \(\frac{\partial^2 G}{\partial^2 \rho }\big(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x) \big)\) are of opposite signs and nonzero by Lemma 47 and Lemma 48. Thus the determinant of the following Jacobian is strictly negative: \[\det \begin{bmatrix} \frac{\partial^2 G}{\partial^2 y}\big(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) & \frac{\partial^2 G}{\partial y \partial \rho} \big(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) \\ \frac{\partial^2 G}{\partial y \partial \rho} \big(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) & \frac{\partial^2 G}{\partial^2 \rho }\big(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big) \end{bmatrix} < 0~.\] Since \(G\) is infinitely differentiable in \(x, y, \rho\), and as \(\big(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\big)\) denotes the unique solution \((y, \rho) \in [0, \infty) \times [\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}]\) to the system \(\frac{\partial G}{\partial y} = \frac{\partial G}{\partial \rho}=0\), it follows by the Implicit Function Theorem that \(y_0(\alpha, \beta, x), \rho_0(\alpha, \beta, x)\) are infinitely differentiable in \(\alpha\), \(\beta\) and \(x\). Hence as \(y_0(\alpha, \beta, x) \ge 0\), it follows that \[q_0(\alpha, \beta, x) = \frac{y_0(\alpha, \beta, x) \rho_0(\alpha, \beta, x)}{1+y_0(\alpha, \beta, x)}\] is also infinitely differentiable in \(\alpha\), \(\beta\) and \(x\).

10.3 Proof of Lemma 23↩︎

For this proof, we make the same transformation to \(G(y,\rho)\) we considered in Appendix 10.2, where \(G(y, \rho)\) is defined as in 247 (again, here \(I\) is held fixed so \(F \equiv F_I\)). We let \(q_0 = q_0(\alpha, \beta, x)\), \(\rho_0 = \rho_0(\alpha, \beta, x)\), and \(y_0 = y_0(\alpha, \beta, x) = \frac{q_0}{\rho_0-q_0}\).

We first prove 1) of the Lemma. Differentiating the relations \(\frac{\partial G}{\partial \rho}(y_0,\rho_0)\equiv0\), \(\frac{\partial G}{\partial y}(y_0,\rho_0)\equiv0\) with respect to \(\beta\) (recall \(y_0, \rho_0\) depend on \(\beta\)), the Chain Rule gives \[\begin{align} \frac{\partial^2 G}{\partial \rho \partial y}(y_0,\rho_0)\cdot \frac{\partial y_0}{\partial \beta} + \frac{\partial^2 G}{\partial \rho^2}(y_0, \rho_0)\cdot \frac{\partial \rho_0}{\partial \beta} + \frac{\partial^2 G}{\partial \beta \partial \rho}(y_0, \rho_0) &= 0\,, \\ \frac{\partial^2 G}{\partial y^2}(y_0, \rho_0)\cdot \frac{\partial y_0}{\partial \beta} + \frac{\partial^2 G}{\partial \rho \partial y}(y_0, \rho_0) \cdot \frac{\partial \rho_0}{\partial \beta} + \frac{\partial^2 G}{\partial \beta \partial y}(y_0, \rho_0) &= 0\,, \end{align}\] where differentiability is justified by Proposition 9. Now identically as functions, we have \(\frac{\partial^2 G}{\partial \beta \partial \rho}=-1\), \(\frac{\partial^2 G}{\partial \beta \partial y}=0\) by the definition of \(G\) in 247. Multiplying the first relation above by \(\frac{\partial \rho_0}{\partial \beta}\) and the second relation above by \(\frac{\partial y_0}{\partial \beta}\) and subtracting, the \(\frac{\partial^2 G}{\partial \rho \partial y}\) terms cancel and we obtain \[\begin{align} \frac{\partial \rho_0}{\partial \beta} = \Big( \frac{\partial \rho_0}{\partial \beta}\Big)^2 \cdot \frac{\partial^2 G}{\partial \rho^2}(y_0, \rho_0) - \Big( \frac{\partial y_0}{\partial \beta} \Big)^2 \cdot \frac{\partial^2 G}{\partial y^2}(y_0, \rho_0) < 0\,, \end{align}\] where Lemma 47 and Lemma 48 justify that \(\frac{\partial^2 G}{\partial \rho^2}(y_0, \rho_0)<0\), \(\frac{\partial^2 G}{\partial y^2}(y_0, \rho_0)>0\). This proves 1) of the Lemma.

We next prove 2) of the Lemma. To this end, we will show that \(\rho_0(\alpha, 1/4, x) > 1-x^2\), \(\rho_0(\alpha, 9, x) < 1-x^2\). The existence and uniqueness of such a \(\beta = \beta(\alpha, x) \in [1/4, 9] \subseteq [\beta_0, \beta_1]\) then follows by part 1) of this Lemma, and moreover this establishes that \(\beta(\alpha, x) \in (1/4, 9)\).

We first show that \(\rho_0(\alpha, 1/4, x) > 1 \ge 1-x^2\). Define \[\begin{align} \mathrm{\small (I)}&:= \begin{cases} \operatorname{\mathbb{E}}\Big[ \kappa' \frac{(1+y_0)^{1/2}}{\rho_0^{3/2}} \mathcal{A}(V)\Big] &: \text{ for interpolators}\,, \\ \operatorname{\mathbb{E}}\big\langle u''(\bar V) + u'(\bar V)^2 \big\rangle - \frac{y}{1+y} \operatorname{\mathbb{E}}\big\langle u'(\bar V) \big\rangle^2 &:\text{ for posterior}\,, \end{cases} \end{align}\] where \(V\) is as in 249 and \(\bar V\) is as in 256, taken with arguments \(\rho_0, y_0\). By 251 for the interpolators and 257 for the posterior, we have \[\begin{align} \label{eq:rs95lemma95295equality} 0 = \frac{\alpha}{2} \mathrm{\small (I)}+ \frac{1}{2 \rho_0 } - \beta\,. \end{align}\tag{266}\] Now note \[\begin{align} \label{eq:rs95lemma95295bound} |\mathrm{\small (I)}| \le \begin{cases} \frac{\sqrt{2}}{\rho_0} K_{\mathrm{\ref{lem:controlexpectationofAW}}} C_{\mathrm{\small sol}}^{1/2} &: \text{ for interpolators}\,, \\ 2D^2+D &: \text{ for posterior}\,. \end{cases} \end{align}\tag{267}\] For the posterior, this simply uses that \(|u'|, |u''| \le D\). For the interpolators, we use the proof of Proposition 9, that \(\rho_0 \ge \frac{1}{C_{\mathrm{\small sol}}}\), \(y_0 \ge 0\), and that \(y_0 \le 1\) by Lemma 45. These facts combined with Lemma 46 imply the above bound on \(\big| \mathrm{\small (I)}\big|\).

Now as \(\alpha \le \alpha_0\) and by our conditions on \(\alpha_0\), we have by 267 that \(\alpha |\mathrm{\small (I)}| / 2 < \frac{1}{4 \rho_0}\). Combining with 266 now establishes \[\begin{align} \label{eq:rs95lemma95295bd1} \beta \in \Big( \frac{1}{4\rho_0}, \frac{3}{4\rho_0} \Big) \implies \frac{1}{4\beta} < \rho_0(\alpha, \beta, x) < \frac{3}{4\beta} \implies \rho_0(\alpha, 1/4, x) > 1 \ge 1-x^2\,. \end{align}\tag{268}\] Next, we claim that \(\rho_0(\alpha, 9, x) < 1-x^2\) for \(x \in [-1+\delta, 1-\delta]\). To this end, 266, 267 imply that \[\begin{align} \label{eq:rs95lemma95295bd2} 9 \le \frac{1}{2\rho_0(\alpha, 9, x)} + \frac{\alpha}{2} |\mathrm{\small (I)}| \implies \rho_0(\alpha, 9, x) < 1-x^2\,. \end{align}\tag{269}\] Here, the last inequality holds for \(x \in [-1+\delta, 1-\delta]\), using the definition of \(\delta\) in ?? for the interpolators or ?? for the posterior. As mentioned earlier, 268, 269 yields 2) of the Lemma.
Now to prove 3) of the Lemma, for fixed \((\alpha, x)\), it follows from Proposition 9 that \(f(\beta)\) is infinitely differentiable in \(\beta\). Let \(F(x, q, \rho) = \bar\Phi(x, q, \rho) - \beta (\rho + x^2)\). Note \(\frac{\partial F}{\partial \rho}=\frac{\partial F_I}{\partial \rho}\), \(\frac{\partial F}{\partial q}=\frac{\partial F_I}{\partial q}\), thus \(\frac{\partial F}{\partial \rho}(x, q_0, \rho_0) = \frac{\partial F}{\partial q}(x, q_0, \rho_0) = 0\). Therefore, \[\begin{align} \frac{\mathrm{d}}{\mathrm{d}\beta}f(\beta) &= 1 - \big( \rho_0 + x^2 \big) + \frac{\partial F}{\partial \rho}(x, q_0, \rho_0) \cdot \frac{\partial \rho_0}{\partial \beta} + \frac{\partial F}{\partial q}(x, q_0, \rho_0) \cdot \frac{\partial q_0}{\partial \beta}= 1 - \big( \rho_0 + x^2 \big)\,. \end{align}\] Thus \[\begin{align} \frac{\mathrm{d}^2}{\mathrm{d}\beta^2} f(\beta) &= -\frac{\partial \rho_0(\alpha, \beta, x)}{\partial \beta}\,. \end{align}\] By 1) of this Lemma, \(\frac{\mathrm{d}^2}{\mathrm{d}\beta^2} f(\beta) > 0\) on \([\beta_0, \beta_1]\), and by 2) of this Lemma, \(\frac{\mathrm{d}}{\mathrm{d}\beta} f\big(\beta(\alpha, x)\big)=0\). Hence 3) of the Lemma follows.
Next, we prove 4) of the Lemma. Since \(\rho_0\big(\alpha, \beta(\alpha, x), x) = 1-x^2\), we have \[\begin{align} f\big(\beta(\alpha, x)\big) = \bar\Phi\big( x, q_0\big(\alpha, \beta(\alpha, x), x\big), 1-x^2 \big)\,. \end{align}\] Note as \(x \in [-1+\delta, 1-\delta] \subseteq [-17/18, 17/18]\), \(1 \ge 1-x^2 \ge \frac{1}{10}\). Thus \(1-x^2 \in \big[\frac{1}{C_{\mathrm{\small sol}}}, C_{\mathrm{\small sol}}\big]\) as \(C_{\mathrm{\small sol}}\ge 10\). Recalling the definition of \(\bar\Phi\) in 28, define the following function of \(y\): \[\begin{align} \bar\Phi'(x, y, \rho) := \bar\Phi \Big(x, \frac{y\rho}{y+1}, \rho \Big)\,. \end{align}\] Note \(\frac{\partial \bar\Phi'}{\partial y}\big( y_0\big( \alpha, \beta(\alpha, x), x \big), 1-x^2 \big) = \frac{\partial G_I}{\partial y}\big( y_0\big( \alpha, \beta(\alpha, x), x \big), \rho_0\big( \alpha, \beta(\alpha, x), x \big) \big) = 0\). Now as a direct consequence of the proof of Lemma 48 and by 2) of this Lemma, \(\bar\Phi'(x, y, 1-x^2)\) attains its unique minimum on \([0, \infty)\) at \(y=y_0\big( \alpha, \beta(\alpha, x), x \big)\). By monotonicity of the transformation \(q = \frac{y\rho}{y+1}\), it follows that \(\bar\Phi(x, q, 1-x^2)\) attains a unique minimum on \([0, 1-x^2)\) at \(q = q_0\big( \alpha, \beta(\alpha, x), x \big)\). Thus \[\begin{align} f\big(\beta(\alpha, x)\big) = \inf_{q \in [0, 1-x^2)} \bar\Phi(x, q, 1-x^2) = \inf_{q \in [0,1)} \Phi(x, q)\,, \end{align}\] where the last step follows from the transformation \(q \leftarrow \frac{q}{1-x^2}\). This proves 4) of the Lemma.
Finally, to prove 5) of the Lemma, we claim that \(\beta(\alpha,x)\) is a continuous function of \((\alpha, x)\). To this end, note by 251 and 2), we know that \(\beta(\alpha, x)\) is the unique solution in \([\beta_0, \beta_1]\) to \[\begin{align} \beta= \frac{\alpha}{2} \mathrm{\small (I)}+ \frac{1}{2(1-x^2)} \,,\label{eq:betacontinuous95fixedpteq} \end{align}\tag{270}\] where \(\mathrm{\small (I)}\) is taken with \(\rho_0 = 1-x^2\). Let \(\bar f(\alpha, \beta, x)\) denote the right hand side of 270; this is continuous in \((\alpha, \beta, x)\) for \((\alpha, \beta, x) \in [0, \alpha_0] \times [\beta_0, \beta_1] \times [-1+\delta, 1-\delta]\) by Proposition 9. Consider any sequence \((\alpha_n, x_n) \rightarrow (\alpha^\star, x^\star)\) where \(\alpha_n \in [0, \alpha_0]\), \(x_n \in [-1+\delta, 1-\delta]\). Consider the corresponding \(\beta_n := \beta(\alpha_n, x_n)\). Since \(\beta_n \in [\beta_0, \beta_1]\), it follows that we can extract a convergent subsequence. Consider any convergent subsequence \(\beta_{n_k}\), with limit \(\beta^{\star}\). By the above it follows by compactness that \(\beta^{\star} \in [\beta_0, \beta_1]\). As \(\bar f(\alpha, \beta, x)\) is continuous, we have \[\begin{align} \beta^{\star} = \lim_{k\rightarrow\infty} \beta_{n_k} = \lim_{k\rightarrow\infty} \bar f(\alpha_{n_k}, \beta_{n_k}, x_{n_k}) = \bar f(\alpha^\star, \beta^\star, x^\star)\,. \end{align}\] However as \((\alpha^\star, x^\star) \in [0, \alpha_0] \times [-1+\delta, 1-\delta]\), the uniqueness of \(\beta(\alpha, x)\) in \([\beta_0, \beta_1]\) supplied by 2) implies that \(\beta^{\star} = \beta(\alpha^\star, x^\star)\). Therefore, \(\lim_{k \rightarrow \infty} \beta(\alpha_{n_k}, x_{n_k}) = \beta^{\star} = \beta\big(\lim_{k\rightarrow\infty}(\alpha_{n_k}, x_{n_k})\big)\). Since the convergent subsequence \(\beta_{n_k}\) is arbitrary, it follows that \(\beta_n\) converges to \(\beta(\alpha^\star, x^\star)\). Continuity of \(\beta(\alpha, x)\) follows. Combining this claim with 4) and Proposition 9 now proves 5). This concludes the proof of Lemma 23.

10.4 Proof of Propositions 2, 3, 5, 6, and Lemma 1↩︎

Here we first prove these four Propositions and then prove Lemma 1. We will prove these four Propositions together in a unified manner as follows. We show the following:

1. There is at most one pair \((x, q)\) satisfying \(\frac{\partial}{\partial x} \Phi(x,q)=\frac{\partial}{\partial q} \Phi(x,q)=0\).

2. This implies that the saddle point problem is uniquely achieved.

10.4.0.1 Proof of Part [it:part1].

First, we show that any \((x, q)\) satisfying \(\frac{\partial}{\partial x} \Phi(x,q)=0\), \(\frac{\partial}{\partial q} \Phi(x,q)=0\) must satisfy the relevant bivariate system of equations given in Propositions 2, 3, 5, 6 respectively. The proof follows from explicitly computing \(\frac{\partial}{\partial x} \Phi(x,q)\) and \(\frac{\partial}{\partial q} \Phi(x,q)\) and applying Gaussian Integration by Parts to simplify the resulting expression. We discuss the proof for Propositions 2, 3 for the interpolators; the proof for Propositions 5, 6 for the posterior is identical. Recalling the definition of \(S\) in 12 in the GMM case and 13 in the logistic case, we let \[\begin{align} V := \frac{\kappa- x S - \sqrt{(1-x^2)q}Z}{\sqrt{(1-x^2)(1-q)}}\,. \end{align}\] Explicitly differentiating \(\Phi(x,q)\) w.r.t. \(q\) and simplifying with Guassian Integration by Parts and the identity \(\mathcal{A}'(V) = \mathcal{A}(V)^2 - V\mathcal{A}(V)\) gives \[\begin{align} \frac{q}{1-q} &= \alpha \operatorname{\mathbb{E}}\Big[ \mathcal{A}(V) \Big\{ \frac{\kappa-xS}{\sqrt{(1-q)(1-x^2)}} - \frac{Z}{\sqrt{q(1-q)}} \Big\} \Big] \\ &= \alpha \operatorname{\mathbb{E}}\Big[ \mathcal{A}(V) \Big\{ V - \sqrt{\frac{1-q}{q}} Z \Big\}\Big] \\ &= \alpha \operatorname{\mathbb{E}}\big[ \mathcal{A}(V) V + \mathcal{A}'(V) \big] = \alpha \operatorname{\mathbb{E}}\big[ \mathcal{A}(V)^2 \big]. \end{align}\] Therefore, such \((x, q)\) satisfying the stationary point equations must satisfy ?? in the GMM case or ?? in the logistic case.

We will now show the proof that such \((x, q)\) satisfying the stationary point equations must satisfy ?? in the logistic case. The proof for ?? in the GMM case is similar (in fact simpler). We differentiate \(\Phi(x, q)\) w.r.t. \(x\) to obtain \[\begin{align} \label{eq:univariate95derivx95eq0} x \sqrt{(1-q)(1-x^2)} = \alpha \operatorname{\mathbb{E}}\Big[ \mathcal{A}(V) \big(S - \kappa x \big) \Big] = \alpha \operatorname{\mathbb{E}}\Big[ \mathcal{A}(V) \big( YG - \kappa x \big) \Big]\,, \end{align}\tag{271}\] where we used the explicit form \(S=YG\) from 13 (for the GMM case, we use \(S=G+\sqrt{\lambda}\) as per 12). We now simplify \(\operatorname{\mathbb{E}}\big[ \mathcal{A}(V) YG \big]\) via Gaussian Integration by Parts to obtain \[\begin{align} \label{eq:univariate95derivx95eq1} \operatorname{\mathbb{E}}\Big[ \mathcal{A}(V) YG \Big] = -\frac{x}{\sqrt{(1-x^2)(1-q)}} \operatorname{\mathbb{E}}\big[ \mathcal{A}'(V) \big] + \sqrt{\lambda} \operatorname{\mathbb{E}}\Big[ \varphi\big(-\sqrt{\lambda}YG \big) \mathcal{A}(V) \Big]\,. \end{align}\tag{272}\] Similar calculations, using the identity \(\mathcal{A}'(V) = \mathcal{A}(V)^2 - V\mathcal{A}(V)\), yield \[\label{eq:univariate95derivx95eq2} \begin{align} \operatorname{\mathbb{E}}\big[ \mathcal{A}'(V) \big] &= (1-x^2)(1-q) \operatorname{\mathbb{E}}\big[ \mathcal{A}(V)^2 \big] - \kappa\sqrt{(1-x^2)(1-q)} \operatorname{\mathbb{E}}\big[ \mathcal{A}(V) \big] \\ &\qquad + x\sqrt{\lambda (1-x^2)(1-q)} \operatorname{\mathbb{E}}\Big[ \varphi\big(-\sqrt{\lambda}YG \big) \mathcal{A}(V) \Big]\,. \end{align}\tag{273}\] Combining 271 , 272 , 273 and using the identity \(\alpha \operatorname{\mathbb{E}}\big[ \mathcal{A}(V)^2 \big] = \frac{q}{1-q}\) and rearranging yields ??. For Proposition 5, this establishes ??, which directly implies ?? and proves 1). For Proposition 6, 1) now follows from Proposition 1. We now prove 1) for Propositions 2, 3 for the interpolators.

To this end, our next step is to bound the value of \(x,q\) for solutions to \(\frac{\partial}{\partial x} \Phi(x,q)=0\), \(\frac{\partial}{\partial q} \Phi(x,q)=0\). Specifically, we will prove the following Lemma.

To prove Lemma 51, we will need the following useful Lemma. Its proof is analogous to that of Lemma 44 and we omit it for brevity.

We now are in a position to finish the proof of 1). Let \(f_1(x, q)\) denote the \(\small\rm LHS\) minus the \(\small{\rm RHS}\) of ?? or ?? in the GMM case and the logistic case respectively. We similarly let \(f_2(x,q)\) denote the \(\small\rm LHS\) minus the \(\small{\rm RHS}\) of ?? or ?? in these two respective cases. We now establish the following Lemma 53, which shows that all principal minors of the Jacobian of \(\big(f_1(x,q), f_2(x,q)\big)\) are strictly positive in the domain \((x, q) \in [0, \alpha K(\lambda)]^2\). Since any solution \((x,q)\) must lie in \([0, \alpha K(\lambda)]^2\) by Lemma 51, injectivity of \(\big(f_1(x,q), f_2(x,q)\big)\) on \((x, q) \in [0, \alpha K(\lambda)]^2\) and therefore 1) now follows from the Gale-Nikaido Theorem [49].

10.4.0.2 Proof of Part [it:part2].

We now complete the proof of Propositions 2, 3, 5, 6. Define the function \(f(x) := \inf_{q \in [0,1)} \Phi(x,q)\). Note \(f(x)\) is the infimum of an arbitrary family of continuous functions, and therefore is upper semicontinuous. First notice for the posterior, as \(u(x) \ge -D(\lambda)(|x|+1)\), we have \[\label{eq:rs95bivariate95lowerbd95u95posterior} \begin{align} &\operatorname{\mathbb{E}}\log \operatorname{\mathbb{E}}_{W} \exp u\Big( x S + \sqrt{(1-x^2)q}Z + \sqrt{(1-x^2)(1-q)} W \Big) \\ &\quad \ge -D(\lambda) \operatorname{\mathbb{E}}\Big[ 1 + \big| x S + \sqrt{(1-x^2)q}Z + \sqrt{(1-x^2)(1-q)} W \big| \Big] \ge -K(\lambda)\,. \end{align}\tag{274}\] For the interpolators, using that \(\mathcal{A}(x) \le 2x+1\) for all \(x \ge 0\) by Lemma 43 and that \(-\log \mathcal{N}(V) \le \log 2\) when \(V \le 0\), we obtain \(-\log \mathcal{N}(V) \le K(V^2_{+} + 1)\) for all \(V \ge 0\) where \(V_+ = \max\{V, 0\}\). Since \((a+b)_+ \le b_+\), it follows that \[\begin{align} \label{eq:rs95bivariate95lowerbd95u95interpolants} \operatorname{\mathbb{E}}\log \mathcal{N}(V) \ge -K \cdot \frac{ \kappa_+^2 + x^2 S^2 + (1-x^2) q Z^2}{(1-x^2)(1-q)}\,. \end{align}\tag{275}\] Thus for \(\alpha \le \alpha_0(\lambda, \kappa_+)\), we have for both the posterior and the interpolators, \[\begin{align} \label{eq:rs95bivariate95lowerbd95q} \Phi(x, q) \ge \frac{q}{4(1-q)} - \frac{\alpha K(\lambda) (\kappa_+^2+1)}{(1-x^2)(1-q)} + \frac{1}{2} \log(1-x^2) + \frac{1}{2} \log(1-q) - \alpha K(\lambda) \end{align}\tag{276}\] Taking \(x=0\) in the above display, bounding \(\alpha K(\lambda) (\kappa_+^2+1) \le 1/8\), and noting the infimum of the resulting lower bound is attained at \(q=1/2\) now proves that \(f(0) \ge -K(\lambda)\).

Next, notice \(f(x) \le \Phi(x, 0)\). Note for the interpolators or the posterior in the logistic case, we have \(u \le 0\) and therefore \(\Phi(x,0) \le \frac{1}{2} \log(1-x^2)\). For the posterior in the GMM case, we have \(u(x) = \sqrt{\lambda} x\) and therefore \[\label{eq:rs95bivariate95upperbd95u} \begin{align} &\operatorname{\mathbb{E}}\log \operatorname{\mathbb{E}}_{W} \exp u\Big( x S + \sqrt{(1-x^2)q}Z + \sqrt{(1-x^2)(1-q)} W \Big) \\ &\quad \le \log \operatorname{\mathbb{E}}\exp \sqrt{\lambda}\Big( x S + \sqrt{(1-x^2)q}Z + \sqrt{(1-x^2)(1-q)} W \Big) \le K(\lambda)\,. \end{align}\tag{277}\] Thus in all cases, we have \(\lim_{x\rightarrow \pm 1} \Phi(x, 0) = -\infty\), and justifying the existence of the following limit and the equality \[\begin{align} \lim_{x \rightarrow \pm 1} f(x) = -\infty\,. \end{align}\] The above derivation also proves that \(f(0) \le \Phi(0,0) \le K(\lambda)\). Now as \(f(0) \ge -K(\lambda)\) and \(\lim_{x \rightarrow \pm 1} f(x) = -\infty\), by the upper semicontinuity of \(f\) and as \(f(0) \le K(\lambda)\), the Weierstrass Extreme Value theorem implies that \(\sup_{x \in (-1,1)} f(x)\) is attained by at least one \(x^\star \in [-1,1]\) and that all such \(x^\star\) must lie in \([-1+\delta(\lambda), 1-\delta(\lambda)]\).

Consider any such \(x^\star\). As \(x^\star \in [-1+\delta(\lambda), 1-\delta(\lambda)]\) and \(\Phi(x^\star, q)\) is continuous in \(q\), 276 implies that \(\inf_{q \in [0,1)} \Phi(x^\star,q)\) is attained at \(q \in [0, 1 - \delta'(\lambda)]\), since the \(\small{\rm RHS}\) of 276 goes to \(+\infty\) as \(q \rightarrow 1\) and as \(\alpha \le \alpha_0(\lambda, \kappa_+)\). Thus \(\sup_{x \in (-1,1)} \inf_{q \in [0,1)} \Phi(x,q)\) is attained by at least one \((x^\star, q^\star)\).

Now consider any \(x \in (-1,1)\). For the interpolators, we explicitly compute using Gaussian Integration by Parts, \[\begin{align} \frac{\partial}{\partial q}\Phi(x, 0) = -\frac{\alpha}{2} \operatorname{\mathbb{E}}\big[ \mathcal{A}(V)^2 \big] < 0\,. \end{align}\] For the posterior, a similar calculation gives \[\begin{align} \frac{\partial}{\partial q}\Phi(x, 0) = -\frac{\alpha(1-x^2)}{2} \operatorname{\mathbb{E}}\Big[ \Big( \frac{\operatorname{\mathbb{E}}_W[ u' \cdot \exp u ]}{\operatorname{\mathbb{E}}_W [\exp u]} \Big)^2 \Big] < 0\,. \end{align}\] It follows that all such \(q^\star > 0\), and therefore any such \((x^\star, q^\star) \in (-1,1) \times (0,1)\). Hence any such \((x^\star, q^\star)\) solves the system \(\frac{\partial}{\partial x} \Phi(x,q)=0\), \(\frac{\partial}{\partial q} \Phi(x,q)=0\). By 1), it follows that \((x^\star, q^\star)\) is unique and satisfies \((x_{\star}, q_\star) \in [0, K(\lambda) \alpha]^2\) – for the posterior these bounds follow directly (GMM) or by Lemma 1 (logistic). This completes the proof.

11 Additional technical results↩︎

11.1 Truncated Logarithm↩︎

References↩︎

---

1. Cornell University, Department of Computer Science. Ithaca, NY, USA. Email: ayc74@cornell.edu↩︎

2. Cornell University, Department of Statistics and Data Science. Ithaca, NY, USA. Email: elalaoui@cornell.edu.↩︎

3. The upper bound only depends on \(\alpha_0\) and is monotonically increasing, so we can apply the bound \(\alpha_0\le 2\).↩︎