On the Provable Advantage of Unsupervised Pretraining
Authors: Jiawei Ge
Shange Tang
Jianqing Fan
Chi Jin
Venue: ICLR 2024 spotlight (2024)
Keywords: unsupervised pretraining; representation learning; sample complexity
Primary area: learning theory

Abstract: Unsupervised pretraining, which learns a useful representation using a large amount of unlabeled data to facilitate the learning of downstream tasks, is a critical component of modern large-scale machine learning systems. Despite its tremendous empirical success, the rigorous theoretical understanding of why unsupervised pretraining generally helps remains rather limited---most existing results are restricted to particular methods or approaches for unsupervised pretraining with specialized structural assumptions. This paper studies a generic framework,
where the unsupervised representation learning task is specified by an abstract class of latent variable models $\Phi$ and the downstream task is specified by a class of prediction functions $\Psi$. We consider a natural approach of using Maximum Likelihood Estimation (MLE) for unsupervised pretraining and Empirical Risk Minimization (ERM) for learning downstream tasks. We prove that, under a mild ``informative'' condition, our algorithm achieves an excess risk of $\\tilde{\\mathcal{O}}(\sqrt{\mathcal{C}\_\Phi/m} + \sqrt{\mathcal{C}\_\Psi/n})$ for downstream tasks, where $\mathcal{C}\_\Phi, \mathcal{C}\_\Psi$ are complexity measures of function classes $\Phi, \Psi$, and $m, n$ are the number of unlabeled and labeled data respectively. Comparing to the baseline of $\tilde{\mathcal{O}}(\sqrt{\mathcal{C}\_{\Phi \circ \Psi}/n})$ achieved by performing supervised learning using only the labeled data, our result rigorously shows the benefit of unsupervised pretraining when $m \gg n$ and $\mathcal{C}\_{\Phi\circ \Psi} > \mathcal{C}\_\Psi$. This paper further shows that our generic framework covers a wide range of approaches for unsupervised pretraining, including factor models, Gaussian mixture models, and contrastive learning.

