Sub-optimality of the Naive Mean Field approximation for proportional high-dimensional Linear Regression
Authors: Jiaze Qiu
Venue: NeurIPS 2023 poster (2023)
Keywords: Variational Bayes; Naive Mean Field; Gaussian comparison inequalities; High-dimensional statistics; Proportional asymptotic.

Abstract: The Naïve Mean Field (NMF) approximation is widely employed in modern Machine Learning due to the huge computational gains it bestows on the statistician. Despite its popularity in practice, theoretical guarantees for high-dimensional problems are only available under strong structural assumptions (e.g. sparsity). Moreover, existing theory often does not explain empirical observations noted in the existing literature. 
 
In this paper, we take a step towards addressing these problems by deriving sharp asymptotic characterizations for the NMF approximation in high-dimensional linear regression. Our results apply to a wide class of natural priors and allow for model mismatch (i.e. the underlying statistical model can be different from the fitted model).  We work under an iid Gaussian design and the proportional asymptotic regime, where the number of features and number of observations grow at a proportional rate. As a consequence of our asymptotic characterization, we establish two concrete corollaries: (a) we establish the inaccuracy of the NMF approximation for the log-normalizing constant in this regime, and (b) we provide theoretical results backing the empirical observation that the NMF approximation can be overconfident in terms of uncertainty quantification.

Our results utilize recent advances in the theory of Gaussian comparison inequalities. To the best of our knowledge, this is the first application of these ideas to the analysis of Bayesian variational inference problems. Our theoretical results are corroborated by numerical experiments. Lastly, we believe our results can be generalized to non-Gaussian designs and provide empirical evidence to support it.

