ITBoost: Information-Theoretic Trust for Robust Boosting

1 Introduction

Gradient Boosting Decision Tree (GBDT) have emerged as the standard for structured data modeling, delivering state-ofthe-art performance across a wide range of machine learning tasks [Bent´ejac et al., 2021; Shwartz-Ziv and Armon, 2022]. The effectiveness of these algorithms lies in their iterative learning paradigm, specifically, by sequentially training weak learners to fit the residuals of the ensemble formed by previous learners [Friedman, 2001]. A core driver of this process is the model's continuous effort to address its own prediction errors: the magnitude of the gradient essentially guides where the model focuses its learning attention in the next iteration.

∗Corresponding authors

Yet, this focus on prioritizing large gradients stands out as a key flaw in gradient boosting. Label noise often causes sharp, even catastrophic, performance declines [Long and Servedio, 2008; Miao et al., 2015; Einziger et al., 2019]. Mislabeled samples are persistent sources of error, and their large gradients slowly lead the model astray. Figure 1 clearly shows this problem: as noise levels rise from 10% (a) to 30% (b), the decision boundary of a standard GBDT becomes fragmented. Here, the model's rigid reliance on gradient magnitude as a guiding cue leads it to distort its structure to fit noisy samples (marked "X"), a choice that severely undermines generalization. This is not just an edge case: label noise is far from uncommon in practical fields like medicine and finance. As such, GBDT's vulnerability poses a major obstacle to its real-world use [Fr´enay and Verleysen, 2013; Shi et al., 2024].

Current efforts to tackle this issue rely on either robust loss functions [Huber, 1992; Zhang and Sabuncu, 2018] or sample selection strategies [Ferreira and Figueiredo, 2012; Dubout and Fleuret, 2014; Liu et al., 2020], but these approaches fall short of addressing the core issue. They still rest on the flawed premise that gradient magnitude alone dictates a sample's relevance to the true decision boundary. This presents a challenge that's hard to resolve: algorithms cannot tell apart two types of samples that both yield large gradients-genuinely valuable hard examples sitting close to the decision boundary, and erroneous noisy samples with incorrect labels [Song et al., 2022]. If we blunt all large gradients outright, we end up hampering the model's ability to learn from critical hard examples; if we accept them uncritically, noise will inevitably corrupt the model's learning process.

In response to this dilemma, we question this foundational assumption and advance a new perspective: a sample's gradient reliability should not hinge on its immediate magnitude, but rather on how interpretable its error history is. Hard examples, while tough to learn, produce residual sequences with recognizable structural patterns. By contrast, noisy examples, intrinsically misaligned with the true data distribution, result in far more erratic prediction errors. Drawing on this observation, we introduce Information-Theoretic Trust Boosting (ITBoost). ITBoost assigns a "trust score" to each sample's gradient. Instead of only asking, "How large is the sample's error?", we shift focus to: "How trustworthy is the historical pattern of its errors?" To formalize this question, we adopt the Minimum Description Length (MDL) principle from information theory [Rissanen, 1978; Gr¨unwald, 2007]. Concretely, we compute the sequential complexity of each sample's residual trajectory online, using the Lempel-Ziv algorithm [Gasieniec et al., 1996] to quantify randomness. A random, uncompressible residual sequence (high complexity) flags the sample as "untrustworthy," prompting us to reduce its weight in the learning process. This new weighting mechanism lets ITBoost effectively de-emphasize noise while still prioritizing genuinely challenging yet informative samples. Our key contributions are summarized below:

• We introduce ITBoost, a robust boosting method that tackles label noise at its root by leveraging an information-theoretic trust framework, an innovative departure from standard boosting.
• We develop an MDL-based sample weighting mechanism; uniquely, this mechanism uses residual time-series characteristics instead of instantaneous values to guide the boosting process.
• We provide theoretical justification for ITBoost, demonstrating that it achieves a tighter generalization error bound than standard GBDT when label noise is present.
• We show that ITBoost delivers optimal performance and robustness, outperforming leading boosting algorithms and modern deep tabular models in noisy environments.

2 Information-Theoretic Boosting

