### Abstract

We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension. These results also imply efficient agnostic-PAC learning of these hypotheses classes. In particular we give an O(n^{min(α-1,2κ-1)}log n) algorithm that solves the m.d.p. for two-dimensional convex κ-gon hypotheses (α is the VC dimension of the implied set system, κ is constant), and an O(n^{3κ-1} log n) algorithm for convex κ-hedra hypotheses in three dimensions. We also give an O(κ^{2}n^{2} logn) algorithm that solves the m.d. p. for planar κ-stripes, and give an approach to approximation algorithms.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 |

Publisher | Association for Computing Machinery, Inc |

Pages | 329-336 |

Number of pages | 8 |

ISBN (Electronic) | 0897917235, 9780897917230 |

DOIs | |

State | Published - Jul 5 1995 |

Event | 8th Annual Conference on Computational Learning Theory, COLT 1995 - Santa Cruz, United States Duration: Jul 5 1995 → Jul 8 1995 |

### Publication series

Name | Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 |
---|---|

Volume | 1995-January |

### Other

Other | 8th Annual Conference on Computational Learning Theory, COLT 1995 |
---|---|

Country | United States |

City | Santa Cruz |

Period | 7/5/95 → 7/8/95 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Artificial Intelligence
- Software

## Fingerprint Dive into the research topics of 'Concept learning with geometric hypotheses'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995*(pp. 329-336). (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January). Association for Computing Machinery, Inc. https://doi.org/10.1145/225298.225338