Learning Bound for Parameter Transfer Learning
We consider a transfer-learning problem by using the parameter transfer approach, where a suitable parameter of feature mapping is learned through one task and applied to another objective task. Then, we introduce the notion of the local stability and parameter transfer learnability of parametric feature mapping, and thereby derive a learning bound for parameter transfer algorithms. As an application of parameter transfer learning, we discuss the performance of sparse coding in selftaught learning. Although self-taught learning algorithms with plentiful unlabeled data often show excellent empirical performance, their theoretical analysis has not been studied. In this paper, we also provide the first theoretical learning bound for self-taught learning.
This paper shows an excess risk bound in a transfer learning setting, with the main emphasis to be the scenario where the data have a latent sparse structure (as in sparse coding). The basic bound, Theorem 1, is proved using an error decomposition into three parts, each of which can be bounded using by-now standard techniques. The main work is establishing (under various assumptions) that a sparse-coding based method learns (from unlabeled ``source'' data) a dictionary that is sufficiently close to the optimal dictionary, and moreover, that under sufficiency proximity, that the sparse codes are stable under dictionary perturbations. The latter result, Theorem 2, was already proved by Mehta and Gray, but the authors offer a variation on this earlier result. They further show (and this constitutes the main technical work of the paper) that under certain assumptions, a notion they call the $k$-margin is large enough to apply the sparse coding stability result.
\documentclass{article} \usepackage[in]{fullpage} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsfonts}  \begin{document}   This paper has an interesting direction and synthesizes a number of results from different previous analyses of sparse coding methods to develop a excess risk bounds for a two-layer (sparse coding and then linear prediction) predictor. While I think this very much is a worthwhile pursuit, I have some concerns with the final (rather implicit) version of Theorem 1 after plugging in the various results from Section 3 (which is concerned with sparse coding, stability, and dictionary learning). I also have some technical concerns that I'll describe shortly. If there are good responses to these concerns, I will increase the score for technical quality (I thought the techniques used in this paper and those it uses from others are highly non-trivial, but the technical score is low right now due to potential correctness issues).  Overall, I found Theorem 1 a straightforward result (assuming a sparse coding stability result and the right error decomposition, the proof is not difficult). I did find the analysis in Section 3 to be techniquely involved and to carefully draw from a number of previous results in this space in order to control the dictionary estimation error and the margin. I did not check the proof of Theorem 3 carefully. However, it is concerning that the failur probability in Theorem 3 does not appear to decay with either $N$ or $n$, but only with the dimension $d$. Practically speaking, this may not be an issue, but theoretically, it limits the power of the results as the confidence is fixed with respect to $N$ and $n$. A similar issue occurs elsewhere, but potentially affecting the rate, as I now describe.  The most pressing issue is how to interpret Theorem 1 under the setting considered in Section 3 (Assumptions 1 through 4). For Theorem 1 to give a non-trivial bound, we must have $\|\hat{\theta}_N - \theta^*\|_{1,2} = o(n^{-1/2})$ due to the last term of (8). Therefore, looking at (43), in the case that $\tau = \frac{1}{4}$, we need $d = \Omega(n^{2/5})$ (and for $\tau = \frac{1}{2}$ we need $d = \Omega(n^{1/5})$). But $d$ is the ambient dimension, not a free parameter! Therefore, we really do not have the ability to play with $d$ in the bound (this did not seem like a nonparametric setting to me). Therefore, let us turn our attention to the earlier appearing equation (41).  If (41) holds as stated, then what prevents us from taking $M, M' \rightarrow \infty$ and thereby concluding that as long as $N$ is polynomial in $d$, then, for all $\varepsilon > 0$, with probability 1 we have $\|\hat{D}_N - D^*\|_{1,2} < \varepsilon$. This feels quite suspect, and so I looked at Theorems 3 and 4 of Arora et al.; their statements say the rate is $d^{-\omega(1)}$,, which I take to mean we have $d^{-h(N)}$ where $\lim_{N \rightarrow \infty} h(N) \rightarrow \infty$. Therefore, to make Theorem 1 useful (say, with a rate of $o(1)$), you need to ensure that $d^{-h(N)} = o(n^{-1/2})$; here I assume that you have made some choice of $N$ to depend on $n$, and typically $N = \Omega(n)$ since unlabeled source data is ``cheap''. Now, for $d^{-h(N)} = o(n^{-1/2})$ to hold seems easy enough if $h(N)$ is linear in $N$, but if it is logarithmic in $N$, one has to be more careful. Therefore, you need to dig into Arora et al.~and present their $\omega(1)$ bound with some additional precision. Please include a response to this in the rebuttal.   Regarding Theorem 2, given how different the RHS of (25) is as compared to the corresponding term in Theorem 4 of Mehta and Gray, you should have a proof which at least outlines what changes when doing the analysis under a bound on a $\|\cdot\|_{1,2}$ perturbation instead of their $\|\cdot\|_{2,2} = \|\cdot\|_2$ perturbation. Also, the scaling as $\lambda^3$ is quite disappointing, especially considering that the scaling is only as $\lambda$ in Theorem 4 of Mehta and Gray. Do you think this can be improved, or are perturbations in the $\|\cdot\|_{1,2}$ norm really that much more perilous?    It would be helpful to provide a short proof of (17), because in your proof of Theorem 1, it seems that wherever you wrote $\|\hat{\theta}_N - \theta^*\|$, you actually meant to write $\|\hat{\theta}_N - \theta^*\|_{1,2}$, since the latter is what actually appears in the theorem statement. But in (17), it is not clear to me if you should be able to get dependence merely on $\|\hat{\theta}_N - \theta^*\|_{1,2}$ rather than the (typically larger) $\|\hat{\theta}_N - \theta^*\|_{2,2}$. Please clarify this in the rebuttal.   Finally, please have your paper checked for English grammatical issues.     \subsection*{Minor points}  \begin{enumerate} \item    I think (using Hoeffding's inequality, a martingale version not being needed here) the last term in (13) should be $L_\ell R_\mathcal{W} R_\psi \sqrt{\frac{2 \log(2/\delta)}{n}}$, since each term is in $[0, 2 R_\psi]$. Also, I don't see how you get $\log(4/\delta)$ since your confidence setting is $\delta/2$. It isn't clear to me that these discrepancies all result from using Azuma-Hoeffding rather than (non-martingale) Hoeffding. \item    Assumption 4 is unclear. Do you mean to say that $\xi$ is zero-mean sub-Gaussian with support contained in the ball in $\mathbb{R}^d$ of radius $\sigma / \sqrt{d}$? That is, the case of bounded noise (which is hence sub-Gaussian)? \item    On line 256, do you mean to set $M = 5 \tau$ (rather than $M = 5 c$)?  \end{enumerate}      \subsection*{Update after authors' rebuttal}  Regarding my issue with Theorem 3, which is that the failure probability $\delta_{t,,\lambda}$ does not decrease with $n$ or $N$: The authors' response makes sense to me and I agree that this failure probability should be independent of $n$ and $N$. Also, I think in the high-dimensional setting this is acceptable due to the failure probability's exponential decay with $d$, practically speaking.  With regards to my issue with the application of Theorem 1 using the sparse coding application of Section 3:  Because the authors mentioned that they were not quite correct in some of the additional statements they made beyond (41), but that (41) itself is correct, I had another look at Arora et al., and was frustrated with the imprecision of that paper in terms of using the phrase "high probability" without explaining technically what they actually mean; my conclusion is that I do not know whether or not the authors are correctly interpreting and applying the results of Arora et al., but I am willing to give the authors the benefit of the doubt here. HOWEVER: I want the authors to be very precise on the exact result they are using from Arora et al. (more precise, it seems, then the exposition, of Arora et al. themselves).  Moreover, I had thought there may have been an issue with the authors own tuning of their parameters in Section 3, because the application of Theorem 1 in the case of sparse coding appears to give a trivial bound for different settings of $\tau$ unless we have the following limitations (I consider only the cases of $\tau = 1/4$ and $\tau = 1/2$): \begin{itemize} \item If $\tau = 1/4$, then we only apply the bound in the regime $n = O(d^{5/2})$. This seems acceptable, since $n$ is in the target domain, and we often do not assume all that much data in the target domain. \item If $\tau = 1/2$, then we only apply the bound in the regime $n = O(d^5)$. This seems even less of a restriction. \end{itemize} Still, I would like the authors to update their paper to be up-front about these (currently implicit) restrictions.  So, my technical concerns are adequately addressed, owing to some optimism on the part of the authors' use of the results of Arora et al.    \end{document}