Statistical Learnability of Generalized Additive Models based on Total Variation Regularization.

A generalized additive model (GAM, Hastie and Tibshirani (1987)) is anonparametric model by the sum of univariate functions with respect to eachexplanatory variable, i.e., $f({\mathbf x}) = \sum f_j(x_j)$, where$x_j\in\mathbb{R}$ is $j$-th component of a sample ${\mathbf x}\in\mathbb{R}^p$. In this paper, we introduce the total variation (TV) of afunction as a measure of the complexity of functions in $L^1_{\rmc}(\mathbb{R})$-space. Our analysis shows that a GAM based on TV-regularizationexhibits a Rademacher complexity of $O(\sqrt{\frac{\log p}{m}})$, which istight in terms of both $m$ and $p$ in the agnostic case of the classificationproblem. In result, we obtain generalization error bounds for finite samplesaccording to work by Bartlett and Mandelson (2002).