Boost Like a (Var)Pro: Trust-Region Gradient Boosting via Variable Projection

1. Problem Statement

Gradient Boosting (GB) has become the state-of-the-art method for tabular data, primarily using decision trees as weak learners. However, extending GB to smooth, parametric weak learners (such as neural networks) remains challenging due to:

• Optimization Complexity: Training parametric models involves navigating non-convex, high-dimensional landscapes where standard gradient descent often struggles with conditioning and convergence.
• Lack of Theoretical Guarantees: Existing methods for boosting neural networks often lack rigorous convergence analysis or rely on weak learning conditions that are difficult to verify in practice.
• Inefficiency: Standard boosting of neural networks often requires re-training or complex architectural adaptations, leading to high computational costs.

The authors aim to bridge the gap between function-space optimization (traditional GB) and parameter-space optimization (neural network training) to create a robust, theoretically grounded boosting algorithm for separable smooth approximators.

2. Methodology: VPBoost

The proposed algorithm, VPBoost (Variable Projection Boosting), integrates three core concepts: Gradient Boosting, Variable Projection (VarPro), and Trust-Region methods.

A. Separable Weak Learners

VPBoost operates on a specific class of models called separable approximators, defined as:
$$h(x; \theta, w) = A_\theta(x)w$$
Where:

• $A_\theta(x)$ is a nonlinear featurizer (e.g., a neural network backbone) parameterized by $\theta$.
• $w$ is a linear mapping (the final layer weights).
  This structure separates the nonlinear feature extraction from the linear combination, allowing for partial optimization.

B. Variable Projection (VarPro)

Instead of jointly optimizing $\theta$ and $w$, VPBoost uses VarPro to eliminate $w$ analytically.

1. Second-Order Approximation: At each boosting step $m$, the loss is approximated by a quadratic model $Q_N^{(m)}$.
2. Closed-Form Solution: Because the model is linear in $w$ and the loss is quadratic (locally), the optimal linear weights $w^*_m(\theta)$ can be solved in closed form:
   $$w^*_m(\theta) = -\left(H_\theta^{(m)} + \lambda_w I\right)^{-1} g_\theta^{(m)}$$
   Where $g$ and $H$ are the reduced gradient and Hessian with respect to the features, and $\lambda_w$ is a regularization parameter.
3. Reduced Optimization: The algorithm then optimizes only the nonlinear parameters $\theta$ using the reduced objective function $J^\downarrow_N(\theta) = J_N(w^*(\theta), \theta)$. This effectively "projects" the optimization onto the manifold of optimal linear weights.

C. Functional Trust-Region Interpretation

The authors reframe VPBoost as a functional trust-region method:

• The regularization parameter $\lambda_w$ in the closed-form solution acts as the inverse of the trust-region radius $\Delta$.
• The algorithm adaptively adjusts $\lambda_w$ based on the ratio of actual reduction to predicted reduction ($\rho$).
• If the quadratic model is a poor approximation (low $\rho$), $\lambda_w$ increases (shrinking the trust region), forcing smaller, more conservative steps.
• This mechanism ensures that the ensemble updates are always descent directions and prevents overfitting without manual hyperparameter tuning of step sizes.

3. Key Contributions

1. Unified Framework: VPBoost is the first algorithm to explicitly bridge function-space boosting and parameter-space VarPro. It aligns updates in the parameter space (optimizing $\theta$) with updates in the function space (minimizing the ensemble loss).
2. Robustness via Trust-Region: By interpreting the linear weight optimization as a trust-region subproblem, VPBoost automatically adapts the scale of weak learners. This reduces the number of hyperparameters (e.g., no need for manual learning rates or boosting rates) and improves stability.
3. Convergence Guarantees:
   • Stationarity: The authors prove that VPBoost converges to a stationary point of the loss functional under mild subspace regularity conditions (e.g., gradient alignment and curvature capture).
   • Superlinear Rate: Under stronger assumptions (asymptotic similarity to Newton steps), the algorithm achieves a superlinear convergence rate.
   • Distinct Conditions: Unlike previous works that require ensemble-level weak learning conditions (like Minimal Cosine Angle), VPBoost imposes conditions on individual weak learners during training, making the theory more applicable to on-the-fly design.
4. Algorithmic Efficiency: The closed-form solution for $w$ eliminates the need for iterative inner-loop optimization of the linear layer, significantly improving conditioning and training speed for the linear component.

4. Experimental Results

The authors evaluated VPBoost on synthetic data, image recognition (MNIST), scientific machine learning (CDR regression), and large-scale tabular data (Higgs boson classification).

• Performance: VPBoost consistently outperformed standard Gradient Descent Boosting (GDBoost) and various VP variants (where VarPro is applied only at the start or end).
• Comparison with XGBoost:
  • On tabular data (Higgs), VPBoost achieved competitive performance against XGBoost, despite XGBoost being the industry standard for such tasks.
  • On image data (MNIST) and scientific regression (CDR), VPBoost significantly outperformed XGBoost, demonstrating the advantage of smooth, smooth-featurizer-based ensembles over decision trees for these specific domains.
• Scalability: While the linear solve adds computational cost, VPBoost reaches target loss thresholds faster than GDBoost because each weak learner is significantly more accurate. The method scales well with output dimensionality in multi-output regression tasks.
• Robustness: VPBoost showed superior generalization and stability, particularly in high-dimensional or oscillatory function approximation tasks where decision trees struggle.

5. Significance and Future Directions

• Theoretical Advancement: This work provides a rigorous theoretical foundation for boosting neural networks, moving beyond heuristic approaches to a method with provable convergence properties rooted in trust-region theory.
• Practical Impact: VPBoost offers a viable alternative to decision-tree boosting for problems requiring smoothness (e.g., scientific computing, physics-informed ML) or where decision trees fail to capture complex boundaries (e.g., image data).
• Future Work: The authors identify scaling to very large output dimensions (e.g., pixel-level prediction) as a challenge due to the cubic cost of the linear solve. Future directions include integrating stochastic optimization, randomized sketching, and exploring generalization bounds for boosted separable neural networks.

In summary, VPBoost successfully fuses the efficiency of variable projection with the robustness of trust-region methods, creating a powerful, theoretically sound framework for boosting smooth parametric models that rivals or exceeds the performance of established tree-based methods.