[Lisa_seminaires] Fwd: a talk by Valentine Kabanets

Yoshua Bengio yoshua.umontreal at gmail.com
Ven 24 Juin 10:11:55 EDT 2016


---------- Forwarded message ----------
From: Pierre McKenzie <mckenzie at iro.umontreal.ca>
Date: 2016-06-24 9:42 GMT-04:00
Subject: a talk by Valentine Kabanets
To: Yoshua Bengio <bengioy at iro.umontreal.ca>, Pascal Vincent <
vincentp at iro.umontreal.ca>, christopher.pal at polymtl.ca, Aaron Courville <
aaron.courville at umontreal.ca>, roland.memisevic at umontreal.ca,
lcharlin at gmail.com
Cc: Sylvie Hamel <hamelsyl at iro.umontreal.ca>


Bonjour collègues du MILA,

If you think some members of your lab might be interested, please don't
hesitate to distribute the announcement.

Regards,
Pierre McKenzie

------------------------------

Tuesday June 28 @ 11:00 in room 3195, pavillon André-Aisenstadt of U de M
Speaker: Valentine Kabanets (Simon Fraser)
Title: Learning Algorithms from Natural Proofs

Abstract:
Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan
(J ACM, 1993) gave a quasipolytime learning algorithm for AC^0
(constant-depth circuits with AND, OR, and NOT gates), in the PAC model
over the uniform distribution. It was an open question to get a learning
algorithm (of any kind) for the class of AC^0[p] circuits (constant-depth,
with AND, OR, NOT, and mod-p gates for a prime p).

Our main result is a quasipolytime learning algorithm for AC^0[p] in the
PAC model over the uniform distribution with membership queries. This
algorithm is an application of the general connection between natural
properties (in the sense of Razborov and Rudich (JCSS, 1997)) and learning
algorithms that we obtain. We show that a natural circuit lower bound
against any (sufficiently powerful) circuit class yields a learning
algorithm for the same circuit class. Then the known lower bounds against AC
^0[p] by Razborov (1987) and Smolensky (1987), shown to be natural by
Razborov and Rudich, imply our main result.

Joint work with Marco Carmosino (UCSD), Russell Impagliazzo (UCSD), and
Antonina Kolokolova (MUN).
-------------- section suivante --------------
Une pièce jointe HTML a été nettoyée...
URL: http://webmail.iro.umontreal.ca/pipermail/lisa_seminaires/attachments/20160624/a9f498c1/attachment.html 


Plus d'informations sur la liste de diffusion Lisa_seminaires