Our work is based on the insight that instantaneous gradient magnitude is an insufficient metric, and often misleading, for assessing a sample's true importance. Indeed, a large gradient may indicate just as readily a valuable, hard-to-learn case as it does a corrupted, noisy counterpart. To clear up this ambiguity, we propose leveraging the full history of a sample's learning trajectory to underpin our assessment of its importance.

2.1 FromGradient Magnitude to Residual History

Let us frame the learning process through a temporal lens. For each sample xi, the sequence of pseudo-residuals, gi = (g(1) i , g(2) i , . . . , g(M) i ), constitutes a time series documenting how the model's understanding of that sample evolves over iterations. What we argue here is that the traits of this time series hold far more information about the sample's inherent nature than the magnitude of any single residual element alone.

• Hard but Clean Samples. Authentic hard samples exhibit low-complexity residual structures. Specifically, (i) boundary samples induce structured sign oscillations as the decision boundary is progressively refined, while (ii) persistent hard samples generate stable, monotonic residual sequences due to systematic model underestimation. Although these samples are difficult to learn, both residual patterns are highly compressible and thus have low algorithmic complexity. Guided by the MDL principle, ITBoost correctly identifies them as reliable and assigns higher weights, directing the model toward these valid yet challenging cases.
• A Noisy Sample. Samples with corrupted labels conflict with the underlying feature structure. Attempts to fit such data lead to erratic and unpredictable model adjustments, producing residual sequences with chaotic sign flips and no discernible pattern, indicative of high complexity. This behavior clearly distinguishes noisy samples from both the structured oscillations of boundary samples and the stable persistence of hard clean samples.

It is this fundamental distinction in the temporal signature of residual sequences that forms the core insight underpinning our work. An unpredictable, random-like sequence is a strong indicator that the model's errors stem from label corruption, rather than being an integral part of the structured learning process.

2.2 Quantifying Trust with Algorithmic Complexity

To formalize this intuition, we measure the randomness of a sequence using its algorithmic complexity. The Kolmogorov complexity [Kolmogorov, 1965; Li and Vit´anyi, 2008], K(s), of a sequence s is the length of the shortest program that generates s. Since K(s) is uncomputable, we employ a practical approximation: the Lempel-Ziv (LZ) complexity, which effectively measures a sequence's compressibility [Wyner and Ziv, 2002; Zozor et al., 2005].

At each iteration m, we consider the binarized residual history for each sample i, s(m) i = (sign(g(1) i ), . . . , sign(g(m) i )). This binarization is a crucial design choice, as it intentionally discards the noisy and volatile error magnitude to focus purely on the temporal pattern of the error's direction-a more stable and robust signal of a sample's learning trajectory. We then compute its LZ complexity, C(s(m) i ). We define the information-theoretic trust weight, w(m) i , as the product of the gradient magnitude and a trust term, τ (m) i :

where the trust term is an exponential penalty based on the normalized complexity of its history:

Here, ¯ C(s(m) i ) is the LZ complexity, normalized to the range [0, 1] across all samples at iteration m. This formulation allows ITBoost to temper the influence of samples that have proven to be historically unreliable.

To compute this normalized complexity, we employ a dynamic Min-Max scaling procedure at each boosting iteration m. For the set of raw LZ complexities {C1,C2, . . . ,CN} computed at step m, the normalized complexity for sample i is given by:

This per-iteration, relative normalization is a critical design choice. A key implication is its adaptive response to outliers. It pins the noisy sample's normalized complexity near 1.0, ensuring it receives a significant trust penalty via the exponential term e-¯ Ci . It compresses the normalized complexities of most clean samples into a narrow band close to 0, thereby shielding them from undue penalization. This dynamic, outlier-driven normalization thus enhances the separation between trustworthy and untrustworthy samples in the trust domain, enabling a more targeted and aggressive suppression of noise.

2.3 Algorithm Summary

The complete ITBoost algorithm is presented in Algorithm 1. The key modification to the standard GBDT framework is the introduction of Step 3, where the information-theoretic

Algorithm 1 The ITBoost Algorithm

