Towards a statistical theory of data selection under weak supervision

We thank the reviewer for their thorough and insightful feedback and questions. Below we summarize the responses to weaknesses and questions.

Imperfect surrogate. It is not true that our analysis beyond Section 4 is limited to perfect surrogates.

• The analysis summarized in Section 5 (and Appendix L) covers the general case in which the surrogate model is misaligned with the true model. The strength of the surrogate model is represented by the parameter $\beta_s$ in Eq 5.2, where a perfect surrogate is a special case with $\beta_0 = || \theta_0 ||$.
• We use this theory to study the effect of surrogate model misspecification in Figure 2 and estimation error in the surrogate model in Figure 7 (Appendix L).
• Notice in particular that the panels in Figure 7 capture the qualitative behavior of Figure 1 (the “magic” effect) with comparable choices for sample size and dimension. We conclude that this theory provides a good starting point for understanding these effects.
• We also point out that the analysis of imperfect surrogates summarized in Section 5 occupies the whole appendix K.

Theorem 1. This theorem is not about adversarial examples, but random i.i.d. ones (“there exists a distribution”). Further, by inspection of the proof (Example G.2), the distribution is very simple and natural (as ‘natural’ as the Gaussian distribution). We simply take feature vectors $x_i$ that are generated as $x_i=r \cdot u_i$, where $u_i$ is uniform on the sphere, and $r$ is a scalar that is independent of $u_i$ and has a power law tail. Gaussian with identity covariance does not work for this example because (informally) 'all Gaussian vectors look the same'. In a sense, this is what makes Gaussian data an unrealistic model in many applications: they have way less variability than real data.

Dimensionality of the parameter. The theory of Section 4 accommodates for a number of parameters (indicated by $p$) different from the number of input dimensions ($d$). The theory of Section 5 assumes a generalized linear model, and therefore $p=d$.

Explaining Figure 1. The experiment settings of the Figure 1 that you described are correct. The test accuracy of the weak (strong) surrogate model is 87% (91%). Weaker models can perform better than stronger ones, depending on $N/p$, see Figure 9 Appendix O. We agree that these results are surprising. Indeed, we were motivated to work out the theory in order to demystify these results. In summary:

• The high-dimensional theory of Section 5 and Appendix L captures this phenomenon. See in particular Figures 2 and 7, where (in some of the settings) the same phenomenon is observed both under misspecification and imperfect surrogate estimation.
• Theorem 2 also proves the same phenomenon in a low-dimensional setting. (In this case the surrogate is assumed to be perfect, but it is elementary to see that using parameters estimated by a number of samples much smaller than $d$ yields the same result).
• The reason for this is that the intuition “every sample is useful” is only correct if the data distribution is perfectly matched to the loss function (e.g. logistic and logistic). As soon as this does not hold (which is the case in most real data applications), not all datapoints improve the estimation error.

Theorem 2. The theorem states that the error is strictly increasing for gamma in the interval $(\gamma_0,1)$. In particular, this means that the error at $\gamma=\gamma_0$ is strictly smaller than the error at $\gamma=1$. Recalling the definition of $\gamma$, the theorem proves that the (test) error achieved by training on subsampled data is strictly smaller than the error on the full sample ERM. We also note that:

• For brevity, we state the theorem in the form “there exists.” However, the proof is constructive and provides data distributions for which data selection improves over full sample ERM.
• As mentioned above, the same claims can be shown to hold if the surrogate model is trained on a vanishing fraction of the n samples for which labels are provided.

We also fixed the typographical error pointed by the reviewer in the updated version. Thank you for catching it.

Proposition 4.1. First of all, we apologize for the somewhat awkward formulation here. We were led to this by the attempt to defer to appendices material that is pedagogically useful, but is not novel.

Second, if the assumption is not satisfied, then the subsampling scheme is (roughly speaking) ‘much worse’ than (say) random subsampling. (Technically, the procedure is not consistent.) In other words, we could write a longer form of this proposition without this assumption, and establish that schemes that do not satisfy it are ‘very bad.’

Finally, under many models, satisfying these assumptions is fairly easy.

Proposition 4.3. Thanks, this is a typographical error, please see the updated version.

