Towards the Fundamental Limits of Knowledge Transfer over Finite Domains

Thank you for your positive feedback and let us address your questions as follows.

Q1: I am not sure whether tabular settings under usual statistical learning framework have been studied.

A1:

• As mentioned at the end of our Section 1.1, previous works [1, 2] similar to our $\mathsf{H}\text{ard }\mathsf{L}\text{abels}$ setting consider the teacher to be also an estimator that learning from samples generated via the Bayes (ground truth) probability. [1, 2] also largely fall into the ERM (empirical risk minimization) framework. In contrast, motivated by modern (proprietary) language (teacher) models, we treat the teacher model to be the Bayes (ground truth) probability and our target of interest is just a kind of symmetric closeness metric between the student and the teacher, and thus is different from the ERM-related ones that mainly concern generalization bounds or the comparison between the generalization bound of the student and that of the teacher.

• The term "knowledge transfer" we considered is to transfer any information from the teacher classifier to the student classifier as we mentioned in our Introduction section, any portion of $\{\pi^\star(\cdot|s_i)\}_{i=1}^n$ is considered as privileged (i.e., additional) information.

• At the very beginning of Section 3 (for $\mathsf{H}\text{ard }\mathsf{L}\text{abels}$), we already emphasize that

  "This is equivalent to the standard setting for estimating the conditional density $\pi^\star(\cdot|\cdot)$"

Q2: Can you generalize your results to continuous case?

A2: In the case of log-linear models $\pi_{{\theta}}(\cdot|\cdot) \propto \exp(\langle {\theta}, {\phi}(\cdot, \cdot))$, we do have some preliminary results that the conditional total variation between two models can be upper bounded by the $\ell_2$-norm between the model parameters given uniformly bounded feature mapping ${\phi}$. We have added these discussions and related conjectures (for log-linear or general softmax $\pi^\star$) on function approximation when the state space is allowed to be any standard Borel space in Appendix H (highlighted in blue) and leave the complete characterization as future work.

References:

[1] Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, Seungyeon Kim, and Sanjiv Kumar. Why distillation helps: a statistical perspective. arXiv preprint arXiv:2005.10419, 2020.

[2] Tri Dao, Govinda M Kamath, Vasilis Syrgkanis, and Lester Mackey. Knowledge distillation as semiparametric inference. arXiv preprint arXiv:2104.09732, 2021.

Thank you for your detailed feedback and we are happy to address your questions as follows.

Q1: The reviewer's interpretation of Theorem 3.1, Theorem 3.2, and other results.

A1: Let us respectfully emphasize some key points to accurately deliver the messages as follows.

• The learner (student model) does not learn $\rho\times\pi^\star$, and only aim to learn $\pi^\star(\cdot|\cdot)$, which is a discrete and conditional density. $\rho\times\pi^\star$ is purely a probability distribution indexed by $(s, a)$ pairs, and learning a good $\widehat{\rho\times\pi^\star}$ can not imply learning a good $\widehat{\pi^\star}$.

• Thus, the target of interest is the conditional total variation $\mathsf{TV}(\hat\pi, \pi^\star|\rho)$, while as we mentioned in the paper, an uniform $\rho$ is indeed good to provide some intuitions about the worst-case upper bound in expectation in Theorem 3.2.

• We respectfully disagree with the reviewer on our contributions to understanding the method efficiency of the later two settings. When certain portion of $\{\pi^\star(\cdot|s_i)\}_{i=1}^n$ is provided to the student, vanilla concentration bounds concerning only samples (such as Hoeffding's inequality, the Angluin-Valiant bound, Bernstein's inequality, Bennett's inequality, or McDiarmid's theorem) are no longer applicable, so our novel technical roadmap is instead inspired by the Missing Mass Analysis [1].

• We also respectfully disagree with the reviewer on our contributions to understanding the problem complexity of each setting. The three information-theoretic lower bounds can not be easily derived from standard concentration bounds. For the first case, the constructive proof of Theorem 3.1 is derived from Assouad's hypercube reduction. For the later two cases, Theorem 4.1 and Theorem 5.1 can not even be derived via standard reductions like Le Cam's, Assound's, or Fano's [2], because these three standard methods can only tackle the case with no ground truth leakage, i.e., they can only deal with estimators of $\pi^\star$ that learn from purely samples from $\rho\times\pi^\star$. In contrast, our proofs of Theorem 4.1 and Theorem 5.1 are based on two different and explicit constructions of Bayes priors over $\rho\times\pi^\star$ and the reduction from bounding minimax risk to bounding worse-case Bayes risk from below [3]. Thus, all the three constructive proofs for Theorem 3.1, Theorem 4.1, and Theorem 5.1 , are not derived from standard concentration bounds, and are different from each other, even from an intuitive perspective.

• Also, we want to mention an important contribution related to instance-dependent/benign-case analysis in Theorem 3.2: the complexity measure $\xi(\pi^\star)$, which provably explains the $O(1/n)$ rate of $\mathsf{CE_{sgl}}$ rather than $O(1/\sqrt{n})$ in expectation when $\xi(\pi^\star)\asymp n^{-1}\text{poly}(|\mathcal S|, |\mathcal A|)$.

• Another contribution is that the while the worst-case high-probability upper bound in Theorem 3.2 has $\text{poly}\log(|\mathcal S|, |\mathcal A|)$ factors, the worst-case upper bound in expectation in Theorem 3.2 does not.