• 1: Initialize F0(x) ← argminc ∑Ni=1 L(yi, c).
• 2: Initialize empty residual histories si ← "" for i = 1, . . . ,N.
• 3: for m= 1 toM do
• 4: Step 1. Compute pseudo-residuals:
• 5: g(m) i ←- [ ∂L(yi,F(xi)) ∂F (xi) ]F (x)=Fm-1(x)
• 6: Step 2. Update binarized residual histories:
• 7: si ← si ◦ (′ 1′ if g(m) i > 0 else ′ 0′ )
• 8: Step 3. Compute information-theoretic trust weights:
• 9: Compute LZ complexity for each history: Ci ← LZ-Complexity(si).
• 10: Normalize complexities across samples: ¯ Ci ← Normalize(C1, . . . , CN) to [0, 1].
• 11: Compute final weights using Eq. (1): w(m) i ← |g(m) i | · exp(- ¯ Ci).
• 12: Step 4. Train weak learner hm(x) on pseudoresiduals using trust weights:
• 13: hm ← arg minh∈H ∑Ni=1 w(m) i · (g(m) i -h(xi))2 14: Update the ensemble: Fm(x) ←Fm-1(x)+ν·hm(x).
• 15: end for
• 16: Output: FM(x).

trust weights are computed. These weights are then used to guide the training of the weak learner in Step 4, replacing the implicit weighting by gradient magnitude in the standard squared-error loss minimization.

3 Theoretical Analysis

In this section, we provide theoretical justification for the robustness of ITBoost. We demonstrate that our informationtheoretic weighting scheme leads to a tighter generalization error bound under a standard model of label noise compared to traditional GBDT.

3.1 Assumptions

Let F be the function class of the final ensemble, which is the convex hull of the base learner class H. We analyze the generalization error, Ex,y[ℓ(y, F (x))], where ℓ is the 0-1 loss. Our analysis will be based on a surrogate loss, the logistic loss L(y, F) = log(1 + exp(-yF)), for y ∈ {-1, 1}, which is convex and 1-Lipschitz. We adopt a standard model for label noise:

Assumption 1 (Symmetric Label Noise). The observed labels yi in the training set D are generated from the true (clean) labels y∗ i according to an independent process, such that for a noise rate p ∈ [0, 1/2):

Our key insight is that noisy samples will, with high probability, exhibit more complex residual histories. We formalize this by assuming that the expected complexity of a noisy sample's residual history is higher than that of a clean sample.

Assumption 2 (Complexity Separation). Let C(si) be the LZ-complexity of a sample's residual history. There exists a gap ∆C > 0 such that the expected complexity conditioned on the label being noisy versus clean is separated:

Remark (Scope of Noise Types). It is important to clarify that Assumption 2 is specifically tailored to stochastic or unstructured label noise, the primary type of label noise observed in practical real-world scenarios. In such cases, conflicts between features and their corresponding labels introduce randomness into the model's learning dynamics. A notable limitation, however, emerges when dealing with systemic or adversarial noise. This kind of noise tends to generate stable, low-complexity residual patterns, which bear resemblance to the persistent hard samples discussed in Section 2.1. Notably, without clean validation data or additional external supervision, purely data-driven methods cannot inherently distinguish such structured corruptions from genuine hard examples. Consequently, this category of structured noise falls outside the scope of this work.

This assumption posits that our complexity measure is a meaningful signal for identifying noise, a hypothesis we validate empirically in Section 4. In Eq. (4), we assumed that the expected residual complexity of noisy samples is strictly greater than that of clean samples. While this assumption aligns with intuitive reasoning, it is relatively strong and lacks explicit conditions that guarantee the separation ∆C > 0. To this end, we reformulate the original assumption into two equivalent, verifiable variants, which also allow for finitesample probabilistic guarantees.

Assumption 3 (Entropy-Rate or Empirical Separability). Let each sample i produce a residual-sign sequence S(T) i = (si,1, ..., si,T ) with normalized complexity ̂ CT (Si) ∈ [0, 1]. We assume one of the following holds:

(A) Entropy-rate gap. Residual sequences for clean and noisy samples can be modeled as two stationary ψ-mixing processes with entropy rates Hclean and Hnoisy, satisfying Hnoisy -Hclean ≥ ∆H > 0. Under the standard Lempel-Ziv consistency theorem [Wyner and Ziv, 2002], the normalized complexity estimator ̂ CT converges exponentially to the true entropy rate:

so for sufficiently large T, we obtain a probabilistic separation E[ ̂ CT | clean] ≥∆c > 0 with ∆c ≃∆H -2ϵT .

