Towards the Fundamental Limits of Knowledge Transfer over Finite Domains
Authors: Qingyue Zhao
Banghua Zhu
Venue: ICLR 2024 poster (2024)
Keywords: knowledge transfer
classification
minimax optimality
density estimation
knowledge distillation
Primary area: learning theory
TL;DR: We settle the sample complexity of knowledge transfer at various levels of privileged information in the tabular setting.

Abstract: We characterize the statistical efficiency of knowledge transfer through $n$ samples from a teacher to a probabilistic student classifier with input space $\mathcal{S}$ over labels $\mathcal{A}$. We show that privileged information at three progressive levels accelerates the transfer. At the first level, only samples with hard labels are known, via which the maximum likelihood estimator attains the minimax rate $\sqrt{{|\mathcal{S}||\mathcal{A}|}/{n}}$. The second level has the teacher probabilities of sampled labels available in addition, which turns out to boost the convergence rate lower bound to ${{|\mathcal{S}||\mathcal{A}|}/{n}}$. However, under this second data acquisition protocol, minimizing a naive adaptation of the cross-entropy loss results in an asymptotically biased student. We overcome this limitation and achieve the fundamental limit by using a novel empirical variant of the squared error logit loss. The third level further equips the student with the soft labels (complete logits) on $\mathcal{A}$ given every sampled input, thereby provably enables the student to enjoy a rate ${|\mathcal{S}|}/{n}$ free of $|\mathcal{A}|$. We find any Kullback-Leibler divergence minimizer to be optimal in the last case. Numerical simulations distinguish the four learners and corroborate our theory.

Published as a conference paper at ICLR 2024 2024
TOWARDS THE FUNDAMENTAL LIMITS OF KNOWLEDGE TRANSFER OVER FINITE DOMAINS
Qingyue Zhao
Banghua Zhu
Department of Computer Science and Technology Tsinghua University
Department of Electrical Engincering and Computer Sciences University of California, Berkeley banghua@bes bew.eeey.eey..........er. edu
zhaots i mnnuueggggmmmmmmm gma i 1. com
ABSTRACT
We characterize the statistical efficiency of knowledge transfer through samples from a teacher to a probabilistic student classifier with input space S over labels A. We show that privileged information at three progressive levels accelerates the transfer. At the first level, only samples with hard labels are known, via which the maximum likelihood estimator attains the minimax rate / /I5lIAl/n. The second level has the teacher probabilities of sampled labels available addition, which turns out to boost the convergence rate lower bound to |S]]Al/n. However, under this second data acquisition protocol, minimizing a naive adaptation the cross-entropy loss results in asymptotically biased student. We overcome this limitation and achieve the fun- damental limit by using a novel empirical variant of the squared error logit loss. The third level further equips the student with the soft labels (complete logits) on A given every sampled input, thereby provably enables the student to enjoy a rate |Sl/n free of IAA. We find any Kullback-Leibler divergence minimizer to be optimal in the last case. Numerical simulations distinguish the four learners and corroborate our theory.
INTRODUCTION
It has become common sense that transferring intrinsic information from teachers to the greatest extent can expedite a student's 's learning progress, especially in machine learning given versatile and powerful teacher models. Learning with their assistance has been coined knowledge distillation (KD) (Hinton et al., 2015; Lopez- Paz et al., 2015), famous paradigm of knowledge transfer leading to remarkable empirical effectiveness in classification tasks across various downstream applications (Gou et al., 2021; Wang & Yoon, 2021; Gu et al., 2023b). The term distillation implies a belief that the inscrutable teacher(s) may possess useful yet complicated structural information, which we should be able to compress and inject into compact one, i.e., the student model (Breiman & Shang, 1996; Buciluă et al., 2006; Li et al., 2014; Ba & Caruana, 2014 4; Allen-Zhu Li, 2020). This has guided the community towards line of knowledge transfer methods featuring the awareness of teacher training details or snapshots, such as the original training set, the intermediate activations, the last-layer logits (for probabilistic classifier), the first- second-order derivative statistical information, and even task-specific knowledge (Hinton et al., 2015; Furlanello et al., 2018; 8; Cho & Hariharan, 2019; Zhao al., 2022; Romero al., 2014; Zagoruyko ko & Komodakis, 2016; Yim al., 2017; Huang & Wang, 2017; Park et al., 2019; Tian et al., 2019; Tung & Mori, 2019; Qiu et al., 2022; Srinivas & Fleuret, 2018; Cheng al., 2020; Liang et al., 2023).
However, in more general modes of knowledge transfer, the procedure- or architectur--specffic information can be unavailable, irrelevant, or ill-defined. Modern proprictary large language models (LLMs) like GPT-4 (OpenAI, 2023b) and Claude 2 (Anthropic, 2023) strictly confine the data returned through their APIs except the generated tokens, not to mention their training sets. Therefore, there has been an effort towards distilling LLMs only through oracle queries via locally crafted prompts (Zheng et al., 2023; Peng et al., 2023). In denoising (Tsybakov, 2003), boosting (Freund & Schapire, 1995), and prediction with expert advice (Cesa-Biand) classes of interest and the student only gets positive- positive-valued feedback from the teacher group, so the teacher implementation is immaterial. In certain cireumstances of robot learning (Abbeel & Ng, 2004; Ross & Bagnell, 2010), the teacher demonstration may come from threshold based classifiers or even human experts, where teacher probability is defined.
et al., 1997), the teacher group itself is the

---

Published as a conference paper at ICLR 2024
To unify different natures of teacher information acquisition in knowledge transfer and assess the technical barriers in a principled way, we decompose the transfer set' into a generative model TT (-I-) giving one in the label space A given query in the input space S and the additional information provided by the teacher for each sample pair (s,a). Take several L.Ms as examples. In OpenAl's chat completion API for GPT-4, only responses are returned given a prompt 8, in which privileged information is accessible. An early completion API for GPT-3 (Brown et al., 2020), however, also returns the log-likelihood of every token the generated response. with open-sourced models like GPT-2 (Radford et al., 2019) in hand, practitioners can extract the last-layer logits of each position in the sampled sequence as the privileged information. These typical examples reveal trend that the more powerful foundation model (Bommusani et al., 2021) is, the less likely it is to release privileged information as teacher modef, which naturally motivates a question:
What is the fundamental limit of knowledge transfer given limited privileged information in general?
In this work, we answer this question with minimal inductive bias by analyzing three classic cases with easier difficulties in order over finite and A. Concretely, for any learner मř, we study the total variation between it and the reference policy x² conditioned on an input distribution i.e.,
#ES
where से can access samples ((s,, and optionally certain fraction of x (e)ss)).Viie)))
1.1 MAIN CONTRIBUTIONS & CLARIFICATIONS
Table I gives overview of rate bounds in distinct data acquisition protocols. Hard Labels indicates n² to be a black-box for throughout the learning process. Partial SLs stands for partial soft labels, which means the teacher provides the student with an extra (partial) ground truth π (als) for every sample (s,a). Soft Labels is synonym of the logits on the entire A exposed to पे given each s in {s: Intuitively, each of the three levels discloses richer information than previous ones, which at least cannot make it harder to learn. Rigorously, progressively faster minimax rates are matching exactly all levels and every high-probability upper bound has its upper confidence radius at most the same order of the corresponding expectation lower bound up to polylog factors.
Table 1:
The second column shows one out of n2 data points available to the student. Worst-case bounds in the last column hold with high probability and (()) hides polylog factors.
Transfer via
Data Format
Lower Bound
Loss
Performance
Ω AIIA))))
Ô (VSIIAA/
Hard Labels
(s,a)
CE
Theorem 3.1
Theorem 3.2
12(1)
CEpd
2(15114144) Theorem 4.1
Theorem 4.3 ((5)))A1//))
Partial SLs
(sla,
SEL ptl
Theorem 4.4
1((5)/)) Theorem 5.1
Ō ((55/))
Soft Labels
(5,a,x((+(ss)
CENul
Theorem 5.2
Technically, the later two protocols are nonstandard in density estimation, especially in terms of the derivation of minimax lower bounds in that assume the data generating process to be (pxx*) The
'Here we mean the information a student has access to in total.
IIspired by the learning using privileged information framework (Vapnik et al., 2015; Lopez-Paz al., 2015).
'htpps: http//aatforrr openai com/ docs/ wttp////ss//aapeeeeeeeeeeeeeeeee refeennceeeeeeeeeeeeeee chat
*https: / /pt/ffffrmommmmmmmm openai. wwt/ /api ference comp lt ionss
vision for a similar tendency. WWe defer the matching expectation bounds to respective sections.
'See, c.g., Ramesh et al. (2021; 2022); OpenAl (2023a) in computer vision
2

---

Published as a conference paper at ICLR 2024
constructive proof (Appendix C.3) of Theorem 4.1 may be of independent interest. The performances at the second level are also more tricky. Theorem 4.3 sentences a naive adaptation of the cross-entrope loss (CEpe) to be misfit with probability 1 when the privileged information is a modest level.
We do not require πT" to be trained in any sense and assume i. to have no awareness of the teacher implementation, inspired by the aforementioned practical trend. Consequently, we do no distinguish the teacher probability from the Bayes probability (Menon et al., 2020; Dao et al., 2021) and can have no relation with teacher training. We idealize the samples to be i.i.d., while all the results already extend to the setting where different (s.a) pairs are mildly dependent, of which we refer the readers to Appendix G for detailed discussions.
We give more discussions on the connections between our framework and previous formulations in Appendix A.2 and review key related works aiming at the principles of knowledge transfer in the next subsection.
1.2 RELATED WORKS ON UNDERSTANDING KNOWLEDGE TRANSFER
Hinton et al. (2015) refers to the logits generated on a dataset by a teacher model, who has been trained using the same dataset, soft labels; and refers to {a, 1=1 in this dataset as hard labels. Our terms, however, pay no attention to whether matches the original dataset; and our Soft Labels strictly carry more information (of p T*) than our Hard Labels, both of whose inputs { are sampled from P. So the third column of Table does not account for the class similarities argument (Furlanello et al., 2018), the regularization effect via label smoothing (LS) argument ( (Yuan et al., 2020; Tang et al., 2020), or the pias-variance trade-off argument (Zhou et al., 2021; Menon et al., 2020); all of which are classical wisdom explaining the benefit of soft labels in KD (Hinton et al., 2015).
These previous views are neither consistent nor complete for justifying why soft labels improves student training. (Müller et al., 2020) undermines the hypothesis that class similarities in soft labels are vital by the effectiveness of KD in binary classification. Han et al. (2023) challenges the regularization via LS thesis through better interpretablity- bias-variance trade-off perspective in more complex scenarios. In contrast, we define Soft Labels (sim- ilarly Partial SLs) and tackle its boost over Hard Labels rigorously following the coormation-theoredee direction of the data processing inequality yPolyanskiy& & Wu, 2022). We survey more works unraveling knowledge transfer. Other empirical and enlightening paradigms are deferred to Appendix A.
effect of KD than LS. Dao et al. (2021) develops the
Most analyses of KD with trained deep nets the teacher (Phuong & Lampert, 2019; Ji & Zhu, 2020; Panahi et al., 2022; Harutyunyan et al., 2023) lie in the linear or kernel regime, notably except Hsu al. (2021), which finds the student network have fundamentally tighter generalization bound than the teacher network under several nonlinear function approximation schemes. There are also works analyzing knowledge transfer between neural networks of the same architecture (Mobahi et al., 2020; Allen-Zhn -Zuu & Li, 2020). Our framework goes exactly in the reverse direction: our analysis is not restricted to parsimonious students, over- per--arameterieed teachers; or the compression subconcept of knowledge transfer (Buciluă et al., 2006; Bu et al., 2020). For example, human demonstrator, who does not learn only from data and is able to output probabilistic belief, can also fit into the first column of Table kind of teacher under our specification of T*
2 PRELIMINARIES
Notation. For two nonnegative sequences {an} and {bn}. we write a, = O(b,) ) or an S b, if lim Rn/b, < oo; equivalently, b, saa,) or bn 2 an- We write en = ((d,) if en = (dd,) and c, = (.d.). For metric space (M.d), dista (:N))= inf d(-.y) yy) for any N M. The term alphabet is a synonym of finite set. For a set or multiset C, let [C] denote its cardinality. For any alphabet X. which given two distributions p, g. the total variation between them is TV (p.g) := 0.5 ||p-gll, their Kullback-Lend Leibler (KL) divergence is (L(p)))) == E, loop - log and we denote all | Dirac distributions X' by Dirac(X'), where Dirac .x) stands for the one concentrated at zz For two alphabets X' and V. we denote by A()) the probability simplex on y and
define ( x)) = (-(-1): (())) = (- E (())),
3