Q2: More intricate scenarios for $\mathcal S$ and $\mathcal A$?

A2: We answer this question in two fold. First, the rationale behind considering discrete $\rho$ and $\pi^\star$ is that modern language models are often classifiers of tokens, with tokens or a collection of tokens as input. Second, we have added some discussions and conjectures (for log-linear or general softmax $\pi^\star$) on function approximation in the face of large state space in Appendix H (highlighted in blue), which builds a quantitative relation between the $\ell_2$-distance of model parameters and the conditional total variation between models, and leave the complete characterization as future work.

References:

[1] David McAllester and Luis Ortiz. Concentration inequalities for the missing mass and for histogram rule error. Journal of Machine Learning Research, 4(Oct):895–911, 2003.

[2] Bin Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam: research papers in probability and statistics, pp. 423–435. Springer, 1997.

[3] Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Book draft, 2022.

We are grateful for your attentive replies and would like to further address the points you mentioned as follows.

• In the latest revision, we highlighted brief discussions on the technical novelty of our work in the original text in blue; namely, the corresponding paragraph in Section 1.1 and the corresponding sentence in Section 3.1. Due to space limit, we may also consider further detailing the technical arguments in Appendix in subsequent revisions.

• To inspire future work on function approximation, we have highlighted our newly added quantitative inequality relationship between the $\ell_2$ distance of two model parameters (assuming both models are log-linear) and the conditional total variation of the corresponding two models; and have proposed relevant conjectures on the lower bound of the $\ell_2$ distance of two model parameters.

• Regarding the term "knowledge transfer", we would like to mention that the three cases we analyzed are idealized versions of "knowledge distillation" in deep learning practice [3]. Recently, there has been a trend of using (prompt, response) pairs queried from (Chat)GPT(-4) to train open-source language models, for example, see [1, 2]. These "black-box" knowledge transfer (distillation) paradigms can be essentially idealized to the first case we considered.

Thank you so much for your nice and scrupulous review.

References

[1] Zheng, L., Chiang, W.-L., Sheng, Y., Zhuang, S., Wu, Z., Zhuang, Y., Lin, Z., Li, Z., Li, D., Xing, E. P., Zhang, H., Gonzalez, J. E. and Stoica, I. (2023). Judging llm-as-a-judge with mt-bench and chatbot arena. https://github.com/lm-sys/FastChat/

[2] Wang, G., Cheng, S., Yu, Q. and Liu, C. (2023a). OpenChat: Advancing Open-source Language Models with Imperfect Data. https://github.com/imoneoi/openchat

[3] Hinton, G., Vinyals, O. and Dean, J. (2015). Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531 .

Thank you for your appreciation and we have added some discussions and conjectures (for log-linear or general Softmax $\pi^\star$) on function approximation in the face of large $\mathcal S$ in Appendix H (highlighted in blue), which builds a quantitative relation between the $\ell_2$-distance of model parameters and the conditional total variation between models.

Thank you for your valuable feedback. We would like to address your concerns as follows.

Q1: What is the definition of "privileged information"?

A1: Our formulations, which can indeed be viewed as concrete instantiations of the learning using privileged information (LUPI) framework [1], are already illustrated via relevant LLM examples in the third paragraph. To be more precise, the privileged information we considered for one sample pair $(s_i, a_i)$ is defined as certain portion of $\pi^\star(\cdot|s_i)$. We apologize for the vague introduction of this concept in the third paragraph of the Introduction and have incorporated your suggestions (highlighted in blue at the end of Introduction) and polished related descriptions in the current revision.

Q2: Notation referenced before definition.

A2: For all the four losses, we have equip them with hyperlinks (highlighted in red) pointing to corresponding definitions in the current revision, especially in Table 1. We also put the formal definition of $\Delta(\cdot|\cdot)$ and $\Delta(\cdot)$ back to the main text (highlighted in blue), which were placed in the Appendix before Appendix A due to limited space. Thank you for helping us improve the writing.

Q3: What additional information is provided with $\pi^\star(a_i|s_i)$  in the case of partially soft labels?

A3: $\pi^\star(a_i|s_i)$ itself is exactly the additional information in Section 4. A plainer explanation is that one student $\hat\pi$ may want to learn $\pi^\star(\cdot|\cdot)$, and in Section 3 she only use $\mathcal{D}$, while in Section 4 she can utilize $\mathcal{D}\cup\{\pi^\star(a_i|s_i)\}_{i=1}^n$. As we mentioned in the paper, $\pi^\star(a_i|s_i)$ is the probability of choosing action $a_i$ conditioned on the state $s_i$ and $\pi^\star(\cdot|s_i)$ is the probability distribution over the entire action space $\mathcal A$ given the state $s_i$, where $(s_i, a_i)$ is one sample pair in $\mathcal D$. For example, suppose $\mathcal S = \{0, 1\}$, $\mathcal{A} = \{0, 1\}$, $\pi^\star(\cdot|0) = [0.3, 0.7]$, and $(s_1, a_1)$ happens to be $(0, 1)$, then $\pi^\star(a_1|s_1) = \pi^\star(1|0) = 0.7$ is the additional information (or privileged information) provided to the student together with the sample pair $(s_1, a_1)$ in the case of $\mathsf{P}\text{artial }\mathsf{SL}\text{s}$.

[1] Vladimir Vapnik, Rauf Izmailov, et al. Learning using privileged information: similarity control and knowledge transfer. J. Mach. Learn. Res., 16(1):2023–2049, 2015.