Smooth Calibration Error: Uniform Convergence and Functional Gradient Analysis
Authors: Futoshi Futami
Atsushi Nitanda
Venue: ICLR 2026 Poster (2026)
Keywords: calibration
smooth calibration
gradient boosting
ece
generalization
uniform convergence
Primary area: learning theory

Abstract: Calibration is a critical requirement for reliable probabilistic prediction, especially in high-risk applications. However, the theoretical understanding of which learning algorithms can simultaneously achieve high accuracy and good calibration remains limited, and many existing studies provide empirical validation or a theoretical guarantee in restrictive settings. To address this issue, in this work, we focus on the smooth calibration error (CE) and provide a uniform convergence bound, showing that the smooth CE is bounded by the sum of the smooth CE over the training dataset and a generalization gap. We further prove that the functional gradient of the loss function can effectively control the training smooth CE. Based on this framework, we analyze three representative algorithms: gradient boosting trees, kernel boosting, and two-layer neural networks. For each, we derive conditions under which both classification and calibration performances are simultaneously guaranteed. Our results offer new theoretical insights and practical guidance for designing reliable probabilistic models with provable calibration guarantees.

Published as a conference paper at ICLR 2026
SMOOTH CALIBRATION ERROR: UNIFORM CONVER- GENCE AND FUNCTIONAL GRADIENT ANALYSIS
Futoshi Futami" ,2,,, Atsushi Nitanda
'he University of Osaka, Japan
PRIKNN AIP, Japan
*Institute High Performance Computing, Agency for Science, Technology and Research, Singapore
'Centre for Frontier Al Research, Agency for Science, Technology and Research, Singapore 'College of Computing and Data Science, Nanyang Technological University, Singapore
"futami futoshi aalosaak-u.act fAtssshi Beaishh__itttte Nitannaa aetassttrr.dd...
ABSTRACT
Calibration is a critical requirement for reliable probabilistic prediction, especially in high-risk applications. However, the theoretical understanding of which learning algorithms can simultaneously achieve high accuracy and good calibration remains limited, and many existing studies provide empirical validation or theoretical guarantee in restrictive settings. To address this issue, this work, we focus on the smooth calibration error (CE) and provide uniform convergence bound, showing that the smooth CE is bounded by the sum the smooth CE over the training dataset and generalization gap. We further prove that the functional gradient of the loss function can effectively control the training smooth CE. Based on this framework, we analyze three representative algorithms: gradient boosting trees, kernel boosting, and two-layer neural networks. For each, we derive conditions under which both classification and calibration performances are simultancously guaranteed. Our results offer new theoretical insights and practical guidance for designing reliable probabilistic models with provable calibration guarantees.
INTRODUCTION
Probabilistic prediction plays a central role many real-world applications, such as healthcare (Jiang et al., 2012), weather forecasting (Murphy & Winkler, 1984), and language modeling (Nguyen & O'Connor, 2015), where uncertainty estimates are often critical. Since ensuring the reliability of such predictions has become key challenge in modern machine learning, calibration Dawid (1982); Foster Vohra (1998) which requires that predicted probabilities align with the actual frequency of the true label-has attracted increasing attention. Calibration is relatively weak condition that be satisfied by simple models. However, it is frequently violated in practice. Notably, Guo et al. (2017) demonstrated that many modern deep learning models can be significantly miscalibrated, which has since drawn increasing attention to calibration within the machine learning community. Although various regularization techniques (Kumar et al., 2018; Karandikar al., 2021; Popordanoska et al., 2022; Marx et al., 2023) and recalibration methods (Zadrozny & Elkan, 2001; Guo et al., 2017; Gupta & Ramdas, 2021; Kull al., 2019) have been proposed to improve calibration, most of them are either empirically evaluated without a theoretical guarantee or lead to a trade-off between calibration and sharpness (Kuleshov & Liang, 2015), degrading predictive accuracy. As result, it remains unclear which learning algorithms train well-calibrated predictors without sacrificing accuracy.
One classical approach to this problem is the minimization proper loss functions, such as the squared loss or the cross-entropy loss (Schervish, 1989; Buja al., 2005). These losses are minimized in expectation by the true conditional probability and thus have a natural connection to calibration. However, in practice, constraints model classes and suboptimal optimization may prevent proper losses from yielding calibrated predictions. To address this issue, in a recent theoretical work, the notion of post-processing gap (Blasiok et al., 2023) has been introduced, which quantifies the

---

Published as a conference paper at ICLR 2026
potential improvement of the loss function achievable by applying Lipschitz-continnon transfor- mations to the model outputs. This framework provides an optimization calibration. Nevertheless, analyses based on this concept typically assume access to infinite data (i.e., population-level risk) (Blasiok et al., 2023; Globus-Hare Harris et al., 2023), which limits their applicability to real-world algorithms based on finite training samples. Furthermore, only few theoretical results explicitly connect calibration error with concrete learning algorithms (Hansen et al., 2024; Blasiok al., 2023). As result, key question remains unresolved: What types of learning algorithms can achieve both high predictive accuracy and strong calibration guarantees in practice?
wttiiiiattioottootttiicoo theoretic perspective on
To address this gap. we focus on the smooth calibration ervor (CE) (Blasiok et al., 2023: Foster Hart, 2018; Kakade & Foster, 2008), recently proposed calibration metric for binary classification that has favorable theoretical properties. Using smooth CE, we contribute to answering the above question through two main theoretical advances. First, we derive a uniform convergence bound for smooth CE, showing that the population- smooth CE can be bounded by the smooth CE over the training dataset plus generalization gap (Section 3). Second, we prove that such training smooth CE can be bounded by the norm of the functional gradient (or its approximation) of the loss evaluated on training data, providing principled criterion for optimizing calibration (Section 4). Taken together, these results show that algorithms that achieve small functional gradients while regularizing model complexity can obtain small smooth CE.
We apply our theoretical framework to three representative algorithms for the binary classification closely tied functional gradients: gradient boosting trees (GBTss, kernel boosting, and two- layer neural networks (NNs). For GBTs, we provide the theoretical guarantee for their calibration performance, showing that the smooth CE decreases with iteration (Section 4.1). For kernel boosting, we analyze the trade-off between optimization and model complexity induced by the reproducing kernel Hilbert space (Section 4.2). For two-layer NNs, we leverage their connection to the neural tangent kernel to study calibration behavior on the basis of function space optimization (Section 4.3). Furthermore, for all these algorithms, by introducing margin-based assumption, we derive sufficient conditions on the sample size and the number of iterations required to simultaneously achieve e-level smooth CE and misclassification rate under appropriately chosen hyperparameters.
In summary, in this work, we develop unified theoretical framework for the smooth CE that integrates a uniform convergence analysis with a functional- eeeetional-grdient--eeee -r-ddgrt--adseeeee characterization of training dynamics. Our results establish new theoretical foundations for understanding and improving calibration in modern learning algorithms.
PRELIMINARIES
In this section, we introduce proper losses and the smooth CE.
2.1 PROBLEM SETTING OF BINARY CLASSIFICATION
We denote random variables by capital letters (e.g., X) and deterministic values by lowercase letters (e.g...) .)) The Euclidean inner product and norm are denoted by and respectively.
We consider a binary classification problem in the supervised setting. Let Z = X' x ) denote the data domain, where X C. I2 is the input space and y {0. 1} is the label space. We assume that data points are sampled from an unknown buta-generating distribution D over X' x Y) Let F be class of predictors f X' -> [0, approximating the ground-truth conditional probability f*(x)) E [x:].
To evaluate the performance of the predictor, we use loss function. Since the task is binary classification, the label Y follows a Bernoulli distribution, i.e., Y ~ Ber(u) for some v E [0. 1]. where Pr(Y = 1) = v. A loss function is defined as L [0, 1] x y + R. with evaluation given by E(v,y) y). Our goal is not only to achieve high classification accuracy but also to assess the quality of the predicted probabilities. In this context, proper loss functions play a central role (Gneiting & Raftery, 2007). The loss E is called proper if, for any u, o' E [0, 1]. the following holds: By-BBe(w)][(C Y)] < Ey -Be())))) [e(v', Y)).
For clarity, we focus on two representative proper losses: the squared loss (v, y) (v u)² and the cross-entropy loss (V, y) == -y log v (1 - 3) log(1 v). Given x and f. we substitute f(x) in these expressions. For other proper losses, see Appendix A and Blasiok et al. (2023).
2

---

Published as a conference paper at ICLR 2026
2.2 CALIBRATION METRICS AND LOSS FUNCTIONS
Given a distribution D and a predictor f, we say the model is perfectly calibrated if B| [(X)] - f(X) holds almost surely (Blasiok et al., 2023). Various metrics have been proposed to quantify the deviation from perfect calibration. The most widely used metric is the expected calibration error (ECE); ECE(f) == E [[ f
f[ Despite its popularity, ECE is difficult to estimate efficiently (Arrieta-lbarra et al.. 2022; Lee et al., 2023) and is known to be discontinuous (Foster & Hart, 2018; Kakade & Foster, 2008). As a more tractable alternative, we focus on the smooth CE:
Definition 1 (Smooth CE (Blasiok al., 2023)). Let Lip (10, 1], 1-) be the of L-Lipschitz functionsfrom [0, 1] to [-,,1]. Given f and D, the smooth CE is defined as
sup sm D) (0. (0.11)
E [x(((X)) (X-((x)))-
We remark that the concept of the smooth CE is also introduced in Foster & Hart (2018); Kakade & Foster (2008). We also express smCE(f, D) =
([0.1)[--111) ( ((x)) Lz(D)) The smooth CE offers favorable properties such as continuity and computational tractability (Blasiok et al., 2023; Hu et al., 2024). Moreover, the smooth CE provides both upper and lower bounds on the binning ECE, making it principled surrogate for analyzing calibration. See Section 5 for details.
Blasiok et (2023) established a connection between the smooth CE and the optimization based on the concept of the possible improvement of the function under the squared loss. Given f and D, we define the post-processing gap as
inf pGap(J, D) = ((x)) heLip, 1,11) ([x))((()))))) + +((()), Y)).
Then, the following inequality holds (Theorem 2.4 Blasiok et al. (2023)):
smCE(J, D)² < pGap(S, D) S 2smCE(J, D)-
(1)
Blasiok et (2023) also provided analogous results for the general proper scoring rule, which indicates that the potential improvement in the population risk is closely tied to calibration quality.
We now consider the setting of the cross-entropy loss. In practice, the predicted probability f is often obtained by applying the sigmoid function to logit function g X - IR i.e., f(x) =g(()) 1/(1 + e =(())). Therefore, it is more natural to consider post-processing the predicted probability f. as many models explicitly learn logits and apply the sigmoid function only the final prediction stage. We define corresponding post- post-processing gap the logit function with the cross-entropy loss as
the logit g rather than
pGap" (g. D) = ( (o())))) Y)
inf (2.--.4)
Eleent (g(((X) + h(g(X)))
where Lip, (RR [-4, 4)) defines a class of 1 1-Lipschitz functions from R to [-4, 4] and the choice of 4 reflects the fact that the sigmoid function is 1/4-Lipschitz. Then, this post-processing leads to defining smooth CE directly over the logit function:
Definition 2 (Dual smooth CE (Blasiok et al., 2023)). Given a logit function X + IR and f(x) (g(x)), the dual smooth CE defined as
SmCE (g, D) =
sup (R.--.1
Similarly Eq. (1), the following relation holds:
2smCE" (g, D)² < pGap"(g. D) < 4smCE" (g, D).
(2)
Finally, note that the dual smooth CE always upper bounds the smooth CE: smCE(J, D) < smCE (g, D). Hence, minimizing the dual smooth CE guarantees a small value of the smooth CE.
3 UNIFORM CONVERGENCE OF THE SMOOTH CE
As shown in Eqs. (1) and (2), (dual) smooth CE is related to improvements in the population risk, and Blasiok al. (2023) utilized these relationships to analyze when algorithms can achieve a small
3

---

Published as a conference paper at ICLR 2026
smooth CE. However, their results defined over population-level quantities, where the expectation by D is taken, making them inapplicable to practical algorithms trained on finite data points.
Since goal is analyze the behavior of the smooth CE under standard learning algorithms trained on fimite data, is natural to consider its empirical counterpart. Given a dataset S, = {(,,, ) consisting of independently and identically distributed (i.i.d.) data points sampled from the data distribution D, we define the empirical smooth CE (Blasiok et al., 2023) given S, as
smCE(f,
heLip, ((0. 1.1)) M(((x)) (Y (Xx))
sup
We also express this as smCE(S, S.) sup ((.1)) - We similarly define smCE" (g, S,) as empirical counterparts of smCE (g. D).
We consider two datasets: a training set Str {Zz /im ~ D", used to learn the predictor f. and as the training smooth CE,
an independent test S. - { DD We call SmCE(J, smm smC Ste) as the test smooth CE, and smCEJ, / D) as the population smooth CE. Given Sur. we are interested in evaluating [smC D) smCE(ff S.)), Blasiok et al. (2023) has shown that (smCE(f, smC St.) = Op(1/vn).
(3)
Therefore, we need to evaluate |smCE((f, S..) smCE(f. S.:). which we refer to as the smooth CE generalization gap. Combining this gap with Eq. (3), we obtain the desired bound. To evaluate the smooth CE generalization gap, we use the covering number bound (Wainwright, 2019). Suppose that F is equipped with the metric ||- ol Le,, F. (loo) be e-cover with metrie || ll of F, with the cardinality NF,,F, FI )l Then, for any F, there exists f ((c, Il such that || fl <.
We now present our first main result: (All proofs for this section are provided in Appendix C.)
Theorem 1. Let Ste ~ DD and Ser DD be independent test and training datasets. Then, for any 5 > O, with probability at least 1 8 over the draw of Sie and Sw. we have:
In In F, 1l0e) de +2
logó-1
sup |smCE(f, Sm) S.)) inf Se + 24 feF
c20
n
n
Since the smooth CE involves evaluating the composite function h((())) standard chaining bounds would introduce complexity over the composite class Lip, ([0, 1], 1-1, 1))oF. However, by leveraging the smoothness property of smooth CE, the above bound does not include the complexity of Lipschitz functions. Combining Theorem I with Eq. (3), we obtain the bound for the population smooth CE.
Corollary 1. Under the same assumptions in Theorem 1, there exist universal constant C₁ such that with probability at leastl - over the draw of Su. the following holds for all EEF:
|smCE(J, -Smb:: C1 inf 8E B2+24 200
In (. 1100 de' +31 [[,
log 3 a
24
7
The first term of the right-hand side represents the complexity of the Lipschitz function class.
In certain cases, the Rademacher complexity offers a more interpretable characterization (Mohri et al., 2018). The empirical and expected Rademacher complexities of a function class F are defined as Rs(F) = E, sup Σ (x:) and Ri (F) == Ep (Rt respectively.
Theorem 2. Under the same assumptions as in Theorem 1, there exist a universal constami C2 such that with probability at least d over the draw of Su., the following holds:
C2 Vn + 49RD (FD (F) + 21
log 2/
sup [sm D) smCE(J, fEF
The first term on the right- side reflects the complexity of Lip, (10, 1]. [-1. 1)). while the second corresponds to F. A direct application of uniform convergence theory would yield a bound in terms of
Hp, (10, 1), [-1, 1)) o F), which cannot be reduced (F) using the standard contraction
4

---

Published as a conference paper at ICLR 2026
lemma. Our analysis cireumvents this difficulty by employing covering argument for Lipschitz functions. Similarly, Rademacher complexity can be used to bound [s smCE Su)) However, such a bound depends the complexity of the Lipschitz function, making it suboptimal relative to Theorem 1. See Appendix D for a detailed comparison between Corollary and Theorem 2.
In conclusion, by jointly controlling the complexity of the hypothesis class and reducing the training smooth CE, we guarantee a small population smooth CE. In the next section, we show how to achieve small training smooth CE via functional gradients.
CONTROLLING THE SMOOTH CE VIA FUNCTIONAL. GRADIENT
In this section, we discuss how we can minimize the training smooth CE. From Eqs. (1) and (2), (dual) smooth CE can be characterized via the (dual) post-processing gap, which describes the potential improvement over functiins. Building on this perspective, we show that both smooth and dual smooth CEs can be further characterized using functional gradients. Since we focus on the functional gradients over the training dataset, they just finite- siite-dimensionll vectors. We provide the precise connection between functional gradients and the population smooth CE in Appendix I.
For the squared loss, the gradient for the predicted probability is V flesa (f. = y. and for the cross-entropy loss, the gradient for the logit is V. (o (g), 8) = ( - y. Using these, we can write the smooth and dual smooth CEs on the training dataset S.r
smCE(J,
sup kELip, ((0,1).--111)
-v (f(),, L) L2(S.))
smCE (g, = sup /E
(M(((X)), - (o Lo.))
The connection between functional gradients and the smooth CE can be extended to general proper scoring rules using the post-processing gaps, see Appendix for the details.
Therefore, to effectively control the training smooth CE, it is natural to consider algorithms that focus on functional gradients. From this perspective, the following subsections. we investigate how the smooth CE interacts with the training dynamics of three widely used models: gradient boosting tree, kernel boosting in a reproducing kernel Hilbert space (RKHS), and two-layer neural networks. These models can all be interpreted on the basis of functional gradients, and our theoretical framework enables a unified understanding of their calibration behavior under different forms of regularization.
In this section, we express the empirical risk as Ln(g) and the functional gradient over the training dataset as VgLn(g) (V ( (a(g(X1)), Yi)). ...,, V Vglent (X)))),)), Y,)) E R..
E (on()()) Y.)
4.1 CASE STUDY I: GRADIENT BOOSTING TREE
Gradient boosting (Friedman, 2001) is a widely used method for constructing predictive models by iteratively adding base learners to minimize a loss function. It generates a sequence of functions F (T via the updates, for t O,.... T ((+)) (x) = (x) w./h
(4)
where w/ > is the stepsize and 3/2 approximates the functional gradient of the empirical loss (Mason al., 1999). Since using the exact functional gradient often leads to overfitting, ti is restricted to predefined function class V, which provides implicit regularization. We impose the following mild assumption on V, which is readily satisfied by common choices such as regression trees.
Assumption 1. The set of real-valued functions Y satisfies: for every vé E V, the negation - - also belongs V sup || S B for some B 1; and the constant function is included in V.
To obtain the update direction, we iteratively solve vi(() = arg mingew Lu (g we (())) Many boosting methods approximate this by quadratic upper bound, leading the squared loss
1b arg min Mw V () (2))))))
Mu, V Velent (o(x)))) Y.)
NEW
5