---

Published as a conference paper at ICLR 2024
2.1
COMMON SETUP
The teacher always exposes to the student a multiset D ((s S consisting of n i.i.d. input-label tuples. To analyze 'D in a fine-grained way we introduce for X 3 X s.i.d. of occurrencee n, (X"") of a and themissing mass m,, which measures the portion of X never observed in X (McAllester & Ortiz, 2003). We refer to the input (resp. label) component { )= (resp. {as [==)==) of D as SDD (resp. A(D)) and also define a multiset A(D,s) for every s e S to denote the 0g s in D that are associated with the visitations of s, taking into account multiplicity.'
~ v the number
2.2 QUANTITY INTEREST
We assume D (p πt )r follows product measure, where x² A(A(S) is the ground truth distribution over A given 8 E S the teacher holds and p is some underlying input generating distribution. No assumption is imposed on the data generating process px nT" except for belonging
P= (pxx* pE (E)) (((II))
In this work, we evaluate the performance of student based on the TV between 7 and x* conditioned on defined as
TV (V((,,
(2.1)
though the student is never allowed to access p directly. We investigate the convergence rate (2.1) among three categories of students told by the teacher's degree of openness in the tabular setting. Intuitively speaking, all the learning procedures of interest try to match the log- bog-probability kernel logæ, notion of normalized logits, between the student and the teacher, especially via variants of the cross-entropy loss, which is standard in the study of classification both theoretically and practically (Paszke al., 2019). Besides the universal definition CEru (pllg) == EEp [logg] of the cross-entropy between p < g, a popular counterpart for hard labels specialized to classifiers is commonly defined as CE (s.a;T) == CE (a.)ra((A.)))l((((((
(ags)(a(s).
3 TRANSFER VIA HARD LABELS
This is equivalent to the standard setting for estimating the conditional density л (-1-)-
3.1 HARDNESS OF ESTIMATION
We first generalize the idea of constructing hard instances for learning discrete distributions A (Paninski, 2008) to our nonsingleton S to understand the difficulty when only (s,a) paris are available. We remark that the proof of Theorem 3.1 (in Appendix C.2) is the only one in this work that utilizes Assouad's 's method (Yu, 1997) directly.
Theorem 3.1. For nonempty S, A with |A| 1, and n 1811-/44
SIA
inf sup *x
( TV(=
(3.1)
where D~ () MT(D) denotes (possibly random) estimators mapping D A(A(S).
The / /S| dependence in the lower bound intuitively makes sense because the classic lower bound for S -1 (2V Al/n) and each input roughly get */|S| samples when p distributed evenly.
3.2 MAXIMUM LIKELIHOOD ESTIMATION
We approximate the teacher "t" via minimizing the following negative log likelihood loss:
See Appendix for the rigorous definitions of n=(X"), mo(v,X"), and A(D,s).
4

---

Published as a conference paper at ICLR 2024
sgg E argmin CEggi = argmin rEA(A|S)
lag (ag))))
(3.2)
TEA(A(S)
It is possible to exactly attain the minimum in (3.2). A refactoring detailed in Appendix B.1 indicates a natural relation between the hard version CEgg and the soft version CEaul which leads to a neat closed-form solution for the optimization problem.
= B(s,a) (D))n, SES(D),
icE (als))
(3.3)
(AA(A) arbitrarily,
otherwise.
We study the convergence behavior of 7cE.sø in fine-grained way with its proof detailed in Appendix D.2: Theorem 3.2. For any 8E (0.1), with probability at least 1 1-6,
TV(FFC, 1p)
(3.4)
"
The upper bound in expectation E [T [p) v // no better than (3.4) up to log factors. An instance-dependent version in expectation
S (((TT)
|
E [B[TV (p)))
(3.5)
n
where E(TT) ;= max, ddst (sls)) = 2 ([lxx((ass))) (als)).
Thus, cc,,sg worst-case optimal and may even have rate in some benign cases with π² close enough to vertices of the simplex ((A).
4 TRANSFER VIA PARTIAL SLS
Besides D, we can also access R = ((81,0,,7 ((; (a;(s:))) as Partial SLs. The introduction of R. leads to quadratic reduction of the learning difficulty.
4.1 BLESSING GROUND TRUTH
Theorem 4.1. For nonempty S, A with |A| 2, and n 1S(IA| -1101/1111122111111111-1
inf sup E ( TV( 1p) |A||A] De
(4.1)
where D ~ (ox )", R ((a. learners mapping (D,R) to ((AS)).
and Īi(,RR) R)) denotes all (possibly random)
We provide a constructive proof of Theorem 4.1 in Appendix C.3, in which we resort to the power of randomized policy as reveal the linear in [A] dependence.
4.2 FAILURE EMPIRICAL CRCOS--ENTROPY Loss
The Partial SLs R motivates us to define loss CE interpolating between CE.gi and CE
CE argmin (D,,(D argmin =EA(A[S)
(4.2)
TEA(AIS)
We can obtain the following exact solution to (4.2) by another technique detailed Appendix B.2,
(als) (Xn(),a) (D) sES(D), (AA) arbitrarily, S(D(
(4.3)

---

Published as a conference paper at ICLR 2024
The convergence analysis of pu erucially relies its relationship with #cE,sgl- For any SE)(D) PcE.ptl can be reformulated as
cE (a|s) (als)) x (c
(4.4)
(b
Lemma 4.2. For |
#CE,pu(-1s)) - (-1s)]
[ (als))?
under 6o in RR px is independent of
Lemma 4.2 roughly means Cc.,pt x (T²)² approximately as n goes to infinity, which implies that small parts of are underestimated and large parts of πt are overestimated. We make this intuition technically right in Theorem 4.3, whose rigorous statement, mechanism, and proof are deferred to Appendix D.4.
Theorem 4.3. px does not vary with n, Ac coincides with #CE (and thus asymptotically unbiased only if (-Is) = Uniform (A) n (+|s) Dirac(AA) for all e S. Even for |S] 1, Atl asymptotically biased in general.
4.3 EMPIRICAL SQUARED ERROR LOGIT Loss
Ba & Caruana (2014) suggests the practically promising SEL loss":
11
((T,T*))
llog (log:)
(4.5)
aEd
Here we analyze the minimization of its empirical variant with normalized logits under the second data acquisition protocol for simplicity:
SELpt (D,R) logg(aa -:) -log= (a:ls)"(a(ss)"""
(4.6)
Exact matching on the seen samples in (D,R) shows that ASEL, Earasin
(D) ((A)) arbitrarily,
SES(D),
RSEL pn (-1s)
(4.7)
otherwise.
The following three-fold Theorem 4.4 indicates that PtEL, converges faster than 7CE by factor of /n though its performance upper bound has worse dependence on |S||AA] compared with that of TcE Theorem 4.4. If [S] > 1, for any á (0,min(1,((5)+2)))) ((5121)1))) with probability at least 1-5,
SS| (1A) + ([A[log((S//)
| log 8
TV 1p)
(4.8)
n
If ||| for any 8 (0,1/1),, with probability at least 1-8,
LAI
TV (p) (p)= TV(SSEL
log 8
(4.9)
n
The expected risk ETV (p)
SIIAl/n not polynomiallyy tighter than (4.8) or (4.9).
'Though 7c is not estimator. can discuss unbiasedness under more general notion, i.e. for K constants (c, 1 the random variables {X,,) YK K called asymptotically unbiased if X.,, - some mode
of convergence as n n-+ no for every i [K]. Practical versions of SEL often allow unnormalized logits. See Remark 3.1 for discussions.

---

Published as a conference paper at ICLR 2024
Remark 4.5. Theorem 4.3 together with Theorem 4.4 manifests the advantage of employing the empirical SEL loss, which induces an alignment between the normalized logits of the learner and those of x* under squared loss, over the empirical CE loss in offline distillation when the teacher is moderately reserved. similar observation between these two style of empirical surrogate losses in online policy optimization is verfied in practice (Zhu et al., 2023b).
TRANSFER VIA SOFT LABELS
At the lightest level, the student has the extra information Q (=s,((('('- E The availability of Q apparently eases the transfer process, especially when the support size |A| of the teacher classifier huge. Such an intuition can be precisely depicted by |.Al-free minimax lower bound.
5.1
|RRFREE LOwER BOUND
The following lower bound roughly requires S(( burn-in cost, whose constructive proof is deferred to Appendix C.4.
Theorem 5.1. For S with [S] > 1, A with |A| > 1, and n |S|
||
inf sup E )= TV( (p))
(5.1)
where x*) Q ((s,TT (19)): and Îi(D, 2) denotes all (possibly random) learners mapping (D12) to A(AS).
This setting cannot have a rate better than -1 which is consistent with the n rate in Theorem 4.1 since the difficulties of the later two settings (intuitively, the information provided at these two levels) should be the same when x (-|s) (Arac(AA) for any SES.
5.2 BULLBACK-LEIBLAR DIVERGENCE MINIMIZATION
Cross-entropy loss minimization under full observation is equivalent to
= (-Is), (AA)) arbitrarily,
if
CE E Eargmin
(5.2)
otherwise.
We give the missing-mant mass- mass-mmssedddeeeeee-aa based proof the matching upper bounds for .CE. in Theorem 5.2 in Appendix D.6.
Theorem 5.2. For any 8 (0,)/1)), with probability at least 1 1-5,
S
S
TV(#CE,,. at 1p)
+
log
(5.3)
n
7
The upper bound (T
on the expected risk for 7CE.. nearly matches (5.3).
Theorem 5.2 guarantees the optimality of iCE in that maximally utilizes the given logits.
EXPERIMENTS
We conduct simulations to verify the intuitive performance rankings iCE 2 TtELL 3 TTE given moderately large sample sizes and also numerically provide the asymptotical biasedness of #CE, with samile counterpart. Moreover, arguments (Appendix C) for the three types of reserved teachers respectively
design adversarial data generating distributions inspired by
the information-thcone in the non-an con-tsymptotic regime, thereby accurately exhibiting the matching convergence rates of #cE,sgl SsEL, and iCE., in terms n.
In this section, specify fair inductive bias due to the tabular nature: if s S(D), f(-ls) is set to Uniform(.A) (AA) for all learners; for (s the missing mass is amortized uniformly among A A\A((Dss) if S(D))
7

---

Published as a conference paper at ICLR 2024
6.1 CLASSIC REGIME: TELLING LEARNERS APART
In the classic regime, px 'T stays invariant matter whether tends to infinity or not. An instance in this sense should not only expose the inferior of RCE.pul but also showease the hardness of S|> i,i.... should be strictly bounded away from zero in (2([S) )) inputs. To these ends, we specify Instance in Appendix F. We simulate four typical realizations of it, whose estimated risks is presented in Figure 1. Each marker in Figure represents the empirical mean of TV . (p) in 100 independent repeats given the corresponding sample size n.. Any broken line in Figure has nothing to do with sequential design and our experiment is purely offline. As shown in Figure (a, b), either in general case with ([S), (100, 25) or for a 100-armed rewardless bandit, ETV (p) learners do, corroborating the asymptotically constant bias of Cct and the consistency of the others.
fails converge but all other
(4)15
Irstance von
(5
ETVIR m
0.4
CEsgl
Eptt
C
(5) f.A- SoCol Inbance &: n-Chbroux
ErVia nt 16)
CEsgl
0.4
CEpt
ETVii, nt
SE
0.2
SELpt
C Erul
CEruI
0.0
10
15
25
30
(8) 15 1024,4 iratares U n40t ous
STVIG.
CE Eggl
SELpt
500
1000
1500
2000
2500
1000 2000
9000
4000
Figure I: Estimated risks in expectation, p xT does not vary with n.
Though Instance is effectively easy to learn for any of #CE,sgl, AtEL and iCEE,, that of the three worst-case upper bounds is tightly attained, the numerical performance rankings among them in Figure 1 coincides with our intuition and theoretical analysis. The "benign" -case comparison in Figure 1 (c), where the sample sizes are small enough to make the worst-case lower bounds vacuous, still favors cC over ĀSEL,pt in the large-I.4 |A| regime. Figure (d) manifests that the /|S|| gap between the worst-case upper bounds for cc and TsEL, which reversely dominated by the exponential rate of iSEL,, pt in this Instance O, may not be observed in general even for large ||| and small n.
Remark 6.1. Direct calculations imply that p 2 cs for all inputs with cs irrespective of when is large enough, (T (p) can decay exponentially fast, exemplified by Figure (a). ETV ETV( (T TT will enjoy similar linear convergence long as we additionally require (+|s) T
C 0 for all s E S and all labels with сд independent of n for sufficiently large n, again exemplified by Figure! (a).
6.2 NON-ASYMPTOTIC REGIME: ILLUSTRATION OF MATCHING RATES
Instance 0 serves as an intriguing average case, but we need to design worst-case instances that may vary with n (Wainwright, 2019) in the non-asymptotic regime for different data acqusstioi settings in order to verify the minimax optimalities. The adversarial Instance 1, 2, and with their design insights are detailed in order Appendix F for verification of matching rates at all three levels.
Since cc ,gl, SEL,, and i... enjoy optimal rates of order n or n 0.5 we can manifest them using lines in a log-log plot. More generally, if some notion of r sk has r risk ((x for some 8* < O, logri sk logn will at least bounded by two straight lines on log-log scale, We instantiate the
See Remark 6.1 for details.
8

---

Published as a conference paper at ICLR 2024
above idea for Instance I, Instance 2, and Instance 3 in Figure 2, in which each marker represents the average of 64000 independent repeats. We also conduct linear regressions over logriste logn for corresponding minimax learners and report the slope B as estimated 3* in each subfigure of Figure 2.
(4 130 kocta
18"
14 188,0 25g besteon an Sil
0115 100, 25) 11) Iistane X. Adhossaiite Ciuy
16"
CEpt
167
CE f -0.532 (orn
SElpet
CFpu
2007
CEp, P wi-0 ffor n0111
SEL,u
CE
167
Chuu
CEnn
SEL á = -1.004 (for a 10*)
1/'
12) iiteca nntormrrtt
2015 ridemarri sist
19 is 1di neceenar
18
161
16
Prote
16
CEty 8 m00522
CEuy
CE.t
CE
CE
CE.u
SE4,
SE f f=-00.988
SE4u
CF
CF.,
CE 8 n -0.977
10"
Figure 2: Estimated risks in expectation. px scales with n in a setting-specifh way.
Remark 6.2. Regarding parameters other than n as constants, the I's precisely verify the worst-case rates ETV(#CE.sg,, [p) no--0-. 0.5 (Figure 2 (a, b)), ETV(LEELL, ETV(EEE x (p)) ~ (Figure (e, f)).
n (Figure (c, d)), and
Remark 6.3. All Instance 2, and 3 happen to be too easy for cc to be obviously biased. This phenomenon is actually predictable because л (-|s) becomes very close to Uniform (AA) in Instance 1, and to some one in (Arac(AA) in both Instance 2 or for all inputs when n is relatively large. In these cases, TCE largely coincides with #cE,sgl as predicted by Theorem 4.3.
Remark 6.4. The risks of SSEL, in Instance and the risks of TCEE.. in Instance 1 and 2 decay exponen- tially fast, which is consistent with the arguemnts in Remark 6.1, i.e., only vanishing schemes like x² in Instance 2 for PtELL,tl and p in Instance 3 for ACE,, can force their risks to have a polynomial decay. Remark 6.5. We are able to provably explain the good performance (beyond worst cases) of fCE in Instance and 3, in which {(x²)= =O(==1) (Recall the definition of {(-) in Theorem 3.2.) Thus, the instance-dependent bound in Theorem 3.2 indicates benign-cass rate of (TCEEE, (p) S
CONCLUSION
We embark on investigating knowledge transfer beyond pure black- or white-box box regimes and settle its sample complexity, respectively; provided that the teacher can afford (1) only to act as a generative model, or (2) additionally the probabilities at sampled classes, or (3) additionally the logits conditioned on each sampled input. The theoretical analysis unveils crucial insight that tailoring the idea of minimizing CE to new information acquisition scenarios may be sub-optimal in general, provably in knowledge transfer via Partial SLs. Several avenues remain to be further explored.
Huge S and A in practice (Zeng et al., 2022; Almazrouei et al., 2023) necessitate function approximation, which also important to our analysis itself. For example, the equivalent effectiveness of minimizing the CE or SEL loss (with Soft Labels) from an alphabet- perspective may be incomplete after incorporating the approximation error, which may consequently corroborate the empirical superior of the vanilla SEL loss (Ba & Caruana, 2014).
All our upper bounds do not adapt to the student initialization strategy for unseen inputs or labels; while the student may be pre-trained in practice (Gu et al., 2023b; Jiang et al., 2023). Thus it is vital to incorporate the skillfulness of the student before transfer to the convergence analysis.

---

Published as a conference paper at ICLR 2024
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 2004.
conffeeeenalcoofeeeenee
Rishabh Agarwal, Nino Vieillard, Piotr Stanezyk, Sabela Ramos, Matthieu Geist, and Olivier Bachem. Gkd: Generalized knowledge distillation for auto-regressive sequence models. arXiv preprint arXiv:23006. 13649, 2023.
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning, arXiv preprint arXiv:2012.09816, 2020.
Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojocaru, Maitha Alhammadi, Mazzotta Daniele, Daniel Heslow, Julien Launay, Quentin Malartic, Badreddine Noune, Baptiste Pannier, and Guilherme Penedo. The falcon series of language models: Towards open frontier models. 2023.
Zaid Alyafeai, Maged Saeed AlShaibani, and Irfan Ahmad. A survey on transfer learning in natural language processing. arXiv preprint MrXiv:2007.042353 2020.
Anthropic. Model card and evaluations for claude models, 2023. URL https: httpt::t/twwEEEE /tte:///wwwEllsss anthropic c. com ippppocciiooo//oo www.mm/aaaaaooooeoe Card Claude 2 2.pdf. Accessed: Sep. 27,2023.
Jimmy Ba and Rich Caruana. Do deep nets really need to be deep? Advances in neural information processing systems, 27, 2014.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07255 2021.
Leo Breiman and Nong Shang. Born again trees. University of California, Berkeley, Berkeley, CA, Technical Report, 1(2):4, 1996.
Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wahrscheinliccheetttteerr und verwandte Gehiete, 47:1 1979.
Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learming. pp. 783-792. PMLR, 2019.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Yuheng Bu, Weihao Gao, Shaofeng Zou, and Venugopal Veeravalli. Information-theomm understanding population risk improvement with model compression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3300-33000000 0300-3337,000 2020.
Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizii. Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. $35-541- 2006.
Christopher Burges and Bernhard Schölkopf. Improving the accuracy and speed of support vector machines. Advances in neural information processing systems, 9, 1996.
Clément L Canonne. short note on learning discrete distributions. arXiv preprint a7X4772002.11457 2020.
Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred Warmuth. How use expert advice. Journal of the ACM (JACM), 44(3):427-488 1997.
Letian Chen, Rohan Paleja, and Matthew Gombolay. Learning from suboptimal demonstration via seff-supervised reward regression. In Conference robot learning, pp. 1262-1277. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2024
Xu Cheng, Zhefan Rao, Yilan Chen, and Quanshi Zhang. Explaining knowledge distillation by quantifying the knowledge. In Proceedings of IEEE/CVE conference on computer vision and pattern recognition, pp. 12925-12935, 2020,,
Jang Hyun Cho and Bharath Hariharan. On the efficacy of knowledge distillation. In Proceedings of the /EEE/CVF international conference on computer vision, pp. 119944802,200 2019.
Tri Dao, Govinda Kamath, Vasilis Syrgkanis, and Lester Mackey, Knowledge distillation as semiparametric inference. arXiv preprint Xi1::2204400933: 2021.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Gongfan Fang, Kanya Mo. Xinchao Wang, Jie Song, Shitao Bei, Haofei Zhang, and Mingli Song. Up to 100x faster data-free knowledge distillation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6597-6604, 2022.
2022.
Yoav Freund and Robert E Schapire. A desicion-theoretie generalization of on-line learning and an application to boosting. In European conference on computational learning theory, pp. 23-37. Springer, 1995.
Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. Born again neural networks. In International Conference on Machine Learning, pp. 1607-1616.
PMLR, 2018
Leo Gao, Jonathan Tow, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Kyle McDonell, Niklas Muennighoff, Jason Phang, Laria Reynolds, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. framework for few-shot language model evaluation, September 2021. URL htt.s://////// //oii org/ / 0 5281 zenodo. 5371 628.
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pp. 10835-10866. PMLR, 2023.
Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 129:1789-18 1819, 2021.
Jiatao Gu, Shuangfei Zhai, Yizhe Zhang. Lingjie Liu, and Joshua M Susskind. Boot: Data-free distillation of denoising diffusion models with bootstrapping. /CMI. Workshop on Structured Probabilistic Inference & Generative Modeling. 2023a.
Yuxian Gu, Li Dong, Furu Wei, and Minlie Huang. Knowledge distillation large language models.
arXiv preprint arXiv:2306. 08543, 2023b.
Hyeongrok Han, Siwon Kim, Hyun-Soo Choi, and Sungroh Yoon. On the impact of knowledge distillation for model interpretability. arXiv preprint 2tti::2355.17344 2023.
Hrayr Harutyunyan, Ankit Singh Rawat, Aditya Krishna Menon, Seungyeon Kim, and Sanjiv Kumar. Supervision complexity and its role in knowledge distillation. arXiv preprint 2rxiv:2301.12244 2023.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv: 0.t.0.0333.3333 2015.
Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. arXiv preprint arXiv:2104.00 0564411,. 2021.
Zehao Huang and Naiyan Wang. Like what you like: Knowledge distill via neuron selectivity transfer. arXiv preprint arXiv: (00.::/7770002//// 2017
Guangda Ji and Zhanxing Zhu. Knowledge distillation in wide neural networks: Risk bound, data efficiency and imperfect teacher. Advances in Neural Information Processing Systems, 33: 20823-20833 2020.
Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Tuo Zhao. Smart: Robust and efficient fine-tuning for pre-trained natural language models through principled regularized optimization. arXiv preprint arXiv: (9t:::9111033333 20199

---

Published as a conference paper at ICLR 2024
Yuxin Jiang, Chunkit Chan, Mingyang Chen, and Wei Wang. Lion: Adversarial distillation of closed-source large language model. arXiv preprint arXiv:2305. 12870, 2023.
Taehyeon Kim, Jaehoon Oh, Nak Yil Kim, Sangwook Cho, and Se- Young Yun. Comparing kullback-leibler divergence and mean squared error loss in knowledge distillation. arXiv preprint arXiv:2105.08919 2021.
JinyuLi, Li, Rui Zhao, Jui-Ting -ing Huang, and Yifan Gong. Learning small-size dnn with output-distribation based criteria. In Fifteenth annual conference of the international speech communication
association, 2014.
Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Guirajani, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Alpacaeval: An automatic evaluator of ceteructtoo-oollwinnn models. https: gi thub.
haalb/aapaaeee aappa_aevalllll 2,23.
Chen Liang, Simiao Zuo, Qingru Zhang, Pengcheng He, Weizhu Chen, and Tuo Zhao. Less is more:
Task-aware layer-wise distillation for language model compression. International Conference on Machine Learning, pp. 20852-20867. PMLR, 2023.
Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. arXiv preprint arXiv:2304.08445 2023.
Raphael Gontijo Lopes, Stefano Fenu, and Thad Starner. Data-free knowledge distillation for deep neural networks. arXiv preprint arXiv: 2017.
David Lopez-Paz, Léon Bottou, Bernhard Schölkopf, and Vladimir Vapnik. Unifying distillation and privileged information. arXiv preprint arXiv:1511.03644 2015.
David McAllester and Luis Ortiz. Concentration inequalities for the missing mass and for histogram rule error. Journal of Machine Learning Research, 4(0ct)):95-911, 2000.
Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, Seungyeon Kim, and Sanjiv Kumar.
Why distillation helps: a statistical perspective. arXiv preprint arXiv:2005. 2020.
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. in hilbert space. Advances in Neural Information Processing Systems, 33:3351-3361 2020.
Self-distillation amplifies regularization
Rafael Müller, Simon Kornblith, and Geoffrey Hinton. Subclass distillation. arXiv preprint arXiv:2002.03996. 2020.
Gaurav Kumar Nayak, Konda Reddy Mopuri, Vaisakh Shaj, Venkatesh Babu Radhakrishnan, and Anirban Chakraborty. Zero-shot knowledge distillation in deep networks. In International Conference Machine Learning, pp. 4743 4751. PMLR, 2019. 2019.
Andrew Ng, Stuart Russell, al. Algorithms for inverse reinforcement learning, In lemi, volume 1, pp. 2, 2000.
Dang Nguyen, Sunil Gupta, Kien Do, and Svetha Venkatesh. Black-box few-shot knowledge distillation. European Conference on Computer Vision, pp. 196-211. Springer, 2022.
OpenAl, 2023a. URL httph:tt//// http///ppa////////////a////./.aa wtw.aai...oo/aaaaaaaaaaeeee wtt.c/oo////aaao wwom/daal-e---- Accessed: Sep. 28,2023.
OpenAI. Gpt-4 technical report, 2023b.
Tribhuvanesh Orekondy, Bernt Schiele, and Mario Fritz. Knockoff nets:
Stealing functionality of black-box models. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 1954-4963. 2019.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744 2022.
12

---

Published as a conference paper at ICLR 2024
Ashkan Panahi, Arman Rahbar, Chiranjib Bhattacharyya, Devdatt Dubhashi, and Morteza Haghir Chehreghani. Analysis of knowledge transfer in kernel regime. Proceedings of the 31st ACM International Conference Information & Knowledge Management, pp. 1615-161222 2022.
Liam Paninski. A coincidence- based test for uniformity given very sparsely sampled discrete data.
IEEE Transactions on Information Theory, 54(10):4750 4755, 2008.
Wonpyo Park, Dongju Kim, Yan Lu, and Minsu Cho. Relational knowledge distillation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 3967-3976, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Py PyTorch: An Imperative Style, High-Performance Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Baolin Peng, Chunyuan Li, Pengcheng He, Michel Galley, and Jianfeng Gao. Instruction tuning with gpt-4, arXiv preprint arXiv:2304. 03277, 226227,2022 2023.
Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. In International conference on machine learning, pp. 5142-111. PMLR, 2019.
Yury Polyanskiy and Yihong Wu. Information theory: From coding learning. Book draft, 2022.
Zengyu Qiu, Xinzhu Ma, Kunlin Yang. Chunya Liu, Jun Hou, Shuai Yi, and Wanli Ouyang. Better teacher better student: Dynamic prior knowledge for knowledge distillation. arXiv preprint arXiv:2206.06065 06067, 2026.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 18):9, 2019.
Nived Rajaraman, Lin F Yang, Jiantao Jiao, and Kannan Ramachandran. Toward the fundamental limits of imitation learning. arXiv preprint arXiv:2009.05990 2020.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pp. 8821-8831. PMLR, 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint 2rXiv:2204.06122 1(2):3, 2022.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702-1 1716, 2021.
Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua 2014.
Bengio. Fitnets: Hints for thin deep nets. arXiv preprint
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 661-668. JMLR Workshop and Conference Proceedings, 2010.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Suraj Srinivas and François Fleuret. Knowledge transfer with jacobian matching. In International Conference on Machine Learning, pp. 4723-4731. PMLR, 2018.
Jiaxi Tang, Rakesh Shivanna, Zhe Zhao, Dong Lin, Anima Singh, Ed H Chi, and Sagar Jain. Understanding and improving knowledge distillation. arXiv preprint arXiv:2002.03533 2020.
Yijun Tian, Shichao Pei, Xiangliang Zhang, Chuxu Zhang, and Nitesh V Chawla. Knowledge distillation graphs: A survey, arXiv preprint 2302002302..0011, 2023.
13

---

Published as a conference paper at ICLR 2024
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive representation distillation. arXiv preprint ar1iv:1910.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée
Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13977/ 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint ar arXiv:2307.09288 2023b.
Alexandre B Tsybakov. Optimal rates of aggregation. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COL.//Kerel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. 303-313. Springer, 2003.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer series in statistics.
Springer, 2009.
Frederick Tung and Greg Mori. Similarity- preserving knowledge distillation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 1365-1377 1374,,17,2220 2019
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
Aad W van der Vaart and Jon A Wellner. Springer series statistics. Weak convergence and empirical processesSpringer, New York, 1996.
Vladimir Vapnik. Rauf Izmailov, et al. Learning using privileged information: similarity control and knowledge transfer. J. Mach. Learn. Res., 16(1):2023-2049) 2015.
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48.
Cambridge university press, 2019.
Dongdong Wang, Yandong Li, Liqiang Wang, and Boqing Gong. Neural networks are more productive teachers than human raters: Active mixup for data-efficient leowledge distillation from blackbox model. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 1498-1507, 2020.
Guan Wang, Sijie Cheng, Qiying Yu, and Changling Liu, OpenChat: Open-souree Language Models with Imperfect Data, 7 2023a. URL https: /ttp:::///ttttt http//gttttttt//./////////t wtt. htt.t//a..cc...oooooeeeeeeeaaaat
Lin Wang and Kuk-Jin Yoon. Knowledge distillation and student-teacher learning for visual intelligence: A review and new outlooks. IEEE transactions on pattern analysis and machine intelligence, 44(6):3048-3065 2021.
Yizhong Wang. Hamish Ivison, Pradeep Dasigi. Jack Hessel, Tushar Khot, Khyathi Raghavi Chandu, David Wadden, Kelsey MacMillan, Noah A. Smith, Iz Beltagy, and Hannanch Hajishirzi. How far can camels go? exploring the state of instruction tuning on open resources, 2023b.
Zi Wang. Zero-shot knowledge distillation from decision-bassee black- model. In International Conference on Machine Learning, pp. 10675-10685. PMLR, 2021.
Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3(1):1444) 2016.
Junho Yim, Donggyu Joo, Jihoon Bac, and Junmo Kim. A gift from knowledge distillation: Fast optimization, network minimization and transfer learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4133 4141, 2017.
Hongxu Yin, Pavlo Molchanov, Jose M Alvarez, Zhizhong Li, Arun Mallya, Derek Hoiem, Niraj K Jha, and Jan Kautz. Dreaming to distill: Data-free knowledge transfer via deepinversion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8715-8724, 2020.
Ming Yin, Yu Bai, and Yu- Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International CorroonaCCCoooee Conference on Artificial Intelligence and Statistics, pp. 1567-1575. PMLR, 2021.
14

---

Published as a conference paper at ICLR 2024
Bin Yu. Assouad, fano, and le cam. In Festschrifttor for Lucien Le Cam: research papers in probability and statistics, pp.
Springer, 1997.
Li Yuan, Francis EH Tay, Guilin Li, Tao Wang, and Jiashi Feng. Revisiting knowledge distillation via label smoothing regularization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 3903-3911, 2020.. 2020.
Sergey Zagoruyko and Nikos Komodakis. Paying more attention to attention: Improving the perfor- mance of convolutional neural networks via attention transfer. arXiv preprint 1tX.vv:612.03322.
2016.
Aohan Zeng, Xiao Liu, Zhengxiao Du, Zihan Wang, Hanyu Lai, Ming Ding, Zhuoyi Yang, Yifan Xu, Wendi Zheng, Xiao Xia, et al. Glm-130h An open bilingual pre-trained model. arXiv preprint arXiv:2210.02414, 2022.
Borui Zhao, Quan Cui, Renjie Song, Yiyu Qiu, and Jiajun Liang. Decoupled knowledge distillation. In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pp. 11953-11962, 2022.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin. Zhuohan Li, Dacheng Li, Eric. P Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging al--as-a-judge with mt-bench and chatbot arena, 2023.
Helong Zhou, Liangchen Song. Jiajie Chen, Ye Zhou, Guoli Wang, Junsong Yuan, and Qian Zhang. Rethinking soft labels for knowledge distillation: bias-variance tradeoff perspective. arXiv preprint arXiv:2102 202000000000050 2021.
Banghua Zhu, Jiantao Jiao, and Michael I Jordan. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. arXiv preprint arXiv:2301. 1270, 2023a.
Banghua Zhu, Hiteshi Sharma, Felipe Vieira Frujeri, Shi Dong, Chenguang Zhu, Michael I Jordan, and Jiantao Jiao. Fine-tuning language models with caantage-induuee policy aligmment. arXiv preprint Xivv:2336.002311 2023b.
Zhuangdi Zhu, Kaixiang Lin, Anil K Jain, and Jiayu Zhou. Transfer learning in deep reinforcement learning: A survey, IEEE Transactions Pattern Analysis and Machine Intelligence, 2023c.
15

---

Published as a conference paper at ICLR 2024
A ADDITIONAL RELATED WORKS
We review key paradigms closely related our formulation, especially KD; and point the reader to Weiss et al. (2016); Gou et al. (2021); Alyafeai et al. (2020); Zhu et al. (2023c); Wang & Yoon (2021); Tian et al. (2023) for numerous algorithms of knowledge transfer on modalities like sequences, images, graphs, etc. We restrict our survey to the single task of interest: classification.
A.1 INSPIRING PARADIGMS OF KNOWLEDGE TRANSFER IN MACHINE LEARNING
Paradigms of Knowledge Transfer. Knowledge transfer is not patent of neural nets with so ft as their last layers. Similar ideas have realizations for ensemble of classification trees (Breiman & Shang, 1996) and even margin-bases classifiers (Burges & Schölkopf, 1996). Since 2010s, there has been a line of work concentrating on the utilization of trained teacher model and its original training set in a totally white-box manner with the purpose of student accuracy improvement (Hinton et al., 2015; Furlanello et al., 2018; Cho & Hariharan, 2019; Zhao et al., 2022: Romero et al., 2014; Yim al., 2017; Huang& & Wang. 2017; Park et al., 2019; Tian et al., 2019; Tung & Mori, 2019; Qiu et al., 2022). As the computation budget becomes relatively tight with respect to the scale of datasets, another line of works propose to avoid using of the full dataset for teacher pre-training during KD, and resort to architecture- specific metadata (Lopes et al., 2017), synthetic data (Nayak et al., 2019; Yin et al., 2020; Fang et al., 2022), or bootstrapping (Gu al., 2023a) instead; which is dubbed the data-free approach. The sagacious vision that the teacher architecture may be agnostic or the teacher (log-) booo)pptbbbilltty output may least go through certain censorship does not receive enough attention from the community in the of open sourcing (Orekondy et al., 2019; Wang et al., 2020; Wang, 2021: Nguyen et al., 2022). However, after the debut of closed-source and game-changing foundation models, practitioners find it plausibly nice to train their own models to purely mimic the response of these strong teachers. For example, though OpenAI only exposes transparent APIS of ChatGPT & GPT-4 (OpenAI, 2023b) to customers, there has been line of efforts towards distilling black-box language models without even accessing the laye-layer logits (Zheng et al., 2023; Wang et al., 2023b;a). Some primary results (Wang et al., 2023a) show that only letting LLaMA (Touvron et al., 2023a) mimic about 6000 carefully chosen trajectories generated by human-GPT-4 interactions can drastically boost the performance of these open-source autoregressive language models on common evaluation benchmarks (Gao et al., 2021; Li et al., 2023).
A.2 OUR FORMULATION VERSUS PREVIOUS PARADIGMS
Motivated by the progress trend of knowledge transfer, we decouple the formulation of the input distribu- tion p from teacher training details and view the reference poicy x² as the gold standard (ground truth), beyond proxy of it. In the following two paragraphs, we would like to also emphasize the distinc- tions between our formulations and 1) imitation learning (whose performance is measured by reward sub-optimality), or 2) the LUPI framework (Vapnik al., 2015; Lopez- Paz et al., 2015), respectively.
Optimality is not explicitly defined for πt in our formulation, yet we solely want to mimic (the conditional density of) the teacher, so x is dubbed the reference policy. This view aligns with recent belief that foundation models are by definition "good" and in effect black-box teachers, judges, and raters of the student ones (Peng et al., 2023; Liu et al., 2023; Zheng al., 2023). Generally speaking, optimal reward maximization is neither sufficient nor necessary for efficient knowledge transfer (+> accurate behavioral imitation), because an optimal policy can differ from teacher demonstrations (Ng et al., 2000), which may even be sub-optimal itself (Brown et al., 2019; Chen et al., 2021), 1), and pure behavioral imitation can result in constant optimality (Gao et al., 2023; Zhu et al., 2023a).
Remark A.I. This work departs from Lopez-Paz et al. (2015, Section 4. essentially in several ways. First, our results hold for any legal data generating distribution x****xxxx and do not need to assume data-xteacher, data->student hinges the assumption that the teacher learns from data faster than the student, while clarified our formulation of TT that differs completely. Finally, their transfer speed from the teacher to the student relies on the hardness of classification of each data point, e.g., the notion of linear separability (Shalev-Shwartz & Ben-David, 2014), yet we consider the product space of finite domains S Ax which does not have these issues.
-acherr-studdnt transfer rates manually. Second, their result crucially
have
Topies related knowledge transfer across di different tasks modalities are beyond the scope.
16

---

Published as a conference paper at ICLR 2024
Additional Notation in Appendix. For any event I, I" denotes its complementary event. [K] } and [K] = {O.....K 1 for any positive integer K. We set (S,A) = ((S),].A) and index the input and label spaces by (S,A) - [[S]][A]) when necessary. We also use a general notion of Dirac dis- tribution in proving the lower bounds: given any measurable space (2,E), we define Dirac(2,=)(A)) (DED), We denote by log the natural logarithm and adopt the convention Olog0=0.
B MISSING NOTATION, DEFINITIONS, AND DERIVATIONS
Additional Notation in Appendix. For any event I, Ie denotes its complementary event. [K] = {}. and [K] == {O....,K 1} for any positive integer K. We set (5,A) = ((S)...4)) and index the input and label spaces by (S,A) - ([S] [AA) when necessary. We also use a general notion Dirac dis- tribution in proving the lower bounds: given any measurable space (2,E), we define Dirac (r)ac)
(2ED), E. We denote by log the natural logarithm and adopt the convention Olog0=0.
Definition B.1. For i.i.d. samples X drawn from distribution over an alphabet X', the number of occurrences of x is denoted by n. (xx))==== {(x; = æ}. upon which we further measure the portion of X' never observed in X" by the missing mass
mo mo(xx"))= E (n,
(B.1)
It is worth mentioning that, D, SDD), A(D). and A(D,s s)) V S are treated as multisets when fed into functionals like mo (p:-). n,, (-), the cardinality operator -), for example, AA(D.s) (S(D)) while in set operations like (DD) or under the summation sign like Ees(tD where they act as ranges of enumeration, we slightly abuse the notations for simplicity to refer to their deduplicated counterparts.
Definition B.2. Ahe n. (SD))) labels in D mapped from s; = s form a multiset
A(D,s) == {a A: for all (2.a) E s.t. x ==
B.1 MAXIMUM LIKELIHOOD ESTIMATION
AcE.sgl E argmin (D) =EA(AIS)
argmin R)
CE (s), argmin ΣΣ
n (s.a) (D) (D)log(als)
TEA(A(S) NESaE.A
(ssaa (D)
argmin
Σ (S(D))
aEA (S(D)) (ags(als)
(B.2)
REA(A(S)
SES(D)
CEm (0)
Noticing that (B.2) is the summation of the cross-entropy between "(..) (PI,, and and weighted by (S(D)) over S(D), we figure out the explicit solution of fiCE as
[ssaa (S()), SES(D),
(alss)
E (AA)) arbitrarily,
otherwise.
B.2 EMPIRICAL
Loss
(ssa) (D) (als)
iCE, E argmin (D,R)) argmin Σ
2, #ES(D)
lals),
xEA(AIS)
*EA(A[S)
Z.
aE.A
where 2. -= E (D) (als). Therefore, by the same cross-entropy minimization argument, explicit solution
(s.aa) (D)r 0,
(s,a)eD, SES(D), A(D,s),
(D)r(a))
(als)
E (AAA arbitrarily,
s4S(D).
17

---

Published as a conference paper at ICLR 2024
C INFORMATION-THEORETT ARGUMENTS
C.I ADDITIONAL NOTATION IN APPENDIX
We write <L(T||T||A) = EEa-A alphabets S.A to have notations concise. The values of A in the proofs of Theorem 3.1, Theorem 4.1, and Theorem 5.1 different under the same notation. A similar logic applies the values of π, in the proofs of Theorem 3.1 and Theorem 4.1.
for X A(S) and x A(AlS) likewise for
C.2 PROOF OF THEOREM 3.1
Proof. We p to be Uniform(S) and define loss function over A(A]S)x as
(T((((())
(C.1)
Obviously, (A(A)S), becomes metric space. Without loss of generality, suppose A is even, we decompose
[22 1111)
dsA/2+5(TT, = (le (
(C.2)
25
1A/2
SA/2
(TT,T')= >> (T) )=
Σ d (TTT')
(C.3)
s=0j=1
Inspired by Paninski's construction (Paninski, 2008), define n
1+T44/2+3 n (2jls) 1 TsA/2+
A
7 (2) - 1[s)
{(s
x
(C.4)
A
A
2
where 7 11 and be specified later. For any -~ i.e. any pair in {-1,+1]-57 that differs only in the i-th coordinate, the construction of π., leads to
A5/2
24 de(Fr:TT:)= SA
(C.5)
We thereby refer T ~ any pair in (-1,+1] 1/////222/22/1
AS/2 that differs only in one coordinate and obtain
LHS of (3.1) inf
sup
E
- p=Uniform(S)
AS 2A/(SA)
min (1-TV((xx=)).(pxxx Tap!
2
2
A
minexp(
poP!
A
4
PNT
rur
n -2 1+4
exp
4
SA
1-A
2
A
exp
-8 n
A²).
(C.6)
4
SA
where
the second inequality is by Assouad's lemma (Yu, 1997, Lemma 2),
the third inequality holds due to variant (Lemma E.2) the Bretagnolle-Huber inequality,
the first equality holds due to the decomposable property of KL (Tsybakov, 2009, Section 2.4),
the second equality follows from a basic property of f-divergence (Polyanskiy & Wu, 2022, Proposition 7.2.4).
18

---

Published as a conference paper at ICLR 2024
the last equality is by the definition of π; in (C.4) and p= D=Uniform(S),
the last inequality derives from we impose.
σ,æ and an additional constraint A 0.5
The assignment A = -0.25 /S4/a with n 2//44ss is feasible choice for inequality (C.6) to hold, whose RHS further equals to
exp(-0.5)
SA 71
16
C.3 PROOF OF THEOREM 4.1
Proof. Without loss of generality, we assume A> 2 odd, then for fixed A= 1, which does NOT vary with A, orn in THIS proof, define II = IT [E 48/3), 3/), where
Tr (2j 1 1[s) = S(1 5(1+TaA/2+) A)
2(n+1)
Tr (2j]s)) = 5(1 - S(1-TeA/2t5
AA-1
(C.7)
2(n+1)
5 A
<A(sss) =
2 n+1
To get lower bound on a Bayes risk, we design prior over P as
XT, A (S.Dirc(A(SS)
(C.8)
where
T Uniform(IT):
Intuitively speaking. for for any x sampled from A, p must be uniform over and must some T with uniformly distributed over [-1,+11 $4/2 Therefore, if we let ADD,R) be the corresponding posterior over P conditioned on (D.R) and [(D,R) R. be the marginal posterior over A(A(S), we can by the definition of T and ,, obtain ADD R) (AS) (s,a) E (0....,S-11) [l,...,A11] and π [ RD),, by the Bayes rule,
(DDRR) where for any
[(D,R) [[]]s =1,=)]=,,({ {
or Buddd((a))
T(D,R) (aass) 5(1+)) = [D( ((lls) 2(++1) = otherwise;
S(1-A)
(C.9)
2(++1)
where (recall that A assumed to be odd) we define the "Buddy" for a [A-1]= (l.....A A-....1111. 1) as
1a-1, is even;
Buddy(a)
(C.10)
la+1, a is odd.
The intuition behind (C.9) is that if ~ I(D,R). the marginal posterior of (als) for any seen (s.a) in D must be Dirae concentrated at n (als) and by the design of (=z), ( ()) is also determined (s, (uddd(da) E 'D." 13 Note that the last label, A, designed to be ignored, which we do not consider in both (C.9) and the following argument driven by Fubini's theorem. We define event (s,s,)) for every (s,a) with < as
{=(x,))= (s,4) E or (s,Buddy(c)) ED.
Next, we can apply Fubini's theorem to the Bayes risk with A as prior.
Exx E px TV(7,**Ip))
12 be technically rigorous, say the prior for p over (SS) and the prior for A(A(S) are assigned independently, similar assignment also appears in proof of Theoorm 5.1.
Rigorously speaking, x (a)s) in (C.9) refers some concrete realization some (ala))) which is collected by is slight abuse of notation and similar appears in (C.15) in the proof of Theorem 5.1,
19

---

Published as a conference paper at ICLR 2024
8
2
B (ew-DDD(TTT)
Σ
25
#ES
acA
1
BxTNI DD Σl
2$
SES
a<d
+ [B
1
2
Ex ID=(ET))))
E T
2S
B T
B[1(E5(s.a))1)
25
1
S(1+4)
S(1-A)
$2 i(als)
2
1(n+1)
2(n+1)
1
Σ E(L(E5(s.a))DD1 1 s
(C.11)
25
n+1
SES
a<A
P((s,a) &D and (s,Buddy(a)) (
(C.12)
4(n+1
s,0:a<A
S )
1- 1 )
Σ
1-p(s)
Σ s
4(n+1)
n+1
4(n+1)
S n+1
5,0:a<AA
1
4(n+1) 5,0:a<A
n+1
4e(n+1) 2 SA
5(A-1)
(C.
where the inequality in (C.11) holds because of the triangle inequality and A = by design, and the equality in (C.12) holds because for any possible value of x a priori, i.e., any T.. (s,)()
is always (1 (1))/++1)) by the design of II (=-); : the penultimate and the last equality hold due to the fact that the distribution of is always Dirac (S), Uniform(()) no matter whether a priori or posteriori (conditioned on (D,R)). Since the minimax risk is bounded from below by the worst-case Bayes risk (Polyanskiy & Wu, 2022, Theorem 28. 1), the proof is completed.
C.4 PROOF OF THEEREM 5.1
Proof. We assign { = 1/(++1) and design a E (SS) as -0- and p= -=1//n+1 for all other inputs following Rajaraman et al. (2020, Figure I (b)). Then it suffices to get lower bound for Bayes risk given a prior over which we design as
Ag = Dirac xT3.
(C.14)
where
T3 = Uniform (aatoormmmTaatt.aa (F : (-1s) Vss
Intuitively speaking, n² is uniformly distributed over all deterministic policies, which indicates the marginal prior distribution of (-Is) for any is
1 Aa
[a = Dirrac(A..a) A'
We abbreviate the corresponding posterior of Ag (resp. Iaa) conditioned on (D, as Ag (D,Q) (resp.
Ta (D, Q)). which by definition implies A3 Q) Dirac(A(S),p) x T3 (D( and by the Bayes
20

---

Published as a conference paper at ICLR 2024
formula implies that for any SE and T>Ix)
T3 (=(D.))r())==((()))
=1,DES(D); =1/A,SES
(C.15)
Without loss of generality, we assume A> is even and then by Fubini's theorem,
E pxxx ~Ag (xx TV
868
eES
+ ( (+
sES
Em (ox ([(()ES(D)))) = [[VG((())DDDaCCAA))
RES
aEA
>p((s) (s) E NI, E
SES
A/2-1
((D())
Σ
1 A/2-1
((( TVDinn((Ae).Dira(AA44444)))
Σ
A o=0
#ES
[((())(((S(()))
1
A
Σ
(((s))(s
(C.16)
A
2
2
SES
SSS
where the last inequality holds due to the triangle incquality of TV. Therefore,
LHS of (C.16)20.5)
Σ
((s))(s
0.5 Σ ((-p()))()))
SES
#ES
S-1
n
S 1
s
(C.17)
2(n+1)
n+1
2e 2e(n+1)
n
where the second inequality is by only considering the S - 1 inputs with mass 1/(n+1). Since the minimax risk is bounded from below by the worst-case Bayes risk. the proof completed.
D ARGUMENTS FOR SPECIFIC LEARNERS
D. ADDITIONAL DEFINITIONS IN APPENDIX
In this section denote the MILE of by
(S)())
p(-)=
(D.1)
The event B,, defined as follows will be used in the proofs of Theorem 3.2 and Theorem 4.4.
B,, Bo.==((o.(11))===\)).)))))
(D.2)
21

---

Published as a conference paper at ICLR 2024
D.2
PROOF OF THEOREM 3.2
D.2.1 PROOF OF THE HIGHI-POOAABILITY BOUND
Proof.
For |S|> 1, we define
Ug (,==m(((DD))T(((ct((()))
We decompose the LHS of (3.4) as
(2(S(D)) +p(s)- -(s)) TV (-
LHS
π
SES
U2
((s) (+1),
T1
(TV().7)
(D.3)
where the first inequality by triangle inequality and the second one holds due the boundedness of TV. We define another two types of events to bound (i) in (D.3):
(S(D))
[|++]
D,
U1 S
[Allog2+
(D.4)
2 [S]log2+ foog2+log +lo S
F= 2TV Sv
(D.5)
Notice that P(D. B..)) by the definition of B..; in (D.2) and for any > P(D.) ( 5/119))))))) by Lemma E.4; thus by the law of total probability,
2
n
Σ P(B.,))=
S YEES.
(D.6)
S|+1
Also noticing that (PE)) S (|(+++ by Lemma E.4, we apply union bound over E and (D.) for (i) in (D.3) to conclude that with probability at least 1 5,
A +log2+log((e (0)(())++))))) E.es n, (S(D))
18|+1)
Sillog 1 +log 5
(D.7)
2
n
By the Suuchy--chwwrrzznequlall
S n. (S(D))
V in (D.7)
S)
(D.8)
n
n
SES
Substituting (D.8) back to the RHS of (D.7) yields the conclusion. The case of [ = follows from Lemma E.4.
D.2.2 PROOF OF THE WORST-CASE UPPER BOUND IN EXPECTATION
Proof. Taking expectation both sides of (D.3) yields
S
E TV [p)] Eu, +
#ES
S
(VV (TCE (-1s), " (-1s)) ( (S(D))
+
(D.9)
sES
22

---

Published as a conference paper at ICLR 2024
where the inequality holds due to Lemma E.3. For every trivially have
ū, (S()),
(D.10)
if conditioned a0 If otherwise conditioned on B we still have
(IAl)n(((D))
(D.11)
2
where the inequality follows from Lemma E.3. Therefore, substituting (D.10) and (D.11) back to (D.9)
gives
VIA
S SV
S
LHS of (D.9)
E (,()))))
+
Σ aES
p(s)
+
2n
n2
2n
n
aES
S||A
n
where the first inequality follows from the law of total expectation with respect to Bx,0 and B the second inequality follows from Jensen's 's inequality together with the definition of n. (S(D)), and the last inequality is by the Cauchy- Boach-SShwwarzi inequality.
D.2.3 PROOF OF THE INSTANCE- INSTANCE-DEPEDENT DEPEDENT UPPER BOUND IN EXPECTATION
Proof. We define the set of the numbers of occurences of all inputs as
Ng (n,(S(D)):.EE))
(D.12)
Then decompose the LHS of (3.5) as
Σ
[(V (+16), (+|=))
#ES
=E
E
(F (111)))))))))) Ns
#ES(D)
Σ E
TV (V()) (-18s) No
SES)
TV (1))), (1)), (n1)) (S(()) (1))))))))))())))))n(((())))))
SE
Σ #ES(D)
E
+ Emo (P,S(D)
(D.13)
1a
where the inequality by the definition and boundedness of (- (-1s)). We divide I and I2 at to conquer them as follows.
Bounding /t.
For every s S, we define
I E TV ( (1ss) n, (S(D))
Then can bound [s) by Jensen's inequality for sES(D):
1 11(s) -
Σ
FTcE,s(((|s)) -slasssss((aaaaa n. (S(D))
2
a
n. (S(D))
2 AEA
(S(D))
1
π (cls) (als))
Σ
(D.14)
2
n, (S(D))
23

---

Published as a conference paper at ICLR 2024
where the last equality holds due to the observation that
CEE sgl (a|s) (((((())))Biomiaatt((65566) (
Therefore, we can bound the summation inside the expectation of I as
1 - Vp(a) p(8) (als)( (als)
E
(())(())= oEAsES(D)
n, (S(D)
SES(D)
p(s) P(s) x (1(s)(1-<((ls))
p(s)
V2 aEAASS
1+tg(((D))
P(s) T (1(
(D.15)
l+n,(((D))
aEAA
SES
where the first inequality holds due (S(D)) 1,4s S(D) and the last inequality is by the Cauchy-Schwarz inequality, Substituting (D.15) into 1, B(s gives
1 2
Σ REAA
p(s)
11
1+n,(8(D))
#ES
1
2
n+1
8ES
min π (Aa)))
2((++1) 1)
aEA
SES
min(T (dls),
V 1((++)
eEAASS
S
m (als).1==<<(ls))
(D.16)
2(n+1)
((T))
where the first inequality is by Jensen's s inequality, the second inequality derives from Lemma E.8, and the penultimate inequality holds due to the Cauchy- -chwwrz inequality. {(x*) in (D.16) can be further bounded from above by
maxmin
1 (bls+ Σ (als))
maxxin (( (V()"((()) #ES PEA
SES PEA
a:azb
= =mxxistrvv(T (1spdisstt(r((sss.iira) (A)))))))))))) #E8
To sum up. 115 ((
Bounding Iz.
yields
4|8|
S
1 ((s)((1p(s))²=
9n n
where the inequality follows from Lemma E.5.
D.3 PROOF OF LEMMA 4.2
Proof. Since [|] = 1, we omit the conditioning on s E for brevity in this proof. By Lemma E.
#CE 0.8,
24

---

Published as a conference paper at ICLR 2024
Therefore, applying the continuous mapping theorem (Durrett, 2019, Theorem 3.2.10) to (4.4) gives
[ [a){²
(c)
EbEAl=((b))
uniformly for every E A.
D.4 PROOF OF THEOREM 4.3
Proof. By (3.3) and (4.3), (-Is) (s()) and (- x ((((())) for any S Therefore, the solution of #CE. coincides with that of TC only if x* = =Uniform(A)
or x* E DDraa((A); otherwise Lemma 4.2 implies that
(F n=+00
> 0 almost surely,
and we thus rigorously justify the (11) in Table with probability one.
D.5
PROOF THEOREM 4.4
D.5.1 PROOF OF THE HIGH- PROB-PPRBBBIIIIYY BOUNDS
Proof. For |S|>1, define
0, - n, (VV (-Is))
and decompose I.HS of (4.8) into three terms
LHS < Σ TV (-1s),TT (+|s)) + Σ
(-1s))
(D.17)
SES
.ES
mo ((D)))(D)) mutchee Definition B.1
p(s)
U. +
Σ p(s)
(D.18)
#ES
*ES(D)
(ES)
where أ is defined in (D.1) and the second inequality follows from p(s) = S along with the boundedness of TV. We additionally define two kinds events bound (ii) (D.18).
4 A 43
S
D
U2
S
AAllo
V S:
9
1|51
3
1 log
È mo(p)S(D))
On
n
Recall Definition B.2 for A(D s), if if, by (4.7),
2TV (118 (-18)) ( Σ
(11)))
7 (
a
Σ
(alb (T1)))
(D.19)
((D.)(D,ss)
where the inequality holds due to triangle inequality Consequently, Conquulity.oossequentty
V n1 ((8)))))))
to which we apply Lemma E.7 to obtain
P.D <
Vi 0;
S
25

---

Published as a conference paper at ICLR 2024
where B is defined in (D.2). Also noticing that Be. by definition, control P (DD))
by
P(D.) - SP(D. 1 6
8
12 1
Σ P P(B..)
VsES.
S|+2
Since P(E) 21 1-211-6110 -1(())+2))))) by Lemma E.7, we apply union bound over E and ( (Dilees for (ii) in (D.18) conclude that with probability at least - (11)+1))((51+2)),
4/
[Aloog((())
p(s)
(ii) -
|S|+
Σ aES(D)
9n
((s)
(D.20)
4
/
3
S
+
+
log 5
9n
We further decompose A in (D.20) in a pragmatically tight enough way as
((s)
S + Σ np(ss
< S + Σ
((8)
(S(D))
SES(D)
SES(D)
2mp(s)
np((s) n. (S(D) +1
= =|S + Σ
aES(D) n. (S(D) + (S( S S|
Σ
.ES(D)
np(s)
$ <18 +2
n. (S()))) +1
np(ss) n. (S(D))+
np(s) n. (S(D))++
= -|8 +
(D.21)
#ES
where S "and& S are defined as
sES:0<p(s) log( (((( 200
(D.22)
99
5 sES: 2 log ((())
200
(D.23)
99
By the definition of S, all s's in S have small enough p(s), and thus in (D.21) can be trivially bounded from above, i.e.,
200
Sloog [[([S)+2)
(D.24)
99
For each S, we define
2log( ( ni((s)
then by the definition of S, 1-11 0.1. Therefore, noticing that n. ((s(())))Binmmill((( we can apply Corollary 1.10 to each r, in (D.21) to conclude that for every s S. with probability at least 1 1-5/1 (()))))
T
10
)))(s))ss)+ +1 0.1np(s)+ +1 S
(D.25)
np(2 8
(1
np(s)'
which followed by union bound argument within S yields that with probability at least 1 5/((8)12).
26

---

Published as a conference paper at ICLR 2024
in (D.21)
(D.26)
We then denote by E the event conditioned which (D.26) holds and denote by E the event conditioned on which (D.20) holds. union bound argument over E and E shows that with probability at least 1- 6, the LHS of (4.8) is bounded from above by
|Allog ( +2)/6)
200 [2|
S
+22
4
/
S
S
+2
loog
+
log
9n
99
8
9n
For ||= = invoking Lemma E.7 for (D.19) to draw the conclusion.
D.5.2 PROOF OF THE UPPER BOUND IN EXPECTATION
Proof.
Substituting (D.19) into (D.17) yields an upper bound for ETV pth TT (p) as
Ev,+
E (()))))))))) (s
(D.27)
SES
SES
Each Ev, (D.27) can be bounded from above via (D.19) by
E
n, (S(D)) (x" (1
(D.28)
Conditioned on Bg invoking Lemma E.5 to conclude
4|41
ú.5
(D.29)
9
The above inequality trivially holds if otherwise conditioned on B,o0- Similarly, we always have
|
4|A1
J. S S(())
(D.30)
n. (S(
9n
Substituting (D.29) back to (D.28) gives
S
Evs
(D.31)
71 #ES
n
By Lemma E.8, substituing (D.30) and (D.31) back (D.27) yields
(S|AA|
p(s)
SIA
(D.32)
n
n. (S(D))
+1
BES
Remark D.I. The empirical variant of vanilla SEL in our second case actually match the log probability, which is by definition normalized. Analyzing unnormalized version, which is more relevant to the matching the logits in practice (Ba & Caruana, 2014; Kim et al., 2021), in the second setting may call for new techniques. Also, some preliminary results the empirical side manifest the difference between minimizing forward KL and reverse KL in scenarios related to our last setting (Jiang et al., 2019; Gu et al., 2023b; Agarwal et al., 2023), whose analysis are left future work.
27

---

Published as a conference paper at ICLR 2024
D.6 PROOF OF THEOREM 5.2
Proof. Since TV is bounded from above by and TV ((s)
LHS E ((c)TV(FCEn, ([s)),=((())))))))))))))))) [ (()) =
(D.33)
(ES)
SES
Noticing that realizes Definition B. to mo (p,S((D)) we invoke Lemma E.7 to get
M EMM+ 3v |Sloo 1/6)
4 3 ///oooo((1/0)
(D.34)
9n
Substituting (D.34) back to (D.33) finishes the proof.
E AUXILIARY LEMMAS
In contrast with other non-asymptotic tools below, we must assume the mass does not vary with in the asymptotic guarantee Lemma E.
Lemma E.1. Let p be a probability mass function over an alphabet S, whose empirical estimation from X1 Xn i.i.d.
is pm (-) = Σ. [|X:=//n, then
Pn Pmp P:
where the almost surely convergence is defined under the foo metric in RR
Proof. Without loss of generality, assume S [[8]]; thereby inducing F(x) F(x))F(xx-- for x E [[S]]. where F(x) = PP(X s x)) is the distribution function of X ~ Similarly, Pr (x(x) = (n()) 11 for
F.()) P()
Therefore,
max (r(x)) - -p(x)
S <supl supp (z) (())FF((--FFl))) (F) F(x--(11)11))
zE|[S|
zER
< Fn F()) = -Fllo.
æek
The proof is thus completed by invoking the Glivenko-Cantelli Theorem (Van der Vaart, 2000, Theorem 19.1).
E.1 BOUNDING TV FROM ABOVE
Lemma E.2 (Bretagnolle-Hubee inequality (Bretagnolle & Huber, 1979)). If P and Q are two probability measures the measurable space, then
TV -xx0)) (xxp(KKL(PIQ);
i.i.d. Lemma F.3. If af. π (AA,), whose M and |A| < co, then
A
ETV
m
Proof. We reproduce the proof of this standard result here for completeness.
LHS
Σ
(1
-B(F(u)-m(a)>
2
aEA
aEA
1
Σ
Var Var(nn((a)
(10)(117(())
2
n2
2
aEd
aEA
28

---

Published as a conference paper at ICLR 2024
1 A a(a)= S 2V n
2/
where the first inequality by Jensen's inequality, the third equality holds due to n (i(lm)))iBi (a)), and the last inequality is by the Souchy-Schwarz inequaity.
Lemma E.4. Under the same setting as Lemma E.3, for any é (0,1), with probability at least 1-
A Algg2 (log20)
TV(
2n
Proof. This is straightforward corollary of the Bretagnolle Cestnoolll--uee---ee Huber- CareerrCrrll inequality (van der Vaart Wellner, 1996, Proposition A.6.6) based on the relationship between TV and f1
E.2 MISSING MASS ANALYSIS
Observations like Lemma E.5 are key and common in the analysis of learning from finite and static datasets (Rajaraman et al., 2020; Rashidinejad et al., 2021).
Lemma E.5. For [0,1],n ax1 (1==)" < (4/))..
Proof. By taking the derivative w.r.t. 2,
n+1 1 lim (1
1
1 en
4
max LHS
)
<
n+1
7
n+1
9n
Lemma E.6 (Rajaraman al. 2020, Theorem A.2). Given a distribution v on an alphabet S and i.dd samples X i.idd. v, then for any de (0,1/10), with probability at least 1 ò.
3 SV/[(og(1//)
Lemma E.7. Under the same setting as Lemma E.6, for any 8 (0, 1/20,, with probability least 1-8.
ma (v, Σ 4|5|
3v 3//8]log(1/0)
9n
n
Proof.
(mp(v,X") = ( ((xE))(
4
(E.
9n
#ES
where the inequality holds due to Lemma E.5; we conclude that vo e (0,1/10), with probability at least 1 1-8,
4
/v/S]log(1/6)
(o(
9n
by substituting (E.1) into Lemma E.6.
E.3 UPPER BOUNDS FOR Binomial(n.p)
The following two bounds for X ~ (innomia(((np))) both follow from E[2x]= (1-ptpe)",YEER Lemma E.8. Let X ~ Binomial(n..p). pe (0,1),
X+1
p(n+1)
29

---

Published as a conference paper at ICLR 2024
Proof. This folklore (Canonne, 2020) derives from observation that by Fubini's Theorem,
E
B[2 Idz,
X+1
whose RHS is
J (1-ptpe)ddz- (1-ptpz)att
1-(1-p)
p(n+1)
p(n+1)
p(n+1)
Lemma E.9. Let X Binomial((n-p)) For any 7y (0,1),
npp
P(X (1-)()))))p) S exp
Proof. A combination of Mitzenmacher & Upfal (2017, Exercise 4.7) and the proof of Mitzenmacher Upfal (2017, Theorem 4.5) yields the upper bound, which we provide here for completeness. For any <00, by Markov's inequality,
E (1+p(e--1)))
(1-)))=
=P =((c <e (((1=)))p))
elll n/mp
et(1-1/)nn
cxp(np(c'-1)) e((1-))mp
exp((e' e!(1-n)
en
up
(1
(1-1)
where the last inequality follows from 1+0 M TR and in the last equality set to 77). It remains to show
(1- á (0,1).
(E.2)
We thereby define -
= 1 (1 direct calculation gives
("(n)= 1- 0,
So f is nonincreasing in (0,1) and thus (E.2) holds.
Lemma E.9 helps us obtain a high-probbbiilty counterpart of Lemma E.8. Corollary E.10. Let X ~ Binomial(nn.) and > 0. For any 8 E (0,1), if
2log(1 (1/8) <1
np
then with probability at least 1 1-
X+1
(1 1-n)mp+1
Proof. By Lemma E.9,
npppp
5 Sexp.
=6.
X+1 (1 (1-m)m+1
2
30

---

Published as a conference paper at ICLR 2024
F HARD-TO-LEARN INSTANCES FOR EXPERIMENTS
For every & S, T- (- == 0.5Uniform( + 0.5Dirac(A,s modA+1] because any reference policy far away from both Uniform(AA) and any one in Dirac(AA) is sufficient to reveal the disadvantage of ptp according to Theorem 4.3. p Uniform(S) is enough to ensure about n/s visitations of each input.
Instance 0
Interestingly, we conjecture there does not exist corss-of-three-wooe instance that can simulta- neously expose the fundamental limits of #c..sgl TsEL, and TTE... in that the constructive proofs (in Appendix C) of Theorem 3.1, Theorem 4.1, and Theorem 5.1 since the progressively richer information are substantially different from each other. Since our learners in this section is uniformly initialized over unseen labels, any single instance covered by the Bayes prior in the lower bound arguments of a setting"* 14 is sufficient to numerically illustrate the corresponding difficulty of estimation (learning).
To verify the minimax optimality of #CEE with only samples avaiable, we adapt the proof of Theorem 1 (Appendix C.2), which is based on Assouad's hypercube reduction (Yu, 1997). In numerical simlations, any vertex of the hypercube is applicable since we have already enforced an uniform initialization of any स in unseen inputs. We choose the teacher policy
Instance 1
n"' m2 (1s)-1|s)= 1 1.0.25 SA/n ST (2jls)= 1-0.25 SA/n ((sj)E
A 2
A
A
and Uniform(S) for simplicity. The two key insights behind the design of Instance 1 are (1) P must be nonvanishing in (((S)) inputs to manifest the hardness of |S] > O, (2) TV("** (1ss Uniffrm((()) = -n -0.0 ) is crucial for Instance to be hard enough for any minimax opti- mal learner. (If) [A] is odd, simply let the last label A to have zero mass and replace A with A here.)
To verify the minimax optimality of ĀtE with sampled odds avaiable, we adapt the proof of Theorem 4.1 (Appendix C.3), which is based on a carefully designd Bayes prior. Similarly, we can use any single instance covered by the support of the Bayes prior. We choose the teacher policy
Instance 2
S "" (2)ls) = 0,m= (Als) =1 "" (2j 1|s) n+1"
S A-1
A-1
2 n+1 [(s.)) x
and p Uniform(S)) for simplicity. (If AA is even, simply let the last label A have zero mass and replace A with A - here.)
Instance 3 To verify the minimax optimality of âCE... with complete logits avaiable, we adapt the proof of Theorem 5.1 (Appendix C.4), which includes a specialized to slow down the convergence of fCE Specifically, p= (n 1)) 1 for inputs except the last one. Theoretically, the assignment of n* will not affect the convergence of aCE so we use xt* same as that in Instance 3 only to ensure that TtEL,pt is not able to converge too fast.
G DISCUSSIONS: DEPENDENT SAMPLES IN REWARDLESS MDPs
Besides the popular approach of fine-tuning L.MMS (Ouyang et al., 2022; Touvron et al., 2023b) that interprets instructions as inputs and the entire response label, there a more granular perspective where each token is considered a label a; (See, e.g., the logprobs option in the OpenAl completion 5P and 8,41 is simply the concatenation of 8; and a,, i.e., 81+1 IP((|s; a:). where IP is the deterministic transition kernel induced by concatenation. Our bounds for i.i.d. samples already subsume this plausible more involved case through lack of reward. The following reductions hold for any IP A (A|S x A) including the aforementioned concatenation kernel.
The proof of any lower bound remains valid long as (P((ls, = p(.), E S x A in the constructed hard-to-learn instance, making the samples i.i.d. Our upper bounds allow to explicitly depend on and even P, so the samples can be viewed as i.i.d. samples from d x given the input
MSee, g.g., Appendix C.3 for a concrete Bayes prior use. 15ttps: http//patfffft ftrrm........oom.oommmmmm openai cww//oca//aaecccccooccccccccaaaa re https///ppp..teeeeeeeee/o/ooooaa Togprobs
31

---

Published as a conference paper at ICLR 2024
meassue d.f. EA(S) is well- Hence, replacing p with de. validates all arguments
occupancy measure for upper bounds. Intuitively, d= (s) is the probability of visiting s in a trajectory induced by the transition kernel IP and reference policy x². is well-developed in either episodic MDPs (Yin et al., 2021) or discounted MDPs (Rashidinejad et al., 2021). These seamless reductions crucially hinge on the absence of value functions and any notion of reward signal in our theoretical framework.
Remark G.1. Our analysis covers but is not specialized to the case where p depends on x² or vice versa. Therefore, the result remains unchanged regardless of the relation between and the original training set for training the teacher x². (For example, p may be the distribution of instructions selected by maintainers on the student side (Peng et al., 2023).) It will be intriguing if some further analysis can show any impact of teacher training or data quality on the students' statistical rate.
H DICUSSIONS ON FUNCTION APPROXIMATION
H.1 LOG-LINEAR AND GENERAL SOFTMAX CONDITIONAL DENSITIES
We discuss potential ways and obstacles of generalizing the results above to large even uncountable (continuous) state space. First, we extend the concept of conditional probability space (-1--) to general spaces rigorously. In the following discussions, we assume the notation Y and A refer to finite sets for simplicity. (-)) in this section receives any standard Borel space as input and returns the set of probability measures it.
Definition H.1 (Polyanskiy & Wu 2022, Definition 2.8). Given two standard Borel spaces X,D', conditional probability (the teacher/student we considered in this paper) ग X + a bivariate function (+I-), whose first argument is measurable subset of y and the second is element of X, such that:
Vz 1 is probability measure on y, and
V measurable ACD, (x((x) is measurable function X'.
The following preliminary result (whose proof deferred Section H.3) may shed light on prospective approaches to the analysis of function approximation.
Proposition H.2. For standard Borel spaces X' and V. if both म, A())))) are log-linear, i.c., #= II = II(,00). where
A (() xcxp
and sutsse..eexsyylllloa. M; then for any V A<())
TV( M
(H.1)
H.2 TAKE-HOME MESSAGES AND CONJECTURES
Obviously, any analysis leveraging Proposition H.2 potentially generalize results, since log-linear π² subsumes tabular T². Technically, (H.1) mainly hinges on the (uniform) M-Lipschitz continuity of (6)00 with respect to 0 for any A E TR.. therefore, it is also conceptually straightforward to extend Proposition H.2 to general Sofxmax π², which we omit here for brevity.
Based on (H.1) 1), we conjecture that a fine- grained analysis of the norm of 0-0" may be the key to bound TV (,, .. (p) from above for any म, E (AASS) and E A(S). Since the tabular setting
TV(
a special case of the log-linear setting, we also conjecture that 0 0" and 0 0+
4/n via Hard Labels
2
2 d/n via Partial SLs.
32

---

Published as a conference paper at ICLR 2024
H.3
PROOF OF PROPOSITION H.2
Proof of Proposition H.2. For any E X,
+ (y(2z) (1)(2)
(L( Σ
(1ylx)))og
yEy
(0(x,)),-0)) +log Excvexp( (0(c..)).))
Σ
((ilz))
Ejeresp (0(z.)).6)
Yey
exp exp((10/20) (00((0(0)))0)))
t(ilz) (01,,)) 0)
JEY InEyexp (xke)xx((((111))) (0(o..))..) (o(aw),0-0)
Ey
Σ ((,;),)0)
Ey
> - VEV
6-0 2
0/2:
<2TV(+((0),*((1b)) M
(H.2)
where the first inequality holds due to the log-sum inequality, the second inequality is a combination of triangle inequality and Cauchy- Schwarz inequality, and the last inequality is by the boundedness of & together with the well-known 2TV = l relation. We plug (H.2) into Pinsker's 's inequality to obtain
[TV( (L
So (V 6|
33


Reviews:
[{"review_id": "PKjax0nWEi", "reviewer": "Reviewer_ADJF", "summary": "The authors provide minimax rates for transfer learning, expressed as the total variation between between a learner and a reference policy or a ground truth distribution, for different levels of knowledge shared with the learner and losses such as cross entropy and squared loss. They also present simulations to demonstrate the performance of their results in the various transfer settings.", "questions": "It would be helpful to have more specific explanation for the settings of transfer using Partially Soft Labels and Soft Labels in sections 3 and 4. It looks like $\\mathcal{D}$ is already generated using $(\\rho \\times \\pi^\\star)^n$. It is not clear what additional information is provided with $\\pi^\\star(a_i\\vert s_i)$ in the case of partially soft labels.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* Their work explores various ways of sharing knowledge and allows for flexibility on how teachers can assist learners.\n* Their theoretical results show that learners might not require too much data. Since their results are for commonly used losses in practice, this can be helpful in engineering other ways of knowledge sharing.", "weaknesses": "For someone who is not familiar with the literature in this field, many notations lack proper definitions or sufficient rigor. For example, there is no clear definition provided for \"privileged information,\" and it would be beneficial for completeness to include such definitions. The technical aspects of their three settings are not distinctly emphasized. Many variables, such as $CE_{sgl}$ or $CE_{ful}$, are referenced without prior definitions. Furthermore, $\\Delta(\\mathcal{A} \\vert \\mathcal{S})$ is mentioned without an initial definition, and it's only later clarified that $\\Delta(\\mathcal{A})$ represents a simplex. \n\nIt took multiple reads to understand the impact of their main contribution. This paper might need several revisions because as it stands, it is not easily understandable.", "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": "IHepqdG9qh", "reviewer": "Reviewer_CQ5M", "summary": "This paper considers the problem of knowledge transfer through empirical samples from a teacher to a student. They characterize sample complexity for three different settings. The first setting is hard labels, where the student knows (input, label) samples from the teacher, the second setting is when the student knows (input, label, prob(label|input)) samples, and in the third setting, the student knows (input, label, prob(.|input)). The paper characterizes the lower bound and matching upper bounds in each of the settings, showing the statistical roles of extra information present to the student.", "questions": "* How can these guarantees generalize to more practical settings where the state space is large? (speculation is fine)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Neat results and message", "weaknesses": "- The tabular setting is quite basic which does not capture many practical settings when the state space is large.", "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": "bIxJUoQq5X", "reviewer": "Reviewer_2SeV", "summary": "This paper attempts to create a mathematical model for a simplified version of \"knowledge transfer\" from a teacher to a student within the context of multi-class learning. Notably, the authors make two key assumptions: that both 1) $\\mathcal{S}$ (representing the space of all possible queries a student can pose to a teacher) and 2) $\\mathcal{A}$ (denoting the space of all possible answers provided by the teacher) are finite.\n\nIn mathematical terms, for each query $s\\in\\mathcal{S}$, let $\\pi^*(\\cdot\\vert s)$ represent the (optimal) teacher policy, or the conditional distribution of labels for the query $s$. The student's goal is to learn $\\hat{\\pi}$, a finite distribution with the same complexity as $\\pi^*$, using only $n$ i.i.d. queries (and answers) from the teacher, represented by the set $\\\\{(a_i,s_i)\\\\}$ for $i\\in[n]$.\n\nIn this context, the authors aim to establish minimax bounds for $\\mathbb{E}_{s\\sim\\rho}\\left[\\mathsf{TV}\\left(\\hat{\\pi},\\pi^*\\vert\\rho\\right)\\right]$, which measures the \"$\\rho$-expected total variation distance\" between the teacher and student's policies. Here, $\\rho$ signifies the distribution that generates queries across $\\mathcal{S}$. The paper successfully derives minimax rates for this problem under three different scenarios: i) when only hard labels are provided, ii) in cases where, in addition to labels, the probability of the label from $\\pi^*$ is also given, and iii) when all class probabilities are given for each query.\n\nThe paper is well-written, and it meticulously references pertinent prior research (as far as I can tell). The mathematical derivations appear sound, with no conspicuous errors. Moreover, there are several experiments, though I haven't examined them closely. Overall, this is a commendable theoretical contribution. However, I believe that the assumption of finiteness for both the \"query\" and \"answer\" spaces oversimplifies the problem, leading to bounds that might not be as intriguing as one might hope (please refer to the weaknesses section for further clarification).\n\nMy vote is a weak accept.", "questions": "Pleae see \"Weaknesses\" section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is very well-written. In particular, the \"Prior Works\" section stands out as highly informative.\n\n- The problem formulation and motivations, especially the connections to Large Language Models (LLMs) and other foundational models, are immensely intriguing.\n\n- The theoretical framework developed in this work appears robust and sufficiently rigorous for a theory paper at ICLR. I scrutinized some of the proofs and did not find any significant errors. Furthermore, the other results seem mathematically sound.\n\n- The problem is analyzed under three distinct regimes, with the gradual introduction of additional side information to the original dataset. This approach allows the reader to observe, in a step-by-step manner, the mathematical impact of incorporating each layer of side information.\n\n- The paper also includes some experimental validations, although I did not review them in detail.", "weaknesses": "I suppose that the assumptions regarding the finiteness of both $\\mathcal{S}$ and $\\mathcal{A}$ may have oversimplified the problem. Here is my interpretation of Theorems 3.1 and 3.2 (please correct me if I am mistaken):\n\n- In essence, the paper aims to \"learn\" a distribution of dimension ($|\\mathcal{S}|\\times|\\mathcal{A}|$), denoted as $\\rho\\times\\pi^*$. By \"learn,\" I mean the process of minimizing a specific expected total variation (TV) distance, as mentioned earlier. Let me introduce the notation $F = |\\mathcal{S}|\\times|\\mathcal{A|}$. It is already established that having approximately $\\tilde{O}(F)$ (where $\\tilde{O}$ hides polylogarithmic factors) samples, denoted as $n$, is sufficient to capture almost all the probability mass within $\\mathcal{S} \\times \\mathcal{A}$ according to the distributions $\\rho$ and $\\pi^*$. This can be directly derived from the coupon collector theorem. Consequently, in the worst-case scenario where both $\\rho$ and $\\pi^*$ are not sparse, we typically have, on average, $\\tilde{O}(n/F)$ samples for each query-answer pair $(a, s)$. Consequently, the overall distribution $\\rho \\times \\pi^*$, as well as any of its derivatives (such as the aforementioned \"expected TV distance,\" which is the primary focus of this paper), can be approximated with an error of at most $\\tilde{O}(\\sqrt{F/n})$, as a direct consequence of general inequalities like Hoeffding. In my opinion, this summarizes most of Theorem 3.1 and 3.2. However, the rigorious derivation of final formulations, which has been done in this paper, is still a nice addition to MLT community.\n\n- The bounds pertaining to other scenarios discussed in the paper can also be derived using mathematical methods similar to the ones mentioned above.\n\nNonetheless, I commend the authors for their precise determination of minimax rates and their detailed analysis of individual cases. It would, however, be more intriguing if the paper explored more intricate scenarios for $\\mathcal{S}$ and $\\mathcal{A}$. For example, one would naturally expect other (and more interesting) notions of complexity (such as VC-dimension, etc.) of distribution families $\\rho$ and $\\pi^*$ to show up in bounds, instead of the mere cardinality of query-answer spaces.", "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": "3cvB67lEIe", "reviewer": "Reviewer_v1b9", "summary": "The authors consider the problem of knowledge transfer between a teacher (e.g., LLMs) and a student classifier (given limited privileged information). They show the fundamental limit of the transfer under three regimes: \n1. only input-label pairs are observed. The optimal rate is $\\sqrt{\\frac{|S||A|}{n}}$, achieved by MLE.\n2. teacher probabilities of sampled labels are also available, then the optimal rate is $\\frac{|S||A|}{n}$, achieved by empirical SEL loss\n3. complete logits are also given, then the optimal rate is $\\frac{|S|}{n}$, achieved by KL divergence minimization\nNumerical simulations are also provided.", "questions": "1. What is the main difference between your setting and the usual statistical learning setting? For example, if I change your notation in the following way: \"input\" $s$ change to \"feature\" $x$, label $a$ change to $y$, then your setting (hard labels) seems to be completely the same as the usual setting of observing data $\\\\{(x_i,y_i)\\\\}\\_{i=1}^{n}$, and the goal is to predict $y$ from $x$. It seems that there is not \"knowledge transfer\" (unless you call the usual machine learning \"knowledge transfer from ground truth\").\n\n2. The results is fully tabular. Can you generalize your results to continuous case?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "quality: high, provide thorough investigation under three regimes, including matching upper and lower bounds.\nclarity: good, the setting is easy to under stand, and the structure of the paper is clear", "weaknesses": "The setting of \"knowledge transfer\" seems to be fancy. But according to the definition, the teacher distribution is considered as \"ground truth\" that is already given, thus the \"hard labels\" regime seems to fall in the common statistical learning framework. I am not sure whether tabular settings under usual statistical learning framework have been studied.", "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 (poster)