acceptodds
Under review as a conference paper at ICLR 2027

Sharp Variance Certificates for Log-Partition Gaps

Abstract

When does the variance of a log density ratio certify, rather than merely approximate, the error of a Gaussian approximation? For a standard Gaussian reference and a smooth log ratio that is square-integrable with its gradient, we prove that , , implies for the tilted target . The coefficient is optimal for every , and the bound extends the known concave case to nonconcave log ratios without bounded-gradient or small-error assumptions. A matrix refinement resolves direction and Hermite degree. It never exceeds the population matrix Fisher (log-Sobolev) certificate, is exact for Gaussian targets when the curvature matrix is their relative precision, and shows that weak curvature is paid only through the degree-one and degree-two components. These are the stationarity residuals of Gaussian variational inference and are known to vanish at its exact optimum. Consequently, at an exact full-covariance VI stationary point of a smooth log-concave target, under mild growth conditions, with no curvature margin. Explicit examples separate the variance, degree-resolved and Fisher certificates at nonvanishing error, and the bound extends to non-Gaussian references with two-sided curvature control. Gaussian polynomial moments and residual bounds make the certificates computable without the target normalizer. On Bayesian logistic posteriors, the scalar certificate is 0.29–0.67 times matrix Fisher across 48 historical fits, and under strong regularization it certifies KL tolerances that the Fisher certificate cannot reach. Under a fixed prior, the degree-resolved certificate decreases as data accumulate, and independent estimates place it within a factor of two of the estimated KL at moderate priors.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
variational inference, functional inequalities, log-partition functions, Gaussian approximation, KL divergence, uncertainty quantification

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_RnBuOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks when the variance of the log density ratio g=log⁡(p~/q)g=\log(\tilde p/q) under a Gaussian approximation QQ certifies, rather than merely approximates, the error KL(Q∥P)\mathrm{KL}(Q\|P). Its contributions are:

  1. Main result. If the target is everywhere at least κ\kappa times as curved as QQ (∇2g⪯(1−κ)I\nabla^2g\preceq(1-\kappa)I), then KL(Q∥P)≤Var⁡Q(g)/(2κ)\mathrm{KL}(Q\|P)\le \operatorname{Var}_Q(g)/(2\kappa). The constant is optimal, and the result extends the known concave case to nonconcave log ratios.
  2. Degree-resolved refinement. A matrix bound that splits gg into Hermite components never exceeds the matrix Fisher (log-Sobolev) certificate and is exact for Gaussian targets. It shows that weak curvature is paid only through the degree-one and degree-two components, which are the stationarity residuals of Gaussian VI. Hence at an exact VI fit of a log-concave target, KL≤32Var⁡Q(g)\mathrm{KL}\le\frac32 \operatorname{Var}_Q(g) with no curvature margin.
  3. Validation. The certificates are made computable via polynomial surrogates with rigorous residual bounds. On Bayesian logistic regression (Spambase, Covertype) they are 0.29-0.67x the matrix Fisher certificate. They certify more fits at tight tolerances under strong priors, and the degree-resolved bound keeps improving with nn in a synthetic fixed-prior study.
Critical strengths
  1. Clean and nice presented theory. The main bound is optimal, and its proof is transparent. The degree-resolved refinement says where weak curvature matters, and the link to VI stationarity residuals explains why converged VI fits certify far better than Laplace fits.

  2. Clear contribution with a normalizer-free implementation. The paper goes beyond an inequality to a deterministic procedure that needs neither sampling nor the normalizer, and it reports its numerical-assurance scope honestly.

Critical weaknesses
  1. Limited experiments and comparisons. The only systematic baseline is matrix Fisher, which the degree-resolved bound dominates by construction. Other computable error bounds (e.g. Kasprzak et al., 2025; Huggins et al., 2020) are not compared. Useful tolerances are reached only under very strong priors (gp∈{1,4}g_p\in\{1,4\}, where the prior supplies at least 50-80% of the curvature).

  2. Underdeveloped motivation. It is not argued convincingly when such certificates are needed in practice or what decisions they would change. The link to log-variance losses for neural samplers is not substantiated, since the theory covers only Gaussian (or strongly log-concave, two-sided) QQ.

