Multi-step learning and underlying structure in statistical models
In multi-step learning, where a final learning task is accomplished via a sequence of intermediate learning tasks, the intuition is that successive steps or levels transform the initial data into representations more and more "suited" to the final learning task. A related principle arises in transfer-learning where Baxter (2000) proposed a theoretical framework to study how learning multiple tasks transforms the inductive bias of a learner. The most widespread multi-step learning approach is semisupervised learning with two steps: unsupervised, then supervised. Several authors (Castelli-Cover, 1996;Balcan-Blum, 2005; Niyogi, 2008;Ben-David et al, 2008;Urner et al, 2011) have analyzed SSL, with Balcan-Blum (2005) proposing a version of the PAC learning framework augmented by a "compatibility function" to link concept class and unlabeled data distribution. We propose to analyze SSL and other multi-step learning approaches, much in the spirit of Baxter's framework, by defining a learning problem generatively as a joint statistical model on X ⇥ Y . This determines in a natural way the class of conditional distributions that are possible with each marginal, and amounts to an abstract form of compatibility function. It also allows to analyze both discrete and non-discrete settings. As tool for our analysis, we define a notion of -uniform shattering for statistical models. We use this to give conditions on the marginal and conditional models which imply an advantage for multi-step learning approaches. In particular, we recover a more general version of a result of Poggio et al (2012): under mild hypotheses a multi-step approach which learns features invariant under successive factors of a finite group of invariances has sample complexity requirements that are additive rather than multiplicative in the size of the subgroups.
The paper studies prediction problems (a binary realizable, separable classification) within a standard PAC framework and tries to quantifies benefits which a learning algorithm can achieve by using a certain structure of the unknown data-generating distribution $P(X,Y)$. More precisely, the authors consider problems where (a) the conditional probability $P(Y=1|X=x)$ function depends on the input $x$ only through a sufficient statistic (or the *representation*) $t(x)$ and (b) function $t(.)$ depends on the unknown distribution $P(X,Y)$ only through its marginal $P(X)$.   The authors approach this problem by providing  (1) the upper bound on the generalization error of the "oracle learner" having access to the structure and  (2) the lower bound for the performance of a standard learner with no knowledge regarding the structure in $P(X,Y)$ (Theorem 3).  The lower bound is based on a novel extension of a fat-shattering dimension (Definition 1), which measures the complexity of a set of *distributions*, while the upper bound trivially follows from the standard worst-case bounds on the ERM algorithm.   Finally, the authors consider two different particular examples where the oracle learner can effectively solve the prediction problem, while the standard learner fails to do so (Section 4).  I checked all the proofs appearing in the main part of the paper and they are correct. 
While the main topic of the paper seems to be important and interesting, I was not impressed with the presented results. First of all, the assumption on the structure of $P$ is too strong for my taste: not only did we assume that such a factorization holds, but we also assumed that the oracle learner knows *exactly* the sufficient statistic $t$. I think this is a rather unrealistic situation. Second, the main theoretical result (Theorem 3) trivially follows the standard proofs of the lower bounds in the supervised learning (Chapter 14 in Devroye et al.). The only difference is captured in the extension of the fat-shattering dimension of Definition 1, but apart from that these are all well-known steps: let a marginal be concentrated on shattered points, then use probabilistic method, and play with the labels on the points not appearing in the training sample. In other words, I would say Theorem 3 does not contain any significant novel ideas. Finally, Section 4 looks confusing to me: the authors did not provide the original example of Niyogi in the "Manifold Learning" paragraph, which makes it hard to assess the novelty of the current paper in this context; "Group-Invariant features" paragraph is overly dense and is not supported with clear and intuitive discussions.   Concluding, I am not sure if this work provides a sufficient contribution to the literature (neither in terms of the techniques used, nor in terms of the results proved and conclusions made).   DETAILED COMMENTS  (0) Line 207 and 221-222. The upper bound of Devroy et al. holds for the *excess loss*, which is the difference between the loss of the learning algorithm and the smallest loss of the functions from the class. Meanwhile, the authors are using it to upper bound the loss of the learner itself. This is true only when we are in the separable realizable situation, meaning the hypotheses class contains the BEST classifier, which achieves zero error overall. This was not explicitly stated in the setting (at least, I did not notice it). (1) Words "fiber sub-bundle" in the abstract look mysterious... (2) Lines 42-43: Devroy et al. does not contain an overview of Rademacher complexities, only VC. (3) Line 64: not clear what do the authors call "a full joint model" (4) Section 2. I had a hard time guessing the meaning of $f_p$. In the end (from the proof of Theorem 3) I conclude that in all cases $f_p(x) = P(Y=1|X=x)$. This should be stated explicitly!  (5) Line 110. p(y|x) = E_p(y|x) should be replaced with p(y = 1|x) = E_p(y|x). (6) It is better to present or sketch the original definition of a fat-shattering dimension somewhere around Definition 1.  (7) Line 173. How can $P$ be an element of $P_t x C$ ?  (8) Equations (3) and (4): parenthesis missing, in (3) dot should be switched to comma. (9) line 212: "stronger notion of a stronger notion of..." (10) I did not get a purpose of a footnote (3) (11) lines 229-230. Better to state explicitly that this is due to probabilistic method, which is a standard tool used in these situations. Refer to the same book of Devroye, Chapter 14 if necessary. (12) Line 233. p(v_p(x)|x) should be replaced with p(y = v_p(x)|x) (13) Definition of $V_l$. Note that the r.h.s. depends on $i$ and $j$ while the l.h.s. does not. Should be fixed. (14) L.h.s. of the first inequality after line 236: the authors forgot to put $1/2^{2^m} \sum_{p\in P_{2m}}$.  (15) Line 246. $\bar{z}(\bar{x})$ should be replaced with $\bar{z}_p(\bar{x})$  =======UPDATE======= I have carefully read the rebuttal. unfortunately, I am going to keep my initial decisions.  The main reason for this is that I still think the assumptions considered in the paper are too strong. The authors are comparing the performance of a standard supervised algorithm to the learner which knows the structure of the problem, including the $t$ function. It is not surprising to me at all that in this case the "smart" learner will easily outperform the standard SL algorithm. In my point of view,  one could hope to *learn* the $t$ function during the training, but for sure it is unrealistic to assume that the algorithms *precisely knows* $t$ in advance. Thus I think the contribution of the paper is  marginal.