Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models

• URL: http://arxiv.org/abs/2605.23422v1
• Date: Fri, 22 May 2026 09:33:20 GMT
• Title: Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models
• Abstract summary: We present the Hinge Tree (HRT) framework which reframes each oblique split as a nonlinear least-squares problem.<n>We propose HRT-Boost, a mathematically synergistic ensemble extension that node-level Newton updates with stagewise functional gradient descent.
• Score: 18.386166970880478
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning high-quality oblique decision trees remains a significant challenge due to the discrete and non-convex nature of split optimization. We present the Hinge Regression Tree (HRT) framework, which reframes each oblique split as a nonlinear least-squares problem over two linear predictors whose max/min envelope induces ReLU-like representation capacity. We show that the resulting node-level optimization can be interpreted as a damped Newton method, and we establish the monotonic decrease of the node objective for its backtracking line-search variant. We establish, theoretically, that HRT is a universal approximator with an explicit $O(δ^2)$ approximation rate. Building upon this base learner, we propose HRT-Boost, a mathematically synergistic ensemble extension that couples node-level Newton updates with stage-wise functional gradient descent. We show that this ensemble construction admits a stage-wise empirical risk reduction guarantee under the squared loss. Empirical evaluations on synthetic and real-world benchmarks show that HRT is highly competitive with established single-tree baselines, and HRT-Boost compares favorably with strong ensemble baselines and often yields substantially more compact models. The code is publicly available at https://github.com/Hongyi-Li-sz/HRT-Boost.

Related papers

• Reducing Learner Redundancy in Boosting via Residual Orthogonalization [18.700465769971434]
  Our framework tackles redundancy through two complementary mechanisms: Spectral Residual Projection (SRP) and Covariance-Regularized Weighting (CRW)<n>Experiments across ten benchmark datasets demonstrate that SCBoost delivers strong out-of-the-box performance.<n>This work reinterprets boosting through a geometric lens, suggesting that explicit redundancy control is a principled and necessary step toward more efficient ensemble architectures.
  arXiv  Detail & Related papers  (2026-06-16T06:13:59Z)
• A Riemannian Approach to Low-Rank Optimal Transport [10.296598409953278]
  Low-rank optimal transport (OT) mitigates the quadratic scaling of classical solvers, yet existing approaches rely heavily on first-order mirror-descent updates.<n>We propose a unified Riemannian geometric framework for low-rank OT, modeling balanced and unbalanced rank-$r$ positive factored couplings.<n>Our regularization-free first- and second-order solvers achieve faster convergence and superior performance over existing state-of-the-art low-rank OT solvers.
  arXiv  Detail & Related papers  (2026-06-10T14:17:08Z)
• Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption [4.52430575477004]
  We study the problem of robustly learning Gaussian Single Index Models (SIMs) in the presence of heavy-tailed noise.<n>We give the first robust recovery algorithm with near-linear sample and time complexity for generic non-monotonic link functions.
  arXiv  Detail & Related papers  (2026-05-28T07:21:04Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Hinge Regression Tree: A Newton Method for Oblique Regression Tree Splitting [18.562483381753804]
  We present the Hinge Regression Tree (HRT), which reframes each split as a non-linear least-squares problem over two linear predictors.<n>We analyze this node-level optimization and, for a backtracking line-search variant, prove that the local objective decreases monotonically and converges.<n>We show on synthetic and real-world benchmarks that HRT matches or outperforms single-tree baselines with more compact structures.
  arXiv  Detail & Related papers  (2026-02-05T06:49:01Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  We provide the first convergence guarantee for Optimistic Multiplicative Weights Update ($mathtOMWU$) in NLHF.<n>Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values.
  arXiv  Detail & Related papers  (2025-12-31T12:08:29Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Lassoed Tree Boosting [53.56229983630983]
  We prove that a gradient boosted tree algorithm with early stopping faster than $n-1/4$ L2 convergence in the large nonparametric space of cadlag functions of bounded sectional variation. Our convergence proofs are based on a novel, general theorem on early stopping with empirical loss minimizers of nested Donsker classes.
  arXiv  Detail & Related papers  (2022-05-22T00:34:41Z)
• Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
  We propose a gradient boosting algorithm for large-scale regression problems called textitGradient Boosted Binary Histogram Ensemble (GBBHE) based on binary histogram partition and ensemble learning. In the experiments, compared with other state-of-the-art algorithms such as gradient boosted regression tree (GBRT), our GBBHE algorithm shows promising performance with less running time on large-scale datasets.
  arXiv  Detail & Related papers  (2021-06-03T17:05:40Z)
• Stochastic tree ensembles for regularized nonlinear regression [0.913755431537592]
  This paper develops a novel tree ensemble method for nonlinear regression, which we refer to as XBART. By combining regularization and search strategies from Bayesian modeling with computationally efficient techniques, the new method attains state-of-the-art performance.
  arXiv  Detail & Related papers  (2020-02-09T14:37:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.