Close to $n$. Here $n$ is the target subsample size. However, since we study probabilistic data selection methods as well, we allow for the subsampled size to have small fluctuations around $n$. (We could of course eliminate these fluctuations, at the cost of making the whole paper clumsier.)

cst. Cst is the standard abbreviation for constant, which means we re-weight the samples inversely proportional to the sampling probabilities.

$\ell_{test}$. This is the loss used for testing. This needs not to be the same as for training (eg cross-entropy for training and classification for testing).

$dy$. Y is the label, $dy$ is an infinitesimal variation of y, $P(dy|x)$ is the probability distribution of the labels conditioned on feature $x$. This is standard calculus notation.

We thank the reviewer for their thoughtful feedback and questions. Below we summarize the responses to weaknesses and questions.

Presentation. We agree that some of the sections are somewhat terse, largely as a byproduct of fitting all the results within the space constraints. Any advice is welcome.

Semi-supervised learning. Semi-supervised learning addresses the same problem as the one in our paper: learning under a limited ‘labeling budget.’ However a formal comparison is at the moment difficult because of the differences between the two settings. In semi-supervised learning, the subset of labeled examples is given (not chosen algorithmically) and the learner tries to make the best use of unlabeled examples.

In our setting, we are allowed to choose which examples to label, but once this is done, learning is carried out uniquely on the labeled examples. The two models are both interesting, but motivated by different use cases.

On the other hand, we believe it should be possible (and interesting) to define a unified setting that captures both scenarios. We expect that in this setting, a mixture of the two strategies will be required.

Imperfect surrogate models. Empirically, Figure 9 in Appendix O carries out a comparison of surrogate models of different strength. Mathematically, formalizing what 'optimality' means in the context of imperfect surrogates is far from obvious. This requires formalizing the notion of uncertainty about the true model. We provides two types of rigorous results for imperfect surrogates:

• Low-dimensional. This is mainly contained in Appendix K and summarized in Section 4.5. In particular, we prove that using a weaker model can yield better data selection (in minimax sense) than using the perfect surrogate (See Theorem 7 and Example K.2).
• High-dimensional. This is mainly contained in Appendix L and summarized in Section 5. In this case we fix an imperfect surrogate and associated data selection procedure, and characterize the resulting generalization error of data learned on data selected by that procedure (See Theorems 4 and 8). We study the effect of surrogate model misspecification (Figure 2) and estimation error in the surrogate model (Figure 7).

We thank the reviewer for their thoughtful feedback and questions. Below we summarize the responses to weaknesses and questions.

Non-convexity and related questions. We present two sets of results:

• Low-dimensional asymptotics: These are not limited to convex methods, but they do assume that the global optimizer is used for estimation.
• High-dimensional asymptotics: these assume a (generalized) linear model, and convex loss.

The referee raises an interesting question, which we rephrase as:

"What is the impact of data selection on the global optimization landscape in non-convex settings?"

This is a very difficult question and indeed more basic questions are widely open in non-convex statistical settings. A few remarks:

• If subsampling is unbiased then we expect that uniform convergence results for the landscape [e.g. Mei, Bai, Montanari Ann. Stat. 2018] can be applied to show that the whole landscape under subsampling is 'as good as' the original one.
• For biased subsampling, the same uniform convergence results will imply that the landscape can be characterized in terms of a certain 'modified population landscape'. The latter can be 'worse' or 'better' than the original landscape, and which one will depend on a case-by-case analysis.
• For models outside the uniform convergence regime (e.g. highly overparameterized models) the above arguments will not apply, but uniform convergence of the landscape is often too strong of a requirement, and convergence in a neighborhood of the optimization trajectory is sufficient.

Overall, we think there is some promise for extending the present results to capture the effects of data selection on non-convex optimization.

Dependency on estimated parameters. Indeed, some of our estimates depend on unobserved parameters (as pointed out in Remark C.1). However, empirical versions of these quantities can be plugged in. Under the stated assumptions, corrections due to this preplacement are negligible. We refrain from making this explicit at each passage uniquely to avoid further notational burden.

Known labels. Our experience is that our weakly supervised approach compares well with data selection methods that make use of the actual labels. If the reviewer has in mind a specific algorithm of this type that would be meaningful to use as a benchmark, we would be interested in carrying out a comparison.