UC Berkeley

We study a class of regression methods in machine learning that construct estimators as finite linear combinations of data-adaptively selected atoms, particularly multivariate adaptive regression splines (MARS) and one of the most widely used gradient boosting methods, XGBoost. Despite their popularity and empirical success, the theoretical properties of these methods remain poorly understood, largely due to the greedy procedures used in their estimator construction, which make rigorous analysis challenging.We study these methods through a unifying infinite-dimensional optimization framework, in which functions are expressed as integrals of atoms with respect to finite signed measures. Within this framework, we consider a natural complexity measure given by the total variation of the representing measure, which serves as an infinite-dimensional analogue of the ` 1 norm of finite-dimensional coefficient vectors. This leads to an infinite-dimensional lasso formulation, which provides an idealized optimization perspective on these methods while abstracting away the greedy procedures used in practice.We apply this framework to MARS and XGBoost. For MARS, it yields a variant of the original method that is amenable to theoretical analysis and can perform competitively in practice, albeit at higher computational cost. For XGBoost, it yields an optimization problem equivalent to the original formulation, but posed over a larger function class. This clarifies the function class implicitly underlying the method. In both settings, we show that the associated function classes and complexity measures admit characterizations in terms of smoothness. These results highlight a previously underappreciated connection between MARS, XGBoost, and smoothness-based nonparametric regression.We also introduce a related shape-constrained regression method, termed totally concave regression, obtained by imposing sign constraints on the representing measure rather than the total variation constraint. It provides a multivariate extension of concave regression that differs from existing approaches based on classical notions of concavity. The proposed method overcomes several limitations of classical approaches and offers a computationally and theoretically attractive alternative in multi-dimensional settings.We study the statistical properties of the resulting constrained least squares estimators for all three methods—MARS, XGBoost, and totally concave regression. We show that our variant of MARS and totally concave regression can be computed via convex optimization, although they are formulated as infinite-dimensional optimization problems. Moreover, we establish rates of convergence for all three methods under standard regression models. In particular, we show that these estimators achieve nearly dimension-free rates, up to logarithmic factors. These results provide theoretical support for the effectiveness of these methods, complementing their strong empirical performance.