## Abstract

We discuss the problem of finding a generalized sphere that encloses points originating from a single source. The points contained in such a sphere are within a maximal divergence from a center point. The divergences we study are known as the Bregman divergences which include as a special case both the Euclidean distance and the relative entropy. We cast the learning task as an optimization problem and show that it results in a simple dual form which has interesting algebraic properties. We then discuss a general algorithmic framework to solve the optimization problem. Our training algorithm employs an auxiliary function that bounds the dual's objective function and can be used with a broad class of Bregman functions. As a specific application of the algorithm we give a detailed derivation for the relative entropy. We analyze the generalization ability of the algorithm by adopting margin-style proof techniques. We also describe and analyze two schemes of online algorithms for the case when the radius of the sphere is set in advance.

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

Pages (from-to) | 388-402 |

Number of pages | 15 |

Journal | Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) |

Volume | 2777 |

DOIs | |

State | Published - 2003 |

Event | 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003 - Washington, DC, United States Duration: Aug 24 2003 → Aug 27 2003 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science