Sub-optimality of the Naive Mean Field approximation for proportional high-dimensional Linear Regression
Jiaze Qiu Department of Statistics Harvard University Cambridge, MA 02138, USA j siazeqiušg ha harvard.
Abstract
The Naive Mean Field (NMF) approximation is widely employed in modern Machine Learning due to the huge computational gains it bestows on the statistician. Despite its popularity problems are only available under strong structural assumptions (e.g., sparsity). Moreover, existing theory often does not explain empirical observations noted the existing literature.
practice, theoretical guarantees for nigh-dimensional
In this paper, take step towards addressing these problems by deriving sharp asymptotic characterizations for the NMF approximation in high- nigh-dimensional linear regression. Our results apply for model mismatch (i.e., the underlying statistical model can be different from the fitted model). We work under an rid Gaussian design and the proportional asymptotic regime, where the number of features and the number of observations grow proportional rate. As consequence of our asymptotic characterization, we establish two concrete corollaries: (a) we establish the inaccuracy of the NMF approximation for the fog-normalizing constant in this regime, and (b) provide theoretical results backing the empirical observation that the NMF approximation can be overconfident in terms of uncertainty quantification.
wide class of natural priors and allow
Our results utilize recent advances in the theory of Gaussian comparison inequal- ities. To the best of our knowledge, this is the first application of these ideas the analysis of Bayesian variational inference problems. Our theoretical results are corroborated by numerical experiments. Lastly, we believe our results be generalized to non-Gaussian designs and provide empirical evidence to support it.
Introduction
The Naive Mean Field (NMF) approximation widely employed in modern Machine Learning as an approximation the actual intractable posterior distribution. The NMF approximation is attractive as (a) it bestows huge computational gains, and (b) it is naturally interpretable and can provide access easily interpretable summaries of the posterior distribution e.g., credible intervals. However, these two advantages may be overshadowed by the following limitations: (a) it is a priori unclear whether this strategy of using product distribution as a proxy for the true posterior will result in a "good" approximation, and (b) it has been empirically observed that NMF often tends to be significantly over-confident, especially when the feature dimension p is not negligible compared to the sample size n. In the traditional asymptotic regime (p fixed and - oo), significant progress was made in understanding these two problems for different statistical models, see for instance [8] and references therein. On the other hand, in the complementary high-ding nigh-dimensional regime where both n and p are growing, Ghorbani al. recently established an instability result for the topic model under the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Appres menter rommaring reedwer pyppoel.gem
Cra eredite rstoraat creeented AMB
to
Liitiigg
0.11
132
140 Oracin Decert Aecee
315
0.1
222
340
Figure 1: These three figures serve as visual summary of our main results when the Gaussian Spike and Slab prior is adopted, i.e., NMF does not provide up to leading order correct approximation the log-oormalizing constant (left), and the estimated credible regions suggested by the NMF distribution do not achieve the nominal coverage (middle), even when NMF could achieve close to optimal MSE. Please see Lemma 6 for definitions of the Gaussian Spike and Slab prior and the hyper-parameters and 2
proportional asymptotics, i.e., n (p). fact, in this regime, based on non-rigorous physics arguments, it is conjectured and partially established that instead of the NMF free energy one should optimize the TAP free energy. For linear regression particular, please see T8). On the other hand, positive results of NMF for high-dimensional linear regression were recently established in [16] when p = o(n).
In this paper, we investigate the performance of NMF approximation for linear regression under the proportional asymptotics regime. As a consequence of our asymptotic characterization, we establish two concrete corollaries: (a) we establish the inaccuracy of the NMF approximation for the nog-onzmag constant in this regime, and (b) provide theoretical results backing the empirical observation that NMF can be overconfident in constructing Bayesian credible regions.
Before proceeding further, formalize the setup under investigation. Given data {[ 24) i < n., E R, Iz E R², the scientist fits linear model
Y XB* +
(1)
sid where E ~ NN(0, and 3 E SP a p-dimensional latent signal. We consider either S S 1-1, In fact, unless explicitly specified otherwise, S = R. Most of our results generalize to bounded support naturally. To recover the latent signal, the scientist adapts a Bayesian approach. She puts iid prior on 3, 's, namely, dTv(3) distribution B,
or
I dd;(B;) and then constructs the posterior
du dmo
dpxww (0) x e + -
(3)
dro
with normalization constant
Zp = Zx(,,)
e - -X91 (dB))
(2)
Our results are established assuming that the design matrix X randomly sampled from an iid Gaussian ensemble, i.e., Xij iid NN(0, 1/n), while we provide empirical evidence for more general classes of X that has iid entries with mean 0 and variance 1/n. Moreover, we assume n/p - a E (0, 00) as n.p co.
Definition (Exponential tilting). For any y (n, 72) R E+ and probability distribution on S, we define n" as
d dπ (z) exp (100
22 x22²-c())) -(7)) d()) =x(() = log exp (nLx= 722 T(dx).
Note that cl-) depends on the distribution æ and usually referred to as the cumulant generating function in the statistics literature.

---

Using this definition of exponential tilts, the (X"X (X"x)ss1 terms in 2 can be absorbed into the base measure
P
m(d3) & x 2 n3 (d3,), 1=1
II
where n, := (0,,d)) and d, = X)s By the classical Gibbs variational principle (see for instance 27 the log-normalizing constant can be expressed as a variational form,
o²
log 2p
inf Q
BQ
2x 1l - x
+ +KK (Q|(
inf Q
EQ
ly
X3112
de o 2
+ DKL
Q
II n
)
Σ
c(0, d:),
20
where the inf is taken over all probability distribution on S". While the infimum is always attained and only if Q = μs, the Naive Mean Field (NMF) approximation restricts the variational domain to product distributions only and renders a natural upper bound,
P
inf Q-I72_1
EQ
20
X1112
Σ 1=1
6 2
DRL
Q
II क
-
-
c0 d:)
(3)
can be shown that the product distribution Q that achieves this infimum is exactly the one closest to 1r, in terms of KL--divegeence Before moving forward, we need some additional definitions and basic properties exponential tilts. The first lemma establishes that instead of using (Y1, 72) we can also use (u, 72) (Bu U, 92) to parameterize the tilted distribution.
Lemma (Basic properties of the cumulant generating function c(-)). supp(x) denote the support of n. If ((x) == inf supp(z) and ((T) == sup > then the following conclusions hold.
Let c(.) be in Definition 7
(a) (m, 72) 8elmi122 Ex (X) is strictly increasing in nn for every "i2 R.
(b) For any E (mn(T), M(T)), there always exists unique h (u, 12) E I such that 8(h (u, 72) 72) = u.
Definition (Naive mean field variational objective). With d; == X)a/o, we define Mp(u). M + R as
Mp(u)= =
20 -
P Ily Xull
Σ
G(u;,d))
duf 2
where defined as a possibly extended real valued function on [m((T, M(T]] x R
G(u, d) == DKT. (1) = uh(u, d) c(h(u, d), c(0,
Eu (m((), ifu M(T) do R,
= DKL
Too (0.d0
DKL Too ((
= m(m) - xc, d R.
in which h(---) was defined in Lemma and noo and n-co are degenerate distributions which assigns all measure to M(T) and m(π) respectively.
Note that under product distributions, the (F(()) term in ( parameterized by the mean vector := 3 and exponential tilts of π, 's minimize the KL--divegeence term. Therefore, the scaled log- noggmommliiing function, which is also referred to as the average free energy in statistical physics parlance and (log) evidence in Bayesian statistics, is bounded by the following variational form,
1
1 Σ
inf Mp(u) log Zp S p (E)((
c(0, d,)
log NNF
(4)
p
p
p
3

---

The right- hand side is equal to ( and is also referred to as the evidence lower bound (ELBO) or NMF right-hand free energy, which can be used as a model selection criterion, see for instance [4. Asymptotically, the second term is nothing but a constant since it concentrates around c(0,, 1/0²) as n. co.
The main theoretical question of interest here is whether this bound in (4) is asymptotically tight or not, which serves as the fundamental first step towards answering the question of whether NMF distribution a good approximation of the target posterior. Please see 44 27 for comprehensive surveys on variational inference, including but not limited to NMF approximation.
To derive sharp asymptotics for the NMF approximation, the key observation is that the optimization problem is convex under certain priors. We then employ the Convex Gaussian Min-max Theorem (CGMT). CGMT is generalization of the classical Gordon's 's Gaussian comparison inequality ()). which allows one to reduce a minimax problem parameterized by Gaussian process to another (tractable) minimax Gaussian optimization problem. This idea was pioneered by Stojnic [2 and then applied to many different statistical problems, including regularized regression, M-estimation, and so on, see for instance [15 (24) Unfortunately, concentration results derived from CGMT require both Gaussianity and convexity. This is exactly why we need the Gaussian design assumption in our analysis. In the meantime, though we do not pursue this front theoretically, we provide empirical evidence for more general design matrices in the Supplementary Material. It is worth noting that there a parallel line of research that aims to develop universality results for these comparison techniques. We refer the interested reader to and references within.
Let us emphasize that our main conceptual concern is not investigating whether 44) convex optimization procedure gives a good point estimator, but instead evaluating whether NMF as a strategy or product distributions for the true posterior. Nevertheless, this optimizer's ' asymptotic mean square error can also be characterized as by-product of our main theorem.
family of distributions can provide "close correct" approximation
Regarding the accuracy of variational approximations in general, certain contraction rates and asymptotic normality results were established in the traditional fixed p large n regime [28] 17 10]. However, under the high high-dimensional setting and scaling we consider in the current paper, without extra structural assumptions (e.g., sparsity), both the true posterior and its variational approximation are not expected to contract towards the true signal, which also explains why one is instead interested in whether the log-normalizing constant can be well approximated, standard of "correctness". Ray et al. [19 studied a pre-specified class of mean field approximation in sparse high-dimensional logistic regression. Recently, the first known results mean and covariance approximation error of Gaussian Variational Inference (GVT) in terms of dimension and sample size were obtained in [1]
weaker
2 Results
This section starts with some necessary definitions and our main assumptions. Then, present main theorem and one natural corollary. Finally, we identify a wide class of priors that would ensure the convexity of the NMF objective, which plays crucial role in our analysis.
2.1 Notations and main assumptions
Notations: We use the usual Brchhmann-Landee notation O(), o(-), O()) for sequences. For a
sequence of random variables (Xp : p 2 1}, we say that X, = (1) if X, E 0 as p -> oc and X, = op(((p) if Xp) = (1). We use C, Ci, C2... to denote positive constants independent of n, p. Further, these constants can change from line to line. For any square symmetric matrix A, ||Alllo and || denote the matrix operator norm and the Frobenius norm, respectively.
Assumption 1 (Proportional asymptotics). We assume n/p + a E (0). as n. + cc.
Assumption 2 (Gaussian features). For all our theoretical results, we assume the design matrix X is randomly sampled from an iid Gaussian ensemble, i.e. X.² Definition 3. Define F : (m(T), M (T)) + E as
sid No0 1/n).
x² u²Ed1
1
x2
F(u)= = Fr.o (u) = G(u, Edd)
= G
u,
2
20
4

---

Definition 4 (The NMF point estimator), Recalling the NMF objective Mp(-) as in Definition 2 let à -ANMP= == arg mii.1e Mn) be the NMF point estimator, which is also the mean vector of the product distribution (Q) that best approximates the posterior in terms of Kl--ivergence. We refer to this optimal product distribution as the NMF distribution.
Assumption (Convexity F(-)). We assume F.) is strongly corvex on S 5
As alluded to, our analysis relies on the convexity of the "penalty" term F()). Please note that the definition of F()) only depends the prior chosen by the statistician, rather than the "true prior" π². Therefore, to support this assumption, we provide a few sufficient conditions that identify a broad class of priors that ensure (strong) convexity of F(.) in Section 2.3
Throughout, we work under a partially well-specified situation, i.e., model [ is assumed to be correct, but [3, is may not have been priori sampled iid from Instead, we assume the empirical distribution of 33 converges in L2 a probability distribution n' supported on In addition, the noise level x² is fixed and known to the statistician. Last but not least, xt is assumed to have finite second moment and let 52 == ET [T < co.
2.2
Main results
From now on, we always assume Assumption I and Next, we introduce a scalar denoising function, which is just the proximal operator of F F(.).
Definition (Scalar denoising function). For x E B and > O,
n)(z, t) arg min wES
ww - x)==x)² 2 + F(w)) E
21
Since F(.) is strongly convex, this one-dimensional optimization has unique minimizer. Note that aw (w) = lim h(w, 1/0²) F oे =o, the minimum is never achieved on the boundary of S. Similarly, when S = R. lim dF (w) = to0. Therefore, the minimum is always achieved at stationary point. Lastly, (70, t) = 0 if is symmetric. In fact, throughout this paper, we only consider symmetric priors.
when S= 1- 1], since lim dF
Before stating our main result and its implications, we first introduce a two-dimensional optimization problem, which will play a central role our later discussion,
max min ((b,T) r) 620 720
(5)
b 0 ((b,T) = _/2 2
E min ( b -² bZw + FFF B) -) -O²F(B)
+ 6²
(6)
WES 27
where F-)) was defined in Definition 3 and the E is taken over (B, Z) ~ T* @ NN 1). In the next lemma, gather some additional characterizations of this min-mat problem.
Lemma 2. The max-mi in (5) is achieved at some (b', r*) E (0, oo) x (a, oo). In fact, b* is unique. In addition, (b",7") ,T") is also a solution to the following fixed point equation,
2
1
TO²
== 0² 2 -
17
TZ + B,
b
-B)
α
TZ + B, TO2
b )] =T
n/ 77 B, TO²
b ))
b=
E
2.1
E
where (z, 8y
dn (I.
Definition 6. We use y* = Vž.-. to denote the distribution of 1n T Z + B, =-2² (B, 7) ~ T" 8 (0, 1). We denote by the empirical distribution of ((ū;, 33 )
B). in which
We are ready to state our main result, which provides a sharp asymptotic characterization of D. Theorem 1. Suppose the max-min problem in (5) has unique optimizer (b*, TT)) or the fixed point
equation in ( has a unique solution (b+, 0,, =*). Then for all > O, as n., - co.
P (Wa (v" ,0, 26) + 0,
where W2(x.)) stands for order 2 Wasserstein distance.
5

---

Remark 1. This result indicates the NMF estimator â should be asymptotically roughly iid among different coordinates, which is different from the NMF distributions being product distributions.
Corollary Suppose the hidden true signal 3 was a priori sumpled iid from a probability distribution x' with finite second moment. Note that n' can differ from the prior that the Bayesian statistician chose. In addition, suppose the max-min problem in (5) has a unique optimizer (b*, ,T",, or the fixed point equation in 77) has unique solution (b", r"), then for all e > 0.
P W2 ()= 1423 - 00 as as 00.
in which v² was defined in Definition 6
We provide proof sketch in Section and all the detailed proof's are deferred to the Supplementary Materials.
2.3 Convexity of F(-)
In this section, we present a few lemmas that would ensure the validity Assumption 3 In fact, conditions of any of these lemmas are satisfied, Assumption holdd.
Lemma 3 (Condition ensure convexity of F()): nice prior). Suppose is absolutely continuous with respect to Lebesgue measure and
d dx
(x) xe e
- Vr E support(T),
for some V support(z) - TR. addition, suppose either of the following two conditions is true,
1. support(T)) R; (x) is continuously differentiable almost everywhere; ((x) is un- bounded above at infinity.
2. support(T)) = [-a, a), for some 0 < a < oo; ((r) is continuously differentiable almost everywhere.
Then if (x) is even, non-decreasing in |a] and V'(x) is convex, F(-) always strongly convex, regardless of the value of o²
Lemma 4 (Condition to ensure convexity of F(-): discrete prior). Suppose π is a symmetric discrete distribution supported on (,1,0,1}
<(xx = qo(x) + 1-9 --98(x 1)) +)+
1 1-9 -8x 1), 5(x
5(x
2
for q (2/3, 1). Then F()) is always strongly convex, regardless of the value of a
Proofs of Lemma and crucially utilize the Griffiths- Ceiffith-HHurs--Se HursttSherrmnn (GHS) inequality 5 which arose from the study of correlation structure in spin systems. The following two lemmas give examples of some other families of priors for which convexity of F-)) depends on the noise level o² while those in Lemma anddddoo not.
6
Lemma 5 (Condition to ensure convexity of F()): low signal nogise ratio). Suppose support(x) C (-a, a) for some > O. Then as long as o² > a², F(u) = F2 (u, o²), as functin of u, always strongly convex on S, regardless of the exact choice of π and value a².
Lemma 6 (Condition to ensure convexity of F(.): Spike and Slab prior). Consider spike and slab prior to the following form.
t (dx) = q0(x)= + 1-9 9
dæ
A
which is just mixture of a point mass and Normal distribution of mean O and variance 2 Suppose
min Varx (X)) o²
(8)

---

Approximation: log normallzing constant (celta alpha111
q-0.1)
0.725
WSP asproommationn
aigrosimation Limiing log
Lensting Bog
2.0
www.maarreeeeoo corplant
1.5
0.630
0.05
0.75
0.7 0.9
20
20
Figure These figures demonstrate the existence of gap between limp-rso (2p)/p and so (log 2/M when x² is Gaussian Spike and Slab distribution. The left panel features the observation that the gap gets smaller as (prior sparsity) increases, while the right panel shows a n/p gets large, the gap seems converge to 0, which is consistent with the results established in [16] when = o(n).
where n a is again a Gaussian spike and slab mixture,
1 - 227 da
T(xx) -](xx) +
2
A²A² x²
with i g a) /2/02--1/2
and
A
Then, Flu) is strongly convex. In addition, one easier-to-check sufficient condition for 8 is
2g (1+12
14 a2 2
1.
A
Remark 2. It is easy to see that for large enough (q and A fixed), or small enough (A and a fixed), or small enough & (q and fixed), (9) is always satisfied. other words, F(.) is strongly convex for low signal-to-non ratio or high temperature in physics parlance.
3 Log normalizing constant: sub-optimality of NMF
As alluded, as implications of Theorem we develop asymptotics of both log 2p ZNM and mean square error (MSE) of the NMF point estimator ú in terms of (b*,7*).
Corollary (MSE). When conditions of Corollary 7 hold, as n, + 0c,
- 1/11 _ E(B =( (T T²0² B
27
= =a -2))
Corollary (Log normalizing constant). When conditions of Corollary 0 hold, as n, + 0c.
P
P, ab+2 20 + +B
NMP log 2p
Mn(
c(0,
Though all our main theorems and corollaries apply the case when + for simplicity and clarity, from now on, we only consider the "nicest" setting, i.e, when assumptions of Corollary [ are satisfied and in addition
x². By doing so, we would like convey that even if there were no model mismatch at all, NMF still would not be "correct".
Concentration and limiting values of both the optimal Bayesian mean square error (i.e., E,11 E[3* |X, 2|]l 1 /p) and the actual nogmaazza constant were conjectured and rigorously established
7

---

Credible
Credibiee intervais generated by NMF Jelpha
0.34
Coverspe Rate
Covergge
0.90
0.025
0.3
0.4
0.803
0.4
0.2
0.73
Figure 3: These two figures show that estimated credible regions given by NMF do not achieve the nominal coverage (95%) when n² is Gaussian Spike and Slab distribution. Recall that n/p and please see Lemma 6 for exact definitions of the hyper-parameters and A
under additional regularity conditions, which provides the "correct answers" to compare with. Please see 12 20
Please see Figure for numerical evaluations of Corollary which suggests the bound in 44) is not tight for Gaussian Spike and Slab prior. Since, in general. both F(-) and 17(-;) lack analytical forms, it is hard to provide universal guarantee whether has unique optimizer or the fixed point equation
7 has a unique solution. In fact, our numerical experiments suggest it possible for (7) to have multiple fixed points. Therefore, how to exactly realize and evaluate the asymptotic predictions in these two corollaries (so as Corollary in the next section) challenging general and can only be done in a case-by-case basis and usually involves numerically solving (7) In light of this observation, we use the Gaussian Spike and Slab prior as defined Lemma for presentation purposes. Since it is both non-trivial and of practical interest, though, we do emphasize that the same framework and workflow also apply to other priors. Without loss of generality, we also take o² 1. This choice renders Figure 2 and in the next section. Details of how to generate these plots are deferred to the Supplementary Material.
Uncertainty quantification: the average coverage rate
To study uncertainty quantification properties of NMF approximation. consider the average cover- age rate of symmetric Bayesian credible regions (of level () suggested by the NMF distributions, i.e Rp.c = 1 Σ 1at c </al}, where d., the 1-th quantile of xt (.)a.) In order to study asymptotic behavior of Rp.c, we define an (m(T), M (=)) x S + {0, 13 indicator function
dbc (uo. 30) 1
BoE (=0))) .cra" c/2" (hiro. 1/=²2 1-///
The following corollary of Theorem establishes the asymptotic convergence Rp.c- Numerically evaluating it for the Gaussian Spike and Slab prior renders Figure 3 which shows NMF credible regions can not achieve the nominal coverage, in this case, 95%, and also provides an exhibition of how large the gaps are for different preeepparameters.
Corollary 4. Suppose conditions of Corollary DaairyyThoo holl. In addition, assume the quantile function of π continuous. Then as n. P > Do,
Rp P.
A' (T
T"O² b+ BBB :)
On the other hand, based on the asymptotic joint distribution of û and 3* stated in Corollary]] we can in fact identify strategy of constructing asymptotically exact Bayesian credible regions based on û. Let de (I:) be the (-th quantile of conditional distribution of B given r/(r* + B, T /b*) This way, the following Corollary ensures (n))),))))/(((5)))) is asymptotically of least 1 - coverage.

---

Corollary 5. Suppose conditions of Corollary 4 hold, then for any E >> 0,
P
lim P p-+00
(e < 51-5-8 0.
5 Discussion: Extensions and Limitations
In order to provide some intuition on why the NMF approximation is loose in the current setting, it is worth noting that in comparison with the proportional asymptoties regime we consider here, positive results of NMF for high-dimensional linear regression were recently established in [[6] when p o(n). Using terminology from Austin [I, Mukherjee and Sen [16] (when restricted to designs with iid Gaussian features) essentially proved. when p/n - O, the eigenvalue concentration behavior of X X leads to the Hamiltonian being of "low complexity". On the other hand, when p (n), tr( (r(A))= * o(p), where A = A(X) is defined as the off-diagonal part of x X, which violates [66] Equation (5)). Roughly speaking, when the eigenstructure of A is not "dominated" by few top eigenvalues, the Hamiltonian can not be covered by an efficient net and thus is not of "low for more details.
complexity", Please see [I [6 3
We want to be clear about the fact that, technically, we did not "prove" the sub-optimality of NMF. Instead, we rigorously derived asymptotic characterizations of NMF approximation through the solution of a fixed point equation. But this fixed point equation can only be solved numerically on case-by-card base basis and is not guaranteed unique solution. All our plots are based on iteratively solving the fixed point equation. As a matter of fact, for instance, when q is close to for the Gaussian Spike and Slab prior considered, the fixed point equation is clearly not converging to the right fixed point, as demonstrated in the Supplementary Material. It could also just not converge for very small a. Nevertheless, all the plots are showing in the main text are backed by numerical simulation using simple gradient descent to optimize the NMF objective, i.e. inf M, for n 8000. All in all, it is probably more accurate say provided tool for establishing the sub-optimality of NMF for a general class of priors rather than proving it for good.
Another obvious limitation is can only handle priors that guarantee convexity of the KL-divergence term in terms of the mean parameters. Though it is indeed a broad class of distributions covering some of the most commonly used symmetric priors (e.g., Gaussian, Laplace, and on), little is known about the asymptotic behavior of NMF when the convexity assumption is violated.
We note that, in theory, in order to carry out the analysis using CGMT, the additive noise as defined in ( does not have be Gaussian. Instead, as long as it has log-concave density, the same proof idea applies, though we intentionally chose to stick with Gaussian noise as it renders much cleaner results and a more comprehensive presentation. In addition, we expect stronger uniform convergence results (e.g., uniform in o²) could also be established, which can be crucial for applications like hyperparameters selection. Please see 15 for an example in which results of this flavor were obtained.
6 Proof strategy
This section gives a proof outline of Theorem More details can be found in the Supplementary Material. Replacing all d, 's in Mp with Ed, I/o2, we define Np as
u =
1
P
Np(n)= 20 y - Xull3
Glui, 1/03)
Y - Xull3 +
F
F(us).
20
20
Lemma 7. Let uN == arg min, (u)]. Then for some C2 E R as n.p + 00,
max (| |i C.)82
Lemma 8. For any > 0, as n, Do, with C. defined in Lemmal
7
P
u 2n
Glu;, di) duu?" 2
P
sup CL))/
Glu,, 1/02)
> +0 (10)
P [|l

---

According to Lemma 8 and 7 N.(.) and M₂(-) are with high probability uniformly close. Thus, from now on, we focus on using Gaussian comparison to analyze üN and (ūx))) in place of à and (,) Since F(.) is strongly convex, di == UN 3 is the unique minimizer of
2
L(w)= = 2n
Xw - cl12
(w: + (3) F())))
By introducing dual vector s, we get
o²
min L(w)= min max 8 (Xw c) WERP sER
||
(F(w; + (3) - F(3)))
2n
By CGMT (see for instance
22 Theorem 3.3.1] or 15 Theorem 5.1]). it suffices now to study
min max
|| + n2/2 1 h2 u s c n3/2
1
1
_ |||
σ²
(F(w, + [1) F(8)))
7
2n
where g (0) and h (O In) and they independent. Note that the min and max can be flipped due to convex-concavin By optimizing with respect to s/|| and introducing
1w1 +o
wil2 0² min
it can be further reduced
2r
0 7)
ba
1
}
max min 620
min
2T wi
bg + o2 P2 + 0² -
T2
at
WER"
1=1
Under minor regularity conditions, n,, + oc, it converges to
2/02 - -r)
6² 1 2
max min 620 72a 2
+ BB min WER
w2 - bzw + B)
2T
with (B, 2) ~ n* @ N(0, 1), which is how we got o(. -) as in (5). Furthermore, by differentiating ((b,7) 7) with respect to and b, we arrive at the fixed point equation in Lemma Last but not least, note that arg min 2 22 bZw F2F(W + B)} n) Z TO? 2 /b) B, which explains why the joint empirical distribution of (ı²;, 87) converges the law of (n)(=" Z B, Finally, we note that similar proof arguments were made in [15]
o² (2>//bb) B, B).
Acknowledgements
I am grateful Subhabrata Sen some very insightful conversations and encouragement throughout the process. Along with Subhabrata Sen and three anonymous referees, they also made valuable suggestions about earlier versions of this paper. The author was partially supported by a Harvard Dean's Competitive Fund Award to Subhabrata Sen and NSF DMS CAREER 2239234.
References
[1] T. Austin. The structure of low-complexity gibbs measures on product spaces. The Annals of Probability, 4766):4002-4023, 2019.
[2] Barbier, N. Macris, M. Dia, and Krzakala. Mutual information and optimality of approxi- mate masssag in random linear estimation. IEEE Transactions on Information Theory, 66(7):4270-436) 4303, 2020.
[3] A. Basak and S. Mukherjee. Universality of the mean meen-field for the potts model. Probability Theory and Related Fields, 168:557-6000 2017.
[4] D. M. Blei, A. Kucukelbir, and J. D. McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 112(518):859 877, 2017.
[5] R. S. Ellis and J. L.. Monroe. A simple proof of the ghs and further inequalities. Communications in Mathematical Physics, 41(1):33-38, 1975.
10

---

[6] R. S. Ellis, J. L. Monroe, and C. M. Newman. The ghs and other correlation inequalities for class of even ferromagnets. Communications Mathematical Physics, 46(2):167-182, 1976.
[7] B. Ghorbani, H. Javadi, and A. Montanari. An instability variational inference for topic models. In International conference machine learning, pages 2221-2231 PMLR, 2019.
[8] R. J. Giordano, T. Broderick, and M. I. Jordan. Linear response methods for accurate covariance estimates from mean field variational bayes. Advances in neural information processing systems, 28, 2015.
[9] Y. Gordon. Some inequalities for gaussian processes and applications. Israel Journal of Mathematics, 50:265-289, 1985.
[10] Hall, T. Pham, M. P. Wand, and S. S. Wang. Asymptotic normality and valid inference for gaussian variational approximation. 2011.
[11] Q. Han and Y. Shen. Universality of regularized regression estimators in high dimensions. arXiv preprint arXiv:2206.07936, 2022.
[12] A. Katsevich and P. Rigollet. On the approximation accuracy of gaussian variational inference. arXiv preprint arXiv:2301.02./66 2023.
[13] F. Krzakala, A. Manoel, E. W. Tramel, and L.. Zdeborová. Variational free energies for compressed sensing. In 2014 IEEE International Symposium on Information Theory, pages 1499-1503, JEEE, 2014.
[14] C. A. McGrory and D. Titterington. Variational approximations in bayesian model selection for finite mixture distributions. Computational Statistics & Data Analysis, 51(11):5352-536) 2007.
[15] L. Miolane and Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. The Annals of Statistics, 49(4):2313-2333 2021.
[16] S. Mukherjee and S. Sen. Variational inference in high-dimensional linear regression. arXiv preprint arXiv:2104.1223 12232, 2021.
[17] D. Pati, Bhattacharya, and Y. Yang. statistical optimality of variational bayes. In International Conference on Artificial Intelligence and Statistics, pages 1579-1588. PMLR, 2018.
[18] Qiu and S. Sen. The tap free energy for high high-dimensional linear regression. arXiv preprint arXiv:2203.077
2022.
[19] K. Ray, B. Szabó, and G. Clara. Spike and slab variational bayes for high dimensional logistic regression. Advances in Neural Information Processing Systems, 33:1 10111444443333 2020.
[20] G. Reeves and H. D. Pfister. The replica-symmetrie prediction for compressed sensing with gaussian matrices is exact. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 665-669. IEEE, 2016.
[21] M. Stojnic. 103 2013.
framework to characterize performance of lasso algorithms. arXiv preprint
[22] C. Thrampoulidis. Recovering structured signals in high dimensions via non-smooth convex optimization: Precise performance analysis. PhD thesis, California Institute of Technology, 2016.
[23] C. Thrampoulidis, Oymak, and Hassibi. Regularized linear regression: precise analysis of the estimation error. In Conference on Learning Theory, pages 1683-1700 PMLR, 2015.
[24] C. Thrampoulidis, E. Abbasi, and B. Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592 5628, 2018.
[25] v. Neumann. Zur theorie der gesellschaftssiele. Mathematische annalen, 100(1):295-320, 1928.

---

[26] R. Vershynin. Introduction to the non aanmmtttttiic analysis of random matrices. arXiv preprint 10X2 2010.
[27] M. J. Wainwright and M. I. Jordan. Graphical models, aaoomentillaamilnin and variational inference. Now Publishers Inc, 2008
[28] F. Zhang and C. Gao. Convergence rates of variational posterior distributions. 2020.
12

---

Supplementary Materials
A Technical lemmas and basic facts
(h, d) and ö(h, d) = 512 (h,, d). We have, for a E (m(()), and Lemma 9. Let o(h, d) = dh 2h
d E R,
0G Du (u,d) huu,d, d), Od
aG
=² dh (htu,d)), (z)
1
/ x² dr (z)
2 s
G² 82 (u,d) E(h(u, d)
1
Var (aituaia (X) > 0.
Lemma 10 (von Neumann's 's minimax theorem, (25)). Let Sw CR" and S. C Ih be compact conver sets. f S., S, R is continuous function that is conver-concave, i.e., f(,,8) S) S. IR is convex for fixed 8, and f(w, ) S, + R. is concave for fixed w. Then we have that
min max f(w, 5) max min f(w,s) s). weSw sES,
sE9. wESw
Theorem 2 (CGMT, 23 D.), Let S IPP and Sn C R" be two compact sets and let
Q Sw. x S. + IR be continuous function. Let G = (Ge))ssssnssssp std NN(0,)) -~ 1p). (0, In) be independent standard Gaussian vectors. Denote
(G) min max s" Gw Qw,,s)
weSw sES,
(g, h) = min max || |||g" w + || h² 8 s).
wESw sES,
Then we have
1. For all t E R.
P(O(G) <)) < (P( S)).
2. If both S., and S, are convex and ifQ(-)) is convex-concave, then for all E IR
P 2 < (g)
Remark 3. The most important message of this theorem is essentially whenever V (g, h) concentrates around certain value (G) will also concentrate around t, assuming Q(:,-) is convex-concave.
B Proofs
Proof of Lemma and can be found in for instance [16].
B.1 Convexity of F(-)
Proof of Lemmal We only prove part (1) here, proof of part (2) is almost exactly the same. For any h, d E 1R, by GHS inequality [6] Equation 1.4],
a Var th (B)
E 3EBE + + (EB) 3 GHS
0.
0h
Together with the assumption that V is even, we have for any h E R and 2 0,
Var (he (B) < Var (B).
Consider family of parametric distributions (Po 0 2 0} generalization of (0.dd) with
dæ dPa (a) x exp(-0V(x)) exp dx= /2)
13

---

Note that Pa=1= = T(0.4) Since (-) is even and increasing,
Ba (B) Varg-Pe-, (S) - Varg~Po-ol (5)
Jg 2 12dz SR e dz3 dz2112d
1 l 2²²--= 22/2222
d JR e ==22/222
1 d Vars-N(o.1)())==
which ensures Var 1, ( I o² and therefore d'F (w) 2 0 by Note that as du
long as is a valid probability distribution, F(-) is not only convex but always strongly convex, as Var B-rth(u 1/00t/ (B) = o² if and only if (+) is constant function and the support of x is the whole real line.
The same proof idea also applies to Lemma 4 therefore, we omit its proof to avoid redundancy.
Proof of Lemma
The conclusion follows by noting
d² F (u)
1
0 > 0,
(II)
du
Var Br (B)
as x (hi,)) is a distribution smaller than o².
[-a, al and thus its variance is most a², which is assumed to be
For Lemma 6 since Var VarBa (B) can be analytically computed for the Gaussian Spike and Slab prior, its proof is nothing but elementary calculation and then checking for (11)
B.2 Replacing de with Ed,
Proof of Lemma 7 We focus on only |ÍÍ|| since almost exactly the same argument also applies to ug. We first collect a few high-probability claims, proofs of which are just direct applications of basic standard random matrix results (see, for instance, (26)).
1. There exist positive constants C1 and C2 (only depend on a), such that for any S1 := {[Amax (X x) C1l < < and S2 == {[Amin (x x) - C2l < E} are both of high probability.
2. Recall the additive noise high probability.
NO o² I,). For any S. (11le|2/n= 0²1 < <&) is of
3. For any > 0, S1 =
= x < E} is of high probability.
Let So = S1 S n S3 n S1, which is again an event of approaching probability. Note that since the empirical distribution of 3t's converge in L2 to π². one has ||5+1 1.01psg for large enough p. When So happens, if ||/||3 /p > (1 + C2)82 (with C, >> to be chosen later, but large enough such that [|xu] uul > Y)))
1 Y - Xull² 2
1
(||xu) - 11 2 P [V[C, - =] C.)s2 - |X3 - cl1/p)
(u) 2
202
202
202
P
V(C² - =1 C.)s2 V 22( +5) 232 + 22(0² tc]
2
20
On the other hand,
N₂ 00) (0) - 1
1
p
[CGs) 2ps2 + 20(02-e0) +2]
20
Upon C. being large enough, we have N₂(x) Np Therefore, | < (1 + C2) on So.
0 for any such that ||ul/// > (1 + C.)82.
14

---