(B) Empirical separability. For finite samples, if ̂ CT ∈ [0, 1], let ¯ Cclean and ¯ Cnoisy denote the empirical means. Then, by Hoeffding's inequality,

Hence, whenever the true expectation gap ∆⋆c > 2ϵ, the empirical means are separable with probability at least 1 - δ, provided n ≥ 1 2ϵ2 log 2δ .

These two formulations replace the untestable Kolmogorov-complexity gap by measurable or statistically verifiable criteria. Empirical separability (B) can be directly checked in experiments, while the entropy-rate formulation (A) connects to the asymptotic theory of universal compression.

3.2 Generalization Bound under Label Noise

With these assumptions, we first establish the statistical properties of our trust weights. The following lemma characterizes the behavior of the trust term τ derived from the complexity random variable.

Lemma 1 (Hoeffding / sub-Gaussian bounds for τ). Let C be a real-valued random variable with mean µ = E[C] and define τ := E[e-C ]. Then:

1. Jensen lower bound: Because f(x) = e-x is convex, τ ≥ e-µ .
2. Bounded-range upper bound: If C ∈ [a, b] with range R = b - a, Hoeffding's lemma gives τ ≤ exp(-µ + R2 /8).
3. Sub-Gaussian upper bound: If C - µ is σ2 -subGaussian, then τ ≤ exp(-µ+σ2 /2).

This lemma makes explicit that the expected trust weight τ is tightly constrained by the expected complexity µ. Specifically, an increase in residual complexity brings about an exponential decay in the upper bound of the trust weight-which in turn furnishes the mathematical basis needed to justify the use of complexity scores for downweighting samples.

Proof. The detailed proof is provided in Appendix A.1 in supplementary material, please.

Based on Lemma 1, we quantify the relative weighting of noisy versus clean samples.

Proposition 1 (Ratio bound for noisy vs. clean samples). Let Cnoisy and Cclean denote the residual-complexity variables of noisy and clean samples, with expectations µnoisy and µclean. Define the complexity gap ∆c = µnoisy - µclean > 0. Then, if both C's lie in [a, b] or are σ2 -sub-Gaussian:

where corr is a small correction term related to the variance or range of C.

What this proposition makes clear is that, as long as the complexity gap ∆c surpasses the correction term (derived from variance), noisy samples will be down-weighted exponentially in comparison to clean ones. This mechanism lays theoretical groundwork for the algorithm's capacity to suppress noise influence, guiding gradient updates to align more closely with the direction dictated by the clean data distribution.

Proof. We provide the full derivation in Appendix A.2 in supplementary material, please.

Finally, we state our main theoretical result regarding the generalization error.

Theorem 1 (Quantitative Effect of Complexity Separation). Assume the loss ℓ is L-Lipschitz, weak learners are bounded by B, and the trust-weight mapping is Lipschitz. Under Assumption 3, if ∆c > 0 and complexities are sub-Gaussian, then the expected empirical risk improvement per boosting iteration satisfies:

Theorem 1 indicates that the generalization risk improvement is explicitly dependent on the complexity gap ∆c. The term -LLgB∆c represents a risk reduction derived from the separation between noisy and clean complexities. This suggests that larger separability contributes to more robust convergence, offering a theoretical basis for ITBoost's performance in noisy environments compared to standard GBDT which lacks this complexity-aware regularization.

Proof. The complete proof is deferred to Appendix A.3 in supplementary material, please.

4 Experiments

In this section, we conduct a comprehensive empirical evaluation to validate the performance of ITBoost. The primary goal of this section is to answer a critical question: Does our information-theoretic trust mechanism, designed for robustness, maintain optimal performance on clean and noise datasets? (Section 4.2 and 4.3). Additionally, we conduct an ablation study for residual binarization (Section 4.4) and visualize the information-theoretic trust mechanism of ITBoost (Section 4.5). Additionally, we provide the complexity and efficiency analysis (Section B) in supplementary material. To ensure statistical significance, all comparative results are validated using Friedman tests (Section C) in supplementary material.

