Timezone: »
Spotlight
Boosting Algorithms for Maximizing the Soft Margin
Manfred K. Warmuth · Karen Glocer · Gunnar Rätsch
We present a novel boosting algorithm, called Softboost, designed for sets of binary labeled examples that are not necessarily separable by convex combinations of base hypotheses. Our algorithm aims to achieve robustness by \emph{capping} the distributions on the examples. Our update of the distribution is motivated by minimizing a relative entropy subject to the capping constraints and constraints on the edges of the obtained base hypotheses. The capping constraints imply a soft margin in the dual optimization problem and our algorithm produces a convex combination of hypotheses whose \emph{soft margin} is within $\delta$ of the optimum. We employ relative entropy projection methods to prove an $O(\frac{\ln N}{\delta^2})$ iteration bound for our algorithm, where $N$ is number of examples.
Author Information
Manfred K. Warmuth (Google Brain)
Karen Glocer (UC Santa Cruz)
Gunnar Rätsch (ETH Zürich)
Related Events (a corresponding poster, oral, or spotlight)
-
2007 Poster: Boosting Algorithms for Maximizing the Soft Margin »
Tue Dec 4th 06:30 -- 06:40 PM Room None
More from the Same Authors
-
2020 Poster: Reparameterizing Mirror Descent as Gradient Descent »
Ehsan Amid · Manfred K. Warmuth -
2019 Workshop: Minding the Gap: Between Fairness and Ethics »
Igor Rubinov · Risi Kondor · Jack Poulson · Manfred K. Warmuth · Emanuel Moss · Alexa Hagerty -
2019 Poster: Robust Bi-Tempered Logistic Loss Based on Bregman Divergences »
Ehsan Amid · Manfred K. Warmuth · Rohan Anil · Tomer Koren -
2018 Poster: Leveraged volume sampling for linear regression »
Michal Derezinski · Manfred K. Warmuth · Daniel Hsu -
2018 Spotlight: Leveraged volume sampling for linear regression »
Michal Derezinski · Manfred K. Warmuth · Daniel Hsu -
2017 Poster: Online Dynamic Programming »
Holakou Rahmanian · Manfred K. Warmuth -
2017 Poster: Unbiased estimates for linear regression via volume sampling »
Michal Derezinski · Manfred K. Warmuth -
2017 Spotlight: Unbiased estimates for linear regression via volume sampling »
Michal Derezinski · Manfred K. Warmuth -
2014 Workshop: Second Workshop on Transfer and Multi-Task Learning: Theory meets Practice »
Urun Dogan · Tatiana Tommasi · Yoshua Bengio · Francesco Orabona · Marius Kloft · Andres Munoz · Gunnar Rätsch · Hal Daumé III · Mehryar Mohri · Xuezhi Wang · Daniel Hernández-lobato · Song Liu · Thomas Unterthiner · Pascal Germain · Vinay P Namboodiri · Michael Goetz · Christopher Berlind · Sigurd Spieckermann · Marta Soare · Yujia Li · Vitaly Kuznetsov · Wenzhao Lian · Daniele Calandriello · Emilie Morvant -
2014 Workshop: Machine Learning for Clinical Data Analysis, Healthcare and Genomics »
Gunnar Rätsch · Madalina Fiterau · Julia Vogt -
2014 Poster: The limits of squared Euclidean distance regularization »
Michal Derezinski · Manfred K. Warmuth -
2014 Spotlight: The limits of squared Euclidean distance regularization »
Michal Derezinski · Manfred K. Warmuth -
2013 Workshop: Large Scale Matrix Analysis and Inference »
Reza Zadeh · Gunnar Carlsson · Michael Mahoney · Manfred K. Warmuth · Wouter M Koolen · Nati Srebro · Satyen Kale · Malik Magdon-Ismail · Ashish Goel · Matei A Zaharia · David Woodruff · Ioannis Koutis · Benjamin Recht -
2012 Poster: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2012 Session: Oral Session 4 »
Gunnar Rätsch -
2012 Spotlight: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2011 Workshop: Machine Learning in Computational Biology »
Jean-Philippe Vert · Gunnar Rätsch · Yanjun Qi · Tomer Hertz · Anna Goldenberg · Christina Leslie -
2011 Poster: Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation »
Nico Goernitz · Christian Widmer · Georg Zeller · Andre Kahles · Soeren Sonnenburg · Gunnar Rätsch -
2011 Poster: Learning Eigenvectors for Free »
Wouter M Koolen · Wojciech Kotlowski · Manfred K. Warmuth -
2010 Workshop: Machine Learning in Computational Biology »
Gunnar Rätsch · Jean-Philippe Vert · Tomer Hertz · Yanjun Qi -
2010 Poster: Repeated Games against Budgeted Adversaries »
Jacob D Abernethy · Manfred K. Warmuth -
2008 Workshop: Machine Learning in Computational Biology »
Gal Chechik · Christina Leslie · Quaid Morris · William S Noble · Gunnar Rätsch -
2008 Mini Symposium: Machine Learning in Computational Biology »
Gal Chechik · Christina Leslie · Quaid Morris · William S Noble · Gunnar Rätsch -
2008 Poster: An empirical Analysis of Domain Adaptation Algorithms for Genomic Sequence Analysis »
Gabriele B Schweikert · Christian Widmer · Bernhard Schölkopf · Gunnar Rätsch -
2007 Workshop: Machine Learning in Computational Biology (Part 2) »
Gal Chechik · Christina Leslie · Quaid Morris · William S Noble · Gunnar Rätsch · Koji Tsuda -
2007 Workshop: Machine Learning in Computational Biology (Part 1) »
Gal Chechik · Christina Leslie · Quaid Morris · William S Noble · Gunnar Rätsch · Koji Tsuda -
2006 Workshop: New Problems and Methods in Computational Biology »
Gal Chechik · Quaid Morris · Koji Tsuda · Gunnar Rätsch · Christina Leslie · William S Noble -
2006 Poster: Large Scale Hidden Semi-Markov SVMs »
Gunnar Rätsch · Soeren Sonnenburg -
2006 Poster: Randomized PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension »
Manfred K. Warmuth · Dima Kuzmin -
2006 Demonstration: SHOGUN Machine Learning Toolbox »
Soeren Sonnenburg · Gunnar Rätsch