Questions for authors
  1. The paper notes that stationarity in a restricted Gaussian family does not give the cancellation a=B=0a=B=0. In practice VI is often mean-field, where only the diagonal of BB vanishes, or trained with noisy reparameterization gradients. What does the certificate give in these cases?

  2. How do your certificates compare with the computable Laplace bounds of Kasprzak et al. (2025) on the same logistic models, either in TV directly or via Pinsker?

  3. The applications are limited to the evidence bracket and event probabilities. Can the certificates be turned into bounds on posterior means, marginal variances or predictive probabilities, for example through the transport conversion in Appendix? How would such bounds compare with those of Huggins et al. (2020) on the same fits?

2 comments

Thank you for the constructive review. The revision adds the comparisons you asked for, on identical fits for both methods (Section 6.4; Appendix G.3 to G.5 and G.7).

Q1. Mean-field and noisy-gradient VI (Appendix G.3, Table 8). Theorem 3.2 holds for every Gaussian. Mean-field stationarity removes the mean residual aa and the diagonal of the covariance residual BB but keeps its off-diagonal entries, so

KL(Q∥P)≤12tr⁡(BW2(K)B)+32∑k≥3Vk,\mathrm{KL}(Q\Vert P)\le\tfrac12\operatorname{tr}\big(BW_2(K)B\big)+\tfrac32\sum_{k\ge3}V_k,

with a weight W2W_2 that grows only like log⁡(1/κ)\log(1/\kappa). On Spambase (n=1024n=1024, d=58d=58) the mean-field certificates are 0.00103 nats at gp=1g_p=1 and 0.0586 at gp=4g_p=4, against estimated KL of 8.36×10−48.36\times10^{-4} and 0.0419. On Banknote, where features are strongly correlated, the certificate attributes 4.2 of its 4.29 nats to the off-diagonal term and so points to a full-covariance family; the estimated KL is 1.19 nats for the mean-field fit and 0.0176 for full covariance. For noisy-gradient VI we compute aa and BB from the target, independently of the optimizer: after 2×1042\times10^4 Adam steps on Spambase (gp=1g_p=1, 4; medians over three seeds) the certificates are 0.185 and 0.257 nats against estimates of 0.161 and 0.179. On Banknote, where κ=0.01\kappa=0.01, the mean residual dominates (8.5–8.9 nats against 0.79–0.80) and calls for more optimization. Over the 37 unconverged, mean-field and noisy Gaussians of our validation set, the certificate is a median of 1.40 times the estimated KL (Table 23).

Q2. Kasprzak et al. (2025) (Appendix G.4). On the 24 Spambase and Covertype targets of Section 6.4, our total-variation bound for the Laplace Gaussian, via Pinsker, is below one on 15 (0.024–0.046 at gp=1g_p=1); no evaluated variant of their Theorem 17 is below one on any (Table 10). Their theorem needs a likelihood maximizer, which separated designs lack, but not global strong log-concavity; ours needs a log-concave likelihood and the prior's curvature. On 12 synthetic fixed-prior Laplace fits where their theorem can be evaluated with certified constants (Table 11), their canonical bound is vacuous on all 12 and ours is informative on 9; with Corollary B.6 (Theorem 3.2 with the likelihood's curvature near the fit), ours is informative on all 12 (0.0199–0.0205 at d=8d=8, n=32,768n=32{,}768, against 0.200–0.210 for the best variant of theirs).

Q3. Means, variances, predictions; Huggins et al. (2020) (Appendix G.4 and G.5). Applied coordinate-wise, the transport inequality of Appendix F.2 gives, for coordinate jj with fitted standard deviation sjs_j and any certificate CC,

∣EPθj−μj∣≤δj,∣sdP(θj)−sj∣≤δj,δj=2C(Λ−1)jj,|\mathbb E_P\theta_j-\mu_j|\le\delta_j,\qquad|\mathrm{sd}_P(\theta_j)-s_j|\le\delta_j,\qquad\delta_j=\sqrt{2C(\Lambda^{-1})_{jj}},

and for a predictive probability kl(pQ(x)∥pP(x))≤C\mathrm{kl}(p_Q(x)\Vert p_P(x))\le C, which we intersect with a transport interval. On the six full-covariance VI fits at gp=1g_p=1 (Spambase, Covertype), all 327 coordinates have δj≤0.1sj\delta_j\le0.1 s_j and 299 of 300 predictive intervals have half-width at most 0.02. On the 24 of 48 fits where their Gaussian-reference bound is finite, the median ratio of their interval width to ours is 0.97 for means, 0.96 for predictions, 0.80 for standard deviations and 0.72 for variances. Ours use no sampling, theirs plug-in Monte Carlo estimates; under weaker priors both are much wider (Table 13).

