Structured Sparsity and Generalization
arXiv:1108.3476
Abstract
We present a data dependent generalization bound for a large class of regularized algorithms which implement structured sparsity constraints. The bound can be applied to standard squared-norm regularization, the Lasso, the group Lasso, some versions of the group Lasso with overlapping groups, multiple kernel learning and other regularization schemes. In all these cases competitive results are obtained. A novel feature of our bound is that it can be applied in an infinite dimensional setting such as the Lasso in a separable Hilbert space or multiple kernel learning with a countable number of kernels.
Cited by in corpus (18)
- Nonparametric sparsity and regularization
- Regularization and the small-ball method II: complexity dependent error rates
- Partition-wise Linear Models
- Asymptotic Confidence Regions for High-dimensional Structured Sparsity
- An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning
- Scalable Matrix-valued Kernel Learning for High-dimensional Nonlinear Multivariate Regression and Granger Causality
- Classification with Sparse Overlapping Groups
- Sharp Oracle Inequalities for Square Root Regularization
- New Perspectives on k-Support and Cluster Norms
- Stochastic inertial primal-dual algorithms
- Meta-Learning with Network Pruning
- Efficient Regularized Piecewise-Linear Regression Trees
- On Regularized Square-root Regression Problems: Distributionally Robust Interpretation and Fast Computations
- Learning with Optimal Interpolation Norms
- Regularization for Multiple Kernel Learning via Sum-Product Networks
- Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint
- Conic Multi-Task Classification
- Multi-Task Classification Hypothesis Space with Improved Generalization Bounds