Timezone: »

 
Poster
Active Learning and Best-Response Dynamics
Maria-Florina F Balcan · Christopher Berlind · Avrim Blum · Emma Cohen · Kaushik Patnaik · Le Song

Wed Dec 10 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

We consider a setting in which low-power distributed sensors are each making highly noisy measurements of some unknown target function. A center wants to accurately learn this function by querying a small number of sensors, which ordinarily would be impossible due to the high noise rate. The question we address is whether local communication among sensors, together with natural best-response dynamics in an appropriately-defined game, can denoise the system without destroying the true signal and allow the center to succeed from only a small number of active queries. We prove positive (and negative) results on the denoising power of several natural dynamics, and also show experimentally that when combined with recent agnostic active learning algorithms, this process can achieve low error from very few queries, performing substantially better than active or passive learning without these denoising dynamics as well as passive learning with denoising.

[ PDF] 

Author Information

Maria-Florina F Balcan (Georgia Tech)
Christopher Berlind (Georgia Institute of Technology)
Avrim Blum (Toyota Technological Institute at Chicago)
Emma Cohen (Georgia Institute of Technology)
Kaushik Patnaik (Georgia Institute of Technology)
Le Song (Georgia Institute of Technology)

More from the Same Authors