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

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.

• Publication year

  2014

• Venue

  Machine-mediated learning

• Publication date

  2014-05-29

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10994-014-5478-4arXiv 1405.7764
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Statistical Learning Theory

  2021cited by this paper
• Extremum Problems with Inequalities as Subsidiary Conditions

  2014cited by this paper
• Applications of Second Order Cone Programming

  2013cited by this paper
• Applications of Second Order Cone Programming

  2012cited by this paper
• Machine learning with operational costs

  2011influential reference
• On combining machine learning with decision making

  2011cited by this paper
• The Convex Geometry of Linear Inverse Problems

  2010cited by this paper
• Convex optimization

  2010cited by this paper
• Various thresholds for ℓ1-optimization in compressed sensing

  2009cited by this paper
• Unlabeled data: Now it helps, now it doesn't

  2008cited by this paper
• Improving Classification with Pairwise Constraints: A Margin-Based Approach

  2008cited by this paper
• On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization

  2008cited by this paper
• Learning and Inference with Constraints

  2008cited by this paper
• Incorporating prior knowledge in support vector machines for classification: A review

  2008cited by this paper
• Classification with partial labels

  2008cited by this paper
• Constraints as Prior Knowledge

  2008cited by this paper
• Semisupervised Image Classification With Laplacian Support Vector Machines

  2008cited by this paper
• Second Order Cone Programming Approaches for Handling Missing and Uncertain Data

  2006cited by this paper
• The Rademacher Complexity of Linear Transformation Classes

  2006cited by this paper
• Simpler knowledge-based support vector machines

  2006cited by this paper
• A PAC-Style Model for Learning from Labeled and Unlabeled Data

  2005influential reference
• The Generic Chaining

  2005cited by this paper
• Generalization Error Bounds Using Unlabeled Data

  2005cited by this paper
• Regularization and Semi-supervised Learning on Large Graphs

  2004cited by this paper
• Semi-supervised Learning with Penalized Probabilistic Clustering

  2004cited by this paper
• Semi-Supervised Learning on Riemannian Manifolds

  2004influential reference
• Rademacher and Gaussian Complexities: Risk Bounds and Structural Results

  2003cited by this paper
• Computing Gaussian Mixture Models with EM Using Equivalence Constraints

  2003cited by this paper
• Knowledge-Based Support Vector Machine Classifiers

  2002cited by this paper
• A Robust Minimax Approach to Classification

  2002cited by this paper
• Covering Number Bounds of Certain Regularized Linear Function Classes

  2002cited by this paper
• Agile Software Development

  2002cited by this paper
• Applications of second-order cone programming

  1998cited by this paper
• Refinement ofApproximate Domain Theories by Knowledge-Based Neural Networks

  1990cited by this paper
• Norms of Gaussian sample functions

  1976cited by this paper
• Circumscribing an Ellipsoid about the Intersection of Two Ellipsoids

  1968cited by this paper
• Entropy and "-capacity of sets in func-tional spaces

  1961cited by this paper
• Mikhail Bilenko

  year unknowncited by this paper
• Journal of Machine Learning Research X (200x) X-x Generalization Error Bounds in Semi-supervised Classification under the Cluster Assumption

  year unknowncited by this paper

• On Regularization and Inference with Label Constraints

  2023cites this paper
• Learning the state of the world: object-based world modeling for mobile manipulation robots

  2017cites this paper
• Interactions between learning and decision making

  2017cites this paper
• Interactions between learning and decision making

  2017cites this paper