Generalization bounds for learning with linear, polygonal, quadratic and conic side knowledge

DOI10.1007/S10994-014-5478-4zbMATH Open1377.68213arXiv1405.7764OpenAlexW2089170859MaRDI QIDQ747246FDOQ747246

Authors: Theja Tulabandhula, Cynthia Rudin 

Publication date: 23 October 2015

Published in: Machine Learning (Search for Journal in Brave)

Abstract: In this paper, we consider a supervised learning setting where side knowledge is provided about the labels of unlabeled examples. The side knowledge has the effect of reducing the hypothesis space, leading to tighter generalization bounds, and thus possibly better generalization. We consider several types of side knowledge, the first leading to linear and polygonal constraints on the hypothesis space, the second leading to quadratic constraints, and the last leading to conic constraints. We show how different types of domain knowledge can lead directly to these kinds of side knowledge. We prove bounds on complexity measures of the hypothesis space for quadratic and conic side knowledge, and show that these bounds are tight in a specific sense for the quadratic case.

Full work available at URL: https://arxiv.org/abs/1405.7764

Recommendations

• Learning with side information: PAC learning bounds
• Learning with generalization capability by kernel methods of bounded complexity
• On-line learning with linear loss constraints.
• 10.1162/153244302760200704
• PAC-Bayes bounds for supervised classification

zbMATH Keywords

supervised learningRademacher complexitycovering numbersgeneralization boundsstatistical learning theoryside knowledge

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Title not available (Why is that?)
• On combining machine learning with decision making
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Generic Chaining
• 10.1162/153244303321897690
• Title not available (Why is that?)
• Applications of second-order cone programming
• Integrals which are convex functionals. II
• 10.1162/153244303321897726
• The convex geometry of linear inverse problems
• 10.1162/153244302760200713
• Semi-supervised learning on Riemannian manifolds
• Second order cone programming approaches for handling missing and uncertain data
• Generalization error bounds in semi-supervised classification under the cluster assumption
• Learning Theory
• Title not available (Why is that?)
• Learning Theory
• Learning Theory
• Machine Learning with Operational Costs
• High-Energy Electron-Electron Scattering
• Title not available (Why is that?)
• The Rademacher Complexity of Linear Transformation Classes

Cited In (1)

• Learning with side information: PAC learning bounds

This page was built for publication: Generalization bounds for learning with linear, polygonal, quadratic and conic side knowledge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q747246)