Abstract
Boosted Additive Models (BAMs) are a cornerstone of modern interpretable machine learning, blending the flexibility of gradient boosting with the transparency of additive structures. However, the theoretical foundations of these models—specifically their optimization targets and behavior in complex settings—have remained under-explored. This paper bridges the gap between empirical success and theoretical understanding. We provide rigorous convergence proofs, derive new linear convergence rates by linking boosting to coordinate descent, and uncover "pathologies" where models can diverge if the learning rate is improperly tuned. Crucially, we show that penalized boosting eventually converges to unpenalized solutions, highlighting the necessity of early stopping.
Introduction
While linear boosting is well-understood, modern BAMs often incorporate complex components like P-splines (penalized splines) and handle non-Gaussian data (e.g., Poisson or Binomial distributions). A common assumption among practitioners is that "penalized boosting" implicitly finds a model with an optimal smoothing parameter. However, theoretical evidence for this has been lacking. Schulte and Rügamer address this by defining the optimization problem BAMs solve at each step and establishing the conditions under which they are guaranteed to converge.
Methods
The authors analyze $L_2$-Boosting and its variants through the lens of optimization theory. Key methodological contributions include:
- Exact Path Derivation: Closed-form expressions for parameter paths in boosting with quadratic penalties.
- Optimization Equivalence: Establishing a formal link between greedy block-wise boosting and Greedy Block Coordinate Descent (GBCD) via the Gauss-Southwell-Quadratic (GSQ) update scheme.
- Convergence Theory: Utilizing the $\mu$-PL (Polyak-Łojasiewicz) inequality and $L$-smoothness conditions to prove linear convergence rates for block-wise boosting, even in high-dimensional settings.
- Hessian Analysis: Examining how boosting implicitly approximates the Hessian of the loss function, which is vital for stability in non-Gaussian models.
The Unpenalized Trap
A significant finding of the paper is that boosting, if run to convergence, will reach the unpenalized solution (e.g., Ordinary Least Squares), even when base learners utilize penalties like P-splines. The regularization in boosting is primarily a product of early stopping, not the internal penalties of the base learners.
As shown in the analysis of Covid-19 prevalence data, as the number of boosting iterations increases, the model fit moves away from the smooth P-spline solution and converges toward the noisier, unpenalized B-spline solution. This demonstrates that the "smoothness" intended by the penalty is lost without careful early stopping.
Pathologies and the Learning Rate
In non-Gaussian models, such as Poisson regression, the loss function lacks global smoothness. The authors identify a "pathology" where the implicit Hessian approximation used by boosting becomes inaccurate if the learning rate ($\nu$) is too high.
Experimental results validate this theoretical warning: higher learning rates lead to significant oscillations or total divergence in Poisson BAMs. A "sufficiently small" step size is therefore a theoretical and practical necessity for maintaining model stability in these contexts.
Key Results and Insights
- Linear Convergence: The paper provides the first explicit convergence rates for regression spline problems fitted via GBCD/Boosting.
- Implicit Regularization: At any iteration $k$, boosting is shown to be the unique solution to an explicitly regularized optimization problem, though this "penalty" evolves at every step.
- Boosting vs. Ridge: The authors clarify that boosting and Ridge regression paths only align under the rare condition of isotropic features; in most real-world scenarios, they explore distinct regions of the model space.
Conclusion
This work provides a rigorous framework for understanding the mechanics of Boosted Additive Models. While it characterizes the solution paths and convergence properties, the authors note that formal statistical inference (e.g., confidence intervals) for boosted models remains an open challenge. Future research may leverage the explicit objective functions derived here to develop post-selection inference tools.
Summary updated