Optimal Learning of Kernel Logistic Regression for Complex Classification Scenarios
Authors: Hongwei Wen
Annika Betken
Hanyuan Hang
Venue: ICLR 2025 Poster (2025)
Keywords: complex classification scenarios
long-tailed learning
domain adaptation
transfer learning
kernel methods
logistic regression
learning theory
Primary area: learning theory

Abstract: Complex classification scenarios, including long-tailed learning, domain adaptation, and transfer learning, present substantial challenges for traditional algorithms. Conditional class probability (CCP) predictions have recently become critical components of many state-of-the-art algorithms designed to address these challenging scenarios. Among kernel methods, kernel logistic regression (KLR) is distinguished by its effectiveness in predicting CCPs through the minimization of the cross-entropy (CE) loss. Despite the empirical success of CCP-based approaches, the theoretical understanding of their performance, particularly regarding the CE loss, remains limited. In this paper, we bridge this gap by demonstrating that KLR-based algorithms achieve minimax optimal convergence rates for the CE loss under mild assumptions in these complex tasks, thereby establishing their theoretical efficiency in such demanding contexts.

Published as a conference paper at ICLR 2025
OPTIMAL LEARNING OF KERNEL LOGISTIC REGRES- SION FOR COMPLEX CLASSIFICATION SCENARIOS
Hongwei Wen & Annika Betken Faculty of Electrical Engineering, Mathematics and Computer Science
University of Twente Enschede, The Netherlands {h. wen, a beu.beeeeeeeetuueee.e.ee
Hanyuan Hang
Hong Kong Research Institute
Contemporary Amperex Technology (Hong Kong) Limited Hong Kong Science Park, New Territories, Hong Kong hanyuan07 21225mmmmm.... com
ABSTRACT
Complex classification scenarios, including long-tailed learning, domain adap- tation, and transfer learning, present substantial challenges for traditional algo- rithms. Conditional class probability (CCP) predictions have recently become critical components many state-of-the-art algorithms designed to address these challenging scenarios. Among kernel methods, kernel logistic regression (KLR) is distinguished by its effectiveness in predicting CCPs through the minimization of the cross-entropy (CE) loss. Despite the empirical success of CCP-based ap- proaches, the theoretical understanding of their performance, particularly regard- ing the CE loss, remains limited. In this paper, bridge this gap by demonstrat- ing that KLR-based algorithms achieve minimax optimal convergence rates for the CE loss under mild assumptions in these complex tasks, thereby establishing their theoretical efficiency in such demanding contexts.
INTRODUCTION
Classification is key problem in machine learning that involves predicting categorical labels from input features. It plays crucial role in applications ranging from image and speech recognition to
medical diagnoses and financial forecasting. In real-world scenarios, classification is often compli- cated by various challenges, like imbalanced label distributions, missing labels, and limited labeled
data. These issues make direct classifier training particularly challenging, leading to the develop-
ment of specialized approaches such long-tailed learning (Kim et al. 2020: Lin 2023 Chen &
Su 2023), domain adaptation (Lipton et al. 2018 8 Bai et al. 2022 Wen et al. 2024). and transfer
learning (Radford al. 2021 Zhu al. 2024 Li et 2024).
A common strategy to address these challenges is to first estimate conditional class probabilities
(CCPs) on related labeled datasets, followed by reweighting or adjusting these estimates for the tar- get problem's 's CCP estimator and classifier. Since accurate CCP estimation on related datasets is crucial for the algorithm's 's practical performance, it important to use methods that are proficient in CCP estimation across various tasks. Logistic regression (LR) (Kleinbaum & Klein 2010), specif- ically designed for modeling CCPs in classification problems, estimates CCPs by fitting a logistic function that achieves linear separation of input data through the minimization of cross-entropy (CE) loss (or equivalently, logistic loss). However, LR is inherently limited to linearly separable data and performs poorly with non-linen -ineeiny separable data. To address this limitation, kernel logistic regres- sion (KLR) (Wahba et al. 1995 Zhu & Hastie 2005) extends LR by incorporating the kernel trick, which maps data into digh-dimessionll feature space using kemel functions. This approach ables linear separation that space, effectively handling non- non-linearly separable data. Unlike other kernel-based classifiers, such support vector machines Gaussian processes, KLR not only han-

---

Published as a conference paper at ICLR 2025
dles complex data structures but also provides interpretable CCP estimates without additional steps or approximations.
The existing literature offers limited theoretical exploration of CCP-based algorithms for classifica- tion in complex scenarios, particularly concerning the CE loss. As CCP estimates approach zero, the CE loss becomes unbounded, posing significant challenges error analysis. This unboundedness invalidates many standard oracle inequalities typically used for error analysis under bounded losses (see Steinwart et al. [Steiwitt & Scovel (2007); Blaschzyk & Steinwart (2018) (022)) ). Re- cently, some studies have attempted to address these issues by establishing new oracle inequalities for the CE loss. For instance, |arrrll et al.] (202T) assumed the true CCP function's range to be [1/(e + 1),e/(e (e + 1)] instead of [0, 11, ensuring that the CE loss remains bounded. However, this assumption does not hold for many practical datasets. Similarly, [os & Schmidt-Hieber (2022) truncated the unbounded excess CE loss to ensure boundedness and analyzed the resulting expected loss, but the derived oracle inequalities and convergence rates do not extend to the unbounded CE loss. More recently, Zhang et al. (2024) proposed bivariate function to address the unboundedness of the CE loss in binary classification. However, their proof techniques for verifying the variance bound in the oracle inequality are not directly applicable multi-class classification.
(Steiwwart&
e/
In this paper, we investigate the convergence rates of algorithms based on CCP estimation using KLR in complex classification scenarios, such long- loig-tailed learning, domain adaptation, and trans- fer learning. We begin by showing that the excess CE risk in these complex scenarios can be reduced to the excess CE risk encountered in standard classification. A significant challenge in this analysis arises from the unbounded nature of the CE loss derived from the true CCP function. To tackle this challenge, we decompose the CE loss into upper and lower components based on the true CCP val- ues, proposing a novel error decomposition for the excess risk of KLR. This decomposition allows the unbounded terms to cancel out, resulting in bounded sample error terms. We can further address these sample errors by establishing new oracle inequality for KLR. Next, we turn our attention to the approximation error associated with KLR. We construct an approximation of the target function that corresponds to the logarithm of the ratio of two CCP functions. However, as the true CCPs ap- proach zero, this target function becomes unbounded. To resolve this issue, we introduce a bounded version of the target function: specifically, the logarithm of the ratio of truncated CCPs that exceed predetermined threshold. Our findings reveal that selecting a higher threshold results in an approx- imation that significantly diverges from the target function, while a lower threshold yields a closer approximation but introduces a large upper bound on the CE loss. By carefully selecting an appro- priate threshold, we can effectively balance these trade-offs, achieving an optimal approximation error with respect to the CE loss.
The contributions of this paper are summarized as follows.
(i) We propose novel decomposition framework that separates the CE loss into upper and lower components, facilitating the decomposition of the excess CE risk of KLR into approximation and sample error terms. This innovative approach effectively tackles the analytical challenges posed by the unbounded nature of the CE loss, paving the way for the derivation of new oracle inequality.
(ii) We establish an upper bound for the approximation error terms of KLR with respect to the CE loss. To achieve this, we design a bounded approximation function that closely approximates the unbounded true CCP function while remaining above specified positive threshold. By carefully selecting this threshold, the constructed approximation minimizes the resulting error.
(iñi) We derive an overall upper bound for the excess CE risk of KLR by integrating the results from (i) and (ii). By judiciously selecting the appropriate KLR parameters, we further establish the convergence rates for KLR in the aforementioned complex classification scenarios.
(iv) We derive lower bounds for the excess CE risk, which align with the convergence rates of KLR established in (iii). This consistency demonstrates the minimax optimality of these rates, underscoring the effectiveness of existing approaches based on CCP estimation.
(v) We conduct numerical experiments to demonstrate the effectiveness of CCP-based algorithms and to empirically validate the minimax optimal convergence rates established in (ii) and (fv).
2 COMPLEX CLASSIFICATION SCENARIOS
Notations. We use the notation an < bn (or an 2 by) to indicate that there exists a constant 0 such that a, I cbn (or a, 2 cb,,) for all n E N. We write a, x b, if there exists a positive constant E (0, 1] such that chn, S an S +b, for all n E N. For natural number M, we denote [M] :=
2

---

Published as a conference paper at ICLR 2025
{1, M). For a, E R. we define A b min b) and V b == max b). representing the smaller and larger values of a and b, respectively. We denote the (M - 1) dimeesssia simplex as A M- : {A E RM, Σm= fm = 1, fm 2 0, m E [M]}
Standard Classification Scenario. In standard classification problems, we observe i.i.d. data D (X,, Ya)==1 E (X' x y)" drawn from an unknown distribution P on X' x V where X' C Ra denotes the input (feature) space and y == [M] represents the output (label) space. Let p(ylx) be the conditional class probability (CCP) function, and let p(ar) and p(v) denote the marginal density functions of X and Y, respectively. Based on the observations D, our goal to find a classifier h: X - V. In practice, an important approach for training classifier involves fitting CCP estimator P(yla) and then inducing the plug-in classifier defined as arg max F(y(z).
For loss function L V R R. the expectation of Ly,, ((-(2)) with respect to P. denoted as RI,P (f(y(=)) := EP|L(Y, [p]L(Y,,(-IX)i) ((I is referred to as the risk. The smallest corresponding risk is termed the Bayes risk and is denoted as Rī., = inf (p(y))) D: n >>= 6(x,,x) be the Dirac measure, and the expectation of a function with respect to D is given by Enh = n= Di= h(X,, Y:). The expectation of the loss function L(y, 7(-11r)) the empirical risk and is expressed Rr (v(x))
P(y|z) is measurable). Let
with respect D is referred
ED(L(Y, (-]]
Σi= L(Yi, By(,,p((-/X p,(((X,)). The cross-entropy (CE) loss is defined as (y (() = - log Ply J), while the classification loss is defined by Lelass (y. P(1[=)) == 1 arg max pl m[x))- Since RL = (Lcer,(p(() [x)) the Bayes risk R Len. can be achieved by the true CCP function p(y]ar). Therefore, the excess CE risk (TcE.P(((y(=))
Ricg, measures the accuracy of the CCP estimator p(y)2)) in estimating the true CCP function p(y|z). The calibration inequality presented in (Steinwart & Christmann, 2008 Theorem 8.29) establishes relationship between the excess classification risk and the excess CE risk. More precisely, it states
R R. P (F(ll)) - R...er.P S (222(R.....PPP(ll)) - Ric,,)) 1/2.
This illustrates that if the CE risk of a CCP estimator converges the CE risk of the true CCP function, then the classification error of its induced classifier will converge to the smallest possible classification error. Thus, CCP estimation offers more informative insights than mere label predic- tion, enabling improved handling of uncertainty and enhancing decision decision-making processes.
Complex Classification Scenarios. Unlike the standard classification setting, complex classifica- tion scenarios involve labeled samples Dp == (X,, Y2);,, drawn from distribution P on X' x Y, while inference is required for different distribution on the same space. In this paper, we pri- marily investigate three complex classification scenarios in which the class-conditional probability (<x (y) is assumed to be identical to the class-conditional probability p(zly)) that is,
p(zly)= = (<<ly),
Vx E X', y E E y
[M].
Using Bayes' theorem and the assumption in Eq. the CCP function ((y|2>) for the test data can be expressed as
(()))(I)))
(())p(r'))
(())((l)))p(=//pb
<(yla) Em Em ((m)
Em E ((m)p(alm) Σm (aamig(mm)) ((m)m(mm)))()))pmmm
(alu)/p(()))(()))))
w² (u)p(ula))
EM w (m)p(maaa)
where w (y) == q1v) /py) is referred to as the class probability ratio. Let ((y) and ply(z) denote the estimators for w" (v) and p(ylz)), respectively. Then we can derive the CCP estimator for the test distribution as
(
((y()) = ΣM w0 (0m) ((ml))
(3)
Consequently, if the CCP estimation 2)) is available, it is sufficient to estimate w to obtain [yy[z). In the following sections, we will present approaches to estimate w w1) for classification problems in three different complex scenarios that satisfy Eq. (2)
3

---

Published as a conference paper at ICLR 2025
2.1 LONG-TAILED LEARNING
In a long-tailed learning problem (Kang et al., 2020; Yang & Xu 2020), in addition to satisfying
Eq. ( the label probability g(y) known to be uniform, specifically yy q(y) 1/M for any y [M].
In contrast, the label probabilities p(y), where E V. may significantly deviate from a uniform
distribution. The probability ply) can be easily estimated by p(y) := " "h 1(Y, y}. Con-
sequently, the class probability ratio w" (y) can be estimated as ((y) == (w)/p(y) 1/(M)(y)) Furthermore, it is worth noting that in
learning, the classifier hy (r). derived from the es- timator ((y|2)) æ)) in Eq. (3). aligns with the logit adjustment classifier proposed in Menon et al. 2021 A detailed proof of this equivalence is provided in Appendix B
2.2 DOMAIN ADAPTATION: LABEL SHIFT
Label shift problems (Saerens al. 2002) are characterized by Eq. (2) and an unknown label dis- tribution qly). In addition to labeled samples Dp from the source distribution P, unlabeled samples D2 ( are drawn from the marginal probability density q(x)) of the target distribution Q. To estimate w= == (m))
based on the observations == (Dp: D:), Wen et al. (2024) proposes a class probability matching- batching-based based estimator w. This estimator aligns two components: the class probability estimator in the source domain, p(y) := " En 1(Y; v). and the empirical mean of the weighted CCP estimation for the target domain samples, i.e.
F(y(X:)
(v) == n
Σ X,ED - wm (m
(4)
Clearly, the CCP estimation p(y|z) (z) influences the estimation of w" through (y) fore, having accurate CCP estimator p(ylz:) in the source domain is essential for effective label shift adaptation.
(y) in Eq. (4). There-
2.3 TRANSFER LEARNING: LABEL. BIAS
In transfer learning, we assume that the condition in Eq. (2) holds and that the label probability dis- tribution q over ) is uniform. We assume that only the pre-trained model p(ylar) on Dp is available, while labeled pre-trained data Dp itself is not accessible. Additionally, we can observe small num- ber of auxiliary samples D. == (Xç, Y;*) drawn from an unknown data distribution S defined on X x Y, which is assumed to satisfy s(xly) = p(xly). Due to the discrepancy between p(y) and q(y), directly applying the pre-trained model p(y) (x)). fitted on D,, for classification on Q results in poor performance, a phenomenon referred to as label bias. Since p(y) = Σm Ex-pt- (m)p(y/ (/)y)(/))pp) ((m) holds for any y E [M], Zhu et al.) (2024) propose the estimator ply) as the stationary distribution of a Markov chain characterized by the transition matrix Č = =(Ckz) E MxM, with entries given by
Exy :=
Σ ?()X;))
(5)
where nsyj denotes the number of samples from the j-th class in D,. Eq. (5) indicates that the CCP estimator p( x)) also influences the estimation of the label distribution p(v). Given that q(m) for all m E [M]. the optimal weight w² (m) can be estimated as ((y) = (wv)p(yy = 1/(M)(y)
In summary, for these complex classification scenarios-namely long-tailed learning, domain adap- tation, and transfer learning-the CCP estimation p(y (z) not only directly influences the estimator ( through Eq. (3). but also impacts the estimation of the class probability ratio ((y) in the latter two scenarios. Consequently, the CCP estimation p(y(ar) based on the labeled data Dp is a crucial and fundamental component in algorithms designed to tackle these complex classification tasks.
MINIMAX CONVERGENCE RATES OF KERNEL LOGISTIC REGRESSION FOR COMPLEX CLASSIFICATION SCENARIOS
As mentioned in Section 2 in many complex classification scenarios, our objective extends beyond merely training classifier for label prediction; we are also interested in estimating the CCPs to
4

---

Published as a conference paper at ICLR 2025
inform subsequent decision decision-making making. Kernel logistic regression (KLR) (Zhu & Hastie 2005 is par- ticularly well-suited for this purpose, as it is specifically designed to model CCPs in classification problems. Specifically, let f (fm) me]M) be score function, where each element fm. X' I belongs to the reproducing kernel Hilbert space (RKHS) H, with the norm || induced by the Gaussian kernel function k(x, x') ; exp(-I|z x' /2112/22) for J, x' IR and bandwidth param- eter y (Steinwart& & Christmann 2008 The collection of score functions is denoted
F
[f
(fm (fm)m=1 fm E H. e [M 41, fM = =},
(6)
where we set the score function for the M-th class to zero to ensure uniqueness. The corresponding CCP estimator for f E F is given by the softmax function of f. i.e.
(xp(f(())) ps(m|/) ΣØ=1 (x)(f
m E [M],
which models the true CCP function p(m|z). Note that if the CCP estimate of py (ylx) is close to zero, the CE loss - log ()g()()) can become extremely large. To prevent an arbitrarily large CE loss, we truncate the CCP estimator py (m|z). Specifically, given & E (0, (2M)) we define
( ps(mm/p) (p5(ml))) - t) - Eepp((eo)) (() t)²
if py <
(m/ar)
if py 2 (8)
The CCP function Py (m) is truncated & for values of less than I, while those py (mmla) greater than are proportionally adjusted to ensure that Eme(M) Pj (mlar = 1. It can be easily shown that for all E [M] and E X, the condition ply (m/ar) 2 holds, thereby bounding the CE loss. More precisely, we have LCE(y. (cE((.P)((l))) = log p (ylxr) x)) S log
Accordingly, given the bandwidth parameter y > the truncation parameter [0.1) and regularization parameter À > 0, the KLR function fn is obtained through
fo = arg min RLCE. (p) + > JEF
where || : EØ
The regularization term \|l/ penalizes the RKHS norm of functions prevent overfitting. The corresponding CCP estimator is expressed
M-1 ||
f(mla) = P/p (m|x), E [M].
(10)
To analyze the proposed CCP estimator, the following restrictions the distribution P on X x y need to be introduced.
Assumption 3.1. We impose the following assumptions on the probability distribution P.
(i) [Hölder Smoothness] Assume that for any x, E X, there exists an a [0, 1] and Hölder constant Ca. E (c) such that (p(m ((mm(x))=a (p(mm='))p(mmx))) S callx'- forall all E [M].
(ii) [Small Value Bound] Assume that for all E (0, 1]. there exist constants B Z 0 and cæ 0 such that (x(mm)) < 1) S cgl8 for all m [M].
The Hölder Smoothness Assumption (i) regarding the conditional probability function p(m]2 [:) is a common assumption classification tasks (Chaudhuri & Dasguptal 2014 Döring et al. 2017 Xue
& Kpoture 2018 Khim et al.) 2020). According to (i), when is small. the conditional probabil- ity function p(m (x) exhibits sharper fluctuations, making accurate estimation more challenging and consequently leading to slower convergence rates. The Small Value Bound (SVB), i.e. Assump-
tion 3.1 (ii), adapted from Bos & Hhlmidd-Hiibbrr (2022), quantifies the size the set where the conditional probabilities p(m (r) are small. As the conditional probability p(m] (z) approaches zero, the value of log m .r) increases towards infinity at an accelerating rate. Thus, accurately esti- mating small conditional probabilities significantly impacts the value of the CE loss. Therefore, the classification problem demonstrates faster convergence rates with respect to the CE loss when the probability of regions with small conditional probabilities is low (i.e., when is large).
5

---

Published as a conference paper at ICLR 2025
3.1 LONG-TAILED LEARNING
The following theorem presents the convergence rate of the CCP estimator T(v()) defined in Eq. (3)
Theorem 3.2 (Upper Bound), Under the setting in Section 2.1 let Assumption 3.1 hold. Moreover,
let Tyyp) be the CCP estimator as in Eq. with ply x)) being KLR's CCP estimator as in Eq. 410 Then by choosing such that for any up N and for any & 0, with probability pn at least 1 2/ng. there holds
"pp T = Rip 1/((1 (oll+pp))++d and L m with Ç 2 1, there exists an N E N
(LIDAD (112A1J6 +
RLCE Q (Q(y)=)) R Len.Q
np
(11)
Under the same ussumptions-nante that the distributions and Q adhere to the long-tailed setting and that P satisfies Assumption 3.1 the following theorem establishes lower bound.
Theorem 3.3 (Lower Bound). Under the setting in Section 2.1 let Assumption (arrtiooon3]]]] 3.7]hold Moreover, let A be a learming algorithm that accepts data Dp and oulpuls CCP estimator. Then, there exists constant E (0, 1) such that with probability pdp at least c, there holds
(11
inf sup RLCe RE....Q(((1)))) ((((D))) - RiCe. P.Q
-RiieRRiee 2 np
D-a81j04R
(12)
Up to the polynomial term ne with an arbitrarily small ç. the lower bound in Eq. 12 aligns with the
upper bound in Eq. 11). Consequently, the CCP estimator ((y(ar) in Eq. (3) is minimax optimal.
3.2 LABEL SHIFT ADAPTATION
For the label shift problem described in Section 2.2 the following theorem presents the convergence rate of ())(x)) for the target domain.
Theorem 3.4 (Upper Bound). Under the setting in Section 2.2 let Assumption holld Moreover,
let T)) be the CCP estimator in Eq. (3) with Plylæ) being KLR's CCP estimator in Eq. (T0)
-1/ -1/(01+ (AP))aa))) and x n. with C 2 1, there exists an
Then, by choosing x mpp Y x Rpp
Ni E N such that for any up A ng Ni and any E> O, there holds
0- +E (11331ja
RLER. (Q(yl=)) - Rics. S np
+ +log ng/
(13)
with probability pay & Qx at least 1 1/np 1/mg.
Eq. 13) indicates that the convergence rate of the CCP estimator ((y()>) is influenced primarily by the larger term in n. and " where 0 == (1 + 3 A 1)a/((1 + B A 1)a + dd. The terms n and log ny are not critical for the rate of decay. In practice, we typically maintain fixed sample size up for the source domain while the sample size n, for the target domain gradually increases. As ny rises from zero to approximately nig myy decreases from infinity to n, resulting in a faster convergence rate in Eq. 13 that ultimately aligns with the order of n- 1 If ny continues to grow, the order of the convergence rate in Eq. (33) remains unchanged. This illustrates that given the labeled source domain data, certain number of unlabeled target domain samples sufficient achieve efficient performance.
Theorem 3.5 (Lower Bound). Under the setting in Section 2.2 let Assumption hold. In addition, let A be a learning algorithu that accepts data D == (Dpr D and outputs a CCP predictor. Then, there exist a constant e E (0. 1) such that with probability pa to Ox at least c, there holds
inf sup RICE RiCE.Q(((D)) RRin. Q 2 np A P.Q
+ 4
(14)
Theorems 3.4 and 3.5 demonstrate that the CCP estimator (1y[2) in Eq. 3 attains minimax optimal rates, up an arbitrarily small polynomial term, for label shift adaptation.

---

Published as a conference paper at ICLR 2025
3.3 MITIGATING LABEL BIAS IN TRANSFER LEARNING
For transfer learning with label bias, as described in Section 2.3 the following theorem presents the convergence rate for (2)2x).
Theorem 3.6 (Upper Bound). Under the setting in Section 2.3 let Assumption 3.1 hold. Moreover,
let gly (r) be the CCP estimator Eq. (3) in the target domain with p(y(ar) being KLR's ss CCP estimator
in Eq. (10). Then, by choosing À x "p 1 = nop
and t x mp with Ç 2 1, there
exists an N2 such that for any up A n, 2 N2 for any & >> 0, there holds
0148A110 + (14861)04d
R (gylz) Ri.z2.0 2 np
log ng/ng
(15)
with probability pdr p at least 1/mp 1/n
In practice, the sample size of the pre-trained dataset is typically much larger than that of the aux- iliary dataset, i.c. n, > ng. If access to the pre-trained model P(ylar is not available, the transfer learning problem discussed in Section 2.3 becomes the long-tailed learning problem addressed in
Section 2.1 this case, Theorem 3.2 provides the convergence rate ni
-1- (LL-BAL))(((++(AA)aat+)
which is significantly slower than that in Eq. (15). This highlights that mitigating label bias in the pre-trained model is more advantageous than training a new model from scratch, thereby illustrating the effectiveness of transfer learning.
Theorem 3.7 (Lower Bound). Under the setting in Section 2.3 let Assumption 3.1 hold. Moreover, let A be a learning algorithm that accepts data D == (Dp: D&) and outputs a CCP predictor. Then, there exists constant E (0, 1) such that with probability pay @ S at least there holds
inf sup RLCE. (Lcx.o(A(D)) - -Rice. 2 (np V n.) A P.S.Q
(+aAllladd + m.
(16)
Since we typically have np >> n, in practice, the upper bound in Eq. (5) aligns with the lower bound in Eq. (6 up to the polynomial term nš with an arbitrarily small ę. Therefore, the predictor ((y[)) in Eq. (3 is minimax optimal with respect to the CE loss for addressing label bias in transfer learning.
In summary, for the three scenarios discussed, the convergence rates with respect to the CE loss in Theorems 3.2 3.4 and 3.6 are minimax optimal. By incorporating the calibration inequality in Eq. (T). we can derive convergence rates for the classification loss as well. Elementary calculations indicate that when the exponent the SVB Z in Assumption (ii), the convergence rates for the classification loss are also minimax optimal. Further details can be found in Appendix
4 ERROR ANALYSIS
In this section, we present the error analysis of the excess CE risk Q (v](r) - -R; Rice. of the CCP estimation ((ylz)) for the complex classification scenarios in Section
4.1 REDUCING ERROR IN COMPLEX CLASSIFICATION SCENARIOS TO ERROR IN STANDARD CLASSIFICATION SCENARIO
The following inequalities indicate that the excess CE risk 2
Ri of the CCP estimation (gy(2) x)) for the complex classification scenarios in Section 3 can be reduced to the excess CE risk RLCe. (f(y)lz) Ri.cg,P P of the CCP estimation ((y|x)) for the standard classification.
(a) Under the long-taiie learning setting in Section 2.1 we have
RICE @ (Q(lla)) Rice.Q S RRt.,,
RLCE.P + log 1p/11p-
(17)
(b) Under the label shift adaptation setting in Section 2.2 we have
RLcee (((x)=)) Rice. S RLCE. (P(ylP((((lz))) - Ri log my + log np/npp
(18)
(c) Under the transfer learning setting in Section 2.3 we have
RLCE. (Tul=)) - Rice. S (L ()) RiCE,P + log n
(19)
All proofs of the above inequalities Eq. (17 Fq. 18 and Eq. 199 can be found in Appendix D.2

---

Published as a conference paper at ICLR 2025
4.2 EXCESS CE RISK OF KLR STANDARD CLASSIFICATION SCENARIOS
In this section, we analyze the excess CE risk RI.r, [x)] Riee.. associated with the KLR estimator Plylæ) for standard classification. For simplicity, we omit the subseript CE in Le w.l.o.g. To address the analytical challenges posed by the unbounded nature of the CE loss, we decompose the CE loss into an upper part L" and lower part L', based on whether the true CCP exceeds or falls below the truncation parameter as defined in Eq. (8). Specifically, for any CCP function we define these two components of its CE loss as follows:
ps : X + A M-1
(L" o P1) (() L (y. == (p(y)2)) 2 t logpr(y/z)).
(20)
(L' o (=)
== 1(((l/)) t)( log (v/z))
(21)
According to Eq. ( the CE loss of the true CCP function p(y æz) on the upper part L is always bounded. Therefore, suffices to focus on the loss in the lower part L' op, which is unbounded. For notational simplicity, in Eq. as hog == L p'J L p. Similarly, we define the excess CE loss for the upper part and
denote the excess CE loss of the truncated CCP estimator p)} (112z) defined
the lower part h;; = L" ptj L" p and h; L' op L' p. respectively.
Using the CE loss decomposition in Eq. (0 and Eq. 21 we can perform an error decomposition of the excess CE risk associated with KLR's s CCP estimator ply x) as defined in Eq. (10). To this
end, let fo be an approximating function within the space F specified in Eq. (6). Thus, we have
Allfo II. + RL,p(p(y) x)) RL, Allf l2 + RL, (y|z)) Rī,p
(By Eq. (10)
fllll + Ephyjo = Allfoll + EDhhyD - EDhh + Ephpt (By definition of hyg)
S So1l + -EDhys EDhLS + +Ephypp
(By definition of fD in Eq. (9)
Al + Ephy3 + +EDlep
Ephyy + EEphys - -Ephpt
A1166122 + EPhiy
+ (EDR
Ertyy + +EPhi - EDDh
+ (EDh% -Eph%
+ +Bphy
EDD ) (Loss decomposition ha; hi, + 1bpp))
(22)
= folfoolla + Ephe3 + +EEDL' oPj EpL' o ppre) (EpL' o p/p - EDL' p/jp)
+ +EDDig Ephi ) (Ephi p/ ED ) (Simplification by definition of h/p (23)
where the first two summands represent the approximation error, while the last four summands correspond to the sample error terms. Note that although L' p is unbounded in Eq. (22). which causes the excess losses on the lower part-h', and h too be unbounded as well, the unbounded 1
component Lt appears in both p% and h/ and subsequently cancels out. As result, only the bounded parts L' p),, and L' pl/-- which lie within [logt, t, - log t). remain in the final Eq. 23
This ensures that all four sample error terms are bounded, highlighting the ingenuity of our analysis.
4.2.1 BOUNDING THE SAMPLE ERRORS
The following theorem presents our new oracle inequality of KLR for CCP estimation.
Theorem 4.1 (Oracle inequality). Let In be as in Eq. 19 and the truncated KLR's CCP estimator x)y)a) as Eq. (T0. Furthermore, let F be as in Eq. to and the truncation threshold I. < 1/(2M).
Then for any fo F. (,,,0001) 1/2), and Ç > O, with probability at least 1 4e 45,5, there holds
Allfflla + RRe.. - RLcn.P
2 [Al]Soll + R.... P(y (ulx)) Rice.P) P + (- log (1 1 an -1 + C/n)).
(24)
Theorem 4.1 establishes that the excess CE risk of KLR's CCP estimator p(ylz) is bounded by the
sum of the approximation error and the sample error, which correspond to the two terms on the right- hand side of Eq. 24). Specifically, the second term the right-hand side of Eq. (24) provides an upper bound for the four sample error components in the error decomposition presented in Eq. (3)
Further discussions about the oracle inequality can be found in Appendix C
8

---

Published as a conference paper at ICLR 2025
4.2.2 BOUNDING THE APPROXIMATION ERROR
In this section, we establish the upper bound of the approximation error, i.e. the first two summands in Eq. (3 To this end, let p(m( be the CCP funtion and define the score function
-" (f=())
with
Fm (x) = log(p(m)(r)) ht)pm/////pp//p (M)))) m E [M]. (25)
Since Pg RLes. (p(y)z)) and p(y|z)) = py (y/æ) in Eq. (7), is the score function that achieves the minimal CE risk. Therefore, in order to bound the approximation error, we need to construct function fo E F in Eq. (6) to approximate the Bayes score function f However, since p(m|z) can be close to zero, f in Eq. (25) can be unbounded. To address this issue, we consider a truncated version of f", namely, for a given threshold т E [0, (0.1/(2M)), define
f (fm))m [] with (x) log (//l///m/////))/)/ (M[z))
E [M],
(26)
where the truncated CCP function p" (m//x) is defined as in Eq. 8 with Py replaced by
Now, construct a function So F in Eq. 66) approximate the bounded function l*1 To this end, let (xx) := ()) d/2 (11-2||>|//// be the convolution operator induced by the Gaussian kernel function and define the score function
fr == (f MeEM) with (x) = (K * fm (x), m E [M],
(27)
where K f is the convolution of K and fm in Eq. 26
The following proposition presents the approximation error bound when the approximating function So is chosen as f in Eq. (27) with properly chosen T.
Proposition 4.2. Let Assumption 3.1 hold. Furthermore, let y be the bandwidth of the Gaussian kernel and let t E [0, [ be the truncation parameter. Then there exists an fo == f E F in Eq. 27 with 5 == 7ft such that for any S T, there holds
2 + RLLEE, (vl=)) RLCE.P S Xy log" + +lg((7 (...)))))).)... (1(1+
(28)
Proposition 4.2 provides the approximation error bound for fo = j² as defined in Eq. (7 relative to f Eq. (25) This achieved by bounding the approximation error of fo with respect to f in Eq. (6). along with the approximation error of f*r to fr The approximation error bound in Eq. (28) can be upper bounded by (AA + + - O as the bandwidth y - 0 and Ao- -> 0. This illustrates that fo can effectively approximate the unbounded score function f" with respect to the CE loss, aided by the intermediate function f Importantly, the ap- propriately chosen value of T := 7ah not only facilitates the closeness of f to the unbounded target function f* through frr but also ensures that fr remains above specified positive threshold, thus guaranteeing that the CE loss of f is bounded. This effectively resolves the issue of unboundedness in the approximation error analysis.
5 EXPERIMENTS
In this section, we evaluate the CCP-based methods on three classification datasets: the Dioni and Sati imae datasets from the OpenML. Science Platform (Vanschoren et al., (004), and the Gas Sensor dataset from the UCI ML Repository (Kelly et al. (007). A detailed description of the data generation process and the hyperparameter grids for KLR provided in Appendix F
Validation of Effectiveness. The CCP-based estimator ((y(x) in Eq. (3). tailored for complex classification tasks distribution Q, is referred F(ylz) in Eq. (10), designed for standard classification on data from P, is referred to as the baseline method. To validate the effectiveness of the CCP- based method in complex classification tasks, compare its performance against that of the baseline method.
the CCP method. Similarly, the estimator
Table summarizes the label prediction accuracy of the CCP-based estimator (yylx:) in Eq. (3) and the baseline estimator P(y(z) in Eq. (10) on the test data D. drawn from distribution Q, evaluated across three complex classification scenarios. The consistently higher accuracy of the based method compared to the baseline demonstrates the effectiveness of CCP-based algorithms, particu- larly those leveraging KLR, in tackling complex learning challenges using real-wort datasets.

---

Published as a conference paper at ICLR 2025
Table 1: Accuracy real- world datasets across different complex classification scenarios.
Dataset
Method
Long-tailed Learning
Domain Adaptation
Transfer Leamning
Buseline
80.71 0.87
77.69 1.58
80.72 = 0.88
Dionis
CCP
83.67 1.10
82.73 1.40
84.22 # 0.99
Baseline
85.57 5.97
96.14 0.89
85.97 #: 5.57
Sensor
CCP
90.49 = 4.47
96.52 = 1.30
90.27 = 4.78
Baseline
80.51 3.70
89.80 =: 3.90
80.51 3.70
Satimmage
CCP
84.56 1.32
96.46 2.42
84.47 1.98
For each dataset and each method, we highlight the best performance in bold.
Validation of Theoretical Results. As illustration, we conduct experiments on the Di on dataset, chosen for its large number of classes, which makes it particularly suitable for this analysis. To validate the theoretical results presented in Section 3 investigate the effect of varying sample sizes (Mp. Rg. and n,) on the performance CCP-based methods.
L0000
Pym
1880
31230
140.0
14000
3000
1000
4300
7007 DRK
(a) Long-tailed learning
Domain adaptation
Transfer learning
Figure 1: The impact of sample sizes accuracy in complex classification scenarios.
(a) In the context of long-tailed learning, Figure ((a) illustrates that the accuracy on test data from Q improves as np increases. This observation aligns with Theorem 3.2 which asserts that the excess CE risk on Q diminishes with larger nd. Furthermore, according to Eq. (T), this reduction in excess risk indicates that the classification error converges toward theoretical minimum. Therefore, Figure ((a) provides empirical support for the theoretical findings in Theorem 3.2
(b) In the case of domain adaptation, Figure I(b) demonstrates that, for a fixed 12p accuracy improves my increases from 500 to 3000. However, 7hg grows beyond 3000 to 5000, the performance sta- bilizes. This pattern suggests that, given the labeled source domain data Dp. a sufficient number of unlabeled target domain samples ny is essential to achieve optimal performance. Additionally. Fig- ure T(b) highlighhs that when n, is sufficiently large, increasing np leads to higher accuracy. These findings are consistent with the results presented in Theorem 3.4 and the associated discussion.
(c) In the context of transfer learning, Figure [(c] shows that the impact of n, and n. accuracy mirrors the trends observed for np and ng label shift adaptation (Figure ( This similarity
indicates that the observations in Figure [[c) serve as empirical validation of the theoretical results
presented in Theorem 3.6, specifically regarding the roles of np and ng.
CONCLUSION AND FUTURE WORK
In this paper, we investigate the theoretical properties of kernel logistic regression (KLR) in ad- dressing complex classification scenarios, including long-tailed learning, domain adaptation, and transfer learning. By emphasizing KLR's strengths in conditional class probability (CCP) estima- tion. we demonstrate that algorithms based on KLR can achieve minimax optimal convergence rates for cross- cross-entropy (CE) loss under mild conditions. These results provide robust theoretical support for the empirical success of KLR-based methods, showcasing their capacity to operate with opti- mal efficiency in challenging scenarios. Our findings enhance the understanding of the theoretical foundations of CCP-based algorithms and validate their effectiveness solving real-world, com- plex classification tasks. Looking ahead, recognizing that deep neural networks (DNNs) are highly effective CCP estimators, we plan to extend our error decomposition framework to include DNNs. This extension will deepen theoretical understanding of DNNs in complex classification narios. Furthermore, we aim to explore even more intricate learning environments, such as those characterized by dynamic conditions evolving data distributions.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Annika Betken gratefully acknowledges financial support from the Dutch Research Council (NWO) through VENI grant 212.164. The authors acknowledge Tao Huang's involvement in some discus- sions.
REFERENCES
Jean- Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2):608 633, 2007.
Yong Bai, Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama, and Zhi-Hua Zhou. Adapting to online label shift with provable guarantees. S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 29960- 29974, 2022.
Ingrid Blaschzyk and Ingo Steinwart. Improved classification rates under refined margin conditions. Electronic Journal of Statisties, 12(1):793-82) 2018.
Ingrid Blaschzyk and Ingo Steinwart. Improved classification rates for localized SVMs. The Journal of Machine Learning Research, 23115):11559 2022.
Thijs Bos and Johannes Schmidt- Hieber. Convergence rates of deep ReLU networks for multiclass classification. Electronic Journal of Statistics, 16(1):2724-2773, 2022.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor elassification. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27, pp. 3437-3445, 2014.
Jiahao Chen and Bing Su. Transfer knowledge from head tail: Uncertainty calibration under tailed distribution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 19978-19877, 2023.
Maik Döring, László Györfi, and Harro Walk. Rate of convergence of --nnarest-neighhor classifi- cation rule. The Journal of Machine Learning Research, 18(1):8485-850) -500000,0800,,, 2017.
Max H Farrell, Tengyuan Liang, and Sanjog Misra. Deep neural networks for estimation and infer- ence. Econometrica, 89(1):181-213 2021.
Trevor Hastie, Saharon Rosset, Ji Zhu, and Hui Zou. Multi-class AdaBoost. Statistics and Its Interface, 2(3):349-360 2009.
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. The Eighth International Conference Learning Representations, 2020.
Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. UCI machine learning repository, 2007.
uuw.eiissssiieieiioooooo.. www. edu
Justin Khim, Ziyu Xu, and Shashank Singh. Multiclass classification via class-weighted nearest neighbors. arXiv preprint arXiv:2004.04715 2020.
Jaehyung Kim, Youngbum Hur, Sejun Park, Eunho Yang, Sung Ju Hwang. and Jinwoo Shin. Distribution aligning refinery of pseudo-label for imbalanced semi-supervised learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin (eds.), Advances in Neural Infor- mation Processing Systems, volume 33, pp. 14567-14579, 2020.
David G Kleinbaum and Mitchell Klein. Logistic Regression. Springer, 2nd edition, 2010.
Kaican Li, Weiyan Xie, Ricardo Silva, and Nevin L Zhang, Dual risk minimization for robust fine- tuning of zero-shot models. In ICML 2024 Workshop on Foundation Models in the Wild, 2024.
Dekun Lin. Probability guided loss for long-tailed multi-label image classification. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 1577-1585, 2023.

---

Published as a conference paper at ICLR 2025
Zachary Lipton. Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80, pp. 3122-3130 PMLR, 2018
Yufeng Liu, Hao Zhang, and Yichao Wu. Hard or soft classification? Large-margin unified ma-
chines. Journal of the American Statisticul Association, 106(493):166-177 2011.
S. Marron, Michael Todd, and Jeongyoun Ahn. Disthnce-weighted discrimination. Journal of the American Statistical Association, 102(480): 2007.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In The Ninth International Conference on Learning Representations, 2021.
Carl D Meyer, Jr.
The condition of a finite markov chain and perturbation bounds for the limiting probabilities. SIAM Journal on Algebraic Discrete Methods, 1(3):273-283, 1980.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139, pp. 8748-8763. PMLR, 2021.
Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of a classifier to new priori probabilities: simple procedure. Neural Computation, 14(1):21-41, 2002.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Science & Business Media, 2008.
Ingo Steinwart and Clint Scovel. Fast rates for support vector machines using Gaussian kernels. The Annals of Statistics, 35(2):575 607, 2007.
Ingo Steinwart, Don Hush, and Clint Scovel. An oracle incquality for clipped regularized risk minimizers. In B. Schölkopf, J. Platt, and T. Hoffman (eds.), Advances in Neural Information Processing Systems, volume 19, pp. 1321-1328. MIT Press, 2006.
Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer Science & Business Media, 2008
Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes. Springer Series in Statistics. Springer- Verlag, New York, 1996.
Joaquin Vanschoren, Jan Van Rijn, Bernd Bischl, and Luis Torgo. OpenML: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 15(2):49-60, 2014.
Rom Rubenovich Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 11 117:739-741, 1957.
Grace Wahba, Chong Gu, Yuedong Wang, and Richard Chappell. Soft classification, aka risk estima- tion, via penalized log likelihood and smoothing spline analysis of variance. In The Mathematics of Generalization, pp. 331-359. CRC Press, 1995.
Hongwei Wen, Annika Betken, and Hanyuan Hang. Class probability matching with calibrated networks for label shift adaption. In The Twelfth International Conference on Learning Repre- sentations, 2024.
Lirong Xue and Samory Kpotufe. Achieving the time of 1-NN, but the accuracy of k-NN. In Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings the Twenty-First International Conference on Artificial Intelligence and Staristics, volume 84, pp. 1628-1636. PMLR, 2018.
Yuzhe Yang and Zhi Xu. Rethinking the value of labels for improving imbalaneed learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 19290-19301, 2020.
12

---

Published as a conference paper at ICLR 2025
Zihan Zhang, Lei Shi, and Ding- Xuan Zhou. Classification with deep neural networks and logistic loss. The Journal of Machine Learning Research, 25(125)11-17, 2024.
Beier Zhu, Kaihua Tang, Qianru Sun, and Hanwang Zhang. Generalized logit adjustment: Cali- brating fine-tuned models by removing label bias in foundation models. In Advances in Neural Information Processing Systems, volume 36, 2024.
Ji Zhu and Trevor Hastie. Kernel logistic regression and the import vector machine. Journal of Computational and Graphical Statistics, 14(1):185-2055 2005.
13

---

Published as a conference paper at ICLR 2025
In this appendix, begin by introducing some notations in Section A In Section discuss the methods for long-tur learning. while Section covers the oracle inqquality related to the CE loss. The proofs of all theoretical results provided in Section D In Section E] establish the convergence rates with respect to the classification loss for the KLR-based algorithms across various scenarios. Finally, additional experimental details are presented in Section
A SOME NOTATIONS
For p oc, the ---norm of (Ii,...,,:d) ad) is defined as || (121 [ ... ( while the Loc -norm is defined ||=||e = max;=1.... [za].- For any E B and > O, explicitly denote (x) == r == {a' E Rd || æ12 S r} as the closed ball centered with radius r. In addition, denote ((A) as the Lebesgue measure of the set C Rd.
B DISCUSSION ON THE METHODS FOR LONG-TAILED LEARNING
In this section, we demonstrate that the classifier (x(x)) induced by our CCP-based estimator ( from Eq. (3) aligns with the logit adjustment classifier introduced in Menon et al. (202T). Specif- ically, Eq. (7) and Eq. (8) in Menon et al. (2021) show that the optimal classifier h under the distribution Q be expressed
(z) arg p(z/m)
arg maxp = arg p(m|x))(()) mE[M]
MEIM M
mE[ad] p(m)
p(m (x)
arg max mE[M] p(m)
arg max [logp(m/z) log lom)(m)).
mE(M)
Since the posterior probability p(m]z) can be estimated
exp(Sm(x))
p(m|z) Eyetan (x)(f
follows that log p(m) x (m). Using this insight, Menon et al. (2021) proposed the logit adjustment classifier defined
(x)(()) = arg max [log p[m|z) - log p(m)] = arg max [f log p(m)).
(29)
mE(M)
mE(M]
This formulation adjusts the logits (xr) by subtracting the logarithm of the estimated class prior p(m), effectively mitigating the influence of class imbalances on the classification decision.
Leveraging Eq. with w(y) (/()) our CCP-based classifier can be expressed as
(x) arg max (( arg p(mlx))f(()) me(M]
ΣjEM P(j(x)/PL)
mc[M]
p(m arg max (ogg((m) - lom)]
arg max
(30)
7(m)
mE[M]
mE(M]
Therefore, the classifier (T(x)) in Eq. 30 derived from the CCP-based estimator 7y(z) in Eq.
consistent with the logit adjustment classifier FLLA in Eq. 29 introduced Menon et al. 2021
C DISCUSSION ON THE ORACLE INEQUALITY
Zhang et al. (2024) also established a new oracle inequality applicable to the CE loss; however, their oracle inequality is limited to binary classification. In this section, we demonstrate that directly extending their proof technique to the multi-class scenario causes their variance bound Eq. (2.5) of Zhang al. (2024) to increase to polynomial order, opposed logarithmic order in the binary case, leading to suboptimal convergence rates. We will illustrate this with examples in the following.
14

---

Published as a conference paper at ICLR 2025
To be specific, in order cope with the unbounded CE loss, Zhang et al. (2024) construct a bounded function (zz r, y) such that the expectation of Φ is equal to the Bayes CE risk, i.e. Ex(X,Y) P [[ log p(Y|)))) When analyzing the excess risk R RICK, (p(yy())) P. they investigate the expectation of a bounded term, that is, ((LCE(D( (X) (X, Y)), instead of the expectation of the original unbounded excess loss, i.e., (E..TCC(P(P))))
[<c(x(Y(x))) Given a small 51 > O, for the binary classification with y = {1, 23. the specific form of bounded functioon (2x y) is chosen
log(p(y(<=),,
if pf [ 11,1-1 611.
if](1)=) (0, (f E
6(2, y) =
(31)
Σ m2
log]
61,1).
Note that in Eq. B1p. when p[1[x:) (1 - 51, 1). that is, the CCP is close to 0 0rr 1, o(x y)
is defined as the inner risk of the true CCP function, i.c. o(I v) = Eyxx==(o<()(((x))
which
bounded by the fixed quantity log òj. Then they prove that can satisfy the variance bound by a careful case-by-case analysis, especially for the special case that p( p[1[x) E (0, (0,62) ) U1 (1- 6,, 1).
They show that when setting p(y|z) E [80, 1 gol and choosing 61 = (o0000lgg1//6) with U
do E (0, 1/3), the variance bound
E(LCe(P(U\X)) - V)) & VE(LCE(((UlX)) - Y))
(32)
holds with V := 125000 log log 6n)2 2 for any distribution P. By choosing a polynomial order for 5o, i.c. 6a n- with 0 a/ + a)), then the variance bound holds with V x (logn)² logarithmic order. In addition, there holds T.C. (P (P) V (0x;, y) S - log ^ 81) x log n for any (ar, y), i.e., the upper bound of (CE(((y(ar)) and ((2, y) are both of logarithmic orders. These results lead to optimal convergence rates up to a logarithmic term for binary classification.
Following the idea of constructing bounded function (22, y) in Zhang al. 22024), for multi- class cases, we obtain the function ((x, y) of the form
log(p(vl=)),
if V p(m|x) E { - 81], mE|M
((I,
0,
if p(m|ar)= =1, ME
(33)
Σ mE[M]
if mE
p(m|z)) E (1,
In the following example with K 3. we show that to ensure that the variance bound Eq. (32 holds for any distribution P, the order of V must be at least a polynomial order in the sample size, which significantly negatively impacts the convergence rates.
Example C.1. Let y (1, For any E X. let nT(x) 0 and p(-[z) (n(x), 1/3. 2/3
). Suppose that for a given n, we have Px (x E X x n(()) S e-n) = 1. Moreover, let do (0, 0.3) and suppose p(-12)) (5o, 1/3, 2/3 60) holds for any T.
By Eq. (33 we have Lex (F(ylz)) < - log 5y and 0(x, y) S 1o In order to ensure that both upper bound of LCr(p(y)a)) and Φ(2, v) are of logarithmic orders in the sample size, the minimum
order of do and o, should only be negative polynomial orders. Therefore, for any I with vπ(x) S e-n
we have nlx) 81 for sufficiently large n. In Example C.1 we have p(1[z) = n²x). By Eq. 333,
we have Φ(x, v) = = Emep3)
--Empp p(m|z) log p(m),z) and thus the left hand side in Eq. 32 turns out to
be
B B(LCB(((Y1X) o(X,))) 2 Ex (xx
-60 o(X,)))²
2 Ex ((1/3) (n(X) log (X) + (2/3) log 1 (2/3 log(2/3 m(x))))? > 0.14
in 2 4. On the other hand, by using the definition of @ and Lemma 2.7 in Tsybakov (2008), the excess risk in the right hand side of Eq. (32) is
((LoR(((Y)x)) - +(X, Y)) B(LOE(F(Y1X)) Lcr(p(Y|X)))
(p(m) X)- pmmm X))²
(mx() - -0)2 + (n(() - -80)²)
< Ex
S Ex
S 60.
do
2/3 6o
m=l
15

---

Published as a conference paper at ICLR 2025
Therefore, ensure that the variance bound Eq. 332 holds, must have
0.14 IE ((LCF(P((1X)) 6(X, Y))
2
((LCR(p(Y (X) o(X Y))
60
In order to achieve small approximation error, Theorem 2.2 in Zhang et al. 2022) selects do x n- with the constant > a<(d + a),, which implies that 2 n a7(a0a This results significantly slower convergence rales.
Similar to Example C.I polynomial order in the sample size to satisfy the variance bound. Therefore, the direct extension of constructing function e to the multi-class case leads essentially slower convergence rates.
provide examples for any K 3 for which V must be of some
Furthermore, the oracle inequality presented in Bos & Schmidt-Hieber (2022) does not provide any theoretical guarantees concerning the unbounded CE loss. Their results regarding the truncated excess CE risk may not hold for the true excess CE risk. Specifically, in their Theorem 3.5, the sample error bound for the truncated excess CE risk shown increase linearly with the truncation threshold. Consequently, if the threshold is taken to infinity to convert the truncated excess CE risk the actual CE excess risk, the resulting sample error bound diverges to infinity.
It is important to note that our proof technique in Section 4.2. can be applied to other models that yield CCP predictions by minimizing the CE loss, such as neural networks. Furthermore, our approach can be generalized to other unbounded loss functions that increase more rapidly than the CE loss, including the exponential loss (Hastie et al. 2009), the large-margin unified machine (Liu ct al. 2011), and the distance- discrimination loss (Marron et al. 2007).
D PROOFS
In this section, we present the proofss related to Sections and 3 in Sections D.1 and D.2 respec- tively. To be specific, Section D.I.I and D.1.2 derive the upper bound of the sample error and the approximation error for KLR. The proots of the convergence rates of KLR and the lower bound of multi-class classification with respect to the CE loss presented in Section D.1.3] Moreover, we prove the convergence rates of approaches using KLR for complex scenarios of classification problems in Section D.2
D.1 PROOFS RELATED TO SECTION 4
D.1.1 PROOFS RELATED TO SECTION 4.2.1
Before we proceed, we need to introduce the following concept of entropy numbers (van der Vaart Wellner 1996) to measure the capacity of a function set.
Definition D.1 (Entropy Numbers), Let (X, d) be a metric space, A C X and 2 be an integer. The i-th entropy number of (A, d) is defined as
(AA, d) = inl & 0: 3e,... T2i-1 E X' such that c U B)
j=1
The following lemma gives the upper bound of the entropy number for Gaussian kernels.
Lemma D.2. Let C Rdd, p(x) be a distribution on X and let supp (Px) C. X be the support of Px. Moreover, for q 0, let H (A) be the RKHS of the Gaussian RBF kernel ko over the set A. Then, for all N E N², there exists a constant CN.d > such that
eş(id: (XX) + (xx)) < 2 CN. -N Ni-Nia
i>1.
Proof of Lemma
D.2
Let consider the commutative diagram
H(X)
La Px))
(x))
id
H H(supp(Px) (Px))
la (supp(Px))
id
16

---

Published as a conference paper at ICLR 2025
where the extension operator Zump((x) (2) (s(pp(((Px)) given by Corollary 4.43 in Steinwart & Christmann (2008) are isometric isomorphisms such that [[aupp(Px) Hx(2))
H,(supp(Px)]ll=
Let loo (B) be the space of all bounded functions B. Then for any f E (B)),, we have [[(s)) ( Σ [f(x)) < ll and thus [lid Loo (supp(X)) + L2(D)] < 1. This together with (A.38), (A.39), and Theorem 6.27 in Steinwart & Christmann (2008) implies that for all 2 and N 2 there holds
ei(id: (2) L2(p(x)))
ediid 1 suppp(px) (x) + (sppp(())) -eiid: (ssupp(Px)) + (suppp()) |lid: Lo0 (supp(2t) - L2(Px)l $ $2" N N
where CN,d is the constant in (Steinwart & Christmann 2008 Theorem 6.27).
Before proceed, need to introduce some notations. To this end, let (LCE (3, LC (z(()) and he; == LCF o pf LCF o p. Similarly, for the upper part LIE Eq. (20) and the lower part Lie Eq. 21 of the CE loss, we define (Ler, (x, LUR(U, (I) and (T'ce o (f)),, v) = T'cE (V)
Let the function space be as Eq. (6) and r* = jnf 115m 11 + Erhgg)) For any r 2 r", we define the function space
M Σ
Fr = FEFF
1l 1 + Bphpp sr}
m=1
and denote the upper part of the loss difference of the functions in F, as
G. = {Le pp' LEE op: FiJ.
(34)
Let rf == inf ye (A Em=1 Il 11 + Epp(Lo o pÿ)) For any r 2 r" we define the function space
concerning the lower part by
F
SEF:A
Σ m=l
Im + Er o p/)) sr}
and denote the lower part of the loss of the functions in Ft. as
g: [ICE o v E F.).
(35)
Lemma D.3. Let 9 and g be defined as in Eq. 34 and Eq. 355. respectively. Then we have
S 20g. M 1+1111100 (11((2))) 222 -
(i L2(D)) a ++1((2))) (r/A) 1/2 //(2)); 1/(EE))
where Cg,d is constant depending only on & and d.
Proof of Lemma D.3 Since for any f E Fr, we have Al S r. mmm [M - 1]. Therefore,
F. fm E (r/x) BH, m [M 1]}.
where By == (h E H: || S $1} is the unit ball in the space H. By applying Lemma D.2 with Ç : d/(2N), we obtain e; (id Hx)) > Lz(D)) I aai-1 a1(1)( where == -d/27 d/((2) with the constant cg, depending only on & and Thus we have
/2((/\))//2, Bu. (2)) S (2
17

---

Published as a conference paper at ICLR 2025
By Definition D.1 and Lemma D.2 there exists an c (/ 11(22) .net N of (r/2)1/2B) Bи
with respect to L2 D) with [ i-1 Define the function set
B = {g = (gm)) m= 9M gm N. [M - 1]}.
Then we have [B] 2 1), Moreover, for any function f Fr, there exists g E such that Il Im La(D) S for m E [M 11. Let us define
Pf(v(z) = exp(fu(x))
Σm m== exp(fm(x))
and truncate (f(()z) to obtain p) (y/2z) as in Eq. 8
By Lemma D.9 get
| p LCE o op- (LÜE pp' LIE op)
L pý LoE PillLaco)
s || -logp + logp's L2(D) S (4M + 1) logps + logg L(x(D)
< (X) gr (X((X) + 1og ΣM Σ exp (X)) L2(D)
m== exp(fm (X))
(36)
For any 0 and E R. the derivative function of the function h(z) == log(a exp(2)) is h'(z) = +xx(//())))xx())))))))) E (0, Therefore, by the Lagrange mean value theorem, we have = | (1))))))))- 2 fe) and 2' = (X) for l E [K], we get
S 22- Applying this to := D explgin (X))+ +
Em=41
Σ m=1 exp exp(ffm(X))) (X))
M
Ens exp(em (X)) + e exp(fm
log
= Σ
log
Σ m== exp(9m (X))
E exp(gm (X)) + Em=ct1 exp(fm(X))
Enn explym (X)) + Em exp( (m)))
Σ
log
> (f((X) (((x))-ee())) (X)).
Em=l exp(em (X)) + EM m=++1 (op(sm(X))
t=1
8=1
This together with Eq. 36 yields
LLe o p/}- LëE op (LÖE o pp' LöE o p))(2((D)
$ (X) - gr (X)]ll)))))) + Σ [l(((X) ge(X)llea(D) S Mc.
Therefore, get | p/ L'g op- (Loe p L'e pp)ll S Mc. Thus, the function set (L'B o 'p' LöE o op: f E B} is (Me)-net of g.¹. similar analysis yields that the function set (Le p/y f E B} is net) of G. These together with (A.36) in Steinwart & Christmann (2008) yield
(z2 s 2M (2
QM (2)) & 2M = 22
which are equivalent
< 2M 2M (r/ (r tे2 = cc.d2.M (r/ (r/2)bg #
cg(g), (2)) < 2M 2M (r\A)) tे- =c (r/2)3g : #े.
This finishes the proof.
Lemma D.4. Let P be probability distribution on X x D. Let t E (0, 1/(2M)) and ply be the truncation of yy as in Eq. 8 Then any V 2 -2 t + 2, there holds
Ep (ooC.LEY (Y,p)(-x)) Tce(Y.p((X))) < V (E((Fc((YDD(((1))) ICcE(.p(.
18

---

Published as a conference paper at ICLR 2025
Proof of Lemma D.4 By definition of the CE loss, have
p(m| xx) 2
Ep Bp((CEE(Y -LCE(V,L(EX()))) E Rxp
Σ (m/(2)
log
pjj (mlz))
M==1
M
p(m[2))
(o.[Tc((V.P)(1111 - LCE(Y, (oee(Y,((-x))) = Rxp
log
pj (mlzx)
m=1
For A E R, we define the function h by
log p(m|(x) 2
ply( (m//x) )
k(p)(+x)) Σ p(ml2)
M
llog p(m) (r)
M
p(m(z)
Σ
2s (m/2)) -1
pj (m|z))
m=1
m=1
Then we have
0h(p (h(p)(112))
2. p(mlar)
log p(m| + +V. p(m(z)
(m((x)
+
(p)(ml/x)
(m|(a)
(ml
p(ml()
(-2 log p(ml2x) (m/())))
+ +V) + 0.
(m|p))
Let g(x) = z(-2 log V) + 0 for E 1/t] and V 2 -2 logt + 2. Since the derivative of g is gx) = 2(log x + + V 2 0, the function g(x) is non-decreasing with respect to r. Therefore, the zero point of (-(p)((1z))/00 (m|x: is the same for all m [M]. In other words, p(ml=)/p/ (m|x) should be the same and thus we have ply (m|2z p(m|z) due the constraint EM p/ 1. Therefore, (/(())))) p(m[x) attains the maximum of
Σ p(mlar) log p(mlla) V pf (mlp))
Σ p(m]))) log p(mlzz) pf, (mlz))
which turns out to be zero. Consequently, for any ply (m|2z) satisfying EM ply (m/x) 1, there holds
M
log p(m|z) pt (m/z)) - V
M
[lg p(m|xx)
)):
Σ pmm(z)
Σ [m])))
pf (m/z)) )m{p))
m=
which finishes the proof.
The following lemma provides the variance bound for the lower part of the CE loss function and the upper bound for the lower part of the CE risk of the truncated estimator.
Lemma D.5. Let L'eg be the lower part of the CE loss function in Eq. (2 with t (0.1)(2M)).
Then for any f X + M and any t E (0, 1/(2M)), we have
6 o/) < (- logt) Ep (L př)),
Ep(L'g pf)) S -Mtlogt.
Proof of Lemma
D.5 By the definition of L' ply, we have
M
Ep (L p2)²² = Erup
p(m [ p(m)))1(p(mm) < t)( (m(lo)
m=l
Ep(L'gr )pt) = Egao
p(ml=)1(p((mp) < < log 19(-logp'' (mlzz)
19

---

Published as a conference paper at ICLR 2025
Since pf (m|2) E [t. 1) for any
[M], we have - loggp/ (0, 100--l0 log Thus obtain
M
(p o p4)2 Exza
p(m (pp((()) -- (-1ogp}(mm(x))
M
(-logg () Rzap
Σ p(m (p(mlx) < ( ([] = (-log (log))Er((e (- o
m=1
which proves the first assertion. Moreover, we have
M
Ep(LIE o ppj) = Boup
Σ
(p(m)x) < (o
m=1
M
( logl) S - -M.
which proves the second assertion.
Before we proceed, we need to introduce another concept to measure the capacity of function set, which is a type of expectation supermum with respect to the Rademacher sequence, see e.g., Definition 7.9 in Steinwart & Christmann (2008).
Definition D.6 (Empirical Rademacher Average). Let { be a Rademacher sequence with re- spect to some distribution v, that is, sequence of i.i.d. random variables, such that V(E, 1) v(E; = -) = 1/2. The n-th empirical Rademacher average of F is defined as
Rad MadD(F,m) (F, == E, sup WEF
e,h(z;))
Proof of Theorem By the definition of Lëe in Eq. 20 and L'e in Eq. 21 we have LCE
LI + L'cE- Let us denote hpz == LCe o p'y LCE p. hy Le pjj Lie o p and
o0y == L'OB o p/y. By Eq. 10 we have p(ylx)) = phr (v|z). Then by Eq. 9 for any fo E F. we
have A|)5 + RL P (ul=)) I Allool + RRCE. D (v/=)) and consequently
1|1/m11 + P RiCE.P- Al|/D|13 + Ephi = AllS 1 + Ephrto
11 EDhn EDh,3 + +Bphyj0
I All.foll,, + EDh EDhy + Ephyip
Allfol1i, + Ephpp + EDhppo Ephpt + +Ephyso - EDhyto
Al1.61113 + Ephy
(EDNi
Ephii +Ephi EDHh
+ (BDh% -Ephi +Ephy
Ephy
= =1lloll2z + Epply + (EDL'CE o v/ - EpLiE o ph, + EpliOR o vho EDL r/1))
+ (BDHi - -Erh"
+Erhy -Eph"
=Allfolla + -Erhy + +ED - Erryy )+ ED ED (Brss - -1/%))
+ED(h" - Ephh" pjo
En (Eph", -Ng )
(37)
where Enhig n Et Mpg (Xi. V.). In the following, we provide the estimates for the last
four terms in Eq. 37
For any f E F. we observe that |10b;3 - Epg'y 1mo = -IIi'E o EpLLE o p8y1 S - -log L. By
Lemma D.5 we have
Ep(g'j - EpSTY )2 Er(spy)) (-log 1): EpSly
(38)
20

---

Published as a conference paper at ICLR 2025
Applying Bernstein's inequality in (Steinwart & Christmann, 2008 Ergy3 : E [n2]}, we obtain that
Theorem 6. t2 (0// (X, Y,)
ED(dgr - -Epopg ) 5 / log-log logt) E) /nn + 4(- log t)5/(n))
(5((-lgg//2// /2)/2 Eropy + (-4çlog') t)m(3)) & Ergpi - 2çlogt/ (39)
holds with probability pa at least 1 - E, where the last inequality is due to 2ab s a² + 6². To estimate the term EDg -Brg let define the function
Erg;; -
Gzr= = >I1fIl + Brgy +r
FEF,r
where r7 = inf{f E F: Allfll + Errgy /.
Then we have ||, S (-logt)/r. By Eq. 38
we have
Br(o,; Br Br(g);)
EpGr S (Brgg +r) S 2rEpg' S loog
2r
Let G - f F.) and F E F: Alf + +Ero/j r]. Symmetrization in Proposition 7.10 of Steinwart & Christmann 2008) yields
ED sup (ED(Egg) o/3 s 2 SEF
n) S 2x)n((r).
For any L'E o Gh we have |E op 1l -- logt and EL p S logt Ep(LEE ptt) - -rlogt L. By applying Theorem 7.16 in Steinwart & Christmann 2008) and Lemma D.3 obtain
SC( 1 (-log ' V tf (ogg rtz) (r),,,,, (40)
where C = CE M
25/
Thus we have
Edd
ED sup
E DD (Eps - 5 =1 (r).
lEFt
is easy verify that ui., (r) 2 (r). Then by applying the peeling technique in Theorem 7.7 of Steinwart & Christmann (0008) on F., we obtain
Ep sup [DD < (r)r()/rr feF
Applying Talagrand's d's inequality in Theorem 7.5 of Steinwart & Christmann 2008 to y= 1/4, we obtain that for any rī. with probability at least e there holds
sup En < 10ph.())r y- log log((((nr) (-14g log (3nr)
feF
By the definition of Ifo.r, we have
Ersyy -Epg'
< (Allfnll + Ergg (100p, V-Clogt/mr) + (-14 log (oggt))(rr)))
+ (r) / (rlgtt/nn (-14(logt)/(3n)
(41)
with probability at least - c- Subsequently, estimate the term Epha Ephh in Eq. 37 For any f E we observe that |//2; Eh
p)
1l -2 t. Using the variance bound Lemma pt
D.4 and t < 1/(2M) & 1/e, get
Ep (1" - 'Enh, ) 2 Ep(hit) Ep(h,;) 5 (-2 + 2) Ep(hng)) S -4log (E (())))))
21

---

Published as a conference paper at ICLR 2025
Then by applying Bernstein's inequality in (Steinwart & Christmann 2008
Theorem 6.12) to
{h" (X,, Y.) -Eph" :iE [n]} and 2ab I a + b", we obtain Pjo
Ephiy ) /2 log 1)) /n + 40-21og 1ogg))lg((/33 (3n) ED
sç- t/n Ephpl (-8Ç (ooggtt33311 (3n) Ephyt 14Ş log (/()).
(42)
To estimate the term Ephh" Pip
EDhy v/ in Eq. (37). we define the function
Eph"; v; Pj H = A|lfl + Ephy +r
- h
fEF,
Then have || | 3-2 t/r and the variance bound in Lemma D.4 yields
Ep(hi p3 )²
(p )2
( logt + 1) - -2log
EpHi. J.r <
(Bplip; + +r) r) $ 2rBrh
r
Let 9. = (h2 pj
f E Fr) and F, == (s FF :::::EEMEN mE(M 1l 11: + EEphi S Sr}. Symmetriza- tion Proposition 7.10 of Steinwart Christmann (2008) yields
Epapa sup feF-
[ED (ED 22 ) PB Rad S (rh,
where the second incquality can be proved in similar way as in proving Eq. (40). Peeling in Theorem 7.7 of /Steinwart & Christmann (2008) together with J, hence gives
En sup SEF
[n S (r)(r)/r.
Applying Talagrand's inequality in the form of Theorem 7.5 of Steinwart & Christmann (2008) applied to y 1/4, therefore obtain for any r > r",
sup E < 10 /2( (ogg2lgg)(//// (nr) - 14Ç logt (3nr) SEF
holds with probability at least e Using the definition of Hn.r, we obtain
Ephi; Ephi %/0
< (Allsollz EEpty; 22-22g (nC((nr) 14Ç log 1/ (3nr)
100%,(() + 2 log 1/clg////////////////////
(43)
with probability at least - -5, Combining Eq. 37 Eq. (39 Eq. obtain
Eq. 422 and Eq. 443 we
Allfll + Ephpps I Al1foll? + 2Ephi + Ergg - 8Clogt//
(2Al) + Epgyy Ephhp (10 (r)/r //<(logt/(mm) 14Ç log logt/(3nr))
20 (r) +
+3 3/ -TÇ log t/n- 28C log (/ggt(3n)
with probability at least 4e 5c
Now, it suffices to bound the various terms. If we take r 2 9 (-looo 2)2 then by elementary calculation, we get V-rçlog Loogl// i/n S r/48, -28 log 1/(nr) S 1/60, and 8 log l/n S r/288. By Lemma D.5 we have Epg' < logt Therefore, for any r > 9000 x -d ( log -n
get (r) I r/30. Moreover, let r -2304 log t/n and thus
2304ç boott/n/n r" r/, we get
Allfpll + Ephp: < foll + Ephi; )- Mt + r/288
+ fDli + Epha MMlog t) (1/3 + 1/24 + 1/120) + 2r/3 + r/16 r/60
22

---

Published as a conference paper at ICLR 2025
I 2(lllfolli Br ) (23/30) + Ephnt (83/60))Mttlg + (9/10)r
with probability least 1 - 4 By the definition of ri and r*, and Lemma D.5 have rÝ S folfoll Ergy rr² - Mt. .ftlog and r" All + + By some elementary caleulations and taking r == 10000000--00 ( log t) 1 2304C logt/n + r" + rī, we get
AllfDll + Ephhp
x 10(2lI + Erhpip 7Mt + 5r
log - 10(2)l + +Ephpto ) logt + 450000 (-logt) =
- -11520Ç logt/ t/ntt/n-nn +5 + 5r
- 20(A|Ifoll2: + Epphp + Co log (t+ A ( + C/n)
with probability at least 1 - S, where Co = (5 + 12M) V 4500C V 11520. This proves the assertion.
D.1.2 PROOFS RELATED TO SECTION 4.2.2
The goal of this section is derive an upper bound for the approximation error of KLR, i.c. an upper bound for
inf Allf FEF
R..... (pfc.))))())z))) R Ri..E.P.
To construct function that approximates the bounded function f in Eq. (26). for a fixed band- width 7 > entering the Gaussian kernel, we define the function Rd R by
K(x) (2/(>²x)) d/2 exp(-21<x1
(44)
Then we define the convolution of J and K as
(x) == (K (0Kx***000 (z)) / Jzd
K(x - =)Sm( (2)m((2) (z) dz,
m [M],
(45)
and the score function f = (fh)meMM)
Let us denote
Ime (a:) == log lmgr)(ml))) Then for (x) in Eq. 26 can be expressed as
(46)
I (x) = Ihm (x) the (z)).
(47)
To analyze the approximation error of J", we first need the following lemma. Lemma D.7. Let Assumption 3.1 hold. Moreover, let Ii be defined as in Eq.
46
Then for any
I, X, we have
log(1 + callx- x' 21112) p" (mlx) p" (mla')
(x) I (2')
To prove Lemma D.7 we need the following Lemmas D.8 and D.9
Lemma D.8. For any c > 1 and z > 0, we have log( (1 - cz) S clog + +)).
Proof of Lemma D.8 For any
1 and z O. define 1(2)) log(1 ez) c clog(1 z). Then
we have
c dl- c)
n'(x)) 1 + cz
1+z (1 + cz) (1+ < 0
and thus h is decreasing on [0, oo). Therefore, for any > 0, there holds h(z) < h(0) = 0. Then the definition of h yields the conclusion.
23

---

Published as a conference paper at ICLR 2025
Lemma D.9. Let Assumption 3.1 hold. Moreover, let p" (mlz) be defined as in Eq. 8
with pf
replaced by p. Then for any x, x' E X, there holds
1p" (ml2z) p" (mla' s (4M + 1)pp(ml)) - p(m]2z)) I cz x' 212
where ey = (4M + 1)
Proof of Lemma D.9 Given t E (0. (2M)). we define the label set M == {m E [M] : pf(m)x) < r} C [M) By Eq. (8) and Assumption 3.1 (i), for any m E M there holds
So.
if E Ma
lp" (m|a)) - p0=((=(m) (m|²²)] = p((mlx") - + < p(m[x') - pmm/ar) S call 12, i & M D.
For any & M and m Ma , by using Assumption 3.1 (i), we get
(m(m))) - p" (mlz²)) p" (m/x))
p(m|z) p(m]/=') S c, 2'18
Otherwise, for any m & M and m & My since T E (0,)/ then for any x E X, we have
Σ (v(()))-))
Σ ((-i(=)) = -) Mr 1/2. (48)
=1
REME..
JEM
Therefore, by the triangle inequality and Assumption 3.1 (i), there holds
pp (m|x) - p" (mlzz)) = (pp" (mlz) - 7) (0 (m/+=))- --)
- -))11 (p(ml)))+))(1
Exemp, (p(e)x) (0(11))-)) 77)
Ejemp,. (T (T-(()(z))
- (p(ml)²) (0(ml)))-))1 ExeMr Diz!
EjEM, (T 15-ppop -(ppp())))
Dist
(p(E)x²)
(p(mll)) - -T) EeAME, (p(1(x) - (p((m/a)) -7) Eefsr (p(e)z²) -T)
1-Mr
1--M
(p(mlz)) -7) -
EnemE, (p(e(x) -T) (p(mlz') -7) Σ Σiem; (p({(x) -T)
1 1 1T
1 Mr
+ (p(ml)x)-1) -T) ELRME (p(((x)-7)
1 1 MT
(p(mlx')-) - -r) EiEm D.z! (p(1)x²) - 7)
1 1 1-
/ Eeeme ,eeng,, (p(1)x') -7) - -EEEy (p(Afz) - -T)
< <|p(mlx) p(ml/=)) + (p(mla')-7) (ENRME, (p(1)z) -T) -Eeens (p(1)x") - -))
Eiem (b(9)x') (1)) - -Eeens_(pllte -7)
S <alllo 2'112 + (Eeemy.. (p(4)x)= -T). (Eeem, (p(()x²) - -]
(49)
By the triangle inequality, we have
Σ (p(e)x') 7) -) Σ (p(e)x) -7)
ERMS
Σ |p((|a') - p({[x)) +
Σ
p((elo)) - 7|+
Σ
[p({|x)
7/.
LEMM Pirt
REME...EMM Diat
(50)
For E M and & Mp... by Assumption 3.1 (i), we have
(p(E(z') - 7| = p((l=') S p()x)) - p(((x') S Ca. 1 - x'112-
Similarly, for& l MT and l & MTT.'. by Assumption 3.1 (i), we have
(p(())) 7| = = -p((()) & p(E(=') - p(((x) S ca -a x'112.
24

---

Published as a conference paper at ICLR 2025
Therefore, combining Eq. (50) and Assumption 3.1 (i), obtain
Σ (p(((x')-7) -)
(p({)z) - 7) S co
Σ
1 - x'12 12 S caMllz - x' 2'
MEME Ric!
og (M pi m.M..
This together with Eq. 488 and Eq. (49
yields
Ip" (m|z) p" (m|x') - co x'12 CaMi2 - -2'112 2'112
(1/2) (1/2)
(4M + 1)call x' 2 =: cz 1| 112
(51)
where ez = (4M + c) Therefore, we finish the proof of the second inequality.
Now, if we assume that [p(m[z) p(m])x') = e2|læ x' 1| holds for any E [M], then similar to the analysis of Eq. (1). we can prove that
10 (mla) p" (m|p') S (4M + 1)calla - 112 = (4M + 1)]p((m)))p(mmpa p(m(a'))
which yields the first inequality. Thus, finish the proof.
Proof of Lemma
D.7
Lemma
D.9 yields that for any x, x' E X, there holds
Ip" (m|x) p" (mmla') ez | x' 112
(52)
Moreover, Lemma D.8 together with Eq. (52 implies that if p" (m|z² 2 px pm(l=')), then
p² (m)xx p" (mla') p" (m|z')
(om(()) - 2 (x') logp" (m|z) log (m) log
log + +p += - p (mlx')) log (1 + ctllx - x' l12)
p (m/lx²)
p p=(m|z')
Otherwise (m]aa) < p" mm)x), then by using Lemma D.8 and Eq. 52 again, we get (o) - In (x')
log p" (mlz²) log (mlz) log 1 p" (m x²) p" (m/x)
p" p=(m (r)
log + p" (ml)') p" (mlz)) log(1 + cz 1|: x' (18)) p" (m/2z)
pd (mlax)
Therefore, we have
log(1 + call= 2'11 p p=(m/z) A (m(lx²)
I (x) (x') S
which yields the assertion.
With the aid of Lemma D.7 we are able to present the pointwise bound for the distance between IT (2:) and f (z), which is crucial to establish the approximation error bound of pj- (m/z).
Proposition D.10. Let Assumption 3.1 hold. Furthermore, let H be the Gaussian RKHS with the bandwidth parameter 7 (0, 20,2-* 2-/a/ Moreover, let E (0, 1/(M)) and let p" (mlz),, fni and J be defined as in Eq. 88 Eq. 26). and Eq. 45), respectively. Then, for any m [M], there holds fin H and
[F((2) - fx)(() < ci(p (mlz))) + (M)
m E m
(53)
where is constant which will be specified in the proof.
Proposition D.10 demonstrates that the approximation error to the target function depends on p" [m] and p" [z)=)), highlighting that smaller CCP values are more challenging to approx- imate. Notably, the upper bound in Eq. (53) adaptively varies for different r and is tighter than the universal bound that replaces both p" (m
and p (M -1 in Eq. (53) by their upper bound -- especially when p(m[x) is not close to zero. This is crucial for us to obtain the minimal approximation error bound later by choosing proper value for
25

---

Published as a conference paper at ICLR 2025
Proof of Proposition D.10 Let the function K I E X and m E [M], there holds
R - IR be defined as in Eq. (44 Then for any
2
d/2
2||x - 2113
* Fm (x)
exp
Iin (2)
JRd
72
2
d/2
2 7/2
exp
Fm (x + h:) dh.
Since the functions I.. m E [M). have a compact support and are bounded, we have Im E (RR)). This together with Proposition 4.46 in Steinwart & Christmann (2008) yields
K I' H.
(54)
Moreover, we have
2
d/2
2 2/
Im (1)
exp
Im (1) dh.
JR
7
72
Then for any E X, there holds
/
2
d/2
21111/
K * (n) 9m(xx)
=
exp
(gm + +h) - Im dh
Rd
72
d/2
21111/2 72
< R
2
exp
| (xr + +1) - Im (x)) dh.
For m E [M). let Am. = (h E Rdd Im (xr + h) 2 Hm (x))
Then by using Lemma D.7 and the
fact that log(1 ( + x) S x, x 0, we get
2
d/2
2111112
K * 9 (x))) Im (x)
(9 h) (x)) dh 72
exp
Ami
4/2
21111
exp
72
(ITh (x) - ITm (or + 11)) dh
Amii
2
d/2
2 72
log (1 + c1111112) dh
exp
2.
pd (ml)ar
d/2
21111/2 72
log (1 + Cr. (11111))))
exp
pd ("(m/x: + h) dh
12
2
d/2
2/ 72
Cr. 1
exp
dh
Rdd
PT
p" (m
2
d/2
| exp
CL h
dh =: (T) + (TT). (55)
2
p (m x h)
Rd
For the first term (T) in Eq. c) = cF(c), c > 0, we get
(5). using the rotation invariance of x exp( - 2 1 and T(1 +
4/2
(T) = CL p (m|z)
7
cxp(- (PP1-11[1) dh
22
Rd
T
CL
7
2
000
e p dr
p. (mlz)
V2)
l(d/2)
CL
l'(d/2) -
d+a a
2 200/270.
(56)
Dd (mlz)
2
Using Eq. 52 and p" (m|x + h) 2 т, for any E X and h E IRd, we get
p" (m|x h) s ppppmmm (m| + 1r" (m/r + h- p" (m
26

---

Published as a conference paper at ICLR 2025
p (mla r + h) - p (m/x))
cr. 1
S (m'(m/))+
S p" (m|x))
(57)
p² (m| h)p" (m|xr)
Tp' (m|
For the second term (IT) in Eq.
55 using Eq. (56) and Eq.
57
we obtain
C2
1111
2
d/2
2111112 72
(11) s c
p² (m|[z)-
exp
||//12 dh
_a
TP" (mlxr)
7
/ Ra D" (m/z))
CL
2
4/2
exp
22116112
||A|12
dh
(22
7/2
2
d/2
(-
(_21
+
cxp
|1/113 20 dh
JRd TP- Tp" (m/z)
72
CL
-((d2))-
d
2 2-0/27a
p" (m|xx
2a
d/2 exp( 3xp(-11413)11113 20 dh.
Tp" (m|rr
/2
3d
The rotation invariance of x + exp( - ||
together with I' + c) cl'c). 0, yields
J π 4/2 exp( dh
T(d/2) exp( 2 ( dr
-((d/2) | expl exp(-r)ratd/221 dr
I(a + d/2) r(d/2)
and consequently we have
(II) S p" (m|a:
CL I(d/2)- 'T
d 0
2 2-0/2
of
( 7
2x
T(a + d/2) T(d/2)
(58)
Tp" (m/x)
v2)
Combining Eq. (6). Eq. (58) and Eq. (55). we obtain
K 9 (x) Im (z)
CL r(d/2)- 11 + a
2 22-0 + 7p T(d/2)
ot T(a+d/2) ( 7
2a
S (mlz)
2
V2
(p (17 V - 1,,2)
(59)
where 6 = 22, (d) + a)/2) + T(a + (d/) By the definition of im we
have
T= K + gm K * ghs = JMM
(60)
Then by Eq. 54 and the linearity of the RKHS, we have Jrm E H. Using the triangle inequality Eq. (59 we obtain that for any æ X, there holds
PT - f. (x)) = |K * Im - K * +TT) - (Im g5r)
< K 9mm (I) (x) + |K (x) 92
< (p" (m|x)- + (M) V 21222
which finishes the proof.
Based on the upper bound of the pointwise distance between F (z) and foh (z)) we are able to derive the approximation error bound for the CCP estimator py- (-Ix)) in Proposition D.I1
Proposition D.11. Let Assumption 3.1 hold. Let E (0,2-1/a) be the bandwidth of the Gaussian kernel, f ) mE[M] with r E [0., 1/2MM] be as in Eq. 445 and C1 > 1 the constant as in Proposition D.10 Then, its induced estimator Pj+ (m)r) in Eq. 77) satisfies
(i) (m/o) 2 T/M;
27

---

Published as a conference paper at ICLR 2025
(i) |p(m|x)- Pj- (m|z)] 4M exp (6cr V (7 /T)))) minimum at r 70th and the resulting order is of 7f"
T. This upper bound achieves its
Proof of Proposition D.17 Using the definition of py- (mlz) and Eq.
47 we get
exp(Fm)
exp( fm)
exp K Iin)
Pj.(mlz) : ΣØ= exp(fm)
اj=1 exp(K * fMt)
Σك exp(K (K Fir.)
Using Eq. (46) and p" (mlx) E [T, (1 (M- 1))),, we get 9 [log r, log(1 (M 1)T) and
thus K * Im E (log T, log(1 - (M - 1)r]]. Consequently we have
5
Pj- (m|z) 2
2 M
E (M 1)7)
which proves the first assertion (i).
Using the definitions of py- (m/z:) and for in Eq. 26), get exp(Fm)
exp(fmt)
p¹ (m)).) Pj- (m/-)
E/ exp(.fr)
Σ/ exp(ff)
exp(smn - (xp(f}) - exp(Fm)
MM exp(J²")
exp(fī") E/nn, exp(f7)
exp(f(t)
5== exp(f7) - (fp ) + (exp(f+t) - exp(Fi)) Σx= exp(ff7)
Σ/= exp(fīt) Σドz exp(f3)
M
(MI-)
Σ
e - -55" (ml+) + = - -
1=1
pj. (M
Σ
(Tf (ct) of5¹) ) (ml.) + (eti - cta )1 (1-)
p² (m(l)))
jpm
(MI-)
Σ
11- -1 -1)el5 -1)ef5p((m)) + (1 - ef (1 pppppp ppmmmmmm))))) (ml.))
(m(m)))
8mm
= PF. (MI-))
JJ -15" - 1)e toi p" (((:))) + (1 - ef
)efiie (1- p (ml-))
jmm
Pp- (MI-))
Σ (exp(ff - )) exp(im fmm) exp((xt) (p (51-)
jp
(MI+)
Σ (exp( - 1, - ((1+))))) (il-)
(M[))
jmm
Pf. (MI-)
Σ (exp(F} - 15 (ir ) 1) explFr - ho' (ml-)p" (mll))p((())) (Gl))
(MI-)
j.m
By the triangle inequality, we have
lp (ml-- - P7. (m|-)
< P7. (M-+)
Σ
Fe -857 - -Frr - -f()) - (mp (1+) exp(Fi - -f (61)
p (M
fmm
Using Eq.
447 and Fim = K for, we get
- - frrm f = K * 93 93 - (K gm 9mm)
(62)
28

---

Published as a conference paper at ICLR 2025
Then by using the triangle inequality and Eq. (59) for any E [M], obtain
183 -デ - (fm - m - K * 9] 931 + K * 9 Iiml
S (p (i)-)) + p" (ml) (7 V r 222
(63)
s (T 7 V ,22 2c,,7
(64)
where we denote Cr,y = ez CI(T= V 2 2, For any function h and h2 satisfying 1hj h2 1
20r,y if h > h2, then by using the Lagrange mean value theorem, there exists E (0, h1 h2) such that
Texp(h1 - h22 exp=x h22 1 h22
I exp(11 h22) (h1 h2) S 220r (h1 h2).
(65)
Otherwise if hn < h2, then by using the Lagrange mean value theorem once again, there exists p E (hi h2, 0) such that
cxp(h2 h2) 1| = - exp(h1 - h22 = ch - h1) S h2 - h1.
(66)
Combining Eq. 65 and Eq. (66), we find
lexp(hi - -h2) 11 20r 1/1 h2)-
(67)
Applying Eq. 67 with h1 == fj 49 and lo2 = fm fut we obtain
exx(ff] ( -f 1 e 18 fj (fr fm
2er C (b0()l-)-1 + p" (ml ) )-)))
(68)
where the last inequality is due to Eq. 663 Similar to the analysis in Eq. 662 and Eq. 66 we have
1 fMll = |K Ii K gNs (Iin gM )l S IK * g. Iml + K * gis gād S 20
Applying Eq.
(67) once again with h1 == fm and h2 == fm we obtain
exp(Fm. fm 1 S 201(1 tyave 2 f S 20 e
which implies
exp( m
pm) S
1 + 20 20 2000
(69)
Combining Eq. 61 Eq. 68
and Eq. 669
we obtain
Ip" (m|z) Pj- (m|x)
pj. (M (z)
$ (1 20,,y 22cmm))
p- (mlz)-1) (Cry) 20 (p=()) ((c)))2nnn(01)))))
pr (M xx)
jpm
= + +2
) T
(p (f(oa)
Jmm
S <M(1 + 20 20 e
20107 T.
By the definition of p" (m|xr) in Eq. inequality, we then get
8
we have lp- (m|o) p(m]a)) < Mr. Using the triangle
1pj. (m|z) - p(m(x)) [m) $ (m|zz) - d" (m|x)] + 1p (m|z) p(m[x))
(11 20T,ye 20 JC,, 20 Mr
M (1 + (1 20,,, 20, )e,, 22..)
S 4M (1 2 4e,m ) S 4M )² exp (4(1 V Cxa))T
S 4M exp (6(1 V Cr,y) T - 4M exp (6e1 (1 v (7 /T)
where the second last inequality follows from 22x 2 2² 1. This finishes the proof.
29

---

Published as a conference paper at ICLR 2025
need the following proposition that gives an upper bound of the excess CE risk for any estimator py (-(z).
Before present the proof of Proposition 4.2
Proposition D.12. Let P be the probability distribution on X x V. Moreover, let f := memm with fm X + R the score function and its corresponding conditional probability estimator be py (m(m).) ) as in Eq. 77. Then we have
(p(mlX) pp(m||X)2
RICE ((ps(-)))() RLCE,P S Ex-p
Pf(m| X)
Proof of Proposition D.12 By the definition of LeE and py (m(m))) we have
R p(pg( = /x
M
Σ
p(m]ar)) logrs(m/z) (m) (x)
m=1
Then we have Ri.EP = Sx Em p(m)a ()) log ((mp)) dPx Consequently, we obtain
pmm log p(m[X)
RLcE,P(P)((1)) RLCR. Exap
Py X)
Using Lemma 2.7 in Tsybakov 2008), get
X(m[X) Py (m)
(p(m|X) p
Ex-p X(m|X) log
E Ex-p
ps(m|[)
which finishes the proof.
Proposition D.13. Let the probability distribution P satisfy Assumption s E (0, 1] and any 2 O. we have
3.1 (ii). Then for any
f (ptml1124)) p(m(ar) dPx(x) S
[ca(1 -)-180 for 0 < B < 1; (ca (1 + log 1l for 1.
Proof of Proposition D.13 Since p(m|z) is probability, have p(m x)) 1 and consequently C 2 For any nonnegative function h and random variable Z ~ Pz, there holds [Z) dP((Z) =
E[M(2)= So Pz(hz 2 u) du. Hence we have
S p(m(x) dPx(x) = Lo Px
1
1p(ml/) 2 s}
du
p(m|2)
1/8
(x(m(m)z) S 1/u) du,
where the last inequality follows from the fact that 1(p(m x) > 8) s)/p(mlz) p(m[x)= & 1/u and u I 1/s. By Assumption 3.1 (ii) with < B 1, we have
2 implies <
L. 1/8
Px (p(m)x) 1/u) du S cæ (" a du Cas
/1/
(70)
1 1- 3
Since Px (p(mlx) < t) < L. we have for all t e [0,
(x(v(m)x) _ 1/u) du S [
1/s
1 du 1/8 S cas
Therefore, Eq. (70) also holds if 8 = and thus we obtain the first assertion.
For B > 1, we have (x(((x)k) < 1) S call S sel,, 1 [0, 1]. If C S -11, then we have
[ 1/s
(x(m(m)x) < 1/u) du /0 peu Px(p(m)x) S 11/)) du + ('1e 1// Px(p(m)a) S 1/u) du
$
02 1 du + / 1/8
$
ca/udu cg + callogs - log S ce + logss
which finishes the proof.
30

---

Published as a conference paper at ICLR 2025
Now, with all the above preparations, are able to establish the excess CE risk of the approximator Pj. (v]z).
Proof of Proposition 4.2 Let ej be the constant as in Propositions D.10 By Proposition D.11
we
have
[p(mlx)= - Pz. (m|/)) - |p(m|z) - p7. (m|22) + 17z. (m]x) pz.. (m|z))
s 4M exp (6c) (1 (7 /T)
s 4M Texp (6c) /T) vt) a1
(71)
and
pz. (mlz) 2 //M (T 02-
(72)
By Proposition D.12 for the truncated conditional probability estimator pz.. we have
M
(p(mlx) - pzz. (m|x)))
RLCE, (ul=)) - RLen,P S Eexu
pj. (m/z)
m=1
(p(m/r) p/y. (m)2x))
Σ
Hawp
1(pmm/x) a + {02)
p/z. (m|2))
M
(p(mlax) 1/ (m)a)))
Eggop
{p(mma) 2 a1 + +22) = (IT)
(73)
pz. (m/z)
m=11
Thus for the first term (1) in Eq. 73 by Eq. Eq. 72 and Assumption 3.1 (ii), we have
(T) S /02) Px (p(mlx) S (a1 + a2)) S (a (2ffa2))cs (2)))(()))))))))))))))))))) + +2))
(74)
For the second term (IT) in Eq.
73
if p(m (z) 2 a1 +22 then we have a₁ S (a1/(a1 tag +a2)) )m(maa)
and thus p(m[(a) (a)) ai 2 pmm x
(a) (a) + 42 (2))p(m((z)) = (a2/(a) + +a2))p(ml(z) This together
with Eq. { yields
7 (m/a) 2 p(m|2)= - [p(m]a)) 7 (m| |) 2 p(m[)) - an 2 (a2/(a1 + a2))p(m(x))
This together with Eq. (7I). Eq. 72 and Proposition D.13 yields
(IT) < (a (a1 a2))
d.x (x))
(p(m)s)2(artas)) p(m]xx)
(a) + 02) 8-1
I1 log(as + +z2) 1(221) ) (75)
s (af(a) + az)/
((211) +
1 1-
Combining Eq. 73 Eq.
74
Eq.
75 and a1 2 az we obtain
RLCR,P(P/ (u|=)) Ri.cE,
S 01
2+ /a2 log(az) (c() & log(az) Log(a2))1(aa) (aa 2+/AA /az)
$ log(r v v eep (6cr ((1 v 1) 2+BA1 /(T V).
Notice that the right-hand side of the above inequality attains the minimal order at 7 == 7 There- fore, we choose So = 1r with 7 as the approximator to get
RLen. p f (y|x)) Ri.c.. p I (og())))0(() v 1+8A1
(76)
In addition, the definition of ir. Н in Eq. 60 together with Proposition 4.46 in Steinwart & Christmann (2008) yields
f S T
4/2g- 1I 1x
4/2 log" 2 ((1 r)/T) < - 4/2 - log² (1/7) S - 1og"(1"
This together with Eq. (76) proves the assertion.
31

---

Published as a conference paper at ICLR 2025
D.1.3 PROOFS OF MINIMAX CONVERGENCE RATES FOR KLR
Theorem D.14. Let Assumption 3.1 hold and let the CCP estimator p(y) x) be defined as in Eq. 10 we choose À n=,, 7 n -I(L+aAaaatd)) and I x n- with 0 1, then there exists some N E N such that for any 2 N and any & E (0, 1/2), there holds
(1-8A1) (L43N3)a-2
RLCE. (((y(z)) RLeg, S
with probability pa at least 1 1/n.
Proof of Theorem D.14 By combining Proposition 4.2 and Proposition 4.1 we obtain
AlIfo I + P
RiCE,P $ xy - log (r (r0))) + log(>" vt) (7 V + (-logt) (t + X An + S/n)
with probability at least 5. In order to minimize the right-hand side with respect to and X, we choose À = n -1 = 4log n, 7 = n -1(((++34))a+dd) and t = n with 1. Then we obtain
Allf 1i + RLOR. (ply)z)) RiCE,P
$
(+#ADO (--AA)aard
log" log (n- +n (47aNilo no n log
0+
For any n 2 N, there exists an E N such that log n nf. Thus we get
(=8A1) (14261)042 +22
Allf + Rrc,, P((gz)((())))) Ri.gg P S n
with probability pa least 1/n. Replacing 25 by ç, we obtain the assertion.
The proof of the lower bound in Theorem 3.5 is based on the construction of two families of distri-
bution pa and Q as well as Proposition D.15 Tsybakov 2008 Theorem 2.5) and the Varshamov- Gilbert bound in Lemma D.16 Varshamov 1957).
Proposition D.15. Let {Th, ten be family of distributions indexed over subset H of semi- metric (F.P). .P). Assume that there exist
E such that for some 2,
(i) p(hj, h4) 2 2s for all siijss
(ii) mh < Th, for all j [L];
(iii) the average divergence to The satisfies ES= KT((Tay: ITho) S log T. for some
K E (0,1/8)
Let 7 ~ nT, and let To 7 + F denote any improper learner of E H. Then we have sup H1 (p(h(Z),n) h) 2 kell
- 2n/ log L) (3 2/2)/88
Lemma D.16 (Varshamov-Gilbee Bound). Let 2 and 2 2t/8, For all 0 S < j S L, let p (a o3) = #(E [L] of + of} be the Hamming distance. Then there exists a subset (oo (o"....,o I of (- such that (orlo'a')) 2 2/8, where σº == (1....,1).
Theorem D.17. Let be the set of all measurable predictors f X - A-1 and let P be collection of all distributions P which satisfies Assumption 3.1 In addition, let learning algorithm that accepts data and outputs predictor, be denoted as A: (X x x))" + F. Then, we have
inf sup RI.cg.((A(D)) - RiCR. Zn "ITAAJTT2 A PEP
with probability pa at least (3 2/8
Theorem D.17 together with Theorem D.14 illustrates that the convergence rates of KLR shown in Theorem D.14 is minimax optimal up to arbitrary small order &.
32

---

Published as a conference paper at ICLR 2025
Proof of Theorem D.17 Without loss of generality, investigate the binary classification, i.e,,
M = 2. Let the imput space X' == [0, 1] and the output space as y {-1,1}. Define r := c,n -1(((AA++)a+td) with the constant e, > 0 to be determined later. In the unit cube X, find grid of points with radius parameter r,
{(2kgr, 2k2r, ..... 2kar) K2 1,2, (2r) 1, 1.,,...,dd d).
Denote L : [ = ((2r) - 1) and g = {aili=1 Without loss of generality, we let (6r) - 1/3 be an integer. Define the of grid points 91 {(2hgr r, 2k2r. ...... 2k(rr) ki 1 ,,.... (6r)
1 1/3, i E [d] C G and 92 = 12 2k2r, 2k2r,.... 2kar) : ki = =(r- 2)/3....,,
1, E
[d] G. Then we have [91] = G22 ((6r)-1 1/3)a --f
Construction of the Conditional Probability Distribution plylz). Since we consider the binary classification case
{1,,1}, we denote the conditional probability of the positive class as p(1[z) := ply 1/x) and the nagative class as 1f/= == 1 - p(1[x). Let the function 9-(-) on
[0, ooj be defined by
(1 - 2/r
if0 f
gx(2) = 0
if 1 r.
Moreover, let au == 1/3+r/3 and az := 2/3 - 7r/3, which are close to 1/3 and 2/3, respectively.
Given E ( _ and ca > 0, we define
cara + ccllfor = 11 of (||x- - 2,112)
if E Uneg, B(zū,r),
1 Car
if x E [ar, Unee, B(z,,r), if E Uneg, B(zir)) if x E [0, Uneeo B(z,r),
p² (1/x) =
1 1/2 + Car,r" - 12
1/2
[1/2, card)
otherwise.
Construction of the Marginal Distribution p(x). First, we define the marginal density function p(x)
by
(natto 11.8 x 22:12-1
if f E Unies, B(x,,)) \ fze)
p(x)= =
(1- (1-Ex,ES, P(B(a,r)))) ( Eneg, ()),)
x E Unies B(x,,r), otherwise.
Let us verify that p is density function by proving Sx p(x) =x= 1. To be specific.
[ pl)) [usco, Bla.m) p(x) dz / +/ p(x) dr
U B(ar))
B(a.r)
(B2l-P(B(a),)))) (1 1921 P(B(21,)))
=3-48. ((B((,((()))))) (1)))((((())))) =1,
where 21 E G2. Finally, for any a¹ E {- we write Px = Px-
Verification of the Hölder Smoothness. First, Ir satisfies the Lipschitz continuity with Ig(x) g(x')l $ r II- - x/). Moreover, using the inequality Ja" bol & la b1a, a E (0, 1), we obtain that for any xr E ()),,r), vi Gi G2, there holds
(1(x))-11 (11x)) = cara 90 (| - x=l12) - 9f (1|x' - z; 21112)l
< car | 21112) - (0 / - x; 22|12)
I r || 2:1l2/r || 22112/110 < 11,1l=''210 2112.
Therefore, p" (y)xz) satisfies the Hölder smoothness assumption.
Verification of the SVB Condition. Using the inequality 1 (1 2/1/a < 1 (1 a1-a
a -1z))
a 1
for any x E (0, 1) and E (0, 1), we obtain that for any ( < f E cara
Px (p (1|x)= 2 - 1)
33

---

Published as a conference paper at ICLR 2025
Σ Px B(r;))) cot + "ar" 1]9 - 2 1 ())
21E92
< 192 Px(f E B(xi, :1 r + cot f (11x - xn (2] 21 43)
= 3 3- - Px (fx B(x1,T) 17" - (r- || 21112) 1 c (
3 -3- Px (fx B( r): :1 -12--1112 s r
- (1- (1-6--r
a)) 1)))/)))))))))/))}})))
<3- Px (12 E B( r): =| 21112 S a
-3 Px (B( c (1)))) = 3 3-4
B(ur al p(x) de
21
a 111-0
---10-ddll dp
(dT(d/2)
00
2/2
2T24/2
34T(d/2)
Choosing c3 2 2T (LT(d/2) v 1, the 3-SVB in Assumption 3.1 (ii) is satisfied.
Verification of the Conditions in Proposition D.15 Let I, = 2 - 1. For the sake of convenience, for any 0³ E 11,, j O,..., L, we write pi == po' and Qi = Q" Denote oº :=
(-1,...,-1) and p0 po" Define the full sample distribution by
I pien
j= 0....... L.
Moreover, define the semi-metric p in Proposition D.15 by
(1)()) S (picll))oog p'(1(x) p' p'((111z) log (1|z)
p' p'(11/z)
pd -1xx) p(z) de KK((P' pi).
Therefore, for any predictor f(ylz), we have RLCs, p (p(y) [z))
RI p(p(-1z), P( (((z)))
Now, we verify the first condition in Proposition D.15 For sufficient large n, we have
20 ((6T)()2)) S 1/2. For any I E UnLEG, B r). there holds
p(x)= = 1- En,,, P(B(z,,)) 1 1 2/ (dd22 - 1------ de 6'T(d/2+1) Ex.e, ((B(x,,)))
3 /Td/22222dd((2222
2md/2
Denote the Hellinger distance between p and pi as H(Pi,P)) f(vdPi VdPij Using the inequality KL(Pi, Pi) > (Pi Pt), va fla-v Vb (a-b)/(Vā + vb) and Lemma D.16 obtain that for any 0 S < j < L, there holds
p( (())) KI. pd) 2 2P² Pt)
2 / (
p(x) dr
2 (p'(11x)) (((11)))-p((()))) (11x) (1000))))*++0(0))))111111)++)))) (-11)) + +-(()1))) p)(() dr
(w'1)=)) - (( p(x) dx
Unies B(auer)
( B(ze.r)
(('))))
p(x)) dz
2 2pm(o',or) /
6 (dd22++ dx
B((T))) (co(t-1k==11))))
2/2/2
+ ppllo',0') /
12 2 ( (ca(r-11a-111)))
(car))) 1. (60--))811 (a
=2112
8- dx
B(
2 2 (6' 1 (r- -)200 م- dp +
d/ Ca
data,,ttoee (a-8--a f- (r pp)-p
20 - dp)
T(d/2)
34

---

Published as a conference paper at ICLR 2025
= od) dr S." (1 (1-t) t)2ard-1 dt + 2m (
/ (1 1)2ay0-1 dt
r ,+(0+1)a
T(d/2)
8
6 2 Beta(2a + 1, Beraa 2m Beta (2 + 1.
T(d/2)
2 --3 2 20 Beta(22 + 1,d) + 2nd Beta 22 + 1, ()) 2 Carall+BA1)
[(d/2)
where Cj = 2 14:=2-4-2
(69 (Betaa22 + 1, d) A 2x Ca ((d22) Beta (2a + 11, By taking
== 2 Cara((+)))) C- n [1-3A1)0+d
(148416
we obtain (-)x), (+1x)) 2 2s. The second condition of Proposition D.15 holds obviously.
Therefore, it suffices to verify the third condition in Proposition D.15 which requires to consider
the KL divergence between ps and po. Using Lemma 2.7 in Tsybakov 2008 and 1 - Car 2 7/8, we get
KL(P), pO)= S / (1/(11)) (1)=2)) 8x (-111)))0(-1111) p(x) dx
Σ 110 = =1 I f B(eeer)) (1/2 + ( - rar
40, (r || Ik 22
T(d/2 + 1)34 (mr dx
Td/2
24 EGi
4ea(1 - ||0 - Ix (22112220 ndtta-1)011z
Σ 1 =1 B(oair) Cara (1 Cara)
x& 12 g-d dxr
20c (d/2 + 1)3d
JB(ew))) (r- ||0 - I* 12112) dx
d/2ppd
4c, (a
(r- [|xl)=)l12)0 2a ||0 rxell 11-- dx
r3(1 carr))
B((xr)
20c3 d pd
/-- (r (r-p) 22)
pd- dx
8// mp 138
(r (r- .p ap-pp- dx
T(d/2) r - ra)
(-- (1 (1-t) 2
Sca
8/2 8/a
mr mm
20c d3 20
(1- 1)- 88-1 dt
r(d/2) - ra)
< d3 Bota + 1, d)n2a + 8n 4/2 ca BetBBBta2B (2xx +1, 11
,a(l+))) < C2 (77)
(d((2/2) )aa
where C3= : 20c,, d3 d3 (eeaa(2++) 1, d)+ 87 c/ Beta 3etaa(att))) 8) (2T((/2)) By the independence of samples and Eq. (77). we have for any j (0, 1,
L}.
KL(U,, Ho) nKL(P), Pd) S Canr(1+
<
qd6 2(log 2) =
L.
By choosing a sufficient small e, such that 2(log 2) ( Czal (I 4d 1/16, we verify the third condition. Applying Proposition D.15 we obtain that for any estimator p(ylæ) built on D, with probability ps at least (3 2/2)/8 8, there holds
sup ( RLon,P 2 (Cic (Cog((L+D)D)))) (2) PEP
0+
which finishes the proof.
D.2 PROOFS RELATED TO SECTION 3
D.2.1 PROOFS RELATED TO SECTION 3.1
Proof of Theorem 3.2
Applying Bernstein's 's inequality in (Steinwart & Christmann 2008 Theorem
6.12) to & := 1(Y m) - pmm), i E [pp]. we get
no
2p(m)r nop
2T 3np
(m(m) - ppmm) = n2p Σ
3
$
+
35

---

Published as a conference paper at ICLR 2025
with probability at least -e_
Using the union bound and (a b)2 - 2((a² b²). we obtain
M
M
2p(m)T
2T
M
4p(m))
4r²
(m(m) p(m)) -
+
"p
3np
9m2
m=1
with probability at least - 2Ke T. Taking T = log 12 we get
M ((mm p(m)] 4 4log(2MMp))
4 4log (2Mnp)
log np
(78)
np
9m3
np
with probability at least 1/mp. Combining Inequality (33), Propositions B.7 and B.9 in al. (2024), get
Wen
RLeR. (Lcml((((llz)) - Lenn X PL RLO,, +
Σ (1/p(y) 1/p(y))
BEIM]
x RLCE, P (f(y)z)) L +
Σ (p(y) p(y))2
MEIM]
x RLC8, RLce, (P(ylx)) R RLO.P + lpggp//p
(1FAAU0T np
+ log Sognp/p S
np
with probability least 1 np. where the third last inequality is due Eq. last inequality follows from Theorem D.14
78
and the second
Proof of Theorem 3.3 Obviously, we have
: = ((,Q)) P and Q satisty Eq.
==
Theorem D.17 then yields that
inf sup R((e))(((D))) - Rien. 2 inf sup A (P.Q)ET
Rice (A((p)) RLes.Q
A (P.Q)ETT
1361)
= inf sup RLOR. RLC,, (AA(p)) - Ricg, 2 np
(14811)642
A PEP
holds with probability p"r at least (3 2222)88. This finishes the proof.
D.2.2 PROOFS RELATED TO SECTION 3.2
Proof of Theorem 3.4
Combining Inequality (33), Propositions B.7 and B.9 in Wen (024))
we get
LLE. Q (((lyl=)) - -Ri)l))))RRcc..0 S RLe.. (p(()=)) Ri.e. p + I|w" 01.
Using Proposition B.1 in Wen et al. (2024) and Theorem D.14. obtain that for any (0, 1/2), there holds
R RLen S PL RZen.P + log ng/n/ + log np/"p
(1+ +e arojardd
S np
+ log n
with probability at least
1/np - 1/ng.
Proof of Theorem 3.5 Note that the lower bound of the excess risk consists of two parts depending on np and ny. respectively. Thus the following, we prove the excess risk larger than the two parts, respectively. First, we prove that the excess risk is larger than the first part related to mp- To this end, we construct sequence of the probability distribution P as in Theorem ID.17 and then we construct the probability distribution Q. To satisfy the label shift assumption, for any rd (11,1), j 0
let Q
p For the sake of convenience, we write
36

---

Published as a conference paper at ICLR 2025
pi := and Q¹ Q² Conresoondingyy, we write pT pot (Y y/X x) and ('())) Q (Y= y X = z))
Verification of the Conditions in Proposition D.15 Let L = 2 - 1, and we define the full sample distribution by 11, pien, % Qx j O...., L. Moreover, define the semi-metric p in in
Proposition D.15 by
p(g(((l).. = J (VV ((11x) (1[x))
+ (=([)//)) log -((11[>)
((x) dz = KL((',Q')
(-(-1xz)
Therefore, for any predictor Aylx), we have RECE ( Lep.Q - p(g(-1z)) (000-1)))((((()))))) [-1x)) Since Qi = -P, the first and second conditions in Proposition D.15 can be verified in the same way as in Theorem D.17 Thus it suffices to verify the third condition in Proposition D.15 By the independence of samples, Ø'x = Qx = Px and Eq. we have for any j EE (0, 10.11.....) L).
[L [1o) n,KL(P), + ny KLLLL
x: ²xx npKIIPP Po) S Canpr CCcc(ttnijatt S Crc(+t8naaatd < 2(log 2) Cae, C log L,
where the constant C3 is defined in Eq. (77) By choosing a sufficient small & such that 2(log 1nof qd = 1/16, we verify the third condition. Apply Proposition D.15 ob- tain that for any estimator ([y|z) built on D. with probability pm, 0Q's at least (3 (3-2/2)/8. /8, there holds
(1+
sup RI R..enQQQQuu (Q(vlz)) - RiCE, 2 (C4/2) np (P.Q)TT
(79)
Next, we construct a new class of probability to prove the second part no" of the lower bound. Let 1/16 and d >> O. Define the 1-dimension class conditional densities:
Awo
if xr [0, 1/4],
4(1 w)o
if E [0, 1/4,, if a E [3/8, 5/8), if x E [3/4,1],
4(1 - 5)
if E 53/8,5/8), if E 13/4,1],
4(1 - 8)
g(a|1)= =
g(xl - 1) =
4(1 - w)
4wō
0
otherwise:
otherwise.
(80)
Let E (-1.1) and 8 will be chosen later. We specify the class probabilities in the following way: p(1) == 11 1/2, q² (1) == (y = == (1 + o2)/2. Then we compute the conditional
probability function of (1(x). By the Bayes formula, we have
qd (1])
(1/x) (1)) + (-1)g((1 1)
w(1 + (o0)/[w[1 o0) + (1 w)( xf)]
if E [0, 1/4],
(1+00)/2 /2
if 1 E [3/8,5/8].
(1-w)(1 + /00//(((/// - ([(--) + o0) + w(1 - -00]]
if E [3/4,1],
1/2
otherwise.
Verification of the SVB Condition. Denote
w(1 0)
w(1 0) t2 w(1 + 0) + (1 - w)(1 -0)
8 == w - 0) (1-
For < 41, have (1((() < () 0. For (2), by taking 0 1/(16/th,) and
8 = cgtf, we have
(1)1 <t) = 1(ao = - 1)4((),144)
=1(0 = - 1)((1 - 0jw6/2 + +) ww)/2)
=1{0 1)(1 + - 20w 20/) / < R 8= = - cst
37

---

Published as a conference paper at ICLR 2025
Moreover, for t E [t2, (1 - 8)/2,, we have
(f(() < f) Q00 1/4)) = (1 + 0 10:02000 20/ S cst & cat
Otherwise if E - (1--))2.112) by taking cg := 4 there holds
(g <) =
(1 0 20w) 6/2
S s11...
We define our distribution class : (11- : o E { |-1, where 11 is defined as 11 == pm x
(*x)",, Then using the inequality (og((1 (1 + x x)) - 3x for 0 x 1/2, the Kullback-
Leibler divergence between II and II² is
KL(MI pr*) - mn, 5 n, (L('IQQ)))
= (1gg((1 + 0)
(1+ log - + +1) (1-0/((1
0)/2)
= 20m, log((1 + ()) < 6, = -
Since KC| = 2, IT < IT- and (K]- 3/256 < (log 2) 88. Then we calculate the
excess risk. Define q² (y/2z) = Q = x) and oe (1) = Q" PY y). The semi-metric p is defined by
p(a'()))), (vl=)) = / (11(11z) log log (1(1/x)
q2 (-11/x)
(1|x) + log
a- (-1x)) ((x)) da
= - log(tz/11)) (1)((11 + log((1 (2)(11 - (-1))((11)(4))))) 1) dr
1 6) 0))g (1)g(=11 log((1 0)/(1 + +0))g (-1)g(x: 1) dx
[3/8,5/88
/ log(te/t1)4 (1) (og(ts/tt) +og 12) (-1)g(z) -1) dx
+
[3/4.1]
= log((1 + ()
- 0))
(t +
20w) / - + 20w))
2 0² + 1 + 20w
12t(1-210)
1 2w)² ス 256 (1+ (1/8) =: 202n,
(81)
where the second last inequality is due to log(1 + x) 2 x/2 for x E (0, 1) and c2 = 512-1(1 + (7/8)248). By Proposition D.15 we then obtain that with probability 11 at least (3 (3-2v2)/8, there holds
sup R.en.o(((yl)) mek
Ri.CE. 2 c2m
(82)
Combining Eq. (79h and Eq. 82 we obtain that for any Tylx:) built on Dp U Dg. with probability
pd> 8 Qx x least (3 2/2)/8. 8, there holds
(1+8A11
sup (P.Q)TT
R.CE ((ul)) - Rice. 2 at
+ nn nn1))
(83)
where == C1/2 A c2. This finishes the proof.
D.2.3 PROOFS RELATED TO SECTION 3.3
Proof of Theorem 3.6 First, let Ō be the true matrix, i.e. Oig = (=X(()==)))((())) By the triangle inequality, we have
1Ck Ckyl S [Cky [PP.(XIY + (ELLCXI-
-Cysl
Σ (f())) --IXII=;;((XX)) + -
-
(84)
Maj sE(
Applying Bernstein's inequality, we get
Σ
(P())) [XXXX(=))((XX)) S
2T
2r
< 221
T
< 20,.1
NsJ
ns..j
3nzj
ns.j
n
iE(n,),,
38

---

Published as a conference paper at ICLR 2025
with probability at least 2e, where Ca,1 (NJE(M) Pa(i)) By the union bound, have
3 3log(n,M)
max J.k
Σ
(f(k)X) (XXXI(=)))((])]) S 2cs,1
(85)
ns.
11
sE[n.],xi=j
with probability at least 1 - 1/ Moreover, using the Bayes formula and the label shift assumption, get
EP((IY-)))P(X ((( p(X|X)] / ((k))) p(k|2)) -p(=l)) dr
(((ckl))) p((|=)) p(z)p(i(a)
dx s(i)) 1 [[(()0)) p((((zr) p(z) de
p(1)
- P((k)))) p())))) p(x)) dx
1/2
S P R RLEE,)) 1/2
where the last two inequalities follow from [EX)² < EX² and Lemma B.4 in Wen et al. 2024 respectively. This together with Eq. (84) and Eq. (85) yields
Ca. Ca.l E (logn./n.) 1/2 (Riee, RLCR,P) 1/2
max j.k
with probability at least 1/n - 1/npp Using Theorem 4.2 in Meyer 1980), we get
|| pll1 s -)All - ||C || & (log n 1/2 + P RLoE, 1/2
where A is the group inverse of the matrix Id C. Combining Inequality (33), Propositions B.7 and B.9 in Wen et al. (2024), we obtain
RL Q ()))
RLCR.Q & RL RLC..P +
Σ
(1/p(y) 1/p(v))
ME[M]
S RL (Ply((x) Ri + Σ (p(v) p(y))2
BE[M]
2 RLcn.p(p(yla)) RLC3.P + |lp P11
11:311)a + + logn,//n.
S "p
with probability at least 1 - 1/n, - 1/nps where the last two inequalities follow from ||p - 213 < lp - and Theorem D.14 This finishes the proof.
Note that the lower bound of the excess risk consists of two parts. Thus in the following, we prove the excess risk is larger than the two parts, respectively. First, we prove that the excess risk larger than the first part. Similar to the first part of proof of Theorem 3.5 let
Proof of Theorem 3.7
Q-' = - = S where j E {0, .0,...,2' 2 13. Then similar analysis as in Eq. 79 yields the lower bound
BD OF
(np n.))
(np V n.))
For the second part, the construction of distribution P and Q" totally follow the second part as in Eq. (80) and we let S Q". Similar arguments for proving Eq. (3) show the lower bound n,
This together with the first part yields the conclusion.
E CONVERGENCE RATES FOR THE CLASSIFICATION LOss
In this section, we present the convergence rates with respect to the classification loss for the three complex scenarios. To this end, first combine the calibration inequality in Eq. (I) and the vergence rates with respect to the CE loss in Eq. [T] Eq. (13) and Eq. (15) yields the following results.
39

---

Published as a conference paper at ICLR 2025
(a) In the long-tailed learning, we have
2ulTaala +6/2
(11 BAil
Letam @ (Q(v(x)) R Leime S R0p
(86)
(b) In the label shift adaptation, we have
+E/2
Reiiam Q eQ((y(=)) R R S Rp
+ ng)
(87)
(c) In the transfer learning, we have
(1 DA-D 22443116 +E/2
R R @ (ā(zlz)) Riesnen S npp
+ (log n (logn./n.))
(88)
To derive the lower bound for the classification loss, we follow the analysis for the constructed probability distribution in Theorem 4.1 offAudibert & Tsybakov (2007). Since the constructed CCP lies within range [Cp, 1 cøl with a constant Cp E (0, 1/2), the distribution satisfies the SVB in Assumption 3.1 (ii) with any / E [0, oo] and therefore their established lower bound n a2aa2a) holds under Assumption 3.1 for the standard classification.
(a) In the long-tailed learning, we let Q = P, then the lower bound would be
inf sup (aieeen@((())) ((A(D,)) RLe.e.. A P.Q
-R Q
2 R&p
2044
(89)
(b) In the label shift adaptation, we have two parts of lower bounds. For the first part, we let Q == and thus get the lower bound /aaa/en -a/(2a+-) by applying the conclusion in the standard classification. For the second part, we follow the constructed probability distribution in Theroerm 3.3 and obtain that the excess classification error
/ 124 (1/x) 11. 1
{ max ( + max q m (ulz) q (x) dx
p(a' (ul=), (
f (3/8,5/88
(x)(x) dr (1 - 8)0 = (1 (1- (16
holds with probability at least a constant E (0,1). Similar analysis of Eq. 82 bound of the order ng
yields the lower
1/2 Combining these two parts, we get
inf sup R.ttar ( (A(D)) - -Ri Ricima Q Z np 2012 A P.Q
+ my 1/2
(90)
with probability at least constant e E 10.
(c) In the transfer learning, similar analysis of Eq. 90 yields the lower bound
inf sup R.ant (A(D)) - RRisswn 2 Up
2042
+ m2 1/2
(91)
A P.Q.S
holds with probability at least constant E 10.
3 1, then the upper bounds in Eq. (6 Eq. and Eq. (88) match the lower bounds in
Eq. (89). Eq. (90) and Eq. (1). respectively. This demonstrates that the KLR-based approaches in
Section are minimax optimal with respect to the classification loss when the probability that CCP
is less than threshold increases sub-linearly the threshold increases from zero, i.e. , 2 1.
F EXPERIMENTAL DETAILS
Using the benchmark datasets, we construct the labeled data Dp and the unlabeled test data D. ) from the distribution Q to evaluate performance. Additionally, we construct D for label shift adaptation and D, for transfer learning. To achieve this, first generate label distributions using either a uniform or Dirichlet distribution. Based on these distributions, we randomly resample data from the original benchmark datasets to create the required datasets. Specifically, generate
40

---

Published as a conference paper at ICLR 2025
10 labeled datasets D.. and for each Dp. create 10 test datasets D and 10 additional datasets (e.g.. Dÿ or Dz) using different random seeds, resulting in a total of 100 repeated experiments.
(a) In the context long-tailed learning, the label distribution g(y) set to be uniform, while the long-tailed label distribution p(y) is generated using Dirichlet distribution with parameter a = 1. Based on ply). we resample "p samples from the original benchmark dataset to construct the labeled dataset Dp- Similarly, resample ny samples according g(y) to generate the unlabeled test dataset D,, which will be used for prediction, along with their corresponding true labels for evaluation.
(b) In domain adaptation under label shift, following the setup in Lipton et al. (2018), the source la- bel distribution p(y) is uniform, while the target label distribution ( is generated using Dirichlet distribution with a 1. Using these distributions, we construct Dp. D and Dr from the bench- mark data, sampled according to p(y). q(y), and g(y), respectively. The CCP estimator T(ylor) is trained the combined dataset (Dp, D and evaluated the test dataset D.
(c) In transfer learning, while the labeled dataset D, is unavailable, we do have access to the CCP estimator p(y| (z). pre-trained on D, using the KLR method. Additionally, we utilize auxiliary data D constructed by resampling n, samples from the remaining benchmark data based on a label distribution syy) This distribution generated using Dirichlet distribution with the parameter 10.
Table 2: Data Descriptions in Three Complex Classification Scenarios
Long-tailed
Domain Adaptation
Transfer Learning
Dataset
M
Rp
fg
f2
Dionis
416188
355
14200
7100
14200
7100
14200
14200
5000
7100
Gas Sensor
13910
128
6
3000
1000
3000
1000
3000
3000
1000
1000
Sat image 6430
36
6
1500
1000
2400
1200
1200
1500
1000
1000
When fitting the KLR model to the source domain D,. we select two key hyperparameters: the regularization parameter and the kernel coefficient 7. These are determined using 5-fold cross- validation. Unlike the commonly used classification loss, cross-validation, as our primary objective to accurately estimate p(y]z). Specifically, from seven values evenly spaced logarithmic scale between 10-6 and 10", while y is selected from seven values evenly spaced on a logarithmic scale between 2-6 and 20.
the CE loss the criterion for chosen
41


Reviews:
[{"review_id": "WoKMrZWoA4", "reviewer": "Reviewer_ZQYY", "summary": "This paper provides a theoretical explanation for the empirical success of conditional class probability (CCP)-based method, particularly regarding the cross entropy (CE) loss. Specifically, this paper first truncates the CCP estimator to prevent large CE loss. Consequently, the authors discuss the properties of kernel logistic regression (KLR) in three complex classification scenarios. The findings indicate that KLR can achieve minimax optimal convergence rates for CE loss under mild conditions. Furthermore, the error analysis reveals that the excess CE risk for the complex classification scenarios can be reduced to that for the standard classification, establishing a new oracle inequality of KLR for CCP estimation.", "questions": "1. In Section 2.1, why is the label probability $q(y)$ set to be uniform while $p(y)$ is far from being uniform? Could you provide more context behind this choice?\n2. The equation in the Theorem 3.5 is not labeled. Labeling this equation would improve readability and make it easier to reference later in the paper.\n3. Note that the first item on the right-hand side of Equation (11), (13) and (14) is the same. The same pattern is observed in the results of lower bounds. Could you explain this phenomenon? What it might reveal about the fundamental nature of these classification tasks?\n4. This paper presents important theoretical results. Could the authors explain how the results can help improve the practical solution of complex classification scenes? For example, what particular aspects of algorithm design or parameter selection that might be informed by these theoretical results? Including toy experiments might be beneficial to illustrate the practical impact.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tThis paper is well-written and organized. The theoretical analysis is detailed and coherent. \n-\tThis paper has proposed a significant theoretical understanding of CCP-based approaches. The results are impressive.", "weaknesses": "Please see the **Question** section", "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": "KXvCAJ1rWg", "reviewer": "Reviewer_Xy6p", "summary": "This paper proposes a theoretical framework using Kernel Logistic Regression (KLR) to address the Conditional Class Probability (CCP) estimation problem in complex classification tasks. By introducing error decomposition and a new oracle inequality, the researchers demonstrate KLR’s optimal convergence rates in scenarios like long-tail learning, label shift, and transfer learning, underscoring its effectiveness in both theoretical and practical applications.", "questions": "1. The experimental section is relatively limited, which limits validation of the framework's practical utility. Examples in the paper lack real-world data validation in complex classification settings, especially regarding long-tail learning and transfer learning. More comprehensive experiments with various real datasets are needed to demonstrate the theoretical findings effectively.\n2. In Assumption 3.1, the authors assume smoothness of the conditional probability function and impose a lower-bound condition on probability values. However, these assumptions are challenging to satisfy in real-world data, where extreme nonlinearity or sparse data often preclude such smoothness, especially in high-dimensional settings. This limits the generalizability of the framework for practical applications.\n3. Although kernel methods can theoretically enhance model expressiveness, the complexity of Kernel Logistic Regression increases significantly with sample size and feature dimensions. Particularly in high-dimensional datasets, memory consumption and computation time grow exponentially. While the authors suggest a Gaussian kernel-based approach, they do not provide further optimization strategies to alleviate computational costs. For large-scale datasets, it would be beneficial to explore additional methods for reducing computational burdens to enhance scalability.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors decompose the unbounded CE loss into upper and lower bounded components, ensuring the boundedness of the sample error term. This decomposition enhances the model's interpretability and strengthens the robustness of using KLR for CCP estimation in complex tasks.\n2. The proposed framework is versatile, offering potential applicability across various complex classification task scenarios and showing promise for real-world applications in long-tail distributions, label shift, and transfer learning.", "weaknesses": "1 The paper focuses on theoretical analysis without experimental validation on real-world datasets or applications. Although the theoretical results suggest that KLR has potential in complex classification tasks, without empirical evaluations, it’s difficult for readers to assess the method’s practical performance or compare it to other methods.\n2 The paper highlights the theoretical advantages of KLR in complex classification tasks but does not extensively compare it with other commonly used kernel methods (e.g., Support Vector Machines, Gaussian Processes) or modern deep learning methods.\n3 The theoretical proofs rely on several assumptions about the data distribution, such as smoothness of conditional probabilities and specific constraints on small values. These assumptions may not hold in all real-world applications, which could affect the generalizability of the method. For example, in long-tailed or multimodal data distributions, these theoretical assumptions might be difficult to satisfy, potentially resulting in degraded model performance.", "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": "Dq7gl4eRM1", "reviewer": "Reviewer_ygYV", "summary": "The existing literature offers limited theoretical exploration of conditional class probabilities-based algorithms for classification in complex scenarios, particularly concerning the cross-entropy loss. In this paper, authors investigated the convergence rates of algorithms based on conditional class probabilities estimation using kernel logistic regression in complex classification scenarios, such as long-tailed learning, domain adaptation, and transfer learning.", "questions": "Please explain the 3rd weakness mentioned above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A new oracle inequality for kernel logistic regression is established that holds with high probability.\n\n2. The approximation error of kernel logistic regression w.r.t. the cross-entropy loss is derived.\n\n3. The optimal convergence rates w.r.t. the cross-entropy loss for complex variants of classification problems is established.", "weaknesses": "1. As stated in the 3rd paragraph, the main motivation is \"The existing literature offers limited theoretical exploration of conditional class probabilities-based algorithms for classification in complex scenarios, particularly concerning the cross-entropy loss.” It can be better to show the connection of the findings in this paper (i.e., kernel logistic regression for complex classification scenarios) and existing findings for standard classification scenario.\n\n2. It can be better to show the connection of the three contributions in introduction. In the current version, it is even hard to find if there is some connection them with the title of this paper.\n\n3. The main novelty is to restrict applications into three kinds of scenarios, i.e., long-tailed learning, domain adaptation, and transfer learning, which are called complex classification scenarios. I know all of them, but I don't know why they are put together in this paper (especially for long-tailed learning). Is there any logic to that? Why does the author focus on these three scenarios? The current version feels pieced together.", "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": "XXvsvpjwCF", "reviewer": "Reviewer_rSR9", "summary": "This paper explores the theoretical properties of kernel logistic regression (KLR) in addressing complex classification challenges, such as long-tailed learning, domain adaptation, and transfer learning. The study highlights KLR's strengths in conditional class probability (CCP) estimation and demonstrates that KLR-based algorithms can achieve minimax optimal convergence rates for cross-entropy (CE) loss under mild conditions. \n\nThis paper presents the relevant theory of kernel logistic regression in complex classification scenarios and provides thorough justification. While it is a solid theoretical work, it somewhat lacks practical guidance for real-world classification problems. Readers may find it difficult to extract feasible methods for addressing issues such as long-tailed distributions from the presented arguments.", "questions": "See Weaknesses.\n\n1. Based on these theories, how should we design classification models? Could you provide some examples explicitly addressing issues like long-tailed distributions? Alternatively, could you analyze existing models, such as LDAM-DRW [1] and Logit Adjustment, and suggest possible improvements?\n\n[1] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga,and Tengyu Ma. Learning imbalanced datasets with labeldistribution-aware margin loss. In NeurIPS, pages 1567–1578, 2019.\n\n[2] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In ICLR, 2021.\n\n2. Data, models, and loss functions are key considerations in classification tasks. This paper has already provided analysis from the perspective of the model (kernel methods) and the loss function (CE). Typically, when dealing with complex tasks, data augmentation techniques such as rotation, flipping, crop, and noise addition are applied. How would these operations impact the proposed framework?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper provides a theoretical analysis of optimal learning for kernel logistic regression in various complex scenarios, including long-tailed learning, domain adaptation, and transfer learning.\n2. A detailed proof process is provided for the theories related to KLR and cross-entropy (CE).\n3. Exploring and analyzing complex classification scenarios from a theoretical perspective is insightful and innovative.", "weaknesses": "1. Currently, kernel-based methods cannot compete with mainstream neural network methods in real-world classification tasks, such as ImageNet and iNaturalist 2018. As a result, the practical significance of this work may be significantly diminished.\n2. To determine whether the theory is truly applicable in complex classification scenarios, experimental validation is needed. This paper lacks experimental results to verify whether the proposed theory aligns with real-world situations. By conducting experiments, further analysis could be done to identify in which cases the theory holds and in which cases it does not. This would provide readers with more valuable insights and practical references.", "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)