---

Published as a conference paper at ICLR 2026
where M is the smoothness parameter of the loss (e.g., M 1/4 for cross-entropy).
Although gradient boosting is often observed to be well calibrated in practice (Niculescu-Miz) & Caruana, 2005; Wenger et al., 2020), its theoretical guarantees remain less understood. Our framework provides a natural way to analyze this. Following prior analysis on boosting, we impose a standard margin assumption:
Assumption 2 (Telgarsky (2013)). Let A. = {g E R. E % 1} denote the n-dimensional probability simplex. Given a dataset St, = {(X,, / there exists 7 > 0 such that for every q E An, there exists v/ E y satisfying 2 (:Y; ()v(X,) 7B.
Here, 2Y; maps the binary label Y; E {0,1} to +1. This condition guarantees that for any weighted sample distribution E A., one can choose a base learner with nontrivial correlation the labels. Such margin assumptions are also standard in classification theory (Wei et al., 2018). Under this setup, we present our main result for the training dual smooth CE:
Theorem 3. Given Sur, under Assumptions and 2, if 2 with constant stepsize wt w, the averaged predictor g( E. ((t) satisfies
sm smCE' (gT),S) S BBTT
(g)
wB
87
Proof outline. By definition, the smooth CE bounded by the Ln norm of the functional gradient:
1 TE
smCE S.))
(g Y.) = V ((X)),
(5)
Under Assumption 2, this norm can be further bounded as
7B(4 (vr, V.) L2(S.) 8y
as shown in Lemma in Appendix F. The inner product (vh,, Vi) Lg(S.) is then bounded based on the standard convex optimization techniques. See Appendix F.3 for the complete proof.
Thus, choosing = ((I/VT) ensures that the training smooth CE converges to O at rate O(IVT))
Next, we establish guarantee for the population smooth CE by applying Theorem This requires specifying T to evaluate the complexity of F. We consider gradient boosting trees (Friedman, 2002; Hastie et al., 2005), where V is the class of binary regression trees. A binary regression tree of depth partitions the input space Ed into at most < 2m disjoint regions: Fd = U Ry, with Ry n R = 0 for j * k. Each region Ry is assigned a constant E IR, yielding a piecewise constant function: vo(x)) Σ/=rs (2ER,) with parameters 0 {cyz R The complete GBT algorithm is provided in Appendix F. Under these settings, obtain the following result:
Corollary 2. Under the same assumptions as Theorem 3, there exist universal constants {C; }s such that, with probability least 8 over the draw of Ser, we have
( ()) BuT
wBB.
C2
2m log nd
log (2g()
+
+
+ +CaUTT Vn
2
8y
We find that increasing the number of steps T reduces the training smooth CE, but also enlarges OwTT). This highlights trade-off between lowering training smooth CE and controlling model complexity. Corollary 3 shows that with appropriate hyperparameters, one can attain any target precision for the smooth CE.
the function class, as the Rademacher complexity grows
In addition, bounding the norm of the functional gradient provides a generalization guarantee for test accuracy (Nitanda Suzuki, 2018). For completeness, we include Appendix formal upper bound on the misclassification rate, P(x,y)=D(22 ()) 0).
Combining this with Theorem 2, we conclude that with suitable choices of T and n, both the smooth CE and the misclassification rate be controlled within any target precision c.

---

Published as a conference paper at ICLR 2026
Corollary 3. Under assumptions in Corollary for any 0, if the hyperparameteers satisfy:
T == -
22
then, with probability at least 1 8. the averaged predictor g satisfies sm CE ( S
and - 1)g (X) - 0]
Here, (2.)) hides logarithmic factors in the big-S? notation. Corollary 3 shows that e-smooth CE and e-classification error be achieved with (1/e²) iterations of GBT. To the best of our knowledge, this is the first theoretical analysis of GBT's that jointly accounts for both test accuracy and smooth CE. We complement theory with numerical experiments in Appendix K, which examine how the number of iterations and training sample size affect smooth CE and prediction accuracy.
4.2 CASE STUDY II: KERNEL BOOSTING
We next consider kernel boosting (Wei et al., 2017), where the functional gradient approximated by functions in an RKHS. Let (H, (:, :)) ) be an RKHS associated with the kernel k X x X' - R. The functional gradient over the training dataset approximated as
LVgLL(g)) | o (0)llm
(g
arg de 1ell
L2(S,)
where T& La = 1 Ei= (X,,, vV gflent (o
(o (x))), Vi)) is the empirical kernel operator. In kernel boosting, we set he = - To 5 (g in Eq. (4) and use the update rule:
g(++1) ( w; TVV In
To analyze this, we introduce the following normalized margin assumption: Assumption 3. Given dataset Sup there exists a function H and constant 7 > 0 such that for all (X,, Yi) E Sw. (2Y; - -2) ((X)) 2 %
This assumption is essentially equivalent to Assumption 2 in the GBT analysis. Setting g in As- sumption 2 as unit vector yields Assumption 3. Conversely, taking convex combinations of (2Y, - 1) x(X,) 2 in Assumption recovers Assumption
Under Assumption 3, the L1 norm of the functional gradient is bounded follows:
|| WVglenc Kll,, 1 n Σ
( YJ) < of
All proofs for this section are provided in Appendix G. Combining this with Eq. (5), we can control the smooth CE via I V (g)n( Using this relation, we obtain the following result.
Theorem 4. Suppose Assumption 3, supa,a'xx k(æ, x') S A, and (|g || S A' hold. When using
the constant stepsize wi = w which satisfies w < 4/A, the average function g( = -TT (t) satisfies
(T)) smCE T) Sw)) S - - [
(g)))())
TT
Additionally, there exist universal constants {Ci}s such that with probability at least 1 8 over the draw of Su. we have:
(P( ), 2
Ln(g(U)) wT
C2 CC(N'N+ 2L
A
log
2
n
Although covering number bounds require assumptions on kernel eigenvalue decay, here we use the Rademacher complexity bound from Theorem 2, which yields simpler result.
We observe that increasing the number of steps decreases the training smooth CE but simultaneously enlarges the function class, since the Rademacher complexity of predictors (the third term the
7

---

Published as a conference paper at ICLR 2026
right- side) grows with the norm of g rate O(VuT). This highlights trade-off between reducing training smooth CE and controlling model complexity.
Since the norm of the functional gradient also upper bounds the misclassification rate, show-analogous to Corollary 3-that suitable hyperparameter choices guarantee any target precision for both the smooth CE and the misclassification rate.
Corollary 4. Suppose assumptions in Theorem 4 hold. For any > 0, if the hyperparameeters satisfy:
T=Q(7= -0007-2 c))
w = 2 n '2 26-)))))
then, with probability at least the average of function g satisfies sm (mC S
and Pxx.))-(((2-1)gg (x) Σ 0] c.
Corollary 4 establishes that both c-smooth CE and c-classification error can be achieved using O(1/c²) iterations of kernel boosting. This result grounded in the observation that bounding the functional gradient norm leads to a small smooth CE and misclassification rate.
4.3 CASE STUDY III: TWO-LAYER NEURAL NETWORK
The next example is the two-layer neural network (NN). While NNs are typically trained by gradient descent their parameters, recent work (Nitanda et al., 2019) shows that under certain hyperparam- eter settings- such as output scaling and a sufficiently large number of neurons two-layer NNs behave similarly to kernel boosting with the neural tangent kernel (NTK).
We adopt the setting of Nitanda et al. (2019). Define the logit function : :X' - R by two-layer 0 is the number of hidden units, B E [0, is scaling exponent, and Ø R + R. is a smooth activation function (e.g.. sigmoid, tanh). The weights { {-1, 13th are fixed, while the parameters 0 } with 0, Rd are updated via gradient descent: ((++1) (1t) V. Lo (gg(s)) with constant stepsize w O.
NN go (z: vy _x=1 ar (0, x)), where
Jm
We now give an informal statement of Theorem 2 from Nitanda et al. (2019), which provides
guarantees for the functional gradient. Assume: (1) the activation function is smooth; (2) the initial parameters are sampled from sub-Gaussian distribution; (3) the "TK-transffrmed data are separable with margin y; (4) the stepsize sufficiently small; and (5) the number of hidden units m is large enough. Then, for T < Ks there exist constants K1. K2, and K3 such that, for all 3 E [0, 1]. with probability at least -"8 over the random initialization, the following bound holds:
K1 72
Σ
| Veneet (gows (X),
Y) 1I
+ K2²
(6)
W
t=
See Appendix for the formal statement. Then, similar Theorem 4, we have
SmCE (g Sw.) K1
m23-1
min SmCE" S.,) S 1E(0....T-11
Σ t=0
+ K2
T
V
2T
w
Combining the Rademacher complexity estimate of Nitanda et al. (2019) with Theorem 2, we derive upper bounds on the population smooth CE and misclassification rate, analogous to the kernel boosting setting (see Appendix H for details). As Theorem 4, the bound reveals trade-off T: increasing T reduces the training smooth CE but enlarges the complexity term, which grows rate O(VuT). Similar to Corollary 4, we further show that with suitable hyperparameters, both e-shooth CE and e-classification error can be guaranteed.
Corollary 5 (Informal). Suppose the same assumptions as those for Eq.. (6) hold. for any 0. the hyperparameters satisfy one of the following:
(i) 9 E [0, 1), 2 (ii) 3 - 0, m = ( 2 3/2 log(1/))). T 0 (2---11-1 log" (1/e)). w O(m 1) 5i( 2).
) 50 -4)
then with probability at least 1 - 8, gradient descent with the stepsize w finds a parameter g(t) satisfying (nCE(a((ggr)) S.) and F(x,y)~D 1(2Y 1)gmce (X) < 0] within T iterations.
See Appendix H for the formal statement with explicit constants. This result shows that both e-smooth CE and e-classification error be achieved within ((1/e) or O(1/c) iterations, assuming the
8

---

Published as a conference paper at ICLR 2026
-rantransf data are separable with margin y. Between the two hyperparameter settings, (ii) attains the same error target with fewer iterations T by increasing the number of hidden units m, and further yields improved complexity compared with Corollary 4 for kernel boosting. Appendix K provides empirical results illustrating how smooth CE and accuracy vary with 7 and n.
5 RELATED WORK
Various metrics have been proposed to quantify deviations from perfect calibration, including ECE (Guo et al., 2017; Rahaman et al., 2021; Minderer et al., 2021). The binning ECE has been widely used estimate the conditional expectation [[ in the ECE, which partitions the prob- ability interval into discrete bins. Despite its popularity, binning ECE is sensitive to hyperparameters such as the number of bins, and it lacks both consistency and smoothness
distance metric (Kumar et al., 2019; Nixon et al., 2019; Minderer et al., 2021). A broader comparison of ECE variants is given by Gruber & Buettner (2022). Blasiok et al. (2023) systematically studied calibration distances and formalized the true distance from calibration as a rigorous notion of deviation from perfect calibration. As an efficiently estimable surrogate, they proposed the smooth CE, building on Foster Hart (2018); Kakade & Foster (2008). More recently, Hu et al. (2024) showed that smooth CE can be efficiently evaluated in practice. Importantly, Blasiok et al. (2023) proved that smooth CE provides both upper and lower bounds binning ECE, making it a theoretically sound proxy. Hence, the results established here for smooth CE also yield implications for binning ECE; see Appendix B for details.
To achieve a well-calibrated prediction with a theoretical guarantee, many prior works focus on recalibration, such as binning-based recalibration methods (Gupta al., 2020; Gupta & Ramdas, 2021; Kumar et al., 2019; Sun et al., 2023; Futami & Fujisawa, 2024). However, it has been reported that such post-procet pos--prcesssig loses the sharpness of the prediction, which sometimes leads to accuracy degradation (Kumar et al., 2018: Karandikar et al., 2021; Popordanoska et al., 2022; Marx et al., 2023; Kuleshov & Liang, 2015). To theoretically guarantee the calibration, our analysis takes a different perspective. We provide guarantees for the smooth CF without relying on such post-processing approach similar to recalibration. This is achieved by combining a uniform convergence bound and a functional gradient characterization of the training smooth CE. Then, our analysis simultancously guarantees both the smooth CE and accuracy for several practical algorithms.
Prior work has connected the post-processing gap to the population smooth CE (Blasiok et al., 2023; Blasiok et al., 2023), making it less applicable to algorithms trained on finite datasets. Similarly, although Gruber & Buettner (2022) discussed post-processing, their approach faces the same limita- tion. In contrast, our analysis directly targets the smooth CE from finite data. From a generalization perspective, Futami & Fujisawa (2024) developed gggorthmm-dependen bounds for binning ECE using information-theorele techniques. By contrast, we derive a uniform convergence bound for smooth CE, which applies more broadly beyond binning. Moreover, their generalization bound for ECE converges at a rate Olog n/n' 1/3), which is slower than rate. We conjecture that this slower convergence arises from the nonparametric estimation of conditional probabilities via binning, whereas smooth CE avoids such estimation and hyperparameter dependence. Finally, their results focus only on the generalization gap and do not address when the training ECE itself becomes small.
Although in recent studies, new boosting algorithms have been proposed improve various notions of calibration (Hebert-Johnson et al., 2018; -arbuss et al., 2023), our analysis provides a theoretical explanation for why existing gradient boosting already yields strong calibration perfor- mance. Unlike prior works on boosting, which primarily focus on accuracy on the basis of functional gradients (Zhang & Yu, 2005; Nitanda Suzuki, 2018; Nitanda et al., 2019), we leverage functional gradients to analyze calibration, offering a novel perspective on the behavior of these algorithms in calibration. While our analysis assumes constant stepsize, the choice of stepsize in boosting is crucial for achieving better performance (Telgarsky, 2013). Extending our calibration analysis beyond the constant stepsize setting is an ammorttan important direction for future work.
In several works, the post-processing has been highlighted in achieving advanced calibration objec- tives, such as multicalibration Hlebert-Johnson et al., 2018; Hansen et al., 2024; Blasiok et al., 2023; Globus-Harte et al., 2023). Whereas our analysis focuses smooth CE, this metric is closely related to these variants of CE from the viewpoint of lew-ee calibration (Gopalan et al., 2022). We believe findings may offer new insights into these metrics, which we leave for future exploration.

---

Published as a conference paper at ICLR 2026
6 CONCLUSION AND LIMITATION
This work presented the first rigorous guarantees on the smooth CE for several widely used learning algorithms. Our analysis proceeds in two stages: we first derive uniform convergence bound for the smooth CE, and then upper-bound the training smooth CE via functional gradients. We demonstrate that algorithms that can control the functional gradient simultaneously achieve small smooth CE and misclassification rate. Despite these contributions, several limitations remain. First, our bounds are derived using uniform bound over the post-processing function h, not the Lipschitz function class, which may result in loose estimates. More refined analyses that better align with practical performance would valuable. Moreover, our analysis relies on a strong margin assumption, which requires well-separated data distribution. Since calibration is rather weak notion compared with accuracy, extending the analysis to more realistic and weaker conditions is an important direction for future work. Finally, analysis is limited to binary classification the smooth CE is designed for this setting. Extending our analysis to the multiclass setting should be explored in future work.
REPRODUCIBILITY STATEMENT
This paper is primarily theoretical, and all technical details and complete proof' of our results are provided in the Appendix. In addition, for the supplementary experimental analyses presented in the Appendix, we provide the corresponding source code in the Supplementary Material to facilitate reproducibility.
ACKNOWLEDGEMEN'S
This work was supported by Japan Science and Technology Agency (JST) as part of Adopting Sustainable Partnerships for Innovative Research Ecosystem (ASPIRE). Grant Number JPMJAP25B1. FF was supported by IST, PRESTO Grant Number JPMJPR22C8, Japan. This research is supported by the National Research Foundation, Singapore, Infocomm Media Development Authority under its Trust Tech Funding Initiative, and the Ministry Digital Development and Information under the AI Visiting Professorship Programme (award number AIVP-2024-004). Any opinions, findings and conclusions or recommendations expressed in this material are those the author(s) and do not reflect the views of National Research Foundation, Singapore, Infocomm Media Development Authority, and the Ministry of Digital Development and Information.
REFERENCES
Ambroladze, A. and Shawe-Taylor, J. Complexity of pattern classes and lipschitz property. In International Conference on Algorithmic Learning Theory, pp. 181-193. Springer, 2004.
Arrieta-lbarra, I., Gujral, P., Tannen, J., Tygert, M., and Xu, C. Metries of calibration for probabilistic predictions. Journal of Machine Learning Research, 23(351): 2022.
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 2002.
Blasiok, J.. Gopalan, P., Hu, L., Kalai, A. T., and Nakkiran, P. Loss minimization yields multicalibra- tion for large neural networks. arXiv preprint arXiv:2304.09422 2023.
Blasiok, J., Gopalan, P., Hu, L., and Nakkiran, P. unifying theory distance from calibration. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pp. 1727-1740, 2023.
Blasiok, J., Gopalan, P., Hu, L., and Nakkiran, P. When does optimizing proper loss yield calibration? In Thirty-seventh Conference on Neural Information Processing Systems, 2023,
Boucheron, S., Lugosi, G., and Massart, P. Concentration Inequalities: A Nonasymptotic Theory of
Independence. Oxford University Press, 02 2013.
Bubeck. S. et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-3577 2015.
10

---

Published as a conference paper at ICLR 2026
Buja, A., Stuetzle, W., and Shen, Y. Loss functions for binary class probability estimation and classification: Structure and applications. Working draft. November, 3:13, 2005.
Dawid, A. P. The well-calibrated Bayesian. Journal the American Statistical Association, 77(379): 605-610, 1982. doi: 10.1000011621499.1992... 198.1797755....
Foster, D. and Hart, S. Smooth calibration, leaky forecasts, finite recall, and nash dynamics. Games and Economic Behavior, 109:271-293, 2018.
Foster, D. P. and Vohra, R. V. Asymptotic calibration. Biometrika, 85(2):379-390, 1998.
Friedman, J. Н. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1189 1232, 2001. doi: 10. 211214/0x/10013203551 URL https://dol org/
1.0.1214 /ata///////////////
Friedman, J. H. Stochastic gradient boosting. 367-378, 2002.
Computational statistics & data analysis, 38(4):
Fujisawa, M. and Futami, PAC-Bayes analysis for recalibration in classification. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., Berkenkamp, F., Maharaj, T., Wagstaff. K., and Zhu, J. (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 17986-18023, PMLR, 13-19 Jul 2025.
Futami, and Fujisawa, M. Informatiion-heoreet generalization analysis for expected calibration error. In Globerson, A., Mackey, I.., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and Zhang, C. Advances Neural Information Processing Systems, volume 37, pp. 84246-84297 Curran Associates, Inc., 2024.
Hlobus-Harris, I., Harrison, D., Kearns, M., Roth, A., and Sorrell, J. Multicalibration as boosting for regression. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 11459-11444 1492. PMLR, 23-29 Jul 2023.
Gneiting, T. and Raftery, A. E. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-378 2007. doi: 10.1198/016214556000000
Gopalan, P., Kim, M. P., Singhal, M. A., and Zhao, S. Low-degree multicalibration. In Conference on Learning Theory, pp. 3193-3234. PMLR, 2022.
Gruber, S. and Buettner, F. Better uncertainty calibration via proper scores for classification and beyond. Advances Neural Information Processing Systems, 35:8618-8632, 2022.
Gruber, S. G. and Bach, F. R. Optimizing estimators of squared calibration errors in classification. Transactions on Machine Learning Research, 2025. ISSN 2835-8856.
Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. On calibration of modern neural networks. In International conference on machine learning, pp. 1321 1330, 2017.
Gupta, C. and Ramdas, A. Distribution-Fii calibration guarantees for histogram binning without sample splitting. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3942-39522 PMLR, 18-24 Jul 2021.
Gupta, C., Podkopaev, A., and Ramdas, A. Distribution-fres binary classification: prediction sets, confidence intervals and calibration. Advances in Neural Information Processing Systems, 33: 3711-3723, 2020.
Hansen, D., Devic, S., Nakkiran, P., and Sharan, When is multicalibration post-processing necessary? arXiv preprint arXiv:2406.0644 2024.
Hastie, T., Tibshirani, R., Friedman, J., and Franklin, J. The elements of statistical learning: data mining, inference and prediction. The Mathematical Intelligencer, 27(2):83-83 85, 2005.

---

Published as a conference paper at ICLR 2026
Hebert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. Multicalibration: Calibration for the (Computationally iddnlifiaiitttile masses. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1939-1948. PMLR, 10-15 Jul 2018.
Hu, L., Jambulapati, A., Tian, K., and Yang, C. Testing calibration in nearly-linear time. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Jiang, X., Osl, M., Kim, J., and Ohno-Machado, L. Calibrating predictive model estimates to support personalized medicine. Journal of the American Medical Informatics Association, 19(2):263-274 2012.
Kakade, S. M. and Foster, P. P. Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences, 74(1): 2008
Karandikar, A., Cain, N., Tran, D., Lakshmmnaraaanaan B., Shlens, J., Mozer, M. C., and Roelofs, B. Soft calibration objectives for neural networks, Advances in Neural Information Processing Systems, 34:29768-29779, 2021.
Klusowski, M. and Tian, M. Large scale prediction with decision trees. Journal of the American Statistical Association, 119(555)5525-537, 2024.
Kuleshov, V. and Liang, P. Calibrated structured prediction. In Advances in Neural Information Processing Systems, volume 28. pp. 3474-3482, 2015.
Kull, M., Perello Nieto, M., Kängsepp, M., Silva Filho, T., Song, H., and Flach, P. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration. In Wallach, H.. Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Kumar, A., Sarawagi. S., and Jain, U. Trainable calibration measures for neural networks from kernel mean embeddings. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp- 2814. PMLR, 10-15 Jul 2018.
Kumar, A., Liang, P. S., and Ma, T. Verified uncertainty calibration. Advances in Neural Information Processing Systems, 32:3792-3803, 2019.
Lee, D.. Huang, X., Hassani, H., and Dobriban, E. T-cal: An optimal test for the calibration of predictive models. Journal of Machine Learning Research, 24 2023.
Luenberger, D. G. Optimization by vector space methods. John Wiley & Sons, 1997.
Luxburg, U. v. and Bousquet, O. Distance-based classification with lipschitz functions. Journal of Machine Learning Research, 5(Jun):669 695, 2004.
Marx, C., Zalouk, S., and Ermon, S. Calibration by distribution matching: Trainable kernel calibration metrics. Advances Neural Information Processing Systems, 06:25910-25922 2023.
Mason, L., Baxter, Bartlett, P., and Frean, M. Boosting algorithms as gradient descent. Advances in neural information processing systems, 12, 1999.
Minderer, M., Djolonga, J., Romijnders, R., Hubis, F., Zhai, X., Houlsby, N., Tran, D., and Lucic, M.
Revisiting the calibration of modern neural networks. Advances in neural information processing systems, 34:1 1 166241 2021.
Mohri, M., Rostamizadeh, A., and Talwalkar, Foundations of Machine Learning. The MIT Press, 2nd edition, 2018. ISBN 0262039400.
Murphy, A. H. and Winkler, R. L. Probability forecasting in meteorology. Journal of the American Statistical Association, 79(387):489-500, 1984.
12

---

Published as a conference paper at ICLR 2026
Nguyen, K. and O'Connor, B. Posterior calibration and exploratory analysis for natural language processing models. In Marquez. L., Callison-Burnii C., and Su, J. (eds.), Proceedings of the 2015 Conference Empirical Methods in Natural Language Processing, pp. 1587-1598, Lisbon, Por- tugal, September 2015. Association for Computational Linguistics. doi: 10. 10.18653/1/D15-1111
Niculescu-Mizil, A. and Caruana, R. Obtaining calibrated probabilities from boosting. In UAI, volume 5, pp. 413-20, 2005.
Nitanda, and Suzuki, Functional gradient boosting based on residual network perception. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference Machine Learning, volume of Proceedings of Machine Learning Research, pp. 38 3819-3828, PMLR, 10-15 Jul 2018. URL https: http::::/pppoceeeeee http://poceeddnggee
mlr. wrwssppssp/pe.pp.p / v80 wwt.aninaaaaaaaan html.
Nitanda, A., Chinot, G., and Suzuki, T. Gradient descent learn less pee-pearaeteriized two-layer 2019.
neural networks on classification problems. arXiv preprinl
Nixon, J., Dusenberry, M. W., Zhang, L., Jerfel, G., and Tran, D. Measuring calibration in deep learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 2019.
Popordanoska, T., Sayer, R., and Blaschko, M. A consistent and differentiable lp canonical calibration сrror estimator. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 7933-7946. Curran Associates, Inc., 2022.
Rahaman, R. et al. Uncertainty quantification and deep ensembles. Advances in neural information processing systems, 34:20063-20075, 2021.
Schervish, M. J. general method for comparing probability assessors. The annals of statistics, 17 (4):1856-187,, 1989.
Sun, Z., Song, D., and Hero, A. Minimum-risk recalibration of classifiers. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Telgarsky, M. Margins, shrinkage, and boosting. In International Conference on Machine Learning, pp. 307-315. PMLR, 2013.
Wainwright, M. High- Biggh-Dimessooall Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Wei, C., Lee, J., Liu, Q., and Ma, T. On the margin theory of feedforward neural networks. 2018.
Wei, Y., Yang, F., and Wainwright, M. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. Advances in Neural Information Processing Systems, 30, 2017.
Wenger. J., Kjellström, H., and Triebel, R. Non-parametric calibration for classification. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 178-190. PMLR, 2020.
Zadrozny, B. and Elkan, C. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. In Icml, volume I, pp. 609-616, 2001.
Zhang. T. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023.
Zhang. and Yu, B. Boosting with early stopping: Convergence and consistency. Annals of Statis- tics, 33:1538-1579 2005. URL https:/ /api. semant i ccsccholaa ar org/ CorpusiI: 13158356.
13

---

Published as a conference paper at ICLR 2026
A ADDITIONAL FACTS ABOUT PROPER LOSSES
Here, we describe the general form of a proper loss function and its relation to the post-processing gap. Given proper loss function f, it can always be represented in terms of convex function as follows:
((p. -pp) Vo(p) (y ()p)), p),
where Φ: [0, 1] + R is convex function and Vp(p) denotes subgradient at This representation known as the Savage representation (Gneiting Raftery, 2007). Blasiok al. (2023) further showed that, in the binary case, the subgradient satisfies Vo(p) E(p, 0) {(p, 1), and referred to Vo(p) as the dual of (dual(p)). Hereinafter, we assume that Φ is differentiable, since the convex functions corresponding to commonly used losses such as the squared loss and the log loss are differentiable.
Table I: Savage representations for the cross-entropy Loss and squared loss
cross-entropy Loss
Squared Loss
{(p,y) y)
-y -ylup (1 y) In p)
p)
((2)
plup + p) I pp)
p(p
dual(p)
In
2p
1
0,
-1
(ss)
In(1 + e*)
(s+1)²
-1
8,
8>1
- ys,
8<-1
(s.
In(1 + ((1++e)--y) y.5
(v
(s + 1)/2)²
-15
y)8,
t>
0, 8<-1
(s Vs)(
s+1
-158<1
Ite
2
1, 8>1
We define the convex conjugate of a function (pp) as follows: for all 8 E R,
(ss) sup pE[0.1]
{s p-- <(p)),
where si is a convex function. We refer to s as a score, as will be explained later. Using this notation, define the dual loss god Rxy R as
e (s, = (8)) -
The score is linked to the probability p via the dual mapping dual(p) = Vo(p) = Op, ((p 1). By Fenchel-Young duality, this relationship is inverted as Vel(s), which we also denote as
p = pred (s).
With these definitions, the proper loss can be equivalently written as
f(p. y) = (dual(p) y) = (ddual(p)) - dual(p)
For details and proofs, see Blasiok al. (2023). We summarize the key properties of these expressions in Table 1.
Similarly, can define the dual post-processing gap for the proper scoring rule (Blasiok et al., 2023):
Definition 3 (Dual-post processing gap). Assume that V a differentiable and convex function with derivative (t) E [0, for all t H. Assume that y is X smooth function. Given s, C g X + IR, and D, we define the dual post-processing gap as
(o) D) = EEe (o(X),Y)
inf heLip, (R. 1/AA1A/)
(g(X) + -(g(x))),
14

---

Published as a conference paper at ICLR 2026
When considering the cross-entropy loss, this dual post-processing gap corresponds improving the logit function.
Definition (Dual smooth calibration). Consider the same setting as the definition of the dual-post processing gap. Given and 9, define f(-) Vvb(g())). We then define the dual calibration error of g as
(
sup (R.
Bn(g(X)) -X(x)
Then, similarly the relationship between the smooth ECE and the post-processing gap, the following holds: if vb is a A-smooth function, then we have
Sm () 22 A / (g, (), smCE(e.A)gg D)
and
smCE(J,D) SmCF
holds.
In the case of the cross-cntropy loss, we have (bss) = log(1 + e*). which is 1/4-smooth. For the squared loss, v is 1/2-smooth. Therefore, the dual smooth calibration and the smooth calibration are essentially equivalent in both cases. We remark that the optimality of the constants appearing in smooth CE in Eq. (1) and dual smooth CE in Eq. (2) is discussed in Appendix D of Blasiok et al. (2023).
B DISCUSSION ABOUT CALIBRATION METRICS
Here, we introduce several definitions of calibration metrics and their relationship to the smooth CE, which is the primary focus of our paper.
B. TRUE DISTANCE CALIBRATION AND SMOOTH CE
Given distribution D and predictor f. we consider the distribution induced by f. which is the joint distribution of prediction-labe pairs (f(z), y) E [0, 1] x {0,1), denoted by Dy-
Definition 5 (Perfect calibration (Blasiok et al., 2023)). We say that prediction-laie labell distribution T over [0, 1] {0, 1) is perfectly calibrated if (n [y vo] v. Moreover, given D over X {0, 1}. suy that I is perfectly calibrated with respect to D if D is perfectly calibrated.
We denote the set of perfectly calibrated predictors with respect to D by cal(D).
Next, we introduce the true calibration distance, defined as the distance to the closest calibrated predictor:
Definition 6 (True calibration distance). The true distance of predictor from calibration is defined as
aCEp(S) = inf gEcal(D)
-
This is the l metric, which possesses many desirable properties for measuring calibration; see Blasiok et al. (2023) for details. However, not practically usable because cal(D) may be non-convex, and the metric depends on the domain X,, whereas calibration metrics typically depend only μ(D, f))
Blasiok et al. (2023) proposed that any calibration metric should satisfy the following three criteria:
(i) Prediction-only access A calibration metric should depend only on the distribution over (f(x).y) D,, and not on the distribution over X. If it meets this requirement, calibration metric satisfies the Prediction-only access (PA) property. Note that the true calibration distance depends on (ar, (x) y) and is therefore called the sample access (SA) model.
say that
15

---

Published as a conference paper at ICLR 2026
(ii) Consistency
Definition 7. For >> O, calibration metric is said to satisfy c-robust completeness if there exists constant such that for every distribution on X x {0.1}, and predictor f FF
((D,)) (dCFp(()))
Definition 8. For s > O, calibration metric μt satisfies s-robust soundness, if there exists a constant b 2 0 such that for every distribution on X {0, [0,1), and predictor f F,
(D, b (dCFE
Definition 9.
A calibration metric is said be (consscont if it satisfies both e-robust completeness and s-robust soundness.
Thus, consistent calibration metrics are polynomially related the true distance from calibration. Blasiok et al. (2023) showed that any PA model must satisfy s/c 2.
(iii) Efficiency A calibration metric μ said to be efficient if it can be computed accuracy in time poly(1/e) using poly(1/e) random samples from Dj-
Blasiok al. (2023) showed that the smooth CE satisfies all of these properties. particular, with respect to consistency, the smooth CE satisfies
smCE(f, dCEp(f) S 44/42mC((f D)
dCEp (f) smCE(S D) s dCEp(J) 32
which means that the smooth CE is (c 1, 2) consissenn and achieves 8/c 2.
B.2 ECE AND BINNING ESTIMATOR
Recall the definition of the expected calibration error (ECE):
ECEx(f) = E [[[(]]((X) - f(X)].
The binning estimator is commonly used approximate this. Given partition I= . of [0, into intervals, we define:
binnedECE,, (T,Z) =
-VV 1,]l-
jE(m)
has been shown in Lemma 4.7 of Blasiok al. (2023) that
dCFp(J) S ECED(()
demonstrating robust soundness. However, ECE does not satisfy robust completeness; Blasiok et al. (2023) proved (Lemma 4.8) that for any e R+ there exists distribution D such that dCEp < but (f) 2 1/2 This also highlights the discontinuity of ECE, which hinders its estimation from finite samples.
Blasiok et al. (2023) showed that by accounting for bin widths, the binning ECE satisfies consistency: intCE(J) == min(binnedECE, (T))
where
(I Σ (EVYY-)j((T)11V eI)
jElm]
and w(L) denotes the width of interval 4.
Then, the following holds (Theorem 6.3 in Blasiok et al. (2023)):
dCEp(f) < inCC((f) s 4 (CC)(((f
16

---

Published as a conference paper at ICLR 2026
Thus, intCE satisfies (1/2, connsistenn. Btasiok et al. (2023) also provided estimator for inICE(T).
As have seen, bounding the smooth CE leads to bound on dCEp(f), which in turn bounds in(CE(f) optimized estimator for the binned ECE.
Finally, remark that since f v) is continuous, we relate the ECE and the smooth CE as follows:
Theorem 5. Suppose that [B If z] satisfies L-Lipschitz continuity. Then the following relation holds:
Sm < ECEp(f) - (1+ ()) (s)
Thus, controlling the smooth CE also leads to controlling the ECE when the underlying conditional probability function is continuous.
Proof. We first prove the following inequality:
ECEp(f) < binnedECE (T, + (1 + L)wr (I).
(7)
This can be derived using Lemma in Futami Fujisawa (2024). For completeness, we outline the key steps of the analysis below:
ECED(() = | = vi -
Vi Σ P(V E A = -] VIIV e I.]
m
P(V E I.) - e I.]
EVVVV
4VIV e 41
P(V e L)E - B/YIV e 4|IlV e I.)
P(V E LE e E - BIVV E AJIlV e A.
P(V E LEVVV e LJ VIV e I.).
As for the second term, is evident that
Σ P(V E L)EJEY [J]-E[VIV e 4 binnedECE, (T,
A
and as for the third term,
Σ P(V VE - e B[w([)]ver]]= w(T).
Finally, the first term be bounded by using the Lipschitz continuity,
P(V E E - E e 1.IlV e T,]
P(V E E -
-Y EY
e 4
m
P(V e EE V 4JllV 4]
<
P(V E LEIVV - EVV e 41IlV E 4 S Lw(())
17

---

Published as a conference paper at ICLR 2026
where
Vi Σ Vn, lver Σ 1=1
BIVIV 4:]
lven.
1=1
The term || E LJIIV [.] holds by the definition of conditional expectation. Thus, we have established Eq. (7).
Next, we consider taking the infimum over all partitions I. By combining Claim 6.6 and Lemma 6.7 in Blasiok et al. (2023) and Eq. (7), we obtain:
ECEp(f) s (1 2/e)dCEp(f) (1 + L)e
where dfEp(f) denotes the lower calibration distance (see Blasiok et al. (2023) for the formal definition), and > is an arbitrary width parameter. By setting V I+L df) and using the fact that dCEp(J) s 2smCE(f; D) from Theorem 7.3 in Blasiok et al. (2023), obtain the desired result.
[
We remark that if the underlying conditional distribution satisfies a continuity condition, then the ECE becomes a consistent calibration metric.
B.3 OTHER METRICS
As discussed in Blasiok et al. (2023) and Gopalan et al. (2022), the smooth CE is special case of the weighted calibration error introduced by Gopalan et al. (2022).
Definition 10 (Weighted Calibration Error). Let M be class of functions [0, 1] + R. The calibration error relative to .M is defined as
CE) = sup E [[((f(X)) (Y f(X))] sup (h(f(X)), ( -f(X)) L2(D) hEM
hEM
In this view, the smooth CE corresponds to smCE(f, CEp Lip, (10, (),,)).
For the dual smooth CE, the inverse of the sigmoid function is o (0(()) log( (1 z)). When g(x) o - (f()), we have:
smCE (g. D) (B-
Another important function class is the RKHS H. associated with positive definite kernel k. This space is equipped with the feature map & > H. satisfying (h, Φ(v)) = h(v). The associated
kernel k R x R I defined by k(u, v) (ő(u), ((v))
Let Hi == (h E H H|llH & 1}. We define the kernel calibration error as CEp (ʃ, Hi).
Given samples ((11,1),. ... (Uns Un))} where e; f(xa), the kernel CE under finite samples is defined as
CE Σ (y: - v.)A(u,, v,) vz).
n
i.j
This was first proposed by Kumar et al. (2018) as the maximum mean calibration error (MMCE).
key kernel the Laplace (exponential) kernel (u, v) exp(- lu ul). for which has been shown that
SmCE(f,D) S CEp(f.HH)
On the other hand, the Gaussian kernel does not upper bound the smooth CE and has several limitations; see Blasiok et al. (2023) for details.
We numerically evaluate the behavior of MMCE with the Laplace kernel and smooth CE Ap- pendix K.
18

---

Published as a conference paper at ICLR 2026
C PROOF OF SECTION 3
C.I PROOF OF THEOREM 1
Before the formal proof, we provide proof sketch to highlight the key differences from standard generalization bounds as in Mohri al. (2018); Wainwright (2019).
First, we reformulate the smooth CE as linear convex optimization (Hu et al., 2024): let v; = fx,,
and w (w1,... ( E R Then smCE(J, = max_ Σ²= (y: - it Jws/n subject to the constraints |4m|| - 1, Vi, and |a wyl S Ma Uzl. vi Let w" denote one such solution, and we define ()) = (y: uz) Then, we express ((f,S)=
o(f.2))
Although our analysis follows the structure of classical generalization bounds, the dependence among (+([,=)))= induced by w" through the optimization precludes the use of standard concentration inequalities based on independence. Instead of Hoeffding's inequality, we use the bounded difference inequality to show su [ Ste) - o(f, S.ffSSu. Su)l s S., SE | Ste) o(S, S.r) +
/log6-1/n. This requires studying the stability of the above convex problem.
We would like to apply symmetrization argument using ii.d. Rademacher variables d; E #1 and evaluate S. EE sup :h >'= o [ø( Z!) - off, Z.)l. However, this technique is not directly applicable in our setting due to dependencies among the terms {Ø(S, 2)))=
To address this, we introduce (a,)s in way that preserves the structure of the linear convex formulation smooth CE. Since the resulting bound does not take the form of standard Rademacher complexity, we discretize the hypothesis class JF and derive covering number bound.
Proof. We begin by leveraging the reformulation of the smooth CE as a linear program introduced by Blasiok et al. (2023) (Theorem 7. 7.). Given a dataset S = {(T,, y/) } and defining vi = (x;)) it is known that the smooth CE on S corresponds the optimal value of the following optimization problem:
1
smCE(f,S) = max fwr ==1
Σ(vs (v: v2)wi
(8)
subject the constraints:
-1 -1 w < 1, Vi, | - wiyl S 10 05ys Vi,j-
Note that this optimization problem a linear optimization problem in n variables, and its feasible region is bounded (and closed) in RR.. Therefore the existence of an optimal solution follows directly from standard results in analysis, that a continuous function on compact set attains its maximum and minimum. Note that the optimal solution is not necessarily unique. Nevertheless, given function f and dataset S, the value smCE(ff S) is uniquely determined. Let w, denote one such optimal solution. Then, we can write:
1 sm SmCE(f,S)
12 >506
(1/ ve)w
Σ (f,+))
where 2; = (xi, v:). We denote smCE(f, ((f, and smCE Stc) =
(lf, Sto).
As discussed above, although the optimizer wt may not be unique, the value smCE(f, is uniquely determined for fixed f and dataset S. Therefore, the uniform upper bound on the smooth CE can be controlled via the supremum over f when the training and test datasets are fixed. We thus focus on the following inequality:
|smCE(J, Ste) smCE(f, < sup (o ((ff
/EF
Following the standard approach in uniform convergence analysis, we derive the convergence in expectation follows:
19

---

Published as a conference paper at ICLR 2026
Lemma 1. Under the same setting as Theorem 1, with probability - 6, we have
log
sup
S()) - Sw)) S Si sup lo(f. Ste) - - +(f) + +21 JEF
FEF
The proof of this lemma is provided in Appedix C.2. Note that this not a consequence of Hoeffding's inequality, since - Σ off.z,
off = Σ (u
- v.)
and thus the terms o(f, zi) are dependent through w/, which is solution of the linear program in Eq. (8). Since there are dependent variables (ff,z), Hoeffding's inequality, which requires independence, is not applicable. To establish Lemma 1, we instead employ McDiarmid's inequality combined with bounded difference argument; see the proof in Appendix C.2.
Our proof proceeds in three steps: (1) we introduce Rademacher random variables, (2) we evaluate the exponential moment to control the empirical process induced by these variables, and (3) we refine the exponential moment bound via a chaining argument.
We introduce Rademacher random variables to control the empirical process in Lemma 1. Following standard generalization analysis, we aim to apply the symmetrization technique. However, the standard formulation
E (ts Eg sup Σ
[aross Z)) - 0, 2,)]
(9)
JEF i=1
is not suitable for Step (2), as it complicates the evaluation of the exponential moment. To understand this, let us explicitly express the uniform generalization gap as follows:
Su sup @(f, Ste) Φ(f. Sw:)
(10)
fer
1 n
12 (14 f(x\))al)
(SS D2 sup feF
max-
yt f(xx))w max
TI
n
sup min = =[(
[(:: - f(x))) -
(11)
JEF
71
Here, we used the reformulation of the smooth CE over the training dataset via a Lipschitz function. For simplicity, we omit the constraints of the linear program. We now introduce Rademacher variables and demonstrate the difficulty in evaluating the exponential moment.
To simplify the discussion, let us consider the case Eq. (9) under the expression of Eq. (10) written as:
2. For a fixed dataset S and function f.
E, max min T1 [(v1 - f(x1)) (ví f(11)) + 02 (122 f(z2)) - (1/2 f(x2)) Woy)
2
2
1
max mimmmnnyyy - f(ri))w) + (12 f(22)) (vi - f(z))) - (0/2 f(22))
8
+
max min(y) f(x [(11))w] - - - f(x))) (14 f(11))a( + (322 - f(r)))
8
&
+
max min - - f(x) ))n + (y2 - ((22)) + ( - f(x1))/( - (3' ((b)))
w/
+
max min - f(x1)) - (y2 - f(22)) + (o) - f(z1)) + (3/ 100--f(aa) f(a)))
8
/
This non-zero result indicates the challenge in applying exponential moment analysis for Step (2). In standard analysis, this type of expectation is typically zero, which enables the use tools such as Massart's ' lemma. Hence, the standard symmetrization technique fails in this setting.
20

---

1 Published as a conference paper at ICLR 2026
Therefore, must develop alternative symmetrization strategy. To illustrate the idea, begin by introducing only σi and consider the following expression:
Eq. (11)
(., Bor sup max min feF "
"
d
(yi (wx1)())))
Wi + - u/)
-(11 1(11)
11
1 01 +
Wl
"
2
2
2
2
+ n
(1n- f(;))) (1/- ((((MW
Here, d1 is Rademacher random variable. This equality holds because, when 01 1, the maxi- mization and minimization are unchanged; when σ -1, the roles of and wi1 are exchanged. However, since we are averaging over and S", and these datasets are ii.d., such swapping does not affect the distribution of the expectation. Therefore, the equality holds. This method of introducing Rademacher variables differs fundamentally from the standard symmetrization approach.
We then introduce i... Rademacher random variables {o, ) and consider the following expression:
Eq. (11)
((S., (( E. sup max min FEF w
w'
1 1-0i w/) - (11
(1
0:
)
(y: - f(x:)) oi
w; +
w/ +
w/
2
2
2
2
An important property is that for fixed f and dataset S, we have:
1 oi (v: ((x))
1 1 oi
1 1- BOWl w/
Eg max min
wi +
(12)
71
1 11 σ; w/ 2 w/ =0.
1 0,
(1/ f1/-f(x)))
This cancellation becomes evident in the case obtain
2: by expanding the left-hand side above,
max min(y1 - f(x1))w1 + (22 f(x2))((2)))))) (3i - f(x1)) (v/2 --((x))
4
+
max min(y - f(x)))/I + (3/2 (x/ - (11 - f(x))(())))))) - (12 f(x2))
4
w
w'
1
+
max manxmin(vi (Ví - f(x()))w + (32 f(x2)) - (y1 - f(x))) (1/2 f(zb))
4
+ max maniminyy (v( - f(a\)) + (w/ fab))) - (v1 - f(x))) - (12 f(x2))
4
0.
This is because the structure of the lincar convex problem ensures symmetric cancellation when Rademacher variables introduced. Therefore, proceed the analysis of the exponential moment of Step (2).
We define the integrated empirical process
R(F,Sn, == Er sup max min JEF
Σ
0:o(f. Zi, Zt),
1=1
where
1 1+0,
1- 0s w/
1
1 0i w
Hi, 27) (y: f(x;))
(
W/
(16- ((x!))
w/
2
2
21

---

Published as a conference paper at ICLR 2026
We now derive bound using variant of the Massart lemma (Mohri et al., 2018). For simplicity, assume the function class F has finite cardinality [F]. This will later replaced by a covering number. Then for all A > O, we have:
R(F, Sn, S²) = Ro sup max min fEF
Σ w' n
a.bss. 2,,
w
E8
log
Σ
exp
max min
a,ols Zi, 23)
FEF
1
log
Ber
exp
max min
oio(S, Zi, 21)
FEF
G , Zi, 2,) ))
1 $
log
[ Bo exp
max min
Since the expectation of the exponential term is 0 from Eq. (12), we apply McDiarmid's inequality: Lemma 2. Under the above setting, we have
Eg exp max min Σ aibls 2r (., (..
12
& exp
2n
The proof of this theorem is provided in Appendix C.3. Using this, we obtain
log F
A
S.)
+
2n
Optimizing over X, we find
2 2log F
R(F, S,, S
This is modified version of Massart's lemma since the left-hand side does not represent the classical Rademacher complexity.
Since F can be uncountable, apply discretization argument using the covering number. By the definition of the supremum, for any é' e R+ there exists f E F such that
n a.olf 2,, M7) E, n
Eg sup JEF n
Σ (f. Zi, 27) +
Here we present stronger result compared to the theorem presented in the main paper, based on the L2(S,) pseudometric, which is defined as:
| -
1 1r (L))s))
s(xi) P.
n
By the definition of the e-covering, for a given f F, there exists f E EN, L2(S2n)) such that
|| - SC.
We first derive the generalization bound using the (2(),) pseudometric, and subsequently upper bound it in terms of the || |/ norm. By definition, have
ES max min
G Zz Z?) < E, max min Σ G, Z,, Z7) + 2e.
22

---

Published as a conference paper at ICLR 2026
To prove this, fix and expand the difference:
1 1+0, 0z
1 ( w/) 1 (x(()
1+ +
1- oi
Y3 (xx))
Wi +
W/
Wi
7
2
1
1 1+
1 1- -- w/) -(1/ - -((x()
(1 w/ +
1 - 02 wi
(yi - ((xi)
2 2
+
2
i=1
Σ
(((m)) - (~)x))
1 +
Wi +
1 1- - u.) -(f(x)))
- (a(2))
( (1+ w/ +
0i 2 wi
2
2
1=1
< (first term)
+
1
- (+))) 1=1
Σ 1f(x)) - (a())
(first term) 2e,
where we used the Cauchy-Schwarz Schwwrz inequality and the bounds |ا/|, k S 1. Taking expectations over a and maximizing/mmnniizzing over w, w', the result follows.
Thus, we obtain:
2 2log.N (e, F,
S St) S
2e + é'.
(13)
n
Letting - 0, we have
log Fe, L2(,,)
R(F, S, S 2c
(14)
n
We can use Eq. (14) for the uniform convergence bound, however, to get the refined dependency, use the chaining technique (Wainwright, 2019; Zhang, 2023); Let é 2- for = 0, 1, 1,,,,,.... Let
Fe be с--cover of F with metric L2(S2n) and define No Fel N(e. F, Lz(S2n)). We may set Fo = {0} at scale 6n = 1.
For each f JF, consider fe(f) E F so that
|| - (e(()) S ct-
Based on the standard chaining technique, which uses f E F, we consider the following multi-scale decomposition:
- Σ
(((
t=1
By the triangle inequality, have
llfe(f) - f(-r() 1 (lfe(f) - fllea(S.) + (lff--(()) - fllea(8a) S 3EE.
Note that the number of distinct fe()) ff) is at most N,N.-1-
Similar to the derivation of Eqs. (13) and (14), regarding Φ(f, Z, Z') as f(Z,), we need to care that 2e appears. Therefore, given e-cover for F.
|l fe(f)lles(San) $ 264-
and
(I - fe-)(lee S (Ife(s) - flle,(s)) + (1)e-1(() - flle)(S)) S (2+ 4)ez.
holds if regarding (bJ, 7,, Z!) as f(Z,) in the above.
23

---

Published as a conference paper at ICLR 2026
Then consider the following decomposition;
R[, Sa)) = E. sup JEl i=1
1 0i
Σ
(f fz(())) + -
1=1
< 7 sup = JEF n 1=1
1
Σ
0, (()))( + Σ
Ear sup fEF n i=1
n
2In(NNNo-1
22 + sup
Σ
[e(s) - -
t=1 fer
2In(NNeNe-1)
<ee +
E
n
1=1
Nn
< 26,, + +
Σ
(a- 10--EMM C4+1)
n
(=1
F,, de'.
< 261. +4
Vn
Then for any > 0, we pick L = supli > 2c}. definition of L, E, >> 2E and this implies E1T1 >
This simple EL+1 S 2e, thus EL S 4e holds. By
Therefore, we have
Vln, Vn
R(F S.,) < inf
8c + 24
de'
e20
By definition, we only need to take e - 1.
Finally using the fact that In FF, < hn N(,,FF (1o0) the result.
(Wainwright, 2019), we obtain
Finally, remark on the case of smCE" The dual smooth CE under the dataset S is equivalent to the optimal value of the following optimization problem:
sm (g. S) max 1 (wi) i=1
Σ(n (vi u:)ws
subject to the constraints:
! 4 lo(x))) 9(X;)1, Vi,j,
-1 < S1, Vi, |ao wyl
where 8; = (g(::)) and denotes the sigmoid function. These constraints can also be rewritten as:
-1 wi 11 Vi, |o wاl S (v:)
(w))) 'O,))
Vi.j.
By definition, the only difference from the standard smooth CE formulation lies in the constraint of the linear program. Since the resulting problem remains a convex optimization. the same proof techniques developed above can be applied to the dual formulation as well. To carry out similar analysis, it is necessary to bound the range of the logit function g.
C.2 PROOF OF LEMMA
Proof. Since S) = 1 Si= (ff2)) = 4 - -(xx))) where S S {2}1 consists
of i.i.d. samples and (y: [(:;] S may wish to apply Hoeffding's inequality. However,
24

---

Published as a conference paper at ICLR 2026
the coefficients W obtained as the solution a linear program that depends the dataset Ste- Consequently, the terms (y: - f(=))w are not independent, and Hoeffding's inequality cannot be applied.
Instead, we employ McDiarmid's inequality, which requires only the bounded difference property of Φf.. Sw.). For completeness, state McDiarmid's inequality below:
Lemma 3. (Boucheron et al., 2013) We say that a function f X - IR has the bounded difference property for some nonnegative constants C1,...y Cau.
sup Z1vonin at [f1. un) 1000-((01) [(1,,...... -.
kn) S Go 1sis (15)
X1..... Xn independent random variables taking values in X and f has the bounded difference
property with constants C1,-.., Cys then for any t E I. we have
E e X.) (K))BBI((X X.)-BI.....))B X.ll)
S 5 27
2
Moreover
-22
Pr Pf Xn) Elf(X1 ................................ X,,) 5) S
(16)
Pr
[ X.)l - -c) S 2
Therefore, we are required to estimate the constants c in Eq. (15). To this end, consider replacing the i-th data point with 2/. and let the resulting dataset be denoted by S% (zi,...,2i 2, 2/, Eitly..., z.). We define the following notation:
smCE Sa.)
11 Σ ty - f(z)))aj,
where wg the solution of Eq. (8) given and Sn, Similarly, define
smm Sm CECC
1
Σ (B) f(zj))W3 + - f((()) Jf
where wift is the solution of Eq. (8) given f and S
We now evaluate the change in the smooth CE under this replacement:
(us [(z))) + 1 - - ((xS))a(+
sm SmCE(S S.) SICE(J,5))
(y) [zxs)aa
j=1
> (gs - [(z)) + -/6 - ((x
<
(u [(x)))
(yi f(xx))w 1 (1/ f(x)))
1 (u - u/) + (f(xx)) - f(x:)) < - n
where the first inequality uses the definition of w By the optimality condition, smCE(f.S, S.)) Ey - ( t// f(x))) 2 Ee f(z,))w + w/t fxx))) ) holds because {wo] is just another feasible choice for the optimization, and the optimal value must be at least as large as the value attained at any feasible point. The second inequality follows from the fact that [w]]] 1.
25

---

Published as a conference paper at ICLR 2026
Similarly, have:
- f(zz))ww + 1 (0% - {x())aa
sm smCE(f. S,) - Sm)E(ff,5)
= Σ
Σ
j=l
ixi
n
(y) - f(z))) + 1 -
2
Σ j=1
11 f(z;))w[
Σ
f(ot))
n
342
(y f(xi))w( - -wi (v/ f=(x)))
1 (s(x') - [(xi)) 2
2
(1l - y:) ):) +
The first inequality follows from smCF(f, S, (wx) 1. E.=, n.)w, Eッ
((ry)) 2 1/2 - f(xz)))) This inequality comes from using value different from the optimal solution wj.
Combining the two results, we obtain:
2
|smCE(J, - smCE(J. S,)) S
Thus, the bounded difference constant in McDiarmid's inequality satisfies:
|sCCF( D.S.) S 1 n { 1
sup
(17)
Our goal is now to study the uniform stability of the quantity sup 10(, Ste) (ff Su)). By definition, for any e E RR+ there exists 9 E F such that
sup fEF
jó(f, S.e) o(f, Sto) ~lg, See) +e.
Therefore, it suffices to study the stability coefficient e; for (Ø(g. Ste) - Φlg. Str) Consider the combined dataset S = Sio U Str D2n, and analyze the effect of replacing a single data point in S, which consists of 2n i.i.d. samples.
We first consider the case where the replaced data point is from the test set S.c { Let the perturbed dataset be
S% (ž1.... , o/, i..1..... En).
Then, using the triangle inequality and Eq. (17), we have:
(Ø(g. Sie) - -(g. Sw.)l - |d(g. Sy,) - Φ(g. Sw.)l S l0(g, Sto) - 6(g. Sta 1l s n'
(Ø(g, Ste) Φ(g, S..) jò(g. Sie) G(g, S.r) 2 -lo(g, Stc) 2(g, Ska)l 2 n
Combining these, we obtain:
2 [lo(g, Sto) p6g St)) |o(g, Sta) - G(g. Sw.)ll <
n
A similar analysis applies when the replaced data point is from the training set Str = { Let the perturbed test
S = (Z1...... 2i 2/, 2.t1...., 2n).
Then,
2
[lb(g, Sto) - $6g, St:)l 166g, Sta) - 0lg Sw,ll
26

---

Published as a conference paper at ICLR 2026
Therefore, the bounded difference coefficient for each data point in the combined dataset is
sup (
lo(g. Ste) o(g, S..) - (ølg. S.,) - o(g, Sw.) =
for 1,....21 2n.
Applying McDiarmid's inequality (Eq. (16)) with these coefficients yields:
S S. Pr sup ((e) &(f, Es..
sup (o( +[1, <exp(-ne2/4)
/EF
FEF
C.3 PROOF OF LEMMA
Similar to the proof of Lemma in Appendix C.2, we apply McDiarmid's inequality to evaluate the exponential moment. To this end, we first compute the bounded difference constants in Eq. (15).
Recall the definition:
max min
aeb(S Zi, Z!),
n
where
6(f, 2i M2) = (y: - f(x))) (L wi + مي w() - (3/ - f(x!)) ( w/ + w:)::
For clarity, we first analyze the special case where a; for all i i [n]: the general case is handled later. Under this assumption, the expression reduces the difference of smooth CEs:
max min
= = AssmCE(f, S.) smCE(f,
(18)
Now fix the dataset and flip single coordinate σj from to -1 Only the j-th term is affected. For jj 1, the term is
(w) f(z;)) - (3/} f(x3))as/,
while for o, = 1, it becomes
- f(/))w - (y) (ay
This corresponds swapping the training and test inputs in the smooth CE optimization. Formally, define the datasets:
S, ((11111)........ vI)...., (2'). v/). (Ins Vn)),, 5, = ((z), (ee,,,)) (I uy)...., (4' vh)).
Then the exponent, with o; for i # j and o, = -1, can written as
V 1. - (b Z, 7 X(smCF(J, Sn) smCE(J, 8%))
max min
W
71
Using Eq. (17), which bounds the stability of smCE, and combining with Eq. (18), we obtain:
T (f Z,)
A Σ Zf
> off of., Z,, Z,)
max min w
max min R it
n
n
Sf, smCE(f,5,) Sw)) + Alsmmm(fffff..mmmm S,, smCE(f,
22
27

---

Published as a conference paper at ICLR 2026
Since this bound holds for arbitrary [nd,, we have:
A
A Φ Li, -)) -(),, (19)
22
sup jE(n]
max min
Zf. Zi, 2,) max min
Σ Y
71
The same reasoning applies to any fixed realization = oI+ of the Rademacher variables (note that a is fixed realization and not random variable), For each such realization, we construct the datasets Sol2 and S used in the smooth CE optimization. Then,
Σ π
ol = => (smCE(f..a - (ale))smmCE(,.5. S
max mii
and changing any single component of a alters the value by at most 2A as in Eq. (19).
Therefore, by the argument in Appendix C.2, the sensitivity coefficients satisfy 2A for all i [n]].
Substituting this into Lemma Appendix C.2 yields the desired exponential moment bound.
C.4 PROOF OF COROLLARY
Proof. As stated in the main paper, Blasiok et al. (2023) proved in Theorem 9.5 that, with probability at least 1 over the draw of the test dataset,
log 2
|smCE(f, D) smCE(f, Sw)l < (Li, (L,,) +
(20)
2n
They further showed that there exists universal constant C' such that
C
RD (Tip, ((0, 1), (-1,1)) & Vn'
based on the result of Ambroladze & Shawe-Taye (2004). See also Luxburg & Bousquet (2004) for the derivation of Rademacher complexity of lipshictz functions.
Combining this with Theorem I and Corollary 6, and applying the triangle inequality, we obtain:
sup sup |mpCsm D) smCE(ff
f
S sup |m smCE(f, + sup Jsm S,e) SmCE(f.
We now allocate the total failure probability across the terms using the union bound. Specifically, we set - 6 in Eq. (20), and 5 > 3 in Theorem or Corollary 6. Then, the sum of the confidence terms becomes:
2 log
log f n1
log 3
log
21
2
2n
2
n
Thus, we obtain the desired high-probability bound.
D ANALYSIS BASED ON RADEMACHER COMPLEXITY
D.1 PROOF OF THEOREM 2
To simplify the notation, we define
-(f()) f(x)).
28

---

Published as a conference paper at ICLR 2026
Then
smCE(f. SmCE(ff Sm))
I sup suppsm D) smCE(f. Su:)
feF
sup
sup fez ((0.),_)(((
Bo h.f.h,X,YY)
sup hELiPE-1(00 ((.11) (.1)).))) 1.1)
o(f,h,X,,YY)
Σ sup
sup
Eø(f, XXY,
off X, Y,)
fEF (1.,)pp_.((01),1111)11
sup (1.1)_11
sup
[ø (off,,,X,Y)
In the last line, we simply used the swapping of the supremum, which can be shown using the definition of the supremum. (In general, for any f F, @(f S sup, o(f', h), which leads to sup, off.)) S sup, s ,(f", .h). This further leads sup, sup, @(f,h) S sup, sup', of h).)
Then, we use Mediramid's inequality. The bounded difference for the training dataset is 2/n, have the following result; for any 5 > 0 with probability 6/2, we have
sup sup EØ f h X, ((_.))).:((U.111111111 FEF
K,,
log
< Dm
sup sup [ h, X, ((..p__.((0.1,..1...)) SEF
Σ of +
Then by considering the standard symmetrization property, we have the following upper bound
sup (ø h, X,) NETiip--((0.1 ([0 II, SEF
sup
(f,,h,
log 22
< E.
sup ([0.)) fEF n
sup
aools. h X Yi) + +21
Finally, by considering the union bound, for any 5 > 0 with probability 1 - ō, we have
sup hELipI=n (f0.)))___(0011111111111 SEF
sup
Eø(f, h, X, Y)
off,h, X.,
log 2
< E.
sup hELip ((0.)) 1). feF n
sup
aoolf h X Yi)
+ +2
Next, we evaluate the Rademacher complexity term.
For the notational convenience, define
1
sup Re T : E,E, (0.1), fEF im1
sup
To = {m: : [0, 1| RR -1 < Lip(n) < 1}.
Our goal is to show
12 T < 222 (0),,.(F)
(' Vlog Nu, no.ll du.
Vn
29

---

1 Published as a conference paper at ICLR 2026
First, will consider c-net of the Lipschitz class, which is independent of data and σ. Fix geometric scales Eg := 2- for & = 0, 1,,....... For each k. choose a fixed (data- and o-independent) Eg-net N₁ C. no under the uniform norm || -looo with [Wvel [(K,, 170, || ll For every пo pick a nearest projection mx) E EV so that || - TA (x) S Ek. Then, by the triangle inequality,
(<(()) T& TT-1 S EN + Ek-1 S 2
Consequently,
1 = To(n)) +
Σ (Tx(1) TT-1(1)) k21
We set A(h) Sup , Ei= 0z0(f X,, Yi). The discretization enror by the k-th covering is given as
EsLE sup A(h) - EsEE sup A(h) heTip
heVi
1
EggEE sup sup fEF
o, h. X,, EgE, sup sup NEN, FEF (,,
Σ
fEF
i=1
< EgLE, sup heLip
Σ
k,
- sup Σ AEN, 1=1
cvol , h, Xi, Yi) 2
S Ex + 26',
where f' and e' is coming from the definition of the supremum, that is, there exists some f E J such that supjer -i o, h X., Y.) S -i= a,o(f", h, X,, Xi) +e' for any E 14, Since we can take e' arbitrarily small, the discretization error is ex.
Next we show that under the k-th covering, we can disentangle the complexity of the lipshicit function class by the covering number as follows:
Es sup A(h) sup EsTE hENr
sup fET
h,, Yi)
hEA,
1 log exp (E5EB, sup AeN,
A(h) sup EsE, MeN,
sup JEF i=1
oi Xi.
< log EsEE, expt( t( sup A(t) sup EsE, heN,
sup JEF nI
0 f. h,,,
heN,
1
< 7 log EgEE exp (( sup A(h) Eg
sup fEF
ho Xi,
heNe
-=1
1
< log EgLE sup exp ((ph(A(h) - Eg keV;
sup fEF
< log EsE
(xpt(A(h) EgE,
sup fEF
oo h,
heV
To evaluate this exponential moment, we use the Mediramid's inequality. The bounded difference coefficient is
n
Σ
Σ
Goolf" h, - 1e
sup fEF
sup PET ド
< sup fef
- (a, h, X,, Yz) - -oOo('' h, Xj, Y,)) -
30

---

Published as a conference paper at ICLR 2026
Thus
EsLE, sup A(h) bEN;
sup Es heM,
1 Σ SEF
sup
o h X,,
s log Σ
1
exp 22 1
heN,
1
t
7 log Wixl
2n'
Next, EgE, [sup 1 over from Lemma 7.4 in Blasiok et al. (2023), off. h, X, X) is 2-Lipshitz with respect to h. Thus by Talagrand's contraction lemma, supheN, EglE [supseF #. Ei= o, h, X,, s 2R)
suPheN, EsE, (su to Ei= o.0(f. h. X,, Yi)] n Em= 2 h, X,, Y))] is the Rademacher complexity of Φff. h, X,Y). More-
we
analyze
Thus, in conclusion, we have
n ,, X,,
EsSE,
sup sup KEM fer n
S (2)D.n()) -logg log Will
2n
Thus, combining the discretization result
EgE,
sup Σ h ((.11.[-1.1I) FEF i=1
sup
S 22)
2 log |N&
+ ck.
Then, following Dudley's integral approach as shown in Eq. (14), we have
1
EsL.
sup hETiP (0.
sup SEF ==1
a, hro(f,h,X, X,, X, Yi)
VinN(e', no. 1lo0) de'
< 2DDD, (F)
inf <20
4e + 12
< (F) Vn¹
(21)
where we used the covering number estimate of the 1-dimensional Lipschitz functions, see Wainwright (2019) for the details.
D.2 SUB-OPTIMAL RESULT OF THE RADEMACHER COMPLEXITY
The evaluation of sm in the same manner as in Appendix D. except that randomness is now considered over the 2n data points from both the test and train sets. Apart from this difference, the argument identical, and the resulting bound again depends-just through covering arguments, as well as on the complexity of F. This reflects the inherent complexity of the composite function (f(()) appearing in the definition of smooth CE. Consequently, compared with Theorem 1, where the covering- -based proof avoids dependence on the complexity of Lipschitz functions, this approach yields suboptimal result.
sm CE((f, S.,) using Rademacher complexity can carried out
in Appendix D.1 the complexity of Lipschitz functions
On the other hand, as shown below, is also possible to derive the Rademacher complexity bound number result of Theorem I. In this case, the dependence the complexity of Lipschitz functions disappears, but at the cost of introducing an additional (log 2n)² factor into the Rademacher complexity bound.
from the covering-number
Corollary 6. Under the same assumptions as in Theorem 1, there exist universal constants {Ci}s such that with probability at least 1 - 5 over the draw of Ste and St, have:
C2 Vn
log 8-1
sup (t,) - SmCC-s fEF
2. 2n)2
+
2
n
Proof. We begin by defining the empirical Gaussian complexity of F as:
6 (F, S.)) = Eg sup
Σ 9. (Z,)
JEF
E=
31

---

Published as a conference paper at ICLR 2026
where g l91..... . are independent standard normal random variables, i.e., 9: N for all 8 [n].
From the modified version of Sudakov's minoration incquality (Theorem 12.4 in Zhang (2023)), have:
2v 2n2nmDD2 +1.
This justifies the reason why we use the covering number based on the L2 (2(2n) pseudometric in the derivation of Theorem 1.
As result, obtain:
8c + 24 '-
(2 (2/20D,2n(F))
1
log(1/0)
|smCE(f, smCE(f, & inf
de'
+
e>0
e'
vni
24
log (1/8)
2 inf <>0
Se + 2448288 log
+
Vn
n
8
24
log(1/6)
+222 (F) log log(2n)
+
2n
22
n
where we have set = 1/v2n in the final inequality.
Furthermore, from Lemma 4 in Bartlett & Mendelson (2002), there exist universal constants and C such that:
DD (F.2n(F) logg(2))Rp.22))
Combining the above results, conclude:
32
log( log(1/6)
Swe (m))))mmmC(,,)))) & 24 (F 2n)
+ 21
V2n
n
E ESTIMATION OF RADEMACHER COMPLEXITY OF THE LIPSHITZ FUNCTION CLASS AND UNIFORM CONVERGENCE BOUNDS
In the main paper, we evaluated the universal constant to express the complexity of Lipshitz functions following the standard way in the learning theory (Wainwright, 2019). In this section, derive the explicit constant of the Lipshitz function class. This leads to the explicit upper bound of Eq. (3). Recall that the constant based Rademacher complexity of the following function class. We define the class of 1-Lipschitz functions on [0, 1] with range in [-1,
F F= { [0.1] [-1.1]
[f(x) f(y) < | vl Va, E [0,
Then we show that the corresponding complexity is
log3
2og Vn
58
Hin (F)
<
<
Vn
Vn
From Eq. (20), have that with probability at least
8 over the draw of the test dataset,
116 Vn
log
|smCE(J SmCCC,,,
S
+
2n
Then this leads to that the constant C, = 116 in Corollary 1. As for the constant C2 Theorem 2, from Eq. (21) and Eq. (22), have C2 24 5 log
57.
32

---

Published as a conference paper at ICLR 2026
Proof. Note that do not impose any anchoring condition such f(0) 0.
For any f E F, define
c: f(0) E [-,,1], s(x) f(x)
Then the following properties are immediate:
g(0) = 0, [g()) g()i - 1f(x) - f(w)] s | yl Ve, E [0,1].
Moreover, since g(0) 0 and g is 1-Lipschitz, have
[g(z) = (x(x) g(0) - z - 0 <
Vx E [0,
so (xx) E 1, for all Hence g belongs to the anchored class
g = [0, 1] --11,,1 g(0) = 0, [g(x) g(v)l - x - yl Vx,y E 10.113.
In addition, f can be written f(x) = g(x) + with g and [-1, 1]. If we define the class of constant functions
C= f + c
we obtain the decomposition
F= + C,
that is, every f E can be written as the sum of an anchored 1 1-Lipschitz function and a constant function.
Next, relate the empirical Rademacher complexity of F those of g and C. Given fixed Rn), the empirical Rademacher
sample (f1.-.., ..,) and independent Rademacher variables complexity of function class H. defined as
RR (H) == E. sup n
Σ a.M((a))
Using the decomposition
= + with g and c E [-1, 1]. obtain
(F) Eg sup
1
Σ Cai((a))
[eF n
E,
sup
(g(x;) tc)
LgEg, cE 1,1,
Org(x;) + cc Σ 0i
E,
sup LgE oE[11]] 1.1]
1=1
The supremum over (g. c) can bounded by splitting the two terms:
sup gEG, (-(-111]
agg()) cc.
sup Σ
arglzz) + sup C.
Σ oi.
gEg 1=1
eE|-1,1]
i=1
For the second term, by definition
E
sup cE(-1.1]
C-
Σ σi
7 i=1
E o, < 0, the maximum is achieved when and if Σ a; 2 0, the maximum achieved when 1. We define 1 = (1....,I) RR, A= (-1, 1]. By using Massart's lemma, we have
1 E,
V2
E_
sup
sup
J3 <
LeE
1,1
1=1
L
1=
n
33

---

Published as a conference paper at ICLR 2026
Therefore, only need to upper bound
n Ri (G) = E. sup - LgEg
Σ i=1
o.g(z,)
By using the discretization argument for the one dimensional Lipshitz function class (for example, see Eaxmple 5.10 in Wainwright (2019)), have
5 log
log (e, 9,, 1100) -
Then the rademacher complexity can be bounded by the Dudley entropy integral (in empirical (2(P,), we have
12 (9) S vn /'' (u, (2())) du.
G,
Since ||/, - (P.)) $ |1/- l12llo for any h1, h2, the covering numbers in (2(Px) are bounded by those in Iloo
5 log 3
log N (u,G, G2L,()) S log N (u, 9, (10)) S u
for all u E (0, 1], where we used the previous lemma with = u. Hence
12
5 logg3
(9) S
du
Vn
"
12 5 log 3
4 1/2 du
Vn
12 log
3
24 5 log
2 =
(22)
Vn
Vn
F PROOFS OF THE GRADIENT BOOSTING TREE
F.1 QUADRATIC UPPER BOUND OF THE BOOSTING
The iterative minimization problem is given as
min L, (t (x)))
Via
and by considering the quadratic upper bound for this M
min (- (V wrbo) + |wrbbll?) min |M 2/1 Via
F.2 FROM WEAK LEARNABILITY TO FUNCTIONAL GRADIENT
We use the empirical inner product and norms
1 Σ a.b,, I := (f, (f, (g(h))) [elle
1 Σ
(a.b)
n
Consider the binary cross-entropy with logit z = g(X), i.e.
Lent 2) - loooo (2) (1-z) log(1 -((2), 0(2) _+e Its per-sample gradient w.r.t. the logit
V.
Lane (Ti, 2)
xg((X))) jr.
Oz
==g(Xi)
Let (VI, V..... V.).
34

---

Published as a conference paper at ICLR 2026
Lemma 4. Under the same assumptions in Theorem 3, the following holds:
smCE (g - (1.)) S 7B (Vr, Le) + Mw B.
27
Proof. Introduce := 2ij 1 E {+1}. Then
V (g(xi)) Vi -y:or -y:orr- (-ug(())))))) -oa qi (0,1).
hence V1 = Gj. Let my j-1 1
E A.. By Assumption 2 there exists vi E such that
E WWt (x,) 2 7 B. Therefore
yal V.lv = 1
(v. 1² (2((5.)
V
Σ
w.br s -7B]]olle..s..>
1=1
Since Vi is sign-flip closed, - E V, and
(v.-v") Lo(s)) 2 (ll
(23)
Note that
MMM Vilia(s.) S [1A Velliz(5..)
which implies that
2M br v.) Lo(Sm) S -2Mw:((-Vb) Vz) Lo(SS) + &M2 || (172())))
and we obtain
((- Vt) Lz(Sw) S (ti,, Vi) Lg(Sw) + Mw B².
(24)
2
Then combining Eq. (23) and (24) we obtain
Mw. B²
y B (sW) S (1r, Vi) (2(Ss))
+
2
By definition, we have
smCE (g Sn) S [[llL
Since M- = 1/4, combining the above two inequalities, we obtain the result.
F.3 PROOF OF THEOREM 3
We consider the Taylor expansion of the objective
((+1))) S ())) wi (. vo.) M w wil vo. (l.),
Here we use Lemma Appendix F.4. The lemma is the Pythagorean relation of the projection of the function gradient. In the lemma, w,M + w and V - x, and + tho, corresponding to the GBT step. From Eq. (25), setting and, we get
(We., w.M to.
Vi) 50.
and this leads to
Mwellyo 112 < Wo Ve)
Finally we have
(++)) < (0))
( Vo.
35

---

Published as a conference paper at ICLR 2026
By summing up from 0 to T - 1, we have
we (2(s.) (n (7)
2 1=0
If we use the constant stepsize Wa = we have
1
2(Lnlg(0))
L (())
E
Vv (o,
S
T 1=0
wT
Combining Lemma 4, we have
T-1
T
T-1
wMB
smCE (0 $ T
(ellt. v
Le, voo (2))) +
T
By
T
24
t=0
1=0
((Ln(g()) (n(g(T))
w wBB
B
u/
24
Since the cross entropy loss is always positive, we drop [n (T) and obtain the result.
F.4 AUXILIARY LEMMAS
Setting. Let X C Rd be nonempty closed convex set and fix scalar weight w > O. Consider
f(=) = | x112
+ const, x Rdd
2
and let
arg min f()). E
=EX
Equivalently, with yo == x/w., p is the Euclidean projection = IIx (yo).
Following is the alternative lemma of Lemma 3.1 in Bubeck et al. (2015),
Lemma 5. For all g E X., the following relation holds.
{p 9, w² wr) 0.
Equivalently, since w2p w. w² (p- yo), we have
(p q. yo) I 0.
(25)
Proof. The objective is convex and differentiable with gradient
ff(2) -² wr.
For convex differentiable optimization over convex set X, the necessary and sufficient first-order condition minimizer p is
-) 20 (Va E X). i.e. (p - g, w2p - wx) < 0.
Rewriting gives (Vf(p).p Φ) S 0, ie.
F.5 SUMMARY OF THE GRADIENT BOOSTING TREE ALGORITHM
We remark that the regions of binary tree are defined as follows: Given a node associated with some region R C X C Rd, split the region using splitting threshold E g and splitting dimension E [d] into two child nodes, R2 and RR. which respectively correspond to the regions R2 {x R v, < s) and RR {a R æy > s). By recursively applying this procedure, obtain partitions {R where each region corresponds to hyperrectangular region in Rd.
The set of such trees defines the following function class:
T
Cj [Zen,) 2 Ry disjoint, ej E
and |C5] is bounded by B
Let Vt, Vyl(o(g1)(X))) Y.) denote the functional gradient the i-th training point.
36

---

Published as a conference paper at ICLR 2026
Algorithm 1 Gradient Boosting Tree with Cross-Entropy Loss
Require: Training data St. {(X,, Yi) base learner via E T, loss function Lent
Ensure: Final logit function (xx)
Initialize g ( (x)
2: for = ,,,, do
3: Compute functional gradients:
V1 V gg (o(o Yi), i= L, L....,n
4: (Optionally step size wt)
5: Solve: 0g = arg mingge 1 Ei=1 |M - Vi,il
6: Update the model:
(x++))(z) g0(0()) wrrb., (2)
7: end for
8: return
(x)) or (x)
F.6 PROOF OF COROLLARY 2
We first remark that the following relationship holds:
smCF(J, Sw)) S smCF (g.Sut Sw)
The proof is nearly identical to that of Lemma 4.7 in Blasiok et al. (2023). By replacing the population expectation over 'D with the empirical expectation over the sample St. we obtain the result.
Therefore, an upper bound on the dual smooth CE over the training dataset directly implies an upper bound on the standard smooth CE. By combining this with our developed generalization bounds, we obtain the desired result.
We now evaluate the Rademacher complexity. We express the function class of g n ET-1 g as g.
Since F= a and 1/ 1/4-Lipschitz, Talagrand's contraction lemma yields:
Rp (o g) 4 Rg).
We now derive an upper bound on the Rademacher complexity of G. Using its sub-additive property, have:
T-1 RD. (9) <
Σ
( (Lg(t))).
T
1=0
where {o(t)) is the function class that after t-step GBT algorithms. Then
Rp. < wtDR (T))
where T denotes the class of regression trees.
Furthermore, by Theorem 6.25 in Zhang (2023), the Rademacher complexity is upper bounded by the covering number:
In In (e,, de'
RD (T) inf
4e
12
<>0
n
To proceed, upper bound the covering number for binary regression trees. From Appendix B in Klusowski & Tian (2024), we have:
C' 2
In N(c, T, (s())) In(nd)2" 2m
2
37

---

Published as a conference paper at ICLR 2026
Therefore, there exists universal constant C' >> 0 such that:
2 log (nd)
RD,n( Cy
n
In conclusion, we have that
2 log
( CwT
Finally, substituting this into Theorem 2, we obtain the result.
()) BBwT +
wMB
n log (nd)
log 3/2
smCE"
S.)
wTC
2y
71
71
F.7 MISCLASSIFICATION RATE
Let Sn. denote the empirical distribution of the training dataset. From standard margin-based general- ization theory, for any > O, with probability least 6, the following inequality holds:
2 RD, p
log _
S pl P(x, - 1)g (x)= s 0] s P(xY) 1(2 (X)
2n
According Nitanda Suzuki (2018); Nitanda et (2019), the empirical margin error can be upper-bounded by the functional gradient as follows:
P(x,r)~s, [(Y - 1) (X) s pl s (1 + el) (X), ()
Combining the above results, we obtain:
(
(n BBuT
wB
CwT
2J log(nd)
log 1h2
- - s 0] s (1+
+
8y +
n
2n
This result illustrates trade-off with respect wT, which balances the training misclassification rate and the complexity of the hypothesis class.
G PROOFS FOR THE KERNEL BOOSTING
G. PROOF OF BQ. (4.2)
From the margin assumption, the following property holds: Φ(xx) Y if yi Since H implies - H. we define T Φ. Then, the margin assumption implies:
-p(x,) 7 if yı 0, for all (z4,gi) E S.r-
Ō(x+) 7 if y: 1, H(x.) if y 0, for all (xt, Str-
We now analyze the gradient the RKHS under this construction:
T L.
| (1) T.V
(26)
| V LL) H
sup
(T.V I., (g)
V Ln, Φ)
Lo(Sw)
Vgl(g(X)), o(Xi)
n
(a(g(())) YY) 6(x)).
38

---

Published as a conference paper at ICLR 2026
where the last equality follows from the functional gradient. Using the margin assumption, we obtain:
1 n
1 7 72
Σ (. -
V Vg((g(X)), Ki)
n
This completes the proof.
G.2
PROOF OF THEOREM 4
Assume that the loss function [(g) is M-Lipschitz smooth with respect to g. meaning that for all
g.g'.
M ll -l.
L(g') S L(g) (VL(g). ().2)))) 2211'
Plugging in 9 gld) and g' = g g(0) w. Tx V ()) ), we obtain:
((g S ()) wT (V ), TvV (gg (.2.(s))
M 2 Th Lig (122(5))
+ 2
MA
S ())
wel TA V, Ln (gg (t)
1 +
w/ ? [ L.
2
wy WA
= I() wi 1
, (0))
2
S L(g0))
Wt
T v L (g 11
2
where the last inequality uses wt S MX
Summing over t = 0, T - 1, we get:
T
We T& سLي (g)) (o)) (.)
In particular, using constant step size wi w, we obtain:
1 T I gI.
2 S wT
10))
T
From Eq. (26), we have:
Σ
S wT
2
Ln ()))
T
Then, using Jensen's 's inequality and the definition of g(()) == $ - (0),, we get:
(x), L.S..)
1
Σ
V V 4 (x),
S T
Combining these gives:
(x)(
S <V W ()))
(T(S.)
39

---

Published as a conference paper at ICLR 2026
Generalization Bound via Rademacher Complexity. We now evaluate the Rademacher complexity. We express the function class of g()) as G. Since F = =a o G and a is 1 1/4-Lipschitz, Talagrand's contraction lemma yields:
Σt= gr
/A
a
Pi (F) = ( o 9) -
4
where a is an upper bound on the RKHS norm of G. which estimate below. The final inequality follows from the standard Rademacher complexity estimate of the RKHS, see Mohri et al. (2018) for the details.
Recall the recursion:
T-1 g = g - w Σ
Ts V )n)(g)))
Then:
T-1
11g (2)
12 S (1 +
" Σ
Vv LTVgLng)
H
Applying Jensen's inequality:
1/0
T (
WTTT V.4VVyLn (n
S u²
1
V g
T
1=
S w2T² 2
wt Ln(g!"))
2w'TLn
Assuming 11 S M, we obtain:
(g II S A' 22TTL.
Absorbing (1( into universal constant. When considering the norm of g(T), it is also O(N' + VwT). Thus, we conclude a O(A' + VwT). Substituting this into the Rademacher bound yields the final generalization result.
G.3 PROOF OF MISCLASSIHICATION RATE
Let Sn, denote the empirical distribution of the training dataset. From standard margin-based general- ization theory, for any O, with probability least 1 - 6, the following inequality holds:
log !
-1g (X) S 0] S (2y pl 2 + V
2n
According Nitanda Suzuki (2018); Nitanda et (2019), the empirical margin error can be upper-bounded by the functional gradient as follows:
P(x,y>~ [(2 - T) (x) S pl s (1+ (1++ee)llv el) (X),
Combining the above results, we obtain:
Pox.)><o((2 - 1))(7) < (1+e")
V wT
2(A' + / 2w
Ln
A +
log
5
n
2m
This result illustrates a trade-off with respect to wT, which balances the training misclassification rate and the complexity of the hypothesis class.
40

---

Published as a conference paper at ICLR 2026
G.4 PROOF OF COROLLARY 4
We first remark that both the smooth calibration error and the misclassification rate exhibit similar asymptotic behavior with respect and w/. By substituting the given hyperparameters into the bound presented in Theorem 4, we obtain the desired result.
H FORMAL SETTINGS OF THE TWO-LAYER NEURAL NETWORK
H.1 FORMAL RESULTS FOR THE SMOOTH CE
Here provide the formal setting of the results from Nitanda et al. (2019). We assume Y {+1} and denote by y the true probability measure on x V, and by in the empirical measure based on samples ((X,, YJ) drawn independently from i.e.,
dun (2, = Σ (xxx)XXX
where 5 denotes the Dirac delta function. In the main paper, we consider labels in Y = {0, 1}; here, we convert them to Y = 2 1, so the distribution DD over X' Y becomes μ over X' x Y.
The marginal distributions and y V, let E(s, y) denote the logistic loss:
and Un over are denoted by vx and Vx,.. respectively. For 8 E TR.
((s, y) = log(1 exp(--yy
We remark that given logit value the predicted probability of i p o()). and the loss also be written {(s, y) g+1 log p - log(1 p). Replacing Y with Y recovers the standard cross-entropy loss: {(s, 5) = log p + (1 ÿ) log(1 - p).
2
The empirical objective be minimized is defined as
L (0) = E (x,,)) (((gg(())).) X))
Σ Eggo (Xt), Xx),,)). Yi).
where go X' > two-layer neural network parameterized by 0 (0,) When treating the function go as the variable of the objective, we also write L, (go) L, (0).
We now introduce the following formal assumptions.
Assumption 1.
(A1) Assume that supp(ux) C. {o X ||~|| S 1}. Let be CC-class function, and there exist constants K1, K₂ > such that
||o'|l K₁ and ||a"|lo0 K2-
(A2) A distribution μi on Rd used for the initialization of 0,, has sub-Gaussian tail bound: there exist constants A, > 0 such that
Pa [1000 2 s A Aexp(-b(²))
(A3) Assume that the number of hidden units m 24 is even. The constant parameters (a, M and parameters g(0) () 7= are initialized symmetrically as follows:
Or = for { 1.... 2 a, - for { + 1, 11...,,7. m
and
0(0)
(()) + for E {1,, {1..... m S 2
where the initial parameters (0. (0/"))//² are independently drawn from the distribution po-
(A4) Assume that there exist 7 > 0 and measurable function v RR + {w Re such that the following incquality holds for all (æ, y) E supp(v) c & x V:
||wl|1 < 13
y (0) x). v(0(0))
13(m)) = yE (000 2) ((B(0)) 2%
41

---

Published as a conference paper at ICLR 2026
Remark. Clearly, many activation functions (sigmoid, tanh, and smooth approximations of ReLU such as swish) satisfy assumption (AI). Typical distributions, including the Gaussian distribution, satisfy (A2). The purpose of the symmetrized initialization (A3) is uniformly bound the initial value of the loss function L., over the number of hidden units This initialization leads to foro (1) O, resulting in L. (0(0) log(2). Assumption (A4) implies the separability of a dataset using the neural tangent kernel. We next discuss the validity of this assumption.
Theorem 6 (Global Convergence, Theorem in Nitanda al. (2019)). Suppose Assumption holds. We set consiant K as
K = K1 + 2 K K3
For all 3 E 10. 8 (0.1), and m E 2 such that
16K? 2n
m
log 8
72
consider gradient descent (6) with learning rate
29-1
0 < 1 S min
m
K? K₂
and the number of iterations
m
T
32w:3 log
Then, with probability at least
8 over the random initialization, we have:
T
16 log((
2
Σ
1V
I
+
K
T
7²T
w
where we define the L' -norm of the functional gradient as
Σ 10,((g6 Y.))
Σ 2n
1
n
v 2po
=1 + 1/.
The result above corresponds Eq. (6). This bound provides a guarantee on the training smooth CE. Proposition 8 in Nitanda et al. (2019) yields estimates for the Rademacher complexity and covering numbers.
Theorem 7 (Proposition 8 in Nitanda al. (2019)). Suppose Assumptions (AI) and (A2) hold. Let Vw > 0, Vm E 2+, VT Z+, 45 E (0,1), and VS of size Then, there exists universal constant C > 0 such that with probability at least 1 with respect to the initialization of (0), the empirical Rademacher complexity satisfies:
Rs(F) Cm 1 Du,,, (1+ K1 K2)
log (n(1 K1 + K2) (log(m/0) + D2 D2.m.)))
(29)
where
D Dw.m,TT TT
Moreover, when a is convex and o00) = 0, with probability at least over random initialization of ((),, we have:
2/2-8 (uw.m.+ +
log( AAm/5)
Rs <
(30)
vn
b
By substituting Theorems and 7 into the uniform convergence bound in Theorem 2, we obtain the following guarantee the smooth CE for two-layer neural networks.
42

---

Published as a conference paper at ICLR 2026
Corollary 7. Suppose Assumption 1 and the settings Theorem 6 hold. Then with probability 1 over the random draw of Sux and initial parameter Bu, we have
6
m28-1
min SmCE (goco, p1) 5 - 72T 1-
+ K
(31)
w
C22 vn
+ C3m Dw.m.r(1 + K1 K2)
log 6
log n((1 + Ki + K2) (1og(2m/0) + D Das,m )) 61
where Ci,..., C3 are universal constants.
Moreover, when is convex and a (0) = 0, with probability at least 1 - 8 over the random draw of Siy and initial parameter 0,, such that we have:
m23-1
min smCE (gows S Cip (E(.....T-1)
+
K
+
72T
C2
CaKim-/2-8
-uumm +
log (2n2Amm/))
log 6
61
Vn
Vn
b
n
where C4 is a universal constant.
Proof.
We use the following upper bound from Mohri al. (2018): with probability - 6/2, we
have
log 3 2m
RD, < Rs(F)++ +
V
Then from Theorem 2 with probability 1 5, we have
C2 nn
+ 49s 61 log
sup
sm S|CCEf, smCE((f, fEr
n
We then substitute Eq. (29) and (30) and taking the union bound, obtain the result.
For completeness, we include the result on the classification error, adapted from Theorem Nitanda & Suzuki (2018):
Theorem (Theorem 4 in Nitanda & Suzuki (2018)). Suppose Assumption and the settings of Theorem 6 hold. Fix Ve > O. Then, with probability least 1 - 35 over a random initialization and random choice of training dataset Suo we have
log(2/8)
min P(X gg (X) 50 5 S C5(1 exp(e))CCu,m.T + 3 (E......,T-11
2n
+ Dumm.(1 + Ki+ + K2) V log [n(1 + K1 + K2) (log(m/5) - D2 )
where
Cw,nnT = 17
1/2
( 1-12 1/2 + VK
and Cr and Cs are universal constants.
Moreover, when a is convex and (0)) O, we can avoid the dependence on the dimension d. With probability least 35 over random initialization and random choice of training dataset Ser.
min TE. P(XY)) gous (X) $ 0] < Cs(1 + exp(c))Cw.m.. + +3 log(2/6)
2n
log log(Am/0)
+ 1/2-8 evn
DumTt +
b
where C7 is universal constant.
43

---

Published as a conference paper at ICLR 2026
H.2 FORMAL STATEMENT FOR COROLLARY 5
We restate Corollary 5 with formal assumptions
Corollary 8. Suppose Assumption I and the settings of Theorem 6 hold. If for any > 0, the hyperparameters satisfy one of the following:
(i) B E [0, 1), ( ). = Q17 )), w= 0gy 3e 2T 2 (2
12( 2c 2)))) (m, n 5i(c 2)
(ii) 3 0. = e ( 3/2 log(1/e)). 7 O ( log (oge((1)))
then with probability at least 1 - 6, gradient descent with the stepsize w finds a parameter ((0) satisfying smCEEggoo, Sw) S and P(x,Y)~ [Y Yaco (X) S 0] S within T iterations.
Proof. The guarantee for the misclassification rate is adapted from Corollary in Nitanda Suzuki (2018). As for the smooth CE, since the complexity terms in the misclassification bound (Theorem 8) and the smooth CE bound (Corollary 7) are of the same order, we also obtain a corresponding guarantee for the smooth CE.
I RELATIONSHIPS OF THE PROPER SCORING RULE AND FUNCTIONAL GRADIENT
In the main paper, we discussed the relationships involving the functional gradient only over the training dataset. Here, we provide the corresponding results for the population smooth CE.
We begin by connecting the post-processing gap with the functional gradient. First, we recall the definition of the functional gradient:
Definition 11. Let be a Hilbert space and h be a function on H. For & E H. we say that is Fréchet differentiable at & in H if there exists an element Veh(gg) E H such that
h(()) h(E) + (Vgh(E), - E) ollE (llx).
Moreover, for simplicity, we refer to V Veh(E) as the functional gradient.
See Luenberger (1997) for more details.
Next, focus the of the squared loss. To simplify the notation, express r(f(x)) f(x) + hx)())) where is the post-processing function in the definition of the smooth CE. Then we h + lsq. (- fxx), and & - rx)()) in the definition of the functional gradient. This results in the following relation.
(xq((()))))
(32)
=ra - (aap://(()))--((()---)))(()-) - 1
- -
where (f 3) denotes the partial derivative of (f. with respect to f. Thus, we observe that V (f corresponds to the functional gradient. Therefore,
v vlls( -A(((X)) 1 [1((((X))1)
smCE(f,D) < pfap(f, D) = sup E
h
I sup E
V ()ss(((()))) M(f(X)),
where the supremum is taken over all I-Lipschitz functions.
Next, for the cross-entropy loss, recall that VEL"(s, v) = p(1 - p), where p = pred, = e* e*/(1 + e*). This implies that the cross-entropy loss is 1/4-Lipschitz with respect to s. Therefore, by Taylor's theorem, there exists 5 E (0, 1/4) such that
e (g(x), e (r(g(z)).v) V (g(x)))) (r(g(x)) g(x)) 7001 ()((((())))9((4)))
(33)
44

---

Published as a conference paper at ICLR 2026
Thus, obtain
2smCE!! D), pGap (1:14)))14)))))
(g. D)
sup E - v) h(o(X)) - 2 ))
I sup E V-V -) h(g(X)))
where the supremum is taken over all 1 1/4-Lipschitz functions.
From Eqs. (32) and (33), we obtain upper bounds on the training smooth CE in terms of the functional gradient evaluated on the training dataset:
Sm sup
- V- V (((x))))
and
n
2s Sw) S sup
(g(,) Yi) n((())))
Finally, we remark on the case of general proper losses. As discussed in Appendix A, the post- processing gap can be defined more generally. the loss is Fréchet differentiable, then similar relationships to those derived above for the cross-entropy loss can be obtained.
J DISCUSSION
J.1 IMPLICATIONS OF THE BOUNDS IN SECTION
finite-samin maite-sample analysis of smooth CE for three representa- tive learning procedures: Gradient Boosting trees (GBT's), Kernel Boosting in RKHS, and Two-layer Neural Networks. In contrast to most existing calibration results, which focus on population-Ieve pre- dictors, these bounds are stated directly for concrete algorithms and make explicit how optimization and generalization jointly control the accuracy and smooth CE.
Section develops an
Technically, the analysis proceeds in three steps for each algorithm. The first is functional gradient analysis evaluate the training smooth CE smCE(J, Suz), which quantifies how optimization (number of iterations, step size, regularization) reduces smCE on the training sample. The second step a control of the discrepancy |smCE(ff D) - smCE( St)) using the uniform convergence bounds for smooth CE derived in Section 3, specialized each hypothesis class. Combining these two ingredients yields explicit conditions on the number of iterations, regularization strength, and model complexity under which test accuracy and smCE(f, D) are simultaneously controlled with the same order.
For each algorithm, we summarize concisely which parts are and how they are connected the above objectives as follows.
Section 4.1: Gradient Boosting Trees (GBT). Under margin-type condition, we establish
convergence of the L -norm of the functional gradient associated with smCE(ff St.), formalized in Theorem 3. This provides an explicit relationship between the number of boosting iterations and the decrease of the training smooth calibration error.
For the generalization step, we invoke the uniform convergence bound for smooth CE from Section and relate the reduction in smCE(f, Stz) to the reduction in smCE((f. D) as function of n and the complexity of the underlying tree class (Corollary 2). This makes explicit how the generalization gap in smooth CE depends on the number of boosting iterations T.
The accuracy bounds themselves rely on existing GBT analyses, but Corollary 3 combines them with the smooth CE bounds to yield simultaneous guarantee for test accuracy and smCE(ff D). This formalizes the common heuristic that, for GBT, suitable early stopping can yield models that are both accurate and well-calibrated.
45

---

Published as a conference paper at ICLR 2026
Section 4.2: Kernel Boosting in RKHS. For kernel boosting, relate the functional -rracional-gradient convergence analysis to the RKHS norn and establish convergence under conditions tailored to smooth CE (Theorem 4). This is closely related to previous analyses of kernel boosting (Wei et al., 2017; Nitanda & Suzuki, 2018), but the assumptions and objective are adapted to the smooth calibration setting. The result shows that, for RKHS-based boosting, the decay of the functional gradient along iterations translates into an improvement of the training smCE((f,
By combining Theorem 4 with the uniform convergence bound from Section 3, we obtain explicit test bounds in which the RKHS norm, the kernel choice, and the number of boosting iterations jointly determine both accuracy and the generalization of smCE(f,
As in the GBT case, the accuracy analysis builds on known results, while Corollary 4 provides simultancous guarantee for accuracy and smooth CE. This yields concrete guideline on how to choose regularization and the number of iterations so that kernel methods achieve both good predictive performance and calibration.
Section 4.3.: Two-layer Neural Networks. For two-layer neural networks, we directly use the functional gradient norm bounds from Nitanda al. (2019): The novelty of this section lies in combining these optimization bounds with the smooth CE generalization bound from Section 3. This leads to Corollary 5, which provides a simultaneous guarantee on test accuracy and smCE(f (D) for two-layer networks, under appropriate choices of iteration number and regularization.
In this way, the analysis offers a theoretical lens on the empirical observation that neural networks can be miscalibrated: it identifies a training regime (in terms of munciooal-graddien control and uniform convergence of smooth CE) under which smooth calibration can be quantitatively guaranteed alongside accuracy.
J.2 LIMITATION OF THE MARGIN ASSUMPTION
In the main analysis, the margin assumption used to control the functional gradient and to derive an upper bound the smooth calibration error smCE over the training dataset. In the RKHS setting, however, there is an alternative route to controlling smCE. Consider an RKHS H that is closed under composition with I Lipschitz functions, in the sense that for any ho f E H. In this case, the composite function o f that appears in the inner product defining the smooth CE is again an element of H. Around Eq. (26), one can therefore take Ø = o f, and it is then natural to expect that SmCE can be controlled directly via the RKHS norm.
H and any h E Lip have
A limitation of this argument is that RKHSs H enjoying such a closure property are rather restricted (for example, the RKHS associated with the Laplace kernel on X' = RR. Clarifying in which more general situations this type of argument holds, and identifying kernel families beyond this restricted Laplace-kerne example, is an interesting direction for future work.
J.3 COMPARISON WITH EXISTING WORK
To the best of our knowledge, no prior work provides generalization bounds specifically for smooth CE; our results are therefore new in this respect. Fujisawa & Futami (2025) derives generalization bounds for ECE, not for smooth CE. Since smCE < ECF. holds in general, their bound can be transferred to smooth CE, but our results are strictly stronger in several ways: First, the bound in Fujisawa & Futami (2025) requires smoothness assumption on the conditional probability, whose validity on real data is unclear. Our bounds hold without such additional assumptions. Second, their bound has rate On (1/3), whereas our bound chieves Onn 11/2), which strictly tighter. Finally, Fujisawa & Futami (2025) does not provide conditions under which the training ECE becomes small, and therefore does not identify when smCE S & can be guaranteed. In contrast, we show explicit conditions under which smooth CE is small for concrete algorithms.
We next clarify how our analysis relates to the post-processing gap of Blasiok et al. (2023). As shown in Section 2.2, Blasiok et al. (2023)establish that the evaluation of the post-processing gap is equivalent to the smooth calibration error. Moreover, post-processing can be interpreted as measuring how much the loss decreases when the predictor is updated; in our setting, this corresponds to updating the function along its functional gradient. This connection is the main motivation behind the analysis developed in Section 4.
46

---

Published as a conference paper at ICLR 2026
While Blasiok et al. (2023) use the post-processing gap primarily discuss, in qualitative rather than fully theoretical way, how much the smooth CE can be reduced, Section 4 provides a rigorous characterization of this phenomenon for concrete algorithms. In particular, in situations where updates, we prove that the smooth CE
post-processing is implemented via functional -aaiinntgggaddnnaaaaaaaaa decreases for specific learning procedures. In this sense, our results can he viewed strengthening and formalizing the insights of Btasiok et al. (2023) within an algoritbm-dependen,, finite-sample framework.
J.4 GUIDANCE FOR PRACTICAL ALGORITHMS
The results in Section 4 provide concrete guidance for practical training of GBT, Kernel Boosting / Two-layer NN models. For example, in Section 4. (Corollary 2), the first term in the upper bound decreases with the number of iterations T, reflecting the improvement of the training smooth CE. In contrast, the fourth term corresponds to the Rademacher complexity of the tree model and increases with T, reflecting the growth of the generalization gap (i.e., overfitting). The same qualitative behavior appears in Section 4.2 and 4.3.
Hence, our analysis formally justifies the following practical tuning rules: i) excessive iterations can worsen smooth CE due to overfitting and ii) appropriate early stopping (and regularization) can jointly optimize accuracy and smooth CE. This shows that, from the perspective of calibration as well, controlling hypothesis class complexity via regularization and early stopping is as important as it is for accuracy.
Finally, our framework and analyses also applies to post-hoc calibration methods. Suppose a model f' is learned using the training data Str. and an independent recalibration dataset S.o. is used to learn post-processing map h, so that predictions are given by (X))).
In this setting, the uniform convergence bounds of Section 3 can be applied to bound |sm CE f) Sm f, Sre) i.e., the generalization gap of the post-processed model with respect to the recalibration sample. For binary classification, this allows one to analyze post-hoc calibration schemes such as histogram binning or beta calibration within the same framework. Moreover, the results in Section 4.2 provide theoretical guarantees for post-hoc methods based on kernel techniques, which have attracted attention in recent years (Wenger et al., 2020; Gruber & Bach, 2025).
The main focus of the paper is the control of smooth CE when learning f on S but Section 3's analysis extends directly to the generalization behavior of post-hoc calibrated models based on S.e.
K EXPERIMENT
In this section, we numerically validate our theoretical findings regarding smooth CE for GBTs and two-layer neural networks presented in Section 4.
We evaluate the behavior of several metrics on both training and test datasets, including cross-entropy loss, accuracy, functional gradient norm (denoted as "Func Grad" in the experiments), and binning ECE, MMCE, and smooth CE. These evaluations are conducted by varying the number of iterations T and the training dataset size n. Each experiment is repeated 10 times with different random seeds, and we report the mean and standard deviation.
For the binning ECE, we use 10 equally spaced bins. For MMCE, we use the Laplacian kernel with bandwidth set to 1. Definitions and additional details of the calibration metrics are provided in Appendix B.
K.1 GRADIENT BOOSTING TREES
We conduct numerical experiments on the Gradient Boosting Tree with cross-entropy loss, as described in Algorithm The main objective is to investigate how the training and test smooth CE behaves on both toy and real datasets, as predicted by Theorem 3 and Corollary 2.
The toy dataset consists of two classes with equal probability, i.e.,
P(Y = 0) = P(Y
2
47

---

Published as a conference paper at ICLR 2026
Given the class label Y {0, 1). the conditional distribution of X E RR is:
([
-1.3
(122-133)
x Y 0 N
-1
0
1.28
1.22
0
x|Y=1~N
(34)
1.3
0
(1.2
1122-11 1.3)
First, we set m = 3 and present the results in Figure 1. In Figure (a)), we fix the training dataset size (n 200) and increase the number of boosting iterations T. The left panel shows the behavior of the metries on the training dataset, the middle panel shows the same metrics on the test dataset, and the right panel reports the generalization gaps for both log loss and smooth CE. From the left panel, observe that both the cross-entropy loss and smooth CE decrease T increases, consistent with Theorem 3. In contrast, the middle panel shows that neither metric necessarily decreases on the test dataset as T increases. This is consistent with the well-known overfitting behavior of boosting, and demonstrates that smooth CE exhibits overfitting trends similar to those of the cross-entropy loss, as predicted by Corollary 2. The right panel confirms this overfitting phenomenon for both cross-entropy loss and smooth CE.
Next, investigate how these metrics behave the training sample size increases. The results are shown in Figure 1(b). We observe that the test calibration metrics decrease monotonically as n increases, indicating improved generalization. These results show that GBTs, when trained with sufficient samples, can achieve both high accuracy and low smooth CE.
Train Metrics
Metric
Cap Text Train
Cras Eokier
Mers
Draing
Goe Gemsg Ca
Iteration
oteracoon
Ioerazion
(a) Increasing the number of iterations T
Train Metrica
Mitrics
Cap
Trait
Feery
Ove
Srech EE
Trinnng Samole Size
Training Sample Size
Training Samole Size
(b) Increasing the number of training samples n
Figure 1: GBT experiments on the toy dataset defined in Eq. (34) with m 2 d
Next, we set m = 1, which shallow since m < d. The results are shown in Figure We can see that the behavior of the calibration metrics seems similar to that of m = 3 2 d.
Next, using the UCI Breast Cancer dataset, we observed how the metries behave on the training and test datasets by increasing the number of iterations T while keeping the training dataset size fixed. The results are shown in Figure 3. Since = 30 in this dataset, we considered two settings: (i) m 30, which is not shallow m d, and (ii)
which is shallow since m d.
We found that the results closely resemble those of the toy dataset in Figure 1. This implies that both shallow and not-so- trees behave similarly in this setting.
Finally, we also remark that the binning ECE, smooth CE, and MMCE exhibit similar behavior across all experimental settings. This observation is consistent with the discussion in Appendix B.
48

---

Published as a conference paper at ICLR 2026
Metrics
Metrics
Gap
Trah
Cres Eniw
for Mars
UAKT
Oe
Iteration
oneratioo
Iteration
(a) Increasing the number iterations T
Menrics
Tieit
Senay Eay
Triinig Samole Size
Traising, Sample
Training Samule
(b) Increasing the number of training samples
Figure GBT experiments on the toy dataset defined in Eq. (34) with m
Tran Meerics
Metrics
Gap
Tran
Onee Enew Mar uarr
Cos Errop
Oa
LE
Iteration
Ieration
Ioeration
(a) Increasing the number iterations T (m 30, m 2 c)
Train Metrica
Tes Matrics
Gap Between Test and Train
Ancwy
Iteation
(b) Increasing the number of iterations T (m < d)
Figure 3: GBT experiments for UCI breast cancer dataset d 30
49

---

Published as a conference paper at ICLR 2026
K.2 NUMERICAL EXPERIMENTS OVER TWO-LAYER NEURAL NETWORK
We conducted similar experiments using a two-layer neural network corresponding to Section 4.3. We prepared the toy dataset and designed the two-layer neural network to satisfy Assumption 1 in Appendix H. We used the sigmoid activation function, initialized the parameters independently from the standard Gaussian distribution, and set the number of hidden units to be even to satisfy Assumption (A3). The coefficients or were also set according to the specification in Assumption (A3). Unless otherwise stated, we used 300 hidden units. We used full-batch gradient descent (GD) for optimization with a fixed step size of w = 0.01.
First, we performed experiments on the same toy dataset used for GBTs. We evaluated the training and test metrics by increasing the number of GD iterations while fixing the training dataset size (n = 200). Figure 4(a) reports the same set of metrics as the GBT experiments (Figure 1). We observed that the smooth CE decreases monotonically, consistent with the upper bound behavior predicted by Eq. (6). However, from the middle and right panels of Figure 4(a), we observe that the test smooth CE does not decrease as the number of training iterations increases. We also confirmed that the generalization gap of the cross-entropy loss increases as T increases. According to Eq. (31), the complexity term grows with the number of iterations, which may explain this phenomenon. On the other hand, we did not observe an apparent increase in the generalization gap of the smooth CE as T increased.
Next, we varied the training dataset size, and the results are shown in Figure 4(b). From the middle and right panels, we observe that both the test smooth CE and the generalization gap decrease monotonically as n increases. This is consistent with the theoretical discussion provided in Appendix H.
Train Metric
Metrics
Cap Retwrent Text Train
Deneay fow
lteratio
Ileration
Tuextion
(a) Increasing the number of iterations '''
Train Metrics
Test Metrics
Gap Between Test and Train
Spopl Socc
Sungle
(b) Increasing the number of training samples n
Figure 4: Two-layer neural network using toydata defined in Eq. (34)
The experiments in Figure 4 are based on toy dataset where the separability condition is easily
satisfied. Next, we consider a toy dataset in which the separability condition is more difficult to satisfy, constructed follows. Assume that is even and define no- - z Let He NN(0, o² 12) with a = 0.05 be shared random base vectors. Define two classes:
uno
x(0) Z, +
0.1
+
(0)
(0) ~ r12).
(35)
0.1
xx"
-2,
0.1
+of d0 ~N(,)
0.1
50

---

Published as a conference paper at ICLR 2026
with 0.01. Each x;") is labeled Y 0, and each x is labeled Y Due to the symmetric structure of the data, this setting makes the margin assumption more difficult to satisfy than in the previous toy dataset. The results are shown in Figure 5, where we increase the training dataset size and evaluate the relevant statistics on both training and test datasets. Even under this more challenging setting, we observe that the test smooth CE decreases monotonically.
Gap
Figure 5: Two--ayer neural network using toy dataset defined in Eq. (35)
Next, we used the UCI Breast Cancer dataset and evaluated various statistics on both the training and test datasets, following the same procedure as in Figure 4(a). Here, varied the number of hidden units from a relatively small size (10) to larger value (100). The results are shown in Figure 6.
Consistent with the results in Figure 4(a), observed that the training statistics decrease mono- tonically in both small and large hidden unit settings. However, the test statistics did not show any corresponding improvement.
Train Metrics
Test Metrics
Gap Between Tist and Train
Asariy
Seach da pv
Aconss
De OCC
Natalion
Blerationn
Tix aliinii
(a) Increasing the number of iterations when the hidden unit size 10
Train Metric
Metrics
Gap
Train
Ove Denocy
Grae Franle
Gral Now
Good Grtny
Itration
(b) Increasing the number of iterations 7 when the hidden unit size is 100
Figure 6: UCI breast cancer dataset d 30
51


Reviews:
[{"review_id": "uHEVu5iG5t", "reviewer": "Reviewer_Y9y6", "summary": "This paper presents a theoretical understanding of learning algorithms that can produce accurate and well calibrated results. The paper mainly focuses on Smooth Calibratin Error(smCE) and provides a uniform convergence bound to that. Also, this paper analyses classifiation and calibration performance of three representative algorithms gradient boosting trees, kernel boosting and two-layer neural networks.", "questions": "1. Explain the relation with lemma 7.6.\n\n2. Explain the inequality of both 2 and 3 in the weaknesses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "1. The paper attempts to provie a theoretical understanding between the relation of calinbration and classification and provided bounds of smCE. \n2. The paper analyses the conditions an algorithm needs for achieving both classification and calibration gurrantees. This is extremely crucial as calibration is very important in safety critical tasks.", "weaknesses": "1. There are issues in the proof of theorem 1. In line 999, the author has refered to Lemma 7.6 of  Blasiok et al. (2023) and justified the existence of an optimal soultion to the convex problem in equation 8. But the assocaiation with lemma 7.6 is not obvious. In the lemma 7.6 of Blasiok et al. (2023), $\\Pi(u,v,y)$ is a distribution function, hence $\\Pi(u,v,y) \\in [0,1]$. But, in line 997 the author has stated that $\\omega_i \\in [-1,1]  $.\n\n2. The inequality in line 1343 is not clear. Means how the inequality is being derived from line 1339. \n\n3.Same problem with the inequality in line 1357. \n\nOverall, the theoretical section is excessively long; however, the three issues mentioned above are particularly critical, as they undermine the validity of Theorem 1. Consequently, the soundness of Corollary 1 and Theorem 2 also comes into question.", "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": "JwD6U6XkpD", "reviewer": "Reviewer_oi3k", "summary": "1.\tThe authors derive a uniform convergence bound for smooth CE.\n2.\tThey prove that such training smooth CE can be bounded by the norm of the functional gradient of the loss evaluated on training data\n3.\tThey apply the theoretical framework to three representative algorithms for the binary classification closely tied to functional gradients.", "questions": "1. Can you compare with existing works that analyze the test accuracy or smooth CE to validate your results in Section 4?\n\n2. What guidance or improvement do the theoretical results (for example, Corollaries 3,4) bring to the algorithms in practice? Or could you design better algorithms to achieve both calibration and accuracy?\n\n3. Neural networks are known as non-calibrated, so calibration methods, such as temperature scaling and vector scaling, are proposed. Can the theoretical framework be applied to these post-hoc techniques, and what results can be derived?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides a solid theoretical guarantee for the calibration performance and the classification error for three standard binary classification algorithms.", "weaknesses": "1. The technical novelty of deriving the results in Section 4 is not clear. In Section 4, the authors present the connection between functional gradients and the smooth CE and derive the convergence rates for three example models. These results heavily rely on the existing conclusion and analysis, but it should be clarified which contents are novel and important contributions, and why they are. \n\n2. Lack of comparison for the uniform convergence results with the previous ones.", "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": "pfiwsCGwUc", "reviewer": "Reviewer_J6Qt", "summary": "This paper presents a two part framework for smooth calibration error or smCE (for the binary case). It first provides uniform convergence bounds that control the population level smCE by training smCE plus a generalization gap that depends on the hypothesis class. The arguments involve standard chaining number, Dudley entrop-integral type techniques (standard Kolmogorov-Tikhomirov fare) for showing a Rademacher bound. Second, it presents a functional gradient view that provides an upper bound on the training smCE by norms (of functional gradients) for proper losses. This can result in concrete guarantees for gradient boosting machines, kernel boosting, and two layer NNs (NTK regime), Under clearly articulated margin assumptions, appropriate values for T, w, and n, we get $\\epsilon$-smCE and $\\epsilon$ misclassification simultaneously. This teases out a clear optimization v capacity trade off. \n\nTo expand in more detail: The paper focuses on a proper loss setup, in particular on squared loss and cross entropy. smCE is defined as a supermum over 1-lipschitz post-processing of the prediction. This is connected to the post-processing gap under squared loss (Biasiok et al). For cross entropy, the dual smCE is defined on the logit with 1/4-lipschitz post-processing and the relation showing the gap is explained. Then a covering number argument is used to bound sup_f |smCE(f,Ste) − smCE(f,Str)|, avoiding explicit composition class Lip \\odot f. Theorem 1 provides a tail bound with an integral over log covering numbers of F (only F, not of Lip \\odot f), plus an O(1\\(sqrt(n))) term reflecting the Lipschitz part. Theorem 2 provides an alternative Rademacher bound. Again, the key point is that the bound depends on F and not on Lip \\odot F. The main observation is that training smCE equals a dual pairing between h(f(X)) and negative functional gradients. This means that small functional gradients imply small training smCE. After this three cases are explicated (GBT, kernel boosting, 2 layer NNs).", "questions": "In the dual post-processing gap relation (p.2), can the (2,4) constants be improved? Would tighter constants significantly change the optimization/complexity trade-offs later?\n\nThe first $C/\\sqrt(n)$  term is attributed to the Lip class. Is it possible to expose the exact constant (and L dependence) and show whether it is improvable by structure in h (e.g. by monotonicity)? \n\nIf $\\gamma$ is small/zero (heavy overlap, label noise), do functional-gradient controls still yield non-trivial smCE bounds (perhaps with slower rates) via early stopping or other regularization?\n\nIs it possible to restate Theorem 4’s population term explicitly in terms of eigen-decay (like effective dimension $N(\\gamma)$. It might be useful to help pick kernels.\n\nWhat breaks in the analysis if we move to softmax?\n\nFor the Dudley chaining analysis, and some of the other standard arguments, please provide in-line citations.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the conceptual clarity of the paper, although I can't say I am extremely familiar with the theoretical literature here. It links calibration to functional gradients, turning calibration control into optimization-style quantities.\n\nThe uniform convergence bounds only depend on  F (plus a small fixed term).\n\nThe results for the three cases are interesting and non-trivial and make the framework concrete, with explicit T, w, n, choices and accuracy-calibration trade-off.", "weaknesses": "The margin assumptions (classification-style) are strong for a calibration question. Many realistic miscalibration settings lack separability. (pages.4–8)\n\nI found the kernel dependence opaque. The population bounds hide kernel spectrum dependence. \n\nAnother weakness has more to do with NTK than the framework itself.: Finite-width and feature-learning behaviors would have been interesting to discuss. \n\nThe dual smCE <> post-processing gap constants are not discussed for tightness. The $C/\\sqrt(n)$ term's origin and size is not specified enough (unless I missed it).", "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": "LYCREC6UBq", "reviewer": "Reviewer_hJEU", "summary": "The paper adds on to the accumulating evidence on the connection between loss minimisation and calibration. They adopt smooth calibration error and derive the uniform convergence result to relate the training set calibration error to test time error, and then show that training set smooth calibration error can be studied in connection to functional gradient. While the insight is simple, in hindsight, this helps answering some questions as to when one can get better predictors (accuracy wise) while also being calibrated, and the paper develops results for boosting (gradient and kernel) and two-layer neural networks. There is an extensive amount of work and details in the appendix as well (which I didn't carefully check) but also the experimental demonstration.", "questions": "see above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.This is a strong paper, that helped answer some of my own questions on the connections between loss minimisation and calibration. My favourite part is the connection to functional gradient. \n\nQuestion wise: is it fair to conclude that loss minimisation will yield calibration together with good performance if the training resembles that of the functional gradient descent or some approximation of it? In that sense, an earlier paper by (Błasiok et al., 2023; when does minimising proper losses yield calibration) argued for the emergent calibration behaviour in modern large neural networks, and how do the current functional gradient analysis add on to that?\n\n\nOverall, I think this is a good paper, with not much concerns, and I think this should be accepted.", "weaknesses": "1. The paper misses to mention [1]. While the focus of this paper is re-calibration, I think they also study the generalisation of calibration error, and might be worth to look at. \n2. While the focus of the paper is theoretical, could the study give some concrete practical guidance to design predictors to achieve both calibration and better accurate predictors. \n\n\n\n[1] Masahiro Fujisawa, Futoshi Futami. PAC-Bayes Analysis for Recalibration in Classification. ICML 2025", "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)