# estimating_learnability_in_the_sublinear_data_regime__e9785699.pdf Estimating Learnability in the Sublinear Data Regime Weihao Kong Stanford University whkong@stanford.edu Gregory Valiant Stanford University gvaliant@cs.stanford.edu We consider the problem of estimating how well a model class is capable of fitting a distribution of labeled data. We show that it is possible to accurately estimate this learnability even when given an amount of data that is too small to reliably learn any accurate model. Our first result applies to the setting where the data is drawn from a d-dimensional distribution with isotropic covariance, and the label of each datapoint is an arbitrary noisy function of the datapoint. In this setting, we show that with O( d) samples, one can accurately estimate the fraction of the variance of the label that can be explained via the best linear function of the data. For comparison, even if the labels are noiseless linear functions of the data, a sample size linear in the dimension, d, is required to learn any function correlated with the underlying model. Our estimation approach also applies to the setting where the data distribution has an (unknown) arbitrary covariance matrix, allowing these techniques to be applied to settings where the model class consists of a linear function applied to a nonlinear embedding of the data. In this setting we give a consistent estimator of the fraction of explainable variance that uses o(d) samples. Finally, our techniques also extend to the setting of binary classification, where we obtain analogous results under the logistic model, for estimating the classification accuracy of the best linear classifier. We demonstrate the practical viability of our approaches on synthetic and real data. This ability to estimate the explanatory value of a set of features (or dataset), even in the regime in which there is too little data to realize that explanatory value, may be relevant to the scientific and industrial settings for which data collection is expensive and there are many potentially relevant feature sets that could be collected. 1 Introduction Given too little labeled data to learn a model or classifier, is it possible to determine whether an accurate classifier or predictor exists? For example, consider a setting where you are given n datapoints with real-valued labels drawn from some distribution of interest, D. Suppose you are in the regime in which n is too small to learn an accurate prediction model; might it still be possible to estimate the performance that would likely be obtained if, hypothetically, you were to gather more data, say a dataset of size n n and train a model on that data? We answer this question affirmatively, and show that in the settings of linear regression and binary classification via linear (or logistic) classifiers, it is possible to estimate the likely performance of a (hypothetical) predictor trained on a larger hypothetical dataset, even given an amount of data that is sublinear in the amount that would be required to learn such a predictor. For concreteness, we begin by describing the flavor of our results in a very basic setting: learning a noisy linear function of high-dimensional data. Suppose we are given access to independent samples from a d-dimensional isotropic Gaussian, and each sample, x Rd is labeled according to a noisy linear function y = x, β + η, where β is the true model and the noise η is drawn (independently) from a distribution of (unknown) variance δ2. One natural goal is to estimate the signal to noise ratio, 1 δ2/Var[Y ], namely estimating how much of the variation in the label we could hope to explain. 32nd Conference on Neural Information Processing Systems (Neur IPS 2018), Montréal, Canada. Even in the noiseless setting (δ = 0), it is information theoretically impossible to learn any function that has even a small constant correlation with the labels unless we are given an amount of data that is linear in the dimension, d. Nevertheless, as was recently shown by Dicker [6] in this Gaussian setting with independent noise, it is possible to estimate the magnitude of the noise, δ, and variance of the label, given only O( d) samples. Our results (summarized in Section 1.1), explore this striking ability to estimate the learnability of a distribution over labeled data based on relatively few samples. Our results significantly extend previous results and the results of Dicker in the following senses: 1) We present a unified approach that yields accurate estimation of this learnability when n = o(d) which applies even when the x portion of the datapoints are drawn from a distribution with arbitrary (unknown) covariance. This is very surprising and was conjectured to be impossible [14] because the best linear model can not be approximated with o(d) data, nor can the covariance be consistently estimated with o(d) datapoints. 2) Agnostic setting: Our techniques do not require any distributional assumptions on the label, y, in contrast to most previous work that assumed y is a linear function plus independent noise (which is not a realistic assumption for many of the practical settings of interest). Instead, our approach directly estimates the fraction of the variance in the label that can be explained via a linear function of x. 3) Binary classification setting: Our techniques naturally extend to the setting of binary classification, provided a strong distributional assumption is made namely that the data is drawn according to the logistic model (see Section 1.1 for a formal description of this model). Throughout, we focus on linear models and classifiers. Because some of our results apply when the covariance matrix of the distribution is non-isotropic (and non-Gaussian), the results extend to the many non-linear models that can be represented as a linear function applied to a non-linear embedding of the data, for example settings where the label is a noisy polynomial function of the features. Still, our assumptions on the data generating distribution are very specific for the binary classification results, and our algorithm for this setting does not apply if the two classes have unequal probabilities. We are optimistic that our techniques may be extended in future work to address that setting, as well as more general function classes and losses. Motivating Applications: Estimating the value of data and dataset selection. In some dataanalysis settings, the ultimate goal is to quantify the signal and noise namely understand how much of the variation in the quantity of interest can be explained via some set of explanatory variables. For example, in some medical settings, the goal is to understand how much disease risk is associated with genomic factors (versus random luck, or environmental factors, etc.). In other settings, the goal is to accurately predict a quantity of interest. The key question then becomes what data should we collect what features or variables should we try to measure?" The traditional pipeline is to collect a lot of data, train a model, and then evaluate the value of the data based on the performance (or improvement in performance) of the model. Our results demonstrate the possibility of evaluating the explanatory utility of additional features, even in the regime in which too few data points have been collected to leverage these data points to learn a model. For example, suppose we wish to build a predictor for whether or not someone will get a certain disease. We could begin by collecting a modest amount of genetic data (e.g. for a few hundred patients, record the presence of genetic abnormalities for each of the 20k genes), and a modest amount of epigenetic data. Even if we have data for too few patients to learn a good predictor, we can at least evaluate how much the model would improve if we were to collect a lot more genetic data, versus collecting more epigenetic data. This ability to explore the potential of different features with less data than would be required to exploit those features seems extremely relevant to the many industry and research settings where it is expensive or difficult to gather data. Alternately, these techniques could be leveraged by data providers in the context of a verify then buy model: Suppose I have a large dataset of customer behaviors that I think will be useful for your goal of predicting customer clicks/purchases. Before you purchase access to my dataset, I could give you a tiny sample of the data too little to be useful to you, but sufficient for you to verify the utility of the dataset. One final downstream application of our techniques is to the data aggregation and federated learning settings. The approaches of this work can be re-purposed to measure the extent to which two or more labeled datasets have the same (or similar) labeling functions, even in the regime in which there is too little data to learn such labeling functions. (This can be accomplished, for example, by applying our techniques of this paper to the aggregate of the datasets versus individually and seeing whether the signal to noise ratio degrades upon aggregation.) Such a primitive might have fruitful applications in realm of federated learning, since one of the key questions in such settings is how to decide which entities have similar models, and hence which subsets of entities might benefit from training a model on their combined data. 1.1 Summary of Results Our first result applies to the setting where the data is drawn according to a d dimensional distribution with identity covariance, and the labels are noisy linear functions. This result generalizes the results of Dicker [6] and Verzelen and Gassiat [14] beyond the Gaussian setting. Provided there are more than O( d) datapoints, the magnitude of the noise can be accurately determined: Proposition 1. [Slight generalization of Lemma 2 in [6] and Corollary 2.2 in [14]] Suppose we are given n labeled examples, (x1, y1), . . . , (xn, yn), with xi drawn independently from a d-dimension distribution of mean zero, identity covariance, and fourth moments bounded by C. Assuming that each label yi = xiβ + η, where the noise η is drawn independently from an (unknown) distribution E with mean 0 variance δ2, and the labels have been normalized to have unit variance. There is an estimator ˆδ2, that with probability 1 τ, approximates δ2 with additive error O(C d+n The fourth moment condition of the above theorem is formally defined as follows: for all vectors u, v Rd, E[(x T u)2(x T v)2] CE[(x T u)2]E[(x T v)2]. In the case that the data distribution is an isotropic Gaussian, this fourth moment bound is satisfied with C = 3. In the above setting, it is information theoretically impossible to approximate β, or accurately predict the yi s without a sample size that is linear in the dimension, d. As we show, the above result is also optimal, to constant factors, in the constant-error regime: no algorithm can distinguish the case that the label is pure noise, from the case that the label has a significant signal, using o( d) datapoints (see e.g. Proposition 4.2 in [15]). Our estimation machinery extends beyond the isotropic setting, and we prove an analog of Proposition 1 in the more general setting where the datapoints, xi are drawn from a d dimensional distribution with (unknown) non-isotropic covariance. This setting is considerably more challenging than the isotropic setting because the geometry of the datapoints depend heavily on the covariance, yet the covariance can not be accurately estimated with o(d) samples. Though our results are weaker than in the isotropic setting, we still establish accurate estimation of the unexplained variance in the sublinear regime, though require a sample size Oϵ(d1 ϵ) to obtain an estimate within error O(ϵ). In the case where the covariance matrix has a constant condition number, the sample size can be reduced to n = Oϵ(d1 1 log 1/ϵ ). Our results in the non-isotropic setting apply to the following standard model of non-isotropic distributions: the distribution is specified by an arbitrary d d real-valued matrix, S, and a univariate random variable Z with mean 0, variance 1, and bounded fourth moment. Each sample x Rd is then obtained by computing x = Sz where z Rd has entries drawn independently according to Z. In this model, the covariance of x will be SST . This model is fairly general (by taking Z to be a standard Gaussian this model can represent any d-dimensional Gaussian distribution, and it can also represent any rotated and scaled hypercube, etc), and is widely considered in the statistics literature (see e.g. [17, 1]). While our theoretical results rely on this modeling assumption, our algorithm is not tailored to this specific model, and likely performs well in more general settings. Theorem 1. Suppose we are given n < d labeled examples, (x1, y1), . . . , (xn, yn), with xi = Szi where S is an unknown arbitrary d d real matrix and each entry of zi is drawn independently from a one dimensional distribution with mean zero, variance 1, and constant fourth moment. Assuming that each label yi = xiβ +η, where the noise η is drawn independently from an unknown distribution with mean 0 and variance δ2, and the labels have been normalized to have unit variance. There is an algorithm that takes n labeled samples, parameter k, σmax,σmin which satisfies σmax I ST S σmin I, and with probability 1 τ, outputs an estimate ˆδ2 with additive error |ˆδ2 δ2| k2 , 2e (k 1) q σmin σmax ))σmax β 2 + f(k) τ Pk i=2 di/2 1/2 ni/2 , where f(k) = k O(k). Considering the case when β , σmax are constants, setting k = 1/ ϵ in the case where σmin = 0 or k = O(log( 1 ϵ )) in the case where σmin is a constant greater than 0 yields the following corollary: Corollary 1. In the setting of Theorem 1, with constant β and σmax, the noise can be approximated to error O(ϵ) with n = O(poly(ϵ)d1 ϵ). With the additional assumption that σmin is a constant greater than 0, the noise can be approximated to error O(ϵ) with n = O(poly(log(1/ϵ))d1 1 log 1/ϵ ). Finally, we establish the lower bound, demonstrating that, without any assumptions on Σ or β , no sublinear sample estimation is possible. See Theorem 3 of the supplementary material for the lowerbound statement. The Agnostic Setting. Our algorithms and techniques do not rely on the assumption that the labels consist of a linear function plus independent noise, and our results partially extend to the agnostic setting. Formally, assuming that the label, y, can have any joint distribution with x, we show that our algorithms will accurately estimate the fraction of the variance in y that can be explained via (the best) linear function of x, namely the quantity infβ E[(βT x y)2]. The analog of Proposition 1 in the agnostic setting is the following: Theorem 2. Suppose we are given n labeled examples, (x1, y1), . . . , (xn, yn), with (xi, yi) drawn independently from a d + 1-dimension distribution where xi has mean zero and identity covariance, and yi has mean zero and variance 1, and the fourth moments of the joint distribution (x, y) is bounded by C. There is an estimator ˆδ2, that with probability 1 τ, approximates infβ E[(βT x y)2] with additive error O(C d+n In the setting where the distribution of x is non-isotropic, the algorithm to which Theorem 1 applies still extends to this agnostic setting. The estimate of the unexplained variance is still accurate in expectation, though additional assumptions on the (joint) distribution of (x, y) would be required to bound the variance of the estimator in this agnostic and non-isotropic setting. Such conditions are likely to be satisfied in many practical settings, though a fully general agnostic and non-isotropic analog of Theorem 1 likely does not hold. Binary Classification. Our approaches and techniques for the linear regression setting also can be applied to the important setting of binary classification namely estimating the performance of the best linear classifier, in the regime in which there is insufficient data to learn any accurate classifier. As an initial step along these lines, we obtain strong results in a restricted model of Gaussian data with labels corresponding to the latent variable interpretation of logistic regression: Theorem 3. Suppose we are given n < d labeled examples, (x1, y1), . . . , (xn, yn), with xi drawn independently from a Gaussian distribution with mean 0 and covariance Σ where Σ is an unknown arbitrary d by d real matrix. Assuming that each label yi takes value 1 with probability g(βT xi) and 1 with probability 1 g(βT xi), where g(x) = 1 1+e x is the sigmoid function and β is an unknown parameter vector. There is an algorithm that takes n labeled samples, parameter k, σmax and σmin which satisfies σmax I Σ σmin I, and with probability 1 τ, outputs an estimate \ erropt with ad- ditive error |\ erropt erropt| c r k2 , 2e (k 1) q σmin σmax )σmax β 2 + f(k) τ Pk i=2 di/2 1/2 where erropt is the classification error of the best linear classifier, f(k) = k O(k) and c is an absolute constant. In the setting where the distribution of x is an isotropic Gaussian, we obtain the simpler result that the classification error of the best linear classifier can be accurately estimated with O( d) samples. This is information theoretically optimal, see Theorem 8 of the supplementary material. Corollary 2. In the setting of Theorem 3 but where each datapoint, xi is drawn according to a d-dimension isotropic Gaussian distribution, there is an algorithm that takes n labeled samples, and with probability 1 τ, outputs an estimate \ erropt with additive error |\ erropt erropt| c( d n )1/2, where erropt is the classification error of the best linear classifier and c is an absolute constant. Despite the strong assumptions on the data-generating distribution in the above theorem and corollary, the algorithm to which they apply seems to perform quite well on real-world data, and is capable of accurately estimating the classification error of the best linear predictor, even in the data regime where it is impossible to learn any good predictor. One partial explanation is that our approach can be easily adapted to a wide class of link functions, beyond just the sigmoid function addressed by the above results. Additionally, for many smooth, monotonic functions, the resulting algorithm is almost identical to the algorithm corresponding to the sigmoid link function. 1.2 Related Work For the specific question of estimating the signal to variance ratio (or signal to noise), also referred to as the unexplained variance , there are many classic and more recent estimators that perform well in the linear and super-linear data regime. These estimators apply to the most restrictive setting we consider, where each label y = βT x + η is given as a linear function of x plus independent noise η of variance δ2. Two common estimators for δ2 involve first computing the parameter vector ˆβ that minimizes the squared error on the n datapoints. These estimators are 1) the naive estimator or the maximum likelihood estimator: (y X ˆβ)T (y X ˆβ)/n, and 2) the unbiased estimator (y X ˆβ)T (y X ˆβ)/(n d), where y refers to the vector of n labels, and X is the n d matrix whose rows represent the n datapoints. Of course, both of these estimators are zero (or undefined) in the regime where n d, as the prediction error (y X ˆβ) is identically zero in this regime. Additionally, the variance of the unbiased estimator increases as n approaches d, as is evident in our empirical experiments where we compare our estimators with this unbiased estimator. In the regime where n < d, variants of these estimators might still be applied but where ˆβ is computed as the solution to a regularized regression (see, e.g. [16]); however, such approaches seem unlikely to apply in the sublinear regime where n = o(d), as the recovered parameter vector ˆβ is not significantly correlated with the true β in this regime, unless strong assumptions are made on β. Indeed, there has been a line of work on estimating the noise level δ2 assuming that β is sparse [9, 7, 13, 12, 2]. These works give consistent estimates of δ2 in the regime where n = Ω(k log(d)) where k is the sparsity of β. More generally, there is an enormous body of work on the related problem of feature selection.The basis dependent nature of this question (i.e. identifying which features are relevant) and the setting of sparse β, are quite different from the setting we consider where the signal may be a dense vector. There have been recent results on estimating the variance of the noise, without assumptions on β, in the n < d regime. In the case where n < d but n/d approaches a constant c 1, Janson et al. proposed the Eigen Prism [10] to estimate the noise level. Their theoretical results rely on the assumptions that the data x is drawn from an isotropic Gaussian distribution, and that the label is a linear function plus independent noise, and the performance bounds become trivial if n/d 0. The most similar work to our paper is the work of Dicker [6], which proposed an estimator of δ2 with error rate O( d n ) in the setting where the data x is drawn from an isotropic Gaussian distribution, and the label is a linear function plus independent Gaussian noise. Their estimator is fairly similar to ours in the identity covariances setting and gives the same error rate. However, our result is more general in the following senses: 1) Our estimator and analysis do not rely on Gaussianity assumptions; 2) Our results apply beyond the setting where the label y is a linear function of x plus independent noise, and estimates the fraction of the variance that can be explained via a linear function (the agnostic setting); and 3) our approach extends to the unknown non-isotropic covariance setting. In case the sparsity of β is unknown, Verzelen and Gassiat [14] introduced a hybrid approach which combines Dicker s result in the dense regime and Lasso in the sparse regime to achieve consistent estimation of δ2 using min(k log(d), p d log(d)) samples in the isotropic covariance setting where k is the unknown sparsity of β, and they showed the optimality of the algorithm. In the unknown covariance, dense β setting, they conjectured consistent estimation of δ2 is not possible with o(d) samples; our Theorem 1 shows that this conjecture is false. Finally, there is a body of work from the theoretical computer science community on testing whether a function belongs to a certain class, including work on testing linearity [3, 4] and monotonicity [8, 5]. Most of this work is in the query model where the algorithm can (adaptively) choose a point, x, and obtain its label ℓ(x), and the flavor of results is very different from the setting we consider. 2 Intuition for Sublinear Estimation We begin by describing one intuition for why it is possible to estimate the magnitude of the noise using only O( d) samples, in the isotropic setting. Suppose we are given data x1, . . . , xn drawn i.i.d. from N(0, Id), and let y1, . . . , yn represent the labels, with yi = βT xi + η for a random vector β Rd and η drawn independently from N(0, δ2). Fix β, and consider partitioning the datapoints into two sets, according to whether the label is positive or negative. In the case where the labels are complete noise (δ2 = 1), the expected value of a positively labeled point is the same as that of a negatively labeled point and is 0 . In the case where there is little noise, the expected value µ+ of a positive point will be different than that of a negative point, µ , and the distance between these points corresponds to the distance between the mean of the top half of a Gaussian and the bottom half of a Gaussian. Furthermore, this distance between the expected means will smoothly vary between 0 and 2 p 2/π as the variance of the noise, δ2, varies between 1 and 0. The crux of the intuition for the ability to estimate δ2 in the regime where n = O( d) is the following observation: while the empirical means of the positive and negative points have high variance in the n = o(d) regime, it is possible to accurately estimate the distance between µ+ and µ from these empirical means! At a high level, this is because the empirical means consists of d coordinates, each of which has a significant amount of noise. However, their squared distance is just a single number which is a sum of d quantities, and we can leverage concentration in the amount of noise contributed by these d summands to save a d factor. This closely mirrors the folklore result that it requires O(d) samples to accurately estimate the mean of an identity covariance Gaussian with unknown mean, N(µ, Id), though the norm of the mean µ can be estimated to error ϵ using only n = O( Our actual estimators, even in the isotropic case, do not directly correspond to the intuitive argument sketched in this section. In particular, there is no partitioning of the data according to the sign of the label, and the unbiased estimator that we construct does not rely on any Gaussianity assumption. 3 The Estimators, Regression Setting The basic idea of our proposed estimator is as follows. Given a joint distribution over (x, y) where x has mean 0 and variance Σ, the classical least squares estimator which minimizes the unexplained variance takes the form β = E[xx T ] 1E[yx] = Σ 1E[yx], and the corresponding value of the unexplained variance is E[(y βT x)2] = E[y2] βT Σβ. Note that this definition of β coincides with the model parameter in the case that y = βT x+η. The variance of the labels, y can be estimated up to 1/ n error with n samples, after which the problem reduces to estimating βT Σβ. While we do not have an unbiased estimator of βT Σβ, as we show, we can construct an unbiased estimator for βT Σkβ for any integer k 2. To see the utility of estimating these higher moments , assume for simplicity that Σ is a diagonal matrix. Consider the distribution over R consisting of d point masses with the ith point mass located at Σi,i with probability mass β2 i / β 2. The problem of estimating βT Σβ is now precisely the problem of approximating the first moment of this distribution, and we are claiming that we can compute unbiased (and low variance) estimates of βT Σkβ for k = 2, 3, . . ., which exactly correspond to the 2nd, 3rd, etc. moments of this distribution of point masses. Our main theorem follows from the following two components: 1) There is an unbiased estimator that can estimate the kth (k 2) moment of the distribution using only O(d1 1/k) samples. 2) Given accurate estimates of the 2nd, 3rd,. . . ,kth moments, one can approximate the first moment with error O(1/k2). The main technical challenge is the first component constructing and analyzing the unbiased estimators for the higher moments. Analyzing the variance of these unbiased estimators is quite complicated, as a significant amount of machinery needs to be developed to deal with the combinatorial number of types of cross-terms in the variance expression for the estimators. Fortunately, we are able to leverage some techniques from [11], which bounds similar looking moments (with the rather different goal of recovering the covariance spectrum). The second component of our approach leveraging estimates of the higher moments to estimate the first moment follows easily from standard results on polynomial approximation. Algorithm 1, to which Theorem 1 applies, describes our estimator in the general setting where the data has an arbitrary covariance matrix. The proof of correctness of Algorithm 1, establishing Theorem 1 is given in a self-contained form in the supplementary material. In the special case where the data distribution has identity covariance, βT Σ2β = βT Σβ simply because I2 = I, and hence we do have a simple unbiased estimator, which is constructed by Algorithm 1 by letting the input polynomial p(x) = 1. To see the intuition for the unbiased estimators of βT Σkβ computed in Algorithm 1, we examine the k = 2 case: consider drawing two independent samples (x1, y1), (x2, y2) from our linear model plus noise. Indeed, y1y2x T 1 x2 is an unbiased estimator of βT Σ2β, because E[y1y2x T 1 x2] = E[y1x T 1 ]E[y2x2] = βT Σ2β. Given n samples, by linearity of expectation, a natural unbiased estimate is hence to compute this quantity for each pair Algorithm 1 Estimating Linearity, General covariance , and degree k polynomial p(x) = Pk 2 i=0 aixi+2 that approxi- mates the function f(x) = x for all x [σmin, σmax], where σmin and σmax are the minimum and maximum singular values of the covariance of the distribution from which the xi s are drawn. Set A = XXT , and let G = Aup be the matrix A with the diagonal and lower triangular entries set to zero. Output: y T y n Pk 1 i=0 ai y T Gi+1y (of distinct) samples, and take the average of these n 2 quantities. This is precisely what Algorithm 1 computes, since E[y T Gy] = E[P i