Baselines and prior strength. The scalar certificate is not ordered with matrix Fisher: in Table 2, at KL≤0.001\mathrm{KL}\le0.001 it accepts 11 of 48 historical and 6 of 36 prospective fits, against 1 and 0 for Fisher. Useful KL certificates do not require $g_p\in\lbrace 1,4\rbrace $: with a fixed N(0,I)N(0,I) prior the full-covariance VI certificate is 0.0425–0.090 nats on Banknote, 1.97–2.43 times the KL computed by quadrature (Section 6.4, Table 21), 0.0184–0.405 nats on seven of ten standard small data sets (Table 17) and 4.03×10−64.03\times10^{-6} nats on HIGGS at full size (10,999,950 observations, d=29d=29; Table 19). In a sweep over prior scales (Table 22), the largest gpg_p certified at each tolerance equals the largest at which the estimated KL meets it in seven of the eight cells.

Motivation and neural samplers. Certificates are needed when a fitted Gaussian replaces the posterior and its accuracy must be guaranteed without sampling or ZPZ_P: to accept a fit at a stated tolerance (Section 1 and Appendix G.5), and to choose between Gaussians (on Banknote 0.0425 nats for full-covariance VI, 0.995 for Laplace, 4.29 for mean-field; Table 8). With the population loss LQ=12VarQ(g)\mathcal L_Q=\frac12\mathrm{Var}_Q(g), Theorem 3.1 reads KL(Q∥P)≤LQ/κ\mathrm{KL}(Q\Vert P)\le\mathcal L_Q/\kappa, so for Gaussian QQ the link to log-variance losses is a theorem, and Theorem C.1 extends it to strongly log-concave QQ with two-sided curvature.

Thanks for the clarification. I will keep my score

Reviewer_bs9qOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper seeks to certify the error KL(Q∣∣P)KL(Q||P), where QQ is a Gaussian distribution and PP is some intractable distribution, i.e., bound KL(Q∣∣P)KL(Q||P) by quantities that can be computed using information from only QQ. One such candidate quantity is the variance under QQ of the log-density ratio, g=log⁡(p~/q)g=\log(\tilde{p}/q), where p~\tilde{p} is the unnormalized target density and qq is approximate density of QQ. This work uses 12κg\frac{1}{2\kappa}g as the target quantity, where κ\kappa is the fraction by which the target density matches the curvature of the Gaussian distribution in every direction and at every point. This paper studies the problem of how to derive a certificate for this problem.

Critical strengths

Perhaps this work is unique in the way the certificate is setup and the several statistical guarantees such a variance characterized certificate allows for several theoretical exposition including bounds on gaussian curvature-variance and degree bounds, which seems unique to the literature (I am not an expert on this, so take this judgement with some grain of salt).

Critical weaknesses
  1. Some of the notations are introduced without explaining what is meant by them, e.g., ZPZ_P in line 2 of section 1. Acronyms are introduced without stating what they stand for (e.g., VI in abstract). The abstract especially reads a bit too condensed, and the general paper seems to be choppy. Some sections seem written by just a LLM and require further polish.
  2. I still don’t understand how adding 1/2κ1/2 \kappa gives anything better than just bounding gg. In fact, in most cases I see a constant factor improvement, e.g., Corollary 3.4. So I am unsure, why the authors chose to add the 1/2κ1/2 \kappa factor.
  3. I believe it is expensive to compute polynomial moments in step 3 of Algorithm 3. For giant data, say n≈106n \approx 10^6, is this even practical?
  4. The authors state that merely computing the Hessian is not sufficient and one would rather need a global relative-curvature control. This circles back to my concern in (3), as for a very large sample set, this algorithm would be completely impractical, and the associated bounds unattainable.
Questions for authors

Please try to address my concerns in the Weaknesses section.

3 comments

Thank you for the careful reading. The revision defines its terms at first use in the abstract and Section 1, adds a worked example of the role of 1/(2κ)1/(2\kappa) after Theorem 3.1, and reports the cost at n=220n=2^{20} and on two real data sets at full size (Section 6.4; Appendix G.6 and G.7).

