For multivariate nonparametric regression, functional analysis-of-variance (ANOVA) modeling aims to capture the relationship between a response and covariates by decomposing the unknown function into various components, representing main effects, two-way interactions, etc. Such an approach has been pursued explicitly in smoothing spline ANOVA modeling and implicitly in various greedy methods such as MARS. We develop a new method for functional ANOVA modeling, based on doubly penalized estimation using total-variation and empirical-norm penalties, to achieve sparse selection of component functions and their knots. For this purpose, we formulate a new class of hierarchical total variations, which measures total variations at different levels including main effects and multi-way interactions, possibly after some order of differentiation. Furthermore, we derive suitable basis functions for multivariate splines such that the hierarchical total variation can be represented as a regular Lasso penalty, and hence we extend a previous backfitting algorithm to handle doubly penalized estimation for ANOVA modeling. We present extensive numerical experiments on simulations and real data to compare our method with existing methods including MARS, tree boosting, and random forest. The results are very encouraging and demonstrate considerable gains from our method in both prediction or classification accuracy and simplicity of the fitted functions.
Total variations. Use of total-variation penalties has often been restricted to univariate and bivariate functions in statistics and computer science, although mathematical theory of multivariate functions of bounded variations seems to be well studied . For univariate smoothing, @cite_9 studied regression splines using total-variation penalties with an arbitrary differentiation order @math . A closely related method is trend filtering . Additive modeling has also been pursued using total variations on univariate functions in low- and high-dimensional settings [e.g.,][] petersen2016convex,sadhanala2017additive,yang2018backfitting .
@cite_9
1989060270 2123513798 1773660948 2078214343
We study the problem of estimating high-dimensional regression models regularized by a structured sparsity-inducing penalty that encodes prior structural information on either the input or output variables. We consider two widely adopted types of penalties of this kind as motivating examples: (1) the general overlapping-group-lasso penalty, generalized from the group-lasso penalty; and (2) the graph-guided-fused-lasso penalty, generalized from the fused-lasso penalty. For both types of penalties, due to their nonseparability and nonsmoothness, developing an efficient optimization method remains a challenging problem. In this paper we propose a general optimization approach, the smoothing proximal gradient (SPG) method, which can solve structured sparse regression problems with any smooth convex loss under a wide spectrum of structured sparsity-inducing penalties. Our approach combines a smoothing technique with an effective proximal gradient method. It achieves a convergence rate significantly faster than the standard first-order methods, subgradient methods, and is much more scalable than the most widely used interior-point methods. The efficiency and scalability of our method are demonstrated on both simulation experiments and real genetic data sets. While total variation is among the most popular regularizers for variational problems, its extension to functions with values in a manifold is an open problem. In this paper, we propose the first algorithm to solve such problems which applies to arbitrary Riemannian manifolds. The key idea is to reformulate the variational problem as a multilabel optimization problem with an infinite number of labels. This leads to a hard optimization problem which can be approximately solved using convex relaxation techniques. The framework can be easily adapted to different manifolds including spheres and three-dimensional rotations, and allows to obtain accurate solutions even with a relatively coarse discretization. With numerous examples we demonstrate that the proposed framework can be applied to variational models that incorporate chromaticity values, normal fields, or camera trajectories. In recent years, there has been considerable theoretical development regarding variable selection consistency of penalized regression techniques, such as the lasso. However, there has been relatively little work on quantifying the uncertainty in these selection procedures. In this paper, we propose a new method for inference in high dimensions using a score test based on penalized regression. In this test, we perform penalized regression of an outcome on all but a single feature, and test for correlation of the residuals with the held-out feature. This procedure is applied to each feature in turn. Interestingly, when an @math penalty is used, the sparsity pattern of the lasso corresponds exactly to a decision based on the proposed test. Further, when an @math penalty is used, the test corresponds precisely to a score test in a mixed effects model, in which the effects of all but one feature are assumed to be random. We formulate the hypothesis being tested as a compromise between the null hypotheses tested in simple linear regression on each feature and in multiple linear regression on all features, and develop reference distributions for some well-known penalties. We also examine the behavior of the test on real and simulated data. We study trend filtering, a recently proposed tool of [SIAM Rev. 51 (2009) 339-360] for nonparametric regression. The trend filtering estimate is defined as the minimizer of a penalized least squares criterion, in which the penalty term sums the absolute @math th order discrete derivatives over the input points. Perhaps not surprisingly, trend filtering estimates appear to have the structure of @math th degree spline functions, with adaptively chosen knot points (we say appear'' here as trend filtering estimates are not really functions over continuous domains, and are only defined over the discrete set of inputs). This brings to mind comparisons to other nonparametric regression tools that also produce adaptive splines; in particular, we compare trend filtering to smoothing splines, which penalize the sum of squared derivatives across input points, and to locally adaptive regression splines [Ann. Statist. 25 (1997) 387-413], which penalize the total variation of the @math th derivative. Empirically, we discover that trend filtering estimates adapt to the local level of smoothness much better than smoothing splines, and further, they exhibit a remarkable similarity to locally adaptive regression splines. We also provide theoretical support for these empirical findings; most notably, we prove that (with the right choice of tuning parameter) the trend filtering estimate converges to the true underlying function at the minimax rate for functions whose @math th derivative is of bounded variation. This is done via an asymptotic pairing of trend filtering and locally adaptive regression splines, which have already been shown to converge at the minimax rate [Ann. Statist. 25 (1997) 387-413]. At the core of this argument is a new result tying together the fitted values of two lasso problems that share the same outcome vector, but have different predictor matrices.