Active and passive learning of linear separators under log-concave distributions

author: Maria-Florina Balcan, College of Computing, Georgia Institute of Technology
published: Aug. 9, 2013,   recorded: June 2013,   views: 7712
Categories

Slides

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Bibliography

Description

We prove that active learning provides an exponential improvement over PAC (passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a computationally efficient PAC algorithm with optimal (up to a constant factor) sample complexity for such problems. This resolves an open question of (Long, 1995, 2003; Bshouty et al., 2009) concerning the sample complexity of efficient PAC algorithms under the uniform distribution in the unit ball. Moreover, it provides the first bound for a polynomial-time PAC algorithm that is tight for an interesting infinite class of hypothesis functions under a general class of data-distributions, providing significant progress towards a long standing open question of (Ehrenfeucht et al., 1989; Blumer et al., 1989). We also provide new bounds for active and passive learning in the case that the data might not be linearly separable, both in the agnostic case and and under the Tsybakov low-noise condition. To derive our results, we provide new structural results for (nearly) log-concave distributions, which might be of independent interest as well.

See Also:

Download slides icon Download slides: colt2013_balcan_learning_01.pdf (758.5 KB)


Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Leonora Brioschi, March 31, 2022 at 8:07 p.m.:

https://toptrans.eu/ vous offre un moyen de trouver d'autres personnes intéressées par une relation sans le drame potentiel associé à la découverte de ce que quelqu'un veut vraiment. Pour participer au site, il faut comprendre que les rencontres sexuelles sont l'objectif final, plutôt que de faire la cour ou de faire des rencontres. Des réseaux sociaux pour le sexe ? Ça nous paraît bien.


Comment2 Giana Lombardo, April 1, 2022 at 8:07 p.m.:

https://bakecaincontri.eu/ cuenta con herramientas de búsqueda local y foros de discusión para permitir contactos instantáneos en línea, y todos los miembros activos están en la escena de las citas en línea en busca de sexo, no de una relación comprometida, por lo que no hay razón para ser tímido en este sitio de citas.


Comment3 Bregtje Looijmans, April 5, 2022 at 8:07 p.m.:

https://speeddaten.eu/ is een ongelooflijk populaire kennismakingsoptie die mensen aantrekt met een kans om anderen te leren kennen in slechts een paar minuten


Comment4 Lea Kasischke, April 6, 2022 at 8:08 p.m.:

https://hobbynutten.eu/deutschland/be... ist die Dating-App, die ich empfehlen würde. Wenn man nur sehr wenig über eine Person weiß, kann die erste Kontaktaufnahme zu einer großen Herausforderung werden. Sie müssen sich durch ein Meer von Profilen wühlen, was es leicht macht, Menschen zu übergehen, denen man unter anderen Umständen vielleicht eine Chance gegeben hätte.


Comment5 Rut Martinsson, May 12, 2022 at 8:08 p.m.:

https://klubb6.eu/ är en av de äldsta och därmed mest populära dejtingsajterna. De är stolta över att vara den bästa tillfälliga dejtingsajten för att hitta vuxna singlar för alla arrangemang du söker. Den här dejtingsajten erbjuder swingers, icke-monogama förhållanden, trekanter och experimentella upplevelser. Vare sig du letar efter en relation utan förbehåll, ett one night stand för att krydda ditt äktenskap eller en snabb flört, kommer du att hitta massor av alternativ och arrangemang på den här webbplatsen.


Comment6 Louise Berglund, May 16, 2022 at 8:07 p.m.:

https://transsex.se/ förbättrar ständigt sina tjänster. Webbplatsen främjar en säker och trygg dejtingmiljö för sina medlemmar. Antalet falska profiler är minimalt och du kommer inte att uppleva några trakasserier här.


Comment7 Julia Pettersson, May 18, 2022 at 8:08 p.m.:

https://sexxxx.se/ er en anden tjeneste, der forbinder dig med online ledsagere og er et godt alternativ til andre escortwebsteder. En vigtig funktion, der adskiller dette websted fra sine konkurrenter, er dets live chat-funktion.

Write your own review or comment:

make sure you have javascript enabled or clear this field: