Learning a 1-layer conditional generative model in total variation
Authors: Ajil Jalal
Justin Kang
Ananya Uppal
Kannan Ramchandran
Eric Price
Venue: NeurIPS 2023 poster (2023)
Keywords: Generative models
distribution learning
maximum likelihood estimation
TL;DR: We prove that MLE can learn deep generative models layer-by-layer using a near-linear number of samples

Abstract: A conditional generative model is a method for sampling from a conditional distribution $p(y \mid x)$.  For example, one may want to sample an image of a cat given the label ``cat''.  A feed-forward conditional generative model is a function $g(x, z)$ that takes the input $x$ and a random seed $z$, and outputs a sample $y$ from $p(y \mid x)$.  Ideally the distribution of outputs $(x, g(x, z))$ would be close in total variation to the ideal distribution $(x, y)$.

Generalization bounds for other learning models require assumptions on the distribution of $x$, even in simple settings like linear regression with Gaussian noise. We show these assumptions are unnecessary in our model, for both linear regression and single-layer ReLU networks.  Given samples $(x, y)$, we show how to learn a 1-layer ReLU conditional generative model in total variation. As our result has no assumption on the distribution of inputs $x$, if we are given access to the internal activations of a deep generative model, we can compose our 1-layer guarantee to progressively learn the deep model using a near-linear number of samples.

Learning a 1-layer conditional generative model in total variation
Ajil Jalal
Justin Kang
Ananya Uppal UT Austin ananya. upwpaaapppp11@@m.l.......m... com
UC Berkeley
[ajiljalal, justin waw.einnllenbeereeeeeee...e.
Kannan Ramchandran
Eric Price UT Austin ecprice8cs utexas.
UC Berkeley kannanr@eecs. ber.aarreeees...bbeeeeeee bew.eley. edu
Abstract
A conditional generative model is a method for sampling from a conditional distribution p(y v). For example, one may want to sample an image a cat given the label "cat". A feed-forward conditional generative model is a function g z) that takes the input x and a random seed z, and outputs a sample from p(y x)) Ideally the distribution of outputs (I, gxx, would be close in total variation the ideal distribution (z,y).
Generalization bounds for other learning models require assumptions on the distri- bution of ær, in simple settings like linear regression with Gaussian noise. We show these assumptions are unnecessary in our model, for both linear regression and single-layer ReLU networks. Given samples (x. y), show how to learn I-layer ReLU conditional generative model in total variation. As our result has no assumption the distribution of inputs if are given access the internal activations of a deep generative model, we can compose our I-layer guarantee to progressively learn the deep model using near-linear number of samples.
Introduction
Generative models are the midst of an explosion in accessibility, as models like DALL-E [31] or Stable Diffusion [32] capture the attention of millions. In many cases, these generative models can be succinctly represented by fundamental mathematical object-the conditional distribution p(y z)) In the example of text-to-image generative models, æ can represent text prompt its Word2Vec embedding [26], and the model can be seen as sampling an image y from its conditional distribution p(y 1²). With large numbers of people accessing these models, a massive amount of sample pairs (1s, 2.), are becoming available online. A natural question to ask is: How many samples (ys, 2;) does take learn the conditional generative model ply a:)?
Recent empirical studies such as Stanford Alpaca [34], which attempt to learn GPT-3.5 from limited samples, indicate that the number of samples needed may be within practical range. In this paper, we attempt to address this problem from fundamental perspective grounded in a concept from classical theoretical statistics: the Maximum Likelihood Estimator (MLE). Specifically, we focus on feed-forward generative models from a relatively simple family and ask: with no assumptions on how many samples are required efficiently learn the conditional generative model p(y x))
Linear Regression. Consider ordinary linear regression with Gaussian noise: you observe indepen- dent samples (I:; y/) R x TR of the form
+1
for y N(0, 1).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

p
311
y2
samples
W22
W3
"Beautiful sunset in New Orleans"
1/4
Noise
Noise
Figure I: A conditional distribution defined by conditional generative model. To sample from the conditional distribution p(y z), we perform inference. Due the stochastic nature of the model, each output is different.
How many samples does it take to get a "good" solution? For standard metrics-sudd parameter distance or prediction error on y y-the sample complexity of linear regression depends on properties of the distribution (such as the conditioning of the variance of that could be unbounded and cannot tested. For example, in the classic analysis (see [7], Chapter 3), sample complexity depends on the design matrix, which in turn results in dependence the expectation of ||>|||- The typical approach to deal with this would require bounded moments for æ. For learning the conditional distribution, the more natural metric is total variation
(TV) distance: the parameters w induce a distribution pw (I. y) = p(z Pu x) where p(z) is the true distribution of æ, and we would like to find t such that
drv (p (x, pa (I. v)) S.
This ensures that when the input model generates a conditional sample that is close in TV to the true model. turns out that this goal,
from the user in the true unknown distribution p(x), the unlike parameter distance, be solved with assumption the distribution.
Theorem 1.1 (Informal version of Theorem 4.1). The MLE (i.e., least squares regression) achieves (1) with ( log samples, regardless of the distribution of x.
To our knowledge, all previous guarantees for linear regression either require some assumptions give guarantees in terms of, the distribution of y. We avoid this dependence on the distribution by adopting a similar analysis to Theorem 11.2 in [20].
Main Result: 1-Layer Networks. Modern feed-forward conditional generative models (e.g.,
StyleGAN2) are more complicated than linear regression. They are stochastic neural networks with layers of the form:
y <(W">>
for (00~~N0,,E)
(2)
for r E R E Rd, o(x) = max(z, 0) is the ReLU activation, and some weights W Bdxk
Σ" E Rdxd
We show that 1 1-layer generative models of the form (2) can also be estimated using the MLE (which concave), with small TV error and without any assumption on x.
Theorem 1.2 (Informal version of Theorem 4.5), Suppose y is drawn according (2) where Σ* has condition number at most K. Using O kd=dd MLE has TV error e, regardless of the distribution of x.
log kdd
samples, the distribution generated by the
Like Theorem 1.1, Theorem 1.2 shows that conditional generative model can be learned in TV regardless of the distribution of the input It generalizes Theorem 1.1 in three ways: (a) the output y is d-dimensional rather than 1-dimensional; (b) the covariance the noise Σ* is learned rather than specified; and (c) the ReLU nonlinearity imparts additional complex structure.
Indeed, the point (c) means that parameter distances are poor metrics for this problem. For example, when an element of W z has large negative bias, the corresponding coordinate in y will almost

---

always be O. This means sample pairs (Iz, provide little information about W' but still provide useful information about the conditional distribution. As we will later see, exploiting this valuable information in the truncated samples allows us to significantly outperform prior works such as [35], which not exploit these O-valued samples.
Multilayer Networks Given Activations. Given our distribution- free results on 1 1-layer networks, it possible to extend our results to deep multi-layer networks. Given access to the internal activations of neural network (but not the weights), our results can be applied layer-wise. Intermediate layers may have poorly conditioned input distributions, but since our result does not depend on the input distribution, we achieve strong guarantees for layer-wise learning in Theorem 4.6.
1.1 Proof Approach
In this outline we focus on the case of 1-dimensional y, and and standard Gaussian noise rj A/,0, 1). Our proof approach is inspired by learning bounds that exploit finite VC dimension. We would like show (1), or equivalently.
d(w", @) (Edrv((ww (v P=) =))] s
when see samples x; of and sample ys for each 2;. We do this in two stages. First, show that the empirical distance between w and w is small i.e.,
d(w", i = Eldrv (p (y 2), pa(y x))] 0.5c,
(4)
where ==] f(x, denotes the empirical expectation over æ. Second, we show that the empirical distance a good proxy for the true distance, i.e.,
d(w"; w S d(w", i + 0.55 Se.
(5)
which gives (3).
Linear Case. In the linear case, both stages straightforward. The linear regression solution has an explicit form, and it is well known and easy to show that
E(x" (w x)) x k/n.
Since dry (pm- (y) Pa x)) Ominn(1, |x (w* - I))),, Jensen's inequality implies (4) for k/6² Secondly, (x) == drv (pw- (y 1), Pw (y x)) is bounded and unimodal in w. Thus, suffices to bound the deviation of the empirical average from the true fw (z) with Chernoff's inequality.
ReLU Case. In the ReLU case, we have y = d(w" x + 7), and both stages of the previous analysis more difficult.
The most interesting part of our proof is showing the first stage for the ReLU case, which states that the @ maximizing
L(w) 1
log P (x))
satisfies (4). Now, for any not satisfying (4).
E [[ L(w")]
= E dk (pw- (y I (y x))
< E(drv (pw- (y x) Pa (u x)) < -2
where the first inequality follows from Pinsker's 's inequality. Unfortunately. L(w) L(w") does not concentrate well, by virtue KL-divergence being unbounded. However, we can upper bound it via the Bernstein inequality, such that for fixed w not satisfying (4), and given zz log( samples, we have
L(w) L(w") -
3

---

with probability 1 - 8. Using a careful covering argument and n = (k/=²) log(1/)) samples, we can uniformly extend this all w not satisfying Eq (4). By definition, the MLE has L( ((w)) and by our uniform bound, it must satisfy (4).
The second stage changes because (x)) depends x: and x == in more complicated way than through r (w w²). ). This makes showing bounded VC dimension more difficult; however, unpacking the proof that VC implies generalization, we can still show that the net (normally given by Sauer's 's lemma) is bounded. This generalization holds as long as fue (I) is unimodal in æ w.
2
Contributions
We show that MLE can perform distribution learning in the setting of linear regression and multi-layer ReLU networks. Our bounds do not make assumptions the distribution of the condition number of W*, and achieve a sample complexity polynomial in the system parameters.
We improve the sample complexity bound in [35], which estimates the parameters of a one-layer ReLU network but suffers exponential dependence the W* term. In contrast, estimate the distribution of (Ir, y), rather than the parameter W*, we are able to avoid this. See Section 4.2 for more details.
seek to
3. Our algorithm for learning multi layer ReLU networks is considerably simpler than [1], who learn discriminators that are engineered to perform moment- matehhig on the output of each layer of the network. Furthermore, [i] impose strong requirement the sparsity and independence of the activations at each layer, which essentially allows standard techniques in sparse coding to recover these activations.
3 Related Work
Generative adversarial networks (GANs) [19, 2, 30] are a popular family of generative models that train a generator and discriminator an adversarial training framework. The seminal result by [22] proposed progressive growing of GANs (PGGANs) as way to stabilize and accelerate the training phase of these models. Future results, such as StyleGAN [23] introduce more complicated architectures and "style" variables. Additionally, these models add noise at each layer of the generator in order to introduce greater stochasticity the generated images, which is important for textures such as hair and skin.
Distributional Learning Most theoretical results have focused on the min-max optimality of GANs [15, 28, 29], characterizing their stationary points [21, 17], or characterizing their generaliza- tion once they have reached a global minimum [3, 5]. The closest result to ours is [35]. Setting æ to deterministic scalar in problem statement reduces it to [35], who consider y @(b + 7)) s.t.
b, 77 E RRd and they seek to learn the covariance of r along with the bias vector b. However, their sample complexity bound suffers an exponential dependence on |1b113.
Single layer networks have attracted recent attention, as they provide a tractable formulation for studying the dynamics and generalization of adversarial learning [24, 18, 25, 11]. The recent results of [1] show that multi-layered models that satisfy a property known as forward super-resolution (such as PGGANs) can be learned in polynomial time and sample complexity using stochastic gradient descent-ascent ascent. In this case, the discriminator is designed to detect differences between higher order moments of the generated and training distribution. Deep models have also been considered in [12, 10].
4
Main Results
In this section we first show that the MLE of the parameters learns the input-output joint distribution for linear regression. Then, we extend this guarantee to the case where the ReL.U activation function applied to the multi-dimensional output y. Finally, we show that we can compose the 1-layer ReLU guarantee to learn the distribution generated by multi-layer model.

---

4.1 Linear Regression
We begin with the classic linear regression problem of learning the parameter w" from a linear model
y = x. w + 1/,
where 7) ~ (N0, o²), w E RR* a known and x E R with some distribution. This problem has been studied for centuries. Our novelty is that view (6) conditional generative process, and instead of studying error in Euclidean distance in parameter space, i.e., minimizing || x == 2: 2212. we focus on eπrоr in d(w", @) as defined in (3), which only captures the error in w insofar as impacts our distribution estimate, Given data {(ri, yi) generated by (6), the MLE is:
(g) w x2)
== arg mna
Σ RE(M]
Po (Wbla,) = arg min WERE
x²
WER"
XE(m]
The following theorem establishes that the MILE is close in TV distance. The proofs for all results in this section are in Appendix A.
Theorem 4.1. Let {(,, y=)] be ii.dd random variables generated from the linear model (6), and assume that is known. Then, for sufficiently large constant C >> 0,
n C k log
8²
samples suffice to ensure that with probability 1 - ss((n)) over the data,
d(w, w²) S.
Note that one cannot hope to get such guarantee in the classical setting where error is measured in || - x - = æ||2 without additional assumptions on the distribution of æ because if x is badly conditioned, the error may be dominated by very rare directions of that we never sample. For example, the bounds in [7], Chapter 3, require the second moment of z to be bounded.
Since only wish to learn the distribution of y in total variation, single x can contribute much to our loss and we get a distribution result. This is possible as the total variation distance is bounded, and
invoke Theorem 1 11.2 in Györf al [20].
We now state two lemmas needed to prove Thereom 4.1, assuming without loss of generality that a² = 1. We split the proof into two stages. In the first stage, we bound d(w,, w²), which denotes the empirical TV distance (4) over the training set {==)==1-
Lemma 4.2. Let {(Ia, y:)) be i.i.d. random variables such that = w" +N 1). Then, for n 2 k 2. with probability 1 - -(n)), the MLE to satisfies
k
ā( w²) S V
2n
The proof relies on the fact that pw. (3/²z)) and p (y) (z.) are Gaussian distributions, so d(p x,) Pw- (z)) Omin (1, |a (w- - ))))
Using the explicit form of the MIF, we can show that, with high probability,
-(((o-w")) 2n
and Lemma 4.2 follows from Jensen's 's inequality.
The second stage shows that the empirical average of the TV distance d(@ō, w²) is close to the population average d(ūr, w²).
Lemma 4.3. Let { be i.i.d. random variables such that ot Dzv For sufficiently large constant C O, and for n C log with n 2 H, we have;
sup Mw. w²) d(w, n0)) > Se -l(n6))
Pr
Dr
WEER
5

---

Note the probability in the above statement is with respect to the distribution of и, and does not depend on y. The proof follows Theorem 11.2 in Györfi et al [20]: it relies on the fact that the TV distance is bounded and unimodal function of w x. This implies that for each 2ú we are able to partition the space of w with O(1/e) hyperplanes such that within each cell the TV distance varies by at most e. As we have samples and w E E the number of cells induced in IR. is (n/e)*, and it is sufficient to provide concentration bounds for one representative in each cell. This approach is similar to bounding the VC dimension of set of binary functions. Setting n. = ( log !)) and combining Lemma 4.2 with Lemma 4.3 gives dl ((0 w²) S.
4.2 ReLU Case
Now consider the linle-layer ReLU. We observe (z. y) IR.ht Rd such that:
y <(W"> x + m),, 7 ~ NOO,"*
where 7) E RRd, W and o(-) max(-, 0) applied coordinate wise. The matrices W E Rd and Σx E Rdxd are unknown, and we do not observe 7). The variable is drawn from an arbitrary probability distribution Dz, and we make no additional assumptions on Dz: this is important, we will progressively cascade layers, and one should think of DD being the distribution of activations at each layer.
Given sample (ar, y) TR* x Rd, let S denote the co-ordinates of y that zero-valued, and let S denote the compliment of S. Then, the log-likelihood of W, Σ, on this sample is given by
log Pw.s(yla) = c- log
(t Wx) "x - Wx)
+ log
exp
dts.
(8)
2
Su
(go san=
where e is normalization constant which does not depend on W or Σ. This function is mixed density: in the coordinates of y that are 0, i... in the set S, we integrate the Gaussian density over the negative orthant, W*r could have been any negative value in those coordinates.In In Lemma F.1
in the Appendix, we show that Eqn (8) is concave after an invertible reparameterization of W, E.
In this setting, proving an analogue of Theorem 4.1 poses multiple challenges:
The output y is d-dimensional rather than scalar, and 17 in Eqn (7) introduces correlations between the coordinates of W x, such that we cannot decompose the log-likelihoor in Equ (8) per coordinate.
We do not know the covariance matrix Σ', and it must be estimated.
Lemma 4.2 requires the explicit form of the MLE in linear regression. In the absence of such closed-form solution, we need to directly analyze the log- oigliikeihood, which is mixed density and involves integrating the Gaussian likelihood over the zero-valued coordinates of y. In order to handle this, we use the Györfi approach again on the log-likelinne aigliikll This is challenging because the variables we concentrate are KL--divergences, which are unbounded and require Bernstein type inequalities.
Recovering the true parameters W "* is difficult: we see a zero in y. we do not know its magnitude in W*r + before the ReLU. This manifests in the results in [35], where it is assumed that each entry in W* is positive otherwise, their sample complexity scales ell ellll,
Nonetheless, we can handle most of these difficulties, and the only assumption we make is that the condition number of Σ" is bounded and known to our estimator.
Assumption 4.4 (Condition number bound). Let Xinxx Xmiin denote the largest and smallest singular values of E. We assume there exists k < oo such that Amax of i known to our estimator.
< We further assume that the value
Xaan
Note that the condition number only allows us to control the correlation between the coordinates of W' x + The other challenges introduce by the ReLUU, such as the lack of closed form MIE, the need estimate Σ* and a mixed density log- likelihood remain.
Under Assumption 4.4, the following theorem shows that the MLE W, E achieves a small total variation distance. The proof of this theorem is in Appendix C.

---

Theorem 4.5, Let Bi denote the set of positive definite matrices with condition number K. Given samples {T Vs) Vi) satisfying Assumption 4.4, where 2; Dz i..dd, and y generated according to (7), let W, == arg m&X ERAXA WERIA. "EBE + 3i pw.. Tz). Then, for a sufficiently large constant C > 0,
kd de E²
kkd
n C.
log
Eδ
samples suffice to ensure that with probability 1 6, have
drv (W. (W*, Σ²)) S..
Comparison [35]. Our result closely related to [35]. Our ReLU model reduces to their model by setting W' E Rd vector, and 1. In order to learn the distribution of y. they first estimate the parameters W*, E", in E2 norm and then convert the le error to a TV error. The parameter recovery is done coordinate of W* by performing MAP estimation on the positive samples in y. This crucially assumes that each coordinate has enough positive samples, and to that end, they assume that each entry in W is positive-othereeeee otherwise, their sample complexity scales as e [W'll, Our results do not make any assumptions W and handles wider class of matrix valued W*. Additionally, the objective function (8) does not discard the zero valued samples in y, making it more sample efficient.
We assumed that the covariance matrix E" has condition number K, and our sample complexity scales as log k. Hence, even = (Poly(d.k), we only pay a poly(d, k) penalty. This improves on the result in [35], where the sample complexity scales as x². While our statistical guarantees are strictly better, [35] gives poly-time and poly-space algorithmic guarantees for their estimator. We discuss the empirical limitations of our algorithm in Section 6.
Lower Bounds Ignoring log factors, the complexity factor of kd is obviously required. Furthermore, learning a Gaussian with unknown covariance matrix in total variation takes (((d²) samples; see [6]. Our Theorem 4.5 would solve their lower bound instance, the same lower bound applies to our problem.
Extension to Multi-Layer Generative Models. model.
Consider the following (L + 1)-leyered generative
FL+1 Wi + nL, where De <(W, --- m)-1) IR A [1
(9)
~ Do and NO0 Ei) A f [].
(10)
We can compose the guarantees provided by Theorem 4.1 and 4.5 to show that we can learn this model.
Theorem 4.6. Given n i...d. samples of (Zo..... LL+1), such that each matrix Σj satisfies Assump- tion 4.4, let We, Ee, be the MLE estimates of Wt. Mi learned from samples of (xe,Zet)) Define m = max; &.. Then,
112m E2
Imn
))
71 0
log
cō
samples suffice to ensure that with probability 1 1-6 8,
drv ( Extte {(W7, 22) Se.
Comparison to [1]. The modelling assumptions in [1] are similar to ours the authors learn generative model per layer, using images produced per layer. The key differences of their model are: (i) each layer is deterministic (there is ne), (ii) their learning algorithm does not require access to the activations of each layer, (iii) their algorithm performs moment-matchin by crafting the discriminator strategically.
In order to avoid requiring activations each layer, [1] imposes a sparsity assumption on the activations: this allows them to leverage tools from existing results in sparse coding [4], such that
7

---

((0.2))
144
(0,)
drawn independently Ox Lap 10
(e:00) 2o) Yيا o))
di at)
Number Samples 10
Ingrtt dimension &
(a) Total Variation
(b) Total Variation vs. A
Figure 2: (a) Plot of TV distance vs. n. 1, w² 1xx1, for two different values of k = 5 and k 20. Plot includes data for two different distributions x. Note that distribution has little impact on TV distance, and in both cases, we see the еттоr decreasing with slope of - 1/2 in alignment with our theory. (b) Plot of TV distance vs. input dimension For both 10 and n 10*, the error grows with slope of roughly 1/2. in alignment with our theory. In both plots 2000 runs are used compute the mean. Error bars represent 95% confidence intervals.
sparse activations at each layer can be recovered using images produced by the layer. This assumption can be somewhat strong, implies that the activations are roughly independent one another, and the sparsity remains constant over layers, despite the layers themselves expanding by a factor of 4, i.e. de 2 4de-1 -
Simulations
We now numerically verify our theoretical claims and compare against other approaches. A detailed description of simulation methods are included in the appendix. Our code is available at https: //githubs
git.
5.1 Scaling in n and k
Figure numerically investigates how TV distance of the MLE scales with the number of samples and the input dimension k. We consider model with 1-dimensional output and a k-dimensional input: = 6(x w" + m), for w* E R and 77 ~ ((0,0²) We set o² = and w" 1 both unknown the optimizer, which has samples (yt, 2x) Figure 2a, which plots the error in TV distance against n on log-log plot, has a slope of roughly - 1/2 as predicted by our theory. Similarly, Figure 2b has slope of 1/2, which is in line with theory scaling with respect input dimension k. We defer simulations involving scaling in d to the appendix because computing TV distance becomes increasingly difficult d becomes large, and must resort to using upper bounds.
5.2 Distribution Independence
The fact that our guarantee does not depend on the distribution of x suggests that the expected TV error of the distribution learned from the MLE may be similar for all distributions over z. To test this we consider both x ~ AO, J&) and x ~ X Lap(0, 1), i.e. each element standard Laplace. Figure 2a verifies our hypothesis, showing only very slight differences in our observed empirical average T'V error between the two distributions over wide range of n, and for A 5 and l 20.

---

0032
Our TV
We al. TV
Our parnittte MSE
We paeamslee MSE
0020
af ((888) 300..r .21)
et TV
801
301
280
Dios Value
(a) Total Variation vs. Bias
(b) Total Variation vs. Condition Number
Figure 3: (a) Left hand axis shows TV distance vs. bias vector b with y o(n + blax1), d 3, ? (0, Σ). and Σ = Id- Note that MLE (blue) has error going to zero as bias becomes negative, while the opposite true for the baseline (red). Right hand axis shows the mean-squared error of the parameters Σ and the mean jr, each point was run a total of 2000 times. (b) TV distance vs. condition number, 3. MLE does not exhibit trend with condition number, but baseline does. Error bars 95% confidence intervals, over 20000 runs.
5.3 Scaling with Bias and Condition Number of Covariance Matrix
A key feature of the MLE is that it makes use of truncated samples. This is in contrast to [35], which leverages results on learning truncated normal distributions [14] where truncated samples are not observed. This leads to a stark difference in performance as the number of truncated samples becomes large. To show this, we consider a model with a d-dimensional output and 1-dimensional input. We let = 1 almost surely, and then take w' bl for some bias b R and n (0, Σ) with = Ia. thus = o(n + bldx1). As becomes more negative, the number of truncated samples increases. Figure 3a shows the differing behavior of MLE and that of [35] as b becomes negative. For ease of computing the TV distance we set d = 3, and restrict optimization over diagonal Σ. The solid blue line depicts the performance of the MLE. We observe that the TV error is constant for b 0 and begins to decrease rapidly for 6 < 0. This happens because as b becomes more negative, the truncation places more probability mass at y = O. Indeed, the dashed blue lines indicate that even as the TV error is decreasing rapidly, the mean square estimation error of the covariance and mean increase, however, since most of the probability mass zero, this does the TV. In contrast, the method of [35] rapidly deteriorates as < as the number of untruncated samples decreases. We also point out that even when the bias is large, [35] is still significantly worse. We attribute this to the fact that even when there is no truncated samples, [35] is still minimizing different MAP objective. More discussion of this provided in the appendix.
significantly impact
Robustness to Condition Number of E. Another concern is how TV error scales as function of the condition number of Σ*. Poorly conditioned Σ* can put significant probability masses on small sets, and potentially cause large error. We consider similar environment to the one described above, but fix 6 = 1 and alter diagonal entries of E such that one entry is VR. another is VN-I and the rest are 1, making the condition number K. Figure 3b shows that the MLE is not measurably impacted by the changing condition number the range plotted. This is not true of [35], where observe that TV does grow with condition number.
Limitations
This work is only first step to understanding fundamental limits of learning generative models. We showed that our theorems for single-layer networks can be composed to get sample complexity bounds on deep networks, with a critical caveat: we require access to not just the input and output pairs, but also the intermediate activations. This is not practical in many scenarios, and removing this restriction will be an important direction for future research. Beyond this, we assume that the learner has an understanding of the model architecture. In many cases, however, learner may not be aware

---

of the number of layers network has or a vast number of other architectural details. Additionally. we inherit known problems with the MLE, such as exacerbation of biases that exist in the training data (Chapter 2..1.3 in [33]).
Our results place emphasis sample complexity
computational complexity. Though show that the MLE problem is concave, this work does not provide thorough analysis of the optimization problem. It is possible that similar results [14, 35] can be derived for the MLE problem. Indeed, empirically, we find that a similar projected stochastic gradient ascent performs well in our problem. careful analysis must consider factors like the distribution over z, the condition number of Σ* and the truncation probability, all of which are likely to impact the optimization.
7 Conclusions
We have studied the problem of learning conditional generative models from a limited number of samples. We have shown that it is possible to learn I-layer ReLU conditional generative model in total variation, with no assumption on the distribution of the conditioning variable x using the MLE. We have also shown that this result can be extended multi-layer ReLU networks, given access to the internal activations, Our results suggest that MLE is promising approach for learning feed-forward generative models from limited samples.
Acknowledgements
Ajil Jalal and Kannan Ramchandran supported by ARO 051242-002. Justin Kang and Kannan Ramchandran are supported by NSF EAGER Award 2232146. Eric Price is supported by NSF awards CCF-2008868, CCF-1751040 (CAREER), and the NSF AI Institute for Foundations of Machine Learning (IFML).
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Forward super-resolution: How can gans learn hierarchical generative models for real-world distributions. arXiv preprint Sikiv::200.026119 2021.
[2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein arXiv:1701.07875 2017.
gan.
arXiv preprint
[3] Sanjeev Arora, Rong Ge, Yingyu Liang Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In International Conference Machine Learning, pages 224-232. PMLR, 2017.
[4] Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. Simple, efficient, and neural algorithms for sparse coding. In Conference on learning theory, pages 149. PMLR, 2015.
[5] Sanjeev Arora, Andrej Risteski, and Yi Zhang. Do gans learn the distribution? some theory and empiries. In International Conference on Learning Representations, 2018.
[6] Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM (JACM), 67(6):1-42, 2020.
[7] Francis Bach. Learning theory from first principles. Draft of a book, version of Sept, 6:2021, 2021.
[8] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasympottic theory of independence. Oxford university press, 2013.
[9] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[10] Sitan Chen, Jerry Li, and Yuanzhi Li. Learning (very) simple generative models is hard. arXiv preprint 2205522255..003 2022.
10

---

[11] Sitan Chen, Jerry Li, Yuanzhi Li, and Raghu Meka. Minimax optimality (probably) doesn't t imply distribution learning for gans. arXiv preprint arXiv:2201.07206, 2022.
[12] Sitan Chen, Jerry Li, Yuanzhi Li, and Anru Zhang. Learning polynomial transformations. arXiv preprint Stt::2004.44009, 2022.
[13] Annie AM Cuyt, Vigdis Petersen, Brigitte Verdonk, Haakon Waadeland, and William B Jones. Handbook of continued fractions fractions for special functions. Springer Science & Business Media, 2008.
[14] Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Ef- ficient statistics, in high dimensions, from truncated samples. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 639-649. IEEE, 2018.
[15] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint wrXiv::711.00//44 2017.
[16] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians. arXiv preprint arXiv: /8 10.08693, 2018.
[17] Farzan Farnia and Asuman Ozdaglar. Do gans always have nash equilibria? In International Conference on Machine Learning, pages 3029 3029-3039. PMLR, 2020.
[18] Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding gans in the lag setting: Formulation, generalization and stability. IEEE Journal on Selected Areas in Information Theory, 1(1):304-311 311, 2020.
[19] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672-2680, 2014.
[20] László Györfi, Michael Köhler, Adam Krzyżak, and Harro Walk. A distribution--fee theory of nonparametric regression, volume 1. Springer, 2002.
[21] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
[22] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for im- proved quality, stability, and variation. International Conference on Learning Representations, 2018.
[23] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4401-4410, 2019.
[24] Qi Lei, Jason Lee, Alex Dimakis, and Constantinos Daskalakis. Sgd learns lne-layer networks in wgans. In International Conference Machine Learning, pages 5799-5808. PMLR, 2020.
[25] Yuanzhi Li and Zehao Dou. Making method of moments great h-ow can gans learn distributions. arXiv preprini arXiv:2003.04033: 2020.
[26] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint
2013.
[27] John Mills. Table of the ratio: area to bounding ordinate, for any portion normal curve. Biometrika, pages 395-400, 1926.
[28] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate of o(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30333333303 2020.
[29] Vaishnavh Nagarajan and 7ico Kolter. Gradient descent gan optimization locally stable. Advances in neural information processing systems, 30, 2017.

---

[30] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06444 2015.
[31] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. sero-shot text-to-image generation. In International Conference Machine Learning, pages 8821-8831 PMLR, 2021.
[32] Robin Rombach, Andreas Blatmannn, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684-10695, 2022.
[33] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[34] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Alpaca: A strong, replicable instruction-followin model. 2023.
[35] Shanshan Wu, Alexandros G Dimakis, and Sujay Sanghavi. Learning distributions generated by one-layer relu networks. Advances in neural information processing systems, 32, 2019.
12

---

A Proofs of Linear Case
Throughout the appendix, for ease of notation, we overload the definition of the function dry(:.)). When inputs are random variables, it represent the TV distance between the distributions of those random variables.
Lemma 4.2. Let [[1 vi)) be i.id. random variables such that = w" + +N(0, 1). Then, for n 2 2' with probability 1 - (im), the MLE t0 satisfies
k
dw, w
2n
The proof of this lemma requires Lemma A.I, which characterizes the distribution of the residual error of the MLE.
Lemma A.I. Given y E RR, X E Buxk satisfying y Xw" + T, where ~ NN,, I,),, the least square solution w satisfies
Xw - Xw ~ N00,N X(x = B Xw"1 = =²k.
Proof. The least squares solution is given by
i (X"x)-1XXX y:
= =xx"x) xx"xx-1Xx1 Xx (Xw" + n))
Multiplying the left by X, we have
Xw X Xw" + x(xxx))
Since 7) is i.i.d. Gaussian with variance σ², have,
This implies
E[[| Xw [|]] Xw
xxxxx(x-xx x7),
= x)- x2 X).
o²k.
Proof of Lemma 4.2. The KL divergence between two Gaussians P = NN Σ) and Q = NN2,, E)
is:
dkz(PllQ) (11 p2) -22)-
By Pinsker's inequality, this implies
1 V(ui - 12) - μ2)
drv (PIQ) S min 1, 2
13

---

Hence, the empirical TV on the dataset can be bounded by
7 (w
Σ drv (Pa Per (u/k;;) v
min
1, 2
1
a (e((@
ww)
2
min
1
71
0
( - w++)
min
1, 4n
Σ
0²
min
1, 4n 0²
||X ([(W=="1l w2
where the second line follows from Jensen's inequality. By Lemma A.I, we have
BIIlX(0 w" )| | o²k.
which implies that with probability 2((), we have
||X w²)l S 20
Substituting in the earlier inequality, we get
Σ drv(pa(()zz) Pw- (ylx:)) s
k
k
k 2
min
1,
for
2n
2n
Lemma 4.3. Let {2, )iz be i.i.d. random variables such that at ~ Dz For a sufficiently large constant 0, and for n C log 1 with n 2 5,, we have:
sup d(w w²) d(w, w+)| > Se-
Pr D,
LWERk
Proof. The proof is inspired by Theorem 11.2 in [20], with modifications to our setting,
Let Since far(x) is bounded, for any fixed w, the Chernoff bound gives
Pr d(w w²) d(w, w²) a 2no
(11)
for any a O. The challenge lies constructing a "net" to be able union bound over R without assuming any bound on w the covariate æ. A net is a partitioning of space, where within each part, points are close together some way. In this case, we construct a net using what we will refer to as "ghost" samples.
Ghost samples. First, we construct a "ghost" dataset D'r consisting of n new samples, drawn i..dd (a/)xe(s) Dz This gives another metric d'().)) Instead of directly considering the distance between d(w, w²) and d(w, w*), is sufficient to consider the difference between d(w, w²) and dww w²) i..,
Pr sup d(w; w²) d(w, w²) > < 2 2r sup d(w, w²) - d' (w, wn)| > e/2
(12)
To see this, let maximize d(w, w²) d' d'(w, w*). Since w and (a/lie(m) are independent, by the Chernoff bound,
Pr (w w²) - d(wi, w²)
> >e/2|D=] Se =e=ne 5 1/2.
14

---

for any (Dz, () and large enough n. Thus,
Pr (w, w²) d( w²) > e/2 2 Pr [((,,w)) - a(w,, w²) > en w")
w²) - 2w, (w,,""))) < e/2)
De [| Pr dd w0) - ((w,,w") < <E/2|Da)
2 (1 1/2) Pr
[dl w²) a(wr > >6]
which implies (12).
Symmetrization. Since D₂ and D', each have independent samples, could instead draw the datasets by first sampling 2n elements ........ 222m from Dz, then randomly partition this sample into two equal datasets. Let 8; [#1] so = 1 if z; lies in D3 and -1 if it lies in Dz., Then
2n
d' w²) d(w; w²) - Σ 8; drv (ylla)) Pw. (x))
For fixed w and 21...., 22n. the random variables ($1,..., 82n) are permutation distribution, so negatively associated. Then the variables s; - drv (Pw (y) [z), Pw (y)):)) are monotone functions of 8t, so also negatively associated. They are also bounded in 1-,, 1]. Hence we can apply Chernoff bound:
Pr | w") ā(w, wn)
< <
(13)
for any fixed wo
Constructing a net.
We partition & the space of w s.t. if w. w are in the same partition then, ddv (Pw (ylx)) (z/z)) drv (Pwr (ylz), Pw (ylz)) < a.
for each x in the dataset 21.... Z2n. Then take the intersection of all 2n partitions to construct a net over R*
As the total variation distance is a unimodal function of 2; w w", we partition w the sets {w : drv (p x;), Pw. (yl (2)))) E [ja, (j 1)a]
where j goes from 0 to 1/a 1. So the space of w, g is partitioned by 2n sets of 1/a parallel hyper-planes. Then the total number cells at most
4en k ad
2n
(2/a) s2
We define a net N by choosing one representative of each cell in the partition, so |N| S 2h log ak. By (13),
Pr max (1o w²) - d(wr, w²) > |Nle n=2 1Nle--n21/2 < 222h
2 log a -n2n2
WEN
Finally, for any Rdd let v N be the representative of its cell. By definition of the cells, |drv (pw Pm (ulx:)) - drv (pna(y) Pw- (y/x:)) <
for all E [2m]. Thus
(d' (w, w²) - d(w, w²)) - (1 w*) d(li, w²) s diww w²) d(wo, wn) + d'(w w²) - -d'(w, (((..w")) w²) s 2a
and so
Pr sup d' (w, w²) d(w, w²) > E
Pr
max WEN
d' (ww C(w, wn) >E 2a S E
2o log :i 20/222)2n/2
LwERd
Setting e/4, we have that
1
S 3
k log
suffices for
max d'(w,w w²) d(w, w²) )=²² > E <e ale'n) weR
Pr
15

---

B ReLU Activation with Scalar
In this section, we consider the model of
<(w" x + 1)), 1 (o,,
where w", x E R 9.7. R. We are given samples (r,y) E R x R. and want to estimate a that estimates the distribution of y in TV.
The most challenging aspect of the ReLU setting is that we do not have an expression for the TV suffered by the MLE, such as Lemma 4.2 in the linear case. This forces us directly analyze the log-likelihodd.
For a fixed x, w,, the expectation of the log- log-likelihood ratio over is
Pw (y
x)
E 9 Pw- y x
log
-xx I -2d w)
where the last inequality is via Pinsker's inequality. This equation implies that if w is e-far from w", then the expected log- likelhhoood ratio(LLR) is < -2s2. By definition, the MLE has a non-nega non-negative LLR. Hence, if the empirical LLR is close the expectation, this would imply that the MLE has small TV.
However, we only receive a single sample of per z. For fixed we can prove a Bernstein inequality, showing that given 1/e² log(1/8) samples, the empirical LLR < -E² for that are e-far.
Lemma B.1. Let pı..... Pu and f1....,
In be distributions with E, Ea (Ps, 9:)] 2 E, where we use
the uniform measure on i [n]. Let for i [n.]. Then w.p. - 8, E, [log 2:(=a]] I _ for 0 log )
The proof of this Lemma, well other Lemmas in this section, can be found in Appendix B.
In order to extend this to all w E R that are e-far, we will construct a cover over R depending on the values the log-like likeliooddood ratio can take, and then apply the Bernstein inequality to each element in the cover.
In order to construct the cover, we first show that the log-likelihood ratio is bounded above by the magnitude of noise in y. For ease of notation, for fixed x R and each R define
(I, w) E IR
and let (a, ).Smmila
,iiilar to the notation for w, for each IR, define pe as the distribution of Φ(0 + 7) for (O,, 1). Define the log likelihood ratio
Pe Py (x:)
(v) == log
Ps- (y|z))
The following Lemma states that for a fixed datapoint (ar, y). the log-likelihood ratio bounded by the noise in Lemma B.2. For any y = 6(0 + n).
{ |log (0(-) -log (--0")
ify=0
r0(1)=
(n(0- ((-)- 2
(0-00)2
if >
and therefore, for all y.
70(2) S 1
Now, as 7 is bounded above by Inl 2 and is concave wrt 0, the following Lemma shows that we can partition 0 into O( (( intervals, such that in each interval, changes by atmost e, or is very negative, i.e., 7 < A.
Lemma B.3 (One-dimensional net). Let A > B²> 1. There exists partition of IR into O(A/s)
intervals such that, for each interval I in the partition and every y = "(0" + 17) with bn) S B, one of the following holds:
16

---

For all 0 E I, 70(3) - -
For all 0, 0' E hv) yo (y)l S
Using Lemma B.2 and Lemma B.3, can form a uniform bound, such that all w that are e-far from w" in distribution will have log- ligliike ratio smaller than -4 on the training set. With some additional arguments, empirical TV.
now show that the MLE has positive log- li-likkiihood ratio, it has small
Lemma B.4. Let 21....,22 Zn be fixed, and yi olat w" ms) a (.. For 2 log the MLE w satisfies
d(, (oo,w))ss S..
This sample complexity guarantees that the MLE good for the set of empirical 2y Dz, and we need to extend this to the expectation over x ~ Dz, for which we use Lemma similar to Lemma 4.3 in the linear case, and this completes the proof.
A straight forward combination of Lemma 4.3 and Lemma B.4 gives the following Theorem.
Theorem B.5. Let y oxx w² + +n), for w" sufficiently large constant C > 0,
E IR. x Dz, and 1 NNO,, 1). Then for
k
C
log
E2
samples of (115 +d) suffices to guarantee that the MLE â satisfies
d(w, w w²)===))) S.
B.1 Proofs
Lemma B.1. p1...... Pr. and q1.....9m In be distributions with E, [drv (ps, 9:)] 2 E, where we use the uniform measure on i E [n]. Let I, ~ for i E [n]. Then w.p. - 8, Eoolo pi(a)) I 5 for n 0 log t))
Proof. Define 7a(x) log (((a) pilz) and (x(x)) max(7;(x), -2). We have that
Eb((z)] = Bldxi 9:)] < F[2drv (pr, 2;) S -2
and want to show that E, (x() < -E2 /4 with high probability. Note that a,()) 2 (²(x), so suffices to show [x)] I -E" /4. We will do this with Bernstein's 's inequality, for which need bounds on the moments of a, (2))
To simplify notation, fix a particular and consider Ps: 4z a, and
For a random variable v, define v_, V_ be the positive/negative parts of v. respectively, so g(x) 1. We have that Ex Ex>p/A(x)) = 0. and p(z)
v = e + u4. Define A(x)
E [A+
E II-A dp.
(14)
Now, consider the function b(z) max(log(1 + 2), 2) z. This function is nonpositive z 2 - 1, and b(z) < - 2² for 2 E 0. Since
a(x) b(A(a)) A(x)
and Exnpl (Axx) = 0, Ex-pl (aasppla(z) a(x) = Ex-pp (-alll-((--- (x)) This means
a(x))
E (-((()))
E (-MA(r))) a>1
>
E A (2:)/2)
xmp
or by (14),
E Bi-a(z)] (x) drv (p.
(15)
17

---

Bounding the positive higher moments.
We have that p(z)e e
/ m
Elealey
<1+e -2].
In the following, we use that ef 2 1 + t for all t. as well as = 1 + 2k=2# Therefore
1 1+ e 2 Pr[a(x) = 2]
> B Ble
= - La aa(w)su + ea-(()) 10 la(x)>u]
2 Bij + (a (z) + (x)) + (1)r
1 Blax)] (1))
SO
Bla (x:) < [xx)] t 2 Pr(a(x) --]
We now show that the Pr(a(()) 2] is smaller than the B[-a(r)] term, by relating to -b. When
alx) 2, (xx) - -1+1/e", and and (()) 22--(()) S 1. Since -b(A(x)) is non-negative,
and at least whenever a(x) -2,
B[-a(x) = B[-b((x))) 2 -2]
and hence
Σ x [(f s (1+ ) )[
(16)
In particular, B[a (x)) < 2k 2k! for all k x23 2.
Bounding the second moment of a. We have that
E[a(z) = E[a (x) + a² (x))
and E[a [x)] < 4E[-a(x)) by (16). We now bound E|a2 (x)]. Note that [a-(x)] { LA (x)
by the construction of a. Therefore
S 64 (x)
and so by (15),
E|a2 (x)) S
6E A (x) 12
Thus
(x:) 16 16
(17)
Bernstein Concentration. Now we can apply Bernstein's inequality (Theorem 2.10 of [8]).
We apply the theorem to X; = a, (wt), which are independent. The theorem uses that
E E [ax())) < 16n E [[]a; =:
by (17), and since
Σ =n Ela,,
=n
2k! E [[-a((x)]] < _ uk!
6,30
so we can set c = 1. Applying the theorem, we have that S = Σ (xx)) - Ela,(z;) satisfies
1 + log
1
S 2v 2o 5
8
18

---

with probability 8. Plugging in e and rescaling by n. with probability 8 we have:
[(a, - E [a((x)) + 0(1) | log |
1 1 5
n 5 + log
By our assumption on for sufficiently large constant in the big O, this implies
B|a.(zi)] - E [x) 1
El (1-a ha
+
6
Since by (15), e I V (pi, 9:) S Ei,l 2a, (r)]. this means
V2
S (-1+ [|aa({))
E a. (x) + 6 1,
V2
1
<
6
1
as desired.
Lemma B.2. For any <(0 + n))
log ((-0) -log ( (f(-)))
ify
(0(3)
1n(0- --)
(0-0-)3 2
ify >
and therefore, for all y.
70(1) S 1////22
Proof. Let (xx) be the cdf of standard Gaussian. For y >
1
(v = ((y 0²)² (yy - 0)²)
2
1
2 (17 (n) + 0" 0)
(0 )²
7(0 0*)
2
Thus:
log (--0) log Φ (-00)
if y
(v))
n((0 0*) (0-0-)²
if y
Now suppose |n| < B. We can upper bound (1) for all 6:
If y 0, then -0" > - B,
(0) < - log (--0)) S <lloge -12/22 =B2/2.
If y 0, then
(0 (0-0") 02)
vo(v) (0 - 0n)
S
2
as desired.
Lemma B.3 (One-dimensional net). Let A >²1
There exists partition of RR into ((A/s)
intervals such that, for each interval I in the partition and every y 5(0" + 17) with In| < B, one of the following holds:
For all 0 E I, 70(y) < A
For all 0, 0' e I. (To(v) ye (w)) S
19

---

Proof. To define our partition, we actually define two partitions, depending on whether 0, then intersect them for our final partition.
First, consider y = 0. By Lemma B.2, no (0) is monotonically decreasing in 0 from its maximum of most B2/2. We thus define partition P1 consisting of intervals of the form 7; == (0 (0) E [B² /2 (i + 1)E, B2/2 ig)). for i E {0, 1,......
, (A + B /2)/e}, plus a special interval of (0 To < -A]. When y this partition satisties the desired conclusion to the lemma: (0) Yot (0) (0)
I for all 0, 0' E I,, while 7a(0) < - for 0 E I'. Call this partition Po. which
has size O(A/E).
Second, consider y 0. Define R V2A + B. Note that R S and (R B)² > 2A. Therefore for 0- 2 R.
(0(4) - -2 max(0, 0- n)² AA
Consider any 0, E E00- R, rr + R with a : 0 8% We have
1
hoo(8) 70" (v)) - In(0 0'1 +
2 (0' )² (0 8²)2|
s Ba ? [(0' 0) + (0' + +))]
s Ba +
2 o0(2 a(B B + R).
Thus, for 2े. this is at most e. If we partition 18" R. 0" + R into length-a: intervals, get size (R2 /e) O(//)) partition P1 of IR that has the desired property for all y >> 0.
Our final partition defined by all endpoints in either Po and Pt. This has size O(A/s), and within each interval the conclusion holds for both y 0 and y > 0, needed.
Lemma B.4. Let 31,..., Fy be fixed, and y: ~ g(xTur w² + mo) do N.( For 2 3 log the MLE w satisfies
a(w 5..
Proof. For any w E RR* and sample (x, v.). let Pw (yl (r:) be the conditional distribution of y Φ((2,, w) + n). and let New be the log- le-likklihood ratio between w and w" on this sample:
Pw (1) Pw- (2) (x))
(v) log
Then
E| [l) -dx (pr,w (yl (M).
Define
n
dkL (w", w) dKL h (gl1))))
Concentration.
From Lemma B.1, we see that if d(ww", w) 2 e, then for n 2 0 log }))
1
Tu
2i (vi) <
(18)
with probability 1 8.
Of course, whenever Yw O, the likelihood under w larger than the likelihood under w. Thus, for
each fixed fied u with d(w", w) 2 E, maximizing likelihood would prefer w² to w with probability 1 if n O log })-
Nothing above specific to our ReI-U-based distribution. But to extend the MLE over all w, we need to build net using properties of our distribution.
20

---

Building net. First, with high probability, 17a $ B = (looog n.) for all i. Suppose this happens. For each i, by an abuse of notation, let " (V) ((...)) (y) where the value of 6* when considering i is (2i, w*). By Lemma B.2,
no (v:) - B²/2
for all í. Let A = OO log > nB2 By Lemma B.3, for each i E [n], there exists partition P; of into O(A/²²) intervals, such that for interval / E P. and any w, w' with of w, at w E I, either
Ti (Wi) Vi.wo (2s) S s²/2
(19)
N. (1A) A.
These individual partitions P. on (I; w) induce a partition P on R² where w' lie in the same cell of if (aa, w) and (rx w*) are in the same cell of P; for all i [m]. Since is defined by n sets of 0 ()) parallel hyperplanes in RR, the number of cells in Pi::
2.Aen
c2k
We choose a net / to contain, for each cell in P, the in the cell maximizing d(w=,, This has size
Log(W| S k log
By (18), for our 2 ( log ) we have with high probability that Tw S - T for all w e N with d(w",, w) 2 e. Suppose that both this happens, and |nd < B for all i. We claim that the MLE w must have d(w", w)
Consider any Rd with drv(wu (w", w) 2 s. Let w/ E N lie in the same cell of P. By our choice of N,, we know drw w²) 2 drv(us (w" w) 2 E, so Fw S = Now we consider two cases. In the first case, there exists with n. (Vi) < A. Then
A + 12 0.
Ju
nw (wr) S
Otherwise, by (19),
Tw S Nwo + 7 - -ool S e + max (a, Vi, (y:) S 222
In either case, To < 0 and the likelihood under w" exceeds that under Hence the MIL T must have d(w=, W) S
Dz, and n NO 1). Then for Theorem B.5. Let y o(2 w² + n). for w RR. sufficiently large constant C > 0,
k n =
e2 log
samples of (1), suffices to guarantee that the MLE to satisfies
d(w, w²) 5 S.
Proof. Let D. denote the dataset {zs hEjn) that is used to find the MLE. Notice that the MLE is found using this finite subset, but we would like to make claim about D. without making any parametric or simplifying assumptions on the distribution Dr.-
An application of Lemma 4.3 tells us that with probability 1 - e An(n)" the expectation over the distribution D. and the dataset Dz are within e/2 of one another:
d(w, w²) s d(ww, w²) =/2..
Now, all need to show is that the MLE has small TV distance the finite dataset, and Lemma B.4 tells us that with probability 1 =)
a w < e/2.
Substituting in the above inequality, get d(w, w²) S
21

---

C ReLU Activations with d > 1, Unknown Covariance
We recommend the reader review Appendix B, which contains the proof recipe for the case of scalar y. The proofs in this section generalize those of Appendix Consider sample (xr 3) Rexd, with
==W(W> x + 7))
(20)
where W E Rd x k, and noise ~ W(, The matrices W* and E' are unknown. For each matrix W E Rddkk let 0 Wx Rd, denote a reparametrization of W, and let 0* denote 8" = W Let S denote the co-ordinates of y that are zero-valued. Then the log- lillikiiihhood for each 8,2 given by
(0,x(1) == log x) = - 2
log + log
exp - -1-00)==--- (1-))))))))) 0)
where normalization constant which does not depend 1 E. Let
P==--
and let P* be the precision matrix of the noise y, and Ps, Pss*, Pses, Pso be the block matrices of P corresponding to the index sets and complement S
By some arithmetic involving completion of squares, we can decompose the integral in f into the sum of functions g, h, such that
So,z()) cc- log + g0,r:(y + he, xy))
The first term g corresponds to the quadratic term involving the observed positive-valued coordinates ys=
(0,r(u) -ys--
- 0g-) (Pp=
(Ps))(Ps)1PP))) (ys= 02-)
As the matrix Ps- s (Ps) Pss= ((P- (s-)- Es is the precision matrix of nss if Σ were the covariance of 17. we can simplify the above equation as
ga,r(y) = -ys- - 0g=) ) (Es=)
( -yys- 0g-)/2
(21)
The second term corresponds to the probability under 0, P of observing zero-valued coordinates corresponding to the index set S, given the positive coordinates ys.:
hay: log {
exp exp(-1113 (1 -0)) (Ps) 1/22///ss (ys- 0ss))1?/2)
(22)
The log-likelddood ratio is the difference between f0.5 and fo- which we denote by
(v) [0,5(y) So (v)
Over dataset (1r; bejo), the average log-likelihood ratio is given by
7W.: 1 Σ TWa,
Remark C.1. For ease of analysis, we will interchange between the precision matrix P in "jo,p and the covariance matrix Σ in Te, and it should be understood that P= Σ-1, The same applies to the functions 90 and hg.5; Finally, the matrix P refers to the ground truth precision matrix (= [[=--1)
Analogous to Appendix B, we start by showing that the log-likelihood ratio is bounded by the noise in the sample. The proofs of results in this Section are in Subsection C.I.
22

---

Lemma C.2. Assume P == E--1 satisfies Assumption 4.4.
For all 600 + 11) such that S denotes the zeno-coordinttes of y, and v such that [|P nsll [|P ns= s B. if the max eigenvalue (P) satisfies
Amax (P) Amin Pr) C
then for all E R we have
P S log(C)) 3B².
For the ease of stating the next Lemma, we assume that across the samples of y in the training data, at least one coordinate has sufficiently many positive samples. The proof of our theorem separately handles cases violating this assumption.
Assumption C.3. Let E (0,1) be a parameter corresponding to the failure probability of our algorithm. Then, there exists coordinate j E [d]. such that for at least n' = Olog b) samples "i....... Yig in the dataset, the j-th coordinate positive.
This is very weak assumption: if it is violated, then W = 0axk: E = 0 will achieve TV distance smaller than /
Appendix B assumed that the variance in y was 1. Since Section 4.2 considers an unknown E', we need the following Lemma show that the MLE will select precision matrix P, whose eigenvalues are reasonably bounded wrt 1
Lemma C.4. Under Assumption 4.4, C.3, consider P E Bdxd such that Amax S and Amia (P)
Amnaxe (P)
B²nk
20
Amaax Pt)
k2
Then, for all W E RRdk and all yi = <WW 24 n:)
with ||P nss 11, |1 nsl S B, we have
TW.P == n
Ww,, (V: < 0.
iE(n)
Lemma C.2 and Lemma C.4 show that the MLE will only select precision matrices P that have max eigenvalues certain range of the true precision matric p
Now, for matrices in the above eigenvalue range, we first construct geometric net over the max eigenvalue p of the precision matrix, and then cover the matrices whose max eigenvalue is smaller than p.
Lemma C.5 (2 cover). For B 1, and 0 < L < U, let A > max Vlog log 1 B² & log (,),),1)
11
Let P E--1 be the precision matrix of n. Let Ω Raxd denote the set of positive definite matrices P Iddxd with condition number k and whose maximum eigenvalue lies LL (P*), U- Amax (P*)).
Then, there exists a partition of of size
A, 1 d²
poly
such that for all 0 E Rdd and all 660" +n) Rd with |P3 nsll. || ns= S B, and each cell in the partition, one of the following holds:
for all P E 1, (g) < A or
for all P' E 1, we have (rep(()) -0. Se.
23

---

Analogous to Appendix B, we now construct a partition over W for a fixed precision matrix P, such that each cell in the partition has very small log- ligeeikl (in which case the MLE will choose it) or the log- likelihood changes slowly.
Lemma C.6 (W -et). Let nss 7s be such that
1 ns=
I B1, nsll S B2,
2slll
for B1, B2 2 O.
Let A > max (B] B2. k.)). Let P = = -r11 be the precision matrix of For fixed matrix P E Bddd whose condition number satisfies Assumption 4.4 and whose eigenvalues satisfy Amax P) E le- Amin ( (2max((*)) there exists purtition I of RRd with size
3d
polly (A. )
such that for each interval I E I. we have one of the following:
for all 70,r(y) < A, or
for all 0,0' (To) 70" P0r p()) (8)l cc
Using the above lemmas, we can show that the MLE will only pick out W, P such that they have small TV on the dataset of {x:}-
Lemma C.7. Let 21:-..;Iy, be fixed, and y; <(W',; + nh) for n, NO )² and W B with E* E Iddd satisfying Assumption 4.4 and Assumption C.3. For sufficiently large constant C>0 0,
C. (df2 kd)
kds
log
E2
samples suffice to guarantee that with high probability, the MLE W. E satisfies
Z(W Σ), (W*, Se. Lemma C.8. Let {xi be i.i.d. random variables such that x, Dzg
Let P --1 Let Xmiin Xmax be the minimum and maximun eigenvalues of P For 0 < < U. let Ω denote the following precision matrices
Q 2: PE Rddxd Amax (P)
Amin (P) S k. and Amax (P) E Amii: U Xmax]
Then, for sufficiently large constant C > O, for
(hil 52
kid d²
kdd
I )
U
n = C
log
log
have:
Pr sup d(WW, P), (W", P*)) d((W, P), (w*, .P))
> > S e S(nn")
WER
Theorem 4.5. Let Idddd denote the set of positive definite matrices with condition namber Given samples {Iz F satisfying Assumption 4.4, where x, ~ D ii..d, and y is generated according log (w. x.). Then, for sufficiently large to (7), let W, E == arg waRxwe 5.endx 1 E,
constant C > 0,
n C kd de
(kdd
skd Eō
log
E2
samples suffice to ensure that with probability 1 -8, we have
drv (W, E), (W*, -.') S c.
24

---

Proof of Theorem 4.5. First, we consider the cases violating Assumption C.3.
As n. & d' 2² log 1 if assumption C.3 is violated, then it implies that each coordinate is non-zero in 5. atmost a = /df fraction of the samples, and union bound implies that the probability of seeing non-zero vector is atmost e² /d. Hence, with high probability over the draws of the data, returning all-zeros vector always will achieve a TV distance smaller than 2ea
Let P, p --1,y-1 -ー1 Now, if Assumption C.3 holds, Lemma C.7 guarantees that the MLE has small TV on the z; observed in the dataset:
a((W, P). (W" PP)) SE.
The above result is over the finite x; observed in our dataset. To generalize it over Das Lemma C.8, which gives
d( P). (W", P*)) ((WW,)). (W"", P*)) Se.
Rescaling gives the conclusion of the Theorem.
C.1 Proofs of Appendix C.
Lemma C.2. Assume P ::--- satisfies Assumption 4.4.
For all = 610 + 11) such that S denotes the zero-coordinates of y, and n such that
[|Pss nsll, P ns & B, if the max eigenvalue Amax (P) satisfies
Amax (P) S C,
Amin (Px)
then for all E Rd, we have
70 S +332
Proof. We have
70. log
+ g0,5
ge- E- hha ho E E*.
(23)
|>]
From Lemma C.9, C.10, we have
P
90.r -0- + ha.
ho
S 90,x +
log
+ 3B2.
2
Ps
Substituting in Eqn (23), we get
PS
70.0 S ga,5
log
log
+ 3B2
2
Σ
2
Ps
As (Pg) E3g
Dige 550 - m Sug. by the matrix determinant rule, have
log|2" + log log//>>+l
This gives
y +BB
70,2 -0. + log
This gives
Amax Σn
28,4 98.5 + log
+32²
Amin
(2)
Amax (P)
-6, + log
Amin px) + 3.3..
(24)
25

---

As the matrix Eg. is positive definite, we trivially get
ge,,)(y)) -vi - 01.sr) (Esz) (vi (Ess)) 01.s=)/2 = 0.
Substituting in Eqn (24), we get
Amax P)
70 S 2
log
Amiu Po) + 3B²..
As the Lemma assumes we get
mmax (P) S Camia (P')
70.2 S 2
1og(C)++ + 3B?.
Lemma C.9. Consider the function defined in Eq (21). For the ground truth parameters 0" Σ" the function 9o- 5r satisfies
E- - 2 || 18g0
which is, with probability 1- -(())
9o S O(d).
Proof. As use are the positive valued coordinates in y, have
ys= 0z 1J55,
which gives
ge- E (v) = (ys= 0za) (233)) ( (ys- 02.)/2, |1 / /
As v/s= is Gaussian with covariance S the expected norm S which implies that with probability
1 - e -R((S)), we have
ga (v) S O((S))..
Lemma C.10. Consider y generated according to Eqn (20) by y= 0( + m), ~ (O,EE").
For all 0 Rdd E E iddd and the finction he. defined in Eqn (22), the difference ha,z(y) he x (y) satisfies
Pš Ps
hyxr(y) - ha- Sx- (y) S
log
+ P ns= 212 + 2/| PS nsl1 || + +([S)) (25)
where p =x-1 is the precision matrix of 1).
Proof. For 0 E Rdd E Idxd and P E-1, have
ha.((v) = log
exp
-11 (t 0s) (Ps) 1/2 Pss- (ys= - 0s=))1?/2).
150
< log
exp
-11 (t 0s) + (Ps) Pss- 0s.))1
JEB181
< |S|
log(2
log Ps|.
(26)
2
2
26

---

where the last step follows from the integral of Gaussian pdf. This gives sufficient upper bound on (v)) and now we will focus on lower bounding h 5:- (3).
For the coordinates of y in S", we have ys=
fg = 7/8-. Substituting in Eqn (22); we get
[ exp
hg -- (y) = log
(-11p3² (1 ffs) + (P3) 1/2 1/2 Pss 7s= || 12//2)
1
Jeso
(-11p3² (t- (6-03) 03)) + (P3) 1/2 Pss-s Ms== 122/2)
= =log
exp
1:0
Using |la + bi12 s 2a² + 22b we get
hgg (y) 2 -
1|a + log
/
exp exp(- (xp(-1113" (1 0'3) 03)1())
Igo
Set u= ps3 (t 0z) and by the change of variables formula, we get:
ho- (y) 2 (1())) 1/2 1s= 112 + log
/ uu00350
/
(P3) 1/2 exp((-luu|?);
Pg p
1 --1(PE)~112 Pss. ns== 112 + 2
log PS 1--1| + loy
exp(-Ilu|?
Ps u40350
For i E S, we have 07 + S 0. This gives
PS zu S ns = Ps u+ S -
log
exp(-llul13) 2 log
P3
50
using which we get
1 log|Ps
ha- (v) 2 - 11(Ps) - 1/2 Psse
1 M1s 1?
logl Pš| + log
exp(-1lu|())
2
P3 uuns
By another change of variables via v =
uu ns. we get
hg x (y) 2 - -1( 10ll:/p55-00 P5s=-ss=1 1| log PšI + log
p exp
(-11p5) (v + 1s 7p))
2
2 - [I(P3) ps ss=- 1
log
PS
2|
P5 3 115 11? + log
|
exp (-21 u1())
550
(I(P)) 1/2 Ps Ps _ log PS 2 PS ns
22 + O((S))
As (Et)))
)1 P5. Ps. PP5s((P)) Pt S5o. we have
-1((p))* 1/2 PS M5= 1| || 12.. ||PS!/ ms=
/ 11
which gives
ha (v) > I 12.. -|P ns- 12 log|
21113 : nsl + O(S)).
(27)
From Eqn (26)- - Eqn (27), we get
PP
ho. - haghhh----- (v) - || 1s==11 + +21 nll1 - || 13 + 2
log
+ O(SS).
(28)
PS
Lemma C.4. Under Assumption 4.4, C.3, consider P E Rdxd such that Amax (P)
S K and
Xmia
Amax (P)
k3 Rn²d
B²nk
2
12 +
Xmaxx P*)
k
Then, for all W Bd and all yı <(W x + nh) with |P ns= II. 11. nsll S B, we have
TW.P = n
Σ
PW,, (J: < 0.
iE[n]
27

---

Proof of Lemma C.4. For each W E Raxk let
0, = Wai-
From Eqn (24) in Lemma C.2, for each E [n], we have,
d
Amax ())
70, S 90
+ log
Xmiu (Pr) + +3B²,
2
d
kimax (P)
S -8,E +
log
Amax pt) + +3B²
2
Now consider
1
g0,,x(y)
2 8 01,5o) (Ess)- 01.5o).
2 11 0 112Amin (Igd):
1
2 |1 0| Amin -=212 -011 0l13>min|( (P),
2 |I 011 Amax (P)
where the second inequality comes from the eigenvalue interlacing Theorem, and the last line follows from the condition number assumption on Σ, P.
By Assumption C.3, there exist at least e2n samples for coordinate j such that (y:); > 0. Averaging E,,E, E. by Lemma A.I, we get that with high probability,
Σ lIue 0 2 o22k
which gives
1 n
90. x(1i) 5 03 k kdmax (P) Σ
4nk
Admax (P) 4nnemaxx Pa)
This gives
Amax (P)k 4nxdmax (Pa) 2
d log
Amax
fw.
Xmax >maxx(P)) +3²,
Amax (P)k
Amax (P)
4nxdmmax + d
Amax (P*) + +B2.
Completing the squares, we get
(v
Ammax (P)k
Rddn n
Tw.
kid kdd
3B².
AnvisXmax (Pt) (Pt)
k
For
Amax (P)
k3 123
2
+
X pa)
k2
k
the above inequality satisfies
7w. S O.
28

---

Lemma C.11. Assume P* := E satisfies Assumption 4.4 with condition number K.
For all 6(0" + 11) such that S denotes the zeno-coordinates of y, and yi such that ns [IP ns || s B. consider precision matrices P whose max eigenvalue Ama (P) sat-
[|P3s
isfies
Amax (P)
SC.
Amin (r))
Let A A 4max{{ log C,3B3). Then for V = (p-1)ge and Rp defined as
3
2B V
A
(29)
have
[0ge Fz. 11v 2 Rp = 78, AA
Proof of Lemma C.I.. Consider Eqn (24) in Lemma C.2. We have
70 90. log Amax P))
d
+3B²
Amin (Px)
$ P +
log C + +3B2
2
where the last inequality follows from
Amsz (P)
< C in the statement of the Lemma.
Amina Pr)
By the definition of ge.p, have
g0.p (ys- - -p.. Ps P Pssss 0g.).
We can rewrite the matrix (Pyr Ps PSS=) as
(Pso Ps.sP Pss.) ((P-1)s.)
By setting
v (P-1) )s=
we can rewrite ge.p as
1 -lus- 0g: 112 = 2
(yse - -5=.)" 0gr).
9a.P =
2
Now, as Us= = 7s= + gs, we have
9o.r 2 I|=s= + +s. - 05e 11:
1 110 Os= 112 + |lns= 1lv00 0sll |/ss1lle.
Ignoring the || 1 term, we get
1 -1003 0g-11 + || llv 1065- 0sllv-
90.P
By the Cauchy-Schward inequality and the eigenvalue interlacing theorem, have
||
||s ||2
| A (P) ||1s- 12
Inse Ilv 5 (V- ||ls==/12
mia (V)
min (P5c)
min (P-1)
29

---

By the statement of the Lemma, we have || 17s= the above inequality, we get
|| 5
Substituting
min
(P
Amax PP) | 12 VCB.
I llv
A A (PS.)
Substituting in the function 9s P. we get
90.P S - 1100 - -0s-112 + BVC - 0sllv.
Hence, for satisfying
0g - 08allv 2 Rp: : :BVC +
we get
T0 S -
In order to cover our precision matrices, we will consider subset of matrices whose entries are quantized by an interval size B: Definition C.12 (Quantized Precision Matrices). For K > 0, define Ω C IRdxd as the set of positive definite matrices with condition number For p > define the set S2p C QQ as
P [/ Op = -PEE:: Amax
For quantization size 3 0, define Ip.0 22p as:
áp.8 (P Q2p Pij ppp B), -p] 23), .P(1 23), -
B), p}-}
Lemma C.5 (E cover). For B 1, and 0 < L U. let A max 1og 1, Br & log mL) )
Let p = -n11 be the precision matrix of n. Let Ω matrices PE Bdxd with condition number n. and whose maximun eigenvalue lies in L (P*), U- Amax (ma)(("))]
gdxd denote the set of positive definite
Then, there exists a partition of of size
poly 1, 1 d²
such that for all 0 E Rdd and all y 6(0 + 7) E Rd with | nsll. | ns-ll S B, and each cell I in the partition, one of the following holds:
for all P E I, rv,r(y) < A, or
for all P, P' E I, we have (g) J0 (y)) S..
Proof. In order to construct the net over the precision matrices, will consider geometrically spaced
values of p E [L. Amin (P*), ) U >max((P))] ]. and for each p. we will construct a net over matrices that have max eigenvalue 5 p.
Now consider p > 0 that lies in the following discrete set:
(Pmin E [logg(*4)]}
This set is a geometric partition over the possible max eigenvalues that the MLE can return. For the current let Q2p follow Definition C.12. Now consider P Zp.
30

---

Constructing the interval for which 78 < -A. By Lemma C.11, for V (P-1)so, and Rp = (Pon + VA) = O(VA), we have
[0g- Gz. llv 2 Rp = 78,8 < -A
For any 0, notice that the set of matrices P satisfying |10s= fg Vlv Rp is connected (as its complement is compact). This forms the set for which N0 < A.
Constructing intervals for which heopp -0. S E. We will now construct partition over those P which satisfy ||0g- f5-llv < Rp, and show that the bog-likel changes by atmost for each cell in this partition.
10
P E Opp then each of its elements P.j e [-P, For a parameter / > that we will specify later, consider the partition l2ps of Ωpp following Definition C.12. Clearly, the size of Ω2 can be upper bounded by
2 d²
P2 Pp.0 1
We will now analyze the effect of rounding down P E S2p to its nearest element in 2,
By Claim C.13, for = 2x,3d2 we have
(1 -1-1i >)]l 011 |lt
O| S (1 7) 0113:
(30)
Consider the log-likelihood at 0, P':
1 fe.p = logl p'l + log
exp (-1lt - -01
S0,tee
We will use the LHS of Eqn (30) to show that
1
for (v)
2 log|P"| S (v) log| +
and deal with the log] P'| term later. The lower bound for the log-likelihood at P' can be obtained via analogous proof using the RHS of Eqn (30).
By the LHS of Eqn (30), we get
1 log! P'|
S0.p (y)
S log
exp (-((11)))1 - 7))1(- 013).
2
Rearranging the terms, we get
(1 (1-
(v) - log| P'l <
Iluse
0g: 112
2
(1
7) |P3 71
+ log
exp
0)s + P5 Pss- (us= 0s- )113
150
2
The non-integral term corresponds to ga.p Eqn (21), while the integral term corresponds to he. in Eqn (22).
Handling the non-integral term. we have that for
As we are only considering 0 such that I|ys= 05=111z S Rr.
of poly(A)
B = O
the non-integral term corresponds to go.P + E, which gives
(1
fa,p(y) (v) log P'| Sgo. + + log
exp
| (t
8)s PS Pss (y5- f5. 11(²)
2
150
(31)
31

---

Handling the integral.
Now we consider the integral term. Define the integral
(-11-
(1 7) | (t (+)1
11 = log
exp
150
y = 2d 2g and μr 0g- 2ps P Pss=(Vs> - 0g.).
Define the analogous integral that does have the (1 7) term in the exponential:
1 |P3 (t n)]??
T2 = log
exp
Clearly, 2 I2.
We only need consider μ such that |a S (V(Ap)) otherwise the likelihood will be smaller than A.
By Lemma C.14, for = =0 polviAA) =((movia))
we have
Handling the log-determinant term.
Now consider the log Pl term. As we are decreasing each element by atmost pp. none of the eigenvalues can increase. Moreover, as
Tr(P') Tr(P) 2 -d3p.
we can conclude that each eigenvalue decreases by at most dd3p. Also, as as as (P)(P) V [d] we can conclude that each eigenvalue satisfies
Xy(P") (, d3k).
Hence, the log-determinant satisfies
d:3x
logl P'| 2 logl Pl dlog(1 Bdk)) 2 logl Pl
2 log P| O(e) for 35 S
1- d3x
Rd
kr d2
This finally gives
he.p po < O(s)
o poly(AA) and the max radius is also O(poly(A)), we
Bounding the size of the net As 3 per entry of the precision matrix (for fixed 2pp).
have a cover of size poly(A)
Intersecting the da nets means that for each 2pp we have net of size
poly A, )
As we are considering poly(A) many 2ps, the size of the net remains the same as the above.
Claim C.13. the setting of Lemma C.5, if P Rp and P' E Kp.. is its nearest neighbor, then for 7 = 2n,dd we have
(1 (1- 0 |t 0 s (1 +1+10 7 0113
(32)
where ::= p-1 --'-''--''
Proof. Consider P E Q2 and P' kp.p such that P p A. Since P' is the rounding down of P. we have Aij E [0,
As Tr(A) pdd], and |||| S p3d, we have
Amax (A) < pdd and Amin -p3d..
32

---

This implies that when considering untruncated Gaussians with precision matrices P, P', we have that for all 8 E R²,
- | - p5d 012 - |t - 01 - 013 - pfdllt - 0112.
Since Amin (P) 2 2 2x
we have
p||C 012 S 2x|1t O
Substituting in the previous inequality, we get
||t - 01 - p3d ||t 0| 1 || 01 S | + p.d 011;
= (1 - 2x:3k) 0 2 S || OI s + 2x:3d|l - 013:
For the sake of symmetry, we will use the weaker bound of
(1 2x:3xd 0 It
S (1 +
Setting 7 2x3dd completes the proof.
Lemma C.14. Consider bounded mean vector with ||a|| S ar and precision matrix P with max
eigenvalue p and condition number K.
For o min
apt/2/8721 क } have
(-1 || 3 (1- (1-w)))) S - log / exp (- (1 (1-))()
(1- (1-1) 2
log
exp
$500
150
Proof of Lemma C.14. Wlog, consider μ 2 0. The case where the entries are possibly negative
follow similar proof.
Define the integral on the LHS and RHS of the Lemma statement by I and Ig respectively.
By a change of variables, we set 1' = vT 7(t 14) + in I, to get
1
(1 J exp (-211120 (1'('' (t'-)))33
I log VI- log
Since 1, we have (1 - /1 7)1u < m. Substituting in 4,, and for 7 O(s), we get
< log -1-7 + log / exp
(-11 (L'- 160--1) w)lf)
USST
(- - w)}pp
< (e)) + log
exp
The integrating set in the above inequality can be split into two parts: over the negative orthant (which is exactly to e and another over the shell
C== it'
S Th \ 1t' < S0.
This gives
1 s 0(s) + log 6 L exp (-H -(-)) -
In the above inequality, let e denote the integral over the shell C. We will now show that I3 satisfies to eet2.
Let fx) denote the Gaussian density with mean a and precision matrix P.
For a subset of co-ordinates S S [d], S + 0, and t E IRd, let x4, x_ E [Rd be such that
7p4 if E S, i S,
x_)((1) = -
if S, 22 if $ S.
(1)
t;
33

---

By the monotonicity of the Gaussian density, the integral over the shell C' can be upper bounded by breaking up into sum integrals over lime-dieensio strips, where for fixed subset [d]. the variables Ige are integrated over (-o0, (=o0, while the variables in S are fixed to yus.-
This gives
e 5
Σ
((x+,)) m
YP: SE
SC14 bie Syuge
Σ
((+15)
SCId]
Aaee Stuse
I
(ra)*
max
f(4+.s)
SC SCId:|S|=
Srgosrnn Srine
By Claim C.15, for any S, and y O min =
mvpal } each summand satisfies
f(x+,s) S sx)
Furthermore, for any S S [d], we have
Jos Stse [( 1(m 18
S
This gives
e
2 s 3 ifed
Rescaling + 3d completes the proof.
Claim C.15. Let be the Gaussian density with mean μ E [0, ald and precision matrix P Rdxd with max eigenvalue and condition number k.
Let 7 0 (min avpd -5te)) }).
For any subset of co-ordinates S [d] # 0. and Rd, let
T4, x- E TRd be such that
7H4
ifi S ifi $ S,
- if S. ifi S.
x1)
x1
ti
t1
we have
f(x4) < 2f(x))
Proof. WLOG, let S be contiguous set such that we can separate the coordinates of x and x into disjoint sets. For the coordinates belonging to S, let μı denote the coordinates of μu belonging to μ. and uĄ- the coordinates not belonging to S (similarly for ts and tg=).
Taking the logarithm both sides of the claimed inequality, want to show that
1 p
74 us
||
2
|t
-us 14s
||
+ log 2
2 1g- - ps
tg
Mse
Let and b denote the vectors whose norms correspond to the log-densities in the claimed inequality, and let 8 = b.
This gives
- Hts(1 - -7) 1g 1r80
Ms + 2) t.gr - 14.0
- +1)
b b= p!
p!
8 = a b= P!
0ge
34

---

We want to show that
- _1bb11 _ --211a1 ||a|12 + log2.
+ (0,b) + [1811 I log 2.
(33)
As ||P]| and |/ a, have
|1012 S p(a² p(a2 1 )²
For 7 = ( (TVTT) we get
| 1
2 log
(34)
Similarly, consider the inner product (6, in Eqn (33). By the trace trick, we get
(6 = Tr(AP),
where
us(1 - 7) tge pAse
[ [-
187 (2 + 1){²
A
Og=
Notice that the diagonal elements of A are all non-negative. This implies that all singular values are non-negative. The trace of is
Tr(A) ||ss||l (1)))(((111>>1-11 (1++
Hence, by Von Neumann's 's trace inequality, we get
(ö, b) S Tr(A)T((P) < ||s -2)7 ( =1 pd.
For y = 0 (0-1ssp1pp (=1s)ppd)
this gives
1 log 2.
(8, < 2
(35)
Substituting Eqn (34) and Eqn (35) in Eqn (33) completes the proof.
Lemma C.6 (W-net), Let msss ns be such that
|| ns= < B1, 1P' nsll
2 S B2,
for B1, B2 2 O. Let A max B37 B2, poly(C, Let P = == 5--1 be the precision matrix of 17. For fixed matrix P Rdddd whose condition number satisfies Assumption 4.4 and whose eigenvalues satisfy Xmaze (P) le- 24 Amin (P*), (omax((*)) there exists partition of Red with size
poly (A.-) )
3d
such that for each interval I E I, we have one of the following:
for all 0 70) - or
for all 0,0' (ro, " pp)) S.
35

---

Proof of Lemma C.6. Recall that the log- log-likelihood ratio va can be decomposed into the difference of two terms that depend on
PP PM
p 2
log
p(. go- pp- (v) + hg. ha- (v).
Without loss of generality, consider the net for the first coordinate 0,. The final net will be the intersection of the per-coordinate nets.
We will construct three partitions: the first is Ia,0 for h when y1 0. the second is is Iv for h when y1 > O, and the last is Ig for when y1 > 0. The final partition will be the intersection of these partitions.
Case 1: Net over h, 81 = O.
As V/ = 0, we have E S. For A E Rd, we have
hg.r(u) = log
exp
1P3 (t 0s) + (Ps) Pss- (ys- - 0g.) 11/22
150
By Claim C.16, 0 2 0
VCnd
then the log-likelihood is smaller than AA
P1
Now, consider 0, < 0(( VCKA
Let 0' = + + ae1 for a > 0. As h is monotonically decreasing per
Pı
coordinate, 0, < 0j = her hor p. We would like now upper bound hep in terms of her p-
Let
:= + (Ps) Pss- (ys= 0ge); μ' :-80g + (Ps) -1 Pss (ys- Ag-))
In the function hg, break the integrating set into two domains: one where a is small,
Ω { E R
| (t Aill sr]:
and another where it is large:
22 ER RS
|P3 (t 1²) > r]
for some > 0 that we will specify later.
Let I and Ig denote the integrals over Ωi and 9g respectively. In corresponds to the tail of an unnormalized Gaussian distribution, and hence we have
In + / J (1
hg.p(v) = log
21 P5 le-2
where 12 $ (2iT)
We can simplify Iz be comparing PP| to P
1 < (2T)
P5 P-1 1/2
PS px-1/2 1/2
-r²
< (2T) 18
{mmn(p)
Ninax
18|
P3 1--1/2 1/2
18|
< (2iT)
Ne
5
e
By Lemma 10, we have
(2th)
[8]
P
<
No (h
36

---

As we are only consider 0' such that hg- (v) - A < heg p()), for
y² = O(dlog + A + log 1 ) O(A),
we have
12 cehor,ll))
Subsituting in ho, py)), we get
hv,r(u) I log (chor.ll) +
[ I50, x-p(-1P33 (t -,)l2//2)
Now consider the integral I Jigonen cxp (-11P3 (t- /21
By Claim C.17, O2 defined for & bounded by r, and μ μ' αεj, we have
I exp (2opir + =a²p²) 11
where 1 =
exp
(- |P3 (t 22)11/22) s scoorplu))
150,EE
Substituting in the expression for hepp, we get
ho,p(v) S log (,v,,(()) (e exp (2ap1r a² a²pi))
As log(e + t S + for 2 0, we have
(v) he p(y) +E 2apir + a²pi.
Setting a = O( O(pp)) we get
he ho) S hgr pV() + 25.
This shows that h changes by at most & for the considered net. We need to defined the other end
point for the net. By a similar argument to the positive end point, 0 -0 ( (CwloR()) ( the
log-likelihood ratio changes by most until 0 -C.
As we are only trying to cover 0 such that [0_| s 00( /CCAA) ), this has size
VCRA Pia
=0
VCKA Pir
A
P1
Case 2: Net over h, y > O. A similar argument to Case 1 works here as well.
Case 3: Net over 9s 31 0. By Lemma C. 10 0. Rí for
R1 = O(VA),
then
90.P 90- P < AA
Now consider 0 such that
10, - 01 R,
and 0, 0' such that 0 - 0' = aε1-
37

---

The difference in gor is
go(y) - go (y) = -- (Zise)
- 0(/e)) (00g
=1103= -0s- 10.1 + =1103- - 0' 1g0
The second and third terms in the RHS bounded by observing that
20 8¹ - 0 S 2R1 = O(v O(V S
and hence we get
2 100 - 05= 112. + 111033 -0's 11. S SO(VA)a
Now, for the first term in the RHS, we have
Bi
BIVE Amax (P*)
1lpg B, |
S
1
Aain (P*)
This further implies that
BIVE
T (Ess)) (0s: -0(s))
(
VPia poly(A)a:
Amax (Pt)
Setting
a = 0 (pol((A))
we get
(go(y) - go (v)l S d.
As we are covering a set of size R₁ using a grid size of a the size of this partition is
0 Rí
(Aly
a
E
Claim C.16. In the setting of Lemma C.6, we have Amax (P) & CAmax(P*) Let p1 denote the first diagonal element of P.
If 01 2 O
CCKA pt
then the function ha.p is such that
he.p hgg P A.
Proof of Claim 1.16. Recall that the function hepp is defined as:
[ exp(-11P) (1 - 0s) + (Ps) 11/2 (1PPss--sss )1/2)11 /2)
hg. log
150
Consider the term | (t 0s) + (Ps) -1s) Ps5- (Us- 0g-))l- By the triangle inequality, have
| (P + (Ps) 11/2 1/2 PsS (ys- - 0g=)]l
1/2
(f's0 )1 - -1|P5 Pss- (ys- 03-))l. 21 (t- 08s) + (Ps) s-. (f's 03)))l VCKA
(t- 0s) +
38

---

where the last inequality follows as
CC B I VCKA.
PP3s : Pss-(ys- 03->)l = -1P5 Pss (ns= s ||3elIllss
Vini
Similarly, the function go, only considers 0 such that | (0s- g S VVRA ( (othewiss, the log-likelihood ratio is smaller than A by virtue of pa irrespective of hg, For these 0, we have
| (t - 0s) + (1/) Pss- (0g= 0s=)1l
1/2
2 1P3 (t - 0s)l VCRA,
which gives
[ (t - 0s) + 1/2 P/s 0 05:)l 2 P (t 00)1l 2VCKA.
Hence, if 01 2 0 /CRAA then we have
p1
|| (t 0s) + (Ps) 1/2 Pss (yss= 8g-)1 20(VCKA) VE50,
and hence the Gaussian integral is at most (2T) //// P5 } e (((OA))
By Lemma C.10, we have hg-
2 1 log P31 - (A), which gives
PS
hv, ho-,p- (y)
<
log
((CKA)
2
Psl
d
Amax
log
(((RA)) < (Allg x) ((CAA) -S((A))).
2
Xmin(P)
This gives a contiguous interval over 0, for which y0 -A
Claim C.17. In the setting of Lemma C.6, let pe, p¹ be such that p - H = aE1
Then, for all such that
[| (t - 11ll Sr.
and pı = PLU. we have
| (1-11)1 2- - 20pir - a²pi + [P (1 - (t-)
Proof of Claim C.17. Consider the term | (t 12) Adding and subtracting |P (t - / we get
| (t 11ll = [|2] (t pull || - w/)]| || (t- n')1
(P} (21 n² (1), P3 (1' n)) + 113 -1-)
(P3 (2t 2p- (μl 1)), (()--))++10 (t- (1=13)
2(P3 (t 1)) P. (1l - -1)) -1 ( + 11p
(t))
As J n/ a61, we have
[1 (1-11)11 a²p3
By the Cauchy- inequality, and since μ - 1t' = aεe, the inner product can be lower bounded Substituting, we get
2(p (t - n). P3 (e' - -1)) 2 -2| (t - 1 |||| P (4' - +ill 2 -2ap1r.
|P 11)1> -2op17 -app | (1 -1/1112
This completes the proof.
39

---

Lemma C.18. Following Definition C.12 let U2 be the set of precision matrices with condition number K satisfying Amax 12 pl. and let 2p be the quantized net with quantization level B.
For any P Aps let P Pp be its element-wie rounding down. Then, for any μ E R., we have drv(N(e: P), PJ) S Old
(36)
Proof of Lemma C.18. Let Σ = p-1 and Σ = p-1
By Theorem 1.1 [16], the TV between Gaussians with the same mean is
drv (N) o min Σ { (
where &, are the eigenvalues of ΣーΣΣー la-
We can convert the bound on the eigenvalues to the Frobenius norm of Σ-'Σ - Ia:
Σ + 1 -
LallF.
Recall that the rounding down per entry of P. Hence,
ğーンΣ Ia = (E-1 [wij)E - Id. where 0 $ Vij < Bp.
Taking the Frobenius norm, we get
- IallF = ||
d
S (dBp) (E)) = (d3pp)
Pmiin (P)
dk
S (dBp)
2d Br.
Pmax (P)
where the first inequality follows as each element of v is at most 3p, the second inequality follows as P has condition number k, and the third follows as P E Stp = Prnax (P) 2 P-
This completes the proof.
Lemma C.7. Let 21...., In be fixed, and y; <(W*;; v, + m)) for N'0, E*), and W e gaxk with E* E RRdxd satisfying Assumption 4.4 and Assumption C.3. For a sufficiently large constant C>0
C (cf + kd)
kdk
log
62
samples suffice guarantee that with high probability, the MLE W. E satisfies
ā( (W Σ), (W*
(W*, Eン) Se.
Proof of Lemma C.7. For any W Rd Σ dxd and sample (x4, y:), let Pt, w.y() be the conditional distribution of = <(W> + n), and let %.w.x be the lig-likelihood ratio between (W, E) and (W*, Σ*) on this sample:
(v. == log P. ax)) P.w- x (y xx)
Then
El (l),wx()) - -KI(P,. x (y xx) (P).we xx)).
40

---

Concentration. 0 ( log }).
From Lemma B.1, we see that if (rw'( ,"), (W,E) 2 then for n 2
E²
TWE = Y2
w.w < 2 2
(37)
with probability
Of course, whenever 7W < O, the likelihood under W Σ" is larger than the likelihood under W, Σ.
Thus, for each fixed W, with ((W 2²), (W, })} 2 é, maximizing likelihood would prefer W* W, 2 with probability
if ( log }
Nothing above specific to our ReLU-based distribution. But to extend to the MLE over all W, Σ, need to build net using properties of our distribution.
Building a net. First, for a given sample yi. let St be the set of coordinates of y that are zero, and S be its complement. Then, with high probability,
IPS (1:)s.ll.1 (w:)s. ll s B O(Vndlogg)) V [n],
where P E--1, and Pg. Ps= are the block matrices in P*
Supposing the above event happens, we will construct a net over the precision matrices P = Σ-1 Note that mapping.
only considering matrices with bounded condition number, this is bijective
Net over Σ-1. By Lemma C.4, any precision matrix P= =- satisfying Assumption 4.4 and whose max eigenvalue satisfies
Amax (P) 2 U. Amax PP*),
for U 0 dn
dd logn
will have 9w,P-1 0, irrespective of W.
82
Similarly, by Lemma C.2, any precision matrix satisfying Assumption 4.4 and whose max eigenvalue satisfies
Amax (P) < L- Amin (P')
for 7. -0 has 7, S. for all [n], and hence its average Fw.p-1 is also < 0.
This shows that for all precision matrices P whose max eigenvalue is extremely small / large when compared to the min / max eigenvalues of P* has
Fw,P-1 < 0,
irrespective of W, and the MLE, which has non-negative 7, will never pick these P.
Let A (nly(n, d, K, 1) be large enough such that A > loglog(U + B²), and such that meets the requirements of Lemma C.5 and Lemma C.6.
Then, by Lemma C.5 with U poly(d, x, n) and log( }.) poly(K, n), there exists parti- tion P of precision matrices whose max- eigeevaee lies in [L Amax (P*), Amax((") into
(poly(d, K, n, 2)) cells, such that for each cell I P. and P, p' E I, the following holds for all i [r]] and W E gdxk.
haw,)(()) N...r" (1:) 16
(38)
or (w.) A.
Using Lemma C.18, we also have that for all W,
2²
dry (rw, (W, P')) <
(39)
16
41

---

We can choose a net N consisting of precision matrices from each cell in P. This net has size
dkn
N| S log
This gives sufficient net over the precision matrices.
Now we will construct a net over W for each precision matrix in the net.
Wenet. Now, for each P Nr. by Lemma C.6, for each [n]. there exists a partition Pp, of Rd into (poly k, Ki n, ) cells such that for each cell T E Pp,e and W, W E I, one of the following holds:
(u,,,(uss) - Ne.,, s(us) 1 8²
(40)
16
or % Tw, < A.
Let W be the j-th row of W. The individual partitions P on (xz, Wj) induce a partition Pp, on R where W,, Wi lie in the same cell of Pr.ay if (ara, W3) and (z,, W3) in the same cell of Pp. for all E [n]. Since Pr.. is defined by n sets of (poly (d, k n, 2)) parallel hyperplanes in Re the number of cells in Pp..." is
poly d, di 1))²
K,
As there are d rows in W, we can intersect Pprss over j E [d], which induces poly k, ks n, ) cells in R choose a net Np to contain, for each cell in Njeja Pp.,, the W in cell maximizing drv( P*), (W, P)). This has size
kdknn
log Nol S kd kd
E
Proving MLE works. By (37), for 0 that
log Ade
we have with high probability
E² Tw.P S
2' 5
for all P N and for all W E Ns with drv (W*,P").(NM 2 Suppose that both this happens, and
| St (1hss.1llP (1)ss.1 s B =B= O0V=Oodn n) Vi [n].
We claim that the MLE W, EL must have dry (W",,")) (W, {)) < e.c.
Consider any W E dd and P E Rdxd with drv ((W*, P*), (W, P)) 2 H. Using our net on precision matrices,
find P N such that
drv (WW P)). Eqn (39), we have drv ((W, P), (W, P)) 16' which gives
drv ((W", P*), (W, 2 drv ((W", P"),
Recall that we are only currently considering W, P such that drv ((W* P*), (W, P)) 2 17 By
drv((W", P*), (W, E
16 16 2
Now, for this P, we can find W Ny. and by our choice of Ny. we know that
drv((W', P"), (W,P)) 2 drv (Pn"("")) (W, (W,P)) 25,
42

---

and by (37), we have w p S T
Now we consider two cases. In the first case, there exists i with pw,) < -A Then
A + /2 <.
Tw.P Σ (.w..(buss
Otherwise, by Eqn (38) and Eqn (40), we have
Ww.r F Tw + / Tw.p/.
Tw.P S
W.
E²
$
+ max T,W Fe.. + max J.,W.P - Fe...r
2
E²
<.
2
16
16
In either case, Tw.r 0 and the likelihood under w* exceeds that under w. Hence the MLE Φ must have drv (ww, w) & 17 Rescaling gives the conclusion of the Lemma.
16
Lemma C.8. Let {ai be i.idd random variables such that I, ~ Dz- Let p = = Let Xmnin Xiaxx be the minimum and maximum eigenvalues of P For 0 < I. < U. let Q denote the following set of precision matrices
Amnax (P)
PeRd
Amin (P) S and Xmax (P) [L Amiua U Xmaxx
Then, for sufficiently large constant O, and
n C. kd d2
kdk
U log
I. )
log
g2
we have:
(W", PP)) d((W, (w", PP')| (W*,,"))
< e (((n))
Pr Bi
sup WERdxi,Per PER
Proof of Lemma C.8. For P P- and p = -t-1 let
f(W,P) == d((W, E),
and
fn (W.,P): (W*, ""),)")> 1 ni Σ
drv (ww.p(plw)),.pppmmmc....l (u (vlkx))
Since the function is bounded, for any fixed W, P, the Chernoff bound gives
Pr(]fa f(W, a] S e 2nna
(41)
for any 0. The challenge lies in constructing net to be able union bound over R without assuming any bound on W or the covariate x. As before, we do so by constructing a "ghost" sample, symmetrizing, and constructing
based these samples.
Ghost sample. First, we construct a "ghost" dataset D' consisting of n fresh samples IID samples (z()ie(m) of D.. This gives another metric
PW :- "(::= (W", ""''
= pww. (ylx()))
Similar to the proof in Lemma 4.3, is sufficient to consider the difference between fn (W, P) and f% (W, P) ie.,
Pr (
2Pr
sup fn (W,, P) (.(WP)) e/2
(42)
W.P
W.P
43

---

Symmetrization. Since D and D'2 each have independent samples, we could instead draw the datasets by first sampling 2n elements 21...... 222n from D,, then randomly partition this sample into two equal datasets. Let 8;
{+1] so = 1 if lies in D' and -1 if it lies in Dz. Then
2n Σ
fa( - FM (W,
(r pw- pw-,p- (ylax))
For fixed W, P and 2i...... 222 the random variables (s1,..., $2n) are permutation distribution, so negatively associated. Then the variables &; drv (pw.((yl (y) [z),, . Pw- (ylz;)) are monotone
functions of 8; also negatively associated. They also bounded in [-1, 1]. Hence apply a Chernoff bound:
(WW. > <6=E1111
(43)
for any fixed W.P. P.
Constructing net. We will first construct net over the precision matrices (independent of W), and then for each element in the P-net, we will construct net over W.
Net over Σ-1, In the following, Amax denotes max eigenvalue of a matrix P. Amia (P) denotes the min eigenvalue, and (P() denotes the i-th eigenvalue, in decreasing order.
In order construct the over the precision matrices, will consider geometrically spaced values of À E [L. Amin ( (P*), ), >max((") and for each A, we will construct a net over matrices that have max eigenvalue X.
Now consider À > 0 that lies in the following discrete set:
{mmin (P* )2' E [log2(x4)1}
This set is a geometric partition over the possible max eigenvalues that the MLE can return.
Following definition C.12, let Ω2 denote the subset of positive definite matrices in Rdxd that have condition number and max-e ein-eigenvaluee in 2 A]. Similarly, following Definition C.12, let 2x2s denote the gridded version of Qx, where entries in the matrix are multiples of X3.
For any P E f2,, let P E Six, be the matrix obtained by rounding down every element in P.
By the Data Processing Inequality, for any Bdxk, we have
drv (pw.P(ule),Pww.(lll)))) Pw.p(vlæ)) drv(WWWW:
By Lemma C.18, upper bound the RHS of the above incquality by
drv PN, P)) S 3id)
Setting
8 8- 0 E
(-
d22
have partition of size ( per À such that:
pw.F(ulz)) drv (ww =
0()).
We will now construct net over W, so to show Eqn (43) for all W, P.
Wenet. By repeated triangle inequalities, we have
(W, fa ()) < (W, - f.W P) + faW - (.,,,)) Using the cover over P. the first and last term on the RHS are O(E). This gives
f... f.WW,))
[w, P) (WW,W P)I s 0(e) + [., P) S.(W, P)
(44)
44

---

For fixed W, P. we will have (43) using a Chernoff bound. Since P is already finite, we will now construct net over W for each P. is sufficient to bound drv (wwp((yaa) Pwr, Pwr,byyla;)) as the triangle inequality implies that this is larger than the RHS above. We want, for any W, W" in a cell,
ddr (Pw. (y)rz)), pw- (V--p-(()zz)) drv (Pw plyl)s), pw pww.p---ee (y(o,)) s O(e). for all [2m]. It is also sufficient to bound drv (Pw, (z)) Pwr, ((y,)))) as the triangle inequality implies that this is larger than the left hand side above.
Lemma C.19 implies that we can find of
d 2372
/ log (
per row of W such that for any W, W in
cell, either
drv (Pw. (pw. p. 2 drv (P (ly (r)), pw. (15lzz) 2 -
which implies
drv drv(y.pbuula.... Pwr ((y(2,)) se
or
drv (Pw, ((yl);)) S Σ drv (Pw (yy kzz Pw. ((Ur|z;)) S s/dd
Therefore, for each i regardless of the value of Wja 24 there most O ( d ing hyperplanes.
2/2 V log [og(?2) 2d)
partition-
We then take the intersection of all 2n partitions (for each data point 2,). The cells of this partition are defined by 2n sets of /2/2
d
/log(?)) parallel hyperplanes. Since & E R& the number of
cells is at most o (( nd (372
X
2d log
Hence the total number of cells for d rows most o (( (and (1 log
dk
2d
Putting everything together. Finally, for any W E Rd let W E Np. be the representative of its cell. Recall that each representative P of P induces different cover Nş over W. Let N be the net over the precision matrices P.
By definition of the cells,
|dzv (Pw,plyla,) Pw- (-----(()x))) drv drv pwwp)) (x)l))))) < O(e).
(w(+:))
for all E [2m]. Thus
(WWW,P)--s(WW) - (I.(W, (ICKP) (17))Jana Sn(W, (W) O(e).
and so
Pr
sup
P) - -W,, el
WeRRxk Pered
< Pr max WEN (W, - P)]
< No
As there are log v partitions over P (corresponding to the maximum possible eigenvalue of P).
each with (0 (0(dx)) of elements, we have
d2
U
log NN| S log
log log
L
45

---

and each cover Np over W has size
d
2dl
)
log NNl = 2kdlog
23/2 V log
This implies that
kd dl
kdk
U )
C.
log
log
g2
L
suffices for
Pr(sup W.P
e) <e
<e-leen A((
Lemma C.19. yety- = 6(p + no-) where o" are fixed, and Vp.o = o(p + no). We partition the space of u s.t. for μ. pl in a cell. either
drv dTv(Pn (v (v). Pae P (w)) S e/2d.
drv Pp (V). Pu .r (1)) 2 - and drv(Pw (w)) Pur ar (1)) 2 1
Then the number of cells is at most O 23/2 (1 [/lo((?)))
Proof. In one dimension
drv (1) Pa- . (v)) = drv (Pen,co (1)) Pept, ,co (1))
where c is a constant. So, we can assume WLOG that o" The number of cells in the grid only depends a/o".
Now, we show that, regardless of the value of μ² we only need to make grid on segment of length most max(o, /log log (2og/2/e)). This is because for any i outside the ranges specified below the
drv (P (V).Pp Pp (y)) 2 -.
If 1r I -Voog(2d/c) and for any P such that / > oy /lgg(2//c) the (Pv(Dyrse - Py), (2)) 2 the difference in the probabilities at 0 which is bigger than 1-
If 2 4º 2 -Vlg((2//e) and for any μ s.t. 2 max(a, 1) (lo/o//////) the drv(Pw's . (y), (y)) is the same as in the linear case and since, μ μ Z max(o, 1) /log(2//c) c), the drv (Pw (V). (y)) 2 1 -ec.
If S 4¹* < Vlog(2d/e). for any μ s.t. P p N max(o, log 2d)c), the drv (Py or (V). (p).Pp.))))
-6
If n² 2 Mlg(2d/e) then for any s.t. - n¹ 2 max (a, 1) (2d/e) using the same argument above, we have, the dry (Prr or (y), Pr. (y) true for j s.t. -a -loggg((2/ S S p² - max(o, 1) / log(2d/e) Therefore, in this case, we have an additional cell.
Moreover, this is also
In addition the above, for any p. < - V log(2d/e). the dry (y). c/2d since both Yu.o Vp'.o are only non-zer with probability at most e/2d. Therefore, for all the above cases, we only need to partition a segment of length at most 3 max(o, 1) /lo(2d/cc
Moreover, for sufficiently small we can do better. We only need to partition space of a /lg////2// e. This primarily because when a sufficiently small, for any l in the linear case we have that drv (p Py (v)) > 1 - c.
46

---

It is easy to see that drv (Pp,o (V). (P).
2 drv (pv(po.)()) (o)). (o..p..))))Po.
The PDFs of (0, o)) and
log log(1/a²) 1/021 To show that drv (po. (v), Po, (1)) 2 6, it is (0, 1) intersect at tov
sufficient to show that
1 20(-11=//o) 2 - and 1 1=||=> c,
where (x) is the CDF of the standard normal distribution. By using classical bounds on (z), we have that
lor 2
2(-1x//o) S exp x² /20
exp
12//a
10///0
which is S c/2if 2 c/2. And,
[x|| exp
22/2
$ ((-|>>)) 2
x² +1
which is 2 (1 c)
When μ² S - (2g(2 the same argument as above shows that if drv (P Pu. consider the case where n 2 -loog22d/e
a /lg log((d/cc then the Pu.o (y)) 2 the difference the probabilities at which is bigger than 1 - e. We
Since, when is small, for any μ in the linear case the TV distance is large it is sufficient to have large enough so that the intersection of the PDFs are positive and we are in the linear case.
The point of intersection assuming o" = 1 is given by
/220222 + (m1 22)2/02 + (22 1) log(o²)
which is positive whenever
P2 2 ov log(1/0² + př 2 o / /lo//2//e.
For the rest of the space, we partition μ E I for any p. n in cell,
|1 - n'l = ac/2d.
This implies that for any μ. pl in cell, either,
drv(Pp-(W) (v)) 5e/2d
or
drv (Pu Pu-.o-())) 2 - and drv (pr, (2), ()))).)))) Pu- o (2)) 2 21c
Then the number of cells is the max of Oldv/oo((2//e)/) (when small) or Old (oog(d////))) /// (when large).
D Proof of composition of layers
Proof. We can use the triangle inequality to compose our single layer guarantees. Suppose, for layer j and j + we have
(xv' c/2 and
CoroWWREEE 1)), (W + +;))) S 5/2
then,
drv(o(WW) M + m.), +
ddrv (O X, n1) (Wi MLE + 1;))
+drv(o(Wi / + n)), <(W'X + +7))
SE where we use the fact that drv J(Y) & dxv(
47

---

(0.
8, Lap (0
0.00 010. 41
20.Dxa ((s. E), (wrr
24
15
Pineker TV Upper Bound
20"
20*
(a) Total Variation Upper Bound
(b) Total Variation vs, n Different D.
Figure 4: (a) Plots Pinsker's upper bound on the TV distance d gets large. We set 2 La and
W = Lax1, thus setting input dimension & = 1. n = 5000 samples are taken. As we might expect, the upper bound is increasing in d. each point is determined by 2000 samples. (b) Plot of TV for additional distributions of z. All three distributions follow roughly the same trend, each point is determined by 2500 samples.
E Simulations
E.1
Additional Simulations
In this section, we provide additional simulations to supplement some of the discussion in Section 5.
E.2
Simulation Details
E.2.1
Figure 2
In these experiment, we set d = 1, and plot the results for various values of the number of samples in Figure and various values of the input dimension & in Figure 2b. For each plot, we fix the true o² = 1 and the w 1x In each case the MLE is solved via gradient descent with backtracking line search, and we check a first order condition V Ww.a log Pw..((y x))]|² < = -3 as the exit condition. We verify that increasing decreasing 5 by one order of magnitude makes no difference to the Figure.
The expected total variation distance for the two distributions is calculated as follows. We sample x according to the true distribution (in this case either Laplace or Normal). Then we compute drv x)), Pmrr (y x)) via the MATLAB integral function which uses vectorized adaptive quadrature. We repeat this total of 100 times and take the average to compute our expected total find an MLE, and then compute its average total variation distance. Lines indicate the average of these experiments, and the error bars, (not easily visible due to their size) indicates one standard error.
variation. We then repeat the entire process 2000 times, each time optimizing
E.2.2 Figure 3
In these experiments fix d 3 to retain reasonable complexity for computing the TV distance, and take input dimension A = with deterministic x in order to compare with [35]. In Figure 3a we 10000.
fix E Ia and take let W blax1, where b will vary across our experiments. We In Figure 3b we n 5000 and adjust E such that one diagonal entry is 22/2, and the other is -- 1/2 making the total condition number
In both of these experiments, we restrict the MLE computation to be over diagonal Σ only. This not because computation of the MLE is too difficult, but rather because computing the TV distance is greatly simplified this case. The algorithm of Wu al. hence modified to use the knowledge that the output must be diagonal. This is simply done, because the procedure of Wu et al. essentially first
48

---

estimates the diagonal entries of the matrix as if it were diagonal and then computes the correlations. Removing this second phase allows to achieve our goal.
Since x is deterministic, we do not need to consider randommess in computing the expected TV distance, though other challenges remain. Since our distribution is degenerate, must be very careful in computing the TV distance in higher dimensions. Specifically, in the diagonal case, the TV may be written as:
drv ( Σ), (W", 2²)
1
Pw,s(y 2) - P.-,E- 2)) dy
Rd
11
Pw (3) x) II pw- E- (yi x) dy.
where is the 7th element of y. Though at first glace it seems that this is single high-dimenssooal integral, the reality that due to the truncation, the probability mass on the boundary of the non- negative orthant cone R has complex structure that cannot be ignored. Instead we perform series of integrals of continuous bounded functions, which are much more amenable to Monte-Carlo integration techniques:
drv (W, E), (W*, (W",E") ".),
Σ Il
Pw ( x) II (E(S))
+ (E
II LES'
pw- - (I
(x)
II
E
dyss.
S'22
20
iES
*E(S")
(45)
Essentially, for each possible support of y, S', we integrate over the absolute deviation in those coordinates.
E.2.3 Figure 4
In Figure 4a, plot upper bounds for the TV distance of the MLE as the output dimension grows. We set the input dimension = with deterministic x and fix the number samples 5000. To estimate the KL divergence, repeatedly sample y according to the true distribution, and compute the empirical average log-likelihood ratio.
In Figure 4b we fix the output dimension d = and input dimension & = 5, and compute the TV over a range of values of n. In addition to x sampled i.idd from the Normal and Laplace distributions, we also plot performance with Normal mixture, where with probability 0.01, the normal distribution has mean shifted by 100. We observe, as our theory suggests, that in all cases, there is only very minor differences in the expected TV distance.
Note that in the case where æ is distributed according optimization may become very challenging, and in the plot above, we have omitted some of the instances where optimization failed due to lack of smoothness in the objective and numerical imprecision. Omitting these point may lead to a small systematic error in the figure, which may explain why lower than the other plots. In practice, for a fixed optimization budget, we may observe meaningful differences in TV for different distributions of x, since computing the MLE becomes more challenging for more complex heavy-tailed distributions.
Normal mixture, we observe that the
The Likelihood Function
In this section, we discuss the likelihood function, proving log-concavity, as well as discussing computational challenges.
F1 One Dimensional Case
In this section, we consider the case where the output dimension d 1, with some a² and some W* E LL and describe how to compute the likelihood function. We defer the proof of the
49

---

log-con concavity to the follwing section, which covers the more general case with d 2 1 When we re-parameterize as u -W/o,, 1/a, the likelihood function is written as:
fu,) 2
1
Σ fu u. x;)² + log(t) + Σ log
2.)
(46)
where in this case we let S = {i y/ = 0}. where yi is the 7th sample in the set {y/- Zj 1i)l Note this is distinct from how we define S and 5 in the multidimensional case, where corresponds the zero and non-zero coordinates of single sample yi. The case of d >> 0 with uncorrelated 1) follows similar approach.
Numerical concerns. In (46), the term log ( m2) presents some numerical concerns when 22 0 if we naively compute (f-u-x;; and then take the logarithm. Instead compute it from the mills ratio m(x) [27]. defined to be the ratio of the standard normal pdf and the complementary cdf. The mills ratio is easily computed, with many well-known expansions, see for example, [13]. Then we can write:
1
log 4 = - log (x) (2g(
- x². > O.
2
Since mxx) changes relatively slowly in compared to #(-z), this greatly improves numerical stability.
F.2 Multidimensional Case
In the multi-dimensional case, we will generally use the more standard natural parameters:
U E- V --
2
Note that in the one-dimensional case, could have also use the natural parameters, but due the truncation structure, the parameters we used make the computation simpler, in a way that does not apply the multidimensional case. Also note that here we are considering fixed x and writing v as a vector. In full generality, we should take V = - - however, this is simple extension which we omit here for readability. It turns out that density log-concave in these natural parameters:
Lemma F.1. The log- likelihoodd function in Eqn (8) is concave in the natural parameter space.
Proof. First, let's write the un-truncated density in terms of these parameters:
Sw.z(ylæ)
exp
1 2 (y Wx) 1 (y Wx) log 2x
1
2
(47)
2
1 //²² M 'y x++x"1 W ي y x² WT -ー
exp
Wx -
log |
(48)
1 1 Uy oJ u T - v
1 2
exp
log (2T))
(49)
(50)
Thus, the untrucated conditional density can be written as:
fu.(()) = exp 1 Toy A(U,0))
where A(U, v) is the cumulant function (note this is distinct from the related cumulant generating function). A well known result that A is jointly convex in its arguments, U and v. Taking logs and using this fact, shows us that (u) is log-concave in U, u.
Our truncated density is simply:
(u) = 19
For any log-concave density f(x), integration over a convex subset of the coordinates preserves log-concavity ([9), Example 3.42-3.44). Thus the objective is log-concave.
50

---

Then the likelihood function at U, can be rewritten as
v²u
Ju,r(y) = log
exp
+
log log/2U|
4
2
UU
log
20| + log
exp (-t fe))
4
2
Separating the terms corresponding to and S", we get
v U + log|2U| y Us
fu.
u ug + log
exp (- 2y Usists tssts).
4
The last term resembles the log & term that appears in the univariate case. This resemblance be made more clear as follows. Let rs = Uss + v and M M
Us.
= log /
exp (-(1SM Mts 215rs))
50
log
exp (-((ME)) MLs + 215rs + - M M-Trs----
log
exp (-I|Mts + M M-MM-TT -M rs|l + +r.
"M Trs)
50
- -M-TTs + log
(-1its + Vr'rrslin (rs(((s)
exp
1s50
(2x) Ug 1 /2 1/2
-r rg + log
exp (-11ts + Ug rrrssslls))
1s (2T) 4/2 U3 /2/ 1/2 /2/1/2
= =T 8 Ts
log 2Us + log
1
exp
1 llts + +U's
1r'rs(1203 +
2
1550 (2 Uz /2 /2/1/2
2
-ršU, rs
log 2U log + 0: U rs:
UU
+c
2
2
Putting this together, fu,, can be written as:
1
log(2)
fu,)
4 loglU' Us - + +r3U rs log + +151
2
+ log きb (0:11 -U rs, E= 2
5 + (51)
Thus, it appears that evaluating the likelihood for even a single sample involves the high-dimensional integral that is the rectangular edf in equation (51).
F33
Computing Gradients
F.3.1
One Dimensional Case
In the one-dimensional case, the gradient with respect to u is easily computed as:
V Vulu, (v) = Σ (wy, u 22)x;;
m(u-u x.))
BES'
iE
where we have previously defined m(x) as the mills ratio. Furthermore, we have:
Volu,( 1 Σ 2 vi xi))
51

---

F.3.2 Multidimensional Case
First we consider the non-integral terms in the likelihood. Differentiating each term wrt U, we get
r U
u
1U
4
U 2
log
|2
U-
0
VUys.Us.us =
y'
Differentiating each term wit v, we get
U v
4
2
0
V Vgyg.
ys'
Now consider the integral term. Differentiating wrt U, get
V log
exp
(-thUsts 2y5.
vgtss
1350
-tst's
-tsys
Ses
exp (-15Usls - 2y Usists v5(ls)
-ysitz
0
Sis exp
(-th - vsts)
Let M be matrix such that
M
Then via completion of squares in the exponential term, we get
Vu log
exp
(-t5 Usst - vssts)
(52)
50
-lsl's
-Isyss
Sts
exp
(-IIMts +
+ " (2)
-ys:
(53)
Seygo exp (-II + (M-I) + 12)
Notice that this density is Gaussian, with mean and covariance:
N M- (M-) (Ussvs =²=:; : U-1
And hence, the gradient can estimated as
tst
-tsys
V log / exp (-15Usts 2uy Usstss - vgls)
50
ys
0
where is is the truncation of to the negative quadrant. A similar calculation gives the gradient for v as
U=1
z~
(UssUu
V. log / exp (ttSUsts 225 Usists uğts)
-1ss
t0
ts
52


Reviews:
[{"review_id": "5TffM9CZsH", "reviewer": "Reviewer_77Ng", "summary": "1. This paper shows how MLE can perform distribution learning in the setting of linear regression and in multi-layer ReLU networks.\n2. This does not take a distribution on labels to be any specific form but rather unknows and tries to derive the sample complexity for a small total variational distance between the model’s conditional distribution and actual conditional distribution.\n3. Improves the sample complexity of the previous work which suffers an exponential dependence on the ||W|| term.\n4. Generalized how one layer Relu layer sample complexity can be extended to multilayer Relu networks.", "questions": "1. Theoretically the distribution of labels x being unknown is correct. But in most cases, labels follow some multinomial distribution with some parameters. Does this assumption make the bound better? It would be better if some analysis is being done with the distribution of x being multinomial.\n\n2. The proofs rely on the distribution of y being Gaussian. What would happen if you take the distribution of y as unknown and rather x being some multinomial as it happens in many practical settings of time series and computer vision?\n\n3. There is some confusion in the notation. In line 36 it is mentioned that x denotes the labels and y is the data generated using that label. In linear regression, authors tried to predict y  using x which is correct. In theorem 4.1. is that notation of y being the data and x being the labels being followed or is it reversed?", "limitations": "1. There is some limitation where we can have the conditional distribution of data to be Gaussian in those cases the proof techniques do not work.\n2. Mostly in the literature of generative models the data distribution is taken to be some unknown complex distribution and labels are multinomial distribution with some appropriate parameters. These bounds don’t address that. So that is why there will be very limited use cases. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This work is a nice extension of the previous work mentioned in the reference[27]. It relaxes the assumption of previous work which assumed a fixed distribution of the labels.\n2. The quality and clarity of the paper is good. Gives good proof techniques using the ideas from the learning theory.\n3. Nice result for the linear regression in Theorem-4.1 where the sample complexity is linear in k: dimensionality of the labels which is some finite value in most of the cases.\n4. This paper can be significant where the label distribution is unknown but the data distribution is known. ", "weaknesses": "1. The proof techniques assumed the distribution of the data is Gaussian which is rarely the case because the actual data distribution for generative models thought of some complex unknown distribution.\n2. Even though theorem 4.2 proved the result nicely there is a dependence of the square of the dimensionality of data. So the curse of dimensionality remains and these bounds can be very loose. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful feedback and criticism. Please find\nbelow our response to your concerns. We wish to emphasize that we do\nnot make assumptions about the distribution over the labels or the\ndata, we only assume that the conditional distribution per-layer is\nGaussian followed by a ReLU.\n\n**Weakness 1:** \"The proof techniques assume the data is Gaussian\".  \n\nThere's been a misunderstanding here: in Section 4.1 we assume that\nthe *conditional distribution* of $y \\mid x$ is Gaussian, and in\nSection 4.2 we assume that it is Gaussian followed by a ReLU. \n\nThis assumption is not just a theoretical convenience. The additive Gaussian noise before the ReLU is used in state-of-the-art models like StyleGAN, where the learned Gaussian noises are called ``style'' variables: these give desirable stochasticity to the images, such as texture in hair, skin, etc.\n\nAs we make no assumptions about the distribution of $x$, the resulting\ndistribution of $y$ will be $p_Y(y) = \\int_{x} q_X(x) p(y|x) dx$, and this\ndistribution can be quite complicated based on the distribution of\n$x$. Furthermore, we can compose our theorem for one-layer networks\nmultiple times. This allows us to give sample complexities for\nmulti-layer ReLU networks. As this process of linear transformation\nfollowed by a non-linear activation is repeated $L$ times, the final\ndistribution will be far more expressive than a simple Gaussian. \nFor example, the distribution of images produces by StyleGAN has such a form.\n\n\nReferences:\n\n[1] Karras, Tero, Samuli Laine, and Timo Aila. \"A style-based generator architecture for generative adversarial networks.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019.\n\n\n**Weakness 2:**\n\"There is a dependence on the square of the dimensionality of\ndata... the bounds are loose\".\n\nUnfortunately, learning a high-dimensional Gaussian with unknown covariance matrix in total variation takes $\\tilde{\\Omega}(d^2)$ samples; see [2].\nOur Theorem 4.5 would solve their lower bound instance, so the same lower bound applies and our bound is not loose beyond possibly log factors.\n\nReferences:\n[2] Ashtiani, Hassan, et al. \"Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes.\" Advances in Neural Information Processing Systems 31 (2018).\n\n\n**Question 1:**\n\"If $x$ has a multinomial distribution, does this improve\nthe bound.\"\n\nPerhaps assuming multinomial\ndistributions on $x$ can help simplify the analysis and remove the\ncondition number dependence, but it's not going to remove the $d^2$ dependence (which appears even if $x = 0$ always). \n\nThe reason we assume an unknown arbitrary distribution\nover $x$ is that it allows us to compose our guarantee over multiple\nlayers. For example, if the generative model maps a Word2Vec embedding\nto an images, then at the first layer, the distribution of $x$ would be\nthat of a Word2Vec embedding. Then for the second layer, we can treat\n$x$ as the output of the first layer. This allows us to compose our\nguarantee over multiple layers, and hence allows for an expressive\ndistribution over the data.\n\n**Question 2:** \n\"What would happen if the distribution of $y$ is unknown\nbut $x$ has a multinomial distribution\".\n\nThis would be a significantly harder case, as this would imply that we\nhave no way of writing the likelihood of $y$. The assumption that\nthe conditional distribution is a Gaussian allows us to write the\nlog-likelihood of $y$ in terms of $x$, regardless of the distribution\nof $x$. It's an interesting question what one could do with fewer assumptions on\n$y|x$, but it would need a pretty different approach.\n\n**Question 3:** \n\"Line 36 says $x$ denotes the labels and $y$ is the data\ngenerated using that label ... does Theorem 4.1 use the same notation\nor is it reversed\" \n\nWe apologize for the confusion -- in line 36, we used labels in the\nsense of the class conditional labels that would be passed to a\ntext-conditional generative model. In the context of linear\nregression, $x$ would be feature vectors (such as Word2Vec embeddings)\nand $y$ would be the data generated. We will change this to reduce\nconfusion.\n"}, {"review_id": "Un28Aw0z7t", "reviewer": "Reviewer_9DZK", "summary": "The article provides complexity bounds for learning the conditional distribution y|x. One of the main novelties claimed by the authors is that the control of the TD distance between the estimated distribution and the ground truth is more meaningful. Thus, they are able to provide bounds independently of the distribution of label x. The article is well written and the flow is quite pleasant. \nSee my comments below for more critical details", "questions": "\n\n- Usually x is the features and y the labels. The notation might be misleading. \nAs a matter of fact the product $x \\cdot w^*$ is even weird when the label does not belong to a vectorial space.\n- On the same flavor, it is difficult to compare with classical results, since the assumptions are usually in the feature space ie distribution assumption on the objet $x$ and the label is generated conditional on $x$ and some noise. It is unclear how the results fit on the same ground.\n- The lines 32-35 need explicit references and maybe explicit classical bounds to discuss.\n\n- The complexity presented is not explicitly compared with (the criticized) classical ones. Hence it makes the contributions harder to appreciates\n\n- Theorem 4.1 (and probably) others must states the full assumptions eg $n \\geq k/2$ which usually does not hold in high dimensional regime where the number of features is way larger than the sample size.\n\n- As a main proof technique, the authors rely on the relation between TV distance and prediction error in the equation below line 159.\nMainly $d(\\hat w, w^*) \\approx |x\\cdot \\hat w - x \\cdot w^*|$. And then we directly fall into the OLS analysis as in https://www.di.ens.fr/%7Efbach/ltfp_book.pdf Chapter 3. Can the authors comments on the main novelties after this. Usually the prediction error does not require much restriction on the design matrix (compared to estimation error control).\n\n- In Lemma 4.3, can the authors specify what the probability Pr is?\nAlso, since the (empirical) distance is Lipschitz, can't we deduce this lemma directly from Talagrand inequality?\n\n- In which practical settings do we know the ground-truth conditioning number?\n- Also in Theorem 4.5, $\\hat W$ and $\\hat \\Sigma$ might be non unique. Can the authors comment on that?\n\nSome failure of MLE are quite known, for example in Chapter 24.1.3, https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf an explicit overfitting example is shown. Can the authors discuss how their proposition escape such a situation?\n", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The document is clearly written and the main arguments are transparent and easy to follow (even if they remain fairly technical). The authors did a great job explaining the intuition before getting into formal details. \n\nThe distribution free result (wrt to label x) is quite remarkable.", "weaknesses": "My main concern is that the results presented might be difficult to compare to classical results on the subject. Below I describe some of my missunderstanding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed analysis of our paper. We will include\nyour suggestions in future versions.\n\n**Question 1:**\"Usually $x$ denotes features and $y$ the labels... $x\n\\cdot w^*$ is even weird when the label does not belong to a vector\nspace.\"\n\nWe apologize for the confusion -- we used labels in the sense of class\nlabels that would be passed to a text-conditional generative model. In\nthe context of linear regression, $x$ would be feature vectors (such\nas Word2Vec embeddings) and $y$ would be the data generated. We will\nchange this to reduce confusion.\n\n**Question 2:**\"On the same flavor, it is difficult to compare with\nclassical results, since the assumptions are usually in the feature\nspace ie distribution assumption on the objet and the label is\ngenerated conditional on and some noise. It is unclear how the results\nfit on the same ground.\"\n\nWhile it would be nice for comparison to use the same assumptions as classical works as you suggest, the nature of this work is such that this is not possible.\n\nA central aspect of this work is to examine this learning framework from a perspective more relevant to modern problems --- specifically in learning generative models. In doing so, we consider new assumptions (1) no distributional assumptions over $x$ and new goals (2) learning distributions in TV.\n\n(1) The reason we assume an unknown arbitrary distribution over $x$ is\nthat it allows us to compose our guarantee over multiple layers. For\nexample, if the generative model maps Word2Vec embeddings to images,\nthen at the first layer, the distribution of $x$ would be those of\nWord2Vec embeddings. Then for the second layer, we can treat $x$ as\nthe output of the first layer. This allows us to compose our guarantee\nover multiple layers, and hence allows for an expressive distribution\nover the data.\n\n(2) Learning in TV is useful because in problems concerning generative models, we are generally concerned with the output of the model, rather than learning the parameters exactly. In our simulation Section 5, Fig. 3 (a), we provide a particular example where the classical objective fails, while our proposed objective succeeds. \n\n**Q3:**\"lines 32-35 need explicit references and classical bounds\". \n\nWe will add this, thank you for the suggestion.\n\n**Q4:**\"The complexity presented is not explicitly compared with (the criticized) classical ones. Hence it makes the contributions\nharder to appreciates\"\n\nIn Section 4.2, we focused on comparing our results to existing\nresults (Wu et al [1], Allen-Zhu and Li [31]) on generative models. The results in Section 4.1 are to\nbuild intuition for our proof techniques, and what needs to change for\nthe ReLU model in Section 4.2. We will add more citations to directly\ncompare our results to existing work in Section 4.1.\nUltimately, as mentioned with our answer to question 2, the differences in assumptions and objectives mean that an exact direct comparison is difficult. \n\n**Q5:**\"Theorem 4.1 ... must states the full\nassumptions eg $ n \\ge k/2$\"\n\nThank you for the suggestion, we shall include this. This was implicit\nin Theorem 4.1 as $\\varepsilon < 1$ with a large enough constant $C$,\nbut we will explicitly mention this. We will also mention that these\nbounds are not for the over-parameterized regime.\n\n**Q6:**\"What are the novelties over OLS analysis.\"\n\nThe analysis in the reference provided by the reviewer has a sample\ncomplexity that depends on the design matrix $\\Phi$, in terms of\ntrace$[(\\frac{1}{n} \\Phi^T \\Phi)]$. This would introduce a \ndependency on the $\\ell_2$-norm of $x$ in Eqn 6 in our paper, and typical assumptions to deal with this would require bounded moments for $x$. Our sample\ncomplexity has no dependence on this design matrix.\n\nWe avoid this dependence on the $x$ distribution by adopting a similar analysis to Theorem 11.2 in Györfi et\nal (https://link.springer.com/book/10.1007/b97848), which is relatively simple because $d(\\hat{w}, w^*)$ is bounded.\n\nFor Theorem 4.5, we cannot fall into the OLS analysis for half the proof, and we use the Györfi approach twice.  The second time is more challenging because the variables we concentrate are KL divergences, which are unbounded.\n\n**Q7:**\"In Lemma 4.3, can the authors specify what the\nprobability Pr is? Also, since the (empirical) distance is Lipschitz,\ncan't we deduce this lemma directly from Talagrand inequality?\"\n\nThe $\\mathrm{Pr}(\\cdot)$ refers to the probability over the finite data samples $x$\ndrawn i.i.d. from some arbitrary distribution $D_x$.  That lemma is independent of the samples $y_i$, sorry for the confusion.\n\nThe distance is actually not Lipschitz: it's Lipschitz in $\\langle w, x \\rangle$, but if $x$ is extremely large then a small change in $w$ can have a large change in $d(w, w^*)$.  So we don't see how to apply\nTalagrand's inequality without assumptions on the distribution\nof $x$.\n\n**Q8:**\"In which practical settings do we know the ground-truth\nconditioning number?\"\n\nThis is a good point and an open question which we shall explicitly\nstate. We only require an upper bound on the condition number, and as\nour sample complexity scales logarithmically on the condition number,\nhence we did not consider this to be a major limitation.\n\n**Q9:**\"$\\widehat{W}, \\widehat{\\Sigma}$ may not be unique\".\n\nWe will state this more explicitly in the paper, but we do not require\nuniqueness.  The reason for this is that as we are not trying to\nestimate the parameters themselves, and instead care about fitting the\ndistribution of the data, any parameters that fit the observed\ndistribution are acceptable.\n\n**Q10:**\"How does the proposition escape known failures of the\nMLE.\"\n\nIn the limitations section, we did mention that our proposition is succeptable to failues of MLE, such as requiring knowledge of the\ngenerative model's architecture, exacerbating bias, etc. The failure case mentioned by the reviewer would correspond to exacerbating bias, as having too few samples leads to a heavily overfit solution."}, {"review_id": "36n5Ou9cNo", "reviewer": "Reviewer_zitB", "summary": "In this paper, the authors consider the problem of linear regression and ReLU applied to linear regression. The goal is to recover the weight vector such that the resulting distributions are close as opposed to recovering the weight vector under certain norms such as $\\ell_2$ which has been thoroughly studied. For the linear regression, the authors show that the MLE estimator learns the distribution in total variation distance. For the ReLU regression, the authors show again the MLE estimator works when the covariance matrix of the noise is well-conditioned. The resulting algorithm is sample-efficient but not time-efficient.", "questions": "None.", "limitations": "None,", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The problem considered is fundamental and it has important connections to learning practically important problems.", "weaknesses": "I think the scientific novelty and contribution of this paper is very limited. The proposed results were well-known in the literature in my opinion. As an example, the distributional learning guarantee of linear regression in TV distance was analyzed in [arXiv:2107.10450]. Similarly, one-layer ReLU networks have been analyzed in the works of [Diakonikolas et al, Klivans et al, and Arora et al]. Moreover, the condition number assumption and the high running time of the proposed algorithms are quite restrictive in my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are disappointed that you've found no positives in our paper. After\nreading the other reviews and this rebuttal, please can you let us\nknow if you have any questions that can help us improve our paper?\n\nPlease find below our responses to your concerns.\n\n**Weakness 1:** \"The proposed results were well-known in the literature in\nmy opinion. As an example, the distributional learning guarantee of\nlinear regression in TV distance was analyzed in [arXiv:2107.10450].\"\n\n2107.10450 considers a Gaussian Bayesian network, where *all* the\nvariables are Gaussian, and they can find parameters that are close to\nthe true distribution over these Gaussian random variables. \n\nIn our problem, the distribution of $x$ is not Gaussian, and should be\nthought of as a distribution over Word2Vec embeddings. The conditional\ndistribution of $y|x$ is assumed to be Gaussian, and the final sample\ncomplexity is independent of any parameter other than the dimension of\n$x$.\n\n**Weakness 2:** \"Similarly, one-layer ReLU networks have been analyzed in\nthe works of [Diakonikolas et al, Klivans et al, and Arora et al].\"\n\nThese are some of the most prolific names in learning theory, and\nwithout pointing to specific papers, we have no concrete way of\nresponding to your criticism.\n\nNonetheless, in an attempt to guess your concern, the simplest response is that none of\nthese results can been extended to multi-layer networks, and our\nassumptions and analysis allow us to consider multi-layer networks.\nAs we make no assumptions on the distribution of $x$, this allows us to\ncompose our one-layer guarantee recursively over multiple layers. \n\nThe assumption that the conditional distribution per layer is a truncated Gaussian is actually used in practice, for example in StyleGAN [1], where the ``style'' vectors are random Gaussian noise variables with learned mean and covariance.\n\nReferences:\n[1] Karras, Tero, Samuli Laine, and Timo Aila. \"A style-based generator architecture for generative adversarial networks.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019.\n\n**Weakness 3**: \"the condition number assumption and the high running time of the proposed algorithms are quite restrictive in my opinion\"\n\nOur sample complexity has a logarithmic dependence on the condition number, which allows for an exponentially large condition number with only a polynomial increase in the sample complexity. We agree that the running time is a concern, but as the optimization problem involves maximizing a concave function over a convex set, we believe a better designed optimization algorithm should be able to achieve a rigorous guarantee. The goal of this work is to show that MLE can be used for *distributional learning* of generative models with a polynomial sample complexity."}, {"review_id": "rJVP237Eo7", "reviewer": "Reviewer_9ZPm", "summary": "This paper studies conditional distribution learning: given iid samples (x,y) where x ~ D and y ~ p(y|w*,x), the goal is to find some estimate w such that the distributions p(y|w*,x) and p(y|w,x) are close in expectation over x ~ D, or equivalently the learned distribution of (x,y) (where x ~ D) is close to the true distribution.\n\nSpecifically, this work studies the 1-layer conditional generative model y = max(W* x + eta, 0) where W* is a matrix and eta is a multivariate mean-zero Gaussian with some unknown covariance Sigma*. The main result shows that for an arbitrary covariate distribution D, and arbitrary W*, so long as Sigma* has covariance at most kappa, the sample complexity of MLE (needed to learn up to total variation distance epsilon) is polynomial in the dimension parameters, log(kappa), and 1/epsilon.\n\nAn straightforward extension to multi-layer networks is also given (under the assumption that intermediate activations are known).", "questions": "See above", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work introduces a (to my knowledge) novel perspective to the problem of learning generative models: distribution learning rather than parameter estimation. This more accurately addresses the problem that actually matters in practice for generative models, and avoids needing to worry about identifiability issues.\n- Due to the new goal, no distributional assumptions are needed (aside from the tame bound on condition number of the noise).\n- The paper is well-written, with a toy example of linear regression given for intuition. I did not have time to check the proofs, but the approach and proof sketch seem reasonable.", "weaknesses": "- As the authors acknowledge, the paper only addresses the statistical question. It's claimed that the MLE is concave; however, I could not find a proof of this fact in the paper. Moreover, looking at the log-likelihood function (8) I do not see why it should be concave.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback, we are delighted that you find\nour problem novel and the results significant.\n\nPlease find below our response to your concern regarding our claim\nthat the MLE is concave.\n\n**Question 1:**\n\"It's claimed that the MLE is concave, however, I could\nnot find a proof\"\n\nWe apologize, due to an editing error we neglected to provide a proof of this in the\nsupplementary. The proof actually follows as a straightforward result\nof the following fact. The objective in Eqn (8) is an integral  of\ntwo log-concave functions: (i) the indicator function over the negative\northant, and (ii) the Gaussian likelihood. As (i) and (ii) are\nlog-concave functions, their integral in Eqn (8) is also log-concave.\n\nLog-concavity being closed under integration is a non-trivial fact -- for a concrete reference, please refer to Page 106 in Boyd and\nVandenberghe (https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf),\nin particular, Examples 3.42, 3.43, and 3.44."}, {"review_id": "dY1KYw4aN6", "reviewer": "Reviewer_NYne", "summary": "The paper investigates the sample complexity of learning conditional generative models without assumptions on the input distribution. It applies the Maximum Likelihood Estimator (MLE) to linear regression and 1-layer networks with ReLU activation. The results show that the MLE achieves small total variation error with sample complexities of $O(k/\\epsilon^2 log(1/\\epsilon))$ for linear regression and O((kd + d^2) / \\epsilon^2 log(kd\\kappa/\\epsilon)) for 1-layer networks. The paper also discusses the extension to multilayer networks,  given access to the internal activations. The results suggest that MLE is a promising approach for learning feed-forward generative models from limited samples, though the authors did mention that the computational aspects of the optimization problem are not thoroughly analyzed in the paper.  \n", "questions": "What are the practical implications of the sample complexity bounds derived in the paper? How do these bounds impact the feasibility and scalability of learning generative models in real-world applications?\n\nI understand that the paper is limited by space restrictions, but can you provide some insights into how to go about addressing the requirement for accessing intermediate activations in order to apply the proposed algorithm to solving deep neural nets? Is it going to be a deal breaker for the practical applicability of the proposed method?", "limitations": "No potential negative societal impact. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper provides a solid theoretical foundation for understanding the sample complexity of learning multi-layer ReLU networks using MLE method. The derived bounds do not make assumptions on the distribution of X or the condition number of W, and achieve a sample complexity polynomial in the system parameters. The developed algorithm and theories show considerable improvement over those in the existing literature. Though there are limitations that are also noted by the authors, I think the paper is innovative and provides interesting insights into efficient learning of conditional generative models. \nMoreover, the paper is well-written and presents its concepts and results in a clear and concise manner.", "weaknesses": "The weakness and limitations of the paper are well noted and discussed by the authors. \n\n1. To extend the theory to multilayer neural networks, it requires access to intermediate activations, which is impractical\n2. It assumes that the learner has an understanding of the model architecture, which might not be the case in practice\n3. It might be challenging to perform MLE on some of the models being considered, such as neural networks, and the computational aspects of the optimization problem are not thoroughly examined in this paper. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback, we are delighted that you find\nour results to be a solid theoretical foundation and a considerable\nimprovement over existing literature.\n\nPlease find below our response to your questions: \n\n**Question 1:**\n\"What are the practical implications of the sample\ncomplexity bounds derived in the paper? How do these bounds impact the\nfeasibility and scalability of learning generative models in\nreal-world applications?\"\n\nAn important part (perhaps the most important part) about our complexity bounds is that they do not depend on the input distribution $x$. This means that our result can be composed for learning multi-layer networks. but also, this means that learning a one layer ReLu network in TV, which is in itself a valid and potentially useful statistical framework is possible with a sample complexity independent of the input distribution $x$. \n\nIn terms of learning actual generative models, this work suggests that learning models in TV is possible even when learning model parameters is not. This might help to explain recent work (https://crfm.stanford.edu/2023/03/13/alpaca.html, https://arxiv.org/pdf/2305.11206.pdf) where researchers are able to essentially clone the behaviour of other language models with a very small fraction of samples when fine-tuning another language model. This may be related to the *superficial alignment hypothesis*, which says that these models only require a superficial modification to align their behaviours. It is clear in this case that the weights are not being learned. \n\n**Question 2:**\n\"I understand that the paper is limited by space\nrestrictions, but can you provide some insights into how to go about\naddressing the requirement for accessing intermediate activations in\norder to apply the proposed algorithm to solving deep neural nets? Is\nit going to be a deal breaker for the practical applicability of the\nproposed method?\"\n\nThis is a very interesting question and one we are actively\nconsidering. We think that the approach in Allen-Zhu and Li [1] can\nactually be used in our paper as well. Allen-Zhu and Li assume that\nthe activations are sufficiently sparse across layers, which means they\ncan use results from sparse-coding to recover these activations given\nonly images at these layers.\n\nThe main difficulty in directly combining the results in [1] into our\nalgorithm as a subroutine is that they are only able to\n*approximately* recover the activations -- this would mean there is a\ndistributional mismatch between the true activations and the estimated\nactivations. If this distribution mismatch is in TV distance, then the\nresults in [1] can be straightforwardly incorporated into ours, where\nthe error in the activations will be an additive error in our results.\nUnfortunately, the error in [1] is wrt the $\\ell_2$-norms of the\nactivations -- this means that the true and estimated activations\nwould perhaps only be close in Wasserstein distance. Accommodating\nthis distribution mismatch is an open problem we are exploring, and\none that would make our method more practical.\n\nReferences:\n\n[1] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"Forward Super-Resolution: How\nCan GANs Learn Hierarchical Generative Models for Real-World\nDistributions.\" The Eleventh International Conference on Learning\nRepresentations. 2022.\n"}]

Author rebuttal:
**General response to reviewers**

Thank you for your thoughtful reviews, we appreciate the
time and effort that you put into the review process. We are delighted that the reviewers
found our paper to have: a solid theoretical foundation [NYne], a
novel perspective [9ZPm], considerable improvements over existing
literature [NYne], clarity with good proof sketches[77Ng, 9DZK, 9ZPm,
NYne], and distribution-free results that are significant and
remarkable [77Ng, 9DZK, 9ZPm, NYne].

We have addressed individual reviewer concerns as separate replies to the respective reviewers.


Meta-review: The paper shows that maximum likelihood estimation can be used to learn one-layer conditional generative models in total variation distance regardless of the label x's distribution. The paper is well written and provides an elegant solution. I strongly encourage authors to incorporate reviewer comments in the final version.
Decision: Accept (poster)