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

DOI10.1007/S10994-014-5478-4MaRDI QIDQ747246zbMATH OpenOpenAlexFDO

Authors Theja Tulabandhula, Cynthia Rudin

Publication date 23 October 2015

Published in Machine Learning (Search for Journal in Brave)

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

zbMATH Keywords

supervised learningRademacher complexitycovering numbersgeneralization boundsstatistical learning theoryside knowledge

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

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.

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

Cites work

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

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)