On the Sample Complexity of Subspace Learning
A large number of algorithms in machine learning, from principal component analysis (PCA), and its non-linear (kernel) extensions, to more recent spectral embedding and support estimation methods, rely on estimating a linear subspace from samples. In this paper we introduce a general formulation of this problem and derive novel learning error estimates. Our results rely on natural assumptions on the spectral properties of the covariance operator associated to the data distribution, and hold for a wide class of metrics between subspaces. As special cases, we discuss sharp error estimates for the reconstruction properties of PCA and spectral support estimation. Key to our analysis is an operator theoretic approach that has broad applicability to spectral learning methods.
The paper deals with the problem of linear subspace 
      estimation from samples, which appears in many applications such as PCA, 
      kernel PCA and support estimation. The main contribution of the paper is 
      that it provides a general formulation for the problem of subspace 
      estimation and provides learning rates assuming certain decay behaviour 
      for the eigenvalues of the covariance operator associated with the data 
      distribution. As special cases, learning rates are provided for PCA and 
      support estimation improving upon the existing results. Clarity: 
      While the paper is technically interesting, the motivation presented in 
      Section 1 is not clear. The paper is more of a technical exercise and 
      lacks intuitive explanation. A better approach would have been to 
      introduce the PCA problem (as discussed in Section 4.1) in Section 2 or 
      may be even elaborate it in Section 1 so that the reader is introduced to 
      the operator theoretic interpretation of PCA. With this motivation, one 
      can generalize this notion as it is done in Section 2. I think this will 
      improve the readability of the paper. As a minor comment, there are few 
      typos, e.g., usage of "it is", which need to be fixed. Originality 
      and Significance: The paper is technically interesting and is 
      mathematically correct. Other comments: 1. In the paragraph 
      below Eq. 2, it is mentioned that d_{\alpha,p} is a metric for 
      0\le\alpha\le 1/2 and 1\le p\le\infty. However, in Proposition D.1 says 
      that it is also a metric for 1/2\le \alpha\le 1. Its not clear why this 
      restriction to 0\le\alpha\le 1/2? I dont see that such a restriction is 
      needed at least at this point. 2. In the proof of Proposition D.1, 
      it is mentioned that S_\rho=Ran C. Isn't it the closure of Ran C by 
      Proposition D.3? 3. As mentioned above, it will be better to 
      motivate the work through PCA and use proposition D.4 to motivate Eq. 2. 
      While one might wonder are there any interesting values of \alpha and p 
      other than 1/2 and 2, then you can present the application of set 
      estimation where \alpha and p take values other than these. 4. In 
      theorem 3.2, corollary 3.3 and remark 3.4, it is not mentioned that \alpha 
      > 1/(rp). Without this condition, the estimator will not be consistent. 
      This means for a fixed \alpha, p > 1/(r\alpha) which means the results 
      do not hold for all 0\le p\le \infty as mentioned in the statements. 
      Similar is the case with $\alpha$ where for a fixed p, the results hold 
      only for \alpha > 1/(rp), or it should be assumed that r > 
      max(1,1/(p\alpha)) 5. Line 126: postponed to "Section 7" 
      6. The discussion about the non-requirement of regularizer from a 
      statistical view point is not clear. Can you please elaborate what is 
      making the difference compared to [11], that the proposed formulation does 
      not require a regularizer even from statistical point of view. It is clear 
      that some regularizer is needed for numerical stability but the lack of it 
      is surprising from statistical sense. 7. While the proof technique 
      is interesting and non-trivial, it appears that one can just do the entire 
      analysis with p=2, i.e., Hilbert-Schmidt norm. Since the Schatten p-norm 
      is a p-norm of the sequence of singular values (which can be countable in 
      number as the operators considered are compact), it easy to check that 
      ||A||_q\le ||A||_p for any 0 < p < q\le infty (because of the 
      inclusion of l^p space in l^q). This means the analysis can simply by 
      carried out using p=2 for any while bouding ||A||_p for any p\ge 2. This 
      means classical Bernstein's inequality in Hilbert spaces can be used 
      without needing sophisticated tools like Theorem B.1. Similarly for the 
      case with 1\le p\le 2, one can bound ||A||_p by ||A||_1 in deriving from 
      (14) onwards where one can use Holder and convert the analysis into 
      bounding HS norms of certain operators. While I do not find 
      anything wrong the current analysis and it is indeed nice, I am just 
      wondering whether one needs the approach used in the paper to get sharp 
      rates or one can still get such rates using the above mentioned analysis 
      using HS norms. If one really needs the approach used in the paper to get 
      sharp rates, this has to be highlighted along with a possible reason 
      showing where HS approach fails.