Published as a conference paper at ICLR 2024
ON THE PROVABLE ADVANTAGE OF UNSUPERVISED PRETRAINING
Jiawei Ge Shange Tang
Jianqing Fan
Chi Jin
ABSTRACT
Unsupervised pretraining, which learns a useful representation using a large amount of unlabeled data to facilitate the learning of downstream tasks, is critical component of modern large-scale machine learning systems. Despite its tremen- dous empirical success, the rigorous theoretical understanding of why unsuper- vised pretraining generally helps remains rather limited most existing results are restricted to particular methods or approaches for unsupervised pretraining with specialized structural assumptions. This paper studies a generic framework, where the unsupervised representation learning task is specified by an abstract class of latent variable models & and the downstream task is specified by class of predic- tion functions Estimation (MLE) for unsupervised pretraining and Empirical Risk Minimization (ERM) for learning downstream tasks. We prove that, under a mild "informa- tive" condition, our algorithm achieves an excess risk O(VCo/m /mm + /Cu /n) for downstream tasks, where Cg., Cy are complexity measures of function classes Φ, V,, and m, n. are the number of unlabeled and labeled data respectively. Com- paring to the baseline of ( ///..//// achieved by performing supervised learn- ing using only the labeled data, our result rigorously shows the benefit of unsu- pervised pretraining when m > n and Crov > Cv. This paper further shows that our generic framework covers wide range of approaches for unsupervised pretraining, including factor models, Gaussian mixture models, and contrastive learning.
consider a natural approach of using Maximum Likelihood
INTRODUCTION
Unsupervised pretraining aims to efficiently use large amount unlabeled data to learn a useful representation that facilitates the learning of downstream tasks. This technique has been widely used in modern machine learning systems including computer vision (Caron et al., 2019; Dai et al., 2021), natural language processing (Radford et al., 2018; Devlin et al., 2018; Song et al., 2019) and speech processing (Schneider et al., 2019; Baevski et al., 2020). Despite its tremendous empirical success, it remains elusive why pretrained representations, which are learned without the information of downstream tasks, often help to learn the downstream tasks.
There have been several recent efforts trying to understand various approaches of unsupervised pretraining from theoretical perspectives, including language models Saunshi et al. (2020); Wei al. (2021), contrastive learning Arora et al. (2019); Tosh al. (2021b;a); HaoChen et al. (2021); Saunshi et al. (2022), and reconstruction-bart this line of works justifies the use of unsupervised pretraining in the corresponding regimes, many of them do not prove the advantage of unsupervised learning, in terms of sample complexity, even when compared the naive baseline of performing supervised learning purely using the labeled data. Furthermore, these results only apply to particular approaches of unsupervised pretraining considered in their papers, and crucially rely on the specialized structural assumptions, which do not generalize beyond the settings they studied. Thus, we raise the following question: Can we develop
self-supervised learning Lee et al. (2021). While
"equal contribution
Department of Operations Research (ig5300, shangetang Department of Electrical and Computer Engineering, Princeton University; chi jēpri inceton..e. edu
Financial
Engineering,
Princcton
University;
edu

---

Published as a conference paper at ICLR 2024
generic framework which provably explains the advantage of unsupervised pretraining? This paper answers this highlighted question positively.
We consider the generic setup where the data and its label y are connected by an unobserved representation z. Concretely, we assume (x, 2) is sampled from a latent variable model o* in an abstract class Φ, and the distribution of label conditioned on representation is drawn from dis- tributions 3/" in class VD We consider a natural approach of using Maximum Likelihood Estimation (MLE) for unsupervised pretraining, which approximately learns the latent variable model o" using w unlabeled data. We then use the results of representation learning and Empirical Risk Minimiza- tion (ERM) to learn the downstream predictor u using n labeled data. We remark that MLE is one of the most important underlying principle for designing unsupervised learning algorithms large number of modern unsupervised pretraining algorithms compute MILE or its proxies (such as optimizing the variational lower hound) due to computational constraints. These examples include contrastive learning (see Section 6), Variational AutoEncoder (VAE) (Kingma & Welling, 2013) and diffusion model
Dicksteick al., 2015). Investigating this generic setup allows us to bypass the limitation of prior works that are restricted to the specific approaches for unsupervised pretraining.
We prove that, under a mild "informative" condition (Assumption 3.2), our algorithm achieves /m + / /Cy /n) for downstream tasks, where Cs., Cy. complexity mea- sures of function classes D, V. and m, n are the number of unlabeled and labeled data respectively. Comparing to the baseline of O ///oo///n achieved by performing supervised learning using only the labeled data, our result rigorously shows the benefit of unsupervised pretraining when we have abundant unlabeled data m > n and when the complexity of composite class Coow is much greater than the complexity of downstream task alone Cy.
excess risk of Ō ((VCo// /
Our generic framework enables a simple and standardlized approach to understand and analyze a wide range of unsupervised pretraining models. Consider the scenario where a new model of unsu- pervised pretraining is proposed, and we would like to evaluate the effectiveness of this pretraining method. We can directly apply our framework to compute the "informative" condition presented in this paper, providing concrete starting point for analysis. If the "informative" condition is satisfied, our main results are directly applicable.
Finally, we highlight that our generic framework (including the "informative" condition) captures a wide range of setups for unsupervised pretraining. We underscore this applicability with three concrete examples, including (1) factor models with linear regression as downstream tasks; (2) Gaussian mixture models with classification as downstream tasks; and (3) Contrastive learning with linear regression as downstream tasks.
1.1 RELATED WORK
Applications and methods for unsupervised pretraining. Unsupervised pretraining has achieved tremendous success in image recognition (Caron et al., 2019), objective detection (Dai et al., 2021), natural language processing (Devlin et al., 2018; Radford et al., 2018; Song et al., 2019) and speech recognition (Schneider al., 2019; Baevski et al., 2020). Two most widely-used pretraining ap- proaches are (1) feature-based approaches (Brown et al., 1992; Mikolov et al., 2013; Melamud al., 2016; Peter et al., 2018), which pretrains a model extract representations and directly uses the pretrained representations as imputs for the downstream tasks; (2) fine-tuning based approaches, (see, e.g., Devlin et al., 2018), which fine-tunes all the model parameters in the neighborhood of pretrained representations based on downstream tasks. Erhan et al. (2010) provides the first em- pirical understanding on the role of pretraining. They argue that pretraining serves as form of regularization that effectively guides the learning of downstream tasks.
majority of settings where pretraining is used fall into the category of semi-supervised learning (see, e.g., Zhu, 2005), where large amount of unlabeled data and a small amount of labeled data are observed during the training process. Semi-supervised learning methods aim to build a better predictor by efficiently utilizing the unlabeled data. Some traditional methods include: generative models (e.g. Ratsaby& & Venkatesh, 1995), low-density separation (Joachims et al., 1999; Lawrence & Jordan, 2004; Szummer & Jaakkola, 2002), and graph-based methods (Belkin et al., 2006). While most works in this line propose new methods and show favorable empirical performance, they do not provide rigorous theoretical understanding the benefit of unsupervised pretraining.
2

---

Published as a conference paper at ICLR 2024
Theoretical understanding of unsupervised pretraining. Recent years witness surge of theoret- ical results that provide explanations for various unsupervised pretraining methods that extract rep- resentations from unlabeled data. For example, (Saunshi et al., 2020; Wei et al., 2021) considers pre- training vector embeddings in the language models, while (Arora et al., 2019; Tosh et al., 2021b;a; HaoChen al., 2021; Saunshi et al., 2022; Lee al., 2021) consider several Self- Sure-rieee Learn- ing (SSL) approaches for pretraining. In terms of results, Wei et al. (2021) shows that linear predictor on the top of pretrained languange model can recover their ground truth model; Arora et al. (2019); Saunshi et al. (2020); Tosh et al. (2021b;a); Saunshi et al. (2022) show that the prediction loss of downstream task can be bounded by the loss of unsupervised pretraining tasks. These two lines of results do not prove the sample complexity advantage of unsupervised learning when compared to the baseline of performing supervised learning purely using the labeled data.
The most related results are Lee et al. (2021); HaoChen et al. (2021), which explicitly show the sample complexity advantage of certain unsupervised pretraining methods. However, Lee et al. (2021) focuses on reconstruction--asee SSL, and critically relies a conditional independency assumption on the feature and its reconstruction conditioned on the label; HaoChen et al. (2021) considers contrastive learning, and their results relies deterministic feature map and the spectral conditions of the normalized adjacency matrix. Both results only apply to the specific setups and approaches of unsupervised pretraining in their papers, which do not apply other setups in general (for instance, the three examples in Section 4, 5, 6). On the contrary, this paper develops a generic framework for unsupervised pretraining using only abstract function classes, which applies to a wide range of setups.
Other approaches for representation learning. There is another line of recent theoretical works that learn representation via multitask learning. Baxter (2000) provides generalization bounds for multitask transfer learning assuming a generative model and a shared representation among tasks. Maurer et al. (2016) theoretically analyses a general method for learning representations from mul- titasks and illustrates their method in a linear feature setting. Tripuraneni et (2021); Du et al. (2020) provide sample efficient algorithms that solve the problem of multitask linear regression. Tripuraneni et al. (2020) further considers generic nonlinear feature representations and shows sam- ple complexity guarantees for diverse training tasks. Their results differ from our work because they learn representations by supervised learning using labeled data of other tasks, while our work learns representations by unsupervised learning using unlabeled data.
2 PROBLEM SETUP
Notation. We denote by F(x) and p(z) the cumulative distribution function and the probability density function defined on E X, respectively. We define [n] = f1.2..... .n.. The cardinality of set A is denoted by [A|. Let || - 112 be the &g norm of vector or the spectral norm of a matrix. We denote by || ||| the Frobenius norm of matrix. For a matrix M E Rmxx we denote by mmin (min(M) and a mmax (M) ) the smallest singular value and the largest singular value of M, respectively. For two probability distributions P, and Fz. we denote the Total Variation (TV) distance and the Hellinger distance between these two distributions by dTv(P11)))
and H (PP), respectively.
We denote by x E X and y E y the input data and the objective of the downstream tasks, respec- tively. Our goal is to predict y using We assume that x is connected to y through an unobserved latent variable 2 E Z (which is also considered as representation of z). Given the latent variable 2, the data and the objective y are independent of each other. Latent variable structure is general in statistics (for example, the hidden categories and low dimension factors) and applies to most unsu- pervised learning models (including contrastive learning, auto-encoder, etc). To incorporate large class of real-world applications, such as contrastive learning, we consider the setup where learning can possibly have access to some side information
S. We assume that (I, 8, 2) P. (I, 82 2) and y|2 ~ P.- (y|z), where Po- and I... are distributions indexed by o* E & and g/ E V. It then holds that Par.g- (I. v) J P' (I, 2)P (y]z) dz.
Let (((,-) be a loss function. For any pair (Ø, v² E & x W, the optimal predictor I6.8 is defined as follows.
Po.v +- arg min, Er,,, [((((x)))] v)]: where the minimum is taken on all the possible functions and EP = ((e.)) Our prediction function class is therefore given by Go.v (gs T 1b E v).
(1)
3

---

Published as a conference paper at ICLR 2024
Algorithm Two-Phase MLE+ERM
1: Input: (#i, 8:) (z Vj 11
2: Use unlabeled data and its corresponding side information {xi, 8: 8t) to learn ò via MLEE
e + arg sa
Σx= log Pa(a,, s,).
(3)
3: Fix e and use labeled data {azz y 1ー= to learn via ERM:
+ arg min Ej=1 (gā (zz).
(4)
Our framework covers the standard setup (e.g., in large language models) which uses large mount unlabeled data to pretrain a deep neural network as representation, and then uses small amount of labeled data to only fine-tunes the linear head for downstream tasks. Concretely, consider the setting where ((;-)) .) the squared loss and y = 3² + E, where ε NN(0, a²) is a Gaussian noise independent of z. Then the optimal predictor gø. (x) = Ep [u|æ] = 3 Er,rr,,=l and the
prediction function class Gg.v { [2[x=] ø E o, 8, ) Here, Ez, [=|x]] corresponds to the
representation learned by deep networks, and is the parameter of the linear head.
Given an estimator pair (Ø, } we define the excess risk with respect to loss e(.,)) as
Errore(0; à) = ,.. [K (x),
Er [e(gor . (x),
where 6* and v6" are the ground truth parameters. By the definition of -o we have Error(ă, (ā, ) 2 0. We aim learn an estimator pair (Ø) 3) from data that achieves smallest der of the excess risk.
We consider the setting where the latent variable cannot be observed. Specifically, many unlabeled data and its corresponding side information {a;, 8; | that are sampled i.i.d from an unknown distribution P P-- (2. s) and only few labeled data {zz, プy 1 that sampled i.i.d (also independent with the unlabeled data) from unknown distribution IP Pf+ (0
given
Learning algorithm. We consider natural learning algorithm consisting of two phases (Algo- rithm 1). In the unsupervised pretraining phase, we use MLE to estimate ø² based on the unlabeled data s, {,);, In the downstream tasks learning phase, we use ERM to estimate z based on pretrained & and the labeled data {z,, 4 See algorithm for details.
We remark that another natural learning algorithm in our setting is to use a two-phase MLE. To be specific, in the unsupervised pretraining phase, we use MLE to estimate o" based on the unlabeled data {ær, s; ) as (3). In the downstream tasks learning phase, we again use MLE to estimate 3² show that this two-phase
based pretrained ò and the labeled data {æ,z y/ 1 However, MLE scheme fails in the worst case. See Appendix E for the details.
Complexity measures. Sample complexity guarantee for Algorithm will be phrased in terms of three complexity measurements, i.e., bracketing number, covering number and the Rademacher complexity, which are defined as follows. We denote by (x( : {po(z) [ E Φ) a set of parameterized density functions (x) defined on z E X, where Ø E + is the parameter.
Definition 2.1 (e-Bracket and Bracketing Number). Let > 0. Under || || distance, set of functions N (P) e) an e-brccktt of ( if for any Ps (x) E (x) there exists function = (=)())
such that: (1)p(()) 2 (2),,, Vz E X: (2) e) .)) needed cover (T). The entropy is defined as the logarithm of the bracketing number.
(x) E (Px
(x)) dr < e. The bracketing number N (Px(#),
is the cardinality of the smallest e-bracket
To measure the complexity of function class, consider the covering number and the Rademacher complexity defined as follows.
Definition 2.2 (e-Cover and Covering Number). Let JF be function class and (F, (111 6,,,ell Il []) is called an e-cover of J if for any ʃ E F.
)) be a metric
space. For each >> 0, set of functions N(F,6,
4

---

Published as a conference paper at ICLR 2024
there exists function 9 E (FF II- such that 9 I defined as the cardinality of the smallest c-cover needed to cover F.
The covering number (JF, || .I)
Definition 2.3 (Rademacher Complexity). Suppose that T1,.....
sampled i.id from proba- bility distribution D defined on a set X. Let & be a class of functions mapping from X' to I. The empirical Rademacher complexity of g is defined follows,
Zn Zn
R2 (G) == ~Ui()t) supgeg ahe E ow)
The Rademacher complexity of G is defined as (G) = B[a (9)].
MAIN RESULTS
In this section, first introduce mild "informative" condition for unsupervised pretraining. We show this "informative" condition is necessary for pretraining to benefit downstream tasks. We then provide our main results-statistical guarantees for unsupervised pretraining and downstream tasks for Algorithm 1. Finally, in Section 3.1, we generalize our results to a more technical but weaker version of the "informative" condition, which turns out to be useful in capturing our third example of contrastive learning (Section 6).
Informative pretraining tasks. We first note that under our generic setup, unsupervised pretrain- ing may not benefit downstream tasks at all in the worst case if no further conditions are assumed. Proposition 3.1. There exist classes (9, v as in Section 2 such that, regardless of unsupervised pretraining algorithms used, pretraining using unlabeled data provides no additional information towards learning predictor "*"
Consider the latent variable model = = Ax, where x ~ NO0 Ia). A E is the parameter of the model. Then, matter how many unlabeled {a,} have, we can gain information of A from the data! In this case, unsupervised pretraining is not beneficial for any downstream task.
Therefore, it's crucial to give an assumption that guarantees our unsupervised pretraining is informa- tive. As a thought experiment, suppose that in the pretraining step, we find an exact density estimator á for the marginal distribution of x, i.e., Pá P3 s) = P& (I, s) holds for every I. 8. We should ex- pect that this estimator also fully reveals the relationship between and 2, i.e., Pa (2, 2) P (z, 2) holds for every z, 2. Unfortunately, this condition does not hold in most practical setups and is often too strong. As an example, consider Gaussian mixture models, where E [K] is the cluster that data point x E Rd belongs since a permutation of = makes no difference in the marginal distribution of x. However, notice that in many circumstances, a permutation of the class label will not affect the downstream task learning. In these cases, a permutation of the clusters is allowed. Motivated by this observation, we introduce the following informative assumption which allows certain "transformation" induced by the downstream task:
Then in this case, it is impossible for us ensure P: (2 2) Pa- (ar, 2),
Assumption 3.2 -inforrnreee condition). We assume that the model class is x -inforrmmaivee
with respect to a transformation group Te. That is, for any o,, there exists Ti E Ta such that drv (Pn (1,, IP, (x, =)) S K drv (P& s), PP s)).
(5)
Here ø² is the ground truth parameter. Furthermore, we assume that Ta is induced by transformation group Ty on V. i.e., for any Ti Tg. there exists T2 Ty such that for any (ò, +) V, (X,(() = 1 T (x, y).
Under Assumption 3.2, if the pretrained & accurately estimates the marginal distribution of xr, up to high accuracy, then it also reveals the correct relation between and representation up some transformation T4 which is allowed by the downstream task, which makes it possible to learn the downstream task using less labeled data.
Proposition 3.1 shows that the informative condition is necessary for pretraining to bring advantage since the counter example in the proposition is precisely O-informative. We will also show this informative condition is rich enough to capture a wide range of unsupervised pretraining methods in Section 4, 5, 6, including factor models, Gaussian mixture models, and contrastive learning models.
5

---

Published as a conference paper at ICLR 2024
Guarantees for unsupervised pretraining. Recall that (x) = (po(x, E D). We have the following guarantee for the MLE step (line 2) of Algorithm
Theorem 3.3. Let å be the maximizer defined in (3). Then, with probability at least 1 - 8, we have
log N (1xxxxx(()) )
drv (F (2,, s). Por (z. 8)) - 31
m
where N11 is the bracketing number as in Definition 2.
Theorem 3.3 claims that the TV error in estimating the joint distribution of (x. 8) decreases as D(Co/m) where is the number of unlabeled data, and Co log Ni (Pxxxxx()), 1/m) measures the complexity of learning the latent variable models d. This result mostly follows from standard analysis of MLE (Van de Geer, 2000). We include the proof in Appendix A. for completeness.
Guarantees for downstream task learning. In practice, we can only learn an approximate down- stream predictor using small amount of labeled data. We upper bound the excess risk of Algorithm as follows.
Theorem 3.4. Let and & be the outputs of Algorithm 1. Suppose that the loss function yxy- R is L-bounded and model is x -informattve Then, with probability at least 1 6, the excess risk of Algorithm is bounded as:
1 log
2N (Pxxs 1/m)
2 4 8" + +2L
Error: .) max (e (Lo Go.v) 12xL ΦED
V
V
log
Here (.) denotes the Rademacher complexity, and i Go.v = = ((()))())))) x y
[-L, L] a E V}.
Note that the Rademacher complexity a function class can be bounded by its metric entropy. We then have the following corollary. Corollary 3.5. Under the same preconditions as Theorem 3.4, we have:
log N(e o Go.v L/ n. 11
2
4 0
Errorz(o, b) S čmax L ΦED
+ 2
log
71
2N (
x x ( 1), 1/m)
+ +1kkL
log
8
where ē is an absolute constant, (FF, (1~)) ) is the 8 8-covering number of function class F with respect the metric || 11.0-
By Corollary 3.5, the excess risk of our Algorithm is approximately OC/C//m++ /t /n), where Ca and Cy. are roughly the log bracketing number of class & and the log covering number of v. Note that excess risk for the baseline algorithm that learns downstream task using only labeled data is O(VCoov/ni where Coov the log covering number of composite function class V. In many practical scenarios such training linear predictor on top of a pretrained deep neural networks, the complexity Crow much larger than Cg. We also often have significantly more unlabeled data than labeled data (m >>> ni). In these scenarios, our result rigorously shows the significant advantage of unsupervised pretraining compared to the baseline algorithm which directly performs supervised learning without using unlabeled data.
3.1 GUARANTEES FOR WEAKLY INFORMATIVE MODELS
We introduce a relaxed version of Assumption 3.2, which allows us to capture richer class of examples.
Assumption 3.6 (K we="-weaaky-ifformmaiie condition). We assume model ( V) is x --eekkly- informative, that is, for any á E 4, there exists E V such that
drv
P. Po- s (x. v)) S K ())
(7)
Here denote by d², 4 the ground truth parameters.

---

Published as a conference paper at ICLR 2024
Assumption 3.6 relaxes Assumption 3.2 by making two modifications: (i) replace the LHS of (5) by the TV distance between the joint distribution of (æ, y); (ii) replace the TV distance on the RHS by the Hellinger distance. See more on the relation of two assumptions in Appendix A.4.1.
In fact, Assumption 3.6 sufficient for us to achieve the same theoretical guarantee as that in Theorem 3.4. Theorem 3.7. Theorem 3.4 still holds under the x
- -weakly-informattie assumptions.
The proof of Theorem 3.7 requires stronger version of MLE guarantee than Theorem 3.3, which guarantees the closeness in terms Hellinger distance. We leave the details Appendix A.4.
PRETRAINING VIA FACTOR MODELS
In this section, instantiate theoretical framework using the factor model with linear regres- sion as a downstream task. Factor model (see, e.g., Lawley & Maxwell, 1971; Forni et al., 2005; Fan al., 2021) is widely used in finance, computational biology, and sociology, where the high- dimensional measurements are strongly correlated. We rigorously show how unsupervised pretrain- ing can help reduce sample complexity in this case.
Model Setup. For the latent variable model, we consider the factor model as follows.
Definition 4.1 (Factor Model). Suppose that we have d-dimensional random vector whose de- pendence driven by r factors x (d >> r). The factor model assumes x = B" 2 + J4, where B" is a x factor loading matrix. Here μ N (0, La) is the idiosyncratic component that uncorrelated with the common factor z ~ NO, I,). We assume that the ground truth parameters B E B, where [B e dd ||B||2 D} for some
0.
For the downstream task, we consider the linear regression problem y = 3 2 + v, where v ~ (0,, is Gaussian noise that is uncorrelated with the factor and the idiosyncratic component J.. We assume that the ground truth parameters 3 E C, where C == {B E IR." ||@1|2 < D} for some D 0. The latent variable model (i.e., L) and the the prediction class (i.c., ) are then represented by B and C. respectively. In the sequel, we consider the case where no side information is available, i.e, we only have access to i.i.d unlabeled data m ) and i.i.d labeled data {I, yj --1 For
regression models, it is natural to consider the squared loss function E(z, y) = (y x)?.
Informative condition. We first show that Assumption 3.2 holds for the factor model with linear regression as downstream tasks. The idea of the factor model is to learn ow-dimensional repre- sentation 2, where rotation over is allowed since in the downstream task, we can also rotate / to adapt to the rotated 2.
Lemma 4.2. Factor model with linear regression downstream tasks is k -in-forrmmaieee where K = C1 (o + ()a(a") Here e₁ is some absolute constants, o'ax and o'iin are the largest and smallest singular value of B", respectively.
Theoretical results. Recall that in Theorem 3.4, we assume a L-bounded loss function to guaran- tee the performance of Algorithm 1. Thus, instead of directly applying Algorithm to the squared loss function, we consider Algorithm with truncated squared loss, i.e.,
((..y) == (y - 2²)² ((==))=L) L 1. ((x=))>>L)-
(8)
Here L is a carefully chosen truncation level. To be more specific, in the first phase, we still use MLE to learn an estimator B as that in line 2 of Algorithm 1. In the second phase, we apply ERM to the truncated squared loss to learn an estimator 3. We then have the following theoretical guarantee. Theorem 4.3. We consider Algorithm with truncated squared loss (8) with (D2 + 1) log Let B, B be the outputs of Algorithm 1. Then, factor models with linear regression as downstream tasks, with probability at least 1 5, the excess risk can be bounded follows,
( < ō ( dr/m LVT/n).
where is defined in the sets B and C, and k is specified in Lemma 4.2. Here Ō(-) omits absolute constants and the polylogarithmic factors in m, d, D, 1/5.

---

Published as a conference paper at ICLR 2024
Notice that the rate obtain in Theorem 4.3 is not optimal for this specific task: by the nature of squared loss, if we consider a direct d dimensionnl linear regression (from x to y) with n data, we can usually achieve the fast rate, where excess risk decreases as ((d/n) n.). To fill this gap, we consider Algorithm with क Rdxr and Vp R and denote D == max { [3 || l12]- Following more refined analysis, could achieve sharper risk rate that scales as ( m r//n), which is much better than the usual linear regression when y7 > n. See Appendix B.5 for details.
5 PRETRAINING VIA GAUSSIAN MIXTURE MODELS
In this section, we show how pretraining using Gaussian Mixture Models (GMMs) can benefit the downstream classification tasks, under our theoretical framework.
Model setup. For the latent variable model, we consider a dddimenssionll GMM with K compo- nents and equal weights. To be specific, the latent variable that represents the cluster is sampled uniformly from [K]. In each cluster, the data is sampled from a standard Gaussian distribution, i.e., a/ = i ((t. Ta) for any i E [K]. It then holds that r Σ K-IN(u,, Ia)- We denote by the parameter space with each element consisting K centers (d-dimensional vectors).
We assume that the set of parameters U satisfies the normalization condition- ttere exists D > 0 such that for any u {w, ] U, we have ||u,]|2 < DydTog K, Vi E [K]. We further assume the ground-truth centers {u, j=z E U satisfy the following separation condition.
Assumption 5.1 (Separation condition). The true parameters {uā y= l satisfies ||u -u]l2 / K, Vi j.
For the downstream task, we consider the binary classification problems with label E {0, 1]. We denote by the set of 2 classifiers such that for each & E V, and any [K]. we have either (v = 1/= i)
where represents the noise. Then, latent variable model and the prediction class are represented by U and V, respectively. In the sequel, we consider the case where side information is available, i.c., only have access to i.i.d
or (v 0|z = i) = 1
Im and i.dd labeled data {æ,, 3/ 1y1 For classification problems, is natural to consider the 0 - loss function f(x, y) = 1 (x*u) which bounded by 1.
unlabeled data {
Informative condition. We prove that Assumption 3.2 for the above model. We have the follow- ing guarantee.
Lemma 5.2. Let Lē
= {u e U d Pa- (z)) S 1/(4K)}. Under Assumption 5.1, GMMs with parameters in'l is (1))-informativee with respect to the transformation group induced by down- stream classification tasks.
Theoretical results
We have the following theoretical guarantee.
Theorem 5.3. Let ú, & be the outputs of Algorithm 1. Suppose that Assumption 5.1 holds and m = 3) Then, for the Gaussian mixture model with classification as downstream tasks, with probability least 8, the excess risk can be bounded as follows,
Error 3) S S <VVdk/mm++ vK/n)
Here Ö(-) omits some constants and the polylogarithmic
m, d, K, D, 1/5.
Theorem 5.3 shows the power of unsupervised pretraining under this setting in the following sense: Note that the number of parameters of a GMM is dK, therefore if we directly do classification without unsupervised pretraining, the risk will scale as O(/dK/nn) When d is large and m > n, we achieve better risk bound than supervised learning that only uses the labeled data.
6 PRETRAINING VIA CONTRASTIVE LEARNING
In this section, we show how pretraining through contrastive learning (learning the embedding func- tion) benefit the downstream linear regression tasks under our theoretical framework.
8

---

Published as a conference paper at ICLR 2024
In the setting of contrastive learning, assume that and æ' are sampled in- dependently from the same distribution P(x)). The similarity between x and x' is captured by a representation function fo- : X R' in the following sense,
Model setup.
Pt 1 |,, = (1 + e- for (x) fz)= (10)1- P(t = -1 12, = (1 + ef (z) fo- (=)))-1
Here is a random variable that labels the similarity between x and x'. If the data pair (x, x²) is similar, then í tends to be 1. If the data pair (xx x²) is not similar (negative samples), then t tends to -. We assume (x, 1 ~ IP fo- (2, t). Here, (x', 4) can be viewed as side information. where I,) is Gaussian noise that is
The latent variable is defined uncorrelated with æ. We denote (zx, 2) P (z,
= for (x)
For the downstream task, we consider the linear regression problem y = 3 v, where y ~ (O, 1) is a Gaussian noise. We assume that the true parameters 0 E O and 3 E B, which satisfy standard normalization assumption, i.e., [[ S for any 0 E θ and x E X' and || I for any B B. We have access to i.i.d unlabeled data {a;; 24,, 1 and i.idd labeled data (zj. 1 1-1 Here (14,, 14) is the side information corresponding to Ti. In the sequel, consider the same form of truncated squared loss as in (8).
Weakly informative condition. We first prove that the above model satisfies Assumption 3.6: Lemma 6.1. Contrastive learning with linear regression downstream tasks is k weakly- informative, where K = C3 . -1/2 (Elfe- fx) (x)"1). Here c3 is an absolute constant.
x' Theoretical results. We define set of density functions Pxxs((F) (x, E O). We then have the following theoretical guarantee.
Theorem 6.2. We consider Algorithm with truncated squared loss (8) where L 36(D² D2 + 1) log n. Let O.F 33 be the outputs of Algorithm Then, for contrastive learning with linear regression as downstream tasks, with probability at least 1 6, the excess risk can be bounded as follows,
Error,(0,3) Ô (KL log Nu (Pxxss((FF)) 1/m²)
+L + H
m
where L 36(D² + 1) log n and is specified in Lemma 6.1. Here O() omits some constants and the polylogarithmic factors 1/5.
Note that the excess risk of directly training with labeled data strongly depends the complexity of the function class Fo. In the case that >>> n, the excess risk of Theorem 6.2 scales as Ó (1/),,), which beats the pure supervised learning if the complexity of Fo quite large. Thus, the utility of unsupervised pretraining is revealed for contrastive learning.
When applying our generic framework to the specific context of contrastive learning, our result morally aligns with that in HaoChen al. (2021), albeit with differing assumptions. In Theorem 4.3 of HaoChen et al. (2021), the risk is characterized by the cigenvalues of an adjacency matrix À whose elements measure the similarity between data pairs. As a counterpart, our excess risk min (B[fo-(x) (x))), where Eifs- (x).f= (x)²² also plays the
incorporates the quantity k -1/2 role of measuring the similarity. Notably, our generic framework covers variety of approaches for unsupervised pretraining, extending beyond just contrastive learning.
7 CONCLUSIONS
This paper proposes a generic theoretic framework for explaining the statistical benefits of unsu- pervised pretraining. We study the natural scheme of using MLE for unsupervised pretraining and ERM for downstream task learning. We identify a natural "informative" condition, under which our algorithm achieves an excess risk bound that significantly improves over the baseline achieved by purely supervised learning in the typical practical regimes. We further instantiate our theoretical framework with three concrete approaches for unsupervised pretraining and provide corresponding guarantees.

---

Published as a conference paper at ICLR 2024
REFERENCES
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural com- plexity and representation learning of low rank mdps. Advances neural information processing systems, 33:20095-20107, 2020.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.092229 2019.
Alexei Baevski, Yuhao Zhou, Abdelrahman Mohamed, and Michael Auli. wav2vec 2.0: A frame- work for self-supervised learning of speech representations. Advances Neural Information Processing Systems, 33:12449-1222 124600 2020.
J. Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12:149 198, mar 2000. doi: 10.1613/jain.33. URL https: http://i.oogoo../////o htt.://1111111111111
161322F jair. 731.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, 7 (11), 2006.
Peter Brown, Vincent Della Pietra, Peter V Desouza, Jennifer C Lai, and Robert L Mereer. Class- based n-gram models of natural language. Computational linguistics, 18(4):467-480, 1992.
Mathilde Caron, Piotr Bojanowski, Julien Mairal, and Armand Joulin. Unsupervised pre-training of image features on non-curated data. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 9959-2968, 2019.
Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. 2021.
Zhigang Dai, Bolun Cai, Yugeng Lin, and Junying Chen. Up-detr: Unsupervised pre-training for object detection with transformers. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1601-1610, 2021.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Lue Devroye, Abbas Mehrabian, and Tommy Reddad, The total variation distance between high- dimensional gaussians. arXiv preprint
181000669, 2018.
Simon Du, Wei Hu, Sham M Kakade, Jason Lee, and Qi Lei. Few-shot learning via learning 2020.
the representation, provably. arXiv preprint arXiv:2002.099:
Dumitru Erhan, Aaron Courville, Yoshua Bengio, and Pascal Vincent. Why does unsupervised pre-
training help deep learning? Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 201-208. JMLR Workshop and Conference Proceedings, 2010.
Jianqing Fan, Kaizheng Wang, Yiqiao Zhong, and Ziwei Zhu. Robust high dimensional factor models with applications to statistical machine learning. Statistical science: a review journal of the Institute of Mathematical Statistics, 36(2):303, 2021.
Mario Forni, Marc Hallin, Marco Lippi. and Lucrezia Reichlin. The generalized dynamic factor model: one-sided estimation and forecasting. Journal of the American statistical association, 100 (471):830-8A4) 2005.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- self-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-5011, 2021.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint 190iv:1902.0377 2019.
10

---

Published as a conference paper at ICLR 2024
Thorsten Joachims et al. Transductive inference for text classification using support vector machines. In leml, volume 99, pp. 200-209, 1999.
Diederik P Kingma and Max Welling. arXiv:1312.61 14, 2013.
Auto-encoding variational bayes. ar preprint
Derrick Norman Lawley and Albert Ernest Maxwell. Factor analysis statistical method. 1971.
Neil Lawrence and Michael Jordan. Semi-supervised learning via gaussian processes. Advances in neural information processing systems, 17, 2004.
Michel Ledoux and Michel Talagrand. Probability Banach Spaces: isoperimetry and processes. Springer Science & Business Media, 2013.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo. Predicting what you already know helps: Provable self-supervised learning. Advances in Neural Information Processing Systems, 34:309- 323, 2021.
Qinghua Liu, Alan Chung, Csaba Szepesvari, and Chi Jin. When is partially observable reinforce- ment learning not scary? Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thiriy Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp- $175-5220. PMLR, 02-05 Jul 2022.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization nonconvex sta- tistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 3145-33555555 PMLR, 2018.
Albert W. Marshall, Ingram Olkin, and Barry C. Arnold. Inequalities: Theory of Majorization and its Applications, volume 143. Springer, second edition, 2011. doi: 10.1007/978 0---000-77--- 387-68876-1
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016. URL http:
// j/mmr.... org/ http:/apppssss/aae satpeers/vv11/122ee0 142. html.
Oren Melamud, Jacob Goldberger, and Ido Dagan. context2vec: Learning generic context embed- ding with bidirectional Istm. In Proceedings of the 20th SIGNLL conference on computational natural language learning, pp. 51-61, 2016.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
Matthew E. Peter, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. arXiv preprint 1.02.08802.05365. 2018.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, al. Improving language under- standing by generative pre-training. 2018
Joel Ratsaby and Santosh S Venkatesh. Learning from a mixture of labeled and unlabeled examples with parametric side information. In Proceedings of the eighth annual conference on Computa- tional learning theory, pp. 412-417, 1995.
Nikunj Saunshi, Sadhika Malladi, and Sanjeev Arora. mathematical exploration of why language models help solve downstream tasks. arXiv preprint arXiv:2010.0366 036448 2020.
Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. arXiv preprint 220.:22202.1433., 2022.
Bernhard A Schmitt. Perturbation bounds for matrix square roots and pythagorean sums. Linear algebra and its applications, 174:215-227, 1992.
Steffen Schneider. Alexei Baevski, Ronan Collobert, and Michael Auli. wav2vee: Unsupervised pre-training for speech recognition. arXiv preprint /9X4v:9004.55000 05862, 2019.

---

Published as a conference paper at ICLR 2024
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learn ing. pp. 2256-2265, PMLR, 2015.
Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie- Yan Liu. Mass: Masked sequence sequence pre-training for language generation. arXiv preprint A905: 02405,0 2019.
Martin Szummer and Tommi Jaakkola. Information regularization with partially labeled data. Ad- vances Neural Information processing systems, 15, 2002.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. In Algorithmic Learning Theory, pp. 1779-1206. PMLR, 2021a.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. J. Mach. Learn. Res., 22:281-1,
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances Neural Information Processing Systems, 33:7852-7862, 2020.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In International Conference on Machine Learning, pp. 10434-1044) PMLR, 2021.
Sara Van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Martin Wainwright. High-dimensionaal statisfics: non-asymptolic viewpoint, volume 48. Cam- bridge University Press, 2019.
Colin Wei, Sang Michael Xie, and Tengyu Ma. Why do pretrained language models help in down- stream tasks? an analysis of head and prompt tuning. Advances in Neural Information Processing Systems, 34:16158-161700 2021.
Tong Zhang. From e-entropy to KL-entropy: Analysis minimum information complexity density estimation. The Annals of Statistics, 34(5), oct 2006.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. 2005.
12


Reviews:
[{"review_id": "wHC6X6YevV", "reviewer": "Reviewer_Qu76", "summary": "This paper develops a framework for understanding the advantages of unsupervised pretraining. The paper factorizes the learning task into two parts: unsupervised pretraining by MLE and supervised learning for downstream tasks via ERM. This paper derives its risk bound via an informative assumption justified by a zero-informative counter-example that any unsupervised pretraining gives no further information. Based on that assumption, the core result is an excess risk bound of $\\tilde{O}(\\sqrt{\\text{Complexity of pretraining class}/\\text{Unsupervised pretraining samples}} + \\sqrt{\\text{Complexity of downstream class}/\\text{Supervised learning samples}})$. This result prevails the risk guarantee of sole supervised learning when provided with abundant unsupervised pretraining samples. The authors also extend their results with three concrete examples.", "questions": "1. I wonder if the authors could comment more on justifying Assumption 3.2. I don't mean that \"Assumption 3.2 is incorrect\"; rather I just want a bit more demonstration on the mechanics behind this informative condition. For example, the authors compute three examples' informative conditions, but are those constants essential to the problem? Any theoretical results (for example, lower bounds of $\\Omega(\\kappa)$) or empirical ones will do.\n\n2. The third example, contrastive learning (Section 6), seems to differ from the mainstream contrastive learning modeling. A common approach is to assume access to positive pairs $(x_i, x_i^+)$ from the same latent class and negative pairs $(x_i, x_i^-)$, while this paper models it in a somewhat \"reverse\" way: each sample of the pair $(x, x^\\prime)$ is i.i.d. (which is often not satisfied in practice; see HaoChen et al. 2021), and the positive/negative signs are logistically distributed according to their latent similarity. I am not sure if this model is representative of a standard contrastive learning model, and it would be great if the authors could provide more explanations.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written and easy to follow.\n\n2. This paper provides a general framework for analyzing the benefits of unsupervised pretraining. The \"MLE+ERM\" approach covers most examples in unsupervised pretraining. The authors also justify the ERM approach by constructing an MLE counter-example.\n\n3. The main result is impressive and natural. Breaking supervised learning's statistical learning bound into two parts is critical to understanding the advantage of unsupervised pretraining.", "weaknesses": "1. The main assumption (Assumption 3.2) is not fully justified. The zero-informative counter-example is solid, but justifying the informative condition by showing \"if some example is zero-informative, then the unsupervised pretraining could be useless\" is a tautology. In short, the paper's conclusion of the superiority of unsupervised pretraining is built on the presumption of believing the pretraining to be useful. \n\n2. This paper shows three instances for its framework: factor models, Gaussian mixture models, and contrastive learning. But the last needs more careful handling since it is usually considered a self-supervised learning task. \n\n3. The contribution of this paper is mainly on the modeling part, while the proof techniques seem standard,", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "enQL38WCW4", "reviewer": "Reviewer_9yFE", "summary": "This paper provides a generalization of and subsequent analysis for unsupervised pretraining. The provided framework is able to capture a wide variety of unsupervised pretraining methods, of which factor models, Gaussian mixture models, and contrastive learning are more closely analyzed. The main result is a proof that the excess risk of the provided unsupervised algorithm scales by at most $\\tilde{\\mathcal{O}}(\\sqrt{C_\\Phi/m} + \\sqrt{C_\\Psi/n})$, which compares favorably to a baseline supervised learning excess risk under certain regimes.", "questions": "The truncation bounds used for the square loss seem very unnatural. Could you explain the use of those particular bounds?\n\nAll of the examples are in relatively simple settings (linear functions, separated Gaussian mixtures). Is this due to the way the bounds scale with model/distribution complexity?\n\nCould you explain how you derive the excess risk for the baseline supervised algorithm?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The presentation is clear. The generic framework provided for unsupervised learning is able to capture a wide variety of unsupervised methods. The theoretical results are able to demonstrate some advantage compared to a baseline supervised learning method.", "weaknesses": "Practical applications are unclear due to assumptions made (such as bounded loss) and the large complexity terms in the bounds. Idealized versions of MLE and ERM are used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Jft7AR2b1r", "reviewer": "Reviewer_rxwf", "summary": "The paper introduces an algorithm that under a specified \"informative\" condition significantly improves the baseline complexity achieved by conventional supervised learning, especially when there is a large amount of unlabeled data (m) compared to labeled data (n). The authors present a versatile framework to analyze various unsupervised pretraining models, emphasizing its applicability across different setups like factor models, Gaussian mixture models, and contrastive learning. The primary contributions are:\n\nExcess Risk Bound: The authors present an upper bound on the excess risk associated with an algorithm (Algorithm 1). The risk is expressed in terms of various parameters, including the Rademacher complexity—a measure that quantifies the function class's capacity to fit random noise.\n\nWeakly Informative Models: The paper introduces the concept of models that are $\\kappa^{-1}$-weakly-informative. These models, while not being fully informative, are shown to have certain desirable properties. The authors provide a relaxed assumption (Assumption 3.6) which broadens the class of examples by considering both the Total Variation (TV) and Hellinger distances to quantify the discrepancy between the model's outputs and the true distribution.\n\nPerformance Guarantees: Crucially, the authors demonstrate that the bounds provided on excess risk remain valid even under the $\\kappa^{-1}$-weakly-informative assumption (Theorem 3.7). This insight is significant as it indicates that despite the potential shortcomings of weakly informative models, one can still establish robust performance guarantees for them.", "questions": "**Real-world Relevance**: How do the assumptions and theorems presented in the paper translate to real-world applications? Are there any practical scenarios where these findings could be directly applied?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "**Originality:** \nThe paper's introduction of assumption 3.2 showcases a unique approach in how it lays out its foundational groundwork. This can be seen as a new definition or problem formulation, adding to the originality of the work.\n\n**Quality:** \nThe research stands out in its rigor and the depth of its theoretical contributions. The introduction and use of explicit models that unravel all hidden parameters, particularly $\\kappa$, underline the paper's commitment to thoroughness and depth.\n\n**Clarity:** \nOne of the standout features of this paper is its clarity. The authors smoothly introduce assumption 3.2 via a preceding thought experiment. This structured approach enhances comprehensibility, ensuring that readers are well-prepped before delving into more complex concepts. Furthermore, the theorems provided give a clear indication of the magnitude of parameters involved, aiding readers in understanding the practical implications and boundaries of the proposed methods.\n\n**Significance:** \nThe paper's structured and well-organized approach to presenting the setup, theorem, and explicit topic application is commendable. Such an approach not only amplifies the paper's readability but also underscores its significance in serving as a potential benchmark for future works in the domain. By ensuring that readers can seamlessly transition through the content, the authors have amplified the paper's potential impact on its audience.", "weaknesses": "### Weaknesses:\n\n**Over-reliance on Assumption 3.2:** \nThe primary weakness of this paper stems from assumption 3.2, which appears to be an overly robust condition. The core challenge of the paper lies in discerning the (constraint) relationship between (x, s) and (x, z). By introducing a new parameter, $\\kappa$, to simply constrain this relationship, the paper sidesteps the intricacy of this challenge. While the existence of such a parameter in the three sub-cases presented in the paper is addressed, its presence in more complex scenarios remains questionable. The use of such a strong assumption might detract from the general applicability of the results.\n\n**Potential Pitfalls with Transformation Assumption:** \nA significant concern arises from the implications of assumption 3.2. Based on the assumption, it can be inferred that given\n$$\\mathbb{P}\\_{\\phi}(x, s) = \\mathbb{P}\\_{\\phi^*}(x, s),$$\nthere exists a transformation $T_1$ such that\n$$\\mathbb{P}\\_{T\\_1 \\circ \\phi}(x, z) = \\mathbb{P}\\_{\\phi^*}(x, z).$$\n\nHowever, when considering mixed uniform distributions over specific cubical sets, these assumptions are immediately invalidated. This limitation highlights potential scenarios where the stated assumption may not be practically applicable.\n\n**Recommendations for Improvement:** \nIt would be beneficial for the authors to provide a more thorough justification or relaxation of assumption 3.2, possibly exploring weaker conditions that achieve similar results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "32URPqt9Lu", "reviewer": "Reviewer_Ht6r", "summary": "This paper sets out to provide a theoretical foundation for the benefits of pretraining on unsupervised data in the context of a broader downstream task. The central premise is that an unknown distribution, denoted as $p_{\\phi^*}$ and belonging to a known distribution family $\\phi^*\\in\\Phi$, generates pairs of data points $(x,z)$, where $x$ represents the input vector, and $z$ is a latent variable. Labels, or $y$ values, are stochastically determined solely by $z$ through an unknown distribution $p_{\\psi^*}$ from a known distribution family $\\psi^*\\in\\Psi$. Consequently, the pretraining procedure utilizes only observations of $x_j$s and Maximum Likelihood Estimation (MLE) to acquire knowledge of $p(z|x)$, while the fine-tuning stage leverages labeled pairs $(x_i,y_i)$ to learn a straightforward classifier, $p(y|z)$.\n\nNotably, the authors introduce the concept of \"informativeness\" as a means to theoretically elucidate the learnability of $p(z|x)$ solely from observations of $x_j$s. The paper then goes on to present a set of generalization bounds that, while somewhat expected, offer a fresh perspective. These bounds are demonstrated in three distinct scenarios: 1) Factor models, 2) Gaussian Mixture Models, and 3) Contrastive Learning.\n\nThe mathematical analysis in this paper appears rigorous and well-founded, and the presented bounds seem to be a novel contribution. However, my skepticism arises regarding the extent to which this paper advances the theoretical understanding of pretraining, as discussed in the \"Weaknesses\" section. It's noteworthy that the improved generalization bounds are primarily a result of the significant assumptions made about the data generation process. In simpler terms, the authors first assumed the efficacy of pretraining, and then substantiated their own assumption.\n\nNonetheless, I believe that this paper could be a valuable addition to the Machine Learning Theory (MLT) community and might meet the standards for acceptance at ICLR. Therefore, my current inclination is toward a weak acceptance. However, I remain open to reconsidering my evaluation if the authors can more effectively emphasize the significance of their work.", "questions": "For me, Theorem 5.3 is of independent interest. In your work, the data generation model is assumed to belong to a known distribution family, such as a Gaussian Mixture Model. This setting bears a resemblance to Ashtiani et al. (2018)'s work, where they provided slightly improved bounds for learning Gaussian mixture models, albeit not within the context of pretraining.\n\nFollowing Ashtiani et al., and adopting the notations used in the present work, the error for the downstream classification task can be bounded as follows:\n\n\n$\\hat{\\mathrm{Error}}\\leq \\mathrm{Error}_{optimal} + \\mathcal{O}(\\sqrt{Kd/m})$\n\nwithout the term $\\mathcal{O}(\\sqrt{K/n})$ which appears in Theorem 5.3 of the present paper. Instead, Ashtiani et al. would require $n\\ge\\tilde{\\mathcal{O}}(K)$ (with $\\tilde{\\mathcal{O}}(\\cdot)$ hiding poly-logarithmic factors).\n\nHowever, as previously mentioned, their focus is not on pretraining, and they pursue a fundamentally different approach. Still, it would be beneficial if the authors could provide further insights into the parallels between these works and offer a comparative analysis of the bounds.\n\n- 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).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is well-structured and exceptionally clear, making it easy to read. The problem formulation and subsequent results are presented with great clarity. The mathematical derivations appear sound, and the results are in line with expectations.\n\n- The introduction of the concept of $\\kappa$-informativeness, which guarantees the learnability of $p(x,z)$ using only observations from $x$, is both innovative and intriguing.\n\n- The authors have skillfully and rigorously framed their problem and have effectively demonstrated their results in three distinct theoretical scenarios: 1) Factor models, 2) Gaussian Mixture Models, and 3) Contrastive Learning.", "weaknesses": "The authors present an analysis of the excess risk associated with a two-stage learning process: first pretraining on a large volume of unlabeled data ($m\\gg n$), followed by fine-tuning on a smaller labeled dataset. Their findings reveal that this excess risk is notably smaller compared to training solely on the initial set of $n$ labeled samples. While the presented bounds are mathematically rigorous and insightful, they do not significantly advance our theoretical understanding of the concept of pretraining per se. In essence, the generalization bounds align with conventional expectations: For a limited $n$ and assuming $m\\rightarrow\\infty$, the training of a small linear head generlizes far better than training the whole NN, therefore, one would naturally expect:\n$\\sqrt{\\mathrm{complexity}(head)/n}+\\sqrt{\\mathrm{complexity}(body)/m}\\ll \\sqrt{\\mathrm{complexity}(head+body)/n}.$ \n\nThe authors, in my opinion, do not definitively establish the \"advantage\" of pretraining, despite the paper's title. In my opinion, the efficacy of unsupervised pretraining primarily stems from its remarkable capacity to mitigate bias, rather than reducing the excess risk. However, the effect of bias is not present in this analysis. The authors postulate the existence of a latent variable, denoted as $z$, which imparts conditional independence between $x$ and $y$. This assumption underpins the essence of pretraining, but the underlying reasons for its practical effectiveness remain elusive. Additionally, the authors rely on the presumption that the \"true\" joint distribution of $x$ and $z$ adheres to a known class of probability distributions, typically those produced by sufficiently large neural networks, which can be learned using a generic estimator such as MLE. The question of why these assumptions hold in practice and whether they can be theoretically justified remains a mystery, and this study does not provide a resolution to this critical issue.\n\nDue to the aforementioned ungrounded assumptions, particularly in the context of theoretical rigor, the proofs and associated mathematical methodologies in this paper lack enough mathematical sophistication. The derived bounds rely on the application of well-established generalization guarantees pertaining to Empirical Risk Minimization (ERM) and Maximum Likelihood Estimator (MLE).\n\nIn light of these concerns, I would suggest to rephrase both the title and abstract of the paper to accurately reflect the highlighted issues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)