Implementation and Reproducibility. All experiments were conducted locally using Jupyter Notebook in an Anaconda environment on Windows 10 (Version 10.0.19045). The hardware infrastructure utilized an Intel processor (Intel64 Family 6 Model 151 Stepping 2, GenuineIntel) equipped with 20 logical cores. The software stack was built on Python 3.12.4, utilizing the following key libraries: pandas 2.2.2, numpy 1.26.4, scikit-learn 1.7.2, statsmodels 0.14.2, imbalanced-learn 0.14.0, lightgbm 4.3.0, xgboost 2.0.3, catboost 1.2.3, ngboost 0.5.7, and tabpfn 6.0.6.

4.1 Setup

Dataset. We used five different datasets from OpenML repository, which are all publicly available. These datasets include Madelon (2,600 samples, 500 features) [Guyon et al., 2007], Jasmine (2,984 samples, 144 features), Bioresponse (3,751 samples, 1,776 features), Creditcard (284,807 samples, 30 features) [Dal Pozzolo et al., 2015], and the OVA Uterus (1,545 samples, 10,936 features) [Stiglic and Kokol, 2010]. We employed random undersampling [Hasanin and Khoshgoftaar, 2018; Liu and Tsoumakas, 2020] to address class imbalance in the Creditcard and OVA Uterus datasets.

Baselines. We compared ITBoost against a comprehensive suite of SOTA tabular learning algorithms. This includes six established boosting methods: AdaBoost (ADA) [Freund and Schapire, 1997], GBDT, XGBoost (XGB) [Chen et al., 2015], LightGBM (LGBM) [Ke et al., 2017], CatBoost (CAT) [Prokhorenkova et al., 2018], and NGBoost (NGB) [Duan et al., 2020]. Additionally, we included TabPFN [Hollmann et al., 2025], a recent Transformer-based priordata fitted network, to benchmark our method against modern deep tabular foundation models. Note that specialized robust boosting variants (e.g., RobustBoost) are excluded from this comparison due to the lack of maintained open-source implementations, consistent with standard practice in recent literature [Luo et al., 2025]. A detailed discussion of these related works is provided in Appendix D. For a fair and reproducible comparison of the algorithms' intrinsic capabilities, we were configured with "random state=42" to ensure reproducibility, with all other parameters set to the official recommendation values provided by the respective software packages (e.g., Scikit-learn). The proposed ITBoost algorithm was configured in the same manner, following an official setup consistent with these baselines. We did not optimize the parameters of any algorithms. This approach evaluates the fundamental "out-of-the-box" performance of the underlying architectures, a crucial factor for practical applications.

Evaluation Protocol. We employed a 5-fold stratified cross-validation protocol for all experiments. The performance of each algorithm was reported as the mean and standard deviation across the five folds and the best results were highlighted in bold, second best are underlined. The primary evaluation metrics were Accuracy (ACC), F1-Score (F1), Area Under the ROC Curve (AUC), and Logarithmic Loss (Log Loss).

4.2 Overall Performance

Table 1 presents the performance comparison of ITBoost against seven SOTA algorithms. The results revealed a clear performance hierarchy. Among the traditional boosting families, ADA generally yielded the lowest performance, while CAT and LGBM demonstrated strong competitiveness. Notably, the recent Transformer-based TabPFN demonstrated strong performance, frequently securing the second-best results. However, ITBoost outperformed all baselines across nearly all datasets and metrics. The performance gap was particularly striking on the Madelon dataset, where ITBoost achieves an accuracy of 92.04% compared to 84.38% for the best GBDT baseline (CAT) and 90.50% for TabPFN. Since Madelon is a synthetic dataset known for its high dimensionality and abundance of uninformative, distracting features (feature noise), this result is highly significant. It suggests that our information-theoretic trust mechanism is not only effective against synthetic label flipping (as we will explore in Section 4.3) but also inherently robust against intrinsic data corruption and spurious correlations. By identifying the chaotic residual patterns caused by these noisy features, ITBoost effectively acts as a dynamic noise filter on the "clean" data.

4.3 Robustness Analysis

