Statistical Learnability of Generalized Additive Models based on Total Variation Regularization

2018/02/08 by Matsushima, Shin
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1802.03001

Abstract

A generalized additive model (GAM, Hastie and Tibshirani (1987)) is a nonparametric model by the sum of univariate functions with respect to each explanatory variable, i.e., f(\mathbf x) = ∑ f_j(x_j), where x_j∈ℝ is j-th component of a sample \mathbf x∈ ℝ^p. In this paper, we introduce the total variation (TV) of a function as a measure of the complexity of functions in L¹_{\rm c}(ℝ)-space. Our analysis shows that a GAM based on TV-regularization exhibits a Rademacher complexity of O(√((log p)/(m))), which is tight in terms of both m and p in the agnostic case of the classification problem. In result, we obtain generalization error bounds for finite samples according to work by Bartlett and Mandelson (2002).

Related

• Measuring Complexity of Learning Schemes Using Hessian-Schatten Total Variation
• Lean Formalization of Generalization Error Bound by Rademacher Complexity
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models
• Learning rates for the risk of kernel based quantile regression estimators in additive models
• Regularization and the small-ball method II: complexity dependent error rates