Dimensionality Dependent PAC-Bayes Margin Bound

2012-12-01 · NeurIPS 2012 12 · Chi Jin, Li-Wei Wang

Margin is one of the most important concepts in machine learning. Previous margin bounds, both for SVM and for boosting, are dimensionality independent. A major advantage of this dimensionality independency is that it can explain the excellent performance of SVM whose feature spaces are often of high or infinite dimension. In this paper we address the problem whether such dimensionality independency is intrinsic for the margin bounds. We prove a dimensionality dependent PAC-Bayes margin bound. The bound is monotone increasing with respect to the dimension when keeping all other factors fixed. We show that our bound is strictly sharper than a previously well-known PAC-Bayes margin bound if the feature space is of finite dimension; and the two bounds tend to be equivalent as the dimension goes to infinity. In addition, we show that the VC bound for linear classifiers can be recovered from our bound under mild conditions. We conduct extensive experiments on benchmark datasets and find that the new bound is useful for model selection and is significantly sharper than the dimensionality independent PAC-Bayes margin bound as well as the VC bound for linear classifiers.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Model Selection

Methods 이 논문이 사용한 방법론

SVM A Support Vector Machine, or SVM, is a non-parametric supervised learning model. For non-linear classification and regression, they utilise the kernel trick to map inputs…

PAC-Bayes Analysis of Multi-view Learning

2014-06-21 · Shiliang Sun, John Shawe-Taylor, Liang Mao

This paper presents eight PAC-Bayes bounds to analyze the generalization performance of multi-view classifiers. These bounds adopt data dependent Gaussian priors which emphasize classifiers with high view agreements. The…

MULTI-VIEW LEARNING

Exact Dimensionality Selection for Bayesian PCA

2017-03-08 · Charles Bouveyron, Pierre Latouche, Pierre-Alexandre Mattei

We present a Bayesian model selection approach to estimate the intrinsic dimensionality of a high-dimensional dataset. To this end, we introduce a novel formulation of the probabilisitic principal component analysis mode…

Model Selection

Prior-dependent analysis of posterior sampling reinforcement learning with function approximation

2024-03-17 · Yingru Li, Zhi-Quan Luo

This work advances randomized exploration in reinforcement learning (RL) with function approximation modeled by linear mixture MDPs. We establish the first prior-dependent Bayesian regret bound for RL with function appro…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Breaking the curse of dimensionality for linear rules: optimal predictors over the ellipsoid

2025-09-25 · Alexis Ayme, Bruno Loureiro arxiv

In this work, we address the following question: What minimal structural assumptions are needed to prevent the degradation of statistical learning bounds with increasing dimensionality? We investigate this question in th…

Maximum Margin Multiclass Nearest Neighbors

2014-01-30 · Aryeh Kontorovich, Roi Weiss

We develop a general framework for margin-based multicategory classification in metric spaces. The basic work-horse is a margin-regularized version of the nearest-neighbor classifier. We prove generalization bounds that …

Generalization Bounds