1. Notation and presentation. The abstract and the first paragraph of Section 1 now define their terms at first use. VI is variational inference: fitting a tractable distribution QQ, here a Gaussian with density qq, to a posterior PP. KL is the Kullback–Leibler divergence KL(Q∥P)\mathrm{KL}(Q\Vert P), the error we bound, measured in nats. ZP=∫p~Z_P=\int\tilde p, the normalizer of the unnormalized posterior density p~\tilde p, is unknown in practice. The evidence lower bound (ELBO) is EQlog⁡(p~/q)\mathbb E_Q\log(\tilde p/q), and log⁡ZP−ELBO(Q)=KL(Q∥P)\log Z_P-\mathrm{ELBO}(Q)=\mathrm{KL}(Q\Vert P), so a bound on KL that does not need ZPZ_P also bounds log⁡ZP\log Z_P from above. The abstract now opens in plain terms and states the curvature condition in words.

2. Why 1/(2κ)1/(2\kappa). The factor multiplies the variance of g=log⁡(p~/q)g=\log(\tilde p/q), not gg itself:

KL(Q∥P)≤VarQ(g)2κ.\mathrm{KL}(Q\Vert P)\le\frac{\mathrm{Var}_Q(g)}{2\kappa}.

Half the variance approximates the KL divergence for small errors, but it is a guarantee only for targets at least as curved as QQ. If the target is at least a fraction κ\kappa as curved, 1/(2κ)1/(2\kappa) is the smallest coefficient valid for all such targets. For Q=N(0,1)Q=N(0,1) and the target N(30,10)N(30,10) (variance 10, so κ=0.1\kappa=0.1): KL=45.70\mathrm{KL}=45.70 nats, VarQ(g)/2=4.70\mathrm{Var}_Q(g)/2=4.70, VarQ(g)/(2κ)=47.03\mathrm{Var}_Q(g)/(2\kappa)=47.03 (the example is now in Section 3.1).

At a VI optimum the gain from the refinement grows without bound as κ\kappa decreases (Section 4). Splitting gg into its components of polynomial degree 1, 2, 3, … under QQ (Corollary 3.3) charges 1/(2κ)1/(2\kappa) only to the linear part, which vanishes at a VI optimum, and at an exact full-covariance VI fit of a log-concave target Corollary 3.4 gives KL≤32VarQ(g)\mathrm{KL}\le\frac32\mathrm{Var}_Q(g) with no κ\kappa. On synthetic logistic regression (d=32d=32) with a fixed N(0,I)N(0,I) prior and n=220n=2^{20} observations (κ=4.46×10−6\kappa=4.46\times10^{-6}), the degree-resolved certificate of the fitted VI Gaussian, which keeps the measured gradient terms, is 1.94×10−51.94\times10^{-5} nats, 74,780 times smaller than the 1.45 nats of the bound with 1/(2κ)1/(2\kappa) (Appendix G.6).

3. Cost at n≈106n\approx10^6. It is practical. For the benchmark above (Section 6.4 and Appendix G.6; polynomial degree 8, no subsampling), the complete certificate took 218 s on eight NVIDIA L4 GPUs, 1268 s on one, and 1979 s with 96 CPU processes; fitting added 35–37 s. Only the pairwise moments of step 3 (Figure 2) scale quadratically in nn; they are computed in blocks of rows, which bounds memory (peak resident memory of the parent process 2.21 GB with one GPU), and parallelize across devices. On real data with the same prior (Appendix G.6 and G.7, Table 19), the VI fit of SUSY is certified at 2.00×10−52.00\times10^{-5} nats at full size (4,999,950 observations, d=19d=19) in a run of about two hours on five L4 GPUs, and that of HIGGS (10,999,950 observations, d=29d=29) at 4.03×10−64.03\times10^{-6} nats in about eight hours on six such GPUs.