Proof of Lemma 8 If S 1-1, 11. by Lemma
@G(u.d) 3d
(u. du.d) - for any u, d. thus
P
u
d
LHS of 10
sup
G(uy, di)
G(u,, 1/09) )
Σ
20²
aG(u, d)
1 p
sup
Od (u,, 1/00//0 (do
+
Σ
d,
1/0
2
p
1
d;
Since Xjy's are iid with variance 1 1/n, know Rd, -
R
X3 X3
=
-, d; " प. and all
d; are rid, which guarantee RHS of the previous display goes to 0 in probability as n. + co. On the other hand, if S R. note that for any (0,0 P(maxısisp |d. 1/o"| 6) + as n, n, + co. In addition, when maxigisp |d; 1/o²/ I is true, which is of approaching 1 probability,
1. LHS of 10 S
P
u
d
G( G(ui, 1/0
Σ
sup vellul/
20
2
P (aG(u, d)
1 p
s
sup u: w:||u|l/><( C., C2)
(n, 1/0² 8,) - 1/02]
Σ
d4 1/02
Od
where 6, (min(0, d. 1/0²), max(0, dz 1/02)). By Lemma 9 it is further smaller than
1 di a²
Vaar Xhxx 1//2 (X) + u² Var x (X) ug
sup wellul//p<(+CCC)pp
Grre true, for d close enough to 1/0², we have Var xarxaa( (X) < 2o for any h E lR. Therefore, upon choosing small enough such that all di 's are close enough to 1/o², the display above is controlled by
Lastly, note that when conditions of one of Lemma 3 4 and 6
P
sup ///2
d
(4a² 2u²)
02|
|121|22
S max |d; - 1/021 15P5P
sup
402 +
p
<8. (4o² + (1 Cx)82)
Lastly, further requiring 8 < , renders Lemma 8
B.3 Regarding the fixed point equation
Proof of Lemma
2 First of all, recall the definition of o(. -) in (6).
de (b, r)
1 (02 - T E
[ B n(TZ + B, ro /b))² 2ra
0b
2a
Note that for any fixed
|x: (),, () is always strictly increasing with respect to I, we have
E
( + B
nnTZ + B, TO2 (r))/ 0,
ab
which further leads to
8
2he r) -1,
Vb,
Therefore, for any fixed r, ((,,) is 1-strongly concave. Define (b) = minz2a Φ(b,7). Since v(()) is the minimum of collection of 1-strongly concave functions, it is 1-strongly concave itself and
15

---

must have unique maximizer b* over [0, 20). In addition, by definition of 17, lime-+0o n12, t) = 0,
dominated convergence theorem gives
lim b-+0+
(TZ + B (TTZ B, Bo (TZ B) = 11
Therefore, for any fixed T,
d6 1 (b. r) (02//+ +
E
lim inf h-00
> 0.
0b
2Ta
Together with Lemma and continuity of ((.,)), it ensures b* * b > 0,
On the other hand, for any
(b, r) = 2T
b
r²
0² + --
B, (B,02+ 13) }
0r
0o
(b, = 0) < O. Or
Together with Lemma 11 we have minrza @(b", .) has at least one minimizer T" E (a, oo). Finally, de (b* +*) 26
since 6* and r" are not the boundary, we have
O, which gives rise to তr (b*, r*)
86
the fixed point equation as in
Lemma 11. Recall the definition of ó in 66. For any fixed E (0, oo).
lim o(b,T) cc. 10000
Therefore, min, o(b, T) admits at least one minimizer.
Proof. Since B[ 82 co, Emin { w² bZw + F2 B) F2F(BB] is decreas- ing in and always finite for any (b, E (0, 00) [o, 00). Therefore lim, (b, r) oc.
B.4 Proof of the main results
We devote this subsection to proving Theorem while we note Corollary 1 and are all direct consequences of it. We first prove Theorem while introducing some necessary lemmas. Then, we prove these lemmas at the end of this subsection. Whenever the optimization domains for w and s omitted throughout this subsection, they are understood to be IR' and IR"", respectively. We use to denote empirical distribution in general.
Since F.)) is strongly convex, ú == UN
8* is the unique minimizer of
L(w)= = X el12
(F(w; + (1) - F(3)))
2n
By introducing dual vector we get
1 J (Xw - c)
1
σ²
min L(w)= min max WERP sER" n
s
F(w;; + -3) - F(2))) == min max $ x (w. 8)
2n
n
1=1
Following the recipe in Theorem 2 we define
1
σ² F (F(w; + Bt) - F(3)))
I () = 33/2 || w 33/2
|
1h
8
-8
S
E 2n
||
2
n
n
(12)
where g NOO Ip) and h ~ (O, and they are independent. Note that with a deliberate abuse of notations, use de and V to denote these two functions to indicate their resemblance to those in the statement of Theorem 2 By Theorem 2 it suffices now to study min max, V g (w, s) in place of min,, max, &. (w, s), which is made rigorous by the following lemma.
Lemma 12. Let D be any close set.
16

---

1. We have for all t E R
min max & x 8) St - 2P
min max U (n)(w,s) s1
WED
wED
2. If D is in addition conver, then we have all t
min max 2x (w, 8) 2 21) S 2P WED
min max (n,((w,))
WED
We defer the proof of Lemma 12 to the end of this section and proceed with proving Theorem Due to strong convexity, ti arg min max, g. (w,, 8) always exists and is unique. Note that the min and max can be flipped due to convex-concavity (Lemma TOp. By optimizing with respect to s/ |||||| and introducing
1 n
||||2
+ 0²
min =2
+
(13)
2r
min max, gon (w., 8) can be further reduced to
max min 9.a (b, 620 72a
(b, 7) = b 2
12
D
}
- +T)
min
wt
bg,ws + + F2F + B1) o² F2
2
a
WER
in the sense that (i) the optimizers dh and ur close, i.e for any x: 0,
( wr 12 xi 0,
(14)
and (ii) the optimum value is preserved with arbitrarily small error with high probability. The next lemma ensures empirical distribution of (wv, B*) is close to the distribution of
(n + +, "²- - -B,B). which we denote as V(mn,, where (B, Z) ~ T' & 1).
Lemma 13, Suppose all conditions of Thhorre 7 are satisfied. For any & > 0, there exists C(e) E
(0,e) such that p, oc,
P 3i IR such that Wz (U(a,or))
V ((wr..r)) and max V (1, 8) < min max V ga 8) C(6) - 0.
In the meantime,
ab+2
min max V Vo, 8) B 202 BF
Again, for now, we proceed assuming Lemma 13 and prove it later at the end of this sec- tion. Building upon Lemma 12 and Lemma 13 we now prove the empirical distribution of (*) (3* + B*) is close to v" as defined in Definition 6 For > 0, define Dr
10 E RP W2 (Die,3r), (w (w)))) )² 2 28
To establish
(W2(P(e,s)) "i m2)) >)) + 0,
it suffices to show with high probability, for some 8(E) > 0,
min max & (w, s) min max Tb (w s) 5(E).
(15)
wED,
wERe
On the one hand, by applying both (1) and (2) of Lemma 12
IR,, together with Lemmal
13
we have
ad.2
lim min max &x (w, lim min max (w, p0
(B
000
20²
17

---

where the "lim" is understood to be convergence in probability. It further leads to
P
min max 4 (w, 8) min max V yg (w, s) > $) +
On the other hand, applying (1) of Lemma 12 to D Ds. together with Lemma 13
we have
P
min max (x s) min max d (wc + C(=) ++) 0, weD.
which establishes 11 with 8(e) - C(e) + E. where C(e) > was defined in Lemma 13
Therefore,
have the empirical distribution of (uN, 8*) is close the target distribution v/", i.e.,
W2(P(un B1), v*) & 0.
(16)
Finally, according Lemma 8 and Np(-) and Mp(+) are with high probability uniformly close. Together with strong convexity N ), we have for any K > 0
uNl1 K 0.
(17)
Theorem therefore given by
16 and 17
Proof of Lemmaa 12, In order to prove Lemma 12 using Theorem 2 only needs establish that
the optimizer of x (w, s) always has a bounded norm with high probability, In fact, Lemma 7nnsures boundedness of ④ arg min, max, 1x(w; s) while the boundedness of 5 arg max, 2x (t) s) can be established by similar argument.
Proof of Lemmal
13
Define
b 0²
12
P
[ 2T w
i (b, 7)
+T)
bgaw; + FF + Bt) - - -0
2
a wEDe
By definition, T' (b, (b, for any (b, r) deterministically. Recall the definition of og (+)
in (2).
min max V a. (w, wED,
|
σ²
P n
min max wED, [ell 33/2
|s||g" T w +
||||||
||
(F(w + B3) - F(3)))
Vn
2n
f=1
1=1 min max wED. 620
|w
b²
σ²
P
bg T
w + by
+
+
(F + B,) - F((3)) (+)-)((3)))
+ (
n2
12
2
n1
b
22
62
9
[
b
bg,w; + 0²F(wn; + +3) 1 -8))-2F((33) 02F(83) }| + 0
min max min
7)
+
wED, 620 220
2
7
2r
Lemmnl 10
max min i 9.th 9.h (b, 7) + on(
620 T20
Therefore,
min max V (w, max min min F (b, 7) + (1) wED,
820 r20
min i ( + 0, (1)
r2o
(b, =(bb)) (1)
(b ((b²)) + (1)
(18)
(0)
2 min I 9.hh (b*, T) + o (1)
?20
-o,,(b", r*) + on,
min max v n.h (w, 8) + (1),
weB
18

---

where F(b*) arg min,20 9. (b", ( r). We claim that the gaps resulting from (i) and (ii) can not be both negligible. Namely, there exists e > such that
suppup P (Ti T2 > e)> 0, a.p
(19)
where
Ti = I an (b", ((b)) - (,,n(b,F((b")) 2 0,
T2 I n (b", =(b")) mbb ,7* 22.
In order to establish (19). we will proceed with proof by contradiction. Suppose 19 NOT true, equivalently, for any 0,
lim PP ( 0) = 0,
(20)
n.p-000
lim (P 2) = 0.
(21)
Recall the definition of (6-) in ( Since (b", is the unique optimizer of ob.)) and T 9.n (b, 7) converges to <bb,T) uniformly on any compact subset of (0) x (0, (2T) is only possible [=(b²) - - 3 as n. p + co. the other hand, by definition De there exists 7 > such that with high probability, for any w E De.
b* b" g:w; + o² F(w B3) - o² r)(88))) }
Σ
2T w
Σ
b* 1
क - 9. + + of FFF(33)) +
where W; is sampled independently from the distribution of n (T' 53 r' 8: with Z /( 1). Therefore, with high probability,
Tb" - g.",
By triangle inequality,
Ti 2 Fan(U -Faxnt,)))-Fa00 (bn (T) - F Fan (((²)) - (b"
T f(b*)) (
In addition, note that if [F(b)) - =+1 1 as n, oo, then
- (bgh r-) B and (b,, "b, o.
Putting them together, we have
P > 75/2) + 1.
The display above is in contradiction to 20 which means Finally, note that Lemma 13 equivalent to
19 is thus established.
P
min max V o (w, wED,
min max V , (w, ((E) + 1 WER
and it therefore direct consequence of and
C Numerical simulations
All source code can be found in separate zip file in the Supplementary Materials.
19

---

indern tie ceuiti deigg
meny more conaatio seigg
232
3.15
0.23
0.20
6/8 DUAGCE EHAROO
36
320
0.2
04
Figure 4: iid Gaussian design versus iid Laplace design (with Gaussian spike and slab prior): These three plots showcase the empirical observation that prediction of Corollary seem to be valid for a design matrix with iid entries that have sub-exponential tails.
C.1 Universality: non-Gaussian design matrix
Instead of assuming Xij aid (O0 1/n), we now present empirical evidence of universality, i.e., Theorem holds for a broader class of design matrix that has rid entries with variance 1/n. Since is impossible to exhaust all possible distributions, we will stick with a representative example Xij did Laplace(v2/2)) and the Gaussian spike and slab prior. We use Gradient Decent to optimize (n( and then demonstrate that the empirical MSE of its optimizer coincides with the prediction of Corollary Please see Figure 4 for a visual summary.
For more comprehensive and rigorous results on the universality of Gaussian comparison incqualities, we refer interested readers to and references within.
C.2 Fixed point equation
0.4,
NPC: DG Theory Prodiction
08-
NPP: ortddirttteeee Decent bi cujn
Pricr Ver ence
Diyca Optimal
(PE
36-
Figure 5: As we can see, when g is large (g = 0.8 0.9 in the figure above), our initialization did not lead to the right fixed point.
As alluded to in the main text, all our plots are generated by iteratively solving the fixed point equation 7). However, this naive strategy might not give the right fixed point, i.e., the (b*, r*) that minimizes obb, r). or it could just do not converge. Please see Figure 5 for an empirical example. Since either F(-) or n)(:-)) lacks analytical forms for most natural priors, unlike other applications of CGMT (e.g., asymptotic analysis of lasso (15).. it is hard to determine whether ( has a unique solution analytically. Fortunately, there are two possible remedies. First, which is the option took, one could solve min, Mn(u) for some large n and check if the empirical MSE matches the prediction given by the fixed point. Alternatively, one could adapt a more brute-force way to find the actual optimizer of max, min, @(b, r). c.g., grid search or iteratively solving (7) with multiple initializations. After all, it only a two-dimensional scalar optimization problem. We followed the first way simply because we wanted to use empirical simulations to corroborate our theoretical predictions anyway.
20


Reviews:
[{"review_id": "ZHcM6rgg0I", "reviewer": "Reviewer_zux4", "summary": "This paper studies the naive mean field approximation (NMF) in high dimensional linear regression in the limit where p/n goes to a constant. While the NMF is known to be consistent when n >>p, the authors show that in the high-dimensional case, this is not true. As a result, this paper gives nice theoretic evidence for empirical observations showing that the NMF is no longer accurate in high dimensional regimes.  Moreover, the paper also discusses the consequences on the uncertainty quantification. \n\n", "questions": "I am currently missing an intuition in the paper for why the NMF approximation is loose in the high dimensional limit. Can the authors elaborate more on this point?\n\nTo me, the main intuition arises from the fact that when $n>>p$, the eigenvalues of $1/n X'X$ concentrate around $1$, which is clearly not the case when $p/n \\to c$. As a result, when $n>>p$, the measure $\\mu$ is approximately symmetric around its mode (and thus a NMF approximation should be accurate). On the other hand, when $p/n \\to c$, the measure $\\mu$ is \"elliptic\" and strongly depends on the small eigenvectors of $X'X$. However, these eigenvectors cannot be captured by the NMF approximation. \n", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The research question is important and the results should definitely be published at a top ML conference.\n\nThe paper is well-written and easily understandable.  The proof sketch is clear and the theoretical results are nicely illustrated with figures.", "weaknesses": "While I recognize that this paper meets the standards for NeurIPS, my reluctance in awarding a higher grade stems from two significant limitations:\n\n1) The proofs' methodological contribution is rather limited. Despite the elegant use of the CGMT, which is commonly seen within the high-dimensional statistics literature, the paper doesn't break new ground in terms of methodology. Although the paper commendably presents the proof in a digestible manner, and the choice of the CGMT is likely the most efficient way to prove the result, this doesn't warrant a significant methodological contribution deserving of a high grade (8+).\n\n2) The insights gained from the results are fairly limited and expected. This is also generally a shortcoming of proofs relying on the CGMT. While such proofs usually yield the precise  asymptotic limit, the resulting theorem statements  are challenging to interpret.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review and insights. We concur with most of the assessments and find the comments helpful. CGMT as a methodology has indeed been applied in past works, as cited. However, it is noteworthy to highlight that, to the best of our knowledge, it has been exclusively applied to the study of frequentist estimators, while we focus on the possibility of using this machinery to analyze Bayesian methods. We acknowledge the challenges the reviewer pointed out regarding the interpretation of our main theorem, though we hope the numerical approach toward the low-dimensional fixed point equation could alleviate this to some extent.\n\nWe concur with the reviewer's intuition regarding why the NMF approximation is loose in the high-dimensional limit. Alternatively, using terminology from (Austin, 2019, \"The Structure of Low-Complexity Gibbs Measures on Product Spaces\"), when $n/p \\to c$, the spectrum behavior of $X^T X$ results in the Hamiltonian no longer being of low complexity, which would further result in the NMF being loose in terms of the log partition function approximation."}, {"review_id": "3mATXPbhCN", "reviewer": "Reviewer_6Ztj", "summary": "This paper studies the Naive Mean-Field Approximation (NMF) for the posterior distribution of a simple linear regression problem with Gaussian design. It provides an exact asymptotic result for the joint distribution between the NMF approximation $\\hat u$ and the regression vector $\\beta^\\star$. This asymptotic is then used to provide results on the log-partition function associated to the NMF, the mean square error between the NMF estimator and the ground truth, as well as the associated confidence intervals around $\\beta^\\star$. Those asymptotics depend on a two-dimensional fixed-point equation, which can only be numerically solved; nevertheless, the authors compare this numerical solution with the full posterior distribution, to quantify how the NMF approximates specific quantities of interest of the posterior.", "questions": "- How well do you expect the conditions of Theorem 1 to hold ? I read your Appendix C, so I understand why it would be complicated, but do you have at least a few examples of unicity ?\n- What's the use of Corollary 1 ? Isn't it strictly weaker than the conditions in l.120-124 ?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is an interesting contribution to the study of Naive Mean-Field estimators. It complements well the results of Sen and Mukherjee on the data-rich setting, by showing that the NMF approximation is not even correct to the first order in the proportional regime. The methods used are fairly standard in the field of exact asymptotics, which is acknowledged in the paper, but they are applied to obtain relevant insights on a new problem. As far as I checked, these methods are applied rigorously and the paper is correct.\n\n", "weaknesses": "Some of the exposition feels however a bit too obscure: it feels like some very important points (e.g. the definition of the NMF objective and its explanation, or the main theorem) are drowned in very technical considerations (e.g. almost a full page of conditions to ensure the convexity of $F$, or the computation part of the CGMT). I think the paper could achieve a better balance between technical content and explanation, to reach communities that may be familiar with either exact asymptotics or Bayesian approximations, but not both.\n\nSome explanations that would maybe need to be highlighted include:\n- why you can replace (3) by the objective in Definition 2, and why you need the $\\frac{d_i}2\\beta_i^2$ correction term for,\n- how the CGMT also imply that the minimizers for both objectives are close (i.e. the part below Lemma 13)\n\nMinor remarks:\n- l.38: unfinished sentence ?\n- Eq. (3): $\\sum_{i=1^p}$\n- your log-normalizing constants are sometimes denoted with $Z$ (e.g. eq (2), (4)) and sometimes with $\\mathcal{Z}$ (most of the time)\n- contrary to what is claimed l.203-207, the expressions for $\\mathcal Z_p$ and related quantities are absent from the Supplementary Material\n- Eq. (9): I'm not sure redefining $F$ here is necessary\n- Fig. 5: there is no right panel", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer very much for the review.\n\nWe appreciate the comments on the general organization of our manuscript. In light of these comments and suggestions from other reviewers, we plan to create a subsection (Section 2.1) devoted exclusively to notations and assumptions, which will be stated in special environments of assumptions instead of being embedded within the text. In addition, we will also move Lemma 2-5 to Section 2.3, hoping to avoid burying the main results among these convexity conditions and appeal to a broader audience.\n\nReplacing (3) with the objective in Definition 2 is made possible by observing that after removing the $d_i \\beta_i^2 /2 $ terms, the first term in (3) is a function of $u:= \\mathbb{E}_Q \\beta$ only and the KL-divergence term in (3) is minimized when $Q_i$ is an exponential tilt of $\\pi_i$ (with the constraint that expectation under $Q_i$ is $u_i$).\n\nWe concur that the explanations below Lemma 13 can be further improved. The main idea is that Lemma 13, together with applying Lemma 12 part 1 to $ D=D_{\\epsilon}$ implies that when $ w $ is within $ D_{\\epsilon} $, the optimization can not achieve the optimal value, i.e., the last display on page 16. To further address this concern, we plan to reorganize the part after Lemma 13 (till the end of Appendix B) into formal proof environments instead of floating texts.\n\nThank you very much for the typos you pointed out in 'minor remarks.' We regret these oversights and will correct them. In particular, a statement of Theorem 3.2 in Barbier et al. (2020) should be added to the appendix. We apologize for the misleading description regarding Fig. 5. There is indeed no right panel there. Instead, we will amend the text in Section C.2 to highlight that \"the iterative algorithm might not converge for small $\\alpha$.\"\n\nAnswers to questions:\n\n1. Q: How well do you expect the conditions of Theorem 1 to hold? I read your Appendix C, so I understand why it would be complicated, but do you have at least a few examples of unicity?\n  - A: It is indeed complicated. One example we have in mind is when $\\sigma$ is sufficiently large, i.e., the Signal to Noise ratio is very small. This condition essentially corresponds to the ``high temperature'' regime in statistical physics parlance. Though we understand that this setting is not necessarily of great statistical interest, we believe it is nice to have at least some examples.\n\n2. Q: What's the use of Corollary 1? Isn't it strictly weaker than the conditions in l.120-124? \n  - A: While Corollary 1 is technically weaker than the conditions in L.120-124, we believe it might interest some readers. We emphasize here that our setup indeed covers the most natural well-specified setting."}, {"review_id": "PvKKBzES7J", "reviewer": "Reviewer_Qw44", "summary": "The authors provide an asymptotic characterization of naive mean field (NMF) for linear regression under certain priors (e.g., those which guarantee strong convexity).  Under these priors, this characterization can be used to demonstrate the sub-optimality of NMF (asymptotically).\n\nThis is primarily a theoretical work, but some experimental observations of the fixed-point scheme are provided.", "questions": "- Could you provide examples of possible practical applications of this work?  The approach seems novel and interesting to me, but I can't ever recall using NMF and thinking that it would yield a highly accurate answer.\n\n- Could you comment on the conditions in Theorem 1 -- are these likely to be true in many instances?  Let's suppose that neither condition is satisfied, is it possible to conclude anything from the fixed point iteration?\n\n\nMinor typos:\n- \"i.e.\" and \"e.g.\" must always be followed by commas.\n- \"using product\" -> \"using a product\"\n- \"when feature\" -> \"when the feature\"\n-  \"progresses were\" -> \"progress was\"\n- Stylistically, it is better not to use a citation as a noun.  You should use So and so et al. [citation] instead.\n... too many more to log here.  Serious proofreading is recommended, and please, please, please remove the phrase \"not gonna be correct.\"\n", "limitations": "Yes, the authors clearly describe the limitations of the current work, which could suggest interesting avenues for future research.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The approach seems novel and fills gaps in the existing literature.  \n\nThe high-level ideas were easy to follow (though I didn't check all of the proofs in detail).\n\nThe authors suggest lots of limitations which may lead to further investigation.", "weaknesses": "It isn't immediately clear what practical utility this work would have.  This isn't necessarily required in a theoretical work, but it would bolster the case for acceptance.\n\nAlthough the main ideas were novel (to me at least), the conditions required to draw the conclusions are difficult to assess (see questions below).  \n\nThe writing needs a lot of work.  Some notation is undefined (though I could guess what it meant).  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the thorough review and constructive suggestions.\n\nWe sincerely apologize for language and stylistic issues and will address them in the revised manuscript. We will try our best to learn our lesson and improve our writing skills to mitigate the impacts of language barriers. To further clarify our presentation, we will introduce a subsection (Section 2.1) dedicated to notations and assumptions and relocate Lemma 2-5 to Section 2.3.\n\nAnswers to questions:\n\n1. Q: Could you provide examples of possible practical applications of this work? The approach seems novel and interesting to me, but I can't ever recall using NMF and thinking that it would yield a highly accurate answer.\n  - A: We would like to gently highlight how our work offers practical insights. Generally, in high dimensions, people have recently started understanding that NMF can be very misleading (see, for instance, Ghorbani, Javadi, and Montanari, 2019); on the other hand, other works (e.g., Mukherjee and Sen, 2022) suggest NMF could be accurate to the leading order in some cases depending on the dimensionality. Therefore, there is this tension that we need to understand precisely - when it works and when it does not work at all. Even if it works, how much sub-optimal is it compared to the information-theoretic optimum? Our paper fills in some gaps here and critically explores this model. We agree that we never expect NMF to yield a highly accurate answer in practice. However, our work (1) confirms that NMF is at least not entirely misleading in this setting (high-dimensional linear regression), in contrast with the topic model where NMF is just completely wrong; (2) characterizes the degree to which NMF is sub-optimal, beyond \"yes it is sub-optimal.\" We also hope some of the insights we developed and the technical tools we highlighted in this paper can contribute to analyzing NMF in other more realistic models of higher practical relevance moving forward.\n\n2. Q: Could you comment on the conditions in Theorem 1 -- are these likely to be true in many instances? Let's suppose that neither condition is satisfied, is it possible to conclude anything from the fixed point iteration?\n  - A: According to physics intuition, as long as one knows what the 'right' fixed point is, then Theorem 1 should still hold. However, we do not have a rigorous proof for this point, so we did not mention it in the manuscript. In addition, we acknowledge the conditions in Theorem 1 are not super straightforward to access. Hopefully, the numerical approach toward the low-dimensional fixed point equation could alleviate it somewhat."}, {"review_id": "26QlLUGZlI", "reviewer": "Reviewer_JMXP", "summary": "This paper derives precise asymptotic characterization for the naive mean field approximation in high-dimensional linear regression under the proportional limit. Two concrete corollaries are obtained including the inaccuracy of the NMF approximation for the log-normalizing constant and the overconfidence of the NMF approximation in terms of uncertainty quantification.", "questions": "1. In line 28, why the map $M_p(u)$ has to be defined over $[-1,1]^p$? It is a bit weird to me because $u=\\mathbb{E}[\\beta]$ but $\\beta$ can be outside the interval.\n\n2. The authors indeed adopt the parametrization based on exponential tilts $\\pi^{(h(u,d),d)}$ on the basis of NMF. Does $\\pi^{(h(u,d),d)}$ conceptually cover all candidates of continuous distributions? If not, is it the standard setup to facilitate analysis in variational inference?", "limitations": "See the weakness stated above.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "1. The naive mean field approximation, the problem studied in the paper, is widely used in modern machine learning. The paper contributes  to understanding the utility of NMF.\n\n2. The paper is mathematically solid and all the technicalities are precisely presented. The proof techniques utilized are quite novel in the area of variational inference.\n", "weaknesses": "I do not find any major weakness of the paper but there are some presentation issues that can be possibly improved. Since the paper is overall very technical and mathematical, I suggest the reviewers to setup a table or a subsection exclusively for all notations. Also, I suggest to considering to formalize conditions utilized throughout the paper such as Gaussian features, noises with special environments of assumptions instead of stating them within texts. The current presentation is a bit challenging for me to follow. Also, there are some typos that need to be fixed. For example, in line 78. I think the definition should be $G(u,d):=D_{KL}(\\pi^{(h(u,d),d)}\\Vert\\pi^{(0,d)})=\\cdots$; in line 129, the right most term should be $G(u,\\frac{1}{\\sigma^2})-\\frac{u^2}{2\\sigma^2}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your detailed review of our manuscript and will revise our draft based on your valuable feedback.\n\nRegarding presentation,\n\n1. To enhance clarity, we will create a subsection (Section 2.1) devoted exclusively to notations and assumptions, such as Gaussian features, which shall be stated in special environments of assumptions instead of within the text. In addition, we will also move Lemma 2-5 to Section 2.3 to avoid burying the main results in these convexity conditions.\n\n2. We thank the reviewer for pointing out some of the typos. We regret these oversights and will correct them in the revised manuscript.\n\nAnswers to questions:\n\n1. Q: In line 28, why the map $M_p(u)$ has to be defined over $[-1,1]^p$? It is a bit weird to me because $u=\\mathbb{E}[\\beta]$ but $\\beta$ can be outside the interval.\n  - A: The correct domain should be $[m(\\pi), M(\\pi)]$ instead of $[-1,1]$. We thank the reviewer for bringing this to our attention.\n\n2. Q: The authors indeed adopt the parametrization based on exponential tilts $\\pi^{(h(u, d), d)}$ on the basis of NMF. Does $\\pi^{(h(u, d), d)}$ conceptually cover all candidates of continuous distributions? If not, is it the standard setup to facilitate analysis in variational inference?\n  - A: The answer is complex. On the one hand, yes, the exponential tilts are the best choices for minimizing KL divergence between the true posterior and the NMF distribution. On the other hand, if the NMF family was pre-specified, then it might not be covered by the exponential tilts. For example, it is not uncommon for practitioners to fit a Gaussian NMF when the prior is not Gaussian. To summarize, while exponential tilts conceptually may not encompass all candidates of continuous distributions, they include the \"best choices.\" Lastly, we believe it is indeed the standard setup to facilitate analysis in high dimensional variational inference, as illustrated in (Mukherjee and Sen, 2022)."}]

Author rebuttal:
We thank the Area Chair and the referees for the thoughtful reviews of our paper. We have carefully considered all the comments and will revise the manuscript accordingly.

In light of the reviewers' comments on the general presentation of our manuscript, we plan to:

1. Create a subsection (Section 2.1) devoted exclusively to notations and assumptions, such as Gaussian features, which shall be stated in special environments of assumptions instead of within the text.

2. We will move Lemma 2-5 to Section 2.3 to avoid burying the main results in these convexity conditions.

3. We will reorganize the part after Lemma 13 (till the end of Appendix B) into formal proof environments instead of floating texts to enhance clarity.

Apart from factual questions, which we have responded to in replies to individual reviewers, the reviewers' questions mostly focus on (1) the interpretability of our main theorem and (2) the practical impacts of our work.

Regarding (1), we acknowledge the challenges the reviewers pointed out regarding the interpretation of our main theorem, though we hope the numerical approach toward the low-dimensional fixed point equation could alleviate this to some extent. In addition, since it is hard to give very general conditions for assumptions of Theorem 1 to hold, we would like to advise the practitioners to take a more case-by-case approach, no matter if it is numerical evaluation of the low-dimensional fixed point equation or analytical approaches based on specific forms of the function $F$. 

Regarding (2), though we agree that we never expect NMF to yield a "highly" accurate answer in practice, there is this tension that we need to understand precisely - when it works (to some degree) and when it does not work at all. Even if it works, how much sub-optimal is it compared to the information-theoretic optimum? Our paper fills in some gaps here and critically explores this question for the proportional high dimensional linear regression model. For more details, please see our response to Question 1 from Reviewer 3 (Qw44).

Finally, we would like to thank all the reviewers for pointing out some of the typos in our manuscript. 

Meta-review: This paper studies proportional asymptotics of the naive mean field approximation in high-dimensional linear models with Gaussian data. Variational inference and high-dimensional asymptotics are certainly key topics of interest in modern statistics and ML. Although their analysis has some clear technical limitations, these are stated explicitly in the work and overall the contribution was appreciated by the reviewers. The authors have also promised some improvements to the exposition after the discussion. Based on this, I recommend acceptance.
Decision: Accept (poster)