Figure 2 shows the robustness of leading boosting methods and deep tabular model (TabPFN) under three noise conditions: symmetric label noise, asymmetric label noise, and feature noise on the Jasmine dataset. These results exhibited that, as the noise rate escalates, leading boosting methods exhibit a consistent drop in performance. Notably, while TabPFN outperformed leading boosting methods, it still displayed clear vulnerability, with a more pronounced decline observed under severe asymmetric noise. However, ITBoost maintained consistently high performance even at extreme noise levels, retaining a substantial advantage over leading ensembles and TabPFN. Such empirical evidence provides robust support for our core hypothesis. Leading boosting methods are prone to being misled by spurious correlations: GBDTs rely heavily on gradient magnitude, while TabPFN's fixed priors fail to adapt to instance-specific corruptions. ITBoost's information-theoretic trust mechanism, by contrast, effectively distinguishes the erratic error patterns generated by noisy samples. Through systematically down-weighting the influence of these samples based on residual complexity, ITBoost preserves the model's integrity and its capacity to capture the stable underlying data structure-ultimately achieving optimal robustness and maintaining optimal performance in scenarios where existing SOTA methods struggle or fail.

4.4 Ablation Study

A core design choice underpinning ITBoost's robustness lies in the binarization of residual history: this design intentionally discards error magnitude to focus exclusively on the temporal pattern of error directions. We further validate the necessity of this simplification, whether it is critical for robustness or causes detrimental information loss, through an ablation study. Specifically, we compare ITBoost-Binary with ITBoost-Quantized, a variant that retains magnitude information via four-symbol encoding. On clean Jasmine and Bioresponse datasets (Table 2), the two variants delivered comparable performance; ITBoost-Binary even achieved a slight edge while cutting training time by 20-25%, confirming no compromise to baseline effectiveness. Under label noise conditions (Figure 3), however, ITBoost-Binary outperformed the Quantized variant across all metrics. This performance gap widened as noise intensity increased, which confirms that gradient magnitude from mislabeled samples constitutes a spurious signal. By focusing solely on directional history, the binary formulation better captures the chaotic patterns linked to untrustworthy labels. Notably, this advantage fades under feature noise-highlighting that binarization serves as a targeted, effective defense specifically against label noise. In summary, these results demonstrate that binary residual encoding is not a detrimental simplification, but rather a targeted noise-filtering mechanism that underpins ITBoost's robust performance.

4.5 Inside ITBoost: AVisual Case Study

To provide a mechanistic understanding of our framework, Figure 4 visualizes the average weight evolution for representative sample types on the Jasmine dataset with 20% noise. The result revealed theoretically consistent trajectories: the easy sample (blue) showed a gently increasing weight as the model solidifies its confidence, while the hard sample (orange) maintained a consistently higher weight, confirming the model correctly focuses on informative boundary points. The most compelling evidence lied with the noisy sample (green). It began with the highest weight due to its large initial error, but as the boosting iterations proceed and its residual history became demonstrably random, its weight entered a steep and continuous decline. This provides direct empirical validation of our core claim: the information-theoretic trust mechanism successfully identifies the noisy sample's chaotic error pattern as untrustworthy and systematically suppresses its influence, preventing it from dominating the learning process. This case study thus provides direct empirical evidence that our trust mechanism successfully differentiates valuable difficulty from misleading noise, validating the core principle behind ITBoost's robustness.

5 Conclusion

In this paper, we proposed ITBoost, a framework that redefines sample importance based on the historical trustworthiness of error sources rather than instantaneous residuals. By leveraging the MDL principle to quantify the complexity of residual trajectories, ITBoost effectively distinguishes informative hard examples from chaotic noise, systematically suppressing the influence of corrupted labels. Our theoretical analysis establishes a tighter generalization bound under label noise, while extensive empirical results demonstrate that ITBoost achieves optimal robustness in noisy environments without compromising performance on clean data. We acknowledge that real-time computation of Lempel-Ziv complexity incurs notable overhead, especially on large-scale datasets. Future work will improve scalability via approximate measures, sliding-window evaluation, and periodic trust updates. More broadly, information-theoretic trust opens several promising directions. Leveraging temporal learning dynamics is not limited to boosting: it can be adapted to deep learning for more robust optimizers, applied to curriculum learning to better identify genuinely difficult samples, and extended to online and continual learning to detect and respond to concept drift. By shifting from a static to a dynamic, history-aware notion of sample importance, this work lays the groundwork for a new class of more adaptive and resilient learning algorithms.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 62403043 and 42171323.