4. Global curvature. For these posteriors it needs no search over parameter space. A log-concave likelihood only adds curvature to the Gaussian prior, so the condition holds with $\kappa=\min\lbrace 1,\lambda_{\min}(L^\top\Lambda L)\rbrace $, computed from the prior precision Λ\Lambda and the fitted covariance LL⊤LL^\top alone (Section 2). This step took 1.7 s of the 218 s above (Table 15). The bounds are not out of reach either: the certificate at n=220n=2^{20} is the 1.94×10−51.94\times10^{-5} nats quoted above, and Corollary B.6 (Theorem 3.2 with the likelihood's curvature near the fit) brings it to 6.59×10−66.59\times10^{-6} (Table 20).

Reviewer_bs9qOpenReview ↗

response to rebuttal

I thank the authors for their response to my questions.

I am sorry, but has the paper been updated? I couldn't find all the updates (maybe a color coding would have helped), altho I do see and recall some improvements in the intro (e.g., definitions before notations are used). While the writing seems to be improved, it still feels choppy in certain areas and I believe it can be further polished (section transitions are not necessarily the best).

Perhaps I am a bit more convinced on the question raised by Reviewer ovTX, where they correctly observe that the proposed variance bound indeed becomes useful only with very strong regularization. Furthermore, the time reports for the Hessian are non comparable without any other competing algorithm and I circled back to complexity analysis which seems to be perhaps a roadblock in using this method practically (L4s have 24GBs of VRAM, which may help facilitate the runs).

As such I am more inclined to keeping my score.

Thank you for reading the revision. Yes, the paper has been updated: the PDF on the paper page is the revised version, and our comment to all reviewers summarizes what changed and where. The main changes are in the abstract and Section 1 (terms defined at first use), Section 2 (the cost of the curvature margin), Section 3 (a worked example after Theorem 3.1, and Proposition 3.5) and Section 6.4 (fixed-prior results, comparisons and cost); Appendices B.3, B.4 and G are new. We will polish the section transitions further in the final version.

Strong regularization. The degree-resolved certificate (Theorem 3.2 and Corollary 3.3) does not need it. A small margin κ affects only the terms that measure how far the fit is from convergence (the average gradient and Hessian of g under Q); these vanish at an exact full-covariance VI optimum, and the certificate includes their measured values. Under a fixed N(0, I) prior, the canonical case ovTX asked for, it gives (Section 6.4, paragraph "A genuinely fixed prior"; all data sets in Tables 17–19):

  • Banknote: 0.0425–0.090 nats, 1.97–2.43 times the KL divergence computed by quadrature (Table 21).
  • SUSY and HIGGS at full size (5 and 11 million observations): 2.00 × 10⁻⁵ and 4.03 × 10⁻⁶ nats (Table 19).
  • Synthetic logistic data (d = 8 and 32), n = 512 to 32,768: the certificate falls at every step, to 0.0003–0.0012 nats, while κ falls about fiftyfold.

On synthetic data at n = 2²⁰ (d = 32), κ = 4.46 × 10⁻⁶: the scalar bound of Theorem 3.1 is 1.45 nats on that fit, the degree-resolved certificate 1.94 × 10⁻⁵ nats (Appendix G.6).

Comparison with competing algorithms. In the follow-up study (Appendix G.4, paragraph "Assumptions, tuning and cost"), the median wall time per Gaussian was 1.6 s for our three certificates together, against 4.7 s for the bounds of Huggins et al. (2020) and 18 s for estimating the KL by importance sampling or sequential Monte Carlo; all variants of Kasprzak et al. (2025) took 4.0 s per target. The global curvature margin is one d × d eigenvalue computation with no search over parameters (Section 2); this phase, with the projections XL, took 1.2–1.9 s at every n from 1,024 to 2²⁰, against 33–35 s for the VI fit at n = 2²⁰ (Table 15).

Complexity and hardware. At n = 2²⁰ ≈ 10⁶, the complete certificate took 218 s on eight L4 GPUs and 1268 s on one (Section 6.4, paragraph "Cost"); without GPUs, it took 1979 s with 96 CPU processes. At fixed d and polynomial degree, only the pairwise moments of step 3 (Figure 2) grow quadratically in n. They are computed in blocks of rows, which bounds their memory: on one GPU, blocks of 512 rows kept the peak of this phase's GPU memory pool at 0.05 GB (Appendix G.6). All timings are for the complete certificate on every observation, without subsampling, low-rank or stochastic approximation.

Reviewer_ovTXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies error certificate for variational approximation using Gaussian densities. An intuitive candidate for such an error certificate is the variance of log-likelihood ratio, which comes from the first-order approximation of the Kullback-Leibler divergence. The paper provides sufficient conditions for such a variance to be a valid error certificate. In particular, the paper proves that the KL divergence is upper bounded by a constant multiple of this variance, with the constant depending on a relative curvature condition satisfied by the target density. The paper further derives improved bounds by more refined analysis, separating the contribution to the error from mismatch of different moments. The paper also provides algorithms for estimating such certificates, as well as numerical experiments to validate the theoretical results.

Critical strengths

The paper addresses a classical problem in variational inference, providing solid theoretical contributions. Notably, the result improves the Fisher information-based bounds. The refined analysis is indeed more interesting --- Corollary 3.4 establishes that as long as we find exact stationary point of the KL objective and the target is log-concave, the dependence on the relative curvature assumption can be removed. To my knowledge, the results are new and the proof techniques are of interest.

Critical weaknesses

On the theoretical side, consequences to variational approximations to posterior distributions are not sufficiently discussed. It would be useful to see how the bound scale with nn (and possibly dd) under

  • Strongly concave population log-likelihood; and
  • Non-strongly concave population log-likelihood, but with a strongly log-concave prior. It seems that for the later case, the constant κ\kappa will decay at the order 1/n1/n, but the curvature is not that bad for the bulk of the distribution. So perhaps some additional arguments can remedy this.

On the experimental side, it appears that the proposed variance bound is only useful with very strong regularization (e.g. gp=O(1)g_p = O(1)), and becomes vacuous when the prior is fixed. This is probably due to the issue with constant κ\kappa in the non-strongly-concave case I discussed above. (bDb_D is a bit better but still suffers from the same blow-up).

Questions for authors

It would be useful to address my questions in the weakness part. In particular, could the author clarify the theoretical consequences to approximating the posterior distribution under some statistical models? Also, for the constant κ\kappa in the experimental studies, I wonder if a variant of Corollary 3.4 could help here (by accounting for the computational error in approximating the stationary point). The paper would be much more convincing by showing some bounds that are useful for the canonical case of fixed prior.

3 comments

Thank you for the detailed review and its suggestions. The revision adds the fixed-prior experiments you asked for, Proposition 3.5 on scaling in nn and dd, and, as Corollary B.6, the consequence of Theorem 3.2 that your remark on the bulk points to.

Useful bounds under a fixed prior (Section 6.4; Appendix G.2, G.7 and G.8). With a fixed N(0,I)N(0,I) prior, full-covariance VI fits are certified on real data at full size (Table 19): 2.00×10−52.00\times10^{-5} nats on SUSY (4,999,950 observations, d=19d=19), 4.03×10−64.03\times10^{-6} on HIGGS (10,999,950, d=29d=29) and 0.127 on Covertype with centred indicator columns (580,962, d=55d=55), an encoding added after standardized indicators gave a vacuous certificate. On ten standard small data sets with the same prior (Table 17) the bound is 0.0157–0.505 nats on eight, 1.73–3.64 times the estimated KL, and 1.04 and 3.43 nats on the two with 61 and 167 parameters for 208 and 476 rows (with Corollaries B.5 and B.6; 0.0184–0.962, 3.04 and 12.5 for the certificate of Proposition B.4 alone). On nested subsets of SUSY and HIGGS the certificate is at most 0.173 nats already at n=256n=256 (Table 18). The same tables show where it stays large: MiniBooNE, DNA and Covertype with standardized indicators. On Banknote (d=5d=5, n=64n=64–13001300) the certificate is 0.0425–0.090 nats, 1.97–2.43 times the KL divergence computed by quadrature (Section 6.4, Table 21). The remainder term does not grow as κ→0\kappa\to0: Proposition B.4 weights it by at most 3\sqrt3, and at a VI optimum the terms that carry 1/κ1/\kappa vanish (Corollary 3.3).

Bulk curvature (Corollary B.6, Appendix B.4). Your remark about the bulk is right, and Theorem 3.2 turns it into a corollary. With mim_i and sis_i the mean and standard deviation of observation ii's linear predictor under QQ, its likelihood curvature is at least ci=σ′(∣mi∣+ρsi)c_i=\sigma'(|m_i|+\rho s_i) wherever the predictor stays within ρsi\rho s_i of mim_i. Applying Theorem 3.2 to the target modified outside these slabs gives

KL(Q∥P)≤12EKρ(g~)+log⁡(1+τρ),Kρ=L⊤(Λ+X⊤diag(c)X)L,\mathrm{KL}(Q\Vert P)\le\tfrac12\mathcal E_{K_\rho}(\tilde g)+\log(1+\tau_\rho),\qquad K_\rho=L^\top\big(\Lambda+X^\top\mathrm{diag}(c)X\big)L,

where τρ\tau_\rho, given explicitly in Corollary B.6, bounds e−ELBOe^{-\mathrm{ELBO}} times the unnormalized posterior mass outside the slabs, and hence also the posterior mass there. On the fixed-prior benchmark at n=220n=2^{20} (d=32d=32), where κ=4.46×10−6\kappa=4.46\times10^{-6}, the certificate falls from 1.94×10−51.94\times10^{-5} to 6.59×10−66.59\times10^{-6} nats (Table 20); in the synthetic fixed-prior study at n=32,768n=32{,}768 (d=32d=32) it goes from 2.97–3.01 to 1.20–1.22 times the estimated KL.

Computational error (Corollary 3.3; Appendix G.3). The variant of Corollary 3.4 you ask for is Corollary 3.3; for a Gaussian prior and a convex likelihood, Proposition 3.5 weights the same residuals by the matrices K−1K^{-1} and W2(K)W_2(K). For any Gaussian, with aa and BB the measured stationarity residuals,

KL(Q∥P)≤∥a∥22κ+W2(κ)2∥B∥F2+32∑k≥3Vk,W2(κ)=O(log⁡(1/κ)).\mathrm{KL}(Q\Vert P)\le\frac{\Vert a\Vert ^2}{2\kappa}+\frac{W_2(\kappa)}{2}\Vert B\Vert _F^2+\frac32\sum_{k\ge3}V_k,\qquad W_2(\kappa)=O(\log(1/\kappa)).

On Banknote (n=1300n=1300) the certificate is 0.995 nats at the Laplace start, 0.0458 after one VI step and 0.0423 after three, when the two residual terms together are 1.9×10−51.9\times10^{-5} (Table 8).

Scaling in nn and dd (Proposition 3.5; Appendix B.3). If the sample negative log-likelihood has ∇2ℓ⪰nm0I\nabla^2\ell\succeq nm_0I everywhere and ∥∇3ℓ∥F≤nG3\Vert \nabla^3\ell\Vert _F\le nG_3, an exact fit has KL≤G32/(4nm03)=O(1/n)\mathrm{KL}\le G_3^2/(4nm_0^3)=O(1/n). For logistic regression with ∥xi∥2≤R2\Vert x_i\Vert ^2\le R^2 and R2=O(d)R^2=O(d), Proposition 3.5 gives O(d2/n)O(d^2/n) at exact fits whose covariance contracts like 1/n1/n, and therefore, by Pinsker's inequality TV≤KL/2\mathrm{TV}\le\sqrt{\mathrm{KL}/2} (Section 6.4), total variation O(d/n)O(d/\sqrt n). Empirically, the certificate decreases at every step from n=512n=512 to 32,76832{,}768 in the synthetic fixed-prior study with d=8d=8 and 32 (Section 6.4, Table 7), and on the nested SUSY and HIGGS subsets it is at most 7.46×10−57.46\times10^{-5} nats at n=220n=2^{20} (Table 18).

Thanks for the response and additional experimental results. Some of my concerns are addressed. However, it still seems that most results rely on either uniform lower bounds on the curvature or a very strong prior. So the practical value may be limited. I think this is a borderline cases.

Thank you for the follow-up. On the remaining point, the fixed-prior results rely on neither a strong prior nor a large uniform curvature bound.

  • Prior. Banknote, SUSY and HIGGS use the fixed N(0, I) prior. At full size the certificates are 2.00 × 10⁻⁵ nats on SUSY and 4.03 × 10⁻⁶ on HIGGS (5 and 11 million observations; Table 19); on Banknote they are 0.0425–0.090 nats, 1.97–2.43 times the KL computed by quadrature (Table 21). All data sets of the panel are in Tables 17–19.
  • Uniform curvature. The uniform bound comes with the prior: with a log-concave likelihood the Gaussian prior supplies it, and some such structure is unavoidable, since without it no multiple of the variance bounds KL (Appendix E). Its size is paid only on the stationarity residuals (Corollary 3.3): at n = 2²⁰ (d = 32), κ = 4.46 × 10⁻⁶ and the certificate is 1.94 × 10⁻⁵ nats (Appendix G.6). Corollary B.6, which follows your remark on the bulk, adds the likelihood's curvature where Q puts its mass, and its gain grows with n: with it, on the synthetic fixed-prior fits at d = 32, n = 32,768, the certificate is 1.20–1.22 times the estimated KL for VI fits and 1.53–1.55 times for Laplace fits (Table 20).
  • Compared with a bound that avoids global strong log-concavity. On the 12 synthetic fixed-prior Laplace fits where the bound of Kasprzak et al. (2025) can be evaluated, it is vacuous on all 12 and its best variant on 9 (0.200–0.210 in total variation on the other 3); ours, with Corollary B.6, is 0.0199–0.114 on all 12 (Table 11).

We hope this resolves the remaining concern and would be grateful if the rating reflected it.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the three reviewers. A revised PDF is uploaded; this comment summarizes what changed and where. The paper keeps its title and section structure, and its main text is within the ten pages allowed during the discussion. In the main text, the abstract and Section 1 define their terms at first use and summarize the new results, the abstract states the curvature condition in words, and Section 1 names a use of the certificates. Section 2 adds that the curvature margin needs one d×dd\times d eigenvalue computation and no search; Section 3 adds a worked example after Theorem 3.1, a sentence on mean-field fits and Proposition 3.5 on approximate stationarity and scaling; Section 6.4 reports the fixed-prior results, optimization error, the comparisons the reviews asked for and the cost at n=220n=2^{20}; Section 8 points to the fixed-prior results. Beyond these, some sentences are qualified or clarified (Sections 2, 3 and 6.4) or shortened (Section 7 and the conclusion in Section 8), one word changes in Section 5, and Section 4 is unchanged; the reproducibility statement adds that the follow-up study also uses GPUs. Corollary B.5, Appendices B.3 and B.4 and Appendix G, a follow-up study under a frozen protocol (86 cases) with later analyses, are new; proofs, tables and details are in the appendices.

1. Fixed priors on real data (ovTX, RnBu). Section 6.4 and Appendices G.7 and G.8. Appendix G.2 reports Banknote (d=5d=5) under a fixed N(0,I)N(0,I) prior, with KL computed by quadrature. A real-data panel with the same prior, designed before its runs, covers ten standard small data sets (Table 17) and Covertype, HIGGS, SUSY and MiniBooNE by sample size (Table 18). At full size (Table 19), full-covariance VI fits are certified at 2.00×10−52.00\times10^{-5} nats on SUSY (4,999,950 observations) and 4.03×10−64.03\times10^{-6} on HIGGS (10,999,950) in post hoc runs, and at 0.127 on Covertype with centred indicator columns (580,962), an encoding added after standardized indicators gave a vacuous certificate. These tables and Table 5 include the cases where the certificate stays large, such as Spambase and MiniBooNE.

2. Bulk curvature under weak priors (ovTX). Corollary B.6 (Appendix B.4) applies Theorem 3.2 with the likelihood's curvature in the bulk of the fitted Gaussian; Corollary B.5 sharpens the remainder of Proposition B.4. Results: Appendix G.7 and Table 20.

3. Scaling in nn and dd (ovTX). Proposition 3.5 and Appendix B.3; certificates by sample size in Tables 7 and 18.

4. Comparisons and prior strength (RnBu). Mean-field and noisy-gradient VI (Appendix G.3); Kasprzak et al. (also on 12 synthetic fixed-prior fits and 64 real-data fits of the panel) and Huggins et al. on identical fits (Appendix G.4, Tables 10 to 12); posterior means, standard deviations and predictions (Appendix G.5); a sweep over prior scales (Table 22); a validation set of 152 Gaussians (Table 23).

5. Presentation and cost (bs9q). Terms are defined at first use in the abstract and Section 1; a worked example of the factor 1/(2κ)1/(2\kappa) follows Theorem 3.1; Appendix G.6 reports the cost at n=220n=2^{20} and of the full-size runs.

All logistic certificates are floating-point evaluations of the analytic bounds, as in the submission. KL references are sampling-based estimates, quadrature on Banknote or the certified Laplace intervals of Table 19, and never enter a certificate. Appendix G states which analyses followed protocols fixed before their runs, and Appendix G.8 lists the limitations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.