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).
Stay in the loop.
Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.